4运筹学B第1章线性规划.ppt

《4运筹学B第1章线性规划.ppt》由会员分享，可在线阅读，更多相关《4运筹学B第1章线性规划.ppt（114页珍藏版）》请在三一办公上搜索。

1、第1章 线性规划,2023/5/25,2,第1章 线性规划,Sub title,内容提要,第一节 线性规划的一般模型一、线性规划模型的举例二、LP模型的要素及特征三、线性规划的图解方法四、线性规划解的可能性第二节 线性规划的单纯形法一、线性规划的标准型式二、线性规划之解的概念三、单纯形法的基本原理,2023/5/25,3,第一节 线性规划的一般模型,线性规划(Linear Programming，LP)是运筹学的重要分支之一，研究较早、发展较快、方法较成熟，而且是众多分支的基础，借助计算机计算更方便，应用更广泛。,线性规划通常研究资源的最优利用、设备最佳运行以及费用最低等问题。例如，当任务或目

2、标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大）。,2023/5/25,4,【例】生产计划问题。某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要在设备A、B上加工，需要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表1.1所示。已知在计划期内设备的加工能力各为200小时，可供材料分别为360、300公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为40、30、50元，假定市场需求无限制。问：企业决策者应

3、如何安排生产计划，使企业在计划期内总的利润最大？,第一节 线性规划的一般模型,一、线性规划模型的举例,2023/5/25,5,表1.1 某企业单位产品资源消耗及利润,x1,x1,x1,x1,x1,x2,x2,x2,x2,x2,x3,x3,x3,x3,x3,2023/5/25,6,【解】设x1、x2、x3 为甲、乙、丙三种产品的产量，则该线性规划问题的数学模型为：,最优解：X*=(50,30,10)T，Z*=3400，即在计划期内甲、乙、丙产量分别为50、30和10件，利润最大，为3400元。,注意：最优解的表达方式！,2023/5/25,7,二、线性规划的三个要素,第一节 线性规划的一般模型,

4、决策变量（一组）决策问题待定的量值取值要求非负约束条件（一组）任何管理决策问题都是限定在一定的条件下求解把各种限制条件表示为一组等式或不等式称约束条件约束条件是决策方案可行的保障约束条件是决策变量的线性函数目标函数（一个）衡量决策优劣的准则，如时间最省、利润最大、成本最低目标函数是决策变量的线性函数有的目标要实现极大，有的则要求极小,2023/5/25,8,练习1.1 某厂生产甲、乙两种产品，生产工艺路线为：各自的零部件分别在设备A、B加工，最后都需在设备C上装配。经测算得到相关数据如下表所示，单位甲、乙产品的销售价格分别为73和75元。问应如何制定生产计划，才能使总利润为最大？,x1,x1,

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

6、设备上加工，单位产品加工所需工时、销售后能获得的利润及设备有效工时数见下表。问：如何安排生产计划，才能使该厂获得总利润最大？,解:设甲、乙产品产量分别 为x1、x2 公斤，设总利润为Z，则：max Z=70 x130 x2,设备可用工时数限制 3x1+9x2 540 5x1+5x2 450 9x1+3x2 720,max Z=70 x130 x2 3x1+9x2 540 s.t.5x1+5x2 450 9x1+3x2 720 x1,x2 0,2023/5/25,11,线性规划的数学模型由,决策变量 Decision variables 目标函数 Objective function 构成，称为

7、三要素。约束条件 Constraints,其主要特征是：1.解决的问题是规划问题；2解决问题的目标函数是多个决策变量的 线性函数，通常是求最大值或最小值；3解决问题的约束条件是多个决策变量 的线性不等式或等式。,怎样辨别一个模型是线性规划模型？,2023/5/25,12,二、线性规划模型的举例,2、物资运输问题,例：某产品商有三个供货源A1、A2、A3，其经销商有4个（需求市场）B1、B2、B3、B4。已知各厂的产量、各经销商的销售量及从 Ai 到 Bj 的单位运费为Cij。问如何调配运输方案，使总运费最小？,x11,x12,x13,x14,x21,x22,x23,x24,x31,x32,x3

