线性规划模型的应用与灵敏度分析正文

1、线性规划模型的应用与灵敏度分析第一章 线性规划问题1. 线性规划简介及发展线性规划（Linear Programming）是运筹学中研究最早、发展最快、应用广泛、方法成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法，研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写为LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面，为合理利用有限的人力、物力、财力等资源做出的最优决策，提供科学的依据。线性规划及其通用解法单纯形法是由美国在1947年研究空军军事规划提出来的。法国数学家傅里叶和瓦莱普森分别于1832和1911年独立地提出线性规划的想

2、法，但未引起注意。1939年苏联数学家康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视1。1947年美国数学家丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法单纯形法，为这门学科奠定了基础。1947年美国数学家诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力2。1951年美国经济学家库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年莱姆基提出对偶单纯形法，1954年加斯和萨迪等人解决了线性规划的灵敏度分析和参数规

3、划问题，1956年塔克提出互补松弛定理，1960年丹齐克和沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究3。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。1979年苏联数学家提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性

4、规划的应用范围不断扩大。 建立线性规划模型线性规划研究的问题主要有两类:一类是当一项任务确定后，如何统筹安排，尽量做到以最少的人力、物力等资源去完成；另一类是在人力、物力等资源确定的情况下，如何安排使用这些资源，使创造的价值最多，其实质是解决稀缺资源在有竞争环境中如何进行最优分配的问题，即寻求整个问题的某个整体指标最优的问题4。2. 线性规划的数学模型2.1 线性规划问题例1-1某工厂在计划期内要安排生产两种产品,，已知生产单位产品所需的设备台数及A,B两种原材料的消耗量，见表1-1。该工厂每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排生产计划使该工厂获得的利润最大？有关资料

5、如下表1-1产品、资源信息产品资源限量设备/台128原材料A/kg4016原材料B/kg0412用数学语言来描述生产计划的安排，建立数学模型。解：设x,x分别表示在计划期内产品,的生产量，在满足资源限量的条件下，它们必须同时满足下列条件。 对设备有效台数： 对原材料A： 对原材料B： 该工厂的生产目标是在不超过所有资源限量的条件下，确定生产量x,x，使该得到的利润最大。若用Z表示总利润，则有 综合上述，该生产计划问题可用数学模型表示为 (1-1)这就是一个线性规划模型5。2.2 线性规划问题的数学模型线性规划数学模型是由一组含有等式或者不等式的代数方程以及一个具有求极值关系的目标函数表达式构成

6、的符合抽象数学模型。下面介绍建立实际问题线性规划模型的基本步骤。（1） 确定决策变量。这是很关键的一步，决策变量选取得当，不仅会使线性规划的数学模型建得容易，而且求解比较方便。 （2） 找出所有限制条件，并用决策变量的线性等式或不等式来表示，从而得到约束条件。一般可用表格形式列出所有的限制数据，然后根据所列出的数据写出相应的约束条件，以避免遗漏或重复所规定的限制要求。 （3） 把实际问题所要达到的目的用决策变量的线性函数来表示，得到目标函数，并确定是求最大值还是最小值。 （4） 根据实际问题添加非负约束。 线性规划的数学表达式成为线性规划的数学模型，一般形式为 (1-2) s.t. (1-3)

7、其中，式(1-2)称为目标函数，(1-3)式称为约束条件。2.3 线性规划的性质定理1 线性规划问题的可行解X是基可行解的充要条件是X的非零分量对应的系数矩阵A的列向量线性无关6。定理2 若一个线性规划问题有可行解，则它必有基本可行解7。定理3 若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。证明：设是可行域的顶点，若不是顶点，且目标函数在处达到最优（标准型是）。因为不是顶点，所以D的顶点线性表示为 (1-4)在所有顶点中必然能找到某个顶点，使是所有中最大者，并且将代替式（1-5）中所有的，这就得到，由此得到，根据假设最大值，所以只能有，即目标函数在顶点处也达到最大值。

