制約条件: \[\begin{cases} a_{11}x_1 + \cdots + a_{1n}x_n \le b_1 \\ a_{21}x_1 + \cdots + a_{2n}x_n \le b_2 \\ ~~~\vdots \\ a_{m1}x_1 + \cdots + a_{mn}x_n \le b_m \\ ~~x_1, \cdots, x_n \ge 0 \end{cases}\] 目的関数: $$z=c_1x_1 + \cdots + c_nx_n \to max$$ ここでは目的関数の最大化としているが、最小化問題の場合には-1を掛ければ等価である。 この線形問題を解くためには、次のようにすればよい。 スラック変数と標準形 まず、不等式で与えられた制約条件式に新たな変数を導入し、等式条件に変換する。 \[\begin{cases} a_{11}x_1 + \cdots +