05 线性规划对偶

线性规划对偶问题线性规划是一种优化问题的数学建模方法，在实际生产和管理中广泛应用。

线性规划问题通常包括最大化或最小化一个线性目标函数的约束条件下的一组线性不等式或等式。

对于一个线性规划问题，其对偶问题是通过对原问题的目标函数和约束条件进行变换而得到的。

对偶问题有助于理解原问题的特性，并提供关于原问题的附加信息。

具体来说，对于一个原问题：最小化 C^T * X约束条件 A * X >= bX >= 0其中，C是目标函数的系数矩阵，X是决策变量向量，A是约束条件的系数矩阵，b是约束条件的右侧向量。

对于原问题的对偶问题，其形式为：最大化 b^T * Y约束条件 A^T * Y <= CY >= 0其中，Y是对偶变量向量。

对偶问题的最优解被称为对偶可行解，对偶问题的最优解与原问题的最优解之间存在弱对偶性和强对偶性。

弱对偶性指的是对于原问题的任意可行解X和对偶问题的任意可行解Y，有C^T * X >= b^T * Y。

这意味着对于原问题的任意最优解X*和对偶问题的任意最优解Y*，有C^T * X* >=b^T * Y*。

强对偶性指的是如果原问题和对偶问题的任意一个都有有界解，那么它们必然存在一对最优解，使得C^T * X* = b^T * Y*。

对偶问题的解决可以通过使用单纯形法或内点法等优化算法来进行求解。

对偶问题对线性规划问题的求解具有重要的应用价值和理论意义。

它可以用于确定原问题的可行解的界限，还可以提供原问题的敏感性分析和稳定性分析。

总之，线性规划的对偶问题是通过对原问题的目标函数和约束条件进行变换而得到的，对偶问题为理解原问题的特性和提供附加信息提供了一种有力的工具。

线性规划对偶理论前言线性规划（linear programming, LP）是一种求解线性模型的算法，该算法可以在目标函数下寻找最佳的解决方案。

通常情况下，线性规划可以被看作是一种最优化问题，其目的是在满足一组约束条件的前提下，找到可以最大化或最小化目标函数的变量值。

而对偶理论是线性规划问题中的重要概念之一，在很多情况下，使用对偶理论能够有效地求解出更优的解答。

线性规划与对偶理论在介绍线性规划对偶理论之前，我们先来简单了解一下线性规划的概念。

线性规划可以被定义为一组决策变量的线性函数，该函数的取值范围应在满足一组线性方程（或不等式）约束条件的前提下，使得目标函数达到最小（或最大）值。

换句话说，线性规划要求我们在可接受的条件下，寻找到最优的决策变量值。

围绕这种思想，我们可以进一步探讨线性规划的对偶问题。

在实践中，我们常常会面对一些较复杂的线性规划问题，此时我们可以使用对偶理论对其进行简化处理。

形式化地说，对于一个线性规划问题，我们可以构建一个对应的对偶问题，二者之间的关系可以被描述为一种对称的互补关系。

具体而言，在每个线性规划问题中，我们可以根据不同的约束条件求出一个对应的乘法因子，这个乘法因子可以在构建对偶问题时被使用。

通过这种方式，我们总是可以在对偶问题中找到一组最优解，而这组最优解实际上是原始问题的一个下界。

同时，我们可以利用对偶问题的最优解来求解原始问题的最优解，这种方法被称为对偶算法。

相比于原始的线性规划问题，对偶问题有着更为简洁的约束条件和更为易于求解的优化问题，因此其求解效率较高。

对偶问题的分析与求解在实际求解中，我们通常需要对给定的线性规划问题进行对偶化处理，并使用一系列的对偶算法来求解对偶问题。

下面，我们将会举两个例子来说明对偶问题的分析与求解。

例1：最小费用最大流问题最小费用最大流问题是一种最优化问题，其目的是在给定图中求出最大流量下的最小费用。

在具体求解中，我们可以通过建立一个对应的线性规划问题，并将其对偶化得到一个更加简洁的对偶问题。

教案五线性规划的对偶问题教学内容第四节线性规划的对偶问题1．线性规划的对偶问题2．对偶单纯形法3．线性规划的灵敏度分析4．线性规划在卫生管理中的应用教学学时7学时教学目标1．理解对偶问题的基本概念2．掌握对偶单纯形法3．掌握线性规划的灵敏度分析4．掌握线性规划在卫生管理中的应用重点难点重点是对偶问题的基本概念、对偶单纯形法线、灵敏度分析、线性规划在卫生管理中的应用。

