Алгоритм симплекс-метода
I. После введения добавочных переменных, система уравнений записывается в виде, который называется расширенной системой (11). Предполагается, что все добавочные переменные имеют тот же знак, что и свободные члены.
II Исходную расширенную систему заносим в первую симплекс таблицу. Последняя строка, в которой приведено уравнение для линейной функции цели, называется оценочной. В ней указываются коэффициенты функции цели с противоположным знаком. В левом столбце таблицы записываем базисные переменные (на первом шаге за базисные переменные берутся дополнительные переменные), в первой строке - все переменные, во втором столбце - свободные члены расширенной системы . Последний столбец подготовлен для оценочных отношений, необходимый при расчете. В рабочую часть таблицы, начиная с третьего столбца и второй строки, занесены коэффициенты, при переменных ау расширенной системы. Далее таблица преобразуется по определенным правилам.
III. Проверяем выполнение критерия оптимальности (при решении задачи на максимум критерий оптимальности состоит в отсутствии отрицательных коэффициентов в оценочной строке). Если критерий оптимальности выполнен, то следовательно, максимум достигнут и оптимальное значение равно (в левом нижнем углу таблицы). Базисные переменные принимают значения остальные переменные равны . Если критерий оптимальности не выполнен, переходим к следующему шагу.
IV. По оценочной строке выбираем переменную, вводимую в базис. Находим наибольший по модулю отрицательный коэффициент в оценочной строке. Соответствующая этомустолбцу переменная будет вводимой в базис, а сам столбец называется разрешающим.
V. Находим переменную, выводимую из базиса. Для этого составляем оценочные отношения (они заносятся в столбец для оценочных отношений) по следующим правилам:
1) , если и имеют разные знаки;
2) , если и ;
3) ли ;
4) 0, если и ;
5) , если и имеют одинаковые знаки.
Определяем . Если конечного минимума нет, то задача не имеет конечного оптимума Если минимум конечен, то выбираем строку q, на которой он достигается (если их несколько, то любую), и называем ее разрешающей строкой. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент .
VI. Переходим к следующей таблице по правилам (преобразования Гаусса-Жордана):
1) В левом столбце записываем новый базис: вместо основной переменной - переменную ,
2) В столбцах, соответствующих базисным переменным, проставляем нули и единицы: 1 - на пересечении строки и столбца, соответствующих одной и той же базисной переменной; 0 - во всех других позициях столбцов базисных переменных.
3) Новую строку получаем из старой делением на разрешающий элемент .
4) Все остальные элементы вычисляем по правилу прямоугольника:
(12)
Далее переходим к шагу III.
Пример.Решить задачу:
Приведем систему ограничений к каноническому виду. Получим расширенную систему:
Целевую функцию представим в виде
Базисными переменными будут являться дополнительные переменные .
Заполняем первую симплекс-таблицу:
Базис | Свободный | Переменные | Оценочные | |||||
член | отношения | |||||||
18/3 | ||||||||
-2 | -3 |
Проверяем критерий оптимальности задачи. В последней оценочной строке имеются отрицательные коэффициенты. Выбираем из них наибольший по модулю - (-3). Следовательно, . Переменная является выводимой из базиса а соответствующий ей столбец - разрешающим.
Находим оценочные отношения и выбираем из них минимальное (5). Следовательно, , переменная является вводимой в базис, а соответствующая ей строка - разрешающей.
Переходим к новой симплекс-таблице:
а) в новом базисе основные переменные ;
б) расставляем 0 и 1; например, на пересечении столбца и строки, соответствующих переменной ставим 1, а остальные элементы столбца равны 0 и т.д. Третья строка получается делением на разрешающий элемент . Остальные клетки таблицы заполняем по формулам (12). Например:
Получаем вторую симплекс-таблицу:
Базис | Свободный | Переменные | Оценочные | |||||
член | отношения | |||||||
-3 | ||||||||
-1 | 11/2 | |||||||
-2 |
Критерий оптимальности вновь не выполнен. Теперь разрешающий первый столбец и - вводимая переменная. Считаем оценочные отношения и находим разрешающую строку - первая и выводимую из базиса переменную - .Разрешающий элемент .
Переходим к новой симплекс-таблице:
Базис | Свободный | Переменные | Оценочные | |||||
член | отношения | |||||||
-3 | ||||||||
-2 | 5/5 | |||||||
5/1 | ||||||||
-3 | 12/9 | |||||||
-3 |
и на этот раз критерий оптимальности не выполнен.
Выводимая переменная ; вводимая переменная- . Переходим к новой таблице.
Базис | Свободный | Переменные | Оценочные | |||||
член | отношения | |||||||
-1/5 | 3/5 | |||||||
-2/5 | 1/5 | |||||||
2/5 | -1/5 | |||||||
3/5 | -9/5 | |||||||
4/5 | 3/5 |
Критерий оптимальности выполнен. Следовательно, Оптимальное решение
Дата добавления: 2015-11-28; просмотров: 1445;