運(yùn)籌學(xué)復(fù)習(xí)

1、運(yùn)籌學(xué)復(fù)習(xí),1、線性規(guī)劃的基本概念2、單純形法和對(duì)偶單純形法3、對(duì)偶線性規(guī)劃4、運(yùn)輸問題5、目標(biāo)規(guī)劃6、整數(shù)規(guī)劃7、網(wǎng)絡(luò)最大流問題8、網(wǎng)絡(luò)最短路徑問題,第一章 線性規(guī)劃模型和單純形法,線性規(guī)劃問題一般模型目標(biāo)函數(shù) ：max，min約束條件：≥,=,≤變量符號(hào)：≥0, unr, ≤0線性規(guī)劃的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：min約束條件：=變量符號(hào)：≥0,非標(biāo)準(zhǔn)形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式 極大化目標(biāo)函數(shù)轉(zhuǎn)化為極小化：

2、目標(biāo)函數(shù)系數(shù)變號(hào) 約束條件是不等式轉(zhuǎn)化為等式：“≤”約束 加上松弛變量 “≥”約束 減去松弛變量 變量沒有符號(hào)限制轉(zhuǎn)化為變量非負(fù)：沒有符號(hào)限制的變量用兩個(gè)非負(fù)變量的差表示例如:max z=3x1+4x2-2x3+5x4s.t 4x1-x2+2x3-x4=4 x1+x2+3x3-x4≤14 -2x1+3x2-x3+2x4≥3x1≥0,x2≥2,x

3、3≤0,x4:unr,線性規(guī)劃的圖解,畫約束直線確定滿足約束條件的半平面所有半平面的交集—凸多邊形—線性規(guī)劃的可行域畫兩條目標(biāo)函數(shù)等值線確定目標(biāo)函數(shù)優(yōu)化的方向平行移動(dòng)目標(biāo)函數(shù)等值線得到線性規(guī)劃的最優(yōu)解,線性規(guī)劃問題的概念基：設(shè)標(biāo)準(zhǔn)形式的LP問題的約束方程組的秩為M，B是系數(shù)矩陣A中的M階滿秩子矩陣，則稱B是該LP問題的一個(gè)基?；兞浚築中的每一個(gè)列向量成為基向量，對(duì)應(yīng)的變量為基變量，共有M個(gè)。非基變量：B以外的列向量稱

4、為非基向量，對(duì)應(yīng)變量成為非基變量，共有N-M個(gè)。基礎(chǔ)解：對(duì)應(yīng)基B，令所有的非基變量為零，求解約束方程組AX=b，可惟一得出基變量的一組值，這樣得到的N個(gè)變量的一組解成為一個(gè)“基礎(chǔ)解”?；A(chǔ)可行解：如果一個(gè)基礎(chǔ)解中的所有變量都大于或等于0，則稱這個(gè)基礎(chǔ)解為“基礎(chǔ)可行解”。退化解：基解中的非零分量的個(gè)數(shù)小于M個(gè)時(shí)，即某個(gè)基變量為零時(shí)，此時(shí)為退化解。線性規(guī)劃的基本定理 線性規(guī)劃的基礎(chǔ)可行解就是可行域的極點(diǎn)。,,線性規(guī)

5、劃的基本概念,min z=x1+2x2s.t. x1+x2 ≥ 4(1) -x1+x2≥2(2) x2 ≤5(3) x1, x2 ≥0,引進(jìn)松弛變量x3, x4, x5min z=x1+2x2s.t. x1+x2+x3 =4 -x1+x2 -x4=2 x2

6、 +x5=5 x1, x2 x3, x4, x5≥0,基礎(chǔ)解,O,A,B,C,D,E,F,G,B,,E,F,四邊形B E F G,基礎(chǔ)可行解,可行域,目標(biāo)函數(shù)等值線….,最優(yōu)解,,,,B,5,G,A不是可行解，是由于變量（ ）< 0。C不是可行解，是由于變量（ ）< 0。滿足 x1，x2，x5≥0， x3 ,x4≤0 的區(qū)域

7、是（ ）。滿足 x1，x2，x4，x5≥0，x3≤0 的區(qū)域是（ ）。,A點(diǎn)對(duì)應(yīng)的解，基變量為（ ），非基變量為（ ）。F點(diǎn)對(duì)應(yīng)的解，基變量為（ ），非基變量為（ ）。G點(diǎn)對(duì)應(yīng)的解，基變量為（ ），非基變量為（ ）。,x1 x4 x5,x2 x

8、3 x4,x1 x2 x3,x2 x3,x1 x5,x4 x5,x4,x3,OABC,BCE,,,,,,,O,A,B,C,D,F,G,E,4,1,2,3,4,1,2,3,,,,,,,,,,,x1,x2,x3=0,x4=0,x2=0,x1=0,x5=0,從O點(diǎn)到C點(diǎn)的單純形疊代，進(jìn)基變量為（ ），離基變量為（ ）。從C點(diǎn)到B點(diǎn)的單純形疊代，進(jìn)基變量為（ ），離基變量為（ ）。從B點(diǎn)到E點(diǎn)的單純形

9、疊代，進(jìn)基變量為（ ），離基變量為（ ）。在B點(diǎn)上,對(duì)偶變量(w1,w2,w3,w4,w5)中大于零的變量是( ), 小于零的變量是( ), 等于零的變量( ),,,,x2,x4,x1,x3,x4,x1,單純形表單純形表的結(jié)構(gòu) 基變量在目標(biāo)函數(shù)中的系數(shù)等于0，基變量在約束條件中的系數(shù)是一個(gè)單位矩陣單純形表的運(yùn)算Step 0 獲得一個(gè)初始的單純形表，確定基變量和非基變量

10、Step 1 檢查基變量在目標(biāo)函數(shù)中的系數(shù)是否等于0，在約束條件中的系數(shù)是否是一個(gè)單位矩陣Step 2 如果表中非基變量在目標(biāo)函數(shù)中的系數(shù)全為負(fù)數(shù)，則已得到最優(yōu)解。停止。否則選擇系數(shù)為正數(shù)且絕對(duì)值最大的變量進(jìn)基。Step 3 如果進(jìn)基變量在約束條件中的系數(shù)全為負(fù)數(shù)或0，可行域開放，目標(biāo)函數(shù)無界。停止。否則選取右邊常數(shù)和正的系數(shù)的最小比值，對(duì)應(yīng)的基變量離基。Step 4 確定進(jìn)基變量的列和離基變量的行交叉的元素為“主元”，對(duì)單純形

11、表進(jìn)行行變換，使主元變?yōu)?，主元所在列的其他元素變?yōu)?。將離基的基變量的位置用進(jìn)基的非基變量代替。轉(zhuǎn)Step 1。,單純形法和對(duì)偶單純形法,單純形法適用的問題約束條件全部為≤，右邊常數(shù)全部為非負(fù)，對(duì)目標(biāo)函數(shù)的系數(shù)沒有要求。對(duì)偶單純形法應(yīng)用的條件約束條件中至少有一個(gè)是≥，相應(yīng)的右邊常數(shù)為非負(fù)，目標(biāo)函數(shù)系數(shù)全部為非負(fù)。,,min z=3x1-2x2s.t. x1+2x2≤12 2x1+ x2≤18 x1

12、,x2≥0,min z=3x1+2x2s.t. x1+2x2≥12 2x1+ x2≤18 x1,x2≥0,單純形表,min z=3x1-2x2s.t. x1+2x2≤12 2x1+ x2≤18 x1,x2≥0,x2進(jìn)基，x3離基,min z=3x1-2x2s.t. x1+2x2+x3 =12 2x1+ x2 +x4 =18

13、 x1,x2,x3,x4≥0,最優(yōu)解為：(x1, x2, x3, x4)=(0,6,0,12)，min z=-12,,min z=3x1+2x2s.t. x1+2x2-x3 =12 2x2+ x2 -x4 =18 x1, x2, x3, x4≥0,對(duì)偶單純形法的例子,min z=3x1+2x2s.t. x1+2x2≥12 2x1+ x2≥18 x1,x2

14、≥0,,,,,9,x4=0,6,18,12,x1,x2,,,,,,最優(yōu)解（x1,x2,x3,x4）=（8,2,0,0）,x3=0,x1=0,x2=0,約束兩邊同乘以-1,,,x4離基，x1進(jìn)基。第二個(gè)約束兩邊同除以-2，得到,,x3離基，x2進(jìn)基,,消去主元所在列的其他元素，得到,,,第一個(gè)約束兩邊同除以-3，得到,,,,消去主元所在列的其他元素，得到,,原始問題的最優(yōu)解為(x1,x2,x3,x4)=(8,2,0,0)，min z=28

15、對(duì)偶問題的最優(yōu)解為(w1,w2,w3,w4)=(1/3,4/3,0,0)max y=28,將主元所在行乘以2，得到,,,,,,9,0,6,18,12,,,,,x1,x2,,,,,,,,單純形疊代的過程如下圖所示,x3=0,x4=0,x1=0,x2=0,人工變量法如果約束條件全為“≤”，且右邊常數(shù)全為非負(fù)，則引進(jìn)的松弛變量就可以作為初始的基變量，得到一個(gè)初始的基礎(chǔ)可行解。如果約束條件有“≥”，右邊常數(shù)全為非負(fù)，則需要引進(jìn)人工變量，

