内容发布更新时间 : 2024/5/22 18:48:11星期一 下面是文章的全部内容请认真阅读。

SAT) X2 + X3 + X4 +X5 + X6 >= 90 SUN) X3 + X4 + X5 + X6 + X7 >= 90 END GIN 7

其中“GIN 7”表示7个变量都是一般整数变量。 （仍然默认为取值是非负的）

求解后状态窗口

中与整数相关的三个域有了相关结果:

“Best IP ：94”表示当前得到的最好的整数解的目标函数值为94（人）。 “IP Bound ：93.5” 表示该整数规划目标值的下界为93.5 （人）。 “Branches ：1”表示分枝数为1（即在第1个分枝中就找到了最优解）。 我们前面说过，LINDO求解IP用的是分枝定界法。

显然，上面第二条“整数规划目标值的下界为93.5 （人）”表明至少要聘用93.5名员工，由于员工人数只能是整数，所以至少要聘用94（人）。而第一条说明目前得到的解就是聘用94（人），所以已经是最优的了。

求解结果的报告窗口如下：

LP OPTIMUM FOUND AT STEP 8

OBJECTIVE VALUE = 93.3333359

SET X2 TO >= 4 AT 1, BND= -94.00 TWIN= -93.50 18

NEW INTEGER SOLUTION OF 94.0000000 AT BRANCH 1 PIVOT 18

BOUND ON OPTIMUM: 93.50000 DELETE X2 AT LEVEL 1

ENUMERATION COMPLETE. BRANCHES= 1 PIVOTS= 18 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION...

OBJECTIVE FUNCTION VALUE 1) 94.00000

VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 4.000000 1.000000 X3 40.000000 1.000000 X4 2.000000 1.000000

- 21 -

X5 34.000000 1.000000 X6 10.000000 1.000000 X7 4.000000 1.000000 ROW SLACK OR SURPLUS DUAL PRICES MON) 0.000000 0.000000 TUE) 2.000000 0.000000 WED) 8.000000 0.000000 THU) 0.000000 0.000000 FRI) 0.000000 0.000000 SAT) 0.000000 0.000000 SUN) 0.000000 0.000000

NO. ITERATIONS= 18

BRANCHES= 1 DETERM.= 1.000E 0

报告窗口中前两行告诉我们：在8次迭代后找到对应的线性规划（LP）问题的最优解，最优值=93.3333359。 LINDO求解IP用的是分枝定界法，紧接着几行显示的是分枝定界的信息，在第1个分枝中设定x2>=4,并在该分枝中找到了整数解，而且就是全局整数最优解，所以算法停止。旋转迭代（PIVOT）共18次。

后面显示的是最后的最优解：x=(0,4,40,2,34,10,4).

松弛和剩余变量（SLACK OR SURPLUS）仍然可以表示约束的松紧程度，但目前IP尚无相应完善的敏感性分析理论，因此REDUCED COST和DUAL PRICES的结果在整数规划中意义不大。

2. 游泳队员的选拔问题 在LINDO模型窗口中输入模型：

MIN 66.8x11+75.6x12+87 x13+58.6x14 +57.2x21+66 x22+66.4x23+53 x24 +78 x31+67.8x32+84.6x33+59.4x34 +70 x41+74.2x42+69.6x43+57.2x44 +67.4x51+71x52+83.8x53+62.4x54 SUBJECT TO

x11+x12+x13+x14 <21 x21+x22+x23+x24 <=1 x31+x32+x33+x34 <21 x41+x42+x43+x44 <=1 x11+x21+x31+x41+x51 =1 x12+x22+x32+x42+x52 =1 x13+x23+x33+x43+x53 =1 x14+x24+x34+x44+x54 =1 END INT 20

- 22 -

其中“INT 20”表示20个变量都是0-1整数变量。

求解得到结果为：x14 = x21 = x32 = x43 = 1, 其它变量为0，成绩为253.2（秒）=4’13”2。即应当选派甲乙丙丁4人组成接力队，分别参加自由泳、蝶泳、仰泳、蛙泳的比赛。

由于这个问题中有20个0-1变量，而最优解中肯定只有其中的4个变量取非零值“1”，所以要在一大堆变量中去找少量的几个取非零值的变量，这是不太方便的。有没有办法只把取非零值的变量显示出来呢？

这是可以做到的：选择菜单命令“Reports | Solution… (Alt+0)”（这个命令的功能是要把最优解显示出来），这时会弹出一个选择对话框（图2-21），缺省的选项是“Nonzeros Only （只显示非零值）”。按下对话框中的“OK”按钮，则报告窗口中的只显示取非零值的变量，这样阅读起来就很方便了。

请注意，这个功能并不仅仅在整数规划中可以使用，在其他模型中也是可以使用的，不妨试试就知道了。

讨论：若考虑到丁、戊最近的状态，c43 由原来的69.6变为75.2（秒），c54由原来的62.4变为57.5（秒）, 试讨论对结果的影响。

