İndeks olarak tamsayı karar değişkenleri

Question

Aşağıdaki problemde sadece iki tamsayı değişkeni vardır; ancak, parametreler dizininde görünürler. Kanonik bir tamsayı programlama modeline dönüştürmek için herhangi birinin etkili bir fikri varsa, bunu takdir edin.

$$ \begin{alignat*}{2} &&\max \quad & (d_y - d_x)^2 \\ &&\text{s.t.} \quad & d_y - d_x \geq \alpha \\ && & x,y \in \mathbb{Z}_+ \\ \end{alignat*} $$

Answer 1

Sanmak$x,y\in\{0,\dots,n\}$. Sanırım bunlar arasında dolaşırım$(n+1)^2$çiftler ve kısıtlamayı karşılayan en iyisini saklayın.

Ancak tamsayılı programlamada ısrar ediyorsanız, ikili değişkenleri tanıtın.$x_i$ve$y_i$için$i\in\{0,\dots,n\}$, yorumlanması ile$d_x=\sum_i d_i x_i$ve$d_y=\sum_i d_i y_i$. Sorun maksimize etmektir$$\left(\sum_i d_i (y_i - x_i)\right)^2$$tabi\begin{align} \sum_i x_i &= 1\\ \sum_i y_i &= 1\\ \sum_i d_i (y_i - x_i) &\ge \alpha \end{align}İsterseniz hedefi doğrusallaştırabilirsiniz.