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

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

Учет двусторонних ограничений






В общем случае на переменные могут накладываться двусторонние ограничения aj£ xj£bj. Каждое такое ограничение порождает 2 равенства в канонической модели и, следовательно, увеличивает размер симплекс-таблицы на 2 строки. Если сместить начало отсчета на aj, ограничение примет вид 0 £ xj£ dj, где dj = bj - aj, и таблица будет увеличиваться только на 1 строку. Однако, если такие ограничения накладываются на многие переменные, увеличение размеров симплекс-таблицы будет значительным.

Идея метода с двусторонними ограничениями состоит в учете ограничения сверху аналогично условию xj³ 0. Выполнение этого условия обеспечивается выбором направляющей строки, т.е. значения вводимой переменной, равного q0. Чтобы переменные в новом базисном решении помимо неотрицательности были не больше dj, усложним выбор значения вводимой переменной. Предельное значение q по условию неотрицательности обозначим , а предельное значение по ограничению сверху ­– . Верхнего значения могут достигать только переменные с отрицательными коэффициентами air. Приравнивая эти переменные значениям dj, получаем формулу для вычисления : q0 =min()

Соответственно и направляющая строка выбирается по q0. В симплекс-таблице вместо одного столбца для q удобнее иметь два: для q и q ’’. Кроме того, добавляется одна строка (сверху), в которой записываются значения небазисных переменных: выводимая из базисного решения переменная xk равна нулю, если < , и равна dk в противном случае.

Изменяется также признак оптимальности базисного решения. Условие Δ j ³0 остается в силе только для нулевых небазисных переменных. К нему добавляется условие для небазисных переменных на верхнем уровне: Δ j £0. Поэтому в случае неоптимальности текущего решения направляющий столбец выбирается по max|Δ j | из отрицательных для xk=0 и положительных для xk = dk. Симплекс-преобразование (пересчет таблицы) не изменяется.

Модифицированный алгоритм

Этот алгоритм отличается тем, что основан на обратной матрице базиса. Для простоты рассмотрим случай с односторонними ограничениями на переменные. Тогда небазисные переменные равны нулю, а система условий задачи принимает вид AbXb=B,

где Ab базисная матрица m x m, Xb – вектор базисных переменных. Тк определитель базисной матрицы не равен нулю, существует обратная матрица . Базисные переменные можно вычислять по формуле

Относительные оценки также можно определять по обратной матрице. Для этого выполним ряд преобразований: Вектор найдем из разложения вектора условий Aj по базису Получаем:

Произведение не зависит от индекса j, поэтому окончательно будем иметь , где

Таким образом, для решения задачи модифицированным симплекс-методом достаточно вести не всю таблицу, а только обратную матрицу. При единичном начальном базисе обратную матрицу вычислять не надо – она также единичная. Имея обратную матрицу текущего решения, вычисляем сначала вектор , а затем оценки небазисных переменных. Если признак оптимальности не выполняется, находим минимальную оценку Коэффициенты разложения air вектора Аr по текущему базису находятся по формуле: где Ar – вектор условий вводимой переменной xr, который берется из канонической модели. Столбец ar добавляем к обратной матрице в качестве направляющего. Далее действуем, как в стандартном методе, то есть для положительных air вычисляем q, находим направляющую строку и направляющий элемент. Затем получаем новую обратную матрицу путем симплекс-преобразования текущей обратной матрицы. После выполнения признака оптимальности находим решение.

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

Новую обратную матрицу можно находить не только симплекс преобразованием старой, но и по формуле

,

где E k – почти единичная матрица (только k -й столбец отличается от единичного). Если эту формулу применять на всех итерациях, то для l -й обратной матрицы получим

.

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








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



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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Логические цифровые микросхемы Более сложные элементы цифровой схемотехники (триггеры, мультиплексоры, декодеры и т.д.) не имеют...

Неисправности автосцепки, с которыми запрещается постановка вагонов в поезд. Причины саморасцепов ЗАПРЕЩАЕТСЯ: постановка в поезда и следование в них вагонов, у которых автосцепное устройство имеет хотя бы одну из следующих неисправностей: - трещину в корпусе автосцепки, излом деталей механизма...

Понятие метода в психологии. Классификация методов психологии и их характеристика Метод – это путь, способ познания, посредством которого познается предмет науки (С...

ЛЕКАРСТВЕННЫЕ ФОРМЫ ДЛЯ ИНЪЕКЦИЙ К лекарственным формам для инъекций относятся водные, спиртовые и масляные растворы, суспензии, эмульсии, ново­галеновые препараты, жидкие органопрепараты и жидкие экс­тракты, а также порошки и таблетки для имплантации...

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

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

Тактические действия нарядов полиции по предупреждению и пресечению групповых нарушений общественного порядка и массовых беспорядков В целях предупреждения разрастания групповых нарушений общественного порядка (далееГНОП) в массовые беспорядки подразделения (наряды) полиции осуществляют следующие мероприятия...

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