線性規(guī)劃模型

1、第5章 線性規(guī)劃模型 4.1 線性規(guī)劃問題及其數(shù)學(xué)模型4.2 線性規(guī)劃的求解方法 4.3 對偶規(guī)劃及靈敏度分析4.4 應(yīng)用舉例-奶制品的生產(chǎn)與銷售例1 生產(chǎn)計劃問題美佳公司計劃制造和兩種家電產(chǎn)品。已知各制造一件時分別占用的設(shè)備A，B的臺數(shù)、調(diào)試時間、調(diào)試工序、每天可用于這兩種家電的能力、各售出一件時的獲利情況，如表5.1所示。問該公司應(yīng)制造兩種家電各多少件，才能獲取的利潤最大？每天可用能力設(shè)備A/h0515設(shè)備B/h6224調(diào)試工序/h115利潤/元211個公司 或獲利4元/個獲利1元/個x1制造家電數(shù)量x2制造家電數(shù)量獲利 2x1 獲利 x2 加工能力決策變量 目標(biāo)函數(shù) 每天獲利約束條件非負(fù)

2、約束 線性規(guī)劃模型(LP)基本模型例2 運輸問題工廠例3 營養(yǎng)問題 某飼養(yǎng)場飼養(yǎng)供實驗用的動物。已知動物生長對飼料中的三種營養(yǎng)成份：蛋白質(zhì)、礦物質(zhì)和維生素特別敏感。每個動物每天至少需要蛋白質(zhì)70g，礦物質(zhì)3g，維生素10mg。該飼養(yǎng)場現(xiàn)有五種飼料，每種飼料10kg的成本如下：飼料A1A2A3A4A5成本27435單位:元每一千克飼料中所含的營養(yǎng)成分表飼 料蛋白質(zhì)/g礦物質(zhì)/g維生素/mgA10.300.100.05A22.000.050.10A31.000.020.02A40.600.200.20A51.800.050.08 我們希望確定既能滿足動物需求，又使總成本為最低的飼料配方建立相應(yīng)的數(shù)

3、學(xué)模型。解: 設(shè)動物每天食用的混合飼料中所含的第j種飼料Aj 的數(shù)量為xj(kg), 混合飼料的總成本為y, 則上述問題的數(shù)學(xué)模型為一般的營養(yǎng)問題可敘述如下：所以線性規(guī)劃問題的數(shù)學(xué)模型的一般形式為它的變量滿足不難看出，上面這些問題雖然各式各樣，但它們的數(shù)學(xué)模型卻有相同的數(shù)學(xué)形式，即求一個線性函數(shù)的最大值(或最小值)，而這個線性函數(shù)的變量是非負(fù)的，滿足一組線性等式或不等式。 我們把具有這種模型的問題稱為線性規(guī)劃問題。5.1.2 線性規(guī)劃模型 線性規(guī)劃問題的數(shù)學(xué)模型有許多種，目標(biāo)函數(shù)有求最小值的，有求最大值的；約束條件有的是“”形式的，也有“”或“”形式的。我們希望能把各種不同形式的線性規(guī)劃問題的

4、數(shù)學(xué)模型化為一種統(tǒng)一的標(biāo)準(zhǔn)形式，這樣只要對標(biāo)準(zhǔn)形式找出一種解法，就可以解決其余不同形式的線性規(guī)劃問題了。 線性規(guī)劃問題的數(shù)學(xué)模型的一般形式 規(guī)定下列形式的線性規(guī)劃問題為標(biāo)準(zhǔn)形式：其中 均為常數(shù)，且 線性規(guī)劃問題標(biāo)準(zhǔn)形式的矩陣表示：其中 求解方法軟件實現(xiàn)法X=lp(c,A,b)對偶規(guī)劃及靈敏度分析9/24/202215例1 美佳公司利用該公司資源生產(chǎn)兩種家電產(chǎn)品的線性規(guī)劃模型為：設(shè)y1，y2，y3分別表示設(shè)備A、B和調(diào)試工序單位時間的價格。則0y1+6y2+y325y1+2y2+y31對生產(chǎn)產(chǎn)品的全部資源的定價。假如另一公司想收購美佳公司的資源，美佳公司出讓自己資源的條件是什么？出讓代價不低于用

5、同等資源組織生產(chǎn)兩種產(chǎn)品所能獲得的利潤。對生產(chǎn)產(chǎn)品的全部資源的定價。產(chǎn)品的利潤產(chǎn)品的利潤9/24/202216原問題與對偶問題的數(shù)據(jù)比較 原問題對偶問題x1x2原關(guān)系min wy10515y26224y3115對偶關(guān)系max z = min wmax z219/24/202217二、對稱形式對偶問題的一般形式定義：滿足下列條件的線性規(guī)劃問題稱為具有對稱形式：其變量均具有非負(fù)約束，其約束條件當(dāng)目標(biāo)函數(shù)求極大時取“”號，當(dāng)目標(biāo)函數(shù)求極小時均取“”號。則其對偶問題的一般形式為：若原問題的一般形式為：yi(i=1,2,，m)代表第i種資源的估價。9/24/202218矩陣形式表示的原問題與對偶問題原問

6、題：對偶問題：令ww對偶問題令zz對偶問題的對偶是原問題9/24/202219四、對偶問題的寫法在寫對偶問題時，要特別注意上表中原問題與其對偶問題的對應(yīng)關(guān)系。9/24/2022202-3 影子價格當(dāng)線性規(guī)劃原問題求得最優(yōu)解xj*( j =1,2,n )時，其對偶問題也得到最優(yōu)解yi*( i =1,2,m )，且兩者的目標(biāo)函數(shù)值相等。即bi：線性規(guī)劃原問題右端項，代表第 i 種資源的擁有量；yi*：對偶變量，代表在最優(yōu)資源利用條件下對單位第 i 種資源的估價，稱為影子價格。影子價格也稱為機(jī)會成本，它是根據(jù)具體的經(jīng)濟(jì)目標(biāo)、技術(shù)水平和資源條件作出的對資源利用的評價市場價格：是資源在市場上流通的實際價

7、格，它由整個社會的經(jīng)濟(jì)技術(shù)狀況決定。返回本章目錄9/24/202221根據(jù) 求 bi 的偏導(dǎo)數(shù)得：這說明，原問題某一約束條件的右邊常數(shù)bi增加一個單位時，則由此引起最優(yōu)目標(biāo)函數(shù)值的增加量，就等于與該約束相對應(yīng)的對偶變量的最優(yōu)值。這樣一來，在有限資源條件下使收益最大化這一類問題中，就可以把對偶變量的最優(yōu)值，看成是相應(yīng)資源每一單位對于目標(biāo)函數(shù)的貢獻(xiàn)，即這些資源被充分利用時所能帶來的收益。從而， yi* 的值就相當(dāng)于對單位 i 種資源在實現(xiàn)最大利潤時的一種價格估計。這種估計是針對具體企業(yè)，具體產(chǎn)品而存在的一種特殊價格，稱之為影子價格，它與市場價格不同。若僅從經(jīng)濟(jì)上考慮，當(dāng)某種資源的市場價格低于影子價

8、格時，企業(yè)就可以考慮買進(jìn)這種資源；當(dāng)市場價格高于影子價格時，企業(yè)則可以出售這種資源。隨著資源的買進(jìn)賣出，它的影子價格也將隨之變化，直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。9/24/202222影子價格的應(yīng)用（1）用影子價格判別資源的供求關(guān)系如果線性規(guī)劃的原問題在得到最優(yōu)解時，某個約束條件為嚴(yán)格的不等式，即最優(yōu)解中該約束的松弛變量的值大于零，即表明該種資源有剩余，供大于求。增加這種資源時，目標(biāo)函數(shù)值不會有任何改善。如果線性規(guī)劃的原問題在得到最優(yōu)解時，某個約束條件為嚴(yán)格的等式，即最優(yōu)解中該約束的松弛變量的值等于零，即表明該資源恰恰用完。這種資源增加一個單位，目標(biāo)函數(shù)值就改進(jìn)一個影子價

9、格。由此可見，影子價格大于零，說明資源緊缺；影子價格等于零，說明資源有剩余。影子價格愈大，說明該資源愈緊缺，該種資源每增加一個單位所相應(yīng)增加的目標(biāo)函數(shù)值愈大。9/24/202223（2）應(yīng)用影子價格來合理分配資源算出各種資源的影子價格后，可參考影子價格高低順序合理分配資源，高者優(yōu)先投資。同時，也可以參考資源的影子價格，合理地確定各種資源的價格。企業(yè)生產(chǎn)計劃5.4 奶制品的生產(chǎn)與銷售 空間層次工廠級：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等條件，以最大利潤為目標(biāo)制訂產(chǎn)品生產(chǎn)計劃；車間級：根據(jù)生產(chǎn)計劃、工藝流程、資源約束及費用參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計劃.時間層次若短時間內(nèi)外部需求和內(nèi)部資

