Referaty
Home
Anglictina
Biologie
Chemie
Dejepis-Historie
Diplom-Projekt
Ekonomie
Filozofie
Finance
Fyzika
Informatika
Literatura
Management
Marketing
Medicina
Nemcina
Ostatni
Politika
Pravo
Psychologie
Public-relations
Sociologie
Technologie
Zemepis-Geografie
Zivotopisy




























Téma, Esej na téma, Referátu, Referát, Referaty Semestrální práce:

Co je to…

Co je to…

* Diference

= rozdíl dvou nejnižších hodnot v každém řádku a každém sloupci nákladové tabulky {cij} při

výpočtu pomocí VAM.

* Příklad nemá optimální řešení z důvodu neomezenosti MPŘ

à poslední nalezené řešení (poslední simplexní) není optimální (tj. existuje lepší řešení), ale nové 28552zjx96zri8s

BPŘ nelze určit (tj. leží v nekonečnu), u duálně sdruženého nemá pak existuje OŘ (menší)

* Degenerované řešení dopravní úlohy

à počet kladných prvků báze < než (m + n - 1); obsahuje > (m x n) nenulových složek



nedegerované - počet prvků báze je právě n jr552z8296zrri

* Jaké proměnné používáme u přiřazovací úlohy?

à bivalentní/nulajednotkové proměnné Þ xij I í0; 1ý kde x = 1 (uskuteční), x = 0 (neuskuteční)

* Jak vypočítáme nejdříve možný konec činností?

Tj(0) = max(Ti(0) + tij) Þ nejdříve možný začátek činností + doba trvání daných činností

* Jakým způsobem upravíte dopr. úlohu, kde součet kapacit zdrojů je nižší než součet

požadavků spotřebitelů tak, aby byla řešitelná běžnými algoritmy (index. metoda, VAM)?

Přidáme fiktivní zdroj, který bude nabízet naše množství, aby úloha byla vybilancovaná.

* Jak nazýváme úlohu sledování závislosti opt. řešení max. úlohy celočíselného LP?

postoptimalizační analýza (analýza citlivosti)

* Co je to bivalentní proměnná?

dvojhodnotová, rozhodovací, nulajednotková, (celočíselná)

* Co udává dolní hranice hodnoty ÚF při řešení max. úlohy celočíselného LP?

dosud nejlepší přípustné řešení

* Co je to vybilancovaná dopr. úloha?

zdroje = požadavky

* Jakými veličinami mohou být ohodnoceny hrany grafu reprezentujícího síť MHD (každá

smysluplná veličina)

čas, kapacita, náklady

 
konvex. množina
krajní body
konvexní polyédr
kruh
/
¥
-
kružnice
-
¥
-
trojúhelník
/
3
/
vnitřek trojúhelníku
/
¥
-
polorovina
/
¥
-
rovina
/
¥
-
přímka
/
¥
-
úsečka
/
2
/
koule
/
¥
-
prázdná množina
/
-
-
bod
/
1
/
vnitřek kruhu
/
¥
-
polopřímka
/
1
-

Primár a duál

* Optimální řešení primáru a duálu

primár

max f (x) = 2x1 + 3x2

ST -x1 + x2 £ 4

3x1 + x2 £ 30

-2x1 + 3x2 £ 20

5x1 + 7x2 £ 28

4x1 - 3x2 £ 15

x1 + x2 £ 8

x1 £ 6

x2 £ 4

x1,2 ³ 0

duál

min g = 4w1 + 30w2 + 20w3 + 28w4 + 15w5 + 8w6 + 6w7 + 4w8

ST -w1 + 3w2 - 2w3 + 5w4 + 4w5 + w6 + w7 ³ 2

w1 + w2 + 3w3 + 7w4 - 3w5 + w6 - w8 ³ 3

wi ³ 0, i = 1 - 8

Předpoklad wopt (0, 0, 0, 2/5, 0, 0, 0, 1/5)

f(xopt) = g(wopt) = 12

w4 > 0 Þ 5x1 + 7x2 = 28

w8 > 0 Þ x2 = 4

xopt = (0, 4)

f(xopt) = 2x1 + 3x2 = 12

* Duál na primár

duál

min z = 3x1 + 2x2 - x3 + 2x4

ST 3x1 - x2 - 2x3 + 2x4 ³ -2

xij ³ 0

xopt = [0; 0; 1; 0]

primár

max g = -2w1

ST 3w1 £ 3 w1 £ 1

-w1 £ 2w1 ³ -2

-2w1 £ -1w1 ³ 1/2

2w1 £ 2w1 £ 1

wopt = [1/2]

* Primár na duál

primár

max 3x1 + 4x2 - 3x3

STx1 + x2 + x3 £ 1

xj > 0; j = 1, 2, 3

duál

min w = 1

STw1 ³ -3

w1 ³ 4

w1 ³ 3

wopt = 4

* Optimální řešení úlohy duálně sdružené úlohy

primár

max x1 - x2

ST x1 £ 1

x2 £ 1

xj ³ 0 pro j = 1, 2 je x[1;0] à 1. podmínka v duálu ve tvaru rovnosti

duál

min f = w1 + w2

w1 ³ 1

w2 ³ -1min f = max z = 1

wi ³ -1

Vektory, podmínky

* Omezující podmínky pro neohraničenou množinu bodů; nepatří tam bod [0, 0]

(-¥ < x < 0) v (0 < x < +¥) nebo

x I í(-¥;0) u (0;+¥)ý

x náleží do R kromě [0;0]

* Napište soustavu rovnic vyjadřující, že bod <x1; x2> leží v čtyřúhelníku daném body (1, 1),

(4, 3), (4, 1) a (3, 3).

k1 + k2 + 4k3 + 3k4 £ x

k1 + 4k2 + 3k3 + 3 k4 £ y

* Napište souřadnice některého krajního bodu množiny z předchozího příkladu.

(1;1), (4;3), (4;1), (3;3)

* Jakými lineárními podmínkami zabezpečíte, aby proměnná x1 nabývala pouze hodnot 1,

13/8, 29/7. Pozor! Podmínky musí platit současně. ? ? ?

x3 = y1 + 13/8 y2 + 29/7y3

xi = 1 a současně xi = 13/8 a současně xi = 27/9

y1 + y2 + y3 = 1

yi I í0;1ý

Dopravní úloha

* 25*125 (tj. m*n) u dopr. úlohy, napsat ÚF a vysvětlit, co znamená

min

m - počet zdrojů

n - počet zákazníků

m*n - počet možných dopr. cest

xij - počet jednotek zboží převážených na trase z i-tého zdroje k j-tému zákazníkovi

* Kolik proměnných se nachází v bázi při řešení dopr. úlohy se 4 zdroji a 8 spotřebiteli?

 
s1
s2
s3
s4
v1
3
4
7
6
v2
3
10
5
8

m + n - 1 = 4 + 8 - 1 = 11 Þ počet proměnných v bázi




m * n Þ počet řešení v úloze

* 3 zdroje mají kapacitu 12, 15, 10 a 3 spotřebitelé mají požadavky 8, 12 a 9. Jak upravíte

tuto dopr. úlohu na vybilancovaný tvar (určete konkrétní hodnoty pro tento příklad).

3 zdroje: 12 + 15 + 10 = 37; 3 spotřebitelé: 8 + 12 + 9 = 29

37 > 29 Þ vybilancovat Þ doplnit zákazníka 8

Další…

* Hodnota účelové funkce

9 spotřebitelů, 9 zdrojů, náklady na přiřazení jsou všude = 6 à přiřazovací úloha

à náklady = 6 * 9 = 54

* Nejdéle přípustný konec Tij = 10, délka trvání činnosti je tij = 6, jedná se o kritickou

činnost. Určete nejdříve možný začátek této činnosti.

Tij - tij = 10 - 6 = 4

* Sůl

A - 9g Þ XA

B - 5g Þ XB

9XA + 5XB £ 8 (XA + XB) ß méně než osm gramů soli v roztoku

* Vyřeš simplexem

max z = -2x1 - 3x2 + x3

ST x1 + 2x2 - x3 = 4

x1 + 2x2 - 2x3 ³ 0

x1 + 2x2 - 2x3 - x4 = 0

xij ³ 0

(0; 0; 0; x4; x5) simplex. tabulka i s pomocným řádkem

převod na kanonický tvar

min z = 2x1 + 3x2 - x3 - 0x4 + wx5

ST x1 + 2x2 - x3 + x5 = 4

-x1 + 2x2 + 2x3 + x4 = 0

 
 
2
3
-1
0
w
 
B
cB
x1
x2
x3
x4
x5
b
x4
0
1
2
-1
0
1
4
x5
w
-1
-2
2
-1
0
0
 
 
-w - 2
-2w - 3
2w + 1
w
-w
0

* Jak se vypočítá v nákladové analýze nejdelší doba trvání?

Þ při nejnižších nákladech, kdy se optimalizují zdroje

náklady ve 25 dnech Þ 37.000,-

jaká bude doba trvání při 57.000,-?

-cij = - 2.500

* Vybíráme 3 výrobky A, B, C

A - zisk 175,-x1

B - zisk 180,-x2

C - ztráta 70,-x3

a) maximalizuj zisk: max z = 175x1 + 180x2 - 70x3

