Veronika Steffanová. Softwarový balík pro práci s polyedry. Univerzita Karlova v Praze Matematicko-fyzikální fakulta. Katedra aplikované matematiky

Univerzita Karlova v Praze Matematicko-fyzikáln´ı fakulta

´ RSK ˇ ´ PRACE ´ BAKALA A

Veronika Steffanová Softwarový bal´ık pro práci s polyedry Katedra aplikované matematiky

Vedouc´ı bakaláˇrské práce: Mgr. Milan Hlad´ık, Ph.D. Studijn´ı program: Informatika Studijn´ı obor: Obecná informatika

Praha 2012

Ráda bych na tomto m´ıstˇe podˇekovala vedouc´ımu mé práce za jeho nekoneˇcnou trpˇelivost a své rodinˇe za podporu a toleranci, bez kterých by tato práce nikdy nemohla vzniknout.

Prohlaˇsuji, zˇ e jsem tuto bakaláˇrskou práci vypracovala samostatnˇe a výhradnˇe s pouˇzit´ım citovaných pramen˚u, literatury a dalˇs´ıch odborných zdroj˚u. Beru na vˇedom´ı, zˇ e se na moji práci vztahuj´ı práva a povinnosti vyplývaj´ıc´ı ze zákona cˇ . 121/2000 Sb., autorského zákona v platném znˇen´ı, zejména skuteˇcnost, zˇ e Univerzita Karlova v Praze má právo na uzavˇren´ı licenˇcn´ı smlouvy o uˇzit´ı této práce jako sˇkoln´ıho d´ıla podle §60 odst. 1 autorského zákona.

V Praze dne 30. cˇ ervence 2012

Veronika Steffanová

Název práce: Softwarový bal´ık pro práci s polyedry Autor: Veronika Steffanová Katedra: Katedra aplikované matematiky Vedouc´ı bakaláˇrské práce: Mgr. Milan Hlad´ık, Ph.D., Katedra aplikované matematiky Abstrakt: V práci jsme se zamˇeˇrili na téma polyedr˚u a základn´ıch algoritm˚u pro práci s nimi. Nejdˇr´ıve je pˇredloˇzena vˇeta o ekvivalenci vrcholové a nerovnicové reprezentace a poté jsou popsány vybrané algoritmy, které ˇreˇs´ı jejich vzájemný pˇrevod. Praktická cˇ a´ st se pak týká implementace tˇr´ı funkc´ı zaloˇzených na zvolených algoritmech a nˇekolika dalˇs´ıch, které jsou jejich pˇr´ımým d˚usledkem. Výsledkem je knihovna funkc´ı pro MATLAB, která obsahuje nástroje pro pˇrevod mezi jednotlivými reprezentacemi, konvexn´ı sjednocen´ı dvou polyedr˚u, pr˚unik dvou polyedr˚u a odstranˇen´ı redundantn´ıch vrchol˚u (resp. nerovnic) z vrcholové (resp. nerovnicové) reprezentace. Kromˇe toho jsme porovnali dva námi implementované algoritmy pro pˇrevod z vrcholové do nerovnicové reprezentace, a to jak z hlediska cˇ asové, tak i prostorové a implementaˇcn´ı nároˇcnosti. Kl´ıcˇ ová slova: polyedr, MATLAB, lineárn´ı programován´ı, konvexn´ı obal

Title: Software package for polyhedra operation Author: Veronika Steffanová Department: Department of Applied Mathematics Supervisor: Mgr. Milan Hlad´ık, Ph.D., Department of Applied Mathematics Abstract: The topic of the thesis is focused on convex polyhedra and algorithms for working with them. At first we give the theorem about vertex and facet description and then we describe selected algorithms connected to the problem of the conversion between these two descriptions. In the practical part we implement three functions using three selected algorithms and a few other functions, which are simple results of the three algorithms. Finally we get a MATLAB library, which contains functions for vertex enumeration, facet enumeration, convex union of two polyhedra, intersection of two polyhedra and irredudancy problem for facets and vertices, too. By the way we compare our two implemented algorithms for facet enumeration, but not only according the running time, also according the memory requirements and the implementation complexity. Keywords: polyhedron, MATLAB, linear programming, convex hull

Obsah ´ 1 Uvod ´ Uvod 1.1 1.2

3

Základn´ı pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algoritmické ˇreˇsen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Seznam hlavn´ıch funkc´ı . . . . . . . . . . . . . . . . . . . .

2 Lineárn´ı programován´ı 2.1 Základn´ı pojmy a tvrzen´ı . . . . . . . . . 2.2 Simplexová metoda . . . . . . . . . . . . 2.2.1 Výchoz´ı pˇr´ıpustné bázické ˇreˇsen´ı 2.2.2 Bˇezˇ ný krok algoritmu . . . . . . 2.2.3 Vyhodnocen´ı posledn´ıho kroku .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

3 Pouˇzité algoritmy vyuˇz´ıvaj´ıc´ı simplexovou metodu 3.1 Algoritmus pro pˇrevod z nerovnicové do vrcholové reprezentace 3.1.1 Analýza algoritmu . . . . . . . . . . . . . . . . . . . . 3.1.2 Neomezené hrany . . . . . . . . . . . . . . . . . . . . . 3.2 Algoritmus pro pˇrevod z vrcholové do nerovnicové reprezentace 3.2.1 Dualita . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Popis algoritmu . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Analýza algoritmu . . . . . . . . . . . . . . . . . . . . 3.2.4 Fasety procházej´ıc´ı poˇca´ tkem . . . . . . . . . . . . . . 4 Konvexn´ı obal kombinatoricky v obecné dimenzi 4.1 Druhy algoritm˚u . . . . . . . . . . . . . . . . 4.1.1 Inkrementáln´ı algoritmy . . . . . . . 4.1.2 Algoritmy procházen´ı grafem . . . . 4.1.3 Algoritmy rozdˇel-a-panuj . . . . . . . 4.2 Algoritmus dvojité reprezentace . . . . . . .

. . . . .

. . . . .

5 Uˇzivatelská dokumentace 5.1 Datové struktury pro vstup a výstup . . . . . . . 5.2 Pˇrevod z nerovnicové do vrcholové reprezentace . 5.3 Pˇrevod z vrcholové do nerovnicové reprezentace . 5.4 Konvexn´ı sjednocen´ı . . . . . . . . . . . . . . . 5.5 Pr˚unik . . . . . . . . . . . . . . . . . . . . . . . 5.6 Odstranˇen´ı redundantn´ıch nerovnic . . . . . . . . 5.7 Odstranˇen´ı redundantn´ıch vrchol˚u . . . . . . . . 5.8 Pˇrizp˚usoben´ı pro Octave . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . .

. . . . . . . .

. . . . .

3 3 4 5

. . . . .

6 6 8 9 10 11

. . . . . . . .

12 12 13 14 15 15 16 17 17

. . . . .

18 18 19 20 21 21

. . . . . . . .

. . . . . . . .

. . . . . . . .

23 23 24 24 25 25 26 26 26

6 Programátorská dokumentace 6.1 Pˇrevod z nerovnicové do vrcholové reprezentace . . . . . . . . . . 6.2 Pˇrevod z vrcholové do nerovnicové reprezentace – duáln´ı metoda . 6.3 Pˇrevod z vrcholové do nerovnicové reprezentace – kombinatoricky 6.4 Konvexn´ı sjednocen´ı . . . . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

28 28 29 29 30

1

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

6.5 6.6 6.7 6.8

Pr˚unik . . . . . . . . . . . . . . . Odstranˇen´ı redundantn´ıch nerovnic Odstranˇen´ı redundantn´ıch vrchol˚u Zaokrouhlovac´ı chyby . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

7 Porovnán´ı pouˇzitých algoritmu˚ 7.1 Omezen´ı na vstup . . . . . . . . . . . . . . . 7.2 Implementaˇcn´ı sloˇzitost . . . . . . . . . . . . 7.3 Prostorová nároˇcnost . . . . . . . . . . . . . 7.3.1 Asymptotická prostorová nároˇcnost . 7.3.2 Porovnán´ı na konkrétn´ıch pˇr´ıkladech ˇ 7.4 Casov´ a sloˇzitost . . . . . . . . . . . . . . . . 7.4.1 Asymptotická cˇ asová sloˇzitost . . . . 7.4.2 Porovnán´ı na konkrétn´ıch pˇr´ıkladech 7.5 Shrnut´ı výsledk˚u porovnán´ı . . . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

31 31 31 32

. . . . . . . . .

33 33 33 33 34 34 35 35 36 37

Závˇer

39

Seznam pouˇzité literatury

40

Seznam tabulek

42

Seznam pouˇzitých zkratek

43

2

´ 1. Uvod C´ılem této bakalárˇské práce bylo sestavit knihovnu funkc´ı, která by umˇela pracovat s polyedry v obecné dimenzi. Hned na poˇca´ tku vyvstává otázka, jak polyedry reprezentovat. Existuje v´ıce moˇznost´ı (v´ıce ve tˇret´ı kapitole), ale mezi ty základn´ı jistˇe patˇr´ı popis pomoc´ı nerovnic, které zastupuj´ı poloprostory, jejichˇz pr˚unikem je popisovaný polyedr, nebo popis pouˇz´ıvaj´ıc´ı seznam vrchol˚u, kde polyedr se rovná jejich konvexn´ımu obalu. Dvˇe základn´ı moˇznosti popisu uˇz na zaˇca´ tku implikovaly nutnost nalezen´ı algoritm˚u pro jejich vzájemný pˇrevod. T´ımto problémem se zabýval uˇz Fourier v roce 1824, ale dodnes z˚ustaly nˇekteré otázky otevˇrené. Jde pˇredevˇs´ım o hledán´ı co nejefektivnˇejˇs´ıch algoritm˚u, ale i stanoven´ı hranice, která urˇcuje minimáln´ı moˇznou sloˇzitost. Softwarový bal´ık, který nakonec vznikl, je napsán v MATLABu a s jistými u´ pravami m˚uzˇ e být pouˇzit i pro zdarma dostupný Octave. Kromˇe funkc´ı pro pˇrevod obsahuje i funkce pro konvexn´ı sjednocen´ı, pr˚unik a odstranˇen´ı redundantn´ıch nerovnic nebo vrchol˚u z popisu polyedru. Po seznámen´ı cˇ tenáˇre se základn´ımi pojmy a formáln´ı definic´ı problému se vˇenujeme objasnˇen´ı teorie potˇrebné k popsán´ı pouˇzitých algoritm˚u, pˇriˇcemˇz zmiˇnujeme i jiné algoritmy, které by bylo moˇzné pouˇz´ıt k ˇreˇsen´ı daných u´ loh. Kapitoly cˇ tvrtá a pátá se d˚ukladnˇe vˇenuj´ı popisu softwarového bal´ıku nejdˇr´ıve z uˇzivatelského a poté z programátorského hlediska. Posledn´ı kapitola pak porovnává dva implementované algoritmy pro pˇrevod z vrcholové do nerovnicové reprezentace, a to jak po teoretické stránce, tak i praktickým vyzkouˇsen´ım na nˇekolika pˇr´ıkladech.

1.1 Základn´ı pojmy Polyedry jako takové m˚uzˇ eme definovat dvˇema zp˚usoby: Definice. H-polyedr je pr˚unik koneˇcnˇe mnoha uzavˇrených poloprostor˚u v Rd . H-polytop je omezený H-polyedr. Definice. V-polytop je konvexn´ı obal koneˇcnˇe mnoha bod˚u v Rd . Dále budeme term´ın polyedr vyuˇz´ıvat jako zkratku pro pojem H-polyedr a polytopem budeme oznaˇcovat omezený polyedr. Druhé pojmenován´ı bychom nemohli pouˇz´ıvat bez následuj´ıc´ı vˇety: Vˇeta 1. Kaˇzdý H-polytop je i V-polytop. Kaˇzdý V-polytop je i H-polytop. D˚ukaz. Nejdˇr´ıve ukázˇ eme, zˇ e kaˇzdý H-polytop je i V-polytop. Budeme postupovat indukc´ı pˇres dimenzi. Pro d = 1 je situace triviáln´ı, pokraˇcujme pro d ≥ 2. Necht’ Π je koneˇcná mnoˇzina uzavˇrených poloprostor˚u takových, zˇ e jejich pr˚unik je omezený, neprázdný a tedy pˇredstavuje H-polytop P. Pro ∀π ∈ Π definujme Fπ = P ∩ ∂π jako pr˚unik P a nadroviny urˇcuj´ıc´ı π. Pro kaˇzdé neprázdné Fπ plat´ı, zˇ e má dimenzi nanejvýsˇ d − 1 (nadrovina má dimenzi d − 1, pr˚unik má maximálnˇe stejnou) a je to H-polytop dimenze maximálnˇe d − 1 (jedná se stále o pr˚unik poloprostor˚u, kde nadrovina m˚uzˇ e být chápána jako dvojice opaˇcných poloprostor˚u), tedy z indukˇcn´ıho pˇredpokladu vyplývá, zˇ e je to V-polytop. Oznaˇcme jeho mnoˇzinu bod˚u Vπ . 3

∪ Nyn´ı zbývá dokázat, zˇ e P = conv(V), kde V = π∈Π Vπ . Vezmˇeme nˇejaké x ∈ P a pˇr´ımku l, která j´ım procház´ı. Pak pr˚unik pˇr´ımky a P je u´ seˇcka. Necht’ y a z jsou jej´ı koncové body. Potom existuj´ı Fη a Fζ , zˇ e y ∈ Fη a z ∈ Fζ (kdyby ne, mohli bychom po pˇr´ımce l popoj´ıt o kousek dál a stále být uvnitˇr P). Z toho dostáváme y ∈ conv(Vη ), z ∈ conv(Vζ ), tedy x ∈ conv(Vη ∪ Vζ ) ⊆ conv(V). Opaˇcný smˇer je zaloˇzen na dualitˇe, která je definována aˇz ve tˇret´ı kapitole, proto i tuto cˇ a´ st d˚ukazu je moˇzné nalézt aˇz ve tˇret´ı kapitole. Právˇe tato vˇeta slouˇz´ı jako kl´ıcˇ ová motivace k celé naˇs´ı práci, jej´ızˇ stˇezˇ ejn´ı cˇ a´ st se zabývá hledán´ım vrcholového protˇejˇsku k H-polytopu a vice versa. Dalˇs´ı otázkou, která se nab´ız´ı, je, zda-li je moˇzné nˇejakým zp˚usobem zobecnit pojem V-polytop na V-polyedr, tedy zapsat pomoc´ı vrchol˚u i neomezené polyedry. Rozhodli jsme se toto zobecnˇen´ı popsat tak, zˇ e k mnoˇzinˇe vrchol˚u pˇridáme i mnoˇzinu vektor˚u, ve které kaˇzdý vektor popisuje smˇer jedné neomezené hrany. Pro pˇresnost jeˇstˇe definujme, co pˇresnˇe pro nás znamená stˇena, vrchol, hrana a faceta. Definice. Stˇenou polyedru P v Rd nazýváme bud’ polyedr P samotný, nebo pr˚unik nadroviny h a polyedru P, kde jeden z uzavˇrených poloprostor˚u definovaný nadrovinou h obsahuje celý polyedr. Znaˇcen´ı. Vrcholem nazýváme stˇenu dimenze 0, hranou stˇenu dimenze 1. Fasetou rozum´ıme stˇenu dimenze d − 1. Ridge je stˇena dimenze d − 2. Polyedrem ve vrcholové reprezentaci rozum´ıme popis polyedru pomoc´ı jeho vrchol˚u (tedy V-polytop). Nerovnicovou reprezentaci chápeme jako popis polyedru jako pr˚unik poloprostor˚u (tedy H-polyedr).

1.2 Algoritmické rˇ eˇsen´ı Výsˇe specifikovaný problém dˇel´ıme na dvˇe základn´ı cˇ a´ sti: • Pˇrevod z nerovnicové do vrcholové reprezentace • Pˇrevod z vrcholové do nerovnicové reprezentace K pˇrevodu z nerovnicové do vrcholové reprezentace pouˇz´ıváme algoritmus poprvé publikovaný v roce 1992 v [1]. Výpoˇcetn´ı postup je zaloˇzen na simplexové metodˇe, která se pouˇz´ıvá k ˇreˇsen´ı u´ loh lineárn´ıho programován´ı. Jeho popisu se vˇenuje následuj´ıc´ı kapitola a prvn´ı cˇ a´ st tˇret´ı kapitoly. K pˇrevodu z vrcholové do nerovnicové reprezentace jsme se rozhodli vyzkouˇset dva r˚uzné algoritmy. Prvn´ı vyuˇz´ıvá principu duality a stejného algoritmu jako pˇrevod z nerovnicové do vrcholové reprezentace. Jeho popis je obsaˇzen v druhé cˇ a´ sti tˇret´ı kapitoly. Druhý algoritmus je naopak ryze kombinatorický, konkrétnˇe se jedná o nejjednoduˇssˇ´ı inkrementáln´ı algoritmus. Pˇri jeho implementaci jsme kladli d˚uraz na jednoduchost bez velkých optimalizac´ı, aby se výsledek dobˇre choval i k pomˇernˇe malým a degenerovaným vstup˚um, kde v´ıce neˇz na asymptotické cˇ asové sloˇzitosti záleˇz´ı na velikosti konstanty. Jeho popisu je vˇenována druhá kapitola. Dvoj´ı implementace algoritmu nám dovolila v posledn´ı kapitole porovnat práci obou algoritm˚u a vyhodnotit jejich rychlost, pamˇet’ovou nároˇcnost a implementaˇcn´ı sloˇzitost. 4

