线性规划的对偶问题.doc

教案五 线性规划的对偶问题
教学内容 第四节 线性规划的对偶问题
1．线性规划的对偶问题
2．对偶单纯形法
3．线性规划的灵敏度分析
4．线性规划在卫生管理中的应用
教学学时 7学时
教学目标 1．理解对偶问题的基本概念
2．掌握对偶单纯形法
3．掌握线性规划的灵敏度分析
4．掌握线性规划在卫生管理中的应用
重点难点 重点是对偶问题的基本概念、对偶单纯形法线、灵敏度分析、线性规划在卫生管理中的应用。难点是对偶问题的基本概念和线性规划的灵敏度分析
教学手段 教师与学生互动 使用多媒体课件
教学过程
一、复习巩固
1．单纯形法的基本原理（见课件）
2．单纯形解法（见课件）
3．大法（见课件）
二、讲授新课
1．线性规划的对偶问题
（1）对偶问题的基本概念（见课件）
对偶现象 每一个线性规划都伴随着另一个线性规划，两者有密切关系，互为对偶．其中一个问题称为原问题，另一个问题称为其对偶问题．两者间只要得到其中一个问题的解，那么也就得到了另一个问题的解．
下面通过一个实例来解释对偶线性规划的概念．
例2-12 以例2-1为例，我们讨论了一个制药厂的生产计划的数学模型及其解法．
现在假定该制药厂决定在计划期内不生产药品Ⅰ、Ⅱ，而将生产设备的有效台时全部租给某公司，那么该公司应对设备每小时付多少租金，才能使成本最小，而又能为制药厂所接受？
从租用设备的公司的角度考虑，一是所付的租金越低越好；二是所付的租金总额能使制药厂接受，即租金应不低于制药厂自己生产该两种药品所得利润，否则，制药厂宁可自己生产，而不租给公司．
设公司租用该制药厂四种设备的租金（元/小时）分别为、、和．在考虑租用设备的定价时，能使该制药厂接受的条件是：
公司租用该制药厂用以生产每千克药品Ⅰ所需四种设备的台时的租金不应少于200元，即

同样，公司租用该制药厂用以生产每千克药品Ⅱ所需四种设备的台时的租金不应少于300元，即

公司在考虑自身利益时，其目标是使付出的租金总额为最小，即

于是，上面的问题可以用下列线性规划的数学模型表示：

若把制药厂利润最大的线性规划问题称为原问题，则想租用四种设备的公司的租金最小的线性规划问题称为原问题的对偶问题（dual problem）；反之，若把租用四种设备的公司的租金最小的线性规划问题称为原问题，则制药厂利润最大的线性规划问题称为原问题的对偶问题．
影子价格 一般地，我们称对偶问题的最优解为原问题约束条件的影子价格，即对偶问题的解称为第种资源的影子价格．它并不是某种资源在市场上的价格，而是代表单位资源在最优利用的条件下所产生的经济效果．为了和市场价格相区别，我们才称它为影子价格．它在经济上是一个很有意义的数据，通过它我们可以知道，当增加某种资源时，可以使利润增长的大小．另外，影子价格还给出了是否应当购进某种资源以增加生产量，而获得更多利润的价格标准．
（2）对称的对偶线性规划（见课件）
如果一个线性规划具备下面两个条件，则称它具有对称形式：①所有的变量都是非负的；②所有的约束条件都是不等式，而且在目标函数是求极大值的情况，不等式具有小于和等于（）的符号，在目标函数是求极小值的情况，不等式具有大于和等于（）的符号．
对称形式的原问题和对偶问题叫做对称的对偶线性规划．
原问题和对偶问题在形式上的对比 如果我们把线性规划

…………………………

称为原问题，则必同时存在另一线性规划问题，我们称为对偶问题：

…………………………

而且
用简缩形式表示：
原问题为

对偶问题为

;
矩阵形式表示：
原问题为

对偶问题为 Min W＝Yb

其中，

原问题与对偶问题之间的关系
1）原问题是求目标函数的最大值，对偶问题是求目标函数的最小值．
2）原问题约束条件的右端项变成对偶问题目标函数的系数．原问题目标函数中的系数变成对偶问题约束条件的右端项．
3）原问题约束条件是“”，对偶问题的约束条件则是“”．
4）原问题约束条件的每一行正好对应于对偶问题的每一列，所以原问题中约束条件的数目等于对偶问题中变量的数目．
5）原问题中约束条件的每一列正好对应于对偶问题的每一行，所以原问题中变量的数目正好等于对偶问题中的约束条件的数目．
6）对偶问题的对偶规划正是原问题．
例2-13 设原问题为：

试写出它的对偶问题．
解

（3）非对称的对偶线性规划（见课件）
对于我们经常遇到的非对称形式的线性规划，我们可首先将其化为等价的对称形式的线性规划问题，然后再按对称的对偶线性规划原问题与对偶问题之间的对应关系，将其化为对偶问题．实际上，我们在考虑对称的对偶线性规划或非对称的对偶线性规划（dual of a nonnormal LP）时，也可以按表2-13原问题与对偶问题之间的对应关系，直接进行变换，得到原问题或对偶问题．
表2-13 原问题与对偶问题间的转换
原问题（或对偶问题）
对偶问题（或原问题）
目标函数
目标函数
约束条件数：个
对偶变量数：个
第个约束条件为“”
对偶变量0
第个约束条件为“”
对偶变量0
第个约束条件为“=”
对偶变量无非负条件
变量的数目：个
约束条件数：个
变量0
第个约束条件为“”
变量0
第个约束条件为“”
变量无非负条件
第个约束条件为“＝”
限定向量
成本或利润向量
成本或利润向量
限定向量
系数矩阵
系数矩阵

例2-14 原问题为：

，符号不限
可按表2-13的原则，将原问题直接转化成对偶问题：

，，符号不限

（4）对偶问题的基本性质（见课件）
1）对偶问题的对偶是原问题（对称性质）．
2）若和分别是原问题和对偶问题的可行解，则（弱对偶性质）．
3）设和分别是原问题和对偶问题的可行解，当两者目标函数值相等，即＝时，，分别是原问题和对偶问题的最优解（可行解是最优解的性质）．
4）若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等（对偶性质）．
5）若和分别是原问题和对偶问题的可行解，则和为原问题及对偶问题最优解的充分条件为：
＝0和＝0
其中，＝, 是原问题的松弛变量，＝（）, 是对偶问题的剩余变量（松弛互补性质）．
此性质在线性规划中有广泛应用．如从已知的原问题最优解（或对偶问题最优解）求取对偶问题最优解（或原问题最优解）；验证原问题的可行解是否最优解等等．
6）原问题的检验数对应于对偶问题的一个基本解．
由对偶性质可知，在求解原问题的过程中，利用单纯形表每一次迭代所得的检验数与对偶问题的基本解仅仅相差一个符号，于是原问题获得最优解时对应的单纯形表中检验数的相反数，即为对偶问题的最优解．
例2-15 设原问题为：

已知其对偶问题的最优解为*＝1.2，*＝0.2，相应的目标函数最小值*＝28，试利用对偶性质求该问题的最优解．
解 原问题的对偶问题为：

由松弛互补性质可知，在最优条件下，＝0和＝0，即
**＝0，**＝0，**＝0，**＝0，**＝0，**＝0；这里*（），*（）分别为原问题的松弛变量及对偶问题的剩余变量．
由* ＝1.2>0，可以推出* =0；由* ＝0.2>0，可推出* =0．
由对偶约束*+2* =1.6>1，知* >0,于是* =0；同理，由2*+* =2.6>2，知* >0,于是* =0．
根据上述结果，原约束可以转化成二元一次线性方程组：
* +* =20
* +* =20
解方程得* =* =4
综上所得，原问题的最优解为* =，相应的目标函数最优值为* =28．
由对偶性质还可以推论：
1）若原问题可行，但有无界解（或称无有限最优解），则对偶问题不可行；若对偶问题可行，但有无界解（或称无有限最优解），则原问题不可行；
2）若原问题可行，而对偶问题不可行，则原问题有无界解（或称无有限最优解）；若对偶问题可行，而原问题不可行，则对偶问题有无界解（或称无有限最优解）．
2．对偶单纯形法
前面已叙述原问题与对偶问题的解之间的对应关系．在用单纯形法进行迭代时，在列中得到的是原问题的基本可行解，而在检验数（）行得到的是对偶问题基本解的相反数．通过逐步迭代，当在检验数行得到的对偶问题的解也是可行解时，原问题和对偶问题都达到了最优解．所以，单纯形法的特点是保持原问题解的可行性，通过逐步迭代，使对偶问题的解由基本解变成基本可行解，这时原问题和对偶问题都达到了最优解．
那么根据对偶问题的对称性，我们也可以这样来处理：保持对偶问题的解是可行解（即），而原问题则从非可行解开始，通过迭代，逐步达到基本可行解．这样，也使原问题和对偶问题都达到了最优解．
事实上，对偶单纯形法（dual simplex method）并不是解对偶问题的单纯形法，而是应用对偶原理来求解原问题的最优解的一种方法．
（1）对偶单纯形法的要点（见课件）
例2-16 用对偶单纯形法求解下列线性规划问题

