线性规划模型的应用与灵敏度分析第一章线性规划问题1.线性规划简介及发展线性规划（Linear Programming）是运筹学中研究最早、发展最快、应用广泛、方法成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法，研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写为LP。

它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面，为合理利用有限的人力、物力、财力等资源做出的最优决策，提供科学的依据。

线性规划及其通用解法——单纯形法是由美国G.B.Dantzig在1947年研究空军军事规划提出来的。

法国数学家傅里叶和瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。

1939年苏联数学家康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视[1]。

1947年美国数学家丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法，为这门学科奠定了基础。

1947年美国数学家诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力[2]。

1951年美国经济学家库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。

50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。

例如，1954年莱姆基提出对偶单纯形法，1954年加斯和萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年塔克提出互补松弛定理，1960年丹齐克和沃尔夫提出分解算法等。

线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究[3]。

由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。

1979年苏联数学家提出解线性规划问题的椭球算法，并证明它是多项式时间算法。

1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。

用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。

现已形成线性规划多项式算法理论。

50年代后线性规划的应用范围不断扩大。

建立线性规划模型线性规划研究的问题主要有两类:一类是当一项任务确定后，如何统筹安排，尽量做到以最少的人力、物力等资源去完成；另一类是在人力、物力等资源确定的情况下，如何安排使用这些资源，使创造的价值最多，其实质是解决稀缺资源在有竞争环境中如何进行最优分配的问题，即寻求整个问题的某个整体指标最优的问题[4]。

2. 线性规划的数学模型2.1 线性规划问题例1-1某工厂在计划期内要安排生产两种产品Ⅰ,Ⅱ，已知生产单位产品所需的设备台数及A,B 两种原材料的消耗量，见表1-1。

该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排生产计划使该工厂获得的利润最大？有关资料如下表1-1产品、资源信息产品Ⅰ Ⅱ 资源限量 设备/台1 2 8 原材料A/kg4 0 16 原材料B/kg 0 4 12用数学语言来描述生产计划的安排，建立数学模型。

解：设x 1,x 2分别表示在计划期内产品Ⅰ,Ⅱ的生产量，在满足资源限量的条件下，它们必须同时满足下列条件。

对设备有效台数： 8221≤+x x对原材料A ： 1641≤x对原材料B ： 1242≤x该工厂的生产目标是在不超过所有资源限量的条件下，确定生产量x 1,x 2，使该 得到的利润最大。

若用Z 表示总利润，则有2132m ax x x Z +=综合上述，该生产计划问题可用数学模型表示为2132m ax x x Z +=⎪⎪⎩⎪⎪⎨⎧≥≤≤≤+0,12416482212121x x x x x x (1-1) 这就是一个线性规划模型[5]。

2.2 线性规划问题的数学模型线性规划数学模型是由一组含有等式或者不等式的代数方程以及一个具有求极值关系的目标函数表达式构成的符合抽象数学模型。

下面介绍建立实际问题线性规划模型的基本步骤。

（1） 确定决策变量。

这是很关键的一步，决策变量选取得当，不仅会使线性规划的数学模型建得容易，而且求解比较方便。

（2） 找出所有限制条件，并用决策变量的线性等式或不等式来表示，从而得到约束条件。

一般可用表格形式列出所有的限制数据，然后根据所列出的数据写出相应的约束条件，以避免遗漏或重复所规定的限制要求。

（3） 把实际问题所要达到的目的用决策变量的线性函数来表示，得到目标函数，并确定是求最大值还是最小值。

（4） 根据实际问题添加非负约束。

