Курсова робота на тему: «ТРАНСПОРТНА ЗАДАЧА І ЇЇ РОЗВ’ЯЗУВАННЯ ЗАСОБАМИ MICROSOFT EXCEL»

План

Вступ     3

1. Поява транспортної задачі     4

2. Транспортна задача    8

3. Транспортна задача за критерієм вартості    10

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

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

4. Транспортна задача за критерієм часу    11

5. Приклад розв’язування транспортної задачі    18

5.1. Аналітичне розв’язування задачі    18

5.2. Розв’язування задачі за допомогою Excel    21

Висновки    27

Література    29

Вступ

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

Зараз слово “Оптимізація” на вустах у багатьох користувачів персональних комп’ютерів. Ми оптимізуємо все що можна: від графічних файлів до операційних систем. Але мало хто замислюється над тим що проблема пошуку найкращого рішення не менш гостро поставлена й в економіці.

Першу в історії оптимізаційну задачу сформулював Леонардо Фібоначчі, італійський математик XIII століття. Його задача “Про гирі” присвячена проблемі зважування за допомогою важільних ваг і створення оптимальної системи гир для цієї мети. У Новий Час у зв’язку зі зміцненням позицій капіталізму, зародженням банківської системи, ростом міст і мануфактур проблема пошуку оптимальних рішень стала дуже актуальною. І вже в XVIII столітті були закладені математичні основи оптимізації: варіаційне числення, чисельні методи й ін. Однак багато з розроблених алгоритмів було дуже складно реалізувати на практиці, і тільки з появою ЕОМ, що володіють великою обчислювальною потужністю, вдалося вирішити великий комплекс оптимізаційних завдань. До теперішнього часу накопичений величезний досвід рішення подібного класу завдань як для конкретних додатків, так й в узагальненому виді.

Дана робота присвячена знайомству з однією з найбільш популярних економіко-математичних моделей – транспортній задачі.

1. Поява транспортної задачі

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

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

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

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

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

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

Важливий внесок щодо розв’язання цих проблем зробив видатний математик академік Л.В.Канторович. У своїй роботі “Математичні методи організації і планування виробництва”, яка була опублікована в 1939 році, він розробив метод для розв’язання транспортної задачі, яка на сьогодні є однією з основних, а також тою, що потребує розв’язування чи не щодня в різних галузях народного господарства.

Вивчення транспортних задач має виключно практичне значення, так, як, по-перше, дозволяє знизити транспортні витрати конкретного підприємства на 10-30 %, а по-друге, велику кількість інших прикладних задач можна описати математичними моделями, що є подібні до моделей транспортних задач.

Методи лінійного програмування поділяються на дві групи: універсальні і спеціальні. За допомогою універсальних методів можна розв’язати будь-яку задачу лінійного програмування, в тому числі і транспортну. З числа цих методів найбільш поширеним є симплексний метод, що був запропонований Дж. Данцигом. До цієї групи відносяться також методи розширених множників Л.В.Канторовича.

Спеціальні методи застосовуються для розв’язування окремих класів задач лінійного програмування. Вони, як правило, простіші ніж універсальні, але застосовуються не для всіх задач. До спеціальних методів відносяться методи розв’язування транспортної задачі, що враховують специфіку її обмежень:

  • всі обмеження задані у вигляді рівнянь;
  • кожна змінна входить лише в два рівняння;
  • коефіцієнти при змінних – одиниці.

    Серед цих методів найбільш відомі наступні:

  1. Розподільчий метод;
  2. Модифікований розподільчий метод (він же метод потенціалів), запропонований Л.В.Канторовичем та М.К.Гавуріним, а згодом, незалежно від них, Дж. Данцігом;
  3. Венгерський метод, запропонований Е. Егерварі і удосконалений Х. Куном для розв’язування окремого випадку транспортної задачі: задачі про призначення (або про вибір), а пізніше узагальнений Дж. Манкресом на транспортну задачу загального виду;
  4. Метод диференціальних рент А. Л. Брудно;

    Для розв’язання питань спеціалізації виробництва часто доводиться розв’язувати таку задачу:

    ЗАВАНТАЖИТИ

    Для скачування файлів необхідно або Зареєструватись

    Transportna Zadacha I Ii Rozv (453.5 KiB, Завантажень: 20)

Сторінка: 1 2 3 4 5 6 7
завантаження...
WordPress: 23.52MB | MySQL:26 | 0,338sec