Математическая постановка транспортної завдання лінійного программирования

Запровадження 2.

1. Постановка завдання й її математична модель 3.

2. Моделі транспортної завдання 7.

2.1. Закрита модель транспортної завдання 7.

2.2. Відкрита модель транспортної завдання 8.

3. Визначення оптимального і опорного плану транспортної задачи.

4. Методи визначення початкового опорного плану 12.

4.1. Метод мінімального елемента 12.

4.2. Метод апроксимації Фогеля 14.

5. Методи визначення оптимального плану 16.

5.1. Угорський метод 16.

5.2. Метод потенціалів 17.

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

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

Мета заданої роботи — освоїти математичну постановку транспортної завдання лінійного программирования.

1. Постановка завдання й її математична модель.

Транспортна завдання є приватною типом завдання лінійного програмування і формулюється так. Є m пунктів відправлення (чи пунктів виробництва) Аi …, Аm, у яких зосереджені запаси однорідних продуктів у кількості a1, …, аm одиниць. Є n пунктів призначення (чи пунктів споживання) В1, …, Вm, потреба що у зазначених продуктах становить b1, …, bn одиниць. Відомі також транспортні витрати Сij, пов’язані в перевезенні одиниці продукту із Ai до пункту Вj, і [pic]1, …, m; j [pic]1, …, n. Припустимо, що [pic] т. е. загальний обсяги виробництва дорівнює загального обсягу споживання. Потрібна скласти такий план перевезень (звідки, куди й скільки одиниць продукту везти), щоб задовольнити попит всіх пунктів споживання з допомогою реалізації всього продукту, виробленого усіма пунктами виробництва, при мінімальної загальної вартості всіх перевезень. Наведена формулювання транспортної завдання називається замкнутої транспортної моделлю. Формализуем цю задачу.

Нехай хij — кількість одиниць продукту, поставленого із Аi в пункт Вj. Підлягають мінімізації сумарні видатки перевезення продуктів із усіх пунктів виробництва в усі пункти споживання виражаються формулою: [pic] (1) Сумарна кількість продукту, спрямовуваного з кожного пункту відправлення в усі пункти призначення, має бути одно запасу продукту даному пункті. Формально це, що [pic], і [pic]1, …, m (2) Сумарна кількість вантажу, доставляемого у кожний пункт призначення із усіх пунктів відправлення, має бути одно потреби. Це умова повного задоволення попиту: [pic], j [pic]1, …, n (3) Обсяги перевезень — неотрицательные числа, оскільки перевезення з пунктів споживання пункти виробництва виключені: xij [pic]0, і [pic]1, …, m; j [pic]1, …, n (4).

Транспортна завдання зводиться, в такий спосіб, до мінімізації сумарних витрат і під час умов задоволення від попиту й рівності вывозимого кількості продукту запасам їх у пунктах відправлення. Визначення 1. Будь-яке ненегативне рішення системи лінійних рівнянь [pic], j [pic]1, …, n і [pic], і [pic]1, …, m, обумовлений матрицею X=(xij)(i [pic]1, …, m; j [pic]1, …, n), називається планом транспортної задачи.

Определение 2. План X*=(x*ij)(i [pic]1, …, m; j [pic]1, …, n), у якому функція [pic] приймає своє мінімальне значення, називається оптимальним планом транспортної завдання. Зазвичай вихідні дані записуються як таблиці 1.

Таблиця 1. |Пункти отправления|Пункты призначення |Запаси | | |В1 |… |Bj |… |Bn |А1 | |A1 |C11 |… |C1j |… |C1n |a1 | | |X11 | |X1j | |X1n | | |… |… |… |… |… |… |… | |Ai |Ci1 |… |Cij |… |Cin |ai | | |Xi1 | |Xij | |Xin | | |… |… |… |… |… |… |… | |Am |Cm1 |… |Cmj |… |Cmn |am | | |Xm1 | |Xmj | |Xmn | | |Потреби |b1 |… |bj |… |bn | |.