8、3,x34,产销平衡(产量等于销量),2023/5/25,13,(1)决策变量：设从 Ai 到 Bj 的运输量为 xij，(2)目标函数：运费最小的目标函数为：minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34(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,非

9、负约束 xij0(i=1,2,3；j=1,2,3,4)4.5,线性规划的数学模型由三个要素组成：,2023/5/25,14,【练习】现有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5(万吨)，现将粮食运往B1，B2，B3，B4四个地区，其需求量分别为5，7，8，3(万吨)。产粮地到需求地的运价(元/吨)如下表所示，问如何安排一个运输计划，使总的运输费用最少？,2023/5/25,15,解：设 xij(i=1,2,3；j=1,2,3,4)为 i 个产粮地运往第 j 个需求地的运输量，这样得到下列运输问题的数学模型：,运输量应大于或等于零（非负),2023/5/25,16,3、产品配比问

10、题,例：用浓度45%和92%的硫酸配置100吨浓度80%的硫酸，已经两种浓度硫酸的单价为每吨30和80元，问如何配置费用最小？,决策变量：需要45%和92%的硫酸分别为 x1 和 x2 吨目标函数：min Z=30 x1+80 x2约束条件：,非负约束：x1 0，x2 0,2023/5/25,17,若有5种不同浓度的硫酸可选(30%,45%,73%,85%,92%)会如何呢？,5种硫酸数量分别为 x1、x2、x3、x4、x5，有：,若5种硫酸价格分别为400,700,1400,1900,2500元/t，则：,2023/5/25,18,练习：某糖果厂用原料A，B，C加工成三种不同牌号的糖果甲、乙

11、、丙。已知各种糖果的中A，B，C的含量要求，原料成本，各种原料每月的限制用量，三种牌号糖果的单位加工费及售价如下表所示。,问该厂每月生产这三种牌号糖果各多少kg，利润最大？,2023/5/25,19,解：设xij为生产第j种糖果使用的第i种原料的数量，则该问题的数学模型为：,最优解：,即该厂每月应生产甲种牌号糖果906.67kg，乙种牌号糖果4793.33kg，利润最大为5450元。,2023/5/25,20,练习：生产某一机床需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是2.9、2.1和1.5m，这些轴需要用同一种圆钢切割而成，圆钢长度为7.4m。现在要制造100台机床，问：最少要用

12、多少圆钢来生产这些轴？(假设切割损失不计),解：1、设一根圆钢切割成甲、乙、丙三种轴的根数分别为y1,y2,y3,则切割方式可用不等式2.9y1+2.1y2+1.5y37.4表示，求这个不等式关于y1，y2，y3的非负整数解。例如：y1=2，y2=0，则 y3 只能为1，余料为0.1。像这样的非负整数解共有8组，也就是有8种下料方式，如表1.4所示。,2、建立线性规划数学模型。设xj(j=1,2,8)为第 j 种下料方案所用圆钢的根数。,4、合理下料问题,2023/5/25,21,min Z=x1+x2+x3+x4+x5+x6+x7+x8,(x1=10,x2=50,x4=30,16m),202

13、3/5/25,22,5、投资问题,某投资公司在第一年初有100万元资金，假设每年都有如下的投资方案：第一年初投入一笔资金，第二年初又继续投入此资金的50%，第三年初就可回收第一年初投入资金的两倍。问：该投资公司应如何确定投资策略才能使第六年初所拥有的资金最多？,解：设x1为第一年的投资，x2为第一年的保留资金，则：,x1+x2=100,第二年：设x3为第二年新的投资，x4为第二年的保留资金，则：,2023/5/25,23,第三年：设 x5 为新的投资，x6 为第三年的保留资金；,第四年：设新的投资 x7，第四年的保留资金 x8；,第五年：设 x9 为第五年的保留资金。根据题意，第五年初不再进行

14、新的投资，因为这笔投资要到第七年初才能收回。,约束条件 每年应满足如下的关系：追加投资金额+新投资金额+保留资金=可利用的资金总额,2023/5/25,24,X*(27.64,72.36,58.54,0,26.02,0,104.06,0,0)T，Z*208.12。,到第六年初，实有资金总额为x9+2x7，整理后得到下列线性规划模型：,max Z=2x7+x9,第一年新投资27.64万元、第二年新投资58.54万元、第三年新投资26.02万元、第四年新投资104.06万元，才能使第六年初拥有资金最多，为208.12万元。,2023/5/25,25,思考题：某人有30万元资金，在今后的三年内有以下

