线性规划数学模型课件学习教案.ppt

《线性规划数学模型课件学习教案.ppt》由会员分享，可在线阅读，更多相关《线性规划数学模型课件学习教案.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 冯诺伊曼(Von Neuman)和摩根斯坦(Morgenstern)1944年发表的 博弈论与经济(jngj)行为涉及与线性规划等价的对策问题及线性规划对偶理论 从1964年诺贝尔奖设经济(jngj)学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中比较著名的还有Simon，Samullson，Leontief，Arrow，Miller等第1页/共29页第一页，共30页。2研究(ynji)对象 有一定的人力、财力、资源条件下，如何合理安排使用，效益最高 某项任务(rn wu)确定后，如何安排人、财、物，使之最省第2页/共29页第二页，共30页

2、。3线性规划(xin xn u hu)模型 是通过对实际问题的分析而建立的表示决策( juc)变量、最优目标和约束条件之间关系的一组数学关系式，由决策( juc)变量、目标函数和约束条件三部分组成。 在满足一组约束条件下，求一组决策( juc)变量的值，使目标函数达到最优。第3页/共29页第三页，共30页。4线性规划(xin xn u hu)的特点v 决策变量连续性：求解出的决策变量值可以是整数、小数；v 线性函数：目标函数方程和约束条件方程都是线性方程；v 单目标：目标函数是单目标，只有(zhyu)一个极大值或一个极小值；v 确定性：只能应用于确定型决策问题。第4页/共29页第四页，共30页

3、。5 A B 备用资源 煤 1 2 30 劳动日 3 2 60 仓库 0 2 24 利润 40 50例1、生产(shngchn)计划问题A, B各生产(shngchn)多少, 可获最大利润?第5页/共29页第五页，共30页。6 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0 max Z= 40 x1 +50 x2解:设产品A, B产量(chnling)分别为变量x1 ， x2第6页/共29页第六页，共30页。7例2求：最低成本(chngbn)的原料混合方案 原料 A B 每单位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8

4、每单位添 加剂中维生 12 14 8 素最低含量第7页/共29页第七页，共30页。8解：设每单位(dnwi)添加剂中原料i的用量为xi(i =1,2,3,4)minZ= 2x1 + 5x2 +6x3+8x4 4x1 + 6x2 + x3+2x4 12 x1 + x2 +7x3+5x4 14 2x2 + x3+3x4 8 xi 0 (i =1,4)第8页/共29页第八页，共30页。9一般(ybn)式Max(min)Z=C1X1+ C2X2+CnXna11X1+ a12X2+ a1nXn (=, )b1a21X1+ a22X2+ a2nXn (=, )b2 am1X1+ am2X2+ amnXn

5、(=, )bmXj 0(j=1,n)第9页/共29页第九页，共30页。10 要解决的问题的目标可以用数值指标(zhbio)反映 对于要实现的目标有多种方案可选择 有影响决策的若干约束条件第10页/共29页第十页，共30页。11 图解法AX=b (1)X 0 (2)maxZ=CX (3)定义1：满足(mnz)约束(1)、(2)的X=(X1 Xn)T称为LP问题的可行解，全部可行解的集合称为可行域。定义2：满足(mnz)(3)的可行解称为LP问题的最优解第11页/共29页第十一页，共30页。12例1、maxZ=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X

6、2 0第12页/共29页第十二页，共30页。13解：(1)、确定(qudng)可行域 X1 0 X1 =0 (纵) X2 0 X2=0 (横) X1+2X2 30 X1+2X2 =30 (0,15) (30,0)2030100102030X2DABC3X1+2X2 =60(0,30) (20,0) 2X2 =24第13页/共29页第十三页，共30页。14(2)、求最优解解：X* = (15,7.5) Zmax =975Z=40X1+50X20=40X1+50X2 (0,0)， (10,-8)C点： X1+2X2 =30 3X1+2X2 =600203010102030X1X2DABC第14页/

