A FOLYAMAT- HÁLÓZATSZINTÉZIS FELADAT KITERJESZTÉSEI

A FOLYAMATHÁLÓZATSZINTÉZIS FELADAT KITERJESZTÉSEI

Ph.D. értekezés

Varga József

7pPDYH]HW 'U)ULHGOHU)HUHQF

0 V]DNLLQIRUPDWLNDLDONDOPD]iVRN doktori program

Nagy rendszerek tervezése és irányítása alprogram

Veszprémi Egyetem Mérnöki Kar Számítástudomány Alkalmazása Tanszék

Veszprém 2000

A folyamat-hálózatszintézis feladat kiterjesztései

1. A FOLYAMAT-HÁLÓZATSZINTÉZIS FELADAT KITERJESZTÉSEI Értekezés doktori (PhD) fokozat elnyerése érdekében a Veszprémi Egyetem 0 V]DNLLQIRUPDWLNDLDONDOPD]iVRNSURJUDPMD0,MHO DOSURJUDPMiKR] tartozóan. Írta: Varga József

A jelölt a doktori szigorlaton .......... pontot ért el. Veszprém, ............................................ a Szigorlati Bizottság elnöke Az értekezést bírálóként elfogadásra javaslom (igen/nem). (OV EtUiOy Dr. .........................................

igen / nem

........................................ aláírás

igen / nem

........................................ aláírás

igen / nem

........................................ aláírás

Második bíráló: Dr. .........................................

Esetleg harmadik bíráló: Dr. .........................................

A jelölt az értekezés nyilvános vitáján .......... pontot ért el. $IHQWLHNDODSMiQDGRNWRULRNOHYpOPLQ VtWpVH Veszprém, ............................................ a bíráló bizottság elnöke

2

Tartalomjegyzék

2. Tartalomjegyzék

1.

A FOLYAMAT-HÁLÓZATSZINTÉZIS FELADAT KITERJESZTÉSEI

2

2.

TARTALOMJEGYZÉK

3

3.

KÖSZÖNETNYILVÁNÍTÁS

5

4.

TARTALMI ÖSSZEFOGLALÓ

6

5.

EXTENSIONS OF PROCESS NETWORK SYNTHESIS (CONTENTS)

7

EXTENSIONEN DER PRODUKTIONSNETZWERKSYNTHESE (INHALT)

8

7.

BEVEZETÉS

9

8.

IRODALMI ÁTTEKINTÉS

6.

12

8.1. Folyamat-hálózatszintézis feladatot megoldó általános módszerek

12

8.2. Hulladékkezeléssel integrált folyamat-hálózatszintézis

13

8.3. Integrált folyamat-hálózat- és irányítórendszer tervezés

14

8.4. Szakaszosan folytonos költségfüggvény alkalmazása folyamat-hálózatszintézis feladatban

15

8.5. )RO\DPDWKiOy]DWV]LQWp]LVIHODGDWPHJROGiVDSiUKX]DPRVP N|GpVLHOY számítógépekkel

15

9.

FOLYAMAT-HÁLÓZATSZINTÉZIS KOMBINATORIKUS MÓDSZERREL

17

9.1. Struktúra reprezentáció

18

9.2. Kombinatorikusan lehetséges struktúrák

20

9.3. Maximális struktúra algoritmikus generálása

21

9.4. Döntés leképezés

21

3

Tartalomjegyzék

9.5. ABB algoritmus

10. A FOLYAMAT-HÁLÓZATSZINTÉZIS FELADAT KITERJESZTÉSEI

23

28

10.1. Hulladékkezeléssel integrált folyamat-hálózatszintézis 10.1.1. Feladat definíció 10.1.2. Kombinatorikusan lehetséges struktúrák 10.1.3. MSGW algoritmus 10.1.4. Az algoritmus helyességének bizonyítása 10.1.5. ABBW algoritmus

29 30 31 34 35 42

10.2. Integrált folyamat-hálózat- és irányítórendszer tervezés 10.2.1. Struktúra reprezentáció 10.2.2. Kombinatorikusan lehetséges irányítható struktúrák 10.2.3. CMSG algoritmus 10.2.4. Az algoritmus helyességének bizonyítása 10.2.5. IPCS feladat megoldása az ABB algoritmus kiterjesztésével

48 49 52 53 53 58

10.3. FoO\DPDWKiOy]DWV]LQWp]LVV]DNDV]RVDQIRO\WRQRVN|OWVpJIJJYpQ\ P YHOHWL egységekkel 58 10.3.1. Szakaszosan folytonos költségfüggvény kezelése 59 10.3.2. Branch-and-bound algoritmus szakaszosan fol\WRQRVN|OWVpJIJJYpQ\ P YHOHWL egységekkel adott folyamat-hálózatszintézis feladat megoldására 64 10.4. )RO\DPDWKiOy]DWV]LQWp]LVIHODGDWPHJROGiVDSiUKX]DPRVP N|GpVLHOY számítógépeken 10.4.1. Szoftver-architektúra 10.4.2. Eredmények

69 70 71

11. ÖSSZEFOGLALÁS

76

12. IRODALOMJEGYZÉK

77

13. FÜGGELÉK

81

13.1. Branch-and-bound

81

4

Köszönetnyilvánítás

3. Köszönetnyilvánítás

(]~WRQV]HUHWQpNN|V]|QHWHWPRQGDQLPLQGHQNLQHNDNLOHKHW YpWHWWHKRJ\H]D dolgozat elkészüljön.

(OV VRUEDQ WpPDYH]HW PQHN 'U )ULHGOHU )HUHQF WDQV]pNYH]HW HJ\HWHPL tanárnak a segítségéért és tanácsaiért.

Dr. Hangos Katalin és Dr. L. T. Fan professzoroknak a közös munkánk során több éven keresztül nyújtott segítségükért.

Tanszéki kollégáimnak a segítségükért, a javító szándékú megjegyzéseikért.

Szüleimnek és öcsémnek a biztatásért.

5

Tartalmi összefoglaló

4. Tartalmi összefoglaló A dolgozatban az alap folyamat-hálózatszintézis feladat gyakorlati szempontból fontos kiterjesztéseinek megoldására alkalmas eszközöket mutatunk be. Az algoritmikus módszerek mindegyike a folyamat-hálózatszintézis feladat megoldására Friedler és munkatársai által kidolgozott kombinatorikus módszerre épül. A hulladékkezeléssel integrált folyamat-hálózatszintézis feladat definíciója a IHODGDWRV]WiO\WOHtUyIHOWpWHOHNHWWDUWDOPD]]DHQQHNPHJIHOHO HQKDWiUR]WXNPHJ a megoldások tulajdonságait. A struktúrákat ebben az esetben az alap folyamatKiOy]DWV]LQWp]LV IHODGDWWDO D WRYiEELDNEDQ DODSHVHW PHJHJ\H] HQ 3JUiIIDO reprezentáljuk. Megadjuk az optimális megoldás keresési terét meghatározó, a maximális struktúrát generáló (MSGW) algoritmust, illetve bebizonyítjuk az algoritmus helyességét. A branch-and-bound algoritmus szétválasztó lépésének leírásához definiáljuk a döntés leképezés kiterjesztését. Mind az MSGW algoritmus, mind a branch-and-bound algoritmus szétválasztó lépése a feladattípusra általánosan alkalmazható, feladatfüggetlen. Az integrált folyamat-hálózat- és irányítórendszer tervezés esetén a feladat GHILQtFLyMDE YOLWWLVPHJKDWiUR]]XNDPHJROGiVVWUXNW~UiNDWOHtUyD[LyPiNDW Ennél a kiterjesztésnél a struktúrákat az ún. CP-gráfokkal reprezentálhatjuk, amelynek a P-gráf az egyik komponense. Ebben az esetben is megadjuk a maximális struktúrát generáló (CMSG) algoritmust és bebizonyítjuk az algoritmus helyességét. A branch-and-bound algoritmus szétválasztó lépése lényegében azonos az eredeti ABB algoritmus szétválasztó lépésével, mindössze HJ\ HJ\V]HU YL]VJiODWRW YpJ]QN PLQGHQ N|]EOV UpV]SUREOpPiUD D] LUiQ\tWKDWyViJRWHOOHQ UL]YH $ V]DNDV]RVDQ IRO\WRQRV N|OWVpJIJJYpQQ\HO DGRWW P YHOHWL HJ\VpJHNE O iOOy hálózat szintézise megoldható az ABB algoritmussal is, itt a cél egy a feladattípus speciális tulajdonságait kihasználó algoritmus megadása volt. (ONpV]OW D V]DNDV]RVDQ IRO\WRQRV N|OWVpJIJJYpQQ\HO DGRWW P YHOHWL HJ\VpJHNE O iOOy KiOy]DW V]LQWp]LVpW PHJROGy EUDQFKDQGERXQG DOJRULWPXV szétválasztó lépése és az algoritmus definiálásához szükséges részprobléma reprezentáció. $ SiUKX]DPRV P N|GpVL HOY V]iPtWyJpSHNHQ IXWWDWKDWy $%% DOJRULWPXV NLGROJR]iViYDO D] DOJRULWPXV D PDQDSViJ HJ\LN OHJJ\RUVDEEDQ IHMO G számítástechnikai környezetben is használhatóvá válik, az óriási számítási WHOMHVtWPpQ\MyONLKDV]QiOKDWyQDJ\PpUHW J\DNRUODWLIHODGDWRNPHJROGiVDNRU

6

Extensions of process network synthesis (contents)

5. Extensions of Process Network Synthesis (contents) Algorithmic methods for solving different extensions of process network synthesis (PNS) have been elaborated. These algorithms are based on the accelerated branch-and-bound (ABB) algorithm proposed by Friedler and his colleagues for PNS problems. For process network synthesis with integrated waste treatment system, (i) the definition of solutions is extended; (ii) the axioms describing the combinatorially feasible structures are defined (iii) the MSGW algorithm for generating the maximal structure to define the search space for the branch-andbound algorithm solving the problem with proof of correctness is given; (iv) for formal definition of the general branching step of the proposed branch-andbound algorithm an extended decision-mapping has been introduced. Both the MSGW algorithm and the branching step of the branch-and-bound method are general; they are independent of the actual problem. In the case of integrated process and control system synthesis, (i) the definition of solutions is extended; (ii) the set of axioms describing the properties of combinatorially feasible and controllable (CFC) solution structures are given; (iii) an algorithm for generating the maximal CFC structure is presented followed by the proof of correctness; (iv) the branching step of the ABB algorithm is extended by a procedure for checking the controllability of a partial problem. Although the ABB algorithm can solve a PNS problem including operating units with sectionally continuous cost functions, an efficient algorithm exploiting the special properties of such problems is developed. An extended branching method and a new representation of partial problems are elaborated. The parallelization of the ABB algorithm allows us to utilize the acceleration achieved by the usage of multiple processors besides the acceleration of the sequential algorithm compared to traditional methods.

7

Extensionen der produktionsnetzwerksynthese (inhalt)

6. Extensionen der Produktionsnetzwerksynthese (Inhalt) Algorithmische Methoden für das Lösen unterschiedlicher Erweiterungen der Produktionsnetzwerksynthese (PNS) sind ausgearbeitet worden. Diese Algorithmen basieren auf dem beschleunigten Verzweigungsalgorithmus (ABB), der von Friedler und seinen Mitarbeitern für PNS-Probleme vorgeschlagen wurde. Bei synthetisierten Prozeßnetzen aus integriertem Abfallbehandlungssystem, ist die Definition der Lösungen erweitert und dergleichen ist das Set der Axiome, welches die Eigenschaften der kombinatorisch möglichen Lösungsstrukturen beschreibt. Die Lösungsstrukturen werden durch P-Diagramme wie im Fall von den PNS-Problemen, dargestellt. Die Superstruktur definiert den Suchraum des Algorithmus, der das Problem löst. Der MSGW-Algorithmus legt die Superstruktur fest; die Korrektheit dieses Algorithmus wurde nachgewiesen. Für formale Definition des allgemeinen erweiterten Jobsteps des vorgeschlagenen Verzweigungsalgorithmus, wurde ein erweitertes Entscheidungs-mapping eingeführt; es kann Abfallbehandlungssysteme behandeln. Beide Algorithmen, der MSGW und der erweiterte Jobstep der Verzweigungsmethode, sind allgemein anwendbar; sie sind vom tatsächlichen Problem unabhängig. Im Fall integrierter Prozeß- und Steuersystemsynthese, wird die Definition der Lösungen auch ausgedehnt und dasselbe gilt für das Set an Axiomen, welche die Eigenschaften der kombinatorisch möglichen und kontrollierbaren, Lösungsstrukturen beschreibt (CFC). Die Lösungsstrukturen werden von CPGRAPHEN beschrieben, das P-Diagramm ist ein Bestandteil des CPGRAPHEN. Ein Algorithmus für das Festlegen der maximalen CFC-Struktur, gefolgt vom Beweis von Korrektheit, wird dargestellt. Der erweiterte Jobstep des ABB-Algorithmus wird durch ein Verfahren für die Überprüfung der Steuerbarkeit eines partiellen Problems ausgedehnt. Obgleich der ABBAlgorithmus ein PNS-Problem einschließlich der funktionierenden Maßeinheiten mit geschnitten ununterbrochenen Kostenfunktionen lösen kann, wird ein noch leistungsfähiger Algorithmus, der die speziellen Eigenschaften solcher Probleme ausnutzt, entwickelt. Eine erweiterte Branching-Methode und eine neue Darstellung der Teilprobleme werden ausgearbeitet. Die Paralellität des ABB-Algorithmus erlaubt es, die Beschleunigung derart zu steigern, daß der Gebrauch von Mehrfachprozessoren zu zusätzlicher Zeiteinsparung führt, die in der Arbeit mit traditionellen Methoden verglichen wird.

8

Bevezetés

7. Bevezetés A dolgozat a Friedler és munkatársai által kidolgozott folyamat-hálózatszintézis IHODGDWRWPHJROGyNRPELQDWRULNXVPyGV]HUpVD]HUUHpSO J\RUVtWRWWEUDQFK and-bound algoritmus [16], az ABB algoritmus, lehetséges továbbfejlesztéseivel foglalkozik. A továbbiakban ezt a módszert tekintjük alapnak és az ABB algoritmussal

megoldható

feladatosztályt

a

folyamat-hálózatszintézis

alapfeladatának. A folyamat-hálózatszintézis feladat rövid leírása: egy folyamat-hálózatszintézis IHODGDW GHILQLiOiVDNRU PHJ NHOO DGQXQN D OHKHWVpJHV pStW HOHPHN D továbbiakban P YHOHWL HJ\VpJQHN KtYMXN KDOPD]iW PHO\HN YDODPLE O LQSXW YDODPLW RXWSXW J\iUWDQDN D P YHOHWL HJ\VpJHN P N|GpVpW OHtUy |VV]HIJJpVHNHW LQSXWRN RXWSXWRN D P YHOHWL HJ\VpJ OHKHWVpJHV iOODSRWDL költségfüggvénye, ezek kapcsolata), a rendelkezésre álló nyersanyagok KDOPD]iW D] H]HNUH YRQDWNR]y HVHWOHJHV NRUOiWRNDW D] HO iOOtWDQL NtYiQW WHUPpNpNHW pV MHOOHP] LNHW WRYiEEi PHJ NHOO KDWiUR]QXQN KRJ\ PLO\HQ szempontból keressük az optimális megoldást (azaz meg kell adnunk egy költségfüggvényt). $ FpO P YHOHWL HJ\VpJHN HJ\ KDOPD]iQDN D WRYiEELDNEDQ struktúra) NLYiODV]WiVD pV H]HN P N|GpVpW OHtUy SDUDPpWHUHN PHJDGiVD ~J\ KRJ\ D VWUXNW~UiW H]HQ SDUDPpWHUHNQHN PHJIHOHO HQ P N|GWHWYH NDSRWW hálózat (a feladat megoldása) megfelel a feladat definíciójában adott követelményeknek és a szintén definiált szempontból optimális. A folyamat-hálózatszintézis feladatot megoldó módszerek célja tehát egy optimális hálózat megkeresése, amely egy struktúrának és a struktúra optimális P N|GpVpQHNDPHJKDWiUR]iViWMHOHQWL A dolgozatban az irodalmi áttekintés után a Friedler és munkatársai által kidolgozott gyorsított branch-and-bound algoritmust külön fejezetben mutatjuk

9

Bevezetés

be, mivel az szolgál a dolgozatban ismertetett kiterjesztések alapjául. Ezt követi a kiterjesztések megoldására kidolgozott módszerek bemutatása. A folyamat-hálózatszintézis feladat kiterjesztésén olyan feladatot értünk, amelyben az alapfeladathoz képest további feltételek adottak. Az itt bemutatott kiterjesztések mellett természetesen további kiterjesztések is léteznek, valamint a


feladat

kiterjesztései

általában

szabadon

kombinálhatóak. A dolgozatban az alábbi kiterjesztéseket mutatjuk be: hulladékkezeléssel integrált

folyamat-hálózatszintézis,

integrált

folyamat-hálózat-

és

irányítórendszer tervezés, folyamat-hálózatszintézis szakaszosan folytonos FpOIJJYpQ\

P YHOHWL

HJ\VpJHNNHO

IRO\DPDWKiOy]DWV]LQWp]LV

IHODGDW

PHJROGiVDSiUKX]DPRVP N|GpVLHOY V]iPtWyJpSHNHQ Hulladékkezeléssel

integrált


esetén

a

feladat

definíciója összetettebb, az alapfeladatban is definiált szükséges termékek halmaza mellett a nem megengedett outputok halmaza is adott. A kiterjesztés legfontosabb alkalmazási területe a vegyipar, ugyanakkor a kidolgozott módszer iOWDOiQRVDQ DONDOPD]KDWy P V]DNL WHUPHO UHQGV]HUHNQpO $ PHJHQJHGHWW GH nem kívánatos outputokhoz a környezet terhelésével arányos értékeket rendelve és ezeket a célfüggvénybe építve olyan módszert kapunk, amely az optimális megoldást a költségen kívül (esetleg helyett) más szempontokat is figyelembe véve határozza meg. Az integrált folyamat-hálózat- és irányítórendszer tervezés esetén a feladat definíciója

szintén

tartalmaz

további

feltételeket,

itt

irányíthatósági

szempontokat veszünk figyelembe az optimális megoldás keresésekor. Az LUiQ\tWiV D P N|GpV VRUiQ HO IRUGXOy GLQDPLNXV YiOWR]iVRNKR] NDSFVROyGLN ugyanakkor a folyamat-hálózatszintézis feladatot megoldó módszerek célja egy optimális hálózat megkeresése, amely egy struktúra és annak egy optimális VWDWLNXVMHOOHJ P N|GpVpQHNDPHJKDWiUR]iViWMHOHQWLËJ\HJ\V]HU %RROHDQ típusú irányíthatósági szempontokat vehetünk figyelembe, az alkalmazhatóság PHJILJ\HOKHW VpJ V]DEiO\R]iV V]HPSRQWMiEyO PiU tJ\ LV OpQ\HJHVHQ MREE megoldást kaphatunk.

10

Bevezetés

Szakaszosan

folytonos

költségfüggvény

alkalmazása

a

folyamat-

hálózatszintézis feladatban a matematikai modell specializálását jelenti. Ez a IHODGDWRV]WiO\ PHJROGKDWy D] DODS $%% DOJRULWPXVVDO LV PHJIHOHO NRUOiWR]y függvény alkalmazásával, viszont az így kapott módszer az óriási számításigény miatt csak korlátozottan lenne használható. Az itt bemutatott módszer ezt a feladatot oldja meg az ABB algoritmusba egy összetettebb szétválasztó lépést integrálva. $ J\RUVtWRWW EUDQFKDQGERXQG DOJRULWPXV SiUKX]DPRV P N|GpVL HOY számítógépeken futtatható változata az eredeti szekvenciális algoritmus PyGRVtWiVD OHKHW Yp WpYH PpJ QDJ\REE PpUHW IRO\DPDWKiOy]DWV]LQWp]LV IHODGDWRNJ\RUVPHJROGiViWIHOWpYHKRJ\DPHJIHOHO HV]N|]UHQGHONH]pVUHiOO

11

Irodalmi áttekintés

8. Irodalmi áttekintés $ IHMH]HWEHQ HO V]|U U|YLGHQ LVPHUWHWQN QpKiQ\ LVPHUW D IRO\DPDW hálózatszintézis feladat megoldására kidolgozott általános módszert. Ezt N|YHW HQ D GROJR]DWEDQ LVPHUWHWHWW IRO\DPDWKiOy]DWV]LQWp]LV IHODGDW kiterjesztésekkel azonos, vagy ahhoz hasonló feladatosztályt megoldó módszereket mutatunk be. Mivel a dolgozatban ismertetett módszerek mindegyike a branch-and-bound technikára épül, a szakirodalomban széles körben publikált módszer egy formális leírását a dolgozat végén függelékként adjuk meg.

8.1. Folyamat-hálózatszintézis feladatot megoldó általános módszerek A folyamat-hálózatszintézis feladat megoldására kidolgozott módszerek egy része heurisztikus szabályokat alkalmaz, itt az optimális megoldás megtalálása QHP JDUDQWiOW $ NRUiEEDQ NLGROJR]RWW HJ]DNW PDWHPDWLNDL PyGV]HUHNUH pSO eljárások nagy része egy általános matematikai programozási módszert alkalmazott a folyamat-hálózatszintézis feladat megoldására [5, 7, 25, 40], ami a IRO\DPDWKiOy]DWV]LQWp]LV NRPELQDWRULNXV MHOOHJpQHN N|V]|QKHW HQ HJ\ YHJ\HV egész, sok bináris változót tartalmazó matematikai programozási feladat PHJROGiViW MHOHQWL D PyGV]HUW O IJJHWOHQO SpOGiXO %HQGHUV GHNRPSR]tFLy >@ NOV N|]HOtWpV >@ (J\ LSDUL PpUHW IHODGDW PHJROGiVD yULiVL V]iPtWiVL LJpQ\ H]HNDPyGV]HUHNQHPKDV]QiOMiNNLDIRO\DPDWKiOy]DWV]LQWp]LVIHODGDW jellegzetességeit, lényegében a feladat matematikai modelljének felírása után nincs szerepe az eredeti feladatnak. A módszerek némelyike megengedi heurisztikus algoritmusok alkalmazását a számítások gyorsítása érdekében, ez viszont a globális optimum figyelmen kívül hagyását jelentheti a megoldás keresésekor.

12


Kifejezetten folyamat-hálózatszintézis feladatok megoldására Grossmann és munkatársai [34] dolgoztak ki egy módszert, amely az optimális megoldás keresésekor a folyamat-hálózatszintézis feladat kombinatorikus tulajdonságait leíró logikai összefüggéseket figyelembevéve teszi hatékonyabbá az optimális megoldás

keresését.

Brendel

és

munkatársai

[2]

bebizonyították,

a

JUiIDOJRULWPXVRNUD DODSR]y NRPELQDWRULNXV WHFKQLND PHJIHOHO DODSRNDW V]ROJiOWDW D PyGV]HUKH] D]D] OHYH]HWKHW EHO OH $ PyGV]HU KiWUiQ\D KRJ\ D logikai formulákat és a matematikai programozási módszereket együttesen alkalmazó módszer hatékony megvalósítása nehézkes (például milyen SURJUDPQ\HOYHW KDV]QiOMXQN WRYiEEi D SXEOLNiOW PyGV]HU QHP PHJIHOHO HQ NH]HO EL]RQ\RV HVHWHNHW SpOGiXO D] HO IRUGXOy N|U|NHW UHFLUNXOiFLyNDW PHJV] QWHWL tJ\ OHKHWVpJHV PHJROGiVRNDW QHP YHV] ILJ\HOHPEH D PHJROGiV keresése során). Kombinatorikus módszereket, részben a branch-and-bound technikát, részben dinamikus programozást alkalmaz Fraga és McKinnon [8, 9]. Módszerük azonban nem törekszik az általános alkalmazhatóságra, a feladatot részproblémákra ERQWy V]pWYiODV]Wy OpSpV IHODGDWIJJ D PyGV]HUEHQ $ V]pWYiODV]WiV IRO\WRQRV változók szerint is lehetséges a módszerben, ekkor a folytonos változót diszkrét értékek egy véges halmazával közelítik. A folyamat-hálózatszintézis feladat megoldására kidolgozott ABB algoritmust a N|YHWNH] IHMH]HWEHQLVPHUWHWMN

8.2. Hulladékkezeléssel integrált folyamathálózatszintézis A

hulladékkezeléssel

integrált


megoldására

NLGROJR]RWWKDJ\RPiQ\RVPyGV]HUHNN|]|VMHOOHP] MHKRJ\DNtYiQWWHUPpNHW WHUPHO KiOy]DW WHUYH]pVpW pV D WLOWRWW LOOHWYH PDJDV N|OWVpJJHO MiUy RXWSXWRN NH]HOpVpWYpJ] KiOy]DWWHUYH]pVpWNpWNO|QOpSpVEHQROGMiNPHJ(]D]RQEDQ általában nem vezet optimális vagy közel optimális megoldáshoz. Az amerikai EPA (Environmental Protection Agency, US) által definiált hierarchiában [1, 35] a hulladékkezeléssel integrált folyamat-hálózatszintézis IHODGDW PHJROGiViEDQ HOV GOHJHV V]HUHSHW NDS D IHOKDV]QiOW Q\HUVDQ\DJRN

13


mennyiségének csökkentése (ami természetesen a szükséges termékek mellett kevesebb egyéb outputot eredményez), második helyen az újrahasznosítás V]HUHSHODKXOODGpNNH]HO UHQGV]HUpStWpVHFVDNH]HNHWN|YHWL0tJD]HOV NpW OHKHW VpJHW

DPL

OpQ\HJpEHQ

D

WHUPHO

KiOy]DW

SDUDPpWHUHLQHN

