运筹学B线性规划.pptx

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

1、2023/4/221第一节 线性规划的一般模型 线性规划(Linear Programming，LP)是运筹学的重要分支之一，研究较早、发展较快、方法较成熟，而且是众多分支的基础，借助计算机计算更方便，应用更广泛。线性规划通常研究资源的最优利用、设备最佳运行以及费用最低等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大）。第1页/共113页2023/4/222【例】生产计划问题。某企业在计划期内计划生产甲、乙、丙三种产品。这些

2、产品分别需要在设备A、B上加工，需要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表1.1所示。已知在计划期内设备的加工能力各为200小时，可供材料分别为360、300公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为40、30、50元，假定市场需求无限制。问：企业决策者应如何安排生产计划，使企业在计划期内总的利润最大？第一节 线性规划的一般模型 一、线性规划模型的举例 第2页/共113页2023/4/223 产品产品 资源资源 甲甲 乙乙丙丙现有资源现有资源设备设备A 3 1 2 200(h)设备设备B 2 2 4 200(h)材料材料C 4 5 1 360(

3、kg)材料材料D 2 3 5 300(kg)利润（元利润（元/件）件）40 30 50表1.1 某企业单位产品资源消耗及利润x x1 1x x1 1x x1 1x x1 1x x1 1x x2 2x x2 2x x2 2x x2 2x x2 2x x3 3x x3 3x x3 3x x3 3x x3 3第3页/共113页2023/4/224【解】设x1、x2、x3 为甲、乙、丙三种产品的产量，则该线性规划问题的数学模型为：产品产品 资源资源 甲甲 乙乙 丙丙现有资源现有资源设备设备A 3 1 2 200设备设备B 2 2 4 200材料材料C 4 5 1 360材料材料D 2 3 5 300利

4、润（元利润（元/件）件）40 30 50最优解：X*=(50,30,10)T，Z*=3400，即在计划期内甲、乙、丙产量分别为50、30和10件，利润最大，为3400元。注意：最优解的表达方式！第4页/共113页2023/4/225二、线性规划的三个要素 第一节 线性规划的一般模型 决策变量（一组）决策问题待定的量值取值要求非负约束条件（一组）任何管理决策问题都是限定在一定的条件下求解把各种限制条件表示为一组等式或不等式称约束条件约束条件是决策方案可行的保障约束条件是决策变量的线性函数目标函数（一个）衡量决策优劣的准则，如时间最省、利润最大、成本最低目标函数是决策变量的线性函数有的目标要实现极

5、大，有的则要求极小第5页/共113页2023/4/226 练习练习1.11.1 某厂生产甲、乙两种产品，生产工艺路线为：各自的零部件分别在设备A、B加工，最后都需在设备C上装配。经测算得到相关数据如下表所示，单位甲、乙产品的销售价格分别为73和75元。问应如何制定生产计划，才能使总利润为最大？产品产品设备设备工时消耗工时消耗甲甲 乙乙工时成本工时成本(元元/h)生产能力生产能力(h)ABC 2 0 0 2 3 4 20 15 10161032x x1 1x x1 1x x1 1x x2 2 x x2 2x x2 2220033002244第6页/共113页2023/4/227(1)(1)决策变

6、量决策变量：设x1为甲产品的产量，x2为乙产品的产量。(2(2)约束条件约束条件：生产受设备能力制约，不能突破有效供给量。设备A的约束条件表达为 2x1 16同理，设备B的加工能力约束条件表达为 2x2 10设备C的装配能力也有限，其约束条件为 3x1+4x2 32(3)(3)目标函数：目标函数：目标是企业利润最大化 max Z=3x1+5x2(4)(4)非负约束：非负约束：甲乙产品的产量为非负 x1 0，x2 0LPLP模型：模型：s.t.(subject to)使满足，使服从第7页/共113页2023/4/228练习1.2：某厂生产甲、乙两种产品，均需在A、B、C三种不同的设备上加工，单位

7、产品加工所需工时、销售后能获得的利润及设备有效工时数见下表。问：如何安排生产计划，才能使该厂获得总利润最大？解:设甲、乙产品产量分别 为x1、x2 公斤，设总利润为Z，则：max Z=70 x130 x2 设备设备产品产品 ABC利润利润甲甲 乙乙3955937030限时限时 540450720 设备可用工时数限制 3x1+9x2 540 5x1+5x2 450 9x1+3x2 720max Z=70 x130 x2 3x1+9x2 540 s.t.5x1+5x2 450 9x1+3x2 720 x1,x2 0第8页/共113页2023/4/229线性规划的数学模型由决策变量 Decision

8、 variables 目标函数 Objective function 构成，称为三要素。约束条件 Constraintsn其主要特征是：n1.解决的问题是规划问题；n2解决问题的目标函数是多个决策变量的 线性函数，通常是求最大值或最小值；n3解决问题的约束条件约束条件是多个决策变量 的线性不等式或等式。怎样辨别一个模型是线性规划模型？第9页/共113页2023/4/2210二、线性规划模型的举例 2、物资运输问题例：例：某产品商有三个供货源A1、A2、A3，其经销商有4个（需求市场）B1、B2、B3、B4。已知各厂的产量、各经销商的销售量及从 Ai 到 Bj 的单位运费为Cij。问如何调配运输

9、方案，使总运费最小？销地销地产地产地B1B2B3B4产量产量A16 32550A27 5 8 4 20A33 2 9 7 30销量销量20301040 x x1111x x1212x x1313x x1414x x2121x x2222x x2323x x2424x x3131x x3232x x3333x x3434产销平衡(产量等于销量)第10页/共113页2023/4/2211(1)(1)决策变量：决策变量：设从 Ai 到 Bj 的运输量为 xij，(2)(2)目标函数：目标函数：运费最小的目标函数为：minZ=6x11+3x12+2x13+5x14+7x21+5x22 +8x23+4x

10、24+3x31+2x32+9x33+7x34(3)(3)约束条件约束条件：产量之和等于销量之和，故要满足：供应平衡条件x11+x12+x13+x14=50 x21+x22+x23+x24=20 x31+x32+x33+x34=30销售平衡条件x11+x21+x31=20 x12+x22+x32=30 x13+x23+x33=10 x14+x24+x34=40非负约束 xij0 (i=1,2,3；j=1,2,3,4)4.5 线性规划的数学模型由三个要素组成：第11页/共113页2023/4/2212【练习】现有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5(万吨)，现将粮食运往B1，B

11、2，B3，B4四个地区，其需求量分别为5，7，8，3(万吨)。产粮地到需求地的运价(元/吨)如下表所示，问如何安排一个运输计划，使总的运输费用最少？地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需求量需求量578323/23第12页/共113页2023/4/2213解：设 xij (i=1,2,3；j=1,2,3,4)为 i 个产粮地运往第 j 个需求地的运输量，这样得到下列运输问题的数学模型：运输量应大于或等于零（非负)B1B2B3B4产量产量A1326310A253828A341295需要需要量量578323第13页/共113页2023/4/221

12、43、产品配比问题 例：例：用浓度45%和92%的硫酸配置100吨浓度80%的硫酸，已经两种浓度硫酸的单价为每吨30和80元，问如何配置费用最小？决策变量决策变量：需要需要45%45%和和92%92%的硫酸分别为的硫酸分别为 x x1 1 和和 x x2 2 吨吨目标函数：目标函数：min Z=30 min Z=30 x x1 1+80 +80 x x2 2约束条件约束条件：非负约束非负约束：x1 0，x2 0第14页/共113页2023/4/2215 若有5种不同浓度的硫酸可选(30%,45%,73%,85%,92%)会如何呢？5种硫酸数量分别为 x1 1、x2 2、x3 3、x4 4、x5

13、 5 ，有：若5种硫酸价格分别为400,700,1400,1900,2500元/t，则：第15页/共113页2023/4/2216练习：某糖果厂用原料A，B，C加工成三种不同牌号的糖果甲、乙、丙。已知各种糖果的中A，B，C的含量要求，原料成本，各种原料每月的限制用量，三种牌号糖果的单位加工费及售价如下表所示。问该厂每月生产这三种牌号糖果各多少kg，利润最大？甲甲乙乙丙丙原料成本原料成本(元元/kg)每月限制用量每月限制用量(kg)A60%30%2.002000B1.502500C20%50%60%1.001200加工费加工费(元元/kg)0.500.400.30售价售价(元元/kg)3.402

