《运筹学(第四版)《运筹学》教材编写组-第3章》由会员分享，可在线阅读，更多相关《运筹学(第四版)《运筹学》教材编写组-第3章（132页珍藏版）》请在金锄头文库上搜索。
1、.,1,二 线性规划与目标规划,第1章 线性规划与单纯形法 第2章 对偶理论与灵敏度分析 第3章 运输问题 第4章 目标规划,.,2,第3章 对偶理论和灵敏度分析,第1节 单纯形法的矩阵描述 第2节 改进单纯形法 第3节 对偶问题的提出 第4节 线性规划的对偶理论 第5节 对偶问题的经济解释影子价格 第6节 对偶单纯形法 第7节 灵敏度分析 第8节* 参数线性规划,.,3,第1节 单纯形法的矩阵描述,设线性规划问题可以用如下矩阵形式表示： 目标函数 max z=CX 约束条件 AXb 非负条件 X0,.,4,第1节 单纯形法的矩阵描述,将该线性规划问题的约束条件加入松弛变量后，得到标准型：,m
2、ax z=CX+0Xs AX+IXs=b X，X s0 其中I 是mm单位矩阵。,.,5,第1节 单纯形法的矩阵描述,若以Xs为基变量，并标记成XB，可将系数矩阵（A，I）分为（B，N）两块。B是基变量的系数矩阵，N是非基变量的系数矩阵。并同时将决策变量也分为两部分： 相应地可将目标函数系数C分为两部分：CB和CN，分别对应于基变量XB和非基变量XN，并且记作 C=（CB, CN）,.,6,第1节 单纯形法的矩阵描述,若经过迭代运算后，可表示为： 相应有,.,7,第1节 单纯形法的矩阵描述,线性规划问题可表示为：,.,8,第1节 单纯形法的矩阵描述,将（2-2）式移项及整理后得到：,.,9,第
3、1节 单纯形法的矩阵描述,令非基变量=0，由上式得到：,.,10,第1节 单纯形法的矩阵描述,（1）非基变量的系数表示为：,.,11,第1节 单纯形法的矩阵描述,（2）规则表示为： RHS值 表示选用0的分量 换入变量的系数向量,.,12,第1节 单纯形法的矩阵描述,（3）单纯形表与矩阵表示的关系,.,13,第1节 单纯形法的矩阵描述,单纯形表中的数据,.,14,小结,1）掌握矩阵的运算； 2）理解基矩阵的作用； 3）了解矩阵运算与单纯表的关系。,.,15,第2节 改进单纯形法,求解线性规划问题的关键是计算B-1 ，以下介绍一种比较简便的计算B-1的方法。,.,16,第2节 改进单纯形法,设m
4、n系数矩阵为A，求其逆矩阵时，可先从第1列开始。,.,17,第2节 改进单纯形法,以a11为主元素, 进行变换,.,18,第2节 改进单纯形法,然后构造含有（1）列，而其他列都是单位列的矩阵,.,19,第2节 改进单纯形法,可得到,.,20,第2节 改进单纯形法,而后以第2列的 为主元素，进行变换,.,21,第2节 改进单纯形法,然后构造含有（2）列，而其他列都是单位列的矩阵,可得到,.,22,第2节 改进单纯形法,重复以上的步骤，直到获得,可见EnE2E1=A-1。用这方法可以求得单纯形法的基矩阵B的逆矩阵B-1,.,23,第2节 改进单纯形法,以例1为例进行计算。,.,24,第2节 改进单
5、纯形法,第1步：确定初始基，初始基变量;确定换入，换出变量（1）确定初始基和初始基变量： （2）计算非基变量的检验数，确定换入变量。,.,25,第2节 改进单纯形法,(3) 确定换出变量,表示选择0的元素,.,26,第2节 改进单纯形法,（4）基变换计算 将新的基 单位矩阵。计算：,.,27,第2节 改进单纯形法,（5）计算非基变量的系数矩阵 （6）计算RHS,.,28,第2节 改进单纯形法,第1步计算结束后的结果,.,29,第2节 改进单纯形法,计算非基变量的检验数，确定换入变量,.,30,第2节 改进单纯形法,确定换出变量,.,31,第2节 改进单纯形法,由此得到新的基,.,32,第2节
6、改进单纯形法,计算RHS,.,33,第2节 改进单纯形法,第2步计算结束后的结果,.,34,第2节 改进单纯形法,第3步：计算非基变量（x3, x5）的检验数,.,35,第2节 改进单纯形法,确定换出变量,.,36,第2节 改进单纯形法,新的基,.,37,第2节 改进单纯形法,计算B的逆矩阵,.,38,第2节 改进单纯形法,计算非基变量的检验数,.,39,第2节 改进单纯形法,得到最优解：,目标函数的最优值为：,.,P87 3.1 的（1),作业,.,41,第3节 对偶问题的提出,什么是对偶？ 对同一事物（或问题），从不同的角度（或立场）提出相对的两种不同的表述。 例如：在平面内，矩形的面积与
7、其周长之间的关系，有两种不同的表述方法。 周长一定，面积最大的矩形是正方形。 面积一定，周长最短的矩形是正方形。 这种表述有利于加深对事物的认识和理解。 线性规划问题也有对偶关系。,.,42,第3节 对偶问题的提出,对第1章例1从对偶的角度进行表述。 假设该工厂的决策者决定不生产产品、，而将其所有资源出租或外售。这时工厂的决策者就要考虑给每种资源如何定价的问题。设用y1，y2，y3分别表示出租单位设备台时的租金和出让单位原材料A，B的附加额。他在做定价决策时，做如下比较：若用1个单位设备台时和4个单位原材料A可以生产一件产品，可获利2元，那么生产每件产品的设备台时和原材料出租或出让的所有收入应
8、不低于生产一件产品的利润，这就有 y1+4y22,.,43,第3节 对偶问题的提出,对第1章例1从对偶的角度进行表述。 同理将生产每件产品的设备台时和原材料出租或出让的所有收入应不低于生产一件产品的利润，这就有 2y1+4y33 把工厂所有设备台时和资源都出租或出让，其收入为 w = 8y1+16y2+12y3 从工厂的决策者来看当然w愈大愈好；但受到接受方的制约，从接受者来看他的支付愈少愈好，所以工厂的决策者只能在满足大于等于所有产品的利润条件下，提出一个尽可能低的出租或出让价格，才能实现其原意，为此需解如下的线性规划问题：,.,44,第3节 对偶问题的提出,称这个线性规划问题为例1线性规划
9、问题(这里称为原问题)的对偶问题。这就是从另一角度提出的线性规划问题。,min w=8y1+16y2+12y3 y1+4y2 2 2y1 +4y33 yi0，i=1,2,3 (2-8),.,45,第3节 对偶问题的提出,进一步来讨论它们之间的关系。 从第1节得到检验数的表达式是 CNCBB-1N与CBB-1 由第1章已知：当检验数 CN CBB-1N 0 (2-9) CBB-10 (2-10) 时，表示线性规划问题已得到最优解。这也是最优解的判断条件。,.,46,第3节 对偶问题的提出,现在讨论这两个条件。 (1) 由于(2-9)式，(2-10)式中都有乘子CBB-1，称它为单纯形乘子，用符号
10、Y= CBB-1表示。由(2-10)式，得到Y0 (2) 对应基变量XB的检验数是0，CBCBB-1B=0。包括基变量在内的所有检验数可用C CBB-1A0表示。 从此可得CCBB-1A=CYA0，移项后，得到YAC (3) Y由(2-10)式，得到 Y= CBB-1 (2-11) 将(2-11)式两边右乘b，得到 Yb= CBB-1b (2-12) Yb= CBB-1b=z，因Y的上界为无限大，所以只存在最小值。,.,47,第3节 对偶问题的提出,现在讨论这两个条件。 (4) 从这里可以得到另一个线性规划问题 min w=Yb YAC Y0 称它为原线性规划问题max z=CXAXb，X0的
11、对偶规划问题 。,.,48,第3节 对偶问题的提出,对偶规划问题,.,49,第4节 线性规划的对偶理论,4.1 原问题与对偶问题的关系 4.2 对偶问题的基本性质,.,50,4.1 原问题与对偶问题的关系,原问题（LP）：,.,51,4.1 原问题与对偶问题的关系,对偶问题(DP),.,52,4.1 原问题与对偶问题的关系,标准型原问题与对偶问题的关系,.,53,4.1 原问题与对偶问题的关系,例2 根据表2-3写出原问题与对偶问题的表达式,.,54,4.1 原问题与对偶问题的关系,下列形式的变换关系为对称形式 原问题 （LP） 对偶问题(DP),.,55,4.1 原问题与对偶问题的关系,非对
12、称形式的变换关系 原问题的约束条件中含有等式约束条件时，按以下步骤处理。 设等式约束条件的线性规划问题为,.,56,4.1 原问题与对偶问题的关系,非对称形式的变换关系 第一步：先将等式约束条件分解为两个不等式约束条件,.,57,4.1 原问题与对偶问题的关系,非对称形式的变换关系 第二步：按对称形式变换关系可写出它的对偶问题 设yi是对应(2-13)式的对偶变量，yi是对应(2-14)式的对偶变量，i=1,2,，m,.,58,4.1 原问题与对偶问题的关系,将上述规划问题的各式整理后得到,.,59,4.1 原问题与对偶问题的关系,综合上述，线性规划的原问题与对偶问题的关系可表示为：,.,60
13、,4.1 原问题与对偶问题的关系,例3 试求下述线性规划原问题的对偶问题,.,61,4.1 原问题与对偶问题的关系,由表2-4中原问题和对偶问题的对应关系，可以直接写出上述问题的对偶问题，,.,62,4.2 对偶问题的基本性质,(1) 对称性：对偶问题的对偶是原问题 ; (2)弱对偶性：若X是原问题的可行解，Y是对偶问题的可行解。则存在CXYb; (3) 无界性：若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解; (4) 可行解是最优解时的性质 ; (5) 对偶定理：若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等; (6) 互补松弛性 ; (7) 原问题检验数与对偶问题
14、解的关系。,.,63,4.2 对偶问题的基本性质,(1) 对称性： 对偶问题的对偶是原问题。 证明：设原问题是 max z=CX; AXb； X0 根据对偶问题的对称变换关系，可以找到它的对偶问题是 min w=Yb; YAC； Y0 若将上式两边取负号，又因min w=max(-)可得到 max(w)=Yb; YA C； Y0 根据对称变换关系，得到上式的对偶问题是 min( w)= CX； AX b; X0 又因 min(w)=max w，可得 Max w=max z=CX； AXb; X0 这就是原问题。,.,64,4.2 对偶问题的基本性质,(2)弱对偶性,.,65,4.2 对偶问题的
15、基本性质,(3) 无界性 若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。 证：由性质（2）可知， 例：,.,66,4.2 对偶问题的基本性质,从两图对比可明显看到原问题无界， 其对偶问题无可行解,.,67,4.2 对偶问题的基本性质,(4) 可行解是最优解时的性质,设 是原问题的可行解， 是对偶问题的可行解， 当 时， 是最优解。 证明:,.,68,4.2 对偶问题的基本性质,(5) 对偶定理 若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。,.,69,4.2 对偶问题的基本性质,(6) 互补松弛性,.,70,4.2 对偶问题的基本性质,(6) 互补松弛性,将原问题目标函数中的系数向量C用C=YA-YS代替后，得到 z=(YA YS)X=YAX YSX (2-15) 将对偶问题的目标函数中系数列向量b，用b=AX+XS代替后，得到 w=Y(AX+XS)=YAX+YXS (2-16),.,71,4.2 对偶问题的基本性质,(7) 原问题检验数与对偶问题解的关系 设原问题是 max z=CX; AX+XS=b; X,XS0 它的对偶问题是 min w=Yb; YA YS=C; Y,Y
