运筹学胡运权第五版课件(第二章)ppt.ppt

《运筹学胡运权第五版课件(第二章)ppt.ppt》由会员分享，可在线阅读，更多相关《运筹学胡运权第五版课件(第二章)ppt.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统第二章第二章 线性规划的对偶理论线性规划的对偶理论Dual Theory篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2.1 对偶问题的提出对偶问题的提出 例例 常山机器厂生产常山机器厂生产 I I、IIII 两种产品。这两种产品两种产品。这两种产品都分别要在都分别要在ABCABC三种不同设三种不同设备上加工。按工艺规定，生备上加工。按工艺规定，生产每件产品的单位利润、消产每件产品的单位利润、消耗三种设备的工时以及各种耗三种设

2、备的工时以及各种设备工时的限额如表设备工时的限额如表：如何安排生产才能使如何安排生产才能使如何安排生产才能使如何安排生产才能使总的利润最大？总的利润最大？总的利润最大？总的利润最大？消耗设备消耗设备工时工时I IIIII设备工时限设备工时限量量 设备设备A A设备设备B B设备设备C C240205121615利润（元）利润（元）23解：max z=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x10，x2 0 s.t.LP1篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 假设另有四海机器厂想租借常山机器厂

3、的全部可用资源进假设另有四海机器厂想租借常山机器厂的全部可用资源进行生产。问：常山机器厂应该如何给这些资源定出一个合理行生产。问：常山机器厂应该如何给这些资源定出一个合理的租金，既使四海机器厂愿意租借，又使本厂能得到自己组的租金，既使四海机器厂愿意租借，又使本厂能得到自己组织生产这些产品时所能获得的最大收益。织生产这些产品时所能获得的最大收益。解：设解：设A、B、C设备每小时出租的价格分别为设备每小时出租的价格分别为y1、y2、y3元元，则新的线性规划数学模型为：则新的线性规划数学模型为：LP2篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类

4、型的系统 对偶性是线性规划问题的最重要的内容之一。对偶性是线性规划问题的最重要的内容之一。每一个线性规划（每一个线性规划（LP1 ）必然有与之相伴而生的另一）必然有与之相伴而生的另一个线性规划问题（个线性规划问题（LP2 ），即任何一个求），即任何一个求 max z 的的LP1都都有一个求有一个求 min w的的LP2 。将将LP1称为称为“原问题原问题”，记为，记为P P；将将LP2称为称为“对偶问题对偶问题”，记为，记为D D。原问题（原问题（P P）：）：对偶问题（对偶问题（D D）：）：1 1、基本概念、基本概念篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛

5、的计时计分系统是一种得分类型的系统原问题 P对偶问题 D原变量 x1,x2对偶变量 y1,y2,y3原目标 z对偶目标 w原约束对偶约束变量变量 约束约束篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2、一般形式原问题原问题P max z=c1 x1+c2 x2+cn xn s.t.a11 x1+a12 x2+a1n xn b1 a21 x1+a22 x2+a2n xn b2 am1 x1+am2 x2+amn xn bm xj 0，（j=1,2,n）对偶问题对偶问题D min w=b1 y1+b2 y2+bm ym s.t.a11

6、 y1+a21 y2+am1 ym c1 a12 y1+a22 y2+am2 ym c2 a1n y1+a2n y2+amn ym cn yi 0，(i=1,2,m)篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统其中 篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统例：写出下列例：写出下列LPLP问题的对偶问题问题的对偶问题解：对偶问题为：解：对偶问题为：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2.2 原问

7、题与对偶问题（max的基本形式）的基本形式）（min的基本形式）的基本形式）1 1、基本形式的联系与区别、基本形式的联系与区别（1 1）原目标求极大，对偶目标求极小；）原目标求极大，对偶目标求极小；（2 2）原约束个数）原约束个数=对偶变量个数对偶变量个数 原变量个数原变量个数=对偶约束个数对偶约束个数 原约束决定对偶变量原约束决定对偶变量 原变量决定对偶约束原变量决定对偶约束；（3 3）原约束）原约束方向，对偶约束方向，对偶约束方向；方向；（4）原目标的系数对应对偶约束的右端常数）原目标的系数对应对偶约束的右端常数 原约束的右端常数对应对偶目标的系数；原约束的右端常数对应对偶目标的系数；（5

