线性规划的基本性质

1、线性规线性规划划线性规划线性规划2022-3-812022-3-82线性规划线性规划线线性性规规划划模模型型.1标准型标准型. 2解解的的概概念念和和性性质质. 4单单纯纯形形算算法法. 5图解法图解法. 32022-3-83线线性性规规划划模模型型一一.生生产产计计划划问问题题例例1利利润润最最大大？生生产产计计划划，才才能能使使所所获获安安排排千千元元。问问：该该厂厂应应如如何何、单单位位产产品品的的利利润润为为、同同，如如下下表表。耗耗费费的的加加工工时时间间各各不不相相产产品品所所需需材材料料的的数数量量和和三三种种产产品品，它它们们的的单单位位、生生产产某某工工厂厂利利用用某某种种原

2、原材材料料754CBACBA产品产品资源资源原材料原材料工时工时ABC资源总量资源总量215 . 12321001502022-3-84解：解：确确定定目目标标函函数数. 2确确定定决决策策变变量量.1。、的的产产量量分分别别为为、设设321xxxCBA，则则设设总总利利润润为为 S321754xxxS 确确定定约约束束条条件件. 310035 . 12321 xxx3 , 2 , 1,015022321 ixxxxi数数学学模模型型.4max123457Sxxx 3 , 2 , 1, 01502210035 . 12.321321ixxxxxxxtsi2022-3-85线线性性规规划划模模型

