当前位置：文档之家 › 1.线性规划及单纯形法1

1.线性规划及单纯形法1

  • 格式：ppt
  • 大小：2.18 MB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

第1讲线性规划及单纯形法

第1讲线性规划及单纯形法
21
解：目标函数： Min 约束条件：
f = 2x1 + 3 x2
s.t.
x1 + x2 ≥ 350
x1 ≥ 125
2 x1 + x2 ≤ 600
x1 , x2 ≥ 0 采用图解法。如下图：得Q点坐标（250，100）为最优解。
x2
x1 =125
600
500
2x1+3x2 =1200
400
2x1+x2 =600
26
凸集
定义 2.2.1：设 S Rn 是 n 维欧氏空间的点集，若对任意 x S, y S 的和任意 [0,1] 都有 x (1 ) y S 就称 S 是一个凸集。
定理 2.2.1 线性规划的可行域 D { x Ax b, x 0} 是凸集 定理 2.2.2 任意多个凸集 Si 的交还是凸集
例1 目标函数： max 50x1+100x2 约束条件：x1+x2+s1=300，
2x1+x2+s2=400， x2+s3=250.
xj≥0 （j=1，2）,sj≥0 （j=1，2,3）
30
它的系数矩阵 ,
1 1 1 0 0
A(p1,p2,p3,p4,p5)2 1 0 1 0
0 1 0 0 1
其中pj为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变
a i1 x 1 a i 2 x 2 a in x n s i b i , s i 0
或
a i1 x 1 a i 2 x 2 a in x n b i
松弛变量
a i1 x 1 a i 2 x 2 a in x n s i b i , s i 0

第一章线性规划问题及单纯形解法演示文稿

第一章线性规划问题及单纯形解法演示文稿
线性规划问题的可行解集S是凸集 设X属于S,若x=0,则一定为极点；若x 0，则为极点的充要条件是：x的正分量所 对应的系数列向量线性无关。
只要存在可行解，就一定存在极点
极点的个数是有限的
最优解只可能在凸集的极点上，而不可能发生 在凸集的内部
38
第38页，共65页。
关于标准型解的若干基本概念：
Z=15x11+21x12+18x13+
20x21+25x22+16x23, x11+x12+x13≤200, x21+x22+x23≤150, x11+ x21 ＝100, x12+x22＝80, x13+x23≥90, x13+x23≤120, xij≥0 ﹙i=1,2 j=1,2,3﹚.
10
第10页，共65页。
maxz( x) c x c x c x
11
22
nn
s.t.
a x a x a x b
11 1
12 2
1n n
1
ax 21 1
a x 22 2
a x 2n n
b 2
am1
x 1
a x m2 2
a x mn n
b m
x , x ,, x 0
1
2
n
12
第12页，共65页。
1、标准型的几种不同的表示方式
对有限个约束条件则其可行域的顶点也是有限的。
z=10000=50x1+100x
2
z=0=50x1+100x2
x2
x1+x2=300
AB C
E
z=27500=50x1+100x

第一章 线性规划及单纯形法

第一章 线性规划及单纯形法
37
线性规划问题的标准形式： 线性规划问题的标准形式：
max f = ∑ c j x
j =1 j n
n ∑ aij x j = bi , i = 1,2,L , m j =1 x j ≥ 0, j = 1,2,L , n
日产量（ 日产量（吨） 9 5 7 21
11
）（模型 例2（运输问题）（模型） （运输问题）（模型）
minf = 2 x11 + 9 x12 + 10 x13 + 7 x14 + x21 + 3 x22 + 4 x23 + 2 x24 + 8 x31 + 4 x32 + 2 x33 + 5 x34 x11 + x12 + x13 + x14 = 9 x +x +x +x =5 23 24 21 22 x31 + x32 + x33 + x34 = 7 x11 + x21 + x31 = 3 s.t. x12 + x22 + x32 = 8 x13 + x23 + x33 = 4 x14 + x24 + x34 = 6 xij ≥ 0(i = 1,2,3; j = 1,2,3,4)
18
3、（线性规划）数学模型的三要素 、（线性规划） 、（线性规划 变量/决策变量 决策变量； ①变量 决策变量； 目标函数（ ②目标函数（max/min）； ）； 约束条件。 ③约束条件。
19
决策变量： ①变量/决策变量：指决策者为实现规划目标采 变量 决策变量 取的方案、措施，是问题中要确定的未知量； 取的方案、措施，是问题中要确定的未知量；

