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

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

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

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

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

5、才能使总利润为最大？,x1,x1,x1,x2,x2,x2,2,0,3,0,2,4,2020/8/2,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) 使满足，使服从,2020/8/2,10,练习

6、1.2：某厂生产甲、乙两种产品，均需在A、B、C三种不同的设备上加工，单位产品加工所需工时、销售后能获得的利润及设备有效工时数见下表。问：如何安排生产计划，才能使该厂获得总利润最大？,解: 设甲、乙产品产量分别 为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,2020/8/2,11,线性规划的数学模型由,决策

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

8、运输方案，使总运费最小？,x11,x12,x13,x14,x21,x22,x23,x24,x31,x32,x33,x34,产销平衡(产量等于销量),2020/8/2,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+

9、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,线性规划的数学模型由三个要素组成：,2020/8/2,14,【练习】现有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5(万吨)，现将粮食运往B1，B2，B3，B4四个地区，其需求量分别为5，7，8，3(万吨)。产粮地到需求地的运价(元/吨)如下表所示，问如何安排一个运输计划，使总的运输费用最少？,2020/8/2,15,解：设 xij (i=1,2,3；

10、j=1,2,3,4)为 i 个产粮地运往第 j 个需求地的运输量，这样得到下列运输问题的数学模型：,运输量应大于或等于零（非负),2020/8/2,16,3、产品配比问题,例：用浓度45%和92%的硫酸配置100吨浓度80%的硫酸，已经两种浓度硫酸的单价为每吨30和80元，问如何配置费用最小？,决策变量：需要45%和92%的硫酸分别为 x1 和 x2 吨 目标函数：min Z = 30 x1 + 80 x2 约束条件：,非负约束： x1 0， x2 0,2020/8/2,17,若有5种不同浓度的硫酸可选(30%,45%,73%,85%,92%)会如何呢？,5种硫酸数量分别为 x1、x2、x3、

11、x4、x5 ，有：,若5种硫酸价格分别为400, 700, 1400, 1900, 2500元/t，则：,2020/8/2,18,练习：某糖果厂用原料A，B，C加工成三种不同牌号的糖果甲、乙、丙。已知各种糖果的中A，B，C的含量要求，原料成本，各种原料每月的限制用量，三种牌号糖果的单位加工费及售价如下表所示。,问该厂每月生产这三种牌号糖果各多少kg，利润最大？,2020/8/2,19,解：设xij为生产第j种糖果使用的第i种原料的数量，则该问题的数学模型为：,最优解：,即该厂每月应生产甲种牌号糖果906.67kg，乙种牌号糖果4793.33kg，利润最大为5450元。,2020/8/2,20,

12、练习：生产某一机床需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是2.9、2.1和1.5m，这些轴需要用同一种圆钢切割而成，圆钢长度为7.4m。现在要制造100台机床，问：最少要用多少圆钢来生产这些轴？(假设切割损失不计),解：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

13、)为第 j 种下料方案所用圆钢的根数。,4、合理下料问题,2020/8/2,21,min Z = x1+x2+x3 +x4+x5 +x6+x7 +x8,(x1=10, x2=50, x4=30, 16m),2020/8/2,22,5、投资问题,某投资公司在第一年初有100万元资金，假设每年都有如下的投资方案：第一年初投入一笔资金，第二年初又继续投入此资金的50%，第三年初就可回收第一年初投入资金的两倍。问：该投资公司应如何确定投资策略才能使第六年初所拥有的资金最多？,解：设x1为第一年的投资，x2为第一年的保留资金，则：,x1 + x2 = 100,第二年： 设x3为第二年新的投资，x4为第二

14、年的保留资金，则：,2020/8/2,23,第三年：设 x5 为新的投资，x6 为第三年的保留资金；,第四年：设新的投资 x7 ，第四年的保留资金 x8 ；,第五年：设 x9 为第五年的保留资金。根据题意，第五年初不再进行新的投资，因为这笔投资要到第七年初才能收回。,约束条件 每年应满足如下的关系： 追加投资金额 + 新投资金额 + 保留资金=可利用的资金总额,2020/8/2,24,X*(27.64, 72.36, 58.54, 0, 26.02, 0, 104.06, 0, 0)T，Z*208.12。,到第六年初，实有资金总额为x9 + 2x7，整理后得到下列线性规划模型：,max Z =

