五、用割平面法求解

六、下列整数规划问题

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

答：不考虑整数约束，求解相应线性规划得最优解为 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 Ⅱ Ⅲ Ⅳ word文档可自由复制编辑

第二章 线性规划问题的基本概念 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

word文档可自由复制编辑

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