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

ある工場では $2$ 種類の製品 $\mathrm{X},\mathrm{Y}$ を作っている。製品 $\mathrm{X}$ を $1$ 単位作るには原料 $\mathrm{P}$ が $2\mathrm{kg}$、原料 $\mathrm{Q}$ が $1\mathrm{kg}$、機械の稼働時間が $1$ 時間必要で、利益は $3$ 万円である。製品 $\mathrm{Y}$ を $1$ 単位作るには原料 $\mathrm{P}$ が $1\mathrm{kg}$、原料 $\mathrm{Q}$ が $3\mathrm{kg}$ 必要で、機械は使わず、利益は $4$ 万円である。$1$ 日に使える原料 $\mathrm{P}$ は $10\mathrm{kg}$、原料 $\mathrm{Q}$ は $15\mathrm{kg}$、機械の稼働時間は $4$ 時間までである。

製品 $\mathrm{X},\mathrm{Y}$ の $1$ 日の生産量をそれぞれ $x,y$ 単位（$x,y$ は $0$ 以上の実数）として、$1$ 日の利益（万円）を最大にする線形計画問題 $\max c^{\top }\mathbf{x}$, $A\mathbf{x}\le b$, $\mathbf{x}\ge 0$ を立てる。ただし制約は原料 $\mathrm{P}$、原料 $\mathrm{Q}$、機械の稼働時間の順に並べる。この $3$ つの不等式制約にそれぞれスラック変数 $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)$ の形でこの順に答えよ。

$c$ を実数の定数とし、次の線形計画問題 $({\mathrm{Q}}_c)$ を考える。
$$({\mathrm{Q}}_c)\begin{array}{rl}\text{maximize}& c{x}_1+2x_2\\ \text{subject to}& x_1+x_2\leqq 4,\\ & x_1+3x_2\leqq 6,\\ & x_1\geqq 0,x_2\geqq 0\end{array}$$
点 $x^{\ast }=(x_1,x_2)=(3,1)$ は $c$ の値によらず実行可能解である。$x^{\ast }$ が $({\mathrm{Q}}_c)$ の最適解となるような $c$ の範囲は $\alpha \leqq c\leqq \beta$ の形に表される。$\alpha$ と $\beta$ をこの順に組 $(\alpha ,\beta )$ で求めよ。

実数 $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)$ の形でこの順に答えよ。