第4數(shù)學(xué)規(guī)劃模型

1、第第4 4章章 數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型 4.2 1奶制品生產(chǎn)奶制品生產(chǎn) 2 2自自來(lái)水輸送來(lái)水輸送練習(xí)題練習(xí)題 汽車(chē)生產(chǎn)與原油采購(gòu)汽車(chē)生產(chǎn)與原油采購(gòu)y數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型 實(shí)際問(wèn)題中實(shí)際問(wèn)題中的優(yōu)化模型的優(yōu)化模型mixgtsxxxxfzmaxminitn, 2 , 1, 0)(. .),(),()(1或x決策變量決策變量f(x)目標(biāo)函數(shù)目標(biāo)函數(shù)gi(x) 0約束條件約束條件多元函數(shù)多元函數(shù)條件極值條件極值 決策變量個(gè)數(shù)決策變量個(gè)數(shù)n和和約束條件個(gè)數(shù)約束條件個(gè)數(shù)m較大較大 最優(yōu)解在可行域最優(yōu)解在可行域的邊界上取得的邊界上取得 數(shù)數(shù)學(xué)學(xué)規(guī)規(guī)劃劃線(xiàn)性規(guī)劃線(xiàn)性規(guī)劃非線(xiàn)性規(guī)劃非線(xiàn)性規(guī)劃整數(shù)規(guī)劃整數(shù)

2、規(guī)劃重點(diǎn)在模型的建立和結(jié)果的分析重點(diǎn)在模型的建立和結(jié)果的分析 一奶制品加工廠(chǎng)用牛奶生產(chǎn)，兩種奶制品，1桶牛奶可以在設(shè)備甲上用12小時(shí)加工成3公斤a1，或者在設(shè)備乙上用8小時(shí)加工成4公斤a2。假設(shè)生產(chǎn)的a1 、a2，全部能售出，且每公斤a1獲利24元，每公斤a2獲利16元?，F(xiàn)在加工廠(chǎng)每天能得到50桶牛奶的供應(yīng)，每天正式工人總的勞動(dòng)時(shí)間為480小時(shí)，并且設(shè)備甲每天至多加工100公斤，設(shè)備乙的加工能力沒(méi)有限制。試為該廠(chǎng)制訂一個(gè)生產(chǎn)計(jì)劃，使每天獲利最大。 奶制品的生產(chǎn)計(jì)劃奶制品的生產(chǎn)計(jì)劃 進(jìn)一步討論以下3個(gè)附加問(wèn)題： 1）若用35元可以買(mǎi)到1桶牛奶，應(yīng)否作這項(xiàng)投資？若投資，每天最多購(gòu)買(mǎi)多少桶牛奶？ 2

3、）若可以聘用臨時(shí)工人以增加勞動(dòng)時(shí)間，付給臨時(shí)工人的工資最多是每小時(shí)幾元？ 3）由于市場(chǎng)需求變化，每公斤的獲利增加到30元，應(yīng)否改變生產(chǎn)計(jì)劃？企業(yè)生產(chǎn)計(jì)劃企業(yè)生產(chǎn)計(jì)劃空間層次空間層次工廠(chǎng)級(jí)：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等工廠(chǎng)級(jí)：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等條件，以最大利潤(rùn)為目標(biāo)制訂產(chǎn)品生產(chǎn)計(jì)劃；條件，以最大利潤(rùn)為目標(biāo)制訂產(chǎn)品生產(chǎn)計(jì)劃；車(chē)間級(jí)：根據(jù)生產(chǎn)計(jì)劃、工藝流程、資源約束及費(fèi)車(chē)間級(jí)：根據(jù)生產(chǎn)計(jì)劃、工藝流程、資源約束及費(fèi)用參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計(jì)劃。用參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計(jì)劃。時(shí)間層次時(shí)間層次若短時(shí)間內(nèi)外部需求和內(nèi)部資源等不隨時(shí)間變化，可若短時(shí)間內(nèi)外部

4、需求和內(nèi)部資源等不隨時(shí)間變化，可制訂制訂單階段生產(chǎn)計(jì)劃單階段生產(chǎn)計(jì)劃，否則應(yīng)制訂多階段生產(chǎn)計(jì)劃。，否則應(yīng)制訂多階段生產(chǎn)計(jì)劃。本節(jié)課題本節(jié)課題模型分析模型分析 背景分析1桶牛奶 3公斤a1 12小時(shí) 8小時(shí) 4公斤a2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶 時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤a1 制訂生產(chǎn)計(jì)劃，使每天獲利最大制訂生產(chǎn)計(jì)劃，使每天獲利最大 35元可買(mǎi)到元可買(mǎi)到1桶牛奶，買(mǎi)嗎？若買(mǎi)，每天最多買(mǎi)多少桶牛奶，買(mǎi)嗎？若買(mǎi)，每天最多買(mǎi)多少? 可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? a1的獲利增加到的獲利增加

5、到 30元元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？公斤，應(yīng)否改變生產(chǎn)計(jì)劃？ 每天：每天：模型分析模型分析 問(wèn)題分析模型分析與假設(shè)模型分析與假設(shè) 比比例例性性 可可加加性性 連續(xù)性連續(xù)性 xi對(duì)目標(biāo)函數(shù)的對(duì)目標(biāo)函數(shù)的“貢貢獻(xiàn)獻(xiàn)”與與xi取值成正比取值成正比 xi對(duì)約束條件的對(duì)約束條件的“貢貢獻(xiàn)獻(xiàn)”與與xi取值成正比取值成正比 x1對(duì)目標(biāo)函數(shù)的對(duì)目標(biāo)函數(shù)的“貢貢獻(xiàn)獻(xiàn)”與與x2取值無(wú)關(guān)取值無(wú)關(guān) x1對(duì)約束條件的對(duì)約束條件的“貢獻(xiàn)貢獻(xiàn)”與與x2取值取值無(wú)關(guān)無(wú)關(guān) x1 x2取值連續(xù)取值連續(xù) a1,a2每公斤的獲利是與各每公斤的獲利是與各自產(chǎn)量無(wú)關(guān)的常數(shù)自產(chǎn)量無(wú)關(guān)的常數(shù)每桶牛奶加工出每桶牛奶加工出a1,a2的數(shù)量和的

6、數(shù)量和時(shí)間是與各自產(chǎn)量無(wú)關(guān)的常數(shù)時(shí)間是與各自產(chǎn)量無(wú)關(guān)的常數(shù)a1,a2每公斤的獲利是與相每公斤的獲利是與相互產(chǎn)量無(wú)關(guān)的常數(shù)互產(chǎn)量無(wú)關(guān)的常數(shù)每桶牛奶加工出每桶牛奶加工出a1,a2的數(shù)量和的數(shù)量和時(shí)間是與相互產(chǎn)量無(wú)關(guān)的常數(shù)時(shí)間是與相互產(chǎn)量無(wú)關(guān)的常數(shù)加工加工a1,a2的牛奶桶數(shù)是實(shí)數(shù)的牛奶桶數(shù)是實(shí)數(shù) 線(xiàn)性規(guī)劃模型線(xiàn)性規(guī)劃模型假設(shè)加工假設(shè)加工a a1 1,a,a2 2的牛奶桶數(shù)分別是的牛奶桶數(shù)分別是x1 , x21桶牛奶 3公斤a1 12小時(shí) 8小時(shí) 4公斤a2 或獲利24元/公斤 獲利16元/公斤 x1桶牛奶生產(chǎn)桶牛奶生產(chǎn)a1 x2桶牛奶生產(chǎn)桶牛奶生產(chǎn)a2 獲利獲利 243x1 獲利獲利 164 x2

7、 原料供應(yīng)原料供應(yīng) 5021 xx勞動(dòng)時(shí)間勞動(dòng)時(shí)間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 216472xxzmax每天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線(xiàn)性線(xiàn)性規(guī)劃規(guī)劃模型模型(lp)時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤a1 50桶牛奶桶牛奶 每天每天模型求解模型求解 圖解法圖解法 x1x20abcdl1l2l3l4l55021 xx48081221 xx10031x0,21xx約約束束條條件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xx

8、zmax目標(biāo)目標(biāo)函數(shù)函數(shù) z=0z=2400z=3600z=c (常數(shù)常數(shù)) 等值線(xiàn)等值線(xiàn)c在在b(20,30)點(diǎn)得到最優(yōu)解點(diǎn)得到最優(yōu)解目標(biāo)函數(shù)和約束條件是線(xiàn)性函數(shù)目標(biāo)函數(shù)和約束條件是線(xiàn)性函數(shù) 可行域?yàn)橹本€(xiàn)段圍成的凸多邊形可行域?yàn)橹本€(xiàn)段圍成的凸多邊形 目標(biāo)函數(shù)的等值線(xiàn)為直線(xiàn)目標(biāo)函數(shù)的等值線(xiàn)為直線(xiàn) 最優(yōu)解一定在凸多邊最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得。形的某個(gè)頂點(diǎn)取得。 模型求解模型求解 軟件實(shí)現(xiàn)軟件實(shí)現(xiàn) lingo max=72max=72* *x1+64x1+64* *x2;x2; x1 + x2 = 50; x1 + x2 = 50; 12 12* *x1+8x1+8* *x2=480;x

