Алгоритм симплекс-метода

I. После введения добавочных переменных, система уравнений записывается в виде, который называется расширенной системой (11). Предполагается, что все добавочные переменные имеют тот же знак, что и свободные члены.

II Исходную расширенную систему заносим в первую симплекс таблицу. Последняя строка, в которой приведено уравнение для линейной функции цели, называется оценочной. В ней указываются коэффициенты функции цели с противоположным знаком. В левом столбце таблицы записываем базисные переменные (на первом шаге за базисные переменные берутся дополнительные переменные), в первой строке - все переменные, во втором столбце - свободные члены расширенной системы Алгоритм симплекс-метода - №1 - открытая онлайн библиотека . Последний столбец подготовлен для оценочных отношений, необходимый при расчете. В рабочую часть таблицы, начиная с третьего столбца и второй строки, занесены коэффициенты, при переменных ау расширенной системы. Далее таблица преобразуется по определенным правилам.

III. Проверяем выполнение критерия оптимальности (при решении задачи на максимум критерий оптимальности состоит в отсутствии отрицательных коэффициентов в оценочной строке). Если критерий оптимальности выполнен, то следовательно, максимум достигнут и оптимальное значение Алгоритм симплекс-метода - №2 - открытая онлайн библиотека равно Алгоритм симплекс-метода - №3 - открытая онлайн библиотека (в левом нижнем углу таблицы). Базисные переменные принимают значения Алгоритм симплекс-метода - №4 - открытая онлайн библиотека остальные переменные равны Алгоритм симплекс-метода - №5 - открытая онлайн библиотека . Если критерий оптимальности не выполнен, переходим к следующему шагу.

IV. По оценочной строке выбираем переменную, вводимую в базис. Находим наибольший по модулю отрицательный коэффициент в оценочной строке. Соответствующая этомустолбцу переменная Алгоритм симплекс-метода - №6 - открытая онлайн библиотека будет вводимой в базис, а сам столбец называется разрешающим.

V. Находим переменную, выводимую из базиса. Для этого составляем оценочные отношения (они заносятся в столбец для оценочных отношений) по следующим правилам:

1) Алгоритм симплекс-метода - №7 - открытая онлайн библиотека , если Алгоритм симплекс-метода - №4 - открытая онлайн библиотека и Алгоритм симплекс-метода - №9 - открытая онлайн библиотека имеют разные знаки;

2) Алгоритм симплекс-метода - №7 - открытая онлайн библиотека , если Алгоритм симплекс-метода - №11 - открытая онлайн библиотека и Алгоритм симплекс-метода - №12 - открытая онлайн библиотека ;

3) Алгоритм симплекс-метода - №7 - открытая онлайн библиотека ли Алгоритм симплекс-метода - №14 - открытая онлайн библиотека ;

4) 0, если Алгоритм симплекс-метода - №11 - открытая онлайн библиотека и Алгоритм симплекс-метода - №16 - открытая онлайн библиотека ;

5) Алгоритм симплекс-метода - №17 - открытая онлайн библиотека , если Алгоритм симплекс-метода - №4 - открытая онлайн библиотека и Алгоритм симплекс-метода - №9 - открытая онлайн библиотека имеют одинаковые знаки.

Определяем Алгоритм симплекс-метода - №20 - открытая онлайн библиотека . Если конечного минимума нет, то задача не имеет конечного оптимума Алгоритм симплекс-метода - №21 - открытая онлайн библиотека Если минимум конечен, то выбираем строку q, на которой он достигается (если их несколько, то любую), и называем ее разрешающей строкой. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент Алгоритм симплекс-метода - №22 - открытая онлайн библиотека .

VI. Переходим к следующей таблице по правилам (преобразования Гаусса-Жордана):

1) В левом столбце записываем новый базис: вместо основной переменной Алгоритм симплекс-метода - №23 - открытая онлайн библиотека - переменную Алгоритм симплекс-метода - №6 - открытая онлайн библиотека ,

2) В столбцах, соответствующих базисным переменным, проставляем нули и единицы: 1 - на пересечении строки и столбца, соответствующих одной и той же базисной переменной; 0 - во всех других позициях столбцов базисных переменных.

3) Новую строку Алгоритм симплекс-метода - №25 - открытая онлайн библиотека получаем из старой делением на разрешающий элемент Алгоритм симплекс-метода - №22 - открытая онлайн библиотека .

4) Все остальные элементы Алгоритм симплекс-метода - №27 - открытая онлайн библиотека вычисляем по правилу прямоугольника:

Алгоритм симплекс-метода - №28 - открытая онлайн библиотека (12)

Далее переходим к шагу III.

Пример.Решить задачу:

Алгоритм симплекс-метода - №29 - открытая онлайн библиотека

Приведем систему ограничений к каноническому виду. Получим расширенную систему:

Алгоритм симплекс-метода - №30 - открытая онлайн библиотека

Целевую функцию представим в виде Алгоритм симплекс-метода - №31 - открытая онлайн библиотека

Базисными переменными будут являться дополнительные переменные Алгоритм симплекс-метода - №32 - открытая онлайн библиотека .

Заполняем первую симплекс-таблицу:

Базис Свободный Переменные Оценочные
  член             отношения
    Алгоритм симплекс-метода - №33 - открытая онлайн библиотека Алгоритм симплекс-метода - №34 - открытая онлайн библиотека Алгоритм симплекс-метода - №35 - открытая онлайн библиотека Алгоритм симплекс-метода - №36 - открытая онлайн библиотека Алгоритм симплекс-метода - №37 - открытая онлайн библиотека Алгоритм симплекс-метода - №38 - открытая онлайн библиотека
