运筹学中-线性规划图解法动态演示.ppt

第二章 线性规划的图解法
第1节问题的提出
1、线性规划的概念
由用线性变量所构建的线性目标函数和线性约束组成的数学模型,我们称之为线性规划。即所有变量都是一次的,目标函数和约束条件(方程或不等式)也是线性的。
2、具体应用例子。
某工厂计划用现有的铜、铅两种资源生产甲、乙电缆,生产甲、乙两种电缆的单位售价及资源消耗如下表所示:
甲电缆
乙电缆
资源量
铜(吨)
2
1
10
铅(吨)
1
1
8
价格(万元)
6
4
另外,市场对乙电缆的最大需求量为7单位,而对甲乙电缆的需求量无限制。问该工厂应如何安排生产才能使工厂的总收入最大?
一、线性数学模型的建立:
.
Object:
解:设x1,x2分别代表甲乙两种电缆的生产量,z代表工厂的总收入,则上述问题可用如下数学模型来表示:
铜资源约束
铅资源约束
市场约束
产量非负
目标函数
LP的基本概念
目标函数中的变量系数用Cj表示,Cj称为价值系数;约束条件的变量系数用aij表示,aij称为工艺系数;约束条件右端的常数用bi表示,bj称为资源限量(系数)
约束条件
(subject to)
目标Object:
指出模型中的可行解
基本概念:
1、什么是可行解?
2、什么是最优解?
二、线性规划模型的求解(方法):
1、图解法;
2、单纯形法(时代标志);
3、计算机软件求解。
第2节图解法
条件:只有两个变量的线性规划问题
理解: X1,x2代表两个数轴:
目标函数:是一条直线(视Z为常量)
约束条件:是等式或不等式,代表直线或直线的上方或下方;
x1
x2
0
7
x2≤7
条件约束图示:
x2≥0
x2=7
x1≥0
x1
x2
5
10
0
2x1+ x2=10
7
8
8
x2≤7
图示:
.
x1+ x2=8
可行域
x1
x2
5
10
0
2x1+ x2≤10
x1+x2≤8
7
8
8
x2≤7
max z=6x1+4x2
0=6x1+4x2
可行域
最优解
(X1=2, x2=6) z=36
.