9、2=480; 3 3 * *x1= 100;x1= 100;endend objective function value 1) 3360.000 variable value reduced cost x1 20.000000 0.000000 x2 30.000000 0.000000 row slack or surplus dual prices 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 no. iterations= 2do range (sensitivity) analysis? no20桶牛

10、奶生產(chǎn)桶牛奶生產(chǎn)a1, 30桶生產(chǎn)桶生產(chǎn)a2，利潤(rùn)，利潤(rùn)3360元。元。 結(jié)果解釋結(jié)果解釋 objective function value 1) 3360.000 variable value reduced cost x1 20.000000 0.000000 x2 30.000000 0.000000 row slack or surplus dual prices 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 no. iterations= 2原料無(wú)剩余原料無(wú)剩余時(shí)間無(wú)剩余時(shí)間無(wú)剩余加工能力剩余加工能力

11、剩余40三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） max=72max=72* *x1+64x1+64* *x2;x2; x1 + x2 = 50; x1 + x2 = 50; 12 12* *x1+8x1+8* *x2=480;x2=480; 3 3 * *x1= 100;x1= 100;endend結(jié)果解釋結(jié)果解釋 objective function value 1) 3360.000 variable value reduced cost x1 20.000000 0.000000 x2 30.000000 0.000000 ro

