Práce je věnována metodám řešení standardních úloh lineárního programování. V teoretické části jsou popsány základní algoritmy pro řešení neceločíselných úloh. Všechny algoritmy jsou popsány nejdříve zcela obecně, nicméně pro jejich lepší pochopení neformálně. Následně jsou demonstrovány na příkladech, které jsou vypracovány dostatečně podrobně na to, aby byl případný čtenář schopen řešit obdobné úlohy samostatně. Ve zcela stejném duchu jsou pak popsány dvě základní metody pro řešení celočíselných úloh metoda Gomoryho řezů a metoda větví a mezí , které jsou založeny na znalosti jejich neceločíselných řešení.
Praktická část nabízí jednoduchý program s přívětivým uživatelským prostředí pro řešení úloh popsaných v teoretické části. Je určen jednak k řešení obdobných úloh, ale především ke kontrole samostatně řešených úloh, ať již neceločíselných, tak celočíselných.
Annotation in English
The bachelor thesis is devoted to methods of solving of standard linear programming problems. The theoretical part contains descriptions of basic algorithms for non-integer problems. All the algorithms are at first described generally, but in an informal way for the sake of simple understanding. Then they are demonstrated by examples, which are elaborated in such a detail, so that the reader should be able to solve similar problems individually. In a similar manner two of the basic methods for solving of integer problems Gomory's cut method and branch & bound method, which are based on the knowledge of their non-integer solutions are described.
The practical part presents a simple program with a user-friendly environment for solving of the problems described in the theoretical part. It is intended for solving of similar problems and mainly for checking of results of individually solved integer or non-integer problems.
Keywords
(celočíselné) lineární programování (ILP, LP), simplexový algoritmus, dualita, duální simplexový algoritmus, metoda Gomoryho řezů, metoda větví a mezí
Práce je věnována metodám řešení standardních úloh lineárního programování. V teoretické části jsou popsány základní algoritmy pro řešení neceločíselných úloh. Všechny algoritmy jsou popsány nejdříve zcela obecně, nicméně pro jejich lepší pochopení neformálně. Následně jsou demonstrovány na příkladech, které jsou vypracovány dostatečně podrobně na to, aby byl případný čtenář schopen řešit obdobné úlohy samostatně. Ve zcela stejném duchu jsou pak popsány dvě základní metody pro řešení celočíselných úloh metoda Gomoryho řezů a metoda větví a mezí , které jsou založeny na znalosti jejich neceločíselných řešení.
Praktická část nabízí jednoduchý program s přívětivým uživatelským prostředí pro řešení úloh popsaných v teoretické části. Je určen jednak k řešení obdobných úloh, ale především ke kontrole samostatně řešených úloh, ať již neceločíselných, tak celočíselných.
Annotation in English
The bachelor thesis is devoted to methods of solving of standard linear programming problems. The theoretical part contains descriptions of basic algorithms for non-integer problems. All the algorithms are at first described generally, but in an informal way for the sake of simple understanding. Then they are demonstrated by examples, which are elaborated in such a detail, so that the reader should be able to solve similar problems individually. In a similar manner two of the basic methods for solving of integer problems Gomory's cut method and branch & bound method, which are based on the knowledge of their non-integer solutions are described.
The practical part presents a simple program with a user-friendly environment for solving of the problems described in the theoretical part. It is intended for solving of similar problems and mainly for checking of results of individually solved integer or non-integer problems.
Keywords
(celočíselné) lineární programování (ILP, LP), simplexový algoritmus, dualita, duální simplexový algoritmus, metoda Gomoryho řezů, metoda větví a mezí
Uveďte formulace úlohy, typové příklady, matematické modely, proveďte klasifikace úloh lineárního programování (LP).
Formulujte kanonický tvar úloh LP,vysvětlete převod nerovnic na rovnice, bázické řešení a simplexovou tabulku.
Vysvětlete primární a duální úlohu LP, uveďte aspekty kombinované úlohy a celočíselnosti.
Analyzujte a aplikujte metodu řezných nadrovin a porovnejte s metodou větví a mezí.
Vypracujte a využijte programovou podporu pro řešení celočíselných úloh LP.
Vytvořte aplikační příklady využití celočíselných úloh LP.
Research Plan
Uveďte formulace úlohy, typové příklady, matematické modely, proveďte klasifikace úloh lineárního programování (LP).
Formulujte kanonický tvar úloh LP,vysvětlete převod nerovnic na rovnice, bázické řešení a simplexovou tabulku.
Vysvětlete primární a duální úlohu LP, uveďte aspekty kombinované úlohy a celočíselnosti.
Analyzujte a aplikujte metodu řezných nadrovin a porovnejte s metodou větví a mezí.
Vypracujte a využijte programovou podporu pro řešení celočíselných úloh LP.
Vytvořte aplikační příklady využití celočíselných úloh LP.
Recommended resources
GASS, Saul I. Linearne programovanie: metódy a aplikácie : príručka pre vysoké školy na Slovensku. preprac. vyd. Bratislava: Alfa, 1972, 397 s. Edícia elektrotechnickej literatúry (Alfa)
RYCHETNÍK, Luděk, Jan ZELINKA a Věra PELZBAUEROVÁ. Sbírka příkladů z lineárního programování. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1968, 314 s.
PLESNÍK, Ján, Jitka DUPAČOVÁ a Milan VLACH. Lineárne programovanie. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1990, 314 s. Edícia matematicko-fyzikálnej literatúry. ISBN 80-05-00679-9
GRYGAROVÁ, Libuše. Úvod do lineárního programování, skripta, Státní pedagogické nakladatelství, Praha 1975, 1. vydání, skripta
DUPÁČOVÁ, Jitka. Lineární programování, Státní pedagogické nakladatelství, Praha 1982, 1. vydání, skripta
JABLONSKÝ, Josef. Operační výzkum: kvantitativní modely pro ekonomické rozhodování. 1. vyd. Brno: Professional Publishing, 2002, 323 s. ISBN 80-86419-23-1
LINDA, Bohdan a Josef VOLEK. Lineární programování. Vyd. 3. Pardubice: Univerzita Pardubice, 2009, 139 s. ISBN 978-80-7395-207-5
Recommended resources
GASS, Saul I. Linearne programovanie: metódy a aplikácie : príručka pre vysoké školy na Slovensku. preprac. vyd. Bratislava: Alfa, 1972, 397 s. Edícia elektrotechnickej literatúry (Alfa)
RYCHETNÍK, Luděk, Jan ZELINKA a Věra PELZBAUEROVÁ. Sbírka příkladů z lineárního programování. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1968, 314 s.
PLESNÍK, Ján, Jitka DUPAČOVÁ a Milan VLACH. Lineárne programovanie. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1990, 314 s. Edícia matematicko-fyzikálnej literatúry. ISBN 80-05-00679-9
GRYGAROVÁ, Libuše. Úvod do lineárního programování, skripta, Státní pedagogické nakladatelství, Praha 1975, 1. vydání, skripta
DUPÁČOVÁ, Jitka. Lineární programování, Státní pedagogické nakladatelství, Praha 1982, 1. vydání, skripta
JABLONSKÝ, Josef. Operační výzkum: kvantitativní modely pro ekonomické rozhodování. 1. vyd. Brno: Professional Publishing, 2002, 323 s. ISBN 80-86419-23-1
LINDA, Bohdan a Josef VOLEK. Lineární programování. Vyd. 3. Pardubice: Univerzita Pardubice, 2009, 139 s. ISBN 978-80-7395-207-5
