运筹学讲义

?x1?x2?5??x1?x2?6 ?x,x?0?12可行域D=?，建模有错误。

四。有图解法得到的启示

1。若可行域非空，则可行域为凸集。

定义：如果集合C中任意两个点X1，X2，其连线上的所有点也都在集合C中，这样的集

图2.1

图2.2

图2.3

图2.4

合称之为凸集。

其中图2.1，2.2，2.4是凸集，图2.3不是。关于两点之间的连线，数学上是这样描述的：

?X1+（1-?）X2 （0

让?从0向1移动，则直线上的点就从顶点X2移动到顶点X1。

2。若LP有最优解，则最优解一定在凸集的顶点处取得。若在两个顶点处取得最优值，则在其连线上所有点都是最优值。

§3 单纯型法原理

一．LP问题的标准形式及其解的概念： 1． LP问题的的标准形式： （1） 一般形式

max(min)z?c1x1?c2x2???cnxn

5

?a11x1?a12x2??ax?ax?211222???s.t???ax?ax?m22?m11?x2,?x1, (2) ∑记号形式 max(min)z?n?a1nxn?b1?a2nxn???amnxn?xn?0?b2?? ?bm?cxjj?1j

?n??aijxjs.t?j?1?xj?0?（3）向量形式

?bj(i?1,?m)(j?1,?n)

max(min)z?CX

?n?Pjxjs.t??j?1??X?0?b

?a1j??x1??b1???????a?2j??x2??b2?b?其中C?(c1,c2,?cn)，X???，Pj??，??? ??????????x??b??a??n??m??mj?（4）矩阵形式

max(min)z?CX

s.t ??AX?b?X?0?a11??a21A=????a?m1a12a22?am2?a1n??b1??x1??????b?a2n??2??x2?，b???，X???

???????????b??x??amn??m??n??2. 将非标准化为标准形式

（1）若目标函数为求最小化：minZ=CX 令z?= -z,即z?=-CX，此时maxz?等价于minZ. 从右图可看出，maxz?=-CX与minZ=CX,就最优解来说，X相同。

（2）若约束条件是≤，则在该约束条件不等式的左边加上一个新变量----称为松弛变量，将不等式改为等式。

??(x) -?(x) O X· ?(x) X

6

例：2x1+3x2≤8?2x1+3x2+x3=8。

（3） 若约束条件是≥型，则在该约束条件不等式左边减去一个新变量——称为剩余变量，将不等式改为等式。

例：2x1-3x2-4x3≥5?2x1-3x2-4x3-x4=5

（4）若某个约束方程的右端项bi<0，则在约束方程两端乘以（-1）,不等好改变方向。 （5）若决策变量xk无非负要求，则可另两个新变量xk≥0，xk≥0，作xk=xk-xk，且在原数学模型中，xk均用（xk-xk）来代替，而在非负约束中增加xk≥0，xk≥0。 （6）对xk≤0的情况，令xk=-xk，显然xk≥0。 例3/P15 将下述线性规划化为标准形 Minz=x1+2x2+3x3

????????????2x1???3x??1 s.t ???4x1??x1?0,

x2x22x2x2?0,??x3?9?2x3?3x3?4

??6x3取值无约束

解：上述问题中令z?= -z, x1=-x1，x3=x3-x3，其中x3≥0，x3≥0，按上述规则，该问题的标准形式为：

Maxz?= x1-2x2-3x3+3x3+0x4+0x5

????????2x?x?x??x??x?92334??1?3x1?x2?2x3??2x3??x5?4 s.t ?

????4x1?2x2?3x3?3x3?6????x,x,x123,x3,x4,x5?0?3.线性规划问题解的概念： maxz??cxjj?1nj （2.1）

?n??aijxjs.t?j?1?xj?0??bj(i?1,?m)(j?1,?n) （2.2）

可行解： 满足上述约束条件（2.2）的解X?(x1,x2,?xn)，称为线性规划问题的可

T 7

行解。全部可行解的集合称为可行域。

最优解：使目标函数（2.1）达到最大值的可行解称为最优解。

基：设A?(aij)m?n为约束方程组（2.2）得系数矩阵，设（n?m）设其秩为m,B是矩阵A的一个m×m阶的满秩子矩阵，称B是LP问题的一个基。不失一般性，设

?a11?a1m??? B???????(P1,?Pm)

?a??m1?amm?B中的每一列向量Pj（j?1,?m)称为基向量。与基向量对应的变量Pj对应的变量xj称为基变量。LP中除基变量以外的变量称为非基变量。

基解：在约束方程（2.2）中令非基变量=0的解称为LP的基解。 基可行解：满足变量非负约束条件的基解称为基可行解。 可行基：对应于基可行解的基称为可行基。

例4/P19 找出下述LP问题的全部基解，指出其中的基可行解，并确定最优解。

Maxz=2x1+3x2+x3

?x1?x?1 s.t????x1~5?x3?2x2x2?0?x4?x5?5?10 ?4解：首先x1，x2，x3是基，对应的基解为 x3=5-x1 x4=10-x1-2x2 x5=4-x2

令x1=x2=x3=0，得x3=5，x4=10，x5=4。为基可行解。

同理，可求出其它基解及基可行解。 4。单纯形迭代原理：

前面讲过，若LP问题有最优解的话，定在可行域的某顶点处达到，又，一个顶点对应

m一个基本可行解，一个自然的想法是：找出所有的基本可行解。因基本可行解的个数?cn，m通过“枚举法”，从理论上讲总能找出所有的基本可行解。而事实上随着m，n的增大，cn迅速增大，致使此路行不通。

我们换一种思路：若从某一基本可行解（今后称之为初始基本可行解）出发，每次总是寻找比上一个更“好”的基本可行解，逐步改善，直至最优。这需要解决以下三个问题：

（1） 如何找到一个初速的基本可行解。

8