Matematikai Lapok, 1968 (19. évfolyam, 1-4. szám)

1968-11-01 / 1-2. szám

1. A DISZKRÉT PROGRAMOZÁSI FELADATOK ÁLTALÁNOS ALAKJA Az általános diszkrét, vagy más néven egész értékű programozási feladatok szokásos algebrai alakja a következő: (1.1) min/(x) (1.2) g;(1) = ° (/=1,2, (1.3) xj = 0,1,2,... (/=1,2,..., x) ahol х = (хг,х2, ...,xi) és /(x), gi(x) tetszőleges­­ változós függvények. A tetszőleges egész értékű feladatok visszavezethetők olyanokra, amelyekben a változók csak 0 vagy 1 értéket vehetnek fel, ha ismerünk egy, a változók értékeire vonatkozó felső korlátot. Ha ugyanis m = 0, 1,2, ...,­­ a megengedett értékek halmaza, akkor ρ = 2r~1u1 + 2r~2u2+...+21ur_1 + 2°ur 0r = 0 vagy 1 (1 = 1,...,r) helyettesítéssel az λ változó helyett csupa 0—1 értékű változó szerepel. Az r értéke meghatározható a 2r_1 s(· 2r egyenlőtlenségből. Ha egy változó csak az öi, a 2, ..., a­ tetszőleges diszkrét értékeket veheti fel (az a­ számok nem feltétlenül egészek), akkor ezt a feladatot is visszavezethetjük 0—1 változós problémára a v · a161 + 62‰52 + ... + akök helyettesítéssel kiegészítve a ‰5i + <52+ ... +Sk = 1 Sj = 0 vagy 1 (j= 1, ..., k) feltételekkel. Ezek után a diszkrét­ és az egész értékű programozás kifejezéseket szinonimákként használhatjuk. Az (1.1)—(1. 3) megfogalmazáson kívül a feltételek között logikai típusúak is szoktak szerepelni, amelyek ugyan a legtöbbször helyettesíthetők volnának (1. 2) típusú feltételekkel, azonban igen sok egyenlőtlenségre lenne szükség, ami nagyon megnehezítené a feladat megoldását. 0—1 értékű változókra fogalmazva ilyen fel­tételek például a következők: х, = 1 =·Xt = 0 (i ?íj, I i -j\ S St), az úgynevezett szeparálási feltételek. Ezek jelentése: ha az xt változó értéke 1, úgy a következő 1 értékűtől legalább öt számú 0 értékű változó választja el. 34

Next