文档介绍：线性规划 Linear Programming( LP )
目标规划 Goal Programming( GP )
整数规划 Integer Programming( IP )
数学规划模型
实际问题中
的优化模型
x~决策变量
f(x)~目标函数
gi(x)0~约束条件
决策变量个数:n
约束条件个数:m
数学规划
线性规划
非线性规划
整数规划
重点在模型的建立和结果的分析
线性规划 Linear Programming(LP)
基本概念
线性规划模型
—— Linear Programming Model
或 Linear Optimization Model
用线性规划方法解决实际问题的第一步是建立能够完整描述和反映实际问题的线性规划模型。
线性规划 Linear Programming(LP)
基本概念
通常建立LP模型有以下几个步骤:
1. 确定决策变量: 决策变量是模型要确定的未知变量,也是模型最重要的参数,是决策者解决实际问题的控制变量。
2. 确定目标函数: 目标函数决定线性规划问题的优化方向,是模型的重要组成部分。实际问题的目标可表示为决策变量的一个线性函数,并根据实际问题的优化方向求其最大化(max)或最小化(min)。
3. 确定约束方程:一个正确的线性规划模型应能通过约束方程来描述和反映一系列客观条件或环境的限制,这些限制通过一系列线性等式或不等式方程组来描述。
4. 变量取值限制:一般情况下,决策变量取正值(非负值)。因此,模型中应有变量的非负约束即Xj≥0,但也存在例外。
线性规划 Linear Programming(LP)
基本概念
线性规划的一般形式:
max(或min)z = c1x1 + c2x2 + …+ cnxn
a11x1 + a12x2 +…+ a1nxn (≤= ≥)b1
a21x1 + a22x2 +…+ a2nxn (≤= ≥)b2
. ………………
am1x1 + am2x2 +…+ amnxn (≤= ≥)bm
xj ≥ 0 (j=1,2 … n)
线性规划 Linear Programming(LP)
基本概念
线性规划问题的标准形式
1、目标函数极大化——“ max ”
2、等式约束条件——“= ”
3、变量非负——“ xj ≥ 0 ”
max z = c1x1 + c2x2 + …+ cnxn
a11x1 + a12x2 +…+ a1nxn = b1
a21x1 + a22x2 +…+ a2nxn = b2
. ……………
am1x1 + am2x2 +…+ amnxn = bm
xj ≥ 0 (j=1,2 … n)
线性规划 Linear Programming(LP)
基本概念
化标准形式的一般步骤
1、目标函数极小化“极大化”
2、约束条件的右端项 bi≤0 “bi≥0”
3、约束条件为不等式≤或≥“=”
4、取值无约束(自由)变量“非负变量”
5、取值非正变量“非负变量”
例把问题转化为标准形式
计算软件
LinDo
LinGo
Matlab
LinDo
输入模型
求解
点击求解按钮即可
结果