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


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



ЗНАЕТЕ ЛИ ВЫ?

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



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

ТЗ в общем виде состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А1 , А2 ,..., Аm в n пунктов назначения B1 , B2 ,..., Bn. В качестве критерия оптимальности можно взять минимальную стоимость перевозок всего груза, либо минимальное время его доставки.

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

Таблица 39.1

Поставщики Потребители Запасы
B1 B2 ... Bn
А1 C11 X11 C12 X12 ... C1n X1n a1
А2 C21 X21 C22 X22 ... C2n X2n a2
... ... ... ... ... ...
Аm Cm1 Xm1 Cm2 Xm2 ... Cmn Xmn am
Потребности b1 b2 ... bn ∑ai=∑bj

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

(39.1)

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

, (39.2)

, (39.3)

, ; (39.4)

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

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

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

, (39.5)

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

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

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

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

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

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

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

 



Поделиться:


Последнее изменение этой страницы: 2016-12-14; просмотров: 497; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.140.185.147 (0.006 с.)