2.1+线性规划问题及其数学模型

次数。 • 目标：
电视台的目标是使电视观众最多。用z表示电视台的电
视观众数，则
max
• 约束：
z 60 x1 20 x2
1、广告公司规定每周至少有3.5分钟广告；
0.5 x1 1 x2 3.5
2、电视台每周只能为宣传片提供不多于16分钟的节目时间；
4 x1 2 x2 16
§2.1 线性规划问题及其数学模型
Page 16
约束条件
Constraints
怎样辨别一个模型是线性规划模型？ 其特征是： （1）问题的目标函数是多个决策变量的线性函数， 通常是求最大值或最小值； （2）问题的约束条件是一组多个决策变量的线性不 等式或等式。
§2.1 线性规划问题及其数学模型
3. 线性规划数学模型的一般形式
Page 17
每周应播映两套宣传片各多少次，才能使得收视观众
最多？
§2.1 线性规划问题及其数学模型
Page 12
播放片甲 片集时间 (min) 广告时间 (min) 收视观众 (万 )
播放片乙
节目要求
3.5
1
16
0.5 1
3.5
60
20
§2.1 线性规划问题及其数学模型
•
Page 13
x2 解：设 x1 ,分别表示电视台每周播放宣传片甲、乙的
§2.1 线性规划问题及其数学模型
约束方程的转换：由不等式转换为等式。
Page 30
a x
j 1 ij
n
j
bi
a x
j 1 ij
n
j
xn i bi
xn i 0 称为松弛变量
ij j
a x
j 1
n
bi
a x
j 1 ij
n
j
xn i bi
称为剩余变量
xn i 0
线性规划的开创者---康托洛维奇和丹捷格Page 4
1939年著名数理经济学者康托洛维奇发表了《生产组织和 计划中的数学方法》这一运筹学的先驱性名著，其中已提 到类似线性规划的模型和“解乘数求解法”。但是他的工 作直到1960年的《最佳资源利用的经济计算》一书出版后， 才得到重视。1975年，康托洛维奇与T . C . Koopmans 一起获得了诺贝尔经济学奖。 1947年G . B. Dantzig 在研究美国空军军事规划时提出了 线性规划的模型和单纯形解法，并很快引起美国著名经济 学家Koopmans的注意。Koopmans为此呼吁当时年轻
§2.1 线性规划问题及其数学模型
例2.3 将例2.1的数学模型化为标准形式的线性规划。
Page 31
max z 2 x1 3 x2 x1 2 x2 8 16 4 x1 4 x2 12 x1 , x2 0
2 z x2 x1 4 4 表示一簇平行线
§2.1 线性规划问题及其数学模型
（3）无界解
max z x1 x2 2 x1 x2 4 x1 x2 2 x ,x 0 1 2
Page 23
x2 x1 z 表示一簇平行线
§2.1 线性规划问题及其数学模型
矩阵形式： max Z CX AX B X 0
a11 A am 1 a1 n (P , P , 1 2 amn
b1 B bm
C (c1 , c2 , 其中：
x1 a1 j X Pj a mj xn
s.t.
Page 10
§2.1 线性规划问题及其数学模型
例2.2 央视为改版后的《非常6＋1》栏目播放两套
Page 11
宣传片．其中宣传片甲播映时间为3分30秒，广告时 间为30秒，收视观众为60万，宣传片乙播映时间为1 分钟，广告时间为1分钟，收视观众为20万．广告公 司规定每周至少有3.5分钟广告，而电视台每周只能为 该栏目宣传片提供不多于16分钟的节目时间．电视台
• 2. 1.1 问题的提出
1. 线性规划举例
Page 7
生产和经营管理中经常提出如何合理安排，使人力、物力等各 种资源得到充分利用，获得最大的效益，这就是规划问题。 线性规划通常解决下列两类问题： （1）当任务或目标确定后，如何统筹兼顾，合理安排，用 最少的资源 （如资金、设备、原标材料、人工、时间等） 去完成确定的任务或目标. （2）在一定的资源条件限制下，如何组织安排生产获得最 好的经济效益（如产品量最多 、利润最大).
,cn )
b1 B bm
Pn )
0 0 0
x1 X xn
§2.1 线性规划问题及其数学模型
（2）如何化标准形式 目标函数的转换
n
Page 29
j 1 即令 z z 则可将目标函数乘以(-1)，可化为求极大值问题。
Page 19
一般方法
§2.1 线性规划问题及其数学模型
（1）唯一最优解
max z 2 x1 3 x2
x1 2 x2 8 16 4 x1 4 x2 12 x1 , x2 0
Page 20
s.t.
§2.1 线性规划问题及其数学模型
（1）唯一最优解
存在可以量化的约束条件，这些约束条件可以用一组线性 等式或线性不等式来表示; 都有达到某一目标的要求，可用决策变量的线性函数来表 示。按问题的要求不同，要求实现最大化或最小化。
§2.1 线性规划问题及其数学模型
2. 线性规划的数学模型由三个要素构成 决策变量 目标函数 Decision variables Objective function
c n xn
a11 x1 a12 x2
约束条件： a x a x m1 1 m2 2
a1n xn b1 amn xn bm
x1 0
xn 0
简写为： max Z n c x j j
j 1
n a ij x j bi s.t j 1 i 1,2, , m x j 0, j 1,2, , n
的经济学家要关注线性规划。
Chapter2 线性规划与单纯形法
本章主要内容：
§2.1 线性规划问题及其数学模型 §2.2 线性规划问题的几何意义
§2.3 单纯形法
§2.4 单纯形法的计算步骤
§2.5 单纯形法的进一步讨论
§2.6 应用举例
5
Page 6
§2.1 线性规划问题及其数学 模型
§2.1 线性规划问题及其数学模型
上面两个问题的数学模型为：
max z 2 x1 3 x2
x1 2 x2 8 16 4 x1 4 x2 12 x1 , x2 0
Page 18
s.t.
§2.1 线性规划问题及其数学模型
• 2. 1.2 图解法
• 线性规划问题的求解方法: 图解法 单纯形法 两个变量、直角坐标 三个变量、立体坐标 适用于任意变量、但必需将 一般形式变成标准形式
运 筹 学
Operations Research
1
Page 2
线性规划
Linear Programming
引 言
Page 3
• 线性规划是运筹学的一个重要分支，也是运筹学中应用最广 泛的方法之一。自1947年丹捷格（G. B. Dantzig）提出了 一般线性规划问题求解的方法——单纯形法之后，线性规划 已被广泛应用于解决经济管理和工业生产中遇到的实际问题。 调查表明，在世界500家最大的企业中，有85%的企业都曾 使用过线性规划解决经营管理中遇到的复杂问题。线性规划 的使用为应用者节约了数以亿万计的资金。 • 简言之，线性规划模型对于解决经济学研究的核心问题—资 源有效配置有比较重要的意义。不仅如此，线性规划在企业 的运作管理、物流管理、财务管理、人力资源管理、战略管 理等诸多方面也能为管理者提供科学的决策支持。
s.t.
§2.1 线性规划问题及其数学模型
上述两个问题具有的共同特征：
Page 15

每一个线性规划问题都用一组决策变量 x1 , x2 ,
xn
表示某一方案，这组决策变量的值代表一个具体方案。一 般这些变量的取值是非负且连续的；


都有关于各种资源和资源使用情况的技术数据，创造新价 值的数据；
非负约束条件
简写为： max (min) Z
c x
j 1 j
n
其中c j 称为价值系数，aij 称为
j
a
j 1
n
技术系数，bi 称为限额系数.
ij
x j ( ) bi
(i 1 2 m ) (j 1 2 n)
xj 0
§2.1 线性规划问题及其数学模型
如果是求极小值 min z c j x j
即 变量的变换
maxz z c j x j
（1）若存在取值无约束的变量x j ,可令 x j xj x ， 其中xj , x 0 j j （2）若存在变量x j 0， 可令xj x j，其中xj 0.
§2.1 线性规划问题及其数学模型
特点： (1) 目标函数求最大值。
Page 27
(2) 约束条件都为等式方程，且右端常数项bi都大于等于零。 (3) 决策变量xj为非负。
§2.1 线性规划问题及其数学模型
向量形式：max z CX
pj x j B X 0
Page 28
Page 21
max z 2 x1 3 x2
2 z x2 x1 3 3 表示一簇平行线