运筹学习题及答案.pdf

运筹学习题答案第一章（ 39页）1.1 用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。（1）max 12zxx51x+102x50 1x+2x1 2x4 1x，2x0 （2）min z=1x+1.52x1x+32x3 1x+2x2 1x，2x0 （3）max z=21x+22x1x-2x-1 -0.51x+2x2 1x，2x0 （4）max z=1x+2x1x-2x0 31x-2x-3 1x，2x0 解：（1） （图略）有唯一可行解， max z=14 （2） （图略）有唯一可行解， min z=9/4 （3） （图略）无界解（4） （图略）无可行解1.2 将下列线性规划问题变换成标准型，并列出初始单纯形表。（1）min z=-31x+42x-23x+54x41x-2x+23x-4x=-2 1x+2x+33x-4x14 -21x+32x-3x+24x2 1x，2x，3x0，4x无约束（2）max kkzsp11nmkikikikza x11(1,., )mikkxinikx0 (i=1n; k=1,m) （1）解：设 z=- z ,4x=5x-6x, 5x,6x0 标准型：Max z =31x-42x+23x-5(5x-6x)+07x+08x-M9x-M10 xs. t . -41x+2x-23x+5x-6x+10 x=2 1x+2x+33x-5x+6x+7x=14 -21x+32x-3x+25x-26x-8x+9x=2 1x,2x,3x,5x,6x,7x,8x,9x,10 x0 初始单纯形表 : jc3 -4 2 -5 5 0 0 -M -M iBCBXb 1x2x3x5x6x7x8x9x10 x-M 10 x2 -4 1 -2 1 -1 0 0 0 1 2 0 7x14 1 1 3 -1 1 1 0 0 0 14 -M 9x2 -2 3 -1 2 -2 0 -1 1 0 2/3 - z4M 3-6M 4M-4 2-3M 3M-5 5-3M 0 -M 0 0 (2)解：加入人工变量1x，2x，3x，nx，得：Max s=(1/kp)1ni1mkikikx-M1x-M2x-.-Mnxs.t. 11miikkxx(i=1,2,3,n) ikx0, ix0, (i=1,2,3n; k=1,2.,m) M 是任意正整数初始单纯形表：jc-M -M -M 11kap12kap1mkap1nkap2nkapmnkapiBCBXb 1x2xnx11x12x1mx1nx2nxnmx-M 1x1 1 0 0 1 1 0 0 0 -M 2x1 0 1 0 0 0 0 0 -M nx1 0 0 1 0 0 0 1 1 1 -s nM 0 0 0 11kaMp12kaMp1mkaMp1nkaMp2nkaMpmnkaMp1.3 在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解，并代入目标函数，确定最优解。（1）max z=21x+32x+43x+74x21x+32x-3x-44x=8 1x-22x+63x-74x=-3 1x,2x,3x,4x0 (2)max z=51x-22x+33x-64x1x+22x+33x+44x=7 21x+2x+3x+24x=3 1x2x3x4x0 （1）解：系数矩阵 A 是：23141267令 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 是：12342112令 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+52x15 61x+22x24 1x，2x0 （2）max z=21x+52x1x4 22x12 31x+22x18 1x，2x0 解： （图略）（1）max z=33/4 最优解是 (15/4,3/4) 单纯形法：标准型是 max z=21x+2x+03x+04xs.t. 31x+52x+3x=15 61x+22x+4x=24 1x,2x,3x,4x0 单纯形表计算：jc2 1 0 0 iBCBXb 1x2x3x4x0 3x15 3 5 1 0 5 0 4x24 6 2 0 1 4 -z 0 2 1 0 0 0 3x3 0 4 1 -1/2 3/4 2 1x4 1 1/3 0 1/6 12 -z -8 0 1/3 0 -1/3 1 2x3/4 0 1 1/4 -1/8 2 1x15/4 1 0 -1/12 5/24 -z -33/4 0 0 -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=4 22x+4x=12 31x+22x+5x=18 1x,2x,3x,4x,5x0 (表略) 最优解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=1c1x+2c2x(1)当2c0 时2x=-（1c/2c）1x+z/2c其中， k=-1c/2cABk=-3/5，BCk=-3 kBCk时，1c，2c同号。当2c0 时，目标函数在C 点有最大值当2c0 时，目标函数在原点最大值。BCkkABk时，1c，2c同号。当2c0， 目标函数在 B 点有最大值；当2c0，目标函数在原点最大值。ABkk 0 时，1c，2c同号。当2c0 时，目标函数在A 点有最大值当2c0 时，目标函数在原点最大值。k 0 时，1c，2c异号。当2c0，1c0 时，目标函数在 A 点有最大值；当2c0，1c0 时，目标函数在 C 点最大值。k= ABk时，1c，2c同号当2c0 时，目标函数在AB 线断上任一点有最大值当2c0，目标函数在原点最大值。k= BCk时，1c，2c同号。当2c0 时，目标函数在BC 线断上任一点有最大值当2c0 时，目标函数在原点最大值。k=0 时，1c=0 当2c0 时，目标函数在A 点有最大值当2c0，目标函数在 OC 线断上任一点有最大值（2）当2c=0 时，max z= 1c1x1c0 时，目标函数在C 点有最大值1c0 时，目标函数在OA 线断上任一点有最大值1c=0 时，在可行域任何一点取最大值。1.6 分别用单纯形法中的大M 法和两阶段法求解下列线性问题，并指出属于哪类解。（1）max z=21x+32x-53x1x+2x+3x15 21x-52x+3x24 1x，2x0 （2）min z=21x+32x+3x1x+42x+23x8 31x+22x6 1x，2x，3x0 （3）max z=101x+152x+123x51x+32x+3x9 -51x+62x+153x15 21x+2x+3x5 1x，2x，3x0 （4）max z=21x-2x+23x1x+2x+3x6 -21x+3x2 22x-3x0 1x，2x，3x0 解： （1）解法一：大 M 法化为标准型：Max z=21x+32x-53x-M4x+05x-M6xs.t. 1x+2x+3x+4x=7 21x-52x+3x-5x+6x=10 1x,2x,3x,5x,4x,6x0 M 是任意大整数。单纯形表：jc2 3 -5 -M 0 -M iBCBXb 1x2x3x4x5x6x-M 4x7 1 1 1 1 0 0 7 -M 6x10 2 -5 1 0 -1 1 5 -z 17M 3M+2 3-4M 2M-5 0 -M 0 -M 4x2 0 7/2 1/2 1 1/2 -1/2 4/7 2 1x5 1 -5/2 1/2 0 -1/2 1/2 - -z 2M-10 0 (7/2)M+8 0.5M-6 0 0.5M+1 -1.5M-1 3 2x4/7 0 1 1/7 2/7 1/7 -1/7 2 1x45/7 1 0 6/7 5/7 -1/7 1/7 -z -102/7 0 0 -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=7 2 1x-5 2x+ 3x- 5x+ 6x=10 1x,2x,3x,4x，5x,6x0 （单纯形表略）最优解X=（45/7，4/7，0，0，0 )T目标函数最优值min w=0 第二阶段单纯形表为：jc2 3 -5 0 iBCBXb 1x2x3x5x3 2x4/7 0 1 1/7 1/7 2 1x45/7 1 0 6/7 -1/7 -z -102/7 0 0 -50/7 -1/7 最优解是X=（45/7，4/7，0，0，0 )TMax z=102/7 （2）解法一：大 M 法z =-z 有 max z =-min （-z）=-min z 化成标准形：Max z=-21x-32x-3x+04x+05x-M6x-M7xS.T. 1x+42x+23x-4x+6x=4 31x+22x-5x+7x=6 1x,2x,3x,4x，5x,6x，7x0 （单纯性表计算略）线性规划最优解 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=10 1x+15 2x+12 3x+0 4x+0 5x+0 6x-M 7xs.t. 5 1x+3 2x+ 3x+ 4x=9 -5 1x+6 2x+15 3x+ 5x=15 2 1x+ 2x+ 3x- 6x+ 7x=5 1x,2x,3x,4x，5x,6x，7x0 单纯形表计算略当所有非基变量为负数，人工变量7x=0.5，所以原问题无可行解。两阶段法（略）（4）解法一：大 M 法单纯形法， （表略）非基变量4x的检验数大于零， 此线性规划问题有无界解。两阶段法略1.7 求下述线性规划问题目标函数z 的上界和下界；Max z=11c x+22c x11 11221a xa xb2112222a xa xb其中：113c，246c，1812b，21014b，1113a，1225a，2124a，2246a解：求 Z 的上界Max z=31x+62xs.t. -1x+22x12 21x+42x14 2x，1x0 加入松弛变量，化成标准型，用单纯形法解的，最优解X=（0，7/2，5，0 )T目标函数上界为z=21 存在非基变量检验数等于零，所以有无穷多最优解。求 z 的下界线性规划模型：Max Z= 1x+42xs.t. 31x+52x8 41x+62x10 2x，1x0 加入松弛变量，化成标准型，解得：最优解为X=（0，8/5，0，1/5 )T目标函数下界是z=32/5 1.8 表 1-6 是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，1a，2a，3a，d，1c，2c为待定常数，试说明这些常数分别取何值时，以下结论成立。（1）表中解为唯一最优解； （2）表中解为最优解，但存在无穷多最优解；（3） 该线性规划问题具有无界解；（4） 表中解非最优， 对解改进，换入变量为1x，换出变量为6x。基 b 1x2x3x4x5x6x3xd 4 1a1 0 2a0 4x2 -1 -3 0 1 -1 0 6x3 3a-5 0 0 -4 1 jjcz1c2c0 0 -3 0 解：（1）有唯一最优解时， d0，1c0，2c0 （2）存在无穷多最优解时，d0，1c0，2c=0 或 d0，1c=0，2c0. （3）有无界解时， d0，1c0，2c0 且10a（4）此时，有 d0，1c0 并且1c2c，30a，3/3ad/4 1.9 某昼夜服务的公交线路每天个时间段内所需司机和乘务员人数如下：班次时间所需人数1 6 点到 10点60 2 10点到 14 点70 3 14点到 18 点60 4 18点到 22 点50 5 22点到 2 点20 6 2 点到 6 点30 设司机和乘务人员分别在各时间区段一开始时上班，并连续上班 8 小时，问该公交线路至少配备多少司机和乘务人员。列出线型规划模型。解 ：设kx（k=1，2，3，4，5，6）为kx个司机和乘务人员第k 班次开始上班。建立模型：Min z=1x+2x+3x+4x+5x+6xs.t. 1x+6x60 1x+2x70 2x+3x60 3x+4x50 4x+5x20 5x+6x30 1x,2x,3x,4x,5x,6x0 1.10 某糖果公司厂用原料A、B、C 加工成三种不同牌号的糖果甲乙丙，已知各种糖果中 ABC 含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价如表所示：原料甲乙丙原 料成 本 （ 元 /千克）每 月限 制 用 量（千克）A 60% 15% 2 2000 B 1.5 2500 C 20% 60% 50% 1 1200 加工费0.5 0.4 0.3 售价3.4 2.85 2.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.63x0 -0.21x-0.22x+0.83x0 -0.854x+0.155x+0.156x0 -0.64x-0.65x+0.46x0 -0.77x-0.58x+0.59x0 1x+4x+7x2000 2x+5x+8x2500 3x+6x+9x1200 1x,2x,3x,4x,5x,6x,7x,8x,9x0 1.11 某厂生产三种产品I、III 。每种产品经过 AB 两道加工程序，该厂有两种设备能完成A 工序，他们以1A,2A表示；有三种设备完成B 工序，分别为1B，2B，3B；产品 I 可以在 AB 任何一种设备上加工，产品可以在任何规格的 A 设备上加工，但完成B 工序时，只能在1B设备上加工；产品III 只能在2A，2B上加工。已知条件如下表，要求安排最优生产计划，使该厂利润最大化。设备产品设备有效台时满负荷时的设备费用I II III 1A5 10 6000 300 2A7 9 12 10000 321 1B6 8 4000 250 2B4 11 7000 783 3B7 4000 200 原料费0.25 0.35 0.5 单价1.25 2.00 2.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件；1x+ 2x= 3x+ 4x+ 5x6x+ 7x= 8x建立数学模型：Max z=(1.25-0.25)*( 1x+ 2x)+(2-0.35)*( 6x+ 7x)+(2.8-0.5) 9x-(5 1x+10 6x)300/6000-(7 2x+9 7x+12 9x)321/10000-(6 3x+8 8x)250/4000-(4 4x+11 9x)783/7000-7 5x*200/4000 s.t 5 1x+10 6x6000 7 2x+9 7x+12 9x10000 6 3x+8 8x4000 4 4x+11 9x7000 7 5x4000 1x+ 2x= 3x+ 4x+ 5x6x+ 7x= 8x1x,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 饲料蛋白质（克）矿物质（克）维生素（毫克）价格（元 /公斤）1 3 1 0.5 0.2 2 2 0.5 1 0.7 3 1 0.2 0.2 0.4 4 6 2 2 0.3 5 18 0.5 0.8 0.8 解题分析：这是一道较简单的数学规划模型问题，根据题意写出约束即可。解题过程：12345min0.20.70.40.30.8zxxxxx12345123451234512345326187000.50.220.530.0.50.220.8100,0 xxxxxxxxxxstxxxxxx x xx x第二章（ 67页）2.1 用改进单纯形法求解以下线性规划问题。（1）Max z=61x-22x+33x21x-2x+33x21x+43x41x，2x，3x0 （2）min z=21x+2x31x+2x=3 41x+32x6 1x+22x3 1x,2x0 解：（1）先化成标准型：Max z=61x-22x+33x+04x+05xs.t. 21x-2x+23x+4x=2 1x+43x+5x=4 1x,2x,3x,4x,5x0 令0B=（4P，5P）=10010BX=（4x,5x )T,0BC=(0,0) 0N=(1P,2P,3P)=212104, 0NX=（1x，2x，3x )T0NC=(6,-2,3)，10B=1001,0b=24非基变量的检验数0N=0NC-0BC10B0N=0NC=(6,-2,3) 因为1x的检验数等于 6，是最大值，所以，1x为换入变量，10B0b=24；10B1P=21由规则得：=1 4x为换出变量。1B=(4P，5P)=2011,1BX=（1x,5x )T，1BC=(6,0). 1N=(4P,2P,3P), 1NX=（4x，2x，3x )T1NC=(0，-2，3)，11B=0.500.51,1b=13非基变量的检验数1N=（-3，1，-3）因为2x的检验数为 1，是正的最大数。所以2x为换入变量；10B2P=0.50.5由规则得：=6 所以5x是换出变量。2B=(1P，2P)=2110,2BX=（1x,2x )T，2BC=(6,-2). 2N=(4P,5P，3P), 2NX=（4x，5x，3x )T2NC=(0，0，3)，12B=0112,2b=46非基变量的检验数2N=（-2，-2，-9）非基变量的检验数均为负数，愿问题已达最优解。最优解 X= 46即：X=（4,6,0)T目标函数最优值max z=12 （2）解 ：Min z=21x+2x+03x+M4x+M5x+06xS.T. 31x+2x+4x=3 41x+32x-3x+5x=6 1x+22x+6x=3 1x,2x,3x,4x,5x, 6x0 M 是任意大的正数。（非基变量检验数计算省略）原问题最优解是X=（0.6，1.2，0）目标函数最优值：z=12/5 2.2 已知某线性规划问题，用单纯形法计算得到的中间某两步的加算表见表，试将空白处数字填上。jc3 5 4 0 0 0 BCBXb 1x2x3x4x5x6x5 2x8/3 2/3 1 0 1/3 0 0 0 5x14/3 -4/3 0 5 -2/3 1 0 0 6x20/3 5/3 0 4 -2/3 0 1 jc-jz-1/3 0 4 -5/3 0 0 . . . 2x15/41 8/41 -10/41 3x-6/41 5/41 4/41 1x-2/41 -12/41 15/41 jc-jz解：jc3 5 4 0 0 0 BCBXb 1x2x3x4x5x6x5 2x8/3 0 5x14/3 0 6x20/3 jc-jz. . . 5 2x80/41 0 1 0 15/41 4 3x50/41 0 0 1 -6/41 3 1x44/41 1 0 0 -2/41 jc-jz0 0 0 -45/41 2.3 写出下列线性规划问题的对偶问题。（1）min z= 2 1x+2 2x+4 3x2 1x+3 2x+5 3x2 3 1x+ 2x+7 3x3 1x+4 2x+6 3x5 1x,2x, 3x0（1）解：对偶问题是：Max w=21y-32y-53ys.t. 21y-32y-3y2 31y-2y-43y2 51y-72y-63y4 1y,2y,3y0 (2)max z= 1x+22x+3 3x+4 4x-1x+2x-3x-34x=5 61x+72x+33x-54x8 121x-92x-93x+94x20 1x,2x0;3x0;4x无约束解：对偶问题：Min w=51y+83y+204yS.t. -1y+63y+124y1 1y+73y-94y2 -1y+33y-94y3 -31y-53y+94y=4 1y无约束，3y0；4y0 （3）min z=11mnijijijc x1nijijxai=1,m 1mijjixbj=1,n ijx0 解：对偶问题 : max w=1miiia y+1njmjjb ys.t. iy+mjyijciy,mjy无约束 i=1,2,.m; j=1,2,.n (4) Max z=1njjjc x1nijjija xb, i=1,., 1mm1nijjija xb, i=111,2,.,mmmjx0,当 j=1，.，1nnjx无约束，当 j=11,.,nn解：Min w=1mjiib ys.t. 1mijiia yjcj=1,2,31n1mijiia yjcj=1n+1, 1n+2,.n iy0 i=1,2. 1miy无约束，i=1m+1, 1m+2.m 2.4 判断下列说法是否正确，并说明为什么. (1)如线性规划问题的原文题存在可行解，则其对偶问题也一定存在可行解。（2）如线性规划的对偶问题无可行解，则原问题也一定无可行解。（3）如果线性规划问题的原问题和对偶问题都具有可行解，则该线性规划问题一定有有限最优解。(1)错误，原问题有可行解，对偶问题可能存在可行解，也可能不存在；（2） 错误，对偶问题没有可行解， 原问题可能有可行解也可能有无界解；（3）错误，原问题和对偶问题都有可行解，则可能有有限最优解也可能有无界解；2.5 设线性规划问题1 是：Max 1z=1njjjc x1nijjija xb，i=1，2，m 0,1,2.,jxjn（*1,.,myy）是其对偶问题的最优解。又设线性规划问题2 是Max 21njjjzc x1nijjija xb+ik，i=1，2，m 0,1,2.,jxjn其中ik是给定的常数，求证：max2maxz1z+*1miiik y解：证明：把原问题用矩阵表示：Max 1z=CX s.t. AXb X0 b=（1b,2b.mb )T设 可行解为1X,对偶问题的最优解1Y=（1y，2ymy）已知。Max 2z=CX s.t. AXb+k X0 k=（1k,2k.mk)T设可行解为2X，对偶问题最优解是2Y,对偶问题是，Min w=Y(b+k) S.t. YA C Y 0 因为2Y是最优解，所以2Y（b+k）1Y（b+k）2X是目标函数2z的可行解， A2Xb+k ；2YA2X2Y（b+k）1Yb+Yk 原问题和对偶问题的最优函数值相等，所以不等式成立，证毕。2.6 已知线性规划问题Max z=112233c xc xc x11121axa12222axa13323axa410 x501x =12bb0,1,.,5jxj用单纯形法求解，得到最终单纯形表如表所示，要求：（1） 求11a，12a，13a，21a，22a，23a，1b，2b的值；（2） 求123,c cc的值；BXb1x2x3x4x5x3x3/2 1 0 1 1/2 -1/2 2x2 1/2 1 0 -1 2 jjcz-3 0 0 0 -4 解：（1）初始单纯形表的增广矩阵是：1C=111213121222321001aaabaaab最终单纯形表的增广矩阵为2C=1010.50.51.50.5101222C是1C作初等变换得来的，将2C作初等变换，使得2C的第四列和第五列的矩阵成为2C的单位矩阵。有：11a=9/2；12a=1；13a=4；21a=5/2；22a=1；23a=2；1b=9；2b=5 由检验计算得：1c=-3；2c=3c=0 2.7 已知线性规划问题Max z=21x+2x+53x+64xs.t. 21x+3x+4x8 21x+22x+3x+24x12 jx0，j=1,4 对偶变量1y，2y，其对偶问题的最优解是*1y=4，*21y，试应用对偶问题的性质，求原问题的最优解。解：对偶问题是：Min w=81y+122ys.t. 21y+22y2 22y1 1y+2y5 1y+22y6 1y，2y0 互补松弛性可知，如?X，?Y是原问题和对偶问题的可行解，那么，?YSX=0和SY?X=0，当且仅当?X，?Y是最优解。设 X,Y 是原问题和对偶问题的可行解，SY=（3y，4y，5y，6y）有：YSX=0; 且SYX=0 5x=6x=0，原问题约束条件取等号，3x=4；4x=4 最优解 X=（0，0，4，4)T目标函数最优值为44。2.8 试用对偶单纯形法求解下列线性规划问题。（1）min z=1x+2x21x+2x4 1x+72x7 1x,2x0 (2) min z=31x+22x+3x+44x21x+42x+53x+4x0 31x- 2x+73x-24x2 51x+22x+3x+104x15 1x,2x, 3x, 4x0 解：（1）取 w=-z，标准形式：Max w=-1x-2x+03x+04xs.t. -21x-2x+3x=-4 -1x-72x+4x=-7 1x，2x，3x，4x0 单纯形法求解（略）：最优解：X=（21/13，10/13，0，0)T目标函数最优值为31/13。（2）令： w=-z，转化为标准形式：Max w=-31x-22x-3x-44x+05x+06x+07xs.t. -21x-42x-53x-4x+5x=0 -31x+2x-73x+24x+6x=-2 -51x-22x-3x-64x+7x=-15 1x，2x，3x，4x，5x，6x，7x0 单纯形法略原问题最优解：X=（3，0，0，0，6，7，0)T目标函数最优值为9。2.9 现有线性规划问题max z=- 51x+52x+133x- 1x+2x+33x20 12 1x+42x+103x90 1x，2x，3x0 先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？（1） 约束条件 1 的右端常数 20变为 30 （2） 约束条件 2 的右端常数 90变为 70 （3） 目标函数中3x的系数变为 8 （4）1x的系数向量变为112（5） 增加一个约束条件21x+32x+53x50 （6） 将约束条件 2 变为 101x+52x+103x100 解：把原问题化成标准型的：Max z=-5 1x+5 2x+13 3x+0 4x+0 5xs.t - 1x+ 2x+3 3x+ 5x=20 12 1x+4 2x+10 3x+ 5x=90 1x，2x，3x，4x，5x0 单纯形法解得：最优解：X=（0，20，0，0，10)T目标函数最优值为100。非基变量1x的检验数等于 0，原线性问题有无穷多最优解。（1）约束条件的右端常数变为30 有1bBb因此bbb单纯形法解得：最优解：X=（0，0，9，3，0)T目标函数最优值为117。（2）约束条件 2 右端常数变为 70 有1bBb因此bbb单纯形法解得，最优解：X=（0，5，5，0，0)T目标函数最优值为90。（3）3x的系数变成 8，3x是非基变量，检验数小于0，所以最优解不变。（4）1x的系数向量变为051x是非基变量，检验数等于 -5，所以最优解不变。（5）解：加入约束条件3用对偶单纯形表计算得：X=（0，25/2，5/2，0，15，0)T目标函数最优值为95。（6）改变约束条件，345,P P P没有变化，线性规划问题的最优解不变。2.10 已知某工厂计划生产I,II,III 三种产品，各产品在 ABC 设备上加工， 数据如下表，设备代号I II III 每月设备有效台时A 8 2 10 300 B 10 5 8 400 C 2 13 10 420 单位产品利润/千元3 2 2.9 （1）如何充分发挥设备能力，使生产盈利最大？（2）如果为了增加产量，可借用其他工厂的设备B，每月可借用 60 台时，租金为 1.8 万元，问借用是否合算？（3）若另有两种新产品IV,V， 其中 IV 为 10 台时，单位产品利润 2.1 千元；新产品 V 需用设备 A 为 4 台时，B 为 4 台时，C 为 12 台时，单位产品盈利1.87千元。如A,B,C 设备台时不增加，分别回答这两种新产品投产在经济上是否划算？（4）对产品工艺重新进行设计，改进结构，改进后生产每件产品I，需要设备 A 为 9 台时，设备 B 为 12台时，设备 C 为 4 台时，单位产品利润 4.5 千元，问这对原计划有何影响？解：（1）设：产品三种产品的产量分别为，1x，2x，3x，建立数学模型：Max z=31x+22x+2.93xs.t. 81x+22x+103x300 101x+52x+83x400 21x+132x+103x420 1x,2x,3x0 把上述问题化为标准型，用单纯形法解得：最优解：X=（338/15，116/5，22/3，0，0，0)T目标函数最优值为2029/15。（2）设备 B 的影子价格为 4/15 千元/台时，借用设备的租金为0.3 千元每台时。所以，借用 B 设备不合算。（3）设备 V ,V 生产的产量为7x，8x，系数向量分别为：7(12,5,10)TP8(4, 4,12)TP检验数7=-0.06，所以生产V 不合算，8=37/300，生产 V 合算。单纯形法计算得：最优解：X=（107/4，31/2，0，0，0，0，55/4)T目标函数最优值为10957/80。（4）改进后 ,检验数1=253/300，大于零。所以，改进技术可以带来更好的效益。2.11 分析下列参数规划中当t 变化时最优解的变化情况。（1）Max ( ) tz=(3-6t) 1x+(2-2t) 2x+(5-5t) 3x(t0) s.t. 1x+22x+3x430 31x+23x460 1x+42x420 1x，2x，3x0 （2）Max ( ) tz=(7+2t)1x+(12+t) 2x+(10-t)3x(t0) s.t. 1x+2x+3x20 21x+22x+ 3x30 1x，2x，3x0 （3）Max ( ) tz=21x+2x(0 t 25) s.t. 1x10+2t 1x+2x25-t 2x10+2t 1x，2x0 （4）Max ( ) tz=211x+122x+183x+154x(0 t 59) s.t. 61x+32x+63x+34x30+t 61x-32x+123x+64x78-t 91x+32x-63x+94x135-2t 1x，2x，3x，4x0 解：（1）化成标准形式：Max ( ) tz=(3-6t) 1x+(2-2t) 2x+(5-5t) 3x+04x+05x+06x(t0) s.t. 1x+22x+3x+4x=430 31x+23x+5x=460 1x+42x+6x=420 1x，2x，3x，4x，5x, 6x0 令 t=0，用单纯形表计算，jc3-6t 2-2t 5-5t 0 0 0 iBCBXB 1x2x3x4x5x6x2-2t 2x100 -1/4 1 0 0.5 -1/4 0 - 5-5t 3x230 3/2 0 1 0 1/2 0 460 0 6x20 2 0 0 -2 1 1 20 -z 1350t -1350 t-4 0 0 t-1 2t-2 0 t 增大， t 大于 1，首先出现4，5大于 0，所以当 0t1 时有最优解。X=（0，100，230，0，0，20)T目标函数最优值为1350（t-1）（0t1） 。t=1 是第一临界点。t 大于 1 时，6x是换出变量。t 大于 1，最优解是： X=（0，0， 0，430，460，420)T目标函数最优值为Max ( ) tz=0，（t 大于 1）（2）化成标准型，然后令t=0，单纯形法解得：t 开始增大时，当 t 大于 8/3 时，首先出现4大于 0，所以 0t8/3，得最优解。目标函数最优值Max ( ) tz=220， （0t8/3）所以， t=8/3 为第一临界点。当 8/3t5，首先1大于 0，8/3t5 的时候，最优解为：X=（0，15，0，5)T目标函数最优值为180+15t ， （8/35 时，1x是换入变量，2x为换出变量，单纯性法计算，当 t 继续增大，所有检验数都非正，所以当t5，最优解：X=（15，0，0，5)T目标函数最优值为105+30t， t0 (3)化成标准型，令 t=0,用单纯形法计算得：当 t 开始增大， t 大于 5 时，首先出现2b小于 0，当 0t5，最优解为：X=（10+2t，0，10+2t，5-t，0)T目标函数最优值为6t+30 ， （0t5） 。所以 t=5 是第一临界点。当 t 大于 5 时，4x是换出变量，5x是换入变量。用对偶单纯形法计算，当 t 大于 5 时，最优解为：X=（10+2t，15+t，0，0，t-5)T目标函数最优值为35+5t。（4）解：先化为标准型，令t=0，用单纯形法计