1、1優化模型2 3特點：從若干可能的計劃（方案）中尋求某種意義下的最優方案，數學上將這種問題稱為最優化問題（optimization).靜態問題(沒有考慮時間t的變化)1、生產計劃問題；2、運輸問題；4單耗 甲 乙 丙 x1 x2 x3限額材料工時工人 2 3 1 3 2 1.5 3 2 5343640利潤(元/件) 4 3 2在一定的條件下，問生產數量xi =？使利潤達到最大？數據表123123123123123max4322334321.536. .32540,0Zxxxxxxxxxstxxxx x x規劃模型利潤材料工時人力5A1325801010312012427010881070627

2、030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道鐵路公路S1S7 鋼管廠火車站450 里程（km）目標：運費達到最小網絡圖6 某種原材料有M個產地，現在需要將原材料從產地運往N個工地，假定M個產地的產量為ai和N個工地的需求量為bj，單位產品的運費cij已知，那么如何安排運輸方案可以使總運費最低？數學模型：1111min.

3、.,1,2,.,1,2,.,MNijijijNijijMijjic xstxaiMxbjN cij 單位運費；xij 運輸量；ai 第i 地產量；bj 第j 地需要量；狀態變量返 回7建立最優化的數學模型應具備三個基本要素1、決策變量（decision variables);2、約束條件（constraints);3、目標函數（objective function)最優化問題分類：線性、非線性靜態、動態整數、非整數隨機、非隨機等 返 回8優化，規劃的類型 無約束優化 線性規劃(LP) 目標和約束均為線性函數 非線性規劃(NLP) 目標和約束均為非線性函數 整數規劃(IP) 決策變量為整數 組合

4、優化 不確定規劃 多目標規劃 目標函數至少兩個以上 網絡優化 動態規劃 研究隨時間變化的決策問題 返 回9典型的工程應用問題返 回線性規劃(LP)運輸問題配料問題投資計劃綜合生產中轉調用生產率比較整數規劃(IP)投資選擇生產計劃指派問題下料問題50個決策變量以上的優化問題稱為大規模的.10min cTxs.t. Axb x0歸納：TT123c4, 3, 2, ,2 3134A3 2 1.5 ,b363 2540 x x xx123123123123123max4322334321.536. .32540,0Zxxxxxxxxxstxxxx x x規劃模型利潤材料工時人力111、可行解（可行點）

5、2、可行域3、最優解例：Max z = 3x1+x2s.t. -x1+x22 L1 x1-2x22 L2 3x1+2x214 L3 x1，x20起作用約束：L2，L3最優解（4，1）最優值 zmax = 13L3L2L112多峰函數，存在局部最大和整體最大等值線圖函數曲面圖形4. 局部最優解5. 整體最優解13建模時需要注意的幾個基本問題1.盡量使用實數優化，減少整數約束和整數變量2.盡量使用光滑優化，減少非光滑約束的個數如：盡量少使用絕對值、符號函數、多個變量求最大/最小、四舍五入、取整函數等3.盡量使用線性模型，減少非線性約束和非線性變量的個數 4.合理設定變量的上下界，盡可能給出變量初始