15、4个 投资项目可供参考，假设有钱就会用于投资。1.三年内的每年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一年的投资；2.只允许第一年年初投入，第二年末可收回，本利合计为投资额的150%，但此类投资额不超过15万元；3.第二年初允许投资，可于第三年末收回，本利合计为投资额的160%，这类投资限额20万元；4.第三年初允许投资，一年回收，可获利40%，投资限额为10万元。试确定一个第三年末本利和为最大的投资计划？,2023/5/25,26,对于约束条件：,第1年，可用于项目1和2投资：x11+x12=300000,第2年，可用于项目1和3投资，投资额为x11的本利和：x21+x23

16、=1.2 x11,第3年，可用于项目1和4投资，投资额x21和x12有关：x31+x34=1.2 x21+1.5 x12,投资限额：x12 150000;x23 200000;x34 10000,非负约束：xij 0(i=1,2,3;j=1,2,3,4),对于目标函数，只需考虑第3年末：,项目1：x31 1.2 x31(本利和)；,项目2：0；,项目3：x23 1.6 x23(本利和)；,项目4：x34 1.4x34(本利和)；,maxZ=1.2 x31+1.6 x23+1.4 x34,2023/5/25,27,解：设xij为第 i 年初投放到 j 项目的资金额(元)，其数学模型为：,maxZ

17、=1.2 x31+1.6 x23+1.4 x34,注意本题条件：有钱就会用于投资，即：可利用的资金=投资金额，据此建立约束等式。,x11+x12=300000 x21+x23=1.2 x11x31+x34=1.2 x21+1.5 x12x12 150000 x23 200000 x34 10000 xij 0(i=1,2,3;j=1,2,3,4),2023/5/25,28,2023/5/25,29,第一节 线性规划的一般模型,用一组非负决策变量表示的一个决策问题；存在一组等式或不等式的线性约束条件；有一个希望达到的目标，可表示成决策变量的极值线性函数。,为了书写方便，上式也可简写：,2023/

18、5/25,30,一般地，xj0，但有时xj0或xj无符号限制。,2023/5/25,31,线性规划图解法,1、概念：利用几何图形求解两个变量线性规划问题的方法。,3、求解步骤：,第一步：建立平面直角坐标系；,第三步：在可行域内平移目标函数等值线，确定最优解及最优目标函数值。,2、特点：简单、直观，但只适用于两个变量的LP问题。,第二步：根据约束条件画出可行域；,2023/5/25,32,1、线性规划的可行域,可行域：满足所有约束条件的解的集合，即由所有约束条件共同围成的区域。,maxZ=3x1+5x2 2x1 16 2x2 10 3x1+4x2 32 x10,x20,s.t.,2023/5/2

19、5,33,2、线性规划的最优解,目标函数 Z=3x1+5x2 代表以 Z 为参数的一族平行线。,(4,5),X*=(4,5)T,Z*=37,2023/5/25,34,x1,x2,O,10,20,30,40,10,20,30,40,(15,10),最优解 X*=(15,10)T,最优值 Z*=85,2023/5/25,35,2,4,6,x1,x2,2,4,6,最优解 X*=(3,1)T最优值 Z*=5,(3,1),min Z=x1+2x2,2023/5/25,36,3、线性规划解的特性,由线性不等式组成的可行域是凸多边形(凸集)凸集：对于某一集合内部任意两点连线上的点都属于这个集合，我们就称这个

20、集合为凸集。,线性规划问题的可行域具有有限个顶点。目标函数最优值一定在可行域的边界(顶点)达到，而不可能在其区域的内部。,2023/5/25,37,凸集的概念,设K为n维欧氏空间的一个点集，若K中任意两个点X1和X2连线上的所有点都属于K，则称K为凸集。,X2,X1,X,设X(x1,x2,xn);X1(u1,u2,un);X2(v1,v2,vn),2023/5/25,38,四、线性规划解的可能性,1、唯一最优解,2、多重最优解/无穷多最优解,当乙产品市场价格从75元下降到74元时，模型变为：,2023/5/25,39,2,4,6,x1,x2,2,4,6,X(2)(3,1)T,X(1)(1,3)

21、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,2023/5/25,40,3、无界解可行域无界，目标值无限增大(缺乏必要约束),2023/5/25,41,2,4,6,x1,x2,2,4,6,(1,2),无界解,max Z=x1+2x2,2023/5/25,42,4、无可行解：线性规划问题的可行域是空集(约束条件相互矛盾),2023/5/25,43,x1,x2,O,10,20,30,40,10,20,30,40,50,50,无可行解,max Z=10 x1+4x

