Dopravní problém
Úloha číslo: 3258
Vyřešte simplexovou metodou následující slovní úlohu:
Společnost provádějící geologický průzkum má k dispozici tři vrtné soupravy, umístěné v lokalitách A1, A2 a A3. Po skončení průzkumu na stanovištích A1–3 má průzkum pokračovat v lokalitách B1, B2 a B3, opět je na každém místě zapotřebí jedné vrtné soupravy. Stanovte způsob, kteým mají souravy přejet mezi jednotlivými stanovišti, tak, aby celková ujetá vzdálenost byla co nejmenší, kde vzdálenosti mezi jednotlivými stanovišti jsou uvedeny v následující tabulce:
\( \begin{array}{cccc} & B1 & B2 & B3 \\ \hline A1 & 6 & 16 & 9 \\ A2 & 12 & 16{,}5 & 10 \\ A3 & 10 & 14 & 8{,}5 \\ \end{array} \)
Nápověda
Úlohu lze vnímat jako úlohu pro nalezení maximálního perfektního párováni v úplném bipartitním grafu.
Řešení
Převedeme ji na celočíselné programování s proměnnými \(x_1,…,x_9\), kde hodnoty proměnných budou z množiny \(\{0{,}1\}\) a \(x_1=1\) pokud zvolíme přejezd z A1 do B1, \(x_2=1\) pro přesun A1 do B2, atd.
Dostáváme úlohu:
\(\min 6x_1 + 16 x_2 + 9 x_3 + 12 x_4 + 16{,}5 x_5 + 10 x_6 + 10 x_7 + 14 x_8 + 8{,}5 x_9\\ \begin{array}{rcl} x_1 + x_2 + x_3 & = & 1 \\ x_4 + x_5 + x_6 & = & 1 \\ x_7 + x_8 + x_9 & = & 1 \\ x_1 + x_4 + x_7 & = & 1 \\ x_2 + x_5 + x_8 & = & 1 \\ x_3 + x_6 + x_9 & = & 1 \\ x_i & \in & \{0{,}1\} \\ \end{array} \)Podmínky zaručují, že z každého a také do každého stanoviště pojede právě jedna vrtná souprava.
Výchozí tvar pro simplexový algoritmus zní:
\(\max -6x_1 - 16 x_2 - 9 x_3 - 12 x_4 - 16{,}5 x_5 - 10 x_6 - 10 x_7 - 14 x_8 - 8{,}5 x_9\\ \begin{array}{rcl} x_1 + x_2 + x_3 & = & 1 \\ x_4 + x_5 + x_6 & = & 1 \\ x_7 + x_8 + x_9 & = & 1 \\ x_1 + x_4 + x_7 & = & 1 \\ x_2 + x_5 + x_8 & = & 1 \\ x_i & \ge & 0 \\ \end{array} \)Rovnici \(x_3 + x_6 + x_9 = 1\) jsme vyloučili, neboť plyne z předchozích pěti.
Zvolíme výchozí přípustnou bázi \(B=x_1,x_2,x_3,x_5,x_9\) (odpovídá přejezdům A\(i\to\)B\(i\)) a dostaneme soustavu
\( \begin{array}{lcrrrrr} x_1 & = & -x_4 & & - x_7 & & + 1 \\ x_2 & = & x_4 & + x_6 & & - x_8 \\ x_3 & = & & - x_6 & + x_7 & + x_8 \\ x_5 & = & -x_4 & - x_6 & & & + 1 \\ x_9 & = & & & - x_7 & -x_8 & + 1 \\ z & = & -5{,}5 x_4 & -0{,}5 x_6 & -4{,}5 x_7 & + 1{,}5 x_8 & - 31 \end{array} \)
Po dvou iteracích simplexového algoritmu získáme optimum
\(x^*=(1{,}0,0{,}0,0{,}1,0{,}1,0)^T\), a \(z=30\).Výsledek
Optimální plán přejezdů zní: A1\(\to\)B1, A2\(\to\)B3 a A3\(\to\)B2, s celkovou najetou vzdáleností 30 jedn.
