数学建模数学规划模型.ppt

《数学建模数学规划模型.ppt》由会员分享，可在线阅读，更多相关《数学建模数学规划模型.ppt（118页珍藏版）》请在三一办公上搜索。

1、1,数学规划模型,2,简介数学规划模型,引例（生产规划问题）：某厂利用a、b、c三种原料生产A、B、C三种产品，已知生产每种产品在消耗原料方面的各项技术条件和单位产品的利润，以及可利用的各种原料的量（具体数据如下表），试制订适当的生产规划使得该厂的总的利润最大。,什么是线性规划,线性规划模型整数规划模型非线性规划模型,3,以,分别表示生产A、B、C三种产品的量，,称之为决策变量，则,目标函数,约束条件,4,目标函数：利润最大化、成本最小化，表现为决策变量的一个函数；,约束条件：资源、工期等，表现为决策变量的一些等式或不等式。,线性规划问题：在满足由一些线性等式或不等式组成的约束条件下，求决策变

2、量的一组具体取值，使得一个线性目标函数实现最优（大或小）化。,线性规划的数学式子,5,线性规划实例：某机床厂生产甲、乙两种机床，每台销售后的利润分别为4元与3元。生产甲机床需用A、B机器加工，加工时间分别为每台 2小时和1小时；生产乙机床需用A、B、C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时，问该厂应生产甲、乙机床各多少台，才能使总利润最大？,非线性规划问题：目标函数或存在约束条件函数是决策变量的非线性函数的最优化问题,整数规划问题：决策变量限取整数值的最优化问题；,6,数学模型：设该厂生产x1台甲机床和x2台乙机床时总利

3、润最大，则 x1、x2应满足,max z=4x1+3x2 s.t 2x1+x2 10 生产甲用A，生产乙用A，x1+x2 8 生产甲用B，生产乙用B（1）x2 7 生产乙用C x1,x2 0,线性规划的 求解方法,单纯形法（表上作业法）,图解法,软件求解法（用Lingo或Lingdo软件）,7,图1,显然等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，本例的最优解为x*=(2,6)T，最优目标值z*=26。,求解线性规划的方法（图解法）,可行点：满足线性规划所有约束条件的点称为问题的可行点。可行域：所有可行点构成的集合称为问题的可行域，记为R。等位线：对于每一固定的值z，使目标函数

4、值等于z的点构成的直线称为目标函数等位线。当z变动时，我们得到一族平行直线（图1）。,8,求解线性规划的方法（软件实现）,model:！程序开始sets:！变量集合开始 var/1.2/:x;！说明x是二维变量endsets！集合说明结束max=4*x(1)+3*x(2);！目标函数求极大2*x(1)+x(2)=10;！约束函数x(1)+x(2)=8;！约束函数x(2)=7;！约束函数End！程序结束 如果不加以 说明,LINGO认为所有变量非负,9,Global optimal solution found at iteration:4 Objective value:26.00000 Va

5、riable Value Reduced Cost X(1)2.000000 0.000000 X(2)6.000000 0.000000 Row Slack or Surplus Dual Price 1 26.00000 1.000000 2 0.000000 1.000000 3 0.000000 2.000000 4 1.000000 0.000000,求解报告窗口,10,不需要变量说明的程序,11,没有变量说明的程序model:max=2*x1+4*x2+3*x3;3*x1+4*x2+2*x3=60;2*x1+x2+2*x3=40;x1+3*x2+3*x3=80;End,Global

6、 optimal solution found.Objective value:76.66667 Total solver iterations:2 Variable Value Reduced Cost X1 0.000000 1.833333 X2 6.666667 0.000000 X3 16.66667 0.000000 Row Slack or Surplus Dual Price 1 76.66667 1.000000 2 0.000000 0.8333333 3 0.000000 0.6666667 4 10.00000 0.000000,12,有变量说明的程序model:set

7、s:var/1.3/:x;endsets max=2*x(1)+4*x(2)+3*x(3);3*x(1)+4*x(2)+2*x(3)=60;2*x(1)+x(2)+2*x(3)=40;x(1)+3*x(2)+3*x(3)=80;End,Global optimal solution found.Objective value:76.66667 Total solver iterations:2 Variable Value Reduced Cost X(1)0.000000 1.833333 X(2)6.666667 0.000000 X(3)16.66667 0.000000 Row Sla

