Побудова початкових опорних планів

Розглянемо на прикладі такі методи знаходження початкових опорних планів: північно-західного кута (діагональний метод) і метод найменшої вартості.

Приклад 11.

aі	bj
	^2	^3	^2	^4
	^2	^4	^6	^5
	^1	^5	^4	^5

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

У першого постачальника є 65 одиниць вантажу, а першому споживачу треба тільки 45 одиниць. Тому у першу клітинку запишемо поставку . Більше першому споживачу вантажу не потрібно, тому інші квадратики у першому стовпчику закреслюємо. Поставки у ці клітинки дорівнюють нулю.

aі	bj
	45^2	^3	^2	^4
	^2	^4	^6	^5
	^1	^5	^4	^5

Заповнені клітинки називатимемо базисними, а закреслені – вільними. Базисні клітинки відповідають базисним невідомим, а вільні – вільним.

Знову вибираємо верхню ліву клітинку у частині таблиці, що залишилась. У першого постачальника є ще 65–45=20 одиниць вантажу, а другому споживачу треба 60 одиниць вантажу. Тому у другу клітинку запишемо поставку . Перший постачальних вичерпав усі свої запаси, тому закреслюємо всі інші клітинки у першому рядку.

aі	bj
	45^2	20^3	^2	^4
	^2	^4	^6	^5
	^1	^5	^4	^5

Заповнюємо наступну вільну верхню ліву клітинку. Запаси вантажу дорівнюють 80, а потреби лише 60–20=40, тому поставка дорівнює 40. Продовжуємо такий процес заповнення до останньої клітинки.

aі	bj
	45^2	20^3	^2	^4
	^2	40^4	40^6	^5
	^1	^5	40^4	65^5

Зауваження. Кількість базисних клітинок завжди визначають як . Якщо заповнених клітинок менше, то отримаємо вироджений опорний розв’язок. В цьому разі потрібно необхідну кількість клітинок заповнити нульовими поставками.

Отже, опорний план, знайдений за методом північно-західного кута має вигляд

Обчислимо вартість перевезення

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

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

aі	bj
	^2	^3	^2	^4
	^2	^4	^6	^5
	45^1	^5	^4	^5

Серед невикористаних клітинок обираємо клітинку з найменшею вартістю. . Поставка , закреслюємо ще дві вільні клітинки.

aі	bj
	^2	^3	65^2	^4
	^2	^4	^6	^5
	45^1	^5	^4	^5

Серед клітинок, що залишились, обираємо клітинку з найменшою вартістю. Таких клітинок дві: . Але , а . Оскільки , то заповнюємо спочатку клітинку з більшою поставкою.

aі	bj
	^2	^3	65^2	^4
	^2	60^4	^6	^5
	45^1	^5	^4	^5

Наступна клітинка з поставкою .

aі	bj
	^2	^3	65^2	^4
	^2	60^4	^6	^5
	45^1	^5	15^4	^5

Серед двох останніх клітинок з однаковими вартостями та поставками і треба обрати , а потім .

aі	bj
	^2	^3	65^2	^4
	^2	60^4	^6	20^5
	45^1	^5	15^4	45^5

Отже, опорний план, знайдений за методом мінімальної вартості має вигляд

.

Обчислимо вартість перевезення

Отже, найближчий до оптимального плану початковий опорний план, який знайдено методом найменшоï вартості. Тому його рекомендується застосовувати на практиці. Метод північно-західного кута, як правило, застосовується при розв’язуванні задач на ЕОМ.

Дата добавления: 2014-12-25