第1章-线性规划及单纯形法-课件(1)

第1章-线性规划及单纯形法-课件(1)

✓ x1、 x2 0
IБайду номын сангаас
设备
1
原材料 A 4
原材料 B 0
利润
2
II 资源限量
2 8 台时
0
16kg
4
12kg
3
第一章 线性规划及单纯形法 运筹学
该计划的数学模型
✓ 目标函数 ✓ 约束条件
Max Z = 2x1 + 3x2
x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0
x1
✓ 美国航空公司关于哪架飞机用于哪一航班和哪些 机组人员被安排于哪架飞机的决策。
✓ 美国国防部关于如何从现有的一些基地向海湾运 送海湾战争所需要的人员和物资的决策。
✓ ……
第一章 线性规划及单纯形法 运筹学
二、线性规划问题的数学模型
✓ 1、一般形式 ✓ 2、简写形式 ✓ 3、表格形式 ✓ 4、向量形式 ✓ 5、矩阵形式
1、唯一最优解
max Z 2 x 1 3 x 2
2 x 1 2 x 2 12 ⑴
x1 4 x1
2 x2
8 16
⑵ ⑶
4 x 2 12 ⑷
x 1 0 , x 2 0
1 234 56
x2
⑶ ⑷
(4，2)
0 1 234 5678
x1
⑵
⑴
✓最优解：x1 = 4,x2 = 2，有唯一最优解Z=14。
第一章 线性规划及单纯形法 运筹学
三、线性规划模型的标准形式
✓ 1、标准形式 ✓ 2、转换方式
第一章 线性规划及单纯形法 运筹学
1、标准形式
maZx cjxj
xj
aijxj 0
bi

第1章线性规划及单纯形法

第1章线性规划及单纯形法

表1-17
原料 甲
乙
丙
A ≥60% ≥3%
B C ≤20% ≤50% ≤60 加工费 0.50 0.40 0.30 (元/kg) 售价 3.4 2.85 2.25 (元/kg)
原料成本 每月限 (元/kg) 制用量
(kg)
2.00 2000
1.50 2500
1.00 1200
（二） 产品计划问题
Min z= 13x1 +9x2 +10x3 +11x4 +12x5 +8x6
s.t.
x1 +x4 =300
x2 +x5 =500
x3 +x6 =400
0.4x1 +1.1x2
+x3 ≤700
0.5x4 +1.2x5 +1.3x6 ≤800
xj ≥0 （j＝1， 2， …， 6）
例3：某昼夜服务的公共交通系统每天各时间段 （ 每4小时为一个时间段）所需的值班人数如下表， 这些值班人员在某一时段开始上班后要连续工作8个 小时 （ 包括轮流用膳时间在内），问该公交系统至
少需多少名工作人员才能满足值班的需要。
班次
时间段
所需人数
1
6:00—10:00
60
2
10:00—14:00
70
3
14:00—18:00
60
4
18:00—22:00
50
5
22:00—2:00
20
6
2:00—6:00
30
设xi为第i个时段开始上班的人员数，由此可得数 学模型如下：
Min z= x1 +x2
+x3 +x4 +x5 +x6

运筹学第1章：线性规划问题及单纯型解法

运筹学第1章：线性规划问题及单纯型解法

