2011建模培训- 数学规划.ppt

一、引言
二、线性规划模型
三、整数规划模型
数学建模专题----规划理论及模型
四、0-1规划模型
五、几种常用的线性规划模型
六、非线性规划模型
七、多目标规划模型
八、LINGO入门
一、引言
我们从2005年“高教社杯”全国大学生数模竞
谈起.
其中第二个问题是一个如何来分配有限资源,
从而达到人们期望目标的优化分配数学模型. 它
在数学建模中处于中心的地位. 这类问题一般可
以归结为
数学规划模型.
赛的B题“DVD在线租赁”问题的第二问和第三问
规划模型的应用极其广泛,其作用已为越来
来越急速地渗透于工农业生产、商业活动、军事
行为核科学研究的各个方面,为社会节省的财富、
创造的价值无法估量.
在数模竞赛过程中,规划模型是最常见的一
类数学模型. 从92-08年全国大学生数模竞赛试题
越多的人所重视. 随着计算机的逐渐普及,它越
的解题方法统计结果来看,规划模型共出现了16
次,占到了近50%,也就是说每两道竞赛题中就有
一道涉及到利用规划理论来分析、求解.
二、线性规划模型
线性规划模型是所有规划模型中最基本、最
例1.(食谱问题)设有 n 种食物,各含 m 种营养
素,第 j 种食物中第 i 种营养素的含量为 aij , n 种
食物价格分别为c1, c2, …, cn,请确定食谱中n 种食
物的数量x1, x2, …, xn,要求在食谱中 m 种营养素
简单的一种.
线性规划模型的基本形式
的含量分别不低于b1, b2, …, bm 的情况下,使得总
总的费用最低.
首先根据食物数量及价格可写出食谱费用为
其次食谱中第 i 种营养素的含量为
因此上述问题可表述为:
解
上述食谱问题就是一个典型的线性规划问题,
寻求以线性函数的最大(小)值为目标的数学模
型.
它是指在一组线性的等式或不等式的约束条件下,
线性规划的数学模型
max z =

线性规划、线性规划的可行解,最优解的概念
线性规划一般可写作
min(or max) f=
.
线性规划问题还可以用矩阵表示
min f=
Ax ≥b, x≥0
其中f被称作目标函数,目标函数下的等式或不等式被称作约束条件,
A=
,b=
一组满足约束条件的变量的值称为一组可行解。
可行解的集合称为可行解域,或可行解空间。
线性规划问题也就是在可行解域上寻找使目标函数取得极小(或极大)值的可行解,称之为最优解。