基于excel的线性规划.pptx

基于Excel的线性规划建模线性规划简介线性规划（Linear programming,简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。线性规划发展史1947年美国数学家G.B.Dantzing提出求解线性规划的单纯形法，为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于计算机的发展，出现了许多线性规划软件，可以很方便地求解几千个变量的线性规划问题。1979年苏联数学家L. G. Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。 建立线性规划模型的方法线性规划的基本概念和数学模型例1.1 生产计划问题。某工厂要生产两种新产品：门和窗。经测算，每生产一扇门需要在车间1加工1小时、在车间3加工3小时；每生产一扇窗需要在车间2和车间3各加工2小时。而车间1、车间2、车间3每周可用于生产这两种新产品的时间分别是4小时、12小时、18小时。已知每扇门的利润为300元，每扇窗的利润为500元。而且根据经市场调查得到的这两种新产品的市场需求状况可以确定，按当前的定价可确保所有新产品均能销售出去。问该工厂应如何安排这两种新产品的生产计划，才能使总利润最大？在该问题中，目标是两种新产品的总利润最大化，所要决策的（变量）是两种新产品（门和窗）的每周产量，而新产品的每周产量要受到三个车间每周可用于生产新产品的时间的限制。因此，该问题可以用“目标函数”、“决策变量”和“约束条件”三个因素加以描述。实际上，所有的线性规划问题都包含这三个因素：（1）决策变量是问题中有待确定的未知因素。例如决定企业经营目标的各产品的产量等。（2）目标函数是指对问题所追求目标的数学描述。例如总利润最大、总成本最小等。（3）约束条件是指实现问题目标的限制因素。如原材料供应量、生产能力、市场需求等，它们限制了目标值所能实现的程度。解：例1.1可用下表表示。每个产品所需时间每周可用工时（小时）门窗车间1104车间20212车间33218单位利润（元）300500（1）决策变量本问题的决策变量是两种新产品（门和窗）的每周产量。可设：x1为门的每周产量（扇）； x2为窗的每周产量（扇）。（2）目标函数本问题的目标是两种新产品的总利润最大。由于门和窗的单位利润分别为300元和500元，而其每周产量分别为x1和x2 ，所以每周总利润z可表示为： z = 300x1＋500x2 （元）（3）约束条件本问题的约束条件共有四个。车间1每周可用工时限制：x1 ? 4车间2每周可用工时限制：2x2 ? 12车间3每周可用工时限制：3x1 +2x2 ? 18非负约束： x1 ? 0, x2 ? 0例1.1的线性规划（数学）模型为:这是一个典型的总利润最大化的生产计划问题。其中，“max”是英文单词“maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，意思是“受约束于……”。因此，上述模型的含义是：在给定的条件限制（约束）下，求目标函数 z 达到最大时x1，x2 的取值。 所谓“线性”规划，是指如果目标函数是关于决策变量的线性函数，而且约束条件也都是关于决策变量的线性等式或线性不等式，则相应的规划问题就称为线性规划问题。在线性规划模型中，也直接称z为目标函数；称xj(j=1,2,?,n)为决策变量；称cj(j=1,2,?,n) 为目标函数系数、价值系数或费用系数；称bi(i=1,2,?,m)为函数约束右端常数或简称右端值，也称资源常数；称aij(i=1,2,?,m;j=1,2,?,n)为约束系数、技术系数或工艺系数。这里，cj，bi，ai