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

2023/1/151运筹学

OPERATIONSRESEARCH

2023/1/152第一、二章习题课图解法单纯形法大M法、两阶段法写出对偶规划用对偶理论证明一些简单的问题灵敏度分析参数规划建立数学模型2023/1/153例1

请用大M法或两阶段法求解下列线性规划问题解：大M法2023/1/1542-12000-M-M-Mb-M6111-100100-M2-2010-10010-M002-100-10012-M3M-12+M-M-M-M000-M6103/2-101/210-1/2-M2-2010-10010-1001-1/200-1/2001/22-M05M/2-M-MM/200-M/22023/1/155-M3400-13/21/21-3/2-1/222-2010-10010-11-1100-1/2-1/201/21/25+4M00M3M/2M/20-5M/2-M/22-12000-M-M-Mb23/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-由表可知，而对应系数列，故该问题为无界解。2023/1/156解：两阶段法（1）构造第一阶段问题，并求解。2023/1/157000000111b16111-10010012-2010-100101002-100-10011-3-111100016103/2-101/210-1/212-2010-100100001-1/200-1/2001/210-5/211-1/2003/22023/1/15813400-13/21/21-3/2-1/202-2010-1001001-1100-1/2-1/201/21/2-4001-3/2-1/205/25/2000000111b03/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/8000000111由表可知最优目标值为0，人工变量全部出基，故原问题有可行解。继续进行第二步。2023/1/1592-12000b23/4100-1/43/81/827/2001-1/2-1/41/4-17/4010-1/4-1/8-3/80005/4-3/8-9/8（2）去掉人工变量，求解第二步由表可知，而对应系数列，故该问题为无界解。2023/1/1510解：大M法2023/1/1511101512000-Mb095311000015-56150100-M521100-1110+2MM+1512+M00-M0109/513/51/51/500002409161100-M7/50-1/53/5-2/50-1109-M/58+3M/5-2-2M/50-M02023/1/1512101512000-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-M0由表可知所有，但人工变量未出基，故原问题无可行解。2023/1/1513例3：书P49，1.14，分析问题例4：书P49，1.15证明例5：书P48，1.12解：设在设备上生产的产品Ⅰ的数量是，i=1，2；j=1，2，3。在设备上生产的产品ІІ的数量是。在设备上生产的产品Ш

的数量是。则：2023/1/1514约束条件目标函数2023/1/1515例6：书P76，2.1（b,d)写出对偶规划解：令，则原问题转化为：2023/1/1516对偶规划为或2023/1/1517运输问题的数学模型解：对应于第一组约束的对偶变量为，对应于第二组约束的对偶变量为。，

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

（3）正确。2023/1/1520例7：已知有线性规划问题如下用单纯形法求得最终表如下：3/2015/14-3/14110-1/72/700-5/14-25/142023/1/1521试进行如下分析：（1）直接写出对偶问题的最优解；（2）目标系数在什么范围内变化时，上述最优解不变；（3）约束条件右端项在什么范围内变化时，上述最优解不变；（4）目标函数变为上述最优解的变化；（5）约束条件右端项变为上述最优解的变化。2023/1/1522解：（1）对偶问题的最优解（2）设目标函数中的系数为，则要使得最优解不变，则需，即由此可得：2023/1/1523（3）设第一个约束的右端常数项为，则要使得最优基不变，则需，即（4）设目标函数中的系数为，则检验数2023/1/1524所以最优解发生变化，选择进基，继续迭代：3/2015/14-3/14110-1/72/7002/7-18/741221/5014/51-3/58/512/501/50-4/50-12/5012所以新最优解为2023/1/1525（5）设右端常数项为，则最终表中，b列数值为：显然已不是可行解，用对偶单纯形法继续迭代-1/7015/14-3/1427/710-1/72/700-5/14-25/145102/30-14/3-5/3111/314/31/300-25/3-10/30010所以新最优解为2023/1/1526例8：已知某厂生产甲、乙、丙三种产品，有关数据如下表，试分别回答下列问题。

产品消耗定额原料甲乙丙原料拥有量A63545B34530单件利润415（1）建立模型，求使该厂获利最大的生产计划；（2）若有一种新产品丁，其原材料消耗定额：A：3单位，B：2单位，单件利润2.5单位，问该产品是否值得安排生产？若值得，求新的最优生计划；(3)若原材料A市场紧缺，除拥有量外一时无法购进，而B数量不足可购买，市场单价0.5，该厂应否购买，购进多少为宜？2023/1/1527解（1）假设甲、乙、丙三种产品的产量分别是，建立模型如下：用单纯形法求解的最终表如下：41500b451-1/301/3-1/353011-1/52/50-8/30-1/3-2/32023/1/1528（2）增加产品丁的产量为，将有关数据列在第6列，415002.5b451-1/301/3-1/31/353011-1/52/51/50-8/30-1/3-2/31/6所以值得安排生产。2023/1/1529415002.5b451-1/301/3-1/31/353011-1/52/51/50-8/30-1/3-2/31/62.5153-101-1150-3/56/51-2/53/50-1/2-5/20-1/2-1/20故新的最优解是2023/1/1530（3）因为原材料B的影子价格是，所以值得购进。设购进量为，反映到最终表中即为：41500b41-1/301/3-1/35011-1/52/50-8/30-1/3-2/3使最优解不变的参数范围是：，

目标函数是：

（1）当时，，重新迭代后得2023/1/153141500b0-310-1156/53/511/500-20-10最优解是：目标函数是：所以最佳购进量为15。2023/1/1532例9：分析下述参数规划问题中，当变化时最优解的变化情况，及目标函数随参数的变化。1100b011/201/21121/21-3/201/203/20解：令求得最优解如下：2023/1/153311b11/201/21121/21-3/201/2-03/2-20将参数变化反映到最终表使最优解不变的参数范围是：，目标函数是：

（1）当