《管理運(yùn)籌學(xué)》演示(整數(shù)規(guī)劃)

1宅)線性規(guī)劃圖解法單純形表結(jié)構(gòu)線性規(guī)劃單純形法(1)最小元素法伏格爾法閉回路法位勢法閉回路調(diào)整法目標(biāo)規(guī)劃圖解法(1)目標(biāo)規(guī)劃圖解法(2)整數(shù)規(guī)劃(分枝定界法)和和線性規(guī)劃單純形法(2)圖解法與單純形法的聯(lián)系指派問題(匈牙利法)(1)使用計(jì)算機(jī)軟件包求解指派問題(匈牙利法)(2)0-1規(guī)劃(隱枚舉法)整數(shù)規(guī)劃(割平面法)典型應(yīng)用案例線性規(guī)劃單純形法(3)目標(biāo)規(guī)劃單純形法線性規(guī)劃求解幾種結(jié)果幾種常用規(guī)劃數(shù)學(xué)軟件比較動態(tài)規(guī)劃(1)動態(tài)規(guī)劃(2)最小樹問題(破圈法/避圈法)最短路問題(迪克斯拉法)(1)最大流問題(福克遜法)最小費(fèi)用最大流問題(2)對偶單純形法改進(jìn)單純形法動態(tài)

2、規(guī)劃(逆推法)(順推法)(3)分枝：如果求出的最優(yōu)解是一個(gè)非整數(shù)解，則以這個(gè)解任一分量相鄰的兩個(gè)整數(shù)點(diǎn)為邊緣將線性規(guī)劃的可行域分成兩個(gè)子區(qū)域，每個(gè)子區(qū)域就是一個(gè)分枝（或子問題）；定界：在分枝過程中，通過分枝找到更好的最優(yōu)值和整數(shù)解不斷地修改上下界，和減小上下界之間的范圍，當(dāng)上下界相同時(shí)，即得到整數(shù)最優(yōu)解。2. 定界。設(shè)整數(shù)規(guī)劃的目標(biāo)最優(yōu)值為z*，則 ，其中， 和 為整數(shù)規(guī)劃目標(biāo)值的上、下界；3. 分枝。在非整數(shù)最優(yōu)解中，任選一個(gè)不符合整數(shù)條件的變量，構(gòu)造兩個(gè)約束條件： 4. 修改上下界。方法如下：q 在各分枝中，找出目標(biāo)值最大者作為新的上界；q 從已符合整數(shù)條件的分枝中，找出目標(biāo)值最大者作為新

3、的下界。5. 比較和剪枝。比較各個(gè)分枝的目標(biāo)值，如果有小于 者，則剪掉這個(gè)分枝；否則，繼續(xù)分枝。反復(fù)進(jìn)行，當(dāng) ，得到整數(shù)最優(yōu)解 。 zzz*整數(shù),0,7020756799040max21212121xxxxxxxxz1. 先不考慮整數(shù)約束條件，求解相應(yīng)的線性規(guī)劃，有以下幾種情況： 如果線性規(guī)劃沒有可行解，則整數(shù)規(guī)劃也沒有可行解，停止計(jì)算； 如果線性規(guī)劃有最優(yōu)解，且為整數(shù)最優(yōu)解，則這個(gè)解為整數(shù)規(guī)劃的整數(shù)最優(yōu)解； 如果線性規(guī)劃有最優(yōu)解，但為非整數(shù)最優(yōu)解，則轉(zhuǎn)入下一步；zzz*zz1,rrrrbxbxz9x1+7x2=56BCx27x1+20 x2=70z = 40 x1+90 x20 Z* 356

4、9x1+7x2=56BCx27x1+20 x2=700 Z* 3560 Z* 3560 Z* 349z = 40 x1+90 x29x1+7x2=56BCx27x1+20 x2=700 Z* 3560 Z* 3560 Z* 3490 Z* 349Z下界= Z*=Z上界z = 40 x1+90 x2O)59,513(B)2,25(A對于整數(shù)規(guī)劃問題,首先不考慮整數(shù)約束,求解相應(yīng)的線性規(guī)劃問題的解,如果最優(yōu)解是一個(gè)非整數(shù)解,就,縮小線性規(guī)劃問題的可行域,繼續(xù)求解,直到求出相應(yīng)的線性規(guī)劃問題的最優(yōu)解為整數(shù)解。例：求解下列整數(shù)規(guī)劃：,0,72134246max21212121xxxxxxxxz整數(shù)42

5、1 xx154321xx1x2x1, 321xx)1 , 3(C例3：用割平面法求解整數(shù)規(guī)劃,0,431max21212121xxxxxxxxz整數(shù)0,431max432142132121xxxxxxxxxxxxz1x2x3x4xBCBXbjjc1100143x4x00-111031011100解：先不考慮整數(shù)約束，求相應(yīng)的線性規(guī)劃的最優(yōu)解，用單純形法求解，標(biāo)準(zhǔn)型和初始單純形表如下： 1x2x3x4xBCBXbjjc11003/47/41110-1/41/4013/41/400-1/2-1/21x2x-5/2經(jīng)過若干步迭代后，得到如下最優(yōu)表及最優(yōu)解：最優(yōu)解：x1=3/4 , x2=7/4 ,

6、x3= x4=0 , max z =5/2 ,顯然不符合整數(shù)條件。構(gòu)造切割方程：首先，從最優(yōu)表中任意選一非整數(shù)分量，寫出其相應(yīng)的約束條件，如：434141431xxx再將上式中的系數(shù)和常數(shù)都分解成整數(shù)和非負(fù)真分?jǐn)?shù)之和，并移項(xiàng)(整數(shù)移到左邊，分?jǐn)?shù)移到右邊)，如：)4143(434331xxxx從約束條件可以看出，由于x1和 x2為非負(fù)整數(shù),所以x3和 x4也必然為非負(fù)整數(shù)，這樣，在上式括號內(nèi)的數(shù)值則為正數(shù)，而且等式右邊必定是負(fù)數(shù)，即有，0)4143(4343xx化簡后，即得到一切割方程：3)343xx再將其作為新的約束條件，加到最優(yōu)表中(添加松弛變量 x5 )；1x2x3x4x5xBCBXbjc

