《第3章(1) 单纯形法》由会员分享，可在线阅读，更多相关《第3章(1) 单纯形法（9页珍藏版）》请在金锄头文库上搜索。
1、1第第 3 章章 单纯形法单纯形法本章介绍求解线性规划问题的单纯形法，它是美国学者丹捷格（George Dantzig）在 1947 年提出来的，是求解线性规划问题的最有效的方法之一。为方便讨论，在第一节首先建立线性规划问题的标准形，然后在第二节讨论线性规划基本解的概念，第三节从几何概念和解释的角度介绍单纯形法，最后，介绍单纯形法的代数表达式和单纯形表。3.1 线性规划问题的标准形式线性规划问题的标准形式：max 1 122nnZc xc xc xs.t. 11 11221121 1222221 12212,0nnnnmmmnnmna xa xa xba xa xa xba xaxaxbx x
2、x （3.1）其中 0, 1,2,.,ibim或简记为11max(1,2,). . 0(1,2, )njj j nijji jjZc xa xbimst xjn 2若记 ， ，111212122212nnmmmnaaaaaaAaaa 12( ,)nCc cc，12mbbbb 12nxxXx 12,1,2,jj jmjaaPjna 则线性规划的标准形式还可以表示为如下几种形式：（1） 矩阵形式 max. .0ZCXAXbstX （2） 向量形式1max. .0njj jZCXp xbstX 其中“0”表示零向量。3线性规划的一般形式转化为标准形式的方法（1） 目标函数的转化：若原问题的目标函数是
3、求最小化，即1minnjj jZc x则可将目标函数乘以，等价转化为求如下最大化问题：( 1)1maxnjj jZc x （2） 不等式约束转化为等式约束：如果约束条件是线性不等式1nijji ja xb则通过引入松弛变量，将其转化为等价的等式约束条件0n ix1nijjn ii ja xxb 类似地，如果约束条件是线性不等式1nijji ja xb则通过引入剩余变量，将其转化为等价的等式约束条件0n ix1nijjn ii ja xxb （3） 变量约束的转换如果原问题中某个变量是自由变量（即无非负限制）则可令jx“0,0jjjjjxxx xx 代入原问题，即在原问题中将用两个非负变量之差代
4、替。jx4为自由变量例例 1： 将下列线性规划问题化为标准形式123123123123132min324231023. .2280,0,Zxxxxxxxxxstxxxxxx 解：原问题等价的线性规划标准形式： 1223“ 12234 12235 1223 122345max3224231023. .22 8,0Zxxxxxxxxxxxxxxstxxxxx x x x x x 53.2 线性规划问题的基本解对于线性规划问题的标准形式max. .0ZCXAXbstX 其中为 n 维行向量，分别12( ,)nCc cc1212( ,) ,( ,)0TT nmXx xxbb bb为 n 维和 m 维列
5、向量；为矩阵。()ijm nAam n假定矩阵 A 的秩为 m，且 m n.。A 中任意一个阶可逆子方阵 B (即m m)，称为线性规划问题的一个基阵基阵或基基。0B 若基阵12121212111222,mmmmjjjjjj jjjmjmjmjaaaaaaBPPPaaa 称为基向量基向量，相应决策变量为基变量基变量，A 中其余的 12, mjjjPPP 12, mjjjXXX列向量（不在 B 中）称为非基向量非基向量，对应的决策变量称为非基变量非基变量。jP例例 2：第一章的例 1 中的线性规划问题引入松弛变量化为如下标准形式：345,x x x12132412512345max4362 8.
6、23 18 ,0Zxxxx xxstxxx x x x x x 故约束系数矩阵123453 510100 02010( ,) 23001AP P P P P 6由于线性无关345,P P P0345100(,)010001BP P P 是可逆的。故是线性规划的一个基。对于基，是基变量，是0B0B345,x x x12,x x非基变量。又由于线性无关234,P P P1234010(,)201300BP P P 也是线性规划的一个基。对于基，是基变量，是非基变量。1B234,x x x15,x x对于线性规划的标准形式，当基确定以后，相应的基变量和非基变量也就确B定，我们可以将系数矩阵写成分块的
7、形式：A( ,)AB N其中，表示非基变量对应列向量构成的子矩阵。N将基变量组成的向量记为，非基变量组成的向量记为， 12(,) mT BjjjXxxxNX则X 也可以写成分块形式：BNXXX因此，约束方程组变为AXbBNBXNXb由于可逆，则存在，将左乘以上式的两边得B1B1B11 BNXB NXB b移项后得 11 BNXB bB NX事实上，对约束方程组，可以看作一组独立变量，它可以取任意的AXbNX7值，令，则，此时约束方程组有一个特殊形式的解0NX1 BXB bAXb10BNXB bXX称为线性规划的基本解基本解。由以上讨论可以看出，线性规划的基本解实际上是在约束方程组中将非基变量看
8、作独立的自由变量并令其取值为 0 后，解方程组得出的解；当基AXb确定时，基本解也唯一确定了。由于基可以是中任意 m 阶的可逆子矩阵，BBA即它的列是从 A 中 n 列中选出的线性无关的 m 列，其选法最多有，故基的个数和基本解的个数均不会超过个。! !()!m nnCm nmm nC基本解满足约束方程，但不一定是可行解。因为，它不10B bXAXb一定满足非负约束。我们把满足非负约束的基本解，即的基0X 10BXB b本解称为基本可行解基本可行解或基可行解基可行解，此时对应的基 B 称为可行基可行基。同10B bX理，线性规划问题基可行解的数目不超过个。m nC下面我们给出例 2 中基阵、基
9、本解、基本可行解以及可行区域顶点之间的对应关系，如表 3-1 所示：表表 3-18基阵 B基变量BX基本解X两个边界约束的交点可行域的顶点是否基本可行解是否是不可行基（）345,P P P（345,x x x）(0)(0,0,6,8,18)TX轴1x轴交2x点O(0,0)是是（）235,P P P（235,x x x）(1)(0,4,6,0,6)TX轴与2x的交点2lE(0,4)是是（）234,P P P（234,x x x）(2)(0,6,6, 4,0)TX轴与2x的交点3lD(0,6)否否（）123,P P P（123,x x x）(3)(3,4,3,0,0)TX与的2l3l交点C(3,4
10、)是是（）125,P P P（125,x x x）(4)(6,4,0,0, 6)TX与的1l2l交点F(6,4)否否（）124,P P P（124,x x x）(5)(6,2,0,4,0)TX与的1l3l交点B(6,2)是是（）134,P P P（134,x x x）(6)(9,0, 3,8,0)TX轴与1x的交点3lA(9,0)否否（）145,P P P（145,x x x）(7)(6,0,0,8,6)TX轴与1x的交点1lC(6,0)是是另外，A 的另外两个 n 阶子矩阵（）和（）不可逆，不能构成245,P P P135,P P P基阵。CDFGBEOA图图 3-1l3126xxl2126
11、xxl1126xx7465321100654321879x2x19由此例可以看出：（1）线性规划问题的每个基本解是原问题两个边界约束方程交点， （2）每个基本可行解对应于可行域的顶点， （3）相邻的顶点共享一个边界约束方程， （4）相邻顶点对应的基阵中只有一个基向量不同，其余两个相同。事实上，对于一般的线性规划问题（m 个约束，n 个决策变量）有类似的特性：（1）每个基本可行解对应于可行域的顶点。（2）可行域中相邻的两个顶点对应基阵中只有一个基向量不同，其余的个基向量相同。1m由于线性规划的最优解是在可行域的顶点获得，由顶点与基可行解的对应关系，我们有以下线性规划的基本定理：线性规划问题如果存在最优解，则一定存在一个基本可行解是最优解。线性规划问题如果存在最优解，则一定存在一个基本可行解是最优解。
