Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Метод потенциалов


Широко распространенным методом решения транспортных задач является метод потенциалов. Этот метод позволяет упростить наиболее трудоемкую часть вычислений — нахождение оценок свободных клеток.

Теорема(признак оптимальности опорного решения). Если допустимое решение X = (хij), i= 1, 2, ..., m, j = 1, 2, ..., п транспортной задачи является оптимальным, то существуют потенциалы (числа) поставщиков иi, i = 1, 2, ..,, т и потребителей v j , j = 1, 2, ..., п, удовлетворяющие следующим условиям:

ui+ vj = cij при хij > 0 и ui+ vj ≤ cij при хij = 0.

Группа равенств ui+ vj = cij при хij > 0 используется как система уравнений для нахождения потенциалов. Нетрудно видеть, что эта система могла иметь несколько другой вид, например - ui+ vj = cij или ui- vj = cij , если перед тем, как записать двойственную задачу, все уравнения одной из групп уравнений исходной задачи умножить на (-1).

Данная система уравнений имеет т + п неизвестных иi, i=1,2, ..., т и vj, j= 1, 2, ..., п. Число уравнений системы, как и число отличных от нуля координат невырожденного опорного решения, равно т + п — 1. Так как число неизвестных системы на единицу больше числа уравнений, то одной из них можно задать значение произвольно, а остальные найти из системы.

Группа неравенств ui+ vj ≤ cij при хij = 0 используется для проверки оптимальности опорного решения. Эти неравенства удобно записать в виде

Δij =ui+ vj - cij 0 при хij = 0.

Числа Δij называются оценками свободных клеток таблицы или векторов ― условий транспортной задачи, не входящих в базис опорного решения. В этом случае признак оптимальностиможно сформулировать так же, как в симплексном методе (для задачи на минимум): опорное решение является оптимальным, если для всех векторов-условий (клеток таблицы) оценки неположительные.

Оценки для свободных клеток транспортной таблицы используются для улучшения опорного решения. С этой целью находят клетку (l, k) таблицы, соответствующую max{Δij}= Δlk. Если Δlk ≤ 0, то решение оптимальное. Если же Δ lk > 0, то для соответствующей клетки (l, k) строят цикл и улучшают решение, перераспределяя груз θ = по этому циклу.



 

<== предыдущая лекция | следующая лекция ==>
Переход от одного опорного решения к другому | Особенности решения транспортных задач с неправильным балансом

Дата добавления: 2014-01-04; Просмотров: 283; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.003 сек.