2.3 Транспортные задачи

Классическая транспортная задача ЛП формулируется следующим образом.Имеется  m  пунктов производства (поставщиков) и n  пунктовпотребления (потребителей) однородного продукта. Заданы величины:

  - объем производства (запас) i-го поставщика,  i=1, m  ;

  - объем потребления   (спрос) j-го потребителя, i=1, n ;

   - стоимость перевозки (транспортные затраты) единицы продукта от i-го поставщика к  j-му потребителю.

Требуется составить такой план перевозок, при котором спросвсех потребителей был бы выполнен и при этом общая стоимость всехперевозок была бы минимальна.

В случае, когда суммарные потребности превышают суммарныезапасы,  т.е., вводится фиктивный m+1 поставщик, запасы которого, стоимость перевозки единицы груза как до фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщикаполагают равными нулю, так как груз в обоих случаях не перевозится.

Прежде чем решать транспортную задачу, необходимо проверить, к какой модели она принадлежит, и если необходимо, то привести ее кзакрытой модели.Основные свойство транспортной задачиМатематические модели любых транспортных задач ЛП обладают

1) коэффициенты  целевой функции неотрицательны (стоимости перевозок не могут быть отрицательными величинами);

2) коэффициенты правых частей ограничений неотрицательны (запасы и потребности продукта);

3) коэффициенты в ограничениях принимают только два значения, это нули и единицы.

В силу этих особенностей транспортная задача обладает следующими свойствами.

Теорема 1.

Базисное решение закрытой модели транспортной задачи содержит m+n-1 базисных компонент.

Доказательство.

Количество базисных компонент определяется число линейно-независимых ограничений задачи. В транспортной задаче не все m+n ограничений линейно-независимы.

Действительно, сложив первые m ограничений и  следующие n ограничений задачи, получим : , но в закрытой модели выполняется балансовое равенство ,поэтому получаем, что нетривиальная линейная комбинация строк ограничений (линейная комбинация с ненулевыми коэффициентами) равна нулю. Это означает, что среди ограничений задачи есть линейно-зависимое ограничение. Следовательно, число линейно-независимых ограничений равно  m+n-1 и базис задачи состоит из m+n-1 компонент.

Теорема доказана

В силу специфики содержательной постановки транспортной задачи допустимое решение называетсяпланом, базисное допустимое решение называется опорным планом, оптимальное решение называетсяоптимальным планом.

2.4 Метод потенциалов

Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке совершает поворот на 90 , Знаком " + " отмечают те вершины, в которых перевозки увеличиваются, а знаком "- " - те вершины, в которых перевозки уменьшаются. Перемещение какого-то количества единиц груза по циклу означает увеличение перевозок на это количество единиц в положительных вершинах и уменьшение перевозок на это же количество единиц в отрицательных вершинах. При этом, если перевозки остаются неотрицательными, план остается допустимым. Стоимость плана при этом может меняться.

Ценой цикла называется увеличение стоимости перевозок при перемещении единицы груза по этому циклу. Очевидно, цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, при этом стоимости в положительных вершинах берутся со знаком " +", а стоимости в отрицательных вершинах берутся со знаком " - ".

Идея метода потенциалов состоит в следующем. Для любой свободной клетки транспортной таблицы всегда существует единственный цикл, положительная вершина которого лежит в этой свободной клетке, а все остальные - в базисных. Если цена такого цикла отрицательна, то план можно улучшить перемещением перевозок по данному циклу. Количество единиц груза, которое можно переместить, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла (если переместить большее число единиц груза, возникнут отрицательные перевозки). Если циклов с отрицательной ценой нет, то это означает, что дальнейшее улучшение плана невозможно, т.е. оптимальный план найден.

Для нахождения циклов с отрицательной ценой вводится система платежейназываемые "псевдо стоимостями" перевозок единицы груза из пункта iв пункт j.  При этом цена цикла пересчета для каждой свободной клетки равна для всех базисных клеток (i, j)

Вычислительная схема метода потенциалов  

Шаг 1. Строим опорный план (методом северо-западного угла) сn+m-1   базисными клетками.

Шаг 2. Определяем платежи для всех базисных клеток. Один из платежей (например 1 ) полагаем равньм нулю.

Шаг 3. Считаем псевдо стоимостидля всех свободных клеток. Еслидля всех клеток, то план оптимален. Вычисляем значение целевой функции L на этом плане и исследования прекращаем.

Шаг 4. Если есть свободная клетка, для которойто улучшаем план, перебрасывая перевозки по циклу этой свободной клетки.

Шаг 5. Возвращаемся к шагу 2 для пересчета платежей нового опорного плана.