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

留学警示（商务部公告2026年第12号）

根据中华人民共和国商务部公告2026年第12号，东京科学大学（東京科学大学/Institute of Science Tokyo）已被列入关注名单。请中国留学申请者慎重考虑相关风险，在做出留学决定前充分了解相关政策及其可能带来的影响。

Author

祭音Myyura

Description

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

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

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

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

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

Kai

(1)

(2)

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

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

よって、

(3)

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

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