第一章线性规划基本性质

1、123如何合理使用有限的人力，物力和资金，如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。使得收到最好的经济效益。如何合理使用有限的人力，物力和资金，如何合理使用有限的人力，物力和资金，以达到最经济的方式，完成生产计划的要以达到最经济的方式，完成生产计划的要求。求。4 56 78910 1112比例性假定：决策变量变化引起的目标函比例性假定：决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，同数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方程左端样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。值的改变量和该变量的改变量成比例。

2、1314连续性假定：线性规划问题中的决策变量连续性假定：线性规划问题中的决策变量应取连续值。应取连续值。1516数学模型的标准型数学模型的标准型v求解目标函数的最小值求解目标函数的最小值v约束条件为等式约束约束条件为等式约束( (右端值非负）右端值非负）v变量非负变量非负171819202122若目标函数是求最大值若目标函数是求最大值 MaxS = CX 令令 S= - S, 则则 Min S= - CX23若目标函数是求最大若目标函数是求最大 值值 Max S = CX 令令 S= - S, 则则 Min S= - CX242526若约束条件右面的某一常数项若约束条件右面的某一常数项 bi0

3、这时只要在这时只要在bi相对应的约束方程两边乘上相对应的约束方程两边乘上-1。27若约束条件右面的某一常数项若约束条件右面的某一常数项 bi=0 令令xj= xj- xj”（可正可负）（可正可负）28:2930313233（1）满足约束条件的变量的值，称）满足约束条件的变量的值，称为可行解。为可行解。3435x2504030201010203040 x136x2504030201010203040 x137x2504030201010203040 x12x1+x2 504x1+3x2 12038x2504030201010203040 x1O（0，0）Q1（25，0）Q2（15，20）Q3（0

4、，40）39x2504030201010203040 x140 x2504030201010203040 x141x2504030201010203040 x1Q2（15，20）4243满足约束条件的可行域一般都满足约束条件的可行域一般都构成凸多边形。这一事实可以构成凸多边形。这一事实可以推广到更多变量的场合。推广到更多变量的场合。44；45最优解是唯一解最优解是唯一解；46x2504030201010203040 x147x2504030201010203040 x1Q1（25，0）Q2（15，20）4849x2504030201010203040 x150515253545556 满足约束

5、条件（满足约束条件（1-10）的）的X，称为，称为 线性规划问题的解。线性规划问题的解。57 满足约束条件（满足约束条件（1-10）的）的X，称为，称为 线性规划问题的解。线性规划问题的解。 满足约束条件（满足约束条件（1-10）与（）与（1-11） 的的X，称为线性规划的问题可行解。，称为线性规划的问题可行解。5859 设设r(A)=m,并且并且B是是A的的m 阶非奇异阶非奇异 的子矩阵（的子矩阵（det(B)0),则称矩阵则称矩阵 B为线性规划问题的一个基。为线性规划问题的一个基。60 设设r(A)=m,并且并且B是是A的的m 阶非奇异阶非奇异 的子矩阵（的子矩阵（det(B)0),则称矩

6、阵则称矩阵 B为线性规划问题的一个基。为线性规划问题的一个基。 矩阵矩阵B=（P1，P2.Pm) ，其列向量，其列向量 Pj称为对应基称为对应基B的基向量。的基向量。6162 对于某一特定的基对于某一特定的基B，非基变量取，非基变量取 0值的解，称为基本解。值的解，称为基本解。63 对于某一特定的基对于某一特定的基B，非基变量取，非基变量取 0值的解，称为基本解。值的解，称为基本解。 满足非负约束条件的基本解，称满足非负约束条件的基本解，称 为基本可行解。为基本可行解。64656667686970717273747576 7778X7980818283 。848586 若若87 若若ZCXAX

7、bXmin0 证：证：XD XDXX(1)(2)(1)(2), AXb AXbXX(1)(2)(1)(2),0,0 (1)(2)(1)(2)(1-)01X, XX= X+X,令令线线段段上上任任意意一一点点为为 AX=AX+X(1)(2)1- 则则 = AX+AXAX(1)(2)(2)-= bX0 且且 ，XDD 即即 ， 由由定定义义， 为为凸凸集集。88 89 证：证：必必要要性性XX为为基基本本可可行行解解的的正正分分量量是是各各个个基基变变量量 基基变变量量对对应应基基向向量量 线线性性无无关关90 证：证：充充分分性性12kXkP ,PP,.不不妨妨设设可可行行解解 的的正正分分量量

8、为为前前 个个， 对对应应的的线线性性无无关关列列向向量量为为kAm 则则 的的秩秩 ，km 如如 ， 由由基基的的定定义义可可得得结结论论；kmn-km-k如如 ， 必必可可从从其其余余的的个个列列向向量量中中取取出出个个，构构成成最最大大线线性性无无关关组组，即即为为一一组组基基，对对应应的的解解为为基基本本可可行行解解。91 92证：证：TmXx xxD12(,0,0) 假假设设 是是一一个个基基本本可可行行解解，但但不不是是可可行行域域 的的顶顶点点，YD,ZD, YZ ,X= Y+ 1Z( -) 则则 （） 使使得得，0 01 1YZn-m由由上上式式， 的的后后个个分分量量为为0

9、0，mmjjjjjjP ybP zb11, mjjjjP yz10, 相相减减，（）jjyz0, 不不全全为为 ，由由线线性性相相关关定定义义可可知知X,正正分分量量对对应应的的系系数数列列向向量量线线性性相相关关X1,由由引引理理不不是是基基本本可可行行解解， 矛矛盾盾！93证：证：XD假假设设 是是可可行行域域 的的顶顶点点，但但不不是是一一个个基基本本可可行行解解，kjjjP xb1, kkjjjjjjjjP xbP xb110, 有有， 得得（）（）X=Y+ZY, Z,2211,00 则则且且 充充分分小小时时，有有X不不是是可可行行域域的的顶顶点点， 矛矛盾盾！XkX设设 的的前前

10、个个分分量量为为正正，其其余余为为0 0，是是可可行行解解，kjjjjP10, 由由引引理理1 1， 一一组组不不全全为为0 0的的数数，TkkTkkY = xxx Zxxx11221122(,(, 令令) ), ,( () ), , （）, ,0 0, ,0 0) ), ,( () ), , （）, ,0 0, ,0 0X即即可可用用可可行行域域内内不不同同两两点点的的凸凸组组合合表表示示，949596979899100101 102 证：证：2kX,X,XXZ(1)( )( )(0) 设设是是可可行行域域的的顶顶点点，且且最最优优解解在在可可行行点点处处达达到到最最优优值值，ZCX(0) = =k2kkiiiXXXXX(0)(0)(1)( )( )12101 由由引引理理2 2，假假设设不不是是可可行行域域的的顶顶点点则则，