8、）原系数矩阵与对偶系数矩阵互为转置；）原系数矩阵与对偶系数矩阵互为转置；（6）原变量与对偶变量都是非负取值。）原变量与对偶变量都是非负取值。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统例 将下列问题作为原问题，写出其对偶问题。解：先改写为原问解：先改写为原问题的基本形式：题的基本形式：再对偶化：再对偶化：最后简化得到已知问最后简化得到已知问题的对偶问题：题的对偶问题：2、基本形式的表格比较篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统3、互为对偶关系若LP2是LP1的对

9、偶问题，则LP1是LP2的对偶问题。min Z=-CXs.t.-AX-bX 0 min W=b TYs.t.AT Y CT Y 0max Z=C Xs.t.AXb X 0对偶的定义对偶的定义对偶的定义对偶的定义max W=-bTYs.t.-ATY-CT Y 0改写改写改写改写篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统例 写出下列问题的对偶问题。解：第一步解：第一步 改写为改写为min 的基本形式的基本形式篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统第二步 对偶化第三

10、步 简化为已知问题的对偶问题：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统比较原问题和对偶问题：基本形式基本形式非基本形式非基本形式篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统4 4、原问题与对偶问题的互化、原问题与对偶问题的互化原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max（基本）（基本）目标函数目标函数 min（基本）（基本）约约束束条条件件m个个m个个变变量量（基本）（基本）0 0（基本）（基本）00=无

11、约束无约束变变量量n个个n个个约约束束条条件件0 0（基本）（基本）（基本）（基本）00无约束无约束=约束条件的右端项约束条件的右端项目标函数的系数目标函数的系数目标函数的系数目标函数的系数约束条件的右端项约束条件的右端项篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统例例 直接写出下列线性规划问题的对偶问题。直接写出下列线性规划问题的对偶问题。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统练习练习 写出下列问题的对偶问题。写出下列问题的对偶问题。解：对偶问题为：解：对偶问

12、题为：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2.3 对偶问题的基本性质在本节中设原问题和对偶问题如下：在本节中设原问题和对偶问题如下：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1 1、弱对偶性（弱对偶原理）：设、弱对偶性（弱对偶原理）：设 和和 分别是问题分别是问题P P和和D D的可行解，则必有的可行解，则必有证明：证明：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 2、最优性：若 X*和 Y*

13、分别是 P 和 D 的可行解且 CX*=bT Y*，则X*，Y*分别是问题 P和D 的最优解。证明：证明：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统3、无界性若原问题有无界解，则对偶问题无可行解。若原问题有无界解，则对偶问题无可行解。若对偶问题有无界解，则原问题无可行解。若对偶问题有无界解，则原问题无可行解。证明：注：逆定理不成立。注：逆定理不成立。即即“如果原问题无可行解，那么对偶问题有无界解如果原问题无可行解，那么对偶问题有无界解”不成立。不成立。此时，对偶问题可能有无界解，也可能无可行解。此时，对偶问题可能有无界解，也可能

14、无可行解。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统4、强对偶性（对偶定理）若原问题有最优解，则对偶问题一定有最优解，且 zmax=wmin.证：设设X*是原问题的是原问题的最优解，则所有检验数都非正。最优解，则所有检验数都非正。即即 =C-CB B-1 A 0 CB B-1 A C令令 CBB-1=Y*T，有，有 Y*T A C,转置得转置得A TY*CT -又因为又因为 S=-CBB-1=-Y*T 0，所以，所以Y*=-（S）T 0-由由知知Y*是对偶问题的可行解，是对偶问题的可行解，而而 CX*=CB b，其满足其满足:C

15、X*=CB(B-1 b)=CB B-1b=Y*T b=b TY*由最优性由最优性(性质性质2)，Y*是对偶问题的是对偶问题的最优解。最优解。注意：若原问题有最优解，则在最终单纯形表中，原问题的最优解注意：若原问题有最优解，则在最终单纯形表中，原问题的最优解是第三列，而对偶问题的最优解是松弛变量检验数的相反数。是第三列，而对偶问题的最优解是松弛变量检验数的相反数。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 4 4 22 X1 0 X5 3 X2 x1

16、x2 x3 x4 x5 CB XB b 2 3 0 0 0 Cj 0 0 -3/2 -1/8 0篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5、互补松弛性证明：证明：松条件松条件-变量变量0 0，约束为等式；，约束为等式；紧条件紧条件-变量变量=0=0，约束不等式。，约束不等式。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统将该性质应用于其对偶问题时，则有：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统例 考

17、虑下面问题篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统解:则篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统6、P和D之间存在一对互补的基解（1 1）原问题的变量对应于对偶问题的剩余变）原问题的变量对应于对偶问题的剩余变量，原松弛变量对应对偶变量；量，原松弛变量对应对偶变量；（2 2）互相对应的变量在一个问题中是基变量，）互相对应的变量在一个问题中是基变量，在另一个问题中是非基变量；在另一个问题中是非基变量；（3 3）互补的基解对应的目标函数值相等。）互补的基解对应的目标

18、函数值相等。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统原问题原问题对偶问题对偶问题原变量x1,x2对偶剩余变量y4,y5原松弛变量x3,x4,x5对偶变量y1,y2,y3篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统例 对比两个互为对偶问题间的互补基解。序序号号原问题原问题P目标目标函数函数值值对偶问题对偶问题Dx1x2x3x4x5基可基可行解行解？y1y2y3y4y5基可基可行解行解？1 14 43 3-2-20 00 017170 01/21/23/53/50 0

19、0 02 23 33 30 04 40 01515*1 10 01/51/50 00 0(15(15)3 34 42 20 00 05 514143/23/2-1/4-1/40 00 00 04 44 40 04 40 015158 80 01/21/20 00 0-3-35 56 60 00 0-8-8151512121 10 00 00 0-1-16 60 03 36 616160 09 90 00 03/53/5-2-20 07 70 06 60 01616-15-1518183/23/20 00 01 10 08 80 00 01212161615150 00 00 00 0-2-2-

20、3-3篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统利用一对互补的基解，判定目标函数的大小：利用一对互补的基解，判定目标函数的大小：目标函数值目标函数值原问题原问题P可行解可行解非可行解非可行解对偶问题对偶问题D可行解可行解最优最优zmaxzzmax非可行解非可行解zzmax不确定不确定篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统小结利用对偶问题的基本性质确定最优解的方法：性质性质2 2（最优性）一对使目标函数相等的可行解为（最优性）一对使目标函数相等的可行解为最优解。

21、最优解。性质性质4 4（强对偶性）最终表中原问题的最优解在第（强对偶性）最终表中原问题的最优解在第三列，对偶问题的最优解是松弛变量的检验数的三列，对偶问题的最优解是松弛变量的检验数的相反数。相反数。性质性质5 5（互补松弛性）（互补松弛性）性质性质6 6（互补的基解）一对可行的互补基解为最优（互补的基解）一对可行的互补基解为最优解。解。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统例例 判断下列说法是否正确：判断下列说法是否正确：（1 1）若线性规划的原问题有可行解，则对偶问题）若线性规划的原问题有可行解，则对偶问题一定有可行解。一

22、定有可行解。（2 2）若线性规划的对偶问题无可行解，则原问题）若线性规划的对偶问题无可行解，则原问题一定无可行解。一定无可行解。（3 3）在互为对偶的一对原问题和对偶问题中，不）在互为对偶的一对原问题和对偶问题中，不管原问题是求极大还是求极小，原问题可行解的目管原问题是求极大还是求极小，原问题可行解的目标函数值一定不超过对偶问题可行解的目标函数值。标函数值一定不超过对偶问题可行解的目标函数值。（4 4）任何线性规划问题都有唯一的对偶问题）任何线性规划问题都有唯一的对偶问题（）（）（）（）篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统

23、1 1、定义、定义对于一对互补的基解，总满足对于一对互补的基解，总满足2.4 2.4 影子价格影子价格其中，其中，bi是线性规划原问题约束条件的右端项，表示第是线性规划原问题约束条件的右端项，表示第i种种资源的拥有量；资源的拥有量；对偶变量对偶变量yi表示对一个单位的第表示对一个单位的第i种资源在生产中做出种资源在生产中做出贡献的估价，称为第贡献的估价，称为第i种资源的影子价格（种资源的影子价格（shadow price）.注意：影子价格不是资源的市场价格。注意：影子价格不是资源的市场价格。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的

24、系统2 2、性质、性质（1）资源的市场价格随市场供求变化，通常是稳定的；）资源的市场价格随市场供求变化，通常是稳定的；影子价格随资源的利用情况变化，通常是不稳定的。影子价格随资源的利用情况变化，通常是不稳定的。（2）影子价格是一种边际价格。）影子价格是一种边际价格。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统例例 已知已知P PQ(4,2)x1x24x1=164x2=12x1+2x2=944083Z=14Q(4.25,1.875)Z=14.125Q(4,2.5)Z=15.5Q(4,2)Z=14x1+2x2=84x1=174x2=1

25、3当b1变化1个单位时，z增加1.5，对应y1=1.5；当b2变化1个单位时，z增加0.125，对应y2=0.125；当b3变化1个单位时，z无变化，对应y3=0.P和D的最优解分别为：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统（3）影子价格是一种机会成本。）影子价格是一种机会成本。假设第假设第i种资源的单位市场价格为种资源的单位市场价格为mi ，影子价格为，影子价格为yi 。当当yi mi 时，企业愿意购进这种资源，单位纯利为时，企业愿意购进这种资源，单位纯利为yimi，即有利可图；即有利可图；当当yi mi 时，企业愿意有偿

26、转让这种资源，可获单位纯利为时，企业愿意有偿转让这种资源，可获单位纯利为miyi，否则企业无利可图，甚至亏损；，否则企业无利可图，甚至亏损；当当yi=mi 时，处于平衡状态。时，处于平衡状态。（4）互补松弛性）互补松弛性在最优配置下，若资源在最优配置下，若资源bi未充分利用，则影子价格未充分利用，则影子价格yi为为0；若影子价格若影子价格yi大于大于0，则该资源，则该资源bi已经利用完。已经利用完。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统（5）检验数的经济意义）检验数的经济意义 其中，其中，cj代表第代表第j j种产品的产值；

27、种产品的产值；是生产一个单位该种产品所消耗的是生产一个单位该种产品所消耗的各项资源的影子价格的总和，称为产品的隐含成本。各项资源的影子价格的总和，称为产品的隐含成本。当该项产品的产值大于隐含成本时，表示生产该产品当该项产品的产值大于隐含成本时，表示生产该产品有利，可在计划中安排；否则不在计划中安排。有利，可在计划中安排；否则不在计划中安排。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 （2 2）使管理者了解花多大代价买进资源或卖出资源是合适的）使管理者了解花多大代价买进资源或卖出资源是合适的 3 3、影子价格的意义、影子价格的意义

28、（1 1）使管理者掌握增加何种资源对企业更有利）使管理者掌握增加何种资源对企业更有利 （3 3）为新产品定价提供依据）为新产品定价提供依据（4 4）使有限资源发挥更大的经济效益）使有限资源发挥更大的经济效益篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2.6 2.6 灵敏度分析灵敏度分析1 1概念概念 广义：对系统或事物因周围条件变化显示出来的敏感程广义：对系统或事物因周围条件变化显示出来的敏感程度的分析。度的分析。狭义：在线性规划问题中，分析一个或多个参数发生变狭义：在线性规划问题中，分析一个或多个参数发生变化时，最优解将如何改变

29、；或者分析参数在一个怎样的范围化时，最优解将如何改变；或者分析参数在一个怎样的范围内变化时，最优解不变。内变化时，最优解不变。其中可以改变的参数有：其中可以改变的参数有：cj 目标函数系数的变化，即市场条件的改变；目标函数系数的变化，即市场条件的改变；bi 约束右端项的变化，即资源拥有量的改变；约束右端项的变化，即资源拥有量的改变；Pj 约束左端系数的变化，即工艺技术条件的改变。约束左端系数的变化，即工艺技术条件的改变。其他的变化例如：增加一种新产品、增加一道新工序等。其他的变化例如：增加一种新产品、增加一道新工序等。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的

30、计时计分系统是一种得分类型的系统2 2步骤步骤 （1）cj的变化：直接反映到最终表中，重新计算检验数。的变化：直接反映到最终表中，重新计算检验数。（2）bi的变化：的变化：（b+b）=B-1（b+b）=B-1 b+B-1 b =b+（b)(b)=B-1 b（3）Pj的变化：的变化：（Pj+Pj）=B-1（Pj+Pj）=B-1 Pj+B-1 Pj=Pj+(Pj)(Pj)=B-1 Pj（4）增加新产品：即增加一个决策变量，仿照）增加新产品：即增加一个决策变量，仿照Pj变化。变化。（5）增加新工序：即增加一个约束条件，直接反映到最终表中。）增加新工序：即增加一个约束条件，直接反映到最终表中。第一步第

