Při výpočtu hraničních přípustných řešení, je nejprve nutné získat maximální hodnoty všech os grafu. Ty poté vynásobíme konstantou multiplier (v současné chvíli nastaveno na 1,8).
Tím je docíleno, že v případě vykreslování neomezené množiny přípustných řešení, bude zobrazena v určitém poměru ke zbytku grafu. Poté přidáme do soustavy omezení tři další omezení (hraniční) v následujícím tvaru:
1 2 3
, , . x graphMaxX1 multiplier x graphMaxX2 multiplier x graphMaxX3 multiplier
(2.2.6)
kde proměnné graphMaxX1, graphMaxX2, graphMaxX3 jsou získaná maxima jednotlivých os grafu a multiplier přednastavená konstanta.
Následně je třeba vytvořit pole, které bude obsahovat všechna omezení, včetně třech nově vzniklých, aby mohly být vypočítány všechny průsečíky hraničních rovin (omezení). Proto je vytvořeno nové pole BorderPsArr. Toto pole vznikne sloučením pole FeasiblesArr a třech nových omezení. Obsahuje tedy všechna omezení zadaná uživatelem a tři nová hraniční omezení (2.2.6). S daným polem provede práci funkce combineBorderP. Tato funkce pracuje téměř stejně jako funkce combine. Vypočítá všechny průsečíky omezení a uloží je jako pole do proměnných BorderPointsX1, BorderPointsX2, BorderPointsX3.
Jelikož tato pole obsahují i některé souřadnice průsečíků z množiny základních přípustných řešení, je nutné odfiltrovat tyto shodné průsečíky. To zajišťuje následující část kódu, která vytvoří tři nová pole filteredX1, filteredX2, filteredX3 s průsečíky s hraničními omezeními, která nahrazují pole BorderPointsX1, BorderPointsX2, BorderPointsX3. V těchto polích už nejsou souřadnice duplicitních průsečíků (viz výpis 6).
Výpis 6 Filtrace shodných bodů (zdroj: autor)
let filteredX1 = [];
let filteredX2 = [];
let filteredX3 = [];
//vyfiltruje stejné body z polí BorderPoints a FeasiblePoints, uloží do nového pole ty, které jsou jedinečné
for(i=0; i<BorderPointsX1.length;i++){
let c = true;
let t = [BorderPointsX1[i], BorderPointsX2[i], BorderPointsX3[i]];
for(j=0;j<FeasiblePointsX1.length;j++){
let f = [FeasiblePointsX1[j], FeasiblePointsX2[j], FeasiblePointsX3[j]];
if(JSON.stringify(t) === JSON.stringify(f)){
c = false;
se pouze odlišnými názvy některých proměnných a některé funkce sloužící k porovnávání hodnot by byly nahrazeny funkcemi inverzními. Diagram lze nalézt v příloze B.
V současné fázi výpočtu jsou k dispozici základní přípustná řešení a hraniční přípustná řešení. Jejich souřadnice jsou uloženy v polích FeasiblePointsX1, FeasiblePointsX2, FeasiblePointsX3 a v polích filteredX1, filteredX2, filteredX3. Nyní je potřeba všechny tyto průsečíky postupně dosazovat do uživatelem zadané účelové funkce a hledat bod, v němž účelová funkce dosahuje maxima nebo minima. (viz výpis 7)
Výsledek úlohy může mít mnoho podob. Zde se pokusím popsat jednotlivé situace.
Pokud hodnota účelové funkce dosahuje lepšího maxima nebo minima v průsečíku hraničních omezení, boolean hodnota proměnné valueBetter je nastavena na true. To znamená, že úloha nemá optimální řešení, jelikož má neomezenou hodnotu účelové funkce.
Pokud maximum nebo minimum pro danou účelovou funkci dosahuje stejné hodnoty (maxima nebo minima) v průsečíku hraničních omezení jako v bodě, který je součástí základních přípustných řešení, pak se boolean hodnota proměnné valueEqual nastaví na true. To znamená, že výsledkem je polopřímka (případně polorovina) a tento průsečík hraničních omezení (bod) udává její směr. Úloha má alternativní optimální řešení.
Pokud hodnoty v průsečících hraničních omezení jsou horší než v bodech základních přípustných řešení, její optimální řešení spočívá v množině základních přípustných řešení.
Výpis 7 Hledání optima účelové funkce (maxima) (zdroj: autor) //maximalizace účelové funkce
1
if(objectiveFunction[3] === "max") { 2
//maxFeas je hodnota pro první bod 3
//pokud máme nějaké hraniční průsečíky 8
if(filteredX1.length>0){
9
maxBorder = firstBorder;
10
SolutionCoordX1border[0] = filteredX1[0];
11
SolutionCoordX2border[0] = filteredX2[0];
12
SolutionCoordX3border[0] = filteredX3[0];
13 14 } 15
for(i = 1; i < FeasiblePointsX1.length; i++) { 16
//a je výpočet hodnoty pro další průsečík 17
a = math.bignumber(math.add(math.round(math.multiply(objectiveFunction[0], 18
//pokud body mají shodnou hodnotu 22
SolutionCoordX1feas[0] = FeasiblePointsX1[i];
31
SolutionCoordX2feas[0] = FeasiblePointsX2[i];
32
SolutionCoordX3feas[0] = FeasiblePointsX3[i];
33 34 } 35 }
//porovnávání pro hraniční body 36
a = math.bignumber(math.add(math.round(math.multiply(objectiveFunction[0], 40
SolutionCoordX1border.push(filteredX1[i]);
45
SolutionCoordX2border.push(filteredX2[i]);
46
SolutionCoordX3border.push(filteredX3[i]);
47
SolutionCoordX1border[0] = filteredX1[i];
52
SolutionCoordX2border[0] = filteredX2[i];
53
SolutionCoordX3border[0] = filteredX3[i];
54
//pokud je výsledná hodnota účelové funkce u hraničních průsečíků stejná jako u průsečíků 63
//pokud je výsledná hodnota účelové funkce u hraničních průsečíků lepší než u průsečíků 68
2.3.4 Grafické zobrazení všech typů výsledků
Vyobrazení výsledků je poměrně složité, jelikož může nastat několik případů. V první fázi je nutné odlišit tři typy výstupů, které mohou nastat.
První možností je, že proměnné valueEqual a valueBetter zároveň nabývají hodnoty false.
V tomto případě se optimální řešení nachází v množině základních přípustných řešení.
V takovém případě je nejprve vykreslován objekt, jehož vrcholy jsou všechny body z množiny základních přípustných řešení. Tyto vrcholy jsou pak v grafu vyznačeny jako modré body. Poté je třeba vykreslit optimální řešení. To může mít trojí podobu. Řešením může být bod, úsečka nebo rovinná výseč. O jaké řešení se jedná, poznáme z délky pole, v němž jsou uloženy souřadnice výsledných bodů. Pokud je délka pole rovna jedné, výsledkem je bod. Pokud je délka pole rovna dvěma, výsledkem je úsečka mezi dvěma body, které máme v poli. Jestliže je délka pole rovna třem, výsledkem je rovinná výseč.
Druhou možností je, že hodnota proměnné valueEqual je rovna true. To nastane, pokud hledaný extrém účelové funkce, má stejnou hodnotu v bodě ze základních přípustných řešení jako v bodě z hraničních přípustných řešeních. Optimálním řešením je v tomto případě polopřímka, případně polorovina či rovinná výseč. Počáteční bod této polopřímky je ten bod ze základních přípustných řešení, se kterým hledaná účelová funkce nabývá extrému. Směr této polopřímky je určen pomocí bodu z hraničních přípustných řešení, v němž hodnota účelové funkce taktéž nabývá extrému. Při vykreslování roviny nebo rovinné výseče jsou sloučeny pole výsledných bodů ze základních přípustných řešení a pole výsledných bodů z hraničních přípustných řešení.
Třetí možností je, že hledaný extrém účelové funkce má „lepší“ hodnoty v nějakém bodě z hraničních přípustných řešení než v bodě z množiny základních přípustných řešení.
V takovém případě je hodnota proměnné valueBetter rovna true. To znamená, že neexistuje optimální řešení, jelikož hodnota účelové funkce je neomezená. V tomto případě je v grafu vykreslena pouze množina přípustných řešení, která pokračuje do nekonečna ve směru žlutých bodů (tyto body pouze pomáhají vyznačit směr, nemají jiný účel). Uživateli je zobrazena hláška, že optimální řešení neexistuje (viz obrázek 28).
Pokud nastane situace, kdy uživatel zadá úlohu, která má prázdnou množinu přípustných řešení, jelikož poloprostory omezení se „rozcházejí“, je upozorněn hláškou, algoritmus je zastaven a dále nepokračuje. Taková situace se pozná, pokud pole FeasiblePointsX1, FeasiblePointsX2, FeasiblePointsX3 jsou prázdná, tedy nemáme žádná základní přípustná řešení. V tomto případě je zobrazen pouze graf se zadanými omezeními.
2.3.5 Použití knihovny Plotly k vykreslení grafu Implementace knihovny
Knihovna je do webové aplikace implementována pomocí odkazu ke stažení ze CDN
v rodičovském elementu body. To zajišťuje, že se při každém načtení webové stránky stahuje nejaktuálnější verze této knihovny.
<script src="https://cdn.plot.ly/plotly-latest.min.js"></script>
Příprava knihovny
V počáteční fázi je na stránce vytvořen prázdný div s unikátním identifikátorem, do něhož je poté vykreslován graf. Následuje vytvoření konstanty v Javascriptu, do které je přiřazen objekt daného „divu“. Dalším potřebným krokem je vytvoření dvou konstant layout a config. Tyto dvě konstanty jsou objekty, ze kterých si později knihovna shromažďuje nastavení pro graf, více o těchto proměnných dále (Vykreslování).
Vykreslování
K vykreslování slouží především dvě funkce. Funkce newPlot a funkce addTrace.
V popisované aplikaci je třeba do grafu postupně přidávat velké množství objektů různých typů, proto po stisknutí tlačítka „Plot!“ je nejprve pomocí funkce newPlot vykreslen prázdný graf a do něj se v průběhu výpočtu přidávají objekty.
Plotly.newPlot(myDiv, [], layout, config);
Prvním parametrem funkce newPlot je myDiv. To je objekt, ve kterém je uložen odkaz na samotný předpřipravený HTML element (typu div), do něhož se graf vykresluje.
Do prázdných hranatých závorek by se většinou vkládal objekt skládající se z dat pro graf, typu objektu a dalších popisných parametrů. Zde jsou pouze prázdné závorky, jelikož zatím je vytvářen prázdný graf.
V objektu layout je potřeba nastavit některé parametry, které určují rozložení grafu.
Například se zde určuje velikost písma nebo názvy os grafu (viz výpis 8).
Výpis 8 Konstanta layout (zdroj: autor)
title: 'x<sub>1</sub>', },
yaxis: {
title: 'x<sub>2</sub>', },
zaxis: {
title: 'x<sub>3</sub>', }
} };
V objektu config se nastavují další parametry pro graf. V případě této aplikace tak, aby byl graf responzivní, tedy zabíral vždy maximální plochu v přiřazeném HTML elementu, a aby nebylo zobrazeno logo vykreslovací knihovny.
const config = {responsive: true, displaylogo: false,};
V průběhu algoritmu se přidávají do „prázdného“ grafu různé typy objektů, a to pomocí funkce addTraces. Na následujícím výpisu (výpis 9) lze například vidět, jak jsou vykreslovány poloprostory rovnoběžné s osami grafu.
Výpis 9 Ukázka funkce addTraces (zdroj: autor) Plotly.addTraces(myDiv, {
Za parametry x, y, z je vždy dosazováno pole, jenž reprezentuje souřadnice vrcholů nebo bodů nutných pro vykreslení grafu. Pomocí parametru type se určuje typ vykreslovaného
parametr mesh3D. Parametr opacity určuje průhlednost daného objektu.
V ukázce (výpis 9) je dosazena proměnná constraintsOpacity, do níž je na počátku funkce dopočítána a přiřazena hodnota odpovídající posuvníku průhlednosti na stránce (více o tomto posuvníku v části Průhlednost omezení).
Do parametru hovertext je vložen textový řetězec, který se zobrazí ve vyskakovací „bublině“
v případě, že uživatel „najede“ myší na daný objekt.
2.3.6 Další funkcionalita aplikace
Základním kritériem této aplikace bylo, aby výsledný graf byl pro uživatele co nejpřehlednější. Pokud nastane situace, kdy je zadáno mnoho omezení, stává se graf méně přehledný. Viz obrázek 16, kde je vykreslen graf s „pouze“ šesti omezeními a už tak ztrácí na přehlednosti.
Zobrazení hraničních rovin značně snižuje přehlednost zobrazení množiny přípustných řešení a optimálního řešení. Proto bylo potřeba implementovat řešení, které uživateli usnadní orientaci v grafu.