Послідовність графічного розв"язання задачі лінійного програмування. Сумісна система лінійних нерівностей, умови невід"ємності, визначення півплощини з граничними прямими. Графічний метод для визначення оптимального плану задачі лінійного програмування.
Система сумісна, тому півплощини, як опуклі множини, перетинаючись, утворюють спільну частину, що є опуклою множиною і являє собою сукупність точок, координати кожній із який є розвязком даної системи (рис. Сукупність цих точок (розвязків) називають багатокутником розвязків Він може бути точкою, відрізком, променем, багатокутником, необмеженою багатокутною областю. Якщо система обмежень сумісна, то ці півпростори, як опуклі множини, перетинаючись, утворять у тривимірному просторі спільну частину, що називається багатогранником розвязків. Таким чином, геометрично задача лінійного програмування являє собою відшукання такої точки багатогранника розвязків, координати, якої надають лінійній функції максимальне (мінімальне) значення, причому допустимими розвязками є усі точки багатогранника розвязків. Розвязати симплекс методом: Розвязання: Графічний метод для визначення оптимального плану задачі лінійного програмування доцільно застосовувати лише для задач із двома змінними.(6) де - лінійно незалежні і за властивістю 3 розвязків задачі лінійного програмування план є кутовою точкою багатогранника розвязків, а отже може бути початковим опорним планом. Для визначення наступного плану необхідно аналогічно продовжити процес: будь-який вектор, що не входить в базис розкласти за базисними векторами, а потім визначити таке , для якого один з векторів виключається з базису. Узагальнюючи розглянутий процес, маємо - визначення нових опорних планів полягає у виборі вектора, який має ввійти в базис і вектора, що має вийти з базису. В такому випадку план містить m 1 додатних компонент, отже система векторів буде лінійно залежною і визначає не кутову точку багатогранника розвязків, а функціонал не може в ній досягати свого максимального значення. Якщо для деякого вектора виконується умова , то план не є оптимальним і можливо побудувати такий план Х, для якого виконуватиметься нерівність .
3. Жильцов О.Б., Кулян В.Р., Юнькова О.О. Математичне програмування (з елементами інформаційних технологій) / Міжрегіональна академія управління персоналом / Олена Олександрівна Юнькова (ред.). - К.: МАУП, 2006. - 184с.
