Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Максимально допустимый сдвиг по циклу пересчета




Понятие цикла пересчета

Циклы пересчета

Пусть имеется транспортная задача (5.1 - 5.4) и соответствующая таблица 5.1. Циклом называется замкнутая ломаная линия, вершины которой лежат в клетках таблицы, а звенья попеременно принадлежат то строке, то столбцу.

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

Цикл называется означенным, если его вершинам попеременно приписаны знаки "+" и "–".

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

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

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

 

Сдвигом на величину h ≥ 0 по циклу пересчета называется увеличение на число h перевозок, стоящих в положительных вершинах цикла, и уменьшение на число h перевозок, стоящих в отрицательных вершинах.

Так как в каждой строке и каждом столбце транспортной таблицы
количество положительных вершин равно количеству отрицательных
вершин цикла, то при сдвиге на любое число h условия (5.2) и (5.3)
не нарушаются. Чтобы не нарушалось условие (5.4), величина сдвига
не должна превышать минимальной перевозки, стоящей в отрицательной
вершине цикла.

Сдвиг, величина которого равна минимальной перевозке, стоящей в отрицательной вершине цикла, называется максимально допустимым сдвигом.

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

Рассмотрим пример (табл.5.4). Сделаем максимально допустимый сдвиг по циклу пересчета, проходящему через свободную клетку (1,3). Перевозки, стоящие в отрицательных вершинах цикла, равны 40, 30 и 40. Поэтому величина максимально допустимого сдвига h=min(40,30,40)=30. После сдвига получим новый опорный план перевозок (табл.5.5).

Таблица 5.5.

Пн По В1 В2 В3 Запасы
А1 2 10 3 1  
А2 4 60 2 5  
А3 3 2 40 6 10  
Потребности       150=150

 

Разумеется, в новом опорном плане число базисных клеток по-прежнему равно 5.

Если минимальная перевозка стоит в нескольких отрицательных клетках, то в результате максимально допустимого сдвига только одна из этих клеток превращается в свободную, а остальные клетки остаются базисными и в них проставляется число 0. Только при соблюдении этого условия число базисных клеток остается равным m+n–1.

Обратимся к таблице 5.5. Величина максимально допустимого сдвига по указанному пунктиром циклу пересчета равна 10. Из двух отрицательных клеток (1,1) и (3,3) только одна в результате сдвига превращается в свободную. Сделав свободной клетку (3,3), получим новый опорный план перевозок (табл.5.6).

Сравним суммарные стоимости планов перевозок, изображенных в
таблицах 5.4, 5.5, 5.6.

Таблица 5.4: f = 40·2 + 30·4 + 30·2 + 10·2 + 40·6 = 520
Таблица 5.5: f = 10·2 + 30·1 + 60·4 + 40·2 + 10·6 = 430
Таблица 5.6: f = 40·1 + 60·4 + 10·3 + 40·2 = 390

 

Таблица 5.6

Пн По В1 В2 В3 Запасы
А1 2 0 3 1  
А2 4 60 2 5  
А3 3 2 40 6  
Потребности       150=150

 

Видим, что в результате двух сдвигов мы значительно улучшили план перевозок. Это произошло потому, что циклы пересчета, по которым производились сдвиги, выбирались специальным образом. Для выяснения сути происшедшего потребуется понятие цены цикла пересчета.

 




Поделиться с друзьями:


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


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



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




Генерация страницы за: 0.009 сек.