12、w slack or surplus dual prices 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 no. iterations= 2最優(yōu)解下最優(yōu)解下“資源資源”增加增加1單位時(shí)單位時(shí)“效益效益”的增的增量量 原料增加原料增加1單位單位, 利潤(rùn)增長(zhǎng)利潤(rùn)增長(zhǎng)48 時(shí)間增加時(shí)間增加1單位單位, 利潤(rùn)增長(zhǎng)利潤(rùn)增長(zhǎng)2 加工能力增長(zhǎng)不影響利潤(rùn)加工能力增長(zhǎng)不影響利潤(rùn)影子價(jià)格影子價(jià)格 35元可再買(mǎi)到元可再買(mǎi)到1桶牛奶，要買(mǎi)嗎？桶牛奶，要買(mǎi)嗎？35 48, 應(yīng)該買(mǎi)！應(yīng)該買(mǎi)！ 聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？聘用臨

13、時(shí)工人付出的工資最多每小時(shí)幾元？ 2元！元！ranges in which the basis is unchanged: obj coefficient ranges variable current allowable allowable coef increase decrease x1 72.000000 24.000000 8.000000 x2 64.000000 8.000000 16.000000 righthand side ranges row current allowable allowable rhs increase decrease 2 50.000000 10.

14、000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 infinity 40.000000最優(yōu)解不變時(shí)目標(biāo)函最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍數(shù)系數(shù)允許變化范圍 do range(sensitivity) analysis? yesx1系數(shù)范圍系數(shù)范圍(64,96) x2系數(shù)范圍系數(shù)范圍(48,72) a1獲利增加到獲利增加到 30元元/千克，應(yīng)否改變生產(chǎn)計(jì)劃千克，應(yīng)否改變生產(chǎn)計(jì)劃 x1系數(shù)由系數(shù)由24 3=72增加增加為為30 3=90，在在允許范圍內(nèi)允許范圍內(nèi) 不變！不變！(約束條件不變約束條件不變)結(jié)果解釋結(jié)果解釋

