第 2讲线性规划第二章 线性规划
2.1 线性规划模型的建立
2.2 线性规划模型的求解
2.3 对偶原理及灵敏度分析
2.4 运输问题表 1-1 每吨产品工时、材料消耗表产品生产每吨 产品所需资源资 源 A B C
工 时材 料
1 1 1
1 4 7
在生产管理和经营活动中经常提出的一类问题是：如何合理地利用有限的人力,物力,财力等资源,以便获得最好的经济效益 。
引例,资源配置,某工厂生产 A,B,C三种产品,每吨利润分别为 2000
元,3000元,3000元；生产单位产品所需的工时及原材料如表 1-1所示 。
若供应的原材料每天不超过 9t,所能利用的劳动力日总工时为 3个单位,
问如何制定日生产计划,使三种产品总利润最大？
2.1 线性规划模型的建立问题：工时和材料的日可供量已知,求使利润最大的生产方案解：产品 A,B,C的日生产量,x1,x2,x3
每日工时 = x1 + x2 + x3
每日消耗材料量 = x1 + 4x2 + 7x3
每天可得利润（以千元为单位）
Z = 2x1 + 3x2 + 3x3
工时约束材料约束非负约束
321 332m a x xxxZ
0,0,0
974
3
..
321
321
321
xxx
xxx
xxx
ts
利润最大
2.1 线性规划模型的建立
模型的组成部分（ Components of the Model）
1,决策变量 （ Decision variables）
2,目标函数 （ Objective function）
3,约束 （ Constraints）
定义,对于求取一组变量 xj(j=1,2,…..,n),使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。
2.1 线性规划模型的建立
2.1.1 线性规划模型的概念
max（ 或 min）
自由,00,,,
),(
),(
),(
..
21
2211
22222121
11212111
n
mnmnmm
nn
nn
xxx
bxaxaxa
bxaxaxa
bxaxaxa
ts
nn xcxcxcZ2211
目标函数（线性）
约束条件
（线性）
非负约束称为决策变量 ),,2,1( njx j
称为价值系数或目标函数系数 ),,2,1( njc
j
称为资源常数或约束右端常数 ),,2,1( mib i
称为技术系数或约束系数
),,2,1,,,2,1( njmia ij
线性规划模型的 一般形式,
紧缩形式：
线性规划建模
max(或 min)
n
j
jj xcZ
1
njx
bxa
ts
j
n
j
ijij
,,2,10
),(
.,1
i=1,2,…..,n
线性规划的假设
1,线性 （ Linearity）
2,可分性 （ Divisibility ）
3,确定性 （ Certainty）
4,非负性 （ Nonnegativity）
线性规划模型的 一般形式,
矩阵形式：
Max(或 Min) CXZ?
0X
bAXts ),(..
称为决策变量向量
nx
x
x
X
2
1
称为价值系数向量或目标函数系数向量 ),,,(
21 ncccC
称为技术系数或约束系数矩阵
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
称为资源常数向量或约束右端常数向量
m
b
b
b
b
2
1
线性规划建模线性规划模型特点：
① 用一组未知变量 （ 决策变量 ） 表示要求的方案 。
通常,根据决策变量所代表的事物的特点可以对变量的取值加以约束,例如非负约束 。
② 存在一定的限制条件,通常称为约束条件,这些约束条件可以用一组线性等式或者线性不等式来表示 。
③ 有一个目标要求,并且可以表示为决策变量的线性函数,称为目标函数,按所研究问题的不同,要求目标函数实现最大化或者最小化 。
线性规划建模
需要做哪些决策？决策变量是什么
问题的目标是什么？写出目标函数
资源和需求之间的情况如何？ 确定约束条件
2.1.2 线性规划问题 建模步骤
资源分配问题 （ resource-allocation）
成本收益平衡问题 （ cost-benefit-trade-off）
网络配送问题 （ distribution-network）
混合问题 （ mixed Problem）
2.1.3线性规划问题主要类型
资源分配问题 （ resource-allocation）
资源分配（ resource-allocation） 问题是将有限的资源 分配到各种活动中去的线性规划问题。这一类问题的 共性是在线性规划模型中每一个函数限制均为资源限 制
(resource constraint),并且每一种有限资源都可以表现为如下的形式：
使用的资源数量?可用的资源数量收集数据
问题所有活动可获得使用的每种资源的有限数量
每一种活动所需要的各种资源的数量,每一种资源
与活动的组合,单位活动消耗资源量必须首先估计
每一种活动对总的绩效测度的单位贡献
2.1.3线性规划问题主要类型
产品组合问题
资金预算问题资源分配问题举例
成本收益平衡问题（ Cost-benefit-trade-off Problem ）
是一类线性规划问题，这类问题中，通过选择各种 活动水平的组合，从而以最小的成本来实现最低可 接受的各种收益的水平。这类问题的共性是，
所有 的函数约束均为收益约束，并具有如下的形式：
完成的水平? 最低可接受的水平成本收益平衡问题
合理配料问题（饮食问题 ）
由多种原料制成含有 m种成份的产品，已知产品中所含各种成份的比例要求，并且知道各种原料所含成份的数量，问应如何配料，才能使产品的成本最低成本收益平衡问题举例例 根据对 77种食物所含的九种营养素：热量（糖与脂肪）、蛋白质、钙、铁、维生素 A,维生素 B1,维生素 B2,草酸与维生素 C
的成份及食物的市场价格调查，按照医生所提出的对每个人每天所需的营养要求，可得表食 物 每天的最低需要量营养成份 A B C D
维生素 A（ 国际单位） 1000 1500 1750 3250 4000
维生 B（ 毫克） 0.6 0.27 0.68 0.3 1
维生素 C（ 毫克） 17.5 7.5 0 30 1.305
单 价（元） 0.8 0.5 0.9 1.5
成本收益平衡问题举例问题,怎样采购食物才能保证在营养要求的前提下花费最省？
解：设每天购买甲、乙、丙、丁四种食物的数量分别为 x1,x2,x3,
x4
4321 5.19.05.08.0m in xxxxZ
0,,,
30305.75.17
13.068.027.06.0
40003250175015001000
..
4321
421
4321
4321
)(
)(
)(
xxxx
xxx
xxxx
xxxx
ts
C
B
A
的需求限制对维生素的需求限制对维生素的需求限制对维生素应购买甲乙丁食品分别约为 0.72,2.03及 0.075单位
69942.1
07496659.00
0258813.271753675.0
43
21
Z
xx
xx
最优解：
工作人员排程 问题,航空公司正准备增加其中心机场的来往航班，因此需要雇佣更多的客户服务代理商，但是不知道到底需要雇佣多少代理商。为了在保证向客户提供令人满意的服务水平的同时能尽量控制成本，要求管理人员研究如何规划人员才能以最小的成本提供令人满意的服务。
分析研究新的航班时间表，发现一天中不同时间的航班数有很大偏差，因而不同时段为实现客户满意水平必须工作的代理商数目也有差别。另一方面，公司与代理商所定协议上规定每一代理商工作 8小时为一班，个班时间安排如下：
轮班 1,6:00AM~2:00PM 轮班 2,8:00AM~4:00PM
轮班 3：中午 ~8:00PM 轮班 4,4:00PM ~午夜轮班 5,10:00PM ~6:00AM
成本收益平衡问题举例
工作人员排程 问题成本收益平衡问题举例轮班的时间时段 1 2 3 4 5 6
6:00AM~8:00AM
8:00AM ~10:00AM
10:00AM ~中午中午 ~2:00PM
2:00PM ~4:00PM
4:00PM ~6:00PM
6:00PM ~8:00PM
8:00PM ~10:00PM
10:00PM ~午夜午夜 ~6:00AM
170 160 175 180 195
例 2
工厂生产 A,B两种产品,每个产品经过两道工序的加工 。
产品 工序一 工序二
A 加工 2小时 加工 3小时
B 加工 3小时 加工 4小时可利用工时 15 25
在每生产一吨 B的同时,可得到两吨副产品 C
A每吨盈利 400元,B每吨盈利 800元销售一吨 C盈利 300元 报废每吨 C损失 200元市场预测,C最大销量为 5吨决定 A,B的产量,使工厂总的盈利最大 。
单位 C产品对总利润的贡献非线性例 2
C的利润
C的数量
5
C产品对总利润的贡献为分段线性函数，将 C产品拆分为销量与报废量两部分。每一部分均为线性函数。
设 A,B产品的生产量分别为 x1,x2，
C产品销量 x3,报废量 x4
C产品销售量 x3 ≤5
利润总值 Z=400x1 +800x2 +300x3 -200x4
C产品数量 2x2 -x3- x4=0
非负约束 x1,x2,x3,x4≥０
工序 1工时 2x1＋ 3x2≤15
工序 2工时 3x1＋ 4x2≤25
例 2
4321 2384m a x xxxxZ
0,0,0,0
5
02
2543
1532
4321
3
432
21
21
xxxx
x
xxx
xx
xx
最优解 x1= 3.75,x2=2.5,x3=5,x4=0
最优值 Ｚ = 5000
例 2
注意：在以下两种情况可以将分段线性函数拆分：
例 2
目标函数为极大化、
边际贡献递减。
目标函数为极小化、
边际贡献递增减例 3(批发商问题 ) 批发商欲制订下半年的进货与销售计划。
经过市场调查及预测，下半年的价格变化情况如下表所示：
7 8 9 10 11 12
进货价格 Pi 25 23 19 24 27 30
销售价格 Si 28 25 22 27 31 35
假设 6月底尚有库存量为 100；最大库容为 1000；每月仅在 1号进货一次；所进商品必须存放在仓库内。试依据上述信息，为该批发商制订下半年的进货与销售计划。
线性规划建模例 3解 1
约束条件设第 i月的进货量为 xi ； 第 i月的销售量为 yi
目标：毛利 Z最大。目标函数为,
12
7
12
7
m a x
i
ii
i
ii xpysZ？
库容约束：月初库存量不能超过最大库容量
1 0 0 01 0 07x
1 0 0 01 0 0 877 xyx
1 0 0 01 0 0
11
7
12
7
i
i
i
i yx
Are there any more constrains?
线性规划建模例 3解 1
销售量约束：当月销售量不能超过月初库存量
1008787 xxyy
100
12
7
12
7
i
i
i
i xy
10077 xy
线性规划建模例 3解 1
12
7
12
7
m a x
i
ii
i
ii xpysZ
1 0 0 01 0 07x
1 0 0 01 0 0 877 xyx
1 0 0 01 0 0 11
7
12
7
i
i
i
i yx
1008787 xxyy
10012
7
12
7
i
i
i
i xy
10077 xy
12~7,0,0 iyx ii
s.t.
线性规划建模例 3解 2
设第 i月月初的库存量为 xi ； 第 i月月底的库存量为 yi
目标函数,
12
7
1
12
7
)()(m a x
i
iii
i
iii yxpyxsZ
库容约束,12~7 1 0 0 0 ix i
销售量约束,12~7 0 iy
i
库存量约束,12~7
1 iyx ii
12~7 iyx ii
线性规划建模考虑更多的因素：
1、计划期末库存量为 a。
2,流动资金因素，假设批发商在计划期初拥有的流动资金为 K,进货时支出，销售后资金回收。
例 3
如何建立线性规划模型？
线性规划建模例 4
例 4配套问题 产品 P由 1个部件 A,2个部件 B组成；各部件由工厂的甲、乙车间生产，有关信息如下：
甲车间 A B 总工时所需工时 5 3 2000
所需材料 8 5
乙车间 A B 总工时所需工时 4 5 3000
所需材料 7 6
工厂可供调配的原材料为 2500。制订使产品数量达到最大的生产计划。
线性规划建模例 4解 1
设甲车间生产部件 A的数量为 x1； B的数量为 x2
乙车间生产部件 A的数量为 x3； B的数量为 x4
目标：产品的数量 Z
2,m i n
42
31
xxxxZ
2,m i n
42
31
xxxxy记
2
xx
y
xxy
y
42
31
m ax
线性规划建模例 4解 1
yZ?m ax
4~1,0 ix i
s.t,2/)(
42
31
xxy
xxy
2 5 0 06758
3 0 0 054
2 0 0 035
4321
31
31
xxxx
xx
xx
线性规划建模例 4解 1 线性规划建模
)(),(m in xgxfy?
)(
)(
max
xgy
xfy
y
x
y
f(x)g(x)
)(),(m a x xgxfy?
)(
)(
min
xgy
xfy
y
x
y
f(x) g(x)
例 4解 2
31m a x xxZ
4~1,0 ix i
s.t,2/)( 4231 xxxx
2 5 0 06758
3 0 0 054
2 0 0 035
4321
31
31
xxxx
xx
xx
线性规划建模线性规划建模例 5
某工厂生产 A,B,C三种产品，产品生产按照合同进行管理。
现欲根据订货合同以及生产状况制定 5月份的生产计划。已知合同甲的内容为,A产品 1000件，单件价格为 500元，违约金为 100元 /
件； B产品 800件，单件价格为 400元，违约金为 120元 /件；合同乙：
C产品 500件，单件价格为 400元，违约金为 120元 /件；合同丙,B
产品 600件，单件价格为 420元，违约金为 130元 /件； C产品 600件，
单件价格为 390元，违约金为 90元 /件；有关各产品生产过程所需工时以及原材料的情况见表 1，试以利润为目标，建立该工厂的生产计划线性规划模型（不求解）。
工序 1 工序 2 原材料 1 原材料 2 其它成本 /件产品 A 2 2 3 4 10
产品 B 1 3 2 3 10
产品 C 2 2 4 2 10
总工时（原材料） 4600 6000 10000 8000
工时原材料成本（元） 15 10 20 40
线性规划建模例 6
张三计划在火车站附近办一某 24小时提供服务的日夜服务社。通过调查分析，张三打算将一天分为 6个时间段，每个时间段为一个班，每班 4小时。每个服务员连续上 2个班。此外了解到在一天的不同班次服务社所需要的服务员的最少人数见下表。在正式营业前，张三需要招聘服务员。试以服务员的编制为目标，建立使编制最小的线性规划模型（不求解）。
班次 1 2 3 4 5 6
时段 8:00--12:00 12:00--16:00 16:00--20:00 20:00--24:00 0:00--4:00 4:00--8:00
人数 8 10 9 12 6 4
现有 50套某种大型成套设备要装入一艘远洋货轮运走,每套设备由两个大型部件组成,各部件的重量,体积如下表 1所示 。 已知货轮有两个货舱,每个货舱的载重量与容积如下表 2所示 。 每套设备的运费为 50万元
,装不走的设备可以留下,航行安全要求各舱的实际载重之比与它们的载重能力之比的误差不超过 10％,试建立线性规划模型 （ 不求解；忽略整数要求 ） 。
部件 重量（吨） 体积 (m3 )
1 250 70
2 80 100
货舱 载重（吨） 容积 (m3 )
1 6000 4500
2 4000 3000
线性规划建模例 7
表 1
表 2
某甲工厂厂长欲为其所生产的 A,B,C 三种产品制定第一季度的生产销售计划,各部门汇报的信息如下,
生产部,A,B,C 三种产品的生产成本依次为 56,31,42元 ; 生产单位产品所需原材料 1依次为 2,1,2公斤 ; 原材料 2依次为 3,2,1公斤,所需工时依次为
3,2,3; 工厂第一季度可使用的最大工时数为 300000.
物资部,工厂第一季度可使用的原材料 1为 200000公斤,原材料 2为 250000
公斤,原材料的购入价依次为 6,7元,
销售部,A,B,C 三种产品的销售成本依次为 2,3,2元 ; 销售价格依次为 75,
52,63元 ;市场容量依次为 20000,10000,10000;其中若采用促销手段,则可使
B产品的市场容量增加 5,000,增加部分的销售成本 4元,价格为 50元,
仓库,A,B,C 三种产品的现有库存量依次为 1000,800,1500; 第一季度末的保险库存量依次为 1500,1800,1000,
厂办公室,接乙工厂电话,该厂请甲厂转让一部分原材料 1,转让价格为 7.8
元 /公斤,
试建立此问题的 LP模型,
线性规划建模例 8
线性规划建模例 8解设产品 A,B,C生产的数量依次为 x1,x2,x3件；
A的销售量为 y1件,B的正常销售量为 y21件、促销销售量为 y22件、
C的销售量为 y3件；转让原材料的数量为 w。
目标函数,Z = 75y1 +52y21 +50y22 +63y3 –(2y1 +3y21 +4y22 +2y3 )
–(56x1 +31x2 +42x3 )+1.8w
约束条件,资源约束 3个市场容量约束 4个期终库存约束 3个生产成本为,56x1 +31x2 +42x3
销售收入为,75y1 +52y21 +50y22 +63y3
销售成本为,2y1 +3y21 +4y22 +2y3
线性规划模型的求解寻找求解方法的思路二,线性规划模型解的性质与模型的求解
Max(或 Min) CXZ?
0X
bAXts ),(..
确定一个体现线性规划模型的特殊代表构建针对该代表的求解方法基于线性规划模型的性质
1,线性规划模型的标准型与标准化
2,线性规划模型解的基本概念及其性质
3,求解线性规划模型的单纯型法线性规划模型的求解线性规划标准型的主要特征：
① 目标最大；
② 约束等式；
③ 变量非负；
④ 右端非负 。
nn xcxcxcZ2211m a x
0,,,
..
21
2211
22222121
11212111
n
mnmnmm
nn
nn
xxx
bxaxaxa
bxaxaxa
bxaxaxa
ts
标准型的矩阵形式：
CXZ?m a x
0.,X
bAXts
线性规划模型的求解把一般的 LP化成标准型的过程称为线性规划问题的标准化。
jjj xxx
0, jxx
jj xx 0jx
f(x)
-f(x)
1 目标标准化
2 化不等式约束为等式约束
3 变量非负化
1032 1032 32121 xxxxx
1032 1032 32121 xxxxx
加松弛变量
min Z = - max ( - Z )
减剩余变量
xj? 0
xj 自由变量
4 右端非负作变换线性规划模型的求解标准化
321 32m i n xxxZ
符号不受限制
321
321
321
321
,0,
13
823
10
..
xxx
xxx
xxx
xxx
ts
654321 00)(32m a x xxxxxxZ
0,,,,,
1)(3
8)(23
10)(
..
654321
4321
64321
54321
xxxxxx
xxxx
xxxxx
xxxxx
ts
线性规划模型的求解解的基本概念可行解,变量满足所有约束条件的一组值可行解集,所有可行解构成的集合可行域,可行解集构成 n维空间的区域
0x
bAX }0{ xb,Ax|xD
CXZ?m a x
0.,X
bAXts
线性规划模型的求解最优解,使得目标函数达到最优的可行解最优值,最优解对应的目标函数值目的,求最优解和最优值求解方法,单纯形法
CXZ?m a x
0.,X
bAXts
线性规划模型的求解先研究 AX=b
设 系数矩阵 A是 m× n矩阵，秩为 m，
B是 A中 m× m阶非奇异子矩阵（即 |B|≠0）,则称 B是线性规划问题的一个 基 。
B 是由 m个线性独立的列向量组成
),,,( 21 mrrr pppB
),,2,1( mjx rj
基向量基变量非基变量,其余变量线性规划模型的求解
AX=BXB+NXN=b
令 非基变量 XN=0 得 BXB=b 和特解 XB =B-1b
结合 XN=0 称为对应于 B的基本解基本解个数 =基的个数 ≤Cnm
基本可行解 可行的基本解
XB≥0 XN=0
可行基：对应的基本解也是可行解
N
BT
n X
X
xxxX ),,,( 21?
A=（ B | N）
线性规划模型的求解图解法用作图的方法确定可行域，判断目标函数的大小，达到求解的目的适用对象,仅有两个变量的 LP问题步骤：
建立平面坐标系
图解约束条件和非负条件
做目标函数等值线
平移目标函数等值线
联立求解相应约束条件线性规划模型的求解用图解法求解下面的线性规划问题：
2x1+5x2=14
2x1+5x2=0
-x1+2x2=2
x1+x2=4
0 1 2 3 4 x1
x2
I
4
3
2
1
F
E
H
A
B
C
D
G
x1-x2=2
21 52m a x xxZ
0,0
2
22
4
..
21
21
21
21
xx
xx
xx
xx
ts
B点 (2,2)为最优解点线性规划模型的求解用图解法求解下面的线性规划问题：
21 22m a x xxZ
0,0
2
22
4
..
21
21
21
21
xx
xx
xx
xx
ts 2x1+2x2=0
-x1+2x2=2
x1+x2=4
0 1 2 3 4 x1
x2
I
4
3
2
1
F
E
H
A
B
C
D
G
x1-x2=2
2x1+2x2=6
线段 BC上的所有点均为最优解点线性规划模型的求解用图解法求解下面的线性规划问题：
21 2m in xxZ
0,0
3
02
..
21
1
21
xx
x
xx
ts
0 1 2 3 4 x1
x1=3
x2
3
2
1
-x1+2x2=0x
1+2x2=4
x1+2x2=6
原点为最优解点线性规划模型的求解用图解法求解下面的线性规划问题：
21 5.175.0m i n xxZ
0,0
3
02
..
21
1
21
xx
x
xx
ts
0 1 2 3 4 x1
x1=3
x2
3
2
1
-x1+2x2=0
-0.75x1+1.5x2=3
O
A
线段 OA上的所有点均为最优解点线性规划模型的求解用图解法求解下面的线性规划问题：
21 2m a x xxZ
0,0
3
02
..
21
1
21
xx
x
xx
ts
0 1 2 3 4 x1
x1=3
x2
3
2
1
-x1+2x2=0
-x1+2x2=4
不存在有限最优解线性规划模型的求解可行域 D
空集有界集无界集最优解无最优解唯一最优解无穷多个最优解无有限最优解线性规划模型的求解猜想 1
线性规划的可行域是凸集；
猜想 2
最优解若存在,则可以在可行域的顶点上得到；
猜想 3
可行域的顶点的个数是有限的；
猜想 4
若有两个最优解，则其连线上的点也是最优解，即最优解有无穷多个可行域
D
A
B
C
E
线性规划模型的求解线性规划问题基本可行解的意义,
21 52m a x xxZ
0,0
2
22
4
..
21
21
21
21
xx
xx
xx
xx
ts
21 52m a x xxZ
0,,,,
2
22
4
..
54321
521
421
321
xxxxx
xxx
xxx
xxx
ts
10011
01021
00111
A
线性规划模型的求解
011
021
111
1B
0
0
5
4
x
x
令取基有
2
22
4
21
21
321
xx
xx
xxx 解方程得
0
0
6
4
6
1
X
0
0
5
3
x
x令取基有
2
22
4
21
421
21
xx
xxx
xx 解方程得
0
3
0
1
3
2
X
011
121
011
2B
线性规划模型的求解
4
0
6
0
2
,
0
4
2
0
2
,
2
0
0
2
2
,
0
3
0
1
3
,
0
0
6
4
6
54321
XXXXX
2
2
4
0
0
,
6
8
0
4
0
,
3
0
3
1
0
,
0
6
6
2
0
,
2
6
0
0
4
109876
XXXXX
同样得到基本可行解均为可行域的顶点线性规划模型的求解可行域
D
A
B
C
E
猜想 5
对于标准型的线性规划,X是可行域顶点的充分必要条件是
X是基本可行解 。
如何找到是最优解的哪个顶点？
线性规划模型的求解瞎子如何能够自己爬到山顶？
线性规划模型的求解
1、初始位置
2、判断何处比当前位置高的规则及实现从当前位置向上走一步的方法
3、判断已经到达最高点的准则
1、确定初始基本可行解
2、判断能够使目标值变优的顶点并实现转移
3、判断最优的准则
？
线性规划模型的求解单纯形法的思路从某一基本可行解转移到另一个基本可行解,并在转移过程中逐步使目标值变优直至最优 。
单纯形方法引例
321 332m a x xxxZ
0,,
974
3
321
321
321
)(
)(
xxx
xxx
xxx
材料约束工时约束
54321 00332m a x xxxxxZ
0~
974
3
51
5321
4321
xx
xxxx
xxxx
9
3
10741
01111 bA
线性规划模型的求解引例
54321 00332m a x xxxxxZ
0~
974
3
51
5321
4321
xx
xxxx
xxxx
得到初始基本可行解（ 0,0,0,3,9）
10741
01111A
取 x4 x5为基变量,0
321 xxx
令非基变量
9,3 54 xx解出从约束中解出基变量，代入目标函数有：
3214 3 xxxx
3215 749 xxxx
321 332 xxxZ
用非基变量表示基变量用非基变量表示目标函数当 x1(或 x2,x3)增加一个单位时，会使目标值增加 2（或 3）单位线性规划模型的求解取 x1增大，应该确定其增大的上限?
3214 3 xxxx
3215 749 xxxx
x1增大时，其余非基变量保持为零，称 x1进基
9
3
5
4
x
x 09,03
取 x1进基时，应该保持所有基变量非负，哪个基变量先成为零，哪个基变量成为非基变量，称这个基变量出基。
319,13m in
X4出基线性规划模型的求解令非基变量等于 0，得到新的基本可行解（ 3,0,0,0,6）
与 Z = 6
4325
4321
636
3
xxxx
xxxx
3214 3 xxxx
3215 749 xxxx
43232432 2633)3(2 xxxxxxxxZ
用新的非基变量表示基变量用新的非基变量表示目标函数取 x2进基
25
21
36
3
xx
xx 2
3
6,
1
3m i n
2
x
X5出基，材料用完线性规划模型的求解新的基本可行解（ 1,2,0,0,0），目标值 Z=8
4325
4321
636
3
xxxx
xxxx
5431 3
1
3
41 xxxx
5432 3
1
3
122 xxxx
43543 23
1
3
1226 xxxxxZ
543 3
58 xxx
用新的非基变量表示基变量用新的非基变量表示目标函数由于当前任何非基变量入基会使目标值变小，所以当前的基本行解（ 1,2,0,0,0）为最优解，最优值为 Z=8
线性规划模型的求解用非基变量表示基变量用非基变量表示目标函数此时目标函数中非基变量的系数称为该变量的检验数，
表示为?j
判别定理：若对于所有非基变量，检验数均非正
（?j≤0），则当前基本可行解最优。
线性规划模型的求解方法步骤总结,
1 确定 （ 观察法 ） 一个初始基本可行解；
2 从约束中解出基变量 （ 用非基变量表示基变量 ） ；
3 代入目标消去基变量 （ 用非基变量表示目标函数 ）,得到非基变量 xj的检验数?j。
4 判断最优 。 若?j≤0,当前解最优；
若?k >0,则选 xk进基
5 用最小比值法确定 xk的最大值 θ,使基变量 xl
取 0值,其它基变量非负,即 xl出基,若 θ不存在,则 Z→∞,没有有限最优解 。
6 重复上述 1到 5的工作 。
线性规划模型的求解
2.1 线性规划模型的建立
2.2 线性规划模型的求解
2.3 对偶原理及灵敏度分析
2.4 运输问题表 1-1 每吨产品工时、材料消耗表产品生产每吨 产品所需资源资 源 A B C
工 时材 料
1 1 1
1 4 7
在生产管理和经营活动中经常提出的一类问题是：如何合理地利用有限的人力,物力,财力等资源,以便获得最好的经济效益 。
引例,资源配置,某工厂生产 A,B,C三种产品,每吨利润分别为 2000
元,3000元,3000元；生产单位产品所需的工时及原材料如表 1-1所示 。
若供应的原材料每天不超过 9t,所能利用的劳动力日总工时为 3个单位,
问如何制定日生产计划,使三种产品总利润最大？
2.1 线性规划模型的建立问题：工时和材料的日可供量已知,求使利润最大的生产方案解：产品 A,B,C的日生产量,x1,x2,x3
每日工时 = x1 + x2 + x3
每日消耗材料量 = x1 + 4x2 + 7x3
每天可得利润（以千元为单位）
Z = 2x1 + 3x2 + 3x3
工时约束材料约束非负约束
321 332m a x xxxZ
0,0,0
974
3
..
321
321
321
xxx
xxx
xxx
ts
利润最大
2.1 线性规划模型的建立
模型的组成部分（ Components of the Model）
1,决策变量 （ Decision variables）
2,目标函数 （ Objective function）
3,约束 （ Constraints）
定义,对于求取一组变量 xj(j=1,2,…..,n),使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。
2.1 线性规划模型的建立
2.1.1 线性规划模型的概念
max（ 或 min）
自由,00,,,
),(
),(
),(
..
21
2211
22222121
11212111
n
mnmnmm
nn
nn
xxx
bxaxaxa
bxaxaxa
bxaxaxa
ts
nn xcxcxcZ2211
目标函数（线性）
约束条件
（线性）
非负约束称为决策变量 ),,2,1( njx j
称为价值系数或目标函数系数 ),,2,1( njc
j
称为资源常数或约束右端常数 ),,2,1( mib i
称为技术系数或约束系数
),,2,1,,,2,1( njmia ij
线性规划模型的 一般形式,
紧缩形式：
线性规划建模
max(或 min)
n
j
jj xcZ
1
njx
bxa
ts
j
n
j
ijij
,,2,10
),(
.,1
i=1,2,…..,n
线性规划的假设
1,线性 （ Linearity）
2,可分性 （ Divisibility ）
3,确定性 （ Certainty）
4,非负性 （ Nonnegativity）
线性规划模型的 一般形式,
矩阵形式：
Max(或 Min) CXZ?
0X
bAXts ),(..
称为决策变量向量
nx
x
x
X
2
1
称为价值系数向量或目标函数系数向量 ),,,(
21 ncccC
称为技术系数或约束系数矩阵
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
称为资源常数向量或约束右端常数向量
m
b
b
b
b
2
1
线性规划建模线性规划模型特点：
① 用一组未知变量 （ 决策变量 ） 表示要求的方案 。
通常,根据决策变量所代表的事物的特点可以对变量的取值加以约束,例如非负约束 。
② 存在一定的限制条件,通常称为约束条件,这些约束条件可以用一组线性等式或者线性不等式来表示 。
③ 有一个目标要求,并且可以表示为决策变量的线性函数,称为目标函数,按所研究问题的不同,要求目标函数实现最大化或者最小化 。
线性规划建模
需要做哪些决策？决策变量是什么
问题的目标是什么？写出目标函数
资源和需求之间的情况如何？ 确定约束条件
2.1.2 线性规划问题 建模步骤
资源分配问题 （ resource-allocation）
成本收益平衡问题 （ cost-benefit-trade-off）
网络配送问题 （ distribution-network）
混合问题 （ mixed Problem）
2.1.3线性规划问题主要类型
资源分配问题 （ resource-allocation）
资源分配（ resource-allocation） 问题是将有限的资源 分配到各种活动中去的线性规划问题。这一类问题的 共性是在线性规划模型中每一个函数限制均为资源限 制
(resource constraint),并且每一种有限资源都可以表现为如下的形式：
使用的资源数量?可用的资源数量收集数据
问题所有活动可获得使用的每种资源的有限数量
每一种活动所需要的各种资源的数量,每一种资源
与活动的组合,单位活动消耗资源量必须首先估计
每一种活动对总的绩效测度的单位贡献
2.1.3线性规划问题主要类型
产品组合问题
资金预算问题资源分配问题举例
成本收益平衡问题（ Cost-benefit-trade-off Problem ）
是一类线性规划问题，这类问题中，通过选择各种 活动水平的组合，从而以最小的成本来实现最低可 接受的各种收益的水平。这类问题的共性是，
所有 的函数约束均为收益约束，并具有如下的形式：
完成的水平? 最低可接受的水平成本收益平衡问题
合理配料问题（饮食问题 ）
由多种原料制成含有 m种成份的产品，已知产品中所含各种成份的比例要求，并且知道各种原料所含成份的数量，问应如何配料，才能使产品的成本最低成本收益平衡问题举例例 根据对 77种食物所含的九种营养素：热量（糖与脂肪）、蛋白质、钙、铁、维生素 A,维生素 B1,维生素 B2,草酸与维生素 C
的成份及食物的市场价格调查，按照医生所提出的对每个人每天所需的营养要求，可得表食 物 每天的最低需要量营养成份 A B C D
维生素 A（ 国际单位） 1000 1500 1750 3250 4000
维生 B（ 毫克） 0.6 0.27 0.68 0.3 1
维生素 C（ 毫克） 17.5 7.5 0 30 1.305
单 价（元） 0.8 0.5 0.9 1.5
成本收益平衡问题举例问题,怎样采购食物才能保证在营养要求的前提下花费最省？
解：设每天购买甲、乙、丙、丁四种食物的数量分别为 x1,x2,x3,
x4
4321 5.19.05.08.0m in xxxxZ
0,,,
30305.75.17
13.068.027.06.0
40003250175015001000
..
4321
421
4321
4321
)(
)(
)(
xxxx
xxx
xxxx
xxxx
ts
C
B
A
的需求限制对维生素的需求限制对维生素的需求限制对维生素应购买甲乙丁食品分别约为 0.72,2.03及 0.075单位
69942.1
07496659.00
0258813.271753675.0
43
21
Z
xx
xx
最优解：
工作人员排程 问题,航空公司正准备增加其中心机场的来往航班，因此需要雇佣更多的客户服务代理商，但是不知道到底需要雇佣多少代理商。为了在保证向客户提供令人满意的服务水平的同时能尽量控制成本，要求管理人员研究如何规划人员才能以最小的成本提供令人满意的服务。
分析研究新的航班时间表，发现一天中不同时间的航班数有很大偏差，因而不同时段为实现客户满意水平必须工作的代理商数目也有差别。另一方面，公司与代理商所定协议上规定每一代理商工作 8小时为一班，个班时间安排如下：
轮班 1,6:00AM~2:00PM 轮班 2,8:00AM~4:00PM
轮班 3：中午 ~8:00PM 轮班 4,4:00PM ~午夜轮班 5,10:00PM ~6:00AM
成本收益平衡问题举例
工作人员排程 问题成本收益平衡问题举例轮班的时间时段 1 2 3 4 5 6
6:00AM~8:00AM
8:00AM ~10:00AM
10:00AM ~中午中午 ~2:00PM
2:00PM ~4:00PM
4:00PM ~6:00PM
6:00PM ~8:00PM
8:00PM ~10:00PM
10:00PM ~午夜午夜 ~6:00AM
170 160 175 180 195
例 2
工厂生产 A,B两种产品,每个产品经过两道工序的加工 。
产品 工序一 工序二
A 加工 2小时 加工 3小时
B 加工 3小时 加工 4小时可利用工时 15 25
在每生产一吨 B的同时,可得到两吨副产品 C
A每吨盈利 400元,B每吨盈利 800元销售一吨 C盈利 300元 报废每吨 C损失 200元市场预测,C最大销量为 5吨决定 A,B的产量,使工厂总的盈利最大 。
单位 C产品对总利润的贡献非线性例 2
C的利润
C的数量
5
C产品对总利润的贡献为分段线性函数，将 C产品拆分为销量与报废量两部分。每一部分均为线性函数。
设 A,B产品的生产量分别为 x1,x2，
C产品销量 x3,报废量 x4
C产品销售量 x3 ≤5
利润总值 Z=400x1 +800x2 +300x3 -200x4
C产品数量 2x2 -x3- x4=0
非负约束 x1,x2,x3,x4≥０
工序 1工时 2x1＋ 3x2≤15
工序 2工时 3x1＋ 4x2≤25
例 2
4321 2384m a x xxxxZ
0,0,0,0
5
02
2543
1532
4321
3
432
21
21
xxxx
x
xxx
xx
xx
最优解 x1= 3.75,x2=2.5,x3=5,x4=0
最优值 Ｚ = 5000
例 2
注意：在以下两种情况可以将分段线性函数拆分：
例 2
目标函数为极大化、
边际贡献递减。
目标函数为极小化、
边际贡献递增减例 3(批发商问题 ) 批发商欲制订下半年的进货与销售计划。
经过市场调查及预测，下半年的价格变化情况如下表所示：
7 8 9 10 11 12
进货价格 Pi 25 23 19 24 27 30
销售价格 Si 28 25 22 27 31 35
假设 6月底尚有库存量为 100；最大库容为 1000；每月仅在 1号进货一次；所进商品必须存放在仓库内。试依据上述信息，为该批发商制订下半年的进货与销售计划。
线性规划建模例 3解 1
约束条件设第 i月的进货量为 xi ； 第 i月的销售量为 yi
目标：毛利 Z最大。目标函数为,
12
7
12
7
m a x
i
ii
i
ii xpysZ？
库容约束：月初库存量不能超过最大库容量
1 0 0 01 0 07x
1 0 0 01 0 0 877 xyx
1 0 0 01 0 0
11
7
12
7
i
i
i
i yx
Are there any more constrains?
线性规划建模例 3解 1
销售量约束：当月销售量不能超过月初库存量
1008787 xxyy
100
12
7
12
7
i
i
i
i xy
10077 xy
线性规划建模例 3解 1
12
7
12
7
m a x
i
ii
i
ii xpysZ
1 0 0 01 0 07x
1 0 0 01 0 0 877 xyx
1 0 0 01 0 0 11
7
12
7
i
i
i
i yx
1008787 xxyy
10012
7
12
7
i
i
i
i xy
10077 xy
12~7,0,0 iyx ii
s.t.
线性规划建模例 3解 2
设第 i月月初的库存量为 xi ； 第 i月月底的库存量为 yi
目标函数,
12
7
1
12
7
)()(m a x
i
iii
i
iii yxpyxsZ
库容约束,12~7 1 0 0 0 ix i
销售量约束,12~7 0 iy
i
库存量约束,12~7
1 iyx ii
12~7 iyx ii
线性规划建模考虑更多的因素：
1、计划期末库存量为 a。
2,流动资金因素，假设批发商在计划期初拥有的流动资金为 K,进货时支出，销售后资金回收。
例 3
如何建立线性规划模型？
线性规划建模例 4
例 4配套问题 产品 P由 1个部件 A,2个部件 B组成；各部件由工厂的甲、乙车间生产，有关信息如下：
甲车间 A B 总工时所需工时 5 3 2000
所需材料 8 5
乙车间 A B 总工时所需工时 4 5 3000
所需材料 7 6
工厂可供调配的原材料为 2500。制订使产品数量达到最大的生产计划。
线性规划建模例 4解 1
设甲车间生产部件 A的数量为 x1； B的数量为 x2
乙车间生产部件 A的数量为 x3； B的数量为 x4
目标：产品的数量 Z
2,m i n
42
31
xxxxZ
2,m i n
42
31
xxxxy记
2
xx
y
xxy
y
42
31
m ax
线性规划建模例 4解 1
yZ?m ax
4~1,0 ix i
s.t,2/)(
42
31
xxy
xxy
2 5 0 06758
3 0 0 054
2 0 0 035
4321
31
31
xxxx
xx
xx
线性规划建模例 4解 1 线性规划建模
)(),(m in xgxfy?
)(
)(
max
xgy
xfy
y
x
y
f(x)g(x)
)(),(m a x xgxfy?
)(
)(
min
xgy
xfy
y
x
y
f(x) g(x)
例 4解 2
31m a x xxZ
4~1,0 ix i
s.t,2/)( 4231 xxxx
2 5 0 06758
3 0 0 054
2 0 0 035
4321
31
31
xxxx
xx
xx
线性规划建模线性规划建模例 5
某工厂生产 A,B,C三种产品，产品生产按照合同进行管理。
现欲根据订货合同以及生产状况制定 5月份的生产计划。已知合同甲的内容为,A产品 1000件，单件价格为 500元，违约金为 100元 /
件； B产品 800件，单件价格为 400元，违约金为 120元 /件；合同乙：
C产品 500件，单件价格为 400元，违约金为 120元 /件；合同丙,B
产品 600件，单件价格为 420元，违约金为 130元 /件； C产品 600件，
单件价格为 390元，违约金为 90元 /件；有关各产品生产过程所需工时以及原材料的情况见表 1，试以利润为目标，建立该工厂的生产计划线性规划模型（不求解）。
工序 1 工序 2 原材料 1 原材料 2 其它成本 /件产品 A 2 2 3 4 10
产品 B 1 3 2 3 10
产品 C 2 2 4 2 10
总工时（原材料） 4600 6000 10000 8000
工时原材料成本（元） 15 10 20 40
线性规划建模例 6
张三计划在火车站附近办一某 24小时提供服务的日夜服务社。通过调查分析，张三打算将一天分为 6个时间段，每个时间段为一个班，每班 4小时。每个服务员连续上 2个班。此外了解到在一天的不同班次服务社所需要的服务员的最少人数见下表。在正式营业前，张三需要招聘服务员。试以服务员的编制为目标，建立使编制最小的线性规划模型（不求解）。
班次 1 2 3 4 5 6
时段 8:00--12:00 12:00--16:00 16:00--20:00 20:00--24:00 0:00--4:00 4:00--8:00
人数 8 10 9 12 6 4
现有 50套某种大型成套设备要装入一艘远洋货轮运走,每套设备由两个大型部件组成,各部件的重量,体积如下表 1所示 。 已知货轮有两个货舱,每个货舱的载重量与容积如下表 2所示 。 每套设备的运费为 50万元
,装不走的设备可以留下,航行安全要求各舱的实际载重之比与它们的载重能力之比的误差不超过 10％,试建立线性规划模型 （ 不求解；忽略整数要求 ） 。
部件 重量（吨） 体积 (m3 )
1 250 70
2 80 100
货舱 载重（吨） 容积 (m3 )
1 6000 4500
2 4000 3000
线性规划建模例 7
表 1
表 2
某甲工厂厂长欲为其所生产的 A,B,C 三种产品制定第一季度的生产销售计划,各部门汇报的信息如下,
生产部,A,B,C 三种产品的生产成本依次为 56,31,42元 ; 生产单位产品所需原材料 1依次为 2,1,2公斤 ; 原材料 2依次为 3,2,1公斤,所需工时依次为
3,2,3; 工厂第一季度可使用的最大工时数为 300000.
物资部,工厂第一季度可使用的原材料 1为 200000公斤,原材料 2为 250000
公斤,原材料的购入价依次为 6,7元,
销售部,A,B,C 三种产品的销售成本依次为 2,3,2元 ; 销售价格依次为 75,
52,63元 ;市场容量依次为 20000,10000,10000;其中若采用促销手段,则可使
B产品的市场容量增加 5,000,增加部分的销售成本 4元,价格为 50元,
仓库,A,B,C 三种产品的现有库存量依次为 1000,800,1500; 第一季度末的保险库存量依次为 1500,1800,1000,
厂办公室,接乙工厂电话,该厂请甲厂转让一部分原材料 1,转让价格为 7.8
元 /公斤,
试建立此问题的 LP模型,
线性规划建模例 8
线性规划建模例 8解设产品 A,B,C生产的数量依次为 x1,x2,x3件；
A的销售量为 y1件,B的正常销售量为 y21件、促销销售量为 y22件、
C的销售量为 y3件；转让原材料的数量为 w。
目标函数,Z = 75y1 +52y21 +50y22 +63y3 –(2y1 +3y21 +4y22 +2y3 )
–(56x1 +31x2 +42x3 )+1.8w
约束条件,资源约束 3个市场容量约束 4个期终库存约束 3个生产成本为,56x1 +31x2 +42x3
销售收入为,75y1 +52y21 +50y22 +63y3
销售成本为,2y1 +3y21 +4y22 +2y3
线性规划模型的求解寻找求解方法的思路二,线性规划模型解的性质与模型的求解
Max(或 Min) CXZ?
0X
bAXts ),(..
确定一个体现线性规划模型的特殊代表构建针对该代表的求解方法基于线性规划模型的性质
1,线性规划模型的标准型与标准化
2,线性规划模型解的基本概念及其性质
3,求解线性规划模型的单纯型法线性规划模型的求解线性规划标准型的主要特征：
① 目标最大；
② 约束等式；
③ 变量非负；
④ 右端非负 。
nn xcxcxcZ2211m a x
0,,,
..
21
2211
22222121
11212111
n
mnmnmm
nn
nn
xxx
bxaxaxa
bxaxaxa
bxaxaxa
ts
标准型的矩阵形式：
CXZ?m a x
0.,X
bAXts
线性规划模型的求解把一般的 LP化成标准型的过程称为线性规划问题的标准化。
jjj xxx
0, jxx
jj xx 0jx
f(x)
-f(x)
1 目标标准化
2 化不等式约束为等式约束
3 变量非负化
1032 1032 32121 xxxxx
1032 1032 32121 xxxxx
加松弛变量
min Z = - max ( - Z )
减剩余变量
xj? 0
xj 自由变量
4 右端非负作变换线性规划模型的求解标准化
321 32m i n xxxZ
符号不受限制
321
321
321
321
,0,
13
823
10
..
xxx
xxx
xxx
xxx
ts
654321 00)(32m a x xxxxxxZ
0,,,,,
1)(3
8)(23
10)(
..
654321
4321
64321
54321
xxxxxx
xxxx
xxxxx
xxxxx
ts
线性规划模型的求解解的基本概念可行解,变量满足所有约束条件的一组值可行解集,所有可行解构成的集合可行域,可行解集构成 n维空间的区域
0x
bAX }0{ xb,Ax|xD
CXZ?m a x
0.,X
bAXts
线性规划模型的求解最优解,使得目标函数达到最优的可行解最优值,最优解对应的目标函数值目的,求最优解和最优值求解方法,单纯形法
CXZ?m a x
0.,X
bAXts
线性规划模型的求解先研究 AX=b
设 系数矩阵 A是 m× n矩阵，秩为 m，
B是 A中 m× m阶非奇异子矩阵（即 |B|≠0）,则称 B是线性规划问题的一个 基 。
B 是由 m个线性独立的列向量组成
),,,( 21 mrrr pppB
),,2,1( mjx rj
基向量基变量非基变量,其余变量线性规划模型的求解
AX=BXB+NXN=b
令 非基变量 XN=0 得 BXB=b 和特解 XB =B-1b
结合 XN=0 称为对应于 B的基本解基本解个数 =基的个数 ≤Cnm
基本可行解 可行的基本解
XB≥0 XN=0
可行基：对应的基本解也是可行解
N
BT
n X
X
xxxX ),,,( 21?
A=（ B | N）
线性规划模型的求解图解法用作图的方法确定可行域，判断目标函数的大小，达到求解的目的适用对象,仅有两个变量的 LP问题步骤：
建立平面坐标系
图解约束条件和非负条件
做目标函数等值线
平移目标函数等值线
联立求解相应约束条件线性规划模型的求解用图解法求解下面的线性规划问题：
2x1+5x2=14
2x1+5x2=0
-x1+2x2=2
x1+x2=4
0 1 2 3 4 x1
x2
I
4
3
2
1
F
E
H
A
B
C
D
G
x1-x2=2
21 52m a x xxZ
0,0
2
22
4
..
21
21
21
21
xx
xx
xx
xx
ts
B点 (2,2)为最优解点线性规划模型的求解用图解法求解下面的线性规划问题：
21 22m a x xxZ
0,0
2
22
4
..
21
21
21
21
xx
xx
xx
xx
ts 2x1+2x2=0
-x1+2x2=2
x1+x2=4
0 1 2 3 4 x1
x2
I
4
3
2
1
F
E
H
A
B
C
D
G
x1-x2=2
2x1+2x2=6
线段 BC上的所有点均为最优解点线性规划模型的求解用图解法求解下面的线性规划问题：
21 2m in xxZ
0,0
3
02
..
21
1
21
xx
x
xx
ts
0 1 2 3 4 x1
x1=3
x2
3
2
1
-x1+2x2=0x
1+2x2=4
x1+2x2=6
原点为最优解点线性规划模型的求解用图解法求解下面的线性规划问题：
21 5.175.0m i n xxZ
0,0
3
02
..
21
1
21
xx
x
xx
ts
0 1 2 3 4 x1
x1=3
x2
3
2
1
-x1+2x2=0
-0.75x1+1.5x2=3
O
A
线段 OA上的所有点均为最优解点线性规划模型的求解用图解法求解下面的线性规划问题：
21 2m a x xxZ
0,0
3
02
..
21
1
21
xx
x
xx
ts
0 1 2 3 4 x1
x1=3
x2
3
2
1
-x1+2x2=0
-x1+2x2=4
不存在有限最优解线性规划模型的求解可行域 D
空集有界集无界集最优解无最优解唯一最优解无穷多个最优解无有限最优解线性规划模型的求解猜想 1
线性规划的可行域是凸集；
猜想 2
最优解若存在,则可以在可行域的顶点上得到；
猜想 3
可行域的顶点的个数是有限的；
猜想 4
若有两个最优解，则其连线上的点也是最优解，即最优解有无穷多个可行域
D
A
B
C
E
线性规划模型的求解线性规划问题基本可行解的意义,
21 52m a x xxZ
0,0
2
22
4
..
21
21
21
21
xx
xx
xx
xx
ts
21 52m a x xxZ
0,,,,
2
22
4
..
54321
521
421
321
xxxxx
xxx
xxx
xxx
ts
10011
01021
00111
A
线性规划模型的求解
011
021
111
1B
0
0
5
4
x
x
令取基有
2
22
4
21
21
321
xx
xx
xxx 解方程得
0
0
6
4
6
1
X
0
0
5
3
x
x令取基有
2
22
4
21
421
21
xx
xxx
xx 解方程得
0
3
0
1
3
2
X
011
121
011
2B
线性规划模型的求解
4
0
6
0
2
,
0
4
2
0
2
,
2
0
0
2
2
,
0
3
0
1
3
,
0
0
6
4
6
54321
XXXXX
2
2
4
0
0
,
6
8
0
4
0
,
3
0
3
1
0
,
0
6
6
2
0
,
2
6
0
0
4
109876
XXXXX
同样得到基本可行解均为可行域的顶点线性规划模型的求解可行域
D
A
B
C
E
猜想 5
对于标准型的线性规划,X是可行域顶点的充分必要条件是
X是基本可行解 。
如何找到是最优解的哪个顶点？
线性规划模型的求解瞎子如何能够自己爬到山顶？
线性规划模型的求解
1、初始位置
2、判断何处比当前位置高的规则及实现从当前位置向上走一步的方法
3、判断已经到达最高点的准则
1、确定初始基本可行解
2、判断能够使目标值变优的顶点并实现转移
3、判断最优的准则
？
线性规划模型的求解单纯形法的思路从某一基本可行解转移到另一个基本可行解,并在转移过程中逐步使目标值变优直至最优 。
单纯形方法引例
321 332m a x xxxZ
0,,
974
3
321
321
321
)(
)(
xxx
xxx
xxx
材料约束工时约束
54321 00332m a x xxxxxZ
0~
974
3
51
5321
4321
xx
xxxx
xxxx
9
3
10741
01111 bA
线性规划模型的求解引例
54321 00332m a x xxxxxZ
0~
974
3
51
5321
4321
xx
xxxx
xxxx
得到初始基本可行解（ 0,0,0,3,9）
10741
01111A
取 x4 x5为基变量,0
321 xxx
令非基变量
9,3 54 xx解出从约束中解出基变量，代入目标函数有：
3214 3 xxxx
3215 749 xxxx
321 332 xxxZ
用非基变量表示基变量用非基变量表示目标函数当 x1(或 x2,x3)增加一个单位时，会使目标值增加 2（或 3）单位线性规划模型的求解取 x1增大，应该确定其增大的上限?
3214 3 xxxx
3215 749 xxxx
x1增大时，其余非基变量保持为零，称 x1进基
9
3
5
4
x
x 09,03
取 x1进基时，应该保持所有基变量非负，哪个基变量先成为零，哪个基变量成为非基变量，称这个基变量出基。
319,13m in
X4出基线性规划模型的求解令非基变量等于 0，得到新的基本可行解（ 3,0,0,0,6）
与 Z = 6
4325
4321
636
3
xxxx
xxxx
3214 3 xxxx
3215 749 xxxx
43232432 2633)3(2 xxxxxxxxZ
用新的非基变量表示基变量用新的非基变量表示目标函数取 x2进基
25
21
36
3
xx
xx 2
3
6,
1
3m i n
2
x
X5出基，材料用完线性规划模型的求解新的基本可行解（ 1,2,0,0,0），目标值 Z=8
4325
4321
636
3
xxxx
xxxx
5431 3
1
3
41 xxxx
5432 3
1
3
122 xxxx
43543 23
1
3
1226 xxxxxZ
543 3
58 xxx
用新的非基变量表示基变量用新的非基变量表示目标函数由于当前任何非基变量入基会使目标值变小，所以当前的基本行解（ 1,2,0,0,0）为最优解，最优值为 Z=8
线性规划模型的求解用非基变量表示基变量用非基变量表示目标函数此时目标函数中非基变量的系数称为该变量的检验数，
表示为?j
判别定理：若对于所有非基变量，检验数均非正
（?j≤0），则当前基本可行解最优。
线性规划模型的求解方法步骤总结,
1 确定 （ 观察法 ） 一个初始基本可行解；
2 从约束中解出基变量 （ 用非基变量表示基变量 ） ；
3 代入目标消去基变量 （ 用非基变量表示目标函数 ）,得到非基变量 xj的检验数?j。
4 判断最优 。 若?j≤0,当前解最优；
若?k >0,则选 xk进基
5 用最小比值法确定 xk的最大值 θ,使基变量 xl
取 0值,其它基变量非负,即 xl出基,若 θ不存在,则 Z→∞,没有有限最优解 。
6 重复上述 1到 5的工作 。
线性规划模型的求解
