кщо серед чисел немає позитивних, то умови теореми виконані, і план є оптимальним. Якщо існує> 0, то побудований план не оптимальний, і його слід поліпшити. p>. Алгоритм поліпшення плану:
1) серед усіх> 0 вибирають максимальне;
2) для відповідної клітини будують цикл перерахунку;
3) позначають вершини циклу перерахунку послідовно знаками "+" і "-", починаючи з "+" у вихідній клітці;
4) серед чисел, що стоять в клітинах, позначених "-", визначають мінімальне;
5) до значень, що стоять в "+"-клітинах, додають це мінімальне число, а з значень, що стоять в "-"-клітинах, це число віднімають.
ВИЗНАЧЕННЯ 5 . Циклом перерахунку називається ламана лінія, вершини якої розташовані в зайнятих клітинах, а ланки - уздовж рядків і стовпців, причому в кожній вершині циклу може бути тільки дві ланки. p>. Змінений таким чином план знову перевіряють на оптимальність, тобто перехід до п. 2.
3. Метод диференціальних рент
На відміну від методу потенціалів, для якого спочатку будувався опорний план, а потім він послідовно поліпшувався, при вирішенні задачі методом диференціальних рент відразу найкращим чином розподіляють частина продукції між споживачами і на подальших ітераціях поступово зменшують загальну величину нерозподілених поставок.
Для визначення вирішення транспортної задачі методом диференціальних рент використовують наступний алгоритм:
. У кожному стовпці визначають мінімальний тариф і виділяють сответствующій-щую клітку. p> 2. Виділені клітини заповнюють максимально можливими числами. p> 3. Т.к. в загальному випадку це розподіл не задовольняє всіх споживачам-лий, щоб на наступних кроках скорочувати величину незадоволених потреб, необхідно оцінити постачальників.
ВИЗНАЧЕННЯ 6 . Рядки, відповідні постачальникам, запаси яких вичерпані, а потреби виділених споживачів не задоволені, є негативними. p> ВИЗНАЧЕННЯ 7. Рядки, відповідні постачальникам, запаси яких не вичерпані повністю, є позитивними.
ВИЗНАЧЕННЯ 8. Рядки, відповідні постачальникам, запаси яких вичерпані, а потреби виділених споживачів задоволені, мають нульову оцінку. При цьому, якщо друга заповнена клітина, що стоїть у стовпці, пов'язаному з даною рядком ще однієї заповненої кліткою, розташована в позитивній рядку, даний рядок з нульовою оцінкою вважається позитивною. В іншому випадку - негативною. p> 4. Для кожного стовпця, що має виділений тариф в негативній рядку, знаходять різниці між виділеним тарифом і найближчим до нього за величиною тарифом, яке стоїть в позитивній рядку. p> 5. Серед отриманих різниць визначають мінімальну. Це число називають проміжної рентою. p> 6. Будують нову таблицю, при цьому тарифи, які стоять в позитивних рядках, переписуються без зміни, а тарифи, що стоять в негативних рядках, збільшуються на величину проміжної ренти. p> 7. Переходять до п.1. p> ЗАУВАЖЕННЯ: а) якщо в рядку або стовпці виявляється більше однієї виділеної клітини, то заповнюють, в першу чергу, ті виділені клітини, які є єдиними в стовпці або строке;
б) якщо вдається розподілити всі запаси, то отримують оптимальний план транспортної задачі.
4. Додаткові обмеження транспортної задачі
1. Заборонені маршрути.
Якщо з яких-небудь причин неможливо постачати продукцію з п. Аi у п. В j, припускають тариф цього шляху як завгодно великою величиною М, сij = М, і вирішують завдання звичайним способом.
2. Обов'язкові поставки.
а) Якщо необхідно з п. Аi перевезти в п. В j певну кількість продукції dij, відповідну клітку заповнюють відразу числом dij, а надалі вирішують завдання, вважаючи заповнену клітку вільною, але з тарифом, сij = М, рівним дуже великим числу, а запаси і потреби зменшують на величину dij.
б) Якщо необхідно з п. Аi у п. В j перевезти не менш певної кількості продукції dij, то вважають запаси і потреби менше на величину dij, це кількість dij вважають перевезених за маршрутом Аi В j, і вирішують задачу далі звичайним способом.
в) Якщо необхідно перевезти з п. Аi у п. В j не більше певної кількості продукції dij, вводять додатковий пункт призначення з потребою, яка дорівнює (- dij), потреба у п. В j роблять рівній dij. Тарифи на перевезення в додатковий пункт призначення дорівнюють тарифам п. В j, крім i-того рядка, тариф в якій буде дорівнює як завгодно великому числу М. Вирішують завдання звичайним чином, а при запису відповіді об'єднують основного і додаткового споживача (складають вміст стовпців).
Лекція 14, 15
Метод динамічного програмування
Запитання:
1. Основні поняття. Загальна постановка задачі ДП. p align="justify">. Принцип оптимальності. Функціональні рівняння Беллмана. p align="justify">. Задач...
