文档介绍：
在生产生活以及军事领域经常会遇到资源分配问题,不同的分配方案产生的效益是不一样的,所以,为了追求最佳效益,必须在不同的分配方案中选择最佳的资源分配方案。规划论就是研究针对不同需求对有限资源进行分配的一个运筹学分支。
第三章规划论
其中,线性规划是形成最早也是最成熟的一个分支。到目前为止,它的应用也最广泛,是数学规划及运筹学其他分支的基础。
线性规划
整数规划
动态规划
零一规划
非线性规划
目标规划
2 理论分支
理论分支
康脱络维奇——论文“生产组织与计划中的数学方法”,1939年。
1947年,丹捷格提出了单纯形法
第一节线性规划
对于一个实际问题,如果采用线性规划去求解,应做两方面的工作,一是把求解问题抽象成能用线性规划来解的数学模型,这就是数学建模。二是对这个线性规划进行求解。即
数学建模
求
解
1 线性规划方法解决问题的过程
(1)引例
某军工厂准备用三种原料来制造两种产品,有关数据如下表所示。问如何安排生产,以使总利润达到最大化。
单位产品产品
消耗量
原料(公斤)
I
II
原料总量
A
9
4
360
B
4
5
200
C
3
10
300
单位产品利润(元)
7
12
2 线性规划问题的数学模型
确定目标:求出生产两种产品的数量各为公斤,以使总利润达到最大。
建立数学模型:
设 I 产品生产 x1 公斤,II 产品生产 x2 公斤
MAX 总利润 Z = 7 x1 + 12 x2
目标是
9 x1 + 4 x2 ≤ 360
4 x1 + 5 x2 ≤ 200
3 x1 + 10 x2 ≤ 300
x1,x2,,x3 ≥ 0
建立数学模型:
设 I 产品生产 x1 公斤,II 产品生产 x2 公斤
MAX 总利润 Z = 7 x1 + 12 x2
目标是
9 x1 + 4 x2 ≤ 360
4 x1 + 5 x2 ≤ 200
3 x1 + 10 x2 ≤ 300
x1,x2,,x3 ≥ 0
以上问题属于线性规划问题,这类问题从数学上讲所具有的共同特征是:
1)决策变量。
每一个问题都用一组未知数(……xn)表示某一方案,这组未知数的一组定值代表一个具体的规划方案。通常要求这些未知数取值是非负。以后我们称这组未知数为决策变量。
2)约束条件。
3)目标函数。
线性规划问题都有一个目标要求,并且这个目标可以表示为一组未知数的线性函数,称之为目标函数,按研究问题的实际情况目标函数可以是求最小值也可以是求最大值。我们总是希望收益、效益、效率等指标达到最大化,而对于成本、费用、支出等指标则希望达到最小化。
(2)线性规划问题的共同特征
综合上述这三点,这类问题都可以用如下数学语言来描述。
 
目标函数: max ( min ) Z = c1x1 + c2x2 + …+ cnxn
a11x1 + a12x2 + … a1nxn ≥(= ,≤)b1
a21x1 + a22x2 + … a2nxn ≥(= ,≤)b2
……
am1x1 + am2x2 + … amnxn ≥(= ,≤)bm
x1,x2,… xn ≥ 0
3 线性规划问题的标准形式
(1)线性规划的标准形式是:
 
目标函数: max Z = c1x1 + c2x2 + …+ cnxn
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
x1,x2,… xn ≥ 0