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

1第二章作业的参考答案73P4、将下面的线性规划问题化成标准形式613032632..2max21321321321xxxxxxxxtsxxx解：将max化为min，3x用54xx代替，则0,61303)(26)(32..)(2min5421542154215421xxxxxxxxxxxxtsxxxx令122xx，则0,70303)()1(26)(3)1(2..)(21min5421542154215421xxxxxxxxxxxxtsxxxx将线性不等式化成线性等式，则可得原问题的标准形式20,,,,,,,73424332..122min98765421928175421654215421xxxxxxxxxxxxxxxxxxxxxxtsxxxx73P5、用图解法求解下列线性规划问题：（1）212620..3min212121xxxxtsxx解：图2.1的阴影部分为此问题的可行区域。将目标函数的等值线cxx213（c为常数）沿它的负法线方向T），（31移动到可行区域的边界上。于是交点T），（812就是该问题的最优解，其最优值为36。等值线20128X2oX1法线方向图2.1注：用图解法求解线性规划问题的步骤①比较准确地画出可行区域；②确定等值线及其法线方向；③由max或min确定等值线的移动方向，并将其移动到可行区域的边界上；④得出结论。374P12、对于下面的线性规划问题，以),,(632AAAB为基写出对应的典式。6,,1,0108341242723..2min63215214321321jxxxxxxxxxxxxtsxxxj解：先将方程组中基变量632,,xxx的系数向量化成单位向量6,,1,039474225341215812145..2min65415215431321jxxxxxxxxxxxxtsxxxj利用线性方程组的典式，把32,xx用541,,xxx表示，再带入目标函数，则可得原问题相应于基),,(632AAAB的典式6,,1,039474225341215812145..8321451min65415215431541jxxxxxxxxxxxxtsxxxj475P16、用单纯形法求解下列线性规划问题：(1)3,2,1,020102603..2min321321321321jxxxxxxxxxxtsxxxzj解：将此问题化成标准形式6,5,4,3,2,1,020102603..2min632153214321321jxxxxxxxxxxxxxtsxxxzj以654,,xxx为基变量，可得第一张单纯形表为以1x为进基变量，5x为离基变量旋转得1x2x3x4x5x6xRHSz21-100004x311100605x1-12010106x11-100120注意单纯形表的格式！注：要用记号把转轴元标出来注（零行元素的获得）：先将目标函数化成求最小值的形式，再把所有变量移到等式左边，常数移到等式右边。则变量前的系数为零行对应的元素。5以2x为进基变量，6x为离基变量旋转得解为Tx)0,5,15(*，最所以最优优值为-35。注：用单纯形法求解线性规划问题的步骤Ⅰ、将问题化成标准形式；Ⅱ、找出初始解；Ⅲ、写出第一张单纯形表，并化成典式；Ⅳ、判定和迭代。①判定：1最优解（检验数向量0）；2问题无界（某个非基变量kx的检验数0k，且kx在典式中的系数向量0kA）②迭代步骤：1确定进基变量kx（检验数向量T中最大的正分量）；2确定转轴元rka（进基变量所在的这一列中的正分量与右端向量中对应元素比值最小的）；1x2x3x4x5x6xRHSz03-50-20-204x04-51-30301x1-12010106x02-30-11101x2x3x4x5x6xRHSz002102123-354x0011-1-2101x102102121152x0123021215注：要记住在单纯形表的左边，用进基变量代替离基变量63确定离基变量rx（转轴元所在的这一行对应的基变量）；4迭代计算（利用初等行变换，将转轴元变为1，转轴元所在的这一列其它元素全部变为0）；5用进基变量kx代替离基变量rx。（3）7,6,5,4,3,2,1,06010263..min7636143265365321jxxxxxxxxxxxxtsxxxxxzj解：在第三个等式两端同乘以-1，并以7125,,,xxxx为基变量可得其单纯形表为将第0行的元素化为检验数可得1x2x3x4x5x6x7xRHSz-11-10-11005x003011062x012-1000101x10000-1007x00100116注：必须先将线性方程组和目标函数化成典式，再用单纯形方法开始判定、迭代！7由于4x的检验数014，并且4x在典式中的系数向量0)0,0,1,0(4TA，所以问题无界。75P17、用两阶段法求解下列线性规划问题：（2）0,3232..42min21212121xxxxxxtsxxz解：将此问题化为标准形式0,,,3232..42min432142132121xxxxxxxxxxtsxxz添加人工变量65,xx得到辅助问题1x2x3x4x5x6x7xRHSz0001010-45x003011062x012-1000101x10000-1007x0010011680,,,,,3232..min6543216421532165xxxxxxxxxxxxxxtsxxg以65,xx为基变量，可得辅助问题的单纯形表为把g所在的这一行的元素化成检验数以1x为进基变量，5x为离基变量旋转得1x2x3x4x5x6xRHSz-2-400000g0000-1-105x2-3-101026x-110-10131x2x3x4x5x6xRHSz-2-400000g1-2-1-10055x2-3-101026x-110-1013注：必须先将线性方程组和目标函数化成典式，才可以开始判定、迭代！9所以，辅助问题的最优解为Tx)4,0,0,0,0,1(*，其最优值为04*g。因此，原问题没有可行解。（4）0,,,14322824..6542max4321432143214321xxxxxxxxxxxxtsxxxxz解：将此问题化成标准形式0,,,14322824..6542min4321432143214321xxxxxxxxxxxxtsxxxxz添加人工变量65,xx得到辅助问题1x2x3x4x5x6xRHSz0-7-10102g02121-121041x12321021016x02121-12114100,,,,,14322824..min654321643215432165xxxxxxxxxxxxxxxxtsxxg以65,xx为基变量，可得辅助问题的单纯形表为把g所在的这一行的元素化成检验数以4x为进基变量，5x为离基变量旋转得1x2x3x4x5x6xRHSz2-45-6000g0000-1-105x14-281026x-12340111x2x3x4x5x6xRHSz2-45-6000g061120035x14-281026x-123401111以3x为进基变量，6x为离基变量旋转得所以，辅助问题的最优解为Tx)0,0,41,0,0,0(，其最优值为0g。因此，原问题的初始解为Tx)41,0,0,0(0，其第一张单纯形表为以1x为进基变量，4x为离基变量旋转得1x2x3x4x5x6xRHSz411-127043023g2304023004x8121411810416x2304021101x2x3x4x5x6xRHSz1665-10016198723g0000-1-104x3212101323161413x83010814101x2x3x4xRHSz1665-100234x3212101413x83010012问题的最优解为Tx)0,3,0,8(*，最优因此，原值为31。76P18、写出下列线性规划问题的对偶规划：为自由变量321321321321321,0,5533622432..42minxxxxxxxxxxxxtsxxxz解：先将此问题化成一般形式为自由变量321321321321321,0,5533622432..42minxxxxxxxxxxxxtsxxxz321所以，其对偶规划为为自由变量231321321321321,0,4564233122..532maxts1x2x3x4xRHSz0-660-130-311x11603283x061123注：要先将问题化成一般形式，再按规则写出它的对偶问题。要记住判定对偶变量是自由变量还是非负变量1377P20、给定线性规划问题0,,32152..min321322131xxxxxxxtsxxz记为（P）（1）用单纯形算法解P;（2）写出P的对偶问题D;（3）写出P的互补松紧条件,并利用它们解对偶D;解：(1)把问题（P）化为标准形式0,,,32152..min43213242131xxxxxxxxxtsxxz以31,xx为基变量，可得到其单纯形表为:把第0行化成检验行，得1x2x3x4xRHSz-10-1001x120153x02110314以2x为进基变量，1x为离基变量，旋转得根据最优化准则知，问题（P）的最优解为Tx)47,25,0(*,最优值为47.(2)将问题（P）化为一般形式0,,32152..min32123212131xxxxxxxtsxxz因此其对偶问题（D）为0102121..35max1221121ts(3)由问题（P）的最优解为Tx)47,25,0(*以及互补松紧性定律可得1x2x3x4xRHSz0250181x120153x0211031x2x3x4xRHSz450041472x211021253x410141471510212221解得411，12.所以，对偶问题（D）的最优解为T)1,41(*，最优值为473521.77P22、用对偶单纯形法解下列问题.（1）.3,2,1,043232..432min321321321ixxxxxxxtsxxxzi解：引入剩余变量将原问题标准化.5,4,3,2,1,043232..432min53214321321ixxxxxxxxxtsxxxzi再将约束条件两边同时乘以1得.5,4,3,2,1,043232..