运筹02线性规划与单纯形法素材.ppt

《运筹02线性规划与单纯形法素材.ppt》由会员分享，可在线阅读，更多相关《运筹02线性规划与单纯形法素材.ppt（132页珍藏版）》请在三一办公上搜索。

1、Chapter2 线性规划与单纯形法,Linear Programming and Simplex Algorithm,1.线性规划问题及其数学模型2.线性规划问题的几何意义3.单纯形法4.单纯形法的计算步骤5.单纯形法的进一步讨论6.应用举例,线性规划是运筹学的一个重要分支。自1947年丹捷格（G.B.Dantzig）提出了线性规划问题求解的方法单纯形法之后，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都

2、可以发挥作用。,引言,线性规划研究的问题：如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。,2.1 线性规划问题及其数学模型,2.1.1 问题的提出,例1 某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的损耗，如表1.1所示。,表1-1,该工厂每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排计划使该工厂获利最多？,（1）确定决策变量,（2）确定目标函数,（4）确定变量取值限制,（3）确定约束条件,得到本问题的数学模型为:,这就是一个最简单的线性规划模型。,例 2 靠近某河流有两个化工厂(见图1-1)，流经第一化工

3、厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。,化工厂1每天排放含有某种有害物质的工业污水2万立方米，化工厂2每天排放的工业污水为1.4万立方米。从化工厂1排出的污水流到化工厂2前，有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。因此两个工厂都需处理一部分工业污水。化工厂1处理污水的成本是1000元/万立方米,化工厂2处理污水的成本是800元/万立方米。问:在满足环保要求的条件下，每厂各应处理多少工业污水，使两个工厂处理工业污水的总费用最小。,（1）确定决策变量 设第一化工厂每天处理工业污水x1万立方米，第二化工厂每天处理工污水

4、x2万立方米。,（2）确定目标函数,（3）确定约束条件,从第一化工厂到第二化工厂之间，河流中工业污水含量不大于0.2%，由此可得近似关系式,流经第二化工厂后，河流中的工业污水含量仍要不大于0.2%，这时有近似关系式,（4）确定变量取值限制,得到本问题的数学模型为：,上述两个问题具有的共同特征：,每一个线性规划问题都用一组决策变量(x1,x2,xn)表示某一方案，这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的；都有关于各种资源和资源使用情况的技术数据，并存在可以量化的约束条件，这些约束条件可以用一组线 性等式或线性不等式来表示;都有一个达到某一目标的要求，可用决策变量的线性函

5、 数(称为目标函数)来表示。按问题的要求不同，要求目 标函数实现最大化或最小化。,决策变量及各类系数之间的对应关系,满足以上特征的数学模型，我们称之为线性规划问题，简单的说线性规划问题是求一个线性目标函数满足一组线性约束条件的极值问题。,线性规划模型的一般形式,【例】常山机器厂生产、两种产品。这两种产品都要分别在A、B、C三种不同设备上加工。按工艺资料规定,生产每件产品需占用各设备分别为2h，4h，0h,生产每件产品需占用各设备分别为2h，0h，5h。已知各设备计划期内用于生产这两种产品的能力分别为12h，16h，15h,又知每生产一件产品企业能获得2元利润,每生产一件产品企业能获得3元利润,

6、问该企业应安排生产两种产品各多少件,使总的利润收入为最大。,2.1.2 线性规划的数学模型,1分析实际问题 2确定决策变量3确定目标函数 4找出约束条件 5整理、写出数学模型,【运输工具配载问题】有一辆运输卡车，载重2.5t，容积18用来装载如下两种货物：箱装件：125kg，0.4包装件：20kg，1.5请问：如何装配，卡车所装的物件个数最多？,1.分析问题：这是一个运输工具的配载问题，给出了最大载重和容积，要求装最多的物件。2.确定决策变量：此问题的决策变量有两个：箱装件和包装件，因此分别设为X1,X2.3.确定目标函数：本问题的目标要求为装物件个数最多：Max z=X1+X2 4.找出约束

