运筹学—线性规划.ppt

《运筹学—线性规划.ppt》由会员分享，可在线阅读，更多相关《运筹学—线性规划.ppt（181页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学运筹学线性规划线性规划（5 5）根据根据 ，确定基变量，确定基变量 为换出变量。为换出变量。（6 6）用替代用替代 得新基得新基1 1，由变换公式，由变换公式计算新基的逆阵计算新基的逆阵1 1-1-1，求出新的基本可行解，求出新的基本可行解 其中为变换矩阵，构造方法是：其中为变换矩阵，构造方法是：从一个单位矩阵出发，把换出变量从一个单位矩阵出发，把换出变量 在基在基B B中的对应列的单位中的对应列的单位 向量，替换成换入变量向量，替换成换入变量 对应的系数列向量对应的系数列向量 ，并做如下变形，并做如下变形，主元素主元素 （应在主对角线上）取倒数，其它元素除以主元素（应在主对角线上）取倒

2、数，其它元素除以主元素 并取相反数。并取相反数。重复（重复（2 2）（）（6 6）直至求得最优解。）直至求得最优解。换入换入无界解无界解换出换出最优解最优解初始基初始基新基新基 例例9 9、试用改进单纯形法求解、试用改进单纯形法求解解：解：（）观察法确定（）观察法确定，为基变量为基变量为非基变量为非基变量 （2 2）计算单纯行乘子）计算单纯行乘子 目标函数当前值目标函数当前值 （3 3）非基变量检验数）非基变量检验数(4(4）选择换入变量选择换入变量 故故 为换入变量。计算为换入变量。计算()确定换出变量确定换出变量确定确定 为换出变量，主元素为换出变量，主元素(6)(6)用用 代替代替 得新

3、可行基得新可行基 为基变量，为基变量，为非基变量，为非基变量，重复以上步骤，进入第二循环重复以上步骤，进入第二循环(1)(1)(2)(2)(3)(3)(4)(4)选择选择 换入变量换入变量(5)(5)选择选择 换出变量换出变量,主元素主元素(6)(6)用用 代替代替 得新可行基得新可行基 为基变量，为基变量，为非基变量，为非基变量，进入第三循环进入第三循环.(1)(1)(2)(2)(3)(3)非基变量对应的检验数全部非正，非基变量对应的检验数全部非正，故当前解故当前解 即为最优解，即为最优解，相应的目标函数最优值相应的目标函数最优值 。六、单纯形法总结六、单纯形法总结1、Min型单纯形表与型单

4、纯形表与Max型的区别仅在于：型的区别仅在于：令令k=minj0的的xk进基，当进基，当0时最优。时最优。2、解的几种情况及其在单纯形表上的体现（讨论、解的几种情况及其在单纯形表上的体现（讨论Max型）型）唯一唯一最优解最优解j0,非基非基0但但B-1Pk0无可行解无可行解用大用大M法法求解，最求解，最优基中含优基中含有有X人人退化解退化解最优解最优解中某基中某基变量为变量为0第三节 对偶问题与灵敏度分析一一、对偶问题及其模型、对偶问题及其模型例例7：回顾例：回顾例1这时有另一家厂商这时有另一家厂商提出要购买其煤、电、提出要购买其煤、电、油全部资源，并希望花油全部资源，并希望花费尽量少。试建立

5、购买费尽量少。试建立购买者的线性规划模型。者的线性规划模型。例例7称为例称为例1的对偶问题，记为的对偶问题，记为（D），例），例1称为例称为例7的原问题的原问题,记为（记为（P）。）。对偶模型的一般式对偶模型的一般式以例以例7为例，原问题为为例，原问题为（P）（D）这是最常见的对偶模型形式，称为对称式对偶模型。二者间这是最常见的对偶模型形式，称为对称式对偶模型。二者间具有十分对称的对应关系：具有十分对称的对应关系：原问题（原问题（P P）对偶问题对偶问题 （D D）目标目标max型型目标目标min型型有有n个变量（非负）个变量（非负）有有n个约束（大于等于）个约束（大于等于）有有m个约束个约束

6、（小于等于）（小于等于）有有m个变量（非负）个变量（非负）价格系数价格系数资源向量资源向量资源向量资源向量价格系数价格系数技术系数矩阵技术系数矩阵技术系数矩阵的转置技术系数矩阵的转置此外，还有一种情形原问题（原问题（P P）对偶问题对偶问题 （D D）第第j个变量为自由变量个变量为自由变量第第j个约束为等式约束个约束为等式约束第第i个约束为等式约束个约束为等式约束第第i个变量为自由变量个变量为自由变量例例8：写出下面线性规划的对偶规划模型：写出下面线性规划的对偶规划模型：例例8：写出下面线性规划的对偶规划模型：写出下面线性规划的对偶规划模型：minZ=-CXs.T-AX-bX0对称性定理：对称

7、性定理：对偶问题的对偶是原问题。对偶问题的对偶是原问题。minW=Ybs.TYACY0maxZ=Cs.TAXbX0对偶的定义对偶的定义对偶的定义对偶的定义maxW=-Ybs.TYACY0二、对偶问题的性质弱对偶原理：弱对偶原理：设设 和和 分别是问题（分别是问题（P P）和（）和（D D）的）的可行解，则必有可行解，则必有推论推论：若若 和和 分别是问题（分别是问题（P P）和（）和（D D）的可行）的可行解，则解，则 是（是（D D）的目标函数最小值的一）的目标函数最小值的一个下界；个下界；是（是（P P）的目标函数最大值的一）的目标函数最大值的一个上界。个上界。对偶问题的性质关于无界性有如

8、下结论：关于无界性有如下结论：问题无问题无界界无可无可行解行解无可无可行解行解问题无问题无界界对偶问对偶问题题原问题原问题无界无界如：如：（原）（原）无可无可行解行解（对）（对）对偶问题的性质推论推论：在一对对偶问题在一对对偶问题(P)(P)和和(D)(D)中，若其中一个问题可行但目中，若其中一个问题可行但目标函数无界，则另一个问题不标函数无界，则另一个问题不可行；反之不成立。这也是对可行；反之不成立。这也是对偶问题的无界性。偶问题的无界性。推推论论：在在一一对对对对偶偶问问题题（P P）和和（D D）中中，若若一一个个可可行行（如如P P），而而另另一一个个不不可可行行（如如D D），则则该

9、该可可行行的的问题无界。问题无界。例例1 1 试估计它们目标函数的界，并验证弱对偶性原理。试估计它们目标函数的界，并验证弱对偶性原理。（P P）对偶问题的性质解：解：（D D）由观察可知：由观察可知：，分别是（，分别是（P P）和）和（D D）的可行解。）的可行解。Z Z=10=10，W W=40=40，故有，故有 ，弱对偶定理成立。由推论弱对偶定理成立。由推论可知，可知，W W 的最小值不的最小值不能小于能小于1010，Z Z 的最大值不能超过的最大值不能超过4040。对偶问题的性质（P）（D）考虑考虑4.对偶定理 若（P）有最优解，则（D）也有最优解，且最优值相同。证：对（证：对（P）增加

10、松弛变量，）增加松弛变量，化为化为设其最优基为设其最优基为B，终表为，终表为其检验数为其检验数为问题：(1)由对偶定理可知，对偶问题最优解的表达式 Y*=？(2)求求Y*是否有必要重新求解（是否有必要重新求解（D）？）？CBB-1不必。可以从原问题（不必。可以从原问题（P）的单纯形终表获得。的单纯形终表获得。例如，已知例如，已知的终表为的终表为请指出其对偶问题的最优解和最优值。请指出其对偶问题的最优解和最优值。5.互补松弛定理y1yiymym+1ym+jyn+mx1xjxnxn+1xn+ixn+m对偶问题的变量对偶问题的变量对偶问题的松弛变量对偶问题的松弛变量原始问题的变量原始问题的变量原始问

11、题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0，另一个一定等于，另一个一定等于0直观上直观上定定义义：在在一一对对P和和D中中，若若P的的某某个个约约束束条条件件的的右右端端项项常常数数bi增增加加一一个个单单位位时时，所所引引起起的的目目标标函函数数最最优优值值Z*的的改改变变量量y*i称称为为第第i个个约约束条件的影子价格，又称为边际价格。束条件的影子价格，又称为边际价格。影子价格CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCBB-1b0CNCBB-1NCBB-1

12、设：设：B是问题是问题P的最优基，由前式可知，的最优基，由前式可知，Z*=CBB-1b=Y*b=y*1b1+y*2b2+y*Ibi+y*mbm当当bi变为变为bi+1时（其余右端项不变，也不影响时（其余右端项不变，也不影响B）影子价格目标函数最优值变为：目标函数最优值变为：Z*=y*1b1+y*2b2+y*I（bi+1）+y*mbmZ*=Z*Z*=y*i也可以写成：也可以写成：即即y*i表示表示Z*对对bi的变化率。的变化率。其其经经济济意意义义是是：在在其其它它条条件件不不变变的的情情况况下下，单单位位资资源源变变化化所所引引起起的的目目标标函函数数的的最最优优值值的的变变化化。即即对对偶偶

13、变量变量yi就是第就是第i个约束条件的影子价格。个约束条件的影子价格。也也可可以以理理解解为为目目标标函函数数最最优优值值对对资资源源的的一一阶阶偏偏导导数（但问题中所有其它数据都保持不变）。数（但问题中所有其它数据都保持不变）。若若第第i种种资资源源的的单单位位市市场场价价格格为为mi，当当yimi时时，企企业业愿愿意意购购进进这这种种资资源源，单单位位纯纯利利为为yimi，则则有有利利可可图图；如如果果yi0。例11：在例1（煤电油例）中，其单纯形终表如下：（3）甲产品的价格在何范围内变化时，现最优解不变？）甲产品的价格在何范围内变化时，现最优解不变？解：甲产品的价格解：甲产品的价格c1是

14、基变量的价格系数。是基变量的价格系数。例例11：在例：在例1（煤电油例）中，其单纯形终表如下：（煤电油例）中，其单纯形终表如下：（4）若现又考虑一新产品丙，其资源单耗为）若现又考虑一新产品丙，其资源单耗为10，2，5，售价为售价为6.5，问该产品是否可投产？，问该产品是否可投产？故丙产品可以投产。故丙产品可以投产。首先将线性规划与经济问题联系起来的是首先将线性规划与经济问题联系起来的是T.G.Koopman（库普曼）和（库普曼）和L.V.Kamtorovich（康脱罗维奇）（康脱罗维奇）二人因此而共同分享了二人因此而共同分享了19751975年的第年的第7 7届诺贝尔经届诺贝尔经济学奖。济学奖

15、。求解线性规划的计算机软件举例LINDO、EXCELLINDO可以从下面的网址下载：可以从下面的网址下载：WWW.LLINDOLINDO由美国芝加哥大学开发，可求解线性规划和线性由美国芝加哥大学开发，可求解线性规划和线性整数规划等。其可按自然格式输入模型，使用方便。整数规划等。其可按自然格式输入模型，使用方便。输入例输入例：MAX2X+3Y？ST？4X+9Y9？7X+6Y13？END：GODORANGE(SENSITIVITY)ANALYSIS?？Y可用可用HELP命命令令得到帮助。得到帮助。计算结果说明：计算结果说明：REDUCEDCOST为使该变量进基，其价格系数至少应为使该变量进基，其价

16、格系数至少应增加的数值；增加的数值；SLACKORSUPLUS松弛或剩余变量；松弛或剩余变量；DUALPRICES影子价格影子价格;ALLOWABLEINCREASE灵敏度分析中可使最优基不灵敏度分析中可使最优基不变的系数可增量之上界；变的系数可增量之上界；ALLOWABLEDECREASE灵敏度分析中可使最优基不灵敏度分析中可使最优基不变的系数可减量之上界；变的系数可减量之上界；使用EXCEL求解线性规划-进入进入EXCELEXCEL后先在表格的第一列输入变量、约束和目标的名后先在表格的第一列输入变量、约束和目标的名 称，在后面某一列对应位置输入约束和目标的表达式称，在后面某一列对应位置输入

17、约束和目标的表达式(前加前加 等号提示符等号提示符)；-然后在工具中调用规划求解，按提示操作。然后在工具中调用规划求解，按提示操作。（可参看关于使用（可参看关于使用EXCELEXCEL的书，如谢国锋等，的书，如谢国锋等，EXCEL2000EXCEL2000中中文版入门与提高文版入门与提高，清华大学出版社，清华大学出版社，19991999）5 5 整数规划整数规划Integer Programming(Integer Programming(简称简称IP)IP)一、整数规划的一般模型一、整数规划的一般模型LP:max z=CX AX=b X0IP:max z=CX AX=b X0 X为整数例一、

18、合理下料问题例一、合理下料问题设用某型号的圆钢下零件设用某型号的圆钢下零件A A1 1,A A2 2,A,Am m 的毛坯。在一根的毛坯。在一根圆钢上下料的方式有圆钢上下料的方式有B B1 1,B,B2 2,B Bn n 种，每种下料方式可以得种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。怎到各种零件的毛坯数以及每种零件的需要量，如表所示。怎样安排下料方式，使得即满足需要，所用的原材料又最少？样安排下料方式，使得即满足需要，所用的原材料又最少？零件 方 个数 式零件零 件毛坯数整数规划的模型设：设：xj表示用表示用Bj(j=1.2n)种方式下料根数种方式下料根数模型：

19、模型：整数规划的模型纯纯整整数数规规划划：所所有有决决策策变变量量要要求求取取非非负负整整数数（这这时时引引进进的的松松弛弛变变量量和和剩剩余余变变量量可可以以不不要要求求取整数）。取整数）。全全整整数数规规划划：除除所所有有决决策策变变量量要要求求取取非非负负整整数数外外，系系数数aij和和常常数数bi也也要要求求取取整整数数（这这时时引引进进的松弛变量和剩余变量也必须是整数）。的松弛变量和剩余变量也必须是整数）。混混合合整整数数规规划划：只只有有一一部部分分的的决决策策变变量量要要求求取取非负整数，另一部分可以取非负实数。非负整数，另一部分可以取非负实数。01整整数数规规划划：所所有有决决

20、策策变变量量只只能能取取0或或1两两个整数。个整数。整数规划的数学模型从从数数学学模模型型上上看看整整数数规规划划似似乎乎是是线线性性规规划划的的一一种种特特殊殊形形式式，求求解解只只需需在在线线性性规规划划的的基基础础上上，通通过过舍舍入入取取整整，寻寻求求满满足足整整数数要要求求的的解解即即可可。但但实实际际上上两两者者却却有有很很大大的的不不同同，通通过过舍舍入入得得到到的的解解（整整数数）也也不不一一定定就就是是最最优优解解，有有时时甚至不能保证所得倒的解是整数可行解。甚至不能保证所得倒的解是整数可行解。整数规划与线性规划的关系例：设整数规划问题如下例：设整数规划问题如下 首先不考虑整

21、数约束，得到线性规划问题（一般首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。称为松弛问题）。整数规划与线性规划的关系且为整数 用图解法求出最优解用图解法求出最优解x x1 13/2,3/2,x x2 2=10/3=10/3且有且有Z=29/6Z=29/6x1x233(3/2,10/3)现现求求整整数数解解（最最优优解解）：如如用用“舍舍入入取取整整法法”可可得得到到4个个点点即即(1，3),(2，3),(1，4),(2，4)。显显然然，它它们们都都不不可可能能是是整整数数规规划划的的最优解。最优解。按按整整数数规规划划约约束束条条件件，其其可可行行解解肯肯定定在在线线性性规规划划问

22、问题题的的可可行行域域内内且且为为整整数数点点。故故整整数数规规划划问问题题的的可可行行解解集集是是一一个个有有限限集集，如图所示。如图所示。整数规划与线性规划的关系因因此此，可可将将集集合合内内的的整整数数点点一一一一找找出出，其其最最大目标函数的值为最优解，此法为完全枚举法。大目标函数的值为最优解，此法为完全枚举法。如如上上例例：其其中中（2 2，2 2）（3 3，1 1）点点为为最最大大值值，Z=4Z=4。目前，常用的求解整数规划的方法有：目前，常用的求解整数规划的方法有：分支定界法和割平面法；分支定界法和割平面法；对对于于特特别别的的0 01 1规规划划问问题题采采用用隐隐枚枚举举法法

23、和和匈匈牙利法。牙利法。整数规划与线性规划的关系考虑纯整数问题：考虑纯整数问题：整数问题的松弛问题：整数问题的松弛问题：分枝定界法1、先先不不考考虑虑整整数数约约束束，解解(IP)的的松松弛弛问问题题(LP)，可可能得到以下情况之一：能得到以下情况之一：.若若(LP)没没有有可可行行解解，则则(IP)也也没没有有可可行行解解，停停止计算。止计算。.若若(LP)有有最最优优解解，并并符符合合(IP)的的整整数数条条件件，则则(LP)的最优解即为的最优解即为(IP)的最优解，停止计算。的最优解，停止计算。.若若(LP)有有最最优优解解，但但不不符符合合(IP)的的整整数数条条件件，转入下一步。为讨

24、论方便，设转入下一步。为讨论方便，设(LP)的最优解为：的最优解为：分枝定界法2、定界：、定界：记记(IP)的的目目标标函函数数最最优优值值为为Z*,以以Z(0)作作为为Z*的的上上界界，记记为为Z(0)。再再用用观观察察法法找找的的一一个个整整数数可可行行解解X，并并以以其其相相应应的的目目标标函函数数值值Z作作为为Z*的的下下界界，记记为为ZZ，也可以令，也可以令Z，则有，则有:Z Z*3、分枝：、分枝：在在(LP)的的最最优优解解X(0)中中，任任选选一一个个不不符符合合整整数数条条件件的的变变量量，例例如如xr=br（不不为为整整数数），以以br 表表示示不不超过超过br的最大整数。构

25、造两个约束条件的最大整数。构造两个约束条件xrbr 和和xrbr 1分枝定界法将将这这两两个个约约束束条条件件分分别别加加入入问问题题(IP)，形形成成两两个个子子问问题题(IP1)和和(IP2)，再再解解这这两两个个问问题题的的松松弛弛问问题题(LP1)和和(LP2)。4、修改上、下界：按照以下两点规则进行。、修改上、下界：按照以下两点规则进行。.在在各各分分枝枝问问题题中中，找找出出目目标标函函数数值值最最大大者者作作为为新的上界；新的上界；.从从已已符符合合整整数数条条件件的的分分枝枝中中，找找出出目目标标函函数数值值最大者作为新的下界。最大者作为新的下界。5、比较与剪枝、比较与剪枝：各

26、各分分枝枝的的目目标标函函数数值值中中，若若有有小小于于Z者者，则则剪剪掉掉此此枝枝，表表明明此此子子问问题题已已经经探探清清，不不必必再再分分枝枝了了;否否则则继继续续分枝。分枝。如此反复进行，直到得到如此反复进行，直到得到ZZ*为止，即得最优解为止，即得最优解X*。分枝定界法例一：用分枝定界法求解整数规划问题例一：用分枝定界法求解整数规划问题记为（记为（IP）解：首先去掉整数约束，变成一般线性规划问题解：首先去掉整数约束，变成一般线性规划问题记为（记为（LP）分枝定界法用图解法求（用图解法求（LP）的最）的最优解，如图所示。优解，如图所示。x1x233(18/11,40/11)对于对于x1

27、18/111.64，取值取值x1 1，x1 2对于对于x2=40/11 3.64，取值取值x23，x24先将（先将（LP）划分为（）划分为（LP1）和（）和（LP2）,取取x1 1,x1 2 x118/11,x2=40/11 Z(0)=218/11(19.8)即即Z(0)是（是（IP）最小值的下限。）最小值的下限。分枝定界法有下式：有下式：现在只要求出（现在只要求出（LP1）和（）和（LP2）的最优解即可。）的最优解即可。分枝定界法x1x233(18/11,40/11)先求（先求（LP1）,如图所示。如图所示。此时此时B在点取得最优解。在点取得最优解。x11,x2=3,Z(1)16找到整数解，

28、问题已探明，找到整数解，问题已探明，此枝停止计算。此枝停止计算。11同理求（同理求（LP2）,如图所示。如图所示。在在C点取得最优解。点取得最优解。即即x12,x2=10/3,Z(2)56/318.7 Z2 Z116原问题有比（原问题有比（16）更小的最优解，但更小的最优解，但x2 不是整数，利用不是整数，利用3 10/34加入条件。加入条件。BAC分枝定界法加入条件：加入条件：x23,x24有下式：有下式：只要求出（只要求出（LP3）和（）和（LP4）的最优解即可。）的最优解即可。分枝定界法x1x233(18/11,40/11)11BAC先求（先求（LP3）,如图所示。此如图所示。此时时D

29、在点取得最优解。在点取得最优解。即即x112/52.4,x2=3,Z(3)-87/5-17.4Z(5)F如如对对Z(6)继继续续分分解解，其其最最小小值值也也不不会会低低于于15.5，问题探明问题探明,剪枝。剪枝。分枝定界法至至此此，原原问问题题（IP）的的最最优优解解为：为：x1=2，x2=3,Z*=Z(5)17以以上上的的求求解解过过程程可可以以用用一一个个树树形形图表示如右：图表示如右：LP1x1=1,x2=3Z(1)16LPx1=18/11,x2=40/11Z(0)19.8LP2x1=2,x2=10/3Z(2)18.5LP3x1=12/5,x2=3Z(3)17.4LP4无可无可行解行解

30、LP5x1=2,x2=3Z(5)17LP6x1=3,x2=5/2Z(6)15.5x11x12x23x24x12x13分枝定界法二、二、0-10-1整数规划整数规划投资场所的选址问题投资场所的选址问题指派问题指派问题固定费用问题固定费用问题背包问题背包问题消防队问题消防队问题1.投资场所的选址问题投资场所的选址问题某城市拟在东、西、南三区设立商业网点，备选位置有某城市拟在东、西、南三区设立商业网点，备选位置有A1A7共共7个，如果选个，如果选Ai，估计投资为，估计投资为bi元，利润为元，利润为ci元，要元，要求总投资不超过求总投资不超过B元，规定元，规定东区：东区：A!、A2、A3中至多选中至多

31、选2个个西区：西区：A4、A5中至少选一个中至少选一个南区：南区：A6、A7中至少选一个中至少选一个问如何设点使总利润最大？问如何设点使总利润最大？1，Ai被选中被选中0，Ai没被选中没被选中解：令解：令xi=maxz=xi=0或或1，i=1,7bixiBi=17x1+x2+x32x4+x51x6+x71s.t.课堂练习课堂练习1:某钻井队要从某钻井队要从S1S10共共10个井位中确定五个钻个井位中确定五个钻井探油，如果选井探油，如果选Si，估计钻探费用为，估计钻探费用为ci元，并且元，并且井位选择上要满足下列条件：井位选择上要满足下列条件：（1）或选择或选择S1和和S7，或选择，或选择S8;

32、（2）选择了选择了S3或或S4就不能选择就不能选择S5，反，反过来也一样过来也一样;（3）在在S5，S6，S7，S8中最多只能选中最多只能选两个。两个。问如何选择井位使总费用最小？问如何选择井位使总费用最小？课堂练习课堂练习1:某钻井队要从某钻井队要从S1S10共共10个井位中确定五个钻井探油，个井位中确定五个钻井探油，如果选如果选Si，估计钻探费用为，估计钻探费用为ci元，并且井位选择上要满足下列条件：元，并且井位选择上要满足下列条件：（1）或选择）或选择S1和和S7，或选择，或选择S8（2）选择了）选择了S3或或S4就不能选择就不能选择S5，反过来也一样，反过来也一样（3）在）在S5，S6

33、，S7，S8中最多只能选两个中最多只能选两个问如何选择井位使总费用最小？问如何选择井位使总费用最小？1，Si被选中被选中0，Si没被选中没被选中解：令解：令xi=min z=s.t.或 1，i=1,10某篮球队有某篮球队有8名队员，其身高和专长如下表，现要选名队员，其身高和专长如下表，现要选拔拔5名球员上场参赛，要求：名球员上场参赛，要求：（1）中锋只有）中锋只有1人上场人上场（2）后卫至少有一人上场）后卫至少有一人上场（3）只有）只有2号上场，号上场，6号才上场号才上场要求平均身高最高，应如何选拔队员？要求平均身高最高，应如何选拔队员？课堂练习课堂练习2:1，队员队员i被选中被选中0，队员，

34、队员i没被选中没被选中解：令解：令xi=max z=或 1，i=1,8s.t.某篮球队有某篮球队有8名队员，其身高和专长如下表，现要选名队员，其身高和专长如下表，现要选拔拔5名球员上场参赛，要求：名球员上场参赛，要求：（1）中锋只有）中锋只有1人上场人上场（2）后卫至少有一人上场）后卫至少有一人上场（3）只有）只有2号上场，号上场，6号才上场号才上场要求平均身高最高，应如何选拔队员？要求平均身高最高，应如何选拔队员？2.指派问题指派问题例：例：有一份中文说明书，需译成英、日、德、俄四种文字，有一份中文说明书，需译成英、日、德、俄四种文字，分别记作任务分别记作任务E、J、G、R，现有甲、乙、丙、

35、丁四人，他们，现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种说明书所需的时间如下表所示，将中文说明书翻译成不同语种说明书所需的时间如下表所示，问应指派何人去完成何项任务，使所需总时间最少？问应指派何人去完成何项任务，使所需总时间最少？问题描述：问题描述：n项任务可由项任务可由n个人完成，由于专长不同，各人完个人完成，由于专长不同，各人完成各任务的时间也不同，求最优安排。成各任务的时间也不同，求最优安排。要求：要求：每人只能完成一项任务，每项任务只能由一人完成。每人只能完成一项任务，每项任务只能由一人完成。x x1111+x x1212+x x1313+x x1414=1 (=1 (甲只

36、能干一项工作甲只能干一项工作)x x2121+x x2222+x x2323+x x2424=1 (=1 (乙只能干一项工作乙只能干一项工作)x x3131+x x3232+x x3333+x x3434=1 (=1 (丙只能干一项工作丙只能干一项工作)x x4141+x x4242+x x4343+x x4444=1 (=1 (丁只能干一项工作丁只能干一项工作)x x1111+x x2121+x x3131+x x4141=1 (E=1 (E任务只能一人干任务只能一人干)x x1212+x x2222+x x3232+x x4242=1 (J=1 (J任务只能一人干任务只能一人干)x x13

37、13+x x2323+x x3333+x x4343=1 (G=1 (G任务只能一人干任务只能一人干)x x1414+x x2424+x x3434+x x4444=1 (R=1 (R任务只能一人干任务只能一人干)x xijij=0 =0 或或 1 1，i,j i,j=1,2,3,4=1,2,3,4min z=2min z=2x x1111+15+15x x1212+13+13x x1313+4+4x x1414+10+10 x x2121+4+4x x2222+14+14x x2323+15+15x x2424 +9 +9x x3131+14+14x x3232+16+16x x3333+1

38、3+13x x3434+7+7x x41 41+8+8x x4242+11+11x x4343+9+9x x44441，指派第指派第i人去完成第人去完成第j项任务项任务0，不指派第不指派第i人去完成第人去完成第j项任务项任务解：令解：令xij=（二）、解题步骤：（二）、解题步骤：指派问题是指派问题是0-1 规划的特例，也是运输问题的特例，规划的特例，也是运输问题的特例，当然可用整数规划，当然可用整数规划，0-1 规划或运输问题的解法去求规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就

39、是的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即匈牙利法，即系数矩阵中独立系数矩阵中独立 0 0 元素的最多个数等于元素的最多个数等于能覆盖所有能覆盖所有 0 0 元素的最少直线数。元素的最少直线数。第第一一步步：变变换换指指派派问问题题的的系系数数矩矩阵阵（cij）为为(bij)，使使在在(bij)的各行各列中都出现的各行各列中都出现0元素，即元素，即(1)从（从（cij）的每行元素都减去该行的最小元素；）的每行元素都减去该行的最小元素；(2)再再从从所所得得新新系系数数矩矩阵阵的的每每列列元元素素中中减减去去该该列列的的最最小元素。小元素。第二步：进行试指派，以寻求最优解。第二

40、步：进行试指派，以寻求最优解。在在(bij)中中找找尽尽可可能能多多的的独独立立0元元素素，若若能能找找出出n个个独独立立0元元素素，就就以以这这n个个独独立立0元元素素对对应应解解矩矩阵阵(xij)中中的的元元素素为为1，其其余余为为0，这这就就得得到到最最优优解解。找找独独立立0元元素素，常常用的步骤为：用的步骤为：(1)从从只只有有一一个个0元元素素的的行行(列列)开开始始，给给这这个个0元元素素加加圈圈，记记作作。然然后后划划去去所所在在列列(行行)的的其其它它0元元素素，记记作作；这这表表示示这这列列所所代代表表的的任任务务已已指指派派完完，不不必必再再考考虑别人了。虑别人了。(2)

41、给给只只有有一一个个0元元素素的的列列(行行)中中的的0元元素素加加圈圈，记记作作；然后划去；然后划去所在行的所在行的0元素，记作元素，记作(3)反反复复进进行行(1)，(2)两两步步，直直到到尽尽可可能能多多的的0元元素素都都被圈出和划掉为止。被圈出和划掉为止。(4)若若仍仍有有没没有有划划圈圈的的0元元素素，且且同同行行(列列)的的0元元素素至至少少有有两两个个，则则从从剩剩有有0元元素素最最少少的的行行(列列)开开始始，比比较较这这行行各各0元元素素所所在在列列中中0元元素素的的数数目目，选选择择0元元素素少少的的那那列列的的这这个个0元元素素加加圈圈(表表示示选选择择性性多多的的要要“

42、礼礼让让”选选择择性性少少的的)。然然后后划划掉掉同同行行同同列列的的其其它它0元元素素。可可反反复复进进行行，直直到所有到所有0元素都已圈出和划掉为止。元素都已圈出和划掉为止。（5）若）若元素的数目元素的数目m 等于矩阵的阶数等于矩阵的阶数n，那么这指，那么这指派问题的最优解已得到。若派问题的最优解已得到。若m n,则转入下一步。则转入下一步。第三步：作最少的直线覆盖所有第三步：作最少的直线覆盖所有0元素。元素。(1)对没有对没有的行打的行打号；号；(2)对已打对已打号的行中所有含号的行中所有含元素的列打元素的列打号；号；(3)再对打有再对打有号的列中含号的列中含元素的行打元素的行打号；号；

43、(4)重复重复(2)，(3)直到得不出新的打直到得不出新的打号的行、列为止；号的行、列为止；(5)对对没没有有打打号号的的行行画画横横线线，有有打打号号的的列列画画纵纵线线，这这就就得得到到覆覆盖盖所所有有0元元素素的的最最少少直直线线数数l。l 应应等等于于m，若若不不相相等等，说说明明试试指指派派过过程程有有误误，回回到到第第二二步步(4)，另另行行试试指指派派；若若lm n，须须再再变变换换当当前前的的系系数数矩矩阵阵，以以找到找到n个独立的个独立的0元素，为此转第四步。元素，为此转第四步。第四步：变换矩阵第四步：变换矩阵(bij)以增加以增加0元素。元素。在没有被直线覆盖的所有元素中找

44、出最小元素，然后在没有被直线覆盖的所有元素中找出最小元素，然后打打各行都减去这最小元素；打各行都减去这最小元素；打各列都加上这最小元各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。的最优解和原问题仍相同。转回第二步。例一：任务任务人员人员ABCD甲甲215134乙乙1041415丙丙9141613丁丁78119-2-4-9-7-4-2任务任务人员人员ABCD甲甲67112乙乙4598丙丙31104丁丁5982例二、例二、求解过程如下：求解过程如下：第一步，变换系数矩阵：第一步，变换系数矩阵：5第二

45、步，试指派：第二步，试指派：找到找到 3 3 个独立零元素个独立零元素 但但 m m=3 3 n=4 第三步，作最少的直线覆盖所有第三步，作最少的直线覆盖所有0 0元素：元素：独立零元素的个数独立零元素的个数m等于最少直线数等于最少直线数l，即，即lm=3n=4；第四步，变换矩阵第四步，变换矩阵(bij)以增加以增加0 0元素：没有被直线覆元素：没有被直线覆盖的所有元素中的最小元素为盖的所有元素中的最小元素为1 1，然后打，然后打各行都减去各行都减去1 1；打；打各列都加上各列都加上1 1，得如下矩阵，并转第二步进行，得如下矩阵，并转第二步进行试指派：试指派：000000得到得到4 4个独个独

46、立零元素，立零元素，所以最优解所以最优解矩阵为：矩阵为：15练习：11115 57 76 64 4戊戊6 69 96 63 37 7丁丁8 86 64 45 58 8丙丙9 911117 712129 9乙乙11118 89 95 57 7甲甲E ED DC CB BA A费费 工作工作 用用人员人员-1-2l=m=4n=5l=m=40时时0，不选择第不选择第j 种方式，即种方式，即xj=0时时令令yj=设第设第j 种生产方式的产量为种生产方式的产量为xj 于是该问题可表示为：于是该问题可表示为：xj Myj例、例、生产三种型号的防寒服，其消耗资源及单件成本如表。生产三种型号的防寒服，其消耗资

47、源及单件成本如表。此外，每种防寒服不管生产多少，都要支付一定的固定费用。此外，每种防寒服不管生产多少，都要支付一定的固定费用。型号型号资源资源小小中中大大资源限制资源限制尼龙绸尼龙绸1.51.71.81500尼龙棉尼龙棉1.31.51.61000劳动力劳动力44.553500设备设备2.83.84.22800单件成本单件成本131210固定费用固定费用120150180今要生产今要生产500件防寒服，确定总费用最低的生产方式。件防寒服，确定总费用最低的生产方式。型号型号资源资源小小中中大大资源限制资源限制尼龙绸尼龙绸1.51.71.81500尼龙棉尼龙棉1.31.51.61000劳动力劳动力4

48、4.553500设备设备2.83.84.22800单件成本单件成本131210固定费用固定费用1201501801，选择第选择第j 种方式种方式0，不选择第不选择第j 种方式种方式令令yj=MinZ=13x1+12x2+10 x3+120y1+150y2+180y3st1.5x1+1.7x2+1.8x315001.3x1+1.5x2+1.6x310004x1+4.5x2+5x335002.8x1+3.8x2+4.2x32800X1+x2+x3=500 xiMyi(i=1,2,3)xi0;yi=0或或14.背包问题背包问题问题描述问题描述已知：已知：一个背包最大容量为一个背包最大容量为b公斤；有

49、公斤；有m件物品供选择，每件物品供选择，每件物品重件物品重ai公斤，价值为公斤，价值为ci（i=1,m）。）。问题：问题：携带哪些物品可使总价值最大？携带哪些物品可使总价值最大？一般模型一般模型s.t.1，物品物品i被选中被选中0，物品，物品i没被选中没被选中xi=例：例：一个徒步旅行者要在背包中选择一些最有价值的物品携一个徒步旅行者要在背包中选择一些最有价值的物品携带。他最多能带带。他最多能带115kg的物品，现有的物品，现有5件物品，分别重件物品，分别重54、35、57、46、19kg，其价值依次为，其价值依次为7、5、9、6、3。问携带哪些物。问携带哪些物品可使总价值最大？品可使总价值最

50、大？解：解：模型为：模型为：s.t.5.消防队问题消防队问题某城市的消防总部将全市划分为某城市的消防总部将全市划分为11个防火区，设有个防火区，设有4个个消防救火站。下图消防救火站。下图表示消防站，表示消防站，111表示防火区域，表示防火区域，图中连线表示各地区由哪个消防站负责。问题：可否减少消图中连线表示各地区由哪个消防站负责。问题：可否减少消防站的数目，仍能同样负责各地区的防火任务？如果可以，防站的数目，仍能同样负责各地区的防火任务？如果可以，应关闭哪个消防站？应关闭哪个消防站？123456789101112341，保留第保留第i个消防队个消防队0，撤消第撤消第i个消防队个消防队解：解：令