8、ck or Surplus Dual Price 1 76.66667 1.000000 2 0.000000 0.8333333 3 0.000000 0.6666667 4 10.00000 0.000000,13,练习：建立下列数学模型,1、某厂生产A、B两种产品，消耗三种资源。已知单位产品消耗资源数量以及单位产品销售利润如表所示。假设一个月内工厂可利用的煤W吨，可利用的技术工时为Q小时，工厂在一个月内必须完成的利润为P元。在充分发挥人力的条件下（即Q小时全部用完），如何安排生产任务，既要完成利润计划，又要使消耗电量最省。,14,2、某车间在未来的五天内所需的某种刀具统计资料如表所示。每

9、把刀具成本0.6元。用过的刀具送机修车间研磨，每把需花费0.2元。刀具每天用过后，如果立即送去磨，两天后可以磨好送回，供当天的需要。第五天后，刀具全部换新的。假设开始时，该车间没有任何刀具。问这个车间需要多少刀具才能应付需要，而成本又最低,15,Global optimal solution found.Objective value:340.0000 Infeasibilities:0.000000 Total solver iterations:0 Variable Value Reduced Cost X1 120.0000 0.000000 X2 85.00000 0.000000 X

10、3 40.00000 0.000000 X4 60.00000 0.000000 X5 140.0000 0.000000 Row Slack or Surplus Dual Price 1 340.0000-1.000000 2 0.000000-0.2000000 3 0.000000-0.2000000 4 0.000000-0.2000000 5 0.000000-0.6000000 6 0.000000-0.6000000,model:min=0.6*(x1+x2+x3+x4+x5)+0.2*x1+0.2*x2+0.2*(x1+x3);x1=120;x2=85;x1+x3=160;x

11、2+x4=145;x1+x3+x5=300;end,16,4.1 奶制品的生产与销售,一奶制品加工厂用牛奶生产A1，A2两种奶制品，1桶牛奶可以在设备甲上用12小时加工成3公斤A1，或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产的A1，A2全部能售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤A1，设备乙的加工能力没有限制。试为该厂制定一个生产计划，使每天获利最大，,17,并且进一步讨论以下三个附加问题。（1）若用35元可以买到一桶牛奶，应否作这项投资？若投资，每天至多

12、买多少桶牛奶？（2）若可以聘用临时工以增加劳动时间，付给临时工的工资最多每小时几元？（3）由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？,18,企业生产计划,奶制品的生产与销售,空间层次,工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；,车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。,时间层次,若短时间内外部需求和内部资源等不随时间变化，可制订单阶段生产计划，否则应制订多阶段生产计划。,19,加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,3

13、5元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天：,20,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,21,模型求解,图解法,约束条件,目标函数,z=c(常数)等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。

14、,22,模型求解（软件求解）,model:sets:var/1.2/:x;endsetsmax=72*x(1)+64*x(2);x(1)+x(2)=50;12*x(1)+8*x(2)=480;3*x(1)=100;end,23,求解结果及其解释,max 72x1+64x2st2）x1+x250 牛奶原料3）12x1+8x2480 劳动时间4）3x1100 加工能力end,三种资源,原料无剩余时间无剩余加工能力剩余40,“资源”剩余为零的约束为紧约束（有效约束）,原料增加1单位,利润增长48时间增加1单位，利润增长2 加工能力增加，利润不增加,24,回答模型中的问题,OBJECTIVE FUNC

15、TION 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,原料增加1单位,利润增长48,时间增加1单位,利润增长2,加工能力增长不影响利润,35元可买到1桶牛奶，要买吗？,35 48,应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,影子价格：资源增加1单位，效益的增量称

16、为影子价格。对偶价格给出3种资源在最优解下资源增加1单位的效益增量。也就是影子价格,25,用程序验证我们的分析结果,牛奶：51桶利润：3360+48=3408,26,灵敏性分析,一般情况下，目标函数的系数发生变化，最优解会发生变化，那么，系数在什么范围内最优解不发生变化呢？注：约束条件不变！,分析一：分析最优解不变时（即不改变生产计划）目标函数系数的允许变化范围。,27,Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable Allowable Variable Coeffici

17、ent Increase Decrease X(1)72.00000 24.00000 8.000000 X(2)64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 2 50.00000 10.00000 6.666667 3 480.0000 53.33333 80.00000 4 100.0000 INFINITY 40.00000,x1系数范围(64,96),x2系数范围(48,72),A1获利增加到 30元/千克，应否改变生产计划,x

18、1系数由24 3=72增加为303=90，在允许范围内,不变！,软件使用方法：lingo菜单 Range，查看灵敏性分析,28,分析二：原料是否可以无限制的增加,29,30,结果解释,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 16.000000 RIGHTHAND SIDE RANGES

19、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 40.000000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶，每天最多买多少？,最多买10桶!,(目标函数不变),问题：为什么原料的减少量不能少于6.66桶,31,软件介绍,1、问题的输入,model:！程序开始sets:！变量集合开始 var/1.2/:x;！说

20、明x是二维变量endsets！集合说明结束max=4*x(1)+3*x(2);！目标函数求极大2*x(1)+x(2)=10;！约束函数x(1)+x(2)=8;！约束函数x(2)=7;！约束函数End！程序结束 如果不加以 说明,LINGO认为所有变量非负,max=Cx Axb x0用拒阵乘法编的程序model:sets:row/1.3/:b;！定义3 维向量 col/1.2/:c,x;！定义2个二维向量 matrix(row,col):A;定义32的矩阵endsetsmax=sum(col:c*x);！目标函数 for(row(i):sum(col(j):A(i,j)*x(j)=b(i);da

21、ta:c=4,3;b=10,8,7;A=2,1,1,1,0,1;enddataend,32,问题的求解,求解图标,结果分析,33,LINGO菜单介绍,1.文件（File）菜单,（1）新建（2）打开（3）保存（4）另存为（5）关闭（6）打印（7）打印设置（8）打印预览（9）输出到文本文件（10）批处理文件（命令文件和模型文件打包，以便自动运行）（11）引入lingo文件（12）退出,34,2、编辑（Edit）菜单,（1）恢复（取消上次操作）（2）再恢复（撤销上次撤销的操作）（3）剪切（4）复制（5）粘贴（6）全部选定（Select all）（7）查找（8）再次查找上次查找内容（9）替换（10）到

22、指定行：到达当前活动窗口中输入数字的指定行（11）匹配表示（12）粘贴函数（13）选择新的字体,35,3、lingo菜单,（1）求解模型（2）求解结果的显示（3）查看当前模型灵敏度分析结果（4）选项（改变模型参数)(5)显示模型（6）模型图片（7）模型计算结果统计（8）查看（look）,36,4、窗口（window)菜单,（1）打开命令窗口（2）打开状态窗口（3）窗口切换（4）关闭全部窗口（5）窗口平铺（将打开窗口在lingo程序窗口中平铺）（6）窗口排列,37,复习上节内容,利用lingo求解可以得到以下结果（1）最优解（最优生产计划及获得最优效益）（2）影子价格（即:资源增加一个单位效益增

23、加量）利用lingo可以查看灵敏度分析（1）分析最优解不变时（即不改变生产计划），目标函数系数的允许变化范围。（2）原料是否可以无限制的增加,38,例2 奶制品的生产销售计划,在例1基础上深加工,制订生产计划，使每天净利润最大,30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？,50桶牛奶,480小时,至多100公斤A1,B1，B2的获利经常有10%的波动，对计划有无影响？,例1：一奶制品加工厂用牛奶生产A1，A2两种奶制品，1桶牛奶可以在设备甲上用12小时加工成3公斤A1，或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产的A1，A2全部能售出，且每公

24、斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤A1，设备乙的加工能力没有限制。(最优生产计划：20捅生产A1，30捅生产A2）在例1基础上进行深加工：加工的A1一部分用来生产B1，每千克A1生产0.8千克B1，费用3元，所用时间2小时，每千克B1获利44元。加工的A2一部分用来生产B2，每千克A2生产0.75千克B2，费用3元，所用时间2小时，每千克B2获利32元。试为该厂制定一个生产计划，使每天获利最大，,39,出售x1 千克 A1,x2 千克 A2，,x3千克 B1,x4千克 B2,原料

25、供应,劳动时间,加工能力,决策变量,目标函数,利润,约束条件,非负约束,x5千克 A1加工B1，x6千克 A2加工B2,附加约束,40,模型求解,软件实现,LINGO 9.0,model:sets:var/1.6/:x;endsetsmax=24*x(1)+16*x(2)+44*x(3)+32*x(4)-3*x(5)-3*x(6);4*x(1)+3*x(2)+4*x(5)+3*x(6)=600;4*x(1)+2*x(2)+6*x(5)+4*x(6)=480;x(1)+x(5)=100;x(3)=0.8*x(5);x(4)=0.75*x(6);end,Global optimal solutio

26、n found at iteration:2 Objective value:3460.800 Variable Value Reduced Cost X(1)0.000000 1.680000 X(2)168.0000 0.000000 X(3)19.20000 0.000000 X(4)0.000000 0.000000 X(5)24.00000 0.000000 X(6)0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 2 0.000000 3.160000 3 0.000000 3.260000

27、4 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000,41,Objectivevalue:1)3460.800 Variable Value Reduced CostA1 X1 0.000000 1.680000A2 X2 168.000000 0.000000B1 X3 19.200001 0.000000B2 X4 0.000000 0.000000A1B1 X5 24.000000 0.000000A2B2 X6 0.000000 1.520000 Row Slack or Surplus Dual Price牛奶 2)0

28、.000000 3.160000时间 3)0.000000 3.260000加工能力4)76.000000 0.000000 5)0.000000 44.000000 6)0.000000 32.000000,结果解释,每天销售168 千克A2和19.2 千克B1，24千克A1加工成B1,利润3460.8（元）,24/3=8桶牛奶加工成A1，168/4=42桶牛奶加工成A2，将得到的24千克A1全部加工成B1,42,结果解释,增加1桶牛奶使利润增长3.1612=37.92,增加1小时时间使利润增长3.26,30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？,投资

29、150元增加5桶牛奶，可赚回189.6元。（大于增加时间的利润增长）,Objectivevalue:1)3460.800 Variable Value Reduced CostA1 X1 0.000000 1.680000A2 X2 168.000000 0.000000B1 X3 19.200001 0.000000B2 X4 0.000000 0.000000A1B1 X5 24.000000 0.000000A2B2 X6 0.000000 1.520000 Row Slack or Surplus Dual Price牛奶 2)0.000000 3.160000时间 3)0.00000

30、0 3.260000加工能力4)76.000000 0.000000 5)0.000000 44.000000 6)0.000000 32.000000,43,结果解释,Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X(1)24.00000 1.680000 INFINITY X(2)16.00000 8.150000 2.100000 B1 X(3)44.00000 19

31、.75000 3.166667 B2 X(4)32.00000 2.026667 INFINITY X(5)-3.000000 15.80000 2.533333 X(6)-3.000000 1.520000 INFINITY Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 2 600.0000 120.0000 280.0000 3 480.0000 253.3333 80.00000 4 100.0000 INFINITY 76.00000 5 0.0 INFINITY 19.20000

32、 6 0.0 INFINITY 0.0,灵敏性计算方法：菜单lingo(option）选择General Solver选择Price&Range,44-3.16B144+19.75,B1获利下降10%，即44-4.4 超出X3 系数允许范围,32-2.02B232,B2获利上升10%，即32+3.2,超出X4 系数允许范围,结论：波动对计划有影响,生产计划应重新制订：如将x(3)的系数改为39.6计算（B1利润下降10），会发现结果有很大变化。,B1,B2的获利有10%的波动，对计划有无影响,44,X(3)系数变为39.6,结论：将x3的系数改为39.6计算，生产计划发生了很大变化。,45,作

33、业,设某工厂有甲、乙、丙、丁四台机床，生产A、B、C、D、E、F六种产品，加工每一件产品所需时间（工时）和每一件产品的单价已知，如下表所示，表中没有填数的表示这台机床不能加工这种零件。假设甲、乙、丙、丁四台机床的最大工作能力分别为850、700、600、900工时，问在机床能力许可的条件下，每件产品应生产多少才能使该厂生产的利润最大。试建立此数学模型并求解。,46,4.2 自来水输送与货机装运,生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；,运输问题,各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少。,47,问题：某城市

34、有甲、乙、丙、丁四个居民区，自来水由A、B、C三个水库供应，四个区基本用水量（必须保证）分别为30、70、10、10千吨，三个水库最多供水量分别50、60、50千吨。自来水公司从水库向各个小区送水付出引水管理费不同，其它管理费是450元/千吨。各小区收费相同，标准900元/千吨。此外，四个小区申请额外用水量分别50、70、20、40千吨，该公司应如何分配供水量能使利润最大？若水库供水量都提高一倍，公司利润可增加到多少？,例1 自来水输送,48,其他费用:450元/千吨,应如何分配水库供水量，公司才能获利最多？,若水库供水量都提高一倍，公司利润可增加到多少？,例1 自来水输送,收入：900元/千

35、吨,支出,49,总供水量：160,确定送水方案使利润最大,问题分析,总需求量：120+180=300,总收入900160=144,000(元),收入：900元/千吨,其他费用:450元/千吨,支出,引水管理费,其他支出450160=72,000(元),50,供应限制,约束条件,需求限制,线性规划模型(LP),目标函数,水库i 向j 区的日供水量为 xij（x34=0）,决策变量,模型建立,确定3个水库向4个小区的供水量,51,模型求解,model:sets:kar/1.3/;car/1.4/;var(kar,car):x;endsetsmin=160*x(1,1)+130*x(1,2)+220

36、*x(1,3)+170*x(1,4)+140*x(2,1)+130*x(2,2)+190*x(2,3)+150*x(2,4)+190*x(3,1)+200*x(3,2)+230*x(3,3);x(1,1)+x(1,2)+x(1,3)+x(1,4)=50;x(2,1)+x(2,2)+x(2,3)+x(2,4)=60;x(3,1)+x(3,2)+x(3,3)=50;x(1,1)+x(2,1)+x(3,1)=30;x(1,2)+x(2,2)+x(3,2)=70;x(1,3)+x(2,3)+x(3,3)=10;x(1,4)+x(2,4)=10;End,Objective value:24400.00V

37、ariable Value Reduced Cost X(1,1)0.000000 30.00000 X(1,2)50.00000 0.000000 X(1,3)0.000000 50.00000 X(1,4)0.000000 20.00000 X(2,1)0.000000 10.00000 X(2,2)50.00000 0.000000 X(2,3)0.000000 20.00000 X(2,4)10.00000 0.000000 X(3,1)40.00000 0.000000 X(3,2)0.000000 10.00000 X(3,3)10.00000 0.000000 X(3,4)0.0

38、00000 0.000000,52,结果解释,利润=总收入-其它费用-引水管理费=144000-72000-24400=47600（元）,引水管理费 24400(元),Objective value:24400.00 Variable Value Reduced Cost X(1,1)0.000000 30.00000 X(1,2)50.00000 0.000000 X(1,3)0.000000 50.00000 X(1,4)0.000000 20.00000 X(2,1)0.000000 10.00000 X(2,2)50.00000 0.000000 X(2,3)0.000000 20.0

39、0000 X(2,4)10.00000 0.000000 X(3,1)40.00000 0.000000 X(3,2)0.000000 10.00000 X(3,3)10.00000 0.000000 X(3,4)0.000000 0.000000,53,目标函数,总供水量(320)总需求量(300),每个水库最大供水量都提高一倍,利润=收入(900)其它费用(450)引水管理费,供应限制,问题讨论,确定送水方案使利润最大,需求约束不变,54,计算三个水库分别向四个小区供应每千吨水的利润,利润/千吨=收入(900)其它费用(450)引水管理费=450-引水管理费,引水管理费,利润,55,模型程

40、序及求解结果,model:sets:kar/1.3/;car/1.4/;var(kar,car):x;endsetsmax=290*x(1,1)+320*x(1,2)+230*x(1,3)+280*x(1,4)+310*x(2,1)+320*x(2,2)+260*x(2,3)+300*x(2,4)+260*x(3,1)+250*x(3,2)+220*x(3,3);x(1,1)+x(1,2)+x(1,3)+x(1,4)=30;x(1,2)+x(2,2)+x(3,2)=70;x(1,3)+x(2,3)+x(3,3)=10;x(1,4)+x(2,4)=10;end,Global optimal so

41、lution found at iteration:0 Objective value:88700.00 Variable Value Reduced Cost X(1,1)0.000000 20.00000 X(1,2)100.0000 0.000000 X(1,3)0.000000 40.00000 X(1,4)0.000000 20.00000 X(2,1)30.00000 0.000000 X(2,2)40.00000 0.000000 X(2,3)0.000000 10.00000 X(2,4)50.00000 0.000000 X(3,1)50.00000 0.000000 X(3

42、,2)0.000000 20.00000 X(3,3)30.00000 0.000000 X(3,4)0.000000 0.000000,56,结果解释,Objective Value 1)88700.00 Variable Value Reduced Cost X11 0.000000 20.000000 X12 100.000000 0.000000 X13 0.000000 40.000000 X14 0.000000 20.000000 X21 30.000000 0.000000 X22 40.000000 0.000000 X23 0.000000 10.000000 X24 50

43、.000000 0.000000 X31 50.000000 0.000000 X32 0.000000 20.000000 X33 30.000000 0.000000,这类问题一般称为“运输问题”(Transportation Problem),总利润 88700（元）,57,例2 货机装运,问题：某架货机有三个货仓：前仓，中仓和后仓三个货仓的载重量和体积都有限制为了保持飞机的平衡，三个货舱中实际载货的重量与其最大容许重量成正比如何安排装运，使该货机本次飞行获利最大？,58,如何装运，使本次飞行获利最大？,三个货舱最大载重(吨),最大容积(米3),货机装运,三个货舱中实际载重必须与其最大载

44、重成比例,飞机平衡,59,目标函数(利润),货机装运,模型建立,xij-第i 种货物装入第j 个货舱的重量,60,货舱容积,约束条件,货舱重量,61,平衡要求,货物供应,货机装运,模型建立,62,model:sets:kar/1.4/;car/1.3/;var(kar,car):x;endsetsmax=3100*(x(1,1)+x(1,2)+x(1,3)+3800*(x(2,1)+x(2,2)+x(2,3)+3500*(x(3,1)+x(3,2)+x(3,3)+2850*(x(4,1)+x(4,2)+x(4,3);x(1,1)+x(2,1)+x(3,1)+x(4,1)=10;x(1,2)+x

45、(2,2)+x(3,2)+x(4,2)=16;x(1,3)+x(2,3)+x(3,3)+x(4,3)=8;480*x(1,1)+650*x(2,1)+580*x(3,1)+390*x(4,1)=6800;480*x(1,2)+650*x(2,2)+580*x(3,2)+390*x(4,2)=8700;480*x(1,3)+650*x(2,3)+580*x(3,3)+390*x(4,3)=5300;8*(x(1,1)+x(2,1)+x(3,1)+x(4,1)-5*(x(1,2)+x(2,2)+x(3,2)+x(4,2)=0;(x(1,2)+x(2,2)+x(3,2)+x(4,2)-2*(x(1,

46、3)+x(2,3)+x(3,3)+x(4,3)=0;x(1,1)+x(1,2)+x(1,3)=18;x(2,1)+x(2,2)+x(2,3)=15;x(3,1)+x(3,2)+x(3,3)=23;x(4,1)+x(4,2)+x(4,3)=12;end,Objective value:121515.8Variable Value Reduced CostX(1,1)0.000000 400.0000X(1,2)0.000000 57.89474X(1,3)0.000000 400.0000X(2,1)7.000000 0.000000X(2,2)0.000000 239.4737X(2,3)8.

47、000000 0.000000X(3,1)3.000000 0.000000X(3,2)12.94737 0.000000X(3,3)0.000000 0.000000X(4,1)0.000000 650.0000X(4,2)3.052632 0.000000X(4,3)0.000000 650.0000,计算程序及计算结果,63,货物2：前仓,后仓8；货物3:前仓3,中仓13；货物4:中仓3。,货机装运,结果解释,最大利润约121516元,货物-供应点货舱-需求点,平衡要求,Objective value:121515.8Variable Value Reduced CostX(1,1)0.

48、000000 400.0000X(1,2)0.000000 57.89474X(1,3)0.000000 400.0000X(2,1)7.000000 0.000000X(2,2)0.000000 239.4737X(2,3)8.000000 0.000000X(3,1)3.000000 0.000000X(3,2)12.94737 0.000000X(3,3)0.000000 0.000000X(4,1)0.000000 650.0000X(4,2)3.052632 0.000000X(4,3)0.000000 650.0000,64,练习,问题：有七种规格的包装箱要装到两节铁路平板车上.包

49、装箱的宽和长是一样的,但厚度(t,cm)和重量(w,kg)是不同的.表中给出包装箱的规格.每节平板车有10.2m厚度的地方可用来装包装箱,载重为40t,由于当地货物的限制,对于c5,c6,c7类包装箱的总数有一个特别的限制:这类箱子所占的空间(厚度)不能超过302.7cm,试把包装箱装到平板车上去使得浪费的空间最小,65,4.3 汽车生产与原油采购,问题：汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。(1)制订月生产计划，使工厂的利润最大.(2)如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？,例1 汽车厂生产计划,66,设每

50、月生产小、中、大型汽车的数量分别为x1,x2,x3,汽车厂生产计划,模型建立,线性规划模型(LP),67,模型求解,3）模型中增加条件：x1,x2,x3 均为整数，重新求解。即整数规划求解,Objective value:632.2581 Variable Value Reduced Cost X(1)64.51613 0.000000 X(2)167.7419 0.000000 X(3)0.000000 0.9462366 Row Slack or Surplus Dual Price 1 632.2581 1.000000 2 0.000000 0.7311828 3 0.000000 0