原料甲 原料乙 最低含量 VA 0.5 0.5 2 VB1 1.0 0.3 3 VB2 0.2 0.6 1.2 VD 0.5 0.2 2 0.3 0.5 单价
分别代表每粒胶丸中甲, 设 x1, x2分别代表每粒胶丸中甲, 乙两种原料的用量
5
例3,合理下料问题 , 分别代表采用切割方案1~8的套数, 的套数, 设 xj 分别代表采用切割方案 的套数
19
( f(x
)= 3
6
1.2.2 单纯型法的基本思路
确定初试基础可行解
检查是否为 最优解? 最优解?
是
求最优解的目标函数值
否 确定改善方向
求新的基础可行解
20
1.2.3 单纯型表及其格式
IV CB III XB II x1 b c1 a11 a21 c1′′= cn+1 xn+1 b1 c2′′= cn+2 xn+2 b2 x2 … xn c2 … cn a12 … a1n a22 … a2n I xn+1 cn+1 1 0 0 zn+1 xn+2 cn+2 0 1 0 zn+2 … … … … … … xn+m cn+m 0 0 1 zn+m
OBJ : max f ( x) = 6x1 + 4x2 2x1 + x2 ≤ 10 铜资源约束 x1 + x2 ≤ 8 铅资源约束 s.t. x2 ≤ 7 产量约束 x1, x2 ≥ 0 产量不允许为负值 最优解: x1 = 2, x2 = 6, max f ( x) = 36.
4
例2,配料问题(min, ≥) ,配料问题(
2 max 1 O 1 2 3 4 D 5 6 7 H 8

第一章线性规划及单纯形法

第一章线性规划及单纯形法

第一章线性规划及单纯形法6.6单纯形法小结Drawingontheexampl,thetwoaxisinterceptsareplotted.2、求初始基可行解并进行最优性检验Cj比值CBXBb 检验数?jx1x2x3x4x53500081010012020103634001x3x4x5000035000令非基变量x1=0，x2=0，找到一个初始基可行解：x1=0，x2=0，x3=8，x4=12，x5=36，σj＞0，此解不是最优（因为z=3x1+5x2+0x3+0x4+0x5)即X0=(0,0,8,12,36)T，此时利润Z=03、寻找另一基可行解Cj比值CBXBb检验数?jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9主元首先确定入基变量再确定出基变量检验数?j81010060101/2012300-21x3x2x5050-30300-5/20Cj比值CBXBb检验数?jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9令x1=0，x4=0，得x2=6，x3=8，x5=12，即得基可行解X1=(0,6,8,0,12)T此时Z＝30σ1=3＞0，此解不是最优迭代4、寻找下一基可行解Cj比值CBXBb检验数?jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数?j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1令x4=0，x5=0，得x1=4，x2=6，x3=4，即X0=(4,6,4,0,0)T?j＜0最优解:X=(4,6,4,0,0)T最优值:Z=42小结：单纯形表格法的计算步骤①将线性规划问题化成标准型。

②找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。

第1章线性规划与单纯形法

第1章线性规划与单纯形法

一、选择填空1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 二、判断正误1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 三、将下列问题化为标准型1.123412341231324237..2358,0,0,Max Z x x x x x x x x s t x x x x x x x =++++++≤⎧⎪-+=-⎨⎪≥≤⎩符号不限[解] 令'22x x =-，'445x x x =-，在约束1中引入非负的松弛变量6x ，约束2两边同乘以-1。

整理得：''12345''123456'123''12345623()()7..23()58,,,,,0Max Z x x x x x x x x x x x s t x x x x x x x x x =-++-⎧-++-+=⎪-+--=⎨⎪≥⎩即：12345123456123123456237..2358,,,,,0Max Z x x x x x x x x x x x s t x x x x x x x x x =-++--++-+=⎧⎪---=⎨⎪≥⎩2. Min Z=-x 1+5x 2-2x 3x 1 +x 2- x 3 ≤ 61 - x2 +3x3 ≥ 5x 1 + x 2 = 10x1 ≥0, x2 ≤0, x3符号不限[解] 首先，令对变量x3进行处理，令x3 = x’3- x4;再令x’2 = - x2。

然后对目标函数和约束条件进行标准化。

Max Z=x1+5x2+2x3-2x4x1 - x2 - x3+x4+x5 = 61 + x2 +3x3 - 3x4 -x6 = 5x1 - x2 = 10x1, x2, x3, x4, x5, x6≥0四、用图解法求解下列线性规1. min Z= - x1+2x2x1 - x2 ≥-2x1 +2x2 ≤6x1, x2 ≥0[解]根据上图，最优解为X*=（x1, x2）T =（6, 0）T，最优值为-6。

第一章 线性规划及单纯形法1图解2006

第一章 线性规划及单纯形法1图解2006

简写为：
n
ma或 x(minz) cjxj
j1
jn1aijxj (,)bi (i 1,,m)
xj 0 (j 1,,n)
向量表达形式：
ma或 xm ( izn)CX
n
j 1
Pj
x
j
(, )b
X 0
C(c1,c2,,cn)
x 1
X
x2 xn
a 1 j
Pj
a2j
目标函数 mzi n 28(x1 0 1x 0 2 1x3 1x4)145(x1 02 0 x22 x3)260(x1 0 3x 0 2)373x10 4 0
约束条件
x11 x12 x13 x14 15
xx1132
x13 x14
x14 x22
x21 x23
x22 x31
x23 x32
第一章 线性规划及单纯形法
第一节 线性规划问题及其数学模型
例：某公司计划生产甲、乙两种产品，已知各生产一件时分别 占用的设备A、B的台时、调试时间和调试工序每天可用于这两 种产品的能力、各销售一件时的获利情况，如下表所示。问该 公司应生产两种产品各多少件，使获取的利润为最大。
甲
乙 每天可用能力
设备A(h)
可行域中使目标函数值达到最优的可行解称为最优解。
图解法的步骤：
（1）在平面上建立直角坐标系 （2）图示约束条件，找出可行域 （3）图示目标函数，寻求最优解
线性规划的图解
max z = x1+3x2 s.t. x1+ x2≤6
-x1+2x2≤8 x1 ≥0, x2≥0
x2 6
4
最优解 可行域
-8
0
目标函数等ห้องสมุดไป่ตู้线

运筹学[第一章线性规划与单纯形法]山东大学期末考试知识点复习

运筹学[第一章线性规划与单纯形法]山东大学期末考试知识点复习

第一章线性规划与单纯形法1．线性规划问题的数学模型(1)一般形式(2)标准型式]2．数学模型化为标准型(1)若目标函数实现最小化，则min z=-max z'(令z'=-z)(2)若约束方程为不等式，则若约束方程为“≤”不等式左端+松驰变量(≥0)=右端若约束方程为“≥”不等式左端-剩余变量(≥0)=右端(3)若存在取值无约束的变量x k(1≤k≤咒)，则在标准型中x k=x'k-x"k(其中x k=x'，x"k≥0)3．线性规划的解线性规划问题：(1)可行解：满足约束条件②和③的解X=(x1，x2，…，x n)T。

(2)最优解：使目标函数①达到最大值的可行解。

(3)基：设A为约束方程组②的m×n阶系数矩阵，设n＞m，其秩为m，B 为矩阵A中的一个m×m阶的满秩子矩阵，则称B为线性规划问题的一个基。

不失一般性，设B中每一个列向量P j(j=1，2，…，m)称为基向量，与基向量PJ对应的变量x j称为基变量。

除基变量以外的变量为非基变量。

(4)基本解：在约束方程组②中，令所有非基变量x m+1=x m+2=…=x n=0，此时方程组②有唯一解X B=(x1，x2，…，x m)T，将此解加上非基变量取0的值有X=(x1，x2，…，x m，0，0…，0)T，称X为线性规划问题的基本解。

(5)基本可行解：满足非负条件③的基本解。

(6)可行基：对应于基本可行解的基。

4．初始基可行解的确定(1)直接从A中观察到存在一个初始可行基。

(2)对所有约束条件是“≤”形式的不等式，可利用化为标准型的方法，在每个约束条件左端加上一个松弛变量，这m个松弛变量就构成一个基变量，则对应的m个向量组成的单位矩阵B就是线性规划问题的一个可行基。

(3)对所有约束条件是“≥”形式的不等式以及等式约束情况，采用人造基的方法。

即对不等式约束的左端减去一个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束的左端再加上一个非负的人工变量。

运筹学基础及应用第五版胡运权第一章