7、11000j00-1/2-1/2-5/203/47/4-31101x2x5x10-1/41/4013/41/400-3-1001顯然，需要按照對偶單純形法繼續(xù)迭代，x5為換出變量， x3為換入變量，迭代結(jié)果如下：5x3x3)343xx3)343xx3)343xx3)343xx3)343xx3)343xx3)343xx3343xx1x2x3x4x5xBCBXbjc11000j000-1/3-2-1/61111101x2x3x1001/30100001-11/120-1/3111整數(shù)最優(yōu)解： x1=1 , x2=1 , x3=1 , x4= x5=0 , max z =2 1, 0,6434422

8、523max3213221321321321或xxxxxxxxxxxxxxxxz1, 0,64344223523523max3213221321321321321或xxxxxxxxxxxxxxxxxxxz)4() 3()2() 1 ()0(解：先找出一個(gè)可行解，顯然， 滿足約束條件，是一個(gè)可行解，目標(biāo)值z為3。由于 目標(biāo)函數(shù)是求最大化，所以，增加一個(gè)過濾條件為：0, 0, 1321xxx3523321xxx計(jì)算過程可列表進(jìn)行，為減少計(jì)算工作量，在表中可將目標(biāo)函數(shù)中的系數(shù) 按遞增順序排列，并結(jié)合新的目標(biāo)值改進(jìn)過濾條件。ix( 0 )( 1 )( 2 )( 3 )( 4 )0 , 0 , 0(0)

9、1 , 0 , 0(5-1101 ),(312xxx滿足條件是 ,否約束條件z 計(jì)算過程如下表:5523321xxx)0( )0( ( 1 )( 2 )( 3 )( 4 ),(312xxx約束條件滿足條件是 , 否z )0 , 1 , 0(3 )1 , 1 , 0(80211 改進(jìn)過濾條件,用 代替)0()0( 58)0( ( 1 )( 2 )( 3 )( 4 )0 , 0 , 1(-2 )1 , 1 , 1(6)1 , 0 , 1(3 )0 , 1 , 1(1 ),(312xxx約束條件滿足條件是 , 否z 8523321xxx)0( 再改進(jìn)過濾條件,用 代替)0( )0( 最優(yōu)解:1, 0

10、, 1321xxx最優(yōu)值:8z例1.設(shè)有四項(xiàng)工作A、B、C、D，需分配甲、乙、丙、丁四個(gè)人去完成，每個(gè)人只能完成一件工作，每件工作只能由一個(gè)人去完成，這四個(gè)人完成各項(xiàng)工作所需的費(fèi)用如下表所示，問如何分配工作才能使總費(fèi)用最省？人工作4679610835711884960 0 683991187471068564ijc3744350624100362412013406231002624020 ijb0010000110000100ijx最優(yōu)解:6 0302016232024w修改指派矩陣:w試求最優(yōu)解:00 00 00 0400 修改指派矩陣方法: 從每一行元素中減去該行的最小元素； 再從所得矩陣

11、的各列元素中減去該列的最小元素。v 試求最優(yōu)解方法： 從第一行開始，給只有一個(gè)0元素的行的0元素加圈，記為 ，表示代表這一行的人承擔(dān)了某一項(xiàng)任務(wù)；然后劃去0元素所在列的其它0元素，并記為，表示這一列所代表的任務(wù)已有人承擔(dān)了，不需要其他人再來承擔(dān)。 給只有一個(gè)0元素的列的0元素加圈，記為 ，然后劃去0元素所在行的其它0元素，并記為； 反復(fù)進(jìn)行，直到所有的0元素加圈和劃去為止。例2: 求下列表所示效率矩陣的指派問題的最優(yōu)解:任務(wù)人員甲乙丙丁戊1287154ABCDE7917141096126776146109691099107104106614159141217766698979712467675636040089275100000322020556360400892