Общая постановка задачи линейного программирования

В тетр общ

Набор значений переменных X1,X2…Xn, удовлетворяющий системе ограничений называется допустимым планом.

Совокупность допустимых планов называется множеством допустимых планов и обозначается *знак омега*.

Допустимый план, доставляющий оптиму (мин/макс) целевой функции, называется оптимальным планом и обозначается (X1*,X2*,…,Xn*)

Значение целевой функции на оптимальном плане F(x1*,x2*,…,x3n*) обозначается через f*

Решить задачу линейного программирования означает: найти оптимальный план и оптимальное значение.

Графический метод решения задач линейного программирования

Предназначен для задач размерности 2. Список ее переменных x1,x2. – т.е. координата точки на числовой плоскости.

Утверждение 1: Прямая ax1+bx2=c делит координатную плоскость Ox1,x2 на две полуплоскости, в одной из которых выполняется неравенство ax1+bx2<c, а в другой противоположное – ax1+bx2>c для построения области, заданную, например, неравенством ax1+bx2<c, необходимо построить прямую заданную уравнением. В одной из получившихся полуплоскостей выбрать произвольную точку и проверить удовлетворяют ли ее координаты требуемому неравенству.

Пример: Построить множество точку 2x1+5x2>10. В тетр 29.02-4

Утверждение 2: Уравнение ax1++bx2=c (прямая L)называется общим уравнением прямой на плоскости. Вектор n(со стрелкой) {a,b}, называется нормальным вектором прямой и обладает тем свойством, что перпендикулярен прямой L. В тетр 29.02-4. Прямая L1:ax1+bx2=C1. Прямая L1 параллельна прямой L. И получена перемещением прямой L в направление вектора n(со стрелкой), если C1>C и против вектора n(Со стрелкой), если C1<C.

Графический метод предназначен для решения задачи f(x1,x2)=C1x1+c2x2 ->max(min) при ограничениях В третр -5

Алгоритм метода состоит из 2х шагов:

1)Построение множества допустимых планов (точки, координаты кот

-Составляем уравнение граничных прямых, заменяем в ограничениях все знаки неравенства на точные равенства.

-Стрелками отмечаем полуплоскости, в которых выполняется неравенство требуемого направления

-Пересечение получившихся полуплоскостей с учетом не отрицательности координат дает множество допустимых планов.

2)Если омега не равно 0.

-Строим вектор n(со стрелкой), координаты которого – это коэффициенты при переменных в целевой функции

-Через произвольную точку множества омега проводим прямую перпендикулярно вектору n.

-При решение задачи на максимум, прямую l перемещаем в направление вектора n.

При решение задачи на минимум – против вектора, До крайнего положения, пока она имеет общие точки с множеством допустимых планов. Это положение прямой называется ее разрешающим положением, а координаты этой крайней точки дают оптимальный план.

Оптимальное значение находится подстановкой в целевую функцию оптимального плана.

Пример в тетр