logo
ио теория

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

Перший крок при використанні графічного методу полягає в поданні області допустимих розв’язків, у якій водночас задовольняються всі обмеження моделі. Умови невід’ємності змінних обмежують область їх допустимих значень першим квадрантом координатної площини (частина площини над віссю x1 і справа від осі x2). Інші межі простору розв’язків зображені прямими лініями, побудованими по рівняннях, що отримані заміною знака “£” знаком “=" в обмеженнях. Області, в яких відповідні обмеження виконуються як нерівності ( в нашому випадку - нерівності із знаком “<”), указуються стрілками, спрямованими вбік допустимих значень змінних. Отриманий простір розв’язків задачі про фарби - багатокутник. У кожній точці, що належить внутрішній області або межам багатокутника розв’язків АВСDЕF, всі обмеження виконуються, тому розв’язки, що відповідають цим точкам, є допустимими. Серед безкінечногочисла таких точок можна знайтиточку оптимальнного розв’язку, якщо з'ясувати, в якому напрямку зростає цільова функція.На графік наносять лінію рівня цільової функції c1×x1+c2×x2=z0, де z0 - довільне значення z. Будують вектор N (c1, c2), що є нормальним до ліній рівня цільової функції й визначає напрямок оптимізації z. Лінію рівня зрушують паралельно самій собі вздовж вектора N доти, поки вона не вийде за межі області допустимих розв’язків. Остання точка цієї області й буде точкою оптимуму. Очевидно, що оптимальному розв’язку відповідає точка С- точка перетину прямих (1) і (2). Значення x1 та x2 в точці С визначаються шляхом розв’язання системи рівнянь: Зазначимо, що у випадку, коли лінії рівня z мають такий самий нахил, як пряма зв’язуючого обмеження (тобто такого, що проходить через оптимальну точку), матимемо безліч оптимумів на відрізку.