Variabel keputusan harus berada dalam gabungan beberapa interval terputus-putus

Dec 25 2020

Dalam Program Linear saya, saya mencoba untuk menyatakan bahwa variabel keputusan $x \in R$ hanya bisa berbaring dalam interval tertentu, mis $x \in [0,2] \cup [5,8] \cup [9,15]$.
Saya menyadari bahwa Anda dapat model baik kendala 1 OR kendala 2 dengan trik Big M (misalnya dijelaskan di sini dalam bagian 7.3 dan bertanya di sini , tapi tidak melihat secara langsung bagaimana ini bisa memecahkan pertanyaan saya. Ada gagasan?

Jawaban

1 MichalAdamaszek Dec 25 2020 at 16:43

Jika $[a_i,b_i]$ adalah $i$Interval -th kemudian untuk variabel biner $z_i$ ketidaksetaraan

$$a_iz_i-(1-z_i)M\leq x\leq b_iz_i+(1-z_i)M$$

memberi $x\in[a_i,b_i]$ kapan $z_i=1$ dan "gratis" ($x\in [-M,M]$) kapan $z_i=0$. Jadi keluarga dengan kendala seperti itu

$$\sum z_i= 1$$

memodelkan keanggotaan dalam persatuan interval $x\in\bigcup_i[a_i,b_i]$.

2 RobPratt Dec 26 2020 at 11:31

Dengan variabel biner yang sama $z_i$ Seperti jawaban @ MichalAdamaszek, formulasi yang lebih ketat \begin{align} \sum_i a_i z_i \le x &\le \sum_i b_i z_i \\ \sum_i z_i &= 1 \end{align}