22、2,2023/5/25,44,20130312 作业：用图解法求解以下问题,（1）,（2）,（3）,（4）,2023/5/25,45,一、线性规划的标准型,1、标准型表达方式,(1)代数式：,(2)向量式：,(3)矩阵式：,A：技术系数矩阵，简称系数矩阵；b：可用的资源量，称资源向量；C：决策变量对目标的贡献，称价值向量；X：决策变量。,第二节 线性规划问题模型,2023/5/25,46,通常X记为：，其中，为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般情况mn，且r()m。,其中:,2023/5/25,47,2、标准型转换方法,(1)“目标函数求最大值”。如果极小化原问题

23、minZ=CX，则令 Z=Z，转为求 maxZ=CX。注意：求解后还原。（2）(2)“资源限量非负”。若某个 bi 0，则将该约束两端同乘“1”，以满足非负性的要求。（4）(3)“约束条件为等式”。对于“”型约束，则在“”左端加上一个非负松弛变量(slack variable)，使其为等式。对于“”型约束，则在“”左端减去一个非负剩余变量(Surplus variable)，使其为等式。（3）(4)“决策变量非负”。若某决策变量 xk 为“取值无约束”(无符号限制)，令：xk=xk xk，(xk0,xk 0)。（1）,2023/5/25,48,【例】将下列线性规划转化为标准型(标准形式)？,【

24、解】(1)决策变量取值 x3 无符号要求(取值无约束)，即x3取正值也可取负值，标准型中要求变量取值为非负，所以可令：,2023/5/25,49,(3)第二个约束条件是“号”，在“号”左端减去剩余变量x5，x50，x5也称松驰变量,(2)第一个约束条件是“号”，在“”左端加入松驰变量 x4，x40，即化为等式；,(4)第三个约束条件是“号”且常数项为负数，因此在“”左边加入松驰变量x6，x60，同时不等式两端同乘以“1”。,(5)目标函数是最小值，令Z=Z,得到max Z=max(Z)，即当Z达到最小值时Z达到最大值，反之亦然。,(1)x3 取值无约束，令 x3=x3 x3，x3,x3 0。,

25、2023/5/25,50,标准型为：,2023/5/25,51,将例1.1的线性规划问题的一般形式化为标准型？,第二节 线性规划问题模型,2023/5/25,52,第二节 线性规划问题模型,2023/5/25,53,练习：将下列线性规划模型转化为标准型？,min Z=3x1 x24x3 x1 2x2+5x3 0 2x1+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

26、+5(x3 x3)x4=0 2x1 x2 3(x3 3x3)+x5=450 3x1+x2=0 x1,x2,x3,x3,x4,x5 0,作业：教材42页,第8题,2023/5/25,54,二、线性规划之解的概念,基矩阵：一个非奇异的子矩阵（向量线性无关）。矩阵A 中任意一个 m 列的线性无关子矩阵 B，称为一个基(矩阵)。组成基的列向量称为基向量，用 Pj 表示(i=1,2,m)。基变量：与基向量 Pj 相对应的变量 xj 称为基变量。其余的 n m 个变量称为非基变量(基矩阵以外的列向量对应变量)。,1、线性规划解之关系,基(本)解：令所有非基变量等于零，得出的唯一解。,基变量是x3,x4,x

27、5非基变量是x1,x2令非基变量 x1=x2=0，基变量取值唯一确定：x3=16，x4=10，x5=32得到一个基解：X=(0,0,16,10,32)T,2023/5/25,55,重要概念,可行解：满足约束条件AX=b和X0的解。基(本)解：令所有非基变量等于零，得出的唯一解。基(本)可行解：满足X0的基解。可行基：基可行解对应的基矩阵。最优解：使目标函数最优的基可行解，称为最优解。最优基：最优解对应的基矩阵，称为最优基。,2023/5/25,56,基的概念,假设线性规划问题模型系数矩阵为m行、n列(mn)，则系数矩阵中秩为m的m行m列子矩阵，称为基矩阵，简称基。,基中的列向量对应的变量称为基

28、变量，决策变量中基变量以外的变量称为非基变量。,2023/5/25,57,基本解,对于某一确定的基，令所有非基变量为0，由约束方程组AX=b可解出m个基变量的唯一解，称为一个基本解。,2023/5/25,58,基本可行解,满足非负条件的基本解，称为基本可行解，基本可行解对应于凸多边形的项点。,2023/5/25,59,练习：已知线性规划问题,问：,中哪一个是基本可行解？,2023/5/25,60,二、线性规划之解的概念,2、线性规划问题基本定理,定理1.若线性规划问题存在可行域，则其可行域一定 是凸集。定理2.线性规划问题的基可行解对应可行域的顶点。定理3.若可行域有界，线性规划的目标函数一定

