2018-02-14
1156
ЗАНЯТТЯ 1
Розробка математичної моделі лінійного програмування
та графоаналітичний метод її розв'язання.
Мета заняття – придбати практичні навички складання математичної моделі задачі лінійного програмування та її розв'язання графоаналітичним методом.
Завдання. Скласти математичну модель задачі та розв'язати її графоаналітичним методом.
Задача. Необхідно сформувати і спрямувати до сільськогосподарських районів А і В вантажно-транспортні загони для вивозу врожаю. Укомплектованість кожного загону технічними засобами та їх загальна кількість наведені в табл. 1.1. Необхідно визначити кількість вантажно-транспортних загонів, направлених до кожного району, забезпечивши максимальний вивіз врожаю з урахуванням добової продуктивності; значення надані в табл. 1.2.
Вказівки до виконання
За своїм варіантом в табл. 1.1 та 1.2 знайти вихідні дані. Варіант завдання в табл. 1.1 для сільськогосподарських районів відповідає останній цифрі номера залікової книжки, а для загальної кількості технічних засобів – передостанній; в табл. 1.2 варіант завдання визначається цілою частиною результату, отриманого від ділення суми двох останніх цифр номера залікової книжки на два.
|
|
|
Виконання завдання здійснюється у такій послідовності:
1. Складання математичної моделі задачі.
1.1. Вибір параметрів управління.
Візьмемо за параметри управління кількість загонів, які треба відправити до сільськогосподарських районів А та В. Їх кількість невідома, тому нехай x1 − кількість загонів, спрямованих до району А;
x2 − кількість загонів, спрямованих до району В.
Вектор X=(x1; x2) – вектор управління або план, і знайти його треба такий, щоб забезпечити максимальне виконання завдання згідно з умовою задачі.
1.2. Встановлення критерія оптимальності.
При розв’язанні даної задачі нам потрібно забезпечити максимальний вивіз врожаю із с/г районів А і В. Добова продуктивність по вивозу врожаю для кожного загону, спрямованого до району А позначається р 1, а така ж характеристика для району В – р2, значення яких наведені у таблиці 1.2.
Тоді із району А за добу буде вивезено врожаю p1 x1, а із району В – p2 x2.
Згідно з умовою задачі нам необхідно знайти такі x1 та x2, щоб величина, яка дорівнює p1x1+p2x2 набувала свого максимального значення.
1.3. Складання системи обмежень та вираження цільової функції.
Крім продуктивності в задачі надаються умови, яким повинна відповідати укомплектованість кожного вантажно-транспортного загону та загальна кількість технічних засобів. Ми маємо чотири види технічних засобів, їх кількість у кожному загоні j -го району 
позначимо 
, а загальну кількість машин i -го виду, 
позначимо bi , тому
|
|
|
Ці нерівності, які задаються умовою задачі і складають систему обмежень для невідомих x1, x2, а нерівностей у системі буде стільки, скільки видів машин:
Цільовою функцією виберемо ту функцію, екстремальне значення якої ми бажаємо знайти. У нашій задачі необхідно знайти максимальний вивіз врожаю, тобто максимальне значення функції
Детальніше, потрібно отримати такий план 
, який визначає кількість загонів, спрямованих до району А та В таку, що значення функції 
буде максимальним.
1.4. Запис математичної моделі задачі.
2. Розв'язання задачі лінійного програмування графоаналітичним методом.
2.1. Побудова багатокутника системи обмежень та лінії рівня цільової функції.
Побудуємо область припустимих значень для невідомих x1 та x2, яка об’єднує всі умови, яким вони задовольняють. Ця множина Ώ для 
графічно буде мати вигляд багатокутника (у загальному вигляді).
2.2. Визначення напрямку переміщення лінії рівня цільової функції.
Напрямок максимального зростання функції Z визначається вектором градієнтного напрямку 
тобто
Градієнтний вектор завжди перпендикулярний лінії рівня цільової функції Z.
2.3. Знаходження оптимальних значень параметрів управління.
а) побудувати вектор 
б) побудувати пряму, яка проходить через початок координат та перпендикулярна вектору 
− лінію рівня цільової функції;
в) переміщати лінію рівня цільової функції у напрямку вектора ;
г) функція Z набуває свого максимального значення в останній точці зустрічі лінії рівня з багатокутником рішень. Це буде вершина багатокутника рішень, або його сторона, координати якої і будуть рішенням задачі.
2.4. Перевірка аналітичне здобутих значень параметрів управління розв'язанням відповідної системи рівнянь.
3. Написати висновок виконання практичного заняття, в якому вказати знайдені значення невідомих та максимального значення функції Z.
Таблиця 1.1 – Кількість технічних засобів вантажно-транспортного загону та загальна їх кількість
| Варіант | Технічні засоби | |||
| Автомобіль | Техдопомога | Навантажений механізм | Меддопомога | |
| Сільськогосподарський район А | ||||
| 0 | 100 | 2 | 1 | 1 |
| 1 | 50 | 1 | 1 | 1 |
| 2 | 75 | 1 | 1 | 1 |
| 3 | 150 | 3 | 2 | 2 |
| 4 | 60 | 1 | 1 | 1 |
| 5 | 80 | 2 | 1 | 1 |
| 6 | 90 | 2 | 1 | 1 |
| 7 | 70 | 1 | 1 | 1 |
| 8 | 120 | 3 | 2 | 2 |
| 9 | 110 | 2 | 2 | 1 |
| Сільськогосподарський район В | ||||
| 0 | 150 | 3 | 2 | 2 |
| 1 | 75 | 1 | 1 | 1 |
| 2 | 100 | 2 | 1 | 1 |
| 3 | 100 | 2 | 1 | 1 |
| 4 | 90 | 2 | 1 | 1 |
| 5 | 120 | 3 | 2 | 2 |
| 6 | 60 | 1 | 1 | 1 |
| 7 | 120 | 3 | 2 | 2 |
| 8 | 80 | 2 | 1 | 1 |
| 9 | 70 | 1 | 1 | 1 |
| Загальна кількість технічних засобів | ||||
| 0 | 1200 | 18 | 16 | 8 |
| 1 | 1000 | 16 | 17 | 7 |
| 2 | 900 | 14 | 15 | 9 |
| 3 | 1500 | 19 | 12 | 10 |
| 4 | 1100 | 17 | 10 | 8 |
| 5 | 1400 | 18 | 11 | 7 |
| 6 | 800 | 14 | 9 | 8 |
| 7 | 950 | 15 | 10 | 9 |
| 8 | 1050 | 16 | 12 | 10 |
| 9 | 1150 | 17 | 14 | 12 |
Таблиця 1.2 – Продуктивність добова вантажно-транспортних загонів
| Сільськогосподарський район | Варіант | |||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| А | 5,0 | 6,0 | 4,5 | 5,5 | 3,5 | 2,5 | 6,5 | 4,0 | 5,5 | 3,0 |
| В | 2,5 | 3,0 | 3,5 | 4,0 | 5,0 | 4,5 | 3,0 | 5,5 | 2,5 | 4,5 |
Контрольні запитання
1. Мета застосування економіко-математичних методів в управлінні та організації транспортного виробництва.
2. Перелік задач транспортного виробництва, що розв'язуються з використанням математичних методів.
3. Оптимальне рішення.
4. Значення понять лінійне, нелінійне та динамічне програмування.
5. Структура математичної моделі загальної задачі лінійного програмування.
6. Основні етапи побудови математичної моделі.
7. Геометричні образи структурних елементів математичної моделі.
8. Порядок розв'язання загальної задачі лінійного програмування.
9. Альтернативні оптимальні рішення.
ЛІТЕРАТУРА [1, 3, 4, 5]
ЗАНЯТТЯ 2
Рішення задачі лінійного програмування симплекс-методом.
|
|
|
Мета заняття – придбати практичні навички рішення задач лінійного програмування симплекс-методом, використовуючи симплекс-таблицю.
Завдання. Вирішити симплекс-методом задачу лінійного програмування, використовуючи симплекс-таблиці. Знайти додаткові значення змінних 
які спрямовують в максимум лінійну форму (2.2) при умовах (2.1).
(2.1)
(2.2)
Вказівки до виконання
За своїм варіантом в табл. 2.1 знайти значення постійних величин виражень (2.1) та (2.2), де і – остання, j – предостання цифра номеру залікової книжки.
Таблиця 2.1 - Значення постійних величин
| 
| 
| 
|
| 
| 
| 
|
| 
| 
| 
|
| 
| 
| 
|
Виконання завдання здійснюється у такій послідовності:
1. Записати систему обмежень для невідомих у канонічному вигляді.
Введемо додаткові змінні 
до кожної нерівності системи для того, щоб записати їх у вигляді рівнянь.
Якщо кожне обмеження має змінну, яка входить до лівої частини рівняння з коефіцієнтом 1, а до всіх інших обмежень – з коефіцієнтом 0, то ця система обмежень представлена у переважному виді. Для нашої задачи система обмежень має переважний вигляд відносно змінних .
2. Скласти опорний план.
Якщо усі змінні, крім переважних прирівняти до 0, то переважні змінні будуть дорівнювати правим частинам рівнянь системи обмежень 
. Згідно з теоремою о структурі координат базисного рішення отримане рішення (план) буде опорним.
– базисне рішення,
– базисні змінні,
– вільні змінні.
3. Симплекс – таблиця.
Записати усі дані до симплекс – таблиці, основна частина якої складається з коефіцієнтів при основних змінних усіх рівнянь і одиничної матриці.
Симплекс-метод складається з математичних кроків, при яких від початкового опорного плану ми рухаємось до знаходження такого рішення, при якому функція цілі отримає своє максимальне значення, – знаходимо оптимальний план.
4. Кроки метода:
а) Оцінки змінних.
До симплекс-таблиці нижче додають рядок (індексний рядок), в яку записують оцінки змінних, обчислені за формулами:
, де 
– коефіцієнти при базисних змінних у функції цілі;
|
|
|
– вектор вільних членів у системі обмежень.
дає значення функції цілі для наданого плану 
.
; − оцінки вільних змінних, де
− вектор коефіцієнтів при цій змінній у системі обмежень;
– коефіцієнт при цій змінній у запису функції цілі.
Оцінки базисних змінних завжди дорівнюють 0.
Отриманий план дає функції цілі максимальне значення 
, якщо усі оцінки вільних змінних невід'ємні.
Тобто вести обчислення у симплекс-методі потрібно до тих пір, доки усі оцінки вільних змінних не стануть ≥ 0.
б) Розв'язуючий стовпчик та рядок.
Після того, як знайдені 
із значень 
обираємо найменше, відповідний стовпчик називають розв'язуючим.
Щоб отримати розв'язуючий рядок треба елементи стовпчика правих частин поділити на додатні елементи розв'зуючого стовпчика та серед отриманих часток обираємо найменшу:
.
Це число буде відповідати деякому рядку 
, цей рядок називають розв’язуючим.
При рішенні задачі на max Z, якщо у розв'язуючому стовпчику нема жодного додатного елемента, то функція цілі Z необмежена зверху та немає max значення.
Змінну 
, яка відповідає розв'язуючому стовпчику треба ввести до складу базисних змінних, а змінну 
виводять із базису. Таким чином, не змінив нульові значення інших вільних змінних, потрібно збільшити функцію Z за рахунок зменшення значення .
в) Друга симплекс-таблиця.
Для нових базисних змінних будують нову симплекс-таблицю, аналогічну першій. Щоб її заповнити, елементи розв'язуючого рядка ділять на розв'язуючий елемент, та результат записують у відповідний рядок, у тій клітинці, де стояв розв'язуючий елемент, тепер буде 1. Інші елементи розв'язуючого стовпчика будуть дорівнювати 0, так як − базисна.
Щоб знайти інші елементи нової симплекс-таблиці застосовують правило прямокутника:
в початковій таблиці виділяють прямокутник, вершинами якого є потрібні для обчислення елементи;
діагональ,яка містить розв’язуючий та шуканий елементи називають головною, а іншу – побічною;
від добутку елементів головної діагоналі віднімають добуток кутових елементів побічної діагоналі та отримане число ділять на розв’язуючий елемент.
г) Отримавши нову симплекс-таблицю з нею поступають відповідно описаному методу.
Обчислення роблять до тих пір, доки усі не стануть ≥0.
За даними останньої симплекс-таблиці визначити значення змінних, які забезпечують оптимальне розв'язання.
Контрольні запитання
1. Як будується симплекс-таблиця?.
2. Як визначаються ключовий стовпець, рядок і число?
3. Як визначаються числа головного рядку?
4. Правила визначення похідних чисел.
6. Ознака оптимального рішення.
7. Що визначають в результаті рішення числа в стовпці вільних членів і число в клітинці індексного рядку стовпця вільних членів?
ЛІТЕРАТУРА [1, 3, 5]
ЗАНЯТТЯ З
Укладання вихідного припустимого плану перевезень
вантажів за допомогою методу північно-західного кута, мінімального елементу рядка або стовпця та методу апроксимації Фогеля.
Мета заняття –придбати практичні навички побудування вихідного припустимого плану перевезень вантажів декількома способами.
Завдання. Скласти вихідний припустимий план перевезень вантажів, користуючись способом північно-західного кута, мінімального елементу строки та апроксимації Фогеля.
Задача. Визначена транспортна задача.
Мається чотири постачальники 
і п'ять споживачів 
вантажу. Наявність вантажу у відправників 
потреба його у споживачів 
та відстані між ними наведені в табл. 3.1. Потрібно знайти вихідний план перевезень вантажів за допомогою декількох методів побудови початкових планів.
Таблиця 3.1 – Наявність та потреба вантажу. Відстані поміж постачальниками та споживачами
| Сільськогосподарський район | Споживач | Наявність | |||||||
| 
| 
| 
| 
| 
| 
| 
| вантажу,
| |
| А 1 | 7+ i | 2+ j | 4+ i | 11– j | 6+ j | 3+ i | 9+ j | 14– i | 75+10 j |
| А 2 | 2+ j | 6+ i | 3+ j | 12– i | 7+ i | 10– j | 5+ j | 4+ j | 220–5 j |
| А 3 | 8+ j | 12– i | 9+ j | 4+ i | 13– j | 8+ i | 7+ i | 10+ j | 150–5 j |
| А 4 | 18– i | 6+ j | 12+ i | 17– j | 15– i | 13– j | 4+ i | 2+ i | 80+15 i |
| А 5 | 16– j | 18– i | 15– i | 4+ i | 5+ j | 7+ j | 3+ i | 21– j | 175–10 i |
| А 6 | 19– j | 6+ i | 21– j | 2+ j | 23– i | 17– i | 14– j | 12– i | 150–5 i |
Потреб вантажу, 
| 60+15 i | 80+5 i | 120–5 i | 140–5 i | 70+5 j | 130–5 j | 90+10 j | 160–10 j | 850 |
Вказівки до виконання
Завдання виконується у такій послідовності:
1. За даними табл. 3.1 скласти транспортну матрицю.
2. Скласти вихідний припустимий план транспортної задачі методом північно-західного кута. Починаючи з клітинки (1;1) порівнюємо наявність та потреби вантажу, заповнюємо її, відповідно переходимо до клітинки (2;1) або (1;2). З тією клітинкою робимо так само, як і з клітинкою (1;1).
3. Скласти вихідний припустимий план транспортної задачі методом мінімального елементу строки. Розглядаючи по черзі кожну строку транспортної матриці, знаходимо у ній мінімальний елемент; порівнюємо наявність та потреби вантажу відповідно до цього елементу, заповнюємо клітину і переходимо до іншого мінімального елементу у цій строчці або до іншої строки.
4. За даними табл. 3.1 скласти транспортну матрицю, яка відрізняється від попередньої тим, що має додатковий рядок та стовпець різниць.
5. Скласти вихідний припустимий план способом апроксимації Фогеля. а) Знайти різниці для кожного рядка і стовпця між двома найменшими значеннями цільових елементів (відстаней) та записати їх у відповідні клітин стовпця та рядка різниць.
б) Серед усіх різниць вибрати найбільшу. В стовпці або рядку з найбільшою різницею знайти клітину з найменшими значеннями цільового елементу та заповнити її максимально можливою кількістю вантажу. За наявності двох та більш однакових значень найбільшої різниці знайти та завантажити “сідлову” клітину. Якщо “сідлова” клітинка відсутня, то необхідно визначити додаткові різниці.
в) Заповнити клітинку максимально можливою кількістю вантажу з найменшим значенням цільового елементу рядка або стовпця, що має найбільшу додаткову різницю. В результаті хоча б один стовпець або один рядок будуть виключені з подальшого розгляду.
г) Скорегувати наявність вантажу або його потреби.
д) Повторювати наведені вище операції, доки весь вантаж не буде розподілений.
6. Отриманий припустимий вихідний план з використанням-способу апроксимації Фогеля перевірити на оптимальність.
7. Зробити висновок на рахунок того, який із побудованих планів ближче до оптимального, тобто, при якому плані значення функції цілі найменше.
Контрольні запитання
1. Яким чином заповнюють клітини рядку та стовпця різниць?
2. Що таке “сідлова” клітина?
3. Як визначається додаткова різниця?
ЛІТЕРАТУРА [1]
ЗАНЯТТЯ 4
Рішення транспортної задачі лінійного програмування
розподільчим методом.
Мета заняття – закріплення практичних навиків рішення транспортної задачі розподільчим методом.
Завдання. Скласти оптимальний план перевезень вантажів розподільним методом.
Задача. Постановка задачі та вихідні дані такі ж, як в попередньому занятті. Необхідно скласти вихідний припустимий план перевезень вантажів способом апроксимації Фогеля. Відштовхуючись від вихідного плану перевезень, знайти оптимальний план розподільчим методом.
Вказівки до виконання
Завдання виконується у такій послідовності:
1. За даними табл. 3.1 скласти транспортну матрицю, вважаючи “ i ” – дорівнюється останній, а “ j ” – передостанній цифрі номеру залікової книжки.
2. Знайти оптимальний план транспортної задачі.
Побудувати вихідний припустимий план за допомогою одного із засобів (за вказівкою викладача): північно-західного куту, мінімального значення цільового елементу рядка або стовпця, методу апроксимації Фогеля.
3. Перевірити кількість завантажених клітин, яких повинно бути у кількості m+n-1=6+8-1=13. Якщо завантажених клітин менше, то треба додати нульові завантаження клітин.
4. Розрахувати допоміжні числа (потенціали) рядків і стовпчиків 
та 
), використовуючи формулу
для завантажених клітин.
5. Знайти потенціали не завантажених клітин
.
Згідно з теоремою об умові оптимальності, для не завантажених клітин повинна виконуватися нерівність 
, тобто 
.
Якщо є клітини для яких 
, то отриманий план не оптимальний, і від нього треба перейти до нового опорного плану.
5. Перерозподілити завантаження кліток.
Вибрати клітину, для якої виконується умова 
. Цю клітину треба додати до плану перевезень, а іншу вивести із плану. Для цього будують цикл та роблять перенос по циклу, перерозподіляють завантаження кліток і знов виконують перевірку нового плану на оптимальність. Процес буде тривати доки не буде знайдений оптимальний план. Після кожної ітерації визначити значення транспортної роботи.
Контрольні запитання
1. Склад математичної моделі транспортної задачі лінійного програмування.
2. Методи розв'язання задач лінійного програмування.
3. Сутність і алгоритм розв'язання транспортної задачі лінійного програмування розподільчим методом.
4. Способи побудови початкового припустимого плану при розв'язуванні транспортної задачі розподільчим методом.
5. Перевірка припустимого плану на оптимальність.
6. Поліпшення неоптимального плану.
7. Основні типи транспортних задач, що вирішуються розподільчим методом.
8. Транспортна задача відкритого типу.
9. Визначення допоміжних чисел (потенціалів) рядків і стовпчиків матриці.
10. Перерозподіл завантаження кліток матриці. Побудова контуру.
11. Знаходження потенціальних не завантажених кліток.
ЛІТЕРАТУРА [1,2, 3, 5]
ЗАНЯТТЯ 5