解 此问题可用大法去解，但用大法求解很麻烦，现在用对偶单纯形法求解．先将原问题化为标准 形式，为此引入剩余变量，，令，得

然后将约束条件等式的两边都乘以（-1），得到

建立这个问题的初始单纯形表，见表2-14：
表2-14 对偶单纯形法求解例2-16（1）

-1600
-2500
-400
0
0

0

-2
-5
-1
1
0
-4
0

-2

0
0
1
-3

-1600
-2500
-400
0
0
=0

在这个初始单纯形表中，、是基本变量，初始单纯形表所对应的基本解为＝，它是一个不可行解．而全部检验数，即所对应的对偶问题的一个基本解也是一个可行解, ，．下面的迭代是在保持检验数小于等于零的条件下，逐步使，．为了满足上面要求，迭代的要点是：
1）首先确定换出变量：选择具有负数的基本变量中绝对值最大的基本变量为换出变量．
2）确定换入变量：用换出变量那一行具有负值的系数分别去除同列的检验数，取最小商数所对应的变量为换入变量；如果换出变量那一行无负值的系数，则原问题无可行解．
3）把换出变量的那一行除以枢元位置的系数，使枢元位置变为1．
4）进行行变换，使除枢元外的其他枢列位置变为0．
5）进行最优解检查．如果所得的基本解都是非负的，则此解即为最优解．如果基本解中还有负的数值，则重复第1步继续迭代，直到所有基本变量为非负的数值为止．
（2）表解形式的对偶单纯形法（见课件）
按上述迭代的要点，对表2-14继续运算，见表2-15．
表2-15 对偶单纯形法求解例2-16（2）

-1600
-2500
-400
0
0

0

-2
-5
[-1]
1
0
-4
0

-2

0
0
1
-3

-1600
-2500
-400
0
0
=0

800
500
400

-400

2
5
1
-1
0
4
0

-2

0
0
1
-3

-800
-500
0
-400
0
=-1600

400
200

-400

[-2]
0
1
-1
2
-2
-2500

1
0
0

-400
0
0
-400
-200
=-2200

200

400

-1600

1
0

-1
1
-2500

0
1

0
0
-200
-200
-600
=-2600
表2-15中列数字全为非负，检验数全为非正，故问题的最优解为
* =，最优值* ＝2600．
若对应两个约束条件的对偶变量分别为和，则对偶问题的最优解为
* =，最优值＝2600．
（3）对偶单纯形法的优点及用途（见课件）
1）初始解可以是非可行解，当检验数都是小于等于零时，就可以进行基变换，这样就避免了增加人工变量，使运算简化．
2）对变量较少，而约束条件很多的线性规划问题，可先将其变为对偶问题，再用对偶单纯形法求解，简化计算．
3）用于灵敏度分析．
3．线性规划的灵敏度分析
在上述讨论线性规划问题时，假定，，都是精确的数据，然而在大多数实际问题中，这些系数往往是估计值和预测值，而且它们也随着某些条件的变化而变化．因此很自然会想到，当这些系数中的一个或几个发生变化时，已求得的规划问题的最优解会发生什么变化？如果最优解发生了变化，又怎样用最简单的方法找到新的最优解？这就是线性规划灵敏度分析（sensitivity analysis of LP）的任务．
（1）单纯形法的矩阵表达式（见课件）
设有一线性规划问题，用矩阵表示为

式中，为矩阵，为1×行向量，为×1列向量，为×1列向量，0为×1列向量．
现引入松弛变量
化为标准型

，
其中，是阶单位矩阵，约束条件也可写成和 ，0有个元素．
如果我们把系数矩阵分为两块，，也称基矩阵（即原始系数矩阵中对应于基本变量的列所组成的矩阵），对应于的变量是基本变量，用向量表示，其他的变量则为非基本变量，于是将也分为两块：

