gn="justify"> + a i2 = b i (i = 1, k), x 1 = 0 і x 2 = 0. У цьому випадку, якщо система нерівностей (4.9), (4.10) сумісна, область її рішень є безліч точок, що належать всім зазначеним півплощин.
Так як безліч точок перетину даних півплощин опукле, то областю допустимих рішень (ОДР) задачі (4.8) - ( 4.10) є опукле безліч, яке називається багатокутником рішень. Сторони цього багатокутника лежать на прямих, рівняння яких виходять з вихідної системи обмежень заміною знаків нерівностей на знаки точних рівностей.
Таким чином, вихідна завдання лінійного програмування полягає в знаходженні такої точки області допустимих рішень, в якій цільова функція F приймає максимальне значення. Ця точка існує тоді, коли багатокутник рішень не порожній і на ньому цільова функція обмежена зверху. За зазначених умов в одній з вершин ОДР цільова функція приймає максимальне значення. Для визначення даної вершини побудуємо лінію рівня c 1 x 1 + c 2 x 2 = h (де h - деяка постійна), що проходить через ОДР, і будемо її пересувати в напрямку вектора C = (з 1 ; з 2 ) до тих пір, поки вона не пройде через останню її загальну точку з багатокутником ОДР. Координати зазначеної точки і визначаю оптимальний план даної задачі.
При знаходженні рішення задачі можуть зустрітися випадки, зображені на рис. 5.1-5.4 . Рис. 5.1 характеризує такий випадок, коли цільова функція приймає максимальне значення в єдиній точці А. З рис. 5.2 видно, що максимальне значення цільова функція приймає в будь-якій точці відрізка АВ.тметім, що знаходження мінімального значення лінійної функції при даній системі обмежень відрізняється від знаходження її максимального значення при тex ж обмеженнях лише тим, що лінія рівня c 1 x 1 + c 2 x 2 = h пересувається не в напрямку вектора С, а в протилежному напрямку.
Той факт, що оптимальне рішення знаходиться в одній з вершин багатокутника ОДР, дозволяє зробити ще два...
