Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [linear-programming]

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

0
votes
1answer
21 views

Stiemke's Theorem

Stiemke's Theorem: Only one of the following statements are true: (a) $Ax\leq 0$ has a solution $x$. (b) $A^Ty=0$, $y>0$ has a solutions $y$. I'm trying to understand this theorem. Look at the ...
0
votes
1answer
19 views

Chebyshev center of a polyhedron: nonnegativity issue

Let us have a polyhedron, defined by the inequalities of the form: $$ \mathcal{P} = \{ x \ | \ a_i^T x \leq b_i, \ i=1,\ldots,m \} $$ Here on page 19, the way to calculate Chebyshev center is given ...
0
votes
1answer
19 views

Terminating condition of Simplex Method - Stronger termination conditon

My textbook states "If there are no negative values in the top row of the Simplex tableau, then we have reached optimality" That seems intuitive enough. However, I am wondering if the following, ...
0
votes
1answer
16 views

First-order necessary condition for a local minimizer

Let C be a convex set in Rn, and let f be a differentiable function on an open set containing C . First-order necessary condition for a local minimizer : If x∗ ∈ C is a local minimizer of f on C, then ...
0
votes
0answers
14 views
0
votes
0answers
11 views

Linear programming/seeing feasibility and unboudedness

Consider the dual linear programming problem and its simplex dually feasible table: $$\begin{array}{|c|c|c|c|c|c|c|c|}\hline -4& 0 & 1&5&16&0&4&0 \\ \hline -12& 0 &...
0
votes
0answers
10 views

Basic feasible solution on convex sets

Let $P = \{x \in R^n | Ax \geq b \}$. Suppose that at a particular basic feasible solution, there are $k$ active constraints with $k>n$. Is it true that there exists exactly $C(k,n)$ bases that ...
0
votes
1answer
29 views

Scheduling Problem

My boss asked me to come up with a presentation that recommends how many hires she would need to support our tests. I have data that shows the number of tests per day. Assuming one worker per test, ...
0
votes
0answers
32 views

Is the following knapsack modelling correct (with additional constraints)

I was wondering whether the following knapsack ILP is modelled correctly. The model is as follows: The knapsack model has a vector $\mathbf{w} = (w_{1}, \cdots, w_{j}, \cdots, w_{n})$, which contain ...
1
vote
1answer
44 views

Find the Dual of a Primal Linear Programming Problem

Consider the problem $$\text{min}_{x\in\mathbb R^n}\lvert Ax-b\rvert,$$ where $A$ is a $m \times n$ matrix and $b\in\mathbb R^m.$ Rewrite the problem into the form$$(P)\qquad \text{Minimize }\lvert z\...
-2
votes
0answers
20 views

Feasible solution which is not basic [on hold]

$\min p= 2x+3y+4z$ s.t: $x+y+z=2$ $x-y+z=0$ $x,y,z\ge0$ here $x=1,y=0,z=1$ and $p=6$ is solution not basic?? Here we added artificial variables A and B
1
vote
1answer
17 views

Is this the most efficient way to rearrange a linear programming objective with an absolute for lpsolve?

If linear programming is to be used to solve an objective function which contains absolutes then the absolute terms have to be rewritten using extra values, for example, the trivial objective "...
0
votes
0answers
21 views

Linear programming problem minimization change problem

minimize $max ${x1,x2} subject to $2x1+5x2<=9$ $x1+3x2<=5$ $x1>=0$, $x2>=0$ show that both are same and give reason minimize t subject to t>=x1 , t>=x2 $2x1+5x2<=9$ $x1+3x2<=5$ ...
1
vote
1answer
25 views

Non degenerate optimal solution in primal <=> non degenerate optimal solution in dual

I was trying to solve this exercise when my primal is $\min c'x$ $s.t: \ Ax=b \ , x \geq 0 $. For the => proof i think i solved it. This helped me a lot. But the reverse, i think is more ...
0
votes
0answers
14 views

Showing Weak Duality

Suppose we have the Linear program max{$c^Tx: Ax \geq b, x \leq 0$}, and thus its corresponding dual is min{$b^Ty: A^Ty \geq c, y \geq0$}. I am trying to prove that weak duality holds and that $b^Ty \...
0
votes
0answers
22 views

Simplex method using two phase

(P) minimize: $z=x_1+x_2$ subject to : $$\begin{aligned} x_1 + 2 x_2 &\geq 4 & &\text{Eq.1} \\ 2x_1 + x_2 &\geq 6 & &\text{Eq.2} \\ -x_1 + x_2 &\leq 1 & &...
0
votes
1answer
77 views

question about linear programming minimization

(P) $\min z=x_1+x_2$ subject to : $ x_1+2x_2 \geq 4$ ( equation 1) $2x_1+x_2\geq6$ (equation 2) $-x_1+x_2\leq1$ (equation 3) $x_1>=0 ,x_2\geq0 $$ $ I'm trying to solve this using two-...
0
votes
1answer
23 views

