运筹学运输问题

1

运筹学

2 第一章 绪论

第二章 线性规划

如何建立线性规划的数学模型；

线性规划的标准形有哪些要求？如何把一般的线性规划化为标准形式？

如何用图解法求解两个变量的线性规划问题？线性规划问题的解有哪些性质？

如何用单纯形方法、两阶段算法 求解线性规划问题？

如何写出一个线性规划问题的对偶问题？如果已知原问题的最优解如何求解对偶问题的最优解？（对偶的性质，互补松紧条件）

对偶单纯形方法适合解决什么样的问题？如何求解？

对于已经求解的一个线性规划问题如果改变价值向量和右端向量原最优解/基是否仍是最优解/基？如果不是，如何进一步求解？

3 1、建立线性规划的数学模型：

特点：

（1）每个行动方案可用一组变量（x1，…，xn）的值表示，这些变量一般取非负值；

（2）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示；

（3）有一个需要优化的目标，它也是变量的线性函数。

2、线性规划的标准形有哪些限制？如何把一般的线性规划化为标准形式？

目标求极小；约束为等式；变量为非负。

min

b 0TzCXAXX

例：把下列线性规划化为标准形式：

121212112max 2328 1 20,0zxxxxxxxxx

3、如何用图解法求解两个变量的线性规划问题？由图解法总结出线性规划问题的解有哪些性质？

例：参看ppt（唯一最优解、无穷多最优解、无界解、无解）

线性规划解的性质：（基、基本解、基本可行解、凸集、顶点）

定理1 线性规划的可行域是凸集。 4 定理2 X是线性规划基可行解的充分必要条件是X是可行域的顶点。

定理3 线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。

4、如何用单纯形方法求解线性规划问题？（单纯形表）

运筹学在运输问题中的应用

关键字：运筹学 运输

引言：运输是土木工程中经常遇到的问题，在工程造价中占较大的比例。如何使运输费用达到最小化，这就需要在施工前优化施工组织设计，将运筹学、网络技术等理论的设计方法应用到施工中，使得成本费用最经济。下面我们借鉴运筹学中的理论来解决运输问题。

一、运输路线最短问题。

根据运筹学中最短路径算法，寻找最短路线，就是从最后一段开始，用由后向前逐步递推的方法求卅各点到终点的最短路线，最终求得南起点到终点的最短路线。

某工程需要从点Sl运送500吨的建筑材料一个工地S1O。

首先．将图l的路线问题看成四个阶段的问题．南S1到S2，S3，S4为第一阶段；南S2，S3，S4到S5，S6，S7为第二阶段；南S5，S6，S7到S8。S9为第i阶段；南S8，S9到SIO为第四阶段。下面引进几个符号： D(Sk,Sm)为Sk到Sm的距离，f(Sk)Sk到终点的最短距离。

(1)在第四阶段。

目前状态可以是S8或S9，可选择的下一状态是S1O，所以有

(2)在第i阶段。

目前状态可以是S5或S6或S7，可以选择的下一状态为S8或S9．所以有

(3)在第二阶段。

目前状态可以是S2或S3或S4，可以选择的下一状态为S5或S6或S7，所以有

(4)在第一阶段。

目前状态只有S1，可以选择的下一状态为S2或S3或S4．所以有

通过最短路径算法计算。可知从Sl(出发点)到S1O(终点)的最短运输路程为1080千米(权数路径距离)，所走的最优路线采用“顺序追踪法”来确定，最优运输路径：S1一S3一S6—S8—S10。

二、自卸车排队问题 在工程中经常遇到材料的运输和施工之间的关系，例如铺路的碎石、沥青的运输和路面的铺设之间的关系。如果运输工作进行得太快，而施工进程跟不上，就会有太多的原料来不及施工，导致运输设备和人员的闲置。相反，如果运输进度赶不上施工，就会出现施工设备和人员的闲置。

