Постановка і вирішення транспортної параметричної завдання

МІНІСТЕРСТВО ОСВІТИ

Димитровградське ІНСТИТУТ ТЕХНОЛОГІЇ,

УПРАВЛІННЯ ТА ДИЗАЙНУ

УЛЬЯНІВСЬК ДЕРЖАВНОГО ТЕХНІЧНОГО УНІВЕРСИТЕТУ

Кафедра математики та інформаційних технологій

Курсова робота

ТЕМА: Постановка і вирішення транспортної параметричної завдання

Виконав:

задача № 25.7 (3)

Перевірив: Бронз Г.А.

Димитровград 2005

Зміст

Введення

1. Математична постановка задачі про оптимальні перевезеннях

2. Аналітичний метод рішення параметричної транспортної задачі

2.1 Методика знаходження вихідного опорного рішення задачі про оптимальні перевезеннях методом Фогеля

2.2 Перевірка отриманого опорного плану на оптимальність

2.3 Методика рішення параметричної транспортної задачі

3. Метод рішення задачі про оптимальні перевезеннях засобами Ms Excel

4. Рішення параметричної транспортної задачі

4.1 Постановка параметричної транспортної задачі

4.2 Математична модель задачі

4.3 Рішення задачі аналітичним методом

4.4 Рішення завдання засобами Ms Excel

Висновок

Бібліографічний список

Введення

Перші завдання геометричного змісту, пов'язані з віднайденням найменших і найбільших величин, з'явилися ще в давні часи. Розвиток промисловості в 17-18 століттях призвело до необхідності дослідження більш складних завдань на екстремум і до появи варіаційного числення. Проте лише в 20 столітті при величезному розмаху виробництва та усвідомлення обмеженості ресурсів Землі на весь зріст постало завдання оптимального використання енергії, матеріалів, робочого часу, велику актуальність набули питання найкращого в тому чи іншому сенсі управління різними процесами фізики, техніки, економіки та ін Сюди відносяться, наприклад, завдання організації виробництва з метою отримання максимального прибутку при заданих витратах ресурсів, завдання управління системою гідростанцій і водосховищ з метою отримання максимальної кількості електроенергії, завдання щодо якнайшвидшого нагріванні чи охолодженні металу до заданого температурного режиму, завдання про найкращий гасінні вібрацій і багато інших завдання.

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

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

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

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

Лінійним програмуванням називаються завдання оптимізації, в яких цільова функція є лінійною функцією своїх аргументів, а умови, що визначають їх допустимі значення, мають вигляд лінійних рівнянь і нерівностей. Лінійне програмування почало розвиватися в першу чергу у зв'язку з завданнями економіки, з пошуком способів оптимального розподілу і використання ресурсів. Воно послужило основою широкого використання математичних методів в економіці. Слід підкреслити, що в рамках реальних економічних завдань число незалежних змінних зазвичай буває дуже великим (близько 10000 елементів).

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

1. Математична постановка задачі про оптимальні перевезеннях

У загальному вигляді завдання можна представити таким чином: у m пунктах виробництва A _1, A _2, ..., A _m є однорідний вантаж у кількості відповідно a _1, a _2, ..., a _m. Цей вантаж необхідно доставити в n пунктів призначення B _1, B _2, ..., B _n у кількості відповідно b _1, b _2, ..., b _n. Вартість перевезення одиниці вантажу (тариф) з пункту A _i в пункт B _j дорівнює c _ij.

Потрібно скласти план перевезень, що дозволяє вивести всі вантажі і має мінімальну вартість.

Позначимо через x _ij кількість вантажу, що перевозиться з пункту Ai, в пункт B _j. Запишемо умови задачі у розподільну таблицю, яку будемо використовувати для знаходження рішення (табл. 1.1).

Таблиця 1.1. Модель розподільчої таблиці.

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

при обмеженнях:

Оптимальним вирішенням завдання є матриця

задовольняє системі обмежень і доставляє мінімум цільової функції [1].

2. Аналітичний метод рішення параметричної транспортної задачі

2.1 Методика знаходження вихідного опорного рішення задачі про оптимальні перевезеннях методом Фогеля

Алгоритм виконання методу.

1. У кожному рядку і кожному стовпці розподільчої таблиці обчислити різниці між усіма парами елементів (C _ij) і вибрати мінімальну.

2. Серед всіх обраних мінімальних різниць C _ij вибрати максимальне значення і виділити відповідний стовпець (рядок).

3. У вибраному стовпці (рядку) знайти мінімальне значення C _ij і призначити необхідну перевезення, орієнтуючись на наявність запасів (a _i) даного постачальника (A _ij) та потреб (b _j) даного споживача (B _ij).

4. Викресливши відповідний рядок (стовпчик), тобто видаливши з подальших розрахунків постачальника (споживача), запаси якого (потреби) вичерпано, повторити заново алгоритм (1-4) до повного складання плану перевезень.

Процес розподілу продовжують до тих пір, поки всі вантажі від постачальників не будуть вивезені, а споживачі не будуть задоволені. При розподілі вантажів може виявитися, що кількість зайнятих клітин менше, ніж m + n -1. У цьому випадку завдання вважається виродженої. У цьому випадку відсутнє число зайнятих клітин заповнюється нульовими поставками, які називаються умовно зайнятими.

2.2 Перевірка отриманого опорного плану на оптимальність

Знайдене вихідне опорне рішення перевіряється на оптимальність методом потенціалів за наступним критерієм: якщо опорне рішення транспортної задачі є оптимальним, то йому відповідає система m + n дійсних чисел u _i і v _j, які відповідають умовам u _i + v _j = c _ij для зайнятих клітин і u _i + v _j - c _ij ≤ 0 для вільних клітин.

Числа u _i і v _j називають потенціалами. У розподільну таблицю додають рядок v _j і стовпець u _i.

Потенціали u _i і v _j знаходять з рівності u _i + v _j = c _ij, справедливого для зайнятих клітин. Одному з потенціалів дається довільне значення, наприклад u ₁ = 0, тоді інші потенціали визначаються однозначно. Так, якщо відомий потенціал u _i, то v _j = c _ij - u _i; якщо відомий потенціал v _j, то u _i = cij - vj.

Позначимо Δ _ij = u _i + v _j - c _ij. Цю оцінку називають оцінкою вільних клітин. Якщо Δ _ij ≤ 0, то опорне рішення є оптимальним. Якщо хоча б одна з оцінок Δ _ij> 0, то опорне рішення не є оптимальним і його можна поліпшити, перейшовши від одного опорного рішення до іншого [1].

2.3 Методика рішення параметричної транспортної задачі

Завдання формулюється так: для всіх значень параметра δ ≤ k ≤ φ де δ і φ - довільні дійсні числа, знайти такі значення які звертають в мінімум функцію

де X _ij - обсяг поставок вантажу,

при обмеженнях:

Xij ≥ 0,

Користуючись методом потенціалів, (Фогеля) вирішуємо завдання при k = δ до отримання оптимального рішення. Ознакою оптимальності є умова:

для незайнятих клітин

і для зайнятих клітин,

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

Умова сумісності транспортної задачі запишеться у вигляді

Значення aij і Bij визначаються з умови

де визначаються з систем рівнянь

Значення k знаходяться в межах k ₁ ≤ k ≤ k _2:

якщо існує хоча б одне B _ij> 0;

якщо все B _ij ≥ 0

якщо існує хоча б одне B _ij> 0;

якщо все B _ij ≤ 0.

Алгоритм рішення.

1. Задачу вирішуємо при конкретному значенні параметра k = δ до отримання оптимального рішення.

2. Визначаємо a _ij і B _ij.

3. Обчислюємо значення параметра k.

4. Якщо k> δ, виробляємо перерозподіл поставок і отримуємо нове оптимальне рішення. Якщо k = δ, то процес вирішення закінчено [1].

3 Метод рішення задачі про оптимальні перевезеннях засобами Ms Excel

Знаходження оптимального плану перевезень із застосуванням комп'ютерної програми Ms Excel здійснюється за допомогою функції "Пошук рішення".

Схема виконання:

1. Для зручності розрахунків необхідно окремо створити матрицю, що відображає вартість перевезень (C _ij) (рис 3.1.), А також матрицю, яка повинна буде відображати шуканий план перевезень (рис. 3.2.).

Рис. 3.1. Фрагмент вікна програми Ms Excel: Модель таблиці «Вартість перевезень».

2. У таблиці «Вартість перевезень» в осередках запасів постачальників і потреб споживачів записати кількість запасів постачальників і потреб споживачів відповідно, вказане в умові завдання.

3. Таблицю "План перевезень" створити з порожніми полями (заповненими одиницями), заздалегідь заданого числового формату. В осередках запасів (потреб) кожного постачальника (споживача) ввести формулу, яка виконує підсумовування всіх можливих поставок цього постачальника (споживача).

Рис. 3.2. Фрагмент вікна програми Ms Excel: Модель таблиці «План перевезень».

4. У клітинці цільової функції ввести формулу, вираховується сума творів елементів матриці "Вартість перевезень" та відповідних елементів матриці "План перевезень".

5. У діалоговому вікні функції "Пошук рішення" встановити необхідні обмеження, в цільовій комірці вказати адресу комірки з формулою цільової функції і встановити її рівною мінімальному значенню, в якості змінюваних клітинок вибрати діапазон всіх елементів матриці "План перевезень". Обмеження в "Пошуку рішень" полягають у необхідності рівності запасів (потреб), в матриці "План перевезень" відповідним запасах і потребам, зазначеним у матриці "Вартість перевезень". Також всі елементи матриці "План перевезень" повинні бути невід'ємними і цілочисельними.

6. У діалоговому вікні "Параметри пошуку рішення" встановити параметр "Лінійна модель" і число ітерацій, що дорівнює 100.

7. Виконати функцію "Пошук рішення" натисканням на кнопку "Виконати". В якості звіту за результатами вибрати необхідний пункт в списку "Тип звіту" діалогового вікна «Результати пошуку рішення».

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

4. Рішення параметричної транспортної задачі

4.1 Постановка параметричної транспортної задачі

Є чотири постачальника однорідного вантажу з обсягами поставок 100, 70, 70, 20 т. і три споживачі з обсягами споживання 120, 80, 60 т. Вартість транспортних витрат задана матрицею

причому вартість перевезення вантажу від четвертого постачальника до третього споживача змінюється в діапазоні 0 ≤ k ≤ 9.

Визначити оптимальний план перевезень, що забезпечує мінімальні транспортні витрати.

Зобразимо матричну запис завдання (табл. 4.1.1)

Табл. 4.1.1. Матрична запис завдання