15、 2x7 + x9,第一年新投资27.64万元、第二年新投资58.54万元、第三年新投资26.02万元、第四年新投资104.06万元，才能使第六年初拥有资金最多，为208.12万元。,2020/8/2,25,思考题：某人有30万元资金，在今后的三年内有以下4个 投资项目可供参考，假设有钱就会用于投资。 1.三年内的每年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一年的投资； 2.只允许第一年年初投入，第二年末可收回，本利合计为投资额的150%，但此类投资额不超过15万元； 3.第二年初允许投资，可于第三年末收回，本利合计为投资额的160%，这类投资限额20万元； 4. 第三年初允

16、许投资，一年回收，可获利40%，投资限额为10万元。 试确定一个第三年末本利和为最大的投资计划？,2020/8/2,26,对于约束条件：,第1年，可用于项目1和2投资： x11 + x12 = 300000,第2年，可用于项目1和3投资，投资额为x11的本利和：x21 + x23 = 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 ),对于目标函数，只需考虑

17、第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,2020/8/2,27,解：设xij为第 i 年初投放到 j 项目的资金额(元)，其数学模型为：,maxZ = 1.2 x31 + 1.6 x23 + 1.4 x34,注意本题条件：有钱就会用于投资，即： 可利用的资金 = 投资金额，据此建立约束等式。,x11 + x12 = 300000 x21 + x23 = 1.2 x11 x31 + x34 = 1.2 x2

18、1 + 1.5 x12 x12 150000 x23 200000 x34 10000 xij 0 (i = 1,2,3; j = 1,2,3,4),2020/8/2,28,2020/8/2,29,第一节 线性规划的一般模型,用一组非负决策变量表示的一个决策问题； 存在一组等式或不等式的线性约束条件； 有一个希望达到的目标，可表示成决策变量的极值线性函数。,为了书写方便，上式也可简写：,2020/8/2,30,一般地，xj0，但有时xj0或xj无符号限制。,2020/8/2,31,线性规划图解法,1、概念： 利用几何图形求解两个变量线性规划问题的方法。,3、求解步骤：,第一步：建立平面直角坐标

19、系；,第三步：在可行域内平移目标函数等值线， 确定最优解及最优目标函数值。,2、特点： 简单、直观，但只适用于两个变量的LP问题。,第二步：根据约束条件画出可行域；,2020/8/2,32,1、线性规划的可行域,可行域：满足所有约束条件的解的集合， 即由所有约束条件共同围成的区域。,maxZ= 3x1 + 5x2 2x1 16 2x2 10 3x1+4x2 32 x10, x20,s.t.,2020/8/2,33,2、线性规划的最优解,目标函数 Z = 3x1 + 5x2 代表以 Z 为参数的一族平行线。,(4, 5),X*=(4, 5)T,Z*=37,2020/8/2,34,x1,x2,O,

20、10,20,30,40,10,20,30,40,(15,10),最优解 X* = (15,10)T,最优值 Z* = 85,2020/8/2,35,2,4,6,x1,x2,2,4,6,最优解 X* = (3,1)T 最优值 Z* = 5,(3,1),min Z = x1 + 2x2,2020/8/2,36,3、线性规划解的特性,由线性不等式组成的可行域是凸多边形(凸集) 凸集：对于某一集合内部任意两点连线上的点都属于这个集合，我们就称这个集合为凸集。,线性规划问题的可行域具有有限个顶点。 目标函数最优值一定在可行域的边界(顶点)达到，而不可能在其区域的内部。,2020/8/2,37,凸集的概念