8、有时目标函数可能在多个顶点处达到最大值，这时在这些顶点的凸集合上也达到最大值，称这种线性规划问题有无穷多最优解。由以上的讨论可知，为了寻求线性规划问题的最优解，只从其有限数目的基本可行解中去寻找基础最优解就可以了。尽管如此，当数m,n较大时，用此种方法求其最优解也是不可行的8。第二章 求解线性规划的方法1. 图解法图解法是求解线性规划模型的一种重要方法，线性规划中一些重要的性质、概念和求解思想都来源于此。当只有两个决策变量时，可以用图解法求解。它具有简单直观的特点。为了给后面的线性问题的基本理论提供较直观的几何说明，先介绍线性规划问题的图解法8。我们把满足约束条件和非负约束条件的一组解叫做可行

9、解，所有可行解组成的集合称为可行域。图解法的求解步骤如下：第一步，根据约束画出可行域，先以决策变量为坐标，建立直角坐标系，再根据各约束条件，作出可行域。第二步，作出一条目标函数等值线，并确定增值方法。第三步，沿等值线的法线方向值增大方向移动，从而找到最大值。图解法得出线性规划的几种情况：表2-1 解的几种情况解的几种情况约束条件图形特点方程特点惟一解一般围成有限区域，最优值只在一个顶点达到-无穷多解在围成的区域边界上，至少有两个顶点处达到最优目标和某一约束方程成比例无可行解（无解）围不成区域有矛盾方程无界解（无解）围成无界区域，且无有限最优值缺少一必要条件的方程2. 单纯形法2.1 单纯形法的

10、发展单纯形法（simplex methods），求解线性规划的通用方法。单纯形法是美国数学家G.B.Dantzig于1947年首先提出的。简单的说就是一种数学迭代方法，求解基本过程是从一个基本可行解跳到另一个基本可行解的逐步替代，从而使目标函数不断得到改善。它的理论根据是：线性规划问题的可行域是n维向量空间中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到9。 单纯形法的基本思路单纯形法的基本思路是：根据线性规划问题的标准型，从可行域中某个基本可行解（一个顶点）开始，转换到另一个基本可行解（顶点），并且当目标函数达到最大值时，问题就得到了解决，其基本思路的框架图如下图2-1。给出一个初始基

