上海交通大学：《线性规划与非线性规划》教学资源_第2章 对偶理论和灵敏度分析 第3节 对偶问题的提出

第2章对偶理论和灵敏度分析 第3节对偶问题的提出

第2章 对偶理论和灵敏度分析 第3节 对偶问题的提出

第1章例1的不同表述 ·现从另一角度来讨论这个问题。 假设该工厂的决策者决定不生产产品I、 Ⅱ，而将其所有资源出租或外售。这时工厂 的决策者就要考虑给每种资源如何定价的问 题 设用y1,y2,y3分别表示出租单位设备台时的 租金和出让单位原材料A,B的附加额 ·他在做定价决策时，做如下比较：

第1章例1的不同表述 • 现从另一角度来讨论这个问题。 • 假设该工厂的决策者决定不生产产品Ⅰ、 Ⅱ，而将其所有资源出租或外售。这时工厂 的决策者就要考虑给每种资源如何定价的问 题 • 设用y1，y2，y3分别表示出租单位设备台时的 租金和出让单位原材料A，B的附加额 • 他在做定价决策时，做如下比较：

约束条件 若用1个单位设备台时和4个单位原材料A 可以生产一件产品I,可获利2元，那么 生产每件产品I的设备台时和原材料出 租或出让的所有收入应不低于生产一件 产品「的利润，这就有 y1+4y2≥2 同理将生产每件产品Ⅱ的设备台时和原 材料出租或出让的所有收入应不低于生 产一件产品Ⅱ的利润，这就有 2y1+4y3≥3

约束条件 • 若用 1个单位设备台时和 4个单位原材料 A 可以生产一件产品Ⅰ，可获利 2元，那么 生产每件产品Ⅰ的设备台时和原材料出 租或出让的所有收入应不低于生产一件 产品Ⅰ的利润，这就有 y 1+4y 2 ≥ 2 • 同理将生产每件产品Ⅱ的设备台时和原 材料出租或出让的所有收入应不低于生 产一件产品Ⅱ的利润，这就有 2y 1+4y 3 ≥ 3

目标函数 ·把工厂所有设备台时和资源都出租或出 让，其收入为 w=8y1+16y2+12y3

目标函数 • 把工厂所有设备台时和资源都出租或出 让，其收入为 ω=8y1+16y2+12y3

·从工厂的决策者来看当然ω愈大愈 好；但受到接受方的制约，从接受 者来看他的支付愈少愈好，所以工 厂的决策者只能在满足大于等于所 有产品的利润条件下，提出一个尽 可能低的出租或出让价格，才能实 现其原意，为此需解如下的线性规 划问题

• 从工厂的决策者来看当然ω愈大愈 好；但受到接受方的制约，从接受 者来看他的支付愈少愈好，所以工 厂的决策者只能在满足大于等于所 有产品的利润条件下，提出一个尽 可能低的出租或出让价格，才能实 现其原意，为此需解如下的线性规 划问题

称这个线性规划问题为例1线性规划 问题（这里称原问题）的对偶问题。 minw=8y1+16y2+12y3 y1+4y2 ≥2 2y1 +4y3≥3 y;≥0，i=1,2,3 (2-8) 这就是从另一角度提出的线性规划问题

称这个线性规划问题为例 1线性规划 问题 (这里称原问题 )的对偶问题。 min ω=8y 1+16y 2+12y 3 y 1+4y2 ≥2 2y1 +4y 3≥3 y i≥0，i=1,2,3 (2-8) 这就是从另一角度提出的线性规划问题

进一步讨论它们之间的关系 ·从第1节得到检验数的表达式是 CN-CBB-N与-CBB-I ·当检验数 CN-CBB-lN≤0 (2-9) -CBB-1≤0 (2-10 一表示线性规划问题已得到最优解。 一也作为得到最优解的判断条件

进一步讨论它们之间的关系 •从第 1节得到检验数的表达式是 C N-C B B-1 N 与-C B B-1 •当检验数 C N-C B B-1 N ≤0 (2-9) -C B B-1 ≤0 (2-10) –表示线性规划问题已得到最优解。 –也作为得到最优解的判断条件

现在讨论这两个条件。 (1)(2-9)式，(2-10)式中都有乘子 CBB1,称它为单纯形乘子，用 符号Y=CBBl表示。 ·由(2-10)式，可得到Y≥0

现在讨论这两个条件。 (1) (2-9)式，(2-10)式中都有乘子 C B B-1，称它为单纯形乘子，用 符号Y= C B B-1表示。 • 由(2-10)式，可得到 Y ≥ 0

(2)对应基变量X,的检验数是0。 ·它是CR-CRB-B=0。包括基变量在内的所 有检验数可用C-CBA≤0表示。 ·从此可得C-C.BA=C-YA≤0 移项后，得到YA≥C

(2) 对应基变量 X B的检验数是 0 。 • 它是 C B- C B B-1B=0。包括基变量在内的所 有检验数可用C- C B B-1 A ≤ 0表示。 • 从此可得C-C B B-1A=C-YA ≤ 0 移项后，得到YA ≥ C

(3)Y由(2-10)式，得到 -Y=-CpB-1 (2-11) ·将(2-11)式两边右乘b,得到 -Yb=-CpB-b (2-12) Yb=CRB-b-z ·因Y的上界为无限大，所以只存在最小值

(3) Y由(2-10)式，得到 -Y= - CBB-1 (2-11) • 将(2-11)式两边右乘b，得到 -Yb=- CBB-1b (2-12) Yb= CBB-1b=z • 因Y的上界为无限大，所以只存在最小值