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

数学规划模型
实际问题中
的优化模型
x~决策变量
f(x)~目标函数
gi(x)0~约束条件
多元函数条件极值
决策变量个数n和
约束条件个数m较大
最优解在可行域
的边界上取得
数学规划
线性规划
非线性规划
整数规划
重点在模型的建立和结果的分析
某工厂生产一种型号的机床,、,这些轴需要用同一种圆钢制作, 。如果要生产100台机床,应如何下料,才能使得用料最省?
一、线性规划问题的数学模型
分析
引例
,、,可以有若干种下料方式,把它截成我们需要的长度,有以下8种下料方式(表1-1):
表1-1 下料方式及每种类型的数目
下料方式
长度
B1
B2
B3
B4
B5
B6
B7
B8
需要量

2
1
1
1
0
0
0
0
100

0
2
1
0
3
2
1
0
100

1
0
1
3
0
2
3
4
100
余料



0




、问题建模举例
一、线性规划问题的数学模型
下料方式是从大到小、从长到短的顺序考虑的。
⑴若只考虑用B3方式下料,需用料100根,没优化。
⑵动一下脑筋,就可以发现组合的下料方式(取长补短)才是最好的下料方法。
一、线性规划问题的数学模型
⑶若要我们安排下料, 暂不排除8种下料方式中的任何一种,通过建立数学模型进行求解,寻找最好的下料方案。
、,即:
因此,可以建立以下线性规划数学模型:
一、线性规划问题的数学模型
通过建立数学模型求解,得到的结果是最优的。这个模型就是线性规划模型。
因此,可以建立以下线性规划数学模型:
用LINGO软件求解,
程序如下:
Min=x1+x2+x3+x4+x5+x6+x7+x8;
2*x1+x2+x3+x4>=100;
2*x2+x3+3*x5+2*x6+x7>=100;
x1+x3+3*x4+2*x6+3*x7+4*x8>=100;
Global optimal solution found at iteration: 3
Objective value:
Variable Value Reduced Cost
X1
X2
X3
X4
X5
X6
X7
X8
Row Slack or Surplus Dual Price
1 -
2 -
3 -
4 -
一、线性规划问题的数学模型
即对模型求解得到结果如下:
运行结果如右所示:
这就是最优的下料方案。
下料问题是在经济和管理中经常遇到的问题,引例是条材下料问题、此外还有板材下料问题(如五金厂生产保险柜的下料、服装厂下料等)或者更复杂的下料问题。本问题能不能将目标函数确定为余料最少,为什么?这是值得读者思考的问题。
在生产管理和经营活动中,经常考虑这样一类问题:如何合理地利用有限的人力、物力和财力等资源,以便得到最好的经济效果——成本最小或收益最大。下面分五个方面介绍典型的建立线性规划模型的方法。
一、线性规划问题的数学模型
说明
一、线性规划问题的数学模型
例1. 某工厂生产一型号机床,、、2、1根,这些轴需要用同一种圆钢制作, 。如果要生产100台机床,应如何下料,才能使得用料最省?
解
关于下料方式的分析如引例,下料方式见表1-1,
可建模如下:
用Lindo对模型求解,得
合理下料问题
一、线性规划问题的数学模型
★一般下料问题:设用某种材料(条材或板材)下零件A1, A2,…,Am的毛坯,据过去的经验,在一件原料上有B1, B2,…,Bn共n种不同的下料方式,每种合理的下料方式可得各种毛坯个数及每种零件的需要量如表1-3。问:
怎样安排下料方式,使得既满足需要,又使得用料最省?