Зауваження

План

Графічний метод вирішення ЗЛП

1. Геометрична інтерпретація задачі лінійного програмування.

2. Алгоритм розв’язання задачі лінійного програмування графічним методом.

3. Розв’язання задачі лінійного програмування графічним методом.

1. Геометрична інтерпретація задачі лінійного програмування

При n=2 можна привести геометричну інтерпретацію на двовимірній площині. Можливі наступні варіанти множини допустимих рішень.

Вектор-градієнт вказує напрямок найшвидшого зростання функції і складається з приватних похідних:

Для F(x)=c₁x₁+c₂x₂+…+c_jx_j+…+c_nx_n gradF(x)=(c₁,c₂,…,c_j,…,c_n). За умови двовимірного простору його легко виразити у вигляді:

2. Алгоритм використання графічного методу:

1. Будуємо множину допустимих рішень;

2. Будуємо вектор-градієнт;

3. Проводимо довільну лінію рівняння цілі F=const (простіше F=0) перпендикулярно до вектора-градієнта;

4. При розв’язання задачі на максимум переміщуємо лінію рівняння F=const у напрямку вектора-градієнта, до тих пір, доки вона займе крайнє положення по відношенню до множини допустимих рішень. У випадку задачі на мінімум – перемуруємо лінію у оберненому напрямку.

3. Розв’язання задачі лінійного програмування графічним методом.

Для вирішення задачі лінійного програмування графічним методом необхідно представити її у формулірізованому вигляді.

Задача використання сировини.

Для виготовлення двох видів продукції Р₁ і Р₂ використовують три види сировини: S₁, S₂, S₃. Запаси сировини, кількість одиниць сировини, що використовується для виготовлення одиниці продукції, а також розмір прибутку, що буде отриманий у результаті реалізації одиниці продукції, наведені у таблиці 2.1.

Таблиця 2.1.

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

Рішення.

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

2х₁ + 5х₂ 20

8х₁ + 5х₂ 40

5х₁ + 6х₂ 30

Яка показує, що кількість сировини, яка використовується на виготовлення продукції, не може перевищувати наявні запаси. Якщо продукція Р₁ не виготовляється, то х₁=0; у протилежному випадку x₂=0. Те ж саме і для продукції Р₂. Таким чином, на невідомі х₁ і х₂ повинна бути накладена вимога невід’ємності : х₁>0, х₂>0.

Кінцеву ціль задачі, що вирішується – отримання максимального прибутку від реалізації продукції – виразимо як функцію двох змінних х₁ и х₂. Реалізація х₁ одиниць продукції Р₁ и х₂ одиниць продукції Р₂ дає Відповідно 50х₁ і 40х₂ грн. прибутку, загальний прибуток Z = 50х₁ + 40х₂ (грн.)

Умовами не зазначена неділимість одиниці продукції, тому х₁ і х₂ (план випуску продукції) можуть бути й дробовими числами.

Потрібно знайти такі х₁ і х₂, за яких функція Z досягає максимум, тобто знайти максимальне значення лінійної функції Z = 50х₁ + 40х₂ за обмежень:

2х₁ + 5х₂ ≤20

8х₁ + 5х₂ ≤40

5х₁ + 6х₂ ≤30

х₁≥0, х₂≥0.

Побудуємо багатокутник рішень (мал. 2.1).

Для цього у системі координат х₁Ох₂ на площині зобразимо граничні прямі:

2х₁ + 5х₂ = 20 (L₁)

8х₁ + 5х₂ = 40 (L₂)

5х₁ + 6х₂ = 30 (L₃)

х₁ = 0, х₂ = 0.

Узявши яку-небудь точку, наприклад, початок координат, установимо, яку півплощину визначає відповідна нерівність (ці півплощини на мал. 2.1 показані штрихами). Багатокутником рішень даної задачі є обмежений п’ятикутник ОАВСD.

Для побудови прямої 50х₁ + 40х₂ = 0 будуємо радіус-вектор N = (50;40) = 10(5;4) и через точку O проводимо пряму, перпендикулярну йому. Побудовану пряму Z=0 переміщуємо паралельно самій собі у напрямку вектора N. З мал. 2.1 виходить, що опорною по відношенню до багатокутника рішень ця пряма стає у точці B, де функція Z приймає максимальне значення. Точка B лежить на перетині прямих L₃ і L₂. Для визначення її координат розв’яжемо систему рівнянь

8x₁ + 5х₂ = 40

5х₁ + 6х₂ = 30

Оптимальний план задачі: х₁=90/23=3,9; х₂=40/23= 1,7. Підставляючи значення х₁ і х₂ до лінійної функції, отримуємо Z_max = 50*3,9 + 40*1,7 = 263

Таким чином, для того щоб отримати максимальний прибуток у розмірі 263 грн., необхідно запланувати виробництво 3,9 од. продукції Р₁ і 1,7 од. продукції Р₂.

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

Таким чином отримуємо нову симплексну таблицю, що відповідає новому плану (перехід до етапу ІІ).

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