第一章 线性规划与单纯形法(3)

maxz?c1x1?c2x2??cnxn?a11x1?a12xx???a1nxn?b1?ax?ax???ax?b21122x2nn2? ?s..t???ax?ax???ax?bmnnm?m11m2xx1,x2,?,xn?0??类似地，用和式的简写形式为：

maxz??cjxjj?1n ?nax?b(i?1,2,?,m)i??ijjs..t?j?1?x?0(j?1,2,?,m)j?用矩阵的形式来表示可写为：

maxz?CX

?AX?bs..t??X?0T其中 C?(c1,c2,?,cn)；X??x1,x2,?,xn?；b??b1,b2,?,bn?；

?a11??a21 A?????a?m1a12a22?am2?a1n???a2n? ????amn??T标准形式的线性规划模型中，目标函数为求最大值，约束条件全部为等式，约束条件右端常数项bi全部为非负值，决策变量xj的取值为非负。对不符合标准形式的线性规划问题，可分别通过下列方法化为标准形式。

1．若目标函数为min型，即

minz?c1x1?c2x2??cnxn

令z???z，于是求minz等价于求max(?z)，即maxz?，故目标函数可化为：

maxz???c1x1?c2x2???cnxn

2．若约束条件为“?”时，如3x1?2x2?18，令x3?18?3x1?2x2，即3x1?2x2?x3?18。由于3x1?2x2?18，所以x3?0。称x3为松弛变量，所表示的是资源的未充分使用量，对目标函数值不会产生影响，故目标函数不变。也就是说x3在目标函数中的系数为0。显然原约束3x1?2x2?18与这组约束条件3x1?2x2?x3?18和x3?0完全等价。

3．若约束条件为“?”，如x1?2x2?12，令x3?x1?2x2?12，即x1?2x2?x3?12。由于x1?2x2?12，所以x3?0。称x3为剩余变量，所表示的是超额部分，同样对目标函

- 15 -

数不会产生影响，故目标函数也不变，即该剩余变量在目标函数中的系数也为0。同样的原约束条件x1?2x2?12与这组约束条件x1?2x2?x3?12和x3?0完全等价。

4．若约束条件为等式，但右端项bi为负值，则在等式两边同时乘以-1即可。 5．若决策变量的非负约束不满足，可分以下两种情况分别进行转化：

（1）当xj?0时，可令x?j??xj，则显然xj?0等价于x?j?0。但注意在整个模型其他位置上也都要同时将xj换成它的相反数x?j；

????? （2）当xj的取值无约束时，可令xj?x?j?xj，且xj,xj?0。同样所有xj都要用xj?x?j?x?j?代换。

例1.5 将下述线性规划模型化为标准形式。

minz?x1?2x2?3x3??2x1?x2?x3?9??3x?x?2x?4 ?123s.t.??3x1?2x2?3x3??6??x1?0,x2?0,x3无约束解：令z???z，目标函数化为

maxz???x1?2x2?3x3

令松弛变量x4?9?2x1?x2?x3，第一个约束条件化为

?2x1?x2?x3?x4?9,x4?0

令剩余变量x5??3x1?x2?2x3?4，则第二个约束条件化为

?3x1?x2?2x3?x5?4,x5?0

第三个约束条件两边同时乘以-1，即化为

?3x1?2x2?3x3?6

经过以上四步，模型化为

maxz???x1?2x2?3x3?2x1?x2?x3?x4?9?? ?3x1?x2?2x3?x5?4?s.t.??3x1?2x2?3x3?6???x1?0,x2?0,x3无约束,x4?0,x5?0???x1，x3?x3??x3??代入得标准化的模型为 最后，令x1??3x3??maxz??x?1?2x2?3x3??x2?x3??x3???x4?92x1????x2?2x3??2x3???x5?4 3x1?s..t???2x2?3x3??3x3???63x1????0,x2?0,x3??0,x3???0,x4?0,x5?0?x1通过线性规划问题的标准化过程，任何一个线性规划问题都可以转化为一个标准形式，因此下面在研究一般求解方法时，只需考虑标准形的线性规划问题的求解就可以了。

- 16 -

第四节 线性规划问题解的性质

一、线性规划问题解的概念

本章第二节已介绍了线性规划问题的可行解和最优解的概念，在讨论求解线性规划问题的一般方法——单纯形法前，仍有必要进一步了解线性规划的有关概念。

设线性规划标准型为

maxz?CX?AX?b

s..t??X?0式中A是线性规划问题约束方程组的m?n阶系数矩阵，一般来说n?m且A的秩为。显然A中至少有一个m?m阶子矩阵B，使得B满m（有兴趣的同学可以思考一下原因）秩。

基：A中的m?m阶子矩阵B满足r(B)?m，则称B是线性规划的一个基（或基矩阵）。

m当m?n时，基矩阵唯一，当m?n时，基矩阵可能有多个，但不超过Cn个。

例1.6 已知线性规划

maxz?2x1?3x2?x3?2x4?x1?x2?2x3?x4?7 ?s..t?x1?2x2?4x3?x4?13?x1,x2,x3,x4?0?求所有基矩阵。

解：约束方程组的系数矩阵为

?1121?A???

124?1??2易知r(A)?2，2阶子矩阵有C4?6个，其中第2列与第3列构成的2阶矩阵不是一

个基，基矩阵共有5个，即

?11??12??11?B1??,B?,B??2??3???12??14??1?1?

1121????B4??,B??5???2?1??4?1?基变量：B是线性规划的一个基，则B中每个列向量所对应的决策变量称为基变量，其余决策变量称为非基变量。对应于一个基B，共有m个基变量，n?m个非基变量。例1.6中基B1所对应的基变量是x1,x2，非基变量是x3,x4。

基本解：对某一确定的基B，令所有非基变量为0，解约束方程组AX?b可解出m个基变量的唯一解，加上非基变量取0值，就得到了n个决策变量的一组具体取值解XB，称

XB为基B所对应的基本解。

基本可行解：基B所对应的基本解XB一定满足约束方程组AX?b，若XB还满足非

- 17 -

负约束X?0，则称XB为线性规划问题的一个基本可行解。

可行基：基本可行解XB所对应的基B称为可行基。

基本最优解：若基本可行解XB是最优解，则称XB为基本最优解。

在例1.6中，对B2来说，x1,x3是基变量，x2,x4是非基变量，令x2?x4?0，代入方程有

?x1?2x3?7 ??x1?4x3?13因B2满秩，B2?0，由克莱姆法则知，x1,x3有唯一解x1?1,x2?3，则基本解为

X(2)?(1,0,3,0)T

对B3来说，x1,x4是基变量，x2,x3是非基变量，令x2?x3?0，代入方程解得x1?10,x4??3，基本解为

X(3)?(10,0,0,?3)T

(3)(3)(2)由于X?0，故它是基本可行解，B2是可行基。在X中x4?0，因此X不是可

行解，也就不是基本可行解。

关于线性规划各种解的相互关系可用图1.6来表示。

图1.6

例1.7 已知线性规划

maxz?2x1?3x2?x3?2x4?x1?x2?x3?x4?6 ?s..t?x1?2x2?x3?x4?12?x,x,x,x?01234?则A?(2,0,4,0)，B?(6,0,3,3)，C?(3,2,3,2)，D?(0,6,0,0)中哪一个是基本可行解?

解：易知，A?(2,0,4,0)，B?TT都不满足约束条件，不是可行解。(6,0,3,3)TTTTC?(3,2,3,2)T，D?(0,6,0,0)T满足约束条件，是可行解。但因为约束方程组的系数矩阵

T秩为2，基变量只有两个，即基本解中非零元素至多两个，故C?(3,2,3,2)不是基本可行

T解。对于D?(0,6,0,0)可以取x1,x2为基变量，其所对应的系数矩阵为

- 18 -

?11??? ?12?

是一个满秩方阵，故可以确认D?(0,6,0,0)T为基本可行解。

二、线性规划解的性质 1．凸集和极点的概念

凸集：设S是n维欧氏空间一个点集，若连接S中任意两点x(1),x(2)的线段上的所有点

?x(1)?(1??)x(2)仍在S中，则S为凸集。

图1.7

圆、球体、立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹陷的部分，内部没有空洞。如图1.7中的（a）（b）是凸集，而（c）不是凸集。从（c）可见，任何两个凸集的并集不一定是凸集，但任何两个凸集的交集一定是凸集。

极点：设S是凸集，若S中的点x不能成为S中任何线段的内点，则称x为S的极点。凸多边形的顶点就是极点。 2.线性规划解的性质

定理1.1 若线性规划的可行域S非空，则S为凸集。即连接任意两个可行解的线段上的点仍为可行解。

定理1.2 线性规划的可行域S中的点X是极点的充要条件是X为基本可行解。简单的说，凸多边形的顶点就是基本可行解

定理1.3 若线性规划有最优解，则最优解一定可在可行域S的某个极点上得到。 定理1.1描述了可行域的特征。定理1.2描述了可行域的极点与基本可行解的对应关系，但注意，它们并非一一对应，可能多个基本可行解对应于一个极点。定理1.3描述了最优解在可行域中的位置，若最优解唯一，则最优解一定是在个极点上达到；若具有无穷多最优解，则最优解是某些极点的凸组合。

若线性规划的可行域非空且有界，则一定有最优解；若可行域无界，则线性规划可能有最优解，也可能没有最优解。若线性规划具有无界解，则可行域一定无界。

定理1.2和定理1.3还启示我们，求最优解不是在无限个可行解中去找，而是在有限个基本可行解中去求得。从理论上说，用枚举法可求出所有基本可行解，再代入目标函数中比较得到最优解。当然这种枚举法求最优解的前提是，线性规划有最优解。

- 19 -

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第一章 线性规划与单纯形法(3)在线全文阅读。