运筹学习题集

《运筹学》精品课程

习 题 集

二○○六年六月三十日

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