最適化・線形計画法の問題

ある工場では 2 種類の製品 $\mathrm{P},\mathrm{Q}$ を生産している。製品 1 単位あたりに必要な資源と利益は次のとおりである。

• 製品 $\mathrm{P}$：原料 A を $2\mathrm{kg}$、原料 B を $1\mathrm{kg}$、機械時間を $1$ 時間使い、利益は $3$ 万円
• 製品 $\mathrm{Q}$：原料 A を $1\mathrm{kg}$、原料 B を $3\mathrm{kg}$、機械時間を $1$ 時間使い、利益は $2$ 万円

使える量は、原料 A が $10\mathrm{kg}$、原料 B が $15\mathrm{kg}$、機械時間が $6$ 時間である。製品 $\mathrm{P},\mathrm{Q}$ の生産量をそれぞれ $x,y$（単位）とする。$x,y$ は $0$ 以上の実数とし、利益の合計を最大にしたい。

この問題を線形計画問題 $\max c^{\top }\mathbf{x}$, $A\mathbf{x}\le b$, $\mathbf{x}\ge 0$（$\mathbf{x}=(x,y{)}^{\top }$）の形に定式化し、原料 A・原料 B・機械時間の制約にこの順にスラック変数 $s_1,s_2,s_3(\ge 0)$ を加えて等式制約の標準形に直す。利益の合計が最大となる生産計画におけるスラック変数の値の組 $(s_1,s_2,s_3)$ を求めよ。

ある工場では $2$ 種類の製品 $\mathrm{P}$, $\mathrm{Q}$ を作っている。それぞれを $1$ 個作るのに必要な原料・作業時間・機械時間と、$1$ 個あたりの利益は次のとおりである。

• 製品 $\mathrm{P}$：原料 $2\mathrm{kg}$、作業時間 $1$ 時間、機械時間 $3$ 時間、利益 $4$ 千円
• 製品 $\mathrm{Q}$：原料 $1\mathrm{kg}$、作業時間 $3$ 時間、機械時間 $2$ 時間、利益 $5$ 千円

$1$ 日に使える量は、原料 $10\mathrm{kg}$、作業時間 $15$ 時間、機械時間 $18$ 時間までである。製品 $\mathrm{P}$, $\mathrm{Q}$ の $1$ 日の生産量をそれぞれ $x_1$, $x_2$（$0$ 以上の実数）とし、$1$ 日の利益を最大にする問題を
$$\max c^{\top }x,Ax\leqq b,x\geqq 0\left(x=\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)\right)$$
の形に定式化する。ただし $A$ の第 $1$ 行・第 $2$ 行・第 $3$ 行をそれぞれ原料・作業時間・機械時間の制約とする。

さらに、各制約に $0$ 以上のスラック変数 $s_1$（原料）, $s_2$（作業時間）, $s_3$（機械時間）を加えて、等式制約の標準形
$$Ax+s=b,x\geqq 0,s\geqq 0\left(s=\left(\begin{array}{c}{s}_1\\ s_2\\ s_3\end{array}\right)\right)$$
に直す。生産計画 $(x_1,x_2)=(2,3)$ に対応するスラック変数の値 $(s_1,s_2,s_3)$ をこの順に求めよ。

実数 $x_1,x_2$ についての次の線形計画問題を考える。
$$\begin{array}{rl}\text{maximize}& z=3x_1+2x_2\\ \text{subject to}& x_1+x_2\leqq 4\\ & 2x_1+x_2\leqq 6\\ & x_1\geqq 0,x_2\geqq 0\end{array}$$
スラック変数 $s_1,s_2(\geqq 0)$ を導入し、原点 $(x_1,x_2)=(0,0)$ を初期基底解として単体法で解け。入る変数は目的関数の係数（被約費用）が最大の非基底変数とする。最適解 $(x_1,x_2)$ と最適値 $z$ を、組 $(x_1,x_2,z)$ の形でこの順に答えよ。

実数 $x_1,x_2$ についての次の線形計画問題を考える。
$$\begin{array}{rl}\text{maximize}& z=4x_1+3x_2\\ \text{subject to}& x_1+x_2\leqq 5\\ & 2x_1+x_2\leqq 8\\ & x_1\geqq 0,x_2\geqq 0\end{array}$$
スラック変数を導入して初期辞書（またはシンプレックス表）を作り、単体法で解け。入る変数は目的関数の係数が最大の非基底変数とし、出る変数は最小比テストで決めること。最適解 $(x_1,x_2)$ と最適値 $z$ を、組 $(x_1,x_2,z)$ の形でこの順に答えよ。

実数 $x_1,x_2$ についての次の線形計画問題を考える。
$$\begin{array}{rl}\text{maximize}& z=3x_1+2x_2\\ \text{subject to}& x_1+x_2\leqq 4\\ & 2x_1+x_2\leqq 6\\ & x_2\leqq 3\\ & x_1\geqq 0,x_2\geqq 0\end{array}$$
スラック変数 $s_1,s_2,s_3(\geqq 0)$ を加えて初期辞書を作り、単体法（入る変数には目的関数の行で係数が正のもののうち最大のものを選ぶ）で解け。最適解 $(x_1,x_2)$ と最適値 $z$ を、組 $(x_1,x_2,z)$ の形で答えよ。