整数规划案例

战略性的选址问题
TRD的主要客户都分布在5个国家: 25%在英国,30%在德国,15%在瑞士,10% 在意大利,20%在法国.
平均送货天 数 England Germany Switzerland Italy France London 0.5 2 3 3 1.5 Madrid 2.5 3 2 1 2 Paris 1.5 1 2 2 0.5 Hamburg 2 0.5 1.5 2 1 Rome 3 2 1 0.5 2
赛塔克国际公司
虽然,赛塔克生产数以百计的不同产品, 但管理层发现作为大范围的制造决策, 四种产品分类就已足够:大型机 (MFRAMES),小型机(MINIS),微 机(PCS)和打印机(PRINTERS).赛 塔克产品的两个主要市场是北美(主要 在美国)和欧洲(主要在西欧).
问题
赛塔克每季度进行大范围的生产决策.每个季 度末,管理层开会讨论过去一季度的生产,并 制定出下一季度的生产计划.会议的主要目的 是确定四类主要产品的生产目标.根据这一生 产目标,工厂的管理者可以估计出下一季度各 自工厂所需的劳动力和原材料,从而可以调整 工人的数量和签订长期的原料供货合同. 虽然季度会议主要是政策性的,但是为了获 得高质量的生产决策也必须完成大量的数据分 析.接着,我们会介绍所用到的数据和分析的 结构.
战略性的选址问题
用EXCEL求解该优化问题,得到的解为: y1=0,y2=0,y3=1,y4=0,y5=1; x13=1,x23=0.58,x25=0.42,x35=1,x45=1,x55=1; w1=1.5,w2=1.42,w3=1,w4=0.50,w5=0.50. 也就是说,应该将服务中心建立在Paris和Rome; 英国所有的和法国58%的顾客由设在Paris的服务中心 来服务, 其余国家所有的顾客由设在Rome的中心来服务.
整供应链选址问题
战略性的选址问题
TRD是一家电脑制造公司,它现在正在考虑在欧洲建 立一些服务中心.而公司目前在London,Madrid和 Paris已有三家服务中心.当欧洲的顾客遇到主机发生 问题时,他们就将问题反馈给当地TRD公司的办公室. 公司接到反映后会派一名工程师前去查明故障原因. 通常在有需要时,工程师会向离顾客最近的服务中心 订一些电脑零部件,要求服务中心将这些零部件送给 顾客.但是,并不是所有的时候都能作到这一点. TRD公司运营部副经理Johan已经受到过好几个大客户 的抱怨,他们抱怨说,他们通常要等两天以上的时间 才能收到那些订购的零部件.另外,公司还面临运输 费用和服务中心维护费用都大幅度上升的难题.
利润(Cijk) 工厂 大型机(i=1) 小型机(i=2) 微机(i=3) 打印机(i=4)
北美(k=1) 欧洲(k=2) 北美(k=1) 欧洲(k=2) 北美(k=1) 欧洲(k=2) 北美(k=1) 欧洲(k=2) 13694.03 14709.96 13216.34 8914.47 9951.04 9148.55 6956.23 7852.36 7272.89 1457.18 1395.35 1197.52 1037.57 1082.49 1092.61 1663.51 1554.55 1478.90 1345.43 1270.16 1312.44
ຫໍສະໝຸດ Baidu
综上所述,该问题的离散优化模型为: minimize 20y1+15y2+22y3+21y4+16y5 subject to: 需求: xi1+xi2+xi3+xi4+xi5 =1 i=1,2,3,4,5 英国: w1=0.5x11+2.5x12+1.5x13+2x14+3x15 德国: w2=2x21+3x22+x23+0.5x24+2x25 瑞士: w3=3x31+2x32+2x33+1.5x34+x35 意大利: w4=3x41+x42+2x43+2x44+0.5x45 法国: w5=1.5x51+2x52+0.5x53+x54+2x55 送货时间: wi≤1.5 i=1,2,3,4,5 总的送货时间: 0.25w1+0.3w2+0.15w3+0.10w4+0.20w5≤1.1 逻辑性约束 xij≤yj i,j=1,2,3,4,5 服务中心的数量:2≤y1+y2+y3+y4+y5≤3 非负性: xij≥0 i,j=1,2,3,4,5 整数性: yj =0,1
模型
总利润用表4中的数据进行计算.表中 的单件利润是该件产品在相应生产加工 工厂和赛塔克国际公司分别所获的利润 总和.这样,表5中的目标函数也就表示 赛塔克所获的总利润,该线性最优化模 型所获的最优解也就是目标函数所确定 的能使赛塔克的总利润达到最大的生产 决策.
赛塔克国际公司
赛塔克公司的总部位于马萨诸塞州的伯 明顿.制造工厂位于伯明顿,台湾和爱 尔兰.这些工厂都是赛塔克的全资子公 司.由于台湾和爱尔兰低廉的劳动力和 更优厚的公司税率,使得赛塔克的海外 子公司能以一个更低的成本进行生产. 然而,为了推进本地的投资和工业发展, 当地政府对从子公司撤资都有很严格的 规定和程序.
问题
分析首先从市场部开始,要作出下一季度的需求预测.这些预测见 表1.正如所预见的,微机的需求量大大超过小型机,而后者又大 大超过大型机.同时北美市场的需求比欧洲市场超出两倍有余.虽 然对于市场部进行需求预测的方法有所争论,但近年来,它所作的 预测多是相当准确的.
市场需求(Dik) 产品(i) 大型机(i=1) 小型机(i=2) 微机 (i=3) 打印机(i=4) 市场(k) 北美(k=1) 962 4,417 48,210 15,540 表1:需求预测 欧洲(k=2) 321 1,580 15,400 6,850
产品(i) 大型机(i=1) 小型机(i=2) 微机 (i=3) 打印机(i=4) 空间/件(si) 17.48 17.48 3.00 5.30 劳动力小时/件(li) 79.0 31.5 6.9 5.6
表3:资源利用率
问题
分析所需的最后一部分数据从会计部提供(见表4).表4中的 数据代表了单件产品的利润情况.例如,在伯明顿生产并在北 美市场销售的每台大型机可以为赛塔克提供$16,136.46的税后 利润.获利最少的产品是伯明顿生产的用于欧洲市场的微机. 为了继续我们的分析框架,对表4中数据及其相关的会计方法 讨论将在以后进行.
对j=1,2,3,4,5定义决策变量
1 yj = 0
选 在建 服 立 中 j 立 务 服 否 则
对i=1,2,3,4,5和j=1,2,3,4,5定义变 量 xij为i国总的顾客要求由城市j服务的比例. 与线性规划不同,变量yj只能取1或者0,若yj取 一个分数值,是没有任何意义的.
战略性的选址问题
模型
决策变量Xijk,表示的是在工厂j生产并在市 场k销售的产品i的产量.例如,X231所代表的 就是一季度中在爱尔兰工厂生产并在北美市场 销售的小型机的产量.这样的话,由决策变量 就可得出下一季度的生产决策. 现在的目标是要使赛塔克公司在下一季度中 所获的总利润最大.总利润也就是各全资子公 司和赛塔克本身利润的总和.虽然,也可以考 虑其他的目标,但管理层认为利润最大化的决 策要求最能体现赛塔克股东们的利益.
问题
空间容量(SCj) 工厂(j) 伯明顿(j=1) 台湾 (j=2) 爱尔兰(j=3) (平方千尺) 540.71 201.00 146.90 劳动力容量(LCj) (千小时) 277.71 499.24 80.17
表2:工厂的生产容量
问题
要应用生产容量数据还需要利用率数据(见表3). 通过利用率数据可以确定单件产品生产所需的空间和 劳动力数据.例如,要生产一台大型机需要17.48平 方尺的空间和79小时的劳动力,而生产一台微机需要 3平方尺的空间和6.9小时的劳动力.
目标函数是要极小化年运营费用: 费用=20y1+15y2+22y3+21y4+16y5 每个国家顾客的所有需求都要得到满足: 需求: xi1+xi2+xi3+xi4+xi5 =1 i=1,2,3,4,5 每个国家平均的送货时间均不超过1.5天: 英国: w1=0.5x11+2.5x12+1.5x13+2x14+3x15≤1.5 德国: w2=2x21+3x22+x23+0.5x24+2x25≤1.5 瑞士: w3=3x31+2x32+2x33+1.5x34+x35≤1.5 意大利: w4=3x41+x42+2x43+2x44+0.5x45≤1.5 法国: w5=1.5x51+2x52+0.5x53+x54+2x55≤1.5
案例
赛塔克国际公司
赛塔克国际公司
赛塔克国际公司是一家大型的计算机及其周边 设备生产商.该公司创建于1951年,并以一种 创新的大型机操作系统进入市场.赛塔克公司 早在软件的"用户界面友好性"被商业社会广 泛接受以前,就已认识到了这一点,并据此信 条不断发展壮大.赛塔克不断显示出它作为个 人计算机最大生产商之一的商业敏锐性,同时 也致力于计算机网络和办公自动化方面的开发 研究.
问题
现在从公司的市场部转向制造部.在每季度开会以前, 各个工厂的管理者被要求提交一份有关各自工厂生产 容量限制的详细报告.这些数据汇总在表2中.考虑两 种生产容量的限制:空间和劳动力.空间方面主要考 虑生产线的设置和库存容量.劳动力主要考虑基础制 造和流水线,但是各工厂的劳动力数量有一个法定的 限制数额.伯明顿的工厂是最大的,它的规模是台湾 工厂的两倍,并差不多是爱尔兰工厂规模的四倍.但 是伯明顿的劳动力总数不过是台湾工厂人数的55%. 爱尔兰工厂的劳动力数量等比例小于伯明顿,使得该 厂更象一个小规模的伯明顿工厂. 图表如下页:
战略性的选址问题
为此,Johan决定重新选择服务中心的地址.可 能的话,他会将服务中心的数量减至2个,以 节省运营费用.除了London,Madrid和Paris以 外,Johan还将Hamburg和Rome列入他的选址 范围.
运营费用 Cost($million) London 20 Madrid 15 Paris 22 Hamburg 21 Rome 16
伯明顿(j=1) 16136.46 台湾 (j=2) 17358.14 爱尔兰(j=3) 15652.68
表4:单件利润($)
模型
以上信息由管理信息组汇总,并通过一个线 性最优化模型来分析和制定有关赛塔克产品生 产的基本策略.这个线性最优化模型已在表5 中给出. 我们用下标i来标识所生产的产品大类.如, i 我们分别用L1,L2,L3和L4分别代表用于生 产大型机,小型机,微机和打印机所需的劳动 力.同样的以下标j来标识三个工厂.以SC1, SC2和SC3分别代表伯明顿,台湾和爱尔兰的 工厂所能提供的总空间.最后以下标k来标识 两个市场.这样的话,D41和D42分别代表北 美和欧洲市场对打印机(i=4)的需求.
战略性的选址问题
Johan要决定的是究竟在哪些城市建立服 务中心.合理的目标就是在确保服务质 量的同时使得运营费用尽量的少.具体 而言,他希望对在5个国家的顾客,送货 的天数分别都不超过1.5天,而所有的顾 客总的平均送货时间不超过1.1天.他同 时想要了解运输费用与送货时间的相互 关系.
战略性的选址问题
用j=1,2,3,4,5来表示5个备选的城市: 1表示London, 2表示Madrid, 3表示Paris, 4表示Hamburg, 5就表示Rome. 用i=1,2,3,4,5来表示5个国家: 1表示英国, 2表示德国, 3表示瑞士, 4表示意大利, 5就表示法国.
战略性的选址问题
战略性的选址问题
希望总的平均送货时间不超过1.1天: 总的送货时间: 0.25w1+0.3w2+0.15w3+0.10w4+0.20w5≤1.1 对i=1,2,3,4,5和j=1,2,3,4,5,如果 yj=0,那么就只能有xij=0: 逻辑性约束:xij≤yj 服务中心数量应满足的条件: 服务中心的数量:2≤y1+y2+y3+y4+y5≤3