11.5.1.2 Метод найменшої вартості
Обчислення проводяться таким чином.
Крок 1. Вибирається змінна, якій відповідає найменша вартість у всій таблиці, і їй надається можливо більше значення. (Якщо таких змінних декілька, то береться будь-яка з них.)
Крок 2. Викреслюється відповідний стовпець або рядок (оскільки дане обмеження задачі виконане). Якщо обмеження по стовпцю і рядку виконуються одночасно, то, як і в методі північно-західного кута, викреслюється або стовпець, або рядок.
Крок 3. Обчислюється нове значення попиту або обсягу виробництва для невикресленого рядка або стовпця.
Крок 4. Після встановлення обсягу перевезень по маршруту, визначеному на кроці 1, ми маємо справу з новою задачею, в якій сумарне число виробник їй і споживачів на 1 менше, ніж в початковій.
Далі процес повторюється при можливо більшому значенні тієї змінної, якій відповідає мінімальна вартість серед невикреслених (це значення може виявитися і нульовим). Процедура завершується, коли залишається один рядок і один стовпець.
Можна показати, що теорема 5 залишається в силі і при такому способі побудови початкового розв’язку.
Приклад
Для наступної ТЗЛП
|
5 |
|
3 |
|
6 |
|
7 |
10 |
|
|
|
|
|
|
|
|
|
|
4 |
|
5 |
|
8 |
|
1 |
12 |
|
|
|
|
|
|
|
|
|
|
8 |
|
2 |
|
9 |
|
10 |
13 |
|
|
|
|
|
|
|
|
|
14 |
8 |
6 |
7 |
|
||||
побудуємо розв’язок методом найменшої вартості.
Ітерація 1
|
5 |
|
3 |
|
6 |
|
7 |
10 |
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
5 |
|
8 |
|
1 |
|
6 |
|
|
|
|
|
|
6 |
|
||
|
8 |
|
2 |
|
9 |
|
10 |
13 |
|
|
|
|
|
|
|
|
|
|
|
14 |
8 |
7 |
|
|
|
||||
|
|
|
-- |
|
|
||||
Ітерація 2
|
5 |
|
3 |
|
6 |
|
7 |
10 |
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
5 |
|
8 |
|
1 |
|
6 |
|
|
|
|
|
|
6 |
|
||
|
8 |
|
2 |
|
9 |
|
10 |
|
5 |
|
|
8 |
|
|
|
|
|
||
14 |
|
7 |
|
|
|
||||
|
-- |
|
-- |
|
|
||||
Ітерація 3
|
5 |
|
3 |
|
6 |
|
7 |
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
5 |
|
8 |
|
1 |
|
|
-- |
6 |
|
|
|
|
|
6 |
|
|||
|
8 |
|
2 |
|
9 |
|
10 |
|
5 |
|
|
|
8 |
|
|
|
|
|
|
||
|
|
7 |
|
|
|
|
||||
8 |
-- |
|
-- |
|
|
|
||||
Ітерація 4
|
5 |
|
3 |
|
6 |
|
7 |
|
2 |
|
8 |
|
|
|
|
|
|
|
|
||
|
4 |
|
5 |
|
8 |
|
1 |
|
|
-- |
6 |
|
|
|
|
|
6 |
|
|||
|
8 |
|
2 |
|
9 |
|
10 |
|
5 |
|
|
|
8 |
|
|
|
|
|
|
||
|
|
7 |
|
|
|
|
||||
|
-- |
|
-- |
|
|
|
||||
-- |
|
|
|
|
|
|
||||
Ітерація 5
|
5 |
|
3 |
|
6 |
|
7 |
|
|
-- |
8 |
|
|
|
2 |
|
|
|
|||
|
4 |
|
5 |
|
8 |
|
1 |
|
|
-- |
6 |
|
|
|
|
|
6 |
|
|||
|
8 |
|
2 |
|
9 |
|
10 |
|
5 |
|
|
|
8 |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
||||
|
-- |
5 |
-- |
|
|
|
||||
-- |
|
|
|
|
|
|
||||
Ітерація 6
|
5 |
|
3 |
|
6 |
|
7 |
|
|
-- |
8 |
|
|
|
2 |
|
|
|
|||
|
4 |
|
5 |
|
8 |
|
1 |
|
|
-- |
6 |
|
|
|
|
|
6 |
|
|||
|
8 |
|
2 |
|
9 |
|
10 |
|
|
-- |
|
|
8 |
|
5 |
|
|
|
|||
|
|
|
|
|
|
|
||||
|
-- |
|
-- |
|
|
|
||||
-- |
|
-- |
|
|
|
|
||||
Відповідь
В результаті застосування
методу було заповнено 6=
клітин транспортної таблиці. Отже,
розв’язок, отриманий методом найменшої
вартості:
інші
,
.