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

ある工場では 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{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)$ をこの順に求めよ。

$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=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{P}}_c)$ を考える。
$$({\mathrm{P}}_c)\begin{array}{rl}\text{maximize}& c{x}_1+2x_2\\ \text{subject to}& x_1+x_2\le 4\\ & x_1+3x_2\le 6\\ & x_1\ge 0,x_2\ge 0\end{array}$$
点 $(x_1,x_2)=(3,1)$ が $({\mathrm{P}}_c)$ の最適解（の一つ）となるような $c$ の範囲は $p\le c\le q$ の形に表される。双対問題の解を用いて、$p$ と $q$ をこの順に求めよ。