Рішення завдання
оптимального управління
Санкт-Петербург
2006
Введення
Глава 1. Рішення завдання класичним симплекс методом
Глава 2. Графічний метод
Глава 3. Рішення задачі за допомогою Excel
Опис діалогу «Пошук рішень»
Рішення завдання
Висновок
Введення
Оптимізація - цілеспрямована діяльність, яка полягає в отриманні найкращих результатів при відповідних умовах.
Пошуки оптимальних рішень привели до створення спеціальних математичних методів і вже в 18 столітті були закладені математичні основи оптимізації (варіаційне числення, чисельні методи тощо). Проте до другої половини 20 століття методи оптимізації в багатьох галузях науки і техніки застосовувалися дуже рідко, оскільки практичне використання математичних методів оптимізації вимагало величезної обчислювальної роботи, що без ЕОМ реалізувати було вкрай важко, а в ряді випадків - неможливо.
Постановка завдання оптимізації передбачає існування конкуруючих властивостей процесу, наприклад:
кількість продукції - витрата сировини
кількість продукції - якість продукції
Вибір компромиcного варіанту для зазначених властивостей і являє собою процедуру вирішення оптимізаційної задачі.
При постановці задачі оптимізації необхідно:
1. Наявність об'єкта оптимізації і цілі оптимізації. При цьому формулювання кожного завдання оптимізації повинна вимагати екстремального значення лише однієї величини, тобто одночасно системі не повинно приписуватися два і більше критеріїв оптимізації, тому що практично завжди екстремум одного критерію не відповідає екстремуму іншого.
2. Наявність ресурсів оптимізації, під якими розуміють можливість вибору значень деяких параметрів оптимизируемого об'єкта.
3. Можливість кількісної оцінки оптимизируемой величини, оскільки тільки в цьому випадку можна порівнювати ефекти від вибору тих чи інших управляючих впливів.
4. Облік обмежень.
Зазвичай оптимізується величина пов'язана з економічністю роботи даного об'єкту (апарат, цех, завод). Оптимізується варіант роботи об'єкта повинен оцінюватися якийсь кількісною мірою - критерієм оптимальності.
Критерієм оптимальності називається кількісна оцінка оптимизируемого якості об'єкта.
На підставі обраного критерію оптимальності складається цільова функція, що є залежність критерію оптимальності від параметрів, що впливають на її значення. Вид критерію оптимальності або цільової функції визначається конкретною задачею оптимізації.
Таким чином, задача оптимізації зводиться до знаходження екстремуму цільової функції.
Залежно від своєї постановки, будь-яка із завдань оптимізації може вирішуватися різними методами, і навпаки - будь-який метод може застосовуватися для вирішення багатьох завдань. Методи оптимізації можуть бути скалярними (оптимізація проводиться за одним критерієм), векторними (оптимізація проводиться за багатьма критеріями), пошуковими (включають методи регулярного і методи випадкового пошуку), аналітичними (методи диференціального числення, методи варіаційного обчислення і ін), обчислювальними (засновані на математичному програмуванні, яке може бути лінійним, нелінійним, дискретним, динамічним, стохастичним, магічними і т.д.), теоретико-імовірнісними, теоретико-ігровими та ін Піддаватися оптимізації можуть завдання як з обмеженнями, так і без них.
Лінійне програмування - один з перших і найбільш детально вивчених розділів математичного програмування. Саме лінійне програмування стало тим розділом, з якого почала розвиватися сама дисципліна «математичне програмування». Термін «програмування» в назві дисципліни нічого спільного з терміном «програмування (тобто складання програм) для ЕОМ» не має, оскільки дисципліна «лінійне програмування» виникла ще до того часу, коли ЕОМ стали широко застосовуватися при вирішенні математичних, інженерних , економічних та ін завдань. Термін «лінійне програмування» виник в результаті неточного перекладу англійського «linear programming». Одне зі значень слова «programming» - складання планів, планування. Отже, правильним перекладом «linear programming» було б не «лінійне програмування», а «лінійне планування», що більш точно відображає зміст дисципліни. Однак, термін лінійне програмування, нелінійне програмування і т.д. в нашій літературі стали загальноприйнятими.
Можна сказати, що лінійне програмування застосовується для побудови математичних моделей тих процесів, в основу яких може бути покладена гіпотеза лінійного представлення реального світу: економічних завдань, завдань управління та планування, оптимального розміщення устаткування і пр.
Завданнями лінійного програмування називаються завдання, в яких лінійні як цільова функція, так і обмеження у вигляді рівностей та нерівностей. Коротко задачу лінійного програмування можна сформулювати наступним чином: знайти вектор значень змінних, що доставляють екстремум лінійної цільової функції при m обмеженнях у вигляді лінійних рівностей або нерівностей.
Лінійне програмування є найбільш часто використовуваний метод оптимізації. До завдань лінійного програмування можна віднести завдання:
раціонального використання сировини та матеріалів; завдання оптимізації розкрою;
оптимізації виробничої програми підприємств;
оптимального розміщення і концентрації виробництва;
складання оптимального плану перевезень, роботи транспорту;
управління виробничими запасами;
і багато інших, що належать сфері оптимального планування.
Сучасні методи лінійного програмування досить надійно вирішують завдання загального вигляду з кількома тисячами обмежень і десятками тисяч змінних. Для вирішення надвеликих завдань використовуються вже, як правило, спеціалізовані методи.
У роботі використовуються методи лінійного програмування для вирішення виробничого завдання
Знаючи прибуток, одержуваний від продажу однієї одиниці продукції і витрата сировини на її виробництво, треба скласти оптимальний виробничий план, що дає максимальний прибуток. У роботі ми вирішимо це завдання класичним симплекс методом, засобами Excel і графічним методом.
Глава 1. Рішення завдання класичним симплекс методом
Коефіцієнти цільової функції
Змінні цільової функції
Завдання
при обмеженнях
Введемо фіктивні змінні Y, щоб з нерівностей зробити рівності
Введемо в базис
Вирішимо щодо базисних змінних
Запишемо отримане рішення в матричній формі
Коефіцієнти відносних зміщень для небазисних змінних негативні
де
-Коефіцієнти цільової функції при базисних змінних
а
- Безліч індексів при вільних змінних
Тому зазначений базис є оптимальним, а оптимальним рішенням є
Значення цільової функції
Глава 2. Графічний метод
Максимізуємо функцію
при обмеженнях
Максимум досягається в точці (відзначена ромбиком)
Значення цільової функції
Глава 3. Рішення задачі за допомогою Excel
Поля введення і кнопки в цьому вікні виконують такі функції:
Встановити цільову клітинку служить для вказівки цільової комірки, значення якої необхідно максимізувати, мінімізувати або встановити рівним заданому числу. Цей осередок повинна містити формулу.
Рівної служить для вибору варіанта оптимізації значення цільової комірки (максимізація, мінімізація або підбір заданого числа). Щоб встановити число, введіть його в поле.
Змінюючи клітинки служить для вказівки осередків, значення яких змінюються в процесі пошуку рішення до тих пір, поки не будуть виконані накладені обмеження і умова оптимізації значення клітинки, зазначеної в полі Встановити цільову клітинку. Використовується для автоматичного пошуку осередків, що впливають на формулу, посилання на яку дана в полі Встановити цільову клітинку. Результат пошуку відображається в полі Змінюючи клітинки.
Обмеження служить для відображення списку граничних умов поставленої задачі.
Додати служить для відображення діалогового вікна Додати обмеження.
Посилання на клітинку служить для вказівки клітинки або діапазону, на значення яких необхідно накласти обмеження.
Обмеження служить для завдання умови, що накладається на значення клітинки або діапазону, зазначеного в полі Посилання на клітинку. Виберіть необхідний умовний оператор і введіть обмеження число, формулу, посилання на клітинку або діапазон у полі праворуч від розкривного списку.
Додати. Натискання на цю кнопку дозволяє, не повертаючись у вікно діалогу Параметри пошуку рішення, накласти нову умову на пошук рішення задачі.
Змінити служить для відображення діалогового вікна Змінити обмеження. Зміст даного вікна в точності повторює зміст вікна Додати обмеження.
Видалити служить для зняття зазначеного обмеження.
Виконати служить для запуску пошуку рішення поставленої задачі.
Закрити служить для виходу з вікна діалогу без запуску пошуку рішення поставленої задачі. При цьому зберігаються установки зроблені у вікнах діалогу, що з'являлися після натискань на кнопки Параметри, Додати, Редагувати або Видалити.
Параметри служить для відображення діалогового вікна Параметри пошуку рішення, в якому можна завантажити або зберегти оптимизируемой модель і зазначити передбачені варіанти пошуку рішення.
Відновити служить для очищення полів вікна діалогу та відновлення значень параметрів пошуку рішення, які використовуються за замовчуванням.
Засобами Excel ми отримали, що треба зробити 6 од. першої продукції та 4 од. другий продукції. Максимальна виручка при цьому дорівнює 24.
Висновок
У задачі були розглянуті класичні та програмні методи розв'язання задачі лінійного програмування. Рішення завдання в усіх випадках було: провести 6 од. першої продукції та 4 од. другий продукції. При цьому прибуток становила 24 ден.ед.
оптимального управління
| Виконав студент |
2006
Зміст
ЗмістВведення
Глава 1. Рішення завдання класичним симплекс методом
Глава 2. Графічний метод
Глава 3. Рішення задачі за допомогою Excel
Опис діалогу «Пошук рішень»
Рішення завдання
Висновок
Введення
Оптимізація - цілеспрямована діяльність, яка полягає в отриманні найкращих результатів при відповідних умовах.
Пошуки оптимальних рішень привели до створення спеціальних математичних методів і вже в 18 столітті були закладені математичні основи оптимізації (варіаційне числення, чисельні методи тощо). Проте до другої половини 20 століття методи оптимізації в багатьох галузях науки і техніки застосовувалися дуже рідко, оскільки практичне використання математичних методів оптимізації вимагало величезної обчислювальної роботи, що без ЕОМ реалізувати було вкрай важко, а в ряді випадків - неможливо.
Постановка завдання оптимізації передбачає існування конкуруючих властивостей процесу, наприклад:
кількість продукції - витрата сировини
кількість продукції - якість продукції
Вибір компромиcного варіанту для зазначених властивостей і являє собою процедуру вирішення оптимізаційної задачі.
При постановці задачі оптимізації необхідно:
1. Наявність об'єкта оптимізації і цілі оптимізації. При цьому формулювання кожного завдання оптимізації повинна вимагати екстремального значення лише однієї величини, тобто одночасно системі не повинно приписуватися два і більше критеріїв оптимізації, тому що практично завжди екстремум одного критерію не відповідає екстремуму іншого.
2. Наявність ресурсів оптимізації, під якими розуміють можливість вибору значень деяких параметрів оптимизируемого об'єкта.
3. Можливість кількісної оцінки оптимизируемой величини, оскільки тільки в цьому випадку можна порівнювати ефекти від вибору тих чи інших управляючих впливів.
4. Облік обмежень.
Зазвичай оптимізується величина пов'язана з економічністю роботи даного об'єкту (апарат, цех, завод). Оптимізується варіант роботи об'єкта повинен оцінюватися якийсь кількісною мірою - критерієм оптимальності.
Критерієм оптимальності називається кількісна оцінка оптимизируемого якості об'єкта.
На підставі обраного критерію оптимальності складається цільова функція, що є залежність критерію оптимальності від параметрів, що впливають на її значення. Вид критерію оптимальності або цільової функції визначається конкретною задачею оптимізації.
Таким чином, задача оптимізації зводиться до знаходження екстремуму цільової функції.
Залежно від своєї постановки, будь-яка із завдань оптимізації може вирішуватися різними методами, і навпаки - будь-який метод може застосовуватися для вирішення багатьох завдань. Методи оптимізації можуть бути скалярними (оптимізація проводиться за одним критерієм), векторними (оптимізація проводиться за багатьма критеріями), пошуковими (включають методи регулярного і методи випадкового пошуку), аналітичними (методи диференціального числення, методи варіаційного обчислення і ін), обчислювальними (засновані на математичному програмуванні, яке може бути лінійним, нелінійним, дискретним, динамічним, стохастичним, магічними і т.д.), теоретико-імовірнісними, теоретико-ігровими та ін Піддаватися оптимізації можуть завдання як з обмеженнями, так і без них.
Лінійне програмування - один з перших і найбільш детально вивчених розділів математичного програмування. Саме лінійне програмування стало тим розділом, з якого почала розвиватися сама дисципліна «математичне програмування». Термін «програмування» в назві дисципліни нічого спільного з терміном «програмування (тобто складання програм) для ЕОМ» не має, оскільки дисципліна «лінійне програмування» виникла ще до того часу, коли ЕОМ стали широко застосовуватися при вирішенні математичних, інженерних , економічних та ін завдань. Термін «лінійне програмування» виник в результаті неточного перекладу англійського «linear programming». Одне зі значень слова «programming» - складання планів, планування. Отже, правильним перекладом «linear programming» було б не «лінійне програмування», а «лінійне планування», що більш точно відображає зміст дисципліни. Однак, термін лінійне програмування, нелінійне програмування і т.д. в нашій літературі стали загальноприйнятими.
Можна сказати, що лінійне програмування застосовується для побудови математичних моделей тих процесів, в основу яких може бути покладена гіпотеза лінійного представлення реального світу: економічних завдань, завдань управління та планування, оптимального розміщення устаткування і пр.
Завданнями лінійного програмування називаються завдання, в яких лінійні як цільова функція, так і обмеження у вигляді рівностей та нерівностей. Коротко задачу лінійного програмування можна сформулювати наступним чином: знайти вектор значень змінних, що доставляють екстремум лінійної цільової функції при m обмеженнях у вигляді лінійних рівностей або нерівностей.
Лінійне програмування є найбільш часто використовуваний метод оптимізації. До завдань лінійного програмування можна віднести завдання:
раціонального використання сировини та матеріалів; завдання оптимізації розкрою;
оптимізації виробничої програми підприємств;
оптимального розміщення і концентрації виробництва;
складання оптимального плану перевезень, роботи транспорту;
управління виробничими запасами;
і багато інших, що належать сфері оптимального планування.
Сучасні методи лінійного програмування досить надійно вирішують завдання загального вигляду з кількома тисячами обмежень і десятками тисяч змінних. Для вирішення надвеликих завдань використовуються вже, як правило, спеціалізовані методи.
У роботі використовуються методи лінійного програмування для вирішення виробничого завдання
| Вид ресурсу | число ресурсів, що витрачаються на виготовлення одиниці продукції | всього ресурсу | |
| P1 | P2 | ||
| S1 | 1 | 3 | 18 |
| S2 | 2 | 1 | 16 |
| S3 | 0 | 1 | 5 |
| S4 | 3 | 0 | 21 |
| прибуток від однієї од | 2 | 3 | |
Глава 1. Рішення завдання класичним симплекс методом
Коефіцієнти цільової функції
Змінні цільової функції
Завдання
при обмеженнях
Введемо фіктивні змінні Y, щоб з нерівностей зробити рівності
Введемо в базис
Вирішимо щодо базисних змінних
Запишемо отримане рішення в матричній формі
Коефіцієнти відносних зміщень для небазисних змінних негативні
де
а
Тому зазначений базис є оптимальним, а оптимальним рішенням є
Значення цільової функції
Глава 2. Графічний метод
Максимізуємо функцію
при обмеженнях
Максимум досягається в точці (відзначена ромбиком)
Значення цільової функції
Глава 3. Рішення задачі за допомогою Excel
Опис діалогу «Пошук рішень»
Інструмент Пошук рішення може бути використаний для вирішення завдань, які включають багато змінних клітинок, і допомагає знайти комбінації змінних, які максимізують або мінімізують значення в цільовій комірці. Він також дозволяє вказати одне або кілька обмежень - умов, які повинні виконуватися при пошуку рішення. Пошук рішення є надбудовою.Поля введення і кнопки в цьому вікні виконують такі функції:
Встановити цільову клітинку служить для вказівки цільової комірки, значення якої необхідно максимізувати, мінімізувати або встановити рівним заданому числу. Цей осередок повинна містити формулу.
Рівної служить для вибору варіанта оптимізації значення цільової комірки (максимізація, мінімізація або підбір заданого числа). Щоб встановити число, введіть його в поле.
Змінюючи клітинки служить для вказівки осередків, значення яких змінюються в процесі пошуку рішення до тих пір, поки не будуть виконані накладені обмеження і умова оптимізації значення клітинки, зазначеної в полі Встановити цільову клітинку. Використовується для автоматичного пошуку осередків, що впливають на формулу, посилання на яку дана в полі Встановити цільову клітинку. Результат пошуку відображається в полі Змінюючи клітинки.
Обмеження служить для відображення списку граничних умов поставленої задачі.
Додати служить для відображення діалогового вікна Додати обмеження.
Посилання на клітинку служить для вказівки клітинки або діапазону, на значення яких необхідно накласти обмеження.
Обмеження служить для завдання умови, що накладається на значення клітинки або діапазону, зазначеного в полі Посилання на клітинку. Виберіть необхідний умовний оператор і введіть обмеження число, формулу, посилання на клітинку або діапазон у полі праворуч від розкривного списку.
Додати. Натискання на цю кнопку дозволяє, не повертаючись у вікно діалогу Параметри пошуку рішення, накласти нову умову на пошук рішення задачі.
Змінити служить для відображення діалогового вікна Змінити обмеження. Зміст даного вікна в точності повторює зміст вікна Додати обмеження.
Видалити служить для зняття зазначеного обмеження.
Виконати служить для запуску пошуку рішення поставленої задачі.
Закрити служить для виходу з вікна діалогу без запуску пошуку рішення поставленої задачі. При цьому зберігаються установки зроблені у вікнах діалогу, що з'являлися після натискань на кнопки Параметри, Додати, Редагувати або Видалити.
Параметри служить для відображення діалогового вікна Параметри пошуку рішення, в якому можна завантажити або зберегти оптимизируемой модель і зазначити передбачені варіанти пошуку рішення.
Відновити служить для очищення полів вікна діалогу та відновлення значень параметрів пошуку рішення, які використовуються за замовчуванням.
Рішення завдання
Засобами Excel ми отримали, що треба зробити 6 од. першої продукції та 4 од. другий продукції. Максимальна виручка при цьому дорівнює 24.
Висновок
У задачі були розглянуті класичні та програмні методи розв'язання задачі лінійного програмування. Рішення завдання в усіх випадках було: провести 6 од. першої продукції та 4 од. другий продукції. При цьому прибуток становила 24 ден.ед.