Транспортная задача (ТЗ) с закрытой моделью

Простейшая формулировка ТЗ

Пусть в пунктах (поставщиках) сосредоточен однородный груз (сено, картофель и т.д.) в количествах соответственно , который необходимо перевезти потребителям в количествах . Известны транспортные расходы (тарифы) , по перевозке единицы груза от поставщика к потребителю . Требуется составить план перевозки груза, по которому:

1) груз от каждого поставщика должен быть вывезен;

2) спрос каждого потребителя полностью удовлетворен;

3) затраты на перевозку должны быть минимальными.

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

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

Поставщик	Потребители	Запас груза
	……………
		……………
……………	……………	……………	……………	……………
		……………
Потребность в грузе		……………

В клетках этой же распределительной таблицы можно составить план перевозок груза из пункта в пункт . При этом расходы на перевозку груза составят:

(1)

Таким образом, математическая формулировка ТЗ следующая: Найти , если переменные удовлетворяют условиям:

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

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

Таким образом, план решения ТЗ может быть определен следующими этапами:

1. Построение опорного плана решения ТЗ (в распределительной таблице заполняются не более клеток).

2. Проверка опорного плана на оптимальность.

3. Улучшение опорного плана, если он не оптимальный.

4. Проверка улучшенного плана на оптимальность. Процесс заканчивается оптимальным планом.

Рассмотрим каждый этап решения ТЗ.

1. Построение опорного плана решения ТЗ.

Рассмотрим два метода построения опорного плана.

а) Метод «Северо-западного угла»

Суть этого метода состоит в том, что заполнение распределительной таблицы ТЗ начинается с левого верхнего угла (клетка 1;1). В ней записывается максимально возможный груз: . Например, если , то и весь груз из пункта вывезен в пункт , но в надо завозить еще единицу груза. Этот недостающий груз завозим из пункта , записывая в клетку (2;1) максимально возможный груз . Заполнив клетку (2;1), заполняем следующую, либо в той же строке 2 (если ), либо в строке 3 (если ). Последней заполняется клетка . При этом число заполненных клеток будет не более .Пример построения опорного плана методом «Северо-западного угла» приведен для следующей задачи.

Задача №1.

Фирма, выпускающая газированные напитки, складируемые в трех разных местах, должна поставить продукцию в четыре супермаркета. Каждая упаковка содержит 20 бутылок по 1,5 литра, тарифы на доставку товара, объемы запасов и заказы на продукцию приведены в Таблице 2.

Таблица 2

Поставщики	Потребители	Запасы груза
Потребность в грузе

Затраты на перевозку 300 ед. груза по этому плану составляют:

(у.е.)

б) Метод «Минимального элемента»

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

Пример построения опорного плана методом «Минимального элемента» приведен в Таблице 3.

Таблица 3

Поставщики	Потребители	Запасы груза
Потребность в грузе

Здесь порядок заполнения клеток следующий:

.

Затраты по этому маршруту перевозок составят: (у.е.). Мы видим, что по этому плану затраты на перевозку груза значительно меньше . И в таблице 2 и в таблице 3 заполненных клеток оказалось 3+4-1=6.

2. Проверка опорного плана на оптимальность.

Будем проверять опорный план на оптимальность методом потенциалов. Суть его состоит в том, что каждой строке и столбцу распределительной таблицы приписываются некоторые числа называемые потенциалами. Таким образом, числа - потенциалы строк, - потенциалы столбцов. Эти числа рассчитываются по формуле: для каждой заполненной клетки распределительной таблицы сумма потенциалов строки и столбца равна тарифу соответствующей заполненной клетки, то есть

. (3)

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

Вычислив, таким образом, потенциалы строк и столбцов, вычисляем характеристики свободных клеток распределительной таблицы по формуле: . Отрицательные характеристики каких-то свободных клеток указывают на их перспективность: в этих клетках тарифы малы и их заполнение приведет к улучшению плана перевозок. Итак, если хотя бы одна свободная клетка будет иметь отрицательную характеристику, то план является не оптимальным и его надо улучшать.

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

3. Алгоритм улучшения неоптимального плана.

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

1) Маршрут начинается и заканчивается в клетке с отрицательной характеристикой;

2) Линии контура строго вертикальны или горизонтальны (нельзя двигаться по диагонали);

3) Повороты (на 90⁰) можно осуществлять только в заполненных клетках.

После построения замкнутого маршрута (самый простой вариант – прямоугольник), происходит перераспределение груза (улучшение опорного плана) по следующей схеме:

4) Каждой угловой клетке маршрута (где осуществлялись повороты на 90⁰) присваивается знак «+» или «-», причем клетке, из которой начинается маршрут, приписывают знак «+», далее знаки чередуются;

5) Среди клеток со знаком «-» выбирают клетку с наименьшим грузом;

6) Наименьший груз прибавляют ко всем клеткам со знаком «+» и вычитают из всех клеток со знаком «-». При этом пустая клетка, из которой начиналось движение и которая имела отрицательную характеристику, становится заполненной, а заполненная клетка, имевшая груз, который подлежал перераспределению, стала пустой.

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

Проверим, например, оптимальность плана, построенного методом «Минимального элемента» в Таблице 3 (он лучше плана построенного методом «Северо-западного угла» в Таблице 2). Для этого рассчитаем потенциалы строк и столбцов по заполненным клеткам Таблицы 3.

Результаты расчетов запишем в таблицу 4.

Таблица 4

Поставщики	Потребители	Потенциалы строк
		«-» 7		«+» 5
	«-» 1	75 «+»			- 5
	«+»			50 «-»	- 3
Потенциалы столбцов

Теперь по таблице 4 рассчитаем характеристики свободных клеток. Имеем, ; ; ; ; ; (-3+3)=20.Таким образом, среди свободных клеток одна клетка (3;1) имеет отрицательную характеристику .

По описанной выше схеме строим маршрут перераспределения груза. Движение начинаем из клетки (3;1) и ей присваиваем знак «+». Далее знаки чередуются. Среди клеток со знаком «-» наименьший груз (равный 5 ед.) в клетке (1;2). Этот груз мы вычитаем из клеток (1;2), (2;1), (3;4) и прибавляем в клетки со знаком «+» (3;1), (1;4), (2;2).

Таблица 5

Поставщики	Потребители	Запасы груза
Потребность в грузе

Получаем новый опорный план (таблица 5).