3、型：一一组组决决策策变变量量；)1(一一个个线线性性目目标标函函数数；)2(一一组组线线性性的的约约束束条条件件。)3(的的一一般般形形式式：线线性性规规划划模模型型)(LP niiixc1(max)min nixbxaxaxabxaxaxabxaxaxatsimnmnmmnnnn,2,1,0),(),(),(),(.221122222121112121112022-3-86标标准准型型二二.标标准准型型.11minniiic x nixbxaxaxabxaxaxabxaxaxatsimnmnmmnnnn,2,1,0.22112222212111212111记记为为。则则线线性性规规划划标标准

4、准型型可可记记nmijTnTmTnaAxxxxbbbbcccc )(,),(,),(,),(212121minTc x 0.xbAxts化化标标准准型型.2目目标标函函数数：)1(xcTmin:目标函数目标函数原问题原问题约约束束条条件件：)2(ininiibxaxaxai 2211)(：原问题条件原问题条件 02211iniinniniixbxxaxaxa称称为为松松弛弛变变量量。inx ininiibxaxaxaii 2211)(：原问题条件原问题条件 02211iniinniniixbxxaxaxa称称为为剩剩余余变变量量。inx 。无无非非负负约约束束，则则令令：原原问问题题 0,)(

5、iiiiiivuvuxxiii2022-3-872022-3-88为为标标准准型型。将将下下述述线线性性规规划划模模型型化化例例14321332minxxxx 无约束无约束243143214214321,0,6347223332.xxxxxxxxxxxxxxxts解解：则则令令,222vux 0,634472223332.22754317432214221543221vuxxxxxxxxvuxxvuxxxxvuxts12234min23u33xvxx2022-3-89图解法图解法三三.求求解解线线性性规规划划例例 2 0,5242.34max21212121xxxxxxtsxxz解：解：。画画

6、出出可可行行解解的的范范围围)1(1x2xoABC求求极极值值点点。利利用用等等值值线线平平移移的的方方法法)2(1243zxxz以以 为为参参数数，则则方方程程表表示示一一族族等等值值平平行行线线( (等等高高线线）。4221 xx5221 xx。顶点顶点极大值点为极大值点为B2022-3-810。中中的的目目标标函函数数改改为为将将例例例例21223xxz 1x2xoABC4221 xx5221 xx解：解：。分分析析同同例例 2。等值线：等值线：zxx 212任任一一点点。上上的的极极大大值值点点为为线线段段 AB1x2xoABC221 xx221 xx解：解：。分分析析同同例例 2。等

7、值线：等值线：zxx 2134求求解解线线性性规规划划例例 4 0,22.34max21212121xxxxxxtsxxz不不存存在在最最大大值值。2022-3-8112022-3-812结结果果：线性规划问题的解线性规划问题的解 无无最最优优解解有有最最优优解解在在顶顶点点取取到到唯唯一一最最优优解解有有无无穷穷多多最最优优解解，但但至至少少有有一一个个顶顶点点最最优优值值无无界界可可行行域域为为空空集集优解？优解？，是否在顶点中存在最，是否在顶点中存在最对一般的线性规划问题对一般的线性规划问题2022-3-813)(LPxczT max 0.xbAxts)1()2()3(的的可可行行解解。

8、称称为为）式式的的解解）、（满满足足（可可行行解解：)(),(3221LPxxxxTn 。可行域：可行域：0,| xbAxxD定理定理是是凸凸集集。线线性性规规划划问问题题的的可可行行域域 D证明：证明：。任取任取10,21 Dxx 是凸集是凸集(convex set)，如果对，如果对S中任意两中任意两 点点 x , y 和和(0,1)中的任一数中的任一数 满足满足 四、线性规划解的概念和性质四、线性规划解的概念和性质1. 线性规划解的概念线性规划解的概念2022-3-8142121)1()1(AxAxxxA bbb )1( 是凸集。是凸集。即。即所以所以DDxx 21)1( 的一个顶点。的一

9、个顶点。为为则称则称，使使。及及，。如果不存在。如果不存在为凸集，为凸集，设设顶点：顶点：SxxxxSxxSxS2121)1(10 x1x2x2022-3-815一一个个基基。问问题题或或的的为为退退化化子子阵阵，则则称称阶阶的的非非中中为为若若。秩秩为为的的系系数数矩矩阵阵为为设设基基)(,:LPABmmABmnmA (,),(,)121iiimijBPPPPjm设设基基称称为为基基向向量量. .()(,)12m nmr AmAmBP PP已已知知， 不不妨妨设设的的前前列列向向量量线线性性无无关关，则则可可取取为为基基，bAx 因为因为 11mmnAPP PPB N,.1111112112

10、2211mmnnmmnnmmmmmnnma xa xa xba xa xa xba xaxa xbB B是可逆的；是可逆的；B B的行列式的行列式0 02022-3-816解得解得令非基变量令非基变量,01 nmxxbBxxTm11),( 的的基基本本解解。为为对对应应于于基基称称解解变变量量的的取取值值得得基基，令令非非基基变变量量取取零零，求求取取定定线线性性规规划划问问题题的的基基基基本本解解：BbBbBBT)0,(,11 ()(130B b基基本本可可行行解解：满满足足条条件件的的基基本本解解称称为为基基本本可可行行解解。问问题题给给定定例例)(LP 0,2222842.22max43

11、21432143214321xxxxxxxxxxxxtsxxxxz和一个基本可行解。和一个基本可行解。求此问题的一个基本解求此问题的一个基本解x02022-3-817解：解：。系数矩阵系数矩阵 12224121A得得，则则令令非非基基变变量量取取,0222143 xxB 222822121xxxx 3731021xx可可行行解解。是是基基本本解解，但但不不是是基基本本Tx)0,0,37,310(1 得得，则则令令非非基基变变量量取取,0124132 xxB 22844141xxxx 91491641xx是是基基本本可可行行解解。Tx)914,0,0,916(2 基本解的基本解的个数？个数？20

12、22-3-818所所以以nnmmmmxPxPbxPxP 111即即1111mmmmnnP xP xPxP xbB,1我们称与基（ ）对应的变量量。变为基mxx,1mnxx与与非非基基向向量量对对应应的的为为非非基基变变量量。1BmNnxxxxxx记记BNBNBxbNxxB bB Nx11则则非基变量是自由变量非基变量是自由变量. . 基变量用非基变量表示。基变量用非基变量表示。2022-3-8线线性性规规划划解解的的性性质质. 2()线性规划问题如果有可行解，则必有基本解定理。1可行LP引理1. 线性规划的可行解为基可行解的充要条件是其正分量对应的系数列向量线性无关. 引理2. 可行解x是K的

13、顶点的充要条件是x为线性规划的基可行解。2022-3-8当这些列向量线性无关时，由引理1 ，知x为基础可行解.当向量 线性相关时，则存在一组不全 ),(, 21kppp为零的数组 k,21,使得 02211kkppp成立。证明： 设x是可行解，且前k个正分量为 若它们在矩阵A中对应的列向量为),(, 21kppp12,.kx xx（1）1122.kkx px px pb则有由(2)式右端为零，因此总可假定存在非零的 ,(否则乘以-1于（2）的两端)，总有 0i0i成立。（2）2022-3-8在上式中乘以 并与（2）相加得： 111222()()()()iiikkkxpxpxpxpb0,miniiix0jjx因而，当取时，上式中至少会有一个分量xx。也就是说，若记上式中对应的点为，则正分量 比x至少减少一个.