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

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

3* 2. EGÉSZ ÉRTÉKŰ PROGRAMOZÁSI FELADATOK ALKALMAZÁSA A teljesség igénye nélkül felsorolunk néhány gyakorlati problémát, amelyek egész értékű programozási feladatként fogalmazhatók meg. a) Hajórakodási probléma: adott súlyú, térfogatú és értékű tárgyak közül kiválasztandó a maximális értékű részhalmaz úgy, hogy ezek összsúlya és össztér­­fogata egy adott korlát alatt legyen. b) Utazó ügynök: adott n számú város és minden városból minden másikba való utazás költsége. Meghatározandó a minimális költségű körút. c) Fix költséges problémák: valamennyi termeléssel kapcsolatos probléma ilyen, amelyben van egy, a termelés volumenétől független beindítási költség. d) Gyártelepítési és beruházási problémák: valamennyi telepítési lehetőséget egy 0—1 változó reprezentálja (0, ha nem telepítjük a gyárat, 1 ha igen). Ezekre felírjuk az össztermelési igényre vonatkozó kikötéseket, valamint a körülményekből adódó megszorításokat. e) Üres szállítókocsi probléma: adott súlyú és térfogatú tárgyakat kell a leg­kevesebb számú adott kapacitású vasúti kocsival elszállítani. Érdekesség kedvéért megmelítjük még két híres elméleti problémát, amelynek konkrét megoldása átfogalmazható egész értékű feladatra: f) Négyszín probléma: bármilyen konkrét térkép esetén a színezési feladattal ekvivalens egész értékű feladatot is felírhatunk. g) Ortogonális latin négyzetek, adott méretű ortogonális latin négyzetek kere­sése szintén felírható egész értékű feladatként. Megemlítjük még, hogy a matematikai programozás számos különleges, ere­detileg nem egész értékű programozásos feladata ilyenné fogalmazható: a) Megkívánjuk, hogy G(x)10 vagy H(x) ^0 teljesüljön. B) A GjCxjsO, ...,Gm(x) = 0 feltételek közül legalább 0 teljesüljön. g) Minimalizálandó a 2 (p (xj) j=1 célfüggvény R konvex poliéder felett, ahol ФХх,) tetszőleges folytonos függvény 0'=1, •••.«)• (5) Ha G(x)=­0, akkor H(x)S0 teljesüljön. e) Keresendő egy f(x) konkáv függvény minimuma egy R konvex poliéderen. 3. A FELADAT MEGFOGALMAZÁSA, VALAMINT NÉHÁNY ALGEBRAI ALAPFOGALOM ÉS LEMMA Jelölje Dn az n dimenziós, 0—1 komponensekkel rendelkező vektorok halmazát. Legyen S azDn tetszőleges halmaz, amely lineáris vagy nemlineáris egyenlőtlen­ségekkel, logikai feltételekkel vagy bármilyen módon van megadva. Célunk az S halmaz elemeinek előállítása, illetve annak kimutatása, hogy 1 1­0. Amennyiben egy ilyen módszerrel rendelkezünk, akkor ezt úgy is módosíthatjuk, hogy sokkal kevesebb számítással csak egy bizonyos kritérium szerinti legjobb elemeket állítjuk elő az S halmazból. Tovább csökkenti a számítások mennyiségét, ha csak egyetlen optimális megoldást akarunk előállítani. A továbbiakban szükségünk lesz néhány alapfogalomra. 35

Next