21、,设K为n维欧氏空间的一个点集，若K中任意两个点X1和X2连线上的所有点都属于K，则称K为凸集。,X2,X1,X,设X(x1,x2,xn); X1(u1,u2,un); X2(v1,v2,vn),2020/8/2,38,四、线性规划解的可能性,1、唯一最优解,2、多重最优解/无穷多最优解,当乙产品市场价格从75元下降到74元时，模型变为：,2020/8/2,39,2,4,6,x1,x2,2,4,6,X(2) (3, 1)T,X(1) (1, 3)T,(5,5),min Z=5x1+5x2,具有无穷多最优解，即多重最优解, 通解为：,01,例如：当=0.5时 = (x1,x2)T = 0.5(1

22、,3)T + 0.5(3,1)T = (2,2)T,2020/8/2,40,3、无界解 可行域无界，目标值无限增大(缺乏必要约束),2020/8/2,41,2,4,6,x1,x2,2,4,6,(1,2),无界解,max Z=x1+2x2,2020/8/2,42,4、无可行解：线性规划问题的可行域是空集 (约束条件相互矛盾),2020/8/2,43,x1,x2,O,10,20,30,40,10,20,30,40,50,50,无可行解,max Z=10 x1+4x2,2020/8/2,44,20130312 作业：用图解法求解以下问题,（1）,（2）,（3）,（4）,2020/8/2,45,一、线

23、性规划的标准型,1、标准型表达方式,(1)代数式：,(2)向量式：,(3)矩阵式：,A：技术系数矩阵，简称系数矩阵； b：可用的资源量，称资源向量； C：决策变量对目标的贡献，称价值向量； X：决策变量。,第二节 线性规划问题模型,2020/8/2,46,通常X记为： ，其中，为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般情况mn，且r()m。,其中:,2020/8/2,47,2、标准型转换方法,(1) “目标函数求最大值”。如果极小化原问题minZ = CX，则令 Z = Z，转为求 maxZ = CX 。 注意：求解后还原。 （2） (2) “资源限量非负”。若某个 b

24、i 0，则将该约束两端同乘 “1” ，以满足非负性的要求。 （4） (3) “约束条件为等式”。对于 “”型约束，则在“”左端加上一个非负松弛变量(slack variable) ，使其为等式。 对于“”型约束，则在“”左端减去一个非负剩余变量(Surplus variable) ，使其为等式。 （3） (4) “决策变量非负”。若某决策变量 xk 为“取值无约束”(无符号限制)，令：xk = xk xk ，(xk0, xk 0) 。 （1）,2020/8/2,48,【例】将下列线性规划转化为标准型(标准形式)？,【解】(1)决策变量取值 x3 无符号要求(取值无约束) ，即x3取正值也可取负

25、值，标准型中要求变量取值为非负，所以可令：,2020/8/2,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。,2020/8/2,50,标准型为：,2020/8/2,5

26、1,将例1.1的线性规划问题的一般形式化为标准型？,第二节 线性规划问题模型,2020/8/2,52,第二节 线性规划问题模型,2020/8/2,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 +

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

28、)解：令所有非基变量等于零，得出的唯一解。,基变量是x3 , x4 , x5 非基变量是x1 , x2 令非基变量 x1 = x2 = 0，基变量取值唯一确定：x3= 16，x4= 10，x5= 32 得到一个基解： X = (0 , 0 , 16 , 10 , 32)T,2020/8/2,55,重要概念,可行解：满足约束条件AX=b和X0的解。 基(本)解：令所有非基变量等于零，得出的唯一解。 基(本)可行解：满足X0的基解。 可行基：基可行解对应的基矩阵。 最优解：使目标函数最优的基可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。,2020/8/2,56,基的概念,假设线性规

