|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Алгоритм симплекс-методаРассмотрим задачу линейного программирования в канонической форме (1.1.3). Определение. Допустимый план x0 задачи (1.1.3) назовем базисным, если его можно представить в виде x0 = (xБ0, xН0), причем xН0=0, т.е. из всех координат вектора x0 по крайней мере n-m равны нулю (m=rang(A)), а остальные соответствуют линейно независимым столбцам матрицы А. Базисный план задачи однозначно определяется указанием того, какие из столбцов матрицы А (или координат вектора х) назначаются базисными, поскольку небазисные координаты у такого вектора должны быть равны нулю, а значения базисных координат можно найти из уравнения АБхБ=b. Базисный план называется невырожденным, если все его базисные координаты больше нуля (в этом случае по плану можно однозначно восстановить перечень базисных координат). Выберем базис Б и приведем задачу (1.1.3) к нормальной форме с использованием этого базиса. Чтобы проверить, соответствует ли этому базису базисный план, необходимо согласно (1.1.7) проверить условия: 0 ≤ AБ-1b, (1.2.1) при выполнении которых найдется план, дающий значение целевой функции z = cБTAБ-1b (1.2.2) Мы не будем останавливаться на проблеме поиска начального базисного плана, предполагая, что в задачах небольшой размерности такой план можно найти подбором. Предположим, что у нас имеется базисный план x. Пользуясь выбранным базисом, приведем задачу к нормальной форме (в дальнейшем полагаем, что AБ – единичная матрица). Получим эквивалентную задачу в виде z = cБTb +(cНT– cБTAH)xH → max,AH xH ≤ b, (1.2.3),xH ≥ 0. Поскольку план x является базисным, то в полученной задаче он соответствует вектору xH = 0, причем оба эти вектора дают (каждый – в своей задаче) значение целевой функции равное z = cБTb. Обозначим вектор ΔT=(cНT– cБTAH). (1.2.4) В случае, когда все координаты вектора Δ неположительны, то при xH ≥ 0 выполняется условие (cНT– cБTAH)xH ≤ 0, следовательно, вектор xH = 0 дает максимально возможное значение целевой функции, равное z = cБTb. Если же у вектора Δ есть положительная координата, например, ΔTj=(cjT– cБTAj)>0, то в случае замены у вектора xH = 0 j-й координаты на положительное число t значение целевой функции увеличится на величину Δz=Δjt, причем это увеличение будет тем значительнее, чем больше будет значение t. Ограничением на выбор t служат условия (1.2.3). Кратко описанная выше процедура улучшения базисного плана составляет основу симплекс-метода решения задачи линейного программирования. Запишем этот алгоритм подробно: 1) Находим начальный базисный план (и соответствующий ему перечень базисных переменных). 2) Тождественными преобразованиями добиваемся того, чтобы матрица АБ коэффициентов перед базисными переменными была единичной. 3) Находим вектор-строку ΔT = (cНT– cБTAH). Если все его координаты отрицательны (или в случае вырожденного случая – неположительны), найденный план является решением задачи. 4) Если у вектора ΔT = (cНT– cБTAH) есть положительные координаты, выбираем координату наибольшей величины (обозначим номер соответствующей переменной через j*). 5) Проверим, можно ли с соблюдением условия AH xH ≤ b, заменить j*-ю координату вектора x на положительное число t. Поскольку остальные небазисные переменные остаются нулевыми, то AH xH = Aj* xj* = Aj* t ≤ b, или для всех i=1,…,m aij*t ≤ bi. Следовательно, нужно искать максимально возможное положительное число t, такое, что для всех i, для которых aij* > 0, выполняется t ≤ bi / aij*. Если для всех i выполняется aij* ≤ 0, то t = +∞, иначе t = min {bi / aij* | aij* > 0} = bi*/ ai*j*. 6) Если t = +∞, задача решения не имеет (целевая функция не ограничена на множестве допустимых планов). 7) Если t <+∞ и i* - номер, на котором максимум был достигнут, то после замены xj на t переменная xi* станет равной нулю (при этом говорят, что мы выводим из базиса переменную xi*, заменяя ее переменной xj*). Набор базисных переменных у нас изменился, а значение целевой функции увеличилось на Δz = Δj* t. 8) Переходим к пункту 2). Работа алгоритма заканчивается либо в пункте 3), либо в пункте 6). Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.) |