Určení maximálního toku od zdroje  ke spotřebiči

Zadání úlohy
Na následujícím obrázku je zadán ohodnocený orientovaný graf (síť), kde ohodnocení hran znamená jejich kapacitu.
Uzel 1 je zdroj a uzel 4 je spotřebič.














Matematický model
                                  xij    = skutečná velikost toku z uzlu i do uzlu j
        maximalizovat
                          z =     x24    +   x34                                    (tok ke spotřebi(alternativně může být x12+x13 jako tok ze zdroje)

        za podmínek
                          x12            -   x23    -   x24               =    0    (stejný tok musí do uzlu 2 vstoupit jako vystoupit)
                                  x13    +   x23               -   x34    =    0    (stejný tok musí do uzlu 3 vstoupit jako vystoupit)
                          x12                                             ?    7    (tok nesmí překročit kapacitu hrany)
                                  x13                                     ?    5    (tok nesmí překročit kapacitu hrany)
                                             x23                          ?    1    (tok nesmí překročit kapacitu hrany)
                                                        x24               ?    3    (tok nesmí překročit kapacitu hrany)
                                                                   x34    ?    9    (tok nesmí překročit kapacitu hrany)
                         x12 ,    x13 ,     x23 ,      x24 ,       x34    ?    0    (tok nesmí být záporný)
##### Sheet 2 #####
Model v Excelu

                                                            PSO            LSO


                       1       0      -1      -1       0       0             -1
                       0       1       1       0      -1       0              1
                       1                                       7              1
                               1                               5              1
                                       1                       1              1
                                               1               3              1
                                                       1       9              1

                  x12     x13     x23     x24     x34
        xij        1       1       1       1       1

           z       2
##### Sheet 3 #####
Nalezení nejkratší cesty ze startu do cíle

Na následujícím obrázku je zadán ohodnocený orientovaný graf kde ohodnocení hran představují jejich délky.
Nechť uzel 1 je start a uzel 4 je cíl.



















                                  xij   je binární proměnná, nabývá tedy jen hodnoty 0 nebo 1
Matematický model                 xij    =    0       (cesta mezi uzly i a j není použita)
                                  xij    =    1       (cesta mezi uzly i a j je použita)
        minimalizovat
                          z =    4 x12   +  8 x13   +  2 x23   +  6 x24   +  3 x34             (celková délka cesty)

        za podmínek
                              -   x12    -   x13                                     =    -1   (součet cest z uzlu 1 do jakéhokoli dalšího musí být 1. tj. musíme volit jen jednu cestu z uzlu 1)
                                  x12               -   x23    -   x24               =    0    (součet příchozích použitých cest do uzlu 2 a odchozích použitých cest z uzlu 2 musí být stejný, tj. pokud jsme přišli do uzlu 2, musíme právě j
                                             x13    +   x23               -   x34    =    0    (součet příchozích použitých cest do uzlu 3 a odchozích použitých cest z uzlu 3 musí být stejný, tj. pokud jsme přišli do uzlu 3, musíme právě j
                                                                   x24    +   x34    =    1    (součet použitých cest do konečného uzlu 4 je jedna, tj. musíme dorazit do konečného uzlu a to právě jednou cestou)
                                 x12 ,      x13 ,      x23 ,      x24 ,       x34    ?    0































ednou z možných odchodových cest odejít)
ednou z možných odchodových cest odejít)


##### Sheet 4 #####
Model v Excelu

                                                            PSO             LSO


                      -1      -1                              -1              -2
                       1              -1      -1               0              -1
                               1       1              -1       0               1
                                               1       1       1               2

                  x12     x13     x23     x24     x34
        xij        1       1       1       1       1
        cij        4       8       2       6       3

           z       23