第一章 线性规划及单纯形法1线性规划介绍 2线性规划数学模型 3线性规划标准形式 4线性规划的图解法 5线性规划基本概念 6单纯形法 7应用举例第一章1线性规划介绍历史悠久，理论成熟，应用广泛运筹学的最基本的方法之一，网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。第一章线性规划理论的发展：1939年前苏联康托洛维奇（KOHTOPOBUZ） 生产组织与计划中的 数学方法提出 “解乘数法”。1线性规划介绍列奥尼德康托罗维奇，前苏联人，由于在1939年创立 了享誉全球的线形规划要点，对资源最优分配理论做 出了贡献，而获得诺贝尔经济学奖。第一章美国科学院院士DANTZIG（丹齐克），1948年在 研究美国空军资源的优化配置时提出线性规划及其通用 解法 “单纯形法”。被称为线性规划之父。1线性规划介绍线性规划之父的Dantzig (丹齐克)。据说，一次上课，Dantzig迟到 了，仰头看去，黑板上留了几个几个题目，他就抄了一下，回家后埋头 苦做。几个星期之后，疲惫的去找老师说，这件事情真的对不起，作业 好像太难了，我所以现在才交，言下很是 惭愧。几天之后，他的老师 就把他召了过去，兴奋的告诉他说他太兴奋了。Dantzig很不解 , 后来 才知道原来黑板上的题目根本就不是什么家庭作业，而是老师说的本领 域的未解决的问题，他给出的那个解法也就是单纯形法。这个方法是上 个世纪前十位的算法。 第一章1线性规划介绍1960年，“最佳资源利用的经济计算” 康托洛维奇 和库伯曼斯(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 ）, 他发展了数理和动态经 济理论，将经济科学提高到新的水平。他的研究涉及经济学的全部领域 。于1970年获得诺贝尔经济学奖。 华西里列昂惕夫（WASSILY LEONTIEF） ，美国人，他发展了投 入产出方法，该方法在许多重要的经济问题中得到运用。曾获1973年诺 贝尔经济科学奖。 肯尼斯-J-阿罗（KENNETH J. ARROW）,美国人，因与约翰-希克 斯（JOHN R. HICKS）共同深入研究了经济均衡理论和福利理论获得 1972年诺贝尔经济学奖。 牟顿-米勒（MERTON M. MILLER）,1923-2000, 美国人,由于他在 金融经济学方面做出了开创性工作，于1990年获得诺贝尔经济奖。第一章1线性规划介绍线性规划研究的主要问题：有一定的人力、财力、资源条件下，如何合 理安排使用，效益最高? 某项任务确定后，如何安排人、财、物，使 之最省?第一章例1 美佳公司计划制造I，II两种家电产品。已知各 制造一件时分别占用的设备A、B的台时、调试时间及A、 B设备和调试工序每天可用于这两种家电的能力、各售出 一件时的获利情况如表Il所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大？项项目III每天可用能力设备设备 A（h） 设备设备 B（h） 调试调试 工序（h ）0 6 15 2 115 24 5利润润（元）212线性规划数学模型第一章例2 捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资。已知各月份所需仓库面积数列见下表。仓库租借费用随 合同期定，期限越长折扣越大，具体数字见下表。租借仓库的合 同每月初都可办理，每份台同具体现定租用面积数和期限。因此 该厂可根据需要，在任何一个月初办理租借台同。每次办理时可 签一份，也可签若干份租用面积和租借期限不同的合同，试确定 该公司签订租借合同的最优决策，目的是使所付租借费用最小。月份1234所需仓库仓库 面积积15102012合同租借期限1个月2个月3个月4个月合同期内的租费费28004500600073002线性规划数学模型第一章目标函数约束条件解：用变量x1和x2分别表示美佳公司制造家电I和II的数量。项项目III每天可用能力 设备设备 A（h） 设备设备 B（h） 调试调试 工序（h ）0 6 15 2 115 24 5利润润（元）21例1用数学语言描述2线性规划数学模型第一章解：设变量xij表示捷运公司在第i(i1，4)个月初签订的租 借期为jj1，4)个月的仓库面积的合同(单位为100m2)。约束条件目标函数例2月份1234 所需仓库仓库 面积积15102012合同租借期限1个月2个月3个月4个月合同期内的租 费费28004500600073002线性规划数学模型第一章A B 备用资源煤 1 2 30劳动日 3 2 60仓库 0 2 24利润 40 50求：最大利润的生产计划。练习1 生产计划问题2线性规划数学模型第一章max Z= 40x1 +50x2解:设产品A, B产量分别为变量x1 ， x2x1 + 2x2 30 3x1 + 2x2 602x2 24x1，x2 0s.t.2线性规划数学模型第一章求：最低成本的原料混合方案？原料 A B 每单位成本1 4 1 0 22 6 1 2 5 3 1 7 1 64 2 5 3 8每单位添加剂中维生 12 14 8 素最低含量练习2 混合配料问题2线性规划数学模型第一章解：设每单位添加剂中原料i的用量为xi(i =1,2,3,4)minZ= 2x1 + 5x2 +6x3+8x44x1 + 6x2 + x3+2x4 12x1 + x2 +7x3+5x4 142x2 + x3+3x4 8xi 0 (i =1,4)s.t.2线性规划数学模型第一章决策变量：向量(x1 xn)T 决策人要考虑和控制的因素。非负约束条件：线性等式或不等式目标函数：Z=(x1 xn) 线性式，求Z极大或极 小线性规划模型特点2线性规划数学模型第一章如果规划问题的数学模型中，决策变量的取值可以是连续的，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则该类规划问题的数学模型称为线性规划的数学模型。 实际问题中线性的含义：一是严格的比例性二是可叠加性关于线性的界定2线性规划数学模型第一章max(min)Z=c1x1+ c2x2+cnxnn个变量价值系 数第i 种资 源的拥有 量技术系数或 工艺系数a11x1+ a12x2+ a1nxn (=, )b1a21x1+ a22x2+ a2nxn (=, )b2 am1x1+ am2x2+ amnxn (=, )bmxj 0(j=1,n)s.t.线性规划的一般式2线性规划数学模型19第一章线性规划的简写式2线性规划数学模型第一章线性规划的向量表示式2线性规划数学模型第一章线性规划的矩阵表示式2线性规划数学模型第一章比例性：决策变量变化引起目标的改变量与 决策变量改变量成正比；可加性：每个决策变量对目标和约束的影响 独立于其它变量；连续性：每个决策变量取连续值；确定性：线性规划中的参数aij , bi , ci为确定值。隐含的假设2线性规划数学模型第一章仓库工厂 1 2 3 库存1 2 1 3 502 2 2 4 303 3 4 2 10需求 40 15 35练习3 运输问题工厂需要的原棉存放在三个仓库中，现将原棉运往工 厂以满足工厂生产的需求。已知原棉运到各个工厂的单位 运费如表所示。问使总运费最小的运输方案？2线性规划数学模型第一章解：设xij为i 仓库运到 j工厂的原棉数量(i =1,2,3 j =1,2,3)minZ= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33x11 +x12+x13 50x21+x22+x23 30x31+x32+x33 10x11 +x21+x31 = 40x12 +x22+x32 = 15x13 +x23+x33 = 35xij 0st.2线性规划数学模型第一章练习4 连续投资10万元 A：从第1年到第4年每年初投资，次年末回收本利1.15； B：第3年初投资，到第5年末回收本利1.25，最大投资4万元 ； C：第2年初投资，到第5年末回收本利1.40，最大投资3万元 ； D：每年初投资，每年末回收本利1.11。 求：使5年末总资本最大的投资方案。分析：1 2 3 4 5A x1A x2A x3A x4A B x3BC x2CD x1D x2D x3D x4D x5D 2线性规划数学模型第一章解：xik( i =1,2,5; k =A,B,C,D)为第i年初投资到第k个项目的资金数。MaxZ= 1.15x4A +1.40 x2C+1.25x3B+1.11x5Dx1A+x1D=10 x2A+x2C+x2D= 1.11 x1D x2C 3 x3A +x3B+x3D =1.15 x1A+ 1.11 x2D x3B 4 x4A +x4D =1.15 x2A+ 1.11 x3D x5D =1.15 x3A+ 1.11 x4Dxik 0s.t.2线性规划数学模型第一章线性规划问题应用市场营销(广告预算和媒介选择，竞争性定价，新产品 开发，制定销售计划) 生产计划制定(合理下料，配料，“生产计划、库存、 劳力综合”) 库存管理(合理物资库存量，停车场大小，设备容量)运输问题 财政、会计(预算，贷款，成本分析，投资，证券管理 ) 人事(人员分配，人才评价，工资和奖金的确定) 设备管理(维修计划，设备更新) 城市管理(供水，污水管理，服务系统设计、运用)2线性规