A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [linear-programming]

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

1,441 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
47 views

### Simplex algorithm calculation time exponential rise

I am building an energy-system-model with python/pyomo. It is basically creating an optimization problem (LP) in following form: ...
353 views

### Could I have two optimal solutions - linear programming problem?

A company produces two different products. They require two types of ingredients: M and N. The first product require 90 grams of the ingredient M and 10 grams of the ingredient N. The second product ...
47 views

### First step of simplex algorithm

I have the following linear program: Maximize $15x + 2y + z$ subject to $$x \le 10 \\ x + y \le 17 \\ 2x + 3 \le 25 \\ y + z \ge 11$$ I created the following Simplex Tableau: ...
122 views

### LP-problem simplex with 3 variables

I have this LP-problem which I need to solve using simplex calculations. $$\max Z = 12x_1 + 18x_2 + 10x_3$$ when, \begin{align} 2x_1 + 3x_2 + 4x_3 &= 50\\ -x_1 + x_2 + x_3 &= 0\\ -x_2 + \...
239 views

### Transforming a linear program into its canonical form for use in the simplex algorithm

A typical example of a LP in my lectures looks like this: From what I've learnt, we are ready to implement the simplex algorithm on this LP, since $x_3, x_4, x_5$ all have positive signs, and so are ...
98 views

300 views

### Use Farkas' lemma to prove no nonnegative solution exists

Show that the system of equations does not have a nonnegative solution: $\left\{\begin{matrix} x + y + z = 0\\ x - y - 2z = 0\\ x + 2y +3z = 0\\ 2x + 2y + z = 1 \end{matrix}\right.$ I want to ...
294 views

### Proof of binary solution of a linear program with specific structure

When solving instances of the following linear program (LP), I always get an integral (actually binary) solution. Is it just a coincidence or is it possible to prove that there always exists a binary ...
62 views

### Is there a way to reduce a set of linear inequalities representing a set of vectors in $\{0,1\}^n$?
Given a fixed number $r$, such that a vector $v_i \in \{1,0\}^n$ has exactly $r$ ones and $n-r$ zeroes, and a number of inequalities, (say $I$ is this set of inequalities) representing a set $J$ of ...
To be as specific as possible, I have a subspace $I \subset R^{14}$ of dimension $3$ and an $11\times14$ matrix $A$ with linearly independent rows spanning the orthogonal complement of $I$. I have an ...