运筹学第二章作业参考答案要点计划

精选文档精选文档PAGE精选文档

第二章作业的参照答案

P734、将下边的线性规划问题化成标准形式

maxx1x22x3

s.t.x12x23x362x1x2x330x131x26解：将max化为min，x3用x4x5取代，则minx1x22(x4x5)s.t.x12x23(x4x5)62x1x2(x4x5)30x13x26

x4,x50

令x2x21，则

minx1x212(x4x5)s.t.x12(x21)3(x4x5)62x1(x21)(x4x5)30x130x27x4,x50

将线性不等式化成线性等式，则可得原问题的标准形式

1

minx1x22x42x51s.t.x12x23x43x5x642x1x2x4x5x74x1x83

x2x97

x1,x2,x4,x5,x6,x7,x8,x90

P735、用图解法求解以下线性规划问题：

X2minx13x2法线方向s.t.x1x220等值线6x18（1）12x22o1220X1图2.1

解：图2.1的暗影部分为此问题的可行地域。将目标函数的等值线x13x2c（c为常数）沿它的负法线方向（TT1，3）挪动到可行地域的界限上。于是交点（12，8）就是该问题的最优解，其最优值为36。

注：用图解法求解线性规划问题的步骤

①比较正确地画出可行地域；

②确立等值线及其法线方向；

③由max或min确立等值线的挪动方向，并将其挪动

到可行地域的界限上；

④得出结论。

2

P7412、对于下边的线性规划问题，以B(A2,A3,A6)为基写出对应的典式。

minx12x2x3s.t.3x1x22x3x472x14x2x5124x13x28x3x610xj0,j1,,6解：先将方程组中基变量x2,x3,x6的系数向量化成单位向量minx12x2x3s.t.5x1x31x41x554281x1x21x532425x14x47x5x63924xj0,j1,,6利用线性方程组的典式，把x2,x3用x1,x4,x5表示，再带入目标函数，则可得原问题相应

于基B(A2,A3,A6)的典式

min15x1x3x412485s.t.5xx1x1x541324851xx1x32124525x4x7xx39214456xj0,j1,,6

3

P7516、用单纯形法求解以下线性规划问题：

minz2x1x2x3

s.t.3x1x2x360

x1x22x310

(1)x1x2x320

xj0,j1,2,3注（零行元素的获取）：解：将此问题化成标准形式

minz2x1x2x3先将目标函数化成求s.t.3x1x2x3x460最小值的形式，再把所x1x22x3x510有变量移到等式左侧，x1x2x3x620xj0,j1,2,3,4,5,6常数移到等式右侧。则以x4,x5,x6为基变量，可得第一张单纯形表为

变量前的系数为零行

对应的元素。

x1x2x3x4x5x6RHSz21-10000注意单纯形表x431110060的格式！x51-1201010注：要用记号把x611-100120转轴元标出来以x1为进基变量，x5为离基变量旋转得

4

以x2为

得

所以最优

优值为

x1x2x3x4x5x6

z03-50-20x404-51-30

x11-12010

x602-30-11

x1x2x3x4x5z0010122x40011-1x11010122x20130122

RHS注：要记着在单

-20纯形表的左侧，

30用进基变量取代

离基变量

10

进基变量，x6为离基变量旋转10

x6RHS

3-352

-210

115215解为x*(15,5,0)T，最

2-35。

注：用单纯形法求解线性规划问题的步骤

Ⅰ、将问题化成标准形式；

Ⅱ、找出初始解；

Ⅲ、写出第一张单纯形表，并化成典式；

Ⅳ、判断和迭代。

①判断：<1>最优解（检验数向量0）；<2>问题无界（某个非基变量xk的检验数k0，且x在典式中的系数向量A0）kk②迭代步骤：<1>确立进基变量xk（检验数向量T中最大的正重量）；<2>确立转轴元ark（进基变量所在的这一列中的正重量与右端向量中

对应元素比值最小的）；

5

<3>确立离基变量xr（转轴元所在的这一行对应的基变量）；

<4>迭代计算（利用初等行变换，将转轴元变成1，转轴元所在的这一列其他元素所有变成0）；

<5>用进基变量xk取代离基变量xr。

minzx1x2x3x5x6s.t.3x3x5x66x22x3x410（3）x1x60x3x6x76xj0,j1,2,3,4,5,6,7解：在第三个等式两端同乘以-1，并以x5,x2,x1,x7为基变量可得其单纯形表为

x1x2x3x4x5x6x7RHSz-11-10-1100x500301106x2012-100010

注：必然先将线

性方程组和目标

函数化成典式，

再用单纯形方法

开始判断、迭代！

x110000-100将第0行x700100116的元素化为检验数可得

6

x1x2x3x4x5x6x7RHSz0001010-4x500301106x2012-100010

x110000-100x700100116因为x4410，而且的检验数x4在典式中的系数向量A4(0,1,0,0)T0，所以问题无界。

P7517、用两阶段法求解以下线性规划问题：

minz2x14x2

s.t.2x13x22

（2）x1x23

x1,x20

解：将此问题化为标准形式

minz2x14x2s.t.2x13x2x32x1x2x43x1,x2,x3,x40

增加人工变量x5,x6获取辅助问题

7

mingx5x6s.t.2x13x2x3x52x1x2x4x63x1,x2,x3,x4,x5,x60

以x5,x6为基变量，可得辅助问题的单纯形表为

x1x2x3x4x5x6RHSz-2-400000g0000-1-10x52-3-10102x6把g所-110-1013在的这一行的元素化成检验数x1x2x3x4x5x6RHS注：必然先将线z性方程组和目标-2-400000g1-2-1-1005函数化成典式，x52-3-10102才可以开始判x6-110-1013定、迭代！以x1为进基变量，x5为离基变量旋转得

8

x1x2x3x4x5x6RHSz0-7-1010211310101222x6011-1114222所以，辅助问题的最优解为x*(1,0,0,0,0,4)T，其最优值为g*40。所以，原问题没有可行解。

maxz2x14x25x36x4s.t.x14x22x38x42（4）x12x23x34x41x1,x2,x3,x40解：将此问题化成标准形式minz2x14x25x36x4s.t.x14x22x38x42x12x23x34x41x1,x2,x3,x40增加人工变量x5,x6获取辅助问题

9

mingx5x6s.t.x14x22x38x4x52x12x23x34x4x61x1,x2,x3,x4,x5,x60

以x5,x6为基变量，可得辅助问题的单纯形表为

x1x2x3x4x5x6RHSz2-45-6000g0000-1-10x514-28102x6-1234011把g所在的这一行的元素化成检验数x1x2x3x4x5x6RHSz2-45-6000g06112003x514-28102x6-1234011以x4为进基变量，x5为离基变量旋转得

10

z

g

x4

以x3为x6转得

z

g

x4

所以，辅

x1x2x3x4x5x6RHS11-1703034242304030022111110182484304011022x1x2x3x4x5x6RHS651973-1008161620000-1-10110131132232164

进基变量，x6为离基变量旋

助问题的最优解为

x3

其最优值为g

31110(0,0,0,1004,0,0)T88x，40。所以，原问题的初始解为x0(0,0,0,1)T，其第一张单纯形表为4x1x2x3x4RHS65-1003z216x411011322430100x38以x1为进基变量，x4为离基变量旋转得

11

x1x2x3x4RHSz0-660-130-31x11160328x3061123所以，原问题的最优解为x*(8,0,3,0)T，最优值为31。

P7618、写出以下线性规划问题的对偶规划：

minzx12x24x3s.t.2x13x24x322x1x26x33x13x25x35x1,x20,x3为自由变量解：先将此问题化成一般形式minzx12x24x3s.t.2x13x24x322x1x26x33x13x25x35x1,x20,x3为自由变量

所以，其对偶规划为

max213253s.t.21223131233241625341,30,2为自由变量

1

2

3

注：要先将问题化成一般形