Очевидно, загальне наявність вантажу в постачальників одно [pic], а загальна потреба у вантаж в пунктах призначення дорівнює одиниці. Якщо загальна потреба у вантаж в пунктах призначення дорівнює запасу вантажу на пунктах відправлення, тобто. [pic], (5) то модель такою транспортною завдання називається закритою. Нерідко непотрібен, щоб весь вироблений продукт у кожному пункті виробництва реалізували. У разі баланс виробництва та споживання може бути порушений: [pic], і [pic]1, …, m. Запровадження його запровадження призводить до відкритої транспортної моделі. Теорему 1. Будь-яка транспортна завдання, що має сумарний обсяг запасів збігаються з сумарним обсягом потреб, має решение.

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

2.1. Закрита модель транспортної задачи.

Аби довести теореми необхідно показати, що з заданих умовах існує хоча б тільки план завдання й лінійна функція на безлічі планів обмежена. Доказ. Нехай [pic]= M > 0[pic].

Тоді величини xij = aibj /M (і = 1,2,3, … m; j = 1,2,3, …, n) є планом, оскільки вони задовольняють системі обмежень (2) і (3). Справді, підставляючи значення в (2) і (3), находим.

[pic]= ai ,.

[pic] = bj. Виберемо з значень Cij найбільше З (= max Cij і замінимо в лінійної функції (1) все коефіцієнти на З (тоді, враховуючи (2), получим.

[pic], Виберемо з значень Cij найменше C ((=min Cij і замінимо в лінійної функції все коефіцієнти на З ((; тоді, враховуючи (2) маємо [pic] Об'єднуючи останні двоє нерівності за одну подвійне, остаточно отримуємо C ((M (Z (З (M, т. е. лінійна функція обмежена на безлічі планів транспортної задачи.

2.2. Відкрита модель транспортної задачи.

Транспортна завдання, у якій сумарні запаси й потреби не збігаються, т. е. не виконується умова [pic], називається відкритої. Для відкритої моделі то, можливо два випадку: a) сумарні запаси перевищують сумарні потреби [pic]; b) сумарні потреби перевищують сумарні запаси [pic]. Лінійна функція однакова в обох випадках, змінюється лише вид системи обмежень. Знайти мінімальне значення лінійної функції [pic] при обмеженнях [pic], і = 1, 2, …, m, (випадок а) [pic], j = 1, 2, …, n; [pic], і = 1, 2, …, m, (випадок б) [pic], j = 1, 2, …, n, xij (0 (і = 1, 2, …, m; j = 1, 2, …, n). Відкрита модель вирішується приведенням до закритою моделі. Що стосується (а), коли сумарні запаси перевищують сумарні потреби, вводиться фіктивний споживач Bn+1, потреби якого bn+1 = [pic]. У разі (б), коли сумарні потреби перевищують сумарні запаси, вводиться фіктивний постачальник Am+1, запаси якого am+1 = [pic]. Вартість перевезення одиниці вантажу як фіктивного споживача, і вартість перевезення одиниці вантажу від фіктивного постачальника вважають рівними нулю, оскільки вантаж в обох випадках не перевозиться. Після перетворень завдання набуває вигляду закритою моделі і вирішується звичайному способом. При рівних вартостях перевезення одиниці вантажу від постачальників до фіктивному споживачеві видатки перевезення вантажу реальним споживачам мінімальні, а фіктивному споживачеві буде скеровано вантаж від найменш вигідних постачальників. Це ж отримуємо у питаннях фіктивного поставщика.

Перш ніж вирішувати якусь транспортну завдання, потрібно спочатку перевірити, якої моделі вона належить, і після цього скласти таблицю на її решения. pic].

3. Визначення оптимального і опорного плану транспортної задачи.

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

Кількість змінних Xij у транспортному завданню з m пунктами відправлення і n пунктами призначення одно nm, а число рівнянь в системах (2) і (3) одно n+m. Оскільки нам здається, що виконується умова (5), то число лінійно незалежних рівнянь одно n+m-1 відмінних нуля неизвестных.

Якщо опорному плані число відмінних нуля компонентів одно у точності n+m-1, то план не вираженим, і якщо менше — то выраженным.

Для визначення опорного плану є кілька методів. Три з них — метод северно-западного кута, метод мінімального елемента і метод апроксимації Фогеля — розглянуті ниже.

Під час упорядкування початкового опорного плану методом північно-західного кута вартість перевезення одиниці до уваги береться, тому побудований план далекий до оптимального, отримання якого пов’язані з більший обсяг обчислювальних робіт. Зазвичай розглянутий метод використовується при обчисленнях з допомогою ЭВМ.

Як це і для будь-якої завдання лінійного програмування, оптимальний план транспортної завдання є і опорним планом.

Для визначення оптимального плану транспортної завдання можна використовувати вищевикладені методи. Проте через виняткової практичної важливості це завдання і через специфіку її обмежень [кожне невідоме входить лише два рівняння системи (2) і (3) і коефіцієнти при невідомих рівні одиниці] визначення оптимального плану транспортної завдання розроблено спеціальні методи. Два їх — метод потенціалів і Угорський метод — розглядаються ниже.

4. Методи визначення початкового опорного плана.

4.1. Метод мінімального элемента.

Суть методу у тому, що із усієї таблиці вартостей вибирають найменшу й у клітину, яка їй відповідає, поміщають менше з чисел [pic]и [pic]. Потім з розгляду виключають або рядок, відповідну постачальнику, запаси якого повністю витрачені, або стовпець, відповідний споживачеві, потреби якого цілком задоволені, або й рядок і стовпець, якщо витрачені запаси постачальника і задоволено потреби споживача. З іншої частини таблиці вартостей знову вибирають найменшу вартість, та інформаційний процес розподілу запасів продовжують, доки всі запаси ні розподілені, а потреби задоволені. Пример

Скласти початковий опорний план методом мінімального елемента для транспортної завдання виду: |2 |3 |4 |15| |11|6 |10|1 | |8 |9 |3 |3 | |4 |1 |2 |21| |10|20|10| |.

Решение: Завдання збалансована. Будуємо початковий опорний план методом мінімального элемента.

1. З’ясуємо де мінімальну вартість перевезень. [pic]Первая перевезення здійснюватиметься з пункту виробництва [pic]в пункт споживання [pic]и становитиме максимально можливу кількість одиниць продукту [pic]:. І тут, потреби пункту споживання [pic]будут задоволені повністю. Отже, вартості шпальти 2 жило якнайбільше не розглядати, оскільки перевезення [pic]. Выясним мінімальну вартість перевезень (не враховуючи шпальти № 2).

2. [pic]Вторая й третя перевезення будуть здійснюватися за пункту виробництва [pic]и [pic]в пункт споживання [pic]и.

[pic]соответственно і становитимуть максимально можливу кількість одиниць продукту: [pic], [pic];

3. [pic].

4. Четверта перевезення здійснюється з пункту [pic]в пункт потребления.

[pic], т.к. [pic](без обліку першого, другого шпальти й четвертою рядки). [pic].

5. П’ята перевезення здійснюється з пункту [pic]в пункт потребления.

[pic], т.к. [pic](без обліку першого, другого шпальти, третього й четвертого рядки). [pic].

6. Шоста перевезення здійснюється з пункту [pic]в пункт потребления.

[pic]т.к. [pic](без обліку першого, другого шпальти, першої, третьої та четвертої строки).

[pic] Опорний план має вигляд; |10|5 |0 | |0 |1 |0 | |0 |3 |0 | |0 |11|10|.

4.2. Метод апроксимації Фогеля При визначенні опорного плану транспортної завдання методом апроксимації Фогеля знаходять різницю за всі столбцам й за всіма рядкам між двома записаними у яких мінімальними тарифами. Ці різниці записують їх у спеціально відведених при цьому рядку і стовпці в таблиці умов завдання. Серед зазначених разностей вибирають мінімальну. У рядку (чи стовпці), якої дана різницю відповідає, визначають мінімальна вартість. Якщо мінімальна вартість однакова для кількох клітин шпальти (рядки), то тут для заповнення вибирають ту клітину, розташовану в стовпці (рядку), відповідному найбільшої різниці між двома мінімальними вартостями, які у даному стовпці (рядку). Приклад Знайти методом апроксимації Фогеля початковий опорний план транспортної завдання: (Тут ми перенесли потреби у верхню рядок для зручності побудови плану). Розглянемо завдання, наведену для методів північно-західного кута і мінімального елемента Рішення: |2 |2 |2 | |2 |2 |2 | |2 |- |2 | |- |- |2 | |- |- |- |.

Опорний план має вигляд: |7|0 |8| |0|1 |0| |3|0 |0| |0|19|2|.

5. Методи визначення оптимального плана.

5.1. Угорський метод Идея методу пролунала угорським математиком Эгервари і полягає у наступному. Будується початковий план перевезень, не задовольняє загалом разі всім умовам завдання (з деяких пунктів виробництва не весь продукт вивозиться, потреба частини пунктів споживання в повному обсязі задоволена). Далі здійснюється перехід до нового плану, ближчому оптимального. Послідовне застосування цього прийому за кінцеве число ітерацій призводить до рішенню задачи.

Алгоритм угорського методу складається з підготовчого етапу і з кінцевого числа ітерацій. На підготовчому етапі будується матриця X0 (xij[0])m, n, елементи якої неотрицательны і задовольняють неравенствам:

і 1, …, m;

j 1, …, m.

Если цих умов є равенствами, то матриця Хo — рішення транспортної завдання. Якщо серед умов є нерівності, то здійснюється перехід до першої ітерації. На k-й ітерації будується матриця Хk (xij[0])m, n. Близькість цієї матриці до вирішення завдання характеризує число Dk — сумарна невязка матриці Хk:

.

В результаті першої ітерації будується матриця Хl, що складається з неотрицательных елементів. У цьому Dl D0. Якщо Dl 0, то Хl — оптимальне вирішення завдання. Якщо Dl 0, то переходять до наступній ітерації. Вони проводяться до того часу, поки Dk попри деякий k стане рівним нулю. Відповідна матриця Хk розв’язує транспортної задачи.

Венгерский метод найефективніший під час вирішення транспортних завдань із целочисленными обсягами виробництва та споживання. І тут число ітерацій вбирається у величини D0/2 (D0 — сумарна невязка підготовчого этапа).

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

5.2. Метод потенциалов Метод потенціалів є модифікацією симплекс-метода виконання завдання лінійного програмування стосовно транспортної завданню. Він дозволяє, вирушаючи від деякого припустимого рішення, отримати оптимальне рішення за кінцеве число ітерацій. Загальна схема окремої ітерації така. По допустимому рішенню кожному пункту завдання порівнюється число, зване його попереднім потенціалом. Пунктах Аi відповідають числа ui, пунктах Bj — числа vj. Вони вибираються таким чином, щоб їх різницю на k-й ітерації дорівнювала Сij — вартості перевезення одиниці виробленої продукції між пунктами Аi і Вj:

vj[k] - ui[k] Cij, і 1, …, m; j 1, …, п.

Если різницю попередніх потенціалів кожної пари пунктів Аi, Вj не перевершує Сij, то отриманий план перевезень розв’язує завдання. У іншому разі вказується спосіб отримання нового припустимого плану, що з меншими транспортними витратами. За кінцеве число ітерацій перебуває оптимальний план задачи.

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

1. Є. Р. Гольштейн, Д. Б. Юдін «Завдання лінійного програмування транспортного типу», Москва, 1993.

2. І. Л. Акулич, У. Ф. Стрельчонок «Математичні методи лікування й комп’ютерні технології рішення оптимізаційних завдань», Рига, 2000.

3. internet.