跳到主要内容

東京工業大学 情報理工学院 数理・計算科学系 2016年8月実施 午前 問4

标签：

Author​

GPT-5

Description​

Consider the linear programming problem

P:maximize−2x1+5x2−4x3subject to3x1+3x2−5x3≤7,7x1−3x2+7x3≤4,x1,x2,x3≥0.\mathcal P:\quad \begin{array}{ll} \text{maximize} & -2x_1+5x_2-4x_3\\ \text{subject to} & 3x_1+3x_2-5x_3\leq7,\\ &7x_1-3x_2+7x_3\leq4,\\ &x_1,x_2,x_3\geq0. \end{array}

(1) Obtain an optimal solution of P\mathcal P using the simplex method.

(2) Write the dual problem D\mathcal D of P\mathcal P.

(3) Draw the feasible set of D\mathcal D and compute its unique vertex.

题目描述​

考虑线性规划问题

P:最大化−2x1+5x2−4x3满足3x1+3x2−5x3≤7,7x1−3x2+7x3≤4,x1,x2,x3≥0.\mathcal P:\quad \begin{array}{ll} \text{最大化} & -2x_1+5x_2-4x_3\\ \text{满足} & 3x_1+3x_2-5x_3\leq7,\\ &7x_1-3x_2+7x_3\leq4,\\ &x_1,x_2,x_3\geq0. \end{array}
  1. 使用单纯形法求 P\mathcal P 的一个最优解。
  2. 写出 P\mathcal P 的对偶问题 D\mathcal D。
  3. 画出 D\mathcal D 的可行域，并计算其唯一顶点。

考点​

  • 单纯形法：把给定不等式型线性规划化为适合迭代的形式，通过换基求出原问题的最优解。
  • 线性规划对偶：依据最大化问题的约束方向与变量符号写出对偶，并从二维可行域的几何结构求指定顶点。

Kai​

(1)​

スラック変数 x4,x5x_4,x_5 を導入した初期辞書は

z=−2x1+5x2−4x3,x4=7−3x1−3x2+5x3,x5=4−7x1+3x2−7x3.\begin{aligned} z&=-2x_1+5x_2-4x_3,\\ x_4&=7-3x_1-3x_2+5x_3,\\ x_5&=4-7x_1+3x_2-7x_3. \end{aligned}

x2x_2 を流入変数、x4x_4 を流出変数としてピボットすると

x2=73−x1+53x3−13x4,x5=11−10x1−2x3−x4,z=353−7x1+133x3−53x4.\begin{aligned} x_2&=\frac73-x_1+\frac53x_3-\frac13x_4,\\ x_5&=11-10x_1-2x_3-x_4,\\ z&=\frac{35}{3}-7x_1+\frac{13}{3}x_3-\frac53x_4. \end{aligned}

次に x3x_3 を流入変数、x5x_5 を流出変数としてピボットすると

x3=112−5x1−12x4−12x5,x2=232−283x1−76x4−56x5,z=712−863x1−236x4−136x5.\begin{aligned} x_3&=\frac{11}{2}-5x_1-\frac12x_4-\frac12x_5,\\ x_2&=\frac{23}{2}-\frac{28}{3}x_1-\frac76x_4-\frac56x_5,\\ z&=\frac{71}{2}-\frac{86}{3}x_1-\frac{23}{6}x_4-\frac{13}{6}x_5. \end{aligned}

非基底変数の係数がすべて非正なので最適である。x1=x4=x5=0x_1=x_4=x_5=0 として

(x1∗,x2∗,x3∗)=(0,232,112),z∗=712.\boxed{(x_1^*,x_2^*,x_3^*)=\left(0,\frac{23}{2},\frac{11}{2}\right)}, \qquad \boxed{z^*=\frac{71}{2}}.

(2)​

双対変数を y1,y2≥0y_1,y_2\geq0 とすると

D:minimize7y1+4y2subject to3y1+7y2≥−2,3y1−3y2≥5,−5y1+7y2≥−4,y1,y2≥0.\mathcal D:\quad \begin{array}{ll} \text{minimize} & 7y_1+4y_2\\ \text{subject to} & 3y_1+7y_2\geq-2,\\ &3y_1-3y_2\geq5,\\ &-5y_1+7y_2\geq-4,\\ &y_1,y_2\geq0. \end{array}

(3)​

第 1 制約は y1,y2≥0y_1,y_2\geq0 のもとで自動的に成り立つ。残りの制約は

y2≤y1−53,y2≥5y1−47,y1,y2≥0y_2\leq y_1-\frac53, \qquad y_2\geq\frac{5y_1-4}{7}, \qquad y_1,y_2\geq0

であり、実行可能領域は 2 本の半直線の間にある右向きのくさび形である。

y2
^                         y2 = y1 - 5/3
|                       /
|                     /   feasible
|                   /    region
|                 *------->
|                /
|               /  y2 = (5y1 - 4)/7
+------------------------------------> y1
               (23/6, 13/6)

2 直線の交点は

y1−53=5y1−47y_1-\frac53=\frac{5y_1-4}{7}

を解いて

(y1,y2)=(236,136).\boxed{(y_1,y_2)=\left(\frac{23}{6},\frac{13}{6}\right)}.

これが実行可能領域の唯一の頂点である。ここでの目的値は 7(23/6)+4(13/6)=71/27(23/6)+4(13/6)=71/2 となり、主問題の最適値とも一致する。

本页目录