运筹学 第三章 线性规划的对偶理论.pdf

第三章线性规划的对偶理论 第三章线性规划的对偶理论 内容提要 内容提要 §3.1 线性规划的对偶问题 §3.2 线性规划的对偶理论 §3.3 对偶解的经济解释 §3.4 对偶单纯形方法 §3.5 灵敏度分析 §3.1 线性规划的对偶问题 §3.1 线性规划的对偶问题 1. 对偶问题的提出 2. 如何将原问题转化为对偶问题 3. 原问题与对偶问题的对应关系 1. 对偶问题的提出 例 3.1 例 3.1 某工厂拥有A 、B、C三种类型的原料，生 产甲、乙两种产品。每件产品在生产中消耗 的原料数量，每件产品的价格以及三种原料 可利用的数量如下表所示： 产品 原料数量 甲 乙 原料 （吨） A 1 1 300 B 2 1 400 C 0 2 250 价格（元/件） 50 100 问题：工厂应如何安排生产可获得最大的总 收益？ 解：设变量x 为第i种（甲、乙）产品的生产 解： i 件数（i ＝1，2 ）。则有 目标函数 Max z = 50x1 + 100x2 s.t. x + x ≤300 1 2 2x + x ≤ 400 1 2 x2 ≤ 250 x ,x ,x ,x ,x ≥ 0 1 2 3 4 5 现在考虑 若三种原料都用于转让，试问：三种原料各 如何收费才能即保证本厂的利益，有能最有 竞争力？ 设 y ，y ，y 分别为每设备工时（或 1 2 3 原料）每单位的收取费用，则有 Min f = 300y + 400y + 250y 1 2 3 s.t.y +2y ≥ 50 （不少于甲产品的利润） 1 2 y + y +y ≥100 （不少于乙产品的利润） 1 2 3 y ,y ,y ≥ 0 1 2 3 型 模 的 偶 对 为 互 型 型 对 模 模 者 者 一 理 理 管 管 Max z = 50x + 100x 1 2 题 题 问 问 原 原 s.t. x + x ≤300