Решение задач линейного программирования симплекс методом

 

·ограничения типа «=»  дополняются одной вспомогательной  переменной.

 

Соответственно, будет создано  некоторое количество дополнительных и вспомогательных переменных. В  исходный базис выбираются дополнительные переменные с коэффициентом «+1»  и все вспомогательные. Осторожно: решение, которому соответствует этот базис, не является допустимым.

 

Различия между дополнительными  и вспомогательными переменными

 

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

 

·дополнительные переменные сообщают, насколько соответствующее  им ограничение «недоиспользовано». Значение дополнительной переменной, равное нулю, соответствует равенству  значений правых и левых частей ограничения.

 

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

 

То есть ненулевое значение дополнительной переменной может (но не должно) сигнализировать о неоптимальности решения. Ненулевое значение вспомогательной переменной сигнализирует о недопустимости решения.

 

Фазы решения

 

После того, как было модифицировано условие, создаётся вспомогательная  целевая функция. Если вспомогательные  переменные были обозначены, как yi, i?{1., k}, то вспомогательную функцию определим, как

 

 

.

 

 

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

 

Когда будет найдено оптимальное  значение вспомогательной целевой  функции, могут возникнуть две ситуации:

 

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

 

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

 

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

 

 

 

4. Модифицированный симплекс-метод

 

 

В модифицированном методе матрица

 

 

 

 

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

 

. Вычисляем двойственные  переменные 

 

. Проверка оптимальности. преобразуется в.

 

Проверка заключается  в вычислении для всех столбцов. Столбец со значением < 0 можно вводить в базис.

 

Часто выбирают минимальное  значение, но для этого нужно перебрать  все столбцы.

 

Чаще выбирают значение, меньшее  некоторого заданного значения

 

Если такого столбца не обнаружится, за принимается максимальное найденное абсолютное значение и  соответствующий столбец вводится в базис.

 

. Определение выводимого.

 

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

 

Умножим слева на, т.е.

 

Здесь  - базисный план,  - разложение вводимого столбца по базису.

 

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

 

. Пересчет опорного(базисного)  плана.

 

Вычисляем новый опорный  план по уже приведенной формуле  с найденным значением.

 

. Пересчитываем обратную  к базисной.

 

Пусть  - выводимый столбец.

 

Матрица B представима в  виде

 

где  - базисная матрица без выводимого столбца.

 

После замены столбца базисная матрица будет иметь вид 

 

Нам нужно найти матрицу, такую что

 

 

=> => =>

 

 

Откуда 

 

 

Замечание.

 

При пересчете матрицы  накапливаются ошибки округления. Во избежание получения больших  ошибок время от времени матрица  пересчитывается полностью. Этот процесс  называется «повторением».

 

Мультипликативный вариант  симплекс-метода

 

 

В мультипликативном варианте матрица не хранится, хранятся лишь множители 

 

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

 

5. Другие варианты симплекс-метода

 

 

Во избежание накопления ошибок округления может использоваться LU-разложение матрицы.

 

При подавляющем числе  ограничений типа «неравенство»  может быть использован метод  переменного базиса.

 

Метод основан на том, что  базисная матрица может быть представлена в виде

 

 

 

 

Обратная к ней имеет  вид

 

 

 

 

При относительно небольших  размерах матрицы остальная часть  матрицы может не храниться.

 

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

 

Двойственный симплекс-метод

 

Для реализации двойственного  метода необходимо перейти от задачи на минимум к задаче на максимум (или наоборот) путем транспонирования матрицы коэффициентов. При переходе от задачи на минимум целевая функция  примет вид:

 

 

 

 

при ограничениях

 

 

.

 

 

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

 

Если линейная функция  одной из задач не ограничена, то другая не имеет решения.

 

 

Узнать стоимость работы без плагиата

Благотворительность

 

 Загружая свои работы, Вы помогаете не только студентам,  но и людям, которым Ваша  помощь действительно нужна. Чем  именно это помогает? Читать дальше…..

 

 

 

 

 © 2003 - 2009 «Библиофонд»

Обратная связь

Пользовательское соглашение «Библиофонд» — Электронная библиотека: статей, учебной и художественной литературы. Рефераты и курсовые, отчеты по практике и контрольные. Дипломные работы и другие творческие, аналитические работы. Наш проект для тех кому интересно, для тех кто учится и для тех кто действительно нуждается!