线性规划问题的数学模型.ppt

数学建模系列讲座(一)线性规划模型
线性规划问题
第一节线性规划问题的数学模型
(一)引言
线性规划是运筹学的重要分支之一,也是研究较早、发展较快、应用较广而且比较成熟的一个分支。自1947年线性规划被成功的运用于工业、交通、农业和军事等各个领域后,现在它已成为管理科学的重要基础和手段之一。随着计算机的普及,它的适应领域越来越广泛。
线性规划研究的问题主要有两类:一是一项任务确定后,如何统筹安排,尽量作到用最少的人力物力资源去完成这一任务。二是已有一定数量的人力物力资源,如何安排使用他们,使得完成任务最多。其实这两类问题是一个问题的两个方面,就是所谓寻求整个问题的某个整体指标最优的问题。



(二)线性规划问题的数学模型

设有两个砖厂A1、A2。其产量分别为23万块与27万块。它们生产的供应B1、B2、 B 3三个工地。其需要量分别为17万块、18万块和15万块。自各产地到各工地的运价格如下表:问应如何调运,才使总运费最省。
运价工地
砖厂
B1
B2
B 3
A1
50
60
70
A2
60
110
160
解:设 xi j表示由砖厂Ai 运往工地 Bj 砖的数量(i=1,2;j=1,2,3)
运量工地
砖厂
B1
B2
B 3
发量
A1
x11
x12
x13
23
A2
x21
x22
x23
27
收量
17
18
15
50
目标函数
约束条件
 某工厂生产A 、B两种产品,现有资源数、生产每单位产品所需原材料数以及每单位产品可得利润如下表所示。问如何制定生产计划使两种产品总利润最大?
单位产品产品
耗用资源
资源
A(公斤)
B(公斤)
现有资源
铜(吨)
9
4
360
电力(千瓦)
4
5
200
劳动日(个)
3
10
300
单位利润
(万元/公斤)
7
12
解:假设生产A产品x1公斤, B产品x2公斤, x1 , x2称为决 策变量,简称变量。得到利润7 x1 +12 x2万元,这一问 题的数学模型为:
约束条件
目标函数
上述例子虽然有不同的实际内容,但是都可归结为一类
优化问题。从数学上说它们具有以下共同特征:
⑴每一个问题都是求一组变量(称为决策变量)的值。
这组变量的一组定值就代表一个具体方案。通常要求这组变
量的取值是非负的。
⑵存在一定的限制条件,称为约束条件。这些约束条件
都可以用一组线性等式或不等式来表示。
⑶都有一个期望达到的目标,并且这个目标可以表示为
决策变量的线性函数(称为目标函数)。按所研究问题的不
同,要求目标函数值最大化或最小化。
我们将具有上述三个特点的最优化问题归结为线性规划问题,其数学模型称为线性规划问题的数学模型,简称线性规划数学模型。
线性规划问题的数学模型的一般形式
(1)式称为目标函数(2)式中等式或不等式称为约束条件
(3)式是非负约束条件
x1 , x2, …,xn称为决策变量,简称变量。
满足约束条件的一组变量的值
称为线性规划问题的一个可行解,使目标函数取得最大(或最
小)的可行解称为最优解。此时,目标函数的值称为最优值。
建立线性规划数学模型的步骤
首先,确定决策变量。线性规划的数学模型建得是否容易,求解是否方便,取决于决策变量的选取是否得当。
其次,确定约束条件,并根据实际问题添加非负条件。明确问题中所有的限制条件,并用决策变量的线性等式或不等式表示。一般可用表格形式列出所有的限制数据,然后根据所列出的数据写出相应的约束条件,以避免遗漏或重复所规定的限制要求。
最后,确定目标函数,并确定是求极大还是求极小。用决策变量的线性函数来表示实际问题所要达到的目标,得到目标函数。