线性规划模型学习教案

1、会计学1线性规划线性规划(xin xn u hu)模型模型第一页，共59页。1234,A A A A 1 8 5 2利润/万元 0.1 0.5 0.3 0.2能耗/t标准煤 75 380 250 100工时/h 产品1A2A3A4A第2页/共59页第二页，共59页。已知该厂明年的工时限额为18480h，能耗限额为100t标准煤，欲使该厂明年的总利润最高，请确定定各种产品的生产数量，试建立数学模型。第3页/共59页第三页，共59页。第4页/共59页第四页，共59页。问题问题(wnt)分析分析1234,x x x x1234258xxxx12341002503807518480 xxxx12340

2、.20.30.50.1100 xxxx1234,0 x x x x 第5页/共59页第五页，共59页。模型模型(mxng)建立建立123412341234max258. .10025038075184800.20.30.50.11000,1,2,3,4izxxxxstxxxxxxxxxi由于目标函数 是变量 的线性函数，约束条件是的线性不等式，所以该问题为线性规划问题，简写为LP.z1234,x x x x1234,x x x x第6页/共59页第六页，共59页。线性规划问题线性规划问题(wnt)的特征的特征比例性 可加性 连续性 xi对目标函数的“贡献”与xi取值成正比 xi对约束条件的“贡

3、献”与xi取值成正比 xi对目标函数的“贡献”与xj取值无关 xi对约束条件的“贡献”与xj取值无关 xi取值连续 第7页/共59页第七页，共59页。|例2 设有m种资源(zyun)：12,mA AA，拟生产(shngchn)n种产品：12,nB BB.用ija表示生产1个单位第j种产品所需要的第i种资源的数量，用 表示第i种资源ib的使用限额，用 表示销售一个单位的第j种产品jc获得的利润，用 表示第j种产品的生产数量，则jx12( ,)Tnxx xx就代表一个生产计划，我们的问题是：要设法安排一个生产计划，使该厂获得的总利润最高。第8页/共59页第八页，共59页。|决策变量(binling

4、):n种产品的生产数量|目标：该厂获得的总利润最大| 利润函数：|约束条件：| 资源 的使用限额| 蕴含约束：n种产品产量非负12,nx xx1nijijjc xiA第9页/共59页第九页，共59页。11m ax. .,1, 2,0,1, 2,njjjnijjijjzc xs ta xbimxjn 当拟订的生产计划规模较大时,我们通常采用向量、矩阵记号，则该模型变成什么样了呢？max. .,0.Tzc xst Axbx第10页/共59页第十页，共59页。|设有3个化肥厂：甲、乙、丙，供应3个地区:A,B,C化肥，各厂的化肥年产量、各地区需求量及各厂到3个地区的单位运价见表所示；假设各地区需求量

5、没有满足会造成经济损失: B,C区的单位损失分别为3万元/万吨和2万元/万吨，A区的需求量必须保证，求使得总运费和经济损失费最少的调运方案。实例1 化肥的供应与销售第11页/共59页第十一页，共59页。 A B C年产量（万吨） 甲 5 1 7 10 乙 6 4 6 80 丙 3 2 5 15销量（万吨） 75 20 50销地运价产地万元/万吨第12页/共59页第十二页，共59页。问题问题(wnt)分析分析第13页/共59页第十三页，共59页。, ,1,2,3()ijx i j 万吨Z1111213212223313233(57)(646)(325)Zxxxxxxxxx1222323(20)x

6、xx1323332(50)xxx|1Z第14页/共59页第十四页，共59页。111213212223313233min1605256433Zxxxxxxxxx3113213313113213311 08 01 5. .7 52 05 00 , ,1, 2 , 3jjjjjjiiiiiiijxxxs txxxxij第15页/共59页第十五页，共59页。|假设某种物资有m个产地，n个销地.第i个产地的产量为 ；第 个产地的需要量为 .其中 .由产地i到销地j的距离已知为 ，问应如何分配该种物资，使既能满足各地的需要，又使所花费的运输总吨公里数最少？,1,2,ia imj,1,2,jb jn11mn

