运筹学（课堂PPT）

运筹学,华南热带农业大学基础学院舒兴明,TeLmail：shuxm02,1,必备知识,基础微积分知识：极限，一元函数微分积分基本知识，多元函数的微分、重积分基本知识；线性代数知识：行列式，矩阵的相关知识，向量相关知识，方程组求解；概率统计知识：概率的概念及其计算方法，随机变量及其特征，一般分布的特征及其概率的计算方法，基本统计知识。,2,文献资料,运筹学手册（1999）徐光辉.北京：科学出版社,优化建模与LINDO/LINGO软件谢金星.薛毅.北京：清华大学出版社,数学模型谭永基等.上海：复旦大学出版社,3,数学模型.姜启源.北京：高等教育出版社,管理科学（运筹学）（加）PeterC.Bell.北京：机械工业出版社,MATLAB7基础与提高飞思科技产品研发中心.北京：电子工业出版社,IntroductiontoOperationsResearchFredrickS.Hillieri=1,2,3,4)。则数学模型为,19,引入向量和矩阵记法，有,其中，,价值向量,决策向量,资源向量,技术系数矩阵,20,线性规划模型的向量写法,sets:juece/1.3/:x,c;ziyuan/1.4/:b;jishu(ziyuan,juece):a;endsetsmax=sum(juece:c*x);for(ziyuan(i):sum(juece(j):a(i,j)*x(j)=b(i);data:c=100,80,70;b=500,450,300,550;a=9,8,65,4,78,3,27,6,4;enddata,这种输入模型的方法叫做集合式输入法，真对大型模型有利,21,Globaloptimalsolutionfoundatiteration:0Objectivevalue:5712.121VariableValueReducedCostX(1)24.242420.000000X(2)0.0000008.484848X(3)46.969700.000000C(1)100.00000.000000C(2)80.000000.000000C(3)70.000000.000000B(1)500.00000.000000B(2)450.00000.000000B(3)300.00000.000000B(4)550.00000.000000,问题的解,22,A(1,1)9.0000000.000000A(1,2)8.0000000.000000A(1,3)6.0000000.000000A(2,1)5.0000000.000000A(2,2)4.0000000.000000A(2,3)7.0000000.000000A(3,1)8.0000000.000000A(3,2)3.0000000.000000A(3,3)2.0000000.000000A(4,1)7.0000000.000000A(4,2)6.0000000.000000A(4,3)4.0000000.000000RowSlackorSurplusDualPrice15712.1211.00000020.00000010.6060630.0000000.9090909412.121210.0000005192.42420.000000,23,sets:juece/1.3/:x,c;ziyuan/1.4/:b;jishu(ziyuan,juece):a;endsets,data:c=100,80,70;b=500,450,300,550;a=9,8,65,4,78,3,27,6,4;enddata,max=sum(juece:c*x);for(ziyuan(i):sum(juece(j):a(i,j)*x(j)=b(i);,集合段,模型段,数据段,集合段以sets：开始，以endsets结束。给出下标集合名称，下标范围，以及与此下标有关的符号变量。,数据段是以data：开始，enddata结束；注意向量都是行写法，每个向量间用“；”隔开；注意矩阵的写法，先行后列输入方式，每行间回车，完毕用分号。,模型段主要书写目标函数和约束函数，各行之间用分号隔开，变量默认非负。,24,案例2运输问题,某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点（销地）出售，各工厂的生产量、各销售地的销售量（单位：吨）以及各个工厂到各个销售点的单位运价（元/吨）表示在下表中，要求研究产品如何调运，才能使得总运费最小。,25,问题理解,1,什么叫做一个完整的调运方案？,2,产地的总产量和销售地的总销售量的关系如何？,3,总运费与什么有关？,4,产地的调出量和销地的销售量应该有什么限制？,分析问题并建立模型,设xij表示从第i产地调往第j销地的调运量；i=1,2,3;j=1,2,3,4，cij表示从第i产地调往第j销地的单位运费（运价）；ai表示第i产地的产量；bj表示第j销地的销量；y表示总运费。,26,A1,A2,A3,B4,B3,B2,B1,a1,a2,a3,b1,b2,b3,b4,x11,x21,x31,x12,x22,x32,x13,x23,x33,x14,x24,x34,运输问题的网络示意图,27,该问题的总产量等于总销售量，所以有,每个销地的销量约束,每个产地的产量约束,各条可能路线运费总和,即该运输问题的数学模型为,28,运输问题的进一步讨论,1,产销不平衡,产大于销，即,这时，数学模型为,29,产小于销，即,2,计算程序编写,注意本问题所涉及的不同下标范围，不同下标形式的字符变量有哪些？单下标和双下标的不同定义方式。,a,书写集合段,30,单下标集合有产地产量集合和销地销量集合，与这两个集合有关的是运价和运量两个集合，称为派生集合（生成集合），或者称为由产量集合和销量集合组合成的笛卡尔集合，定义如下：,endsets,chanliang/1.3/:a;表示生成产量a(1),a(2),a(3);,xiaoliang/1.4/:b；表示生成销量b(1),b(2),b(3),b(4)值得注意的是，这里的1,2,3,4表示变量下标自然顺序，不因为书写而改变。,sets:,chanliang/1,2,3/:a;,xiaoliang/1,2,3,4/:b;,yunjia(chanliang,xiaoliang):c,x;,集合初始语句,与前两个变量的下标都有关系的是运价和运量，所以，派生集合yunjia是双下标，第一个下标是chanliang集合的下标，第二下标是xiaoliang集合的下标,决策变量x和价值系数c都与此集合下标有关，表示为c(i,j),i=1,2,3;j=1,2,3,4;x(i,j),i=1,2,3;j=1,2,3,4。,表示集合定义结束。注意，集合定义中，每个集合定义后，都用分号结束，每个集合有关的变量之间用逗号隔开。,31,b,书写模型段,把所有的c(i,j)*x(i,j),求和，则用如下表达方式,c(1,1)*x(1,1)+c(1,2)*x(1,2)+c(1,3)*x(1,3)+c(1,4)*x(1,4)+c(3,1)*x(3,1)+c(3,4)*x(3,4)。,min=sum(yunjia(i,j):c(i,j)*x(i,j);min=sum(yunjia:c*x);,对yunjia集合中每个元素(i,j),对c(i,j)*x(i,j)求和，表示,如果对每对下标都求和，则上述两种表达方式一样。,32,对每个销地，所有产地运来的货物量恰好等于销售量：,for(xiaoliang(j):sum(chanliang(i):x(i,j)=b(j);,对每个产地，运出的货物量总合恰好等于该产地的产量：,for(chanliang(i):sum(xiaoliang(j):x(i,j)=a(i);,33,data:a=16,10,22;B=8,14,12,14;C=4,12,4,112,10,3,98,5,11,6;enddata,34,sets:chanliang/1.3/:a;xiaoliang/1.4/:b;yunjia(chanliang,xiaoliang):c,x;endsetsmin=sum(yunjia:c*x);,for(chanliang(i):sum(xiaoliang(j):x(I,j)=a(i);for(xiaoliang(j):sum(chanliang(i):x(I,j)=b(j);,data:a=16,10,22;B=8,14,12,14;C=4,12,4,112,10,3,98,5,11,6;enddata,程序组合及调试：,注意：这三个模块，在lingo中放置与顺序无关。且，lingo读取程序与字母大小写无关。如果是产销不平衡，把某些=改成，即可。,35,sets:chanliang/1.3/:a;xiaoliang/1.4/:b;yunjia(chanliang,xiaoliang):c,x;endsetsdata:a=16,10,22;B=8,14,12,14;C=4,12,4,112,10,3,98,5,11,6;enddatamin=sum(yunjia:c*x);for(chanliang(i):sum(xiaoliang(j):x(I,j)=a(i);for(xiaoliang(j):sum(chanliang(i):x(I,j)=b(j);,36,Globaloptimalsolutionfoundatiteration:6Objectivevalue:244.0000,VariableValueReducedCostX(1,1)4.0000000.000000X(1,2)0.0000002.000000X(1,3)12.000000.000000X(1,4)0.0000000.000000X(2,1)4.0000000.000000X(2,2)0.0000002.000000X(2,3)0.0000001.000000X(2,4)6.0000000.000000X(3,1)0.0000009.000000X(3,2)14.000000.000000X(3,3)0.00000012.00000X(3,4)8.0000000.000000,37,与运输问题有关的进一步思考：,1,2,该问题一般从生产销售单位考虑，如果从运输公司出发，会怎么样？有这类现象吗？那种场合会出现？,VariableValueReducedCostX(1,1)4.0000000.000000X(1,2)0.0000002.000000,观察这组最优解，如果想要直接从产地1运输货物到销地2，应该有什么政策？如何实施。,3,如果运送的货物有若干种类，怎么办？这些货物有些可以混合运输，有些则不能混合运送，怎么办？如果有不同的交通运输工具怎么分配？如果货物有运输时间限制，怎么办？,垄断,38,案例3货物装载问题,一艘轮船分前、中、后三个舱位，它们的容积与最大允载重量如表1。现有三种货物待运，已知有关数据列在表2。又为了安全，前、中、后的实际载重量大体保持各舱最大允许载重量的比例关系。具体要求：前、后舱分别与中舱之间的载重量比例上偏差不超过15%，前、后舱之间不超过10%。问轮船应装载A、B、C各多少件才能使运费收入最大？,表1三舱的允载重量与体积约束,39,表2三种货物的数量指标,问题理解,1,一个完整的货物装载方案是什么？,2,如何理解“为了安全，前、中、后的实际载重量大体保持各舱最大允许载重量的比例关系。”,40,建立模型,设xij表示第i种商品装入第j舱的件数，其中，i=1,2,3表示A、B、C三种商品；j=1,2,3表示前、中、后三个舱位。,商品参数符合变量：,ai表示第i商品的数量上限；i=1,2,3vi表示第i商品的单位体积；wi表示第i商品的单位重量；pi表示第i商品的运输单价；,船的装载参数约束：,uj表示第j舱位的体积上限；mj表示第j舱位的重量上限；J=1,2,3;,舱位间的重量比利系数：t1表示中舱与前、后舱位的载重比利系数；t2表示前后舱位之间载重比利系数。,41,s.t,装入三个舱位的商品带来的总运费。,装入的每种商品的总件数不超过商品总数。,每个舱位，装入的三种商品重量总和不超过舱位最大载重量。,每个舱位，装入的三种商品总体积不超过舱位最大体积容量。,前舱的实际载重量和中舱的实际载重量的偏差不超过0.15%,42,后舱载重量与中舱载重量的偏差不超过0.15,后舱与前舱载重量的偏差不超过10%。,43,计算程序,sets:shangpin/1.3/:a,w,v,p;cangwei/1.3/:u,m;fenpei(shangpin,cangwei):x;endsets,data:a=600,1000,800;v=10,5,7;w=8,6,5;p=1000,700,600;m=2000,3000,1500;u=4000,5400,1500;t1=0.15;t2=0.10;enddata,44,max=sum(shangpin(i):p(i)*sum(cangwei(j):x(i,j);for(shangpin(i):sum(cangwei(j):x(i,j)=a(i);for(cangwei(j):sum(shangpin(i):w(i)*x(i,j)=m(j);for(cangwei(j):sum(shangpin(i):v(i)*x(i,j)=u(j);,(1-t1)*sum(shangpin(i):w(i)*x(i,2)=sum(shangpin(i):w(i)*x(i,1);(1-t1)*sum(shangpin(i):w(i)*x(i,2)=sum(shangpin(i):w(i)*x(i,3);(1-t2)*sum(shangpin(i):w(i)*x(i,1)=sum(shangpin(i):w(i)*x(i,3);,45,Globaloptimalsolutionfoundatiteration:5Objectivevalue:608921.6VariableValueReducedCost,X(1,1)208.33330.000000X(1,2)220.58820.000000X(1,3)75.000000.000000X(2,1)0.00000050.00000X(2,2)0.00000050.00000X(2,3)150.00000.000000X(3,1)0.00000025.00000X(3,2)0.00000025.00000X(3,3)0.00000040.00000,46,特别注意，模型在lingo中的输入方式：,Max=sum(shangpin(i):p(i)*sum(cangwei(j):x(i,j);,0.85*sum(shangpin(i):w(i)*x(i,2)=sum(shangpin(i):w(i)*x(i,1);,0.85*sum(fenpei(i,j)|j#eq#2:w(i)*x(i,j)=)大于等于,算术运算符号,逻辑运算符号,逻辑运算的结果只有“真”（TRUE)和“假”（FALES)，lingo用1表示True,其它的都是False。,关系运算符号,在lingo程序下字母的大小写是没有区别的,Lingo8.0的基本运算符号,49,常见运算函数,abscosexpfloor(取整）lgm(自变量的gama函数的自然对数）smax(list)（返回列数的最大值）sminsintansign(示性函数）,变量约束函数,gin（取整约束）bin（0-1变量约束）free（自由变量约束）bnd（上下界约束函数）,Lingo基本函数,50,function(setname(set_index_list)|condition：expression_list);,集合循环函数,for对集合setname的每个元素独立生成约束，约束由expression_list描述。max、min、sum依次返回集合setname上的表达式的最大值、最小值、和。,0.85*sum(fenpei(i,j)|j#eq#2:w(i)*x(i,j)=sum(shangpin(i)|j#eq#1:w(i)*x(i,j);,其中，function是集合函数名，有for,max,min,sum四种；setname是集合名；set_index_list是集合索引列表；condition是逻辑表达式描述的条件；expression_list是一个表达式，对for函数可以有一组表达式。,51,for(jihe1(i)|i#LE#5#and#i#GE#2:x(i)=2);,利用sets建立一个序列的下标集合，这个问题就是建立了x1-x6,y1-y7这13个变量，Z11-z67由前面两个集合的下标共同生成了42个变量。由sets:开始，endsets结束。,sets:jihe1/1.6/:x;jihe2/1.7/:y;link(jihe1,jihe2):z;endsets,表示的意义为,基本运算、集合、函数的表达,52,sum(jihe2(j)|j#NE#3:y(j)=3);for(link(i,j):x(i)*z(j)=10-p(i,j);y(i)*Z(j)0;,建立模型,s.t,65,其中，M为产品的最大产量，根据问题，产品的最大产量不超过100件，故设M=100；,计算程序：,sets:ziyuan/1.3/:b;chanpin/1.3/:c,x,y,d,e;link(chanpin,ziyuan):f;endsets,data:b=500,300,100;c=8,10,12;e=4,5,6;d=100,150,200;f=2,2,14,3,28,4,3;M=100;enddata,66,max=sum(chanpin:c*x)-sum(chanpin:e*x)-sum(chanpin:d*y);for(ziyuan(j):sum(chanpin(i):f(i,j)*x(i)=b(j);for(chanpin:x=M*y);for(chanpin:bin(y);,Globaloptimalsolutionfoundatiteration:4Objectivevalue:300.0000VariableValueReducedCostX(1)100.00000.000000X(2)0.0000000.000000X(3)0.0000001.500000Y(1)1.000000-50.00000Y(2)0.000000150.0000Y(3)0.000000200.0000,计算结果：,根据计算结果，只需要安排生产第1种产品，可以获得最大利润300。,67,案例6混合配料问题,某糖果厂用原料A，B，C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A，B，C含量、原料成本、各种原料的每月限制用量、三种牌号糖果的单位加工费及售价如下表所示。问该厂每月生产这三种牌号的糖果各多少kg，使该厂获利最大。试建立这个问题的线性规划的数学模型。,68,分析问题,设xi表示第i种糖果的产量(kg)，i=1,2,3;,yij表示第i种糖果中原料j的含量；i=1,2,3,j=1,2,3,qi表示每种糖果的加工费；pi表示每种糖果的售价；,dj表示每种原料的单价；bj表示每种原料的每月限用量；,cij表示第i种糖果中原料j的含量要求（%）。,69,s.t,70,max=sum(tangguo:p*x)-sum(tangguo:q*x)-sum(yuanliao(j):d(j)*sum(tangguo(i):y(i,j);for(tangguo(i):x(i)=sum(yuanliao(j):y(i,j);for(yuanliao(j):sum(tangguo(i):y(i,j)=x(i)*c(i,j);for(link(i,j)|j#ge#3:y(i,j)=c(j);sum(moshi:y)=3;for(moshi:x/100=y);for(moshi:y=c(j);for(moshi(i):16=16);for(moshi(i):sum(yonghu(j):b(j)*x(i,j)=19);for(link:gin(x);for(moshi:gin(y);for(moshi:y=15);for(link:x=3);,在解决第1个问题基础上，增加这两个条件，计算收敛速度快10倍。否则，可能存不可行。,这个上界不宜太小，也不宜太大！,88,Globaloptimalsolutionfoundatiteration:4862Objectivevalue:0.000000,VariableValueReducedCostY(1)14.000000.000000Y(2)15.000000.000000Y(3)11.000000.000000X(1,1)2.0000000.2596895E-07X(1,2)1.0000000.000000X(1,3)1.0000000.1517287E-06X(2,2)1.0000000.000000X(2,3)1.0000000.1067591E-06X(2,4)1.0000000.4043221E-07X(3,1)2.0000000.000000X(3,2)1.0000000.000000X(3,3)1.0000000.000000,89,航班编排问题,某航空公司经营A，B，C三个城市的航线，这些航线每天班次起飞与到达时