运筹学(胡运权第四版及答案)精编版ppt课件.ppt

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

1、 管理运筹学管理运筹学主讲：谢先达主讲：谢先达2014.092014.09 联系方式联系方式办公室：办公室：QL643 87313663QL643 87313663手机：手机： 1360051236013600512360邮箱：邮箱： 绪绪 论论 绪论绪论什么是运筹学？什么是运筹学？运筹学发展历史运筹学发展历史运筹学主要内容运筹学主要内容运筹学的基本特征与基本方法运筹学的基本特征与基本方法 绪论绪论什么是运筹学？什么是运筹学？定义：定义：为决策机构在对其控制下业务活动进行为决策机构在对其控制下业务活动进行决策决策时，提供以时，提供以数量化数量化为基础的科学方法。为基础的科学方法。西蒙：管理就是

2、决策西蒙：管理就是决策 决策决策 定性定性管理者的判断和经验管理者的判断和经验定量定量运筹运筹学学 绪论绪论运筹学发展历史运筹学发展历史古代运筹思想：田忌赛马、古代运筹思想：田忌赛马、丁渭修皇宫丁渭修皇宫 二战期间的二战期间的Operational Research Operational Research 研究成果被应用到生产、经济领域，且研究不断深研究成果被应用到生产、经济领域，且研究不断深化，逐步形成化，逐步形成“运筹学运筹学” 绪论绪论 绪论绪论运筹学的主要内容有哪些？运筹学的主要内容有哪些？线性规划线性规划运输问题运输问题整数规划整数规划目标规划目标规划动态规划动态规划图与网络模型图

3、与网络模型排序与统筹方法排序与统筹方法存储论存储论排队论排队论对策论对策论决策分析决策分析预测预测 绪论绪论运筹学研究的基本特征运筹学研究的基本特征系统的整体观念系统的整体观念多学科的综合多学科的综合模型方法的应用模型方法的应用 绪论绪论运筹学研究的基本方法运筹学研究的基本方法分析和表述问题分析和表述问题建立模型建立模型求解模型和优化方案求解模型和优化方案测试模型及对模型进行必要的修正测试模型及对模型进行必要的修正建立对解的有效控制建立对解的有效控制方案的实施方案的实施 第一章：线性规划及单纯形法第一章：线性规划及单纯形法 第一章：线性规划及单纯形法第一章：线性规划及单纯形法线性规划问题及其数

4、学模型线性规划问题及其数学模型线性规划图解法线性规划图解法单纯形法原理单纯形法原理单纯形法计算步骤单纯形法计算步骤单纯形法的进一步讨论单纯形法的进一步讨论 第一章：线性规划及单纯形法第一章：线性规划及单纯形法 例题：某工厂在计划期内要安排例题：某工厂在计划期内要安排、两种产品的生产，生两种产品的生产，生产单位产品所需的设备台时及产单位产品所需的设备台时及A A、两种原材料的消耗以及、两种原材料的消耗以及资源的限制如表所示资源的限制如表所示 工厂每生产一单位产品工厂每生产一单位产品可获利可获利5050元，每生产一单位产品元，每生产一单位产品可获利可获利100100元，问工厂应分别生产多少单位产品

5、元，问工厂应分别生产多少单位产品 和产品和产品才能获利最多？才能获利最多？资源限制资源限制设备设备1 11 1300300台时台时原料原料A A2 21 1400KG400KG原料原料B B0 01 1250KG 250KG 第一章：线性规划及单纯形法第一章：线性规划及单纯形法线性规划问题的数学模型线性规划问题的数学模型 目标函数：目标函数： maxz=50 xmaxz=50 x1 1+100 x+100 x2 2 x x1 1+x+x2 2300300 2x 2x1 1+x+x2 2400400 x x2 2250250 x x1 10 0 ，x x2 2 0 0 概念：可行解、最优解、最优

