1、3.6 優化問題與規劃模型 與最大、最小、最長、最短等等有關的問題都是優化問題。 解決優化問題形成管理科學的數學方法： 運籌學。 運籌學主要分支： （非）線性規劃、動態規劃、圖與網絡分析、存貯學、排隊倫、對策論、決策論。6.1 線性規劃 1939年蘇聯數學家康托洛維奇發表生產組織與計劃中的數學問題 1947年美國數學家喬治.丹契克、馮.諾伊曼提出線性規劃的一般模型及理論.1. 問題例1 作物種植安排 一個農場有50畝土地, 20個勞動力, 計劃種蔬菜,棉花和水稻. 種植這三種農作物每畝地分別需要勞動力 1/2 1/3 1/4, 預計每畝產值分別為 110元, 75元, 60元. 如何規劃經營使

2、經濟效益最大. 分析：以取得最高的產值的方式達到收益最大的目標.1. 求什么？分別安排多少畝地種蔬菜、棉花、水稻？ x1 畝、 x2 畝、 x3 畝 2. 優化什么？ 產值最大 max f=10x1+75x2+60x33. 限制條件？ 田地總量 x1+x2+x3 50 勞力總數 1/2x1+1/3x2+1/4x3 20模型 i : 設決策變量：種植蔬菜 x1 畝, 棉花 x2 畝, 水稻 x3 畝，求目標函數 f=110x1+75x2+60x3在約束條件x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20 下的最大值規劃問題：求目標函數在約束條件下的最值,規劃問題包含3個組成要素:

3、 決策變量、目標函數、約束條件。當目標函數和約束條件都是決策變量的線性函數時，稱為線性規劃問題, 否則稱為非線性規劃問題。2. 線性規劃問題求解方法 稱滿足約束條件的向量為可行解,稱可行解的集合為可行域,稱使目標函數達最值的可行解為最優解.命題 1 線性規劃問題的可行解集是凸集.因為可行解集由線性不等式組的解構成。兩個變量的線性規劃問題的可行解集是平面上的凸多邊形。命題2 線性規劃問題的最優解一定在可行解集的某個極點上達到.圖解法： 解兩個變量的線性規劃問題，在平面上畫出可行域，計算目標函數在各極點處的值，經比較后，取最值點為最優解。命題3 當兩個變量的線性規劃問題的目標函數取不同的目標值時，

4、構成一族平行直線,目標值的大小描述了直線離原點的遠近。于是穿過可行域的目標直線組中最遠離(或接近)原點的直線所穿過的凸多邊形的頂點即為取的極值的極點最優解。單純形法 : 通過確定約束方程組的基本解, 并計算相應目標函數值, 在可行解集的極點中搜尋最優解. 正則模型: 決策變量: x1,x2,xn. 目標函數: z=c1x1+c2x2+cnxn. 約束條件: a11x1+a1nxnb1, am1x1+amnxnbm,模型的標準化10. 引入松弛變量將不等式約束變為等式約束. 若有 ai1x1+ainxnbi, 則引入 xn+i 0, 使得 ai1x1+ainxn+ xn+i =bi 若有 aj1

5、x1+ajnxnbj, 則引入 xn+j 0, 使得 aj1x1+ajnxn- xn+j =bj. 且有 z=c1x1+c2x2+cnxn+0xn+1+0xn+m. 20. 將目標函數的優化變為目標函數的極大化. 若求 min z, 令 z=z, 則問題變為 max z .30. 引入人工變量,使得所有變量均為非負. 若 xi 沒有非負的條件,則引入 xi 0 和 xi0, 令 xi= xi xi, 則可使得問題的全部變量均非負. 標準化模型 求變量 x1, x2, xn, max z = c1x1+ cnxn, s. t. a11x1+ a1nxn= b1, am1x1+ amnxn= bm

6、, x1 0, xn 0, 定義: 若代數方程ax=b的解向量有n-m個分量為零, 其余m個分量對應a的m個線性無關列, 則稱該解向量為方程組的一個基本解.在一個線性規劃問題中, 如果一個可行解也是約束方程組的基本解, 則稱之為基本可行解. 命題 4 一個向量 x 是線性規劃問題可行解集的一個極點, 當且僅當它是約束方程的一個基本可行解。于是尋找取得極值的凸集極點的幾何問題變成了求代數方程基本解的問題，形成了解優化問題的單純形方法，改進單純形方法等。按這些計算方法編制程序，產生了專門解優化問題的軟件 lindo、lingo 。 用matlab求解：標準的線性規劃的模型： min f=ctxs.