10、源等不隨時間變化，可制訂單階段生產(chǎn)計劃，否則應(yīng)制訂多階段生產(chǎn)計劃.本節(jié)課題例1 加工奶制品的生產(chǎn)計劃1桶牛奶 3kgA1 12h 8h 4kgA2 或獲利24元/kg 獲利16元/kg 50桶牛奶 時間480h 至多加工100kgA1 制訂生產(chǎn)計劃，使每天獲利最大 35元可買到1桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到 30元/kg，應(yīng)否改變生產(chǎn)計劃？ 每天：問題1桶牛奶 3kgA1 12h 8h 4kgA2 或獲利24元/kg 獲利16元/kg x1桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)A2 獲利 243x1 獲利 164 x2 原料供應(yīng)

11、勞動時間 加工能力 決策變量 目標(biāo)函數(shù) 每天獲利約束條件非負(fù)約束 線性規(guī)劃模型(LP)時間480h 至多加工100kgA1 50桶牛奶 每天基本模型模型分析與假設(shè) 比例性 可加性 連續(xù)性 xi對目標(biāo)函數(shù)的“貢獻(xiàn)”與xi取值成正比 xi對約束條件的“貢獻(xiàn)”與xi取值成正比 xi對目標(biāo)函數(shù)的“貢獻(xiàn)”與xj取值無關(guān) xi對約束條件的“貢獻(xiàn)”與xj取值無關(guān) xi取值連續(xù) A1,A2每千克的獲利是與各自產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工A1,A2的數(shù)量, 時間是與各自產(chǎn)量無關(guān)的常數(shù)A1,A2每千克的獲利是與相互產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工A1,A2的數(shù)量,時間是與相互產(chǎn)量無關(guān)的常數(shù)加工A1,A2的牛奶桶數(shù)是實數(shù)

12、線性規(guī)劃模型模型求解 軟件實現(xiàn) LINGO model:max = 72*x1+64*x2;milk x1 + x250;time 12*x1+8*x2480;cpct 3*x1100;end Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.0000

13、00 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000 20桶牛奶生產(chǎn)A1, 30桶生產(chǎn)A2，利潤3360元. 結(jié)果解釋 Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.00

14、0 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000 model:max = 72*x1+64*x2;milk x1 + x250;time 12*x1+8*x2480;cpct 3*x1100;end三種資源“資源” 剩余為零的約束為緊約束（有效約束） 原料無剩余時間無剩余加工能力剩余40結(jié)果解釋 Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Val

15、ue Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000最優(yōu)解下“資源”增加1單位時“效益”的增量 影子價格 35元可買到1桶牛奶，要買嗎?35 48, 應(yīng)該買！ 聘用臨時工人付出的工資最多每小時幾元? 2元！原料增加1單位, 利潤增長48 時間增加1單位, 利潤增長2 加工能力增長不影響利潤Ran

16、ges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable AllowableVariable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease MILK 50.00000 10.00000 6.666667

17、TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000 最優(yōu)解不變時目標(biāo)函數(shù)系數(shù)允許變化范圍 敏感性分析 (“LINGO|Ranges” ) x1系數(shù)范圍(64,96) x2系數(shù)范圍(48,72) A1獲利增加到 30元/kg，應(yīng)否改變生產(chǎn)計劃? x1系數(shù)由24 3=72增加為303=90，在允許范圍內(nèi) 不變！(約束條件不變)結(jié)果解釋 Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowabl

18、eVariable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease MILK 50.00000 10.00000 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000影子價格有意義時約束右端的允許變化范圍 原料最多增加10

19、時間最多增加53 35元可買到1桶牛奶, 每天最多買多少?最多買10桶!(目標(biāo)函數(shù)不變)充分條件 !例2 奶制品的生產(chǎn)銷售計劃 在例1基礎(chǔ)上深加工1桶牛奶 3kgA1 12h 8h 4kgA2 或獲利24元/kg 獲利16元/kg 0.8kgB1 2h, 3元1kg獲利44元/kg 0.75kgB2 2h, 3元1kg獲利32元/kg 制訂生產(chǎn)計劃，使每天凈利潤最大 30元可增加1桶牛奶，3元可增加1h時間，應(yīng)否投資？現(xiàn)投資150元，可賺回多少？50桶牛奶, 480h 至多100kgA1 B1，B2的獲利經(jīng)常有10%的波動，對計劃有無影響？ 每天銷售10kgA1的合同必須滿足，對利潤有什么影響

