Egy kémiai feladattípus elemzése egészértékű programozás

segítségével

Diplomamunka

Írta: Hubik Irén

Alkalmazott matematikus szak

Témavezető:

Vizvári Béla, egyetemi docens

Operációkutatási Tanszék

Eötvös Loránd Tudományegyetem, Természettudományi Kar

Eötvös Loránd Tudományegyetem Természettudományi Kar

Tartalomjegyzék

1. Bevezetés 1 1.1. Általánosságban az egészértékű programozásról . . . . . . . . . . . . . . . . . . . . 1 1.2. Kémiai alkalmazás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2. A csoportelméleti módszer 8 2.1. A csoportfeladat megoldása dinamikus programozással . . . . . . . . . . . . . . . . 11 2.2. A csoportfeladat optimális megoldásának néhány tulajdonsága . . . . . . . . . . . 15 2.3. A csoportelméleti módszer felhasználása a korlátozás és szétválasztás algoritmusában 16 2.4. A csoportelméleti feladat alkalmazása az (1.2)-ben adott feladatra . . . . . . . . . 20

3. A Hilbert bázis meghatározása 25 3.1. Contejean-Devie algoritmusa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2. A Contejean-Devie algoritmus módosítása a (3.0.2)-es tétel alapján . . . . . . . . . 28 3.3. A Hilbert bázis meghatározása az (1.2)-ben adott feladatra . . . . . . . . . . . . . 30

Irodalomjegyzék 33

1. fejezet

Bevezetés

Az egészértékű programozás egy kémiai alkalmazásával fogunk foglalkozni. Adva van egy reakció, ami tulajdonképpen nem egy reakcióból áll, hanem több elemi reakció történik, de mi csak a kezdeti és végtermékeket ismerjük. A feladat, hogy meghatározzuk, hogy mik azok az elemi reakciók, amelyek az adott folyamatban lezajlanak. Erre adunk egy egészértékű programozási modellt, és megoldjuk a csoportelméleti módszerrel. Vizsgáljuk azt is, hogy mi az elemi reakciók Hilbertbázisa, és ezekből a reakciókból előáll-e a teljes reakció.

1.1. Általánosságban az egészértékű programozásról

Az egészértékű programozás széles körben elterjedt, mind a tudomány, mind a gazdasági és ipari területeken. Egészértékű programozási feladatok szinte bárhol előfordulhatnak, és bár néhol egy alkalmas közelítő megoldás is jó, ez nem mindig elegendő. Mindig az adott probléma határozza meg, hogyan is kezdjük el megoldani a feladatot. Az egészértékű programozási feladat NP teljes, azaz nem tudjuk polinom időben megoldani. A matematika területéről ilyen problémák például a halmazfedési feladatok, míg a gazdaságban például az utazóügynök feladat, különböző raktározási, készletezési, és termelésütemezési feladatok. Elméletben, végig tudnánk nézni minden megoldást, de ezek száma exponenciálisan nő a változók számában.

Jelöljük ℤ_{+}^{n}-szal az n-dimenziós, nemnegatív egész koordinátájú vektorokat. Egy általános egészértékű feladat a következő alakú:

\begin{aligned}min & c_{1}^{⊤}x + c_{2}^{⊤}y \\ & Ax + By = b_{1} \\ & P x + Qy ≤ b_{2} \\ & x ∈ ℤ_{+}^{n} \\ & y ∈ ℤ^{m} \end{aligned}  (1.1)

ahol A: (k × n), B: (k × m), P: (l × n), Q: (l × m)-es mátrixok, c^{⊤} = (c_{1}^{⊤}, c_{2}^{⊤}): (n + m)-es és b: (l + k)-as vektorok.

Többféle megoldási lehetőség és módszer létezik. Vannak heurisztikus algoritmusok, amelyek már egy meglévő megengedett megoldásból indulnak ki, és azt módosítják, amíg jobb megoldást tudnak így elérni. Ezekre a módszerekre létezik a T SP LIB mérőszám, ami mutatja, hogy az optimális megoldástól általában (tesztfeladatokra futatják őket, és így mérik) mennyire tér el az így kapott eredmény. Legtöbbször érdemes több ilyen heurisztikát is alkalmazni egymás után.

Egy másik megoldási lehetőség, hogy a feladat valamilyen relaxáltját oldjuk meg. Ez azt jelenti, hogy valamit elhagyunk a feltételek közül, ami nélkül egyszerűbb feladathoz jutunk. Az így kapott feladatot megoldva kapunk egy alsó, illetve felső korlátot a feladat minimum, illetve maximum értékére. Az egyik legelterjedtebb, mikor az egészértékűségi feltételt hagyják el, és a lineáris programozási relaxáltat oldják meg. Erre jól működő megoldó programok léteznek.

Erre aztán akár felépíthetünk egy korlátozás, és szétválasztás módszert is. Ez azt jelenti, hogy felbontjuk a megoldások halmazát, majd ezeken vizsgáljuk az optimumot, és azon a részhalmazon haladunk tovább, ahol a jobb optimumot tudjuk elérni. Léteznek vágás-típusú módszerek is, amik az egész pontok konvex burkát közelítik, és így állítanak elő megoldást.

Legtöbbször a feladat tulajdonságából adódóan, gyors megoldásra van szükség, ilyenek például a különböző ütemezési feladatok, ami újabb korlátot ad a feladatmegoldásnak.

Ezeket a módszereket legtöbbször nem önmagukban használják, hanem kombinálják egymással, annak érdekében, hogy minél jobb optimumot tudjanak elérni.

1.2. Kémiai alkalmazás

Egy adott folyamat reakció útvonalainak meghatározása fontos elméleti kérdés, mindamellett ipari fontossága is van. Szeretnénk pontosan ismerni mi zajlik egy folyamaton belül, és az ipar ezt szeretné szabályozni is, és azt a reakció útvonalat meghatározni, ami számára valamilyen szempontból a legjobb, például a legkisebb költségű.

A probléma tulajdonképpen kétszintű. Az egyik, hogy meghatározzuk, milyen elemi reakciók mehetnek egyáltalán végbe, és ezek után a második feladat annak leírása, hogy áll ezekből elő a folyamat. Ez természetesen több úton mehet végbe.

Az első problémával [5] foglalkozik részletesen. Hogy szemléltethessük, tekintsük a következő reakciót:

2MnO_{4}^{−} + 6H^{+} + 5H_{2}C_{2}O_{4} = 2Mn^{2+} + 8H_{2}O + 10CO_{2}

Elemi reakciónak azt nevezzük, amelyben legfeljebb két anyag reagál (molekula, ion, atom, illetve gyök). Tételezzük fel egy közvetítő oldat jelenlétét. Adva vannak azok az anyagok, amelyek a közvetítő oldatban benne vannak, ezeket a kémikusok mérésekkel állapítják meg. A mi példánkban összesen 19 anyag. Ezek 4 atomból és elektronokból állnak elő. Ezt mutatja a következő táblázat:

C H Mn O e
H_{2}C_{2}O_{4}  2 2 0 4 0
HC_{2}O_{4}^{−}  2 1 0 4 1
H^{+}  0 1 0 0 -1
C_{2}O_{4}^{2−}  2 0 0 4 2
Mn^{2+}  0 0 1 0 -2
MnC_{2}O_{4}  2 0 1 4 0
MnO_{4}^{−}  0 0 1 4 1
MnO_{2}  0 0 1 2 0
Mn^{3+}  0 0 1 0 -3
CO_{2}  1 0 0 2 0
H_{2}O  0 2 0 1 0
[MnO_{2}, H_{2}C_{2}O_{4}]  2 2 1 6 0
CO_{2}^{−}  1 0 0 2 1
[Mn (C_{2}O_{4})]^{+}  2 0 1 4 -1
[Mn (C_{2}O_{4})_{2}]^{−}  4 0 1 8 1
[MnC_{2}O_{4}, MnO_{4}^{−}, H^{+}]  2 1 2 8 0
[MnC_{2}O_{4}^{2+}, MnO_{3}^{−}]^{+}  2 0 2 7 -1
[MnC_{2}O_{4}^{2+}, MnO_{3}^{−}, H^{+}]^{2+} 2 1 2 7 -2
[H^{+}, MnO_{2}, H_{2}C_{2}O − 4]^{+}  2 3 1 6 -1

A táblázat egy mátrixot ad, melynek transzponáltját D-vel jelöljük. D ∈ ℤ^{5×19}. D nevezhető atom mátrixnak, hiszen azt mondja meg, hogy az egyes jelenlévő anyagokban a különböző atomokból és az elektronból mennyi van. Az utóbbiakból csak a hiányt, vagy a többletet mutatja. Egy elemi reakció többféle lehet. Vagy egy létező molekula felbomlása, például ha az oldószer egy molekulája nekiütközik és "felrobbantja", vagy két (azonos, vagy különböző) molekula ütközése és átalakulása nyomán jön létre. Jelölje d azt a vektort, ami vagy egy D-beli oszlop, ha egy elem felbomlását szeretnénk megkapni, vagy két D-beli oszlop összege, ha két anyag találkozásakor létrejövő reakciót akarjuk leírni. Ekkor egy x ∈ ℤ_{+}^{19} vektor fogja megadni, hogy milyen anyagok jönnek létre:

Dx = d,

feltéve, hogy x-ben a d-t előállító oszlopokhoz tartozó komponensek 0-k. Például: H_{2}C_{2}O_{4} dekom-

poziciója. Ennek az anyagnak a d = ( \begin{matrix}2 \\ 2 \\ 0 \\ 4 \\ 0 \end{matrix} ) vektor felel meg. Ekkor az

x = ( 0 0 2 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 )^{⊤}

megoldás a H_{2}C_{2}O_{4} = 2H^{+} + 2CO_{2}^{−} reakciót fogja meghatározni.

Ebben az esetben összesen 19 + 19 + ( \begin{matrix}19 \\ 2 \end{matrix} ) = 209 lineáris egyenletrendszert kell megoldani,

az egész számok halmazán. A kapott reakciók számát csökkenteni lehet kémiai vizsgálatokkal.

