1第二章线性规划及单纯形法解释.ppt

第二章 线性规划及单纯形法;1．线性规划介绍;线性规划理论的发展： 1939年前苏联康托洛维奇（KOHTOPOBUZ） 《生产组织与计划中的 数学方法》提出 “解乘数法”。;美国科学院院士DANTZIG（丹齐克），1948年在研究美国空军资源的优化配置时提出线性规划及其通用解法 “单纯形法”。被称为线性规划之父。;1．线性规划介绍;1961年，查恩斯与库伯提出了目标规划，艾吉利提出了用优先因子来处理多目标问题。 20世纪70年代，斯．姆．李与杰斯开莱尼应用计算机处理目标规划问题。 计算机 50约束 100变量 30000约束 3000000变量;从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中著名的有Simon，Samullson，Leontief，Arrow，Miller等。;1．线性规划介绍; 例1 美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表I—l所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大？;例2 捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资。已知各月份所需仓库面积数列见下表。仓库租借费用随合同期定，期限越长折扣越大，具体数字见下表。租借仓库的合同每月初都可办理，每份台同具体现定租用面积数和期限。因此该厂可根据需要，在任何一个月初办理租借台同。每次办理时可签一份，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。;目标函数;解：设变量xij表示捷运公司在第i(i＝1．…，4)个月初签订的租借期为j〔j＝1，…，4)个月的仓库面积的合同(单位为100m2)。; A B 备用资源 煤 1 2 30 劳动日 3 2 60 仓库 0 2 24 利润 40 50 ;max Z= 40x1 +50x2;求：最低成本的原料混合方案？;解：设每单位添加剂中原料i的用量为xi(i =1,2,3,4);决策变量：向量(x1… xn)T 决??人要考虑和控制的因素。非负 约束条件：线性等式或不等式 目标函数：Z=?(x1 … xn) 线性式，求Z极大或极小;如果规划问题的数学模型中，决策变量的取值可以是连续的，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则该类规划问题的数学模型称为线性规划的数学模型。 实际问题中线性的含义： 一是严格的比例性。如生产某产品对资源的消耗量和可获取的利润，同其生产数量严格成比例。 二是可叠加性。如生产多种产品时对某项资源的消耗量应等于各产品对该项资源的消耗量之和。;*;线性规划的简写式;;线性规划的矩阵表示式;比例性：决策变量变化引起目标的改变量与决策变量改变量成正比； 可加性：每个决策变量对目标和约束的影响独立于其它变量； 连续性：每个决策变量取连续值； 确定性：线性规划中的参数aij , bi , ci为确定值。;仓库\工厂 1 2 3 库存 1 2 1 3 50 2 2 2 4 30 3 3 4 2 10 需求 40 15 35;解：设xij为i 仓库运到 j工厂的原棉数量(i =1,2,3 j =1,2,3);练习4 连续投资10万元 A：从第1年到第4年每年初投资，次年末回收本利1.15； B：第3年初投资，到第5年末回收本利1.25，最大投资4万元； C：第2年初投资，到第5年末回收本利1.40，最大投资3万元； D：每年初投资，每年末回收本利1.11。 求：使5年末总资本最大的投资方案。;解：xi