Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного...
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Интересное:
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Дисциплины:
2017-06-19 | 517 |
5.00
из
|
Заказать работу |
|
|
Рассмотрим ОЗЛП, где базисные переменные разрешены относительно свободных . Например,
– вершина, при этом базисные переменные , , .
В ОЗЛП все переменные должны быть , следовательно, эта вершина недопустима. Признаком недопустимости вершины является наличие отрицательных свободных членов в ограничениях равенствах. Если отрицательный свободный член есть, то надо перейти в другую вершину, для чего одну базисную переменную сделать свободной и приравнять к нулю, а какую-то свободную превратить в базисную. Следовательно, переход из одной вершины в другую осуществляется путем замены базисной переменной на свободную. Это называется симплекс-преобразованием. Если мы будем переходить из вершины в вершину «в сторону ОДР», то за конечное число таких переходов попадем в допустимую вершину. Назовем ее опорной вершиной, а соответствующее решение опорным решением. Пусть получено опорное решение, например, для следующей задачи. Проверим, оптимально оно или нет.
,
,
,
; ; ; .
Видно, что если все коэффициенты при свободных переменных в целевой функции положительны, то никакие увеличения свободных переменных от 0 вверх не уменьшают , следовательно, это является оптимальным значением. Если же есть отрицательные коэффициенты при свободных переменных (в нашем примере при ), то ее надо сделать базисной, т.к. если она будет положительной, то будет меньше. Но может увеличиваться не бесконечно, так как в ограничениях есть отрицательный коэффициент при . Видно, что увеличивать можно только до , так в противном случае будет отрицательным, а это невозможно. Так мы нашли базисную переменную , которую надо поменять со свободной . Поиск этой пары для симплекс-преобразования и является основным элементом симплекс-метода.
|
Таким образом, симплекс-метод – это метод решения задач ЛП, который основывается на процедуре перехода от одной вершины к другой до тех пор, пока не придем в оптимальную вершину. Он состоит из трех алгоритмов:
1. Алгоритм перехода из одной вершины в другую, когда известна пара пре образования. Он пересчитывает коэффициенты системы уравнений для нового базиса. Назовем его алгоритмом симплекс-преобразования.
2. Алгоритм нахождения такой пары преобразования, чтобы при переходе в новую вершину мы приближались к ОДР. Это алгоритм отыскания опорного решения.
3. Алгоритм нахождения такой пары преобразования, чтобы новая опорная вершина давала лучшее значение целевой функции. Это алгоритм отыскания оптимального решения.
В симплекс-методе начинают со стандартной вершины (все свободные переменные равны нулю), т.е. с точки 1 (это недопустимая вершина, смотри рисунок справа). Дальше последовательно переходим из одной вершины в другую (2,3) и попадаем в опорную вершину 4.
Найдя опорное решение, мы движемся по вершинам ОДР так, чтобы целевая функция улучшалась, и при этом эти вершины были опорными (5 и 6 – оптимальная). Эти три алгоритма гарантируют либо отыскание оптимального решения, либо доказательство отсутствия допустимого решения, либо доказательство отсутствия оптимального решения.
12.1Симплекс-таблица, стандартный алгоритм симплекс-преобразования
Существует много форм симплекс-таблиц (СТ). Мы рассмотрим наиболее компактную форму, в которой строки — базисные переменные, а столбцы свободные переменные. Каждая СТ содержит коэффициенты модели задачи ЛП. Для записи СТ необходимо представить ОЗЛП в стандартной форме:
т.е. на первом месте свободный член, а коэффициенты при свободных переменных меняют знак.
Рассмотрим порядок вычислений для перехода в новую вершину. Пусть нам необходимо выполнить симплекс-преобразование . Тогда нужно получить новую симплекс-таблицу. Для этого выполним алгоритм.
|
Алгоритм 1:
1. Отыскиваем в СТ элемент и объявляем его генеральным. Тогда i-я строка и j -й столбец - генеральные.
2. Вычисляем величину, обратную генеральному элементу, и записываем ее в нижней части генеральной клетки:
3. Все элементы генеральной строки умножаем на . Результат записываем в нижней части соответствующих клеток.
4. Все элементы генерального столбца умножаем на . Результат записываем в нижней части клеток.
5. Отмечаем верхние элементы генеральной строки и нижние элементы генерального столбца.
6. В каждой клетке, не принадлежащей ни генеральному столбцу, ни генеральной строке, в нижнюю часть записываем произведение отмеченных элементов, стоящих в том же столбце и той же строке, что и данная клетка.
7. Переписываем СТ, заменяя в соответствии с табл. 2:
|
|
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!