02 Знаходження максимуму цільової функції

Знаходження максимуму цільової функції

Ми використовуємо модель, побудовану для компанії Reddy Mikks, щоб показати обидва етапи графічного рішення задачі ЛП.

Етап 1. Побудова простору допустимих рішень.

Спочатку проведемо осі: на горизонтальній будуть вказуватися значення змінної x 1. а

на вертикальній - x 2. Далі розглянемо умова невід'ємності змінних: x 1 0 і x 2 0. Ці два обмеження показують, що простір допустимих рішень буде лежати в першому квадранті.

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

Тепер розглянемо, як графічно інтерпретуються нерівності. Кожне нерівність ділить площину x 1. x 2 на два півпростору, які розташовуються по обидва боки прямий, яка відповідає даному нерівності. Точки площині,

розташовані по одну сторону прямої, задовольняють нерівності (припустиме півпростір), а точки, що лежать по інший бік, - немає. "Тестової" точкою,

перевіряє, точки якого полупространства задовольняють нерівності, а якого - ні,

може служити точка (0, 0). Наприклад, ця точка задовольняє першому нерівності

6 x 1 4 x 2 24 (тут 6 * 0 + 4 * 0 = 0 <24 ). Это означает, что точки полупространства,

що містить початкову точку (0,0), задовольняють цьому нерівності. На рис. 1

допустимі півпростору показані стрілками.

У тому випадку, коли точка (0,0) не задовольняє нерівності, допустимим півпростором буде те, яке не містить цю точку. Якщо ж пряма проходить через цю точку, слід як "тестової" взяти будь-яку іншу точку.

Етап 2. Знаходження оптимального рішення.

Точки простору допустимих рішень, показаного на рис. 1, задовольняють

одночасно всім обмеженням. Це простір обмежений відрізками прямих, які з'єднуються в кутових точках А, В, С, D, Е і F. Будь-яка точка, розташована всередині або на кордоні області, обмеженою ламаної ABCDEF, є допустимим рішенням, тобто

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

Знаходження оптимального рішення вимагає визначення напрямку зростання цільової функції z 5 x 1 4 x 2. Ми можемо прирівняти z до кількох зростаючим значенням, наприклад 10 і 15. Ці значення, підставлені замість z в вираз цільової функції, породжують рівняння прямих; для значень 10 і 15 отримуємо рівняння прямих

5 x 1 4 x 2 10 і 5 x 1 4 x 2 15. На рис. 2 ці прямі показані штриховими лініями, а

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

і буде точкою оптимуму.

На рис. 2 видно, що оптимальне рішення відповідає точці С. Ця точка є місцем перетину прямих (1) і (2), тому її координати x 1 і х 2 знаходяться як рішення системи рівнянь, які задають ці прямі:

Рішенням цієї системи буде х 1 = 3 і х 2 = 1.5, при цьому значення цільової функції дорівнює z = 21. Отримане рішення означає, що для компанії Reddy Mikks оптимальним вибором буде щоденне виробництво 3 т фарби для зовнішніх робіт і 1.5 т - для внутрішніх робіт з щоденним доходом в 21 000.