《运筹学》对偶理论.ppt

第第3章章 线性规划对偶理论及其应用线性规划对偶理论及其应用 线性规划的对偶模型对偶性质对偶问题的经济解释影子价格对偶单纯形法 本章主要内容：线性规划的对偶模型线性规划的对偶模型设某工厂生产两种产品甲和乙，生产中需设某工厂生产两种产品甲和乙，生产中需4种设备按种设备按A，B，C，D顺序加工，每件产品加工所需的机时数、每件产品的利润值顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表及每种设备的可利用机时数列于下表：产品数据表 设备设备产品产品ABCD产品利润产品利润（元件）（元件）甲甲 21402乙乙 22043设备可利用设备可利用机时数（时）机时数（时）1281612问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？1.对偶问题的现实来源对偶问题的现实来源线性规划的对偶模型线性规划的对偶模型解：设甲、乙型产品各生产解：设甲、乙型产品各生产x1及及x2件，则数学模型为：件，则数学模型为：反过来问：若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么种机器的机时如何定价才是最佳决策？线性规划的对偶模型线性规划的对偶模型在市场竞争的时代，厂长的最佳决策显然应符合两条：在市场竞争的时代，厂长的最佳决策显然应符合两条：（1）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则，便构成了新规划的不等式约束条件。产品所获利润。由此原则，便构成了新规划的不等式约束条件。（2）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。费，以便争取更多用户。设A、B、C、D设备的机时价分别为y1、y2、y3、y4，则新的线性规划数学模型为：线性规划的对偶模型线性规划的对偶模型把同种问题的两种提法所获得的数学模型用表把同种问题的两种提法所获得的数学模型用表2表示，将会发表示，将会发现一个有趣的现象。现一个有趣的现象。原问题与对偶问题对比表A（y1）B（y2）C（y3）D（y4）甲（甲（x1）21402乙（乙（x2）220431281612 min max z 线性规划的对偶模型线性规划的对偶模型2.原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题（对偶问题）对偶问题（原问题）线性规划的对偶模型线性规划的对偶模型（1）对称形式）对称形式特点：目标函数求极大值时，所有约束条件为号，变量非负;目标函数求极小值时，所有约束条件为号，变量非负.已知P，写出D线性规划的对偶模型线性规划的对偶模型例例.写出线性规划问题的对偶问题写出线性规划问题的对偶问题解：首先将原问题变形为对称形式线性规划的对偶模型线性规划的对偶模型线性规划的对偶模型线性规划的对偶模型(2)非对称型对偶问题若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。也可直接写出非对称形式的对偶问题。线性规划的对偶模型线性规划的对偶模型原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量00=无约束无约束变变量量n个个n个个约约束束条条件件00无约束无约束=线性规划的对偶模型线性规划的对偶模型例例2 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题.解：原问题的对偶问题为资源定价问题（LP2）比较原问题（生产计划）对偶问题（资源定价）规范形式的线性规划问题规范形式的线性规划问题原问题（LP）对偶问题（DLP）规范形式最大化问题:约束条件全为型决策变量全部非负最小化问题:约束条件全为型决策变量全部非负规范形式的对偶关系原问题对偶问题目标函数:max CX目标函数:minbYm个约束条件:AX bm个决策变量:Y 0n个决策变量:X 0n个约束条件:AY C原问题对偶问题非规范形式的对偶关系对非规范形式的对偶关系，只需对上述表进行相应修改即可：例如对于一个最小化问题，若某个决策变量yi 0,则期对偶的约束条件为型的;若其某个约束条件是型,则其对应的对偶变量是非正的.非规范形式线性规划的对偶问题非规范形式线性规划的对偶问题非规范形式线性规划的对偶问题非规范形式线性规划的对偶问题1 变量取值范围不符合非负要求的情况非规范形式线性规划的对偶问题非规范形式线性规划的对偶问题非规范形式线性规划的对偶问题非规范形式线性规划的对偶问题2 约束方程不是“”的情况 总结总结总结总结约束条件对变量，变量对约束条件；正常对正常，不正常对不正常；变量正常是非负，约束条件正常看目标(max ，min)。课堂作业：求解下面线性规划的对偶规划课堂作业：求解下面线性规划的对偶规划LPDLP对偶性质对偶性质例3 分别求解下列2个互为对偶关系的线性规划问题分别用单纯形法求解上述2个规划问题，得到最终单纯形表如下表：对偶性质对偶性质XBb原问题的变量原问题的变量原问题的松弛变量原问题的松弛变量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/20001/41/2XBb对偶问题的变量对偶问题的变量对偶问题的剩余变量对偶问题的剩余变量y1y2y3y4y5y21/4-4/510-1/41/4y31/215/2011/2-3/215/2007/23/2原问题最优表对偶问题最优表对偶性质对偶性质原问题与其对偶问题的变量与解的对应关系：原问题与其对偶问题的变量与解的对应关系：原问题与其对偶问题的变量与解的对应关系：原问题与其对偶问题的变量与解的对应关系：在单纯形表中，原问题的松弛变量对应对在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问偶问题的变量，对偶问题的剩余变量对应原问题的变量。题的变量。对偶性质对偶性质性质1 对称性定理：对偶问题的对偶是原问题 min W=Y bs.t.YA C Y 0max Z=C Xs.t.AXb X 0对偶性质对偶性质性质2 弱对偶原理(弱对偶性)：设 和 分别是问题(P)和(D)的可行解，则必有推论1:原问题任一可行解的目标函数值是其对偶问题目标函数值的下届；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。推论推论2:在一对对偶问题（在一对对偶问题（P）和（）和（D）中，若其中一个问题可）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。也是对偶问题的无界性。无界如：（原）无可行解（对）对偶性质对偶性质推论推论3 3：在一对对偶问题（在一对对偶问题（P）和（）和（D）中，若一个可行（如）中，若一个可行（如P），而另一个不可行（如），而另一个不可行（如D），则该可行的问题目标函数），则该可行的问题目标函数值无界。值无界。性质3 最优性定理：如果 是原问题的可行解，是其对偶问题的可行解，并且:则 是原问题的最优解，是其对偶问题的最优解。对偶性质对偶性质性质性质4 强对偶性：若原问题及其对偶问题均具有可行解，则强对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。两者均具有最优解，且它们最优解的目标函数值相等。还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。性质5 互补松弛性：设X0和Y0分别是P问题 和 D问题 的可行解，则它们分别是最优解的充要条件是：其中：Xs、Ys为松弛变量约束 条件 也分为两种情况：，约束条件比较松；，约束条件比较紧；yi 0,分为两种情况：yi0，约束条件比较松；yi=0，约束条件比较紧；互补松弛定理的解释互补松弛定理的解释互补松弛定理的解释互补松弛定理的解释变量同其对偶问题的约束方程之间至多只能够有一个取松弛的情况，当其中一个取松弛的情况时，另外一个比较紧，即取严格等号。已知下面的已知下面的LP1和和LP2为一组对偶规划，且已知为一组对偶规划，且已知LP1的最优解的最优解为为X=（1.5，1）。试运用互补松弛定理求出对偶问题的最。试运用互补松弛定理求出对偶问题的最优解优解Y。原问题（LP1）对偶问题（LP2）解：由X=（1.5，1）得联立求解得：对偶性质对偶性质性质性质5的应用：的应用：该性质给出了已知一个问题最优解求另一个问题最优解该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知的方法，即已知Y求求X或已知或已知X求求Y互补松弛条件由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：若Y0，则Xs必为0；若X0，则Ys必为0利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。对偶性质对偶性质例例4 已知线性规划已知线性规划的最优解是X=(6,2,0)T,求其对偶问题的最优解Y。解：写出原问题的对偶问题，即标准化对偶性质对偶性质设对偶问题最优解为设对偶问题最优解为Y(y1，y2),由互补松弛性定理可知，由互补松弛性定理可知，X和和 Y满足：满足：即：因为X10，X20，所以对偶问题的第一、二个约束的松弛变量等于零，即y30，y40，带入方程中：解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为：Y=(1,1)，最优值w=26。对偶性质对偶性质例例5 已知线性规划已知线性规划 的对偶问题的最优解为Y=(0,-2)，求原问题的最优解。解:对偶问题是标准化对偶性质对偶性质设对偶问题最优解为设对偶问题最优解为X(x1，x2，x3)T,由互补松弛性定理由互补松弛性定理可知，可知，X和和 Y满足：满足：将Y带入由方程可知，y3y50，y41。y2=-20 x50又y4=10 x20将x2，x5分别带入原问题约束方程中，得：解方程组得：x1=-5,x3=-1,所以原问题的最优解为X=(-5,0,-1)，最优值z=-12对偶问题的经济解释影子价格对偶问题的经济解释影子价格1.影子价格的数学分析：影子价格的数学分析：定义：在一对 P 和 D 中，若 P 的某个约束条件的右端项常数bi（第i种资源的拥有量）增加一个单位时，所引起目标函数最优值z*的改变量称为第 i 种资源的影子价格，其值等于D问题中对偶变量yi*。由对偶问题得基本性质可得：对偶问题的经济解释影子价格对偶问题的经济解释影子价格2.影子价格的经济意义影子价格的经济意义1）影子价格是一种边际价格）影子价格是一种边际价格在其它条件不变的情况下，单位资源数量的变化所引起在其它条件不变的情况下，单位资源数量的变化所引起的目标函数最优值的变化。即对偶变量的目标函数最优值的变化。即对偶变量yi 就是第就是第 i 种资源的种资源的影子价格。即：影子价格。即：对偶问题的经济解释影子价格对偶问题的经济解释影子价格2）影子价格是一种机会成本）影子价格是一种机会成本影子价格是在资源最优利用条件下对单位资源的估价，影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市场价格。因此，从另一个角度说，这种估价不是资源实际的市场价格。因此，从另一个角度说，它是一种机会成本。它是一种机会成本。若第i 种资源的单位市场价格为mi，则有当yi*mi 时，企业愿意购进这种资源，单位纯利为yi*mi，则有利可图；如果yi*mi 则购进资源i，可获单位纯利yi*mi 若yi*mi则转让资源i，可获单位纯利miyi影子价格影子价格010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 x1123(50/7，200/7)多了 32/7010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 x1123(50/7.200/7)x1010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 123(55/7.199/7)影子价格影子价格010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 x1123(47/7.202/7)多了 6/7影子价格影子价格对偶问题的经济解释影子价格对偶问题的经济解释影子价格3）影子价格在资源利用中的应用）影子价格在资源利用中的应用根据对偶理论的互补松弛性定理根据对偶理论的互补松弛性定理:Y*Xs=0 ,YsX*=0表明生产过程中如果某种资源表明生产过程中如果某种资源bi未得到充分利用时，该种资未得到充分利用时，该种资源的影子价格为源的影子价格为0；若当资源资源的影子价格不为；若当资源资源的影子价格不为0时，表明时，表明该种资源在生产中已耗费完。该种资源在生产中已耗费完。对偶问题的经济解释影子价格对偶问题的经济解释影子价格4）影子价格对单纯形表计算的解释）影子价格对单纯形表计算的解释单纯形表中的检验数其中cj表示第j种产品的价格;表示生产该种产品所消耗的各项资源的影子价格的总和,即产品的隐含成本。当产值大于隐含成本时，即 ，表明生产该项产品有利，可在计划中安排；否则 ，用这些资源生产别的产品更有利，不在生产中安排该产品。定义：在一对 P 和 D 中，若 P 的某个约束条件的右端项常数bi 增加一个单位时，所引起的目标函数最优值Z*的改变量y*i称为第i个约束条件的影子价格，又称为边际价格。影子价格影子价格CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCB B-1b0CNCB B-1NCB B-1本章小结本章小结学习要点：1.线性规划解的概念以及3个基本定理2.熟练掌握单纯形法的解题思路及求解步骤三、灵敏度分析 讨论模型的系数或变量发生小的变化时对解的影响（如它们在何范围内变化时可使原最优解或最优基不变？）我们主要讨论C、b和变量结构变化时对解的影响。对解怎样影响？影响解的 -最优性 -可行性3.增加新变量时的分析 主要讨论增加新变量xn+1是否有利。经济意义是第n+1种新产品是否应当投产，数学意义是xn+1是否应进基。经济意义：市场价影子价1.1.C C变化时的分析变化时的分析变化时的分析变化时的分析1、目标函数系数cj变化例 3.7 C由(3.2)变为(3,1)，请问最优生产计划如何变化？解：由原最优单纯形表得：基变量31000bCBxBx1x2x3x4x50 x30 0 1 5/2-3/23/23x11 0 0 3/2-1/23/21x20 1 0 -2 1 1 0 0 0 -5/21/211/2单纯形迭代得：单纯形迭代得：基变量31000bCBxBx1x2x3x4x50 x30 3/21 -1/2033x11 1/20 1/2020 x50 10 -21 1 0 -1/20-3/2-3/26所以得到新的最优生产计划为产品所以得到新的最优生产计划为产品I生产生产2件，产品件，产品II不生产，此时总利润上升为不生产，此时总利润上升为6万元。万元。2、约束条件右端向量、约束条件右端向量b的变化的变化2、约束条件右端向量、约束条件右端向量b的变化的变化例 穗羊公司仓库盘点时发现，资源B的每周可使用量可以增加到5吨，请制定新的最优生产计划。解：解：因为，所以需要进行对偶单纯形迭代。由原最优单纯形表得：基变量32000bCBxBx1x2x3x4x50 x30 0 1 5/2-3/24（1）3x11 0 0 3/2-1/23（2）2x20 1 0 -2 1 -1 （3）0 0 0 -1/2-1/27（4）l因为因为x2=-10，所以令其岀基。，所以令其岀基。l拿检验数所在行除以出基变量所在行的负数，商拿检验数所在行除以出基变量所在行的负数，商最小的列对应的元素作为主元素。这里正数和零最小的列对应的元素作为主元素。这里正数和零不能作为主元素不能作为主元素。l本题中第三行只有本题中第三行只有a34=-20，所以选择，所以选择a34作为主元作为主元素，进行对偶迭代。素，进行对偶迭代。l迭代的目标：迭代的目标：右端向量划为非负右端向量划为非负右端向量划为非负右端向量划为非负把基变量所在列划成单位矩阵把基变量所在列划成单位矩阵把基变量所在列划成单位矩阵把基变量所在列划成单位矩阵基变量检验数化为零。基变量检验数化为零。基变量检验数化为零。基变量检验数化为零。基变量32000bCBxBx1x2x3x4x50 x30 5/4 1 0-1/411/4（1）+5*（3）/43x11 3/4 0 01/49/4（2）+3*（3）/40 x40 -1/2 0 1 -1/2 1/2 （3）*（-1/2）0 -1/4 0 0-1/427/4（4）-（3）/4迭代后得：3、增加一种新产品、增加一种新产品例例3.10 穗羊公司研发部门开发了一种新产品穗羊公司研发部门开发了一种新产品III，单位产品对，单位产品对A、B、C三种三种资源的消耗系数为，该产品单位利润为资源的消耗系数为，该产品单位利润为2万元。问产品万元。问产品III是否应该生产？是否应该生产？如果生产，各产品生产量是多少？如果生产，各产品生产量是多少？解：解：产品III机会成本 该产品的检验数，所以应该生产。将上述数据代入原最优单纯形表得下表：将上述数据代入原最优单纯形表得下表：基变量320002bCBxBx1x2x3x4x5x60 x30 0 1 5/2-3/203/23x11 0 0 3/2-1/2-13/22x20 1 0 -2 1 21 0 0 0 -1/2-1/2113/20 x30 01 5/2-3/203/23x11 00 1/20022x60 1/20 -11/211/20 -1/20 -11/4-107所以，新的最优生产计划是产品I和产品III分别生产2件和1/2件，产品II不生产，总利润为7万元。4、增加一个新的约束条件、增加一个新的约束条件例：穗羊公司生产部门发现生产除了受到例：穗羊公司生产部门发现生产除了受到A、B、C三种资源的约束外，还要三种资源的约束外，还要受到资源受到资源D的约束。资源的约束。资源D周可用量为周可用量为6，生产单位产品，生产单位产品I、II对资源对资源D的消的消耗分别为耗分别为7/2和和2。请制定新的最优生产计划。请制定新的最优生产计划。解：根据题意，需要在原问题后面增加新约束 将原最优生产计划X=（3/2，1）代入该约束方程得：不满足新约束条件。将约束方程添加松弛条件得：将此约束方程代入原最优单纯形表得下表：将此约束方程代入原最优单纯形表得下表：基变量310000bCBxBx1x2x3x4X5x60 x30 0 1 5/2-3/203/2（1）3x11 0 0 3/2-1/203/2（2）1x20 1 0 -2 1 01 （3）0 x67/2200016（4）0 0 0 -1/2-1/2011/2将将a41、a42化为化为0得下表：得下表：基变量310000bCBxBx1x2x3x5x5x60 x30 0 1 5/2-3/203/2（1）3x11 0 0 3/2-1/203/2（2）1x20 1 0 -2 1 01 （3）0 x6000-5/4-1/41-5/4（4）0 0 0 -1/2-1/2011/2对偶单纯形迭代得下表：对偶单纯形迭代得下表：基变量310000bCBxBx1x2x3x4x5x60 x30 0 1 0-22-13x11 0 0 0-4/56/501x20 1 0 07/5-8/530 x400011/5-4/510000-2/5-2/550 x50 0 -1/201 -11/23x11 0 -2/500 2/52/51x20 1 7/1000 -1/523/100 x4001/1010-3/59/1000-1/500-4/524/5所以新的最优生产计划是产品I和产品II分别生产2/5件和23/10件，总利润为24/5万元。5、约束条件系数、约束条件系数aij的变化的变化例：穗羊公司经过技术革新，将生产产品例：穗羊公司经过技术革新，将生产产品I对资源对资源C的单位消耗量从的单位消耗量从4变为变为2，即，即P1=（1,2,4）变为变为P1=（1,2,2）。请求出新的最优生产计划。请求出新的最优生产计划。解：令将 插入原最优单纯形表格得：基变量-99731000bCBxBx1x1x2x3x4x50 x30 30 1 5/2-3/23/2-997x11 20 0 3/2-1/23/22x20 -21 0 -2 1 1 0 20010 0 2999/2-1001/22987/23x10 10 1/35/6-1/21/2-997x11 00 -2/3-1/61/21/22x20 01 2/3-1/3020 00-667-168500493基变量31000bCBxBx1x2x3x4x53x110 -1/32/3010 x500 -4/3-1/3112x201 2/3-1/30200-1/3-4/30-7继续迭代，并删除原第一列，得下表：故新的最优生产计划是产品I、II分别生产1单位和2单位，总利润为7万元。灵敏度分析灵敏度分析灵敏度分析灵敏度分析已知线性规划问题已知线性规划问题已知线性规划问题已知线性规划问题MaxZ MaxZ 1010 x x1 1+5+5x x2 2 3 3x x1 14 4x x2 2 9999 s.t s.t 5 5x x1 12 2x x2 2 8 8 8 8 x x1 1，x x2 200最优表如右：最优表如右：最优表如右：最优表如右：试用灵敏度分析的方法判断：试用灵敏度分析的方法判断：试用灵敏度分析的方法判断：试用灵敏度分析的方法判断：1 1、价值系数、价值系数、价值系数、价值系数c c1 1或或或或c c2 2分别在什么范围内变动，上述最优解不变；分别在什么范围内变动，上述最优解不变；分别在什么范围内变动，上述最优解不变；分别在什么范围内变动，上述最优解不变；X XB Bb bx x1 1x x2 2x x3 3x x4 4x x2 23/23/20 01 15/145/14-3/14-3/14x x1 11 11 10 0-1/7-1/7-1/7-1/72/72/7 j j0 00 0-5/14-5/14-25/14-25/14c cj j10105 50 00 0C CB BX XB Bb bx x1 1x x2 2x x3 3x x4 45 5x x2 23/23/20 01 15/145/14-3/14-3/141010 x x1 11 11 10 0-1/7-1/7-1/7-1/72/72/7 j j0 00 0-5/14-5/14-25/14-25/141 1、价值系数、价值系数、价值系数、价值系数 c c1 1和和和和 c c2 2分别在什么范围内变动，上述最优解分别在什么范围内变动，上述最优解分别在什么范围内变动，上述最优解分别在什么范围内变动，上述最优解不变；不变；不变；不变；解解解解 3 3 0 025/1425/141/71/7（1010 c c1 1）0 0 0 0，c c1 1 5/25/2 4 4 0 015/1415/142/72/7（1010 c c1 1）0 0，c c1 1 25/425/4当当当当25/425/4 c c1 1 5/2 5/2，即，即，即，即15/415/4 c c1 1 22225/25/2时，最优解不变时，最优解不变时，最优解不变时，最优解不变将将c1=10+c c1 1 代入最优表中代入最优表中代入最优表中代入最优表中10+c c1 110+c c1 1c cj j10105 50 00 0C CB BX XB Bb bx x1 1x x2 2x x3 3x x4 45 5x x2 23/23/20 01 15/145/14-3/14-3/141010 x x1 11 11 10 0-1/7-1/7-1/7-1/72/72/7 j j0 00 0-5/14-5/14-25/14-25/141 1、价值系数、价值系数、价值系数、价值系数 c c1 1和和和和 c c2 2分别在什么范围内变动，上述最优解分别在什么范围内变动，上述最优解分别在什么范围内变动，上述最优解分别在什么范围内变动，上述最优解不变；不变；不变；不变；解解解解 3 3 0 05/14(55/14(5 c c2 2）+10/7+10/70000，c c2 2 -1-1 4 4 0 03/143/14（5 5 c c2 2）-20/70-20/70，c c2 2 25/325/3当当当当1 1 c c1 1 22225/3 5/3，即，即，即，即4 4 c c2 2 40404040/3/3时，最优解不变时，最优解不变时，最优解不变时，最优解不变将将c2=5+c c2 2代入最优表中代入最优表中代入最优表中代入最优表中5+c25+c2c cj j10105 50 00 0C CB BX XB Bb bx x1 1x x2 2x x3 3x x4 45 5x x2 23/23/20 01 15/145/14-3/14-3/141010 x x1 11 11 10 0-1/7-1/7-1/7-1/72/72/7 j j0 00 0-5/14-5/14-25/14-25/141 1、若、若、若、若c c1 14 4，c c2 21010，则上述最优解是否改变？，则上述最优解是否改变？，则上述最优解是否改变？，则上述最优解是否改变？解：将解：将c c1 14 4，c c2 210 10 代入单纯形表：代入单纯形表：代入单纯形表：代入单纯形表：4104 3 3 0 025/1425/144/7=4/7=3030 4 4=030/148/710所以最优解改变所以最优解改变102 2、右端向量、右端向量、右端向量、右端向量b b1 1保持不变，保持不变，保持不变，保持不变，b b2 2在什么范围内变化，最优基不变。在什么范围内变化，最优基不变。在什么范围内变化，最优基不变。在什么范围内变化，最优基不变。c cj j10105 50 00 0C CB BX XB Bb bx x1 1x x2 2x x3 3x x4 45 5x x2 23/23/20 01 15/145/14-3/14-3/141010 x x1 11 11 10 0-1/7-1/7-1/7-1/72/72/7 j j0 00 0-5/14-5/14-25/14-25/14 5/14 5/143/143/149 9 -1/7 2/7-1/7 2/78 8 b b2 2 0000解解解解B B-1-1b bMaxZ MaxZ 1010 x x1 1+5+5x x2 2 3x 3x1 14 4x x2 2 9999 s.t s.t 5 5x x1 12 2x x2 2 8 8 8 8 x x1 1，x x2 200 45/14 45/143/143/14（8 8 b b2 2 ）-9/7-9/72/72/7（8 8 b b2 2）0000当当当当7/2 7/2 b b2 2 7 7，即，即，即，即9/29/2 b b2 2 15151515时，最优基不变。时，最优基不变。时，最优基不变。时，最优基不变。c cj j10105 50 00 0C CB BX XB Bb bx x1 1x x2 2x x3 3x x4 40 0 x x3 39 93 34 41 10 00 0 x x4 48 85 52 20 0 0 01 1 8 8 b b2 2 3 3、问题的目标函数变为、问题的目标函数变为、问题的目标函数变为、问题的目标函数变为MaxZ MaxZ 1212x x1 1+4+4x x2 2时上述最优解的变化；时上述最优解的变化；时上述最优解的变化；时上述最优解的变化；c cj j10105 50 00 0C CB BX XB Bb bx x1 1x x2 2x x3 3x x4 45 5x x2 23/23/20 01 15/145/14-3/14-3/141010 x x1 11 11 10 0-1/7-1/7-1/7-1/72/72/7 j j0 00 0-5/14-5/14-25/14-25/14c cj j12124 40 00 0C CB BX XB Bb bx x1 1x x2 2x x3 3x x4 44 4x x2 23/23/20 01 15/145/14-3/14-3/141212x x1 11 11 10 0-1/7-1/7-1/7-1/72/72/70 0 x x3 32121/5 50 014/514/51 1-3/5-3/51 12 2x x1 18/58/51 12/52/50 0 0 01/51/5 j j0 0-4/5-4/50 0-12/5-12/5 j j得新最优解得新最优解得新最优解得新最优解X*X*（8/58/5，0 0，21/521/5，0 0）T T 0 0 2/7 -18/70 0 2/7 -18/74 4、约束条件右端项由变为、约束条件右端项由变为、约束条件右端项由变为、约束条件右端项由变为 时上述最优解的变化。时上述最优解的变化。时上述最优解的变化。时上述最优解的变化。9 98 811111919c cj j10105 50 00 0C CB BX XB Bb bx x1 1x x2 2x x3 3x x4 45 5x x2 23/23/20 01 15/145/14-3/14-3/141010 x x1 11 11 10 0-1/7-1/7-1/7-1/72/72/7 j j0 00 0-5/14-5/14-25/14-25/14解解解解 B B-1-1b b 5/14 5/143/143/141111-1/7-1/7 -1/7 2/7-1/7 2/719 27/719 27/7最优基改变，用对偶单纯形法继续求解。最优基改变，用对偶单纯形法继续求解。最优基改变，用对偶单纯形法继续求解。最优基改变，用对偶单纯形法继续求解。c cj j10105 50 00 0C CB BX XB Bb bx x1 1x x2 2x x3 3x x4 45 5x x2 2-1/7-1/70 01 15/145/14-3/14-3/141010 x x1 127/727/71 10 0-1/7-1/7-1/7-1/72/72/7 j j0 00 0-5/14-5/14-25/14-25/14c cj j10105 50 00 0C CB BX XB Bb bx x1 1x x2 2x x3 3x x4 45 5x x2 2-1/7-1/70 01 15/145/14-3/14-3/141010 x x1 127/727/71 10 0-1/7-1/7-1/7-1/72/72/7 j j 0 00 0-5/14-5/14-25/14-25/14 i i 0 0 x x4 42/32/30 0-14/3-14/3-5/3-5/31 11010 x x1 111/311/31 14/34/31/31/31/31/30 0 j j 0 0-25/3-25/3-10/3-10/30 0得新最优解得新最优解得新最优解得新最优解X*X*（11/311/3，0 0，0 0，2/32/3）T T