 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Симплекс-метод
Алгоритм метода рассмотрим для линейной задачи, в которой требуется найти экстремум целевой функции
Z = z 1 x 1 +z 2 x 2 ® extr,
при ограничениях-равенствах
a 11 x 1 +a 12 x 2 + х 3 = b 1;
a 21 x 1 +a 22 x 2 + х 4 = b2;
a 31 x 1 +a 32 x 2 + х 5 = b 3
и граничных условиях неотрицательности переменных
х i > 0, i = 1, 2,...5.
| х 1 | х 2 | х 3 | х 4 | х 5 | b; Z |
| a 11 | a 12 | b 1 | |||
| a 21 | a 22 | b 2 | |||
| a 31 | a 32 | b 3 | |||
| z 1 | z 2 | -Z |
Исходное решение:
свободные переменные x 1 = 0; x 2 = 0;
базисные переменные х 3 = b 1; х 4 = b 2; х 5 = b 3;
целевая функция –Z=0.
Примечание. Значение целевой функции входит в табличную запись с противоположным знаком.
Это универсальный метод решения линейных оптимизационных задач;
Метод основан на таком переборе решений, что на каждом шаге решение улучшается;
Метод состоит из двух этапов: на первом этапе ищется допустимое решение; на втором – оптимальное решение.
1. В табличной записи просматривается столбец свободных членов bj. Если все bj >0, выполня-ется переход к п.4. Если есть bj <0, то соответ-ствующая строка будет разрешающей.
2. Просматриваются коэффициенты aij разрешаю-щей строки. Выбирается отрицательный коэф-фициент и соответствующий столбец будет разрешающим.
3. Выполняется пересчет всех коэффициентов таблицы, включая значение целевой функции и ее коэффициенты zi. Переход к п.1
4. Просматриваются коэффициенты z i. Если все z i³0 (при поиске минимума Z) или все z i £ 0 (при поиске максимума Z), то текущее решение будет оптимальным, вычисления заканчиваются.
5. Если есть z i<0 (при поиске минимума Z) или z i>0 (при поиске максимума Z), то соответ-ствующий столбец будет разрешающим.
6. Вычисляются отношения свободных членов b j к положительным коэффициентам a ji разрешающе-го столбца. Строка, отвечающая минимальному из этих отношений будет разрешающей.
7. Выполняется пересчет всех коэффициентов таблицы. Переход к п. 4.
Тесты
Поиск по сайту: