1、运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题a） 1212min z=346.,0xst解：由图 1 可知，该问题的可行域为凸集 MABCN，且可知线段 BA 上的点都为最优解，即该问题有无穷多最优解，这时的最优值为 min3z=20P47 1.3 用图解法和单纯形法求解线性规划问题a） 1212mx z=05349.8,st解：由图 1 可知，该问题的可行域为凸集 OABCO，且可知 B 点为最优值点，即 ，即最优解为1122349358xx*31,2Tx这时的最优值为 max5z=0单纯形法：原问题化成标准型为 123124max z=059.8,xstjc10 5 0
2、0BCXb 1x23x40 3x9 3 4 1 00 48 5 2 0 1jjCZ10 5 0 00 3x21/5 0 14/5 1 -3/510 18/5 1 2/5 0 1/5jjCZ0 1 0 -25 2x3/2 0 1 5/14 -3/1410 11 1 0 -1/7 2/7jjCZ0 0 -5/14 -25/14所以有 *max3351,1022TxzP78 2.4 已知线性规划问题： 12341243124ax869,0zxx求: (1) 写出其对偶问题；（2）已知原问题最优解为 ，试根据对)0,42(*X偶理论，直接求出对偶问题的最优解。解：（1）该线性规划问题的对偶问题为： 1
3、23412431234min8691,0wyyy（2）由原问题最优解为 ，根据互补松弛性得：),(*X12431yy把 代入原线性规划问题的约束中得第四个约束取严格不等号，)0,42(*X即 89y从而有1234y得 12344,05y所以对偶问题的最优解为 ，最优值为*3(,1)5Tymin16wP79 2.7 考虑如下线性规划问题： 123123123min604804,0zxxx（1）写出其对偶问题；（2）用对偶单纯形法求解原问题；解：（1）该线性规划问题的对偶问题为： 123123123max4608,wyy（2）在原问题加入三个松弛变量 把该线性规划问题化为标准型：456,x1231
4、23456ma08040,jzxxjc-60 -40 -80 0 0 0BCXb 1x23x45x60 4x-2 -3 -2 -1 1 0 00 5-4 -4 -1 -3 0 1 00 6x-3 -2 -2 -2 0 0 1jjCZ-60 -40 -80 0 0 00 4x1 0 -5/4 5/4 1 -1/12 080 11 1 1/4 3/4 0 -1/4 00 6x-1 0 -3/2 -1/2 0 -1/2 1jjCZ0 -25 -35 0 -15 00 4x11/6 0 0 5/3 1 1/3 -5/680 15/6 1 0 2/3 0 -1/3 1/640 2x2/3 0 1 1/3
5、 0 1/3 -2/3jjCZ0 0 -80/3 0 -20/3 -50/3*max5523(,),64863TxzP81 2.12 某厂生产 A、B、C 三种产品，其所需劳动力、材料等有关数据见下表。要求：（a）确定获利最大的产品生产计划；（b）产品 A 的利润在什么范围内变动时，上述最优计划不变；（c）如果设计一种新产品 D，单件劳动力消耗为 8 单位，材料消耗为 2 单位，每件可获利 3 元，问该种产品是否值得生产？ （d） 如果劳动力数量不增，材料不足时可从市场购买，每单位 0.4 元。问该厂要不要购进原材料扩大生产，以购多少为宜。A B C 可用量（单位）劳动力材 料6 3 53 4
6、 54530产品利润（元/件） 3 1 4解：由已知可得，设 表示第 种产品，从而模型为：jxj123123max465.30,zstxa) 用单纯形法求解上述模型为：jc3 1 4 0 0产品资源消 耗定 额BCXb 1x23x45x0 4x45 6 3 5 1 00 530 3 4 5 0 1jjCZ3 1 4 0 00 4x15 3 -1 0 1 -14 36 3/5 4/5 1 0 1/5jjCZ3/5 -11/5 0 0 -4/53 1x5 1 -1/3 0 1/3 -1/34 33 0 1 1 -1/5 2/5jjCZ0 -2 0 -1/5 -3/5得到最优解为 ；最优值为*(5,
7、3)Txmax35427zb）设产品 A 的利润为 ，则上述模型中目标函数 的系数用 替代并求1x3解得： jc31 4 0 0BCBXb 1x23x45x3 1x5 1 -1/3 0 1/3 -1/34 33 0 1 1 -1/5 2/5jjCZ-2 0 -1/5 -3/5jj0 -2+ /3 0 -1/5- /3-3/5+ /3要最优计划不变，要求有如下的不等式方程组成立解得：2031503395从而产品 A 的利润变化范围为： ,即39,524,5C）设产品 D 用 表示，从已知可得6x16/5BcP166283455把 加入上述模型中求解得：6xjc3 1 4 0 0 3BCXb 1x
8、23x45x63 1x5 1 -1/3 0 1/3 -1/3 24 33 0 1 1 -1/5 2/5 -4/5jjCZ0 -2 0 -1/5 -3/5 1/53 6x5/2 1/2 -1/6 0 1/6 -1/6 14 35 2/5 13/15 1 -1/15 4/15 0jjCZ-1/10 -59/30 0 -7/30 -17/30 0从而得最优解 ；最优值为*(0,5,/2)Txmax54327.z所以产品 D 值得生产。d）P101 3.1 已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最优解及最小运费。表 3-35B1 B2 B3 B4 产量A1A2A31012227
9、142091611201815255销量 5 15 15 10解：由已知和最小元素法可得初始方案为B1 B2 B3 B4 产量A1A2A3 5150 1501015255销量 5 15 15 10检验：由于有两个检验数小于零，所以需调整，调整一：B1 B2 B3 B4 产量A1A2A3 5150 15 10015255销量 5 15 15 10检验：产地 销地产地 销地产地 销地由于还有检验数小于零，所以需调整，调整二：B1 B2 B3 B4 产量A1A2A3 5510 1510015255销量 5 15 15 10检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为： min257109510835z表 3-36B1 B2 B3 B4 产量A1A2A386549314427372526销量 10 10 20 15解：因为 ，即产大于销，所以需添加一个假想的销地，销34118ijab量为 3，构成产销平衡问题，其对应各销地的单位运费都为 0。产地 销地产地 销地