向量也可分为两块，其中是目标函数中基本变量向量的系数行向量，是目标函数中非基本变量向量的系数行向量．所以
于是线性规划问题可以写成

在单纯形法的每次迭代中，是用行变换的方法将基矩阵变成单位矩阵．用矩阵方法，则将上述约束方程的两边乘以基矩阵的逆矩阵,于是可得
（2-9）
即: （2-10）
所以 （2-11）
将式（2-11）代入目标函数可得

（2-12）
或者 （2-13）
从式（2-9）可知，在单纯形表每次迭代后,每个变量的系数列向量是的逆阵乘以该变量的原始列向量而得到的，右端常数的列向量是的逆阵乘以右端常数的原始列向量而得到的．从式（2-10）可见，其松弛变量的系数矩阵正好是基矩阵的逆阵．更一般地理解，在任一单纯形表中相应于初始基本变量的那些列给出了相应于该表格的基矩阵的逆阵．
例如第二章第三节的例2-8中，表2-4、表2-5、表2-6和表2-7给出了单纯形法的计算过程，其中表2-7为最优解单纯形表，其基本变量是,，和．对应于表2-7的基矩阵

所以对应于表2-7的列向量是
＝×＝
式中为原始单纯形表中对应于的列向量.
对应于表2-7的列向量是
＝×＝
式中为原始单纯形表中对应于的列向量.
对应于表2-7的列向量是
＝×＝
式中为原始单纯形表中右端列向量.
对应于表2-7的非基本变量的检验数是，松弛变量的检验数是．
（2）系数变化的灵敏度分析（见课件）
系数变化的灵敏度分析是在决策变量和约束条件数目不变时，研究各种系数的变化对最优解的影响．它主要考虑两种情况：一是这些系数在什么范围内变化时，已得到的最优解保持不变，或者最优解的基本变量保持不变（但数值有所改变）；二是如果某些系数的变化引起最优解的变化，如何用最简便的方法求出新的最优解．
目标函数中变化范围的确定 假设其他参数不变，仅目标函数中的系数变成＋，现求不改变最优解的的大小．这分两种情况：
1）是非基本变量的成本或利润系数
因为 （）
（式中是基本变量的成本或利润系数）
所以改变非基本变量的成本或利润系数，Zj不变，但变为新的检验数：
要想保持极大化问题最优解不变，即，则：．
2）是基本变量的成本或利润系数
因为

要保持极大化问题最优解不变，则．
对于基本变量检验数总为零，而对于非基本变量，因，所以要求检验数小于等于0变为：

例2-17 以例2-8的最终计算表（表2-7）为例．设基本变量在目标函数中的系数变化了；这时表2-7的最终计算表便成为表2-16所示．
表2-16 基本变量利润系数变化的灵敏度分析

200
300＋
0
0
0
0

0

0
0
1
-1

0
0
200

1
0
0
0

0
4
0

0
0
0
-2

1
4
300＋

0
1
0

0
2

0
0
0

0
=1400＋2

这时要保持最优解不变，则必须满足下列不等式：
-150-=-150-0
-=-0

即可在[0,400]间变动，不影响原来的生产计划安排，但制药厂收益变化了．
在约束条件中变化范围的确定 初始单纯形表中的变化，除了影响最优解的数值之外，不影响最终单纯形表中的其他系数．所以只要保证最后的解仍是可行解，那么它仍然是最优解．即

式中，为右端常数变化后，最终单纯形表右端常数向量；为右端常数未变化时，最终单纯形表右端常数向量．
例2-18 在例2-8中，如果第三个约束条件发生变化，变化量为，为了使最后的解仍为可行解，应满足下列不等式：
＋＝＋
＝

所以在[－8,0]之间变动时（即的变化范围在[8,16]时），原来最优解的基本变量不变，但最优解的值发生变化．例如，为－2时（即＝14），则
＝＋＝＝
最优解*＝，最优值*＝1375，见表2-17．
表2-17 右端常数变化后的最优解

200
300
0
0
0
0

0

0
0
1
-1

0

200

1
0
0
0

0

0

0
0
0
-2

1
3

300

0
1
0

0

0
0
0
-150

0
=1375

如果的变化超出了[－8,0]的范围，这时最优解的基本变量就发生变化．在这种情况下要用对偶单纯形法继续求出新的最优解．
例如为2时（即＝18），则
＝＋＝＝
则最终单纯形表变为表2-18．

表2-18 右端常数变化后的对偶单纯形法求解

