运筹学之对偶单纯形法

应⽤运筹学基础：线性规划（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$，可以看作是对原问题的每个限制，都⽤⼀个变量来表⽰。

41第2章对偶理论与灵敏度分析即y 是对偶问题（D ）的一个可行解。

条件式（2-21）称为对偶可行性条件，即最优性条件式（2-20）与对偶可行性条件式（2-21）是等价的，因此，如果一个原始可行基B 是原问题（P ）的最优基，则1=B y c B -就是对偶问题（D ）的一个可行解，此时对应的目标函数值1B w=yb =c B -，等于原问题（P ）的目标函数值，可知1=B y c B -也是对偶问题（D ）的最优解。

若原问题（P ）的一个基本解1=0B b x ⎛⎞⎜⎟⎝⎠-对应的检验数向量满足条件式（2-20），即 =(,)=0,0B N N B σσσc c B N -1（-）≤则称x 为（P ）的一个正则解。

于是可知，原问题（P ）的正则解x 与对偶问题（D ）的可行解y 是一一对应的，它们由同一个基B 所决定，我们称这一基为正则基。

因此，我们可以设想另一条求解思路，即在迭代过程中，始终保持对偶问题解的可行性，而原问题的解由不可行逐渐向可行性转化，一旦原问题的解也满足了可行性条件，也就达到了最优解。

也即在保持正则解的正则性不变条件下，在迭代过程中，使原问题解的不可行性逐步消失，一旦迭代到可行解时，即达到了最优解。

这正是对偶单纯形法的思路，这个方法并不需要把原问题化为对偶问题，利用原问题与对偶问题的数据相同（只是所处位置不同）这一特点，直接在反映原问题的单纯形表上进行运算。

2.3.2 对偶单纯形法的计算步骤求解如下标准形式线性规划问题：max =z cx s.t.0Ax =bx ⎧⎨⎩≥对偶单纯形法的计算步骤如下：（1）找一个正则基B 和初始正则解(0)x ；将原问题化为关于基B [不妨设12=(,,,)m B P P P ]的典式，列初始对偶单纯形表，如表2-5所示。

表2-5 对偶单纯形表12 1 2 12121c 1x 1'b 1 0 … 0 1+1'm a 1+2'm a … 1'n a 2c 2x 2'b 01 02+1'm a 2+2'm a … 2'n am c m x'm b 0…1 +1'mm a +2'mm a … 'mn a c j -z j0 0 0+1m σ+2m σ…n σ（2）若1=b'B b -≥0，则停止计算，当前的正则解1=x B b -，即为原问题的最优解；否则转下一步。

对偶单纯形法与单纯形法对比分析1．教学目标：通过对偶单纯形法的学习，加深对对偶问题的理解2．教学内容：1）对偶单纯形法的思想来源 2）对偶单纯形法原理3．教学进程：1）讲述对偶单纯形法解法的来源：所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由美国数学家C.莱姆基于1954年提出的，它并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。

2）为什么要引入对偶单纯形法：单纯形法是解线性规划的主要方法，对偶单纯形法则提高了求解线性规划问题的效率，因为它具有以下优点： （1）初始基解可以是非可行解, 当检验数都为负值时, 就可以进行基的变换, 不需加入人工变量, 从而简化计算； （2）对于变量多于约束条件的线性规划问题,用对偶单纯形法可以减少计算量,在灵敏度分析及求解整数规划的割平面法中,有时适宜用对偶规划单纯形法。

由对偶问题的基本性质可以知道，线性规划的原问题及其对偶问题之间存在一组互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w 。

据此可知，用单纯形法求解线性规划问题时，在得到原问题的一个基可行解的同时，在检验数行得到对偶问题的一个基解，并且将两个解分别代入各自的目标函数时其值相等。

我们知道，单纯形法计算的基本思路是保持原问题为可行解（这时一般其对偶问题为非可行解）的基础上，通过迭代，增大目标函数，当其对偶问题的解也为可行解时，就达到了目标函数的最优值。

那么对偶单纯形法的基本思想可以理解为保持对偶问题为可行解（这时一般原问题为非可行解）的基础上，通过迭代，减小目标函数，当原问题也达到可行解时，即达到了目标函数的最优值。

其实对偶单纯形法本质上就是单纯形法, 只不过在运用时需要将单纯形表旋转一下而已。

第2章对偶理论及灵敏度分析主要内容对偶理论⏹线性规划对偶问题⏹对偶问题的基本性质⏹影子价格⏹对偶单纯形法灵敏度分析⏹灵敏度问题及其图解法⏹灵敏度分析⏹参数线性规划线性规划的对偶问题⏹对偶问题的提出⏹原问题与对偶问题的数学模型⏹原问题与对偶问题的对应关系实例：某家电厂家利用现有资源生产两种产品，有关数据如下表：设备A设备B 调试工序利润（元）612521115时24时5时产品Ⅰ产品ⅡD一、对偶问题的提出如何安排生产，使获利最多？厂家设Ⅰ产量–––––Ⅱ产量–––––1x 2x ⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+=052426155 2max 212121221x x x x x x x s.t.x x z ,设设备A ——元／时设备B ––––元／时调试工序––––元／时1y 2y 3y 收购付出的代价最小，且对方能接受。

出让代价应不低于用同等数量的资源自己生产的利润。

设备A 设备B 调试工序利润（元）0612521115时24时5时ⅠⅡD ⏹厂家能接受的条件：⏹收购方的意愿：32152415min yy y w ++=单位产品Ⅰ出租收入不低于2元单位产品Ⅱ出租收入不低于1元出让代价应不低于用同等数量的资源自己生产的利润。

1252632132≥++≥+y y y y y52426155 2212121221⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+=x x x x x x x s.t.x x z ,max ⎪⎩⎪⎨⎧≥≥++≥+++=0y 125265241532132132321y y y y y y y t s y y y w ,,.min 对偶问题原问题收购厂家一对对偶问题⎩⎨⎧≥≥=⇒⎩⎨⎧≥≤=00bY C YA s.t.Yb w X AX t s CX z min ..max ),(21c c C =⎪⎪⎫ ⎛=1x x X )(ij a A =()321,y ,y y Y =⎪⎪⎪⎫ ⎛=321b b b b 3个约束2个变量2个约束3个变量原问题对偶问题其它形式的对偶问题?特点：1.原问题的约束个数（不包含非负约束）等于对偶问题变量的个数；2.原问题的价值系数对应于对偶问题右端项；3.原问题右端项对应于对偶问题的价值系数；4.原问题约束矩阵转置就是对偶问题约束矩阵；5.原问题为求最大，对偶问题是求最小问题；6.原问题不等约束符号为“≤”，对偶问题不等式约束符号为“≥”;二、原问题与对偶问题的数学模型1．对称形式的对偶当原问题对偶问题只含有不等式约束时，称为对称形式的对偶。

运筹学课程运筹学对偶单纯形法与单纯形法对比分析大作业哈尔滨工业大学工业工程系学生姓名:学号：指导教师：成绩：评语：运筹学对偶单纯形法与单纯形法对比分析摘要：这篇论文主要介绍了对偶单纯形法的实质、原理、流程和适用条件等。

将对偶单纯形法与单纯形法的基本思想进行对比分析，从而说明对偶单纯形法的优点和适用范围。

关键词：对偶单纯形法；对偶理论；单纯形法；基本思想在线性规划早期发展阶段的众多重要发现中，对偶的概念及其分支是其中最重要的内容之一。

这个发现指出，对于任何一个线性规划问题都具有对应的称为对偶问题的线性规划问题。

对偶问题与原问题的关系在众多领域都非常有用。

（一）教学目标：通过对偶单纯形法的学习，加深对对偶问题的理解。

掌握对偶单纯形法的解题过程，理解对偶理论的其原理，了解对偶单纯形法的作用和应用范围（二）教学内容：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 ，故将 和分别和 比较，可得上述结论。