Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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




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

Полная симплекс-таблица имеет следующую структуру.

Здесь Cj – коэффициенты линейной формы L, Csi – коэффициенты в L при базисных переменных (подмножество Cj), Asi – базисные векторы, si – индекс базисного компонента на позиции i. Жирной линией выделена главная часть таблицы. 1 и послед. строки и 2 столбец таблицы – вспомогат., обязательны только в начальной таблице. Алгоритм состоит из предварительного и основного этапов.

На предварительном этапе сначала определяется начальное базисное решение. Исходя из него заполняется начальная симплекс-таблица. В третий столбец заносятся m базисных векторов, а во второй – соответствующие коэффициенты из L в порядке следования условий в модели (на первую позицию ставится вектор при базисной переменной из первого условия и т.д.). Так как начальный базис единичный, элементы главной части таблицы кроме последней строки берутся прямо из модели (в столбец A0 заносятся правые части условий, в Aj – коэффициеты при ). Значения zj находятся как скалярное произведение векторов Cb=[Csi] и Aj. Вычитая из нижней строки верхнюю, получаем L и оценки Δj.

Основной этап является итерационным.Очередная итерация заканчивается заполнением симплекс-таблицы за исключением столбца q. Пусть завершилась l-я итерация. Цикл начинается с анализа оценок Δj в таблице l. Если нет отрицательных оценок, значит, выполнился признак оптимальности. Возможны два вывода:

1) если не вводились искусственные переменные или они равны нулю, получено оптимальное решение;

2) если хотя бы одна искусственная переменная не равна нулю, задача неразрешима из-за противоречивости условий.

При невыполнении признака оптимальности анализируются столбцы с отрицательными оценками. Если среди них обнаружится столбец, в котором все коэффициенты разложения неположительные, то есть aij£0, "i, то задача неразрешима по причине неограниченности критерия на допустимом множестве. В противном случае выбирается минимальная (отрицательная) оценка

Она определяет столбец Ar - направляющий. Заполняется столбец q. Значения q вычисляются делением элементов столбца A0 на положительные элементы направляющего столбца По минимальному значению q определяется направляющая строка k: На пересечении направляющейстроки и направляющего столбца находится направляющий элементakr. Тем самым определена переменная которая становится базисной, и переменная выводимая из числа базисных (она становится равной нулю). Заполняется таблица l+1. В ней отражается смена базиса: вектор Ask заменяется вектором Ar, соответственно вместо Csk ставится Cr, остальные базисные элементы остаются на месте. Элементы главной части таблицы вычисляются согласно:

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

Для контроля вычислений можно проводить повторный счет оценок, используя вспомогательные строки z и C.

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

 







Дата добавления: 2015-04-19; просмотров: 339. Нарушение авторских прав


Рекомендуемые страницы:


Studopedia.info - Студопедия - 2014-2021 год . (0.002 сек.) русская версия | украинская версия