# Tag Info

## Hot answers tagged two-phase-simplex

4

Here's the bad news: you can't do this with a straight-up linear program. Here's the good news: you can do this with an integer linear program. Introduce an additional binary decision variable $z$. Let $z=0$ whenever $x=0$ and $z=1$ whenever $x\ge 4$. Furthermore, pick an arbitrarily large number, call it $M$, such that $M$ can not bound your $x$ variable ...

3

I believe that what you're looking for is simply this: $$\sum_{i:~x_i\geq C} (x_i - C) \leq L \quad\Longleftrightarrow\quad \sum_i \max\{ x_i - C, 0 \} \leq L$$ It is not difficult to express this in a linear program. Let $y\in\mathbb{R}^n$ be a new variable of the same size as $x$. Then this system of inequalities will give you what you want: \sum_i y_i \... 3 It isn't. The objective of the new problem is constructed so that 1) Any feasible solution of the new problem has objective value \ge 0. 2) Feasible solutions of the new problem where the objective value is 0 have all artificial variables 0 and correspond to feasible solutions of the original problem. When you solve the new problem, it may be that ... 3 If you want a given vector v \in {\mathbb R}^n as a solution: take a random m \times n matrix A choose a vector b \in{\mathbb R}^m such that b \ge A v. You can generate b by taking b=Av+\delta, \delta_i\ge0 Then the constraints can be A x \le b. Generically, if m \ge n and b - Av has at least n zero entries, v will be a basic ... 2 That is right. M is the quantity you want to maximize subject to the four constraints above it. 2 Based on Thomas Ferguson's Linear Programming: A Concise Introduction, I would solve it like this: First, construct the simplex tableau. \begin{align*} \begin{array}{c | rrr | r} & x_1 & x_2 & x_3\\ \hline y_1 & -1 & -1 & -1 & -2\\ y_2 & 2 & -1 & 1 & 1\\ \hline & -2 & 6 & 0 & 0 \end{array} \end{... 2 You are right, that does not make any sense. Another error in this example is that they claim that \lambda=[-5/3; -2/3] found at the start of the third iteration is optimal, but it clearly is not since strong duality does not hold: c^Tx = -4\cdot 11/3 - 2\cdot 4/3 = -52/3, while b^T\lambda = 5\cdot -5/3 + 8\cdot -2/3 = -41/3. They report the correct ... 2 First you should define the variables A=Amount of Hamper A B=Amount of Hamper B C=Amount of Hamper C Constraint for the weight of nuts (kg): 6A+4B+8c\leq 10,000 If you produces 1000 Hamper C, then you need 6000 kg of nuts. Constraint for the packs of smoked salmon: 3A +2B\leq 4,000 Constraint for the bottles of wine: 2A+3C\leq 2,000 ... 2 There is no closed form solution for an LP or MIP. For LPs we can say a few things about how the optimal solution may change when we start to perturb c (search for reduced cost and more generally: sensitivity analysis). The simplex method is very good in finding optimal solutions to related problems. After changing some coefficients, it can often find the ... 2 If the current basic solution to your Phase-I problem is optimal and one of the auxiliary (artificial) variables is basic and strictly greater than 0, then this means that your original LP is infeasible. You're done. If the current basic solution to your Phase-I problem is optimal with an objective value of 0 and an artificial variable is basic at zero, ... 1 Let me explain what's happening before getting back to the text. In the standard form, \begin{align} \max z= \quad& -6 x_1 - 3 x_2 \tag{\star}\label{z1} \\ \text{s.t.} \quad& x_1+x_2-z_1 = 1 \tag{1}\label{c1} \\ & 2x_1-x_2-z_2 = 1 \tag{2}\label{c2} \\ & 3x_2+z_3 = 2 \tag{3}\label{c3} \\ & x_1, x_2, z_1, z_2, z_3 \geq 0. \tag{FC}\label{... 1 I figured out my error. I forget to apply one Minimum Ratio Test and should have applied a pivot to x_0 instead of w_2. Since choosing w_2 to leave the basis provides a tighter bound. for x_0 to be \geq 0 x_0 \leq 2 - x_1 \implies x_1 \leq 2 for w_2 to be \geq 0 w_2 \leq 3 - 3x_1 \implies x_1 \leq 1 1 How did s_2 suddenly become negative? What did I do wrong? You've chosen the wrong entering variable. This give rise to an unfeasible solution. To set up the initial tableau, multiply the second equation of the system \left\{ \begin{array}{c} x - s_1 + a_1=1\\ -2x +y - s_2=0, \end{array} \right. $$by -1, so that the coefficient of the current ... 1 The salient point is that the entries of the RHS have to be non-negative. You calculate the minimum of the fractions. Only the entries in the matrix has to be positive. The short notation is \min\bigg\{\frac{b_i}{a_{ij^*}}|a_{ij^*}>0\bigg\}  where b_{i}\geq 0 In your case \min\bigg\{\frac{b_2}{a_{22^*}}\bigg\}= \min\bigg\{\frac{0}{1}\bigg\}= 0 \... 1 Yes, you can. That's precisely the statement of the Strong Duality Theorem, which asserts the existence of \mathbf{y}_{*} provided that of \mathbf{x}_{*} (and vice versa) the zero duality gap \mathbf{y}_{*}^{T}\mathbf{b} - \mathbf{c}^{T}\mathbf{x}_{*} is zero provided the existence of \mathbf{x}_{*} or \mathbf{y}_{*} Both the primal and the ... 1 It might be wrong but I think we cannot minimize \,x_1+3x_2-x_3\, ----------- Let \,x_1=0,\ x_2\geq1,\ x_3=4x_2, \ then we have$$2x_1+x_2+3x_3=13x_2>3-x_1+x_2=x_2\geq1-x_1-5x_2+x_3=-x_2<4x_1=0,\ \ x_2>0,\ \ x_3=4x_2>0$$Now all inequalities hold, so we can make \,x_2\,be infinitely large, and that will make$$\,x_1+...

1

One way would be, for a start at (5,0), to set up a new variable $x_1'$ and put the original $x_1$ equal to $5+x_1'$ in the objective and constraints. Then the usual simplex, starting at $(0,0)$ in the $x_1',x_2$ variables, would in effect be starting at $(5,0)$ in the $x_1,x_2$ variables.

1

To get the matrix back in canonical form, you simply need to make sure that any basic variable has a 0 coefficient in the objective function row. So looking at the matrix $$\begin{bmatrix} 1&0&-1&-1&0&2 \\ 0&0&-4&-4&1&10 \\ 0&1&3&1&0&4 \\ -2&-1&2&0&0&0 \\ \end{bmatrix}$$ You ...

1

You have to use artificial variables ($a_i$), because of the equality signs. $\begin{array}{|c|c|c|c|c|c|} \hline x_1 &x_2&x_3&a_1&a_2&RHS \\ \hline 0&3&-1&0&0&-8 \\ \hline 1&1&\color{red}{ \boxed{ 1}} &1&0&10 \\ \hline 2&3&1&0&1&15 \\ \hline \end{array}$ \color{red}{ \boxed{ ... 1 \begin{align*} x_1 + x_2 + x_3 + x_4 & =40\\ 2x_1 + x_2− x_3 − x_5 & =10\\ −x_2 + x_3− x_6 & =10 \end{align*} Solve all three equations forx_4$,$x_5$, and$x_6$after setting$x_1 = x_2 = x_3 = 0. Now, \begin{align*} x_4 & = 40\\ -x_5 & = 10\\ -x_6 & = 10. \end{align*} So we need only two artificial variables for the negative ... 1 I can almost get the same result as on your slides but\bar{c}'=[5,82/7,0,0,0]$, perhaps there is a small typo in the slide? The basic idea is to use the formula for the reduced cost: $$\bar c_j = c_j -\bf{c_B}B^{-1}A_j$$ where$\bar{c}_j$means the reduced cost (not vector!) and$c_j$denotes the terms in the minimization like$$\bf{c}'\bf{x}=c_1x_1+... 1 In the first phase of the simplex method it is convenient to choose the objective function$z=y_1 + \cdots + y_n$where the$y_i$variables are the auxiliary variables and$z$is the objective value of the current tableau(not every textbook writes the$z\$ out explicitly). Recall that the auxiliary are introduced to make a starting basis obvious: simply take ...

Only top voted, non community-wiki answers of a minimum length are eligible