运筹学整数规划问题整数规划的典型例子工厂A,和A生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A，和A两个。这种物资的需求地有B,B,B,,B四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费Ci，见下表：B1B2B3B4年生产能力932A400A1837600A25762200A31545A42200350400300150年需求量工厂A，或A4开工后，每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂A，还是A4，才能使今后每年的总费用最少。-6-X主页下一页退出上一页后退China University of Mining and Technology
-6- China University of Mining and Technology 运 筹 学 整数规划的典型例子 工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建 一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有 B1 ,B2 ,B3 ,B4四个。各工厂年生产能力、各地年需求量、各厂至各需求 地的单位物资运费cij，见下表： B1 B2 B3 B4 年生产能力 A1 2 9 3 4 400 A2 8 3 5 7 600 A3 7 6 1 2 200 A4 4 5 2 5 200 年需求量 350 400 300 150 工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。 现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。 整数规划问题
运筹学整数规划问题解：这是一个物资运输问题，特点是事先不能确定应该建A，还是A中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入0-1变量：若建工厂(i = 1,2)=V若不建工厂再设x为由A，运往B的物资数量，单位为千吨；z表示总费用，单位万元。则该规划问题的数学模型可以表示为：-7-米主页页银China University of Mining and TechnologyK
-7- China University of Mining and Technology 运 筹 学 解：这是一个物资运输问题，特点是事先不能确定应该建A3 还是A4中哪一个，因而不知道新厂投产后的实际生产物资。 为此，引入0-1变量： ( 1,2) 0 1 y i i 若不建工厂 若建工厂 再设xij为由Ai运往Bj的物资数量，单位为千吨；z表示总费用， 单位万元。 则该规划问题的数学模型可以表示为： 整数规划问题
运筹学整数规划问题min z =ZZCijX; +[1200 y, +1500 y2]i=1 j=1Xi1 + X21 + X31 + X41 = 350X12 + X22 + X32 + X42 = 400X13 + X23 + X33 + X43 = 300X14 + X24 + X34 + X44 = 150X11 + X12 + X13 + Xi4 = 400混合整数规划问题S.tX21 +X22 + X23 + X24 = 600X31 + X32 + X33 + X34 = 200 yi年生产B1B2B3B4能力X41 + X42 + X43 + X44 = 200 y23A1294004(i, j = 1,2,3,4)Xj ≥035A2876002A3612007[y; = 0,1 (i=1,2)525A4200年需350400300150-8-求量X人下页后退退出主页上一页China University of Mining and Technology
-8- China University of Mining and Technology 运 筹 学 0,1 ( 1,2) 0 ( , 1,2,3,4) 200 200 600 400 150 300 400 350 . min [1200 1500 ] 4 1 4 2 4 3 4 4 2 3 1 3 2 3 3 3 4 1 2 1 2 2 2 3 2 4 1 1 1 2 1 3 1 4 1 4 2 4 3 4 4 4 1 3 2 3 3 3 4 3 1 2 2 2 3 2 4 2 1 1 2 1 3 1 4 1 4 1 4 1 1 2 y i x i j x x x x y x x x x y x x x x x x x x x x x x x x x x x x x x x x x x s t z c x y y i i j i j i j i j 混合整数规划问题 B1 B2 B3 B4 年生产 能力 A1 2 9 3 4 400 A2 8 3 5 7 600 A3 7 6 1 2 200 A4 4 5 2 5 200 年需 求量 350 400 300 150 整数规划问题
运筹学整数规划问题现有资金总额为B。可供选择的投资项目有n个，项目i所需投资额和预期收益分别为a;和c；（j=1,2,…,n），此外由于种种原因，有三个附加条件：若选择项目1，就必须同时选择项目2，反之不一定；项目3和4中至少选择一个项自5,6,7中恰好选择2个。应该怎样选择投资项自，才能使总预期收益最大。9.米上一页人下页主页后退银China University of Mining and Technology
-9- China University of Mining and Technology 运 筹 学 现有资金总额为B。可供选择的投资项目有n个，项目j 所需投资额和预期收益分别为aj和cj（j＝1,2,.,n），此外由 于种种原因，有三个附加条件： 若选择项目1，就必须同时选择项目2，反之不一定; 项目3和4中至少选择一个； 项目5,6,7中恰好选择2个。 应该怎样选择投资项目，才能使总预期收益最大。 整数规划问题
运筹学整数规划问题因此分解：对每个投资项目都有被选择和不被选择两种可能，别用0和1表示，令x；表示第个项目的决策选择，记为对项目投资(j = 1,2..., n)对项目不投资nZex,投资问题可以表示为：z=maxj=1"Wajx, ≤BX, ≥ Xis.tX+x ≥1Xs +X +X, = 2x,=0或者1(j=1,2,...n)-10-退出主页上一页页后退China University of Mining and Technology
-10- China University of Mining and Technology 运 筹 学 解：对每个投资项目都有被选择和不被选择两种可能，因此分 别用0和1表示，令xj表示第j个项目的决策选择，记为： ( 1,2,., ) 0 1 j n j j xj 对项目 不投资 对项目 投资 投资问题可以表示为： x 或 者 （ n） x x x x x x x a x B s t z c x j n j j j n j j j 0 1 j 1,2, 2 1 . max 5 6 7 3 4 2 1 1 1 整数规划问题