§3整教规划的应用 解:引入0—1变量x;并令 1(当指派第i人去完成第j项工作时)或0(当不指派第i人去 完成第j项工作时).这可以表示为一个0-1整数规划问题 z=15x1+18x12+21x3+24x14+19x21+23x2+22x23+18x24+26x31+17x32+16x3 +19X34+19x1+21x2+23x43+17x14 s.t.x1+x12+x13+x14=1(甲只能干一项工作) x2+x23+x2=1(乙只能干一项工作) x31+x2+x32+x3=1(丙只能干一项工作) x1+x+x13+x4=1(丁只能干一项工作) x1计+x2+x1+x1=1(A工作只能一人干) x2+x2+x32+x42=1(B工作只能一人干) x13+x23+x3+x3=1(C工作只能一人干) x4+x2+x34+x4=1(D工作只能一人干) x1;为0--1变量,i,j=1,2,3,4 ***求解可用《管理运籌学》錾件中整数规划方法
管 理 运 筹 学 11 §3 整数规划的应用 解：引入0—1变量 xij，并令 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 * * * 求解可用《管理运筹学》软件中整数规划方法
§3整教规划的应用 四、分布系统设计 例7.某企业在A1地已有一个工厂,其产品的生产能力为30千箱,为了 扩大生产,打算在A2,A3,A4,A地中再选择几个地方建厂。已知在 A2,A3,A4,A地建厂的固定成本分别为175千元、300千元、375千 元、500千元,另外,A1产量及A2,A3,A4,A建成厂的产量,那时 销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。 a)问应该在哪几个地方建厂,在满足销量的前提下,使得其总的固定成 本和总的运输费用之和最小? b)如果由于政策要求必须在A2,A3地建一个厂,应在哪几个地方建厂? 销地 B 产地 B2B3产量(千吨) 10 4 4 20 「销量(千吨) 20 20 运筹 12
管 理 运 筹 学 12 §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地建一个厂，应在哪几个地方建厂? 销地 产地 B1 B2 B3 产量(千吨) A1 8 4 3 30 A2 5 2 3 10 A3 4 3 4 20 A4 9 7 5 30 A5 10 4 2 40 销量(千吨) 30 20 20
§3整教规划的应用 解:a)设x1为从A运往B的运输量(单位千箱),=1(当Ax被选中时)或0 (当Ak没被选中时),k=2,3,4,5.这可以表示为一个整数规划问题 Minz=175y2+300y3+375y4+500y+8x1+4x12+3x13+5x21+2x2+3x23+4x31+ 3x32+4x3+9x41+7x42+5x43+10x51+4x52+2x53 其中前4项为固定投资额,后面的项为运输费用。 s.t.x1+x2+x3≤30(A1厂的产量限制) x21+x2+x23≤10y2(A2厂的产量限制) x31+x32+x3≤20y3(A3厂的产量限制) x41+x42+x43≤30y4(A4厂的产量限制) x1+x52+x53≤40y5(A5厂的产量限制) x1+x21+x31+xq1+x51=30(B1销地的限制) x2+x2+x32+x42+x52=20(B2销地的限制) x13+x23+X3+x43+ 20(B3销地的限制) x≥0,i=1,2,3,4,5;j=1,2,3,为0-1变量,k=2,3,4,5。 **求解可用《管理运筹学》软件中整数规划方法 理蓦总 13
管 理 运 筹 学 13 §3 整数规划的应用 解： a) 设 xij为从Ai 运往Bj 的运输量(单位千箱)， yk = 1(当Ak 被选中时)或0 （当Ak 没被选中时),k =2,3,4,5．这可以表示为一个整数规划问题： Min z = 175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+ 3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53 其中前4项为固定投资额，后面的项为运输费用。 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，i = 1,2,3,4,5； j = 1,2,3， yk 为0--1变量，k =2,3,4,5。 * * * 求解可用《管理运筹学》软件中整数规划方法