清华大学运筹学4整数规划ppt课件.pptx

《清华大学运筹学4整数规划ppt课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章整数规划第一节整数规划数学模型及解的特点第二节割平面法第四节0-1型整数规划第五节指派问题1/68第一节整数规划模型及解的特点一、整数规划模型一般形式2/683/68Maxz=CXs.t.AX≤或=或≥bX≥0，b≥0C=(c1,c2,…,cn)X=(x1,x2,…,xn)T有些或全部xj取整数b=(b1,b2,…,bm)Ta11a12…a1nA=a21a22…a2n.........m

2、，则该整数规划问题叫做整数线性规划。整数线性规划有如下几种类型：1.纯整数线性规划——全部决策变量须取整数，亦称全整数规划。2.混合整数线性规划——部分决策变量须取整数。3.0-1型整数线性规划——决策变量只取0或1的整数线性规划。5/68二、整数规划之例[例1]某商场拟用集装箱托运两种货物，每箱体积、重量、可获利润以及所受限制如下表。问：两种货物各托运多少，利润最大？货物体积立方米/箱重量百斤/箱利润千元/箱服装5220玩具4510托运限制24136/68用x1和x2将表示服装和玩具的托运箱数，则该问题可表示如下：

3、Maxz=20x1+10x2(1)s.t.5x1+4x2≤24(2)2x1+5x2≤13(3)x1，x2≥0，(4)x1，x2取整数(5)7/68[例2]某地区要建水电站，有15处可行，可用资金总额为B。各处所需投资和预期收益分别为aj和cj(j=1,3,…,15)。要求是：若在第一处建，第二处也要建；但是，第二处建；第一处不一定建；第三和第四处至少有一处必须建；第五、六和第七处建两个。问：如何在这15处布置水电站，才能预期最大收益？8/689/68[例3]现有A1和A2生产某产品，在B1、B2、B3和B4销售。因供

4、不应求，计划再建一厂。新厂有方案A3和A4，建成后年生产费用分别为1200和1500万元。从产地到销地运费见下表。问哪一方案使新厂建成后年运费与生产费用总和最少？B1B2B3B4产能（千吨/年）A12934400A28357600A37612200A44525200需求量（千吨/年）35040030015010/6811/68三、解的特点整数线性规划的解一定是松弛问题的解，可行域是松弛问题可行域的子集。目标函数值不会超过松弛问题目标函数值。反过来，不一定成立。不能将松弛问题的解四舍五入当作整数线性规划的解。xj=1或

5、0，j=1,3,…,1512/68现在看托运问题：Maxz=20x1+10x2s.t.5x1+4x2≤242x1+5x2≤13x1，x2≥0，x1，x2取整数先用图解法解松驰问题，得13/684x1x23225x1+4x2=24z=20x1+10x2=96z=15oA(4.8,0)2x1+5x2=136z=90(4,1)z=1014/68最优解是(x1,x2)=(4.8,0)Maxz=96再看整数规划问题，若取x1=5，x2=0，破坏了约束条件5x1+4x2≤24若取x1=4，x2=0，z=20x1+10x2=80，

6、实际上，(x1,x2)=(4,1)也是可行解，z=90可见，将松弛问题的解四舍五入不能求得整数线性规划的解。第二节解整数规划的割平面法就是在解松驰问题过程中逐一去掉非整数解域，寻找整数解的方法，也就是“切割”可行域平面。切割的办法是增加约束条件。15/68He(born7May1929inBrooklyn)isanappliedmathematician.HeworkedatIBMasaresearcherandlaterasanexecutiveandhisresearchledtothecreationofnew

7、areasofappliedmathematics.Afterhiscareerinthecorporateworld,hebecamethepresidentoftheAlfredP.SloanFoundation,whereheoversawprogramsdedicatedtobroadeningpublicunderstandinginthreekeyareas:theeconomicimportanceofscienceandresearch;theeffectsofglobalizationontheUn

8、itedStates;andtheroleoftechnologyineducation.16/68RalphEdwardGomory17/68[例1]Maxz=x1+x2s.t.-x1+x2≤13x1+x2≤4x1，x2≥0，x1，x2取整数先用图解法解松驰问题，得18/68x1x2211-x1+x2=1z=x1+x2=2.5o4/33x1+