31、一步 利用最终单纯形表将变化后的结果按下述基本原则修利用最终单纯形表将变化后的结果按下述基本原则修改最终表。改最终表。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统第二步第二步 在最终表中分别检查原问题和对偶问题是否为可在最终表中分别检查原问题和对偶问题是否为可行解。行解。若第三列没有负数，则原问题的基解是可行解；若第三列没有负数，则原问题的基解是可行解；若检验数没有正数，则对偶问题的基解是可行解。若检验数没有正数，则对偶问题的基解是可行解。第三步第三步 按下表所列情况进行：按下表所列情况进行：原问题原问题对偶问题对偶问题结论或继续

32、结论或继续可行解可行解可行解可行解仍为最优解仍为最优解可行解可行解非可行解非可行解用单纯形法继续用单纯形法继续非可行解非可行解可行解可行解用对偶单纯形法继用对偶单纯形法继续续(略略)非可行解非可行解非可行解非可行解引入人工变量，用单纯形法继续（略）引入人工变量，用单纯形法继续（略）篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统6-1 分析cj的变化范围 例例 已知线性规划问题如下，试分析已知线性规划问题如下，试分析1和和2 2分别在什么范围分别在什么范围内变化时，问题的最优解不变。内变化时，问题的最优解不变。篮球比赛是根据运动队在规

