Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
В. 28. Алгоритм графического метода решения задачи ЛП с двумя переменными
|
|
Шаг 1. По ограничениям задачи построить область допустимых значений (ОДЗ). Каждому неравенству на плоскости соответствует полуплоскость, каждому уравнению соответствует прямая, ОДЗ будет пересечением построенных полуплоскостей и прямых. Возможны несколько вариантов ОДЗ (замкнутая область, неограниченная область, луч, отрезок, точка, пустое множество). Если ОДЗ - пустое множество, то задача не имеет решения. Если ОДЗ не пусто, то перейти на шаг 2.
Шаг 2. Построить вектор градиента, координаты начала вектора - (x1=0, x2=0,), координаты конца вектора - (x1=с1, x2=с2), где с1 и с2 - коэффициенты целевой функции. Перейти на шаг 3.
Шаг 3. Построить линию уровня целевой функции. Линия уровня целевой функции перпендикулярна вектору градиента и должна проходить по ОДЗ задачи. Перейти на шаг 4.
Шаг 4. Определить точки-кандидаты из ОДЗ для оптимального решения. Если целевая функция на максимум, то линию уровня целевой функции перемещать параллельно самой себе в направлении градиента до последней точки ОДЗ. Если целевая функция на минимум, то линию уровня перемещаем в направлении антиградиента (противоположное градиенту направление). Перейти на шаг 5.
Шаг 5. (Точное определение координат оптимального решения). Если очевидно, что точка-кандидат является оптимальным решением, то подставляем ее значение в целевую функцию и записываем решение задачи ЛП в виде: оптимальное значение целевой функции, и соответствующие значения х1 и х2. Если точек-кандидатов несколько, то для каждой такой точки составляется система двух уравнений с двумя неизвестными, линии которых в пересечении дают данные точки. Для каждой точки решается система уравнений. Полученные решения подставляются в целевую функцию. В качестве оптимальной выбирается та точка, для которой значение целевой функции лучше. Завершить алгоритм.
Замечание - возможны несколько вариантов решений: оптимальное решение единственно, оптимальных решений множество, целевая функция неограниченна.
Замечание - часто ОДЗ имеет достаточно простой вид и сразу известны координаты угловых точек. В этом случае, если угловых точек не слишком много, можно найти ответ, перебирая все эти точки, не рисуя линию уровня.
Пример в распечатке!
Date: 2015-12-12; view: 515; Нарушение авторских прав