Алгоритм симплекс-метода - №35 - открытая онлайн библиотека 18/3
Алгоритм симплекс-метода - №36 - открытая онлайн библиотека
Алгоритм симплекс-метода - №37 - открытая онлайн библиотека
Алгоритм симплекс-метода - №38 - открытая онлайн библиотека Алгоритм симплекс-метода - №7 - открытая онлайн библиотека
Алгоритм симплекс-метода - №2 - открытая онлайн библиотека -2 -3  

Проверяем критерий оптимальности задачи. В последней оценочной строке имеются отрицательные коэффициенты. Выбираем из них наибольший по модулю - (-3). Следовательно, Алгоритм симплекс-метода - №45 - открытая онлайн библиотека . Переменная Алгоритм симплекс-метода - №34 - открытая онлайн библиотека является выводимой из базиса а соответствующий ей столбец - разрешающим.

Находим оценочные отношения и выбираем из них минимальное (5). Следовательно, Алгоритм симплекс-метода - №47 - открытая онлайн библиотека , переменная Алгоритм симплекс-метода - №37 - открытая онлайн библиотека является вводимой в базис, а соответствующая ей строка - разрешающей.

Переходим к новой симплекс-таблице:

а) в новом базисе основные переменные Алгоритм симплекс-метода - №49 - открытая онлайн библиотека ;

б) расставляем 0 и 1; например, на пересечении столбца и строки, соответствующих переменной Алгоритм симплекс-метода - №35 - открытая онлайн библиотека ставим 1, а остальные элементы столбца Алгоритм симплекс-метода - №35 - открытая онлайн библиотека равны 0 и т.д. Третья строка получается делением на разрешающий элемент Алгоритм симплекс-метода - №52 - открытая онлайн библиотека . Остальные клетки таблицы заполняем по формулам (12). Например:

Алгоритм симплекс-метода - №53 - открытая онлайн библиотека Алгоритм симплекс-метода - №54 - открытая онлайн библиотека

Получаем вторую симплекс-таблицу:

Базис Свободный Переменные Оценочные
  член             отношения
    Алгоритм симплекс-метода - №33 - открытая онлайн библиотека Алгоритм симплекс-метода - №34 - открытая онлайн библиотека Алгоритм симплекс-метода - №35 - открытая онлайн библиотека Алгоритм симплекс-метода - №36 - открытая онлайн библиотека Алгоритм симплекс-метода - №37 - открытая онлайн библиотека Алгоритм симплекс-метода - №38 - открытая онлайн библиотека
Алгоритм симплекс-метода - №35 - открытая онлайн библиотека -3
Алгоритм симплекс-метода - №36 - открытая онлайн библиотека -1 11/2
Алгоритм симплекс-метода - №34 - открытая онлайн библиотека Алгоритм симплекс-метода - №7 - открытая онлайн библиотека
Алгоритм симплекс-метода - №38 - открытая онлайн библиотека
Алгоритм симплекс-метода - №2 - открытая онлайн библиотека -2  

Критерий оптимальности вновь не выполнен. Теперь разрешающий первый столбец и Алгоритм симплекс-метода - №33 - открытая онлайн библиотека - вводимая переменная. Считаем оценочные отношения и находим разрешающую строку - первая и выводимую из базиса переменную - Алгоритм симплекс-метода - №35 - открытая онлайн библиотека .Разрешающий элемент Алгоритм симплекс-метода - №69 - открытая онлайн библиотека .

Переходим к новой симплекс-таблице:

Базис Свободный Переменные Оценочные
  член             отношения
    Алгоритм симплекс-метода - №33 - открытая онлайн библиотека Алгоритм симплекс-метода - №34 - открытая онлайн библиотека Алгоритм симплекс-метода - №35 - открытая онлайн библиотека Алгоритм симплекс-метода - №36 - открытая онлайн библиотека Алгоритм симплекс-метода - №37 - открытая онлайн библиотека Алгоритм симплекс-метода - №38 - открытая онлайн библиотека
Алгоритм симплекс-метода - №33 - открытая онлайн библиотека -3
Алгоритм симплекс-метода - №36 - открытая онлайн библиотека -2 5/5
Алгоритм симплекс-метода - №34 - открытая онлайн библиотека 5/1
Алгоритм симплекс-метода - №38 - открытая онлайн библиотека -3 12/9
Алгоритм симплекс-метода - №2 - открытая онлайн библиотека -3  

и на этот раз критерий оптимальности не выполнен.

Выводимая переменная Алгоритм симплекс-метода - №36 - открытая онлайн библиотека ; вводимая переменная- Алгоритм симплекс-метода - №37 - открытая онлайн библиотека . Переходим к новой таблице.

Базис Свободный Переменные Оценочные
  член             отношения
    Алгоритм симплекс-метода - №33 - открытая онлайн библиотека Алгоритм симплекс-метода - №34 - открытая онлайн библиотека Алгоритм симплекс-метода - №35 - открытая онлайн библиотека Алгоритм симплекс-метода - №36 - открытая онлайн библиотека Алгоритм симплекс-метода - №37 - открытая онлайн библиотека Алгоритм симплекс-метода - №38 - открытая онлайн библиотека
Алгоритм симплекс-метода - №33 - открытая онлайн библиотека -1/5 3/5  
Алгоритм симплекс-метода - №37 - открытая онлайн библиотека -2/5 1/5  
Алгоритм симплекс-метода - №34 - открытая онлайн библиотека 2/5 -1/5
Алгоритм симплекс-метода - №38 - открытая онлайн библиотека 3/5 -9/5  
Алгоритм симплекс-метода - №2 - открытая онлайн библиотека 4/5 3/5  

Критерий оптимальности выполнен. Следовательно, Алгоритм симплекс-метода - №94 - открытая онлайн библиотека Оптимальное решение Алгоритм симплекс-метода - №95 - открытая онлайн библиотека