(运筹学大作业)单纯性法与对偶单纯性法比较
- 格式:doc
- 大小:387.29 KB
- 文档页数:8
《管理运筹学》第四版第6章单纯形法的灵敏度分析与对偶课后习题解析《管理运筹学》第四版第6章单纯形法的灵敏度分析与对偶课后习题解析《管理运筹学》第四版课后习题解析第6章单纯形法的灵敏度分析与对偶1(解:(l)cl?24⑵ c2?6(3)cs2?82(解:(1)cl??0.5(2)?2?c3?0(3)cs2?0.53(解:(1)bl?250(2)0?b2?50(3)0?b3?1504(解:(1)bl??4(2)0?b2?10(3)b3?4最优基矩阵和其逆矩阵分别为:B???最优解变为xl?10??10??l??, B????41??;41?????x2?0, x3?13,最小值变为-78;?0, x2?14, x3?2,最小值变为-96;最优解没有变化;最优解变为xl6(解:⑴利润变动范围cl?3,故当cl=2时最优解不变。
⑵根据材料的对偶价格为1判断,此做法有利。
(3)0?b2?45o(4)最优解不变,故不需要修改生产计划。
(5)此时生产计划不需要修改,因为新的产品计算的检验数为?3小于零,对原生产计划没有影响。
7.解:⑴设xl,x2,x3为三种食品的实际产量,则该问题的线性规划模型为max z?2.5xl?2x2?3x3约束条件:8xl?16x2?10x3?35010xl?5x2?5x3?4502xl?13x2?5x3?400xl,x2,x3?0解得三种食品产量分别为xl?43.75,x2?x3?0,这时厂家获利最大为109.375万ye©(2)如表中所示,工序1对于的对偶价格为0.313万元,由题意每增加10工时可以多获利3.13万元,但是消耗成本为10万元,所以厂家这样做不合算。
(3)B食品的加工工序改良之后,仍不投产B,最大利润不变;若是考虑生产甲产品,则厂家最大获利变为169.7519万元,其中xl?14.167,x2?0, x3?ll, x4?31.667;(4)若是考虑生产乙产品,则厂家最大获利变为163.1万元,其中xl?ll,x2?0, x3?7.2, x4?38;所以建议生产乙产品。
2013-2014(1)学期《管理运筹学A》复习题二参考答案1.对偶单纯形法与单纯形法的主要区别是每次迭代的基变量都满足最优检验但不完全满足(非负)约束。
2.若原问题有最优解,那么对偶问题(一定)有最优解,且原问题与对偶问题的最优(目标函数值)相等。
3.原问题可行,而对偶问题不可行,则原问题(无)界。
4.一般的图都具有(点)和(边)两个要素。
5. 网络中从一点到另一点的所有路中各边权数之和最小的路称为(最短路)。
6. 线性规划问题的基本解一定是基本可行解。
(×)7.用单纯形法求解标准型线性规划问题时,与检验数大于0相对应的变量都可被选作换入变量。
(√)8. 在运输问题中,只要给出一组含有(m + n -1)个非零的x ij且满足全部约束,就可以作为基本可行解。
(×)9.表上作业法实质上就是求解运输问题的单纯形法。
(√)10.如果网络G中不含有流f的增流链,则网络的流为最大流。
(√)11. 增流链一定是不饱和链,不饱和链不一定是增流链。
(√)12. 如果网络G中含有流f的增流链,则网络的流值可以增加。
(√)13.网络的最小费用流与最小费用最大流是什么关系?答:网络的最小费用流是指网络的流值等于某一目标流的流值时,在这所有的流中费用最小的流;也就是在满足某一目标运输量下,所有的运输方案中,运输费用最小的运输方案。
而网络的最小费用最大流是指在网络流值达到最大时,所有流中费用最小的流;也就是达到运输网络最大运输量的所有运输方案中,运输费用最小的运输方案。
可以看出,网络的最小费用最大流是网络的最小费用流的一种特殊情况,即目标流的流值等于最大流的的流值的情况。
14.当线性规划的可行解集合非空时一定(D)A.包含原点X=(0,0,…,0) B.有界C.无界D.是凸集15. 有5个产地6个销地的平衡运输问题模型具有特征(D)A.有11个变量B.有10个约束C.有30约束D.有10个基变量16. 根据所给的表和一组解判断是否最优解,若不是,请求出最优解。
2023年运筹学大作业单纯性法与对偶单纯性法的比较目前,运筹学领域中的单纯性法和对偶单纯性法是两种最为常用的线性规划求解方法。
随着科技和工业的不断发展,未来的运筹学研究也将越来越受到人们的关注。
因此,在未来的2023年中,我们不仅需要掌握这两种方法的基本概念和原理,还需要深入的了解它们的比较和应用。
第一章单纯性法的基本原理单纯性法是一种常用的线性规划求解方法,其基本流程可以归纳为以下几个步骤:1. 确定一个基本可行解;2. 判断该基本可行解是否是最优解;3. 如果不是最优解,则选择一个入基变量和一个出基变量;4. 对出基变量进行互换,更新基本可行解;5. 重复执行步骤2至步骤4,直至得到最优解。
单纯性法的优点在于可快速地求得最优解,特别是在少数变量和简单约束的情况下,可以快速解决线性规划问题。
但是,当规模较大或者约束条件复杂时,单纯性法很可能会陷入循环,导致计算时间过长。
第二章对偶单纯性法的基本原理对偶单纯性法是单纯性法的一种扩展,其实质是对线性规划模型的对偶模型进行求解。
其基本流程可以归纳为以下几个步骤:1. 确定一个对偶基本可行解;2. 判断该对偶基本可行解是否是最优解;3. 如果不是最优解,则选择一个入基变量和一个出基变量;4. 对出基变量进行互换,更新对偶基本可行解;5. 重复执行步骤2至步骤4,直至得到最优解。
对偶单纯性法的优点在于可以避免陷入循环的情况,同时,还可以通过求解对偶问题来产生原问题的最优解。
第三章两种方法的比较从计算复杂度的角度来比较单纯性法和对偶单纯性法,很明显对偶单纯性法更加高效。
因为对偶单纯性法的目标函数和限制条件比原问题要少,因此需要的计算步骤相对更少。
但是,在实际操作中,对偶单纯性法的计算结果通常需要进行一次转换才能得到原问题的最优解。
从求解结果的角度来比较单纯性法和对偶单纯性法,也可以发现它们的区别。
在某些情况下,单纯性法得出的最优解不一定是方案的唯一最优解,而对偶单纯性法则可以直接得到原问题的唯一最优解。
应⽤运筹学基础:线性规划(4)-对偶与对偶单纯形法这⼀节课讲解了线性规划的对偶问题及其性质。
引⼊对偶问题考虑⼀个线性规划问题:$$\begin{matrix}\max\limits_x & 4x_1 + 3x_2 \\ \text{s.t.} & 2x_1 + 3x_2 \le 24 \\ & 5x_1 + 2x_2 \le 26 \\ & x \ge0\end{matrix}$$ 我们可以把这个问题看作⼀个⽣产模型:⼀份产品 A 可以获利 4 单位价格,⽣产⼀份需要 2 单位原料 C 和 5 单位原料 D;⼀份产品 B 可以获利 3 单位价格,⽣产⼀份需要 3 单位原料 C 和 2 单位原料 D。
现有 24 单位原料 C,26 单位原料 D,问如何分配⽣产⽅式才能让获利最⼤。
但假如现在我们不⽣产产品,⽽是要把原料都卖掉。
设 1 单位原料 C 的价格为 $y_1$,1 单位原料 D 的价格为 $y_2$,每种原料制定怎样的价格才合理呢?⾸先,原料的价格应该不低于产出的产品价格(不然还不如⾃⼰⽣产...),所以我们有如下限制:$$2y_1 + 5y_2 \ge 4 \\ 3y_1 + 2y_2 \ge3$$ 当然也不能漫天要价(也要保护消费者利益嘛- -),所以我们制定如下⽬标函数:$$\min_y \quad 24y_1 + 26y_2$$ 合起来就是下⾯这个线性规划问题:$$\begin{matrix} \min\limits_y & 24y_1 + 26y_2 \\ \text{s.t.} & 2y_1 + 5y_2 \ge 4 \\ & 3y_1 + 2y_2 \ge 3 \\ & y \ge 0\end{matrix}$$ 这个问题就是原问题的对偶问题。
对偶问题对于⼀个线性规划问题(称为原问题,primal,记为 P) $$\begin{matrix} \max\limits_x & c^Tx \\ \text{s.t.} & Ax \le b \\ & x \ge 0\end{matrix}$$ 我们定义它的对偶问题(dual,记为 D)为 $$\begin{matrix} \min\limits_x & b^Ty \\ \text{s.t.} & A^Ty \ge c \\ & y \ge 0\end{matrix}$$ 这⾥的对偶变量 $y$,可以看作是对原问题的每个限制,都⽤⼀个变量来表⽰。
运筹学课程运筹学对偶单纯形法与单纯形法对比分析大作业哈尔滨工业大学工业工程系学生姓名:学号:指导教师:成绩:评语:运筹学对偶单纯形法与单纯形法对比分析摘要:这篇论文主要介绍了对偶单纯形法的实质、原理、流程和适用条件等。
将对偶单纯形法与单纯形法的基本思想进行对比分析,从而说明对偶单纯形法的优点和适用范围。
关键词:对偶单纯形法;对偶理论;单纯形法;基本思想在线性规划早期发展阶段的众多重要发现中,对偶的概念及其分支是其中最重要的内容之一。
这个发现指出,对于任何一个线性规划问题都具有对应的称为对偶问题的线性规划问题。
对偶问题与原问题的关系在众多领域都非常有用。
(一)教学目标:通过对偶单纯形法的学习,加深对对偶问题的理解。
掌握对偶单纯形法的解题过程,理解对偶理论的其原理,了解对偶单纯形法的作用和应用范围(二)教学内容:1)对偶单纯形法的思想来源2)对偶单纯形法原理3)对偶理论的实质4)单纯形法和对偶单纯形法的比较(三)教学进程:一、对偶单纯形法的思想来源所谓对偶单纯形法,就是将单纯形法应用于对偶问题的计算,该方法是由美国数学家 C.莱姆基于1954年提出的,它并不是求解对偶问题解的方法,而是利用对偶理论求解原问题的解的方法。
二、对偶问题的实质下面是原问题的标准形式以及其对应的对偶问题:从而可以发现如下规律:1.原问题目标函数系数是对偶问题约束方程的右端项。
2.原问题约束方程的右端项是对偶问题目标函数的系数。
3.原问题一个变量在所有约束方程中的系数是对偶问题一个约束方程中的所有系数。
三、对偶单纯形法原理对偶单纯形法是通过寻找原问题的对偶问题的可行解来求解原问题的最优解的方法,它的应用包括影子价格和灵敏度分析等。
为了理解对偶单纯形法为什么能够解出原方程的最优解,我们需要对对偶理论的几个基本原理有所了解。
1.弱对偶性如果是原问题的可行解,是其对偶问题的可行解,则恒有证明:由于对偶方程中原问题的约束条件是各行的a i j x j 之和小于等于y i 的系数b i ,而对偶问题的约束条件是各行的a i j y i 之和小于等于x j 的系数c j ,故将 和分别和 比较,可得上述结论。
1.用图解法求解下列线性规划问题,并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。
2。
将下述线性规划问题化成标准形式。
(1)解:令,3。
分别用图解法和单纯形法求解下述线性规划问题,并对照指出单纯形表中的各基可行解对应图解法中的可行域的哪个顶点。
解:①图解法:单纯型法步骤:转化为标准线性规划问题;找到一个初始可行解,列出初始单纯型表;最优性检验,求cj-zj,若所有的值都小于0,则表中的解便是最优解,否则,找出最大的值的那一列,求出bi/aij,选取最小的相对应的xij,作为换入基进行初等行变换,重复此步骤。
4.写出下列线性规划问题的对偶问题。
(1)(2)5。
给出线性规划问题要求:(1)写出其对偶问题;(2)已知原问题最优解为,试根据对偶理论,直接求出对偶问题的最优解。
解:(1)(2)因为,第四个约束取等号,根据互补松弛定理得:求得对偶问题的最优解为:,最优值min w=16。
弱对偶性的推论:(1) 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界;反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界(2) 如原问题有可行解且目标函数值无界(具有无界解),则其对偶问题无可行解;反之对偶问题有可行解且目标函数值无界,则其原问题无可行解。
注意:本点性质的逆不成立,当对偶问题无可行解时,其原问题或具有无界解或无可行解,反之亦然。
(3)若原问题有可行解而其对偶问题无可行解,则原问题目标函数值无界;反之对偶问题有可行解而其原问题无可行解,则对偶问题的目标函数值无界。
强对偶性(或称对偶定理)若原问题及其对偶问题均具有可行解,则两者均具有最优解,且它们最优解的目标函数值相等。
互补松弛性在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值为非零,则该约束条件取严格等式;反之如果约束条件取严格不等式,则其对应的对偶变量一定为零。
影子价格资源的市场价格是其价值的客观体现,相对比较稳定,而它的影子价格则有赖于资源的利用情况,是未知数。
运筹学复习一、单纯形方法(表格、人工变量、基础知识)线性规划解的情况:唯一最优解、多重最优解、无界解、无解。
其中,可行域无界,并不意味着目标函数值无界。
无界可行域对应着解的情况有:唯一最优解、多重最优解、无界解。
有界可行域对应唯一最优解和多重最优解两种情况。
线性规划解得基本性质有:满足线性规划约束条件的可行解集(可行域)构成一个凸多边形;凸多边形的顶点(极点)与基本可行解一一对应(即一个基本可行解对应一个顶点);线性规划问题若有最优解,则最优解一定在凸多边形的某个顶点上取得。
单纯形法解决线性规划问题时,在换基迭代过程中,进基的非基变量的选择要利用比值法,这个方法是保证进基后的单纯型依然在解上可行。
换基迭代要求除了进基的非基变量外,其余非基变量全为零。
检验最优性的一个方法是在目标函数中,用非基变量表示基变量。
要求检验数全部小于等于零。
“当x1由0变到45/2时,x3首先变为0,故x3为退出基变量。
”这句话是最小比值法的一种通俗的说法,但是很有意义。
这里,x1为进基变量,x3为出基变量。
将约束方程化为每个方程只含一个基变量,目标函数表示成非基变量的函数。
单纯型原理的矩阵描述。
在单纯型原理的表格解法中,有一个有趣的现象就是,单纯型表中的某一列的组成的列向量等于它所在的单纯型矩阵的最初的基矩阵的m*m矩阵与其最初的那一列向量的乘积。
最初基变量对应的基矩阵的逆矩阵。
这个样子:'1222 1 0 -32580 1 010 0 158P B P -⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥==⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦51=5所有的检验数均小于或等于零,有最优解。
但是如果出现非基变量的检验数为0,则有无穷多的最优解,这时应该继续迭代。
解的结果应该是:X *= a X 1*+(1-a)X 2* (0<=a<=1)说明:最优解有时不唯一,但最优值唯一;在实际应用中,有多种方案可供选择;当问题有两个不同的最优解时,问题有无穷多个最优解。
线性规划的求解算法线性规划(linear programming )是运筹学中的一个重要分支,在现代工业、农业、商业、交通运输、国防军事及经济管理等诸多领域都有着广泛重要的应用。
在数学系的竞赛数学建模中,也多次应用线性规划来建模从而解决实际问题。
在这里介绍单纯性法和对偶单纯形法两种求解线性规划的方法。
一、单纯形法算法主体思想 标准线性规划简记如下:LP-max LP-min s.t {0Ax b x =≥ s.t {0Ax bx =≥ 这里只以LP-min 为例。
1、算法思想单纯形法是在已知一个可行基的前提下采用的解决线性规划的算法。
步骤如下:(1)输入初始矩阵:01020,111121,112,1n n m m m n a a a a a a a a a +++⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦K L M MO M K,并化为典则形式。
用R (i )记录单位矩阵I 中元素1的位置。
(2)求{}0min|0,1jj aj n t >≤≤@若t 不存在,则得到最优解;(i),1R i n x a += (i=1,2,...m ).其他j x =0,停。
否则,转到(3)。
(3)求,1min{|0,1}i n it ita a i m a λ+>≤≤@。
若λ不存在,则LP-min 无下届,所以无最优解,停;否则,求,1min (i)|,0,1(s)i n it it a R a i m R a λ+⎧⎫=>≤≤⎨⎬⎩⎭@,转到(4)。
(4)sjsj sta a a ⇐,(j=1,2....n+1)ijij sj it a a a a ⇐-,(i=0,1,2...m;i ≠s;j=1,2,....,n+1),(s)t R ⇐,转到(2).二、对偶单纯形法对偶单纯形法是在已知一个正则基的条件下的求解线性规划的方法。
步骤如下:(1)输入初始矩阵:01020,111121,112,1n n m m m n a a a a a a a a a +++⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦K L M MO M K,并化为典则形式。
对偶单纯形法与单纯形法对比分析1.教学目标:通过对偶单纯形法的学习,加深对对偶问题的理解2.教学内容:1)对偶单纯形法的思想来源 2)对偶单纯形法原理3.教学进程:1)讲述对偶单纯形法解法的来源:所谓对偶单纯形法,就是将单纯形法应用于对偶问题的计算,该方法是由美国数学家C.莱姆基于1954年提出的,它并不是求解对偶问题解的方法,而是利用对偶理论求解原问题的解的方法。
2)为什么要引入对偶单纯形法:单纯形法是解线性规划的主要方法,对偶单纯形法则提高了求解线性规划问题的效率,因为它具有以下优点: (1)初始基解可以是非可行解, 当检验数都为负值时, 就可以进行基的变换, 不需加入人工变量, 从而简化计算; (2)对于变量多于约束条件的线性规划问题,用对偶单纯形法可以减少计算量,在灵敏度分析及求解整数规划的割平面法中,有时适宜用对偶规划单纯形法。
由对偶问题的基本性质可以知道,线性规划的原问题及其对偶问题之间存在一组互补的基解,其中原问题的松弛变量对应对偶问题的变量,对偶问题的剩余变量对应原问题的变量;这些互相对应的变量如果在一个问题的解中是基变量,则在另一问题的解中是非基变量;将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w 。
据此可知,用单纯形法求解线性规划问题时,在得到原问题的一个基可行解的同时,在检验数行得到对偶问题的一个基解,并且将两个解分别代入各自的目标函数时其值相等。
我们知道,单纯形法计算的基本思路是保持原问题为可行解(这时一般其对偶问题为非可行解)的基础上,通过迭代,增大目标函数,当其对偶问题的解也为可行解时,就达到了目标函数的最优值。
那么对偶单纯形法的基本思想可以理解为保持对偶问题为可行解(这时一般原问题为非可行解)的基础上,通过迭代,减小目标函数,当原问题也达到可行解时,即达到了目标函数的最优值。
其实对偶单纯形法本质上就是单纯形法, 只不过在运用时需要将单纯形表旋转一下而已。
对偶单纯形法与单纯形法对比分析1.教学目标:通过对偶单纯形法的学习,加深对对偶问题的理解2.教学内容:1)对偶单纯形法的思想来源 2)对偶单纯形法原理3.教学进程:1)讲述对偶单纯形法解法的来源:所谓对偶单纯形法,就是将单纯形法应用于对偶问题的计算,该方法是由美国数学家C.莱姆基于1954年提出的,它并不是求解对偶问题解的方法,而是利用对偶理论求解原问题的解的方法。
2)为什么要引入对偶单纯形法:单纯形法是解线性规划的主要方法,对偶单纯形法则提高了求解线性规划问题的效率,因为它具有以下优点: (1)初始基解可以是非可行解, 当检验数都为负值时, 就可以进行基的变换, 不需加入人工变量, 从而简化计算; (2)对于变量多于约束条件的线性规划问题,用对偶单纯形法可以减少计算量,在灵敏度分析及求解整数规划的割平面法中,有时适宜用对偶规划单纯形法。
由对偶问题的基本性质可以知道,线性规划的原问题及其对偶问题之间存在一组互补的基解,其中原问题的松弛变量对应对偶问题的变量,对偶问题的剩余变量对应原问题的变量;这些互相对应的变量如果在一个问题的解中是基变量,则在另一问题的解中是非基变量;将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w 。
据此可知,用单纯形法求解线性规划问题时,在得到原问题的一个基可行解的同时,在检验数行得到对偶问题的一个基解,并且将两个解分别代入各自的目标函数时其值相等。
我们知道,单纯形法计算的基本思路是保持原问题为可行解(这时一般其对偶问题为非可行解)的基础上,通过迭代,增大目标函数,当其对偶问题的解也为可行解时,就达到了目标函数的最优值。
那么对偶单纯形法的基本思想可以理解为保持对偶问题为可行解(这时一般原问题为非可行解)的基础上,通过迭代,减小目标函数,当原问题也达到可行解时,即达到了目标函数的最优值。
其实对偶单纯形法本质上就是单纯形法, 只不过在运用时需要将单纯形表旋转一下而已。
一.单纯形法和对偶单纯性法单纯形法是求解线性规划的主要方法, 单纯形表则是单纯形法和对偶单纯形法的运算工具。
设线性规划问题为Max ∑==nj j j x c Z 1⎪⎩⎪⎨⎧=≥=≤∑=),....,1(0),...,1(..1n j m i t s x b x a jnj i j ij ⑴将其化为标准形式,得Max Z= CXs.t. ⎪⎩⎪⎨⎧≥=+0,X X ss X bAX ⑵其中),(C C N B C =,)0,...,0,0(0==C N ,),(N B A =,⎪⎩⎪⎨⎧=X X NBX ,则其对应的线性约束转换为011=++--X BX BX s N B ,XBX BB X sN B b 111---+-=,代入目标函数得XBC X B C C B C SB N B N B b Z 111)(-----+=,相应的一个基解为b B X B 1-=,0=X N ,0=X S 。
显然,若01≥-b B ,且0)(1≥--N B C C B N ,01≥--X BC SB ,则基解⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧=-01b X B 为该线性规划的最优解, 此时检验数均大于零, 见表1。
通过上面的分析, 我们知道单纯形表的检验数实际上是目标函数中基变量、非基变量的价值系数,又由对偶理论知道它们是相应对偶问题的一个( 加一个负号) 基解。
那么表中b 列的数字仅仅表示的是X B 的取值吗? 我们可以猜想b B1- 很可能是对偶问题的检验数。
这里首先给出问题(1) 的对偶问题的一般形式Min ∑==mi ii y b w 1s.t.⎪⎩⎪⎨⎧=≥=≥∑=),....,1(0),...,1(1m i n j y c y a imi j i ij ⑶将问题(3)化为标准形式,得 Min YB w =s.t.⎪⎩⎪⎨⎧≥=-0,Y Y S S Y CYA ⑷由),(C C N B C =,),(N B A =,Ys 为松弛变量,Ys 相应分解为Y sB 、Y sN ,其中0),....,,(211≥=++y yyY mm m sB ,0),....,,(22212≥=++y yyY nm m sN 。
得:C Y B sB YB =- ⑸ C Y N sN YN =- ⑹ 由式⑸得到B Y BC sB B Y 11--+= ⑺ 通过令0=Y sB ,由式(5)得对偶问题的基解B C B Y 1-=,代入式(6)得C B C Y N B sN N -=-1,将式(7)对偶问题的目标函数得b b w B Y B C sB B 11--+=。
显然若目标函数达到最小,非基变量Y sB 的价值系数要求大于等于零,单纯形表b 列01≥-b B , 即01≥-b B 实际上是对偶问题的非基变量检验数。
二.对偶单纯形法的算法步骤(1)确定换出基的变量设原问题为(1),对偶问题为(3)。
由),(),,(C C N B C N B A ==,不等式C YA ≥则可分解为 C C N B YN YB ≥≥, (8) 进一步添加松弛变量有等式(5)、(6),对等式(5)两端同时左乘B 1-有 B C B Y B sB Y 11--=- (9) 将B Y sB 1-移至等式右端得B C B Y B sB Y 11--+= (10) 由不等式(8)得0≤-YB C B (11) 0≤-YN C N (12) 将式(10)代入不等式(11)、(12)得011≤--=---B B YB B Y B C C C sB B B B (13)011≤--=---N N YN B Y B C C C sB B N N (14) 将(13)、(14)合并得0),)((),(),(),(11≤+-=---N B N B Y B Y B C C C C C sB B N B N B (15) 整理得011≤----A A C B Y B C sB B (16) 其中A C B C B 1--是单纯形表中X 变量的检验数,记)(1σj B A C B C =--,(j=1,2,....,n),n m ij a BA x '1)(=-矩阵,显然,若Y 为基可行解,而若01<-b B,则对偶问题的目标函数b b w B Y B C sB B 11--+=未取得最小值,取{}l i i b b b B B B )(0)(|)(m i n 111---=<,确定单纯形表的换出基变量x l ,即(在单纯形表中的)对偶问题相应的换入基变量ylm +,令Y sB 其余分量为零,即)0,...,0,...,0(),...,,(221yy yyYlm mm m sB+++==,ylm +可能取大,使对偶问题的目标函数值下降,由Y 为基可行解,则要求满足式(16),即对于任意的j ,均有0'≥-+a y ijl m j σ,得a a a y km l km ij j ij j l m ',''0,0|min +++=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧≤≤=σσσ,从而确定单纯形表中换入基变量x k m +,同时确定对偶问题(在单纯形表中)换出基变量y k。
这与单纯形法确定换出基变量的规则是完全一样的。
3)例题讲解下面举例说明对偶单纯形法的算法步骤:【例题】用对偶单纯形法求解线性规划问题: min y y y w 32152415++=⎪⎪⎩⎪⎪⎨⎧≥≥++≥+0,12526..3,2132132y y y y y y y y t s解:1)将问题改写为:2)算法步骤第一步:建立一个初始单纯形表,使表中检验行的 j值全部大于或等于零,即对其对偶问题而言是一基本可行解。
约束条件两端乘 -1,得:根据原问题和对偶问题之间的对称关系,这时单纯形表中原基变量列数字相当于对偶问题解的非基变量的检验数。
第二步:由于对偶问题的求解是使目标函数达到最小值,所以最优判别准则是 当所有检验数大于或等于零时为最优(也即这时原问题是可行解)。
如果不满足这个条件,找出绝对值最大的负检验数,设为b i -,其对应 的原问题的基变量x l 即为对偶问题的换入变量。
第三步:将σj 行数字与表中第l 行对应的数字对比,令a C a a C lkj ij ij j =⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧<=0||min θ,a lk 即为主元素,x k 为对偶问题的换出变 量。
第四步:用换入变量替换对偶问题中的换出变量(在单纯形表中反映为用替原问 题的基变量),得到一个新的单纯形表。
表中数字计算同用单纯形法时完全一样。
新表中对偶问题仍保持基本 可行解,原问题基变量列数字列数字相当于对偶问题的检验数。
据此可以完成对这个对偶问题的求解。
4.总结。
1)对比单纯形法&对偶单纯形法单纯性法基本思想2)对偶单纯形法优点这里我们需要对单纯形法和对偶单纯形法做一个详细的对比: 1,单纯形法中的b 对应于对偶单纯形法中的σ;2,单纯形法中的σ作为检验数,对偶单纯形法中的b 作为检验数;3,单纯形法中的0≥b ,对偶单纯形法中的0≤σ;4,单纯形法中当0≤σ时得到最优解,对偶单纯形法中当0≥b 时得到最优 解;5,单纯形法的可行解为b X B 1-=,对偶单纯形法的可行解为B C B Y 1-=; (由于松弛变量X s 对应的检验数为B C B 1--,由于X s 与Y 对应,又由于 01<--B C B ,可得01≥=-B C B Y )。
对于单纯形法和对偶单纯形法,我们建立了使用单纯形法解决线性规划问题 的依据:1,表中有单位矩阵I ,当0≥b 时用单纯形法; 2,表中有单位矩阵I ,当0≤σ时用单纯形法; 3,两者都不满足时,使用人工变量法或两阶段法。
接下来需要说明在哪些场合下使用对偶单纯形法解决线性规划问题较为便 捷,我将通过下面的例子来说明:min x x x x Z 43211216812+++=⎪⎪⎩⎪⎪⎨⎧≥≥++≥++0,,,3422242..4321421321x x x x x x x x x x t s 令Z Z -=-,则问题可变为max x x x x Z 43211216812----=-⎪⎪⎩⎪⎪⎨⎧=≥-=+----=+---)6~1(03422242..64215321i t s x x x x x x x x x i取),(65P P B =为初始基,易见所有检验数0≤σj ,从而建立单纯形表,计 算结果如下:本例如果用单纯形法计算,确定初始基可行解时需引入两个人工变量,计算量要多于对偶单纯形法。
一般情况下,如果问题能够用对偶单纯形法计算,计算量会少于单纯形法。
但是,对偶单纯形法并不是一种普遍算法,它有一定的局限性,不是任何线性规划问题都能用对偶单纯形法计算的。