教案五线性规划的对偶问题.docxVIP

教案五线性规划的对偶问题

教学内容第四节线性规划的对偶问题

1.线性规划的对偶问题

2.对偶单纯形法

3.线性规划的灵敏度分析

4.线性规划在卫生管理中的应用

教学学时7学时

教学目标1.理解对偶问题的基本概念

2.掌握对偶单纯形法

3.掌握线性规划的灵敏度分析

4.掌握线性规划在卫生管理中的应用

重点难点重点是对偶问题的基本概念、对偶单纯形法线、灵敏度分析、线性规划在卫生管理中的应用。难点是对偶问题的基本概念和线性规

划的灵敏度分析

教学手段教师与学生互动使用多媒体课件

教学过程

一、复习巩固

1.单纯形法的基本原理(见课件)

2.单纯形解法(见课件)

3.大M法(见课件)

二、讲授新课

1.线性规划的对偶问题

(1)对偶问题的基本概念(见课件)

对偶现象每一个线性规划都伴随着另一个线性规划，两者有密切关系，

互为对偶.其中一个问题称为原问题，另一个问题称为其对偶问题.两者间只要

得到其中一个问题的解，那么也就得到了另一个问题的解.

下面通过一个实例来解释对偶线性规划的概念.

例2-12以例2-1为例，我们讨论了一个制药厂的生产计划的数学模型及

其解法.

现在假定该制药厂决定在计划期内不生产药品I、Ⅱ,而将生产设备的有效台时全部租给某公司，那么该公司应对设备A、B、C、D每小时付多少租金，

才能使成本最小，而又能为制药厂所接受?

从租用设备的公司的角度考虑，一是所付的租金越低越好；二是所付的租金总额能使制药厂接受，即租金应不低于制药厂自己生产该两种药品所得利润，

否则，制药厂宁可自己生产，而不租给公司.

设公司租用该制药厂A、B、C、D四种设备的租金(元/小时)分别为y,、

y?、y,和y?.在考虑租用设备的定价时，能使该制药厂接受的条件是：

公司租用该制药厂用以生产每千克药品I所需A、B、C、D四种设备的台

时的租金不应少于200元，即

2y?+y?+4y?+0y?≥200

同样，公司租用该制药厂用以生产每千克药品Ⅱ所需A、B、C、D四种设

备的台时的租金不应少于300元，即

2y?+2y?+0y?+4y?≥300

公司在考虑自身利益时，其目标是使付出的租金总额为最小，即

MinW=12y?+8y?+16y?+12y.

于是，上面的问题可以用下列线性规划的数学模型表示：

MinW=12y?+8y?+16y?+12y?

s.t.

若把制药厂利润最大的线性规划问题称为原问题，则想租用A、B、C、D

四种设备的公司的租金最小的线性规划问题称为原问题的对偶问题(dualproblem);反之，若把租用A、B、C、D四种设备的公司的租金最小的线性规划

问题称为原问题，则制药厂利润最大的线性规划问题称为原问题的对偶问题.

影子价格一般地，我们称对偶问题的最优解为原问题约束条件的影子价格，即对偶问题的解y,称为第i种资源的影子价格.它并不是某种资源在市场上的价格，而是代表单位资源在最优利用的条件下所产生的经济效果.为了和市场价格相区别，我们才称它为影子价格.它在经济上是一个很有意义的数据，通过它我们可以知道，当增加某种资源时，可以使利润增长的大小.另外，影子价格

还给出了是否应当购进某种资源以增加生产量，而获得更多利润的价格标准.

(2)对称的对偶线性规划(见课件)

如果一个线性规划具备下面两个条件，则称它具有对称形式：①所有的变量都是非负的；②所有的约束条件都是不等式，而且在目标函数是求极大值的情况，不等式具有小于和等于(≤)的符号，在目标函数是求极小值的情况，不等

式具有大于和等于(≥)的符号.

对称形式的原问题和对偶问题叫做对称的对偶线性规划.

原问题和对偶问题在形式上的对比如果我们把线性规划

MaxZ=c?x?+C?x?+…+cx,

称为原问题，则必同时存在另一线性规划问题，我们称为对偶问题：

MinW=b?Y?+b?Y?+…+bym

s.t

而且

用简缩形式表示：

MinW=MaxZ

原问题为

对偶问题为

矩阵形式表示：

原问题为MaxZ=CX

s.t.

对偶问题为MinW=Yb

s.t.

其中，C=(c?,c?,…,c)

Y=(y?,y?,…,y。)

原问题与对偶问题之间的关系

1)原问题是求目标函数的最大值，对偶问题是求目标函数的最小值.

2