《运筹学第3章线性规划问题的计算机求解ppt课件》由会员分享，可在线阅读，更多相关《运筹学第3章线性规划问题的计算机求解ppt课件（32页珍藏版）》请在金锄头文库上搜索。
1、 第三章第三章 线性规划问题的线性规划问题的 计算机求解计算机求解如何求解？如何求解？“管理运筹学管理运筹学”的软件包的软件包 本章将介绍如何使用计算机软件包求解线性规划问题。本章将介绍如何使用计算机软件包求解线性规划问题。本章将介绍如何使用计算机软件包求解线性规划问题。本章将介绍如何使用计算机软件包求解线性规划问题。 解决线性规划问题的软件包分两种，一种是大规模解决线性规划问题的软件包分两种，一种是大规模解决线性规划问题的软件包分两种，一种是大规模解决线性规划问题的软件包分两种，一种是大规模的软件包，它可以用来解决复杂的包含数千个决策变量的软件包，它可以用来解决复杂的包含数千个决策变量的软件
2、包，它可以用来解决复杂的包含数千个决策变量的软件包，它可以用来解决复杂的包含数千个决策变量和数千个约束条件的大型的线性规划的问题，重点掌握和数千个约束条件的大型的线性规划的问题，重点掌握和数千个约束条件的大型的线性规划的问题，重点掌握和数千个约束条件的大型的线性规划的问题，重点掌握国内外常用软件：由芝加哥大学国内外常用软件：由芝加哥大学国内外常用软件：由芝加哥大学国内外常用软件：由芝加哥大学LinusELinusESchrageSchrage开发开发开发开发的的的的lindo6.1lindo6.1软件，此软件包可解决软件，此软件包可解决软件，此软件包可解决软件，此软件包可解决320003200
3、0个变量个变量个变量个变量(3200(3200整整整整型变量）型变量）型变量）型变量）1600016000个约束方程的运筹学问题。个约束方程的运筹学问题。个约束方程的运筹学问题。个约束方程的运筹学问题。 另一种是用于微机的软件包，它们有很好的界面，另一种是用于微机的软件包，它们有很好的界面，另一种是用于微机的软件包，它们有很好的界面，另一种是用于微机的软件包，它们有很好的界面，使用方便，由科研机构和小软件公司为解决包含数百个使用方便，由科研机构和小软件公司为解决包含数百个使用方便，由科研机构和小软件公司为解决包含数百个使用方便，由科研机构和小软件公司为解决包含数百个决策变量的线性规划问题而开发
4、的。本章介绍的是与本决策变量的线性规划问题而开发的。本章介绍的是与本决策变量的线性规划问题而开发的。本章介绍的是与本决策变量的线性规划问题而开发的。本章介绍的是与本书配套的名为书配套的名为书配套的名为书配套的名为“ “管理运筹学管理运筹学管理运筹学管理运筹学” ”2.02.0软件包就是属于这种软件包就是属于这种软件包就是属于这种软件包就是属于这种软件，此软件包可解决软件，此软件包可解决软件，此软件包可解决软件，此软件包可解决100100个变量个变量个变量个变量5050个约束方程的管理个约束方程的管理个约束方程的管理个约束方程的管理运筹学问题。运筹学问题。运筹学问题。运筹学问题。 本章的重点放在
5、如何读懂本章的重点放在如何读懂本章的重点放在如何读懂本章的重点放在如何读懂“ “管理运筹学管理运筹学管理运筹学管理运筹学” ”软件包的软件包的软件包的软件包的计算机输出结果计算机输出结果计算机输出结果计算机输出结果关于线性规划问题的求解和灵敏度关于线性规划问题的求解和灵敏度关于线性规划问题的求解和灵敏度关于线性规划问题的求解和灵敏度分析的信息，解决工商管理中的实际问题。分析的信息，解决工商管理中的实际问题。分析的信息，解决工商管理中的实际问题。分析的信息，解决工商管理中的实际问题。3.1“管理运筹学管理运筹学”软件的操作方法软件的操作方法下面用运筹学软件下面用运筹学软件2.0来解决例来解决例1
6、的线性规划问题。的线性规划问题。 从开始从开始程序程序管理运筹学管理运筹学2.0，这样就打开此软件，如下，这样就打开此软件，如下图：图：然后就然后就然后就然后就根据需根据需根据需根据需要选择要选择要选择要选择运筹学运筹学运筹学运筹学的各个的各个的各个的各个分枝分枝分枝分枝 1输入的系数可以是整数、小数，输入的系数可以是整数、小数，但不能是分数，要把分数先化为小数再输入。但不能是分数，要把分数先化为小数再输入。 2输入前先要合并同类项。输入前先要合并同类项。 3、此软件的一个最大缺点是变量只有一组、此软件的一个最大缺点是变量只有一组X，不能有不能有Y和和Z等，而且下标不能是二维下标如：等，而且下
7、标不能是二维下标如：X12是错的（看作是一维）。还有是错的（看作是一维）。还有X1A等也是错等也是错误的，其次模型的修改比较麻烦。误的，其次模型的修改比较麻烦。注意！下面以第二章的例下面以第二章的例1为例说明为例说明此软件的用法此软件的用法 max Z=50x1+100x2， 约束条件：约束条件：x1+x2300， 2 x1+x2400， x2250, x10, x20.选择了线性规划后，就出现的界面，然后点选择了线性规划后，就出现的界面，然后点新建。得到如下对话框：新建。得到如下对话框：然后新建清零，下面就可以然后新建清零，下面就可以然后新建清零，下面就可以然后新建清零，下面就可以输入模型了
8、。输入模型了。输入模型了。输入模型了。先输入变量个数、约束个数和先输入变量个数、约束个数和先输入变量个数、约束个数和先输入变量个数、约束个数和MAXMAX或或或或MinMin，然后点确定后，然后点确定后，然后点确定后，然后点确定后，才能输入模型。才能输入模型。才能输入模型。才能输入模型。输入目标函数系数输入目标函数系数输入目标函数系数输入目标函数系数一般地变量的非负性不必一般地变量的非负性不必一般地变量的非负性不必一般地变量的非负性不必修改。修改。修改。修改。在这输入约束条件，在输在这输入约束条件，在输在这输入约束条件，在输在这输入约束条件，在输入约束条件时注意清入约束条件时注意清入约束条件时
9、注意清入约束条件时注意清0 0，还，还，还，还要注意不等号的方向。要注意不等号的方向。要注意不等号的方向。要注意不等号的方向。输完模型后就可以选择要进行的操作，输完模型后就可以选择要进行的操作，输完模型后就可以选择要进行的操作，输完模型后就可以选择要进行的操作，如：保存、解决（求解）等。下面是例如：保存、解决（求解）等。下面是例如：保存、解决（求解）等。下面是例如：保存、解决（求解）等。下面是例1 1的输入结果。的输入结果。的输入结果。的输入结果。输完模型后，苦要修输完模型后，苦要修输完模型后，苦要修输完模型后，苦要修改模型点这里改模型点这里改模型点这里改模型点这里样？就这解决后得到如下结果。
10、解决后得到如下结果。解决后得到如下结果。解决后得到如下结果。如果选择保存，就弹出保存路如果选择保存，就弹出保存路如果选择保存，就弹出保存路如果选择保存，就弹出保存路径的对话框。径的对话框。径的对话框。径的对话框。输入文件名，然后输入文件名，然后输入文件名，然后输入文件名，然后点保存即可，以后点保存即可，以后点保存即可，以后点保存即可，以后可以点打开调出模可以点打开调出模可以点打开调出模可以点打开调出模型。型。型。型。 从上面变量、最优解、相差值一栏中，知道例从上面变量、最优解、相差值一栏中，知道例1的最优解为生的最优解为生产产产品产品50单位；生产单位；生产产品产品250单位。单位。相差值的数
11、值表示相应的决相差值的数值表示相应的决相差值的数值表示相应的决相差值的数值表示相应的决策变量的目标系数需要改进的数量，使得该决策变量有可能取正策变量的目标系数需要改进的数量，使得该决策变量有可能取正策变量的目标系数需要改进的数量，使得该决策变量有可能取正策变量的目标系数需要改进的数量，使得该决策变量有可能取正数值，一般地，当决策变量已取正数值时则相差值为零。如果决数值，一般地，当决策变量已取正数值时则相差值为零。如果决数值，一般地，当决策变量已取正数值时则相差值为零。如果决数值，一般地，当决策变量已取正数值时则相差值为零。如果决策变量取策变量取策变量取策变量取0 0值，则相差值可能不为值，则相
12、差值可能不为值，则相差值可能不为值，则相差值可能不为0 0。对例对例1来说由于来说由于x1=50，x2=250，都是正值，所以它们的相差值都为零。如果都是正值，所以它们的相差值都为零。如果x1的值为的值为0；x1 的相的相差值为差值为20；则就知道，只有当产品；则就知道，只有当产品I 的利润再提高的利润再提高20元，即达到元，即达到50+20=70元时（这里的元时（这里的50是表示是表示X1的利润，不是的利润，不是X1的最优解），的最优解）， 产品产品I 才可能生产，即才可能生产，即x1才可能大于零。才可能大于零。对于目标函数求最小值的对于目标函数求最小值的对于目标函数求最小值的对于目标函数求
13、最小值的线性规划问题，那么所谓的改进就应该使其对应的决策变量的系线性规划问题，那么所谓的改进就应该使其对应的决策变量的系线性规划问题，那么所谓的改进就应该使其对应的决策变量的系线性规划问题，那么所谓的改进就应该使其对应的决策变量的系数减少其相差值。这在以后还要说明。数减少其相差值。这在以后还要说明。数减少其相差值。这在以后还要说明。数减少其相差值。这在以后还要说明。如何读懂输出结果？如何读懂输出结果？如何读懂输出结果？如何读懂输出结果？3.2软件输出信息分析软件输出信息分析喂！相差值是什么意思？ 我知道：我知道：我知道：我知道：如果决策变量取正数值，则相差值一般为零。如果决策变量取正数值，则相
14、差值一般为零。如果决策变量取正数值，则相差值一般为零。如果决策变量取正数值，则相差值一般为零。则此时目标函数的系数无法再改变使目标函数值变得更则此时目标函数的系数无法再改变使目标函数值变得更则此时目标函数的系数无法再改变使目标函数值变得更则此时目标函数的系数无法再改变使目标函数值变得更好。好。好。好。 如果决策变量取如果决策变量取如果决策变量取如果决策变量取0 0值，则相差值可能不为值，则相差值可能不为值，则相差值可能不为值，则相差值可能不为0 0（比如说（比如说（比如说（比如说相差值为正相差值为正相差值为正相差值为正a a，也有可能为，也有可能为，也有可能为，也有可能为0)0)。则此时目标函
15、数的系数可则此时目标函数的系数可则此时目标函数的系数可则此时目标函数的系数可以在原来基础上增加以在原来基础上增加以在原来基础上增加以在原来基础上增加a a（而当目标函数是求最小值时，减而当目标函数是求最小值时，减而当目标函数是求最小值时，减而当目标函数是求最小值时，减少少少少a)a)，则可能才能使此决策变量变为非零（即生产该种则可能才能使此决策变量变为非零（即生产该种则可能才能使此决策变量变为非零（即生产该种则可能才能使此决策变量变为非零（即生产该种产品），才有可能使目标函数值变得更好。产品），才有可能使目标函数值变得更好。产品），才有可能使目标函数值变得更好。产品），才有可能使目标函数值变得
16、更好。也可以这样理解：在相差值内也可以这样理解：在相差值内也可以这样理解：在相差值内也可以这样理解：在相差值内, ,价值系数增加就不会影价值系数增加就不会影价值系数增加就不会影价值系数增加就不会影响原来的最优基，但当价值系数增加大于等于相差值时响原来的最优基，但当价值系数增加大于等于相差值时响原来的最优基，但当价值系数增加大于等于相差值时响原来的最优基，但当价值系数增加大于等于相差值时, ,最优基就会发生变化。最优基就会发生变化。最优基就会发生变化。最优基就会发生变化。 满足约束条件：满足约束条件：x1+x2300，（，（台时数）台时数） 2 x1+x2400，（，（原料原料A） x2250,
17、 （原料原料B） 在约束条件、松弛剩余变量、对偶价格这栏中，可在约束条件、松弛剩余变量、对偶价格这栏中，可知设备的台时数全部使用完，每个设备台时的对偶价格知设备的台时数全部使用完，每个设备台时的对偶价格为为50元，即增加了一个台时数就可使总利润增加元，即增加了一个台时数就可使总利润增加50元；元；原料原料A还有还有50千克没有使用，原料千克没有使用，原料A的对偶价格当然为零，的对偶价格当然为零，即增加即增加1千克千克A原料不会使总利润有所增加；原料原料不会使总利润有所增加；原料B全部使全部使用完，原料用完，原料B的对偶价格为的对偶价格为50元，即增加一千克原料元，即增加一千克原料B就就可使总利
18、润增加可使总利润增加50元。元。设备设备原料原料A A原料原料B B 在目标函数系数范围一栏中，在目标函数系数范围一栏中，所谓的当前值是指在目标函数所谓的当前值是指在目标函数所谓的当前值是指在目标函数所谓的当前值是指在目标函数中决策变量的当前系数值。如中决策变量的当前系数值。如中决策变量的当前系数值。如中决策变量的当前系数值。如x x1 1的系数值为的系数值为的系数值为的系数值为5050，x x2 2的系数值为的系数值为的系数值为的系数值为100100。所谓的上限与下限值是指目标函数的决策变量的系数（其它决策所谓的上限与下限值是指目标函数的决策变量的系数（其它决策所谓的上限与下限值是指目标函数
19、的决策变量的系数（其它决策所谓的上限与下限值是指目标函数的决策变量的系数（其它决策变量的系数固定在当前值）在此范围内变化时，其线性规划的最变量的系数固定在当前值）在此范围内变化时，其线性规划的最变量的系数固定在当前值）在此范围内变化时，其线性规划的最变量的系数固定在当前值）在此范围内变化时，其线性规划的最优解不变。优解不变。优解不变。优解不变。例如当例如当c1= 80时，因为时，因为080100，在，在x1的系数变化范的系数变化范围内，所以其最优解不变（此时要固定围内，所以其最优解不变（此时要固定c2=100)，也即当也即当x1=50，x2=250时，有最大利润。当然由于产品时，有最大利润。当
20、然由于产品的单位利润由的单位利润由50变为变为80了，了，其最大利润也增加了其最大利润也增加了(最优值变了最优值变了)， 变为变为8050 +100250 =29000(元元)。 但是如果但是如果c1=110元时，由于元时，由于110100，所以原来的最优解就可，所以原来的最优解就可能不再是最优解了。能不再是最优解了。 同样从上图可知，当同样从上图可知，当c2 在在50与与之间变化时（此时要固定之间变化时（此时要固定c1=50) ，原来的最优解依然是其最优解。，原来的最优解依然是其最优解。 所谓当前值是指约束条件右边值的现在值，可知所谓当前值是指约束条件右边值的现在值，可知b1=300；b2=
21、400，b3=250。所谓上限值与下限值是指当约束条件的右边值在此范围所谓上限值与下限值是指当约束条件的右边值在此范围所谓上限值与下限值是指当约束条件的右边值在此范围所谓上限值与下限值是指当约束条件的右边值在此范围内变化时，则与其对应的约束条件的对偶价格不变，不能保证最内变化时，则与其对应的约束条件的对偶价格不变，不能保证最内变化时，则与其对应的约束条件的对偶价格不变，不能保证最内变化时，则与其对应的约束条件的对偶价格不变，不能保证最优解不变优解不变优解不变优解不变。从可由对偶价格判断增加某约束条件的常数项值是否从可由对偶价格判断增加某约束条件的常数项值是否能使目标函数值变得更好能使目标函数值
22、变得更好（前提条件是其它常数项保持不变）（前提条件是其它常数项保持不变）。 当设备台时数在当设备台时数在250325的范围内，其对偶价格都为的范围内，其对偶价格都为50元，说元，说明增加设备台时数可使目标函数值变大，每增加明增加设备台时数可使目标函数值变大，每增加1个台时数可增加个台时数可增加利润利润50元。当原料元。当原料A的公斤数在的公斤数在350到到+范围内，其对偶价格都为范围内，其对偶价格都为零；增加原料零；增加原料A对目标函数值无影响。当原料对目标函数值无影响。当原料B的千克数在的千克数在200到到300的范围内，其对偶价格都为的范围内，其对偶价格都为50元。例如设备台时数和原料元。
23、例如设备台时数和原料A的的数量不变，即数量不变，即b1=300；b2=400，原料，原料B变为变为280千克，由于千克，由于200280300，原料，原料B的对偶价格仍为的对偶价格仍为50元，故新的最大利润值应元，故新的最大利润值应为：为： 27500+(280-250)50=29000元。这里元。这里50是对偶价格。是对偶价格。设备设备原料原料A A原料原料B B如果所有的右端常数项同时在变，对偶价格是否变啊？ 以上关于目标函数系数及约束条件右边值的灵敏度分以上关于目标函数系数及约束条件右边值的灵敏度分以上关于目标函数系数及约束条件右边值的灵敏度分以上关于目标函数系数及约束条件右边值的灵敏度
24、分析都是基于这样一个重要假设：只有一个系数在变化，而析都是基于这样一个重要假设：只有一个系数在变化，而析都是基于这样一个重要假设：只有一个系数在变化，而析都是基于这样一个重要假设：只有一个系数在变化，而其他的系数值保持不变。所有以上的目标函数系数及约束其他的系数值保持不变。所有以上的目标函数系数及约束其他的系数值保持不变。所有以上的目标函数系数及约束其他的系数值保持不变。所有以上的目标函数系数及约束条件右边值的变化范围只适合于单个系数变化的情况。如条件右边值的变化范围只适合于单个系数变化的情况。如条件右边值的变化范围只适合于单个系数变化的情况。如条件右边值的变化范围只适合于单个系数变化的情况。
25、如果两个或更多或者说所有约束条件右边常数项同时变动，果两个或更多或者说所有约束条件右边常数项同时变动，果两个或更多或者说所有约束条件右边常数项同时变动，果两个或更多或者说所有约束条件右边常数项同时变动，就不能用上面方法来判断对偶价格是否变了。要用下面方就不能用上面方法来判断对偶价格是否变了。要用下面方就不能用上面方法来判断对偶价格是否变了。要用下面方就不能用上面方法来判断对偶价格是否变了。要用下面方法来判断。法来判断。法来判断。法来判断。 百分之一百法则：百分之一百法则： 先以例先以例1为例看一看如何用百分之一百法为例看一看如何用百分之一百法则对两个目标函数系数同时变化进行灵敏度则对两个目标函
26、数系数同时变化进行灵敏度分析。例分析。例1中原来每件中原来每件产品和产品和产品的利润分产品的利润分别为别为50元和元和100元，现在由于市场情况的变化元，现在由于市场情况的变化每件每件产品和产品和产品的利润分别变为产品的利润分别变为74元和元和78元，最优解发生变化吗元，最优解发生变化吗? 为了解决这个问题我们首先来定义为了解决这个问题我们首先来定义“允许允许增加值增加值”和和“允许减少值允许减少值”这两个术语，对这两个术语，对一个目标函数的决策变量系数，一个目标函数的决策变量系数，所谓允许增所谓允许增加值是该系数在上限范围内的最大增加量，加值是该系数在上限范围内的最大增加量，所谓的允许减少量
27、是该系数在下限范围内的所谓的允许减少量是该系数在下限范围内的最大的减少量最大的减少量。 这样可以计算出这样可以计算出这样可以计算出这样可以计算出C C1 1的允许增加量百分比为：的允许增加量百分比为：的允许增加量百分比为：的允许增加量百分比为：(74-50)(74-50)50=4850=48；C C2 2 的允许减少百分比为的允许减少百分比为的允许减少百分比为的允许减少百分比为(100-78)(100-78)50=4450=44，C C1 1允许增加百分比与允许增加百分比与允许增加百分比与允许增加百分比与C C2 2的允许减的允许减的允许减的允许减少百分比之和为：少百分比之和为：少百分比之和为
28、：少百分比之和为：4848+44+44=92=92。 变量变量变量变量 下限下限下限下限 当前值当前值当前值当前值 上限上限上限上限 x x1 1 0 50 100 0 50 100 x x2 2 50 100 50 100 无上限无上限无上限无上限 从上面可知目标函数中从上面可知目标函数中从上面可知目标函数中从上面可知目标函数中X X1 1的系数的上限为的系数的上限为的系数的上限为的系数的上限为100100，故，故，故，故C C1 1允许增加量为：允许增加量为：允许增加量为：允许增加量为： 上限上限上限上限- -现在值现在值现在值现在值=100-50=50=100-50=50；而而而而X X
29、2 2的下限为的下限为的下限为的下限为5050，故，故，故，故C C2 2的允许减少量为：的允许减少量为：的允许减少量为：的允许减少量为： 现在值现在值现在值现在值- -下限下限下限下限=100-50=50=100-50=50。 定义定义定义定义C Ci i 的允许增加的允许增加的允许增加的允许增加( (减少减少减少减少) )百分比为：百分比为：百分比为：百分比为：C Ci i 的增加量的增加量的增加量的增加量( (减少量减少量减少量减少量) )除以除以除以除以C Ci i 的允许增加量的允许增加量的允许增加量的允许增加量( (允许减少量允许减少量允许减少量允许减少量) )的值。的值。的值。的
30、值。 目标函数决策变量系数的百分之一百法则：目标函数决策变量系数的百分之一百法则：对于所有变化的目标函数决策变量系数，当其对于所有变化的目标函数决策变量系数，当其所有允许增加百分比和允许减少百分比之和不所有允许增加百分比和允许减少百分比之和不超过百分之一百时超过百分之一百时(含百分百），最优解不变。含百分百），最优解不变。 在上题中在上题中C1 的允许增加百分比与的允许增加百分比与C2 的允许减的允许减少百分比之和为少百分比之和为92不超过不超过100，所以当每件产，所以当每件产品品利润从利润从50元增加到元增加到74元，每件产品元，每件产品利润从利润从100元减少到元减少到78元时，此线性规
31、划最优解仍然为元时，此线性规划最优解仍然为产品产品生产生产50件，件， 产品生产产品生产250件件(即即x1= 50，x2=250)，此时有最大利润为，此时有最大利润为: 74 50+78 250=370019500=23200(元元)。 注意最大利润已变。注意最大利润已变。 同样有约束条件右边常数值的百分之一百法同样有约束条件右边常数值的百分之一百法则：对于所有变化的约束条件右边常数值，当其则：对于所有变化的约束条件右边常数值，当其所有允许增加百分比和允许减少百分比之和不超所有允许增加百分比和允许减少百分比之和不超过百分之一百时，则其对偶价格不变。过百分之一百时，则其对偶价格不变。 其中其中
32、bj 的允许增加的允许增加(减少减少)百分比的定义同百分比的定义同Ci 的允许的允许增加增加(减少减少)百分比一样：百分比一样：为为bj 的增加量的增加量(减少量减少量)除以除以bj的允许增加量的允许增加量(减少量减少量)的值。的值。并不难 仍以例仍以例1为例来说明如何用约束条件右边常数值的为例来说明如何用约束条件右边常数值的百分之一百法则进行灵敏度分析。不妨设设备台时百分之一百法则进行灵敏度分析。不妨设设备台时数从数从300台时增加为台时增加为315台时，而原料台时，而原料A从从400千克减千克减少到少到390千克，原料千克，原料B从从250千克减少到千克减少到240千克，这千克，这样可以得
33、到它们的允许增加样可以得到它们的允许增加(减少减少)百分比。因为：百分比。因为：约束约束 下限下限 当前值当前值 上限上限 1 250 300 325 2 350 400 无上限无上限 3 200 250 300设备台时数：设备台时数： (315-300)/(325-300)=15/25=60，原料原料A： (400-390)/(400-350)=10/50=20，原料原料B： (250-240)/(250-200)=10/50=20。 所以它们的允许增加百分比与允许减少所以它们的允许增加百分比与允许减少百分比之和为百分比之和为60+20+20=100，从，从以上约束条件右边常数值的百分之一百
34、法则以上约束条件右边常数值的百分之一百法则可知此线性规划的对偶价格不变。因为设备可知此线性规划的对偶价格不变。因为设备台时数从台时数从300台时增加为台时增加为315台时，而原料台时，而原料A从从400千克减少到千克减少到390千克，原料千克，原料B从从250千千克减少到克减少到240千克，所以从对偶价格可知千克，所以从对偶价格可知5015+0（-10）+50（-10）=250(元元)，则最大利润，则最大利润增加了增加了250元，为元，为27750元。元。 在使用百分之一百的法则进行灵敏度分在使用百分之一百的法则进行灵敏度分析时，要注意以下四点：析时，要注意以下四点： 1)、当允许增加量、当允
35、许增加量(减少量减少量)为无穷大时，则对于任为无穷大时，则对于任一个增加量一个增加量(减少量减少量)，其允许增加，其允许增加(减少减少)百分比都看成百分比都看成零。零。 例如，在表例如，在表3- 4中，约束条件中，约束条件2的常数项变动范围的常数项变动范围为为350至至+, 如果原料如果原料A从从400增加到增加到410，则相当于，则相当于 （410- 400）/（无穷大（无穷大- 400)=0. 2)、当允许增加量、当允许增加量(减少量减少量)为为0时，时，则对于任一个增加量则对于任一个增加量(减少量减少量)，其，其允许增加允许增加(减少减少)百分比都看成无穷百分比都看成无穷大（相当于该变量
36、不能增加或减少）。大（相当于该变量不能增加或减少）。 要打开思路!3)、百分之一百法则是判断最优解或对偶价、百分之一百法则是判断最优解或对偶价格变不变的格变不变的充分条件充分条件，但，但不是必要条件不是必要条件，也，也就是说当其允许增加和减少百分比之和不超就是说当其允许增加和减少百分比之和不超过过100时，其最优解或对偶价格不变，但时，其最优解或对偶价格不变，但是当其允许增加和减少百分比之和超过是当其允许增加和减少百分比之和超过100时，我们并不知道其最优解或对偶价格变时，我们并不知道其最优解或对偶价格变还是不变。还是不变。 4)、百分之一百法则不能应用于目标函数、百分之一百法则不能应用于目标
37、函数决决策变量系数策变量系数和约束条件和约束条件右边常数值右边常数值同时变化同时变化的情况，在这种情况下，只有重新求解。的情况，在这种情况下，只有重新求解。 下面把例下面把例2输入计算机来分析此线性规划的输入计算机来分析此线性规划的计算机输出，例计算机输出，例2的数学模型如下：的数学模型如下： 目标函数：目标函数：min 2x1+3x2 约束条件：约束条件：x1+x2350， x1125， 2x1+x2600 x10， x20上机计算得到如下结果：上机计算得到如下结果： 从上面结果知道，当购进从上面结果知道，当购进A原料原料250吨吨(X1=250)，B原料原料100吨吨(X2=100)时，使
38、得购进成本最低为时，使得购进成本最低为800万万元。在松弛剩余栏中，约束条件元。在松弛剩余栏中，约束条件的值为的值为125，约，约束条件束条件表示对原料表示对原料A的最低需求，由于此约束为大的最低需求，由于此约束为大于等于，这样可知原料于等于，这样可知原料A的剩余变量值为的剩余变量值为125（因为（因为x1=250）。）。同样可知约束条件同样可知约束条件（对所有原料的总需（对所有原料的总需要量）的剩余变量值为零，约束条件要量）的剩余变量值为零，约束条件（加工时数的（加工时数的限制）的松弛变量值为零。限制）的松弛变量值为零。约束约束 松弛剩余变量松弛剩余变量 对偶价格对偶价格 1 0 - 4 2
39、 125 0 3 0 1 在对偶价格一栏中，可知约束条件在对偶价格一栏中，可知约束条件的对偶价格为的对偶价格为- 4万元，也就是说如果把购进原料万元，也就是说如果把购进原料A+原料原料B的下限从的下限从350吨增加到吨增加到351吨，那么总成本将加大（因为对偶价格为吨，那么总成本将加大（因为对偶价格为负值），由负值），由800万元增加到万元增加到800+4=804(万元万元)了。当然如了。当然如果减少对原料果减少对原料A+原料原料B的下限，如把原料的下限，如把原料A+原料原料B的下的下限从限从350吨减少到吨减少到349吨，那么总成本将得到改进，由吨，那么总成本将得到改进，由800万元减少到万
40、元减少到800- 4=796万元了。万元了。 可知约束条件可知约束条件（加工时数）的对偶价格为（加工时数）的对偶价格为1万元，万元，也就是说如果把加工时数从也就是说如果把加工时数从600小时增加到小时增加到601小时，则小时，则总成本将得到改进总成本将得到改进(因为对偶价格为正值因为对偶价格为正值)，由，由800万元万元减少为减少为800-1=799万元了。万元了。 目标函数系数范围：目标函数系数范围： 变量变量 下限下限 当前值当前值 上限上限 X1 无下限无下限 2 3 X2 2 3 无上限无上限 在目标函数系数范围这一栏中，知道当在目标函数系数范围这一栏中，知道当C2(目标函数中目标函数
41、中X2的系数的系数)不变，不变，C1（目标函目标函数中数中X1的系数）在的系数）在-到到3范围内变化时，最范围内变化时，最优解不变；当优解不变；当C1不变时，不变时，C2在在2到到+范围内范围内变化时，最优解不变。变化时，最优解不变。 常数项范围：常数项范围： 约束约束 下限下限 当前值当前值 上限上限 1 300 350 475 2 无下限无下限 125 250 3 475 600 700 在约束条件右边值范围一栏中，知道当约束条件在约束条件右边值范围一栏中，知道当约束条件的右边值（原料的右边值（原料A和原料和原料B的总量的下限）在的总量的下限）在300到到475范围内变化，而其他约束条件的
42、右边值不变时，范围内变化，而其他约束条件的右边值不变时，则约束条件则约束条件的对偶价格不变仍为的对偶价格不变仍为 - 4。 当约束条件当约束条件的右边值（原料的右边值（原料A的需求量的下限）的需求量的下限）在在0 到到250范围内变化时，而其他约束条件的右边值不范围内变化时，而其他约束条件的右边值不变时，则约束条件变时，则约束条件的对偶价格不变，仍为的对偶价格不变，仍为0。当约。当约束条件束条件的右边值（加工时数的上限）在的右边值（加工时数的上限）在475到到700范范围内变化，而其他约束条件的右边值不变时，则约束围内变化，而其他约束条件的右边值不变时，则约束条件条件的对偶价格不变仍为的对偶价
43、格不变仍为1。练习练习 P37 ,4在本章结束时，还有一件事要注意的。在本章结束时，还有一件事要注意的。 有些书上常常使用有些书上常常使用影子价格影子价格这个术语，当约束这个术语，当约束条件右边值增加一个单位时最优目标函数值增加条件右边值增加一个单位时最优目标函数值增加的数量称之为的数量称之为影子价格影子价格，对照对偶价格的定义：，对照对偶价格的定义：当约束条件右边值增加一个单位时最优目标函数当约束条件右边值增加一个单位时最优目标函数值改进的数量。可知当求目标函数的值改进的数量。可知当求目标函数的最大值时最大值时，增加的数量就是改进的数量，所以增加的数量就是改进的数量，所以影子价格就等影子价格就等于对偶价格于对偶价格。而当求目标函数的。而当求目标函数的最小值时最小值时，改进，改进的数量应该是减少的数量。所以的数量应该是减少的数量。所以影子价格即为负影子价格即为负的对偶价格的对偶价格。
