2._线性规划(14课时)

1、1 这一章介绍在分析各种管理问题中非常有用的一个强大工具这一章介绍在分析各种管理问题中非常有用的一个强大工具的基本原理，即线性优化模型。我们论证开发和利用线性优化的基本原理，即线性优化模型。我们论证开发和利用线性优化模拟工具所需要的基本概念，并说明这些工具如何能够帮助管模拟工具所需要的基本概念，并说明这些工具如何能够帮助管理人员从他们的公司资源中获得最多价值。理人员从他们的公司资源中获得最多价值。 线性优化模型正应用于有关全球经济中的每个领域，包括运线性优化模型正应用于有关全球经济中的每个领域，包括运输、电信、日程的制定，以及战略决策的支持。计算机科学家输、电信、日程的制定，以及战略决策的支持

2、。计算机科学家尤金尤金.劳勒劳勒(Eugene Lawler)说说:“线性优化模型应用于资源配置、线性优化模型应用于资源配置、生产计划、工人的日程安排、计划投资组合以及营销策略的描生产计划、工人的日程安排、计划投资组合以及营销策略的描述，线性优化模型对当今工业界的多种作用和经济影响是真正述，线性优化模型对当今工业界的多种作用和经济影响是真正令人赞叹的。令人赞叹的。”l第第2章章 线性规划问题的数学模型线性规划问题的数学模型l第第3章章 线性规划问题的解法线性规划问题的解法图解法单纯形法原理及计算步骤对偶单纯形法Excel求解l第第4章章 对偶理论与灵敏度分析对偶理论与灵敏度分析线性规划的对偶理

3、论对偶解的经济解释和影子价格灵敏度分析319391939年苏联的经济学家年苏联的经济学家.在在生产组织与计划中的数学方法生产组织与计划中的数学方法一书中，首次用线性规一书中，首次用线性规划方法解决了生产组织与运输问题。划方法解决了生产组织与运输问题。19471947年美国数学家年美国数学家G.B.DantzigG.B.Dantzig提出了线性规划的数学模提出了线性规划的数学模型，并给出了求解该模型的单纯形法（型，并给出了求解该模型的单纯形法（Simplex method).Simplex method).这标志着线性规划这一运筹学的重要分支的诞生。这标志着线性规划这一运筹学的重要分支的诞生。计

4、算机的发展促进了计算机的发展促进了LPLP计算理论的发展，使其应用更加广计算理论的发展，使其应用更加广泛和深入。泛和深入。生产的组织与计划问题生产的组织与计划问题运输问题运输问题合理下料问题合理下料问题配料问题配料问题生产布局问题生产布局问题n特点特点：在现有条件下，统筹安排，使总的经济效益最好。：在现有条件下，统筹安排，使总的经济效益最好。6 2.1 LP问题及其数学模型例1(课本P13): 某个工厂生产甲、乙两种产品。每件产品的利润、所消耗的材料、工时及每天的材料限额，如表2.1所示.试问如何安排生产,使每天所得的利润为最大?甲甲乙乙限额限额材料材料2324工时工时3226利润利润(元元/

5、件件)43解: 这是一个研究在现有资源条件下,如何充分利用资源，从而使产出达到最大的问题.7解：解：设设x1,x2分别表示每天生产产品甲、乙的产量。由于分别表示每天生产产品甲、乙的产量。由于资源的限制，所以有：资源的限制，所以有： 材料的限制条件:2x1+3x224工时的限制条件： 3x1+ 2x2 26 （称为资源约束条件）同时，产品甲、乙甲、乙的产量不能是负数，所以有x10，x20（称为变量的非负约束）显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1，x2以得到最大的利润，即使目标函数 Z=4x1+3x2的值

6、达到最大。8综上所述，该生产计划安排问题可用以下数学模型表示：0,26232432. .212121xxxxxxts max z = 4x1+3x29 某养鸡专业户某养鸡专业户,养鸡养鸡1000只只,用大豆和谷物饲料混合喂用大豆和谷物饲料混合喂养养,每天每只鸡平均吃混合饲料每天每只鸡平均吃混合饲料0.5公斤公斤;其中应至少含有其中应至少含有0.1公斤的蛋白质和公斤的蛋白质和0.002公斤钙公斤钙.已知每公斤大豆含有已知每公斤大豆含有50%的蛋白质和的蛋白质和0.5%的钙的钙,价格是每公斤价格是每公斤1.00元元;每公斤谷物含每公斤谷物含有有10%的蛋白质和的蛋白质和0.4%的钙的钙,价格是每公

7、斤价格是每公斤0.30元元.粮食部粮食部门每周只保证供应谷物饲料门每周只保证供应谷物饲料2500公斤公斤,大豆供应量不限大豆供应量不限,问问如何搭配这两种饲料如何搭配这两种饲料,才能使喂养成本最低才能使喂养成本最低?10解解:设每周供应大豆和谷物设每周供应大豆和谷物x1,x2公斤，则由它们配合而成的公斤，则由它们配合而成的混合饲料总量应恰好为鸡群一周的饲料混合饲料总量应恰好为鸡群一周的饲料,从而有从而有 x1+x2=710000.5=3500,即即 x1+x2=3500由蛋白质要求由蛋白质要求: 50%x1+10%x2 710000.1=700即即5x1+x2 3500由钙要求由钙要求:0.5

8、%x1+0.4%x2 710000.002=14即即5x1+4x2 14000谷物饲料限制谷物饲料限制: x22500目标是喂养成本最低目标是喂养成本最低:minZ=x1+0.3x2因此因此,综合而得其数学模型为综合而得其数学模型为:0,25001400045700053500. .3 . 0min21221212121xxxxxxxxxtsxxZ例3 运输问题（课本P16）11 某公司经销某种产品，三个产地和四个销地的产量、销量、单位运价如下表所示。问在保证产销平衡的条件下，如何调运可使总运费最少？ 销地 单位运价产地B1B2B3B4产量A15610360A2419740A3423860销量

9、3050404012解:（1）确定决策变量：设xij(i=1,2,3;j=1,2,3,4)为从产地 i运到销地j的运量 xcij31i41jij（2）确定目标函数：总运费最小 minz= （3）确定约束条件： x11+x12+x13+x14=60产量约束： x21+x22+x23+x24=40 x31+x32+x33+x34=60 x11+x21+x31=30 销量约束： x12+x22+x32=50 x13+x23+x33=40 x14+x24+x34=40 非负约束 xij0 13由此模型总结为： )4 , 3 , 2 , 1j ; 3 , 2 , 1i (040405030604060.

10、 t . sZminxxxxxxxxxxxxxxxxxxxxxxxxxXCij34241433231332221231211134333231242322211413121131i41jijij 上述几例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大或最小的问题。它们具有共同的特征：（1）每个问题都可用一组决策变量(x1,x2,xn)表示某一方案，其具体的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可对变量的取值加以约束，如非负约束。（2）存在一组线性等式或不等式的约束条件。（3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目

11、标函数实现最大化或最小化。15满足以上三个条件的数学模型称为LP问题的数学模型，其为： 0,),(),(),(.min)(21222122222221112122112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxczMax或目标函数 资源约束非负约束16或其中c=(c1,c2,cn)，称为价值系数向量；aaaaaaaaamn2m1mn22221n11211A称为技术系数矩阵(也称消耗系数矩阵) 0Xb),(AXt . scxzmin)max( 或m21bbbb称为资源限制向量, X=(x1,x2,xn)T称为决策变量向量Objective fu

12、nctionFunctional constraint or Structure constraintNon-negativity constraint or non-negativity condition181920下面我们再来看几个实际例子。案例4 课本P32 例2-11（投资计划问题）某公司经调研分析知，在今后三年内有四种投资机会。第种方案是在三年内每年年初投资，年底可获利15%，并可将本金收回；第种是在第一年的年初投资，第二年的年底可获利45%，并将本金收回，但该项投资不得超过2万元；第种是在第二年的年初投资，第三年的年底可获利65%，并将本金收回，但该项投资不得超过1.5万元；第种

13、是在第三年的年初投资，年底收回本金，且可获利35%，但该项投资不得超过1万元。现在本公司准备拿出3万元来投资，问如何计划可使到第三年年未本利和最大？ 21解：问题分析。该问题的实际投资背景如下表所示：（1）确定决策变量：设xij表示第i年对第j个方案的投资额,i=1,2,3; j=1,2,3,4年份 一 二 三 四 x11 1.15x11 x12 1.45x12 x21 1.15x21 x23 1.65x23 x31 1.15x31 x34 1.35x3422（2）确定目标函数：第三年年未的本利和为 maxz=1.65x23+1.15x31+1.35x34 （3）确定约束条件：每一年的投资额应

14、等于当年公司拥有的资金数：x11+x12=3x21+x23=1.15x11 x31+x34=1.45x12+1.15x21 每个方案投资额的限制：x122x231.5 非负约束：xij0,i=1,2,3;j=1,2,3,4 x34123案题案题5 一贸易公司专门经营某商品的批发业务一贸易公司专门经营某商品的批发业务,公司有库容公司有库容5000单位的仓库单位的仓库,一月一日一月一日,公司有库存公司有库存1000单位单位,并有资金并有资金20000元元.估估计第一季度该商品价格如表所示计第一季度该商品价格如表所示.进货价进货价出货价出货价一月一月2.853.10二月二月3.053.25三月三月2

15、.902.95如买进的商品当月到货如买进的商品当月到货,但需到下月才能卖出但需到下月才能卖出,且规定且规定“货到付货到付款款”.公司希望本季末库存为公司希望本季末库存为2000单位单位,问应采取什么样的买进问应采取什么样的买进卖出的策略可使卖出的策略可使3个月总的获利最大个月总的获利最大?24解：设解：设xi为第为第i个月的进货量，个月的进货量，yi为第为第i个月的出货量个月的出货量,则其线则其线性规划模型为：性规划模型为：2000100095. 205. 325. 385. 210. 32000090. 210005000100025. 385. 210. 32000005. 3100050

16、00100010. 32000085. 21000. .90. 295. 205. 325. 385. 210. 3max332211322113221132211211211211111332211xyxyxyyxyxyxxyxyyxyxyyxyxxyyxyyxytsxyxyxyZ25某文教用品厂，其经济结构为：某文教用品厂，其经济结构为：产品范围产品范围：信封，公文袋，便条：信封，公文袋，便条工人总数工人总数：100人人原料情况：每天有原料情况：每天有30000公斤纸胚公斤纸胚生产定额生产定额：每个工人每天单独生产三种产品的任何一种定：每个工人每天单独生产三种产品的任何一种定额都是额都是3

17、0单位单位消耗定额消耗定额：1单位信封用纸胚单位信封用纸胚10/3公斤，公斤， 1单位公文袋用纸单位公文袋用纸胚胚40/3公斤，公斤， 1单位便条用纸胚单位便条用纸胚79/3公斤公斤盈利情况：盈利情况：信封，公文袋，便条的单位利润分别是信封，公文袋，便条的单位利润分别是2元、元、3元、元、1元元为使盈利最大，建立该问题的线性规划模型为使盈利最大，建立该问题的线性规划模型案例案例6(P26) （合理下料问题）要用一批长度为7.4米的园钢做100套钢架，每套钢架由2.9米、2.1米、1.5米的园钢各一根组成，问：应如何下料才能使所用的原料最省？ 解：问题分析：一根长度为7.4米的园钢，要裁出2.9

18、米、2.1米、1.5米的料有多种裁法，如可裁出一根2.9米、二根2.1米，也可裁出三根2.1米的。这样我们把所有裁法列举出来，如下表所示： 下料 方案 根数 一 二 三 四 五 六 七 八 长度米 2.9 1 1 1 2 0 0 0 0 2.1 2 0 1 0 1 2 3 0 1.5 0 3 1 1 3 2 0 4 合计 7.1 7.4 6.5 7.3 6.6 7.2 6.3 6 料头（米） 0.3 0 0.9 0.1 0.8 0.2 1.1 1.427（1） 确定决策变量：设xj表示按第j种方案所用的园钢的数量（2） 确定目标函数：问题要求所用原料最省，所用原料为： minz=x1+x2+x

19、3+x4+x5+x6+x7+x8（3） 确定约束条件： 2.9米园钢的数量限制 x1+x2+x3+2x4100 2.1米园钢的数量限制 2x1+x3+x5+2x6+3x7100 1.5米园钢的数量限制 3x2+x3+x4+3x5+2x6+4x3100 非负限制 xj0，且为整数， j=1,2,8 建立线性规划模型的一般步骤：建立线性规划模型的一般步骤：（1）确定决策变量；（2）确定目标函数；（3）确定约束条件。28案例案例7（P27木材库存问题）木材库存问题）一个木材储运公司有很大的仓库用以一个木材储运公司有很大的仓库用以储运出售木材。由于木材季度价格的变化，该公司于每季度初购进储运出售木材。

20、由于木材季度价格的变化，该公司于每季度初购进木材，一部分于本季度内出售，一部分储存起来以后出售。已知该木材，一部分于本季度内出售，一部分储存起来以后出售。已知该公司仓库的最大储存量为公司仓库的最大储存量为2000万米万米3，储存费用为（，储存费用为（70+100u）千元）千元/万米万米3，u为存储时间（季度数）。已知每季度的买进卖出价及预为存储时间（季度数）。已知每季度的买进卖出价及预计的销售量如下表所示。计的销售量如下表所示。 季度季度买进价（万元买进价（万元/万米万米3）卖出价（万元卖出价（万元/万米万米3）预计销售量（万米预计销售量（万米3）冬冬4104251000春春430440140

21、0夏夏4604652000秋秋4504551600由于木材不宜久贮，所有库存木材应于每年秋末售完。为使售后利由于木材不宜久贮，所有库存木材应于每年秋末售完。为使售后利润最大，试建立这个问题的线性规划模型。润最大，试建立这个问题的线性规划模型。 29设设yi分别表示冬、春、夏、秋四个季度采购的木材数，分别表示冬、春、夏、秋四个季度采购的木材数，xij代表第代表第i季度季度采购的用于第采购的用于第j季度销售的木材数。季度销售的木材数。1600 xxxx0 xy2000yxxx2000 xxx0 xxy2000yxxxx1400 xx0 xxxy2000yxxx1000 x0 xxxxy2000y)