20、？1桶牛奶 3kg A1 12h 8h 4kg A2 或獲利24元/kg 獲利16元/kg 0.8kg B12h, 3元1kg獲利44元/kg 0.75kg B22h, 3元1kg獲利32元/kg 出售x1 kg A1, x2 kg A2， x3 kg B1, x4 kg B2原料供應(yīng) 勞動時間 加工能力 決策變量 目標(biāo)函數(shù) 利潤約束條件非負(fù)約束 x5 kg A1加工B1， x6 kg A2加工B2附加約束 基本模型模型求解 軟件實現(xiàn) LINGO Global optimal solution found. Objective value: 3460.800 Total solver iter

21、ations: 2 Variable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.0

22、0000 6 0.000000 32.00000Global optimal solution found. Objective value: 3460.800 Total solver iterations: 2 Variable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460

23、.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000結(jié)果解釋每天銷售168 kgA2和19.2 kgB1， 利潤3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，將得到的24kgA1全部加工成B1 除加工能力外均為緊約束結(jié)果解釋Global optimal solution found. Objective value: 3460.800 Total solver iterations: 2 V

24、ariable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.00

25、0000 32.00000增加1桶牛奶使利潤增長3.1612=37.92增加1h時間使利潤增長3.26 30元可增加1桶牛奶，3元可增加1h時間，應(yīng)否投資？現(xiàn)投資150元，可賺回多少？投資150元增加5桶牛奶,可賺回189.6元(大于增加時間的利潤增長).結(jié)果解釋B1,B2的獲利有10%的波動，對計劃有無影響 Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 24.00

26、0000 1.680000 INFINITY X2 16.000000 8.150000 2.100000 X3 44.000000 19.750002 3.166667 X4 32.000000 2.026667 INFINITY X5 -3.000000 15.800000 2.533334 X6 -3.000000 1.520000 INFINITY 敏感性分析 B1獲利下降10%，超出X3 系數(shù)允許范圍B2獲利上升10%，超出X4 系數(shù)允許范圍波動對計劃有影響生產(chǎn)計劃應(yīng)重新制訂：如將x3的系數(shù)改為39.6計算，會發(fā)現(xiàn)結(jié)果有很大變化. Global optimal solution fo

27、und. Objective value: 3460.800 Total solver iterations: 2 Variable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000

28、 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000結(jié)果解釋x1從0開始增加一個單位時，最優(yōu)目標(biāo)函數(shù)值將減少1.68Reduced Cost有意義也是有條件的(LINGO沒有給出)每天銷售10kgA1的合同必須滿足，對利潤有什么影響？公司利潤減少1.6810=16.8（元）最優(yōu)利潤為 3460.8 16.8 = 3444 問題1. 如何下料最節(jié)省 ? 例1 鋼管下料 問題2. 客戶增加需求：原料鋼管:每根19m 50根4m20根6m15根8m客戶需求節(jié)省的標(biāo)準(zhǔn)是什么？由于采用不同切割模式太多, 會增加生

29、產(chǎn)和管理成本,規(guī)定切割模式不能超過3種. 如何下料最節(jié)省？10根5m按照客戶需要在一根原料鋼管上安排切割的一種組合,如: 切割模式余料1m 4m 6m 8m 余料3m 4m 6m 6m 合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸.余料3m 8m 8m 鋼管下料 為滿足客戶需要，按照哪些種合理模式切割，每種模式切割多少根原料鋼管，最為節(jié)??？合理切割模式2. 所用原料鋼管總根數(shù)最少 .模式4m鋼管根數(shù)6m鋼管根數(shù)8m鋼管根數(shù)余料(m)14003231013201341203511116030170023鋼管下料問題1 節(jié)省的兩種標(biāo)準(zhǔn)1. 原料鋼管剩余總余量最小 .xi 按第i 種模式切割的原料

30、鋼管根數(shù)(i=1,7) 約束滿足需求 決策變量 目標(biāo)1（總余量）按模式2切割12根,按模式5切割15根,共27根,余料27m. 模式4m根數(shù)6m根數(shù)8m根數(shù)余料14003m23101m32013m41203m51111m60301m70023m需求502015最優(yōu)解：x2=12, x5=15, 其余為0；最優(yōu)值：27.整數(shù)約束： xi 為整數(shù)目標(biāo)2（總根數(shù)）鋼管下料問題1 約束條件不變 最優(yōu)解：x2=15, x5=5, x7=5, 其余為0；最優(yōu)值：25.xi 為整數(shù)按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35m .目標(biāo)2切割減少了2根, 但余料增加8m, 為什么?與目標(biāo)1的結(jié)果“