ЛАБОРАТОРНАЯ РАБОТА № 5
«Решение транспортных задач с помощью прикладного программного пакета MS Excel»
Цель работы: ознакомиться с понятием транспортной задачи, методами нахождения опорного плана (метод северо-западного угла, метод минимального элемента, метод Фогеля), освоить метод исследования опорного плана задачи на оптимальность (метод потенциалов).
Методы решения транспортной задачи
Транспортная задача линейного программирования формулируется следующим образом. Необходимо минимизировать транспортные расходы
при ограничениях
,
где 
- стоимость перевозки единицы продукции из пункта i в пункт j; 
– планируемая величина перевозок из пункта i в пункт j (план перевозок 
– матрица размерности 
); 
- потребности в продукте в пункте j; 
- запасы в пункте i.
Предполагается, что модель закрытого типа, то есть 
.
Если модель открытого типа 
, то ее всегда можно привести к закрытому типу введением фиктивного пункта производства или фиктивного пункта потребления:
· Если 
, то 
, тогда 
, причем 
.
· Если 
, то 
, 
и 
.
Транспортная задача представляет собой задачу линейного программирования и, естественно, ее можно решить с использованием метода последовательного улучшения плана или метода последовательного уточнения оценок. В этом случае основная трудность бывает связана с числом переменных задачи (m´n) и числом ограничений (m+n). Поэтому специальные алгоритмы оказываются более эффективными. К таким алгоритмам относятся метод потенциалов и венгерский метод.
Алгоритм метода потенциалов, его называют еще модифицированным распределительным алгоритмом, начинает работу с некоторого опорного плана транспортной задачи (допустимого плана перевозок). Для построения опорного плана обычно используется один из двух методов: метод северо-западного угла или метод минимального элемента.
Метод северо-западного угла
Он позволяет найти некоторый допустимый план перевозок
При построении плана должны учитывать, что сумма перевозок в столбце должна оказаться равной потребностям в данном пункте, а сумма перевозок в строке запасу в пункте, соответствующем данной строке.
Заполнение начинается с верхнего левого угла таблицы. Величина перевозки устанавливается равной минимальной из величин: величины остатка запасов в пункте i или величины еще неудовлетворенного спроса в пункте j.
· Если ресурс в данной строке исчерпан, то переходим к перевозке в следующей строке текущего столбца (на одну строку вниз).
· Если потребности для данного пункта (столбца) удовлетворены, то переходим к следующей перевозке текущей строки в следующем столбце.
Метод минимального элемента
В таблице отыскивается 
и в первую очередь заполняется соответствующая клетка: 
. Затем вычеркивается остаток соответствующей строки, если 
, или столбца, если 
, и корректируем остатки запасов и неудовлетворенного спроса. В оставшихся клетках таблицы снова отыскивается минимальная стоимость перевозки и заполняется соответствующая клетка и т.д.
Метод Фогеля
На каждом шаге методаФогеля для каждой i-й строки вычисляются штрафы 
как разность между двумя наименьшими тарифами строки. Таким же образом вычисляются штрафы 
для каждого j-го столбца. После чего выбирается максимальный штраф из всех штрафов строк и столбцов. В строке или столбце, соответствующем выбранному штрафу, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом 
.
Если существует несколько одинаковых по величине максимальных штрафов в матрице, то в соответствующих строках или столбцах выбирается одна не вычеркнутая клетка с минимальным тарифом 
.
Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т.е. суммой штрафов по i-й строке и j-му столбцу.
Определение 1. Набором называется произвольная совокупность перевозок транспортной таблицы.
Определение 2. Цепью называют такие наборы, когда каждая пара соседних клеток в цепи расположены либо в одном столбце, либо в одной строке.
Определение 3. Циклом называется цепь, крайние элементы которой находятся либо в одной строке, либо в одном столбце.
Метод потенциалов
Метод позволяет находить оптимальный план перевозок транспортной таблицы. В основе лежит следующая теорема.
Теорема. Для того, чтобы некоторый план 
транспортной задачи был оптимальным, необходимо и достаточно, чтобы ему соответствовала такая система m+n чисел 
, для которой выполняются условия:
, 
, 
, (1)
, 
. (2)
и 
называются потенциалами соответствующих пунктов отправления и пунктов назначения. Условия (1)-(2) называются условиями потенциальности.
План будем называть потенциальным, если для него существует система и , удовлетворяющая (1)-(2). Тогда теорем коротко формулируется следующим образом.
Теорема. Для оптимальности транспортной задачи необходимо и достаточно, чтобы он был оптимален.
Достаточность. Пусть план потенциален, так что существует система и , удовлетворяющая (1)-(2). Тогда для любого допустимого плана 
,
т.е. стоимость перевозок по любому плану 
не меньше стоимости перевозок по потенциальному плану . Следовательно, план оптимален.
Необходимость. Будем рассматривать транспортную задачу, как задачу линейного программирования с минимизацией линейной формы
при соответствующих ограничениях. Заполним симплексную таблицу и рассмотрим двойственную к ней задачу, что легко получить из таблицы. Прямую таблицу будем заполнять, повернув.
0=
– 
| … | 0=
–
| … | 0=
– 
| 0=
– 
| … | 0=
– 
| … | 0=
– 
| 
| |
| x11 y11 = | -1 | … | … | … | … | c11 | |||||
| … | … | … | … | … | … | … | … | … | … | … | … |
| x1n y1n = | -1 | … | … | … | … | c1n | |||||
| … | … | … | … | … | … | … | … | … | … | … | … |
| xi1 yi1 = | … | -1 | … | … | … | ci1 | |||||
| … | … | … | … | … | … | … | … | … | … | … | … |
| xijyij = | … | -1 | … | … | … | cij | |||||
| … | … | … | … | … | … | … | … | … | … | … | … |
| xinyin = | … | -1 | … | … | … | cin | |||||
| … | … | … | … | … | … | … | … | … | … | … | … |
| xm1 ym1 = | … | … | -1 | … | … | Cm1 | |||||
| … | … | … | … | … | … | … | … | … | … | … | … |
| xmnymn = | … | … | -1 | … | … | Cmn | |||||
| 1 w = | a1 | … | ai | … | an | b1 | … | bj | … | bn |
Получаем, что двойственная задача имеет вид:
при ограничениях
, , ,
т.е. , , .
Пусть – оптимальное решение транспортной задачи. Тогда на основании теоремы двойственности двойственная задача имеет оптимальное решение
.
Убедимся, что эти числа являются потенциалами соответствующих пунктов транспортной задачи. Действительно, все 
как опорное решение двойственной задачи удовлетворяют неравенствам (1).
Если 
, то по второй теореме двойственности соответствующее ограничение
двойственной задачи обращается в строгое равенство
.