7、条件：约束条件有两个：载重和容积约束，因此列出约束条件：容积约束：0.4X1+1.5X218载重约束：125X1+20X2 2500非负约束：X10，X2 0.5.整理、写出数学模型,南京某市场调查公司受一洗涤剂厂委托，调查消费者对新型洗衣粉的了解与反应，对不同家庭采用不同调查方式的费用见表，洗涤剂厂对市场调查公司提出了以下几个方面的具体要求：（1）调查800个家庭。（2）被调查家庭中，至少有300个是没有孩子的家庭，同时至少有300个是有孩子的家庭。（3）至少对500个被调查家庭采用问卷式书面调查，其余家庭可用口头调查。（4）在有孩子的被调查家庭中，至少有50%的家庭采用问卷式书面调查。（5

8、）在没有孩子的被调查家庭中，至少有60%的家庭采用问卷式书面调查。,市场调查计划优化问题,投资问题 上海某投资公司在今后三年内有四种投资机会，第1种是3年内每年年初投资，年底可获利润20%，并可将本金收回，第2种是在第一年的年初投资，第二年年底可获利润50%，并将本金收回。但该项投资不得超过2000万。第3种是在第二年的年初投资，第三年年底收回本金，并获利润60%，但该项目投资不得超过1500万，第4种是在第三年的年初投资，于该年年底收回本金，且获利润40%，但该项投资不得超过1000万，现在该公司拿出3000万，问如何制定投资计划，使得第三年年末本利和最大。,配料问题某糖果厂用原料A、B、C

9、加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表所示，问该厂每月应生产这三种牌号糖果各多少千克，使得该厂获利最大？试建立这个问题的线性规划的数学模型。,下料问题 某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋90根，长度为4米的钢筋60根，问怎样下料，才能使所使用的原材料最省?,（1）每个行动方案可用一组变量（x1，xn）的值表示，这些变量一般取非负值；（2）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示；（3）有一个需要优化的目标，它也是变量的线性函数。具备以上

10、三个特点的数学模型称为线性规划（Linear Programming，简记为LP）,下料问题练习：有一批原料钢材(如钢管、钢筋、角钢、钢梁等)，每根长7.4m现需做100套钢架，每套利用长2.9m、2.1m、1.5m的钢材各一根问如何下料，才能使所用的原料最省?,有A、B、C三个工地，每天需要水泥各为17、18、15百袋。为此甲、乙两个水泥厂每天各生产23百袋和27百袋水泥供应这三个工地。其单位运价如下表，求最佳调运方案。,线性规划模型的一般形式,Ci为价值系数，ai为技术系数，bi为限制系数,2.1.3 线性规划问题的标准形式,目标函数为求最大值，约束条件为等式约束，约束方程右端常数项为非负

11、数值，决策变量取非负数值。,用向量形式表示的标准形式线性规划,价值向量,决策向量,系数向量,资源向量,用矩阵形式表示的标准形式线性规划,这时只需将目标函数最小化变换为求目标函数最大化，,必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号。,如何将一般线性规划转化为标准形式的线性规划？,引进一个松弛变量，把原不等式约束用两个约束来等价地替换,设约束条件为,（2）约束方程为不等式 有两种情况：一种是约束方程为“”不等式，则可在“”不等式的左端加入非负松弛变量，把原“”不等式变为等式。,另一种是约束方程为“”不等式，则可在“”不等式的左端减去一个非负剩余变量把原“”不等式

12、变为等式。,引进一个剩余变量，把原不等式约束用两个约束来等价地替换,设约束条件为,（4）在标准形式中，要求约束条件的右端项bi0，否则等式两端乘以-1。下面举例说明。,可以令，其中。,即用两个非负变量之差来表示一个无符号限制的变量，当然 的符号取决于 和 的相对大小。,（3）若存在取值无约束的变量,例3 将例1的数学模型化为标准形式的线性规划。,例4 将下述线性规划问题化为标准形式线性规划,(1)用x4x5替换x3，其中x4，x50；(2)在第一个约束不等式左端加入松弛变量x6；(3)在第二个约束不等式左端减去剩余变量x7；(4)令z=z，将求min z 改为求max z即可得到该问题的标准型

13、。,例4 例4的标准型,2.1.4 线性规划问题解的概念,可行解满足约束条件（1-5）、（1-6）式的解称为线性规划问题的可行解，其中使目标函数达到最大值的可行解称为最优解。,考虑LP的标准型,称 为基向量，与基向量 相对应的变量 称为基变量，否则称为非基变量。,设A是约束方程组的 维系数矩阵，其秩为m。,B是 A 中m 阶非奇异子矩阵(|B|0)，则称B是线性规划问题的一个基，这就是说，矩阵B是由A中m个线性无关的列向量组成。为不失一般性,可设B是A中的前m列，即,2 基,注：（1）对应于给定的基B，基解是唯一的。（2）基解中非基变量取零值，非零分量的数目不超过m。（3）基解一定满足等式约束

14、，但不一定满足非负约束。,称 为对应于基B的基解。,令所有非基变量得到,因B可逆，该方程有唯一解。,把约束方程（1-5）式写成,例 在下述线性规划问题 中列出全部的基并确定相应的基解。,解：将该线性规划问题化为标准形：,只要从A的列向量中找出3个线性无关的列向量就组成该线性规划问题的一个基。,取A的第一、二、三列组成子矩阵 易见，故B1是该线性规划问题的一个基。,令非基变量，则约束方程变为,基变量为，非基变量。,令非基变量为零，求解线性方程组，就可找出全部基解。,解得,取A的第一、四、五列得到基，相应地基解,取A的第一、三、五列得到基，相应地基解,类似地取A的第一、二、四列得到基，相应地基解,

15、取A的第一、二、五列得到基，相应地基解,对于A的第一、三、四列组成的矩阵易见，故 不能作成一组基。,取A的第二、三、四列得到基 相应地基解取A的第二、四、五列得到基 相应地基解取A的第三、四、五列得到基，相应地基解,同理，也不能作成一组基。,（1）基解的数目最多是 个。（2）基解中非零分量的个数小于m个时，该基解是退化解。,3 基可行解满足非负约束条件的基解称为基可行解。,以下讨论时，假设不出现退化的情况，即基解中非零分量恰为m个。,说明：,4 可行基对应于基可行解的基称为可行基。,几何上，图中A、B、C、D、E、F、G、H对应X（i）（i=1，2，,8）,直观上，可行解即可行域中的点，基解是

16、约束直线的交点，基可行解即可行域的顶点。它们之间的关系可以用图1-6表示。,在下述线性规划问题 列出一个基并确定相应的基解。,线性规划问题的求解方法,一 般 有两种方法,图 解 法单纯形法,两个变量、直角坐标三个变量、立体坐标,适用于任意变量、但必需将一般形式变成标准形式,下面我们分析一下简单的情况 只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。,2.1.2 图解法,例1 一个二维线性规划问题，因而可用图解法直观地进行求解。,目标值在（4，2）点，达到最大值14,（1）无穷多最优解(多重最优解)，见图1。（2

17、）无界解，见图2。（3）无可行解，见图。3,通过图解法，可观察到线性规划的解可能出现的几种情况：,目标函数 max z=2x1+4x2,图1 无穷多最优解（多重最优解）,max z=2x1+3x2 4x1 16 x1，x2 0 则x2，z。即存在无界解。,图2 无界解,当存在相互矛盾的约束条件时，线性规划问题的可行域为空集。例如，如果在例1的数学模型中增加一个约束条件:则该问题的可行域即为空集，即无可行解.,无可行解的情形,图3 不存在可行域,思考：1）线性规划的可行域是一个什么形状？2）最优解在什么位置获得？,结论：,问题：性质2有何重要意义？,凸集：如果集合C中任意两个点X1、X2，其连线

18、上的所有点也都是集合C中的点，称C为凸集。,凸集,凸集,不是凸集,2.2 线性规划问题的几何意义1 基本概念,试判断下列图形是否凸集：,凸组合,设 是n维欧氏空间En中的k个点。若存在 且 使则称X为 的凸组合。,设K是凸集，若X不能用K中两个不同的点的凸组合表示为则称X是K的一个顶点或极点。,2 顶点,注：X是凸集K的顶点即X不可能是K中某一线段的内点，而只能是K中某一线段的端点。,凸集,凸集,顶 点,定理1：若线性规划问题存在可行解，则该问题的可行域是凸集。引理1:线性规划问题的可行解为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。定理2：线性规划问题的基可行解X对应可行域

19、(凸集)的顶点。定理3：若问题存在最优解，一定存在一个基可行解是最优解。（或在某个顶点取得）,定理2刻划了可行域的顶点与基可行解的对应关系，顶点是基可行解，反之，基可行解一定是顶点，但它们并非一一 对应，有可能两个或几个基可行解对应于同一顶点（退化基可行解时）。,定理3描述了最优解在域中的位置，若最优解唯一，则最优解只能在某一顶点上达到，若具有多重最优解，则最优解是某些顶点的凸组合，从而最优解是可行域的顶点或界点，不可能是可行域的内点。,若线性规划的可行解集非空且有界，则一定有最优解；若可行解集无界，则线性规划可能有最优解，也可能没有最优解。,几点结论,若线性规划问题有可行解,则可行域是一个凸

