Транспортная задача. Закрытая и открытая модели.

↑

▷ Содержание

⇐ ПредыдущаяСтр 7 из 11Следующая ⇒

Частным случаем задачи линейного программирования является транспортная задача (ТЗ).

ТЗ в общем виде состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А₁ , А₂ ,..., А_m в n пунктов назначения B₁ , B₂ ,..., B_n. В качестве критерия оптимальности можно взять минимальную стоимость перевозок всего груза, либо минимальное время его доставки.

Рассмотрим задачу с первым критерием, обозначив через - тарифы перевозок единицы груза из i -го пункта отправления в j -й пункт назначения, через a_i - запасы груза в пункте А_i, через b_j - потребности в грузе пункта B_j , - количество единиц груза, перевозимого из i -го пункта в j -й пункт.
Составим математическую модель задачи. Так как от i -гo поставщика к j -му потребителю запланировано к перевозке единиц груза.

Таблица 39.1

Соответственно математическая постановка задачи состоит в определении минимума целевой функции

(39.1)

при условиях:

, (39.2)

, (39.3)

, ; (39.4)

Всякое неотрицательное решение систем уравнений (39.2)-(39.4), определяемое матрицей , называют опорным планом ТЗ, а план при котором функция Z принимает минимальное значение - называется оптимальным планом ТЗ.

Все данные, а затем и опорный план, удобно занести в распределительную таблицу.

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

, (39.5)

то модель ТЗ называется закрытой.

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

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

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

Для разрешимости задачи равенство (39.5) является необходимым и достаточным условием.

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

Нахождение опорных планов ТЗ можно осуществить одним из пяти методов: северо-западного угла, минимальной стоимости, аппроксимации Фогеля, двойного предпочтения и дельта-метода.

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры