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.

Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
	Zaslat komentář k úloze