Розв'язання задач транспортного типу методом потенціалів

МІНІСТЕРСТВО ОСВІТИ РОСІЙСЬКОЇ ФЕДЕРАЦИИ.

ВОРОНЕЗЬКИЙ ІНСТИТУТ ВИСОКИХ ТЕХНОЛОГИЙ.

Факультет заочно-послевузовского обучения.

КУРСОВА РАБОТА.

По дисципліни: «Методи оптимізації «.

На тему: «Рішення завдань транспортного типу методом потенціалів «.

Воронеж 2003 г.

1. Лінійна транспортна завдання. 3 2. Математична модель транспортної завдання. 4 3. Упорядкування опорного плану. 5 4. Розподільний метод досягнення оптимального плану. 8 5. Рішення транспортної завдання методом потенціалів. 11 Список використаної літератури 16.

1. Лінійна транспортна задача.

Лінійні транспортні завдання становлять особливий клас завдань лінійного програмування. Завдання залежить від знаходженні цього плану перевезень продукції з m складів пункт призначення n який, зажадав б мінімальних витрат. Якщо споживач j отримує одиницю продукції (по прямою дорогою) зі складу і, то виникають витрати Сij. Передбачається, що транспортні витрати пропорційні перевозимому кількості продукції, тобто. перевезення k одиниць продукції викликає витрати k З і j.

Далі, передбачається, что.

[pic] де ai є кількість продукції, яка була складі і, і bj — потреба споживача j.

Замечание.

1. Якщо сума запасів у пунктах відправлення перевищує суму поданих заявок [pic]то кількість продукції, однакову [pic]остается на складах. І тут ми введемо «фіктивного «споживача n +1 з потребою [pic] і між іншим транспортні витрати pi, n+1 рівними 0 всім i.

2. Якщо сума поданих заявок перевищує готівкові запаси [pic]то потреба може бути покрита. Це можна зводити до звичайній транспортної завданню із правильною балансом, якщо запровадити фіктивний пункт відправлення m + 1 з запасом [pic] і вартість перевезень з фіктивного пункту відправлення в усі пункти призначення прийняти рівним нулю.

2. Математична модель транспортної задачи.

[pic].

[pic].

[pic].

[pic].

[pic].

де xij кількість продукції, поставлене зі складу і споживачеві j, а З і j витрати (вартість перевезень зі складу і споживачеві j).

3. Упорядкування опорного плана.

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

Розглянемо найпростіший, так званий спосіб північно-західного кута. Пояснити його найпростіше буде конкретному примере:

Умови транспортної завдання задано транспортної таблицей.

Таблиця № 1.

|ПН | | | | | |Запаси | |ПО |В1 |В2 |В3 |В4 |В5 |аi | |А1 |10 |8 |5 |6 |9 | | | | | | | | |48 | |А2 |6 |7 |8 |6 |5 | | | | | | | | |30 | |А3 |8 |7 |10 |8 |7 | | | | | | | | |27 | |А4 |7 |5 |4 |6 |8 | | | | | | | | |20 | |Заявки |18 |27 |42 |12 |26 |125 | |bj | | | | | | |.

Будемо заповнювати таблицю перевезеннями поступово починаючи з лівого верхньої осередки («північно-західного кута «таблиці). Говоритимемо при цьому так. Пункт В1 подав заявку на 18 одиниць вантажу. Задовольнимо цю заявку рахунок запасу 48, наявного у пункті А1, і запишемо перевезення 18 у клітині (1,1). Після цього заявка пункту В1 задоволена, а пункті А1 залишилося ще 30 одиниць вантажу. Задовольнимо рахунок них заявку пункту В2 (27 одиниць), запишемо 27 у клітині (1,2); решта 3 одиниці пункту А1 призначимо пункту В3. У складі заявки пункту В3 залишилися неудовлетворёнными 39 одиниць. У тому числі 30 кроєм рахунок пункту А2, ніж його запас буде вичерпаний, і ще 9 візьмемо із А3. З 18 одиниць пункту А3 12 виділимо пункту В4; решта 6 одиниць призначимо пункту В5, що зі усіма 20 одиницями пункту А4 покриє його заявку. У цьому розподіл запасів закінчено; кожен пункт призначення отримав вантаж, відповідно до свого заявки. Це виявляється в тому, сума перевезень у кожному рядку дорівнює відповідному запасу, а стовпці - заявці. Отже, нами відразу ж потрапляє складено план перевезень, зрозумілу балансовими умовам. Отримане рішення є опорним рішенням транспортної задачи:

