运筹学B线性规划课件

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

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

3、使企业在计划期内总的利润最大？第一节 线性规划的一般模型 一、线性规划模型的举例 7/29/20224 产品 资源 甲 乙丙现有资源设备A 3 1 2 200(h)设备B 2 2 4 200(h)材料C 4 5 1 360(kg)材料D 2 3 5 300(kg)利润（元/件） 40 30 50表1.1 某企业单位产品资源消耗及利润x1x1x1x1x1x2x2x2x2x2x3x3x3x3x37/29/20225【解】设x1、x2、x3 为甲、乙、丙三种产品的产量，则该线性规划问题的数学模型为： 产品 资源 甲 乙 丙现有资源设备A 3 1 2 200设备B 2 2 4 200材料C 4 5 1

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

5、目标要实现极大，有的则要求极小7/29/20227 练习1.1 某厂生产甲、乙两种产品，生产工艺路线为：各自的零部件分别在设备A、B加工，最后都需在设备C上装配。经测算得到相关数据如下表所示，单位甲、乙产品的销售价格分别为73和75元。问应如何制定生产计划，才能使总利润为最大？ 产品设备工时消耗甲 乙工时成本(元/h)生产能力(h)ABC 2 0 0 2 3 4 20 15 10161032x1x1x1x2 x2x22030247/29/20228(1)决策变量：设x1为甲产品的产量，x2为乙产品的产量。(2)约束条件：生产受设备能力制约，不能突破有效供给量。设备A的约束条件表达为 2x1 1

6、6同理，设备B的加工能力约束条件表达为 2x2 10设备C的装配能力也有限，其约束条件为 3x1+ 4x2 32(3)目标函数：目标是企业利润最大化 max Z = 3x1 + 5x2 (4)非负约束：甲乙产品的产量为非负 x1 0， x2 0LP模型：s.t. (subject to) 使满足，使服从7/29/20229练习1.2：某厂生产甲、乙两种产品，均需在A、B、C三种不同的设备上加工，单位产品加工所需工时、销售后能获得的利润及设备有效工时数见下表。问：如何安排生产计划，才能使该厂获得总利润最大？ 解: 设甲、乙产品产量分别 为x1、x2 公斤， 设总利润为Z，则： max Z = 7

7、0 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 07/29/202210线性规划的数学模型由决策变量 Decision variables 目标函数 Objective function 构成，称为三要素。约束条件 Constraints其主要特征是：1. 解决的问题是规划问题；2解决问题的目标函数是多个

8、决策变量的 线性函数，通常是求最大值或最小值；3解决问题的约束条件是多个决策变量 的线性不等式或等式。怎样辨别一个模型是线性规划模型？7/29/202211二、线性规划模型的举例 2、物资运输问题例：某产品商有三个供货源A1、A2、A3，其经销商有4个（需求市场）B1、B2、B3、B4。已知各厂的产量、各经销商的销售量及从 Ai 到 Bj 的单位运费为Cij。问如何调配运输方案，使总运费最小？ 销地产地B1B2B3B4产量A16 32550A27 5 8 4 20A33 2 9 7 30销量20301040 x11x12x13x14x21x22x23x24x31x32x33x34产销平衡(产量

9、等于销量)7/29/202212(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+

10、x34=40非负约束 xij0 (i=1,2,3；j=1,2,3,4) 4.5 线性规划的数学模型由三个要素组成：7/29/202213【练习】现有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5(万吨)，现将粮食运往B1，B2，B3，B4四个地区，其需求量分别为5，7，8，3(万吨)。产粮地到需求地的运价(元/吨)如下表所示，问如何安排一个运输计划，使总的运输费用最少？地区产粮区B1B2B3B4产量A1326310A253828A341295需求量578323/237/29/202214解：设 xij (i=1,2,3；j=1,2,3,4)为 i 个产粮地运往第 j 个需求地的运输量

11、，这样得到下列运输问题的数学模型：运输量应大于或等于零（非负)B1B2B3B4产量A1326310A253828A341295需要量5783237/29/2022153、产品配比问题 例：用浓度45%和92%的硫酸配置100吨浓度80%的硫酸，已经两种浓度硫酸的单价为每吨30和80元，问如何配置费用最小？决策变量：需要45%和92%的硫酸分别为 x1 和 x2 吨目标函数：min Z = 30 x1 + 80 x2约束条件：非负约束： x1 0， x2 07/29/202216 若有5种不同浓度的硫酸可选(30%,45%,73%,85%,92%)会如何呢？5种硫酸数量分别为 x1、x2、x3、

