Transform the following linear program into an equivalent standard form:

$max{\textstyle \phantom{\rule{1em}{0ex}}}{x}_{2}-{x}_{1}$ $\text{subject to:}{\textstyle \phantom{\rule{1em}{0ex}}}2{x}_{1}+{x}_{2}\ge 3,{\textstyle \phantom{\rule{1em}{0ex}}}3{x}_{1}-{x}_{2}\le 7,{\textstyle \phantom{\rule{1em}{0ex}}}{x}_{1}\ge 0.$ Consider the following optimization problem:

$min{\textstyle \phantom{\rule{1em}{0ex}}}\sum _{i}{c}_{i}|{x}_{i}-{d}_{i}|$ ,$\text{subject to:}{\textstyle \phantom{\rule{1em}{0ex}}}Ax=b,{\textstyle \phantom{\rule{1em}{0ex}}}x\ge \mathbf{0}$ where

,$A$ ,$b$ and$c$ are given. Assume that$d$ for all${c}_{i}\ge 0$ .$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?

Solve the following linear program by simplex method (note that

is feasible):$({x}_{1},{x}_{2},{x}_{3})=(0,0,0)$ $max{\textstyle \phantom{\rule{1em}{0ex}}}{x}_{1}+4{x}_{2}+5{x}_{3}$ .$\text{subject to:}{\textstyle \phantom{\rule{1em}{0ex}}}{x}_{1}+2{x}_{2}+3{x}_{3}\le 2,{\textstyle \phantom{\rule{1em}{0ex}}}3{x}_{1}+{x}_{2}+2{x}_{3}\le 2,{\textstyle \phantom{\rule{1em}{0ex}}}2{x}_{1}+3{x}_{2}+{x}_{3}\le 4,{\textstyle \phantom{\rule{1em}{0ex}}}{x}_{1},{x}_{2},{x}_{3}\ge 0$ Write all intermediate forms.

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

$max{\textstyle \phantom{\rule{1em}{0ex}}}3{x}_{1}+{x}_{2}$ .$\text{subject to:}{\textstyle \phantom{\rule{1em}{0ex}}}{x}_{1}-{x}_{2}\le -1,{\textstyle \phantom{\rule{1em}{0ex}}}-{x}_{1}-{x}_{2}\le -3,{\textstyle \phantom{\rule{1em}{0ex}}}2{x}_{1}+{x}_{2}\le 4,{\textstyle \phantom{\rule{1em}{0ex}}}{x}_{1},{x}_{2}\ge 0$ The first step should be to find a feasible solution by simplex method, since

is not feasible. What linear program should we solve at the first step (in order to find a feasible solution)?$({x}_{1},{x}_{2})=(0,0)$ (You only need to write the linear program. No need to solve it.)

Consider the dual of linear programs in standard form.

Write the dual to

$min{\textstyle \phantom{\rule{1em}{0ex}}}5{x}_{1}+7{x}_{2}+9{x}_{3}+11{x}_{4}+13{x}_{5}$ ,$\text{subject to:}{\textstyle \phantom{\rule{1em}{0ex}}}15{x}_{1}+14{x}_{2}+45{x}_{3}+44{x}_{4}+13{x}_{5}=2021,{\textstyle \phantom{\rule{1em}{0ex}}}{x}_{i}\ge 0$ and solve it by solving its dual.

What is the dual to the general standard linear program?

$min{\textstyle \phantom{\rule{1em}{0ex}}}{c}^{T}x$ .$\text{subject to:}{\textstyle \phantom{\rule{1em}{0ex}}}Ax=b,{\textstyle \phantom{\rule{1em}{0ex}}}x\ge 0$

Consider the linear program

$max{\textstyle \phantom{\rule{1em}{0ex}}}{c}^{T}x$ .Assume that this linear program is unbounded. Prove that, if we replace

by any vector$b$ , the resulting linear program is either infeasible or unbounded.${b}^{\prime}$

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