第一章线性规划-运筹学课件.ppt

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

1、线线 性性 规规 划划(Linear Programming)线性规划问题及其数学模型线性规划问题及其数学模型线性规划的单纯形法线性规划的单纯形法线性规划的图解法线性规划的图解法单纯形法计算步骤单纯形法计算步骤单纯形法的进一步讨论单纯形法的进一步讨论线性规划模型的应用线性规划模型的应用5/26/20231一、线性规划问题及其数学模型一、线性规划问题及其数学模型 例例1.1 1.1 某厂生产两种产品，某厂生产两种产品，下表给出了单位产品所需资源下表给出了单位产品所需资源及单位产品利润及单位产品利润 问：应如何安排生产计划，才问：应如何安排生产计划，才能使总利润最大？能使总利润最大？（一）问题的提

2、出（一）问题的提出解：解：1.1.决策变量：设产品决策变量：设产品I I、IIII的产量的产量 分别为分别为 x1、x22.2.目标函数：设总利润为目标函数：设总利润为z z，则有：，则有：max z=2 x1+x23.3.约束条件：约束条件：5x2 15 6x1+2x2 24 x1+x2 5 x1，x205/26/20232 设设 备备产产 品品 A B C D利润（元）利润（元）2 1 4 0 2 2 2 0 4 3 有有 效效 台台 时时 12 8 16 12 例例1.2 已知资已知资料如下表所示，料如下表所示，问如何安排生产问如何安排生产才能使利润最大才能使利润最大？或如何考虑利？或如

3、何考虑利润大，产品好销。润大，产品好销。模模 型型max Z=2x1+3x2 x1 0,x2 0s.t.2x1+2x2 12 x1+2x2 8 4x1 16 4x2 125/26/20233 例例1.3 1.3 某厂生产三种药物，某厂生产三种药物，这些药物可以从四种不同的原这些药物可以从四种不同的原料中提取。下表给出了单位原料中提取。下表给出了单位原料可提取的药物量料可提取的药物量 要求：生产要求：生产A A种药物至少种药物至少160160单单位；位；B B种药物恰好种药物恰好200200单位，单位，C C种药物不超过种药物不超过180180单位，且使单位，且使原料总成本最小。原料总成本最小。

4、解：解：1.1.决策变量：设四种原料的使用决策变量：设四种原料的使用 量分别为：量分别为：x1、x2、x3、x42.2.目标函数：设总成本为目标函数：设总成本为z min z=5 x1+6 x2+7 x3+8 x43.3.约束条件：约束条件：x1+2x2+x3+x4 160 2x1 +4 x3+2 x4 200 3x1 x2+x3+2 x4 180 x1、x2、x3、x4 0 药物药物原料原料A AB BC C单位成本单位成本（元吨）（元吨）甲甲1 12 23 35 5乙乙2 20 01 16 6丙丙1 14 41 17 7丁丁1 12 22 28 85/26/20234（二）数学模型（二）数

5、学模型 船只种类船只数拖 轮30A型驳船34B型驳船52航线号合同货运量12002400航线号船队类型编队形式货运成本（千元队）货运量（千吨）拖轮A型驳船B型驳船1112362521436202322472404142720问：应如何编队，才能既完成合同任务，又使总货运成本为最小？例1.4 某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运 成本如下表所示：5/26/20236解：解：设：设：x xj j为第为第j j号类型船队的队数（号类型船队的队数（j=1j=1，2 2，3 3，4 4），），z z 为总货运成本为总货运成本则：min z=36x1+36x2+72x3+27x4

6、x1+x2 +2x3+x4 30 2x1 +2x3 34 4x2+4x3+4x4 5225x1+20 x2 200 40 x3+20 x4 400 xj 0 （j=1,2,3,4）5/26/202371 1 问题中总有未知的变量，需要我们去解决。问题中总有未知的变量，需要我们去解决。要求：有目标函数及约束条件，一般有非负条件要求：有目标函数及约束条件，一般有非负条件存在，由此组成规划数学模型。存在，由此组成规划数学模型。如果在规划问题的数学模型中，变量是连续的如果在规划问题的数学模型中，变量是连续的（数值取实数）其（数值取实数）其目标函数是目标函数是有关有关线性函数线性函数（一次方）（一次方）