1.2.1 Seznam hlavn´ıch funkc´ı Zde pˇredkládáme seznam hlavn´ıch funkc´ı, které m˚uzˇ e pˇr´ıpadný uˇzivatel pouˇz´ıt (seznam neobsahuje pomocné funkce, které jsou volány z hlavn´ıch funkc´ı a které nejsou primárnˇe urˇceny pro pouˇzit´ı uˇzivatelem) • ineqtovertices funkce pro pˇrevod z nerovnicové do vrcholové reprezentace • verticestoineqdual funkce pro pˇrevod z vrcholové do nerovnicové reprezentace, vyuˇz´ıvá geometrickou dualitu a algoritmus pro pˇrevod z nerovnicové do vrcholové reprezentace • verticestoineqcomb funkce pro pˇrevod z vrcholové do nerovnicové reprezentace, vyuˇz´ıvá kombinatorického algoritmu z cˇ tvrté kapitoly • union funkce pro konvexn´ı sjednocen´ı dvou polyedr˚u • intersection funkce pro pr˚unik dvou polyedr˚u • rmineq funkce pro odstranˇen´ı redundantn´ıch nerovnic • rmvertices funkce pro odstranˇen´ı redundantn´ıch vrchol˚u V zadán´ı jsme pˇremýsˇleli jeˇstˇe o implementaci funkce rozd´ılu, ale nakonec jsme se rozhodli tuto cˇ a´ st vynechat, protoˇze zm´ınˇená u´ loha se výraznˇe liˇs´ı od zbylých funkc´ı a to zejména t´ım, zˇ e jej´ım výsledkem nen´ı polyedr.

5

2. Lineárn´ı programován´ı Lineárn´ı programován´ı (dále LP) je jednou z mnoha cˇ a´ st´ı rozsáhlého oboru aplikované matematiky. Vzniklo na základˇe poˇzadavk˚u pˇredevˇs´ım ekonomické praxe, kde se cˇ asto setkáváme s u´ lohami, ve kterých se hledá nejlepˇs´ı ˇreˇsen´ı v rámci prostoru ohraniˇceného r˚uznými omezen´ımi, které lze reprezentovat pomoc´ı lineárn´ıch rovnic nebo nerovnic. V nadcházej´ıc´ıch odstavc´ıch se nebudeme ani tolik zabývat hloubkovou analýzou LP a moˇznostmi ˇreˇsen´ı, ale zamˇeˇr´ıme se pouze na tu cˇ a´ st, kterou v následuj´ıc´ı kapitole aplikujeme na problém pˇrevodu mezi r˚uznými reprezentacemi polyedr˚u.

2.1 Základn´ı pojmy a tvrzen´ı Definice. Obecnou u´ lohou lineárn´ıho programován´ı rozum´ıme min{cT x | A1 x = b1 , A2 x ≥ b2 , A3 x ≤ b3 , x ∈ Rn }

(2.1)

kde c ∈ Rn , Ai ∈ Rmi ×n , bi ∈ Rmi , ∀i. Poznámka. V definici bychom mˇeli jeˇstˇe uvést moˇznost zamˇenit minimalizaci za maximalizaci. Vzhledem k tomu, zˇe v aplikaci pro nás nebude c´ılová funkce d˚uleˇzitá, budeme dále uvaˇzovat pouze u´ lohy minimalizaˇcn´ı.

´ Definice. Ulohou lineárn´ıho programován´ı v rovnicovém tvaru rozum´ıme min{cT x | Ax = b, x ∈ Rn , x ≥ 0}

(2.2)

kde c ∈ Rn , A ∈ Rm×n , rank(A) = m, b ∈ Rm , b ≥ 0, 1 ≤ m < n. Tento tvar u´ lohy nˇekdy nazýváme také standardn´ı, protoˇze právˇe ji na vstupu vyˇzaduje simplexová metoda. Znaˇcen´ı. Mnoˇzinu {x | Ax = b, x ∈ Rn , x ≥ 0} (resp. ≤) budeme nazývat konvexn´ım polyedrem u´ lohy a budeme ho obvykle znaˇcit p´ısmenem M. Uˇz jsme poznamenali, zˇ e budeme cht´ıt v dalˇs´ı cˇ a´ sti pouˇz´ıt simplexový algoritmus. Ten na vstupu vyˇzaduje u´ lohu v rovnicovém tvaru, a proto nyn´ı dokázˇ eme, zˇ e kaˇzdou u´ lohu lze pˇrevést na rovnicový tvar. Pˇrevod rozdˇel´ıme do nˇekolika krok˚u. Zaˇcneme t´ım, zˇ e nerovnice pˇridán´ım promˇenné zmˇen´ıme na rovnice, aniˇz bychom zmˇenili ˇreˇsen´ı. Bez u´ jmy na obecnosti pˇredpokládáme, zˇ e vˇsechny nerovnice jsou ve tvaru ≤ , jinak vynásob´ıme −1. ´ Vˇeta 2. Ulohy min{cT x | Ax ≤ b, x ∈ Rn } min{cT x | Ax + Im x′ = b, x ∈ Rn , x′ ∈ Rm , x′ ≥ 0} jsou co do rˇeˇsitelnosti ekvivalentn´ı. D˚ukaz. Oznaˇcme cT x jako f (x), polyedr z prvn´ı u´ lohy jako M a polyedr z druhé u´ lohy jako M ∗ . Necht’ funkce f (x) dosahuje minima na M v bodˇe x0 . Pak plat´ı n ∑

cα x0α ≤

α=1

n ∑ α=1

6

cα xα

∀x ∈ M. Definujme ′ x0r = br −

pro r = 1, . . . , m, pak zˇrejmˇe plat´ı pro n ∑

cα x0 α + 0

α=1

n ∑

arα x0α

α=1 ′ (x0 , x0 ) ∈

m ∑

x0′ r ≤

M∗

n ∑

cα xα + 0

α=1

r=1

m ∑

x′ r

r=1

∀(x, x′ ) ∈ M ∗ , tedy x0 , x0′ je minimum f (x) na M ∗ . Pro opaˇcný smˇer pouˇzijeme analogické vyjádˇren´ı.

Pokraˇcujeme t´ım, zˇ e kaˇzdou promˇennou, která m˚uzˇ e nabývat záporných hodnot, rozdˇel´ıme na dvˇe nezáporné. Pro snazˇs´ı formulaci pˇredpokládejme, zˇ e takové jsou vˇsechny. ´ Vˇeta 3. Ulohy min{cT x | Ax = b, x ∈ Rn } min{cT (x+ − x− ) | Ax+ − Ax− = b, x+ , x− ∈ Rn , x+ , x− ≥ 0} kde pro i-tou sloˇzku vektoru x plat´ı xi = xi+ − xi− , jsou co do rˇeˇsitelnosti ekvivalentn´ı. D˚ukaz. Nejdˇr´ıve ukázˇ eme, zˇ e minimum druhé u´ lohy odpov´ıdá minimu prvn´ı u´ lohy. Druhý smˇer bychom dokázali analogicky. Oznaˇcme cT (x+ − x− ) jako f ∗ (x+ , x− ), M ∗ polyedr z druhé u´ lohy a minimum f ∗ na M ∗ jako (x0+ , x0− ). Totézˇ pro prvn´ı u´ lohu, ale bez hvˇezdiˇcek. Pro vˇsechna (x+ , x− ) ∈ M ∗ plat´ı, zˇ e n ∑ α=1

cα x0+ α

−

n ∑ α=1

cα x0− α

≤

n ∑

cα x

+

α

−

n ∑

cα x − α

α=1

α=1

a poloˇz´ıme-li x0α = x0+ α − x0− α (α = {1 . . . n}), pak zˇrejmˇe plat´ı, zˇ e x0 ∈ M a n ∑

cα x0α ≤

α=1

n ∑

cα xα

α=1

pro vˇsechna xα = x+ α − x− α , tedy i pro vˇsechna x ∈ M. Z toho vyplývá, zˇ e funkce f dosahuje na M minima v x0 . Z p˚uvodn´ı u´ lohy 2.1 po výsˇe uvedených u´ pravách dostáváme ′

min{cT x | Ax = b, x ∈ Rd , x ≥ 0} kde d′ = 2n + m2 + m3 a Ax = b, A ∈ v následuj´ıc´ım blokovém schématu:   A1 −A1 −A2 A2  A3 −A3

(2.3)

′

Rm×d , b ∈ Rm , m = m1 + m2 + m3 , je vyjádˇreno     0 0   x+   b1      Im2 0   x−  = −b2   ′   0 Im3 x b3

Tento tvar budeme pouˇz´ıvat jako vstup pro simplexovou metodu. Nejdˇr´ıve bychom ale mˇeli jeˇstˇe ovˇeˇrit, zˇ e jsou splnˇeny i zbylé podm´ınky rovnicového tvaru: 7

rank( A) = m Pokud je hodnost matice menˇs´ı, m˚uzˇ eme závislé rovnice vylouˇcit. V praxi vˇsak nen´ı nutné tuto podm´ınku ovˇeˇrovat, inicializace algoritmu ji zajist´ı. b ≥ 0 Pokud podm´ınka nen´ı splnˇena, staˇc´ı pˇr´ısluˇsnou rovnici vynásobit −1. 1 ≤ m < d′ Jediná cˇ a´ st, která by nemusela být splnˇena, je m < d′ : Pokud je m ≥ d′ , tak lze u´ lohu ˇreˇsit jako obyˇcejnou soustavu rovnic, která má bud’ jediné ˇreˇsen´ı, které je t´ım pádem i minimáln´ım, nebo ˇreˇsen´ı nemá zˇ a´ dné. Ani tuto podm´ınku nen´ı nutné v praxi ovˇeˇrovat, inicializace algoritmu ji zajist´ı.

2.2 Simplexová metoda Simplexový algoritmus byl poprvé publikován v roce 1947 matematikem Danzigem. Základn´ı myˇslenka spoˇc´ıvá v tom, interpretovat podm´ınky u´ lohy lineárn´ıho programován´ı jako polyedr. Jak uˇz jsme v u´ vodu ukázali, vrcholy polyedru reprezentuj´ı jeho extrémy, tedy pokud hledáme minimum nebo maximum nˇejaké lineárn´ı funkce, m˚uzˇ eme se spolehnout na to, zˇ e ho najdeme právˇe v nˇekterém vrcholu. Pr˚ubˇeh algoritmu pak spoˇc´ıvá v postupném upravován´ı vstupn´ı matice, kdy v kaˇzdém kroku aktuáln´ı hodnota x odpov´ıdá nˇekterému z vrchol˚u zkoumaného polyedru. Nav´ıc je k matici pˇridán jeden ˇra´ dek nav´ıc, který urˇcuje dalˇs´ı krok algoritmu a jeho konec. Pˇred formulac´ı samotného algoritmu je tˇreba nejdˇr´ıve definovat nˇekolik pojm˚u. Definice. Konvexn´ı polyedr M z (2.3) nazýváme mnoˇzinou pˇr´ıpustných rˇeˇsen´ı u´ lohy min x∈M cT x a kaˇzdý bod x ∈ M pˇr´ıpustným rˇeˇsen´ım stejné u´ lohy. Definice. Bod x0 ∈ M, pro který plat´ı cT x0 ≤ cT x pro vˇsechny body x ∈ M, nazýváme minimáln´ım nebo také optimáln´ım rˇeˇsen´ım u´ lohy (2.3). Definice. Je-li β = {β1 , β2 , . . . , βm } ⊂ {1, . . . , n} indexová podmnoˇzina, pro kterou plat´ı ∑ a) systém rovnic β∈β arβ xβ = br (r = 1, . . . , m) má jednoznaˇcné rˇeˇsen´ı ( x˜β1 , . . . , x˜βm ) b) x˜βi ≥ 0 (i = 1, . . . , m) potom bod x˜ o souˇradnic´ıch ( x˜β1 , . . . , x˜βm , x˜ν1 = . . . = x˜νd′ −m = 0), kde νi ∈ {1, . . . , d′ }\β, nazýváme pˇr´ıpustným bázickým rˇeˇsen´ım u´ lohy (2.3). Nen´ı-li splnˇena podm´ınka b), potom x˜ nazýváme bázickým rˇeˇsen´ım u´ lohy (2.3). Promˇenné xβ1 , . . . , xβm nazýváme bázickými a xν1 , . . . , xνd′ −m nebázickými promˇennými. Nyn´ı m˚uzˇ eme vyslovit vˇetu kl´ıcˇ ovou nejen pro samotný simplexový algoritmus, ale hlavnˇe pro jeho pozdˇejˇs´ı interpretaci v algoritmu pˇrevodu z nerovnicové do vrcholové reprezentace polyedru. Vˇeta 4. Kaˇzdému pˇr´ıpustnému bázickému rˇeˇsen´ı x˜ u´ lohy (2.3) odpov´ıdá jeden vrchol konvexn´ıho polyedru M a kaˇzdému vrcholu M alespoˇn jedno pˇr´ıpustné bázické rˇeˇsen´ı. D˚ukaz. Myˇslenka d˚ukazu v jednom smˇeru spoˇc´ıvá ve speciáln´ım rozˇs´ıˇren´ı matice bázického ˇreˇsen´ı a dokázán´ı toho, zˇ e jej´ı tvar odpov´ıdá tolika vzájemnˇe nerovnobˇezˇ ným nadrovinám, kolik jich je potˇreba k urˇcen´ı bodu (maj´ı pr˚unik dimenze 0). V druhém smˇeru je k vrcholu nalezena odpov´ıdaj´ıc´ı matice a o n´ı je dokázáno, zˇ e jej´ı tvar odpov´ıdá velikosti báze. M˚uzˇ e se stát, zˇ e ji dokonce pˇrevyˇsuje, pak ˇreˇsen´ı nen´ı jednoznaˇcnˇe urˇceno, a proto jsme ve vˇetˇe nemohli pouˇz´ıt vazbu mezi vrcholy a ˇreˇsen´ımi jako jedna ku jedné. 8

Pˇresná formulace d˚ukazu vyˇzaduje mnoho dalˇs´ıch pomocných tvrzen´ı a také hlubˇs´ı studium polyedru urˇceného lineárn´ı u´ lohou, a proto ho zde pomineme a na pˇresné znˇen´ı odkazujeme na [8, str. 34 – 35]. Nyn´ı uˇz m˚uzˇ eme v bodech vyjádˇrit postup simplexového algoritmu. 1. Sestaven´ı simplexové tabulky a nalezen´ı výchoz´ıho pˇr´ıpustného bázického ˇreˇsen´ı. 2. Proveden´ı bˇezˇ ného kroku (pˇrechod od jedné báze k jiné). 3. Vyhodnocen´ı výsledku po posledn´ım kroku a pˇr´ıp. konec. V následuj´ıc´ıch cˇ a´ stech rozebereme jednotlivé kroky.

2.2.1 Výchoz´ı pˇr´ıpustné bázické rˇ eˇsen´ı Pro u´ lohu (2.3) mohou nastat dvˇe moˇznosti. Bud’ je výchoz´ı pˇr´ıpustné bázické ˇreˇsen´ı zˇrejmé, nebo je potˇreba nejdˇr´ıve ˇreˇsit pomocnou, tzv. umˇelou u´ lohu, jej´ımˇz výsledkem bude výchoz´ı pˇr´ıpustné bázické ˇreˇsen´ı p˚uvodn´ı u´ lohy. Prvn´ı pˇr´ıpad nastává, pokud matice A obsahuje jednotkovou submatici ˇra´ du m × m. Potom bázickým promˇenným odpov´ıdaj´ı jednotkové sloupce a tyto promˇenné poloˇz´ıme rovny br (r = 1, . . . , m), kde r odpov´ıdá souˇradnici s jedniˇckou. Ostatn´ı (nebázické) promˇenné poloˇz´ıme rovny 0. D´ıky tomu, zˇ e br ≥ 0, tak je podm´ınka nezápornosti ˇreˇsen´ı splnˇena a stejnˇe tak i vˇsechny ostatn´ı. Druhý pˇr´ıklad se na prvn´ı pohled jev´ı o nˇeco komplikovanˇejˇs´ı. C´ılem je opˇet upravit soustavu rovnic tak, aby se vlevo nacházela jednotková submatice. Kdyby se vˇsak cˇ lovˇek pokusil pouˇz´ıt pˇr´ımo napˇr´ıklad Gaussovu eliminaci, mohlo by se stát, zˇ e mu pravé strany nevyjdou nezáporné. Proto se bˇezˇ nˇe postupuje tak, zˇ e se zavede pomocná tzv. umˇelá u´ loha LP, která vydá výchoz´ı pˇr´ıpustné bazické ˇreˇsen´ı automaticky. Definice. Umˇelou u´ lohou k u´ loze (2.3) formulujeme jako ′

min{1T u | Ax + Im u = b, x ∈ Rd , u ∈ Rm , x, u ≥ 0}

(2.4)

Vˇsimnˇeme si, zˇ e tato u´ loha splˇnuje vˇsechny potˇrebné poˇca´ teˇcn´ı podm´ınky pro simplexovou metodu a nav´ıc jej´ı výchoz´ı pˇr´ıpustné ˇreˇsen´ı je zˇrejmé (promˇenné u vol´ıme jako bázické, ostatn´ı jako nebázické). Tato u´ loha je ovˇsem jiná neˇz p˚uvodnˇe zadaná u´ loha, a proto mus´ıme jeˇstˇe objasnit vztah mezi ˇreˇsen´ımi umˇelé a p˚uvodn´ı u´ lohy. Znaˇcen´ı. V následuj´ıc´ı cˇ a´ sti budeme polyedr z pomocné u´ lohy oznaˇcovat jako M ∗ . Vˇeta 5. Existuje-li minimáln´ı rˇeˇsen´ı (2.4) (x0 , u0 ), pro nˇezˇ plat´ı 1T u > 0, pak je konvexn´ı polyedr M z p˚uvodn´ı u´ lohy prázdný a p˚uvodn´ı u´ loha tedy nemá rˇeˇsen´ı. D˚ukaz. Bod (x0 , u0 ) ∈ M ∗ splˇnuje vztah d′ ∑ α=1

