Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
В. 23 Алгоритм двойного симплексного метода
|
|
Двойственный симплексный метод предназначен для решения задачи линейной оптимизации вида: сх → min, Ах ≥ b, x ≥ 0
Пусть выполнены следующие условия:
1. задача ЛП имеет стандартный вид на минимум;
2. вектор коэффициентов целевой функции (с) неотрицателен;
3. ограничения должны быть типа «≥»;
4. ограничения на переменные должны быть типа «≥», (xj≥0)
Тогда можно построить начальную симплексную таблицу:
| с1 | c2 | сn | ||||||||
| Базис | БДР | x1 | x2 | … | xn | y1 | y2 | … | ym | |
| Θ | y | -b | -A | E | ||||||
| z | ∆0 | ∆1 | ∆ 2 | … | ∆n | ∆n+1 | ∆n+2 | ∆n+m |
Оценки Δj для переменных xj будут, очевидно, равны - сj. Значение целевой функции Δ0=0.
Алгоритм двойственного симплексного метода:
Шаг 0. Построить начальную симплексную таблицу. Перейти на шаг 1.
Шаг 1. Проверить значения базисных переменных в столбце «БДР». Если все значения неотрицательны, то найдено оптимальное решение перейти на шаг 7. Если хотя бы одно значение отрицательно, перейти на шаг 2.
Шаг 2. Среди отрицательных значений переменных столбца «БДР» выбрать максимальное по модулю значение (если их несколько, выбрать любое из них) и соответствующую строку объявить ведущей (r). Перейти на шаг 3.
Шаг 3. Проверить коэффициенты матрицы ограничения (аrj, j=1,...,n) ведущей строки. Если все arj ≥0, то задача не имеет решения, перейти на шаг 7. Иначе перейти на шаг 4.
Шаг 4. Для отрицательных элементов ведущей строки рассчитать отношение соответствующих элементов строки оценок к элементам ведущей строки. Среди полученных отношений выбрать минимальное (если их несколько - любое). Столбец, соответствующий минимальному отношению, объявить ведущим столбцом (s). Перейти на шаг 5.
Шаг 5. Элемент ars, стоящий на пересечении ведущей строки и ведущего столбца объявить ведущим элементом. Перейти на шаг 6.
Шаг 6. Нарисовать новую симплексную таблицу. В столбце "Базис" вместо переменной хг записать переменную xs. Применяя преобразование Жордана-Гаусса относительно ars, рассчитать значения элементов новой симплексной таблицы. Перейти на шаг 1.
Шаг 7. Конец алгоритма.
Пример в распечатке!
В. 24 Определение выпуклого множества.
Опр1. Множество Х называется выпуклым, если вместе с двумя любыми точками ему принадлежит весь отрезок, соединяющий эти точки.
Опр2. Множество Х называется выпуклым, если для любых x’и x” из Х, и для любых α1,α2 Î R (множество всех действительных чисел) таких, что α1+α2=1, α1, α2 ≥0, точка α1х’+ α2х”Î X. Выпуклое множество:
1) α1=1, α2=0
Невыпуклое множество:
Окружность - не выпуклое множество, круг – выпуклое.
2) α1= α2=1/2; 1/2x’+1/2x”=x
α1=1, α2=0
Мы можем воспринимать значение α 1, α2 как силу притяжения к полюсам x’ и x”.
Date: 2015-12-12; view: 495; Нарушение авторских прав