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

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

Читайте также:
  1. I.2.4. Алгоритм симплекс-метода.
  2. II. 4.1. Алгоритм метода ветвей и границ
  3. LU – алгоритм нахождения собственных значений для несимметричных задач
  4. QR- алгоритм нахождения собственных значений
  5. SALVATOR - это переход физического явления в семантико-нейронный алгоритм (инструкцию) освобождения человека от негативных последствий этого явления.
  6. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  7. Алгоритм
  8. Алгоритм
  9. Алгоритм
  10. Алгоритм
  11. Алгоритм
  12. Алгоритм 1.2. Выделение групп предприятий с помощью заливки контрастным цветом

Рассмотрим задачу линейного программирования в канонической форме (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).


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.)