Системный анализ и управление грузопотоками по экономическому критерию путем решения транспортной задачи линейного программирования

Транспортная задача линейного программирования формулируется следующим образом. Имеется m пунктов отправления А₁, А₂,.... А_m в которых находятся запасы какого-то однородного груза в количестве соответственно а₁, а₂,..... а_m единиц. Кроме того, имеется n пунктов назначения В₁, В₂,...... В_n, подавших заявки соответственно на b₁, b₂,.... b_n единиц груза. Предполагается, что сумма всех заявок равна сумме всех запасов, т.е.

. (8.1)

Известна стоимость с_{i j} перевозка единицы товара от каждого пункта отправления А_i до каждого пункта назначения В _j. Матрица стоимостей С имеет вид:

(8.2)

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

Таким образом, в качестве критерия выбрана стоимость перевозки груза.

Критериями в транспортной задаче могут быть следующие показатели: расстояние, время, мощность и др.

Транспортная задача, в которой выполняется условие (8.1), называется закрытой. Задача, в которой это условие не выполняется, называется открытой. В данной теме рассматривается закрытая транспортная задача.

Математическая формулировка транспортной задачи может быть представлена в следующем виде: пусть x_{i j} ¾ количество груза, отправляемого из i-го пункта отправления А_i в j-й пункт назначения В_j(), x_{i j} ³0.

Переменные x_ij должны удовлетворять неравенствам

 

. (8.9)

Любую совокупность значений x_ij () называют планом перевозок. План, удовлетворяющий условиям (8.3) ¾ (8.9), называют допустимым. Так как ранг системы (8.3) ¾ (8.8) r = m + n -1, то ней (m + n -1) базисных и (m-1)(n-1) свободный переменных. Поэтому план, в котором отлично от нуля не более m + n -1 переменных, а остальные равны нулю, называют опорным.

Оптимальный план ¾ это такой план, который среди всех допустимых имеет наименьшую стоимость перевозок.

Отыскание оптимального плана выполняется с помощью транспортной табл.8.1.

 

Таблица 8.1.

 

Стоимость перевозок с_ij помещают в правом верхнем углу клеток таблицы.

Клетки таблицы, в которых будем записывать отличные от нуля перевозки x_ij, называются базисными. Таких клеток не более чем m+n-1. Пустые клетки называются свободными, их не менее (m-1)(n-1). Все дальнейшие действия по нахождению решения транспортной задачи будут сводится к преобразованию транспортной табл.8.1, т.е. к двум этапам:

а) отыскание первого решения методом «северо-западного угла»;

б) нахождение оптимального решения потенциалов.

Продемонстрируем применение этого метода на примере транспортной табл.8.2.

Таблица 8.2

Пункты		Пункты назначения				Запа-
отправления	В1		В2		В3		В4		В5		сы
A1
A2
A3
A4
Заявки

Начнем заполнения транспортной таблицы с левого верхнего («северо-западного») угла. Пункт В₁ подал заявку на 18 единиц груза. Удовлетворим её из запасов А ₁. После этого в нем ещё останется 30 -18 = 12 единиц груза. Отдадим их пункту В₂. Но заявка этого пункта еще не удовлетворена. Выделим недостающие 15 единиц из запасов пункта А ₁₂ и т.д. применяя такую методику, заполним до конца перевозками x _ij транспортную табл.8.3.

Таблица 8.3

Пункты		Пункты назначения				Запа-
отправления	В1		В2		В3		В4		В5		сы
A1
A2
A3
A4
Заявки

В полученном опорном решении базисных клеток r = n + m -1 = 5 + 4 - 1 = 8, свободных клеток (m - 1)(n - 1) = 3 × 4 = 12.

Опорный план, получаемый в результате применения метода «северо-западного угла», как правило, не оптимальный. Поэтому для отыскания оптимального решения применяется метод потенциалов.

После того как с помощью метода «северо-западного угла» найден первый опорный план, выполним его улучшение с помощью метода потенциалов. Алгоритм метода показан на рис.8.1.

Улучшение плана перевозок в этом методе выполняется с помощью перемещения перевозок из клетки в клетку в транспортной таблице без нарушения баланса заявок и запасов. Перемещение грузов в таблице выполняется по замкнутому циклу.

 

6. Выполнить перенос грузов по циклу

5.Построить цикл для не заполненной клетки, в которой с¢ ij³ с ij

 

 

 

 

Рисунок 8.1.Схема алгоритма метода потенциалов.

 

Циклом в транспортной таблице называются несколько клеток, соединенных замкнутой ломаной линией, которая совершает поворот на 90° в отдельных клетках. Цикл стоят так, чтобы одна его вершина была в свободной клетке, остальные вершины в базисных (заполненных) клетках.

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

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

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

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

Изменение стоимости перевозок при перемещении одной единиц груза по циклу называют ценой цикла. Определяется цена цикла как алгебраическая сумма стоимостей, стоящих в вершинах цикла, причем, стоимости, стоящие в положительных вершинах, берутся со знаком «+», а в отрицательных ¾ со знаком «-». Для улучшения плана перевозок целесообразно перемещать перевозки только по тем циклам, цена которых отрицательна.