14、.852.25第16页/共113页2023/4/2217解：设xij为生产第j种糖果使用的第i种原料的数量，则该问题的数学模型为：最优解：即该厂每月应生产甲种牌号糖果906.67kg，乙种牌号糖果4793.33kg，利润最大为5450元。第17页/共113页2023/4/2218练习：生产某一机床需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是2.9、2.1和1.5m，这些轴需要用同一种圆钢切割而成，圆钢长度为7.4m。现在要制造100台机床，问：最少要用多少圆钢来生产这些轴？(假设切割损失不计)解解：1 1、设一根圆钢切割成甲、乙、丙三种轴的根数分别为、设一根圆钢切割成甲、乙、丙三种轴

15、的根数分别为y y1 1,y y2 2,y y3 3,则切割方式可用不等则切割方式可用不等式式2.92.9y y1 1+2.1+2.1y y2 2+1.5+1.5y y3 37.47.4表示，求这个不等式关于表示，求这个不等式关于y y1 1，y y2 2，y y3 3的非负整数解。例如：的非负整数解。例如：y y1 1=2=2，y y2 2=0=0，则，则 y y3 3 只能为只能为1 1，余料为，余料为0.10.1。像这样的非负整数解共有。像这样的非负整数解共有8 8组，也就是有组，也就是有8 8种下料方种下料方式，如表式，如表1.41.4所示。所示。2 2、建立线性规划数学模型。设、建立

16、线性规划数学模型。设x xj j(j j=1,2,8)=1,2,8)为第为第 j j 种下料方案所用圆钢的根数。种下料方案所用圆钢的根数。4、合理下料问题第18页/共113页2023/4/2219 方案方案规格规格12345678需求量需求量y1(2.9m)21110000100y2(2.1m)02103210100y3(1.5m)10130234100总长总长7.4m0.10.30.90.01.10.20.81.4余料余料min Z=x1+x2+x3+x4+x5+x6+x7+x82x1+x2+x3+x4 1002x2+x3+3x5+2x6+x7 100 x1+x3+3x4+2x6+3x7+4

17、x8 100 xj 0,j=1,2,8 (x1=10,x2=50,x4=30,16m)第19页/共113页2023/4/22205、投资问题 某投资公司在第一年初有100万元资金，假设每年都有如下的投资方案：第一年初投入一笔资金，第二年初又继续投入此资金的50%，第三年初就可回收第一年初投入资金的两倍。问：该投资公司应如何确定投资策略才能使第六年初所拥有的资金最多？解：设解：设x x1 1为第一年的投资，为第一年的投资，x x2 2为第一年的保留资金，则：第一年的保留资金，则：x x1 1+x x2 2=100=100第二年：第二年：设设x x3 3为第二年新的投资，为第二年新的投资，x x4

18、 4为第二年的保为第二年的保留资金留资金，则：则：第20页/共113页2023/4/2221第三年：设第三年：设 x x5 5 为新的投资，为新的投资，x x6 6 为第三年的保留资金；为第三年的保留资金；第四年：设新的投资第四年：设新的投资 x x7 7 ，第四年的保留资金，第四年的保留资金 x x8 8 ；第五年第五年：设设 x x9 9 为第五年的保留资金。根据题意，第五年初不再进行新的投资，因为这为第五年的保留资金。根据题意，第五年初不再进行新的投资，因为这笔投资要到第七年初才能收回。笔投资要到第七年初才能收回。约束条件约束条件 每年应满足如下的关系：每年应满足如下的关系：追加投资金额

19、追加投资金额 +新投资金额新投资金额 +保留资金保留资金=可利用的资金总额可利用的资金总额 第21页/共113页2023/4/2222X X*(27.64,72.36,58.54,0,26.02,0,104.06,0,0)(27.64,72.36,58.54,0,26.02,0,104.06,0,0)T T，Z Z*208.12208.12。到第六年初，实有资金总额为到第六年初，实有资金总额为x x9 9+2+2x x7 7，整理后得到下，整理后得到下列线性规划模型：列线性规划模型：max Z=2max Z=2x x7+x x9 第一年新投资第一年新投资27.6427.64万元、第二年新投资万

