Мал.7.1. Геометричний метод рішення задачі лінійного

Програмування

Відповідь: виробів моделі А – 300 од.

виробів моделі В – 200 од.

максимальний прибуток

 

Симплексний метод рішення.

Нехай потрібно мінімізувати цільову функцію при обмеженнях (7.4). Приведемо (7.4) до стандартного виду (7.2). Для цього до лівої частини кожного обмеження, що має вид нерівності ≤, добавляємо позитивну змінну: . Якщо обмеження у виді нерівності ≥, те з лівої частини віднімаємо . Система прийме вид:

Усього перемінних . Усі повинні бути позитивні, якщо , те дане рівняння потрібно помножити на (-1). Оскільки цільова функція не має стаціонарних точок, те своїх максимального і мінімального значень вона досягає на границі області.

Th. Нехай область припустимих рішень - обмежений замкнутий багатогранник, тоді мінімальне (максимальне) значення функції мети досягається в кутовій точці.

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

Виз. Рішення називається базисним, якщо вільні перемінні рівні нулю.

Кожне базисне рішення відповідає кутовій точці. Кількість базисних рішень:

Таким чином, щоб знайти оптимальне рішення, потрібно обчислити значення функції мети у всіх кутових точках і вибрати точку, у якій значення функції мети мінімально (максимально); якщо велике, то кількість кутових точок є велике число.

Виз. Симплексний метод - упорядкований перехід від одного базисного рішення до іншого, при якому відбувається зменшення значення функції мети. (Використовується для відшукання мінімального значення функції мети)

Розглянемо побудову нульового базисного рішення. Припустимо, що система обмежень (7.3) містить одиничних векторів (така ситуація виникає, якщо всі обмеження визначаються нерівностями ≤; інакше перші перемінних вибираються в якості базисних і щодо них зважується система лінійних рівнянь). Тоді система обмежень має вид:

Базисні перемінні: ; інші - вільні. Нехай вільні змінні рівні нулю, тоді отримуємо нульове базисне рішення:

.

Далі виникає необхідність перевірити, чи не є знайдене базисне рішення оптимальним. Помітимо, що вектори системи обмежень мають вид:

; ;…; ; ;…; .

Вектори ,…, – одиничні й утворять базис у – мірному просторі, тобто кожної з векторів можна розкласти по даному базисі:

Оскільки базис одиничний, те . Кожному розкладанню відповідає єдине значення :

Th: (критерій оптимальності) Якщо для деякого базисного рішення розкладання усіх векторів задовольняють умові , то план оптимальний, інакше потрібно вибрати новий базис і шукати нове базисне рішення.