29、可以 在可行域的顶点上达到最优。定理4.线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。,2023/5/25,61,二、线性规划之解的概念,3、线性规划问题的解题思路,首先，找到一个初始基可行解，也就是找到一个初始可行基，想办法判断这个基可行解是不是最优解。如果是最优解，就得到这个线性规划问题的最优解；如果判断出不是最优解，就想法由这个可行基按一定规则变化到下一个可行基，然后再判断新得到的基可行解是不是最优解；如果还不是，再接着进行下一个可行基变化，直到得到最优解。,2023/5/25,62,求解线性规划问题的思路单纯形法,1947年，美国斯坦福大学丹捷格教授发

30、明单纯形法。,2023/5/25,63,一、线性规划问题的代数解法（教材第32页例题）,解：(一)标准化：,(二)求初始基可行解,2023/5/25,64,令非基变量：x1=x2=0，得到初始基可行解：X(0)=(0,0,16,10,32)T,此时，目标函数值：Z(0)=3x1+5x2+0=0目标函数用非基变量表示。,(三)判优,对于Z(0)=3x1+5x2，若x1或x2从0变为正数，则目标函数值会增加，因此可判断X(0)一定不是最优解。(X(0)X*),2023/5/25,65,Z(0)=3x1+5x2,(四)方案调整(换基),寻找一个新的基可行解，使目标函数值得到改善。,选择入基变量 寻找

31、使目标函数增加量最大的非基变量入基，即目标函数中系数最大的变量。(x2),选择出基变量 为什么要选择原基变量出基？,要求决策变量非负，因此有：,说明x2最大取值是5，且当x2=5时，x4=0，即x4出基。(x4),2023/5/25,66,(五)求新的基可行解,此时，基变量为x3、x2和x5，非基变量为x1和x4。,用非基变量表示基变量：用x4表示x2，x2=5(x4/2)，用x4表示x5，x5=12 3x1+2x4。,令非基变量 x1=x4=0，则 X(1)=(0,5,16,0,12)T。,2023/5/25,67,(六)判优(检验),将式(4)代入目标函数，目的：用非基变量表示目标函数，得

32、到新的目标函数值：Z(1)=3x1+5x2=3x1+5(5 x4/2)=3x1 5x4/2+25,非基变量x1的系数为3，大于零，可见，如果x1 能从非基变量变为基变量，即变为正数，则目标函数值会增加，因此X(1)=(0,5,16,0,12)T 不是最优解。,2023/5/25,68,Z(1)=3x1 5x4/2+25,(七)换基,当x1=4时，x5=0,即：当x1 入基，x5 出基。,2023/5/25,69,(八)求新的基可行解,此时，基变量为x3、x2和x1，非基变量为x4和x5。,用非基变量表示基变量：x1=4+2x4/3 x5/3，x3=8 4x4/3+2x5/3。,令非基变量 x4

33、=x5=0，则 X(2)=(4,5,8,0,0)T。,2023/5/25,70,松弛变量x3=8,说明第一项资源有剩余，资源相对宽松，这就是松驰变量的经济含义。,(九)判优(检验),非基变量x4和x5的系数均为负值，如果x4 和x5从非基变量变为基变量，即从零变为正数，则目标函数值会减少，因此X(2)=(4,5,8,0,0)T 是最优解，目标函数最优值Z*=37。,2023/5/25,71,求解过程(换基迭代过程),初始基,初始基可行解：X(0)=(0,0,16,10,32)T Z(0)=0,新的可行基,新的基可行解：X(1)=(0,5,6,0,12)T Z(1)=25,最优基,最优解：X*=

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

35、25,75,单纯形法的管理启示,2x1=16,X0=(0,0,10,10,32)T,X1=(0,5,16,0,12)T,X1=(4,5,8,0,0)T,在管理过程中，把现有方案作为初始方案，找到最急需要改进的某个问题和改进方向，一次做好某个主要问题的解决与改进；一次只解决和改进一个问题的难度最小；解决之后，再寻求可以改进的其它地方，再次改进，不断地追求更优。,2023/5/25,76,单纯形法原理(1)举例说明ppt52页,2023/5/25,77,单纯形法原理(2),非基变量检验数,令非基变量等于0，则,2023/5/25,78,单纯形法原理(单纯形表),2023/5/25,79,例 求解下

