Курсовая работа: Стандартна задача лінійного програмування

(26б)

(27б)

Матрична форма:

(25в)

(26в)

(27в)

Векторна форма:

(25г)

(26г)

(27г)

Лема 2. Перша стандартна форма основної задачі лінійного програмування завжди може бути зведена до другої стандартної форми.

Доведення. Припустимо, що невідомі є вільними;

- базисними; ранг матриці системи обмежень (22) дорівнює

Розв'яжемо систему рівнянь (22) відносно базисних невідомих і нехай розв'язок має вигляд

(28)

Всі невідомі невід'ємні, тому

Враховуючи це, поставимо у відповідність отриманому розв'язку (28) еквівалентну систему нерівностей:

Введемо позначенняі помноживши всі нерівності на -1 отримуємо систему обмежень:

Очевидно, що остання система обмежень збігається з (26) і рівносильна системі обмежень (3-9) У тому розумінні, що будь-якому розв'язку системи нерівностей відповідає певний розв'язок системи рівнянь (22) Для завершення доведення леми підставимо у цільову функцію (21) замість базисних невідомих їхні вирази (28). Якщо згрупувати подібні члени, то цільова функція набуде вигляду (25). Приклад 2. Звести до другої стандартної форми задачу

Розв'язання. Виписуємо матрицю системи обмежень

і шукаємо ранг матриці. Базисним буде мінор

Отже, ранг . Базисні невідомі: ; вільні невідомі: