数学建模算法 一 简述(3)规划模型-整数规划
P/ w- J K; |$ j M摘要: 本文讲的是数学建模算法 一 简述(3)规划模型-整数规划, 整数规划 定义: 规划中的变量(全部或部分)限制为整数,称为整数规划。若在线性模型中,变量限制为整数,则称为整数线性规划。 一类要求问题的解中的全部或一部分变量为整数的数学规划。从约束条件的构成又可细分为线性,二次和非线 教程 云栖大会 Mysql 备案 文档 域名 whois查询 PHP教程 备份 互联网大学 云教程
' I) i0 l2 L3 c整数规划 : K9 R" W6 z( M+ t0 I
定义: & [, y6 r$ h P4 {+ g) C! T
规划中的变量(全部或部分)限制为整数,称为整数规划。若在线性模型中,变量限制为整数,则称为整数线性规划。 ' T$ k# {" n$ n) S5 [
一类要求问题的解中的全部或一部分变量为整数的数学规划。从约束条件的构成又可细分为线性,二次和非线性的整数规划。 数学规划问题中有很多决策变量都只能取整数,如人员数量、机器设备台数、服装件数、汽车辆数等.如果规划问题中的决策变量xi(i=1,2,…,n),要求取整数值,则称这个模型为整数规划模型数学表现形式
9 A% x! v3 L. ~% s, ]; j' K主要解法分为这几种: (i)分枝定界法—可求纯或混合整数线性规划。 ; E: j5 |0 ~" W, w' P; J; o i; e) R
(ii)割平面法—可求纯或混合整数线性规划。 * c, g2 f2 _& E8 w( G
(iii)隐枚举法—求解“0-1”整数规划: ' Q: V o [1 n" g
①过滤隐枚举法; + c8 O7 u3 z/ s* P$ \% z+ ~
②分枝隐枚举法。 - {& ]5 P4 S6 K! O
(iv)匈牙利法—解决指派问题(“0-1”规划特殊情形)。
" _7 d! v1 R% _% t(v)蒙特卡洛法—求解各种类型规划。 示例:
& T6 R# M: k7 E6 A乐家百货商场准备派小李、小张、小王三位销售人员去销售库存的120件大衣.由于他们以前的销售业绩不同,每销售一件产品小李、小张、小王的报酬分别为6元、4元、3元.商场为保证销售速度,规定小李至少要承担30件销售任务,小张至少要承担20件销售任务,而小王承担的销售任务不能超过50件.问应该如何安排销售计划使总销售成本最低. 一、模型假设与变量说明 - Y- g) k/ s, w% Q& h9 `: @8 D
1.假设三位销售人员能销售完120件大衣. 5 g& k% P' t! I5 O& R: R' k6 v# y
2.小李、小张、小王承担的销售任务分别为 x1,x2,x3. 二、模型的分析与建立 . Q6 U% L: R& @4 m
该问题是在对三位销售人员销售数量进行一定限制的情况下,合理安排各销售人员的销售数量,使得公司支付给三位销售人员的总报酬最少. % g# ?# R# B' b6 f/ U- _
目标:三位销售人员的总报酬最低.而总报酬为 1 N# [$ q+ h I. V4 }
4 }) _# p% Q @" b: N约束条件: + e% t+ `+ }/ ^3 ]2 |
1.受总销售数量的限制: ( M( }9 B2 C1 h8 @7 R
2.受销售员销售数量的限制(如小李): X(1) ≥ 30 8 f6 G% v4 g o
x=intvar(1,3); f=[6 4 3]*x'; F=set(0<=x<inf); F=F+set([1 1 1]*x'==120)+set(x(1)>=30)+set(x(2)>=20)+set(0<=x(3)<=50); solvesdp(F,f) double(f) double(x)( X0 w" p) \( Q) n0 m9 i
由此可知,小李,小张,小王分别承担30,40,50件销售任务时,公司支付的总报酬最少.
; c. y# N/ e" Y' \; ]! S# I1 P+ g% ^' f2 h; h9 G, x
4 {/ Q3 A! W O, a* ?1 m: h3 F
|