complex problem turning logical conditions into linear expressions

I'm trying to add a logical condition constraint into a linear expression on puLP in python. I have translated them by myself and coded them, but the solution is infeasible, which should not be the ...
1
vote
1answer
21 views

(Existence part of) Neyman-Pearson via weak-* convergence

I would like a ask whether there is any statistical reference containing the following functional analytic argument for the existence part of Neyman-Pearson: Let $(R, \mathcal{F}, \mu)$ be a measure ...
0
votes
2answers
66 views

IF a == b, then c = 1, else 0. How to turn this to a linear expression? [closed]

I want to turn the following condition into a linear expression: If a == b, then c = 1, else 0. How should I transform this into a linear expression? Thanks!
0
votes
1answer
26 views

Degeneracy Condition

I understood that when plotting the feasible area there had to be an intersection with more than two lines. In the case of: $$\text{Max } z=2x_1+x_2$$ S.T $$ \begin{cases} 4x_1+3x_2\leq 12\\ ...
-1
votes
1answer
22 views

Basic Columns In Simplex

On the following note it says that if a non basic column has no positive coefficient so this is the case of unboundedness. What non basic column refer to?
2
votes
0answers
28 views

Stochastic programming: Is the linear program over the vertices the same as over the simplex?

Suppose we have a random variable $W$ with probability distribution, $\Pr(W = w) = p_w \in [0,1], \quad w \in I = \{1, \ldots n\}$ Consider the maximization problem: $$\max\limits_{w \in I} \...
0
votes
2answers
64 views

How to calculate minimax value with simplex method?

For the LP problems with only inequality constraints, I know how to use simplex method to give an optimal solution. However, when I want to calculate the minimax value, how should I use the simplex ...
0
votes
1answer
29 views

Convexity Proof for $\mathbb R ^n \backslash A$

