![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
I. Общая задача ЛП
z – целевая функция c = (c 1, …, cn) – вектор целей A = (aij) m x n – матрица задачи (матрица условий) b = (b 1, …, bm) – вектор ограничений (вектор правых условий) x = (x 1, …, xn) – план задачи (решение задачи) Условие xj ≥ 0 – условие неотрицательности переменных
Множество x, удовлетворяющих всем ограничениям называется множеством допустимых решений, обозначается X. План, на котором достигается оптимум целевой функции (минимум/максимум) называется решением задачи (оптимальный план), обозначается x *. X * – множество решений задачи. Решить общую задачу ЛП означает, найти хотя бы один оптимальный план и вычислить оптимальное значение. Частные задачи ЛП
Все виды задач ЛП эквивалентны: существуют однозначные правила перехода от одного вида задачи к другому и решая последнюю задачу и вспоминая правила перехода, мы можем написать решение исходной задачи, не решая ее.
1)
2)
3) xn + i – дополнительные переменные, (насколько недоиспользовано ограничение)
4)
5) Пусть ai 1 ≠ 0 6) Пусть 7) Пусть xj – свободная ~
11.
m = 3
1) Строим границы множества решений, которые соответствуют неравенствам (прямые: 2) Находим полуплоскости, соответствующие каждому ограничению (метод пробной точки) 3) Находим многоугольник допустимых решений, как пересечение найденных полуплоскостей. Полученную область заштриховать. Возможные варианты: a. X – многоугольник b. X – пустое множество c. X – неограниченное многоугольное множество 4) Находим координаты вектора градиента целевой функции (вектор целей – вектор нормали к линиям уровня) 5) Строим прямую (перпендикулярно вектору цели), которая соответствует линии уровня для z 0 = 0. Затем перемещаем прямую в направлении вектора цели (в случае задачи на min – в противоположном направлении) до тех пор, пока прямая имеет общие точки с множеством допустимых решений. Крайнее положение – ответ. 6) Вычисляем координаты крайней точки, как пересечение соответствующих прямых и вычисляем значение целевой функции в этой точке. Ответ:
|