15、ranges in which the basis is unchanged: obj coefficient ranges variable current allowable allowable coef increase decrease x1 72.000000 24.000000 8.000000 x2 64.000000 8.000000 16.000000 righthand side ranges row current allowable allowable rhs increase decrease 2 50.000000 10.000000 6.666667 3 480.

16、000000 53.333332 80.000000 4 100.000000 infinity 40.000000影子價(jià)格有意義時(shí)約束右端的允許變化范圍影子價(jià)格有意義時(shí)約束右端的允許變化范圍 原料最多增加原料最多增加10 時(shí)間最多增加時(shí)間最多增加53 35元可買(mǎi)到元可買(mǎi)到1桶牛奶，每天最多買(mǎi)多少？桶牛奶，每天最多買(mǎi)多少？最多買(mǎi)最多買(mǎi)10桶桶!(目標(biāo)函數(shù)不變目標(biāo)函數(shù)不變) 自來(lái)水輸送自來(lái)水輸送生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤(rùn)最大；怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤(rùn)最大；運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題各種類(lèi)型的貨物裝箱，

17、由于受體積、重量等限制，各種類(lèi)型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少。如何搭配裝載，使獲利最高，或裝箱數(shù)量最少。其他費(fèi)用其他費(fèi)用: :450元元/千噸千噸 應(yīng)如何分配水庫(kù)供水量，公司才能獲利最多？應(yīng)如何分配水庫(kù)供水量，公司才能獲利最多？ 若水庫(kù)供水量都提高一倍，公司利潤(rùn)可增加到多少？若水庫(kù)供水量都提高一倍，公司利潤(rùn)可增加到多少？ 元元/千噸千噸甲甲乙乙丙丙丁丁a160130220170b140130190150c190200230/引水管理費(fèi)引水管理費(fèi)例例2 自來(lái)水輸送自來(lái)水輸送收入：收入：900元元/千噸千噸 支出支出a：50b：60c：50甲：甲：3

18、0；50乙：乙：70；70丙：丙：10；20?。憾。?0；40水庫(kù)供水量水庫(kù)供水量(千噸千噸)小區(qū)基本用水量小區(qū)基本用水量(千噸千噸)小區(qū)額外用水量小區(qū)額外用水量(千噸千噸)（以天計(jì)）（以天計(jì)）總供水量：總供水量：160確定送水方案確定送水方案使利潤(rùn)最大使利潤(rùn)最大問(wèn)題問(wèn)題分析分析a：50b：60c：50甲：甲：30；50乙：乙：70；70丙：丙：10；20?。憾。?0；40 總需求量總需求量(300)每個(gè)水庫(kù)最大供水量都提高一倍每個(gè)水庫(kù)最大供水量都提高一倍利潤(rùn)利潤(rùn) = 收入收入(900) 其它費(fèi)用其它費(fèi)用( (450) 引水管理費(fèi)引水管理費(fèi)利潤(rùn)利潤(rùn)(元元/千噸千噸)甲甲乙乙丙丙丁丁a29032

19、0230280b310320260300c260250220/3332312423222114131211220250260300260320310280230320290 xxxxxxxxxxxzmax供應(yīng)供應(yīng)限制限制b, c 類(lèi)似處理類(lèi)似處理50:a14131211xxxx10014131211xxxx問(wèn)題討論問(wèn)題討論 確定送水方案確定送水方案使利潤(rùn)最大使利潤(rùn)最大需求約束可以不變需求約束可以不變求解求解 objective function value 1) 88700.00 variable value reduced cost x11 0.000000 20.000000 x12 10

