Произведение двух переменных в цели целочисленного программирования

Я пытаюсь создать проблему оптимизации в следующей форме, используя lpSolveAPI.

максимум 10(x1 + x2) * S1 + 20(x1 + x 2) * S2

под.к. S1 + S2 ‹= 1 # Это бинарные переменные.

2 * х1 + 3 * х2 ‹= 30

1 * х1 + 2 * х2 ‹= 10

x1 и x2 — целые числа.

Моя проблема в том, как создать эту мультипликативную переменную? Все примеры, с которыми я сталкиваюсь, переменным присваиваются линейно. Как упоминалось ранее, я использую lpSolveAPI из R.


mathematical-optimization linear-programming integer-programming lpsolve
person Beta    schedule 31.12.2017    source источник
comment
Вы можете рассмотреть случаи S1=0,S2=1 и S1=1,S2=0 отдельно и выбрать решение с большим результатом.   -  person Axel Kemper    schedule 31.12.2017
comment
@AxelKemper: Спасибо за отличное предложение! Я не думал об этом. Но одна проблема заключается в том, что если мой S, скажем, 50. Тогда мне нужно выполнить 50 отдельных оптимизаций, что будет немного сложно сделать. И мои S на самом деле больше 2.   -  person Beta    schedule 31.12.2017
comment
Возможно, вы можете использовать линеаризацию.   -  person Axel Kemper    schedule 31.12.2017
comment
@AxelKemper: Спасибо за это предложение! Обязательно посмотрю.   -  person Beta    schedule 31.12.2017

Ответы (1)


arrow_upward
1
arrow_downward

Похоже, у вас есть сумма вроде (10*x1 + 10*x2) * S1 + (20*x1 + 20*x2) * S2 +... с двоичными S1, S2,... и вы пытаетесь максимизировать этот термин.

Один из способов сделать это — определить переменные V1, V2,..., по одной для каждой из переменных S1, S2,.... Затем вы можете добавить следующие ограничения:

V1 <= 10*x1 + 10*x2
V1 <= M*S1
V2 <= 20*x1 + 20*x2
V2 <= M*S2
...

Здесь M — большая положительная константа. Независимо от значения S1, переменная V1 должна удовлетворять V1 ‹= 10*x1 + 10*x2. Если S1=0, то дополнительно имеем V1 ‹= 0. Если S1=1, то дополнительно имеем V1 ‹= M. Однако если M достаточно велико, то это никогда не будет связывающим ограничением.

Теперь мы можем заменить цель на:

max V1 + V2 + ...

Поскольку мы максимизируем, переменные V будут принимать значение 0, когда их соответствующая переменная S не установлена, и в противном случае она будет принимать значение, которое вы хотите в цели.

person josliber♦    schedule 31.12.2017