习题详解.doc

《实用管理运筹学教程2009年5月第2章 线性规划及其对偶问题 1 第3章整数规划与运输问题 20 第4章 目标规划 38 第5章 动态规划方法的基本思想及应用 48 第6章 非线性规划简介 56 第7章 对策论模型 63 第8章 排队论模型 72 第9章 存储论模型 82 第10章 决策分析 89 第11章 图论与网络计划 97 第2章 线性规划及其对偶问题 2.1 用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解？ （1） （2） （3） （4） 解：各线性规划模型的图解如下。 有惟一最优解 有无穷多最优解 有无界解 无可行解 2.2 将下列线性规划模型化为标准形式并列出初始单纯形表。 （1） （2） 解：（1）令，则得到标准型为（其中M为一个任意大的正数） 初始单纯形表如表2-1所示： 表2-1 cj -2 2 4 -4 0 0 -M -M ( CB XB b x2 x4 x5 x6 x7 0 x4 19 3 2 2 -2 1 0 0 0 19/3 -M x6 14 [ 4 ] 3 4 -4 0 -1 1 0 14/4 -M x7 26 5 2 4 -4 0 0 0 1 26/5 -z -2+9M 2+5M 4+8M -4-8M 0 -M 0 0 （2）在上述问题的约束条件中加入人工变量，得到标准型 其中，M是一个任意大的正数。初始单纯形表如表2-2所示： 表2-2 cj -M -M … ( CB XB b x1 xn x11 x1m xn1 xnm -M x1 1 1 0 1 1 0 0 -M x2 1 0 0 0 0 0 0 -M xn 1 0 1 0 0 1 1 -s 0 0 +M +M +M +M 2.3 用单纯形法求解下列线性规划问题。 （1） （2） 解：（1）最优解为。 （2）最优解为。 2.4 分别用大M法和两阶段法求解下列线性规划问题。 （1） （2） 解：（1）最优解为。 （2）最优解为。 2.5 写出下列线性规划的对偶问题，并用单纯形法或对偶单纯形法求出对偶问题的最优解。 （1） （2） 解：（1）将原问题化为： 设y1,y2,y3分别为三个约束条件对应的对偶变量，则原问题的对偶问题为 整理后得 求解此问题的初始单纯形表及最终单纯形表分别为表2-3和表2-4。 表2-3 初始单纯形表 cj 2 -3 -5 0 0 0 ( CB XB b y1 y2 y3 y4 y5 y6 0 y4 2 2 -3 -1 1 0 0 1 0 y5 2 [ 3 ] -1 -4 0 1 0 2/3 0 y6 4 5 -7 -6 0 0 1 4/5 -z 2( -3 -5 0 0 0 表2-4 最终单纯形表 cj 2 -3 -5 0 0 0 ( CB XB b y1 y2 y3 y4 y5 y6 0 y4 2/3 0 -7/3 5/3 1 -2/3 0 2 y1 2/3 1 -1/3 -4/3 0 1/3 0 0 y6 2/3 0 -16/3 -4/3 0 -5/3 1 -z 0 -7/3 -7/3 0 -2/3 0 所以，原问题的对偶问题最优解为(2/3,0,0)T,w*=4/3。 （2）令三个约束条件的对偶变量分别为y1,y2,y3，则根据对偶问题的转换法则可直接得到原问题的对偶问题 令，则对偶问题转化为 利用单纯形方法求解此模型（求解过程略），可得此对偶问题无最优解。 2.6 已知线性规划问题 其对偶问题最优解为。试用对偶理论找出原问题最优解。 解：先写出它的对偶问题 将代入约束条件可知，第2、3、4个约束为严格不等式，因此，由互补松弛性得。又因为，所以原问题的两个约束条件应取等式，因此有 ( 故原问题最优解为。 2.7 某单位加工制作100套工架，每套工架需用长为2.9m、2.1m和1.5m的圆钢各一根。已知原材料长7.4m。问如何下料使得所用的原材料最省？ 解：简单分析可知，在每一根原材料上各截取一根2.9m,2.lm和1.5m的圆钢做成一套工架，每根原材料剩下料头0.9m，要完成100套工架，就需要用100根原材料