线性规划课用学习教案

1、会计学1线性规划线性规划(xin xn u hu)课用课用第一页，共109页。返回(fnhu)第2页/共109页第二页，共109页。单位产品所需原料数量（公斤）产品Q1产品Q2产品Q3 原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000单位产品的利润（千元）354问问题题第3页/共109页第三页，共109页。可控因素：每天生产三种产品的数量，分别设为321,xxx 目标：每天的生产利润最大 利润函数321453xxx 受制条件： 每天原料的需求量不超过可用量： 原料1P：15003221 xx 原料2P：8004232 xx 原料3P：2000523321x

2、xx 蕴含约束：产量为非负数 0,321xxx 第4页/共109页第四页，共109页。321453maxxxx 15003221 xx s.t. 8004232 xx 2000523321xxx 0,321xxx 第5页/共109页第五页，共109页。 O BJECTIV E FU N CTIO N V A LU E 2675.000 V A RIA BLE V A LU E RED U CED CO ST X 1 375.000000 0.000000 X 2 250.000000 0.000000 X 3 75.000000 0.000000 RO W SLA CK O R SU RPLU

3、 S D U A L PRICES 1) 0.000000 1.050000 2) 0.000000 0.625000 3) 0.000000 0.300000 返回(fnhu)第6页/共109页第六页，共109页。一个制造厂要把若干单位的产品从两个仓库2 , 1; iAi发送到零售点4 , 3 , 2 , 1;jBj， 仓库iA能供应的产品数量为2 , 1; iai，零售点jB所需的产品的数量为4 , 3 , 2 , 1;jbj。假设供给总量和需求总量相等，且已知从仓库iA运一个单位产品往jB的运价为ijc。问应如何组织运输才能使总运费最小？ 第7页/共109页第七页，共109页。可控因素：

4、 从仓库iA运往jB的产品数量,设为4 , 3 , 2 , 1, 2 , 1;jixij 目标：总运费最小 费用函数 2141ijijijxc 受控条件： 从仓库运出总量不超过可用总量，运入零售点的数量不低于需求量。由于总供给量等于总需求量，所以都是等号。即 2 , 1;4321iaxxxxiiiii 4 , 3 , 2 , 1;21jbxxjjj 蕴含约束：数量非负4 , 3 , 2 , 1, 2 , 1; 0jixij 第8页/共109页第八页，共109页。min 2141ijijijxc 2 , 1;4321iaxxxxiiiii s.t. 4 , 3 , 2 , 1;21jbxxjjj