20、0.000000 0.000000 x13 0.000000 40.000000 x14 0.000000 20.000000 x21 30.000000 0.000000 x22 40.000000 0.000000 x23 0.000000 10.000000 x24 50.000000 0.000000 x31 50.000000 0.000000 x32 0.000000 20.000000 x33 30.000000 0.000000 這類(lèi)問(wèn)題一般稱(chēng)為這類(lèi)問(wèn)題一般稱(chēng)為“運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題”(transportation problem)總利潤(rùn)總利潤(rùn) 88700（元）（元） a(100)

21、b(120)c(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030 如果生產(chǎn)某一類(lèi)型汽車(chē)，則至少要生產(chǎn)如果生產(chǎn)某一類(lèi)型汽車(chē)，則至少要生產(chǎn)8080輛，輛， 那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？練習(xí)練習(xí)1 汽車(chē)廠(chǎng)生產(chǎn)計(jì)劃汽車(chē)廠(chǎng)生產(chǎn)計(jì)劃 汽車(chē)廠(chǎng)生產(chǎn)三種類(lèi)型的汽車(chē)，已知各類(lèi)型每輛車(chē)對(duì)鋼汽車(chē)廠(chǎng)生產(chǎn)三種類(lèi)型的汽車(chē)，已知各類(lèi)型每輛車(chē)對(duì)鋼材、勞動(dòng)時(shí)間的需求，利潤(rùn)及工廠(chǎng)每月的現(xiàn)有量。材、勞動(dòng)時(shí)間的需求，利潤(rùn)及工廠(chǎng)每月的現(xiàn)有量。 小型小型 中型中型 大型大型 現(xiàn)有量現(xiàn)有量鋼材（噸）鋼材（噸） 1.5 3 5 600勞動(dòng)時(shí)間（小時(shí)）勞動(dòng)

22、時(shí)間（小時(shí)） 280 250 400 60000利潤(rùn)（萬(wàn)元）利潤(rùn)（萬(wàn)元） 2 3 4 制訂月生產(chǎn)計(jì)劃，使工廠(chǎng)的利潤(rùn)最大。制訂月生產(chǎn)計(jì)劃，使工廠(chǎng)的利潤(rùn)最大。練習(xí)：練習(xí)： 汽車(chē)生產(chǎn)計(jì)劃和汽車(chē)生產(chǎn)計(jì)劃和原油采購(gòu)與加工原油采購(gòu)與加工 應(yīng)如何安排原油的采購(gòu)和加工應(yīng)如何安排原油的采購(gòu)和加工 ？ 練習(xí)練習(xí)2 原油采購(gòu)與加工原油采購(gòu)與加工 市場(chǎng)上可買(mǎi)到不超過(guò)市場(chǎng)上可買(mǎi)到不超過(guò)1500噸的原油噸的原油a： 購(gòu)買(mǎi)量不超過(guò)購(gòu)買(mǎi)量不超過(guò)500噸時(shí)的單價(jià)為噸時(shí)的單價(jià)為10000元元/ /噸；噸； 購(gòu)買(mǎi)量超過(guò)購(gòu)買(mǎi)量超過(guò)500噸但不超過(guò)噸但不超過(guò)1000噸時(shí)，超過(guò)噸時(shí)，超過(guò)500噸的噸的 部分部分8000元元/ /噸；噸；

23、 購(gòu)買(mǎi)量超過(guò)購(gòu)買(mǎi)量超過(guò)1000噸時(shí)，超過(guò)噸時(shí)，超過(guò)1000噸的部分噸的部分6000元元/ /噸。噸。 售價(jià)售價(jià)4800元元/噸噸 售價(jià)售價(jià)5600元元/噸噸庫(kù)存庫(kù)存500噸噸 庫(kù)存庫(kù)存1000噸噸 汽油甲汽油甲(a 50%) 原油原油a 原油原油b 汽油乙汽油乙 (a 60%) 設(shè)每月生產(chǎn)小、中、大型設(shè)每月生產(chǎn)小、中、大型汽車(chē)的數(shù)量分別為汽車(chē)的數(shù)量分別為x1, x2, x3321432xxxzmax600535 . 1.321xxxts60000400250280321xxx0,321xxx汽車(chē)廠(chǎng)生產(chǎn)計(jì)劃汽車(chē)廠(chǎng)生產(chǎn)計(jì)劃 模型建立模型建立 小型小型 中型中型 大型大型 現(xiàn)有量現(xiàn)有量鋼材鋼材 1.

24、5 3 5 600時(shí)間時(shí)間 280 250 400 60000利潤(rùn)利潤(rùn) 2 3 4 線(xiàn)性線(xiàn)性規(guī)劃規(guī)劃模型模型(lp)模型模型求解求解 3） 模型中增加條件：模型中增加條件：x1, x2, x3 均為整數(shù)，重新求解。均為整數(shù)，重新求解。 objective function value 1) 632.2581variable value reduced cost x1 64.516129 0.000000 x2 167.741928 0.000000 x3 0.000000 0.946237 row slack or surplus dual prices 2) 0.000000 0.73118

25、3 3) 0.000000 0.003226結(jié)果為小數(shù)，結(jié)果為小數(shù)，怎么辦？怎么辦？1）舍去小數(shù)：?。┥崛バ?shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值，算出目標(biāo)函數(shù)值z(mì)=629，與，與lp最優(yōu)值最優(yōu)值632.2581相差不大。相差不大。2）試探：如取）試探：如取x1=65，x2=167；x1=64，x2=168等，計(jì)算函數(shù)等，計(jì)算函數(shù)值值z(mì)，通過(guò)比較可能得到更優(yōu)的解。，通過(guò)比較可能得到更優(yōu)的解。 但必須檢驗(yàn)它們是否滿(mǎn)足約束條件。為什么？但必須檢驗(yàn)它們是否滿(mǎn)足約束條件。為什么？ip可用可用lindo直接求解直接求解整數(shù)規(guī)劃整數(shù)規(guī)劃( (integer programming, ,簡(jiǎn)記簡(jiǎn)記ip

26、) )“gin 3”表示表示“前前3個(gè)變量個(gè)變量為整數(shù)為整數(shù)”，等價(jià)于：，等價(jià)于：gin x1gin x2gin x3 ip 的最優(yōu)解的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值，最優(yōu)值z(mì)=632 max 2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin 3 objective function value 1) 632.0000variable value reduced cost x1 64.000000 -2.000000 x2 168.000000 -3.000000 x3 0.000000 -4.00000

27、0 321432xxxzmax600535 . 1.321xxxts60000400250280321xxx為非負(fù)整數(shù)321,xxx模型求解模型求解 ip 結(jié)果輸出結(jié)果輸出其中其中3個(gè)個(gè)子模型應(yīng)子模型應(yīng)去掉，然后去掉，然后逐一求解，比較目標(biāo)函數(shù)值，逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：再加上整數(shù)約束，得最優(yōu)解：80, 0, 0321xxx0,80, 0321xxx80,80, 0321xxx0, 0,80321xxx0,80,80321xxx80, 0,80321xxx80,80,80321xxx0,321xxx方法方法1：分解為：分解為8個(gè)個(gè)lp子模型子模型 汽車(chē)廠(chǎng)生產(chǎn)計(jì)劃汽車(chē)

28、廠(chǎng)生產(chǎn)計(jì)劃 若生產(chǎn)某類(lèi)汽車(chē)，則至少生產(chǎn)若生產(chǎn)某類(lèi)汽車(chē)，則至少生產(chǎn)8080輛，求生產(chǎn)計(jì)劃。輛，求生產(chǎn)計(jì)劃。321432xxxzmax600535 . 1.321xxxts60000400250280321xxxx1, ,x2, x3=0 或或 80 x1=80，x2= 150，x3=0，最優(yōu)值，最優(yōu)值z(mì)=610lindo中對(duì)中對(duì)0-1變量的限定：變量的限定：int y1int y2int y3 方法方法2：引入引入0-1變量，化為整數(shù)規(guī)劃變量，化為整數(shù)規(guī)劃 m為大的正數(shù)，為大的正數(shù)，可取可取1000 objective function value 1) 610.0000variable val