6、值概念：可行解、最优解、最优值 约束条件：约束条件：非负约束：非负约束： 第一章：线性规划及单纯形法第一章：线性规划及单纯形法500500万万m m3 3 练习：靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天练习：靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500500万万m m3 3，在两个工厂之间有一条流量为每天在两个工厂之间有一条流量为每天200200万万m m3 3支流，第一化工厂每天支流，第一化工厂每天排放含有某种有害物质的工业污水排放含有某种有害物质的工业污水2 2万万m m3 3 ，第二化工厂每天排放这种工，第二化工厂每天排放这种工业污水业污水1.41.4万万m

7、 m3 3 。从第一化工厂排出的工业污水流到第二化工厂以前，。从第一化工厂排出的工业污水流到第二化工厂以前，有有20%20%可自净化。根据环保要求，河流中工业污水的含量应不大于可自净化。根据环保要求，河流中工业污水的含量应不大于0.2%0.2%，这两个工厂都需各自处理一部分工业污水，第一化工厂处理工业污水的这两个工厂都需各自处理一部分工业污水，第一化工厂处理工业污水的成本是成本是10001000元元/ /万万m m3 3 。第二化工厂处理污水的的成本是。第二化工厂处理污水的的成本是800800元元/ /万万m m3 3 。现。现问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工问在

8、满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。厂总的处理工业污水费用最小。200200万万m m3 3工厂工厂1 1工厂工厂2 2 第一章：线性规划及单纯形法第一章：线性规划及单纯形法线性规划问题的数学模型线性规划问题的数学模型目标函数：目标函数：minz=1000 xminz=1000 x1 1+800 x+800 x2 2约束条件：约束条件： (2-x(2-x1 1)/5000.2%)/5000.2% 0.8(2-x0.8(2-x1 1) +(1.4-x) +(1.4-x2 2) )/700 0.2%/700 0.2% x x1 1 22 x x2

9、21.41.4非负约束：非负约束： x x1 10 0 ，x x2 2 0 0 线性规划的一般模式线性规划的一般模式目标函数：目标函数：max(min)Z=cmax(min)Z=c1 1x x1 1+c+c2 2x x2 2+c+c3 3x x3 3+ +c+cn nx xn n约束条件：约束条件：a a1111x x1 1+a+a1212x x2 2+a+a1313x x3 3+ +a+a1n1nx xn n (= )b(= )b1 1 a a2121x x1 1+a+a2222x x2 2+a+a2323x x3 3+ +a+a2n2nx xn n (= )b(= )b2 2 a am1m

10、1x x1 1+a+am2m2x x2 2+a+am3m3x x3 3+ +a+amnmnx xn n (= )b(= )bn n非负性约束：非负性约束：x x1 1 0,x0,x2 2 0, 0,x,xn n 00第第一一章：线性规划及单纯形法章：线性规划及单纯形法 解得：解得： 最大利润：最大利润：2750027500 X X1 1=50 X=50 X2 2=250=250代入得：代入得： 设备台时：设备台时：300300 原料原料A A：350350 原料原料B B：250250概念：松弛变量概念：松弛变量 剩余变量剩余变量第第一一章：线性规划及单纯形法章：线性规划及单纯形法 线性规划的

11、标准型线性规划的标准型 maxZ=cmaxZ=c1 1x x1 1+c+c2 2x x2 2+ +c+cn nx xn n a a1111x x1 1+a+a1212x x2 2+ +a+a1n1nx xn n=b=b1 1 a a2121x x1 1+a+a2222x x2 2+ +a+a2n2nx xn n=b=b2 2 a am1m1x x1 1+a+am2m2x x2 2+ +a+amnmnx xn n=b=bm m x xj j 0 0 j j=1,2,=1,2,n,n第第一一章：线性规划及单纯形法章：线性规划及单纯形法标准型的四个标准：求最大值、约束条件为等式、标准型的四个标准：求

12、最大值、约束条件为等式、bj 0. xbj 0. xj j 0 0 化非标准形线性规划为标准形式化非标准形线性规划为标准形式minz=xminz=x1 1+2x+2x2 2+3x+3x3 3 -2 -2x x1 1+x+x2 2+x+x3 3 9 9 -3x -3x1 1+x+x2 2+2x+2x3 3 400 400 4x 4x1 1-2x-2x2 2-3x-3x3 3=-6=-6 x x1 1 0,x 0,x2 2 0, x 0, x3 3取值无约束取值无约束 第第一一章：线性规划及单纯形法章：线性规划及单纯形法 练习：将下面线性规划问题化为标准形式练习：将下面线性规划问题化为标准形式 m