难点是对偶问题的基本概念和线性规划的灵敏度分析教学手段教师与学生互动使用多媒体课件教学过程一、复习巩固1．单纯形法的基本原理（见课件）2．单纯形解法（见课件）3．大M法（见课件）二、讲授新课1．线性规划的对偶问题（1）对偶问题的基本概念（见课件）对偶现象 每一个线性规划都伴随着另一个线性规划，两者有密切关系，互为对偶．其中一个问题称为原问题，另一个问题称为其对偶问题．两者间只要得到其中一个问题的解，那么也就得到了另一个问题的解．下面通过一个实例来解释对偶线性规划的概念．例2-12 以例2-1为例，我们讨论了一个制药厂的生产计划的数学模型及其解法．现在假定该制药厂决定在计划期内不生产药品Ⅰ、Ⅱ，而将生产设备的有效台时全部租给某公司，那么该公司应对设备D C B A 、、、每小时付多少租金，才能使成本最小，而又能为制药厂所接受？从租用设备的公司的角度考虑，一是所付的租金越低越好；二是所付的租金总额能使制药厂接受，即租金应不低于制药厂自己生产该两种药品所得利润，否则，制药厂宁可自己生产，而不租给公司．设公司租用该制药厂D C B A 、、、四种设备的租金（元/小时）分别为1y 、2y 、3y 和4y ．在考虑租用设备的定价时，能使该制药厂接受的条件是：公司租用该制药厂用以生产每千克药品Ⅰ所需D C B A 、、、四种设备的台时的租金不应少于200元，即2000424321≥+++y y y y同样，公司租用该制药厂用以生产每千克药品Ⅱ所需D C B A 、、、四种设备的台时的租金不应少于300元，即30040224321≥+++y y y y公司在考虑自身利益时，其目标是使付出的租金总额为最小，即43211216812Min y y y y W +++=于是，上面的问题可以用下列线性规划的数学模型表示：43211216812Min y y y y W +++=20004 24321≥+++y y y y ..t s 30040224321≥+++y y y y0,,,4321≥y y y y若把制药厂利润最大的线性规划问题称为原问题，则想租用DC B A 、、、四种设备的公司的租金最小的线性规划问题称为原问题的对偶问题（dualproblem ）；反之，若把租用D C B A 、、、四种设备的公司的租金最小的线性规划问题称为原问题，则制药厂利润最大的线性规划问题称为原问题的对偶问题．影子价格 一般地，我们称对偶问题的最优解为原问题约束条件的影子价格，即对偶问题的解i y 称为第i 种资源的影子价格．它并不是某种资源在市场上的价格，而是代表单位资源在最优利用的条件下所产生的经济效果．为了和市场价格相区别，我们才称它为影子价格．它在经济上是一个很有意义的数据，通过它我们可以知道，当增加某种资源时，可以使利润增长的大小．另外，影子价格还给出了是否应当购进某种资源以增加生产量，而获得更多利润的价格标准．（2）对称的对偶线性规划（见课件）如果一个线性规划具备下面两个条件，则称它具有对称形式：①所有的变量都是非负的；②所有的约束条件都是不等式，而且在目标函数是求极大值的情况，不等式具有小于和等于（≤）的符号，在目标函数是求极小值的情况，不等式具有大于和等于（≥）的符号．对称形式的原问题和对偶问题叫做对称的对偶线性规划．原问题和对偶问题在形式上的对比 如果我们把线性规划n n x c x c x c Z +++= 2211M a x 11212111b x a x a x a n n ≤+++22222121b x a x a x a n n ≤+++..t s …………………………m n m n m m b x a x a x a ≤+++ 22110,,,21≥n x x x称为原问题，则必同时存在另一线性规划问题，我们称为对偶问题：m m y b y b y b W +++= 2211Min11221111c y a y a y a m m ≥+++22222112c y a y a y a m m ≥+++..t s …………………………n m m n n n c y a y a y a ≥+++ 22110,,,21≥m y y y而且 M a x Z M i n =W用简缩形式表示：原问题为 ∑==nj j j x c Z 1Max∑=≤nj i j ij b x a 1 m i ,,2,1 =0 ≥j x n j ,,2,1 =对偶问题为 ∑==mi i i y b W 1M i n∑=≥mi j i ij c y a 1 n j ,,2,1 =0 ≥i y ; m i ,,2,1 =矩阵形式表示：.t .s .t .s原问题为 CX Z =Maxb AX ≤0 ≥X 对偶问题为 Min W ＝YbC YA ≥ 0 ≥Y其中， ),,,(21n c c c C =⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=mn m m n n a a a a a a a a a A 212222111211 ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=n x x x X 21 ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=m b b b b 21 ()m y y y Y ,,,21 =原问题与对偶问题之间的关系1）原问题是求目标函数的最大值，对偶问题是求目标函数的最小值．2）原问题约束条件的右端项变成对偶问题目标函数的系数．原问题目标函数中的系数变成对偶问题约束条件的右端项．3）原问题约束条件是“≤”，对偶问题的约束条件则是“≥”．4）原问题约束条件的每一行正好对应于对偶问题的每一列，所以原问题中约束条件的数目等于对偶问题中变量的数目．5）原问题中约束条件的每一列正好对应于对偶问题的每一行，所以原问题中变量的数目正好等于对偶问题中的约束条件的数目．.t .s .t .s .t .s6）对偶问题的对偶规划正是原问题．例2-13 设原问题为：2152M i n x x W +=41≥x3 2≥x8221≥+x x0,21≥x x试写出它的对偶问题．解 321834M a x y y y Z ++=2y 31≤+y5 232≤+y y0,,321≥y y y（3）非对称的对偶线性规划（见课件）对于我们经常遇到的非对称形式的线性规划，我们可首先将其化为等价的对称形式的线性规划问题，然后再按对称的对偶线性规划原问题与对偶问题之间的对应关系，将其化为对偶问题．实际上，我们在考虑对称的对偶线性规划或非对称的对偶线性规划（dual of a nonnormal LP ）时，也可以按表2-13原问题与对偶问题之间的对应关系，直接进行变换，得到原问题或对偶问题．表2-13 原问题与对偶问题间的转换.t .s例2-14 原问题为：2154M a x x x Z +=202321≤+x x1034 21≥-x x5 21=+x x01≥x ，2x 符号不限可按表2-13的原则，将原问题直接转化成对偶问题：32151020Min y y y W ++=443321≥++y y y..t s 532321=+-y y y01≥y ，02≤y ，3y 符号不限（4）对偶问题的基本性质（见课件）1）对偶问题的对偶是原问题（对称性质）．2）若X 和Y 分别是原问题和对偶问题的可行解，则C X ≤Y b （弱对偶性质）．3）设X 和Y 分别是原问题和对偶问题的可行解，当两者目标函数值相等，.t .s即C X ＝Y b 时，X ，Y 分别是原问题和对偶问题的最优解（可行解是最优解的性质）．4）若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等（对偶性质）．5）若X 和Y 分别是原问题和对偶问题的可行解，则X 和Y 为原问题及对偶问题最优解的充分条件为：v X ＝0和Y u ＝0其中，u ＝T m u u u ),,,(21 , m u u u ,,,21 是原问题的松弛变量，v ＝（n v v v ,,,21 ）, n v v v ,,,21 是对偶问题的剩余变量（松弛互补性质）．此性质在线性规划中有广泛应用．如从已知的原问题最优解（或对偶问题最优解）求取对偶问题最优解（或原问题最优解）；验证原问题的可行解是否最优解等等．6）原问题的检验数对应于对偶问题的一个基本解．由对偶性质可知，在求解原问题的过程中，利用单纯形表每一次迭代所得的检验数与对偶问题的基本解仅仅相差一个符号，于是原问题获得最优解时对应的单纯形表中检验数的相反数，即为对偶问题的最优解．例2-15 设原问题为：4321432Max x x x x Z +++=20322 4321≤+++x x x x..t s 2023 2 4321≤+++x x x x0,,,4321≥x x x x已知其对偶问题的最优解为1y *＝1.2，2y *＝0.2，相应的目标函数最小值W *＝28，试利用对偶性质求该问题的最优解．解 原问题的对偶问题为：212020Min y y W +=12 21≥+y y2 221≥+y y..t s 33221≥+y y42321≥+y y0,21≥y y由松弛互补性质可知，在最优条件下，v X ＝0和Y u ＝0，即1u *1y *＝0，2u *2y *＝0，1v *1x *＝0，2v *2x *＝0，3v *3x *＝0，4v *4x *＝0；这里i u *（2,1=i ），j v *（4,3,2,1=j ）分别为原问题的松弛变量及对偶问题的剩余变量．由1y * ＝1.2>0，可以推出1u * =0；由2y * ＝0.2>0，可推出2u * =0．由对偶约束1y *+22y * =1.6>1，知1v * >0,于是1x * =0；同理，由21y *+2y *=2.6>2，知2v * >0,于是2x * =0．根据上述结果，原约束可以转化成二元一次线性方程组：32x * +43x * =2033x * +42x * =20解方程得3x * =4x * =4综上所得，原问题的最优解为X * =()T4400，相应的目标函数最优值为Z * =28．由对偶性质还可以推论：1）若原问题可行，但有无界解（或称无有限最优解），则对偶问题不可行；若对偶问题可行，但有无界解（或称无有限最优解），则原问题不可行；2）若原问题可行，而对偶问题不可行，则原问题有无界解（或称无有限最优解）；若对偶问题可行，而原问题不可行，则对偶问题有无界解（或称无有限最优解）．2．对偶单纯形法前面已叙述原问题与对偶问题的解之间的对应关系．在用单纯形法进行迭代时，在b 列中得到的是原问题的基本可行解，而在检验数（j j Z c -）行得到的是对偶问题基本解的相反数．通过逐步迭代，当在检验数行得到的对偶问题的解也是可行解时，原问题和对偶问题都达到了最优解．所以，单纯形法的特点是保持原问题解的可行性，通过逐步迭代，使对偶问题的解由基本解变成基本可行解，这时原问题和对偶问题都达到了最优解．那么根据对偶问题的对称性，我们也可以这样来处理：保持对偶问题的解是可行解（即0≤-j j Z c ），而原问题则从非可行解开始，通过迭代，逐步达到基本可行解．这样，也使原问题和对偶问题都达到了最优解．事实上，对偶单纯形法（dual simplex method ）并不是解对偶问题的单纯形法，而是应用对偶原理来求解原问题的最优解的一种方法．（1）对偶单纯形法的要点（见课件）例2-16 用对偶单纯形法求解下列线性规划问题32140025001600M i n xx x W ++= 45 2321≥++x x x..t s 3 5.2221≥+x x 0,,321≥x x x解 此问题可用大M 法去解，但用大M 法求解很麻烦，现在用对偶单纯形法求解．先将原问题化为标准 形式，为此引入剩余变量4x ，5x ，令W Z -=，得32140025001600Max x x x Z ---=4 5 24321=-++x x x x..t s 3 5.22521=-+x x x0,,,,54321≥x x x x x然后将约束条件等式的两边都乘以（-1），得到 32140025001600Max x x x Z ---=4 5 24321-=+---x x x x..t s 35.22521-=+--x x x0,,,,54321≥x x x x x建立这个问题的初始单纯形表，见表2-14：表2-14 对偶单纯形法求解例2-16（1）在这个初始单纯形表中，4x 、5x 是基本变量，初始单纯形表所对应的基本解为X ＝()T34000--，它是一个不可行解．而全部检验数0≤-j j Z C ，即所对应的对偶问题的一个基本解也是一个可行解, 0≥i y ，5,,2,1 =i ．下面的迭代是在保持检验数小于等于零的条件下，逐步使0≥j x ，5,,2,1 =j ．为了满足上面要求，迭代的要点是：1）首先确定换出变量：选择具有负数的基本变量中绝对值最大的基本变量为换出变量．2）确定换入变量：用换出变量那一行具有负值的系数分别去除同列的检验数，取最小商数所对应的变量为换入变量；如果换出变量那一行无负值的系数，则原问题无可行解．3）把换出变量的那一行除以枢元位置的系数，使枢元位置变为1．4）进行行变换，使除枢元外的其他枢列位置变为0．5）进行最优解检查．如果所得的基本解都是非负的，则此解即为最优解．如果基本解中还有负的数值，则重复第1步继续迭代，直到所有基本变量为非负的数值为止．（2）表解形式的对偶单纯形法（见课件）按上述迭代的要点，对表2-14继续运算，见表2-15．表2-15 对偶单纯形法求解例2-16（2）表2-15中b 列数字全为非负，检验数全为非正，故问题的最优解为X * =()T 0004.01，最优值W * ＝2600．若对应两个约束条件的对偶变量分别为1y 和2y ，则对偶问题的最优解为Y * =()20000600200，最优值＝2600．（3）对偶单纯形法的优点及用途（见课件）1）初始解可以是非可行解，当检验数都是小于等于零时，就可以进行基变换，这样就避免了增加人工变量，使运算简化．2）对变量较少，而约束条件很多的线性规划问题，可先将其变为对偶问题，再用对偶单纯形法求解，简化计算．3）用于灵敏度分析． 3．线性规划的灵敏度分析在上述讨论线性规划问题时，假定ij a ，i b ，j c 都是精确的数据，然而在大多数实际问题中，这些系数往往是估计值和预测值，而且它们也随着某些条件的变化而变化．因此很自然会想到，当这些系数中的一个或几个发生变化时，已求得的规划问题的最优解会发生什么变化？如果最优解发生了变化，又怎样用最简单的方法找到新的最优解？这就是线性规划灵敏度分析（sensitivity analysis of LP）的任务．（1）单纯形法的矩阵表达式（见课件）设有一线性规划问题，用矩阵表示为CXZ=MaxbAX≤≥X式中，A为nm⨯矩阵，C为1×n行向量，X为n×1列向量，b为m×1列向量，0为n×1列向量．现引入松弛变量化为标准型SXMax +=CXZbXIXAS=+≥X，0≥SX其中，I是mm⨯阶单位矩阵，约束条件也可写成()bXXIAS=⎪⎪⎭⎫⎝⎛,和0≥⎪⎪⎭⎫⎝⎛SXX，0有nm+个元素．如果我们把系数矩阵A分为两块，),(NBA=，B也称基矩阵（即原始系数矩阵中对应于基本变量的列所组成的矩阵），对应于B的变量BmBBxxx,,,21是基()TmnnnmnnnSxxxxxxX++++++=⎪⎪⎪⎪⎪⎭⎫⎝⎛=,,,2121本变量，用向量T Bm B B B x x x X ),,,(21 =表示，其他的变量则为非基本变量，于是将X 也分为两块：0≥⎪⎪⎭⎫ ⎝⎛NBXX 向量C 也可分为两块),(N B C C C =，其中B C 是目标函数中基本变量向量BX 的系数行向量，N C 是目标函数中非基本变量向量N X 的系数行向量．所以于是线性规划问题可以写成S N N B B X X C X C Z 0Max ++=b IX NX BX S N B =++0 ≥S N B X ,X ,X在单纯形法的每次迭代中，是用行变换的方法将基矩阵变成单位矩阵．用矩阵方法，则将上述约束方程的两边乘以基矩阵B 的逆矩阵1-B ,于是可得b B IX B NX B BX B S N B 1111----=++ （2-9） 即: b B X B NX B IX S N B 111---=++ （2-10） 所以S N B X B NX B b B X 111-----=（2-11）将式（2-11）代入目标函数可得N N S B N B B X C X B C NX B C b B C Z +--=---111()()()()S N B S N B S S N N B B S N B N B S IX NX BX X X X I N B X X I A X X C X C X X X C C X X C ++=⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎭⎫⎝⎛++=⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎭⎫⎝⎛,,,00,,0,.t .sS B N B N B X B C X N B C C b B C Z 111)(-----+= （2-12） 或者 b B C X B C X C N B C Z B S B N N B 111)(---=+-+ （2-13）从式（2-9）可知，在单纯形表每次迭代后,每个变量的系数列向量是B 的逆阵1-B 乘以该变量的原始列向量而得到的，右端常数的列向量是B 的逆阵1-B 乘以右端常数的原始列向量而得到的．从式（2-10）可见，其松弛变量的系数矩阵正好是基矩阵的逆阵1-B ．更一般地理解，在任一单纯形表中相应于初始基本变量的那些列给出了相应于该表格的基矩阵的逆阵．例如第二章第三节的例2-8中，表2-4、表2-5、表2-6和表2-7给出了单纯形法的计算过程，其中表2-7为最优解单纯形表，其基本变量是3x ,1x ，6x 和2x ．对应于表2-7的基矩阵⎪⎪⎪⎪⎪⎭⎫⎝⎛=4100004020102021B ⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛----=-0812101212004100041111B 所以对应于表2-7的1x 列向量是11P B ⨯-＝⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛----081210121200410004111×⎪⎪⎪⎪⎪⎭⎫ ⎝⎛0412＝⎪⎪⎪⎪⎪⎭⎫ ⎝⎛0010 式中1P 为原始单纯形表中对应于1x 的列向量. 对应于表2-7的4x 列向量是41P B ⨯-＝⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛----081210121200410004111×⎪⎪⎪⎪⎪⎭⎫ ⎝⎛0010＝⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--21201式中4P 为原始单纯形表中对应于4x 的列向量. 对应于表2-7的b 列向量是b B ⨯-1＝⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛----081210121200410004111×⎪⎪⎪⎪⎪⎭⎫⎝⎛1216812＝⎪⎪⎪⎪⎪⎭⎫ ⎝⎛2440 式中b 为原始单纯形表中右端列向量.对应于表2-7的非基本变量的检验数是N B C C B N 1--，松弛变量的检验数是1--B C B ．（2）系数变化的灵敏度分析（见课件）系数变化的灵敏度分析是在决策变量和约束条件数目不变时，研究各种系数的变化对最优解的影响．它主要考虑两种情况：一是这些系数在什么范围内变化时，已得到的最优解保持不变，或者最优解的基本变量保持不变（但数值有所改变）；二是如果某些系数的变化引起最优解的变化，如何用最简便的方法求出新的最优解．目标函数中j c 变化范围的确定 假设其他参数不变，仅目标函数中j x 的系数j c 变成j c ＋j c ∆，现求不改变最优解的j c ∆的大小．这分两种情况：1）j c 是非基本变量j x 的成本或利润系数 因为 j j j Z c C -= （n j ,,2,1 =）∑='='=mi j B iji j P C a c Z 1（式中i c 是基本变量的成本或利润系数） 所以改变非基本变量的成本或利润系数，Z j 不变，但j j j Z c C -=变为新的检验数j C '：j j j j j j c C Z c c C ∆+=-∆+=要想保持极大化问题最优解不变，即j C '0≤∆+=j j c C ，则：j j C c -≤∆． 2）j c 是基本变量j x 的成本或利润系数 因为j B j j mi ij i j j mi ij i j m i ij i j mi ij i i j j j j j j P C c C a c c C a c c a c c a c c c c Z c c C '∆-∆+=∆-∆+=∆-∆+-=∆+-∆+='-∆+='∑∑∑∑====1111' '' ')()()(要保持极大化问题最优解不变，则0≤'∆-∆+=j B j j j P C c C C ．对于基本变量检验数总为零，而对于非基本变量j x ，因0=∆j c ，所以要求检验数小于等于0变为：0≤'∆-j B j P C C例2-17 以例2-8的最终计算表（表2-7）为例．设基本变量2x 在目标函数中的系数2c 变化了2c ∆；这时表2-7的最终计算表便成为表2-16所示．表2-16 基本变量利润系数变化的灵敏度分析这时要保持最优解不变，则必须满足下列不等式：-150-()⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--∆212010002c =-150-221c ∆≤0-()⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--∆-812141410002252c =-281225c ∆+≤01003002≤∆≤-c即2c 可在[0,400]间变动，不影响原来的生产计划安排，但制药厂收益变化了．在约束条件中i b 变化范围的确定 初始单纯形表中i b 的变化，除了影响最优解的数值之外，不影响最终单纯形表中的其他系数．所以只要保证最后的解仍是可行解，那么它仍然是最优解．即0)(1111≥∆+'=∆+=∆+='----b B b b B b B b b B b式中，b '为右端常数变化后，最终单纯形表右端常数向量；b '为右端常数未变化时，最终单纯形表右端常数向量．例2-18 在例2-8中，如果第三个约束条件3b 发生变化，变化量为3b ∆，为了使最后的解仍为可行解，3b ∆应满足下列不等式：=∆+'-b B b 1⎪⎪⎪⎪⎪⎭⎫ ⎝⎛2440＋⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛----081210121200410004111⎪⎪⎪⎪⎪⎭⎫ ⎝⎛∆0003b ＝⎪⎪⎪⎪⎪⎭⎫ ⎝⎛2440＋⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛∆-∆∆∆-333381214141b b b b ＝⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛∆-∆+∆+∆-333381221441441b b b b 0≥03≤∆b163-≥∆b 83-≥∆b163≤∆b 083≤∆≤-b所以3b ∆在[－8,0]之间变动时（即3b 的变化范围在[8,16]时），原来最优解的基本变量不变，但最优解的值发生变化．例如，3b ∆为－2时（即3b ＝14），则b B b b ∆+'='-1＝⎪⎪⎪⎪⎪⎭⎫ ⎝⎛2440＋⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛----081210121200410004111⎪⎪⎪⎪⎪⎭⎫ ⎝⎛∆0003b ＝⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛∆-∆+∆+∆-333381221441441b b b b ＝⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛4932721 最优解X *＝T⎪⎭⎫⎝⎛300214927，最优值Z *＝1375，见表2-17． 表2-17 右端常数变化后的最优解如果3b ∆的变化超出了[－8,0]的范围，这时最优解的基本变量就发生变化．在这种情况下要用对偶单纯形法继续求出新的最优解．例如3b ∆为2时（即3b ＝18），则b B b b ∆+'=-1＝⎪⎪⎪⎪⎪⎭⎫ ⎝⎛2440＋⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛----081210121200410004111⎪⎪⎪⎪⎪⎭⎫ ⎝⎛∆0003b ＝⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛∆-∆+∆+∆-333381221441441b b b b ＝⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛-4752921则最终单纯形表变为表2-18．表2-18 右端常数变化后的对偶单纯形法求解新的最优解X *＝()T420024，最优值Z *＝1400．矩阵A 中的系数改变对最优解的影响 当对应于j P 的变量j x 为非基本变量的系数时，它的变化不会改变基矩阵B 和它的逆阵1-B ，所以只需修改单纯形表中所对应j x 的列就可以了．j j P B P 1-='j B j j P B C C C 1--='若极大化问题j C '≤0,则得到的还是新问题的最优单纯形表，最优解和最优值不变，否则可用单纯形法求解．当对应于j P 的变量j x 为基本变量的系数时，它的变化会改变基矩阵B 和它的逆阵1-B ，所以会影响到最终单纯形表的右端向量和非基本变量对应的列．下面就举例讨论此种基本变量的系数变化情况．例2-19 以例2-1为例，若计划生产的药品Ⅰ的工艺结构有了改进，相应地生产单位药品Ⅰ所需设备D C B A 、、、的台时改为（3,2,5,2），它的利润也提高到每千克400元．试分析已求得的最优计划有何变化？解 当1x 的系数列向量变化后,原最终单纯形表（表2-7）中1x 的系数列向量变成:111P B P -='=⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛----081210121200410004111⎪⎪⎪⎪⎪⎭⎫ ⎝⎛2523=⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛-83214541 原最终单纯形表变成表2-19：表2-19 决策变量系数改变对最优解的影响（1）由1x 的系数列向量可知，到此尚未完成行变换，所以需继续使1x 的系数列向量变成单位列向量，于是得到表2-20．表2-20 决策变量系数改变对最优解的影响（2）因为j C ≤0，所以新的最优解()TX 4.2008.08.02.3*=，最优值Z*＝1520元.4．线性规划在卫生管理中的应用 （1）放射科的业务安排（见课件）A 医院放射科可以开展X 线平片检查和CT 检查业务，现拟购买磁共振仪，以增设磁共振检查业务．为此A 医院收集了有关信息，以决策是否购买磁共振仪．A 医院估计今后放射科如果开展此3项业务，在现有放射科医务人员力量和病人需求的情况下，每月此3项业务的最多提供量为1800人次．平均每人次检查时间、每月机器实际可使用时间、平均每人次检查利润如下表2-25．表2-25 放射科3项检查时间与利润及机器可使用时间放射科业务项 目X 线平片检查CT 检查 磁共振检查平均每人次检查时间（小时/次） 0.1 0.25 0.5 每月机器实际可使用时间（小时） 300 120 120 平均每人次检查利润（元/次） 206010设每月X 线平片检查、CT 检查和磁共振检查的业务量分别为1x ,2x 和3x 人次，则使A 医院放射科此3项业务收入最多的线性规划模型如下：321106020Max x x x Z ++=300 1.01≤x 12025.0 2≤x ..t s 1205.0 1≤x 1800 321≤++x x x0,,321≥x x x利用单纯形法可得最终单纯形表（见表2-26）．表2-26 放射科业务安排最终单纯形表最优解X*＝()T04801320，最优值Z*＝55200．168120从最终单纯形表上可读出如下信息：1）A医院从放射科收益的角度考虑，不应购买磁共振机.2）在每月X线平片检查和CT检查业务量各为1320人次和480人次时，放射科利润最大，达55200元．3）在最优业务安排情况下，每月X光机仍有168小时未实际利用，故它的影子价格为0元/小时；每月CT机可使用的时间已完全利用，它的影子价格为160元/小时，如果市场上能租到CT机的价格低于影子价格160元/小时，那么就应当租用CT机，增加CT检查业务，以求得更高的利润．4）在最优业务安排情况下，每月X线平片检查和CT检查的服务量已达到现有的最大量．A医院如果想通过从人才市场上聘用医务人员以增加放射科的服务能力，则只有当增加一个病人的服务量所需额外增加的人员招聘费和宣传费低于20元时，才是适宜的，可使放射科的利润更高．三、课堂练习（见课件）四、小结（见课件）五、作业（见课件）。

线性规划的对偶理论线性规划的对偶理论⾸先我们指出对线性规划问题引⼊对偶问题的动机：有时解对偶问题会⽐解原问题更容易，同时便于后续进⾏灵敏度分析。

⽬录1 推导考虑线性规划问题max z=cx s.t.Ax≤b,x i≥0现假设x是⼀个可⾏解，则对于任意⼀个⾮负向量y≥0，有y T Ax≤y T b假设能找到y满⾜c≤y T A，那么对所有可⾏解x都有cx≤y T Ax≤y T b即y T b是原问题的⼀个上界，那么现在我们要找最⼩的⼀个，得到对偶问题min w=b T y s.t.A T y≥c T,y i≥0此时原问题的最优解和对偶问题的最优解⼀定满⾜max z=min w。

2 变换假设我们由⼀个最⼤化的问题，我们通过如下步骤将其转化为其对偶问题⽬标函数改为最⼩化x i≥0 对应约束条件≥，x i⽆约束对应约束条件=原约束条件≤对应y i≥0，原约束条件=对应y i⽆约束补充说明⼀点，从实际意义上来说，光看⼤于号⼩于号或许会有点奇怪，我们可以考虑变量⾃⾝约束或者⽅程约束条件对于⽬标函数优化的贡献“⽅向”。

设想⼀个系数全正的⽬标函数，那么≥0 的变量变换后始终是限制⽬标函数的，反之亦然。

3 性质对偶的对偶就是原问题CX≤Yb，其中X,Y是原问题、对偶问题的任意可⾏解具有⽆界解的问题的对偶是⽆解的问题当可⾏解X,Y满⾜CX=Yb时它们是最优解原问题有最优解则对偶问题有⽬标函数值相同的最优解互补松弛性：可⾏解X,Y是最优解当且仅当YX S=0 且Y S X=0原问题单纯形表的检验数⾏对应对偶问题的⼀个基本解4 影⼦价格我们观察到乘⼦Y=C B B−1到处都是，它究竟是什么？现考虑问题的最优基B，那么z∗=C B B−1b=Y∗b，对b求偏导数，得到∂z∗∂b=C−1=Y∗B B因此，Y∗实际上反映了某种资源的单位资源转化为利润的效率。

由于它是在⽬标函数的最优值中体现的，因此说Y∗包含了每种资源对⽬标函数的边际贡献。

线性规划的对偶原理3。

1 线性规划的对偶问题一、 对偶问题的提出换位思考家具厂的线性规划问题,该问题站在家具厂管理者的角度追求销售收入最大213050m ax x x z +=⎪⎩⎪⎨⎧≥≤+≤+0,50212034212121x x x x x x某企业家有一批待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。

他 需要与家具厂谈判付给该厂每个工时的价格。

如果该企业家已对家具厂的经营情况有详细了 解，他可以构造一个数学模型来研究如何才能既让家具厂觉得有利可图,肯把资源出租给他, 又使自己付的租金最少.目标：租金最少；1y —付给木工工时的租金；2y -付给油漆工工时的租金2150120m in y y w +=所付租金应不低于家具厂利用这些资源所能得到的利益1）支付相当于生产一个桌子的木工、油漆工的租金应不低于生产一个桌子的收入 502421≥+y y2）支付相当于生产一个椅子的木工、油漆工的租金应不低于生产一个椅子的收入 30321≥+y y3）付给每种工时的租金应不小于零 0,021≥≥y y二、 原问题与对偶问题的数学模型1. 对称形式的对偶原问题和对偶问题只含有不等式约束时，一对对偶问题的模型是对称的，称为对称形式的对偶。

原问题:⎪⎩⎪⎨⎧≥≥=0min X b AX CX z对偶问题:⎪⎩⎪⎨⎧≥≤=0max Y C YA Yb w2. 非对称形式的对偶若原问题的约束条件全部是等式约束（即线性规划的标准型）,即⎪⎩⎪⎨⎧≥==0min X b AX CX z则其对偶问题的数学模型为⎪⎩⎪⎨⎧≤=是自由变量Y C YA Yb w max可把原问题写成其等价的对称形式:min z =CX AX ≥b AX ≤b X ≥0即 min z =CX⎥⎦⎤⎢⎣⎡-A A X ≥⎥⎦⎤⎢⎣⎡-b bX ≥0设Y 1=(y 1,y 2,…,y m ）， Y 2=（y m+1，y m+2，…,y 2m ）。

第四节 线性规划对偶问题对偶理论是线性规划的重要组成部分，研究互为对偶的线性规划问题，不仅在理论上有重要意义，而且具有深刻的经济意义。

（一 ）对偶问题的提出 引例：设某企业计划生产甲、乙两种产品，要用A 、B 、C 三种不同的原料。

按工艺规定，产品甲和乙所需要的原料数及其它有关数据见下表求应如何安排生产计划，才能使总利润最大？设12,x x 分别是产品1，产品2的生产数量，则问题的线性规划模型是1212121212m ax 150********34120..55150,0z x x x x x x s t x x x x =++≤⎧⎪+≤⎪⎨+≤⎪⎪≥⎩（1）上述线性规划模型在使用有限资源条件下，从追求最大利润的角度讨论如何组织生产。

现在从另一角度来讨论问题。

如果另一企业想从该企业购买这3种原材料，这时企业主就要考虑这些原材料应如何定价，才对双方都合理。

设123,,y y y 分别表示企业主对A 、B 、C 三种不同的原料制定的单位价格。

从企业主考虑，出售这些原材料所得到的收入应不低于用这些原材料进行生产所得到的利润，否则自己生产更为有利。

具体来说，若用2个单位原材料A 、3个单位原材料B 和5个单位原材料C 可以生产一单位产品1而获利150元，那么就应有123235150y y y ++≥同理，对产品2作类似分析也应有 123345210y y y ++≥把企业所有的原材料都出售，其总收入为123100120150w y y y =++，表面看w 越大的越好，但实际上定价太高会失去竞争能力。

在保证出售原材料不会比自己生产获利少的前提下，为了使企业的竞争能力达到最大，应该极小化总收入w 。

为此需解如下线性规划问题：123123123123m in 100120150235150..345210,,0w y y y y y y s t y y y y y y =++++≥⎧⎪++≥⎨⎪≥⎩(2)上述两个线性规划问题是为了提高企业的经济效益，从两个不同的角度出发而形成的一对线性规划问题。

线性规划的对偶问题
线性规划的对偶问题
线性规划的对偶问题是线性规划中的一个分支，它的求解历程和一般的线性规
划想法不同，而且根据不同的约束条件最终能够求出最优解，使得问题获得最小的成本或最大的利润。

线性规划的对偶问题是从原问题的另一个角度去理解原来的模型，它将原有问
题转化为无穷多个单纯形模型，检验原问题各部分的存在可行性。

线性规划的对偶问题以可行性条件检验为主要特色，它可以检验原问题在具体变量形式下各限制条件之间的约束关系，这特别有利于解决在实际问题中模型中非可行情况的求解问题。

求解线性规划的对偶问题的核心思想就是将原问题的约束转换成一系列的子问题，通过求解子问题，再根据子问题的结果得到原问题的求解解，先求解子问题的时间复杂度会比求解原问题的复杂度小很多。

线性规划的对偶问题即其可行性检验的能力，由于其能有效处理问题中约束条
件之间存在的相互作用，具有优越的求解能力，因而在很多复杂的线性规划问题中都被广泛应用。

线性规划的对偶问题不仅能使求解结果更加准确，而且可以大大减少求解的时间，使程序性能更加突出。