运筹学(胡运权第四版及答案)

管理运筹学主讲：谢先达2014.09联系方式办公室：QL64387313663手机：[phone]邮箱：[e-mail]绪论绪论什么是运筹学？运筹学发展历史运筹学主要内容运筹学的基本特征与基本方法绪论什么是运筹学？定义：为决策机构在对其控制下业务活动进行决策时，提供以数量化为基础的科学方法。西蒙：管理就是决策决策定性管理者的判断和经验定量运筹学绪论运筹学发展历史古代运筹思想：田忌赛马、丁渭修皇宫二战期间的OperationalResearch研究成果被应用到生产、经济领域，且研究不断深化，逐步形成“运筹学”绪论绪论运筹学的主要内容有哪些？线性规划运输问题整数规划目标规划动态规划图与网络模型排序与统筹方法存储论排队论对策论决策分析预测绪论运筹学研究的基本特征系统的整体观念多学科的综合模型方法的应用绪论运筹学研究的基本方法分析和表述问题建立模型求解模型和优化方案测试模型及对模型进行必要的修正建立对解的有效控制方案的实施第一章：线性规划及单纯形法第一章：线性规划及单纯形法线性规划问题及其数学模型线性规划图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论第一章：线性规划及单纯形法例题：某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，生产单位产品所需的设备台时及A、Ｂ两种原材料的消耗以及资源的限制如表所示工厂每生产一单位产品Ⅰ可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应分别生产多少单位产品Ⅰ和产品Ⅱ才能获利最多？ⅠⅡ资源限制设备11300台时原料A21400KG原料B01250KG第一章：线性规划及单纯形法线性规划问题的数学模型目标函数：maxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1≥0，x2≥0概念：可行解、最优解、最优值约束条件：非负约束：250KG10原料B400KG12原料A300台时11设备资源限制ⅡⅠ250KG10原料B400KG12原料A300台时11设备资源限制ⅡⅠ第一章：线性规划及单纯形法500万m3练习：靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为每天200万m3支流，第一化工厂每天排放含有某种有害物质的工业污水2万m3，第二化工厂每天排放这种工业污水1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自净化。根据环保要求，河流中工业污水的含量应不大于0.2%，这两个工厂都需各自处理一部分工业污水，第一化工厂处理工业污水的成本是1000元/万m3。第二化工厂处理污水的的成本是800元/万m3。现问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。200万m3工厂1工厂2第一章：线性规划及单纯形法线性规划问题的数学模型目标函数：minz=1000x1+800x2约束条件：(2-x1)/500≤0.2%〔0.8(2-x1)+(1.4-x2)〕/700≤0.2%x1≤2x2≤1.4非负约束：x1≥0，x2≥0线性规划的一般模式目标函数：max(min)Z=c1x1+c2x2+c3x3+…+cnxn约束条件：a11x1+a12x2+a13x3+…+a1nxn≤(=≥)b1a21x1+a22x2+a23x3+…+a2nxn≤(=≥)b2…………am1x1+am2x2+am3x3+…+amnxn≤(=≥)bn非负性约束：x1≥0,x2≥0,…,xn≥0第一章：线性规划及单纯形法解得：最大利润：27500X1=50X2=250代入得：设备台时：300原料A：350原料B：250概念：松弛变量剩余变量第一章：线性规划及单纯形法250KG10原料B400KG12原料A300台时11设备资源限制ⅡⅠ250KG10原料B400KG12原料A300台时11设备资源限制ⅡⅠ线性规划的标准型maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2………am1x1+am2x2+…+amnxn=bmxj≥0j=1,2,…,n第一章：线性规划及单纯形法标准型的四个标准：求最大值、约束条件为等式、bj≥0.xj≥0化非标准形线性规划为标准形式minz=x1+2x2+3x3-2x1+x2+x3≤9-3x1+x2+2x3≥4004x1-2x2-3x3=-6x1≤0,x2≥0,x3取值无约束第一章：线性规划及单纯形法练习：将下面线性规划问题化为标准形式minz=2x1-2x2+3x3-x1+x2+x3=4-2x1+x2-x3≤6x1≤0,x2≥0,x3取值无约束第一章：线性规划及单纯形法第一章：线性规划及单纯形法线性规划问题及其数学模型线性规划图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论4002001001002003004003000x1x2第一章：线性规划及单纯形法2x1+x2=400x2=250x1+x2=300目标函数：maxz=50x1+100x2约束条件：x1+x2≤3002x1+x2≤400x2≤250非负约束：x1≥0，x2≥04002001001002003004003000x1x22x1+x2=400x2=250x1+x2=300第一章：线性规划及单纯形法可行域目标函数：maxz=50x1+100x2约束条件：x1+x2≤3002x1+x2≤400x2≤250非负约束：x1≥0，x2≥04002001001002003004003000x1x22x1+x2=400x2=250x1+x2=300Z=0=50x1+100x2Z=1000=50x1+100x2Z=20000=50x1+100x2Z=27500=50x1+100x2第一章：线性规划及单纯形法等值线目标函数：maxz=50x1+100x2约束条件：x1+x2≤3002x1+x2≤400x2≤250非负约束：x1≥0，x2≥0线性规划问题解的几种情况线性规划存在唯一最优解线性规划存在有无穷多个最优解的情况线性规划可能存在无界解线性规划存在无可行解的情况第一章：线性规划及单纯形法练习：P43：1.1（1）（2）第一章：线性规划及单纯形法第一章：线性规划及单纯形法线性规划问题及其数学模型线性规划图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论基本概念：可行解最优解基基解基可行解可行基第一章：线性规划及单纯形法解的几何意义例:线性规划问题基本可行解的意义：2152maxxxZ0,02224..21212121xxxxxxxxts2152maxxxZ0,,,,2224..54321521421321xxxxxxxxxxxxxxts第一章：线性规划及单纯形法解的几何意义100110102100111A01112101101102111121BB00110101111102101143BB10101100110100101165BB第一章：线性规划及单纯形法解的几何意义100110102100111A10100201100110201187BB100010001101012001109BB),(),,(),,(),,(),,(),,(),,(),,(),,(),,(21314151324252435354xxxxxxxxxxxxxxxxxxxx第一章：线性规划及单纯形法解的几何意义100110102100111A,00,00,00,00,00,00324252435354xxxxxxxxxxxx00,00,00314151xxxxxx0021xx40602,04202,20022,03013,0064654321XXXXX第一章：线性规划及单纯形法解的几何意义100110102100111A,00,00,00,00,00,00324252435354xxxxxxxxxxxx00,00,00314151xxxxxx0021xx22400,68040,30310,06620,26004109876XXXXX第一章：线性规划及单纯形法解的几何意义212minxxZ0,0302..21121xxxxxts432002maxxxxxZ0,,,302432141321xxxxxxxxx10010121A110101110121321BBB001210011002654BBB第一章：线性规划及单纯形法解的几何意义10010121A110101110121321BBB001210011002654BBB3000,3000,3000,0303,0023354321XXXXX第一章：线性规划及单纯形法算法思路求一个初始基本可行解是判断基本可行解是否最优结束不是求使目标得到改善的基本可行解是否存在？如何得到？是否唯一？如何判断？如何改善？如何判断没有有限最优解？第一章：线性规划及单纯形法基本定理定理1若线性规划问题存在可行解，则该问题的可行解集（即可行域）是凸集。定理2线性规划问题的基可行解x对应线性规划问题可行域(凸集)的顶点定理3若线性规划问题有最优解，一定存在一个基可行解（可行域顶点）是最优解，如果在几个顶点上都出现最优解，则这些顶点的每个凸组合上也达到最优。第一章：线性规划及单纯形法凸集的概念1、基本概念：凸集——设K是n维欧氏空间的一个点集，若任意两点X（1）∈K，X（2）∈K的连线上的一切点：αX（1）+（1-α）X（2）∈K（0α1），则称K为凸集。第一章：线性规划及单纯形法凸集的概念凸组合——设X（1），X（2），…，X（k）是n维欧氏空间中的K个点，若存在k个数μ1，μ2，…，μk,满足0≤μi≤1,i=1,2,…,k；则称X=μ1X（1）+μ2X（2）+…+μkX(k)为X（1）,，X（2），…，X（k）的凸组合。顶点——设K是凸集，XK；若K中不存在两个不同的点X（1）K，X（2）K使X=αX（1）+（1-α）X（2）（0α1）则称X为K的一个顶点（也称为极点或角点）。第一章：线性规划及单纯形法凸集的概念凸集凸集不是凸集顶点第一章：线性规划及单纯形法表格单纯形法1c…nc1nc…mncCBXBjcjxb1x…nx