资源描述：
《运筹学 第三章 对偶单纯形法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、运筹帷幄之中决胜千里之外对偶理论与灵敏度分析第二章对偶理论与灵敏度分析第一节 对偶问题的提出第二节 线性规划的对偶理论第三节 对偶问题的经济解释第四节 对偶单纯形法【例2-1】某家电厂利用现有资源生产两种产品，有关数据如下表：设备A设备B调试工序利润（元）0612521115时24时5时产品Ⅰ产品ⅡD第一节对偶问题的提出如何安排生产，使获利最多？厂家设Ⅰ产量––––Ⅱ产量––––设：设备A——元／时设备B––––元／时调试工序––––元／时承租付出的代价最小，且对方能接受。出让代价应不低于用同等数量的资源自己生产的利润。设备A
2、设备B调试工序利润（元）0612521115时24时5时ⅠⅡD厂家能接受的条件：出让代价应不低于用同等数量的资源自己生产的利润。收购方的意愿：厂家对偶问题原问题承租厂家一对对偶问题第二节线性规划的对偶理论一﹑原问题与对偶问题的关系二﹑对偶问题的基本性质一﹑原问题与对偶问题的关系1﹒对称式的对偶“≤”不等式约束条件的原问题与“≥”不等式约束条件的对偶问题，称为对称式的一对对偶问题。原问题：maxz=c1x1+c2x2+…+cnxna11a12…a1nam1am2…amn·········x1xn···b1bm···≤x1，x2，
3、…，xn≥0对偶问题：minω=b1y1+b2y2+…+bmyma11a12…a1nam1am2…amn·········≥y1，y2，…，ym≥0(y1,y2,…,ym)(c1,c2,…,cn)maxz=CXAX≤bX≥0minω=YbYA≥CY≥0n个变量，m个约束条件m个变量，n个约束条件2﹒约束条件全部为“=”的对偶maxz=CXAX＝bX≥0原问题：maxz=CXAX≤bX≥0AX≥b等价maxz=CXAX≤bX≥0－AX≤－bmaxz=CXX≥0A－AX≤b－bminω=(Y1,Y2)Y1,Y2≥0A－A≥Cb－b
4、(Y1,Y2)其中Y1=(y1,y2,…ym)，Y2=(ym+1,ym+2,…y2m)等价等价minω=YbY为无约束YA≥Cminω=(Y1－Y2)bY1,Y2≥0(Y1－Y2)A≥C令Y=(Y1－Y2)对偶问题对偶问题3﹒约束条件为“≥”的对偶maxz=CXAX≥bX≥0原问题：maxz=CX－AX≤－bX≥0minω=Y1(－b)Y1(－A)≥CY1≥0minω=YbYA≥CY≤0等价对偶问题令Y=－Y1对偶问题4﹒变量≤0的对偶maxz=CXAX≤bX≤0原问题：令X=－X1maxz=C(－X1)A(－X1)≤bX1≥
5、0maxz=(－C)X1(－A)X1≤bX1≥0等价minω=YbY(－A)≥－CY≥0minω=YbYA≤CY≥0对偶问题对偶问题等价5﹒变量无约束的对偶maxz=CXAX≤bX无约束原问题：令X=X1－X2X1，X2≥0maxz=CX1－CX2X1,X2≥0AX1－AX2≤bmaxz=(C,－C)X1,X2≥0≤bX1X2(A,－A)X1X2等价minω=YbY≥0Y(A,－A)≥(C,－C)对偶minω=YbYA≥CY≥0－YA≥－Cminω=YbYA＝CY≥0minω=YbYA≥CY≥0YA≤C等价等价等价对偶问题6﹒
6、原问题与对偶问题的关系表原问题（或对偶问题）对偶问题（或原问题）目标函数maxzn个变量变量≥0变量≤0变量无约束目标函数minωn个约束条件约束≥约束≤约束=m个约束条件约束≥约束≤约束=约束条件右端项目标函数变量系数m个变量变量≤0变量≥0变量无约束目标函数变量系数约束条件右端项【例2-2】试求下述线性规划问题的对偶问题（P）与(D)的关系对应表：原(对偶)问题对偶(原)问题目标函数max目标函数min目标函数系数约束方程常数列约束方程常数列目标函数系数变量个数n约束方程个数n约束方程个数m变量个数m约束方程≤变量≥0≥≤
7、0=无符号约束变量≥0约束方程≥≤0≤无符号约束=系数矩阵A解：（P）与(D)的关系对应表：原(对偶)问题对偶(原)问题目标函数max目标函数min目标函数系数约束方程常数列约束方程常数列目标函数系数变量个数n约束方程个数n约束方程个数m变量个数m约束方程≤变量≥0≥≤0=无符号约束变量≥0约束方程≥≤0≤无符号约束=系数矩阵A【例2-3】试求下述线性规划原问题的对偶问题解：原问题的对偶问题【课堂练习】（P）与(D)的关系对应表：原问题对偶问题目标函数max目标函数min目标函数系数约束方程常数列约束方程常数列目标函数系数变量
8、个数n约束方程个数n约束方程个数m变量个数m约束方程≤变量≥0≥≤0=无符号约束变量≥0约束方程≥≤0≤无符号约束=系数矩阵A构建对偶问题的规则原始问题的目标对偶问题目标约束类型变量符号最大化极小化>=无限制最小化极大化<=无限制要求：1、将所有约束转换成等式；2、将所有决策