cα x0α +

m ∑

u0r ≤

d′ ∑ α=1

r=1

cα xα +

m ∑

ur

r=1

pro vˇsechna (x, u) ∈ M ∗ . Pro spor nyn´ı pˇredpokládejme, zˇ e M , ∅. Potom pro libovolné x∗ ∈ M je (x∗ , O) ∈ ∗ M , tedy m˚uzˇ eme zvolit ur = O, ale pak docház´ı ke sporu s minimalitou 1T u > 0. 9

Vˇeta 6. Existuje-li minimáln´ı rˇeˇsen´ı (2.4) (x0 , u0 ), pro nˇezˇ plat´ı 1T u = 0, pak je x0 pˇr´ıpustným bázickým rˇeˇsen´ım p˚uvodn´ı u´ lohy nebo ho lze snadno odvodit. D˚ukaz. Vezmˇeme (x0 , u0 ) = (x0 , O) ∈ M ∗ jako minimáln´ı rˇeˇsen´ı umˇelé u´ lohy. Protoˇze u ≥ 0 mus´ı platit u0 = O, pak jsou u mimo bázi a nebo je z n´ı m˚uzˇ eme vylouˇcit pomoc´ı zámˇeny s odpov´ıdaj´ıc´ı nebázickou promˇennou. Po této u´ pravˇe z´ıskáváme výchoz´ı bázické ˇreˇsen´ı.

2.2.2 Bˇezˇ ný krok algoritmu Necht’ máme nˇejaké x0 jako výchoz´ı pˇr´ıpustné bázické ˇreˇsen´ı a k nˇemu odpov´ıdaj´ıc´ı matici A′ , kterou oznaˇcujeme jako aktuáln´ı simplexovou tabulku. Podle vˇety 4 v´ıme, zˇ e toto ˇreˇsen´ı odpov´ıdá nˇekterému vrcholu konvexn´ıho polyedru M. V bˇezˇ ném kroku simplexové metody hledáme hranu vycházej´ıc´ı z tohoto vrcholu, podél které c´ılová funkce neroste nebo, lépe, klesá. Vzhledem k tomu, zˇ e v algoritmu na pˇrevod z nerovnicové do vrcholové reprezentace polyedru nebudeme potˇrebovat c´ılovou funkci, budeme se v následuj´ıc´ıch odstavc´ıch zabývat pouze t´ım, jak se dostat do libovolného dalˇs´ıho vrcholu bez ohledu na c´ılovou funkci. Jedinou moˇznost´ı, jak zmˇenit aktuálnˇe dosaˇzené ˇreˇsen´ı na jiné, je zmˇenit bázi, resp. prohodit nˇekterou bázickou promˇennou za nebázickou. Následuj´ıc´ı vˇeta popisuje, jaké dvojice pˇripadaj´ı v u´ vahu, aby nové ˇreˇsen´ı bylo opˇet pˇr´ıpustné. Vˇeta 7. Vstupuj´ıc´ı promˇennou se m˚uzˇe stát kterákoli nebázická promˇenná, které odpov´ıdá sloupec A′ tak, zˇe v tomto sloupci existuje kladný cˇ len. D˚ukaz. V daném sloupci existuje kladný cˇ len, tedy následuj´ıc´ı mnoˇzina pro výbˇer minima je neprázdná, a minimum tedy existuje. Poznámka. Sloupce, které jsou celé nekladné, mohou reprezentovat neomezené hrany. Podrobnˇeji se této otázce vˇenuje vˇeta 10. Vˇeta 8. Vystupuj´ıc´ı promˇennou pro danou vstupuj´ıc´ı promˇennou s indexem j je ta odpov´ıdaj´ıc´ı sloupci i-tého jednotkového vektoru, kde i ∈ arg min{

bk , k ∈ {1, . . . , m}, akr > 0} akr

Pokud nen´ı minimum urˇceno jednoznaˇcnˇe, lze vybrat libovolné z nich. D˚ukaz. Nyn´ı mus´ıme ovˇeˇrit, zˇ e po u´ pravˇe tabulky bude ˇreˇsen´ı pˇr´ıpustné. Bázické je urˇcitˇe, protoˇze nemˇen´ıme poˇcet bázických promˇenných. Pro spor pˇredpokládejme, zˇ e výsledné ˇreˇsen´ı x∗ nen´ı pˇr´ıpustné, tedy ∃r ∈ {1 . . . m} tak, zˇ e b∗r < 0. To by znamenalo, zˇ e br − ale to by byl spor s minimalitou pomˇeru

bi ar j < 0 ai j bi . ai j

Poznámka. Pokud nastane nejednoznaˇcnost ve výbˇeru vystupuj´ıc´ı promˇenné, znamená to, zˇe následuj´ıc´ı rˇeˇsen´ı bude tzv. degenerované. V bˇezˇné simplexové metodˇe tato situace m˚uzˇe zp˚usobit problémy, ale v naˇsem pˇr´ıpadˇe se j´ı nemus´ıme zabývat, protoˇze náhodný výbˇer nem˚uzˇe zp˚usobit, zˇe bychom nˇekterý vrchol zcela pˇreskoˇcili (je vidˇet, zˇe vˇzdy existuje nˇekterý sousedn´ı vrchol, ze kterého je cesta urˇcena jednoznaˇcnˇe). 10

2.2.3 Vyhodnocen´ı posledn´ıho kroku Jak uˇz jsme výsˇe poznamenali, situace, kdy konˇc´ı tradiˇcn´ı simplexový algoritmus, pro nás nen´ı urˇcuj´ıc´ı, protoˇze my nehledáme vrchol minimáln´ı podle c´ılové funkce, ale hledáme vrcholy vˇsechny. Na tomto m´ıstˇe proto vyslov´ıme pouze vˇetu o tom, zˇ e vrchol˚u polyedru je vˇzdy pouze koneˇcnˇe mnoho, a zˇ e tedy násˇ algoritmus, popsaný v následuj´ıc´ı kapitole, po koneˇcnˇe mnoha kroc´ıch skonˇc´ı. Vˇeta 9. Kaˇzdý konvexn´ı polyedr urˇcený koneˇcným poˇctem rovnic má pouze koneˇcný poˇcet vrchol˚u. D˚ukaz. Podle vˇety 4 v´ıme, zˇ e kaˇzdému vrcholu odpov´ıdá nˇekteré bázické ˇreˇsen´ı. Bázických ˇreˇsen´ı je maximálnˇ (d′e) tolik, kolika zp˚usoby lze vybrat promˇenné do báze (a nezáleˇz´ı na poˇrad´ı), tedy m .

11

3. Pouˇzité algoritmy vyuˇz´ıvaj´ıc´ı simplexovou metodu 3.1 Algoritmus pro pˇrevod z nerovnicové do vrcholové reprezentace Uˇz v pˇredcházej´ıc´ıch odstavc´ıch byl naznaˇcen pr˚ubˇeh algoritmu. V této cˇ a´ sti se proto zamˇeˇr´ıme pˇredevˇs´ım na to, jak z´ıskat výsledné ˇreˇsen´ı a také jak oˇsetˇrit pˇr´ıpadnou pˇr´ıtomnost neomezených hran. V základn´ı ideji algoritmu jsme se inspirovali cˇ lánkem [1]. Na tomto m´ıstˇe bychom rádi pˇripomnˇeli i dalˇs´ı autory, kteˇr´ı se zabývali stejným problémem, napˇr´ıklad prof. Noˇziˇcku a jeho algoritmus popsaný v knize [12] nebo Chvátal˚uv algoritmus z [9]. Nejdˇr´ıve zformulujeme pˇresnˇe pr˚ubˇeh algoritmu. Postupujeme od výchoz´ıho vrcholu po hranách prohledáván´ım do sˇ´ıˇrky, pˇriˇcemˇz u kaˇzdé poloˇzky ovˇeˇrujeme jak pˇr´ıtomnost báze mezi uˇz nalezenými bázemi, tak i pˇr´ıtomnost vrcholu ve výsledku. Pouˇzitý pseudokód se drˇz´ı syntaxe bl´ızké MATLABu. %VSTUP: Pole Rovnic(Eq) a Nerovnic(Ineq) %inicializace %fronta obsahuje simplexovou tabulku s poˇ c´ ateˇ cn´ ım ˇ reˇ sen´ ım queue = inicialize(Ineq, Eq); FoundBasis = []; FoundVertices = []; EndlessEdges = []; %tˇ elo algoritmu %v kaˇ zd´ em cyklu se zpracuje prvn´ ı vrchol fronty while ˜isEmpty(queue) [actual queue] = pop(queue); %v kaˇ zd´ em sloupeˇ cku se pokus´ ı nal´ ezt pivota for i = 1:columns(actual.matice) pivot = findPivot(actual.matice(:,i),actual.b); %pokud byl pivot nalezen, tabulka se podle nˇ ej uprav´ ı if definied(pivot) new = simplexOneStep(pivot, actual); %pokud novˇ e upraven´ a tabulka jeˇ stˇ e nebyla nalezena dˇ r´ ıve, %je zaˇ razena do prohled´ avac´ ı fronty if ˜in(new.basis,FoundBasis) Basis = add(new.basis, FoundBasis); queue = add(new, queue);

12

%pokud z´ aroveˇ n ˇ reˇ sen´ ı odpov´ ıd´ a dosud nenalezen´ emu vrcholu, %je nov´ y vrchol zaˇ razen do v´ ysledku if ˜in(new.vertex,FoundVertices) FoundVertices = add(new.vertex,FoundVertices); end %if end %if %pokud pivot nebyl nalezen, tak je sloupeˇ cek cel´ y nekladn´ y, %m˚ uˇ ze mu odpov´ ıdat nekoneˇ cn´ a hrana else %pokud mu nekoneˇ cn´ a hrana odpov´ ıd´ a, %je zaˇ razena do v´ ysledku if isEndlessEdge(actual,i) endlessEdge = computeEndlessEdge; if ˜in(endlessEdge,EndlessEdges) EndlessEdges = add(endlessEdge,EndlessEdges); end %if end %if end %if end %for end %while %V´ YSTUP: Vrcholy(FoundVertices) a Neomezen´ e hrany(EndlessEdges) %v´ ystup je na n´ asobnost oˇ setˇ ren v pr˚ ubˇ ehu algoritmu

3.1.1 Analýza algoritmu Z uvedeného kódu je jasná správnost algoritmu, a to d´ıky tomu, zˇ e mezi kaˇzdými dvˇema vrcholy existuje cesta po hranách a tato cesta je nalezena prohledáván´ım z jednoho vrcholu po hranách. Ve vˇetˇe 9 jsme zároveˇn vyslovili i podm´ınku pro koneˇcnost algoritmu, protoˇze v kaˇzdém cyklu zpracuje algoritmus jednu z moˇzných báz´ı a tˇech je pouze koneˇcnˇe mnoho. Co se týká cˇ asové sloˇzitosti, ta asymptoticky odpov´ıdá sloˇzitosti simplexové metody, protoˇze i pˇri té se teoreticky m˚uzˇ e stát, zˇ e k nalezen´ı optimáln´ıho ˇreˇsen´ı je tˇreba proj´ıt vˇsechny vrcholy. Nav´ıc je nutné ji jeˇstˇe vynásobit nároˇcnost´ı prohledáván´ı v kaˇzdém kroku pˇri ovˇeˇrován´ı, jestli uˇz nebyl nový vrchol nalezen dˇr´ıve. Tento koeficient závis´ı na pouˇzitých vyhledávac´ıch strukturách, ale vˇzdy se do nˇej prom´ıtne hlavnˇe poˇcet nebo struktura pˇr´ıpustných báz´ı, které je nutné prohledat. O cˇ asové sloˇzitosti naˇs´ı konkrétn´ı implementace se hovoˇr´ı v kapitole 7. Prostorová nároˇcnost je v tomto pˇr´ıpadˇe vyˇssˇ´ı neˇz v [1], protoˇze zat´ımco v cˇ lánkem popsaném algoritmu postupuj´ı od minimáln´ıho ˇreˇsen´ı prohledáván´ım do hloubky smˇerem po maximalizaci p˚uvodnˇe minimalizované funkce, v naˇsem algoritmu prob´ıhá prohledáván´ı do sˇ´ıˇrky pˇres vˇsechny vrcholy, a je tedy nutné pamatovat si i vˇsechny dosud nalezené báze, nikoliv pouze nalezené vrcholy (pˇr´ıpustných báz´ı pak m˚uzˇ e být i výraznˇe v´ıce, neˇz kolik je výsledných vrchol˚u). Konkrétn´ı prostorová nároˇcnost pak závis´ı pˇredevˇs´ım na pouˇzitých datových strukturách, pˇriˇcemˇz pro naˇsi implementaci se 13

o n´ı hovoˇr´ı v kapitole 7. V celkovém porovnán´ı s [1] sice m˚uzˇ e na prvn´ı pohled násˇ algoritmus vycházet h˚uˇre, ale na druhou stranu tu odpadaj´ı problémy s pˇr´ıpadnými degenerovanými vrcholy (takové, kde i bázická promˇenná je rovna 0) a také jasnˇe popisuje, jak se vyrovnat s neomezenými hranami. O tomto problému pojednává následuj´ıc´ı cˇ a´ st.

3.1.2 Neomezené hrany V simplexové metodˇe jsou zkoumány pouze ty neomezené hrany, po kterých neomezenˇe klesá c´ılová funkce. Tato situace nastává tehdy, kdy je pivotovac´ım pravidlem zvolen jeden sloupec odpov´ıdaj´ıc´ı vstupuj´ıc´ı promˇenné, ale v tomto sloupeˇcku uˇz nen´ı jediná kladná hodnota. Vzhledem k tomu, zˇ e v naˇsem algoritmu nepracujeme s c´ılovou funkc´ı, je tˇreba provˇeˇrit vˇsechny nekladné sloupeˇcky. Avˇsak ne kaˇzdý nekladný sloupeˇcek odpov´ıdá nˇejaké neomezené hranˇe. Je nutné si uvˇedomit, zˇ e oproti p˚uvodn´ımu zadán´ı nám kv˚uli u´ pravˇe u´ lohy pro simplexovou metodu pˇribylo mnoho promˇenných. Problém nastává pˇredevˇs´ım s promˇennými, které byly pˇridány kv˚uli podm´ınce nezápornosti. Vzhledem k tomu, zˇ e dvojice xi+ , xi− pˇred sebou maj´ı vˇzdy jen o znaménko jiné koeficienty, je jasné, zˇ e pokud je jedna z dvojice v bázi, tedy jej´ı odpov´ıdaj´ıc´ı sloupeˇcek je jednotkový, tak druhá z dvojice má sloupeˇcek sloˇzený ze samých 0 a jedné −1. Následuj´ıc´ı vˇeta formuluje pˇresnˇe podm´ınku nutnou a postaˇcuj´ıc´ı pro nalezen´ı neomezené hrany Vˇeta 10. Právˇe kaˇzdý nekladný sloupeˇcek matice A′ , který se vyskytne v pr˚ubˇehu algoritmu a který neodpov´ıdá promˇenné xi+ (resp. x− ) tak, zˇe xi− (resp. x+ ) je v bázi, definuje nˇejakou neomezenou hranu. Poznámka. Zd˚uraznˇeme jeˇstˇe, zˇe hranˇe m˚uzˇe odpov´ıdat v´ıce nekladných sloupeˇck˚u, stejnˇe jako vrchol˚um m˚uzˇe odpov´ıdat v´ıce báz´ı. Dále je dobré upozornit, zˇe nalezen´ı neomezené hrany v urˇcitém vrcholu nemus´ı nutnˇe znamenat, zˇe hrana vycház´ı z nˇej, resp. nalezený vrchol se pak m˚uzˇe ukázat, zˇe nen´ı vrcholem p˚uvodn´ıho polyedru, ale pouze vrcholem polyedru definovaným upravenou u´ lohou. D˚ukaz. V pˇredchoz´ı kapitole jsme pˇri formulaci simplexového algoritmu ukázali, zˇ e pokud existuje v nˇejakém sloupeˇcku aspoˇn jedna kladná hodnota, vycház´ı z vrcholu daného ˇreˇsen´ım hrana, která vede do jiného vrcholu odpov´ıdaj´ıc´ımu dalˇs´ımu ˇreˇsen´ı. Pro definici neomezené hrany tak pˇripadaj´ı v u´ vahu pouze nekladné sloupce. Staˇc´ı tedy ukázat, zˇ e nekladné sloupce definuj´ı neomezené hrany a zˇ e sloupce z podm´ınky vˇety nikoliv. Necht’ A′∗s ≤ 0. Je jasné, zˇ e s nen´ı z báze, a proto m˚uzˇ eme definovat zβ = −A′∗s , z s = 1, z j = 0 jinak Vid´ıme, zˇ e z ≥ 0 a proto m˚uzˇ eme vyjádˇrit Az = Aβ zβ + A∗s = −Aβ (A−1 β A)∗s + A∗s = −A∗s + A∗s = 0 Vezmˇeme polopˇr´ımku x + zα, α ∈ R, α ≥ 0, kde x je nˇejaké pˇr´ıpustné bázické ˇreˇsen´ı. Protoˇze A(x + zα) = Ax = b 14

