Приложение 3

Общая постановка транспортной задачи линейного программирования и методы составления начального плана перевозок

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

Общая постановка транспортной задачи:

«Определить оптимальный по стоимости план перевозок однородного груза из m пунктов отправления (ПО) в n пунктов назначения (ПН) в следующих условиях:

1) запасы грузов в ПО заданы вектором ā = (а₁, а₂, …, а_j, …, а_m);

2) потребности в грузах в ПН заданы вектором  = (b₁, b₂, …, b_i, …, b_n);

3) тарифы на перевозку единицы груза из j-го ПО в i-ый ПН заданы матрицей (C_ij)».

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

Если условие не выполняется, то в задачу вводится либо фиктивный пункт ПН с потребностью (тарифы С_in+1 =0 для всех j=1,m), либо фиктивный ПО с запасом (тарифы С_m+1i =0 для всех i=1,n).

Решение транспортной задачи выполняется в 2 этапа:

Этап 1. Определяется начальный опорный план перевозок одним из трех методов:

• метод «северо-западного угла»;

• метод минимального элемента;

• метод Фогеля.

Этап 2. Определяется оптимальный план перевозок в результате итерационных улучшений опорного плана перевозок (распределительный метод, метод потенциалов и его модификации).

Пример. Сравнительный анализ различных методов определения начального опорного плана.

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

Метод исключительно прост, так как не учитывает тарифы на перевозку. Оптимизация отсутствует.

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

Метод минимального элемента:

Метод ориентируется на минимальные тарифы матрицы перевозок. Происходит оптимизация текущего шага.

Технология: В матрице перевозок находится ячейка, которой соответствует минимальный тариф на перевозку. Если таких ячеек несколько, выбирается любая. В выбранную ячейку записывается максимально возможный объем перевозимого груза (-//-). ПО с исчерпанными запасами и ПН с закрытыми потребностями постепенно выбывают из рассмотрения. Процесс продолжается до полного заполнения матрицы.

Метод Фогеля:

Метод учитывает все тарифы в матрице. Происходит оптимизация текущего шага с учетом следующего.

Технология: По строкам и столбцам матрицы находятся наиболее дешевые тарифы, после чего рассчитываются их возможные минимальные удорожания на следующем шаге. Удорожание рассчитывается как разница между предпоследним по дешевизне доступным тарифом по каждой строке/столбцу и самым дешевым доступным тарифом в той же строке/столбце. Для заполнения выбирается одна строка или столбец, по которым на следующем шаге ожидается максимальное удорожание. В выбранной строке или столбце, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом, куда записывается максимально возможный объем перевозимого груза (-//-). Если на шаге существует несколько строк или столбцов с одинаковым удорожанием или несколько ячеек с одинаковым тарифом, то для заполнения выбирается любая из них. ПО с исчерпанными запасами и ПН с закрытыми потребностями постепенно выбывают из рассмотрения. Процесс продолжается до полного заполнения матрицы.

Вывод: метод Фогеля дает начальный опорный план наиболее близкий к оптимальному.

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

Алгоритм решения транспортной задачи методом потенциалов

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

ШАГ №1. Любым методом определяется начальный опорный план перевозок, в котором есть базисные и свободные клетки.

ШАГ №2. Определяются потенциалы (U_j, V_i) таким образом, чтобы в любой базисной клетке псевдостоимость была равна стоимости (псевдотариф был равен тарифу). Причем для расчета один из потенциалов можно назначить произвольно (например, положить равным нулю).

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

ШАГ №4. Выполняется улучшение плана путем перестановки груза по циклам, которые соответствуют свободным клеткам с отрицательной ценой цикла. Для этих клеток псевдостоимость превышает стоимость. Переходим к шагу №2.

Замечания:

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

1) для всех базисных клеток;

2) для всех небазисных клеток.

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

Пример решения транспортной задачи методом потенциалов.

Задача о назначениях и ее решение по двухэтапной схеме методом К. Мака

Задача о назначениях имеет важное практическое значение и связана с распределением:

• исполнителей по работам;

• рабочих по станкам;

• механизмов по объектам;

• заказов по предприятиям;

• задач по компьютерам;

• автобусам по маршрутам;

• самолетов по авиалиниям;

• инвестиций по проектам и т.д.

Задача о назначениях формулируется следующим образом:

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

Замечания:

1. Если задана матрица выигрышей, то следует перейти к матрице затрат;

2. Если количество исполнителей и работ не совпадает, то вводятся фиктивные исполнители или фиктивные работы (аналогично транспортной задаче с неправильным балансом);

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

Метод Мака реализуется по двухэтапной схеме:

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

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

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

Пример постановки и решения задачи о назначениях.

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

краны	объекты
	№1	№2	№3	№4
№1	3	7	5	8
№2	2	4	4	5
№3	4	7	2	8
№4	9	7	3	8

Найти вариант распределения кранов по объектам, при котором затраты времени на монтаж всех 4 объектов будут минимальными.

Решение.

Этап 1. Каждый кран назначается на объект по минимальным затратам на выполнение работ. Причем на объекты №2 и №4 краны не назначены.

краны	объекты
	№1	№2	№3	№4
№1	3	7	5	8
№2	2	4	4	5
№3	4	7	2	8
№4	9	7	3	8

Этап 2. К элементам столбца №1 прибавлено число 2, что позволяет кран №2 назначить на объект №2, причем на объект 4 кран не назначен.

краны	объекты
	№1	№2	№3	№4
№1	6	8	10	8
№2	5	5	9	5
№3	7	8	7	8
№4	12	8	8	8

К элементам столбцов №1 и 2 прибавлено число 1, к элементам столбца №3 – 5, что позволяет кран 4 назначить на объект 4. Останов вычислительного процесса, так как все краны распределены по объектам.

Оптимальное решение: Кран №1 выполняет монтаж объекта №1; №2-№2; №3 - №3; №4 - №4. Минимальные затраты времени на монтаж всех объектов 17 крано-суток.

(еще 2 примера)

.