第二章线性规划学习教案

1、会计学1第二章线性规划第二章线性规划(xin xn u hu)第一页，共55页。11max12012njjjnijjijjzc xa xbimxjn， ， ， ， ，第1页/共55页第二页，共55页。第2页/共55页第三页，共55页。线性规划模型线性规划模型化为标准形式化为标准形式变量变量Xj0不变不变Xj0令令 Xj * = - Xj ,则则Xj * 0Xj无约束无约束令令 Xj * -Xj * = Xj ,则则Xj *, Xj * 0约约束束条条件件右端右端项项bi0不变不变bi0约束式两端同乘以约束式两端同乘以”-1”形式形式ai1x1+ainxn =bi不变不变ai1x1+ainxn

2、biai1x1+ainxn+xsi =biai1x1+ainxn biai1x1+ainxn-xri =bi目标函数目标函数max z= c1x1+cnxn 不变不变min z= c1x1+cnxn 令令z*= -z, 化为求化为求 max z*=- c1x1-cnxn 第3页/共55页第四页，共55页。第4页/共55页第五页，共55页。1 1 可行可行(kxng)(kxng)解与最解与最优解：优解：最优解一定(ydng)是可行解，但可行解不一定(ydng)是最优解。基解不一定(ydng)是可行解，可行解也不一定(ydng)是基解。2 2 可行解与基解：可行解与基解：3 3 可行解与基可行解可

3、行解与基可行解：基可行解一定是可行解，但可行解不一定是基可能解。基可行解一定是基解，但基解不一定是基可行解。4 4 基本解与基可行解基本解与基可行解：非可行解可行解基可行解基本解线性规划问题解的概念线性规划问题解的概念第5页/共55页第六页，共55页。6 6 问题问题(wnt)(wnt)：最优解与基可行：最优解与基可行解？解？最优解不一定(ydng)是基可行解，基可行解也不一定(ydng)是最优解。5 5 最优解与基本最优解与基本(jbn)(jbn)解：解：最优解不一定是基解，基解也不一定是最优解。为什么？非可行解可行解基可行解基本解考虑无穷多最优解的情况。线性规划问题解的概念线性规划问题解的