29、ue reduced cost x1 80.000000 -2.000000 x2 150.000000 -3.000000 x3 0.000000 -4.000000 y1 1.000000 0.000000 y2 1.000000 0.000000 y3 0.000000 0.000000 若生產(chǎn)某類(lèi)汽車(chē)，則至少生產(chǎn)若生產(chǎn)某類(lèi)汽車(chē)，則至少生產(chǎn)8080輛，求生產(chǎn)計(jì)劃。輛，求生產(chǎn)計(jì)劃。x1=0 或 80 x2=0 或 80 x3=0 或 801 , 0,80,11111yyxmyx1 , 0,80,22222yyxmyx1 , 0,80,33333yyxmyx最優(yōu)解同前最優(yōu)解同前 nlp雖然可

30、用現(xiàn)成的數(shù)學(xué)軟件求解雖然可用現(xiàn)成的數(shù)學(xué)軟件求解( (如如lingo, , matlab) )，但是其結(jié)果常依賴(lài)于初值的選擇。，但是其結(jié)果常依賴(lài)于初值的選擇。 方法方法3：化為非線(xiàn)性規(guī)劃化為非線(xiàn)性規(guī)劃 非線(xiàn)性規(guī)劃（非線(xiàn)性規(guī)劃（non- linear programming，簡(jiǎn)記，簡(jiǎn)記nlp） 實(shí)踐表明，本例僅當(dāng)初值非常接近上面方法算出實(shí)踐表明，本例僅當(dāng)初值非常接近上面方法算出的最優(yōu)解時(shí)，才能得到正確的結(jié)果。的最優(yōu)解時(shí)，才能得到正確的結(jié)果。 若生產(chǎn)某類(lèi)汽車(chē)，則至少生產(chǎn)若生產(chǎn)某類(lèi)汽車(chē)，則至少生產(chǎn)8080輛，求生產(chǎn)計(jì)劃。輛，求生產(chǎn)計(jì)劃。 x1=0 或 80 x2=0 或 80 x3=0 或 800)8

