运筹学论文

湖北师范大学数学与统计学院运筹学论文1管理运筹学论文---产销不平衡运输摘要运输问题是运筹学中的一个重要问题，也是物流系统优化中常见的问题，同时也是一种特殊的线性规划问题。怎么样尽可能的在产地与销地之间减少运输成本和降低运输费用是很多运输公司热切关注的话题。本文涉及的是一个总产量大于总销量的产销不平衡运输问题，通过对产地与销售地车辆运输的建立模型，在运用表上作业迭代法（最小元素法）求解后，再根据模型用lingo软件编写程序进行求解。然后对结果进行分析，以及运输问题的延伸。最后证明用lingo解决车辆运输的可行性。关键字：运输问题，产销不平衡，表上作业法，lingo湖北师范大学数学与统计学院运筹学论文2目录一、问题的提出与分析.....................................................错误!未定义书签。1.1问题提出..........................................................................................................31.2问题分析..........................................................................................................3二、模型的建立与基本假设............................................................................12.1模型的建立......................................................................................................42.2基本假设..........................................................................错误!未定义书签。三、定义符号说明与表上作业法.......................................................................6四、问题求解........................................................................错误!未定义书签。4.1、Lingo求解模型............................................................错误!未定义书签。4.2、Lingo结果....................................................................................................9五、模型结果分析与改进.................................................................................10参考文献................................................................................错误!未定义书签。湖北师范大学数学与统计学院运筹学论文3一、问题的提出与分析1.1问题提出重庆有三家电子厂分别是新普，隆宇和恒华，生产的笔记本电脑将要运向北京，天津，广东，上海四个城市销售，其产量和销售量见下表：（单位：万台）表：1-1北京天津广东上海产量新普626730隆宇495325恒华881521销量15172212-问：哪种销售方案将会取得最少的运输费用，费用为多少？1.2问题分析图表数据显示产量总和为30+25+21=76万台，销量的总和为15+17+22+12=66万台，说明了此问题是一个总产量大于总销量的运输问题（7666）。该问题一方面要求满足北京，天津，广东，上海四个销售地的供货需求，而另一方面又要考虑新普，隆宇和恒华三个产地的运往销售地的运输费用，此外问题不但要求满足销售地分配要足，同时也要保证最大化的减少运输费用。这里选择何种分配方案，将涉及不同的运输费用，所以其是一个典型的线性规划问题，同时也是一个总产量大于总销量的产销不平衡运输问题。根据题目已知可以得出以下图论：新普隆宇恒华北京天津广东上海湖北师范大学数学与统计学院运筹学论文4二、模型的建立与基本假设2.1模型的建立假设某物品有m个产地A1、A2、…、Am，各产地的产量是a1、a2、…、am；有n个销地B1、B2、…、Bn，各销售地销量分别为b1、b2、…、bn；假定从产地Ai（i=1,2，…，m）向销售地Bj（j=1，2，…，n）运价单位物品的运价是cij，问这样调运这些物品才能使运费最少？设xij为从产地Ai运往销地Bj的运输量，若各产地产量之和大于各销地销量之和，即有：njjmiiba11则得到下列产销平衡运输量问题的模型：0,...,2,1,,...,2,1,min11111ijjmiijinjijminjijijxnjbxmiaxxcz其中，约束条件右侧常数ai和bj，约束条件最多有m+n-1个有效，即最多有m+n-1个基可行解。为了能使用表上作业法，可增加一个假想的销地虚销地Bn+1而由产地Ai（i=1,2，…，m）调运到这个假想销地的物品数量的销量Xi，n+1（相当于松弛变量），实际上就地储存在Ai。因为就地储存没有运输，故单价为Ci，n+1=0，（i=1,2，…，m）令假想销地的销量为：湖北师范大学数学与统计学院运筹学论文5njjmiinbab111从而数学模型：0,...,2,1,,...,2,1,min11111ijjmiijinjijminjijijxnjbxmiaxxcz2.2模型的基本假设针对该运输问题，为了方便计算，可以设新普（A1），隆宇（A2）和恒华（A3）分别销往北京（B1）、天津（B2）、广东（B3）和上海（B4）四个城市销售量为x11、x12、x13、x14、x21、x22、x23、x24、x31、x32、x33、x34。建立以下模型：表：1-2B1B2B3B4产量A1626730A2495325A3881521销量15172212-目标（Theobjective）最少费用：湖北师范大学数学与统计学院运筹学论文634333231242322312114131211415xx8x8x3x5x9x4x7x6x2x6xzMinijjijixc约束条件：供应限制（Thesupplyconstrains）21xxxx25xxxx30xxxx343332312423222114131211指标约束（Thedamandconstrains）12xxx22xxx17xxx15xxx342414332312322212312111三、模型的定义符号说明与表上作业法定义符号说明：A1、A2、A3分别代表新普，隆宇和恒华生产商；B1、B2、B3、B4分别代表北京，天津，广东，上海销售地。x11、x12、x13、x14、x21、x22、x23、x24、x31、x32、x33、x34为新普、隆宇和恒华分别销往北京、天津、广东和上海四个城市销售量。Cij为从产地Ai（i=1,2，…，m）向销售地Bj（j=1，2，…，n）运价单位物品的运价，xij为从产地Ai（i=1,2，…，m）运往销地Bj（j=1，2，…，n）的运输量。Z即为整个运输过程中涉及的运输费用。Minz则为该运输问题中的最小费用。表上作业法（最小元素法）：最小元素法：是找出运价表中最小的元素，然后在运量表内对应的格填入允许取得的最大数值，若某行或者某列的产量或者销量已得到满足，则把运价表中该运价所在行或者列划去；找出未划去的运价中的最小湖北师范大学数学与统计学院运筹学论文7数值，按此办法依次进行下去，直至得到一个基本可行解的方法。表上作业法：是求解运输问题的一种简便而有效的方法，求解过程在运输表上进行行，这是一种迭代求解法，迭代步骤为：步骤一：按某种规则找出一个初始基可行解。步骤二：对进行解作最有判断，即求个非基变量的检验数，判别是否达到最优解。如果已经是最优解，则停止计算；如果不是最优解，则进行下一步骤。步骤三：在表上对初始方案进行改进，找出新的基可行解，再按照步骤二进行判别，直至找出最优解。表上作业法具体求解如下：表：1-3：步骤一：从表1-2中找出最小运价为1，故首先考虑此项，由于A3产地产量小于B3销量（2122），故在表1-3的（A3，B3）交叉格填上21，由于A3产地产量已经饱和，故划去表1-3中的A3行得表1-4。表：1-4B1B2B3B4A16267A24953步骤二：从表1-4中找出最小运价为2，故首先考虑此项，由于A1产地产量大于B2销量（3017），故在表1-3的（A1，B2）交叉格填上17，由于B2销量已经饱和，故划去表1-4中的B2列得表1-5。表：1-5B1B3B4-12221715销量21501218080A3253125090413A217230706126A1产量B4B3B2B1湖北师范大学数学与统计学院运筹学论文8A1667A2453步骤三：从表1-5中找出最小运价为3，故首先考虑此项，由于A2产地产量大于B4销量（2512），故在表1-3的（A2，B4）交叉格填上12，由于B4销量已经饱和，故划去表1-5中的B2列得表1-6。表：1-6B1B3A166A245步骤四：从表1-6中找出最小运价为4，故首先考虑此项，由于A2产地剩余产量小于B1销量（25-12=1315），故在表1-3的（A2，B1）交叉格填上12，由于A2产地产量已经饱和，故划去表1-6中的A2行得表1-7。表：1-7B1B3A166步骤五：从表1-7中找出最小运价都是6，故随机选择一项优先考虑此处选择（A1，B1），由于A1产地剩余产量大于B1剩余销量（30-17=1315-13=2），故在表1-3的（A1，B1）交叉格填上2，由于B1销量已经饱和，故划去表1-5中的B2列。步骤六：由于B3销地为达到饱和，故在（A1，B3）交叉格填上1，然后在其它空格位置统一填上0。经以上步骤得到一个总产量大于总销量，且销量全部满足的调配方案。经过计算，空格的检验数均大于零，最优方案为：0x2112131172ij332412131211，其它，，，，，xxxxxx最小费用为：湖北师范大学数学与统计学院运筹学论文931411611213124136121762ijjijixcz四、问题求解4.1、lingo求解模型：LINGO模型：model:sets:origin/1..3/:a;sale/1..4/:b;routes(origin,sale):c,x;endsetsdata:a=30,25,21;b=15,17,22,12;c=6,2,6,7,4,9,5,3,8,8,1,5;enddata[OBJ]min=@sum(routes:c*x);@for(origin(i):[SUP]@sum(sale(j):x(i,j))=a(i));@for(sale(j):[DEM]@sum(origin(i):x(i,j))=b(j));end4.2、lingo结果：Globaloptimalsolutionfound.Objectivevalue:161.0000Infeasibilities:0.000000Totalsolveriterations:6湖北师