管理运筹学_第5章__整数规划_（可编辑）.doc
10页
第五章整数线性规划§1整数线性规划的图解法§ 2整数线性规划的计算机求解§3整数线性规划的应用§1整数规划的图解法例llx/a>. 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的 体积、重量、可获利润以及托运所受限制如表所示甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大解：设xl、x2分别为甲、乙两种货物托运的件数，建立模型目标函数： Max z = 2x1 +3 x2约束条件： s.t.195 xl + 273 x2 <13654 xl + 40 x2 <140xlW4xl, x2 NO 为整数如果去掉最后一个约束，就是一个线性规划问题利用图解法，货物每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲乙19527344023托运限制1365140第五章整数线性规划整数规划一类要求问题的解中的全部或一部分变量为整数的数学规划从约 束条件的构成又可细分为线性，二次和非线性的整数规划求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数 解加以处理都能解决的，而要用整数规划的方法加以解决第五章整数线性规划在整数规划中，如果所有的变量都为整数，则称为纯整数规划问题；如果有 一部分变量为整数，则称之为混合整数规划问题。
在整数规划中，如果变量的取 值只限于0和1,这样的变量我们称之为0-1变量如果所有的变量都为0-1变 量，则称之为0-1规划0-1变量可以数量化地描述诸如开与关、取与弃、有与无等现象所反映的离 散变量间的逻辑关系、顺序关系以及互斥的约束条件，因此0-1规划非常适合 描述和解决如线路设计、工厂选址、生产计划安排、旅行购物、背包问题、人 员安排、代码选取、可靠性等人们所关心的多种问题实际上，凡是有界变量的 整数规划都可以转 化为0-1规划来处理§1整数线性规划的图解法得到线性规划的最优解为xl=2.44, x2=3.26,目标函数值为14.66由图表可看出，整数规划的最优解为xl=4,x2=2,目标函数值为14o性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目 标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目 标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相 应的线性规划的最小目标函数值12341232xl+3x2 = 14.66xlx22xl+3x2 =142xl+3x2 =6§1整数规划的图解法例2：Max z = 3x1 + x2 + 3x3s.t.-xl + 2x2 + x3 W 44x2 -3x3 W2xl -3x2 + 2x3 W3xl,x2,x3 3 0 为整数例3：Max z = 3x1 + x2 + 3x3-xl + 2x2 + x3 W 44x2 -3x3 W2xl -3x2 + 2x3 W3x3 <1xl,x2,x3 3 0xl, x3为整数 x3为0-1变量用《管理运筹学》软件求解得：xl = 5 x2 = 2 x3 = 2用《管理运筹学》软件求解得：xl = 4 x2 = 1.25 x3 = 1z = 16.25§ 2整数线性规划的计算机求解§3整数线性规划的应用一、投资场所的选择例4、京成畜产品公司计划在市区的东、西、南、北四区建立销 售门市部，拟议中有10个位置Aj (j = l, 2, 3,…，10)可供选择，考虑到各地 区居民的消费水平及居民居住密集度，规定：在东区由Al , A2 , A3三个点至多选择两个；在西区由A4 , A5两个点中至少选一个；在南区由A6 , A7两个点中至少选一个；在北区由A8 , A9 , A10三个点中至少选两个。
Aj各点的设备投资及每年可获利润由于地点不同都是不一样的， 预测情况见表所示（单位：万元）但投资总额不能超过7>720 万元，问应选择哪几个销售点， 可使年利润为最大？§3整数线性规划的应用解：设：0-1变量xi = 1 （Ai点被选用）或0（Ai点没被选用） 这样我们可建立如下的数学模型：Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 W 720xl + x2 + x3 W 2x4 + x5 3 1x6 + x7 3 1x8 + x9 + xlO 3 2xj 3 0 且 xj 为 0—1 变量，i = l,2,3, ,10§3整数线性规划的应用二、固定成本问题例5.高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。
不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300 A/月，机器有100台/月，此外 不管每种容器制造的数量是多少，都要支付一笔固定的费用： 小号是100万元，中号为150万元，大号为200万元现在要制 定一个生产计划，使获得的利润为最大§3整数线性规划的应用解：这是一个整数规划的问题设xl, x2, x3分别为小号容器、中号容器和大号容器的生 产数量各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用 的这种性质，设yi = 1（当生产第i种容器，即xi > 0时）或0 （当不生产第i 种容器即xi = 0时）引入约束 xi W M yi , i =1, 2, 3, M充分大，以保证当 yi = 0 时，xi = 0建立如下的数学模型：Max z = 4x1 + 5x2 + 6x3 - lOOyl - 150y2 - 200y3s.t. 2x1 + 4x2 + 8x3 W 5002x1 + 3x2 + 4x3 W 300xl + 2x2 + 3x3 W 100xi W M yi , i =1, 2, 3, M 充分大xj 3 0 yj 为 0-1 变量，i = 1,2,3§3整数线性规划的应用三、指派问题有n项不同的任务，恰好n个人可分别承担这些任务，但由 于每人特长不同，完成各项任务的效率等情况也不同。
现假设必须 指派每个人去完成一项任务，怎样把n项任务指派给n个人，使 得完成n项任务的总的效率最高，这就是指派问题例6.有四个工人，要分别指派他们完成四项不同的工作，每 人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能 使总的消耗时间为最少§3整数线性规划的应用解：引入0—1变量xij,并令xij = 1（当指派第i人去完成第j项工作时）或0 （当不指派第i人去完成第j项工作时）.这可以表示为一个0-1整数规划问题:MinZ=15xll+18xl2+21xl3+24xl4+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44s.t. xll+ xl2+ xl3+ xl4= 1 （甲只能干一项工作）x21+ x22+x23+x24= 1 （乙只能干一项工作） x31+ x32+ x33+ x34= 1（丙只能干一项工作）x41+ x42+ x43+ x44= 1（丁只能干一项工作）xll+ x21+x31+x41= 1（A工作只能一人干）X12+ x22+x32+x42= 1（B工作只能一人干）X13+ x23+ x33+ x43= 1（C工作只能一人干）X14+ x24+ x34+ x44= 1（D工作只能一人干）xij 为 0—1 变量，i,j = l,2,3,4§3整数线性规划的应用四、分布系统设计例7.某企业在A1地已有一个工厂，其产品的生产能力为30千箱，为了 扩大生产，打算在A2, A3, A4, A5地中再选择几个地方建厂。
已知在A2 , A3,A4, A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外，A1产量及A2, A3, A4, A5建成厂的产量，那时销地的销量以及产地到销地的单位运价（每千箱运费）如下表所示a）问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?b）如果由于政策要求必须在A2, A3地建一个厂，应在哪几个地方建厂?§3整数规划的应用解：a）设xij为从Ai运往Bj的运输量（单位千箱），yk = l（^g Ak被选中时）或当Ak没被选中时）,k=2,3,4,5.这可以表示为一个整数规划问题:Min z = 175y2+300y3+375y4+500y5+8xll+4xl2+3xl3+5x21+2x22+3x23+4x31+3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53其中前4项为固定投资额，后面的项为运输费用s.t. X11+X12+X13 W 30 （Al 厂的产量限制）x21+ x22+x23 W 10y2x31+x32+x33 W 20y3 x41+ x42+ x43 W 30y4 x51+ x52+ x53 W 40y5（A2厂的产量限制）（A3厂的产量限制）（A4厂的产量限制）（A5厂的产量限制）xll+ x21+ x31+ x41 + x51 = 30 （ Bl 销地的限制）X12+ x22+ x32+ x42 + x52 = 20 （ B2 销地的限制）X13+x23+x33+x43 + x53 = 20 （ B3 销地的限制）xij 30, i = 1,2,3,4,5； j = 1,2,3, yk 为 0—1 变量，k=2,3,4,5。
§3整数线性规划的应用五、投资问题例8.某公司在今后五年内考虑给以下的项目投资已知：项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%, 但要求第一年投资最低金额为4万元，第二、三、四年不限；项目B：第三年初需要投资，到第五年末能回收本利128%，但规定最低投 资金额为3万元，最高金额为5万元；项目C：第二年初需要投资，到第五年末能回收本利140%,但规定其投资 额或为2万元或为4万元或为6万元或为8万元项目D：五年内每年初可购买公债，于当年末归还，并加利息6%,此项投 资金额不限该部门现有资金10万元，问它应如何确定给这些项目的每年投资 额，使到第五年末拥有的资金本利总额为最大？§3整数线性规划的应用解：1）设xiA、xiB、xiC、xiD （i =1, 2, 3, 4, 5）分别表示第i年年初给项 目A, B, C, D的投资额；设yiA, yiB,是0—1变量，并规定取1时分别表示第i年给A、 B投资，否则取 0 （ i = l, 2, 3,4, 5）设yiC是非负整数变量，并规定：第2年投资C项目8万元时，取 值为4；第2年投资C项目6万元时，取值3；第2年投资C项目4万元时，取值2；第2年投资C项目2万元时，取值1；第2年不投资C项目时。
