4.Методи знаходження опорного плану транспортної задачі (метод північно-західного кута, метод мінімального елементу, метод апроксимації Фогеля)

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

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

Метод "мінімального елемента" ("найменшої вартості")

При реалізації" цього методу перехід від однієї компоненти плану (клітини, де вона записана) до іншої виконується не лише з урахуванням наявного запасу вантажу в пункті постачання та обсягу запиту пункту призначення, але й з оцінкою тарифу. Існує кілька різновидів цього методу в залежності від того, як вибирається розташування наступної компоненти шуканого плану перевезення: клітина з найменшим тарифом по рядку, або по стовпцю, або на множині усіх незаповнених клітин розподільчої таблиці. Обчислення компонент опорного плану (формування клітин розподільчої таблиці) починається з клітини (s, р), яка має найменший тариф; якщо таких клітин декілька, то з будь-якої з них. У клітину (s, р) з найменшим тарифом записуємо найменше з чисел а_s та b_p. У подальшому виключаємо з розгляду або стовпець, якщо запит р-го пункту призначення виконано, або рядок, якщо запаси s-го пункту постачання вичерпано. Може трапитися випадок, коли необхідно водночас вилучити відповідно і стовпець, і рядок, якщо в пункті постачання вичерпано запас і виконано запит у пункт призначення. Потім серед незаповнених клітин розподільчої таблиці знову вибирають клітину з найменшим тарифом і обчислюють відповідну компоненту плану за описаним раніше алгоритмом. Процес розподілу запасів (виконання запитів) продовжують до тих пір, поки всі запаси не будуть розподілені, а запити виконані, бо розглядаємо збалансовану ТЗ.

Метод «Пн-Зх» кута.

Назва методу обумовл. порядком заповнення клітин розподільчої табл., починаючи з лівої верхньої, або з правої нижньої клітини

6. Розв'язати і дати графічну інтерпритацію гри

=

=2 - стратегія максиміну, нижня ціна гри

=

= 2 - стратегія мінмаксу, верхня ціна гри

Геометрична інтерпретація гри 2*2:

А1 x=0, F2 x=1. Всі внутрішні точки відрізка (0,1) – це мішані стратегій гравця.

Сідлова точка – (А1, В1)=2, так як то маємо оптимальний розв’язок гри.

Ціна гри (А1, В1)=2

Білет №25