5、 4 , 3 , 2 , 1, 2 , 1; 0jixij 返回(fnhu)第9页/共109页第九页，共109页。mqqjxqjxmpibxaxaxapibxaxaxat sxcxcxczjjininiiininiinn,.,2, 1;,.,2 , 1; 0,.,1;,.,2 , 1;. .min221122112211无限制 约束条件目标函数第10页/共109页第十页，共109页。返回(fnhu)njxj,.,2 , 1;为待定的决策变量， ),(21ncccc为 价 值 向 量 ，njcj,.,2 , 1;为价值系数， ),.,(21mbbbb 为右端向量， 矩阵 mnmmnnaaaaaa

6、aaaA212222111211 为系数矩阵。 第11页/共109页第十一页，共109页。可行解（或可行点） ：满足所有约束条件的向量),(21nxxxx 可行集（或可行域） ：所有的可行解的全体 0,xbAxxD 最优解：在可行域中目标函数值最大（或最小）的可行解，最优解的全体称为最优解集合 DyycxcDxO, 最优值：最优解的目标函数值 Oxxcv, 第12页/共109页第十二页，共109页。令自由变量jjjxxx，其中jjxx ,为非负变量 求最大可以等价成求负的最小 xcxc minmax 返回(fnhu)第13页/共109页第十三页，共109页。ininiibxaxaxa2211

7、ininiibxaxaxa2211 ininiibxaxaxa2211 返回(fnhu)第14页/共109页第十四页，共109页。ininiibxaxaxa2211 0,2211iiininiisbsxaxaxa 或 ininiibxaxaxa2211 0,2211iiininiisbsxaxaxa 返回(fnhu)松弛(sn ch)变量第15页/共109页第十五页，共109页。ininiibxaxaxa2211 ininiibxaxaxa2211 或 ininiibxaxaxa2211 ininiibxaxaxa2211 返回(fnhu)第16页/共109页第十六页，共109页。0. .mi

8、nxbAxtsxc 返回(fnhu)第17页/共109页第十七页，共109页。0. .minxbAxtsxc 返回(fnhu)第18页/共109页第十八页，共109页。052222. .21max1212121xxxxxxxtsxxz 7 , 6 , 5 , 4 , 3 , 1; 05)(2)(22)(2. .)(min743164315431431ixxxxxxxxxxxxxtsxxxzi 返回(fnhu)第19页/共109页第十九页，共109页。返回(fnhu)第20页/共109页第二十页，共109页。对于只有两个变量的线性规划问题可以用图解法求解： 变量用直角坐标系中的点表示 约束条件用

9、坐标系中的半空间或直线的交表示，可行 区域是一个凸多面体 目标函数用一组等值线表示，沿着增加或减少的方向 移动，与可行域最后的交点就是最优解。 第21页/共109页第二十一页，共109页。解线性规划 052222. .max121212121xxxxxxxtsxxz 2221 xx 2221 xx 521 xx 最优解（1，4） 第22页/共109页第二十二页，共109页。当目标函数改变后，等直线的方向会发生改变， 如果等值线与某个约束对应的函数直线平行， 则该函数值线上的所有可行解都是最优解 2221 xx 2221 xx 521 xx 最优解（1，4） 第23页/共109页第二十三页，共1

10、09页。返回(fnhu)第24页/共109页第二十四页，共109页。返回(fnhu)第25页/共109页第二十五页，共109页。考虑线性规划的标准形式 0. .minxbAxtsxc 其中nmmnRARbRcx,，并且假定可行域0,xbAxRxDn不空， 系数矩阵A是行满秩的，mAr)(，否则的话可以去掉多余约束。 返回(fnhu)第26页/共109页第二十六页，共109页。凸集及其性质：凸集及其性质： 定义定义 2.2.1：设nRS 是n维欧氏空间的点集，若对任意SySx ,的和任意 1 , 0都有 Syx)1 ( 就称S是一个凸集。 定理定理 2.2.1 线性规划的可行域 0,xbAxxD

11、是凸集 定理定理 2.2.2 任意多个凸集的交还是凸集 返回(fnhu)第27页/共109页第二十七页，共109页。超平面 bxaRxHn 半空间 bxaRxHn； bxaRxHn 多面凸集 ,.,2, 1;,.,2 , 1;qpppibxapibxaRxSiiiin 定义定义 2.2.2：设S为凸集Sx，如果对任意Szy,和 10，都有 zyx)1 (, 则称x为S的顶点. 第28页/共109页第二十八页，共109页。1可行域顶点的个数是否有限？ 2最优解是否一定在可行域顶点上达到？ 3如何找到顶点？ 4 如何从一个顶点转移到另一个顶点 返回(fnhu)第29页/共109页第二十九页，共10

12、9页。返回(fnhu)第30页/共109页第三十页，共109页。令),(NBA ， x=(Bx,Nx)。 bAx 分块 bNxBxNB 左乘1B bBNxBxNB11 NBNxBbBx11 Nx=0 01bBx 第31页/共109页第三十一页，共109页。定义定义2.2.3：设B是秩为m的约束矩阵A的一个m阶满秩子方阵， 则称B为一个基；B中m个线性无关的列向量称为基向量， 变量x中与之对应的m个分量称为基变量， 其余的变量为非基变量，令所有的非基变量取值为 0，得到的解01bBx称为相应于B的基本解。当01bB则称基本解为基本可行解， 这时对应的基阵B为可行基。 如果01bB则称该基可行解为

13、非退化的， 如果一个线性规划的所有基可行解都是非退化的则称该规划为非退化的。 返回(fnhu)第32页/共109页第三十二页，共109页。例例 考虑问题： 5 , 4 , 3 , 2 , 1; 052222. .min52142132121jxxxxxxxxxxtsxxzj 系数矩阵 100110102100112A 基阵为 1000100011B 1010110022B 对应的基解分别为)5 , 2 , 2 , 0 , 0(1x和)6 , 3 , 0 , 0 , 1(2x，其中1x为基本可行解，2x不是基本可行解。 返回(fnhu)第33页/共109页第三十三页，共109页。定理定理2.2.

14、3 可行解x是基本可行解的充要条件是它的正分量所对应的矩阵A中列向量线性无关。 定理定理2.2.4 x是基本可行解的充要条件是x是可行域D的顶点。 定理定理 2.2.5 一个标准的 LP 问题如果有可行解，则至少有一个基本可行解 定理定理 2.2.6 一个标准的 LP 问题如果有有限的最优值， 则一定存在一个基本可行解是最优解。 返回(fnhu)第34页/共109页第三十四页，共109页。1不一定所有的基本可行解都是最优解，最优解也不一定都是基本解 2如果有两个基本可行解是最优解，则两解的凸组合也都是最优解。 3如果最优解不唯一，则会有多个基本可行解是最优解，它们必然在同一个面上。 4基可行解

15、个数有限，可以在基可行解中寻找最优解。剩余的问题是如何判断一个基可行解是最优解，如果不是则如何从一个基可行解转到另一个基可行解。 返回(fnhu)第35页/共109页第三十五页，共109页。返回(fnhu)第36页/共109页第三十六页，共109页。例 2.3.1 求解问题 5,.,2 , 1; 021322. .2min53243232132jxxxxxxxxxxtsxxzj 第37页/共109页第三十七页，共109页。以1x、4x和5x为基变量就可以得到初始基可行解)2 , 1 , 0 , 0 , 2(，其对应的单纯形表为 1x 2x 3x 4x 5x 1 -2 1 -2 1 1 -3 1

16、 1 -1 1 2 1 2 第38页/共109页第三十八页，共109页。由于012，所以该基可行解不是最优解，同时系数矩阵该列有大于 0 的元素，所以取2x为入基变量。计算1,min1211，所以取第二个约束对应的基变量4x为出基变量， 就可以得到一个新的基可行解， 在上表中把2x对应的列变成单位向量，系数矩阵第 2 行对应的元素为 1，则可以得到该基可行解的单纯形表 1x 2x 3x 4x 5x 0 1 -1 -1 1 0 -5 2 1 -3 1 0 2 -1 1 4 1 1 第39页/共109页第三十九页，共109页。由于013， 所以该基可行解不是最优解， 同时系数矩阵该列有大于 0 的

17、元素， 所以取3x为入基变量。计算21，所以取第 3 个约束对应的基变量5x为出基变量，就可以得到一个新的基可行解，在上表中把3x对应的列变成单位向量，系数矩阵第 3 行对应的元素为 1，则可以得到该基可行解的单纯形表： 1x 2x 3x 4x 5x 0 0 -1/2 -1/2 -3/2 1 0 0 -1/2 5/2 1 0 -1/2 3/2 0 1 -1/2 1/2 13/2 5/2 1/2 第40页/共109页第四十页，共109页。由于检验数都小于等于 0，所以该基可行解就是最优解，对应的最优解为)0 , 0 , 2/1 , 2/5 , 2/13(，最优值为-3/2。 注注： 1该算法在实

18、际应用中非常有效，被广泛采用，但在理论上不是多项式时间算法。 2现在还有待解决的问题是如何给出初始基可行解以及出现退化的时候如何处理。 返回(fnhu)第41页/共109页第四十一页，共109页。定定理理 2.3.1（最优性准则）如果0，则基可行解x为原问题的最优解。 定定 理理2.3.2 如 果 向 量的 第k个 分 量0k，而向量01kAB，则原问题无界。 定定理理 2.3.3 对于非退化的基本可行解x，若 向 量的 第k个 分 量0k， 而 向 量.1kAB至少有一个正分量，则可以找到一个新的基本可行解x 使得xcxc。 返回(fnhu)第42页/共109页第四十二页，共109页。ste

19、p1 找一个初始可行基 step2 求出典式和检验数 step3 求,.,2 , 1maxnjjk step4 如果0k则该基可行解就是最优解停止； 否则转 step5； step5 如果01kAB，则问题无最优解，停止； 否则转 step6 step6 求rkrikikiabmiaab/,.,2 , 1, 0/min step7 以kA替代rA得到一个新的基，转 step2； 返回(fnhu)第43页/共109页第四十三页，共109页。第44页/共109页第四十四页，共109页。返回(fnhu)第45页/共109页第四十五页，共109页。 返回(fnhu)第46页/共109页第四十六页，共1

20、09页。第47页/共109页第四十七页，共109页。返回(fnhu)第48页/共109页第四十八页，共109页。返回(fnhu)第49页/共109页第四十九页，共109页。数学数学(shxu)(shxu)规规划模型划模型 实际实际(shj)问题中问题中的优化模型的优化模型mixgtsxxxxfzMaxMiniTn, 2 , 1, 0)(. .),(),()(1或x决策决策(juc)变量变量f(x)目标函数目标函数gi(x) 0约束条件约束条件多元函数多元函数条件极值条件极值 决策变量个数决策变量个数n和和约束条件个数约束条件个数m较大较大 最优解在可行域最优解在可行域的边界上取得的边界上取得

21、数数学学规规划划线性规划线性规划非线性规划非线性规划整数规划整数规划重点在模型的建立和结果的分析重点在模型的建立和结果的分析第50页/共109页第五十页，共109页。企业生产企业生产(shngchn)计计划划应用应用(yngyng)1： 奶制品的生奶制品的生产与销售产与销售 空间空间(kngjin)层次层次工厂级：根据外部需求和内部设备、人力、原料等条件，工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费用参车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生

22、产批量计划。数等，以最小成本为目标制订生产批量计划。时间层次时间层次若短时间内外部需求和内部资源等不随时间变化，可若短时间内外部需求和内部资源等不随时间变化，可制订制订单阶段生产计划单阶段生产计划，否则应制订多阶段生产计，否则应制订多阶段生产计划。划。本节课题本节课题第51页/共109页第五十一页，共109页。例例1 加工加工(ji gng)奶制品的奶制品的生产计划生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶(ni ni) 时间时间(shjin)480小小时时 至多加工至多加工100公斤公斤A1 制订生产计划，使每天获利最大

23、制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶桶牛奶,买吗？若买买吗？若买,每天最多买多少每天最多买多少? 可聘用临时工人可聘用临时工人,付出的工资最多是每小时几元付出的工资最多是每小时几元? A1的获利增加到的获利增加到 30元元/公斤公斤,应否改变生产计划？应否改变生产计划？ 每天：每天：第52页/共109页第五十二页，共109页。1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶桶牛奶(ni ni)生产生产A1 x2桶牛奶桶牛奶(ni ni)生产生产A2 获利获利(hu l) 243x1 获利获利 164 x2 原料供应原料供

24、应 5021 xx劳动时间劳动时间 48081221 xx加工能力加工能力 10031x决策变量决策变量 目标函数目标函数 216472xxzMax每天获利每天获利约束条件约束条件非负约束非负约束 0,21xx线线性性规规划划模模型型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每每天天第53页/共109页第五十三页，共109页。模型分析模型分析(fnx)(fnx)与假设与假设 比比例例(bl)性性 可可加加性性 连续性连续性 xi对目标函数对目标函数(hnsh)的的“贡献贡献”与与xi取值成正比取值成正比 xi对约束条件的对约束条件的“贡献贡献”与与x

25、i取值取值成正比成正比 xi对目标函数的对目标函数的“贡贡献献”与与xj取值无关取值无关 xi对约束条件的对约束条件的“贡贡献献”与与xj取值无关取值无关 xi取值连续取值连续 A1,A2每公斤的获利是与各自产每公斤的获利是与各自产量无关的常数量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和的数量和时间是与各自产量无关的常数时间是与各自产量无关的常数A1,A2每公斤的获利是与相互每公斤的获利是与相互产量无关的常数产量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和的数量和时间是与相互产量无关的常数时间是与相互产量无关的常数加工加工A1,A2的牛奶桶数是实数的牛奶桶数是实数 线

26、性规划模型线性规划模型第54页/共109页第五十四页，共109页。模型模型(mxng)(mxng)求求解解 图解法图解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx约约束束条条件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMax目标目标(mb(mbio)io)函数函数 Z=0Z=2400Z=3600z=c (常数常数(chngsh) 等值等值线线c在在B(20,30)点得到最优解点得到最优解目标函数和约束条件是线性函数目标函数和约束条件是线性函数 可行域为直线段围成的凸

27、多边形可行域为直线段围成的凸多边形 目标函数的等值线为直线目标函数的等值线为直线 最优解一定在凸多最优解一定在凸多边形的某个顶点取边形的某个顶点取得。得。 第55页/共109页第五十五页，共109页。模型模型(mxng)(mxng)求解求解 软件软件(run (run jin)jin)实现实现 LINDO 6.1 max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.

28、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? No20桶牛奶桶牛奶(ni ni)生产生产A1, 30桶生产桶生产A2，利润，利润3360元。元。 第56页/共109页第五十六页，共109页。max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end结果结果(ji (ji gu)

29、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原料原料(yunlio)无无剩余剩余时间时间(shjin)无剩余无剩余加工能力剩余加工能力剩余40三三种种资资源源“资源资源” 剩余为零

30、的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束） 第57页/共109页第五十七页，共109页。结果结果(ji (ji gu)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

31、最优解下最优解下“资源资源”增加增加1单位单位(dnwi)时时“效益效益”的增量的增量 原料原料(yunlio)增加增加1单位单位,利润增长利润增长48 时间增加时间增加1单位单位,利润增长利润增长2 加工能力增长不影响利润加工能力增长不影响利润影子价格影子价格 35元可买到元可买到1桶牛奶桶牛奶,要买吗？要买吗？35 48, 应该买！应该买！ 聘用临时工人付出的工资最多每小时几元？聘用临时工人付出的工资最多每小时几元？ 2元！元！第58页/共109页第五十八页，共109页。RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANG

32、ES VARIABLE CURRENT ALLOWABLE ALLOWABLE 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最优

33、解不变时目标函数最优解不变时目标函数(hnsh)系数允许变化范系数允许变化范围围 DO RANGE(SENSITIVITY) ANALYSIS? Yesx1系数系数(xsh)范围范围(64,96) x2系数系数(xsh)范围范围(48,72) A1获利增加到获利增加到 30元元/千克千克,应否改变生产计划应否改变生产计划 x1系数由系数由24 3=72增增加加为为30 3=90，在，在允允许范围内许范围内 不变！不变！(约束条件不变约束条件不变)第59页/共109页第五十九页，共109页。结果结果(ji (ji gu)gu)解解释释 RANGES IN WHICH THE BASIS IS U

34、NCHANGED: 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 ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 1

35、00.000000 INFINITY 40.000000影子价格有意义影子价格有意义(yy)时约束右端的允许变化范时约束右端的允许变化范围围 原料原料(yunlio)最多增加最多增加10 时间最多时间最多增加增加53 35元可买到元可买到1桶牛奶桶牛奶,每天最多买多少？每天最多买多少？最多买最多买10桶桶!(最优基不变最优基不变)第60页/共109页第六十页，共109页。例例2 奶制品的生产销售奶制品的生产销售(xioshu)计划计划 在例在例1基础基础(jch)上深上深加工加工1桶桶牛奶牛奶 3千克千克A1 12小时小时 8小时小时 4公斤公斤A2 或或获利获利24元元/公公斤斤 获利获利1

36、6元元/公斤公斤 0.8千克千克B12小时小时,3元元1千千克克获利获利44元元/千千克克 0.75千克千克B22小时小时,3元元1千千克克获利获利32元元/千千克克 制订生产制订生产(shngchn)(shngchn)计划计划, ,使每天使每天净利润最大净利润最大 30元可增加元可增加1桶牛奶桶牛奶,3元可增加元可增加1小时时间小时时间,应否投资？现投应否投资？现投资资150元元,可赚回多少？可赚回多少？50桶牛奶桶牛奶, 480小时小时 至多至多100公斤公斤A1 B1,B2的获利经常有的获利经常有10%的波动的波动,对计划有无影响？对计划有无影响？第61页/共109页第六十一页，共109

37、页。1桶桶牛奶牛奶 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千克千克

38、 A1加工加工B1， x6千克千克 A2加工加工B26543213332441624xxxxxxzMax50436251xxxx48022)(2)(4656251xxxxxx10051 xx附加约束附加约束 5380 x.x64750 x.x 第62页/共109页第六十二页，共109页。模型模型(mxng)(mxng)求求解解 软件软件(run (run jin)jin)实实现现 LINDO 6.1 5043)26251xxxx48022)(2)(4)3656251xxxxxx OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCE

39、D 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= 2600334

40、) 26521xxxx44804624) 36521xxxxDO RANGE (SENSITIVITY) ANALYSIS? No第63页/共109页第六十三页，共109页。 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.000000 1.520000ROW SLACK OR SURPL

41、US 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 (ji gu)gu)解释解释每天销售每天销售168 千克千克(qink)A2和和19.2 千千克克(qink)B1， 利润利润3460.8（元）（元）8桶牛奶加工桶牛奶加工(ji gng)成成A1，42桶牛奶加工桶牛奶加工(ji gng)成成A2，将得到的将得到的24千克千克A1全部全部加工加工(ji

42、gng)成成B1 除加工能力外除加工能力外均为紧约束均为紧约束第64页/共109页第六十四页，共109页。结果结果(ji (ji gu)gu)解解释释 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.000000 1.520000ROW SLACK OR SURPLUS DUAL PRIC

43、ES 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增加增加(zngji)1桶牛奶桶牛奶使利润增长使利润增长3.1612=37.925043)26251xxxx600334) 26521xxxx4增加增加(zngji)1小小时时间使利润增时时间使利润增长长3.26 30元可增加元可增加1桶牛奶桶牛奶,3元可增加元可增加1小时时间小时时间,应否投应否投资？现投资资？现投资150元元,可赚回多少？可赚回多少？投资投资150元增加元增

44、加5桶牛奶，可桶牛奶，可赚回赚回189.6元。（大于增加元。（大于增加时间的利润增长）时间的利润增长）第65页/共109页第六十五页，共109页。结果结果(ji (ji gu)gu)解释解释B1,B2的获利有的获利有10%的波动的波动(bdng)，对计划有无影响，对计划有无影响 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 24.000000 1.680000 INFINITY X2 16.

45、000000 8.150000 2.100000 X3 44.000000 19.750002 3.166667 X4 32.000000 2.026667 INFINITY X5 -3.000000 15.800000 2.533334 X6 -3.000000 1.520000 INFINITY DO RANGE (SENSITIVITY) ANALYSIS? YesB1获利下降获利下降10%，超，超出出X3 系数允许系数允许(ynx)范围范围B2获利上升获利上升10%，超出，超出X4 系数允许范围系数允许范围波动对计划有影响波动对计划有影响生产计划应重新制订：如将生产计划应重新制订：如将

46、x3的系数改为的系数改为39.6计算，计算，会发现结果有很大变化。会发现结果有很大变化。 第66页/共109页第六十六页，共109页。应用应用2：自来水输送：自来水输送(sh sn)与货机与货机装运装运生产、生活物资从若干供应点运送到一些需求生产、生活物资从若干供应点运送到一些需求(xqi)点点,怎样安排输送方案使运费最小怎样安排输送方案使运费最小,或利润最或利润最大；大；运输运输(ynsh)问问题题各种类型的货物装箱各种类型的货物装箱,由于受体积、重量等限制由于受体积、重量等限制,如如何搭配装载何搭配装载,使获利最高使获利最高,或装箱数量最少。或装箱数量最少。第67页/共109页第六十七页，

47、共109页。其他费用其他费用:450:450元元/ /千吨千吨(qin dn) (qin dn) 应如何分配水库供水量应如何分配水库供水量, ,公司才能公司才能(cinng)(cinng)获利最多？获利最多？ 若水库供水量都提高一倍若水库供水量都提高一倍, ,公司公司(n s)(n s)利润可增加到多少？利润可增加到多少？ 元元/千吨千吨甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理费引水管理费收入：收入：900元元/千吨千吨 支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40水库供水量水

48、库供水量(千吨千吨)小区基本用水量小区基本用水量(千吨千吨)小区额外用水量小区额外用水量(千吨千吨)（以天计）（以天计）第68页/共109页第六十八页，共109页。总供水量：总供水量：160确定送水方案确定送水方案(fng n)使利使利润最大润最大问题问题(wnt)分分析析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40 总需求量总需求量(300)每个水库每个水库(shuk)(shuk)最大供水量都提最大供水量都提高一倍高一倍利润利润(lrn) = 收入收入(900) 其它费用其它费用(450) 引水管理引水管理费费利润利润(元元/千吨千吨)甲甲

49、乙乙丙丙丁丁A290320230280B310320260300C260250220/3332312423222114131211220250260300260320310280230320290 xxxxxxxxxxxZMax供应供应限制限制B, C 类似处理类似处理50:A14131211xxxx10014131211xxxx问题讨论问题讨论 确定送水方案确定送水方案使利润最大使利润最大需求约束可以不变需求约束可以不变第72页/共109页第七十二页，共109页。求解求解(qi (qi ji)ji) OBJECTIVE FUNCTION VALUE 1) 88700.00 VARIABLE

