线性规划应用课件课件.pptx

《线性规划应用课件课件.pptx》由会员分享，可在线阅读，更多相关《线性规划应用课件课件.pptx（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 产品生产计划：产品生产计划：合理利用人力、物力、财力等，使获利最大。劳动力安排：劳动力安排：用最少的劳动力来满足工作的需要。运输问题：运输问题：如何制定调运方案，使总运费最小。2.线性规划应用线性规划应用第1页/共53页 数学规划的建模有许多共同点，要遵循下列原则：(1)容易理解。建立的模型不但要求建模者理解，还应当让有关人员理解。这样便于考察实际问题与模型的关系，使得到的结论能够更好地应用于解决实际问题。(2)容易查找模型中的错误。这个原则的目的显然与(1)相关。常出现的错误有：书写错误和公式错误。2.线性规划应用线性规划应用第2页/共53页 (3)容易求解。对线性规划来说，容易求解问题主

2、要是控制问题的规模，包括决策变量的个数和约束条件的个数。这条原则的实现往往会与(1)发生矛盾，在实现时需要对两条原则进行统筹考虑。2.线性规划应用线性规划应用第3页/共53页 建立线性规划模型的过程可以分为四个步骤：(1)设立决策变量；(2)明确约束条件并用决策变量的线性等式或不等式表示；(3)用决策变量的线性函数表示目标，并确定是求极大（Max）还是极小（Min）；(4)根据决策变量的物理性质研究变量是否有非负性。2.线性规划应用线性规划应用第4页/共53页 例例3.123.12：某昼夜服务的公交线路每天各某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：时间段内所需司机和乘务人员

3、数如下：人力资源分配的问题人力资源分配的问题设司机和乘务人员分别在各时间段一开始时上班，并连续工作8h，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?第5页/共53页 解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：Min x1+x2+x3+x4+x5+x6 约束条件：s.t.x1+x6 60 x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 x1,x2,x3,x4,x5,x6 0 人力资源分配的问题人力资源分配的问题第6页/共53页例例3.13:3.13:某工厂要做某工厂要

4、做100100套钢架，每套用长为套钢架，每套用长为2.9 2.9 m,m,2.1m,1.5m2.1m,1.5m的圆钢各一根。已知原料每根长的圆钢各一根。已知原料每根长7.4 7.4 m m，问：应如何下料，可使所用原料最省？问：应如何下料，可使所用原料最省？套裁下料问题套裁下料问题解:考虑下列各种下料方案（按一种逻辑顺序给出）把各种下料方案按剩余料头从小到大顺序列出第7页/共53页假设 x1,x2,x3,x4,x5 分别为上面前 5 种方案下料的原材料根数。我们建立如下的数学模型。目标函数：Min x1+x2+x3+x4+x5 约束条件：s.t.x1+2x2+x4 100 2x3+2x4+x5

5、 100 3x1+x2+2x3+3x5 100 x1,x2,x3,x4,x5 0套裁下料问题套裁下料问题第8页/共53页 例例3.14:3.14:明兴公司生产甲、乙、丙明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工三种产品，都需要经过铸造、机加工和装配和装配 三个车间。甲、乙两种产三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸

6、各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各造中，由本公司铸造和由外包协作各应多少件？应多少件？生产计划的问题生产计划的问题第9页/共53页解：解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5 分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。生产计划的问题生产计划的问题第10页/共53页 求 xi 的利润:利润=售价-各成本之和可得到 xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。这样我们建立如下数学模型：目标函数:Max 15x1+10 x2+7x3+13x4+9x5 约束条件：s.t.5x

7、1+10 x2+7x3 8000 6x1+4x2+8x3+6x4+4x5 12000 3x1+2x2+2x3+3x4+2x5 10000 x1,x2,x3,x4,x5 0 生产计划的问题生产计划的问题第11页/共53页 例3.15:永久机械厂生产永久机械厂生产、三种产三种产品，均要经过品，均要经过 A A、B B 两道工序加工。假设有两道工序加工。假设有两种规格的设备两种规格的设备A A1 1、A A2 2能完成能完成 A A 工序；有三工序；有三种规格的设备种规格的设备B B1 1、B B2 2、B B3 3能完成能完成 B B 工序。工序。可在可在 A A、B B的任何规格的设备上加工；的

