文档介绍：线性规划 Linear Programming
Ludong University
2018/12/3
Ludong University
2
线性规划
线性规划问题
可行区域与基本可行解
单纯形算法
初始可行解
对偶理论
灵敏度分析
计算软件
案例分析
对偶问题的提出
对偶规划
对偶理论
对偶单纯形算法
2018/12/3
Ludong University
3
线性规划的对偶理论
这里的对偶是指对同一事物(问题)从不同的角度(立场)观察,有两种对立的表述。如“平面中矩形的面积与周长的关系。”
,面积最大的矩形是正方形;
,周长最短的矩形是正方形。
本节所讨论的对偶理论是线性规划理论中一个重要而又有趣的概念。对偶理论告诉我们:对于每个一个线性规划(P),总存在另一个线性规划(D),两者之间存在着密切的联系,甚至人们常常通过求解对偶问题(D)来获得原规划(P)的最优解。
2018/12/3
Ludong University
4
对偶问题的提出
引例美佳公司计划制造两种产品。已知各制造一件时分别占用的设备A、B的台时、调试工序时间、,试制订总利润最大的生产计划。
项目
产品Ⅰ
产品Ⅱ
每天可用能力
设备A(h)
0
5
15
设备B(h)
6
2
24
调试工序(h)
1
1
5
利润(元)
2
1
模型LP1
2018/12/3
Ludong University
5
对偶问题的提出
假设有某个公司想把美佳公司的资源收买过来,它至少应付出多大的代价,才能使美佳公司愿意放弃生产,出让自己的资源。显然美佳公司出让自己资源的条件是:出让代价应不低于用同等数量资源由自己组织生产时获得的利润。
项目
产品Ⅰ
产品Ⅱ
每天可用能力
设备A(h)
0
5
15
设备B(h)
6
2
24
调试工序(h)
1
1
5
利润(元)
2
1
现在从另外一个角度提出上述问题
2018/12/3
Ludong University
6
对偶问题的提出
可控因素:
受制条件:
目标:
蕴含约束:
2018/12/3
Ludong University
7
对偶问题的提出?
模型LP2
模型LP1
上述LP1和LP2两个线性规划问题,通常称LP1为原问题,LP2是LP1者的对偶问题。
?
2018/12/3
Ludong University
8
对偶规划
标准形式线性规划的对偶规划
规范形式线性规划的对偶规划
一般形式线性规划的对偶规划
实例
2018/12/3
Ludong University
9
标准形式LP的对偶规划
2018/12/3
Ludong University
10
标准形式LP的对偶规划
(Ⅱ)
反之亦然。