6、值5.模型中使用的參數數量級要恰當（小于103） 返 回141.LINDO/LINGO軟件2.MATLAB優化工具箱3.EXCELL軟件的優化功能4.SAS(統計分析）軟件的優化功能151.LINDO/LINGO軟件2.MATLAB優化工具箱3.EXCELL軟件的優化功能4.SAS(統計分析）軟件的優化功能16優化模型連續優化整數規劃(IP)線性規劃二次規劃非線性規劃規劃LINDOLINGO例例1 加工奶制品的生產計劃加工奶制品的生產計劃1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶 時間時間480小時小時 至多加工至多加工100公斤

7、公斤A1 制訂生產計劃，使每天獲利最大制訂生產計劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時工人，付出的工資最多是每小時幾元可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到的獲利增加到 30元元/公斤，應否改變生產計劃？公斤，應否改變生產計劃？ 每天：每天：奶制品的生產與銷售奶制品的生產與銷售1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1桶牛奶生產桶牛奶生產A1 x2桶牛奶生產桶牛奶生產A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應原料供應

8、 5021 xx勞動時間勞動時間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標函數目標函數 216472xxzMax每天獲利每天獲利約束條件約束條件非負約束非負約束 0,21xx線性線性規劃規劃模型模型(LP)時間時間480小時小時 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型求解模型求解 圖解法圖解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx約約束束條條件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMax目標目標函

9、數函數 Z=0Z=2400Z=3600z=c (常數常數) 等值線等值線c在在B(20,30)點得到最優解點得到最優解目標函數和約束條件是線性函數目標函數和約束條件是線性函數 可行域為直線段圍成的凸多邊形可行域為直線段圍成的凸多邊形 目標函數的等值線為直線目標函數的等值線為直線 最優解一定在凸多邊最優解一定在凸多邊形的某個頂點取得。形的某個頂點取得。 模型求解模型求解 軟件實現軟件實現 LINDO 6.1 max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE

10、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桶牛奶生產桶牛奶生產A1, 30桶生產桶生產A2，利潤，利潤3360元。元。 結果解釋結果解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000

11、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原料無剩余原料無剩余時間無剩余時間無剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束

12、）剩余為零的約束為緊約束（有效約束） 結果解釋結果解釋 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最優解下最優解下“資源資源”增加增加1單位時單位時“效益效益”的增的增量量 原料增加原料增加1單

13、位單位, 利潤增長利潤增長48 時間增加時間增加1單位單位, 利潤增長利潤增長2 加工能力增長不影響利潤加工能力增長不影響利潤影子價格影子價格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？35 48, 應該買！應該買！ 聘用臨時工人付出的工資最多每小時幾元？聘用臨時工人付出的工資最多每小時幾元？ 2元！元！RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.00

14、0000 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.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000最優解不變時目標函最優解不變時目標函數系數允許變化范圍數系數允許變化范圍 DO RANGE(SENSITIVITY) ANALYSIS? Yesx1系數范圍系數范圍(

15、64,96) x2系數范圍系數范圍(48,72) A1獲利增加到獲利增加到 30元元/千克，應否改變生產計劃千克，應否改變生產計劃 x1系數由系數由24 3=72增加增加為為30 3=90，在在允許范圍內允許范圍內 不變！不變！(約束條件不變約束條件不變)結果解釋結果解釋 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.00

16、0000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000影子價格有意義時約束右端的允許變化范圍影子價格有意義時約束右端的允許變化范圍 原料最多增加原料最多增加10 時間最多增加時間最多增加53 35元可買到元可買到1桶牛奶，每天最多買多少？桶牛奶，每天最多買多少？最

17、多買最多買10桶桶!(目標函數不變目標函數不變)例例2 奶制品的生產銷售計劃奶制品的生產銷售計劃 在例在例1基礎上深加工基礎上深加工1桶桶牛奶牛奶 3千克千克A1 12小時小時 8小時小時 4公斤公斤A2 或或獲利獲利24元元/公斤公斤 獲利獲利16元元/公斤公斤 0.8千克千克B12小時小時,3元元1千克千克獲利獲利44元元/千克千克 0.75千克千克B22小時小時,3元元1千克千克獲利獲利32元元/千克千克 制訂生產計劃，使每天凈利潤最大制訂生產計劃，使每天凈利潤最大 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小時時間，應否投小時時間，應否投資？現投資資？現投資150元，可

18、賺回多少？元，可賺回多少？50桶牛奶桶牛奶, 480小時小時 至多至多100公斤公斤A1 B1，B2的獲利經常有的獲利經常有10%的波動，對計劃有無影響？的波動，對計劃有無影響？1桶桶牛奶牛奶 3千克千克 A1 12小時小時 8小時小時 4千克千克 A2 或或獲利獲利24元元/千克千克 獲利獲利16元元/kg 0.8千克千克 B12小時小時,3元元1千克千克獲利獲利44元元/千克千克 0.75千克千克 B22小時小時,3元元1千克千克獲利獲利32元元/千克千克 出售出售x1 千克千克 A1, x2 千克千克 A2， X3千克千克 B1, x4千克千克 B2原料原料供應供應 勞動勞動時間時間 加

19、工能力加工能力 決策決策變量變量 目標目標函數函數 利潤利潤約束約束條件條件非負約束非負約束 0,61xx x5千克千克 A1加工加工B1， x6千克千克 A2加工加工B26543213332441624xxxxxxzMax50436251xxxx48022)(2)(4656251xxxxxx10051 xx附加約束附加約束 5380 x.x64750 x.x 模型求解模型求解 軟件實現軟件實現 LINDO 6.1 5043) 26251xxxx48022)(2)(4)3656251xxxxxx OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VAL

20、UE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS

21、= 2600334) 26521xxxx44804624) 36521xxxxDO RANGE (SENSITIVITY) ANALYSIS? No 自來水輸送與貨機裝運自來水輸送與貨機裝運生產、生活物資從若干供應點運送到一些需求點，生產、生活物資從若干供應點運送到一些需求點，怎樣安排輸送方案使運費最小，或利潤最大；怎樣安排輸送方案使運費最小，或利潤最大；運輸問題運輸問題各種類型的貨物裝箱，由于受體積、重量等限制，各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數量最少。如何搭配裝載，使獲利最高，或裝箱數量最少。其他費用其他費用: :450元元/千噸千噸 應如何分配

22、水庫供水量，公司才能獲利最多？應如何分配水庫供水量，公司才能獲利最多？ 若水庫供水量都提高一倍，公司利潤可增加到多少？若水庫供水量都提高一倍，公司利潤可增加到多少？ 元元/千噸千噸甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理費引水管理費例例1 自來水輸送自來水輸送收入：收入：900元元/千噸千噸 支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40水庫供水量水庫供水量(千噸千噸)小區基本用水量小區基本用水量(千噸千噸)小區額外用水量小區額外用水量(千噸千噸)（以天計）（以天計）總供水量：總

23、供水量：160確定送水方案確定送水方案使利潤最大使利潤最大問題問題分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40 總需求量總需求量(300)每個水庫最大供水量都提高一倍每個水庫最大供水量都提高一倍利潤利潤 = 收入收入(900) 其它費用其它費用( (450) 引水管理費引水管理費利潤利潤(元元/千噸千噸)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/3332312423222114131211220250260300260320310280230320290 xxxxxxxxxxxZMax供

24、應供應限制限制B, C 類似處理類似處理50:A14131211xxxx10014131211xxxx問題討論問題討論 確定送水方案確定送水方案使利潤最大使利潤最大需求約束可以不變需求約束可以不變求解求解 OBJECTIVE FUNCTION VALUE 1) 88700.00 VARIABLE VALUE REDUCED COST X11 0.000000 20.000000 X12 100.000000 0.000000 X13 0.000000 40.000000 X14 0.000000 20.000000 X21 30.000000 0.000000 X22 40.000000 0.

25、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 這類問題一般稱為這類問題一般稱為“運輸問題運輸問題”(Transportation Problem)總利潤總利潤 88700（元）（元） A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030如何如何裝運，裝運，使本次飛行使本次飛行獲利最大？獲利最大？ 三個貨艙三個貨艙最大最

26、大載載重重( (噸噸),),最大容積最大容積( (米米3 3) ) 例例2 貨機裝運貨機裝運 重量（噸）重量（噸）空間空間( 米米3/噸）噸）利潤（元利潤（元/噸）噸）貨物貨物1184803100貨物貨物2156503800貨物貨物3235803500貨物貨物4123902850三個貨艙中實際載重必須與其最大三個貨艙中實際載重必須與其最大載載重成比例重成比例 前倉：前倉：10；6800中倉：中倉：16；8700后倉：后倉：8；5300飛機平衡飛機平衡決策決策變量變量 xij-第第i 種貨物裝入第種貨物裝入第j 個貨艙的重量個貨艙的重量( (噸）噸）i=1,2,3,4, j=1,2,3 (分別代

27、表前、中、后倉分別代表前、中、后倉)模型假設模型假設 每種貨物可以分割到任意小；每種貨物可以分割到任意小；貨機裝運貨機裝運每種貨物可以在一個或多個貨艙中任意分布；每種貨物可以在一個或多個貨艙中任意分布；多種貨物可以混裝，并保證不留空隙；多種貨物可以混裝，并保證不留空隙； 模型建立模型建立 貨艙貨艙容積容積 目標目標函數函數( (利潤利潤)約束約束條件條件 )(2850)(3500)(3800)(3100434241333231232221131211xxxxxxxxxxxxZMax680039058065048041312111xxxx870039058065048042322212xxxx5

28、30039058065048043332313xxxx貨機裝運貨機裝運模型建立模型建立 貨艙貨艙重量重量 1041312111xxxx1642322212xxxx843332313xxxx10；680016；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j 個貨艙的重量個貨艙的重量約束約束條件條件平衡平衡要求要求 81610433323134232221241312111xxxxxxxxxxxx貨物貨物供應供應 18131211xxx15232221xxx23333231xxx12434241xxx貨機裝運貨機裝運模型建立模型建立 10；680016；87008；5300 xi

29、j-第第i 種貨物裝入第種貨物裝入第j 個貨艙的重量個貨艙的重量 OBJECTIVE FUNCTION VALUE 1) 121515.8 VARIABLE VALUE REDUCED COST X11 0.000000 400.000000 X12 0.000000 57.894737 X13 0.000000 400.000000 X21 10.000000 0.000000 X22 0.000000 239.473679 X23 5.000000 0.000000 X31 0.000000 0.000000 X32 12.947369 0.000000 X33 3.000000 0.00

30、0000 X41 0.000000 650.000000 X42 3.052632 0.000000 X43 0.000000 650.000000 貨物貨物2：前倉：前倉10, ,后倉后倉5； 貨物貨物3: : 中倉中倉13, 后倉后倉3；貨物貨物4: : 中倉中倉3。貨機裝運貨機裝運模型求解模型求解 最大利潤約最大利潤約121516元元貨物貨物供應點供應點貨艙貨艙需求點需求點平衡要求平衡要求運輸運輸問題問題運輸問題的擴展運輸問題的擴展 OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1

31、.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2結果解釋結果解釋每天銷售每天銷售168 千克千克A2

32、和和19.2 千克千克B1， 利潤利潤3460.8（元）（元）8桶牛奶加工成桶牛奶加工成A1，42桶桶牛奶加工成牛奶加工成A2，將得到的將得到的24千克千克A1全部全部加工成加工成B1 除加工能力外均除加工能力外均為緊約束為緊約束結果解釋結果解釋 OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6

33、 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000增加增加1桶牛奶使利潤增桶牛奶使利潤增長長3.1612=37.925043)26251xxxx600334) 26521xxxx4增加增加1小時時間使利小時時間使利潤增長潤增長3.26 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小時時間，小時時間，應否投資？現投資應否

34、投資？現投資150元，可賺回多少？元，可賺回多少？投資投資150元增加元增加5桶牛奶，桶牛奶，可賺回可賺回189.6元。（大于元。（大于增加時間的利潤增長）增加時間的利潤增長）結果解釋結果解釋B1,B2的獲利有的獲利有10%的波動，對計劃有無影響的波動，對計劃有無影響 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 24.000000 1.680000 INFINITY X2 16.00000

35、0 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 DO RANGE (SENSITIVITY) ANALYSIS? YesB1獲利下降獲利下降10%，超，超出出X3 系數允許范圍系數允許范圍B2獲利上升獲利上升10%，超，超出出X4 系數允許范圍系數允許范圍波動對計劃有影響波動對計劃有影響生產計劃應重新制訂：如將生產計劃應重新制訂：如將x3的系數改為的系數

36、改為39.6計算，會發現結果有很大變化。計算，會發現結果有很大變化。 43設每月生產小、中、大型設每月生產小、中、大型汽車的數量分別為汽車的數量分別為x1, x2, x3321432xxxzMax600535 . 1.321xxxts60000400250280321xxx0,321xxx汽車廠生產計劃汽車廠生產計劃 模型建立模型建立 小型小型 中型中型 大型大型 現有量現有量鋼材鋼材 1.5 3 5 600時間時間 280 250 400 60000利潤利潤 2 3 4 線性線性規劃規劃模型模型(LP)模型模型求解求解 3） 模型中增加條件：模型中增加條件：x1, x2, x3 均為整數，重

37、新求解。均為整數，重新求解。 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.731183 3) 0.000000 0.003226結果為小數，結果為小數，怎么辦？怎么辦？1）舍去小數：取）舍去小數：取x1=64，x2=167，算出目標函數值，算出目標函數值z=629，與，與LP最優值最優值6

