整数规划模型教学课件

1、3 整数规划模型 在一个数学规划模型中，如果它的某些决策变量或全部变量要求取整数时，就称这个数学规划模型为整数规划模型。整数规划模型可分为整数线性规划模型与整数非线性规划模型。整数规划又分为整数规划、混合整数规划及0-1规划。整数规划模型的一般形式例3.1 某航空公司为满足客运量日益增长的需要，欲购置一批新的远程及短程客机。每架客机价格6300万元，中程客机5000万元，短程客机3500万元。该公司现有资金7.5亿元可用于购买飞机。估计年净利润每架远程客机为420万元，中程客机300万元，短程客机230万元。该公司现有熟练驾驶员可用来配备30架新飞机。维修设备足以维修新增加40架新的短程客机，

2、每架中程客机的维修量相当于4/3架短程客机，而每架远程客机的维修量相当于5/3架短程客机。为获取最大利润，该公司应购买各类客机多少架？用Lindo软件求解例3.2 合理下料问题 某钢管零售商从钢管厂家进货，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原料钢管都是19m. 1）现有一客户需要50根4m、20根6m和15根8m的钢管，应如何下料最节省？1）问题的分析。 首先，应当确定哪些切割模式是可行的。所谓一个切割模式，是指按照客户需要在原料上安排切割的一种组合。例如：我们可以将19m的钢管切割成3根4m的钢管，余料为7m；或者将19m的钢管切割成4m、6m和8m的钢管各1根，余料为1m

3、。显然，可行的切割模式是很多的。 其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小此寸。例如：将19m的钢管切割成3根4m的钢管是可行的，但余料为7m，可以进一步将7m的余料切割成4m钢管（余料为3m），或者将7m的余料切割为6m钢管（余料为1m）。在这种合理性假设下，切割模式一共有7种，如表3.1所示表3.1 钢管下料的合理切割模式4m钢管根数6m钢管根数8m钢管根数余料m模式14003模式23101模式32013模式41203模式51111模式60301模式70023问题化为在满足客户需要的条件下，按照哪些合理的模式，切割多少根原料钢

4、管最为节省。而所谓最为节省，可以有两种标准：一是切割后剩余的总余料量最小，二是切割原料钢管的总根数最少。下面将对这两个目标分别讨论。2）模型建立。决策变量：用表示按第种模式切割的原料钢管的根数，显然它们应当是非负整数。目标函数：以切割后剩余的总余料量最少为目标，则由表3.1可得 z1=3x1+x2+3x3+3x4+x5+x6+3x7 以切割原料钢管的总根数最少为目标，则有 z2=x1+x2+x3+x4+x5+x6+x7下面分别在这两种目标下求解。3）模型求解分别将目标函数与约束条件构成整数线性规划模型输入Lindo求解。2）该客户除需要1）中的三种钢管外还需要10根5m的钢管。应如何下料最节省

5、？1）问题分析。按照问题1）的思路，可以通过枚举法首先确定哪些切割模式是可行的。但由于需求的钢管规格增加到4种，所以枚举法的工作量较大。下面介绍的整数非线性规划模型，可以同时确定切割模式和切割计划，是带有普遍性的方法。 同问题1）类似，一个合理的切割模式的余料不应该大于和等于客户需要的钢管的最小尺寸(本题中为4m)，切割计划中只使用合理的切割模式，而由于本题中的参数都是整数，所以合理的切割模式的余量不能大于3m。此外，这里我们仅选择总根数最少为目标进行求解。2）模型建立。 决策变量：由于不同切割模式不能超过3种，可以用xi表示按照第i种模式(i=1,2,3)切割的原料钢管的根数，显然它们应当是

6、非负整数。设所使用的第i种切割模式下每根原料钢管生产4m,5m,6m和8m的钢管数量分别为r1i,r2i,r3i和r4i(均为非负整数)。3)模型求解。以上模型是一个整数非线性规划模型，我们用Lingo软件求解。0-1整数规划模型例3.3 指派问题。在实际工作中，常常会碰到这样的问题：要派n个人去完成n项不同的任务，每人必须而且只需完成其中一项。但由于各人的专长不同，完成各项任务的效率也就不同，因此就产生这样一个问题，应指派哪个人去完成哪项任务，使总的效率最高或总的花费时间最少？今欲指派甲、乙、丙、丁四人加工A、B、C、D四种不同零件，每人加工四种零件分别所需要的时间如表3.2所示。问应该指派

7、每人加工何种零件使总的花费时间最少？表3.2 工人加工零件的工作效率ABCD甲4658乙61074丙78119丁9386例3.4 选址问题某公司拟在市东、西、南三区建立门市部，假设三个区共有7个位置点Ai (i=1,2,7)可供选择，且规定：东区只能在A1,A2,A3中至多选两个点；西区只能在A4,A5两个点中至少选一个点；南区只能在A6,A7中至少选一个点。 如选用Ai，设备投资估计为bi元，每年可获利润估计为ci元，问在投资不得超过b元的条件下，怎样选址可使公司年利润最大？ 假设投资总额b为1000万元，设备投资估计bi与每项投资每年获利ci,列于表3.3，试求最优选址方案。表3.3 投资估计与年获利