20、元、第二年新投资58.5458.54万元、第三年新投资万元、第三年新投资26.0226.02万元、第四万元、第四年新投资年新投资104.06104.06万元，才能使第六年初拥有资金最多，为万元，才能使第六年初拥有资金最多，为208.12208.12万元。万元。第22页/共113页2023/4/2223思考题：某人有30万元资金，在今后的三年内有以下4个 投资项目可供参考，假设有钱就会用于投资。1.三年内的每年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一年的投资；2.只允许第一年年初投入，第二年末可收回，本利合计为投资额的150%，但此类投资额不超过15万元；3.第二年初允许投资

21、，可于第三年末收回，本利合计为投资额的160%，这类投资限额20万元；4.第三年初允许投资，一年回收，可获利40%，投资限额为10万元。试确定一个第三年末本利和为最大的投资计划？第23页/共113页2023/4/2224 项目项目投资时间投资时间1234第第1年初年初x11x12第第2年初年初x21x23第第3年初年初x31x34对于约束条件：对于约束条件：第第1 1年，可用于项目年，可用于项目1 1和和2 2投资：投资：x x1111+x x1212=300000=300000第第2 2年，可用于项目年，可用于项目1 1和和3 3投资，投资额为投资，投资额为x x1111的本利和：的本利和：

22、x x2121+x x2323=1.2 =1.2 x x1111第第3 3年，可用于项目年，可用于项目1 1和和4 4投资，投资额投资，投资额x x2121和和x x1212有关：有关：x x3131+x x3434=1.2 =1.2 x x2121+1.5 +1.5 x x1212投资限额：投资限额：x x1212 150000;150000;x x2323 200000;200000;x x3434 10000 10000非负约束：非负约束：x xij ij 0 (0 (i i=1,2,3;=1,2,3;j j=1,2,3,4)=1,2,3,4)对于目标函数，只需考虑第对于目标函数，只需考

23、虑第3 3年末：年末：项目项目1 1：x x31 31 1.2 1.2 x x31 31(本利和本利和)；项目项目2 2：0 0；项目项目3 3：x x23 23 1.6 1.6 x x2323(本利和本利和)；项目项目4 4：x x34 34 1.4 1.4x x3434 (本利和本利和)；maxZ=1.2 maxZ=1.2 x x3131+1.6 +1.6 x x2323+1.4 +1.4 x x3434 第24页/共113页2023/4/2225解：设解：设x xij ij为第为第 i i 年初投放到年初投放到 j j 项目的资金额项目的资金额(元元)，其数学模型为：，其数学模型为：ma

24、xZ=1.2 maxZ=1.2 x x3131+1.6 +1.6 x x2323+1.4 +1.4 x x3434 注意本题条件：有钱就会用于投资，即：注意本题条件：有钱就会用于投资，即：可利用的资金可利用的资金 =投资金额，据此建立约束等式。投资金额，据此建立约束等式。x x11 11+x x12 12=300000=300000 x x21 21+x x23 23=1.2=1.2 x x1111x x31 31+x x34 34=1.2=1.2 x x21 21+1.5+1.5 x x1212x x12 12 150000 150000 x x23 23 200000 200000 x x

25、34 34 10000 10000 x xij ij 0 (0 (i i=1,2,3;=1,2,3;j j=1,2,3,4)=1,2,3,4)第25页/共113页2023/4/2226第26页/共113页2023/4/2227第一节 线性规划的一般模型 用一组非负决策变量表示的一个决策问题；存在一组等式或不等式的线性约束条件；有一个希望达到的目标，可表示成决策变量的极值线性函数。为了书写方便，上式也可简写：第27页/共113页2023/4/2228一般地，xj0，但有时xj0或xj无符号限制。第28页/共113页2023/4/2229线性规划图解法 1、概念：利用几何图形求解两个变量线性规划问

26、题的方法。3、求解步骤：第一步：建立平面直角坐标系；第三步：在可行域内平移目标函数等值线，确定最优解及最优目标函数值。2、特点：简单、直观，但只适用于两个变量的LP问题。第二步：根据约束条件画出可行域；第29页/共113页2023/4/22301、线性规划的可行域可行域：满足所有约束条件的解的集合，即由所有约束条件共同围成的区域。maxZ=3x1+5x2 2x1 16 2x2 10 3x1+4x2 32 x10,x20s.t.2x1=162x2=103x1+4 x2=32x1x24810359OABCD第30页/共113页2023/4/22312x1=162x2=10 x1x28103583x

27、1+4x2=320ABCD2、线性规划的最优解目标函数 Z=3x1+5x2 代表以 Z 为参数的一族平行线。Z=25Z=37Z=15(4,5)X*=(4,5)TZ*=37第31页/共113页2023/4/2232x1x2O1020304010203040(15,10)最优解 X*=(15,10)T最优值 Z*=85第32页/共113页2023/4/2233246x1x2246最优解 X*=(3,1)T最优值 Z*=5(3,1)min Z=x1+2x2第33页/共113页2023/4/22343、线性规划解的特性abcd由线性不等式组成的可行域是凸多边形(凸集)凸集：对于某一集合内部任意两点连线

28、上的点都属于这个集合，我们就称这个集合为凸集。线性规划问题的可行域具有有限个顶点。目标函数最优值一定在可行域的边界(顶点)达到，而不可能在其区域的内部。第34页/共113页2023/4/2235凸集的概念设K为n维欧氏空间的一个点集，若K中任意两个点X1和X2连线上的所有点都属于K，则称K为凸集。X2X1X设X(x1,x2,xn);X1(u1,u2,un);X2(v1,v2,vn)第35页/共113页2023/4/2236四、线性规划解的可能性1、唯一最优解2、多重最优解/无穷多最优解当乙产品市场价格从75元下降到74元时，模型变为：2x1=162x2=103x1+4x2=32x1x24810

29、2580 0A AB BC CD DZ=24Z=32Z=12第36页/共113页2023/4/2237246x1x2246X(2)(3,1)TX(1)(1,3)T(5,5)min Z=5x1+5x2具有无穷多最优解，即多重最优解,通解为：01 例如：当=0.5时=(x1,x2)T=0.5(1,3)T+0.5(3,1)T =(2,2)T 第37页/共113页2023/4/22383、无界解可行域无界，目标值无限增大(缺乏必要约束)第38页/共113页2023/4/2239246x1x2246(1,2)无界解max Z=x1+2x2第39页/共113页2023/4/22404、无可行解：线性规划问

30、题的可行域是空集 (约束条件相互矛盾)第40页/共113页2023/4/2241x1x2O10203040102030405050无可行解max Z=10 x1+4x2第41页/共113页2023/4/224220130312 作业：用图解法求解以下问题（1）（2）（3）（4）第42页/共113页2023/4/2243一、线性规划的标准型 1、标准型表达方式(1)代数式：(2)向量式：(3)矩阵式：A：技术系数矩阵，简称系数矩阵；b：可用的资源量，称资源向量；C：决策变量对目标的贡献，称价值向量；X：决策变量。第二节 线性规划问题模型 第43页/共113页2023/4/2244通常X记为：，其

31、中，为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般情况mn，且r()m。其中:第44页/共113页2023/4/22452、标准型转换方法(1)“目标函数求最大值”。如果极小化原问题minZ=CX，则令 Z=Z，转为求 maxZ=CX。注意：求解后还原。（2）(2)“资源限量非负”。若某个 bi 0，则将该约束两端同乘“1”，以满足非负性的要求。（4）(3)“约束条件为等式”。对于“”型约束，则在“”左端加上一个非负松弛变量(slack variable)，使其为等式。对于“”型约束，则在“”左端减去一个非负剩余变量(Surplus variable)，使其为等式。（3）(

32、4)“决策变量非负”。若某决策变量 xk 为“取值无约束”(无符号限制)，令：xk=xk xk，(xk0,xk 0)。（1）第45页/共113页2023/4/2246【例】将下列线性规划转化为标准型(标准形式)？【解】(1)决策变量取值 x3 无符号要求(取值无约束)，即x3取正值也可取负值，标准型中要求变量取值为非负，所以可令：第46页/共113页2023/4/2247 (3)第二个约束条件是“号”，在“号”左端减去剩余变量x5，x50，x5也称松驰变量 (2)第一个约束条件是“号”，在“”左端加入松驰变量 x4，x40，即化为等式；(4)第三个约束条件是“号”且常数项为负数，因此在“”左边