36、列线性规划问题,解：引入松驰变量x3,x4,x5，化为标准形式：,2023/5/25,80,由于x1，x2的检验数均为正，且x2的检验数k最大，选取x2为入基变量；再按最小比值=min(-,3/1,8/2)=3，选取x4为出基变量。,x2,5,2,1,0,0,-2,1,2,0,0,-5,0,15,2023/5/25,81,由于x1检验数为正，选取x1为入基变量；再按最小比值=min（4/1,-,2/1）=2，选取x5为出基变量。,x1,2,2,0,0,1,2,-1,0,0,0,-1,-2,19,2023/5/25,82,初始基本可行解：X(0)=(0,0,4,3,8)T，Z(0)=0,新的基本

37、可行解：X(1)=(0,3,4,0,2)T，Z(1)=15,新的基本可行解：X(2)=(2,3,2,0,0)T，Z(2)=19,判别定理 1：在单纯形表中（目标函数求max），若所有非基变量的检验数小于零，且XB取值非负，则线性规划问题具有唯一最优解。,2023/5/25,83,图解法求解结果：,A(0,0),A：X(0)=(0,0,4,3,8)T，Z(0)=0,B(0,3),B：X(1)=(0,3,4,0,2)T，Z(1)=15,C,C：X*=(2,3,2,0,0)T，Z*=19,D(4,2),E(4,0),0,2023/5/25,84,例 求解下列线性规划问题,解：引进松驰变量x3,x4,

38、x5，化为标准形式：,2023/5/25,85,x2,4,2,-1/2,1,1/2,0,0,6,2,0,-1,1,0,4,1/2,0,1/2,0,1,4,0,-2,0,0,8,2023/5/25,86,x1,2,3,1,0,-1/2,1/2,0,0,1,1/4,1/4,0,7/2,0,0,3/4,-1/4,1,5/2,0,0,0,-2,0,20,2023/5/25,87,x3,0,10/3,0,0,1,-1/3,4/3,8/3,0,1,0,1/3,-1/3,14/3,1,0,0,1/3,2/3,0,0,0,-2,0,20,2023/5/25,88,初始基本可行解：X(0)=(0,0,4,10,

39、2)T，Z(0)=0,新的基本可行解：X(1)=(0,2,0,6,4)T，Z(1)=8,新的基本可行解：X(2)=(3,7/2,0,0,5/2)T，Z(2)=20,新的基本可行解：X(3)=(14/3,8/3,10/3,0,0)T，Z(3)=20,判别定理 2：在单纯形表中，若所有非基变量的检验数小于等于零，其中某个检验数等于零，则线性规划问题具有无穷多最优解(多重最优解)。,2023/5/25,89,图解法求解结果：,A(0,0),A：X(0)=(0,0,4,10,2)T，Z(0)=0,B(0,2),B：X(1)=(0,2,0,6,4)T，Z(1)=8,C(3,7/2),C：X*=(3,7/

40、2,0,0,5/2)T，Z*=20,D(14/3,8/3),E(2,0),D：X*=(14/3,8/3,10/3,0,0)T，Z*=20,2023/5/25,90,例 求解下列线性规划问题,解：引入松驰变量x3,x4，标准化：,2023/5/25,91,不满足出基变量确定法则：,虽然，不能确定x3和x4哪个变量出基，但无论哪个变量出基，都必须满足：x30，x40。因x2入基，所以一定满足：x20。,说明x2可以无限增大，所以目标函数值可以无限增大。,无界解,2023/5/25,92,图解法求解结果：,A(0,0),无界解,2023/5/25,93,练习 求解下列线性规划问题,解：引进松驰变量x

41、3,x4，化为标准形式：,从标准形中可看出存在可行基B=(P3，P4)=E，基变量为X3，X4；非基变量为X1，X2。建立初始单纯形表得：,2023/5/25,94,由于x1，x2的检验数均为非负，且x1的检验数绝对值最大，选取x1为进基变量；再按最小比值=min（24/2，26/3）=26/3，选取x4为出基变量，进行换基迭代。,2023/5/25,95,表中最后一行的所有检验数均为非正，表明目标函数已达到最大值，上表为最优单纯形表。从表中可得到最优解为：X*=(x1,x2,x3,x4)T=(6,4,0,0)T，最优值为：Z*=36。,2023/5/25,96,20130319 作业：用单纯