16、建立輔助問題。大M法的步驟引進(jìn)松弛變量，使約束條件全為等式。引進(jìn)人工變量，令人工變量在目標(biāo)函數(shù)中的系數(shù)為大M （任意大的正數(shù)）用單純形法求解，得到原問題的最優(yōu)解。,兩階段法的步驟引進(jìn)松弛變量，使約束條件全為等式。引進(jìn)人工變量，建立輔助問題。輔助問題的目標(biāo)函數(shù)為各人工變量之和（僅含人工變量）。用人工變量作為輔助問題的初始基變量，用單純形法求解輔助問題，得到輔助問題的最優(yōu)解和最優(yōu)解的目標(biāo)函數(shù)值。如果輔助問題最優(yōu)解的目標(biāo)函數(shù)

17、值大于0，原問題可行域?yàn)榭占?，無可行解。如果輔助問題最優(yōu)解的目標(biāo)函數(shù)值等于0，輔助問題的最優(yōu)解是原問題的一個(gè)可行解。將第一階段得到的最終表除去人工變量，將目標(biāo)函數(shù)行的系數(shù)換原問題的目標(biāo)函數(shù)系數(shù)，作為第二階段計(jì)算的初始表，用單純形法求解，得到原問題的最優(yōu)解。,Max z=4x1+5x2+x3S.t 3x1+2x2+x3≥18 2x1+x2 ≤ 4 x1+x2-x3 =5

18、 X1,x2,x3 ≥0,線形規(guī)劃問題的應(yīng)用,某車間有一批長(zhǎng)度為180cm的鋼管,且數(shù)量充足.為制造零件的需要,要將其截成三種不同長(zhǎng)度的管料,分別為72cm,52cm,35cm.生產(chǎn)任務(wù)規(guī)定這三種不同的需要量分別不少于100,150和100根.問如何下料才能使消耗的鋼管數(shù)量最少?試建立此問題的線形規(guī)劃模型.,第二章 對(duì)偶理論和靈敏度分析,對(duì)偶的定義原始問題： 目標(biāo)函數(shù)極大化 約束條件全為≤ 變量全為非

19、負(fù)對(duì)偶問題： 目標(biāo)函數(shù)極小化 約束條件全為≥ 變量全為非負(fù),對(duì)偶問題Min W=bTys.t. ATy ≥ Cy ≥0,原始問題Max z=CTXs.t.AX ≤ bX ≥0,原始問題（prime)與對(duì)偶問題之間的關(guān)系,極小化問題 （min) 極大化問題 （max) 變量 Xj ≥0 約束

20、∑aijwj ≤ bi Xj :unr ∑aijwj =bi Xj ≤ 0 ∑aijwj ≥ bi約束 ∑aijxj ≥ bi 變量 wj ≥0 ∑aijxj = bi

21、 wj: unr ∑aijxj ≤ bi wj ≤ 0,,,,,,,對(duì)偶問題的形成,min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12

22、 2x1+x2+2x3 8 x1+3x2-x3 15,max w=6y1+12y2+8y3+15y4s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0,≤,≥,=,≥,unr,≤,≥,≥

23、,=,≤,≥,x1≥0,x2≤0,x3: unr,其他形式問題的對(duì)偶,,,,原始——對(duì)偶關(guān)系原始問題和對(duì)偶問題可行解目標(biāo)函數(shù)之間的關(guān)系z(mì)=CTX≥yTAX ≥bTy=w 原始問題任何一個(gè)可行解的目標(biāo)函數(shù)值不小于對(duì)偶問題任何一個(gè)可行解的目標(biāo)函數(shù)值原始問題和對(duì)偶問題最優(yōu)解的目標(biāo)函數(shù)值之間的關(guān)系z(mì)=CTX＝y(tǒng)TAX ＝bTy=w 如果原始問題和對(duì)偶問題都有最優(yōu)解，它們的目標(biāo)函數(shù)值相等原始問題和對(duì)偶

24、問題最優(yōu)解之間的互補(bǔ)松弛關(guān)系向量形式：XTYs=0YTXs=0分量形式：xjym+j=0yixn+i=0 原始問題第j個(gè)變量和對(duì)偶問題的第j個(gè)松弛變量中至少有一個(gè)是0；對(duì)偶問題的第i個(gè)變量和原始問題的第i個(gè)松弛變量之間至少有一個(gè)是0。,,,,,,,,,,,y1 yi ym vm+1 vm+j vn+m,x1 xj

25、 xn un+1 un+i un+m,對(duì)偶問題的變量 對(duì)偶問題的松弛變量,原始問題的變量 原始問題的松弛變量,xjvm+j=0yiun+i=0(i=1,2,…,m; j=1,2,…,n)在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于0,,,,max z=3x1+4x2-x3s.t. 4x1+2x2+5x3≤38 -x1+3x2- x3≥18 2x1-

26、 x2+3x3≤26 3x1+ x2- 2x3 ≥10 x1, x2, x3≥0,min w=38y1+18y2+26y3+10y4s.t. 4y1- y2+2y3+3y4 ≥3 2y1+3y2- y3+ y4 ≥4 5y1- y2+3y3-2y4 ≥-1y1≥0,y2≤0,y3≥0,y4≤0,| － 變量 － | － 松弛變量 － |(x1, x2,

27、 x3, x4, x5, x6, x7)( 0, 19, 0, 0, 39, 45, 9 ),( 2, 0, 0, 0, 5, 0, 11)(y1, y2, y3, y4, y5, y6, y7)| － 變量 － |－松弛變量－|,,,,,,,,互補(bǔ)松弛關(guān)系,+x4 =38,-x5 =18,+x6 =26,-

28、x7=10,x4, x5, x6, x7 ≥0,-y5 = 3,-y6 =4,-y7 =-1,,y5,y6,y7≥0,原始問題,對(duì)偶問題,原始問題的每一個(gè)變量和對(duì)偶問題相應(yīng)的松弛變量組成互補(bǔ)松弛對(duì)，每一對(duì)變量中至少有一個(gè)等于0。,對(duì)偶問題的每一個(gè)變量和原始問題相應(yīng)的松弛變量組成互補(bǔ)松弛對(duì)，每一對(duì)變量中至少有一個(gè)等于0。,對(duì)偶的性質(zhì)對(duì)偶的對(duì)偶是原始問題：對(duì)偶是相對(duì)的，一對(duì)

29、原始——對(duì)偶問題中的任何一個(gè)都可以作為原始問題，而另一個(gè)則是對(duì)偶問題原始問題約束條件的性質(zhì)影響對(duì)偶問題變量的性質(zhì)原始問題變量的性質(zhì)影響對(duì)偶問題約束條件的性質(zhì)原始——對(duì)偶問題最優(yōu)解的條件原始可行條件：X, Xs是原始問題的可行解對(duì)偶可行條件：Y, Ys是對(duì)偶問題的可行解互補(bǔ)松弛條件： XTYs=0 WTYs=0,單純形表的結(jié)構(gòu)和對(duì)偶問題的關(guān)系設(shè)原始問題為：min z=CTX引進(jìn)松弛變量min z=CTXs.t.

30、 AX≥bs.t. AX-Xs=b X≥0 X, Xs ≥0單純形表中x1，x2，x3，x4為原始問題的變量，x5，x6，x7為原始問題的松弛變量。對(duì)偶問題的變量和松弛變量為,對(duì)偶單純形法對(duì)偶單純形法用來求解對(duì)偶可行，原始不可行的問題。對(duì)偶單純形法的步驟Step 0：從一個(gè)對(duì)偶可行、原始不可行的解出發(fā)，確定基變量、非基變量，列出單純形表，轉(zhuǎn)Step 1。Step 1：如果右邊常數(shù)全為非負(fù)

31、，得到最優(yōu)解，算法終止。否則，選擇右邊常數(shù)為負(fù)數(shù)，絕對(duì)值最大的基變量離基，轉(zhuǎn)Step 2。Step 2：在離基變量行中，選擇系數(shù)為負(fù)數(shù)，并且和目標(biāo)函數(shù)行的比值最小的元素作為主元，確定進(jìn)基變量Step 3：對(duì)單純形表進(jìn)行行變換，使主元為1，主元所在列的其他元素為0，轉(zhuǎn)Step 1。,對(duì)偶的經(jīng)濟(jì)解釋影子價(jià)格的性質(zhì),影子價(jià)格越大，說明這種資源越是相對(duì)緊缺影子價(jià)格越小，說明這種資源相對(duì)不緊缺如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的

32、影子價(jià)格一定等于0對(duì)偶問題是資源定價(jià)問題，對(duì)偶問題的最優(yōu)解y、y2、...、ym稱為m種資源的影子價(jià)格（Shadow Price）,,,,種資源的邊際利潤(rùn),第,種資源的增量,第,最大利潤(rùn)的增量,i,i,b,z,y,i,o,o,i,=,=,D,D,=,m,m,i,i,2,2,1,1,y,b,y,b,y,b,y,b,w,z,+,+,+,+,+,=,=,L,L,i,i,y,b,z,D,=,D,互補(bǔ)松弛關(guān)系的經(jīng)濟(jì)解釋,wixn+i=0,如果w

33、i>0，則xn+i=0,如果xn+i>0，則wi=0,邊際利潤(rùn)大于0的資源，在最優(yōu)生產(chǎn)計(jì)劃條件下沒有剩余,wm+jxj=0,如果wm+j>0，則xj=0,如果xj>0，則wm+j=0,最優(yōu)生產(chǎn)計(jì)劃條件下有剩余的資源，其邊際利潤(rùn)等于0,差額成本大于0（機(jī)會(huì)成本大于利潤(rùn)）的產(chǎn)品，不安排生產(chǎn),安排生產(chǎn)的產(chǎn)品，差額成本等于0（機(jī)會(huì)成本等于利潤(rùn)）,靈敏度分析 主要分析當(dāng)所給問題數(shù)據(jù)改變時(shí)，原有解的可行性和最有優(yōu)性

34、有何變化。目標(biāo)函數(shù)中系數(shù)的變化約束條件右端常數(shù)的變化約束條件左端系數(shù)的變化引入新的變量引入新的約束,利用對(duì)偶單純形法求解,Min z=4x1+6x2+18x3S.t x1+ 3x3 ≥3 x2+2x3 ≥5 x1,x2,x3≥ 0,第三章 運(yùn)輸問題,運(yùn)輸問題的模型,運(yùn)輸問題的表格表示,運(yùn)輸表中一個(gè)基必須具備的特點(diǎn)1、一個(gè)基應(yīng)占表中的m+n-1格2、構(gòu)成基的同行同列格子

35、不能構(gòu)成閉回路3、一個(gè)基在表中所占的格子應(yīng)包括表的每行和每列,初始基可行解的求法西北角法最小元素法,最優(yōu)解的獲得,運(yùn)輸問題,用最小元素法得到一個(gè)初始基礎(chǔ)可行解,125,85,180,30,35,75,-7,求非基變量x11的檢驗(yàn)數(shù),125,85,180,30,35,75,-7,-8,求非基變量x14的檢驗(yàn)數(shù),125,85,180,30,35,75,-7,-8,-4,求非基變量x22的檢驗(yàn)數(shù),125,85,180,30,35,75,

36、-7,-8,-6,-7,求非基變量x31的檢驗(yàn)數(shù),125,85,180,30,35,75,-7,-8,-4,-7,+1,求非基變量x32的檢驗(yàn)數(shù),125,85,180,30,35,75,-7,-8,-4,-7,+1,+4,求非基變量x33的檢驗(yàn)數(shù),125,85,180,30,35,75,-7,-8,-6,-7,+1,+4,x33=75進(jìn)基，x23=0離基，x24=30+75=105，x34=180-75=105,確定進(jìn)基變量和離基變量,

37、125,85,105,35,,-3,,,,,,,求非基變量x11的檢驗(yàn)數(shù),125,85,105,35,,-3,-4,,,,,求非基變量x14的檢驗(yàn)數(shù),125,85,105,35,,-3,-4,-8,,,,,,,求非基變量x22的檢驗(yàn)數(shù),125,85,105,35,-6,-4,-4,-8,,,,,求非基變量x23的檢驗(yàn)數(shù),125,85,105,35,,-5,-4,-4,-7,-8,,,,,求非基變量x31的檢驗(yàn)數(shù),125,85,105,3

38、5,,-5,-4,-4,-7,-3,-8,,,,,得到最優(yōu)解：x12=85, x13=35, x21=125, x24=105, x33=75, x34=105 min z = 3660,求非基變量x32的檢驗(yàn)數(shù),,不平衡運(yùn)輸問題發(fā)大于收，則虛設(shè)收地，運(yùn)價(jià)為零發(fā)小于收，則虛設(shè)發(fā)地，運(yùn)價(jià)為零靈敏度分析基變量的運(yùn)價(jià)調(diào)整非基變量的運(yùn)價(jià)調(diào)整,物流配送案例,騰飛電子儀器廠在大連和廣州有兩個(gè)分廠生產(chǎn)同一種儀器 。大連分廠每月生產(chǎn)4

39、00臺(tái)．廣州分廠每月生產(chǎn)600臺(tái)。該公司在上海和天津有兩個(gè)物流配送服務(wù)網(wǎng)點(diǎn)，負(fù)責(zé)對(duì)南京、濟(jì)南、南昌、青島四個(gè)城市的儀器進(jìn)行配送供應(yīng)。另外，因?yàn)榇筮B距離青島較近，公司同意大連分廠向青島直接供貨。 這些城市間的每臺(tái)儀器的運(yùn)輸費(fèi)用標(biāo)在兩個(gè)城市間的弧上，單位為百元。公司應(yīng)該如何調(diào)運(yùn)儀器可使總運(yùn)輸費(fèi)用最低?,廣州600,南昌350,天津,南京200,濟(jì)南150,大連400,青島300,上海,,,,,,,,,,,,,,2,4,4,6,3

40、,6,2,5,6,1,4,3,3,多工廠模型,一家公司有A和B兩個(gè)工廠,每個(gè)工廠生產(chǎn)兩種同樣的產(chǎn)品,一種是普通的,每件利潤(rùn)10元;一種是精制的,每件利潤(rùn)15元.兩廠采用相同的加工工藝:研磨和拋光.A廠每周的研磨能力為80小時(shí),拋光能力為60小時(shí); B廠每周的研磨能力為60小時(shí),拋光能力為75小時(shí).兩廠生產(chǎn)各類單位產(chǎn)品所需的研磨和拋光工時(shí)(以小時(shí)計(jì))如表所示.另外,每類每件產(chǎn)品都消耗4公斤的原材料,該公司每周可獲得原材料120公斤.問:應(yīng)

41、該如何制定生產(chǎn)計(jì)劃?,分析 先假定每周分配原料給A廠75公斤,B廠45公斤.設(shè)x1為A廠的普通產(chǎn)品產(chǎn)量;x2為A廠的精制產(chǎn)品產(chǎn)量;x3為B廠的普通產(chǎn)品產(chǎn)量;x4為B廠的精制產(chǎn)品產(chǎn)量.,A廠模型:Maxz=10x1+15x2S.t 4x1+4x2 ≤ 75 (原料A) 4x1+2x2 ≤ 80(研磨A) 2x1+5x2 ≤ 60(拋光A) X1,x2 ≥ 0最優(yōu)解:(11.25,7.5,利潤(rùn)

42、225)剩余20小時(shí)的研磨時(shí)間,B廠模型:Maxz=10x3+15x4S.t 4x3+4x4 ≤ 45 (原料B) 5x3+3x4 ≤ 60(研磨B) 5x3+6x4 ≤ 75(拋光B) X3,x4 ≥ 0最優(yōu)解:(11.25,3.75,利潤(rùn)168.5)剩余26.25小時(shí)的研磨時(shí)間和7.5小時(shí)的拋光工時(shí).,假設(shè)建立一個(gè)公司模型,讓模型去確定原材料的分配:Max z=10x1+15x2+

43、10x3+15x4S.t 4x1+4x2+4x3+4x4 ≤120 4x1+2x2 ≤80 2x1+5x2 ≤60 5x3+3x4 ≤60 5x3+6x4 ≤75 x1,x2,x3,x4 ≥ 0最優(yōu)解:X1=9.17,x2=8.33,x4=12.5, z=404.15,多周期動(dòng)態(tài)生產(chǎn)計(jì)劃問題,考慮某廠配套生產(chǎn)產(chǎn)品問題.今年頭四個(gè)月收到的訂單數(shù)量分別為3000,4500,35

44、00和5000件.該廠正常生產(chǎn)每月可生產(chǎn)產(chǎn)品3000件,利用加班還可生產(chǎn)1500件.正常生產(chǎn)成本為每件5000元,加班生產(chǎn)還要追加1500元的成本,庫存成本為每件每月200元.問該廠如何組織生產(chǎn)才能使生產(chǎn)成本最低?,第五章 目標(biāo)規(guī)劃,,概念偏差變量：實(shí)際值與目標(biāo)值之間差距的變量表示，通常以di+ di-表示，分別為正、負(fù)偏差變量，且有di+》0、 di- 》0， di+ di- =0 優(yōu)先因子：描述問題中目標(biāo)重要性程度的差別，一般

45、用pi表示，通常i值越小，代表的優(yōu)先程度越高。目標(biāo)約束：用來描述允許對(duì)給定目標(biāo)值有一定偏離程度的限制條件。,目標(biāo)規(guī)劃模型的特點(diǎn)1、引進(jìn)正負(fù)偏差變量 2、模型中必須有目標(biāo)約束 3、目標(biāo)函數(shù)為偏差變量的表達(dá)式 4、以優(yōu)先級(jí)因子描述目標(biāo)的重要性程度目標(biāo)規(guī)劃的解法 單純形法：按單純形法求解一搬目標(biāo)規(guī)劃問題的滿意解。求解時(shí)需按優(yōu)先級(jí)的順序進(jìn)行逐步優(yōu)化。各目標(biāo)具有相同等級(jí)的目標(biāo)規(guī)劃各目標(biāo)具有不同優(yōu)

46、先等級(jí)的目標(biāo)規(guī)劃各目標(biāo)具有賦權(quán)優(yōu)先等級(jí)的目標(biāo)規(guī)劃,第六章 整數(shù)規(guī)劃,整數(shù)規(guī)劃的基本概念變量的取值為整數(shù)的LP問題為整數(shù)規(guī)劃問題。 整數(shù)規(guī)劃的一般模型整數(shù)規(guī)劃的解法 割平面法（純整數(shù)規(guī)劃） 分支定界法,人力資源安排,某超市物流配送中心，星期六有4個(gè)裝卸工人當(dāng)班．要分別指派他們?nèi)ネ瓿?項(xiàng)不同的裝卸工作．每人做各項(xiàng)工作所取得的利潤(rùn)如下表所示．應(yīng)如何合理地指派這4人的工作，才能使配送中心獲得的利潤(rùn)最大。,,點(diǎn)與（

47、有向）邊 每一條邊和兩個(gè)節(jié)點(diǎn)關(guān)聯(lián)，一條邊可以用兩個(gè)節(jié)點(diǎn)的標(biāo)號(hào)表示（i，j）,路徑（Path） 前后相繼并且方向相同的邊序列 P={(1,2),(2,3),(3,4)},4,2,3,1,4,2,3,1,網(wǎng)絡(luò)由點(diǎn)和邊組成,第七章 網(wǎng)絡(luò)規(guī)劃,圖的基本概念,連通圖 任意兩個(gè)節(jié)點(diǎn)之間至少有一條鏈的圖稱為連通圖,2,4,3,5,1,圈(Cycle) 起點(diǎn)和終點(diǎn)重合的鏈稱為圈 ρ ={(1,2),

48、(2,4),(3,4),(1,3)} 圈中各條邊方向不一定相同,4,2,3,1,,樹(Tree) 無圈的連通圖稱為樹 樹中只與一條邊關(guān)聯(lián)的節(jié)點(diǎn)稱為懸掛節(jié)點(diǎn),回路（Circuit） 起點(diǎn)和終點(diǎn)重合的路徑稱為回路 μ={(1,2),(2,4),(4,1)} 回路中各條邊方向相同,4,2,3,1,,鏈（Chain） 前后相繼并且方向不一定相同的邊序列稱為鏈 C={(1,2),

49、(3,2),(3,4)},4,2,3,1,樹的性質(zhì),任何樹至少有一個(gè)懸掛節(jié)點(diǎn),2,4,3,5,1,2,4,3,5,1,2,4,3,5,1,,,如果樹的節(jié)點(diǎn)個(gè)數(shù)為m，則邊的個(gè)數(shù)為m-1,樹中任意兩個(gè)節(jié)點(diǎn)之間只有唯一的一條鏈,在樹的任意兩個(gè)不相鄰的節(jié)點(diǎn)之間增加一條邊，則形成唯一的圈,最小支撐樹,由網(wǎng)絡(luò)的所有節(jié)點(diǎn)（m個(gè)）和網(wǎng)絡(luò)的m-1條邊組成的樹稱為網(wǎng)絡(luò)的支撐樹，構(gòu)成支撐樹的各邊賦權(quán)之和最小的為最小支撐樹。,最小支撐樹的算法Kruskal算

50、法Prim算法最短路問題 D氏算法最短鏈問題網(wǎng)絡(luò)上的最大流問題最小割集,1,2,5,4,3,6,7,最大流問題,3,6,11,2,7,4,3,8,4,7,12,5,uij,,求從1到7的最大流,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,uij,,檢查每一條邊不飽和的方向，用 表示,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0

51、,,①→②→⑥→⑦ ?=min{?12, ?26, ? 67}=min{3,6,12}=3①→③→⑤→⑦ ?=min{?13, ?35, ? 57}=min{11,4,5}=4,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,uij,,尋找從1到7的不飽和鏈，用 表示，求出每一條不飽和鏈的間隙 ?,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x

52、=0,x=0,?=3,,?=6,?=12,?=11,?=4,?=5,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,uij,,增加不飽和鏈的流量檢查每一條邊不飽和的方向，用 表示,x=3,x=3,x=4,x=0,x=0,x=0,x=0,x=0,x=3,x=4,x=4,x=0,,f=7,f=7,尋找從1到7的不飽和鏈，用 表示，求出每一條不飽和鏈的間隙 ?,1,2,5,4,3,6,7,3,

53、6,11,2,7,4,3,8,4,7,12,5,uij,,x=3,x=3,x=4,x=0,x=0,x=0,x=0,x=0,x=3,x=4,x=4,x=0,?=7,f=7,f=7,,①→③→④→⑥→⑦?=min{?13, ?34, ? 46 , ? 67}=min{7,3,4,8}=3,?=3,?=4,?=9,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,uij,,增加不飽和鏈的流量檢查每一條邊不

54、飽和的方向，用 表示,x=3,x=3,x=7,x=0,x=0,x=3,x=3,x=0,x=6,x=4,x=4,x=0,,f=10,f=10,尋找從1到7的不飽和鏈，用 表示，求出每一條不飽和鏈的間隙 ?,,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,uij,,x=3,x=3,x=7,x=0,x=0,x=3,x=3,x=0,x=6,x=4,x=4,x=0,,f=10,f=10,①→ ③

55、→ ② →⑥→⑦?=min{?13, ?32, ? 26 , ? 67}=min{4,2,3,6}=2,?=4,?=2,?=3,?=6,增加不飽和鏈的流量檢查每一條邊不飽和的方向，用 表示,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,uij,,x=3,x=5,x=9,x=2,x=0,x=3,x=3,x=0,x=8,x=4,x=4,x=0,f=12,f=12,,,,尋找從1到7的不飽和鏈

56、,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,uij,,x=3,x=5,x=9,x=2,x=0,x=3,x=3,x=0,x=8,x=4,x=4,x=0,f=12,f=12,已不存在從1到7的不飽和鏈。獲得最大流， f=12X={1,3}，X={2,4,5,6,7}最小割集為{(1,2),(3,2),(3,4),(3,5)}，用 表示最小割集的容量為u12+u32+u34+u35=3

57、+2+3+4=12,,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,最短路徑問題,求1到8的最短路徑,,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,w1=0,X={1}min{0+2,0+6,0+3}=min{2,6,3}=2，w2=2,,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12

58、,6,w1=0,X={1,2}min{2+9,2+5,2+4,0+6,0+3}=min{11,7,6,6,3}=3，w4=3,w2=2,,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,w1=0,w2=2,X={1,2,4}min{2+9,2+5,2+4,0+6,3+7,3+6,3+10}=min{11,7,6,6,10,9,13}=5，w3=6,w4=3,,1,2,3,4,5,6

59、,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,w1=0,w2=2,X={1,2,3,4}min{2+9,2+5,6+8,3+6,3+10}=min{11,7,14,9,13}=7，w6=7,w4=3,w3=6,,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,w1=0,w2=2,X={1,2,3,4,6}min{2+9,7+4,7+11,3+10}=m

60、in{11,11,18,13}=11，w5=11,w4=3,w3=6,w6=7,,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,w1=0,w2=2,X={1,2,3,4,5,6}min{11+12,7+7,7+11,3+10}=min{23,14,18,13}=13，w7=13,w4=3,w3=6,w6=7,w5=11,,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7

61、,6,10,4,11,7,12,6,w1=0,w2=2,X={1,2,3,4,6,7}min{11+12,7+7,13+6}=min{23,14,19}=14，w8=14,w4=3,w3=6,w6=7,w5=11,w7=13,,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,w1=0,w2=2,X={1,2,3,4,6,7,8}min{11+12,7+7,13+6}=min{23,1

62、4,19}=14，w8=14,w4=3,w3=6,w6=7,w5=11,w7=13,w8=14,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,w1=0,w2=2,w4=3,w3=6,w6=7,w5=11,w7=13,w8=14,從1到8的最短路徑為14，最短路徑為1→2 →6 →8從1到其他節(jié)點(diǎn)的最短路徑如上圖紅線所示，其中到3和5的最短路徑有兩條。,一、最短路徑問題,求從A到E的最

63、短路徑,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f5(E)=0,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D1)=5,f5(E)=0

64、,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f4(D1)=5,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f

65、4(D2)=2,f5(E)=0,f3(C1)=8,f4(D1)=5,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C2)=7,f4(D1)=5,f3(C1)=8,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,1

66、1,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f3(C1)=8,f3(C2)=7,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(

67、C3)=12,f4(D1)=5,f2(B1)=20,f3(C2)=7,f3(C1)=8,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B2)=14,f3(C2)=7,f3(C1)=8,f2(B1)=21,,,,,,,

68、,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f2(B1)=21,f2(B2)=14,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,1