50、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.000000 0.000000 这类问题这类问题(wnt)一一般称为般称为“运输问题运

51、输问题(wnt)”(Transportation Problem)总利润总利润(lrn) 88700(lrn) 88700（元）（元） A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030第73页/共109页第七十三页，共109页。如何如何(rh)装装运，使本次运，使本次飞行获利最飞行获利最大？大？ 三个货舱最大载重三个货舱最大载重(zizhng)(吨吨),最大容积最大容积(米米3) 重量（吨重量（吨）空间空间( 米米3/吨）吨）利润（元利润（元/吨）吨）货物货物1184803100货物货物2156503800货

52、物货物3235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成比例重成比例 前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8；5300飞机平衡飞机平衡第74页/共109页第七十四页，共109页。决策决策(ju(jucc)变量变量 xij-第第i 种货物装入第种货物装入第j 个货舱个货舱(hucng)的重量的重量(吨）吨）i=1,2,3,4, j=1,2,3 (分别代表前、中、后仓分别代表前、中、后仓)模型模型(mxng)(mxng)假设假设 每种货物可以分割到任意小；每种货物可以分割到任意小；货机装运货机装运每种货物

53、可以在一个或多个货舱中任意分布；每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；多种货物可以混装，并保证不留空隙； 模型建立模型建立 第75页/共109页第七十五页，共109页。货舱货舱(hucng)容积容积 目标函目标函数数(hns(hnsh)h)( (利润利润) )约束约束条件条件 )(2850)(3500)(3800)(3100434241333231232221131211xxxxxxxxxxxxZMax680039058065048041312111xxxx870039058065048042322212xxxx53003905806504804333231

54、3xxxx货机货机(hu (hu j)j)装运装运模型建立模型建立 货货舱舱重重量量 1041312111xxxx1642322212xxxx843332313xxxx10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量第76页/共109页第七十六页，共109页。约束约束条件条件平衡平衡(pnghng)要求要求 81610433323134232221241312111xxxxxxxxxxxx货物货物(huw)供应供应 18131211xxx15232221xxx23333231xxx12434241xxx货机货机(hu (hu j)j

55、)装运装运模型建立模型建立 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量第77页/共109页第七十七页，共109页。 OBJECTIVE FUNCTION VALUE 1) 121515.8 VARIABLE VALUE REDUCED COST X11 0.000000 400.000000 X12 0.000000 57.894737 X13 0.000000 400.000000 X21 10.000000 0.000000 X22 0.000000 239.473679 X23 5.000000 0.000000 X31

56、 0.000000 0.000000 X32 12.947369 0.000000 X33 3.000000 0.000000 X41 0.000000 650.000000 X42 3.052632 0.000000 X43 0.000000 650.000000 货物货物(huw)2:(huw)2:前仓前仓10,10,后仓后仓5 5； 货物货物(huw)3:(huw)3:中仓中仓13, 13, 后仓后仓3 3；货物；货物(huw)4:(huw)4:中仓中仓3 3。货机货机(hu (hu j)j)装运装运模型模型(mxn(mxng)g)求解求解 最大利润约最大利润约121516元元货物货物供

57、应点供应点货舱货舱需求点需求点平衡要求平衡要求运输运输问题问题运输问题的扩展运输问题的扩展第78页/共109页第七十八页，共109页。 如果生产如果生产(shngchn)(shngchn)某一类型汽车某一类型汽车, ,则至少则至少要生产要生产(shngchn)80(shngchn)80辆辆, , 那么最优的生产那么最优的生产(shngchn)(shngchn)计划应作何改变？计划应作何改变？汽车厂生产三种类型的汽车汽车厂生产三种类型的汽车,已知各类型每辆车对钢已知各类型每辆车对钢材、劳动时间的需求材、劳动时间的需求,利润利润(lrn)及工厂每月的现有及工厂每月的现有量。量。 小型小型 中型中型

58、 大型大型 现有量现有量钢材（吨）钢材（吨） 1.5 3 5 600劳动时间（小时）劳动时间（小时） 280 250 400 60000利润（万元）利润（万元） 2 3 4 制订月生产计划制订月生产计划,使工厂的利润最大。使工厂的利润最大。应用应用3：汽车生产与原油采购：汽车生产与原油采购第79页/共109页第七十九页，共109页。设每月生产小、中、设每月生产小、中、大型大型(dxng)(dxng)汽车的汽车的数量分别为数量分别为x1, x2, x1, x2, x3x3321432xxxzMax600535 . 1.321xxxts60000400250280321xxx0,321xxx汽车厂

59、生产汽车厂生产(shngchn)(shngchn)计计划划 模型模型(mxn(mxng)g)建立建立 小型小型 中型中型 大型大型 现有现有量量钢材钢材 1.5 3 5 600时间时间 280 250 400 60000利润利润 2 3 4 线线性性规规划划模模型型(LP)第80页/共109页第八十页，共109页。模型模型(m(mxnxng)g)求求解解 3） 模型中增加条件模型中增加条件:x1, x2, x3 均为整数均为整数(zhngsh),重新求解。重新求解。 OBJECTIVE FUNCTION VALUE 1) 632.2581VARIABLE VALUE REDUCED COST

60、X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.731183 3) 0.000000 0.003226结果结果(ji gu)为小数为小数,怎么怎么办？办？1）舍去小数）舍去小数:取取x1=64,x2=167,算出目标函数值算出目标函数值z=629,与与LP最优值最优值632.2581相差不大。相差不大。2）试探）试探:如取如取x1=65,x2=167;x1=64,x2=168等等,计算函数值计算函数值z,通通过比较可能