42、形法求解以下问题,（1）,（2）,（3）,（4）,2023/5/25,97,练习：已知某线性规划用单纯形法求得的某两步迭代表如下，请将表中空白处填上适当的数字。,2023/5/25,98,思考题 已知线性规划问题：,其中b1,b2是常数，且已知此问题的最终单纯形表如下。试确定表中所有的参数？,e=0,d=5,b=5,c=10,a=23,b1=30,b2=40,2023/5/25,99,思考：某极大化线性规划问题的单纯形表如下，问表中参数 a1,a2,a3,d,1,2 为何取值范围时，下列结论成立？,(1)表中解为唯一最优解：(2)表中解为无穷多最优解：(3)该问题具有无界解：(4)表中解为退化

43、的基解：(5)表中解为不可行解：(6)x1入基，x6出基：,10,20,12=0,d 0,1 0,2 0,d 0,2 0,a1 0,d 0,1 0,2 0,d=0,d 0,1 0,d 0,d/43/a3,a3 0,2023/5/25,100,已知线性规划问题的最优单纯形表如下，求初始单纯形表中的参数C,A,b 以及最优基B？,2023/5/25,101,求解结果：,2023/5/25,102,大M法（大M单纯形法）,通过添加人工变量构成单位基，进而求解线性规划问题的方法。,2023/5/25,103,例 求解下列线性规划问题,解：引进松驰变量x4,x5，化为标准形式：,2023/5/25,10

44、4,加入变量x6,x7，加入参数M，M为任意大的正数,2023/5/25,105,x3,-1,10,3,-2,0,1,0,0,-1,1,0,1,0,0,-1,1,-2,1,-1+M,0,0,-M,0,1-3M,2023/5/25,106,x2,-1,12,3,0,0,1,-2,2,-5,1,-2,0,1,0,0,0,1,1,0,0,0,-1,1-M,-1-M,2023/5/25,107,x1,3,4,1,0,0,1/3,-2/3,2/3,-5/3,9,0,0,1,2/3,-4/3,4/3,-7/3,0,0,0,-1/3,-1/3,1/3-M,2/3-M,2,X*=(4,1,9,0,0,0,0)

45、T,Z*=2,基变量中不含人工变量，且所有非基变量的检验数均为负，所以该问题具有唯一最优解。,2023/5/25,108,大M法可能的求解结果：,(1)基变量中不含人工变量；,(2)基变量中含人工变量，但基变量取值为零；,(3)基变量中含人工变量，但基变量取值不为零。,注意：只在前两种情况下，线性规划问题有最优解。,2023/5/25,109,练习 用大M法求解下列线性规划问题,解：引入松驰变量x4，化为标准形式：,2023/5/25,110,加入变量x5,x6，加入参数M，M为任意大的正数,2023/5/25,111,x1,1,2,0,-4,2,1,-1,1,0,-10-4M,4+2M,1+

46、M,-1-2M,0,x3,3,1,0,-2,1,1/2,-1/2,1/2,3,1,0,0,-1/2,1/2,1/2,0,-2,0,-1,1-M,-2-M,6,2023/5/25,112,基变量中不含人工变量，且所有非基变量的检验数均为负，所以该问题具有唯一最优解。,X*=(3,0,1,0,0,0)T,Z*=6,作业：教材42页，第11题,2023/5/25,113,一、线性规划问题的一般模型(问题的提出)三个要素：决策变量、目标函数、约束条件(含非负约束)。线性规划模型的一般形式与标准形式 标准形式：目标函数(max)、决策变量(0)、资源向量(0)、约束方程(=)。,本章小结,二、图解法求线性规划问题 基本步骤：建立平面直角坐标系、利用约束条件画出可行域、平移目标函数等值线得到最优值。解的形式：唯一最优解、多重最优解、无界解、无可行解。,2023/5/25,114,本章小结(续),三、单纯形法求线性规划问题,线性规划问题的一般形式转化成标准形式的步骤。标准型的表达方式：代数式、向量式、矩阵式。线性规划问题解的概念：基(矩阵)、基变量、基本解、可行解、基可行解、可行基、最优解、最优基。线性规划问题基本定理 单纯形法基本原理与一般步骤 单纯形法的表格形式(单纯形表)矩阵形式的单纯形表 大M法,