# Questions tagged [linear-programming]

Questions on linear programming, the optimization of a linear function subject to linear constraints.

4,630 questions
Filter by
Sorted by
Tagged with
42 views

### Is my method equivalent to my lecturers?

In lectures we were shown how to 'breakdown' a piece-wise linear function so that it can be used as part of a linear program. Now, my lecturer wrote the function as $a=f(x)=\max(0,55x-11000)$ and in ...
• 579
19 views

### Is $\{ x \in \mathbb{R}^2 \mid x \ge 0, v^Tx \le 1 \quad (\forall v \in \mathbb{R}^2 : \lvert\lvert v \rvert\rvert = 1) \}$ a polyhedron?

I am working on the following exercise: Consider $$P := \{ x \in \mathbb{R}^2 \mid x \ge 0, v^Tx \le 1 \quad (\forall v \in \mathbb{R}^2 : \lvert\lvert v \rvert\rvert = 1) \}$$ Is $P$ a polyhedron? ...
• 2,462
1 vote
8 views

### Is there a result on the maximum value of the dual variable for a parametric LP in terms of the parameters of the LP?

I am working with a linear program of the following kind: \begin{array}[t]{l} \min c^{\top} x\\ s.t.\\ \quad A x = b\\ \quad 0 \le x \le x^{u} \end{array} Can I find out the upper limit of the shadow ...
• 11
1 vote
20 views

### Theorem of Alternatives proof only one of the systems is solvable

Let $A \in R^{nxm}$, $x \in R^n$, $c,y \in R^m$ show that, either I) $Ax=c$ II) $A^Ty=0, c^Ty=1$ is solvable I'm completely new to the theorem of alternatives, so my attempt is: If I is solvable ...
1 vote
29 views

### The effect that slightly increasing a variable has on the optimal solution

I am going through a past exam paper that doesn't have a mark scheme provided. I am struggling to figure out how you would do part b. Can anyone explain how you would go about getting an answer for ...
• 579
1 vote
51 views

### how can I linearize a constraint of the form sum(min(x(i),y(i))) for a linear optimisation problem?

I have an linear optimisation problem and I'd like to impose a constraint of the following form: $∑_{i=0}^N min⁡(x_i,y_i)≥C$ where x_i,y_i are rational numbers greater or equal to 0. how can I ...
• 11
21 views

### In this simplex algorithm tableau, what are the basic variables?

At some point while running the simplex algorithm, we find this tableau: Would I be correct in saying that at this stage, our basic variables are $x_4,x_3,x_6$ as they are the only ones not equal to ...
• 579
57 views

### Proof that markov chain equilibrium using Farkas' lemma

Given a transition matrix for markov chain $P \in \mathbb R^{dxd}$ such that $$P_{i,j} \geq 0,\quad 1 \leq (i,j) \leq d, \quad \sum_{j=1 \in d }P_{i,j}$$ and $i=1,....,d$. Let $x_{0}$ be ...
22 views

### How to find such a Markov matrix?

Suppose $A$ is a $m\times n$ Markov matrix, and $C$ is a $m\times k$ Markov matrix. How to decide (analytically or numerically) whether there is a $n\times k$ Markov matrix such that $AB=C$? I feel ...
• 175
36 views

### code a program in matlab (or python) that: [closed]

generate 10 random values ​​from 0 to 100 Place these 10 values ​​(in order) on the diagonal of a square matrix that we will call A. Generate a 10x10 matrix C with random values. In the problem, each ...
22 views

### a set of linear constraints defines a smaller and smaller set, to what extent?

Let's say I have a set of linear constraints over $x \in \mathbb{R}^d$ in the form of $Ax \le b$. Is there a way to know the volume'' of the feasible set (in the sense that every two points in the ...
• 143
36 views

### How to graph an interval of real numbers?

Assume that intergers $m$ and $n$ satisfy $2|m|+3|n-1|\leq 7$. $m+n$ is maximum when $(m,n) = (3,?), (?,?)$ and its maximum value is $?$ given the above question the first thing i tried was ...
• 47
1 vote
17 views

### Stochastic Portfolio Optimization with Recourse

I am given the following problem from a tutorial in my course: (Portfolio Optimization with Recourse). You have £10,000 to invest (without short selling) in a portfolio composed of eight leading ...
• 191
34 views

1 vote
32 views

### Computing the dual of an LP with equality constraints

