论文部分内容阅读
摘要：本文以出口报刊邮寄费用最小为目标函数，以办刊数量为优化变量，并综合考虑了公司运营容量、海外市场需求量，建立了邮寄费用选择模型。针对出口报刊邮寄费用的特点，采用整数规划的分支定界模型求解，运用该方法既可以提高计算效率，又可以在较大解空间范围内获得最优出口数量组合方案，使得选型结果最优。
关键词：报刊征订；整数规划；分支定界
一、引言
在图书出口中，如何降低邮寄费用是一项重要任务。中文书刊对国外出口业务是中华图书进出口总公司的主营业务之一，在国内，总公司下辖有两个分公司也可执行对外出口书刊业务；国外主要市场集中于东南亚地区。因而，该课题是一种多对多的关系。国内图书出口过程中，由于邮寄距离不同，邮寄方式及人工费用不用，导致从各部门寄往国外各市场的费用也不同。现行的各种邮寄策略中，大多数只考虑本分公司的利益，从自身单位利润最大化出发，没有从整体上把握，得到一种全局最优。针对这一问题，本文提出了以总体邮寄成本费用最小为目标函数，建立了邮费优化选型数学模型，应用整数规划确定最优解的新方法。
二、模型的建立与描述
根据邮寄出去的书刊数量必须为整数的基本要求，本文采用整数规划的分支定界法对邮寄费用进行优化。
整数规划作为一种寻求最优解的优化方法，专门求解对决策变量要求是整数的线性规划问题，该方法主要以单纯形法为基础，运用分支定界方法对非整数解进行分支求解，分支定界法是一种隐枚举法或部分枚举法，其关键是分支和定界。
若整数规划的松弛问题的最优解不符合整数要求，假设x1=bi不符合整数要求，[b]是不超过b1的最大整数，则构成两个约束条件x1≤[b1]和x1≥[b1]+l，分别将其加入松弛问题中，形成两个分支。根据需要，各后继问题可以类似方法进行分支，如此继续，直到获得整数规划的最优解，这就是所谓的“分支”。
所谓“定界”，是在分支过程中，若某个后继问题恰巧获得整数规划的一个可行解，那么它的目标函数值就是一个“界限”，作为处理其他分支的一个依据。因为整数规划问题的可行解集是它的松弛问题可行解集的一个子支，前者解的目标函数值不会优于后者函数值，所以，对于那些相应松弛问题最优解的目标函数值比上述“界限”值差的后继问题，就可以剔除而不再考虑。当然，如果在以后的分支过程中出现了更好的“界限”，而“定界”则可以取代原来的界限，这样可以提高定界的效果。
“分支”为整数规划最优解的出现创造了条件，而“定界”则可以提高搜索的效率。经验表明：根据对实际问题的了解，选择一个合理的“界限”，可以提高分支定界法的搜索效率。
整数规划分支定界法其目标函数和约束条件为：
目标函数：S(x1,x2 ……xk)=cl x1 +c2 x2+……ckxk,
约束方程：
a11x1+a12x2+……a1k+xk ≤(或=，或≥)b1
a21x1+a22x2+……a2k+xk ≤(或=，或≥)b2
……………………………………………………………......
ak1x1+ak2x2+……a2kxk ≤(或=，或≥)bk
其中：xj为整数，j=l,2, ……,k.
并要求bi≥10，i=1,2,……,m,
优化选型原则：设市场需求量已定情况下，满足各单位存货和海外市场的订货量要求；设计年限内，满足邮寄费用最小要求。
适用条件：公司运营容量、海外市场需求量已知；各分公司可分别向各海外市场进行图书邮寄。
2.1目标函数的确定
通常表示图书出口效益特征的主要指标有海外市场容量大小、分公司选址和有机费用问题，同时考虑这三个因素的指标有年图书出口情况和邮寄费用等。因此很多优化问题可以用海外市场容量或邮寄费用成本最小作为目标函数。但是在目前的规划阶段，分公司的选址和海外市场容量都已经确定下来，短期内不能做出调整，否则成本太高。因此以公司选址出或海外市场定位作为目标函数将会给计算工作带来很大麻烦。由于图书出口效益与邮寄费用有密切的关系，如如果将市场容量考虑不足，就会造成某市场的出口书刊会挤压或者不能满足市场需求。一方面导致了邮费增加，造成不必要的浪费，引起效率；另一方面，可能导致需求不足，无法完成既定目标，并且为以后报刊出口工作造成不良影响。为此，在初步设计阶段可以把最小邮寄费用作为有机策略优化选型的目标函数,表达式为：
S(x1,x2……xk)=c1x1+c2x2+……ckxk，
式中：ci——书刊出口到市场邮寄成本(i=1,2,3……k)；
xi——出口到海外市场i的书刊数量。
2.2约束条件的确定
首先，若出口到某海外市场的总书刊数量为零，表示不选该种市场，但若出口书刊的数量为负数却毫无意义。因此，出口书刊数量必须满足x1,x2,x3≥0的约束条件。其次，出口书刊数量也不可能为小数，因为分公司和海外市场和多对多的关系，因此，若出口到某海外市场的书刊数量零点几是不可能的，故出口书刊数量必须满足x1,x2,x3为非负整数的约束。另外，对于跨区域的邮寄，其出口数量是允许有一定变化幅度的。出口数量太小不能满足市场要求，出口数量太大又会造成挤压，造成不必要浪费，增加邮资成本。因此，其约束条件可表示如下：
x1,x2,……xk≥0
x1∈N
Qmin≤Q≤Qmax。
三、案例实证分析
3.1问题的来源、提出
中华图书进出口总公司的主营业务之一是中文书刊对国外出口业务，由中文书刊出口部两个分公司负责。就中文报刊而言，每年10—12月为下一年度报刊订阅的征订期，在此期间，为巩固老订户，发展新订户，要向国外个人、大学图书馆、科研机构等无偿寄发小礼品和征订宣传推广材料。
中华图书馆进出口总公司在深圳、上海设有分公司，总公司从形成内部竞争机制，提高服务竞争的角度考虑，允许这两家分公司也部分经营中文报刊的出口业务，但为维护公司整体利益，避免内部恶性竞争，公司对征订期间三个部门寄发征订材料的工作做了整体安排（详见表-1）。日本、韩国以及中国香港地区集中了该公司的绝大部分中文报刊订户，根据订户数分布数量的不同，寄发征订材料的数量也不同，对此公司也作了安排（详见表-2）。
由于一般情况下，这些材料无论由三家中哪个部门寄出，征收订户的效果大致相同；同时，无论读者向哪个部门订阅，为总公司创造的利益均是大致一样的。但由于各部门邮寄距离不同，邮寄方式及人工费用不用，导致从各部门寄往各地的费用也不同（详见表-3）。
由于寄发量大且每份材料的寄发费用较高，导致每年征订期日本、韩国以及中国香港特别行政区三地读者征订费用很高昂，大大加重了经营成本。为此，如何在服从公司总体安排的前提下合理规划各部门的寄发数量，从而使总费用最少就成为一项有意义、值得研究的课题，根据所学运筹学知识，尝试对以上问题进行探讨。
3.2数据的获得与实证分析
从1998年征订起，获得如表-1，表-2和表-3所示的数据：
要求做出一个公司整体的中文书刊征订材料的邮运方案，使得公司总的邮运费最小。
设A1A2A3 分别表示“中文书刊出口部”、“深圳分公司”和“上海分公司”。B1B2B3分别表示“日本”、“香港”和“韩国”。
经过对以上数据的分析，我们可以得到该问题是一个混合的整数规划问题，建立模型如下：
约束条件为：
相应模型图表为：
表中数字表示Ai邮寄到Bi的邮件数量。
通过以上分析，我们可知：在该设定时间范围内，中文书刊出口部寄往日本、中国香港特别行政区、韩国的书刊数量分别为7500、2500、5000册；深圳分公司出口部寄往日本、中国香港特别行政区、韩国的书刊数量分别为0、7500、0册；上海分公司寄往日本、中国香港特别行政区、韩国的书刊数量分别为7500、0、0册。
四、结论
本文介绍的优化选型方法是一种实用方法，它可以用于书刊出口的任务阶段和初设阶段，同样可以用于分公司的选址的优化调度。由于该方法计算量较大，故需要辅助计算机程序实现。因而，如何设计一款实用的软件可以作为本文的后续研究。
由于该模型在应用时进行了一些简化，计算结果仅供参考。在实际推广应用时，可通过广泛调查，采用实际值，减少简化。
参考文献：
[1 ] 李爱云，吴建华.整数规划在水源选型中的应用研究[J].山西水利，2008(2)
[2 ] 高风华等，整数规划在农村饮用水安全水源优化配置模型中的应用与探讨[J].山东大学学报（工学版），2007(12)
[3 ] 张方，刘丙午.基于混合整数规划模型的物流配送中心选址优化[J].分析与决策，2007(11)
[4 ] 伍翔，李四福，於世为.煤矿建筑安装工程项目优化模型研究[J].决策与信息，2008（7）
[5 ] 邓成梁，诸克军.运筹学的原理与方法[M].华中科技大学出版社，2001
[6 ] 王恩奎，金春来.货币供给量对通货膨胀影响的实证分析[J].世界华商经济年鉴，2008（7）
[7 ] 何宝亮，伍翔.工程项目采稿分析风险研究综述[J].总裁，2008（9）
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
关键词：报刊征订；整数规划；分支定界
一、引言
在图书出口中，如何降低邮寄费用是一项重要任务。中文书刊对国外出口业务是中华图书进出口总公司的主营业务之一，在国内，总公司下辖有两个分公司也可执行对外出口书刊业务；国外主要市场集中于东南亚地区。因而，该课题是一种多对多的关系。国内图书出口过程中，由于邮寄距离不同，邮寄方式及人工费用不用，导致从各部门寄往国外各市场的费用也不同。现行的各种邮寄策略中，大多数只考虑本分公司的利益，从自身单位利润最大化出发，没有从整体上把握，得到一种全局最优。针对这一问题，本文提出了以总体邮寄成本费用最小为目标函数，建立了邮费优化选型数学模型，应用整数规划确定最优解的新方法。
二、模型的建立与描述
根据邮寄出去的书刊数量必须为整数的基本要求，本文采用整数规划的分支定界法对邮寄费用进行优化。
整数规划作为一种寻求最优解的优化方法，专门求解对决策变量要求是整数的线性规划问题，该方法主要以单纯形法为基础，运用分支定界方法对非整数解进行分支求解，分支定界法是一种隐枚举法或部分枚举法，其关键是分支和定界。
若整数规划的松弛问题的最优解不符合整数要求，假设x1=bi不符合整数要求，[b]是不超过b1的最大整数，则构成两个约束条件x1≤[b1]和x1≥[b1]+l，分别将其加入松弛问题中，形成两个分支。根据需要，各后继问题可以类似方法进行分支，如此继续，直到获得整数规划的最优解，这就是所谓的“分支”。
所谓“定界”，是在分支过程中，若某个后继问题恰巧获得整数规划的一个可行解，那么它的目标函数值就是一个“界限”，作为处理其他分支的一个依据。因为整数规划问题的可行解集是它的松弛问题可行解集的一个子支，前者解的目标函数值不会优于后者函数值，所以，对于那些相应松弛问题最优解的目标函数值比上述“界限”值差的后继问题，就可以剔除而不再考虑。当然，如果在以后的分支过程中出现了更好的“界限”，而“定界”则可以取代原来的界限，这样可以提高定界的效果。
“分支”为整数规划最优解的出现创造了条件，而“定界”则可以提高搜索的效率。经验表明：根据对实际问题的了解，选择一个合理的“界限”，可以提高分支定界法的搜索效率。
整数规划分支定界法其目标函数和约束条件为：
目标函数：S(x1,x2 ……xk)=cl x1 +c2 x2+……ckxk,
约束方程：
a11x1+a12x2+……a1k+xk ≤(或=，或≥)b1
a21x1+a22x2+……a2k+xk ≤(或=，或≥)b2
……………………………………………………………......
ak1x1+ak2x2+……a2kxk ≤(或=，或≥)bk
其中：xj为整数，j=l,2, ……,k.
并要求bi≥10，i=1,2,……,m,
优化选型原则：设市场需求量已定情况下，满足各单位存货和海外市场的订货量要求；设计年限内，满足邮寄费用最小要求。
适用条件：公司运营容量、海外市场需求量已知；各分公司可分别向各海外市场进行图书邮寄。
2.1目标函数的确定
通常表示图书出口效益特征的主要指标有海外市场容量大小、分公司选址和有机费用问题，同时考虑这三个因素的指标有年图书出口情况和邮寄费用等。因此很多优化问题可以用海外市场容量或邮寄费用成本最小作为目标函数。但是在目前的规划阶段，分公司的选址和海外市场容量都已经确定下来，短期内不能做出调整，否则成本太高。因此以公司选址出或海外市场定位作为目标函数将会给计算工作带来很大麻烦。由于图书出口效益与邮寄费用有密切的关系，如如果将市场容量考虑不足，就会造成某市场的出口书刊会挤压或者不能满足市场需求。一方面导致了邮费增加，造成不必要的浪费，引起效率；另一方面，可能导致需求不足，无法完成既定目标，并且为以后报刊出口工作造成不良影响。为此，在初步设计阶段可以把最小邮寄费用作为有机策略优化选型的目标函数,表达式为：
S(x1,x2……xk)=c1x1+c2x2+……ckxk，
式中：ci——书刊出口到市场邮寄成本(i=1,2,3……k)；
xi——出口到海外市场i的书刊数量。
2.2约束条件的确定
首先，若出口到某海外市场的总书刊数量为零，表示不选该种市场，但若出口书刊的数量为负数却毫无意义。因此，出口书刊数量必须满足x1,x2,x3≥0的约束条件。其次，出口书刊数量也不可能为小数，因为分公司和海外市场和多对多的关系，因此，若出口到某海外市场的书刊数量零点几是不可能的，故出口书刊数量必须满足x1,x2,x3为非负整数的约束。另外，对于跨区域的邮寄，其出口数量是允许有一定变化幅度的。出口数量太小不能满足市场要求，出口数量太大又会造成挤压，造成不必要浪费，增加邮资成本。因此，其约束条件可表示如下：
x1,x2,……xk≥0
x1∈N
Qmin≤Q≤Qmax。
三、案例实证分析
3.1问题的来源、提出
中华图书进出口总公司的主营业务之一是中文书刊对国外出口业务，由中文书刊出口部两个分公司负责。就中文报刊而言，每年10—12月为下一年度报刊订阅的征订期，在此期间，为巩固老订户，发展新订户，要向国外个人、大学图书馆、科研机构等无偿寄发小礼品和征订宣传推广材料。
中华图书馆进出口总公司在深圳、上海设有分公司，总公司从形成内部竞争机制，提高服务竞争的角度考虑，允许这两家分公司也部分经营中文报刊的出口业务，但为维护公司整体利益，避免内部恶性竞争，公司对征订期间三个部门寄发征订材料的工作做了整体安排（详见表-1）。日本、韩国以及中国香港地区集中了该公司的绝大部分中文报刊订户，根据订户数分布数量的不同，寄发征订材料的数量也不同，对此公司也作了安排（详见表-2）。
由于一般情况下，这些材料无论由三家中哪个部门寄出，征收订户的效果大致相同；同时，无论读者向哪个部门订阅，为总公司创造的利益均是大致一样的。但由于各部门邮寄距离不同，邮寄方式及人工费用不用，导致从各部门寄往各地的费用也不同（详见表-3）。
由于寄发量大且每份材料的寄发费用较高，导致每年征订期日本、韩国以及中国香港特别行政区三地读者征订费用很高昂，大大加重了经营成本。为此，如何在服从公司总体安排的前提下合理规划各部门的寄发数量，从而使总费用最少就成为一项有意义、值得研究的课题，根据所学运筹学知识，尝试对以上问题进行探讨。
3.2数据的获得与实证分析
从1998年征订起，获得如表-1，表-2和表-3所示的数据：
要求做出一个公司整体的中文书刊征订材料的邮运方案，使得公司总的邮运费最小。
设A1A2A3 分别表示“中文书刊出口部”、“深圳分公司”和“上海分公司”。B1B2B3分别表示“日本”、“香港”和“韩国”。
经过对以上数据的分析，我们可以得到该问题是一个混合的整数规划问题，建立模型如下：
约束条件为：
相应模型图表为：
表中数字表示Ai邮寄到Bi的邮件数量。
通过以上分析，我们可知：在该设定时间范围内，中文书刊出口部寄往日本、中国香港特别行政区、韩国的书刊数量分别为7500、2500、5000册；深圳分公司出口部寄往日本、中国香港特别行政区、韩国的书刊数量分别为0、7500、0册；上海分公司寄往日本、中国香港特别行政区、韩国的书刊数量分别为7500、0、0册。
四、结论
本文介绍的优化选型方法是一种实用方法，它可以用于书刊出口的任务阶段和初设阶段，同样可以用于分公司的选址的优化调度。由于该方法计算量较大，故需要辅助计算机程序实现。因而，如何设计一款实用的软件可以作为本文的后续研究。
由于该模型在应用时进行了一些简化，计算结果仅供参考。在实际推广应用时，可通过广泛调查，采用实际值，减少简化。
参考文献：
[1 ] 李爱云，吴建华.整数规划在水源选型中的应用研究[J].山西水利，2008(2)
[2 ] 高风华等，整数规划在农村饮用水安全水源优化配置模型中的应用与探讨[J].山东大学学报（工学版），2007(12)
[3 ] 张方，刘丙午.基于混合整数规划模型的物流配送中心选址优化[J].分析与决策，2007(11)
[4 ] 伍翔，李四福，於世为.煤矿建筑安装工程项目优化模型研究[J].决策与信息，2008（7）
[5 ] 邓成梁，诸克军.运筹学的原理与方法[M].华中科技大学出版社，2001
[6 ] 王恩奎，金春来.货币供给量对通货膨胀影响的实证分析[J].世界华商经济年鉴，2008（7）
[7 ] 何宝亮，伍翔.工程项目采稿分析风险研究综述[J].总裁，2008（9）
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文