33、加入松驰变量x6，x60，同时不等式两端同乘以“1”。(5)目标函数是最小值，令Z=Z,得到max Z=max(Z)，即当Z达到最小值时Z达到最大值，反之亦然。(1)x3 取值无约束，令 x3=x3 x3，x3,x3 0。第47页/共113页2023/4/2248标准型为：第48页/共113页2023/4/2249将例1.1的线性规划问题的一般形式化为标准型？第二节 线性规划问题模型 第49页/共113页2023/4/2250第二节 线性规划问题模型 第50页/共113页2023/4/2251练习：将下列线性规划模型转化为标准型？min Z=3x1 x24x3 x1 2x2+5x3 0 2x1

34、+x2 3x3 450 3x1 x2 0 x10,x20,x3 无约束解：令Z=Z,x2=x2,x3=x3 x3,其中：x2,x3,x3 0，约束引入剩余变量 x4，约束引入松弛变量 x5，则标准型：max Z=3x1 x2 4(x3 x3)+0 x4+0 x5 x1 +2x2+5(x3 x3 )x4=0 2x1 x2 3(x3 3x3)+x5 =450 3x1+x2 =0 x1,x2,x3,x3,x4,x5 0作业：教材42页,第8题 第51页/共113页2023/4/2252二、线性规划之解的概念 基矩阵：一个非奇异的子矩阵（向量线性无关）。矩阵A 中任意一个 m 列的线性无关子矩阵 B，

35、称为一个基(矩阵)。组成基的列向量称为基向量，用 Pj 表示(i=1,2,m)。基变量：与基向量 Pj 相对应的变量 xj 称为基变量。其余的 n m 个变量称为非基变量(基矩阵以外的列向量对应变量)。1、线性规划解之关系 基(本)解：令所有非基变量等于零，得出的唯一解。x3x4x5基变量是x3,x4,x5非基变量是x1,x2令非基变量 x1=x2=0，基变量取值唯一确定：x3=16，x4=10，x5=32得到一个基解：X=(0,0,16,10,32)T第52页/共113页2023/4/2253重要概念 可行解：满足约束条件AX=b和X0的解。基(本)解：令所有非基变量等于零，得出的唯一解。基

36、(本)可行解：满足X0的基解。可行基：基可行解对应的基矩阵。最优解：使目标函数最优的基可行解，称为最优解。最优基：最优解对应的基矩阵，称为最优基。第53页/共113页2023/4/2254基的概念假设线性规划问题模型系数矩阵为m行、n列(mn)，则系数矩阵中秩为m的m行m列子矩阵，称为基矩阵，简称基。基中的列向量对应的变量称为基变量，决策变量中基变量以外的变量称为非基变量。第54页/共113页2023/4/2255基本解 对于某一确定的基，令所有非基变量为0，由约束方程组AX=b可解出m个基变量的唯一解，称为一个基本解。第55页/共113页2023/4/2256基本可行解 满足非负条件的基本解

37、，称为基本可行解，基本可行解对应于凸多边形的项点。第56页/共113页2023/4/2257练习：已知线性规划问题问：问：中哪一个是基本可行解？中哪一个是基本可行解？第57页/共113页2023/4/2258二、线性规划之解的概念 2、线性规划问题基本定理定理定理1.1.若线性规划问题存在可行域，则其可行域一定若线性规划问题存在可行域，则其可行域一定 是凸集。是凸集。定理定理2.2.线性规划问题的基可行解对应可行域的顶点。线性规划问题的基可行解对应可行域的顶点。定理定理3.3.若可行域有界，线性规划的目标函数一定可以若可行域有界，线性规划的目标函数一定可以 在可行域的顶点上达到最优。在可行域的

38、顶点上达到最优。定理定理4.4.线性规划如果有可行解，则一定有基可行解；线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。如果有最优解，则一定有基可行解是最优解。第58页/共113页2023/4/2259二、线性规划之解的概念 3、线性规划问题的解题思路 首先，找到一个初始基可行解，也就是找到一个初始可行基，想办法判断这个基可行解是不是最优解。如果是最优解，就得到这个线性规划问题的最优解；如果判断出不是最优解，就想法由这个可行基按一定规则变化到下一个可行基，然后再判断新得到的基可行解是不是最优解；如果还不是，再接着进行下一个可行基变化，直到得到最优解。第59页/共