22、y450 x455()y460 x438x465()y430 x428x448x440()y410 x438x423x425(max443424144444342414332313343333242314132212242322221413121114131211114443343322423221131211季季度度买进价（万买进价（万元元/万米万米3）卖出价（万卖出价（万元元/万米万米3）预计销售量预计销售量（万米（万米3）冬冬 4104251000春春 4304401400夏夏 4604652000秋秋 4504551600案例案例8、有一艘货轮，分前、中、后三个舱位，它们的容积与最大允

23、许有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如表载重量如表1所示。现有三种货物待运，已知有关数据列于表所示。现有三种货物待运，已知有关数据列于表2。为了航。为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系，具体要求前、后舱分别与中舱之间载重量比例上偏差不量的比例关系，具体要求前、后舱分别与中舱之间载重量比例上偏差不超过超过15%，前、后舱之间不超过，前、后舱之间不超过10%。问该货轮应装载。问该货轮应装载A，B，C各多各多少件，运费收入为最大？试建立这个问题的线性规划模型。少件，运费

24、收入为最大？试建立这个问题的线性规划模型。 前舱前舱中舱中舱后舱后舱最大允许载重量（吨）最大允许载重量（吨）200030001500容积（立方米）容积（立方米）400054001500商品商品数量（件）数量（件）每件体积（立方米每件体积（立方米/件）件）每件重量（吨每件重量（吨/件）件） 运价（元运价（元/件）件）A6001081000B100056700C8007560031设表示设表示xij装于第装于第j(j=1,2,3)舱位的第舱位的第i(i=1,2,3)种商品的数量种商品的数量)10.01 (34x5x6x8x5x6x8)10.01 (34)15.01 (21x5x6x8x5x6x8)

