精品PPT课件----第七章 线性规划模型.ppt

线性规划模型
第七章
§1 线性规划问题
例1. 运输问题
要把某种货物从m个工厂 A1,A2, …,Am 运到n个商店 B1,B2, …,Bn去,其中各工厂的库存量为a1,a2, …, am,各商店的需求量为b1,b2, …,bn ,这里。已知从工厂Ai到商店Bj的运费(每一单位货物)Cij。现在要确定一个运输方案,即确定从Ai到Bj的运量xij(i=1,2, …,m,j=1,2,
…,n), 使在满足供求的条件下总的运费最小。
数
学
模
型

某饲养场所用的混合饲料由n种配料组成,要求这种混合饲料必须含m种不同营养成分,并且每一份混合饲料中第i种营养成分的含量不低于bi,已知每单位第j种配料中所含第i种营养成分的量为aij,每单位第j种配料的价格为cj。现在的问题是在保证营养的条件下,如何配方使混合饲料的费用最小?
数
学
模
型
以xj表示一份混合饲料中第j种配料的含量,则
§2 线性规划的标准形式
目标函数
约束条件
一般形式
矩阵形式
标准形式
化一般形式为标准形式
目标函数的转化
约束条件的转化
变量的非负约束的转化
x
y
0
§3 线性规划的一般理论
线性规划的图解法
可行域
A
B
C
D
最优解B(x1,x2)
可行解
一个向量x=(x1,x2, …,xn)如果满足所有的约束条件,则称之为线性规划的一个可行解。
全部可行解所构成的集合称为可行解集
使目标函数达到极小的可行解称为最优解。
可行域
最优解
线性规划可能发生的三种情况
(1)约束条件彼此不相容,可行解集是空的,因而(LP)问题无解;
(2)可行域是无界的,而且随着x趋向无穷,目标函数取任意小的值,此时不存在有限的最优解;
(3)至少存在一个最优解。以后仅研究情况(3)
上例中可行域与最优解的特点:
可行域是凸多边形(凸多胞形)
最优解是凸多边形的一个顶点

定义1 设S是Rn中的一个向量集,若对任意及
任意,有

则称S是一个凸集。
定义2 若S是一个凸集, ,但对任意
,均有,则称z是凸集S的一个顶点。
容易证明,线性规划问题(LP)的可行域是一个凸集


把看作一组自由变量,任意一组值,则可得到对应的的一组值,于是便是约束方程的一个解。令=0,则,我们把约束方程这种特殊形式的解称为基本解。
定义3 设B是矩阵A中的一个m阶满秩方阵,则称B为一个基;B中的m个线性无关的列向量称为基向量;x中与之对应的m个分量称为基本变量,其余变量称为非基本变量;令所有的非基本变量取值为零,得到的解称为对应于B的基本解。
定义4 如果一个基本解满足非负条件,即它也是可行的,则称为基本可行解,对应的基B称为可行基。