2.4. Завдання

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

,

рядки якої відповідають певному виду сировини, а стовпці – певному виду продукції, що виробляється. Запаси сировини на підприємстві визначаються матрицею-стовпцем

.

На даний момент часу ринкові ціни на кожний вид продукції описуються матрицею-рядком .

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

2.5. Приклад виконання лабораторної роботи № 2

Побудуємо математичну модель задачі. Матриця описує можливі плани виробництва, де кількість продукції 1-го типу позначається , а кількість продукції 2-го типу – . Відповідно

. (2.3^І)

Отже, маємо обмеження на знак.

Витрати сировини всіх видів на виготовлення продукції обох типів можна записати у вигляді нерівностей:

(2.2^І)

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

Сукупність нерівностей (2.2^І) та (2.3^І) визначає множину можливих планів виробництва. Серед них оптимальним планом є той, що забезпечує найбільший прибуток від реалізації продукції. Відповідно критерієм ефективності є функція, що характеризує загальний прибуток від реалізації при заданому рівні ринкових цін на продукцію:

. (2.1^І)

Співвідношення (2.1^І) – (2.3^І) утворюють математичну модель задачі про оптимальне використання сировини. Отже, цільова функція і всі функції системи обмежень є лінійними, тобто маємо задачу лінійного програмування. Оскільки цільова функція цієї задачі досліджується на максимум і всі нерівності основної системи обмежень мають знак , то математична модель задачі лінійного програмування надана у стандартній формі. Задача має лише дві змінні, отже, її можна розв’язати за допомогою графічного методу.

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

1. За основною системою обмежень та обмеженнями за знаком будуємо многокутник планів, тобто знаходимо область значень змінних та . Для цього за кожною нерівністю основної системи обмежень знайдемо на площині 0Х₁Х₂ область її виконання. Наприклад, визначимо півплощину, де виконується нерівність . З цією метою перепишемо це обмеження у вигляді рівняння і перетворимо рівняння прямої до вигляду у відрізках на осях, поділивши обидві його частини на 220. Матимемо:

.

Це означає, що пряма відсікає на осі 0Х₁ відрізок 55 (знаменник першого дробу в рівнянні прямої) та на осі 0Х₂ – теж відрізок 55 (знаменник другого дробу). Відклавши ці відрізки вздовж відповідних осей, побудуємо цю пряму (рис. 3.1). Щоб визначити півплощину, де виконується вихідна нерівність, підставимо в цю нерівність координати точки, що не належить прямій , наприклад, початок координат. Так, для т. О (0; 0) маємо: . Оскільки отримали правильну числову нерівність, то т. О належить тій півплощині, де вихідна нерівність задовольняється. Отже, перпендикулярно до лінії ставимо дві стрілки, які вказують півплощину, де ця нерівність виконується.

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

Рис. 2.6. Графічний розв’язок

2. За коефіцієнтами цільової функції знаходимо вектор нормалі і перпендикулярно до нього через початок координат проводимо лінію рівня . У даному випадку лінія рівня входить до многокутника планів через т. О, якій відповідає опорний план . За цим планом цільова функція має найменше з можливих значень: .

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

3. Визначаємо лінії, перетин яких утворює вершину , якій відповідає максимальне значення цільової функції. Це лінії та . Отже, оптимальному плану відповідає повне використання сировини 1-го та 2-го видів, оскільки відповідні цим видам сировини нерівності основної системи обмежень перетворились на рівняння. Утворюємо систему рівнянь, які відповідають лініям та :

Розв’язком цієї системи є оптимальний план .

4. За оптимальним планом задачі обчислюємо максимальне значення цільової функції:

(ум. од.).

5. За оптимальним планом сировина 1-го та 2-го видів використана повністю. Визначимо надлишки інших видів сировини. Для цього підставимо значення оптимального плану до інших обмежень основної системи. Залишки сировини 3-го виду становлять

,

сировини 4-го виду

.

Перетворимо вихідну математичну модель задачі. Для цього поряд з основними змінними, які визначають кількість продукції кожного типу, введемо додаткові змінні. Ці змінні визначають залишки сировини кожного виду, вони вводяться у нерівності основної системи обмежень з метою перетворення їх на рівняння. Таким чином, застосування додаткових змінних дозволяє перейти від стандартної форми математичної моделі задачі лінійного програмування до канонічної, або основної. Так, залишки сировини 1-го виду позначимо , 2-го – , 3-го – і 4-го – . Оскільки залишки сировини підприємство не продає, то цільова функція, що визначає прибуток підприємства, залишилась без змін.

Отже, математична модель задачі набуває вигляду:

, (2.1^ІІ)

(2.2^ІІ)

, . (2.3^ІІІ)

Знайдемо опорні розв’язки основної системи обмежень (2.2^ІІ) за допомогою MS Excel. Для цього здійснимо перетворення розширеної матриці системи (2.2^ІІ) за методом Жордана – Гаусса (рис. 2.7).

Рис. 2.7. Опорні плани задачі

Зверніть увагу, що додаткові змінні у системі рівнянь (2.2^ІІ) утворюють одиничну матрицю , відповідно, її визначник не дорівнює нулю. Отже, ранг матриці коефіцієнтів системи дорівнює чотирьом, тоді кількість базисних змінних теж дорівнює чотирьом, а кількість вільних невідомих – двом. Згідно з цим кількість загальних розв’язків системи рівнянь визначається як кількість сполучень з множини, що містить шість елементів, по чотирьом:

.

Однак многокутник планів має шість вершин, звідси випливає, що система рівнянь (2.2^ІІ) матиме лише шість опорних розв’язків. Ці розв’язки є опорними планами задачі про оптимальне використання сировини і саме серед них треба шукати оптимальний план. Визначимо всі опорні розв’язки як координати кутів многокутника планів.

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

План означає, що виробляється лише продукція першого типу у кількості 40 одиниць, при цьому сировина 4-го виду використана повністю, залишки сировини 1-го виду становлять 60 одиниць, 2-го – 240 одиниць, 3-го – 175 одиниць. За цим планом прибутки підприємства при реалізації продукції становитимуть

(ум. од.).

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

(ум. од.);

(ум. од.);

(ум. од.);

(ум. од.).

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

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

.

Зверніть увагу, що при розв’язанні системи рівнянь (2.2^ІІ) було отримано відомості не тільки про кількість продукції, яку підприємство виробляє за оптимальним планом, але і про залишки сировини кожного виду при виконанні цього плану.

Для застосування надбудови «Поиск решения» приймемо такий алгоритм.

1. Побудуємо на робочому аркуші книги MS Excel таблицю, що відповідає умовам задачі, за таким зразком (рис. 2.8).

Рис. 2.8. Вихідні дані задачі визначення оптимального плану

2. Стовпчик лівої частини D6:D10 заповнюється за допомогою функції СУМПРОИЗВ(). Так, D6 = СУМПРОИЗВ($B$4:$C$4,B6:C6). Вважаємо, що первинний план виробництва (B4:C4) складає 0 одиниць за кожним видом продукції. Зверніть увагу, що позначення ($B$4:$C$4) свідчить про відповідність обраного діапазону обчисленим значенням усіх клітин стовпчика лівої частини. Стовпчик правої частини E6:E9 відображає існуючі обмеження щодо ресурсів.

3. Виділяємо клітину цільової функції (D10).

4. Активізуємо режим «Сервис Поиск решения».

5. Заповнюємо поле «Установить целевую ячейку». Обираємо варіант оптимізації – «максимальному значению». У рядку «Изменяя ячейки» посилаємось на блок керованих змінних B4:C4. У вікні «Ограничения» вказуємо співвідношення між лівою та правою частинами системи обмежень. Це можна зробити для діапазону клітин одночасно, якщо нерівності основної системи обмежень мають однакові знаки (рис. 2.9).

Рис. 2.9. Діалогове вікно «Поиск решения»

Для цього натискаємо «Добавить» і у вікні вводимо обмеження (або викликаємо вікно «Изменение ограничений», якщо це необхідно).

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

Обмеження можна вводити кожне окремо або блоками, що мають один знак. Перед введенням кожного наступного обмеження натискають клавішу «Добавить».

Рис. 2.10. Діалогове вікно «Изменение ограничений»

6. Натискаємо кнопку «Параметры» та вибираємо режим «Линейная модель» і «Неотрицательные значения» (рис. 2.11), потім натискаємо OK та повертаємось у діалогове вікно «Поиск решения».

Рис. 2.11. Діалогове вікно «Параметры поиска решения»

7. Тепер натискаємо кнопку «Выполнить». Унаслідок цього на екрані з’являється вікно «Результаты поиска решения», у якому відображено повідомлення про результат роботи. Повідомлення, яке виводиться у діалоговому вікні, може бути такого змісту: Решение найдено. Все ограничения и условия оптимальности выполнены. Це означає, що ми отримали розв’язок, який можемо зберегти натисканням клавіші OK, якщо перемикач стоїть у положенні Сохранить найденное решение. У цьому ж вікні пропонується вивести звіти Результаты, Устойчивость Пределы, для чого слід вказати тип звіту. Однак повідомлення може мати такий зміст: Значения целевой ячейки не сходяться, тобто задача у тому вигляді, як вона була введена, не має розв’язків. Причиною може бути як помилка при введенні моделі, так і те, що задача дійсно не має розв’язку. У цьому випадку необхідно провести додатковий аналіз економічного аспекту моделі задачі.

Результат розв’язання представлено на рис. 2.12.

Рис. 2.12. Результат розв’язання задачі