运筹(第一、二章习题课)

1、2022-3-171运筹学运筹学OPERATIONS RESEARCH2022-3-172第一、二章第一、二章 习题课习题课n图解法图解法n单纯形法单纯形法n大大M 法、两阶段法法、两阶段法n写出对偶规划写出对偶规划n用对偶理论证明一些简单的问题用对偶理论证明一些简单的问题n灵敏度分析灵敏度分析n参数规划参数规划n建立数学模型建立数学模型2022-3-173例例1 1 请用大请用大M M法或两阶段法求解下列线性规划问题法或两阶段法求解下列线性规划问题0,02226.22max) 1 (3213231321321xxxxxxxxxxtsxxxz解解：大大M法法0,.02226.22max9196

2、32853174321987321xxxxxxxxxxxxxxxtsMxMxMxxxxz2022-3-1742-12000-M-M-Mb-M6111-100100-M2-2010-10010-M002-100-10012-M3M-12+M-M-M-M0009x8x7x6x5x4x3x2x1xBXBC9x8x7x-M6103/2-101/210-1/2-M2-2010-10010-1001-1/200-1/2001/22-M05M/2-M-MM/200-M/22x8x7x2022-3-175-M3400-13/21/21-3/2-1/222-2010-10010-11-1100-1/2-1/20

3、1/21/25+4M00M3M/2M/20-5M/2-M/22-12000-M-M-Mb9x8x7x6x5x4x3x2x1xBXBC2x3x7x23/4100-1/43/81/81/4-3/8-1/827/2001-1/2-1/41/41/2-3/4-1/4-17/4010-1/4-1/8-3/81/41/83/80005/4-3/8-9/8-M-M-M-2x3x1x由表可知由表可知 ，而对应系数列，而对应系数列 ，故该问题为无界，故该问题为无界解。解。0404P2022-3-176解解：两阶段：两阶段法法0,.02226.min919632853174321987xxxxxxxxxxxxxx

4、xtsxxxw（1）构造第一阶段问题，并求解。）构造第一阶段问题，并求解。2022-3-177000000111b16111-10010012-2010-100101002-100-10011-3-11110009x8x7x6x5x4x3x2x1xBXBC9x8x7x16103/2-101/210-1/212-2010-100100001-1/200-1/2001/210-5/211-1/2003/22x8x7x2022-3-17813400-13/21/21-3/2-1/202-2010-1001001-1100-1/2-1/201/21/2-4001-3/2-1/205/25/200000

5、0111b9x8x7x6x5x4x3x2x1xBXBC2x3x7x03/4100-1/43/81/81/4-3/8-1/807/2001-1/2-1/41/41/2-3/4-1/407/4010-1/4-1/8-3/81/41/83/80000001112x3x1x由表可知由表可知 最优目标值为最优目标值为0，人工变量全部出基，故原问题有，人工变量全部出基，故原问题有可行解。继续进行第二步。可行解。继续进行第二步。2022-3-1792-12000b23/4100-1/43/81/827/2001-1/2-1/41/4-17/4010-1/4-1/8-3/80005/4-3/8-9/86x5x

6、4x3x2x1xBXBC2x3x1x（2）去掉人工变量，求解第二步）去掉人工变量，求解第二步由表可知由表可知 ，而对应系数列，而对应系数列 ，故该问题为无界，故该问题为无界解。解。0404P2022-3-17100,52151565935.121510max)2(321321321321321xxxxxxxxxxxxtsxxxz解：大解：大M法法0,.52151565935.121510max7176321532143217321xxxxxxxxxxxxxxxtsMxxxxz2022-3-1711101512000-Mb095311000015-56150100-M521100-1110+2M

7、M+1512+M00-M07x6x5x4x3x2x1xBXBC7x5x4x109/513/51/51/500002409161100-M7/50-1/53/5-2/50-1109-M/58+3M/5-2-2M/50-M07x5x1x2022-3-1712101512000-Mb103/2139/8003/16-1/8000123/209/1611/161/1600-M1/20-43/800-7/16-3/80-110-43M/800-7M/16-3M/80-M07x6x5x4x3x2x1xBXBC7x3x1x由表可知所有由表可知所有 ，但人工变量未出基，故原问题无可行，但人工变量未出基，故原问

8、题无可行解。解。0j2022-3-1713例例3：书：书P49，1.14， 分析问题分析问题 例例4：书：书P49，1.15 证明证明例例5：书：书P48，1.12 解解：设在设备：设在设备 上生产的产品上生产的产品的数量是的数量是 ，i=1，2；j=1，2，3。在设备。在设备 上生产的产品上生产的产品的数量的数量是是 。在设备。在设备 上生产的产品上生产的产品 的数量是的数量是 。则：则：jiBA,ijxjiBA,ijyjiBA,ijz2022-3-1714约约束束条条件件0,4000)(7700011)(440008)(610000129)(7600010)(523132222122121

9、11222123222121131211ijijijzyxxxzxxyxxzyxxxyxxx)(705. 011)(411. 08)(606. 0129)(703. 010)(505. 0)50. 080. 2()( )35. 000. 2()(25. 025. 1 (max2313222212212111222123222111131211222111232221131211xxzxxyxxzyxxxyxxxzyyxxxxxxz目目标标函函数数2022-3-1715例例6：书：书P76，2.1（b,d) 写出对偶规划写出对偶规划00837435522365max)(3213213213213

10、21xxxxxxxxxxxxxxxzb，无约束，321yyy解解：令：令 ，则原问题转化为：，则原问题转化为：00837435522365max)(321321321321321xxxxxxxxxxxxxxxzb，无约束，033xx2022-3-171600332675254835min321321321321321yyyyyyyyyyyyyyyw，无约束，对偶规划为对偶规划为或或00332675254835min321321321321321yyyyyyyyyyyyyyyw，无约束，2022-3-17170)2(,.,2 , 1) 1 (,.2 , 1min)(1111ijmijijnjii

11、jninjijijxnjbxmiaxxczc运输问题的数学模型运输问题的数学模型 解解：对应于第一组约束的对偶变量为对应于第一组约束的对偶变量为 ，对应于第二，对应于第二 组约束的对偶变量为组约束的对偶变量为 。 ， 于是对偶规划为于是对偶规划为 iyjzmi,.2 , 1nj,.,2 , 12022-3-17180, 0.111112211111jimnnmmmnnzyczyczyczyczyczynjjjmiiizbyaw11max或或 njjjmiiizbyaw11maxnjmizyczyjiijji,.1,.10, 02022-3-1719例例7：书：书P76，2.2 判断下列各种说法

12、是否正确判断下列各种说法是否正确 ，为什么？，为什么？（1 1）如果线性规划问题的原问题存在可行解，则对偶问题也）如果线性规划问题的原问题存在可行解，则对偶问题也一定存在可行解。一定存在可行解。（2 2）若某线性规划的对偶问题无可行解，则原问题为无界解。）若某线性规划的对偶问题无可行解，则原问题为无界解。（3 3）在互为对偶的一对问题中，不论原问题是求最大还是求）在互为对偶的一对问题中，不论原问题是求最大还是求最小，原问题目标函数值一定不超过对偶问题的目标函数值。最小，原问题目标函数值一定不超过对偶问题的目标函数值。解解：（1) 1) 错错 , , 原问题是无界解时，对偶问题无可行解原问题是无

