数学建模算法 一 简述(3)规划模型-整数规划
* J. ^5 R6 I/ |( T+ f: n4 q* `5 G摘要: 本文讲的是数学建模算法 一 简述(3)规划模型-整数规划, 整数规划 定义: 规划中的变量(全部或部分)限制为整数,称为整数规划。若在线性模型中,变量限制为整数,则称为整数线性规划。 一类要求问题的解中的全部或一部分变量为整数的数学规划。从约束条件的构成又可细分为线性,二次和非线 教程 云栖大会 Mysql 备案 文档 域名 whois查询 PHP教程 备份 互联网大学 云教程
8 m: W' k% G) R: z整数规划
) {5 V" Q' L, ` n, i/ e7 D* q6 Q定义: & o/ T! z+ K8 ]7 x, e) L
规划中的变量(全部或部分)限制为整数,称为整数规划。若在线性模型中,变量限制为整数,则称为整数线性规划。
3 k& n# S" s1 r- H+ M. \一类要求问题的解中的全部或一部分变量为整数的数学规划。从约束条件的构成又可细分为线性,二次和非线性的整数规划。 数学规划问题中有很多决策变量都只能取整数,如人员数量、机器设备台数、服装件数、汽车辆数等.如果规划问题中的决策变量xi(i=1,2,…,n),要求取整数值,则称这个模型为整数规划模型数学表现形式
& E/ ^4 B( T l2 p. R' H9 y![]() 主要解法分为这几种: (i)分枝定界法—可求纯或混合整数线性规划。 : N" b8 ~: Q. f k$ G' S& D" s
(ii)割平面法—可求纯或混合整数线性规划。
. }$ S" D' o+ J% U5 p1 v1 u# r(iii)隐枚举法—求解“0-1”整数规划: 2 `8 k1 X- d2 d# ~: c
①过滤隐枚举法; : J: i7 t5 u; W; r3 [! w& G
②分枝隐枚举法。
$ H5 S( x0 f3 F! @' l. C(iv)匈牙利法—解决指派问题(“0-1”规划特殊情形)。 % B7 u4 k& }* F* Z j& M% R" ^
(v)蒙特卡洛法—求解各种类型规划。 示例:
5 T* B9 P# b# m. v; s5 e O乐家百货商场准备派小李、小张、小王三位销售人员去销售库存的120件大衣.由于他们以前的销售业绩不同,每销售一件产品小李、小张、小王的报酬分别为6元、4元、3元.商场为保证销售速度,规定小李至少要承担30件销售任务,小张至少要承担20件销售任务,而小王承担的销售任务不能超过50件.问应该如何安排销售计划使总销售成本最低. 一、模型假设与变量说明 2 W n- O0 `* A' ]9 Y' ^7 v; J$ g3 w
1.假设三位销售人员能销售完120件大衣. * k4 f* g# p, A) P" S
2.小李、小张、小王承担的销售任务分别为 x1,x2,x3. 二、模型的分析与建立 7 B2 o& Y8 K9 A+ H* v
该问题是在对三位销售人员销售数量进行一定限制的情况下,合理安排各销售人员的销售数量,使得公司支付给三位销售人员的总报酬最少.
& }: Q" i+ {1 M% T目标:三位销售人员的总报酬最低.而总报酬为 - o3 H( |' T: x) z9 {
1 Z& v1 h: g* H约束条件: 4 y, A+ q3 o. @9 ^, B( Y
1.受总销售数量的限制: + e6 f4 \" \" a/ C- t) h0 m( |
![]() 2.受销售员销售数量的限制(如小李): X(1) ≥ 30 0 U d% z7 ]& m2 r1 r( |
![]() 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) / v7 J. B; z4 r. A a' p) v; {9 Y
由此可知,小李,小张,小王分别承担30,40,50件销售任务时,公司支付的总报酬最少. 4 E. L5 `, \# y0 s) d
# _: W4 C6 C+ M
4 T0 h9 @' f9 f$ k4 a" i* L! r1 r9 h |