29、划问题模型系数矩阵为m行、n列(mn)，则系数矩阵中秩为m的m行m列子矩阵，称为基矩阵，简称基。,基中的列向量对应的变量称为基变量，决策变量中基变量以外的变量称为非基变量。,2020/8/2,57,基本解,对于某一确定的基，令所有非基变量为0，由约束方程组AX=b可解出m个基变量的唯一解，称为一个基本解。,2020/8/2,58,基本可行解,满足非负条件的基本解，称为基本可行解，基本可行解对应于凸多边形的项点。,2020/8/2,59,练习：已知线性规划问题,问：,中哪一个是基本可行解？,2020/8/2,60,二、线性规划之解的概念,2、线性规划问题基本定理,定理1. 若线性规划问题存在可行

30、域，则其可行域一定 是凸集。 定理2. 线性规划问题的基可行解对应可行域的顶点。 定理3. 若可行域有界，线性规划的目标函数一定可以 在可行域的顶点上达到最优。 定理4. 线性规划如果有可行解，则一定有基可行解； 如果有最优解，则一定有基可行解是最优解。,2020/8/2,61,二、线性规划之解的概念,3、线性规划问题的解题思路,首先，找到一个初始基可行解，也就是找到一个初始可行基，想办法判断这个基可行解是不是最优解。 如果是最优解，就得到这个线性规划问题的最优解； 如果判断出不是最优解，就想法由这个可行基按一定规则变化到下一个可行基，然后再判断新得到的基可行解是不是最优解； 如果还不是，再接

31、着进行下一个可行基变化，直到得到最优解。,2020/8/2,62,求解线性规划问题的思路单纯形法,1947年，美国斯坦福大学丹捷格教授发明单纯形法。,2020/8/2,63,一、线性规划问题的代数解法（教材第32页例题）,解：(一)标准化：,(二)求初始基可行解,2020/8/2,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)一定不是最优

32、解。(X(0) X*),2020/8/2,65,Z(0) = 3x1 + 5x2,(四)方案调整(换基),寻找一个新的基可行解，使目标函数值得到改善。,选择入基变量 寻找使目标函数增加量最大的非基变量入基，即目标函数中系数最大的变量。(x2),选择出基变量 为什么要选择原基变量出基？,要求决策变量非负，因此有：,说明x2最大取值是5，且当x2=5时，x4=0，即x4出基。 ( x4),2020/8/2,66,(五)求新的基可行解,此时，基变量为x3、x2和x5，非基变量为x1和x4。,用非基变量表示基变量：用x4表示x2，x2 = 5 (x4/2) ，用x4表示x5，x5 = 12 3x1 +

33、 2x4 。,令非基变量 x1 = x4 = 0，则 X(1) = (0, 5, 16, 0, 12)T 。,2020/8/2,67,(六)判优(检验),将式(4)代入目标函数，目的：用非基变量表示目标函数，得到新的目标函数值： Z(1) = 3x1 + 5x2 = 3x1 + 5(5 x4/2) = 3x1 5x4 / 2 + 25,非基变量x1的系数为3，大于零，可见，如果x1 能从非基变量变为基变量，即变为正数，则目标函数值会增加，因此X(1) = (0, 5, 16, 0, 12)T 不是最优解。,2020/8/2,68,Z(1) = 3x1 5x4/2 + 25,(七)换基,当x1

34、= 4时，x5 = 0,即：当x1 入基，x5 出基。,2020/8/2,69,(八)求新的基可行解,此时，基变量为x3、x2和x1，非基变量为x4和x5。,用非基变量表示基变量： x1 = 4 + 2x4 /3 x5/3 ， x3 = 8 4x4/3 + 2x5/3 。,令非基变量 x4 = x5 = 0，则 X(2) = (4, 5, 8, 0, 0)T 。,2020/8/2,70,松弛变量x3 = 8,说明第一项资源有剩余，资源相对宽松，这就是松驰变量的经济含义。,(九)判优(检验),非基变量x4和x5的系数均为负值，如果x4 和x5从非基变量变为基变量，即从零变为正数，则目标函数值会减

