線形計画法 総合スレッド

線形計画法 総合スレッド

ある工事完了に必要な作業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という変数も考えています。
上の解答は間違っていますか？

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

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

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