跳到主要内容

神戸大学 システム情報学研究科 2017年8月実施 専門科目 システム理論 [2]

标签：

Author​

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

Description​

  1. 次の標準形線形計画問題 P1P_1 の双対問題 D1D_1 を求めよ。双対変数を w\boldsymbol w とする。

    (P1)最小化cTx制約条件Ax=b,x≥0.\begin{array}{ll} (P_1)\quad\text{最小化} & \boldsymbol c^{\mathsf T}\boldsymbol x\\ \text{制約条件} & A\boldsymbol x=\boldsymbol b,\\ & \boldsymbol x\geq\boldsymbol 0. \end{array}

    ただし c,x,b\boldsymbol c,\boldsymbol x,\boldsymbol b は列ベクトル、AA は m×nm\times n 行列であり、m<nm<n かつ rank⁡A=m\operatorname{rank}A=m とする。

  2. P1P_1 と D1D_1 の関係を利用し、次の一般形線形計画問題 P2P_2 の双対問題 D2D_2 を求めよ。双対変数を w\boldsymbol w とする。

    (P2)最小化cTx制約条件Ax≥b,x≥0.\begin{array}{ll} (P_2)\quad\text{最小化} & \boldsymbol c^{\mathsf T}\boldsymbol x\\ \text{制約条件} & A\boldsymbol x\geq\boldsymbol b,\\ & \boldsymbol x\geq\boldsymbol 0. \end{array}

    ただし P1P_1 と同様に、c,x,b\boldsymbol c,\boldsymbol x,\boldsymbol b は列ベクトル、AA は m×nm\times n 行列であり、m<nm<n かつ rank⁡A=m\operatorname{rank}A=m とする。

  3. 次の主問題 P3P_3 の双対問題 D3D_3 を作り、D3D_3 を図解法とシンプレックス・タブローにより解け。なお、P3P_3 を解く必要はない。

    (P3)最大化6x1+4x2制約条件2x1+x2≤70,3x1+4x2≤180,x1,x2≥0.\begin{array}{ll} (P_3)\quad\text{最大化} & 6x_1+4x_2\\ \text{制約条件} & 2x_1+x_2\leq70,\\ & 3x_1+4x_2\leq180,\\ & x_1,x_2\geq0. \end{array}

题目描述​

  1. 写出标准形式最小化问题 P1P_1 的对偶问题 D1D_1。
  2. 利用 P1P_1 与 D1D_1 的关系，写出不等式形式最小化问题 P2P_2 的对偶问题 D2D_2。
  3. 写出给定二维线性规划 P3P_3 的对偶 D3D_3，并分别用图解法和单纯形表求解 D3D_3；不要求求解 P3P_3。

Kai​

(1)​

P1P_1 の双対問題は

(D1)最大化bTw制約条件ATw≤c,w∈Rm\begin{array}{ll} (D_1)\quad\text{最大化} & \boldsymbol b^{\mathsf T}\boldsymbol w\\ \text{制約条件} & A^{\mathsf T}\boldsymbol w\leq\boldsymbol c,\\ & \boldsymbol w\in\mathbb R^m \end{array}

である。等式制約に対応する双対変数 w\boldsymbol w には符号制約がない。

(2)​

余剰変数 s≥0\boldsymbol s\geq\boldsymbol0 を用いると、P2P_2 の制約は

Ax−s=b,(xs)≥0A\boldsymbol x-\boldsymbol s=\boldsymbol b,\qquad \begin{pmatrix}\boldsymbol x\\\boldsymbol s\end{pmatrix}\geq\boldsymbol0

となる。(1) を行列 (A,−Im)(A,-I_m)、目的係数 (c,0)(\boldsymbol c,\boldsymbol0) に適用すると

ATw≤c,−w≤0A^{\mathsf T}\boldsymbol w\leq\boldsymbol c,\qquad -\boldsymbol w\leq\boldsymbol0

を得る。したがって

(D2)最大化bTw制約条件ATw≤c,w≥0\begin{array}{ll} (D_2)\quad\text{最大化} & \boldsymbol b^{\mathsf T}\boldsymbol w\\ \text{制約条件} & A^{\mathsf T}\boldsymbol w\leq\boldsymbol c,\\ & \boldsymbol w\geq\boldsymbol0 \end{array}

