Производственно-транспортные задачи и их решение

Прикладные науки

Решение производственно-транспортных задач основывается на решении классической транспортной задачи по критерию минимума целевой функции (т/км, руб.) с учетом суммарных затрат на производство и доставку однородной продукции до потребителей.

Транспортная задача по критерию издержек

Постановка задачи: На m станциях отправления А1,, А2,…, Аi,.., Аm имеется а1, a2,.., аi,.., аm единиц однородного груза, упакованного в контейнеры, соответственно. Этот груз необходимо перевезти n потребителям В1, В2,.., Вi,…, Вn в количествах, соответственно равных b1, b2, . . .  ,bi,.., bn. Известны величины Сij, характеризующие затраты по перевозке единицы груза из пункта Аi, в пункт Bj. Требуется определить оптимальный план перевозок, при котором минимизируются общие суммарные затраты на перевозки.

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

Пусть Хij — объем перевозки груза из пункта Аi в пункт Вj, (от i-го поставщика до j-го потребителя), тогда

         

              (3.25) (3.26) (3.27)

Система ограничений (3.25) характеризует ограничения по ресурсам, (3.26) – ограничения по потребностям.

Составим таблицу для решения данной задачи.

Если для задачи (3.25) — (3.27) выполнено условие баланса.

Сумма (аi) = Сумма (bj),

(3.28)

то транспортная задача называется закрытой.

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

или фиктивного потребителя со спросом 

(если Сумма (аi > bj ). Для фиктивного поставщика или потребителя Сij = 0.

Необходимое и достаточное условие для разрешимости задачи сводится к выполнению условия баланса (3.28).

Исходный опорный план можно найти по методу северо-западного угла или минимального элемента. Невырожденный план задачи содержит (m + п — 1) базисных переменных, которым соответствуют занятые клетки в таблице решения.

Решение задачи обычно находится по методу потенциалов.

Book-Science
Добавить комментарий