运筹学概论第章线性规划的对偶理论(“问题”相关文档)共38张.pptxVIP

第二章线性规划的对偶实际;第一节线性规划的对偶问题;例1美佳公司方案制造甲、乙两种家电产品，知制造一件甲需占用B设备5小时，调试工序1小时；制造一件乙需占用A设备6小时，B设备2小时，调试工序1小时；A设备每天可用15小时，B设备可用24小时，调试工序每天可用5小时。知售出一件甲获利2元，售出一件乙获利1元，问该公司每天应制造两种家电各多少件，使获取的利润最大？;;●任何线性规划问题都有其对偶问题

●对偶问题有其明显的经济含义;●设A、B资源的出卖价钱分别为y1和y2

●显然商人希望总的收买价越小越好(目的)

●工厂希望出卖资源后所得不应比消费产品所得少〔约束〕;;那么xj*(j=1,…n)是原问题的最优解，yi*(i=1,…m)是其对偶问题的最优解。

B-1NB-1

y1y2y3

资源的市场价钱是知数，相对比较稳定，而它的影子价钱那么有赖于资源的利用情况，是未知数。

01/4－1/2

假设原问题和对偶问题都有可行解，那么它们都有最优解，且它们的最优解的目的函数值相等。

〔2〕初始单纯形表中基变量Xs=b，迭代后的表中XB=B-1b

00

假设xj*(j=1,2…n)是原问题(max)的可行解，yi*(i=1,2…m)是对偶问题(min)的可行解，那么恒有

y4y5

●显然商人希望总的收买价越小越好(目的)

资源的影子价钱实践上是一种时机本钱。

x3x4x5

0－1/43/2

0-1/4-1/2

知售出一件甲获利2元，售出一件乙获利1元，问该公司每天应制造两种家电各多少件，使获取的利润最大？;课堂练习：;三、非对称方式的原-对偶问题关系;;;;解：设对偶变量为y1,y2,y3,对偶问题模型为：

Maxw=5y1+4y2+6y3

y1+2y2

y1+y3

-3y1+2y2+y3

y1-y2+y3;;第二章线性规划的对偶实际;第二节对偶问题的根本性质;原线性规划问题的矩阵表达式加上松弛变量后为：;Cj?;;当迭代后基变量为XB时，其在初始单纯形表中的系数矩阵为B，那么有：

〔1〕对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1

〔2〕初始单纯形表中基变量Xs=b，迭代后的表中XB=B-1b

〔3〕初始单纯形表中约束系数矩阵为，迭代后的表中约束系数矩阵为(B-1左乘):;〔5〕当B为最优基时，应有:;例1两个互为对偶的线性规划问题，两者分别加上松弛和剩余变量后为：;两个问题的最终单纯形表见下页：;二、原规划与对偶规划问题的变量及解之间的对应关系;三、线性规划的对偶定理;弱对偶定理推论:;2.最优性〔最优解判别定理〕;3.强对偶性〔对偶定理〕;例1两个互为对偶的线性规划问题，两者分别加上松弛和剩余变量后为：

●假设原问题〔对偶问题〕为无界解，那么其对偶问题〔原问题〕无可行解。

y4y5

又因单纯形法的迭代是对约束增广矩阵进展的行的初等变换，对应XS的系数矩阵在新表中应为B-1。

min问题的任何可行解目的函数值是其对偶max问标题的函数值的上限。

x1x2

00

0－1/43/2

最优性〔最优解判别定理〕

资源的市场价钱是知数，相对比较稳定，而它的影子价钱那么有赖于资源的利用情况，是未知数。

－1/41/4

〔2〕初始单纯形表中基变量Xs=b，迭代后的表中XB=B-1b

01/4－1/2

x3x4x5

●工厂希望出卖资源后所得不应比消费产品所得少〔约束〕;第二章线性规划的对偶实际;例1美佳公司方案制造甲、乙两种家电产品，知制造一件甲需占用B设备5小时，调试工序1小时；制造一件乙需占用A设备6小时，B设备2小时，调试工序1小时；A设备每天可用15小时，B设备可用24小时，调试工序每天可用5小时。知售出一件甲获利2元，