Главная » Учебно-методические материалы » ВЫСШАЯ МАТЕМАТИКА, ТВ и МС, МАТ. МЕТОДЫ » Математические методы. Попова Н.В.

Тема 2.5. Транспортная задача
22.12.2011, 14:12

Частным случаем задачи линейного программирования является транспортная задача. 
ТЗ в общем виде состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А, А, ..., Аm в n пунктов назначения B, B, ..., Bn. В качестве критерия оптимальности можно взять минимальную стоимость перевозок всего груза, либо минимальное время его доставки. 
Рассмотрим задачу с первым критерием, обозначив через сn тарифы перевозок единицы груза из i-го пункта отправления в j-й пункт назначения, через ai - запасы груза в пункте Аi через bj - потребности в грузе пункта Bxij - количество единиц груза, перевозимого из i-го пункта в j-й пункт. 
Составим математическую модель задачи. Так как от i-гo поставщика к j-му потребителю запланировано к перевозке xij единиц груза.

Таблица 2.2

Поставщики
Потребители
Запасы
BB2
...
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

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

(2.17)

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

(i = l, ..., m),(2.18)
(j = 1, ..., n),(2.19)
xij ≥ 0
(i = l, ..., m; j = l, ..., n).(2.20)

Всякое неотрицательное решение систем уравнений (2.18)-(2.20), определяемое матрицей X=(xij ), называют опорным планом ТЗ, а план X*=(xij ), при котором функция Z принимает минимальное значение - называется оптимальным планом ТЗ. 
Все данные, а затем и опорный план, удобно занести в распределительную таблицу (см, в примерах параграфа). 
Если общее количество груза в пунктах отправления и общая потребность в нем в пунктах назначения совпадают, т.е.

(2.21)

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

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

Доказательство:

Тогда величины xij = aib/M (i = 1, 2, ..., m; j = 1, 2, ..., n) являются планом, так как они удовлетворяют, системе ограничений (2.18), (2.19). Действительно, подставляя значения xij в (2.18) и (2.19), имеем

Выберем из значений Cij наибольшее С'= mах Cij и заменим в линейной функции (2.17) все коэффициенты на С' тогда, учитывая (2.18), получаем 

Выберем из значений Cij наименьшее С''=min Cij и заменим в линейной функции все коэффициенты на С'' тогда, имеем 

Объединяя два последних неравенства в одно двойное, окончательно получаем C"M ≤ Z ≤ C'M, т. е. линейная функция ограничена на множестве планов транспортной задачи. 
Ч.Т.Д. 
Если общее количество груза в пунктах отправления и общая потребность в нем в пунктах назначения не совпадают ТЗ называется открытой. Введением фиктивного потребителя (если ), или фиктивного отправителя (если , любая задача приводится к закрытой модели (во всех фиктивных ячейках таблицы полагают cij= 0). Для разрешимости задачи равенство (2.21) является необходимым и достаточным условием. 
Нахождение опорных и оптимального планов ТЗ можно вести симплексным методом, но, ввиду специфики ТЗ, и большого ее прикладного значения, разработаны специальные методы. 
Нахождение опорных планов ТЗ можно осуществить одним из пяти методов: северо-западного угла, минимальной стоимости, аппроксимации Фогеля, двойного предпочтения и дельта-метода.


http://matmetod-popova.narod.ru/




БАНКОВСКОЕ ДЕЛО
БУХГАЛТЕРСКИЙ УЧЕТ
БЮДЖЕТ И БЮДЖЕТНАЯ СИСТЕМА РФ
ВЫСШАЯ МАТЕМАТИКА, ТВ и МС, МАТ. МЕТОДЫ
ГУМАНИТАРНЫЕ НАУКИ
ДОКУМЕНТОВЕДЕНИЕ И ДЕЛОПРОИЗВОДСТВО
ДРУГИЕ ЭКОНОМИЧЕСКИЕ ДИСЦИПЛИНЫ
ЕСТЕСТВЕННЫЕ ДИСЦИПЛИНЫ
ИНВЕСТИЦИИ
ИССЛЕДОВАНИЕ СИСТЕМ УПРАВЛЕНИЯ
МАРКЕТИНГ
МЕНЕДЖМЕНТ
МЕТ. РЕКОМЕНДАЦИИ, ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
МИРОВАЯ ЭКОНОМИКА И МЭО
НАЛОГИ И НАЛОГООБЛОЖЕНИЕ
ПЛАНИРОВАНИЕ И ПРОГНОЗИРОВАНИЕ
РАЗРАБОТКА УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ
РЫНОК ЦЕННЫХ БУМАГ
СТАТИСТИКА
ТЕХНИЧЕСКИЕ ДИСЦИПЛИНЫ
УПРАВЛЕНИЕ ПЕРСОНАЛОМ
УЧЕБНИКИ, ЛЕКЦИИ, ШПАРГАЛКИ (СКАЧАТЬ)
ФИНАНСОВЫЙ МЕНЕДЖМЕНТ
ФИНАНСЫ, ДЕНЕЖНОЕ ОБРАЩЕНИЕ И КРЕДИТ
ЦЕНЫ И ЦЕНООБРАЗОВАНИЕ
ЭКОНОМИКА
ЭКОНОМИКА, ОРГ-ЦИЯ И УПР-НИЕ ПРЕДПРИЯТИЕМ
ЭКОНОМИКА И СОЦИОЛОГИЯ ТРУДА
ЭКОНОМИЧЕСКАЯ ТЕОРИЯ (МИКРО-, МАКРО)
ЭКОНОМИЧЕСКИЙ АНАЛИЗ
ЭКОНОМЕТРИКА
ЮРИСПРУДЕНЦИЯ