Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Фазы решенияПосле того, как было модифицировано условие, создаётся вспомогательная целевая функция. Если вспомогательные переменные были обозначены, как yi, i∈{1., k}, то вспомогательную функцию определим, как
.
После этого проводится обыкновенный симплекс-метод относительно вспомогательной целевой функции. Поскольку все вспомогательные переменные увеличивают значение, в ходе алгоритма они будут поочерёдно выводится из базиса, при этом после каждого перехода новое решение будет всё ближе к множеству допустимых решений. Когда будет найдено оптимальное значение вспомогательной целевой функции, могут возникнуть две ситуации: оптимальное значение больше нуля. Это значит, что как минимум одна из вспомогательных переменных осталась в базисе. В таком случае можно сделать вывод, что допустимых решений данной задачи линейного программирования не существует. - оптимальное значение равно нулю. Это означает, что все вспомогательные переменные были выведены из базиса, и текущее решение является допустимым. Во втором случае мы имеем допустимый базис, или, иначе говоря, исходное допустимое решение. Можно проводить дальнейшую оптимизацию с учётом исходной целевой функции, при этом уже не обращая внимания на вспомогательные переменные. Это и является второй фазой решения.
3. МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД
В модифицированном методе матрица
не пересчитывается, хранится и пересчитывается только матрица. В остальном алгоритм похож на вышеописанный. . Вычисляем двойственные переменные . Проверка оптимальности. преобразуется в. Проверка заключается в вычислении для всех столбцов. Столбец со значением < 0 можно вводить в базис. Часто выбирают минимальное значение, но для этого нужно перебрать все столбцы. Чаще выбирают значение, меньшее некоторого заданного значения Если такого столбца не обнаружится, за принимается максимальное найденное абсолютное значение и соответствующий столбец вводится в базис. . Определение выводимого. Пусть - вводимый столбец, соответствующий переменной Базиный план - это решение системы Увеличиваем. Умножим слева на, т.е. Здесь - базисный план, - разложение вводимого столбца по базису. Находим максимальное значение, при котором все значения не отрицательны. Если может быть взято как угодно велико, решение не ограничено. В противном случае один из элементов выйдет на нулевое значение. Выводим соответствующий столбец из базиса. . Пересчет опорного(базисного) плана. Вычисляем новый опорный план по уже приведенной формуле с найденным значением. . Пересчитываем обратную к базисной. Пусть - выводимый столбец. Матрица B представима в виде где - базисная матрица без выводимого столбца. После замены столбца базисная матрица будет иметь вид Нам нужно найти матрицу, такую что
=> => => Откуда
Замечание. При пересчете матрицы накапливаются ошибки округления. Во избежание получения больших ошибок время от времени матрица пересчитывается полностью. Этот процесс называется «повторением». Мультипликативный вариант симплекс-метода В мультипликативном варианте матрица не хранится, хранятся лишь множители При решении экономических задач часто матрица ограничений разреженная, в таком случае мультипликативный вариант получает дополнительные преимущества - можно хранить мультипликаторы в сжатом виде (не хранить нули).
Во избежание накопления ошибок округления может использоваться LU-разложение матрицы. При подавляющем числе ограничений типа «неравенство» может быть использован метод переменного базиса. Метод основан на том, что базисная матрица может быть представлена в виде
Обратная к ней имеет вид
При относительно небольших размерах матрицы остальная часть матрицы может не храниться. Таким подходом удается решить задачи с десятками миллионов строк ограничений (например, из теории игр).
|