Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
В. 7 Алгоритм прямого симплексного метода
|
|
Прямой симп. метод предназначен для решения задачи ЛП вида 
.
Симплексный метод можно применять, только если выполняются 3 условия:
1) задача ЛП имеет канонический вид;
2) правая часть ограничений (вектор свободных членов) неотрицателен (b≥0)
3) матрица А содержит единичную подматрицу (имеется начальное допустимое базисное решение).
Тогда можно построить начальную симплексную таблицу:
| с1 | c2 | сn | ||||
| Базис | БДР | x1 | x2 | … | xn | |
| cB | xB | b | A | |||
| z | ∆0 | ∆1 | ∆ 2 | … | ∆n |
Элементы 
, называемые оценками, вычисляются по формуле 
. Оценка 
равна текущему значению целевой функции.
Элементы вектора cB содержат коэффициенты целевой функции, соответствующие базисным переменным. Столбец «Базис» содержит названия текущих базисных переменных (в правильном порядке). Столбец «БДР» показывает текущее значение базисных переменных, при которых достигается текущее значение целевой функции. В конце работы алгоритма в этом столбце будет содержаться ответ.
Алгоритм прямого симплексного метода.
Шаг 0. Построить начальную симп.таблицу. В столбце «Базис» записать базисные переменные в правильном порядке. Вычислить оценки. Перейти на шаг 1.
Шаг 1. Проверить оценки 
. Если все оценки 
, то найдено оптимальное решение. Перейти на шаг 5.
Среди положительных оценок найти максимальную и столбец, соответствующий выбранной оценке, объявить ведущим (s). Перейти на шаг 2.
Шаг 2. Просмотреть элементы s-го столбца, если все они , то целевая функция неограниченна (нет оптимального решения), перейти на шаг 5. Иначе перейти на шаг 3.
Шаг 3. Для положительных элементов s-го столбца найти строчку r, в которой симп. отношение br/ars принимает минимальное значение. Объявить строку r ведущей. Перейти на шаг 4.
Шаг 4. На пересечении ведущего столбца и ведущей строки обозначить ведущий элемент. Нарисовать новую симплексную таблицу. На месте элемента xr в столбце «базис» поставить элемент xs и с помощью преобразования Жордана-Гаусса пересчитать всю таблицу (в том числе оценки и столбец БДР). Перейти на шаг 1.
Шаг 5. Конец алгоритма.
Пример в распечатке!
Date: 2015-12-12; view: 449; Нарушение авторских прав