运筹学的课后习题.pdf

运筹学的课后习题1.化为标准形式预备知识标准形式为设“NOmax z=g%H-Fc x1 1 n ns上.a、1%i+a1c%1c+兄 b.1111 12 12 In In 1i i+Q”人”l-=久21 21 22 22 2n 2n 2a.x.+a cX H-Fa x=b.ml ml m2 m2 mn mn mlx.N 0,i=这类题的做法：1）查看与标准型有哪些不一样的地方，把它们先找出来2 ）然后再-化为标准形式即可（m in令 z=-/;若出现不等式，则引入松弛变量，若金 加上一个松弛变量，若,减去一个松弛变量;若 变 量 0,贝分X：=f.带入；若变量占无非负限制，令菁=x；-0(2 )引入松弛变量%4，工5 ,令月=-2；X3=X3-X 1 1令Z=-于max z=$+5芯 +2x；-3%一 2K-4%；+4x；+x4=62%1+3 芯 +x；x；+/=5石一芯+%：-x；=9%,，冗；,芯,工4，工5 0(3)首先查看与标准型中有多少不一样的min/=3玉 +/+4x3+2x4s j.3X+x2+4X3+2X4 0,x4 0 )x3=-x X；=-x4m ax z =-3x-x2-+4x+2x；s.t.%小？+4乂-4x；-2x；+x5=1一2 X|一 3 2 +x：一 石 2 x；=5 -3 X|+x；+X y =72否 +4%3 x；+3x 2 x：=1 5xi,x2,x?r!,x,x4,x5,x(),x1 0,2、图解法解题方法：(1)建立直角坐标系：以决策变量x l,x 2为坐标轴。（2 ）绘制可行域：对每个约束条件（包括x i 0）,先取其为等式，并在坐标系中作出相应的直线，判定不等式所决定的半平面。若各约束半平面交出的区域存在，则其中的点称为线性规划的可行解，所有可行解组成的集合称为可行域或可行集。若不存在，线性规划无可行解。（3）绘制目标函数等值线，并移动求解 做一条目标函数的等值线。（最好穿过可行域）查看目标函数，若 求m ax ,确定函数值增加的方向；若求m i n ,确定函数值减少的方向；最后，依据目标函数的要求在可行域内平移等值线（平移到等值线与可行域的最后交点（一个或多个）2xl-x2=6xl=3 3x1+2x2=12线性规划解的种类：有唯一的最优解；有无穷多个最优解；没有有限的最优解；没有可行解，没有最优解；线性规划的可行域与最优解的关系：（参 见2 2页，图2-5）1 .可行域为封闭的有界区域：1 有唯一的最优解；2 有无穷多个最优解；2 .可行域为非封闭的无界区域：1 有唯一的最优解；2 有无穷多个最优解；3 没有有限的最优解;（目标函数随着可行域无限的增大或减少,可以看作目标函数与可行域的最后的交点在无穷远处）3.可行域为空集：没有可行解，没有最优解；线性规划解的性质：1.如何找最优解：在可行解中，找目标函数值最大的；2在有限个极点上，找目标函数值最大的；（24页）3在基本可行解中，找目标函数值最大的那个。（线性规划的基本定理：线性规划的基本可行解就是可行域的极点）三.求基（参考例2.10）1 先化为标准形式max z=2x1+x2 x3s.t.xl+x2+2x3+x4=6x+4x2-x3+x5=4xl,x2,x3,x4,x5 0_F1 1 2 1 o-2A=1 4 _ o 1，任选其中的两列Bl=（Pl,尸2）52=（Pl,P3）B3=（Pl,尸4）B4=（P1,P5）85=（P2,尸 3）B6=（P2,尸4）B7=（P2,P5）88=（尸3,尸4）89=（尸3,尸5）f i l O =（P4,P5）3 先判断是否是基？只有基才有基变量和非基变量，才能求出基本解。因为忸卜0,i =l,2,10,所以B,为线性规划的基对于Bl=(Pl,P2),xl,x2为用的基变量，令非基变量x3=x4=x5=Q 9则可得到 x(n=(2 0/3-2/3 0 0 0)基本解，非可行解。对于B2=(Pl,P3),xl,x3为4的基变量，令非基变量x2=x5=0,则可得到 产=(14/3 0 2/3 0 0)基本可行解，区为可行基。同理，基本可行解有x=(4 0 0 2 0)为基本可行解，为可行基。5)=(0 14/9 20/9 0 0)为基本可行解，区为可行基。x=(0 1 0 5 0)为基本可行解，然为可行基。产=(0 0 3 0 7)为基本可行解，为为可行基。x(,o)=(O 0 0 6 4)为基本可行解，为可行基。基本解产=(6 0 0 0-2)x=(0 6 0 0-2)(x=(0 0-4 1 40)4.求出基本可行解的目标函数值，目标函数值最大的那个基本可行解为最优解，其目标函数值为最优值，对应的基为最优基。Z=26/3 Z=8 Z=-2/3,Z=1 Z=一3 Z。)=0所以最优解为x=(14/3 0 2/3 0 0),最优值为26/3,最优基为B2 O四，单纯形法步骤：1首先找到一个基本可行解(如标准型中有单位矩阵，选择为基，此时得到的基本解一定是基本可行解)，将基变量和目标用非基变量来表示。2.判断是否最优，（目标函数用非基变量表示以后，目标函数中非基变量对应的系数称为检验数），若所有的检验数都小于等于零，则此时的基本可行解为最优解，结束计算。否则，不是最优解，转 入 33 判断进基变量，原则上选择检验数大于零中任何一个都可以，但是为了更快的达到最优解，一般选择大于零中最大的那个对应的非基变量作为进基变量。4.若检验数大于零中，某个检验数对应的变量系数都小于等于零，则线性规划无有限的最优解，计算结束，否则转55 选择出基变量，当进基变量从零开始增加时，查看那个基变量首先减少为零，选择首先降为零的那个变量为出基变量。6.这样得到了新的基变量、非基变量。将新基变量及目标函数用新的非基变量来表示，再令非基变量为零，可以得到新的基本可行解，然后重复2-6过程，直到最终结果算出来为止。例如4（2）法一先化为标准形式（引入松弛变量%）m a x z =x 2 2 x 3s.t.xl+3 x 2 +4 x 3 =1 ：Fl 3 4 0,A=2 x 2-x 3 +x 4 =1 2|_ 0 2 -1 1x l,x 2,x 3 01 取可行基为8=（6 2），（原则上任找一个基本可行解都可以，但是如果标准型中有单位矩阵，选单位矩阵作为基，那么得到的基本解一定是基本可行解）。将基变量*多 及 Z用非基变量如马来表示:z=x2-2 x 3xl=1 2-(3 x 2 +4 x 3)%4 =1 2-(2 x 2-x 3)令非基变量 Xy%2 =0，则 得 到=(1 2,0,0,1 2),Z(0)=0 2 判断是否是最优解？因为检验数中l0,所以”不是最优解。选择进基变量，(原则上选择检验数大于0中的任何一个都可以，但为了使得达到最大值更快一些，一般选择检验数中大于零里最大的那个非基变量进基)，m a x l|l 0 =lf 进基3 查看检验数大于零的非基变量所对应的约束系数是否都小于等于零。若是，则该问题无有限的最优解。若不是，选择出基变量。当进基变量开始增加时，选择首先降为0的基变量作为出基变量。1 o 19m i n(,3 0,2 0 =4 f x i 出 基4 将 新 基 变 量%及目标函数z 用新的非基变量七,为来表示,/2 1 1 、=4 _(-内令非基变量/=玉=0,则新基本可行解”=(0,4,0,4),Z=4,再 转 2因为检验数一，(),所以该解为最优解。法二取基为8 =仍 舄)=(单 位矩阵)，则建立单纯形表如下：注意:CBXBbf01-200王了2苫3%01213404*0%1202-116-Z001*-201X241/314/300%4-2/30-11/31-Z-4-1/30-10/30判断为取何值时，有最优解，唯一的最优解，有无穷多个最优解，没有有限的最优解。1X21/31%00X44-2/30-11/31-Z-4a20a30max z=3玉 +x2s.t.课后习题：求最优解：%+2+%3=42%+x2 05.利用大M法和两阶段法来求解下列模型m i n/=3%+x2-x1+x2 lX j,x2 01化为标准形式m a x z=-3玉-x2s.t.-x,+x2 4-x3=2 -1 1 1 0 09 A=1X j +x2-x4=1 1 10-11xpx2,x3,x4 0_ X)+超 +%3 =22 引入人工变量 X5,X j +x2 x4 4-x5=1xpx2,x3,x4,x5 0【法一构造新目标函数m a x z =-3 x,-x2-Mx5CBXBbr-3-100-Me玉X2X3%X50X32-111002-MX51110-111*-zMM-3M-l*0-M00X31-2011-11X21110-11-z1-200-11-M所以，此问题的最优解为(0,1,1,0,0),最优值为T,因为“5*=0,所以(0,1,1,0)为原问题的最优解，原问题的最优值为L 法二构造新目标函数m a x z=-x5CBXBb0 0 0 0-10占 x2 x3%X50七2-1 1 1 0 0-1X511 1 0-1 11*-Z11*1 0-100X330 2 1-1 1011 1 0-1 1-Z00 0 0 0-1所以此时最优解为(1,0,3,0,0),因为因为毛*=,所以(1,0,3,0)为原问题的基本可行解。CBXBbr-3-1000百X3%0X33021-13/2-3x1110-11*-Z302*0-3所以（0,1,0）为原问题的最优解，最优值为1.0-1X3x211-2011110-1-z1-200-1第二章，课后习题选解一、如何来求对偶规划1.化为这种对称形式min f=brYs.t.A Y Cy 0max z=CT Xs.t.AX 0max匚模式为 口工口si.二 o 2、可 相 互 转 化 mln0-r S工 作 口7 L 0 0可相互转化原 问 题（对 偶）0量/V。-一j 无非负限制目 标min f约 n个束j 条j 0喳i 0i 无非负限制min/=5%+2y2f +为 2一31.s.t.2%+3y2 2 52。2.(P)max z=xl+2x2+X3s.t.2x+毛=8一%+2X2+3 J3=6再，马均无非负限制mins.t.f=S yi+6y22%一必=1%+2%=23 y 2 =1%,当均无非负限制3.max z=芭 +2X2-3x3+4x4s.t.X +一 退一3%=56%+7 -&+5%-812%一 9工2+7X3+6/4 10演，/羽将后限制Max值形式，先化为工max z=玉 +2X2-3x3+4x4s.t.-x+x2-x3-3X4=5P 6斗7%2 +X 3-54 812xl-9X2+7&+65 11%-7y2-9%=2_%+2+7%-3-3%-5y2+6%=4%无非负限制,y2 y3 04.min f =-3%+2x2+5x3-7 x4-8x5s.OX+x,一 当 +3%4 4/=62%+3X2-3X3-X4+0X5 2-1+0 x9+213 2%4+0%54 5-2%105 x2 2%1 Ox?2尤3+2犬4 Ox5 N 5 X j 10X N 2尤2 2 5一%2 25X L，%为无非负限制，%之0max z=63+2为 +5%-1。、4-2y5+5%一 25%s2y2+%-%+为 =-3M+3y2+儿一，7 V2_%-3%_ 2y3=53%一、2+2%=-7-4y=-8必无非负限制，%，%加 为 为202.判断原问题是否有最优解,此类问题的知识点:考察推论2 P有可行解，若 看最优解()伤中行解 匕 其逆否：无可行解，则原问题无有限的最优解。min f =2yl+%s.t.-y-2y2 21.(0,0,0)为原问题的可行解，其对偶问题为：y,+y22-,显%-2 0M，2然对偶问题没有可行解，所以原问题没有有限的最优解。max z=-4+6为+y2 -12.(2,2,0)为原问题的可行解，其对偶问题为-5+2%42,V 41弘NO,为为无非负限制显 然(1,3)为对偶问题的可行解，所以原问题有最优解。max z=5%+6%+8%+7%3.s.t.%+为1为+为准形式:m ax z=5必+6 y 2 +8%+7 y4，+%+%=1%+%+%=1%+%+%=1%+%+%=1?，%，%，,4，为，丁6，7，为 2 4.应用对偶性质，直接写出原问题的最优值这里主要考察：定理政问题有最例解有最优解 电两者最优解的目标函数值相等。max z=50yls/.5yl 46%+3%2+5/10 x1,J C2 x3 0max z=-5x-2x2-4x33%+x2+2X3-x4=46xj+3X2+5X3-X5=10 xpx2 x3,x4,x5 0max z=-5%一 2x2-4x33X|%2 2/+%=4s.t.0建立对偶单纯形表：min-4,10卜 4 0,10 演出基-5-2-4.2min,卜 6Vo 3 0,一 5 6 3 5 3CBXBb-5-2-400 xl工2X3X4X50X4-4-3-1-2100XS-10-6-3-501-z0-5-2-400min-4,-10|-4 0,-10 0=-10 f 演出基-5-2-4 2min,-6 0 3 0,5%基-6-3-5 30X4-2/3-1 0-1/3 1 -1/3-2工210/32 1 5/3 0-1/3-Z20/3-1 0-2/3 0-2/3min-2/3 卜 2/3 v 0=-2/3-与出基mm.f 1 2/3 2/3i1-1 0,-2,/3 0maxz=一 -2X2-3x3所以标准型的最优解为(0,2,0,0,6,2),),最优值为-20X5601/25/2-1/2100X6201-1001-z20-5/2-5/2-1/200原问题的最优解为(0,2,0,(),6,2),),最优值为2用对偶单纯形法求解m i n w =2 x i +3 x2+4 x3Xi+2x2+X 3 三 12 x i -X 2 +3x3 三 4Xi,x2,X 3 三 0解：max z=-2xi-3x2-4x3+0 x4+0 x5z*_ Xi _ 2x2-X3+X4=-1 -2xi+X 2 -3x3+X s=4I Xi,x2,x3,x4,X 5 2 0-2-3-400CBX Bbxlx2x3x4X 50 x4-1-1-2-1100 x5-4*-21-301-z0-2-3-400m in-l,-4|-l0,-4/出基.-2 -4,-2m i n =，F|-2 0,-3 x,进基0 x4 10-5/2 1/2 1 -1/2-2 xl 21 -1/2 3/2 0-1/2-z40-4-1 0-1所以标准型的最优解为(2,0,0,1,00),最优值为-46.初始单纯形表:原问题的最优解为(2,0,0,1,0 0),最优值为4cBXBb230000/X2X、*4X5X60X3122210000X481201000Z16400010012040001-z0230000最优单纯形表CBXBb230000X1X2*4X60X30001-1-1/402X410001/400*64000-21/213X220101/2-1/80-z-14000-3/2-1/80怎样找初始基矩阵？只要在最优单纯形表中将基变量按顺序找到（X3,X 1，X6,X2），然后按顺序在初始单纯形表中将这些变量对应的系数向量写下来即可。1 2 0 20 1 0 2B=0 4 0 00 0 1 4怎样找其逆矩阵？只要在初始单纯形表中找到单位矩阵所在的变量（也要注意顺序）（0，*4，*5，尤6），然后按顺序在最优单纯形表中将这些变量对应的系数向量写下来即可。1-1-1/4 0-,0 0 1/4 0B i=0-2 1/2 1，0 1/2-1/8 0设A =（4,舄，尸3,居，尸5,尸6），000B1P4=-10-21/21 1-1/40一o-1/4-001/4001/4=0-21/2111/201/2-1/800-l/8_1)G 为基变量的目标系数，则G 变化会改变非基变量的检验数q,不会影响基变量的检验数。J f q +Ie1保持最优解不变的条件：%T q =-以+J C)B P4=C4-C/B-P,-A C V P4=(T4-dCrB P,=-3/2+0生.仇飞_(+加断？=6_品用？_ 加，？=0 _ 加甘卬5=_/8+，40 Ac.1 2 C2为基变量的目标系数,则C2变化会改变非基变量的检验数。4，不会影响基变量的检验数。保持最优解不变的条件：d =。4 -爆 +/C)B?=cC W A-4”A=/一/C M A=一 3/2+%4 0%4 G =c -+4C)B?=0 5 -C J B?-=%-=-1/8 组 4 0=Ac 122 2。2=3 f 弓=5,4。2=3,则亍4=-3/2 +：*2=-1 0;万5=-1/8-：4 2=-l/8-l/4*2=-5/8b=,则1/2-1/810Xg f NB=B-xb=B l(b+Ab)=XB+B 1-1/41/41/2-1/8001000叫0一:皿4dAbo4+4832 Ab8 3则，8 3 -05）增加一个约束条件：2xt+2AX2 0 1*2 *5 1 4、51 0 1 00 1-4 14=（耳谯,舄通迷）=-1 112 43 110 00BiP1=0-1112-116B1 4013103-2B1P4=0103)c 3 fM =8,4 3 =一5,则b3 f 6 =q +=-2-5=-7 v 0,所以最优解不变5X245-11310 00X5 90*160-2-4i-z-10000-2-50采用对偶单纯形法XBR =B-lb=1 0_ 厂,2(，4=B-吊=8 他+仍)=H1 1 .(+B-i f)2 0一=d5 J|_ 1 0 _1 O-4 1 o i r o