式，再按规则写出它的对偶

问题。要记着判断对偶变量

是自由变量还是非负变量

12

P7720、给定线性规划问题

minzx1x3

s.t.x12x251x2x332x1,x2,x30记为（P）

1）用单纯形算法解P;

2）写出P的对偶问题D;

3）写出P的互补松紧条件,并利用它们解对偶D;

解：(1)把问题（P）化为标准形式minzx1x3s.t.x12x2x451x2x332x1,x2,x3,x40以x1,x3为基变量，可获取其单纯形表为:x1x2x3x4RHSz-10-100x112015x3011032把第0行化成检验行，得

13

x1x2x3x4RHS

z050182x112015x301103进基变量，x1为离基变量，旋转得以x2为2x1x2x3x4RHS5

z400

x21102依据最优1x3401

将问题（P）化为一般形式

1744152217化准则知，问题（P）的最优解为4(0,5,7)T,最优值为74x*.244minzx1x3s.t.x12x2511x2x3322x1,x2,x30所以其对偶问题（D）为max5132s.t.112101222110(3)由问题（P）的最优解为x*(0,5,7)T以及互补松紧性定律可得24

14

2101221

解得11，21.所以，对偶问题（D）的最优解为*(1,1)T，最优值为4745132.4

P7722、用对偶单纯形法解以下问题.minz2x13x24x3s.t.x12x2x33（1）2x1x23x34xi0,i1,2,3.

解：引入节余变量将原问题标准化minz2x13x24x3s.t.x12x2x3x432x1x23x3x54xi0,i1,2,3,4,5.

再将拘束条件两边同时乘以1得

minz2x13x24x3s.t.x12x2x3x432x1x23x3x54xi0,i1,2,3,4,5.以x4,x5为基变量，可得其单纯形表为

注：若问题存在一个

基本解，而且该解的

检验数向量小于等于

零，则可使用对偶单

纯形方法。特别地，

要将问题典式化

15

x1x2x3x4x5RHSz-2-3-4000x4-1-2-110-3以x5x5-21-301-4为离基变量，x1为进基变量，旋转得x1x2x3x4x5RHSz0-4-10-14x45110212-12以x4x1131为离基变量，x2为进基变量，旋转102222得x1x2x3x4x5RHSz00981285555x21212015555依据最x171211优化准则知，原问题的最优解为105555(11,2,0)T,最优值为28x*.555

注：用对偶单纯形方法求解线性规划问题的步骤：

Ⅰ、将问题化成标准形式；

Ⅱ、找出初始解；

Ⅲ、写出第一张单纯形表，并化成典式；

Ⅳ、判断和迭代。

①判断：<1>最优解（右端向量b0）；<2>没有可行解（某个br0，而且在典式中br所在的这一行内没有负重量）

16

②迭代步骤：

<1>确立离基变量xr（右端向量最小的负重量）<2>arkT确立转轴元（离基变量所在的这一行中的负重量与中对应元素比值最小的）<3>确立进基变量xk（转轴元所在的这一列对应的非基变量）<4>迭代计算（利用初等行变换，将转轴元变成1，转轴元所在的这一列其他元素全部变成0）；<5>用进基变量xk取代离基变量xr。

minz3x12x2x3s.t.x1x2x36（2）x1x34x2x33xi0,i1,2,3.解：先将原问题标准化minz3x12x2x3s.t.x1x2x3x46x1x3x54x2x3x63xi0,i1,2,3,4,5,6.在第2、3个等式的两端同乘以-1，并以x4,x5,x6为基变量，可得其单纯形表为

17

x1x2x3x4x5x6RHSz-3-2-10000x41111006x5-101010-4以x5x60-11001-3x1为进基变量，旋转为离基变量，得x1x2x3x4x5x6RHSz0-2-40-3012x40121102x110-10-104以x6为x6x1x2x3x4x5x6RHS0-11001-3离基变z量，x200-60-3-218x4为进基变量，旋转得003111-1x110-10-104x201-100-