北京交通大学运筹学教案对偶理论.pptVIP

影子价格的意义 (1)影子价格客观地反映资源在系统内的稀缺程度。 如果某一资源在系统内供大于求（即有剩余），其影子价格就为零。如果某一资源是稀缺的（即相应约束条件的剩余变量为零）,则其影子价格必然大零。影子价格越高，资源在系统中越稀缺。 (2)影子价格是对系统资源的一种优化估价，只有当系统达到最优时才能赋予该资源这种价值，因此也称最优价格。 (3)影子价格的取值与系统状态有关。系统内部资源数量、技术系数和价格的任何变化，都会引起影子价格的变化，它是一种动态价格。 (4)如果考虑扩大生产能力，应该从影子价格高的设备入手。 * 设B为A中的一个m×m可行基，则可将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,XS≥0 (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+ （CN－CB B-1 N）XN－ CB B-1 XS Z=CB（ B-1 b－ B-1 NXN－ B-1 XS）+CNXN+0XS = CB B-1 b+ （CN－CB B-1 N）XN－ CB B-1 XS 即方程组为：-Z+(C－CBB-1A)X－CBB-1XS=CBB-1b B-1AX+B-1XS=B-1 b -Z X B XN XS 右端 此方程组的系数增广矩阵为： B-1b -CBB-1b B-1 -CBB-1 B-1 N CN-CBB-1N I 0 XS XN XB 非基变量 基变量 单纯形表的矩阵形式 如例1 的初始表和第三张表 2 改进单纯形法 单纯形法中，除换入变量外，非基变量系数列的 迭代运算是多余的。为了减少计算量和存储量，产生 了改进单纯形法。当 m n 时这种改进的效果明显。 ?实际问题： 某养鸡所用的混合饲料由A、B、C三种配料组成，下表给出了1单位各种配料所含的营养成分、单位成本以及1份饲料必须含有的各种成份。问如何配制混合饲料使成本最小？ 10 6 20 1份饲料应含量 6 3 2 2 1 1 ? ? ? 1 1 1 A B C 单位成本 F E D 营养成分 设:Xj=混合饲料中第j种配料的含量，j=A、B、C Min Z=6XA+3XB+2XC XA+XB+XC 320 1/2XA+1/2XB+1/4XC 36 2XA+XB+XC 310 Xj 30 有一个饲料厂，制造含有这3种营养成份各1单位的营养丸，知道养鸡场对混合饲料的要求，因此，在制定营养丸的价格时，使每丸D、E、F营养丸的价格分别为q1、q2、q3。养鸡场采购1单位配料A,相当于对3种营养丸分别采购1、1/2、2丸等，采购1单位的B,…,1单位的C, 因此饲料厂定营养丸售价时，必须有： q1+1/2q2+2q3 ￡6 q1+1/2q2+q3 ￡3 q1+1/4q2+q3 ￡2 Max Z=20q1+6q2+10q3 设出租单位设备台时的租金y1 ，转让原材料A、B的收费为y2， y3。 第一章例1 生产组织问题 Max Z =2x1+3x2 x1+2x2≤8 4x1 ≤16 4x2 ≤12 x1，x2≥0 若工厂决策者准备将所 有资源出租或转让，问应如何定价？ 设备 原材A y1 y2 原材B y3 12 0 4 原材料B 16 4 0 原材料A 8 1 2 机械设备 可用量 甲 乙 ?对偶问题的定义 标准型为： 互为转置 列向量 行向量 n个变量 n个约束 ≤ 2 ≥ 证：AX=b AX≤b AX≥b AX≤b -AX≤-b y′ y〃 解：设对偶变量为y1,y2,y3,对偶问题模型为： Max w=5y1+4y2+6y3 y1 +2y2 y1