资源描述：
《运筹学课件 第一节 整数规划的数学模型及解的特点.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、0－1规划指派问题问题定义建立模型问题求解整数规划第五章整数规划一、整数线性规划(IntegerLinearProgramming,IP)问题定义：决策变量是整数的线性规划所有变量都取整数的规划称为纯整数规划部分变量取整数的规划称为混合整数规划整数规划与线性规划的关系线性规划问题整数规划问题第一节整数规划的数学模型及解的特点二、整数规划例子例1:某服务部门各时段(2小时为一时段)需要的服务人员见表,服务人员连续工作8小时为一班.要求安排服务员的工作时间,使服务部门的人员最小.时段12345678最小人数10891
2、113853设在第j时段开始上班的服务人员的数量为xj,由于第j时段开始上班人员将在第j+3时段结束后下班,变量有x1,x2,x3,x4,x5Minz=x1+x2+x3+x4+x5x1≥10x1+x2≥8x1+x2+x3≥9x1+x2+x3+x4≥11x2+x3+x4+x5≥13x3+x4+x5≥8x4+x5≥5x5≥3x1,x2,x3,x4,x5≥0,且为整数.St.例2、现有资金总额B。可供选择的项目有n个，项目j所需要投资和预期收益分别为aj,cj(j=1,2,..n),条件（1）如果选择项目1，必须选择项
3、目2。反之，不一定；（2）项目3和4中至少选择一个；（3）项目5、6、7恰好选择2个。问：如何选择投资项目，使总预期收益最大？如果选择项目1，必须选择项目2。反之，不一定项目3和4中至少选择一个项目5、6、7恰好选择2个例3背包问题有一只背包，最大装载重量为W公斤，现有k种物品，每种物品数量无限。第i种物品每件重量为wi公斤，价值为vi元。每种物品各取多少件装入背包，使其中物品的总价值最高。设取第i种物品xi件（i=1，2，…，k），则规划问题可以写为：例4:工厂A1,A2上产某种物资,由于该种物资供不应求,需要
4、建设一家工厂,建厂方案有A3和A4两个.这种物资的需求地有B1,B2,B3,B4四个,生产、需求、运费见表。工厂A3或A4开工后，每年的生产费用分别为1200或1500。需要决定应该建设A3还是A4，能使今后每年的总费用最小（运费+生产费用）B1B2B3B4生产量A12934400A28357600A37612200A44525200需求量350400300150运输问题，但是不能确定A3，A4，不能确定新厂投产后的实际生产费用，引入0-1变量xij为Ai运到Bj的数量例5、某集装箱运输公司，箱型标准体积24m3
5、，重量13T,现有两种货物可以装运，甲货物体积5m3、重量2T、每件利润2000元；乙货物体积4m3、重量5T、每件利润1000元，如何装运获利最多？maxZ=2000x1+1000x25x1+4x2≤242x1+5x2≤13x1.x2≥0且为整数解此LP问题，得：X1=4.8，X2=0显然不是可行解St.三、解的特点A（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是IP的最优解。纯整数规划的可行解就是可行域中的整数点。非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不
6、妨碍整数规划问题的优化。IP问题的最优解不优于LP问题的最优解。第二节解纯整数规划的割平面法割平面法的基本思想：首先放弃变量的整数要求，求得线性规划的最优解。如果最优解恰是一个整数解，则线性规划的最优解就是相应的整数规划的最优解。如果线性规划的最优解不是整数解，则要求构造一个新的约束，对线性规划问题的可行域进行切割，切除已经得到的线性规划的最优解，但保留原可行域中所有的整数解，求解新的线性规划问题，如果最优解仍不是整数解，再增加附加的约束将其切除，但仍保持最初可行域中所有的整数解，如此一直进行，直至得到一个整数的
7、最优解为止。LP的最终单纯形表割平面如何得到？x1..xi..xm1…0…0a’1m+1a’1m+2…a’1n…………………….0…1…0a’im+1a’im+2…a’in…………………….0…0…1a’mm+1a’mm+2…a’mnb’1..b’i..b’mx1…xr…xmxm+1xm+2…xn基变量b割平面法求解整数规划问题时，若其松驰问题的最优解X*不满足整数要求时，则从X*的非整分量中选取一个，用以构造一个线性约束条件（Gomory割平面），将其加入原松驰问题中，形成一个新的线性规划，然后求解之。其关键在
8、于新增加的这个线性约束条件将切割掉部分非整数解，至少将当前松驰问题的非整数最优解切割掉了，而不会切割掉问题的任何整数解。18构造切割方程的步骤：1、令xi是相应松驰问题的最优解中为非整数值的一个基变量，由单纯形表最终表得：xi0+∑ai0,jxj=bi0…………………（1式）其中i0∈Q（Q指基变量下标集）j∈K（K指非基变量下标集）192、将bi0和ai0,j都分解成整
