《《运筹学教学资料》运筹学第2章》由会员分享，可在线阅读，更多相关《《运筹学教学资料》运筹学第2章（165页珍藏版）》请在金锄头文库上搜索。
1、-1-China University of Mining and Technology运筹学 Chapter2 Chapter2 对偶理论对偶理论对偶理论对偶理论 ( Duality Theory )( Duality Theory )单纯形法的矩阵描述单纯形法的矩阵描述对偶问题的提出对偶问题的提出线性规划的对偶理论线性规划的对偶理论对偶问题的经济解释影子价格对偶问题的经济解释影子价格对偶单纯形法对偶单纯形法灵敏度分析灵敏度分析(选讲选讲)掌握掌握WinQSB软件求解对偶规划软件求解对偶规划本章主要内容：本章主要内容：本章主要内容：本章主要内容：-2-China University of
2、Mining and Technology运筹学 学习要点：学习要点：1. 理解对偶理论，掌握描述一个线性规划问题理解对偶理论，掌握描述一个线性规划问题 的对偶问题。的对偶问题。 2. 能够运用对偶单纯形法来求解线性规划问题。能够运用对偶单纯形法来求解线性规划问题。 3. 会用互补松弛条件来考虑一对对偶问题的界。会用互补松弛条件来考虑一对对偶问题的界。 4. 了解影子价格、灵敏度分析以及用了解影子价格、灵敏度分析以及用WinQSB求求 解对偶规划问题。解对偶规划问题。-3-China University of Mining and Technology运筹学 2.1 单纯形法矩阵描述单纯形法
3、矩阵描述-4-China University of Mining and Technology运筹学 0.16-0.120102412x2-0.20.4001207x11.16-3.12100840x3-1.20003.41000.10010,33012x220-0.51002.5500x430.8-0.40107.82400x3000127301001033000x540010542000x490001493600x3x5x4x3x2x1B-1bCBXB每一列的含每一列的含义？义？每个表中的每个表中的B和和B-1的查的查找？找？B从初表中找，从初表中找，B-1从当前表中从当前表中找，相当于
4、初表找，相当于初表中的中的I的位置的位置单单纯纯形形法法的的矩矩阵阵描描述述-5-China University of Mining and Technology运筹学 单纯形法的主要步骤单纯形法的主要步骤因此，单纯形表的主体内容是因此，单纯形表的主体内容是B-1(b,A)CXB-1bB-1AC- CB-1A单纯形表的主要结构单纯形表的主要结构单单纯纯形形法法的的矩矩阵阵描描述述-6-China University of Mining and Technology运筹学 CBCNbXBXNbBNCBCNbXBXNB-1bIB-1N-CBB-1b0CN-CBB-1 N 单单纯纯形形法法的的矩
5、矩阵阵描描述述-7-China University of Mining and Technology运筹学 CBCNCS(0)bXBXNXSbBNI0CBCN0CBCNCS(0)bXBXNXSB-1bIB-1NB-1-CBB-1b0CN-CBB-1 N-CBB-1 单单纯纯形形法法的的矩矩阵阵描描述述-8-China University of Mining and Technology运筹学 单单纯纯形形法法的的矩矩阵阵描描述述-9-China University of Mining and Technology运筹学 2.2 改进单纯形法改进单纯形法-10-China Universi
6、ty of Mining and Technology运筹学 15001/31/311/35X23301-1-2013X500001320j-1001-113X6000-1001-156101/34/304/38X6001x4010x5000x606-13218X50513115X40x3x2x1bXBCB1321/4-1/35/121001X32-5/6-1/61/4-1/31/30-1/21/2-1/4000-20j0015X100103X20P1P1P1思考：思考：P1分分别与别与P1、 P1的关系的关系改改 进进 的的 单单 纯纯 形形 法法-11-China University o
7、f Mining and Technology运筹学 231000CBXBbx1x2x3x4x5x60X41513110050X51823-101060X631-11001-j02310003X251/311/31/300150X5310-2-11030X684/304/31/3016-15100-100改改 进进 的的 单单 纯纯 形形 法法-12-China University of Mining and Technology运筹学 231000CBXBbx1x2x3x4x5x63X251/311/31/300150X5310-2-11030X684/304/31/3016j-15100
8、-1000X240112/3-1/3041X1310-2-110-0X640045/3-4/311j-180020-10改改 进进 的的 单单 纯纯 形形 法法-13-China University of Mining and Technology运筹学 设设mm系数矩阵系数矩阵A，求其逆矩阵求其逆矩阵可以先从第可以先从第1列开始列开始:以下介绍一种比较简便的计算方法以下介绍一种比较简便的计算方法求解线性规划问题的关键是计算求解线性规划问题的关键是计算B-1改改 进进 的的 单单 纯纯 形形 法法-14-China University of Mining and Technology运筹学
9、 以以a11为主元素为主元素, 进行变换进行变换然后构造含有（然后构造含有（1）列，而其他列都是单位列的矩阵）列，而其他列都是单位列的矩阵改改 进进 的的 单单 纯纯 形形 法法-15-China University of Mining and Technology运筹学 可得到：可得到：而后以第而后以第2列的列的a22(1) 为主元素，进行变换为主元素，进行变换改改 进进 的的 单单 纯纯 形形 法法-16-China University of Mining and Technology运筹学 然后构造含有（然后构造含有（2）列，而其他列都是单位列的矩阵）列，而其他列都是单位列的矩阵 可
10、得到可得到改改 进进 的的 单单 纯纯 形形 法法-17-China University of Mining and Technology运筹学 重复以上的步骤，直到获得重复以上的步骤，直到获得求单纯形表的基矩阵的逆矩阵也可以用这方法。求单纯形表的基矩阵的逆矩阵也可以用这方法。改改 进进 的的 单单 纯纯 形形 法法书上例题自学。书上例题自学。-18-China University of Mining and Technology运筹学 2.3 对偶问题的提出-19-China University of Mining and Technology运筹学 对偶对偶理论是线性规划中最重要的理
11、论之一，是深入了理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，统进行经济分析和敏感性分析的重要工具。那么，对偶问对偶问题是怎样提出的，为什么会产生这样一种问题呢？题是怎样提出的，为什么会产生这样一种问题呢？对偶问题的提出对偶问题的提出-20-China University of Mining and Technology运筹学 俩家具制造商间的对话：俩家具
12、制造商间的对话：唉唉!我想租您的木工和我想租您的木工和油漆工一用。咋样？价油漆工一用。咋样？价格嘛格嘛好说，肯定不好说，肯定不会让您兄弟吃亏。会让您兄弟吃亏。 王老板做家王老板做家具赚了大钱，具赚了大钱，可惜我老李可惜我老李有高科技产有高科技产品，却苦于品，却苦于没有足够的没有足够的木工和油漆木工和油漆工咋办？只工咋办？只有租咯。有租咯。Hi：王老板，听王老板，听说近来家具生意说近来家具生意好呀，也帮帮兄好呀，也帮帮兄弟我哦弟我哦!家具生意还真赚钱，家具生意还真赚钱，但是现在的手机生但是现在的手机生意这么好，不如干意这么好，不如干脆把我的木工和油脆把我的木工和油漆工租给他，又能漆工租给他，又能
13、收租金又可做生意。收租金又可做生意。价格嘛价格嘛好商量，好商量， 好商量。只好商量。只是是. 王王 老老 板板李李 老老 板板引例引例1对偶问题的提出对偶问题的提出-21-China University of Mining and Technology运筹学 王老板的王老板的家具生产模型家具生产模型：x1 、 x2是桌、椅生产量。是桌、椅生产量。Z是家具销售总收入（总利润）。是家具销售总收入（总利润）。max Z = 50x1 + 30x2s.t. 4x1+3x2 120（木工）木工） 2x1+ x2 50 （油漆工）油漆工） x1，x2 0原始线性规划问题，记为（原始线性规划问题，记为（P
14、）王老板的王老板的资源出租模型资源出租模型：y1、 y2单位木、漆工出租价格。单位木、漆工出租价格。W是资源出租租金总收入。是资源出租租金总收入。min W =120y1 + 50y2s.t. 4y1+2y2 50 3y1+ y2 30 y1，y2 0对偶线性规划问题，记为（对偶线性规划问题，记为（D）1.所得不得低于生产的获利所得不得低于生产的获利（不吃亏原则）（不吃亏原则）2.要使对方能够接受要使对方能够接受3. （竞争性原则）（竞争性原则）两个原则两个原则对偶问题的提出对偶问题的提出-22-China University of Mining and Technology运筹学 王老板按
15、（王老板按（D D）的解的解 y1 、y2出租其拥有的木、漆工出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金的吸引力（李老板所付出的总租金W W最少）。最少）。按时下最流行的一个词，叫什么来着按时下最流行的一个词，叫什么来着按时下最流行的一个词，叫什么来着按时下最流行的一个词，叫什么来着对偶问题的提出对偶问题的提出-23-China University of Mining and T
16、echnology运筹学 Max Z= 40x1 +50x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t目标函数目标函数约束条件约束条件设设三种资源的使用单价分别为三种资源的使用单价分别为 y1 , y2 , y3y1 y2 y3生产单位产品生产单位产品A的资源消耗所得不少于单位产品的资源消耗所得不少于单位产品A的获利的获利生产单位产品生产单位产品B的资源消耗所得不少于单位产品的资源消耗所得不少于单位产品B的获利的获利y1 +3 y2 40 2y1 + 2 y2 + 2y3 50甲甲乙乙资源量资源量A1230B3260C0224单位获利单位获利4050
17、引例引例2通过使用所有资源对外加工所获得的收益通过使用所有资源对外加工所获得的收益W = 30y1 + 60 y2 + 24y3对偶问题的提出对偶问题的提出-24-China University of Mining and Technology运筹学 根据原则根据原则2 ，对方能够接受的价格显然是越低越好，因此，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：此问题可归结为以下数学模型：Min W = 30y1 + 60 y2 + 24y3 y1 + 3y2 402y1 + 2 y2 + 2y3 50y1 , y2 , y3 0s.t目标函数目标函数约束条件约束条件原线性规
18、划问题称为原线性规划问题称为原问题原问题，此问题为此问题为对偶问题对偶问题，y1 , y2 , y3为为对偶变量对偶变量，也称为，也称为影子价格影子价格对偶问题的提出对偶问题的提出-25-China University of Mining and Technology运筹学 2.4 2.4 线性规划的对偶理论线性规划的对偶理论-26-China University of Mining and Technology运筹学 Max Z= 40x1 +50x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t原问题原问题（对偶问题）（对偶问题）对偶问题对偶问题
19、（原问题）（原问题）一、一、一、一、 原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题与对偶问题的对应关系Min W = 30y1 + 60 y2 + 24y3 y1 + 3y2 402y1 + 2 y2 + 2y3 50y1 , y2 , y3 0s.t（y1）（y2）（y3）（x1）13040（x2）22250306024minmaxz3 3个约束个约束2 2个变量个变量2 2个约束个约束 3 3个变量个变量线性规划的对偶理论线性规划的对偶理论-27-China University of Mining and Technology运筹学 对偶问题的形式
20、对偶问题的形式定义定义 设原线性规划问题为设原线性规划问题为 则称下列线性规划问题则称下列线性规划问题l为其对偶问题，其中为其对偶问题，其中yi (i=1,2,m) 称为称为对偶变量对偶变量l上述对偶问题称为上述对偶问题称为对称型对称型对称型对称型对偶问题对偶问题l原问题简记为原问题简记为(P)，对偶问题简记为对偶问题简记为(D)称问题称问题(P)和和(D )为为一对对偶问题一对对偶问题线性规划的对偶理论线性规划的对偶理论-28-China University of Mining and Technology运筹学 对称型问题的对偶规则对称型问题的对偶规则对称型问题的对偶规则对称型问题的对偶
21、规则1、给每个原始约束条件定义一个非负对偶变量、给每个原始约束条件定义一个非负对偶变量yi(i=1,2,m)；2、使原问题的目标函数系数使原问题的目标函数系数 cj 变为其对偶问题约束条变为其对偶问题约束条 件的右端常数；件的右端常数；3、使原问题约束条件的右端常数、使原问题约束条件的右端常数 bi 变为其对偶问题目变为其对偶问题目 标函数的系数；标函数的系数；4、将原问题约束条件的系数矩阵转置，得到其对偶问、将原问题约束条件的系数矩阵转置，得到其对偶问 题约束条件的系数矩阵；题约束条件的系数矩阵；5、改变约束问题不等号的方向，即将、改变约束问题不等号的方向，即将“”改为改为“”；6、原问题为
22、、原问题为“max”型，对偶问题为型，对偶问题为“min”型。型。线性规划的对偶理论线性规划的对偶理论-29-China University of Mining and Technology运筹学 原始原始问题问题Max Z=CXs.t. AXbX 0bACMaxnm对偶问题对偶问题Min W=Ybs.t.YACY 0MinCATbnmY为行向量为行向量线性规划的对偶理论线性规划的对偶理论-30-China University of Mining and Technology运筹学 当原问题为求极小值时，对偶问题为求极大值。当原问题为求极小值时，对偶问题为求极大值。原始问题中目标函数的系数
23、变成对偶问题中约束条件原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问题中的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系数。目标函数的系数。原始问题约束条件系数矩阵的转置对应对偶问题中约原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵。束条件的系数矩阵。原始问题的约束条件个数决定对偶问题变量的个数；原始问题的约束条件个数决定对偶问题变量的个数；原始问题变量个数，决定对偶问题的约束个数。原始问题变量个数，决定对偶问题的约束个数。原始问题的约束方程的匹配形式决定对偶问题变量的原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问
24、题决策变量的符号决定所对应对偶问题符号；原始问题决策变量的符号决定所对应对偶问题的约束方程的匹配形式。的约束方程的匹配形式。线性规划的对偶理论线性规划的对偶理论-31-China University of Mining and Technology运筹学 求线性规划问题的求线性规划问题的对偶规划对偶规划解：由原问题的结构可知为对称型对偶问题解：由原问题的结构可知为对称型对偶问题例例1线性规划的对偶理论线性规划的对偶理论-32-China University of Mining and Technology运筹学 求线性规划问题的求线性规划问题的对偶规划对偶规划解：由原问题的结构可知不是对称
25、型对偶问题，可先化为解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。对称型，再求其对偶规划。例例2线性规划的对偶理论线性规划的对偶理论-33-China University of Mining and Technology运筹学 求线性规划问题的求线性规划问题的对偶规划对偶规划解：由原问题的结构可知不是对称型对偶问题，可先化为解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。对称型，再求其对偶规划。例例3线性规划的对偶理论线性规划的对偶理论-34-China University of Mining and Technology运筹学 上式已
26、为对称型对偶问题，故可写出它的对偶规划上式已为对称型对偶问题，故可写出它的对偶规划令令则上式化为则上式化为线性规划的对偶理论线性规划的对偶理论-35-China University of Mining and Technology运筹学 q对偶问题的非对称形式对偶问题的非对称形式min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max w=6y1+12y2+8y3+15y4s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3- y4 -1
27、 y1 0,y2 ,y3 0,y4 0=unr=x10x20x3: unrq原始问题变量的个数原始问题变量的个数(3)等于对偶问题约束条件的个数等于对偶问题约束条件的个数(3)； 原始问题约束条件的个数原始问题约束条件的个数(4)等于对偶问题变量的个数等于对偶问题变量的个数(4)。q原始问题变量的性质影响对偶问题约束条件的性质，用原始问题变量的性质影响对偶问题约束条件的性质，用 表示表示 原始问题约束条件的性质影响对偶问题变量的性质，用原始问题约束条件的性质影响对偶问题变量的性质，用 表示表示线性规划的对偶理论线性规划的对偶理论-36-China University of Mining an
28、d Technology运筹学 1 原问题为原问题为“max”，对偶问题为对偶问题为“min”；2 原问题中目标函数系数原问题中目标函数系数 ci 变为其对偶问题约束条件的右端常数；变为其对偶问题约束条件的右端常数；3 原问题约束条件的右端常数原问题约束条件的右端常数 bi 变为其对偶问题目标函数的系数；变为其对偶问题目标函数的系数；4 原问题约束条件的系数矩阵转置，即为其对偶问题的系数矩阵；原问题约束条件的系数矩阵转置，即为其对偶问题的系数矩阵；5 原问题的变量个数原问题的变量个数n等于其对偶问题的约束条件个数等于其对偶问题的约束条件个数n，原问题原问题 约束约束条件的个数条件的个数m等于其
29、对偶问题变量的个数等于其对偶问题变量的个数m；6 在求极大值的原问题中，在求极大值的原问题中，“”，“”和和“=”的约束条件分别的约束条件分别对应其对偶变量对应其对偶变量“0”，“0”和和“无符号限制无符号限制”；7 在求极大值的原问题中，变量在求极大值的原问题中，变量“0”，“0”和和“无符号限制无符号限制”分别对应其对偶约束条件的分别对应其对偶约束条件的“”，“”和和“=”约束约束.混合型问题的对偶规则：混合型问题的对偶规则：线性规划的对偶理论线性规划的对偶理论-37-China University of Mining and Technology运筹学 原问题（或对偶问题）对偶问题（或
30、原问题）约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项目标函数max目标函数min约束条件m个m个变量00=无约束变量n个n个约束条件00无约束=线性规划的对偶理论线性规划的对偶理论-38-China University of Mining and Technology运筹学 Max Z=40x1+ 50x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0 0s.ty1y2y3Min W = 30y1+ 60y2 + 24y3 y1+3y2 + 0y3 402y1+2y2 + 2y3 50 y1 , y2 , y3 0 0s.tMax W= -30
31、y1- 60y2 - 24y3 y1+3y2 + 0y3 y4 = = 402y1+2y2 + 2y3 y5 = = 50 y1 , y2 , y3 , y4 , y5 0 0s.t例例4二、二、二、二、 对偶问题的解对偶问题的解对偶问题的解对偶问题的解线性规划的对偶理论线性规划的对偶理论-39-China University of Mining and Technology运筹学 Max W= -30y1- 60y2 - 24y3 +0(y4 + y5 )-M (y6 + y7 ) y1+3y2 + 0y3 y4 + y6 = = 402y1+2y2 + 2y3 y5 + y7 = = 5
32、0 y1 , y2 , y3 , y4 , y5 0 0s.tcj-30-60-2400-M-MB-1bcByBy1y2y3y4y5y6y7-My6130-10104040/3-My72220-1015050/2j3M-305M-602M-24-M-M00-90M线性规划的对偶理论线性规划的对偶理论-40-China University of Mining and Technology运筹学 cj-30-60-2400-M-MB-1bcByBy1y2y3y4y5y6y7-60y21/310-1/301/3040/3-My74/3022/3-1-2/3170/335/3j4M/3-1002M-
33、242M/3+20-M-5M/3+200800-70M/3-60y21/310-1/301/3040/340-24y32/3011/3-1/2-1/31/235/335/2j600-12-12-M+12-M+12-1080-60y201-1/2-1/21/41/2-1/415/2-30y1103/21/2-3/4-1/23/435/2j00-9-15-15/2-M+30-M-15/2-975线性规划的对偶理论线性规划的对偶理论-41-China University of Mining and Technology运筹学 cj4050000 B-1bcBxBx1x2x3x4x540x1101/
34、2-1/20150x5003/2-1/21950x201-3/41/4015/2j00-35/2-15/20975 Max Z=40x1+ 50x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0 0s.t x1+2x2 +x3 = 303x1+2x2 +x4 =60 2x2 +x5 = 24 x1 x5 0 0s.t线性规划的对偶理论线性规划的对偶理论-42-China University of Mining and Technology运筹学 线性规划的对偶理论线性规划的对偶理论-43-China University of Mining and Technol
35、ogy运筹学 原问题与其对偶问题的变量与解的对应关系： 在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。线性规划的对偶理论线性规划的对偶理论-44-China University of Mining and Technology运筹学 XBb原原问题的变量问题的变量原原问题的松弛变量问题的松弛变量x1x2x3x4x5x115101/2-1/20x59003/2-1/21x215/2013/4-1/4000-35/2-15/20YBb对偶问题对偶问题的变量的变量对偶问题的对偶问题的剩余变量剩余变量y1y2y3y4y5y215/201-1/2-1/21/4y
36、135/2103/21/2-3/400-9-15-15/2原问原问题最题最优表优表对偶对偶问题问题最优最优表表 Max Z=40x1+ 50x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0 0s.tMin W = 30y1+ 60y2 + 24y3 y1+3y2 + 0y3 402y1+2y2 + 2y3 50 y1 , y2 , y3 0 0s.t线性规划的对偶理论线性规划的对偶理论-45-China University of Mining and Technology运筹学 性质性质1 对称性定理对称性定理：对偶问题的对偶是原问题：对偶问题的对偶是原问题 m
37、in W= Y bs.t. YA C Y 0max Z=C Xs.t. AXb X 0三、三、三、三、 对偶原理对偶原理对偶原理对偶原理线性规划的对偶理论线性规划的对偶理论-46-China University of Mining and Technology运筹学 min z= - CXs.t. -AX-bX 0maxw= -Ybs.t. -YA-C Y 0min w=Ybs.t. YAC Y 0max z=CXs.t. AXb X 0对偶的对偶的定义定义对偶的对偶的定义定义简要证明：简要证明：线性规划的对偶理论线性规划的对偶理论-47-China University of Mining
38、 and Technology运筹学 性质性质2 弱对偶原理弱对偶原理(弱对偶性弱对偶性)：设设 和和 分别是问题分别是问题(P)和和(D)的可行解，则必有的可行解，则必有推论推论1: 原问题任一可行解的目标函数值是其对偶问题目标函数值原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任意可行解的目标函数值是其原问题目的下界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。标函数值的上界。证明：证明：(1) 当当X和和Y为原问题和对偶问题的一个可行解为原问题和对偶问题的一个可行解有有原问题目标函数值原问题目标函数值对偶问题目标函数值对偶问题目标函数值线性规
39、划的对偶理论线性规划的对偶理论-48-China University of Mining and Technology运筹学 推论推论2: 在一对对偶问题（在一对对偶问题（P）和（）和（D）中，若其中一个问题可行但）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；目标函数无界，则另一个问题无可行解；反之不成立反之不成立。这也是对这也是对偶问题的偶问题的无界性无界性无界性无界性。若（若（P）为无界解，则（）为无界解，则（D）无可行解；）无可行解；若（若（D）为无界解，则（）为无界解，则（P）无可行解。）无可行解。线性规划的对偶理论线性规划的对偶理论推论推论3：在一对对偶问题（在一对
40、对偶问题（P）和（）和（D）中，若一个可行（如）中，若一个可行（如P），），而另一个不可行（如而另一个不可行（如D），则该可行的问题目标函数值无界。），则该可行的问题目标函数值无界。-49-China University of Mining and Technology运筹学 已知原问题已知原问题(LP)，试估计它的目标函数值的界试估计它的目标函数值的界,并验证弱对偶定理并验证弱对偶定理.例例5线性规划的对偶理论线性规划的对偶理论-50-China University of Mining and Technology运筹学 解：解：解：解：问题问题(LP)的对偶问题的对偶问题(DP)为为
41、(DP)线性规划的对偶理论线性规划的对偶理论-51-China University of Mining and Technology运筹学 由观察可知由观察可知 分别是原问题和对偶问题的可行解。分别是原问题和对偶问题的可行解。 ，弱对偶定理成立。，弱对偶定理成立。且由推论且由推论1知，对偶问题目标函数知，对偶问题目标函数W的下界为的下界为10，原问题目，原问题目标函数标函数Z的上界为的上界为40。且原问题的目标函数值为且原问题的目标函数值为对偶问题的目标函数值为对偶问题的目标函数值为故故线性规划的对偶理论线性规划的对偶理论-52-China University of Mining and
42、Technology运筹学 例：利用对偶性质判断下面问题有无最优解例：利用对偶性质判断下面问题有无最优解例例6解：此问题的对偶问题为解：此问题的对偶问题为不能成立，因此对偶问题不不能成立，因此对偶问题不可行。故由推论可行。故由推论3知原问题知原问题无界。无界。为可行解为可行解线性规划的对偶理论线性规划的对偶理论-53-China University of Mining and Technology运筹学 性质性质3 最优性定理：最优性定理：如果如果 是原问题的可行解，是原问题的可行解， 是其对偶是其对偶问题的可行解，并且问题的可行解，并且:则则 是原问题的最优解，是原问题的最优解， 是其对偶
43、问题的最优解。是其对偶问题的最优解。线性规划的对偶理论线性规划的对偶理论-54-China University of Mining and Technology运筹学 性质性质4 强强(主主)对偶性：对偶性：若原问题及其对偶问题均具有可行解，若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。则两者均具有最优解，且它们最优解的目标函数值相等。还可推出另一结论：还可推出另一结论：若一对对偶问题中的任意一个有最优解，若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等；若一个问题则另一个也有最优解，且目标函数最优值相等；若一个问题无最优解，
44、则另一问题也无最优解。无最优解，则另一问题也无最优解。一对对偶问题的关系，有且仅有下列三种：一对对偶问题的关系，有且仅有下列三种：1.都有最优解，且目标函数最优值相等；都有最优解，且目标函数最优值相等；2.两个都无可行解；两个都无可行解；3.一个问题无界，则另一问题无可行解。一个问题无界，则另一问题无可行解。线性规划的对偶理论线性规划的对偶理论-55-China University of Mining and Technology运筹学 证明：证明：当当X*为原问题的一个最优解，为原问题的一个最优解，B为相应的最优基，通过引为相应的最优基，通过引入松弛变量入松弛变量Xs，将问题，将问题(P)
45、转化为标准型转化为标准型令令CCBCN0解解基系数基系数基变量基变量XBXNXsCBXBIB-1NB-1B-1b0CN -CBB-1N -CBB-1CBB-1bCXAC-CBB-1A说明说明Y*可行可行线性规划的对偶理论线性规划的对偶理论-56-China University of Mining and Technology运筹学 问题问题:（1）由性质）由性质4可知，对偶问题最优解的表达式可知，对偶问题最优解的表达式 Y*=?（2）求）求 Y*是否有必要重新求解是否有必要重新求解(D)?不必。可以从原问题（不必。可以从原问题（P）的单纯形终表获得。）的单纯形终表获得。CCBCN0解解基系数
46、基系数基变量基变量XBXNXsCBXBIB-1NB-1B-1b0CN -CBB-1N -CBB-1CBB-1b线性规划的对偶理论线性规划的对偶理论-57-China University of Mining and Technology运筹学 性质性质5 互补松弛性互补松弛性：设：设X0和和Y0分别是分别是P问题问题 和和 D问题问题 的可行的可行解，则它们分别是最优解的充要条件是：解，则它们分别是最优解的充要条件是：其中：其中：Xs、Ys为松弛变量为松弛变量。在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，则在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，则该
47、约束条件取严格等式该约束条件取严格等式；另一方面，如果约束条件取严格不等式，则其对应另一方面，如果约束条件取严格不等式，则其对应的变量一定为零。的变量一定为零。紧约束与紧约束与紧约束与紧约束与松约束松约束松约束松约束线性规划的对偶理论线性规划的对偶理论-58-China University of Mining and Technology运筹学 一个约束称为一个约束称为紧约束紧约束，如果该约束在，如果该约束在所有最优解所有最优解上的值使左右上的值使左右取等号。取等号。 即我们把严格等式约束称为紧约束（或起作用约束）即我们把严格等式约束称为紧约束（或起作用约束）. 不是紧约束的约束称为不是紧约
48、束的约束称为松约束松约束。 即把即把某一最优解某一最优解处取严格不等式的约束称为松约束（或不起处取严格不等式的约束称为松约束（或不起作用约束）。作用约束）。对于最优解对于最优解X*和和Y*而言，而言，松约束的对偶约束是紧约束松约束的对偶约束是紧约束.以上关系称为对偶问题的以上关系称为对偶问题的互补松弛关系互补松弛关系或或松紧关系松紧关系。在计算上，。在计算上，若已知一个问题的最优解，则可利用互补松弛条件求另一个问若已知一个问题的最优解，则可利用互补松弛条件求另一个问题的最优解题的最优解. .紧约束与松约束紧约束与松约束紧约束与松约束紧约束与松约束松紧关系松紧关系非常重要非常重要线性规划的对偶理
49、论线性规划的对偶理论-59-China University of Mining and Technology运筹学 证证: (: (必要性）必要性）原问题原问题 对偶问题对偶问题线性规划的对偶理论线性规划的对偶理论-60-China University of Mining and Technology运筹学 y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量 原始问题的变量原始问题的变量 原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m; j=
50、1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0，另一个一定等于，另一个一定等于0线性规划的对偶理论线性规划的对偶理论-61-China University of Mining and Technology运筹学 性质性质5的应用：的应用：该性质给出了已知一个问题最优解求另一个问题最优解该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知的方法，即已知Y求求X或已知或已知X求求Y互补松弛条件互补松弛条件由于变量都非负，要使求和式等于零，则必定每一分量为零，由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：因而有下列关系： 若若Y0，则，则Xs必
51、为必为0；若；若X0，则，则Ys必为必为0利用上述关系，建立对偶问题（或原问题）的约束线性方程组，利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。方程组的解即为最优解。线性规划的对偶理论线性规划的对偶理论-62-China University of Mining and Technology运筹学 已知线性规划已知线性规划的最优解是的最优解是X=(6,2,0)T,求其对偶问题的最优解求其对偶问题的最优解Y。解：写出原问题的对偶问题，即解：写出原问题的对偶问题，即标准化标准化例例7线性规划的对偶理论线性规划的对偶理论-63-China University of
52、Mining and Technology运筹学 设对偶问题最优解为设对偶问题最优解为Y(y1，y2),由互补松弛性定理可知，由互补松弛性定理可知，X和和 Y满足满足：即：即：因为因为x10，x20，所以对偶问题的第一、二个约束的松弛变，所以对偶问题的第一、二个约束的松弛变量等于零，即量等于零，即y30，y40，带入方程中：，带入方程中：解此线性方程组得解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为：从而对偶问题的最优解为：Y=(1,1)，最优值，最优值w=26。线性规划的对偶理论线性规划的对偶理论-64-China University of Mining and Technol
53、ogy运筹学 已知线性规划已知线性规划 的对偶问题的最优解为的对偶问题的最优解为Y=(0,-2)，求原问题的最优解。，求原问题的最优解。解解: 对偶问题是对偶问题是标准化标准化例例8线性规划的对偶理论线性规划的对偶理论-65-China University of Mining and Technology运筹学 设原问题最优解为设原问题最优解为X(x1，x2 ，x3)T ,由互补松弛性定理知，由互补松弛性定理知，X和和 Y满足满足：将将Y带入由方程可知，带入由方程可知，y3y50，y41。y2=-20 x50又又y4=10 x20将将x2，x5分别带入原问题约束方程中，得：分别带入原问题约束
54、方程中，得：解方程组得：解方程组得：x1=-5,x3=-1, 所以原问题的最优解为所以原问题的最优解为X=(-5,0,-1)，最优值，最优值z=-12线性规划的对偶理论线性规划的对偶理论-66-China University of Mining and Technology运筹学 试用对偶原理求解线性规划问题试用对偶原理求解线性规划问题已知其对偶规划的最优解为已知其对偶规划的最优解为练习练习线性规划的对偶理论线性规划的对偶理论-70-China University of Mining and Technology运筹学 对偶规划可以用线性规划的单纯形法求解。对偶规划可以用线性规划的单纯形法
55、求解。由对偶原理可见，原问题与对偶问题之间有紧密联系，因由对偶原理可见，原问题与对偶问题之间有紧密联系，因此我们能够通过求解原问题来找出对偶问题的解，反之依然。此我们能够通过求解原问题来找出对偶问题的解，反之依然。互补松弛条件就可以解决由原问题的最优解直接求出对偶互补松弛条件就可以解决由原问题的最优解直接求出对偶问题的最优解。问题的最优解。对偶问题解的求法对偶问题解的求法线性规划的对偶理论线性规划的对偶理论-71-China University of Mining and Technology运筹学 原问题与对偶问题解的对应关系小结原问题与对偶问题解的对应关系小结对应关系对应关系原问题原问题
56、最优解最优解无界解无界解无可行解无可行解对偶问题对偶问题最优解最优解(Y,Y)(N,N)无界解无界解(Y,Y)无可行解无可行解(Y,Y)无法判断无法判断线性规划的对偶理论线性规划的对偶理论-73-China University of Mining and Technology运筹学 2.5 2.5 影子价格影子价格-74-China University of Mining and Technology运筹学 单位产品消耗的资源单位产品消耗的资源( (吨吨/ /件件)原始问题是利润最大化的生产计划问题原始问题是利润最大化的生产计划问题总利润总利润( (元元) )产品产量产品产量( (件件)
57、)单位产品的利润单位产品的利润( (元元/ /件件) )消耗的资源消耗的资源( (吨吨) )剩余的资源剩余的资源( (吨吨) )资源限量资源限量( (吨吨) )影影 子子 价价 格格-75-China University of Mining and Technology运筹学 对偶问题对偶问题资源定价问题资源定价问题对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为称为m种资源的种资源的影子价格影子价格（Shadow Price）原始和对偶问题都取得最优解时，原始和对偶问题都取得最优解时，最大利润最大利润 Max z=Min w总利润总利
58、润(元元)资源限量资源限量(吨吨)资源价格资源价格(元元/吨吨)影影 子子 价价 格格-76-China University of Mining and Technology运筹学 在在一一对对 P 和和 D 中中，若若 P 的的某某个个约约束束条条件件的的右右端端项项常常数数 bi （第第 i 种种资资源源的的拥拥有有量量）增增加加一一个个单单位位时时，所所引引起起目目标标函函数数最最优优 值值 z* 的的改改变变量量称称为为第第 i 种种资资源源的的影影子子价价格格，其其值值等等于于 D问题中对偶变量问题中对偶变量 yi*。由对偶问题得基本性质可得：由对偶问题得基本性质可得：1. 影子价
59、格的数学分析：影子价格的数学分析：影影 子子 价价 格格-77-China University of Mining and Technology运筹学 2. 影子价格的经济意义影子价格的经济意义1）影子价格是一种边际价格）影子价格是一种边际价格在其它条件不变的情况下，单位资源数量的变化所引起的在其它条件不变的情况下，单位资源数量的变化所引起的目标函数最优值的变化。即对偶变量目标函数最优值的变化。即对偶变量yi 就是第就是第 i 种资源的影子种资源的影子价格。即：价格。即： 影影 子子 价价 格格影影子子价价格格是是针针对对某某一一具具体体约约束束条条件件而而 言言 ,因因此此影影子子价价格格
60、可可理理解解为为目目标标函函数数最最优优值值对对资资源源的的一一阶阶偏偏导导数数-78-China University of Mining and Technology运筹学 资源影子价格的性质资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于价格一定等于0 0影影 子子 价价 格格-80-China University of Mining and Technology
61、运筹学 0X2X1X= (15,7.5) Z=975Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t-81-China University of Mining and Technology运筹学 0X2X1X= (15,7.5) Z=975X= (14.5,8.25) Z=992.5Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t-82-China University of Mining and Technology运筹学 0X2X1X= (15,7.5) Z=9
62、75X= (15.5,7.25) Z=982.5Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t-83-China University of Mining and Technology运筹学 0X2X1X= (15,7.5) Z=975Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t-84-China University of Mining and Technology运筹学 0X2X1X= (15,7.5) Z=975X= (15.5,7.25) Z=982.5
63、X= (14.5,8.25) Z=992.5Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t-85-China University of Mining and Technology运筹学 2）影子价格是一种机会成本）影子价格是一种机会成本影子价格是在资源最优利用条件下对单位资源的估价，这影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市场价格。因此，从另一个角度说，它种估价不是资源实际的市场价格。因此，从另一个角度说，它是一种机会成本。是一种机会成本。若第若第i 种资源的单位市场价格为种资源的单位市场价格为
64、mi ，则有，则有当当yi* mi 时，企业愿意购进这种资源，单位纯利为时，企业愿意购进这种资源，单位纯利为yi*mi ，则有利可图；，则有利可图；当当yi* mi 则购进资源则购进资源 i，可，可获单位纯利获单位纯利yi*mi ； 若若yi* 0，则，则xn+i =0如果如果xn+i 0，则，则yi =0影子价格大于0的资源，在最优生产计划条件下没有剩余ym+jxj=0如果如果ym+j 0，则，则xj =0如果如果xj 0，则，则ym+j =0最优生产计划条件下有剩余的资源，其影子价格等于0差额成本大于0（机会成本大于利润）的产品，不安排生产安排生产的产品，差额成本等于0（机会成本等于利润）
65、互补松弛关系经济解释互补松弛关系经济解释影影 子子 价价 格格-90-China University of Mining and Technology运筹学 4）影子价格对单纯形表计算的解释）影子价格对单纯形表计算的解释单纯形表中的检验数单纯形表中的检验数其中其中cj表示第表示第j种产品的价格种产品的价格; 表示生产该种产品所消耗表示生产该种产品所消耗的各项资源的影子价格的总和，即产品的隐含成本。的各项资源的影子价格的总和，即产品的隐含成本。当产值大于隐含成本时，即当产值大于隐含成本时，即 ，表明生产该项产品有利，表明生产该项产品有利，可在计划中安排；可在计划中安排；否则否则 ，用这些资源生
66、产别的产品更有利，不在生产中，用这些资源生产别的产品更有利，不在生产中安排该产品。安排该产品。影影 子子 价价 格格-91-China University of Mining and Technology运筹学 2.6 2.6 对偶单纯形法对偶单纯形法-92-China University of Mining and Technology运筹学 对偶单纯形法是求解线性规划的另一个基本方法。它是根对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。形法。不要简单理解为是求解对偶问题
67、的单纯形法。不要简单理解为是求解对偶问题的单纯形法。对偶单纯形法原理对偶单纯形法原理对偶单纯形法基本思路：对偶单纯形法基本思路： 找出一个对偶问题的可行基，保持对偶问题为可行解的条找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断件下，判断XB是否可行（是否可行（XB为非负），若否，通过变换基解，为非负），若否，通过变换基解，直到找到原问题基可行解（即直到找到原问题基可行解（即XB为非负），这时原问题与对为非负），这时原问题与对偶问题同时达到可行解，由定理偶问题同时达到可行解，由定理4可得最优解。可得最优解。对对 偶偶 单单 纯纯 形形 法法-93-China University
68、of Mining and Technology运筹学 找出一个找出一个DP的可行基的可行基LP是否可行是否可行（XB 0）保持保持DP为可行解情况下转移到为可行解情况下转移到LP的另一个基本解的另一个基本解最优解最优解是是否否循循环环结束结束对对 偶偶 单单 纯纯 形形 法法-94-China University of Mining and Technology运筹学 先回顾一下单纯形算法：先回顾一下单纯形算法：它是从线性规划的一个基可行解迭代到另一个基可行解的过它是从线性规划的一个基可行解迭代到另一个基可行解的过程，在迭代过程中，保持基解的可行性，逐步消除基解的检程，在迭代过程中，保持基
69、解的可行性，逐步消除基解的检验数的非负性，即验数的非负性，即为了求解线性规划，我们也可以从线性规划的一个基解迭代为了求解线性规划，我们也可以从线性规划的一个基解迭代到另一个基解，在迭代过程中，保持基解的检验数的非正性，到另一个基解，在迭代过程中，保持基解的检验数的非正性，逐步消除基解的不可行性，即逐步消除基解的不可行性，即对对 偶偶 单单 纯纯 形形 法法-95-China University of Mining and Technology运筹学 如果原问题如果原问题(P)的一个基本解的一个基本解X与对偶问题与对偶问题(D)的基可的基可 行解行解Y对应的检验数向量满足条件对应的检验数向量满
70、足条件 则称则称X为原问题为原问题(P)的的一个一个正则解正则解正则解正则解。求解原问题求解原问题(P)时，可以从时，可以从(P)的一个正则解开始的一个正则解开始，迭代到另一迭代到另一个正则解，使目标函数值增加，当迭代到正则解满足原始可个正则解，使目标函数值增加，当迭代到正则解满足原始可行性条件行性条件(即即xi0)时，就找到了原问题时，就找到了原问题(P)的最优解。的最优解。 这一方法称为对偶单纯形法这一方法称为对偶单纯形法这一方法称为对偶单纯形法这一方法称为对偶单纯形法对对 偶偶 单单 纯纯 形形 法法定义定义-96-China University of Mining and Techn
71、ology运筹学 原始单纯形法原始单纯形法对偶单纯形法对偶单纯形法前前提提条条件件所有所有bi 0所有所有检验数检验数0最最 优优 性性 检检 验验所有所有检验数检验数0？所有所有bi 0？换换 入入 、 出出 基基变变 量量 的的 确确 定定先确定换入基变量先确定换入基变量后确定换出基变量后确定换出基变量先确定换出基变量先确定换出基变量后确定换入基变量后确定换入基变量原原始始基基本本解解的的进进化化可行可行最优最优（对偶问题的解从（对偶问题的解从不可行到可行）不可行到可行）非可行非可行可行（最优）可行（最优）（原问题的解从不可行（原问题的解从不可行到可行）到可行）对对 偶偶 单单 纯纯 形形
72、 法法-97-China University of Mining and Technology运筹学 原问题解空间原问题解空间对偶问题解空间对偶问题解空间可行解可行解可行解可行解基本解基本解基本解基本解正则解正则解正则解正则解基可行解基可行解基可行解基可行解最优解最优解对对 偶偶 单单 纯纯 形形 法法-98-China University of Mining and Technology运筹学 对偶单纯法的迭代步骤：对偶单纯法的迭代步骤：对偶单纯法的迭代步骤：对偶单纯法的迭代步骤：（1）找一个正则基）找一个正则基B和初始正则解和初始正则解X(0)，将问题（将问题（P）化为化为关于基关于基
73、B的典式，列的典式，列初始对偶单纯形表初始对偶单纯形表.设正则解设正则解的典式为：的典式为：对对 偶偶 单单 纯纯 形形 法法-99-China University of Mining and Technology运筹学 将将上面的典式转换成前面所学习过的单纯形表：上面的典式转换成前面所学习过的单纯形表：（2）若）若, 则迭代停止，已求得原问题（则迭代停止，已求得原问题（P）的最优的最优解解;否则转下一步。否则转下一步。对对 偶偶 单单 纯纯 形形 法法-100-China University of Mining and Technology运筹学 则迭代停止，原问题无解；否则转下一步。则
74、迭代停止，原问题无解；否则转下一步。为换出变量。若为换出变量。若（3）确定换出变量：若）确定换出变量：若则取相应的变量则取相应的变量对对 偶偶 单单 纯纯 形形 法法-101-China University of Mining and Technology运筹学 （4）确定换入变量：若）确定换入变量：若则取则取x l 为换入变量。为换入变量。 以以正则解，返回正则解，返回（2）。为主元进行换基运算得为主元进行换基运算得到新的到新的对对 偶偶 单单 纯纯 形形 法法-102-China University of Mining and Technology运筹学 用对偶单纯形法计算用对偶单纯形
75、法计算解：为了便于解：为了便于寻找初始正则寻找初始正则解，将问题变解，将问题变形为：形为：取取x4,x5为初始正则为初始正则解，列单纯形表如下：解，列单纯形表如下：例例9对对 偶偶 单单 纯纯 形形 法法-103-China University of Mining and Technology运筹学 -2-3-400XBbx1x2x3x4x5x4-3-1-2-110x5-4-21-3010-2-3-4由于初始正则解有负分量，于是取由于初始正则解有负分量，于是取min-3,-4=-4x5为换出变量，取为换出变量，取x1为换入变量，得新基为换入变量，得新基x4,x1 ， 51= -2为主元为主元
76、对对 偶偶 单单 纯纯 形形 法法-104-China University of Mining and Technology运筹学 基变换的过程：基变换的过程：1.主元变为主元变为1，即用，即用-2去除单纯形表中基变量去除单纯形表中基变量x5所在的行；所在的行；2.主元所在列的其它元变为主元所在列的其它元变为0，消去非基变量，消去非基变量x1所在的列的所在的列的其余元其余元-1，-2；3.得新基得新基x4,x1的单纯形表的单纯形表-2-3-400XBbx1x2x3x4x5x4-3-1-2-110x5-4-21-3010-2-3-4对对 偶偶 单单 纯纯 形形 法法-105-China Uni
77、versity of Mining and Technology运筹学 基变换的过程：基变换的过程：-2-3-4XBbx1x2x3x4x5x4x1-2-3-400XBbx1x2x3x4x5x4-3-1-2-110x5-4-21-3010-2-3-421-1/23/20-1/2-10-5/21/21-1/240-4-10-1对对 偶偶 单单 纯纯 形形 法法-106-China University of Mining and Technology运筹学 -2-3-4XBbx1x2x3x4x5x4x121-1/23/20-1/2-10-5/21/21-1/240-4-10-1可见正则解的有负分量
78、，由于可见正则解的有负分量，由于x4=1 , 所以取所以取x4为换为换出变量，取出变量，取x2为换入变量，得新基为换入变量，得新基x2,x1 ， 42=-5/2为主元为主元对对 偶偶 单单 纯纯 形形 法法-107-China University of Mining and Technology运筹学 -2-3-4XBbx1x2x3x4x5x22/501-1/5-2/51/5x111/5107/5-1/5-2/528/500-3/5-8/5-1/5此时正则解是可行解，也是最优解。此时正则解是可行解，也是最优解。 X*=(11/5，2/5，0，0，0)；z*=-28/5进行基变换，得新正则解的
79、单纯形表：进行基变换，得新正则解的单纯形表：对对 偶偶 单单 纯纯 形形 法法-108-China University of Mining and Technology运筹学 例例10-109-China University of Mining and Technology运筹学 cjB-1b-120-5000cByBy1y2y3y40y3-50-4-2100y4-30-3-101j0-120-5000-120/-4-50/-2-50y22521-1/200y4-5-10-1/21j-1250-200-2502050-50y21501-3/22-120y15101/2-1j-135000-
80、15-20-110-China University of Mining and Technology运筹学 例例11-111-China University of Mining and Technology运筹学 cjB-1b23-5-M0cBxBx1x2x3x4x5-Mx471111070x5-10-25-101j-7MM+2M+3M-5003x27111100x5-45-70-6-51j21-10-7-M-301/77/6(M+3)/53x24/7011/72/71/72x145/7106/75/7-1/7j102/700-50/7-(M+16)/7-1/7-112-China Uni
81、versity of Mining and Technology运筹学 例例12-113-China University of Mining and Technology运筹学 cj3-1-100-MB-1bcBxBx1x2x3x4x5x60x41-2110011110x54-1-2010-3-Mx6-20100111j-6M+3-1M-1000-Mcj3-1-100-MB-1bcBxBx1x2x3x4x5x60x43-2010-1100x50-10012-1-1x3-2010011j1-1000-M+1-1-114-China University of Mining and Techno
82、logy运筹学 cj3-1-100-MB-1bcBxBx1x2x3x4x5x63x11001/3-2/3-5/34-1x20100-1-21-1x30012/3-4/3-7/39j000-1/3-1/3-M+2/32cj3-1-100-MB-1bcBxBx1x2x3x4x5x60x43001-2-512-1x20100-1-21-1x3-2010011j1000-1-M-1-2-115-China University of Mining and Technology运筹学 对偶单纯形法的迭代步骤中对偶单纯形法的迭代步骤中, ,如何找一个如何找一个初始正则解初始正则解？初始正则解的确定初始正则
83、解的确定初始正则解的确定初始正则解的确定标准形线性规划问题标准形线性规划问题选定的基选定的基B，不妨设不妨设对对 偶偶 单单 纯纯 形形 法法可行基可行基B的典式为的典式为右端常数中有负数，而检验数全非正，则基右端常数中有负数，而检验数全非正，则基B为正则为正则基，相应的基，相应的 解解为初为初始正则解，就可用对偶单纯形法求解。始正则解，就可用对偶单纯形法求解。否则，若出现正检否则，若出现正检验数，验数，X(0)就不是就不是正则解。正则解。-116-China University of Mining and Technology运筹学 为为此，此，求初始正则基和初始正则解，可增加一个约束条件
84、：求初始正则基和初始正则解，可增加一个约束条件：原问题原问题(P)的典式扩充为下列问题的典式扩充为下列问题:扩充问题：扩充问题：对对 偶偶 单单 纯纯 形形 法法非基变量非基变量充分大数充分大数-117-China University of Mining and Technology运筹学 u扩充问题的一个正则基和正则解是不难得到的。扩充问题的一个正则基和正则解是不难得到的。对对 偶偶 单单 纯纯 形形 法法u扩充问题的两种可能结果：扩充问题的两种可能结果：（1）若扩充问题无可行解，则原问题）若扩充问题无可行解，则原问题(P)也无可行解。也无可行解。（2）若扩充问题有最优解）若扩充问题有最优
85、解且目标函数最优值与且目标函数最优值与 M 无关无关,则有则有必为原问题必为原问题(P)的最优解。的最优解。-121-China University of Mining and Technology运筹学 对偶单纯形法的理论解释对偶单纯形法的理论解释对偶单纯形法的理论解释对偶单纯形法的理论解释对偶单纯形法所使用的表格与原单纯形法一样，可将典式对偶单纯形法所使用的表格与原单纯形法一样，可将典式中的数据放在原单纯形表上，即得到对偶单纯形表，中的数据放在原单纯形表上，即得到对偶单纯形表，所不所不同的是同的是这里保证在整个过程中这里保证在整个过程中不保证不保证,即右端常数中可以出现负数。即右端常数中
86、可以出现负数。对对 偶偶 单单 纯纯 形形 法法先定换出变量，再定换入变量。先定换出变量，再定换入变量。从本章起，不从本章起，不强调右端常数强调右端常数非负这个条件。非负这个条件。-129-China University of Mining and Technology运筹学 (1)用对偶单纯形法求解线性规划问题时，当约束条件为用对偶单纯形法求解线性规划问题时，当约束条件为“”时，不必引进人工变量，使计算简化。时，不必引进人工变量，使计算简化。(2)当线性规划问题中变量多于约束条件时，用对偶单纯形法当线性规划问题中变量多于约束条件时，用对偶单纯形法计算可以减少工作量。计算可以减少工作量。(3
87、)对偶单纯形法应用于主要应用于灵敏度分析及整数规划等对偶单纯形法应用于主要应用于灵敏度分析及整数规划等有关章节中。有关章节中。(4)对偶单纯形法的对偶单纯形法的局限性局限性主要是：对大多数线性规划问题，主要是：对大多数线性规划问题，很难找到一个初始正则解。因此对偶单纯形法一般不单独很难找到一个初始正则解。因此对偶单纯形法一般不单独使用。使用。对偶单纯形法的优缺点：对偶单纯形法的优缺点：对偶单纯形法的优缺点：对偶单纯形法的优缺点：对对 偶偶 单单 纯纯 形形 法法-130-China University of Mining and Technology运筹学 2 2. .7 7 灵灵敏敏度度分
88、分析析-131-China University of Mining and Technology运筹学 灵敏度分析灵敏度分析= =对于市场的变化，我们的决策究竟怎样变化对于市场的变化，我们的决策究竟怎样变化 （不需要将它当成一个新问题）（不需要将它当成一个新问题）灵敏度分析的重要性在于：灵敏度分析的重要性在于：1. 向决策者提供线性规划问题的最优解所能适应的环境向决策者提供线性规划问题的最优解所能适应的环境条件变化的范围；条件变化的范围；2. 环境条件变化时可能对经营状况带来何种影响；环境条件变化时可能对经营状况带来何种影响；3. 产生影响后的解决途径。产生影响后的解决途径。灵灵 敏敏 度度
89、 分分 析析-132-China University of Mining and Technology运筹学 灵敏度分析的类型：灵敏度分析的类型：1. 模型中各个参数在什么范围变化时，最优基不发生改变。模型中各个参数在什么范围变化时，最优基不发生改变。2. 模型中参数变化已经超出上述范围时，如何快速确定新的最模型中参数变化已经超出上述范围时，如何快速确定新的最优基和最优解优基和最优解新的最优决策方案。新的最优决策方案。模型中参数变化主要指：模型中参数变化主要指：1. 目标函数的系数变化；目标函数的系数变化；2. 约束条件右边的值变化；约束条件右边的值变化；3. 约束条件中约束条件中aij 的
90、的变化；变化；4. 可决策变量增减的变化；可决策变量增减的变化；5. 约束条件增减的变化。约束条件增减的变化。 灵灵 敏敏 度度 分分 析析-133-China University of Mining and Technology运筹学 灵敏度分析的任务：灵敏度分析的任务：1.当当系系数数A、b、C中中的的某某个个发发生生变变化化时时,目目前前的的最最优优基基是是否否仍仍最最优优（即即目目前前的的最最优优生生产产方方案案是是否否要要变变化化）?(称称为为模模型型参参数数的的灵灵敏度分析敏度分析)2.增增加加一一个个变变量量或或增增加加一一个个约约束束条条件件时时，目目前前的的最最优优基基是是
91、否否仍仍最最优优（即即目目前前的的最最优优生生产产方方案案是是否否要要变变化化）？(称称为为模模型型结结构构的灵敏度分析的灵敏度分析) 灵灵 敏敏 度度 分分 析析-134-China University of Mining and Technology运筹学 线性规划问题线性规划问题 I 表与表与 B 表的关系表的关系对给定符合典式的线性规划问题中，初始基矩阵为对给定符合典式的线性规划问题中，初始基矩阵为 I ，基变量为基变量为 XS ，即松即松弛变量。其对应的初始单纯形表如下：弛变量。其对应的初始单纯形表如下： I 表（初始表）表（初始表）对初始单纯形表进行迭代之后得到对初始单纯形表进行
92、迭代之后得到 B 为最优基矩阵，最终典式所对应的单纯为最优基矩阵，最终典式所对应的单纯形表：形表： B 表（最终表）表（最终表）基基解解 X XS XSb A I j C 0 基基解解 XB XN XS XBB -1b I B -1N B -1 j 0 CN CB B -1N - CB B -1 灵灵 敏敏 度度 分分 析析-135-China University of Mining and Technology运筹学 原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解非可行解非可行解非可行解非可行解可行解可行解非可行解非可行解可行解可行解非可行解非
93、可行解问题的最优解或最优基不变问题的最优解或最优基不变可以用单纯形法继续迭代求最优解可以用单纯形法继续迭代求最优解可以用对偶单纯形法继续迭代求最优解可以用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重新计算引进人工变量，编制新的单纯形表重新计算线性规划原问题单纯形法对应的线性规划原问题单纯形法对应的 I 表表中中参数的变化将引起参数的变化将引起B 表表中中对应对应参数的变化情况如下：参数的变化情况如下：灵灵 敏敏 度度 分分 析析基基解解X XS XSbA I j C 0 基基解解XB XN XS XBB -1b I B -1N B -1 j 0 CN CB B -1N - CB
94、 B -1 I 表（初始表）表（初始表）B 表（最终表）表（最终表）-136-China University of Mining and Technology运筹学 灵敏度分析的方法：灵敏度分析的方法： 灵敏度分析方法的关键是从单纯形法对应的灵敏度分析方法的关键是从单纯形法对应的 I 表表中中参参数的变化来分析数的变化来分析B 表表中中对应参数的变化情况来回答决策者对应参数的变化情况来回答决策者所关心问题。所关心问题。 灵敏度分析的方法是在目前最优基灵敏度分析的方法是在目前最优基B下进行的。即当下进行的。即当参数参数A、b、c中的某一个或几个发生变化时，考察是否影中的某一个或几个发生变化时，
95、考察是否影响以下两式的成立？响以下两式的成立？ 灵灵 敏敏 度度 分分 析析-137-China University of Mining and Technology运筹学 1. 对于参数对于参数b的灵敏度分析的灵敏度分析基基解解 XB XN XS XSb B N I j CB CN 0基基解解 XB XN XS XBB-1b I B -1N B -1 j 0 CN CB B -1 - CB B -1I 表表B 表表当当I 表表中中b变化为变化为b时，在时，在B 表中将只有解列表中将只有解列 B-1b发生变化。发生变化。灵灵 敏敏 度度 分分 析析-138-China University
96、of Mining and Technology运筹学 bXXBB-1bB-1AZC BB-1bC-C BB-1Ab变化的时候，仅对变化的时候，仅对B-1b有影响有影响仅关心仅关心B-1b0?若新的若新的B-1b不满足不满足0，最优基发生，最优基发生变化，此时需用对偶单纯形法进行变化，此时需用对偶单纯形法进行计算，调整可行性可能计算，调整可行性可能当当B-1b0时，最优基不变（即时，最优基不变（即生产产品的品种不变，但数量生产产品的品种不变，但数量及最优值会变化），此时可以及最优值会变化），此时可以简单求出新最优解。简单求出新最优解。所以，所以，b的变化只影响最优解的变化和最优值的变化。的变化
97、只影响最优解的变化和最优值的变化。灵灵 敏敏 度度 分分 析析-139-China University of Mining and Technology运筹学 若若B-1b0，其，其是一个不等式组，从中可以解得是一个不等式组，从中可以解得b的变化范围的变化范围（此时，需保证当前最优基变化后仍为最优基）（此时，需保证当前最优基变化后仍为最优基）若若B-1b中有小于中有小于0的分量，则需用对偶单纯形法迭代，以求出的分量，则需用对偶单纯形法迭代，以求出新的最优方案新的最优方案。（此时，基变量不变，因为（此时，基变量不变，因为基变量只需要相应的基变量只需要相应的B可逆可逆就可以了就可以了）bXXBB
98、-1bB-1AZC BB-1bC-C BB-1A灵灵 敏敏 度度 分分 析析-140-China University of Mining and Technology运筹学 I 表表Cj21000CB基基解解X1X2X3X4X50X315051000X424620100X5511001检验数检验数 j21000B 表表Cj21000CB基基解解X1X2X3X4X50X315/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2检验数检验数 j000-1/4-1/2灵灵 敏敏 度度 分分 析析-141-China University of Mining a
99、nd Technology运筹学 若若b2增加到增加到30，最优解如何变化？，最优解如何变化？最优基不变，最优解变为（最优基不变，最优解变为（5，0，15，0，0）。）。灵灵 敏敏 度度 分分 析析-142-China University of Mining and Technology运筹学 I 表表Cj21000CB基基解解X1X2X3X4X50X315051000X424620100X5511001检验数检验数 j21000B 表表Cj21000CB基基解解X1X2X3X4X50X315/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2检验数检验
100、数 j000-1/4-1/2灵灵 敏敏 度度 分分 析析-143-China University of Mining and Technology运筹学 若若b2增加到增加到32，最优解如何变化？，最优解如何变化？最优基发生变化，用对偶单纯形法求解。最优基发生变化，用对偶单纯形法求解。灵灵 敏敏 度度 分分 析析-144-China University of Mining and Technology运筹学 B 表表Cj21000CB基基解解X1X2X3X4X50X315051002X15110010X420-401-6检验数检验数 j0-100-2B 表表Cj21000CB基基解解X1X
101、2X3X4X50X335/20015/4-15/22X111/21001/4-1/21X2-1/2010-1/43/2检验数检验数 j000-1/4-1/2灵灵 敏敏 度度 分分 析析-145-China University of Mining and Technology运筹学 已知某生产计划问题的数学模型，为使最优方案不变，已知某生产计划问题的数学模型，为使最优方案不变，试讨论第二个约束条件试讨论第二个约束条件b2的变化范围。的变化范围。 cj 4 3 0 0 CBXBb x1 x2 x3 x4 34x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5 Z36 0 0 1/5
102、 6/5 解：生产计划问题的数学模型和最优单纯形表为：解：生产计划问题的数学模型和最优单纯形表为：灵灵 敏敏 度度 分分 析析-146-China University of Mining and Technology运筹学 从矩阵形式的单纯形表中可知，从矩阵形式的单纯形表中可知，b2的变化只影响解的可行性的变化只影响解的可行性B-1b0，因此，为使最优解不变，只需变化以后的，因此，为使最优解不变，只需变化以后的B-1b0即可。即可。由由解得：解得：当数据量十分当数据量十分大的时候，十大的时候，十分麻烦分麻烦写为写为B-1(24,26)+B-1b灵灵 敏敏 度度 分分 析析-147-China
103、 University of Mining and Technology运筹学 若若b2变化超过范围，则需用对偶单纯形法进行求解。如变化超过范围，则需用对偶单纯形法进行求解。如b2=6，则则 cj 4 3 0 0 CBXBb x1 x2 x3 x4 34x2x112-6 0 1 3/5 -2/5 1 0 -2/5 3/5 Z12 0 0 1/5 6/5 将上述数字替换最优单纯形表中相应位置的数据得：将上述数字替换最优单纯形表中相应位置的数据得：灵灵 敏敏 度度 分分 析析-148-China University of Mining and Technology运筹学 cj 4 3 0 0 C
104、BXBb x1 x2 x3 x4 30x2x3315 3/2 1 0 1/2 -5/2 0 1 -3/2 Z9 1/2 0 0 3/2 用对偶单纯形法迭代，求出的最优单纯形表如下：用对偶单纯形法迭代，求出的最优单纯形表如下：得到新的最优解为：得到新的最优解为：x1=0，x2=3; max z=9灵灵 敏敏 度度 分分 析析-149-China University of Mining and Technology运筹学 当当 Cj 是非基变量是非基变量 X 的的目标系数目标系数时，若要保持最优解（或基）不时，若要保持最优解（或基）不变，则必须满足：变，则必须满足：CN CB B -1N 0基基
105、 解解 XB XN XS XSb B N I j CB CN 0基基解解 XB XN XS XBB -1b I B -1N B -1 j 0 CN CB B -1N - CB B -1I 表表B 表表2.对价值系数对价值系数Cj变化的分析变化的分析(1)当当 Cj 变化使得非基变变化使得非基变量的量的Cj Zj 0，即最优即最优解（或基）发生变化，解（或基）发生变化，则在原单纯形表的基则在原单纯形表的基础上，继续求解模型。础上，继续求解模型。灵灵 敏敏 度度 分分 析析-150-China University of Mining and Technology运筹学 max z = 2x1 +
106、 x2 5x2 15s.t. 6x1 + 2x2 24 x1 + x2 5 x1 ，x2 0I 表表Cj21000CB基基解解X1X2X3X4X50X315051000X424620100X5511001检验数检验数 j21000灵灵 敏敏 度度 分分 析析-151-China University of Mining and Technology运筹学 B 表表Cj21000CB基基解解X1X2X3X4X50X315/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2检验数检验数 j000-1/4-1/2B 表表CjC11000CB基基解解X1X2X3X
107、4X50X315/20015/4-15/2C1X17/21001/4-1/21X23/2010-1/43/2检验数检验数 j0001/4-C1/4C1/2-3/2若要使最优解保持不变，求若要使最优解保持不变，求x1的价值系数变化范围。的价值系数变化范围。灵灵 敏敏 度度 分分 析析-152-China University of Mining and Technology运筹学 因此：因此：当当CN（非非基基变变量量的的目目标标函函数数系系数数）中中某某个个Cj发发生生变变化化时时，只影响到非基变量只影响到非基变量xj的检验数的检验数 最优解改变，需要用单纯形法重新进行迭代，以最优解改变，需要
108、用单纯形法重新进行迭代，以求得新的最优解。求得新的最优解。最优解不变（最小值）最优解不变（最小值）灵灵 敏敏 度度 分分 析析-153-China University of Mining and Technology运筹学 对于下列线性规划模型对于下列线性规划模型,为使最优解不变，讨论非基变量为使最优解不变，讨论非基变量y1的目标函数系数的目标函数系数c3的变化范围。的变化范围。用单纯形法求得其最优表为：用单纯形法求得其最优表为： cj 4 3 2 0 0 CBXBb x1 x2 y1 x3 x4 34x2x146 0 1 -1/5 3/5 -2/5 1 0 4/5 -2/5 3/5 Z36
109、 0 0 3/5 1/5 6/5 灵灵 敏敏 度度 分分 析析-154-China University of Mining and Technology运筹学 解：因为解：因为y1为非基变量，其目标函数系数为非基变量，其目标函数系数c3的变化只会影响到的变化只会影响到y1的检验数，因此为使最优解不变，只需的检验数，因此为使最优解不变，只需即即若若C3=3，则，则代入最优单纯形表中相应位置代入最优单纯形表中相应位置继续迭代以求出新的最优解。继续迭代以求出新的最优解。 cj4 3 2 0 0 CBXBbx1 x2 y1 x3 x4 34x2x146 0 1 -1/5 3/5 -2/5 1 0 4
110、/5 -2/5 3/5 Z36 0 0 -2/5 1/5 6/5 灵灵 敏敏 度度 分分 析析-155-China University of Mining and Technology运筹学 当当 Cj 变化使得非基变变化使得非基变量的量的Cj Zj 0，即最优即最优解（或基）发生变化，解（或基）发生变化，则在原单纯形表的基则在原单纯形表的基础上，继续求解模型。础上，继续求解模型。当当 Ci 是基变量是基变量 Xi 的的目标系数目标系数时，若要保持最优解（或基）时，若要保持最优解（或基）不变，则必须满足：不变，则必须满足：CN CB B 1N 0 - CB B -1 0基基解解 XB XN
111、XS XSb B N I j CB CN 0基基解解 XB XN XS XBB -1b I B -1N B -1 j 0 CN CB B -1N - CB B -1I 表表B 表表2.对价值系数对价值系数Cj变化的分析变化的分析(2)灵灵 敏敏 度度 分分 析析-156-China University of Mining and Technology运筹学 在上题中，设基变量在上题中，设基变量x1的系数的系数C1变化为变化为C1+C1 ，在最优性不，在最优性不变的条件下，试确定变的条件下，试确定C1的范围的范围解：解：因此：因此：当当CB（基变量的目标函数系数）中某个（基变量的目标函数系数）
112、中某个Cj发生变化时，会影响发生变化时，会影响到所有变量的检验数，解不等式组到所有变量的检验数，解不等式组灵灵 敏敏 度度 分分 析析-157-China University of Mining and Technology运筹学 将上述数字替换单纯形表中相应位置的数字得：将上述数字替换单纯形表中相应位置的数字得： cj 4 3 0 0 CBXBb x1 x2 x3 x4 35x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5 Z42 0 0 -1/5 8/5 灵灵 敏敏 度度 分分 析析-158-China University of Mining and Technolog
113、y运筹学 用单纯形法迭代得最优解表如下：用单纯形法迭代得最优解表如下： cj 4 3 0 0 CBXBb x1 x2 x3 x4 05x3x120/326/3 0 5/3 1 -2/3 1 2/3 0 1/3 Z130/3 0 1/3 0 16/15 灵灵 敏敏 度度 分分 析析-159-China University of Mining and Technology运筹学 第一种情况（当第一种情况（当j JN）：即）：即aij为非基变量为非基变量xj的技术系数时，它的的技术系数时，它的变化只影响变化只影响xj的系数列的系数列B-1Pj和检验数和检验数j，为使最优方案不变，只需，为使最优方案
114、不变，只需j 0。3.对技术系数对技术系数aij变化的分析变化的分析第第二二种种情情况况（当当j JB）：由由于于B中中元元素素的的改改变变影影响响到到B-1的的变变化化，因因此此也也影影响响到到整整个个单单纯纯形形表表T(B)的的变变化化。目目前前的的基基B对对应应的的解解有有可能既不是原始可行，也不是对偶可行。于是不如重新求解。可能既不是原始可行，也不是对偶可行。于是不如重新求解。灵灵 敏敏 度度 分分 析析-160-China University of Mining and Technology运筹学 cj 4 3 2 0 0 CBXBb x1 x2 y1 x3 x4 34x2x146
115、 0 1 -1/5 3/5 -2/5 1 0 4/5 -2/5 3/5 Z36 0 0 3/5 1/5 6/5 对于下列规划问题的最优解，若由于工艺改进，对于下列规划问题的最优解，若由于工艺改进，y1的技术系数改为的技术系数改为p3=(1,1)T，试讨论最优解的变化。，试讨论最优解的变化。解：解：最优解改变。此时其系数列改为：最优解改变。此时其系数列改为：灵灵 敏敏 度度 分分 析析-161-China University of Mining and Technology运筹学 将上述数据替换最优表中相应位置的数据，然后再用单纯形法将上述数据替换最优表中相应位置的数据，然后再用单纯形法求得新
116、的最优解。求得新的最优解。 cj 4 3 2 0 0 CBXBb x1 x2 y1 x3 x4 34x2x146 0 1 1/5 3/5 -2/5 1 0 1/5 -2/5 3/5 Z36 0 0 -3/5 1/5 6/5 灵灵 敏敏 度度 分分 析析-162-China University of Mining and Technology运筹学 设某企业在计划期内，拟议生产新产品设某企业在计划期内，拟议生产新产品Xn+1，并已知新产品的，并已知新产品的单位利润为单位利润为Cn+1，消耗系数向量为，消耗系数向量为Pn+1=(a1,n+1,a2,n+1,am,n+1)T，此，此时应如何分析才能
117、确定该新产品是否值得投产？时应如何分析才能确定该新产品是否值得投产？ 增加新产品应在不影响企业目前计划期内最优生产的前提下增加新产品应在不影响企业目前计划期内最优生产的前提下进行。因此可从现行的最优基进行。因此可从现行的最优基B出发考虑：出发考虑：若若n+1=CBB-1Pn+1Cn+10，则不应投入则不应投入。 即新产品的机会成本小于目前的市场价格时，应投产否则不即新产品的机会成本小于目前的市场价格时，应投产否则不应投产。应投产。4.对增加新产品的分析对增加新产品的分析灵灵 敏敏 度度 分分 析析-163-China University of Mining and Technology运筹学
118、 现有一新产品丙，经预测其单位利润为现有一新产品丙，经预测其单位利润为3，技术消，技术消耗系数为耗系数为P5=（2，2）T，问该产品是否值得投产？，问该产品是否值得投产？解：解：值得投产。值得投产。其系数列为：其系数列为：灵灵 敏敏 度度 分分 析析-164-China University of Mining and Technology运筹学 cj 4 3 0 0 3CBXBb x1 x2 x3 x4 y5 34x2x146 0 1 3/5 -2/5 2/5 1 0 -2/5 3/5 2/5 Z36 0 0 1/5 6/5 -1/5将此变量加入最优单纯形表中得：将此变量加入最优单纯形表中得
119、：用单纯形法迭代求得最优解为：用单纯形法迭代求得最优解为： cj 4 3 0 0 3CBXBb x1 x2 x3 x4 y5 34y5x1102 0 5/2 3/2 -1 1 1 -1 -1 1 0 Z38 0 1/2 1/2 1 0灵灵 敏敏 度度 分分 析析-165-China University of Mining and Technology运筹学 在企业生产过程中，经常有新情况发生，造成原本不紧缺的某种资源在企业生产过程中，经常有新情况发生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响，如水、电和资源的供应不足等，对变成为紧缺资源，对生产计划造成影响，如水、电和资源的
120、供应不足等，对生产过程提出了新约束等。生产过程提出了新约束等。 对增加新约束条件的分析方法步骤是：对增加新约束条件的分析方法步骤是： 第第一一步步：将将目目前前的的最最优优解解代代入入新新增增加加的的约约束束，若若能能满满足足约约束束条条件件，则则说说明明新新增增约约束束对对目目前前的的最最优优解解（即即最最优优生生产产方方案案）不不构构成成影影响响（称称此此约约束束为为不不起作用约束），可暂时不考虑新增约束条件。否则转下一步；起作用约束），可暂时不考虑新增约束条件。否则转下一步； 第第二二步步：把把新新增增约约束束添添加加到到原原问问题题最最终终表表中中，并并作作初初等等行行变变换换，构构成成对对偶可行的单纯形表，并用对偶单纯形法迭代，求出新的最优解。偶可行的单纯形表，并用对偶单纯形法迭代，求出新的最优解。5.对增加新约束条件的分析对增加新约束条件的分析灵灵 敏敏 度度 分分 析析
