《运筹学之线性规划的对偶理论和灵敏度分析课件丁剑飞.ppt》由会员分享，可在线阅读，更多相关《运筹学之线性规划的对偶理论和灵敏度分析课件丁剑飞.ppt（97页珍藏版）》请在金锄头文库上搜索。
1、窗含西岭千秋雪，门泊东吴万里船 对偶是一种普遍现象,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,2.1 单纯形法的矩阵描述 上一章我们讨论了如何运用单纯形表，通过迭代调整变量，求出线性规划模型的最优解。这一节我们运用矩阵、向量的形式来揭示这种迭代运算的本质，以利于讨论线性规划的对偶理论与灵敏度分析。 假如有一个求最大值的线性规划标准形式，其初始基变量为XI，迭代如干次后，其基变量为XB，先不妨假设XI与XB中无相同的变量。,将模型填入单纯形表2.1中：,第二章 线性规划的对偶理论和灵敏度分析,约束条件：,表2.1,第二章 线性规划的对偶理论和灵敏度分析,经过
2、若干次迭代后，基变量变为XB，则在表2.1中，基一列的XI应改为XB，为计算出XB的取值，XB一列中，约束条件行的B应变为I，则当非基变量XN，XI变为零时，在解的一列中直接可得XB的取值，故可在上表中的约束条件行两边同左乘B-1，得表2.2：,表2.2,在这里不妨假设B-1是存在的，因为如果B不可逆，说明约束条件中含有多余的约束方程，或含相关变量，可采取适当方法处理之，以保证B的可逆性。 为判断当前的基本可行解是否最优，必须将表2.2中的基变量XB从目前函数行中消去，可通过以下运算来实现，将约束条件行左乘CB后，加到目标函数行得：,第二章 线性规划的对偶理论和灵敏度分析,这样就得到了：当XB
3、为基变量时，解为B-1b，目标函数值为CBB-1b，非基变量XN，XI的检验数分别为CBB-1N-CN和CBB-1-CI 。当CBB-1N-CN和CBB-1-CI都满足最优条件时，已得最优解，否则，当前的基本解还不是最优的，还需进一步迭代，考虑新的XB（基变量）。,第二章 线性规划的对偶理论和灵敏度分析,表2.3,通过以上对单纯形表矩阵形式的分析可以看出：当单纯形表迭代到某一步时，表格中的所有数据均由基变量XB决定，即我们取XB在约束条件中的系数矩阵为B，求出它的逆矩阵B-1，再取XB在目标函数中的系数CB，则利用表2.3可将整个单纯形表计算出来。只是我们在计算时，我们要注意以下三点： 1.在
4、表2.1到表2.3中，我们将所有的变量分为XB，XN和XI，它们在目标函数中的系数分别记,第二章 线性规划的对偶理论和灵敏度分析,为B，N，和I。这种记法主要方便表示和运算。就其本质而言，在迭代计算中，它们运算的实质是完全一样的。即都是对约束方程乘以B-1，而且目标函数行的运算是利用约束方程消去目标函数行基变量的系数。这些运算都是按列运算的，各列之间并没有任何运算。例如对任意一个变量xj（不论它属于XB，XN还是XI），记其在目标函数中的系数为cj，在约束条件中的系数为pj，则迭代后的xj在目标函数的系数都为CBB-1pj-cj，约,第二章 线性规划的对偶理论和灵敏度分析,束条件中的系数都为B
5、-1pj。只是由于pj的初始状态不同，在迭代后的表才会有不同的形式。 2.可能有一个或几个变量同时出现在XB与XI中，也就是说，有一个或几个变量既是迭代若干次后的基变量，也是初始基变量。虽然它们每个变量在单纯形表中占一列，但是我们在讨论XI时要把它考虑进去，在讨论XB时也要把它考虑进去，即一列扮演了两个角色。 3.由于单纯形表中个变量的位置一般按x1， x2，xn等事先确定，而未必会正好按基变,第二章 线性规划的对偶理论和灵敏度分析,量XB，非基变量XN等排好，好在线性规划约束条件、目标函数中，交换变量的先后位置是不要紧的，我们可以通过交换变量的位置来实现XB，XN，XI的排列，或更常用的是，
6、就用原有的次序，按列来进行计算，选取有关的数据。,第二章 线性规划的对偶理论和灵敏度分析,2.2 改进单纯性法 我们在第一章已经熟悉了单纯形法的表格计算。用这种方法求解线性规划问题时，发现每一步迭代过程中不必要地计算了很多与下一步迭代无关的数据，严重影响了计算效率。在单纯性法的迭代过程中，基矩阵的逆阵B-1求出后，调出行表中的其他行和列的数据随之可以确定。这就是单纯形法的出发点。,第二章 线性规划的对偶理论和灵敏度分析,2.2.1 用改进单纯形法求解线性规划的计算步骤 (1)根据给出的线性规划问题，在加入松弛变量后，得到初始基变量。求解初始基变量B的逆阵B-1，求出初始解 ，然后计算单纯性乘子
7、Y=CBB-1。 (2)计算非基变量XN的检验书N，N=CN-CBB-1N。若N0，已经得到最优解，停止计算。否则转下一步。 (3)根据max(j| j0)= k所对应的非基变量Xk为调入变量计算B-1N，若B-1N 0则问题无解，停止计算，否则转下一步。,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,(4)求出 它对应的基变量Xl跳出变量。可以得出一组新的基变量和基矩阵B。 (5) 计算基矩阵的逆阵B-1，求出B-1b和Y=CBB-1。重复（2）（5）。 如果我们细心的话，只要注意单纯形法的计算步骤就可以看出上一步的基B与下一步的基B之间只差了一个变量。如果
8、只根据B-1和调入变量Xk,的系数变量来计算出B1-1，而不是直接求B1-1，计算过程为： (a)把mm的单位阵表示为：Im=(e1,e2,em) (b)设Xk为调入变量，Xl为调出变量，则有,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,第l行,第二章 线性规划的对偶理论和灵敏度分析,2.2.2例子 例2.1用改进单纯形法求解,解：,第二章 线性规划的对偶理论和灵敏度分析,x1 x2 x3 x4 x5,计算非基变量检验数 2=31=1，因此，选x2作为调入变量，则：,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性
9、规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,第三步迭代略，最后得最优解,第二章 线性规划的对偶理论和灵敏度分析,2.3对偶问题的提出 例2.2 某公司在计划期内安排生产I、II两种产品。已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表所示，该工厂每生产一件产品I可获取2元，每生产一件产品II可获利3元，问如何安排计划使该工厂获利最多。,第二章 线性规划的对偶理论和灵敏度分析,解 设x1，x2分别表示产品I和II的产量，则可建立如下线性规划模型： max z=2x1+3x2 x1+2x28 4x116 4x212 x1，x20 我们从另一个角度考虑这个问题。假
10、如该工厂的决策者决定不生产产品I、II，而将其所有资源出售或出租。这时工厂的决策者就要考虑给每个资,第二章 线性规划的对偶理论和灵敏度分析,S.t.,源如何定价的问题。设用y1，y2，y3分别表示出租单位设备台时的租金和出让单位原材料A、B的附加额。它们在定价决策时，作如下比较：若用一个单位设备台时和4个单位原材料A可以生产一件产品I，可获利2元，那么生产每件产品I的设备台时和原材料出租和出让的所有收入应不低于生产一件产品I的利润，这就有： y1+4y22 同理，将生产每件产品II的设备台时和原材料的出租和出让的所有收入应不低于生产一件产品II的利润，这就有：,第二章 线性规划的对偶理论和灵敏
11、度分析,2y1+4y33 把所有的设备台时和资源出租和出让，其收入为： f=8y1+16y2+12y3 从工厂的角度看，f当然是越大越好，但从接受者眼光看，f是越小越好，所以工厂决策者只可以在满足所有产品利润条件下，使其总收入尽可能的小。因此可以列出如下线性规划问题：,第二章 线性规划的对偶理论和灵敏度分析,我们称这个问题为原问题的对偶问题。各模型中有关数据的“位置”示意图如下图所示。,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,2.3.2 用矩阵形式表示线性规划的对偶问题 从上一节得到的检验数的表达式是 CN-CBB-1N与-CBB-1 另外我们知道，当检
12、验数 CN-CBB-1N0 (2-9) 这表示线性规划问题已得到最优解，可见上面两式是得到最优解条件。 由上一节我们知道： Y=CBB-10称为单纯形子，,第二章 线性规划的对偶理论和灵敏度分析,由于，CB-CBB-1B=0 所以 (CB,CN)-(CBB-1B，CBB-1N)=C-CBB-1(B,N)0 包括基变量在内的所有检验数可以用C-CBB-1A0表示，因此可知：C-YA0 移项后得到：YAC 由于 Y=CBB-1 同乘于b得：Yb=CBB-1b=z,第二章 线性规划的对偶理论和灵敏度分析,由于Y的上界为无穷大，所以只存在最小值。 从而可以得到另一个线性规划问题： min f=Yb Y
13、Ac Y0 我们称它为原线性规划问题的对偶问题。 从这里两个线性规划问题的表达式可以看出：根据原线性规划问题的系数矩阵A、C、b就可以写出它的对偶问题。以例2.2为例原线性规划问题各系数矩阵是：,第二章 线性规划的对偶理论和灵敏度分析,S.t.,第二章 线性规划的对偶理论和灵敏度分析,2.3.3 线性规划问题的对偶问题举例 例2.3 某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中占用的设备机时数、每件产品可以获得的利润以及三种设备可利用的时数如下表。求最大利润的方案。,第二章 线性规划的对偶理论和灵敏度分析,根据例2.2的分析思路不难得出下面一对对偶问题。,第二章 线
14、性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,例2.4 资源利用问题 考虑，资源拥有者为了实现一定的收入目标，将其所拥有的资源出售，给每个资源如何定价？,第二章 线性规划的对偶理论和灵敏度分析,解 yi(i=1,2,m)表示出售单位数量的第i种资源的价值。资源拥有者在作出出售资源的决策时，考虑出售资源的收入不应低于生产所获得的收入，则有： 如果资源所有者将资源出售，则他得到的总收入 ，资源买方希望越小越好，所以资源拥,第二章 线性规划的对偶理论和灵敏度分析,有者出售每一种资源的合理估价，可以通过求解线性规划问题而得到。 对于同一个资源利用问题，从不同的角度考虑，将可以得
15、到两个相互关联的线性规划模型，这就是线性规划的对偶问题。,第二章 线性规划的对偶理论和灵敏度分析,2.3.4 原问题与对偶问题的关系 1. 线性规划问题是对称形式 以上是一对对偶问题，它们之间的关系可以用下表表示。,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,如上例所示，对偶规划之间具有下面的关系： “max，”“min，” “A”“AT” “C，b” “b，C” 变量均非负 2.线性规划问题是非对称形式 非对称形式的规划可以按照下面的对应关系直接给出其对偶规划： 将模型统一为“max，”或“min，”。,第二章 线性
16、规划的对偶理论和灵敏度分析,若原规划的某个约束条件为等式，则对偶问题中与此约束对应的那个变量取值没有非负约束。 若原规划的某个约束没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。 证明：,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,2.4 对偶问题的基本性质 性质1 对称性 对偶问题的对偶问题是原问题 性质2 弱对偶性 若X*是原问题的可行解，Y*是对偶问题的可行解，则存在CX*Y*b 性质3 可行解是最优解的情况 设X*是原问题的可行解，Y*是对偶问题的可行解，则当CX*=Y*b时，X*、Y*分别是最优解。,第二章 线性规划的对偶理论和灵敏度分析,性质4 线性规划的对偶原理 （1）若原问题有最优解，那么对偶问题也有最优解，且二者最优值相等（强对偶性质）。 （2）若原问题（对偶问题）的解
