Решение задачи математического программирования.

[SergeyZakroishikov]

Здравствуйте! Передо мной встала следующая задача: имеется некоторая организация, структурно разделенная на 3 отдела с заданным количеством работников в каждом ($n_i(t_0), \sum_1^3 n_i(t)=N=\operatorname{const}$) и структурой $s_i(t_0)=\frac{n_i(t_0)}{N}$. Известна марковская матрица вероятностей переходов работников между отделами - матрица $P$ . Имеется набор ограничений: $0 < p_{ij} < 1$, $\sum_{i=1}^3 p_{ij}$ для любого $j$ и имеется линейная система $X\cdot a=b$, где $a,b$ - векторы $3\times 1$.
Требуется перейти к новой структуре отделов $g_i=\operatorname{const}$, используя матрицу вероятностей переходов как функцию управления (обозначим $X$). Критерием качества является норма разницы матриц $P$ и $X$, т.е. необходимо решить $\left||P-X\right|| \to \min$.
Автор задачи утверждает, что использование нормы $\left||A\right||=\sum_{i,j=1}^n\left|a_{ij}\right|$ позволяет свести задачу к задаче линейного программирования.

Вот в этом и заключается вопрос: как эта норма позволяет перейти к линейному программированию? Воспользовавшись этой нормой, можем получить следующее:
$\sum_{i,j=1}^{i,j=3}\left|p_{ij} - x_{ij}\right| \to \min$, что не решается линейным программированием.

Для применения метода неопределенных коэффициентов Лагранжа надо "разобраться" с модулями, опять же не совсем понимаю, как.

Подскажите пожалуйста, в каком направлении двигаться? Может быть я не знаю о подходящих в данном случае методах? Или возможно "свести" систему к линейной?

[mserg]

Если нужно минимизировать модуль выражения z, то заводите вспомогательные неотрицательные переменные a и b. Далее, добавляете ограничение
$z=a-b$
И минимизируете вместо модуля z выражение $a+b$

[SergeyZakroishikov]

Не понимаю сути новых переменных. Если взять один элемент из суммы - $\left|p_{ij}-x_{ij}\right|$, то:

$a=p_{ij}, b=x_{ij}$ - неотрицательные величины - вероятности, $p_{ij}$ известна, а ограничение $z=a-b$ представляет собой саму функцию.

В таком случае вместо $\left| z \right|=\left|p_{ij}-x_{ij}\right|$ минимизируем $p_{ij}+x_{ij}$?

[mserg]

Особо не вникал в задачу, но если ни $p_{ij}$ (это константы?), ни $x_{ij}$ не связаны более никакими ограничениями, то будет так, как Вы написали.

В противном случае это не так – для каждого минимизируемого слагаемого нужно вводить вспомогательные переменные. Видимо, существует требование равенства сумм вероятностей единице (подозреваю, что есть описка в исходном сообщение, пропущено =1 после суммы вероятностей).

[SergeyZakroishikov]

Да, описался, сумма вероятностей в каждой строке равна единице как следствие того, что P - марковская. Так же ошибся я там и с индексом: сумма по строке, т.е. по $j$ для любого $i$
Ограничения представляют собой:
$0<p_{ij}<1,$
$\sum_{j=1}^3 p_{ij} = 1 \ \ \ \forall i,$
$Xa=b$

Но минимизация модуля разницы - поиск наиболее близкого по значению числа, а минимизация суммы - поиск просто наименьшего $x_{ij}$, т.е. минимум суммы не гарантирует минимума модуля разницы. Я видимо чего-то не понимаю...

[mserg]

Положим, что
$p_{ij}-x_{ij}=r_{ij}-s_{ij}$
где $ r_{ij}, s_{ij}$ – вспомогательные переменные

Вместо минимизации
$| r_{ij}-s_{ij}|$
можно нагло минимизировать
$r_{ij}+s_{ij}$

Это возможно потому, что в оптимальном решении либо $r_{ij}=0$, либо $ s_{ij}=0$. Почему так, подумайте самостоятельно.

[SergeyZakroishikov]

Думаю потому, что если $r_{ij} = k$, $s_{ij} = l$ в оптимальном решении, то мы можем сделать очередную замену $r'_{ij} = r_{ij} - k$ или $s'_{ij} =s_{ij} - l$ и получить, например, $s'_{ij}=0$, $r_{ij} = k - l$. Я прав?