Основы симплес метода

     Шаг 8. Пересчет элементов симплекс-таблицы (переход к новому базисному решению). Порядок  пересчета различных элементов таблицы несколько отличается.

     Для элементов разрешающей строки используются следующие формулы:

     ,

     ,

     ,

       

     где  - новые значения пересчитываемых элементов,

       - старые значения пересчитываемых элементов.

     Полностью результат пересчета для нашего примера можно видеть в таблице 1.3

Таблица 1.3

     Таким образом, в новом базисном решении  базисными переменными являются: = 10, = 60, = 12 (соответствующие значения можно видеть в последнем столбце таблицы). Неосновные переменные и равны нулю. Значение целевой функции в этом случае равно 40 (значение можно видеть в правой нижней ячейке таблицы).

     Доведем решение нашего примера до конца.

     Вернемся  к шагу 4 симплекс - алгоритма. Рассмотрим последнюю строку таблицы 1.3. В ней есть положительные элементы, значит полученное решение не является оптимальным.

     Шаг 5. Выберем разрешающий столбец. Им окажется столбец, поскольку здесь содержится единственный положительный элемент нижней строки. Стало быть, переменную будем переводить в основные.

     Далее. Шаг 6. Проверка показывает, что в  разрешающем столбце есть положительные  элементы, следовательно, можно продолжать решение.

     Шаг 7. Определим разрешающую строку. При этом будем рассматривать  лишь первую и вторую строки, поскольку  для третьей строки в разрешающем  столбце находится нуль. Найдем частное  от деления элемента на элемент, находящийся в разрешающем столбце:

     Для первой строки: = 60 / 4 = 15.

     Для второй строки: = 12 / 2 = 6.

     Наименьший  результат деления - во второй строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. переводить в неосновные (исключать из базиса) будем переменную.

     Ниже  приведена симплекс-таблица с  выделенными разрешающей строкой и столбцом (таблица 1.4).

Таблица 1.4

     Далее перейдем к шагу 8 и осуществим пересчет элементов симплексной таблицы  в соответствии с правилами, приводимыми  выше. Результат пересчета представлен в таблице 1.5.

Таблица 1.5

     Таким образом, в очередном (третьем) базисном решении основными переменными  являются: x₁ = 6, x₂ = 10, x₃ = 36. Неосновные переменные x₄ и x₅ равны нулю. Значение целевой функции для этого решения равно 52.

     Вернемся  к шагу 4 симплекс - алгоритма. Рассмотрим последнюю строку таблицы 1.6. В ней все еще есть положительные элементы, значит полученное решение не является оптимальным, и необходимо продолжить выполнение симплекс - алгоритма.

     Шаг 5. Выберем разрешающий столбец. Им окажется столбец _x5, поскольку здесь содержится единственный положительный элемент нижней строки. Переменную x₅ будем переводить в основные.

     Шаг 6. Проверка показывает, что в разрешающем  столбце есть положительные элементы, следовательно, можно продолжать решение.

     Шаг 7. Определим разрешающую строку. При этом будем рассматривать  лишь первую и третью строки, поскольку  для второй строки в разрешающем  столбце находится отрицательное  число. Найдем частное от деления  элемента b_i на элемент, находящийся в разрешающем столбце:

     Для первой строки: D₁ = 60 / 4 = 15.

     Для второй строки: D₂ = 12 / 2 = 6.

     Наименьший  результат деления - во второй строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. переводить в неосновные (исключать из базиса) будем переменную x₄.

     Ниже  приведена симплекс-таблица с  выделенными разрешающей строкой и столбцом (таблица 1.6)

 

Таблица 1.6 
 

     Далее перейдем к шагу 8 и осуществим пересчет элементов симплексной таблицы  в соответствии с правилами, приводимыми  выше. Результат пересчета представлен  в таблице 1.7.

 

Таблица 1.7

     Таким образом, в очередном (четвертом) базисном решении основными переменными  являются: x₁ = 24, x₂ = 4, x₅ = 6. Неосновные переменные x₃ и x₄ равны нулю. Значение целевой функции для этого решения равно 64.

     Вернемся  к шагу 4. Рассмотрим последнюю строку таблицы 1.7. Положительных элементов в ней не осталось, следовательно полученное решение является оптимальным. Решение задачи найдено. Оно, что естественно, совпадает с решением, полученным для этой же задачи при помощи графического метода

     x₁₌24, x₂=4  
 
 
 
 
 
 
 

На  рисунке 1.1 приведена общая схема симплексного алгоритма, наглядно показывающая порядок его реализации.

                            Да

Нет

                            Да

Рисунок 1.1 
 
 
 

     

3. Метод искусственного базиса

     Для получения начального плана существует несколько алгоритмов, среди которых  часто используется М-метод и  метод искусственного базиса, характерной  особенностью которого является то, что при решении задач линейного программирования на 1 этапе можно использовать симплекс метод.

1. Алгоритм метода искусственного базиса

     Для того, чтобы воспользоваться стандартной процедурой симплекс метода на 1 этапе необходимо выполнить замену. Ввести искусственную целевую функцию F′=-F.

     Представление исходной системы неравенств ограничений  в виде системы равенств 

     Ввод  искусственных или вспомогательных  неизвестных по числу уравнений    

       В системе переменные образуют опорный план

     Формирование искусственной целевой функции, выраженной через искусственные переменные  

     Используем СМ для минимизации целевой функции, при этом возможны 2 пути:

     * minF>0 В этом случае система уравнений, исходная система ограничений не имеет неотрицательных решений, а это значит, что и исходная задача ЛП с такой системой ограничений не имеет решений

     * minF=0

     Исходная  система имеет по крайней мере 1 неотрицательное решение. В этом случае после нескольких итераций симплекс метода приходят к системе уравнений , в которой все переменные уже не базисные. Оставшаяся система будет равносильна исходной, но уже имеющей базис.  

     

2. ^{Решение задачи искусственным  базисом}

     ^{Решим симплекс-методом  задачу с искусственным  базисом (хотя бы один знак неравенств-ограничений " ≥ " или " = ").}