7、共29页第十四页，共30页。15例2、 maxZ=40X1+ 80X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0第15页/共29页第十五页，共30页。160Z= 40 X1 + 80X2 =0 X1 + 2X2 =30DABCX2X1最优解：BC线段(xindun)B点 C点X(1)=(6,12) X(2)=(15,7.5)X= X(1)+(1-) X(2) (0 1)求解(qi ji)第16页/共29页第十六页，共30页。17X1 =6+ +(1- )15X2=12+ +(1- )7.5X1 =15-9X2 =7.5+4.5 (0 1)X= = +(1- )m

8、axZ=1200 X1 6 15 X2 12 7.5第17页/共29页第十七页，共30页。18无界无有限(yuxin)最优解例3、 maxZ=2X1+ 4X2 2X1+X2 8-2X1+X2 2X1 , X2 0Z=02X1+ X2=8-2X1+ X2=28246X240X1第18页/共29页第十八页，共30页。19例4、 maxZ=3X1+2X2 -X1 -X2 1X1 , X2 0无解无可行(kxng)解-1X2-1X10第19页/共29页第十九页，共30页。20总结(zngji) 唯一解 无穷多解 无有限最优解 无可行解有解无解第20页/共29页第二十页，共30页。21单纯形法 单纯形法

9、（Simplex Method）是美国数学家但泽（Dantzig）于1947年提出的。基本思想(sxing)是通过有限次的换基迭代来求出线性规划的最优解。第21页/共29页第二十一页，共30页。22两个(lin )变量的LP问题的解： 可行(kxng)域为凸多边形（凸集）X(1)X(2)凸多边形凹多边形X(1)X(2)第22页/共29页第二十二页，共30页。23顶点(dngdin)原理v顶点（极点）v 凸集中满足一下条件的点：凸集中通过任意两个(lin )点的直线上都不包含此点作为内点，它只能是凸集的端点。v顶点原理v 由于线性规划问题的可行域都是凸集，如果存在最优解，必然对应于可行域凸集的至

10、少一个顶点；如果只有一个最优解，它必然对应于一个顶点；如果存在多个最优解，它们必然相邻。第23页/共29页第二十三页，共30页。24顶点原理(yunl)的运用 顶点(dngdin)原理证明，如果线性规划的最优解存在，要找到最优解，只要找到可行域凸集顶点(dngdin)的坐标，将其代入目标函数，使得目标函数值最大的点就是最优解。 考察例1的情形。第24页/共29页第二十四页，共30页。25 单纯形法的指导思想是，不需要考察和计算所有顶点，如存在最优解，可以任意顶点为起点(qdin)，求出初始解，然后转到相邻顶点，看目标函数值是否有改善。 利用单纯形法解决线性规划问题，实际上是从线性规划问题的一个

11、基本可行解转移到另一个基本可行解，同时目标函数值不减少的过程。 对于两个变量的线性规划问题，就是从可行域的一个端点转移到另一个端点，而使得目标函数的值不减少。第25页/共29页第二十五页，共30页。26线性规划(xin xn u hu)的扩展一、整数规划（整数线性规划(xin xn u hu)）：部分或全部的决策变量只能取整数值。例1转变成整数规划情形第26页/共29页第二十六页，共30页。27二、01规划： 变量的取值被限定为0或1，可以看成是整数规划的扩展。 例2：某市拟建设若干公共图书馆，经过调研得到相关数据如下表。现财政预算不超过2亿元，人员编制不超过160人。在财政预算与人员编制约束

12、下，要达到最大的服务读者数量(shling)，应该如何建设 ？第27页/共29页第二十七页，共30页。28 A地点B地点C地点D地点E地点资金耗费（万元）40003500500060005500需要工作人员（个）3020504035服务读者数量（百人）150100200300280第28页/共29页第二十八页，共30页。29感谢您的观看(gunkn)！第29页/共29页第二十九页，共30页。NoImage内容(nirng)总结1。决策变量(binling)连续性：求解出的决策变量(binling)值可以是整数、小数。线性函数：目标函数方程和约束条件方程都是线性方程。解：设每单位添加剂中原料i的用量为xi(i =1,2,3,4)。Max(min)Z=C1X1+ C2X2+。am1X1+ am2X2+。解：X* = (15,7.5)。单纯形法（Simplex Method）是美国数学家但泽（Dantzig）于1947年提出的。如果只有一个最优解，它必然对应于一个顶点第三十页，共30页。