1、学习目标理解对偶问题的基本理论；掌握对偶问题的经济解释影子价格；理解对偶单纯性法；掌握灵敏度分析第三章对偶问题与灵敏度分析原始的角度原始的角度对偶的角度对偶的角度例例唉唉!我想租您的木工和油漆工一我想租您的木工和油漆工一用。咋样？价格嘛用。咋样？价格嘛好说，好说，肯定不会让您兄弟吃亏讪。肯定不会让您兄弟吃亏讪。 王老板做家具赚了王老板做家具赚了 大钱，虽然我也想做家具大钱，虽然我也想做家具生意，却苦于没有生意，却苦于没有足够的木工和油漆工足够的木工和油漆工 咋办？只有租咯。咋办？只有租咯。Hi：王老板，听说：王老板，听说近来家具生意好惨了，近来家具生意好惨了，也帮帮兄弟我哦也帮帮兄弟我哦! 家
2、具生意还真赚钱，但家具生意还真赚钱，但 是现在的手机生意这么好，是现在的手机生意这么好， 不如干脆把我的木工和油漆不如干脆把我的木工和油漆工租给他，又能工租给他，又能收租金又可做生意。收租金又可做生意。价格嘛价格嘛好商量，好商量， 好商量。只是好商量。只是. 王王 老老 板板李李 老老 板板王老板的王老板的家具生产模型家具生产模型：x1 、 x2是桌、椅生产量。是桌、椅生产量。Z是家具销售总收入（总利润）。是家具销售总收入（总利润）。max Z = 50 x1 + 30 x2s.t. 4x1+3x2 120（木工）木工） 2x1+ x2 50 （油漆工）（油漆工） x1，x2 0原始线性规划问
3、题，记为（原始线性规划问题，记为（P）王老板的王老板的资源出租模型资源出租模型：y1、 y2单位木、漆工出租价格。单位木、漆工出租价格。W是资源出租租金总收入。是资源出租租金总收入。min W =120y1 + 50y2s.t. 4y1+2y2 50 3y1+ y2 30 y1，y2 0对偶线性规划问题，记为（对偶线性规划问题，记为（D）王老板按（王老板按（D）的解）的解 y1 、y2出租其拥有的木、漆工资源，既保证了自出租其拥有的木、漆工资源，既保证了自己不吃亏己不吃亏(出租资源的租金收入并不低于自己生产时的销售收入出租资源的租金收入并不低于自己生产时的销售收入)，又使，又使得出租价格对李老
4、板有极大的吸引力得出租价格对李老板有极大的吸引力(李老板所付出的总租金李老板所付出的总租金W最少最少).对偶问题min W=bTYs.t. ATYC Y 0minCATbTbACTmaxnmnm项目项目原问题原问题对偶问题对偶问题AbC目标函数目标函数约束条件约束条件决策变量决策变量约束系数矩阵约束系数矩阵约束条件的右端项向量约束条件的右端项向量目标函数中的价格系数向量目标函数中的价格系数向量max Z = CTXAX bX 0其约束系数矩阵的转置其约束系数矩阵的转置目标函数中的价格系数向量目标函数中的价格系数向量约束条件的右端项向量约束条件的右端项向量min W = bTYATY CY 0对
5、偶问题为min w=2y1+3y2-y3s.t. y1+2y2+y36 2y1-3y2+2y39 y1, y2, y30根据定义，原始问题为max z=6x1+9x2s.t. x1+2x22 2x1- 3x23 x1+2x2-1 x1, x20对偶问题是极小化问题对偶问题的约束全为对偶问题有3个变量，2个约束对偶问题的变量全部为非负原始问题是极大化问题原始问题的约束全为原始问题有2个变量，3个约束原始问题的变量全部为非负对偶问题变量的个数(3)等于原始问题约束条件的个数(3)对偶问题约束条件的个数(2)等于原始问题变量的个数(2)max z=2x1+x2-3x3s.t. x1-3x2+2x3-
6、 5x4 6 4x1+x2- 5x3+2x4 9 -x1+2x2 +x4 12 x1, x2, x3, x4 0原始问题有4个变量，3个约束，对偶问题应该有3个变量，4个约束。根据定义，对偶问题为：y1y2y3min w=6y1+9y2+12y3s.t. y1+4y2- y3 2 -3y1+ y2+2y3 1 2y1-5y2 -3 -5y1+2y2+ y3 0 y1, y2, y3 0 x1x2x3x4max z=2x1+3x2-x3s.t. x1+2x2+x3=6 2x1-3x2+2x39 x1, x2, x30max z=2x1+3x2-x3s.t. x1+2x2+x36 x1+2x2+x
7、36 2x1-3x2+2x39 x1, x2, x30max z=2x1+3x2-x3s.t. -x1-2x2-x3 -6 x1+2x2 +x3 6 2x1-3x2+2x39 x1, x2, x30min w=-6w1+6w2+9w3s.t. -w1+w2+2w3 2 -2w1+2w2-3w3 3 -w1+w2+2w3 -1 w1, w2, w30min w=6(w2-w1)+9w3s.t. (w2-w1)+2w3 2 2(w2-w1)-3w3 3 (w2-w1)+2w3 -1 w1, w2, w30min w=6y1+9y2s.t. y1+2y2 2 2y1- 3y2 3 y1+2y2 -1
8、 y1:Free y20y1=w2-w1,y1:Free,y2=w3如果原始问题中一个约束是等号约束，则对偶问题中相应的变量没有符号限制非对称形式的对偶原始问题有“=”约束非对称形式的对偶原始问题有“”约束max z=2x1+3x2-x3s.t. x1+2x2+x3 6 2x1-3x2+2x39 x1, x2, x30max z=2x1+3x2-x3s.t. -x1-2x2-x3-6 2x1-3x2+2x39 x1, x2, x30min w=-6y1+9y2s.t. -y1+2y22 -2y1 -3y23 -y1+2y2-1 y1, y20min w=6y1+9y2s.t. y1+2y22
9、2y1- 3y23 y1+2y2-1 y10, y20y1=-y1, y10如果极大化原始问题中一个约束是“”约束，则对偶问题中相应的变量0非对称形式的对偶总结原始问题约束条件的性质，影响对偶问题变量的性质。原始问题变量的性质，影响对偶问题约束条件的性质。min w=bTYs.t. ATYC Y 0min w=bTYs.t. ATYC Y :Freemin w=bTYs.t. ATYC Y 0项目项目原问题原问题对偶问题对偶问题目标函数类型目标函数类型maxmin目标函数系数与右边项目标函数系数与右边项的对应关系的对应关系目标函数各变量系数对应目标函数各变量系数对应约束条件右边项的系数约束条件
10、右边项的系数右边项的系数对应目标右边项的系数对应目标函数系数函数系数变量个数与约束条件个变量个数与约束条件个数的对应关系数的对应关系变量个数变量个数 n约束条件个数约束条件个数 m约束条件个数约束条件个数 n变量个数变量个数 m原问题变量类型与对偶原问题变量类型与对偶问题约束条件类型的对问题约束条件类型的对应关系应关系 0变量类型变量类型 0 无限制无限制 约束条件类型约束条件类型 =原问题约束条件类型与原问题约束条件类型与对偶问题变量类型的对对偶问题变量类型的对应关系应关系 约束条件类型约束条件类型 = 0 变量类型变量类型 0 无限制无限制max z=2x1+x2-3x3s.t. x1-3
11、x2+2x3- 5x46 4x1+x2- 5x3+2x4 9 -x1+2x2 +x4 12 x1, x2 0, x3Free, x4 0写对偶问题的练习（1）min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max y=6w1+12w2+8w3+15w4s.t. 3w1- w2+2w3+ w4 2 -w1+2w2+ w3+3w4 4 2w1- 3w2+2w3- w4 -1 w1 0,w2 ,w3 0,w4 0=Free=x10 x20 x3: Freep原始问题变量的个数(3)等于对偶问题约束
12、条件的个数(3)；p原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。p原始问题变量的性质影响对偶问题约束条件的性质。p原始问题约束条件的性质影响对偶问题变量的性质。写对偶问题的练习（2）对偶问题的性质总结1、对偶的对偶就是原始问题对偶的定义min w=bTYs.t. ATYCY 0对偶的定义max w=-bTYs.t. -ATY-CY 02、两个问题的可行解对应的目标函数值互为上下界例：min z=2x1+3x2s.t. x1+3x23 2x1+x2 4 x1, x2 0max w=3y1+4y2s.t. y1+2y22 3y1+y2 3 y1, y2 00 1 2 34321A(3
13、,0)B(1.8,0.4)C(0,4)D(2,2)3210 1 2A(1,0)B(1.9,0.4)C(0,1)O(0,0)3、若原问题解无界，则其对偶问题无可行解。4、两个问题最优解的目标函数值必相等。5、两个问题都有可行解时则两个问题必都有最优解。6、两个问题最优解中，一个问题中某个变量取值非零，则该变量在对偶问题中对应的约束条件必为紧约束；反之，如果约束条件为松约束，则其对应的对偶变量一定取值为零。互补松弛性定理互补松弛关系的分量表示onojo2o1OxxxxXomnoino2no1nOSxxxxX12ooOoiomyyYyy 12omomOSomjom nyyYyy 互补松弛关系的分量表
14、示121210omomnOTOooooooSjnjm jojm jom nyyXYxxxxx yyy121210ononmOTOooooooSimin ioin ion mxxYXyyyyy xxx互补松弛关系的分量表示0000112210noooooojm jmmjm jnm njx yx yx yx yx y112210mooooooooooin innin imn miy xy xy xy xy x由于原始问题和对偶问题的所有变量和松弛变量都是非负的，因此以上两式中的每一项都等于0。即001,2,01,2,ojm jooin ix yjny xim在原始问题和对偶问题的最优解中，原始问题
15、的一个变量和对偶问题相应的松弛变量，对偶问题的一个变量和原始问题相应的松弛变量，组成互补松弛对，在每一对变量中，其中一个大于0，另一个一定等于0。互补松弛关系的分量形式 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=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0互补松弛关系的分量表示利用互补松弛关系求解线性规划min z=6x1+8x2+3x3s.t. x1+ x2 1 x1+2x2+x3
16、 -1 x1, x2, x3 0max w=y1-y2s.t. y1+ y2 6 y1+2y2 8 y2 3 y1, y20原始问题对偶问题0 1 2 3 4 5 6 7 8654321y1y2w=-1 w=1w=3w=6最优解为(y1, y2)=(6, 0)max w=6先用图解法求解对偶问题。min z=6x1+8x2+3x3s.t. x1+ x2 1 x1+2x2+x3 -1 x1, x2, x3 0max w=y1-y2s.t. y1+ y2 6 y1+2y2 8 y2 3 y1, y20max w=y1-y2s.t. y1+y2+y3 =6 y1+2y2 +y4 =8 y2 +y5=
17、3 y1, y2, y3, y4, y50(y1, y2)=(6,0)(y1,y2,y3,y4,y5)=(6, 0, 0, 2, 3)min z=6x1+8x2+3x3s.t. x1+ x2 -x4 =1 x1+2x2+x3 -x5 =-1 x1, x2, x3 ,x4, x50(x1, x2, x3 | x4, x5)(y1, y2 | y3, y4, y5)x2=x3=x4=0 x1=1, x5=2引进松弛变量 求对偶引进松弛变量图解法求解代入约束求出松弛变量互补松弛关系代入约束求解(x1, x2, x3, x4, x5)=(1, 0, 0, 0, 2)对偶问题解的经济解释影子价格0 xx
18、xxxxbxxaxaxabxxaxaxabxxaxaxa. t . sxcxcxczmaxmn2n1nn21mmnnmn22m11m22nnn222212111nnn1212111nn2211原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）对偶问题112211121211112122222211221212min. .0mmmmmmmmnnmnmm nnmmmm nwb yb yb ysta ya ya yyca ya yayyca ya yayycyyyyyy 资源限量（吨）资源价格
19、（元/吨）总租金（元）对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格（Shadow Price）原始和对偶问题都取得最优解时，最大利润 max z=min y资源的影子价格(Shadow Price)ooiizyibi最大利润的增量第 种资源的边际利润第 种资源的增量1122iimmzwb yb yb yb y1122()iiimmzzb yb ybb yb y iizb y 对偶问题解中变量 yio 的经济含义经济含义是在其他条件不变的情况下，在其他条件不变的情况下，单位第单位第i种种“资源资源”变化所引起的目标函数最优值的变化变化所引起的目标函数最优值的
20、变化。所以， yi o描述了原始线性规划问题达到最优时最优时（各种“资源”都处于最优最优的配置时），第 i 种“资源”的某种“价值”，故称其为第 i 种“资源”的影子价格影子价格.影子价格的特点 影子价格是对偶解的一个十分形象的名称，它既表明对偶解是对系统内部资源在当前的最优利用配置下的一种客观估价，又表明它是一种虚拟的价格（或价值的影象）而不是真实的价格。 特点1、影子价格是对系统资源的一种内部最优估价，只有当系统达到最优状态时才可能赋予资源这种价值。 特点2、系统资源的一种动态价格体系，影子价格的大小与系统的价值取向有关，并受系统状态变化的影响。系统环境的任何变化都可能会引起影子价格的变化
21、。影子价格的特点 特点3、影子价格的大小客观地反映资源在系统内的稀缺程度。如果某种资源在系统内供大于求，尽管它有实实在在的市场价格，但它在系统内的影子价格却为零，而影子价格越高，资源在系统内越稀缺。 特点4、影子价格是一种边际价值，其与经济学中的边际成本的概念相同。因而，在经济管理中有十分重要的应用价值。企业管理者可以根据资源在企业内部的影子价格的大小决定企业的经营策略。 特点5、对偶解准确的经济意义与线性规划模型的构造方法有关，模型构造方法的不同有时会导致对偶解的不同经济解释。y1y2ym产品的机会成本(Opportunity Cost)产品j的机会成本：表示减少一件产品所节省的所有资源可以
22、增加的利润1122jjijimjma ya ya ya y增加单位资源可以增加的利润减少一件产品的产量可以节省的资源0 xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211机会成本利润差额成本产品的差额成本（Reduced Cost）ym+j=(ai1y1+ai2y2+.aimym)-cj产品的差额成本产品的机会成本产品的利润1 12211 121211112122222211221212min. .0mmmmmmmmnnmnmm nnmmmm nwb
23、 yb yb ysta ya ya yyca ya yayyca ya yayycyyyyyy 0 xxxxxxbxxaxaxabxxaxaxabxxaxaxa. t . sxcxcxczmaxmn2n1nn21mmnnmn22m11m22nnn222212111nnn1212111nn2211112211121211112122222211221212min. .0mmmmmmmmnnmnmm nnmmmm nwb yb yb ysta ya ya yyca ya yayyca ya yayycyyyyyy 原始问题和对偶问题的经济解释总结资源占用（吨）资源剩余（吨）资源总量（吨）产品的机会
24、成本（元/件）产品的差额成本（元/件）产品的利润（元/件）产品的产量（件）资源的影子价格（元/吨）互补松弛关系的经济解释yixn+i=0如果yi0，则xn+i=0如果xn+i0，则yi=0边际利润大于0的资源，在最优生产计划条件下没有剩余ym+jxj=0如果ym+j0，则xj=0如果xj0，则ym+j=0最优生产计划条件下有剩余的资源，其边际利润等于0差额成本大于0（机会成本大于利润）的产品，不安排生产安排生产的产品，差额成本等于0（机会成本等于利润）和资源有关的量n资源限量（吨）n资源占用（吨）n资源剩余（吨）n资源的影子价格（元/吨）和产品有关的量n产品利润（元/件）n产品产量（件）n产品
25、的机会成本（元/件）n产品的差额成本（元/件）互补松弛关系，其中一个大于0，另一个一定等于0互补松弛关系，其中一个大于0，另一个一定等于0对偶单纯形法 如果线性规划原问题标准化之后不能简单得出一个初始基可行解，但却能容易得到该问题的对偶问题的一个初始基可行解，此时我们就可以通过保持对偶基可行解的可行性的方法进行迭代，逐步消除原问题基本解的不可行性，最终，当对偶基可行解迭代到对偶最优解的同时原问题也得到了最优的基可行解。书例3-612341231241234min9101612. .2422430,0,0,0zxxxxstxxxxxxxxxx123412351246min9101612. .24
26、22430(1,2,3,4,5,6)jzxxxxstxxxxxxxxxj 化成标准形式123412351246min9101612. .2422430(1,2,3,4,5,6)jzxxxxstxxxxxxxxxj 9/2 10 - 3 - - 3 7/2 4 - - - - 4/3 2 - - 12已获得最优解：（x1, x2, x3, x4, x5, x6）=（4/3, 1/3, 0, 0, 0, 0） min z=46/3单纯形法对偶单纯形法前提条件最优性检验换入、换出变量的确定原始基解的变化所有bi0所有sj0 ?所有bi0 ?所有sj0 先确定换入变量后确定换出变量先确定换出变量后确定
27、换入变量可行最优非可行可行(最优)对偶单纯形法练习0 xxx2xx2x5xx3x24xxx. t . sxx2x3zmin3213213213213210 xxxxxx2xxx2x5xxx3x24xxxx. t . sxx2x3zmin6543216321532143213210 xxxxxx2xxx2x25xxx3x24xxxx. t . sxx2x3zmin654321632153214321321已获得最优解：（x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=35引例 一奶制品加工厂用牛奶生产A，B两种奶制品，1桶牛奶可以在甲车间用12小
28、时加工成3公斤A，或者在乙车间用8小时加工成4公斤B 。根据市场需求，生产的A, B全部能售出，且每公斤A获利24元，每公斤B获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间480小时，并且甲车间每天至多能加工100公斤A，乙车间的加工能力没有限制。试为该厂制订一个生产计划，使每天获利最大解：设该厂每天给甲车间x1桶牛奶，给乙车间x2桶牛奶，可得线性规划模型1212121imax z=3 24x +4 16xx +x5012x +8x480s.t. 3x100 x0,1,2.i最优解为x1=20，x2=30，最优值z=3360，即用20桶牛奶生产A, 30桶牛奶生产B
29、 ，可获最大利润3360元 并进一步讨论以下3个附加问题： 1） 若用35元可以买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？ 2） 若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？ 3） 由于市场需求变化，每公斤A的获利增加到30元，应否改变生产计划？生产计划中的一般形式：其中，C代表企业产品的市场状况，称为价值系数向量；A代表企业的技术状况，称为技术系数矩阵；b代表企业的资源状况，称之为资源向量列。资源数量b中某个bi 发生变化，即bi= bi +bi时，假设规划问题的其它系数不变，这样就会影响基变量的值，进而最优解可能发生变化。 由于单纯形法的最优性
30、检验标准为B-1b 0，所以只要变化后的b 满足 B-1b 0 ，则目前的基还是最优基，目前最优解仍然为z= CBTB-1b ；否则若B-1b 中某些分量小于0，则目前的基成不了可行基，最优解也会发生变化。此时需用对偶单纯形法重新求解。最优基B的逆矩阵B-1就是最优表中初始基对应的位置.1212121imax z=3 24x +4 16xx +x5012x +8x480s.t. 3x100 x0,1,2.i引例 已知线性规划模型的标准型的最优单纯形表如下，其中z = -z, x3, x4, x5为松弛变量.12min z=-72x -64x问题：1） 若用35元可以买到1桶牛奶，应否作这项投资
31、？若投资，每天最多购买多少桶牛奶？ 2） 若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？解：由最优单纯形表可见，松弛变量的值分别为-48, -2, 0，根据z=-z 和对偶理论得知，牛奶和劳动时间的影子价格分别为48和2，甲车间生产能力的影子价格为0，意味着增加牛奶和劳动时间可以增加利润，从而可以考虑投资购买牛奶和聘用临时工人。(1) 设只有b1 发生变化，由1163/4131/40480021/40100bB b 可得130/3 b160，意味着我们可以将牛奶从50桶增加到60桶，即每天最多购买10桶牛奶. 由于牛奶的市场价35小于牛奶的影子价格48，故应该作这项投资
32、，且每天最多投资购买10桶牛奶.(2) 设只有b2 发生变化，由1263/415031/40021/40100B bb 可得400 b21600/3，意味着我们的劳动时间可以从480小时增加到1600/3小时，即每天最多购买160/3小时劳动时间. 由于劳动时间的影子价格为2，故付给临时工人的工资最多为每小时2元.进一步问：若该厂的正式工人中突然有15人请假，则原生产计划还是否可行？若不可行，求改变后的最优生产计划？(假设每名工人每天的劳动时间为8小时)解：15名正式工人请假意味着劳动时间将由480小时减少到360小时，由于360400，故不在最优基允许的范围内，即原生产计划不再可行，须重新求
33、解最优的生产计划.512163/415013031/403606021/4010010BxXxB bx11300647260312010TBzC B b即z = -3120，改写最优单纯形表， 根据对偶单纯形法- - 5 - -可知，最优解x =(5, 45, 0, 0, 100)，z = -2880，最优解z = 2880.基变量的价值系数变化分析 当某个基变量的价值系数cj发生变化时，会影响目标函数中所有非基变量x的系数发生变化，且目标函数中非基变量xN的系数为CNT- CBTB-1N ( N表示约束条件中非基变量xN的技术系数). 若cj变化后，仍有新的CBTB-1N-CNT0 ，则原解
34、还是最优；否则就不是最优，需继续迭代才能达到最优。关键是在最优表中查出矩阵B-1N (它是由最优表中非基变量相对应的列构成的矩阵).对于引例中的线性规划问题，最优表如下问题： 3） 由于市场需求变化，每公斤A的获利增加到30元，应否改变生产计划？解：每公斤A获利由24增加到30元，意味着目标函数中基变量x1的系数由72变成90，将影响到所有非基变量的系数，要是最优解不变，则由CBTB-1N-CNT0 及最优表中的数据可得1152134(,)( ,)TTBNC B NCc c c B Nc c163/40,-64,-31/40,0021/4c可得64 c1 96，目标函数中X1的新系数90在这个
35、范围内，意味着最优基不变，即不需要改变生产计划.进一步问：若每公斤A的获利增加到35元，则原生产计划还是否可行？若不可行，求改变后的最优生产计划？解：当每公斤A的获利增加到35元，x1的系数由72增加到105，由于10596，故不在最优基允许的范围内，即原生产计划不再可行，须重新求解最优的生产计划.最优解x =(100/3,10,20/3,0,0)，z = -4140，最优解z =4140.非基变量的价值系数变化分析 当某个非基变量的价值系数cj 发生变化时，也就是目标函数中xj 的系数发生变化，且目标函数中xj 的系数为cj -CBTB-1Pj (Pj表示约束条件中xj 的技术系数). 若变
36、化后的cj CBTB-1Pj ，则原解还是最优；否则就不是最优，可改变系数后重新求解最优值.工艺结构改变的分析 由于设备的改进，人工技术娴熟程度的变化等原因导致的生产工艺结构发生改变使得系数矩阵会发生变化. 通常工艺结构改变后，最优解会发生变化，需重新求解. 通常用B-1Pj 替换最优表中xj 列的位置，用CBTB-1Pj - cj 来替换单纯形表中目标行里xj 的系数，对新的单纯形表求解即可得改变后的最优解.引例 由于奶制品工厂乙生产车间设备的改进， 1桶牛奶可以在乙车间可用6小时加工成4公斤B，问改进后的最优生产计划？解：设备改进后，产品B的技术系数向量由P2T= (1,8,0)变为P2T
37、= (1, 6, 0)，由c2 =6，从而1263/4113/231/4063/221/4001/2B P 1223/2(0,64,72)3/265401/2TBC B Pc最优解发生变化，需重新计算生产计划.最优表换为80/320-180最优解x =(0,50,0,180,100)，z = -5700，最优解z =5700.注意：若碰到原问题和对偶问题均为非可行解时，这就需要引进人工变量后重新求解. (参照人工变量法)增加新变量的分析 由于新产品的研发问题而增加决策变量，使得系数矩阵增加列而改变. 引入新变量xj 后，若CBTB-1Pj - cj 0，则意味着新变量的引入可以使得目标函数值优
38、化，从而可以引入新变量；否则没有必要引入新变量xj .引例 该奶制品工厂除了甲车间和乙车间两条生产线外，现安排引进一条新的生产线丙车间， 1桶牛奶可以在丙车间用9小时快速加工成3公斤C，且丙车间的加工能力没有限制. 设市场对C的需求没有限制，且每公斤C可获利20元，问该奶制品厂是否应该引进这条新的生产线以及引进后的最优生产计划？解：设将x3桶牛奶用于丙车间生产，其技术系数向量P3T= (1,9,0) ，由c3 =60，从而13363/4113/431/4093/421/4001/4PB P 333/4(0,64,72)3/460601/4TBC Pc引进新的生产线丙车间生产产品C是有利的. 为了求得新的生产计划，在原最优表的最后一列再增加一列x6，将P3和系数-3填在相应的位置得下表-4080最优解x =(10,0,40,60, 0)，z = -3600，最优解z =3600.注意：若碰到原问题和对偶问题均为非可行解时，这就需要引进人工变量后重新求解. (参照人工变量法)增加新约束的分析 由于市场产品销售或资源配置问题而增加(或减少)约束条件，使得系数矩阵增加(或减少)行而改变.
