ні у вигляді нерівностей з двома змінними, вона може бути вирішена графічно. Графічний метод розв'язання ЗЛП складається з наступних етапів. p> Етап 1. p> Спочатку на координатної площині
x 1 Ox 2 будується допустима багатокутна область (Область допустимих рішень, область визначення), відповідна обмеженням:
1.6)
Не наводячи строгих доказів, вкажемо ті випадки, які тут можуть вийде. p> 1. Основний випадок - получающаяся область має вигляд обмеженого опуклого багатокутника (рис. 1а). p> 2. Неосновний випадок пЂ виходить необмежений опуклий багатокутник, що має вигляд, подібний зображеному на рис. 1б. Подібна ситуація, наприклад, вийде, якщо в розглянутому вище прикладі прибрати обмеження х 1 + х 2 ≤ 3. Решта буде необмеженим опуклим багатокутником. br/>
Рис. 1
б)
а)
br/>
Нарешті, можливий випадок, коли нерівності (1.6) суперечать один одному , і допустима область взагалі порожня .
Розглянемо теорію на конкретному прикладі:
Знайти допустиму область задачі лінійного програмування, яка визначається обмеженнями
1.32)
В
Рішення:
1. Розглянемо пряму-x 1 + x 2 = 1. При x 1 = 0, x 2 = 0, а при x 2 = 0, x 1 = - 1. Таким чином, ця пряма проходить через точки (0,1) і (-1,0). Беручи x 1 = x 2 = 0, отримаємо, що -0 +0 <1 і тому цікавить нас напівплощина лежить нижче прямої, зображеної на рис. 4.а. p> 2. Розглянемо пряму. При, а при. Таким чином, ця пряма проходить через точки (0, -1/2) і (1,0). так як (4.б). p> 3. Нарешті, розглянемо пряму. Вона проходить через точки (0,3) і (3,0) і так як 0 +0 <3, то цікавить нас напівплощина лежить нижче прямий, зображеної на рис. 4.в. p> Зводячи всі разом і додаючи умови х 1 ≥ 0, х 2 ≥ 0 отримаємо малюнок 5, де виділена область, в якій виконуються одночасно всі обмеження (1.32). Звернемо увагу на те, що вийшла, область має вигляд опуклого багатокутника .
В
Етап 2. p> Повернемося тепер до вихідної задачі лінійного програмування. У ній, крім системи нерівностей, є ще цільова функція з 1 х 1 + з 2 х 2 => ma...
