数学建模定义符号说明1
2. 定义符号说明:
x
i
表示按照第i 种模式切割I 型号玻璃的块数(i=1,2,3...,
20);
y 表示按照第j 种模式切割II 型号玻璃的块数
j
(j=1,2,3,... ,20);
3. 模型建立:
此问题为建筑公司下料问题,其与钢管易拉罐下料问题,自来水分
派问题,奶制品的生产销售问题非常相似,都属于数学优化模型。所以我们可以用一些数学规划的相关知识来解决。 按照假设把这其中规格的窗户分为两组,如表1:
I,II 型号玻璃分别以这两组的窗户的尺寸进行切割,例如I 型号玻璃按照A 组切割,可以切3块1200x800,1块1200x650和1块700x600;II 玻璃按照A 组切割,可以切3块1200x800,4块1200x650和2块
700x600等等多种方案,这多种方案由表2,3表示: 表2
表3
对A 组建立的模型为:
决策变量 x i y j 它们为非负整数;
决策目标 分别以切割后剩余的余料量和切割原料玻璃的总块数为最小目标,由表2,3可以得到目标函数 Min
M1=141x1+117x+99x3+94.5x4+93x5+171x6+358.5x7+39x8+34.5x9+21x10+57x11+93x12+93x13+40.5x14+39x15+120x16+118.5x17+73.5x18+112.5x19+21x20+120y1+96y2+133.5y3+109.5y5+108.y6+61.5y7+18y8+12y9+6y10+42y11+193.5y12+256.5y13+54y15+72y16+136.5y17+3y18 ;(1) Min M2=∑x i +∑y j ;(2)
i =120
20
j =1
约束条件:
4x1+3x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10+x11+x12+6y1+5y2+5y3+4y4+4y5+4y6+4y7+3y8+3y9+3y10+3y11+3y12+2y13+2y14+y15 >=540 (3)
x2+3x3+2x4+2x5+x6+5x8+4x9+2x10+x11+5x13+3x14+3x15+2x16+2x17+x18+x19+y2+4y4+y5+y6+5y8+4y9+3y10+2y11+7y15+8y16+4y17+2y18 >=480 (4)
x2+2x5+2x6+2x7+6x10+7x11+8x12+x13+4x14+6x15+2x16+4x17+3x18+6x19+12x20+y2+y5+3y6+4y7+2y9+4y10+5y11+12y14+y18 (5)
x2+2x5+2x6+2x7+6x10+7x11+8x12+x13+4x14+6x15+2x16+4x17+3x18+6x19+12x20+y2+y5+3y6+4y7+2y9+4y10+5y11+12y14+y18 (6)
模型求解:
将(1)(3)(4)(5)(6)构成的整数线性规划模型输入 LINDO 如下:
min
141x1+117x2+99x3+94.5x4+93x5+171x6+358.5x7+39x8+34.5x9+21x10+57x11+93x12+93x13+40.5x14+39x15+120x16+118.5x17+73.5x18+112.5x19+21x20+120y1+96y2+133.5y3+109.5y5+108y6+61.5y7+18y8+12y9+6y10+42y11+193.5y12+256.5y13+54y15+72y16+136.5y17+3y18 st
4x1+3x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10+x11+x12+6y1+5y2+5y3+4y4+4y5+4y6+4y7+3y8+3y9+3y10+3y11+3y12+2y13+2y14+y15 >=540
x2+3x3+2x4+2x5+x6+5x8+4x9+2x10+x11+5x13+3x14+3x15+2x16+2x17+x18+x19+y2+4y4+y5+y6+5y8+4y9+3y10+2y11+7y15+8y16+4y17+2y18 >=480
x2+2x5+2x6+2x7+6x10+7x11+8x12+x13+4x14+6x15+2x16+4x17+3x18+6x19+12x20+y2+y5+3y6+4y7+2y9+4y10+5y11+12y14+y18 >=480
x2+2x5+2x6+2x7+6x10+7x11+8x12+x13+4x14+6x15+2x16+4x17+3x18+6x19+12x20+y2+y5+3y6+4y7+2y9+4y10+5y11+12y14+y18 >=600 end
>=480
>=600
求解可得到解如下:
Global optimal solution found.
Objective value: 0.000000 Total solver iterations: 6
V ariable V alue Reduced Cost X1 0.000000 141.0000 X2 0.000000 117.0000 X3 0.000000 99.00000
X4 0.000000 94.50000
X5 X6 X7 X8
0.000000 0.000000 0.000000 0.000000
93.00000 171.0000 358.5000 39.00000
X9 0.000000 34.50000 X10 0.000000 21.00000 X11 0.000000 57.00000 X12 0.000000 93.00000 X13 0.000000 X14 0.000000 X15 0.000000 X16 0.000000 X17 0.000000 X18 0.000000 X19 0.000000 X20 0.000000 Y1 0.000000 Y2 0.000000 Y3 0.000000 Y5 0.000000 Y6 0.000000 Y7 0.000000 Y8 0.000000
Y9
0.000000 Y10 0.000000 Y11 0.000000 Y12 0.000000 Y13 0.000000 Y15 0.000000 Y16 0.000000 Y17 0.000000 Y18 0.000000 Y4 120.0000 Y14 50.00000 Row Slack or Surplus 1 0.000000 2 40.00000 3 0.000000 4 120.0000 5 0.000000 93.00000 40.50000 39.00000 120.0000 118.5000 73.50000 112.5000 21.00000 120.0000 96.00000 133.5000 109.5000 108.0000 61.50000 18.00000 12.00000
6.000000 42.00000 193.5000 256.5000 54.00000 72.00000 136.5000 3.000000 0.000000 0.000000 Dual Price -1.000000 0.000000 0.000000 0.000000 0.000000
即按照模式4切割II 号玻璃120块和模式14切割II 号玻璃50块使得余量最小; 为0。
将(1)(3)(4)(5)(6)构成的线性规划模型输入LINDO 如下: min
x1+x2+x3+x4+x+5x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+y1+y2+y3+y4+y5+y6+y7+y8+y9+y10+y11+y12+y13+y14+y15+y16+y17+y18+y19+y20 st
4x1+3x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10+x11+x12+6y1+5y2+5y3+4y4+4y5+4y6+4y7+3y8+3y9+3y10+3y11+3y12+2y13+2y14+y15 >=540
x2+3x3+2x4+2x5+x6+5x8+4x9+2x10+x11+5x13+3x14+3x15+2x16+2x17+x18+x19+y2+4y4+y5+y6+5y8+4y9+3y10+2y11+7y15+8y16+4y17+2y18 >=480
x2+2x5+2x6+2x7+6x10+7x11+8x12+x13+4x14+6x15+2x16+4x17+3x18+6x19+12x20+y2+y5+3y6+4y7+2y9+4y10+5y11+12y14+y18 >=480
x2+2x5+2x6+2x7+6x10+7x11+8x12+x13+4x14+6x15+2x16+4x17+3x18+6x19+12x20+y2+y5+3y6+4y7+2y9+4y10+5y11+12y14+y18 >=600 end
求解可得到下结果:
Global optimal solution found.
Objective value: 165.0000 Total solver iterations: 7
V ariable V alue Reduced Cost X1 0.000000 0.5000000 X2 0.000000 0.4375000 X3 0.000000 0.3750000 X4 0.000000 0.5000000 X5 0.000000 0.3750000 X6 0.000000 0.5000000 X7 0.000000 0.6250000 X8 0.000000 0.2500000 X9 0.000000 0.3750000 X10 0.000000 0.2500000 X11 0.000000 0.3125000 X12 0.000000 0.3750000
X13 0.000000 0.3125000
X14 X15 X16 X17
0.000000 0.3750000 0.000000 0.2500000 0.000000 0.6250000 0.000000 0.5000000
X18 0.000000 0.6875000 X19 0.000000 0.5000000 X20 0.000000 0.2500000 Y1 0.000000 0.2500000 Y2 0.000000 0.1875000 Y3 0.000000 0.3750000 Y4 75.00000 0.000000 Y5 0.000000 0.3125000 Y6 0.000000 0.1875000 Y7 0.000000 0.2500000 Y8 0.000000 0.000000 Y9 0.000000 0.000000 Y10 60.00000 0.000000 Y11 0.000000 0.6250000E-01 Y12 0.000000 0.6250000 Y13 0.000000 0.7500000
Y14 Y15 Y16 Y17
30.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.5000000
Y18 0.000000 0.6875000 Y19 0.000000 1.000000 Y20 0.000000 1.000000
Row Slack or Surplus Dual Price 1 165.0000 -1.000000 2 0.000000 -0.1250000 3 0.000000 -0.1250000 4 120.0000 0.000000 5 0.000000 -0.6250000E-01
即按照模式4购买II 号玻璃75块,按照模式10购买II 号玻璃60块和按照模式14购买II 号玻璃35块使得总的购买量最小;为165块。
对B 组建立的模型为:
决策变量 x i y j 它们为非负整数;
决策目标 分别以切割后剩余的余料量和切割原料玻璃的总块数为最小目标,由表2,3可以得到目标函数
Min
N1=142.5x1+132x2+126x3+79.5x4+73.5x5+67.5X6+61.5x7+165x8+63x9+93x10+96y1+90y2+133.5y3+127.5y4+121.5y5+81y6+75y7+69y8+63y9+57y10+208.5y11+202.5y12+196.5y13+190.5y14+88.5y15 (1) Min N2=∑x i +∑y j (2)
i =110
15
j =1
约束条件为:
3x1+2x2+2x3+x4+x5+x6+x7+4y1+4y2+3y3+3y4+3y5+2y6+2y7+2y8+2y9+2y10+y11+y12+y13+y14+y15 >=600(3)
x2+3x4+2x5+x6+4x8+3x9+y1+2y3+y4+4y6+3y7+2y8+y9+4y11+3y12+2y13+y14>=960 (4)
x2+3x3+x4+3x5+5x6+7x7+4x9+9x10+2y2+2y4+4y5+2y7+4y8 +6y9+8y10+2y12+4y13+6y14+10y15>=1320(5) 模型求解:
将(1)(3)(4)(5)构成的整数线性规划模型输入
Min
142.5x1+132x2+126x3+79.5x4+73.5x5+67.5X6+61.5x7+165x8+63x9+93x10+96y1+90y2+133.5y3+127.5y4+121.5y5+81y6+75y7+69y8+63y9+57y10+208.5y11+202.5y12+196.5y13+190.5y14+88.5y15
st
3x1+2x2+2x3+x4+x5+x6+x7+4y1+4y2+3y3+3y4+3y5+2y6+2y7+2y8+2y9+2y10+y11+y12+y13+y14+y15 >=600
LINDO 如下:
x2+3x4+2x5+x6+4x8+3x9+y1+2y3+y4+4y6+3y7+2y8+y9+4y11+3y12+2y13+y14>=960
x2+3x3+x4+3x5+5x6+7x7+4x9+9x10+2y2+2y4+4y5+2y7+4y8 +6y9+8y10+2y12+4y13+6y14+10y15>=1320 end
可以求得解入下:
Global optimal solution found.
Objective value: 26640.00 Extended solver steps: Total solver iterations:
V ariable X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10 Y11 Y12 Y13 Y14 Y15 Row 1 2 3 0 6 V alue Reduced Cost 0.000000 57.00000 0.000000 69.00000 0.000000 69.00000 0.000000 33.00000 0.000000 33.00000 0.000000 33.00000 0.000000 33.00000 0.000000 141.0000 84.00000 45.00000 0.000000 93.00000
0.000000 -24.00000
0.000000 -24.00000 0.000000 36.00000 0.000000 36.00000 0.000000 36.00000 0.000000 0.000000 204.0000 0.000000 0.000000 0.000000 96.00000 0.000000 0.000000 0.000000 0.000000 156.0000 0.000000 156.0000 0.000000 156.0000 0.000000 156.0000 0.000000 60.00000 Slack or Surplus Dual Price 26640.00 -1.000000 0.000000 -28.50000 0.000000 -6.000000
即按照模式9分别切割I 号玻璃84块和II 号玻璃96块,按照模式7切割II 号玻璃204块使得总的剩余量最小,为26640.00。
将(2)(3)(4)(5)构成的整数线性规划模型输入
Min
x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+y1+y2+y3+y4+y5+y6+y7+y8+y9+y10+y11+y12+y13+y14+y15
st
4x1+3x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10+x11+x12+6y1+5y2+5y3+4y4+4y5+4y6+4y7+3y8+3y9+3y10+3y11+3y12+2y13+2y14+y15 >=540
x2+3x3+2x4+2x5+x6+5x8+4x9+2x10+x11+5x13+3x14+3x15+2x16+2x17+x18+x19+y2+4y4+y5+y6+5y8+4y9+3y10+2y11+7y15+8y16+4y17+2y18 >=480
x2+2x5+2x6+2x7+6x10+7x11+8x12+x13+4x14+6x15+2x16+4x17+3x18+6x19+12x20+y2+y5+3y6+4y7+2y9+4y10+5y11+12y14+y18 >=480
x2+2x5+2x6+2x7+6x10+7x11+8x12+x13+4x14+6x15+2x16+4x17+3x18+6x19+12x20+y2+y5+3y6+4y7+2y9+4y10+5y11+12y14+y18 >=600
end LINDO 如下:
求得结果为:
Global optimal solution found.
Objective value: 371.1000
Extended solver steps: 0
Total solver iterations: 14
V ariable V alue Reduced Cost
X1 0.000000 1.000000
X2 0.000000 0.6500000
X3 0.000000 0.7000000
X4 0.000000 0.1500000
X5 0.000000 0.2000000
X6 0.000000 0.2500000
X7 0.000000 0.3000000
X8 0.000000 0.000000
X9 6.000000 -0.1500000
X10 0.000000 0.1000000
Y1 0.000000 0.7500000
Y2 0.000000 0.8000000
Y4 Y5 Y6 Y7 0.000000 0.5500000 0.000000 0.6000000 235.5000 0.000000 0.000000 0.5000000E-01 Y8 0.000000 0.1000000
Y9 0.000000 0.1500000
Y10 0.000000 0.2000000
Y11 0.000000 0.000000
Y12 0.000000 0.5000000E-01 Y13 0.000000 0.1000000
Y14 0.000000 0.1500000
Y15 129.6000 0.000000
Row Slack or Surplus Dual Price
1 371.1000 -1.000000
2 0.6000000 0.000000
3 0.000000 -0.2500000
4 0.000000 -0.1000000
即按照模式9购买6块I 号玻璃,按照6模式购买II 号236块玻璃和按照模式15购买130块II 号玻璃使得购买量最小,为372块。
综合A 组和B 组考虑:
购买I 号玻璃6块,II 号玻璃块526块使得总的购买量最小,为572块。
按照模式9切割84块I 号玻璃,14模式切割50块II 号玻璃,9模式切割96块II 号玻璃,7模式切割204块II 号玻璃使得浪费最小,最少余量为26660.00。