跳到主要内容

早稲田大学 創造理工学研究科 経営システム工学専攻 2018年7月実施 オペレーションズリサーチ 問題9

标签：

Author​

祭音Myyura

Description​

  1. 次の線形計画問題 (P)(P) について答えよ。

    maximizez=5x1+3x2+2x3subject tox1+x2+2x3≤4,2x1+x2+x3≤5,2x1+2x2+x3≤9,x1,x2,x3≥0.\begin{array}{ll} \text{maximize}&z=5x_1+3x_2+2x_3\\ \text{subject to} &x_1+x_2+2x_3\leq4,\\ &2x_1+x_2+x_3\leq5,\\ &2x_1+2x_2+x_3\leq9,\\ &x_1,x_2,x_3\geq0. \end{array}
    1. pivot の列・行を示して単体法で解け。
    2. 双対問題を示せ。
    3. 主・双対問題の最適目的関数値が一致することを示せ。
    4. 第1制約の右辺を正の微小量だけ増加させたときの最適目的関数値の変化を求めよ。
    5. 最適基底行列の逆行列を積形式で示せ。

  2. 有向グラフ上の巡回セールスマン問題を、部分巡回路除去制約を含めて定式化せよ。

Kai​

[小問 1-1]​

スラック変数 s1,s2,s3s_1,s_2,s_3 を加える。表の最下段は cj−zjc_j-z_j である。

初期表​

基底右辺x1x_1x2x_2x3x_3s1s_1s2s_2s3s_3
s1s_14112100
s2s_25211010
s3s_39221001
cj−zjc_j-z_j532000

x1x_1 列を pivot 列とする。比は 4,5/2,9/24,5/2,9/2 なので s2s_2 行が pivot 行である。

第1 pivot 後​

基底右辺x1x_1x2x_2x3x_3s1s_1s2s_2s3s_3
s1s_13/23/201/21/23/23/21−1/2-1/20
x1x_15/25/211/21/21/21/201/21/20
s3s_340100-11
cj−zjc_j-z_j01/21/2−1/2-1/20−5/2-5/20

次に x2x_2 列を pivot 列とする。比は 3,5,43,5,4 なので s1s_1 行が pivot 行である。

第2 pivot 後​

基底右辺x1x_1x2x_2x3x_3s1s_1s2s_2s3s_3
x2x_230132-10
x1x_1110-1-110
s3s_3100-3-201
cj−zjc_j-z_j00-2-1-20

すべての cj−zj≤0c_j-z_j\leq0 なので最適である。したがって

(x1,x2,x3)=(1,3,0),z∗=14.\boxed{(x_1,x_2,x_3)=(1,3,0)},\qquad \boxed{z^*=14}.

[小問 1-2]​

双対問題 (D)(D) は

minimize4y1+5y2+9y3subject toy1+2y2+2y3≥5,y1+y2+2y3≥3,2y1+y2+y3≥2,y1,y2,y3≥0.\begin{array}{ll} \text{minimize}&4y_1+5y_2+9y_3\\ \text{subject to} &y_1+2y_2+2y_3\geq5,\\ &y_1+y_2+2y_3\geq3,\\ &2y_1+y_2+y_3\geq2,\\ &y_1,y_2,y_3\geq0. \end{array}

[小問 1-3]​

(y1,y2,y3)=(1,2,0)\boxed{(y_1,y_2,y_3)=(1,2,0)}

は双対実行可能であり、目的値は

4(1)+5(2)+9(0)=14=z∗.4(1)+5(2)+9(0)=14=z^*.

主・双対の実行可能解の目的値が一致したので、弱双対性から両者は最適である。

[小問 1-4]​

第1制約の右辺を 4+δ4+\delta とする。最適双対変数 y1=1y_1=1 は第1資源の影価格なので、同じ基底が実行可能な範囲では

z∗(δ)=14+δ.\boxed{z^*(\delta)=14+\delta}.

実際、最適基底を (x2,x1,s3)(x_2,x_1,s_3) の順に取ると

(x2,x1,s3)=(3+2δ,1−δ,1−2δ).(x_2,x_1,s_3)=(3+2\delta,1-\delta,1-2\delta).

したがって 0≤δ≤1/20\leq\delta\leq1/2 ではこの式が成立し、正の微小増加に対する目的値の増加率は1である。

[小問 1-5]​

最適基底行列を列 (x2,x1,s3)(x_2,x_1,s_3) の順に

B=(110120221)B=\begin{pmatrix}1&1&0\\1&2&0\\2&2&1\end{pmatrix}

とする。2回の pivot に対応する行基本変形行列は

E1=(1−1/2001/200−11),E2=(200−110−201).E_1=\begin{pmatrix}1&-1/2&0\\0&1/2&0\\0&-1&1\end{pmatrix},\qquad E_2=\begin{pmatrix}2&0&0\\-1&1&0\\-2&0&1\end{pmatrix}.

よって積形式の逆行列は

B−1=E2E1=(2−10−110−201).\boxed{ B^{-1}=E_2E_1 =\begin{pmatrix}2&-1&0\\-1&1&0\\-2&0&1\end{pmatrix} }.

[小問 2]​

枝 (i,j)(i,j) が巡回路に含まれるとき xij=1x_{ij}=1、それ以外を0とする。定式化は

minimize∑i∈N∑j∈Nj≠icijxijsubject to∑j∈Nj≠ixij=1(i∈N),∑i∈Ni≠jxij=1(j∈N),∑i∈S∑j∈Sj≠ixij≤∣S∣−1(∅≠S⊊N),xij∈{0,1}.\begin{array}{ll} \text{minimize} &\displaystyle\sum_{i\in N}\sum_{\substack{j\in N\\j\neq i}}c_{ij}x_{ij}\\ \text{subject to} &\displaystyle\sum_{\substack{j\in N\\j\neq i}}x_{ij}=1 \quad(i\in N),\\ &\displaystyle\sum_{\substack{i\in N\\i\neq j}}x_{ij}=1 \quad(j\in N),\\ &\displaystyle\sum_{i\in S}\sum_{\substack{j\in S\\j\neq i}}x_{ij} \leq |S|-1 \quad(\varnothing\neq S\subsetneq N),\\ &x_{ij}\in\{0,1\}. \end{array}

最初の2組の制約だけでは、全頂点が複数の互いに素な閉路へ分かれる可能性がある。第3組は任意の真部分集合 SS の内部だけで閉路を完成させることを禁じる部分巡回路除去制約であり、全頂点を1回ずつ通る単一のハミルトン閉路を保証する。

目录