Набір засобів для лінійного програмування GNU: Частина 1: Введення в лінійну оптимізацію

1. Серія контенту:
2. Цей контент є частиною серії: Набір засобів для лінійного програмування GNU
3. Вступ
4. Набір засобів для лінійного програмування GNU
5. Мова моделювання GNU MathProg
6. Giapetto's Woodcarving Inc.
7. моделювання
8. трохи теорії
9. Малюнок 1. Необмежена простір Giapetto
10. Малюнок 2. Простір Giapetto з урахуванням обмеження для годин на обробку
11. Малюнок 3. Простір Giapetto з урахуванням обмеження для годин на обробку та теслярські роботи
12. Малюнок 4. Область допустимих рішень задачі Giapetto
13. Використання GLPK для вирішення моделі
14. Лістинг 1. Перше рішення задачі Giapetto: giapetto.sol
15. Лістинг 2. Вихідні дані glpsol
16. Лістинг 3. Рішення завдання Giapetto: giapetto.sol
17. Використання розділів Модель і Дані в завданні Giapetto
18. Лістинг 4. Завдання Giapetto з розділами Модель і Дані: giapetto2.mod
19. Лістинг 5. Рішення завдання Giapetto з моделлю з розділом даних: giapetto2.sol
20. Висновок
21. Ресурси для скачування

Набір засобів для лінійного програмування GNU

Знайдіть найкраще рішення для складних чисельних завдань

Серія контенту:

Цей контент є частиною # з серії # статей: Набір засобів для лінійного програмування GNU

https://www.ibm.com/developerworks/ru/library/?series_title_by=**auto**

Слідкуйте за виходом нових статей цієї серії.

Цей контент є частиною серії: Набір засобів для лінійного програмування GNU

Слідкуйте за виходом нових статей цієї серії.

Вступ

"Лінійне програмування - інструмент для вирішення завдань оптимізації. У 1947 році Джордж Данциг (George Dantzig) розробив ефективний метод, симплексний алгоритм, для вирішення завдань лінійного програмування. Після розробки симплекс-алгоритму лінійне програмування стало використовуватися для вирішення завдань оптимізації в різних сферах, від банківської справи до освіти, лісової і нафтогазової промисловості і вантажоперевезень. у звіті з дослідження 500 найбільш успішних фірм 85% респондентів відзначили, що використовують в роботі лінійне про граммірованіе. "
Цит. по Дослідження Операцій: Програми та Алгоритми, Видання четверте, Вейн Л. Уїнстон (Wayne L. Winston) (Томсон, 2004 року); для посилання см. ресурси нижче.

Для вирішення проблем лінійного програмування існує безліч інструментів. Добре відомі спеціалізовані інструменти, але багато фахівців по ПО з відкритим програмним кодом можуть бути не знайомі з безкоштовним GLPK.

Серія складається з трьох статей, що ілюструють можливості та використання GLPK, і дана стаття, перша в серії, коротенько описує GLPK, а потім демонструє можливості та застосування мови GNU MathProg в GLPK.

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

Набір засобів для лінійного програмування GNU

Набір засобів для лінійного програмування GNU (GLPK) це бібліотека (стандартних) програм, що використовують широко відомі алгоритми дослідження операцій для розв'язання задач лінійного програмування. Програми реалізують такі алгоритми, як симплекс, метод гілок і меж, внутрішньої точки одночасного вирішення прямої і двоїстої задач, і інші. Для отримання додаткової інформації, зверніться до керівництва по GLPK, включеному в завантаження GLPK. (Для завантаження GLPK, див. ресурси , Де вказано посилання на сторінку GLPK на gnu.org.)

GLPK це не програма - він не може бути запущений і не має функції main (). Замість цього клієнт вводить дані завдання в програму алгоритму, за допомогою GLPK API і отримує назад результати. Клієнтом GLPK за замовчуванням є програма glpsol, яка взаємодіє з цим API. Зазвичай програма на зразок glpsol називається вирішальною програмою, а не клієнтом, тому далі Вам буде зустрічатися саме цей термін.

Мова моделювання GNU MathProg

Мова моделювання GNU MathProg простий і зручний для опису задач лінійного програмування. У загальному вигляді опис завдання складається з:

• Змінні рішення задачі.
• Функція мети (objective function). Ім'я функції є стандартним в теорії дослідження операцій.
• Обмежувальні умови задачі.
• Параметри завдання (дані).

Почнемо з простого прикладу з двома змінними: Giapetto's Woodcarving, Inc.

Giapetto's Woodcarving Inc.

Дане завдання взята з Дослідження Операцій:

Giapetto's Woodcarving Inc. виробляє два види дерев'яних іграшок: солдатики і паровозики. Солдатики продаються за ціною $ 27 за штуку, при витратах сировини на $ 10 на їх виробництво. Кожен вироблений Giapetto солдатик збільшує змінні Трудові витрати і Невиробничі витрати на $ 14. Паровозики продаються за ціною $ 21 за штуку, при витратах сировини на $ 9 на їх виробництво. Кожен вироблений Giapetto паровозик збільшує змінні Трудові витрати і Невиробничі витрати на $ 10. Виробництво дерев'яних солдатиків і паровозиків вимагає двох типів кваліфікованої праці: теслярські роботи і оздоблення. При виробництві солдатика витрачається один годину на теслярські роботи і 2 години на обробку. При виробництві паровозика витрачається один годину на теслярські роботи і одна година на обробку. Щотижня Giapetto може отримувати всю необхідну кількість сировини, але тільки 100 годин по обробці і 80 годин теслярські роботи. Попит на паровозики не обмежений, але не більше 40 солдатиків купується щотижня. Giapetto потрібно максимально підвищити щотижневий дохід (виручка від продажів (revenues) - витрати (costs)).

Узагальнимо важливу інформацію і умови даної задачі:

1. Є два вигляді дерев'яних іграшок: солдатики і паровозики.
2. Солдатик продається за ціною $ 27 при витратах сировини на $ 10 на його виробництво і збільшує змінні Трудові витрати і Невиробничі витрати на $ 14.
3. Паровозик продається за ціною $ 21 при витратах сировини на $ 9 на його виробництво і збільшує змінні Трудові витрати і Невиробничі витрати на $ 10.
4. При виробництві солдатика витрачається один годину на теслярські роботи і 2 години на обробку.
5. При виробництві паровозика витрачається один годину на теслярські роботи і одна година на обробку.
6. Не більше 100 годин по обробці і 80 годин теслярські роботи доступні щотижня.
7. Попит на паровозики не обмежений, але не більше 40 солдатиків купується щотижня.

Мета: знайти кількість солдатиків і паровозиків, виробництво яких дозволить максимально збільшити прибуток.

моделювання

При моделюванні завдання лінійного програмування спочатку визначаються змінні рішення, оскільки вони будуть змінюватися з кожної итерацией симплекс-алгоритму та визначати значення функції мети і, отже, оптимального рішення. У задачі про Giapetto функція мети - прибуток, яка є функцією від двох змінних - кількість солдатиків і кількість паровозиків, вироблених щотижня. Тому маємо дві змінні рішення:

• x1: кількість солдатиків, вироблених щотижня
• x2: кількість паровозиків, вироблених щотижня

Після того, як змінні рішення позначені, функція мети даного завдання зводиться до простої різниці виручки від продажів і витрат для кожної іграшки, як функції від x1 і x2.

Зверніть увагу, що прибуток лінійно залежить від x1 і x2 - це лінійна задача.

На перший погляд може здатися, що максимальне збільшення прибутку досягається простим збільшенням значень x1 і x2. Мабуть, якщо б життя було настільки проста, ми б все почали виробництво солдатиків і паровозиків і переїхали б на Кариби! На жаль, існують певні обмеження, які визначають межі для обираних змінних рішення (в іншому випадку модель виявиться, швидше за все, невірна).

Згадайте умови даного завдання. Перші три визначають змінні рішення і функцію мети. Четверте і шосте говорять про те, що виробництво солдатиків вимагає витрат часу на теслярські роботи і обробку. Обмеженням тут є те, що Giapetto має кінцеве число годин на теслярські роботи і на обробку. Це обмежує умова! Давайте проаналізуємо його для більшої ясності.