25、15.01 (21)15.01 (32x5x6x8x5x6x8)15.01 (32800 xxx1000 xxx600 xxx1500 x7x5x105400 x7x5x104000 x7x5x101500 x5x6x83000 x5x6x82000 x5x6x8)xxx(600)xxx(700)xxx(1000zmax332313312111322212332313322212312111333231232221131211332313322212312111332313322212312111333231232221131211舱位载重限制舱位载重限制舱位体积限制舱位体积限制商品数量限制商

26、品数量限制平衡条件平衡条件前舱中舱后舱重量200030001500容积400054001500商品数量体积重量运价A6001081000B100056700C80075600P31案例案例9 . (仓库租用问题仓库租用问题)捷运公司拟在下一年度的捷运公司拟在下一年度的1-4月的月的4个月内个月内需租用仓库堆放物资需租用仓库堆放物资.已知各月份所需仓库面积数列于表已知各月份所需仓库面积数列于表1.仓库租借费仓库租借费用随合同期而定用随合同期而定,期限越长期限越长,折扣越大折扣越大,具体数字见表具体数字见表2.租借仓库的合同租借仓库的合同每月初都可办理每月初都可办理,每份合同具体规定租用面积数和期

27、限每份合同具体规定租用面积数和期限.因此该厂可根因此该厂可根据需要据需要,在任何一个月初办理租借合同在任何一个月初办理租借合同.每次办理时可签一份每次办理时可签一份,也可签若也可签若干份租用面积和租借期限不同的合同干份租用面积和租借期限不同的合同,试确定该公司签订租借合同的最试确定该公司签订租借合同的最优决策优决策,目的是使所付租借费用最小目的是使所付租借费用最小.月份1234所需仓库面积(100m2)15102012表表1合同租借期限1个月2个月3个月 4个月仓库借费用(元/100m2)2800450060007300表表233解解:1)设决策变量设决策变量xij表示捷运公司在第表示捷运公司

