@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}
}
}
  • Вопрос задан
  • 314 просмотров
Решения вопроса 2
Rsa97
@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.
Ответ написан
Комментировать
@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 -> максимизировать

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы