Методичні рекомендації до виконання завдань:

Задача 1. Розв’язування задачи проводиться відповідно до такої послідовності етапів:

1. Побудова математичної моделі. Нехай x₁ – кількість полиць моделі А, що виготовляється фірмою за тиждень, а x₂ – відповідна кількість полиць моделі В. Цільова функція моделі – максимізація прибутку фірми від реалізації продукції. Математично вона записується так:

Z = 50x₁ + 30x₂ → max.

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

Обмеження на час роботи верстатів 1 і 2 набирають такого вигляду: для верстата 1

30x1 + 15x2 2400 (хв.);

для верстата 2

12x1 + 26x2 2160 (хв.).

Обмеження на попит набирають вигляду:

x1 – x2 30 іx2 80.

Отже, економіко-математична модель поставленої задачі має вигляд

2. Розв’язання. Замінимо знаки нерівностей на знаки рівностей і побудуємо графіки відповідних прямих (рис. 5.1). Кожна з побудованих прямих поділяє площину системи координат на дві півплощини. Координати точок однієї задовольняють розглянуту нерівність, а іншої – не задовольняють. Щоб визначити необхідну півплощину (на рис. 1 її напрям позначено стрілкою), потрібно взяти будь-яку точку та перевірити, чи задовольняють її координати зазначене обмеження. Якщо задовольняють, то півплощина, в якій міститься вибрана точка, є геометричним зображенням нерівності. У протилежному випадку таким зображенням є інша півплощина. Умова невід’ємності змінних x1 0,x20 обмежує область допустимих планів задачі першим квадрантом системи координат. Переріз усіх півплощин визначає область допустимих планів задачі – шестикутникOABCDE.

Рисунок 5.1 – Визначення області допустимих планів

Поставлену задачу буде розв’язано, якщо ми відшукаємо таку вершину багатокутника OABCDE, в якій цільова функція Z набуває найбільшого значення.

Для цього будуємо вектор = {50; 30}. Він задає напрям збільшення значень цільової функції Z, а вектор, протилежний йому, – напрям їх зменшення.

Побудуємо лінію, що відповідає, наприклад, значенню Z = 0. Це буде пряма 50x₁ + 30x₂ = 0, яка перпендикулярна до вектора і проходить через початок координат. Оскільки маємо визначити найбільше значення цільової функції, то пересуваємо пряму 50x₁ + 30x₂= 0 в напрямі вектора доти, доки не визначимо вершину багатокутника, яка відповідає оптимальному плану задачі. Останньою спільною точкою цієї прямої та багатокутника OABCDE є точка C. Координати цієї точки визначають оптимальний план задачі.

Координати точки С визначаються перетином прямих

Розв’язавши цю систему, дістанемо x1 = 50, x2 = 60. Отже, X = (50; 60); max Z = 50 50 + 30 60 = 4300.

Це означає, що коли фірма щотижня виготовлятиме 50 збірних книжкових полиць моделі А та 60 – моделі В, то вона отримає максимальний прибуток в 4300 у.о. При цьому тижневий фонд роботи верстатів 1 і 2 буде використано повністю.

Задача 2.

1. Проводимо пряму (рис.5.2) через точки з координатами:

х₁ = 0; х₂=16/(–5)=–3,2;

х₁ = 2; х₂=0;

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

Рисунок 5.2. Графік прямої лінії

Точка задовольняє умові, тоді цій нерівності задовольняють усі точки множини, що лежать лівіше прямої;

2) проводимо пряму (рис.5.2) через точки з координатами

х₁ = 0; х₂=0,667;

х₁ = 2; х₂=0;

Рисунок 5.3 – Графік прямої

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

3) проводимо пряму (рис.5.4):

Рисунок 5.4 – Графік прямої

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

4) обмежуємо допустиму область умовами та(рис.5.5).

Рисунок 5.5 – Визначення обмежень допустимої області

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

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

; ;

; .

Таким чином, .

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

Задача 3. Побудуємо прямі (рис. 5.6). На рис. 5.6 допустима множина не обмежена. Значенняліній рівня функціїбудуть зменшуватись при переміщенні у напрямку, протилежному градієнту. Очевидно, щоі задача не має оптимального розв’язку (цільова функція не обмежена знизу).

Рисунок 5.6 – Графічний роз’вязок задачи

Питання для самоконтролю:

1. Назвіть основні етапи графічного розв’язування задач лінійного програмування?

2. Що графічно являє собою область допустимих планів?

3. Назвіть умови графічного розв’язання ЗЛП?