《线性规划及单纯形法(运筹学的知识)》由会员分享，可在线阅读，更多相关《线性规划及单纯形法(运筹学的知识)（140页珍藏版）》请在金锄头文库上搜索。
1、第一章 线性规划及单纯形法,1线性规划介绍 2线性规划数学模型 3线性规划标准形式 4线性规划的图解法 5线性规划基本概念 6单纯形法 7应用举例,1线性规划介绍,历史悠久，理论成熟，应用广泛 运筹学的最基本的方法之一，网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。 解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。,线性规划理论的发展： 1939年前苏联康托洛维奇（KOHTOPOBUZ） 生产组织与计划中的 数学方法提出 “解乘数法”。,1线性规划介绍,美国科学院院士DANTZIG（丹齐克），1948年在研究美国空军资源的优化配置时提出线性规划及其通用解法
2、“单纯形法”。被称为线性规划之父。,1线性规划介绍,线性规划之父的Dantzig (丹齐克)。据说，一次上课，Dantzig迟到 了，仰头看去，黑板上留了几个几个题目，他就抄了一下，回家后埋头苦做。几个星期之后，疲惫的去找老师说，这件事情真的对不起，作业好像太难了，我所以现在才交，言下很是 惭愧。几天之后，他的老师就把他召了过去，兴奋的告诉他说他太兴奋了。Dantzig很不解 , 后来才知道原来黑板上的题目根本就不是什么家庭作业，而是老师说的本领域的未解决的问题，他给出的那个解法也就是单纯形法。这个方法是上个世纪前十位的算法。,1线性规划介绍,1960年，“最佳资源利用的经济计算” 康托洛维奇
3、和库伯曼斯(Koopmans) 。两人因对资源最优分配理论的贡献而获1975年诺贝尔经济学奖,1961年，查恩斯与库伯提出了目标规划，艾吉利提出了用优先因子来处理多目标问题。 20世纪70年代，斯姆李与杰斯开莱尼应用计算机处理目标规划问题。 计算机 50约束 100变量 30000约束 3000000变量,1线性规划介绍,从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中著名的有Simon，Samullson，Leontief，Arrow，Miller等。,1线性规划介绍,保罗-萨缪尔逊（PAUL A SAMUELSON
4、 ）, 他发展了数理和动态经济理论，将经济科学提高到新的水平。他的研究涉及经济学的全部领域。于1970年获得诺贝尔经济学奖。 华西里列昂惕夫（WASSILY LEONTIEF） ，美国人，他发展了投入产出方法，该方法在许多重要的经济问题中得到运用。曾获1973年诺贝尔经济科学奖。 肯尼斯-J-阿罗（KENNETH J. ARROW）,美国人，因与约翰-希克斯（JOHN R. HICKS）共同深入研究了经济均衡理论和福利理论获得1972年诺贝尔经济学奖。 牟顿-米勒（MERTON M. MILLER）,1923-2000, 美国人,由于他在金融经济学方面做出了开创性工作，于1990年获得诺贝尔经
5、济奖。,1线性规划介绍,线性规划研究的主要问题： 有一定的人力、财力、资源条件下，如何合理安排使用，效益最高? 某项任务确定后，如何安排人、财、物，使之最省?,例1 美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表Il所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大？,2线性规划数学模型,例2 捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资。已知各月份所需仓库面积数列见下表。仓库租借费用随合同期定，期限越长折扣越大，具体数字见下表。租借仓库的合同每月初
6、都可办理，每份台同具体现定租用面积数和期限。因此该厂可根据需要，在任何一个月初办理租借台同。每次办理时可签一份，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。,2线性规划数学模型,目标函数,约束条件,解：用变量x1和x2分别表示美佳公司制造家电I和II的数量。,例1,用数学语言描述,2线性规划数学模型,解：设变量xij表示捷运公司在第i(i1，4)个月初签订的租借期为jj1，4)个月的仓库面积的合同(单位为100m2)。,约束条件,目标函数,例2,2线性规划数学模型,求：最大利润的生产计划。,练习1 生产计划问题,2线性规划数学模型,m
7、ax Z= 40x1 +50x2,解:设产品A, B产量分别为变量x1 ， x2,2线性规划数学模型,求：最低成本的原料混合方案？,练习2 混合配料问题,2线性规划数学模型,解：设每单位添加剂中原料i的用量为xi(i =1,2,3,4),minZ= 2x1 + 5x2 +6x3+8x4,2线性规划数学模型,决策变量：向量(x1 xn)T 决策人要考虑和控制的因素。非负 约束条件：线性等式或不等式 目标函数：Z=(x1 xn) 线性式，求Z极大或极小,线性规划模型特点,2线性规划数学模型,如果规划问题的数学模型中，决策变量的取值可以是连续的，目标函数是决策变量的线性函数，约束条件是含决策变量的线
8、性等式或不等式，则该类规划问题的数学模型称为线性规划的数学模型。 实际问题中线性的含义： 一是严格的比例性 二是可叠加性,关于线性的界定,2线性规划数学模型,19,max(min)Z=c1x1+ c2x2+cnxn,n个变量,价值系数,第i 种资源的拥有量,技术系数或工艺系数,线性规划的一般式,2线性规划数学模型,线性规划的简写式,2线性规划数学模型,线性规划的向量表示式,2线性规划数学模型,线性规划的矩阵表示式,2线性规划数学模型,比例性：决策变量变化引起目标的改变量与决策变量改变量成正比； 可加性：每个决策变量对目标和约束的影响独立于其它变量； 连续性：每个决策变量取连续值； 确定性：线性
9、规划中的参数aij , bi , ci为确定值。,隐含的假设,2线性规划数学模型,练习3 运输问题 工厂需要的原棉存放在三个仓库中，现将原棉运往工厂以满足工厂生产的需求。已知原棉运到各个工厂的单位运费如表所示。问使总运费最小的运输方案？,2线性规划数学模型,解：设xij为i 仓库运到 j工厂的原棉数量(i =1,2,3 j =1,2,3),minZ= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33,2线性规划数学模型,练习4 连续投资10万元 A：从第1年到第4年每年初投资，次年末回收本利1.15； B：第3年初投资，到第5年末回收本利1.
10、25，最大投资4万元； C：第2年初投资，到第5年末回收本利1.40，最大投资3万元； D：每年初投资，每年末回收本利1.11。 求：使5年末总资本最大的投资方案。,分析：,2线性规划数学模型,解：xik( i =1,2,5; k =A,B,C,D)为第i年初投资到第k个项目的资金数。,MaxZ= 1.15x4A +1.40 x2C+1.25x3B+1.11x5D,2线性规划数学模型,线性规划问题应用 市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划) 生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”) 库存管理(合理物资库存量，停车场大小，设备容量) 运输问题 财
11、政、会计(预算，贷款，成本分析，投资，证券管理) 人事(人员分配，人才评价，工资和奖金的确定) 设备管理(维修计划，设备更新) 城市管理(供水，污水管理，服务系统设计、运用),2线性规划数学模型,线性规划的适用情况 要解决的问题的目标可以用数值指标反映 对于要实现的目标有多种方案可选择 有影响决策的若干约束条件,2线性规划数学模型,线性规划模型的结构 目标函数 ：max，min 约束条件：,=, 变量符号：0, 0,线性规划的标准形式 目标函数：max 约束条件 ：= 变量符号 ：0,3线性规划标准形式,标准型的一般型,maxZ=c1x1+ c2x2+cnxn,其中 bi 0 (i=1,2,m
12、),3线性规划标准形式,C=(C1 C2 Cn ),标准型的矩阵型,3线性规划标准形式,P1 x1+ P2 x2 + +Pn xn=b,标准型的向量型,3线性规划标准形式,线性规划问题化标准型：,(1)、约束条件 (2)、变量 (3)、目标函数 (4)、右端常数,3线性规划标准形式,(1)、约束条件,x3为松弛变量,x4为剩余变量,松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。,当约束条件为“ ”时：,当约束条件为“ ”时：,3线性规划标准形式,3线性规划标准形式,转化为：maxZ=40X1+ 50X2
13、+0X3 +0X4+0X5,例：max Z= 40x1 +50x2,松弛变量,3线性规划标准形式,例：,剩余变量,(2)、变量,1、x 0的情况，,令x1= x1- x1 “,2、x取值无约束的情况。,令x- x。,令x= x- x“,3线性规划标准形式,（3）、x两边有约束的情况。,-6+6 x1+6 10+6 令x1 = x1 +6 0 x1 16,3线性规划标准形式,(3)、目标函数,令Z = - Z,3线性规划标准形式,(4)、右端常数,右端项b0时，只需将等式或不等式两端同乘(一1)，则等式右端项必大于零。,3线性规划标准形式,例3：将 min Z = -x1+2x2 -3x3,化为
14、标准型,3线性规划标准形式,解： 令x3 =x4 - x5, 加松弛变量x6,加剩余变量x7, 令Z= -Z,maxZ= x1 -2x2 +3x4 -3x5,3线性规划标准形式,(1) min Z= 2x1 -x2+2x3,练习5 将下列线性规划问题化成标准型：,(2) max Z= 2x1 +x2+3x3 +x4,3线性规划标准形式,(3) min Z= 2x1 +3x2+5x3,(4) max Z= x1 -3x2,3线性规划标准形式,作业: 课本P44 12,3线性规划标准形式,定义1：满足约束(1)、(2)的x=(x1 xn)T称为LP问题的可行解，全部可行解的集合称为可行域。,定义2
15、：满足(3)的可行解称为LP问题的最优解,线性规划的标准型,4线性规划的图解法,图解法求解的目的： 一是判别线性规划问题的求解结局； 二是在存在最优解的条件下，把问题的最优解找出来。,4线性规划的图解法,图解法的步骤： 1、在平面上建立直角坐标系； 2、图示约束条件，找出可行域； 3、图示目标函数和寻找最优解。,4线性规划的图解法,例4 maxZ=40x1+ 50x2,4线性规划的图解法,解：(1)、确定可行域 x1 0 x1 =0 (纵) x2 0 x2=0 (横),x1+2x2 30 x1+2x2 =30 (0,15) (30,0),3x1+2x2 =60 (0,30) (20,0),2x2 =24,4线性规划的图解法,(2)、求最优解,最优解：x* = (15,7.5) Zmax =975,Z=40x1+50x2 0=40x1+50x2 (0,0)， (10,-8),4线性规划的图解法,解: 最优解：BC线段 B点 C点 x(1)=(6,12) x(2)=(15,7.5) x= x(1)+(1-) x(2) (0 1),4线性规划的图解法,4线性规划的图解法,无界解 无有限最优解,4线性规划的图解法,无解 无可行解,4线性规划的图解法,当目标函数的直线族与某约束条件平行，且该问题有解时。,约束条件无公共区域。,有解但可行域可伸展到无穷时,总 结,4
