对偶和灵敏分析.pptxVIP

第三章 内容提要;3.1 单纯形法的矩阵描述;设线性规划问题： Max z =CX AX= b X ? 0;设B是一个可行基，则可将系数矩阵(A, I)分为两块 (B, N)，N 是非基变量的系数矩阵。 对应于B的变量xB1, xB2,… , xBm 是基变量，用向量 XB=(xB1, xB2,… , xBm )T 表示 其它为非基变量，则;同时将 C 也分为两块(CB, CN)，则 ;这时可将(3.1), (3.2), (3.3)式改写为 Max z =CBXB+CNXN (3.4) BXB + NXN= b (3.5) XB? 0, XN ? 0 (3.6) 将(3.5)式移项后，得到 BXB = b - NXN (3.7) 给(3.7)式左乘B-1后，得到XB的表达式 XB = B-1 b - B-1 NXN (3.8) 将(3.8)式代入目标函数，得 z =CB B-1 b+(CN-CBB-1 N)XN (3.9); XB = B-1 b - B-1 NXN (3.8) z =CB B-1 b+(CN-CBB-1 N)XN (3.9) 令非基变量XN=0，得到一个基可行解 ; XB = B-1 b - B-1 NXN (3.8) z =CB B-1 b+(CN-CBB-1 N)XN (3.9) 从上式中可以看到： 非基变量 XN 的系数CN-CBB-1 N 就是检验数，即?N=CN-CBB-1 N 因为 XB 在式(2.9)中的系数是0，即CB-CBB-1 B=0 故包括基变量在内的所有检验数可用 C-CBB-1A≤0表示。 松驰变量检验数为-CBB-1，故所有检验数可用 C-CBB-1A和-CBB-1，即 C-YA和-Y 表示。;将式(3.8)和 (3.9)综合写成矩阵式如下： XB = B-1 b - B-1 NXN (3.8) z =CB B-1 b+(CN-CBB-1 N)XN (3.9);3.2 对偶问题的提出;某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表所示： ;其数学模型归结为： 目标函数 Max z= 2 x1+3 x2 约束条件 x1+2 x2?8 4 x1 ?16 s.t. 4 x2 ?12 x1, x2?0 ;设用 y1, y2, y3 分别表示出租单位设备台时的租金和出让单位原材料A, B的利润。 若用一个单位设备台时和4个单位原材料A可以生产一件产品I可获得2元，那么生产每件产品I的设备台时和原材料出租和出让的所有收入不应低于生产一件产品I的利润，即 y1+4y2≥2;同理，将每生产每件产品II的设备台时和材料出租和出让的所有收入不应低于生产一件产品II的利润，即 2y1+4y3≥3 把工厂所有设备台时和资源都出租或出让，其收入为 w=8y1+16y2+12y3 ;从工厂的决策者来看，当然 w 越大越好，但从接受者来看他的支付越少越好。因此决策者只能在满足所有产品利润的条件下，使其总收入尽可能地小。 即解如下线性规划问题 Min w=8y1+16y2+12y3 y1+4y2 ≥2 2y1 +4y3≥3 y1, y2 , y3 ≥0 这个问题即为原问题的对偶问题。 ;矩阵形式的对偶问题;3.3 线性规划的对偶理论;3.3.1 原问题与对偶问题的关系;例 写出下述线形规划问题的对偶问题 Max Z=5x1+4x2+6x3 x1+2x2 ≥2 x1 +x3≤3 -3x1+2x2+x3≤-5 x1- x2+x3＝1 x1≥0;x2≤0,;x3无约束;例 写出下述线形规划问题的对偶问题 minZ=2x1+3x2-5x3+x4 x1+x2-3x3+x4≥5 2x1 +2x3-x4≤4 x2+ x3+x4＝6 x1≤0,x2,x3≥0;x4无约束;写出下列问题的对偶问题：;;再