Можно ли сформулировать s_j=max{ a_j, s_i+t_ij } как линейное ограничение?

Question

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

S_j = max {a_j, S_i + t_ij}

где a_j и t_ij являются константами

Спасибо заранее

Answer 1

Да, вы можете сделать это, введя новую двоичную переменную y_j (0 или 1) и пару линейных ограничений.

Мы можем переписать ваше ограничение как:

Sj = a      if a > Si + T
Sj = Si + T if a < Si + T


Sj = a y_j + (Si + T) (1 - yj)       .....(1)

Допустим, что y_j = 0, если а больше

y_j = 1, если a меньше, чем Si + T

M y_j + a - (Si + T) > 0   ....(2) 
where M is a big number, much bigger than a or Si or T.

Если y_j равно 1, вышеуказанное ограничение тривиально выполняется, и Sj будет равно a. Если y_j равно 0, a должно быть больше, чтобы ограничения были выполнены, и Sj = Si + T

В вашей формулировке просто включите (1) и (2), и вы будете применять max ограничение.