運籌學(xué)復(fù)習(xí)資料ppt課件-在線瀏覽
2025-03-04 13:29本頁面
【正文】 minZ=P1 (d1 + d1+ ) + P2d2 + P3d3 2x1+x2 ≤8 10x1+12x2 +d1 d1+ =66 10x1+20x2 +d2 d2+ =100 x1+x2 +d3 d3+ =0 x1,x2 ,d1 ,d1+ ,d2 , d2+ ,d3 , d3+ ≥0 6個人完成 4項工作，由于個人和技術(shù)專長不同，他們完成 4項工作任務(wù)所獲得收益如下表： Ⅰ Ⅱ Ⅲ Ⅳ 1 3 5 4 5 2 6 7 6 8 3 8 9 8 8 4 10 10 9 11 5 12 11 10 12 6 13 12 11 13 且規(guī)定每人只能做一項工作，一項工作任務(wù)只需一人操作，試求使 總收益最大的分派方案。 標(biāo)準(zhǔn)的指派問題的收益矩陣為： ? ?3 5 4 5 0 06 7 6 8 0 08 9 8 10 0 010 10 9 11 0 012 11 10 12 0 013 12 11 13 0 0????????? ??????????ijc6611m a x??? ??目 標(biāo) 函 數(shù) ： i j i jijz c x 將其化為極小值問題 ?；∨詳?shù)字為（ cij， fij）。（ 5分） 因此，網(wǎng)絡(luò)中的可行流不是最大流，將其調(diào)整后得一新的可行流，如下圖所示（ 2分） ?再用標(biāo)號法在上圖中找增廣鏈，標(biāo)號法中斷，表明已找不出增廣鏈，故上圖中的可行流即為最大流，其流量為 5+3+5=13。 作 業(yè) 代 號 緊 前作 業(yè) 作 業(yè) 代 號 緊 前作 業(yè) A 無 H B B 無 I E , H C 無 J E , H D A , B K C , D , F , J E B L K F B M L, I , G G F , C A B C D E F G H I J K L M 1 3 9 8 7 6 5 4 2 10 1 (10分 ) 、寫出如下線性規(guī)劃問題的對偶問題，并利用弱對偶性說明 z的最大值不大于 1。? ?2 0 1 0 1 12,Yb????????????而?所以 z的最大值不大于 1。 Cj 2 5 0 0 0 基 b x1 x2 x3 x4 x5 0 5 0 x3 x2 x5 4 6 6 1 0 3 0 1 0 1 0 0 0 1/2 1 0 0 1 Cj Z 2 0 0 5/2 0 解： 再進(jìn)行一次迭代結(jié)果如下： Cj 2 5 0 0 0 基 b x1 x2 x3 x4 x5 0 5 0 x3 x2 x5 4 6 6 1 0 [3] 0 1 0 1 0 0 0 1/2 1 0 0 1 Cj Zj 2 0 0 5/2 0 0 5 2 x3 x2 x1 2 6 2 0 0 1 0 1 0 1 0 3 1/3 1/2 1/3 1/3 0 1/3 Cj Zj 0 0 0 11/6 2/3 ? ?2 6 2 0 0 TX ???最 優(yōu) 解 ， ， ， ，2(10分 )、對于線性規(guī)劃問題： 1 2 3131 2 31 2 31 2 36 4 7 3 23 2 4 .2 2 50m i n,f x x xxxx x xx x xx x x? ? ?????? ? ???? ? ? ??? ???（ 1）寫出此問題的對偶問題； ?（ 2）求出此問題和它的對偶問題的最優(yōu)解和最優(yōu)值。 13131 2 3123233 1 0 2 032 2 2 5 ( 1) 1 6 011326 2 2 5 2311 2 0 1263,Tyyxxx x xxxxxxxXz????? ? ? ??????? ? ? ????????????????? ? ?????又 為 ， 取 不 等 號 ， 即 。（ 12分）給出下列 線性規(guī)劃的最優(yōu)單純形表，其中 s s2分別為第 第 2約束方程中的松弛變量。 解 （ 1） 設(shè) b2→ b2+△ b2， 則最終表中的 b變?yōu)椋? 128= 6b B b b? ???? ??????其中 ， 8≥0， 要使原最優(yōu)基不變 ， 還應(yīng)滿足：6+△ b2≥0， 即得到 △ b2≥6， ∴ b2≥24。 習(xí)題 用對偶單純形法求解下述線性規(guī)劃問題： ?????????????0x,x,x5x2x23x3x.x18x12x4zm i n32132313211 2 31 3 42 3 51 2 3 4 5m a x 4 1 2 1 833. 2 2 5, , , , 0z x x xx x xx x xx x x x x? ? ? ? ?? ? ? ? ???? ? ? ? ??? ??解 先將問題改寫為 列出單純形表，并用對偶單純形法求解，計算步驟見表 28 cj? 4 12 18 0 0 CB 基
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1