教案6-对偶理论改

1、 设B为A中的一个mm可行基，则可将A分为（B，N），同样，将X分为（XB，XN）T，C亦分为（CB，CN），原模型Max Z= CBXB+CNXN+0XS (2.1) BXB+NXN+IXS=b (2.2) XB,XN,XS0 (2.3)XB=B-1 b B-1 NXN B-1 XS 代入（2.1）式，有 Z=CB（ B-1 b B-1 NXN B-1 XS）+CNXN+0XS = CB B-1 b+ （CNCB B-1 N）XN CB B-1 XS1Z=CB（ B-1 b B-1 NXN B-1 XS）+CNXN+0XS = CB B-1 b+ （CNCB B-1 N）XN CB B-1

2、XS即方程组为：-Z+(CCBB-1A)XCBB-1XS=CBB-1b B-1AX+B-1XS=B-1 b -Z X B XN XS 右端此方程组的系数增广矩阵为：2单纯形表的矩阵形式3如例1 的初始表和第三张表42 改进单纯形法单纯形法中，除换入变量外，非基变量系数列的迭代运算是多余的。为了减少计算量和存储量，产生了改进单纯形法。当mn时这种改进的效果明显。5实际问题： 某养鸡所用的混合饲料由A、B、C三种配料组成，下表给出了1单位各种配料所含的营养成分、单位成本以及1份饲料必须含有的各种成份。问如何配制混合饲料使成本最小？设:Xj=混合饲料中第j种配料的含量，j=A、B、CMin Z=6X

3、A+3XB+2XCXA+XB+XC 201/2XA+1/2XB+1/4XC 62XA+XB+XC 10Xj 06 有一个饲料厂，制造含有这3种营养成份各1单位的营养丸，知道养鸡场对混合饲料的要求，因此，在制定营养丸的价格时，使每丸D、E、F营养丸的价格分别为q1、q2、q3。养鸡场采购1单位配料A,相当于对3种营养丸分别采购1、1/2、2丸等，采购1单位的B,1单位的C, 因此饲料厂定营养丸售价时，必须有：q1+1/2q2+2q3 6q1+1/2q2+q3 3q1+1/4q2+q3 2Max Z=20q1+6q2+10q37设出租单位设备台时的租金y1 ，转让原材料A、B的收费为y2， y3。

4、第一章例1 生产组织问题 Max Z =2x1+3x2 x1+2x28 4x1 16 4x2 12 x1，x20若工厂决策者准备将所 有资源出租或转让，问应如何定价？ 设备原材Ay1y2原材By38对偶问题的定义标准型为：9互为转置列向量行向量n个变量n个约束10211证：AX=b AXbAXbAXb-AX-byy12解：设对偶变量为y1,y2,y3,对偶问题模型为：Max w=5y1+4y2+6y3 y1 +2y2 y1 + y3 -3y1 +2y2 +y3 y1 - y2 +y323-5=1y10, y20, y3无约束134.2 对偶问题的基本性质14注意：(D)无可行解，(P)不一定为

5、无界解。 此性质还说明：(P)有可行解，(D)不一定有可行解。4、可行解是最优解时的性质 设 是(P)的可行解， 是(D)的可行解，当 时， 是最优解。3、无界性 若（P）问题可行，但目标函数无界，则（D）问题不可行。（D）不可行（P）无界 （P）不可行利用弱对偶定理 5、对偶定理 若（P）有最优解，则（D）也有最优解，且目标函数最优值相等。15例1 已知线性规划问题 试用对偶理论证明上述问题无最优解。无界性定理。（P）可行，但无界 则（D）不可行。（D）不可行（P）无界（P）不可行对偶问题X（0）=（0，0，0）T是原问题的一个可行解对偶问题不可行166、互补松弛定理 设X*和Y*分别(P）

6、问题(D）问题的可行解，则它们分别是最优解的充要条件是Y*（b-AX*)=0 (Y*A-C)X*=0如何应用该定理？AX* bAX*+XS*= bb-AX*=XS*Y*（b-AX*)=0Y*XS*=017对偶变量不为0，原问题相应约束式是等式原问题约束为不等式，相应对偶变量为0最优解点18检验数行19cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 4 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0-14 0 0 -1.5 -1/8 0 x1x5x2203205 对偶问题的经济解释 影子价格 (P)的最终单纯形表中松弛变量的检验数对应(D)的

7、最优解。 当某约束条件的右端常数增加一个单位时（假设原问题的最优基不变），原问题的目标函数最优值增加的数量。Z*=CX*=Y*b =(y1*,y2*, ,ym*)b1b2bm=y1*b1+y2*b2+ym*bm当某个右端常数bi bi+1时bi+1yi*+yi*(bi+1)=Y*b+yi*=Z*+yi*第I种资源的影子价格是第i个约束条件的右端常数增加一个单位时，目标函数增加的数量21 X(3)=(4，2，0，0, 4)T， z3 =14经济意义：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。影子价格22X*=(30,35,0,50,0)T, Z*=135y1*=3/4y

8、2*=0,y3*=1/4影子价格经济意义：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。23影子价格的意义(1)影子价格客观地反映资源在系统内的稀缺程度。如果某一资源在系统内供大于求（即有剩余），其影子价格就为零。如果某一资源是稀缺的（即相应约束条件的剩余变量为零）,则其影子价格必然大零。影子价格越高，资源在系统中越稀缺。(2)影子价格是对系统资源的一种优化估价，只有当系统达到最优时才能赋予该资源这种价值，因此也称最优价格。(3)影子价格的取值与系统状态有关。系统内部资源数量、技术系数和价格的任何变化，都会引起影子价格的变化，它是一种动态价格。(4)如果考虑扩大生产能力，

9、应该从影子价格高的设备入手。246 对偶单纯形法保持对偶可行性，逐步改进主可行性，求解主问题。 当b有负分量，A中有一明显初始对偶可行基(检验数均非正)，因而易得一初始解时，可用对偶单纯形法求解。 设B为一个基基本解X（0）为基本可行解的条件？B-1b0X（0）为最优解的条件？原原始可行性条件原始最优性条件令Y=CBB-1，代入原始最优性条件，YAC对偶可行性条件25例 用对偶单纯形法求解单纯形法大M 法剩余变量、人工变量 用（-1）乘不等式两边，再引入松弛变量。26先选出基变量后选进基变量原问题，符合原始最优性条件，但不可行27最优解X*=（7，0，4，0）TZ*=-728例6 用对偶单纯形法求解（P）291 - 4/3 - -1 0 -5/2 1/2 1 -1/2 2 1 -1/2 3/2 0 -1/2 0 -4 -1 0 -1- 8/5 - - 22/5 0 1 -1/5 -2/5 1/5 11/5 1 0 7/5