200
300
0
0
0
0

0

0
0
1
-1

0

200

1
0
0
0

0

0

0
0
0
-2

1
5
300

0
1
0

0

0
0
0
-150

0
=1425

150
50

0

0
0
-4
4
1
0
2
200

1
0
1
-1
0
0
4
0

0
0
2
-4
0
1
4
300

0
1

1
0
0
2

0
0
-50
-100
0
0
=1400

新的最优解*＝，最优值Z*＝1400．
矩阵A中的系数改变对最优解的影响 当对应于的变量为非基本变量的系数时，它的变化不会改变基矩阵和它的逆阵，所以只需修改单纯形表中所对应的列就可以了．

若极大化问题0,则得到的还是新问题的最优单纯形表，最优解和最优值不变，否则可用单纯形法求解．
当对应于的变量为基本变量的系数时，它的变化会改变基矩阵和它的逆阵，所以会影响到最终单纯形表的右端向量和非基本变量对应的列．下面就举例讨论此种基本变量的系数变化情况．
例2-19 以例2-1为例，若计划生产的药品Ⅰ的工艺结构有了改进，相应地生产单位药品Ⅰ所需设备的台时改为（3,2,5,2），它的利润也提高到每千克400元．试分析已求得的最优计划有何变化？
解 当的系数列向量变化后,原最终单纯形表（表2-7）中的系数列向量变成:
==
原最终单纯形表变成表2-19：
表2-19 决策变量系数改变对最优解的影响（1）

400
300
0
0
0
0

0

0
1
-1

0
0
400

0
0
0

0
4
0

0
0
-2

1
4
300

1
0

0
2

由的系数列向量可知，到此尚未完成行变换，所以需继续使的系数列向量变成单位列向量，于是得到表2-20．
表2-20 决策变量系数改变对最优解的影响（2）

400
300
0
0
0
0

0

0
0
1
-1

0

400

1
0
0
0

0

0

0
0
0
-2

1

300

0
1
0

0

0
0
0
-150
-20
0
=1520

因为0，所以新的最优解，最优值*＝1520元.
4．线性规划在卫生管理中的应用
（1）放射科的业务安排（见课件）
医院放射科可以开展线平片检查和检查业务，现拟购买磁共振仪，以增设磁共振检查业务．为此医院收集了有关信息，以决策是否购买磁共振仪．
医院估计今后放射科如果开展此3项业务，在现有放射科医务人员力量和病人需求的情况下，每月此3项业务的最多提供量为1800人次．平均每人次检查时间、每月机器实际可使用时间、平均每人次检查利润如下表2-25．
表2-25 放射科3项检查时间与利润及机器可使用时间

放射科业务
项 目
线平片检查
检查
磁共振检查
平均每人次检查时间（小时/次）
0.1
0.25
0.5
每月机器实际可使用时间（小时）
300
120
120
平均每人次检查利润（元/次）
20
60
10

设每月线平片检查、检查和磁共振检查的业务量分别为,和人次，则使医院放射科此3项业务收入最多的线性规划模型如下：

利用单纯形法可得最终单纯形表（见表2-26）．
表2-26 放射科业务安排最终单纯形表

20
60
10
0
0
0
0

0
x4
0
0

1

0

168
60
x2
0
1
0
0
4
0
0
480
0
x6
0
0

0
0
1
0
120
20
x1
1
0
1
0
-4
0
1
1320

0
0
-10
0
-160
0
-20
*=55200
最优解*＝，最优值*＝55200．
从最终单纯形表上可读出如下信息：
1）医院从放射科收益的角度考虑，不应购买磁共振机.
2）在每月线平片检查和检查业务量各为1320人次和480人次时，放射科利润最大，达55200元．
3）在最优业务安排情况下，每月光机仍有168小时未实际利用，故它的影子价格为0元/小时；每月机可使用的时间已完全利用，它的影子价格为160元/小时，如果市场上能租到机的价格低于影子价格160元/小时，那么就应当租用机，增加检查业务，以求得更高的利润．
4）在最优业务安排情况下，每月线平片检查和检查的服务量已达到现有的最大量．医院如果想通过从人才市场上聘用医务人员以增加放射科的服务能力，则只有当增加一个病人的服务量所需额外增加的人员招聘费和宣传费低于20元时，才是适宜的，可使放射科的利润更高．
三、课堂练习（见课件）
四、小 结 （见课件）
五、作 业 （见课件）