При виробництві одного солдатика витрачається один годину на теслярські роботи і 2 години на обробку, і Giapetto має не більше 100 годин по обробці щотижня, тому не може виробляти понад 50 солдатиків в тиждень. Подібним чином обмеження числа годин на теслярські роботи обмежує кількість вироблених солдатиків 80 шт. в тиждень. Зверніть увагу, що перше обмеження більш суворе, ніж друге. Перше обмеження фактично є підумови другого, тим самим, роблячи його (друге обмеження) зайвим.

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

Почніть з аналізу обмежуючих факторів для визначення обмежуючих умов. По-перше, що обмежує кількість годин на обробку? Оскільки і солдатики, і паровозики вимагають часу на обробку, і ті, і інші повинні прийматися до уваги. Припустимо, вироблено 10 солдатиків і 20 паровозиків. Необхідна кількість годин на обробку буде 10 раз по 2 години (для солдатиків) плюс 20 раз по 1 годині (для паровозиків), що в сумі складе 40 годин на обробку. Загальне обмеження, виражене через змінні рішення, виглядає наступним чином:

Існує безліч пар (x1, x2), що задовольняють даному нерівності, тому воно не визначає оптимальне поєднання для підприємства Giapetto.

Тепер, коли знайдено обмеження для годин на обробку, таким же чином визначається обмеження для годин на теслярські роботи:

Відмінно! Є ще одне додаткове обмеження для даного завдання. Пам'ятайте щотижневий попит на солдатиків? Відповідно до опису завдання, може бути проведено не більш 40 солдатиків в тиждень:

Попит на паровозики не обмежений, тому для них не встановлюється обмежень. Модель завершена і складається з наступних рівнянь:

Зверніть увагу на останню умову. Воно гарантує, що значення змінних рішення завжди позитивні. Завдання не вимагає цього явно, але це важливо (і очевидно).

Тепер GLPK може вирішити дану модель (оскільки GLPK добре вирішує завдання оптимізації лінійного програмування).

трохи теорії

Давайте розглянемо область рішення задачі. Маючи дві змінні рішення, воно має два виміри.

Малюнок 1. Необмежена простір Giapetto

Рішення (x1, x2) поза першого квадранта (де все значення позитивні) були відкинуті. Зверніть увагу, проте, що область рішення все ще не обмежена (це могла б бути при якому я б відправився на Кариби!)

У міру написання обмежень це необмежена область рішень набуває кордону. З рівнянням 6 , Наведеним вище, результат більш цікавий.

Малюнок 2. Простір Giapetto з урахуванням обмеження для годин на обробку

Область рішення містить всі можливі рішення (x1, x2) в першому квадраті (секторі), які задовольняють обмеження для годин на обробку.

Після введення обмеження, вираженого в рівнянні 7 , Область вирішення зменшується.

Малюнок 3. Простір Giapetto з урахуванням обмеження для годин на обробку та теслярські роботи

Зверніть увагу, що область рішення стає менше, що означає наявність у ній меншого числа пар рішень (x1, x2). Після введення обмеження, вираженого в рівнянні 8, результат стає ще менше.

Малюнок 4. Область допустимих рішень задачі Giapetto

Область рішення стає менше. Область рішення, що задовольняє всім обмеженням, називається областю допустимих значень (ОДЗ). На малюнку 4 показана ОДЗ для завдання Giapetto. Будь-яка пара (x1, x2), з цієї області є потенційним рішенням завдання.

Питання тепер стоїть таким чином: яка з цих пар робить прибуток Giapetto найбільшою?

Використання GLPK для вирішення моделі

GLPK чудовий інструмент для вирішення такого завдання. Математичне формулювання завдання Giapetto повинна бути написана на мові GNU MathProg. Ключові елементи для оголошення наступні:

• змінні рішення
• функція мети
• обмеження
• Набір даних завдання

Наступна програма призводить рішення задачі Giapetto за допомогою MathProg. Порядкові номери рядків не є частиною програмного коду, а наведені для зручності звернення до нього.

Лістинг 1. Перше рішення задачі Giapetto: giapetto.sol

