整数规划的建模.ppt

《整数规划的建模.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章整数规划在线性规划问题中，有一类特殊的情形，称为整数规划，这类问题的最优解必须是整数。如求解完成工作所需的最少人数，或加工一批零件所需机器的台数。由于这类问题并不是由简单的“四舍五入”法或“去零化整”法就能求得最优解，因此有必要对它作专门的讨论。本章包含四部分的内容：第一部分：整数规划的建摸第二部分：整数规划的应用（0-1型整数规划）第三部分：分支定界法第四部分：指派问题§1、整数规划的建摸整数规划问题的数学模型和线性规划基本相同，只是约束条件有所不同，下面我们以例题说明整数规划的建模。1、问题的提出例1某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利

2、润以及托运所受限制如表，问两种货物各托运多少箱可获利润最大？货物体积每箱（m3)重量每箱（m3)利润每箱（百元）甲5220乙4510托运限制2413解：设x1,x2分别为甲、乙两种货物的托运箱数（应为大于或等于零的整数），这是一个整数规划问题，数学模型如下从上式可见，它和线性规划问题的区别仅在于x1,x2为整数这一条件。如果我们暂不考虑这一条件，很容易求得相应线性规划问题的最优解为，但不满足整数要求，如按四舍五入取，又破坏了这一条件，如舍去尾数取x1=4,x2=0虽然满足了约束条件，但此时z=80，不是最优解，因为当时x1=4,x2=1，既满足约束条件，且z=90>8

3、0。由此可见整数规划问题并非通过“化整”求其最优解。从以上的例题可以看出：由于相应的线性规划的可行域包含了其整数规划的可行解，就可有如下的性质：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值。2、定义规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。3、整数规划分类如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：（1）变量全限制为整数的，称纯（完全）整数规划。（2）变量部分限制为整数的，称混合整数规划。4、整数规划特点整数规划标准

4、形式（实际为整数线性规划）AX=b，X≥0，CTX=min，xj为整数（j=1，…，n）(1)（1．原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况；①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。②整数规划无可行解。③有可行解（当然就存在最优解），但最优解值变差。原线性规划为：2x1+4x2=6，X≥0，CTX=x1+x2=min其最优实数解为：x1=0，x2=3/2，minCTX=3/2。若限制整数则得：x1=1，x2=1，minCTX=2。5、求解方法分类：（1．割平面法——主要求解纯整数线性规划（2．分枝定界法——可求纯或混

5、合整数线性规划（3．隐枚举法——求解“01”整数规划：①过滤隐枚举法；②分枝隐枚举法（4．匈牙利法——解决指派问题（“01”规划特殊情形）。（5．蒙特卡洛法——求解各种类型规划。§2、整数规划的应用（0-1型整数规划）在整数规划中有一类特殊的情形，它的变量xi仅能取0或1，这时的xi称为0-1变量，这类问题也就称为0-1型整数规划。2、10-1型数规划的建模0-1变量作为逻辑变量，常被用来表示系统是否处于某个特定状态或者决策时是否采取某个特定方案。当问题含有多项要素，而每项要素皆有两种选择时，也可用0-1变量来描述设某问题有有限要素E1,E2,…,En，其中每项E

6、j有两种选择Aj和(j=1.2.---,n)则：2、1、2下面讨论0-1整数规划的几种应用实例。1．相互排斥的计划问题例3某超市连锁店的布点问题。某超市连锁店在分析某城市的特征后，将该城市划分成四个区域：东片、西片、南片、北片。在四个区域中共确定了10个连锁店的备选点，记作在连锁店选择时需考虑以下限制：①东片的三个点中,至少应选择一个;②西片的两个点中，应恰好选择一个；③南片的四个点中，最多只能选三个；④北片只有一个备选点，可选可不选。如果选中点，其投资为元，每年的预期收益为元。现要求总投资不超过Z元，问应选择哪些备选点，既可满足限制，又可使每年的总收益最大。试建立这

7、个问题的0-1型整数规划数学模型。解：设则可建立如下0-1型整数规则数学模型：例4某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为，相应的钻探费用为，并且井位选择上要满足下列限制条件：①或选择S1和S7，或选择S8；②选择了S3或S4就不能选S5，反之，选了S5，则不能选S3或S4；③在S5~S8中最多选两个。建立这个问题的0-1型整数规划模型解：例5指派问题有n项不同的任务，恰好n个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把n