39、113页2023/4/2260求解线性规划问题的思路单纯形法求初始基本可行解判断该可行解是否最优寻找新的基本可行解结束是否19471947年，美国斯坦福大学丹捷格教授发明单纯形法。年，美国斯坦福大学丹捷格教授发明单纯形法。第60页/共113页2023/4/2261一、线性规划问题的代数解法（教材第32页例题）解：解：(一一)标准化：标准化：(二二)求初始基可行解求初始基可行解第61页/共113页2023/4/2262 令非基变量：令非基变量：x x1 1=x x2 2=0=0，得到初始基可行解：得到初始基可行解：X X(0)(0)=(0,0,16,10,32)=(0,0,16,10,32)T

40、T 此时，目标函数值：此时，目标函数值：Z Z(0)(0)=3=3x x1 1+5+5x x2 2+0=0+0=0目标函数用非基变量表示。目标函数用非基变量表示。(三三)判优判优 对于对于Z Z(0)(0)=3=3x x1 1+5+5x x2 2，若，若x x1 1或或x x2 2从从0 0变为正数，变为正数，则目标函数值会增加，因此可判断则目标函数值会增加，因此可判断X X(0)(0)一定不是最优一定不是最优解。解。(X(X(0)(0)XX*)第62页/共113页2023/4/2263Z Z(0)(0)=3=3x x1 1+5 5x x2 2(四四)方案调整方案调整(换基换基)寻找一个新的基

41、可行解，使目标函数寻找一个新的基可行解，使目标函数值得到改善。值得到改善。选择入基变量选择入基变量 寻找使目标函数增加量最大的非基寻找使目标函数增加量最大的非基变量入基，即目标函数中系数最大的变变量入基，即目标函数中系数最大的变量。量。(x x2 2)选择出基变量选择出基变量 为什么要选择原基变量出基？为什么要选择原基变量出基？要求决策变量非负，因此有：要求决策变量非负，因此有：说明说明x x2 2最大取值是最大取值是5 5，且当，且当x x2 2=5=5时，时，x x4 4=0 0，即，即x x4 4出基出基。(x x4 4)第63页/共113页2023/4/2264(五五)求新的基可行解求

42、新的基可行解 此时，基变量为此时，基变量为x x3 3、x x2 2和和x x5 5，非基变量为，非基变量为x x1 1和和x x4 4。用非基变量表示基变量：用非基变量表示基变量：用用x x4 4表示表示x x2 2，x x2 2=5=5 (x x4 4/2)/2)，用用x x4 4表示表示x x5 5，x x5 5=12 3=12 3x x1 1+2 2x x4 4。令非基令非基变量变量 x x1 1=x x4 4=0=0，则，则 X X(1)(1)=(0,5,16,0,12)=(0,5,16,0,12)T T。第64页/共113页2023/4/2265(六六)判优判优(检验检验)将式将式

43、(4)(4)代入目标函数，目的：用非代入目标函数，目的：用非基变量表示目标函数，得到新的目标函数值：基变量表示目标函数，得到新的目标函数值：Z Z(1)(1)=3 3x x1 1+5+5x x2 2=3=3x x1 1+5(5 +5(5 x x4 4/2)/2)=3 =3x x1 1 5 5x x4 4/2/2 +2525 非基变量非基变量x x1 1的系数为的系数为3 3，大于零，可见，大于零，可见，如果如果x x1 1 能从能从非基变量变为基变量，即变为正数，则目标非基变量变为基变量，即变为正数，则目标函数值会增加，因此函数值会增加，因此X X(1)(1)=(0,5,16,0,12)=(0

44、,5,16,0,12)T T 不是最不是最优解。优解。第65页/共113页2023/4/2266Z Z(1)(1)=3 3x x1 1 5 5x x4 4/2/2 +25+25(七七)换基换基 当当x x1 1=4 4时，时，x x5 5=0=0 即：当即：当x x1 1 入基入基，x x5 5 出出基。基。第66页/共113页2023/4/2267(八八)求新的基可行解求新的基可行解 此时，基变量为此时，基变量为x x3 3、x x2 2和和x x1 1，非基变量，非基变量为为x x4 4和和x x5 5。用非基变量表示基变量：用非基变量表示基变量：x x1 1=4+2=4+2x x4 4/