7、ijijabijd什么(shn me)是吨公里数呢？吨公里数=运载量*运载公里数第16页/共59页第十六页，共59页。模型模型(mxng)建立建立ijx1111min. .,1,2,1,2,0,1,2,;1,2,.mnijijijnijjinijijijsd xstxbjnxa imxim nn 对运输问题感兴趣的同学可以查阅相关书籍，例如由前苏联数学家编写的生产组织与计划中的数学方法一书提出了这一类问题的数学模型和求解方法。 第17页/共59页第十七页，共59页。|假定有n种食品(shpn)，每种食品(shpn)中含有m种营养成分.其中：ijijjjabicjxj一个单位的第j种食品中含有第

8、i种营养的数量每人每天对第 种营养的最低需求第 种食品的单价所用第 种食品的数量问：应该怎样选配食品，才能保证在满足(mnz)m种营养成分需要的条件下，使食品总成本y最低？第18页/共59页第十八页，共59页。模型模型(mxng)建立建立11min. .,1,2,0,1,2, .njjjnijjijjyc xsta xb imxjn第19页/共59页第十九页，共59页。土地的总面积，即土地的总面积，即2.4 作物布局问题12,nB BB12,mA AA11mnijijab第20页/共59页第二十页，共59页。计划播种面积/平方米 土地面积/平方米111212122212nnmmmncccccc

9、ccc12nBBB12nbbb12mAAA12maaa土地(td)每平产量(chnling)/kg作物(zuw)第21页/共59页第二十一页，共59页。问题问题(wnt)分析分析决策量：各块土地种植某种作物的面积，且非负.目标：总产量最高约束：各块土地上种植作物 面积总和=作物 计划种植面 积 ；第j块土地种植各种作物面积总和= 土地面积 种植面积非负iAiAiajBjbiijjijjiaAbBcBA计划播种作物 的面积土地的面积土地上种植作物 的单位产量第22页/共59页第二十二页，共59页。模型模型(mxng)建立建立1111max. .,1,2,1,2,0,1,2,;1,2,mnijij