33、定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统解：当当1=2=0时，上述线性规划问题的最终表为：时，上述线性规划问题的最终表为：Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X2 3 4 3 1 0 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5 0 0 -1 0 -1/5篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统当当2=0时，将时，将1反映到最终表得到反映到最终表得到Cj 2+1 3 0 0 0 CB XB b X1 X2

34、X3 X4 X5 2+1 X1 0 X43 X2 3 4 3 1 0 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5 0 0 -1-1 0 -1/5+1/51 为使表中解为最优解，条件是为使表中解为最优解，条件是即当即当 时，满足要求。时，满足要求。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统当当1=0时，将时，将2反映到最终表得到反映到最终表得到Cj 2 3+2 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X43+2 X2 3 4 3 1 0 0 -1/5 0 0 -2 1 4/5 0

35、 1 0 0 1/5 0 0 -1 0 -1/5-1/52 为使表中解为最优解，条件是为使表中解为最优解，条件是即当即当 时，满足要求。时，满足要求。综上所述，为使最优解不变必须满足：综上所述，为使最优解不变必须满足：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统6-2 分析bi的变化范围 例例 已知线性规划问题如下，试分析已知线性规划问题如下，试分析1，2和和3分别在什么分别在什么范围内变化时，问题的最优基不变。范围内变化时，问题的最优基不变。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统

36、是一种得分类型的系统Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X2 3 4 3 1 0 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5 0 0 -1 0 -1/5解：当解：当1=2=3=0时，上述线性规划问题的最终表为：时，上述线性规划问题的最终表为：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统（1）分析1的影响由公式由公式使问题的最优基不变的条件是：使问题的最优基不变的条件是：解得：解得：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比

37、赛的计时计分系统是一种得分类型的系统（2）分析2的影响由公式由公式使问题的最优基不变的条件是：使问题的最优基不变的条件是：解得：解得：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统（3）分析3的影响由公式由公式使问题的最优基不变的条件是：使问题的最优基不变的条件是：解得：解得：终上所述，使问题的最优基不变的条件是：终上所述，使问题的最优基不变的条件是：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统6-3 增加一个变量的分析例例 已知线性规划问题如下，若增加一个变量已知线性

38、规划问题如下，若增加一个变量x6，而且，而且 试分析试分析问题最优解的问题最优解的变化。变化。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X2 3 4 3 1 0 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5 0 0 -1 0 -1/5解：该解：该线性规划问题的最终表为：线性规划问题的最终表为：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统Cj 2 3 0

39、0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X2 3 4 3 1 0 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5 j 0 0 -1 0 -1/54X60411 -1 3 CB XB b X1 X2 X3 X4 X5 2 X1 4 X6 3 X2 3 1 2 1 0 0 -1/5 0 0 -1/4 1/5 0 1 -1/4 0 j 0 0 -1/4 -2/5 0X6010故新的最优解为故新的最优解为x1=3,x2=2,x6=1,zmax=16注：最优基改变了。注：最优基改变了。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统最优解不变最优解不变最优解改变，最优基不变最优解改变，最优基不变最优基改变最优基改变灵敏度分析的三种常见结果