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

Задачи линейного программирования.

Симплексный метод.

Контрольные вопросы и задания.

1.Какую задачу линейного программирования (ЛП) называют общей, стандартной, канонической (основной)?

2.Как перейти от одной формы записи задачи ЛП к другой?

3.Какие задачи линейного программирования можно решать симплексным методом?

4.Каков признак оптимальности в симплексном методе?

5.Как строится опорный план?

6.Как определяется разрешающая строка и разрешающий столбец?

7.Как осуществляется перерасчет элементов симплексной таблицы?

Рекомендуемая литература.

1. Красс М.С., Чупрынов Б.П.. Основы математики и ее приложения в экономическом образовании. – М.: Дело, 2001. Стр.347-348, 367-374.

2. Исследование операций в экономике: Учебн. пособие для ВУЗов/Под ред. Проф. Кремера Н.Ш. – М.: Банки и биржи, ЮНИТИ, 1997. Стр.16-26, 64-98.

3. Шелобаев С.И. Математические методы и модели в экономике, финансах, бизнесе: Учеб.пособие для вузов. – М.: ЮНИТИ – ДАНА, 2000. Стр.44.

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

Идея симплексного метода (метода последовательного улучшения плана) заключается в том, что, начиная с некоторого исходного опорного решения, осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному. Значение целевой функции при этом перемещении для задач на максимум не убывает. Поскольку число опорных решений конечно, через конечное количество шагов получим оптимальное опорное решение.

Для удобства вычислений симплексным методом составляют симплексные таблицы. В строке сверху (с_j) указывают коэффициенты всех переменных целевой функции, в строке снизу – оценки ∆j.

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

1. Математическая модель задачи должна быть канонической. Если она неканоническая, то ее нужно привести к каноническому виду.

2. Заполняем симплексную таблицу. Все строки таблицы 1-го шага, за исключением строки ∆_j (индексная (оценочная) строка), заполняем по данным системы ограничений и целевой функции. Находим исходное опорное решение.

3. Проверяем найденное опорное решение на оптимальность. Оценочная строка находится по формуле

для переменных и для свободного члена.

При решении задачи на максимум возможны следующие случаи

· , тогда найденное решение оптимально;

· Хотя бы одна оценка , но при ней нет ни одного положительного коэффициента, тогда целевая функция не ограничена и решение задачи прекращаем;

· Хотя бы одна оценка , и при ней есть хотя бы один положительный коэффициент, тогда можно перейти к новому оптимальному плану, которому соответствует большее значение функции;

· Если отрицательных оценок несколько, то в базис выбираем ту переменную, которой соответствует наибольшая по абсолютной величине отрицательная оценка

Пусть одна оценка ∆_k < 0 или наибольшая по абсолютной величине ∆_k < О, тогда k-ю графу принимаем за разрешающую.

За разрешающую строку принимаем ту, которой соответствует минимальное отношение свободных членов (b_i) к положительным коэффициентам k-й графы. Элемент, находящийся в разрешающей строке и разрешающем столбце, называют разрешающим элементом.

4. Заполняем симплексную таблицу 2-го шага:

• переписываем разрешающую строку, разделив ее на разрешающий элемент;

• заполняем базисные графы;

• остальные коэффициенты таблицы находим по правилу “прямоугольника” или по упрощенной схеме. Получаем новое опорное решение.

5. Возвращаемся к первому шагу алгоритма.

Задача. Решить задачу линейного программирования