7、，约束条件是约束条件是有关变量的有关变量的线性等式或不等式线性等式或不等式，这样，这样，规划问题的数学模型是规划问题的数学模型是线性线性的。反之，就是非线性的的。反之，就是非线性的规划问题（其中一个条件符合即可）。规划问题（其中一个条件符合即可）。（二）数学模型（二）数学模型 5/26/20238 模型特点模型特点1 1 都用一组决策变量都用一组决策变量X=(x1,x2,xn)T表示某一方案，表示某一方案，且决策变量取值非负；且决策变量取值非负；满足以上三个条件的满足以上三个条件的数学模型称为线性规划数学模型称为线性规划2 2 都有一个要达到的目标，并且目标要求可以表示成都有一个要达到的目标，

8、并且目标要求可以表示成决策变量的线性函数；决策变量的线性函数；3 3 都有一组约束条件，这些约束条件可以用决策变量都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等式来表示。的线性等式或线性不等式来表示。5/26/202310也可以记为如下形式也可以记为如下形式：目标函数：目标函数：约束条件：约束条件：5/26/202311目标函数目标函数价值系数价值系数技术系数技术系数右端项常数右端项常数决策变量决策变量5/26/202313矩阵形式：矩阵形式：5/26/202315（三）线性规划模型的标准形式（三）线性规划模型的标准形式1 1、标准形式标准形式 将模型的一般形式变成标准形式，

9、再根据标准型模型，将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基本可行解，并判断是否是最优。如果从可行域中找一个基本可行解，并判断是否是最优。如果是，获得最优解；如果不是，转换到另一个基本可行解，是，获得最优解；如果不是，转换到另一个基本可行解，当目标函数达到最大时，得到最优解。当目标函数达到最大时，得到最优解。5/26/202316 2 2、特征：、特征：目标函数为求极大值，也可以用求极小值；目标函数为求极大值，也可以用求极小值；所有约束条件（非负条件除外）都是等式，所有约束条件（非负条件除外）都是等式，右端常数项为非负；右端常数项为非负；变量为非负。变量为非负。3、转换

10、方式：、转换方式：目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即 ，则可将目标函，则可将目标函数乘以（数乘以（1 1），可化为求极大值问题。），可化为求极大值问题。也就是：令也就是：令 ，可得到下式，可得到下式即即5/26/202318(3)(3)约束方程的转换：由不等式转换为等式约束方程的转换：由不等式转换为等式 。称为松弛变量称为松弛变量 称为剩余变量称为剩余变量(2)(2)常数项常数项b bi i0 0的转换：约束方程两边乘以（的转换：约束方程两边乘以（1 1）。）。5/26/202319(4)(4)变量的变换变量的变换 若存在取值无约束的变量若存在取值无约束的变量 ，可

11、令，可令 其中：其中：例例 一、将下列线性规划问题化为标准形式一、将下列线性规划问题化为标准形式为无约束（无非负限制）为无约束（无非负限制）5/26/202320 解解:用用 替换替换 ，且，且 ，将第将第3 3个约束方程两边乘以个约束方程两边乘以（1 1）将极小值问题反号，变为求极大值将极小值问题反号，变为求极大值标准形式如下：标准形式如下：引入变量引入变量5/26/202321例二、将线性规划问题化为标准型例二、将线性规划问题化为标准型解解：5/26/202322例四：例四：将将 min Z=-X1+2X2-3X3X1+X2+X3 7X1-X2+X3 2 2X1，X2 0 0，X3无限制无

12、限制化为标准型化为标准型5/26/202324解：解：令令X3=X4-X5 加松弛变量加松弛变量X6 加剩余变量加剩余变量X7 令令Z=-ZmaxZ=X1-2X2+3X4-3X5 X1+X2+X4-X5+X6 =7X1-X2+X4-X5-X7=2X1,X2,X4,X7 0 0返回返回5/26/202325例五：将以下数学模型化为标准形例五：将以下数学模型化为标准形5/26/202326一一 般般 有有两种方法两种方法图图 解解 法法单纯形法单纯形法两个变量、直角坐标两个变量、直角坐标三个变量、立体坐标三个变量、立体坐标适用于任意变量、但需将适用于任意变量、但需将一般形式变成标准形式一般形式变成

