Рішення X

Рис.3 Приклад ЗЛП, що має безліч рішень (ребро АВ багатогранника допустимих рішень ABCDE)

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

Рис.4 Приклад ЗЛП, що має безліч допустимих рішень.

залежить від того, обмежена знизу на множині Xцільова функція або немає. Виникаючі ситуації ті ж, що й у завдань максимізації.

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

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

Кожна нерівність системи обмежень та умова невід'ємності є напівплощиною. Перетин напівплощин утворює опукле багатокутне безліч (багатогранник допустимих рішень).

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

Для вирішення задачі лінія рівня зсувається в межах області допустимих рішень (багатогранника допустимих рішень) у напрямку вектора-градієнта grad z=f(x) =

до крайньої точки області для завдання максимізації, і в напрямку антиградієнта

grad z=

для задачі мінімізації.Координати цієї

точки та визначають рішення ЗЛП (оптимальний план завдання).

Приклад 1 Розв'язати геометричним способом злп:

4x1+5x2  61 (a)

Побудуємо область допустимих рішень ЗЛП, що є безліч точок, що задовольняють обмеженням завдання. Область допустимих рішень – обмежений багатокутник, виділений зовнішній

Рис.5 Приклад геометричного рішення ЗЛП у стандартній формі при n=2.

Вектор-градієнт цільової функції grad z = c = визначає напрямок її зростання. З малюнка видно, що цільова функція z набуває максимального значення в точці перетину прямих, що задаються нерівностями (а) і (б):

4x1+5x2 = 61

Розв'язавши цю систему рівнянь, отримаємо x1*=9, x2*=5. Максимальне значення функції zmax = 64.

Приклад 2Вирішити геометричним способом ЗЛП:

x1+2x2  220 (a)

Побудуємо область допустимих розв'язків задачі.

іс.6 Приклад геометричного рішення ЗЛП.

Ця область є опуклим багатокутником ОМ1М2М3М4. Визначимо координати вершин багатокутника як точки перетину відповідних прямих. Координати вершини М1 із рішення системи

x1+2x2=220

Вирішивши цю систему, отримаємо М1 =. Координати вершини М2 =

отримаємо із системи

Координати вершини М3= отримаємо із системи

Координати вершини М4= отримаємо із системи

2x1+x2=260

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

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

z = 8x1+10x2=const=1280 містить вершини М2, М3 і, отже, все ребро (М2, М3). Отже, рішень нескінченно багато – всі точки ребра (М2, М3). У цьому максимальне значення цільової функції z дорівнює 1280.

Приклад 3Розв'язати геометричним способом ЗЛП

---