第1章线性规划

第 1章 线性规划1.1 原始问题1.2 对偶问题1.3 敏感分析1.4 模型讨论 数学规划（ mathematical programming）是运筹学的一个主要分支，它是研究在一些给定的条件下（即约束条件下），求的考察函数（即目标函数）在某种意义下的极值（极小或极大）。 对于数学规划，我们研究其中应用最为广泛的线性规划问题线性规划的基本特点： 是运筹学中应用最广泛的方法之一 网络分析、整数规划、目标规划和多目标规划都是以线性规划为基础的 解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大研究对象： 有一定的人力、财力、资源条件下，如何合理安排使用，效益最高 某项任务确定后，如何安排人、财、物，使之最省典型应用 合理利用线材问题：如何下料使用材最少 配料问题：在原料供应量的限制下如何获取最大利润 投资问题：从投资项目中选取方案，使投资回报最大 产品生产计划：合理利用人力、物力、财力等，使获利最大 劳动力安排：用最少的劳动力来满足工作的需要 运输问题：如何制定调动方案，使总运费最小 为什么要使用线性规划？ 线性规划很容易且有效率地被求解 如果存在最优解，则肯定能够找到 功能强大的敏感性分析 许多实际问题本质上是线性的1.1 原始问题例 1.1（产品组合问题） 某公司现有三条生产线来生产两种新产品，其主要数据如表 1.1所示。请问如何生产可以让公司每周利润最大？表 1.1 产品组合问题的数据表生产线 生产单位产品所需时间 生产线每周可用时间产品甲 产品乙一 1 0 4二 0 2 12三 3 2 18单位产品的利润 3 5此问题是在生产线可利用时间受到限制的情形下寻求每周利润最大化的产品组合问题。在建立产品组合模型的过程中，以下问题需要得到回答：（ 1）要做出什么决策？（ 2）做出的决策会有哪些条件限制？（ 3）这些决策的全部评价标准是什么？（ 1）变量的确定要做出的决策是两种新产品的生产水平，记 x1为每周生产产品甲的产量， x2为每周生产产品乙的产量。一般情况下，在实际问题中常常称为变量（决策变量）（ 2）约束条件求目标函数极值时的某些限制称为约束条件。如两种产品在相应生产线上每周生产时间不能超过每条生产线的可得时间，对于生产线一，有 x14，类似地，其它生产线也有不等式约束（ 3）目标函数对这些决策的评价标准是这两种产品的总利润，即目标函数是要求每周的生产利润（可记为 z，以百元为计量单位）为最大这样，可以把产品组合问题抽象地归结为一个数学模型：max z = 3x1+5x2s.t. x1 42x2 123x1+ 2x2 18x1 0， x2 0其中， max是最大化（ maximize）的英文简称， s.t.是受约束于（ subject to）的简称。上面数学模型中的决策变量为可控的连续变量，目标函数和约束条件都是线性的，称为线性规划（ linear programming）问题，是最基本的数学规划问题。线性规划问题隐藏了如下假定： 比例性假定：意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是一个常数 可加性假定：每个决策变量对目标函数和约束条件的影响是独立于其它变量的，目标函数值是每个决策变量对目标函数贡献的总和 连续性假定：决策变量应取连续值 确定性假定：所有参数都是确定的，不包含不确定因素上述隐含的假定条件是很强的。因此在使用线性规划时必须注意问题在什么程度上满足这些假定。当不满足的程度较大时，应考虑使用其它方法。如：整数规划 (integer programming，简记为 IP)模糊线性规划 (fuzzy linear programming)非线性规划 (nonlinear programming，简记为 NP或NLP)组合优化 (combinatorial optimization)参数规划 (parametric programming)多目标规划 (multi-objective programming)随机规划 (stochastic programming)下面我们把例 1.1推广为一般产品组合问题。设有 m种资源用于生产 n种不同产品，各种资源的拥有量分别为 bi（ i=1,2, m）。又生产单位第 j种产品（ j=1,2, n）时将消费第 i种资源 aij单位，利润为 cj元。表 1.2给出线性规划模型所需的数据。表 1.2 线性规划模型所需数据资源 单位活动对资源的使用量 资源可利用量1 2 n1 a11 a12 a1n b12 a21 a22 a2n b2 m am1 am2 amn bm单位活动对 z的贡献c1 c1 cn仍用 xj（ j=1,2, n）代表第 j种产品的生产数量，则线性规划模型为max z = c1x1 + c2x2 + + cnxns.t. a11x1 +a12x2 + a1nxnb1a21x1 +a22x2 + a2nxnb2 am1x1+am2x2 + amnxnbmx1 ， x2 ， ， xn 0其中，目标函数可以为 min的形式，函数约束中 “”可以为 “ ”或 “”，变量的非负性限制也可以取消。以上模型可简写为：用向量形式表达时，上述模型可简写为：其中， c=(c1,c2, cn)， x=(x1,x2, xn)T，pj=(a1j,a2j, amj)T， b=(b1,b2, bm)T. 用矩阵形式表达时，上述模型可简写为：max z = cxs.t. Ax bx 0其中， c=(c1,c2, cn)， x=(x1,x2, xn)T， b=(b1,b2, bm)T ， A=(aij)mn被称为约束方程组的（消耗）系数矩阵 . 在求解例 1.1之前，先复习并引入一些基本概念（ 1）决策变量（ 2）目标函数，目标函数值（ 3）约束条件：非负约束与函数约束（ 4）参数：模型的参数是数学模型中的常数（ 5）解：决策变量的任何一个取值称为模型的解（ 6）满足所有约束条件的解称为可行解。反之，一个非可行解至少违反一个约束条件。全部可行解的集合称为可行域（ 7）使目标函数达到最大值的可行解称为最优解，该目标函数值称为最优值。下面用图解法求解例 1.1图 1.1 产品组合问题(0,9)(0,6)(6,0)(4,0)(2,6)(4,3)(4,6)可行域z=3x1+5x2x2x1(0,0)x1=03x1+2x2=18x1=42x2=12x2=0思考，此最优解是唯一的吗？在一般情况下，解的情况还可能出现下列几种：（ 1）无穷多最优解（ 2）无界解（ 3）无可行解无穷最优解(0,9)(0,6)(6,0)(4,0)(2,6)(4,3)(4,6)可行域x2x1(0,0)x1=03x1+2x2=18x1=42x2=12x2=0z=3x1+2x2无界解可行域x2x1(0,0)x1=0x1=4x2=0(4,0)z=3x1+5x2无可行解(0,9)(0,6)(6,0)(4,0)(2,6)(4,3)(4,6)x2x1(0,0)x1=03x1+2x2=18x1=42x2=12x2=03x1+5x2=50若线性规划问题的决策变量超过 2个时，应用图解法求解时便会显得很困难。这里需要解决线性规划问题的更一般的代数的方法 单纯形法。单纯形法可以解决成千上万个变量或约束条件的线性规划问题。在使用单纯形法解决问题中，必须对线性规划的一般形式进行变形，化为标准形式。线性规划的标准形式： 目标函数取极大化， 约束条件全为等式， 约束条件右端常数项均为非负值， 变量取值为非负。对于非标准形式的线性规划问题，可通过下列方法化为标准形式：（ 1）目标函数求极小值。即 min z=cjxj，令 z=-z即可。（ 2）约束条件为不等式。当为 “”时，如 x14时，可添加 x30，使得 x1+x3=4；当为“”时，如 6x1+4x29，可添加 x40，使得6x1+4x2-x4=9。这里