【正文】 6/5 表 表中最后一行的所有檢驗(yàn)數(shù)都已是正數(shù)或零，從而得到基本最優(yōu)解 X*=(6,4,0,0)T, Z*=36 。由于 x3 , x4 是引進(jìn)的松弛變量，因此原問題的最優(yōu)解為 x1=6, x2=4, 最優(yōu)值 Z*=36 。 j?i?例 2 一奶制品加工廠用牛奶生產(chǎn) A1 , A2 兩種奶制品， 1 桶牛 奶可以在設(shè)備甲上用 12 小時加工成 3 公斤 A1,或者在設(shè)備 乙上用 8 小時加工成 4 公斤 A2。根據(jù)市場需求，生產(chǎn)的 A1 , A2 全部能售出，且每公斤 A1 獲利 24 元，每公斤 A2 獲利 16 元?，F(xiàn)在加工廠每天能得到 50 桶牛奶的供應(yīng)，每天正式工人 總的勞動時間為 480 小時，并且設(shè)備甲每天至多能加工 100 公斤 A1 , 設(shè)備乙的加工能力沒有限制。試為該廠制定一個 我們無意過深涉及線性規(guī)劃的具體計(jì)算方法，而著重介紹的是如何建立若干實(shí)際的線性規(guī)劃模型，如何使用現(xiàn)成的數(shù)學(xué)軟件進(jìn)行求解，以及如何對結(jié)果進(jìn)行深入的分析。 下面以奶制品加工生產(chǎn)計(jì)劃為例，進(jìn)行詳細(xì)的討論。 生產(chǎn)計(jì)劃，使每天獲利最大，并進(jìn)一步討論以下 3 個附加問題： ? 若用 35 元可買到 1 桶牛奶，買嗎？若買，每天最多 買多少 ? ? 若可以聘用臨時工人以增加勞動時間，付給臨時工人 的工資最多是每小時幾元 ? ? 由于市場需求的變化， A1 的獲利增加到 30元 /公斤， 應(yīng)否改變生產(chǎn)計(jì)劃？ 1桶牛奶 3公斤 A1 12小時 8小時 4公斤 A2 或 獲利 24元 /公斤 獲利 16元 /公斤 50桶牛奶 時間 480小時 至多加工 100公斤 A1 每天： 分析 x1 桶牛奶生產(chǎn) A1 x2 桶牛奶生產(chǎn) A2 獲利 24 3x1 獲利 16 4 x2 決策變量 ???????????????0, 1 0 03 4 8 0812 50 .6472 211212121xxxxxxxtsxxzM a x數(shù)學(xué)模型 原料供應(yīng) 勞動時間 加工能力 非負(fù)約束 解法 1：圖解法。 x1 x2 0 A B C D l1 l2 l3 l4 l5 5021 ?? xx480812 21 ?? xx1 0 03 1 ?x0, 21 ?xx約束條件 50: 211 ?? xxl480812: 212 ?? xxl1003: 13 ?xl0:,0: 2514 ?? xlxl21 6472 xxzM a x ?? Z=0 Z=2400 Z=3360 c 從圖中可以看出，在 B(20,30) 點(diǎn)得到最優(yōu)解。 解法 2：軟件實(shí)現(xiàn)。 求解線性規(guī)劃有不少現(xiàn)成的數(shù)學(xué)軟件，比如用 LINDO 軟件就可以很方便地實(shí)現(xiàn)。在 開一個新文件，像書寫模型一樣。直接輸入： max 72x1+64x2 st 2） x1+x250 3） 12x1+8x2480 4） 3x1100 end 注： LINDO中已規(guī)定所有決策變量均為非負(fù)，故變量非負(fù)的條件不必輸入。輸入文件中第 1行為目標(biāo)函數(shù)， 2),3),4)是為了標(biāo)示各約束條件，便于從輸出結(jié)果中查找相應(yīng)信息；程序最后以 end 結(jié)束。 將文件存儲并命名后，選擇菜單 “ Solve” 并對提示 “ DO RANGE(SENSITIVITY)ANALYSIS? ”回答“是”，即可得到如下輸出： OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST X1 X2 ROW SLACK OR SURPLUS DUAL PRICES 2) 3) 4) NO. ITERATIONS= 2 20桶牛奶生產(chǎn) A1, 30桶生產(chǎn) A2，利潤 3360元。 原料無剩余 時間無剩余 加工能力剩余 40 三種資源 “資源” 剩余為零的約束為緊約束（有效約束） 結(jié)果解釋 OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST X1 X2 ROW SLACK OR SURPLUS DUAL PRICES 2) 3) 4) NO. ITERATIONS= 2 最優(yōu)解下“資源”增加1單位時“效益”的增量 原料增加 1單位 , 利潤增長 48 時間增加 1單位 , 利潤增長 2 加工能力增長不影響利潤 影子價格 ? 35元可買到 1桶牛奶，要買嗎？ 35 48, 應(yīng)該買！ ? 聘用臨時工人付出的工資最多每小時幾元？ 2元！ RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 X2 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 3 4 INFINITY 最優(yōu)解不變時目標(biāo)函數(shù)系數(shù)允許變化范圍 DO RANGE(SENSITIVITY) ANALYSIS? Yes x1系數(shù)范圍 (64,96) x2系數(shù)范圍 (48,72) ? A1獲利增加到 30元 /千克，應(yīng)否改變生產(chǎn)計(jì)劃 x1系數(shù)由 24 ?3=72增加 為 30?3=90，在 允許范圍內(nèi) 不變！ (約束條件不變 ) 線性規(guī)劃問題經(jīng) 典例題 ? ?? ??minjji ba1 1典例 1（運(yùn)輸問題） :設(shè)某種物資有 m 個產(chǎn)地 A1 , A2 , , Am ,產(chǎn)量分別為 a1 , a2 , , am , 有 n 個銷地 B1 , B2 , , B n , 銷量分別為 b1 , b2 , , bn 假設(shè)產(chǎn)銷是平衡的， 即有： 設(shè) cij（ i=1,2, ,m 。 j=1,2, ,n ) 為由產(chǎn)地 Ai 運(yùn)往銷地 Bj 的單位運(yùn)費(fèi)。這些數(shù)據(jù)匯總于表 中，試求總運(yùn)費(fèi)最少的運(yùn)輸方案。 銷 地 產(chǎn) 地 B1 B2 Bn 供應(yīng)量 A1 A2 : Am 需 求 量 c11 c12 c1n c21 c22 c2n : : : cm1 cm2 cmn b1 b2 bn a1 a2 : am ? ?? ??minj jiba1 1表１ .4 假設(shè) f 為總運(yùn)費(fèi)， xij 為從 Ai 運(yùn)往 Bj 的物資的數(shù)量，則這個問題的數(shù)學(xué)模型是： ?????????????????????? ???? ?),2,1。,2,1( 0 ),2,1( ),2,1( .m i n 111 1njmixnjbxmiaxtsxcfijmijijnjiijnjmiijij???? 前面討論的是產(chǎn)銷平衡的問題，而實(shí)際問題中產(chǎn)銷往往是不平衡的。對于這樣的運(yùn)輸問題，解決的辦法是把它轉(zhuǎn)化為平衡的問題來處理。 當(dāng)產(chǎn)大于銷時，即： ? ?? ??minjji ba1 1此時，運(yùn)輸問題的數(shù)學(xué)模型可表示為： ?????????????????????? ???? ?),2,1。,2,1( 0 ),2,1( ),2,1( .m i n 111 1njmixnjbxmiaxtsxcZijmijijnjiijminjijij????由于總產(chǎn)量大于總銷量，可虛擬 Bn+1 為存儲地，并設(shè) xi , n+1 是產(chǎn)地 Ai 的存儲量，于是有： 的運(yùn)輸問題：從而得到一個產(chǎn)銷平衡費(fèi)為０，所以，令由于就地存儲的單位運(yùn)總的存量為： ,2,1 ,0 ).,2,1( 1,1 1 111,1111,micbbaxniaxxxnimiminjnjininjnjiijniij????????????? ? ???????? ? ?? ?????????????????????????? ???????)1,2,1。,2,1( 0 )1,2,1( ),2,1( .m i n 111111njmixnjbxmiaxtsxcZijmijijnjiijminjijij???? 同樣，當(dāng)總銷量大于總產(chǎn)量時，只要增加一個虛擬的產(chǎn)地Am+1 , 它的產(chǎn)量 am+1 為 ? ?? ?? ??njmiijm aba1 11 可令，從假想產(chǎn)地 Am+1 到銷地 Bj 的單位運(yùn)費(fèi) cm+1,j=0 (j=1,2, ,n),同樣可以將這類問題轉(zhuǎn)化為產(chǎn)銷平衡的問題。 典例 2（下料問題） :某工廠有一批長度為 300cm 的鋼管（數(shù)量充分多），要把它們截成長度為 45cm 、80cm 、 95cm 的管料，并要求其根數(shù)比例為 5:3:2 ，來配套生產(chǎn)某種零件。問采用怎樣的方案進(jìn)行鋸割，