[5] alapján, meg tudjuk adni a folyamatban lezajló elemi reakciókat. Tekintsük a [3] által adott egyszerűbb példát. A folyamat, azaz az összetett reakció a következő:

C_{4}H_{10} → C_{4}H_{8} + H_{2}

A bután dehidrogenizálása. Temkin (1971) határozta meg a folyamatban lévő elemi reakciókat:

\begin{matrix}(1 →) & C_{4}H_{10} + λ → C_{4}H_{8}λ + H_{2} \\ (1 ←) & C_{4}H_{8}λ + H_{2} → C_{4}H_{10} + λ \\ (2 →) & C_{4}H_{8}λ → C_{4}H_{8} + λ \\ (2 ←) & C_{4}H_{8} + λ → C_{4}H_{8}λ \\ (3 →) & C_{4}H_{8}λ → C_{4}H_{6}λ + H_{2} \\ (3 ←) & C_{4}H_{6}λ + H_{2} → C_{4}H_{8}λ \\ (4 →) & C_{4}H_{6}λ → C_{4}H_{6} + λ \\ (4 ←) & C_{4}H_{6} + λ → C_{4}H_{6}λ \\ (5 →) & C_{4}H_{10} + λ + C_{4}H_{6}λ → 2C_{4}H_{8}λ \\ (5 ←) & 2C_{4}H_{8}λ → C_{4}H_{10} + λ + C_{4}H_{6}λ \end{matrix}

[3]-ban felteszik, hogy minden elemi reakció, mindkét irányban végbe tud menni. Bevezettek 6 axiómát, amelyek a folyamat lefolyásának szabályait adják meg, és amelyeknek teljesülniük kell minden egyes reakció útvonalra. (Azaz minden olyan reakció részhalmazra, amelyek előállítják az összetett reakciót.) Kiindulási anyagoknak fogjuk nevezni az összetett reakció kiindulási anyagait, és célanyagoknak a létrejövő anyagait. Ebben a példában, kiindulási anyag a C_{4}H_{10}, és célanyagok C_{4}H_{8}, H_{2}. Közbülső anyagnak nevezünk minden olyan anyagot, amely a folyamatban létrejön, vagy keletkezik, a kiindulási, és célanyagokon kívül. Az axiómák:

(R1) Minden célanyag előáll az útvonalban szereplő reakciókból.

(R2) Minden kiindulási anyagot felhasználnak az útvonalban lévő reakciók.

(R3) Minden közbülső anyag, ami előáll valamely reakcióból, az teljesen felhasználódik egy, vagy több reakcióban, amely az útvonalban szerepel. Illetve, minden közbülső anyag, amit felhasználunk valamely reakcióhoz, az előáll egy, vagy több reakcióból.

(R4) Az útvonal csak előre definiált reakciókat tartalmaz.

(R5) Az útvonal körmentes, azaz nincs olyan reakcióhalmaz (részútvonal) az útvonalban, amelyre a kiinduló és célanyagok megegyeznének.

(R6) Legalább egy elemi reakció felhasználja a kiinduló anyagot.

Az elemi reakciókat, és az összetett reakciót le tudjuk írni vektorokkal aszerint, hogy melyek a kiindulási és célanyagaik. A vektor legyen a következő: Minden koordináta egy anyagnak felel meg aszerint, hogy ha az az anyag kiindulási anyaga a reakciónak, akkor negatív szám, ha célanyag, akkor pozitív, egyébként 0. A számok az a mennyiséget jelölik, ahány egységnyi anyag felhasználódik, illetve létrejön a reakcióban. A példában összesen 7 anyag van, ezért most 7 dimenziós vektoroknak felelnek meg. Azaz a reakciókat leíró mátrix:

1 → 1 ← 2 → 2 ← 3 → 3 ← 4 → 4 ← 5 → 5 ← a folyamat
C_{4}H_{10} -1  1  0  0  0  0  0  0  -1  1  -1
λ  -1  1  1  -1  0  0  1  -1  -1  1  0
C_{4}H_{8}λ 1  -1  -1  1  -1  1  0  0  2  -2  0
H_{2}  1  -1  0  0  1  -1  0  0  0  0  1
C_{4}H_{8}  0  0  1  -1  0  0  0  0  0  0  1
C_{4}H_{6}λ 0  0  0  0  1  -1  -1  1  -1  1  0
C_{4}H_{6}  0  0  0  0  0  0  1  -1  0  0  0

Ekkor az előző példához hasonlóan, A jelölje a táblázat első 10 oszlopa által adott mátrixot, míg b legyen az utolsó oszlop. Ekkor a következő egyenletrendszer és az egészértékűségi feltétel kielégíti az axiómákat, kivéve a körmentességet. De azt is biztosítani tudjuk a csupa 1-ből álló célfüggvényvektorral.

Ax = ab : (A ∈ ℤ^{7×10}, b ∈ ℤ^{7}) x ∈ ℤ_{+}^{10}, a ∈ ℤ_{+}, a ≠ 0.

A jelenlegi feladatunk olyan, hogy mindkét irányú reakció szerepel benne, ezért a feladatot átalakíthatjuk egy ekvivalens alakba, úgy, hogy a mátrixunk, csak az odairányú reakciónak megfelelő oszlopot tartalmazzák, és ha a neki megfelelő komponens pozitív, akkor a reakció az adott irányban fog végbemenni, míg ha negatív, akkor visszafelé. Ez következik abból, hogy az útvonal körmentes, azaz nem szerepelhet egyszerre az oda- és visszareakció is. A jobboldali b vektort is átvihetjük a másik oldalra, és akkor a-t is változóként tekintve, egy homogén rendszert kapunk. Azaz

Ā = ( \begin{matrix}−1 & 0 & 0 & 0 & −1 & 1 \\ −1 & 1 & 0 & 1 & −1 & 0 \\ 1 & −1 & −1 & 0 & 2 & 0 \\ 1 & 0 & 1 & 0 & 0 & −1 \\ 0 & 1 & 0 & 0 & 0 & −1 \\ 0 & 0 & 1 & −1 & −1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \end{matrix} ) , b̄ = ( \begin{matrix}0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix} ) .

Vizsgálnunk kell az

Āx = b̄, x ∈ ℤ^{6}

rendszert, az

x_{6} > 0

feltétel mellett, ami ekvivalens az x_{6} ≥ 1 korláttal. Az egyenletrendszert megoldva a következő megoldásokat kapjuk:

x = ( \begin{matrix}a − c \\ a \\ c \\ 0 \\ c \\ a \end{matrix} ) ,

ahol a ≥ 1 és c tetszőleges egész számok. Ekkor a és c számok nagyságától függően a következő eredményeket kapjuk:

a megoldás előjelei reakciók
c < 0 < a (+, +, −, 0, −, +)  1-es és 2-es oda-, 3-as és 5-ös visszafelé
c = 0 < a (+, +, 0, 0, 0, +)  1-es, 2-es odafelé
0 < c < a (+, +, +, 0, +, +)  1,2,3,és 5-ös odafelé
0 < c = a (0, +, +, 0, +, +)  2,3,és 5-ös odafelé
0 < a < c (−, +, +, 0, +, +)  1-es vissza-, 2,3,és 5-ös odafelé.

Ebből az eredményből látszik, hogy a 4-es reakció egyik útvonalban sem fut le, míg a 2-es reakció mindegyiknél odafelé minden esetben végbemegy. Az azonosan 1 célfüggvény, a feladat ezen alakjában a következő alakú:

|a − c| + 2 |a| + 2 |c| .

Ennek segítségével tudjuk meghatározni, hogy az egyes intervallumokon belül, melyik a körmentes megoldás. Ilyen módszerrel meghatározhatjuk az összes reakció útvonalat:

• Ha c < 0 < a, akkor a célfüggvény: 3a − 3c. Ez akkor minimális, ha a = 1, c = −1. Ez azt jelenti, hogy

1→ reakció 2-szer
2→ reakció 1-szer
3← reakció 1-szer
5← reakció 1-szer
teljes reakció 1-szer megy végbe

• Ha c = 0 < a, akkor a célfüggvény: 3a, azaz a = 1, c = 0 az optimális.

1→ reakció 1-szer
2→ reakció 1-szer
teljes reakció 1-szer megy végbe

• Ha 0 < c < a, akkor a célfüggvény: 3a + c. Ha itt a = 1 lenne, akkor nem lenne egész c érték, így a célfüggvény akkor minimális, ha a = 2, c = 1.

1→ reakció 1-szer
2→ reakció 2-szer
3→ reakció 1-szer
5→ reakció 1-szer
teljes reakció 2-szer megy végbe

• Ha 0 < c = a, akkor a célfüggvény: 4a. Ekkor az a = c = 1 az optimális.

2→ reakció 1-szer
3→ reakció 1-szer
5→ reakció 1-szer
teljes reakció 1-szer megy végbe

• Ha 0 < a < c, akkor a célfüggvény: a + 3c, azaz a = 1, c = 2 minimális. Ekkor:

1← reakció 1-szer
2→ reakció 1-szer
3→ reakció 2-szer
5→ reakció 2-szer
teljes reakció 1-szer megy végbe

Azt is észrevehetjük, hogy 0 < c < a eset előáll a c = 0 < a, és a 0 < c = a esetek összegeként.

Tehát a reakció útvonalakat az azonosan 1 célfüggvénnyel határozhatjuk meg, és így kaphatunk képet a folyamat hátteréről. Másrészt, ha célfüggvénynek például az adott elemi reakció előállításának költségét adjuk, akkor ipari haszna is lehet, hiszen meghatározhatjuk azt az útvonalat, ami a legköltségkímélőbb és optimálisan állíthatjuk elő az összetett reakciót. Feltehetjük, hogy a költségek pozitívak, így garantálni tudjuk ismét a körmentességet. (Hiszen így a kör súlya is pozitív és azt elhagyva jobbat kapnánk.)

Az elemi reakciók mátrixa, többnyire alacsony rangú, ezért jól alkalmazható rájuk például a csoportelméleti módszer.