运筹学基础及应用第五版胡运权第一章
问题的提出 某企业计划生产Ⅰ、Ⅱ两种产品。这两种产品都要分别在A、B、C、D四种不同设备上加工。生产每件产品Ⅰ需占用各设备分别为2、1、4、0h，生产每件产品Ⅱ，需占用各设备分别为2、2、0、4h。已知各设备计划期内用于生产这两种产品的能力分别为12、8、16、12h，又知每生产一件产品Ⅰ企业能获得2元利润，每生产一件产品Ⅱ企业能获得3元利润，问企业应安排生产两种产品各多少件，使总的利润收入为最大。
xi 0
aij
aLj
xL 0
i
∴ P1 , P2,······,PL-1, PL+1,······ Pm, Pj 线性无关。
∴ X1 也为基本可行解。
四、最优性检验和解的判别
令
，其中 随基的改变而改变
X1 = (x1 0- a1j ,x2 0- a2j ,···,xm 0- amj ,0,···,,···,0)T
必要性：X非基本可行解 X非凸集顶点 不失一般性，设X=(x1,x2,······,xm,0,0,······,0)T，为非基本可行解， ∵ X为可行解，
证：等价于 X非基本可行解X非凸集顶点
又 X是非基本可行解， ∴ P1,P2,······,Pm线性相关，即有 1P1+2P2+······+mPm=0， 其中1，2，······，m不全为0，两端同乘≠0，得 1P1+2P2+······+mPm=0，······（2）
∵ >0, 1->0 ，当xj=0， 必有yj=zj=0
∴
pjyj =
j=1
n
pjyj=b ······(1)
j=1
r
pjzj =
j=1
n
pjzj=b ······(2)

运筹学第1章线性规划及单纯形法复习题

运筹学第1章线性规划及单纯形法复习题

max (min)
Z = CX
AX ≤ ( = , ≥ ) b X ≥ 0
3、线性规划的标准形式 、
ma0
4、线性规划问题的解 、 （一）求解方法
一 般 有 两种方法 图 解 法 单纯形法 两个变量、 两个变量、直角坐标 三个变量、 三个变量、立体坐标
适用于任意多个变量、 适用于任意多个变量、但需将 一般形式变成标准形式
（二）线性规划问题的解
1、解的概念 可行解：满足约束条件② 的解为可行解。 ⑴ 可行解：满足约束条件②、③的解为可行解。 所有解的集合为可行解的集或可行域。 所有解的集合为可行解的集或可行域。 最优解： 达到最大值的可行解。 ⑵ 最优解：使目标函数①达到最大值的可行解。 ⑶ 基：B是矩阵A中m×m阶非奇异子矩阵 是矩阵A ≠0）， ），则 是一个基。 （∣B∣≠0），则B是一个基。
§2 图 解 法
例一、 例一、 max
Z = 2 x 2 x 2 x 4 x
2 2 1
+ 3 x
2
2 x1 + x + 1 4 x1 x1 ≥
≤ 12 ≤ 8 ≤ 16 ≤ 12
2
⑴ ⑵ ⑶ ⑷
2
0, x
≥ 0
max
Z = 2 x1 + 3 x 2 x 2 x
2 2
当xj=0时, 必有 j=zj=0, 因此 时 必有y
∑P x = ∑P y = ∑P z
j =1
r
r
r
r
j
j
j =1
j
j
j =1
j
j
=b
∑(y
j =1
j
− z j ) Pj = 0

运筹学第一章

运筹学第一章

第一章、 线性规划和单纯形法1.1 线性规划的概念一、线性规划问题的导出1．(引例) 配比问题——用浓度为45%和92%的硫酸配置100t 浓度为80%的硫酸。

取45%和92%的硫酸分别为x1和x2t,则有： 求解二元一次方程组得解。

目的相同，但有5种不同浓度的硫酸可选（30%，45%，73%，85%，92%）会出现什么情况？设取这5种硫酸分别为 x1、x2、x3、x4、x5 t, 则有： ⎩⎨⎧⨯=++++=++++1008.092.085.073.045.03.01005432154321x x x x x x x x x x 请问有多少种配比方案？为什么？哪一种方案最好？假设5种硫酸价格分别为：400，700，1400，1900，2500元/t ，则有：2.生产计划问题如何制定生产计划，使三种产品总利润最大？考虑问题：⎩⎨⎧⨯=+=+1008.092.045.01002121x x x x ⎪⎩⎪⎨⎧=≥⨯=++++=++++++++=5,,2,1,01008.092.085.073.045.03.0100..250019001400700400543215432154321 j x x x x x x x x x x x t s x x x x x MinZ j（1）何为生产计划？（2）总利润如何描述？（3）还要考虑什么因素？（4）有什么需要注意的地方（技巧）？（5）最终得到的数学模型是什么？二、线性规划的定义和数学描述（模型）1．定义：对于求取一组变量xj (j =1,2,......,n)，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划。

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