20、多边形或凸多面体(凸集),且仅有有限个顶点(极点);线性规划问题的每一个基可行解都对应于可行域上的一个顶点(极点);若线性规划问题有最优解,则最优解必可在基可行解(极点)上达到;线性规划问题的基可行解(极点)的个数是有限的,不会超过 个.,上述结论说明:线性规划的最优解可通过有限次运算在基可行解中获得.,丹捷格教授在一次演说中，形象而风趣地说明了单纯形解法的奇效：设给70个人分配70项任务，每人一项。如果每人完成各项任务所需要付出的代价（时间、工资）都知道，要寻求代价最小的方案。所有的可行方案共有70！种。70！比 还要大。如果用穷举法，逐个来比较的话，即使用 个地球或 个太阳的容量来装计算机

21、，这些计算机从150亿年前开始，全部投入计算，大约要算到太阳熄灭才有答案。而用单纯形法软件，几秒钟就可以给出答案。,单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B.Dantzig）提出。,2.3 单纯形法,单纯形法(Simplex Algorithm)先求出一个初始基可行解并判断它是否最优，若不是最优，再换一个基可行解并判断，直到得出最优解或无最优解。它是一种逐步逼近最优解的迭代方法。,优,跨越式寻找最优解,2.3.1 单纯形法的基本思路和原理,单纯形法的思路,找出一个初始可行解,是否最优,转移到另一个基本可行解（找出更大的目标函数值）,最优解,是,否,循环,核

22、心是：变量迭代,结束,关键的3步：1、找出一个初始基本可行解(单位矩阵)2、最优性检验(检验数 j)3、基变换(换入变量与换出变量),标准型：,例6 用单纯形法求下列线性规划的最优解,2.3.3 最优性检验与解的判别,设 是LP的一个基，为相应的基可行解。将约束写成非基变量表示基变量的形式，不妨设,思路：对一个给定的基可行解，把目标函数用非基变量表示，非基变量前的系数称为检验数。当所有非基变量的检验 数均小于等于零时，当前解即最优解。,2.3.3 最优性检验与解的判别,将（1-24）式代入目标函数,令,则,法则1 最优性判定法则法则2 换入变量确定法则设,，则xk为换入变量。法则3 换出变量确

23、定法则,bi,xj0(i=1,2,m;j=1,2,n),2.4.1 单纯形法的表格形式,表称为初始单纯形表，每迭代一步构造一个新单纯形表。,表的说明XB列中填入基变量，这里是x1，x2,，xm；CB列中填入基变量的价值系数，这里是c1,c2,cm；它们是与基变量相对应的；b列中填入约束方程组右端的常数；cj行中填入变量的价值系数c1,c2,cn；i列的数字是在确定换入变量后，按规则计算后填入；最后一行称为检验数行，对应各非基变量xj的检验数是,标准型：,(1)取松弛变量x3,x4,x5为基变量，它对应的单位矩阵为基。这就得到初始基可行解X(0)=(0,0,8,16,12)T。将有关数字填入表中

24、，得到初始单纯形表，见表1-3。表中左上角的 cj 是表示目标函数中各变量的价值系数。在CB列填入初始基变量的价值系数，它们都为零。,表 1-3,计算非基变量的检验数 各非基变量的检验数为1=c1z1=2(01+04+00)=22=c2z2=3(02+00+04)=3,(4)以4为主元素进行旋转运算或迭代运算，即初等行变换，使P2变换为(0,0,1)T,在XB 列中将x2 替换x5,于是得到新表1-4。,换人变量,换出变量,主元素,表1-4,(5)检查表1-4的所有cjzj,这时有c1z1=2；说明x1应为换入变量。重复(2)(4)的计算步骤，得表1-5。,换人变量,换出变量,因为还存在检验数

25、0，继续进行迭代。,主元素,表1-5,(6)表1-6最后一行的所有检验数都已为负或零.这表示目标函数值已不可能再增大，于是得到最优解.,表1-6,X*=X(3)=(4,2,0,0,4)T目标函数的最大值 z*=14,练习1,练习2 用单纯形法求下列线性规划的最优解,解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:,2）求出线性规划的初始基可行解，列出初始单纯形表。,检验数,3）进行最优性检验,如果表中所有检验数，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。,4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表,确定换入基的变量。选择，对应的变量xj作

26、为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：，其对应的xk作为换入变量。确定换出变量。根据下式计算并选择，选最小的对应基变量作为换出变量。,用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。5）重复3）、4）步直到计算结束为止。,单纯形法的计算步骤,换入列,bi/ai2，ai20,40,10,换出行,将3化为1,5/3,1,18,0,1/3,0,1/3,10,1,1/3,30,30,0,5/3,0,4/3,乘以1/3后得到,1,0,3/5,1/5,18,0,1,1/5,2/5,4,0,0,1,1

27、,将线性规划问题化成标准型。找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。计算各非基变量xj的检验数j=Cj-CBPj，若所有j0，则问题已得到最优解（唯一最优或无穷多最优解），停止计算，否则转入下步。在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此问题是无界解，停止计算，否则转入下步。根据maxjj0=k原则，确定xk为换入变量(进基变量)，再按规则计算：=minbi/aik|aik0=bl/aik 确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。以aik为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik变为1，同列中其它元素为

28、0，转第 步。,单纯形法的计算步骤,原问题解的类型的判断 对于所有约束条件都是0的线性规划问题的解的类型有三种：唯一最优解无穷多最优解无界解,最优性检验与解的判别,原问题具有无界解,判断原问题解的类型(一),原问题具有唯一最优解:X*=(4,6,4,0,0)T，Z*=42,判断原问题解的类型(二),判断原问题解的类型(三),原问题具有无穷多个最优解,判断原问题解的类型(四),原问题具有唯一最优解,标准型：,2.5单纯形法的进一步讨论,max z=3x1-x2-x3s.t.x1-2x2+x3 11-4x1+x2+2x3 3-2x1+x3=1 x1,x2,x30,max z=3x1-x2-x3+0

29、 x4+0 x5 x1-2x2+x3+x4=11-4x1+x2+2x3 x5=3-2x1+x3=1 x1,x2,x3,x4,x5 0,2.5单纯形法的进一步讨论,设线性规划问题的约束条件.其中没有可作为初始基的单位矩阵，则分别给每个约束方程加入人工变量xn+1,xn+m，得到,2.5单纯形法的进一步讨论,以xn+1,xn+m为基变量，便可得到一个mm单位矩阵。令非基变x1,xn为零，便可得到一初始基可行解X(0)=(0,0,0,b1,b2,bm)T,注：人工变量与松弛变量和剩余变量不同。松弛变量、剩余变量可以取零值，也可以取正值，而人工变量只能取零值。一旦人工变量取正值，那么有人工变量的约束方

30、程和原始的约束方程就不等价了，这样所求得的解就不是原线性规划的解。,这就要求经过基变换将人工变量从基变量中逐个替换出来。基变量中不再含有非零的人工变量，这表示原问题有解。若在最终表中当所有cjzj0，而在其中还有某个非零人工变量，这表示原问题无可行解。如何求解含有人工变量的线性规划问题?,两种方法大M法两阶段法,2.5.1 人工变量法,两阶段法,两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划分两阶段求解。,第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行解第二阶段以第一阶段得到的基础可行解为初始解，采用原单纯型法求解若第一阶段结束时，人工变量

31、仍在基变量中，则原问题无解,具体步骤,第一阶段：构造一个只包含人工变量的最大化目标函数，人工变量的价值系数为-1（其他变量的价值系数为0），在原约束条件下利用单纯形法求解；第二阶段：在第一阶段的最终单纯形表的基础上替换成原目标函数，去掉人工变量，继续求解。,用二阶段法求解下列线性规划问题,max z=3x1-x2-x3s.t.x1-2x2+x3 11-4x1+x2+2x3 3-2x1+x3=1 x1,x2,x30,解:引入松弛变量x4,x5，标准形为：第一阶段：引入人工变量x6,x7，构造一个只包含人工变量的目标函数：max w=-x6 x7 x1-2x2+x3+x4=11 s.t.-4x1+

32、x2+2x3 x5+x6=3-2x1+x3+x7=1 xj0（j=1,2,7）用单纯形法求解得：,max z=3x1-x2-x3+0 x4+0 x5 x1-2x2+x3+x4=11-4x1+x2+2x3 x5=3-2x1+x3=1 x1,x2,x3,x4,x5 0,x1 x2 x3 x4 x5 x6 x7,CB XB b,CB,j,i,0 0 0 0 0-1-1,x4x6x7,0-1-1,11 1-2 1 1 0 0 0,3-4 1 2 0-1 1 0,1-2 0 1 0 0 0 1,0 1 0 0-1 0-3,11/13/21/1,x4x6x3,0-1 0,10 3-2 0 1 0 0-1,

33、1 0 1 0 0-1 1-2,1-2 0 1 0 0 0 1,-6 1 3 0-1 0 0,i,-1/1-,j,x1 x2 x3 x4 x5 x6 x7,CB XB b,CB,j,0 0 0 0 0-1-1,x4x2x3,0 0 0,12 3 0 0 1-2 2-5,1-2 0 1 0 0 0 1,1 0 1 0 0-1 1-2,0 0 0 0 0-1-1,最优解为:X*=(x1,x2,x3,x4,x5,x6,x7)T=(0,1,1,12,0,0,0)T 最优值:Z*=0 人工变量x6,x7皆为0，说明原问题具有可行解，并找到原问题的一个可行基（单位矩阵p4,p2,p3）,进入第二阶段:,m

34、ax z=3x1-x2-x3,x1 x2 x3 x4 x5 x6 x7,CB XB b,CB,j,0 0 0 0 0-1-1,x4x2x3,0 0 0,12 3 0 0 1-2 2-5,1-2 0 1 0 0 0 1,1 0 1 0 0-1 1-2,0 0 0 0 0-1-1,x1 x2 x3 x4 x5,CB XB b,CB,j,3-1-1 0 0,x4x2x3,0-1-1,12 3 0 0 1-2,1-2 0 1 0 0,1 0 1 0 0-1,1 0 0 0-1,i,12/3-,0 0 0-1/3-1/3,x1x2x3,3-1-1,9 0 0 1 2/3-4/3,j,1 0 1 0 0-

35、1,4 1 0 0 1/3-2/3,x1 x2 x3 x4 x5,CB XB b,CB,j,3-1-1 0 0,x4x2x3,0-1-1,12 3 0 0 1-2,1-2 0 1 0 0,1 0 1 0 0-1,1 0 0 0-1,i,12/3-,所以原线性规划问题具有唯一最优解:最优解：X*=(4,1,9)T最优值：Z*=2,练习：两阶段法求解,无可行解的情况：最终单纯形表得基变量中，仍然有非零人工变量,则原问题无可行解。,在单纯形法计算过程中，基变量有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这称之为退化。,2.5.3退化问题,得到最优解x11，x20，x

36、32，x41，x50，x60，其最优值为5。,在单纯形法计算过程中，基变量有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这称之为退化。退化的出现原因是模型中存在多余的约束,使多个基可行解对应同一顶点.当存在退化问题时,就可能出现迭代计算的循环(尽管可能性极其微小)。,勃兰特（Bland）法则。首先我们把松弛变量（剩余变量）、人工变量都用 xj 表示，一般松弛变量（剩余变量）的下标号列在决策变量之后，人工变量的下标号列在松弛变量（剩余变量）之后，在计算中，遵守以下两个规则：,（1）在所有检验数大于零的非基变量中，在存在两个和两个以上相等的检验数时，选一个下标最小的

37、作为入基变量。（2）在存在两个和两个以上最小比值时，选一个下标最小的基变量作为出基变量。这样就一定能避免出现循环。,线性规划的练习题,习题一 下表为求极大化的单纯形表，问表中a1,a2,c1,c2,d为何值及表中变量为哪一类型时，（1）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3）表中解为退化的可行解；（4）下一步迭代将以x1替代基变量x5;（5）该问题具有无界解；（6）该问题无可行解；,习题二 线性规划的目标函数是maxZ,在用标准的单纯形法求解的过程中，得到下表（其中a、b是常数，部分数据有缺失）,（1）在所有的空格中填上适当的数（其中可含a、b参数）（2）判断以下四种情况在什

38、么时候成立，并简要说明理由。1.此解为最优解，试写出相应的基解和目标函数值；2.此解为最优解，且此规划有无穷多最优解；3.此规划有无界解；4.此解不是最优解，且能用单纯形法得到下一个基可行解。,习题三 已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到的表如下所示，试求括号中未知数al的值。,Thank You!,Add your company slogan,人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。,