je kaˇzdý bod definované polopˇr´ımky pˇr´ıpustným ˇreˇsen´ım, tedy polopˇr´ımka je obsaˇzena v polyedru M. To, zˇ e polopˇr´ımka urˇcuje hranu, bychom dokázali obdobnˇe, jako zˇ e pˇr´ıpustné bázické ˇreˇsen´ı urˇcuje vrchol. Nyn´ı se pod´ıvejme na sloupce z podm´ınky ve vˇetˇe. Uvˇedomme si, zˇ e formulace polopˇr´ımky je v dimenzi d′ , ale násˇ p˚uvodn´ı polyedr je v dimenzi n. Po pˇrevodu do p˚uvodn´ı dimenze by se vektor z vynuloval (A∗s = −ek ), proto sloupce z podm´ınky neurˇcuj´ı neomezenou hranu. Poznámka. Z d˚ukazu vyplývá, jak konstruovat neomezené hrany, které tedy urˇcuje vektor z pˇrevedený do p˚uvodn´ı dimenze.

3.2 Algoritmus pro pˇrevod z vrcholové do nerovnicové reprezentace 3.2.1 Dualita Dualita je speciáln´ım geometrickým zobrazen´ım, které bodu pˇriˇrazuje nadrovinu a vice versa. T´ımto zp˚usobem je tedy moˇzné z vrchol˚u polyedru odvodit, jak vypadá jeho duáln´ı obraz, s t´ım rozd´ılem, zˇ e jeho popis dostaneme v nerovnicové reprezentaci. To se nám ovˇsem hod´ı, protoˇze pak na duáln´ı obraz m˚uzˇ eme pouˇz´ıt algoritmus z pˇredcházej´ıc´ı cˇ a´ sti a z jeho výsledku opˇet pˇres dualitu odvodit, jak vypadá nerovnicová reprezentace p˚uvodn´ıho polyedru. Na okraj poznamenejme, zˇ e námi pouˇzitá dualita je jednou z mnoha, kterou lze definovat, ale pro naˇse potˇreby je tato nejznámˇejˇs´ı forma zcela dostaˇcuj´ıc´ı. Definice. Duáln´ı obraz bodu a ∈ Rd \ {0} je pˇriˇrazen zobrazen´ım oznaˇceným D a definovaným pˇredpisem D(a) = {x ∈ Rd | ⟨a, x⟩ = 1} a analogicky nadrovinˇe h, která neprocház´ı poˇca´ tkem a m˚uzˇe být jednoznaˇcnˇe popsána jako h = {x ∈ Rd | ⟨a, x⟩ = 1} je pˇriˇrazen D(h) = a ∈ Rd . Podobnˇe m˚uzˇ eme definovat i duáln´ı obraz k nˇejaké podmnoˇzinˇe Rd . Definice. Duáln´ı obraz mnoˇziny X ⊆ Rd definujeme jako X ∗ = {y ∈ Rd | ⟨x, y⟩ ≤ 1, x ∈ X}. Nyn´ı vyslov´ıme vˇetu o tom, zˇ e duáln´ı obraz duáln´ı mnoˇziny je mnoˇzina primárn´ı za urˇcitých pˇredpoklad˚u. D´ıky tomu m˚uzˇ eme pouˇz´ıt výsˇe naznaˇcený algoritmus pro pˇrevod z vrcholové do nerovnicové reprezentace polyedru. Vˇeta 11. Necht’ X ⊆ Rd uzavˇrená, konvexn´ı a {0} ∈ X. Pak plat´ı, zˇe (X ∗ )∗ = X. Pˇred uveden´ım d˚ukazu mus´ıme jeˇstˇe vyslovit tzv. oddˇelovac´ı vˇetu (separation theorem), kterou budeme cht´ıt pouˇz´ıt. Ovˇeˇrit, zˇ e tato vˇeta plat´ı, nen´ı jednoduché, ale ani pro nás d˚uleˇzité, proto pouze odkazujeme napˇr´ıklad na d˚ukaz uvedený v [10, Mat02, str. 6]. Vˇeta 12. Necht’ C, D ⊂ Rd jsou konvexn´ı mnoˇziny, které se neprot´ınaj´ı. Pak ∃v ∈ Rd a b ∈ R tak, zˇe ∀c ∈ C plat´ı ⟨c, v⟩ ≤ b a ∀d ∈ D plat´ı ⟨d, v⟩ ≥ b. Pokud jsou nav´ıc mnoˇziny uzavˇrené a aspoˇn jedna omezená, pak plat´ı nerovnosti ostˇre. 15

D˚ukaz. Vˇetu 11 dokazujeme pomoc´ı inkluze. Smˇer X ⊆ (X ∗ )∗ je jasný z definice duáln´ı mnoˇziny, proto se podrobnˇeji pod´ıváme pouze na druhý smˇer. Pro spor pˇredpokládejme, zˇ e ∃x ∈ X, ale x < (X ∗ )∗ . Z definice vyplývá, zˇ e (X ∗ )∗ je uzavˇrená, proto podle oddˇelovac´ı vˇety existuje vektor v normovaný tak, zˇ e ∀y ∈ (X ∗ )∗ plat´ı ⟨v, y⟩ < 1 a ⟨v, x⟩ > 1 (protoˇze (X ∗ )∗ obsahuje poˇca´ tek). Z toho vyplývá, zˇ e v ∈ X ∗ , ale protoˇze v ∈ X, mus´ı tedy ⟨h, v⟩ ≤ 1, a to je spor. V této chv´ıli uˇz máme vˇsechny teoretické podklady pro to zformulovat algoritmus. Jeˇstˇe pˇred t´ım se vˇsak na tomto m´ıstˇe vrát´ıme k d˚ukazu vˇety z u´ vodu o ekvivalenci reprezentace polytop˚u. D˚ukaz. Vˇety 1. Nyn´ı dokázˇ eme, zˇ e kaˇzdý V-polytop je také H-polytopem. Mˇejme P = conv(V), kde V je koneˇcná mnoˇzina vrchol˚u a nav´ıc bez u´ jmy na obec∩ nosti P obsahuje poˇca´ tek. Nejdˇr´ıve dokázˇ eme pomocné lemma, zˇ e P∗ = v∈V D(v)− , tedy pr˚unikem poloprostor˚u urˇcených duáln´ımi nadrovinami k vrchol˚um a obsahuj´ıc´ıch poˇca´ tek. Pr˚unik zkrácenˇe oznaˇc´ıme jako D. Je vidˇet, zˇ e P∗ ⊂ D. Ve druhém smˇeru pro spor pˇredpokládejme, zˇ e existuje w ∈ P∗ = conv(V)∗ , ale w < D. Tedy ∃v ∈ V tak, zˇ e w < D(v)− . To by znamenalo, zˇ e ⟨v, w⟩ > 1, ale to by byl spor s t´ım, zˇ e w ∈ P∗ . Vrat’me se k hlavn´ımu d˚ukazu. Protoˇze P obsahuje poˇca´ tek, tak jeho duáln´ı obraz je omezený, a jak jsme dokázali pˇredchoz´ım lemmatem, je to pr˚unik poloprostor˚u. Uˇz máme dokázáno, zˇ e pro kaˇzdý omezený pr˚unik poloprostor˚u existuje jeho vrcholová reprezentace. Na tuto reprezentaci opˇet aplikujeme dualitu a opˇet d´ıky tomu, zˇ e P obsahuje poˇca´ tek, a vˇetˇe 11 dostáváme p˚uvodn´ı polyedr v nerovnicové reprezentaci.

3.2.2 Popis algoritmu Jak jiˇz bylo napsáno výsˇe, idea algoritmu pracuje s t´ım, zˇ e na základˇe zadaných vrchol˚u je vypoˇc´ıtán duáln´ı obraz polyedru, který je popsán nerovnicovou reprezentac´ı. D´ıky tomu je moˇzné na nˇej pouˇz´ıt algoritmu z cˇ a´ sti (3.1). Z výsledku jsou pak opˇet pˇres dualitu odvozeny nerovnice popisuj´ıc´ı fasety p˚uvodn´ıho polyedru. Tento posledn´ı krok bychom nemohli uˇcinit, pokud by neplatila vˇeta 11. Abychom ji vˇsak v˚ubec mohli pouˇz´ıt, mus´ıme posunout souˇradnou soustavu tak, aby se poˇca´ tek nacházel uvnitˇr polyerdu v´ıce viz 3.2.4. Podm´ınka uzavˇrenosti je pro libovolný polyedr splnˇena automaticky. Pro popsán´ı algoritmu opˇet zvol´ıme formu pseudokódu, který se drˇz´ı syntaxe MATLABu. %VSTUP: Vrcholy(Vertices) dim = columns(Vertices); ´tku %v´ ypoˇ cet a posunut´ ı poˇ ca newOrigin = middle(Vertices); Vertices = moveOrigin(newOrigin,Vertices); %vytvoˇ ren´ ı du´ aln´ ıho obrazu Dual = []; 16

for i =1:rows(Vertices) Dual = add(dual(Vertices(i,:)),Dual); end %for %pouˇ z´ ıt´ ı algoritmu z (2.3) DualResult = facetsVerticesTransformation(Dual); %pˇ revod zpˇ et na prim´ arn´ ı polyedr for i = 1:rows(DualResult) Inequalities = add(dual(DualResult(i,:)),Inequalities); end %for %posun v´ ysledn´ ych nerovnic do p˚ uvodn´ ıch souˇ radnic for i = 1:rows(Inequalities) Inequalities(i,:) = moveoriginineq(Inequalities(i,:),-neworigin); end %for %V´ YSTUP: Nerovnice(Inequalities)

3.2.3 Analýza algoritmu Algoritmus je zcela jistˇe koneˇcný, protoˇze jeho vstup je koneˇcný a koneˇcnost pouˇzitého algoritmu pro pˇrevod z nerovnicové do vrcholové reprezentace byla dokázána v jedné z pˇredcházej´ıc´ıch cˇ a´ st´ı. Správnost algoritmu je zajiˇstˇena vˇetou 11 a t´ım, zˇ e je v celém algoritmu pouˇzita pˇr´ımá dualita. Jediný problém by mohl nastat, pokud nˇekterá ze stˇen procházela poˇca´ tkem. Tomuto problému se podrobnˇeji vˇenuje následuj´ıc´ı cˇ a´ st. ˇ Casov´ a sloˇzitost je závislá na sloˇzitosti pomocného algoritmu. Vˇsechny ostatn´ı operace, pˇredevˇs´ım tedy pˇrevádˇen´ı duálu a posouván´ı poˇca´ tku jsou lineárnˇe závislé na vstupu. Prostorová sloˇzitost opˇet odpov´ıdá pomocnému algoritmu, bˇehem pˇrevodu nejsou kladeny dalˇs´ı nároky na pamˇet’.

