资源预览内容
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
第9页 / 共9页
亲,该文档总共9页全部预览完了,如果喜欢就下载吧!
资源描述
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 xx (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) 目标函数的转化:若原问题的目标函数是求最小化,即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 代入原问题,即在原问题中将用两个非负变量之差代替。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 维列向量;为矩阵。()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.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定,我们可以将系数矩阵写成分块的形式:A( ,)AB N其中,表示非基变量对应列向量构成的子矩阵。N将基变量组成的向量记为,非基变量组成的向量记为, 12(,) mT BjjjXxxxNX则X 也可以写成分块形式:BNXXX因此,约束方程组变为AXbBNBXNXb由于可逆,则存在,将左乘以上式的两边得B1B1B11 BNXB NXB b移项后得 11 BNXB bB NX事实上,对约束方程组,可以看作一组独立变量,它可以取任意的AXbNX7值,令,则,此时约束方程组有一个特殊形式的解0NX1 BXB bAXb10BNXB bXX称为线性规划的基本解基本解。由以上讨论可以看出,线性规划的基本解实际上是在约束方程组中将非基变量看作独立的自由变量并令其取值为 0 后,解方程组得出的解;当基AXb确定时,基本解也唯一确定了。由于基可以是中任意 m 阶的可逆子矩阵,BBA即它的列是从 A 中 n 列中选出的线性无关的 m 列,其选法最多有,故基的个数和基本解的个数均不会超过个。! !()!m nnCm nmm nC基本解满足约束方程,但不一定是可行解。因为,它不10B bXAXb一定满足非负约束。我们把满足非负约束的基本解,即的基0X 10BXB b本解称为基本可行解基本可行解或基可行解基可行解,此时对应的基 B 称为可行基可行基。同10B bX理,线性规划问题基可行解的数目不超过个。m nC下面我们给出例 2 中基阵、基本解、基本可行解以及可行区域顶点之间的对应关系,如表 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)是是()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-1l3126xxl2126xxl1126xx7465321100654321879x2x19由此例可以看出:(1)线性规划问题的每个基本解是原问题两个边界约束方程交点, (2)每个基本可行解对应于可行域的顶点, (3)相邻的顶点共享一个边界约束方程, (4)相邻顶点对应的基阵中只有一个基向量不同,其余两个相同。事实上,对于一般的线性规划问题(m 个约束,n 个决策变量)有类似的特性:(1)每个基本可行解对应于可行域的顶点。(2)可行域中相邻的两个顶点对应基阵中只有一个基向量不同,其余的个基向量相同。1m由于线性规划的最优解是在可行域的顶点获得,由顶点与基可行解的对应关系,我们有以下线性规划的基本定理:线性规划问题如果存在最优解,则一定存在一个基本可行解是最优解。线性规划问题如果存在最优解,则一定存在一个基本可行解是最优解。
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号