11、本可行解是否最优 否 是从当前基可行解出发，寻求一个能使目标函数值活的改善的新的基本可行解写出最优解 图2-1 单纯形法的基本思路例2-1 用单纯形法讨论例1-1的求解。解：已知例1.1的标准型为： (2-1) (2-2) 约束条件(2-2)的系数矩阵 显然，的系数列向量 ， (2-3)是线性独立的，因而这些向量构成一个基 (2-4)对应于的基变量为,，从约束条件(2-2)中可以看到 (2-5)当令非基变量，这时得到一个基本可行解 (2-6)将式(2-3)代入目标函数(2-1)得到 (2-7)这个基本可行解表示：工厂没有安排生产,产品；资源都没有被利用，所以工厂的利润。分析目标函数的表达式(2

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

13、，才能使式(2-8)成立。因为当时，基变量，所以可用去替代。以上数学模型说明了每生产一件产品，需要用掉的各种资源数为(2,0,4)。这些资源中的薄弱环节确定了产品的产量。原材料B的数量决定产品的产量只能是件。为了求得以为基变量的一个基本可行解和进一步分析问题，需将方程(2-5)中的位置对换。得到 (2-10)用高斯消去法求解，得到以非基变量表示的基变量 (2-11)再将式(1-12)代入目标函数(1-6)得到 (2-12)令非基变量，得到，并得另一个基本可行解。从目标函数的表达式(2-12)中可以看到，非基变量的系数是正的，说明目标函数的值还可以增大，还不是最优解。于是用上述方法，确定换入、换

14、出变量，继续迭代，再得到另外一个基本可行解。再经过一次迭代，得到一个基本可行解。而这时得到的目标函数的表达式是 (2-13)再分析目标函数(2-13)，可知所有非基变量,的系数都是负数，这说明若要用剩余资源,，就必须支付附加费用。所以当时，即不再利用这些资源时，目标函数达到最大值，那么是最优解。这说明当产品生产4件，产品生产2件，工厂才能得到最大利润。通过上例，可以了解利用单纯形法求解线性规划问题的思路。 单纯形法的一般描述和求解步骤一般的线性规划问题的求解有以下几个步骤。（1） 确定初始基本可行解。为了确定初始基本可行解，首先要找出初始可行解。设一线性规划问题为 (2-14)可分为两种情况讨

15、论。 若中存在一个单位基，则将其作为初始可行基 (2-15) 若中不存在一个单位基，则人为地构造一个单位初始基。（2） 检验最优解。得到初始基本可行解后，要检验该解是否为最优解。如果是最优解，则停止运算；否则转入（3）基变换。下面给出最优性判别定理。一般情况下，经过迭代后可以得到以非基变量表示基变量的表达式 (2-16)将式(2-11) 代入式(2-10)的目标函数，整理后得 (2-17)令 , (2-18)于是 (2-19)再令 (2-20)则得到以非基变量表示目标函数的表达式 (2-21)（3） 基变换。若初始基本可行解不是最优解，又不能判别无界时，由目标函数(2-10)的约束条件可看到，

16、当某些，增加则目标函数值还可能增加，这时就要将其中某个非基变量换到基变量中去（称为换入变量），同时，某个基变量要换成非基变量（称为换出变量），随之会得到一个新的基本可行解。从一个基本可行解到另一个基本可行解的变换，就是进行一次基变换。从几何意义上就是从可行域的一个顶点转向另一个顶点。（4） 迭代。在确定了换入变量和换出变量后，要把和的位置进行对换，就是说要把对应的系数列向量变成单位列向量。这可以通过对约束方程组的增广矩阵进行初等行变换来实现，变换结果得一新的基本可行解。然后转入（2）。2.2 单纯形法的进一步讨论对于一般的线性规划问题，在用单纯形法求解之前，总是先化为标准型。如果在系数矩阵中有

17、一个单位阵，则可以作为初始可行基。如果约束条件的系数矩阵中不存在单位矩阵，则可以通过添加人工变量的方法，在标准型的约束方程的系数矩阵中人为地构造一个单位阵，从而获得初始可行基，再作进一步迭代。在单纯形迭代过程中，要求人工变量逐步从基变量被替换出，变为非基变量，这有两种方法：大M法和两阶段法10。人工变量法的基本思想：对于线性规划问题，有时候很难找出初始基本可行解，这时可以考虑加入人工变量的方法来解决问题。基本原理对于标准型的线性规划问题： (2-22)给每个约束方程硬性加入一个人工变量之后得到： (2-23)这样，就可以以为基变量，得到问题的初始基本可行解。在求解的过程中，通过迭代不断地将这些

18、人工变量从基变量中迭代出去，使人工变量均等于0，从而求得原始问题的最优解。若不能把人工变量完全迭代出去，则表明原始问题无可行解。下面介绍人工变量的两种方法。（1） 大M法在目标函数求最大值的线性规划问题中，设人工变量在目标函数中的系数为-M，M为任意大的正数。只要人工变量不为零，目标函数最大值就是一个任意小的数。（2） 两阶段法第一阶段：建立一个辅助线性规划，并求解，以判断原线性规划是否存在可行解。所有人工变量都变成非基变量，目标函数最小值为0，原问题存在基可行解。转到第二阶段。若目标函数大于0，至少有一个人工变量不能从基变量中转出，由于它取正值，原问题没有可行解。停止。第二阶段：在第一阶段最

19、优表格中去掉人工变量，将目标函数系数换成原问题的目标函数系数，接下去用单纯形法计算，直到得到最优解为止。3单纯形法对偶规划是线性规划问题从另一个角度进行研究，是线性规划理论的进一步深化，也是线性规划理论的进一步深化，也是线性规划理论整体的一个不可分割的组成部分。3.1 对偶问题的提出每个线性规划都有另一个线性规划（对偶问题）与它密切相关，对偶理论揭示了原问题与对偶问题的内在联系11。3.2 对偶问题的数学模型及对偶关系原问题P的标准形式： (2-24)对偶问题D的标准形式： (2-25)当我们讨论对偶问题时，它必定是与原问题成对出现的；同时，原问题与对偶问题之间没有严格的界限，它们互为对偶：一

20、个是原问题，则另一个就为对偶问题。表2-1给出了线性规划原问题与对偶问题的对应关系，该表也可以看做是一个线性规划原问题转化为对偶问题的一般规律。其中，对于变量与约束间关系的理解，必须考虑到对偶模型的约束与原问题模型的变量相对应，变量则是与原问题模型的约束相对应。如原问题是最小化，则可将对偶问题看做原问题12。表2-1 原问题模型与对偶问题模型的对应关系原问题(或对偶问题)对偶问题(或原问题)目标函数最大化()目标函数最小化()个变量个约束约束条件的资源向量（右端项）目标函数的价格向量（系数）个约束个变量目标函数的价格向量约束条件的资源向量变量约束约束变量例2-2 试求下列线性规划问题的对偶问题

21、。 (2-26)解：设对应于约束条件(2-14)的对偶变量分别为 则由表2-1中原问题与对偶问题的对应关系，可以直接写出上述线性规划问题的对偶问题，有 (2-27)3.3 线性规划的对偶理论线性规划的对偶理论包括以下几个主要的基本定理：定理2-1(对称性定理) 对偶问题的对偶是原问题。这一定理的内涵显而易见，证明从略。定理2-2(弱对偶定理) 设和分别是原问题P和对偶问题D的可行解，则必有13。定理2-3(对偶原理) 原问题P与对偶问题D存在如下对应关系：(1) P有最优解的充要条件是D有最优解。(2) 若P无界则D不可行，若D无界则P不可行。(3) 若和分别是P和D的可行解，则它们分别为P和

22、D的最优解的充要条件是。原问题与对偶问题的对应关系见表2-2。表2-2 原问题与对偶问题解的对应关系对应关系对偶问题有最优解无界无可行解原问题有最优解一定不可能不可能无界不可能不可能一定无可行解不可能一定可能定理2-4(互补松弛定理) 如果和分别为P和D的可行解，它们分别为P和D的最优解的充要条件是和。互补松弛定理也称松紧定理，它描述了线性规划问题达到最优时，原问题(或对偶问题)的变量取值和对偶问题(或原问题)约束的松紧性之间的对应关系。我们知道，在一对互为对偶的线性规划问题中，原问题的变量和对偶问题的约束是一一对应的，原问题的约束和对偶问题的变量也是一一对应的。当线性规划问题达到最优时，我们

23、不仅可以同时得到原问题与对偶问题的最优解，而且还可以得到变量与约束之间的一种对应关系。互补松弛定理即揭示了这一点。3.4 对偶单纯形法的思路对偶单纯形法是用对偶理论求解原问题的一种方法，而不是求解对偶问题解的单纯形法。与对偶单纯形法相对应，已有的单纯形法称原始单纯形法14。对偶单纯形法适应求解：（1）使用条件：检验数全部0； 解答列至少一个元素小于零。 （2）实施对偶单纯形法的基本原则在保持对偶可行的前提下进行基变换每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量(作为换入变量)，使原始问题的非可行解向可行解靠近。（3） 计算步骤 建立初始单纯形表，计算检验数行。 基变换

24、。先确定换出变量解答列中的负元素(一般选最小的负元素)对应的基变量出基；即 (2-28)相应的行为主元行。然后确定换入变量原则是：在保持对偶可行的前提下，减少原始问题的不可行性。如果 (2-29)(最小比值原则)，则选为换入变量，相应的列为主元列，主元行和主元列交叉处的元素为主元素。 将主元素进行换基迭代(旋转运算、枢运算)，将主元素变成1，主元列变成单位向量，得到新的单纯形表。继续以上步骤，直至求出最优解15。例2-3 用对偶单纯形法解下列线性规划问题 (2-30)解：先将这个问题化成标准型 (2-31)再建立这个问题的初始单纯形表，并进行迭代计算，见下表。表2-3 初始单纯形表-3-900

25、00-2-1-11000-3-1-40100-3-1-70010-3-9000-3/-1-9/-1-表2-4 单纯形表（第一步迭代）-3-9000-3211-1000-30-3-1100-30-6-10160-6-300-6/-3-3/-1-表2-5 单纯形表（第二次迭代）-3-9000-35/310-4/31/30-91/3011/3-1/3001001-21800-1-20-0-1-2-最优解是目标函数最优值为。第三章 灵敏度分析灵敏度分析是研究与分析一个系统(或模型)的状态或输出变化对系统参数或周围条件变化的敏感程度的方法。在最优化方法中经常利用灵敏度分析来研究原始数据不准确或发生变化时

26、最优解的稳定性。通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响。因此，灵敏度分析几乎在所有的运筹学方法中以及在各种方案进行评价时都是很重要的16。1边际值(影子价)首先以()为例。边际值(影子价)是指在最优解的基础上，当第个约束行的右端项减少一个单位时，目标函数的变化量 (3-1) (3-2)机会成本 (3-3)因此 (3-4)机会成本的另外表达形式 (3-5)关于影子价的一些说明影子价是资源最优配置下资源的理想价格，资源的影子价与资源的紧缺度有关；松弛变量增加一个单位等于资源减少一个单位；剩余变量增加一个单位等于资源增加一个单位；资源有剩余，在最优解中就有对应松弛变量存在，且其影子

27、价为0；影子价为0，资源并不一定有剩余。2价值向量的灵敏度分析价值向量(即目标函数系数)的灵敏度分析分为原最终单纯形表中与非基变量和基变量对应两种情况来讨论17。（1） 若是非基变量的系数，则其对应的最终单纯形表中的检验数为 (3-6)或 (3-7)当变化，要保证最终单纯形表的最优解不变，必有 (3-8)保证最终单纯形表最优解不变，可得的允许变化值 (3-9)（2） 若是基变量的系数，应有,当变化时，就引起的变化，这时 (3-10)若要求原最优解不变，必须满足。于是得到 当 (3-11) (3-12)所以，可变化的范围是 (3-13)3灵敏度的应用（1）投入产出法中灵敏度分析可以用来研究采取某

28、一项重大经济政策后将会对国民经济的各个部门产生怎样的影响。（2）方案评价中灵敏度分析可以用来确定评价条件发生变化时备选方案的价值是否会发生变化或变化多少。第四章 应用实例某厂生产甲乙两种口味的饮料，每百箱甲饮料需用原料6千克，工人10名，可获利10万元；每百箱乙饮料需用原料5千克，工人20名，可获利9万元。今工厂共有原料60千克，工人150名，又由于其他条件所限甲饮料产量不超过800箱。问如何安排生产计划，即两种饮料各生产多少使获利最大.进一步讨论：1)若投资0.8万元可增加原料1千克，问应否作这项投资。2)若每100箱甲饮料获利可增加1万元，问应否改变生产计划。解：分别设在利润最大的时候生产

