9299.net
大学生考试网 让学习变简单
当前位置:首页 >> 工学 >>

第一章--线性规划及图解法_图文

第一章--线性规划及图解法_图文

运 筹 学
Operations Research

第一章

线性规划及图解法

第一章

线性规划及单纯形法

线性规划( 线性规划(Linear Programming,简称 ) ,简称LP) 运筹学的一个重要分支,是运筹学中研究较早、 运筹学的一个重要分支,是运筹学中研究较早、发展较 理论上较成熟和应用上极为广泛的一个分支。 快、理论上较成熟和应用上极为广泛的一个分支。 1947年G.B. Dantying提出了一般线性规划问题求解 1947年 提出了一般线性规划问题求解 的方法——单纯形法之后,线性规划的理论与应用都得 单纯形法之后, 的方法 单纯形法之后 到了极大的发展。 到了极大的发展。 60年来,随着计算机的发展, 60年来,随着计算机的发展,线性规划已广泛应用 年来 于工业、农业、商业、交通运输、 于工业、农业、商业、交通运输、经济管理和国防等各 个领域,成为现代化管理的有力工具之一。 个领域,成为现代化管理的有力工具之一。

§1 线性规划问题及其数学模型

e.g. 1 资源的合理利用问题
某工厂在下一个生产周期内生产甲、乙两种产品, 要消耗A、B 两种资源,已知每件产品对这两种资源的 消耗,这两种资源的现有数量和每件产品可获得的利 润如表 1。 问:如何安排生产计划,
资源 甲 1 1 15 乙 3 1 25 库存量 60 40 表1 产品

使得既能充分利用现有资 源又使总利润最大?

A B
单件利润

第一章

线性规划及单纯形法
决策变量
表1

解 : 设 x1,x2 为下一个生
产周期产品甲和乙的产量;
产品 资源 甲 1 1 15 乙 3 1 25 库存量 60 40

约束条件: x1 + 3x2 ≤ 60 x1 + x2 ≤ 40 x1,x2 ≥ 0 目标函数: z = 15 x1 +25 x2
Subject to
A B
单件利润

max z = 15x1 +25x2 s.t. x1 + 3x2 ≤ 60 x1 + x2 ≤ 40 x1,x2 ≥ 0

§1 线性规划问题及其数学模型

e.g. 2 营养问题
假定在市场上可买到 B1,B2,…Bn n 种食品,第 i 种 食品的单价是 ci , 另外有 m 种营养 A1,A2,…Am。设 Bj 内含有 Ai 种营养数量为 aij (i=1~m,j=1~n),又知人们每 天对 Ai 营养的最少 需要量为 bi。见表2: 试在满足营养要
A1 表2 食品 营养 B1 a11 a21 … am1 c1 B2 a12 a22 … am2 c2 … Bn … a1n 最少 需要量 b1 b2 … bm

求的前提下,确定食
A2 … … a2n … … … … amn cn

品的购买量,使食品
Am

的总价格最低。

单 价

第一章 解:

线性规划及单纯形法
表2 食品 营养 A1 A2 … Am B1 a11 a21 … am1 c1 B2 a12 a22 … am2 c2 … Bn … a1n 最少 需要量 b1 b2 … bm

设 xj 为购买食 品 Bj 的数量 ( j=1,2, …,n )
m in
s .t .

… a2n … … … … amn cn

z =


ij

n

j =1

cjxj

单 价

∑a
j =1

n

x j ≥ bi

(i = 1,2,…,m) 0≤ xj ≤lj

xj≥0 (j = 1,2,…,n)

§1 线性规划问题及其数学模型 Note:

1、善于抓住关键因素,忽略对系统影响不大的因素; 善于抓住关键因素,忽略对系统影响不大的因素; 2、可以把一个大系统合理地分解成 n 个子系统处理。 个子系统处理。

三个基本要素: 三个基本要素
1、决策变量 、
xj≥0

2、约束条件 —— 一组决策变量的线性等式或不等式 3、目标函数 —— 决策变量的线性函数

第一章

线性规划及单纯形法

线性规划问题的一般形式: 线性规划问题的一般形式: max(min)z = c1x1 + c2x2 + … + cnxn s.t. a11x1 + a12x2 + … + a1nxn ≤(或=,≥)b1 a21x1 + a22x2 + … + a2nxn ≤(或=,≥)b2 …… am1x1 + am2x2 + … + amnxn ≤(或=,≥)bm xj ≥ 0 (j = 1,2,…,n) 其中aij、bi、cj(i = 1,2,…,m;j = 1,2,…,n)为已知 常数

§1 线性规划问题及其数学模型 特点: 特点:

线性规划问题的标准形式:
1、目标函数为极

max z = c1x1 + c2x2 + … + cnxn s.t. a11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2 …… am1x1 + am2x2 + … + amnxn = bm xj ≥ 0 (j = 1,2,…,n) bi ≥ 0 (i = 1,2,…,m)

大化; 大化; 2、除决策变量的 非负约束外, 非负约束外,所有 的约束条件都是等 式,且右端常数均 为非负; 为非负; 3、所有决策变量 均非负。 均非负

第一章

线性规划及单纯形法

如何转化为标准形式? 如何转化为标准形式? 1、目标函数为求极小值,即为:min z =



n

j =1

cjx

j



因为求 min z 等价于求 max (-z),令 z’ = - z, 即化为:
max z = ? ∑ c j x
' j =1 n j

xn+1 ≥ 0

松弛变量

2、约束条件为不等式,

∑ ∑
n

n

a a

j =1

ij

x x

j

≤ bi ≥ bi

∑a
j =1

n

ij

x j + x n +1 = b i

j =1

ij

j

如何处理? 如何处理?

§1 线性规划问题及其数学模型 0时 只需将等式两端同乘( 3、右端项bi < 0时,只需将等式两端同乘(-1) 则右端项必大于零 4、决策变量无非负约束 设 xj 没有非负约束,若 xj ≤0,可令 xj = - xj’ , 没有非负约束, ≤0, ≥0; 则 xj’ ≥0; 为自由变量, 可为任意实数, 又若 xj 为自由变量,即 xj 可为任意实数, 可令 xj = xj’ - xj’’,且 xj’ , xj’’ ≥0

第一章

线性规划及单纯形法
max z’= x1-2x2+3x4- 3x5 s.t. x1+x2+x4-x5+x6=7 x1-x2+x4-x5-x7=2 3x1-x2-2x4+2x5=5 x1,x2,x4,x5,x6,x7≥0

e.g. 3 试将 LP 问题

min z = -x1+2x2-3x3 s.t. x1+x2+x3 ≤7 x1-x2+x3 ≥2 -3x1+x2+2x3 = -5 x1,x2 ≥0 化为标准形式。

解: 令 x3= x4 - x5 其中x4、x5 ≥0;
对第一个约束条件加上松弛变量 x6 ; 对第二个约束条件减去松弛变量 x7 ; 对第三个约束条件两边乘以“-1” ; 令 z’=-z 把求 min z 改为求 max z’

§1 线性规划问题及其数学模型

LP的几种表示形式:
max s.t . z=
n

∑c
j =1 ij

n

j

xj

∑a
j =1

x j = bi (i = 1, 2 , K , m )

? a11 ? ?a A = ? 21 M ? ?a ? m1

a12 a 22 M am2

L a1n ? ? L a2n ? ? ? ? 系数矩阵 M M ? L a mn ? ?

x j ≥ 0 ( j = 1, 2, K , n )

c = ( c1 , c2 ,K , cn ) ? ?价值向量

m ax s .t .

z = cx Ax = b x ≥ 0

(1) (2) (3 )

x = ( x1 , x2 ,K, xn ) ? ?决策向量
T

b = (b1 , b 2 , K , b m

)T , b i
T

≥ 0 ? ? 右端向量

m ax s .t .

z = cx



n

j =1

p jx

j

= b

p j = (a1 j , a 2 j , K , a mj ) 为 A 的第 j列向量

x ≥ 0

§2 线性规划问题的图解法

m ax s .t .

z = cx Ax = b x ≥ 0

(1) (2) (3 )

定义1 问题中,凡满足约束条件(2) (3)的 (2)、 定义 在LP 问题中,凡满足约束条件(2)、(3)的 称为LP 问题的可行解, 解 x = (x1,x2,…,xn)T 称为 问题的可行解, 所有可行解的集合称为可行解集(或可行域)。 所有可行解的集合称为可行解集(或可行域)。 D={ x | Ax = b ,x≥0 }。 记作 定义2 设LP问题的可行域为D,若存在x*∈D,使得 定义 问题的可行域为 对任意的x 都有c 对任意的 ∈D 都有 x*≥c x,则称x*为LP 问题 , 的最优解,相应的目标函数值称为最优值, 的最优解,相应的目标函数值称为最优值, 记作 z*=c x*。

§2 线性规划问题的图解法 max z = 15x1 +25x2 目标函数变形: 目标函数变形: x2=-3/5 x1+z/25 x2
x1 + x2 = 40

s.t.
B点是使z达到最 点是使z 大的唯一可行点

x1 + 3x2 ≤ 60 x1 + x2 ≤ 40 x1,x2 ≥ 0

最优解:
A (0,20) B (30,10)

x1=30 x2 =10
x1 + 3x2 = 60

最优值:zmax=700
x1
L1

(0,0) O Z=250

C (40,0)

L2

第一章

线性规划及单纯形法

LP问题图解法的基本步骤 LP问题图解法的基本步骤: 问题图解法的基本步骤
1、在平面上建立直角坐标系; 、在平面上建立直角坐标系; 2、图示约束条件,确定可行域和顶点坐标; 、图示约束条件,确定可行域和顶点坐标; 3、图示目标函数(等值线)和移动方向; 、图示目标函数(等值线)和移动方向; 4、寻找最优解。 、寻找最优解。

§2 线性规划问题的图解法
绿色线段上的所有点 都是最优解,即有无穷多 都是最优解 即有无穷多 最优解。 最优解。Zman=34.2

x2

x1 + 1.9 x2 = 11.4
(3.8,4) )

max z =3x1 + 5.7x2 s.t. x1 + 1.9x2 ≥ 3.8 x1 - 1.9x2≤ 3.8 x1 + 1.9x2 ≤11.4 x1 - 1.9x2 ≥ -3.8 x1 ,x2 ≥ 0

x1 - 1.9 x2 = -3.8
(0,2)

D

x1 - 1.9 x2 = 3.8
(7.6,2) ) 34.2 = 3 x1 +5.7 x2

可行域

max Z (3.8,0) min Z

o
0=3 x1 +5.7 x2

x1 + 1.9 x2= 3.8

x1

第一章

线性规划及单纯形法
可行域为无界 区域一定无最 优解吗? 优解吗?

x2
2 x1 ? x2 = 2
? x1 + 4 x2 = 4

max z = 2x1 + 2x2 s.t. 2x1 – x2 ≥ 2 -x1 + 4x2≤ 4 x1,x2 ≥ 0

Note: 可行域为无界区域, 可行域为无界区域, 目标函数值可无限 增大,即解无界。 增大,即解无界。

(1,0)

称为无最优解。 称为无最优解
O A

x1

§2 线性规划问题的图解法

由以上两例分析可得如下重要结论: 由以上两例分析可得如下重要结论:
1、LP 问题从解的角度可分为: 、 问题从解的角度可分为:
a. 有唯一最优解

⑴ 有可行解 b. 有无穷多最优解
C. 无最优解

⑵ 无可行解 2、LP 问题若有最优解,必在可行域的某个顶点上取 、 问题若有最优解,
若有两个顶点上同时取到, 到;若有两个顶点上同时取到,则这两点的连线上 任一点都是最优解。 任一点都是最优解。

§2 线性规划问题的图解法

图解法优点: 图解法优点: 直观、易掌握。有助于了解解的结构。 直观、易掌握。有助于了解解的结构。 图解法缺点: 图解法缺点: 只能解决低维问题,对高维无能为力。 只能解决低维问题,对高维无能为力。


推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 大学生考试网 9299.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com