13、界解时，对偶问题无可行解. . (2) (2) 错错 , , 原问题可能是原问题可能是无界解无界解，也可能，也可能无可行解。无可行解。 （3 3）正确。）正确。2022-3-1720例例7：已知有线性规划问题如下已知有线性规划问题如下 0,825943510max21212121xxxxxxxxz用单纯形法求得最终表如下：用单纯形法求得最终表如下：3/2015/14-3/14110-1/72/700-5/14-25/141x2x3x4x1x2x2022-3-1721试进行如下分析：试进行如下分析：（1）直接写出对偶问题的最优解；）直接写出对偶问题的最优解；（2）目标系数）目标系数 在什么范围内

14、变化时，上述最优解不变；在什么范围内变化时，上述最优解不变；（3）约束条件右端项）约束条件右端项 在什么范围内变化时，上述最优在什么范围内变化时，上述最优解不变；解不变；（4）目标函数变为）目标函数变为 上述最优解的变化；上述最优解的变化；（5）约束条件右端项变为）约束条件右端项变为 上述最优解的变化。上述最优解的变化。1c1b21510maxxxz19112022-3-1722解解： （1）对偶问题的最优解）对偶问题的最优解)1425,145(),(21yy（2）设目标函数中）设目标函数中 的系数为的系数为 ，则要使得最优解不，则要使得最优解不变，则需变，则需 ，即，即1x1c0, 0430

15、7214157/214/3), 5(00714257/114/5), 5(0114113cccc由此可得：由此可得：2254151 c2022-3-1723（3）设第一个约束的右端常数项为）设第一个约束的右端常数项为 ，则要使得最优基，则要使得最优基不变，则需不变，则需 ，即，即1b01bB00716771214587/27/114/314/5111bbb165241b（4）设目标函数中的系数为）设目标函数中的系数为 ，则检验数，则检验数)4 ,12(),(21cc072414127/214/3)12, 4(007271214207/114/5)12, 4(0432022-3-1724所以最优

16、解发生变化，选择所以最优解发生变化，选择 进基，继续迭代：进基，继续迭代：3x3/2015/14-3/14110-1/72/7002/7-18/71x2x3x4x1x2x41221/5014/51-3/58/512/501/50-4/50-12/51x3x012所以新所以新 最优解为最优解为0,521, 0,584321xxxx2022-3-1725（5）设右端常数项为）设右端常数项为 ，则最终表中，则最终表中，b列数值为：列数值为：T19,11727717387111457145519117/27/114/314/5显然已不是可行解，用对偶单纯形法继续迭代显然已不是可行解，用对偶单纯形法继续

17、迭代-1/7015/14-3/1427/710-1/72/700-5/14-25/141x2x3x4x1x2x5102/30-14/3-5/3111/314/31/300-25/3-10/301x4x010所以新所以新 最优解为最优解为3/2, 0, 0, 3/114321xxxx2022-3-1726例例8：已知某厂生产甲、乙、丙三种产品，有关数据如下表，已知某厂生产甲、乙、丙三种产品，有关数据如下表，试分别回答下列问题试分别回答下列问题 。 产品 消耗定额原料甲乙 丙原料拥有量A63545B34530单件利润415（1 1）建立模型，求使该厂获利最大的生产计划；）建立模型，求使该厂获利最大

18、的生产计划；（2 2）若有一种新产品丁，其原材料消耗定额：）若有一种新产品丁，其原材料消耗定额：A A：3 3单位，单位，B B：2 2单位，单件利润单位，单件利润2.52.5单位，问该产品是否值得安排生产？若单位，问该产品是否值得安排生产？若值得，求新的最优生计划；值得，求新的最优生计划；(3)(3)若原材料若原材料A A市场紧缺，除拥有量外一时无法购进，而市场紧缺，除拥有量外一时无法购进，而B B数量数量不足可购买，市场单价不足可购买，市场单价0.50.5，该厂应否购买，购进多少为宜？，该厂应否购买，购进多少为宜？2022-3-1727解解（1 1）假设甲、乙、丙三种产品的产量分别是假设甲

19、、乙、丙三种产品的产量分别是 ，建立模型如下：建立模型如下： 321,xxx0,305434553654max321321321321xxxxxxxxxxxxz用单纯形法求解的最终表如下：用单纯形法求解的最终表如下： 41500b451-1/301/3-1/353011-1/52/50-8/30-1/3-2/31x2x3x4x1x3x5xBCBX2022-3-1728（2 2）增加）增加产品丁的产量为产品丁的产量为 ，将有关数据列在第，将有关数据列在第6 6列，列，6x415002.5b451-1/301/3-1/31/353011-1/52/51/50-8/30-1/3-2/3 1/61x2

20、x3x4x1x3x5xBCBX6x51312352513131616PBP0616所以值得安排生产。所以值得安排生产。2022-3-1729415002.5b451-1/301/3-1/31/353011-1/52/51/50-8/30-1/3-2/31/61x2x3x4x1x3x5xBCBX6x2.5153-101-1150-3/56/51-2/53/50-1/2-5/20-1/2-1/206x3x故新的最优解是故新的最优解是15, 0, 0, 06321xxxx2022-3-1730（3 3）因为原材料）因为原材料 B B 的影子价格是的影子价格是 ，所以值得，所以值得购进。设购进量为购进

21、。设购进量为 ，反映到最终表中即为：，反映到最终表中即为：21322y41500b41-1/301/3-1/35011-1/52/50-8/30-1/3-2/31x2x3x4x1x3x5xBCBX35523使最优解不变的参数范围是：使最优解不变的参数范围是： ， 目标函数是：目标函数是： （1 1）当）当 时，时， ，重新迭代后得，重新迭代后得 1501501 b635z5 . 054max321xxxz2022-3-173141500b0-310-1156/53/511/500-20-101x2x3x4x5x3x5xBCBX15915, 0, 0, 0, 054321xxxxx最优解是：最优解是： 目标函数是：目标函数是： 所以最佳购进量为所以最佳购进量为1515。245z2022-3-1732例例9 9：分析下述参数规划问题中，当：分析下述参数规划问题中，当 变化时最优解的变化变化时最优解的变化情况，及目标函数随参数的变化。情况，及目标函数随参数的变化。0,.,532222)(min414214314321xxxxxxxxxxxxz1100b011/201/21121/21-3/201/203/201x2x3x4x4x2xBCBX解解：令：令 求得最优解如下：求得最优解如下：01,