Муніципальне освітній заклад
середньої професійної освіти
"Коледж економіки і управління"
Курсова робота
з дисципліни "Математичні методи"
Тема: Знаходження мінімальних витрат при розподілі товарів серед магазинів методами вирішення транспортної задачі
ЗМІСТ
ВСТУП
Глава 1. ЛІНІЙНЕ ПРОГРАМУВАННЯ
1.1 Транспортна задача
1.2 Методи складання опорного плану транспортної задачі
1.2.1 Метод північно-західного кута
1.2.2 Метод найменшої вартості
1.2.3 Метод потенціалів
1.2.4 Метод апроксимації Фогеля
Глава 2. ПРАКТИЧНА РЕАЛІЗАЦІЯ МЕТОДІВ ВИРІШЕННЯ ТРАНСПОРТНОЇ ЗАВДАННЯ
2.1 Постановка завдання
2.2 Знаходження початкового плану методом північно-західного кута
2.3 Знаходження початкового плану методом найменшої вартості
2.4 Метод потенціалів
2.5 Метод апроксимації Фогеля
2.6 Застосування можливостей електронних таблиць при вирішенні транспортної задачі
ВИСНОВОК
СПИСОК ЛІТЕРАТУРИ ТА ДЖЕРЕЛ
ВСТУП
Транспортна задача відноситься до класу задач лінійного програмування. Транспортна задача вирішує проблему знаходження оптимального (мінімального за вартістю) плану розподілу і переміщення ресурсів від виробників до споживачів.
Існує безліч методів для вирішення даного завдання. Вибравши один з методів можна швидко розрахувати оптимальний план розподілу, що значно скоротить витрати на доставку товарів по точках, на відміну від методу "навмання", коли доводиться гадати куди і скільки розподілити товарів.
Метою даної курсової роботи є вирішення завдання на розподілу товарів серед магазинів з мінімальними витратами різними методами.
Дуже важливо підібрати оптимальний метод розподілу товарів, так як для вирішення різних завдань оптимальними можуть виявитися різні методи.
Курсова робота складається з двох глав: теоретична частина, в якій розглянуті методи рішення транспортної задачі на розподілу ресурсів. І практична частина, в якій дані методи реалізовані для вирішення конкретно поставленої задачі.
ГЛАВА 1. ЛІНІЙНЕ ПРОГРАМУВАННЯ
В даний час лінійне програмування є одним з найбільш уживаних апаратів математичної теорії оптимального прийняття рішень, у тому числі і у фінансовій математиці. Для вирішення завдань лінійного програмування розроблено складне програмне забезпечення, що дає можливість ефективно і надійно вирішувати практичні завдання великих об'ємів. Ці програми і системи забезпечені розвиненими системами підготовки початкових даних, засобами їх аналізу і представлення отриманих результатів. У розвиток і вдосконалення цих систем вкладена праця і талант багатьох математиків, акумульований досвід рішення тисяч завдань. Володіння апаратом лінійного програмування необхідно кожному фахівцеві в області прикладної математики.
Лінійне програмування являє собою найбільш часто використовуваний метод оптимізації. До числа завдань лінійного програмування можна віднести завдання:
В· раціонального використання сировини і матеріалів; задачі оптимального розкрою;
В· оптимізації виробничої програми підприємств;
В· оптимального розміщення і концентрації виробництва;
В· складання оптимального плану перевезень, роботи транспорту;
В· управління виробничими запасами;
В· і багато інших, належать сфері оптимального планування.
1.1 Транспортна завдання
Транспортна задача відноситься до класу задач лінійного програмування. Транспортна задача вирішує проблему знаходження оптимального (мінімального за вартістю) плану розподілу і переміщення ресурсів від виробників до споживачів. Проблема оптимізації вартості перевезень актуальна і на сьогоднішній день, так як дозволяє фірмам та підприємствам суттєво скоротити витрати на транспорт. Правильна організація перевезень дозволяє усунути зустрічні та дублюючі перевезення, скоротити кількість дальніх перевезень і т. д. При вирішенні транспортної задачі необхідно:
В· забезпечити всіх споживачів ресурсами;
В· розподілити всі вироблені ресурси;
В· перемістити ресурси від виробників до споживачів з найменшими витратами.
Від кожного виробника ресурс може переміщатися до будь споживачеві і вимірюватися в одних одиницях вимірювання.
1.2 Методи складання опорного плану транспортної задачі
1.2.1 Метод північно-західного кута
На кожному етапі максимально можливим числом заповнюють ліву верхню клітинку залишилася частини таблиці. Заповнення таким чином, що повністю виноситься вантаж з або повністю задовольняється потреба.
1.2.2 Метод найменшої вартості
Суть методу полягає в тому, що з усієї таблиці вартостей вибирають найменшу. І в клітину, яка їй відповідає, поміщають менше з чисел a i або b j . Потім, з розгляду виключають або рядок, відповідний постачальнику, запаси якого повністю витрачені, або стовпець, відповідний споживачеві, потреби якого повністю задоволені. Або й рядок і стовпець, якщо витрачені запаси постачальника і задоволені потреби споживача. З решти таблиці вартостей знову вибирають найменшу вартість, і процес розподілу запасів продовжують, поки всі запаси не будуть розподілені, а потреби задоволені.
Алгоритм:
В· З таблиці тарифів вибирають найменшу вартість. І в клітину, яка їй відповідає, вписують менше з чисел.
В· Перевіряються рядки постачальників на наявність рядки з витраченими запасами і стовпці споживачів на наявність стовпця, потреби якого повністю задоволені. Такі стовпці і рядки далі не розглядаються.
В· Якщо не всі споживачі задоволені і не всі постачальники витратили товари, повернення до п.1, в іншому випадку задача вирішена.
1.2.3 Метод потенціалів
Найбільш простим методом ТЗ є метод потенціалів. Потенціалами називаються умовні числа U i , V j , приписані певним чином кожному постачальнику і споживачу.
Теорема (умови оптимального плану): Сума потенціалів постачальника і споживача дорівнює тарифній ставкою для зайнятих клітин; сума потенціалів постачальника і споживача не перевищує тарифну ставку для вільних клітин
Опорний план повинен бути не виродження (r = m + n-1 - невироджений план)
Алгоритм рішення:
1. Будуємо початкові плани методом північно-західного кута і методом найменшої вартості з них вибираємо кращий
2. Знаходимо потенціали постачальника і споживача, користуючись першою умовою оптимальності плану U i + V j ij
3. Перевіряємо другу умова оптимальності плану для вільних клітин
Якщо воно виконане, то план оптимальний, якщо ні то покращуємо план.
4. Поліпшення плану:
a. При не виконанні другої умови в клітку заносимо порушення зі знаком плюс. Такі клітки називаються потенційними.
b. Серед всіх потенційних клітин вибираємо клітину з найбільшим
порушенням.
c. Будуємо для обраної клітини замкнутий контур, що складається з вертикальних і горизонтальних відрізків прямої, причому вершини контуру лежать в зайнятих клітках.
За винятком тієї клітини, для як...
