Problem 1

Write the dual problems for the following linear programming probloms.

1.

minimize z=2x1+2x2+4x3\text{minimize~}z=2x_{1}+2x_{2}+4x_{3}

subject to

{x1+3x2+4x3≥2x1+x2+3x3≤3x1+4x2+3x3=5x1,x2≥0,x3 unrestricted\begin{cases} x_{1}+3x_{2}+4x_{3}\geq2\\ x_{1}+x_{2}+3x_{3}\leq3\\ x_{1}+4x_{2}+3x_{3}=5\\ x_{1},x_{2}\geq0,x_{3} \text{ unrestricted} \end{cases}
  • The dual of this problem is
max⁡2y1+3y2+5y3\max 2y_1+3y_2+5y_3

subject to

{y1+y2+y3≤23y1+y2+4y3≤24y1+3y2+3y3=4y1≥0,y2≤0,y3 unrestricted\begin{cases} y_{1}+y_{2}+y_{3}\leq2\\ 3y_{1}+y_{2}+4y_{3}\leq 2\\ 4y_{1}+3y_{2}+3y_{3}=4\\ y_{1}\geq0,y_2\leq 0, y_{3} \text{ unrestricted} \end{cases}

2.

maximize z=5x1+6x2+3x3\text{maximize~}z=5x_{1}+6x_{2}+3x_{3}

subject to

{x1+2x2+2x3=5−x1+5x2−x3≥34x1+7x2+3x3≤8x1 is unrestricted, x2≥0,x3≤0\begin{cases} x_{1}+2x_2+2x_{3}=5\\ -x_{1}+5x_{2}-x_{3}\ge 3\\ 4x_1+7x_2+3x_3\leq 8\\ x_{1}\text{ is unrestricted, }x_{2}\geq0,x_{3}\leq0 \end{cases}
  • The dual of this problem is
min⁡z=5y1+3y2+8y3\min z=5y_{1}+3y_{2}+8y_{3}

subject to

{y1−y2+4y3=52y1+5y2+7y3≥62y1−y2+3y3≤3y1 is unrestricted, y2≤0,y3≥0\begin{cases} y_{1}-y_2+4y_{3}=5\\ 2y_{1}+5y_{2}+7y_{3}\ge 6\\ 2y_1-y_2+3y_3\leq 3\\ y_{1}\text{ is unrestricted, }y_{2}\leq0,y_{3}\geq0 \end{cases}

3. General Form (for referencece)

maximize z=∑j=1ncjxj\text{maximize }z=\sum_{j=1}^{n}c_{j}x_{j}

subject to

{∑j=1naijxj≤bi(i=1,…,m1<m)∑j=1naijxj=bi(i=m1+1,m1+2,…,m)xj≥0(j=1,…,n1<n)xj is unrestricted(j=n1+1,…,n)\begin{cases} \sum_{j=1}^{n}a_{ij}x_{j}\leq b_{i} & (i=1,\ldots,m_{1}<m)\\ \sum_{j=1}^{n}a_{ij}x_{j}= b_{i} & (i=m_1+1,m_1+2,\dots,m)\\ x_j\ge 0 & (j=1,\dots,n_1<n)\\ x_j \text{ is unrestricted} & (j=n_1+1,\dots,n) \end{cases}
  • The dual of this problem is
min⁡∑i=1mbiyi\min \sum_{i=1}^{m}b_{i}y_{i}

subject to

{∑i=1maijyi≥cj(j=1,…,n1<n)∑i=1maijyi=cj(j=n1+1,…,n)yi≥0(i=1,…,m1<m)yi is unrestricted(i=m1+1,…,m)\begin{cases} \sum_{i=1}^{m}a_{ij}y_{i}\geq c_{j} & (j=1,\ldots,n_{1}<n)\\ \sum_{i=1}^{m}a_{ij}y_{i}= c_{j} & (j=n_1+1,\dots,n)\\ y_i\geq 0 & (i=1,\dots,m_1<m)\\ y_i \text{ is unrestricted} & (i=m_1+1,\dots,m) \end{cases}

Problem 2

Prove that the dual of the dual problem of a linear programming problem is the original problem.

  • Consider the original problem as:
max⁡cTxAx≤bx≥0\max c^Tx\\ Ax\leq b\\ x\geq0

And it's dual problem can be written as:

min⁡bTyATy≥cy≥0\min b^Ty\\ A^Ty\geq c\\ y\geq0

And the dual of the dual problem is:

max⁡cTz(AT)Tz=Az≤bz≥0\max c^Tz\\ (A^T)^Tz=Az\leq b\\ z\geq0

So the dual of the dual problem is the original problem.

Problem 3

Given the linear programming problem:

maximize z=x1+x2\text{maximize~}z=x_1+x_2

subject to:

{−x1+x2+x3≤2−2x1+x2−x3≤1x1,x2,x3≥0\begin{cases} -x_1+x_2+x_3\leq2\\ -2x_1+x_2-x_3\leq1\\ x_1,x_2,x_3\geq0 \end{cases}

Prove, using the properties of duality, that the objective function of the above linear programming problem is unbounded.

  • Conisder it's fual problem:
min⁡2y1+y2s.t.{−y1−2y2≥1y1+y2≥1y1−y2≥0y1,y2≥0\min 2y_1+y_2\\ \mathrm{s.t.} \begin{cases} -y_1-2y_2\geq1\\ y_1+y_2\geq1\\ y_1-y_2\geq0\\ y_1,y_2\geq0 \end{cases}

Notice that, −y1−2y2≥1,y1,y2≥0-y_1-2y_2\ge1,y_1,y_2\ge0, which is a contradiction. So, the fesible region is empty. And as the feasible region of the original problem is not empty, the original problem must be unbounded.

Problem 4

Given the original problem and dual problem:
Original Problem:

max⁡f(X)=CX\max f(X)=CX

subject to

AX≤BX≥0AX\leq B\\ X\ge0

Dual Problem:

min⁡g(Y)=YB\min g(Y)=YB

subject to

YA≥CY≥0YA\ge C\\ Y\ge 0

Given the original problem and its dual problem as above, let X0X^0 and Y0Y^0 be feasible solutions to the original problem and dual problem, respectively. Let U0U^0 be the slack variable of the original problem constraints, and V0V^0 be the slack variable of the dual problem constraints.
When V0X0+Y0U0=0V^0X^0+Y^0U^0 =0, prove that X0X^0 and Y0Y^0 are optimal solutions to the original problem and dual problem, respectively.

  • According to the slack variable, we can get U0=B−AX0,V0=Y0A−CU^0=B-AX^0,V^0=Y^0A-C. As X0,Y0X^0,Y^0 is feasible solutions, by the V0X0+Y0U0=0V^0X^0+Y^0U^0=0, we have (Y0A−C)X0+Y0(B−AX0)=−CX0+Y0B=0(Y^0A-C)X^0+Y^0(B-AX^0)=-CX^0+Y^0B=0, which means CX0=Y0BCX^0=Y^0B. By the weak duality lemma, CX0≤Y0BCX^0\leq Y^0B, now we have CX0=Y0BCX^0=Y^0B, which means X0X^0 and Y0Y^0 are optimal solutions.

Problem 5

max⁡z=6x1+10x2+9x3+20x4\max z= 6x_1+10x_2+9x_3+20x_4

subject to

{4x1+9x2+7x3+10x4≤600x1+x2+3x3+40x4≤4003x1+4x2+2x3+x4≤500xj≥0(j=1,2,3,4)\begin{cases} 4x_1+9x_2+7x_3+10x_4\leq600\\ x_1+x_2+3x_3+40x_4\leq400\\ 3x_1+4x_2+2x_3+x_4\leq500\\ x_j\geq0\quad(j=1,2,3,4) \end{cases}

The optimal solution of this problem is:

x=(4003,0,0,203),z∗=28003x=\left(\frac{400}{3},0,0,\frac{20}{3}\right),\quad z^*=\frac{2800}{3}

Find the optimal solution of the dual problem using the complementary slackness conditions.

  • The dual problem is:
min⁡600y1+400y2+500y3s.t.{4y1+y2+3y3≥69y1+y2+4y3≥107y1+3y2+2y3≥910y1+40y2+y3≥20yi≥0(i=1,2,3)\min 600y_1+400y_2+500y_3\\ \text{s.t.} \begin{cases} 4y_1+y_2+3y_3\geq6\\ 9y_1+y_2+4y_3\geq10\\ 7y_1+3y_2+2y_3\geq9\\ 10y_1+40y_2+y_3\geq20\\ y_i\geq0\quad(i=1,2,3) \end{cases}

Since the optimal solution is x=(4003,0,0,203)x=\left(\frac{400}{3},0,0,\frac{20}{3}\right), we have:

{4y1+y2+3y3=610y1+40y2+y3=20\begin{cases} 4y_1+y_2+3y_3=6\\ 10y_1+40y_2+y_3=20 \end{cases}

Solving this linear equations gives y1=2215−119150y3,y2=215+1375y3y_1=\frac{22}{15}-\frac{119}{150}y_3,y_2=\frac{2}{15}+\frac{13}{75}y_3.
So, the objective function can be written as min⁡28003+2803y3\min \frac{2800}{3}+\frac{280}{3}y_3, which means y3y_3 should be 00.
Therefore, the optimal solution is (2215,215,0)(\frac{22}{15},\frac{2}{15},0).