1 # 2 # завдання Giapetto 3 # 4 # дана програма відшукує оптимальне рішення для максимізації прибутку Giapetto 5 # 6 7 / * змінні рішення * / 8 var x1> = 0; / * Солдатики (soldier) * / 9 var x2> = 0; / * Паровозики (train) * / 10 11 / * функція мети * / 12 maximize z: 3 * x1 + 2 * x2; 13 14 / * обмеження * / 15 st Finishing: 2 * x1 + x2 <= 100; 16 stCarpentry: x1 + x2 <= 80; 17 st Demand: x1 <= 40; 18 19 end;

Рядки 1 - 5 це коментарі. Символ # в кінці рядка позначає початок коментаря. Коментарі в стилі C (/ * * /) також можуть бути використані (як показано в рядку 7), і можуть працювати навіть в середині оголошення.

Перший крок MathProg -Оголошення змінних рішення. Рядки 8 і 9 оголошують змінні x1 і x2. Оголошення змінної рішення починається з зарезервованого слова var. Для спрощення введення обмеження по знаку (див. Нерівність 9), MathProg дозволяє вводити обмеження> = 0 в опис змінної рішення, як у рядках 8 і 9. Кожне вираз в GNU MathProg має закінчуватися крапкою з комою (;). Згадайте, що x1 позначає кількість солдатиків, а x2 позначає кількість паровозиків. Ці змінні могли б бути названі солдатики і паровозики, але це б призвело до замішання математиків, які читають цей підручник.

Рядок 12 містить оголошення функції мети. Лінійні задачі можуть бути на максимізацію або мінімізацію. Пам'ятайте, математична модель Giapetto реалізує завдання максимізації, тому зарезервоване слово maximize, а не minimize є підходящим. Функція мети носить ім'я z і дорівнює 3x1 + 2x2. Зверніть увагу, що:

• Символ двокрапка (:) розділяє ім'я функції мети і її опис.
• Символ зірочка (*) позначає множення, аналогічно, символи плюс (+), мінус (-), і прямий слеш (/) позначають додавання, віднімання і ділення, як Ви й очікували.

Рядки 15, 16, і 17 описують обмеження. Хоча вказівку st не потрібно на початку рядка для оголошення обмеження, це покращує читабельність коду

Три обмеження Giapetto названі Finishing (Обробка), Carpentry (Плотнічние роботи), і Demand (Попит). Кожен з них описаний як математична модель. Символи <= і> = позначають нерівність. Не забувайте ; в кінці кожного оголошення.

Кожен файл GNU MathProg повинен закінчуватися рядком end ;, як показано в рядку 19.

Тепер glpsol може використовувати цей файл як вхідні дані. Але, почекайте хвилину, де ж розділ даних нашого завдання? Ну, оскільки дана задача настільки проста, всі дані безпосередньо включені в функцію мети і оголошення обмежень у вигляді коефіцієнтів при змінних рішення в оголошеннях. Наприклад, у функції мети коефіцієнти 3 і 1 є частиною даних завдання. Коли я перепишу цю задачу з використанням набору даних, Вам стане ясно, як працює програма, тому зараз не хвилюйтеся з цього приводу.

Хорошим стилем програмування є використання розширення .mod для вхідних файлів MathProg і перенаправлення рішення в файл з розширенням .sol. Це не вимога - Ви можете використовувати будь-яке ім'я файлу і його розширення. Для даного прикладу файл Giapetto MathProg для введення - giapetto.mod, а для виведення - giapetto.sol. тепер запустіть glpsol в обраному терміналі:

glpsol -m giapetto.mod -o giapetto.sol

У даній командному рядку використані два параметра glpsol:

• Параметр -m повідомляє glpsol, що вхідні дані написані на GNU MathProg.
• Параметр -o повідомляє glpsol, що вихідні дані необхідно переслати в файл giapetto.sol.

Звіт про рішення буде знаходитися в файлі giapetto.sol, але деяка інформація, що стосується витрат часу і пам'яті GLPK, наводиться в стандартних вихідних даних системи:

Лістинг 2. Вихідні дані glpsol

