运筹学习题及解答（熊义杰版）

《运筹学》习题及其解答

目录

《运筹学》习题及其解答 .............................................. 1

第一章 线性规划 ........................................................................................................... 1 第二章 对偶规划及灵敏度分析 ........................................................................................... 12 第三章 运输问题 ................................................................................................................... 17 第四章 整数规划 ................................................................................................................... 22 第五章 动态规划 ................................................................................................................... 27 第六章 图与网络分析 ........................................................................................................... 34

第一章 线性规划

1.1将下列线性规划模型转化为标准型：

（1）Min.Z?4x1?6x2 （2）Min.Z??x1?2x2

S.t.?3x1?x2?6?x?2x?10?12 S.t.?7x?6x?42?1??x1,x2?0?3x1?5x2?70??2x?5x?50?12 ??3x?2x?3012??x1?0?【解】（1）—Max(?Z)??4x1?6x2

S.t.?3x1?x2?s1?6?x?2x?s?10?122 ?7x?6x?412???x1,x2,s1,s2?0（2）—Max(?Z)??y1?2u?2v

S.t.??3y1?5u?5v?s1?70?2y?5u?5v?50?1 ?3y?2u?2v?301??y1,u,v?0?1.2 用图解法解下列线性规划问题：

(1)Min.Z?6x1?4x2 （2）Max.Z?4x1?8x2

S.t.?2x1?x2?1??3x1?4x2?3 S.t.?x,x?0?12?x1?x2?5???x1?x2?8 ?x,x?0?12(1)Max.Z?x1?x2 （2）Max.Z?3x1?9x2

S.t.?8x1?6x2?24??4x1?6x2??12 S.t.?x?0,x?22?1?x1?3x2?22???x1?x2?4 ?2x?5x?012???x1?0,0?x2?6【解】应用图解法得到：

2－（1）题图解

2－（2）题图解

2－（3）题图解

2－（4）题图解

1.3 用图解法解下列线性规划问题，并指出所有的基本可行解及相应的目标函数值：

(1)Min.Z?3x1?7x2 （2）Max.Z?5x1?3x2

S.t.?2x1?5x2?10??3x1?x2?8 S.t.?x,x?0?12?3x1?4x2?16??2x1?x2?8 ?x?0,0?x?42?1

【解】（1）图解法(略)。设：

x1=x2=0，则当：x3=-10，x4=-8时，z=0 x1=x3=0，则当：x2=2，x4=-6时，z=14 x1=x4=0，则当：x3=30，x2=8时，z=56

x3=x2=0，则当：x1=5，x4=7时，z=15

x2=x4=0，则当：x3=-14/3，x1=8/3时，z=8

x3=x4=0，则当：x1=90/39，x2=14/13时，z=188/13

基本可行解为：Z(0,8,30,0)?56；Z(5,0,0,7)?15；Z(（2）图解法(略)。设：

3014188,,0,0)?

131313x1=x2=0，则当：x3=16，x4=8时，z=0 x1=x3=0，则当：x2=4，x4=4时，z=-12 x1=x4=0，则当：x3=16，x2=8时，z=-48

x3=x2=0，则当：x1=16/3，x4=-8/3时，z=80/3 x2=x4=0，则当：x3=4，x1=4时，z=8

x3=x4=0，则当：x1=16/5，x2=8/5时，z=56/5

基本可行解为：Z(0,0,16,8)?0；Z(0,4,0,4)??12；Z(4,0,4,0)?8；

16856Z(,,0,0)?

5551.4 请写出下列线性规划问题的所有基本解，指出那些属于基本可行解，并确定最优的目标

函数值。

Min.Z?5x1?2x2?3x3?2x4

S.t.?x1?2x2?3x3?4x4?7 ??2x1?2x2?x3?2x4?3?x?0(j?1,2,3,4)?j【解】列出2*2子矩阵，并列出基与基本解如下：

（x1，x2）当：x1=-4，x2=11，x3=x4=0时：Z?-42 （x1，x3）当：x1=2/5，x2=0，x3=11/5，x4=0时：Z?43/5 （x1，x4）当：x1=-1/3，x2=x3=0，x4=11/6时：Z?2 （x2，x3）当：x1=0，x2=1/2，x3=2，x4=0时：Z?5 （x2，x4）当：x1=0，x2=-1/2，x3=0，x4=2时：Z?5 （x3，x4）当：x1=0，x2=0，x3=1，x4=1时：Z?5

其中属于基本可行解的是：（x1，x3），（x2，x3），（x3，x4）所对应的解，最优目标

函数值为5。

1.5 试应用单纯形方法解下列线形规划问题：

(1)Max.Z?2x1?3x2 （2）Min.Z??x1?x2

S.t.?x1?2x2?6??x1?x2?4 S.t.?x,x?0?12?x1?x2?1??x1?x2?2 ?x,x?0,?12

【解】（1）将原线性规划问题化为标准型：

Max.Z?2x1?3x2

?x1?2x2?x3?6??x1?x2?x4?4 ?x,x,x,x?0?1234 0 6 4 -9 3 1 -10 2 2 x1 2 1 1 x1 1/2 1/2 x2 3 1 x2 0 1 x3 0 0 x3 -1/2 1/2 -1 x3 -1/2 3/2 -2 x4 0 0 1 x4 0 0 1 x4 -1 -1 2 R 3 4 R 6 2 R S.t.可得到单纯形表： Z x3 x4 Z x2 x4 Z x2 x1 （2） 1 因为检验数有大于0，所以进行换基迭代得： （1/2） 0 x1 0 0 1 x2 0 1 0 因为检验数有大于0，所以进行再次换基迭代得： 检验数已经没有正数，达到最优。 当：x1=2，x2=2，x3=x4=0时,Z=10 （2）将原线性规划问题化为标准型：

?Max.(?Z)?x1?x2

?x1?x2?x3?1??x1?x2?x4?2 ?x,x,x,x?0,?1234x1 x2 x3 x4 R S.t.可得到单纯形表：

本文来源：https://www.bwwdw.com/article/olnf.html