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

 

1.Математическую модель задачи привести к каноническому (стандартному) виду.

 

2. Построить начальную симплекс-таблицу исходя из стандартного вида.

 

3. Найти разрешающий столбец. В строке коэффициентов ЦФ найти значение с самим маленьким отрицательным числом. Этот столбец и будет разрешающим.

 

4. Вычислить разрешающую строку и ведущий элемент (Почленно разделить столбец свободных членов на элементы разрешающего столбца, за исключением строки ЦФ. Выбрать наименьшее из частных. Эта строка будет разрешающей.Ведущий элемент будет на пересечении разрешающего столбца и разрешающей строки.).

 

5.Построить новую симплекс-таблицу-второй шаг.

 

При построении новой таблицы убрать из базиса строку с переменной разрешающей строки в предыдущей таблице. Ввести в базис строку с названием разрешающего столбца предыдущей таблицы.

 

 

-Построение ведущей строки в новой таблице. Почленно поделить всю разрешающую строку на разрешающий элемент.

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

 

6. Проверяем таблицу второго шага на оптимальность. Если в строке целевой функции нет отрицательных элементов, тогда таблица имеет оптимальный план, записать ответ. Если в строке ЦФ есть отрицательный элемент (элементы), тогда переходят к следующему (третьему) шагу, строят новую симплекс-таблицу в соответствии п.5 и затем проверяют ее на оптимальность. Построение таблиц заканчивается с нахождением оптимального плана.

 

Прямая задача на минимум решается следующим образом:

-Написать математическую модель двойственной задачи в стандартном виде

-Решить двойственную модель симплекс - методом

-Записать ответ.

 

 

Связь между задачами двойственной пары в том, что, решая симплексным методом одну из них, автоматически получаем решение другой.

Для этого достаточно воспользоваться соответствием переменных прямой и двойственной задач в последней симплекс-таблице.

 

Х1 x2 xn S1 S2 Sm
S1 S2 Sm y1 y2 ym