3.2.4 Fasety procházej´ıc´ı poˇca´ tkem Problém v algoritmu by mohl nastat ve chv´ıli, kdy by v p˚uvodn´ım polyedru nˇekteré nadroviny urˇcuj´ıc´ı r˚uzné fasety procházely posunutým poˇca´ tkem. Takové fasety totiˇz nemaj´ı definován duáln´ı obraz, takˇze by je nebylo moˇzné jednoznaˇcnˇe dostat jako duáln´ı obraz vypoˇctených vrchol˚u. Mus´ıme se tud´ızˇ této situaci vyhnout, cˇ ehoˇz lze dosáhnout vhodným posunut´ım poˇca´ tku. V naˇsem pˇr´ıpadˇe jsme vzali vˇsechny zadané vrcholy polyedru a pomoc´ı následuj´ıc´ıho vztahu jsme urˇcili stˇred: ∑n ∑n (an )i i=1 (a1 )i ; . . . ; i=1 ] (3.1) S =[ n n Takto definovaný stˇred je jistˇe v polyedru obsaˇzen (je konvexn´ı kombinac´ı vˇsech vrchol˚u). Vzhledem k nezávislosti volených vrchol˚u, kterou jsme ovˇeˇrili na poˇca´ tku algoritmu, tento vrchol nem˚uzˇ e leˇzet v zˇ a´ dné stˇenˇe. 17

4. Konvexn´ı obal kombinatoricky v obecné dimenzi Problém pˇrevodu z vrcholové na nerovnicovou reprezentaci polyedru je podmnoˇzinou rozsáhlého problému shrnutého do pojmu konvexn´ıho obalu. Zat´ımco samotný pˇrevod by mohl být chápán tak, zˇ e jsou zadány pouze skuteˇcné vrcholy, v u´ plné obecnosti lze samozˇrejmˇe zadat libovolné body a teprve v pr˚ubˇehu výpoˇctu se ukázˇ e, jestli jsou vˇsechny opravdu vrcholy výsledného polytopu. V této kapitole se budeme vˇenovat nejdˇr´ıve obecnˇe konvexn´ımu obalu, r˚uzných moˇznostech jeho výpoˇctu. Omez´ıme se vˇsak pouze na algoritmy vhodné pro aplikaci v obecné dimenzi a budeme uvaˇzovat pouze polytopy dimenze d v Rd . Neˇz pˇredstav´ıme jednotlivé pˇr´ıstupy, mˇeli bychom jeˇstˇe pˇresnˇe specifikovat, co vlastnˇe m˚uzˇ e být výsledkem výpoˇctu. Jedná se o r˚uzné moˇznosti, jak popsat polyedr. Vrcholová reprezentace: Mnoˇzina vˇsech vrchol˚u (bez redudance) Nerovnicová reprezentace: Mnoˇzina vˇsech faset popsaných lineárn´ımi nerovnicemi (bez redudance) Dvojitá reprezentace: Mnoˇzina vˇsech vrchol˚u a vˇsech faset vˇcetnˇe vzájemné incidence (popsána zpravidla matic´ı incidence) Svazová reprezentace: Svaz vˇsech stˇen popsaný Hasseovým diagramem (angl. Lattice description) Hraniˇcn´ı reprezentace: Triangulace povrchu (sloˇzená z d − 1-dimenzionáln´ıch simplex˚u a nerovnic popisuj´ıc´ıch jejich polohu) R˚uzné popisy jsou vhodné pro r˚uzné dalˇs´ı problémy a pouˇzit´ı. Prvn´ı dva patˇr´ı do skupiny cˇ istˇe geometrických popis˚u, protoˇze definuj´ı objekt ve smyslu geometrické nezbytnosti, zat´ımco druhé tˇri patˇr´ı mezi tzv. kombinatorické popisy, protoˇze sice definuj´ı objekt jako takový, ale nav´ıc poskytuj´ı dodateˇcnou informaci o jeho kombinatorické sloˇzitosti. Kromˇe toho také lze tyto reprezentace mezi sebou libovolnˇe pˇrevádˇet bez pouˇzit´ı aritmetických operac´ı na reálných cˇ´ıslech. Poznamenejme, zˇ e r˚uzné popisy se ale výraznˇe liˇs´ı co do velikosti a na poˇzadovaném výstupu pak závis´ı výsledná sloˇzitost celého algoritmu.

4.1 Druhy algoritmu˚ V této cˇ a´ sti bychom rádi podali struˇcný pˇrehled algoritm˚u, které se pouˇz´ıvaj´ı pro výpoˇcet konvexn´ıho obalu na základˇe mnoˇziny vrchol˚u {p1 , . . . , pn }. Jako i v dalˇs´ıch oblastech výpoˇcetn´ı geometrie i zde jsou vˇsechny algoritmy zaloˇzeny na základn´ıch postupech, konkrétnˇe na inkrementáln´ım, procházej´ıc´ım graf a rozdˇel-a-panuj. Pˇred t´ım, neˇz pˇristoup´ıme k popisu obecných algoritm˚u, zmiˇnme, zˇ e speciáln´ım pˇr´ıpadem problému je protˇr´ıdˇen´ı vrchol˚u tak, aby zˇ a´ dný v mnoˇzinˇe se nedal vyjádˇrit jako konvexn´ı kombinace zbylých. V angliˇctinˇe se tento typ u´ lohy nazývá irredudancy problem. Duáln´ım problémem k tomuto je odstranˇen´ı redundantn´ıch nerovnic z lineárn´ıho programu. K ˇreˇsen´ı se tedy pouˇz´ıvá lineárn´ı program, který pˇri testován´ı 18

kaˇzdého vrcholu bˇezˇ´ı v pevné dimenzi v cˇ ase O(n2 ). Clarkson [3] tuto metodu jeˇstˇe upravil tak, zˇ e kaˇzdý program obsahuje pouze tolik nerovnost´ı, kolik je vrchol˚u ve výsledk˚u. Dosáhl t´ım cˇ asového vylepˇsen´ı na O(nV), kde V je právˇe velikost výsledné mnoˇziny vrchol˚u.

4.1.1 Inkrementáln´ı algoritmy Pravdˇepodobnˇe nejˇcastˇeji volenou metodou pro výpoˇcet konvexn´ıho obalu je ta inkrementáln´ı. Právˇe zde vˇsak narázˇ´ıme na problém s formou výstupu. Nˇekteré z reprezentac´ı jsou sami o sobˇe velké (viz tabulka 4.1) a nav´ıc, v pr˚ubˇehu algoritmu jsou poˇc´ıtány vˇsechny jednotlivé mezikroky, které mohou m´ıt také výraznˇe vyˇssˇ´ı sloˇzitost neˇz výsledný polyedr. Tyto nesnáze autoˇri algoritm˚u ˇreˇs´ı pˇredevˇs´ım sofistikovanými metodami, které jsou pouˇzity pˇri urˇcován´ı poˇrad´ı, ve kterém budou vrcholy zpracovávány. Reprezentace Dvojitá Svazová Hraniˇcn´ı

Nejhorˇs´ı pˇr´ıpad Nedegenerovaný pˇr´ıpad d · µ(d, n) d·m d 2 · µ(d, n) 2d · m µ(d, n) m

Tabulka 4.1: Velikosti reprezentac´ı polytop˚u ( ) ( ) n − ⌈d/2⌉ n − 1 − ⌈(d − 1)/2⌉ µ(n, d) = + . ⌊d/2⌋ ⌊(d − 1)/2⌋ m = poˇcet faset polyedru Pˇred popisem inkrementáln´ıho algoritmu definujme nˇekteré zákládn´ı pojmy. Definice. P je degenerovaný polytop v Rd , pokud nˇekterou jeho stˇenu tvoˇr´ı v´ıce neˇz d vrchol˚u nebo z nˇekterého vrcholu vycház´ı v´ıce neˇz d hran. Definice. Pro nedegenerovaný polytop P v Rd a pro bod v < P rˇekneme, zˇe faseta f polytopu P je viditelná, pokud plat´ı, zˇe nadrovina h definuj´ıc´ı f oddˇeluje v a P (tj. nacház´ı se v r˚uzných poloprostorech). Jinak je faceta zakrytá (angl. obscured). Horizontem nazýváme mnoˇzinu ridges, která oddˇeluje viditelné a zakryté fasety. Nyn´ı uˇz m˚uzˇ eme formulovat bˇezˇ ný krok algoritmu. Pˇred n´ım samozˇrejmˇe mus´ı probˇehnout inicializace, bˇehem které je vytvoˇren z nˇekolika vrchol˚u polytop plné dimenze a zpravidla je i urˇceno poˇrad´ı vkládaných vrchol˚u (pokud tak nen´ı uˇcinˇeno na zaˇca´ tku kaˇzdého bˇezˇ ného kroku). Bˇezˇ ný krok algoritmu pak bere jako vstup polytop Pi−1 tvoˇrený vrcholy {p1 , . . . , pi−1 }, ke kterému pˇridá vrchol pi a vytvoˇr´ı nový polyedr z vrchol˚u {p1 , . . . , pi }. Skládá se z tˇechto operac´ı: 1. Nalezen´ı (a vymazán´ı) vˇsech viditelných faset 2. Identifikace horizontu 3. Vytvoˇren´ı nových faset 19

Vˇsechny algoritmy se pak liˇs´ı pouze v tom, jak pˇristupuj´ı k jednotlivým bod˚um bˇezˇ ného kroku a v urˇcen´ı poˇrad´ı vkládaných vrchol˚u. Viditelné fasety: Nejednoduˇssˇ´ı zp˚usob, jak naj´ıt vˇsechny viditelné fasety, je otestovat vˇsechny fasety polytopu Pi−1 . Tento postup vol´ı napˇr´ıklad “beneath-beyond” algoritmus [13] nebo Motzkin˚uv algoritmus dvojité reprezentace [11]. Asymptotická cˇ asová sloˇzitost vycház´ı na Ω(n⌊d/2⌋+1 ). Jiný pˇr´ıstup pro zmˇenu udrˇzuje pro kaˇzdý dosud nevloˇzený vrchol seznam z nˇeho viditelných faset. Udrˇzován´ı této struktury ale nakonec vycház´ı v nejhorˇs´ım pˇr´ıpadˇe stejnˇe jako pˇredcházej´ıc´ı pˇr´ıpad. Ukazuje se vˇsak, zˇ e pˇri randomizovaném poˇrad´ı vkládán´ı vrchol˚u v pr˚umˇeru dopadne lépe, konkrétnˇe O(n⌊d/2⌋ ). Posledn´ı pouˇz´ıvaný pˇr´ıstup spoˇc´ıvá v udrˇzován´ı fasetového grafu, kde vrcholy zastupuj´ı fasety a hrany ridges. Dva vrcholy jsou spojeny hranou právˇe tehdy, kdyˇz nˇekteré dvˇe fasety je obsahuj´ıc´ı sd´ıl´ı spoleˇcnou ridge. Ve chv´ıli vyhledáván´ı vˇsech viditelných faset pak staˇc´ı nalézt pouze jednu a zbylé identifikovat prohledáván´ım grafu do hloubky. Poˇca´ teˇcn´ı fasetu je moˇzné nalézt prohledáván´ım vˇsech ve vhodném poˇrad´ı ([18]), udrˇzován´ım vˇzdy viditelných faset jako u [5] a [4] nebo s vyuˇzit´ım lineárn´ıho programován´ı (opˇet [18]). Tento zp˚usob vycház´ı cˇ asovˇe optimálnˇe vzhledem k poˇctu viditelných stˇen v kaˇzdém kroku. Horizont: Jeho sestaven´ı je triviáln´ı ve fasetovém grafu, odpov´ıdá hranám, které vedou mezi viditelnými a zakrytými fasetami. Jinak vyˇzaduje pouˇzit´ı speciáln´ıch datových struktur, které v krátkém cˇ ase odhal´ı, které zakryté fasety soused´ı s právˇe jednou viditelnou fasetou. Nové fasety: Samotná konstrukce je jednoduchá a vycház´ı cˇ asovˇe odpov´ıdaj´ıc´ı poˇctu nových faset. Aby jejich poˇcet z˚ustal co nejmenˇs´ı, je tˇreba zvolit vhodné poˇrad´ı vkládaných vrchol˚u. Nejjednoduˇs´ı je zvolit náhodné poˇrad´ı, které v pr˚umˇerném cˇ ase dopadne O(n⌊d/2⌋ ). Chazelle v roce 1993 publikoval dokonce deterministický algoritmus zaloˇzený na pseudonáhodném výbˇeru, který dopadne cˇ asovˇe optimálnˇe i v nejhorˇs´ım pˇr´ıpadˇe. Degenerovaný vstup: Pˇripomeˇnme, zˇ e vˇsechny výsledky byly uvedeny pouze ve vztahu k nedegenerovanému vstupu. Pokud dovol´ıme naprosto náhodný vstup, dopadaj´ı vˇsechny uvedené algoritmy sˇpatnˇe, pˇriˇcemˇz hlavnˇe jejich datové struktury se podstatnˇe komplikuj´ı. Zat´ım nejlepˇs´ım algoritmem pro obecný vstup je algoritmus dvojité reprezentace, jejˇz jsme zvolili i my pro naˇsi implementaci. Proto o nˇem budeme podrobnˇe hovoˇrit aˇz ve vztahu k naˇs´ı implementaci v dalˇs´ı cˇ a´ sti. Na závˇer bychom jeˇstˇe rádi zd˚uraznili podm´ınku na plnou dimenzi zpracovávaného polyedru. Pokud by tato nebyla splnˇena, museli bychom naj´ıt nejmenˇs´ı afinn´ı podprostor, který obsahuje celý polyedr, provést projekci do prostoru odpov´ıdaj´ıc´ı dimenze a pokraˇcovat ve výpoˇctu v niˇzsˇ´ı dimenzi. V p˚uvodn´ı dimenzi bychom nevˇedˇeli, jak vypadaj´ı fasety polyedru (jakou maj´ı dimenzi) a problematický by byl i jejich popis pomoc´ı nerovnic (ˇslo by o pr˚unik nejednoznaˇcnˇe urˇcených nadrovin a zm´ınˇeného afinn´ıho podprostoru).

4.1.2 Algoritmy procházen´ı grafem Algoritmy tohoto druhu procházej´ı graf faset polytopu P pˇres jeho ridges. Z fasety F pˇres ridge R hledaj´ı sousedn´ı fasetu F ′ tak, zˇ e maximalizuj´ı u´ hel mezi nimi. V dimenzi dvˇe a tˇri je tento postup známý pod pojmem gift-wrapping. Mimochodem, duáln´ı algoritmus procház´ı vrcholy po hranách, a jedná se tedy o algoritmy ze stejné tˇr´ıdy jako 20

uvedené metody z druhé kapitoly. Základn´ı idea algoritmu spoˇc´ıvá v nalezen´ı nˇejaké inicializaˇcn´ı fasety a vˇsech jej´ıch ridges. Ty jsou z poˇca´ tku vˇsechny oznaˇceny jako otevˇrené, protoˇze jeˇstˇe neznáme zˇ a´ dnou fasetu, která by s nˇekterou z nich sousedila z druhé strany. V obecném kroku algoritmu jde o nalezen´ı libovolné dalˇs´ı fasety, která soused´ı s nˇekterou z dosud nalezených facet pˇres otevˇrenou ridge. U nové fasety jsou spoˇc´ıtány vˇsechny jej´ı ridges a je rozhodnuto, zda-li jsou otevˇrené cˇ i nikoliv. Tady nastává problém, protoˇze ne vˇsechny ridges nové fasety mus´ı být nutnˇe otevˇrené, nová faseta m˚uzˇ e sousedit s dalˇs´ımi jiˇz nalezenými fasetami. Po vyhodnocen´ı, které ridges jsou otevˇrené a které jsou naopak z otevˇrených vylouˇceny, se postup opakuje, dokud existuje otevˇrená ridge. Z výsˇe popsaného postupu vyplývaj´ı následuj´ıc´ı problémy: 1. Jak co nejrychleji nalézt samotnou fasetu F ′ 2. Jak co nejrychleji nalézt ridges nové fasety F ′ 3. Jak spravovat otevˇrené ridges Pokud budeme nejdˇr´ıve pro jednoduchost pˇredpokládat, zˇ e vstup nen´ı degenerovaný, automaticky nám odpadne problém 2. Pˇr´ımá cesta k vyˇreˇsen´ı 3 vede pˇres pouˇzit´ı datové struktury zaloˇzené na dictionary. Nakonec k nalezen´ı fasety F ′ vede nejpˇr´ımˇejˇs´ı cesta pˇres vyzkouˇsen´ı pˇres vˇsechny vrcholy, kde jeden takový krok pobˇezˇ´ı v cˇ ase odpov´ıdaj´ıc´ımu poˇctu vrchol˚u na vstupu. Sofistikovanˇejˇs´ı algoritmy ale mohou m´ıt lepˇs´ı nejen cˇ asovou, ale hlavnˇe prostorovou sloˇzitost. Velmi praktickým se jev´ı algoritmus, který popsali Avis a Fukuda v [1], který procház´ı fasetový graf do hloubky pˇres jeho kostru, takˇze nen´ı nutné v pr˚ubˇehu ukládat informace o ridges. Jiný algoritmus, tentokrát je jeho autorem Seidel, postupuje po smˇeru pˇr´ımky shelling of P [16]. Pokud pˇripust´ıme degenerovaný vstup, tak jako prvn´ı se nab´ız´ı jeho u´ prava perturbac´ı jednotlivých vrchol˚u. Jiná cesta vede pˇres u´ pravu algoritm˚u na výpoˇcet svazové reprezentace nebo výsˇe zm´ınˇených pro obecnou polohu. Rote [15] se pokusil optimalizovat algoritmus Avise a Fukudy, ale bohuˇzel se ukázalo, zˇ e nen´ı tak praktický jako jeho vzor. I Seidelova metoda byla upravována, a to samotným autorem ve stejném roce v [17].

4.1.3 Algoritmy rozdˇel-a-panuj Tento druh algoritmu se zat´ım nepovedlo generalizovat pro obecnou dimenzi, respektive jeho pouˇzit´ı se zat´ım jev´ı jako velmi nepraktické. Na druhou stranu jako jeden z mála zp˚usob˚u lze efektivnˇe pouˇz´ıt pro dimenzi 4 a 5, na které bˇezˇ né algoritmy pro malou dimenzi nestaˇc´ı. Této problematice se vˇenovali Chan, Snoeyink a Yap v [6] nebo Amato a Ramos v [2].

4.2 Algoritmus dvojité reprezentace Tento algoritmus patˇr´ı do tˇr´ıdy inkrementáln´ıch algoritm˚u a bývá vyuˇz´ıván jako snadná metoda pro výpoˇcet degenerovaných vstup˚u. Pro nedegenerovaný vstup sice nen´ı optimáln´ı, ale samozˇrejmˇe je moˇzné ho vyuˇz´ıt. Z d˚uvodu této obecnosti jsme se rozhodli vz´ıt ho jako inspiraci pro násˇ algoritmus. 21

Viditelné fasety jsou vyhledány jednoduchým testován´ım vˇsech faset. Na výpoˇcet horizontu se pak vyuˇz´ıvá dvojité reprezentace, na základˇe které je vypoˇc´ıtán pr˚unik kaˇzdé viditelné a zakryté fasety. Pokud tento pr˚unik je podmnoˇzinou nˇekteré dalˇs´ı fasety z Pi−1 , pak nem˚uzˇ e tvoˇrit ridge, a tedy nen´ı ani horizontáln´ı ridge. V naˇsem algoritmu jsme vyuˇzili pˇredevˇs´ım nápad neuchovávat ridges v nˇejaké struktuˇre. Po nalezen´ı nˇekteré viditelné hrany, dopoˇc´ıtáváme uvedeným zp˚usobem jednotlivé ridges, ale d´ıky datové struktuˇre popsané v následuj´ıc´ı kapitole pod heslem dvojité reprezentace, nemus´ıme prohledávat vˇsechny moˇzné fasety, ale jen ty, které obsahuj´ı nˇejaký vrchol z aktuálnˇe prohledávané. Tam, kde prohledáván´ı konˇc´ı, automaticky v´ıme, zˇ e se nacház´ı horizont. Výhoda algoritmu v degenerovaném pˇr´ıpadˇe spoˇc´ıvá v tom, zˇ e nen´ı potˇreba vypoˇc´ıtávat ridges degenerovaných faset, na coˇz by bylo nutné pouˇz´ıt napˇr´ıklad rekurzi nebo lineárn´ı program. V silnˇe degenerovaných pˇr´ıpadech tyto cˇ asovˇe pˇr´ıp. prostorovˇe nároˇcné metody selhávaj´ı.

22

5. Uˇzivatelská dokumentace Násˇ program je postaven jako bal´ık funkc´ı, které slouˇz´ı k práci s polyedry. Uˇzivateli je urˇceno pˇet základn´ıch funkc´ı, pˇriˇcemˇz dvˇe z toho jsou co do funkˇcnosti ekvivalentn´ı. Rozhodli jsme se pro programovac´ı jazyk MATLAB, pˇriˇcemˇz jsme se pokusili zachovat kompatibilitu s freewarem Octave. Bohuˇzel se nám to nepodaˇrilo stoprocentnˇe, ale d´ıky tomu, zˇ e nˇekteré zdrojové kódy Octavu je moˇzné upravovat, doc´ılili jsme po malých zmˇenách v nainstalovaných bal´ıc´ıch kompatibility. Tato kapitola by mˇela slouˇzit pˇredevˇs´ım jako uˇzivatelská dokumentace a jej´ı pˇreklad do anglického jazyka je moˇzné nalézt na pˇriloˇzeném CD.

5.1 Datové struktury pro vstup a výstup V programu se vyskytuj´ı v zásadˇe tˇri druhy datových struktur, pˇriˇcemˇz kaˇzdá z nich m˚uzˇ e být pouˇzita jako vstupn´ı nebo výstupn´ı u vˇetˇsiny funkc´ı. 1. Nerovnice/Rovnice: jsou uchovávány jednom objektu sloˇzeném ze dvou cˇ a´ st´ı: A zastupuje matici, tedy levé strany nerovnost´ı/rovnost´ı, b pravé strany. V objektu nen´ı urˇceno, zda-li se jedná o rovnice cˇ i nerovnice, jejich povaha je vˇzdy zˇrejmá z kontextu. Je moˇzné pouˇz´ıt konstruktor inequalities(A,b) Pˇr´ıklad: ( ) ( ) 1 2 5 ≤ 3 4 6 Nerovnice.A = [1 2;3 4]; Nerovnice.b = [5;6] %nebo Nerovnice = inequalities([1 2;3 4],[5;6]) 2. Vrcholy jsou zadány jednoduˇse v matici, kaˇzdý na jednom ˇra´ dku. Pˇr´ıklad: △ABC, A[0; 0], B[0; 1], C[1; 0] ABC = [0 0; 0 1; 1 0]; 3. Dvojitá reprezentace je uloˇzena do ponˇekud komplikovanˇejˇs´ı struktury tak, aby vzájemné propojen´ı vrchol˚u a facet mohlo být prohledáváno v konstantn´ım cˇ ase. Mˇejme polyedr P, pak P.c vrát´ı souˇradnice jednotlivých vrchol˚u. Pro i-tý vrchol P(i).c vrát´ı jeho souˇradnice. P(i).ineq uchovává informace o fasetách, ve kterých i-tý vrchol leˇz´ı. P(i).ineq(j) vrát´ı j-tou fasetu. Informace o jedné fasetˇe se skládáj´ı ze dvou cˇ a´ st´ı: inequal – obsahuje nerovnici a1 + . . . + ad ≤ b jako pole [a1 , . . . , ad , b]; vert – obsahuje seznam index˚u, které odkazuj´ı na pozice vrchol˚u, které leˇz´ı ve fasetˇe (vˇcetnˇe i-tého vrcholu). Pˇr´ıklad: △ABC, A[0; 0], B[0; 1], C[1; 0], AB : −y ≤ 0, AC : −x ≤ 0, BC : x + y ≤ 1 ABC.c ans = 0 0 23

ans = 0 1 ans = 1 0 ABC(1).c ans = 0 0 ABC(1).ineq(1) inequal = 0 -1 0 vert = 1 2 ABC(1).ineq(2) inequal = -1 0 0 vert = 1 3 %v´ ypis vˇ sech nerovnic Nerovnice = extractineq(ABC) %v´ ypis vˇ sech vrchol˚ u do jedn´ e matice Vrcholy = extractvertices(ABC)

5.2 Pˇrevod z nerovnicové do vrcholové reprezentace Pro pˇrevod z nerovnicové do vrcholové reprezentace slouˇz´ı funkce [Vrcholy, Hrany] = ineqtovertices(Nerovnice,Rovnice,’S’) kde tˇret´ı parametr je volitelný. Do parametru Nerovnice se zadávaj´ı nerovnice, a to ve tvaru (1) a vˇsechny s porovnávac´ım znaménkem ≤. Za parametr Rovnice se dosazuj´ı rovnice v tomtézˇ tvaru. Tˇret´ı volitelný parametr m˚uzˇ e m´ıt pouze hodnotu ’S’ a znamená, zˇ e uˇzivatel nechce vrátit pouze seznam vrchol˚u tvoˇr´ıc´ıch polyedr, ale chce vrátit polyedr v dvojité reprezentaci (3). Pokud uˇzivatel nemá zadány zˇ a´ dné nerovnice resp. rovnice, nechá na jejich m´ıstˇe prázdné pole, tj []. Funkce má dva výstupn´ı parametry, pˇriˇcemˇz druhý je volitelný. V prvn´ım je podle toho, jestli je nebo nen´ı definován tˇret´ı parametr, seznam vrchol˚u polyedru, nebo polyedr v dvojité reprezentaci. Druhý parametr Hrany obsahuje seznam vektor˚u, které urˇcuj´ı smˇer neomezených hran. Pokud takové existuj´ı, znamená to, zˇ e polyedr je neomezený a tato informace je vˇzdy vypsána i na konzoli, i kdyˇz nen´ı poˇzadován druhý výstup. Jako polyedr m˚uzˇ e být zadána libovolná kombinace nerovnic a rovnic dimenze 1 a v´ıce. Pokud nemá polyedr zˇ a´ dný vrchol, ale je neprázdný, je vráceno prázdné pole Vrcholy. Neomezené hrany nejsou bez vrcholu dobˇre definovány, a proto druhý parametr nedává smysl.

5.3 Pˇrevod z vrcholové do nerovnicové reprezentace Pro pˇrevod z vrcholové do nerovnicové reprezentace slouˇz´ı dvˇe funkce: Polyedr = verticestoineqcomb(Vrcholy, ’S’) Polyedr = verticestoineqdual(Vrcholy, ’S’) 24

které se liˇs´ı v pouˇzitém algoritmu pro výpoˇcet, ale výstup maj´ı stejný. Prvn´ı funkce pouˇz´ıvá inkrementáln´ı algoritmus zaloˇzený na algoritmu dvojité reprezentace, druhá vyuˇz´ıvá duáln´ı pˇrevod a lineárn´ı programován´ı. Na vstupu se zadává seznam vrchol˚u podle (2). Druhý parametr je volitelný, m˚uzˇ e nabývat pouze hodnoty ’S’ a znamená, zˇ e uˇzivatel chce m´ısto nerovnic vrátit polyedr v dvojité reprezentaci podle (3). Výsledek funkce vrac´ı jako nerovnice ve tvaru (1), nebo, pokud je zadán druhý vstupn´ı parametr, jako polyedr ve dvojité reprezentaci podle (3). U tˇechto funkc´ı je podm´ınka na vstup taková, zˇ e mezi vrcholy mus´ı existovat d + 1 afinnˇe nezávislých, protoˇze jinak by netvoˇrily polyedr plné dimenze. Pokud je vrchol˚u málo nebo neobsahuj´ı afinnˇe nezávislou podmnoˇzinu, skuteˇcnost je oznámena na konzoli a výstup z˚ustává prázdný.

5.4 Konvexn´ı sjednocen´ı Konvexn´ı sjednocen´ı je binárn´ı operace, jej´ımˇz výsledkem je nejmenˇs´ı konvexn´ı mnoˇzina obsahuj´ıc´ı oba operandy. V naˇsem pˇr´ıpadˇe sjednocujeme konvexn´ı polyedry a výsledkem je tedy opˇet konvexn´ı polyedr. Pro konvexn´ı sjednocen´ı je definována funkce [Polyedr, Hrany] = union(Polyedr1, Polyedr2, vystup) kde Polyedr1 a Polyedr2 zastupuj´ı operandy a tˇret´ı argument znaˇc´ı, v jakém tvaru má být prvn´ı výstupn´ı parametr. Polyedr1 i Polyedr2 mohou být zadány v kterémkoli ze tˇr´ı pˇr´ıpustných tvar˚u, oba mus´ı být definovány v prostoru se stejnou dimenz´ı. Vstupn´ı tvar nen´ı tˇreba nijak specifikovat, funkce sama zjist´ı, která forma byla zvolena. Pokud je nˇekterý nebo oba vstupy ve sˇpatném tvaru, je tato skuteˇcnost oznámena výpisem na konzoli a výstup z˚ustává prázdný. I tady plat´ı podm´ınka, zˇ e polyedr ve vrcholové reprezentaci mus´ı m´ıt plnou dimenzi a v nerovnicovém tvaru mus´ı m´ıt aspoˇn jeden vrchol. Parametr vystup m˚uzˇ e nabývat tˇr´ı hodnot: ’S’ – výsledek se vrac´ı v dvojité reprezentaci, ’F’ – výsledek se vrac´ı v nerovnicové (fasetové) reprezentaci, ’V’ – výsledek se vrac´ı ve vrcholové reprezentaci. Výstup obsahuje dvˇe hodnoty, pˇriˇcemˇz druhá je volitelná. Prvn´ı parametr obsahuje výsledek v tvaru specifikovaném tˇret´ım vstupn´ım argumentem, druhý parametr obsahuje seznam neomezených hran. Tento parametr má význam pouze, pokud se na vstupu objevil polyedr v nerovnicové reprezentaci. Pokud zˇ a´ dné neomezené hrany neexistuj´ı, vrac´ı se pole prázdné. Kromˇe výstupn´ıch parametr˚u m˚uzˇ e být na konzoli vytisknuta i informace o tom, zˇ e nˇekterý polyedr nebo oba jsou neomezené, coˇz znamená, zˇ e i výsledek je neomezený.

˚ 5.5 Prunik Výsledkem binárn´ı operace pr˚unik je maximáln´ı mnoˇzina, která byla obsaˇzena v obou vstupn´ıch mnoˇzinách. V pˇr´ıpadˇe pr˚uniku konvexn´ıch polyedr˚u jde opˇet o konvexn´ı polyedr. Definice funkce pr˚uniku je v podstatˇe analogická k funkci sjednocen´ı

25

[Polyedr, Hrany] = intersection(Polyedr1, Polyedr2, vystup) Polyedr1 i Polyedr2 mohou být zadány v kterémkoli ze tˇr´ı pˇr´ıpustných tvar˚u, oba mus´ı být definovány v prostoru se stejnou dimenz´ı. Vstupn´ı tvar nen´ı tˇreba nijak specifikovat, funkce sama zjist´ı, která forma byla zvolena. Pokud je nˇekterý nebo oba vstupy ve sˇpatném tvaru, je tato skuteˇcnost oznámena výpisem na konzoli a výstup z˚ustává prázdný. I tady plat´ı podm´ınka, zˇ e polyedr ve vrcholové reprezentaci mus´ı m´ıt plnou dimenzi a v nerovnicovém tvaru mus´ı m´ıt aspoˇn jeden vrchol. Parametr vystup m˚uzˇ e nabývat tˇr´ı hodnot: ’S’ – výsledek se vrac´ı v dvojité reprezentaci, ’F’ – výsledek se vrac´ı v nerovnicové (fasetové) reprezentaci, ’V’ – výsledek se vrac´ı ve vrcholové reprezentaci. Výstup obsahuje dvˇe hodnoty, pˇriˇcemˇz druhá je volitelná. Prvn´ı parametr obsahuje výsledek v tvaru specifikovaném tˇret´ım vstupn´ım argumentem, druhý parametr obsahuje seznam neomezených hran. Tento parametr má význam pouze, pokud se na vstupu objevily dva polyedry v nerovnicové reprezentaci. Pokud zˇ a´ dné neomezené hrany neexistuj´ı, vrac´ı se pole prázdné.

5.6 Odstranˇen´ı redundantn´ıch nerovnic Pro odstranˇen´ı redundantn´ıch nerovnic slouˇz´ı funkce Nerovnice = rmineq(Nerovnice) kde jako vstupn´ı parametr jsou zadány nerovnice ve tvaru (1) a výsledkem jsou nerovnice ve stejném tvaru tak, zˇ e kaˇzdá urˇcuje jednu fasetu polyedru, který p˚uvodn´ı nerovnice definovaly.

5.7 Odstranˇen´ı redundantn´ıch vrcholu˚ Pro odstranˇen´ı redudantn´ıch vrchol˚u je vyuˇz´ıvána funkce Vrcholy = rmvertices(Vrcholy) kde jako vstupn´ı parametr jsou zadány vrcholy ve tvaru (2) a výsledkem jsou vrcholy ve stejném tvaru tak, zˇ e kaˇzdý je extrémn´ı, tj. konvexn´ı obal vˇsech vrchol˚u a mnoˇziny bez jednoho z vrchol˚u se liˇs´ı.

˚ 5.8 Pˇrizpusoben´ ı pro Octave Pokud bude uˇzivatel cht´ıt spustit funkce z knihovny v prostˇred´ı Octave, je nutné nahradit ve sloˇzce bal´ıcˇ ku optim (Octave/gcc-ˇc. verze/share/octave/packeges/optim-ˇc. verze) soubor linprog.m stejnojmenným souborem pˇriloˇzeným k bal´ıku. Funkce linprog bˇezˇ nˇe pouˇz´ıvaná v MATLABu pro lineárn´ı programován´ı je v Octavu nahrazena funkc´ı glpk. Aby byla zachována kompatibilita mezi Octavem a MATLABem, linprog v Octavu zpracuje zadané parametry a k výpoˇctu je nakonec pouˇzita funckce glpk. V p˚uvodn´ım souboru linprog.m bylo vˇsak nˇekolik bug˚u a nav´ıc nebyla moˇznost dosáhnout na vˇsechny návratové hodnoty dostupné pro origináln´ı linprog.

26

Upravený soubor linprog.m umoˇznˇ uje rˇeˇsit vˇsechny u´ lohy, které zvládl p˚uvodn´ı soubor, nav´ıc um´ı vrátit tˇret´ı výstupn´ı parametr funkce linprog, který ˇr´ıká, jestli bylo dosaˇzeno optimáln´ıho ˇreˇsen´ı, a pokud nebylo, z jakého d˚uvodu. Pro naˇs´ı potˇrebu staˇcilo zjistit, jestli ˇreˇsen´ı existuje (Octave kód 180), pak vrac´ı 1, jinak vrac´ı 0.

27

6. Programátorská dokumentace V této cˇ a´ sti pop´ısˇeme podrobnˇe pouˇzité datové struktury a algoritmy. Hlavn´ı cˇ a´ st bude vˇenována pˇrevod˚um mezi r˚uznými reprezentacemi, protoˇze algoritmy sjednocen´ı a pr˚uniku v podstatˇe pouze vyuˇz´ıvaj´ı pˇredchoz´ıch dvou funkc´ı.

6.1 Pˇrevod z nerovnicové do vrcholové reprezentace Jak uˇz bylo ˇreˇceno v pˇredchoz´ı kapitole, pouˇz´ıvanou funkc´ı je [Vrcholy, Hrany] = ineqtovertices(Nerovnice,Rovnice,’S’) Algoritmus pouˇzitý v implementaci této funkce je zaloˇzen na pivotovac´ım algoritmu z (3.1). M˚uzˇ eme ho rozdˇelit na tˇri cˇ a´ sti: inicializaci, hlavn´ı cˇ a´ st a formátován´ı výsledku. Inicializace se skládá ze zaveden´ı promˇenných, analýzou vstupu a pokud je vstup správnˇe, je spuˇstˇena funkce fronta = iniineqtovertices(Nerovnice, Rovnice, dimenze) která uprav´ı vstupn´ı omezen´ı pro potˇreby simplexové metody podle pravidel z prvn´ı kapitoly, odstran´ı redundantn´ı rovnice a najde vstupn´ı pˇr´ıpustné bázické ˇreˇsen´ı. Vrac´ı pak frontu, ve které se nacház´ı poˇca´ teˇcn´ı vrchol ve tvaru: vrchol.v obsahuje souˇradnice vrcholu vrchol.mat obsahuje redukovanou simplexovou tabulku vˇcetnˇe sloupeˇcku obsahuj´ıc´ıho b. vrchol.bz obsahuje indexy bázických promˇenných vrchol.n obsahuje indexy nebázických promˇenných Hlavn´ı cˇ a´ st je uzavˇrena do while-cyklu. V kaˇzdém jeho kroku je odstranˇen a zpracován prvn´ı prvek fronty, dokud ta nen´ı prázdná. Ve vnoˇreném for-cyklu jsou prohledávány sloupeˇcky simplexové tabulky aktuáln´ıho prvku a jsou hledáni pivoti, podle pravidel popsaných v druhé kapitole. Pokud je pivot v daném sloupeˇcku nalezen, je tabulka upravena a spolu s n´ı vznikne nový prvek, který je moˇzné zaˇradit do fronty. Pˇred t´ım je otestováno, zda-li uˇz dˇr´ıve nebyl nalezen prvek se stejnou báz´ı. Pokud nikoliv, prvek je zaˇrazen do fronty. Poté prob´ıhá jeˇstˇe test ˇreˇsen´ı, a to jestli jemu odpov´ıdaj´ıc´ı vrchol uˇz je ve výsledku. Pokud ne, zaˇrad´ı se do promˇenné Vrcholy, která zastupuje seznam vrchol˚u polyedru. Vzhledem k velkému poˇctu moˇzných báz´ı, byla k jejich ukládán´ı zvolena trie. Vyhledáván´ı pak prob´ıhá vˇzdy v O(rd), kde r znaˇc´ı poˇcet promˇenných. Vrchol˚u je naproti tomu ˇra´ dovˇe ménˇe, a proto jsme si vystaˇcili s lineárn´ım seznamem. Pokud pro daný sloupeˇcek nebyl nalezen pivot, otestuje se, opˇet podle pravidla z druhé kapitoly, jestli tento sloupeˇcek reprezentuje neomezenou hranu, a pokud ano, je tato zaˇrazena do výsledku. V závˇereˇcné u´ pravˇe výsledku je ovˇeˇreno, zˇ e vˇsechny nalezené vrcholy jsou skuteˇcnˇe vrcholy (podle toho, zˇ e náleˇz´ı aspoˇn do d stˇen). Tento test je nutný, protoˇze kv˚uli

28

u´ pravám promˇenných na kladné se mohou objevit vrcholy, které ve skuteˇcnosti vrcholy nejsou, i kdyˇz jsou v polyedru samozˇrejmˇe obsaˇzeny. Kromˇe toho jsou také protˇr´ıdˇeny neomezené hrany, aby se do výsledku dostaly pouze unikátn´ı hrany, a to i co do násobku. Pokud je na výstupu vyˇzadován polyedr ve dvojité reprezentaci, je tato spoˇc´ıtána z p˚uvodn´ıch omezen´ı a výsledných vrchol˚u.

6.2 Pˇrevod z vrcholové do nerovnicové reprezentace – duáln´ı metoda Jedna ze dvou funkc´ı, které slouˇz´ı k pˇrevodu z vrcholové do nerovnicové reprezentace Vrcholy = verticestoineqdual(Vrcholy, ’S’) pouˇz´ıvá ve svém algoritmu dualitu a pˇrevod z nerovnicové do vrcholové reprezentace. Funkce samotná obsahuje v podstatˇe pouze pˇrevod na duáln´ı polyedr a zpˇet a mezit´ım ve svém tˇele volá funkci ineqtovertices. Nejdˇr´ıve je ovˇeˇrena vstupn´ı podm´ınka na afinn´ı nezávislost. Poté probˇehne inicializace pomoc´ı funkce [Vrcholy,centroid,OriginalV] = inivertoineqdual(Vrcholy) která spoˇc´ıtá nový stˇred souˇradné soustavy vzhledem k p˚uvodn´ım souˇradnic´ım (centroid) a vrát´ı vrcholy vzhledem k novým souˇradnic´ım (Vrcholy) a k p˚uvodn´ım souˇradnic´ım (OriginalV). Kromˇe toho, pokud by byl zadán polyedr dimenze 1, okamˇzitˇe ho spoˇc´ıtá a v následuj´ıc´ım kroku je uloˇzen do výsledku a hlavn´ı funkce konˇc´ı. Po inicializaci probˇehne pˇrevod na duáln´ı polyedr a je spuˇstˇen algoritmus pro pˇrevod z nerovnicové reprezentace. Po jeho dobˇehnut´ı jsou vrcholy pˇrevedeny zpˇet na primárn´ı polyedr, poté jsou výsledné nerovnice upraveny do p˚uvodn´ı souˇradné soustavy. Pokud uˇzivatel poˇzadoval výstup v dvojité reprezentaci, je výsledek dopoˇc´ıtán na základˇe p˚uvodn´ıch vrchol˚u a nerovnic.

6.3 Pˇrevod z vrcholové do nerovnicové reprezentace – kombinatoricky Druhá ze dvou funkc´ı pro pˇrevod z vrcholové do nerovnicové reprezentace Vrcholy = verticestoineqcomb(Vrcholy, ’S’) vyuˇz´ıvá kombinatorického inkrementáln´ıho algoritmu, pˇriˇcemˇz tento je inspirován algoritmem dvojité reprezentace, který je popsán v posledn´ı cˇ a´ sti cˇ tvrté kapitoly. Inicializace se skládá ze dvou krok˚u. V prvn´ım je ovˇeˇrena podm´ınka na afinn´ı nezávislost, a v dalˇs´ım shrnutém do funkce [Nerovnice, Polyedr, Vrcholy] = inivertoineqcomb(Vrcholy) je vytvoˇren poˇca´ teˇcn´ı polyedr (jehlan) plné dimenze v dvojité reprezentaci (Polyedr), vypsány nerovnice, které ho definuj´ı (Nerovnice), a urˇceno poˇrad´ı pro vkládán´ı dalˇs´ıch vrchol˚u (Vrcholy). Následuje hlavn´ı cyklus, ve kterém jsou postupnˇe pˇridávány dalˇs´ı vrcholy do poˇca´ teˇcn´ıho polyedru. Pˇridán´ı jednoho vrcholu je zabaleno do souhrnné funkce 29

[Nerovnice, Polyedr] = addvertex(Vrcholy(i,:), Nerovnice, Polyedr) která vˇzdy vrát´ı polyedr Pi v dvojité reprezentaci (Polyedr) a fasety, které ho definuj´ı (Nerovnice). Pˇridán´ı vrchol˚u prob´ıhá v nˇekolika fáz´ıch. Nejdˇr´ıve je nalezena prvn´ı viditelná faseta nebo faseta, ve které pˇridávaný vrchol leˇz´ı. Tato faseta je zaˇrazena do fronty, která bude slouˇzit k prohledáván´ı. Pokud nav´ıc nastane druhá situace, je tato stˇena uloˇzena pro pozdˇejˇs´ı pouˇzit´ı. Poznamenejme jeˇstˇe, zˇ e viditelná faseta je vyhledávána mezi vˇsemi fasetami postupnˇe v poˇrad´ı podle cˇ asu pˇridán´ı od nejnovˇejˇs´ı. V dalˇs´ı fázi zaˇc´ıná prohledáván´ı do sˇ´ıˇrky od jedné viditelné stˇeny k ostatn´ım. D´ıky dvojité reprezentaci jsou v konstantn´ım cˇ ase nalezeny vˇsechny vrcholy, které patˇr´ı do aktuálnˇe prob´ırané fasety. U kaˇzdého z nich jsou prohledány vˇsechny jeho fasety a hledá se pr˚unik tˇechto faset s prob´ıranou. Pokud maj´ı spoleˇcných aspoˇn d − 1 vrchol˚u a tyto vrcholy nejsou podmnoˇzinou jiné fasety, je mezi tˇemito dvˇema fasetami ridge. Pokud je nová faseta také viditelná, je zaˇrazena do prohledáván´ı. Pokud nen´ı, ridge se stává souˇca´ st´ı horizontu. Kromˇe toho je také z polyedru odstranˇena prob´ıraná faseta. Nakonec prob´ıhá konstrukce nových faset. Ty se nacház´ı mezi novým vrcholem a kaˇzdou ridge z horizontu. Pokud byly cestou nalezeny fasety, do kterých patˇril pˇridávaný vrchol, jsou tyto o nˇej rozˇs´ıˇreny, a pokud byly smazány, jsou znovu do polyedru pˇridány. D´ıky povaze struktury pouˇz´ıvané k dvojité reprezentaci jsou vˇsechny tyto operace provedeny v lineárn´ım cˇ ase vzhledem k poˇctu nových faset. Po tom, co jsou vˇsechny vrcholy zpracovány, jsou ze seznamu faset odstranˇeny nulové ˇra´ dky, které tu zbyly po fasetách, které byly pozdˇeji odstranˇeny. Pokud je nav´ıc na výstupu poˇzadován polyedr ve dvojité reprezentaci, je tato jeˇstˇe jednou pˇrepoˇc´ıtána, protoˇze polyedr, který je výsledkem algoritmu, m˚uzˇ e obsahovat body, které nejsou extrémn´ı.

6.4 Konvexn´ı sjednocen´ı Funkce konvexn´ıho sjednocen´ı [Polyedr, Hrany] = union(Polyedr1,Polyedr2,vystup) vrac´ı nejmenˇs´ı polyedr, ve kterém jsou Polyedr1 a Polyedr2 obsaˇzeny. Algoritmus zaˇc´ıná analýzou vstupu, pˇri které je zjiˇstˇeno, v jaké reprezentaci jsou polyedry zadány, a pˇr´ıpadnˇe jsou oba upraveny na vrcholovou reprezentaci (z dvojité reprezentace jsou vytaˇzeny pouze vrcholy, na nerovnicovou reprezentaci je pouˇzita funkce pro pˇrevod z nerovnicové do vrcholové reprezentace). Výjimeˇcná situace nastává ve chv´ıli, kdy jsou oba polyedry zadány ve vrcholové reprezentaci a na výstup je poˇzadován opˇet vrcholová reprezentace, pak je m´ısto funkce pro pˇrevod z vrcholové do nerovnicové reprezentace pouˇzita funkce pro odstranˇen´ı redundantn´ıch vrchol˚u. Seznamy vrchol˚u obou polyedr˚u jsou spojeny do jednoho, který reprezentuje sjednocen´ı. Aby byly vylouˇceny body, které nejsou extrémn´ı, je pouˇzita funkce pro pˇrevod z vrcholové do nerovnicové reprezentace. Ta nav´ıc vydá polyedr ve dvojité reprezentaci, ze kterého je moˇzné vypsat i seznam faset. Na závˇer je výsledek upraven do formy, kterou si vyˇza´ dal uˇzivatel specifikac´ı tˇret´ıho parametru. Pokud byl nˇekterý z polyedr˚u zadán v nerovnicové reprezentaci, je moˇzné, zˇ e pˇri jeho pˇrevodu se objevily nˇejaké neomezené hrany. V takovém pˇr´ıpadˇe je 30

jejich seznam vrácen na m´ıstˇe druhého parametru, pˇriˇcemˇz, pokud mˇely oba polyedry neomezené hrany, jsou tyto porovnány a jsou odstranˇeny pˇr´ıpadné redudance.

˚ 6.5 Prunik Funkce pr˚uniku [Polyedr, Hrany] = intersection(Polyedr1,Polyedr2,vystup) vrac´ı nejvˇetˇs´ı polyedr, který je obsaˇzen v obou zadaných. Algoritmus zaˇc´ıná analýzou vstupu, pˇri které je zjiˇstˇeno, v jaké reprezentaci jsou polyedry zadány, a pˇr´ıpadnˇe jsou oba upraveny na nerovnicovou reprezentaci (z dvojité reprezentace jsou vytaˇzeny pouze nerovnice, na vrcholovou reprezentaci je pouˇzita funkce pro pˇrevod z vrcholové do nerovnicové reprezentace). Výjimeˇcná situace nastává ve chv´ıli, kdy jsou na vstupu oba polyedry v nerovnicové reprezentaci a na výstupu je opˇet poˇzadována nerovnicová reprezentace. Pak je m´ısto funkce pro pˇrevod z nerovnicové do vrcholové reprezentace pouˇzita funkce na odstranˇen´ı redundantn´ıch nerovnic. Seznamy faset obou polyedr˚u jsou spojeny do jednoho, který reprezentuje pr˚unik. Aby byly vylouˇceny nerovnice, které nedefinuj´ı zˇ a´ dnou fasetu, je pouˇzita funkce pro pˇrevod z nerovnicové do vrcholové reprezentace. Ta nav´ıc vydá polyedr ve dvojité reprezentaci, ze kterého je moˇzné vypsat i seznam vrchol˚u. Na závˇer je výsledek upraven do formy, kterou si vyˇza´ dal uˇzivatel specifikac´ı tˇret´ıho parametru. Pokud byly oba polyedry zadány v nerovnicové reprezentaci, je moˇzné, zˇ e se ve výsledku objevily nˇejaké neomezené hrany. V takovém pˇr´ıpadˇe je jejich seznam vrácen na m´ıstˇe druhého parametru.

6.6 Odstranˇen´ı redundantn´ıch nerovnic K odstranˇen´ı redundantn´ıch nerovnic z popisu polyedru se pouˇz´ıvá funkce Nerovnice = rmineq(Nerovnice) která je zaloˇzena na testován´ı pomoc´ı lineárn´ıho programován´ı. V cyklu je postupnˇe kaˇzdá nerovnice stanovena jako maximalizaˇcn´ı c´ılová funkce. Pokud optimáln´ı ˇreˇsen´ı vyjde s konkrétn´ı hodnotou, je tato dosazena do zvolené nerovnice a pokud pˇri porovnán´ı vycház´ı levá strana menˇs´ı nebo rovna pravé, je nerovnice z popisu polyedru odstranˇena.

6.7 Odstranˇen´ı redundantn´ıch vrcholu˚ K odstranˇen´ı redundantn´ıch vrchol˚u z popisu polyedru se pouˇz´ıvá funkce Vrcholy = rmvertices(Vrcholy) která pouˇz´ıvá pˇrevod z vrcholové do nerovnicové reprezentace a poté testuje, zda-li je kaˇzdý bod ze zadaných vrcholem cˇ i nikoliv. Tento zp˚usob nen´ı pˇr´ıliˇs efektivn´ı, zvolili jsme ho zejména z d˚uvodu snadné implementace. 31

Funkce pˇrevodu z vrcholové do nerovnicové reprezentace vrac´ı seznam vˇsech nerovnic, kde kaˇzdá urˇcuje jednu fasetu. D´ıky tomu je moˇzné testovat, zda-li je nˇejaký bod vrcholem, t´ım, do kolika nadrovin urˇcených nerovnicemi patˇr´ı. Pokud patˇr´ı alespoˇn do d nezávislých nadrovin, znamená to, zˇ e daný bod je vrcholem polyedru.

6.8 Zaokrouhlovac´ı chyby Na závˇer této kapitoly bychom jeˇstˇe rádi zm´ınili problém s numerickou stabilitou. Pˇri vˇsech aritmetických operac´ıch vznikaj´ı drobné zaokrouhlovac´ı chyby, pˇriˇcemˇz nˇekteré algoritmy jsou na nˇe citlivˇejˇs´ı neˇz jiné, mezi jinými napˇr´ıklad i pouˇz´ıvaná Gaussova eliminace. Rozhodli jsme pˇri veˇskerém porovnáván´ı cˇ´ısel brát ohled jen na prvn´ıch pˇet desetinných m´ıst. V bˇezˇ ných pˇr´ıpadech je tato konstanta ideáln´ı, protoˇze správnˇe urˇc´ı, která cˇ´ısla jsou skuteˇcnˇe stejná a která se naopak liˇs´ı aˇz pˇr´ıliˇs. Je vˇsak moˇzné, zvlásˇtˇe u rozsáhlých vstup˚u, které vyˇzaduj´ı velké mnoˇzstv´ı aritmetických operac´ı, zˇ e se numerická chyba postupnˇe zaˇcne projevovat i na prvn´ıch pˇeti desetinných m´ıstech. Jindy se naopak m˚uzˇ e stát, zˇ e skuteˇcnˇe r˚uzná cˇ´ısla jsou po zaokrouhlován´ı rozpoznána jako identická. Problému s numerickou stabilitou se nelze vyvarovat, protoˇze v geometrii situace, kdy malá odchylka znamená velkou zmˇenu vlastnost´ı, nastávaj´ı. Vzpomeˇnme pˇr´ıklad dvou rovnobˇezˇ ných pˇr´ımek, kdy uˇz drobná nepˇresnost zp˚usob´ı, zˇ e p˚uvodnˇe rovnobˇezˇ né pˇr´ımky se nakonec nˇekdy protnou.

32

7. Porovnán´ı pouˇzitých algoritmu˚ V této cˇ a´ sti bychom rádi porovnali dva zvolené algoritmy pro pˇrevod z vrcholové do nerovnicové reprezentace. Vzhledem k tomu, zˇ e jeden z algoritm˚u pouˇz´ıvá algoritmus pro pˇrevod z nerovnicové do vrcholové reprezentace, dojde v této kapitole na analýzu dvou hlavn´ıch algoritm˚u pouˇzitých v celém bal´ıku funkc´ı. Porovnáváme algoritmus zaloˇzený na geometrické dualitˇe a pivotovac´ım algoritmu, jehoˇz járdo spoˇc´ıvá ve vhodné u´ pravˇe simlexové metody, který je zastoupený funkc´ı verticestoineqdual (1), a algoritmus zaloˇzený na kombinatorické metodˇe dvojité reprezentace, který je zastoupen funkc´ı verticestoineqcomb (2). Znaˇcen´ı. d′ : poˇcet promˇenných v simplexovém algoritmu d′ = 2 · d + m kde m = poˇcet facet.

7.1 Omezen´ı na vstup Oba algoritmy vyˇzaduj´ı na vstupu mnoˇzinu vrchol˚u, která obsahuje afinnˇe nezávislou podmnoˇzinu s d + 1 vrcholy. Toto omezen´ı je dáno v (2) t´ım, zˇ e algoritmus je potˇreba inicializovat na polyedr plné dimenze. V (1) by sice teoreticky mohl být výsledkem polyedr menˇs´ı dimenze, ale takový postup by vyˇzadoval naj´ıt nejmenˇs´ı afinn´ı podprostor Rd , který by obsahoval daný polyedr, a vyhledáván´ı bodu, do kterého by bylo potˇreba posunout poˇca´ tek, by se také znaˇcnˇe komplikovalo. Rozhodli jsme se tedy v obou pˇr´ıpadech nechat na uˇzivateli nalezen´ı takového podprostoru a vytvoˇren´ı projekce do niˇzsˇ´ı dimenze, ve které uˇz bude násˇ algoritmus fungovat.

7.2 Implementaˇcn´ı sloˇzitost Vzhledem k tomu, zˇ e souˇca´ st´ı bal´ıku mˇela být funkce pro pˇrevod z nerovnicové do vrcholové reprezentace, vycház´ı nám implementaˇcnˇe jednoduˇssˇ´ı (1), protoˇze v nˇem pouze jednoduˇse upravujeme vstup pro dˇr´ıve naimplementovanou funkci. Pokud bychom mˇeli do porovnán´ı zahrnout i programován´ı algoritmu pro pˇrevod z nerovnicové do vrcholové reprezentace, doˇsli bychom k opaˇcnému závˇeru. Zat´ımco (2) pouˇz´ıvá pouze základn´ı kombinatorické a programovac´ı triky, pomocná funkce (1) vyˇzadovala ruˇcne implementovat simplexový algoritmus (kv˚uli práci se simplexovou tabulkou), pouˇzit´ı sloˇzitˇejˇs´ıch datových struktur, napˇr´ıklad trie, jej´ızˇ naprogramován´ı bez moˇznosti pouˇz´ıt pointery nebylo pˇr´ımoˇcaré, ale napˇr´ıklad i ladˇen´ı programu se stávalo nepˇrehledným napˇr´ıklad v okamˇziku, kdy se objevilo mnoho pˇr´ıpustných báz´ı a mezi nimi se ztrácela jedna neomezená hrana.

7.3 Prostorová nároˇcnost Analýzu prostorové nároˇcnosti bychom rádi rozdˇelili na dvˇe cˇ a´ sti. V prvn´ı rozebereme asymptotické chován´ı algoritm˚u, zat´ımco v druhé porovnáme pomoc´ı tabulky namˇeˇrených hodnot nároky na pamˇet’ u r˚uzných pˇr´ıklad˚u zadán´ı. 33

7.3.1 Asymptotická prostorová nároˇcnost Hlavn´ı nároky na pamˇet’ v (1) jsou obsaˇzeny v pomocném algoritmu, protoˇze jinak jsou uchovávány pouze u´ daje lineárnˇe odpov´ıdaj´ıc´ı vstupu. Nejzásadnˇejˇs´ı prostorové nároky algoritmu pro pˇrevod z nerovnicové do vrcholové reprezentace spoˇc´ıvaj´ı v udrˇzován´ı fronty, ve které jeden jej´ı cˇ len má kv˚uli simpleˇ u fronty m˚uzˇ e být maximálnˇe tolik, kolik xové tabulce ˇra´ dovˇe velikost O(d (d′ )· m). Clen˚ existuje pˇr´ıpustných báz´ı, tedy m , kde m je poˇcet vrchol˚u na vstupu. Podobný objem pamˇeti mus´ıme vyhradit ( ′ )i pro uloˇzen´ı jiˇz nalezených báz´ı, pouˇz´ıvaná trie má celkem maximáln´ı velikost O( dm d2 ) Inkrementáln´ı algoritmus vyˇzaduje pamˇet’ pouze na uloˇzen´ı aktuáln´ı podoby polyedru, coˇz znamená lineárn´ı prostor pro vrcholy a prostor na fasety. Tˇech m˚uzˇ e být v pr˚ubˇehu algoritmu výraznˇe v´ıce neˇz ve výsledku, pˇriˇcemˇz jsme nepouˇzili zˇ a´ dnou heuristiku, která by poˇcet faset zmenˇsovala. Jejich mnoˇzstv´ı tedy odhadneme jako maximáln´ı poˇcet faset pro polyedr o n vrcholech ( n ) v R. Pouˇzijeme tzv. Upper bound theorem, který ˇr´ıká, zˇ e facet je maximálnˇe 2 ⌊d/2⌋ . Po rozepsán´ı vˇsech výraz˚u dojdeme k výsledku, zˇ e (2) by mˇel vycházet lépe.

7.3.2 Porovnán´ı na konkrétn´ıch pˇr´ıkladech Pro porovnán´ı na konkrétn´ıch pˇr´ıkladech jsme se rozhodli vygenerovat náhodná data pro nˇekolik dimenz´ı v r˚uzném rozsahu. Konkrétn´ı hodnoty se nacház´ı v souboru testData.txt na pˇriloˇzeném CD. K vygenerován´ı dat jsme implementovali jednoduchou konzolovou aplikaci pro C#, která generuje r˚uzné typy polyedr˚u a zapisuje je do souboru. I tento program je moˇzné dohledat na pˇriloˇzeném CD. K mˇeˇren´ı pamˇet’ových nárok˚u jsme pouˇzili funkci memory = whos jej´ızˇ výstupem je na pozici memory.bytes cˇ´ıslo, které zastupuje poˇcet byt˚u aktuálnˇe vyuˇz´ıvaných pro lokáln´ı promˇenné. U funkce (1) jsme mˇeˇren´ı vloˇzili na konec hlavn´ıho cyklu pomocného algoritmu, pˇriˇcemˇz v kaˇzdé obrátce cyklu bylo testováno, zda-li aktuáln´ı nároky na pamˇet’ jsou vyˇssˇ´ı neˇz dˇr´ıve dosaˇzená hodnota, a pokud ano, je p˚uvodn´ı hodnota pˇrepsána novou vˇetˇs´ı. Nakonec je hodnota vrácena jako dalˇs´ı výstupn´ı parametr (1). Funkci (2) jsme mˇeˇrili obdobnˇe a test pamˇeti jsme um´ıstili dokonce na dvˇe m´ısta, konkrétnˇe na konec funkce [Nerovnice, Polyedr, pamet] = addvertex(vrchol, nerovnice, Polyedr) a pak do cyklu, ve kterém jsou vyhledávány viditelné fasety. Mimo to bylo nutné drobnˇe upravit funkci [Nerovnice, Polyedr, Vrcholy, pamet] = inivertoineqcomb(Vrcholy) protoˇze i v n´ı je pouˇz´ıvána funkce pro pˇridán´ı vrcholu a nav´ıc, pokud je zadáno pouze d + 1 vrchol˚u, tak uˇz v n´ı je dosaˇzeno výsledného polyedru. Vˇsechny funkce, které bylo nutné upravit, pouˇzité skripty ke spouˇstˇen´ı test˚u a jejich výsledky jsou opˇet k dispozici na pˇriloˇzeném CD. 34

Následuj´ı tabulky výsledk˚u, kterých bylo dosaˇzeno bˇehem test˚u. Kaˇzdá tabulka zastupuje jednu dimenzi, pro kterou byly testy provedeny, jde konkrétnˇe o dimenze dva, tˇri, cˇ tyˇri a deset. V kaˇzdé dimenzi jsme poˇc´ıtali pˇr´ıklady s d + 1 (simplex s vrcholem v poˇca´ tku a s jedn´ım vrcholem na kaˇzdé kladné souˇradnicové poloose), 15, 50 a 100 vrcholy (náhodnými), s krychl´ı a osmistˇenem (v pˇr´ısluˇsné dimenzi). Kaˇzdý ˇra´ dek tabulky odpov´ıdá jednomu pˇr´ıkladu a ve sloupeˇcc´ıch jsou uvedeny namˇeˇrené hodnoty pro obˇe funkce v bytech. Znaˇcen´ı. Znak ? znamená, zˇe program na tomto vstupu nedobˇehl a nebylo tedy moˇzné urˇcit jeho pamˇet’ové nároky. D˚uvodem selhán´ı byla pˇr´ıliˇsná cˇ asová nároˇcnost (viz dále). 2D d+1 15 50 100 krychle osmistˇen

4D d+1 15 50 100 krychle osmistˇen

comb 584 2373 4565 8149 1077 1077

comb 2328 20877 86965 166661 9085 7533

dual 2168 18640 16720 33376 3232 3664


dual 44696 365200 2966912 9066064 6517872 78256

comb dual 1256 8632 21141 332400 19957 424896 33253 600752 2917 76456 2757 17288


comb dual 22536 ? 637581 ? ? ? ? ? ? ? ? ?

Tabulka 7.1: Prostorová nároˇcnost algoritm˚u Jak je vidˇet, prostorová nároˇcnost vycház´ı vˇzdy lépe pro kombinatorický algoritmus, coˇz jsme po naˇsem odvozen´ı oˇcekávali. Nejvˇetˇs´ı rozd´ıl nastává v pˇr´ıpadu krychle, tedy velmi degenerovaném vstupu.

ˇ 7.4 Casov´ a sloˇzitost Stejnˇe jako u prostorové nároˇcnosti i zde budeme postupovat ve dvou kroc´ıch: teoretickém a praktickém.

7.4.1 Asymptotická cˇ asová sloˇzitost ˇ Pod´ıvejme se nejdˇr´ıve na algoritmus (1). Casov´ a nároˇcnost pomocného algoritmu se odv´ıj´ı od sloˇzitosti simplexové metody. V nejhorˇs´ım pˇr´ıpadˇe je nutné proj´ıt vˇsechny báze, pˇriˇcemˇz jeden krok je lineárn´ı vzhledem k d′( a)poˇctu výsledných vrchol˚u V. Jak ′ uˇz jsme vidˇeli v pˇredchoz´ı cˇ a´ sti, moˇzných báz´ı je dm , takˇze celková sloˇzitost vycház´ı ( ′) na O( dm (V + d′ )). 35

ˇ Casov´ a nároˇcnost inkrementáln´ıho algoritmu (2) závis´ı na sloˇzitosti jednoho kroku, pˇriˇcemˇz krok˚u je celkem n. Prvn´ı viditelná faseta je nalezena pr˚umˇernˇe v O(d) (leˇz´ı kolem posledn´ıho pˇridaného vrcholu a okolo nˇej leˇz´ı pr˚umˇernˇe O(d) faset). Dalˇs´ı kroky spoˇc´ıvaj´ı ve vyhledán´ı vˇsech viditelných faset, pˇriˇcemˇz sloˇzitost tohoto kroku je O(i·dd−2 ), kde i je poˇcet viditelných faset v Pi z aktuáln´ıho vrcholu, pˇriˇcemˇz výsledkem kroku je nejen nalezen´ı a smazán´ı viditelných faset, ale i vytvoˇren´ı horizontu. Zbývá uˇz pouze vytvoˇrit nové fasety, pˇriˇcemˇz cˇ asu k tomu potˇrebný je lineárn´ı k poˇctu nových faset. Jeˇstˇe poznamenejme, zˇ e odhad poˇctu viditelných facet uvaˇzujeme jako nejhorˇs´ı moˇzný, tedy jako maximáln´ı poˇcet vˇsech stˇen v polyedru s odpov´ıdaj´ıc´ım poˇctem vrchol˚u. Po seˇcten´ı sloˇzitost´ı nám vycház´ı O(nd dd−2 ), coˇz je v porovnán´ı s prvn´ım algoritmem v pr˚umˇerném pˇr´ıpadˇe horˇs´ı výsledek.

7.4.2 Porovnán´ı na konkrétn´ıch pˇr´ıkladech Pro porovnán´ı cˇ asové nároˇcnosti jsme pouˇzili stejná testovac´ı data a skripty jako pˇri porovnán´ı prostorové nároˇcnosti. Na mˇeˇren´ı cˇ asu jsme vyuˇzili dvojici funkc´ı tic; time = toc; kde prvn´ı zahajuje mˇerˇen´ı na intern´ıch stopkách a druhá ho ukonˇcuje, pˇriˇcemˇz vrac´ı aktuáln´ı dosaˇzenou hodnotu. Funkce jsme um´ıstili vˇzdy na u´ plný zaˇca´ tek a konec kódu funkc´ı, pˇriˇcemˇz jsme pˇridali dalˇs´ı výstupn´ı parametr obsahuj´ıc´ı namˇeˇrený cˇ as. Upravený kód a testovac´ı skript je opˇet nahrán na pˇriloˇzeném CD. Na rozd´ıl od pamˇeti je cˇ as závislý i na tom, na jakém stroji je spouˇstˇen a v jakém prostˇred´ı. Testován´ı prob´ıhalo na na notebooku HP Compaq 6710b s 32bitovým operaˇcn´ım systémem Windows Vista Business, procesorem Intel(R) Core(TM)2 Duo T8100 2.10 GHz 3MB L2 Cache, 2 GB pamˇet´ı. Stejnˇe jako v cˇ a´ sti o pamˇet’ové nároˇcnosti i zde uvád´ıme tabulky s výsledky ze ´ vˇsech mˇeˇren´ı, a to opˇet ve stejném tvaru. Udaje jsou v sekundách. Znaˇcen´ı. ∞ znamená, zˇe program s tˇemito vstupn´ımi daty bˇezˇel v´ıce neˇz dvacet minut a jeho výpoˇcet se nebl´ızˇil konci. 2D d+1 15 50 100 krychle osmistˇen

comb 0,01400009996723384 0,18700005987193440 0,75299997790716590 1,56900008092634400 0,02299995883367956 0,02299989399034530

36

dual 0,09399992250837386 0,30200002365745600 0,50499995693098750 0,90099990926682950 0,13399995688814670 0,09799989208113402


comb 0,02000006556045264 1,63999990921001900 2,75500009045936200 6,37000005797017400 0,11699993396177890 0,06799989589489996

dual 0,4910000846721232 5,5500000427709890 3,5100000484380870 4,7490000064717610 2,5930000693770130 0,3860000560525805


comb 0,03100005607120693 1,57100007892586300 17,1250000904547100 48,2310000217985000 0,93500000843778250 0,23600009805522860

dual 2,691999991191551 5,539999979780987 31,05799992452376 77,56999989587350 636,4840000655968 2,208000037004240


comb dual 0,1079999237554148 ∞ 75,539999956148680 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

ˇ Tabulka 7.2: Casov´ a nároˇcnost algoritm˚u

Z uvedených tabulek je jasnˇe vidˇet, zˇ e s vˇetˇs´ım náhodným vstupem se algoritmus zaloˇzený na dualitˇe chová lépe, ale pouze pokud velikost vstupu výraznˇe pˇrevyˇsuje dimenzi. V dimenzi dva a tˇri se pˇri naˇs´ı velikosti vstupu tato vlastnost jeˇstˇe projev´ı, ale v dimenzi cˇ tyˇri uˇz vycház´ı duáln´ı algoritmus vˇzdy jako pomalejˇs´ı. Zaj´ımavou se ukázala dimenze deset. Duáln´ı algoritmus nedobˇehl ani v tom nejjednoduˇssˇ´ım pˇr´ıpadˇe a ukázalo se tedy, zˇ e ve vyˇssˇ´ıch dimenz´ı je naprosto nepouˇzitelný. Kombinatorický algoritmus se sice snadno vyrovnal s nejjednoduˇssˇ´ım vstupem, ale patnáct vrchol˚u uˇz zpracovával déle neˇz minutu. Pˇri spuˇstˇen´ı na vˇetˇs´ı vstup se ukázalo, zˇ e pˇridán´ı 17. vrcholu trvá kolem pˇeti minut a 18. vrchol nebyl pˇridán ani po deseti minutách bˇehu. Jak je vidˇet, pˇridán´ı padesáti vrchol˚u by bylo cˇ asovˇe naprosto neúnosné.

7.5 Shrnut´ı výsledku˚ porovnán´ı Z porovnán´ı na konkrétn´ıch datech vyˇsel lépe kombinatorický algoritmus i pˇresto, zˇ e na skuteˇcnˇe velkých vstupech v malých dimenz´ıch by pravdˇepodobnˇe zaˇcal vycházet výraznˇe h˚uˇre co do cˇ asové nároˇcnosti. 37

Bohuˇzel se ukázalo, zˇ e ani jeden algoritmus nestaˇc´ı na vˇetˇs´ı vstupy ve vyˇssˇ´ıch dimenz´ıch a spoˇc´ıtat napˇr´ıklad nerovnice faset deseti-dimenzionáln´ı krychle se ukázalo jako naprosto nemoˇzné.

38

Závˇer Výsledkem práce je pˇredevˇs´ım odladˇená knihovna funkc´ı pro pokroˇcilou práci s polyedry, kterou jsme publikovali na https://sourceforge.net/p/polyhedrainmatl/ Mimoto jsme implementovali hned dvˇe funkce pro pˇrevod z vrcholové do nerovnicové reprezentace, a to nám umoˇznilo je vzájemnˇe porovnat a ovˇeˇrit si naˇse teoretické závˇery. Bohuˇzel se ukázalo, zˇ e pro velké vstupy se naˇse funkce pˇr´ıliˇs nehod´ı, protoˇze bˇezˇ´ı neúmˇernˇe dlouho v porovnán´ı s jinými knihovnami dostupnými na internetu (qhull, Fukudova knihovna [7], a dalˇs´ı). Nicménˇe pro menˇs´ı vstupy se m˚uzˇ e stát snadno a zdarma dostupnou knihovnou jak pro MATLAB, tak pˇredevˇs´ım pro Octave, pro který zˇ a´ dná podobná knihovna na internetu nen´ı dostupná. V budoucnosti je moˇzné pokraˇcovat ve vývoji knihovny, doimplementovat napˇr´ıklad rozd´ıl polyedr˚u, triangulaci, algoritmy pro pˇrevod do dalˇs´ıch reprezentac´ı, ale také vylepˇsit stávaj´ıc´ı funkce, aby se dostaly na u´ roveˇn svých konkurent˚u.

39

Seznam pouˇzité literatury [1] D. Avis, K. Fukuda. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete Comput. Geom., 8:295-313, 1992. [2] N.M. Amato, E.A. Ramos. On computing Voronoi diagrams by divide-pruneand-conquer. In Proc. 12th Annu. ACM Sympos. Comput. Geom., 1996. [3] K.L. Clarkson. More output-sensitive geometric algorithms. In Proc. 35th Annu. IEEE Sympos. Found. Comput. Sci., 1994. [4] K.L. Clarkson, K. Mehlhorn, R. Seidel. Four results on randomized incremental constructions. Comput. Geom. Theory Appl., 3:185-212, 1993 [5] K.L. Clarkson, P.W. Shor. Application of random sampling in computational geometry, II. Discrete Comput. Geom. 4:387-421, 1989 [6] T.M. Chan, J. Snoeyink, C.K. Yap. Output sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three. In Proc. 6th ACM-SIAM Sympos. Discrete Algorithms (SODA ’95), 1995. [7] K. Fukuda. Vertex Enumeration Package for Convex Polytopes and Arrangements, Version 0.41 Beta http://library.wolfram.com/infocenter/Demos/440/ ´ [8] L. Grygarová. Uvod do lineárn´ıho programován´ı. 1. vydán´ı Praha: Státn´ı pedagogické nakladatelstv´ı, 1975. [9] V. Chvátal. Linear Programming. 1. vydán´ı. New York: W. H. Freeman, 1983. ISBN 0-716-71587-2. [10] J. Matouˇsek. Lectures on Discrete Geometry. Volume 212 of Graduate texts in Math. 1. vydán´ı New York: Springer-Verlag, 2002. ISBN 0-387-95374-4 [11] T.S. Motzkin, H. Raiffa, G.L. Thompson, R.M. Thrall. The double description method. In H.W. Kuhn, A.W. Tucker, editors, Contributions to the Theory of Games II, volume 8 of Ann. of Math. Stud. Princeton: Princeton University Press, 1953. ISBN 0-691-07935-8 [12] Noˇziˇcka F., Guddat J., Bank B., Hollatz H. Theorie der linearen parametrischen Optimierung. Berlin: Akademie- Verlag, 1974. [13] F.P. Preparata, M.I. Shamons. Computational Geometry: An Introduction. 3. vydán´ı New York: Springer-Verlag,1985. ISBN 0-387-96131-3 [14] J. Rohn. Lineárn´ı algebra a optimalizace na slidech. http://uivtx.cs.cas.cz/ rohn/publist/laslidesrev.ps revidovaná verze, 2004. [15] G. Rote. Degenerate convex hulls in high dimensions withou extra storage. In Proc. 8th Annu. ACM Sympos. Comput. Geom., 1992. [16] R. Seidel. Constructing higher dimensional convex hulls at logaritmic cost per face. In Proc. 18th Annu. ACM Sympos. Theory Comput., 1986. 40

[17] R Seidel. Output-size sensitive algorithms for constructive problems in computational geometry. Ph.D. thesis, Dept. Comput. Sci., Cornel Univ., Ithaca, 1986. Tech. Rep. TR 86-784. [18] R. Seidel. Small-dimensional linear programming and convex hull made easy. Discrete Comput. Geom., 6:423-434, 1991 [19] R. Seidel Convex hull computations. In J.E. Goodman, J. O’Rourke, editors, Handbook of Computational and Discrete Geometry, first edition Boca Raton: CRCPress, 1997. ISBN 0-849-38524-5 [20] G.M. Ziegler. Lectures on Polytopes. Volume 152 of Graduate texts in Math. 1. vydán´ı New York: Springer-Verlag, 1994. ISBN 0-387-94329-3

41

Seznam tabulek 4.1 Tabulka 4.1. Velikosti reprezentac´ı polytop˚u 7.1 Tabulka 7.1. Prostorová nároˇcnost algoritm˚u ˇ 7.2 Tabulka 7.2. Casov´ a nároˇcnost algoritm˚u

42

Seznam pouˇzitých zkratek Rd Euklidovský prostor dimenze d In Jednotková matice s rozmˇerem n × n cT Transpozice vektoru c rank(A) Hodnost matice A 1 Vektor sloˇzený ze samých jedniˇcek (dimenze urˇcena z kontextu) O Vektor sloˇzený ze samých nul (dimenze je urˇcena z kontextu) ei jednotkový vektor s jedniˇckou na i-té pozici A∗s S-tý sloupec matice A ⟨a, b⟩ Skalárn´ı souˇcin vektor˚u a, b conv(X) Konvexn´ı obal mnoˇziny X (kde X ⊂ Rd )

43

Veronika Steffanová. Softwarový balík pro práci s polyedry. Univerzita Karlova v Praze Matematicko-fyzikální fakulta. Katedra aplikované matematiky

Recommend Documents