12、x4、x5 ，有：若5种硫酸价格分别为400, 700, 1400, 1900, 2500元/t，则：7/29/202217练习：某糖果厂用原料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.852.257/29/202218解：

13、设xij为生产第j种糖果使用的第i种原料的数量，则该问题的数学模型为： 最优解：即该厂每月应生产甲种牌号糖果906.67kg，乙种牌号糖果4793.33kg，利润最大为5450元。7/29/202219练习：生产某一机床需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是2.9、2.1和1.5m，这些轴需要用同一种圆钢切割而成，圆钢长度为7.4m。现在要制造100台机床，问：最少要用多少圆钢来生产这些轴？(假设切割损失不计)解：1、设一根圆钢切割成甲、乙、丙三种轴的根数分别为y1, y2, y3, 则切割方式可用不等式2.9y1+2.1y2+1.5y37.4表示，求这个不等式关于y1，y2，

14、y3的非负整数解。例如：y1=2， y2=0 ，则 y3 只能为1，余料为0.1。像这样的非负整数解共有8组，也就是有8种下料方式，如表1.4所示。 2、建立线性规划数学模型。设xj (j=1,2,8)为第 j 种下料方案所用圆钢的根数。4、合理下料问题7/29/202220 方案规格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

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

16、202222第三年：设 x5 为新的投资，x6 为第三年的保留资金；第四年：设新的投资 x7 ，第四年的保留资金 x8 ；第五年：设 x9 为第五年的保留资金。根据题意，第五年初不再进行新的投资，因为这笔投资要到第七年初才能收回。 约束条件 每年应满足如下的关系：追加投资金额 + 新投资金额 + 保留资金=可利用的资金总额 7/29/202223X*(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.6

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

18、0万元。 试确定一个第三年末本利和为最大的投资计划？7/29/202225 项目投资时间1234第1年初x11x12第2年初x21x23第3年初x31x34对于约束条件：第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 )

19、对于目标函数，只需考虑第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 7/29/202226解：设xij为第 i 年初投放到 j 项目的资金额(元)，其数学模型为：maxZ = 1.2 x31 + 1.6 x23 + 1.4 x34 注意本题条件：有钱就会用于投资，即：可利用的资金 = 投资金额，据此建立约束等式。x11 + x12 = 300000 x21 + x23 = 1.2 x11x31 + x34 = 1.2 x

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

21、在可行域内平移目标函数等值线， 确定最优解及最优目标函数值。 2、特点： 简单、直观，但只适用于两个变量的LP问题。 第二步：根据约束条件画出可行域；7/29/2022311、线性规划的可行域可行域：满足所有约束条件的解的集合，即由所有约束条件共同围成的区域。maxZ= 3x1 + 5x2 2x1 16 2x2 10 3x1+4x2 32 x10, x20s.t.2x1 =162x2 =103x1 +4 x2 =32x1x24810359OABCD7/29/2022322x1 =162x2 =10 x1x28103583x1 + 4x2 =320ABCD2、线性规划的最优解目标函数 Z = 3

22、x1 + 5x2 代表以 Z 为参数的一族平行线。Z=25Z=37Z=15(4, 5)X*=(4, 5)TZ*=377/29/202233x1x2O1020304010203040(15,10)最优解 X* = (15,10)T最优值 Z* = 857/29/202234246x1x2246最优解 X* = (3,1)T最优值 Z* = 5(3,1)min Z = x1 + 2x27/29/2022353、线性规划解的特性abcd由线性不等式组成的可行域是凸多边形(凸集)凸集：对于某一集合内部任意两点连线上的点都属于这个集合，我们就称这个集合为凸集。线性规划问题的可行域具有有限个顶点。 目标函

23、数最优值一定在可行域的边界(顶点)达到，而不可能在其区域的内部。7/29/202236凸集的概念设K为n维欧氏空间的一个点集，若K中任意两个点X1和X2连线上的所有点都属于K，则称K为凸集。X2X1X设X(x1,x2,xn); X1(u1,u2,un); X2(v1,v2,vn)7/29/202237四、线性规划解的可能性1、唯一最优解2、多重最优解/无穷多最优解当乙产品市场价格从75元下降到74元时，模型变为： 2x1 =162x2 =103x1+4x2=32x1x248102580ABCDZ=24Z=32Z=127/29/202238246x1x2246X(2) (3, 1)TX(1) (

24、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 7/29/2022393、无界解可行域无界，目标值无限增大(缺乏必要约束)7/29/202240246x1x2246(1,2)无界解max Z=x1+2x27/29/2022414、无可行解：线性规划问题的可行域是空集 (约束条件相互矛盾)7/29/202242x1x2O10203040102030405050无可行解max Z=10 x1+4x27/29/20224320130312 作业

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

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

27、3 无符号要求(取值无约束) ，即x3取正值也可取负值，标准型中要求变量取值为非负，所以可令：7/29/202248 (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。7/29

28、/202249标准型为： 7/29/202250将例1.1的线性规划问题的一般形式化为标准型？ 第二节 线性规划问题模型 7/29/202251第二节 线性规划问题模型 7/29/202252练习：将下列线性规划模型转化为标准型？ 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 +

29、 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题 7/29/202253二、线性规划之解的概念 基矩阵：一个非奇异的子矩阵（向量线性无关）。矩阵A 中任意一个 m 列的线性无关子矩阵 B ，称为一个基(矩阵)。组成基的列向量称为基向量，用 Pj 表示 ( i = 1 , 2 , , m ) 。基变量：与基向量 Pj 相对应的变量 xj 称为基变量。其余的 n m 个变量称为非基变量(基矩阵以外的列向量对应变量)。1、线性规

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

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

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

33、直到得到最优解。 7/29/202261求解线性规划问题的思路单纯形法求初始基本可行解判断该可行解是否最优寻找新的基本可行解结束是否1947年，美国斯坦福大学丹捷格教授发明单纯形法。7/29/202262一、线性规划问题的代数解法（教材第32页例题）解：(一)标准化：(二)求初始基可行解7/29/202263 令非基变量：x1=x2=0，得到初始基可行解： X(0)=(0,0,16,10,32)T 此时，目标函数值： Z(0) = 3x1 + 5x2 + 0 = 0目标函数用非基变量表示。(三)判优 对于Z(0) = 3x1 + 5x2 ，若x1或x2从0变为正数，则目标函数值会增加，因此可判

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

35、 3x1 + 2x4 。 令非基变量 x1 = x4 = 0，则 X(1) = (0, 5, 16, 0, 12)T 。7/29/202266(六)判优(检验) 将式(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 不是最优解。7/29/202267Z(1) = 3x1 5x4/2 + 25(七)换基 当x1

36、 = 4时，x5 = 0 即：当x1 入基，x5 出基。7/29/202268(八)求新的基可行解 此时，基变量为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 。7/29/202269 松弛变量x3 = 8 说明第一项资源有剩余，资源相对宽松，这就是松驰变量的经济含义。(九)判优(检验) 非基变量x4和x5的系数均为负值，如果x4 和x5从非基变量变为基变量，即从零变为正数，则目标函数值会减少，因

37、此X(2) = (4, 5, 8, 0, 0)T 是最优解，目标函数最优值Z* = 37。7/29/202270求解过程(换基迭代过程)初始基初始基可行解：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* =377/29/202271 单纯形法求解线性规划问题的步骤： (1)求出初始基本可行解(标准化、单位基)； (2)最优性检验(非基变量检验数非正时停止，否则进入下一步)； (3)换基(迭代)： 确定入基变量 确定出基变量 初等变换，求出新的基本可行解；

38、 (4)重复步骤(2)、(3)，直到求出最优解。7/29/202272单纯形法求解步骤举例 maxZ = 3x1 + 5x2 +0 x3 +0 x4+0 x5 2x1 + x3 = 16 2x2 + x4 = 10 3x1 +4x2 + x5 = 32 Cj比值CBXBb检验数jx1x2x3x4x535000162010010020103234001x3x4x5000035000-10/2=532/4=87/29/202273162010050101/2012300-21x3x2x5050300-5/205-4Cj比值CBXBb检验数jx1x2x3x4x535000检验数j80014/3-2/

39、350101/204100-2/31/3x3x2x1053000-1/2-1最优解: X*=(4,5,8,0,0)T，Z*=377/29/202274单纯形法的管理启示2x1=162x2 =103x1 + 4x2 =32x1x24812590ABC(4,5)DX0=(0,0,10,10,32)TX1=(0,5,16,0,12)TX1=(4,5,8,0,0)T 在管理过程中，把现有方案作为初始方案，找到最急需要改进的某个问题和改进方向，一次做好某个主要问题的解决与改进；一次只解决和改进一个问题的难度最小；解决之后，再寻求可以改进的其它地方，再次改进，不断地追求更优。7/29/202275单纯形法

40、原理(1) 举例说明ppt52页7/29/202276单纯形法原理(2)非基变量检验数 令非基变量等于0，则7/29/202277CjCBCNCBXBbXBXN0XBbBNjCBCNCBXBbXBXNCBXBB-1bEB-1Nj0CN CBB-1N单纯形法原理(单纯形表)7/29/202278例 求解下列线性规划问题解：引入松驰变量x3, x4 , x5 ，化为标准形式：7/29/202279 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 0

41、由于x1，x2的检验数均为正，且x2的检验数k最大，选取x2为入基变量；再按最小比值= min(-, 3/1, 8/2) = 3，选取x4为出基变量。 cj 2 5 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x3 x5 4 3 1 0 1 0 0 0 1 0 1 0 j x252100-21200-50157/29/202280 cj 2 5 0 0 0 CB XB b x1 x2 x3 x4 x5 0 5 0 x3 x2 x5 4 3 2 1 0 1 0 0 0 1 0 1 0 1 0 0 -2 1 j 15 2 0 0 -5 0 由于x1检验数为正，选取x1为入基变

42、量；再按最小比值 = min（4/1, -, 2/1）=2，选取x5为出基变量。 cj 2 5 0 0 0 CB XB b x1 x2 x3 x4 x5 0 5 x3 x2 3 2 0 1 0 1 0 1 0 0 -2 1 j x122001 2-1000-1-2197/29/202281 初始基本可行解：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：在单纯形表中（目标函数求max），若所有非基

43、变量的检验数小于零，且XB取值非负，则线性规划问题具有唯一最优解。7/29/202282图解法求解结果：x1x1 = 4x2 = 3x1 + 2x2 = 8x2(2, 3)x2 = -(2/5)x1 +Z/5 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) 07/29/202283例 求解下列线性规划问题解：引进松驰变量x3, x4, x5，化为标准形式：7/29/

44、202284 cj 2 4 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 4 10 2 -1 2 1 0 0 1 2 0 1 0 1 -1 0 0 1 j 0 2 4 0 0 0 cj 2 4 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x4 x5 j x242-1/21 1/200620-11041/201/20140-20087/29/202285 cj 2 4 0 0 0 CB XB b x1 x2 x3 x4 x5 4 0 0 x2 x4 x5 2 6 4 -1/2 1 1/2 0 0 2 0 -1 1 0 1/2 0 1

45、/2 0 1 j 8 4 0 -2 0 0 cj 2 4 0 0 0 CB XB b x1 x2 x3 x4 x5 4 0 x2 x5 j x12310-1/2 1/20011/41/407/2003/4-1/415/2000-20207/29/202286 cj 2 4 0 0 0 CB XB b x1 x2 x3 x4 x5 4 2 0 x2 x1 x5 7/2 3 5/2 0 1 1/4 1/4 0 1 0 -1/2 1/2 0 0 0 3/4 -1/4 1 j 20 0 0 0 -2 0 cj 2 4 0 0 0 CB XB b x1 x2 x3 x4 x5 4 2 x2 x1 j x

46、3010/3001 -1/34/38/30101/3-1/314/31001/32/3000-20207/29/202287 初始基本可行解：X(0) = (0, 0, 4, 10, 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：在单纯形表中，若所有非基变量的检验数小于等于零，其中某个检验数等于零，则线性规划问题具有无穷多最优解(

47、多重最优解)。7/29/202288图解法求解结果： 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/2, 0, 0, 5/2)T，Z* = 20D (14/3, 8/3)E (2, 0) D：X* = (14/3, 8/3, 10/3, 0, 0)T，Z* = 207/29/202289例 求解下列线性规划问题解：引入松驰变量x3, x4，标准化：7/29/202290 cj -2 3 0 0 CB XB b x1 x2 x

48、3 x4 0 0 x3 x4 2 4 4 -2 1 0 2 -3 0 1 j 0 -2 3 0 0 不满足出基变量确定法则：虽然，不能确定x3和x4哪个变量出基，但无论哪个变量出基，都必须满足： x30，x40。因x2入基，所以一定满足： x20。说明x2可以无限增大，所以目标函数值可以无限增大。无界解7/29/202291图解法求解结果： A (0, 0)无界解7/29/202292练习 求解下列线性规划问题解：引进松驰变量x3, x4，化为标准形式： 从标准形中可看出存在可行基B=(P3，P4)=E，基变量为X3，X4；非基变量为X1，X2。建立初始单纯形表得：7/29/202293cj

49、4 3 0 0CBXBb x1 x2 x3 x400 x3x42426 2 3 1 0 3 2 0 1 0 4 3 0 0 由于x1，x2的检验数均为非负，且x1的检验数绝对值最大，选取x1为进基变量；再按最小比值=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 104/3 0 1/3 0 -4/37/29/202294cj 4 3 0 0CBXBb x1 x2 x3 x434x2x146 0 1 3/5 -2/5 1 0 -2/5

50、3/5 36 0 0 -1/5 -6/5 表中最后一行的所有检验数均为非正，表明目标函数已达到最大值，上表为最优单纯形表。从表中可得到最优解为：X*=(x1, x2, x3, x4)T = (6, 4, 0, 0)T，最优值为：Z*=36。7/29/20229520130319 作业：用单纯形法求解以下问题（1）（2）（3）（4）7/29/202296cj 2 -1 1 0 0 0CBXBb x1 x2 x3 x4 x5 x6000 x4x5x6601020 3 1 1 1 0 0 1 -1 2 0 1 0 1 1 -1 0 0 1 -2 1 -1 0 0 0 练习：已知某线性规划用单纯形法求

51、得的某两步迭代表如下，请将表中空白处填上适当的数字。Cj 0 0 0 0 1 1CBXBb x1 x2 x3 x4 x5 x602-1x4x1x2 1 -1 -2 0 1/2 1/2 0 -1/2 1/2 cj 0 0 0 0 1 1CBXBb x1 x2 x3 x4 x5 x602-1x4x1x210155 0 0 1 1 -1 -2 1 0 1/2 0 1/2 1/2 0 1 -3/2 0 -1/2 1/2 25 0 0 -3/2 0 -3/2 -1/27/29/202297思考题 已知线性规划问题：其中b1, b2是常数，且已知此问题的最终单纯形表如下。试确定表中所有的参数？cj 5 2

52、 3 0 0CBXBb x1 x2 x3 x4 x5 50 x1x53010 1 b 2 1 0 0 c -8 -1 1 150 0 a -7 d e e = 0, d = 5, b = 5, c = 10, a = 23, b1= 30, b2= 407/29/202298思考：某极大化线性规划问题的单纯形表如下，问表中参数 a1, a2, a3, d, 1, 2 为何取值范围时，下列结论成立？ cj 0 0 0 0 1 1 CB XB b x1 x2 x3 x4 x5 x6 3 0 0 x3 x4 x6 d 2 3 4 a1 1 0 a2 0 -1 -3 0 1 -1 0 a3 -5 0

53、0 -4 1 j 1 2 0 0 -3 0 (1)表中解为唯一最优解：(2)表中解为无穷多最优解：(3)该问题具有无界解：(4)表中解为退化的基解：(5)表中解为不可行解：(6) x1入基，x6出基：10, 20, 12 = 0, d 01 0, 2 0, a1 0, d 01 0, 2 0, d = 0 d 0, d 0, d /43/a3 , a3 07/29/202299已知线性规划问题的最优单纯形表如下，求初始单纯形表中的参数C, A, b 以及最优基B ？cj c1 c2 c3 c4 c5 CB XB b x1 x2 x3 x4 x5 c1 c2 x1 x2 6 2 1 0 4 1/

54、6 1/15 0 1 -3 0 1/5 j 0 0 -1 -2 -3 7/29/2022100求解结果：7/29/2022101大M法（大M单纯形法） 通过添加人工变量构成单位基，进而求解线性规划问题的方法。7/29/2022102例 求解下列线性规划问题解：引进松驰变量x4, x5，化为标准形式：7/29/2022103加入变量x6, x7，加入参数M，M为任意大的正数7/29/2022104 cj 3 -1 -1 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 0 -M -M x4 x6 x7 11 3 1 1 -2 1 1 0 0 0 -4 1 2 0 -1 1 0 -2 0 1