整数二次规划（精选3篇）
整数二次规划 篇1
摘要：目前关于选址问题研究有很多, 基于混合整数规划的选址问题研究也有一些, 但是还存在一些问题。其中一个是, 在目前的多源供应模型中 (即多工厂) , 只考虑了单位产品的运输费用, 都没有考虑到工厂到配送中心和配送中心到客户路线开启的固定成本投入, 即一条线路上不管运多运少其单位价格都一样, 这显然是不合理的。因此本文在原来混合整数规划模型的基础上考虑以上线路开启的固定成本投入, 建立了新的模型, 并且进行实例求解。
关键词：CPLEX,混合整数规划,配送中心,选址,模型
0 引言
混合整数规划模型是一种经常被用来解决物流网络系统中大型、复杂选址问题的方法。其的主要优点是它能够把固定成本以最优的方式考虑进去, 它是商业选址模型中最受欢迎的方法。一般用混合整数规划来描述选址模型, 目标是使各种成本费用的总和最小, 而用整数变量表示各种选择, 用连续变量表示工厂的生产能力、各种资源的分配等, 用约束表示物流平衡关系和供需关系等。
在以往关于混合整数规划的选址模型已经有了一些研究。[1]中是一个只有配送中心和顾客的两级供应模型, 因此可以归属于一个单源供应模型, 目标函数是总成本最小, 这里的总成本考虑了配送中心的固定投资成本和运输费用, 其中认为运输费用是一个与运输量呈线性的函数。[2]中是也是一个只有配送中心和顾客两级的单源供应的模型, 它与[1]中的不同之处在于它考虑了不同商品种类的配置成本。[3][4]这两篇文中都是一个包括工厂、配送中心和顾客三级的多源供应模型, 其目标函数是总成本最小, 这的总成本考虑了从工厂到配送中心的运输费用、配送中心到顾客的配送费用、仓储管理费用和固定设施的投资费用, 其中两项运输费用都认为是一个与运输量呈线性的函数。[5]中也是一个多源供应模型, 它在上述模型的基础上考虑了工厂直供这一情况及相应的运输费用。
目前在包括以上的单源和多源供应的模型中, 在考虑运输成本时只考虑了单位产品的运输费用, 都没有考虑到工厂到配送中心和配送中心到客户路线开启的固定成本投入, 即一条线路上不管运多运少其单位价格都一样, 这显然是不合理的。因此本文希望在原有模型的基础上考虑线路开启的固定成本投入, 建立新的模型, 并且在IBM ILOG CPLEX上进行实例求解。
1 物流配送中心的选址模型
1.1 模型问题描述
假设有m个备选的配送中心, 可以从L个工厂中进货, 同时又必须给n个顾客提供配送服务, 其配送网络如图1所示。工厂和客户的数量和位置是固定的, 要从备选的配送中心中选出建设的配送中心 (个数没有要求) , 问如何进行选址及运输使总成本最小?
1.2 假设条件
为了建模的方便, 做出如下的假设: (1) 工厂到备选配送中心的、备选配送中心到顾客两段的运输费用是有固定成本和可变成本组成; (2) 工厂到备选配送中心的、备选配送中心到顾客的线路开启的固定成本已知; (3) 单个周期的供应和配送次数只有一次; (4) 工厂能力已知; (5) 备选配送中心的容量已知; (6) 本文不对配送中心的数量设限, 只要全面考虑到成本就没必要进行数量限制; (7) 配送中心的固定费用、单位管理费用已知; (8) 配送的商品是只有一种; (9) 工厂到配送中心和配送中心到顾客的配送周期一致。
1.3 新模型建立
1.3.1 已知参数定义
l表示:工厂数目;
m表示:备选配送中心数目;
n表示:顾客数目;fi表示:配送中心的固定投资费用;b表示:设定的周期数;
ai表示:配送中心的容量;
gi表示:配送中心单位产品单个周期的管理费用;
cki表示:单位产品单个周期从工厂k到备选配送中心i的运输费用;
hij表示:单位产品单个周期从配送中心i到顾客j的配送费用;
vki表示:单个周期内开启运输路线从工厂k到备选配送中心i的固定费用;
uij表示:单个周期内开启运输路线从备选配送中心i到顾客j的固定费用;
pk表示:单周期内工厂k的生产能力。
1.3.2 决策变量的定义
wki表示:工厂k到备选配送中心i一次的运输量;xij表示:备选配送中心i到顾客j一次的运输量;
yki表示:开启运输路线从工厂k到备选配送中心i与否, yki=0表示不开启, yki=1表示开启。
qij表示:开启运输路线从备选配送中心i到顾客j与否, qij=0表示不开启, qij=1表示开启。
zi表示:备选配送中心i被选择与否, i=0表示不选择, i=1表示选择。
1.3.3 目标函数的定义
这表示一定时间内的成本最小的目标函数。
1.3.4 约束条件的定义
(2) 表示工厂的能力限制, (3) 表示配送中心的进出货量应该平衡, (4) 表示每个顾客的需求都能够得到满足, (5) 表示每个配送中心的通过量不能超过其容量限制, (6) 表示工厂到配送中心每条线路的运输量不能超过工厂的能力, (7) 表示配送中心到顾客每条线路的运输量不能超过配送中心的能力, (8) ~ (12) 为变量的约束。
1.3.5 模型的一些说明
(1) 以往的混合整数规划的选址模型中的周期性都不是很强, 因此本文强调了周期性这一概念。这里的周期性即是配送中心向工厂采购和配送中心给顾客配送一次的时间, 并且为了建模和计算方便本文假定了这两个周期是一致的。 (2) 目标函数以一个较长的时间来评价, 因为考虑到前期的固定成本投入很大, 而一个周期的运输和管理成本较小, 如果不考虑长期的话运输成本和管理成本对于目标函数的影响就很小, 这样考虑运输费用和管理费用就显得没有必要。 (3) 本文没有对备选配送中心的数目进行一个限制, 只要在一个较长的时间内的总成本是最小的就行。 (4) 本文认为的一条线路上的运输成本是由线路开启的成本和变动运输费用两部分组成。其中的固定成本主要是指一条线路上的人员工资成本、燃油费等, 而变动成本是与运输量有关的运输费用。
2 物流配送中心的选址算例及用CPLEX求解
2.1 实例问题描述
某家电制造企业, 生产一种产品, 设有5个工厂, 4个备选配送中心, 10个顾客, 假设配送中心的采购和配送都是一周进行完一次, 各工厂的每周的生产能力已知, 如下表1, 单位产品从工厂到配送中心的运价表如表2, 单个周期内开设工厂到配送中心的固定费用如表3, 备选配送中心的固定投资费用、容量及单位管理费用如表4, 单位产品从配送中心到顾客的运价表如表5, 单个周期内开设配送中心到顾客的固定费用如表6。
(单位:台)
(单位:元/ (台*周) )
(单位:元/周)
(单位:元/ (台*周) )
(单位:元/周)
以3年为限, 问如何选址及配送使得3年的总成本最小?
2.2 用IBM ILOG CPLEX进行求解
CPLEX是IBM公司中的一个优化引擎。该优化引擎用来求解线性规划、二次规划、带约束的二次规划、二阶锥规划这四类基本问题, 以及相应的混合整数规划问题。CPLEX具有 (1) 能解决一些非常困难的行业问题; (2) 求解速度非常快; (3) 有时还提供超线性加速功能的优势。
将上述问题在IBM ILOG CPLEX中进行建模和求解后得到的结果是:选择3号和4号备选配送中心作为物流配送中心选址, 选择工厂1, 2, 5作为供应商, 并且3号配送中心由工厂2和工厂5供货和给顾客1, 3, 5, 6, 7, 10配送, 4号配送中心由工厂1供货和给顾客2, 4, 8, 9配送。3年内最小的成本为938427.2元, 求解用时3.36秒。
3 结语
IBM ILOG CPLEX是一个功能强大的优化软件, 混合整数规划是包含离散的整数变量和连续变量。在实际的配送中心选址问题中往往是符合这种既含有连续型变量又含有离散型变量条件的, 加之实际中选址的复杂性, 用普通计算方法既难求解又不高效。因此运用混合整数规划的方法构建同时拥有连续型变量和离散型变量的选址问题模型, 并且用IBM ILOG CPLEX进行求解, 这是一种很不错的方法, 值得在选址问题中进行推广使用。另外在选址问题建模中应当考虑各线路开启时的固定成本投入, 使更加符合实际情况, 从而得出更好的结果。
参考文献
[1]胡列格, 何其超, 盛玉桂.物流运筹学[M].北京:电子工业出版社, 2005:113-115.
[2]黄小原, 卢震.二级供应链模型及其在服务销售问题中的应用[J].东北大学学报 (自然科学版) , 2001 (6) :692-695.
[3]丁小东, 姚志刚, 程高.LINGO语言与0_1混合整数规划选址模型的再结合[J].物流工程与管理, 2009 (10) :72-75.
[4]王林, 叶小侠.基于Lingo语言求解物流配送中心选址模型[J].物流技术2008 (10) :113-115.
[5]程继红, 马颖亮, 李高鹏.基于混合整数规划模型的物流中心选址方法[J].海军航空工程学院学报, 2007 (2) :292-294.
整数二次规划 篇2
二、实验目的：
熟练使用Spreadsheet建立整数规划、动态规划模型，利用excel建立数学模型，掌握求解过程，并能对实验结果进行分析及评价
三、实验设备
计算机、Excel
四、实验内容
（一）整数规划
1、0-1整数规划
其中，D11=F2;D12=F3;D13=F4;D14=F5;
B11=SUMPRODUCT($B$9:$E$9,B2:E2);
B12=SUMPRODUCT($B$9:$E$9,B3:E3);
B13=SUMPRODUCT($B$9:$E$9,B4:E4);
B14=SUMPRODUCT($B$9:$E$9,B5:E5);
H8==SUMPRODUCT($B$9:$E$9,B6:E6);
用规划求解工具求解：目标单元格为$H$8,求最大值，可变单元格为$B$9:$E$9，约束条件为$B$11:$B$14<=$D$11:$D$14;$B$9:$E$9=二进制。在【选项】菜单中选择“采用线性模型”“假定非负”。即可进行求解得结果，实现最大利润为140.
2、整数规划
其中，D11=D2;D12=D3;
B11=SUMPRODUCT($B$8:$C$8,B2:C2);B12=SUMPRODUCT($B$8:$C$8,B3:C3); F7=SUMPRODUCT($B$8:$C$8,B4:C4);
用规划求解工具求解：设置目标单元格为F7,求最大值，可变单元格为$B$8:$C$8,约束条件为$B$11:$B$12<=$D$11:$D$12;$B$8:$C$8=整数。在【选项】菜单中选择“采用线性模型”“假定非负”。即可进行求解得结果，实现最大利润为14.
3、指派问题
人数跟任务数相等：
其中，F11=SUM(B11:E11);F12=SUM(B12:E12);F13=SUM(B13:E13);F14=SUM(B14:E14); B15=SUM(B11:B14);C15=SUM(B11:B14);D15=SUM(B11:B14);E15=SUM(B11:B14); H11,H12,H13,H14,B17,C17,D17,E17单元格值均设为1.
用规划求解工具求解：设置目标单元格为$B$8,求最小值，可变单元格为$B$11:$E$14,约束条件为$B$11:$E$14=二进制；$B$15:$E$15=$B$17:$E$17;$F$11:$F$14=$H$11:$H$14. 在【选项】菜单中选择“采用线性模型”“假定非负”。即可进行求解得结果，实现最少时间为70.
人数跟任务不等：（人少任务多）要求每人都有任务，要求每个任务都要完成。
与人数任务相等的情况类似，只需要将约束条件稍作改变即可。
（二）动态规划
1、资源分配问题
其中，B19==SUM(B13:B18)；
E21==SUMPRODUCT(B13:B18,A13:A18)+SUMPRODUCT(C13:C18,A13:A18)+SUMPRODUCT(D13:D18,A13:A18);
目标值C10=SUMPRODUCT(B2:D7,B13:D18)。
规划求解得：分配给乙分厂2台机器，分配给丙分厂3台机器，甲不分配机器，所得利润为21。
2、机器分配问题
其中，D2=SUM(B2:C2);
F3=0.5*B2+0.8*C2;
目标值
I7=SUMPRODUCT(B2:C2,H2:I2)+SUMPRODUCT(B3:C3,H2:I2)+SUMPRODUCT(B4:C4,H2:I2)+SUMPRODUCT(B5:C5,H2:I2)+SUMPRODUCT(B6:C6,H2:I2)。
规划求解得最优结果如题，所能达到的最大利润为2790。
3、载货问题
其中，E7=SUMPRODUCT(B7:B9,B2:B4)；
目标单元格F10=SUMPRODUCT(B7:B9,C2:C4);
规划求解如图，装载1类货与3类货各一件，利润为26。
五、实验体会
通过实验，觉得用excel做这类题速度很快，很方便。首先就是要掌握题目梗概，有一个基本的轮廓，才能为建模做好铺垫；将题目的信息输入excel表格中；建模，确定变量，约束条件，目标值的计算方法，求解便可。
★ 小数乘整数说课稿
★ 《小数除以整数》说课稿
★ 数学教案－整数除以分数
★ 分数乘整数练习题
★ 《分数除以整数》说课稿
★ 《小数乘整数》教学设计
★ 分数乘整数教学设计
★ 小数乘整数教学设计
★ 分数除以整数教学设计
整数二次规划 篇3
关键词：Matlab语言,整数规划,枚举法,线性规划函数,最优解
1 Matlab语言线性规划函数linprog介绍
[x,fval,exitflag,output,lambda]=linprog(f,a,b,aeq,beq,lb,ub).
在输入部分,f是目标函数,它以列向量形式出现;a、b分别是线性规划中不等式约束的技术系数矩阵和资源向量;aeq、beq分别是线性规划中的技术系数矩阵和资源向量;这其中如有缺省,则以[]代替;lb是决策变量下界,ub是决策变量上界。在输出部分,x是线性规划最优解,fval是线性规划最优值;exitflag是输出标记,当exitflag=1时,表示线性规划有解,当exitflag=-1时,表示线性规划无解;output是指算法和迭代情况;lambda是指存储情况。当程序通过时,屏目上有一段文字:Optimization terminated successfully(最优化成功地结束),它表示程序通过。当程序中有问题时,屏目上会用红字告知,在某行某列有什么性质的问题。这些都显示出Matlab语言的智能化的优势。下面举例说明Matlab语言线性规划函数的应用。
例:minz=3x1+6x2+2x3+4x4+5x5+3x6+3x7+4x8+x9+7x10+5x11+2x12
下面给出例题Matlab计算程序。
f=[3 6 2 4 5 3 3 4 1 7 5 2]’;
o=ones(1,4);z=zeros(1,4);y=eye(4);
a=[o,z,z;z,o,z;z,z,o];b=[70 80 65]’;
aeq=[y,y,y];beq=[40 30 70 60]’;lb=zeros(12,1);
[x,fval,exitflag,output,lambda]=linprog(f,a,b,aeq,beq,lb);
因为没有规定上界,故可不填ub。
程序执行后得exitflag=1,故线性规划有解。又fval=460,即最小值为460,並得优解是;
x1=0,x2=0,x3=70,x4=0,x5=0,x6=30,x7=0,x8=35,x9=40,x10=0,x11=0,x12=25.
2 整数规划的枚举法
应用Matlab语言的线性规划函数linprog,先取消整数限制求解,因目标函数为线性函数,它具有一致倾斜性,再求出整数规划的最优解。下面举例说明。
例1:
这个问题可转化为:
解:下面对转化后的问题求解,先取消整数限制求解。
f=[3 2]';
a=[2 3;2 1];b=[14 9]';lb=[0 0]';
[w,fv,ex]=linprog(-f,a,b,[],[],lb);
%w1=3.25,w2=2.5,fv=-14.75.
因目标函数为线性函数,它具有一致倾斜性,故其整数规划解应在上述解附近,现参照w1,w2给出x1,x2的取值范围,用枚举法求解。
z为行向量,它是满足约束条件的整型点的数值。
[zm,mi]=max(z);%此处zm=14为最大值,mi=19为其在z中的序号。
如果将z向量展开,若还有元素值=zm,便可查出其它最优解。
由上述计算可知例1的最优解为:x1=4,x2=1,其最大值为14。
在计算时,可调整x1和x2的取值范围,以观察结果,如取x1=0:8,x2=0:8等。
例2:
解:下面用枚举法求解,给出Matlab计算程序。
由此可知例2的最优解为x1=2,x2=6,x3=1其最大值为38。
3 结束语
Matlab语言是由美国Marhwords公司于1984年正式推出,后集语言专家和各类技术专家的共同努力,版本逐次更新,功能更为完善。该文采用的是2007年1月发行的Matlab 7.4版,跟原有的计算机语言相比,它具有简洁、直观和智能化的优势。作者所提算法较原有算法,具有简洁、快捷和直观的特点,值得推广。
参考文献
[1]张志涌.精通MATLAB6.5版[M].北京:北京航空航天大学出版社,2003.3.
[2]胡运权.运筹学教程[M].2版.北京:清华大学出版社,2003.
[3]胡知能,徐玖平.运筹学——线性系统优化[M].北京:科学出版社,2003.
[4]刁在筠,郑汉鼎,刘家壮,等.运筹学[M].2版.北京:高等教育出版社,2001.9.
[5]吴良刚,徐选华,王坚强,等.运筹学[M].长沙:湖南人民出版社,2001.3.
[6]王沫然.Matlab与科学计算(二)[M].西安:电子出版社,2003.9.
[7]罗建军,杨琦.精讲多练MATLAB[M].西安:西安交通大学出版社,2002.