基于excel的线性规划PPT学习课件.ppt

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