тачальник і споживач, то в клітку, відповідну даному методу, ставиться 0-поставка;
б) метод мінімального елемента: заповнення клітин здійснюється за принципом: "найдешевша перевезення здійснюється першої". Вибирається клітка з мінімальним тарифом і заповнюється максимально можливим числом, при цьому вичерпуються або запаси, або потреби (викреслюється рядок або стовпець), вибирається наступна клітка з мінімальним тарифом і т.д. Якщо на якомусь кроці викреслюються одночасно постачальник і споживач, те ставиться 0-поставка в цьому рядку або стовпці в клітку з мінімальним тарифом;
в) метод апроксимації Фогеля: у всіх рядках і стовпцях знайти різниці між двома мінімальними тарифами, записати їх, відповідно, праворуч і внизу таблиці. Серед знайдених різниць вибирають максимальну. У рядку (або стовпці), якій відповідає дана різниця, заповнюють клітку з мінімальним тарифом. Якщо максимальних різниць кілька однакових, вибирають ту, якій відповідає мінімальний тариф. Якщо мінімальний тариф однаковий для декількох клітин в рядку (стовпці), то заповнюють ту, яка стоїть у стовпці (рядку), що має найбільшу різницю між двома мінімальними тарифами. p align="justify"> Серед отриманих опорних рішень вибирають план з мінімальною вартістю перевезень і перевіряють його на оптимальність:
1) обчислюють потенціали постачальників і споживачів з умови для всіх зайнятих клітин (за умови);
) визначають оцінки всіх вільних клітин.
Якщо все, то план є оптимальним (наявність рівних 0 оцінок свідчить про неоднозначність оптимального плану). Якщо існують, то побудований план не оптимальний. Для його поліпшення серед всіх вибирають максимальне і для відповідної вільної клітки будують цикл перерахунку:
1) цикл зображують у таблиці у вигляді замкнутої ламаної лінії. У будь зайнятої клітці циклу можливий поворот лінії на 90 0 ;
) відзначають вершини циклу перерахунку (там, де лінія повертає) послідовно знаками "+" і "-", починаючи з "+" у вихідній клітці. Серед поставок, що стоять в "-" клітинах, визначають мінімальну. До значенням, яке стоїть в "+" клітинах, додають цю поставку, а з значень, що стоять в "-" клітинах, її віднімають;
) по цьому циклу перерозподіляються обсяги перевезень. Перевезення завантажується в обрану вільну клітину і звільняється одна із зайнятих клітин, виходить нове опорне рішення, яке потрібно перевірити на оптимальність. br/>
Рішення транспортної задачі методом диференціальних рент
Алгоритм вирішення транспортної задачі методом диференціальних рент
1) У кожному стовпці відзначити клітку з мінімальним тарифом.
) У ці відмічені клітини максимально розподілити вантаж. Спочатку в клітини, єдині відмічені в рядку і стовпці, потім єдині в стовпці або в рядку з мінімальними тарифами.
) Необхідно отримати оцінки постачальників:
а) якщо постачальник не всі вивіз, то його оцінка В«+ nВ», де n - кількість залишився вантажу у даного постачальника;
б) якщо всі запаси вичерпані, а потреби споживачів не задоволені з урахуванням розподілу по всьому стовпцю, то оцінка постачальника В«-В», де - кількість вантажу, необхідного споживачам у зазначених стовпцях цього рядка, з урахуванням того вантажу, який, можливо , отримав споживач від інших постачальників. Потреби споживача, якому не вистачило товару, при оцінці постачальників враховуються один раз;
в) якщо всі запаси постачальника вичерпані і в зазначених клітинах стовпців споживач задоволений з урахуванням усього стовпця, то оцінка В«0В». Знак нуля: якщо зазначена клітина в рядку пов'язана в стовпці із зазначеною клітиною тільки в негативній рядку, то знак біля нуля В«-В». В інших випадках знак В«+В». p>) Для кожного стовпця знайти ренту: різницю між зазначеним тарифом в В«негативнійВ» рядку і мінімальним тарифом в В«позитивнійВ» рядку.
) Вибрати мінімальну не нульовий різниця, яка називається проміжної рентою.
) Проміжна рента додається до тарифів в негативних рядках. Після чого скласти нову таблицю із зміненими тарифами і перейти до пункту 1 даного алгоритму. Якщо всі оцінки рівні 0, то знайдено оптимальне рішення. p> Зауваження:
) Сума всіх оцінок у кожній таблиці повинна дорівнювати 0.
) При підрахунку загальної вартості перевезення використовувати вихідні тарифи, а не ті, які вийшли в останній таблиці.
Рішення транспортної задачі з додатковими обмеженнями
Якщо дані додаткові обмеження в транспортній задачі
В
то в таблиці дані зміняться
а) якщо, то
б) якщо, т...
