大工16春《运筹学》辅导资料五1460941106734.doc

大连理工大学网络教育学院运筹学辅导资料五主 题：第一章第二节“线性规划基本概念及模型”辅导资料学习时间：2016年4月25日5月1日内 容：我们这周主要学习第二章，第二节“线性规划基本概念及模型”的相关内容。希望通过下面的内容能使同学们加深对线性规划基本概念及模型相关知识的理解。一、学习要求1掌握线性规划的概念；2掌握线性规划的四条基本假设；3了解线性规划的数学模型；4了解线性规划的发展；二、主要概念及典型习题解析1线性规划（Linear Programming，LP）的概念：针对数学规划，若决策变量为可控的连续变量，且目标函数和约束函数都是线性的，则称此类数学规划问题为线性规划问题。 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.规划问题。一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素。2. 线性规划的四条基本假设 比例性：要求每个决策变量在目标函数和约束函数中，其贡献与决策变量的值存在直接比例性。 连续性：指所有的决策变量取值为连续的数。 确定性：指线性规划中所有目标函数和约束函数中的系数都是确定的常数，不含随机因素。 可加性：指所有决策变量对目标函数和约束函数的贡献是相互独立的（包括正向贡献和负向贡献），目标函数值等于每个决策变量各自对目标函数贡献的总和。 3. 线性规划的数学模型（1）列出约束条件及目标函数（2）画出约束条件所表示的可行域（3）在可行域内求目标函数的最优解及最优值4. 线性规划的发展法国数学家J.- B.- J.傅里叶和C.瓦莱普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年苏联数学家.康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视。1947年美国数学家G.B.Dantzing提出求解线性规划的单纯形法，为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。1979年苏联数学家L. G. Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。5.整数规划整数变量：决策变量是整数，如电视产量，人的数量。 整数规划问题（Integer Programming，IP）：全部或者某些决策变量是整数变量的数学规划问题。 整数变量的分类: 一般离散型整数变量，即取值为多个离散整数的变量，如产品个数等。 0-1变量，即取值为0或者1的变量，如表示某一经济、管理活动是否执行等。6.目标规划和非线性规划目标规划（Goal Programming，GP）概念：解决多目标决策的定量分析的数学规划方法 。 非线性规划（Nonlinear Programming，NLP）概念：若某一数学规划问题的目标函数和约束函数中至少有一个是非线性的，则称此类数学规划为非线性规划。 三、典型习题（一）选择题1. 线性规划问题中决策变量应为（ ）。A.连续变量 B.离散变量 C.整数变量 D.随机变量答案：A2.线性规划的四条基本假设不包括（ ）。A.比例性 B.连续性 C.确定性 D.发散性答案：D3. 线性规划四条基本假设中的（ ）是指所有决策变量对目标函数和约束函数的贡献是相互独立的，目标函数值等于每个决策变量各自对目标函数贡献的总和。A.比例性 B.连续性 C.确定性 D. 可加性答案：D4.全部或者某些决策变量是整数变量的数学规划问题称为（ ）。A. 线性规划问题 B. 非线性规划问题C. 目标规划问题 D. 整数规划问题答案：D5.（ ）是解决多目标决策的定量分析的数学规划方法。A. 线性规划 B. 非线性规划 C. 目标规划 D. 整数规划答案：C（二）判断题1.目标函数和约束函数都是非线性的数学规划问题称为线性规划问题。答案：错2. 线性规划基本假设中的可加性是指线性规划中所有目标函数和约束函数中的