Граф. розв’язування ЗЛП

Обл. визн. ЗЛП, яка задовольн. умови (5,6) являє собою опуклу многогранну множину.

Кожна точка цієї множини назив. планом задачі, а кожна вершина – опорним планом задачі.

ЗЛП має розвиток, якщо існує x <x₁, x₂, x₃>, що задовольняє умови (5,6) і приводить цільову ф-ю до екстремуму.

Алгоритм знаходження оптим. розв’язків ЗЛП граф. методом:

1) За обмеженнями (9,10) будуємо граничні.

2) Для кожного з обмеж. (9,10) визн. відповідну півплощину за допомогою підстановки точки з півплощинами.

Якщо нерівн. виконуеться, то шуканою буде півпл., яка містить точку. Якщо нер. не викон., то шук. буде півпл., яка точку не містить. Таким чином знаходимо многокутни розв’язків як перелік відповідних площин.

Многокутник розв’язків – область, кожна точка якої задоволн. сис-му обмеж. (9) та умову невід’ємності.

3) Будують вектор нормалі ц. ф-ї.

n =<c₁,c₂> та лінії рівня l_e які перетин. область.

Прямі l_e назив. лініями рівня. ф-ї F(x), що відпов. значенню С.

4)Вміщують лінії рівня паралельно собі в напрямку вектора n до тих пір, поки не досягн. області. В першій спільній точці з обл. маємо - min, в ост. спільн. т. – max.

5)Визн. корд. вершин екстра.,як корд. точок перетину відповідних прямих.

6)Обчислюємо F_max = F(x_max), F_min = F(x_min)

При граф. методі розв’язів ЗЛП зустр. такі випадки:

1)Цільова ф-ція має ектрем в одній точці 2)ЦФ має екер. в кожній т. відрізку. 3)ЦФ не обм. знизу(згори) в не обмеж області Д. 4)Область визн. склад. з 1 точки. 5)Обл. визн не існує.

 

 

Алгоритм 1кроку жорд. перетв.:

1)Обираємо пару величин 1, в рядку, іншу в стовпці,які будемо міняти місцями. Відповідний рядок та стовпчик назив. ведучим, а елемент, що стоїть на їх перетині – ведучим елементом.

Позначаємо ел-т кружочком(він не повинен = 0)

2)Міняємо місцями обрані величини.

3)На місце ведучого ел-та ставимо одиницю

4)Усім(іншим) ел-там ведучого рядка змін. знаки.

5)Усі інш. ел-ти вед. стовпця залиш. без змін.

6)Усі інші ел-ти табл. рахуємо за правилом прямокутника, подумки створ. прямокутн., в якому шукані та ведучі елем. стоять на кінцях діагоналі, яку назив. головною.

Нове знач. елем. = різниці пар елем., що стоять на головній та інш. діагоналі. A_ij= A_ijA_iojo- A_iojA_ijo

Усі без вийнятнку елем. табл.. ділимо на вед. ел-т.

Властивості жорд. пер-нь:

1)Якщо вед. елем. доданий внаслідок жор. перетв., всі інші елем. вед. рядка міняють знак.

2)Якщо вед. ел-т від’ємний внасл. перетвор., всі інш. ел-ти вед. стовпця змінюють знак.

3)Якщо у табл. виник рядок в якому все ел-ти = 0, А – вільний член не дор. 0

Правило 1. Для пошуку невід’ємних розв’язків сис-ми потрібно знайти віднош. від’ємних вільних членів, додатн. елем у їх рядках і з цих відношень обрати наймешне.

Елемент, що дає таке відн. обирають як ведучий.

Якщо у рядку з вільн. членом немає додатніх елем. і змін. знак вільного члена неможливе, то це є ознакою відсутності невід’ємних розв’язків.

 

Симплекс метод (алгоритм):

1) Зводимо задачу до станд. вигляду, при чому F(x) -> min і
“>=”, “=”.

2) Склад. симплекс таблицю. Якщо серед обмеж є рівняння, необх. спочатку замінити 0 в базисі на вільну змінну.

3)Знаходимо допустимий розв’язок. Послідовно застов. Правило 1, до того моменту, покі всі члену будуть невід’ємні. Досягаємо невід’ємності вільних членів або відсутн. допустимої області.

Допустимий розв’язок –розв’язок, який задовольняє сист. обмеж та умову невід’ємн.

Базисний допуст. розв’язок – розв’язок допустимий, з вільними змінними рівними 0.

4)Знаход. оптим розв’язок (за Правилом 2)

Елементи ост. рядка назив. оцінками, x₁, x₂ – вільні змінні – це змінні, через яккі вираж. інш змінні сис-ми. Базисні змінні – це ті змінні, які вираж. з сист. через вільні змінні.

Для того, щоб знайти оптим. план ЗЛП вільні змінні повинні = 0, щоб потрапити у верш. многогранника. Ознакою оптим. плану. є невід’ємність оцінок.

Правило 2. Для прямув. до оптим. плану беремо віднош. додатніх вільних членів до від’ємн. ел-тів у їх рядках, які належ стовпчикам з від’ємн. оцінками. З усіх таких відн. обираємо найбільше і ел-т, що дає таке віднош. беремо за ведучий.

Зауваження 1. Якщо в процесі пошуку допуст. плану виявл., що у рядку, де є від’ємн. вільний член немає додатн. ел-ів, то задача допустим. плану не має. Економ. зміст: для викон. обсягу робіь не вистачає ресурсів.

Зауваження 2. Якщо в процесі пошуку оптим. плану виявл., що у стовпчику з від’ємн. оцінкою немає дод. елем, то задача не має оптим. плану. ЦФ не обмежена.