Стандартна задача лінійного програмування (стр. 3 из 8)
Скалярно-векторна форма:
(216) 
(22б) 
(23б)Матрична форма:
(21в) 
(22в) 
(23в)Векторна форма:
(21г) 
(22г) 
(23г)Лема 1. Будь-яку задачу лінійного програмування у загальній формі можна звести до першої стандартної форми.
Доведення. Покажемо, що будь-яку нерівність, введенням додаткової невідомої можна звести до рівності. Дійсно, нехай деяке обмеження має вигляд
Перепишемо його таким чином:
Введемо позначення
За побудовою
є невід'ємною величиною. Крім того останнєспіввідношення є рівняння відносно невідомих 
:
Отже ми прийшли до рівності еквівалентній вихідної нерівності.
За таким самим алгоритмом можна звести до рівності й нерівність з протилежним знаком, але завжди треба нові невідомі додавати до менших частин нерівностей, бо у протилежному випадку вони не будуть невід'ємними величинами.
Наступний крок полягає в зведені до однорідної системи обмежень на знак. Умови недодатності (3.6) легко перетворюються в умови невід'ємності за допомогою заміни відповідних змінних
.Складніше позбутися змінних, на знак яких обмежень не накладено. Цього можна досягти двома способами.
1-й спосіб. Якщо число таких змінних (3.7) менше, ніж число обмежень основної групи і вектори-стовпці коефіцієнтів при них разом з деякими іншими утворюють базисний мінор, то, розв'язавши добуту нами систему обмежень-рівностей відносно згаданих змінних, виключаємо їх як з системи умов, так і з цільової функції, залишаючи без уваги формули, що виражають їх через невід'ємні змінні, підставляючи які у залишені вирази, дістаємо й оптимальні значення змінних (3.7).
Хоч цей спосіб придатний для більшості практичних випадків, однак буває, що умови необхідні для його використання, не виконуються.
Тоді цим способом можна виключити лише частину вільних змінних, а до тих, що залишилися у задачі, застосувати 2-й спосіб.
2-й спосіб. Кожну змінну, на знак якої не накладено обмежень, подають у вигляді різниці двох невід'ємних змінних
(24)Визначивши оптимальні значення
та 
, можемо знайти за (24) і оптимальне значення відповідних 
Приклад 1. Звести до першої стандартної форми таку задачу лінійного програмування:
Розв'язання. Введенням однієї додаткової змінної
та заміною 
зводимо задачу до вигляду 
Хоч тут кількість змінних без обмеження на знак і менша від кількості основних обмежень, їх не можна вивести з задачі, оскільки вектори-стовпці їхніх коефіцієнтів пропорційні і не можуть разом входити до базисного мінору. Тому виведемо одну з них, а другу замінимо різницею двох невід'ємних змінних.
Запишемо задачу в таблицю (в нульовий рядок записане рівняння, що відповідає цільової функції:
| № рядка |  |  |  |  |  |  |
| 0 | -6 | 3 | 4 | -5 | 0 | 0 |
| 1 | 2 | -6 | -2 |  | 0 | 12 |
| 2 | 3 | 1 | -2 | 1 | 0 | 6 |
| 3 | 1 | -1 | -4 | 2 | 1 | 8 |
Вибравши
= 1 ключовим елементом, переходимо до нової таблиці. | № рядка |  |  |  |  |  |  |
| 0 | 4 | -27 | -6 | 0 | 0 | 60 |
| 1 | 2 | -6 | _2 | 1 | 0 | 12 |
| 2 | 1 | 7 | 0 | 0 | 0 | -6 |
| 3 | -3 | 11 | 0 | 0 | 1 | -16 |
Виписуючи окремо 1-й рядок (виразивши з нього,
) 
і замінивши 
, дістаємо першу стандартну форму задачі 
де
Основна задача лінійного програмування у другій стандартній формі полягає в тому, що серед всіх невід'ємних розв'язків системи основних обмежень-нерівностей треба знайти такий, при якому цільова функція буде мати оптимальне значення:
(25) 
(26) 
(27)Або у короткому запису
(25а) 
(26а)Скалярно-векторна форма:
(25б) 
(26б) 
(27б)Матрична форма:
(25в) 
(26в) 
(27в)Векторна форма:
(25г)
(26г)
(27г)Лема 2. Перша стандартна форма основної задачі лінійного програмування завжди може бути зведена до другої стандартної форми.
Доведення. Припустимо, що невідомі
є вільними; 
- базисними; ранг матриці системи обмежень (22) дорівнює 
Розв'яжемо систему рівнянь (22) відносно базисних невідомих і нехай розв'язок має вигляд
(28)Всі невідомі невід'ємні, тому
Враховуючи це, поставимо у відповідність отриманому розв'язку (28) еквівалентну систему нерівностей:
