Как можно динамически определять ограничения с помощью симплексного метода?

Я пытаюсь правильно написать модель линейного программирования для своей задачи. Я хочу минимизировать сумму 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: я использую симплексный метод, все переменные являются целыми числами


mixed-integer-programming linear-programming simplex
person FifaBen    schedule 21.12.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

(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 из-за симметрии.

person Erwin Kalvelagen    schedule 21.12.2020
comment
Да, это ИЛИ, я уже добавил двоичные переменные, но проблема в том, что когда я хочу сформулировать таблицу, которая соответствует стандартной форме, w (i) и w (j) должны вычисляться ILP, так как я могу определить бюджет в моей таблице ?! - person FifaBen; 21.12.2020
comment
Не уверен, какая у вас стандартная форма. Это в основном используется в главе 1 учебников, но программные инструменты для моделей MIP обычно более гибкие в том, что они могут принять. - person Erwin Kalvelagen; 21.12.2020