Максимально припустиме зрушення по циклу перерахування

Поняття циклу перерахування

Цикли перерахування

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

Легко переконатися, що кожний цикл має парне число вершин, яке дорівнює подвоєному числу горизонтальних ланок.

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

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

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

У таблиці 5.4 пунктиром показано два цикли перерахування. Перший проходить через вільну клітинку (1,3), а другий – через вільну клітинку (3,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	10 -		+ 30
А2		2
А3	+		_ 10
Потреби				150 = 150

Зрозуміло, у новому опорному плані число базисних клітинок як і раніше дорівнює 5.

Якщо мінімальне перевезення стоїть в декількох від’ємних клітинках, то в результаті максимально припустимого зрушення тільки одна з цих кліток перетворюється у вільну, а інші клітинки залишаються базисними й в них проставляється число 0. Тільки при дотриманні цієї умови число базисних клітинок залишатиметься рівним m+ n -1.

Звернемось до таблиці 5.5. Величина максимально припустимого зрушення по циклу перерахування дорівнює 10. З двох від’ємних клітинок (1,1) і (3,3) тільки одна в результаті зрушення перетворюється у вільну. Зробивши вільною клітинкою клітинку (3,3), отримаємо новий опорний план перевезення (табл. 5.6).

Таблиця 5.6.

Пп   Пв	В1	В2	В3	Запасы
А1
А2		2
А3
Потреби				150 = 150

Порівняємо сумарні вартості планів перевезень, зображених у
таблицях 5.4, 5.5, 5.6.

Таблиця 5.4: f = 2*40 + 4*30 + 2*30 + 2*10 + 6*40 = 520 гр. од.
Таблиця 5.5: f = 2*10 +1*30 + 4*60 + 2*40 + 6*10 = 430 гр. од.
Таблиця 5.6: f = 1*40 +4*60 + 3*10 + 2*40 = 390 гр. од.

Бачимо, що в результаті двох зрушень ми значно покращили план перевезення. Це відбулося з причини того, що цикли перерахунку, по яких здійснювались зрушення, обиралися у спеціальний спосіб. Для з’ясування сутності того, що відбулося, потрібно ввести поняття ціни циклу перерахування.

Дата добавления: 2014-01-07