Формулирование ценовой оптимизации как MILP - PullRequest
Новая
       105

Формулирование ценовой оптимизации как MILP

1 голос
/ 13 марта 2020

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

I wi sh, чтобы найти оптимальную комбинацию фиксированного сбора F и переменной цены p для продукта.

У меня есть определенное количество n клиентов, которые каждый хочет приобрести количество q_i, за которое они готовы заплатить w_i.

Моя цель - максимизировать доход: max sum( F + q_i * p) для всех клиентов i in n

Мои переменные решения, конечно, F и p, а затем n двоичных переменных s_i, указывающих покупает ли клиент или нет.

У меня проблемы с формулировкой этой проблемы и ограничений, позволяющих клиентам не совершать покупки - некоторые клиенты имеют очень низкую готовность платить.

Очевидно, что есть ограничение F + q_i * p <= w_i, но это касается только покупателей. Я хотел бы наложить что-то вроде s_i * (F + q_i * p) <= w_i, но это явно не линейно.

Надеюсь, вышесказанное имеет смысл, и заранее спасибо за любую помощь.

1 Ответ

1 голос
/ 15 марта 2020

Позвольте мне повторить попытку.

Мы можем сформулировать проблему следующим образом: 

 max sum(i,  s(i)*(F+p*q(i))) 
     s(i)*(F+p*q(i)) ≤ w(i)
     for variables s(i) ∈ {0,1}, p ≥ 0, F ≥ 0

Это может быть линеаризовано как: 

 max sum(i, y(i))
     y(i) ≤ F+p*q(i)
     y(i) ≤ s(i)*w(i)
     y(i) ≥ F+p*q(i) - (1-s(i))*M
     for variables s(i) ∈ {0,1}, p ≥ 0, F ≥ 0, y(i) ≥ 0
     with M a large enough constant

Многие решатели допускают ограничения индикатора , Это упростит вещи: 

 max sum(i, y(i))
     s(i) = 1 ==> y(i) = F+p*q(i)
     y(i) ≤ s(i)*w(i)  
     for variables s(i) ∈ {0,1}, p ≥ 0, F ≥ 0, y(i) ≥ 0

или использование двух ограничений индикатора :: 

 max sum(i, y(i))
     s(i) = 1 ==> y(i) = F+p*q(i)
     s(i) = 0 ==> y(i) = 0
     for variables s(i) ∈ {0,1}, p ≥ 0, F ≥ 0, y(i) ∈ [0,w(i)]
...