【導(dǎo)讀】現(xiàn)實世界中普遍存在著優(yōu)化問題。靜態(tài)優(yōu)化問題指最優(yōu)解是數(shù)。建立靜態(tài)優(yōu)化模型的關(guān)鍵之一是根。備要付生產(chǎn)準(zhǔn)備費，產(chǎn)量大于需求時要付貯存費。生產(chǎn)能力非常大，即所需數(shù)量可在很短時間內(nèi)產(chǎn)出。試安排該產(chǎn)品的生產(chǎn)計劃，即多少天生產(chǎn)。一次，每次產(chǎn)量多少，使總費用最小。日需求100件，準(zhǔn)備費5000元，貯存費每日每件1元。這是一個優(yōu)化問題，關(guān)鍵在建立目標(biāo)函數(shù)。設(shè)r,c1,c2已知，求T,Q使每天總費用的平均值最小。需求速率r遞減，q=0.經(jīng)濟批量訂貨公式。在什么條件下才不考慮？零時，Q件立即到貨。Q~不允許缺貨時的產(chǎn)量QQR???備，估計可使80千克重的生豬體重增加2公斤。低，問生豬應(yīng)何時出售。如果估計和預(yù)測有誤差，對結(jié)果有何影響。

　　

【正文】 1) VARIABLE VALUE REDUCED COST X11 X12 X13 X14 X21 X22 X23 X24 X31 X32 X33 利潤 =總收入 其它費用 引 水 管 理 費=1440007202024400 = 47600（ 元 ） A(50) B(60) C(50) 甲 (30。50) 乙 (70。70) 丙 (10。20) 丁 (10。40) 50 50 40 10 10 引水管理費 24400(元 ) 福 州 大 學(xué) 72 目標(biāo)函數(shù) 總供水量 (320) 總需求量 (300) 每個水庫最大供水量都提高一倍 利潤 = 收入 (900) –其它費用 (450) –引水管理費 利潤 (元 /千噸 ) 甲 乙 丙 丁 A 290 320 230 280 B 310 320 260 300 C 260 250 220 / 3332312423222114131211220250260300260320310280230320290xxxxxxxxxxxZM ax???????????供應(yīng)限制 B, C 類似處理 50:A 14131211 ???? xxxx10014131211 ???? xxxx問題討論 確定送水方案 使利潤最大 需求約束可以不變 福 州 大 學(xué) 73 求解 OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST X11 X12 X13 X14 X21 X22 X23 X24 X31 X32 X33 這類問題一般稱為“運輸問題” (Transportation Problem) 總利潤 88700（ 元 ） A(100) B(120) C(100) 甲 (30。50) 乙 (70。70) 丙 (10。20) 丁 (10。40) 40 100 50 30 50 30 福 州 大 學(xué) 74 如何 裝運，使本次飛行獲利最大？ 三個貨艙 最大 載 重 (噸 ),最大容積 (米 3) 例 2 貨機裝運 重量（噸） 空間 ( 米 3/噸） 利潤（元 /噸） 貨物 1 18 480 3100 貨物 2 15 650 3800 貨物 3 23 580 3500 貨物 4 12 390 2850 三個貨艙中實際載重必須與其最大 載 重成比例 前倉： 10； 6800 中倉： 16； 8700 后倉： 8； 5300 飛機平衡 福 州 大 學(xué) 75 決策變量 xij第 i 種貨物裝入第 j 個貨艙的重量 (噸） i=1,2,3,4, j=1,2,3 (分別代表前、中、后倉 ) 模型假設(shè) 每種貨物可以分割到任意小； 貨機裝運 每種貨物可以在一個或多個貨艙中任意分布； 多種貨物可以混裝，并保證不留空隙； 模型建立 福 州 大 學(xué) 76 貨艙容積 目標(biāo)函數(shù)(利潤 ) 約束條件 )(2850)(3500)(3800)(3100434241333231232221131211xxxxxxxxxxxxZM ax????????????6 8 0 03 9 05 8 06 5 04 8 0 41312111 ???? xxxx8 7 0 0390580650480 42322212 ???? xxxx5 3 0 03 9 05 8 06 5 04 8 0 43332313 ???? xxxx貨機裝運 模型建立 貨艙重量 1041312111 ???? xxxx1642322212 ???? xxxx843332313 ???? xxxx10；6800 16；8700 8；5300 xij第 i 種貨物裝入第 j 個貨艙的重量 福 州 大 學(xué) 77 約束條件 平衡要求 81610433323134232221241312111xxxxxxxxxxxx???????????貨物供應(yīng) 18131211 ??? xxx15232221 ??? xxx23333231 ??? xxx12434241 ??? xxx貨機裝運 模型建立 10；6800 16；8700 8；5300 xij第 i 種貨物裝入第 j 個貨艙的重量 福 州 大 學(xué) 78 OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST X11 X12 X13 X21 X22 X23 X31 X32 X33 X41 X42 X43 貨物 2：前倉 10,后倉 5； 貨物 3: 中倉 13, 后倉 3；貨物 4: 中倉 3。 貨機裝運 模型求解 最大利潤約 121516元 貨物 ~供應(yīng)點 貨艙 ~需求點 平衡要求 運輸問題 運輸問題的擴展 福 州 大 學(xué) 79 ? 如果生產(chǎn)某一類型汽車，則至少要生產(chǎn) 80輛， 那么最優(yōu)的生產(chǎn)計劃應(yīng)作何改變？ 例 1 汽車廠生產(chǎn)計劃 汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤及工廠每月的現(xiàn)有量。 小型 中型 大型 現(xiàn)有量 鋼材（噸） 3 5 600 勞動時間（小時） 280 250 400 60000 利潤（萬元） 2 3 4 ? 制訂月生產(chǎn)計劃 ， 使工廠的利潤最大 。 汽車生產(chǎn)與原油采購 福 州 大 學(xué) 80 設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為 x1, x2, x3 321 432 xxxzM a x ???.. 321 ??? xxxts6 0 0 0 0400250280 321 ??? xxx0, 321 ?xxx汽車廠生產(chǎn)計劃 模型建立 小型 中型 大型 現(xiàn)有量 鋼材 3 5 600 時間 280 250 400 60000 利潤 2 3 4 線性規(guī)劃模型(LP) 福 州 大 學(xué) 81 模型求解 3） 模型中增加條件： x1, x2, x3 均為整數(shù) ， 重新求解 。 OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST X1 X2 X3 ROW SLACK OR SURPLUS DUAL PRICES 2) 3) 結(jié)果為小數(shù)，怎么辦？ 1）舍去小數(shù)：取 x1=64， x2=167，算出目標(biāo)函數(shù)值 z=629，與LP最優(yōu)值 。 2） 試探：如取 x1=65， x2=167； x1=64， x2=168等 ， 計算函數(shù)值 z， 通過比較可能得到更優(yōu)的解 。 ? 但必須檢驗它們是否滿足約束條件。為什么？ 福 州 大 學(xué) 82 IP可用 LINDO直接求解 整數(shù)規(guī)劃 (Integer Programming,簡記 IP) ―gin 3‖表示 “ 前 3個變量為整數(shù) ” ，等價于： gin x1 gin x2 gin x3 IP 的最優(yōu)解 x1=64， x2=168， x3=0，最優(yōu)值 z=632 max 2x1+3x2+4x3 st +3x2+5x3600 280x1+250x2+400x360000 end gin 3 OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST X1 X2 X3 321 432 xxxzM a x ???.. 321 ??? xxxts60000400250280 321 ??? xxx為非負(fù)整數(shù)321 , xxx模型求解 IP 結(jié)果輸出 福 州 大 學(xué) 83 其中 3個 子模型應(yīng) 去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解： 80,0,0 321 ??? xxx0,80,0 321 ??? xxx80,80,0 321 ??? xxx0,0,80 321 ??? xxx0,80,80 321 ??? xxx80,0,80 321 ??? xxx80,80,80 321 ??? xxx0, 321 ?xxx方法 1：分解為 8個 LP子模型 汽車廠生產(chǎn)計劃 ? 若生產(chǎn)某類汽車，則至少生產(chǎn) 80輛，求生產(chǎn)計劃。 321 432 xxxzM a x ???.. 321 ??? xxxts60000400250280 321 ??? xx