Egy másik lehetőség, hogy az elemi reakciók által kifeszített kúp Hilbert-bázisát vizsgáljuk. Feleltessünk meg minden reakciónak egy vektort, ugyanúgy mint az előbb. Ezek a vektorok egy kúpot feszítenek ki. Ha ismerjük ezen kúp Hilbert-bázisát, akkor minden reakció a kúpból előáll ezen Hilbert-bázis elemeinek egész együtthatós lineáris kombinációjaként. Azt kell ezután megvizsgálnunk, hogy az összetett folyamatunk benne van-e ebben a kúpban, azaz előáll-e Hilbert-bázis-beli elemek összegeként.

A csoportelméleti módszer

Ebben a fejezetben az egészértékű programozási feladat megoldását relaxáció segítségével fogjuk megadni, és így egy olyan feladathoz jutunk, amelyben a feltételek együtthatói egy csoport elemei.

A megoldani kívánt egészértékű feladat:

\begin{aligned}min & c^{⊤}x \\ & Ax = b \\ & x ∈ ℤ_{+}^{n} \end{aligned}  (2.1)

ahol A ∈ ℤ^{m×n} teljes rangú, (m ≤ n), b ∈ ℤ^{m}, c ∈ ℤ^{n}. Megoldjuk a lineáris programozási relaxáltat és felbontjuk az A mátrixot, az optimális bázis szerint:

A = (B, N)

(B a lineáris programozás szerinti optimális bázis), így a megfelelő vektorok is felbomlanak két részre:

c = ( \begin{matrix}c_{B} \\ c_{N} \end{matrix} ) , x = ( \begin{matrix}x_{B} \\ x_{N} \end{matrix} )

Ekkor az Ax = b átírható

Bx_{B} + Nx_{N} = b

alakba. Mivel feltettük, hogy A teljes rangú, B optimális bázisa, ezért létezik a B mátrix inverze. Így x_{B} a következő alakba írható:

x_{B} = B^{−1}b − B^{−1}Nx_{N}.

Innen a feladat következő ekvivalens alakját kapjuk:

\begin{aligned}min & (c_{N}^{⊤} − c_{B}^{⊤}B^{−1}N) x_{N} + c_{B}^{⊤}B^{−1}b \\ & x_{B} = B^{−1}b − B^{−1}Nx_{N} \\ & x_{B} ∈ ℤ_{+}^{m} \\ & x_{N} ∈ ℤ_{+}^{n−m} \end{aligned}  (2.2)

A feladatnak ebből az alakjából készítünk relaxációt. Többnyire az egészértékűségi feltételt szokták elhagyni, és így lineáris programozási feladathoz jutnak, amire vannak megoldási lehetőségek. Most ehelyett x_{B} pozitivitási megkötését hagyjuk el. x_{B} egészértékűsége miatt, az x_{B} = B^{−1}b − B^{−1}Nx_{N}-nek is egésznek kell lennie. Így a feladat következő alakját kapjuk:

\begin{aligned}min & (c_{N}^{⊤} − c_{B}^{⊤}B^{−1}N) x_{N} + c_{B}^{⊤}B^{−1}b \\ & B^{−1}Nx_{N} ≡ B^{−1}b (mod 1) \\ & x_{N} ∈ ℤ_{+}^{n−m} \end{aligned}  (2.3)

A kongruencia minden sorra vonatkozik.

Az A mátrix elemeinek egészértékűségéből következik, hogy a feltétel együtthatói, és a jobboldal egy véges csoport elemei. Ezt a csoportot a B^{−1} mátrix oszlopai generálják, a komponensenkénti mod 1 összeadással. Ennek a csoportnak a B^{−1} mátrix elemeit explicit módon megadó algebrai tétel következtében legfeljebb |det (B)|^{m} eleme lehet. Hogy a csoport elemeit meg tudjuk adni és a feladatot megoldjuk, szükségünk van a mátrixok Smith-féle normálalakjára.

2.0.1. Tétel. Legyen B ∈ ℤ^{m×m} nem szinguláris mátrix. Ekkor léteznek olyan, szintén (m × m)- es P és Q mátrixok, hogy

i. |det (P)| = |det (Q)| = 1,

ii. léteznek olyan ε_{1}, ε_{2}, ..., ε_{m} egészek, hogy

P BQ = ( \begin{matrix}ε_{1} & 0 & … & 0 \\ 0 & ε_{2} & … & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & … & ε_{m} \end{matrix} )

iii. ε_{i} | ε_{i+1}, i = 1, ..., m − 1.

Azaz a mátrix olyan alakra transzformálható, hogy a fődiagonálisban lévő elemek, az előzőek többszörösei. Ennek egy következményét használjuk majd fel a csoportfeladatnál.

2.0.2. Következmény. Legyen d = |det (B)|. Legyen p^{k} a d szám legnagyobb kitevős prím faktora. Ekkor az előző tétel ii-pontjában, a P BQ transzformált alakban legfeljebb k darab ε_{i} lehet különböző az 1 vagy −1 számoktól.

Mivel a P BQ mátrix diagonális, ezért könnyen megadhatjuk az inverzét. Jelöljük ε-nal a P BQ mátrixot, ekkor

ε^{−1} = ( \begin{matrix}\frac{1}{ε_{1}} & 0 & … & 0 \\ 0 & \frac{1}{ε_{2}} & … & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & … & \frac{1}{ε_{m}} \end{matrix} )

Ekkor világos, hogy

P BQε^{−1} = E,

ahol E az m×m-es egységmátrixot jelöli. Ezt az egyenletet beszorozva balról P^{−1}-el, jobbról P -vel a következőt kapjuk:

BQε^{−1}P = E.

Ebből látszik, hogy a B mátrix inverze:

B^{−1} = Qε^{−1}P.

Most visszatérhetünk a feladathoz, de nem B^{−1}-el fogunk beszorozni, mint (2.2)-ben, hanem ε^{−1}P -vel. Ez szintén nem szinguláris mátrix, így továbbra is ekvivalens feladatot fogunk kapni. Az előbbiek szerint ε^{−1}P = Q^{−1}B^{−1}. A felbontás tulajdonságai miatt

|det (Q)| = |det (Q^{−1})| = 1,

ezért Q^{−1} mátrixnak is egészek az elemei. A következő állítás szerint ezért a Q^{−1} mátrixszal való szorzás nem változtat a feladat kongruenciáján.

2.0.3. Állítás. Legyen r és s két rögzített pozitív egész, Y tetszőleges (r × s) méretű mátrix, w r-dimenziós vektor. Legyen továbbá V ∈ ℤ^{r×r} mátrix, melyre |det (V)| = 1. Ekkor tetszőleges x ∈ ℝ^{s} esetén az

Y x ≡ w (mod 1)

kongruencia akkor és csak akkor áll fenn, ha

V Y x ≡ V w (mod 1),

ahol a kongruencia soronként értendő.

Bizonyítás: Tegyük fel, hogy Y x ≡ w (mod 1) igaz, akkor ∃z ∈ ℤ^{r} vektor, hogy

Y x − w = z.

Ezt megszorozva balról a V mátrixszal, kapjuk:

V Y x − V w = V z.

Mivel V egészekből álló mátrix, így V z is egész, amiből V Y x ≡ V w (mod 1) következik. Visszafelé ugyanígy bizonyítható, csak most V^{−1} szintén egész mátrixszal kell szorozni. □

Az állítás szerint a feladatunk ekvivalens alakja:

\begin{aligned}min & (c_{N}^{⊤} − c_{B}^{⊤}B^{−1}N) x_{N} + c_{B}^{⊤}B^{−1}b \\ & ε^{−1}P^{−1}Nx_{N} ≡ ε^{−1}P^{−1}b (mod 1) \\ & x_{N} ∈ ℤ_{+}^{n−m} \end{aligned}  (2.4)

Az ε^{−1} mátrix diagonális, ezért a vele való szorzás azt jelenti, hogy minden sort beszorzunk a hozzá tartozó \frac{1}{ε_{i}} -vel (i = 1, ..., m). P és N is egész együtthatós mátrixok, ezért ha ε_{i} = ±1, akkor a kongruencia tetszőleges egész x_{N} vektor esetén fenn fog állni. Most tudjuk felhasználni a (2.0.2.)-es következményt, hogy ε diagonálisában, csak legfeljebb annyi különbözik ±1-től, mint d = |det (B)| prímtényezős felbontásában szereplő legnagyobb kitevő. Általában ez jelentősen csökkenti a feltételek számát.

Jelölje p_{i} a P N mátrix i-dik sorát, és q_{i} a P b vektor i-dik elemét. Tegyük fel, hogy az utolsó r ε_{i} különbözik ±1-től, ahol r : 0 ≤ r ≤ m. Ekkor a feladat ekvivalens alakja:

\begin{aligned}min & (c_{N}^{⊤} − c_{B}^{⊤}B^{−1}N) x_{N} + c_{B}^{⊤}B^{−1}b \\ & p_{i}x_{N} ≡ q_{i}  (mod ε_{i}),  i = m − r + 1, ..., m \\ & x_{N} ∈ ℤ_{+}^{n−m} \end{aligned}  (2.5)

Ebből látható, hogy a kongruenciarendszer bal oldalán legfeljebb d különböző vektor állhat, melyek a komponensenkénti (mod ε_{i}) vett összeadásra nézve egy legfeljebb d-edrendű csoportot alkotnak. Tehát így javítani tudtuk korábbi d^{m}-es becslésünket.

2.1. A csoportfeladat megoldása dinamikus programozással

Az egyszerűbb jelölés kedvéért vezessük be a következőket: t := n − m, x := x_{N}. Legyenek a csoport generáló elemei, azaz a P N mátrix oszlopai α_{1}, α_{2}, ..., α_{t}, és a jobb oldalon álló elem P b = β. Jelölje a csoportbeli összeadást ⊕, a csoport nullelemeit 0, és a célfüggvény vektort γ = c_{N}^{⊤} − c_{B}^{⊤}B^{−1}N. Az általánosság megszorítása nélkül feltehetjük, hogy

α_{i} ≠ α_{j}, i ≠ j.

Így a csoportfeladat:

\begin{aligned}min & ∑_{j=1}^{t} γ_{j}x_{j} \\ & \begin{matrix}t \\ ∑ & ⊕ \\ j=1 \end{matrix} α_{j}x_{j} = β \\ & x ∈ ℤ_{+}^{t} \end{aligned}  (2.6)

Jelölje G az α_{i}, i = 1, ..t elemek által generált részcsoport elemeinek halmazát, azaz

G = \{ \begin{matrix}t \\ ∑ & ⊕ \\ j=1 \end{matrix} α_{j}x_{j} : x ∈ ℤ_{+}^{t}\} .

G véges halmaz, elemeinek száma legfeljebb d. G nem az összes r-dimenziós, (mod ε_{i}) komponensenként vett vektor additív csoportja, hanem ennek csak a részcsoportja, amit az α_{i}-k (i = 1, ..., t) feszítenek ki. Így előfordulhat, hogy β ∉ G. Ez azt jelentené, hogy a csoportfeladatnak nincs megengedett megoldása. Ebből az is következne, hogy az eredeti egészértékű programozási feladatnak sincs megengedett megoldása, hiszen a csoportfeladat ennek relaxációja.

Ha

β ∈ G,

akkor a csoportfeladat ekvivalens egy gráfban legrövidebb utat kereső feladattal. Legyen ez a gráf a következő: a csúcsok halmaza G, az élek:

E = {(μ, ν) : μ, ν ∈ G; ∃j : μ ⊕ α_{j} = ν} ,

a (μ, μ ⊕ α_{j}) él költsége pedig γ_{j}. Ebben a gráfban keressük a 0-ból β-ba vezető legrövidebb utat. Ilyen optimális út akkor és csak akkor létezik, ha a gráfban nincs negatív kör. Erre szükségünk van ahhoz, hogy a dinamikus programozási algoritmus megtaláljon egy legrövidebb utat. Negatív kör akkor és csak akkor van a gráfban, ha

inf \{γ^{⊤}x : x ∈ ℤ_{+}^{t}; \begin{matrix}t \\ ∑ & ⊕ \\ j=1 \end{matrix} α_{j}x_{j} = 0\} < 0.  (2.7)

Most fog nagyon fontos szerepet játszani, hogy miért a lineáris programozás szerinti optimális bázis szerint osztottuk fel az eredeti mátrixunkat. Lineáris programozásban optimális bázis esetén a γ célfüggvény vektor nemnegatív. Ha nem tettük volna ezt fel, és létezne egy j index, melyre

γ_{j} < 0.

Mivel G véges csoport, ezért elemeinek rendje véges, azaz ∃k ∈ ℤ_{+}, hogy kα_{j} = 0, így

kγ_{j} < 0,

és teljesül (2.7).

Ezek alapján már fel lehet építeni, egy dinamikus programozáson alapuló legrövidebb út kereső algoritmust, amely megoldja a feladatot. Ehhez persze fel kell tenni, hogy a számítógépnek van elegendően nagy memóriája, a csoportelemekhez tartozó összes adat tárolásához. Szükségünk van arra is, hogy egyszerűen tudjunk hivatkozni a csoportelemekre. Felhasználva a p_{i}x ≡ q_{i} (mod ε_{i}) kongruenciát, minden csoportelem egyértelműen felírható egy u, r-dimenziós vektorként:

u ∈ ℤ^{r}; 0 ≤ u_{i} ≤ ε_{i} − 1, i = 1, 2, ..., r.

Ez pedig egyértelműen megfeleltethető egy 0 és d − 1 közé eső egésznek, az ε_{i} (i = 1, ..., r) alapszámokkal meghatározott általánosított számrendszerben a következő módon:

u ↦ ∑_{i=1}^{r} u_{i} ∏_{k=1}^{i−1} ε_{i}.

Így sorba rendeztük a csoportelemeket.

Vezessük be a következő jelöléseket: δ (q): a q indexű csoportelem, c(μ), c(q): a μ, illetve a δ(q) csoportelemhez vezető eddig megtalált legrövidebb út, m(ν): a ν-höz vezető, eddig megtalált legrövidebb út utolsó élének típusa, azaz ha az út utolsó éle

(μ, μ ⊕ α_{j} = ν), akkor j, w(q): a δ(q) csoportelem állapotváltozója, értéke \underline{true}, ha δ(q)-ból, mint a gráf csúcsából még nem

léptünk tovább, különben \underline{false}, z: egy valós értékű segédváltozó.

A dinamikus programozás a Bellman egyenletek kielégítésével adja meg a gráf minden pontjához a legrövidebb utat, az egyenletek mostani alakja, a következő:

c (0) = 0,

c (ν) = min {c (μ) + γ_{j} : μ ⊕ α_{j} = ν}

Az algoritmusban mindig abból a legkisebb c(q) értékkel rendelkező δ(q) csúcsból / csoportelemből lépünk tovább, amelyből ezt még nem tettük meg, mert itt már nem érhető el javulás a nemnegatív költségek miatt.

Az algoritmus:

1 \underline{Begin}

2 c(0) := 0; 3 w(0) :=\underline{true}; 4 \underline{for} k := 1 \underline{to} d − 1 \underline{do}

5  \underline{begin}

6 c(k) := +∞; 7 w(k) :=\underline{true}; 8 \underline{end}; 9 q := 0; 10 \underline{for} k := 0 \underline{to} d − 2 \underline{do}

11  \underline{begin}

12 z := +∞; 13 \underline{for} j := 1 \underline{to} d − 1 \underline{do} 14 \underline{if} c(j) < z \underline{and} w(j) \underline{then}

15  \underline{begin}

16 q := j; 17 z := c(j); 18 \underline{end}; 19 w(q) :=\underline{false}; 20 \underline{for} j = 1 \underline{to} t \underline{do}

21  \underline{begin}

22 ϕ := δ(q) ⊕ α_{j}; 23 \underline{if} c(ϕ) > c(q) + γ_{j} \underline{then}

24  \underline{begin}

25 c(ϕ) := c(q) + γ_{j}; 26 m(ϕ) := j; 27 \underline{end}; 28 \underline{end}; 29 \underline{end}; 30 \underline{end};

Az első 9 sor a változók beállítása, és a kezdeti értékek meghatározása. Utána következik a fő ciklus, ami két másik ciklust tartalmaz. Az első, a 13-diktól a 18-dik sorig kiválasztja azt a csúcsot, ahonnét továbblépünk. A második, a 20-dik sortól, a továbblépés. A fő ciklus d − 1-szer fut le, minden lépésben továbblép egy csúcsból, és aztán abból többször nem lép, ezt azzal tudjuk biztosítani, hogy mindig a legkisebb potenciálértékű csúcsból lépünk tovább. A fő ciklus d − 1-szer, a két belső ciklus d − 1-szer és t-szer fut le. Így az algoritmus lépésszáma: O(d^{2} + dt).

Az algoritmus meghatározta a β-ba vezető legrövidebb utat, ebből ezután meg kell adnunk a csoportfeladat optimális x megoldását. Minden csoportelemhez az algoritmus eltárolta, az oda vezető legrövidebb út utolsó élének típusát, így a következő algoritmussal meghatározhatjuk az x-et.

1 δ := β; 2 \underline{while} δ ≠ 0 \underline{do}

3 \underline{begin}

4 x_{m(δ)} := x_{m(δ)} + 1; 5 δ := δ ⊖ α_{m(δ)}; 6 \underline{end};

2.2. A csoportfeladat optimális megoldásának néhány tulaj-

donsága

Tekintsük újra a csoportfeladatot.

min ∑_{j=1}^{t} γ_{j}x_{j}

\begin{matrix}t \\ ∑ & ⊕ \\ j=1 \end{matrix} α_{j}x_{j} = β

x ∈ ℤ_{+}^{t}

Jelöljük v_{1}, v_{2}, ..., v_{t}-vel az α_{1}, α_{2}, ..., α_{t} elemek rendjét a csoportban. 2.2.1. Tétel. A csoportfeladatnak van olyan x^{∗} optimális megoldása, amelyre

x_{j}^{∗} ≤ v_{j} − 1, j = 1, 2, ..., t.

Bizonyítás: Jelölje z^{∗} az x^{∗} értékhez tartozó optimális célfüggvényértéket. Indirekt tegyük fel, hogy x^{∗} valamely k komponensére: x_{k}^{∗} > v_{k} − 1. Legyen x̄ az a vektor, melynek elemei:

x̄_{j} = \{ \begin{matrix}x_{j}^{∗} & j ≠ k \\ x_{k}^{∗} − v_{k} & j = k \end{matrix}

Legyen z̄ az ehhez az elemhez tartozó célfüggvényérték. Ekkor x̄ ≥ 0, és

\begin{matrix}t \\ ∑ & ⊕ \\ j=1 \end{matrix} α_{j}x̄_{j} = \begin{matrix}t \\ ∑ & ⊕ \\ j=1 \end{matrix} α_{j}x_{j}^{∗} ⊖ α_{k}v_{k} = \begin{matrix}t \\ ∑ & ⊕ \\ j=1 \end{matrix} α_{j}x_{j}^{∗} = β,

azaz x̄ kielégíti a csoportfeladat feltételeit, és

z^{∗} = z̄ + v_{k}γ_{k} ≥ z̄.

Mivel x^{∗} optimális, ezért itt csak egyenlőség lehet, azaz x̄ is optimális megoldása a csoportfeladatnak. □

2.2.2. Tétel. A csoportfeladatnak van olyan x^{∗} optimális megoldása, amelyre

∑_{j=1}^{t} x_{j}^{∗} ≤ d − 1.

Bizonyítás: Tegyük fel indirekt, hogy a csoportfeladat egy tetszőleges megoldására:

∑_{j=1}^{t} x_{j} ≥ d.

Ekkor a gráfban x-nek egy legalább d+1 csúcsot érintő út felel meg, ami azt jelenti, hogy tartalmaz kört. Ha kört elhagyjuk, akkor csökkenhet az út hossza, és így a célfüggvényérték. □

A csoportfeladat az egészértékű programozási feladatnak egy relaxációja, így az optimális megoldás nem biztos, hogy az egészértékű programozási feladatnak is optimális megoldása lesz. Ahhoz, hogy optimális megoldást kapjunk az egészértékű programozási feladatra is, teljesülnie kell a következőnek:

x_{B} = B^{−1}b − B^{−1}Nx_{N} ≥ 0.

2.2.3. Tétel. Jelölje v = (v_{1}, v_{2}, ...v_{t}), N̄ azt a mátrixot, amelyre N̄_{ij} = |(B^{−1}N)_{ij}|. Legyen x^{∗} a csoportfeladat optimális megoldása, amelyre x_{j}^{∗} ≤ v_{j} − 1, (j = 1, 2, ..., t) teljesül. Jelölje e a csupa 1-esből álló t-dimenziós vektort. Ha

B^{−1}b ≥ N̄ (v − e) ,

akkor

B^{−1}b − B^{−1}Nx^{∗} ≥ 0.

Bizonyítás: Legyen y_{i} = |(B^{−1}Nx^{∗})_{i}| , (i = 1, 2, ..., m), ekkor

B^{−1}Nx^{∗} ≤ y ≤ N̄x^{∗} ≤ N̄ (v − e) ≤ B^{−1}b. □

2.2.4. Következmény. Az előző tétel jelölései mellett, ha

B^{−1}b ≥ N̄ (d − 1) e,

akkor

B^{−1}b − B^{−1}Nx^{∗} ≥ 0.

Bizonyítás: Az előző tételből adódik v − e ≤ (d − 1)e miatt. □

2.3. A csoportelméleti módszer felhasználása a korlátozás és

szétválasztás algoritmusában

A korlátozás és szétválasztás algoritmusok azon alapulnak, hogy adva van egy relaxáció, amelyet könnyen, gyorsan meg tudunk oldani, és ennek segítségével szűkítjük a megengedett megoldások halmazát. Pontosabban felbontjuk a megengedett halmazt diszjunkt részekre és a relaxáció segítségével alsó korlátot adunk a célfüggvény értékére az egyes halmazokon. Ennek segítségével lépésről lépésre kizárjuk a megengedett halmaz egy-egy részét és eljutunk az optimális megoldásig.

Jelölje v, mint eddig, a csoportfeladatot meghatározó elemek rendjét.

2.3.1. Definíció. Legyen y ∈ ℤ_{+}^{t}, y < v egy tetszőleges vektor. Ekkor z ∈ ℤ_{+}^{t} az y vektor \underline{folytatása}, ha

\begin{matrix}y ≨ z, \\ z < v. \end{matrix}

Tehát y folytatásai nem egyenlők vele.

Legyen 0 ≤ y < v egy tetszőleges egész vektor, és tekintsük a (2.6)-os csoportfeladatot az x ≥ y plusz feltétel mellett. Legyen ennek optimális megoldása x̄. Ekkor a következő feladatot kell megoldanunk:

\begin{aligned}min & ∑_{j=1}^{t} γ_{j}u_{j} \\ & \begin{matrix}t \\ ∑ & ⊕ \\ j=1 \end{matrix} α_{j}u_{j} = β ⊖ \begin{matrix}t \\ ∑ & ⊕ \\ j=1 \end{matrix} α_{j}y_{j} \\ & u ∈ ℤ_{+}^{t} \end{aligned}  (2.8)

Ennek u^{∗} optimális megoldása megadja az x̄ vektort is, x̄ = u^{∗} + y. Ezután legyen y ≤ w ≤ x̄ egy tetszőleges egész vektor, ekkor ha megoldjuk a csoportfeladatot ((2.6)-ot) az x ≥ w feltétel mellett, akkor az optimális megoldás megint x̄ lesz. Ezért vezessük be a következőt:

2.3.2. Definíció. Legyen egy rögzített y vektor mellett a (2.8)-as feladat optimális megoldása u^{∗}. A 0 ≨ z < v, z ∈ ℤ_{+}^{t} az y vektor \underline{közvetlen folytatása}, ha létezik olyan 1 ≤ k ≤ t index, hogy

z_{j} = \{ \begin{matrix}y_{k} + u_{k}^{∗} + 1 & ha j = k \\ y_{j} & ha j ≠ k. \end{matrix}

Tehát az y vektor közvetlen folytatásai, azok a parciális rendezésben minimális folytatásai, amelyek a csoportfeladat garantáltan más megoldását adják meg, mint y. A definícióban megadott z vektort y k-adik közvetlen folytatásának fogjuk nevezni. Ha

y_{k} + u_{k}^{∗} ≥ v_{k} − 1,

akkor a k-adik közvetlen folytatás nem létezik.

A közvetlen folytatások meghatározásához a (2.8)-as feladatot kell megoldani. Ehhez nincs szükség a csoportfeladatot megoldó algoritmust újra és újra lefuttatni, mert az minden jobboldalra meghatározza a megoldást. Ez még inkább felgyorsítja a megoldást.

Az algoritmusban a megoldások szerinti részhalmazokat az y folytatásai adják. Tehát a halmazt legfeljebb t részre bontjuk fel, az egyes részekben y k-adik közvetlen folytatása, (ha létezik) és annak folytatásai vannak.

Legyen S az a halmaz, amelybe y és folytatásai tartoznak. y-t az S halmaz gyökérpontjának fogjuk nevezni.

Az algoritmus jelölései: L: a felbontandó halmazok listája, amelyeket a gyökérpontjukkal adunk meg, h(y): az y gyökérpontú halmazhoz tartozó alsó becslés, azaz a (2.8)-as feladat optimális célfügg-

vényértéke, Opt(y): az y vektorral definiált (2.8)-as feladat optimális megoldásainak halmaza, f: az eddig megtalált legjobb megengedett megoldás célfüggvényértéke, g: segédváltozó. Az eljárásban feltételezzük, hogy a csoportfeladatot már megoldottuk, és volt optimális megoldása, de az nem volt megoldása az egészértékű programozási feladatnak. Ezért a h(y) értékeket és a hozzájuk tartozó optimális megoldásokat ki tudjuk olvasni a dinamikus programozás által készített táblázatból.

Az algoritmus:

1 \underline{Begin}

2 L := {0}; 3 f := ∞; 4 \underline{while} L ≠ ∅ \underline{do}

5  \underline{begin}

6 kiválasztunk egy y elemet L-ből; 7 L := L − y; 8 megoldjuk a (2.8)-as feladatot y-nal; 9 \underline{while} Opt(y) ≠ ∅ \underline{do}

10  \underline{begin}

11 kiválasztunk egy u^{∗} elemet Opt(y)-ból; 12 Opt(y) := Opt(y) − u^{∗}; 13 \underline{if} B^{−1}b ≥ B^{−1}N(y + u^{∗}) \underline{then}

14  \underline{begin}

15 g := c_{B}^{⊤}B^{−1}b + (c_{N}^{⊤} − c_{B}^{⊤}B^{−1}N)(y + u^{∗});

16 \underline{if} g < f \underline{then} f := g;

17  \underline{end}
18  \underline{else}
19  \underline{begin}

20 \underline{for} j := 1 \underline{to} t \underline{do}

21  \underline{begin}

22 \underline{if} (∃y k-dik közvetlen folytatása) \underline{then} z := y k-dik közvetlen folytatása;

23 \underline{if} h(z) < f \underline{then} L := L + z;

24 \underline{end};

25 \underline{end};

26 \underline{end};

27 \underline{end};

28 \underline{end};

2.3.3. Tétel. Ez az algoritmus véges.

Bizonyítás: Tegyük fel indirekt, hogy az algoritmus nem véges. Ez csak úgy fordulhat elő, ha az L lista nem ürül ki. Minden L-beli elem egy előzőleg már L-be kerülő elem folytatása, és kezdetben csak a 0 vektor van L-ben. Ezért létezik egy egész vektorokból álló {y_{i}} végtelen sorozat úgy, hogy mind a 0 folytatása, és kisebb, mint a v vektor, azaz

0 = y_{1} ≤ y_{2} ≤ …
y_{i} < v i = 1, 2, …

Ez viszont ellentmondás, mert csak véges sok olyan ℤ_{+}^{t}-beli vektor van, ami a v vektornál kisebb. □

A korlátozás és szétválasztás módszer valamilyen módon végignézi az összes megoldást, ezért be kell látnunk, hogy az algoritmus nem hagy ki egy szóba jöhető vektort sem. Azt kell bizonyítanunk, hogy egy tetszőleges w ∈ ℤ_{+}^{t}, w < v vektor minden (2.8)-as feladat által adott megoldását megvizsgálja.

2.3.4. Tétel. Az algoritmus minden w ∈ ℤ_{+}^{t}, w < v vektorhoz tartozó (2.8)-as feladat egy optimális megoldásából származó w + u^{∗} vektort megvizsgál, feltéve, hogy a csoportfeladatnak van optimális megoldása.

Bizonyítás: Legyen a csoportfeladat egy optimális megoldása x^{∗}. Ekkor az

u_{j} = \{ \begin{matrix}x_{j}^{∗} − w_{j} + v_{j} & ha x_{j}^{∗} < w_{j} \\ x_{j}^{∗} − w_{j} & ha x_{j}^{∗} ≥ w_{j} \end{matrix}

választással a (2.8)-as feladatnak egy megengedett megoldását kapjuk, így annak létezik optimális megoldása is. Indirekt tegyük fel, hogy egy, w vektorhoz tartozó w + u^{∗} vektort nem vizsgált meg az algoritmus. Ez csak úgy lehet, hogy w nem került be az L listába. Kezdetben csak a 0 vektor van a listában, ennek w folytatása, a választása miatt. Legyen ȳ az L listából utoljára kikerülő vektort, amelynek w a folytatása. Ha w nem közvetlen folytatása az ȳ vektornak, és nem folytatása ȳ valamely közvetlen folytatásának, akkor w vektort az algoritmus 13-dik sorában vizsgálta, amikor y az ȳ értéket vette fel. Ezek után tegyük fel, hogy ȳ-nak van olyan z̄ közvetlen folytatása, amelyre z̄ ≤ w. Mivel z̄ nem került be az L listába, ezért az algoritmus 23-dik sorában a feltétel nem teljesült, azaz az ȳ-nal felírt (2.8)-as feladat megoldása nem adott jobb megoldását az egészértékű programozási feladatnak, mint az algoritmus által előbb megvizsgált vektorok. □

Az egészértékű programozási feladat, így a következőképpen oldható meg. Először megoldjuk a feladat lineáris programozási relaxáltját, ha ekkor egész megoldást kapunk, akkor kész. Ha nem, akkor ez ad nekünk egy optimális bázist, amelynek segítségével fel tudjuk írni a csoportfeladatot. Ha a csoportfeladatnak létezik megoldása, és az optimális, akkor megint kész vagyunk, ha nem akkor az előző algoritmust lefuttatva kapunk megoldást. Azaz az egészértékű programozási feladat megoldásának menete a következő:

1 \underline{Begin}

2 Az egészértékű programozási feladat LP-relaxációjának megoldása;

3 a csoportfeladat felállítása;

4 \underline{if} (∃ a csoportfeladatnak optimális megoldása) \underline{then} x := egy optimális megoldás;

5 \underline{if} B^{−1}b ≱ B^{−1}Nx \underline{then} az előző algoritmus lefuttatása;

6 \underline{end};

2.4. A csoportelméleti feladat alkalmazása az (1.2)-ben adott

feladatra

A feladat a következő:

Ax = ab : x ∈ ℤ_{+}^{10}, a ∈ ℤ_{+}, a ≠ 0

ahol

A = ( \begin{matrix}−1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & −1 & 1 \\ −1 & 1 & 1 & −1 & 0 & 0 & 1 & −1 & −1 & 1 \\ 1 & −1 & −1 & 1 & −1 & 1 & 0 & 0 & 2 & −2 \\ 1 & −1 & 0 & 0 & 1 & −1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & −1 & −1 & 1 & −1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & −1 & 0 & 0 \end{matrix} ) , b = ( \begin{matrix}−1 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \\ 0 \end{matrix} ) .

és a célfüggvény:

c = ( 1 1 1 1 1 1 1 1 1 1 )^{⊤} .

Ez azonban nagyon sok feladat, így nehéz lenne megoldani, de átírható egy ekvivalens alakba, ahol csak egy egyenlőségrendszerünk lesz. Vigyük át a b jobboldali vektorunkat a bal oldalra. Így az a tekinthető mint a −b-hez tartozó változó. Ekkor viszont fel kell még tennünk, hogy ez a változó pozitív, ami az egészértékűség miatt ekvivalens azzal, hogy a ≥ 1.

Így a következő feladathoz jutunk:

min (c, 1)^{⊤} x

( \begin{matrix}−1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & −1 & 1 & 1 \\ −1 & 1 & 1 & −1 & 0 & 0 & 1 & −1 & −1 & 1 & 0 \\ 1 & −1 & −1 & 1 & −1 & 1 & 0 & 0 & 2 & −2 & 0 \\ 1 & −1 & 0 & 0 & 1 & −1 & 0 & 0 & 0 & 0 & −1 \\ 0 & 0 & 1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & −1 \\ 0 & 0 & 0 & 0 & 1 & −1 & −1 & 1 & −1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & −1 & 0 & 0 & 0 \end{matrix} ) x = ( \begin{matrix}0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix} )

x_{11} ≥ 1 x ∈ ℤ_{+}^{11}

Itt (c, 1) a csupa egyesből álló 11 dimenziós vektor.

A csoportelméleti módszert úgy építettük fel, hogy a korlátozások egyenlőségek, ezért vezessünk be egy kiegészítő változót, legyen ez x_{12}, olyan, hogy

x_{11} ≥ 1 ⇔ −x_{11} + x_{12} = −1, x_{12} ≥ 0

Ekkor a feladatunk a következő alakba írható:

min ĉ^{⊤}x

Â = ( \begin{matrix}−1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & −1 & 1 & 1 & 0 \\ −1 & 1 & 1 & −1 & 0 & 0 & 1 & −1 & −1 & 1 & 0 & 0 \\ 1 & −1 & −1 & 1 & −1 & 1 & 0 & 0 & 2 & −2 & 0 & 0 \\ 1 & −1 & 0 & 0 & 1 & −1 & 0 & 0 & 0 & 0 & −1 & 0 \\ 0 & 0 & 1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & −1 & 0 \\ 0 & 0 & 0 & 0 & 1 & −1 & −1 & 1 & −1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & −1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & −1 & 1 \end{matrix} ) x = b̂ = ( \begin{matrix}0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ −1 \end{matrix} )

x ∈ ℤ_{+}^{12}

Itt ĉ a csupa egyesből álló 12 dimenziós vektor.

A csoportelméleti módszer alkalmazásához kell még, hogy a mátrixunk teljes sorrangú. Az Â mátrix rangja 5, azaz el kell hagynunk 3 sorát, amely lineárisan függ a megmaradó 5-től. Jelöljük az Â mátrix sorait a^{i}-vel i = 1, ..., 8. Ekkor

a^{1} = −a^{4} + a^{6} + a^{7}
a^{2} = −a^{4} + a^{5} + a^{6} + 2a^{7}
a^{3} = a^{4} − a^{5} − 2a^{6} − 2a^{7}.

Így a következő mátrixhoz és hozzá tartozó jobboldali vektorhoz jutunk:

Ā := ( \begin{matrix}1 & −1 & 0 & 0 & 1 & −1 & 0 & 0 & 0 & 0 & −1 & 0 \\ 0 & 0 & 1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & −1 & 0 \\ 0 & 0 & 0 & 0 & 1 & −1 & −1 & 1 & −1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & −1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & −1 & 1 \end{matrix} ) , b̄ = ( \begin{matrix}0 \\ 0 \\ 0 \\ 0 \\ −1 \end{matrix} ) .

Ekkor a feladatunk:

\begin{aligned}min & ĉ^{⊤}x \\ & Āx = b̄ \\ & x ∈ ℤ_{+}^{12} \end{aligned}

A csoportfeladat felállításához szükségünk lesz egy optimális bázisra, az első, a harmadik, a hetedik, a kilencedik, és a tizenegyedik, (azaz a b-nek megfelelő,) oszlopokból álló vektorok megfelelnek, azaz

B := ( \begin{matrix}1 & 0 & 0 & 0 & −1 \\ 0 & 1 & 0 & 0 & −1 \\ 0 & 0 & −1 & −1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & −1 \end{matrix} ) ,

ekkor

B^{−1} = ( \begin{matrix}1 & 0 & 0 & 0 & −1 \\ 0 & 1 & 0 & 0 & −1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & −1 & −1 & 0 \\ 0 & 0 & 0 & 0 & −1 \end{matrix} ) , N = ( \begin{matrix}−1 & 0 & 1 & −1 & 0 & 0 & 0 \\ 0 & −1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & −1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & −1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} ) .

A bázis optimális, mert

c_{N}^{⊤} − c_{B}^{⊤}B^{−1}N = ( 2 2 1 1 2 2 4 ) ≥ ( 0 0 0 0 0 0 0 ) .

Meg kell határoznunk a B bázis Smith-féle normálalakját is.

P = B^{−1} = ( \begin{matrix}1 & 0 & 0 & 0 & −1 \\ 0 & 1 & 0 & 0 & −1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & −1 & −1 & 0 \\ 0 & 0 & 0 & 0 & −1 \end{matrix} )

Ez megfelel, mert P -vel balról megszorozva egységmátrixot, azaz diagonális mátrixot kapunk, és P determinánsa -1. Ezért a ξ = ξ^{−1} = E, ahol E a (5 × 5)-ös egységmátrix. Így a csoportfeladat:

min ( 2 2 1 1 2 2 4 ) x + 3

ξ^{−1}P Nx = ( \begin{matrix}−1 & 0 & 1 & −1 & 0 & 0 & −1 \\ 0 & −1 & 0 & 0 & 0 & 0 & −1 \\ 0 & 0 & 0 & 0 & −1 & 0 & 0 \\ 0 & 0 & −1 & 1 & 0 & −1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & −1 \end{matrix} ) x ≡ ξ^{−1}P b̄ = ( \begin{matrix}1 \\ 1 \\ 0 \\ 0 \\ 1 \end{matrix} ) (mod 1)

x ∈ ℤ_{+}^{7}

Mivel a B mátrix determinánsa -1 volt, ezért a kongruencia (mod 1), és így minden egész x vektorra teljesülni fog. Ezek közül a minimális a

x_{N} = ( 0 0 0 0 0 0 0 )^{⊤} .

Ekkor

x_{B} = B^{−1}b − B^{−1}Nx_{N} = ( \begin{matrix}1 \\ 1 \\ 0 \\ 0 \\ 1 \end{matrix} ) ≥ 0

és így az eredeti feladat optimális megoldása

x = ( 1 0 1 0 0 0 0 0 0 0 1 0 ) .

Ez azt jelenti, hogy a következő két elemi reakcióból áll elő a kívánt reakció optimálisan:

C_{4}H_{10} + λ → C_{4}H_{8}λ + H_{2}
C_{4}H_{8}λ → C_{4}H_{8} + λ.

(A megoldásnál a számolásokat MATLAB-bal végeztem.) A feladat lineáris programozási relaxáltját a MAPLEV simplex csomagjának minimum programjával megoldva is ugyanezt az egész megoldást kapjuk.

A Hilbert bázis meghatározása

Ebben a fejezetben a következő alakú egészértékű feladattal fogunk foglalkozni:

\begin{matrix}Ax = 0 \\ x ≥ 0 \\ x ∈ ℤ^{n} \end{matrix} \} M