31、0(11xx0)80(22xx0)80(33xx應(yīng)如何安排原油的采購(gòu)和加工應(yīng)如何安排原油的采購(gòu)和加工 ？ 例例2 原油采購(gòu)與加工原油采購(gòu)與加工 市場(chǎng)上可買(mǎi)到不超過(guò)市場(chǎng)上可買(mǎi)到不超過(guò)1500噸的原油噸的原油a： 購(gòu)買(mǎi)量不超過(guò)購(gòu)買(mǎi)量不超過(guò)500噸時(shí)的單價(jià)為噸時(shí)的單價(jià)為10000元元/ /噸；噸； 購(gòu)買(mǎi)量超過(guò)購(gòu)買(mǎi)量超過(guò)500噸但不超過(guò)噸但不超過(guò)1000噸時(shí)，超過(guò)噸時(shí)，超過(guò)500噸的噸的 部分部分8000元元/ /噸；噸； 購(gòu)買(mǎi)量超過(guò)購(gòu)買(mǎi)量超過(guò)1000噸時(shí)，超過(guò)噸時(shí)，超過(guò)1000噸的部分噸的部分6000元元/ /噸。噸。 售價(jià)售價(jià)4800元元/噸噸 售價(jià)售價(jià)5600元元/噸噸庫(kù)存庫(kù)存500噸噸 庫(kù)存庫(kù)

32、存1000噸噸 汽油甲汽油甲(a 50%) 原油原油a 原油原油b 汽油乙汽油乙 (a 60%) 決策決策變量變量 目標(biāo)目標(biāo)函數(shù)函數(shù)問(wèn)題問(wèn)題分析分析 利潤(rùn)：銷(xiāo)售汽油的收入利潤(rùn)：銷(xiāo)售汽油的收入 - - 購(gòu)買(mǎi)原油購(gòu)買(mǎi)原油a的支出的支出 難點(diǎn)：原油難點(diǎn)：原油a的購(gòu)價(jià)與購(gòu)買(mǎi)量的關(guān)系較復(fù)雜的購(gòu)價(jià)與購(gòu)買(mǎi)量的關(guān)系較復(fù)雜)()(6 . 5)( 8 . 422122111xcxxxxzmax甲甲(a 50%) a b 乙乙(a 60%) 購(gòu)買(mǎi)購(gòu)買(mǎi)xx11x12x21x224.8千元千元/噸噸 5.6千元千元/噸噸原油原油a的購(gòu)買(mǎi)量的購(gòu)買(mǎi)量, ,原油原油a, b生產(chǎn)生產(chǎn)汽油汽油甲甲,乙的數(shù)量乙的數(shù)量c(x) 購(gòu)買(mǎi)

33、原油購(gòu)買(mǎi)原油a的支出的支出利潤(rùn)利潤(rùn)(千元千元)c(x)如何表述？如何表述？原油供應(yīng)原油供應(yīng) 約束約束條件條件xxx500121110002221 xx1500 x500)1(1000 300061000)(500 1000 8500)(0 10)(xxxxxxxc x 500噸單價(jià)為噸單價(jià)為10千千元元/ /噸；噸； 500噸噸 x 1000噸，超過(guò)噸，超過(guò)500噸的噸的8千千元元/ /噸；噸；1000噸噸 x 1500噸，超過(guò)噸，超過(guò)1000噸的噸的6千千元元/ /噸。噸。 目標(biāo)目標(biāo)函數(shù)函數(shù)購(gòu)買(mǎi)購(gòu)買(mǎi)x a b x11x12x21x22庫(kù)存庫(kù)存500噸噸 庫(kù)存庫(kù)存1000噸噸 目標(biāo)函數(shù)中目標(biāo)函

34、數(shù)中c(x)不是線(xiàn)性函數(shù)，是非線(xiàn)性規(guī)劃；不是線(xiàn)性函數(shù)，是非線(xiàn)性規(guī)劃； 對(duì)于用分段函數(shù)定義的對(duì)于用分段函數(shù)定義的c(x)，一般的非線(xiàn)性規(guī)劃軟，一般的非線(xiàn)性規(guī)劃軟件也難以輸入和求解；件也難以輸入和求解； 想辦法將模型化簡(jiǎn)，用現(xiàn)成的軟件求解。想辦法將模型化簡(jiǎn)，用現(xiàn)成的軟件求解。 汽油含原油汽油含原油a的比例限制的比例限制 5 . 0211111 xxx6 . 0221212 xxx2111xx 221232xx 約束約束條件條件甲甲(a 50%) a b 乙乙(a 60%) x11x12x21x22x1 , x2 , x3 以?xún)r(jià)格以?xún)r(jià)格10, 8, 6(千元千元/ /噸噸) )采購(gòu)采購(gòu)a的噸數(shù)的噸數(shù)

35、目標(biāo)目標(biāo)函數(shù)函數(shù) 只有當(dāng)以只有當(dāng)以10千元千元/噸的價(jià)格購(gòu)買(mǎi)噸的價(jià)格購(gòu)買(mǎi)x1=500( (噸噸) )時(shí)，才能以時(shí)，才能以8千元千元/噸的價(jià)格購(gòu)買(mǎi)噸的價(jià)格購(gòu)買(mǎi)x2方法方法1 )6810()( 6 . 5)( 8 . 432122122111xxxxxxxzmax0)500(32xx500,0321xxx非線(xiàn)性規(guī)劃模型非線(xiàn)性規(guī)劃模型，可以用，可以用lingo求解求解模型求解模型求解x= x1+x2+x3, c(x) = 10 x1+8x2+6x3 500噸噸 x 1000噸，超過(guò)噸，超過(guò)500噸的噸的8千千元元/ /噸噸增加約束增加約束0)500(21xxx= x1+x2+x3, c(x) = 10 x1+8x2+6x3 方法方法1：lingo求解求解model:max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - 10*x1 - 8*x2 - 6