Klasifikace celociselnych uloh programovani

1) Ryze celociselne ulohy- rozdeluje ulohy na

- ulohy s obecnymi podminkami celociselnosti

- bivalentni ulohy

2) Smisene celociselne ulohy - vychází z toho, zda jsou kladeny podminky celociselnosti na všechny promenne modelu nebo pouze na jejich podmnožinu

Ulohy s obecnými podmínkami celočíselnosti:

- Ulohy výrobního planovani (promenne x1,x2,x3,x4 vyjadrujut počet kusu stolu a zidli ve vyrobnim programu)

- Ulohy rozvrhovani vyroby

- Ulohy o deleni materialu

- Nutriční problem

Ulohy s binárními (bivalentními) proměnnými: prirazovaci, pokryvaci a okružní dopravni problem.
Grafy

Grafy – útvary, které lze znázornit pomocí bodů (uzlů) a spojnic (hran) mezi nimi. Hrany mohou být buď orientované (s vyznačeným směrem pohybu) nebo neorientované (hrany umožňující oboustranný pohyb mezi dvěma uzly).

Základní typy grafů:

• Neorientovaný graf – graf pouze s neorientovanými hranami
• Orientovaný graf – graf, který obsahuje i orientované hrany

Další typy grafů:

• Souvislý graf– graf, kde je mezi libovolnou dvojicí uzlů nějaká neorientovaná cesta
• Hranově (uzlově) ohodnocený graf– graf, ve kterém jsou všechny hrany (uzly) ohodnocené
• Síťový graf– orientovaný, nezáporně ohodnocený a souvislý graf s jediným vstupním a jediným výstupním uzlem
• Strom– souvislý, neorientovaný graf, který neobsahuje žádny cyklus.

Typy cest v grafu (cesta v grafu = navzájem na sebe navazující posloupnost hran):

• Orientovaná cesta – cesta v orientovaném grafu, která respektuje orientaci hran
• Neorientovaná cesta – cesta v orientovaném grafu, která nerespektuje orientaci hran
• Cyklus – cesta, která začíná a končí ve stejném uzlu

Nejkratší cesta –cesta mezi dvojicí uzlů s minimální délkou.

Optimální spojení míst = minimální kostra grafu – tj. podgraf původního grafu zahrnující všechny uzly, který bude stromem a bude mít minimální součet ohodnocení hran, které tento strom tvoří.

Optimální toky v grafu – výchozí uzel produkuje nějaké jednotky a výstupní uzel je cílovým místem, ohodnocení hran představuje max. propustnost hrany, cíl je zajistit maximální propustnost sítě tak, aby byly respektovány propustnosti hran (maximální tok= maximální objem toku, který může vstoupit do sítě a projít sítí do výstupního uzlu během daného časového intervalu).

Řízení projektů

Date: 2016-01-03; view: 823