数学规划建模

《数学规划建模》由会员分享，可在线阅读，更多相关《数学规划建模（154页珍藏版）》请在装配图网上搜索。

1、Click to edit Master title style,,Click to edit Master text styles,,Second level,,Third level,,Fourth level,,Fifth level,,,,*,,,,,1,,最优化问题的,数学模型的一般形式,为：,（,1,）,（,2,）,三个要素：决策变量,decision bariable,，目标函数,objective function,，约束条件,constraints,。,,2,,,（,2,）所确定的,x,的范围称为,可行域,feasible region,，满足（,2,）的解,x,称为,可行解

2、,feasible solution,，同时满足（,1,）（,2,）的解,x,称为,最优解,Optimal solution,，整个可行域上的最优解称为,全局最优解,global optimal solution,，可行域中某个领域上的最优解称为,局部最优解,local optimal solution,。最优解所对应的目标函数值称为,最优值,optimum,。,,3,,,优化模型的分类,（一）按有无约束条件,（,2,）可分为：,,,1.,无约束优化,unconstrained optimization,。,,,2.,约束优化,constrained optimization,。,,大部分实际

3、问题都是约束优化问题。,,4,,,（二）,按决策变量取值是否连续,可分为：,,1.,数学规划或连续优化,。,,可继续划分为,线性规划,(,LP)Linear programming,和,非线性规划,(,NLP) Nonlinear programming,。在非线性规划中有一种规划叫做,二次规划,(QP)Quadratic programming,，目标为二次函数，约束为线性函数。,,2.,离散优化或组合优化,。,,包含：,整数规划,(IP)Integer programming,，整数规划中又包含很重要的一类规划：,0-1,（整数）规划,Zero-one programming,，这类规划问

4、题的决策变量只取,0,或者,1,。,,5,,,（三）,按目标的多少,可分为：,,1.,单目标规划。,,2.,多目标规划。,,（四）,按模型中参数和变量是否具有不确定性,可分为：,,1.,确定性规划。,,2.,不确定性规划。,,（五）,按问题求解的特性,可分为：,,1.,目标规划。,,2.,动态规划。,,3.,多层规划。,,4.,网络优化。,,5.……,等等。,,6,,,优化问题求解常用的软件,,LINGO,软件和,MATLAB,软件。,,对于,LINGO,软件，线性优化求解程序通常使用,单纯形法,simplex method,，单纯形法虽然在实际应用中是最好最有效的方法，但对某些问题具有指数阶

5、的复杂性，为了能解大规模问题，也提供了,内点算法,interior point method,备选（,LINGO,中一般称为障碍法，即,barrier,），非线性优化求解程序采用的是,顺序线性规划法,，也可用,顺序二次规划法,，广义既约梯度法，另外可以使用多初始点（,LINGO,中称,multistart,）找多个局部最优解增加找全局最优解的可能，还具有全局求解程序,—,分解原问题成一系列的,凸规划,。,,7,,,软件介绍,,例,1,,帆船生产计划,,SAILCO,公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是,40,条，,60,条，,75,条，,25,条，这些需求必须按时满

6、足。每个季度正常的生产能力是,40,条帆船，每条船的生产费用为,400,美元。如果加班生产，每条船的生产费用为,450,美元。每个季度末，每条船的库存费用为,20,美元。假定生产提前期为,0,，初始库存为,10,条船。如何安排生产可使总费用最小？,,分析,:,,DEM,－需求量，,RP,－正常生产的产量，,,OP,－加班生产的产量，,INV,－库存量，,,则,DEM,RP,OP,INV,对每个季度都应该有一个对应的值，也就说他们都应该是一个由,4,个元素组成的,数组,，其中,DEM,是已知的，而,RP,OP,INV,是未知数。,,8,,,目标函数：正常生产费＋加班生产费＋储存费 最小,约束

7、条件：,1,）能力限制：,2,）产品数量的平衡方程：,4,）变量非负,3,）初始库存：,－引例－ 模型建立,,9,,,记四个季度组成的集合,QUARTERS={1,，,2,，,3,，,4},，它们就是上面数组的,下标集合,，而数组,DEM,RP,OP, INV,对集合,QUARTERS,中的每个元素,1,，,2,，,3,，,4,分别对应于一个值。,LINGO,正是充分利用了这种,数组及其下标,的关系，引入了“集合”及其“属性”的概念，把,QUARTERS={1,，,2,，,3,，,4},称为,集合,，把,DEM,RP,OP, INV,称为该集合的,属性,(,即定义在该集合上的属性,),。,－集

