基本信息

---

下载

文档摘要

---

第三章线性规划

1

1、极小化型

2、约束方程为等式

3、所有的决策变量为非负值

4、约束方程的右端项系数为非负值

2

3

?非标准型LP模型转化为标准型LP模型

一、目标函数求极大值转化为极小值

例：

-z

x

z

4

一、可行解

满足线性规划模型的约束条件且

满足非负条件的解。

5

在线性规划中，约束条件均为线性等式及不

等式，满足这些条件的点的集合是凸集。

定理1:线性规划的可行域是凸集。

6

二、最优基本可行解

按列分块

7

系数矩阵A中任意m列所组成的m阶可逆子

方阵B，称为线性规划的一个基（矩阵）。

变量x，若它所对应的列P包含在基B中，

jj

则称x为基变量，否则称为非基变量。基变

j

量的全体称为一组基变量，记为

8

9

称x为线性规划的基本解。

10

11

引入松弛变量，标准化为：

x?3x?x6

?123

?

x?2x?x4

?124

12

?13-10?

系数矩阵A

?