線形計画法

◆線形計画法

　　複数の一次元の条件式から最適解を求める手法

参考として過去に二種試験で出題された問題を解いてみましょう．

【1998/10　問７３】
　ある工場で製品Ａ，Ｂを生産している。製品Ａを１トン製造するのに，原料
Ｐ，Ｑをそれぞれ４トン，９トン必要とし，製品Ｂについてもそれぞれ８トン，
６トン必要とする。また，製品Ａ，Ｂは，１トン当たりそれぞれ２万円，３万円
の利益を生む。しかし，原料Ｐは４０トン，Ｑは５４トンしかない。
　利益を最大にする生産量を求めるために，線形計画問題として定式化したもの
はどれか。ここで，製品Ａ，Ｂの生産量をそれぞれｘ，ｙで表すものとする。

ア　条件　４ｘ＋８ｙ≧４０　　　　イ　条件　４ｘ＋８ｙ≦４０　
　　　　　９ｘ＋６ｙ≧５４　　　　　　　　　９ｘ＋６ｙ≦５４
　　　　　ｘ≧０，ｙ≧０　　　　　　　　　　ｘ≧０，ｙ≧０
　　目的関数　２ｘ＋３ｙ→最大化　　　目的関数　２ｘ＋３ｙ→最大化

ウ　条件　４ｘ＋９ｙ≦４０　　　　エ　条件　４ｘ＋９ｙ≦２
　　　　　８ｘ＋６ｙ≦５４　　　　　　　　　８ｘ＋６ｙ≦３
　　　　　ｘ≧０，ｙ≧０　　　　　　　　　　ｘ≧０，ｙ≧０
　　目的関数　２ｘ＋３ｙ→最大化　　　目的関数　４０ｘ＋５４ｙ→最小化

解答例

制約条件
　　　　　　４ｘ＋８ｙ≦４０-------原材料Ｐの条件　　　　　　
　　　　　　９ｘ＋６ｙ≦５４-------原材料Ｑの条件
　　　　　　当然、生産量ｘ、ｙは０以上
目的関数
　　　　　　２ｘ＋３ｙ　→　最大化


�@は　ｙ≦-１／２×ｘ＋５
�Aは　ｙ≦-３／２×ｘ＋９

基底解は（０、５）、（６、０）、(４、３)となる

上記の基底解で利益が最大になるのは
　(４、３)の時となる。
また、最大の利益は
　２×４＋３×３＝１７万円

この問題は線形計画法とは違う解きかたになります。

★★★宿題：二種向け★（1999/1/12）

　表は，各顧客（ｘ，ｙ，ｚ）を営業担当者（Ａ，Ｂ，Ｃ）が分担するときの売
上高を示している。例えば，営業担当者Ａの顧客ｘに対する売上高は２百万円で
ある。各営業担当者は，顧客を一人しか担当できないとしたとき，最大の売上高
は何百万円か。

　　単位　百万円

　ア　16

　イ　17

　ウ　18

　エ　19

正解 ウです

Aが最も多い売上の顧客はｚ,B,Cがそれぞれ
同じ担当にならないようにして、全体で最大
の売上高をあげる組み合わせは
Az(5)+Bx(5)+Cz(8)=18

Bが最も多い売上の顧客はｚ,A,Cがそれぞれ
同じ担当にならないようにして、全体で最大
の売上高をあげる組み合わせは
Bz(6)+Ay(4)+Cx(7)=17

Cが最も多い売上の顧客はy,A,Bがそれぞれ
同じ担当にならないようにして、全体で最大
の売上高をあげる組み合わせは
Cy(8)+Az(5)+Bx(5)=18

地道な計算をしてしまいました。

■解答■(宿題メールより）
　　二種午前平成１１年秋問７３

> 営業担当者Aが顧客z, 営業担当者Bが顧客x, 営業担当者Cが顧客yを担当した場合
>に最大の売上高になる。
> 5(営業担当者A)＋5(営業担当者B)＋8(営業担当者C)＝18　となり, 答えはウ。

　どうもありがとうございました。

>表からそれぞれの担当者毎に売り上げが最大の顧客を見ます
>Ａ・・・ｚ
>Ｂ・・・ｚ
>Ｃ・・・ｙ
>この時点で、Ｃさんが顧客ｙを担当するのは確定するので
>Ａ，Ｂそれぞれが　x,z どちらを担当するか２パターン考えます
>
>Ａが x を担当すると
>2+6+8=16
>
>Ａが z を担当すると
>5+5+8=18
>よってウ

　どうもありがとうございました。

> 組み合わせが 6通りしかないのでやってみるのが一番早くて確実ですね。
> {A, B, C} = {x, y, z} = 2 + 3 + 6 = 11
>             {y, z, x} = 4 + 6 + 7 = 17
>             {z, x, y} = 5 + 5 + 8 = 18
>             {z, y, x} = 5 + 3 + 7 = 15
>             {y, x, z} = 4 + 5 + 6 = 15
>             {x, z, y} = 2 + 6 + 8 = 16
> から 18 が最大なので ウ。

　どうもありがとうございました。