运筹习题参考答案

《实用管理运筹学》

习题参考答案

沈阳航空航天大学 2010年6月

目 录

第2章 线性规划及其对偶问题 ..................................................................................... 1 第3章整数规划与运输问题 ......................................................................................... 20 第4章 目标规划 ........................................................................................................... 40 第5章 动态规划方法的基本思想及应用 ................................................................... 50 第7章 对策论模型 ....................................................................................................... 58 第10章 决策分析 ......................................................................................................... 67

第2章 线性规划及其对偶问题

2.1 用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解？

maxZ?4x1?3x2maxZ?x1?2x2?x1?2x2?6? 2x1 ? x2?10?3x?2x?12 ??3x?2x?6 （2） （1）

??212s..t?1s..t?? x2?2? x1 ? x2?6???x1?0,x2?0?x1,x2?0 minZ?3x1?2xmaxZ?x1?x2（3）

?x1?2x2?2 （4）

?s..ts..t?x1?x2??1?x,x?0 ?12? x1? x2? 1 ??2x1?3x2?6?x,x?0 ?12解：各线性规划模型的图解如下。

有惟一最优解 有无穷多最优解

有无界解 无可行解

1

第2章 线性规划及其对偶问题

2.2 将下列线性规划模型化为标准形式并列出初始单纯形表。

minz?x1?2x2?4x3maxs?zk/pk??3x1?2x2?2x3?19?zk??n?maikxiki?1k?1??4x?3x?4x?14 （2） ?（1） m?1?23s..t?s..t??k?1?xik??1,?i5x?2x?4x??2623??1xik?0,?i,k??x1?0,x2?0,x3无约束??解：（1）令x1'??x1,x3?x3'?x3\,z'??z，则得到标准型为（其中M为一个任

意大的正数）

maxz'??2x1'?2x2?4x3'?4x3''?0x4?0x5?Mx6?Mx7?3x1'?2x2?2x3'?2x3''?x4?19?4x'?3x?4x'?4x''?x?x?14?123356s..t??5x1'?2x2?4x3'?4x3''?x7?26??x1',x2,x3',x3'',x4,x5,x6,x7?0初始单纯形表如表2-1所示：

表2-1 cj CB 0 -M -M XB x4 x6 x7 -z b 19 14 26 -2 2 x2 2 3 2 2+5M 4 x3'

-4 0 x4 1 0 0 0 0 x5 0 -1 0 -M -M x6 0 1 0 0 -M x7 0 0 1 0 x1' 3 [ 4 ] 5 -2+9M x3'' -2 -4 -4 -4-8M ? 19/3 14/4 26/5 2 4 4 4+8M

（2）在上述问题的约束条件中加入人工变量x1,x2,?,xn，得到标准型

maxs?m1pk?i?1?k?1xik?M?i?1xi

nmn?x?xi?1(i?1,2,?,n)?s..t??k?1ik??xik?0,xi?0(i?1,2,?,n;k?1,2,?,m)其中，M是一个任意大的正数。初始单纯形表如表2-2所示：

2