Таблиця № 2.

|ПН | | | | | |Запаси | |ПО |В1 |В2 |В3 |В4 |В5 |аi | |А1 |10 |8 |5 |6 |9 |48 | | |18 |27 |3 | | | | |А2 |6 |7 |8 |6 |5 |30 | | | | |30 | | | | |А3 |8 |7 |10 |8 |7 |27 | | | | |9 |12 |6 | | |А4 |7 |5 |4 |6 |8 |20 | | | | | | |20 | | |Заявки |18 |27 |42 |12 |26 |125 | |bj | | | | | | |.

Складений нами план перевезень, перестав бути оптимальним по вартості, бо за його побудові зовсім не враховували вартість перевезень Сij .

Інший спосіб — спосіб мінімальної вартості по рядку — грунтується на тому, що ми розподіляємо продукцію від пункту Ai над кожній із пунктів Bj, а на той, якого вартість перевезення мінімальна. Якщо цього пункті заявка повністю задоволена, ми прибираємо його з розрахунків й знаходимо мінімальну вартість перевезення які залишилися пунктів Bj. В усьому іншому його схожий із методом північно-західного кута. Через війну, опорний план, складений способом мінімальної вартості по рядку виглядає, так як показано в таблиці № 3.

У цьому методі може й, що вартості перевезень Cij і Cik від пункту Ai до пунктів Bj і Bk рівні. І тут, з економічної точки зору, вигідніше розподілити продукцію у той пункт, у якому заявка більше. Приміром, в рядку 2: C21 = C24, але заявка b1 більше заявки b4, тому 4 одиниці виробленої продукції ми розподілимо у клітину (2,1).

Таблиця № 3.

|ПН | | | | | |Запаси | |ПО |В1 |В2 |В3 |В4 |В5 |аi | |А1 |10 |8 |5 |6 |9 |48 | | | | |42 |6 | | | |А2 |6 |7 |8 |6 |5 |30 | | |4 | | | |26 | | |А3 |8 |7 |10 |8 |7 |27 | | | |27 | | |0 | | |А4 |7 |5 |4 |6 |8 |20 | | |14 | | |6 | | | |Заявки |18 |27 |42 |12 |26 |125 | |bj | | | | | | |.

Спосіб мінімальної вартості по стовпцю аналогічний попередньому способу. Їх відмінність у тому, в другому способі ми розподіляємо продукцію від пунктів Bi до пунктів Aj по мінімальної вартості Cji.

Опорний план, складений способами мінімальних вартостей, зазвичай ближчий оптимального рішенню. Так було в прикладі загальні видатки транспортування за планом, складеного першим способом F0 = 1039, а, по другому F0 = 723.

Клітини таблиці, у яких стоять ненульові перевезення, є засадничими. Їх кількість має рівнятися m + n — 1. Слід зазначити також, що зустрічаються такі ситуації, коли кількість базисних клітин менш як m + n — 1. І тут розподільна завдання називається вырожденной. І треба на одній із вільних клітин поставити кількість перевезень однакову нулю. Приміром, в таблиці № 3: m + n — 1 = 4 + 5 — 1 = 8, а базисних клітин 7, тому у жодну з клітин рядки 3 чи шпальти 2 поставити значення «0». Наприклад у клітину (3,5).

Складаючи план зі способів мінімальних вартостей на відміну від плану за способом північно-західного кута ми враховуємо вартості перевезень Cij, але навряд чи можемо стверджувати, що складений нами план є оптимальным.

4. Розподільний метод досягнення оптимального плана.

Тепер спробуємо поліпшити план, складений способом северозахідного кута. Перенесемо, наприклад, 18 одиниць із клітини (1,1) в клітину (2,1) і ніж порушити балансу перенесём самі 18 одиниць із клітини (2,3) у клітину (1,3). Одержимо новий план. Підрахувавши вартість опорного плану (вона ровняется 1039) і вартість нового плану (вона ровняется 913) неважко переконатися, що вартість нового плану на 126 одиниць менше. Отже, рахунок циклічною перестановки 18 одиниць вантажу лише з клітин на інші ми змогли понизити вартість плана:

Таблиця № 4.

|ПН | | | | | |Запаси | |ПО |В1 |В2 |В3 |В4 |В5 |аi | |А1 |10 |8 |5 |6 |9 |48 | | | |27 |21 | | | | |А2 |6 |7 |8 |6 |5 |30 | | |18 | |12 | | | | |А3 |8 |7 |10 |8 |7 |27 | | | | |9 |12 |6 | | |А4 |7 |5 |4 |6 |8 |20 | | | | | | |20 | | |Заявки |18 |27 |42 |12 |26 |125 | |bj | | | | | | |.

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

Є кілька варіантів цикла:

1.) 2.).

3.).

Неважко переконатися, кожен цикл має чётное число вершин і отже, чётное число ланок (стрілок). Домовимося відзначати знаком + ті вершини циклу, у яких перевезення слід збільшити, а знаком —, ті вершини, у яких перевезення необхідно зменшити. Цикл з зазначеними вершинами називатимемо зазначеним. Перенести якесь кількість одиниць вантажу по зазначеного циклу, це що означає збільшити перевезення, які у позитивних вершинах циклу, цю кількість одиниць, а перевезення, які у негативних вершинах зменшити на таку саму кількість. Очевидно, при перенесення будь-якого числа одиниць по циклу рівновагу між запасами і заявками не змінюється: як раніше сума перевезень у кожному рядку дорівнює запасам цього рядка, а сума перевезень у кожному стовпці - заявці цього шпальти. Отже, незалежно від циклічний перенесення, полишає перевезення неотрицательными припустимий план залишається допустимим. Вартість ж плану у своїй не може змінюватися: збільшуватися чи зменшаться. Назвемо ціною циклу зростання вартості перевезень при переміщенні однієї одиниці вантажу по зазначеного циклу. Вочевидь, ціна циклу рівна алгебраїчній сумі вартостей, котрі стоять у вершинах циклу, причому які у позитивних вершинах беруться зі знаком +, а негативних зі знаком -. Означимо ціну циклу через (. При переміщенні однієї одиниці вантажу по циклу вартість перевезень поповнюється величину (. При переміщенні у ній k одиниць вантажу вартість перевезень збільшитися на k (. Вочевидь, підвищення плану можна буде переміщати перевезення лише за тими циклам, ціна яких негативною. Щоразу, коли вдається зробити таке переміщення, вартість плану зменшується на відповідну величину k (. Оскільки перевезення неможливо знайти негативними, ми користуватися тільки такими циклами, негативні вершини яких у базисних клітинах таблиці, де стоять позитивні перевезення. Якщо циклів із від'ємною вартістю таблиці большє нє залишилося, це, подальше поліпшення плану неможливо, тобто оптимальний план достигнут.

Метод послідовного поліпшення плану перевезень і полягає у тому, що у таблиці знаходяться цикли із від'ємною ціною, по ним переміщаються перевезення, і план поліпшується до того часу, поки циклів із від'ємною ціною не залишиться. При поліпшенні плану циклічними перенесеннями, зазвичай, користуються прийомом, запозиченим з симплекс-метода: при кожен крок (циклі) заміняють одну вільну зміну на базисну, тобто заповнюють одну вільну клітку та замість того звільняють жодну з базисних клітин. У цьому загальне число базисних клітин залишається незмінним і рівним m + n — 1. Цей метод зручний тим, що з нього легше знаходити підходящі циклы.

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

Применённый вище метод відшукання оптимального рішення транспортної завдання називається распределённым; він полягає у безпосередньому знаходженні вільних клітин із негативною ціною циклу й у переміщенні перевезень у цій циклу.

Розподільний метод рішення транспортної завдання, з яких ми познайомилися, має одним недоліком: треба відшуковувати цикли для всіх вільних клітин та знаходити їхні ціни. З цієї трудоёмкой роботи нас рятує спеціальний метод рішення транспортної завдання, що називається методом потенциалов.

5. Рішення транспортної завдання методом потенциалов.

Цей метод дозволяє автоматично виділяти цикли з негативною ціною та імідж визначатимуть їх цены.

Нехай є транспортна завдання з балансовими условиями.

[pic].

[pic].

[pic].

[pic].

[pic].

Вартість перевезення одиниці вантажу з Ai в Bj дорівнює З ij; таблиця вартостей задана. Потрібна знайти план перевезень xij, який задовольняв б балансовими умовам і навіть вартість всіх перевезень балу минимальна.

Ідея методу потенціалів на вирішення транспортної завдання зводитися ось до чого. Уявімо що з пунктів відправлення Ai вносить перевезення одиниці вантажу (усе одно куди) певну суму (і; своєю чергою кожен із пунктів призначення Bj також вносить перевезення вантажу (будь-куди) суму (j. Ці платежі передаються деякому третій особі («перевізникові»). Означимо (і + (j = (ij (i=1.m ;j=1.n) і називати величину (ij «псевдостоимостью» перевезення одиниці вантажу з Ai в Bj. Зауважимо, що платежі (і і (j необов’язково мали бути зацікавленими позитивними; не виключено, що «перевізник» сам платить тому чи іншому пункту якусь премію перевезення. Також потрібно відзначити, що сумарна псевдостоимость будь-якого припустимого плану перевезень при заданих платежах ((і і (j) сама й той самий і південь від плану до плану не меняется.

До цього часу ми пов’язували платежі ((і і (j) і псевдостоимости (ij зі справжніми вартостями перевезень З ij. Нині ми встановимо з-поміж них зв’язок. Припустимо, що план xij невырожденный (число базисних клітин на таблиці перевезень рівно m + n -1). Всім цих клітин xij >0. Визначимо платежі ((і і (j) те щоб переважають у всіх базисних клітинах псевдостоимости були рівні стоимостям:

(ij = (і + (j = сij, при xij >0.

Що ж до вільних клітин (де xij = 0), то них співвідношення між псевдостоимостями і вартостями то, можливо, яке угодно.

Виявляється співвідношення між псевдостоимостями і вартостями в вільних клітинах показує, чи є план оптимальним або він то, можливо поліпшився. Існує спеціальна теорема: Якщо всіх базисних клітин плану xij > 0,.

(і + (j = (ij= сij, а всіх вільних клітин xij =0,.

(і + (j = (ij (сij, то план є оптимальним й жодними способами поліпшився не може. Неважко показати, що це теорема справедлива також і вырожденного плану, і з базисних змінних рівні нулю. План у якого властивістю :

(ij= сij (всім базисних клітин) (1).

(ij (сij (всім вільних клітин) (2) називається потенційним планом, а відповідні йому платежі ((і і (j) — потенціалами пунктів Ai і Bj (i=1,…, m; j=1,…, n). Користуючись цієї термінологією вищезгадану теорему можна сформулювати так:

Кожен потенційний план є оптимальным.

Отже, на вирішення транспортної завдання ми мусимо одне — побудувати потенційний план. Виявляється може бути побудувати методом послідовних наближень, переймаючись спочатку якийсь довільній системою платежів, задовольняє умові (1). Причому у кожної базисної клітині вийти сума платежів, рівна вартості перевезень у цій клітині; потім, поліпшуючи план слід одночасно змінювати систему платежів. Тож вони наближаються до потенциалам. При поліпшенні плану нам допомагає таке властивість платежів і псевдостоимостей: як і вона була система платежів ((і і (j) яка задовольнить умові (1), кожної вільної клітини ціна циклу пересчёта дорівнює різниці між вартістю і псевдостоимостью у цій клітині: (i, j= сi, j — (i, j.

Отже, при користуванні методом потенціалів на вирішення транспортної завдання відпадає найбільш трудомісткий елемент розподільного методу: пошуки циклів із від'ємною ценой.

Процедура побудови потенційного (оптимального) плану полягає в следующем.

Як першого наближення оптимального плану береться будь-який припустимий план (наприклад, побудований способом мінімальної вартості по рядку). У цьому плані m + n — 1 базисних клітин, де m — число рядків, n — число шпальт транспортної таблиці. І тому плану можна визначити платежі ((і і (j), те щоб у кожному базисної клітині виконувалося умова :

(і + (j = сij (3).

Рівнянь (3) всього m + n — 1, а число невідомих одно m + n. Отже, з цих невідомих можна поставити довільно (наприклад, рівної нулю). Після цього з m + n — 1 рівнянь (3) можна знайти інші платежі (і, (j, а, по ним обчислити псевдостоимости, (i, j= (і + (j кожної вільної клетки.

Таблиця № 5.

|ПН | | | | | | | |ПО |В1 |В2 |В3 |В4 |В5 |(і | |А1 |10 |8 |5 |6 |9 |(1= 0 | | |(= 7 |(= 6 |42 |6 |(= 6 | | |А2 |6 |7 |8 |6 |5 |(2= -1 | | |4 |(= 5 |(= 4 |(= 5 |26 | | |А3 |8 |7 |10 |8 |7 |(3= 1 | | |(= 8 |27 |(= 6 |(= 7 |0 | | |А4 |7 |5 |4 |6 |8 |(4= 0 | | |14 |(= 6 |(= 5 |6 |(= 6 | | | |(1= 7 |(2= 6 |(3= 5 |(4= 6 |(5= 6 | | |(j | | | | | | |.

(4 = 0, (.

(4 = 6, оскільки (4 + (4 = С44 = 6, (.

(1= 0, оскільки (1 + (4 = С14 = 6, (.

(3 = 5, оскільки (1 + (3 = С13 = 5, (.

(1 = 7, оскільки (4 + (1 = С41 = 7, (.

(2= -1, оскільки (2 + (1 = С21 = 6, (.

(5 = 6, оскільки (2 + (5 = С25 = 5, (.

(3= 1, оскільки (3 + (5 = С35 = 7, (.

(2 = 6, оскільки (3 + (2 = С25 = 7.

Якщо виявилося, всі ці псевдостоимости вищими за стоимостей.

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

У таблиці № 5 ми маємо у двох клітинах (ij? сij, тепер можна побудувати цикл у кожній із цих двох клітин. Вигідніше всього будувати цикл в тієї клітині, у якій різницю (ij — сij максимальна. У нашому випадку в обох клітинах різницю однакова (дорівнює 1), тому, для побудови циклу виберемо, наприклад, клітину (4,2):

Таблиця № 6.

|ПН | | | | | | | |ПО |В1 |В2 |В3 |В4 |В5 |(і | |А1 |10 |8 |5 |6 |9 |0 | | | | |42 |6 | | | |А2 |6 |7 |8 |6 |5 |-1 | | |+ | | | |- | | | |4 | | | |26 | | |А3 |8 |7 |10 |8 |7 |1 | | | |- | | |+ | | | | |27 | | |0 | | |А4 |7 |5 |4 |6 |8 |0 | | |- |+ | |6 | | | | |14 |? | | | | | |(j | | | | | | | | |7 |6 |5 |6 |6 | |.

Тепер переміщати по циклу число 14, бо вона є мінімальним з чисел, котрі стоять у клітинах, помічених знаком —. При переміщенні ми вичитати 14 з клітин з знаком — і додавати до клітинам зі знаком + .

Після цього потрібні підрахувати потенціали (і і (j та циклу розрахунків повторяется.

Отже, ми дійшли наступному алгоритму рішення транспортної завдання методом потенциалов.

1. Взяти будь-який опорний план перевезень, у якому відзначені m + n — 1 базисних клітин (інші клітини свободные).

2. Визначити при цьому плану платежі ((і і (j) з умови, щоб у будь-якій базисної клітині псевдостоимости були рівні вартостям. Одне з платежів можна призначити довільно, наприклад, покласти рівним нулю.

3. Підрахувати псевдостоимости (i, j = (і + (j всім вільних клітин. Якщо з’ясується, що вони становить вартостей, то план оптимален.

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

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

Так було в прикладі після 2 циклів розрахунків одержимо оптимальний план. У цьому вартість всієї перевезення змінювалася так: F0 = 723, F1 = 709, F2 = Fmin = 703.

Слід зазначити як і, що оптимальний план може мати і той вид, та його вартість залишиться той самий Fmin = 703.

Список використаної литературы.

1. Єрьомін І.І., Астаф'єв М. М. Введення ЄІАС у теорію лінійного і опуклого програмування М.; Наука, 1976 г.

2. Кишень В. Г. Математичне програмування. — М.; Наука, 1986 г.

3. Моїсєєв М.М., Іванов Ю.П., Столярова О. М. Методи оптимізації. — М.; Наука, 1978 г.

4. Іванов Ю.П., Лотів А.В. Математичні моделі у економіці. — М.; Наука, 1979 г.

5. Бронштейн І.Н., Семендяев К. А. Довідник з математики. — М.; Наука, 1986 г.