数学与计算科学学院
实 验 报 告
实验项目名称 运输问题求解
所属课程名称 运筹学B
实 验 类 型 综合
实 验 日 期 2014年10月25日
姓 名 张丽芬
学 号 0102
成 绩
一、实验概述：
【实验目的】
1. 运输问题求解的编程实现
2．掌握使用Matlab、Lingo的求解功能求解运输问题，并对结果进行分析。
【实验原理】
利用线性规划基本原理对问题建立数学模型，用沃格尔法分析和求解运输问题
【实验环境】
计算机，Matlab软件，lingo软件，运筹学软件
二、实验内容：
【实验方案】
通过对实际问题的具体分析，建立线性规划模型，再利用LINGO,MATLAB中的线性规划函数进行求解.
【实验过程】（实验步骤、记录、数据、分析）
已知某企业有甲、乙、丙三个分厂生产一种产品，其产量分别为7、9、7个单位，需运往A、B、C、D四个门市部，各门市部需要量分别为3、5、7、8个单位。已知单位运价如下表。 A B C D
甲 12 13 10 11
乙 10 12 14 10
丙 14 11 15 12
试确定运输计划使总运费最少。
由题设知，总产量为：7+9+7=23个单位，总销量为：3+5+7+8=23个单位，所以这是一个产销平衡的运输问题。
设：xij(i=1,2,3;j=1,2,34)代表代表从第i个产地运往第j个销地的数量，z为总运费。ai表示第i个产地的产量，bj表示第j个销地的销量，cij表示从第i个产地运往第j个销地的单位产品运输费用。
一．数学模型：
{ ∑xij4j=1=ai∑xij4i=1=bjxij≥0,i=1,2,3;j=1,2,34
龙源期刊网
运输问题出现退化解时0元添加的改进方法
作者：丁龙 付小连 吴珊 苏瑞超
来源：《价值工程》2014年第02期
摘要： 运输问题表上作业法确定初始基可行解时，可能出现退化解，此时应当在适当的位置添加一个0元。本文探讨了这种情况下，如何恰当选取0元添加的位置，以减少表上作业法调整的工作量，最后提出了0元添加的改进方法。
Abstract： When the table dispatching method of transportation problems determines initial
basic feasible solution， degenerate solution may appear， at this time， a "0" should be added in
appropriate position. This paper discussed how to properly select the addition position of the "0" in
this situation so as to reduce the workload of table dispatching method adjustment， and finally
proposes improvement methods for "0" addition.
关键词： 运输问题；退化解；闭回路；初始基可行解；最优解
Key words： transportation problems；degenerate solution；closed loop；initial basic feasible
solution；optimal solution
中图分类号：O223 文献标识码：A 文章编号：1006-4311（2014）02-0059-02
WinQSB求解运输问题
1.一般运输问题
运输问题的运算程序是 Network Modeling(网络模型)，选项为Network Flow
或Transportation Problem。
【例 1】用WinQSB 软件求解表1最小值的运输问题，其中 A2 不可达及 B2。
表 1 ：
解：
这是一个销大于产的问题，用软件求解不必化为平衡问题，A2 不可达及 B2，因此令 C22=M，操作步骤如下：
（1）启动程序。点击开始→程序→WinQSB→Network Modeling。
（2）建立新问题。在图 1 中分别选择：
Transportation Problem
Minimization
Spreadsheet
输入标题
产地数为3
销地数为4
图 1
（3）输入表1 的数据到表 2 中，并重命名产地和销地。
表 2
重命名产地和销地：
Step1： 产地的数量 销地的数量 目标函数
表格输入格式
图表输入格式 图 2
Step2：
图 3
（4）求解，点击菜单栏 Solve and Analyze，下拉菜单有四个选择求解方法：
Solve the Problem——只求出最优解；
Solve the Display Steps-Network——网络图求解并显示迭代步骤；
Solve the Display Steps-Tableau——表格求解并显示迭代步骤；
Select Initial Solution Method——选择求初始解方法。
求初始解有八种方法选择：
Row Minimum (RM)逐行最小元素法。
Modified Rpw Minimum (MRM)修正的逐行最小元素法。
Calurnn Minimum (CM)逐列最小元素法。
Modified Column Minimum (MCM)修正的逐列最小元素法。
Northwest Corner Method (NWC)西北角法。
-1- 图与网络模型及方法
§1 概论
图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷22nnHC的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。
图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当 然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。
图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。