下面以高速公路高速公路沥青路面机械化施工系统为例子进行说明。高速公路沥青路面机械化施工系统，是指以沥青混合料拌和站、自卸汽车、沥青混凝土摊铺机、初压压路机、复压压路机、终压压路机等6种主体机械组成的沥青路面铺筑机群施工系统。沥青混凝土混合料作为纽带，将这6种机械共同联系在一起。准确、协调地工作，形成在“拌和一运料一摊铺一初压一复压一终压”过程中机械间的“相互影响、相互联系、相互制约”规律，即沥青路面施工系统机群工作规律。”

实验报告

课程名称：___ 运筹学 ____ 项目名称：_运输问题

姓名：__专业：_ 班级：班 学号： 同组成员：_ __

一、

实验准备1：

在社会、经济和军事等领域中，经常会遇到大宗物资的调运问题，如煤、

钢铁、木材、粮食、军事装备等，如果有若干个生产或储存地，则根据已有的

交通网，应如何制定调运方案？将这些物资运到消费（或使用）地，使总的运输

费用最少，或运输路线最短？这类问题的数学模型就是运输规划模型，事实上

运输规划是一类特殊的线性规划。

运输规划分为，产销平衡和产销不平衡两个问题。当产销不平衡时，我们

可以通过增加销售地或者增加产地从而使得该类问题转化为产销平衡问题。本

次实验主要研究运输问题中的产销平衡和产销不平衡的求解。

1、 掌握线性规划问题求解原理；

产销平衡模型：

产销不平衡模型：

产大于销

1 注：1、实验准备部分包括实验环境准备和实验所需知识点准备。

2、若是单人单组实验，同组成员填无。 0,,2,1,,2,1..min1111ijmijijnjiijminjijijxnjbxmiaxtsxcz

销大于产

2、产销平衡问题的运输问题模型给出一般的LINGO模型如下：

model:

sets:

row/1…m/:a;

arrange/1…n/:b;

link(row,arrange):c,x;

endsets

data:

a=a(1),a(2),…,a(m);

b=b(1),b(2),…b(n);

c=c(1,1),c(1,2),…,c(1,n),

c(2,1)c(2,2),…c(2,n), 0),,2,1(,),,2,1(,min1111ijmijijnjiijminjijijxnjbxmiaxxcz0),,2,1(,),,2,1(,min1111ijmijijnjiijminjijijxnjbxmiaxxcz …

第 1 页 共 6 页 一、 实验目的及要求

熟悉运用WinQSB软件求解运输问题，掌握操作方法。

二、 实验环境及相关情况（包含使用软件、实验设备、主要仪器及材料等）

装有WinQSB软件的个人电脑

三、 实验内容及步骤（包含简要的实验步骤流程）

实验内容：

DF公司在接下来的三个月内每月都要按照销售合同生产出两种产品。这两种产品使用相同的设备并需要投入相同的生产能力。每个月可供使用的生产和存储设备都会发生变化，所以生产能力、单位生产成本以及单位存储成本每个月都不相同，有必要在某些月中多生产一种或者多种新产品并在存储起来以备需要的时候使用。表5-24中给出了在正常时间（Regular Time，缩写为RT）和加班时间（Over Time，缩写为OT）内能够生产这两种产品的总数。

月 最大生产总量 产品1/产品2

销售

产品1/产品2 单位生产成本(1000元/件) 单位储存成本（1000元/件）

RT OT RT OT

1

2

3 10

8

10 3

2

3 5/3

3/5

4/4 15/16

17/15

19/17 18/20

20/18

22/22 1/2

2/1

生产管理人员想要开发一个在正常时间内生产每一种新产品数量的计划进度，目标是在满足合同规定的基础上，3个月的总生产和存储成本最小。开始和在3个月结束后的存储都为零。

（1）对这个问题进行分析，描述成一个运输问题的产销平衡表，使之可用运输单纯形法求解．

（2）建立总成本最小的数学模型；

第 2 页 共 6 页 （3）输入数据，将产地和销地更名为下表所示的名称；

（4）求解并打印最优生产方案；

（5）显示并打印生产方案网络图。

1月(1) 1月(2) 2月(1) 2月(2) 3月(1) 3月(2) 生产能力

1月RT 15 16 16 18 18 19 10

1月OT

8 20 19 22 21 23 3

2月RT 17 15 19 16 8