2003年度　数理計画法　中間試験問題 [50点満点]

問題 1.[8点]
    (a)    線形計画問題とはどのような数理計画問題か？ 簡潔に説明しなさい。
[ヒント: 目的関数, 制約, 線形 というキーワードを使うこ と]

    (b)    次の問題を線形計画問題として定式化しなさい （問題を解く必要はない）。
ある工場では、４種類の原料A, B, C, D を用いて３種類の製品X, Y, Z を生産 している。 各製品を一単位だけ生産するのに必要な原料の量(単位：kg)は以下の表のようになる。
  X Y Z
A 5 0 6
B 0 2 8
C 7 0 15
D 3 11 0
製品を一単位生産するごとに得られる利益は、 製品Xは70万円、製品Yは120万円、製品Zは30万円となっている。 現在、工場に原料Aは80kg, 原料Bは50kg, 原料Cは100kg, 原料Dは70kg ある。このような条件のもとで、製品を生産して最大の総利益を得るには、どのような 生産計画をたてれば良いか?
[ヒント: 製品 $ X$ を $ x$ 単位, 製品 $ Y$ を $ y$ 単位, 製品 $ Z$ を $ z$ 単 位つくるものとして定式化すれば良い。 各変数の非負条件を忘れないこと。]


問題 2.[14点]
    (a)    単体法における巡回について簡潔に説明しなさい。
[ヒント：「同じ辞書が繰り返し現れる」、「単体法が終了しない」という ポイントを押さえること]

    (b)    単体法における最小添字規則について簡潔に説明しなさい。
[ヒント：ピボット演算, 基底に入れる非基底変数, 基底から出す基底変数, 添字が最小, などのキーワードを使うこと]

    (c)    次の線形計画問題を最小添字規則に従って単体法で解きなさい。 答えだけではなく、解いている途中で現れる辞書や基底解も書くこと。

\begin{displaymath} \begin{array}{\vert\vert lrrrrrrrrrr} 最小化 & -3 x_1 & - 2... ...space*{-5.5cm} x_1 \geq 0,\ x_2 \geq 0,\ x_3 \geq 0 \end{array}\end{displaymath}

     (余力のある人へ：相補性定理を使って上記の答えが正しいことを確認しよう)
[ヒント：途中で計算がおかしくなったと思ったら、現在の基底解が許容解か どうか調べてみること。ちなみに2回のピボット演算で終了し、最適値は-21/2。]


問題 3.[11点]
    (a)    ２段階単体法について簡潔に説明しなさい。
[ヒント：一段階目、補助問題、実行可能性判定、許容辞書、 二段階目、非有界性判定、最適解, などのキーワードを使うこと]

    (b)    下記の線形計画問題は実行可能な問題である。 この問題に対し、２段階単体法の第１段階目を使って許容辞書を求めなさい。 なお、単体法を使うときには、必ずしも最小添字規則に従う必要はない。 途中の計算過程も書くこと。

\begin{displaymath} \begin{array}{\vert\vert lrrrrrrrrrr} 最小化 & 3 x_1 & + x_... ...\ & & & & &\hspace*{-3cm} x_1 \geq 0,\ x_2 \geq 0 \end{array}\end{displaymath}

    (上記で得られた基底解が元の問題の許容解になっていることを確認しよう)
[ヒント：2回または3回のピボット演算で終了する。]


問題 4.[17点]
    (a)     次の線形計画問題[P]

   [P] \begin{displaymath} \begin{array}{\vert\vert ccllllllllllllllllll} 最小化 & c_1 ... ...2} x_{2} & + \ \cdots & + \ a_{mn} x_{n} \geq b_m \end{array}\end{displaymath}

の双対問題が[D]のようになることを以下の手順にしたがって示しなさい。

   [D] \begin{displaymath} \begin{array}{\vert\vert cclllllllllllllllllllll} 最大化 & b... ...{-8cm} y_1 \geq 0,\ y_2 \geq 0\ \cdots, y_m \geq 0 \end{array}\end{displaymath}

        (a-1)    問題 [P] を不等式標準形に変換しなさい(結果だけ書けば良い)。
        (a-2)    (a-1) で得られた問題の双対問題をつくりなさい。 (結果だけ書けば良い)
        (a-3)    (a-2) で得られた問題の変数や制約式 を整理すると問題 [D] が得られることを示しなさい。
[ヒント：不等式標準形の定義、およびそれに対する双対問題の形を 思いだそう。]

    (b)    問題 [P] の任意の許容解 $ x$$ = (x_1, x_2, ..., x_n)$ と問題 [D] の任意の許容解 $ y$$ = (y_1, y_2, ..., y_m)$ に対して、 不等式 $ \displaystyle \sum_{j=1}^n c_j x_j \geq \sum_{i=1}^m b_i y_i$ が 成り立つことを証明しなさい。
[ヒント：不等式標準形の場合の弱双対定理の証明をそのまま書かないこと。 途中の等号、不等号がなぜ成り立つのか、きちんと説明すること。 変数 $ y_i$ の非負性を使っていることを忘れないこと。]

        (c)    問題 [P] が非有界ならば、問題 [D] は実行不可能になること を証明しなさい。なお、証明のときに (b) で示した不等式を使っても良い。
[ヒント：授業でやった証明と同じです。 その際、$ x$, $ y$ が何を表すのか、きちんと説明すること。]