x <0, тобто цільова функція зменшується при переході до нового базису. p> Оскільки в задачі лінійного программрованія може бути лише кінцеве число базисів, а на кожній ітерації відбувається зменшення цільової функції, базиси не можуть повторюватися. Отже, після кінцевого числа ітерацій вектор модифікованих вартостей стане невід'ємним, а це означає, що подальше зменшення цільової функції неможливо, тобто буде отримано одне з оптимальних рішень. p> У силу опуклості завдання будь-яке інше оптимальне рішення матиме також значення цільової функції, тобто буде в цьому сенсі еквівалентно. h4>
Геометричний метод
В
Розглянемо задачу лінійного програмування в стандартній формі з двома змінними (n = 2). До такої форми може бути зведена і канонічна задача (з обмеженнями у вигляді рівнянь), коли число змінних n більше числа рівнянь m на 2, тобто n - m = 2. p> Нехай геометричним зображенням системи обмежень є багатокутник ABCDE (рис. 1). Необхідно серед точок цього багатокутника знайти таку точку, в якій лінійна функція F = c 1 x 1 + c 2 x 2 приймає максимальне (або мінімальне) значення. p> Розглянемо так звану лінію рівня лінійної функції F, тобто лінію уздовж якої ця функція приймає одне і теж значення a, тобто F = a, або
c 1 x 1 + c 2 x 2 = а (1)
лінії рівня широко використовуються, наприклад, на картах прогнозу погоди, де звивисті лінії - так звані ізотерми є ніщо інше, як лінії рівня температури Т = с. Ще більш простим прикладом ліній рівня є паралелі на географічній карті. Це лінії рівня широти. p> Припустимо треба знайти саму північну точку небудь області, наприклад країни або материка. Це буде точка, яка має найбільшу широту, тобто точка через яку проходить паралель (лінія рівня) з найбільшою широтою (Рівнем). p> Саме так і треба поступати при геометричному вирішенні завдань лінійного програмування. на многоугольнике рішень слід знайти точку, через яку проходить лінія рівня функції F з найбільшим (якщо лінійна функція максимізується) або найменшим (якщо вона мінімізується) рівнем. p> Рівняння лінії функції (1) є рівняння прямої лінії. При різних рівнях а
Лінії рівня паралельні, так як їх кутові коефіцієнти визначаються тільки співвідношенням між коефіцієнтами c 1 і c 2 і отже, рівні. Таким чином, лінії рівня функції F - це своєрідні "паралелі", розташовані зазвичай під кутом до осей координат. p> Важлива властивість лінії рівня лінійної функції полягає в тому, що при паралельному зміщенні лінії в одну сторону рівень тільки зростає, а при зміщенні лінії в іншу сторону - тільки убуває. p> Нехай є три лінії рівня:
F = c 1 x 1 + c 2 x 2 = а 1 (I)
F = c 1 x 1 + c 2 x 2 = а 2 (II)
...
