数学建模算法 一 简述（3）规划模型-整数规划

杨利霞

数学建模算法 一 简述（3）规划模型-整数规划

摘要： 本文讲的是数学建模算法 一 简述（3）规划模型-整数规划， 整数规划 定义： 规划中的变量（全部或部分）限制为整数，称为整数规划。若在线性模型中，变量限制为整数，则称为整数线性规划。 一类要求问题的解中的全部或一部分变量为整数的数学规划。从约束条件的构成又可细分为线性，二次和非线

教程 云栖大会 Mysql 备案 文档 域名 whois查询 PHP教程 备份 互联网大学 云教程

. |4 m: Z; l' X/ C2 r8 N& |5 r! O

整数规划
; H4 k3 T+ m& C3 B7 G7 ^5 a0 y定义：
: g9 l- ]8 e. w8 c2 R8 V$ Y规划中的变量（全部或部分）限制为整数，称为整数规划。若在线性模型中，变量限制为整数，则称为整数线性规划。
6 G% V! N% E/ W  h$ ~一类要求问题的解中的全部或一部分变量为整数的数学规划。从约束条件的构成又可细分为线性，二次和非线性的整数规划。

数学规划问题中有很多决策变量都只能取整数，如人员数量、机器设备台数、服装件数、汽车辆数等．如果规划问题中的决策变量xi(i=1,2,…,n),要求取整数值，则称这个模型为整数规划模型

数学表现形式

主要解法分为这几种:

（i）分枝定界法—可求纯或混合整数线性规划。
, Y0 e# a) h3 {$ n+ r（ii）割平面法—可求纯或混合整数线性规划。
5 ^7 u' V$ E( P- j. D( F（iii）隐枚举法—求解“0-1”整数规划：
①过滤隐枚举法；
3 a6 Y. p3 z- U, H; h6 k; u, _; i3 ?②分枝隐枚举法。
; Y, Z# D7 Z, k) g（iv）匈牙利法—解决指派问题（“0-1”规划特殊情形）。
（v）蒙特卡洛法—求解各种类型规划。

示例：
乐家百货商场准备派小李、小张、小王三位销售人员去销售库存的120件大衣．由于他们以前的销售业绩不同，每销售一件产品小李、小张、小王的报酬分别为6元、4元、3元．商场为保证销售速度，规定小李至少要承担30件销售任务，小张至少要承担20件销售任务，而小王承担的销售任务不能超过50件．问应该如何安排销售计划使总销售成本最低．

一、模型假设与变量说明
/ i6 S& R% U. e1．假设三位销售人员能销售完120件大衣．
2．小李、小张、小王承担的销售任务分别为 x1,x2,x3．

二、模型的分析与建立
* l' p( J# d' H/ e) ?该问题是在对三位销售人员销售数量进行一定限制的情况下，合理安排各销售人员的销售数量，使得公司支付给三位销售人员的总报酬最少．
0 t, l4 b+ B6 x目标：三位销售人员的总报酬最低．而总报酬为
1 V4 B0 b8 l7 J$ F1 s2 ~& A4 D
约束条件：
1．受总销售数量的限制：
2 E, F. S+ |; o$ s" W

2．受销售员销售数量的限制（如小李）： X(1) ≥ 30
( o) n$ T( ?# A1 A5 V

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)

" h' G( E' |' D$ R& c4 H由此可知，小李，小张，小王分别承担30，40，50件销售任务时，公司支付的总报酬最少．

" E# T# n. R0 R3 W3 z0 }
* u$ H; e& g8 D' ~& C0 |
8 y* U! j4 k+ ^0 `4 @8 m1 \