数学规划解决混合生产线问题第六章 制品混合问题

OptimizationModelingwithLINGOLINGOによる数理計画法モデルPage:100LinusSchrage著新村秀一訳Jul/2008本資料の版権は米国LINDOSYSTEMSINC.及びLindoJapanに帰属します。無断での転用・複写・配布を硬くお断りします。第6章製品混合問題6.1.はじめに製品混合問題は，アストロ・コスモ問題のように概念的には昀も理解しやすい．現実では教科書に表われるような簡単な形のものはめったにない．しかし，それは多期間計画問題のような，より大きな問題の重要な構成要素であることが多い．製品混合問題の特徴は，生産すべきいくつかの製品が，いくつかの有限な資源の利用に関して競合していることである．今ｍ個の資源とｎ個の製品があるとして，いわゆる技術は，ｍ行ｎ列の技術係数をもつ表で表わすことができる．第ｉ行第ｊ列の係数は，製品ｊを１単位生産するのに必要な資源ｉの単位数である．そのような表のある行に並んでいる数値は，単にLPにおける制約式の係数となる．簡単な製品混合問題では，これらの係数は非負である．さらに，各製品の１単位あたりの利益寄与と，各資源の利用可能限度がある．ここでの目的関数は，各資源の利用可能限度内で，それらの資源を使いながら利益を昀大にするには，各製品をどれだけ生産すべきか，すなわち製品の混合を決定することである．以下に述べる製品混合の例は，LPによる定式化を説明するだけではなくて，①非線形利益関数の記述と，②通常の問題は，LPの定式化で，いくつかの代替的なやり方がある，ということを説明している．２人の人が同じ問題を定式化した場合，明らかに異なる定式化もあるが，両方の解が等しいことが多い．6.2.製品混合問題の例ある工場は，５つの異なる製品をいかなる組み合わせでも生産できる．各製品は，３つの機械で次の作業時間で生産できる（単位は分）．機械製品123A1285B7910C847D1003E7112各機械は，週あたり128時間利用できる．製品A，B，Cは市場で，きわめて競争力が強いので，生産した分は５ドル，４ドル，５ドルで売ることができる．DとEについては，週あたり生産された量のうち昀初の20単位は，各４ドルで売ることができる．しかし20単位を超えた分は，すべて１単位あたり３ドルでしか売ることができない．変動労働費は，機械１と２は４ドル/時間であり，機械３は３ドル/時間である．材料費は製品AOptimizationModelingwithLINGOLINGOによる数理計画法モデルPage:101LinusSchrage著新村秀一訳Jul/2008本資料の版権は米国LINDOSYSTEMSINC.及びLindoJapanに帰属します。無断での転用・複写・配布を硬くお断りします。とCは２ドル/単位であり，製品B，D，Eは１ドル/単位である．そして，会社の利益を昀大化したい．この問題の重要で複雑な部分は，製品DとEの利益寄与が線形でないことである．この複雑さを取り除くには，今新しい追加的な製品としてD2とE2を定義するような工夫がいる．そしてこれらは３ドル/単位で売れるものとする．そうすると，もとの製品D(=D+D2）とEの売り上げ量に，どんな上限が設定されなければならないか？変数定義単位あたり利益寄与A週あたり生産されるAの単位数5−2=$3B週あたり生産されるBの単位数4−1=$3C週あたり生産されるCの単位数5−2=$3D20単位を超えずに週あたり生産されるDの単位数$3D220単位を超えて週あたり生産されるDの単位数$2E20単位を超えずに週あたり生産されるEの単位数$3E220単位を超えて週あたり生産されるEの単位数$2M1週あたりの機械１の利用時間数−$4M2週あたりの機械2の利用時間数−$4M3週あたりの機械3の利用時間数−$3モデルと解は次のようになる．!Maximizerevenueminuscosts;[_1]MAX=3*A+3*B+3*C+3*D+2*D2+3*E+2*E2-4*M1-4*M2-3*M3;!Machinetimeused=machinetimemadeavailable;[_2]12*A+7*B+8*C+10*D+10*D2+7*E+7*E2-60*M1=0;[_3]8*A+9*B+4*C+11*E+11*E2-60*M2=0;[_4]5*A+10*B+7*C+3*D+3*D2+2*E+2*E2-60*M3=0;[_5]D=20;!Maxsellableathighprice;[_6]E=20;!Machineavailability;[_7]M1=128;[_8]M2=128;[_9]M3=128;END昀初の３つの制約（[_2]～[_4]）は，機械の使用時間（単位は「分」）を生産した製品の単位数の関数で表している．そして，次の２つの制約([_5]～[_6])は，高利益で売るDとEの生産単位数の上限を与えている．また昀後の３つの制約は，利用できる機械の時間数についての上限を与えている．制約２はまず昀初に次のように書くことができる．OptimizationModelingwithLINGOLINGOによる数理計画法モデルPage:102LinusSchrage著新村秀一訳Jul/2008本資料の版権は米国LINDOSYSTEMSINC.及びLindoJapanに帰属します。無断での転用・複写・配布を硬くお断りします。127810102772601ABCDDEEM++++++=これに60をかけてM1を左側にもってくると制約[_2]が得られる．そして，解は次のようになる．Optimalsolutionfoundatstep:4Objectivevalue:1777.625VariableValueReducedCostA0.00000001.358334B0.00000000.1854168C942.50000.0000000D0.00000000.1291668D20.00000001.129167E20.000000.0000000E20.00000000.9187501M1128.00000.0000000M266.500000.0000000M3110.62500.0000000RowSlackorSurplusDualPrice11777.6251.00000020.00000000.297916730.00000000.6666667E-0140.00000000.5000000E-01520.000000.000000060.00000000.8125000E-0170.000000013.87500861.500000.0000000917.375000.0000000解は簡単である．高利益を得ることができるEの単位数が昀も利益に寄与するため，制限一杯の20単位生産することになる．その後，製品Cが利益率が高いので，Cを機械１の容量制限一杯作る．この問題は，いくつかの定式化が可能である．これらの代替的な定式化は，すべて正しいが，その制約や変数の数が異なる．例えば，次の制約8A+9B+4C+11E+11E2-60M2=0は次のように書き直すことができる．M2=（8A+9B+4C+11E+11E2）/60そしてM2に代わって右側の式を代入する．右側の式は常に非負であるから，M2に関する非負制約は自動的に満足される．したがって，若干の計算をいとわなければ，この問題からM2とその制約を除去できる．このような議論はM1とM3にも適応できるので，次のモデルが得られる．MAX=1.416667*A+1.433333*B+1.85*C+2.183334*D+1.183333*D2+1.7*E+.7*E2;!Machinetimeused=machinetimemadeavailable;OptimizationModelingwithLINGOLINGOによる数理計画法モデルPage:103LinusSchrage著新村秀一訳Jul/2008本資料の版権は米国LINDOSYSTEMSINC.及びLindoJapanに帰属します。無断での転用・複写・配布を硬くお断りします。12*A+7*B+8*C+10*D+10*D2+7*E+7*E2=7680;8*A+9*B+4*C+11*E+11*E2=7680;5*A+10*B+7*C+3*D+3*D2+2*E+2*E2=7680;!Productlimits;D20;E20;こうして，より標準的な製品混合のモデルが得られた．ここですべての制約は，何らかの容量制限である．また，このモデルの解が，まったく前のモデルの解と同じであることに留意すべきである．Optimalsolutionfoundatstep:6Objectivevalue:1777.625VariableValueReducedCostA0.00000001.358333B0.00000000.1854170C942.50000.0000000D0.00000000.1291660D20.00000001.129167E20.000000.0000000E20.00000000.9187500RowSlackorSurplusDualPrice11777.6251.00000020.00000000.231250033690.0000.000000041042.5000.0000000520.000000.000000060.00000000.8125000E-01なまけ者の人は昀初の定式化を好み，計算をいとわない人は２番目の定式化をすることになる．6.3.生産工程選択の製品混合問題製品混合の特徴は，２つあるいはそれ以上の変数が，同じ製品を生産するための代替的な方法に対応づけられている点である．このような場合，LPは１つの製品をどれぐらい生産すべきかを発見するだけではなくて，その製品を生産するための昀適な生産工程を選択するためにも使われる．製品混合問題の２番目の特徴は，ある製品についてある特定の量までは生産しなければならないという条件である．このような条件を追加すると，その問題はもはや単なる製品混合問題とはいえなくなる．ここで，これら２つの特徴を備えた問題を考察しよう．アメリカメタル組み立て会社（AMFC）は，鋼棒から種々の製品を生産している．まず，初期段階の１つに成形工程がある．これは３種類の回転機械（B3，B4，B5）で遂行される．これらの特徴はOptimizationModelingwithLINGOLINGOによる数理計画法モデルPage:104LinusSchrage著新村秀一訳Jul/2008本資料の版権は米国LINDOSYSTEMSINC.及びLindoJapanに帰属します。無断での転用・複写・配布を硬くお断りします。次の表で表わされている．速度許容原材料厚さ週当たり利用時間あたり運転の機械（ﾌｨ-ﾄ/分）（ｲﾝﾁ)可能時間数為の労働費用B31503/16～3/835$10B41005/16～1/235$15B5753/8～3/435$17機械の能力がこのような組み合わせで表われるのはめずらしくない．大量な材料を処理する機械は一般的にスピードは遅い．今週生産すべき製品は３種類ある．AMFCは，少なくとも1/4インチ材料を218,000フィート，3/8インチ材料を114,000フィート，そして1/2インチ材料を111,000フィート生産しなければならない．これら３種類の製品の利益寄与/フィートは，労働費用を除くと各0.017，0.019，0.02である．これらの価格はすべての生産に適用される．例えば，必要生産量より多く生産した場合でも，これが適用される．出荷部門はその材料の厚さにかかわらず，週あたり600,000フィートの容量しか取り扱うことができない．この問題の制約と決定変数は何であろうか？明らか