8、合与属性－,,10,,,QUARTERS,集合的属性,DEM,,,RP,OP,,INV,,,QUARTERS,集合,2,3,4,1,－集合与属性－,,11,,,集合元素及集合的属性确定的所有,变量,集合,QUARTERS,的元素,,1,2,3,4,定义在集合,,QUARTERS,,上的属性,DEM,DEM(1),DEM(2),DEM(3),DEM(4),,RP,RP(1),RP(2),RP(3),RP(4),,OP,OP(1),OP(2),OP(3),OP(4),,INV,INV(1),INV(2),INV(3),INV(4),,－集合与属性－,,12,,,－程序编写－,,MODEL:,,!,

9、集合段：定义集合,SET,，元素,member,及其属性,attribute,；,,,SETS:,,QUARTERS/1,2,3,4/:DEM,RP,OP,INV;,,ENDSETS,,!,目标与约束段：没有开始和结束标记，顺序无关；,,,MIN=@SUM(QUARTERS(I):400*RP(I)+450*OP(I)+20*INV(I));,,,@FOR(QUARTERS(I):RP(I)<40);,,@FOR(QUARTERS(I),|I#GT#1,:,,INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I););,,INV(1)=10+RP(1)+OP(1)-DEM(1);

10、,,!,数据段：对集合的属性输入必要的常数数据；,,,DATA:,,DEM=40,60,75,25;,,ENDDATA,,,END,或,1..4,或用空格或回车隔开，“属性＝常数列表”,对“：”前的每个元素求和或循环,,遍历下标元素，可省略下标,“,︱,”,后是过滤条件，逻辑关,,系式,I>1,（,greater than,）,,13,,,－展开式－,LINGO︱Generate︱Disply Model(Ctrl+G),MIN=@SUM(QUARTERS(I):400*RP(I)+450*OP(I)+20*INV(I));,,,@FOR(QUARTERS(I):RP(I)<40);,,@FO

11、R(QUARTERS(I),|I#GT#1,:,,INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I););,,INV(1)=10+RP(1)+OP(1)-DEM(1);,,14,,,全局最优解,,RP=(40,40,40,25),,OP=(0,10,35,0),最小成本,=78450,自动生成行号,－结果报告－,,15,,,例,2,运输问题,,16,,,解：设,A,1,,A,2,调运到三个粮站的大米分别为,x,11,，,,x,12,，,,x,13,，,,x,21,，,,x,22,，,,x,23,吨。,题设量可总到下表：,8,4,库,存,量,x,23,x,22,x,21,A,2

12、,5,4,2,需要量,x,13,x,12,x,11,A,1,B,3,B,2,B,1,粮库,粮站,距离及运量,12,12,24,30,8,24,,17,,,结合存量限制和需量限制得数学模型,：,,18,,,程序编写 推荐,,,MODEL,:,,TITLE,,调运大米的运输问题程序４,;,,!,定义集合段,;,,SETS,:,,LIANGKU/1..2/:A;,!,定义粮库的集合,;,,LIANGZHAN/1..3/:B;,!,定义粮站的集合,;,,YULIANG(LIANGKU,LIANGZHAN):X,C;,!,定义运量和距离,;,,ENDSETS,,DATA,:,,!,粮库到粮站的距离,;

13、,,C= 12 24 8,,,,30 12 24;,,19,,,!,粮库的限量,;,,A=4 8 ;,,!,粮站的限量,;,,B=2 4 5;,,ENDDATA,,[OBJ],MIN,=,@SUM,(YULIANG:C*X);,,!,粮库上限的约束,;,,@FOR,(LIANGKU(I):[LK],,,@SUM,(LIANGZHAN(J):X(I,J))B(J));,,END,,,20,,,程序的调试,,,1.,直接点击运行，如果出错会弹出错误提示

14、，根据提示做相应的修改；,,,2.,可以用“！”把约束变成说明语句，而把这条语句屏蔽掉，缩小寻找出错的范围；,,,3.,可以边写程序边运行，保证每行书写都是正确的程序；,,21,,,料场的建立与运输,建筑工地的位置,(,用平面坐标,a,,,b,表示，距离单位：公里,),及水泥日用量,d,(,吨,),下表给出。有两个临时料场位于,P (5,1), Q (2, 7),,日储量各有,20,吨。,(1),从,A, B,两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。,(2),两个新的料场应建在何处，节省的吨公里数有多大？,,１,２,３,４,５,６,a,1.25,8.75,0.5,5.75,3,7

15、.25,b,1.25,0.75,4.75,5,6.5,7.75,d,3,5,4,7,6,11,非线性规划－引例,－,,22,,,已知为,LP,模型，未知为,NLP,模型,－引例－ 模型建立,料场向工地的运送量为：,工地：位置,水泥日用量：,料场：位置,日储量：,,23,,,利用集合的概念，可以定义需求点,DEMAND,和供应点,SUPPLY,两个集合，分别有,6,个和,2,个元素,(,下标,),。但决策变量,(,运送量,),c,ij,与集合,DEMAND,和集合,SUPPLY,都有关系的。该如何定义这样的属性？,集合的属性相当于以集合的元素为下标的数组。这里的,c,ij,相当于二维数组。它的两

16、个下标分别来自集合,DEMAND,和,SUPPLY,，因此可以定义一个由二元对组成的新的集合，然后将,c,ij,定义成这个新集合的属性，这个集合称为,派生集合,。,－派生集合－,,24,,,－程序编写－,MODEL:,,Title Location Problem;,,sets:,,demand/1..6/:a,b,d;,,supply/1..2/:x,y,e;,,link(demand,supply):c;,,endsets,,data:,,!locations for the demand(,需求点的位置,);,,a=1.25,8.75,0.5,5.75,3,7.25;,,b=1.25,0

17、.75,4.75,5,6.5,7.75;,,!quantities of the demand and supply,（供需量）,;,,d=3,5,4,7,6,11; e=20,20;,,enddata,,……,基本集合,primary set,与,,派生集合,derived set,（定义多维数组）,,25,,,－程序编写－,……,,!,初始段：对集合属性定义初值（迭代算法的迭代初值）,;,,init:,,!initial locations for the supply,（初始点）,;,,x,y=5,1,2,7;,,endinit,,!Objective function,（目标）,;,,

18、[OBJ] min=@sum(link(i,j): c(i,j)*((x(j)-a(i))^2+(y(j)-b(i))^2)^(1/2) );,,!demand constraints,（需求约束）,;,,@for(demand(i):,[DEMAND_CON],@sum(supply(j):c(i,j)) =d(i););,,!supply constraints,（供应约束）,;,,@for(supply(i):[SUPPLY_CON] @sum(demand(j):c(j,i)) <=e(i); );,,@for(supply: @bnd(0.5,X,8.75); @bnd(0.75,Y

19、,7.75); );,,END,LINGO,对数值顺序按列赋值，即：,x=5,2;y=1,7;,标号自动在后加下标 *,_1 , _2…,比,@free(x);@free(y);,要好，可减少计算工作量,,26,,,－求解观察－,激活全局最优解：,,LINGO︱Options→Global Solver︱Use Global Solver,,27,,,－结果报告－,工地与料场运输示意图,: “,*,”,表示料场，“,+,”,表示工地,,,28,,,－认识“初始段”－,……,,data:,,!(,需求点的位置,);,,a=1.25,8.75,0.5,5.75,3,7.25;,,b=1.25,0.

20、75,4.75,5,6.5,7.75;,,!,（供需量）,;,,d=3,5,4,7,6,11; e=20,20;,,Enddata,,init:,,!,（初始点）,;,,x,y=5,1,2,7;,,Endinit,,……,……,,data:,,!(,需求点的位置,);,,a=1.25,8.75,0.5,5.75,3,7.25;,,b=1.25,0.75,4.75,5,6.5,7.75;,,!,（供需量）,;,,d=3,5,4,7,6,11; e=20,20;,,x,y=5,1,2,7;,,Enddata,,init:,,!,（初始点）,;,,Endinit,,……,求解,NLP,问题,求解,L

21、P,问题,只对非线性模型起作用,,29,,,－知识重整－,LINGO,建模语言也称为矩阵生成器（,MATRIX GENERATOR,）。类似,DEMAND,和,SUPPLY,直接把元素列举出来的集合，称为,基本集合,(primary set),,,而把,LINK,这种基于其它集合而派生出来的二维或多维集合称为,派生集合,(derived set),。由于是,DEMAND,和,SUPPLY,生成了派生集合,LINK,，所以,DEMAND,和,SUPPLY,称为,LINK,的,父集合,。,,表示集合,LINK,中的元素就是集合,DEMAND,和,SUPPLY,的元素组合成的有序二元组，从数学上看,

22、LINK,是,DEMAND,和,SUPPLY,的笛卡儿积，也就是说,,LINK={,（,S,，,T,）,|S,∈,DEMAND,，,T,∈,SUPPLY},,因此，其属性,C,也就是一个,6*2,的矩阵（或者说是含有,12,个元素的,二维数组,）。,,30,,,－模型构成－,一般来说，,LINGO,中建立的优化模型可以由五个部分组成，或称为五“段”（,SECTION,）：,（,1,）,集合段,（,SETS,）：以“,SETS:”,开始， “,ENDSETS”,结束，定义必要的集合变量（,SET,）及其元素（,MEMBER,，含义类似于数组的下标）和属性（,ATTRIBUTE,，含义类似于数组）

23、。,（,2,）,目标与约束段,：目标函数、约束条件等，没有段的开始和结束标记，因此实际上就是除其它四个段,(,都有明确的段标记,),外的,LINGO,模型。,（,3,）,数据段,(DATA),：以 “,DATA:”,开始,, “ENDDATA”,结束，,,对集合的属性,(,数组,),输入必要的常数数据。,,格式为：“,attribute(,属性,) = value_list(,常数列表,);,”,,31,,,－模型构成－,(5),计算段,:,在数据段输入完成之后在正式求解模型之前对,,原始数据进行处理，语句是,顺序,执行的，不能更换顺序，只能,,直接使用,赋值语句,，不能包含需要经过解方程或经

24、过求解优化,,问题以后才能决定的变量。,CALC,:,,T_DEM=@,SUM,(QUARTERS:DEM);,!,总需求；,,A_DEM=T_DEM/@,SIZE,(QUARTERS);,!,平均需求；,,ENDCALC,（,4,）,初始段,(INIT),：以“,INIT: ”,开始， “,ENDINIT”,结束，,,对集合的属性,(,数组,),定义初值,(,因为求解算法一般是迭代算法，,,所以用户如果能给出一个比较好的迭代初值，对提高算法的计,,算效果是有益的,),。,,格式为：“,attribute,（属性）,= value_list,（常数列表）；,”,,32,,,－试一试－,使用集合

25、改写下面程序：,,min=-5*x1-2*x2,；,,2*x1+x2+x3=8,；,,x1+x4=3,；,,x2+x5=4;,,请动手试一下,MODEL,:,,TITLE,,露一小手,;,,SETS,:!,集合段,;,,HANG/1..3/:B;,,LIE/1..5/:C,X;,,XISHU(HANG,LIE):A;,,ENDSETS,,DATA,:,,A= 2 1 1 0 0,,1 0 0 1 0,,0 1 0 0 1;,,C=-5 -2 0 0 0;,,B=8 3 4;,,ENDDATA,,[OBJ],MIN=@SUM,(LIE:C*X);,,@FOR,(HANG(I):[YUESHU]

26、,,,@SUM,(LIE(J):A(I,J)*X(J))=B(I));,,END,SETS,:,,HANG:B;,,……,,ENDSETS,,DATA,:,,HANG=1..3;,,……,,ENDDATA,,……,教你一招,,33,,,线性规划,怎样建立优化模型与,LINGO,软件的使用,,34,,,线性规划模型的一般形式：,,35,,,一般线性规划问题都可以通过引入非负的松弛变量,slack variable,与非负的剩余变量,surplus v-ariable,的方法化为标准形式（约束全是等约束）。,线性规划问题的可行域,feasible region,是一个凸集,convex set,（

27、任意两点的连线上的点都在区域内部，可以看作是没有凹坑的凸多面体），所以最优解,Optimal solution/point,在凸多面体的某个顶点上达到,求解方法：单纯形算法,simplex method,。,,36,,,连续性线性规划,,1.,比例性,：每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比。,,2.,可加性,：每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关。,,3.,连续性,：每个决策变量的取值都是连续的。,线性规划问题的性质,,37,,,例,3,阶段生产问题,某公司生产某产品,,,最大生产能力为,10000,单位,,,每单位,,存储费,2,元,,,预

28、定的销售量与单位成本如下,:,月份,单位成本,(,元,),销售量,1,,2,,3,,4,,70 6000,,72 7000,,80 12000,,76 6000,求一生产计划,,,使,1),满足需求,; 2),不超过生产能力,;,,3),成本,(,生产成本与存储费之和,),最低,.,,38,,,解,:,假定,1,月初无库存,,4,月底买完,,,当月生产的不库,

