Граф. Розв’язування злп
Обл. визн. ЗЛП, яка задовольн. умови (5,6) являє собою опуклу многогранну множину.
Кожна точка цієї множини назив. планом задачі, а кожна вершина – опорним планом задачі.
ЗЛП має розвиток, якщо існує x<x1, x2, x3>, що задовольняє умови (5,6) і приводить цільову ф-ю до екстремуму.
Алгоритм знаходження оптим. розв’язків ЗЛП граф. методом:
1)За обмеженнями (9,10) будуємо граничні.
2)Для кожного з обмеж. (9,10) визн. відповідну півплощину за допомогою підстановки точки з півплощинами.
Якщо нерівн. виконуеться, то шуканою буде півпл., яка містить точку. Якщо нер. не викон., то шук. буде півпл., яка точку не містить. Таким чином знаходимо многокутни розв’язків як перелік відповідних площин.
Многокутник розв’язків – область, кожна точка якої задоволн. сис-му обмеж. (9) та умову невід’ємності.
3)Будують вектор нормалі ц. ф-ї.
n=<c1,c2> та лінії рівня le які перетин. область.
Прямі le назив. лініями рівня. ф-ї F(x), що відпов. значенню С.
4)Вміщують лінії рівня паралельно собі в напрямку вектора n до тих пір, поки не досягн. області. В першій спільній точці з обл. маємо - min, в ост. спільн. т. – max.
5)Визн. корд. вершин екстра.,як корд. точок перетину відповідних прямих.
6)Обчислюємо Fmax = F(xmax), Fmin = F(xmin)
При граф. методі розв’язів ЗЛП зустр. такі випадки:
1)Цільова ф-ція має ектрем в одній точці 2)ЦФ має екер. в кожній т. відрізку. 3)ЦФ не обм. знизу(згори) в не обмеж області Д. 4)Область визн. склад. з 1 точки. 5)Обл. визн не існує.
Алгоритм 1кроку жорд. перетв.:
1)Обираємо пару величин 1, в рядку, іншу в стовпці,які будемо міняти місцями. Відповідний рядок та стовпчик назив. ведучим, а елемент, що стоїть на їх перетині – ведучим елементом.
Позначаємо ел-т кружочком(він не повинен = 0)
2)Міняємо місцями обрані величини.
3)На місце ведучого ел-та ставимо одиницю
4)Усім(іншим) ел-там ведучого рядка змін. знаки.
5)Усі інш. ел-ти вед. стовпця залиш. без змін.
6)Усі інші ел-ти табл. рахуємо за правилом прямокутника, подумки створ. прямокутн., в якому шукані та ведучі елем. стоять на кінцях діагоналі, яку назив. головною.
Нове знач. елем. = різниці пар елем., що стоять на головній та інш. діагоналі. Aij= AijAiojo- AiojAijo
Усі без вийнятнку елем. табл.. ділимо на вед. ел-т.
Властивості жорд. Пер-нь:
1)Якщо вед. елем. доданий внаслідок жор. перетв., всі інші елем. вед. рядка міняють знак.
2)Якщо вед. ел-т від’ємний внасл. перетвор., всі інш. ел-ти вед. стовпця змінюють знак.
3)Якщо у табл. виник рядок в якому все ел-ти = 0, А – вільний член не дор. 0
Правило 1. Для пошуку невід’ємних розв’язків сис-ми потрібно знайти віднош. від’ємних вільних членів, додатн. елем у їх рядках і з цих відношень обрати наймешне.
Елемент, що дає таке відн. обирають як ведучий.
Якщо у рядку з вільн. членом немає додатніх елем. і змін. знак вільного члена неможливе, то це є ознакою відсутності невід’ємних розв’язків.