7、t. ax b a1x=b1 lb x ubmatlab求解程序: x,f=linprog(c,a,b,a1,b1,lb,ub)還有軟件excel 也可應用于解優化問題。3 對偶問題例1 作物種植安排 一個農場有50畝土地, 20個勞動力, 計劃種蔬菜,棉花和水稻. 種植這三種農作物每畝地分別需要勞動力 1/2 1/3 1/4, 預計每畝產值分別為 110元, 75元, 60元. 如何規劃經營使經濟效益最大. 分析：以最經濟的投入達到收益最大的目標.（或者說以直接出售土地和勞動力的方式達到收益最大的目標.）1 求什么？土地成本價格 y1 勞動力成本價格 y22. 優化什么？ 成本價格最低 mi

8、n g=50y1+20y2 3. 限制條件？蔬菜的市場價 y1+1/2y2 110棉花的市場價 y1+1/3y2 75水稻的市場價 y1+1/4y2 60模型 ii . 設決策變量: 對單位土地和對單位勞力投入成本價格分別為 y1 y2求目標函數 g=50y1+20y2在約束條件 y1+1/2y2 110 y1+1/3y2 75 y1+1/4y2 60 下的最小值.設 a 是m n 矩陣， c 是 n 1向量，b 是 m 1向量x是 n 1向量, y是1 m 向量問題: max f=ctx s.t. ax b xi0, i=1,2,n.對偶問題: min f=yb s.t. ya c yi0,

9、 i=1,2,m.對偶定理: 互為對偶的兩個線性規劃問題, 若其中一個有有窮的最優解, 則另一個也有有窮的最優解, 且最優值相等. 若兩者之一有無界的最優解, 則另一個沒有可行解模型 i ii構成對偶問題.模型 i 解得最優解(optimun solution) xopt=(30 0 20), 最大值 f(xopt)=4500模型 ii 解得最優解 yopt=(10 200), 最小值 g(yopt)=4500.模型i 給出了生產中的資源最優分配方案模型 ii 給出了生產中資源的最低估價. 進一步問：如果增加對土地和勞動力的投入，每種資源的單位投入增加會帶來多少產值？由最優解 y=(10,20

10、0) 可見, 多耕一畝地增加10元收入，多一個勞動力增加200元收入。也就是說, 此時一個勞動力的估價為200元,而一畝土地估價為10元.這種價格涉及到資源的有效利用, 它不是市場價格, 而是根據資源在生產中做出的貢獻確定的估價, 被稱為“影子價格”. 再進一步問，棉花價格提高到多少才值的生產？ 由 y1+1/3y2=10+200/3=76.675, （而其它兩個約束條件是等式）可見，只有當棉花價格提高到 76.6元時才值得生產.4 靈敏度分析當線性規劃問題中的常數發生變化(由于測量誤差或具有多個取值可能)時, 最優解是否會隨之變化?通常假定變化的常數是某參數的線性函數.討論參數取值與最優解的

11、關系的問題, 被稱為參數線性規劃. 例如, 當農作物的價格發生變化時, 生產計劃是否應馬上隨之改變? 參見線性規劃書籍將實際問題歸結為線性規劃模型是一個探索創造的過程。線性規劃模型的求解仍是計算數學的一個難題。例 2 供貨問題一家公司生產某種商品. 現有n 個客戶, 第 j 個客戶需要貨物量至少為 bj, 可在m 各不同地點設廠供貨. 在地區 i 設廠的費用為 di , 供貨能力為 hi , 向第 j 個客戶供應單位數量的貨物費用為 cij. 如何設廠與供貨使總費用最小.模型： 設決策變量： xij 為在地區 i 向第 j 個客戶供貨數量, 在地區 i 設廠，記 yi =1 , 否則 記 yi

12、 =0 求 目標函數 f= i (j cij xij + yi di )在約束條件 i xij = bj, j xij -hi yi 0, xij0, yi 0，1 下的最小值例3 鋼材截短 有一批鋼材, 每根長7.3米. 現需做100套短鋼材. 每套包括長2.9米, 2.1米,1.5米的各一根. 至少用掉多少根鋼材才能滿足需要, 并使得用料最省.分析： 可能的截法和余料第1種 7.3-(2.9 2+1.5)=0第2種 7.3-(2.9+2.1 2)=0.2第3種 7.3-(2.9+1.5 2)=1.4第4種 7.3-(2.9+2.1+1.5)=0.8第5種 7.3-(2.1 2+1.5 2)

13、=0.1第6種 7.3-(2.1 3)=1第7種 7.3-(2.1+1.5 3)=0.7第8種 7.3-(1.5 4)=1.3模型：設決策變量：按第i種方法截 xi 根鋼材。求目標函數 f=0.2x2+1.4x3+0.8x4+0.1x5+x6+0.7x7+1.3x8在約束條件 2x1+x2+x3+x4=100 2x2+x4+2x5+3x6+x7=100 x1+2x3+x4+2x5+3x7+4x8=100 xi 0 , i=1,8 下的最小值用matlab程序解得 xopt=(40, 20, 0, 0, 30, 0, 0, 0) , f (xopt )= 7 （實際上應要求xi 為正整數。這是一

14、個整數規劃問題）。 6.2 整數規劃如果要求決策變量取整數, 或部分取整數的線性規劃問題, 稱為整數規劃.例 4 . 飛船裝載問題 設有n種不同類型的科學儀器希望裝在登月飛船上, 令cj0表示每件第 j 類儀器的科學價值; aj 0表示每件第 j 類儀器的重量. 每類儀器件數不限, 但裝載件數只能是整數. 飛船總載荷不得超過數 b. 設計一種方案, 使得被裝載儀器的科學價值之和最大.建模 記 xj 為第 j 類儀器的裝載數. 求 目標函數 f= j cj xj 在約束條件 jaj xj b, xj 為正整數, 下的最大值.用分枝定界法求解整數規劃問題基本思想:反復劃分可行域并確定最優值的界限,

15、將原問題不斷地分枝為若干個子問題, 且縮小最優質的取值范圍,直到求得最優解. 例:求目標函數 f=3x1+2x2 在約束條件: 2x1+3x2 14, 2x1+x 2 9, x1 x 2為自然數下的最大值.用lindo軟件求解整數規劃max 3x1+2x2s.t.2x1+3x2=142x1+x2=9endgin x1gin x2(或者用 gin 2 代替gin x1 gin x2)6.3 0-1規劃 如果要求決策變量只取0 或 1的線性規劃問題, 稱為0-1規劃. 0-1 約束不一定是由變量的性質決定的, 更多地是由于邏輯關系引進問題的例5 背包問題 一個旅行者的背包最多只能裝 6 kg 物品

16、. 現有4 件物品的重量和價值分別為 2 kg , 3 kg, 3 kg, 4 kg, 1 元, 1.2元, 0.9元, 1.1元. 應攜帶那些物品使得攜帶物品的價值最大?建模: 記 xj為旅行者攜帶第 j 件物品的件數, 取值只能為 0 或 1.求目標函數 f=x 1 +1.2x 2 +0.9x 3 +1.1x 4 在約束條件 2x 1 +3x 2 +3x 3 +4x 4 6下的最大值. 用lingo 軟件求解0-1規劃model:max=x1+1.2*x2+0.9*x3+1.1*x4;2*x1+3*x2+3*x3+4*x4=6;int(x1);int(x2);int(x3);int(x4)

17、;end例 6 集合覆蓋問題實際問題 1 某企業有5種產品要存放, 有些不能存放在一起, 有些能存放在一起的, 由于組合不同所需費用不同. 求費用最低 的儲存方案. 實際問題 2 某航空公司在不同城市之間開辟了5 條航線, 一個航班可以飛不同的航線組合, 不同組合成本不同, 求開通所有航線且總費用最小的方案.抽象為集合覆蓋問題：設集合 s=1,2,3,4,5 有一個子集類f=1,2,1,3,5,2,4,5,3,1,4,5其中每一個元素對應一個數 cj , 稱為該元素的費用. 選 f 的一個子集使其覆蓋s , 且總費用最低.即實際問題 1中5種產品能存放在一起的各種組合為 f=1,2,1,3,5

18、,2,4,5,3,1,4,5第 i 種組合的存儲費用為 cj , 求這五種產品費用最低的儲存方案。模型: 設決策變量：設df是 s 的一個覆蓋（一種存儲方案）. 當f的第 i 個元素屬于d, （即第 i 種組合被采用）記 xi=1，否則xi=0求 目標函數 f= si cixi在約束條件 x1 +x2 + x51 x1 + x3 1 (因為第2種產品只在第1，3個組合中出現) x2 + x4 1 x3 + x6 1 x2 +x3 + x6 1 xi0，1， i=1,2, ,6, 下的最小值.6.4 多目標線性規劃目標函數 fk=c (k)t x k=1,2, , m,s.t. ax b a1x=b1 lb x ub有最優解 x (k), 記 f (k) =f(x (k)整體評價法min s=s(f