10、ijnijijmijjiijyc xstxa imxbjnxim jn这是等式约束第23页/共59页第二十三页，共59页。一一 般般 形形 式式 qjxqjxmpibxaxaxapibxaxaxatsxcxcxczjjininiiininiinn,.,2 , 1;,.,2 , 1; 0,.,1;,.,2 , 1;.min221122112211无无限限制制 目标(mbio)函数约束条件第24页/共59页第二十四页，共59页。注注 释释njxj,.,2 , 1; 为待定的为待定的决策变量决策变量， ),(21ncccc 为为价值向量价值向量， njcj,.,2 , 1; 为为价值系数价值系数，

11、),.,(21mbbbb 为为右端向量右端向量， 矩阵矩阵 为为系数矩阵系数矩阵。 mnmmnnaaaaaaaaaA212222111211第25页/共59页第二十五页，共59页。规规 范范 形形 式式 0.min xbAxtsxc 第26页/共59页第二十六页，共59页。标标 准准 形形 式式 0.min xbAxtsxc 第27页/共59页第二十七页，共59页。概概 念念可可行行解解（或或可可行行点点） ：满满足足所所有有约约束束条条件件的的向向量量 ),(21nxxxx 可可行行集集（或或可可行行域域） ：所所有有的的可可行行解解的的全全体体 0, xbAxxD 最最优优解解：在在可可行

12、行域域中中目目标标函函数数值值最最大大（或或最最小小）的的可可行行解解，最最优优解解的的全全体体称称为为最最优优解解集集合合 DyycxcDxO , 最最优优值值：最最优优解解的的目目标标函函数数值值 Oxxcv , 第28页/共59页第二十八页，共59页。模模 型型 转转 换换令令自自由由变变量量 jjjxxx，其其中中 jjxx ,为为非非负负变变量量 求最大可以等价成求负的最小求最大可以等价成求负的最小 xcxc minmax v目标(mbio)转换v变量(binling)转换第29页/共59页第二十九页，共59页。约约 束束 转转 换换(dngsh)等式等式(dngsh)ininiib

13、xaxaxa 2211 ininiibxaxaxa 2211 ininiibxaxaxa 2211 v等式(dngsh)变不等式(dngsh)第30页/共59页第三十页，共59页。不不 等等 式式 变变 等等 式式ininiibxaxaxa 2211 0,2211 iiininiisbsxaxaxa 或或 ininiibxaxaxa 2211 0,2211 iiininiisbsxaxaxa 松弛(sn ch)变量剩余(shngy)变量第31页/共59页第三十一页，共59页。不等式变不等式不等式变不等式ininiibxaxaxa 2211 ininiibxaxaxa 2211 或或 inini

14、ibxaxaxa 2211 ininiibxaxaxa 2211 第32页/共59页第三十二页，共59页。 052222.21max1212121xxxxxxxtsxxz 7 , 6 , 5 , 4 , 3 , 1; 05)(2)(22)(2.)(min743164315431431ixxxxxxxxxxxxxtsxxxzi 第33页/共59页第三十三页，共59页。图图 解解 法法第34页/共59页第三十四页，共59页。例例 解线性规划解线性规划(xin xn u hu) 第35页/共59页第三十五页，共59页。第36页/共59页第三十六页，共59页。第37页/共59页第三十七页，共59页。其

15、他费用:450元/千吨(qin dn) 应如何(rh)分配水库供水量，公司才能获利最多？ 若水库供水量都提高一倍，公司利润(lrn)可增加到多少？ 元/千吨甲乙丙丁A160130220170B140130190150C190200230/引水管理费收入：900元/千吨 支出A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40水库供水量(千吨)小区基本用水量(千吨)小区额外用水量(千吨)（以天计）第38页/共59页第三十八页，共59页。总供水量：160确定(qudng)送水方案使利润最大问题(wnt)分析A：50B：60C：50甲：30；50乙：70；70丙：10；2

16、0丁：10；40 总需求量(300)每个水库(shuk)最大供水量都提高一倍利润 = 收入(900) 其它费用(fi yong)(450) 引水管理费利润(元/千吨)甲乙丙丁A290320230280B310320260300C260250220/3332312423222114131211220250260300260320310280230320290 xxxxxxxxxxxZMax供应限制B, C 类似处理50:A14131211xxxx10014131211xxxx问题讨论 确定送水方案使利润最大需求约束可以不变第42页/共59页第四十二页，共59页。求解(qi ji) OBJECTI

17、VE FUNCTION 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.000000 0.000000 X31 50.000000 0.000000 X32 0.000000 20.000000 X33 30.0000

18、00 0.000000 这类问题一般称为(chn wi)“运输问题”(Transportation Problem)总利润(lrn) 88700（元） A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030第43页/共59页第四十三页，共59页。例2 加工奶制品的生产(shngchn)计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶(ni ni) 时间(shjin)480小时 至多加工100公斤A1 制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？若买，每天

19、最多买多少? 可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到 30元/公斤，应否改变生产计划？ 每天：第44页/共59页第四十四页，共59页。1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶(ni ni)生产A1 x2桶牛奶(ni ni)生产A2 获利(hu l) 243x1 获利 164 x2 原料供应 5021 xx劳动时间 48081221 xx加工能力 10031x决策变量 目标函数 216472xxzMax每天获利约束条件非负约束 0,21xx线性规划模型(LP)时间480小时 至多加工100公斤A1 50桶牛奶 每

20、天第45页/共59页第四十五页，共59页。模型分析(fnx)与假设 比例(bl)性 可加性 连续性 xi对目标函数(hnsh)的“贡献”与xi取值成正比 xi对约束条件的“贡献”与xi取值成正比 xi对目标函数的“贡献”与xj取值无关 xi对约束条件的“贡献”与xj取值无关 xi取值连续 A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数 线性规划模型第46页/共59页第四十六页，共59页。模型(mxng)求解

21、图解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx约束条件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMax目标(mbio)函数 Z=0Z=2400Z=3600z=c (常数(chngsh) 等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形 目标函数的等值线为直线 最优解一定在凸多边形的某个顶点取得。 第47页/共59页第四十七页，共59页。模型(mxng)求解 软件(run jin)实现 LINDO 6.1 max 72x

22、1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE 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 NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? N

23、o20桶牛奶(ni ni)生产A1, 30桶生产A2，利润3360元。 第48页/共59页第四十八页，共59页。结果(ji gu)解释 OBJECTIVE 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 NO. ITERATIONS= 2原料(yunli

24、o)无剩余时间(shjin)无剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三种资源“资源” 剩余为零的约束为紧约束（有效约束） 第49页/共59页第四十九页，共59页。结果(ji gu)解释 OBJECTIVE 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

25、.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2最优解下“资源(zyun)”增加1单位时“效益”的增量 原料增加1单位(dnwi), 利润增长48 时间增加1单位, 利润增长2 加工能力增长不影响利润影子价格 35元可买到1桶牛奶，要买吗？35 48, 应该买！ 聘用临时工人付出的工资最多每小时几元？ 2元！第50页/共59页第五十页，共59页。RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLO

26、WABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 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 40.000000最优解不变时目标函数系数允许(ynx)变化范围 DO RANGE(SEN

27、SITIVITY) ANALYSIS? Yesx1系数(xsh)范围(64,96) x2系数(xsh)范围(48,72) A1获利增加到 30元/千克，应否改变生产计划 x1系数由24 3=72增加为303=90，在允许范围内 不变！(约束条件不变)第51页/共59页第五十一页，共59页。结果(ji gu)解释 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.0000

28、00 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE R H S I N C R E A S E DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000影子价格有意义时约束(yush)右端的允许变化范围 原料(yunlio)最多增加10 时间最多增加53 35元可买到1桶牛奶，每天最多买多少？最多买10

29、桶!(目标函数不变)第52页/共59页第五十二页，共59页。例3 奶制品的生产(shngchn)销售计划 在例2基础(jch)上深加工1桶牛奶 3千克A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 0.8千克B12小时,3元1千克获利44元/千克 0.75千克B22小时,3元1千克获利32元/千克 制订生产(shngchn)计划，使每天净利润最大 30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？50桶牛奶, 480小时 至多100公斤A1 B1，B2的获利经常有10%的波动，对计划有无影响？第53页/共59页第五十三页，共59页。1桶

30、牛奶 3千克 A1 12小时 8小时 4千克 A2 或获利24元/千克 获利16元/kg 0.8千克 B12小时,3元1千克获利44元/千克 0.75千克 B22小时,3元1千克获利32元/千克 出售(chshu)x1 千克 A1, x2 千克 A2， X3千克(qink) B1, x4千克(qink) B2原料(yunlio)供应 劳动时间 加工能力 决策变量 目标函数 利润约束条件非负约束 0,61xx x5千克 A1加工B1， x6千克 A2加工B26543213332441624xxxxxxzMax50436251xxxx48022)(2)(4656251xxxxxx10051 xx附

31、加约束 5380 x.x64750 x.x 第54页/共59页第五十四页，共59页。模型(mxng)求解 软件(run jin)实现 LINDO 6.1 5043)26251xxxx48022)(2)(4)3656251xxxxxx OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.0000

32、00 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2600334) 26521xxxx44804624) 36521xxxxDO RANGE (SENSITIVITY) ANALYSIS? No第55页/共59页第五十五页，共59页。 OBJECTIVE FUNCTION VALUE 1) 3460.800 VA

33、RIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2结果(ji gu)解释每天销售168 千克(qink)A2和19.2 千克(qink)B1， 利润3460.8（元）8桶牛奶加工(ji gng)成A1，42桶牛奶加工(ji gng)成A2，将得到的24千