Adding a Constraint to Mathematical Models of LP problems during manual calculation in branch and bound methods
Result description
In solving problems of linear programming (LP) where integer optimal solution is required is also possible to use simple combinatorial methods of Branch and bound based on dividing the feasible region of LP problem from which the integer requirement wasdropped, by newly created constraint added to the initial mathematical model until integer solution is found. Solving of these derived partial LP problems by simplex method is fully automatized thanks to computer technology. But this article involves theory of manual calculation procedures and answers questions in which phase of the calculation and in what form is the adding of the new constraint to the matrix of simplex tableau the most effective and how to convert it quickly as well.
Keywords
integer linear programmingmathematical model of the problemsimplex methodbranch and bound methodsstructure and artificial variablefeasible regionoptimal solution
The result's identifiers
Result code in IS VaVaI
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
čeština
Original language name
Doplnění vlastního omezení do matematického modelu úlohy LP při ručním výpočtu celočíselného řešení metodou větvení a mezí
Original language description
V úlohách lineárního programování, ve kterých je vyžadována celočíselnost nale- zeného optimálního řešení, je možné k jeho nalezení použít jednoduchou kombinatorickou metodu - metodu větvení a mezí. Je založena na dělení množiny přípustných řešení původní neceločíselné úlohy doplněním vhodně volených podmínek k původnímu matematickému modelu. Díky počítačové technice je řešení dílčích odvozených úloh simplexovou metodou automatizováno. Tento článek se ale věnuje teorii ručních výpočtů a postupů a zabýváse otázkou, v jaké fázi výpočtu a v jakém tvaru novou podmínku do matice simplexové tabulky efektivně doplnit, popř. jak ji dále upravovat.
Czech name
Doplnění vlastního omezení do matematického modelu úlohy LP při ručním výpočtu celočíselného řešení metodou větvení a mezí
Czech description
V úlohách lineárního programování, ve kterých je vyžadována celočíselnost nale- zeného optimálního řešení, je možné k jeho nalezení použít jednoduchou kombinatorickou metodu - metodu větvení a mezí. Je založena na dělení množiny přípustných řešení původní neceločíselné úlohy doplněním vhodně volených podmínek k původnímu matematickému modelu. Díky počítačové technice je řešení dílčích odvozených úloh simplexovou metodou automatizováno. Tento článek se ale věnuje teorii ručních výpočtů a postupů a zabýváse otázkou, v jaké fázi výpočtu a v jakém tvaru novou podmínku do matice simplexové tabulky efektivně doplnit, popř. jak ji dále upravovat.
Classification
Type
Jost - Miscellaneous article in a specialist periodical
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
—
Continuities
V - Vyzkumna aktivita podporovana z jinych verejnych zdroju
Others
Publication year
2014
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
LOGOS POLYTECHNIKOS
ISSN
1804-3682
e-ISSN
—
Volume of the periodical
5
Issue of the periodical within the volume
3
Country of publishing house
CZ - CZECH REPUBLIC
Number of pages
14
Pages from-to
15-28
UT code for WoS article
—
EID of the result in the Scopus database
—
Result type
Jost - Miscellaneous article in a specialist periodical
OECD FORD
Pure mathematics
Year of implementation
2014