3.3. Распределительный метод решения транспортной задачи.

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

Алгоритм распределительного метода

Алгоритм распределительного метода построен на принципе последовательного улучшения опорных решений и включает в себя следующие этапы:

Рис 1. Блок-схема принципа последовательного улучшения

опорных решений

Рассмотрим алгоритм более подробно для решения задачи на минимум. Блок-схема алгоритма приведена на рис. 2.

Блок 1. Записывается исходное опорное решение одним из методов (перечисленных в п. 3.2. – выше).

Рис.2. Блок-схема алгоритма распределительного метода

решения задач на минимум

Блок 2. Строятся циклы для всех свободных клеток.

Циклом свободной клетки называется замкнутый набор клеток распределительной таблицы, соединенных отрезками прямых, удовлетворяющих следующим условиям:

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

Стороны цикла могут пересекать как свободные, так и базисные клетки.

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

Блок 3. Характеристики свободных клеток вычисляются по формуле:

где - характеристики свободной клетки,

- коэффициенты транспортных затрат.

Блок 4. Вычисленные характеристики записываются.

Блок 5. Если все характеристики неотрицательные, то при решении задачи на минимум, получиться оптимальное решение (блок 9). Если условие не выполняется, план не оптимален и требует улучшения.

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

Блок 7. Для свободной клетки, имеющей наименьшую отрицательную характеристику, используем цикл, построенный в блоке 2. Выполняем преобразования однократного замещения для этого цикла. Свободная клетка цикла всегда первая (нечетная). Нечетные вершины цикла обозначаем «+», а четные – «-». Находим значение , равное минимальному значению из значений базисных переменных в отрицательных (четных) вершинах (клетках) цикла:

(четные клетки цикла)

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

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

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

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

Блок 9. Критерием оптимальности при решении задач на минимум является отрицательное значение характеристик свободных клеток.

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

Пример

Поле зерновых занимает 70 га в севообороте. Запланировано посеять пшеницы 30 га, ржи 20 га и овса 20 га. Поле состоит из участков 25, 35, 10 га. Известна урожайность зерновых с каждого участка (табл. 1). Составить план посева зерновых так, чтобы он обеспечивал максимальный выход зерна.

Таблица 1