13、标准形式线性规划问题的求解方法线性规划问题的求解方法 5/26/202328二、图二、图 解解 法法（一）解题步骤（一）解题步骤4 4 将最优解代入目标函数，求出最优值。将最优解代入目标函数，求出最优值。1 1 在直角平面坐标系中画出所有的约束等式，并找出所在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共部分，称为可行域，可行域中的点称有约束条件的公共部分，称为可行域，可行域中的点称为可行解。为可行解。2 2 标出目标函数值增加或者减小的方向。标出目标函数值增加或者减小的方向。3 3 若求最大（小）值，则令目标函数等值线沿（逆）目若求最大（小）值，则令目标函数等值线沿（逆）目标函

14、数值增加的方向平行移动，找与可行域最后相交的标函数值增加的方向平行移动，找与可行域最后相交的点，该点就是最优解点，该点就是最优解。5/26/20232901 2 3 4 5 6 7 8 1 2 3 4 5 6 作作 图图 最最 优优 解：解：x1=4 x2=2有唯一最优解，有唯一最优解，Z=14Z=14x2 x1(4 2)5/26/202331例二：用图解法求下列线性规划问题的最优解例二：用图解法求下列线性规划问题的最优解5/26/2023321.画出可行域x1x2X1+x2=3003003004002002x1+x2=400X2=250250X2=0X1=05/26/2023332.用目标函

15、数切割可行域x1x2X1+x2=3003003004002002x1+x2=400X2=250250X2=0X1=0Z=0=50 x1+100 x25/26/202334例三 5/26/202335x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1-1.9X2=-3.8()X1+1.9X2=10.2()4=2X1+X2 20=2X1+X2 17.2=2X1+X2 11=2X1+X2 Lo：0=2X1+X2（7.6，2）Dmax Zmin Z此点是唯一最优解，此点是唯一最优解，且最优目标函数值且最优目标函数值 max Z=17.2可行域可行域5/26/202336最小化问题的

16、图解法x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1-1.9X2=-3.8()X1+1.9X2=10.2()DL0：0=5X1+4X2 max Z43=5X1+4X2（0，2）可行域可行域此点是唯一最优解此点是唯一最优解5/26/2023375/26/2023385/26/2023395/26/202340（二）线性规划问题解的情况（二）线性规划问题解的情况唯唯 一一 解解无无 穷穷 解解无无 界界 解解无可行解无可行解5/26/202341 例二、例二、例三、例三、无穷多最优解无穷多最优解无界解无界解x1x1x2 x2 5/26/202342x1x2 无可行解无可行解例四

17、、例四、5/26/202343（三）由图解法得到的几种情况（三）由图解法得到的几种情况 根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况 1.可行域为封闭的有界区域 (a)有唯一的最优解；(b)有无穷多个最优解；2.可行域为封闭的无界区域 (c)有唯一的最优解；(d)有无穷多个最优解；(e)目标函数无界(即虽有可行解，但在可行域中，目标 函数可以无限增大或无限减少)，因而没有有限最优解。3.可行域为空集 (f)没有可行解，原问题无最优解5/26/202344（四）由图解法得到的启示（四）由图解法得到的启示(1)(1)线性规划问题解的情况：惟一最优解；无穷线性规划问题

18、解的情况：惟一最优解；无穷多最优解；无界解；无可行解多最优解；无界解；无可行解 (3)(3)最优解一定是在凸集的某个顶点最优解一定是在凸集的某个顶点(2)(2)线线性规划问题的可行域是凸集（凸多边形）性规划问题的可行域是凸集（凸多边形）(4)(4)解题思路是，先找出凸集的任一顶点，计算解题思路是，先找出凸集的任一顶点，计算 其目标函数值，再与周围顶点的目标函数值比其目标函数值，再与周围顶点的目标函数值比 较，如不是最大，继续比较，直到找出最大为较，如不是最大，继续比较，直到找出最大为 止。止。5/26/202345（一）线性规划问题解的概念（一）线性规划问题解的概念 可行解可行解：满足约束条件

