运筹学4

窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象第二章线性规划的对偶理论和灵敏度分析第二章线性规划的对偶理论和灵敏度分析2.1单纯形法的矩阵描述上一章我们讨论了如何运用单纯形表，通过迭代调整变量，求出线性规划模型的最优解。这一节我们运用矩阵、向量的形式来揭示这种迭代运算的本质，以利于讨论线性规划的对偶理论与灵敏度分析。假如有一个求最大值的线性规划标准形式，其初始基变量为XI，迭代如干次后，其基变量为XB，先不妨假设XI与XB中无相同的变量。将模型填入单纯形表2.1中：第二章线性规划的对偶理论和灵敏度分析0,,),,(maxINBINBIINNBBXXXbXXXINBXCXCXCz基XBXNXI解z-CB-CN-CI0XIBNIb约束条件：表2.1第二章线性规划的对偶理论和灵敏度分析经过若干次迭代后，基变量变为XB，则在表2.1中，基一列的XI应改为XB，为计算出XB的取值，XB一列中，约束条件行的B应变为I，则当非基变量XN，XI变为零时，在解的一列中直接可得XB的取值，故可在上表中的约束条件行两边同左乘B-1，得表2.2：基XBXNXI解z-CB-CN-CI0XBIB-1NB-1B-1b表2.2在这里不妨假设B-1是存在的，因为如果B不可逆，说明约束条件中含有多余的约束方程，或含相关变量，可采取适当方法处理之，以保证B的可逆性。为判断当前的基本可行解是否最优，必须将表2.2中的基变量XB从目前函数行中消去，可通过以下运算来实现，将约束条件行左乘CB后，加到目标函数行得：第二章线性规划的对偶理论和灵敏度分析这样就得到了：当XB为基变量时，解为B-1b，目标函数值为CBB-1b，非基变量XN，XI的检验数分别为CBB-1N-CN和CBB-1-CI。当CBB-1N-CN和CBB-1-CI都满足最优条件时，已得最优解，否则，当前的基本解还不是最优的，还需进一步迭代，考虑新的XB（基变量）。第二章线性规划的对偶理论和灵敏度分析基XBXNXI解zOCBB-1N-CNCBB-1-CICBB-1bXBIB-1NB-1B-1b表2.3通过以上对单纯形表矩阵形式的分析可以看出：当单纯形表迭代到某一步时，表格中的所有数据均由基变量XB决定，即我们取XB在约束条件中的系数矩阵为B，求出它的逆矩阵B-1，再取XB在目标函数中的系数CB，则利用表2.3可将整个单纯形表计算出来。只是我们在计算时，我们要注意以下三点：1.在表2.1到表2.3中，我们将所有的变量分为XB，XN和XI，它们在目标函数中的系数分别记第二章线性规划的对偶理论和灵敏度分析为B，N，和I。这种记法主要方便表示和运算。就其本质而言，在迭代计算中，它们运算的实质是完全一样的。即都是对约束方程乘以B-1，而且目标函数行的运算是利用约束方程消去目标函数行基变量的系数。这些运算都是按列运算的，各列之间并没有任何运算。例如对任意一个变量xj（不论它属于XB，XN还是XI），记其在目标函数中的系数为cj，在约束条件中的系数为pj，则迭代后的xj在目标函数的系数都为CBB-1pj-cj，约第二章线性规划的对偶理论和灵敏度分析束条件中的系数都为B-1pj。只是由于pj的初始状态不同，在迭代后的表才会有不同的形式。2.可能有一个或几个变量同时出现在XB与XI中，也就是说，有一个或几个变量既是迭代若干次后的基变量，也是初始基变量。虽然它们每个变量在单纯形表中占一列，但是我们在讨论XI时要把它考虑进去，在讨论XB时也要把它考虑进去，即一列扮演了两个角色。3.由于单纯形表中个变量的位置一般按x1，x2，……，xn等事先确定，而未必会正好按基变第二章线性规划的对偶理论和灵敏度分析量XB，非基变量XN等排好，好在线性规划约束条件、目标函数中，交换变量的先后位置是不要紧的，我们可以通过交换变量的位置来实现XB，XN，XI的排列，或更常用的是，就用原有的次序，按列来进行计算，选取有关的数据。第二章线性规划的对偶理论和灵敏度分析2.2改进单纯性法我们在第一章已经熟悉了单纯形法的表格计算。用这种方法求解线性规划问题时，发现每一步迭代过程中不必要地计算了很多与下一步迭代无关的数据，严重影响了计算效率。在单纯性法的迭代过程中，基矩阵的逆阵B-1求出后，调出行表中的其他行和列的数据随之可以确定。这就是单纯形法的出发点。第二章线性规划的对偶理论和灵敏度分析2.2.1用改进单纯形法求解线性规划的计算步骤(1)根据给出的线性规划问题，在加入松弛变量后，得到初始基变量。求解初始基变量B的逆阵B-1，求出初始解，然后计算单纯性乘子Y=CBB-1。(2)计算非基变量XN的检验书σN，σN=CN-CBB-1N。若σN≤0，已经得到最优解，停止计算。否则转下一步。(3)根据max(σj|σj≥0)=σk所对应的非基变量Xk为调入变量计算B-1N，若B-1N≤0则问题无解，停止计算，否则转下一步。第二章线性规划的对偶理论和灵敏度分析01bBXXNB第二章线性规划的对偶理论和灵敏度分析(4)求出它对应的基变量Xl跳出变量。可以得出一组新的基变量和基矩阵B。(5)计算基矩阵的逆阵B-1，求出B-1b和Y=CBB-1。重复（2）~（5）。如果我们细心的话，只要注意单纯形法的计算步骤就可以看出上一步的基B与下一步的基B之间只差了一个变量。如果只根据B-1和调入变量XklliikiNBbBNBNBbB)()(0)()()(min11111的系数变量来计算出B1-1，而不是直接求B1-1，计算过程为：(a)把m×m的单位阵表示为：Im=(e1,e2,…,em)(b)设Xk为调入变量，Xl为调出变量，则有第二章线性规划的对偶理论和灵敏度分析第二章线性规划的对偶理论和灵敏度分析lkmklklkklkkmiaaaaaaeeeeEBBa-1-),,,,,,(E21121111。其中，第l行第二章线性规划的对偶理论和灵敏度分析2.2.2例子例2.1用改进单纯形法求解5,2,1,012416482..32max524132121ixxxxxxxxtsxxzi解：第二章线性规划的对偶理论和灵敏度分析]3,2[C],[X0,0,0],,[X100010001),,(12168b1004001004001210000N21N543B5430，，，，xxCxxxPPPBABx1x2x3x4x5计算非基变量检验数σ2=3σ1=1，因此，选x2作为调入变量，则：第二章线性规划的对偶理论和灵敏度分析]3,2[01000NBCCBNN)0,2(C],[N)3,0,0(),,,(],,[x3412,,28min0)()(min402111N511243243151112，，，于是得新的基对应调出变量为PPCxxxxPPPBPBPBbBPBBkiki第二章线性规划的对偶理论和灵敏度分析]4/3,2[1004014/1000102/101]3,0,0[]0,2[4/1000102/101B4/1000102/101,4/102/1,402B111N101-11112-10111NBCCBEEPBN非基变量检验数，第一次迭代，计算第二章线性规划的对偶理论和灵敏度分析的逆阵第二次迭代，计算由此得新的基对应的调出变量为，计算对应的调入变量为2221-11532241241231111B100014001,041,041B]0,0[],,[],3,0,2[],,,[],,[,x2,416,12min0)()(minx222EPCPPNCxxxXPPPBPBPBbBNBBkiki第二章线性规划的对偶理论和灵敏度分析41115212N112-12x44/13,28,min0)()(min,x]4/1,2[1000014/1000142/101]3,0,2[]0,0[4/1000142/1014/1000102/101100014001B222对应的调出变量为，计算对应的调入变量为非基变量的检验数kikiBNPBPBbBNBCCBE第三步迭代略，最后得最优解第二章线性规划的对偶理论和灵敏度分析244X251*xxx2.3对偶问题的提出例2.2某公司在计划期内安排生产I、II两种产品。已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表所示，该工厂每生产一件产品I可获取2元，每生产一件产品II可获利3元，问如何安排计划使该工厂获利最多。第二章线性规划的对偶理论和灵敏度分析III设备128台时原材料A4016公斤原材料B0412公斤解设x1，x2分别表示产品I和II的产量，则可建立如下线性规划模型：maxz=2x1+3x2x1+2x2≤84x1≤164x2≤12x1，x2≥0我们从另一个角度考虑这个问题。假如该工厂的决策者决定不生产产品I、II，而将其所有资源出售或出租。这时工厂的决策者就要考虑给每个资第二章线性规划的对偶理论和灵敏度分析S.t.源如何定价的问题。设用y1，y2，y3分别表示出租单位设备台时的租金和出让单位原材料A、B的附加额。它们在定价决策时，作如下比较：若用一个单位设备台时和4个单位原材料A可以生产一件产品I，可获利2元，那么生产每件产品I的设备台时和原材料出租和出让的所有收入应不低于生产一件产品I的利润，这就有：y1+4y2≥2同理，将生产每件产品II的设备台时和原材料的出租和出让的所有收入应不低于生产一件产品II的利润，这就有：第二章线性规划的对偶理论和灵敏度分析2y1+4y3≥3把所有的设备台时和资源出租和出让，其收入为：f=8y1+16y2+12y3从工厂的角度看，f当然是越大越好，但从接受者眼光看，f是越小越好，所以工厂决策者只可以在满足≥所有产品利润条件下，使其总收入尽可能的小。因此可以列出如下线性规划问题：第二章线性规划的对偶理论和灵敏度分析我们称这个问题为原问题的对偶问题。各模型中有关数据的“位置”示意图如下图所示。第二章线性规划的对偶理论和灵敏度分析3,2,1,034224..12168yfmin3121321iyyyyytsyyi第二章线性规划的对偶理论和灵敏度分析max23≤min8161212400481612140204232.3.2用矩阵形式表示线性规划的对偶问题从上一节得到的检验数的表达式是CN-CBB-1N与-CBB-1另外我们知道，当检验数CN-CBB-1N≤0(2-9)这表示线性规划问题已得到最优解，可见上面两式是得到最优解条件。由上一节我们知道：Y=CBB-1≥0称为单纯形子，第二章线性规划的对偶理论和灵敏度分析由于，CB-CBB-1B=0所以(CB,CN)-(CBB-1B，CBB-1N)=C-CBB-1(B,N)≤0包括基变量在内的所有检验数可以用C-CBB-1A≤0表示，因此可知：C-YA≤0移项后得到：YA≥C由于Y=CBB-1同乘于b得：Yb=CBB-1b=z第二章线性规划的对偶理论和灵敏度分析由于Y的上界为无穷大，所以只存在最小值。从而可以得到另一个线性规划问题：minf=YbYA≥cY≥0我们称它为原线性规划问题的对偶问题。从这