29、,存,,,库存量无限制,.,第,j+1,个月的库存量,第,j+1,个月的库存费,共,3,个月的库存费,到本月总生产量大于等于销售量,4,个月总生产量等于总销售量,4,个月总生产成本,,39,,,,model,:,,title,,生产计划程序,1;,,Sets,:,,yuefen/1..4/:c,x,e,d;,,endsets,,data,:,,c=70 71 80 76;,,d=6000 7000 12000 6000;,,e=2 2 2 2 ;,,a=10000;,,enddata,,min,=,@sum,(yuefen:c*x)+,,,@sum,(yuefen(j)|j#lt#4:,,,@

30、sum,(yuefen(i)|i#le#j:x-d)*e(j+1));,,@for,(yuefen(j)|j#lt#4:,,,@sum,(yuefen(i)|i#le#j:x)>,@sum,(yuefen(i)|i#le#j:d));,,@sum,(yuefen:x)=,@sum,(yuefen:d);,,@for,(yuefen:x

31、0 6000;,,e=2 2 2 2 ;,,a=10000;,,enddata,,min,=,@sum,(yuefen:c*x+e*s);,,@for,(yuefen(i)|i#lt#4:s(i+1)=s(i)+x(i)-d(i));,,s(4)+x(4)-d(4)=0;,,s(1)=0,;,,@for,(yuefen:x

32、 6000,,43,,,76,82,76,76,-,-,-,80,-,-,74,72,-,74,72,70,生产月,,10000,10000,10000,10000,产量,6000,4,12000,7000,6000,销量,4,3,2,1,3,2,1,,需求月,费用,c,ij,,44,,,,45,,,model,:,,title,,生产计划程序,3;,,sets,:,,yuefen/1..4/:a,d,xx;,,!,定义上三角矩阵,;,,link(yuefen,yuefen)|,,endsets,,data,:,,c=70 72 74 76,,71 73 75,,80 82,,

33、76;,,d=6000 7000 12000 6000;,,a=10000 10000 10000 10000;,,enddata,,min,=,@sum,(link:c*x);,,@for,(yuefen(i):,@sum,(yuefen(j)|j#ge#i:x(i,j))d(j););,,!,得到每个月的生产量,;,,@for,(yuefen(i):xx=,@sum,(yuefen(j):x(i,j)));,,End,,46,,,Model Title: :,生产计划程序,1

34、,,Variable Value Reduced Cost,,A 10000.00 0.000000,,C( 1) 70.00000 0.000000,,C( 2) 71.00000 0.000000,,C( 3) 80.00000 0.000000,,C( 4) 76.00000 0.000000,,X( 1) 10000.00 0.000000

35、,,X( 2) 10000.00 0.000000,,X( 3) 5000.000 0.000000,,X( 4) 6000.000 0.000000,,E( 1) 2.000000 0.000000,,E( 2) 2.000000 0.000000,,E( 3) 2.000000 0.000000,,E( 4) 2.000000 0.00000

36、0,,D( 1) 6000.000 0.000000,,D( 2) 7000.000 0.000000,,D( 3) 12000.00 0.000000,,D( 4) 6000.000 0.000000,,,,47,,,课堂练习,1:,转运问题,设有两个工厂,A,、,B,，产量都是,10,万个，工厂有三个仓库,x,，,y,，,z,，产品都先送到仓库。现有四个顾客分别为甲，乙，丙，丁，需求量分别为,3,，,5,，,4,，,5,万个。工厂到仓库、仓库到顾客

37、的运费单价（元,/,个）见下表所示。试求总运费最少的运输方案以及总运费。,,A,B,甲,乙,丙,丁,x,4,3,5,7,10,20,y,2,1,9,6,7,15,z,5,2,20,6,7,4,,48,,,连续投资,10,万元,A,：从第,1,年 到第,4,年每年初要投资，次年末回收本利,1.15,B,：,第3年初投资，到第5年末回收1.25,，最大投资,4,万元,C,：,第2年初投资，到第5年末回收1.40,，最大投资,3,万元,D,：,每年初投资，每年末回收1.11,。,求：,5,年末总资本最大。,课堂练习,2:,连续投资,,49,,,灵敏度分析与影子价格,,50,,,,例,4,生产计划问题

38、,某工厂计划安排生产,Ⅰ,，,Ⅱ,两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及,A,B,两种原材料的消耗，现有原材料和设备台时的定额如表所示，问：,,１）怎么安排生产使得工厂获利最大？,,２）产品,Ⅰ,的单位利润降低到,1.8,万元，要不要改变生产计划，如果降低到,1,万元呢？,,３）产品,Ⅱ,的单位利润增大到,5,万元，要不要改变生产计划？,,４）如果产品,Ⅰ,，,Ⅱ,的单位利润同时降低了,1,万元，要不要改变生产计划？,,产品,Ⅰ,产品,Ⅱ,最大资源量,设备,1,2,8,台时,原材料,A,4,0,16kg,原材料,B,0,4,12kg,单位产品利润,2,3,,,51,,,,

39、,52,,,程序编写,,,model,:,,title,,生产计划问题,;,,[maxf],max,=2*x1+3*x2;,,[A]x1+2*x2<8;,,[B]4*x1<16;,,[TIME]4*x2<12;,,END,,,53,,,运行结果,,,,Model Title:,生产计划问题,,,Variable Value Reduced Cost,,X1 4.000000 0.000000,,X2 2.000000 0.000000,,Row Slack or Surplus

40、 Dual Price,,MAXF 14.00000 1.000000,,A 0.000000 1.500000,,B 0.000000 0.1250000,,TIME 4.000000 0.000000,,对问题,1,，安排是生产产品,Ⅰ4,单位，产品,Ⅱ2,单位，最大盈,,利为,14,万元,。,,,54,,,－线性模型－敏感性理论,1,目标函数的系数变化的敏感性分析,如果目标函数的系数发生变化，将会影响目标函数,f,斜率的变化，但是只要,f,的斜

41、率小于等于,-1/2,（也就是直线,l,夹在,l,1,与,l,2,之间时），最优解都在,(4,2),上取到，最优解不变，从而生产计划不会变,.,,,55,,,－线性模型－,敏感性分析,1,要使用敏感性分析,,必须要在这里选择,Prices & Ranges,,然后,保存,退出,路径：,,LINGO︱Options︱General Solver,,(,通用求解程序,),选项卡,,56,,,要调出敏感性分析的结果，必须,先求解,后再,在程序窗口下,点击,,LINGO,｜,Range,，,,,57,,,Ranges in which the basis is unchanged:,,Objectiv

42、e Coefficient Ranges,,,Current Allowable Allowable,,Variable Coefficient Increase Decrease,,X1 2.000000 INFINITY 0.5000000,,X2 3.000000 1.000000 3.000000,,Righthand Side Ranges,,Row Current Allowable

43、 Allowable,,RHS Increase Decrease,,A 8.000000 2.000000 4.000000,,B 16.00000 16.00000 8.000000,,TIME 12.00000 INFINITY 4.000000,,当前变量系数,允许增加量,允许减少量,对问题,2,，产品,Ⅰ,的单位利润降低到,1.8,万元，在（,1.5,，∞）之间，所以不改变生产计划。如果降低到,1,万元

44、，不在（,1.5,，∞）内，要改变生产计划。在程序中将目标函数的系数“,2”,改为“,1”,，可得新的计划为,安排是生产产品,Ⅰ2,单位，产品,Ⅱ3,单位，最大盈利为,11,万元,.,,对问题,3,，要改变生产计划，更改程序得新计划为生产产品,Ⅰ2,单位，产品,Ⅱ3,单位，最大盈利为,19,万元,.,,对问题,4,，因为两个系数同时改变了，所以只有更改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到,8,万元,.,,,,58,,,,,59,,,把,y,1,,,y,2,,,y,3,作为三种原料的定价，,定价的目标是在比生产产品获得更多利润的前提下的最小利润,.,在最优情况下，,y,的值

45、就是资源的,影子价格，,影子价格有意义是有范围的,。,影子价格经济含义是：在资源得到最优配置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量．,,,60,,,Ranges in which the basis is unchanged:,,Objective Coefficient Ranges,,,Current Allowable Allowable,,Variable Coefficient Increase Decrease,,X1 2.000000 INFINITY

46、 0.5000000,,X2 3.000000 1.000000 3.000000,,,Righthand Side Ranges,,Row Current Allowable Allowable,,RHS Increase Decrease,,A 8.000000 2.000000 4.000000,,B 16.00000 16.00000 8.000000,,

47、TIME 12.00000 INFINITY 4.000000,,运行结果,,,,Model Title:,生产计划问题,,,Variable Value Reduced Cost,,X1 4.000000 0.000000,,X2 2.000000 0.000000,,Row Slack or Surplus,Dual Price,,MAXF 14.00000,1.000000,,A 0.000000,1.

48、500000,,B 0.000000,0.1250000,,TIME 4.000000,0.000000,,,,61,,,1,桶牛奶,3,公斤,A,1,,12,小时,8,小时,4,公斤,A,2,,或,获利,24,元,/,公斤,获利,16,元,/,公斤,50,桶牛奶,时间,480,小时,至多加工,100,公斤,A,1,,制订生产计划，使每天获利最大,,35,元可买到,1,桶牛奶，买吗？若买，每天最多买多少,?,可聘用临时工人，付出的工资最多是每小时几元,?,,A,1,的获利增加到,30,元,/,公斤，应否改变生产计划？,每天：,例,5,加工奶制品的生产计划,,62,,

49、,x,1,桶牛奶生产,A,1,,x,2,桶牛奶生产,A,2,,获利,24×3,x,1,,获利,16×4,x,2,,原料供应,,劳动时间,,加工能力,,决策变量,,目标函数,,每天获利,约束条件,非负约束,,线性规划模型,(LP),,,63,,,Max=72*x1+64*x2;,,x1+x2<50,;,,12*x1+8*x2<480;,,3*x1<100;,,OBJECTIVE FUNCTION VALUE,,,1) 3360.000,,,VARIABLE VALUE,REDUCED COST,,,X1 20.000000,0.000000

50、,,,X2 30.000000,0.000000,,ROW SLACK OR SURPLUS DUAL PRICES,,2) 0.000000 48.000000,,3) 0.000000 2.000000,,4) 40.000000 0.000000,,NO. ITERATIONS= 2,20,桶牛奶生产,A,1,, 30,桶生产,A,2,，利润,3360,元。,,,64,,,,OBJECT

51、IVE FUNCTION VALUE,,1) 3360.000,,VARIABLE VALUE REDUCED COST,,X1 20.000000 0.000000,,X2 30.000000 0.000000,,ROW SLACK OR SURPLUS,DUAL PRICES,,,2),0.000000,48.000000,,,3),0.000000,2.000000,,,4),40.000000,0.000000,,35,元可买到,1,桶牛奶，

