Задача линейного программирования. Как добавить ограничение в модель?

Question

[1alexandr]

Здравствуйте.

Необходимо решить следующую задачу. Так сложилось что необходимо это сделать на javascript :(
Система имеет вид CX = 0, где С - это матрица n на n, а X - вектор, который надо найти. Кроме того, вводится еще одно ограничение - неравенство x1+x2+..+xn <= 1. Целевая функция: F = x1+x2+...xn -> max.

Для решения задачи нашел такую либу. Попытался составить модель. Не понятно каким образом можно добавить ограничение x1+x2+..+xn <= 1. К сожалению примеров приведено мало и они все простые.

{
"optimize":{
"1s":"max",
"2s":"max",
"3s":"max"
},
"constraints":{
"1":{"min":1},
"2":{"min":1},
"3":{"min":1}
},
"variables":{
"1s":{"1":0,"2":-1,"3":0.2844},
"2s":{"1":0.1653,"2":0.1873,"3":-1},
"3s":{"1":0.0551,"2":0.115,"3":0.0987}
}
}

Answer 1

[Rsa97]

Решением системы C·X = B является вектор X = C^-1·B.
В вашем случае B = 0, значит при ΔC ≠ 0 получаем X = 0 (правило Крамера), а при ΔC = 0 система имеет бесконечное множество решений и надо сначала преобразовать её методом Гаусса, выделив зависимые переменные.

Покажу на примере:

2·x + 3·y - z = 0
4·x + 6·y -2·z = 0
3·x - y + 2·z = 0

Определитель равен нулю. Приводим методом Гаусса.

x + 3/2·y - 1/2·z = 0
0 = 0
- 11/2·y + 7/2·z = 0

Упрощаем

y = 7/11·z
x = -5/11·z

Преобразуем ваши условия

x + y + z = -5/11·z + 7/11·z + z  = 13/11·z <= 1
x + y + z = 13/11·z -> max

Очевидно, что максимум будет при z = 11/13. При этом x = -5/13, y = 7/13.

Answer 2

[tomatho]

Надо у либы просто из примера выписать получающиеся ограничения, чтобы понять.
А ограничения там такие:

brit * brit.plane    + yank * yank.plane  <= constraints.plane
brit * brit.person   + yank * yank.person <= constraints.person
brit * brit.cost     + yank * yank.cost   <= constraints.cost
brit * brit.capacity + yank * yank.capacity -> максимизировать

Затем смотрим на вашу систему:

x1 * x1.r1 + x2 * x2.r1 + ... + xn * xn.r1 = constraints.r1
x1 * x1.r2 + x2 * x2.r2 + ... + xn * xn.r2 = constraints.r2
...
x1 * x1.rn + x2 * x2.rn + ... + xn * xn.rn = constraints.rn
// и наконец!
x1 * x1.one + x2 * x2.one + ... + xn * xn.one <= 1
x1 * x1.one + x2 * x2.one + ... + xn * xn.one -> максимизировать

Вот и всё, надо написать для вас итоговый конфиг или сами уже поняли?