跳到主要内容

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

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

次の線形計画問題を考える。

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 の実行可能集合を図示し、その唯一の端点を求めよ。

题目描述​

给定线性规划问题

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. 运用单纯形法求出 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 本の半直線の間にある右向きのくさび形である。

双対問題の実行可能領域

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 となり、主問題の最適値とも一致する。

本页目录