ceron @ curly ~ $ glpsol -m giapetto.mod -o giapetto.sol Reading model section from giapetto.real.mod ... 19 lines were read Generating z ... Generating Finishing ... Generating Carpentry ... Generating Demand. .. Model has been successfully generated lpx_simplex: original LP has 4 rows, 2 columns, 7 non-zeros lpx_simplex: presolved LP has 2 rows, 2 columns, 4 non-zeros lpx_adv_basis: size of triangular part = 2 * 0: objval = 0.000000000e +00 infeas = 0.000000000e +00 (0) * 2: objval = 1.400000000e + 02 infeas = 0.000000000e +00 (0) OPTIMAL SOLUTION FOUND Time used: 0.0 secs Memory used: 0.1M (151326 bytes) lpx_print_sol: writing LP problem solution to `giapetto.sol '...

Звіт показує, що glpsol прочитує модель, викликає функцію GLPK API для генерації функції мети, потім викликає іншу функцію API для генерації обмежень. Після створення моделі, glpsol коротко пояснює, як GLPK здійснював пошук рішення задачі. Нарешті, наводиться інформація про рішення і ресурсах, витрачених GLPK на його пошук, рішення зазначено як оптимальне.

Відмінно, проте які ж оптимальні значення для змінних рішення? Вони наведені в файлі giapetto.sol:

Лістинг 3. Рішення завдання Giapetto: giapetto.sol

Problem: giapetto Rows: 4 Columns: 2 Non-zeros: 7 Status: OPTIMAL Objective: z = 180 (MAXimum) No. Row name St Activity Lower bound Upper bound Marginal ------ ------------ - ------------- -------- ----- ------------- ------------- 1 z B 180 2 Finishing NU 100 100 1 3 Carpentry NU 80 80 1 4 Demand B 20 40 No. Column name St Activity Lower bound Upper bound Marginal ------ ------------ - ------------- -------- ----- ------------- ------------- 1 x1 B 20 0 2 x2 B 60 0 Karush-Kuhn-Tucker optimality conditions: KKT .PE: max.abs.err. = 0.00e +00 on row 0 max.rel.err. = 0.00e +00 on row 0 High quality KKT.PB: max.abs.err. = 0.00e +00 on row 0 max.rel.err. = 0.00e +00 on row 0 High quality KKT.DE: max.abs.err. = 0.00e +00 on column 0 max.rel.err. = 0.00e +00 on column 0 High quality KKT.DB: max.abs.err. = 0.00e +00 on row 0 max.rel.err. = 0.00e +00 on row 0 High quality End of output

Рішення розділене на три секції:

• Інформація про задачу і оптимальне значення функції мети
• Точні дані про стан функції мети і обмежень
• Точні дані про оптимальні значеннях змінних рішення
• Інформація про рівняння оптимальності, якщо такі є

Ми бачимо, що для даного конкретного завдання рішення OPTIMAL (оптимальне), а максимальний прибуток Giapetto в тиждень становить $ 180.

Статус обмеження по годинах на обробку позначений як NU (стовпець St (статус)). NU значить, що є трохи базисна змінна на верхній межі для цього обмеження. Якщо Ви знайомі з теорією Дослідження Операцій побудуйте симплексну таблицю і перевірте її. Якщо немає, нижче наведено короткий практичне пояснення.

Досягнення значення обмеження верхньої або нижньої межі називається граничною умовою. Гранична умова перешкоджає досягненню функцією мети більшого значення. Уявіть його собі як регулятор гучності, наприклад, повернути який далі неможливо. Коли це відбувається, glpsol показує стан обмеження як NU або NL (для верхньої та нижньої кордонів відповідно), а також показує крайнє (marginal) значення, також зване прихованої ціною (shadow price). Прихована ціна це величина, на яку змінилася б функція мети, якби обмеження зменшили на одну одиницю (якби регулятор гучності можна було повернути ще трошки). Зверніть увагу, що підвищення залежить від того, чи є метою мінімізація або максимізація. Наприклад, в завданню Giapetto, яка є завданням на максимізацію, крайнє значення дорівнює 1, тобто значення функції мети збільшиться на 1, якщо на 1 годину збільшиться кількість годин на обробку (ми знаємо, що мова йде про збільшення на 1 годину, а не про зменшення, оскільки для обмеження кількості годин на обробку встановлена ​​верхня межа).

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

Попит на солдатиків, однак, не обмежений, тому його стан позначено B, а його зміна не спричинить за собою зміну оптимального значення функції мети.

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

Нарешті, значення змінних рішення будуть виведені в звіті glpsol: x1 = 20 і x2 = 60. Дані значення повідомляють Giapetto, що для отримання максимальної щотижневої прибутку необхідно виробляти 20 солдатиків і 60 паровозиків.

Завдання Giapetto дуже мала. Можливо, Вас цікавить питання, чи доведеться Вам оголошувати кожну змінну і кожне обмеження окремо в завданні з набагато більшою кількістю змінних рішення і обмежень. А як бути, якщо Вам хотілося б ввести в задачу такі дані, як, наприклад, ціна реалізації одного солдатика? Чи потрібно Вам вносити зміни усюди, де зустрічається дане значення? У наступному розділі розглянуті всі ці питання.

Використання розділів Модель і Дані в завданні Giapetto

Модель MathProg зазвичай має розділи Модель і Дані, іноді в двох різних файлах. Таким чином, glpsol може легко вирішити задачу по одній моделі, але з різними наборами даних. Наведений нижче лістинг містить опис завдання Giapetto набагато більш витонченим способом:

Лістинг 4. Завдання Giapetto з розділами Модель і Дані: giapetto2.mod

1 # 2 # Giapetto's problem 3 # 4 # This finds the optimal solution for maximizing Giapetto's profit 5 # 6 7 / * Set of toys * / 8 set TOY; 9 10 / * Parameters * / 11 param Finishing_hours {i in TOY}; 12 param Carpentry_hours {i in TOY}; 13 param Demand_toys {i in TOY}; 14 param Profit_toys {i in TOY}; 15 16 / * Decision variables * / 17 var x {i in TOY}> = 0; 18 19 / * Objective function * / 20 maximize z: sum {i in TOY} Profit_toys [i] * x [i]; 21 22 / * Constraints * / 23 st Fin_hours: sum {i in TOY} Finishing_hours [i] * x [i] <= 100; 24 st Carp_hours: sum {i in TOY} Carpentry_hours [i] * x [i] <= 80; 25 st Dem {i in TOY}: x [i] <= Demand_toys [i]; 26 27 28 data; 29 / * data section * / 30 31 set TOY: = soldier train; 32 33 param Finishing_hours: = 34 soldier 2 35 train 1; 36 37 param Carpentry_hours: = 38 soldier 1 39 train 1; 40 41 param Demand_toys: = 42 soldier 40 43 train 6.02E + 23; 44 45 param Profit_toys: = 46 soldier 3 47 train 2; 48 49 end;

Замість двох окремих файлів завдання сформульована в одному файлі з розділом Модель (рядки 1-27) і розділом Дані (рядки 28-49).

У рядку 8 визначається SET (безліч). SET це сукупність елементів. Наприклад, якщо я оголошую математично xi, для всіх i в {1; 2; 3; 4}, я говорю, що x - масив з цілими значеннями від 1 до 4 і, отже, ми маємо x1, x2, x3, x4. В цьому випадку {1; 2; 3; 4} це безліч. Отже, в завданню Giapetto є безліч TOY (Іграшки). Де вказана фактична величина цієї множини? У розділі даних файлу в рядку 31, де визначено, що безліч TOY (Іграшки) містить soldier (солдатик) і train (паровозик). Безліч не є областю числових значень. Як це можливо? GLPK забезпечує це досить цікавим способом. Як - ви дізнаєтеся буквально через кілька секунд. Тепер зверніть увагу на синтаксис оголошення SET в розділі даних:

set label: = value1 value2 ... valueN;

Рядки 11, 12 і 13 задають параметри завдання. Є три параметра: Finishing_hours (Годинник на обробку), Carpentry_hours (Годинник на теслярські роботи), і Demand_toys (Попит на іграшки). Ці параметри утворюють матрицю даних завдання і використовуються при обчисленні обмежень, як Ви побачите пізніше.

Розглянемо параметр Finishing_hours (Годинник на обробку). Він визначений для безлічі Іграшки (TOY), тому кожен вид іграшки з безлічі Іграшки (TOY) матиме значення параметра Finishing_hours. Пам'ятайте, що виробництво одного солдатика потребує 2 годин оздоблювальних робіт, а паровозика - 1 години. Подивіться на рядки 33, 34 і 35. Вони містять визначення кількості годин на обробку для кожного виду іграшок. Практично, ці рядки оголошують, що Finishing_hours [soldier] = 2 і Finishing_hours [train] = 1. Finishing_hours, таким чином, це матриця з 1 рядка і 2 стовпців.

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

У рядку 17 оголошена змінна x для кожного i в TOY (в кінцевому рахунку x [soldier] і x [train]), і її значення обмежена умовою: воно має дорівнювати нулю або більше нуля. Маючи безлічі, оголошувати змінні досить просто, чи не так?

У рядку 20 оголошена функція мети - максимізація від z, яка є загальний прибуток для кожного виду іграшок (їх всього два: солдатики і паровозики). Наприклад, для солдатиків прибуток дорівнює кількості солдатиків помноженому, на прибуток з продажу кожного солдатика.

Обмеження в рядках 23, 24, і 25 оголошені аналогічним способом. Розглянемо, наприклад, обмеження по годинах на обробку: воно складається як сума годин на обробку іграшки кожного виду, помножене на кількість вироблених іграшок зазначеного виду, для двох видів іграшок (паровозики (trains) і солдатики (soldiers)), і воно повинно бути менше або дорівнює 100. Аналогічно, сумарні кількість годин на теслярські роботи повинно бути менше або дорівнює 80.

Обмеження щодо попиту трохи відрізняється від двох описаних вище, оскільки визначено для кожного типу іграшок окремо, а не як загальне значення для всіх типів іграшок. Отже, нам необхідно два обмеження: одна для паровозиків, інше для солдатиків, як Ви можете бачити в рядку 25. Зверніть увагу, що індексна змінна ({i in TOY}) вказується до:, таким чином повідомляючи GLPK про необхідність створення обмеження для кожного типу іграшок в TOY (Іграшки), і рівняння, що визначає кожне обмеження, буде побудовано згідно із записом, наведеної після знака:. В даному випадку GLPK створить

Dem [soldier]: x [soldier] <= Demand [soldier]

Dem [train]: x [train] <= Demand [train]

Рішення даної моделі має дати ті ж результати, що і рішення попередньої моделі:

Лістинг 5. Рішення завдання Giapetto з моделлю з розділом даних: giapetto2.sol

Problem: giapetto2 Rows: 5 Columns: 2 Non-zeros: 8 Status: OPTIMAL Objective: z = 180 (MAXimum) No. Row name St Activity Lower bound Upper bound Marginal ------ ------------ - ------------- -------- ----- ------------- ------------- 1 z B 180 2 Fin_hours NU 100 100 1 3 Carp_hours NU 80 80 1 4 Dem [ soldier] B 20 40 5 Dem [train] B 60 6.02e + 23 No. Column name St Activity Lower bound Upper bound Marginal ------ ------------ - ------------- -------- ----- ------------- ------------- 1 x [soldier] B 20 0 2 x [train] B 60 0 Karush-Kuhn -Tucker optimality conditions: KKT.PE: max.abs.err. = 0.00e +00 on row 0 max.rel.err. = 0.00e +00 on row 0 High quality KKT.PB: max.abs.err. = 0.00e +00 on row 0 max.rel.err. = 0.00e +00 on row 0 High quality KKT.DE: max.abs.err. = 0.00e +00 on column 0 max.rel.err. = 0.00e +00 on column 0 High quality KKT.DB: max.abs.err. = 0.00e +00 on row 0 max.rel.err. = 0.00e +00 on row 0 High quality End of output

Зверніть увагу, що імена обмежень і змінних рішення пов'язані з безліччю TOY (Іграшки), яке виглядає акуратним і впорядкованим. Дуже добре. Ви максимізувати прибуток Giapetto!

Висновок

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

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

Ресурси для скачування

Схожі тими

Підпішіть мене на ПОВІДОМЛЕННЯ до коментарів