Метод потенциалов позволяет автоматически выделять циклы с отрицательной ценой и определить их цены. Для этого поставим в соответствие каждому пункту отправления (столбцу) А_i число a _i, а каждому пункту назначения (строке) В_j ¾ число b _j. Эти числа называются потенциалами. Определим значения a _i и b _j. Для этого составим для базисных клеток m + n - 1 уравнений c m + n неизвестными, т.е.

(8.10)

Система (8.10) имеет бесконечное число решений. Поэтому для нахождения одного из них примем a ₁ = 0. Решая m + n - 1 уравнений (8.10) методом подстановок, находим остальные потенциалы

Затем для незаполненных клеток вычисляют псевдостоимоти по формуле

.

Для каждой незаполненной клетки цена цикла пересчета равна разности между стоимостью с _ij и псевдостоимостью с¢ _ij.

Следующим шагом алгоритма является проверка опорного решения на оптимальность (рис.8.1).

Если для базисных клеток плана (x _ij >0)

,

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

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

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

Решим задачу, сформулированную в табл.8.2. В результате применения метода «северо-западного угла» полученное первое опорное решение, которое занесено в табл.9.4 для дальнейших расчетов.

Таблица 8.4.

Пункты

Пункты назначения

Запа-

Отправления

В1

В2

В3

В4

В5

сы

a1=0

A1

a2=1

A2

a3=-1

A3

a4=1

A4

Заявки

b ₁ =13; b ₂ = 7; b ₃ = 11; b ₄ = 9; b ₅ = 14.

Значений целевой функции будет .

Определим потенциалы из уравнений:

Приняв a ₁ = 0. Найдем a ₂ = 1, a ₃ = -1, a ₄ = 1, b ₁ =13; b ₂ = 7; b ₃ = 11; b ₄ = 9; b ₅ = 14.

Подсчитаем для незаполненных клеток псевдостоимости по формуле

.

Результаты запишем в табл.8.4. Псевдостоимости будем заносить в левый верхний угол незаполненных клеток.

Анализируя табл.8.4 приходим к выводу, что опорное решение не оптимально и может быть улучшено. Наименьшая отрицательная цена

Поэтому построим на клетке (1, 5) цикл (табл.8.4). Выполним перемещение грузов по циклу, результаты поместим в табл.8.5. Дальнейшие расчеты выполнены в

табл.8.6. ¾ 8.10.

Таблица 8.5

Пункты

Пункты назначения

Запа-

отправления

В1

В2

В3

В4

В5

сы

A1

a 1 = 0

A2

a 2 = 1

-1

A3

a 3 = -1

A4

a 4 = 10

Заявки

 

b ₁ =13; b ₂ = 7; b ₃ = 11; b ₄ = 9; b ₅ = 14.

Z = 1343

Таблица 8.6.

Пункты

Пункты назначения

Запа-

отправления

В1

В2

В3

В4

В5

сы

-4

A1

a 1 = 0

A2

a 2= 12

A3

a 3 =10

A4

a 4 = 10

Заявки

b ₁ =13; b ₂ = -4; b ₃ = 0; b ₄ = 0; b ₅ = 5.

Z = 1332

 

 

Таблица 8.7.

Пункты

Пункты назначения

Запа-

отправления

В1

В2

В3

В4

В5

сы

A1

-

+

a 1 = 0

A2

a 2 = -5

-2

A3

+

a 3 = -7

-

-

-2

A4

+

a 4 = -7

Заявки

b ₁ =13; b ₂ =13; b ₃ =17; b ₄ = 17; b ₅ = 5.

Z = 1094

 

Таблица 8.8.

Пункты

Пункты назначения

Запа-

отправления

В1

В2

В3

В4

В5

сы

A1

a 1 = 0

A2

-

+

a 2 = 5

A3

a 3 =3

A4

+

-

a 4 = 3

Заявки

 

b ₁ =3; b ₂ =3; b ₃ =7; b ₄ = 7; b ₅ = 5.

Z = 1054.

Таблица 8.9.

Пункты

Пункты назначения

Запа-

отправления

В1

В2

В3

В4

В5

сы

A1

+

a 1 = 0

-

Y

A2

a 2 = -1

-

+

A3

a 3 = -3

A4

a 4 = -3

Заявки

b ₁ =9; b ₂ =9; b ₃ =13; b ₄ = 7; b ₅ = 5.

Z = 988.

Таблица 8.10.

Пункты

Пункты назначения

Запа-

отправления

В1

В2

В3

В4

В5

сы

A1

a 1 = 0

A2

a 2 = 1

A3

a 3 = -1

A4

a 4 = -1

Заявки

b ₁ =7; b ₂ =7; b ₃ =11; b ₄ = 5; b ₅ = 5.

Z = 980.