19、：满足约束条件、的解为可行解。的解为可行解。所有解的集合为可行解的集或可行域。所有解的集合为可行解的集或可行域。最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。基基：B B是系数矩阵是系数矩阵A A（mnmn阶）中的一个阶）中的一个mmmm阶阶 的满秩子矩阵的满秩子矩阵(B0)(B0)，称，称B B是一个基。是一个基。则称则称 Pj(j=1 2 m)为基向量为基向量。Xj 为基变量，否则为非基变量。为基变量，否则为非基变量。三、线性规划的单纯形法三、线性规划的单纯形法5/26/202346 基解基解：满足条件：满足条件，但不满足条件，但不满足条件的的 所有解，最多为

20、所有解，最多为 个。个。基可行解基可行解：满足非负约束条件的基解，：满足非负约束条件的基解，简称基可行解。简称基可行解。可行基可行基：对应于基可行解的基称为可行基。：对应于基可行解的基称为可行基。非可行解非可行解可可行行解解基解基解基可行解基可行解5/26/202347（二）凸集及其顶点（二）凸集及其顶点 凸集凸集：如果集合：如果集合C C中任意两个点中任意两个点X X1 1，X X2 2,其连线上其连线上的所有点也都是集合的所有点也都是集合C C中的点，称中的点，称C C为凸集。为凸集。凸集凸集凸集凸集不是凸集不是凸集顶顶 点点 顶点顶点：如果凸集：如果凸集C C中不存在任何两个不同的点中不

21、存在任何两个不同的点X X1 1，X X2 2，使，使X X成为这两个点连线上的一个点成为这两个点连线上的一个点5/26/202348（三）基本定理（三）基本定理 定理定理1 1 若线性规划问题存在可行解，则问题的可行域是一个凸集。定理定理2 2 线性规划的基可行解对应线性规划问题可行域（凸集）的顶点。定理定理3 3 若线性规划问题有最优解，一定存在一个基可行解是最优解。5/26/202349 将模型的一般形式变成标准形式，再根据标将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基本可行解，并判准型模型，从可行域中找一个基本可行解，并判断是否是最优。如果是，获得最优解；如果不是

22、，断是否是最优。如果是，获得最优解；如果不是，转换到另一个基本可行解，当目标函数达到最大转换到另一个基本可行解，当目标函数达到最大时，得到最优解。时，得到最优解。（四）单纯形法迭代原理（四）单纯形法迭代原理基本思路5/26/202350例例:变成标准型变成标准型 5/26/202351约束方程的系数矩阵约束方程的系数矩阵 为基变量为基变量为非基变量为非基变量I I 为单位矩阵且线性独立为单位矩阵且线性独立5/26/202352令：令：则：则：基可行解为基可行解为（0 0 12 8 16 120 0 12 8 16 12）此时，此时，Z=0Z=0 然后，找另一个基可行解。然后，找另一个基可行解。

23、即将非基变量换即将非基变量换入基变量中，但保证其余的非负入基变量中，但保证其余的非负。如此循环下。如此循环下去，直到找到最优解为止。去，直到找到最优解为止。注意注意：为尽快找到最优解，在换入变量时有一定：为尽快找到最优解，在换入变量时有一定的要求。如将目标系数大的先换入等。的要求。如将目标系数大的先换入等。5/26/202353找出一个初始可行解找出一个初始可行解 是否最优是否最优转移到另一个目标函数转移到另一个目标函数（找更大的基可行（找更大的基可行 解）解）最优最优 解解是是否否循循环环直到找出为止，直到找出为止，核心核心是：是：变量迭代变量迭代结结 束束其步骤总结如下：其步骤总结如下：5

24、/26/202354当当 时，时，为换入变量为换入变量 确定换出变量确定换出变量为换出变量为换出变量接下来有下式：接下来有下式：5/26/202355 用高斯法，将用高斯法，将 的系数列向量换为单位列向量，其的系数列向量换为单位列向量，其步骤是：步骤是：结果是：结果是：5/26/202356代入目标函数：代入目标函数：有正系数表明：还有潜力可挖，没有达到最大值；有正系数表明：还有潜力可挖，没有达到最大值；此时：令此时：令 得到另一个基可行解得到另一个基可行解 （0，3，6，2，16，0）有负系数表明：若要剩余资源发挥作用，就必须有负系数表明：若要剩余资源发挥作用，就必须支付附加费用。当支付附加

25、费用。当 时，即不再利用这些资源。时，即不再利用这些资源。如此循环进行，直到找到最优为止。如此循环进行，直到找到最优为止。本例最优解为：本例最优解为：（4，2，0，0，0，4）5/26/202357四、单纯形法计算步骤四、单纯形法计算步骤单纯形表单纯形表5/26/202358例例 题：题：判定标准：判定标准：5/26/202359cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60000 x3x4x5x61281612 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1Z0 2 3 0 0 0 012/28/212/4cj 2

26、 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x6000 x3x4x516 4 0 0 0 1 0 Z3x23010001/42620100-1/210010-1/25/26/202360 cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60003x3x4x5x262163 2 0 1 0 0 -1/2 1 0 0 1 0 -1/2 4 0 0 0 1 0 0 1 0 0 0 1/4Z9 2 0 0 0 0 -3/46/2216/4cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x3 x1x5x22283 0 0 1 -

27、2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/44412Z13 0 0 0 -2 0 1/45/26/202361cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x6 x1x5x2 4402 0 0 2 -4 0 1 1 0 1 -1 0 0 0 0 -4 4 1 0 0 1 -1/2 1 0 0 Z14 0 0 -1/2 -1 0 0 0 0 0 -2 0 1/413Z4412 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/42283x3 x1x

28、5x20203 x1 x2 x3 x4 x5 x6bxBcB 2 3 0 0 0 0cj5/26/202362例例2 2：用单纯形法求解下面线性规划问题：用单纯形法求解下面线性规划问题5/26/202363解：化为标准型解：化为标准型5/26/202364建立初始单纯形表建立初始单纯形表cj23000CBXBbx1x2x3x4x50 x381210040 x41640010-0 x512040013z0230002-0*1-0*4-0*08/25/26/202365第一次迭代第一次迭代cj23000CBXBbx1x2x3x4x50 x321010-1/2 20 x4164001043x2301

29、001/4-z92000-3/45/26/202366第二次迭代第二次迭代cj23000CBXBbx1x2x3x4x52x121010-1/2-0 x4800-41243x2301001/412z1300-201/45/26/202367第三次迭代第三次迭代cj23000CBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80z1400-1.5-1/805/26/202368于是得到最优解于是得到最优解目标函数值目标函数值 5/26/202369（一）模型情况（一）模型情况 变变 量：量：xj0 xj0 xj无约束无约束 结结1、组成、组成 约

30、束条件：约束条件：=b 目标函数：目标函数：max min 果果2、变量、变量 xj0 令令 xj=-xj，xj0 xj0 不处理不处理 xj 无约束无约束 令令xj=xj xj,xj0,xj0 惟一最优解惟一最优解无穷最优解无穷最优解无界解无界解无可行解无可行解 五、单纯形法的进一步讨论五、单纯形法的进一步讨论5/26/2023703 3、约束、约束 条件：条件：加入松弛变量加入松弛变量加入人工变量加入人工变量先减去先减去 再加上再加上例：例：5/26/2023714 4、目标函数：、目标函数：max (min)设规划模型约束条件为设规划模型约束条件为 ，需加入人工变量，需加入人工变量 ，而

31、得到一个，而得到一个mm的单位矩阵，即基变量组合。因人工的单位矩阵，即基变量组合。因人工变量为虚拟变量，且存在于初始基可行解中，需要将它们变量为虚拟变量，且存在于初始基可行解中，需要将它们从基变量中替换出来。若基变量中不含有非零的人工变量，从基变量中替换出来。若基变量中不含有非零的人工变量，表示原问题有解。若当表示原问题有解。若当 ，还有人工变量（非零），还有人工变量（非零）时，则表示原问题无可行解。时，则表示原问题无可行解。5/26/202372 加入人工变量后，目的是找到一个单位向量，叫人加入人工变量后，目的是找到一个单位向量，叫人工基。其目标价值系数要确定，但不能影响目标函数工基。其目标

