运筹学整数规划建模讲义.pptVIP

* 解：令 xij = 1(第 i人完成第j项工作)或0（第 i人不进行第j项工作)．于是得到一个0--1整数规划问题： Min z=15x11+18x12+21x13+24x14+19x21+23x22 +22x23+18x24+26x31+17x32+16x33+19x34 +19x41 +21x42+23x43+17x44 s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能干一项工作) x31+ x32+ x33+ x34= 1 (丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作) x11+ 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 = 1,2,3,4 * 例．某企业在 A1 地已有工厂，其产品的生产能力为30 万箱。为扩大生产，拟在 A2，A3，A4，A5地中再选择若干地建厂。已知在 A2 ， A3，A4，A5地建厂的固定成本分别为17.5、30、37.5、50万元，另外， A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每万箱运费)如右下表所示。 问应该在哪些地方建厂，在满足销量的前提下，使得其总的固定成 本和总的运输费用 之和最小? 整数规划建模 * 解： 设 xij为从Ai 运往Bj 的运输量(单位千箱)， yi = 1(当Ai 被选中时)或0（当Ai 没被选中时)． Min z = 8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32 +4x33+9x41+7x42 +5x43+10x51 +4x52+2x53 +17.5y2+30y3+37.5y4+50y5 s.t. x11+ x12+ x13 ≤ 30 ( A1 厂的产量限制) x21+ x22+ x23 ≤ 10y2 ( A2 厂的产量限制) x31+ x32+ x33 ≤ 20y3 ( A3 厂的产量限制) x41+ x42+ x43 ≤ 30y4 ( A4 厂的产量限制) x51+ x52+ x53 ≤ 40y5 ( A5 厂的产量限制) x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( B3 销地的限制) xij ≥ 0 yi为0--1变量，i = 1,2,3,4,5；j = 1,2,3 * 例．某公司考虑今后五年内给以下项目投资。 项目A：每年年初需要投资，于次年末回收本利115%，但要求第1年投资最低金额为4万元，第2、3、4年不限； 项目B：第3年初投资，到第5年未能回收本利128％，但规定最低投资金额为3万元，最高金额为5万元； 项目 C：第2年初投资，到第5年未能回收本利140%，但规定其投资额只能为2、4、6或8万元。 项目 D：每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。 该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第 5 年末拥有的资金本利总额为最大? * 解：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 = 1, 2, 3, 4, 5）。 设yiC 是非负整数变量，并规定： 2年投资C项目为8万元、6万元、4万元、2万元、不投资C项目时，分别取值为4、3、2、1、0； 变量： 第1年 第2年