29、甲和乙的数量分别为：、百箱，则相应的甲和乙的原料数、工人数、利润分别为：、；、；、。根据题设条件可以得出线性规划模型为：目标函数为： (4-1)约束条件为： s.t. (4-2)编写M文件yuqian1.m如下：c=-10 -9;A=6 5;10 20;1 0;b=60;150;8;Aeq=; beq=;vlb=0;0; vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)计算结果为：x = 6.4286 4.2857fval = -102.8571所以最后应该生产的甲和乙分别为：6.4286、4.2857百箱，保留两位小数，应为6.42百箱和4.28百箱，相应

30、的最大利润为：102.72万元。下面进一步讨论：(1) 若投资0.8万元可增加原料1千克，问应否作这项投资。当增加1千克原料时的线性规划模型如下。目标函数： ； (4-3)约束条件： s.t. (4-4)编写M文件yuqian2.m如下：c=-10 -9;A=6 5;10 20;1 0;b=61;150;8;Aeq=; beq=;vlb=0;0; vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)计算结果为：x = 6.7143 4.1429fval = -104.4286这说明应该生产的甲和乙分别为：6.7143、4.1429百箱，保留两位小数，应为6.71

31、百箱和4.14百箱。相应的利润增加为：104.36-102.72=1.64>0.8。说明此时应该做这项投资。(2) 若每100箱甲饮料获利可增加1万元，问应否改变生产计划。此时相应的线性规划模型的目标函数为： ； (4-5)约束条件： s.t. (4-6)编写M文件yuqian3.m如下：c=-11 -9;A=6 5;10 20;1 0;b=60;150;8;Aeq=; beq=;vlb=0;0; vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)运行结果为：x = 8.0000 2.4000fval = -109.6000即相应的利润为：109.6000>102.8571，说明应该改变生产计划。结 论本文主要介绍了线性规划的应用及灵敏度分析，包括解线性规划问题的各种方法：图解法，单纯形法，大M法，两阶段法以及对偶单纯形法等，以及简单介绍了有关灵敏度分析的各种问题。通过对本论文的学习研究，除了能够写出线性规划问题的各种模型并对它进行分析求解，还能够写出任意一个线性规划问题的对偶理论，并能应用对偶单纯形法解决相应的线性规划问题，同时能对线性规划的求解结果进行多种情况的