第三章线性规划的对偶理论.pptVIP

CBcj2060100000bx1x2x3x4x5x6x70x400-0.110.40-0.116860x201004004800x6000.5001012020x11010-4011320Cj00-100-1600-20z=55200XBXj模型maxZ=20x1+60x2+10x3x1,x2,x3≥0s.t.0.1x1≤3000.25x2≤1200.5x3≤120x1+x2+x3≤1800每月业务量X线：x1次；CT：x2次；磁共振：x3次。问题：（1）A医院从放射科收益的角度考虑，如何开展最优业务量？（2）在最优业务安排情况下，A医院如何利用影子价格进行决策？第59页，共117页，星期日，2025年，2月5日（1）该线性规划模型的最优解X*=（1320,480,0,168,0,120,0）T，最优值Z*=55200。则A医院从放射科收益的角度考虑，在每月X线平片检查和CT检查业务量各为1320人次和480人次，且不开展磁共振检查业务时，放射科利润最大，达55200元。（2）该对偶规划的最优解为Y*=(0,160,0,20)，即对应于原问题资源约束的影子价格。X线y1*=0，xs1=x4=168CT检查y2*=160，xs2=x5=0磁共振机y3*=0，xs3=x6=120放射科服务量y4*=20，xs4=x7=0。第60页，共117页，星期日，2025年，2月5日一、对偶单纯形法的基本思想设有标准型的线性规划模型MaxZ=CX，AX=b;X≥0，上一章讨论的单纯形法基本思想是从某一基本可行解出发，B-1b≥0,在初始单纯形表中，检验数C-CBB-1A≤0不一定成立，在保持B-1b≥0成立的条件下，经过逐步换基迭代，使检验数C-CBB-1A≤0成立，从而得到最优解或判断无最优解。如果求解线性规划时，是否可以这样来进行，某个初始基本解使得检验数C-CBB-1A≤0一定成立，B-1b≥0不成立，我们能否对约束等式和目标函数进行适当的行初等变换使条件C-CBB-1A≤0始终成立，直至B-1b≥0成立，从而求得最优解或判断无最优解。这就是对偶单纯形法的基本思想。对偶单纯形法的基本思想：求解一般的线性规划问题时，由满足C-CBB-1A≤0的对偶可行解出发，逐次换基迭代，但始终保持对偶可行性成立，也即C-CBB-1A≤0成立，直至B-1b≥0成立，从而求得最优解或判断无最优解。第三节对偶单纯形法第61页，共117页，星期日，2025年，2月5日1.将线性规划问题化为标准型；建立初始对偶单纯形表。检查b列的数字，若都有非负数，检验数均为非正，则已得到最优解，停止计算。若b列的数字中至少有一个负分量，且所有检验数保持非正，那么转入下一步。2.确定出基变量；取b列中最负的值对应的变量为出基变量。min{bi＜0}=bl，该行称为主元行。3.确定入基变量；在单纯形表中检查主元行的各系数，若所有alj’≥0，则原问题无可行解,停止计算;否则,若有alj’0则选?=min{?j’/alj’┃alj’0}=?k’/alk’那么,在换出变量那一行，用检验数除以同列具有负值的系数，取最小商数对应的变量为换入变量，相应列为主元列。如果换出变量那一行无负值的系数，则原问题无可行解。二、对偶单纯形法求解线性规划问题的一般步骤和过程：第62页，共117页，星期日，2025年，2月5日4.求出最优解或判断问题无解。当出基变量与入基变量选定后，则主元alk’也就确定，以alk’为转轴元,按原单纯形法在表中进行迭代运算，即作矩阵行变换，使其主元位置元素变为1,该列其他元素变为0,转1，重复计算，直至求出最优解或判断问题无解。如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。三、对偶单纯形法求解线性规划问题的一般