Открытая транспортная задача

В случае открытой транспортной задачи имеем .

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

Если , то объем потребления товара превышает объем запасов. Для решения этой задачи вводят фиктивного поставщика с запасом товара . Полученная таким образом задача будет уже закрытой.

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

Пример. Составить оптимальный план перевозки груза от трех складов с товаром 240, 40, 110 тонн к четырем потребителям с запросами 90,190,40, 130 тонн. Стоимости перевозок заданы матрицей .

Запасы товара равны 390 тонн, запросы потребителя 450 тонн. Вводим фиктивный 4-й склад с запасом 60 тонн. Тарифы этого поставщика возьмем равными 20 ко всем потребителям. Составим распределительную таблицу:

						-5
						-2

Количество занятых клеток равно 6. Так как , то имеем вырожденное допустимое решение. Для получения невырожденного решения введем нулевую поставку в клетку (2,2).

Найдем потенциалы . Положим , тогда и .

Так как , то . Так как , то . Так как , то . Так как , тогда . Так как , тогда .

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

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

Этот цикл содержит клетки (1,3),(2,3),(2,2),(1,2). Расставим знаки (+) и (–) вершины со знаком (–) имеют минимальную поставку в 40 тонн. Вычтем эту поставку у вершин со знаком (–) и добавим к вершинам со знаком (+). В результате получим новое решение, которое оформим в таблице.

						-5
						-2

Найдем потенциалы и оценки свободных клеток. , , , , , , , , . Все оценки отрицательные, значит, получили оптимальное решение. . Стоимость всех перевозок 3120 усл.ед.

Приложение транспортных моделей к решению экономических задач

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

1. Оптимальное закрепление за станками операций по обработке деталей. В этом случае тарифы интерпретируются как производительность -го станка при выполнении -й операции. Требуется определить сколько времени и на какой операции нужно использовать станки так, что бы обработать максимальное количество деталей. При этом тарифы берутся с отрицательным знаком.
2. Решение проблемы выбора. Имеется механизмов, которые могут выполнять видов работ с производительностью . Требуется определить какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности.
3. Решение задачи о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции.
4. Увеличение производительности автомобильного транспорта за сет снижения минимизации порожнего пробега, при этом увеличивается производительность автомобилей..

Дата добавления: 2015-06-30; просмотров: 157; Нарушение авторских прав

Мы поможем в написании ваших работ!