Транспортне завдання

Юридичний техникум.

Розглянуто і схвалено ПЦК р. Кропоткіна программирования.

Голова ПЦК.

Покалицына О.В.

План читання лекцій з навчальної дисциплине.

«Математичні методи» Розділ № 2. Лінійне програмування. Тема № 2.5. Транспортна задача.

Місце проведення: аудиторія. Література: 1. Венцель Е. С. Дослідження операцій. Завдань, принципи, методологія. — М.: Наука, 1980. 2. Шелобаев С.І. Математичні методи лікування й моделі у економіці, фінансах, бізнесі. — М.:ЮНИТИДАНА, 2001.

Навчальні і питання розрахунок часу |№п/п |Навчальні питання |Час, мин|Методические | | | | |вказівки | |1. |Постановка транспортної завдання. | | | |2. |Математична модель транспортної | | | |3. |завдання. | | | | |Методи рішення транспортної завдання. | | |.

Вступна частина. Організаційний момент. План заняття. Найвища вимога. Більшість. 1. Постановка транспортної задачи.

Важливим приватним випадком завдання лінійного програмування є транспортна завдання. Постановка завдання: Нехай є m постачальників і n споживачів. Потужність постачальників і спросы споживачів, а як і видатки перевезення вантажу для кожної пари «постачальник — споживач» задано таблицею. |A2 |С21|С22| |С2j| |С2n|a2 | |… |… |… | |… | |… | | |Ai |Сij|Сij| |Сij| |Сin|ai | |… |… |… | |… | |… | | |Am |Cm1|Cm2| |Cmj| |Cmn|am | |Попит споживачів |b1 |b2 | |bj | |bn | |.

Знайти обсяги перевезень кожної пари «постачальник — споживач» так, щоб: потужності всіх постачальників були реалізовані; спросы всіх споживачів задовольнили; сумарні видатки перевезення було б максимальны.

Особливості математичну модель транспортної завдання: система обмежень є система рівнянь, тобто завдання ЛЗ в канонічному вигляді; коефіцієнти при невідомих системи обмежень рівні одиниці чи нулю; кожна змінна входить до системи обмежень двічі: раз на систему обмежень поставок, вдруге — до системи обмежень попиту. 2. Математична модель транспортної завдання. Нехай хij — кількість вантажу, перевезеного з i-го в j-й пункт. Цільова функція: [pic] Система обмежень: [pic].

Для виконання завдання складається таблиця. У клітини таблиці записується вартість відповідних перевезень сij і над ними ж заносяться значення перевезень xij, які відповідають поставленим обмеженням. Клітини з не нульовими перевезеннями називаються засадничими, і з нульовими — вільними. У залежність від співвідношень між запасами і заявками транспортна завдання називається збалансованої чи незбалансованої. Збалансована ТЗ:[pic] Незбалансована ТЗ: [pic] Для збалансованої ТЗ обмеження приймають вид рівностей, тобто отримуємо m+n обмежень, де всі перемінні лінійно залежні. У результаті дозволене рішення збалансованої ТЗ то, можливо отримано, якщо заповнювати клітини транспортної таблиці в такий спосіб, щоб сума перевезень у кожному рядку [pic] мусить бути дорівнює запасам ai, а сума перевезень в кожному стовпці [pic] дорівнює відповідної заявці вj. Варіантів заповнення транспортної таблиці безліч, тому потрібним рішенням і те з допустимих рішень, котрим загальна вартість перевезень буде мінімальної. Методи рішення транспортної задачи.

Транспортна це може стати вирішеною симплекс методом. Проте специфічна форма системи обмежень дозволяє спростити симплекс метод. МЕТОД ПІВНІЧНО-ЗАХІДНОГО КУТА. Заповнення клітин відбувається послідовно за таким алгоритмом: спочатку вивозиться вантаж із А1 і завозиться до пункту В1, і цієї перевезенні х11 присвоюється максимально можливе значення. Якщо заявка пункту В1 виконано, а пункті А1 ще залишається вантаж, він вивозиться до пункту В2 тощо. Якщо пункті А1 замало було вантажу для В1, то що цей вантаж береться з А2 і т.д.

Коли попит споживача А1 задоволений, він випадає з розгляду тощо. | |В1 |В2 |В3 |В4 |Запаси | |А1 |15 |5 |6 |8 |20 | | |5 |7 | | | | |А2 |6 |25 |8 |5 |25 | | | |7 | | | | |А3 |5 |5 |25 |7 |30 | | | |4 |6 | | | |А4 |6 |5 |10 |5 |15 | | | | |7 |4 | | |А5 |5 |6 |6 |10 |10 | | | | | |6 | | |Заявки |15 |35 |35 |15 |100 |.

Вартість перевезення: W=5*15+5*7+25*7+5*4+25*6+10*7+5*4+10*6=605 Суттєвим недоліком методу північно-західного кута і те, що він побудований не враховуючи вартості перевезень. МЕТОД МІНІМАЛЬНОГО ЕЛЕМЕНТА. Заповнення клітин транспортної таблиці починається з тим клітини, у якій значення мінімально. У неї записується максимально можливе значення перевезення хij, що може бути одно або запасу аi, або заявці вj. Якщо заявка вj виконано, то j-й стовпець большє нє розглядається. Не вивезений вантаж ще, то він вивозиться до пункту з найменшою тарифом. | |В1 |В2 |В3 |В4 |Запаси | |А1 |15 |7 |5 |8 |20 | | |5 | |6 | | | |А2 |6 |7 |25 |5 |25 | | | | |8 | | | |А3 |5 |30 |6 |7 |30 | | | |4 | | | | |А4 |6 |5 |7 |15 |15 | | | | | |4 | | |А5 |5 |5 |5 |6 |10 | | | |6 |6 | | | |Заявки |15 |35 |35 |15 |100 |.

Вартість перевезення: W = 30*4+5*6+15*4+15*5+5*6+25*8+5*6 = 545. РАСПЕРЕДЕЛЕННЫЙ МЕТОД ПОЛІПШЕННЯ ПЛАНА ПЕРЕВЕЗЕНЬ. Заради покращання плану використовують цикл транспортної таблиці. Цикл — тут щось клітин, з'єднаних замкнутої ламаної з прямими кутами. Зобразимо два циклу: А1В1, А1В2, А2В2, А2В1; А1В3, А1В4, А2В4, А2В6, А1В5, А4В5, А4В3. |A2 |С21 |С22 |С23 |С24 |С25 |С26 |a2 | |A3 |С31 |С32 |С33 |С34 |С35 |С36 |a3 | |А4 |С41 |С42 |С43 |С44 |С45 |С46 |а4 | |A5 |С51 |С52 |С53 |С54 |С55 |С56 |a5 | |Попит споживачів |b1 |b2 |в3 |b4 |в5 |b6 | |.

Кожен цикл має парне число вершин і ребер, тобто у таблиці у кожному рядку чи стовпці може находтся лише парне число клітин, містять вершини. Тож у клетках-вершинах можна змінювати значення петевозки так, що у сума по рядкам і столбцам не змінюється. Вершини циклу, у яких збільшуємо перевезення «+», а яких зменшуємо перевезення «-». Значимість зміни позначимо ?, її переміщуватимемо по циклу. Максимальне значення ?, яким можна зменшити перевезення, визначається умовою неотрицательности перевезень. Ціна циклу q — це й зміна вартості перевезень при переміщенні? по циклу, яка дорівнює різниці між сумою вартостей перевезень, відповідних «+"-ым вершин і сумою вартостей «-» -ых вершин. Q1= (с11+с22)-(с12+с21) Q2 = (с13+с24+с16+с45)-(с14+с26+с15+с43) При перенесення по циклу до одиниць вантажу, вартість циклу і вартість плану перевезень змінитися на до одиниць. Заради покращання плану перевезень потрібно знайти «-» цикл і перемістити у ній максимально можливу кількість вантажу, до того часу поки таких циклів не залишиться. Кількість вантажу, що можна перемістити визначається мінімальним значенням перевезень в «-» вершинах цикла.