第2章线性规划
《第2章线性规划》由会员分享，可在线阅读，更多相关《第2章线性规划（130页珍藏版）》请在文档大全上搜索。
1、第二章第二章 线性规划线性规划Linear Programming线性规划线性规划线性规划是运筹学中研究较早、应用较广泛、发展较成线性规划是运筹学中研究较早、应用较广泛、发展较成熟的一个分支。它有效地解决了生产规划、任务分配以熟的一个分支。它有效地解决了生产规划、任务分配以及配料等的最优化问题。这种最优化方法在油气储运系及配料等的最优化问题。这种最优化方法在油气储运系统中的应用也较为广泛，如炼厂或商品油库油品调和的统中的应用也较为广泛，如炼厂或商品油库油品调和的最优化问题，最优月输油计划、商品油库的最优进货计最优化问题，最优月输油计划、商品油库的最优进货计划问题等，都可以用线性规划方法解决。单
2、纯形法是线划问题等，都可以用线性规划方法解决。单纯形法是线性规划的主要算法，虽然有人还提出过其他一些算法，性规划的主要算法，虽然有人还提出过其他一些算法，但到目前为止，单纯形法仍然是最有效的算法。本章重但到目前为止，单纯形法仍然是最有效的算法。本章重点介绍单纯形法的原理和算法。点介绍单纯形法的原理和算法。2.1 线性规划问题的一般形式及其标准型线性规划问题的一般形式及其标准型线性规划问题是一类特殊的最优化问题，其目标函数是决线性规划问题是一类特殊的最优化问题，其目标函数是决策变量的线性函数，约束条件是关于决策变量的线性等式策变量的线性函数，约束条件是关于决策变量的线性等式或不等式。线性规划问题
3、的一般形式为：或不等式。线性规划问题的一般形式为：nnxcxcxcS 2211 max(min) 0,.2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats线性规划问题的一般形式及其标准型线性规划问题的一般形式及其标准型 njjjxcSmax(min)1 简写为：简写为： njxmibxatsjijij1 01 .n1j在上述数学模型中，在上述数学模型中，的含义包括的含义包括、=、 。 为了便为了便于讨论和求解，通常把给定的线性规划问题都划成如于讨论和求解，通常把给定的线性规划问题都划成如下的标准形式：下的标准形式：线性规划问题
4、的一般形式及其标准型线性规划问题的一般形式及其标准型 njjjxcS1 max njxmibxatsjijij1 01 .n1j这种形式称为线性规划问题的标准型，其中这种形式称为线性规划问题的标准型，其中bi0(i=1m)。有些书上规定标准型的目标函数是求有些书上规定标准型的目标函数是求min ,但这对问题的但这对问题的求解没有本质的影响，因为求求解没有本质的影响，因为求min 也可以转化为求也可以转化为求max。线性规划问题的一般形式及其标准型线性规划问题的一般形式及其标准型 标准型的向量形式：标准型的向量形式：CXS max 0 .1XbxPtsnjjj其中其中 ：C=(c1,c2, ,
5、cn) 称为目标系数行向量。称为目标系数行向量。线性规划问题的一般形式及其标准型线性规划问题的一般形式及其标准型 mmjjjjnbbbbaaaPxxxX212121 (决策变量列向量决策变量列向量) (xj的系数列向量的系数列向量) (右端系数列向量右端系数列向量) 标准型的矩阵形式：标准型的矩阵形式：CXS max 0.XbAXts nmijmnmmnnaaaaaaaaaaA 212222111211 其其中中A称为约束系数矩阵。称为约束系数矩阵。线性规划问题的一般形式及其标准型线性规划问题的一般形式及其标准型对于给定的线性规划问题，如果它不符合标准型的要求，对于给定的线性规划问题，如果它不
6、符合标准型的要求，则可通过下述途径将其化为标准型：则可通过下述途径将其化为标准型： SmaxSmaxSminSS ，则则令令 njijijbxa1 2、约约束束条条件件为为，使得，使得非负变量非负变量在不等式左边加上一个在不等式左边加上一个0 inx njiinjijbxxa1xn+i称为松弛变量称为松弛变量(slack variable)。1、目标函数为、目标函数为min S线性规划问题的一般形式及其标准型线性规划问题的一般形式及其标准型 njijijbxa1 3、约约束束条条件件为为，使使得得非非负负变变量量在在不不等等式式左左边边减减去去一一个个0 inx njiinjijbxxa1xn
7、+i称为剩余变量称为剩余变量(surplus variable)。）（、约约束束条条件件为为0 41 injijijbbxa在等式两端同乘以在等式两端同乘以-1，则，则)0( )(1 iinjijijbbbxa线性规划问题的一般形式及其标准型线性规划问题的一般形式及其标准型可可正正可可负负。的的数数值值无无正正负负要要求求，为为自自由由变变量量，即即对对、 5jjjxxx关于松弛变量和剩余变量，有以下几点需要说明：关于松弛变量和剩余变量，有以下几点需要说明： 在标准型中，松弛（剩余）变量与原问题中的决策变量在标准型中，松弛（剩余）变量与原问题中的决策变量具有同等地位。具有同等地位。 对实际问题
8、而言，松弛（剩余）变量与原问题中的决策对实际问题而言，松弛（剩余）变量与原问题中的决策变量一样具有明确的物理和经济意义。变量一样具有明确的物理和经济意义。、，令，令为了满足标准型的要求为了满足标准型的要求0 jjjjjxxxxx线性规划问题的一般形式及其标准型线性规划问题的一般形式及其标准型 松弛（剩余）变量对目标函数无影响，因为它们在目松弛（剩余）变量对目标函数无影响，因为它们在目标函数中的系数均为标函数中的系数均为0。 从数学上讲，松弛变量与剩余变量无本质区别，故也从数学上讲，松弛变量与剩余变量无本质区别，故也可将两者统称为松弛变量。可将两者统称为松弛变量。2.2 线性规划的图解法线性规划
9、的图解法图解法是求解线性规划问题最简单、直观的方法，它的图解法是求解线性规划问题最简单、直观的方法，它的基本思想是将一个代数问题转化为一个几何问题求解。基本思想是将一个代数问题转化为一个几何问题求解。但这种方法只适用于有两个决策变量的情况，对于有三但这种方法只适用于有两个决策变量的情况，对于有三决策变量的情况，图解法原则上也是适用的，但由于作决策变量的情况，图解法原则上也是适用的，但由于作图复杂，一般不予采用。对于三维以上的情况，图解法图复杂，一般不予采用。对于三维以上的情况，图解法更是无能为力。尽管如此，图解法对我们从直观上了解更是无能为力。尽管如此，图解法对我们从直观上了解线性规划问题解的
10、性质还是很有启发的。下面通过一个线性规划问题解的性质还是很有启发的。下面通过一个例子说明图解法的解题步骤。例子说明图解法的解题步骤。线性规划的图解法线性规划的图解法例：例：某企业计划生产某企业计划生产I 、II两种产品，需要两种产品，需要A、B、C、D四四种不同的原料。已知生产每种产品需要各种原料的比种不同的原料。已知生产每种产品需要各种原料的比例、产品的单位利润和原料总量见下表。问该企业应例、产品的单位利润和原料总量见下表。问该企业应如何安排生产才能获得最大利润？如何安排生产才能获得最大利润？ABCD利润利润(千元千元/吨吨)III2212400423原料总量原料总量(吨吨)1281612线
11、性规划的图解法线性规划的图解法解：设解：设I、II两种产品的产量分别为两种产品的产量分别为x1、x2，总利润，总利润为为S，则可以列出以下数学模型：，则可以列出以下数学模型： 0124164821222.32 max2121212121xxxxxxxxtsxxS，显然这是一个线性规划问题。因为它只有两个决策变量，显然这是一个线性规划问题。因为它只有两个决策变量，故可以用图解法求解。图解法的具体步骤如下：故可以用图解法求解。图解法的具体步骤如下：线性规划的图解法线性规划的图解法1、在平面直角坐标系中作出问题的可行域、在平面直角坐标系中作出问题的可行域 可行域：可行域：对于一个数学规划来说，其可行
