运筹学大作业.doc

运筹学课程上机实践要求及内容（2）一、 实验教学的目的和要求目的：借助运筹学软件的强大功能，通过小组的充分讨论，对管理实践中的实际问题进行建模、求解，并对求解结果进行分析（特别是敏感性分析），进而激发学生的学习兴趣和热情，克服对课程学习的“恐惧感”。要求：熟练掌握LINGO、WinQSB等软件的基本功能和基本语法结构，能用软件对运筹学问题进行求解和分析。二、 请于第1次-第6次上机时间及平时完成。三、 作业务请写清学号、姓名、专业、班级，上机作业格式请用老师提供的模版。四、 编写的代码请用记事本单独保存。五、 要求所有题目用LINGO和教材自带的求解软件各做一遍。并分析解释求解的结果。六、 各题目中的A，B，C，D，E，F为参数，除特别规定外，请自行设定，各个同学参数值不能相同，若发现完全一致的，作业以零分计。A=1，B=2，C=2，D=4，E=4，F=1第1题(线性规划) (1)介绍单纯型算法及其处理人工变量的两阶段法； (2)建立下列问题的数学模型并求解，讨论资源的影子价格； 某造纸厂拟生产漂白松木浆、包装纸(水泥、松木包装纸、松木本色纸)、漂白桦木纸和胶版纸等四种产品，单位产品所需资源情况见表1，市场上胶版纸的需求量不超过6000吨。(a)制订该造纸厂的生产计划；(b)若电的资源可用量下降10%，重新制订该造纸厂的生产计划。表1 单位产品用量产品所需资源漂白松木浆包装纸漂白桦木纸胶版纸资源可用量松木4.2502.4155000m3桦木1153.5102000m3水19044043044018000000m3电920880880134045000000千瓦汽7889375000吨单位产品利润(元/吨)3500384034003960 (3)结合本题，谈谈你对线性规划的认识。Hint: 若参数为5，5，5，5，5，5，则最优目标函数值为(a)167236800；(b)167236800。解：(1)单纯形法是求解线性规划问题的通用方法。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。两阶段单纯形法也是一种人工变量法，它的算法可分为两个阶段：第一阶段，引入人工变量，构造一个具有标准基的新线性规划，求解这个新线性规划，其结果有两种可能：或者将原问题的约束方程组化成具有标准基的形式，或者提供信息，表明原问题没有可行解。第二阶段，利用第一阶段所得的标准基，对原问题求解。(2)A、设分别生产漂白松木浆X1吨，包装纸X2吨，漂白桦木纸X3吨，胶版纸X4吨，则LP的数学模型为： max S=3500X1+2820X2+3400X3+3990X4约束条件为：4.2X1+5X2+2.4X4=155000 X1+X2+5X3+3.5X4=102000 190X1+440X2+430X3+440X4=18000000 920X1+880X2+880X3+1340X4=45000000 7X1+8X2+8X3 +9X4=375000 软件计算得知，当X1= 34224.319，X2=2251.572，X3=13104.822，X4=0时，取得最大利润172987547.78B、若电的可用量降低10%，则为45000000*0.9=40500000.利润最大为maxZ=3500*x1+3840*x2+3400*x3+3960*x4;4.2*x1+5*x2+2.2*x4=155000; x1+x2+5*x3+3.5*x4=103000; 190*x1+440*x2+390*x3+440*x4=18000000; 920*x1+880*x2+880*x3+1340*x4=40500000; 7*x1+8*x2+8*x3+9*x4=375000;x4=0软件计算得知，当X1=5770.914，X2=26152.433，X3=13837.067，X4=0时，获得最大利润167669569.52。（3）在线性规划的实际应用中，要明确LP问题的类型，然后套用数学模型。由于某种原因，有时线性规划的目标函数的系数和约束条件的常数不是固定的，不同情况出现的概率不同，这些参数与概率联系在一起，这是我们所关心的不同经济状况下的最优方案。第2题(线性规划) (1)介绍单纯型算法及其处理人工变量的大M法； (2)某厂在今后六个月内需租用仓库堆存物资，各月所需仓库面积及租用单价见下表，租借合同每月初可办理，问如何签约使租借费用最小？(a)试把这个问题表示成一个LP模型；(b)求该问题的解。表2A 各月所需仓库面积月份123456需用面积(平方米)210120520440340610表2B 租用单价合同租用期限123456租用单价(元/平方米)100195285370450525 (3)结合本题，谈谈你对线性规划的认识。Hint: 若参数为5，5，5，5，5，5，则最优目标函数值为222250。解：设Xij表示为第I 个月签订了为期为就个月的租用合同，i=1，2，3，4，5，6；j=1，2，3，4，5，6（1） 建模：大M法就是在目标函数中加上一个惩罚因素M作为人工变量的系数，其值可以无穷大，迭代的目标就是要去掉目标函数中的大M，否则由于-M充分地小，目标函数就无法达到最优。（2） 设租用情况如下表月份合同租用期限1234561X11X21X31X41X51X612X12X22X32X42X523X13X23X33X434X14X24X345X15X256X16minS=100（X11+X21+X31+X41+X51+X61）+195（X12+X22+X32+X42+X52）+285（X13+X23+X33+X43）+370（X14+X24+X34）+450（X15+X25）+525X16ST X11+X21+X31+X41+X51+X61=210X12+X22+X32+X42+X5 =120X13+X23+X33+X43 =520X14+X24+X34 =440 X15+X25=340X16=610（3）在企业的各项管理活动中,例如计划、生产、运输、技术等问题,如何做到最少的人力物力资源去完成一个任务，线性规划是指从各种限制条件的组合中,选择出最为合理的计算方法,建立线性规划模型从而求得最佳结果，有时要引入人工变量，用大M法或两阶段法进行求解。第3题(对偶线性规划) (1)介绍对偶理论及对偶单纯型算法； (2)一家宾馆，每天需要的服务员人数如表3所示：表3 不同时段需要的服务员人数起迄时间服务员的最少人数0-3153-6336-9289-123312-153815-183418-213321-2412 服务员由正式员工和临时工组成，每个正式员工每天连续工作6小时，每个临时工每天连续工作9小时，且在时段开始时上班，工作时正式员工数不得少于1/4。问题的目标是要求满足以上要求的最少上班人数。(a)试把这个问题表示成一个LP模型；(b)写出对偶LP；(c)求解该问题并尽可能求出所有的解。 (3)结合本题，谈谈你对对偶线性规划的认识。Hint: 若参数为5，5，5，5，5，5，则最优目标函数值为92。解：（1） 对偶理论主要研究经济学中的相互确定关系，涉及到经济学的诸多方面。产出与成本的对偶、效用与支出的对偶，是经济学中典型的对偶关系。经济系统中还有许多其他这样的对偶关系。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为mincx|Ax=b，x0，则其对偶问题（Dual Problem）为 maxyb|yAc。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c0。即知y=cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。（2） 设各时段工作的正式员工数为xi(i=1,2,3,8)，临时员工数为xi（i=9,10,1116)要求最少上班人数，则目标函数为minZ=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16 x1+x8=5x1+x2=11x2+x3=10x3+x4=11x4+x5=13x5+x6=12x6+x7=11x7+x8=4x1+x8+x9+x15+x16=15 x1+x2+x9+x10+x16=33x2+x3+x9+x10+x11=28x3+x4+x10+x11+x12=33x4+x5+x11+x12+x13=38x5+x6+x12+x13+x14=34x6+x7+x13+x14+x15=33x7+x8+x14+x15+x16=12x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16=0x1=7,x2=7,x3=3,x4=8,x5=5,x6=7,x7=4,x8=0,x9=0,x10=15,x11=3,x12=4,x13=18,x14=0,x15=4,x16=4时，上班总人数最少，为89对偶LP问题：maxZ=5y1+11y2+10y3+11y4+13y5+12y6+11y7+4y8+15y9+33y10+28y11+33y12+38y13+34y14+33y15+12y16y1+y2+y9+y10=1y2+y3+y10+y11=1y3+y4+y11+y12=1y4+y5+y12+y13=1y5+y6+y13+y14=1y6+y7+y14+y15=1y7+y8+y15+y16=1y1+y8+y9+y16=1y9+y10+y11=1y10+y11+y12=1y11+y12+y13=1y12+y13+y14=1y13+y14+y15=1y14+y15+y16=1y9+y15+y16=1y9+y10+y16=0最优解为89.05。（3）对偶问题的性质，若（LP)有最优解x*，则对偶问题（DP)也有最优解Y*,且y*是（LP)最优单纯性表松弛变量下的检验数的负值，x*是（DP）最优单纯形表中剩余变量下检验数的负值。原问题对偶问题目标函数min目标函数max约束条件数为m个对偶变量个数为m个第i个约束条件为=第i个对偶变量yi=0第i个约束条件为=第i个对偶变量yi为自由变量第4题(对偶线性规划) (1)介绍对偶理论及对偶单纯型算法； (2)一家宾馆，每天需要的服务员人数如表4所示：表4 不同时段需要的服务员人数起迄时间服务员的最少人数0-3153-6336-9289-123312-153815-183418-213321-2412 服务员由正式员工和临时工组成，每个正式员工每天连续工作6小时，每小时工资为25元，每个临时工每天连续工作9小时，每小时工资为12元，且在时段开始时上班，工作时正式员工数不得少于1/4。问题的目标是要求满足以上要求的最少工资成本。(a)试把这个问题表示成一个LP模型；(b)写出对偶LP；(c)求该问题的解。 (3)结合本题，谈谈你对对偶线性规划的认识。解：（1） 对偶理论主要研究经济学中的相互确定关系，涉及到经济学的诸多方面。产出与成本的对偶、效用与支出的对偶，是经济学中典型的对偶关系。经济系统中还有许多其他这样的对偶关系。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为mincx|Ax=b，x0，则其对偶问题（Dual Problem）为 maxyb|yAc。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c0。即知y=cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。（2） 在本题中，我设在0-3时间段内，有X1个正式员工，X2个临时工，在3-6时间段内，有X3个正式员工，X4个临时工，以此类推，所得LP的模型为：MinS=25*6（X1+X3+X5+X7+X9+X11+X13+X15）+12*9(X2+X4+X6+X8+X10+X12+X14+X16)x1+x15=4x1+x3=9x3+x5=7x5+x7=9x7+x9=10x9+x11=9x11+x13=9x13+x15=4x1+x2+x14+x15+x16=15 x1+x2+x3+x4+x16=33x2+x3+x4+x5+x6=28x4+x5+x6+x7+x8=33x6+x7+x8+x9x10=38x8+x9+x10+x11+x12=34x10+x11+x12+x13+x14=33x12+x13+x14+x15+x16=12x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16=0其最优解为10632其对偶Lp为maxZ=15y1+33y2+28y3+33y4+38y5+34y6+33y7+12y8+4y9+9y10+7y11+9y12+10y13+9y14+9y15+4y16y1+y2+y9+y10=150y2+y3+y10+y11=150y3+y4+y11+y12=150y4+y5+y12+y13=150y5+y6+y13+y14=150y6+y7+y14+y15=150y7+y8+y15+y16=150y1+y8+y9+y16=150y9+y10+y11=108y10+y11+y12=108y11+y12+y13=108y12+y13+y14=108y13+y14+y15=108y14+y15+y16=108y9+y15+y16=108y9+y10+y16=0最优解为17100（3）对偶问题的性质，若（LP)有最优解x*，则对偶问题（DP)也有最优解Y*,且y*是（LP)最优单纯性表松弛变量下的检验数的负值，x*是（DP）最优单纯形表中剩余变量下检验数的负值。原问题对偶问题目标函数min目标函数max约束条件数为m个对偶变量个数为m个第i个约束条件为=第i个对偶变量yi=0第i个约束条件为=第i个对偶变量yi为自由变量Hint: 若参数为5，5，5，5，5，5，则最优目标函数值为12280。第5题(运输问题) (1)介绍表上作业法及其求解不平衡运输问题的方法； (2)某战区军械物资仓库与所属部队之间的距离、供应关系、部队的需求量以及有关的已知条件如表5所示。(a)求解该问题；(b)若122库的可供量增加200吨，再求该问题的解。表5 仓库、部队供需数量表仓库距离km121库122库123库124库125库部队需求量(吨)部队146师386130304746447360147师348258232874319250坦克4师1401702751017587130坦克3师26035320864563140坦克2师333222213438305150守备5师120398614312971056140守备7师1599138221914931452160守备10师9016843971081110180守备6师816566103665753200仓库可供量500300300300310 (3)结合本题，谈谈你对运输问题的认识。Hint: 若参数为5，5，5，5，5，5，则最优目标函数值为(a)471620；(b)410810。（1） 解：表上作业法，是直接在运价表上求最优解的一种方法，条件是：问题求最小值、产销平衡和运价非负。它的步骤是：第一步：求初始可行解（初始调运方案）。常用的方法有最小元素法，左上角法（西北角法）；第二步：求检验数并判断是否得到最优解。常用求检验数的方法有闭回路法和位势法，当非基变量的检验数ij全部非负时得到最优解，若存在=360;x12+x22+x32+x42+x52=250;x13+x23+x33+x43+x53=130;x14+x24+x34+x44+x54=140;x15+x25+x35+x45+x55=150;x16+x26+x36+x46+x56=140;x17+x27+x37+x47+x57=160;x18+x28+x38+x48+x58=180;x19+x29+x39+x49+x59=200; x11+x12+x13+x14+x15+x16+x17+x18+x19=500; x21+x22+x23+x24+x25+x26+x27+x28+x29=300; x31+x32+x33+x34+x35+x36+x37+x38+x39=500; x41+x42+x43+x44+x45+x46+x47+x48+x49=300; x51+x52+x53+x54+x55+x56+x57+x58+x59=360;x12+x22+x32+x42+x52=250;x13+x23+x33+x43+x53=130;x14+x24+x34+x44+x54=140;x15+x25+x35+x45+x55=150;x16+x26+x36+x46+x56=140;x17+x27+x37+x47+x57=160;x18+x28+x38+x48+x58=180;x19+x29+x39+x49+x59=200; x11+x12+x13+x14+x15+x16+x17+x18+x19=500; x21+x22+x23+x24+x25+x26+x27+x28+x29=500; x31+x32+x33+x34+x35+x36+x37+x38+x39=300; x41+x42+x43+x44+x45+x46+x47+x48+x49=300; x51+x52+x53+x54+x55+x56+x57+x58+x59=310;此运输问题的成本或收益为: 410940（3）对于运筹学在运输问题的研究，首先运筹学在寻求物流运输成本最低的运输组合中起着重要的作用，在企业拥有资源有限的情况下，比如运输工具有限。运输人员有限，运输时间的限制等，利用管理运筹学把现实中的抽象问题转化成具体的数学问题，再建立相应的数学模型并求解，使问题得到解决，因而使运输成本最小化。其次，我们在算法中引进这样的运算机制：将场地、销地、运输工具、运输数量等进行综合评估后得找到最优运输方案和运输路线及运量，运用管理运筹学表上作业法算法找出最优运输方案。第三，随着企业在运输过程中提出的目标不断增加，并且决定运输成本的因素也不断增加，问题会越来越复杂，如果不借助科学的方法，很难找到成本最低的最优组合。正是因为这样，运筹学在物流运输成本控制中的作用越来越重要。第6题(运输问题) (1)介绍表上作业法； (2)广东省水泥厂与所属城市之间的运费(空白表示两者之间的运输不予考虑)、城市的需求量以及有关的已知条件如表6所示。(a)求解该问题；(b)若乙厂到各城市的运费有所变化，再求该问题的解。表6A 水泥厂、城市供需数量表用户水泥厂123456需求量1梅县59.0120.062.072902汕头47.179.749.521.0369403潮州53.486.053.920904惠阳21.830.062.322.2131405深圳21.222.021.350.021.680806韶关30.312.630.3127807肇庆25.243.046.060.129.2156808佛山12.321.051.028.0164609江门21.237.051.128.0513010珠海21.237.549.029.0380011湛江47.112.647.521.01672012茂名59.612.560.033513海口50.250.850.225.01183014三亚54.370.054.740.0595015广州12.612.652.125.022655供应量62520176802087096503156036600表6B 水泥厂、城市供需数量表用户水泥厂甲乙丙丁午己需求量1梅县59.060.0120.062.072902汕头47.148.079.749.521.0369403潮州53.454.086.053.920904惠阳21.822.030.062.322.2131405深圳21.222.021.350.021.680806韶关30.312.630.3127807肇庆25.243.046.060.129.2156808佛山12.313.021.051.028.0164609江门21.222.037.051.128.0513010珠海21.222.137.549.029.0380011湛江47.148.012.647.521.01672012茂名59.660.012.560.033513海口50.250.850.850.225.01183014三亚54.355.070.054.740.0595015广州12.613.012.652.125.022655供应量62520176802087096503156036600 (3)结合本题，谈谈你对运输问题的认识。Hint: 若参数为5，5，5，5，5，5，则最优目标函数值为(a)4900885.5；(b)4896145.5。解：（1）表上作业法是求解运输问题的一种简便而有效的方法，求解过程在运输表上进行这是一种迭代求解法，迭代步骤为：1）按某种规则找出一个初始基可行解；2）对现行解作最优性判断，即求各非基变量检验数，判别是否达到最优解，若是最优解，则停止计算，若不是最优解，则进行下一步骤。在表上对初始方案进行改进，找出新的基可行解，再按第二步进行判别，直至找出最优解。（2）设min=59*x11+120*x41+62*x51+47.1*x21+79.7*x42+49.5*x52+21*x62+53.4*x13+86*x43+53.9*x53+21.8*x14+30*x34+62.3*x44+22.2*x54+21.2*x15+22*x25+21.3*x35+50*x45+21.6*x55+30.3*x16+12.6*x26+30.3*x56+25.2*x17+43*x27+46*x37+60.1*x47+29.2*x57+12.3*x18+21*x38+51*x48+28*x58+21.2*x19+37*x39+51.1*x49+28*x59+21.2*x110+37.5*x310+49*x410+29*x510+47.1*x111+12.6*x411+47.5*x511+21*x611+59.6*x112+12.5*x412+60*x512+50.2*x113+50.8*x413+50.*x513+25*x613+54.3*x114+70*x414+54.7*x514+40*x614+12.6*x115+12.6*x315+52.1*x416+25*x515;x11+x12+x13+x14+x15+x16+x17+x18+x19+x110+x111+x112+x113+x114+x115=62520;x25+x26+x27=17680;x34+x35+x37+x38+x39+x310+x315=20870;x41+x42+x43+x44+x45+x47+x48+x49+x410+x411+x412+x413+x414+x415=9650;x51+x52+x53+x54+x55+x56+x57+x58+x59+x510+x511+x512+x513+x514+x515=31560;x62+x611+x613+x614=7290;x12+x42+x52+x62=36940;x13+x43+x53=2090;x14+x34+x44+x54=13140;x15+x25+x35+x45+x55=8080;x16+x26+x56=12780;x17+x27+x37+x47+x57=15680;x18+x38+x48+x58=16460;x19+x39+x49+x59=5130;x110+x310+x410+x510=3800;x111+x411+x511+x611=16720;x112+x412+x512=335;x113+x413+x513+x613=11830;x114+x414+x514+x614=5950;x115+x315+x415+x515=22655;解得最优解为 2181747（b)min=59*x11+60*x12+120*x41+62*x51+47.1*x21+48*x22+79.7*x42+49.5*x52+21*x62+53.4*x13+54*x23+86*x43+53.9*x53+21.8*x14+22+x24+30*x34+62.3*x44+22.2*x54+21.2*x15+22*x25+21.3*x35+50*x45+21.6*x55+30.3*x16+12.6*x26+30.3*x56+25.2*x17+43*x27+46*x37+60.1*x47+29.2*x57+12.3*x18+13*x28+21*x38+51*x48+28*x58+21.2*x19+22*x29+37*x39+51.1*x49+28*x59+21.2*x110+22.1*x210+37.5*x310+49*x410+29*x510+47.1*x111+48*x211+12.6*x411+47.5*x511+21*x611+59.6*x112+60*x212+12.5*x412+60*x512+50.2*x113+50.8*x213+50.8*x413+50.2*x513+25*x613+54.3*x114+55*x214+70*x414+54.7*x514+40*x614+12.6*x115+13*x215+12.6*x315+52.1*x416+25*x515;x11+x12+x13+x14+x15+x16+x17+x18+x19+x110+x111+x112+x113+x114+x115=62520;x21+x22+x23+x24+x25+x26+x27+x28+x29+x210+x211+x212+x213+x214+x215=17680;x34+x35+x37+x38+x39+x310+x315=20870;x41+x42+x43+x44+x45+x47+x48+x49+x410+x411+x412+x413+x414+x415=9650;x51+x52+x53+x54+x55+x56+x57+x58+x59+x510+x511+x512+x513+x514+x515=31560;x62+x611+x613+x614=7290;x12+x22+x42+x52+x62=36940;x13+x23+x43+x53=2090;x14+x24+x34+x44+x54=13140;x15+x25+x25+x35+x45+x55=8080;x16+x26+x56=12780;x17+x27+x37+x47+x57=15680;x18+x28+x38+x48+x58=16460;x19+x29+x39+x49+x59=5130;x110+x210+x310+x410+x510=3800;x111+x211+x411+x511+x611=16720;x112+x212+x412+x512=335;x113+x213+x312+x413+x513+x613=11830;x114+x214+x414+x514+x614=5950;x115+x215+x315+x415+x515=22655;解得最优解为3057112（3） 对于运筹学在运输问题的研究，首先运筹学在寻求物流运