第1章线性规划与单纯形法

第1章线性规划与单纯形法
26
线性规划问题的数学模型
7. 线性规划问题的解
线性规划问题
n
max Z cj xj (1) j 1
s.t
n j 1
aij
xj
bi
(i 1, 2,
, m) (2)
x
j
0,
j
1, 2,
, n (3)
求解线性规划问题，就是从满足约束条件(2)、(3)的方程组 中找出一个解，使目标函数(1)达到最大值。
解： Max z = 3x1–5x2’+5x2”–8x3 +7x4 s.t. 2x1–3x2’+3x2”+5x3+6x4+x5= 28 4x1+2x2’-2x2”+3x3-9x4-x6= 39 -6x2’+6x2”-2x3-3x4-x7 = 58 x1 ,x2’,x2”,x3 ,x4 ,x5 ,x6 ,x7 ≥ 0
x1 , x2 0, x3无约束
解:（１）因为x3无符号要求 ，即x3取正值也可取负值，标准 型中要求变量非负，所以
用 x3 x3 替换 x3 ，且 x3 , x3 0
20
线性规划问题的数学模型
(2) 第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4， x4≥0,化为等式；
(3) 第二个约束条件是“≥”号，在“≥”左端减去剩余变量x5， x5≥0；
11
线性规划问题的数学模型
3. 建模条件 (1) 优化条件：问题所要达到的目标能用线型函数描述，且 能够用极值 （max 或 min）来表示；
(2) 限定条件：达到目标受到一定的限制，且这些限制能够 用决策变量的线性等式或线性不等式表示；
(3) 选择条件：有多种可选择的方案供决策者选择，以便找 出最优方案。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
1. 标准型的构成要素 （1）目标函数：max （2）约束条件：等式 （3）变量约束：非负 xj0 （4）资源限量：非负bi 0
18
2. 标准型的表示方法
（1）解析式
max Z c1 x1 c2 x2 cn xn
a11x1 a12x2 a1n xn b1
a21 x1
a22x2
a2n xn
1.线性规划及单纯形 法1
第一章 线性规划及其单纯形法
第一第节一章 线线性性规规划划及问单题纯及形数法学模型
Linear Programming , LP
• 1939年 苏 康托洛维奇和1941年 美 Hichook
在生产组织管理和制定交通运输方案方面研究和应用线性规划，求 解方法——解乘数法
• 1947年 G. B. Dantzig 单纯形法 • 1979年 苏 哈奇安多项式算法（椭球算法） • 1984年 Karmarkar算法
图解法意义不大，但可直观揭示有关概念。
11
3.LP解的类型
有4类： （1）唯一最优解
如例1的Q2点。 （2）无穷多最优解（多重解） （3）无界解 （4）无可行解
12
多重解示例
x2 当例1 的目标函数变为 max Z =2x1+4x2
①
96 3
③
4, 6
②
可行域
0
4
此线段上的点 均为最优点
Z=36
工 1 下 : 厂 ( 2 x 游 1 ) /5 0 .2 % 0s.t .
工 2 下 厂 :游
x1 0.8xx11
x2 x2
1.0 1.6 2.0 1.4
[0 .8 (2x 1)(1 .4x 2)/]70 0 .0 2 %
x1, x2 0
7
二、总结
线性规划问题（LP问题）的共同特征：
③
①
x1
16
4. 图解法的作用
揭示了线性规划问题有关规律和结论。
（1）规律：
有可行解 LP问题
有最优解
唯一解 无穷多解
无最优解（可行域为无界）
无可行解（无解）
（2）结论：若LP问题有最优解，则要么最优解唯一（对 应其中一个顶点），要么有无穷多最优解（对 应其中两个顶点连线上的所有点）。
17
五、 线性规划问题的标准型
b2
s.t.
am1 x1
am2 x2
amn xn
bm
x j 0, j 1,2,n
n :变量个数; m :约束行数; c j : 价值系数 bi : 右端项，bi 0, i 1,2,m; aij : 技术系数
19
简写的解析式
• 每一个问题变量都用一组决策变量（x1, x2, …, xn）表
示某一方案，这组决策变量的值代表一个具体方案，这 些变量是非负的且在某范围内连续取值。
• 存在一定的约束条件，这些约束条件可以用一组
线性等式或线性不等式来表示。
• 目标函数用决策变量的线性函数来表示。按问题
的不同，要求目标函数实现最大化和最小化。
原 A 约 料4 束 x 10x ： 216
原 B 约 料0 束 x 14x ： 212
变量非负约 x1 束0， ： x2 0
5
Step 3: 给出目标函数
mZ a 2 x x 1 3 x 2
Step 4: 整理数学模型
OBJ:maxZ 2x1 3x2
x1 s.t. 4x1
2x2 8 16
4x2 12 x1,x2 0
说明：OBJ 表示Objective;
s.t. 表示Subject to
6
例2 污水处理问题 (书P9)
2万m3 ，1000元/万m3 o工厂1
500万m3
200万m3
1.4万m3，800元/万m3 o工厂2
设 x1﹑x2 为 工 厂 1﹑2
OBJ : minZ 1000x1 800x2
的日污水处理量。建 立该问题的数学模型 为：
n :变量个数；m : 约束条件个数。
bi (, )0, i 1,2,m
9
四、两变量线性规划问题的图解法
1.线性不等式的几何意义— 半平面
2.图解法步骤
例1 （典型示例）：
• 作出LP问题的可行域
• 作出目标函数的等值线
• 移动等值线到可行域边界 得到最优点
OBJ : max Z 2x1 3x2
8
三、线性规划问题的一般形式
max(min)Z c1 x1 c2 x2 cn xn
a11 x1 a12 x2 a1n xn (, )b1
a21 x1 a22 x2 a2n xn
(, )b2
s.tБайду номын сангаас.
am1 x1
am2 x2
amn xn
(, )bm
x j (, )0, j 1,2,n
4
一、实例
例1 生产计划问题 (书P8，典型示例)
产品 I 设备 1 原料A 4 原料B 0 利润 2
II 资源限量 2 8台时 0 16公斤 4 12公斤 3
Step 1:明确问题，设定决策变量
设I、II两种产品的产量分别为x1, x2 。 Step 2: 确定约束条件
工时约x束 12： x2 8
多项式时间算法每次迭代不是从一个顶点出发求改进的顶点，而是使 迭代点保持在某个单纯形的内部，因此是一种内点算法。
3
LP是数学规划的一个重要分支，数学规划着重解决资源的 优化配置，一般可以表达成以下两个问题中的一个：
（1）当资源给定时，要求完成的任务最多； （2）当任务给定时，要求为完成任务所消耗的资源最少。 若上述问题的目标﹑约束都能表达成变量的线性关系， 则这类优化问题称LP问题。 LP是一种解决在线性约束条件下追求最大或最小的线性目 标函数的方法。
8
12
8, 3
x1
13
无界解示例
x2
①
可行域不闭合 Z增大方向
②
x1
14
产生原因：缺少约束条件 注 意：可行域不闭合不一定就会出现无界
解，这要看目标函数的性质。若目 标函数是min，则有最优解。无论 有无最优解，一定有可行解。
15
无可行解示例
x2
④
②
无公共区域(可行域) 产生原因：
有相互矛盾的 约束条件。
x1 2x2 8
s.t
.
4
x1
16 4x2 12
x1, x2 0
10
x2
Q6(0,4) Q4(0,3)
4x1=16 x1+2x2=8
Q3(2,3) Q5(4,3) Q2(4,2)
4x2=12
O(0,0)
Q1(4,0) Z=2x1+3x2
x1
Q7(8,0)
做目标函数2x1+3x2的等值线，与阴影部分的 边界相交于Q(4,2)点，表明最优生产计划为：生产I 产品4件，生产II产品2件。