# Questions tagged [linear-programming]

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

1,443 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
601 views

### Solving 2 × 2 Matrix Games Using Geometric Methods

I think my text book may be wrong. I am trying to learn how to solve matrix games using a geometric method. So I am given the matrix $$\begin{pmatrix}-2 & 4 \\1 & -3\end{pmatrix}$$ So the ...
152 views

### Fourier Motzkin Elimination and totally unimodularity

Suppose $A\in \mathbb R^{m\times n}$ and $b\in \mathbb R^m$, and $A$ is totally unimodular (TUM). For the system $$Ax\leq b,$$ suppose I use Fourier-Motzkin elimination to eliminate first $k$ ...
1k views

### Geometric interpretation of linear programming dual

Is there a geometric interpretation of the linear programming dual in terms of the primal? I feel like without some sort of intuition of it, I don't truly understand it.
551 views

### How to reduce the number of (overlapping) constraints in a linear program?

I am trying to solve a linear program with more than 7 million constraints which could not be solved on my computer (In total around 5000 variables). In the constraints there is a overlap between them....
400 views

61 views

### What's the difference between GLPP and LPP

$a)$ Express the following optimization problem as a linear programming problem(LPP): $$\text{maximize }3x+3y-30$$$$\text{subject to }|x-2|+|y|\le5$$ Hint: you will need to express the ...
55 views

### Linear Program such that Simplex (w/ any pivot rule) takes exponential time?

I had this exam question last semester, and it's still bothering me: For every natural number $n$, you want an LP (not necessarily with $n$ inequalities) such that simplex cannot solve it in ...
26 views

66 views

### Can strong duality for linear programming be viewed intuitively?

Is there a somewhat intuitive way of understanding strong duality in linear programming? I do understand weak duality quite well since it pretty much follows from how the dual problem is defined but I ...
27 views

### simplex algorithm help for continuing in case of $\lambda \equiv 0$

Is it possible that while the simplex algorithm is working, we get a lambda $$(Ax < b, \max c^T x )$$ $$\lambda_B = c^T A^{-1}_B$$ with only zeros in it ? if so what does it would represent/ ...
40 views

### Warm start a simplex algorithm using a feasible solution

I've been searching a lot for relevant answers to my question. However, I was unable to find a problem formulation with satisfactory answers that would help for my problem. In a nutshell, I would ...
53 views

### how do we know from a degenerate simplex tableau of an LP problem if the current basic feasible solution is optimal?

(simplex method) In degenerate cases, the current basic feasible solution with positive reduced cost coefficient can also be an optimal solution (in non-degenerate cases, the optimal solution is ...