4、概念第6页/共55页第七页，共55页。定理定理1 1 线性规划的可行线性规划的可行(kxng)(kxng)域域 R R 是一个凸集，且有有限个顶点。是一个凸集，且有有限个顶点。定理定理3 3 若线性规划有最优解，则必存在一个若线性规划有最优解，则必存在一个(y (y )基可行解是最优解。基可行解是最优解。线性规划问题的可行域是一个凸集。线性规划的每一个基可行解对应可行域的一个顶点(基可行解与可行域顶点一一对应)。定理定理2 2 X是线性规划可行域 R 顶点的充要条件是 X是 线性规划的基本可行解。1 1对线性规划的回顾对线性规划的回顾若线性规划有最优解，则一定在凸集的某个（些）顶点上 达到最优

5、，即此时一定存在某个顶点是最优解。定理定理4 4 若线性规划在可行域的两个顶点上达到最优，则在两个顶点的连线上也达到最优。若线性规划在两个顶点以上达到最优,则一定有无穷多个最优解。最优解不一定是基可行解，基可行解也不一定是最优解。第7页/共55页第八页，共55页。1 1对线性规划对线性规划(xin xn u (xin xn u hu)hu)的回顾的回顾第8页/共55页第九页，共55页。c1 cmcm+1cncBxBbx1 xmxm+1xnc1x1b110a1,m+1 a1,nc2x2b200a2,m+1a2,n cmxmbm01am,m+1am,n00jc 1,11mmii micc a,1m

6、nii nicc a1 1对线性规划对线性规划(xin xn u (xin xn u hu)hu)的回顾的回顾j第9页/共55页第十页，共55页。1 1221111,111,221122,112,2222,11,2212max,0mmmmnnmmmmnnmmmmnnmm mmm mmmnnmnzc xc xc xcxc xxaxaxa xbxaxaxa xbxaxaxaxbx xx1 1对线性规划对线性规划(xin xn u (xin xn u hu)hu)的回顾的回顾第10页/共55页第十一页，共55页。max0jjk min0ilikiklkbbaaa1 1对线性规划对线性规划(xin x

7、n u (xin xn u hu)hu)的回顾的回顾5、以alk为主元素进行迭代(di di)，把xk所对应的列向量 将xB列中xl的换为xk，得到新的单纯形表，重复25，直至终止。120010kkklkmkaaPaa第11页/共55页第十二页，共55页。选择换出变量时，若按选择换出变量时，若按规则计算，有几个比值同时达规则计算，有几个比值同时达到最小，则选择下标最小的对应的基变量作为换出到最小，则选择下标最小的对应的基变量作为换出变量变量1 1对线性规划对线性规划(xin xn (xin xn u hu)u hu)的回顾的回顾第12页/共55页第十三页，共55页。第13页/共55页第十四页，

8、共55页。线性规划的对偶线性规划的对偶(du u)理论理论1 1对线性规划对线性规划(xin xn u (xin xn u hu)hu)的回顾的回顾原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量0000= =无约束无约束变变量量n个个n个个约约束束条条件件0000无约束无约束= =约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项第14页/共55页第十五页，共55页。1 1对线性规划对线性规划(xin

9、 xn u (xin xn u hu)hu)的回顾的回顾对偶对偶(du u)问题的性质问题的性质【性质1】对称性定理：对偶问题的对偶是原问题。【性质2】弱对偶原理（弱对偶性）：设X 和Y 分别是问题（P）和（D）的任一可行解，则必有 z(X) f(Y).【性质3】最优性判别定理：若 X* 和 Y* 分别是 P 和 D 的可行解且CX* = Y* b， 则X*, Y*分别是问题 P和D 的最优解。【性质4】 (强对偶性) 原规划与对偶规划同有最优解，且两者最优值相等。【性质5】互补松弛定理：设X、Y各为原规划与对偶规划的一个可行解，则X、Y为最优解的充分必要条件(b yo tio jin)为 Y

10、 XS = YS X = 0。【性质6】 (基解对应性) 原规划单纯形表中检验数行对应对偶规划的一个基解。 max zCXAXb X0P m in Y AC Y0DfY b推论.若X和Y分别是问题（P）和（D）的可行解，则 CX是（D）的目标函数最小值的一个下界；Yb是（P）的目标函数最大值的一个上界。推论.在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。推论.在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行，（如D），则该可行的问题无界。第15页/共55页第十六页，共55页。1 1对线性规划对线性规划

11、(xin xn (xin xn u hu)u hu)的回顾的回顾原规划（原规划（P P）对偶规划（对偶规划（D D）可行可行可行可行不可行不可行可行（无界）可行（无界）可行（无界）可行（无界）不可行不可行不可行不可行不可行不可行第16页/共55页第十七页，共55页。 对偶(du u)单纯形法1 1对线性规划对线性规划(xin xn u (xin xn u hu)hu)的回顾的回顾基本思想是：从原规划的一个基本解出发，此基本解不一定可行，基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以但它对应着一个对偶可行解（检验数非正），所以也可以说是从一

12、个对偶可行解出发；然后检验原规也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果划的基本解是否可行，即是否有负的分量，如果(rgu)有小于零的分量，则进行迭代，求另一个基有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数本解，此基本解对应着另一个对偶可行解（检验数非正）。如果非正）。如果(rgu)得到的基本解的分量皆非负则得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正代过程中始终保持对偶解的可行性（即检验数非正），使

13、原规划的基本解由不可行逐步变为可行，当），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。规划的最优解。对偶单纯形法求解线性规划问题过程：对偶单纯形法求解线性规划问题过程：第17页/共55页第十八页，共55页。0，故，故x2为入基变量；又因为入基变量；又因最小比值在第三行，故最小比值在第三行，故x5为出基变量。合之，知主为出基变量。合之，知主元为元为4。第21页/共55页第二十二页，共55页。23Cj3122000iCBXBbx1x2x3x4x531x120105/240-1/120 x420005/

14、121-13/622x23001-1/801/4- - z-128000-89/240-35/12以4为主元作旋转变换得下表：第22页/共55页第二十三页，共55页。24第23页/共55页第二十四页，共55页。25例1某昼夜(zhuy)服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?第24页/共55页第二十五页，共55页。第25页/共55页第二十六页，共55页。时间所需售货员人数星期日28星期一15星期二24星期三25星期四19星期五31星期六2

15、8第26页/共55页第二十七页，共55页。28第27页/共55页第二十八页，共55页。2.2 2.2 生产计划生产计划(jhu)(jhu)问题问题第28页/共55页第二十九页，共55页。2.2 2.2 生产计划生产计划(jhu)(jhu)问题问题第29页/共55页第三十页，共55页。2.2 2.2 生产生产(shngchn)(shngchn)计计划问题划问题第30页/共55页第三十一页，共55页。产品单件工时 设备 设备的 有效台时 满负荷时的设备费用 A1 5 10 6000 300 A2 7 9 12 10000 321 B1 6 8 4000 250 B2 4 11 7000 783 B

16、3 7 4000 200 原料（元/件） 0.25 0.35 0.50 售价（元/件） 1.25 2.00 2.80 2.2 2.2 生产计划生产计划(jhu)(jhu)问问题题第31页/共55页第三十二页，共55页。332.2 2.2 生产计划生产计划(jhu)(jhu)问题问题第32页/共55页第三十三页，共55页。2.2 2.2 生产计划生产计划(jhu)(jhu)问题问题目标函数为计算利润最大化，利润的计算公式为： 利润 = （销售单价(dnji) - 原料单价(dnji)）* 产品件数之和 -（每台时的设备费用*设备实际使用的总台时数）之和。这样得到目标函数： Max(1.25-0.

17、25)(x111+x112)+(2-0.35)x221+(2.80-0.5)x312 300/6000(5x111+10 x211)-321/10000(7x112+9x212+12x312)- 250/4000(6x121+8x221)-783/7000(4x122+11x322)-200/4000(7x123).经整理可得： Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123第33页/共55页第三十四页，共55页。 例5某工厂要用三种原料

18、1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据(shj)如右表。问：该厂应如何安排生产，使利润收入为最大？产品名称规格要求单价（元/kg）甲原材料1不少于50%，原材料2不超过25%50乙原材料1不少于25%，原材料2不超过50%35丙不限25原材料名称每天最多供应量单价（元/kg）11006521002536035 解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑： 对于(duy)甲： x11，x12，x13； 对于(duy)乙： x21，x22，x23； 对于(duy)丙： x31，x32，x33； 对于(duy)原料1： x11，

19、x21，x31； 对于(duy)原料2： x12，x22，x32； 对于(duy)原料3： x13，x23，x33； 目标函数： 利润最大，利润 = 收入 - 原料支出 约束条件： 规格要求 4 个； 供应量限制 3 个。第34页/共55页第三十五页，共55页。第35页/共55页第三十六页，共55页。第36页/共55页第三十七页，共55页。第37页/共55页第三十八页，共55页。标准汽油标准汽油辛烷数辛烷数蒸汽压力蒸汽压力(g/cm2)库存量库存量(L)1107.57.1110-2380000293.011.38 10-2265200387.05.6910-24081004108.028.45

20、 10-2130100例6.汽油混合问题。一种汽油的特性可用两种指标描述，用“辛烷数”来定量描述其点火特性，用“蒸汽压力”来定量描述其挥发性。某炼油厂有1、2、3、4种标准汽油，其特性和库存量列于表1中，将这四种标准汽油混合，可得到标号为1，2的两种飞机汽油，这两种汽油的性能指标及产量需求列于表2中。问应如何根据库存情况适量混合各种标准汽油，既满足(mnz)飞机汽油的性能指标，又使2号汽油满足(mnz)需求，并使得1号汽油产量最高？飞机汽油飞机汽油辛烷数辛烷数蒸汽压力蒸汽压力(g/cm2)产量需求产量需求1不小于不小于91不大于不大于9.96 10-2越多越好越多越好2不小于不小于100不大于

21、不大于9.96 10-2不少于不少于250000表表 1 1表表 2 2第38页/共55页第三十九页，共55页。解：设xij为飞机汽油i中所用(su yn)标准汽油j的数量(L)。 目标函数为飞机汽油1的总产量：库存量约束(yush)为：1121122213231424380000265200408100130100 xxxxxxxx产量约束为飞机汽油2的产量：21222324250000 xxxx由物理中的分压定律， 可得有关蒸汽压力的约束条件：1njjjPVp v11121314212223242.851.424.2718.4902.851.424.2718.490 xxxxxxxx同样可

22、得有关辛烷数的约束条件为：111213141112131416.52.04.017.007.57.013.08.00 xxxxxxxx第39页/共55页第四十页，共55页。综上所述，得该问题(wnt)的数学模型为：111213142122232411211222132314241112131421222324111213142122max2500003800002652004081001301002.851.424.2718.4902.851.424.2718.49016.5241707.57xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx232413800,(1,2;1,2,3,4)ijxxxij2.32.3配料配料(pi lio)(pi lio)问题问题第40页/共55页第四十一页，共55页。例7某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回