52、要买吗？,35 <48,,应该买！,聘用临时工人付出的工资最多每小时几元？,2,元！,,,65,,,RANGES IN WHICH THE BASIS IS UNCHANGED:,,OBJ COEFFICIENT RANGES,,VARIABLE CURRENT ALLOWABLE ALLOWABLE,,COEF INCREASE DECREASE,,,X1 72.000000 24.000000 8.000000,,X2 64.000000 8.000000

53、 16.000000,,RIGHTHAND SIDE RANGES,,ROW CURRENT ALLOWABLE ALLOWABLE,,RHS INCREASE DECREASE,,,2 50.000000 10.000000 6.666667,,3 480.000000 53.333332 80.000000,,4 100.000000 INFINITY

54、 40.000000,,A,1,获利增加到,30,元,/,千克，应否改变生产计划？,不变！,,35,元可买到,1,桶牛奶，每天最多买多少？,最多买,10,桶！,,,66,,,整数规划,,67,,,问题： 如何下料最节省,?,原料钢管,:,每根,19,米,4,米,50,根,6,米,20,根,8,米,15,根,客户需求,,例,6,下料问题,,68,,,按照客户需要在一根原料钢管上安排切割的一种组合。,,余料,1,米,4,米,1,根,6,米,1,根,8,米,1,根,余料,3,米,4,米,1,根,6,米,1,根,6,米,1,根,合理切割模式,的余料应小于客户需要钢管的最小尺寸,余料,3,米,8

55、,米,1,根,8,米,1,根,,69,,,model,:,,title,,搜索合理的下料方式,;,,sets,:,,ren:;,!,用一根原料可下各需求长度的最多根数定义元素个数，最多为,4,，这里要定义,5(0—4,有,5,个数,);,,long(ren,ren,ren):;,!,有三种需求长度，定义三维数组,;,,endsets,,data,:,,ren=1..5;,,!,为了美观输出一些题头,;,,@text,('d:renxinglong.txt')=,@write,(1*' ',',下料方式,',7*' ',',余料长度,',,@newline,(1));,,@text,('d:re

56、nxinglong.txt')=,@write,(12*'-',4*' ',8*'-',,@newline,(1));,,!,搜索所有满足过滤条件的,i,j,k;,,@text,('d:renxinglong.txt')=,@writefor,(long(i,j,k)|,,(19-8*(i-1)-6*(j-1)-4*(k-1))#ge#0,,#and#(19-8*(i-1)-6*(j-1)-4*(k-1))#lt#a,,,!,一种下料方式下料长度和不超过总长度,,,合理模式的余料小于最短需求,;,,,!,输出下料方式到文本文件,renxinglong.txt,，我们需要的数是,0--4;,,,

57、:i-1,4*' ',j-1,4*' ',k-1,8*' ',19-8*(i-1)-6*(j-1)-4*(k-1),,@newline,(2));,,!,输出计算段计数过的下料方式总数,;,,@text,('d:renxinglong.txt')=,@write,(',下料方式总数为：,',2*' ',n,',种,');,,Enddata,,,70,,,calc,:,,a=,@smin,(8,6,4);,,b=,@floor,(19/a)+1;,,n=0;,,@for,(long(i,j,k)|,,(19-8*(i-1)-6*(j-1)-4*(k-1))#ge#0,,#and#(19-8*(i

58、-1)-6*(j-1)-4*(k-1))#lt#a,,:n=n+1);,!,下料方式计数,;,,endcalc,,end,,,71,,,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？,模式,,4,米钢管根数,,6,米钢管根数,,8,米钢管根数,,余料,(,米,),,1,,4,,0,,0,,3,,2,,3,,1,,0,,1,,3,,2,,0,,1,,3,,4,,1,,2,,0,,3,,5,,1,,1,,1,,1,,6,,0,,3,,0,,1,,7,,0,,0,,2,,3,,x,i,~,按第,i,种模式切割的原料钢管根数,(,i,=,1,2,…7,),决策变量,,,72

