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
Is it possible to strictly separate two disjoint non empty convex sets , one of which is compact and other one closed? [on hold]
Is the strict separation possible in the given case ? I cannot find a proof .
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 ...
