1-1线性规划的概念

李鹏翔 郭菊娥《运筹学》精品课小组成员管理学院 管理科学系(Office: 756, 429) Email:lipengx@http://www.77cn.com.cn

主 讲 教 师

Email:guojue@http://www.77cn.com.cn

《运筹学》精品课建设网站：http://www.77cn.com.cn 进展：2003年7月被评为校精品课程 2004年9月评为省精品课程 传承教学风格，保持精品课水准

精品课小组负责人：徐 渝 教授 杨民助 副教授 郭菊娥 教授

线 性 规 划 内 容 框 架

实际问题

(1) LP 数学模型 可行解(重点) 基本解(难点) 基本概念 ( 2 ) LP 各种解的概念 基本可行解(重点) 最优解 基本最优解 图解法 大M法 法、人工变量法 ) 基本方法 单纯形法(原始单纯形 两阶段法 对偶单纯形法 ?条件 LP 模型 (求解) 前提？步骤？ 修正单纯形法 对偶理论 进一步讨论 灵敏度分析 参数规划 算法复杂性问题 哈奇扬算法、 karmarkar 算法 经济管理方面的典型问 整数 LP 运输问题 特殊 LP 多目标 LP FuzzyLP 题

第一章、 线性规划1.1 线性规划的概念一、线性规划问题的导出

1.(引例) 配比问题——用浓度为45%和92%的硫酸配置 100吨浓度为80%的硫酸。

取45%和92%的硫酸分别为x1和x2吨, 则有：

x 1 x 2 100 0 . 45 x 1 0 . 92 x 2 0 . 8 100 求解二元一次方程组得解。

目的相同，但有5种不同浓度的硫 酸可选(30%,45%,73%,85%, 92%)会出现什么情况？ 取这5种硫酸分别为x1 、x2 、x3 、x4 、 x5 吨, 则有： x 1 x 2 x 3 x 4 x 5 100 0 . 3 x 1 0 . 45 x 2 0 . 73 x 3 0 . 85 x 4 0 . 92 x 5 0 . 8 100

有多少种配比方案？为什么？ 何为最好？

5种硫酸价格分别为：400,700,1400, 1900,2500元/吨，则有：M in Z 400 x1 700 x 2 1400 x 3 1900 x 4 2500 x 5 x1 x 2 x 3 x 4 x 5 100 s .t . 0.3 x1 0.45 x 2 0.73 x 3 0.85 x 4 0.92 x 5 0.8 100 x 0, j 1, 2, , 5 j

2. 生产计划问题：生产单位 产品 产品所需资源 资 源

A

B

C

每天可利用 资源量

工时(单位) 材料(吨) 产品利润 (元/吨)

1 1

1 4

1 7

3 9

2000 3000 1000

如何制定生产计划，使三种产品总 利润最大？

问题讨论

何为生产计划？

(设定决策变量)

总利润如何描述？(目标函数) 还要考虑什么因素？(约束条件)

有什么需要注意的地方(技巧)? 最终得到的数学模型是什么？

M a x

Z 2 x1 3 x 2 x 3 x1 x 2 x 3 3 s .t . x1 4 x 2 7 x 3 9 x 0 , j 1, 2 , 3 j

二、线性规划的定义和数学描述(模型)1.定义：对于求取一组变量xj (j =1,2,......,n), 使之既满足线性约束条件，又使具有线性表达 式的目标函数取得极大值或极小值的一类最优 化问题称为线性规划问题，简称线性规划。

2.配比问题和生产计划问题的线性规 划模型的特点： 用一组未知变量表示要求的方案，这组 未知变量称为决策变量； 存在一定的限制条件，且为线性表达式； 有一个目标要求(最大化，当然也可以 是最小化),目标表示为未知变量的线 性表达式，称之为目标函数； 对决策变量有非负要求。

3.LP的数学描述(数学模型):(1)一般形式Max ( 或 Min ) Z c 1 x 1 c 2 x 2 c n x n a 11 x 1 a 12 x 2 a 1 n x n ( , ) b1 a 21 x 1 a 22 x 2 a 2 n x n ( , ) b 2 s .t . a x a x a x ( , )b m2 2 mn n m m1 1 x1 , x 2 , , x n 0

(2)紧缩形式Max ( 或 Min ) Z n

cj 1

n

j

xj

i 1, 2 , m a ij x j ( , ) b i s .t . j 1 xj 0 j 1, 2 , n

(3)矩阵形式Max ( 或 Min ) Z CX AX ( , ) b s .t . X 0

其中 :C ( c1 , c 2 , c n )

X ( x1 , x 2 , x n )

b ( b1 , b 2 , , b m )

T

a 11 a 21 A a m1

a 12 a 22 am 2

a1 n a2n a mn

(4)向量—矩阵形式：Max ( 或 Min ) Z CX n Pj x j ( , )b s .t . j 1 X 0 其中：

P j ( a 1 j , a 2 j , , a mj ) , j 1, 2 , , nT

A ( P1 , P2 , , Pn )

课堂练习1-1(1)P43 习题1 :1).填空(1)

加深理解线性规划的定义(2)复习线性规划定义及数学描述 以《生产计划问题》为例，写出线性规划的4 种模型 M a x Z 2 x1 3 x 2 x 3 x1 x 2 x 3 3 s .t . x1 4 x 2 7 x 3 9 x 0 , j 1, 2 , 3 j

三、LP的标准型：1、LP标准型的概念

(1)什么是LP的标准型？(2)为什么要用标准型？

(3)LP标准型的特点： 目标函数约定是极大化Max(或极小化Min);

约束条件均用等式表示; 决策变量限于取非负值; 右端常数均为非负值 ;