Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Лекция 4–6




8. Транспортная задача

 

Рассмотрим одну из важнейших задач линейного программирования - транспортную задачу. Это задача наиболее рационального прикрепления пунктов отправления грузов к пунктам их назначения, чтобы общая стоимость перевозок была минимальной. Являясь одной из задач линейного программирования, транспортная задача, конечно, может быть принципиально решена алгоритмом симплекс-метода.

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

Один из наиболее распространенных методов решения транспортной задачи – метод потенциалов, полностью использующий особенности условий этой задачи и приводящий к цели значительно быстрее и проще, симплекс-метод.

Транспортная задача формулируется так:

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

 

    b1 b2   …   … bn
a1   c11   x11 c12   x12   …   … c1n   x1n
a2   c21   x21 c22   x22   …   … c2n   x2n
  …     …   …   …   …   …
  …     …   …   …   …   …
am   cm1   xm1 cm2   xm2   …   … cmn   xmn

 

 
 
(1.4.1)

 


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

 

 

План называется допустимым, если числа удовлетворяют следующим естественным ограничениям:

(1.4.2)
( ; ),

( ),

( ),

в которых первые равенств означают, что из каждого пункта производства вывозится весь продукт, а последние равенств означают, что каждый пункт потребления полностью удовлетворяется.



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

(1.4.3)

минимальна.

 

Если система (1.4.2) совместна,

,

таким образом, условие

(1.4.4)

необходимо для совместности (1.4.2). Условие (1.4.4) является и достаточным для совместности (1.4.2). В самом деле, при выполнении условия (1.4.4) значения

( ; ),

как легко проверить, удовлетворяют системе (1.4.2) (нетрудно проверить, что любое из уравнений (1.4.2) является следствием остальных , образующих линейно независимую систему).

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

а) ограничения заданы в виде уравнений,

б) каждая неизвестная входит лишь в два уравнения,

в) коэффициенты при неизвестных – единицы, для ее решения созданы специальные алгоритмы, значительно менее громоздкие, чем алгоритм симплекс-метода. Один из них – м е т о д п о т е н ц и а л о в – представляет собой приспособление общего метода Л,В, Канторовича для решения транспортной задачи.

Другой, так называемый в е н г е р с к и й м е т о д усовершенствован для решения частного случая транспортной задачи – задачи о назначениях (или о выборе).

 


mylektsii.ru - Мои Лекции - 2015-2019 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал