当前位置：文档之家 › 运筹学大作业单纯性法与对偶单纯性法比较

运筹学大作业单纯性法与对偶单纯性法比较

  • 格式：docx
  • 大小：197.66 KB
  • 文档页数：8

运筹学大作业单纯性法与对偶单纯性法比较

Pleasure Group Office【T985AB-B866SYT-B182C-BS682T-STT18】 对偶单纯形法与单纯形法对比分析 1．教学目标： 通过对偶单纯形法的学习，加深对对偶问题的理解 2．教学内容： 1）对偶单纯形法的思想来源 2）对偶单纯形法原理 3．教学进程： 1）讲述对偶单纯形法解法的来源： 所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由美国数学家C.莱姆基于1954年提出的，它并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。 2）为什么要引入对偶单纯形法： 单纯形法是解线性规划的主要方法，对偶单纯形法则提高了求解线性规划问题的效

率，因为它具有以下优点：

（1）初始基解可以是非可行解, 当检验数都为负值时, 就可以进行基的变换, 不需加入人工变量, 从而简化计算； （2）对于变量多于约束条件的线性规划问题,用对偶单纯形法可以减少计算量,在灵敏度分析及求解整数规划的割平面法中,有时适宜用对偶规划单纯形法。 由对偶问题的基本性质可以知道，线性规划的原问题及其对偶问题之间存在一组互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w。据此可知，用单纯形法求解线性规划问题时，在得到原问题的一个基可行解的同时，在检验数行得到对偶问题的一个基解，并且将两个解分别代入各自的目标函数时其值相等。 我们知道，单纯形法计算的基本思路是保持原问题为可行解（这时一般其对偶问题为非可行解）的基础上，通过迭代，增大目标函数，当其对偶问题的解也为可行解时，就 达到了目标函数的最优值。那么对偶单纯形法的基本思想可以理解为保持对偶问题为可行解（这时一般原问题为非可行解）的基础上，通过迭代，减小目标函数，当原问题也达到可行解时，即达到了目标函数的最优值。其实对偶单纯形法本质上就是单纯形法, 只不过在运用时需要将单纯形表旋转一下而已。 一.单纯形法和对偶单纯性法

单纯形法是求解线性规划的主要方法, 单纯形表则是单纯形法和对偶单纯形法的运算工具。设线性规划问题为

