Мат_методи дослідження операційі. Навчальний посібник Київ 2008 Зміст Анотація 3 План курсу 4 Лекція Вступ. Цілі, критерії, обмеження. 4
 Скачать 0.81 Mb.
|
Лекція 4. Транспортна задача: алгоритм вирішення.Приклад. На території міста є три телефонні станції: А, В, С. Є три нових райони забудови, що мають потребу в телефонізації. Незадіяна ємність: станція А – 5 тис. станція В – 3 тис. станція С – 4 тис. Потреби нових районів у телефонних номерах: 1-й – 3 тис. 2-й – 4 тис. 3-й – 5 тис. Відома вартість прокладки і будівництва лінійних споруджень від діючих АТС до нових районів. Потрібно знайти такий розподіл ємності АТС між новими районами, щоб сумарні витрати на прокладку лінійних споруджень були мінімальними.  .Рішення розбивається на 2 етапи. 1-й етап: здійснюється пошук припустимого рішення (первинного базисного рішення, опорного рішення, опорного плану); 2-й етап: знаходиться оптимальне рішення (якщо воно існує). 1-й етап. Пошук первинного базисного рішення. Існує два методи знаходження припустимого рішення (первинного базисного рішення).
Пошук рішення починається з визначення змінної хА1 лівого стовпця верхнього рядка («північно-західний кут»), якій надається максимально можливе значення, чи іншими словами, максимально можливе постачання в клітку (А, 1): хА1= min{5тис;3тис}=3тис. Після цього попит 1-го споживача (району) буде цілком задоволений, у результаті чого перший стовпець таблиці постачань випаде з наступного розгляду. У таблиці постачань знайдемо новий «північно-західний кут» - клітку (А, 2) і надамо їй максимально можливого значення. З огляду на те, що А-й постачальник (АТС) вже віддав 3тис номерів, то в нього залишилося тільки 2тис=5тис-3тис. Одержуємо хА2 = min{5тис; 3тис}=2тис. Після цього потужність першого постачальника (АТС) цілком реалізована і з розгляду випадає перший рядок таблиці постачань. У таблиці, що залишилася, знову знаходимо «північно-західний кут» і т.д. У результаті одержуємо такий вихідний розподіл постачань.
Істотним недоліком методу «північно-західного кута» є те, що він не враховує значень коефіцієнтів витрат. W = 3т*4 + 2т*7 + 2т*15 + 1т*11 + 4т*10 = 107 т.
Цей метод є модифікацією методу «північно-західного кута» і дозволяє враховувати витрати (коефіцієнт витрат) на постачання при відшуканні опорного рішення. Це дає можливість одержати рішення, як правило, більш близьке до оптимального. На кожному кроці максимально можливе постачання поміщають у клітку з найменшим коефіцієнтом витрат, тобто з усіх витрат на постачання вибираємо найменші. Розподілимо ємність АТС А між районами з найменшими витратами відповідно до потреб цих районів, починаючи з найменших витрат. Це (А, 1) і (А,3). Повторюємо пошук і заповнення кліток, що залишилися, аналогічним чином. Одержимо:
W = 3т*4 + 2т*6 + 3т*11 + 4т*7 = 85. Таким чином. використання методу найменшого елемента дозволило одержати рішення більш близьке до оптимального з меншою вартістю. 2-й етап. Пошук оптимального рішення (поліпшення планів перевезень). Цикл перерахунку. На другому етапі перевіряється - чи є базисне рішення оптимальним. Для цього спочатку потрібно виразити цільову функцію W (3.1) задачі через неосновні (вільні) змінні. Мінімум цільової функції, тобто рішення транспортної задачі, отримується тоді, коли всі коефіцієнти при вільних (неосновних) змінних у виразі для цільової функції W (3.1) через вільні перемінні невід’ємні. У транспортній задачі змінна хij ототожнюється з вмістом відповідної клітки (i, j) таблиці постачань. Позначимо bij коефіцієнт біля вільної змінної хij у виразі для лінійної функції цілі W (3.1) через вільні змінні; bij називається оцінкою вільної клітки (i, j). При даному базисному розподілі постачань клітка (i, j) - вільна (змінна хij - вільна), bij - оцінка клітки (i, j) чи коефіцієнт у виразі лінійної функції W(3.1) через вільні змінні: W = W0 + bij хij + … (3.4) де трикрапкою позначені доданки, що відповідають вільним змінним, відмінним від хij, W0 – сумарні витрати на даний розподіл постачань. Тоді з (3.4) випливає, що оцінка bij вільної (i, j) клітки дорівнює зміні сумарних витрат ΔW на постачання при переведенні в клітку (i, j) одиничного постачання (збільшення змінної хij від 0 до 1), тобто: bij = ΔW = Wп – Wн, де Wн - первинні витрати на постачання; Wп - витрати на постачання після перерозподілу. Передбачається, що у всіх вільних клітках відмінних від клітки (i, j), постачання залишиться нульовим. Очевидно, що ΔW > 0 якщо bij > 0; ΔW < 0 якщо bij < 0. Останнє непряме визначення оцінки вільної клітки називають економічним змістом оцінки вільної клітки. Знайдемо оцінку вільної клітки А3. Для цього дамо в клітку А3 одиничне постачання. При цьому буде потрібно змінити постачання в заповнених клітках так, щоб зберігся баланс по рядках і стовпцям (передбачається, що у всіх вільних клітках відмінних від клітки А3, постачання залишиться нульовим). Так, щоб 3-й район як і раніше одержав 5 тис. номерів, постачання в клітці В3 варто зменшити на 1тис. Для того, щоб АТС В як і раніше поставила 3тис. номерів, постачання в клітці В2 збільшуємо на 1тис. 2-му району необхідно тільки 4тис. номерів, тому постачання в клітці А2 варто зменшити на 1тис. З'єднавши один по одному зазначені клітки A3 à B3 à B2 à A2 à A3 одержимо замкнутий контур (цикл). Циклом перерахунку базисної транспортної таблиці називається група кліток цієї таблиці, з'єднаних замкнутою ламаною лінією, що проходить через клітки зі змінюваним постачанням і в кожній клітці робить поворот на +900. Одна з вершин лежить у вільній клітці, інші - у заповнених. Кожен цикл має парне число вершин. Позначимо знаком «+» ті вершини, у яких постачання (перевезення) збільшуються, а знаком « - » ті, у яких вони зменшуються. Позначеним циклом перерахунку називається цикл, у вершинах якого розставлені знаки «+» і «-», так, що у вільній клітці стоїть знак «+», а сусідні вершини мають протилежні знаки. При переміщенні ресурсу по циклу перерахунку знаки у вершинах чергуються тому, що не повинна порушуватися умова балансу постачань і по рядках і по стовпцях. Ціною (оцінкою) циклу називають алгебраїчну суму коефіцієнтів витрат, що стоять у вершинах циклу, узятих з відповідними знаками. Ця величина відбиває зміну вартості постачань при переміщенні одиниці ресурсу по обраному циклу перерахунку. Так, якщо після перерозподілу маємо bij=ΔW з від’ємною оцінкою, то вихідний базовий розподіл – не оптимальний і його можна поліпшити. Якщо ціна циклу додатня величина, то поліпшити рішення за рахунок цього циклу перерахунку не вдасться. З іншого боку вартість перевезень зросте, якщо інакше перерозподілити ресурси по цьому циклу. Якщо ціна дорівнює 0, то вартість постачань по цьому циклу не змінюється при переміщенні. В отриманій базовій транспортній таблиці необхідно побудувати зазначені цикли перерахунку для усіх вільних кліток. У вихідній вільній клітці розміщаємо одну з вершин і приписуємо «+». Всі інші вершини перерахунку повинні спиратися на зайняті клітки.
А3: A3 à B3 à B2 à A2 à A3 bA3 = 6-11+15-7 = 3 B1: В1 à А1 à А2 à В2 à В1 bВ1 = 12-4+7-15 = 0 C1: С1 à С3 à В3 à В2 à А2 à A1 à C1 bС1 = 13-10+11-15+7-4 = 2 C2: С2 à В2 à В3 à C3 à C2 bС2 = 7-15+11-10 = -7 Для поліпшення рішення в розглянутій задачі можна виконати єдиний цикл перерахунку з від’ємною ціною bС2:
Оптимізація рішення транспортної задачі (оптимізація розподілу постачань). При переміщенні по циклу k одиниць ресурсу зміна вартості складе ΔW=k´bij. При цьому значення ресурсу в клітках зі знаком «+» збільшиться на k, а в клітках зі знаком «-» - зменшиться на k. Значення k вибирається серед кліток циклу, що мають знак «-». Крім того, воно має мінімальне значення серед цих кліток, отже k = min{2,4} = 2, тобто це буде клітка B2. Для обнулення постачання в цій клітці по циклу слід передати 2 одиниці ресурсу. Постачання, передане по циклу, визначається як мінімум серед постачань у клітках циклу зі знаком «-». Після цього клітка В3 вважається заповненою, а клітка В2 - вільною. Одержали новий базисний розподіл постачань:
Зміна витрат на новому розподілі складе ΔW(1) = -7 ´ 2 = -14. Загальний обсяг витрат при новому базисному розподілі складе: W(1) = W(0) + ΔW(1) = 107-14 = 93. Таким чином, нове базисне розподілення ближче до оптимального. Розглянемо новий базисний розподіл на предмет його оптимальності. Для цього побудуємо цикли перерахунку для вільних кліток і знайдемо оцінки вільних кліток розподілу постачань, як на попередній ітерації (кроці). A3: bA3 = 6-10+7-7 = - 4 по циклу A3àC3àC2à А2 à A3. B1: bB1 = 12-4+7-7+10-11 = 7 пo циклу B1àA1àA2àC2àC3àВ3àВ1. В2: bB2 = 15-7+10-11 = 7 по циклу B2àC2àC3àB3àB2. C1: bC1 = 13-4+7-7 = 9 по циклу C1àA1àA2àC2àC1. Оскільки є вільні клітки з від’ємною оцінкою (b3 = - 4), то оптимальне рішення ще не знайдене. Для одержання чергового базисного розподілу використовуємо цикл перерахунку по A3. При цьому k = min{2,2} = 2; ΔW(2) = b3 x k(2) = - 4 x 2 = - 8; W(2)= W(1) + ΔW(2) = 93 - 8 = 85. Дослідження отриманого базисного розподілу на оптимальність покаже, що в ньому відсутні клітки з від’мною оцінкою. Таким чином, даний розподіл постачань буде оптимальним. У розглянутій задачі отримане оптимальне рішення збігається з первинним базисним рішенням, отриманим методом найменшого елемента. Як видно, при виконанні кожного чергового циклу перерахунку вільна клітка стає заповненою, а одна з заповнених – вільною.
Загальний алгоритм рішення транспортної задачі може бути сформульований у такому вигляді:
Даний алгоритм рішення відповідає закритій транспортній задачі - коли сумарний попит споживачів збігається із сумарною потужністю постачальників. Відкрита транспортна задача припускає, що сумарна потужність постачальників менше сумарного попиту споживачів, і зводиться до рішення закритої транспортний шляхом уведення фіктивного постачальника. Тема 4. |
5-
-