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

Author

祭音Myyura

Description

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

ただし， の変数は であり，入力は である． また，上付き添え字 はベクトルまたは行列の転置を表し， はベクトル の各要素が非負であることを示す．

(1) の双対問題 を書け．ただし， の変数は とする．

(2) と が実行可能であると仮定し， と をそれぞれ と の実行可能解とする． このとき， を示せ．（つまり，弱双対定理を示せ．）

(3) 以下の入力のときの の最適解と最適値を求めよ．

Kai

(1)

(2)

が の実行可能解なので、。

が の実行可能解なので、。

よって、

(3)

シンプレックス法で解くと、

を得る。最適値は である。