b) vyrábíme 3x více C než A+Bx3 ³ 3*(x1 + x2)

* 5 automobilů A - 1000,- Þ x1

6 automobilů B - 1500,- Þ x2

4 automobily C - 2000,- Þ x3

a) napsat podmínky Þ více aut B než A + C

x2 > x1 + x3x2 - x1 - x3 > 0

b) co nejvíce aut vyrobit (ÚF)

max z = x1 + x2 + x3

c) můžeme půjčit pouze 2/3 aut z celku

x1 + x2 + x3 £ 10(2/3 z 15 Þ 10)

d) maximalizuj zisk

max z = 1000 x1 + 1500 x2 + 2000 x3

* 24 dní Þ 17.000,-

8 dní Þ 25.000,-

19 dní Þ ???

Nij = -Cij * tij + b

= ((17.000 - 25.000)/(24 - 8))*19 + (25.000 - (17.000 -25.000)/(24 - 8))*8 = 19.500,-

* Proměnná x vyjadřuje množství zboží, které chceme vozit ze skladu o kapacitě 400. Je

možné provést rozšíření kapacity skladu o 100 jednotek s náklady f1. Zvolte proměnnou

a zapište podmínku, která zabezpečí nepřekročení kapacity skladu.

x = množství rozvezeného zboží

x £ 400 + 100 y

y = 1 Þ sklad bude rozšířen

y = 0 Þ sklad nebude rozšířen

* Napište model úlohy. Určete souřadnice (x1, x2, x3) bodu, který patří tělesu

ohraničenému následující soustavou nerovností a leží nejblíže k bodu (10, 9, 8).

2x1 - x2 £ 6

x1 + x2 + x3 £ 6

xj £ 0; j = 1, 2, 3

* Mějme úlohu o batohu, kde počet předmětů je n = 4, kapacita batohu je k = 20,

hmotnost jednotlivých předmětů jsou po řadě 8, 4, 7, 9 jednotek a cena předmětů je po

řadě 12, 16, 8 a 15. Podle které proměnné začnete větvit při použití metody větví a

hranic (definujte použité proměnné) Þ x2

hmotnost8479

cena1216815

x3x1x4x2

12/8 = 1,5 Þ x3

16/4 = 4 Þ x1

8/7 = 1,16 Þ x4

15/9 = 1,66 Þ x2

(x1 = největší číslo, x4 = nejmenší číslo)

odečtení hmotnosti:

pro x120 - 4 = 16

pro x216 - 9 = 7

pro x37 - 8 = -1 Þ záporné číslo Þ větvím podle x3

(1, 1, 7/8, 0)

..

x3 = 0x3 = 1

(1, 1, 0, 1)(1, 1, 1, 0)

..

cena předmětů:1 * 16 + 1 * 15 + 1 * 12 + 0 * 8 = 43 Þ vyšší hodnota celočís. řešení

1 * 16 + 1 * 15 + 0 * 12 + 1 * 8 = 39

proměnné: 0 Þ nenaložím do batohu

1 Þ naložím do batohu

max z = 16 x1 + 15 x2 + 12 x3 + 8 x4

ST 4 x1 + 9 x2 + 8 x3 + 7 x4 £ 20 (podm. kapacity)

7/8 narušuje výsledek Þ neceločíselné řešení

* Určete výchozí neceločíselné řešení předchozí úlohy.

1 * 16 + 1 * 15 + 7/8 * 12 + 0 * 8 = 41,5

* Jsou-li zi I í0;1ý rozhodující proměnné, které nabývají hodnoty 1, jestliže zřídíme

středisko i s invest. N fi a jsou-li yijj I í0;1ý přiřazovací proměnné, které nabývají

hodnoty 1, jestliže budeme zákazníka j s požadavky bj obsluhovat ze střediska i s

neomezenou kapacitou, přičemž p je počet možných středisek a q je počet zákazníků,

zapište:

a) podmínku, vyjadřující, že ze střediska i nelze obsluhovat více než 4 zákazníky.

b) podmínku vyjadřující, že ze střediska i je třeba obsluhovat alespoň 1/4 součtu požadavků

všech zákazníků

c) ÚF pro min celk. invest. N

d) podm. vyjadřující, že budou splněny požadavky zákazníka k

e) podmínku vyjadřující, že nebude překročena kapacita střediska

* Načrtněte libovolný souvislý

a) neorientovaný graf s 5 vrcholy a 4 hranami

b) orientovaný graf s 5 vrcholy a 5 hranami, který obsahuje cyklus

* Známe model Þ určit alespoň jeden krajní bod.

max z = x1 + x2

ST2x1 - x2 + x4 = 6

x1 + x2 + x3 + x5 = 6

řešení (0, 0, 6, 6)