Problem 1

Determine whether the following statements are true or false. If true, provide a proof; if false, give a counterexample.

(a) If the primal linear programming problem has a feasible solution, then its dual problem must also have a feasible solution.

  • False. Consider:
max⁡xs.t.{−x≤−1x≥0\max x\\ \text{s.t.} \begin{cases} -x\leq-1\\ x\ge0 \end{cases}

, which has a feasible solution x=1x=1, its dual problem:

min⁡−ys.t.{−y≥1y≥0\min -y\\ \text{s.t.} \begin{cases} -y\ge1\\ y\ge0 \end{cases}

, has no feasible solution.

(b) If the dual linear programming problem has no feasible solution, then the primal problem must also have no feasible solution.

  • False. The counterexample is the same with (a).

(c) In a primal-dual pair of linear programming problems, regardless of whether the primal is a maximization or minimization problem, the objective function value of any feasible primal solution does not exceed that of any feasible dual solution.

  • False. Consider:
min⁡xs.t.{x=1x≥0\min x\\ \text{s.t.} \begin{cases} x=1\\ x\ge0 \end{cases}

, which the objective function can be x0=1x_0=1, and its dual problem:

max⁡ys.t. y≤1\max y\\ \text{s.t. }y\leq1

, which the objective function can be y0=0y_0=0. So, x0>y0x_0> y_0.

Problem 2

Introduce 0-1 variables to express the following constraints as general linear constraints.

(a) At least one of the following three constraints must hold:

3x1−2x2≥4 or x1+5x2≤12 or 4x1−x2≤83x_1-2x_2\ge 4\text{ or }x_1+5x_2\leq 12\text{ or }4x_1-x_2\leq8
{3x1−2x2≥4−(1−y1)Mx1+5x2≤12+(1−y2)M4x1−x2≤8+(1−y3)My1+y2+y3≥1yi=0 or 1, i=1,2,3\begin{cases} 3x_1-2x_2\ge 4-(1-y_1)M\\ x_1+5x_2\leq 12+(1-y_2)M\\ 4x_1-x_2\leq 8+(1-y_3)M\\ y_1+y_2+y_3\geq1\\ y_i=0\text{ or }1,~ i=1,2,3 \end{cases}

(b) If x1≥3x_1\ge3, then x2≤6x_2\leq6; otherwise x2≥4x_2 \ge 4.

{x1≥3−(1−y)Mx1<3+yMx2≤6+(1−y)Mx2≥4−yMy=0 or 1\begin{cases} x_1\ge3-(1-y)M\\ x_1<3+yM\\ x_2\leq 6+(1-y)M\\ x_2\ge 4-yM\\ y=0\text{ or }1 \end{cases}

(c) The variable x1x_1 can only take one of the following discrete values:

x1∈{2,4,6,8}x_1\in\{2,4,6,8\}
{x1=2y1+4y2+6y3+8y4y1+y2+y3+y4=1yi=0 or 1, i=1,2,3,4\begin{cases} x_1=2y_1+4y_2+6y_3+8y_4\\ y_1+y_2+y_3+y_4=1\\ y_i=0\text{ or }1,~ i=1,2,3,4 \end{cases}

Problem 3

Use the Branch and Bound method to solve the following integer linear programming problem:

{max⁡z=2x1+x2s.t.x1+x2≤5−x1+x2≤06x1+2x2≤21x1,x2≥0, and integers.\begin{cases} \max&z=2x_1+x_2\\ \text{s.t.}&x_1+x_2\leq5\\ &-x_1+x_2\leq0\\ &6x_1+2x_2\leq21\\ &x_{1},x_{2}\geq0,\text{ and integers.} \end{cases}
  • The optimal solution for the relaxation problem is x=(11/4,9/4)x=(11/4,9/4). Since 2≤x1≤32\leq x_1\leq3, we can add two more constraints x1≤2 and x1≥3x_1\leq 2\text{ and }x_1\ge 3 to form two sub-linear programming problem.
    (LP1):
{max⁡z=2x1+x2s.t.x1+x2≤5−x1+x2≤06x1+2x2≤21x1≤2x1,x2≥0\begin{cases} \max&z=2x_1+x_2\\ \text{s.t.}&x_1+x_2\leq5\\ &-x_1+x_2\leq0\\ &6x_1+2x_2\leq21\\ &x_1\leq 2\\ &x_{1},x_{2}\geq0 \end{cases}

, which x∗=(2,2)x^*=(2,2), optimum 66.
(LP2):

{max⁡z=2x1+x2s.t.x1+x2≤5−x1+x2≤06x1+2x2≤21x1≥3x1,x2≥0\begin{cases} \max&z=2x_1+x_2\\ \text{s.t.}&x_1+x_2\leq5\\ &-x_1+x_2\leq0\\ &6x_1+2x_2\leq21\\ &x_1\ge 3\\ &x_{1},x_{2}\geq0 \end{cases}

, which x∗=(3,1.5)x^*=(3,1.5), optimum 7.57.5.
Since (LP2) has an larger optimum value, we further partition this branch by adding two more constraints, x2≤1 and x2≥2x_2\leq 1\text{ and }x_2\ge 2. As when x2≥2x_2\ge 2, xx can only be (3,2)(3,2), and 6x1+2x2=22>216x_1+2x_2=22>21, so it's impossible.
Letting x2≤1x_2\leq 1, the interger feasible solutions are (3,0),(3,1)(3,0),(3,1). And x∗=(3,1)x^*=(3,1), optimum 77.
After all, we have (3,1)(3,1) is the optimal solution and zmax⁡=7z_{\max}=7.