45、3 /3 x x5 5/3/3 ，x x3 3=8 4=8 4x x4 4/3/3 +2+2x x5 5/3/3。令非基令非基变量变量 x x4 4=x x5 5=0=0，则，则 X X(2)(2)=(4,5,8,0,0)=(4,5,8,0,0)T T。第67页/共113页2023/4/2268 松弛变量松弛变量x x3 3=8=8 说明第一项资源有剩余，资源相对宽松，这就是说明第一项资源有剩余，资源相对宽松，这就是松驰变量的经济含义。松驰变量的经济含义。(九九)判优判优(检验检验)非基变量非基变量x x4 4和和x x5 5的系数均的系数均为负值，为负值，如果如果x x4 4 和和x x5

46、5从从非基变非基变量变为基变量，即从零变为正量变为基变量，即从零变为正数，则目标函数值会减少，因数，则目标函数值会减少，因此此X X(2)(2)=(4,5,8,0,0)=(4,5,8,0,0)T T 是最优是最优解，目标函数最优值解，目标函数最优值Z Z*=37=37。第68页/共113页2023/4/2269求解过程求解过程(换基迭代过程换基迭代过程)初始基初始基初始基可行解：初始基可行解：X X(0)(0)=(0,0,16,10,32)=(0,0,16,10,32)T T Z Z(0)(0)=0=0新的可行基新的可行基新的基可行解：新的基可行解：X X(1)(1)=(0,5,6,0,12)

47、=(0,5,6,0,12)T T Z Z(1)(1)=25=25最最优优基基最优解：最优解：X X*=(4,5,8,0,0)=(4,5,8,0,0)T T Z Z*=37=37第69页/共113页2023/4/2270 单纯形法求解线性规划问题的步骤：(1)求出初始基本可行解(标准化、单位基)；(2)最优性检验(非基变量检验数非正时停止，否则进入下一步)；(3)换基(迭代)：确定入基变量 确定出基变量 初等变换，求出新的基本可行解；(4)重复步骤(2)、(3)，直到求出最优解。第70页/共113页2023/4/2271单纯形法求解步骤举例 maxZ=3x1+5x2+0 x3+0 x4+0 x5

48、 2x1 +x3 =16 2x2 +x4 =10 3x1+4x2 +x5=32 Cj比比值值CBXBb检验数检验数 jx1x2x3x4x535000162010010020103234001x3x4x5000035000-10/2=532/4=8第71页/共113页2023/4/2272162010050101/2012300-21x3x2x5050300-5/205-4Cj比比值值CBXBb检验数检验数 jx1x2x3x4x535000检验数检验数 j80014/3-2/350101/204100-2/31/3x3x2x1053000-1/2-1最优解:X*=(4,5,8,0,0)T，Z*=

49、37第72页/共113页2023/4/2273单纯形法的管理启示2x1=162x2=103x1+4x2=32x1x24812590 0A AB BC(4,5C(4,5)D DX0=(0,0,10,10,32)TX1=(0,5,16,0,12)TX1=(4,5,8,0,0)T 在管理过程中，把现有方案作为初始方案，找到最急需要改进的某个问题和改进方向，一次做好某个主要问题的解决与改进；一次只解决和改进一个问题的难度最小；解决之后，再寻求可以改进的其它地方，再次改进，不断地追求更优。第73页/共113页2023/4/2274单纯形法原理(1)举例说明ppt52页第74页/共113页2023/4/2

50、275单纯形法原理(2)非基变量检验数 令非基变量等于0，则第75页/共113页2023/4/2276CjCBCNCBXBbXBXN0XBbBNjCBCNCBXBbXBXNCBXBB-1bEB-1Nj0CN CBB-1N单纯形法原理(单纯形表)第76页/共113页2023/4/2277例 求解下列线性规划问题解：引入松驰变量x3,x4,x5，化为标准形式：第77页/共113页2023/4/2278 cj 2 5 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 4 3 8 1 0 1 0 0 0 1 0 1 0 1 2 0 0 1 j 0 2 5 0 0