рух), присвоїмо всім початковим змінним x значення 0 і будемо їх вважати непростими, а всі нові будемо вважати простими. При цьому початкова дозволене рішення обчислюється однозначно:.
Алгоритм
Тепер наведемо кроки алгоритму. На кожному кроці ми будемо міняти безлічі простих і непростих векторів (рухатися по ребрах), і матриця буде мати наступний вигляд:
В
де c B - коефіцієнти вектора c відповідні простим змінним (змінним x s відповідають 0), B - стовпці, відповідні простим змінним. Матрицю, утворену залишилися стовпцями позначимо D. Чому матриця буде мати такий вигляд пояснимо в описі кроків алгоритму.
Перший крок
Вибираємо початкове допустиме значення, як зазначено вище. На першому кроці B - одинична матриця, так як простими змінними є x s . c B - нульовий вектор з тих же причин.
Другий крок
Покажемо, що у виразі тільки непрості змінні мають ненульовий коефіцієнт. Зауважимо, що з виразу Ax + x s = b прості змінні однозначно виражаються через непрості, так як число простих змінних дорівнює числу рівнянь . Нехай x '- прості, а x' '- непрості змінні на даній ітерації. Рівняння Ax + x s = b можна переписати, як Bx '+ Dx' '= b. Помножимо його на ліворуч: Таким чином ми висловили прості змінні через непрості, і у виразі, еквівалентному лівій частині рівності, всі прості змінні мають одиничні коефіцієнти. Тому, якщо додати до рівності рівність, то в отриманому рівність всі прості змінні будуть мати нульовий коефіцієнт - всі прості змінні виду x скоротяться, а прості змінні виду x s не ввійдуть у вираз.
Виберемо ребро, по якому ми будемо переміщатися. Оскільки ми хочемо максимізувати Z, то необхідно вибрати змінну, яка буде більш всіх зменшувати вираз
.
Для цього виберемо змінну, яка має найбільший по модулю негативний коефіцієнт. Якщо таких змінних немає, тобто всі коефіцієнти цього виразу невід'ємні, то ми прийшли в шукану вершину і знайшли оптимальне рішення. В іншому випадку почнемо збільшувати цю непросту змінну, тобто переміщатися по відповідному їй ребру. Цю змінну назвемо входить. p align="justify"> Третій крок
...
