Графічне рішення задачі ЛП

ТЕМА 3. ЛІНІЙНЕ ПРОГРАМУВАННЯ

Основи лінійного програмування.

Моделі з двома змінними у лінійному програмуванні (ЛП).

Графічне рішення задачі ЛП

Графічне рішення з програмою TORA

ОСНОВИ ЛІНІЙНОГО ПРОГРАМУВАННЯ

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

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

Лі́нія — геометричне місце точок, що задовільняє певне рівняння.

¾ пряма, що з’єднує якісь дві точки, визначає напрям.

Загальне рівняння прямої на плоскості:

y = ах + в

де: a і b — постійні.

 

Лінійне програмування успішно застосовується у військовій сфері, індустрії, сільському господарстві, транспортній галузі, економіці, системі охорони здоров*я та соціальних науках. Широке застосування цього методу підкріплено високоефективними комп*ютерними алгоритмами, які реалізують цей метод.

Лінійне програмування об'єднує методи вирішення завдань, які описуються лінійними рівняннями:

1) складання оптимального плану виробництва,

2) вибір структури інвестицій,

3) складання розкладу,

4) маршрутизація перевезень

2. МОДЕЛІ З ДВОМА ЗМІННИМИ У
ЛІНІЙНОМУ ПРОГРАМУВАННІ (ЛП)

Приклад 1.

Етап 1. Отримання змісту задачі.

Компанія «СМАРТ» виробляє фарбу для внутрішніх та зовнішніх робіт з сировини двох типів: М1 та М 2.

	Витрати сировини на тонну фарби (т)	Максимально можливі щоденні витрати сировини
	для зовнішніх робіт (х1)	для внутрішніх робіт (х2)
Сировина М1
Сировина М2
Дохід на тонну фарби (тис. $)z

 

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

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

Етап 2. Формалізація задачі у вигляді математичної моделі, яка складається з трьох основних елементів:

1) змінні, які слід визначити;

2) цільова функція, яку треба оптимізувати;

3) обмеження, яким мають задовольняти змінні

1) В нашому прикладі необхідно визначити щоденні обсяги виробництва фарби для внутрішніх і зовнішніх робіт. Об означимо ці змінні:

х₁ – щоденний обсяг виробництва фарби для зовнішніх робіт;

х₂ – щоденний обсяг виробництва фарби для внутрішніх робіт.

 

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

Максимізувати z = 5х₁ + 4х₂

3) Умови обмеження:

3.1.)

Використовуємий об*єм сировини для виробництва обох видів фарби

≤

Максимально можливі щоденні витрати сировини

 

Отже, відповідно отримуємо:

Використовуємий обсяг сировини (т): М1 = 6х₁ + 4х₂

Використовуємий обсяг сировини (т): М2 = 1х₁ + 2х₂

 

А оскільки щоденні витрати сировини М1 та М2 обмежені відповідно24 та 6 т, то отримуємо таке обмеження:

6х₁ + 4х₂ ≤ 24 (сировина М1)

1х₁ + 2х₂ ≤ 6 (сировина М2)

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

х₂ ¾ х₁ ≤ 1

Друге обмеження - максимальний щоденний обсяг виробництва фарби для внутрішніх робіт не має перевищувати 2 т, тобто:

х₂ ≤ 2

 

3.3.) Ще одне обмеження у тому, що х_1, х₂ мають бути невід*мними. Таким чином додаємо, ще обмеження:

х₁ ≥ 0

х₂ ≥ 0

Остаточна формалізована задача прийме такий вигляд:

Максимізувати z = 5х₁ + 4х₂

При виконанні обмежень:

6х₁ + 4х₂ ≤ 24

х₁ + 2х₂ ≤ 6

-х₁ + х₂ ≤ 1

х₂ ≤ 2

х₁ ≥ 0

х₂ ≥ 0

 

Таким чином, будь-яке рішення, що задовольняє обмеження моделі, є допустимим ???

Наприклад, х₁ = 3, х₂ = 1. Задача має дуже багато допустимих рішень і тому необхідна ефективна процедура відбору допустимих рішень для пошуку оптимального.

ГРАФІЧНЕ РІШЕННЯ ЗАДАЧІ ЛП

Графічний спосіб рішення задачі ЛП складається з двох етапів:

1) побудова простору допустимих рішень, які задовольняють всі обмеження моделі;

2) пошук оптимального рішення серед всіх точок простору допустимих рішень.