運籌學(xué)課程設(shè)計-用MATLAB和LINGO求解生產(chǎn)問題

1、1 問題的提出生產(chǎn)問題是一類常見的線性規(guī)劃問題.在生產(chǎn)一種或多種產(chǎn)品的時候，面對多種可選擇的資源有多種不同的生產(chǎn)方案，與此同時不同的生產(chǎn)方案可以帶來不同的產(chǎn)品效益，而選擇不同的生產(chǎn)方案時所消耗的資源也不同，即導(dǎo)致成本費用的差異.因此制定生產(chǎn)方案則是要解決在限定的資源下選擇一套生產(chǎn)方案，使其滿足各項約束條件的情況下同時達到最小成本，增加產(chǎn)品利潤.例如：某廠決意生產(chǎn)兩種糖果:硬糖和軟糖,糖果僅由糖,堅果,和巧克力制成，三種材料的總量分別為100盎司，20盎司以及30盎司.軟糖須含有至少20%的堅果，糖須含有至少10%的堅果和10%的巧克力.并且已知1盎司軟糖和硬糖的售價分別為25、20美分，根據(jù)要

2、求安排生產(chǎn)計劃使得工廠的收入最大化.2 問題的分析線性規(guī)劃問題的數(shù)學(xué)模型包括三個組成要素：(1)決策變量：又稱為控制變量，是模型所代表的系統(tǒng)中受到控制或能夠控制的變量，表現(xiàn)為未知參數(shù)（變量），最后通過選定決策變量來實現(xiàn)最優(yōu)解；(2)約束條件：決策變量客觀上必須滿足的限制條件，反映出實際問題中不受控制的系統(tǒng)變量對受控制的決策變量的限制關(guān)系，包括等式約束和不等式約束 ；(3)目標(biāo)函數(shù)：模型所代表的性能指標(biāo)，在模型中表現(xiàn)為決策變量的函數(shù)，反映了實際問題所要達到的理想目標(biāo)，分為求最大值和最小值兩種形式.如果規(guī)劃問題的數(shù)學(xué)模型中，決策變量的取值是連續(xù)的，目標(biāo)函數(shù)是決策變量的線性函數(shù)，約束條件是含決策變量

3、的線性等式或不等式，則該類規(guī)劃問題的數(shù)學(xué)模型成為線性規(guī)劃的數(shù)學(xué)模型.實際問題中線性的含義:一是嚴(yán)格的比例性，如生產(chǎn)某產(chǎn)品對資源的消耗量和可獲取的利潤，同其生產(chǎn)數(shù)量嚴(yán)格成比例；二是可疊加行，如生產(chǎn)多種產(chǎn)品時，可獲取的總利潤是各項產(chǎn)品的利潤之和，對某項資源的消耗量應(yīng)等于各產(chǎn)品對該項資源的消耗量的和.很多實際問題往往不符合上述條件，為處理問題方便，可看做近似滿足線性條件.如安排生產(chǎn)計劃問題則是以收入為目標(biāo)函數(shù)，各種材料所占比例以及材料總數(shù)為約束條件，構(gòu)成線性規(guī)劃問題.線性規(guī)劃問題部分內(nèi)容框架如下：實際問題LP模型 基本概念線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的各種解的概念可行解基本解基本可行解最優(yōu)解基本最優(yōu)解

4、基本方法圖解法單純形法對偶單純形法進一步討論修正單純形法對偶理論靈敏度分析算法復(fù)雜度分析 線性規(guī)劃問題的數(shù)學(xué)模型的一般形式:（1）列出目標(biāo)函數(shù)及約束條件：max（或min）z=st（2）畫出約束條件所表示的可行域；（3）在可行域內(nèi)求目標(biāo)函數(shù)的最優(yōu)解.3 問題假設(shè)（1）制造糖果的三種原材料總量不會因為任何因素發(fā)生改變；（2）每種糖果對原料的需求可以嚴(yán)格控制；（3）糖果的生產(chǎn)過程是穩(wěn)定的，并且沒有技術(shù)問題；（4）生產(chǎn)過程中互不干擾；（5）在生產(chǎn)時不會存在材料浪費的情況，即生產(chǎn)機器上不會沾到原材料導(dǎo)致實際使用的原材料與加入材料量不符.4 符號說明設(shè)以i表示糖果的種類，以j表示制造糖果所需要的原材料，

5、xij表示每種糖果所需要的每種材料的含量，具體對應(yīng)關(guān)系如表： 單位：盎司 ji糖堅果巧克力硬糖x11x12x13軟糖x21x22x23z:生產(chǎn)硬糖和軟糖的總收入.5 模型的建立5.1 模型的準(zhǔn)備工作目標(biāo)函數(shù)：max（或min）約束條件：st 上述模型簡化形式為：目標(biāo)函數(shù)：max（或min）z=約束條件：st5.2 建立模型5.2.1 運用MATLAB軟件求解模型目標(biāo)函數(shù)系數(shù)矩陣：c=20,20,20,25,25,25即目標(biāo)函數(shù)為：max z=20*（x11+x12+x13）+25(x21+x22+x23)各決策變量在其相關(guān)的影響因素下所需滿足的約束條件： x11 +x21100x12+x222

6、0x13+x2330x11-9x12+x130x11+x12-9x130x21-4x22+x230xij0,i,j=1,2,35.2 .2 運用lingo軟件求解模型其具體過程如下流程圖：輸入lingo軟件按題要求求解最優(yōu)可行解寫出目標(biāo)函數(shù)、決策變量所滿足的約束條件依照題目要求，將各因素數(shù)字量化，決定目標(biāo)函數(shù)變量，決策變量 6 模型求解由問題分析可得：(1)生產(chǎn)的總收入與兩類糖果的生產(chǎn)總量有關(guān);(2)每類糖果的生產(chǎn)總量等于糖、堅果和巧克力三者的含量之和;(3)糖、堅果和巧克力三者的總含量有限，生產(chǎn)兩類糖果時所耗用的總材料數(shù)不能超過給定材料的總含量.6.1 MATLAB軟件求解結(jié)果z=3.250

7、0e+003x= 80.0000 10.0000 10.0000 20.0000 10.0000 20.0000對結(jié)果進行分析得： 單位：盎司 ji糖堅果巧克力硬糖801010軟糖201020合計1002030最大收入（美分）32506.2 Lingo軟件求解結(jié)果根據(jù)以上的目標(biāo)函數(shù)和約束條件，借助lingo軟件中的求解線性規(guī)劃程序，最終得到：Global optimal solution found. Objective value: 3250.000 Infeasibilities: 0. Total solver iterations: 5 Variable Value Reduced C

8、ost X11 80.00000 0. X12 10.00000 0. X13 10.00000 0. X21 20.00000 0. X22 10.00000 0. X23 20.00000 0.對結(jié)果進行分析得： 單位：盎司 ji糖堅果巧克力硬糖801010軟糖201020合計1002030最大收入（美分）32507 模型驗證及結(jié)果分析7.1 模型驗證7.1.1 MATLAB軟件求解結(jié)果驗證采用MATLAB軟件中的線性規(guī)劃模型得：x11=80x12=10x13=10x21=20x22=10x23=20max z=3250由以上結(jié)果可知：（1）硬糖的生產(chǎn)計劃為：80盎司糖、10盎司堅果和10

9、盎司巧克力；（2）軟糖的生產(chǎn)計劃為：20盎司糖、10盎司堅果和20盎司巧克力；（3）生產(chǎn)硬糖和軟糖產(chǎn)生的最大收入為3250美分.7.1.2 Lingo軟件求解結(jié)果驗證采用Lingo軟件中的線性規(guī)劃模型得：x11=80x12=10x13=10x21=20x22=10x23=20max z=3250由以上結(jié)果可知：（1）硬糖的生產(chǎn)計劃為：80盎司糖、10盎司堅果和10盎司巧克力；（2）軟糖的生產(chǎn)計劃為：20盎司糖、10盎司堅果和20盎司巧克力；（3）生產(chǎn)硬糖和軟糖產(chǎn)生的最大收入為3250美分.7.2 結(jié)果分析通過我們建立的Lingo模型，求解出了一個合理的生產(chǎn)計劃，下面我們將對Lingo求解的結(jié)果

10、進行詳細(xì)的分析如下：查看Lingo報告窗口（Reports Window）,可以看到如下結(jié)果Global optimal solution found. Objective value: 3250.000 Infeasibilities: 0. Total solver iterations: 5Variable Value Reduced CostX11 80.00000 0.X12 10.00000 0.X13 10.00000 0.X21 20.00000 0.X22 10.00000 0.X23 20.00000 0.Row Slack or Surplus Dual Price1 3

11、250.000 1.2 0. 15.000003 0. 65.000004 0. 15.000005 0. 5.6 0. 0.7 0. 10.00000 “Objective value:3250.000”表示最優(yōu)目標(biāo)值為3250.“Value”給出最優(yōu)解中各變量的值：最優(yōu)生產(chǎn)計劃是：生產(chǎn)硬糖需要80盎司的糖，10盎司的堅果和 10盎司的巧克力；生產(chǎn)軟糖需要20盎司的糖，10盎司的堅果和10盎司的巧克力.“Slack or Surplus”為給出的松馳變量的值：第1行松馳變量 =3250（模型第一行表示目標(biāo)函數(shù)，所以第二行對應(yīng)第一個約束）第2行松馳變量 =0第3行松馳變量 =0第4行松馳變量

12、=0第5行松馳變量 =0第6行松馳變量 =0第7行松馳變量 =0 “DUAL PRICE”（對偶價格）表示當(dāng)對應(yīng)約束有微小變動時, 目標(biāo)函數(shù)的變化率.輸出結(jié)果中對應(yīng)于每一個約束有一個對偶價格.若其數(shù)值為p， 表示對應(yīng)約束中不等式右端項若增加1 個單位，目標(biāo)函數(shù)將減少p個單位（min型問題）.顯然，如果在最優(yōu)解處約束正好取等號（也就是“緊約束”，也稱為有效約束或起作用約束），對偶價格值才可能不是0.本例中：除了第6行都是緊約束，對應(yīng)的對偶價格值分別為1、15、65、15、5、10.對于非緊約束（如本例中第6行是非緊約束），DUAL PRICE 的值為0, 表示對應(yīng)約束中不等式右端項的微小擾動不影

13、響目標(biāo)函數(shù).有時, 通過分析DUAL PRICE, 也可對產(chǎn)生不可行問題的原因有所了解.用MATLAB軟件求解可知：c=-20,-20,-20,-25,-25,-25;A=1,0,0,1,0,0;0,1,0,0,1,0;0,0,1,0,0,1;1,-9,1,0,0,0;1,1,-9,0,0,0;0,0,0,1,-4,1;b=100,20,30,0,0,0;其中c表示目標(biāo)函數(shù)的系數(shù)，A表示約束條件的系數(shù)矩陣，b表示約束條件滿足的值.我們發(fā)現(xiàn)通過MATLAB軟件編程得到的結(jié)果與Lingo軟件編程得到的結(jié)果相同,即生產(chǎn)計劃為：生產(chǎn)硬糖需要80盎司的糖，10盎司的堅果和 10盎司的巧克力；生產(chǎn)軟糖需要

14、20盎司的糖，10盎司的堅果和10盎司的巧克力.并且兩種方法求解得到的最大收入都是3250美分，因此該計劃是最優(yōu)的生產(chǎn)計劃.參 考 文 獻1 何堅勇編著最優(yōu)化方法 M北京：清華大學(xué)出版社，2007：1-27.2 朱德通編著. 最優(yōu)化模型與實驗 M上海：同濟大學(xué)出版社，2003：1-39.3 徐渝、賈濤編著. 運籌學(xué)（上冊）M北京：清華大學(xué)出版社，2005：1-8.4 Hamdy A. Taha著.運籌學(xué)導(dǎo)論（英文版第8版）M北京：人民郵電出版社，2007：1-80.5 劉衛(wèi)國編.MATLAB程序設(shè)計教程M北京：中國水利水電出版社，2001：1-180.6 謝金星，薛毅編注優(yōu)化建模與LINGO軟件M北京：清華大學(xué)出版社，2005：1-280.附 錄1、MATLAB軟件的源程序clear;c=-20,-20,-20,-25,-25,-25;A=1,0,0,1,0,0;0,1,0,0,1,0;0,0,1,0,0,1;1,-9,1,0,0,0;1,1,-9,0,0,0;0,0,0