59、,,,2.,所用原料钢管总根数最少,1.,原料钢管剩余总余量最小,目标函数：（,两种标准）,,,73,,,模,,式,,4,米,,根数,,6,米,,根数,,8,米,,根数,,余,,料,,1,,4,,0,,0,,3,,2,,3,,1,,0,,1,,3,,2,,0,,1,,3,,4,,1,,2,,0,,3,,5,,1,,1,,1,,1,,6,,0,,3,,0,,1,,7,,0,,0,,2,,3,,需,,求,,50,,20,,15,,,约束,整数约束：,x,i,为整数,,,74,,,－程序编写－,model,:,,Title,,钢管下料,;,,,Min,=3*x1 + x2 + 3*x3 + 3*x4

60、 + x5 + x6 + 3*x7;,,4*x1 + 3*x2 + 2*x3 + x4 + x5>50;,,x2 + 2*x4 + x5 + 3*x6> 20;,,x3 + x5 + 2*x7>15;,,@gin,(x1);,@gin,(x2);,@gin,(x3);,@gin,(x4);,,@gin,(x5);,@gin,(x6);,@gin,(x7);,,end,程序编写,,75,,,按模式,2,切割,12,根,,,按模式,5,切割,15,根，余料,27,米,,最优解：,x,2,=12,,x,5,=15,,其余为,0,；,,最优值：,27,最优解：,x,