35、少，因此X(2) = (4, 5, 8, 0, 0)T 是最优解，目标函数最优值Z* = 37。,2020/8/2,71,求解过程(换基迭代过程),初始基,初始基可行解：X(0)=(0,0,16,10,32)T Z(0) =0,新的可行基,新的基可行解：X(1)=(0,5,6,0,12)T Z(1) =25,最优基,最优解：X* = (4,5,8,0,0)T Z* =37,2020/8/2,72,单纯形法求解线性规划问题的步骤：,(1)求出初始基本可行解(标准化、单位基)；,(2)最优性检验(非基变量检验数非正时停止，否则进入下一步)；,(3)换基(迭代)： 确定入基变量 确定出基变量 初等变

36、换，求出新的基本可行解；,(4)重复步骤(2)、(3)，直到求出最优解。,2020/8/2,73,单纯形法求解步骤举例,maxZ = 3x1 + 5x2 +0 x3 +0 x4+0 x5 2x1 + x3 = 16 2x2 + x4 = 10 3x1 +4x2 + x5 = 32,2020/8/2,74,最优解: X*=(4,5,8,0,0)T，Z*=37,2020/8/2,75,单纯形法的管理启示,2x1=16,X0=(0,0,10,10,32)T,X1=(0,5,16,0,12)T,X1=(4,5,8,0,0)T,在管理过程中，把现有方案作为初始方案，找到最急需要改进的某个问题和改进方向，

37、一次做好某个主要问题的解决与改进；一次只解决和改进一个问题的难度最小；解决之后，再寻求可以改进的其它地方，再次改进，不断地追求更优。,2020/8/2,76,单纯形法原理(1) 举例说明ppt52页,2020/8/2,77,单纯形法原理(2),非基变量检验数,令非基变量等于0，则,2020/8/2,78,单纯形法原理(单纯形表),2020/8/2,79,例 求解下列线性规划问题,解：引入松驰变量x3, x4 , x5 ，化为标准形式：,2020/8/2,80,由于x1，x2的检验数均为正，且x2的检验数k最大，选取x2为入基变量；再按最小比值= min(-, 3/1, 8/2) = 3，选取x

38、4为出基变量。,x2,5,2,1,0,0,-2,1,2,0,0,-5,0,15,2020/8/2,81,由于x1检验数为正，选取x1为入基变量；再按最小比值 = min（4/1, -, 2/1）=2，选取x5为出基变量。,x1,2,2,0,0,1,2,-1,0,0,0,-1,-2,19,2020/8/2,82,初始基本可行解：X(0) = (0, 0, 4, 3, 8)T，Z(0) = 0,新的基本可行解：X(1) = (0, 3, 4, 0, 2)T，Z(1) = 15,新的基本可行解：X(2) = (2, 3, 2, 0, 0)T，Z(2) = 19,判别定理 1：在单纯形表中（目标函数求

39、max），若所有非基变量的检验数小于零，且XB取值非负，则线性规划问题具有唯一最优解。,2020/8/2,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,2020/8/2,84,例 求解下列线性规划问题,解：引进松驰变量x3, x4, x5，化为标准形式：,2020/8/2,85,x2,4,2,-1/2,1,1/2,0,0,6,2,0

40、,-1,1,0,4,1/2,0,1/2,0,1,4,0,-2,0,0,8,2020/8/2,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,2020/8/2,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,2020/8/2,88,初始基本可行解：X(0) = (0, 0, 4, 10, 2)T，Z(0) = 0,新的基本可行解：X(1) = (0, 2, 0, 6, 4)T，Z(1

41、) = 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：在单纯形表中，若所有非基变量的检验数小于等于零，其中某个检验数等于零，则线性规划问题具有无穷多最优解(多重最优解)。,2020/8/2,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

42、/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,2020/8/2,90,例 求解下列线性规划问题,解：引入松驰变量x3, x4，标准化：,2020/8/2,91,不满足出基变量确定法则：,虽然，不能确定x3和x4哪个变量出基，但无论哪个变量出基，都必须满足： x30，x40。因x2入基，所以一定满足： x20。,说明x2可以无限增大，所以目标函数值可以无限增大。,无界解,2020/8/2,92,图解法求解结果：,A (0, 0),无界解,2020/8/2,93,练习 求

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

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