である。

(3)​

P3P_3 の双対問題は

(D3)最小化z=70w1+180w2制約条件2w1+3w2≥6,w1+4w2≥4,w1,w2≥0\begin{array}{ll} (D_3)\quad\text{最小化} & z=70w_1+180w_2\\ \text{制約条件} & 2w_1+3w_2\geq6,\\ & w_1+4w_2\geq4,\\ & w_1,w_2\geq0 \end{array}

である。

図解法​

境界直線を

L1:2w1+3w2=6,L2:w1+4w2=4L_1:2w_1+3w_2=6,\qquad L_2:w_1+4w_2=4

とする。実行可能領域は両直線の上側であり、その下側境界は次の折れ線となる（模式図）。

w2
 ↑       実行可能領域
 │       ↑ ↑ ↑ ↑ ↑
2│ A●╲
 │    ╲  L1
 │     ╲
2/5     C●╲  L2
 │          ╲
0└───────────B●════════════→ w1
 0          12/5  4

端点は

A=(0,2),C=L1∩L2=(125,25),B=(4,0).A=(0,2),\qquad C=L_1\cap L_2=\left(\frac{12}{5},\frac25\right),\qquad B=(4,0).

各点での目的関数値は

点AACCBB
zz360360240240280280

である。目的係数は正なので、非有界方向へ進めば zz は増加する。ゆえに

(w1,w2)=(125,25),zmin⁡=240.\boxed{(w_1,w_2)=\left(\frac{12}{5},\frac25\right)},\qquad \boxed{z_{\min}=240}.

シンプレックス・タブロー​

q=−zq=-z を最大化し、制約を

−2w1−3w2+s1=−6,−w1−4w2+s2=−4-2w_1-3w_2+s_1=-6,\qquad -w_1-4w_2+s_2=-4

と書く。Cj=(−70,−180,0,0)C_j=(-70,-180,0,0) として双対シンプレックス法を用いる。初期タブローは

基底CBw1w2s1s2bs10−2−310−6s20−1−401−4Cj−Zj−70−18000\begin{array}{c|r|rrrr|r} \text{基底}&C_B&w_1&w_2&s_1&s_2&b\\\hline s_1&0&-2&-3&1&0&-6\\ s_2&0&-1&-4&0&1&-4\\\hline &C_j-Z_j&-70&-180&0&0& \end{array}

である。第 11 行を離脱行とすると

−70−2=35<−180−3=60\frac{-70}{-2}=35<\frac{-180}{-3}=60

より w1w_1 が進入する。ピボット後は

基底CBw1w2s1s2bw1−70132−1203s200−52−121−1Cj−Zj0−75−350\begin{array}{c|r|rrrr|r} \text{基底}&C_B&w_1&w_2&s_1&s_2&b\\\hline w_1&-70&1&\frac32&-\frac12&0&3\\ s_2&0&0&-\frac52&-\frac12&1&-1\\\hline &C_j-Z_j&0&-75&-35&0& \end{array}

となる。第 22 行を離脱行とすると

−75−5/2=30<−35−1/2=70\frac{-75}{-5/2}=30<\frac{-35}{-1/2}=70

より w2w_2 が進入する。したがって最終タブローは

基底CBw1w2s1s2bw1−7010−4535125w2−1800115−2525Cj−Zj00−20−30\begin{array}{c|r|rrrr|r} \text{基底}&C_B&w_1&w_2&s_1&s_2&b\\\hline w_1&-70&1&0&-\frac45&\frac35&\frac{12}{5}\\ w_2&-180&0&1&\frac15&-\frac25&\frac25\\\hline &C_j-Z_j&0&0&-20&-30& \end{array}

である。右辺は非負、かつ Cj−Zj≤0C_j-Z_j\leq0 なので最適であり、

(w1,w2)=(125,25),qmax⁡=−240(w_1,w_2)=\left(\frac{12}{5},\frac25\right),\qquad q_{\max}=-240

すなわち zmin⁡=240z_{\min}=240 を得る。

本页目录