n1-n10-величина попиту,шт.
Черкаси ЧДТУ 2007
МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ
ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ
УНІВЕРСИТЕТ
МЕТОДИЧНІ ВКАЗІВКИ
ДО ВИКОНАННЯ ЛАБОРАТОРНИХ РОБІТ
ПО КУРСУ:
“ДОСЛІДЖЕННЯ ОПЕРАЦІЙ”
ДЛЯ СТУДЕНТІВ СПЕЦІАЛЬНОСТІ
“МЕНЕДЖМЕНТ ОРГАНІЗАЦІЙ”
ДЕННОЇ ТА ЗАОЧНОЇ ФОРМИ НАВЧАННЯ
Затверджено на засіданні
кафедри менеджменту
протокол №9 від 20.04.2007 р.
та Методичною радою ЧДТУ
протокол №___ від ______2007р.
Черкаси ЧДТУ 2007
Укладач Чижиков В.О., к.т.н., доцент
Рецензент Хомяков В.І., д.т.н., професор
Методичні вказівки до виконання лабораторних робіт по курсу “Дослідження операцій” для студентів спеціальності “Менеджмент організацій” денної та заочної форми навчання
/Укл. В.О.Чижиков/ Черкаси: ЧДТУ, 2007. -___с.
Методичні вказівки містять необхідний для виконання лабораторних робіт, консультаційний матеріал, вимоги до виконання і оформлення відповідних елементів робіт, а також контрольні питання.
Для студентів 2-го курсу денної (заочної) форми навчання спеціальності „Менеджмент організацій”
Черкаський державний технологічний університет, 2007
ВСТУП
Дані методичні вказівки призначені для виконання лабораторних дисциплін з дисципліни“Дослідження операцій”. В процесі виконання лабораторних робіт, які приведені в даних вказівках , студенти опрацюють проблематику лінійного програмування та мережевих задач .
Методичні вказівки побудовані таким чином , щоб студенти в максимально можливій мірі могли самостійно вирішувати поставлені задачі. З цією метою в описах приведені основні теоретичні відомості з відповідної тематики лабораторних робіт, алгоритми вирішення типових задач , приведені мета, задачі роботи та порядок їх використання.
ЗАГАЛЬНІ МЕТОДИЧНІ ВКАЗІВКИ
1.Лабораторні роботи кожний студент виконує самостійно на індивідуальному робочому місці з оформленням та подачою протоколу.
2.Звіт про виконану лабораторну роботу оформлює та захищає кожний студент індивідуально в термін не пізніше дня проведення наступної лабораторної роботи.
3.В процесі підготовки до виконання лабораторної роботи студент вивчає дані методичні вказівки та відповідні розділи із рекомендуємої літератури.
4.Для отримання дозволу на виконання лабораторної роботи студент повинен дати правильні відповіді викладачу на контрольні запитання, знати зміст та порядок виконання роботи.
Лабораторная работа N0 1
Тема:Аналіз приймаємих ріщень на чутливість на базі графічного рішення задач лінійного програмування (ЛП).
Мета роботи:Придбати навички основ аналізу задач ЛП на базі графічного методу.
Задачі роботи:засвоїти основи постановки задач ЛП; навчитися використовувати прикладні пакети програм для рішення задач ЛП.
Студент повинен знати:Суть проблематики лінійного програмування, основні етапи рішення оптимізаційних задач.
Знаряддя дослідження:Персональний комп’ютер з процесором не нижче 486.
Об’єкт дослідження:Виробничий процес.
1.1 Загальні відомості
ЛП - це розділ математичного програмування в якому розглядаються методи рішення екстремальних задач з лінійним функціоналом та лінійними обмеженнями, яким повинні задовільняти пошукові змінні.
Рішення людина приймає завжди у всіх сферах своєї діяльності. Важлива область прийняття рішення пов’язана з проблематикою технічних об’єктів (ТО) на всих всих етапах їх життєвого циклу. Темпи розвитку ТО стрімко зростають , відповідно збільшується і ціна помилково прийнятого рішення.
Якщо прийняти що метою виробництва являється перетворення ресурсів у готову продукцію, то значна частина задач , які виникають у ході виробництва ,можна розглядати як задачі розподілу ресурсів - матеріальних, фінансових тощо.
Досить широке коло задач подібного типу допускає формуліровку у вигляді задачі лінійного програмування . В якості критеріїв в даному випадку виступають загальні витрати на транспортування, витрати часу, матеріалів, комплектуючих, витрати на реконструкцію існуючих ТО і т.п. Обмеження звичайно носять характер нерівностей, які відзеркалюють, зокрема для технологічних систем,можливості засобів транспортування, продуктивність обладнання, кількість постачаємих матеріалів та комплектуючих. Можливості оптимізації системи в цілому за допомогою метода ЛП дозволяють на самому ранньому етапі проектування проглянути множину різних варіантів і отримати досить корисну додадкову інформацію для її структурного синтезу.Важливе прикладне значення теорії ЛП має для оптимізації технологічних процесів (ТП). Так, в сучасній технології радіо-електронної апаратури за допомогою ЛП можна вирішувати задачу синтезу речовин з високою гологеністю складу. На базі ЛП можна також вирішувати задачі побудови кінематичних вузлів із заданими властивостями, визначити оптимальні режими різання і ряд інших прикладних задач виробництва.
Важливе значення для розуміння суті ЛП має графічний метод, який дає конкретну інаглядну інтерпретацію процесу оптимізації, а також дозволяє проілюструвати прийоми аналізу моделей на чутливість.
Перший крок при використанні графічного методу заключається в геометричному представленні допустимих рішень. На слідуючому етапі будують лінію, яка ототожнює функцію мети, потім переміщують її по нормалі в напрямку покращення початкового значення до тих пір , поки воно не переміститься в область недопустимих рішень.При цьому крайня кутова точка , якої торкається пряма функції мети і буде визначати координати оптимального рішення задачі ЛП.
Математична модель задачі ЛП буде мати вигляд:
L = c1x1+c2x2+...+ cnxn
за умов
a11x1+a12x+...a1nxn=b1
a21x1+a22x2+...+a2nxn=b2
am1x1+am2x2+...+amnxn=bm
xj 
0, j=1,2,....,n,
де аij,bi,cj-задані постійні величини. При цьому припустимо , що bi j 0 (i=1,2,...,m) і m<n.
Наявність оптимального рішення дозволяє провести аналіз моделі на чутливість при внесенні відповідних змін в обмеження та цільову функцію.
Порядок виконання роботи
1.2.1 Ознайомитися з матеріалом даних методичних вказівок.
1.2.2 Опрацювати лекційний матеріал та літературні джерела ( ) відносно постановки та аналізу задач ЛП.
1.2.3 Розробити математичну модель отриманного варіанту.
1.2.4 Засвоїти інструкції по використанню пактів „ЕКСТРЕМУМ”, „TORA”.
1.2.5. Знайти за допомогою ЕОМ графічне рішення задачі ЛП.
1.2.6 Провести аналіз моделі на чутливість.
1.2.7 Провести аналіз отриманних результатів.
1.2.8 Зробити висновок по роботі.
Завдання до роботи
Підприємство після виконання основної виробничої програми має запаси зекономленної сировини 4 видів - S1,S2,S3,S4 відповідно в кількостях b1,b2,b3,b4 умовних одиниць. Із цієї сировини може бути виготовленно 2 види виробів - P1 i P2. Відомі: аij - кількість одиниць Si виду сировини, яка іде на виготовлення одиниці Pi виду виробу, та Сj - дохід, який отримується від реалізації однієї одиниці кожного виду виробу. Всі приведенні величини подані в таблиці 1.1.
Задача полягає в тому, що необхідно скласти такий план випуску продукції, при якому дохід підприємства від реалізації всієї продукції був би максимальним.
Таблиця 1.1
| N0 вар | Види сировини | Запаси сировини | Витрати сировини на виріб , P1 | Витрати сировини на виріб , P2 |
| S1 | ||||
| S2 | ||||
| S3 | ||||
| S4 | ||||
| Прибуток від реалізації 1 виробу |
| S1 | ||||
| S2 | ||||
| S3 | ||||
| S4 | ||||
| Прибуток від реалізації 1 виробу |
| S1 | ||||
| S2 | ||||
| S3 | ||||
| S4 | ||||
| Прибуток від реалізації 1 виробу |
| S1 | ||||
| S2 | ||||
| S3 | ||||
| S4 | ||||
| Прибуток від реалізації 1 виробу |
| S1 | ||||
| S2 | ||||
| S3 | ||||
| S4 | ||||
| Прибуток від реалізації 1 виробу |
| S1 | ||||
| S2 | ||||
| S3 | ||||
| S4 | ||||
| Прибуток від реалізації 1 виробу |
| S1 | ||||
| S2 | ||||
| S3 | ||||
| S4 | ||||
| Прибуток від реалізації 1 виробу |
| S1 | ||||
| S2 | ||||
| S3 | ||||
| S4 | ||||
| Прибуток від реалізації 1 виробу |
| S1 | ||||
| S2 | ||||
| S3 | ||||
| S4 | ||||
| Прибуток від реалізації 1 виробу |
| S1 | ||||
| S2 | ||||
| S3 | ||||
| S4 | ||||
| Прибуток від реалізації 1 виробу |
| S1 | ||||
| S2 | ||||
| S3 | ||||
| S4 | ||||
| Прибуток від реалізації 1 виробу |
| S1 | ||||
| S2 | ||||
| S3 | ||||
| S4 | ||||
| Прибуток від реалізації 1 виробу |
1.4 Зміст звіту про виконану лабораторну роботу
1.4.1 Мета роботи.
1.4.2 Короткі теоретичні відомості.
1.4.3 Алгоритм вирішення задач ЛП.
1.4.4 Математична модель відповідного варіанту задачі.
1.4.5 Результат рішення задачі на моделі.
1.4.6 Аналіз отриманих результатів.
1.4.7 Висновки по роботі.
1.4.8 Перелік використанної літератури.
Контрольні питання
1. Чи необхідно знати всі рішення в екстремальних точках багатокутника допустимих рішень для пошуку оптимального рішення ?
2. Що означає термін “Оптимальне рішення”?
3. В яких випадках ресурс є дефіцитним ?
4. Чим може бути викликана відсутність допустимого рішення задачі ЛП ?
5. Поясніть суть альтернативних рішень ?
6. Поясніть при яких умовах може мати місце необмеженне рішення ?
7. Поясніть першу задачу аналізу на чутливість ?
8. Як визначається цінність ресурса ?
9. Поясніть третю задачу аналізу на чутливість ?
10. Як впливають на оптимальне рішення надлишкові обмеження ?
Лабораторна робота N0 2
Тема:Рішення задач лінійного програмування (ЛП) симплекс методом та інтерпритація отриманних результатів.
Мета роботи:Придбати навички вирішення задач ЛП симплекс-методом.
Задачі роботи:Опрацювати алгоритм алгебраїчного вирішення задач ЛП; навчитися вирішувати задачі ЛП за допомогою ЕОМ, та вірно інтерпретувати отриманні результати.
Студент повинен знати:Постановку задачі у вигляді моделі ЛП; порядок проведення вихідної моделі ЛП до стандартного вигляду; алгоритм симплекс-методу.
Знаряддя дослідження:Персональній комп’ютер з процесором не нижче 486.
Об’єкт дослідження:Організаційно-технічні питання розробки та використання технічних об’єктів.
1.1 Загальні відомості
За допомогою графічного методу можна вирішувати задачі ЛП з двома змінними. При більшому числі змінних необхідно використовувати алгебраїчний апарат, в основі якого лежить симплекс метод.
Процес рішення задачі ЛП симплекс-методом носить ітераційний характер; однотипові обчислювальні процедури у визначеній послідовності повторюються до тих пір, поки не буде отримане оптимальне рішення.Рішення реальних задач базується на використанні обчислювальної техніки. Для використання загального методу вирішення задач ЛП відповідні моделі повинні бути представлені в стандартній формі де:
1)всі обмеження запишуться у вигляді рівностей з невід’ємною правою
частиною;
2) значення всих змінних моделі невід’ємні;
3) цільова функція підлягає максимізації або мінімізації.
Обчислювальна процедура симплекс-методу включає слідуючі основні кроки:
Крок0
Визначають початкове допустиме базисне рішення.
Крок1
Із числа поточних небазисних змінних вибираються включаєма в новий базис змінна,збільшення якої забезпечує покращення значення цільової функції.Якщо такої змінної нема, обчислення закінчують,поскільки поточне рішення оптимальне. В іншому випадку робиться перехід до кроку 2.
Крок2
Із числа змінних поточного базису вибирається виключаєма змінна.
Крок3
Визначається нове базисне рішення.Здійснюється перехід до кроку1.Нове базисне рішення находитьсяметодом виключення змінних,або методом Гаусса-Жордана.
Після того як буде знайдено оптимальне рішення поставленої задачі ЛП, необхідно приділити основну увагу інтерпритації та аналізу отриманих результатів.Із остаточної симплекс-таблиці або безпосередньо,або за допомогою простих додаткових обчислень можна отримати інформацію відносно оптимального рішення ;статусу ресурсу; цінності кожного ресурсу;чутливості оптимального рішення до змін запасів ресурсів,варіацій коефіцієнтів цільової функції та інтенсивності використання ресурсів.
Порядок виконання роботи
2.1.1. Ознайомитися з матеріалом даних методичних вказівок.
2.1.2 Опрацювати лекційний матеріал та літературні джерела ( ) відносно алгебраічного методу вирішення та задач ЛП.
2.1.3.Вивчити можливості та порядок використання пакету прикладних програм L PROG, L PG та QSB для вирішення задач ЛП симплекс-методом.
2.1.4. Розробити математичні моделі ЛП зазначеної задачі і вирішити її за допомогою пакета прикладних програм.
2.1.5. Дати інтерпритацію отриманих результатів, відповідно слідуючої послідовності:
Оптимальне рішення
Таблиця 2.1
| Управляємі змінні | Оптимальне значення | Рішення |
| Хв | ||
| . . . | ||
| Z |
Статус ресурсів
Таблиця 2.2
| Ресурс | Залишкова змінна | Статус ресурсів |
| . . . | ||
Цінність ресурсу
Таблиця2.3
| Базисні змінні | х1,х2,х3...хn | Рішення |
| . . . | ||
Максимальні зміни запасу
Таблиця 2.4
| Рівняння | Значення елементів правої частини на відповідну ітерацію 0 | Значення елементів правої частини на відповідну ітерацію 1 | Значення елементів правої частини на відповідну ітерацію К | Оптимум |
| Z | ||||
| m |
Діапазони зміни правих частин обмежень
Таблиця 2.5
| Обмеження | Нижня межа | Поточне значення | Верхня межа |
| . . | |||
| m |
Максимальні зміни коефіцієнтів питомої вартості витрат
Таблиця 2.6
| Змінна | Нижня межа | Поточне значення | Верхня межа |
| х1 | |||
| х2 | |||
| х3 | |||
| . | |||
| хn |
Задача 1
Підприємство випускає n видів продукції (виробів) . В процесі виробництва використовується m технологічних операцій та k видів сировини, варіанти використання яких приведені в таблиці 2.7, 2.8
Таблиця 2.7
| Тип операції | Тривалість технологічних операцій при виготовленні 1 виробу кожного виду | Макс. можли вий ресурс хв | |||||||||
| V1 | V2 | V3 | V4 | V5 | V6 | V7 | V8 | V9 | V10 | ||
| - | - | ||||||||||
| - | - | - | - | ||||||||
| - | - | - | - | ||||||||
| - | - | - | |||||||||
| - | - | - | - | ||||||||
| - | - | - | |||||||||
| - | - | - | - | ||||||||
| - | - | - | |||||||||
| - | - | - | |||||||||
| - | - | - | |||||||||
| - | - | - | - | ||||||||
| - | - | - | - | ||||||||
| - | - | - | - | - | |||||||
| - | - | - | |||||||||
| - | - | - | - |
Таблиця 2.8
| Вихідний продукт | Витрати вихідних продуктів на один виріб кожного виду. | макс. можливий запас | |||||||||
| V1 | V2 | V3 | V4 | V5 | V6 | V7 | V8 | V9 | V10 | ||
| - | - | ||||||||||
| - | - | - | |||||||||
| - | - | - | |||||||||
| - | - | - | |||||||||
| - | - | ||||||||||
| - | - | - | |||||||||
| - | |||||||||||
| - |
Згідно контракту кількість виробів повина бути не меньше об’єму зазначеному в таблиці 2.9.
Таблиця 2.9
| N вар | Тип виробництва та його мінімальна кількість(у.о) | |||||||||
| V1 | V2 | V3 | V4 | V5 | V6 | V7 | V8 | V9 | V10 | |
| - | ||||||||||
| - | - | |||||||||
| - | ||||||||||
| - | ||||||||||
| - | - | |||||||||
| - |
Вивчення ринку збуту показало що очікуємий прибуток від реалізації однієї у. о. виробу Vi складає відповідну величину,яка приведина в таблиці 2.10.
Т аблиця 2.10
| Nвар | Прибуток від реалізації одиниці виробу Vj | |||||||||
| V1 | V2 | V3 | V4 | V5 | V6 | V7 | V8 | V9 | V10 | |
Який найбільш доцільний добовий об’єм виробництва кожного виду продукції?
Зміст звіту про виконану лабораторну роботу
1. Мета роботи.
2. Короткі теоретичні відомості.
3. Алгоритм вирішення задач ЛП.
4. Математична модель відповідного варіанту задачі.
5. Результат рішення задачі на моделі.
6. Аналіз отриманих результатів.
7. Висновки по роботі.
8. Перелік використанної літератури.
Контрольні питання
1.Поясніть алгоритм приведення вихідної моделі ЛП до стандартного виду?
2.Що включає в себе обчислювальна процедура симплекс методу?
3.Як знаходиться оптимальне рішення?
4.Поясніть метод Гаусса-Жордана?
5.Як визначається цінність ресурса?
6.За допомогою яких обчислень можна отримати інформацію відносно чутливості оптимального рішення до змін запасів ресурсів?
Лабораторна робота N3
Тема :Аналіз моделей оптимального використання виробничих потужностей.
Мета роботи:придбати навички використання двоїстих моделей для аналізу організаційно-технічних проблем виробництва технічної продукції.
Задачі роботи:опрацювати методику проведення аналізу моделей ЛП на чутливість,навчитися використовувати результати модельовання на базі двоїстих обчислювальних процедур для аналізу прямої задачі ЛП.
Студент повинен знати:алгоритм побудови двоїстої задачі ЛП,спі
ввідношення двоїстості,які характерезують зв’язок між прямою та двоїстою задачами ЛП,порядок використання співвідношень двоїстості в обчислювальних процедурах.
Знаряддя дослідження:Персональний комп’ютер з процесором не нижче 486.
Об’єкт дослідження:Виробничий процес.
3.1 Загальні відомості
Поняття двоїстості теорії ЛП являється виключно важливим в теоретичному відношенні а також має великий практичний інтерес поскількі використовується при розробкі та застосуванні ефективних методів аналізу моделей на чутливість.
Двоїста задача- це допоміжна задача ЛП, яка формулюється за допомогою визначенних правил безпосередньо із умов вихідної, або прямої задачі.При якому пряма задача повина бути записана у стандартному виді слідуючим чином:
(max або min)Z= 
сjxj
при обмеженнях aijxj=bi ,i=1,2,...m; j=1,2,...n, xj i 0.
В данній моделі до складу n змінних xi виключається також надлишкові та залишкові змінні.Тоді двоїста задача буде представлена у такому вигляді:
(max або min)Z= 
iyi
при обмеженнях
aijyi cj j=1,2,...n;
yi-не має обмеження по знаку.
Сумісний розгляд таких пар задач дозволяє проаналізувати вплив змін управляємих та неуправляємих змінних системи на значення цільової функції , проводити економічний аналіз розрахунків.
Порядок виконання роботи
3.2.1 Ознайомитися з матеріалом даних методичних вказівок.
3.2.2 Опрацювати лекційний матеріал та літературні джерела ( ) відносно постановки та аналізу задач ЛП.
3.2.3 Розробити математичну модель отриманного варіанту на базі вихідних данних лабораторної роботи N 2.
3.2.4 Засвоїти інструкції по використанню пакета прикладних програм “QSB”.
3.2.5 Вирішити двоїсту задачу на моделі за допомогою ЕОМ.
3.2.6 Провести аналіз отриманних результатів.
3.2.7 На базі двоїстих обчислень знайти :
- елементи Z-строчки оптимальної СТ прямої задачі;
елементи недостаючих стопчиків в оптимальній СТ прямої задачі;
- провести аналіз змін правих частин для вказаних викладачем бмежень прямої задачі;
-внести зміни у вихідному ЦФ прямої задачі (характер яких визначається викладачем) при поточних базисних змінних, знайти нові двоїсті оцінки і на їх базі підрахувати коєфіціенти Z-рівняння.
3.2.8 Зробити висновок по роботі.
3.3 Зміст звіту про виконану лабораторну роботу
3.3.1 Мета роботи.
3.3.2 Короткі теоретичні відомості.
3.3.3 Алгоритм переходу від прямої задачі до двоїстої .
3.3.4 Математична модель двоїстої задачі.
3.3.5 Результат рішення задачі.
3.3.6 Аналіз отриманих результатів.
3.3.7 Висновки по роботі.
3.3.8 Перелік використанної літератури.
Контрольні питання
1.Про що свідчить неоптимальність рішення прямої задачі по відношенню до допустимості рішення двоїстої задачі?
2.Коли доцільно використати двоїстий симплекс метод?
3.Що отримаємо ,якщо будемо вирішувати двоїсту до двоїстої задачу?
4.Як можна знайти ряд елементів поточної симплекс-таблиці, не використовуючи правила Гауса- Жордана?
5.Чим відрізняється оптимальне рішення прямої задачі від оптимального рішення двоїстої задачі?
6.Пояніть алгоритм переходу від прямої задачі до двоїстої?
7.Коли доцільно використовувати двоїсту задачу?
8.Чи можуть двоїсті змінні мати від’ємне значення?
9.Як можна знайти рішення прямої задачі вирішивши двоїсту?
10.Дайте економічну характеристику двоїстих змінних?
Лабораторна робота N04
Тема:Рішення транспортних задач .
Мета роботи:придбати навички по застосуванню транспортних моделей,їх рішенню та аналізу.
Задачі роботи: Навчитися використовувати ЕОМ для рішення транспортих задач; вияснити взаемо зв’язок транспортних задач та даних задач ЛП.
Студент повинен знати:Як скласти транспортну модель, алгоритм рішення транспортних задач.
Знаряддя дослідження:Персональній комп’ютер з процесором не нижче 486.
Обєкт дослідження:Організаційно-технічні питання виробництва та реалізації техніки .
4.1 Загальні відомості
Загальна постановка транспортної задачі складається у визначенні оптимального плану перевозки деякого однорідного грузу з m міст відправки у n міст призначення. Розглянемо транспорту задачу ,в якості критерія оптимальності якого взята мінімальна ціна всього грузу.Визначемо через cij тарифи перевозок одиниці груза з i-того пункта відправлення в j-тий пункт назначення, через ai -запаси груза в i-м пункті відправлення, через bj-потреби в грузі в j-м пункті назначення, а через xij-кількість одиниць груза, перевезеного із i-того пункта відправлення в j-тий пункт назначення. Тоді математична постановка задачі заключається у визначенні мінімального значення функції:
Z= 
cijxj 
min (4.1)
при обмеженнях
xij=ai, i= 
(4.2)
xij=bj j= 
xij 0, , i= ; j= ; (4.3)
ai= bj (4.4)
Оскільки змінні xij задовільняють системі лінійних рівнянь (4.2) і умові невід’ємності (4.3),забезпечується вивіз маючого груза з усіх місць відправки ,доставка необхідної кількості груза в кожний з пунктів назначення,а також виключаються зворотні перевозки.
Умова (4.4) є необхідним і достатнім для розв’язку транспортної задачі (4.1 -4.3).
Якщо умова (4.3) виконується , тоді модель такої транспортної задачі називається закритой. Якщо вказана умова (4.4) порушена , тоді модель транспортної задачі називається відкритой.
Рішення відкритой транспортної задачі зводиться до рішення закритої. Для цього в випадку збільшення запасів над потребами, тобто при ai> bj ,вводиться фіктивний (n+1)- пункт призначення з потребою bn+1= ai - bj і відповідні тарифи считаються рівними нулю :ci, n+1 =0,
i= . Для отриманої задачі виконується умова (4.4).
Аналогічно при ai < bj вводиться фіктивний (m+1)-й пункт відправки з запасом грузу am+1= bj- ai і тарифи покладають рівними нулю:cm+1,j=0 , j= .І умова (4.4) виконується.
Цими перетвореннями відкрита транспортна задача зводиться до закритої , з оптимального рішення якої виходить оптимальне рішення початкової задачі.
Порядок виконання роботи
4.2.1. Ознайомитися з матеріалом даних методичних вказівок.
4.2.2. Опрацювати лекційний матеріал та літературні джерела відносно постановки та аналізу транспортних задач.
4.2.3. Розробити математичну модель отриманого варіанту транспортної задачі.
4.2.4. Засвоїти інструкцію по використанню пакету прикладних програм “TRANSP”.
4.2.5. Вирішити вихідну задачу класичним симплекс-методом.
4.2.6. Вирішити вихідну задачу за допомогою транспортної моделі.
4.2.7. Провести аналіз отриманих результатів.
4.2.8. Зробити висновки по роботі.
Завдання до роботи
Заводи приладобудівної фірми розташовані в m містах.Основні центри розподілу продукції зосередженні в n інших містах.Щоквартальні об’єми виробництва m заводів щоквартального попиту в n центрах розподілу приведені відповідно в таблиці 1 і таблиці 2.
Таблиця 1
| N варианту | m1 | m2 | m3 | m4 | m5 | m6 | m7 |
m1-m7-об’єми виробництва,шт.
Таблиця 2
| N варианту | n1 | n2 | n3 | n4 | n5 | n6 | n7 | n8 | n9 | n10 |
n1-n10-величина попиту,шт.
Вартість перевезення одного приладу на 1км дорівнює приблизно 5коп. Відстань в км між заводами та центрами приведенні в таблиці3.
Таблиця 3
| m/n | n1 | n2 | n3 | n4 | n5 | n6 | n7 | n8 | n9 | n10 |
| m1 | ||||||||||
| m2 | ||||||||||
| m3 | ||||||||||
| m4 | ||||||||||
| m5 | ||||||||||
| m6 | ||||||||||
| m7 |
Необхідно визначити найбільш доцільну кількість продукції ,яку необхідно перевезти із пункта mi в пункт nj з тим ,щоб витрати на перевезення були мінімальними.
4.4 Зміст звіту про виконану лабораторну роботу
1. Мета роботи.
2. Короткі теоретичні відомості.
3. Алгоритм вирішення транспортної задачі.
4. Математична модель відповідного варіанту задачі.
5. Результат рішення задачі на моделі.
6. Аналіз отриманих результатів.
7. Висновки по роботі.
8. Перелік використанної літератури.
Контрольні питання
1.Чи можна завжди збалансувати транспортну модель?
2. Коли необхідно використовувати фіктивні вихідні пункти та фіктивні пункти призначення?
3.Яка основна умова застосування методу рішення транспортної задачі?
4.Поясніть аналогію методу рішення транспортної задачі з симплекс-методом?
5.Як знаходиться у методі рішення транспортної задачі початкове базисне рішення?
6.Як визначається кількість базисних змінних?
7.Для чого використовується процедура замкнених циклів і в чому її суть?
8.Поясніть призначення та порядок використання методу потенціалів?
9.Що уявляють собою потенціали з точки зору двоїстої задачі?
10.Чи можуть базисні змінні дорівнювати нулю?
11.Поясніть умову оптимальності рішення транспортної задачі?
12.Для яких інших прикладних задач може бути використана процедура рішення транспортної задачі?
Лабораторна робота N05
Тема: Рішення задач цілочисельного програмування.
Мета роботи: Придбати навички рішення задач цілочисельного програмування (ЦП).
Задачі роботи: Освоїти рішення задач ЦП за допомогою ЕОМ, провести аналіз задачі ЦП на базі використання алгоритму меж та гілок.
Студент повинен знати:особливості використання моделей ЦП для вирішення виробничих задач, алгоритм рішення задач ЦП.
Знаряддя дослідження:Персональній комп’ютер з процесором не нижче 486.
Обєкт дослідження:Організаційно-технічні питання виробництва та реалізації техніки .
5.1 Загальні відомості
В задачах ЛП в деяких випадках на значення змінних xj може бути накладено обмеження. Значення цих змінних в оптимальному рішенні повино бути цілим. Такі задачі називають цілочисельними задачами ЛП або задачами цілочисельного програмування (ЦП). Математична формуліровка задачі ЦП мае вигляд:
де xj - ціле. Якщо k=n, то задача називаеться повністю цілочисельною задачею. Якщо k<n, то задача являеться частинно-цілочисельною задачею (ЧЦП).
Розв’язок задач ЦП принципово відрізняеться від розв’язку задач ЛП, які є неперервними. Неперервні задачі, які записані у вигляді симпликс-таблиці, мають ознаки наявності допустимого і отриманого оптимального рішення; задачі ЦП таких ознак немають.
Розв’язок задач ЦП є складним процесом. Тому по можливості краще не накладати обмежень цілочисельності змінних. В деяких випадках ЦП можливо розв’язувати слідуючим чином: як неперервну задачу; округляти змінні; перевіряти допустимість округленного рішення; якщо округленне рішення є допустимим, приймати його в якості цілочисленого.
Існують методи відсіку і методи повернення, серед яких найбільш відомим є метод гілок і границь.
Суть методу гілок і границь заключається у слідуючому. Задача ЛП розв’язується без урахування цілочисельності. Така задача називається неперервною.Далі розглядається одна із змінних хj, на яку накладається обмеження цілочисельності, але яка при неперервному розв’язку отримала значення у вигляду дробу (тобто не ціле число). На основі отриманого розв’зку складаються додаткові обмеження:
xj < [xj*] і xj > [xj*] + 1,
де [xj*] - ціла частина значення змінної xj* в оптимальному рішенні, і тоді вирішують ще дві задачі ЛП, в кожну з яких увійшли всі вихідні обмеження і одне з додаткових.
Отриманий розв’язок нових задач перивіряється на цілочисельність змінних. Якщо розв’язок не задовільняє умовам цілочисельності, на основі кожної із задач складаються дві нові аналогічно розглянутим вище і т. д. Якщо один із розв’язків задовільняє умовам цілочисельності , значення цільової функції приймається за граничне Егр. При цьому розгляд інших задач продовжується до тих пір, поки не буде отримано:
1.На одній із гілок недопустиме рішення; тоді подальше обчислення по цій гілці зупиняється.
2.На одній із гілок цілочисельне рішення; тоді значення цільової функції при данних значеннях змінних порівнюється з верхнім(нижнім при мінімізації) граничним значенням Егр., якщо отримане значення гірше то воно відкидається, якщо -краще, то приймається за граничне.
3.На одній із гілок нецілочисельне рішення,але при цьому значення цільової функції гірше граничного; тоді подальший розгляд зупиняється.
Граничне значення на першому циклі розрахунку приймається рівним Егр = - 
при максимізації і Егр = при мінімізації.
Порядок виконання роботи
5.2.1. Ознайомитися з матеріалом даних методичних вказівок.
5.2.2. Опрацювати лекційний матеріал та літературні джерела відносно постановки та аналізу задач ЦП.
5.2.3. Розробити математичну модель отриманого варіанту задачі.
5.2.4. Засвоїти інструкцію по використанню пакету прикладних програм “TRANSP”.
5.2.5. Вирішити вихідну задачу .
5.2.7. Провести аналіз отриманих результатів.
5.2.8. Зробити висновки по роботі.
Завдання до роботи
Використати вихідні данні виробничої проблеми з лабораторної роботи N 3 і на базі алгоритму меж та гілок знайти рішення повністю цілочисельної задачі ЛП та частково цілочисельної задачі ЛП.
5.4 Зміст звіту про виконану лабораторну роботу
1. Мета роботи.
2. Короткі теоретичні відомості.
3. Алгоритм вирішення транспортної задачі.
4. Математична модель відповідного варіанту задачі.
5. Результат рішення задачі на моделі.
6. Аналіз отриманих результатів.
7. Висновки по роботі.
8. Перелік використанної літератури.
Контрольні питання
1.Приведіть приклади застосування ЦП?
2.Поясніть метод меж та гілок?
3. В чому полягає доцільність альтернативних рішень?
4.Чи може значення цільової функції в оптимальному рішенні цілочисельної задачі максимізації бути більше оптимального значення ЦФ відповідної задачі з ослабленими обмеженнями?
5. Що дає розгалудження вихідної задачі ЦП?
6.Поясніть переваги та недоліки метода меж та гілок?
7.Як вирішити частково цільчисельні задачі ЛП?
Лабораторна робота N06
Тема:Задача раціонального використання верстатів.
Мета роботи: Опрацювати алгоритм рішення задачі про призначення.
Задачі роботи:навчитися використовувати транспортну модель для вирішення прикладних виробничих задач ,освоїти алгоритм Маке для рішення задач про призначення на базі використання ЕОМ.
Студент повинен знати: алгоритм рішення транспортних задач та задач про призначення.
Знаряддя дослідження:Персональній комп’ютер з процесором не нижче 486.
Обєкт дослідження:Виробничі задачі використання верстатів в цехах приладобудівного заводу.
6.1 Загальні відомості
У схему транспортної задачі вкладається низка виробничих задач.
Однією з цих задач є задача раціонального використання верстатів. Сформулюємо її. Припустимо , що ми маємо m різних верстатів A1,A2, ... ,Am ,кожний з яких може обробляти деталі n різних типів B1, B2, ...Bn. Відомо , що верстат Ai обробляє за одиницю часу gij деталей типу Bj.
Будемо вважати, що продуктивність верстата Аi при обробці деталей типу Вj можна зобразити у вигляді gij=aibj, де величина аi - визначається типом верстата, bj- типом деталі ,яка обробляється на ньому. Нехай rij -вартість експлуатації верстата Ai при обробці деталей типу Bj протягом одиниці часу. Задача полягає в раціональному розподілу часу роботи верстатів по обробці різних деталей,що б деталей типу Bj було оброблено sj штук , верстат Аi працював не більше hi одиниць часу іпри цьому вартість обробки деталей була б мінімальною.
Якщо позначити через hij час,протягом якого верстат Аi повинен обробляти деталі типу Bj ,то математична модель задачі буде такою: треба знайти мінімум лінійної форми( сумарної вартості експлуатації всіх верстатів)
L= rij hij
за умов
hij 
hi (i=1,2,...,m),
ai bj hij=sj (j=1,2,...,n),
hij 0 (i=1,2,...,m; j=1,2,...,n).
Дану задачу можна звести до звичайної транспортної задачі. Для її рішення на даний час маються два методи,які базуються на тому факті, що положення оптимального вибору не міняється, якщо до кожного елементу деякої строки або стобчика добавити одне і теж значення або відняти його.
Венгерський метод заснован на деяких доволі складних і нетривіальних комбінаторних свойствах матриц. Його доволі тяжко програмувати,тому повідомимо про те, що опис відповідної процедури можна знайти в багатьох монографіях по випробовуванню операцій і по математичному програмуванню.
Метод Мака має переваги більш простого інтуітивного пояснення . Це логічний процес. Цей метод заснован на ідеї вибору в кожній строчкі мінімального елементу. Взагалі, мінімальні елементи строк не розподілені по всім n стобчикам матриці. Тут використовується ідея додавання (або віднімання) одного і того ж значення з усіма елементами строки або стобчика,щоб розподілити мінімальні елементи строк по стобчикам (тоді вони утворюють оптимальний вибор).
Метод Мака для задачі вибору.
Засновник метода К.Мак .Розглядається задача вибору розмірності n x n.Вибирем по мінімальному елементу в кожній строкі. Підкреслемо кожний з цих елементів. Якщо в кожному стобчику є рівно по одному підкресленому елементу, то підкреслені елементи - базис -визначають оптимальний вибор.
Початок
Розділемо множину стобчиків на дві множини А і А’ ,А-вибрана множина , А’ - невибрана множина.На початку (і при