Введення
Мета роботи
Реалізувати графічний метод розв'язання задач лінійного програмування.
1. Теоретичні відомості
Найбільш простим і наочним методом лінійного програмування (ЛП) є графічний метод. Він застосовується для вирішення завдань ЛЗ з двома змінними. br/>
Розглянемо задачу ЛП у стандартній формі запису:
В
Покладемо n = 2 , тобто розглянемо це завдання на площині. Нехай система нерівностей совместна (має хоча б одне рішення). p> Кожне нерівність цієї системи геометрично визначає полуплоскость з граничній прямій a i1 x 1 + a i2 x 2 = b i , i = 1,2, ... m . Умови невід'ємності визначають півплощини, відповідно, з граничними прямими x1 = 0, x2 = 0. Система сумісна, тому півплощини, як опуклі множини, перетинаючись, утворюють спільну частину, яка є опуклим множиною і являє собою сукупність точок, координати кожної з яких є вирішенням даної системи. Сукупність цих точок називають багатокутником рішень. Він може бути точкою, відрізком, променем, багатокутником, необмеженою багатокутної областю. p> Таким чином, геометрично задача лінійного програмування (ЗЛП) являє собою відшукання такої точки багатокутника рішень, координати якої доставляють лінійної функції мети максимальне (мінімальне) значення, причому допустимими рішеннями є всі крапки багатокутника рішень.
Лінійне рівняння описує безліч точок, що лежать на одній прямій. Лінійна нерівність описує деяку область на площині. Визначимо, яку частину площині описує нерівність 2х 1 +3 х 2 ВЈ 12. По-перше, побудуємо пряму 2х 1 +3 х 2 = 12 . Ця пряма проходить через точки (6, 0) і (0, 4). Для того щоб визначити, яка напівплощина задовольняє нерівності необхідно вибрати будь-яку точку на графіку, що не належить прямій, і підставити її координати в нерівність. Якщо нерівність буде виконуватися, то дана точка є допустимим рішенням і напівплощина, що містить точку, задовольняє нерівності. Зручною для використання при підстановці в нерівність є початок координат. Підставимо х1 = х2 = 0 в нерівність 2х 1 +3 х 2 ВЈ < i> 12 . Отримаємо 2'0 +3'0 ВЈ 12. Дане твердження є вірним, отже, нерівності 2х1 +3 х2 ВЈ 12 відповідає нижня напівплощина, що містить точку (0.0). Це відображено на графіку, зображеному на. 1. br/>
Рис. 1. Нерівності 2х1 +3 х2 ВЈ 12 відповідає нижня напівплощина. p> Аналогічно можна зобразити графічно кожне обмеження завдання лінійного програмування.
Рішенням кожного нерівності системи обмежень ЗЛП є напівплощина, що містить граничну пряму і розташована по одну сторону ві...
