五、用割平面法求解

六、下列整数规划问题

说明能否用先求解相应的线性规划问题然后四舍五入的办法来求得该整数规划的一个可行解。

答：不考虑整数约束，求解相应线性规划得最优解为 x1=10/3，x2=x3=0，用四舍五人法时，令x1=3，x2=x3=0，其中第2个约束无法满足，故不可行。

七、若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。使总的钻探费用为最小。若10个井位的代号为S1,S2．?，S10相应的钻探费用为C1 ,C2 ,? C10，并且井位选择要满足下列限制条件：

(1)在s1，s2，S4中至多只能选择两个； (2)在S5，s6中至少选择一个；(3)在s3，s6，S7，S8中至少选择两个； 试建立这个问题的整数规划模型

八、有四项工作要甲、乙、丙、丁四个人去完成．每项工作只允许一人去完成。每个人只完成其中一项工作，已知每个人完成各项工作的时间如下表。问应指派每个人完成哪项工作，使总的消耗时间最少?

工作 人 甲 乙 丙 丁 15 19 6 19 18 23 7 21 2l 22 16 23 24 18 19 17 I Ⅱ Ⅲ Ⅳ

第二章 线性规划问题的基本概念 3、本章典型例题分析

例： maxZ?20x1?15x2 用单纯形法求解 S?t? 2x1?3x2?600

2x1?x2?400

x1,x2?0

解：先化为标准形式：maxZ?20x1?15x2 S?t? 2x1?3x2?x3?600

2x1?x2?x4?400

xj?0(j?1,2,3,4)

把标准形的系数列成一个表 基 S X1 X2

X3 S 1 -20 -15 0 X3 0 2 3 1 X4 0 2 1 0

第一次迭代：调入x1,调出x4 基 S X1 X2 X3 S 1 0 -5 0 X3 0 0 2 1 X1 0 1 1/2 0 第二次迭代：调入x2,调出x3 基 S X1 X2 X3 S 1 0 0 5/2 X2 0 0 1 1/2 X1 0 1

0

-1/4

X4 0 0 1 X4 10 -1 1/2 X4 15/2 -1/2 3/4

解 0 600 400

解 4000 200 200 解 4500 100 150

?Zmax

x1?150x2?100?4500

4、本章作业

见本章练习题 3、本章典型例题分析

例：写出下列线性规划问题的对偶问题

maxZ?3x1?x2?4x3?6x1?3x2?5x3?25 ?S?t??3x1?4x2?5x3?20?x?0(j?1,2,3)?j

解：其对偶问题为：

minW?25y1?20y2?6y1?3y2?3?3y?4y?1 ?2S?t??1?5y1?5y2?4??y1,y2?04、本章作业

见本章练习题

二、写出下列线性规划问题的对偶问题：

（1） maxZ?2x1?x2?3x3?x4

s.t. 2x?x?3x3??4 12x1?x3?x4?1x1?x2?x3?x4?5

x1,x3?0,x2,x4无约束（2） minZ?2x1?2x2?4x3

s.t. 3x?x?7x3?3 12

x1?4x2?6x3?5x2?0,x3?02x1?3x2?5x3?2

管理运筹学复习

一、 考虑下列线性规划（20分） MaxZ=2X1+3X2 2X1+ 2X2+X3=12 X1+2X2 +X4=8

4X1 +X5=16 4X2 +X6=12 Xj≥0（j=1,2,…6） 其最优单纯形表如下： 基变量 X1 X2 X3 X4 X5 X6 X3 0 0 0 1 -1 -1/4 0 X1 4 1 0 0 0 1/4 0 X6 4 0 0 0 -2 1/2 1 X2 2 0 1 0 1/2 -1/8 0 σj 0 0 0 -3/2 -1/8 0 1）当C2=5时，求新的最优解 2）当b3=4时，求新的最优解

3）当增加一个约束条件2X1+X2≤12，问最优解是否发生变化，如果发生变化求新解？

解当C2=5时 σ4=－5/2

σ5=1/8＞0所以最优解发生变化 基变量 X1 X2 X3 X4 X5 X6 0 X3 0 0 0 1 -1 -1/4 0 2 X1 4 1 0 0 0 1/4 0 0 X6 4 0 0 0 -2 1/2 1 5 X2 2 0 1 0 1/2 -1/8 0 σj 0 0 0 -5/2 1/8 0 0 X3 2 0 0 1 －2 0 1/2 2 X1 2 1 0 0 1 0 -1/2 0 X5 8 0 0 0 -4 1 2 5 X2 3 0 1 0 0 0 1/4 σj 0 0 0 -2 0 -1/4 最优解为X1=2，X2=3,Z＝19 2）当b3=4时 基变量 X1 X2 X3 X4 X5 X6 0 X3 3 0 0 1 -1 -1/4 0

2 X1 1 1 0 0 X6 -3 0 0 3 X2 5/2 0 1 σj 0 0 0 X3 9/2 0 0 2 X1 1 1 0 0 X4 3/2 0 0 3 X2 7/4 0 1 σj 0 0 此时最优解为X1=1，X2=7/4,Z＝29/4 3)增加一个约束条件 基变量 X1 X2 X3 X3 0 0 0 1 X1 4 1 0 0 X6 4 0 0 0 X2 2 0 1 0 X7 12 2 1 0 σj 0 0 0 X3 0 0 0 1 X1 4 1 0 0 X6 4 0 0 0 X2 2 0 1 0 X7 2 0 0 0 σj 0 0 0 由于X7＝2大于0，所以最优解不变

0 0 0 0 1 0 0 0 0 0 -2 1/2 -3/2 0 0 1 0 0 1/4 1/2 -1/8 -1/8 -1/2 1/4 -1/4 0 -1/2 0 1 0 0 1 0 -1/2 1/4 -3/4 X4 -1 0 -2 1/2 0 -3/2 -1 0 -2 1/2 －1/2 -3/2 X5 -1/4 1/4 1/2 -1/8 0 -1/8 -1/4 1/4 1/2 -1/8 －3/8 -1/8 X6 0 0 1 0 0 0 0 0 1 0 0 0 X7 0 0 0 0 1 0 0 0 0 0 1 0