Решение транспортной задачи

Задача

Математическая модель задачи

Проверка задачи на закрытость модели

Нахождение начального опорного плана и метод потенциалов

Краткая теория

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

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

Имеется пунктов отправления: , в которых сосредоточены запасы какого-то однородного товара (груза) в количестве соответственно единиц. Кроме того имеется пунктов назначения: , подавших заявки соответственно на единиц товара.

Предполагается, что сумма всех заявок равна сумме всех запасов:

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

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

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

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

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

2. Суммарное количество груза, доставляемое в каждый пункт назначения изо всех пунктов отправления, должно быть равно заявке, поданной данным пунктом. Это даст условий-равенств:

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

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

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

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

Любую совокупность значений будем называть планом перевозок или просто планом.

План будем называть допустимым, если он удовлетворяет условиям системы равенств (так называемым «балансовым условиям»): все заявки удовлетворены, все запасы исчерпаны.

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

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

Основные этапы решения транспортной задачи будут такими:

I этап. Нахождение начального опорного плана .

II этап. Выделение из небазисных переменных вводимой в базис переменной (метод потенциалов). Если все небазисные переменные удовлетворяют условию оптимальности, то следует закончить вычисления; в противном случае - перейти к III этапу.

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

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

В трех пунктах отправления имеется однородный груз в количестве соответственно. Этот груз нужно доставить пяти заказчикам . Потребности в грузе в каждом пункте известны и равны соответственно. Известны также тарифы перевозки - стоимость перевозки единицы груза из пункта в пункт . Нужно найти такой план перевозок, при котором весь груз из пунктов потребления будет вывезен, потребности всех заказчиков будут удовлетворены, и при этом общая стоимость перевозки всего груза будет наименьшей. Данные в таблице, в клетках которой проставлены элементы матрицы тарифов ; в последнем столбце таблицы указаны значения величин , в последней строке - значения величин .

Требуется:

Составить математическую модель задачи.
Найти оптимальное решение транспортной задачи методом потенциалов.

На сайте можно заказать решение задач, контрольных, самостоятельных, домашних работ (возможно срочное решение). Для этого вам нужно только связаться со мной:

Телеграм (+7 968 849-45-98)
ВКонтакте
WhatsApp (+7 968 849-45-98)

Мгновенная связь в любое время и на любом этапе заказа. Общение без посредников. Удобная и быстрая оплата переводом на карту. Опыт работы более 25 лет.

Подробное решение в электронном виде (docx, pdf) получите точно в срок или раньше.

Решение

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

Ограничения для поставщиков:

Ограничения для потребителей:

Объем суммарных поставок любого поставщика к потребителю не может быть отрицательным числом, поэтому справедливы ограничения:

Полученную задачу можно решить симплекс-методом, так как это классическая ЗЛП, однако относительная простота систем уравнений дает возможность использовать метод решения более простой. Особенности систем следующие:

коэффициенты при неизвестных во всех уравнениях равны 1;

каждая переменная встречается только в двух уравнениях; система уравнений транспортной задачи симметричная относительно всех переменных ; матрица, составленная из коэффициентов при переменных состоит из единиц и нулей, причем каждый столбец матрицы содержит два элемента, равных 1, а остальные 0.

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

В нашем случае:

Модель транспортной задачи закрытая.

Заказчики Пункты

Заполняем таблицу по правилу минимального элемента .

Просматривая таблицу замечаем, что наименьшие затраты соответствуют маршруту , поэтому в клетку помещаем . В этом случае 4-й столбец в расчет не принимается. Просматриваем оставшиеся таблицы клетки. Наименьший тариф имеет клетка

Далее действуя по аналогичной схеме:

Решать задачу будем методом потенциалов. Число занятых клеток должно быть . Потенциал 1-й строки принимаем равным нулю. После этого мы можем вычислить остальные потенциалы (если известны потенциал и тариф занятой клетки, то из соотношения v + u =c легко определить неизвестный потенциал).

Найдем оценки свободных клеток по формуле:

S ( 1, 1)= 4-( 0-1)= 5	S ( 1, 2)= 9-( 0+ 0)= 9
S ( 1, 4)= 5-( 0-4)= 9	S ( 2, 2)= 6-( 5+ 0)= 1
S ( 2, 3)= 2-( 5+ 2)= -5	S ( 3, 1)= 6-( 2-1)= 5
S ( 3, 3)= 3-( 2+ 2)= -1	S ( 3, 4)= 4-( 2-4)= 6

Для клетки ( 2, 3) с минимальной отрицательной оценкой строим цикл.

Перемещаем груз, равный 1 из вершин, помеченных минусом к вершинам цикла, помеченным плюсом.

Вычисляем потенциалы:

Найдем оценки свободных клеток по формуле

S ( 1, 1)= 4-( 0+ 4)= 0	S ( 1, 2)= 9-( 0+ 0)= 9
S ( 1, 4)= 5-( 0+ 1)= 4	S ( 2, 2)= 6-( 0+ 0)= 6
S ( 2, 5)= 8-( 0+ 3)= 5	S ( 3, 1)= 6-( 2+ 4)= 0
S ( 3, 3)= 3-( 2+ 2)= -1	S ( 3, 4)= 4-( 2+ 1)= 1

Для клетки ( 3, 3) с минимальной отрицательной оценкой строим цикл.

Перемещаем груз, равный 7 из вершин, помеченных минусом к вершинам цикла, помеченным плюсом.

Вычисляем потенциалы:

Найдем оценки свободных клеток по формуле

S ( 1, 1)= 4-( 0+ 4)= 0	S ( 1, 2)= 9-( 0+ 1)= 8
S ( 1, 4)= 5-( 0+ 1)= 4	S ( 2, 2)= 6-( 0+ 1)= 5
S ( 2, 5)= 8-( 0+ 3)= 5	S ( 3, 1)= 6-( 1+ 4)= 1
S ( 3, 4)= 4-( 1+ 1)= 2	S ( 3, 5)= 5-( 1+ 3)= 1

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

Ответ

Пункт поставляет 8 единиц груза в пункт и 15 единиц груза в пункт

Пункт поставляет 14 единиц груза в пункт , 1 единицу груза в пункт и 10 единиц груза в пункт

Пункт поставляет 10 единиц груза в пункт и 7 единиц груза в пункт

Минимальные транспортные издержки оптимального плана: