ється так званий метод викреслювання, який полягає в наступному.
Якщо в рядку або стовпці таблиці одна зайнята клітина, то вона не може входити до будь-якої цикл, оскільки цикл має дві і тільки дві клітини в кожному стовпці. Отже, можна викреслити всі рядки таблиці, що містять по одній зайнятої клітці, потім викреслити всі стовпці, що містять по одній зайнятої клітці, далі повернутися до рядках і продовжити викреслення рядків і стовпців. Якщо в результаті викреслювання всі рядки і стовпці будуть викреслені, значить, із зайнятих клітин таблиці не можна виділити частину, що утворить цикл, і система відповідних векторів умов є лінійно незалежної, а рішення опорним. Якщо ж після викреслювань залишиться частина клітин, то ці клітини утворюють цикл, система відповідних векторів умов лінійно залежна, а рішення не є опорним.
Метод мінімальної вартості. Даний метод дозволяє побудувати опорне рішення, яке досить близько до оптимального, оскільки використовує матрицю вартостей транспортної завдання, i = 1,2, ..., m; j = 1,2 ..., n. Даний метод складається з ряду однотипних кроків, на кожному з яких заповнюється тільки одна клітина таблиці, відповідна мінімальної вартості, і виключається з розгляду тільки одна рядок (постачальник) або один стовпець (споживач). Чергову клітку, відповідну, заповнюють також. Постачальник виключається з розгляду, якщо його запаси закінчуються. Споживач виключається з розгляду, якщо його запити задоволені повністю. На кожному кроці виключається або один постачальник, або один споживач. При цьому якщо постачальник не виключений, але його запаси рівні нулю, то на тому кроці, коли від нього вимагається поставити вантаж, у відповідну клітину таблиці заноситься базисний нуль і лише потім постачальник виключається з розгляду. Аналогічно поступають із споживачем. p> Приклад 2:
Використовуючи метод мінімальної вартості, побудувати початкову опорне рішення транспортної задачі, доставки ліків з трьох складів у чотири аптеки.
Таблиця 3
В
80
120
160
120
120
1
3
4
2
160
4
5
8
3
200
2
3
6
7
Рішення. Запишемо окремо матрицю вартостей для того, щоб зручніше було вибирати вартості, викреслювати рядки і стовпці:
В
4 січня 3 червня
серед елементів матриці вартостей вибираємо найменшу в...