8、任何规格的设备上加工；可在任意规格的可在任意规格的A A设备上加工，但对设备上加工，但对B B工序工序,只只能在能在B B1 1设备上加工；设备上加工；只能在只能在A A2 2与与B B2 2设备上设备上加工；数据如下表。问：为使该厂获得最大加工；数据如下表。问：为使该厂获得最大利润，应如何制定产品加工方案利润，应如何制定产品加工方案？生产计划的问题生产计划的问题第12页/共53页解：解：设设 x xijkijk 表示第表示第 i i 种产品，在第种产品，在第 j j 种工序上的第种工序上的第 k k 种设备上加工的数量种设备上加工的数量.利利润润 =（销售单价（销售单价 -原料单价）原料单价

9、）产品产品件数件数 之和之和 -（每台时的设备费用（每台时的设备费用设备设备实际使用的总台时数）之和实际使用的总台时数）之和。生产计划的问题生产计划的问题第13页/共53页这样我们建立如下的数学模型:Max 0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123 s.t 5x111+10 x2116000 （设备 A1）7x112+9x212+12x31210000（设备 A2）6x121+8x221 4000 (设备 B1）4x122+11x3227

10、00 (设备 B2）7x123 4000 （设备 B3）生产计划的问题生产计划的问题第14页/共53页x111+x112-x121-x122-x123=0(产品在A、B工序加工的数量相等）x211+x212-x221=0(产品在A、B工序加工的数量相等）x312 -x322 =0(产品在A、B工序加工的数量相等）xijk0,i=1,2,3;j=1,2;k=1,2,3生产计划的问题生产计划的问题第15页/共53页 例例3.13.16:6:某工厂要用三种原料某工厂要用三种原料1 1、2 2、3 3混合调配出三种不同规格的产品甲、混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如乙、丙

11、，数据如下表。问：该厂应如何安排生产，使利润收入为最大？何安排生产，使利润收入为最大？配料问题配料问题第16页/共53页配料问题配料问题 解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学 模型时，要考虑：对于甲：对于甲：x x1111，x x1212，x x1313；对于乙：对于乙：x x2121，x x2222，x x2323；对于丙：对于丙：x x3131，x x3232，x x3333；对于原料对于原料1 1：x x1111，x x2121，x x3131；对于原料对于原料2 2：x x1212，x x2222，x x3232；对于原料对于原料3 3：

12、x x1313，x x2323，x x3333；第17页/共53页目标函数：目标函数：利润最大，利润利润最大，利润 =收入收入 -原料支出原料支出 约束条件：约束条件：规格要求规格要求 4 4 个；个；供应量限制供应量限制 3 3 个。个。Max z=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 配料问题配料问题第18页/共53页s.t.0.5 0.5 x x1111-0.5-0.5 x x12 12-0.5-0.5 x x1313 0 0 （原材料原材料1 1不少于不少于50%50%）-0.25-0.25x x1111+0.75+0.75x x

13、1212-0.25-0.25x x1313 0 0 （原材料原材料2 2不超过不超过25%25%）0.75 0.75x x2121-0.25-0.25x x2222-0.25-0.25x x2323 0 0 （原材料原材料1 1不少于不少于25%25%）-0.5-0.5 x x2121+0.5+0.5 x x2222-0.5 -0.5 x x2323 0 0 （原材料原材料2 2不超过不超过50%50%）x x1111+x x2121+x x3131 100 (100 (供应量限制）供应量限制）x x1212+x x2222+x x3232 100 (100 (供应量限制）供应量限制）x x1

14、313+x x2323+x x3333 60 (60 (供应量限制）供应量限制）x xijij0,0,i i=1,2,3;=1,2,3;j j=1,2,3=1,2,3配料问题配料问题第19页/共53页 例例3.173.17：某部门现有资金：某部门现有资金200200万元，今后五万元，今后五年内考虑给以下的项目投资。已知：项目年内考虑给以下的项目投资。已知：项目A A ：从第一年到第五年每年年初都可投资，当从第一年到第五年每年年初都可投资，当年末能收回本利年末能收回本利110%110%；项目；项目B B：从第一年到第从第一年到第四年每年年初都可投资，次年末能收回本利四年每年年初都可投资，次年末能

15、收回本利125%125%，但规定每年最大投资额不能超过，但规定每年最大投资额不能超过3030万万元；项目元；项目C C：需在第三年年初投资，第五年末需在第三年年初投资，第五年末能收回本利能收回本利140%140%，但规定最大投资额不能超，但规定最大投资额不能超过过8080万元；项目万元；项目D D：需在第二年年初投资，需在第二年年初投资，第五年末能收回本利第五年末能收回本利155%155%，但规定最大投资，但规定最大投资额不能超过额不能超过100100万元。万元。投资问题投资问题第20页/共53页 据测定每万元每次投资的风险指数如下表：据测定每万元每次投资的风险指数如下表：投资问题投资问题第2

16、1页/共53页 a a）应如何确定这些项目的每年投资额，使得应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？第五年年末拥有资金的本利金额为最大？b b）应如何确定这些项目的每年投资额，使得应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在第五年年末拥有资金的本利在330330万元的基础上使万元的基础上使得其投资总的风险系数为最小？得其投资总的风险系数为最小？问：问：投资问题投资问题第22页/共53页投资问题投资问题 解：1）确定决策变量：连续投资问题 设 xij(i=15，j=1、2、3、4)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D

17、(j=4)项目的金额。这样我们建立如下决策变量：A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24第23页/共53页2）约束条件：第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是：x11+x12=200 第二年：B次年末才可收回投资故第二年年初的资金为1.1x11，于是：x21+x22+x24=1.1x11 第三年：年初的资金为1.1x21+1.25x12，于是：x31+x32+x33=1.1x21+1.25x12 第四年：年初的资金为1.1x31+1.25x22，于是：x41+x42=1.1x31+1.25x22 第五年：年

18、初的资金为1.1x41+1.25x32，于是：x51=1.1x41+1.25x32 B、C、D的投资限制：xi2 30(i=1，2，3，4)，x33 80，x24 100投资问题投资问题第24页/共53页a)Max z=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200 x21+x22+x24=1.1x11 x31+x32+x33=1.1x21+1.25x12 x41+x42=1.1x31+1.25x22 x51=1.1x41+1.25x32 xi2 30(i=1、2、3、4)，x33 80，x24 100 xij0(i=1,2,3,4,5；j=1,2,3

19、,4）最优解 Z=341.35 x11=170 x12=63 x13=0 x14=0 x15=33.5 x21=30 x22=24 x23=26.79999 x33=80 x42=1003）目标函数及模型：目标函数及模型：投资问题投资问题第25页/共53页b)Min f=（x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24 s.t.x11+x12 200 x21+x22+x24 1.1x11+200-(x11+x12)x31+x32+x33 1.1x21+1.25x12 x41+x42 1.1x31+1.25x22 x51 1.1x41+1.

20、25x32 xi2 30(i=1、2、3、4)，x33 80，x24 100 1.1x51+1.25x42+1.4x33+1.55x24 330 xij0(i=1,2,3,4,5；j=1,2,3,4）投资问题投资问题第26页/共53页牧草农场问题（最小化问题）牧草农场问题（最小化问题）农场在试验一种新赛马食品。赛马食品有三种：普通饲料、高营养燕麦和新饲料。成分如下表：饲料成分饲料成分普通饲料普通饲料S S高营养燕麦高营养燕麦E E新饲料新饲料A A饲料饲料A0.80.20.0饲料饲料B1.01.53.0饲料饲料C0.10.62.0每磅成本每磅成本0.250.503.00一匹马一天的最小进食量为

21、：一匹马一天的最小进食量为：3 3单位单位A A、6 6单位单位B B、4 4单位单位C C 总摄入量不能超过总摄入量不能超过6 6磅。磅。农场希望找到一种饲料组合，既可以满足马一天的营养需要，又可以农场希望找到一种饲料组合，既可以满足马一天的营养需要，又可以使总成本最低。使总成本最低。第27页/共53页牧场问题的线性规划模型为：牧场问题的线性规划模型为：最小化0.25S+0.50E+3A约束条件饲料A0.8S+0.2E3饲料B1.0S+1.5E+3.0A6饲料C0.1S+0.6E+2.0A4总饲料量S+E+A6S，E,A0最优解 S=3.514 E=0.946 A=1.541第28页/共53

22、页电子通信公司问题（电子通信公司问题（4变量）变量）公司开发了新产品，有4种分销渠道。情况如下表：分销渠道分销渠道单位销售利润单位销售利润单位广告成本单位广告成本单位销售时间单位销售时间航海分销店航海分销店M90102商业分销店商业分销店B8483全国连锁店全国连锁店R7093直接邮购直接邮购D6015无无广告预算广告预算50005000美元，每个分销点最大销售时间美元，每个分销点最大销售时间18001800小时。小时。现阶段产品现阶段产品600600个，个，全国连锁店最少销售全国连锁店最少销售150个个如何分配各渠道的销售量、销售时间以及广告预算，可以使销售利润如何分配各渠道的销售量、销售时

23、间以及广告预算，可以使销售利润最大。最大。第29页/共53页通信公司问题的线性规划模型：通信公司问题的线性规划模型：最大化90M+84B+70R+60D约束条件广告10M+8B+9R+15D5000可销售时间2M+3B+3R1800生产水平M+B+R+D=600连锁店销售要求R150M,B，R,D0最优解 M=25 B=425 AR=150 D=0第30页/共53页威尔特公司企业退休金财务计划威尔特公司企业退休金财务计划公司有一个提前退休计划，未来8年内为68个提前退休人员准备资金如下表(每年年初支付)：理财途径有理财途径有1.1.一年期储蓄一年期储蓄 利率利率4 42.2.第一年年初可以投资

24、政府债券投资（第一年年初可以投资政府债券投资（3 3种），面值种），面值10001000，到期时支，到期时支付付10001000，利率是相对于面值的。利息每年年末提取，利率是相对于面值的。利息每年年末提取,不作复利计算。不作复利计算。收益如下：收益如下：年度年度12345678现金现金需求需求430210222231240195225255第31页/共53页 威尔特公司企业退休金财务计威尔特公司企业退休金财务计划划债券债券价格价格利率利率到期年数到期年数111508.8755210005.50063135011.7507决策变量有决策变量有F F 八年计划所需总金额八年计划所需总金额B B1

25、1 第一年年初买入债券第一年年初买入债券1 1的单位数量的单位数量B B2 2 第一年年初买入债券第一年年初买入债券2 2的单位数量的单位数量B B3 3 第一年年初买入债券第一年年初买入债券3 3的单位数量的单位数量S Si i 第第i i年年初投资于储蓄的金额（年年初投资于储蓄的金额（i=1i=1、2 2、8 8）第32页/共53页威尔特公司企业退休金财务计划：最小值F约束条件第一年F-1.15B1-1B2-1.35B3-S1=430第二年0.08875B1+0.055B2+0.1175B3+1.04S1-S2=210第三年0.08875B1+0.055B2+0.1175B3+1.04S2

26、-S3=222第四年0.08875B1+0.055B2+0.1175B3+1.04S3-S4=231第五年0.08875B1+0.055B2+0.1175B3+1.04S4-S5=240第六年1.08875B1+0.055B2+0.1175B3+1.04S5-S6=195第七年1.055B2+0.1175B3+1.04S6-S7=225第八年1.1175B3+1.04S7-S8=255各参数0最优解 F=1728.794 B1=144.988 B2=187.856 B3=228.188 S1=636.148 S2=501.606 S3=349.682 S4=182.681 S5=S6=S7=S

27、8=0年初可用资金年初可用资金-投资于债券和储蓄的金额投资于债券和储蓄的金额=该年的支付责任该年的支付责任第33页/共53页 资源利用问题资源利用问题 假设某地区拥有m种资源，其中，第i种资源在规划期内的限额为bi(i=1，2，m)。这m种资源可用来生产n种产品，其中，生产单位数量的第j种产品需要消耗的第i种资源的数量为aij(i=1，2，m；j=1,2,n)，第j种产品的单价为cj(j=1，2，n)。试问如何安排这几种产品的生产计划，才能使规划期内资源利用的总产值达到最大?第34页/共53页设第设第j种产品的生产数量为种产品的生产数量为xj(j=1，2，n)，则上述资源问题就是：则上述资源问

28、题就是：求一组实数变量xj(j=1，2，n)，使其满足第35页/共53页 农场种植计划模型农场种植计划模型 某农场I、II、III等耕地的面积分别为100 hm2（公顷）、300 hm2和200 hm2，计划种植水稻、大豆和玉米，要求三种作物的最低收获量分别为190000 kg、130000 kg和350000kg。I、II、III等耕地种植三种作物的单产如表3.3.1所示。若三种作物的售价分别为水稻1.20元/kg，大豆1.50元/kg，玉米0.80元/kg。那么，（1）如何制订种植计划，才能使总产量最大？（2）如何制订种植计划，才能使总产值最大？第36页/共53页表3.3.1不同等级耕地种

29、植不同作物的单产(单位:kg/hm2)I等耕地II等耕地III等耕地水稻1100095009000大豆800068006000玉米140001200010000第37页/共53页对于上面的农场种植计划问题，我们可以用线性规划方法建立模型。根据题意，决策变量设置如表3.3.2所示,表中Xij表示在第j等级的耕地上种植第i种作物的面积。三种作物的产量可以用表3.3.3表示。第38页/共53页表3.3.2作物计划种植面积（单位:hm2)表3.3.3三种作物的总产量（单位:kg）I等耕地II等耕地III等耕地水稻大豆玉米作物种类总产量水稻大豆玉米第39页/共53页根据题意，约束方程如下,耕地面积约束：

30、最低收获量约束：非负约束：第40页/共53页调用Matlab软件系统优化工具箱中的linprog函数，进行求解运算，可以得到一个最优解（如表3.3.4所示）。在该方案下，最优值，即最大总产量为6892200kg。从表中可以看出，如果以追求总产量最大为种植计划目标，那么，玉米的种植面积在I、II、III等耕地上都占绝对优势。（1）追求最大总产量的目标函数为：第41页/共53页表3.3.4追求总产量最大的计划方案（单位：hm2）I等耕地II等耕地III等耕地水稻0021.1111大豆0021.6667玉米100300157.2222第42页/共53页(2)追求最大总产值的目标函数为：进行求解运算，

31、可以得到一个最优解（如表3.3.5所示）。在该方案下，最优值，即最大总产值为6830500元。从表中可以看出，如果以追求总产值最大为种植计划目标，那么，水稻的种植面积在I、II、III等耕地上都占绝对优势。第43页/共53页表3.3.5追求总产值最大的计划方案（单位：hm2）I等耕地II等耕地III等耕地水稻58.75 300 200大豆16.25 00玉米2500第44页/共53页证券组合投资决策证券组合投资决策 某人有一笔50万的资金可用于长期投资，可供选择的投资机会包括购买国库券、公司债券、投资房地产、购买股票或银行保值储蓄等。不同的投资方式的具体参数见下表。第45页/共53页序号投资方

32、式投资期限（年）年收益率（%）风险系数增长潜力（%）1国库券311102公司债券10153153房地产6258304股票2206205短期定期存款110156长期保值储蓄5122107现金存款0300第46页/共53页投资者希望投资组合的平均年限不超过5年，平均的期望收益率不低于13%，平均风险系数不超过4，平均的收益的增长潜力不低于10%.问：在满足上述要求的前提下投资者该如何选择投资组合使平均年收益率最高。第47页/共53页解：由题意，目标：平均年收益率最高；决策变量：设 xi 是第i 种投资在总投资中所占的比例；资源约束：投资组合的平均年限不超过5年；平均的期望收益率不低于13%；平均风

33、险系数不超过4；平均的收益的增长潜力不低于10%；各项投资比例之和等于1。则，其线性规划模型为：第48页/共53页Max Z=11x1+15x2+25x3+20 x4+10 x5+12x6+3x7s.t.3x1+10 x2+6x3+2x4+x5+5x6 5 平均年限x1+3x2+8x3+6x4+x5+2x6 4 风险系数 15x2+30 x3+20 x4+5x5+10 x6 10 增长潜力x1+x2+x3+x4+x5+x6+x7 =1 各项投资比例之和等于1 x1,x2,x3,x4,x5,x6,x7 0第49页/共53页施肥问题施肥问题 某农场主需要对他的20亩菜地和30亩小麦地施肥。经土壤分

34、析后，分析报告指出每亩菜地至少需施6公斤氮，2公斤磷，1.5公斤钾；每亩小麦地至少需施8公斤氮，1公斤磷，3公斤钾。现市场上有A,B两种可用的肥料，相关数据如下表所示。请帮助该农场主制定购买A,B两种肥料的合理预算和施肥方案。每袋重量（公斤）每袋价格（元）氮含量（）磷含量（）钾含量（）A406020520B605010105第50页/共53页解：设xij表示第i种肥施于第j类用地的数量（袋），i=1,2,j=1,2.依题意，建立数学模型如下，min z=60(x11+x12)+50(x21+x22)菜地：400.2x11+600.1x21206400.05x11+600.1x21202400.2x11+600.05x21201.5麦地：400.2x12+600.1x22308400.05x12+600.1x22301400.2x12+600.05x22303xij0,i,j=1,2.第51页/共53页线性规划的其他应用线性规划的其他应用市场营销调查。医院绩效评定等线性规划的其他应用线性规划的其他应用第52页/共53页感谢您的观看！第53页/共53页