第10章 线性规划方法
线性规划的一般模型； 线性规划解的概念与理论； 线性规划的求解方法； 线性规划的软件求解方法； 线性规划的应用案例分析。
2020/8/12
数学建模方法及其应用（3）-- 韩中庚
2
一、线性规划的一般模型
1. 问题的提出
设某企业现有 m 种资源 Ai (i 1, 2, , m) 用于生产
现在要解决的问题： （1)如何求出第一个基可行解？ （2)如何判断基可行解是否为最优解？ （3)如何由一个基可行解过渡到另一个基可行解？
2020/8/12
数学建模方法及其应用（3）-- 韩中庚
11
三、线性规划的求解方法
2、线性规划的MATLAB求解
j 1
n
决策变量所受的约束条件为 max z c j x j
n
aij x j bi
(i 1, 2,
j1
x
j
0
( j 1, 2,
, n)
, m)
j 1
s.t.
n j 1
aij
xj
ቤተ መጻሕፍቲ ባይዱ
bi (i
1,2,, m)
称之为问题的约束条件。
x j 0 ( j 1,2,, n)
2020/8/12
基向量与非基向量：如果基为 B (aij )mm (P1, P2 ,, Pm ) ，
则称向量 Pj (a1j ,a2 j ,,amj)T ( j 1,2,,m) 为基向量，其它称
为非基向量；
基变量与非基变量：与基向量对应的决策变量
x j ( j 1,2,, m) 称为基变量，其它的变量称为非基变量。
c2
cn
2020/8/12
数学建模方法及其应用（3）-- 韩中庚
3
一、线性规划的一般模型
1. 问题的提出
建立数学模型：设产品 B j 产量为 x j ( j 1,2,, n) ，称之
为决策变量，所得的利润为 z ，则要解决的问题的目标是使得（利
n
润）函数 z c j x j 有最大值，称为目标函数。
0
A (aij ) mn 为 系 数 矩 阵 ；
Pj (a1j , a2 j ,, amj )T ( j 1,2,, n)
为约束方程组的系数向量。
2020/8/12
数学建模方法及其应用（3）-- 韩中庚
5
一、线性规划的一般模型
3 .线性规划模型的标准型
标准型: max z C X
max (min) z C X
数学建模方法及其应用（3）-- 韩中庚
4
一、线性规划的一般模型
2 .线性规划模型的一般形式
分量形式:
向量形式
n
max (min) z c j x j j 1
n
aij x j (, )bi (i 1,2,, m)
s.t. j1
max (min) z C X
s.t.
n
Pj x j
(, )b
（2）如果线性规划问题的可行域有无界，则问题可 能无最优解；若有最优解也一定在可行域的某个顶
点上达到。
2020/8/12
数学建模方法及其应用（3）-- 韩中庚
10
三、线性规划的求解方法
1、单纯形法的基本思想
寻求问题的一个基可行解(即可行域的顶点)；检 查该基可行解是否为最优解；如果不是，则设法再 求另一个没有检查过的基可行解,如此进行下去,直到 得到某一个基可行解为最优解为止。
A X b
A X (, )b
s.t.
X
0
s.t.
X
0
标
准
（1）最小化问题：令 z z ，则 maxz min z C X ；
化
（2）约束条件为不等式：对不等号“ () ”的约束
方 条件，则在“ () ”的左端加上（或减去）一个非负变 法 量（称为松弛变量）使其变为等式。 ： （ 3 ） 对 无 约 束 的 变 量 ： 如 x (,) ， 则 令
2 、线性规划解的基本理论
定理 1 如果线性规划问题存在可行解，则其可行域
n
D X Pj x j b, x j 0 是凸集。
j1
定理 2 线性规划问题的任一个基可行解 X 必对应于
可行域 D 的一个顶点。
定理3 （1）如果线性规划问题的可行域有界， 则问题的最优解一定在可行域的顶点上达到。
x x x ，使得 x, x 0 ，代入模型即可。
2020/8/12
数学建模方法及其应用（3）-- 韩中庚
6
二、线性规划解的概念与理论
1 .线性规划解的概念
（1）解：
max (min) z C X
s.t.
A X (, )b
X
0
可行解:满足约束条件的解 X (x1, x2 ,, xn )T ;
j1
X
0
x j 0 ( j 1,2,, n)
矩阵形式
max (min) z C X
C (c1, c2 ,, cn ) 为 系 数 向 量 ； X (x1 , x2 ,, xn )T 为决策向量； b (b1 , b2 ,, bm )T 为常数向量；
A X (, )b
s.t.
X
可行域:可行解的全体构成的集合，记为 D ；
最优解:使目标函数达到最大的可行解。
2020/8/12
数学建模方法及其应用（3）-- 韩中庚
7
1. 线性规划解的概念
（2）基
基：设系数矩阵 A (aij )mn 的秩为 m ，则称 A 的某个 m m 阶非奇异子矩阵 B( B 0) 为线性规划问题的一个基。
2020/8/12
数学建模方法及其应用（3）-- 韩中庚
8
1. 线性规划解的概念
（3）基解：设问题的基为
max z C X
B (aij )mm (P1 , P2 ,, Pm )
将约束方程组变为
s.t.
n
Pj x j b
j 1
m
n
Pj x j b Pj x j
X
0
j 1
j m 1
n 种产品 Bj ( j 1, 2, , n) ，
每种资源的拥有量 和每种产品所消耗
产品 资源
B1
A1
a11
的资源量，以及单 位产品的利润如下 表，试问如何安排 生产计划使得该企
A2
a 21
Am
a m1
利润
c1
业获利最大?
B2 Bn 总 量
a12
a1 n
b1
a 22
a2 n
b2
am2
a mn
bm
令 x j 0( j m 1,, n) ， 则 称 解 向 量
X (x1, x2 ,, xm ,0,,0)T 为问题的基解。
（4）基可行解：满足非负约束条件的基解称为基
可行解。
（5）可行基：对应于基可行解的基称为可行基。
2020/8/12
数学建模方法及其应用（3）-- 韩中庚
9
二、线性规划解的概念与理论