38、32.2581相差不大。相差不大。2）試探：如取）試探：如取x1=65，x2=167；x1=64，x2=168等，計算函數等，計算函數值值z，通過比較可能得到更優的解。，通過比較可能得到更優的解。 但必須檢驗它們是否滿足約束條件。為什么？但必須檢驗它們是否滿足約束條件。為什么？IP可用可用LINDO直接求解直接求解整數規劃整數規劃( (Integer Programming, ,簡記簡記IP) )“gin 3”表示表示“前前3個變量個變量為整數為整數”，等價于：，等價于：gin x1gin x2gin x3 IP 的最優解的最優解x1=64，x2=168，x3=0，最優值，最優值z=632 m

39、ax 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.000000 321432xxxzMax600535 . 1.321xxxts60000400250280321xxx為非負整數321,xxx模型求解模型求解 IP 結果輸出結果輸出其中其中3個個子模型應子模型應去掉

40、，然后去掉，然后逐一求解，比較目標函數值，逐一求解，比較目標函數值，再加上整數約束，得最優解：再加上整數約束，得最優解：80, 0, 0321xxx0,80, 0321xxx80,80, 0321xxx0, 0,80321xxx0,80,80321xxx80, 0,80321xxx80,80,80321xxx0,321xxx方法方法1：分解為：分解為8個個LP子模型子模型 汽車廠生產計劃汽車廠生產計劃 若生產某類汽車，則至少生產若生產某類汽車，則至少生產8080輛，求生產計劃。輛，求生產計劃。321432xxxzMax600535 . 1.321xxxts60000400250280321xx

41、xx1, ,x2, x3=0 或或 80 x1=80，x2= 150，x3=0，最優值，最優值z=610LINDO中對中對0-1變量的限定：變量的限定：int y1int y2int y3 方法方法2：引入引入0-1變量，化為整數規劃變量，化為整數規劃 M為大的正數，為大的正數，可取可取1000 OBJECTIVE FUNCTION VALUE 1) 610.0000VARIABLE VALUE REDUCED COST X1 80.000000 -2.000000 X2 150.000000 -3.000000 X3 0.000000 -4.000000 Y1 1.000000 0.0000

42、00 Y2 1.000000 0.000000 Y3 0.000000 0.000000 若生產某類汽車，則至少生產若生產某類汽車，則至少生產8080輛，求生產計劃。輛，求生產計劃。x1=0 或 80 x2=0 或 80 x3=0 或 801 , 0,80,11111yyxMyx1 , 0,80,22222yyxMyx1 , 0,80,33333yyxMyx最優解同前最優解同前 NLP雖然可用現成的數學軟件求解雖然可用現成的數學軟件求解( (如如LINGO, , MATLAB) )，但是其結果常依賴于初值的選擇。，但是其結果常依賴于初值的選擇。 方法方法3：化為非線性規劃化為非線性規劃 非線性