这类似于线性规划中的敏感性分析, 但是可惜的是，对于整数规划模型，一般没有与线性规划相类似的理论，此时LINDO中所输出的敏感性分析结果通常是没有意义的，因此不能利用这个输出的敏感性分析结果。

于是我们只好用c43，c54 的新数据重新输入模型，用LINDO求解得到：x21 = x32 = x43 = x51 = 1, 其它变量为0，成绩为257.7（秒）=4’17”7。即应当选派乙丙丁戊4人组成接力队，分别参加蝶泳、仰泳、蛙泳、自由泳的比赛。

3. 汽车生产计划（混合整数规划）

一汽车厂生产小、中、大三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润以 及每月工厂钢材、劳动时间的现有量如下表所示：

钢材（吨） 劳动时间（小时） 利润（万元） 小型 1.5 280 2 中型 3 250 3 大型 5 400 4 现有量 600 60000 由于各种条件限制，如果生产某一类型汽车，则至少要生产80辆。试制订月生产计划，使工厂的利润最大。

设每月生产小、中、大型汽车的数量分别为x1, x2, x3，（由于生产是一个月一个月连续进行的，所 以这里可以合理地认为这个产量不一定非取整数不可，而是可以取实数）设工厂的月利润为z, 在题目所给参数均不随生产数量变化的假设下，立即可得线性规划模型：

- 23 -

Maxz?2x1?3x2?4x3st.1.5x1?3x2?5x3?600280x1?250x2?400x3?60000x1,x2,x3?0 但是，如果生产某一类型汽车，则至少要生产80辆，这个约束怎么表达？可以引入0-1变量，化为整数规划。设y1只取0, 1两个值，则“x1=0 或80”等价于

x1?My1,x1?80y1,y1?{0,1}其中M为相当大的正数，本例可取1000（x1不可能超过1000）。 类似地有

x2?My2,x31?My3,x2?80y2,x3?80y3,y2?{0,1}y3?{0,1}于是这个模型构成一个混合整数规划模型（既有一般的实数变量x，又有0-1变量y），用LINDO直接求解时，输入的最后（END语句后）只需要加上0-1变量y的限定语句。 在LINDO模型窗口中输入模型：

max 2 x1 + 3 x2 + 4 x3 st

1.5 x1 + 3 x2 + 5 x3 < 600 280 x1 + 250 x2 +400 x3 < 60000

x1 - 1000 y1 < 0 x2 - 1000 y2 < 0 x3 - 1000 y3 < 0 x1 - 80 y1 > 0 x2 - 80 y2 > 0 x3 - 80 y3 > 0 end

int y1 int y2 int y3

求解得到输出如下 ： OBJECTIVE FUNCTION VALUE 1) 611.2000

VARIABLE VALUE REDUCED COST Y1 1.000000 108.800003 Y2 1.000000 0.000000 Y3 0.000000 0.000000 X1 80.000000 0.000000 X2 150.399994 0.000000 X3 0.000000 0.800000

- 24 -

ROW SLACK OR SURPLUS DUAL PRICES 2) 28.799999 0.000000 3) 0.000000 0.012000 4) 920.000000 0.000000 5) 849.599976 0.000000 6) 0.000000 0.000000 7) 0.000000 -1.360000 8) 70.400002 0.000000 9) 0.000000 0.000000 NO. ITERATIONS= 25

BRANCHES= 1 DETERM.= 1.000E 0

即：只生产小型和中型汽车，产量分别为80辆和150辆(近似值),可获得最大利润611.2万元。 不妨试试把产量x也限定只取整数，结果会如何呢？

4. 注意

尽管LINDO 对整数规划问题很有威力, 但要想有效地使用，有时还是需要一定的技巧的。这是因 为, 人们很容易将一个本质上很简单的问题列成一个不太好的输入模型, 从而有可能会导致一个冗长的分枝定界计算。遗憾的是，我们往往难以预先估计什么样的模型才能避免冗长的分枝定界计算，也难以判别什么样的模型是“不太好”的输入模型。当然这时 LINDO 会主动砍去一些计算过程, 以缩短计算时间，而且越是高版本的LINDO软件，这种自动处理的“智能”越强。我们的建议是：如果分枝定界计算时间很长仍得不到最优解，你可以试试对输入模型进行一些等价变换：如交换变量的次序，交换约束的顺序等，有时也许会对减少求解所需的时间有所帮助。 五、实验步骤

1.启动lindo软件

2.验证教材教材《运筹学基础及应用》上第四章整数规划几个例子。 3.根据实际问题建立线性规划模型

4.按照lindo软件在线性规划中灵敏度分析的使用说明将所建立的线性规划模型运用lindo软件求解整数线性规划。 六、实验结果

例1 求下述整数线性规划问题的最优解：

maxz?3x1?2x2?2x1?3x2?14 ?s..t?x1?0.5x2?4.5?x,x?012?x1,x2均取整数值

例2 有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间(h)如表（通常称为效率矩阵）所示。

- 25 -