32、价值系数要确定，但不能影响目标函数的取值。一般可采用两种方法处理：大的取值。一般可采用两种方法处理：大M法和两阶段法和两阶段法。法。即假定人工变量在目标函数中的系数为即假定人工变量在目标函数中的系数为M M（任意大正数），如果是求极大值，需加（任意大正数），如果是求极大值，需加-M；如果；如果是求极小值，需加是求极小值，需加M。如基变量中还存在。如基变量中还存在M，就不能，就不能实现极值。实现极值。大大M法：法：5/26/202373cj3-1-100-M-McBxBbx1x2x3x4x5x6x70 x4111-21100011-Mx63-4120-1103/2-Mx71-20100011Z-

33、4M3-6M-1+M-1+3M0-M00cBxBbx1x2x3x4x5x6x70 x4103-20100-1-Mx610100-11-21-1x31-2010001Z-M-11-1+M00-M0-3M+15/26/202374cj3-1-100-M-McBxBbx1x2x3x4x5x6x70 x4123001-22-54-1x210100-11-2-1x31-2010001Z-21000-1-M+1-M-1cBxBbx1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Z2000-1/3-1/3-M+1/3

34、-M+2/3最优解为最优解为（4 1 9 0 0 0 0），Z=25/26/202375 用计算机处理数据时，只能用很大的数代用计算机处理数据时，只能用很大的数代替替M,可能造成计算机上的错误，故多采用两阶段法。可能造成计算机上的错误，故多采用两阶段法。第一阶段：第一阶段：在原线性规划问题中加入人工变量，构造如下模型：在原线性规划问题中加入人工变量，构造如下模型：两阶段法：两阶段法：5/26/202376 对上述模型求解（单纯形法），若对上述模型求解（单纯形法），若=0,=0,说明问说明问题存在基可行解，可以进行第二个阶段；否则，原问题存在基可行解，可以进行第二个阶段；否则，原问题无可行解，停

35、止运算。题无可行解，停止运算。第二阶段：第二阶段：在第一阶段的最终表中，去掉人工变在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。作为第二阶段计算的初始表（用单纯形法计算）。上例：上例：5/26/202377第一阶段的线性规划问题可写为：第一阶段的线性规划问题可写为：第一阶段单纯形法迭代的过程见下表第一阶段单纯形法迭代的过程见下表（注意：没有化为极大化问题）（注意：没有化为极大化问题）5/26/202378cj0000011cBxBbx1x2x3x4x5x6x70 x4111

36、-211000111x63-4120-1103/21x71-2010001146-1-301000 x4103-20100-11x610100-11-210 x31-201000110-1001030 x4123001-22-50 x210100-11-20 x31-2010000000000115/26/202379cj3-1-100cBxBbx1x2x3x4x50 x4123001-24-1x210100-1-1x31-20100Z-21000-13x141001/3-2/3-1x210100-1-1x390012/3-4/3Z2000-1/3-1/3第二阶段：第二阶段：最优解为（最优解为

37、（4 1 9 0 04 1 9 0 0），目标函数），目标函数 Z=2 Z=25/26/2023806 6、无、无可行解的判断：运算到检验数全负为止，可行解的判断：运算到检验数全负为止，仍含有人工变量，无可行解。仍含有人工变量，无可行解。5/26/202381 8 8、退化：、退化：即计算出的即计算出的（用于确定换（用于确定换出变量）存在有两个以上相同的最小比值，出变量）存在有两个以上相同的最小比值，会造成下一次迭代中由一个或几个基变量等会造成下一次迭代中由一个或几个基变量等于零，这就是退化（会产生退化解）。于零，这就是退化（会产生退化解）。当存在多个当存在多个 时，时，选下标最小的选下标最小

38、的非基变量为换入变量；非基变量为换入变量；为避免出现计算的循环，勃兰特为避免出现计算的循环，勃兰特(Bland)提出一个简便有效的规则：提出一个简便有效的规则：当当值值出现两个以上相同的最小值时，选出现两个以上相同的最小值时，选下标最小的基变量为换出变量。下标最小的基变量为换出变量。5/26/202382 一、无可行解一、无可行解 例例1 1、用单纯形表求解下列线性规划问题、用单纯形表求解下列线性规划问题解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到：解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到：填入单纯形表计算得：填入单纯形表计算得：几种特殊情况5/26/2

39、02383 几种特殊情况迭迭代代次次数数基基变变量量CBx1 x2 s1 s2 s3 a1b比值比值20 30 0 0 0 -M0s1s2a100-M3 10 1 0 0 01 0 0 1 0 01 1 0 0 -1 11503040150/1040/1cj-zj20+M 30+M 0 0 -M 01x2s2a1300-M3/10 1 1/10 0 0 0 1 0 0 1 0 07/10 0 -1/10 0 -1 115302515/(3/10)30/125/(7/10)cj-zj11+7/10M 0 -3-M/10 0 -M 0 2x2x1a13020-M0 1 1/10 -3/10 0 0

40、1 0 0 1 0 00 0 -1/10 -7/10 -1 1 6304cj-zj0 0 -3-M/10 -11-7M/10 -M 05/26/202384 从第二次迭代的检验数都小于零来看，可知第从第二次迭代的检验数都小于零来看，可知第2 2次迭代所得的基本可行次迭代所得的基本可行解已经是最优解了，其最大的目标函数值为解已经是最优解了，其最大的目标函数值为780-4M780-4M。我们把最优解。我们把最优解x x1 1=30,x=30,x2 2=6,s=6,s1 1=0,s=0,s2 2=0,s=0,s3 3=0,a=0,a1 1=4,=4,代入第三个约束方程得代入第三个约束方程得x x1

41、1+x+x2 2-0+4=40,-0+4=40,即即有：有：x x1 1+x+x2 2=3640.=3640.并不满足原来的约束条件并不满足原来的约束条件3 3，可知原线性规划问题无可行解，或者说其，可知原线性规划问题无可行解，或者说其可行解域为空集，当然更不可能有最优解了。可行解域为空集，当然更不可能有最优解了。像这样只要求线性规划的最优解里有人工变量不等于零，则此线性规像这样只要求线性规划的最优解里有人工变量不等于零，则此线性规划无可行解。划无可行解。二、无界解二、无界解 在求目标函数最大值的问题中，所谓无在求目标函数最大值的问题中，所谓无界解是指在约束条件下目标函数值可以取界解是指在约束

42、条件下目标函数值可以取任意的大。任意的大。例例2 2、用单纯形表求解下面线性、用单纯形表求解下面线性规划问题。规划问题。几种特殊情况5/26/202385 填入单纯形表计算得：填入单纯形表计算得：解：在上述问题的约束条件中加入松驰变量，得标准型如下：解：在上述问题的约束条件中加入松驰变量，得标准型如下：迭迭代代次次数数基基变变量量CBx1 x2 s1 s2b比值比值1 1 0 00s1s2001 -1 1 0-3 2 0 1161cj-zj1 1 0 001x1s2101 -1 1 0 0 -1 3 119cj-zj0 2 -1 05/26/202386 从单纯形表中，从第一次迭代的检验数等于

43、2，可知所得的基本可行解x1=1,x2=0,s1=0,s2=9不是最优解。同时我们也知道如果进行第2次迭代，那么就选x2为入基变量，但是在选择出基变量时遇到了问题：=-1,=-1,找不到大于零的 来确定出基变量。事实上如果我们碰到这种情况就可以断定这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此目标函数值可以取得无限大。从1次迭代的单纯形表中，得到约束方程：移项可得：移项可得：5/26/202387 由于由于M M可以是任意大的正数，可知此目标函数值无界。可以是任意大的正数，可知此目标函数值无界。上述的例子告诉了我们在单纯形表中识别线性规划问题是无界的上述的例子告诉了我们在单纯形

44、表中识别线性规划问题是无界的方法：在某次迭代的单纯形表中，如果存在着一个大于零的检验数方法：在某次迭代的单纯形表中，如果存在着一个大于零的检验数 ，并且该列的系数向量的每个元素，并且该列的系数向量的每个元素a aijij(i=1,2,m)(i=1,2,m)都小于或等于零，都小于或等于零，则此线性规划问题是无界的，一般地说此类问题的出现是由于建模则此线性规划问题是无界的，一般地说此类问题的出现是由于建模的错误所引起的。的错误所引起的。三、无穷多最优解三、无穷多最优解例例3 3、用单纯形法表求解下面的线性规划问题。、用单纯形法表求解下面的线性规划问题。5/26/202388 解：此题我们用图解法已

45、求了解，现在用单纯形表来求解。解：此题我们用图解法已求了解，现在用单纯形表来求解。填入单纯形表计算得：填入单纯形表计算得：5/26/202389迭迭代代次次数数基变基变量量CBx1 x2 s1 s2 s3b比值比值50 50 0 0 00s1s2s30001 1 1 0 02 1 0 1 00 1 0 0 1300400250300/1400/1250/1cj-zj50 50 0 0 01s1s2x200501 0 1 0 -12 0 0 1 -10 1 0 0 15015025050/1150/2cj-zj50 0 0 0 02x1s2x2500501 0 1 0 -10 0 -2 1 10

46、 1 0 0 1505025050/1250/1cj-zj0 0 -50 0 05/26/202390 这样我们求得了最优解为x1=50,x2=250,s1=0,s2=50,s3=0,此线性规划的最优值为15000。这个最优解是否是惟一的呢？由于在第2次迭代的检验数中除了基变量的检验数 等于零外，非基变量s3的检验数也等于零，这样我们可以断定此线性规划问题有无穷多最优解。不妨我们把检验数也为零的非基变量选为入基变量进行第3次迭代。可求得另一个基本可行解，如下表所示：迭代迭代次数次数基基变变量量CBx1 x2 s1 s2 s3b50 50 0 0 03x1s3x2500501 0 -1 1 00

47、 0 -2 1 10 1 2 -1 010050200cj-zj0 0 -50 0 05/26/202391 从检验数可知此基本可行解x1=100,x2=200,s1=0,s2=0,s3=50,也是最优解，从图解法可知连接这两点的线段上的任一点都是此线性规划的最优解，不妨用向量Z1，Z2表示上述两个最优解即Z1=（50，250，0，50，0），Z2=（100，200，0，0，50），则此线段上的任一点，即可表示为Z1+（1-）Z2，其中01。如图5-1所示：100100200200300300100100200200300300250250Z Z1Z Z2图图5-15/26/202392 在一

48、个已得到最优解的单纯形表中，如果存在一个非基变量的检验数 为零，为什么我们把这个非基变量xs作为入基变量进行迭代时，得到的最优解仍为最优解呢？不妨设出基变量为xk，则原最优单纯形表可表示如下：5/26/202393 通过迭代，我们得到了新的单纯形表，其中xs为基变量了，而xk为非基变量了。我们可得到下表。5/26/202394 又显然在新的单纯形表中，基变量的检验数为零，用同样的方法可证明其他的非基变量的检验数不变，仍然小于零，这样就证明了新得到的基本可行解仍然是最优解。这样我们得到了判断线性规划有无穷多最优解的方法：对于某个最优的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题

49、有无穷多最优解。四、退化问题 在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。例4.用单纯形表，求解下列线性规划问题。解：加上松驰变量s1,s2,s3化为标准形式后，填入单纯形表计算得：5/26/202395迭迭代代次次数数基基变变量量CBx1 x2 x3 s1 s2 s3b比值比值2 0 3/2 0 0 00s1s2s30001 -1 0 1 0 02 0 1 0 1 01 1 1 0 0 12432/14/23/1cj-zj2 0 3/2 0 0 01x1s2s32001 -1 0 1 0 0 0 2 1

50、-2 1 00 2 1 -1 0 12010/21/2cj-zj0 2 3/2 -2 0 02x1x2s32001 0 1/2 0 1/2 00 1 1/2 -1 1/2 00 0 0 1 -1 1 2012/(1/2)0/(1/2)cj-zj0 0 1/2 0 -1 05/26/202396 在以上的计算中可以看出在0次迭代中，由于比值b1/a11=b2/a21=2为最小比值，导致在第1次迭代中出现了退化，基变量s2=0。又由于在第1次迭代出现了退化，基变量s2=0，又导致第2次迭代所取得的目标函数值并没有得到改善，仍然与第1次迭代的一样都等于4。像这样继续迭代而得不到目标函数的改善，当然减