Добрый день.
Возникла такая задача:
<c, x> -> max;
Ax <= b,
где A - матрица (m,n), b - (m,1), x - (n,1), c - (n,1), <c,x> - скалярное произведение с и x.
Пробую решить с помощью ф-ии Лагранжа.
Для этого перехожу к эквивалентной задаче, но уже на минимум:
- <c, x> -> min;
Ax - b <= 0.
Составляю ф-ю Лагранжа:
L = - a0 * <c,x> + <a1, Ax - b>.
(a0 - число, a1 - вектор (m,1))
Для нахождения решения исходной задачи необходимо найти x, доставляющий минимум ф-ии Лагранжа и такой что,
a0 > 0, a1 >= 0,
L'_a0 = 0; // производная по a0.
L'_a1 = 0;
L'_x = 0;
Ну еще возможно нормировка коэффицентов a0, a1.
Из первого уравнения получается <c,x> = 0.
Из второго Ax - b = 0.
А вот что получится в третьем не получается понять.
И что потом с этим делать?
; 
