运筹学总复习(嘉兴2课时)

运筹学总复习(嘉兴2

课时)

-CAL-FENGHAI.Network Information Technology Company.2020YEAR

基本要求

一、将线性规划化为标准型和写出相应的对偶规划； 二、用图解法求解具有两个决策变量的线性规划问题； 三、用单纯形方法；

四、整数规划与分枝定界法，0-1规划与隐枚举法，指派问题 六、求解产销平衡的运输问题和产销不平衡的运输问题； 七、动态规划与求解.

问题一、化标准型

⑴标准型的概念： ①目标函数为极大化； ②资源常数bi0； ③约束条件关系为等式； ④决策变量xi0。

例： 将下面的线性规划化为标准型 min z3x14x22x35x4

4x1x22x3x42 x1x23x3x414

2x13x2x32x42 x10,x20,x30,x4无非负

解 max zz3x14x92x35x75x8

2

4x1x92x3x7x82 x1x93x3x7x8x514

2x13x9x32x72x8x62

x1,x3,x5,x6,x7,x8,x90.

二、图解法

例 用图解法求解线性规划问题 极大化 z2x13x2

x12x28 4x1 16

 4x212 xi0,i1,2 解：最优解X(4,2),z14 三、单纯形方法

对于具有两个以上决策变量的线性规划问题，采用单纯形方法进行求解。具体过程是：

⑴建立单纯形表，在单纯形表中，务必使基变量的价值系数为零，则检验数行是价值系数行的相反数；

⑵若检验数0,则当前解为最优解（当前解是基变量取相应的资源常数，非基变量取为零）；若存在检验数0，则要进行相应的换基，即：迭代； ⑶①进基：进基变量 xs： smin{ii0}

②出基：出基变量xk为第r行所对应的基变量，r由下面的关系确定

brbiminais0

arsais ③以主元ars进行迭代，目标：主元化为1，该列的其余元化为零。

3

⑷再一次判定当前解是否为最优解。

建立对偶规划的要点

⑴原规划是极大化，则对偶规划是极小化；

⑵原规划的价值系数是对偶规划中的资源常数；

⑶原规划与对偶规划的约束条件系数矩阵为矩阵的转置关系；

⑷原规划中的第i个决策变量非正，则对偶规划中的第i个约束条件取反向不等式；

⑸原规划中的第i个决策变量无非负，则对偶规划中的第i个约束条件为等式.

例 求下面问题的对偶规划

极大化 z3x12x25x37x4

2x13x22x37x42 x1 +2x32x43

2x1x24x3x48 x10,x20,x30,x4无非负。 解 极小化 w2y13y28y3

2y1y22y333yy32 1 2y12y24y357y2yy7231 y10,y20,y30

对偶单纯形法

4

基本要求：检验数0；资源常数存在负值。 解法：

1．列出对偶单纯形表；

2．将基变量在目标函数中系数化为零，检验数为新目标函数中系数的相反数；

3．判断，若0,b0，则当前解为最优解；

若0,且b中存在负项，则进行迭代，确定出基和进基变量；

为0。

例：用单纯性方法求解下面线性规划问题：

minbibi0,xk为第r行对应的变量； 出基：记br 进基：sarsiminari0，xs为进基变量；

ari 以ars为主元进行迭代。目标：将主元化为1，该列的其余元化

max z10x16x24x3

x1x2x3100,10x14x25x3600, 

2x12x26x3300, xi0,i1,2,3.解 由单纯形方法得

5

xcx4x5x6x1101x26142635256521000x34156412125156183x401000100053232103Tx5001001101101511616023x60001000100010406018060020031003 100220031006003001021001000100x4x1x6x2x1x62200100200,,0,z. 即,原问题的最优解为X333

例 用分枝定界法求解整数规划

max zx1x2

951xx,1214142xx1,

123x1,x20且为整数.用隐枚举法求解0-1规划

6

max z4x13x22x3

2x15x23x34,4x1x23x33, xx1,32 xi01,i1,2,3.解 增加过滤条件：4x13x22x34，则原规划改为

max z4x13x22x3

4x13x22x34,2x5x3x4,1234x1x23x33, x2x31, xi01,i1,2,3.

解向量 条件1 F F F T T T T T 条件2 T T F T T 条件3 T T T T T 条件4 T F F T T 函数值 5 7 9 0,0,0 0,0,1 0,1,0 0,1,1 1,0,0 1,0,1 1,1,0 1,1,1

所以，最优方案为1,1,1，最优值为9.

指派问题的求解：

7

1.mn的指派问题的最小值解的求解方法： ⑴用行缩减和列缩减在每行和每列至少产生一个零； ⑵用划线法判定是否有n个的零；

⑶如果有n个的零，则可以求出最小值解；

⑷若没有n个的零，重新进行调整，以求出n个的零。

2.mn的指派问题的最小值解的求解方法：设置虚拟变量，其价值系数取为零。

3.指派问题中的最大值求解。

例：求下面指派问题的最小值解：

128 715479171410979666121412

66107106解：

79795020296662300017121412  010575 14661098004107106063627020243000  08353

11800404140

故最优解为：x12x24x31x43x551，最优解值为

12871Y7676632。

8

例：求下面指派问题的最小值及最大值解：

1519C26191821242151341041415232218,C. 914161317161921231778119例：求下面指派问题的最大值解：

7578

9109669108 88运输问题（产销平衡）的求解方法：表上作业法 1.用最小元素法求初始解；

2.用位势法求出当前解所对应的位势：若xij为基变量，则行位势和列位势满足关系

cijuivj

3.用位势法计算非基变量的影响系数：若xij为非基变量，则影响系数与行位势和列位势满足关系