61、2,=15,,x,5,=5,,x,7,=5,,其余为,0,；,,最优值：,25,。,按模式,2,切割,15,根，按模式,5,切割,5,根，按模式,7,切割,5,根，共,25,根，余料,35,米,当余料没有用处时，,通常以总根数最少为目标,,,76,,,课堂练习,3,某服务部门一周中每天需要不同数目的雇员，周一到周四每天至少需要,50,人，周五至少需要,80,人，周六和周日至少需要,90,人，现规定应聘者需连续工作,5,天，试确定聘用方案。,,77,,,0-1,规划,,78,,,例,7,选址问题,,79,,,,80,,,,例,8,面试顺序问题,,有,4,名同学到一家公司参加三个阶段的面试，公司要

62、求每个同学都必须首先找公司秘书初试，然后到主管部门处复试，最后到经理处参加免试，并且不允许插队，由于,4,名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如表所示，这,4,名同学约定他们全部面试完以后一起离开公司，假定现在时间是早上,8,：,00,，请问他们最早何时能离开公司？,,,秘书初试,主管复试,经理面试,同学甲,13,15,20,同学乙,10,20,18,同学丙,20,16,10,同学丁,8,10,15,,81,,,,82,,,优化目标为：,约束条件：,个人时间先后次序约束：,同阶段不同同学时间不相容：（同阶段靠前同学的完成时间小于靠后同学的开始时间）,,83,,,可将目标改