ahol A ∈ ℤ^{m×n}, b ∈ ℤ^{m}. Ennek a rendszernek a megoldásai egy kúpot alkotnak, az egész megoldásait pedig generálják a nem nulla minimális elemek.

3.0.1. Definíció. Az M rendszer egész megoldásainak a következő rendezés szerinti minimális elemeinek véges halmazát, H(M)-t Hilbert bázisnak nevezzük. A rendezés:

(x_{1}, …, x_{n}) ≤ (y_{1}, …, y_{n}) ⇔ ∀i 1 ≤ i ≤ n, x_{i} ≤ y_{i}.

Ekkor az M rendszer minden megoldása előáll a H(M) Hilbert bázis elemeinek valamilyen pozitív, egész együtthatós lineáris kombinációjaként.

Vezessük be a következő jelöléseket:

∥M∥_{1} = sup_{x∈H(M)} ∥x∥_{1} , ∥A∥_{1,∞} = sup_{i=1,...,m} (∑_{j=1}^{n} |a_{ij}|) ,

ahol ∥x∥_{1} = ∑_{i=1}^{n} |x_{i}|, továbbá legyen r := rang(A).

3.0.2. Tétel.

∥M∥_{1} ≤ (1 + ∥A∥_{1,∞})^{r}

Bizonyítás: Az Ax = b egyenletrendszerből kiválaszthatunk r lineárisan független sort, ezért feltehető, hogy az A mátrixunk r sorból áll. Legyen x = (x_{1}, …, x_{n}) ∈ M, az M egy nem nulla eleme, p := ∥x∥_{1}, és e_{i}, (i = 1, …, n) az a vektor, amelynek az i-edik koordinátája 1, a többi 0. Minden y ∈ ℝ^{n} vektorra, jelölje C_{y} azt az egységkockát, amelyre