ijcijuivj

4.最优解的判定：若影响系数ij0则当前解为最优解；否则通过解的调整求出最优解； 5.解的调整：

minijij0, ⑴记：st 9

所对应的非基变量，以xst为当前变量，构造闭回路； ⑵令xst为st⑶在闭回路上确定最大调整量； ⑷求出新解

6.重新判定当前解是否为最优解。

产销不平衡的运输问题的求解方法：设置虚拟产地或销地以达到产销平衡.

例 求下面运输问题的最小值解：

1 2 3

解：由最小元素法得到初始解： u1=0 u2=-1

1 3 3 1 7 2 11 9 4 6 3 3 2 10 5 4 10 3 5 6 7 4 9 1 2 v1=2 1 3 1 v2=9 9 11 9 10

v3=3 3 4 3 2 v4=10 4 10 3 3 7 4 3 u3=-5 3 7 3 6 4 6 1 10 5 3 5 6 9 则：111,122,221,246,3110,3312，最小值为-6，

非基变量为x24，闭回路x24:x24为1，得新解：

x23x13x14x24，最大调整量

x135,x142,x213,x241,x326,x343，

重新计算位势及影响系数，得下表： u1=0 u2=-7 u3=-5 1 2 3 3 v1=8 1 3 1 7 3 6 v2=9 2 11 9 4 6 5 v3=3 3 3 2 10 5 2 1 3 v4=10 4 10 3 5 6 7 4 9 115,122,227,236,314,3312，最小值为-5，非基

变量为x11，闭回路x11:x11x14得新解：

x24x21x11，最大调整为2，

x112,x135,x211,x243,x326,x343

重新计算位势及影响系数，得下表： u1=0 u2=-2

1 2 2 v1=3 1 3 1 v2=4 2 11 9 11

v3=3 3 5 3 2 v4=5 4 10 3 7 4 1 u3=0 3 7 3 6 4 6 10 5 3 3 5 6 9 127,145,227,231,314,337，此时，ij0，故

当前解为最优解。最优解值为：

Y32351133465370。

产销不平衡的运输问题：对产销不平衡的运输问题，求解的基本方法是设置虚拟变量，其单位运输成本为0，从中求出最优解。

例：求下面运输问题的最小运费解：

1 2 3

例: 求解运输问题

1 2 3 4

60 1 3 7 2 M 40 2 2 5 5 M 20 3 7 2 4 M 25 4 6 3 5 M 50 60 25 10 145 2 1 2 10 7 3 2 11 3 8 4 3 3 5 1 6 4 4 9 2 5 0 0 0 4 7 5 7 19 12

例：最短路问题：求下面从A到E的最短线路和最短距离： 解：

k4:f4(D1)30,f4(D2)40

k3:f3(C1)min{d(C1,D1)f(D1),d(C1,D2)f(D2)}

min{1030,4040}40

f3(C2)min{d(C2,D1)f(D1),d(C2,D2)f(D2)}

min{6030,3040}70

f3(C3)min{d(C3,D1)f(D1),d(C3,D2)f(D2)}

min{3030,3040}60；

所以：f3(C1)40,C1D1E,f3(C2)70,C2D2E

f3(C3)60,C3D1E

k2:f2(B1)min{d(B1,C1)f3(C1),d(B1,C2)f3(C2) d(B1,C3)f3(C3)}min{7040,4070,5060}

110

f2(B2)min{d(B2,C1)f3(C1),d(B2,C2)f3(C2) d(B2,C3)f3(C3)}min{3040,2070,4060}70 f2(B3)min{d(B3,C1)f3(C1),d(B3,C2)f3(C2)

13

d(B3,C3)f3(C3)}min{4040,1070,5060}80

所以：

f2(B1)110,B1C1D1E,f2(B2)70,B2C1D1E f3(B3)80,B3C1D1E

k1:f1(A)min{d(A,B1)f2(B1),d(A,B2)f2(B2) d(A,B3)f2(B3)}min{20110,4070,3080}110,

AB2C1D1E。

例：设有某种肥料共6个单位，准备给4块粮田用，其每块粮田施肥数量与增产粮食的关系如下表所示。试求对每块田施多少单位重量的肥料，才能使总的粮食增产最多。

施 肥 1 1 2 3 4 5 6

14

粮 田 2 3 25 45 67 87 106 128 4 28 47 65 74 80 85 解：

表1，对两块田的施肥：

1 2 3 4 5 6 0 1 2 0+45 20+45 42+45 60+45 75+45 3 0+57 20+57 42+57 60+57 4 0+65 20+65 42+65

表2，对三块田的施肥：

1 2 3 4 5 6 0 25+0 1 0+18 2 25+39 45+39 67+39 87+39 3 0+61 25+61 45+61 67+61 4 0+78 25+78 45+78 5 0+90 25+90 6 0+95 收益 25 45 67 87 106 128 1 0 1 2 2 2 2 2 1 1 1 2 1 1 3 0 0 0 0 2 3 5 0+70 20+70 6 0+73 收益 25 45 67 87 105 120 田1 0 1 2 2 3 4 田2 1 1 1 2 2 2 20+0 0+25 42+0 60+0 75+0 85+0 90+0 20+25 42+25 60+25 75+25 85+25 45+0 25+18 0+39 67+0 45+18 87+0 67+18 105+0 120+0 87+18 105+18 表3，对四块田的施肥：

0 1 2 3 4 5 6 收益 1 2 3 4 15

6 128+0 106+28 87+47 67+65 45+78 25+80 0+85 134 2 2 0 2

所以最优解为2，2，0，2，最大增产量为134。

16