Основні види аналізу задач оптимізації з комп’ютерною підтримкою

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Основні види аналізу задач оптимізації з комп'ютерною підтримкою

Кузьміна Н.М.



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

Ключові слова: аналіз, параметричний, багатокритеріальний, структурний, несумісність.

В статье продолжено рассмотрение некоторых методических аспектов обучения основам теории и методов оптимизации студентов информатических специальностей и специализаций педагогических университетов. Приведена классификация различных видов анализа задач оптимизации на этапах постановки и после получения оптимального решения, а также примеры их применения с использованием информационных технологий. Умение проводить всестороннее оценивание оптимальных решений и значений соответствующих величин при решении задач оптимизации способствует развитию у студентов математических и информатических компетентностей и обеспечивает необходимую их практическую подготовку как будущих специалистов.

Ключевые слова: анализ, параметрический, многокритериальный, структурный, несовместимость.

The article continues to consider some methodological aspects of teaching basics of theory and methods of optimization of students of information science specialities and specializations of pedagogical universities. The classification of different types of analysis of optimization problems at the stage of the statement and after getting an optimal solutions, and examples of their application using information technologies are given. The ability to conduct a comprehensive assessment of optimal solutions and values of corresponding quantities for solving optimization problems promotes students' mathematical and information science competencies and provides them with necessary practical training as future professionals.

Keywords: analysis, parametric, multicriterial, structural, incompatibility.



У даному дослідженні продовжено аналіз навчання основ теорії і методів оптимізації, який було розглянуто у роботах [2-4], з метою забезпечення необхідної практичної підготовки майбутніх фахівців - студентів інформатичних спеціальностей і спеціалізацій педагогічних університетів.

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

Рис. 1

На етапі постановки задачі оптимізації доцільно провести так званий варіантний аналіз з метою дати відповіді на питання «що буде з оптимальним розв'язком, якщо будуть виконані деякі умови?» і / або «що потрібно зробити, щоб оптимальний розв'язок задовольняв певні умови?».

До варіантного аналізу відносять [5]:

параметричний аналіз - розв'язування задачі оптимізації за різних значень деяких параметрів. Як правило під параметричним аналізом розуміють розв'язування задачі оптимізації за різних значень тих параметрів, через величини яких обмежується збільшення (зменшення) цільової функції;

багатокритеріальний аналіз - розв'язування задачі оптимізації за кількома цільовими функціями;

аналіз за умовних вихідних даних - вихідні дані, що використовуються під час розв'язування задачі оптимізації, залежать від додаткових умов;

структурний аналіз - розв'язування задачі оптимізації за різної структури обмежень;

розв'язок за замовленням - розв'язування задачі оптимізації з заданими значеннями змінних, правих частин обмежень, цільової функції тощо.

Розглянемо різні види варіантного аналізу класичної задачі лінійного програмування про оптимальний розподіл ресурсів для виробництва продукції за допомогою засобу MS Excel.

Приклад. Визначити оптимальну структуру виробництва 3-х видів продукції за критерієм максимуму прибутку, якщо задано нормативи витрат 5- ти різних видів ресурсів (затрати праці, сировина, фінанси, площа тощо) на виробництво одиниці відповідної продукції, наявні ресурси і прибуток від реалізації одиниці продукції (рис. 2).



Наведемо математичну модель даної задачі:

z = 7 5 x-l+5 0 х2+3 5 х3 ^max (1)

х1 +х2 < 450 х1 < 250

+2 х2+х3< 800 (2)

х1 +х2 < 450

+х2 +х3 < 6 0 0 Хі ,Х2 ,х3 > 0,

де х1; х2 , х3 - невідомі змінні, що відповідають плану виробництва відповідної продукції.

На рисунку 2 у діапазонах клітин B4:D4; F3 наведено оптимальний розв'язок даної задачі, який отримано за допомогою табличного процесора MS Excel із використанням засобу Пошук розв'язку. Для цього у клітину F3 введемо функцію скалярного добутку =SUMPRODUCT(B6:D6;B4:D4) для визначення цільової функції; у клітину E8 - функцію =SUMPRODUCT(B8:D8; $B$4:$D$4) і скопіюємо її на діапазон E9: E12 для визначення лівих частин обмежень.



Параметричний аналіз

Оскільки через задане значення РесурсуЗ (800) стримується отримання максимального прибутку, то розв'яжемо наведену вище задачу за таких варіантів РесурсуЗ: 850, 900,1000.

Скористаємось послугою Зберегти сценарій, розв'язуючи задачу оптимізації за допомогою послуги Пошук розв'язку для кожного варіанта параметра РесурсуЗ. Далі, за допомогою послуги Диспетчер сценаріїв отримаємо стандартний звіт Структура сценарія. Відредагуємо його і

Багатокритеріальний аналіз

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

Призначимо додаткові граничні умови на всі види продукції:

1 < Прод* < 250

Тоді математична модель першої задачі - це наведені вище співвідношення (1), (2) з уточненням.

Для розв'язування другої задачі у наведену вище математичну модель обмежень (2) введемо додаткові змінні, через які визначаються величини невикористаних відповідних ресурсів, і наведемо математичну модель другої задачі:

+У2 +Уз + У4 + y5^max (3)

х1 +х2 + y1 = 450 = 250

+2 х2+х3+у3= 800 (4)

+ = 450

2 х1 +х2 +х3+ у5 = 60 0 ,

> 0, 250.

Введемо умови задачі з двома цільовими функціями у робочу книгу MS Excel (рис. 4). Для цього у клітину E14 введемо функцію =SUMPRODUCT(B6:D6;B4:D4) для визначення цільової функції першої задачі, у клітину E15 - функцію =SUM(E4:I4) для визначення цільової функції другої задачі.



На рисунках 4, 5 наведено відповідно оптимальні розв'язки першої і другої задач оптимізації.

Зберігши сценарії даних розв'язків так, як було описано вище, отримаємо відповідний звіт (рис. 6), який доцільно унаочнити діаграмами:



Розв'язування за умовних вхідних даних

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

В MS Excel такою умовною функцією є логічна функція IF. У загальному випадку умовні цільові функції можуть бути складеними:

=IF(AND(A;B); ФМ1;ФМ2), =IF(OR(A;B); ФМ1;ФМ2).

На рис. 7 наведено використання даної функції під час розв'язування розглянутої вище задачі оптимізації ресурсів за умовної цільової функції.

Рис. 7

Структурний аналіз. Розглянемо структурний аналіз - пошук оптимальних розв'язків за різних структур обмежень - на прикладі задачі оптимізації з булевими змінними. Нехай у наведеній вище задачі оптимізації невідомі змінні набувають одного з двох значень: 0 або 1:

