《运筹学本科》PPT课件.ppt

管理运筹学管理运筹学主讲：谢先达主讲：谢先达2011.092011.09 联系方式联系方式办公室：办公室：QL643 87313663QL643 87313663手机：手机：13600512360 13600512360邮箱：邮箱： 绪绪 论论 绪论绪论什么是运筹学？什么是运筹学？运筹学发展历史运筹学发展历史运筹学主要内容运筹学主要内容运筹学的基本特征与基本方法运筹学的基本特征与基本方法 绪论绪论什么是运筹学？什么是运筹学？定义：定义：为决策机构在对其控制下业务活动进行为决策机构在对其控制下业务活动进行决策决策时，提供以时，提供以数量化数量化为基础的科学方法。为基础的科学方法。西蒙：管理就是决策西蒙：管理就是决策 决策决策 定性定性管理者的判断和经验管理者的判断和经验定量定量运筹运筹学学 绪论绪论运筹学发展历史运筹学发展历史古代运筹思想：田忌赛马、古代运筹思想：田忌赛马、丁渭修皇宫丁渭修皇宫 二战期间的二战期间的Operational Research Operational Research 研究成果被应用到生产、经济领域，且研究不断深研究成果被应用到生产、经济领域，且研究不断深化，逐步形成化，逐步形成“运筹学运筹学”绪论绪论 绪论绪论运筹学的主要内容有哪些？运筹学的主要内容有哪些？线性规划线性规划运输问题运输问题整数规划整数规划目标规划目标规划动态规划动态规划图与网络分析图与网络分析网络计划网络计划存储论存储论排队论排队论对策论对策论决策分析决策分析预测预测 绪论绪论运筹学研究的基本特征运筹学研究的基本特征系统的整体观念系统的整体观念多学科的综合多学科的综合模型方法的应用模型方法的应用 绪论绪论运筹学研究的基本方法运筹学研究的基本方法分析和表述问题分析和表述问题建立模型建立模型求解模型和优化方案求解模型和优化方案测试模型及对模型进行必要的修正测试模型及对模型进行必要的修正建立对解的有效控制建立对解的有效控制方案的实施方案的实施 第一章：线性规划及单纯形法第一章：线性规划及单纯形法 第一章：线性规划及单纯形法第一章：线性规划及单纯形法线性规划问题及其数学模型线性规划问题及其数学模型线性规划图解法线性规划图解法单纯形法原理单纯形法原理单纯形法计算步骤单纯形法计算步骤单纯形法的进一步讨论单纯形法的进一步讨论 第一章：线性规划及单纯形法第一章：线性规划及单纯形法例题：某工厂在计划期内要安排例题：某工厂在计划期内要安排、两种产品的生产，生两种产品的生产，生产单位产品所需的设备台时及产单位产品所需的设备台时及A A、两种原材料的消耗以及、两种原材料的消耗以及资源的限制如表所示资源的限制如表所示 工厂每生产一单位产品工厂每生产一单位产品可获利可获利5050元，每生产一单位产品元，每生产一单位产品可获利可获利100100元，问工厂应分别生产多少单位产品元，问工厂应分别生产多少单位产品 和产品和产品才能获利最多？才能获利最多？资源限制资源限制设备设备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 概念：可行解、最优解、最优值概念：可行解、最优解、最优值 约束条件：约束条件：非负约束：非负约束：第一章：线性规划及单纯形法第一章：线性规划及单纯形法500500万万m m3 3练习：靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天练习：靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500500万万m m3 3，在两个工厂之间有一条流量为每天在两个工厂之间有一条流量为每天200200万万m m3 3支流，第一化工厂每天支流，第一化工厂每天排放含有某种有害物质的工业污水排放含有某种有害物质的工业污水2 2万万m m3 3 ，第二化工厂每天排放这种工，第二化工厂每天排放这种工业污水业污水1.41.4万万m m3 3 。从第一化工厂排出的工业污水流到第二化工厂以前，。从第一化工厂排出的工业污水流到第二化工厂以前，有有20%20%可自净化。根据环保要求，河流中工业污水的含量应不大于可自净化。根据环保要求，河流中工业污水的含量应不大于0.2%0.2%，这两个工厂都需各自处理一部分工业污水，第一化工厂处理工业污水的这两个工厂都需各自处理一部分工业污水，第一化工厂处理工业污水的成本是成本是10001000元元/万万m m3 3 。第二化工厂处理污水的的成本是。第二化工厂处理污水的的成本是800800元元/万万m m3 3 。现。现问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。厂总的处理工业污水费用最小。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 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 am1m1x 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,x 0,xn n 00第第一一章：线性规划及单纯形法章：线性规划及单纯形法 解得：解得：最大利润：最大利润：2750027500 X X1 1=50 X=50 X2 2=250=250代入得：代入得：设备台时：设备台时：300300 原料原料A A：350350 原料原料B B：250250概念：松弛变量概念：松弛变量 剩余变量剩余变量第第一一章：线性规划及单纯形法章：线性规划及单纯形法 线性规划的标准型线性规划的标准型 maxZ=c maxZ=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,n=1,2,n第第一一章：线性规划及单纯形法章：线性规划及单纯形法标准型的四个标准：求最大值、约束条件为等式、标准型的四个标准：求最大值、约束条件为等式、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取值无约束取值无约束 第第一一章：线性规划及单纯形法章：线性规划及单纯形法 练习：将下面线性规划问题化为标准形式练习：将下面线性规划问题化为标准形式 minz=2x minz=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取值无约束取值无约束 第第一一章：线性规划及单纯形法章：线性规划及单纯形法 第一章：线性规划及单纯形法第一章：线性规划及单纯形法线性规划问题及其数学模型线性规划问题及其数学模型线性规划图解法线性规划图解法单纯形法原理单纯形法原理单纯形法计算步骤单纯形法计算步骤单纯形法的进一步讨论单纯形法的进一步讨论 4004002002001001001001002002003003004004003003000 0 x x1 1x x2 2第第一一章：线性规划及单纯形法章：线性规划及单纯形法2x1+x2=400 x2=250 x1+x2=300目标函数：目标函数：maxz=50 x maxz=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 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=10000=50 x1+100 x2Z=20000=50 x1+100 x2Z=27500=50 x1+100 x2第第一一章：线性规划及单纯形法章：线性规划及单纯形法等值线等值线 线性规划问题解的几种情况线性规划问题解的几种情况线性规划存在唯一最优解线性规划存在唯一最优解线性规划存在有无穷多个最优解的情况线性规划存在有无穷多个最优解的情况线性规划可能存在无界解线性规划可能存在无界解线性规划存在无可行解的情况线性规划存在无可行解的情况第第一一章：线性规划及单纯形法章：线性规划及单纯形法 练习：练习：P43P43：1.11.1（1 1）（2 2）第第一一章：线性规划及单纯形法章：线性规划及单纯形法 第一章：线性规划及单纯形法第一章：线性规划及单纯形法线性规划问题及其数学模型线性规划问题及其数学模型线性规划图解法线性规划图解法单纯形法原理单纯形法原理单纯形法计算步骤单纯形法计算步骤单纯形法的进一步讨论单纯形法的进一步讨论 基本概念：基本概念：可行解可行解最优解最优解基基基解基解基可行解基可行解可行基可行基第一章：线性规划及单纯形法第一章：线性规划及单纯形法 解的几何意义解的几何意义例例:线性规划问题基本可行解的意义：线性规划问题基本可行解的意义：第一章：线性规划及单纯形法第一章：线性规划及单纯形法 解解的的几几何何意意义义第一章：线性规划及单纯形法第一章：线性规划及单纯形法 解解的的几几何何意意义义第一章：线性规划及单纯形法第一章：线性规划及单纯形法 解解的的几几何何意意义义第一章：线性规划及单纯形法第一章：线性规划及单纯形法 解解的的几几何何意意义义第一章：线性规划及单纯形法第一章：线性规划及单纯形法 解解的的几几何何意意义义第一章：线性规划及单纯形法第一章：线性规划及单纯形法 解解的的几几何何意意义义第一章：线性规划及单纯形法第一章：线性规划及单纯形法 算算法法思思路路求一个初始基本可行解求一个初始基本可行解是是 判断基本可行解是否最优判断基本可行解是否最优结结 束束不是不是求使目标得到改善的基本可行解求使目标得到改善的基本可行解是否存在？是否存在？如何得到？如何得到？是否唯一？是否唯一？如何判断？如何判断？如何改善？如何改善？如何判断没有有限最优解？如何判断没有有限最优解？第一章：线性规划及单纯形法第一章：线性规划及单纯形法 基基本本定定理理定定定定理理理理1 1 1 1 若若线线性性规规划划问问题题存存在在可可行行解解，则则该该问问题题的可行解集（即可行域）是凸集。的可行解集（即可行域）是凸集。定定定定理理理理2 2 2 2 线线性性规规划划问问题题的的基基可可行行解解x x对对应应线线性性规规划问题可行域划问题可行域(凸集凸集)的顶点的顶点定定定定理理理理3 3 3 3 若若线线性性规规划划问问题题有有最最优优解解，一一定定存存在在一一个个基基可可行行解解（可可行行域域顶顶点点）是是最最优优解解，如如果果在在几几个个顶顶点点上上都都出出现现最最优优解解，则则这这些些顶顶点点的每个凸组合上也达到最优。的每个凸组合上也达到最优。第一章：线性规划及单纯形法第一章：线性规划及单纯形法 凸凸集集的的概概念念1 1、基本概念：、基本概念：凸集凸集设设K K是是n n维欧氏空间的一个点维欧氏空间的一个点集，若任意两点集，若任意两点X X（1 1）K K，X X（2 2）K K的的连线上的一切点：连线上的一切点：XX（1 1）+（1-1-）X X（2 2）K K（0101），则称），则称K K为为凸集凸集。第一章：线性规划及单纯形法第一章：线性规划及单纯形法 凸凸集集的的概概念念凸组合凸组合凸组合凸组合设设X X（1 1），X X（2 2），X X（k k）是是n n维欧氏空维欧氏空间中的间中的K K个点，若存在个点，若存在k k个数个数1 1，2 2，k k,满满足足00i i1,i=1,2,k1,i=1,2,k；则则称称X=X=1 1X X（1 1）+2 2X X（2 2）+k kX X(k)(k)为为X X（1 1）,，X X（2 2），X X（k k）的的凸组合凸组合。顶点顶点顶点顶点设设K K是凸集，是凸集，X X K K；若；若K K中不存在两个不同的中不存在两个不同的点点X X（1 1）K K，X X（2 2）K K 使使 X=XX=XX=XX=X（1 1 1 1）+（1-1-1-1-）X X X X（2 2 2 2）（01010100d1+0d2-=0d2-0(810,1476)目标规划的这种求解方法可以表述如下：目标规划的这种求解方法可以表述如下：1 1确定解的可行区域。确定解的可行区域。2 2对对优优先先权权最最高高的的目目标标求求解解，如如果果找找不不到到能能满满足足该该目目标标的的解解，则寻找最接近该目标的解。则寻找最接近该目标的解。3 3对对优优先先权权次次之之的的目目标标进进行行求求解解。注注意意：必必须须保保证证优优先先权权高高的目标不变。的目标不变。4.4.重复第重复第3 3步，直至所有优先权的目标求解完。步，直至所有优先权的目标求解完。目标规划模型的标准化目标规划模型的标准化 例例6 6中对两个不同优先权的目标单独建立线性规划进行求解。为简中对两个不同优先权的目标单独建立线性规划进行求解。为简便，把它们用一个模型来表达，如下：便，把它们用一个模型来表达，如下：Min PMin P1 1（d d1 1+）+P+P2 2（d d2 2-）s.ts.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一一工工艺艺品品厂厂商商手手工工生生产产某某两两种种工工艺艺品品A A、B B，已已知知生生产产一一件件产产品品A A需需要要耗耗费费人人力力2 2工工时时，生生产产一一件件产产品品B B需需要要耗耗费费人人力力3 3工工时时。A A、B B产产品品的的单单位位利利润润分分别别为为250250元元和和125125元元。为为了了最最大大效效率率地地利利用用人人力力资资源源，确确定定生生产产的的首首要要任任务务是是保保证证人人员员高高负负荷荷生生产产，要要求求每每周周总总耗耗费费人人力力资资源源不不能能低低于于600600工工时时，但但也也不不能能超超过过680680工工时时的的极极限限；次次要要任任务务是是要要求求每每周周的的利利润润超超过过7000070000元元；在在前前两两个个任任务务的的前前提提下下，为为了了保保证证库库存存需需要要，要要求求每每周周产产品品A A和和B B的的产产量量分分别别不不低低于于200200和和120120件件，因因为为B B产产品品比比A A产产品品更更重重要要，不不妨妨假假设设B B完完成成最最低低产量产量120120件的重要性是件的重要性是A A完成完成200200件的重要性的件的重要性的2 2倍。倍。试求如何安排生产？试求如何安排生产？解：本问题中有解：本问题中有3 3个不同优先权的目标，不妨用个不同优先权的目标，不妨用P P1 1、P P2 2、P P3 3表表示从高至低的优先权。示从高至低的优先权。对应对应P P1 1有两个目标：每周总耗费人力资源不能低于有两个目标：每周总耗费人力资源不能低于600600工工时时,也不能超过也不能超过680680工时；工时；对应对应P P2 2有一个目标：每周的利润超过有一个目标：每周的利润超过7000070000元；元；对对应应P P3 3有有两两个个目目标标：每每周周产产品品A A和和B B的的产产量量分分别别不不低低于于200200和和120120件。件。采用简化模式，最终得到目标线性规划如下：采用简化模式，最终得到目标线性规划如下：Min P Min P1 1(d(d1 1+)+P)+P1 1(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个目标个目标 2x 2x1 1+3x+3x2 2-d-d2 2+d+d2 2-=600 =600 对应第对应第2 2个目标个目标 250 x 250 x1 1+125x+125x2 2+d+d3 3-d-d3 3+70000 70000 对应第对应第3 3个目标个目标 x x1 1-d-d4 4+d+d4 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 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都有一些偏差。都有一些偏差。加权目标规划加权目标规划加权目标规划加权目标规划是另一种解决多目标决策问题的方法，其基本方法是通过是另一种解决多目标决策问题的方法，其基本方法是通过量化的方法分配给每个目标的偏离的严重程度一个罚数权重，然后建立总量化的方法分配给每个目标的偏离的严重程度一个罚数权重，然后建立总的目标函数，该目标函数表示的目标是要使每个目标函数与各自目标的加的目标函数，该目标函数表示的目标是要使每个目标函数与各自目标的加权偏差之和最小，假设所有单个的目标函数及约束条件都符合线性规划的权偏差之和最小，假设所有单个的目标函数及约束条件都符合线性规划的要求，那么，整个问题都可以描述为一个线性规划的问题。要求，那么，整个问题都可以描述为一个线性规划的问题。如果在例如果在例7 7中我们对每周总耗费的人力资源超过中我们对每周总耗费的人力资源超过680680工时或低于工时或低于600600工时工时的每工时罚数权重定为的每工时罚数权重定为7 7；每周利润低于；每周利润低于7000070000元时，每元的罚数权重为元时，每元的罚数权重为5 5；每周产品；每周产品A A产量低于产量低于200200件时每件罚数权重为件时每件罚数权重为2 2，而每周产品，而每周产品B B产量低产量低于于120120件时每件罚数权重为件时每件罚数权重为4 4。则其目标函数化为：则其目标函数化为：min7d min7d1 1+7d+7d2 2-+5d+5d3 3-+2d+2d4 4-+4d+4d5 5-这就变成了一个普通的单一目标的线性规划问题这就变成了一个普通的单一目标的线性规划问题 min7d min7d1 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,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，这样的变量我们称之为，这样的变量我们称之为0-10-1变量变量。在纯整数。在纯整数规划和混合整数规划问题中，如果所有的变量都为规划和混合整数规划问题中，如果所有的变量都为0-10-1变变量，则称之为量，则称之为0-10-1规划规划。第五章第五章 整数规划整数规划 整数规划的图解法整数规划的图解法例例:某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。获利润以及托运所受限制如表所示。甲种货物至多托运甲种货物至多托运4 4件，问两种货物各托运多少件，可使获得利润最大。件，问两种货物各托运多少件，可使获得利润最大。解：设解：设x x1 1、x x2 2分别为甲、乙两种货物托运的件数，建立模型分别为甲、乙两种货物托运的件数，建立模型 目标函数：目标函数：Max z=2x Max z=2x1 1+3 x+3 x2 2 约束条件：约束条件：195 195 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 为整数。为整数。如果去掉最后一个约束，就是一个线性规划问题。利用图解法，如果去掉最后一个约束，就是一个线性规划问题。利用图解法，货物每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲乙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：任何求最：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。值。12341232x1+3x2=14.66x1x22x1+3x2=142x1+3x2=6整数规划的图解法整数规划的图解法 例例2 2：Max z=3 Max 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-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=3x Max 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 为整数为整数 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、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有拟议中有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 三个点中至少选两个。三个点中至少选两个。A Aj j 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示情况见表所示 (单位：万元单位：万元)。但投资总额不能超过。但投资总额不能超过720720万元，问应选择哪万元，问应选择哪几个销售点，可使年利润为最大几个销售点，可使年利润为最大?解：解：设：设：0-10-1变量变量x xi i=1(A=1(Ai i 点被选用）或点被选用）或0 0(A(Ai i 点没被选用）。点没被选用）。这样我们可建立如下的数学模型：这样我们可建立如下的数学模型：Max z=36Max 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+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,10=1,2,3,10 固定成本问题固定成本问题 例例5 5高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为示。不考虑固定费用，每种容器售出一只所得的利润分别为 4 4万元、万元、5 5万万元、元、6 6万元，可使用的金属板有万元，可使用的金属板有500500吨，劳动力有吨，劳动力有300300人人/月，机器有月，机器有100100台台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是号是l00l00万元，中号为万元，中号为 150 150 万元，大号为万元，大号为200200万元。现在要制定一个生产计万元。现在要制定一个生产计划，使获得的利润为最大。划，使获得的利润为最大。解：这是一个整数规划的问题。解：这是一个整数规划的问题。设设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种容器即种容器即 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 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 个人可分别承担这些任务，但由于每人个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把去完成一项任务，怎样把 n n 项任务指派给项任务指派给 n n 个人，使得完成个人，使得完成 n n 项任项任务的总的效率最高，这就是务的总的效率最高，这就是指派问题。指派问题。例例6 6有四个工人，要分别指派他们完成四项不同的工作，每人做各项有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。间为最少。解：引入解：引入0101变量变量 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+17x x3232+16+16x x3333+19+19x x3434+19+19x x41 41+21+21x x4242+23+23x x4343+17+17x x4444s.t.s.t.x x1111+x x1212+x x1313+x x1414=1 (=1 (甲只能干一项工作甲只能干一项工作)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 (A=1 (A工作只能一人干工作只能一人干)x x1212+x x2222+x x3232+x x4242=1 (B=1 (B工作只能一人干工作只能一人干)x x1313+x x2323+x x3333+x x4343=1 (C=1 (C工作只能一人干工作只能一人干)x x1414+x x2424+x x3434+x x4444=1 (D=1 (D工作只能一人干工作只能一人干)x xijij 为为0-10-1变量变量，i,j i,j=1,2,3,4=1,2,3,4 *求解可用管理运筹学软件中整数规划方法。求解可用管理运筹学软件中整数规划方法。分布系统设计分布系统设计例例7 7某企业在某企业在 A A1 1 地已有一个工厂，其产品的生产能力为地已有一个工厂，其产品的生产能力为 30 30 千箱，为了千箱，为了扩大生产，打算在扩大生产，打算在 A A2 2，A A3 3，A A4 4，A A5 5地中再选择几个地方建厂。已知在地中再选择几个地方建厂。已知在 A A2 2，A A3 3，A A4 4，A A5 5地建厂的固定成本分别为地建厂的固定成本分别为175175千元、千元、300300千元、千元、375375千元、千元、500500千元，另外，千元，另外，A A1 1产量及产