《运筹学》精品课程
习 题 集
二○○六年六月三十日
0
目 录
第一章 线性规划 ................................................................................ 1 第二章 运输问题 ................................................................................ 9 第三章 整数规划 .............................................................................. 14 第四章 目标规划 .............................................................................. 20 第五章 动态规划 .............................................................................. 21 第六章 图与网络分析 ...................................................................... 24 第七章 存储论................................................................................... 27 第八章 对策论................................................................................... 28
1
第一章 线性规划
1、将下列线性规划问题化为标准型
(1) max Z = 3x1+ 5x2- 4x3+ 2x4
?2x1? 6x2- x3? 3x4 ? 18??x1- 3x2? 2x3- 2x4 ? 13 s.t.??-x1? 4x2- 3x3- 5x4 ? 9? x1, x2, x4 ? 0? (2) min f = 3x1+ x2+ 4x3+ 2x4 ≤ 1
? 2x1? 3x2- x3- 2x4 ? -51?? 3x1- 2x2? 2x3- x4 ? -7 s.t.?? 2x1? 4x2- 3x3? 2x4 ? 15? x1 , x2? 0, x4 ? 0?(3) min F=x1+x2+x3+x4
?x1?x4??x1?x2???s.t.?x2?x2??x3?x4????x1,x2,x3,5687x4?0
(4) minF?x1?3x2?x3
?x1+x2+x3?3??-x1+2x2?2 s.t.??-x1+5x2+x3?4?x1,x2,x3?0?2、求出下列不等式组所定义的多面体的所有基本解和基本可行解（极点）：
?2x1? 3x2? 3x3? 6??-2x1? 3x2? 4x3? 12?x1,x2,x3? 0?
３、用图解法求解下列线性规划问题
(1)maxZ?X1?X2?2x1- x2? 6??3x1+ 2x2?12s.t.??x1? 3?x1,x2?0?
1
(2)minZ??x1?3x2?4x1? 7x2? 56?s.t.?3x1- 5x2? 15?x1,x2? 0?
４、在以下问题中，列出所有的基，指出其中的可行基，基础可行解以及最优解。
maxZ?2x1?x2?x3?x1? x2?2x3?6 s.t.??x1?4x2-x3?4??x1,x2,x3?0maxZ?X1?X2?3x1+2x2?13?s.t.?x2+3x3?17 ??2x1+x2+x3=13??x1,x2,x3?05、用单纯形法求解以下线性规划问题
(1)maxZ?3x1?2x2?2x1- 3x2? 3s.t.?
?-x1? x2? 5??x1,x2?0(2)maxZ?x2?2x3?x1? 3x2? 4x3? 12s.t.? ?2x2- x3? 12??x1,x2,x3? 0 （３） max z = x1 +2 x2 +3 x3
x1 + 2x2 + 3x3≤8
s.t. 4x1 + 5x3≤12 x1，x2 ，x3 ≥0
（４） max z = 3x1 + x2
x1 + x2 ≤4
s.t.
－x1 + x2 ≤2 6x1 + 2x2≤18
x１ ，x2 ≥0
（５） max z = 5x1 + 2 x2 + 4 x3
2
s.t.
3 x1 + x2 + 2 x3 ≤ 4 6 x1 + 3 x2 + 5 x3 ≤ 10 x1，x2，x3 ≥ 0
６、试用大M法或两阶段求下述线性规划问题的最优解和最优值
（３） max z = 3x1 – 3 x2 x1 + x2 ≥1
2x1 + 3x2 ≤6
x1，x2 ≥0
（4）maxz?2x1?x2?2x3
?x1?x2?x3?6???2x1?x3?2s.t.??2x2?x3?0?x,x,x?023?1
7、写出下列问题的对偶规划
maxZ?2x1?2x2minf??x1?2x2?x3??x1?x2?x3?2?2x1?x2?x3??4（3）s.t.? （4）??2x?x?x?1s.t.?x1?2x2?6?123?x,x,x?0?x,x,x?0?123?123
8、试用对偶理论讨论下列原问题与它们的对偶问题是否有最优解
3