线规划的对偶模型DualModelofLP对偶质课件

LOGO2.1线性规划的对偶模型线性规划的对偶模型DualModelofLP2.2对偶性质对偶性质Dualproperty2.3对偶单纯形法对偶单纯形法DualSimplexMethod2.4灵敏度与参数分析灵敏度与参数分析SensitivityandParametricAnalysis2.1.1 引例引例【例例21】某企业用四种资源生产三种产品，工艺系数、某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：资源限量及价值系数如下表：建立总利润最大的数学模型。建立总利润最大的数学模型。产品产品资源资源ABC资源限量资源限量986500547450832300764550单件产品利润单件产品利润10080702.1线性规划的对偶模型线性规划的对偶模型2第第2章章对偶理论对偶理论【解解】设设x1，x2，x3分别为产品分别为产品A，B，C的产量，则的产量，则现现在在从从另另一一个个角角度度来来考考虑虑企企业业的的决决策策问问题题。假假如如企企业业自自己己不不生生产产产产品品，要要将将现现有有的的资资源源转转让让或或出出租租给给其其它它企企业业，那那么资源的转让价格应是多少才合理？么资源的转让价格应是多少才合理？合合理理的的价价格格应应是是对对方方用用最最少少的的资资金金购购买买本本企企业业的的全全部部资资源源，而而本本企企业业所所获获得得的的利利润润不不应应低低于于自自己己用用于于生生产产时时所所获获得得的利润。的利润。2.1.1引引例例（LP）3第第2章章对偶理论对偶理论设设y1，y2，y3，y4分别表示四种资源的单位增值价格分别表示四种资源的单位增值价格售价成本增值售价成本增值总增值最低可表示为总增值最低可表示为min w=500y1+450y2+300y3+550y4企企业业生生产产一一件件产产品品A用用了了四四种种资资源源的的数数量量分分别别是是9，5，8和和7个个单单位位，利利润润是是100，企企业业出出售售这这些些数数量量的的资资源源所所得的利润（增值）不能少于得的利润（增值）不能少于100，即，即同理，对产品同理，对产品B和和C有有另有另有2.1.1 引引 例例yi0,i=1,44第第2章章对偶理论对偶理论这这是是一一个个线线性性规规划划数数学学模模型型，称称这这一一线线性性规规划划问问题题是是前前面面生生产产计计划划模模型型()的的对对偶偶线线性性规规划划问问题题或或对对偶偶问问题题（DualPoblem,DP）。生生产产计计划划的的线线性性规规划划问问题题称称为为原始线性规划问题原始线性规划问题或或原始问题原始问题。2.1.1 引引 例例（）（DP）5第第2章章对偶理论对偶理论观察以上两个线性规划模型的对应关系观察以上两个线性规划模型的对应关系 原始问题原始问题 对偶问题对偶问题2.1.1 引引 例例原始问题的原始问题的C,A,b分别转置后就是对偶问题的资源限量分别转置后就是对偶问题的资源限量(b)，消耗系数，消耗系数(A)及利益系数及利益系数(C)原始问题和对偶问题是互为对偶的两个线性规划问题，原始问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可以写出另一个问题已知一个问题就可以写出另一个问题。6第第2章章对偶理论对偶理论xj yix1x2x3原始原始约束约束miny1986500y2547450y3832300y4764550对偶约束对偶约束max1008070对对 偶偶 表表2.1.1 引引 例例7第第2章章对偶理论对偶理论规范形式（规范形式（Canonical Form）的定义：）的定义：目标函数求目标函数求极大值极大值时，所有约束条件时，所有约束条件为为号号，变量非负变量非负；目标函数求目标函数求极小值极小值时，所有约束条件时，所有约束条件为为号号，变量非负变量非负。2.1.2 线性规划的规范形式线性规划的规范形式8第第2章章对偶理论对偶理论2.1.3 对偶模型对偶模型u每个线性规划问题都有一个与之相伴的对偶问题每个线性规划问题都有一个与之相伴的对偶问题。u已知一个问题就可写出另一个问题。已知一个问题就可写出另一个问题。l 当原始问题是规范形式，其对偶问题很容易写出；当原始问题是规范形式，其对偶问题很容易写出；l 如如果果给给出出的的问问题题不不是是规规范范形形式式，可可以以先先化化成成规规范范形形式式再再写写对对偶偶问问题题。也也可可直直接接按按表表2-4中中的的对对应应关关系系写写出出非规范形式的对偶问题。非规范形式的对偶问题。10第第2章章对偶理论对偶理论（2.3）是原始线性规划问题（）是原始线性规划问题（2.1）的对偶问题，反之，）的对偶问题，反之，（2.3）的对偶问题是（）的对偶问题是（2.1）。原始问题和对偶问题是）。原始问题和对偶问题是互互为对偶为对偶的两个线性规划问题。的两个线性规划问题。u规范形式的线性规划的对偶仍然是规范形式。规范形式的线性规划的对偶仍然是规范形式。u 已知一个规范形式问题就可写出另一个对偶问题已知一个规范形式问题就可写出另一个对偶问题2.1.3 对偶模型对偶模型其中其中Y=(y1,y2，,ym)原始问题原始问题对偶问题对偶问题对偶问题对偶问题原始问题原始问题12第第2章章对偶理论对偶理论【例例22】写出下列线性规划的对偶问题写出下列线性规划的对偶问题【解解】这是一个规范形式的线性规划这是一个规范形式的线性规划2.1.3 对偶模型对偶模型13第第2章章对偶理论对偶理论【补充例补充例】写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题2.1.3 对偶模型对偶模型14第第2章章对偶理论对偶理论2.1.3 对偶模型对偶模型y2=-y2设设原始问题是求最小值原始问题是求最小值的非规范形式，则有下列关系的非规范形式，则有下列关系1.第第i个约束是个约束是“”约束时，第约束时，第i个对偶变量个对偶变量yi02第第i个约束是个约束是“=”约束时，第约束时，第i个对偶变量个对偶变量yi无约束；无约束；3当当xj无约束时无约束时，第，第j个对偶约束为个对偶约束为“=”约束。当约束。当xj0时，时，第第j个对偶约束为个对偶约束为“”约束。约束。15第第2章章对偶理论对偶理论原始问题（原始问题（或对偶问题或对偶问题）对偶问题（对偶问题（或原始问题或原始问题）目标函数目标函数max目标函数系数目标函数系数约束条件系数矩阵约束条件系数矩阵A目标函数目标函数min约束右端常数项约束右端常数项约束条件系数矩阵约束条件系数矩阵ATn个变量，个变量，m个约束个约束n个约束个约束,m个变量个变量变变量量第第j个变量个变量0第第j个变量个变量0第第j个变量无约束个变量无约束约约束束第第j个约束为个约束为第第j个约束为个约束为第第j个约束为个约束为=约约束束第第i个约束个约束第第i个约束个约束第第i个约束为个约束为=变变量量第第i个变量个变量0第第i个变量个变量0第第i个变量无约束个变量无约束表表2-42.1.3 对偶模型对偶模型16第第2章章对偶理论对偶理论【例例2-3】写出下列线性规划的对偶问题写出下列线性规划的对偶问题【解解】目标函数求最小值，应将表目标函数求最小值，应将表2-4的右边看作原始问题，的右边看作原始问题，左边是对偶问题，原始问题有左边是对偶问题，原始问题有3个约束个约束4个变量，则对偶问题个变量，则对偶问题有有3个变量个变量4个约束，对照表个约束，对照表2-4的对应关系，写出对偶问题。的对应关系，写出对偶问题。=y10，y20，y3无约束无约束2.1.3 对偶模型对偶模型y1y2y317第第2章章对偶理论对偶理论1.本本节节以实例引出对偶问题以实例引出对偶问题;2.介绍了如何写规范与非规范问题的对偶问题介绍了如何写规范与非规范问题的对偶问题;2.1.3 对偶模型对偶模型 下一节：对偶性质下一节：对偶性质本节学习要点18第第2章章对偶理论对偶理论对偶问题对偶问题假设假设Xs与与Ys分别是（分别是（LP）与（与（DP）的松驰变量。的松驰变量。原始问题原始问题2.2 对偶问题的性质对偶问题的性质2.2.1 对偶性质对偶性质19第第2章章对偶理论对偶理论【性质性质2】（弱对偶性）设（弱对偶性）设X、Y分别为分别为LP(max)与与DP(min)的可行解，则的可行解，则这这一一性性质质说说明明了了两两个个线线性性规规划划互互为为对对偶偶时时，求求最最大大值值的的线线性性规规划划的的任任意意目目标标值值都都不不会会大大于于求求最最小小值值的的线性规划的任一目标值。线性规划的任一目标值。【性质性质1】（对称性）对偶问题的对偶是原问题。对称性）对偶问题的对偶是原问题。2.2.1 对偶性质对偶性质20第第2章章对偶理论对偶理论由性质由性质2可得到下面几个推论：可得到下面几个推论：推论推论1:(LP)的任一可行解的目标值是的任一可行解的目标值是(DP)的最优值下界；的最优值下界；(DP)任一可行解的目标是任一可行解的目标是(LP)的最优值的上界；的最优值的上界；推论推论2:在互为对偶的两个问题中，若一个问题具有无在互为对偶的两个问题中，若一个问题具有无界解，则另一个问题无可行解；界解，则另一个问题无可行解；推论推论3:若原问题可行且另一个问题不可行，则原问题具若原问题可行且另一个问题不可行，则原问题具有无界解。有无界解。注意上述后两个推论的条件不能少注意上述后两个推论的条件不能少。2.2.1 对偶性质对偶性质21第第2章章对偶理论对偶理论思考：思考：一个问题无可行解时，另一个问题解的情况怎样？一个问题无可行解时，另一个问题解的情况怎样？【结论结论】一个问题无可行解时，另一个问题可能有可行一个问题无可行解时，另一个问题可能有可行 解（此时具有无界解）也可能无可行解。解（此时具有无界解）也可能无可行解。2.2.1 对偶性质对偶性质22第第2章章对偶理论对偶理论例：例：无可行解无可行解其对偶问题有可行解其对偶问题有可行解由推论由推论3知知对偶问题必有无界解。对偶问题必有无界解。2.2.1 对偶性质对偶性质23第第2章章对偶理论对偶理论【性质性质3】（最优性）最优性）设设X0与与Y0分别是（分别是（LP）与（与（DP）的可行解，则的可行解，则X0、Y0是（是（LP）与（与（DP）的最优解的最优解当且仅当当且仅当C X 0=Y 0b【性质性质4】（对偶性）若互为对偶的两个问题其中一个（对偶性）若互为对偶的两个问题其中一个有优解，则另一个也有最优解，且最优值相同。有优解，则另一个也有最优解，且最优值相同。由性质由性质4 4还可推出另一结论：还可推出另一结论：若若（LPLP）与与（DPDP）都都有有可可行行解解，则则两两者者都都有有最最优解；若一个问题无最优解，则另一问题也无最优解。优解；若一个问题无最优解，则另一问题也无最优解。2.2.1 对偶性质对偶性质24第第2章章对偶理论对偶理论2.2.1 对偶性质对偶性质【性质性质5】（互补松弛定理）（互补松弛定理）X 0、Y 0分别为（分别为（LP）与）与（DP）的可行解，）的可行解，XS 和和YS是它的松弛变量的可行是它的松弛变量的可行解，则解，则X 0和和Y 0是最优解当且仅当是最优解当且仅当YS X 0=0和和Y 0XS=0性质性质5 5表明：表明：在线性规划的最优解中，如果对应某一约束条件的在线性规划的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零。约束条件取严格不等式，则其对应的对偶变量一定为零。Y=(1,1)25第第2章章对偶理论对偶理论【解解】对偶问题是对偶问题是u因因为为x10，x20，所所以以对对偶偶问问题题的的第第一、二个约束取严格等式，即一、二个约束取严格等式，即u解此线性方程组得解此线性方程组得y1=1,y2=1u对偶问题的最优解为对偶问题的最优解为Y=(1,1)，最优值，最优值w=26。2.2.1 对偶性质对偶性质的最优解是的最优解是求对偶问题的最优解。求对偶问题的最优解。【例例2-4】已知线性规划已知线性规划26第第2章章对偶理论对偶理论u因为因为y20，所以原问题第二个约束取严格等式，所以原问题第二个约束取严格等式x1+x2-x3=6u将将y1=0、y2=-2代人对偶问题，得代人对偶问题，得-y1-y2=2y1+y2=-23.2所以丙产品不值得生产所以丙产品不值得生产,只有当利润超过只有当利润超过7/2千元时才值得千元时才值得生产。生产。2.2.2 影子价格影子价格49第第2章章对偶理论对偶理论1.本节介绍的本节介绍的6个性质都是原问题与对偶问题的有关个性质都是原问题与对偶问题的有关解的对应关系；解的对应关系；2.性质性质5和性质和性质6可用来已知一个问题的最优解求另一可用来已知一个问题的最优解求另一个问题的最优解；个问题的最优解；3.第第2章的大部分概念都集中在这一节。章的大部分概念都集中在这一节。下一节：对偶单纯形法下一节：对偶单纯形法2.2.2 影子价格影子价格4.深刻领会影子价格的含义，学会用影子价格作经深刻领会影子价格的含义，学会用影子价格作经济活动分析。济活动分析。本节学习要点50第第2章章对偶理论对偶理论根根据据对对偶偶性性质质6，可可以以构构造造一一个个求求解解线线性性规规划划的的另另一一种种方法，即方法，即对偶单纯形法对偶单纯形法。对对偶偶单单纯纯形形法法的的条条件件是是：初初始始表表中中对对偶偶问问题题可可行行，即极大化问题时即极大化问题时j0，极小化问题时，极小化问题时j0。2.3 对偶单纯形法对偶单纯形法原始问题原始问题对偶问题对偶问题51第第2章章对偶理论对偶理论【例例2-8】用对偶单纯形法求解用对偶单纯形法求解【解解】先将约束不等式化为等式，再两边同乘以（先将约束不等式化为等式，再两边同乘以（1），得到），得到取取x4、x5为基变量，建立初始单纯形表为基变量，建立初始单纯形表2.3 对偶单纯形法对偶单纯形法52第第2章章对偶理论对偶理论XBx1x2x3x4x5b表表(1)x4x5-1-1-11-141001-5-3j-4-1-300表表（2）x2x51-21013-11015-8j-30-2-10表表（3）x2x101105/2-3/2-1/2-1/21/2-1/214j00-13/2-5/2-3/2表表2-7最优解最优解X(4，1，0)T；最优值；最优值Z=172.3 对偶单纯形法对偶单纯形法53第第2章章对偶理论对偶理论对偶单纯形法的计算步骤：对偶单纯形法的计算步骤：（1）将将线线性性规规划划的的约约束束化化为为等等式式，取取对对偶偶可可行行基基B（全全部部检检验验数数j0（max）或或j0（min），模模型型为为典典式式）建建立立初初始始单单纯纯形表；形表；（2）检检验验：当当基基本本解解可可行行时时，即即常常数数项项列列B-1b0,达达到到最最优优解；若基本解不可行，即解；若基本解不可行，即B-1b中有负数，则要进行换基迭代；中有负数，则要进行换基迭代；（3）换基迭代：换基迭代：先确定出基变量。先确定出基变量。l 行对应的变量行对应的变量xl出基，出基，l 行称为主行；行称为主行；再选进基变量。求最小比值再选进基变量。求最小比值，k所在列所在列对应的变量对应的变量xk出基，第出基，第k列称为主列。列称为主列。2.3 对偶单纯形法对偶单纯形法54第第2章章对偶理论对偶理论若第若第l 行所有元素行所有元素aij0,说明线性规划说明线性规划无可行解无可行解；用初等变换将主元素用初等变换将主元素alk化为化为l，主列的其它元素化为，主列的其它元素化为零，得到新的单纯形表；零，得到新的单纯形表；重重复复（2）、（3），直直到到得得出出最最优优解解或或判判断断无无可可行行解。解。2.3 对偶单纯形法对偶单纯形法55第第2章章对偶理论对偶理论2.3 对偶单纯形法对偶单纯形法【例例2-9】用对偶单纯形法求解用对偶单纯形法求解【解解】取取x3、x4为初始基变量为初始基变量56第第2章章对偶理论对偶理论表表28XBx1x2x3x4b表表（1）x3x42112100122j7300表表（2）x2x42310120126j13030第第二二张张表表中中x4=60且且第第二二行行的的元元素素全全部部大大于于等等于于零，说明原问题无可行解。零，说明原问题无可行解。2.3 对偶单纯形法对偶单纯形法57第第2章章对偶理论对偶理论2.3 对偶单纯形法对偶单纯形法注意：注意：（1）用用对对偶偶单单纯纯形形法法求求解解线线性性规规划划是是一一种种求求解解方方法法，而不是去求对偶问题的最优解而不是去求对偶问题的最优解；换基迭代换基迭代B-1b0C-CBB-1A0B为可行基为可行基 单纯形法单纯形法对偶单纯形法对偶单纯形法换基迭代换基迭代C-CBB-1A0B-1b0B为对偶可行基为对偶可行基58第第2章章对偶理论对偶理论（2）最小比值中）最小比值中的绝对值是使得比值非负；的绝对值是使得比值非负；（3）对对偶偶单单纯纯形形法法与与普普通通单单纯纯形形法法换换基基时时主主元元素素的的选选取取不不一一样样，对对偶偶单单纯纯形形法法的的主主元元素素始始终终为为负负数数，普普通通单单纯形法的主元素始终为纯形法的主元素始终为正数正数。2.3 对偶单纯形法对偶单纯形法59第第2章章对偶理论对偶理论其目的是保证下一个其目的是保证下一个对偶问题的基本解可行对偶问题的基本解可行；（4）普通单纯形法的最小比值是）普通单纯形法的最小比值是其目的是保证下一个其目的是保证下一个原问题的基本解可行原问题的基本解可行，对偶单纯形法的最，对偶单纯形法的最小比值是小比值是（5）对偶单纯形法在确定出基变量时，若不遵循）对偶单纯形法在确定出基变量时，若不遵循 规则，任选一个小于零的规则，任选一个小于零的bi 对应的基变量出基，不影响计算结果，对应的基变量出基，不影响计算结果，只是迭代次数可能不一样只是迭代次数可能不一样2.3 对偶单纯形法对偶单纯形法60第第2章章对偶理论对偶理论本节介绍了一种特殊线性规划的求解方法本节介绍了一种特殊线性规划的求解方法对偶对偶单纯形法。单纯形法。1.对偶单纯形法的应用条件；对偶单纯形法的应用条件；2.出基与进基的顺序；出基与进基的顺序；3.如何求最小比值；如何求最小比值；4.最优解、无可行解的判断。最优解、无可行解的判断。下一节：灵敏度分析与参数分析下一节：灵敏度分析与参数分析2.3 对偶单纯形法对偶单纯形法本节学习要点61第第2章章对偶理论对偶理论线线性性规规划划的的灵灵敏敏度度分分析析也也称称为为敏敏感感性性分分析析，它它是是研研究究和和分分析析参参数数（cj，bi，aij）的的波波动动对对最最优优解解的的影响程度，主要研究下面几个方面的问题：影响程度，主要研究下面几个方面的问题：（1）参参数数在在什什么么范范围围内内变变化化时时，原原最最优优解解或或最最优优基基不变；不变；（2）当参数已经变化时，最优解或最优基有何变化。）当参数已经变化时，最优解或最优基有何变化。当当模模型型的的参参数数发发生生变变化化后后，可可以以不不必必对对线线性性规规划划问问题题重重新新求求解解，而而用用灵灵敏敏度度分分析析方方法法直直接接在在原原线线性性规规划取得的最优结果的基础上进行分析或求解。划取得的最优结果的基础上进行分析或求解。2.4 灵敏度分析灵敏度分析62第第2章章对偶理论对偶理论【例例2-10】某企业用三种资源生产三种产品，消耗系数、某企业用三种资源生产三种产品，消耗系数、资源限量及价值系数如下表：资源限量及价值系数如下表：求总利润最大的生产方案。求总利润最大的生产方案。产品产品资源资源ABC资源限量资源限量112401212001115单件产品利润单件产品利润1132.4 灵敏度分析灵敏度分析63第第2章章对偶理论对偶理论【解解】建建立立模模型型，加加入入松松弛弛变变量量x4,x5,x6，用用单单纯纯形形法法求解得最优表求解得最优表表表29Cj113000bCBXBx1x2x3x4x5x60 x402011151x111001153x301100115j030012最优解最优解X=(5，0，15，5，0，0)T;最优值最优值Z=50。对偶问题最优解对偶问题最优解Y=(0,1,2)2.4 灵敏度分析灵敏度分析64第第2章章对偶理论对偶理论设线性规划设线性规划其中其中Amn，线性规划存在最优解，单纯形表为线性规划存在最优解，单纯形表为最优基最优基B的逆矩阵为的逆矩阵为 检验数为检验数为2.4.1 价值系数价值系数cj的变化分析的变化分析2.4 灵敏度与参数分析灵敏度与参数分析XbXBB-1AB-1bC-CBB-1A65第第2章章对偶理论对偶理论（1）cj 是非基变量是非基变量xj 的系数的系数 即即cj 的的增增量量不不超超过过xj 的的检检验验数数的的相相反反数数时时，最最优优解解不变，否则最优解就要改变。不变，否则最优解就要改变。所以所以当当cj变化为变化为要使最优解不变，则检验数应仍然是小于等于零，即要使最优解不变，则检验数应仍然是小于等于零，即这时分这时分cj是是非基变量非基变量和和基变量基变量的系数两种情况讨论。的系数两种情况讨论。2.4.1 价值系数价值系数 cj 的变化分析的变化分析66第第2章章对偶理论对偶理论（2）ci 是基变量是基变量xi 的系数的系数令令 因因ciCB，所以每个检验数所以每个检验数j中含有中含有c i,当当c i变化为变化为c ici 时，时，所有非基变量的检验数所有非基变量的检验数j同时变化同时变化2.4.1 价值系数价值系数 cj 的变化分析的变化分析67第第2章章对偶理论对偶理论要使得所有要使得所有，则有，则有只要求出上限只要求出上限2及下限及下限1就可以求出就可以求出ci的变化区间。的变化区间。即即ci 的增量的增量ci在此区间内变化时，最优解不变，否则在此区间内变化时，最优解不变，否则最优解就要改变。最优解就要改变。2.4.1 价值系数价值系数 cj 的变化分析的变化分析68第第2章章对偶理论对偶理论【例例】对对例例2-10分分别别求求c1,c2,c3的的变变化化范范围围，使使得得最优解不变。最优解不变。2.4.1 价值系数价值系数 cj 的变化分析的变化分析69第第2章章对偶理论对偶理论【解解】表表29Cj113000bCBXBx1x2x3x4x5x60 x402011151x111001153x301100115j030012最优解最优解X=(5，0，15)T;最优值最优值Z=50。2.4.1 价值系数价值系数 cj 的变化分析的变化分析70第第2章章对偶理论对偶理论c1对应的变量对应的变量x1为基变量：最优表中为基变量：最优表中x1对应行的系数只有一个负对应行的系数只有一个负数数,有两个正数有两个正数c1的变化范围是：的变化范围是：2.4.1 价值系数价值系数 cj 的变化分析的变化分析 x2为非基变量，则为非基变量，则c2变化范围是：变化范围是：71第第2章章对偶理论对偶理论c3无上界，即有无上界，即有c32，c3的变化范围是的变化范围是对于对于c3：最优表中：最优表中x3对应行对应行2.4.1 价值系数价值系数 cj 的变化分析的变化分析72第第2章章对偶理论对偶理论对对c3的变化范围，也可直接从最优表推出。将的变化范围，也可直接从最优表推出。将c3=3写成写成分别计算非基变量的检验数并令其小于等于零。分别计算非基变量的检验数并令其小于等于零。2.4.1 价值系数价值系数 cj 的变化分析的变化分析73第第2章章对偶理论对偶理论得得c32，即，即同理，用此方法可求出同理，用此方法可求出c2和和c1的变化区间。的变化区间。要使要使 同时小于等于零，解不等式组同时小于等于零，解不等式组2.4.1 价值系数价值系数 cj 的变化分析的变化分析74第第2章章对偶理论对偶理论常数项常数项b的变化与检验数的变化与检验数C-CBB-1A无关，但会导致基变无关，但会导致基变量量XB=B-1b的变化，若变化后的的变化，若变化后的B满足满足则则B仍为最优基。仍为最优基。设设br的增量为的增量为br，b的增量为的增量为要使最优基要使最优基B不变，即要使不变，即要使2.4.2 资源限量资源限量bi 的灵敏度分析的灵敏度分析75第第2章章对偶理论对偶理论因为因为所以所以 76第第2章章对偶理论对偶理论令令2.4.2 资源限量资源限量bi的灵敏度分析的灵敏度分析因而要使得所有因而要使得所有必须满足必须满足 即即br的增量的增量br在此区间内变化时，最优基不变，否则最在此区间内变化时，最优基不变，否则最优基就要改变。优基就要改变。注意：注意：u 最优基不变不等于最优解不变。最优基不变不等于最优解不变。u br在在允许范围内变化只能说明产品结构不变，但生产量允许范围内变化只能说明产品结构不变，但生产量 有可能改变。有可能改变。77第第2章章对偶理论对偶理论 【解解】由表由表29知，最优基知，最优基B、B1及及XB分别为分别为对于对于b1：比值的分母取比值的分母取B1的第一列，则的第一列，则b1无无上上界界，即即b15，因因而而b1在在35,+)内内变变化化时时最最优优基基不变。不变。【例例2-11】求求例例2-10的的b1、b2、b3分分别别在在什什么么范范围围内内变变化化时时，原原最优基不变。求最优基不变。求b2由由20变为变为24时的最优解。时的最优解。Cj113000bCBXBx1x2x3x4x5x60 x402011151x111001153x301100115j03001278第第2章章对偶理论对偶理论对于对于b2：比值的分母取比值的分母取B1的第二列，的第二列，120，220，则，则即即b215，25时最优基不变时最优基不变此时，最优解为此时，最优解为X=(9,0,15)T，最优值，最优值Z=5479第第2章章对偶理论对偶理论对于对于b3：比值的分母取比值的分母取B1的第三列，有的第三列，有故有故有15b35，b30，20时最优基不变。时最优基不变。若若线线性性规规划划模模型型是是一一个个生生产产计计划划模模型型，当当求求出出cj或或bi的的最最大大允允许许变变化化范范围围时时，就就可可随随时时根根据据市市场场的的变变化化来来掌握生产计划的调整。掌握生产计划的调整。2.4.2 资源限量资源限量bi 的灵敏度分析的灵敏度分析80第第2章章对偶理论对偶理论2.4.2 资源限量资源限量bi 的灵敏度分析的灵敏度分析【补充例补充例】求例求例2-10的的b2由由20变为变为30时的最优解。时的最优解。【解解】由例由例2-11知知b2的变化范围是的变化范围是15，25即即b2=30时，在范围之外时，在范围之外XB不可行，原方案不再是最优方案不可行，原方案不再是最优方案在原最优表的基础上用对偶单纯形法求解在原最优表的基础上用对偶单纯形法求解81第第2章章对偶理论对偶理论2.4.2 资源限量资源限量bi 的灵敏度分析的灵敏度分析表表29Cj113000bCBXBx1x2x3x4x5x60 x4020111-51x1110011153x301100115j030012最优解最优解X=(10，0，15，0，5，0)T，最优值最优值Z=55。0 x5020-11151x11-1010-2103x3011001150-10-10-182第第2章章对偶理论对偶理论 说明：说明：u 上上述述cj及及bi的的最最大大允允许许变变化化范范围围是是假假定定其其它它参参数数不不变变的的前前提提下下，单单个个参参数数的的变变化化范范围围，当当几几个个参参数数同同时时在各自范围内变化时，最优解或最优基有可能改变。在各自范围内变化时，最优解或最优基有可能改变。u灵灵敏敏度度分分析析的的关关键键在在于于线线性性规规划划某某些些参参数数或或条条件件发发生生变变化化时时，需需要要判判断断最最优优表表中中哪哪些些数数据据发发生生了了变变化化，如如何何求求这这些些数数据据，如如果果不不是是最最优优解解再再用用什什么么方方法法计计算算等等问问题题。前前两两个个问问题题可可以以直直接接用用1.5的的矩矩阵阵公公式式判判断断和计算。将这些问题简要综合在表和计算。将这些问题简要综合在表2-15中。中。2.4.2 资源限量资源限量bi 的灵敏度分析的灵敏度分析83第第2章章对偶理论对偶理论2.4.3 综合分析综合分析灵灵敏敏度度分分析析方方法法还还可可以以分分析析工工艺艺系系数数aij的的变变化化对对最最优优解解的的影影响响，对对增增加加约约束束、变变量量或或减减少少约约束束、变变量量等等情形的分析。情形的分析。84第第2章章对偶理论对偶理论【例例2-12】考虑下列线性规划考虑下列线性规划求求出出最最优优解解后后，分分别别对对下下列列各各种种变变化化进进行行灵灵敏敏度度分分析析，求求出出变化后的最优解。变化后的最优解。（1）改变右端常数为）改变右端常数为:2.4.3 综合分析综合分析85第第2章章对偶理论对偶理论（2）改变目标函数）改变目标函数x3的系数为的系数为c3=1;（3）改变目标函数中）改变目标函数中x2的系数为的系数为c2=2；（4）改变）改变x2的系数为的系数为（5）改变约束（）改变约束（1）为）为（6）增加新约束）增加新约束（7）增加新约束）增加新约束2.4.3 综合分析综合分析86第第2章章对偶理论对偶理论【解解】加入松弛变量加入松弛变量x4、x5、x6，用单纯形法计算，最优表如下用单纯形法计算，最优表如下表表210Cj2-14000bCBXBx1x2x3x4x5x64x305/711/73/7022x112/701/74/7010 x60200111j031/702/720/70最优解最优解X=（1，0，2，0，0，1）T，最优值最优值Z=102.4.3 综合分析综合分析87第第2章章对偶理论对偶理论最优基矩阵及其逆矩阵为最优基矩阵及其逆矩阵为（1）基变量的值为）基变量的值为基基本本解解不不可可行行，将将求求得得的的XB代代替替表表210中中的的常常数数项项，用用对对偶偶单纯形法求解，其结果见表单纯形法求解，其结果见表211所示。所示。2.4.3 综合分析综合分析88第第2章章对偶理论对偶理论表表211Cj214000bCBXBx1x2x3x4x5x64x305/711/73/7022/72x112/701/74/706/70 x60200112j031/702/720/704x30011/71/145/1417/72x11001/73/71/74/71x201001/21/21j0002/79/1431/142.4.3 综合分析综合分析最优解最优解89第第2章章对偶理论对偶理论（2）由表）由表210容易得到基变量容易得到基变量x3的系数的系数c3的增量变化范围是的增量变化范围是而而c3=1在允许的变化范围之外，故表在允许的变化范围之外，故表210的解不是最优解。的解不是最优解。计算非基变量的检验数计算非基变量的检验数x4进基，用单纯形法计算，得到表进基，用单纯形法计算，得到表2122.4.3 综合分析综合分析90第第2章章对偶理论对偶理论表表212XBx1x2x3x4x5x6bx305/711/73/702x112/701/74/701x60200111j016/701/711/70 x405713014x11110103x60200111j031020最优解为最优解为X=（3，0，0，14，0，1)T，最优值，最优值z=6。2.4.3 综合分析综合分析91第第2章章对偶理论对偶理论2.4.3 综合分析综合分析方法方法2：直接求出直接求出x2的检验数的检验数（3）c2是非基变量是非基变量x2的系数，由表的系数，由表27知，知，由由1变为变为2时，时，从而最优解不变。，从而最优解不变。方法方法2：直接求出直接求出x2的检验数的检验数（3）c2是非基变量是非基变量x2的系数，由表的系数，由表27知，知，由由1变为变为2时，时，从而最优解不变。，从而最优解不变。方法方法2：直接求出直接求出x2的检验数的检验数（3）c2是非基变量是非基变量x2的系数，由表的系数，由表27知，知，由由1变为变为2时，时，从而最优解不变。，从而最优解不变。92第第2章章对偶理论对偶理论(4)这这时时目目标标函函数数的的系系数数和和约约束束条条件件的的系系数数都都变变化化了了，同同样样求出求出2判别最优解是否改变。判别最优解是否改变。x2进基，计算结果如表进基，计算结果如表213所示所示2.4.3 综合分析综合分析93第第2章章对偶理论对偶理论表表213Cj234000bCBXBx1x2x3x4x5x64x30011/73/7022x11101/74/7010 x60300111j0502/720/704x30011/73/7022x11001/75/211/34/33x201001/31/31/3j0002/725/215/3最优解最优解2.4.3 综合分析综合分析94第第2章章对偶理论对偶理论（5）第第一一个个约约束束变变为为实实际际上上是是改改变变了了a12及及b1，这时要求这时要求2及及XB，判断解的情况。判断解的情况。因为因为可行，所以可行，所以最优基不变最优基不变，最优解为最优解为2.4.3 综合分析综合分析95第第2章章对偶理论对偶理论。（6）先先验验证证最最优优解解X=(1,0,2)是是否否满满足足该该约约束束，若若满满足，最优解不变。足，最优解不变。（不满足）（不满足）引入松弛变量引入松弛变量x7得得 x1、x3是基变量，利用表是基变量，利用表210消去消去x1、x3，得得 x7为为新新的的基基变变量量，将将上上式式加加入入表表210中中用用对对偶偶单单纯纯形形法法迭代得到表迭代得到表2-14。2.4.3 综合分析综合分析96第第2章章对偶理论对偶理论XBx1x2x3x4x5x6x7bx305/711/73/7002x112/701/74/7001x602001101x7013/7011/72/7012j031/702/720/700 x306/11105/1101/1120/11x115/11006/1101/1113/11x602001101x4013/11012/1107/1114/11j045/110032/1102/11表表214最优解最优解2.4.3 综合分析综合分析97第第2章章对偶理论对偶理论（7）将原最优解代入约束）将原最优解代入约束的左边有的左边有5122=118时表时表2-17(1)仍然是最优表仍然是最优表,最优解是参数的函数最优解是参数的函数 X（8，9+0.5，0）,目标值目标值Z67+1.5(2)当当18时最优解时最优解X（8，0，0），目标值），目标值Z40(3)当当18时不可行，用对偶单纯形法，时不可行，用对偶单纯形法，x2出基出基x5进基得到进基得到表表2-17(2)，当，当3018时最优解时最优解X=（20+2/3，0，0），最优值），最优值Z100+10/3(4)当当30时无可行解目标函数与参数时无可行解目标函数与参数的关系如图的关系如图2.1所示所示104第第2章章对偶理论对偶理论同理，当目标函数中含有参数时，先令参数等于零，再用公同理，当目标函数中含有参数时，先令参数等于零，再用公式求出检验数，分析参数在不同区间解的关系式求出检验数，分析参数在不同区间解的关系图图2.1目标值目标值Z(30,0)(18,40)(0,67)2.4.4参数分析参数分析105第第2章章对偶理论对偶理论TheEndofChapter21.注意最优解与最优基不变的区别；注意最优解与最优基不变的区别；2.掌握某个参数变化后，最优表中哪些数据会发生变化，如何掌握某个参数变化后，最优表中哪些数据会发生变化，如何变化；变化；3.模型发生变化后不是重新求解，而是在原模型的最优表中求模型发生变化后不是重新求解，而是在原模型的最优表中求出变化后的数据，根据变化条件，选择合适的方法继续计算。出变化后的数据，根据变化条件，选择合适的方法继续计算。4.了解参数分析的思路。了解参数分析的思路。5.利用利用WinQSB软件中的修改（软件中的修改（Modifyproblem）和）和PerformParametricAnalysis功能，进行灵敏度分析和参数分析。功能，进行灵敏度分析和参数分析。2.4.4 参数分析参数分析本节学习要点106第第2章章对偶理论对偶理论