13、inz=2xminz=2x1 1-2x-2x2 2+3x+3x3 3 - -x x1 1+x+x2 2+x+x3 3 = 4= 4 -2x -2x1 1+x+x2 2-x-x3 3 6 6 x x1 1 0,x 0,x2 2 0, x 0, x3 3取值无约束取值无约束 第第一一章：线性规划及单纯形法章：线性规划及单纯形法 第一章：线性规划及单纯形法第一章：线性规划及单纯形法线性规划问题及其数学模型线性规划问题及其数学模型线性规划图解法线性规划图解法单纯形法原理单纯形法原理单纯形法计算步骤单纯形法计算步骤单纯形法的进一步讨论单纯形法的进一步讨论 400400200200100100100100

14、2002003003004004003003000 0 x x1 1x x2 2第第一一章：线性规划及单纯形法章：线性规划及单纯形法2x1+x2=400 x2=250 x1+x2=300目标函数：目标函数： maxz=50 xmaxz=50 x1 1+100 x+100 x2 2约束条件：约束条件： x x1 1+x+x2 2300300 2x 2x1 1+x+x2 2400 400 x x2 2250250非负约束：非负约束： x x1 10 0 ，x x2 200 4004002002001001001001002002003003004004003003000 0 x x1 1x x2

15、22x1+x2=400 x2=250 x1+x2=300第第一一章：线性规划及单纯形法章：线性规划及单纯形法可行域可行域 4004002002001001001001002002003003004004003003000 0 x x1 1x x2 22x1+x2=400 x2=250 x1+x2=300Z=0=50 x1+100 x2Z=1000=50 x1+100 x2Z=20000=50 x1+100 x2Z=27500=50 x1+100 x2第第一一章：线性规划及单纯形法章：线性规划及单纯形法等值线等值线 线性规划问题解的几种情况线性规划问题解的几种情况线性规划存在唯一最优解线性规划存

16、在唯一最优解线性规划存在有无穷多个最优解的情况线性规划存在有无穷多个最优解的情况线性规划可能存在无界解线性规划可能存在无界解线性规划存在无可行解的情况线性规划存在无可行解的情况第第一一章：线性规划及单纯形法章：线性规划及单纯形法 练习：练习：P43P43：1.11.1（1 1） （2 2）第第一一章：线性规划及单纯形法章：线性规划及单纯形法 第一章：线性规划及单纯形法第一章：线性规划及单纯形法线性规划问题及其数学模型线性规划问题及其数学模型线性规划图解法线性规划图解法单纯形法原理单纯形法原理单纯形法计算步骤单纯形法计算步骤单纯形法的进一步讨论单纯形法的进一步讨论 基本概念：基本概念：可行解可行

17、解最优解最优解基基基解基解基可行解基可行解可行基可行基第一章：线性规划及单纯形法第一章：线性规划及单纯形法 解的几何意义解的几何意义例例: : 线性规划问题基本可行解的意义：线性规划问题基本可行解的意义：2152maxxxZ0, 02224. .21212121xxxxxxxxts2152maxxxZ0,2224. .54321521421321xxxxxxxxxxxxxxts第一章：线性规划及单纯形法第一章：线性规划及单纯形法 解解的的几几何何意意义义 100110102100111A01112101101102111121BB00110101111102101143BB1010110011

