Как можно динамически определить ограничения с помощью симплексного метода?
Я пытаюсь правильно написать модель линейного программирования для своей задачи.
Я хочу минимизировать сумму w_i, и у меня есть следующее ограничение:
(a_i+w_i ≤ w_j) XOR (a_j+w_j ≤ w_i)
a_i and a_j are integer constants
w_i and w_j are integer variables
в общем, когда мы пишем стандартную форму системы, у нас есть уравнения, где часть записи представляет собой максимальное или минимальное количество продукта, это количество хорошо определено, но в моей задаче и w_i, и w_j неизвестны, их нужно вычислить по моему ILP, поэтому я не могу определить бюджет b при написании стандартной формы и при составлении первой таблицы, которые соответствуют стандартной форме! пожалуйста, как я могу это сделать?!
Re: Я использую симплексный метод. все переменные целые
Ответы 1
(1) Строго говоря, симплекс-метод предназначен только для непрерывных задач.
(2) INEQ1 OR INEQ2 можно сделать, добавив двоичные переменные. Я никогда не видел модели с INEQ1 XOR INEQ2. Я подозреваю, что в вашем случае мы просто можем использовать INEQ1 OR INEQ2.
(3) OR часто моделируется как:
a(i)+w(i) ≤ w(j) + M*δ(i,j)
a(j)+w(j) ≤ w(i) + M*(1-δ(i,j))
δ(i,j) ∈ {0,1}
Здесь M — это большое М: достаточно большая константа. Часто мы можем ограничить эти ограничения случаем, когда i<j из-за симметрии.
Не знаю, какая у вас "стандартная форма". Это в основном используется в главе 1 учебников, но программные инструменты для моделей MIP обычно более гибкие в том, что они могут принять.
для двоичных переменных a,b XOR — это просто «a + b == 1» в качестве ограничения, а OR — «a + b <= 1». (Стандарт для задачи MILP)
Да, это ИЛИ, я уже добавил двоичные переменные, но проблема в том, что когда я хочу сформулировать таблицу, которая соответствует стандартной форме, w(i) и w(j) должны быть вычислены ILP, так как я могу определить бюджет в моей таблице?!