Homework 5

Due: Nov. 9, 22:00:00

Linear program and standard form

1. Transform the following linear program into an equivalent standard form:

   $max{x}_2-x_1$$\max \quad x_2-x_1$

   $\text{subject to:}2x_1+x_2\ge 3,3x_1-x_2\le 7,x_1\ge 0.$$\textrm{subject to:} \quad 2x_1 +x_2 \geq 3,\quad 3x_1-x_2 \leq 7,\quad x_1 \geq 0.$

2. Consider the following optimization problem:

   $min\sum _i{c}_i|x_i-d_i|$$\min \quad \sum_i c_i \abs{x_i-d_i}$

   $\text{subject to:}Ax=b,x\ge \mathbf{0}$$\text{subject to:} \quad Ax = b, \quad x\geq \mathbf{0}$,

   where $A$$A$, $b$$b$, $c$$c$ and $d$$d$ are given. Assume that $c_i\ge 0$$c_i \geq 0$ for all $i$$i$.

   As such this is not a linear program since the objective function involves absolute values. Show how this problem can be formulated equivalently as a linear program. Explain why the linear program is equivalent to the original optimization problem.

   Would the transformation work if we were maximizing?

Simplex method

3. Solve the following linear program by simplex method (note that $(x_1,x_2,x_3)=(0,0,0)$$(x_1,x_2,x_3)=(0,0,0)$ is feasible):

   $max{x}_1+4x_2+5x_3$$\max \quad x_1+4x_2+5x_3$

   $\text{subject to:}{x}_1+2x_2+3x_3\le 2,3x_1+x_2+2x_3\le 2,2x_1+3x_2+x_3\le 4,x_1,x_2,x_3\ge 0$$\text{subject to:}\quad x_1+2x_2+3x_3\leq 2, \quad 3x_1+x_2+2x_3\leq 2, \quad 2x_1+3x_2+x_3\leq 4, \quad x_1,x_2,x_3\geq 0$.

   Write all intermediate forms.

4. We would like to use two-phase simplex method to solve the following linear program.

   $max3x_1+x_2$$\max\quad 3x_1+x_2$

   $\text{subject to:}{x}_1-x_2\le -1,-x_1-x_2\le -3,2x_1+x_2\le 4,x_1,x_2\ge 0$$\text{subject to:} \quad x_1-x_2 \leq -1, \quad -x_1-x_2\leq -3, \quad 2x_1+x_2\leq 4, \quad x_1, x_2\geq 0$.

   The first step should be to find a feasible solution by simplex method, since $(x_1,x_2)=(0,0)$$(x_1,x_2)=(0,0)$ is not feasible. What linear program should we solve at the first step (in order to find a feasible solution)?

   (You only need to write the linear program. No need to solve it.)

Duality

5. Consider the dual of linear programs in standard form.

   • Write the dual to

     $min5x_1+7x_2+9x_3+11x_4+13x_5$$\min\quad 5x_1 + 7x_2 + 9x_3 + 11x_4 + 13x_5$

     $\text{subject to:}15x_1+14x_2+45x_3+44x_4+13x_5=2021,x_i\ge 0$$\text{subject to:}\quad 15x_1 + 14x_2 + 45x_3 + 44x_4 + 13x_5 = 2021, \quad x_i \geq 0$,

     and solve it by solving its dual.

   • What is the dual to the general standard linear program?

     $min{c}^{T}x$$\min\quad c^T x$

     $\text{subject to:}Ax=b,x\ge 0$$\text{subject to:} \quad Ax = b, \quad x\geq 0$.

6. Consider the linear program

   $max{c}^{T}x$$\max\quad c^T x$

   $\text{subject to:}Ax=b,x\ge 0$$\text{subject to:} \quad Ax=b, \quad x\geq 0$.

   Assume that this linear program is unbounded. Prove that, if we replace $b$$b$ by any vector $b^{\prime }$$b'$, the resulting linear program is either infeasible or unbounded.

Questionnaire

• How long does it take you to do this homework?
• If $1$$1$ represents "very easy" and $10$$10$ represents "too hard", how difficult do you feel this homework is? (You can give different points for different problems.)