(1,якщо Продї входить до оптимального плану ^ 12 3 О,якщо Продї не входить до оптимального плану ' ' '

Тоді математична модель такої задачі - це наведені вище співвідношення (1), (2) з уточненнями 0 < хі < 1; Хі - цілі, і = 1,2,3.

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

Таким чином, якщо задають умову ПОВИНЕН, то в обмеженнях ставиться знак рівності, якщо задають умову МОЖЕ - знак нерівності. Очевидно, що подібних умов можна задати як завгодно багато.

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

Рис. 9

інформатичний компетентність оптимізація комп'ютерний

Розв'язок за замовленням

Під час розв'язування задач оптимізації за замовленням користувач задає значення деяких величин, які йому необхідно мати в оптимальному розв'язку. Такі задачі можуть бути трьох видів:

задання величини цільової функції;

задання величин невідомих змінних;

задання величин ресурсів, що використовуються.

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

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

Аналіз отриманого оптимального розв'язку

Крім аналізу задачі оптимізації, що виконується на етапі постановки задачі, важливими операціями, виконання яких допомагає прийняти рішення, оцінити його математичні та економічні показники, є аналіз отриманого оптимального розв'язку, аналіз його стійкості та аналіз його меж.

Аналіз оптимального розв'язку для задач лінійного програмування виконується на основі використання основних положень симплекс-методу. За допомогою MS Excel формуються 3 види звітів для всебічного аналізу оптимального розв'язку:

звіт за результатами;

звіт щодо стійкості;

звіт щодо меж.

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

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

У звіті щодо стійкості (рис. 10) наводять: результати розв'язування задачі оптимізації;

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

коефіцієнти цільової функції;

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

величини використаних ресурсів;

тіньову ціну, тобто двоїсті оцінки (величини змінних в оптимальному плані двоїстої задачі), за значеннями яких визначають, як зміниться цільова функція при зміні ресурсів на одиницю;

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

Рис. 10

За даними звіту студенти навчаються аналізувати оптимальні розв'язки конкретних прикладних задач, використовуючи значення змінних в оптимальному плані відповідної двоїстої задачі оптимізації, а також додаткові двоїсті змінні, не будуючи моделі і не розв'язуючи безпосередньо двоїсті задачі оптимізації.

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

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

У прикладі про розподіл ресурсів в оптимальному плані прямої задачі Ресурсі використовується не повністю, його резерв дорівнює 50 (рис. 10, стовпчики Кінцеве значення, Обмеження Права сторона). Очевидно, коли б запас Ресурсуі становив не 450, а 451, то резерв дорівнював би 51. В такому разі збільшення значення цільової функції не відбувається. Звідси випливає, що для цього обмеження відповідна йому змінна в оптимальному плані двоїстої задачі дорівнює нулю (рис. 10, стовпчик Тіньова Ціна).

У той же час РесурсЗ використовується повністю. Відповідні до таких ресурсів змінні в оптимальному плані двоїстої задачі не дорівнюють нулю. Отже, в разі збільшення (зменшення) РесурсуЗ на одиницю, значення цільової функції збільшиться (зменшиться) на величину відповідної до цього ресурсу змінної в оптимальному плані двоїстої задачі, а саме на 12,5. (рис. 10, стовпчик Тіньова Ціна).

Який зміст мають додаткові двоїсті змінні? Якщо основні змінні увійшли в оптимальний план (х-|_ = 200 , х2 = 200), то відповідні додаткові двоїсті змінні дорівнюють нулю. Якщо основні змінні не увійшли в оптимальний план (х3 = 0 ), то відповідні додаткові двоїсті змінні не дорівнюють нулю (рис.10, стовпчик Приведена вартість). За цими величинами визначають, наскільки зменшиться значення цільової функції в разі примусового випуску одиниці даної продукції.

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

Для перевірки наведених вище розв'язків або результатів аналізу задачі оптимізації і для аналізу математичної моделі відповідної двоїстої задачі студентам пропонується використати спеціалізовані пакети Simplex, Optimization системи комп'ютерної математики Maple: > with, (simplex)', [basis, convexhull, cterm, definezero, display, dual, feasible, maximize, minimize, pivot, pivoteqn, pivotvar, ratio, setup, standardize ]

a ¦= 15-xl + 50-x2 + 35-x3;

15 xl + 50 x2 + 35 x3

L ¦= {xl + x2 < 450, xl < 250, 2-xl + 2-х2 + x3

800, xl + x2 < 450, 2-xl + x2 + x3 < 600};

{xl + x2 < 450, xl < 250, 2 xl + 2 x2 + x3 < 800,

2 xl + x2 + x3 < 600 }

b ¦= evalf {maximize {a, L, NONNEGATIVE));

{x2 = 200., x3 = 0., xl = 200.} evalf {subs {b, a));

25000.

fl *= dual{al, L2, u);

450 ul + 250 u2 + 800 u3 + 600 u4, {75 < ul + u2 + 2 u3 + 2 u4, 50 < ul + 2 u3 + u4, 35 < u3 + u4)

zl := minimize [fl[\],fl[2], NONNEGATIVE)-,

¦ «2 = 0, ul = 0, u4 = 25, иЗ =

evalf [subs [zl,fl[\]));

25000.

with (Optimization);

[ImportMPS, Interactive, LPSolve, LSSolve, Maximize,

Minimize, NLPSolve, QPSolve]

al *= 15-xl + 50-x2 + 35-x3;

_ 75 xl + 50 x2 + 35 x3

L2 ¦-- {xl + x2 < 450, xl < 250, 2-xl + 2-x2 + x3

800, xl + x2 < 450, 2-xl + x2 + x3 < 600};

{xl + x2 < 450, xl < 250, 2 xl + 2 x2 + x3 < 800,

2 xl + x2 + x3 < 600 }

LPSolve {al, L2, assume = nonnegative, maximize)-,

[25000., [xl = 200., x2 = 200., x3 = 0. ] ]

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



Подолання несумісності

Якщо умови задачі несумісні, то це означає, що не існує допустимого розв'язку задачі оптимізації. У цьому випадку математична модель відповідної задачі потребує коригування.

Для отримання несумісності у розглянутій вище задачі з навчальною метою змінимо умови вихідної задачі: використаємо значення змінних в оптимальному плані хг =200, х2 =200 і додатково введемо умову х3 =100.

Очевидно, що для випуску такої кількості продукції наявних ресурсів буде недостатньо.

Якщо розв'язувати дану задачу за допомогою MS Excel, отримаємо повідомлення «Пошук не може дати прийнятного розв'язку».

Для подолання несумісності введемо додаткові необхідні ресурси, додамо їх відповідно в праві частини обмежень (2) і знайдемо розв'язок задачі оптимізації :

+12+t з + t4 + t 5^min (4)

хі+х2 -- tx = 450

x1 -- t2 = 250

+2 x2+x3 -- t3 = 800 x1 +x2 -- t4= 450 2 x-i_ +x2 +x3 -- t5 = 6 0 0 x-i_ =200, x2 =200 , x3 =100,



Таким чином, мінімально необхідно додати 200 одиниць ресурсів, із них РесурсуЗ - 100 одиниць, Ресурсу5 - 100 одиниць. Це означає, що для заданого випуску продукції необхідно мати такі кількості ресурсів: РесурсуЗ - 900 одиниць, Ресурсу5 - 700 одиниць. В такому разі буде отримано 28750 одиниць прибутку.

Корисність такого підходу при подоланні несумісності важко переоцінити.

Подолання необмеженості цільової функції

Розв'язок задачі оптимізації буває необмеженим у тому випадку, коли область допустимих значень не має обмежень, що призводить до нескінченного зростання (чи спадання) цільової функції. Якщо таку задачу розв'язують за допомогою MS Excel, то на екрані про це свідчить повідомлення «Значення цільової функції не збігаються».

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

В якості індивідуальних проектів студенти розв'язують конкретні прикладні задачі лінійного, нелінійного, цілочислового, дискретного, стохастичного програмування і проводять всі розглянуті види аналізу отриманих оптимальних розв'язків, їх математичних та економічних показників.

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



Список використаних джерел

1. Жалдак М.І., Триус Ю.В. Основи теорії і методів оптимізації: Навчальний посібник. - Черкаси: Брама-Україна, 2005. - 608 с.

2. Кузьміна Н.М. Зміст і методика навчання курсу «Основи теорії і методів оптимізації» в педагогічному університеті // Науковий часопис НПУ імені М.П. Драгоманова. Серія № 2 Комп'ютерно-орієнтовані системи навчання: Зб. наук. праць / Редрада. - К. НПУ імені М.П. Драгоманова, 2012. - №13(20). - C. 85-89.

3. Кузьміна Н.М. Основи теорії і методів оптимізації: програма навчальної дисципліни для підготовки студентів спеціальностей 7.04030201, 8.04030201 «Інформатика*» Інституту інформатики НПУ імені М.П. Драгоманова// К.: Вид-во НПУ імені М.П. Драгоманова, 2014. - 28 с.

4. Кузьміна Н.М. Деякі методичні аспекти навчання основ теорії і методів оптимізації з комп'ютерною підтримкою // Науковий часопис НПУ імені М.П. Драгоманова. Серія № 2 Комп'ютерно-орієнтовані системи навчання: Зб. наук. праць / Редрада. - К. НПУ імені М.П. Драгоманова, 2015. - №15(22). - C. 42-49.

5. Курицкий Б.Я. Поиск оптимальных решений средствами Excel 7.0. - СПб.: BHV - Санкт- Петербург, 1997. - 384с.

Размещено на Allbest.ru

...