meghatározásakor a hulladékminimalizálás figyelembevételét jelenti, több PyGV]HUEHQ LV D WHUPHO KiOy]DW WHUYH]pVpYHO LQWHJUiOYD DONDOPD]]iN D KXOODGpNNH]HO pV WHUPHO KiOy]DW YDOyGL LQWHJUiOW WHUYH]pVpUH HGGLJ HJ\HWOHQ módszer sem vállalkozott. Több hulladékkezeléssel foglalkozó módszer [3, 4] a fenti hierarchiának csak az HOV YDJ\HOV NpWOpSpVpWDONDOPD]]DD]D]DKXOODGpNNH]HO KiOy]DWWHUYH]pVH nem is része a módszernek. A Crabtree és El-Halwagi által javasolt módszer [4] NpV] WHUPHO KiOy]DW KXOODGpNNLERFViWiViW PLQLPDOL]iOMD D PiU IL[ VWUXNW~UD iOODSRWYiOWR]yLQDN PyGRVtWiViYDO GH D WHUPHO UHQGV]HU VWUXNW~UiMiW QHP PyGRVtWMD D]D] QHP iOWDOiQRV LQWHJUiOW WHUYH] PyGV]HUW DG D WHUPHO KiOy]DW WHUYH]pVpW OHOYiODV]WMDDKXOODGpNNH]HOpVW A Berger által javasolt hulladékkezeléssel integrált folyamat-hálózatszintézis feladatot megoldó módszer [1] az optimális megoldás tervezését több lépésre ERQWMD VWDJH JDWH PRGHO $] HOV OpSpVEHQ D P N|GpVW OHtUy SDUDPpWHUHN PHJKDWiUR]iVDNRU ILJ\HOHPEH YHV]L D KLHUDUFKLD HOV NpW V]LQWMpW 9LV]RQW D KXOODGpNNH]HO UHQGV]HU WHUYH]pVpW HJ\ NO|QiOOy OpSpVEHQ ROGMD PHJ $ módszer nyilván jobb megoldást eredményez, mint a szükséges termékek WHUPHOpVpWpVDQHPPHJHQJHGHWWRXWSXWRNNH]HOpVpWYpJ] KiOy]DWRNDWWHOMHVHQ HONO|QOWHQWHUYH] PyGV]HUHNGHD]LQWHJUiFLyLWWVHPWHOMHV

8.3. Integrált folyamat-hálózat- és irányítórendszer tervezés A hagyományos tervezési módszer szerint egy hálózat és irányítórendszerének WHUYH]pVH NpW HJ\PiVW N|YHW OpSpVEHQ W|UWpQLN $ OHJW|EE PXQND D] irányítórendszer tervezésével kapcsolatban a kiértékelésre összpontosít, csak kevesen adnak algoritmikus eljárásokat, amelyek az irányíthatóság mértékét is integrálják a tervezési lépésbe [37].

14


1LVKLGD pV PXQNDWiUVDL > @ W|UHNHGWHN HOV NpQW D] LUiQ\tWKDWyViJ V]LV] tematikus

figyelembevételére


feladatok

megoldásakor. Nagyon kevés publikáció jelent meg, amelyben olyan módszert LVPHUWHWQHN DPHO\ HJ\LGHM OHJ W|UHNV]LN D JD]GDViJRV pV D] LUiQ\tWKDWy tervezésre [20, 28, 30, 31], ezek speciális folyamat-hálózatszintézis feladatok irányítórendszerrel integrált tervezésére adnak megoldást általános matematikai programozási módszereket alkalmazva.

8.4. Szakaszosan folytonos költségfüggvény alkalmazása folyamat-hálózatszintézis feladatban A feladattípus az alap folyamat-hálózatszintézis feladathoz hasonlóan megoldható általános matematikai programozási módszerekkel, viszont a V]DNDV]RQIRO\WRQRVIJJYpQ\HNMHOHQOpWHPLDWWH]NO|Q|VHQQHKp]LG LJpQ\HV nagy ipari feladatok megoldása szinte lehetetlen. A feladattípus megoldására alkalmas a Raman és Grossmann által kidolgozott matematikai logikát használó módszer, az úgynevezett diszjunktív programozás, DPHOO\HO D NO|QE|] PpUHW P YHOHWL HJ\VpJHN KDV]QiODWD HJ\HJ\ megoldásban logikai formulákkal jól leírható. Ez a módszer jóval hatékonyabb, mint egy általános matematikai programozási módszer alkalmazása, azonban QpKiQ\ SUREOpPiW PHJROGDWODQXO KDJ\RWW SpOGiXO D P YHOHWL HJ\VpJHN NDSDFLWiVDLUDIHOV NRUOiWDOJRULWPLNXVV]iPROiVDKLiQ\]LNH]WLQSXWNpQWYiUMDD módszer.

8.5. Folyamat-hálózatszintézis feladat megoldása SiUKX]DPRVP N|GpVLHOY V]iPtWyJpSHNNHO $ V]DNLURGDORPEDQ IHOOHOKHW PyGV]HUHN QDJ\ UpV]H > @ iOWDOiQRV PDWHPDWLNDL

SURJUDPR]iVL

PyGV]HUHN

SiUKX]DPRV

P N|GpVL

HOY

számítógépekre adaptált változatát [29, 32, 36] alkalmazza folyamathálózatszintézis feladat megoldására. A folyamat-hálózatszintézis feladat megoldására kidolgozott kombinatorikus módszer párhuzamos feldolgozásra alkalmas változatát készítette el Fraga és McKinnon [9], az átalakított módszer dinamikus programozást használ. A

15


módszert transzputeren, 64 processzoros Intel i860-as számítógépen és munkaállomás hálózaton valósították meg. Elkészítették mind a dinamikus processzorterhelés-kiegyenlítéssel (load balance) dolgozó, mind a hierarchikus mester-szolga (master-slave) alapú változatot. Mindkét típusú algoritmussal, PLQGHQ JpSWtSXV HVHWpQ N|]HO OLQHiULV J\RUVXOiVW WDSDV]WDOWDN V W D IHODGDWRN méretének növelésével a gyorsulás tovább javult. A mester-szolga algoritmus DONDOPD]iVDNRUDPHVWHUQHPYiOWV] NNHUHV]WPHWV]HWWpDIHODGDWRNPHJROGiVD során.

16

Folyamat-hálózatszintézis kombinatorikus módszerrel

9. Folyamat-hálózatszintézis kombinatorikus módszerrel A folyamat-hálózatszintézis kiterjesztéseinek megoldására javasolt módszerek a Friedler és munkatársai által kidolgozott, gráfalgoritmusokra alapozó, kombinatorikus technikára épülnek [16]. A folyamat-hálózatszintézis alapfeladatának formális definíciója: adott P YHOHWL egységHNHJ\KDOPD]DPLQGHQP YHOHWLHJ\VpJHJ\LQi, outi, mi, ki) rendezett QpJ\HVQHNWHNLQWKHW DKROLQiD]LP YHOHWLHJ\VpJLQSXWMDLQDNKDOPD]DRXWi az L P YHOHWL HJ\VpJ RXWSXWMDLQDN KDOPD]D Pi D] L P YHOHWL HJ\VpJ P N|GpVpW OHtUy IJJYpQ\ D P YHOHWL HJ\VpJ LQSXWMDLQDN pV HJ\pE iOODSRWYiOWR]yLQDN IJJYpQ\pEHQPHJDGMDDP YHOHWLHJ\VpJRXWSXWMDLWDNiD]LP YHOHWLHJ\VpJ költségfüggvénye. $ P YHOHWL HJ\VpJHN N|]|WWL NDSFVRODWRW D P YHOHWL HJ\VpJHN LQSXWMDL pV outputjai jelentik. Ezeket a továbbiakban anyagoknak nevezzük, bár az input vagy output lehet energia, vagy például pozíció is egy szállítási feladat esetén. $]DQ\DJRNKDOPD]DWHUPpV]HWHVHQNO|QLVGHILQLiOKDWyEiUHJ\HWOHQP YHOHWL egységhez sem tartozó anyag definiálása nyilván felesleges. Hálózaton a P YHOHWL HJ\VpJHN HJ\ UpV]KDOPD]iQDN YDODPLO\HQ iOODSRWYiOWR]yN V]HULQWL P N|GWHWpVpW pUWMN DPHO\ EL]RQ\RV LQSXW DQ\DJRNEyO EL]RQ\RV RXWSXW DQ\DJRNDW iOOtW HO $ hálózat struktúráját GHILQLiOKDWMXN P YHOHWL HJ\VpJHN halmazának állapotváltozók nélküli megadásával. Ha a lehetséges input-output anyagok közül bizonyos anyagok (nyersanyagok) rendelkezésünkre állnak (korlátozott vagy korlátlan mennyiségben) és célunk valamely

más anyaghalmaz

(termékek HO iOOtWiVD DOXOUyO NRUOiWR]RWW

PHQQ\LVpJEHQ DNNRU D IRO\DPDWKiOy]DWV]LQWp]LV DODSIHODGDWD D P YHOHWL HJ\VpJHN

HJ\

RO\DQ

UpV]KDOPD]iQDN

PHJNHUHVpVH

D

PHJIHOHO

iOODSRWYiOWR]yNNDO DPHO\HNE O IHOpSO KiOy]DW PHJROGiV D] DGRWW LQSXWRN (nyersanyagok) segítségével a kért outputokat (termékek) minimális költséggel

17


iOOtWMDHO $KiOy]DWN|OWVpJHiOWDOiEDQDP YHOHWLHJ\VpJHNDQ\HUVDQ\DJRND WHUPpNHN pV D] HJ\pE KDV]QRV YDJ\ QHP NtYiQW RXWSXWRN N|OWVpJpE O számítható. Ez a hálózat lesz a folyamat-hálózatszintézis feladat optimális megoldása. A folyamat-hálózatszintézis alapfeladata tehát definiálható a P YHOHWLHJ\VpJHNQ\HUVDQ\DJRNpVWHUPpNHNPHJDGiViYDO Mint a feladat definíciójából is látható, a folyamat-hálózatszintézis részben NRPELQDWRULNXV P YHOHWL HJ\VpJHN HJ\ UpV]KDOPD]iQDN NHUHVpVH UpV]EHQ PDWHPDWLNDL SURJUDPR]iV N|OWVpJIJJYpQ\ iOODSRWYiOWR]yN MHOOHJ IHODGDW ami egyben megoldását is nehézzé teszi, hiszen a kombinatorikus jelleg miatt a feladat matematikai modellje egy sok bináris változót tartalmazó vegyes egész programozási feladat lesz. A megoldások mindegyikének rendelkeznie kell néhány triviális tulajdonsággal, viszont ezek felírása a matematikai modellbe azt lényegesen bonyolultabbá tenné, azaz a megoldás keresésének hatékonysága nem javulna, így ezek a tulajdonságok csak a matematikai modellel dolgozva nem használhatóak ki. A gyorsított branch-and-bound algoritmus lényegében egy olyan speciális algoritmus, amely a folyamat-hálózatszintézis feladat kombinatorikus jellegét kihasználva több nagyságrenddel gyorsítja az optimális megoldás keresését az általános matematikai programozási módszerekhez képest. A kombinatorikus jelleg kihasználása nyilvánvalóan azt jelenti, hogy a módszer QHP HJ\V]HU HQ HJ\ PDWHPDWLNDL PRGHOOW ROG PHJ KDQHP D KiOy]DWRN VWUXNW~UiLYDO LV GROJR]LN D NHUHVpV VRUiQ H]pUW DODSYHW IRQWRVViJ~ KRJ\ D VWUXNW~UDUHSUH]HQWiFLy HJ\pUWHOP PDWHPDWLNDL pUWHOHPEHQ V]LJRU~ pV NRPELQDWRULNXV DOJRULWPXVRNNDOMyONH]HOKHW OHJ\HQ

9.1. Struktúra reprezentáció Bevett szokás, hogy a hálózat struktúráját egy irányított gráffal írják le, de ez QHP DONDOPDV D] HJ\pUWHOP PHJDGiViUD H]pUW D KiOy]DW VWUXNW~UiMiW HJ\ irányított páros gráffal, az úgynevezett P-gráffal reprezentáljuk [10, 11, 17]. A gráf csúcspontjait a folyamat-hálózatszintézis feladat definíciójában adott P YHOHWL HJ\VpJHN pV D KR]]iMXN NDSFVROyGy DQ\DJRN DONRWMiN $ JUiI pOHL D]

18


DQ\DJRN pV P YHOHWL HJ\VpJHN N|]|WWL NDSFVRODWRN HJ\ b P YHOHWL HJ\VpJ típusú csúcsból él vezet egy a anyag típusú csúcshoz, ha a eleme b outputhalmazának (a∈outb), illetve egy a anyag típusú csúcsból él vezet egy b P YHOHWLHJ\VpJWtSXV~FV~FVKR]KDa eleme b inputhalmazának (a∈inb). Az ily módon definiált gráf nyilván páros, hiszen soha nincs él két azonos típusú csúcs N|]|WW$3JUiIRWDFV~FVRNDWDONRWyDQ\DJpVP YHOHWLHJ\VpJKDOPD]EyOiOOy SiURVVDO DGKDWMXN PHJ SpOGiXO 0 2 3JUiI D] pOHNHW D P YHOHWL HJ\VpJHN HJ\pUWHOP HQPHJKDWiUR]]iN $ 3JUiI iEUi]ROiVDNRU D P YHOHWL HJ\VpJ WtSXV~ FV~FVRNDW Yt]V]LQWHV YRQDOODO (

), az anyag típusú csúcsokat körrel (l) jelöljük. Az anyag típusú csúcsok

között a nyersanyagokat

, a termékeket különbözteti meg a többi anyagtól.

1. példa. Az 1 iEUD HJ\ P YHOHWL HJ\VpJE O iOOy IRO\DPDWKiOy]DWV]LQWp]LV feladat P-gráfját szemlélteti, és mint az az ábráról is leolvasható, a feladat az 1, P YHOHWLHJ\VpJHNYDODPHO\NRPELQiFLyMiYDOD]$DQ\DJWHUPHOpVH~J\ hogy nyersanyagként az E, G, J és K anyagok állnak rendelkezésre.

K

J

6

5 F

E 3 B

G

H

4

C

D

1

2 A

1. ábra. Az ({A, B, C, D, E, F, G, H, J, K}, {1, 2, 3, 4, 5, 6}) P-gráf.

19


9.2. Kombinatorikusan lehetséges struktúrák Az optimális megoldás struktúrájának rendelkeznie kell néhány olyan WXODMGRQViJJDO DPHO\HN IJJHWOHQHN D P YHOHWL HJ\VpJHN PDWHPDWLNDL PRGHOOMpW O $] RSWLPiOLV PHJROGiV NHUHVpVH VRUiQ H]HNHW D NRPELQDWRULNXV tulajdonságokat hatékonysága.

figyelembevéve Ezeket

a

nagyságrendekkel

nyilvánvaló

javítható

tulajdonságokat

mint

a

keresés

axiómákat

fogalmazzuk meg [11]: (S1) Minden termék szerepel a struktúrában. (S2) (J\ D VWUXNW~UiEDQ V]HUHSO DQ\DJ DNNRU pV FVDN DNNRU Q\HUVDQ\DJ KD HJ\HWOHQDVWUXNW~UiEDQV]HUHSO P YHOHWLHJ\VpJVHPiOOtWMDHO (S3) 0LQGHQ D VWUXNW~UiEDQ V]HUHSO P YHOHWL HJ\VpJ D IRO\DPDW hálózatszintézis feladatban definiált. (S4) 0LQGHQDVWUXNW~UiEDQV]HUHSO P YHOHWLHJ\VpJW OYH]HW~WWHUPpNKH] (S5) Ha egy a anyag része a struktúrának, akkor létezik a struktúrában olyan P YHOHWLHJ\VpJDPHO\QHNa inputja vagy outputja. $]6D[LyPiEDQV]HUHSO ~WDJUiIHOPpOHWEHQV]RNiVRVLUiQ\tWRWWXWDWMHOHQWLD struktúra P-gráfjában. A megoldások struktúráinak, a továbbiakban megoldásstruktúráknak, nyilván rendelkezniük kell a fenti tulajdonságokkal, de ez csak szükséges feltétel, nem HOpJVpJHV (ONpS]HOKHW KRJ\ D IHQWL IHOWpWHOHNHW WHOMHVtW VWUXNW~UD QHP P N|GWHWKHW ~J\ KRJ\ D NtYiQW PHQQ\LVpJ WHUPpNHW HO iOOtWVD D rendelkezésre álló nyersanyagokból. Azokat a struktúrákat, amelyek teljesítik a fenti axiómákat kombinatorikusan lehetséges struktúráknak nevezzük. Az optimális megoldás keresését a kombinatorikusan lehetséges struktúrák KDOPD]iUDV] NtWYHDNHUHVpVLWpUOpQ\HJHVHQFV|NNHQ3pOGiXOHJ\P YHOHWL egységgel definiált folyamat-hálózatszintézis feladat esetén [17] 235-1, azaz több mint 34 milliárd struktúra adható meg, ugyanakkor a kombinatorikusan lehetséges struktúrák száma mindössze 3465. Láthattuk, hogy a kombinatorikusan lehetséges struktúrák száma általában nagyságrendekkel kisebb, mint a berendezések halmazának összes lehetséges

20


UpV]KDOPD]DXJ\DQDNNRUDP YHOHWLHJ\VpJHNV]iPiQDNQ|YHOpVpYHOH]DV]iP LVH[SRQHQFLiOLVDQQ KHW$WHOMHVOHV]iPOiOiVD]D]D]|VV]HVNRPELQDWRULNXVDQ lehetséges struktúra generálása, majd a fix struktúra matematikai modelljének PHJROGiVD DPHO\ PiU QHP WDUWDOPD]]D D NRPELQDWRULNXV MHOOHJE O DGyGy ELQiULVYiOWR]yNDWDP YHOHWLHJ\VpJHNPRGHOOMpE OtUKDWyIHOiOWDOiEDQHJ\/3 YDJ\ 1/3 IHODGDW QHP PHJIHOHO PyGV]HU $] LO\HQ MHOOHJ IHODGDWRN megoldására az egyik legelterjedtebb módszer a branch-and-bound (Függelék) DONDOPD]iVD $ EUDQFKDQGERXQG IRQWRVDEE HO Q\HL D OHV]iPOiOiVQiO lényegesen hatékonyabb keresésen túl: (i) az optimális megoldás mellett az n legjobb

megoldás

is

generálható,

(ii)

heurisztikus

algoritmusokkal

kombinálható, (iii) alkalmas párhuzamos feldolgozásra.

9.3. Maximális struktúra algoritmikus generálása $ NHUHVpV WHUpW PLQLPDOL]iOKDWMXN KD FVDN D]RNDW D P YHOHWL HJ\VpJHNHW vesszük figyelembe a keresés során, amelyek valamely kombinatorikusan lehetséges struktúra részei lehetnek. Mivel a kombinatorikusan lehetséges struktúrák halmaza véges és zárt az unióra [12], ha ez a halmaz nem üres, akkor létezik maximális struktúra, melynek minden kombinatorikusan lehetséges struktúra részhalmaza. Így a folyamat-hálózatszintézis feladat megoldására készített algoritmusban erre a struktúrára szorítkozhatunk a keresés során. A Friedler és munkatársai által kidolgozott MSG algoritmus ezt a maximális struktúrát generálja az összes kombinatorikusan lehetséges struktúra generálása QpONO SROLQRPLiOLV LG EHQ >@ $] 06* DOJRULWPXV W|EE D GROJR]DWEDQ ismertetett folyamat-hálózatszintézis feladat kiterjesztés esetén az adott feladatosztály megoldásához szükséges maximális struktúra generálásához szolgál alapként.

9.4. Döntés leképezés Az MSG algoritmus a minimális komplexitást biztosító keresési teret határozza meg.

A


feladatot

megoldó

branch-and-bound

algoritmus pontos megadásához definiálni kell a korlátozó (bounding) és a szétválasztó

(branching)

lépéseket.

A

korlátozó

eljárás

a

folyamat-

21


KiOy]DWV]LQWp]LV IHODGDW PDWHPDWLNDL PRGHOOMpW O IJJ H]pUW iOWDOiQRVDQ QHP adható meg, a MINLP vagy MILP matematikai programozási feladatok megoldásakor az általános branch-and-bound módszereknél szokásos módon FpOV]HU DUHOD[iOWPRGHOOWGHILQLiOQL$V]pWYiODV]WyOpSpVQpOLVDONDOPD]KDWyDN az általános módszerek, ebben az esetben azonban a folyamat-hálózatszintézis feladat speciális kombinatorikus tulajdonságait nem használjuk ki. A folyamathálózatszintézis feladat megoldására kidolgozott ABB algoritmus ezeket a kombinatorikus tulajdonságokat használja ki a szétválasztó lépésben. A szétválasztó lépés alapja a döntés leképezés [14], amely egyrészt garantálja a branch-and-bound algoritmusok szétválasztó lépésére megkívánt tulajdonságok teljesülését, másrészt segítségével a szétválasztó lépések sorrendjét úgy határozhatjuk meg, hogy az minimális számú részprobléma megoldását tegye V]NVpJHVVp $] DOiEELDNEDQ D G|QWpV OHNpSH]pV DODSYHW GHILQtFLyLW pV tulajdonságait mutatjuk be. Mivel az alábbi állítások a folyamat-hálózatszintézis IHODGDW PDWHPDWLNDL PRGHOOMpW O IJJHWOHQHN FVDN D PHJROGiVVWUXNW~UiNUD vonatkoznak, így a folyamat-hálózatszintézis feladat megadására megfelel a feladat (M, O) P-gráfja. Jelölje ∆ D]W D OHNpSH]pVW D] DQ\DJRN pV D P YHOHWL HJ\VpJHN KDWYiQ\KDOPD]D között, amely minden X∈0 DQ\DJUD PHJDGMD D] ;HW HO iOOtWy P YHOHWL egységek halmazát, azaz ∆(X) = {i∈O | X∈outi}. 1. definíció. Legyen m⊆M és δ(X)⊆∆(X) minden X∈m-re. Ekkor δ-t, mint OHNpSH]pVW D] P KDOPD]EyO D P YHOHWL HJ\VpJHN UpV]KDOPD]DLQDN KDOPD]iED δ[m] = {(X, δ(X)) | X∈m}, döntés leképezésnek nevezzük m felett. 2. definíció. A δ[m] döntés leképezés komplementere a δ [m] = {(X, ∆(X)\δ(X)) | X∈m} leképezés. 3. definíció. A δ[m] döntés leképezés (m≠∅) akkor és csak akkor konzisztens, ha minden X, Y ∈ m-re δ(X)∩ δ (Y)=∅. Jelölje op(δ[m]) a δ>P@ G|QWpV OHNpSH]pV P YHOHWL HJ\VpJHLW D]D] RSδ[m]) = {o∈O | o∈δ(X), X∈m}, továbbá mat(o) = {x∈M | valamely u∈R P YHOHWL egységre x∈inu vagy x∈outu}. 4. definíció. Legyen δ[m] egy konzisztens döntés leképezés, o = op(δ[m]), m = mat(o)∪m, és δ'[m] = {(X, Y) | X∈m és Y = {i∈o | X∈outi}}. Ekkor δ'[m]

22


döntés leképezés a δ[m] döntés leképezés lezártja. A δ[m] döntés leképezés zárt, ha δ[m] = δ'[m]. 5. definíció. Két konzisztens döntés leképezés ekvivalens, ha a lezártjuk azonos. A szükséges fogalmak bevezetése után megadhatjuk a döntés leképezés és a Pgráf kapcsolatát. 6. definíció. Adott az (m, o) P-gráf. Ha egy m'⊆m halmazra teljesül, hogy minden i∈o-ra outi∩m'≠∅, akkor m'-t az (m, o) P-gráf aktív halmazának nevezzük. 7. definíció. Legyen m' az (m, o) P-gráf aktív halmaza. A δ[m'] = {(X, Y) | X∈m' és Y = {i∈o | X∈outi}} döntés leképezés az (m, o) P-gráfhoz tartozó döntés leképezés. Minden P-gráfhoz tartozó döntés leképezés konzisztens. A fordított kapcsolat bemutatásához tekintsük a δ[m'] konzisztens döntés leképezést. Legyen o = op(δ[m']), és m = mat(o)∪m'. Ekkor (i) az (m, o) P-gráf; (ii) m' az (m, o) P-gráf aktív halmaza; (iii) δ[m'] az (m, o) P-gráfhoz tartozó döntés leképezés. Ez alapján: 8. definíció. Egy δ[m’] konzisztens döntés leképezés P-gráfja (m, o), ahol o = op(δ[m']), és m = mat(o)∪m', és gráf(δ[m'])-mel jelöljük. 9. definíció. Legyenek δ1[m1] és δ2[m2] konzisztens döntés leképezések. A δ1[m1] a δ2[m2] kiterjesztése, δ1[m1] ≥ δ2[m2], ha m1 ⊇ m2 és δ1(X) = δ2(X) minden X∈m2-re. A kiterjesztés reláció parciális rendezés a konzisztens döntés leképezések halmazán.

9.5. ABB algoritmus $ V]NVpJHV HO NpV]OHWL OpSpVHN XWiQ GHILQLiOKDWMXN D J\RUVtWRWW EUDQFKDQG ERXQG DOJRULWPXVW 0LYHO D FpOIJJYpQ\ pV D P YHOHWL HJ\VpJHN PRGHOOMH IHODGDWIJJ D] iOWDOiQRV EUDQFKDQGERXQG OHtUiVQiO )JJHOpN DGRWW PyGRQ használjuk az f, F és G függvényeket, ezek azonban a kombinatorikus módszerek leírásához nem szükségesek. $IRO\DPDWKiOy]DWV]LQWp]LVIHODGDWNRPELQDWRULNXVMHOOHJpE ODGyGyDQDIHODGDW matematikai modellje vegyes-egész programozási feladat: Tegyük fel, hogy adott egy folyamat-hálózatszintézis feladat, amelynek maximális struktúrája n 23


P YHOHWLHJ\VpJHWWDUWDOPD]DIHODGDWGHILQtFLyMiEDQHVHWOHJHVHQV]HUHSO W|EEL P YHOHWLHJ\VpJHOKDJ\KDWy 0LQGHQRiP YHOHWLHJ\VpJKH]KR]]iUHQGHOYHHJ\ yi ELQiULV YiOWR]yW D PHJROGiVRN P YHOHWL HJ\VpJHN PRGHOOMpW O IJJHWOHQ struktúrái, azaz a maximális struktúra részgráfjai, az (y1, y2, ..., yn) vektor DODSMiQHJ\pUWHOP HQPHJKDWiUR]KDWyDN A folyamat-hálózatszintézis feladat matematikai modelljében a további változók D P YHOHWL HJ\VpJHN iOODSRWYiOWR]yL H]HN iOWDOiEDQ IRO\WRQRV YiOWR]yN $ folytonos változók miatt a folyamat-hálózatszintézis feladat lehetséges megoldásainak halmaza általában nem véges, viszont a tervezés szempontjából HOHJHQG KD D VWUXNW~UiMXNEDQ HOWpU PHJROGiVRNDW WHNLQWMN FVDN NO|QE|] QHN $] DGRWW PHJROGiVVWUXNW~UD RSWLPiOLV P N|GpVpQHN PHJKDWiUR]iVD HJ\ MyO HONO|QtWKHW IHODGDW DPHO\ D] DGRWW VWUXNW~UD N|OWVpJpUH NRUOiWRW V]iPROy IJJYpQ\ IHODGDWD (QQHN PHJIHOHO HQ D J\RUVtWRWW EUDQFKDQGERXQG DOJRULWPXV HVHWpQ D * NRUOiWR]y IJJYpQ\U O IHOWpWHOH]]N KRJ\ HJ\ RO\DQ 3i részproblémára, amely struktúrájukban azonos megoldások halmaza, a G(Pi) = F(Pi) összefüggés fennáll. Mivel a kombinatorikusan lehetséges megoldások halmaza véges, ez a feltétel elégséges a gyorsított branch-and-bound algoritmus megállási feltételeként is, továbbá egy Pi UpV]SUREOpPD GHILQLiOiVDNRU HOHJHQG PHJDGQL PHO\ NRPELQDWRULNXVDQ OHKHWVpJHV VWUXNW~UiNDW WDUWDOPD]]D ËJ\ SpOGiXO D NH]G 30 részprobléma az összes kombinatorikusan lehetséges megoldásstruktúrát magában foglalja. A hagyományos branch-and-bound algoritmusok szétválasztó lépése gyakran úgy bontja fel a részproblémákat, hogy az a kombinatorikusan lehetséges struktúrák szerint nem jelent szétválasztást. A gyorsított branch-and-bound algoritmus szétválasztó lépése tér el lényegesen a "hagyományos" vegyes egész típusú matematikai programozási feladatokat megoldó branch-and-bound PyGV]HUHNW O PLYHO D V]pWYiODV]Wy OpSpV D NRPELQDWRULNXVDQ OHKHWVpJHV struktúrákat figyelembe véve történik. A részproblémákat a döntés leképezés segítségével definiáljuk. Egy részproblémához tartozó döntés leképezést a branch-and-bound algoritmus

24


IiMiQDN J\|NHUpW O D UpV]SUREOpPiW UHSUH]HQWiOy FV~FVLJ YH]HW OpSpVHN VRUiQ hozott döntések halmaza adja meg. Az újabb szétválasztó lépés egy újabb döntés

meghozatalát

jelenti,

amely

a

(i)

részproblémához

tartozó

kombinatorikusan lehetséges megoldások particionálását jelenti, (ii) egy újabb NRQ]LV]WHQV G|QWpV OHNpSH]pVW HUHGPpQ\H] DPHO\ D V]O UpV]SUREOpPiKR] tartozó döntés leképezés kiterjesztése. A folyamat-hálózatszintézis feladat megoldásakor a Pi - δi[mi] konzisztens döntés leképezéssel definiált - részproblémát S(δi[mi])-vel jelöljük és azokat a megoldásokat

tartalmazza,

amelyekhez

tartozó

P-gráfnak

az

aktuális

részprobléma döntés leképezése által definiált P-gráf részgráfja és nem WDUWDOPD]QDND]HGGLJLG|QWpVHNNHONL]iUWP YHOHWLHJ\VpJHNHWD]D]6δi[mi]) = {gráf(δk[mk]) | δk[mk] ≥ δi[mi]}. A branch-and-bound fa gyökeréhez a ∅G|QWpVOHNpSH]pVpVHQQHNPHJIHOHO HQ az összes kombinatorikusan lehetséges struktúra tartozik, míg a branch-andbound fa leveleihez tartozó döntés leképezések egy kombinatorikusan lehetséges megoldás P-gráfját adják meg. A szétválasztó függvénynek az aktuális részproblémához tartozó döntés leképezés alapján kell új döntés leképezéseket megadnia úgy, hogy azok az aktuális részproblémához tartozó döntés leképezés kiterjesztései legyenek, és a hozzájuk tartozó részproblémák megfeleljenek a szétválasztó függvény általános definíciójában leírtaknak. A keresés hatékonyságát növeli, hogy a "diszjunkt leszármazottak" tulajdonság is teljesül. Ezek alapján a szétválasztó lépés: keressünk egy olyan anyagot, amely minden S(δi[mi@ EHOL VWUXNW~UD UpV]H GH PpJ QHP YROW G|QWpV D] HO iOOtWiViUyO (]HQ anyagok halmazát az alábbi p leképezés segítségével határozhatjuk meg: p(S(δi[mi])) = (matin(op(δi[mi]))∪P)\(mi∪R), ahol matin(o) = {x∈inu | u∈o}. Ha ilyen anyag nincs, az S(δi[mi]) részproblémában a megoldások struktúrája WHOMHVHQ GHILQLiOW D]D] HJ\pUWHOP tJ\ D NRUOiWR]y IJJYpQ\ WXODMGRQViJiQDN PHJIHOHO HQ HQQpO D UpV]SUREOpPiQiO QLQFV V]NVpJ WRYiEEL V]pWYiODV]WiVUD D részprobléma levél. Ha a p(S(δi[mi])) halmaz nem üres, valamely x elemének kiválasztása után az összes lehetséges módon, a konzisztencia megtartásával,

25


E YtWMN D] 6δi[mi]) részprobléma döntés leképezését, így megkapjuk a UpV]SUREOpPD J\HUHNHLW GHILQLiOy G|QWpV OHNpSH]pVHNHW (O IRUGXOKDW KRJ\ bizonyos anyagok esetén csak egy lehetséges döntést hozhatunk, így nem történik valódi szétválasztás. A maximális neutrális kiterjesztés alkalmazásával >@ H] D] HVHW HONHUOKHW PLQGHQ G|QWpV XWiQ YDODPLQW D NH]G OpSpVEHQ PHJYL]VJiOMXN KRJ\ V]pWYiODV]Wy OpSpV DONDOPD]iVD QpONO WRYiEE E YtWKHW H az aktuális döntés leképezés, majd ezt követi a korlátozó függvény hívása és az esetleges újabb szétválasztás. A maximális neutrális kiterjesztést alkalmazva garantált, hogy az újabb döntések minden esetben valódi szétválasztást eredményeznek. Az ABB algoritmus szétválasztó függvényének pontos definiálásához meg kell adnunk egy "anyagválasztó függvényt" (x = A(S(δi[mi])) ∈ p(S(δi[mi@ DPL OHKHW D OHJNLVHEE LQGH[ DQ\DJ D IHODGDW GHILQtFLy DODSMiQ YDJ\DOHJNHYHVHEEPyGRQHO iOOtWKDWyDQ\DJGHH]OpQ\HJpEHQWHWV] OHJHVD] $%%DOJRULWPXVP N|GpVpWQHPEHIRO\iVROMDOpQ\HJHVHQ Az

ABB

algoritmus

szétválasztó

függvénye

valamely

S(δi[mi])≠∅

részproblémára: son(S(δi[mi])) = {S(δij[mij]) | δk[mk] = {(δi[mi]∪{(x, c)}, x = A(S(δi[mi])), c∈ ℘(∆(x)) \ {∅}, δk[mk] konzisztens, δij a δk maximális neutrális kiterjesztése} Ez a függvény megfelel mint szétválasztófüggvény [16]. A feldolgozásra váró részproblémák közül az aktuális részproblémát kiválasztó NHUHV IJJYpQ\

OHKHW

SpOGiXO

D

KDJ\RPiQ\RV

EUDQFKDQGERXQG

DOJRULWPXVRNQiO LV DONDOPD]RWW GHSWKILUVW VWUDWpJLiQDN PHJIHOHO HQ YiODV]Wy függvény. Ezzel definiáltuk a folyamat-hálózatszintézis feladat megoldására kidolgozott gyorsított branch-and-bound szétválasztó lépését, amely a feladat matematikai PRGHOOMpW O IJJHWOHQO PLQGHQ IRO\DPDWKiOy]DWV]LQWp]LV IHODGDW PHJROGiViUD alkalmazható. $ G|QWpV OHNpSH]pV DODSMiQ HJ\ DGRWW UpV]SUREOpPiQiO SROLQRPLiOLV LG EHQ meghatározhatjuk a részproblémához tartozó összes megoldásstruktúrában V]HUHSO P YHOHWL HJ\VpJHNHW D NL]iUW P YHOHWL HJ\VpJHNHW pV D YiODV]WKDWy P YHOHWL HJ\VpJHNHW (]HN VHJtWVpJpYHO D P YHOHWL HJ\VpJHN PRGHOOMpW pV KD

26


szükséges valamilyen relaxáló módszert felhasználva, már meghatározható a korlátozó függvény.

27


10. A folyamat-hálózatszintézis feladat kiterjesztései $] HO ] IHMH]HWEHQ LVPHUWHWHWW $%% DOJRULWPXV DONDOPDV DODSYHW YiOWR]WDWiV nélkül több feladatosztály megoldására is, sok feladattípus megoldható a NRUOiWR]y HOMiUiV PyGRVtWiViYDO D PHJROGiV NHUHVpVpW YH]pUO DOJRULWPXV kombinatorikus lépéseinek módosítása nélkül. Az ABB algoritmus ezeken kívül sok olyan feladatosztály megoldásának alapjául is szolgálhat, amelyek hatékony megoldása az algoritmus lényegi módosítása nélkül nem lehetséges. Ebben a fejezetben az alap folyamat-hálózatszintézis feladat kiterjesztéseivel foglalkozunk, a kiterjesztések mint feladatosztályok megoldására szolgáló módszereket mutatunk be, amelyek mindegyike az ABB algoritmusra épül. Ezekben a feladatosztályokban már a megoldásstruktúra definíciója is PyGRVXOKDW HQQHN PHJIHOHO HQ YiOWR]QDN iOWDOiEDQ E YOQHN D megoldásstruktúrák tulajdonságait leíró axiómák és így az ABB algoritmus OpQ\HJL YH]pUO UpV]H LV $ IHMH]HWEHQ EHPXWDWRWW NLWHUMHV]WpVHN N|]O D] HOV NHWW LVLO\HQWtSXV~$]HOV D]DODSIHODGDWEDQGHILQLiOWN|WHOH] HQHO iOOtWDQGy termékek mellett a megoldásstruktúra összes lehetséges outputját megadja, míg D PiVRGLN NLWHUMHV]WpVEHQ PiU D WHUYH]pV VRUiQ EL]RQ\RV HJ\V]HU VtWHWW irányíthatósági megkötéseket veszünk figyelembe. $ KDUPDGLN NLWHUMHV]WpV HOWpU D] HO ] HNW O D UHQGV]HUW DONRWy P YHOHWL egységek matematikai modellje változik lényegesen, a megoldásstruktúrák definíciója változatlan marad. Ennek a feladatosztálynak a megoldása lehetséges az $%% DOJRULWPXV YH]pUO UpV]pQHN YiOWR]WDWiVD QpONO XJ\DQDNNRU HEEHQ D] esetEHQ D NRUOiWR]y HOMiUiV D P YHOHWL HJ\VpJHN V]DNDV]RVDQ IRO\WRQRV QHP konkáv költségfüggvénye miatt önmagában is nehéz feladat, lényegében egy újabb branch-and-bound algoritmus szükséges a megoldásához. Az ismertetett módszer ezt a második branch-and-bound algoritmust integrálja az ABB algoritPXVEDOHKHW YpWpYHDIHODGDWNRPELQDWRULNXVMHOOHJpQHNMREENLKDV]QiOiViW

28


$ QHJ\HGLN NLWHUMHV]WpV OpQ\HJpEHQ D PHJROGy PyGV]HU WHFKQLNDL MHOOHJ NLWHUMHV]WpVpW MHOHQWL LWW D] $%% DOJRULWPXV SiUKX]DPRV P N|GpVL HOY számítógépeken futtatható változatát mutatjuk be. Mind az itt ismertetett, mind további kiterjesztések [13, 19, 22] – például többOpSFV V

PXOWLSHULyGLNXV

IRO\DPDWKiOy]DWV]LQWp]LV

KLEDW U

irányítórendszerrel integrált folyamat-hálózatszintézis – kombinált alkalmazása lehetséges. Így az ABB algoritmusra alapozva akár olyan módszer is PHJDGKDWy DPHO\ W|EEOpSFV V KXOODGpNNH]HOpVVHO LQWHJUiOW IRO\DPDW hálózatszintézis feladatot old meg szakaszosan folytonos költségfüggvénnyel DGRWWP YHOHWLHJ\VpJHNHVHWpQ7HUPpV]HWHVHQH]DPyGV]HULVPHJYDOyVtWKDWy párhuzamos feldolgozású számítógépeken.

10.1. Hulladékkezeléssel integrált folyamathálózatszintézis Mint azt már korábban definiáltuk, a folyamat-hálózatszintézis alapfeladata a UHQGHONH]pVUH iOOy P YHOHWL HJ\VpJHN HJ\ UpV]KDOPD]iQDN pV D]RN P N|GpVL paramétereinek megkeresése, amelyek azt a hálózatot alkotják, amely a kívánt WHUPpNHNHWPLQLPiOLVN|OWVpJJHOiOOtWMDHO (]PiU|QPDJiEDQLVQHKp]IHODGDW UpV]EHQ D NRPELQDWRULNXV MHOOHJH UpV]EHQ D P YHOHWL HJ\VpJHN HVHWOHJHVHQ bonyolult matematikai modellje miatt. A hulladékkezeléssel integrált folyamat-hálózatszintézis feladat megoldása az alapfeladatnál is bonyolultabb, hiszen kombinatorikus szempontból a termék J\iUWiViEDQUpV]WYHY P YHOHWLHJ\VpJHNPHOOHWWHJ\LGHM OHJDKXOODGpNNH]HO UHQGV]HU P YHOHWL HJ\VpJHLW LV NL NHOO YiODV]WDQL PDWHPDWLNDL SURJUDPR]iVL szempontból a részfeladatok mérete és száma is nagyobb. Mint az irodalmi áttekintésben is bemutattuk, az eddig kidolgozott módszerek ennél az összetett feladatnál nem integrálták teljesen a termékgyártást és a hulladékkezelést, azaz két kisebb folyamat-hálózatszintézis feladatként oldották meg a feladatot. Mivel a két rész nem független, ez a megközelítés könnyen eredményezhet az optimális megoldásnál lényegesen rosszabb megoldást, egy ROFVyEE WHUPHO KiOy]DWKR] WHUYH]HWW KXOODGpNNH]HO UHQGV]HU OpQ\HJHVHQ GUiJiEEiWHKHWLDNRPSOHWWPHJROGiVWPLQWKDDWHUPHO UpV]V]HPSRQWMiEyOHJ\

29


költségesebb megoldást választottunk volna. Nyilvánvaló, hogy optimális megoldást csak az együttes tervezés adhat. A hulladékkezeléssel integrált folyamat-hálózatszintézis feladat megoldására kidolgoztuk az ABB algoritmus módosított változatát [15, 39]. $] DODS IRO\DPDWKiOy]DWV]LQWp]LV IHODGDWKR] KDVRQOyDQ D P YHOHWL HJ\VpJHN modellezésével itt sem foglalkozunk, bár fontos feladat, továbbra is IHOWpWHOH]]N KRJ\ PHJIHOHO WHFKQLNiN HUUH UHQGHONH]pVUH iOOQDN pV D NpV] KiOy]DWRN RSWLPiOLV P N|GpVpW LV PHJKDWiUR]y N|OWVpJIJJYpQ\V]iPtWiV (valamely matematikai programozási módszer) is adott. $UHQGHONH]pVUHiOOyPiUPHJpStWHWW P YHOHWLHJ\VpJHNN|OWVpJIJJYpQ\pQHN PHJIHOHO PyGRVtWiViYDO D NLGROJR]RWW PyGV]HU DONDOPDV PiU PHJOHY rendszerek hulladékkezeléssel integrált újratervezésére, ha szükséges a WHUPHO UHQGV]HUWLVPyGRVtWYD 10.1.1. Feladat definíció A

hulladékkezeléssel

integrált


a

folyamat-

KiOy]DWV]LQWp]LV DODSIHODGDWiW D WHOMHV RXWSXW GHILQtFLyYDO E YtWL $ V]NVpJHV termékek megadásán túl a további output anyagoknak is teljesíteniük kell további feltételeket. %L]RQ\RV DQ\DJRN QHP OHKHWQHN PHJROGiV RXWSXWMDL H]HNHW N|]EOV anyagoknak nevezzük. Az általánosságra törekedve a termékek mellett megengedett outputokat tovább osztályozzuk kibocsátható anyagokra és OHKHWVpJHV WHUPpNHNUH ËJ\ D VWUXNW~UiNEDQ HO IRUGXOy DQ\DJRNDW FVRSRUWED sorolhatjuk. A nyersanyagok pV D N|WHOH] HQ J\iUWDQGy termékek definíciója azonos az alapfeladat definíciójában leírtakkal. .|]EOV DQ\DJ nem lehet megoldás outputja. A lehetséges termékek és a kibocsátható anyagok OHKHWQHN D UHQGV]HU RXWSXWMDL DPtJ D] HO EEL J\iUWiVD HVHWpQ pUWpNHVtWKHW WHUPpNQHN PLQ VO D]D] FV|NNHQWKHWL D PHJROGiV N|OWVpJpW DGGLJ D NLERFViWKDWyDQ\DJRNJ\iUWiVDDNRQNUpWIHODGDWFpOIJJYpQ\pW O IJJ HQ DNiU növelheti is a költségeket: ezen anyagok gyártása megengedett, de EQWHW N|OWVpJHW HUHGPpQ\H]KHW $ KXOODGpNNH]HOpVVHO LQWHJUiOW IRO\DPDW KiOy]DWV]LQWp]LV IHODGDWD D P YHOHWL HJ\VpJHN HJ\ RO\DQ UpV]KDOPD]iQDN

30


PHJNHUHVpVH D PHJIHOHO iOODSRWYiOWR]yNNDO DPHO\HNE O IHOpSO KiOy]DW (megoldás) az adott inputok (nyersanyagok) segítségével a kért outputokat WHUPpNHN PLQLPiOLVN|OWVpJJHOiOOtWMDHO WRYiEEiDKiOy]DWQDNQHPRXWSXWMD N|]EOV DQ\DJ WtSXV~ DQ\DJ (] D IHODGDW GHILQLiOKDWy D WHUPpNHN D OHKHWVpJHV WHUPpNHN D Q\HUVDQ\DJRN D N|]EOV DQ\DJRN pV D P YHOHWL egységek megadásával. A megoldások struktúráinak reprezentációjára az alapesethez hasonlóan a PJUiIRW KDV]QiOMXN D NO|QE|] WtSXV~ DQ\DJRN PHJNO|QE|]WHWpVpUH KDV]QiOW szimbólumokat a 2. ábra mutatja.

Nyersanyag Termék Lehetséges termék Kibocsátható termék .|]EOV DQ\DJ 2. ábra. Az öt anyagcsoport szimbólumai a P-gráf reprezentációban.

Illusztrációként a 3. ábra az A, B, C nyersanyagokból H terméket gyártó struktúra P-gráfját mutatja be, amelynek a termék mellett a G lehetséges termék és a D kibocsátható anyag az outputja. B C

A 1 D

2 F

E

G

3

H

3. ábra. Az ({A,B,C,D,E,F,G,H}, {1,2,3}) P-gráf.

10.1.2. Kombinatorikusan lehetséges struktúrák A módosított feladat definíció miatt nyilván változik a megoldások halmaza is. $ PHJROGiV KiOy]DWRNEDQ EL]RQ\RV P YHOHWL HJ\VpJHN PiU QHP GLUHNW YDJ\ LQGLUHNWPyGRQDWHUPpNJ\iUWiViWV]ROJiOMiNKDQHPD]LQWHJUiOWKXOODGpNNH]HO 31


UHQGV]HU UpV]HL (QQHN PHJIHOHO HQ D PHJROGiVRN VWUXNW~UiL LV PyGRVXOQDN azaz a kombinatorikusan lehetséges megoldások halmaza is eltér, így a tulajdonságaikat hulladékkezeléssel

definiáló

axiómákat

integrált

is

módosítanunk

kell.


A

feladat

megoldásstruktúráit leíró módosított axiómák az alábbiak: (SW1) Minden termék része a struktúrának. (SW2) (J\DVWUXNW~UiEDQV]HUHSO DQ\DJDNNRUpVFVDNDNNRUQ\HUVDQ\DJ KDHJ\HWOHQDVWUXNW~UiEDQV]HUHSO P YHOHWLHJ\VpJVHPiOOtWMDHO (SW3) 0LQGHQ D VWUXNW~UiEDQ V]HUHSO P YHOHWL HJ\VpJ D IRO\DPDW hálózatszintézis feladatban definiált. (SW4) Minden D VWUXNW~UiEDQ V]HUHSO \ P YHOHWL HJ\VpJUH OpWH]LN XWDN VRUR]DWDDKROD]\P YHOHWLHJ\VpJHWUHSUH]HQWiOyFV~FVD]HOV ~W HOHMH D] XWROVy ~W YpJH YDODPHO\ OHKHWVpJHV WHUPpNHW HO iOOtWy P YHOHWL HJ\VpJHW UHSUH]HQWiOy FV~FV PLQGHJ\LN ~W HOV pV XWROVy HOHPHP YHOHWLHJ\VpJHWUHSUH]HQWiOyFV~FVPLQGHJ\LN~WQDNN|]|V D] HOHMH YDJ\ D YpJH D N|YHWNH] ~WWDO pV D] XWDNEDQ QLQFV N|]|V anyagot reprezentáló csúcs. (SW5) Ha egy anyag része a struktúrának, akkor létezik a struktúrában RO\DQP YHOHWLHJ\VpJDPHO\QHND]LQSXWMDYDJ\RXWSXWMD (SW6) +DYDODPHO\DQ\DJRWQHPGROJR]IHOHJ\HWOHQP YHOHWLHJ\VpJVHP DNNRUD]QHPN|]EOV DQ\DJWtSXV~ Mint látható az (SW1), (SW2), (SW3) és (SW5) axiómák azonosak az (S1), (S2), (S3) és (S5) axiómákkal, az általuk definiált tulajdonságok erre a feladatosztályra is érvényesek. Az alapesetben az (S4) axióma biztosította, hogy FVDN WHUPpN J\iUWiViEDQ UpV]WYHY P YHOHWL HJ\VpJHN V]HUHSHOMHQHN D YL]VJiOW VWUXNW~UiNEDQ $ KXOODGpNNH]HOpVVHO YDOy LQWHJUiOiV PLDWW LWW D WHUPHO P YHOHWL HJ\VpJHN PHOOHWW KXOODGpNNH]HO P YHOHWL HJ\VpJHNHW LV PHJ NHOO engednünk. Az (SW4) axiómát a 2. példa szemlélteti. $]~MRQQDQEHYH]HWHWW6: D[LyPDDN|]EOV DQ\DJNpQWGHILQLiOWDQ\DJRNDW kibocsátó struktúrákat zárja ki a lehetséges megoldásstruktúrák közül.

32


2. példa. Tekintsük a P1 terméket az R1, R2, R3, R4 nyersanyagokból az 1. WiEOi]DWEDQ DGRWW P YHOHWL HJ\VpJHN VHJtWVpJpYHO HO iOOtWy KXOODGpNV]LQWp]LVVHO integrált folyamat-hálózatszintézis feladatot. Mivel a példát a strukturális WXODMGRQViJRNV]HPOpOWHWpVpUHKDV]QiOMXNDP YHOHWLHJ\VpJHNHWFVDND]LQSXW output halmazaikkal adjuk meg, pontosabb modellezésükkel nem foglalkozunk. $ IHQW HPOtWHWW DQ\DJRNRQ NtYO D : N|]EOV DQ\DJ D W|EEL D]D] ' ' D3, D4 és D5 kibocsátható anyagok. WiEOi]DW$SpOGDP YHOHWLHJ\VpJHL

# 1 2 3 4 5 6

Input R1, D3 D3 W1, D4 D5 R2, R3 R4

Output P1 P1 D1 D2 D3, W1 D4, D5

7HNLQWVQNHJ\DIHQWLP YHOHWLHJ\VpJHNE OpStWHWWVWUXNW~UiWDPHO\D4. ábrán látható. Az SW1, SW2, SW3, SW5, és SW6 axiómáknak nyilván megfelel a VWUXNW~UD 9L]VJiOMXN PHJ KRJ\ D VWUXNW~UiEDQ V]HUHSO P YHOHWL HJ\VpJHN PHJIHOHOQHNH D] 6: D[LyPD IHOWpWHOHLQHN $ WiEOi]DW D P YHOHWL HJ\VpJHNKH] WDUWR]y D] 6: D[LyPD IHOWpWHOHLQHN PHJIHOHO ~WVRUR]DWRNDW tartalmazza. R3

R2

R4

6

5

P1

D3

W1

2

3

D5

D4

4

D1

D2

4iEUD$SpOGDP YHOHWLHJ\VpJHLE OiOOy3JUiI

33

A folyamat-hálózatszintézis feladat kiterjesztései WiEOi]DW$SpOGDP YHOHWLHJ\VpJHLKH]WDUWR]y~WVRUR]DWRN

P YHOHWL egység 2 3 4 5 6

útsorozat (2) (5,3), (5,2) (4),(6,4), (6,3), (5,3), (5,2) (5,2) (6,3), (5,3), (5,2)

Mivel a többi axiómát is teljesíti a 4. ábrán látható struktúra, ezért NRPELQDWRULNXVDQ OHKHWVpJHV VWUXNW~UD $ VWUXNW~UiEDQ D pV D] P YHOHWL HJ\VpJ V]HUHSH D WHUPpN J\iUWiVD D P YHOHWL HJ\VpJ PiU D VWUXNW~UD KXOODGpNNH]HO UpV]pKH] WDUWR]LN D : N|]EOV DQ\DJRW GROJR]]D IHO $ P YHOHWLHJ\VpJDKXOODGpNIHOGROJR]iVKR]V]NVpJHV'DQ\DJRWiOOtWMDHO PtJ D P YHOHWL HJ\VpJ D ' DQ\DJRW GROJR]]D IHO (] D P YHOHWL HJ\VpJ HJ\ kibocsátható anyagot dolgoz fel, azaz elhagyható lenne, viszont a D5 anyag helyett a D2 kibocsátását indokolttá teheti a költségfüggvény. Az alapesethez hasonlóan itt is azon struktúrákat nevezzük kombinatorikusan lehetségesnek, melyek P-gráfjai megfelelnek az axiómáknak. Az 5. ábra egy kombinatorikusan nem lehetséges struktúrát mutat be (azaz a struktúra nem lehet optimális megoldás struktúrája).

5iEUD$]6:D[LyPiWQHPWHOMHVtW VWUXNW~UD3JUiIMD

10.1.3. MSGW algoritmus $] 6: 6: 6: D[LyPiN GUDV]WLNXVDQ FV|NNHQWLN D]RQ P YHOHWL egység-kombinációk számát, amelyeket lehetséges megoldásként figyelembe kell vennünk a hulladékkezeléssel integrált folyamat-hálózatszintézis során. Az

34


alap folyamat-hálózatszintézis feladathoz hasonlóan az itt vizsgált feladatosztály PHJROGiVDLLV]iUWDND]XQLyP YHOHWUH 1. tétel. A hulladékkezeléssel integrált folyamat-hálózatszintézis feladat PHJROGiVVWUXNW~UiL]iUWDND]~QLyP YHOHWUH %L]RQ\tWiV (OHJHQG PHJPXWDWQL KRJ\ NpW PHJROGiVVWUXNW~UD 3JUiIMiQDN (jelölje ezeket P1, illetve P2) uniójaként kapott P-gráf is teljesíti az SW1-SW6 axiómákat, azaz szintén kombinatorikusan lehetséges struktúrát reprezentál. SW1: A P1∪P2 gráf tartalmazza mind a P1, mind a P2 gráf csúcsait, tehát tartalmazza a termékeket is. 6:6HPD3VHPD3JUiIQHPWDUWDOPD]Q\HUVDQ\DJWtSXV~FV~FVEDYH]HW élet, így ez teljesül a P1∪P2 gráfra is. SW3: Nyilvánvalóan teljesül. 6:+DHJ\P YHOHWLHJ\VpJWtSXV~FV~FVUpV]HD3∪P2 gráfnak, akkor eleme D3YDJ\D3JUiIQDN'HHNNRUD]6:D[LyPDIHOWpWHOHLWWHOMHVtW 3YDJ\3 gráfbeli útsorozat is része a P1∪P2 gráfnak, azaz a P1∪P2 gráf is tejesíti az axióma feltételeit. SW5: Nyilvánvalóan teljesül. 6: 0LYHO VHP D 3 VHP D 3 JUiI QHP WDUWDOPD] RO\DQ N|]EOV DQ\DJ WtSXV~ FV~FVRW DPHO\E O QLQFV NLYH]HW pO P YHOHWL HJ\VpJ WtSXV~ FV~FVKR] ezért ilyen csúcs a P1∪P2 gráfban sincs. Az alapesettel analóg módon tehát létezik maximális struktúra, amely itt is megadja a minimális keresési teret az optimális megoldás kereséséhez. A PD[LPiOLV VWUXNW~UD JHQHUiOiViUD NLGROJR]WXN D SROLQRPLiOLV LGHM 06*: algoritmust, amely az alap folyamat-hálózatszintézis feladatra kidolgozott MSG algoritmus kiterjesztése. A 6 iEUD D] 06*: DOJRULWPXV 3LGJLQ $OJRO Q\HOY változatát mutatja be. 10.1.4. Az algoritmus helyességének bizonyítása $] DOJRULWPXV NpW I UpV]E O iOO D] HOV UpV]EHQ D] VW XWDVtWiVLJ D]RQ P YHOHWL HJ\VpJHN NL]iUiVD W|UWpQLN DPHO\HN EL]WRVDQ QHP OHKHWQHN

35


Input: ODP YHOHWLHJ\VpJHNKDOPD]D M: az anyagok halmaza IDN|]EOV DQ\DJRNKDOPD]D Pr: a termékek halmaza Pp: a lehetséges termékek halmaza R: a nyersanyagok halmaza Jelölések: o⊆O, matin(o)={x∈M | u∈o, x∈inu}, matout(o)={x∈M | u∈o, x∈outu} m⊆M, opin(m)={u∈O | m∈outu}, opout(o)={u∈O | m∈inu} Azaz az opin, matinIJJYpQ\HNHJ\FV~FVKDOPD]EDEHM|Y pOHNNH]G SRQWMDLQDNKDOPD]iWPtJD]RSout, matout függvények egy csúcshalmazból kiinduló élek végpontjainak halmazát határozzák meg.

procedure msg_w(): begin st1: O := O\opin(R); rp1: repeat st2: M := matin(O)∪matout(O); r := matin(O)\(matout(O)∪R); wh1: while r is not empty do begin x∈r; M := M\{x}; o := opout(x); O := O\o; r := (r∪(matout(o)\matout(O)))\{x}; end; co1: if Pr∩M ≠ Pr then stop; comment: there is no maximal structure st3: Pp := Pp∩M; r := (I∩M)\matin(O); ow := ∅; wh2: while r is not empty do begin x∈r; M := M\{x}; o := opin(x); O := O\o; r := (r∪((matin(o)\matin(O))∩I))\{x}; ow := ow∪o; end; until ow = ∅; st4: p := (Pr∪Pp); Ou := ∅; Od := ∅; mu := ∅; md := ∅; r := ∅; rp2: repeat wh3: while p is not empty do begin x∈p; mu := mu∪{x}; ox := opin(x)\Ou; r :=r∪(matout(ox\Od)\({x}∪md));

wh4:

Ou := Ou∪ox; p := (p∪matin(ox))\(R∪mu); end; while r is not empty do begin x∈r; md := md∪{x}; ox := opout(x)\Od; p := p∪(matin(ox\Ou)\({x}∪R∪mu));

Od := Od∪ox; r := (r∪matout(ox))\md; end; until p is empty; st5: Or := Ou∪Od; st6: Mr := matin(Or)∪matout(Or); write( Mr, Or ); end; 6. ábra. Az MSGW algoritmus.

36


megoldásstruktúra részei, a második rész a maximális struktúra felépítése. A ZK FLNOXV D QHP HO iOOtWKDWy QHP Q\HUVDQ\DJ LQSXWRW KDV]QiOy P YHOHWL egységeket törli, ez a ciklus az alap folyamat-hálózatszintézis feladathoz kidolgozott MSG algoritmusnak is része. A wh2 ciklus a nem felhasználható N|]EOV DQ\DJRNDW HO iOOtWy P YHOHWL HJ\VpJHNHW ]iUMD NL D WRYiEEL vizsgálatból. Mivel ez a két ciklus nem független (mindegyik ugyanabból az O P YHOHWL HJ\VpJ KDOPD]EyO W|U|O HOHPHNHW SpOGiXO HJ\ P YHOHWL HJ\VpJHW D ZK FLNOXVEDQ W|U|OYH LVPpW OHKHWVpJHV RO\DQ P YHOHWL HJ\VpJ DPHO\QHN YDODPHO\QHPQ\HUVDQ\DJLQSXWMDQHPHO iOOtWKDWyH]pUWDGGLJLVPpWHOMN NHW US DPtJHJ\LNFLNOXVVHPW|U|O~MDEEP YHOHWLHJ\VpJHW $ZKFLNOXVHO V]|UDWHUPpNHNHWHO iOOtWyP YHOHWLHJ\VpJHNHWKDWiUR]]DPHJ pV DGMD KR]]i D PD[LPiOLV VWUXNW~UD P YHOHWL HJ\VpJHLQHN KDOPD]iKR] D NpV EELHNEHQ D ZK FLNOXVW N|YHWYH D] US LVPpWHOW IXWiVDNRU D PD[LPiOLV VWUXNW~UiED D ZK FLNOXVEDQ IHOYHWW KXOODGpNNH]HO P YHOHWL HJ\VpJHN LQSXWMDLWHO iOOtWyP YHOHWLHJ\VpJHNHWKDWiUR]]DPHJ$ZKFLNOXVDZKiOWDO NLYiODV]WRWWP YHOHWLHJ\VpJHNRXWSXWMDLWIHOGROJR]y KXOODGpNNH]HO P YHOHWL egységeket adja meg. 0LYHODP YHOHWLHJ\VpJHNKDOPD]DYpJHVYDODKiQ\OpSpVXWiQ~MDEEP YHOHWL HJ\VpJ QHP YiODV]WKDWy NL $ N|]EOV DQ\DJRNDW IHOKDV]QiOy LOOHWYH D QHP Q\HUVDQ\DJLQSXWRWJ\iUWyP YHOHWLHJ\VpJHNOpWH]pVpWD]USFLNOXVJDUDQWiOMD 2. tétel$]06*:DOJRULWPXVYpJHVpVSROLQRPLiOLVLG EHQYpJHWpU %L]RQ\tWiV 0LYHO D] DOJRULWPXV QHP KtY PHJ NOV DOJRULWPXVRNDW pV QHP UHNXU]tYHOHJHQG EHOiWQLKRJ\DFLNOXVRNYpJHVHNpVPLQGHQFLNOXVOHKHWVpJHV LVPpWOpVHLQHNV]iPDSROLQRPLiOLVDP YHOHWLHJ\VpJHNV]iPiWWHNLQWYH A wh1 és wh2 ciklusokban a véges O P YHOHWL HJ\VpJ KDOPD]EyO HOHPHNHW törlünk, ezért a két ciklus és így az rp1 ciklus végrehajtása is csak véges sokszor LVPpWO GKHWKDD]O üres az opin illetve opout halmazok is üresek). A wh3 ciklus minden ismétlésekor az OuKDOPD]E YOPtJDZKFLNOXVEDQD] Od KDOPD] 0LYHO D OHKHWVpJHV P YHOHWL HJ\VpJHN V]iPD YpJHV D] DOJRULWPXV HOV UpV]pKH] KDVRQOyDQ D ZK ZK US FLNOXVRN LV FVDN YpJHV VRNV]RU LVPpWO GQHN D] DOJRULWPXVEDQ D P YHOHWHN V]iPD SROLQRPLiOLV D P YHOHWL egységek számát tekintve.

37


3. tétel. Az rp2 ciklus i. futásakor az Ou KDOPD]ED D]RQ P YHOHWL HJ\VpJHN NHUOQHN DPHO\HNE O OpWH]LN L ~WEyO iOOy D] 6: D[LyPD IHOWpWHOHLQHN PHJIHOHO ~WVRUR]DW +DVRQOyDQ D] 2d KDOPD]ED D]RQ P YHOHWL HJ\VpJHN NHUOQHN DPHO\HNE O OpWH]LN L ~WEyO iOOy D] 6: D[LyPD IHOWpWHOHLQHN PHJIHOHO ~WVRUR]DW Bizonyítás: Az rp2 ciklus 1. lefutása után (i=1): (i) Az OuKDOPD]D]RQP YHOHWLHJ\VpJHNHWWDUWDOPD]]DDPHO\HNUHOpWH]LNHJ\ OHKHWVpJHV WHUPpNKH] YH]HW ~W Q\LOYiQYDOy D ZK FLNOXV D] U KDOPD]W PyGRVtWyXWDVtWiVWHOKDJ\YDD]RQRVD]06*DOJRULWPXV>@pStW UpV]pYHO (ii) Az OdKDOPD]HOHPHLE ONpWD]6:D[LyPDIHOWpWHOHLQHNPHJIHOHO XWDW megadva eljuthatunk egy (lehetséges) termékhez: az r halmaz a wh4 ciklus indulásakor azokat az x anyagokat tartalmazza, amelyeket valamely y∈Ou P YHOHWL HJ\VpJ iOOtW HO pV OpWH]LN RO\DQ ~W \EyO OHKHWVpJHV WHUPpNKH] amelynek x nem része. Mivel a wh4 ciklusban OdHOHPHLD]UHOHPHLE ONLLQGXOy XWDNP YHOHWLHJ\VpJHLOHV]QHNDIHQWLLL iOOtWiVWHOMHVODWpWHOL UHLJD] Tegyük fel, hogy az állítás igaz i-1-re. Ekkor az rp2 ciklus i-1. végrehajtása után a p halmaz elemei azon x anyagok lesznek, amelyek egy olyan y∈Od P YHOHWL HJ\VpJ LQSXWMDL DPHO\KH] OpWH]LN HJ\L~WEyOiOOyOHKHWVpJHV WHUPpNKH]YH]HW ~WVRUR]DWS1, p2, ..., p2i-2) és x H]HNHJ\LNpQHNVHPHOHPHËJ\DZKFLNOXVN|YHWNH] IXWiVDNRUSRQWRVDQD]RN D]P YHOHWLHJ\VpJHNNHUOQHND]2u halmazba, amelyekre a [z, ..., x, y], p1, p2, ..., p2i-2 útsorozat megfelel az SW4 axióma feltételeinek. Az i=1 esethez KDVRQOyDQ EHOiWKDWy D ZK FLNOXVEDQ IHOYHWW P YHOHWL HJ\VpJHNUH D] HJJ\HO hosszabb útsorozat létezése. 4. tétel. Az MSGW algoritmus által meghatározott (Mr, Or) struktúra kombinatorikusan lehetséges. Bizonyítás: Megmutatjuk, hogy az (Mr, Or) struktúra teljesíti az axiómákat. SW1: Mivel a wh3 ciklus kezdetén minden termék eleme a p halmaznak, a ciklus befejezésekor az Ou KDOPD] P YHOHWL HJ\VpJHL J\iUWMiN D] |VV]HV terméket, így az st6 utasítás után minden termék eleme lesz az Mr halmaznak.

38


6: $ Q\HUVDQ\DJRNDW J\iUWy P YHOHWL HJ\VpJHNHW D] VW XWDVtWiV NL]iUMD D vizsgálatból. A wh1 ciklus indulásakor az r halmaz azon nem nyersanyagok halmaza, amelyet az aktuális O P YHOHWL HJ\VpJ KDOPD] HOHPHL IHOKDV]QiOQDN GH QHP iOOtWDQDN HO (] D WXODMGRQViJ D FLNOXV IXWiVD VRUiQ LJD] FLNOXV LQYDULiQV D FLNOXV FpOMD D] LO\HQ DQ\DJRNDW IHOKDV]QiOy P YHOHWL HJ\VpJHN NLV] UpVH D PD[LPiOLV VWUXNW~UD OHKHWVpJHV P YHOHWL HJ\VpJHL N|]O $ ZK FLNOXV EHIHMH] GpVHNRU WHKiW QLQFV LO\HQ DQ\DJ $] US FLNOXV DNNRU IHMH] GLN EHDPLNRUDZKFLNOXVXWiQDZKFLNOXVQHPW|U|O~MDEEP YHOHWLHJ\VpJHNHW tJ\H]D]USFLNOXVLQGXOiVDNRULVLJD]D]D]PLQGHQ P YHOHWL HJ\VpJ PLQGHQ LQSXWMDYDJ\Q\HUVDQ\DJYDJ\HO iOOtWKDWyPiVP YHOHWLHJ\VpJHNNHOËJ\H]D wh3 ciklusban minden Ou, illetve a wh4 ciklusban minden Od halmazba felvett P YHOHWLHJ\VpJPLQGHQLQSXWMiUDLVLJD]D]D]2r minden elemére is. SW3: Nyilvánvalóan teljesül. SW4: A 3WpWHOE ON|YHWNH]LN SW5: Nyilvánvalóan teljesül. 6: $ ZK FLNOXV D P YHOHWL HJ\VpJHN RXWSXWMDLW IHOGROJR]y P YHOHWL egységeket felveszi a maximális struktúrába, a wh2 ciklus garantálja, hogy ez N|]EOV DQ\DJWtSXV~RXWSXWUDPLQGLJOHKHWVpJHV 5. tétel. Az MSGW algoritmus által generált struktúra a feladat maximális struktúrája. %L]RQ\tWiV7HJ\NIHOKRJ\OpWH]LNRO\DQXP YHOHWLHJ\VpJDPHO\QHPHOHPH Or-nak, de eleme valamely kombinatorikusan lehetséges megoldásstruktúrának. +D HJ\ P YHOHWL HJ\VpJHW D PD[LPiOLV &)& VWUXNW~UD OHKHWVpJHV P YHOHWL egységei közül az st1 utasítás zár ki, az nyersanyagként definiált anyagot állít HO tJ\D]6: D[LyPDV]HULQWQHPOHKHWPHJROGiVUpV]H$WRYiEELP YHOHWL egységeket kizáró utasítások a ciklusokon belül vannak, ezért mindig azt kell megvizsgálnunk, hogy az Or illetve OP YHOHWLHJ\VpJKDOPD]DNWXiOLVP YHOHWL HJ\VpJHLW WHNLQWYH LQGRNROWH D] X P YHOHWL HJ\VpJ NL]iUiVD D WRYiEEL vizsgálatból. +DD]USFLNOXVEDQW|U|OWND]XP YHOHWLHJ\VpJHWDNNRUYDJ\D]OP YHOHWL HJ\VpJKDOPD]HOHPHLYHOHO QHPiOOtWKDWyQHPQ\HUVDQ\DJLQSXWMDYDQW|UOpVD

39


wh1 ciklusban), vagy az O P YHOHWL HJ\VpJ KDOPD] HOHPHLYHO QHP IHOGROJR]KDWyN|]EOV DQ\DJWtSXV~RXWSXWMDYDQW|UOpVDZKFLNOXVEDQ WHKiW nem lehet része az O P YHOHWL HJ\VpJ KDOPD] HOHPHLE O NpS]HWW megoldásstruktúrának. Ha az u része valamely kombinatorikusan lehetséges struktúrának, akkor létezik HJ\D]6:D[LyPDIHOWpWHOHLQHNPHJIHOHO QKRVV]~~WVRUR]DWHNNRUD]RQEDQ az rp2 ciklus n/2-ik végrehajtásakor u-nak be kellett kerülnie az Ou vagy az Od P YHOHWLHJ\VpJKDOPD]EDDPLHOOHQWPRQGiVUDYH]HW 6. tétel. Az MSGW algoritmus akkor és csak akkor nem ad struktúrát eredményként, ha feladathoz nem létezik maximális struktúra. Bizonyítás: Az algoritmus szerint nincs maximális struktúra, ha az algoritmus végrehajtása során egy O P YHOHWL HJ\VpJ KDOPD]UD D FR IHOWpWHO WHOMHVO Ekkor az O P YHOHWL HJ\VpJ KDOPD] HOHPHLE O Q\LOYiQ QHP DGKDWy PHJ megoldásstruktúra. A 5. tétel bizonyításában megmutattuk, hogy a törölt P YHOHWLHJ\VpJHNQHPOHKHWQHNHJ\HWOHQPHJROGiVVWUXNW~UDUpV]HLVHPtJ\D] LQSXWNpQW DGRWW P YHOHWL HJ\VpJ KDOPD] HOHPHLE O VHP DGKDWy PHJ megoldásstruktúra, így a feladatnak nem létezik megoldása, és ezzel együtt maximális struktúrája sem. A 5 WpWHOE O N|YHWNH]LN KRJ\ KD D] DOJRULWPXV DG VWUXNW~UiW HUHGPpQ\NpQW akkor az a maximális struktúra. 3. példa. Tegyük, fel hogy 7iEUiEDQDGRWWP YHOHWLHJ\VpJHNVHJtWVpJpYHOD3 terméket kell gyártanunk. A többi anyag osztályozása leolvasható az ábráról. A feladathoz tartozó P-gráfot a 8. ábra tartalmazza. A 9. ábra a maximális struktúrát mutatja be. Összehasonlításképp a 10. ábrában megadjuk azt a maximális struktúrát, amelyet szintén a 7iEUDP YHOHWLHJ\VpJHLE ONLLQGXOYD kaphatunk, de az integrált hulladékkezelés elhagyásával. A 11. ábra néhány kombinatorikusan lehetséges megoldást illusztrál.

40


W2

W2

2

1

D1

D2

W1

W9

11

W5

3

D3

D4

W10

W1

D10

D5

R1

P1

D8

R4

15

W7

P2

W8

9

W4

W3

R3

14

D12

17

W9

D10

W9

10

P1

W5

D11

16

D9

D9

8

P1

W2

R2

13

D7

P1

W8

W7

7

6

W10

D10

D8

D8

5

4

12

W6

D7

W6

D12

D6

R5

18

D10

D10

7iEUD$SpOGDP YHOHWLHJ\VpJHL

R5

D12

18 R4

R3

D11

16

15

17 R2

R1 W8

8

W9

D9

10

9

D10

11

12

W6

D6

W5

W10

13

D7

14

D8

W7

P2

W4 4

3

W1

D4

5

6

7

P1

D5

W2 W3 1

2

D1

D2

D3

8. ábra. A 3. példa P-gráfja.

R4

16 R1 W9

10

W10

D10

11

12

W6

D6

4

W1

13

D7

D8

5

D5

P2

6

P1

W2 1

D1

2

D2

D3

9. ábra. A 3. példa maximális struktúrája.

41


R5

D12

18 R4

R3

D11

16

15

17 R2

R1 W8

W9

D9

9

10

W10

D10

11

12

W6

W5

13

D7

14

D8

W7

P2 4

W1

5

6

D5

7

W2 W3

P1

10. ábra. A 3. példa maximális struktúrája a hulladékkezelés figyelembevétele nélkül.

R4

16

R4

R4

R1 W9

D10

16

16

10

13

R1 W9

W10

D10

11

12

W9

W10

D10 D6

10

12

D8

P2

13 6

W6

D6

D7

D7

D8

P2 P1

4

W2

5

5

2

W1

D5

P1

D3

P1

11. ábra. A 3. példa néhány kombinatorikusan lehetséges struktúrája.

0LQW OiWKDWy QpKiQ\ D IHODGDW GHILQtFLyMiEDQ V]HUHSO P YHOHWL HJ\VpJ QHP UpV]H D PD[LPiOLV VWUXNW~UiQDN H]HNHW D P YHOHWL HJ\VpJHNHW PiU QHP NHOO figyelembe vennünk az optimális megoldás keresése során. 10.1.5. ABBW algoritmus Az ABB algoritmushoz hasonló módon a hulladékkezeléssel integrált folyamathálózatszintézis feladatot megoldó ABBW algoritmusra is definiáljuk a PHJIHOHO IJJYpQ\HNHW $ UpV]SUREOpPiN GHILQtFLyMD D] DODSHVHWWHO D]RQRV D szétválasztó lépés során is a megoldások struktúráinak fokozatos felépítésével kereshetjük az optimális megoldást. Mivel ebben az esetben is a termék(ek)et minden

megoldásstruktúrának

tartalmaznia

kell,

ezeket

tekinthetjük

42


NLLQGXOySRQWQDN $] DODSHVHWW O HOWpU HQ D]RQEDQ LWW YiODV]WiVL OHKHW VpJ QHP csak egy anyag gyártásánál adódik, hanem az integrált hulladékkezelés miatt bizonyos esetekben egy anyag további feldolgozásáról is döntenünk kell. Ennek PHJIHOHO HQ D V]pWYiODV]Wy IJJYpQ\W PyGRVtWDQXQN NHOO pV D V]pWYiODV]Wy függvény alapjául szolgáló döntés leképezést is ki kell terjesztenünk. A kiterjesztett döntés leképezés esetén használt definíciók, illetve jelölések az alábbiak: Jelölje ∆inD]WDOHNpSH]pVWD]DQ\DJRNpVDP YHOHWLHJ\VpJHNKDWYiQ\KDOPD]D között, amely minden X∈0 DQ\DJUD PHJDGMD D] ;HW HO iOOtWy P YHOHWL egységek halmazát, azaz ∆in(X) = {i∈O | X∈outi}. Továbbá jelölje ∆out azt a OHNpSH]pVW D] DQ\DJRN pV D P YHOHWL HJ\VpJHN KDWYiQ\KDOPD]D N|]|WW DPHO\ minden X∈0 DQ\DJUD PHJDGMD D] ;HW IHOKDV]QiOy P YHOHWL HJ\VpJHN halmazát, azaz ∆out(X) = {i∈O | X∈ini}. 10. definíció. Legyen m⊆M és δin(X)⊆∆in(X) minden X∈m-re. Ekkor δin, mint OHNpSH]pV D] P KDOPD]EyO D P YHOHWL HJ\VpJHN UpV]KDOPD]DLQDN KDOPD]iED δin[m] = {(X, δin(X)) | X∈m}, a gyártó döntés leképezés m felett. 11. definíció. Legyen m⊆M és δout(X)⊆∆out(X) minden X∈m-re. Ekkor δout, PLQW OHNpSH]pV D] P KDOPD]EyO D P YHOHWL HJ\VpJHN UpV]KDOPD]DLQDN halmazába, δout[m] = {(X, δout(X)) | X∈m}, a felhasználó döntés leképezés m felett. 12. definíció. Legyen δin[min] gyártó döntés leképezés, δout[mout] felhasználó döntés leképezés, ekkor a δ[min∪mout] = δin[min]∪δout[mout] döntés leképezés m = min∪mout felett (mint a definíció is mutatja, az így definiált döntés leképezés nem függvény). 13. definíció. A δin[m] gyártó döntés leképezés komplementere a δ in[m] = {(X, ∆in(X)\δin(X)) | X∈m} leképezés. 14. definíció. A δout[m] felhasználó döntés leképezés komplementere a

δ out[m] = {(X, ∆out(X)\δout(X)) | X∈m} leképezés. 15. definíció. A δ[m] = δin[min]∪δout[mout] döntés leképezés komplementere a

δ [m] = δ in[min]∪ δ out[mout] leképezés.

43


16. definíció. A δ[m] döntés leképezés (m≠∅) akkor és csak akkor konzisztens, ha minden X, Y ∈m-re δ(X)∩ δ (Y)=∅. Jelölje op(δ[m]) a δ>P@ G|QWpV OHNpSH]pV P YHOHWL HJ\VpJHLW D]D] RSδ[m]) = {o∈O | o∈δ(X) valamely (X, δ(X))∈δ[m]-re}, továbbá mat(o) = {x∈M | valamely u∈RP YHOHWLHJ\VpJUH[∈inu vagy x∈outu}. 17. definíció. Legyen δ[m] egy konzisztens döntés leképezés, o = op(δ[m]), m = mat(o)∪m, és δ'[m] = {(X, Y) | X∈m és Y = {i∈o | X∈outi}}∪{(X, Y) | X∈m és Y = {i∈o | X∈ini}}. Ekkor δ'[m] döntés leképezés a δ[m] döntés leképezés lezártja. A δ[m] döntés leképezés zárt, ha δ[m] = δ'[m]. 18. definíció. Két konzisztens döntés leképezés ekvivalens, ha a lezártjuk azonos. A szükséges fogalmak bevezetése után most már megadhatjuk a döntés leképezés és a P-gráf kapcsolatát. 19. definíció. Adott az (m, o) P-gráf és a δ[m'] = δin[min]∪δout[mout] konzisztens döntés leképezés. Ha op(δ[m'])=o, akkor δ[m'] döntés leképezés az (m, o) Pgráfhoz tartozó döntés leképezés. A fordított kapcsolat bemutatásaként tekintsük a δ[m'] konzisztens döntés leképezést. Legyen o = op(δ[m']) és m = mat(o)∪m'. Ekkor (i) az (m, o) P-gráf, (ii) δ[m'] az (m, o) P-gráfhoz tartozó döntés leképezés. Ez alapján: 20. definíció. Egy δ[m] konzisztens döntés leképezés P-gráfja (m, o), ahol o = op(δ[m’]), m = mat(o)∪m', és gráf(δ[m'])-mel jelöljük. 21. definíció. Legyenek δ1[m1] és δ2[m2] konzisztens döntés leképezések. A δ1[m1]= δ1in[m1in] ∪ δ1out[m1out] döntés leképezés a δ2[m2] = δ2in[m2in] ∪ δ2out[m2out] döntés leképezés kiterjesztése (jelölés: δ1[m1]≥δ2[m2]), ha m1in⊇m2in és δ1in(X) = δ2in(X) minden X∈m2in-re, továbbá m1out⊇m2out és δ1out(X) = δ2out(X) minden X∈m2out-ra. A kiterjesztés reláció parciális rendezés a konzisztens döntés leképezések halmazán. $V]NVpJHVHO NpV]OHWLOpSpVHNXWiQPiUGHILQLiOKDWMXND]$%%:DOJRULWPXV szétválasztó lépését. Az alapesethez hasonlóan a korlátozó függvényekkel itt

44


sem foglalkozunk. A részproblémák definíciója, valamint a G korlátozó függvényre vonatkozó feltételek azonosak az alapesetben ismertetettekkel. $]LQWHJUiOWKXOODGpNNH]HOpVQHNN|V]|QKHW HQHJ\DGRWWUpV]SUREOpPiWPiUQHP NL]iUyODJHJ\PHJIHOHO HQNLYiODV]WRWWDQ\DJHO iOOtWiViUyOKR]RWWG|QWpVDODSMiQ bonthatunk diszjunkt részproblémákra, hanem bizonyos esetekben anyagok NO|QE|] PyGRQ W|UWpQ IHOKDV]QiOiViUyO KR]RWW G|QWpVVHO LV (QQHN PHJIHOHO HQ D G|QWpVL SRQWRNNpQW ILJ\HOHPEH YHKHW DQ\DJRNDW NpW KDOPD]]DO adhatjuk meg. Tekintsük a (Pr, Pp, R, I, O) hulladékkezeléssel integrált folyamathálózatszintézis feladat egy Pi - S(δi[mi])-vel adott - részproblémáját. A δi[mi] döntés leképezés felírható mint δi,in[mi,in]∪ δi,out[mi,out] valamely mi,in⊆mi és mi,out⊆mi halmazokra. Ekkor a Pi részprobléma a pin(S(δi[mi])) = ((matin(op( δi,out[mi,out]))\matout(op(δi,out[mi,out]))) ∪ Pr ∪ Pp ∪ matin(op(δi,in[mi,in])))\ (mi,in ∪ R) halmaz elemeinek gyártására, illetve a pout(S(δi[mi])) = (matout(op(δi,out[ mi,out])) ∪ (matout(op(δi,in[mi,in]))\ matin(op(δi,in[mi,in]))))\ mi,out halmaz elemeinek felhasználására hozott újabb döntéssel bontható újabb részproblémákra, ahol matout, matin az MSGW algoritmusban is használt függvényeket jelöli. Ha mindkét halmaz üres, az S(δi[mi]) részproblémában a megoldások struktúrája WHOMHVHQ GHILQLiOW D]D] HJ\pUWHOP tJ\ D NRUOiWR]y IJJYpQ\ WXODMGRQViJiQDN PHJIHOHO HQ HQQpO D UpV]SUREOpPiQiO QLQFV V]NVpJ WRYiEEL V]pWYiODV]WiVUD D UpV]SUREOpPD OHYpO $ YDOyGL V]pWYiODV]WiVW QHP HUHGPpQ\H] HVHWHNHW D] alapesethez hasonlóan a maximális neutrális kiterjesztés alkalmazásával V] UKHWMNNL 22. definíció. A δ’[m’] = δ[m]∪{(x,d)} döntés leképezés a δ[m] konzisztens döntés leképezés direkt neutrális kiterjesztése, ha vagy (i) x∈pin(S(δ[m])), d⊆∆in(x), és δ[m]∪{(x,c)} inkonzisztens minden c∈℘(∆in(x))\{d} esetén; vagy (ii) x∈pout(S(δ[m])), d⊆∆out(x), és δ[m]∪{(x,c)} inkonzisztens minden c∈℘(∆out(x))\{d} esetén. A δn[mn] döntés leképezés a δ0[m0] konzisztens döntés leképezés neutrális kiterjesztése, ha létezik konzisztens döntés leképezések egy δ0[m0], δ1[m1], …, δn[mn] sorozata úgy, hogy δi[mi] a δi-1[mi-1] döntés leképezés direkt neutrális kiterjesztése (i=1, 2, …, n). A δmax[mmax]

45


döntés leképezés a δ[m] konzisztens döntés leképezés maximális neutrális kiterjesztése, ha neutrális kiterjesztése δ[m]-nek, és δmax[mmax]-nak nincs direkt neutrális kiterjesztése. Az S(δmax[mmax])=S(δ[m]) nyilvánvalóan teljesül. Az ABBW algoritmus szétválasztó függvényének pontos definiálásához meg kell adnunk egy "anyagválasztó függvényt" (x = A(S(δi[mi])) ∈pin(S(δi[mi])) ∪ pout(S(δi[mi@ DPLOHKHWDOHJNLVHEELQGH[ DQ\DJDIHODGDWGHILQtFLyDODSMiQ DOHJNHYHVHEEPyGRQHO iOOtWKDWyLOOHWYHIHOGROJR]KDWyDQ\DJGHH]OpQ\HJpEHQ WHWV] OHJHVD]$%%:DOJRULWPXVP N|GpVpWQHPEHIRO\iVROMDOpQ\HJHVHQ Az

ABBW

algoritmus

szétválasztó

függvénye

valamely

S(δi[mi])≠∅

részproblémára: son(S(δi[mi])) = {S(δij[mij]) | δk[mk] = δi[mi]∪{(x, c)}, x = A(S(δi[mi])), c∈D, δk[mk] konzisztens, δij a δk maximális neutrális kiterjesztése},

℘( ∆ in ) ha  ℘( ∆ in ) \ {∅} ha ahol D =  ℘( ∆ out ) \ {∅} ha ℘( ∆ out ) ha

x ∈ p in (S( δ i [m i ])) és x ∈ Pp \ mat in ( op( δ i [ m i ])) x ∈ p in (S( δ i [ m i ])) és x ∉ Pp \ mat in ( op( δ i [ m i ])) x ∈ p out (S( δ i [ m i ])) és x ∈ I

.

x ∈ p out (S( δ i [ m i ])) és x ∉ I

Ez a függvény megfelel mint szétválasztófüggvény, a feladat matematikai PRGHOOMpW O IJJHWOHQO PLQGHQ KXOODGpNNH]HOpVVHO LQWHJUiOW IRO\DPDW hálózatszintézis feladat megoldására alkalmazható. $ G|QWpV OHNpSH]pV DODSMiQ HJ\ DGRWW UpV]SUREOpPiQiO SROLQRPLiOLV LG EHQ meghatározhatjuk a részproblémához tartozó összes megoldásstruktúrában V]HUHSO NLYiODV]WRWW P YHOHWL HJ\VpJHNHW D NL]iUW P YHOHWL HJ\VpJHNHW pV D YiODV]WKDWy P YHOHWL HJ\VpJHNHW (]HN VHJtWVpJpYHO D P YHOHWL HJ\VpJHN modelljét és ha szükséges, valamilyen relaxáló módszert felhasználva már meghatározható a korlátozó függvény. 3. példa (folytatás) $ P YHOHWL HJ\VpJHW WDUWDOPD]y KXOODGpNNH]HOpVVHO integrált folyamat-hálózatszintézis feladatot az ABBW algoritmus legrosszabb esetben 15 részprobléma megvizsgálásával oldja meg. A branch-and-bound NHUHV IiWD12. ábra mutatja, a részproblémákat a 3. táblázat tartalmazza. Ha egy feladat költségfüggvénye nem bünteti a kibocsátható anyagok gyártását, D]D] D] DODSIHODGDW FVDN D N|]EOV DQ\DJRN J\iUWiViQDN WLOWiViYDO E YOW D]

46


6:D[LyPDPyGRVtWiViYDOWRYiEEV] NtWKHW DNHUHVpVLWpU(EEHQD]HVHWEHQ ugyanis

a

megoldásstruktúra

hulladékkezelésre

szolgáló

részeiben

a

kibocsátható anyagok további feldolgozása már szükségtelen, ilyen struktúra nem tartozhat az optimális megoldáshoz. 1

2

9

3

4

6

5

7

10

8

11

13

12

14

15

12. ábra. $EUDQFKDQGERXQGDOJRULWPXVNHUHV IiMDDSpOGDPHJROGiVDNRU legrosszabb esetben.

3. táblázat. A 12iEUDUpV]SUREOpPiLQDNPiUNLYiODV]WRWWpVPpJNLYiODV]WKDWyP YHOHWL egységei.

részprobléma NLYiODV]WRWWP YHOHWL egységek 1 ∅ 2 3 4 5 6 7 8 9 10 11 12 13 14 15

5, 12, 16 5, 12, 13, 16 5, 10, 12, 13, 16 4, 5, 11, 12, 13, 16 5, 12, 16 5, 10, 12, 16 4, 5, 11, 12, 16 6, 13, 16 1, 6, 13, 16 1, 6, 10, 13, 16 1, 4, 6, 11, 13, 16 2, 6, 13, 16 2, 6, 10, 13, 16 2, 4, 6, 11, 13, 16

NLYiODV]WKDWyP YHOHWL egységek 1, 2, 4, 5, 6, 10, 11, 12, 13, 16 4, 10, 11, 13 4, 10, 11 ∅ ∅ 4, 10, 11 ∅ ∅ 1, 2, 4, 10, 11 4, 10, 11 ∅ ∅ 4, 10, 11 ∅ ∅

A megváltozott (SW4) axióma: (SW4') Minden D VWUXNW~UiEDQ V]HUHSO \ P YHOHWL HJ\VpJUH D] DOiEEL feltételek közül legalább egy teljesül

47


(a) /pWH]LNDVWUXNW~UiEDQD]\P YHOHWLHJ\VpJHWUHSUH]HQWiOyFV~FVWyO YDODPHO\OHKHWVpJHV WHUPpNHWUHSUH]HQWiOyFV~FVLJYH]HW ~W (b) Létezik utak egy sorozaWD ~J\ KRJ\ \ P YHOHWL HJ\VpJHW UHSUH]HQWiOyFV~FVD]HOV ~WHOHMHD]XWROVy~WYpJHHJ\OHKHWVpJHV WHUPpNHW UHSUH]HQWiOy FV~FV 0LQGHJ\LN ~W HOV pV XWROVy HOHPH P YHOHWL HJ\VpJHW UHSUH]HQWiOy FV~FV PLQGHJ\LN ~WQDN N|]|V D] HOHMH YDJ\ D YpJH D N|YHWNH] ~WWDO pV D] XWDNEDQ QLQFV N|]|V anyagot reprezentáló csúcs. (c) /pWH]LNDVWUXNW~UiEDQD]\P YHOHWLHJ\VpJHWUHSUH]HQWiOyFV~FVKR] YH]HW ~W DPHO\QHN HOHMH HJ\ RO\DQ [ N|]EOV DQ\DJ DPHO\E O nem vezet út (lehetséges) termékhez és x-et valamely, az SW4a YDJ\6:EIHOWpWHOQHNHOHJHWWHY P YHOHWLHJ\VpJJ\iUWMDD]~WRQ x és y között nincs kibocsátható anyag. (QQHN PHJIHOHO HQ D] 06*: pV D] $%%: DOJRULWPXVRN LV NLVHEE PyGRVtWiVVDO DONDOPDVVi WHKHW HN HQQHN D IHODGDWWtSXVQDN D PpJ KDWpNRQ\DEE megoldására [15, 39].

10.2. Integrált folyamat-hálózat- és irányítórendszer tervezés Az integrált folyamat-hálózat- és irányítórendszer tervezésekor a költségIJJYpQ\ PLQLPDOL]iOiVD PHOOHWW D UHQGV]HU LUiQ\tWKDWyViJD LV DODSYHW IRQ WRVViJ~,O\HQNRUDUHQGV]HUGLQDPLNiMiWpVV]DEiO\R]KDWyViJiWOHKHW VpJV]HULQW DUHQGV]HUWHUYH]pVpQHNOHKHW OHJNRUiEELIi]LViEDQNHOOILJ\HOHPEHYHQQL $ KDJ\RPiQ\RV PHJN|]HOtWpVEHQ D WHUPHO UHQGV]HU pV D] HKKH] WDUWR]y LUiQ\tWyUHQGV]HU NpW IJJHWOHQ OpSpVEHQ W|UWpQ PHJWHUYH]pVpW YpJ]LN DPL általában nem ad optimális megoldást. A feladat megoldására javasolt eddigi módszerek egyike sem integrálja a rendszer tervezésével az irányítórendszer tervezését. Az irányítórendszer tervezésekor ugyan módosíthatják a rendszer RSWLPiOLV P N|GpVpW OHtUy iOODSRWYiOWR]yNDW GH UHQGV]HU VWUXNW~UiMD HEEHQ D OpSpVEHQ PiU N|W|WW ËJ\ HO IRUGXOKDW KRJ\ HJ\ N|OWVpJPLQLPXPKR] WDUWR]y megoldás nem, vagy nagyon nehezen irányítható, azaz a megoldás értéktelen.

48


Az általunk javasolt módszerben már a folyamat-hálózatszintézis során figyelembe veszünk irányíthatósági szempontokat. $] DODSYHW QHKp]VpJ D NpW WHUYH]pVL IHODGDW HOWpU MHOOHJpE O DGyGLN PtJ D IRO\DPDWKiOy]DWV]LQWp]LV VRUiQ P YHOHWL HJ\VpJHN HJ\ RO\DQ KDOPD]iW NHUHVVN DPHO\HN PHJIHOHO PyGRQ P N|GWHWYH PLQLPiOLV N|OWVpJJHO iOOtWMiN HO D WHUPpNHN HW D]D] D WHUYH]pV H]HQ UpV]H VWDWLNXV MHOOHJ DGGLJ D] irányítórendszer a hálózat dinamikus állapotváltozásaihoz kapcsolódik, tehát az irányítórendszer tervezéséhez a rendszer dinamikáját kell leírni. Ugyanakkor a VWUXNW~UD WHUYH]pVH VRUiQ HJ\V]HU %RROHDQ WtSXV~ VWUXNWXUiOLV LUiQ\tWKDWyViJL szempontokat már figyelembe vehetünk, melyekkel a struktúra állapotától függetlenül írhatjuk le annak irányíthatósági tulajdonságait [21]. A kidolgozott módszerben irányíthatósági szempontokat vettünk figyelembe, amely szabályozórendszer tervezésére alkalmas. Hasonló algoritmussal a PHJILJ\HOKHW VpJLVYL]VJiOKDWy[18], ez már alkalmas diagnosztikára is. A


feladat

megoldására

kidolgozott

ABB

algoritmusban a struktúrákat P-gráfokkal reprezentáljuk. A strukturális irányíthatóság vizsgálatára kidolgozott módszerekben irányított gráf alapú PRGHOOHNHW KDV]QiOQDN D P YHOHWL HJ\VpJHN GLQDPLNiMiQDN VWUXNW~UiOLV leírására. A javasolt módszer e két eredményre alapozva oldja meg az integrált folyamat-hálózat- és irányítórendszer tervezés (IPCS) feladatot. A struktúrákat a P-gráf egy kiterjesztésével tudjuk modellezni. 10.2.1. Struktúra reprezentáció $],3&6IHODGDWPHJROGiVDNRUDP YHOHWLHJ\VpJGHILQtFLyMiWLVPyGRVtWDQXQN kell. Míg az alapesetben egy rendezett (ini, outi, mi, ki) négyessel írtuk le a P YHOHWL HJ\VpJHNHW HEEHQ D] HVHWEHQ PLQGHQ P YHOHWL HJ\VpJ HJ\ UHQGH]HWW (ini, outi, ai, ci, mi, ki) hatossal írható le, ahol inti, outi, mi, ki szerepe változatlan, iniDP YHOHWLHJ\VpJLQSXWMDLQDNKDOPD]DRXWiDP YHOHWLHJ\VpJRXWSXWMDLQDN halmaza, miDP YHOHWLHJ\VpJP N|GpVpWOHtUyIJJYpQ\NiDP YHOHWLHJ\VpJ költségfüggvénye. Az ai D P YHOHWL HJ\VpJ OHKHWVpJHV DNWXiWRUDLQDN (beavatkozó változó) halmaza, míg ci az ún. "hatásfüggvény", amelynek értelmezési tartománya az aktuátorok és input anyagok halmazának uniója,

49


értékkészlete az output anyagok halmazának hatványhalmaza. Az IPCS feladat KDWiVIJJYpQ\H D P YHOHWL HJ\VpJHN KDWiVIJJYpQ\HLQHN XQLyMDNpQW definiálható. $],3&6IHODGDWDP YHOHWLHJ\VpJHNHJ\RO\DQUpV]KDOPD]iQDNPHJNHUHVpVHD PHJIHOHO iOODSRWYiOWR]yNNDO pV DNWXiWRURNNDO DPHO\HNE O IHOpSO KiOy]DW (megoldás) egyrészt az adott nyersanyagok segítségével a kért termékeket HO iOOtWMD~J\KRJ\DVWUXNW~UiEDIHOYHWWDNWXiWRURNVHJtWVpJpYHODWHUPpNHNpVD VWUXNW~UDPLQGHQN|]EOV WHUPHOWpVIHOKDV]QiOW DQ\DJDLUiQ\tWKDWyPiVUpV]W a hálózat költsége minimális. Ebben az esetben a költség mind a gyártási mind az irányítási költségeket tartalmazza. $],3&6IHODGDWGHILQLiOiViKR]HOHJHQG DP YHOHWLHJ\VpJHNQ\HUVDQ\DJRNpV termékek halmazának megadása. Megengedett az anyagok és aktuátorok halmazának különálló definiálása is, bár felesleges olyan aktuátor definiálása, DPHO\ HJ\LN P YHOHWL HJ\VpJEHQ VHP OHKHWVpJHV LOOHWYH YDODPHO\ P YHOHWL egységnél olyan aktuátort megadni, amelyet nem tartalmaz a külön megadott aktuátorhalmaz. Ugyanakkor az alap folyamat-hálózatszintézis feladattól megkülönböztetésképp az IPCS feladatokat a (P, R, O, A) négyessel adjuk meg. $ NLE YtWHWW P YHOHWL HJ\VpJHNE O iOOy VWUXNW~UiNDW D] DODSHVHWKH] KDVRQOyDQ irányított páros gráffal reprezentálhatjuk, ezeket megkülönböztetésképp CPgráfnak nevezzük. $ JUiI FV~FVSRQWMDLW D P YHOHWL HJ\VpJHN H]HNHW D] DODSHVHWKH] KDVRQOyDQ vízszintes vonallal,

, jelöljük), anyagok (jelölésük változatlanul kör, l) és

aktuátorok (jelölésük tömör négyzet, n) alkotják. A nyersanyagokat és a termékeket továbbra is megkülönböztetjük a többi anyagtól ( , illetve ). A JUiI pOHL D] DQ\DJRN pV P YHOHWL HJ\VpJHN N|]|WWL YDODPLQW D KDWiVIJJYpQ\ által leírt kapcsolatok: egy b P YHOHWL HJ\VpJ WtSXV~ FV~FVEyO pO YH]HW HJ\ a anyag típusú csúcshoz, ha az a eleme b outputhalmazának (a∈outb), illetve egy a anyag típusú csúcsból él vezet egy b P YHOHWL HJ\VpJ WtSXV~ FV~FVKR] KD a eleme b inputhalmazának (a∈inb). A hatásfüggvény által leírt relációkat UHSUH]HQWiOy pOHNHW V]DJJDWRWW YRQDOODO MHO|OMN D P YHOHWL HJ\VpJHN pV LQSXW RXWSXWDQ\DJDLNNDSFVRODWiWMHO|O IRO\DPDWRVpOHNW OPHJNO|QE|]WHWpVNpSS$

50


&3JUiIRWDKiURPNO|QE|] WtSXV~FV~FVDLQDNKDOPD]DLEyONpS]HWW0$2 rendezett hármassal definiáljuk. 4. példa. A 13iEUDHJ\NpWP YHOHWLHJ\VpJE OR1 és o2, álló CP-gráfot mutat be, ahol ino1={A, B}, outo1={C, D}, ao1={a1, a2}, co1={(B, {D}), (a1, {C, D}), (a2, {D})} ino2={D}, outo2={E, F}, ao2={a3}, co2={(D, {E}), (a3, {F})}. $ P YHOHWL HJ\VpJHN iOODSRWYiOWR]yL pV N|OWVpJIJJYpQ\HL D VWUXNW~UD szempontjából lényegtelenek. a1 A

B a2 o1 a3

C

D o2 E

F

13. ábra. Az ({A, B, C, D, E, F}, {a1, a2, a3}, {o1, o2}) CP-gráf.

Mint azt a CP-gráf definíciója mellett a fenti ábra is jól mutatja, a P-gráf része a CP-gráfnak. 23. definíció. Az (M, A, O) CP-gráf strukturális komponense, (M, A, O)S, a CP-gráf aktuátor típusú csúcsainak és a hatásfüggvényt reprezentáló éleinek elhagyásával kapott P-gráf. Az (M, A, O) CP-gráf kontrol komponense, (M, A, O)C D &3JUiIEyO D P YHOHWL HJ\VpJHN pV DQ\DJRN N|]|WWL LQSXWRXWSXW relációkat leíró élek elhagyásával kapott gráf. $]0$2 &3JUiIEDQD]DNWXiWRURNKDOPD]DUpV]KDOPD]DDJUiI2P YHOHWL HJ\VpJHLQ OHKHWVpJHV DNWXiWRURN KDOPD]iQDN HQQHN PHJIHOHO HQ D NRQWURO NRPSRQHQV pOHL LV D P YHOHWL HJ\VpJHN KDWiVIJJYpQ\HLQHN FVDN HJ\ részhalmazát reprezentálják. 24. definíció. Az a1, a2, ..., an sorozat struktúra út a CP-gráfban, ha út a strukturális komponensében, jelölése [a1, an]S. Ha b1 aktuátor és b1, b2, ..., bm út a CP-gráf kontrol komponensében, akkor kontrol útnak nevezzük és [b1, bm]Cvel jelöljük.

51


$ &3JUiIRN FV~FVDL N|]|WW W|EE NRQWURO ~W LV OHKHWVpJHV D &3 JUiI P YHOHWL egységeinek és a kontrol út definíciójából következik, hogy aktuátor csak kontrol út elején lehetséges. 10.2.2. Kombinatorikusan lehetséges irányítható struktúrák Az alapesethez hasonlóan a megoldásstruktúráknak bizonyos tulajdonságoknak PHJ NHOO IHOHOQLN (]HNHW D WXODMGRQViJRNDW pV D] NHW OHtUy D[LyPiNDW NpW csoportba oszthatjuk. Egy IPCS feladat megoldásainak kombinatorikusan lehetséges megoldásoknak kell lenniük: ha elhagyjuk az irányítórendszerre vonatkozó feltételeket, akkor egy alap folyamat-hálózatszintézis feladatot kapunk, tehát a megoldásstruktúráknak teljesíteniük kell az S1-S5 axiómákat. Az irányítórendszerre vonatkozó követelményt a feladatosztály definíciójában megfogalmaztuk: a struktúrába felvett aktuátorok segítségével a termékek és a VWUXNW~UiEDQ HO IRUGXOy PLQGHQ N|]EOV WHUPHOW pV IHOKDV]QiOW DQ\DJ LV LUiQ\tWKDWy (QQHN PHJIHOHO HQ D VWUXNWXUiOLV LUiQ\tWKDWyViJRW PHJIRJDOPD]y axióma: (SC1) A struktúrában minden x anyagra, amely termék vagy termelt és felhasznált anyag, létezik a∈A, hogy [a, x]C kontrol út a struktúra CP-gráfjában. Formálisan: a (P, R, O, A) IPCS feladatra adott struktúra, amelyhez tartozó CPgráf (M', A', O'), csak akkor lehet egy megoldás struktúrája, ha ∀x∈P∪ (matin(O')∩matout(O'))-hoz ∃a∈A', hogy [a, x]C kontrol út (M', A', O')-ban. 25. definíció. Az (M', A', O') CP-gráffal adott struktúra kombinatorikusan lehetséges és irányítható, röviden CFC struktúra, ha teljesíti az S1, S2, ..., S5 és SC1 axiómákat. A 14. ábrán egy CFC struktúra, valamint egy kombinatorikusan lehetséges, de nem irányítható (azaz nem CFC) struktúra látható. 7. tétel. Egy IPCS feladat CFC struktúráinak halmaza zárt az unióra. Bizonyítás: Legyen (M', A', O') és (M", A", O") a (P, R, O, A) IPCS feladat két CFC struktúrájának CP-gráfja. (i) A két struktúra uniója teljesíti az S1, S2, ..., S5 axiómákat: Az unió eredményeképp kapott CP-gráf strukturális komponense a két CP-gráf

52


strukturális komponensének uniója. Mivel két kombinatorikusan lehetséges Pgráf uniója is kombinatorikusan lehetséges [12], a két CP-gráf uniójaként kapott gráf strukturális komponense, így maga a CP-gráf is kombinatorikusan lehetséges.

14.a. ábra. CFC struktúra. .

14.b. ábra. Kombinatorikusan lehetséges, de nem irányítható struktúra.

(ii) A két struktúra uniója teljesíti az SC1 axiómát: Az unió eredményeként kapott CP-gráf kontrol útjai az eredeti CP-gráfok kontrol útjainak uniója, azaz minden x∈P∪matin(O'∪O")∩matout(O'∪O")-re létezik a∈A'∪A", hogy [a, x]C kontrol út. 10.2.3. CMSG algoritmus Az unióra zártság következményeként létezik maximális CFC struktúra. Az DODSIHODGDWKR] KDVRQOyDQ D] RSWLPiOLV PHJROGiV NHUHVpVH OHV] NtWKHW D &)& struktúrákra, így a maximális struktúra segítségével lényegesen csökkenthetjük a keresési teret. A maximális CFC struktúra egy hatékony polinomiális algoritmussal generálható. A maximális CFC struktúrát meghatározó CMSG algoritmust Pidgin Algol nyelven a 15. ábra mutatja. 10.2.4. Az algoritmus helyességének bizonyítása Tekintsünk egy IPCS feladatot és a feladathoz tartozó maximális CFC struktúrát. Mivel az alap folyamat-hálózatszintézis feladat kombinatorikusan lehetséges megoldásstruktúráit leíró axiómák a CFC struktúrákat definiáló

53


Input: ODP YHOHWLHJ\VpJHNKDOPD]D M: az anyagok halmaza P: a termékek halmaza R: a nyersanyagok halmaza A: az aktuátorok halmaza Jelölések: o⊆O, matin(o)={x∈M | u∈o, x∈inu}, matout(o)={x∈M | u∈o, x∈outu} m⊆M, opin(m)={u∈O | m∈outu}, opout(o)={u∈O | m∈inu} Azaz az opin, matinIJJYpQ\HNHJ\FV~FVKDOPD]EDEHM|Y pOHNNH]G SRQWMDLQDN halmazát, míg az opout, matout függvények egy csúcshalmazból kiinduló élek végpontjainak halmazát határozzák meg. procedure cmsg(): begin st1: O := O\opin(R); rp1: repeat st2: M := matin(O)∪matout(O); r := matin(O)\(matout(O)∪R); wh1: while r is not empty do begin x∈r; M := M\{x}; o := opout(x); O := O\o; r := (r∪(matout(o)\matout(O)))\{x}; end; co1: if P∩M ≠ P then stop; comment: there is no maximal controllable structure st3: p := P; Or:= ∅; m:= ∅; wh2: while p is not empty do begin x∈p; m := m∪{x}; ox := opin(x); Or := Or∪ox; p := (p∪matin(ox))\(R∪m); end; st4: r := {x | ∃oi∈Or, ∃a∈ai, x∈ci(a)}; s := ∅; O := Or; wh3: while r is not empty do begin x∈r; s := s∪{x}; u := opout(x); for all oi∈u do r := r∪ci(x); r := r\s; end; co2: if P∩s ≠ P then stop; comment: there is no maximal controllable structure st5 nco := opout(matin(Or)\(s∪R)); st6:: O := Or\nco; M := mat(O); until nco is empty; st7: Mr := matin(Or)∪matout(Or); Ar := {x∈ai | i∈Or}; write( Mr, Or, Ar ); end; 15. ábra. A CMSG algoritmus.

axiómák részhalmaza, az IPCS feladatból az irányíthatósági szempontokat elhagyva a maximális CFC struktúra strukturális komponense a kapott alap folyamat-hálózatszintézis feladatnak egy kombinatorikusan lehetséges megoldás VWUXNW~UiMD (EE O N|YHWNH]LN KRJ\ D PD[LPiOLV &)& VWUXNW~UD VWUXNWXUiOLV

54


komponense része az irányíthatósági feltételek elhagyásával kapott alap IRO\DPDWKiOy]DWV]LQWp]LVIHODGDWPD[LPiOLVVWUXNW~UiMiQDN(QQHNPHJIHOHO HQ D]DOJRULWPXVP N|GpVpWD]DOiEELPyGRQYi]ROKDWMXN 1. lépés. Az irányíthatósági feltételek elhagyásával határozzuk meg a (P, R, O) alapfeladat maximális struktúráját. Ha ez nem létezik, akkor a feladatnak nincs kombinatorikusan lehetséges megoldása és így nyilvánvalóan kombinatorikusan lehetséges és irányítható megoldása sincs. 2. lépés. Ha a kapott maximális struktúra irányítható, akkor ez egyben a maximális CFC struktúra is. Egyébként határozzuk meg az anyagok s halmazát, amelyekhez létezik kontrol út. 3. lépés. Ha a termékek valamelyike nem eleme az s halmaznak, nem létezik PD[LPiOLV &)& VWUXNW~UD 7|U|OMN D]RNDW D P YHOHWL HJ\VpJHNHW DPHO\HNQHN valamely nem nyersanyag inputja (azaz a struktúrában gyártott és egyben felhasznált anyag) nem eleme az s halmaznak. Keressük meg a megmaradt P YHOHWLHJ\VpJHNKH]WDUWR]yPD[LPiOLVVWUXNW~UiW)RO\WDVVXND]DOJRULWPXVWD 2. lépéssel. 8. tétel. $ ZK FLNOXV EHIHMH] GpVHNRU D] s KDOPD] D P YHOHWL HJ\VpJHN (mat(Or), Or, act(Or)) IPCS feladathoz tartozó struktúrában irányítható anyagokat tartalmazza. Bizonyítás: Jelölje c az irányítható anyagok halmazát. (i) c⊆s Legyen x∈c, azaz létezik [p1, pn]C kontrol út, ahol p1 aktuátor, pn=x, minden i=2, 3, ..., n-re ∃oj∈Or, hogy pi∈cj(pi-1). Az st3 utasítás után p2∈r. A ciklus i. futásakor a pi+2 bekerül az r halmazba, pi+1 pedig az s halmazba. A pn anyag a ciklus n-1. futásakor kerül az sKDOPD]EDËJ\DFLNOXVYpJHVDE YO s halmazt kivonva az rE OYDODKiQ\OpSpVXWiQr üres lesz), s pedig tartalmazza p2, p3, ..., pn anyagokat. (ii) c⊇s Az s halmaz konstrukciójából nyilvánvaló. 9. tétel$&06*DOJRULWPXVYpJHVpVSROLQRPLiOLVLG EHQYpJHWpU

55


%L]RQ\tWiV 0LYHO D] DOJRULWPXV QHP KtY PHJ NOV DOJRULWPXVRNDW pV QHP UHNXU]tYHOHJHQG EHOiWQLKRJ\DFLNOXVRNYpJHVHNpVPLQGHQFLNOXVOHKHWVpJHV LVPpWOpVHLQHN V]iPD SROLQRPLiOLV YDJ\ D] DQ\DJRN YDJ\ D P YHOHWL HJ\VpJHN számát tekintve. $NOV UHSHDWFLNOXVLVPpWHOWIXWiViQDNIHOWpWHOHOHJDOiEEHJ\P YHOHWLHJ\VpJ W|UOpVH VW D PD[LPiOLV &)& VWUXNW~UD OHKHWVpJHV P YHOHWL HJ\VpJHLQHN KDOPD]iEyO tJ\ H] D FLNOXV N P YHOHWL HJ\VpJJHO GHILQLiOW IHODGDW HVHWpQ PD[LPXPNV]HULVPpWO GKHW$EHOV FLNOXVRNN|]ODZKpVZKFLNOXVRN D]06*DOJRULWPXVWUpV]HLH]HNYpJHVHNpVSROLQRPLGHM HN>@$ZKFLNOXV az irányítható anyagokat határozza meg, lényegében egy gráfbejárás, ez nyilván YpJHV D] DQ\DJRN V]iPD PLQGLJ IHOV NRUOiWRW MHOHQW D FLNOXV LVPpWOpVpQHN számára. 10. tétel. A CMSG algoritmus által meghatározott (Mr, Or, Ar) struktúra CFC struktúra. Bizonyítás: (i) Az (Mr, Or, Ar) struktúra kombinatorikusan lehetséges. Az wh2 ciklus befejezésekor a (mat(Or), Or, act(Or)) struktúra kombinatorikusan OHKHWVpJHV D &06* DOJRULWPXV HOV UpV]H D] 06* DOJRULWPXV +D D] VW XWDVtWiVEDQD]QFRKDOPD]UHVD]DOJRULWPXVEHIHMH] GLNpVD]2r halmaz nem változik. (ii) Az (Mr, Or, Ar) struktúra irányítható. Mivel kaptunk maximális CFC struktúrát, a co2 feltétel nem teljesült és így PLQGHQ

WHUPpN

LUiQ\tWKDWy

$]

DOJRULWPXV

EHIHMH] GpVHNRU

D

opout(matin(Or)\(s∪R)) = ∅ (az nco halmaz üres), az opout és a matin definíciójából következik, hogy ez csak akkor lehetséges, ha matin(Or)\(s∪R)) = ∅, azaz matin(Or)⊆s∪R. Így matin(Or) ∩ matout(Or) ⊆ (s∪R)∩matout(Or) = (s∩matout(Or))∪(R∩matout(Or)) = s∩matout(Or) ⊆ s. Mivel s az irányítható anyagok halmaza, a struktúra teljesíti a strukturális irányíthatóság axiómáját. 11. tétel. A CMSG algoritmus által meghatározott (Mr, Or, Ar) struktúra a maximális CFC struktúra.

56


%L]RQ\tWiV 0HJPXWDWMXN KRJ\ KD HJ\ P YHOHWL HJ\VpJ QHP UpV]H D] eredményként kapott struktúrának, akkor nem lehet része egyetlen megoldásnak sem. L +D HJ\ P YHOHWL HJ\VpJHW D PD[LPiOLV &)& VWUXNW~UD OHKHWVpJHV P YHOHWL egységei közül az st1 utasítás zár ki, az nyersanyagként definiált anyagot állít HO tJ\D]6 D[LyPDV]HULQWQHPOHKHWPHJROGiVUpV]H $ WRYiEEL P YHOHWL HJ\VpJHNHW NL]iUy XWDVtWiVRN D FLNOXVRNRQ EHOO YDQQDN ezért mindig azt kell megvizsgálnunk, hogy az Or illetve O P YHOHWL HJ\VpJ KDOPD] DNWXiOLV P YHOHWL HJ\VpJHLW WHNLQWYH LQGRNROWH HJ\ P YHOHWL HJ\VpJ kizárása a további vizsgálatból. (ii) Ha egy bP YHOHWLHJ\VpJHWDZKFLNOXVEDQW|UOQNDNNRUb-nek létezik az O P YHOHWL HJ\VpJ KDOPD]EDQ QHP HO iOOtWRWW LQSXWMD D]D] QHP OHKHW D] O P YHOHWLHJ\VpJKDOPD]HOHPHLE ONpS]HWWPHJROGiVVWUXNW~UDUpV]H (iii) Ha egy b P YHOHWL HJ\VpJ D ZK FLNOXVEDQ QHP OHV] HOHPH D] 2r halmaznak, akkor nem adható meg út a bP YHOHWLHJ\VpJpVYDODPHO\WHUPpN között az O P YHOHWL HJ\VpJ KDOPD] DNWXiOLV P YHOHWL HJ\VpJHLW IHOKDV]QiOYD tJ\ D FLNOXVW N|YHW VW XWDVtWiV XWiQ D] O P YHOHWL HJ\VpJ KDOPD]QDN indokoltan nem lesz eleme. LY 0LQW D]W NRUiEEDQ EHEL]RQ\tWRWWXN D ZK FLNOXV EHIHMH] GpVHNRU D] s KDOPD] D] LUiQ\tWKDWy DQ\DJRN KDOPD]D ËJ\ D] QFR KDOPD] D]RQ P YHOHWL egységek halmaza, amelyeknek valamely inputja az OP YHOHWLHJ\VpJKDOPD] DNWXiOLVP YHOHWLHJ\VpJHLYHOQHPLUiQ\tWKDWyËJ\D]QFRHOHPHLQHPOHKHWQHN az OP YHOHWLHJ\VpJHLE ONpS]HWWPHJROGiVVWUXNW~UiNUpV]HL 12. tétel. Ha a CMSG algoritmus nem ad maximális CFC struktúrát, akkor a feladatnak nincs kombinatorikusan lehetséges és irányítható megoldása. Bizonyítás: Az algoritmus szerint nincs maximális CFC struktúra, ha az algoritmus végrehajtása során egy OP YHOHWLHJ\VpJKDOPD]UDDFRYDJ\FR feltétel teljesül. Ekkor az O P YHOHWL HJ\VpJ KDOPD] HOHPHLE O Q\LOYiQ QHP adható meg megoldásstruktúra. A 11. tétel bizonyításában megmutattuk, hogy a P YHOHWL HJ\VpJHN W|UOpVH PLQGLJ LQGRNROW tJ\ D] LQSXWNpQW DGRWW P YHOHWL HJ\VpJKDOPD]HOHPHLE OVHP DGKDWy PHJ PHJROGiVVWUXNW~UD tJ\ D IHODGDWQDN nem létezik megoldása.

57


10.2.5. IPCS feladat megoldása az ABB algoritmus kiterjesztésével Amíg az algoritmusban a megoldások struktúrája nem teljesen meghatározott, azaz amíg egy adott részprobléma több megoldásstruktúrát reprezentál, az irányíthatósági szempontokat relaxáljuk, így az alap folyamat-hálózatszintézis feladat részprobléma reprezentációját és szétválasztó függvényét változtatás nélkül alkalmazhatjuk. Mivel a strukturális komponens és a kontrol komponens költségei additívek, az így kapott érték az IPCS feladat esetén is megfelel mint N|OWVpJIJJYpQ\$]D]DN|OWVpJIJJYpQ\WDN|YHWNH] PyGRQGHILQLiOKDWMXN .|]EOV UpV]SUREOpPiN HVHWpQ KD HJ\ UpV]SUREOpPD QHP WDUWDOPD] kombinatorikusan lehetséges és irányítható struktúrákat, akkor kizárhatjuk a további vizsgálatból, az alapfeladat költségfüggvényének változtatás nélküli DONDOPD]iVD HO WW HJ\ HJ\V]HU JUiIEHMiUy DOJRULWPXVVDO HOOHQ UL]YH D strukturális irányíthatóságot. Teljesen definiált strukturális komponens esetén valamely hagyományos módszer segítségével meghatározzuk az irányítórendszerrel integrált folyamatKiOy]DWV]LQWp]LVIHODGDWHJ\OHKHWVpJHVVWUXNW~UiMiQDNRSWLPiOLVP N|GpVpWD]D] az állapotváltozókat és a struktúrába felvett aktuátorok halmazát.

10.3. Folyamat-hálózatszintézis szakaszosan folytonos N|OWVpJIJJYpQ\ P YHOHWLHJ\VpJHNNHO Mint korábban jeleztük, nagy ipari feladatok megoldása esetén a hagyományos branch-and-bound algoritmust alkalmazva nagyon sok részproblémát kell megoldani, amelyek mindegyike egy matematikai programozási feladat PHJROGiViW MHOHQWL (QQHN PHJIHOHO HQ D] HGGLJL PyGV]HUHN D P YHOHWL HJ\VpJHN N|OWVpJIJJYpQ\pU O D MREE PHJROGKDWyViJ pUGHNpEHQ iOWDOiEDQ feltételezik, hogy az folytonos és konkáv függvény. A gyorsított branch-andbound algoritmus segítségével ezen részproblémák számát nagyságrendekkel FV|NNHQWHWWN tJ\ OHKHW Yp YiOW KRJ\ ERQ\ROXOWDEE D YDOyViJRW MREEDQ PRGHOOH] N|OWVpJIJJYpQ\WKDV]QiOMXQN $ J\DNRUODWEDQ D P YHOHWL HJ\VpJHN FVDN DGRWW PpUHWHNEHQ HOpUKHW HN H]W ILJ\HOHPEH YpYH HJ\ DGRWW WtSXV~ P YHOHWL HJ\VpJ N|OWVpJIJJYpQ\H FVDN V]DNDV]RVDQ IRO\WRQRV $ V]DNDV]RVDQ IRO\WRQRV N|OWVpJIJJYpQ\ P YHOHWL

58


HJ\VpJHNE OiOOy IRO\DPDWKiOy]DWV]LQWp]LV PHJROGiViUD NLGROJR]RWW PyGV]HU D gyorsított branch-and-bound algoritmuson alapul. A branch-and-bound módszer V]pWYiODV]WyOpSpVpQHNNLWHUMHV]WpVpYHODP YHOHWLHJ\VpJHNNDSDFLWiViUDDOVypV IHOV NRUOiWV]iPROiViYDOPHJROGRWWXNDV]DNDV]RVDQIRO\WRQRVN|OWVpJIJJYpQ\ PLDWWIHOPHUO SUREOpPiNDW 1.1.1. Szakaszosan folytonos költségfüggvény kezelése 6]DNDV]RVDQ IRO\WRQRV N|OWVpJIJJYpQ\ P YHOHWL HJ\VpJHN IRO\DPDW hálózatszintézisének

megoldására

kidolgozott

módszerünkben

a

N|OWVpJIJJYpQ\ IRO\WRQRV V]DNDV]DLUyO IHOWpWHOH]]N KRJ\ D]RN QHPFV|NNHQ konkáv függvények. Ez nem jelent komoly megszorítást, mivel ez a feltétel szinte mindig teljesül gyakorlati példák esetében. Tekintsük

a


feladat

megoldása

során

a

N|OWVpJIJJYpQ\V]DNDV]RVIRO\WRQRVViJDPLDWWIHOPHUO QHKp]VpJHNHWpVD]RN megoldását a kidolgozott módszerben. 1. probléma. +D HJ\ P YHOHWL HJ\VpJ W|EE PpUHWEHQ HOpUKHW EL]RQ\RV HVHWHNEHQNLIL]HW G EEOHKHWNLVHEEP YHOHWLHJ\VpJHNYDODPHO\NRPELQiFLyMiW alkalmazni, ha ez megengedett. $]HVHWOHJHVHQNLIL]HW G EEP YHOHWLHJ\VpJNRPELQiFLyNLOOP YHOHWLHJ\VpJ többszörözések meghatározása a folyamat-hálózatszintézis feladatot megoldó DOJRULWPXVLQGtWiVDHO WWPHJROGKDWytJ\H]]HODSUREOpPiYDOD]DOJRULWPXVEDQ PiU QHP NHOO IRJODONR]QXQN 0LXWiQ PHJROGRWWXN D IHODGDWRW D P YHOHWL HJ\VpJHNRSWLPiOLVP N|GpVHNpQWNDSRWWNDSDFLWiVpUWpNHNE OPHJiOODStWKDWMXN KRJ\ D] DGRWW NDSDFLWiVKR] P YHOHWL HJ\VpJHN PLO\HQ NRPELQiFLyMD YDJ\ W|EEV]|U|]pVHWDUWR]LN$NO|QE|] P YHOHWLHJ\VpJHNNRPELQiFLyMiQDNLOOHWYH YDODPHO\ P YHOHWL HJ\VpJ W|EEV]|U|]pVpQHN IHOWpWHOH KRJ\ D] |VV]HWHWW P YHOHWLHJ\VpJN|OWVpJIJJYpQ\pWLOOHWYHiOODSRWYiOWR]yLWPHJWXGMXNDGQLD gyakorlatban a költségfüggvényre az additivítás szinte mindig teljesül. 5. példa.7HJ\NIHOKRJ\HJ\P YHOHWLHJ\VpJNpWNO|QE|] PpUHWEHQOpWH]LN 0LQGNpWP YHOHWLHJ\VpJKH]DGRWWDN|OWVpJIJJYpQ\MHO|OMNH]HNHWF1 illetve c2YHO DPHO\HNU O LWW D] HJ\V]HU EE iEUi]ROiV NHGYppUW IHOWpWHOH]]N KRJ\ OLQHiULVDN pV D P YHOHWL HJ\VpJHNHW NRPELQiOYD |VV]HDGyGQDN $ NpW P YHOHWL

59


HJ\VpJKH]WDUWR]yNDSDFLWiVLQWHUYDOOXPRNHJ\PiVWiWIHGKHWLNDP YHOHWLHJ\ ségek kombinációja és többszörözése megengedett. Az eredeti és az algoritmus inicializáló lépésében meghatározható költségfüggvényt a 16. ábra mutatja.

költség

költség

c2 c1 kapacitás

16DiEUD(J\P YHOHWLHJ\VpJW|EE típusának költségfüggvényei.

kapacitás

16EiEUD(J\P YHOHWLHJ\VpJN|OWVpJIJJYpQ\H az inicializáló lépés után.

2. probléma. Egy szakaszosan folytonos függvény se nem folytonos, se nem konkáv. A megoldó algoritmusban két relaxált költségfüggvényt vezettünk be, illetve a szétválasztó függvényben figyelembe vesszük a költségfüggvény folytonos részintervallumait. Mindig meg tudunk adni egy a költségfüggvényt alulról N|]HOtW OLQHiULV IJJYpQ\W D IRO\WRQRV LQWHUYDOOXP NLYiODV]WiVD QpONO LV D szaggatott vonal a 17 iEUiQ PLYHO D OHKHWVpJHV P YHOHWL HJ\VpJHN NDSDFL WiVDLQDNIHOV NRUOiWMDYpJHVtJ\D]HJ\P YHOHWLHJ\VpJKH]WDUWR]yPD[LPiOLV NDSDFLWiVpUWpNIHOHWWLIJJ OHJHVYRQDOD17. ábrán) kapacitás elérése már csak P YHOHWL HJ\VpJHN W|EEV]|U|]pVpYHO OHKHWVpJHV $ PyGV]HU KDWpNRQ\ViJiQDN javítására egy második, élesebb korlátot adó relaxált célfüggvényt is bevezethetünk, amely már egy adott kapacitás-intervallum kiválasztása után közelíti a célfüggvény egy folytonos szakaszát, így NLP feladatot megoldó NRUOiWR]y IJJYpQ\W HOHJHQG FVDN WHOMHVHQ PHJKDWiUR]RWW VWUXNW~UiN HVHWpQ KDV]QiOQL N|]EOV UpV]SUREOpPiNQiO HOHJHQG HJ\ /3 IHODGDWRW PHJROGy korlátozó függvény alkalmazása. 7HUPpV]HWHVHQQDJ\RQIRQWRVPHJIHOHO D]1/3IHODGDWRWKDWpNRQ\DQPHJROGy módszer kiválasztása is, mivel a levélfeladat megoldása egy nem hatékony PyGV]HUUHOW|EELG WLJpQ\HOKHWPLQWDIHODGDWW|EELUpV]HLQHNPHJROGiVD

60


A 17 iEUD HJ\ P YHOHWL HJ\VpJ V]DNDV]RVDQ IRO\WRQRV N|OWVpJIJJYpQ\pW pV relaxált függvényeit mutatja be.

költség

kapacitás

17iEUD(J\P YHOHWLHJ\VpJV]DNDV]RVDQIRO\WRQRVFpOIJJYpQ\H

3. probléma.ÈOWDOiEDQQHPLVPHUWDOVyLOOHWYHIHOV NRUOiWDP YHOHWLHJ\VpJHN kapacitására. $ MDYDVROW PyGV]HU V]pWYiODV]Wy OpSpVpEHQ pOHV DOVy pV IHOV NRUOiWRNDW KDWiUR]XQN PHJ $ NDSDFLWiVNRUOiWRN V]iPROiViUD NpW NO|QE|] PyGV]HUW alkalmazhatunk együttesen. Az analitikus módszer /3 IHODGDWRN PHJROGiViW MHOHQWL (J\ P YHOHWL HJ\VpJ IHOV NDSDFLWiVNRUOiWMiQDN NLV]iPROiViKR] D] DOiEEL /3 IHODGDWRW NHOO megoldani: maximalL]iOMXNDYL]VJiOWP YHOHWLHJ\VpJNDSDFLWiViW feltéve, hogy az anyagegyensúly teljesül, a relaxált költségfüggvény ≤D]RSWLPiOLVPHJROGiVIHOV NRUOiWMD $] RSWLPiOLV PHJROGiV Q\LOYiQ IHOV NRUOiW OHV] D P YHOHWL HJ\VpJ RSWLPiOLV megoldásban lehetséges kapacitására. Az alsó korlát hasonló módon állapítható meg: PLQLPDOL]iOMXNDYL]VJiOWP YHOHWLHJ\VpJNDSDFLWiViW feltéve, hogy az anyagegyensúly teljesül, a relaxált költségfüggvény ≤D]RSWLPiOLVPHJROGiVIHOV NRUOiWMD A második feltétel elhagyásával kapott eredmény szintén valódi alsó kapacitáskorlátot eredményezne, de bizonyos esetekben az így kapott korlát élesebb.

61


Amint az látható, a kapacitáskorlátok analitikus számolásához szükségünk van D] RSWLPiOLV PHJROGiV N|OWVpJpQHN IHOV NRUOiWMiUD (]W PHJNDSKDWMXN KD D NH]G OpSpVEHQDNRUOiWR]yIJJYpQ\iOWDOPHJKDWiUR]RWWPHJROGiVN|OWVpJpWD] eredeti költségfüggvénybe behelyettesítve is meghatározzuk. Ha ezt a korlátozó függvény minden hívása után megtesszük, a korlátot élesebbé tehetjük. A kombinatorikus módszer HJ\ HJ\V]HU NHUHVOHWHOOHQ U]pV D YL]VJiOW P YHOHWL HJ\VpJ LQSXWRXWSXW DQ\DJDLUD $ PyGV]HU FVDN DEEDQ D] HVHWEHQ DONDOPD]KDWy KD D P YHOHWL HJ\VpJHN LQSXWRXWSXW DQ\DJDL N|]|WW YDODPLO\HQ arányokat meg tudunk állapítani, illetve lineáris függvénnyel jól közelíthetjük az input-output anyagok mennyiségét leíró összefüggéseket. 6. példa. Tekintsünk egy folyamat-hálózatszintézis feladat megoldásának egy N|]EOV Ii]LViW$]18. ábra a feladat P-gráfjának egy részét mutatja. Az élekre tUW V]iPRN D] DQ\DJRN NL LOOHWYH EHPHQ DUiQ\iW DGMiN PHJ D P YHOHWL egységekre. 7HJ\N IHO KRJ\ D] DNWXiOLV UpV]SUREOpPiEDQ D] 2 pV D] 2 P YHOHWL HJ\VpJHNHWNLYiODV]WRWWXND]2P YHOHWLHJ\VpJHWSHGLJNL]iUWXNHJ\NRUiEEL G|QWpVVHOYDODPHO\DQ\DJRNJ\iUWiViUDWRYiEEiD]2pV2P YHOHWLHJ\VpJHN kapacitása az (1, 3] illetve a (4, 10] intervallumon belül változhat. Jelenleg az 0DQ\DJJ\iUWiViUDD]2P YHOHWLHJ\VpJHWYiODV]WRWWXNNL$]2P YHOHWL HJ\VpJNDSDFLWiViUDDOVypVIHOV NRUOiWV]iPROiViKR]D P YHOHWL HJ\VpJ LQSXW és output anyagait kell megvizsgálnunk. $ P YHOHWL HJ\VpJ HJ\HWOHQ LQSXWMD Q\HUVDQ\DJ KD D Q\HUVDQ\DJ NRUOiWR]RWW PHQQ\LVpJEHQiOOUHQGHONH]pVUHDNNRUH]IHOV NRUOiWRWMHOHQWDP YHOHWLHJ\VpJ NDSDFLWiViUDHJ\pENpQWD]LQSXWYL]VJiODWDQHPDGIHOV NRUOiWRW,QSXWDQ\DJRN PHQQ\LVpJpE ODOVyNRUOiWQHPKDWiUR]KDWyPHJPLYHOKDQHPV]NVpJHVQHP NHOOIHOGRJR]QL NHW $] 0 RXWSXW DQ\DJEyO OHJDOiEE HJ\VpJ HO iOOtWiVD V]NVpJHV 2 P YHOHWL HJ\VpJ LQSXWMDNpQW PLYHO FVDN D] 2 P YHOHWL HJ\VpJ iOOtWMD HO D] 0 DQ\DJRW D] 2 P YHOHWL HJ\VpJ NDSDFLWiVD OHJDOiEE $] 0 DQ\DJRW YL]VJiOYD IHOV NRUOiWRW QHP WXGXQN PHJDGQL PLYHO D] 2 P YHOHWL HJ\VpJ IHOV NRUOiWMDLVPHUHWOHQpVtJ\D]0DQ\DJEyOV]NVpJHVPHQQ\LVpJLV$]0 output anyagot vizsgálva alsó korlát nem adható meg, mivel az M2 anyagot az

62


2P YHOHWLHJ\VpJLVJ\iUWMDpVHQQHNDP YHOHWLHJ\VpJQHNPpJQHPLVPHUWD IHOV NDSDFLWiVNRUOiWMD $] 0 DQ\DJEyO OHJIHOMHEE HJ\VpJ HO iOOtWiVD V]NVpJHV tJ\ D] 0 DQ\DJRW YL]VJiOYD D IHOV NRUOiW D] 2 P YHOHWL HJ\VpJ kapacitására 5. Tehát az input anyagok vizsgálata nem eredményez NDSDFLWiVNRUOiWRWPtJD]RXWSXWDQ\DJRNYL]VJiODWDD]2P YHOHWLHJ\VpJDOVy NDSDFLWiVNRUOiWMiUD W DG $ IHOV NDSDFLWiVNRUOiWRW D] DQDOLWLNXV PyGV]HUUHO határozhatjuk meg.

LP (2,?] O5 (2,?] 2

2

O6 [0, 5] M2

M1 1 (?,?]

(?,?]

1

4

O1 O2 (1,3]

4 (4,10]

1

3

O3 O4

[0, 0]

18iEUD$OVyIHOV NRUOiWNRPELQDWRULNXVPHJKDWiUR]iVD

A javasolt algoritmusban, ha lehetséges mindkét módszert alkalmazzuk. A kombinatorikus módszer nem mindig ad kapacitáskorlátot, mivel bizonyos esetekben D P YHOHWL HJ\VpJ QHP PLQGHQ LQSXWRXWSXW DQ\DJiUD DGKDWy PHJ PD[LPiOLV LJpQ\ PLQLPiOLV LJpQ\ QXOOiYDO EHFVOKHW XJ\DQDNNRU HJ\V]HU VpJH PLDWW pUGHPHVDONDOPD]QLDNiUD]DQDOLWLNXVNRUOiWWDOPHJHJ\H] HUHGPpQ\WLVDGKDW $]DOVypVIHOV NDSDFLWiVNRUOiWRNDWPHJKDWiUR]yHOMiUiVRNDWDMDYDVROWEUDQFK and-bound módszer szétválasztó lépésének leírásában adjuk meg. 4. probléma. A feladat mérete nagyon nagy lehet a bináris változók számát tekintve. 0LYHODPyGV]HUD]$%%DOJRULWPXVUDpSODNRPELQDWRULNXVMHOOHJE ODGyGy J\RUVtWiVL OHKHW VpJHNHW NLKDV]QiOMXN D MDYDVROW PyGV]HUUHO YLV]RQ\ODJ QDJ\ hagyományos módszerrel nagyon sok bináris változót tartalmazó feladat is megoldható. Az összetettebb szétválasztó lépés bevezetése nyilván lényegesen növeli a megoldandó részproblémák számát, azonban a szétválasztó lépés sok esetben nem megoldható részproblémát eredményez.

63


10.3.2. %UDQFKDQGERXQGDOJRULWPXVV]DNDV]RVDQIRO\WRQRVN|OWVpJIJJYpQ\ P YHOHWLHJ\VpJHNNHODGRWWIRO\DPDWKiOy]DWV]LQWp]LVIHODGDW megoldására $]HGGLJEHPXWDWRWWNLWHUMHV]WpVHNEHQDUpV]SUREOpPDUHSUH]HQWiFLyUDPHJIHOHO volt a döntés leképezés. Ebben az esetben nem csak valamely anyagot gyártó P YHOHWL HJ\VpJHNHW KDWiUR]]XN PHJ KDQHP D P YHOHWL HJ\VpJ N|OWVpJ IJJYpQ\HYDODPLQWDP YHOHWLHJ\VpJUHNLV]iPROWDOVypVIHOV NRUOiWDODSMiQ NLYiODV]WXQN D P YHOHWL HJ\VpJ NDSDFLWiViUD HJ\ RO\DQ LQWHUYDOOXPRW LV DPHO\HQ D P YHOHWL HJ\VpJ N|OWVpJIJJYpQ\H IRO\WRQRV (]pUW HJ\ 3i részprobléma definiálására az δi[mi] döntés leképezés mellett egy rendezett párokból álló IiKDOPD]WKDV]QiOXQNDPHO\EHQDSiURNHOV HOHPHHJ\P YHOHWL HJ\VpJDPiVRGLNHOHPDP YHOHWLHJ\VpJN|OWVpJIJJYpQ\pQHNHJ\IRO\WRQRV szakasza. Ii = {(u, ( x, y]) | u∈op(δi[mi@ [ \@ D] X P YHOHWL HJ\VpJ költségfüggvényének egy folytonos szakasza} Az Ii WHNLQWKHW HJ\ RO\DQ IJJYpQ\QHN DPHO\ D] RSδi[mi@ EHOL P YHOHWL egységekre megadja a korábbi döntésekkel kiválasztott folytonos szakaszt. A részprobléma által reprezentált megoldások halmazát így S(δi[mi], Ii)-vel jelöljük és azon megoldásokat tartalmazza, amelyekhez tartozó P-gráf az aktuális részprobléma döntés leképezése által definiált P-gráf részgráfja és nem WDUWDOPD]QDN D] HGGLJL G|QWpVHNNHO NL]iUW P YHOHWL HJ\VpJHNHW WRYiEEi P YHOHWLHJ\VpJHNNDSDFLWiVDD],i-ben adott intervallumon belül van. Ha valamely részproblémára igaz, hogy minden a részproblémába tartozó PHJROGiVQDN D]RQRV D VWUXNW~UiMD WRYiEEi D P YHOHWL HJ\VpJHN NDSDFLWiVDL mindig ugyanabba a folytonos szakaszba esnek, akkor a branch-and-bound algoritmusban egy részproblémára meghatározott korlátozó függvénynél megköveteljük, hogy az F és G függvények értékei megegyezzenek, így az ilyen részproblémákra további szétválasztó lépések nem szükségesek. A lehetséges döntési pontok halmaza, a p(S(δi[mi], Ii)) halmaz, azonos az alapesettel, nem függ az Ii halmaztól. A p(S(δi[mi], Ii)) halmazból az m döntési pontot kiválasztó A(S(δi[mi], Ii)) anyagválasztó függvény is változatlan, a szétválasztó lépésben az m DQ\DJRW J\iUWy P YHOHWL HJ\VpJHN |VV]HV konzisztens kiválasztása mellett az IiKDOPD]EDQHPWDUWR]yP YHOHWLHJ\VpJHN 64


PpUHWpW LV PHJ NHOO KDWiUR]QL D P YHOHWL HJ\VpJHN NDSDFLWiViUD PHJKDWiUR]RWW DOVypVIHOV NRUOiWDODSMiQOHKHWVpJHV|VV]HVNDSDFLWiVLQWHUYDOOXPRWNLYiODV]WYD Az m anyagot gyártó b P YHOHWL HJ\VpJHNUH D] DOVy LOOHWYH IHOV NRUOiWRW D] lb(S(δi[mi], Ii), b), illetve az ub(S(δi[mi], Ii), b) függvények segítségével adjuk meg. Ezek a korábban vázolt analitikus és kombinatorikus módszereket alkalmazva számolják a korlátokat, a függvényeket minden olyan mHWHO iOOtWy b P YHOHWL HJ\VpJUH PHJKtYMXN DPHO\ QHP HOHPH RSδi[mi])-nek. A IJJYpQ\HNHW PHJYDOyVtWy DOJRULWPXVRN 3LGJLQ $OJRO Q\HOY YiOWR]DWiW D 19. ábra mutatja be. $]DODSHVHWKH]KDVRQOyDQHO IRUGXOKDWKRJ\EL]RQ\RVDQ\DJRNUDQHPW|UWpQLN valódi szétválasztás. Ezeket az eseteket az alapesetben is alkalmazott maximális neutrális kiterjesztéshez hasonló módon kezeljük. Megkeressük azokat a döntési SRQWRNDWDPHO\HNQpOFVDNHJ\NRQ]LV]WHQVHO iOOtWiVLPyGOpWH]LNpVDP YHOHWL egységek kapacitásintervalluma is kötött (mert már elemei az Ii halmaznak, vagy D NDSDFLWiVNRUOiWNpQW NDSRWW DOVy pV IHOV NRUOiWRN HJ\ IRO\WRQRV V]DNDV]RQ belülre esnek a célfüggvényükben), ezeket az eddigi döntésekhez hozzávéve a NRUOiWR]yIJJYpQ\NLV]iPROiVDHO WWD]~MDEEV]pWYiODV]WyOpSpVHNEHQPLQGLJ valódi szétválasztást fogunk végezni. A szétválasztó függvény ezek alapján valamely nem üres S(δi[mi], Ii) részproblémára: son(S(δi[mi], Ii)) = {S(δij[mij], Iij) | δk[mk] = {(δi[mi]∪{(x, c)}, x = A(S(δi[mi], Ii)), c∈℘(∆(x))\{∅}, δk[mk] konzisztens, Ik = Ii∪{(b, (e, f]) | b∈c, (e, f] intervallum b költségfüggvényének egy folytonos szakasza, az [lb(S(δi[mi], Ii), b), ub(S(δi[mi], Ii), b)] intervallumon belül}, (δij[mij], Iij) a (δk[mk], Ik) maximális neutrális kiterjesztése} A korlátozó függvény lényegében változatlan, a korlátozó feltételek közé a kapacitáskorlátokat is fel kell venni és kétféle relaxált költségfüggvénnyel dolgozhatunk. 7. példa.7HNLQWVQNHJ\KDWP YHOHWLHJ\VpJE OiOOyIRO\DPDWKiOy]DWV]LQWp]LV IHODGDWRW D P YHOHWL HJ\VpJHN N|OWVpJIJJYpQ\H V]DNDV]RVDQ IRO\WRQRV $ feladat két termék gyártása minimális költséggel négy nyersanyag segítségével.

65


Input: δ[m]: a branch-and-bound ezen ágán eddig meghozott döntések bD]DNWXiOLVV]pWYiODV]WyOpSpVEHQYL]VJiOWP YHOHWLHJ\VpJ IDEP YHOHWLHJ\VpJNDSDFLWiViUDYRQDWNR]yNRUOiWRNLQWHUYDOOXP Jelölések: (nem vezettünk be új jelölést az eljárás leírásában) procedure lb(δ[m], I, b): begin lb := 0; for all output material m of b do begin if x∉∆[m] produces m [P YHOHWLHJ\VpJOHKHW6δ[m], I)-beli megoldás része, GHNDSDFLWiViUDQHPLVPHUWIHOV NRUOiW

then lbm := 0 else lbm := ("min. demand"-"max. production")/ratio; // az m anyagból minimálisan szükséges, illetve maximálisan termelt mennyiség a δ[m] és // I paraméterek segítségével könnyen meghatározható

if lbm>lb then lb := lbm; end x := {min. b kapacitása | relaxált költségfüggvény ≤ aktuális optimum, anyagegyensúly} // LP if x>lb then return x; return lb; end

procedure ub(δ[m], I, b): begin ub := 0; for all output material m of b do begin if x∉∆[m] consumes m // x P YHOHWLHJ\VpJOHKHW6δ[m], I)-beli megoldás része, //GHNDSDFLWiViUDQHPLVPHUWIHOV NRUOiW

then ubm := ∞ else ubm := ("max. demand"-"min. production")/ratio;

// az m anyagból maximálisan szükséges, illetve minimálisan termelt mennyiség a δ[m] és // I paraméterek segítségével könnyen meghatározható

if ubm>ub then ub := ubm end x := {max. b kapacitása | relaxált költségfüggvény ≤ aktuális optimum, anyagegyensúly} // LP if x
)HOWpWHOH]KHWMNKRJ\QLQFVIHOV NRUOiWDUHQGHONH]pVUHiOOyQ\HUVDQ\DJRNUD$ IHODGDW PD[LPiOLV VWUXNW~UiMD PLQG D KDW P YHOHWL HJ\VpJHW WDUWDOPD]]D D 3

66


gráfot a 20iEUDPXWDWMD$P YHOHWLHJ\VpJHNN|OWVpJIJJYpQ\HLWDWiEOi]DW WDUWDOPD]]D D P YHOHWL HJ\VpJHN PRGHOOMpEHQ D] LQSXW RXWSXW DUiQ\ IL[ D P YHOHWL HJ\VpJ HJ\HWOHQ iOODSRWYiOWR]yMD D P YHOHWL HJ\VpJ NDSDFLWiVD $ P YHOHWLHJ\VpJHNNRPELQiFLyMDpVW|EEV]|U|]pVHPHJHQJHGHWWD]LQLFLDOL]iOy lépésben kiszámolt költségfüggvényt és a relaxált függvényeket a 21. ábra tartalmazza. Hagyományos módszerrel ez a feladat 16 bináris változóval reprezentálható, a költségfüggvény nemlineáris. Az optimális megoldást 42 LP és 2 NLP részprobléma megoldása után találtuk meg, ez az O1, O3, O4, O5 és O6 P YHOHWLHJ\VpJHNHWWDUWDOPD]]DDKR]]iMXNWDUWR]yNDSDFLWiVYHNWRU 3, 1.5). WiEOi]DW$SpOGDP YHOHWLHJ\VpJHLQHNN|OWVpJIJJYpQ\H

0 YHOHWL egység típusa 1 1 1 1 2 2 2 2 3 3 3 4 4 4 5 5 5 6 6

Kapacitáskorlát

Költségfüggvény

0 0<x≤2 2<x≤5 5<x≤15 0 0<x≤2 2<x≤4 4<x≤15 0 0<x≤3 3<x≤10 0 0<x≤3 3<x≤10 0 0<x≤4 4<x≤8 0 0<x≤2

0 0.66x0.6+1 0.9x0.6+0.64 0.81x0.6+1.9 0 1.32x0.6+5 1.32x0.6+6 1.44x0.6+7.7 0 0.5x0.6+2.1 0.5x0.6+3.1 0 x0.6+4.1 x0.6+6.1 0 0.88x0.6+2 0.88x0.6+3 0 x+12

Relaxált $P YHOHWLHJ\VpJ függvény az típus relaxált intervallumra költségfüggvénye 0 0.5x+1 0.4x 0.33+1.33 0.2x+3 0 x+5 x 0.5x+7 0.36x+9.54 0 0.33x+2 0.5x 0.14x+3.57 0 0.66x+4 x 0.28x+6.85 0 0.5x+2 0.75x 0.25x+4 0 x+12 x

67


R4 1 O6 1

R2

R3

I4 1

2 0.5

1

2

1 O5

O4 1

2 R1

I2

I1

I3 1

2

1

O1

1 O3

O2 1

2 0.5 P1

1

P2

20. ábra. A 7. példa maximális struktúrája.

költség

költség

kapacitás

kapacitás

P YHOHWLHJ\VpJ

P YHOHWLHJ\VpJ költség

költség

kapacitás

kapacitás

P YHOHWLHJ\VpJ

P YHOHWLHJ\VpJ költség

költség

kapacitás

P YHOHWLHJ\VpJ

kapacitás

P YHOHWLHJ\VpJ

21. ábra. Az inicializáló lépésben kiszámolt költségfüggvény és két relaxációja. (Jelölések: folytonos vonal – költség, szagatott vonal – kezdeti relaxáció, pontozott vonal – relaxáció az intervallum kiválasztása után.)

68


10.4. Folyamat-hálózatszintézis feladat megoldása SiUKX]DPRVP N|GpVLHOY V]iPtWyJpSHNHQ $] HGGLJLHNW O HOWpU HQ D] LWW EHPXWDWRWW PyGV]HU QHP D] DODS IRO\DPDW hálózatszintézis feladat egy kiterjesztését oldja meg, hanem az alap folyamatKiOy]DWV]LQWp]LV IHODGDWRW PHJROGy $%% DOJRULWPXV WHFKQLNDL MHOOHJ NLWHUMHV]WpVpWDQQDNSiUKX]DPRVP N|GpVLHOY V]iPtWyJpSHNHQYpJUHKDMWKDWy változatát mutatjuk be. Mivel csak az algoritmus megvalósítása tér el, ebben az esetben a struktúra reprezentáció,

a

gyorsított

branch-and-bound

szétválasztó-,

illetve

költségfüggvénye is változtatás nélkül alkalmazható. Amíg azonban a szekvenciális algoritmus egyben megadja a számítógép által végrehajtandó XWDVtWiVVRUR]DWRW SiUKX]DPRV P N|GpVL HOY V]iPtWyJpS HVHWpQ PLQGHQ HJ\HV processzorra meg kell adni, hogy az algoritmus mely részét, mely utasítássorozatot kell végrehajtania. Természetesen megengedett, hogy ugyanazt az algoritmusrészt több processzor LVYpJUHKDMWVDV WD]LVOHKHWVpJHVKRJ\D]|VV]HVSURFHVV]RUIHODGDWDD]RQRV 0LYHO D SiUKX]DPRVDQ P N|G SURFHVV]RURN XJ\DQD]RQ IHODGDW PHJROGiViQ dolgoznak, általában annak független részfeladatait végrehajtva, a processzorok a folyamat-hálózatszintézis feladatmegoldását szolgáló utasítások mellett a IHODGDWRN YpJUHKDMWiViW YH]pUO SURFHVV]RURN N|]|WWL NRPPXQLNiFLyW LV YpJH]QHN.|]|VPHPyULDWHUOHWWHOLVUHQGHONH] UHQGV]HUHNHVHWpQH]MHOHQWKHWL valamilyen adat felírását a közös memóriaterületre. Osztott memóriájú rendszerek esetén valódi kommunikációról van szó, a processzorok csatornákon keresztül üzeneteket küldve vezérlik a feladat végrehajtását. A fejezetben ismertetett algoritmus is egy osztott memóriájú rendszerre, transzputerre készült. Ilyen esetekben egy processzor gyakran több részfeladatot – processzt - futtat, ezek egyike általában a feladatot megoldó processz, itt például az ABB algoritmus, míg egy másik processz például az üzenetek kezelését (fogadását, továbbítását) végzi. $IHODGDWPHJROGiVDV]HPSRQWMiEyOIHOHVOHJHVNRPPXQLNiFLyWYpJ] SURFHVV] iOWDOiEDQ MyYDO HJ\V]HU EE D JpSLG QHN FVDN D W|UHGpNpW KDV]QiOMD NO|QEHQ 69


nem érünk el gyorsulást a több processzor használatával). Ugyanakkor léteznek RO\DQ PyGV]HUHN DPLNRU YDODPHO\LN SURFHVV]RU DODSYHW IHODGDWD D PHJROGiV vezérlése, azaz a kommunikáció irányítása, de itt a többi processzornál a kommunikáció valóban elhanyagolható, ezek az ún. mester-szolga típusú algoritmusok. $EUDQFKDQGERXQGWtSXV~DOJRULWPXVSiUKX]DPRVYpJUHKDMWiViUDNpWDODSYHW módszer létezik: az egyik a mester-szolga (master-slave) algoritmus, a másik a dinamikus processzorterhelés-elosztó (load balance) módszer. 10.4.1. Szoftver-architektúra Mivel


feladat

megoldása

során

egy

adott

részproblémából generált részproblémák száma nagy eltéréseket mutathat, nehéz PLQGHQ IHODGDWWtSXVUD MyO P N|G ORDG EDODQFLQJ PyGV]HUW PHJDGQL Ugyanakkor a folyamat-hálózatszintézis feladat egy-egy részproblémájának feldolgozása önmagában is nehéz feladat (korlátozó függvény kiszámolása, új részproblémák generálása), így mester-szolga algoritmust alkalmazva [38] várhatóan sok processzort használva sem válik a mester a feladat megoldása VRUiQV] NNHUHV]WPHWV]HWWp A processzorok közötti fizikai kapcsolat korlátozott, a mester-szolga típusú algoritmusoknál ideális csillag topológia helyett a számítógép struktúrájának PHJIHOHO WRSROyJLiW NHOO GHILQLiOQL (ONpV]OW D SiUKX]DPRV $%% DOJRULWPXV DODSYiOWR]DWD J\ U 22. ábra) és bináris fa processzortopológia esetén. Az algoritmusokat

occam

nyelven

implementáltuk,

ezt

a

konkurens

algoritmusokhoz kifejlesztett nyelvet lényegében a transzputerrel együtt fejlesztették ki. (Transzputerhez való hozzáférést a JATE biztosította, amit ezúton is köszönünk.)

Mester

Szolga #1

Szolga #2

Szolga #n

22iEUD*\ U WRSROyJLD

0LQWD]DJ\ U WRSROyJLiWEHPXWDWyiEUiQLVOiWKDWyDIL]LNDLNDSFVRODWNRUOiWDL miatt a szolga processzeknek a többi processz közötti üzeneteket is továbbítania

70


kell. Ezért a szolga processz a részfeladatokat megoldó processz mellett több, kommunikációt biztosító processzt is tartalmaz (23. ábra).

e l ô z ô s z o l g a

transzfer

ABB algoritmus

puffer

multiplexer

k ö v e t ô s z o l g a

23iEUD(J\N|]EOV V]ROJDVWUXNW~UiMD

10.4.2. Eredmények A kidolgozott eszközt három feladat megoldásával teszteltük. A legkisebb IHODGDWEDQ $ IHODGDW D P YHOHWL HJ\VpJHN V]iPD 0LYHO HQQHN D feladatnak a megoldása a szekvenciális ABB algoritmus segítségével több megoldás keresése esetén is mindössze egy másodperc, ezért ennél kisebb példák vizsgálata párhuzamos feldolgozású algoritmussal már értelmetlen. $PiVLNWHV]WHOpVEHEHYRQWIHODGDW%IHODGDW P YHOHWLHJ\VpJHWWDUWDOPD] (QQpODIHODGDWQiOPiUMyOOiWKDWy D YpJUHKDMWiVL LG V]i]DOpNRV FV|NNHQpVH $ KDUPDGLNIHODGDW&IHODGDW P YHOHWLHJ\VpJHLQHNV]iPDXJ\DQFVDNGHD maximális struktúra bonyolultsága miatt (sok az él a P-gráfban) ennek a IHODGDWQDN D PHJROGiVD OpQ\HJHVHQ KRVV]DEE LGHLJ WDUW LWW PiU MHOHQW V gyorsítást jelent abszolút értékben is a párhuzamos feldolgozás. $WHV]WHOpVVRUiQDIHODGDWRN0,/3PRGHOOMpWROGRWWXNPHJD]LG HUHGPpQ\HN párhuzamos feldolgozás esetén T800-as transzputeren mért futási eredmények, a V]HNYHQFLiOLV IXWWDWiVRN LG HUHGPpQ\HL D 7DV WUDQV]SXWHU VHEHVVpJpQHN PHJIHOHO 3HQWLXPHVSURFHVV]RUUDOHOOiWRWW3&YHOPpUWHUHGPpQ\HN A tesztelés során az algoritmusok a legjobb 5 megoldást keresték, a teszteredményeket a 5. táblázat tartalmazza.

71


5. táblázat. Futási eredmények a legjobb 5 megoldás keresése esetén.

*\ U

processzortopológia N/A processzorok száma

1 LG

4

8

16

4

8

16

YpJUHKDMWiVLLG relatív gyorsítás*

"A" feladat

0.93 0.71 0.61 0.62 3.05 5.24 10.66

"B" feladat

6.92 3.82 2.15 2.15 2.21 2.49 4.97

"C" feladat

474 160.2 70.3 34.3 1.35 1.19 1.16

YpJUHKDMWiVLLG ⋅(processzorok száma)/(szekvenciális algoritmus végrehajtási ideje)

processzortopológia N/A processzorok száma

bináris fa

1 LG

4

8

16

4

8

16

YpJUHKDMWiVLLG relatív gyorsítás*

"A" feladat

0.93 0.71 0.61 0.62 3.05 5.24 10.66

"B" feladat

6.92 3.81 2.13 2.14 2.2 2.46 4.95

"C" feladat

474 160.2 70.3 34.2 1.35 1.19 1.15

YpJUHKDMWiVLLG ⋅(processzorok száma)/(szekvenciális algoritmus végrehajtási ideje)

A táblázat adatai alapján nyilvánvaló, hogy (i) nincs lényeges különbség a megvalósított két processzortopológia WHOMHVtWPpQ\HN|]|WW$MREEQDNW Q ELQiULVIDWRSROyJLDHO Q\HN|]HOHEE vannak a szolgák a mesterhez") várhatóan csak több processzor használatakor mutatkozik meg határozottabban, illetve olyan feladatok HVHWpQ DKRO VRN UpV]SUREOpPiW NHOO PHJROGDQL WHKiW HEE O D V]HPSRQWEyO QDJ\DIHODGDWXJ\DQDNNRUHJ\HVUpV]SUREOpPiNPHJROGiVDNHYpVLG WYHV] igénybe, azaz nincs több nagyságrendnyi különbség a kommunikációra IRUGtWRWWLG K|]NpSHVW (ii) Az "A" feladatot nem érdemes párhuzamos feldolgozású algoritmussal megoldani, a kapott gyorsítás sem százalékosan, sem abszolút értékben nem MHOHQW V (iii) A "B" feladat már nem tud 16 processzornak feladatot adni, a plusz 8 processzor lényegében csak plusz adminisztrációt jelent erre a feladatra. (iv) A "C" feladat esetén a párhuzamos algoritmus gyorsulása közel lineáris (a relatív gyorsítás 1-hez közel van). Ez azt mutatja, hogy a kommunikációra

72


IRUGtWRWWLG HOKDQ\DJROKDWyDUpV]SUREOpPiNPHJROGiViUDIRUGtWRWW LG K|] képest, továbbá a szolga processzorok terhelése egyenletes. A processzorok leterheltségét az "A" és "B" feladatok esetén nem érdemes vizsgálni, mindkét feladat esetében maximum 8 processzort érdemes DONDOPD]QLWRYiEELIXWiVLLG FV|NNHQWpVQHPpUKHW HOPLQGNpWIHODGDWQiOD] HOV UpV]IHODGDWPHJROGiVDXWiQ~MDEEUpV]SUREOpPDNHOHWNH]LNpVHQQpOVRKD nem lesz több, azaz 7 szolgánál több alkalmazása felesleges). Az "A" feladatnál minden szolga 1 vagy 2 részfeladatot old meg, míg a "B" feladat esetén 3 vagy 4 részfeladatot. A "C" feladat megoldását érdemes részletesebben megvizsgálni. Itt a közel lineáris

gyorsítás

azt

mutatja,

hogy

az

egyes

feladatok

megoldása

QDJ\ViJUHQGHNNHOQDJ\REELG WYHV]LJpQ\EHPLQWDUpV]IHODGDWKR]NDSFVROKDWy NRPPXQLNiFLyV LG N IHODGDW NLNOGpVH HUHGPpQ\HN YLVV]DNOGpVH (QQpO D feladatnál az egyes szolga processzoroknak már jóval több részproblémát kell PHJROGDQLXNPHJN|]HOtW HQV]ROJDHVHWpQV]ROJDHVHWpQV]ROJD esetén 25 részproblémát). Egyes szolgák által megoldott részproblémák száma természetesen lényegesen eltérhet, mivel a részproblémák megoldására fordított LG N LV OpQ\HJHVHQ HOWpUKHWQHN (]HN D] HOWpUpVHN DNNRU RNR]QDN HJ\HQHWOHQ OHWHUKHOWVpJHWKDW|EERO\DQUpV]SUREOpPDYDQDPHO\PHJROGiViUDIRUGtWRWWLG QHP WpU HO OpQ\HJHVHQ D KR]]i NDSFVROyGy NRPPXQLNiFLyUD IRUGtWRWW LG W O ekkor ugyanis az ilyen részfeladatokat megoldó szolgák leterheltsége lényegesen rosszabb lesz, illetve ha az adott szolga a mesterhez "közel" áll a processzortopológiában, a többi processzor maradhat munka nélkül. A "C" IHODGDWUpV]SUREOpPiLQDNPHJROGiViKR]V]NVpJHVLG NHWD24. ábra illusztrálja $ N|]HO UpV]SUREOpPiW D PHJROGiVXNKR] V]NVpJHV LG N|]EOV részprobléma esetén ez természetesen a korlátozó függvény végrehajtásának és a leszármazottak generálásának ideje) szerint rendeztük, így az ábráról jól OHROYDVKDWy KRJ\ L D] HJ\ UpV]SUREOpPD PHJROGiViUD IRUGtWRWW LG PLQGHQ esetben több tizedmásodperc, (ii) a részproblémák felénél az egy másodpercet is PHJKDODGMD pV LLL D UpV]SUREOpPiN PHJROGiViUD IRUGtWRWW LG N HORV]OiVD egyenletlen.

73


2.5

2

1.5

1

0.5

381

361

341

321

301

281

261

241

221

201

181

161

141

121

101

81

61

41

1

21

0

24iEUD$&IHODGDWUpV]SUREOpPiLQDNPHJROGiViKR]V]NVpJHVLG N (másodpercben).

Az ábrában megadott részproblémák a szekvenciális algoritmus által megoldott részproblémák. A párhuzamos algoritmus néhány plusz részproblémától eltekintve lényegében ugyanezeket oldja meg, ezért a párhuzamos algoritmus által megoldott részproblémákat tartalmazó ábra eltérése a fenti ábrától HOKDQ\DJROKDWy OHQQH XJ\DQDNNRU D YpJUHKDMWiVL LG PpUpVH pV NO|Q|VHQ D] LG HUHGPpQ\HN WRYiEEtWiVD EHIRO\iVROKDWMD D] DOJRULWPXV P N|GpVpW PtJ D V]HNYHQFLiOLVDOJRULWPXVWFVDNODVVtWKDWMDGHDP N|GpVpWQHPEHIRO\iVROMD Ezeket az adatokat az egy részproblémához kapcsolódó kommunikáció idejével NHOO |VV]HKDVRQOtWDQL (KKH] PHJDGXQN HJ\ GXUYD IHOV NRUOiWRW D] HJ\ UpV]SUREOpPiKR] NDSFVROyGy NRPPXQLNiFLy LGHMpUH DPL NpW UpV]E O iOO D mester részfeladatot küld a szolgának, illetve a szolga eredményt (új megoldások, új részproblémák) küld vissza a mesternek. A részfeladat küldése FVDWRUQDLQLFLDOL]iOiVEyOV]NVpJHVLG µsec) és 10 egész szám (40 byte) NOGpVpE O×0.58 µsec = 23.2 µVHF iOOD]D]DV]NVpJHVLG NHYHVHEEPLQW 40 µsec. Az eredmény visszaküldése hasonlóan csatorna inicializálásból és PD[LPXPYDOyVV]iPE\WH NOGpVpE OiOOH]XWyEELQDJ\RQH[WUpP HVHW PHJROGiV YLVV]DNOGpVpW MHOHQWL DPL QDJ\RQ GXUYD IHOV NRUOiW (J\ részproblémához kapcsolódó kommunikáció ideje tehát kevesebb, mint 1600 µsec = 0.0016 sec. 0LQWOiWKDWyDUpV]SUREOpPiNPHJROGiViKR]V]NVpJHVLG NN|]ODOHJNLVHEE LVQDJ\ViJUHQGHNNHOQDJ\REEDNRPPXQLNiFLyUDIRUGtWRWWLG QpO$]D]DPHVWHU

74


a 16 szolgánál jóval többet tudna irányítani úgy, hogy azok terhelése egyenletes maradna. A teszteredmények azt mutatják, hogy a párhuzamos feldolgozású gyorsított branch-and-bound algoritmus alkalmazása indokolt bonyolult feladatok - amely nem feltétlenül jelent nagy feladatot - megoldása esetén.

75

Összefoglalás

11. Összefoglalás $ GROJR]DWEDQ EHPXWDWWXN D N|YHWNH] IRO\DPDWKiOy]DWV]LQWp]LV IHODGDW kiterjesztéseket: hulladékkezeléssel integrált folyamat-hálózatszintézis, integrált folyamat-hálózat-

és

irányítórendszer

tervezés,


V]DNDV]RVDQ IRO\WRQRV FpOIJJYpQ\ P YHOHWL HJ\VpJHNNHO IRO\DPDW KiOy]DWV]LQWp]LVIHODGDWPHJROGiVDSiUKX]DPRVP N|GpVLHOY V]iPtWyJpSHNHQ 0LQGHJ\LN NLWHUMHV]WpV PHJROGiViUD PHJDGWXQN HJ\ NRPELQDWRULNXV MHOOHJ D feladattípus jellegzetességeit jól kihasználó megoldó módszert. A módszerek PLQGHJ\LNH OHKHW Yp WHV]L D] RSWLPiOLV PHJROGiVRN KDWpNRQ\ NHUHVpVpW matematikailag jól megalapozott feladat reprezentációra építenek, az optimális megoldás megtalálása mindegyik módszer esetében garantált. Mind az itt ismertetett, mind más kiterjesztések kombinált alkalmazása lehetséges, ezzel gyakorlati szempontból fontos, ugyanakkor hagyományos módszerekkel nehezen vagy nem megoldható feladatosztályok megoldása válik lehetségessé.

76

Irodalomjegyzék

12. Irodalomjegyzék [1]

Berger, S. A., The Pollution Prevention Hierarchy as an R&D Management Tool, AIChE Symposium Series, Volume on Pollution Prevention via Process and Product Modifications (Eds: M. M. ElHalwagi and D. P. Petrides), 90(303), 23-29 (1995).

[2]

Brendel, M. H., F. Friedler, and L. T. Fan, Combinatorial Foundation for Logical Formulation in Process Network Synthesis, accepted for publication in Computers chem. Engng (1998).

[3]

Constantinou, L., C. Jakslund, K. Bagherpour, R. Gani, and I. D. L. Bogle, Application of the Group Contribution Approach to Tackle Environmentally Related Problems, AIChE Symposium Series, Volume on Pollution Prevention via Process and Product Modifications (Eds: M. M. El-Halwagi and D. P. Petrides), 90(303), 105-117 (1995).

[4]

Crabtree, E. W. and M. M. El-Halwagi, Synthesis of Environmentally Acceptable Reactions, AIChE Symposium Series, Volume on Pollution Prevention via Process and Product Modifications (Eds: M. M. ElHalwagi and D. P. Petrides), 90(303), 117-128 (1995).

[5]

Duran, M. A. and I. E. Grossmann, An Outer-Approximation Algorithm for a Class of Mixed-integer Nonlinear Programs, Math. Programming, 36, 307 (1986).

[6]

Eckstein, J., Parallel branch-and-bound algorithms for general mixed integer programming on the CM-5, Technical report TMC-257, Thinking Machines Corporation, Cambridge, MA. U.S.A. (1993).

[7]

Floudas, C. A. and V. Visweswaran, A Global Optimization Algorithm (GOP) for Certain Classes of Nonconvex NLPs - I. Theory, Computers chem. Engng, 14, 1397-1417 (1990).

[8]

Fraga, E. S. and K. I. M. McKinnon, The Use of Dynamic Programming with Parallel Computers for Process Synthesis, Computers chem. Engng, 18, 1-13 (1994).

[9]

Fraga, E. S. and K. I. M. McKinnon, Portable Code for Process Synthesis Using Workstation Clusters and Distributed Memory Multicomputers, Computers chem. Engng, 19, 759-774 (1995).

77

Irodalomjegyzék

[10] Friedler, F., K. Tarjan, Y. W. Huang, and L. T. Fan, Combinatorial Algorithms for Process Synthesis, Computers chem. Engng, 16, S313-20 (1992). [11] Friedler, F., K. Tarjan, Y. W. Huang, and L. T. Fan, Graph-Theoretic Approach to Process Synthesis: Axioms and Theorems, Chem. Eng. Sci., 47(8), 1973-1988 (1992). [12] Friedler, F., K. Tarjan, Y. W. Huang, and L. T. Fan, Graph-Theoretic Approach to Process Synthesis: Polynomial Algorithm for Maximal Structure Generation, Computers chem. Engng, 17(9), 929-942 (1993). [13] Friedler, F., J. Varga, and L. T. Fan, A Combinatorial Approach to the Multiperiod Synthesis of the Structure of Process Industries, Proceedings of the ESCAPE-3 (European Symposium on Computer Aided Process Engineering), 2-6 (1993). [14] Friedler, F., J. B. Varga, and L. T. Fan, Decision-Mapping: A Tool for Consistent and Complete Decisions in Process Synthesis, Chem. Engng Sci., 50(11), 1755-1768 (1995). [15] Friedler, F., J. B. Varga, and L. T. Fan, Algorithmic Approach to the Integration of Total Flowsheet Synthesis and Waste Minimization, AIChE Symposium Series, Volume on Pollution Prevention via Process and Product Modifications (Eds: M. M. El-Halwagi and D. P. Petrides), 90(303), 86-97 (1995). [16] Friedler, F., J. B. Varga, E. Feher, and L. T. Fan, Combinatorially Accelerated Branch-and-Bound Method for Solving the MIP Model of Process Network Synthesis, Nonconvex Optimization and Its Applications, State of the Art in Global Optimization, Computational Methods and Applications (Eds: C. A. Floudas and P. M. Pardalos), 609-626, Kluwer Academic Publishers, Norwell, MA, U.S.A. (1996). [17] Friedler, F., L. T. Fan, and B. Imreh, Process Network Synthesis: Problem Definition, Networks, 28(2), 119-124 (1998). [18] Gál, I. P., Gráfelméleti módszerek alkalmazása az irányításelméletben, Ph.D. értekezés (1997). [19] Gál, I. P., J. B. Varga, and K. M. Hangos, Integrated Structure Design of a Process and Its Control System, J. Proc. Cont., 8(4), 251-263 (1998). [20] Georgiou, A., and C. A. Floudas, Simultaneous Process Synthesis and Control: Minimization of Disturbance Propagation in Heat Recovery Systems. Foundations of Computer-Aided Process Design (Eds: J. Siirola, J., I. E. Grossmann, and G. Stephanopoulos), 435-450 (1990). 78

Irodalomjegyzék

[21] Hangos, K. M., F. Friedler, J. Varga, and L. T. Fan, Graph-Theoretic Approach to Integrated Process and Control System Synthesis, Proceedings of the IFAC ‘94 (International Federation of Automatic Control), Workshop on Integration of Process Design and Control, 58-63 (1994). [22] Hangos, K. M., J. B. Varga, F. Friedler, and L. T. Fan, Integrated Synthesis of a Process and its Fault-Tolerant Control System, Computers chem. Engng, 19, S465-470 (1995). [23] High, K. A. and R. D. LaRoche, Parallel Nonlinear Optimization Techniques for Chemical Process Design Problems, Computers chem. Engng, 19, 807-827 (1995). [24] Ibaraki, T., Theoretical Comparisons of Search Strategies in Branch-andBound Algorithms, Journal of Computer and Information Science, 5, 315344 (1976). [25] Kocis, G. R., and I. E. Grossmann, A Modeling and Decomposition Strategy for the MINLP Optimization of Process Flowsheets, Computers chem. Engng, 13, 797-819 (1989) [26] Kudva, G. K. and J. F. Pekny, DCABB a Distributed Control Architecture for Branch and Bound Calculations, Computers chem. Engng, 19, 847-866 (1995). [27] Lawler, E. L. and D. E. Wood, Branch-and-Bound Methods: A Survey, Operations Research, 14(4), 699-719 (1966). [28] Luyben, M. L. and C. A. Floudas, A Multiobjective Optimization Approach for Analysing the Interaction of Design and Control, Part 1: Theoretical Framework, Interactions between Process Design and Process Control (Ed. J. D. Perkins), 101-106, Pergamon Press, Oxford (1992). [29] Meyer, R. R. and S. A. Zenios, Parallel Optimization on Novel Computer Architectures, Ann. Opn. Res., 14 (1988). [30] Nichida, N. and A. Ichikawa, Synthesis of Optimal Dynamic Process Systems by a Gradient Method, Ind. Eng. Chem. Proc. Des. Dev., 14(3), 236-242 (1975). [31] Nichida, N., Y. A. Liu, and A. Ichikawa, Studies in Chemical Process Design and Synthesis, part 2: Optimal Synthesis of Dynamic Process Systems with Uncertainty, AIChE Journal, 22(3), 539-549 (1976).

79

Irodalomjegyzék

[32] Pardalos, P. M., A.T. Philips, and J. B. Rosen, Topics in Parallel Computing in Mathematical Programming, Science Press, New York (1992). [33] Quinn, M. J., Designing Efficient Algorithms for Parallel Computers, McGraw-Hill Computer Science Series, New York (1987). [34] Raman, R. and I. E. Grossmann, Symbolic Integration of Logic in MILP Branch and Bound Methods for the Synthesis of Process Networks, Annals of Operations Research, 42, 169-191 (1993). [35] Rittmeyer, R. W., Prepare an Effective Pollution-Prevention Program, Chemical Engineering Progress, 87, 56-62 (1991). [36] Schnabel, R. B., Concurrent Function Evaluations in Local and Global Optimization, Comp. Meth. Appl. Mech. Engng, 64, 537-552 (1987). [37] Varga, E. I. and K. M. Hangos, The Effect of Heat Exchanger Network Topology on the Network Control Properties, Control Engineering Practice, 1, 375-380 (1993). [38] Varga, J. B., F. Friedler, and L. T. Fan, Parallelization of the Accelerated Branch and Bound Algorithm of Process Synthesis: Application in Total Flowsheet Synthesis, Acta Chimica Slovenica, 42(1), 15-20 (1995). [39] Varga, J. B., F. Friedler, and L. T. Fan, Risk Reduction through Waste Minimizing Process Synthesis, Proceedings of the 21st Annual RREL (Risk Reduction Engineering Laboratory) Research Symposium, 359-363 (1995). [40] Visweswaran, V. and C. A. Floudas, A Global Optimization Algorithm (GOP) for Certain Classes of Nonconvex NLPs - II. Application of Theory and Test Problems, Computers chem. Engng, 14, 1419-1434 (1990).

80

Függelék

13. Függelék

13.1. Branch-and-bound A “branch-and-bound” egy eszköztípus összefoglaló neve, jól ismert technika optimalizálási feladatok megoldására [27], sok változata ismert [24], itt csak egy olyan általános formális leírást adunk meg, ami szükséges a folyamathálózatszintézis

megoldására

kidolgozott

gyorsított

branch-and-bound

algoritmus definiálásához. A feladat definiálásához meg kell adnunk a lehetséges megoldások halmazát (feltételrendszer), valamint azt a szempontot (célfüggvény), ami szerint az optimális megoldást keressük: Tegyük fel, hogy adott egy f célfüggvény, amelyet a lehetséges megoldások S0 halmazán kell minimalizálnunk. Bevezetünk egy a lehetséges megoldások KDOPD]iQiO QHP V] NHEE 30 halmazt, e halmaz részhalmazait nevezzük részproblémáknak. A Pi részprobléma optimális megoldásainak halmazát Opt(Pi)-vel, az optimum értékét F(Pi)-vel jelöljük. Ha Opt(Pi) halmaz üres, akkor F(Pi) értékét végtelennek tekintjük. A szétválasztó lépésben egy részproblémát bontunk részhalmazaira, új részproblémákat generálva. A szétválasztó lépés után egy Pi részproblémából generált új részproblémák halmazát son(Pi)-vel jelöljük. A son operátornak az alábbi tulajdonságokkal kell rendelkeznie: (i) a son(Pi) elemeinek uniója Pi-t adja, (ii) a son(Pi) minden eleme valódi részhalmaza Pi-nek. Ha a Pi halmaz üres, akkor Opt(Pi) is az, így Pi-re a szétválasztás nem folytatódik. Nem szükséges feltétel, de a hatékonyságot javítja, ha a son(Pi) elemei diszjunkt halmazok. /HJ\HQ D * D] ) RO\DQ NRUOiWR]y IJJYpQ\H DPHO\ D N|YHWNH] IHOWpWHOHNHW teljesíti: (i)

G(Pi)≤F(Pi) minden Pi∈℘(P0)\{∅} részproblémára,

81

Függelék

(ii) G(Pi) = ∞ ha Pi = ∅ és (iii) G(Pij)≥G(Pi), Pij∈son(Pi). A

megoldandó

részproblémák

közül

bármelyik

választható

további

IHOGROJR]iVUD PHO\HW D] V NHUHV IJJYpQ\ KDWiUR] PHJ gVV]HIRJODOYD D branch-and-bound

algoritmus

pontos

megadásához

szükség

van

egy

V]pWYiODV]WyVRQ HJ\NHUHV V pVHJ\NRUOiWR]y* IJJYpQ\UH Az algoritmus végességének biztosításához azonban vagy további feltételeket NHOO D NRUOiWR]y IJJYpQ\QHN WHOMHVtWHQLH YDJ\ DOVy pV IHOV NRUOiWRNDW alkalmazva adhatunk lezárási feltétel(eke)t, melyek teljesülése esetén az adott részprobléma dekomponálása nem folytatódik. Ilyen feltétel lehet például a vegyes egész programozási feladatoknál az egész változók értékének HJ\pUWHOP VtWpVH XWiQ D *3i) = F(Pi) feltétel. Ekkor a korlátozó függvény minimumhelye lehetséges megoldás lesz. Folyamat-hálózatszintézis feladat PHJROGiVDNRU H] D IHOWpWHO D PHJROGiV P YHOHWL HJ\VpJHLQHN SRQWRV PHJDGiVD XWiQ D] HUHGHWL N|OWVpJIJJYpQ\ DONDOPD]iViW MHOHQWL 0HJIHOHO PHJiOOiVL feltétel teljesülése után rendelkezésünkre áll az Opt(Pi) halmaz, illetve az Opt(Pi) egy részhalmaza, ha a korlátozó függvény egy optimális megoldást ad meg valamely részfeladatra optimális megoldáshalmaz esetén is. $EUDQFKDQGERXQGPyGV]HUOpSpVHLDN|YHWNH] N 1. Inicializálás A := {P0}; z := ∝; sol := ∅; 2. Keresés Ha A = ∅, ugrás a 7. lépésre, egyébként Pi := s(A); 3. Teszt Ha G(Pi) = ∝ vagy G(Pi)>z, akkor ugrás a 6. lépésre; Ha a megállási feltétel teljesül, ugrás az 5. lépésre; 4. Szétválasztás A := (A∪son(Pi))\{Pi}; ugrás a 2. lépésre; 5. Frissítés

82

Függelék

Ha z>F(Pi), sol := Opt(Pi); Ha z = F(Pi), sol := sol∪Opt(Pi); z := min(z, F(Pi)); .|]EOV UpV]SUREOpPDHVHWpQD]2SW(Pi) és az F(Pi) helyett alkalmazható a G függvény által meghatározott optimális megoldás illetve az F függvény értéke erre a megoldásra.) 6. Lezárás A := A\{Pi}; ugrás a 2. lépésre; 7. Megállás Ekkor sol ⊆ Opt(S0) és z = F(S0). A branch-and-bound algoritmus garantálja optimális megoldás és az optimum értékének megtalálását, ha az létezik. Ha az optimum értéke ∝ az algoritmus lefutása után, akkor nincs lehetséges megoldás. A branch-and-bound típusú DOJRULWPXVRN WRYiEEL HO Q\HL D] RSWLPiOLV PHJROGiV PHOOHWW D] Q OHJMREE PHJROGiV JHQHUiOiViQDN OHKHW VpJH D KHXULV]WLNXV DOJRULWPXVRNNDO YDOy NRPELQiOKDWyViJ YDODPLQW D My PHJYDOyVtWKDWyViJ SiUKX]DPRV P N|GpVL HOY számítógépeken [6, 33].

83

A FOLYAMAT- HÁLÓZATSZINTÉZIS FELADAT KITERJESZTÉSEI

Recommend Documents