管理运筹：第2章线性规划的图解法.ppt

《管理运筹：第2章线性规划的图解法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、多媒体教学课件(02)南京财经大学工商管理学院李时椿管理运筹学1第二章线性规划图解法线性规划数学模型线性规划图解法线性规划数学模型标准型2线性规划（LinearProgramming,LP）线性规划是研究线性约束条件下线性目标函数的极值问题的数学理论与方法。即对于统筹规划问题，为如何合理地、有效地利用现有有限的人力、物力、财力资源来完成更多的任务，或者如何才能以最少的代价去实现目标，作出的最优决策，提供科学的依据。有关线性规划问题的建模、求解和应用研究构成了运筹学中一个重要的、应用最为广泛的分支。其典

2、型问题有：运输问题、生产计划问题、下料问题、混合配料问题等。31939年苏联数学家康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题﹐并未引起重视。1947年美国数学家丹捷格﹐G.B.提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法﹐为这门学科奠定了基础。1947年美国数学家诺伊曼﹐J.von提出对偶理论﹐开创了线性规划的许多新的研究领域﹐扩大了它的应用范围和解题能力。线性规划的发展41951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域﹐为此与康托罗维奇一起获

3、1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究﹐并涌现出一大批新的算法。例如﹐1954年C.莱姆基提出对偶单纯形法﹐1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题﹐1956年A.塔克提出互补松弛定理﹐1960年丹捷格﹐G.B.和P.沃尔夫提出分解算法等。线性规划的发展5线性规划的研究成果还直接推动了其它数学规划问题包括整数规划﹑随机规划和非线性规划的算法研究。由于数字电子计算器的发展﹐出现了许多线性规划软件﹐如MPSX﹐OPHEIE﹐UMPIRE等﹐可以很方

4、便地求解几千个变量的线性规划问题。线性规划的发展大型电子计算器的出现对线性规划的理论以及应用的发展起着决定性的作用，在经济领域中广泛地应用线性规划方法﹐利用电子计算机目前已能解决变量多达数百万之多的具有特殊结构的大型线性规划问题。6第二章线性规划的图解法§1问题的提出§2图解法§3图解法的灵敏度分析7第二章线性规划的图解法在管理中一些典型的线性规划应用合理利用线材问题：如何在保证生产的条件下，下料最少配料问题：在原料供应量的限制下如何获取最大利润投资问题：从投资项目中选取方案，使投资回报最大产品生产计

5、划：合理利用人力、物力、财力等，使获利最大劳动力安排：用最少的劳动力来满足工作的需要运输问题：如何制定调运方案，使总运费最小线性规划的组成：目标函数MaxF或MinF约束条件s.t.(subjectto)满足于决策变量用符号来表示可控制的因素8§1问题的提出例1.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？线性规划模型：目标函数：Maxz=50x1+100x2约束条件：

6、s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥09§1问题的提出建模过程1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，…，xn），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件一般形式目标函数：Max（Min）z=c1x1+c2x2+…+cnxn约束条件：s.t.a11x1+a12x2+…+a1nxn≤（=,≥）b1a21x1+a22x2+…

7、+a2nxn≤（=,≥）b2…………am1x1+am2x2+…+amnxn≤（=,≥）bmx1，x2，…，xn≥010例1.目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：x1=50，x2=250最优目标值z=27500§2图解法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：11§2图解法(1)分别取决策变

8、量X1,X2为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X2≥0X2=0x2x1X1≥0X1=012§2图解法（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=40030020030040013§2图解法（3）