43、規劃（非線性規劃（Non- Linear Programming，簡記，簡記NLP） 實踐表明，本例僅當初值非常接近上面方法算出實踐表明，本例僅當初值非常接近上面方法算出的最優解時，才能得到正確的結果。的最優解時，才能得到正確的結果。 若生產某類汽車，則至少生產若生產某類汽車，則至少生產8080輛，求生產計劃。輛，求生產計劃。 x1=0 或 80 x2=0 或 80 x3=0 或 800)80(11xx0)80(22xx0)80(33xx應如何安排原油的采購和加工應如何安排原油的采購和加工 ？ 例例2 原油采購與加工原油采購與加工 市場上可買到不超過市場上可買到不超過1500噸的原油噸的原油A

44、： 購買量不超過購買量不超過500噸時的單價為噸時的單價為10000元元/ /噸；噸； 購買量超過購買量超過500噸但不超過噸但不超過1000噸時，超過噸時，超過500噸的噸的 部分部分8000元元/ /噸；噸； 購買量超過購買量超過1000噸時，超過噸時，超過1000噸的部分噸的部分6000元元/ /噸。噸。 售價售價4800元元/噸噸 售價售價5600元元/噸噸庫存庫存500噸噸 庫存庫存1000噸噸 汽油甲汽油甲(A 50%) 原油原油A 原油原油B 汽油乙汽油乙 (A 60%) 決策決策變量變量 目標目標函數函數問題問題分析分析 利潤：銷售汽油的收入利潤：銷售汽油的收入 - - 購買原

45、油購買原油A的支出的支出 難點：原油難點：原油A的購價與購買量的關系較復雜的購價與購買量的關系較復雜)()(6 . 5)( 8 . 422122111xcxxxxzMax甲甲(A 50%) A B 乙乙(A 60%) 購買購買xx11x12x21x224.8千元千元/噸噸 5.6千元千元/噸噸原油原油A的購買量的購買量, ,原油原油A, B生產生產汽油汽油甲甲,乙的數量乙的數量c(x) 購買原油購買原油A的支出的支出利潤利潤(千元千元)c(x)如何表述？如何表述？原油供應原油供應 約束約束條件條件xxx500121110002221 xx1500 x500)1(1000 300061000)(

46、500 1000 8500)(0 10)(xxxxxxxc x 500噸單價為噸單價為10千千元元/ /噸；噸； 500噸噸 x 1000噸，超過噸，超過500噸的噸的8千千元元/ /噸；噸；1000噸噸 x 1500噸，超過噸，超過1000噸的噸的6千千元元/ /噸。噸。 目標目標函數函數購買購買x A B x11x12x21x22庫存庫存500噸噸 庫存庫存1000噸噸 目標函數中目標函數中c(x)不是線性函數，是非線性規劃；不是線性函數，是非線性規劃； 對于用分段函數定義的對于用分段函數定義的c(x)，一般的非線性規劃軟，一般的非線性規劃軟件也難以輸入和求解；件也難以輸入和求解； 想辦法

47、將模型化簡，用現成的軟件求解。想辦法將模型化簡，用現成的軟件求解。 汽油含原油汽油含原油A的比例限制的比例限制 5 . 0211111 xxx6 . 0221212 xxx2111xx 221232xx 約束約束條件條件甲甲(A 50%) A B 乙乙(A 60%) x11x12x21x22x1 , x2 , x3 以價格以價格10, 8, 6(千元千元/ /噸噸) )采購采購A的噸數的噸數目標目標函數函數 只有當以只有當以10千元千元/噸的價格購買噸的價格購買x1=500( (噸噸) )時，才能以時，才能以8千元千元/噸的價格購買噸的價格購買x2方法方法1 )6810()( 6 . 5)(

48、8 . 432122122111xxxxxxxzMax0)500(32xx500,0321xxx非線性規劃模型非線性規劃模型，可以用，可以用LINGO求解求解模型求解模型求解x= x1+x2+x3, c(x) = 10 x1+8x2+6x3 500噸噸 x 1000噸，超過噸，超過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*x3;x11+

49、x12 x + 500;x21+x22 0; 2*x12 - 3*x22 0;x=x1+x2+x3; (x1 - 500) * x2=0; (x2 - 500) * x3=0; x1 500;x2 500;x3 0;x11 0;x12 0;x21 0;x22 0;x1 0;x2 0;x3 0;end Objective value: 4800.000Variable Value Reduced CostX11 500.0000 0.0000000E+00X21 500.0000 0.0000000E+00X12 0.0000000E+00 0.0000000E+00X22 0.0000000E+00 0.0000000E+00