線形計画法総合スレッド

**１３２人目の素数さん** · 2022/10/07(金) 09:35:17.57

線形計画法総合スレッド

**１３２人目の素数さん** · 2022/10/07(金) 09:49:42.08

ある工事完了に必要な作業1～6について以下の制約がある。
作業2は作業1が終わるまで開始できない。
作業3は作業1が終わるまで開始できない。
作業4は作業2と3が終わるまで開始できない。
作業5は作業3が終わるまで開始できない。
作業6は作業4と5が終わるまで開始できない。
この工事はT日以内で終えねばならず、各作業iはt_i日かかる。
しかし臨時作業員を雇うことにより作業日数を減らすことができるが、
s_i日よりは少なくはできない。また、1日減らすのにm_i万円かかる。
費用を最小にする作業計画をたてよ。

minimize: 農{i=1}^{6} m_i × (t_i - x_i)
subject to:
x_1 + x_2 + x_4 + x_6 ≦ T
x_1 + x_3 + x_4 + x_6 ≦ T
x_1 + x_3 + x_5 + x_6 ≦ T
s_i ≦ x_i ≦ t_i (i = 1, …, 6)

模範解答では各作業の開始日y_iという変数も考えています。
上の解答は間違っていますか？

**１３２人目の素数さん** · 2022/10/11(火) 10:58:53.41

単体法
内点法
双対計画
クーンタッカー条件

思いつく用語を書いて見た

**１３２人目の素数さん** · 2022/10/12(水) 09:31:13.93

英語でリニアプログラミング