线性规划的数学表达式成为线性规划的数学模型，一般形式为n n x c x c x c Z +++= 2211m ax (m in) (1-2)s.t.⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥≥≥=≤+++≥=≤+++≥=≤+++0,,0,0),(),(),(2122112222212111212111n m n mn m m n n n n x x x b x a x a x a b x a x a x a b x a x a x a (1-3)其中，式(1-2)称为目标函数，(1-3)式称为约束条件。

2.3 线性规划的性质定理1 线性规划问题的可行解X 是基可行解的充要条件是X 的非零分量对应的系 数矩阵A 的列向量线性无关[6]。

定理2 若一个线性规划问题有可行解，则它必有基本可行解[7]。

定理3 若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。

证明：设)2()1(,X X 是可行域的顶点，若)0(X 不是顶点，且目标函数在)0(X 处达到最优)0(*CX Z =（标准型是Z Z max *=）。

因为)0(X 不是顶点，所以D 的顶点线性表示为)(1)0(i ki i X a X ∑== (1-4)在所有顶点中必然能找到某个顶点)(m X ，使)(m CX 是所有)(i CX 中最大者，并且将)(m X 代替式（1-5）中所有的)(i X ，这就得到)()(1)(1m m ki i i k i i CX X C XC =≤∑∑==αα，由此得到)()0(m CX CX ≤，根据假设)(O CX 最大值，所以只能有)()0(m CX CX =，即目标函数在顶点)(m X 处也达到最大值。

有时目标函数可能在多个顶点处达到最大值，这时在这些顶点的凸集合上也达到最大值，称这种线性规划问题有无穷多最优解。

由以上的讨论可知，为了寻求线性规划问题的最优解，只从其有限数目的基本可行解中去寻找基础最优解就可以了。

尽管如此，当数m,n 较大时，用此种方法求其最优解也是不可行的[8]。

第二章求解线性规划的方法1. 图解法图解法是求解线性规划模型的一种重要方法，线性规划中一些重要的性质、概念和求解思想都来源于此。

当只有两个决策变量时，可以用图解法求解。

它具有简单直观的特点。

为了给后面的线性问题的基本理论提供较直观的几何说明，先介绍线性规划问题的图解法[8]。

我们把满足约束条件和非负约束条件的一组解叫做可行解，所有可行解组成的集合称为可行域。

图解法的求解步骤如下：第一步，根据约束画出可行域，先以决策变量为坐标，建立直角坐标系，再根据各约束条件，作出可行域。

第二步，作出一条目标函数等值线，并确定增值方法。

第三步，沿等值线的法线方向值增大方向移动，从而找到最大值。

图解法得出线性规划的几种情况：表2-1 解的几种情况解的几种情况约束条件图形特点方程特点惟一解一般围成有限区域，最优值只在一个顶点达到--无穷多解在围成的区域边界上，至少有两个顶点处达到最优目标和某一约束方程成比例无可行解（无解）围不成区域有矛盾方程无界解（无解）围成无界区域，且无有限最优值缺少一必要条件的方程2. 单纯形法2.1 单纯形法的发展单纯形法（simplex methods ），求解线性规划的通用方法。

单纯形法是美国数学家G .B.Dantzig 于1947年首先提出的。

简单的说就是一种数学迭代方法，求解基本过程是从一个基本可行解跳到另一个基本可行解的逐步替代，从而使目标函数不断得到改善。

它的理论根据是：线性规划问题的可行域是n 维向量空间n R 中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到[9]。

2.1.1 单纯形法的基本思路单纯形法的基本思路是：根据线性规划问题的标准型，从可行域中某个基本可行解（一个顶点）开始，转换到另一个基本可行解（顶点），并且当目标函数达到最大值时，问题就得到了解决，其基本思路的框架图如下图2-1。

图2-1 单纯形法的基本思路 例2-1 用单纯形法讨论例1-1的求解。

解：已知例1.1的标准型为：5432100032m ax x x x x x Z ++++= (2-1)⎪⎪⎩⎪⎪⎨⎧=≥=+=+=+5,,2,1,012416482524121 j x x x x x x x j (2-2) 约束条件(2-2)的系数矩阵⎪⎪⎪⎭⎫ ⎝⎛==100400100400121),,,,(54321P P P P P A显然，3x ，4x ，5x 的系数列向量⎪⎪⎪⎭⎫ ⎝⎛=0013P ，⎪⎪⎪⎭⎫ ⎝⎛=0104P ，⎪⎪⎪⎭⎫ ⎝⎛=1005P (2-3) 是线性独立的，因而这些向量构成一个基()⎪⎪⎪⎭⎫ ⎝⎛==100010001,,543P P P B (2-4)对应于B 的基变量为3x ,4x ,5x ，从约束条件(2-2)中可以看到251421341241628x x x x x x x -=-=--= (2-5)当令非基变量021==x x ，这时得到一个基本可行解)0(XT X )12,16,8,0,0()0(= (2-6) 将式(2-3)代入目标函数(2-1)得到032021=++=x x Z (2-7) 这个基本可行解表示：工厂没有安排生产Ⅰ,Ⅱ产品；资源都没有被利用，所以工厂的利润0=Z 。

分析目标函数的表达式(2-7)可以看到：非基变量1x ,2x 的系数都是正数，因此将非基变量变为基变量，目标函数的值就可能增大，从经济意义上讲，安排生产产品Ⅰ或Ⅱ，就可以使工厂的利润指标增加，所以只要在目标函数(2-7)的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与某个基变量进行对换，一般选择正系数最大的那个非基变量2x 为换入变量，将它换入到基变量中区，同时还有确定基变量中有一个要换出来成为非基变量，可按以下方法来确定换出变量。

现分析式(2-5)，当将2x 定为换入变量后，必须从3x ,4x ,5x 中换出一个，并保证其余的都是非负，即3x ,4x ,5x ≥0。

当01=x ，由式(2-5)得到41201602825423≥-=≥=≥-=x x x x x (2-8)从式(2-8)中可以看出，只有选择3)4/12,2/8m in(2=-=x (2-9)时，才能使式(2-8)成立。