I am having a linear program in the form : \begin{cases} \min_x\ \ -5x_1 + 27.5x_2 + 4.5x_3 + 12x_4\ \ \mathrm{s.t.}\ \\ \ \\ \qquad\qquad 0.25x_1 − 2.75x_2 − 1.25x_3 + 4.5x_4 + 0.5x_5 = 0\\ \...
• 605
31 views

### Solving a linear programming problem with 26 variables - is it possible?

I need to minimise two equations with 26 variables relative to some constraints. I am not very familiar with linear programming, but understand that it is probably the correct way to approach my ...
• 11
45 views

### Polyhedra intersection

If $A$ and $B$ are polyhedra, how do we show that the intersection $A ∩ B$ is a polyhedron. Does the same apply if they are both polytopes, will the intersection $A ∩ B$ also be a polytope? The ...
• 47
27 views

30 views

• 2,370
22 views

### How can I convert non-linear constraint to linear one?

Problem: Suppose I have $n$ finished products and each product has its own completion time, such as C$_i$ (C$_i$=completion time of product $i$, where $i=\{1,2,...,n\}$). These products will be ...
• 15
17 views

### dual of a LP constraint

Consider the minimization problem minax1+bx2 s.t: x1(i,j)-sum(i,x1(i,j))<=0 for each j that both varibales in the constraint is equivalent. so what is the constraint for x in the dual problem? how ...
24 views

### Reduce minmax problem to linear problem

A is mxn matrix, c is n vector and b is m vector. Convert following problem to linear problem $$max_{x \ge 0} min_{y \ge 0} (c^Tx - y^TAx + b^Ty)$$ I think I can write min to max by just changing sign ...
1 vote
60 views

### Linear Programming - Motivation behind the Dual Simplex Method

I am trying to understand the motivation behind the Dual Simplex Method. However, I have run into some roadblocks while understanding the rationale behind the Dual Simplex Method. This is my current ...
• 8,444
61 views

### How many slack variables need to be introduced?

So I was trying to solve this exercise (from DPV book) I modeled the problem as such: minimize : $4x_1 + x_2 + 2x_3 + 3x_4$ s.t: $x_1 + x_2 = 8$ (Mexico's production) $x_3 + x_4 = 15$ (Cansa's ...
• 605
I've been biting my teeth out, trying to find an example of the following. Is it even possible? Consider two LPs $$(P1) \ \max \{c^Tx|Ax\leq b, x\geq 0\} \\ (P2)\ \max \{c^Tx|Ax\leq \tilde{b}, x\geq ... 0 votes 0 answers 14 views ### Linear optimization problem with affine subspaces I have this fun linear optimization problem for you! Let u and v in {\mathbb R^n} be two non-collinear vectors where \|\vec u\|=1 and \|\vec v\|=1 and let \alpha and \beta two real ... 0 votes 1 answer 20 views ### Projection onto union of two affine subsets Let \ C_1=\{\ x\in {R^n} \ |\ \langle u,x\rangle\leq\alpha\ \}\  and \ C_2=\{\ x\in {R^n} \ |\ \langle u,x\rangle\leq\beta\ \}.  Give the orthogonal projection of x\in{R^n} onto \ C_1\cup C_2.... 1 vote 2 answers 64 views ### Minimize sum of absolute value with linear constraint Consider a minimization problem:$$ \begin{aligned} & \min \sum_{i=1}^n |x_i|,\\ & A x = b, \end{aligned} $$where A is an m\times n matrix of rank m. I know that the minimum points ... 0 votes 0 answers 46 views ### Representation theorem linear programming What I have read is: The General Representation Theorem states that every point in a convex set can be represented as a convex combination of extreme points, plus a nonnegative linear combination of ... • 1,424 0 votes 0 answers 13 views ### What is a general way to find Direction of unboundedness of a linear program. One of the way I know is Ad=0 then d is direction of unboundedness where A is the constraint matrix and Ax=b. In my exam there was question, to first convert problem into standard form, determine 2 ... 0 votes 0 answers 26 views ### 1-norm maximization - is this a linear program? I have two conditional probability distributions \tilde{Q}_{Y|X} and Q_{Y|X} and I am trying to find the probability distribution P_X that maximizes the quantity below$$\|(\tilde{Q}_{Y|X}(y|x) -...
Im trying to solve the following problem First I write out the objective function with t=1=October,...,4=January: $x_t=$ no. of units produced during month t $i_t=$ the amount of inventory at the ...