10. fejezet - Szűk-keresztmetszetű szállítási feladat

10.1. 10.1. A feladat megfogalmazása

Legyenek adottak a termelők (vagy termelőhelyek), amelyek rendre kínálattal rendelkeznek és az fogyasztók (vagy fogyasztóhelyek), amelyek kereslete (igénye) rendre . Legyenek továbbá adottak a szállítási idők, amelyek a termelőtől az fogyasztóhoz történő szállítás időtartamát jelentik és függetlenek a szállított mennyiségtől. A megadott adatok legyenek nemnegatív egészek.

A szűk-keresztmetszetű szállítási feladat az alábbi sémával jellemezhető:

Tegyük fel, hogy az összkínálat egyenlő az összkereslettel, azaz

A szűk-keresztmetszetű szállítási feladat:

Határozzuk meg a keresletet és a kínálatot kielégítő szállítást úgy, hogy az a legrövidebb ideig tartson feltéve, hogy a szállítások egyidőben kezdődnek el.

A szállítás lebonyolításának idejét a szállításban eltöltött leghosszabb idő határozza meg.

A szokásos módon jelöljük -vel a döntési változót, amely a termelőtől az fogyasztóhoz szállítandó mennyiséget jelenti.

Matematikai megfogalmazás:

Jelölje egész szám a termelőtől az fogyasztóhoz szállítandó meennyiséget.

Meghatározandók a keresletet és a kínálatot kielégítő egész számok (a termelőktől a kínálatuknak megfelelő mennyiség legyen elszállítva és a fogyasztók a keresletüknek megfelelő mennyiséget kapjanak) úgy, hogy a

mennyiség minimális legyen.

Az olyan optimalizálási feladatokat, amelyekben a célfüggvény valamilyen maximális érték és ennek a maximális értéknek kell a minimumát keresni szűk-keresztmetszet feladatoknak nevezzük.