18、0100101165BB第一章：线性规划及单纯形法第一章：线性规划及单纯形法 解解的的几几何何意意义义 100110102100111A 10100201100110201187BB100010001101012001109BB),(),(),(),(),(),(),(),(),(),(21314151324252435354xxxxxxxxxxxxxxxxxxxx第一章：线性规划及单纯形法第一章：线性规划及单纯形法 解解的的几几何何意意义义 100110102100111A ,00,00,00,00,00,00324252435354xxxxxxxxxxxx00,00,00314151xxx

19、xxx0021xx40602,04202,20022,03013,0064654321XXXXX第一章：线性规划及单纯形法第一章：线性规划及单纯形法 解解的的几几何何意意义义 100110102100111A ,00,00,00,00,00,00324252435354xxxxxxxxxxxx00,00,00314151xxxxxx0021xx22400,68040,30310,06620,26004109876XXXXX第一章：线性规划及单纯形法第一章：线性规划及单纯形法 解解的的几几何何意意义义212minxxZ0, 0302. .21121xxxxxts432002maxxxxxZ0,3

20、02432141321xxxxxxxxx10010121A110101110121321BBB001210011002654BBB第一章：线性规划及单纯形法第一章：线性规划及单纯形法 解解的的几几何何意意义义10010121A110101110121321BBB001210011002654BBB3000,3000,3000,0303,0023354321XXXXX第一章：线性规划及单纯形法第一章：线性规划及单纯形法 算算法法思思路路 求一个初始基本可行解求一个初始基本可行解 是是 判断基本可行解是否最优判断基本可行解是否最优 结结 束束 不是不是 求使目标得到改善的基本可行解求使目标得到改善

21、的基本可行解 是否存在？是否存在？如何得到？如何得到？是否唯一？是否唯一？如何判断？如何判断？如何改善？如何改善？如何判断没有有限最优解？如何判断没有有限最优解？第一章：线性规划及单纯形法第一章：线性规划及单纯形法 基基本本定定理理 若线性规划问题存在可行解，则该问若线性规划问题存在可行解，则该问题的可行解集（即可行域）是凸集。题的可行解集（即可行域）是凸集。 线性规划问题的基可行解线性规划问题的基可行解x x对应线性对应线性规划问题可行域规划问题可行域( (凸集凸集) )的顶点的顶点 若线性规划问题有最优解，一定存在若线性规划问题有最优解，一定存在一个基可行解（可行域顶点）是最优解，如一个基

22、可行解（可行域顶点）是最优解，如果在几个顶点上都出现最优解，则这些顶点果在几个顶点上都出现最优解，则这些顶点的每个凸组合上也达到最优。的每个凸组合上也达到最优。第一章：线性规划及单纯形法第一章：线性规划及单纯形法 凸凸集集的的概概念念 设设K K是是n n维欧氏空间的一个点维欧氏空间的一个点集，若任意两点集，若任意两点X X（1 1）K K，X X（2 2）K K的的连线上的一切点：连线上的一切点：（0100d1+0d2-=0d2-0(810,1476) 目标规划的这种求解方法可以表述如下：目标规划的这种求解方法可以表述如下： 1 1确定解的可行区域。确定解的可行区域。 2 2对优先权最高的目

23、标求解，如果找不到能满足该目标的解，对优先权最高的目标求解，如果找不到能满足该目标的解，则寻找最接近该目标的解。则寻找最接近该目标的解。 3 3对优先权次之的目标进行求解。注意：必须保证优先权高对优先权次之的目标进行求解。注意：必须保证优先权高的目标不变。的目标不变。 4. 4. 重复第重复第3 3步，直至所有优先权的目标求解完。步，直至所有优先权的目标求解完。 目标规划模型的标准化目标规划模型的标准化 例例6 6中对两个不同优先权的目标单独建立线性规划进行求解。为简中对两个不同优先权的目标单独建立线性规划进行求解。为简便，把它们用一个模型来表达，如下：便，把它们用一个模型来表达，如下： Mi

24、n PMin P1 1（d d1 1+ +）+P+P2 2（d d2 2- -） s.t.s.t. 20 x 20 x1 150 x50 x2 29000090000 0.5x 0.5x1 1 +0.2x +0.2x2 2-d-d1 1+ +d+d1 1- -=700=700 3x 3x1 1+4x+4x2 2-d-d2 2+ +d+d2 2- -=10000=10000 x x1 1,x,x2 2,d,d1 1+ +,d,d1 1- -,d,d2 2+ +,d,d2 2- -0 0 复杂情况下的目标规划复杂情况下的目标规划例例7 7一工艺品厂商手工生产某两种工艺品一工艺品厂商手工生产某两种工

25、艺品A A、B B，已知生产一件产品，已知生产一件产品A A需要需要耗费人力耗费人力2 2工时，生产一件产品工时，生产一件产品B B需要耗费人力需要耗费人力3 3工时。工时。A A、B B产品的单位产品的单位利润分别为利润分别为250250元和元和125125元。为了最大效率地利用人力资源，确定生产的元。为了最大效率地利用人力资源，确定生产的首要任务是保证人员高负荷生产，要求每周总耗费人力资源不能低于首要任务是保证人员高负荷生产，要求每周总耗费人力资源不能低于600600工时，但也不能超过工时，但也不能超过680680工时的极限；次要任务是要求每周的利润超过工时的极限；次要任务是要求每周的利润

26、超过7000070000元；在前两个任务的前提下，为了保证库存需要，要求每周产品元；在前两个任务的前提下，为了保证库存需要，要求每周产品A A和和B B的产量分别不低于的产量分别不低于200200和和120120件，因为件，因为B B产品比产品比A A产品更重要，不妨假产品更重要，不妨假设设B B完成最低产量完成最低产量120120件的重要性是件的重要性是A A完成完成200200件的重要性的件的重要性的1 1倍。倍。 试求如何安排生产？试求如何安排生产？ 解：本问题中有解：本问题中有3 3个不同优先权的目标，不妨用个不同优先权的目标，不妨用P P1 1、P P2 2、P P3 3表表示从高至

27、低的优先权。示从高至低的优先权。 对应对应P P1 1有两个目标：每周总耗费人力资源不能低于有两个目标：每周总耗费人力资源不能低于600600工工时时, ,也不能超过也不能超过680680工时；工时； 对应对应P P2 2有一个目标：每周的利润超过有一个目标：每周的利润超过7000070000元；元； 对应对应P P3 3有两个目标：每周产品有两个目标：每周产品A A和和B B的产量分别不低于的产量分别不低于200200和和120120件。件。 采用简化模式，最终得到目标线性规划如下：采用简化模式，最终得到目标线性规划如下： Min PMin P1 1(d(d1 1+ +)+ P)+ P1 1

28、(d(d2 2)+P)+P2 2(d(d3 3- -)+ P)+ P3 3(d(d4 4- -)+ P)+ P3 3(2d(2d5 5- -) ) s.t. s.t. 2x 2x1 1+3x+3x2 2-d-d1 1+ +d+d1 1- -=680 =680 对应第对应第1 1个目标个目标 2x2x1 1+3x+3x2 2-d-d2 2+ +d+d2 2- -=600 =600 对应第对应第2 2个目标个目标 250 x250 x1 1+125x+125x2 2-d-d3 3- -+d+d3 3+ +70000 70000 对应第对应第3 3个目标个目标 x x1 1-d-d4 4+ +d+d

29、4 4- -=200 =200 对应第对应第4 4个目标个目标 x x2 2-d-d5 5+ +d+d5 5- -=120 =120 对应第对应第5 5个目标个目标 x x1 1,x,x2 2,d,d1 1+ +,d,d1 1- -,d,d2 2+ +,d,d2 2- -,d,d3 3+ +,d,d3 3- -,d,d4 4+ +,d,d4 4- -,d,d5 5+ +,d,d5 5- -00 使用运筹学软件求解可得：使用运筹学软件求解可得：x x1 1=250=250；x x2 2=60=60；d d1 1+ +=0=0；d d1 1- -=0=0；d d2 2+ +=80=80；d d2

30、2- -=0=0；d d3 3+ +=0=0；d d3 3- -=0=0；d d4 4+ +=50=50；d d4 4- -=0=0；d d5 5+ +=0=0；d d5 5- -=60=60，目标函数，目标函数d d4 4- -+2d+2d5 5- - =120 =120。 可见，目标可见，目标1 1、目标、目标3 3和目标和目标4 4达到了，但目标达到了，但目标2 2、目标、目标5 5都有一些偏差。都有一些偏差。 加权目标规划加权目标规划 加权目标规划加权目标规划是另一种解决多目标决策问题的方法，其基本方法是通过是另一种解决多目标决策问题的方法，其基本方法是通过量化的方法分配给每个目标的偏

31、离的严重程度一个罚数权重，然后建立总量化的方法分配给每个目标的偏离的严重程度一个罚数权重，然后建立总的目标函数，该目标函数表示的目标是要使每个目标函数与各自目标的加的目标函数，该目标函数表示的目标是要使每个目标函数与各自目标的加权偏差之和最小，假设所有单个的目标函数及约束条件都符合线性规划的权偏差之和最小，假设所有单个的目标函数及约束条件都符合线性规划的要求，那么，整个问题都可以描述为一个线性规划的问题。要求，那么，整个问题都可以描述为一个线性规划的问题。 如果在例如果在例7 7中我们对每周总耗费的人力资源超过中我们对每周总耗费的人力资源超过680680工时或低于工时或低于600600工时工时

32、的每工时罚数权重定为的每工时罚数权重定为7 7；每周利润低于；每周利润低于7000070000元时，每元的罚数权重为元时，每元的罚数权重为5 5；每周产品；每周产品A A产量低于产量低于200200件时每件罚数权重为件时每件罚数权重为2 2，而每周产品，而每周产品B B产量低产量低于于120120件时每件罚数权重为件时每件罚数权重为4 4。 则其目标函数化为：则其目标函数化为： min7dmin7d1 1+ +7d+7d2 2- -+5d+5d3 3- -+2d+2d4 4- -+4d+4d5 5- - 这就变成了一个普通的单一目标的线性规划问题这就变成了一个普通的单一目标的线性规划问题 mi

33、n7dmin7d1 1+ +7d+7d2 2- -+5d+5d3 3- -+2d+2d4 4- -+4d+4d5 5- - s.t. 2x s.t. 2x1 1+3x+3x2 2-d-d1 1+ +d+d1 1- -=680=680 2x 2x1 1+3x+3x2 2-d-d2 2- -+d+d2 2+ +=680=680 250 x 250 x1 1+125x+125x2 2-d-d3 3- -+d+d3 3+ +=70000=70000 x x1 1-d-d4 4+ +d+d4 4- -=200=200 x x2 2-d-d5 5+ +d+d5 5- -=120=120 x x1 1,x,

34、x2 2,d,d1 1+ +,d,d1 1- -,d,d2 2- -,d,d2 2+ +, d, d3 3+ +,d,d3 3- -,d,d4 4+ +,d,d4 4- -,d,d5 5+ +,d,d5 5- -0 0 。 第八章第八章 整数规划整数规划 在整数规划中，如果所有的变量都为非负整数，则称为在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问题纯整数规划问题；如果有一部分变量为负整数，则称之；如果有一部分变量为负整数，则称之为为混合整数规划问题混合整数规划问题。在整数规划中，如果变量的取值。在整数规划中，如果变量的取值只限于只限于0 0和和1 1，这样的变量我们称之为，这样

35、的变量我们称之为0-10-1变量变量。在纯整数。在纯整数规划和混合整数规划问题中，如果所有的变量都为规划和混合整数规划问题中，如果所有的变量都为0-10-1变变量，则称之为量，则称之为0-10-1规划规划。第五章第五章 整数规划整数规划 整数规划的图解法整数规划的图解法例例: :某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。获利润以及托运所受限制如表所示。甲种货物至多托运甲种货物至多托运4 4件，问两种货物各托运多少件，可使获得利润最大。件，问两种货物各托运多少件，可使获得利润

36、最大。解：设解：设x x1 1 、 x x2 2分别为甲、乙两种货物托运的件数，建立模型分别为甲、乙两种货物托运的件数，建立模型 目标函数：目标函数： Max z = 2xMax z = 2x1 1 +3 x+3 x2 2 约束条件：约束条件： 195195 x x1 1 + 273 x+ 273 x2 2 1365 1365 4 4 x x1 1 + 40 x+ 40 x2 2 140140 x x1 1 44 x x1 1，x x2 2 0 0 为整数。为整数。如果去掉最后一个约束，就是一个线性规划问题。利用图解法，如果去掉最后一个约束，就是一个线性规划问题。利用图解法，货物每件体积（立方

37、英尺）每件重量（百千克）每件利润（百元）甲乙19527344023托运限制1365140 得到线性规划的最优解为得到线性规划的最优解为x x1 1=2.44, x=2.44, x2 2=3.26,=3.26,目标函数值为目标函数值为14.6614.66。由图表可。由图表可看出，整数规划的最优解为看出，整数规划的最优解为x x1 1=4, x=4, x2 2=2,=2,目标函数值为目标函数值为1414。性质。性质1 1：任何求最：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值

38、；任何求最小目标函数值的纯整数规划或混应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。值。12341232x1+3x2 =14.66x1 x2 2x1+3x2 =142x1+3x2 =6整数规划的图解法整数规划的图解法 例例2 2： Max z = 3Max z = 3x x1 1 + + x x2 2 + 3 + 3x x3 3 s.t. s.t. - -x x1 1 + 2 + 2x x2 2 + + x x3 3 4 4 4 4x x2 2

39、 -3 -3x x3 3 2 2 x x1 1 -3-3x x2 2 + 2 + 2x x3 3 3 3 x x1 1, ,x x2 2, ,x x3 3 0 0 为整数为整数例例3 3： Max z = 3xMax z = 3x1 1 + x + x2 2 + 3x + 3x3 3 s.t.s.t. -x -x1 1 + 2x + 2x2 2 + x + x3 3 4 4 4x 4x2 2 -3x -3x3 3 2 2 x x1 1 -3x -3x2 2 + 2x + 2x3 3 3 3 x x3 3 1 1 x x1 1,x,x2 2,x,x3 3 0 0 x x1 1，x x3 3 为整

40、数为整数 x x3 3为为0-10-1变量变量用用管理运筹学管理运筹学软件求解得：软件求解得： x x1 1 = 5 = 5 x x2 2 = 2 = 2 x x3 3 = 2 = 2 用用管理运筹学管理运筹学软件求解得：软件求解得： x x1 1 = 4 = 4 x x2 2 = 1.25 = 1.25 x x3 3 = 1 = 1 z = 16.25 z = 16.25整数规划的计算机求解整数规划的计算机求解 整数规划的应用整数规划的应用投资场所的选择投资场所的选择例例4 4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，、京成畜产品公司计划在市区的东、西、南、北四区建立销售

41、门市部，拟议中有拟议中有1010个位置个位置 A Aj j (j(j1 1，2 2，3 3，10)10)可供选择，考虑到各地区居可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：民的消费水平及居民居住密集度，规定： 在东区由在东区由A A1 1 ， A A2 2 ，A A3 3 三个点至多选择两个；三个点至多选择两个； 在西区由在西区由A A4 4 ， A A5 5 两个点中至少选一个；两个点中至少选一个； 在南区由在南区由A A6 6 ， A A7 7 两个点中至少选一个；两个点中至少选一个； 在北区由在北区由A A8 8 ， A A9 9 ， A A1010 三个点中至少选两个。

42、三个点中至少选两个。 A Aj j 各点的设备投资及每年可获利润由于地点不同都是不一样的，预各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示测情况见表所示 ( (单位：万元单位：万元) )。但投资总额不能超过。但投资总额不能超过720720万元，问应选择万元，问应选择哪几个销售点，可使年利润为最大哪几个销售点，可使年利润为最大? ? 解：解：设：设：0-10-1变量变量x xi i = 1(A = 1(Ai i 点被选用）或点被选用）或0 0( (A Ai i 点没被选用）。点没被选用）。 这样我们可建立如下的数学模型：这样我们可建立如下的数学模型：Max z =36Ma

43、x z =36x x1 1+40+40 x x2 2+50+50 x x3 3+22+22x x4 4+20+20 x x5 5+30+30 x x6 6+25+25x x7 7+48+48x x8 8+58+58x x9 9+61+61x x1010s.t.s.t.100100 x x1 1+120+120 x x2 2+150+150 x x3 3+80+80 x x4 4+70+70 x x5 5+90+90 x x6 6+80+80 x x7 7+140+140 x x8 8+160+160 x x9 9+180+180 x x1010 720720 x x1 1 + + x x2 2

44、 + + x x3 3 2 2 x x4 4 + + x x5 5 1 1 x x6 6 + + x x7 7 1 1 x x8 8 + + x x9 9 + + x x1010 2 2 x xi i 0 0 且且x xi i 为为0-10-1变量变量，i i = 1,2,3,= 1,2,3,10,10 固定成本问题固定成本问题 例例5 5高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用

45、，每种容器售出一只所得的利润分别为示。不考虑固定费用，每种容器售出一只所得的利润分别为 4 4万元、万元、5 5万万元、元、6 6万元，可使用的金属板有万元，可使用的金属板有500500吨，劳动力有吨，劳动力有300300人人/ /月，机器有月，机器有100100台台/ /月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是号是l00l00万元，中号为万元，中号为 150 150 万元，大号为万元，大号为200200万元。现在要制定一个生产计万元。现在要制定一个生产计划，使获得的利润为最大。划，使获得的利润为最大。

46、 资源小号容器中号容器大号容器金属板（吨）248劳动力（人月）234机器设备（台月）123 解：这是一个整数规划的问题。解：这是一个整数规划的问题。设设x x1 1，x x2 2， x x3 3 分别为小号容器、中号容器和大号容器的生产数量。各分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设这种性质，设 y yi i = 1( = 1(当生产第当生产第 i i种容器种容器, , 即即 x xi i 0 0 时时) ) 或或0 0（当不生当不生产第产第 i i种

47、容器即种容器即 x xi i = 0 = 0 时）。引入约束时）。引入约束 x xi i M M y yi i ，i =1i =1，2 2，3 3，M M充分大，以保证当充分大，以保证当 y yi i = 0= 0时，时，x xi i= 0 = 0 。 这样我们可建立如下的数学模型：这样我们可建立如下的数学模型：Max z = 4Max z = 4x x1 1 + 5+ 5x x2 2 + 6+ 6x x3 3 - 100y- 100y1 1 - 150y- 150y2 2 - 200y- 200y3 3s.t. 2s.t. 2x x1 1 + 4+ 4x x2 2 + 8+ 8x x3 3

48、500 500 2 2x x1 1 + 3+ 3x x2 2 + 4+ 4x x3 3 300 300 x x1 1 + 2+ 2x x2 2 + 3+ 3x x3 3 100 100 x xi i M M y yi i ，i =1i =1，2 2，3 3，M M充分大充分大 x xj j 0 0 y yj j 为为0-10-1变量变量，i i = 1,2,3= 1,2,3 指派问题指派问题 有有 n n 项不同的任务，恰好项不同的任务，恰好 n n 个人可分别承担这些任务，但由于每人个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人特长不同，完成

49、各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把去完成一项任务，怎样把 n n 项任务指派给项任务指派给 n n 个人，使得完成个人，使得完成 n n 项任项任务的总的效率最高，这就是务的总的效率最高，这就是指派问题。指派问题。例例6 6有四个工人，要分别指派他们完成四项不同的工作，每人做各项有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。间为最少。 工 作工 人ABCD甲15182124乙19232218丙26171619丁192

50、12317 解：引入解：引入0 01 1变量变量 x xijij，并令并令x xij ij = 1(= 1(当指派第当指派第 i i人去完成第人去完成第j j项工作项工作时时) )或或0 0（当不指派第（当不指派第 i i人去完成第人去完成第j j项工作时项工作时) )这可以表示为一个这可以表示为一个0-10-1整数规划问题：整数规划问题：Minz=15Minz=15x x1111+18+18x x1212+21+21x x1313+24+24x x1414+19+19x x2121+23+23x x2222+22+22x x2323+18+18x x2424+26+26x x3131+17+