运筹学第五版习题答案.docx
运筹学习题答案第一章（39 页）1.1 用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。（1）max12zxx51x+102xEMBED Equation.DSMT4501x+2xEMBED Equation.DSMT412xEMBED Equation.DSMT441x，2xEMBED Equation.DSMT40（2）min z=1x+1.52x1x+32xEMBED Equation.DSMT431x+2xEMBED Equation.DSMT421x，2xEMBED Equation.DSMT40（3）max z=21x+22x1x-2xEMBED Equation.DSMT4-1-0.51x+2xEMBED Equation.DSMT421x，2xEMBED Equation.DSMT40（4）max z=1x+2x1x-2xEMBED Equation.DSMT4031x-2xEMBED Equation.DSMT4-31x，2xEMBED Equation.DSMT40解：（1）（图略）有唯一可行解，max z=14（2）（图略）有唯一可行解，min z=9/4（3）（图略）无界解（4）（图略）无可行解1.2 将下列线性规划问题变换成标准型，并列出初始单纯形表。（1）min z=-31x+42x-23x+54x41x-2x+23x-4x=-21x+2x+33x-4xEMBED Equation.DSMT414-21x+32x-3x+24xEMBED Equation.DSMT421x，2x，3xEMBED Equation.DSMT40，4x无约束（2）maxikxEMBED Equation.DSMT40(i=1n;k=1,m)（1）解：设 z=-z,4x=5x-6x,5x,6xEMBED Equation.DSMT40标准型：Maxz=31x-42x+23x-5(5x-6x)+07x+08x-M9x-M10 xs.t.-41x+2x-23x+5x-6x+10 x=21x+2x+33x-5x+6x+7x=14-21x+32x-3x+25x-26x-8x+9x=21x,2x,3x,5x,6x,7x,8x,9x,10 xEMBED Equation.DSMT40初始单纯形表:jcEMBEDEquation.DSMT43-42-5500-M-MiBCBXb1x2x3x5x6x7x8x9x10 x-M10 x2-41-21-10001207x14-M9x2-23-12-20-1102/3-z4M 3-6M4M-42-3M3M-55-3M0-M00(2)解：加入人工变量1x，2x，3x，nx，得：Maxs=(1/kp)1niEMBEDEquation.DSMT41mkikEMBEDEquation.DSMT4ikx-M1x-M2x-.-Mnxs.t.(i=1,2,3,n)ikxEMBEDEquation.DSMT40,ixEMBEDEquation.DSMT40,(i=1,2,3n;k=1,2.,m)M 是任意正整数初始单纯形表：jc-M-M-MiBCBXb1x2xnx11x12x1mx1nx2nxnmx-M1x11 0 0 11 000-M2x10 1 00 000 -Mnx10 0 1 000 111-snM0 0 01.3 在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解，并代入目标函数，确定最优解。（1）max z=21x+32x+43x+74x21x+32x-3x-44x=81x-22x+63x-74x=-31x,2x,3x,4xEMBED Equation.DSMT40(2)max z=51x-22x+33x-64x1x+22x+33x+44x=721x+2x+3x+24x=31xEMBED Equation.DSMT42x3xEMBED Equation.DSMT44x0（1）解：系数矩阵 A 是：令 A=(1P，2P，3P，4P)1P与2P线形无关，以（1P，2P）为基，1x，2x为基变量。有21x+32x=8+3x+44x1x-22x=-3-63x+74x令非基变量3x，4x=0解得：1x=1；2x=2基解(1)X=（1，2，0，0)T为可行解1z=8同理，以（1P，3P）为基，基解(2)X=（45/13，0，-14/13，0)T是非可行解；以（1P，4P）为基，基解(3)X=（34/5，0，0，7/5)T是可行解，3z=117/5；以（2P，3P）为基，基解(4)X=（0，45/16，7/16，0)T是可行解，4z=163/16；以（2P，4P）为基，基解(5)X=（0，68/29，0，-7/29)T是非可行解；以（4P，3P）为基，基解(6)X=（0，0，-68/31，-45/31)T是非可行解；最大值为3z=117/5；最优解(3)X=（34/5，0，0，7/5)T。（2）解：系数矩阵 A 是：令 A=(1P，2P，3P，4P)1P，2P线性无关，以（1P，2P）为基，有：1x+22x=7-33x-44x21x+2x=3-3x-24x令3x，4x=0 得1x=-1/3，2x=11/3基解(1)X=（-1/3，11/3，0，0)T为非可行解；同理，以（1P，3P）为基，基解(2)X=（2/5，0，11/5，0)T是可行解2z=43/5；以（1P，4P）为基，基解(3)X=（-1/3，0，0，11/6)T是非可行解；以（2P，3P）为基，基解(4)X=（0，2，1，0)T是可行解，4z=-1；以（4P，3P）为基，基解(6)X=（0，0，1，1)T是6z=-3；最大值为2z=43/5；最优解为(2)X=（2/5，0，11/5，0)T。1.4 分别用图解法与单纯形法求解下列线性规划问题，并指出单纯形迭代每一步相当于图形的哪一点。（1）max z=21x+2x31x+52xEMBED Equation.DSMT41561x+22xEMBED Equation.DSMT4241x，2xEMBED Equation.DSMT40（2）max z=21x+52x1xEMBED Equation.DSMT4422xEMBED Equation.DSMT41231x+22xEMBED Equation.DSMT4181x，2xEMBED Equation.DSMT40解：（图略）（1）max z=33/4最优解是(15/4,3/4)单纯形法：标准型是 max z=21x+2x+03x+04xs.t.31x+52x+3x=1561x+22x+4x=241x,2x,3x,4xEMBED Equation.DSMT40单纯形表计算：jc2100iBCBXb1x2x3x4x03x153510504x2462014-z0210003x3041-1/23/421x411/301/612-z-801/30-1/312x3/4011/4-1/821x15/410-1/125/24-z-33/400-1/12-7/24解为：（15/4，3/4，0，0)TMax z=33/4迭代第一步表示原点；第二步代表 C 点（4，0，3，0)T；第三步代表 B 点（15/4，3/4，0，0)T。（2）解：（图略）Max z=34此时坐标点为（2，6）单纯形法，标准型是：Max z=21x+52x+03x+04x+05xs.t.1x+3x=422x+4x=1231x+22x+5x=181x,2x,3x,4x,5xEMBED Equation.DSMT40(表略)最优解X=（2，6，2，0，0)TMax z=34迭代第一步得(1)X=（0，0，4，12，18)T表示原点，迭代第二步得(2)X=（0，6，4，0，6)T，第三步迭代得到最优解的点。1.5 以 1.4 题（1）为例，具体说明当目标函数中变量的系数怎样变动时，满足约束条件的可行域的每一个顶点，都可能使得目标函数值达到最优。解：目 标 函 数：max z=1cEMBED Equation.DSMT41x+2cEMBEDEquation.DSMT42x(1)当2cEMBED Equation.DSMT40 时2x=-（1c/2c）1x+z/2c其中，k=-1c/2cABk=-3/5，BCk=-3kEMBED Equation.DSMT4BCk时，1c，2c同号。当2cEMBED Equation.DSMT40 时，目标函数在 C 点有最大值当2c0 时，目标函数在原点最大值。BCkkABk时，1c，2c同号。当2c0，目标函数在 B 点有最大值；当2c0，目标函数在原点最大值。ABkk0 时，1c，2c同号。当2cEMBED Equation.DSMT40 时，目标函数在 A 点有最大值当2c0 时，目标函数在原点最大值。k0 时，1c，2c异号。当2cEMBED Equation.DSMT40，1c0 时，目标函数在 A 点有最大值；当2c0，1c0 时，目标函数在 C 点最大值。k=ABk时，1c，2c同号当2cEMBED Equation.DSMT40 时，目标函数在 AB 线断上任一点有最大值当2c0，目标函数在原点最大值。k=BCk时，1c，2c同号。当2cEMBED Equation.DSMT40 时，目标函数在 BC 线断上任一点有最大值当2c0 时，目标函数在原点最大值。k=0 时，1c=0当2cEMBED Equation.DSMT40 时，目标函数在 A 点有最大值当2c0，目标函数在 OC 线断上任一点有最大值（2）当2c=0 时，max z=1c1x1c0 时，目标函数在 C 点有最大值1c0 时，目标函数在 OA 线断上任一点有最大值1c=0 时，在可行域任何一点取最大值。1.6 分别用单纯形法中的大 M 法与两阶段法求解下列线性问题，并指出属于哪类解。（1）max z=21x+32x-53x1x+2x+3xEMBED Equation.DSMT41521x-52x+3xEMBED Equation.DSMT4241x，2xEMBED Equation.DSMT40（2）min z=21x+32x+3x1x+42x+23xEMBED Equation.DSMT4831x+22x61x，2x，3x0（3）max z=101x+152x+123x51x+32x+3x9-51x+62x+153xEMBED Equation.DSMT41521x+2x+3xEMBED Equation.DSMT451x，2x，3xEMBED Equation.DSMT40（4）max z=21x-2x+23x1x+2x+3xEMBED Equation.DSMT46-21x+3xEMBED Equation.DSMT4222x-3xEMBED Equation.DSMT401x，2x，3xEMBED Equation.DSMT40解：（1）解法一：大 M 法化为标准型：Max z=21x+32x-53x-M4x+05x-M6xs.t.1x+2x+3x+4x=721x-52x+3x-5x+6x=101x,2x,3x,5x,4x,6xEMBED Equation.DSMT40M 是任意大整数。单纯形表：jc23-5-M0-MiBCBXb1x2x3x4x5x6x-M4x71111007-M6x102-510-115-z17M3M+23-4M2M-50-M0-M4x207/21/211/2-1/24/721x51-5/21/20-1/21/2-z2M-100(7/2)M+80.5M-600.5M+1-1.5M-132x4/7011/72/71/7-1/721x45/7106/75/7-1/71/7-z-102/700-50/7-M-16/7-1/7-M+1/7最优解是：X=（45/7，4/7，0，0，0)T目标函数最优值max z=102/7有唯一最优解。解法二：第一阶段数学模型为 min w=4x+6xS.t.1x+2x+3x+4x=721x-52x+3x-5x+6x=101x,2x,3x,4x，5x,6xEMBED Equation.DSMT40（单纯形表略）最优解X=（45/7，4/7，0，0，0)T目标函数最优值 min w=0第二阶段单纯形表为：jc23-50iBCBXb1x2x3x5x32x4/7011/71/721x45/7106/7-1/7-z-102/700-50/7-1/7最优解是X=（45/7，4/7，0，0，0)TMax z=102/7（2）解法一：大 M 法z=-z有 maxz=-min（-z）=-min z化成标准形：Maxz=-21x-32x-3x+04x+05x-M6x-M7xS.T.1x+42x+23x-4x+6x=431x+22x-5x+7x=61x,2x,3x,4x，5x,6x，7xEMBED Equation.DSMT40（单纯性表计算略）线性规划最优解 X=（4/5，9/5，0，0，0，0)T目标函数最优值 min z=7非基变量3x的检验数3=0，所以有无穷多最优解。两阶段法：第一阶段最优解 X=（4/5，9/5，0，0，0，0)T是基本可行解,min w=0第二阶段最优解（4/5，9/5，0，0，0，0)Tmin z=7非基变量3x的检验数3=0，所以有无穷多最优解。（3）解：大 M 法加入人工变量，化成标准型：Max z=101x+152x+123x+04x+05x+06x-M7xs.t.51x+32x+3x+4x=9-51x+62x+153x+5x=1521x+2x+3x-6x+7x=51x,2x,3x,4x，5x,6x，7xEMBED Equation.DSMT40单纯形表计算略当所有非基变量为负数，人工变量7x=0.5，所以原问题无可行解。两阶段法（略）（4）解法一：大 M 法单纯形法，（表略）非基变量4x的检验数大于零，此线性规划问题有无界解。两阶段法略1.7 求下述线性规划问题目标函数 z 的上界与下界；MaxMax z=z=1 1c x+22c x其中：113c，246c，1812b，21014b，1113a，1225a，2124a，2246a解：解：求 Z 的上界Max z=31x+62xs.t.-1x+22xEMBED Equation.DSMT41221x+42xEMBED Equation.DSMT4142x，1xEMBED Equation.DSMT40加入松弛变量，化成标准型，用单纯形法解的，最优解X=（0，7/2，5，0)T目标函数上界为 z=21存在非基变量检验数等于零，所以有无穷多最优解。求 z 的下界线性规划模型：Max Z=1x+42xs.t.31x+52xEMBED Equation.DSMT4841x+62xEMBED Equation.DSMT4102x，1xEMBED Equation.DSMT40加入松弛变量，化成标准型，解得：最优解为X=（0，8/5，0，1/5)T目标函数下界是 z=32/51.8 表 1-6 是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，1a，2a，3a，d，1c，2c为待定常数，试说明这些常数分别取何值时，以下结论成立。（1）表中解为唯一最优解；（2）表中解为最优解，但存在无穷多最优解；（3）该线性规划问题具有无界解；（4）表中解非最优，对解改进，换入变量为1x，换出变量为6x。基 b1x2x3x4x5x6x3xd41a102a04x2-1-301-106x33a-500-41jjcz1c2c00-30解：解：（1）有唯一最优解时，d0，1cEMBED Equation.DSMT40，2cEMBED Equation.DSMT40（2）存在无穷多最优解时，d0，1cEMBED Equation.DSMT40，2c=0 或 d0，1c=0，2cEMBED Equation.DSMT40.（3）有无界解时，d0，1cEMBED Equation.DSMT40，2cEMBEDEquation.DSMT40 且10a（4）此时，有 d0，1cEMBED Equation.DSMT40 并且1cEMBEDEquation.DSMT42c，30a，3/3aEMBED Equation.DSMT4d/41.9 某昼夜服务的公交线路每天个时间段内所需司机与乘务员人数如下：班次时间所需人数16 点到 10 点60210 点到 14 点70314 点到 18 点60418 点到 22 点50522 点到 2 点2062 点到 6 点30设司机与乘务人员分别在各时间区段一开始时上班，并连续上班 8小时，问该公交线路至少配备多少司机与乘务人员。列出线型规划模型。解解：设kx（k=1，2，3，4，5，6）为kx个司机与乘务人员第 k 班次开始上班。建立模型：Min z=1x+2x+3x+4x+5x+6xs.t.1x+6xEMBED Equation.DSMT4601x+2xEMBED Equation.DSMT4702x+3xEMBED Equation.DSMT4603x+4xEMBED Equation.DSMT4504x+5xEMBED Equation.DSMT4205x+6xEMBED Equation.DSMT4301x,2x,3x,4x,5x,6x01.10 某糖果公司厂用原料 A、B、C 加工成三种不同牌号的糖果甲乙丙，已知各种糖果中 ABC 含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用与售价如表所示：原料甲乙丙原 料成本（元/千克）每 月限制用量（千克）A60%15%22000B1.52500C20%60%50%11200加工费0.50.40.3售价3.42.852.25问该厂每月应当生产这三种牌号糖果各多少千克，使得获利最大？建立数学模型。解解:解：设1x，2x，3x是甲糖果中的 A，B，C 成分，4x，5x，6x是乙糖果的 A，B，C 成分，7x，8x，9x是丙糖果的 A，B，C 成分。线性规划模型：Max z=0.91x+1.42x+1.93x+0.454x+0.955x+1.456x-0.057x+0.458x+0.959xs.t.-0.41x+0.62x+0.63xEMBED Equation.DSMT40-0.21x-0.22x+0.83xEMBED Equation.DSMT40-0.854x+0.155x+0.156xEMBED Equation.DSMT40-0.64x-0.65x+0.46xEMBED Equation.DSMT40-0.77x-0.58x+0.59x01x+4x+7x20002x+5x+8x25003x+6x+9x12001x,2x,3x,4x,5x,6x,7x,8x,9x01.11 某厂生产三种产品 I、III。每种产品经过 AB 两道加工程序，该厂有两种设备能完成 A 工序，他们以1A,2A表示；有三种设备完成 B 工序，分别为1B，2B，3B；产品 I 可以在 AB 任何一种设备上加工，产品可以在任何规格的 A 设备上加工，但完成 B 工序时，只能在1B设备上加工；产品 III 只能在2A，2B上加工。已知条件如下表，要求安排最优生产计划，使该厂利润最大化。设备产品设备有效台时满负荷时的设备费用IIIIII1A51060003002A7912100003211B6840002502B41170007833B74000200原料费0.250.350.5单价1.252.002.8解：产品 1，设1A,2A完成 A 工序的产品1x，2x件；B 工序时，1B,2B，3B完成 B 工序的3x，4x，5x件，产品，设1A,2A完成 A 工序的产品6x，7x件；B 工序时，1B完成 B 的产品为8x件；产品 111，2A完成A 工序的9x件，2B完成 B 工序的9x件；建立数学模型：Max z=(1.25-0.25)*(1x+2x)+(2-0.35)*(6x+7x)+(2.8-0.5)9x-(51x+106x)300/6000-(72x+97x+129x)321/10000-(63x+88x)250/4000-(44x+119x)783/7000-75x*200/4000s.t51x+106x600072x+97x+129x1000063x+88x400044x+119x700075x40001x,2x,3x,4x,5x,6x,7x,8x,9x0最优解为 X=（1200，230，0，859，571，0，500，500，324)T最优值 1147.试题：试题：1.（2005 年华南理工大学）设某种动物每天至少需要 700 克蛋白质、30 克矿物质、100 毫克维生素。现有 5 种饲料可供选择，每种饲料每公斤营养成分的含量与单价如下表所示：试建立既满足动物生长需要，又使费用最省的选用饲料方案的线性规划模型。表 11饲料蛋白质（克）矿物质（克）维生素（毫克）价格（元/公斤）1310.50.2220.510.7310.20.20.446220.35180.50.80.8解题分析：这是一道较简单的数学规划模型问题，根据题意写出约束即可。解题过程：12345min0.20.70.40.30.8zxxxxx第二章（第二章（6767 页）页）2.1 用改进单纯形法求解以下线性规划问题。（1 1）MaxMax z=z=61x-22x+33x2 21x-2x+33xEMBED Equation.DSMT421x+43xEMBED Equation.DSMT441x，2x，3xEMBED Equation.DSMT40（2）min z=21x+2x31x+2x=341x+32xEMBED Equation.DSMT461x+22xEMBED Equation.DSMT431x,2xEMBED Equation.DSMT40解：解：（1 1）先化成标准型：Max z=61x-22x+33x+04x+05xs.t.21x-2x+23x+4x=21x+43x+5x=41x,2x,3x,4x,5x0令0B=（4P，5P）=0BX=（4x,5xEMBED Equation.DSMT4)T,0BC=(0,0)0NC=(6,-2,3)，10B=,0b=24 非基变量的检验数0N=0NC-0BC10B0N=0NC=(6,-2,3)因为1x的检验数等于 6，是最大值，所以，1x为换入变量，由规则得：=14x为换出变量。1B=(4P，5P)=,1BX=（1x,5xEMBED Equation.DSMT4)T，1BC=(6,0).1NC=(0，-2，3)，11B=,1b=13 非基变量的检验数1N=（-3，1，-3）因为2x的检验数为 1，是正的最大数。所以2x为换入变量；由规则得：=6所以5x是换出变量。2B=(1P，2P)=,2BX=（1x,2xEMBED Equation.DSMT4)T，2BC=(6,-2).2NC=(0，0，3)，12B=,2b=46 非基变量的检验数2N=（-2，-2，-9）非基变量的检验数均为负数，愿问题已达最优解。最优解 X=46 即：X=（4,6,0)T目标函数最优值 maxz=12（2 2）解：Min z=21x+
