《运筹学》清华版-5-01整数规划的数学模型及解的特点

第一节整数规划的数学模型及解的特点整数规划数学模型的一般形式整数规划的例子解的特点整数规划IntegerProgramming,简称IP.一、整数规划数学模型的一般形式我们只研究整数线性规划(integerlinearprogramming)。一般形式：.整数线性规划分类纯整数线性规划（PIP）混合整数线性规划（MIP）0-1（二进制）整数线性规划（BIP）

.二、整数规划的例子例1、某服务部门各时段（每2h为一时段）需要的人员数如下：时段12345678需求数10891113853按规定，服务员连续工作8h（4时段）为一班。现要求安排服务员的工作时间，使服务员总数最少。.

上班下班解：设在第j时段开始时上班的服务员人数为xj。第1时段初第4时段末第2时段初第3时段初第4时段初第5时段初第5时段末第6时段末第7时段末第8时段末x1x2x3x4x5.各时段服务员数供求情况：时段服务员总数需求数1234567810891113853x1x1+x2x1+x2+x3x1+x2+x3+x4x2+x3+x4+x5x3+x4+x5x4+x5x5≥≥≥≥≥≥≥≥.目标：PIP问题约束：.例2、现有资金总额为B。可供投资的项目有n个，项目j所需投资额和预期收益分别为aj和cj。此外，有三个附加条件：1、若选项目1，就必须选项目2；反之则不一定；2、项目3和4中至少选一个；3、项目5、6、7中恰好选两个。

应如何投资，使总预期收益最大？用0－1变量表示选择：1——选；0——不选.解：设决策变量.约束：1、若选项目1，就必须选项目2；反之则不一定；满足此约束的项目1、2全部选择组合.约束：2、项目3和4中至少选一个；项目3、4的全部选择组合.约束：3、项目5、6、7中恰好选两个；.约束：4、总金额限制——总金额为B项目j的实际投资额=.项目j的实际收益=.模型：BIP问题或0－1规划问题.总结：1、n中至多选k个2、n中至少选k个3、n中恰好选k个4、选i＝>

选j.例3、（选址问题）工厂A1和A2生产某种物资，现希望在A3或者A4处再建一家工厂。需求地有四个：B1、B2、B3、B4。生产量、需求量及单位运价cij如下表所示：cijB1B2B3B4生产能力A12934400A28357600A37612200A44525200需求350400300150.工厂A3或A4开工后，每年生产费估计A3——1200万元/年，A4——1500万元/年。问：应建在哪里，才能使总费用最低？.解：设xij——Ai

运往Bj的数量cijB1B2B3B4A1x11x12x13x14A2x21x22x23x24A3x31x32x33x34A4x41x42x43x44.cijB1B2B3B4生产能力A1x11x12x13x14400A2x21x22x23x24600A3x31x32x33x34200A4x41x42x43x44200需求350400300150供需平衡∑=需求平衡∑=∑=∑=供应平衡∑=∑=？.难点——“不可兼或”分析：若在A3建工厂，则

x31＋x32＋

x33＋

x34＝200（1）若不在A3建工厂，则

x31＋x32＋

x33＋

x34＝0（2）（1）与（2）可统一表示成

x31＋x32＋

x33＋

x34＝200y1其中y1是0－1变量.难点——“不可兼或”分析：若在A4建工厂，则

x41＋x42＋

x43＋

x44＝200（3）若不在A4建工厂，则

x41＋x42＋

x43＋

x44＝0（4）（3）与（4）可统一表示成

x41＋x42＋

x43＋

x44＝200y2其中y2是0－1变量.难点——“不可兼或”分析：A3与A4不可兼＝>y1+y2=1＝>y2=1－y1因此：二选一时候也常常只引入一个0－1变量y即可.综上：A3与A4中选一处建厂可表示成x31＋x32＋

x33＋

x34＝200yx41＋x42＋

x43＋

x44＝200（1－y）这里y＝1表示选A3，y＝0表示选A4.目标：min（运费＋生产费）运费cijB1B2B3B4生产能力A12934400A28357600A37612200A44525200需求350400300150x11x12x13x14x21x22x23x24x31x32x33x34x41x42x43x44.

A3生产费＝

A4生产费＝.模型MIP问题.练习：背包问题背包可再装入8单位重量，10单位体积物品物品名称重量体积价值12345书摄像机枕头休闲食品衣服53124214352030101815假设如果装，每件只能装1件。如何装，使总价值最大？.解：Xi为是否带第i种物品maxZ=20X1+

30X2+10X3+18X4+15X55X1+3X2+X3+2X4+4X582X1+X2+4X3+3X4+5X510Xi为0,1.推广——背包问题一般形式：,整数(1)、Xi为i物品携带数量

ai为i物品单位重量

ci为i物品重要性估价

b为最大负重一维背包问题.LP最优解(18/7,19/7)最优值94