63、为如下线性优化目标：,,84,,,程序编写,,model,:,,title,:,面试问题,;,,sets,:,,student/1..4/:;,,office/1..3/:;,,link1(student,office):x,t;,,link2(student,student)|,,endsets,,data,:,,t=13 15 20,,10 20 18,,20 16 10,,8 10 15 ;,,Enddata,,min,=time;,,!time,大于每名同学最后面试完毕时间,;,,@for,(student(i):time>x(i,3)+t(i,3););,,85,,,!,面试先后次序

64、约束,;,,@for,(student(i):,@for,(office(j)|j#lt#3:x(i,j)+t(i,j)

65、:,,x(k,j)+t(k,j)-x(i,j)<1000*(1-y(i,k)))));,,!,定义,0-1,变量,,,最后通过,0-1,变量可以查看面试顺序,;,,@for,(link2:,@bin,(y));,,End,,86,,,运行结果,,Model Title: :,面试问题,,,Variable Value Reduced Cost,,TIME 84.00000 0.000000,,,……………………,（省略）,,,Y( 1, 2) 0.000000 -1000.000,,Y( 1

66、, 3) 0.000000 0.000000,,Y( 1, 4) 1.000000 1000.000,,Y( 2, 3) 0.000000 -1000.000,,Y( 2, 4) 1.000000 0.000000,,Y( 3, 4) 1.000000 0.000000,,所以面试完成至少需要,84min,，面试顺序为,4-1-2-3,（丁,-,甲,-,乙,-,丙）．,,87,,,课堂练习,4,某班准备从,5,名游泳员中选择４人组成接力队，藏家学校的,4×100m,混合泳接力比赛，,5,名队员,4,种泳姿的百米平均成绩如表，问如何选拔队员。,队员,甲,乙,丙,丁,戊,蝶泳,1’06’’8,57’’2,1’18’’,1’10’’,1’07’’4,仰泳,1’15’’6,1’06’’,1’14’’2,1’14’’2,1’11’’,蛙泳,1’27’’,1’06’’4,1’09’’6,1’09’’6,1’23’’8,自由