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

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

Алгоритм заключается в том, что сначала, строится какой-либо первоначальный допустимый план (рис.1.1), затем проверяется, является ли план оптимальным, если план оптимальный — задача решена, если не оптимальный— отыскивается другой, но обязательно улучшенный и вновь проверяется на оптимальность. Шаги (этапы) 2 и 3 повторяются до тех пор, пока очередной улучшенный план не будет оптимальным.

1.Построение первоначального плана

2 да

нет

3.Построение улучшенного плана

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

Рис.1.1. Алгоритм решения транспортной задачи.

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

1.3. Методы построения начального плана

Существует несколько методов построения начального плана, который иногда называют опорным решением. Наиболее распространенные из них: метод северо-западного угла, метод наименьшей стоимости, двойного предпочтения, по приоритету ближайших пунктов, способ Фогеля, способ Лебедева— Тихомирова и др. Рассмотрим простейшие из них.

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

Решение удобно выполнять в табличной форме. Для этого составляется рабочая таблица в которой в строке слева указываются поставщики (А₁, А₂,..., Аm) и их мощности, в верхней строке указываются потребители (В₁, В₂,..., В_n) и их спрос. В клетках таблицы в верхних левых углах указываются единичные стоимости (С₁₁С₁₂ …….. С_mn), т. е. затраты на доставку единицы продукции от соответствующего поставщика А_i (i=1, 2,.... m) соответствующему потребителю B_j (j=1,2,..:,n).

Рассмотрим конкретный пример решения задачи. Три лесозаготовительных предприятия (А₁, A₂, А₃) заготовляют пиловочник в объемах соответственно 300, 600 и 500 тыс. м³ в год и поставляют четырем деревообрабатывающим предприятиям (В_1, В₂, В₃, В₄). Годовой объем потребления пиловочника деревообрабатывающими предприятиями равен 450, 400, 200 и 350 тыс. м³. Стоимость доставки сырья от ЛЗП к деревообрабатывающим предприятиям представлена матрицей стоимостей, показанной в табл.1.1. цифрами С_ij в левых верхних углах клеток рабочей таблицы.

Таблица 1.1.

Исходные данные для решения транспортной задачи линейного программирования (рабочая таблица).

Поставщики и их мощности, тыс.куб. м.	Потребители и их спрос, тыс.куб.м.
В₁	В₂	В₃	В₄

А₁
А₂
А₃

Согласно методу северо-западного угла распределение поставок от поставщиков к потребителям начинается с клетки А₁B₁ Сравниваем мощность первого поставщика А₁ (300) с потребностью потребителя B₁ (450). Меньшую величину (300) помещаем в клетку А₁B₁ и вычитаем ее из обеих сравниваемых величин. В итоге в остатке первой строки проставляется 0, а в итоге первого столбца остаток 450—300=150 (табл.1.2.). Первую строку из дальнейшего рассмотрения исключаем. Поскольку остаток оказался в первом столбце, следующую поставку назначаем в соседнюю клетку А₂B₁. Сравнивая итоги второй строки (600) и первого столбца (остаток 150), устанавливаем величину поставки, равную 150. Вычтя эту поставку из сравниваемых величин, в итоге первого столбца проставляем 0, а в итоге второй строки записываем разницу 600—150 = 450. На третьей итерации, сравнивая потребность потребителя второго столбца B₂ =400 и остаток мощности второго поставщика А₂ = 450, меньшее значение записываем в клетку А₂B₂. В остатке второго столбца остается 400—400 = 0, а второй строки 450—400 = 50, что и записываем в остаток по строке в результате третьей итерации. Продолжая этот процесс, распределяем поставки по всей таблице. Итог распределения поставок приведен в табл.1.2.

Таблица 1.2.

Построение опорного плана методом северо-западного угла.

Поставщики и их мощности, тыс.куб. м.	Потребители и их спрос, тыс.куб.м.	Остатки по строкам итерации
В₁	В₂	В₃	В₄

А₁
А₂
А₃
Остатки по столбцам	Итерации

В итоге получили некоторое возможное решение. Проверка сумм ∑X_ij по строкам и столбцам показывает на допустимость такого плана распределения поставок и отсутствие арифметических ошибок.

Вычислим значение целевой функции. Для этого перемножим удельные стоимости доставки на соответствующие объемы и найдем сумму

Рассмотрим еще один способ составления начального плана - способ минимального элемента.

Способ минимального элемента несколько сложнее, но позволяет отыскать начальное решение очень близкое к оптимальному, а иногда и оптимальное.

Сущность его заключается в следующем.

В матрице стоимостей отыскивается клетка с минимальным значением C_ij и в эту клетку записывается поставка X_ij =min (a_i b_j). Если матрица содержит несколько одинаковых минимальных значений C_ij, то выбирают любое одно.

После этого вычеркивается строка или столбец. Если a_i> b_j, вычеркивают столбец, при a_i < b_j вычеркивают строку.

Далее процесс (итерации, шаги) повторяют до тех пор, пока не будут распределены все поставки.

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

Распределение поставок по методу минимального элемента выполняется в следующей последовательности.

Шаг 1. Находим минимальное значение стоимости C_ij. В нашем случае это будет C₂₁ = 4. В эту клетку таблицы записываем возможную поставку, т. е. минимальную из А₂ и В₁, Сравнивая А₂ = 600 и В₁ = 450, записываем в клетку Х₂₁ поставку 450. Вычисляем нераспределенные мощности поставщиков и неудовлетворенный спрос потребителей (табл.1.3).

Потребитель В₁ — удовлетворен полностью, во вспомогательной части таблицы проставляем 0, а столбец в дальнейших расчетах не рассматриваем.

Потребитель В₂ неудовлетворен, его спрос остался равным 400, что и записываем во вспомогательной части таблицы.

Потребитель В₃ — неудовлетворен, спрос остался — 200.

Потребитель В₄ — неудовлетворен, спрос —350.

Поставщик А₁ — мощность его не распределена, остаток нераспределенной мощности, равный 300, записываем во вспомогательной части таблицы справа.

Таблица1.3.

Построение опорного плана по методу минимального элемента (шаг 1).

Поставщики и их мощности, тыс.куб. м.	Потребители и их спрос, тыс.куб.м.	Нераспределенные мощности на шагах
В₁	В₂	В₃	В₄

А₁
А₂
А₃
Неудовлетворенный спрос на шагах

Поставщик А₂ — часть мощности распределена потребителю В₁ но осталась нераспределенной мощность 600—450 = = 150, что и записываем во вспомогательную часть таблицы, как нераспределенную мощность на первом шаге.

Поставщик А₃ — мощность его не распределена и записываем результат нераспределенной мощности 500.

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

Шаг 2. Находим минимальное значение стоимости C_ij без вычеркнутого столбца В₁ это значение С₃₃ =5. Записываем в эту клетку (табл. 1.4.) возможную поставку-минимум из А₃ = 500 и В₃ =200, min=200, записываем нераспределенные мощности и неудовлетворенный спрос на этом шаге и их сумму, равную 750, и вычеркиваем из дальнейшего рассмотрения столбец у которого спрос удовлетворен.

Шаг 3. Минимальный элемент А₂В₂ = 7. В эту клетку записываем минимальное значение из нераспределенной мощности А₂ =150 и спроса В₂ =400, min=150. В результате третьего шага мощность поставщика А₂ исчерпана, а сумма нераспределенных мощностей и неудовлетворенного спроса осталась равной 600. Продолжая аналогично, доводим распределение до конца.

Таблица1.4.

Построение опорного плана по методу минимального элемента (шаг 2).

Поставщики и их мощности, тыс.куб. м.	Потребители и их спрос, тыс.куб.м.	Нераспределенные мощности на шагах
В₁	В₂	В₃	В₄

А₁
А₂
А₃
Неудовлетворенный спрос на шагах

Шаг 4. Минимальное C_ij из оставшихся имеют клетки А₁В₂ и А₃В₂ — выбираем А₃В₂ _. Записываем сюда поставку 250 как минимум из значений остатка потребителя В₂ и поставщика А₃ и так далее.