I need to tell if it is true or false and prove that given $A$ a convex set, $\mathbb R^n$ \ $ A $ is never convex. So far I get that considering $p,q \in \mathbb R^n$ convex, $\lambda p + (1- \...
0
votes
1answer
28 views

Solution of a LP, give the probabilities of a mixed strategy of a zero sum game

Given a zero sum game like this one : \begin{array}{c|rrrr} & A & B \\\hline X & 4 & 3 \\ Y & 2 & 5 \\ \end{array} and the given LP : minimize $ x+y $ s.t. : $x \geq 0, y \...
1
vote
0answers
87 views

Dual of the barrier transformed linear program $\min_{x \in \mathbb{R}^n} \left\{ c^T x - \mu \sum_{j=1}^n \log(x_j) : Ax = b; x \geq 0 \right\}$

Dual of the following linear program \begin{align} \text{minimize}_{x \in \mathbb{R}^n} \quad & c^T x \ -\mu \sum_{j=1}^n \log(x_j) \\ \text{subject to }\quad & Ax = b\\ & x \geq 0 \ , \...
1
vote
2answers
43 views

Linear program geometry

I’ve tried to solve a question in my homework, and I don’t really know what to do. In the problem a polyhedron is given and I need to build the set of constraints that defines this polyhedron. The ...
2
votes
2answers
30 views

Strict inequality logical implication in optimization problems

I have $ x \in \{0,1\}$ and $y \geq 0$ and I want to model that $x=1$ iff $y>0$, is this possible while keeping the constraint linear? Thanks. One part of the implication is easy $ y \leq Mx$. The ...
0
votes
1answer
17 views

Linear programming with what I think has 3 variable. I need to plot a graph of the constraints too. [closed]

I have a question. A refinery gets oil from three wells. Each wells provides oil with a certain amount of lead and iso-octane. The blended product must contain a maximum of 3.5% lead and a minimum of ...
1
vote
2answers
39 views

Corresponding LP problems to zero sum games

Given a zero sum game like this one : \begin{array}{c|rrrr} & A & B \\\hline X & 10 & 3 \\ Y & 5 & 9 \\ \end{array} how do you find an equivalent linear program ? I think ...
0
votes
0answers
26 views

Products of k/l-gons

For $k \geq 3$ let $P_k = conv\{(\cos\frac{2\pi\cdot i}{k}, \sin\frac{2\pi\cdot i}{k})\ |\ 0 \leq k < i\}$ be a regular $k$-gon in $\mathbb{R}^2$. We want to look at product $P_k \times P_l$ in $\...
1
vote
1answer
111 views

Help in understanding proof of lexicographic rule's role in terminating the simplex method

Theorem: The simplex method terminates as long as the leaving variable is selected by the lexicographic rule in each iteration. I am reading through the proof of this theorem and understand all but ...
0
votes
2answers
39 views

confused in linear property?

I have a system $$y(t)=3x(t)+2\cos(\pi t/3)$$ I am confused if this function/system is linear or not? As if only we had $y=3x$, it would be definitely linear but now due to cos term, scenario ...
0
votes
1answer
27 views

Why do we need (or use) identity matrix while proceeding simplex method

I've been studying for operational research recently.I did comprehend how the algorithm works.However I could not figure out why do we need identity matrix and why do we need to create it while ...
1
vote
0answers
22 views

Is this dual linear program correct? If so, how would I interpret its variables/contstraints/optimum?

I'm confronted with the following situation: A company has $5$ employees (conveniently numbered from $1$ to $5$). Each employee is paid at a fixed rate per task completed. The company also has an ...
2
votes
1answer
25 views

Linear programming: redistributing bikes at the end of the day

I'm not sure how I can approach this problem. I need to state the problem before asking my questions. Problem. Suppose a city has many bike stations. You can rent a bike and turn it back at any ...
-1
votes
2answers
58 views

How to write the optimization constraint of the following problem

$A$ is an adjacency matrix and $W$ is the weight matrix. So the problem is to find the maximum matching, such that for those nodes are connected, the weight between them is limited by $d$, which $W_{...
0
votes
1answer
29 views

How to find initial optimal(dual feasible) basis which may not be primal feasible.

I am studying the dual simplex method from Lieberman - 10e. An approach called dual simplex method was described that is "applied" on the "primal table" itself, i.e., We do not convert it into its ...
0
votes
1answer
28 views

Local optima is small than Global optima for min objective

I developed a MIP on LINGO. My objective is minimizing makespan (time). When I run it using the LP solver using a set of data, the objective value is 237. But when I run it using the global solver and ...
0
votes
0answers
22 views

Changing from non linear to linear using Big M

I have a binary variable $v_{ij}$ and integer variable $c_{ijk}$ and the following relationship: $$ c_{ijk} \le M \; v_{ij} $$ $M$ is a very large number Is there a way to change this nonlinear ...
2
votes
1answer
32 views

Dual Simplex Method

Suppose that in a Linear Programming problem in the dual Simplex Method there is a first element (in the first column) negative. If there are in that pivot row some negative numbers we take $\max$ ...
0
votes
1answer
44 views

Linear programming constraints

How do I formulate a linear constraint using LP for the following? $$x_1 + x_2 + \cdots + x_n \geq 5$$ then $z$ takes a value of $1$, where $x_1, x_2, \dots, x_n, z \in \{0,1\}$.
2
votes
1answer
34 views

How to get an equation system from a Simplex table

Let's assume I already have a simplex table (with an optimal solution): $$\left(\begin{array}{ccccc|c} & x_1 & x_2 & S_1 & S_2 & \\ S_1 & 0 & 2 & 0 & 1 & 2 \\ ...
0
votes
0answers
13 views

Show that LPs concerning $P(A,b)$ and $P^{=}(A^{'},b^{'})$ are equivalent

Define $P^{=}(A^{'},b^{'}):=\{x \in \mathbb R^{n}: A^{'}x=b^{'}, x \geq 0\}$ and $P=P^{=}(A,b)=\{x \in \mathbb R^{n}: Ax = b, x \geq 0\}$ Let $A \in \mathbb R^{m\times n}$ and $\operatorname{Rank}A&...
0
votes
1answer
37 views

Strictly positive solution to system of linear equations

I have the following system: \begin{align} \left\{ \begin{array} $21 = 55x_{100} + 54x_{99} + \dots + x_{46} \\ 17 = 50x_{100} + 49x_{99} + \dots + x_{51} \\ 13 = 45x_{100} + 44x_{99} + \dots + x_{56} ...
0
votes
0answers
21 views

Maximal value, linear programming problem

I want to find the maximal $\psi_1$ for the following linear programming problem: \begin{align} \max \frac{2}{3025}(525+121\psi_3 + 1089 \psi_4), \text{ s.t.} \\ \end{align} \begin{array} \text{0} \...
1
vote
2answers
52 views

If then convex condition in mixed integer linear programming with binary variables

I have a convex polynomial $f(x_1,\dots,x_t)$ where $x_1,\dots,x_t\in\mathbb R$ and constant $a$. If condition $$f(x_1,\dots,x_t)\leq a$$ holds I have to make variables $y_1,\dots,y_n\in\mathbb R$ ($...
5
votes
1answer
81 views

How to minimize $\| c \mathbf{x} - \mathbf{y}\|_1$ without using linear programming?

Is there a closed form solution to the minimization problem $$\min_{c \in \mathbb{R}}\left\lVert c \mathbf{x} - \mathbf{y}\right\rVert_1$$ where $\mathbf{x} = \begin{bmatrix}0 & 1 & \dots &...
1
vote
3answers
48 views

Can someone explain this Linear Programming example's explanation?

Can anyone explain part c) to me from this explanation? I don't understand how the author gets: $x=\frac1b$ when $a>b$ and $x=\frac1a$ when $b>a$ Intuitively I don't see how x can be used in ...