# Questions tagged [linear-programming]

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

5,063 questions
Filter by
Sorted by
Tagged with
29 views

### Why it is not possible for both primal and dual LP to be unbounded?

I already read this post and its answers and I am still not satisfied. I want to know how to use weak duality to explain why it is not possible for both primal and dual LP to be unbounded. Here is one ...
• 399
56 views

### Help with reformulating linear programming with rounding numbers

I have the following problem, abstracting away a few details from a real-world application, that I want to solve with linear programming (or any other mathematical optimization with constraints, ...
• 157
42 views

### Given these constraints is class scheduling forecasting impossible? [closed]

We are trying to model/simulate and optimize class scheduling for a trade school. I am hoping for some direction to solve the puzzle described below. Context We have, say, 1000 active apprentices at ...
• 1
84 views

### Linear Programming: Minimize deviation and evenly maximize decisive variable [closed]

I came across linear programming while trying to find a solution to a problem. I didn't use LP before so pardon if it is naive question. I hope this forum can help. There are n tasks (x1, x2 .., xn) ...
60 views

• 19.9k
1 vote
48 views

### Application of Farkas Lemma

Let $A \in \mathbb R^{m \times n }, b \in \mathbb R^m$ and $0 \neq c \in \mathbb R^m$. Prove: Either the system $Ax = c$ or the system $A^T y = 0, c^T y = 1$ has a solution. Looks a bit like Farkas ...
• 689
71 views

### How to find expression for the reduced cost?

I'd like to know how to obtain an expression for the reduced cost for each of my primal variables, after having formed the dual problem. I have the following dual problem, where the dual variables are ...
58 views

### Reduction from a Chebyshev\minimax approximation to linear programming to find solution vector

For this question $i\in\{1,2,\dots k\}$ Given samples $$x_{i}\in\mathbb{R}^{8},y_{i}\in\mathbb{R}$$ Assume a linear model such that $y_{i}=a^{T}x_{i}-b+\varepsilon_{i}$ where $\varepsilon_i$ is ...
1 vote
32 views

• 579
25 views

### Why are shadow prices the optimal solution of the dual

Consider an LP $\max_x c^t x$ s.t. $Ax \leq b, x\geq 0$. Let the dual problem be $\min_v b^t v$ s.t. $A^\top v \geq c,v\geq 0$. It is stated in standard text book that the shadow prices of constraints ...
• 1,279
100 views

### Linear program with unknown coefficients in objective function

I was given the following linear program \begin{align} \alpha x_1 + \beta x_2 &\rightarrow \max \\ -3x_2 &\le -9 \\ -x_1-2x_2 &\le -12 \\ -x_1-x_2 &\le -8 \end{align} where $\alpha$...
• 113
21 views

41 views

### How to formulate this transportation problem?

I have been trying to formulate this as a transportation problem but I can't seem to do so: We have $3$ types of projects and $3$ types of evaluators. We need to evaluate $61,40$ and $21$ projects of ...
55 views

### How can linear programming condition check if variable is a multiple of number?

Let's say we have linear programming problem with x1 and x2 variables. Maximize x1 + x2 where (for example) 0.3x1 + 0.7x2 <= 2 0.2x1 + 0.3x2 <= 3 How can be added one more condition, so linear ...
26 views

### Finding possible values of entries of a simplex tabeau

While solving a standard form problem, we arrive at the following tableau, with $x_3, x_4, and x_5$ being the basic variables: The entries α, β, γ, δ, η are unknown parameters. We have to determine ...
• 497
85 views

### How to linearize a max function in a constraint? [closed]

I have linear program that has constraint as follows: $\max(x,y) \geq 0$ where $x$ and $y$ are variables. How to linearize this inequality? How to write this constraints in google or tools?
13 views

### Obtaining tight edges from a graph to find an MST

As far as I understand, to obtain an optimal solution of the Dual of the MST, meaning: \begin{align} ~\max &~ z (|V|-1) + \sum_{S \subseteq V : |S| \neq \emptyset} (|S|-1) y_{s} \\ \label{DMST2} ...
• 308
26 views

### How to identify a CPF solution in an LP model?

"For any linear programming problem with n decision variables, each CPF solution lies at the intersection of n constraint boundaries; i.e., it is the simultaneous solution of a system of n ...
• 25
56 views

### Reference Request: LP representation of problems

I am preparing for an exam on Linear optimisation and came across different problems where some apparently non linear problems can be modelled as LP (For example here, here and here). I was wandering ...
• 497
78 views

### Complexity of solving systems of linear inequalities with two variables per inequality with additional constraints

Consider a system $X$ of linear inequalities containing at most two variables. In the general case, finding a solution over $\mathbb{R}\cap[0,1]$ can be done deterministically in polynomial time due ...
When designing LPs for exams I often run across problems where I would like to input an "if-statement". For example: $5\leq x_b$ if $p_a\geq 10$ I've tried dividing by itself and using floor ...