哈工大运筹学大作业-对偶单纯形法对比

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

第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 ，故将 和分别和 比较，可得上述结论。

对偶问题的单纯形法关键信息项：协议编号：____________________________签署日期：____________________________甲方（委托方）信息：姓名/公司名称：____________________________身份证号码/法人代表证件号码：____________________________联系地址：____________________________电话号码：____________________________电子邮箱：____________________________乙方（承接方）信息：姓名/公司名称：____________________________身份证号码/法人代表证件号码：____________________________联系地址：____________________________电话号码：____________________________电子邮箱：____________________________问题描述：对偶问题的形式：____________________________目标函数：____________________________约束条件：____________________________变量范围：____________________________服务内容：提供的服务（如模型构建、求解算法实现等）：____________________________服务详细描述：____________________________时间安排：服务开始日期：____________________________服务结束日期：____________________________重要里程碑及时间节点：____________________________费用及支付方式：总费用：____________________________付款方式（如银行转账、支票等）：____________________________付款时间安排：____________________________权利与义务：甲方的权利与义务：____________________________乙方的权利与义务：____________________________保密条款：保密信息定义：____________________________保密期限：____________________________违约责任：违约金：____________________________违约条款：____________________________争议解决：争议解决地点：____________________________争议解决方式（如仲裁、诉讼）：____________________________协议的变更与终止：变更条件：____________________________终止条件：____________________________协议的有效性：协议生效日期：____________________________协议有效期：____________________________其他约定：其他条款：____________________________协议1. 协议目的本协议旨在明确甲方委托乙方处理与对偶问题相关的单纯形法应用服务，包括对偶问题的建模、求解和分析，以确保双方在服务过程中的权利与义务得到明确和保障。

课程名称：对偶单纯形法1、教学目标在对偶单纯形法的学习过程中，理解和掌握对偶问题；综合运用线性规划和对偶原理知识对对偶单纯形法与单纯形法进行对比分析，了解单纯形法和对偶单纯形法的相同点和不同点，总结出各自的适用范围；掌握对偶单纯形法的求解过程；并能运用对偶单纯形法独立解决一些运筹学问题。

2、 教学内容1) 对偶单纯形法的思想来源(5min)2) 对偶单纯形法原理(5min)3) 总结对偶单纯形法的优点及适用情况(5min)4) 对偶单纯形法的求解过程(10min)5) 对偶单纯形法例题(15min)6) 对比分析单纯形法和对偶单纯形法(10min)3、 教学进程：1）讲述对偶单纯形法思想的来源：1954年美国数学家C.莱姆基提出对偶单纯形法（Dual Simplex Method）。

单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。

对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。

在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。

因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。

2）讲述对偶单纯形法的原理A.对偶问题的基本性质依照书第58页，我们先介绍一下对偶问题的六个基本性质：性质一：弱对偶性性质二：最优性。

如果（j=1...n)原问题的可行解，是其对偶问题可行解，且有=，则是原问题的最优解，是其对偶问题的最优解。

性质三：无界性。

如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。

性质四：强对偶性。

如果原问题有最优解，则其对偶问题也一定有最优解。

性质五：互补松弛型。

在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。

性质六：线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w.B.对偶单纯形法（参考书p64页）设某标准形式的线性规划问题，对偶单纯形表中必须有-≤0（j=1...n),但(i=1...m)的值不一定为正，当对i=1...m，都有≥0时，表中原问题和对偶问题均为最优解，否则通过变换一个基变量，找出原问题的一个目标函数值较小的相邻的基解。

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

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

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

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

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

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

掌握对偶单纯形法的解题过程，理解对偶理论的其原理，了解对偶单纯形法的作用和应用范围（二）教学内容：1）对偶单纯形法的思想来源2）对偶单纯形法原理3）对偶理论的实质4）单纯形法和对偶单纯形法的比较（三）教学进程：一、对偶单纯形法的思想来源所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由美国数学家C.莱姆基于1954年提出的，它并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。

二、对偶问题的实质从而可以发现如下规律：1.原问题目标函数系数是对偶问题约束方程的右端项。

2.原问题约束方程的右端项是对偶问题目标函数的系数。

3.原问题一个变量在所有约束方程中的系数是对偶问题一个约束方程中的所有系数。

三、对偶单纯形法原理对偶单纯形法是通过寻找原问题的对偶问题的可行解来求解原问题的最优解的方法，它的应用包括影子价格和灵敏度分析等。

为了理解对偶单纯形法为什么能够解出原方程的最优解，我们需要对对偶理论的几个基本原理有所了解。

1.弱对偶性如果x j ̅(j =1,⋯,n)是原问题的可行解，y i ̅(i =1,⋯,m)是其对偶问题的可行解，则恒有∑c j x ̅j nj=1≤∑b i y ̅i mi=1证明：由于对偶方程中原问题的约束条件是各行的a i j x j 之和小于等于y i的系数b i ，而对偶问题的约束条件是各行的a i j y i 之和小于等于x j 的系数c j ，故将∑c j x ̅j n j=1和∑b i y ̅i m i=1分别和∑∑x̅j nj=1a ij y ̅i m i=1比较，可得上述结论。