МІНІСТЕРСТВО ОСВІТА ТА НАУКИ
УКРАЇНИ
НАЦІОНАЛЬНИЙ АВІАЦІЙНИЙ УНІВЕРСИТЕТ
Навчально-науковий Інститут
Економіки та Менеджменту
Факультет Економіки і Підприємництва
Кафедра економічної кібернетики
КУРСОВА РОБОТА
З ДИСЦИПЛІНИ «ЕКОНОМІЧНА КІБЕРНЕТИКА»
НА ТЕМУ: «ЗАДАЧА ПРО ВИБІР
НАЙБІЛЬШ ЕКОНОМНОГО ВИБОРУ МАРШРУТУ»
Виконала:
Студентка 2 курсу, група ФЕП-210
Жаб’як Софія Андріївна
Київ – 2017
ЗМІСТ
ВСТУП
Кожна людина щодня, не завжди
усвідомлюючи це, вирішує проблему: як
отримати найбільший ефект, володіючи
обмеженими засобами. Наші засоби та ресурси
завжди обмежені. Життя було б менш цікавою,
якби це було не так. Не важко виграти бій,
маючи армію в 10 разів більшу, ніж у супротивника.
Щоб досягти найбільшого ефекту, маючи
обмежені кошти, треба скласти план, або
програму дій. Раніше план у таких випадках
складався на око . У середині XX століття
був створений спеціальний математичний
апарат, що допомагає це робити з науки
. Відповідний розділ математики називається
математичним програмуванням. Слово програмування
"тут і в аналогічних термінах ( лінійне
програмування, динамічне програмування
і т.п.) зобов'язана почасти історичного
непорозуміння, почасти неточному перекладу
з англійської. З програмуванням для ЕОМ
математичне програмування має лише те
загальне, що більшість виникаючих на практиці задач
математичного програмування занадто
громіздкі для ручного рахунку, вирішити
їх можна тільки за допомогою ЕОМ, попередньо
склавши програму. Часом народження лінійного
програмування прийнято вважати 1939 р.,
коли була надрукована брошура Леоніда
Віталійовича Канторовича «Математичні
методи організації і планування виробництва».
Під назвою транспортна задача
об'єднується широке коло завдань з єдиною
математичною моделлю. Дані завдання відносяться
до завдань лінійного програмування і
можуть бути вирішені симплексним методом.
Однак матриця системи обмежень транспортної
задачі настільки своєрідна, що для її
рішення розроблені спеціальні методи.
Ці методи, як і симплексний метод, дозволяють
знайти початкове опорне рішення, а потім,
поліпшуючи його, отримати оптимальне
рішення.
Метою транспортної задачі є забезпечення
отримання (доставки) продукції (товару)
споживачеві в потрібний час і місце при
мінімально можливих сукупних витратах
трудових, матеріальних, фінансових ресурсів.
Мета транспортної діяльності
вважається досягнутою при виконанні
шести умов:
- потрібний товар;
- необхідної якості;
- в необхідній кількості доставлений;
- в потрібний час;
- в потрібне місце;
- з мінімальними витратами.
Об'єктом вивчення є матеріальні і відповідні
їм фінансові, інформаційні потоки, які
супроводжують виробничо-комерційну діяльність.
РОЗДІЛ 1. ТРАНСПОРТНА ЗАДАЧА ЛІНІЙНОГО
ПРОГРАМУВАННЯ
1.1 Загальна постановка,
цілі, завдання. Основні типи, види моделей
Під назвою "транспортна задача" об'єднується широке
коло завдань з єдиною математичною моделлю. Дані завдання відносяться
до завдань лінійного програмування і
можуть бути вирішені симплексним методом.
Однак матриця системи обмежень транспортної
задачі настільки своєрідна, що для її
рішення розроблені спеціальні методи.
Ці методи, як і симплексний метод, дозволяють
знайти початкове опорне рішення, а потім,
поліпшуючи його, отримати оптимальне
рішення. У загальній постановці транспортна
задача полягає у знаходженні оптимального
плану перевезень деякого однорідного
вантажу з m баз n споживачам .
Розрізняють два типи транспортних
завдань: але критерієм вартості (план перевезень оптимальний,
якщо досягнуть мінімум витрат на його
реалізацію) і за критерієм часу (план оптимальний, якщо на його
реалізацію витрачається мінімум часу).
- Позначимо кількість вантажу,
що є на кожній з m баз (запаси), відповідно
, А загальна кількість наявного
в наявності вантажу – a:
- замовлення кожного із споживачів
(потреби) позначимо відповідно , А загальна кількість потреб - .
- Тоді за умови a = b, ми маємо закриту модель, а за умови a ≠ b – відкриту модель
транспортної задачі.
Очевидно, у випадку закритої
моделі весь наявний вантаж розвозиться
повністю, і всі потреби замовників повністю
задоволені; у разі ж відкритої моделі
або всі замовники задоволені і при цьому
на деяких базах залишаються надлишки вантажу (а > b) або весь вантаж виявляється
витраченим, хоча потреби повністю не
задоволені (а < b).
Так само існують одноетапні
моделі задач, де перевезення здійснюється
безпосередньо від, наприклад, бази або
заводу виробника до споживача, і двохетапні,
де між ними є "перевалочний пункт",
наприклад - склад.
План перевезень із зазначенням запасів
і потреб зручно записувати у вигляді
такої таблиці, званої таблицею перевезень (1):
Умови a = b або a ≠ b означає, з якою завданням ми
маємо справу, із закритою моделлю або
відкритою моделлю транспортної задачі.
Змінне означає кількість вантажу,
що перевозиться з бази споживачеві . Сукупність
цих величин утворює матрицю (матрицю перевезень).
Очевидно, змінні повинні відповідати
умовам (1.4):
Система (1.4) містить m + n рівнянь з m n невідомими. Її особливість полягає в тому,
що коефіцієнти при невідомих всюди рівні
одиниці. Крім того, всі рівняння системи
(1.4) можуть бути розділені на дві групи:
перша група з т перших рівнянь ("горизонтальні"
рівняння) і друга група з п решти рівнянь ("вертикальні"
рівняння). У кожному з горизонтальних
рівнянь містяться невідомі з одним і
тим же першим індексом (вони утворюють один рядок матриці перевезень), у кожному з вертикальних
рівнянь містяться невідомі з одним і
тим же другий індексом (вони утворюють один стовпець
матриці перевезень). Таким чином, кожна
невідома зустрічається в системі (1.4)
двічі: в одному і тільки одному горизонтальному
і в одному і тільки одному вертикальному
рівняннях.
Така структура системи (1.4)
дозволяє легко встановити її ранг. Дійсно, покажемо, що
сукупність невідомих, які утворюють перший
рядок і перший стовпець матриці перевезень,
можна прийняти як базису. При такому виборі
базису, принаймні, один з двох їхніх індексів дорівнює одиниці, а, отже, вільні
невідомі визначаються умовою
,
. Перепишемо систему (1.4) у вигляді (1.4а):
де символи
означають підсумовування за відповідним індексом.
При цьому легко помітити, що
під символами такого підсумовування
об'єднуються тільки вільні невідомі (i
≥ 2, j ≥ 2).
У розглянутій нами системі
тільки два рівняння, а саме перше горизонтальне і перше
вертикальне, містять більше одного невідомого
з числа обраних нами для побудови базису.
Виключивши з першого горизонтального
рівняння базисні невідомі за допомогою вертикальних
рівнянь, ми отримуємо рівняння (1.5):
або коротше (1.6):
,
де символ
означає суму всіх вільних невідомих. Аналогічно, виключивши з першого вертикального
рівняння базисні невідомі за допомогою горизонтальних
рівнянь, ми отримуємо рівняння (1.6а):
Так як для закритої моделі
транспортної задач a = b, то отримані
нами рівняння (1.6) та (1.6а ) однакові і, виключивши
з одного з них невідоме , ми отримаємо рівняння-тотожність 0 = 0, яке з системи викреслюється.
Отже, перетворення системи (1.5) звелося до заміни
двох рівнянь (першого горизонтального
і першого вертикального) рівнянням (1.6).
Решта рівняння залишаються незмінними.
Система прийняла вигляд (1.7):
У системі (1.7) виділено зазначений вище базис:
базисні невідомі з перших т рівнянь утворюють перший стовпець
матриці перевезень, а базисні невідомі
решти рівнянь утворюють перший рядок
матриці перевезень без першого невідомого[Вона входить у перше
рівняння системи (1.7)]. У системі (1.7) є m + n – 1 рівнянь, виділений базис містить
m + n - 1 невідомих, а, отже, і ранг системи
(1.5) r = n + m – 1.
Для вирішення транспортної
задачі необхідно крім запасів і потреб
знати також і тарифи , тобто вартість перевезення одиниці
вантажу з бази споживачеві .
Сукупність тарифів також утворює матрицю, яку
можна об'єднати матрицею перевезень і
даними про запаси та потреби в одну таблицю
(2):
Сума всіх витрат, тобто вартість
реалізації даного плану перевезень, є
лінійною функцією змінних (1.8):
Необхідно в області допустимих
рішень системи рівнянь (1.5) знайти рішення,
яке мінімізує лінійну функцію (1.8).
Таким чином, ми бачимо, що транспортна задача є задачею лінійного
програмування. Для її вирішення застосовують
також симплекс-метод, але в силу специфіки завдання
тут можна обійтися без симплекс-таблиць.
Рішення можна отримати шляхом деяких
перетворень таблиці перевезень. Ці перетворення відповідають переходу від одного плану перевезень
до іншого. Але, як і в загальному випадку,
оптимальне рішення шукається серед базисних
рішень. Отже, ми будемо мати справу тільки з базисними (або
опорними) планами. Так як в даному випадку
ранг системи обмежень - рівнянь дорівнює m + n - 1 то серед всіх m n невідомих виділяється m + n - 1 базисних невідомих, а решта (m – 1) (n – 1) невідомих є вільними. У базисному
рішенні вільні невідомі рівні нулю. Зазвичай
ці нулі в таблицю не вписують, залишаючи відповідні клітини порожніми.
Таким чином, в таблиці перевезень,
що представляє опорний план, ми маємо m + n -1 заповнених і (m –1) (n – 1) порожніх клітин.
Для контролю треба перевіряти, дорівнює
чи сума чисел в заповнених клітках кожного рядка таблиці перевезень
запасу вантажу на відповідній базі, а в кожному стовпці - потреби
замовника [цим підтверджується, що цей
план є рішенням системи (1.5)].
Зауваження
1. Не виключаються тут і вироджені
випадки, тобто можливість звернення до
нуль однієї або кількох базисних невідомих.
Але ці нулі на відміну від нулів вільних
невідомих вписуються у відповідну клітину, і ця клітина вважається
заповненою.
Зауваження
2. Під величинами , Очевидно, не обов'язково мати
на увазі тільки тарифи. Можна також вважати
їх величинами, пропорційними тарифами,
наприклад, відстанями від баз до споживачів.
Якщо, наприклад, виражені в тоннах, а в кілометрах, то величина S, яка визначається формулою
(1.8), є кількістю тонно-кілометрів, що складають
обсяг даного плану перевезень.
Очевидно, що витрати на перевезення пропорційні
кількості тонно-кілометрів і, отже, будуть
мінімальними при мінімумі S. У цьому випадку замість матриці
тарифів ми маємо матрицю відстаней.
РОЗДІЛ
2. МЕТОДИ ВИРІШЕННЯ ТРАНСПОРТНОЇ ЗАДАЧІ
2.1 Методи складання
початкового опорного плану
Як і в загальному випадку, рішення
транспортної задачі починається з відшукання першого
опорного плану (вихідного базису). Ми
розглянемо два найбільш поширені методи
побудови такого базису. Суть обох цих
методів полягає в тому, що базисний план
складається послідовно, у кілька кроків
(точніше, m + n - 1 кроків). На кожному з цих кроків
заповнюється одна клітина, до того ж так,
що, або повністю задовольняється один
із замовників (той, у стовпці якого знаходиться
заповнювана клітина), або повністю вивозиться
весь запас вантажу з однієї з баз (з тією,
в рядку якої знаходиться заповнювана
клітина).
У першому випадку ми можемо
виключити стовпець, що містить заповнену
на цьому кроці клітку, і вважати, що завдання
звелася до заповнення таблиці з кількістю
стовпців, на одиницю меншим, ніж було
перед цим кроком, але з тією ж кількістю
рядків і з відповідно зміненим запасом
вантажу на одній з баз (на тій базі, якою
було задоволено замовник на даному кроці).
У другому випадку
виключається рядок, що містить
заповнюють клітину, і вважається,
що таблиця звузилася на один
рядок при незмінній кількості
шпальт і при відповідній зміні
потреби замовника, у стовпці
якого знаходиться заповнювана клітина.
Починаючи зі спочатку даної
таблиці і повторивши m + n - 2 разів описаний крок, ми прийдемо
до "таблиці", що складається з одного
рядка і одного стовпця (інакше кажучи,
з однієї порожньої клітки). Іншими словами,
ми прийшли до завдання з однією базою
і з одним споживачем, причому потреби
цього єдиного замовника рівні запасу
вантажу на цій єдиній базі. Заповнивши
останню клітку, ми звільняємо останню
базу і задовольняємо потребу останнього
замовника. У результаті, здійснивши m + n – 1 кроків, ми і отримаємо шуканий
опорний план.
Зауваження. Може статися, що вже на деякій
(але не на останньому!) Кроці потреба чергового
замовника виявиться рівною запасу вантажу
на черговий базі. Тоді після заповнення
черговий клітини обсяг таблиці як би
одночасно зменшується на одні стовпець
і на один рядок. Але і при цьому ми повинні
вважати, що зменшення обсягу таблиці
відбувається або на один стовпець, а на
базі зберігається "залишок" рівний
нулю, або на один рядок, а у замовника
ще залишилася незадоволена "потреба"
в кількості нуля одиниць вантажу, яка
і задовольняється на одному з наступних
кроків. Цей нуль ("запас" або "потребою"
- байдуже) треба записати в чергову заповнюють
клітину на одному з наступних кроків.
Тому що при цьому виявляється рівною
нулю одна з базисних невідомих, то ми
маємо справу з виродженим випадком.
Різниця методів відшукання
першого опорного плану полягає у відмінності
способів набору заповнюваної клітини.