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

Question

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

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, но это явно не линейно.

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

Answer 1

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

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

 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)]