神戸大学 システム情報学研究科 2019年8月実施 専門科目 数理計画

标签：

• Kobe-University
• Production-Planning
• Simplex-Method
• Linear-Programming-Duality

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

ある工場で製品 A, B の生産計画を立てる。製品を 1 kg 生産するために必要な原料量と利益は次のとおりである。

製品	原料 x	原料 y	利益
A	9 kg	4 kg	7 万円
B	4 kg	5 kg	12 万円

原料 x, y の供給可能量はそれぞれ 1080 kg, 600 kg である。利益が最大となる生産計画について，以下に答えよ。

1. 線形計画問題 $(P)$ として定式化せよ。
2. $(P)$ を図式解法で解き，最適解と最適値を求めよ。
3. $(P)$ を標準形 $(P_s)$ に変換し，シンプレックス表で解け。また，問 2 の図式解法との関係を説明せよ。
4. $(P)$ の双対問題 $(D)$ を定式化し，図式解法で解け。最適解と最適値も求めよ。
5. $(D)$ が $(P)$ に対してもつ意味と，工場経営に利用できる理由を説明せよ。

题目描述

某工厂生产 A、B 两种产品。每生产 1 kg 产品 A，需原料 x 9 kg、原料 y 4 kg，利润为 7 万日元；每生产 1 kg 产品 B，需原料 x 4 kg、原料 y 5 kg，利润为 12 万日元。原料 x、y 的供应上限分别为 1080 kg、600 kg。

1. 将利润最大化问题写成线性规划 $(P)$。
2. 用图解法求 $(P)$ 的最优解与最优值。
3. 将 $(P)$ 化为标准形 $(P_s)$，用单纯形表求解，并说明它与第 2 问图解法的关系。
4. 写出 $(P)$ 的对偶问题 $(D)$，用图解法求其最优解与最优值。
5. 说明对偶问题相对于原问题的含义，以及它能为工厂经营提供什么信息。

Kai

(1)

製品 A, B の生産量をそれぞれ $x_A,x_B$ kg とする。求める問題は

$$\begin{aligned} (P)\qquad \max\quad &z=7x_A+12x_B\\ \text{s.t.}\quad &9x_A+4x_B\le1080,\\ &4x_A+5x_B\le600,\\ &x_A,x_B\ge0 \end{aligned}$$

である。目的関数の単位は万円である。

(2)

実行可能領域の頂点と目的関数値を調べる。2 本の境界線の交点は

$$9x_A+4x_B=1080,\qquad 4x_A+5x_B=600$$

より

$$(x_A,x_B)=\left(\frac{3000}{29},\frac{1080}{29}\right).$$

図の概形は次のとおりである（縮尺は一定でない）。

x_B
 ↑
270 ●╲                    L_x: 9x_A+4x_B=1080
    │ ╲
    │  ╲
120 ●····╲····            L_y: 4x_A+5x_B=600
    │      ╲  ····
37.2│        × C  ····
    │        │╲       ···
    │        │ ╲         ·
  0 └────────┼──●─────────●──→ x_A
           103.4 120      150

C=(3000/29,1080/29)，実行可能領域は両直線の左下側
L_x: (0,270) -- C -- (120,0)
L_y: (0,120) -- C -- (150,0)

各頂点での値は

$$\begin{array}{c|c} (x_A,x_B)&z=7x_A+12x_B\\ \hline (0,0)&0\\ (120,0)&840\\ \left(\dfrac{3000}{29},\dfrac{1080}{29}\right)&\dfrac{33960}{29}\\ (0,120)&1440 \end{array}$$

である。したがって

$$\boxed{(x_A^*,x_B^*)=(0,120),\qquad z^*=1440\text{ 万円}}.$$

(3)

スラック変数 $s_x,s_y\ge0$ を導入すると，標準形は

$$\begin{aligned} (P_s)\qquad \max\quad &z=7x_A+12x_B\\ \text{s.t.}\quad &9x_A+4x_B+s_x=1080,\\ &4x_A+5x_B+s_y=600,\\ &x_A,x_B,s_x,s_y\ge0 \end{aligned}$$

となる。初期表で目的関数係数の絶対値が最大の $x_B$ を入れる。比率は

$$\frac{1080}{4}=270,\qquad \frac{600}{5}=120$$

なので $s_y$ を出し，第 2 行の $5$ を軸に 1 回ピボットする。

$$\begin{array}{c|rrrr|r} \text{基底}&x_A&x_B&s_x&s_y&\text{右辺}\\ \hline s_x&9&4&1&0&1080\\ s_y&4&5&0&1&600\\ \hline z&-7&-12&0&0&0 \end{array} \quad\longrightarrow\quad \begin{array}{c|rrrr|r} \text{基底}&x_A&x_B&s_x&s_y&\text{右辺}\\ \hline s_x&\dfrac{29}{5}&0&1&-\dfrac45&600\\ x_B&\dfrac45&1&0&\dfrac15&120\\ \hline z&\dfrac{13}{5}&0&0&\dfrac{12}{5}&1440 \end{array}.$$

最終行は

$$z=1440-\frac{13}{5}x_A-\frac{12}{5}s_y$$

を表すため，これ以上 $z$ を増加させる非基底変数はない。よって

$$\boxed{x_A=0,\qquad x_B=120,\qquad s_x=600,\qquad s_y=0,\qquad z=1440}.$$

シンプレックス法の各基底実行可能解は図式解法における頂点に対応する。このピボットは原点 $(0,0)$ から頂点 $(0,120)$ への移動であり，問 2 と同じ最適頂点を得る。

(4)

原料 x, y の双対変数をそれぞれ $u,v\ge0$ とすると，双対問題は

$$\begin{aligned} (D)\qquad \min\quad &w=1080u+600v\\ \text{s.t.}\quad &9u+4v\ge7,\\ &4u+5v\ge12,\\ &u,v\ge0 \end{aligned}$$

である。2 本の境界線の交点は $u=-13/29<0$ となるため，第 1 象限では第 2 制約が下側境界を定める。

v
↑  実行可能領域
│  ███████████
│  ███████████
12/5 ●████████
│      ╲██████   4u+5v=12
│       ╲█████
0 └──────●████────────→ u
         3

下側境界の端点 $(u,v)=(3,0),(0,12/5)$ を比較すると

$$w(3,0)=3240,\qquad w\left(0,\frac{12}{5}\right)=1440.$$

となる。目的係数は正なので，非有界方向では目的値が増加する。したがって図式解法より

$$\boxed{(u^*,v^*)=\left(0,\frac{12}{5}\right),\qquad w^*=1440\text{ 万円}}.$$

強双対性により $z^*=w^*=1440$ であり，問 2, 3 の結果とも一致する。

(5)

$u,v$ は原料 x, y の 1 kg 当たりの影価格である。双対制約は，各製品に必要な原料の評価額がその製品の利益以上であることを表し，双対目的関数は保有資源全体の評価額を最小化している。

最適解では

$$u^*=0,\qquad v^*=\frac{12}{5}=2.4$$

である。したがって，最適基底が変わらない範囲では，原料 x を 1 kg 増やしても最大利益は増えない一方，原料 y を 1 kg 増やすと最大利益は 2.4 万円増える。実際，最適解では原料 x が 600 kg 余り，原料 y は全量を使用している。

よって影価格は，どの原料がボトルネックか，追加購入や設備投資にいくらまで支払う価値があるかを判断する指標となる。