Модели в таком виде на самом деле называют задачами билинейной оптимизации. Типичный подход к линеаризации билинейных членов - это так называемая огибающая Маккормика.
Рассмотрим переменные x и y, где вы хотите x*y в целях вашей задачи максимизации. Если мы предположим, что x и y ограничены xL <= x <= xU и yL <= y <= yU, то мы можем заменить x*y на w, верхнюю границу количества, со следующими ограничениями (вы можете увидеть вывод здесь):
w <= xU*y + x*yL - xU*yL
w <= x*yU + xL*y - xL*yU
xL <= x <= xU
yL <= y <= yL
Обратите внимание, что все эти ограничения линейны по переменным решения. В конверте Маккормика есть соответствующие нижние границы, но, поскольку вы максимизируете, они не важны в вашем случае.
Если вы хотите более жестко ограничить x*y, вы можете разделить интервал одной из переменных (здесь я буду использовать x) на диапазоны [xL1, xU1], [xL2, xU2], ..., [xLn, xUn ], вводя вспомогательные непрерывные переменные {x1, x2, ..., xn} и {w1, w2, ..., wn}, а также вспомогательные двоичные переменные {z1, z2, ..., zn}, которые будут указывать какой диапазон значений x был выбран. Приведенные выше ограничения можно заменить на (я покажу случай индекса 1, но они понадобятся вам для всех n индексов):
w1 <= xU1*y + x1*yL - xU1*yL*z1
w1 <= x1*yU + xL1*y - xL1*yU*z1
xL*z1 <= x1 <= xU*z1
В основном у вас будет x1 = 0 и w1 ‹= 0 всякий раз, когда z1 = 0 (иначе говоря, эта часть диапазона не выбрана), и у вас будет нормальный конверт Маккормика, если z1 = 1 (иначе, эта часть диапазона выбрана) .
Последний шаг - сгенерировать x и w из версий этих переменных, зависящих от диапазона. Это можно сделать с помощью:
x = x1 + x2 + ... + xn
w = w1 + w2 + ... + wn
Чем больше вы сделаете n, тем точнее будет оценка билинейного члена. Однако большие значения n повлияют на управляемость решения вашей модели.
И последнее замечание: вы указываете, что одна из ваших переменных не ограничена, но конверт Маккормика требует ограничений для обеих переменных. Вы должны исправить границы, решить, и если ваше оптимальное значение находится на границе, вы должны повторно решить с другой границей.
person
josliber♦
schedule
12.06.2015
