第一章 线性规划与单纯形法11

c1c2?cn称为价值系数 b1b2?bn称为资源拥有量

aij(i?1?m,j?1?n)称为技术系数或工艺系数，表示变量xj取值为一个单位时所消耗或含有的第i种资源的数量。

上述模型的简写形式为：

max(min)z??cjxjj?1n

i?1?mj?1,2,?n s.t.

?n??aijxj?(?,?)bj?j?1?x?0?j

用向量表示时，上述模型可写为：

z?CX max(min)?n??Pjxj?(?,?)b?j?1?X?0s.t.?

TTTP?(aa?a)C?(cc?c);X?(xx?x)j1j2jnj12n12n其中；；b?(b1b2?bn);

用矩阵和向量表示为：

z?CX max(min)?AX?(??)b? s.t.?X?0?a11?a?21????an1a12a22?an2

其中A=

?a1n??a2n???????ann? A为约束方程组（约束条件）的系数矩阵。

变量xj的取值一般为非负，即xj?0；从数学意义上可以有xj?0。又如果变量xj表示第i种产品本期内产量相对于前期产量的增加值，则xj的取值范围为（??,??），称xj取值不受约束，或xj无约束。

二、线性规划问题的标准形式。

标准形式：

maxz??cjxjj?1n

(i?1?m)(j?1,2,?n) s.t.

?n??aijxj?bj?j?1?x?0?j

（注意：有些书上规定是求极小值），约束条件全为等式，约束条件右端常数项bj全为非负值（bj?0），变量xj的取值全为非负值。

对不符合标准形式（或称非标准形式）的线性规划问题，可分别通过下列方法化为标准形式。

1、目标函数为求极小值，即为

max(?z)，令z'??z，即化为

minz?CX??cjxjj?1n因为求minz就等价于求

maxz???cjxj'j?1n

2、若某个约束方程的右端项bj?0，则在此等式或不等式两端同乘以（－1），则等式或不等式的右端项必大于零。

3、若约束条件是小于等于型，则在该约束条件不等式左边加上一个新变量—称为松弛变量，将不等式改为等式。

如：x1?2x2?3x3?8?x1?2x2?3x3?x4?8

4、若约束条件是大于等于型，，则在该约束条件不等式左边加上一个新变量—称为剩余变量，将不等式改为等式。

例：2x1?3x2?4x3?8?2x1?3x2?4x3?x4?8 一般地，

ai1x1?ai2x2??ainxn?bi?ai1x1?ai2x2??ainxn?xn?i?bixn?i?0

5、若决策变量xk无非负要求，即xk可正可负，则可令两个新的变量：

??xk??，在原有的数学模型中，xk均用(xk??xk?)来代替。x??0,x???0，作xk?xk??0,xk???0。 而在非负约束中增加xk6、对x?0的情况，令x???x则x??0。 例：将下述线性规划化为标准形式。

minz?x1?2x2?x3??2x1?x2?x3?4??3x?x?2x?4?123s.t.??4x1?2x2?3x3??6? ?x1?0,x2?0,x3无约束

解：由于决策变量x3无约束。故令x3＝x4?x5,(x4,x5?0)

minz?x1?2x2?x4?x5??2x1?x2?x4?x5?4??3x?x?2x?2x?4?1245?s.t.??4x1?2x2?3x4?3x5??6??x1?0,x2?0,x4,x5?0 maxz???x1?2x2?x4?x5??2x1?x2?x4?x5?x6?4??3x?x?2x?2x?x?4?12457?s.t.???4x1?2x2?3x4?3x5??6???x1?0,x2?0,x4,x5,x6,x7?0

maxz??x8?2x2?x4?x5?2x8?x2?x4?x5?x6?4?3x?x?2x?2x?x?4?82457?s.t.??4x8?2x2?3x4?3x5??6??x2,x4,x5,x6,x7,x8?0

第二节 图解法