28、在第i(I=1,2,3,4)个月初签订的个月初签订的租借期为租借期为j(j=1,2,3,4)个月的仓库面积的合同个月的仓库面积的合同(单位为单位为100m2).因因5月份起该公司不需要租借仓库月份起该公司不需要租借仓库,故故x24,x33,x34,x42,x43,x44均为零均为零2)目标函数目标函数:使总的租借费用最小使总的租借费用最小xxxxxxxxxxZ142313322212413121117300)(600)(4500)(2800min3)约束条件约束条件:每个月份所需仓库面积的限制每个月份所需仓库面积的限制)4 , 3 , 2 , 1; 4 , 3 , 2 , 1(01220101

29、54132231432312322141323222114131214131211jixxxxxxxxxxxxxxxxxxxxxij34案例案例10 (混合配料问题混合配料问题)某糖果厂用原料某糖果厂用原料A,B,C加工成三种不同加工成三种不同牌号的糖果甲牌号的糖果甲,乙乙,丙丙.已知各种牌号糖果中已知各种牌号糖果中A,B,C含量含量,原料成本原料成本,各种原料的每月限制用理各种原料的每月限制用理,三种牌号糖果的单位加工费及售价三种牌号糖果的单位加工费及售价如下表所示如下表所示.问该厂每月生产这三种牌号糖果各多少时问该厂每月生产这三种牌号糖果各多少时,使该厂使该厂获利最大获利最大.试建立这个问

30、题的线性规划模型试建立这个问题的线性规划模型.甲乙乙丙原料成本(元/kg)第每月限制量(kg)A60%30%2.002000B1.502500C20%50%=0目标函数：目标函数：minzmax(-z)=-cx若约束为若约束为“ ”型型左边左边+“松驰变量松驰变量”； 若约束为若约束为“ ”型型左边左边“松驰变量松驰变量”若变量若变量xj 0-xj 0变量，变量， 若变量若变量xj无限制无限制令令xj=xj xj 若右边常数若右边常数bi=0缩写形式缩写形式: :., 2 , 1, 0, 2 , 1,.maxnjxmibxatsxcZjnjjjijnjjj0, 0, 0.max21221122

31、222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZ标准型标准型矩阵表示矩阵表示mnmmnnaaaaaaaaaA212222111211ncccC21其中，mbbbb21nxxxx210.maxxbAxtsCxZ41P52例3-2 化下述问题为标准型minz=-x1+2x2-3x3 x1+2x2+3x37 s.t. -x1+x2-x3-2 -3x1+x2+2x3=5 x1,x30,x2无约束 解：首先考察变量：令 ，并加入松驰变量x4,x5化为如下标准型： xxx222 0,52)(32)(73)(2543221322

32 .3)(2max3221xxxxxxxxxxxxxxxxxxxxxxxxtsz42练习：课本P53无约束y, x3x2yx. t . syxmax解：令 0 x, 00 x, xx当当 0 x, x0 x, 0 x当当0y, 00y, yy当当 0y, y0y, 0y当当 则 xxx xxx yyy yyy 加入松驰变量s,w，得到标准型如下： 0w, s ,y,y,x,x3wxx2syyxx. t . s)yy()xx(zmax无约束y, x3x2yx. t . syxmax 对于标准型LP问题 p 可行解可行解(feasible solution)：满足约束条件(

33、1)和(2)的解。p 基基(basis)：A中线性无关的列向量构成的子矩阵，称为该问题的一个基，与这些列向量对应的变量称为基变量基变量（basic variable）一、一、 解的基本概念解的基本概念(2) 0(1) .maxxbAxtsCxZA是 mn 矩阵，m n，且A的秩为m.2.1 LP问题的解p最优解最优解（optimal solution）：若基本可行解又是最优解（也称基本最优解），这个基就称为最优基（最优基（optimal basis）。p基本解基本解（basic solution）：对于基，令非基变量为零，求得满足（1）式的解，称为该基对应的基本解。p基本可行解基本可行解（ba

34、sic feasible solution）：满足（2）式的基本解称为基本可行解；基本可行解所对应的基称为可行基可行基（feasible basis）。凸集不是凸集二、解的性质二、解的性质极点p线性规划问题的几个定理线性规划问题的几个定理p 定理3-4 线性规划问题有可行解，必有基本可行解；有最优解，必有基本最优解。p定理3-1 线性规划问题的可行域是凸集。p定理3-2 A为线性规划问题可行域的极点的充要条件是的A正分量对应的系数列向量线性无关。（证明从略）p定理3-3 A是可行域的极点的充要条件是它为基本可行解。 （证明从略）综上所述,我们在理论上得到了线性规划问题的以下结论：l线性规划问题

35、的可行域是一凸集(包括有界凸集和无界凸集)；线性规划问题的每个基本可行解对应着可行域的一个极点（顶点）；若线性规划问题有最优解，必在可行域的某一极点上得到。 由此可见，我们只需在基本可行解中寻求最优解。如何有效地寻求最优解，这就是下节要介绍的单纯形法。可行解集可行解集基础可行解最优解基础最优解目标函数目标函数约束条件约束条件行列式行列式0 0基矩阵基矩阵右边常数右边常数= =10987654321xxxxxxxxxx其余变量为非基变量为基变量742xxx1、LP问题图解法的步骤：问题图解法的步骤： （1）画出直角坐标系；）画出直角坐标系； （2）依次做每条约束直线，标出可行域的方向，并）依次做

36、每条约束直线，标出可行域的方向，并找出它们共同的可行域；找出它们共同的可行域； （3）任取一目标函数值作一条目标函数线（称等值）任取一目标函数值作一条目标函数线（称等值线）线）,根据目标函数（最大或最小）类型，平移该直线即根据目标函数（最大或最小）类型，平移该直线即将离开可行域处，则与目标函数线接触的最终点即表示将离开可行域处，则与目标函数线接触的最终点即表示最优解。最优解。0, 08234.52max21212121xxxxxxtsxxW目标函数等目标函数等值线值线1x2x此点为此点为LP的最优解的最优解目标函数目标函数等值线等值线可行域可行域o41x4332x8221 xx65221 xx

37、155221 xx例例1：用图解法求解如下线性规划问题用图解法求解如下线性规划问题计算出这个最优解计算出这个最优解: :19max3282321212SLP，LPxxxxx的目标函数最优值为的最优解为上述作法称为上述作法称为LP的图解法的图解法.本问题有本问题有唯一最优解唯一最优解.例例2 用图解法解下面的线性规划用图解法解下面的线性规划0, 08234.2max21212121xxxxxxtsxxZAB目标函数等目标函数等值线值线目标函数目标函数等值线等值线1x2x08221 xx计算出计算出LPLP的最优解及目标函数最优值的最优解及目标函数最优值: :8max24482:32382:211

38、2121221SLPxxxxxBxxxxxA的最优值均为除A,B两个最优解外,AB线段上的所有点都是LP的最优解.本问题有无穷多最优解.例例3 3 用图解法解下面的线性规划用图解法解下面的线性规划0, 0331.2min21212121xxxxxxtsxxZ1x2xo无界的可无界的可行解集行解集1Z3Z此题此题有可行解有可行解但无最优解但无最优解112Z例例4 4 用图解法解下面的线性规划用图解法解下面的线性规划0, 011.3max21212121xxxxxxtsxxZ无可行解1x2xo本题本题无可行解，更无最优解无可行解，更无最优解p有唯一最优解有唯一最优解, ,这个最优解一定在可行解集合

39、的某一顶点上这个最优解一定在可行解集合的某一顶点上达到达到; ;p有无穷多最优解有无穷多最优解, ,最优解充满一个线段最优解充满一个线段, ,可以用它的两个端可以用它的两个端点作为代表点作为代表; ;p有可行解有可行解, ,但无最优解但无最优解; ;p无可行解无可行解. . 小结小结: : 两个变量的两个变量的LPLP图解法有如下四种情况图解法有如下四种情况592、线性规划的有关定理（、线性规划的有关定理（）：）： （1）LP问题的可行域是凸集（凸多边形，凸多面体，问题的可行域是凸集（凸多边形，凸多面体，）。）。 （2）LP问题最优解若存在，则必可在可行域的顶点上达到。问题最优解若存在，则必可

40、在可行域的顶点上达到。 （3）LP问题的可行域的顶点个数是有限的。问题的可行域的顶点个数是有限的。 （4）若）若LP问题若有两个最优解，则其连线上的点都是最优解问题若有两个最优解，则其连线上的点都是最优解 因此，求解因此，求解LP问题可转化为：问题可转化为：“如何在可行域的顶点上求出如何在可行域的顶点上求出使目标函数值达到最优的点的问题使目标函数值达到最优的点的问题”结论：结论：（5）对于标准型的）对于标准型的LP问题，问题，X是基可行解的充要条是基可行解的充要条件是件是X为可行域的顶点。为可行域的顶点。 （6）LP问题可行域顶点的个数问题可行域顶点的个数=基可行解的个数基可行解的个数基的基的

41、个数个数Cmn603.图解法只适用于两个变量（最多含三个变量）的LP问题。4.求解LP问题方法的思考：完全枚举法，对m、n较大时，Cmn是一个很大的数，几乎不可能；从可行域的一个顶点（基可行解）迭代到另一个顶点（基可行解）。61练习：判断下列说法是否正确练习：判断下列说法是否正确1、X(0)为线性规划问题的最优解，为线性规划问题的最优解， X(0)则一定是可行解则一定是可行解2、在线性规划问题的可行解集的顶点中一定可以找到最优解。、在线性规划问题的可行解集的顶点中一定可以找到最优解。3、线性规划问题如果存在最优解，则一定存在基础最优解。、线性规划问题如果存在最优解，则一定存在基础最优解。4、如

42、果线性规划问题的可行解集为一无界区域，则最优解一、如果线性规划问题的可行解集为一无界区域，则最优解一定不存在。定不存在。5、如果、如果X(1)、 X(2)是线性规划问题的两个不同最优解，则该线是线性规划问题的两个不同最优解，则该线性规划问题一定有无穷多个最优解。性规划问题一定有无穷多个最优解。（一）、单纯形法的基本思路（一）、单纯形法的基本思路 如果线性规划问题存在最优解，一定有一个基本可行解如果线性规划问题存在最优解，一定有一个基本可行解是最优解。因此单纯形法迭代的基本思路是：先找出一个基是最优解。因此单纯形法迭代的基本思路是：先找出一个基本可行解，判断其是否为最优解，如为否，则转换到相邻的

43、本可行解，判断其是否为最优解，如为否，则转换到相邻的基本可行解，并使目标函数值不断增大，一直找到最优解为基本可行解，并使目标函数值不断增大，一直找到最优解为止。止。 63),.,2 , 1(0.max112211221111112211njxbxaxaxbxaxaxbxaxaxxcxcxczjmnmnmmmmnnmmnnmmnn将目标函数改写为：把上述方程组和目标函数方程构成n+1个变量，m+1个方程的方程组，并写成增广矩阵的形式：1、建立初始单纯形表，、建立初始单纯形表，假定B=I，b0 02211nnxcxcxcz Z x1 x2 xm xm+1 xn0000110000100001011

44、22121111nmmmnmmnmnmccbaabaabaa0.221111221122111111nnmnmnmmmmnnmmnnmmxcxcxczbxaxaxbxaxaxbxaxaxnmjjijiixabx1：以非基变量表示基变量minmjnmjjjjijiixcxabcZ111)( miminmjnmjjjjjiiiixcxacbc1111)( minmjjjmiijiiixcacbc111)( mimijiijiiacZbcZ110,令令nmjjjjoxcZZZ1)(于是于是得代目标函数将nnnmjjijiixcxcxczxabx2211166因此，上述增广矩阵就可写成：因此，上述增广

45、矩阵就可写成： Z x1 x2 xm xm+1 xn0111221211110001100001000010zczczbaabaabaannmmmmnmmnmnm67再令jmiijijjjcaccZ1 则上述增广矩阵可写成下面表格形式：即初始单纯形表T（B） CjC1Cmcm+1cnCBxBbx1xmxm+1xniC1x1b110a1m+1a1nC2x2b200a2m+1a2n： ：Cmxmbm01amm+1amnZZ000m+1nj检验数行68上述初始单纯形表可确定初始可行基和初始基可行解：B=(P1,P2,Pm)=I, x=(b1,b2,bm, 00)T从初始单纯形表建立的过程可以看到以下

46、事实： （1）凡LP模型中约束条件为“”型，在化为标准型后必有B=I，如果b0，则模型中约束方程的各数据不改变符号照抄在表中相应的位置。目标函数中非基变量的系数则以相反数填入检验数行各相应位置。 （2）在单纯形表中，凡基变量所在的列向量必是单位列向量，其相应的检验数均为零。 mimijijijjjiinmjcaccZbcZ110),.,1(, 692、判别最优解、判别最优解 1 在T(B)中，若所有的检验数j0 (j=1,2,n)则B为最优基，相应的基可行解为最优解，停止计算。 2 在T(B)中，若有k0 (1kn)，且xk的系数列向量Pk0，则该问题无界，停止计算。否则转入（3） （3）换基

47、迭代（基变换） 1 先确定进基变量Xk: k=minj| j0，即检验数行从左至右选择负数所对应的变量进基。 LKaKPLkLikikiabaab0|min2 按最小比值原则确定出基变量xL： 3 以 为主元，进行初等行变换（又称旋转变换）即将列向量 变换为单位列向量：70返回（2） 。 换基迭代的关键在于将换入变量对应的列向量KP 用初等行变换方法变换成单位列向量。其中主元LKa变成1。即 0:1:00:121mkkkkkaaaaP第L个分量 如果在最终表中有非基变量的检验数为0，则该问题有多重最优解。 例例5 用表格形式的单纯形法求解下列线性规划问题用表格形式的单纯形法求解下列线性规划问题

48、710,26232432. t . s34Zmaxxxxxxxxx21212121解：引进松驰变量x3, x4，化为标准形得：0,26232432. t . s0034Zmaxxxxxxxxxxxxxxx43214213214321从标准形中可看出存在可行基B=（P3，P4）=I，基变量为X3，X4；非基变量为X1，X2。建立初始单纯形表得： cj 4 3 0 0CBXBb x1 x2 x3 x400 x3x42426 2 3 1 0 3 2 0 1 Z 0 -4 -3 0 0 由于由于X1，X2的检验数均为负，且的检验数均为负，且X1的检验数绝对值最大，选的检验数绝对值最大，选取取X1为进基

49、变量；再按最小比值为进基变量；再按最小比值=min（24/2，26/3）=26/3，因此选取因此选取X4为出基变量，进行换基迭代。为出基变量，进行换基迭代。 cj 4 3 0 0CBXBb x1 x2 x3 x404x3x120/326/3 0 5/ 3 1 -2/3 1 2/3 0 1/3 Z104/3 0 -1/3 0 4/373 cj 4 3 0 0CBXBb x1 x2 x3 x434x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5 Z36 0 0 1/5 6/5 表中最后一行的所有检验数均为非负数，表明目标函数表中最后一行的所有检验数均为非负数，表明目标函数已达到最大

50、值，上述表为最优表。从表中可得到最优解为已达到最大值，上述表为最优表。从表中可得到最优解为X=（x1,x2,x3,x4）=（6，4，0，0），最优值为），最优值为Z=36例2、用表格形式的单纯形法求解下列线性规划问题0,1826224. t . s3Zmaxxxxxxxxxxx2121212121解：化标准形，建立初始单纯形表解：化标准形，建立初始单纯形表 cj 3 1 0 0 0 CBXBb x1 x2 x3 x4 x5 000 x3x4x54218 1 1 1 0 0 -1 1 0 1 0 6 2 0 0 1 Z0 -3 -1 0 0 0 75经过一次迭代得到最优表如下经过一次迭代得到最优

51、表如下 cj 3 1 0 0 0 CBXBb x1 x2 x3 x4 x5 003x3x4x1153 0 2/3 1 0 -1/6 0 4/3 0 1 1/6 1 1/3 0 0 1/6 Z9 0 0 0 0 1/2 最优解为最优解为X=(x1,x2)=(3，0), maxZ=9。但是在这个问题中，非基变量。但是在这个问题中，非基变量x2的的检验数为检验数为0，说明此问题有多重最优解。，说明此问题有多重最优解。 以以x2为进基变量，再迭代一次，为进基变量，再迭代一次，得到另一个最优解。结果如下表。得到另一个最优解。结果如下表。 cj 3 1 0 0 0 CBXBb x1 x2 x3 x4 x5

52、 000 x3x4x54218 1 1 1 0 0 -1 1 0 1 0 6 2 0 0 1 Z0 -3 -1 0 0 0 76 cj 3 1 0 0 0 CBXBb x1 x2 x3 x4 x5 003x2x4x13/235/2 0 1 3/2 0 -1/4 0 0 -2 1 1/2 1 0 -1/2 0 1/4 Z9 0 0 0 0 1/2 此表对应的最优解为此表对应的最优解为X=(x1,x2)=(5/2，3/2), maxZ=9nmjjjjoxcZZZ1)(例题例题3 求解下列线性规划问题。求解下列线性规划问题。 0,536322.max32132132121xxxxxxxxxtsxxZ

53、 cj 1 1 0 0 0CBXBb x1 x2 x3 x4 x500 x4x546 -2 2 3 1 0 -3 1 -1 0 1 Z0 -1 -1 0 0 0解：解： 化标准形，列出其初始单纯形表为化标准形，列出其初始单纯形表为从表中可以看出，从表中可以看出，x1所对应的检验数及列向量均为负数，所对应的检验数及列向量均为负数，因此，此问题存在无界解，即目标函数因此，此问题存在无界解，即目标函数+ 。nmjjjjoxcZZZ1)(jjjcZ 78练习：练习：求解下列线性规划问题求解下列线性规划问题0,6242. .2max32121321321xxxxxxxxtsxxxZ其单纯形表为：其单纯形

54、表为： cj -1 2 1 0 0 CBXBb x1 x2 x3 x4 x5 00 x4x546 2 1 1 1 0 1 2 0 0 1 Z0 1 -2 -1 0 0 cj -1 2 1 0 0 CBXBb x1 x2 x3 x4 x5 12x3x213 3/2 0 1 1 -1/2 1/2 1 0 0 1/2 Z7 7/2 0 0 1 1/2 cj -1 2 1 0 0 CBXBb x1 x2 x3 x4 x5 02x4x213 3/2 0 1 1 -1/2 1/2 1 0 0 1/2 Z6 2 0 -1 0 1 最优解为最优解为X=(x1,x2,x3)T=(0,3,1)T，最优值为：，最优

55、值为：maxZ=73、 换基迭代换基迭代检验数有两种情况检验数有两种情况: 所有检验数大于等于零所有检验数大于等于零,则基则基B已是最优基已是最优基,得到最优表及最得到最优表及最优解优解,停止计算停止计算; 有某些检验数为负值，此表不是最优表即基有某些检验数为负值，此表不是最优表即基B不是最优基，不是最优基，则应进行换基迭代则应进行换基迭代.换基迭代的步骤换基迭代的步骤:.选取入基变量选取入基变量:设设 则相应的非基变量则相应的非基变量 为为入基变量入基变量，简称，简称“入基入基”.如果如果j不唯一不唯一,可选取绝对值较大可选取绝对值较大的的 值对应的非基变量入基值对应的非基变量入基., 01

56、jBjjpBCcjxj.求主元素并确定出基变量求主元素并确定出基变量:观察在入基变量观察在入基变量 所对应的所对应的 中的第中的第j列列,如果该列所有的分量均小于等于零如果该列所有的分量均小于等于零,则该则该LP问题无最问题无最优解优解(定理定理).如果该列存在如果该列存在正分量正分量,则以这些正分量为分母则以这些正分量为分母,以这些以这些正分量所在正分量所在行行中对应的中对应的基变量取值基变量取值为分子为分子,求出这些求出这些比值比值中的中的最最小值小值,该最小值对应的基变量为该最小值对应的基变量为出基变量出基变量,简称简称“出基出基”,出入基交出入基交叉点上的元素称为叉点上的元素称为主元素

57、主元素或轴心项或轴心项,用方框将其框起来用方框将其框起来. 这种求出基变量的方法称为这种求出基变量的方法称为 法则法则. jxAB1.换基迭代换基迭代:利用矩阵的初等变换利用矩阵的初等变换,将主元素变为将主元素变为1,将其所在列的其余元素变为将其所在列的其余元素变为0,得一张新单纯形表得一张新单纯形表.重重复上述步骤复上述步骤,经过有限次换基迭代经过有限次换基迭代,一定可得到最优一定可得到最优解解. -Z 0 -2 -5 0 0 0 4 3 8 1 0 1 0 0 0 1 0 1 0 1 2 0 0 154321xxxxx543xxx入基2x, 328,13min出基4x -Z 15 -2 0

58、 0 5 0 4 3 2 1 0 1 0 0 0 1 0 1 0 1 0 0 -2 154321xxxxx523xxx入基1x212,14min出基5x S19 0 0 0 1 2 2 3 2 0 0 1 2 -1 0 1 0 1 0 1 0 0 -2 154321xxxxx123xxx该表检验数全部大于等于零该表检验数全部大于等于零,称称此表为此表为最优表最优表.其结果如下表示其结果如下表示:.19max3221SSxx最优解为注意注意:松弛变量的取值不必写出松弛变量的取值不必写出.本题迭代本题迭代2次次.说明说明:(1)如果单纯形表中的基变量取值皆为正数如果单纯形表中的基变量取值皆为正数,

59、称这个基可行称这个基可行解为非退化解解为非退化解.若若LP的所有基可形解都是非退化的的所有基可形解都是非退化的,则则LP经过经过有限次迭代可达到最优有限次迭代可达到最优.(2)如果单纯形表中的基变量取值有的为零时如果单纯形表中的基变量取值有的为零时,称为称为LP的退化解的退化解,此时称此时称LP是退化的是退化的,理论上认为这种线性规划在迭代过程中可理论上认为这种线性规划在迭代过程中可能产生循环能产生循环,从而得不到最优解从而得不到最优解.为避免循环为避免循环,常采用常采用1976年年R.G.Bland提出提出Bland法则法则:单纯形表中有若干个检验数单纯形表中有若干个检验数 时时,取下标号小

60、的非基变量入基取下标号小的非基变量入基; 用用 法则选取出基变量时法则选取出基变量时,若比值相同，则选取下标号小的基变量出基若比值相同，则选取下标号小的基变量出基.0j以上各例的系数矩阵以上各例的系数矩阵A中，都存在一个中，都存在一个m阶单位阵，因此很阶单位阵，因此很容易用单纯行法求解容易用单纯行法求解.但是大多数但是大多数LP问题并不是这样问题并不是这样.0,123241123max32131221321321xxxxxxxxxxxxxxZ例例化为标准形0,12324112003max76543217316532143217654321xxxxxxxxxxxxxxxxxxxMxMxxxxxx