Практична робота №4 на тему Технологія розв’язання оптимізаційних задач, НУДПСУ

Практична робота №4

Тема: Технологія розв’язання оптимізаційних задач

Мета: Ознайомлення зі спеціальним інструментарієм (оптимізатором) електронної таблиці Excel для рішення оптимізаційних задач.

Програмне забезпечення: Табличний процесор MS Excel

Завдання: Використання табличного процесора MS Excel для пошуку оптимального рішення розв’язання оптимізаційних задач

Короткі теоретичні відомості

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

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

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

1. Є єдина цільова комірка. У неї користувач повинний увести формулу, указавши пізніше в програмному діалозі який екстремум необхідний ( максимум чи мінімум). Після завершення побудови моделі й ініціалізації розрахунку програма автоматично повинна домогтися для цієї комірки екстремального результату. Формула буде обчислювати цільовий показник, наприклад, чистий  прибуток чи витрати, при автоматичному варіюванні значень інших (змінюваних) комірок. Для цільової комірки в програмному діалозі (а не в самій комірці) можна установити і конкретне цільове значення, якщо для його досягнення необхідно буде підбирати значення взаємозалежних з нею комірок. Задачі такого типу відносять до так званого аналізу – яким чином? (how саn-аналізу).

2. У формулі цільової комірки повинні бути зроблені посилання на одну чи більш змінюваних комірок, від значень яких залежить результат. Вони можуть бути названі також невідомими чи змінними для рішення. Функція (Поиск решения) установлює значення змінюваних комірок так, щоб знайти для формули цільової комірки оптимальне рішення.

3. Обмежуючих комірок може бути не менш однієї на кожну змінювану комірку. Може існувати і деяка кількість додаткових комірок обмежень, наприклад, обмеження по обсязі ресурсу й обмеження по попиті (мінімальний попит, максимальний попит).

Типи задач для оптимізатора:

1. Задачі про перевезення: наприклад, мінімізація витрат по доставці товарів з декількох фабрик у кілька магазинів з урахуванням попиту.

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

3. Задачі управління асортиментом товарів: витяг максимального прибутку за допомогою варіювання асортиментним набором товарів (при дотриманні вимог клієнтів). Аналогічна задача виникає при продажі товарів з різною структурою витрат, рентабельністю і показниками попиту.

4. Задачі заміни чи змішування матеріалів: наприклад, маніпуляція матеріалами з метою зниження собівартості, підтримки необхідного рівня якості і дотримання вимог споживачів.

5. Задачі лінійної алгебри: рішення лінійних рівнянь.

У технологічному процесі рішення лінійної оптимізаційної задачі за допомогою Excel виділяються три типових етапи:                    

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

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

3) заключний (збереження результатів поточного рішення і збереження створеної моделі для можливих майбутніх рішень).

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

Хід виконання роботи

І. Підготовчий етап

Підприємство випускає продукцію 4-х видів: А, В, С, D. Щомісяця воно може випускати не більш 1000 екземплярів (при цьому кожного типу - не менше 150). Протягом місяця 500 працівників працюють по 150 годин кожний. Підприємство може витратити за місяць не більш 1000 тон сировини.

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

В основі розрахунку лежать нормативи, розроблені службою техніко-економічного планування виробництва. Ці нормативні дані зведені в таблицю:

Уточнимо набір наявних даних і їхній зміст у контексті оптимізаційної задачі:

• кожен вид продукції - це перемінна (A, B, C, D);

• ліміт по ресурсах - основне обмеження;

• потужність підприємства і дилерське замовлення - це нижня і верхня границі виробництва продукції (додаткове обмеження);

• максимум прибутку - це цільова функція;    

• виробництво такого набору моделей і кількості виробів, що дасть вам максимальний прибуток - це рішення.

Обговоримо і злегка формалізуємо обмеження. Перше обмеження має вид: A+B+C+D=< 1000.

Однак відомо, що підприємство повинно випускати не менш 600 одиниць, тому друге обмеження має вид: A+B+C+D => 600.

Витрати сировини не можуть перевищувати 1000 тонн на місяць, тому третє обмеження умовне має вид:

(A сировина) + (B сировина) + (C сировина) + (D сировина) =< 1000.

Кількість годин, що щомісяця відпрацьовують усі працівники підприємства, не може перевищувати 75000, тобто четверте обмеження умовне має вид:

(A годин) + (B годин) + (C годин) + (D годин) =< 75000.

Таким чином, ми маємо систему лінійних нерівностей:

- A+B+C+D=< 1000;

- 0.5 A + 0.9 B + 1.0 C + 1.3 D =< 1000;

- 70 A + 100 B + 90 C + 130 D =< 75000;

- A+B+C+D=>600.                                        

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

Порядок дій з електронною таблицею Excel на підготовчому етапі

1. Ввести дані про витрати ресурсів на одиницю потужності (блок В2..Е4), тобто на одиницю продукції, а також дані про прибуток з одиниці продукції (блок В5..Е5).

2. Ввести в окрему групу комірок (F2..F4)  константи обмежень, що будуть потрібні нам на етапі основного діалогу при формулюванні обмежень.

3. Ввести рядок комірок (В8..Е8) для майбутнього оптимального результату, - ці комірки є порожніми на початку рішення, але ми будемо посилатися на них, уводячи формули в комірки G2..G4 для підрахунку витрат ресурсів на програму виробництва, а також при уведенні формули цільової функції (прибуток):

в G2=B2*B8+C2*C8+D2*D8+E2*E8;

 в G3=B3*B8+C3*C8+D3*D8+E3*E8;

в G4=B4*B8+C4*C8+D4*D8+E4*E8.

4. Ввести формулу для підрахунку прибутку в комірку G5, - повний вид цієї формули відображений у рядку формул (угорі таблиці) =B5*$B$8+C5*$C$8+D5*$D$8+E5*$E$8

5. Ввести верхні і нижні обмеження даних  в комірки В6..Е7.

Основний етап

Активізувати \Сервис, Поиск решения\ і в діалоговому вікні \Поиск решения\ для нашої задачі виконати дії:

1) визначите адресу цільової комірки G5;

2) активізуйте один з перемикачів бажаного екстремума (Мах);

3) задайте, які осередки програма повинна змінювати доти, поки не буде досягнутий максимальний прибуток, тобто В8:Е8;

4) для початку введення обмежень виберіть опцію \Добавить\. Відкриється нове вікно \Добавление ограничения\ для визначення трьох частин окремого обмеження. Послідовність уведення декількох обмежень несуттєва;

5) укажемо верхні границі перемінних $В$8:$Е$8 <= $В$7:$Е$7, і для введення нового обмеження виберемо кнопку \Добавить\, що очистить вікно для визначення наступного обмеження;

6) покажемо нижні границі перемінних $В$8:$Е$8 >= $В$6:$Е$6 і знову активізуємо кнопку \Добавить\ для визначення обмежень по ресурсах;

7) задамо обмеження по ресурсах $G$2:$G$4 <= $F$2:$F$4;

8) задати інші обмеження ($B$8:$E$8=целое);

9) після введення останнього обмеження активізуємо кнопку ОК, вона поверне нас у вікно \Поиск решения\;

10) після перевірки всіх установок у діалоговому вікні \Поиск решения\ активізуємо кнопку /Выполнить/.

Заключний етап

Для одержання звіту за результатами, у вікні /Результати поиска решения/ визначите /Отчет по результатам/ чи інший звіт і активізуйте ОК. Звіт автоматично запишеться в новий лист робочої книги. 

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

Контрольні питання

1. Назвіть три характерних ознаки оптимізаційної задачі.

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

3. Опишіть порядок підготовки цільової комірки до початку основного етапу технології. Що повинно бути в комірці наприкінці рішення?

4. Назвіть правила підготовки змінюваних комірок. Скільки їх може бути в одній задачі?

З повагою ІЦ "KURSOVIKS"!