Главная | Обратная связь

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

Зрушенням на величину 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 гр. од.

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