工程最优化方法

1、第二章第二章 线性规划线性规划 lixgi, 1 , 0)(mxhj, 1j , 0)( min f(x) s.t. 在模型在模型 中中当当f(x), g i(x), (i=1,l ), hj(x), (j=1,m)均为线性函数时，称为均为线性函数时，称为线性规划线性规划问题问题 Linear Programming ( LP ) 二维问题的图解法二维问题的图解法 线性规划的基本定理线性规划的基本定理 单纯形法单纯形法 大大M法法要点：要点：基本定理、顶点、标准形式、典范形式、可行基本解、基本定理、顶点、标准形式、典范形式、可行基本解、 价值系数、最优性准则、单纯形表格法价值系数、最优性准则、

2、单纯形表格法 研究重要性研究重要性（1）一些）一些 NLP 问题可简化为问题可简化为 LP 问题求解问题求解（2）是开发一些较复杂）是开发一些较复杂 NLP 算法的基础算法的基础（3）是所有最优化方法中最常用的技术）是所有最优化方法中最常用的技术 ( 占占47；科学计算中，；科学计算中，LP的计算时间占的计算时间占1/4） 1939 1939年，苏联数学家康托洛维奇提出并解决了一个线性规划年，苏联数学家康托洛维奇提出并解决了一个线性规划问题（问题（生产组织与计划中的数学方法生产组织与计划中的数学方法） 1947 1947年，美国数学家年，美国数学家G.B.DantzingG.B.Dantzin

3、g提出单纯形法，奠定了提出单纯形法，奠定了LPLP的理论基础的理论基础 1832和和1911年，法国数学家年，法国数学家J. B. J.傅里叶和傅里叶和C.瓦莱普森分别瓦莱普森分别提出线性规划的想法提出线性规划的想法2.1 2.1 建立建立LPLP问题数学模型的实例问题数学模型的实例 （1）确定自变量）确定自变量建模的三个步骤建模的三个步骤 （2）把问题的约束条件表示成等式或不）把问题的约束条件表示成等式或不等式等式 （3）写出目标函数）写出目标函数例例2.1.1 确定职工编制问题确定职工编制问题 某厂每日某厂每日8小时的产量不低于小时的产量不低于1800件。为了进行质量控制，计划聘请两种件。

4、为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准是：速度不同水平的检验员。一级检验员的标准是：速度 25件件/小时，正确率小时，正确率 98，计时工资计时工资 4元元/小时；二级检验员的标准是：速度小时；二级检验员的标准是：速度 15件件/小时，正确率小时，正确率 95，计时工资计时工资 3元元/小时。检验员每错验一次，工厂要损失小时。检验员每错验一次，工厂要损失2元。现可供厂方聘请元。现可供厂方聘请的检验员人数为一级的检验员人数为一级8人和二级人和二级10人。为使总检验费用最省，该工厂应聘一人。为使总检验费用最省，该工厂应聘一级和二级检验员各多少名？级和二级检验员各多少名？分

5、析：分析：设应聘一级检验员设应聘一级检验员x1 ，二级检验员，二级检验员x2 约束一：约束一：可聘两级检验员人数可聘两级检验员人数 x1 8 x2 10 约束二：约束二：每日产量要求每日产量要求 8(25)x1+8(15)x2 1800 5x1+3x2 45 目标函数目标函数 一级检验员每小时费用一级检验员每小时费用 425 (0.02) (2)=5元元/小时小时 二级检验员每小时费用二级检验员每小时费用 315 (0.05) (2)=4.5元元/小时小时 f(x) = 8(5x1+4.5x2) = 40 x1+36x2 min f(x)=40 x1+36x2 s.t. 5x1+3x2 45

6、x18 x210 x1, x2 0数学模型数学模型隐含的隐含的约束条件约束条件2.2 2.2 二维问题的图解法二维问题的图解法图解步骤图解步骤（1）在在x10 x2坐标平面上画出可行域；坐标平面上画出可行域；（2）作目标函数的等高线作目标函数的等高线 (为一组平行的直线为一组平行的直线)，根据等高线函数值的变化规律及目标函数的要根据等高线函数值的变化规律及目标函数的要 求，确定等高线的移动方向，按此方向移动求，确定等高线的移动方向，按此方向移动 等高线，使其达到可行域的极限点（最优点）；等高线，使其达到可行域的极限点（最优点）；（3）根据最优点的位置，联立求解对应的约束方程，根据最优点的位置，

7、联立求解对应的约束方程， 求出最优点坐标；求出最优点坐标；（4）将最优点坐标代入目标函数，求出最优值。将最优点坐标代入目标函数，求出最优值。ABCD P19 例：例： max f(x)=4x1+3x2 s.t. 3x1+4x212 3x1+3x210 4x1+2x28 x1, x2 00 x1x2343x1+4x2=123x1+3x2=104x1+2x2=8f =7f =52/5最优点最优点(x1* =4/5, x2*=12/5)f *=52/5 ABCD 例：例： max f(x)=4x1+ 3 x2 s.t. 3x1+4x212 3x1+3x210 4x1+2x28 x1, x2 00 x

8、1x23x1+4x2123x1+3x2104x1+2x28f =4f =8最优点：最优点：CD上的所有点上的所有点f *=8 2.3 2.3 线性规划问题的几种特殊情况线性规划问题的几种特殊情况2.3.12.3.1 有无限个最优解有无限个最优解2 例：例： max f(x)=4x1+3x2 s.t. 3x1+4x2 12 3x1+3x2 10 4x1+2x2 8 x1, x2 00 x1x23x1+4x2=123x1+3x2=104x1+2x2=82.3.22.3.2 无界可行域无界可行域f 增大方向增大方向数学上存在数学上存在但对于实际问题，可但对于实际问题，可能是遗漏或写错了约能是遗漏或写

9、错了约束条件！束条件！0 x1x23x1+4x2=123x1+3x2=104x1+2x2=82.3.32.3.3 可行域为空集可行域为空集 例：例： max f(x)=4x1+3x2 s.t. 3x1+4x2 12 3x1+3x2 10 4x1+2x2 8 x1, x2 02.4 2.4 线性规划的基本定理线性规划的基本定理2.4.1 2.4.1 凸集与顶点凸集与顶点凸集：凸集：设设M为为Rn中的一个集合，如果对中的一个集合，如果对M中任意两点为端点中任意两点为端点 的线段全部含于的线段全部含于M中，则称中，则称M为凸集。为凸集。 x(1) x(2) x(1) x(2) 直观理解：直观理解：内

10、部没有内部没有“洞洞”，边界不向内凹的形体，边界不向内凹的形体非凸集非凸集实例实例x(1) x(2) A B C D FE G H（球面上的所有（球面上的所有 点都是顶点）点都是顶点） 凸集的基本性质凸集的基本性质若若M1和和M2为凸集，为凸集，为正实数，则集合为正实数，则集合 （1）y|y =x, xM1 （2）y|y =x+z, xM1, zM2 （3）M1和和M2的交集的交集M1M2都为凸集。都为凸集。 顶点顶点如果凸集如果凸集M中的一个点中的一个点x不是不是M中任一线段的内点，则中任一线段的内点，则x是是M的一个顶点的一个顶点 K2.4.2 2.4.2 线性规划的两个重要性质线性规划的

11、两个重要性质基本定理基本定理（1）线性规划的可行域是一个凸集；）线性规划的可行域是一个凸集； （2）线性规划若存在可行点，则必存在可行域的顶点；）线性规划若存在可行点，则必存在可行域的顶点； 若存在最优点，则至少有一个顶点是最优点。若存在最优点，则至少有一个顶点是最优点。 定理的重要意义定理的重要意义（1）保证了顶点的存在性；）保证了顶点的存在性； （2）把一般要从无限个可行点中寻优最优点的问题）把一般要从无限个可行点中寻优最优点的问题 简化为仅在有限个顶点中确定最优点的问题简化为仅在有限个顶点中确定最优点的问题 问题：为什么顶点只有有限个？怎样找出顶点？问题：为什么顶点只有有限个？怎样找出顶

12、点？2.5 2.5 线性规划的标准形式线性规划的标准形式一般一般LP标准标准LP单纯形法求解标准单纯形法求解标准LP 思路：思路： min z=c1x1+ c2x2+ cnxns.t. a11x1+ a12x2+ a1nxn=b1 a21x1+ a22x2+ a2nxn=b2 am1x1+ am2x2+ amnxn=bm目标函数目标函数x10, x20, , xn0b10, b20, , bm0非负条件非负条件约束方程组约束方程组 LP LP的标准形式：的标准形式： 用矩阵和向量表示的用矩阵和向量表示的LPLP的标准形式：的标准形式：c=c1,c2,cnT 价值系数向量价值系数向量x=x1,x

13、2,xnT 决策向量决策向量b=b1,b2,bnT 要求向量要求向量a11 a12 a1n a21 a22 a2n am1 am2 amn A= 系数矩阵系数矩阵 min z = cTx s.t. Ax = b x 0 b 0 目标函数目标函数非负条件非负条件约束方程组约束方程组n LP的维数的维数 m LP的阶数的阶数2.5.1 2.5.1 将等式约束的右端化为非负将等式约束的右端化为非负 若某等式约束的若某等式约束的bi 0 2.5.2 2.5.2 化不等式约束为等式约束化不等式约束为等式约束 （1）若第若第 i 个约束条件为个约束条件为 ai1x1+ ai2x2+ ainxn bi 则引

14、入则引入“剩余变量剩余变量” wi 0 ，将不等式化为等式，将不等式化为等式 ai1x1+ ai2x2+ ainxnwi = bi （2）若第若第 i 个约束条件为个约束条件为 ai1x1+ ai2x2+ ainxn bi 则引入则引入“松弛变量松弛变量” wi 0 ，将不等式化为等式，将不等式化为等式 ai1x1+ ai2x2+ ainxnwi = bi 不利方面：维数增加了！不利方面：维数增加了！（在（在LP中存在可取任意值的自由变量中存在可取任意值的自由变量xj ，在标准形式中不允许存在），在标准形式中不允许存在）方法二：方法二： 引进新变量引进新变量xj0, xj”0, 作变换作变换x

15、j=xjxj”， 代入原问题消除代入原问题消除xj （参见（参见 PP25 例例2.5.1 )2.5.3 2.5.3 自由变量的处理自由变量的处理方法一：方法一：（消去法）（消去法） （1）先用松驰变量或剩余变量将约束条件中的不等式先用松驰变量或剩余变量将约束条件中的不等式 变为等式；变为等式； （2）把自由变量把自由变量xj 从某个等式约束中解出；从某个等式约束中解出； （3）把已解出的）把已解出的xj 代入其余约束及目标函数，代入其余约束及目标函数， 新问题中消去了新问题中消去了xj 。2.5.4 2.5.4 化最大值问题为最小值问题化最大值问题为最小值问题 若原问题为若原问题为 max

16、z = d1x1+d2x2+ dnxn则引入新目标函数则引入新目标函数 z = z ，而约束条件不变，而约束条件不变，原问题等价为原问题等价为 min z =- - d1x1- -d2x2- - -dnxn 上次课回顾上次课回顾 2.2 2.2 二维问题的图解法二维问题的图解法2.3 2.3 线性规划问题的几种特殊情况线性规划问题的几种特殊情况2.4 2.4 线性规划的基本定理线性规划的基本定理（1）线性规划的可行域是一个凸集；）线性规划的可行域是一个凸集； （2）线性规划若存在可行点，则必存在可行域的顶点；）线性规划若存在可行点，则必存在可行域的顶点； 若存在最优点，则至少有一个顶点是最优点

17、。若存在最优点，则至少有一个顶点是最优点。 2.5 2.5 线性规划的标准形式线性规划的标准形式 min z = cTx s.t. Ax = b x 0 b 02.6 2.6 单纯形法单纯形法 19471947年由年由美国数学家美国数学家George Dantzig提出，实践证明实用提出，实践证明实用 有效，但理论上不能保证不出现有效，但理论上不能保证不出现退化退化和和迭代循环迭代循环的问题。的问题。 后有人提出了修正单后有人提出了修正单 纯形法，有所简化，计算量小了，纯形法，有所简化，计算量小了， 且能避免无限循环问题且能避免无限循环问题 求解条件：求解条件：在在LPLP标准形式中，标准形式

18、中，系数矩阵系数矩阵A A的的秩秩 m m （即（即m m个约束方程相互独立）个约束方程相互独立）否则，否则，n = m，约束方程组只有唯一解，约束方程组只有唯一解 或无解或无解 n m,n m,在在A中任选中任选mm方阵，其行列式至少有一个不等于方阵，其行列式至少有一个不等于0自由度自由度大于零大于零2.6.1 2.6.1 基本概念基本概念( (一一) ) 基本解基本解对于标准形式的对于标准形式的LP， min z=c1x1+ c2x2+ cnxns.t. a11x1+ a12x2+ a1nxn=b1 a21x1+ a22x2+ a2nxn=b2 am1x1+ am2x2+ amnxn=bm

19、x10, x20, , xn0b10, b20, , bm0如何求如何求 min ?2.6.1 2.6.1 基本概念基本概念( (一一) ) 基本解基本解对于标准形式的对于标准形式的LP，如何求如何求 min ?开开 始始解方程组解方程组 Ax = b是否满足非负条件？是否满足非负条件？否否将解将解x代入目标函数代入目标函数是是目标函数值还能减小吗？目标函数值还能减小吗？是是否否得出最优解得出最优解？ 变量数变量数 n 方程个数方程个数m，可见其中的可见其中的 nm变量变量 可任意取值可任意取值非基本变量非基本变量基本变量基本变量基本解基本解（基本解的个数（基本解的个数 Cnm个个 ）令其中令

20、其中nm个个变量等于变量等于0解出剩余的解出剩余的m个变量个变量(x1,x2,xm, 0,0)( (二二) ) 可行基本解可行基本解称称满足非负条件满足非负条件（xi 0 , i=1,2,n）的基本解为）的基本解为可行基本解可行基本解? 可行基本解有什么用可行基本解有什么用 ？考察下列线性规划问题：考察下列线性规划问题： min z=200 x1500 x2 s.t. 1.5x1+5x240 2x1+4x240 x1, x2 0 x20 x1102030AB2468101.5x1+5x2402x1+4x240DC图解法可知图解法可知顶点顶点D为最优点为最优点 x1*=10, x2*=5, z*

21、=4500 z= 2000引入松弛变量，将上述引入松弛变量，将上述LP化为标准形式：化为标准形式： min z=200 x1500 x2 s.t. 1.5x1+5x2 +x3 =40 2x1+4x2 +x4=40 x1, x2 , x3 , x4 0非基本变量非基本变量基本变量基本变量目标函数值目标函数值z是否为可行基本解是否为可行基本解x1x2=0 x3=40, x4=400是是x1x3=0 x2=8, x4=8 4000是是x1x4=0 x2=10, x3= 10否否 5000 x2x3=0 x1=80/3, x4= 40/3否否 16000/3x2x4=0 x1=20, x3=10是是

22、4000 x3x4=0 x1=10, x2=5是是 45000基本解的个数基本解的个数 C426个个 引入松弛变量，将上述引入松弛变量，将上述LP化为标准形式：化为标准形式： min z=200 x1500 x2 s.t. 1.5x1+5x2 +x3 =40 2x1+4x2 +x4=40 x1, x2 , x3 , x4 0非基本变量非基本变量基本变量基本变量目标函数值目标函数值z是否为可行基本解是否为可行基本解x1x2=0 x3=40, x4=400是是x1x3=0 x2=8, x4=8 4000是是x1x4=0 x2=10, x3= 10否否 5000 x2x3=0 x1=80/3, x4

23、= 40/3否否 16000/3x2x4=0 x1=20, x3=10是是 4000 x3x4=0 x1=10, x2=5是是 4500082461020Cx20AB10D（最优）（最优）EFC对应于右图中的点对应于右图中的点BAEFCD(最优最优) LPLP的重要性质：的重要性质：可行域的每一个顶点与一个可行基可行域的每一个顶点与一个可行基本解相对应本解相对应 根据根据LP的基本定理，可知，的基本定理，可知，只须在有限个可行基本只须在有限个可行基本解中寻优！解中寻优！ ？如何最简便地得到可行基本解？如何最简便地得到可行基本解？如果从如果从LP的一般标准形式出发，如何获得可行基本解？的一般标准

24、形式出发，如何获得可行基本解？ min z=c1x1+ c2x2+ cnxns.t. a11x1+ a12x2+ a1nxn=b1 a21x1+ a22x2+ a2nxn=b2 am1x1+ am2x2+ amnxn=bmx10, x20, , xn0b10, b20, , bm0( (三三) ) 线性规划的典范形式线性规划的典范形式 x1 +a1,m+1xm+1+ a1nxn = b1 x2 +a2,m+1xm+1+ a2nxn = b2 xm +am,m+1xm+1+ amnxn = bm假设在假设在LP标准形式中的标准形式中的m个约束方程的形式是个约束方程的形式是优点：优点：令令m个特殊

25、变量为基本变量，其余个特殊变量为基本变量，其余nm个为非个为非基本变量，从而基本变量，从而可立即求得一个可行基本解可立即求得一个可行基本解 xi=bi, i=1,2,mxj=0, j=m+1,n 特点：特点：在在m个约个约束方程中有束方程中有m个个特殊变量，它们特殊变量，它们分别只在一个方分别只在一个方程中出现，且系程中出现，且系数为数为1 每一个典范形式与一个可行基本解相对应每一个典范形式与一个可行基本解相对应 ? 如何最简便地得到典范形式如何最简便地得到典范形式? min z=c1x1+ c2x2+ cnxns.t. a11x1+ a12x2+ a1nxn=b1 a21x1+ a22x2+

26、 a2nxn=b2 am1x1+ am2x2+ amnxn=bmx10, x20, , xn0b10, b20, , bm0 x1 +a1,m+1xm+1+ a1nxn = b1 x2 +a2,m+1xm+1+ a2nxn = b2 xm +am,m+1xm+1+ amnxn = bm? 消元法消元法？2.6.2 2.6.2 单纯形法的基本思路单纯形法的基本思路 开开 始始初始可行基本解初始可行基本解x(0)z0=z(x(0) 下一个可行基本解下一个可行基本解x(i)要求要求 zi=z(x(i)zi1 目标函数值还能减小吗？目标函数值还能减小吗？是是否否得出最优解得出最优解( (一一) ) 迭

27、代过程的一般描述迭代过程的一般描述初始顶点初始顶点下一个下一个顶点顶点在一小撮可行基本解中在一小撮可行基本解中寻优寻优 初始初始典范形式典范形式下一个下一个典范形式典范形式目标函数值下降目标函数值下降( (二二) ) 由一个典范形式化为另一个典范形式的迭代过程由一个典范形式化为另一个典范形式的迭代过程 x1 +a1, m+1xm+1+ a1nxn = b1 x2 +a2, m+1xm+1+ a2nxn = b2 xm+am, m+1xm+1+ amnxn = bm假设初始典范形式是假设初始典范形式是xi=bi, i=1,2,m 基本变量基本变量xj=0, j=m+1,n 非基本变量非基本变量初

28、始可行基本解为初始可行基本解为 x1, x2,xm , 0,0T 或或迭代过程分为两步：迭代过程分为两步：（1）从原来的非基本变量中选出一个（称为）从原来的非基本变量中选出一个（称为进基变量进基变量）使其成为新的基本变量）使其成为新的基本变量（2）从原来的基本变量中选出一个（称为）从原来的基本变量中选出一个（称为离基变量离基变量）使其成为新的非基本变量）使其成为新的非基本变量选进基变量和离基变量的原则：使目标函数下降最快选进基变量和离基变量的原则：使目标函数下降最快称为称为xs的相对的相对价值系数，价值系数， 或或检验数检验数1、选取进基变量、选取进基变量 方法方法：依次让某个非基本变量增加一

29、个单位值（：依次让某个非基本变量增加一个单位值（01），），而其而其余非基本变量仍取余非基本变量仍取0，分别计算目标函数的相应变化量，选出，分别计算目标函数的相应变化量，选出使目标函数下降最快的那个非基本变量作为进基变量使目标函数下降最快的那个非基本变量作为进基变量设非基本变量设非基本变量xs=0 1，xj=0, (j=m+1,n, j s) ， 那么那么 目标函数的变化量为目标函数的变化量为 rs =miisisacc1目标函数的变化量为目标函数的变化量为 rs = cs ci aismi1 min z= c1 x1 + c2 x2 + + cm xm + cs xs + cnxn x1 +

30、a1,m+1xm+1 + + a1s xs + a1nxn = b1 x2 +a2,m+1xm+1 + + a2s xs + a2nxn = b2 xi +ai,m+1xm+1 + + ais xs + ainxn = bi xm +am,m+1xm+1 + ams xs + amnxn = bm需要特别注意的是需要特别注意的是：rs计算公式中计算公式中cB是基本变量在目标函数中是基本变量在目标函数中的价值系数，的价值系数，cB中元素的顺序与约束方程组（从上到下）中基中元素的顺序与约束方程组（从上到下）中基本变量的顺序一致。本变量的顺序一致。rs = cs ci ais = cs cBTAsm

31、i1目标函数的变化量为目标函数的变化量为 rs = cs ci aismi1 min z= c1 x1 + c2 x2 + + cm xm + cs xs + cnxn x1 +a1,m+1xm+1 + + a1s xs + a1nxn = b1 x2 +a2,m+1xm+1 + + a2s xs + a2nxn = b2 xi +ai,m+1xm+1 + + ais xs + ainxn = bi xm +am,m+1xm+1 + ams xs + amnxn = bm！基本变量的检验数均为零基本变量的检验数均为零！（请参照（请参照PP29验证一下）验证一下）1、选取进基变量、选取进基变量

32、方法方法：依次让某个非基本变量增加一个单位值（：依次让某个非基本变量增加一个单位值（01），），而其而其余非基本变量仍取余非基本变量仍取0，分别计算目标函数的相应变化量，选出，分别计算目标函数的相应变化量，选出使目标函数下降最快的那个非基本变量作为进基变量使目标函数下降最快的那个非基本变量作为进基变量设非基本变量设非基本变量xs=0 1，xj=0, (j=m+1,n, j s) ， 那么那么 目标函数的变化量为目标函数的变化量为 rs =miisisacc1选取进基变量的原则选取进基变量的原则：当非基本变量相对价值系数的最小值当非基本变量相对价值系数的最小值 rJ=min rj 0，则相应的，

33、则相应的xi 随随 xJ 的增加而减小的增加而减小(xi =biaiJ xJ )，为了满足非负条件，为了满足非负条件，必须有必须有 LJLiJiaJababxiJmin0在在xJ增大时，增大时，首先不满足非首先不满足非负条件的负条件的xL选选为离基变量为离基变量应选取应选取xL为离基变量为离基变量迭代一步后可行基本解变为迭代一步后可行基本解变为 ： x1, x2, xL1, 0, xL+1, xm, 0 , 0, xJ, 0,0T2.6.3 单纯形表格与解题步骤单纯形表格与解题步骤 例例2.6.1 求解线性规划问题求解线性规划问题 min z=3x12x2 s.t. x1+2x2 4 3x1+

34、2x2 14 x1x2 3 x1, x2 0解：解：引入松驰变量引入松驰变量, 将原问题化为标准形式将原问题化为标准形式 min z=3x12x2 s.t. x1+2x2 x3 =4 3x1+2x2 +x4 =14 x1x2 +x5 =3 xi 0， i=1，2，3，4，5嘿嘿，刚好是嘿嘿，刚好是典范形式！典范形式！迭代迭代次数次数cB xB 价值系数价值系数 c b比值比值 （0）rT （1）rT （2）rT 3 2 0 0 0 x1 x2 x3 x4 x5 x3 x4 x50001 2 1 0 0 4 3 2 0 1 0 14 1 1 0 0 1 33 2 0 0 0 14/3 30=zx

35、3 x4 x1 0 03 0 1 1 0 1 7 0 5 0 1 3 5 1 1 0 0 1 3 7 1 0 5 0 0 3 9=zx3 x2 x1 023 0 0 1 1/5 8/5 6 0 1 0 1/5 3/5 1 1 0 0 1/5 2/5 4 0 0 0 1 0 14=z基本变量基本变量价值系数价值系数基本变量基本变量最优化问题最优化问题要求向量要求向量判判断断行行最优解为最优解为(4,1,6,0,0)T, z* = 14 min z=3x12x2 s.t. x1+2x2 x3 =4 3x1+2x2 +x4 =14 x1x2 +x5 =3 xi 0， i=1,5miisissaccr

36、1迭代迭代次数次数cB xB 价值系数价值系数 c b比值比值 （0）rT （1）rT （2）rT 3 2 0 0 0 x1 x2 x3 x4 x5 x3 x4 x50001 2 1 0 0 4 3 2 0 1 0 14 1 1 0 0 1 33 2 0 0 0 14/3 30=zx3 x4 x1 0 03 0 1 1 0 1 7 0 5 0 1 3 5 1 1 0 0 1 3 7 1 0 5 0 0 3 9=zx3 x2 x1 023 0 0 1 1/5 8/5 6 0 1 0 1/5 3/5 1 1 0 0 1/5 2/5 4 0 0 0 1 0 14=z最优解为最优解为(4,1,6,0,

37、0)T, z* = 14 0=z！基本变量的检验数总为零！基本变量的检验数总为零！2.6.4 2.6.4 退化与循环退化与循环 （一）（一）退化的可行基本解退化的可行基本解定义：定义：基本变量中有取零的可行基本解称为退化的可行基本解。基本变量中有取零的可行基本解称为退化的可行基本解。（1） 初始典范形式的基本解初始典范形式的基本解 就是退化的；就是退化的；( bi 中有等于零的中有等于零的 )（2）迭代过程求离基变量时，迭代过程求离基变量时， 若有一个以上的比值成为若有一个以上的比值成为 最小比值时最小比值时, 则新的可行基本解必是退化的。则新的可行基本解必是退化的。可能出现退化的可行基本解的

38、情况：可能出现退化的可行基本解的情况：（二）（二）循环循环在迭代过程中如出现退化的可行基本解，即出现等于在迭代过程中如出现退化的可行基本解，即出现等于0的的基本变量，如基本变量，如 xk = bk = 0 ，则下次迭代会出现什么情况呢，则下次迭代会出现什么情况呢？假设假设xJ被选为进基变量，则被选为进基变量，则xk=bkakJ xJ，比值，比值( bk/akJ )0 肯定为最小，所以肯定为最小，所以xk被选为离基变量。下一步迭代时，离基被选为离基变量。下一步迭代时，离基变量变量xk=0，则进基变量，则进基变量xJ =0，所以目标函数值没有下降，所以目标函数值没有下降，出现无限循环情况。出现无限

39、循环情况。 1976年，年，Bland 提出在迭代过程中遵循两个规则，可避免出提出在迭代过程中遵循两个规则，可避免出现循环问题：现循环问题：（1）如果有几个非基本变量如果有几个非基本变量xj的相对价值系数为负时，那么的相对价值系数为负时，那么选其中下标选其中下标 最小的为进基变量，即如最小的为进基变量，即如 J=minj|rj 0，就选，就选xJ为进基变量为进基变量 ；（选第一个（选第一个rj为负的）为负的）（2）选离基变量选离基变量xL时，若同时出现几个最小比，取其中下标时，若同时出现几个最小比，取其中下标最小的基本变量为离基变量。最小的基本变量为离基变量。 这样处理，收敛速度会变慢，迭代次

40、数变多，为什么呢？这样处理，收敛速度会变慢，迭代次数变多，为什么呢？到此为止，如果给定的到此为止，如果给定的LP为典范形式，我们马上就能通过为典范形式，我们马上就能通过单纯形法求出最优解。单纯形法求出最优解。但问题是如何由标准形式化为典范但问题是如何由标准形式化为典范形式？形式？用消去法？用消去法？没有普遍意义没有普遍意义 思路：思路：如果最初的标准形式不是典范形式，引入人工变量如果最初的标准形式不是典范形式，引入人工变量构造一个以典范形式出现的新问题，然后以单纯形法解之。构造一个以典范形式出现的新问题，然后以单纯形法解之。 2.6.5 2.6.5 求初始可行基本解求初始可行基本解 （一）（一

41、）大大M法法+xn+1+xn+2+xn+mMxn+1 Mxn+2 + Mxn+m+m min z=c1x1+ c2x2+ cnxn s.t. a11x1+ a12x2+ a1nxn =b1 a21x1+ a22x2+ a2nxn =b2 am1x1+ am2x2+ amnxn =bm xi0, i=1,2,n b10, b20, , bm0原问题原问题引入人工变量，构造新问题引入人工变量，构造新问题其中，其中，xn+1 ，xn+2 ， xn+m为人工变量，为人工变量，M为其价值系数，为其价值系数，是一个充分大的正数是一个充分大的正数只要只要M取得足够大，新问题的最优解与原问题的最优解取得足够大

42、，新问题的最优解与原问题的最优解是等价的：是等价的：(1) 若新问题不存在最优解，即某些人工变量不等于零，若新问题不存在最优解，即某些人工变量不等于零， 则原问题不存在最优解；则原问题不存在最优解； min z=c1x1+ c2x2+ cnxnMxn+1 Mxn+2 + Mxn+m反证法：反证法：如果原问题有解，这个解加上所有的人工变量，并令人工如果原问题有解，这个解加上所有的人工变量，并令人工变量取零值，构成新问题的一个可行解，对应这个可行解，变量取零值，构成新问题的一个可行解，对应这个可行解，新问题的目标函数值为一有限值，导致矛盾！新问题的目标函数值为一有限值，导致矛盾！ 只要只要M取得足

43、够大，新问题的最优解与原问题的最优解取得足够大，新问题的最优解与原问题的最优解是等价的：是等价的：(1) 若新问题不存在最优解或有些人工变量不等于零，若新问题不存在最优解或有些人工变量不等于零， 则原问题不存在最优解；则原问题不存在最优解；(2) 新问题最优解中人工变量都取零，去掉人工变量即为新问题最优解中人工变量都取零，去掉人工变量即为 原问题的最优解。原问题的最优解。例例2.6.2 用大用大M法求解法求解LP问题：问题： min z=4x1x2x3 s.t. 2x1+x2 +2x3=4 3x1+3x2 +x3=3 x1, x2 ,x30解：解：引入人工变量引入人工变量x4、x5，构造新问题

44、：，构造新问题： min z=4x1x2x3+Mx4+Mx5 s.t. 2x1+x2 +2x3+x4 =4 3x1+3x2 +x3 +x5 =3 xi0, i=1, 2, 3, 4, 5迭代迭代次数次数cB xB 价值系数价值系数 c b比值比值 （0）rT （1）rT （2）rT （3）rT 4 1 1 M M x1 x2 x3 x4 x5 x4 x5MM 2 1 2 1 0 4 3 3 1 0 1 345M 14M 13M 0 0 217M=zx4 x1 M 4 0 1 4/3 1 2/3 2 3/2 3 0 3M 1/34/3M 0 4/3+5/3M 42M=z最优解为最优解为(0,2/

45、5,9/5)T, z* = 11/5 1 1 1/3 0 1/3 1x3 x1 1 4 0 3/4 1 3/4 1/2 3/2 2/5 0 13/4 0 1/4+M 3/2+M 7/2=z 1 5/4 0 1/4 1/2 1/2x3 x2 1 1 3/5 0 1 3/5 1/5 9/5 13/5 0 0 2/5+M 1/5+M 11/5=z 4/5 1 0 1/5 2/5 2/5+xn+1+xn+2+xn+m+m min z=c1x1+ c2x2+ cnxn s.t. a11x1+ a12x2+ a1nxn =b1 a21x1+ a22x2+ a2nxn =b2 am1x1+ am2x2+ a

46、mnxn =bm xi0, i=1,2,n b10, b20, , bm0原问题原问题引入人工变量，构造新问题引入人工变量，构造新问题其中其中xn+1 ，xn+2 ， xn+m为人工变量为人工变量（二）（二）两阶段法两阶段法min z=xn+1 xn+2 + xn+m第一阶段：第一阶段：在约束条件中引入人工变量，构造一个典范形式的在约束条件中引入人工变量，构造一个典范形式的 新问题，目标函数为求所有人工变量之和的最小值。新问题，目标函数为求所有人工变量之和的最小值。 用单纯形法求解上述新问题，有两种可能：用单纯形法求解上述新问题，有两种可能： （1）新目标函数的最小值大于零新目标函数的最小值大

47、于零 ( 即最优解中至少有一个人工即最优解中至少有一个人工 变量取正值变量取正值)，则原问题无解。，则原问题无解。 反证法：反证法： min z=xn+1 xn+2 + xn+m 如果原问题有解，这个解加上所有的人工变量，并令如果原问题有解，这个解加上所有的人工变量，并令人工变量取零值，构成新问题的一个可行解，对应这个可人工变量取零值，构成新问题的一个可行解，对应这个可行解，新问题的目标函数值为零，导致矛盾！行解，新问题的目标函数值为零，导致矛盾！ （2）新目标函数的最小值为零，此时人工变量必为零。从最新目标函数的最小值为零，此时人工变量必为零。从最 后后所得的典范形式中去掉所有人工变量，即得原问题的一个所得的典范形式中去掉所有人工变量，即得原问题的一个典范形式，为第二阶段作好准备；典范形式，为第二