Max njjjxcZ1

),....,1(0),...,1(..1njmitsxbxajnjijij ⑴ 将其化为标准形式，得 Max Z= CX

. 0,XXssXbAX ⑵

其中),(CCNBC，)0,...,0,0(0CN，),(NBA，



XXNBX，则其对应的线性约束

转换为011XBXBXsNB，XBXBBXsNBb111，代入目标函数得

XBCXBCCBCSBNBNB

bZ111)(，相应的一个基解为bBXB1，

0XN，0XS。显然，若01bB，且0)(1NBCCBN，01XBCSB，

则基解



01bXB

为该线性规划的最优解, 此时检验数均大于零, 见表1。

通过上面的分析, 我们知道单纯形表的检验数实际上是目标函数中基变量、非基变量的价值系数,又由对偶理论知道它们是相应对偶问题的一个( 加一个负号) 基解。那

么表中b列的数字仅仅表示的是XB的取值吗 我们可以猜想bB1 很可能是对偶问题

的检验数。这里首先给出问题(1) 的对偶问题的一般形式

Min miiiybw1 .),....,1(0),...,1(1minjycyaimijiij ⑶ 将问题（3）化为标准形式，得 Min YBw

.0,YYSSYCYA ⑷

由),(CCNBC，),(NBA，Ys为松弛变量，Ys相应分解为YsB、YsN，其中0),....,,(211yyyYmmmsB，0),....,,(22212yyyYnmmsN。得：

CYBsBYB ⑸ CYNsNYN ⑹ 由式⑸得到 BYBCsBBY11 ⑺ 通过令0YsB，由式(5)得对偶问题的基解BCBY1,代入式(6)得CBCYNBsNN1,将式(7)对偶问题的目标函数得bbwBYBCsBB

11。显然若

目标函数达到最小,非基变量YsB的价值系数要求大于等于零,单纯形表b列01bB, 即01bB实际上是对偶问题的非基变量检验数。

二．对偶单纯形法的算法步骤 (1)确定换出基的变量 设原问题为（1），对偶问题为（3）。由),(),,(

CC

NBCNBA，不等式CYA则可

分解为 CCNBYNYB, (8)

进一步添加松弛变量有等式（5）、（6），对等式（5）两端同时左乘B1有 BCBYBsBY11 (9) 将BYsB1移至等式右端得 BCBYBsBY11 (10) 由不等式（8）得 0YBCB (11) 0YNCN (12) 将式（10）代入不等式（11）、（12）得 011BBYBBYBCCCsBBBB (13) 011NNYNBYBCCCsBBNN (14) 将（13）、（14）合并得 0),)((),(),(),(11NBNBYBYBCCCCCsBBNBNB (15) 整理得 011AACBYBCsBB (16) 其中ACBCB1是单纯形表中X变量的检验数,记)(1jBACBC

，

(j=1,2,....,n),nmijaBAx

'1)(

矩阵，显然，若Y为基可行解，而若01bB，则对偶

问题的目标函数bbw

BYBC

sBB

11未取得最小值，取

liibbbBBB)(0)(|)(min111，确定单纯形表的换出基变量x

l，即（在单纯形表中

的）对偶问题相应的换入基变量ylm，令YsB其余分量为零，即)0,...,,0,...,0(),...,,(221yyyyYlmmmmsB，ylm可能取大，使对偶问题的目标函数值

下降，由Y为基可行解，则要求满足式（16），即对于任意的j，均有0'ayijlmj，

得aaaykmlkmijjijjlm',''0,0|min，从而确定单纯形表中换入基变量xkm，同时确定对偶问题（在单纯形表中）换出基变量yk。这与单纯形法确定换出基变量的规则是完全一样的。 3）例题讲解 下面举例说明对偶单纯形法的算法步骤：

【例题】用对偶单纯形法求解线性规划问题： min yyyw32152415 解：1）将问题改写为： 2）算法步骤 第一步：建立一个初始单纯形表，使表中检验行的j值全部大于或等于零，

即对其对偶问题而言是一基本可行解。 约束条件两端乘 -1，得： 根据原问题和对偶问题之间的对称关系，这时单纯形表中原基变量列数字 相当于对偶问题解的非基变量的检验数。 第二步：由于对偶问题的求解是使目标函数达到最小值，所以最优判别准则是 当所有检验数大于或等于零时为最优（也即这时原问题是可行解）。

如果不满足这个条件，找出绝对值最大的负检验数，设为bi-，其对应

的原问题的基变量xl即为对偶问题的换入变量。 第三步：将j行数字与表中第l行对应的数字对比，令

aCaaClkjijijj0||min，alk即为主元素，xk为对偶问题的换出变 量。 第四步：用换入变量替换对偶问题中的换出变量（在单纯形表中反映为用替原问

题的基变量），得到一个新的单纯形表。 表中数字计算同用单纯形法时完全一样。新表中对偶问题仍保持基本 可行解，原问题基变量列数字列数字相当于对偶问题的检验数。 据此可以完成对这个对偶问题的求解。 4．总结。 1）对比单纯形法&对偶单纯形法单纯性法基本思想 2）对偶单纯形法优点 这里我们需要对单纯形法和对偶单纯形法做一个详细的对比： 1，单纯形法中的b对应于对偶单纯形法中的； 2，单纯形法中的作为检验数，对偶单纯形法中的b作为检验数； 3，单纯形法中的0b，对偶单纯形法中的0； 4，单纯形法中当0时得到最优解，对偶单纯形法中当0b时得到最优 解； 5，单纯形法的可行解为bXB1，对偶单纯形法的可行解为BCBY1；

（由于松弛变量Xs对应的检验数为BCB1，由于Xs与Y对应，又由于 01BCB，可得01BCBY）。 对于单纯形法和对偶单纯形法，我们建立了使用单纯形法解决线性规划问题 的依据： 1，表中有单位矩阵I，当0b时用单纯形法； 2，表中有单位矩阵I，当0时用单纯形法； 3，两者都不满足时，使用人工变量法或两阶段法。 接下来需要说明在哪些场合下使用对偶单纯形法解决线性规划问题较为便 捷，我将通过下面的例子来说明： min xxxxZ43211216812 令ZZ，则问题可变为

max xxxxZ43211216812 取),(65PPB为初始基，易见所有检验数0j，从而建立单纯形表，计

算结果如下： 本例如果用单纯形法计算，确定初始基可行解时需引入两个人工变量，计算 量要多于对偶单纯形法。一般情况下，如果问题能够用对偶单纯形法计算， 计算量会少于单纯形法。但是，对偶单纯形法并不是一种普遍算法，它有一 定的局限性，不是任何线性规划问题都能用对偶单纯形法计算的。当线性规 划问题具备下面条件时，可以用对偶单纯形法求解： ①问题标准化后，价值系数全非正； ②所有约束全是不等式。

合集下载

运筹学复习重点

运筹学复习重点

运筹学复习重点第1章线性规划与单纯形法（1）化线形规划标准形的手法（2）线性规划解的概念、解的情形、解的判定（3）单纯形法的计算过程、迭代逻辑。

（4）熟练运用单纯形表求解问题；若给出单纯形表，要会解读，会基于单纯形法基本原理反推出表中一些参数。

（5）两阶段法、大M法第2章对偶理论和灵敏度分析（1）会写对偶问题，掌握对偶性质，原问题与对偶问题之间的关系。

（2）互补松弛定理的应用：知道一个问题的最优解，求另一个问题的最优解。

（3）对偶单纯形法（4）当目标函数系数和右端项变化时灵敏度分析的简便方法第4章整数规划（1）分支定界法：如何构造分支子问题，如何更新目标函数最优值上下界，何时终止。

（2）割平面法：如何写对源约束方程；如何拆分、组装割平面方程；如何利用对偶单纯形法继续求解。

第5章无约束优化（1）凸函数与凸规划的定义与判别（2）一维搜索的0.618法基本原理和迭代过程（3）无约束优化的最速下降法的基本原理、迭代过程第6章约束极值优化（1）可行下降方向的含义、满足什么代数条件、几何意义（2）正确写出Kuhn-Tucker条件，理解K-T条件与最优解的关系（3）利用Kuhn-Tucker条件，求出K-T点和最优解。

（4）外点法和内点法的基本原理、无约束优化目标函数的一般构造手法第7章动态规划（1）动态规划的基本原理和基本方程（2）动态规划的逆推解法（3）动态规划求静态规划问题的套路第8章图与网络优化（1）图的基本概念、树的基本性质、最小支撑树的求法（2）求最短路的Dijkstra算法（3）增广链的概念、用途，求网络最大流的标号法第10章排队论（1）排队系统基本性能指标的含义、关系（2）泊松流与负指数分布的关系，排队系统中基本参数λ和μ含义的多维解读。

（3）系统状态概率Pn的含义、它在推导系统基本性能指标中的基础地位，推导它自身所依据的状态转移图。

（4）M/M/1模型、M/M/c模型的状态转移图，概率平衡方程，以及了解系统状态概率、基本性能指标的计算过程。

运筹学课件 第2章：线性规划的对偶理论

运筹学课件 第2章：线性规划的对偶理论


min w 16y1 36y2 65y3
90 y1 3 y 2 y1 2 y 2 5 y 3 70 y , y , y 0 1 2 3
原问题 A b C 约束系数矩阵
对偶问题 约束系数矩阵的转臵
约束条件的右端项向量 目标函数中的价格系数向量 目标函数中的价格系数向量 约束条件的右端项向量 Max z=CX Min w=Y’b 目标函数 AX≤b A’Y≥C’ 约束条件 X≥0 Y≥0 决策变量
若原问题为求极小形式的对称形式线性规划问题， 对偶问题应该具有什么形式？
Min w Y 'b A'Y C Y 0
max w Y 'b A'Y C Y 0
min z CX
Max z CX
AX b X 0
AX b X 0
min w 5 y1 4 y2 6 y3 4 y1 3 y2 2 y3 2 y1 2 y2 3 y3 3 3 y1 4 y3 5 2 y 7 y y 1 2 3 1 y1 0, y2 0, y3无约束
对偶问题 约束系数矩阵的转臵
目标函数中的价格系数向量
目标函数 约束条件
变量
Max z=CX m个 ≤ ≥ = n个 ≥0 ≤0 无约束
约束条件的右端项向量 目标函数 Min w=Y’b m个 ≥0 变量 ≤0 无约束 n个 ≥ 约束条件 ≤ =
【例2-3】写出下列线性规划问题的对偶问题
min 2x1 3x2 5x3 x4
1.初始表中单位阵在迭代后单纯形表中对应的位臵就是B-1 2.对于原问题的最优解，各松弛变量检验数的相反数恰好 是其对偶问题的一个可行解，且两者具有相同的目标函数 值。根据下面介绍的对偶问题的基本性质还将看到，若原 问题取得最优解，则对偶问题的解也为最优解。
运筹学2对偶问题

运筹学2对偶问题

运筹学2对偶问题运筹学教程运筹学Operations Research Chapter 2 对偶问题Dual Problem1. 线性规划的对偶模型Dual Model of LP2.对偶性质对偶性质3.对偶单纯形法对偶单纯形法4.灵敏度分析灵敏度分析Dual property Dual Simplex Method Sensitivity Analysis 运筹学教程§2.1线性规划的对偶模型线性规划的对偶模型Dual model of LPCh2 Dual Problem2022年11月26日星期五Page 2 of 19在线性规划问题中，存在一个有趣的问题，即每一个线性规划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。

【例2.1】某企业用四种资源生产三种产品，工艺系数、例资源限量及价值系数如下表：产品资源Ⅰ Ⅱ Ⅲ Ⅳ 每件产品利润9 5 8 7 100 8 4 3 6 80 6 7 2 4 70 500 450 300 550 A B C 资源限量建立总收益最大的数学模型。

运筹学教程§2.1线性规划的对偶模型线性规划的对偶模型Dualmodel of LPCh2 Dual Problem2022年11月26日星期五Page 3 of 19 设x1,x2,x3分别为产品A,B,C的产量，则线性规划数学模解型为：m Z = 100x + 80x + 70x ax1 2 39x1 + 8x2 + 6x3 ≤ 500 5x + 4x + 7x ≤ 450 2 3 1 8x1 + 3x2 + 2x3 ≤ 300 7x + 6x + 4x ≤ 550 2 3 1 x1, x2, x3 ≥ 0 现在从另一个角度来考虑企业的决策问题。

假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？价格太高对方不愿意接受，价格太低本单位收益又太少。

运筹学作业-王程130404026

运筹学作业-王程130404026

运筹学作业王程信管1302130404026目录运筹学作业 (1)第一章线性规划及单纯形法 (3)第二章线性规划的对偶理论与灵敏度分析 (24)第三章运输问题 (53)第四章目标规划 (63)第五章整数规划 (73)第六章非线性规划 (85)第七章动态规划 (94)第八章图与网络分析 (97)第九章网络计划 (99)第一章 线性规划及单纯形法1.1分别用图解法和单纯形法求下列线性规划问题，⑴指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解；⑵当具有限最优解时，指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。

121212121min 23466 s.t.324,0z x x x x x x x x =++≥⎧⎪+≥⎨⎪≥⎩（） 1212121,22max 3222s.t.34120z x x x x x x x x =++≤⎧⎪+≥⎨⎪≥⎩（）121212123max 105349 s.t.528 ,0z x x x x x x x x =++≤⎧⎪+≤⎨⎪≥⎩（） 121212124max 5622 s.t.232,0z x x x x x x x x =+-≥⎧⎪-+≤⎨⎪≥⎩（）解：⑴图解法：当212133x x z =-经过点6155（，）时，z 最小，且有无穷多个最优解。

⑵图解法：1x该问题无可行解。

⑶图解法：当21125x x z =-+经过点312（，）时，z 取得唯一最优解。

单纯形法：在上述问题的约束条件中分别加入松弛变量34,x x ， 化为标准型：12341231241234max 10+500349s.t.528,,,0z x x x x x x x x x x x x x x =++++=⎧⎪++=⎨⎪≥⎩由线性规划问题的标准型可列出单纯初始形表逐步迭代，计算结果如下表所示：**33(,1,0,0),10512022(0,0,9,8)821(,0,,0)553(1,,0,0)2T T T T X Z X O X C X B ==⨯+⨯====（0）（1）（2）单纯形表的计算结果表明：单纯形表迭代的第一步得，表示图中原点（0,0）单纯形表迭代的第二步得，表示图中点单纯形表迭代的第三步得，表示图中点⑷图解法：当215166x x z =-经过点2,2（）时，z 取得唯一最优解。