5.5. 5.5. Feladatok

  1. Határozza meg az alábbi „honnan-hova” táblázattal adott hálózaton

    a) az 1-ből a 8-ba irányuló maximális folyamot,

    b) a 3-ból az 5-be irányuló maximális folyamot,

    c) a 2-t a 7-től elválasztó minimális vágást,

    d) a 4-et a 3-tól elválasztó minimális vágást!

  2. A , pontok között naponként (vasúton, közúton stb.) szállítható anyag mennyiségét az alábbiakban adjuk meg : : 100, : 10, : 50, : 70, : 30, : 140, : 30, : 20. Számitsa ki a és a pontok között átáramoltatható napi szállítás maximális értékét és adja meg mely pontok képezik a szűk keresztmetszetet!

  3. Adott az alábbi „honnan-hova” táblázattal egy hálózat. Határozza meg a 3 és a 4 pontokat elválasztó vágást úgy, hogy a vágásbeli élek összhosszúsága minél kisebb legyen!

  4. Adott az alábbi "honnan-hova" táblázattal egy digráf. Határozza meg a 3-as és a 4-es pontokat elválasztó vágások közül azt, amelynél a vágásban lévő élek száma a legkevesebb!

  5. Adott egy városi úthálózat-részlet: , , , , , , útszakaszokkal, ahol útkereszteződéseket jelöl. A pont a város nyugati, a pont pedig a keleti részén van. Hogyan kell a és a pontok között É-D irányú utat tervezni, hogy az új út minél kevesebb helyen keresztezze a meglevő útszakaszokat?

    Útmutatás a 4. és az 5. feladathoz:

    A digráfot hálózattá kell alakítani egységnyi kapacitásokkal és utána minimális vágást kell meghatározni.

  6. Határozza meg az 1-ből a 7-be irányuló maximális folyamot és az 1-et a 7-től elválasztó minimális vágást!

  7. Adott az alábbi hálózat, amelyben keressük az 1-ből a 4-be irányuló maximális folyamot.

    a) Írja fel a maximális folyam feladatot matematikai formában és adja meg a feladat duálisát is!

    b) Oldja meg a feladatot szimplex módszerrel!

    c) Oldja meg a feladatot duál módszerrel!

    d) Oldja meg a feladatot növelő út módszerrel!