运筹学第3章详解.pptVIP

* 4.1 原问题与对偶问题的关系 例3 试求下述线性规划原问题的对偶问题 * 4.1 原问题与对偶问题的关系 由表2-4中原问题和对偶问题的对应关系，可以直接写出上述问题的对偶问题， * 4.2 对偶问题的基本性质 (1) 对称性：对偶问题的对偶是原问题 ; (2)弱对偶性：若X是原问题的可行解，Y是对偶问题的可行解。则存在CX≤Yb; (3) 无界性：若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解; (4) 可行解是最优解时的性质 ; (5) 对偶定理：若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等; (6) 互补松弛性 课堂练习 1．minZ=2x1+2x2+4x3 M I S 二、线性规划与目标规划 第2章 线性规划与单纯形法 第3章 对偶理论与灵敏度分析 第4章 运输问题 第5章 线性目标规划 * 对偶问题的提出 什么是对偶？ 对同一事物（或问题），从不同的角度（或立场）提出相对的两种不同的表述。 例如：在平面内，矩形的面积与其周长之间的关系，有两种不同的表述方法。 周长一定，面积最大的矩形是正方形。 面积一定，周长最短的矩形是正方形。 这种表述有利于加深对事物的认识和理解。 线性规划问题也有对偶关系。 * 对偶问题的提出 对第1章例1从对偶的角度进行表述。 假设该工厂的决策者决定不生产产品Ⅰ、Ⅱ，而将其所有资源出租或外售。这时工厂的决策者就要考虑给每种资源如何定价的问题。设用y1，y2，y3分别表示出租单位设备台时的租金和出让单位原材料A，B的附加额。他在做定价决策时，做如下比较：若用1个单位设备台时和4个单位原材料A可以生产一件产品Ⅰ，可获利2元，那么生产每件产品Ⅰ的设备台时和原材料出租或出让的所有收入应不低于生产一件产品Ⅰ的利润，这就有 y1+4y2≥2 * 对偶问题的提出 对第1章例1从对偶的角度进行表述。 同理将生产每件产品Ⅱ的设备台时和原材料出租或出让的所有收入应不低于生产一件产品Ⅱ的利润，这就有 2y1+4y3≥3 把工厂所有设备台时和资源都出租或出让，其收入为 w = 8y1+16y2+12y3 从工厂的决策者来看当然w愈大愈好；但受到接受方的制约，从接受者来看他的支付愈少愈好，所以工厂的决策者只能在满足大于等于所有产品的利润条件下，提出一个尽可能低的出租或出让价格，才能实现其原意，为此需解如下的线性规划问题： * 对偶问题的提出 称这个线性规划问题为例1线性规划问题(这里称为原问题)的对偶问题。这就是从另一角度提出的线性规划问题。 min w=8y1+16y2+12y3 y1+4y2 ≥2 2y1 +4y3≥3 yi≥0，i=1,2,3 (2-8) * 对偶问题的提出 对偶规划问题 * 线性规划的对偶理论 4.1 原问题与对偶问题的关系 4.2 对偶问题的基本性质 * 4.1 原问题与对偶问题的关系 原问题（LP）： * 4.1 原问题与对偶问题的关系 对偶问题(DP) 对偶问题的定义 一般线性规划问题的对偶问题 * 4.1 原问题与对偶问题的关系 标准型原问题与对偶问题的关系 * 4.1 原问题与对偶问题的关系 下列形式的变换关系为对称形式 原问题 （LP） 对偶问题(DP) * 4.1 原问题与对偶问题的关系 非对称形式的变换关系 原问题的约束条件中含有等式约束条件时，按以下步骤处理。 设等式约束条件的线性规划问题为 * 4.1 原问题与对偶问题的关系 非对称形式的变换关系 第一步：先将等式约束条件分解为两个不等式约束条件 * 4.1 原问题与对偶问题的关系 非对称形式的变换关系 第二步：按对称形式变换关系可写出它的对偶问题 设yi′是对应(2-13)式的对偶变量，yi″是对应(2-14)式的对偶变量，i=1,2,…，m * 4.1 原问题与对偶问题的关系 将上述规划问题的各式整理后得到 * 4.1 原问题与对偶问题的关系 综合上述，线性规划的原问题与对偶问题的关系克表示为： 或对偶问题 或原问题 M I S