z ∈ C_{y} ⇔ z = y + ∑_{i=1}^{n} λ_{i}e_{i}, λ_{i} ∈ [0, 1] ∀i = 1, …, n.

Definiálunk y^{0}, …, y^{p} ∈ ℤ_{+}^{n} és z^{0}, …, z^{p} ∈ ℝ^{n} vektorokat úgy, hogy

y^{0} = 0 < y^{1} < ⋯ < y^{p} = x
∀k ∈ [0, p − 1] , ∃j y^{k+1} = y^{k} + e_{j}
∀k ∈ [0, p] ∃z^{k} ∈ C_{y^{k}} ∩ [0, x]

Azaz lépésenként valamelyik koordinátát eggyel növelve haladunk 0-ból x-be úgy, hogy közben a megfelelő egységkocka messe a [0, x] szakaszt. (Ezekből a metszetekből választjuk a z^{k}-kat) Tudunk ilyen vektorokat választani, mert tegyük fel, hogy y^{k}-kat és z^{k}-kat ismerjük valamilyen k-ig (0 ≤ k ≤ p − 1). (x^{0} = z^{0} = 0) Ekkor, mivel z^{k} ∈ [0, x] ∩ C_{y^{k}}, ezért ∃λ : 0 ≤ λ ≤ 1, hogy z^{k} felírható

z^{k} = λ ∑_{i=1}^{n} x_{i}e_{i}

alakban, úgy

∀i = 1, …, n y_{i}^{k} ≤ λx_{i} ≤ y_{i}^{k} + 1.

Legyen

λ_{k} = min_{i:x_{i}≠0} \frac{y_{i}^{k} + 1}{x_{i}}

Legyen j az az index, amelyre λ_{k} = \frac{y_{j}^{k}+1}{x_{j}}. Ekkor legyen

z^{k+1} = λ_{k} ∑_{i=1}^{n} x_{i}e_{i}, y^{k+1} = y^{k} + e_{j}.

Már csak azt kell belátnunk, hogy z^{k+1} ∈ C_{y^{k+1}}. λ_{k} választása szerint

∀i = 1, …, n : y_{i}^{k+1} ≤ λ_{k}x_{i} ≤ y_{i}^{k+1} + 1,

azaz z^{k+1} ∈ C_{y^{k+1}} teljesül. Ha k = p − 1 akkor y^{p} = x, mert y^{p} ≤ x és ∥y^{p}∥_{1} = p = ∥x∥_{1}. Ebből az is következik, hogy z^{p} = x. Legyen most ȳ^{k} = z^{k} − y^{k}. Ekkor

∀i = 1, …, n 0 ≤ ȳ_{i}^{k} ≤ 1.

Jelölje (Ay^{k})_{i} az Ay^{k} i-edik koordinátáját. Most Az^{k} = 0, mert z^{k} a [0, x] szakaszon van, ezért

|(Ay^{k})_{i}| = |(Az^{k})_{i} − (Aȳ^{k})_{i}| = |(Aȳ^{k})_{i}| = |∑_{j=1}^{n} a_{ij}ȳ_{j}^{k}| ≤ ∑_{j=1}^{n} |a_{ij}| .

Mivel |(Ay^{k})_{i}| nemnegatív egész, ezért összesen ∑_{j} |a_{ij}| + 1 különböző értéket vehet fel. (0, 1, …, ∑_{j} |a_{ij}| értékeket veheti fel.) Ay^{k} egy r-dimenziós vektor, így legfeljebb

(1 + sup_{i} ∑_{j} |a_{ij}|)^{r}

különböző értéket vehet fel. Tegyük fel, hogy p > (1 + sup_{i} ∑_{j} |a_{ij}|)^{r}. Ekkor léteznek i, j : i > j > 0 indexek, hogy Ay^{i} = Ay^{j}. Legyen

z = y^{i} − y^{j}

Ekkor Az = 0, és 0 < z < x miatt z ∈ M, amiből következik, az ellentmondás, hogy x ∉ H(M). □

3.1. Contejean-Devie algoritmusa

E.Contejean és H.Devie algoritmusához nincs szükség H(M) korlátjára. Az algoritmus elve a következő: rendezzük ℤ_{+}^{n}-t a már definiált rendezés szerint, így kapunk egy körmentes, irányított gráfot, amelynek a gyökere 0. Nevezzük el a gráfot DAG-nak (directed acyclic graph). Az algoritmus ebben a gráfban fog keresni, mégpedig a következők szerint: Induljunk ki a nullából. Csak olyan x csúcsra lépünk tovább, amely teljesíti, hogy x minden y szülőjére A (x − y) ≠ 0, és x csak olyan x + e_{j} gyerekeire lépünk tovább, amelyekre teljesül, hogy ⟨Ax, Ae_{j}⟩ ≤ 0.

Vizsgáljuk meg, miért így választjuk a csúcsokat. 3.1.1. Lemma. Elég azokat az x ≥ 0 csúcsokat vizsgálni, amelyekre:

A (x − y) ≠ 0

az x minden y ősére. Bizonyítás: Tegyük fel indirekt, hogy létezik x-nek y őse, hogy A (x − y) = 0. Azaz

∃y : y ≤ x, Ax = Ay

Ha x megoldás, akkor y is az és y ≤ x, ami ellentmond annak, hogy x minimális megoldás. Így x nem eleme a Hilbert bázisnak. Ha x nem megoldás, de létezik z ≥ 0, z ≠ 0 vektor, hogy x+z megoldás, akkor A(x+z) = A(y +z) miatt y + z is megoldás. y + z őse x + z-nek, ezért csak y + z lehet a Hilbert bázis eleme. Azaz x egyik leszármazottja sem lehet tagja a Hilbert bázisnak. □

3.1.2. Lemma. Legyen x ≥ 0, x ≠ 0. Elég x azon x + e_{j} (j ∈ 1, 2, ..., n) gyermekeit vizsgálni, amelyekre

⟨Ax, Ae_{j}⟩ < 0.

Bizonyítás: Azt kell belátnunk, hogy minden, a rendezés szerint, minimális megoldásba el lehet jutni ilyen úton.

Tegyük fel, hogy y minimális megoldás, azaz a Hilbert-bázis eleme. Ekkor ∀0 ≤ x ≤ y ∃z ≥ 0 : x + z = y. Mivel Ay = 0, ezért

0 = ⟨Ay, Ax⟩ = ⟨A (x + z) , Ax⟩ =
= ∥Ax∥^{2} + ⟨Az, Ax⟩ =
= ∥Ax∥^{2} + ∑_{j=0}^{n} z_{j}⟨Ae_{j}, Ax⟩

Mivel y minimális megoldás, ezért Ax ≠ 0, azaz

∥Ax∥ > 0.

A z-ről feltettük, hogy minden koordinátája nem negatív, ∀z_{j} ≥ 0, ezért

∑_{j=1}^{n} z_{j}⟨Ae_{j}, Ax⟩ < 0.

Ebből következik, hogy létezik egy j ∈ {1, ..., n} index, hogy

⟨Ae_{j}, Ax⟩ < 0.

Így az e_{i} (i = 1, ...n) vektorokból kiindulva, minden megoldáshoz meg tudunk konstruálni egy ilyen utat. Ezt az utat az algoritmus vizsgálni fogja, és így eljut a megoldáshoz. □

Ha nem vizsgálunk többször egy csúcsot a DAG-ban, és csak a rendezés szerinti legkisebb megoldásokat keressük, akkor megkapjuk H(M)-et. Ez az algoritmus jól működik a gyakorlatban, de időigényes, ha H(M) elemeinek nagy a normájuk.

3.2. A Contejean-Devie algoritmus módosítása a (3.0.2)-es té-

tel alapján

Az előbbi algoritmus futását lerövidíthetjük, ha figyeljük azt is, mekkora a választandó csúcs normája. A H(M) normájára adott egy felső becslést a (3.0.2)-es tétel. Ez alapján adódik a következő tétel:

3.2.1. Tétel. Elég x azon x + e_{l} gyermekeit vizsgálnunk, amelyre az A(x + e_{l}) i-edik koordinátája − ∑_{j=1}^{n} a_{ij}^{−} és ∑_{j=1}^{n} a_{ij}^{+} közé esik.

Bizonyítás: Legyen egy a ∈ ℝ szám pozitív része: a^{+} := max{0, a}, illetve negatív része: a^{−} := max{0, −a}. Azaz mind a pozitív, mind a negatív rész pozitív szám, emellett igaz a következő:

a = a^{+} − a^{−},
|a| = a^{+} + a^{−}.

A (3.0.2)-es tétel bizonyításának alapján megbecsülhetjük (Ay^{k})_{i}-t:

(Ay^{k})_{i} = (Az^{k})_{i} − (Aȳ^{k})_{i} = (Aȳ^{k})_{i} = ∑_{j=1}^{n} a_{ij}ȳ_{j}^{k} = ∑_{j=1}^{n} a_{ij}^{+}ȳ_{j}^{k} − ∑_{j=1}^{n} a_{ij}^{−}ȳ_{j}^{k}.

Mivel 0 ≤ ȳ_{j}^{k} ≤ 1, és a_{ij}^{−}, a_{ij}^{+} ≥ 0 (∀i, j -re), ezért:

∑_{j=1}^{n} a_{ij}^{+}ȳ_{j}^{k} − ∑_{j=1}^{n} a_{ij}^{−}ȳ_{j}^{k} ≤ ∑_{j=1}^{n} a_{ij}^{+}ȳ_{j}^{k} ≤ ∑_{j=1}^{n} a_{ij}^{+}

és

∑_{j=1}^{n} a_{ij}^{+}ȳ_{j}^{k} − ∑_{j=1}^{n} a_{ij}^{−}ȳ_{j}^{k} ≥ − ∑_{j=1}^{n} a_{ij}^{−}ȳ_{j}^{k} ≥ − ∑_{j=1}^{n} a_{ij}^{−},

így a következő becslésből következik a tétel:

− ∑_{j=1}^{n} a_{ij}^{−} ≤ (Ay^{k})_{i} ≤ ∑_{j=1}^{n} a_{ij}^{+}.

□

Ezek alapján felírhatunk egy elméleti, szélességi keresésen alapuló algoritmust. Legyen az X a vizsgálandó csúcsok halmaza, a DAG valamelyik szintjén.

Az algoritmus:

1 \underline{Begin}

2 X := {e_{k} : k = 1, …, n}; 3 H (M) := {e_{k} : k = 1, …, n; Ae_{k} = 0}; 4 X := X \ H(M); 5 \underline{while} X ≠ 0 \underline{do}

6  \underline{begin}
7  \begin{aligned}X := \{x + e_{k} : & x ∈ X , k = 1, …, n \\ & ⟨Ax, Ae_{k}⟩ < 0 \\ & Ax ≠ Ay : 0 ≠ y ≤ x \\ & − ∑_{j=1}^{n} a_{ij}^{−} ≤ A (x + e_{k}) ≤ ∑_{j=1}^{n} a_{ij}^{+}\}; \end{aligned}

8 H (M) := H (M) ∪ {x ∈ X : Ax = 0}; 9 X := X \ {x ∈ X : Ax = 0}; 10 \underline{end}; 11 \underline{end};

Az algoritmus minden lépésében egy szintjét vizsgáljuk a DAG-nak, azokat a vektorokat, amelyek 1-es normája k.(ha a k-adik szinten vagyunk.) Az adott szinten viszont, csak azokat a vektorokat vizsgálja, amelyek megfelelnek a választási szabályoknak, és így sokat kizár, ami nem lehet tagja a Hilbert bázisnak.

3.3. A Hilbert bázis meghatározása az (1.2)-ben adott fela-

datra

A feladatunk a következő:

( \begin{matrix}−1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & −1 & 1 & 1 \\ −1 & 1 & 1 & −1 & 0 & 0 & 1 & −1 & −1 & 1 & 0 \\ 1 & −1 & −1 & 1 & −1 & 1 & 0 & 0 & 2 & −2 & 0 \\ 1 & −1 & 0 & 0 & 1 & −1 & 0 & 0 & 0 & 0 & −1 \\ 0 & 0 & 1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & −1 \\ 0 & 0 & 0 & 0 & 1 & −1 & −1 & 1 & −1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & −1 & 0 & 0 & 0 \end{matrix} ) x = ( \begin{matrix}0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix} )

x_{11} ≥ 1
x ∈ ℤ_{+}^{11}

Tekintsünk el egy kicsit az x_{11} ≥ 1 feltételtől. Ekkor x_{11} = 0, ami azt mutatja, hogy az adott reakciók vektoraiból a nullát állítjuk elő, azaz az így kapott megoldások okoznak köröket a reakció útvonalban. Így elég az algoritmussal azokat a vektorokat vizsgálni, ahol x_{11} ≥ 1.

Az 1.fejezetben megadott megoldásból a feladat általános megoldása a következő:

(|a − c|_{+} + b_{1}, |a − c|_{−} + b_{1}, a + b_{2}, b_{2}, |c|_{+} + b_{3}, |c|_{−} + b_{3}, b_{4}, b_{4}, |c|_{+} + b_{5}, |c|_{−} + b_{5}, a)^{⊤} .

(a nemnegatív egész, c egész.) A b_{i}, (i = 1, …, 5) azoknak a triviális köröknek felelnek meg, amikor az egyes reakciók oda, és vissza irányban is végbemennek. Ezért ezeket el is hagyhatjuk, hiszen a parciális rendezés szerinti legkisebb megoldásokat keressük. Ha a = 0, akkor megkapjuk a nem triviális köröket:

|−c|_{+} |−c|_{−} 0 0 |c|_{+} |c|_{−} 0 0 |c|_{+} |c|_{−} 0
c > 0  0  1  0 0 1  0 0 0 1  0 0
c < 0  1  0  0 0 0  1 0 0 0  1 0

azaz az (1 ←, 3 →, 5 →) és az (1 →, 3 ←, 5 ←) reakciók köröket alkotnak.

Ezek után tegyük fel, hogy a ≥ 1. Ekkor két eset lehet: a − c > 0 és 0 < a ≤ c, a parciális rendezés szerinti legkisebb megoldások ekkor:

|a − c|_{+} |a − c|_{−} a 0 |c|_{+} |c|_{−} 0 0 |c|_{+} |c|_{−} a
a − c > 0  1  0  1 0 0  0 0 0 0  0 1
0 < a ≤ c  0  0  1 0 1  0 0 0 1  0 1

Minden más megoldás előáll ezeknek a vektoroknak nemnegatív, egész lineáris kombinációjaként. Nézzük meg az 1.fejezetben kapott megoldásokat. Ezekből kettőt megkaptunk most is, így ezeknél triviális.

Az (1 →, 2 →, 3 →; 5 →) a kapott két megoldás összege, azaz:

1 0 1 0 0 0 0 0 0 0 1
+ 0 0 1 0 1 0 0 0 1 0 1
1 0 2 0 1 0 0 0 1 0 2

Ebből a felírásból kiderül viszont, hogy a másik két megoldás tartalmaz kört, hiszen egyik sem állítható elő az előzőleg megkapott megoldások lineáris kombinációjaként, csak ha olyat veszünk hozzá, ami kört okoz.

1 0 1 0 0 0 0 0 0 0 1
+ 1 0 0 0 0 1 0 0 0 1 0
2 0 1 0 0 1 0 0 0 1 1
0 0 1 0 1 0 0 0 1 0 1
+ 0 1 0 0 1 0 0 0 1 0 0
0 1 1 0 2 0 0 0 2 0 1

Ez azt jelenti, hogy összesen 3 reakció útvonal van, (1 →, 2 →), (2 →, 3 →, 5 →), és ennek a kettőnek az összege.

Futtassuk le az algoritmust úgy a feladatra, hogy elhagyjuk x_{11} ≥ 1 feltételt, és megengedjük, hogy nulla legyen. Ekkor megkapjuk azokat a vektorokat amikhez az előbb eljutottunk, és azokhoz amik köröket okoznak. Azaz a Hilbert bázis:

( 1 1 0 0 0 0 0 0 0 0 0 )^{⊤}
( 0 0 1 1 0 0 0 0 0 0 0 )^{⊤}
( 0 0 0 0 1 1 0 0 0 0 0 )^{⊤}
( 0 0 0 0 0 0 1 1 0 0 0 )^{⊤}
( 0 0 0 0 0 0 0 0 1 1 0 )^{⊤}
( 0 1 0 0 1 0 0 0 1 0 0 )^{⊤}
( 1 0 0 0 0 1 0 0 0 1 0 )^{⊤}
( 1 0 1 0 0 0 0 0 0 0 1 )^{⊤}

( 0 0 1 0 1 0 0 0 1 0 1 )^{⊤}

Összehasonlításképpen az algoritmus a második szinten 11^{2} vektor helyett, csak 26-ot vizsgál meg, a harmadik szinten 11^{3} vektor helyett, csak 34-et, a negyedik szinten 11^{4} vektor helyett 36-ot.

(Ha csak e_{11}-ből indítjuk, akkor is eljut az algoritmus a Hilbert bázis 2 eleméhez, és így még kevesebb vektort vizsgál szintenként, például: a harmadik szinten 9-et, a negyediken 13-at, az ötödiken 9-et.)

(Az elméleti algoritmus lépéseinél a számolásokat MATLAB-bal végeztem.)

Irodalomjegyzék

[1] Vizvári Béla: Egészértékű programozás, Tankönyvkiadó, Budapest, 1989

[2] A.Schrijver: Theory of Linear and Integer Programming, Wiley, 1986

[3] L.T. Fan, B.Bertók, F.Friedler: A graph-theoretic method to identify candidate mechanisms for deriving the rate law of a catalytic reaction, Computers & Chemistry, 2001

[4] L.Pottier: Minimal solution of linear diophantine systems: bounds and algorithms, S.A.F.I.R Project, Institut National de Recherche en Informatique et Automatique, jan. 1991 http://www-sop.inria.fr/lemme/Loic.Pottier/rta91.ps

[5] Kovács Krisztián, Vizvári Béla, Riedel Miklós, Tóth János: Decomposition of the permanganate/oxalic acid overall reaction to elementary steps based on integer programming theory, Physical Chemistry Chemical Physics, (megjelenés alatt)

[6] E.Contejean and H.Devie: Solving Systems of linear diophantine equations UNIF’89, proc. of the third international Workshop on unification,Lambrecht, RFA 89.

[7] Frank András: Operációkutátás előadásjegyzet, http://www.cs.elte.hu/˜ frank/jegyzet/ulinp.ps

[8] Papp Dávid: Bruttó reakciók felbontása diszkrét matematikai eszközökkel, TDK dolgozat, konzulens: Dr. Tóth János egyetemi docens, 2003