教案对偶理论

设B为A中的一个m×m可行基，则可将A分为（B，N），同样，将X分为（XB，XN）T，C亦分为（CB，CN），原模型maxz=CBXB+CNXN+0XS(2.1)BXB+NXN+IXS=b(2.2)XB，XN，XS≥0(2.3)XB=B-1b－B-1NXN－B-1XS

代入（2.1）式，有Z=CB（B-1b－B-1NXN－B-1XS）+CNXN+0XS

=CBB-1b+（CN－CBB-1N）XN－CBB-1XSZ=CB（B-1b－B-1NXN－B-1XS）+CNXN+0XS

=CBB-1b+（CN－CBB-1N）XN－CBB-1XS

-ZXBXNXS右端此方程组的系数增广矩阵为：此方程组的系数增广矩阵亦为：基变量非基变量XBXNXSI0B-1NCN-CBB-1NB-1-CBB-1B-1b-CBB-1b单纯形表的矩阵形式如例1的初始表和第三张表§2改进单纯形法单纯形法中，除换入变量外，非基变量系数列的迭代运算是多余的。为了减少计算量和存储量，产生了改进单纯形法。当m<<n时这种改进的效果明显。实际问题：某养鸡所用的混合饲料由A、B、C三种配料组成，下表给出了1单位各种配料所含的营养成分、单位成本以及1份饲料必须含有的各种成份。问如何配制混合饲料使成本最小？

营养成分DEF单位成本ABC111½½¼2116321份饲料应含量20610设:Xj=混合饲料中第j种配料的含量，j=A、B、CMinZ=6XA+3XB+2XCXA+XB+XC³201/2XA+1/2XB+1/4XC³62XA+XB+XC³10Xj³0

有一个饲料厂，制造含有这3种营养成份各1单位的营养丸，知道养鸡场对混合饲料的要求，因此，在制定营养丸的价格时，使每丸D、E、F营养丸的价格分别为q1、q2、q3。养鸡场采购1单位配料A,相当于对3种营养丸分别采购1、1/2、2丸等，采购1单位的B,相当于对3种营养丸分别采购1、1/2、1丸等，采购1单位的C,相当于对3种营养丸分别采购1、1/4、1丸等，

因此饲料厂定营养丸售价时，必须有：q1+1/2q2+2q3

£6q1+1/2q2+q3

£3q1+1/4q2+q3

£2MaxZ=20q1+6q2+10q3设出租单位设备台时的租金y1，转让原材料A、B的收费为y2，y3。第一章例1生产组织问题

MaxZ=2x1+3x2

x1+2x2≤84x1≤164x2≤12x1，x2≥0若工厂决策者准备将所有资源出租或转让，问应如何定价？设备原材Ay1y2原材By3

甲乙可用量机械设备128原材料A4016原材料B0412对偶问题的定义标准型为：列向量行向量n个变量n个约束

证：AX=bAX≤bAX≥bAX≤b-AX≤-by′y〃解：设对偶变量为y1,y2,y3,对偶问题模型为：Maxw=5y1+4y2+6y3y1+2y2y1+y3-3y1+2y2+y3y1-y2+y3≥2≤3≤-5=1y1≥0,y2≤0,y3无约束4.2对偶问题的基本性质注意：(D)无可行解，(P)不一定为无界解。此性质还说明：(P)有可行解，(D)不一定有可行解。4、

可行解是最优解时的性质

设是(P)的可行解，是(D)的可行解，当时，是最优解。3、无界性

若（P）问题可行，但目标函数无界，则（D）问题不可行。（D）不可行（P）无界（P）不可行利用弱对偶定理5、对偶定理若（P）有最优解，则（D）也有最优解，且目标函数最优值相等。例1已知线性规划问题

试用对偶理论证明上述问题无最优解。无界性定理。（P）可行，但无界则（D）不可行。（D）不可行（P）无界（P）不可行对偶问题X（0）=（0，0，0）T是原问题的一个可行解对偶问题不可行6、互补松弛定理

设X*和Y*分别(P）问题(D）问题的可行解，则它们分别是最优解的充要条件是Y*（b-AX*)=0(Y*A-C)X*=0如何应用该定理？AX*≤bAX*+XS*=bb-AX*=XS*Y*（b-AX*)=0Y*XS*=0对偶变量不为0，原问题相应约束式是等式原问题约束为不等式，相应对偶变量为0最优解点检验数行cj

CBXBbx1x2x3x4x5

-z

23000

4

1

00

1/40

4

0

0-2

1/21

2

0

11/2

-1/8

0-1400-1.5-1/8

0x1x5x2203§5对偶问题的经济解释—

影子价格

(P)的最终单纯形表中松弛变量的检验数对应(D)的最优解。

当某约束条件的右端常数增加一个单位时（假设原问题的最优基不变），原问题的目标函数最优值增加的数量。Z*=CX*=Y*b=(y1*,y2*,…,ym*)b1b2﹕﹒bm=y1*b1+y2*b2+…+ym*bm当某个右端常数bibi+1时bi+1yi*+yi*(bi+1)=Y*b+yi*=Z*+yi*第I种资源的影子价格是第i个约束条件的右端常数增加一个单位时，目标函数增加的数量

甲乙可用量机械设备128原材料A4016原材料B0412

X(3)=(4，2，0，0,4)T，z3=14cj23000CBXBbx1x2x3x4x5203x1x5x2442100001-2½-3/2½-1/81/8010-1400-3/2-1/80经济意义：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。影子价格

产品资源ⅠⅡ现有资源数钢材12100（吨）煤22180（吨）机时16240（小时）利润（万元）13x1x2x3x4x5-zXB-13500-3/40-1/4x130103/20-1/2x45000-5/211/2x23501-1/401/4X*=(30,35,0,50,0)T,Z*=135y1*=1/4y2*=0,y3*=1/4影子价格经济意义：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。影子价格的意义(1)影子价格客观地反映资源在系统内的稀缺程度。如果某一资源在系统内供大于求（即有剩余），其影子价格就为零。如果某一资源是稀缺的（即相应约束条件的剩余变量为零）,则其影子价格必然大零。影子价格越高，资源在系统中越稀缺。(2)影子价格是对系统资源的一种优化估价，只有当系统达到最优时才能赋予该资源这种价值，因此也称最优价格。(3)影子价格的取值与系统状态有关。系统内部资源数量、技术系数和价格的任何变化，都会引起影子价格的变化，它是一种动态价格。(4)如果考虑扩大生产能力，应该从影子价格高的设备入手。§6对偶单纯形法保持对偶可行性，逐步改进主可行性，求解主问题。

当b有负分量，A中有一明显初始对偶可行基(检验数均非正)，因而易得一初始解时，可用对偶单纯形法求解。

设B为一个基基本解X（0）为基本可行解的条件？B-1b≥0X（0）为最优解的条件？原原始可行性条件原始最优性条件令Y=CBB-1，代入原始最优性条件，→YA≥C对偶可行性条件例用对偶单纯形法求解单纯形法大M法剩余变量、人工变量

用（-1）乘不等式两边，再引入松弛变量。cj

-1-40-300CBXBbx1

x2x3x4x5x600x5x6-3-2-1-21-11021-4-1010-1-40-300先选出基变量后选进基变量原问题，符合原始最优性条件，但不可行cj

-1-40-300CBXBbx1

x2x3x4x5x6-10x1x63-812-11-100-3-2-32130-2-1-2-10cj

-1-40-300CBXBbx1

x2x3x4x5x6-10x1x63-812-11-100-3-2-32130-2-1-2-10-10x1x37417/205/2-2-1/203/213/2-1-1/270-1/20-1/2-2