# Questions tagged [linear-programming]

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

4,075 questions
Filter by
Sorted by
Tagged with
9 views

### How to derive the dual for LP like this?

I know how to derive dual for normal LPs, but what if we are unlikely to have something like this: maximize z s.t. z < 3y-2 1 < y < 2 , where ...
14 views

### Filling a piecewise continuous linear shape with a constant volume of liquid

We have a piecewise continuous linear function (representing topography). The shape is to be filled with a constant volume of liquid (representing an ocean). How can we find the 'sea level', and where ...
13 views

25 views

### converting con-convex region to convex [closed]

I'm trying to model a problem using Linear Programming theory, though the feasible region of the problem is non-convex. Yet, I think using Big-M and some binary variables this region can be converted ...
21 views

### Can we solve bimatrix game using linear programming like zero-sum games?

Why can we not use linear programs to solve bi-matrix games like the prisoner's dilemma or the peace-war game? Can you provide a counter example?
46 views

### Doubts in a textbook lemma

There is a lemma in the book saying: "If the primal basic solution is an optimal solution of a linear program (P), B is not necessarily an optimal basis." I don't understand because, by ...
14 views

### Construct satisfiable solution to a bunch of constraints

I have to determine a problem is feasible or not, but I am not sure how to categorize my problem. It's not LP, or other standard forms of feasibility problems I've encountered. The specific problem is ...
30 views

### When are Chebyshev centroids and “analytic” centroids equivalent?

Let $A\in \mathbb{R}^{m \times n}$ and $x,b \in \mathbb{R}^n$. The intersection of a finite number of halfplanes in $n$ dimensions can be expressed as the solution set to a system of linear ...
15 views

### Terminology for Linear Programs without Objective Functions

I have a linear program without an objective function. That is, I am looking for a feasible solution to a given set of linear constraints. Is there a specific term for such problems? Likewise, for ...
38 views

22 views

27 views

32 views

### Different linear programming versions of optimal transport

What is the difference between these two different versions of the linear programming optimization set-up for optimal transport (OT)? how to reconcile them mathematically to show that they are ...
19 views

### Linearization of a Max-Max Function

I need help in the linearization of this maxmax function: max max {2x1+3x2, x1+4x2, 5x1+8x2} subject to: x ϵ X. I already started it by: α = max {2x1+3x2, x1+4x2, 5x1+8x2} max α α ≥2x1+3x2 α ≥x1+...
33 views

### Prove : The variable that becomes non-basic in one iteration of the simplex cannot become basic in the next iteration.

I am aksed for giving short proof for this statement. I know the working of Simplex and also that this statement is correct. Once any basic variable becomes non-basic, it has a negative coefficient ...
36 views

### Optimization question on a function $𝑢(𝑥, 𝑦, 𝑧, 𝑤) = \min\{𝑥, 2𝑦\} + \max \{3𝑧, 4𝑤\}$

I have the following utility function $$𝑢(𝑥, 𝑦, 𝑧, 𝑤) = \min\{𝑥, 2𝑦\} + \max \{3𝑧, 4𝑤\}$$ I want to find its demand function. For that \operatorname{Max}𝑢(𝑥, 𝑦, 𝑧, 𝑤) = \min\{𝑥, 2𝑦\} ...
33 views

### Linear programming - Objective function is a multiple of one of the constraints

I wondered if someone could explain to me the intuition of what it would mean if the objective function in a Linear Programme is a multiple of one of the constraints? I am thinking it means that the ...
21 views

### Is this equivalent to the matroid exchange axiom for closure operators?

Given any set $X$ and some closure operator $\text{cl}:2^X\to 2^X$ on $X$, suppose we define $\psi:2^X\to 2^X$ so that $\psi(Q)=\{q\in Q:q\in\text{cl}(Q\setminus\{q\})\}$ for all $Q\subseteq X$, now ...
15 views

### How to find an intial basic solution (partial tree) for the simplex method of a graph if you know the maximum flow?

Let's say I have a graph and I know that the maximum flow that can be pushed into this graph. What are the main guidelines of making a partial tree out of this graph that will be a feasible initial ...
15 views

### Minimal cost flow problem - How to balance supply and demand by adding a node and edges? [closed]

I have the following graph for a minimal cost flow problem. Usually in this type of problem the demand = supply. However here we have 30 of supply and only 16 of demand. I'm tasked with adding a node ...
25 views

### infeasibility of primal LP problem

Let's say we have an LP problem \begin{align*} \text{minimize} \quad &c^Tx\\ \text{subject to} \quad & Ax \preceq b \end{align*} If this problem is infeasible, then $p^* = \infty$. In ...
25 views

### How to find the other x,y points of one segment AC knowing the angle and the base

How to find the other x,y points of one segment AC knowing the angle and the base length (can be any angle in the example). Having the base segment line, in this case, is the red line knowing the A(x, ...
"Consider the polytope in $\mathbb{R}^4$ generated by taking the convex hull of the points $(\pm 1,0,0,0),(0,\pm 1,0,0),(0,0,\pm 1,0),$ and $(0,0,0,\pm 1)$. Describe all of its faces. How many ...