Wikipédia

Programação linear: diferenças entre revisões

Explorar interativamente o histórico
← Ver a alteração anteriorVer a alteração posterior →
Conteúdo apagado Conteúdo adicionado
VisualTexto wiki
Clara C. (discussão | contribs)
28 942 edições
m
Pecorajr (discussão | contribs)
30 edições
Linha 45:
 
Entretanto, a performance prática do algoritmo de Khachiyan é desapontadora: geralmente, o método simplex é mais eficiente. Sua grande importância é que ele encoraja a pesquisa de [[interior point method]]s. Ao contrário de algoritmo simplex, que apenas evolui ao longo de pontos na fronteira da região factível, métodos de ponto interior podem se mover pelo interior da região factível.
<!--▼
In [[1984]], [[Narendra Karmarkar|N. Karmarkar]] proposed the [[projective method]]. This is the first algorithm performing well both in theory and in practice: Its worst-case complexity is polynomial and experiments on practical problems show that it is reasonably efficient compared to the simplex algorithm. Since then, many interior point methods have been proposed and analysed. A popular interior point method is the [[Mehrotra predictor-corrector method]], which performs very well in practice even though little is known about it theoretically.▼
 
==Variáveis Inteiras ==
The current opinion is that the efficiency of good implementations of simplex-based methods and interior point methods is similar for routine applications of linear programming. ▼
 
Se todas as variávies do problema pertencenrem ao conjunto dos números inteiros, temos uma sub-classe da Programação Linear chamada [Programação Inteira] (PI) ou programação linear inteira. Ao contrário, da PL que pode-se encontrar a solução ótima em um tempo razoável, muitos problemas de Programação Inteira são considerados [[NP-dificel]]. Se as variáveis forem binárias, ou seja, assumirem somente os valore 0 (zero) ou 1, temos um caso especial da PI, que também pode ser classificado como [[NP-dificel]].
LP solvers are in widespread use for optimization of various problems in industry, such as optimization of flow in transportation networks, many of which can be transformed into linear programming problems only with some difficulty.▼
 
Quanto somente algumas das variáveis são inteiras e outras permanecendo contínuas, temos a "Programação Inteira Mista" (PIM).
==Integer unknowns==
 
Existem no entando algumas classes de problemas que podem ser resolvidos na otimalidade em tempo polinomial, estes têm uma estrutural matricial própria chamada [[Matrizes totalmente unimodular]].
If the unknown variables are all required to be integers, then the problem is called an '''integer programming''' (IP) or '''integer linear programming''' (ILP) problem. In contrast to linear programming, which can be solved efficiently in the worst case, integer programming problems are in the worst case undecidable, and in many practical situations (those with bounded variables) [[NP-hard]]. '''0-1 integer programming''' is the special case of integer programming where variables are required to be 0 or 1 (rather than arbitrary integers). This method is also classified as [[NP-hard]], and in fact the decision version was one of [[Karp's 21 NP-complete problems]].
 
Alguns algorithmos aplicados com sucesso na PI são:
If only some of the unknown variables are required to be integers, then the problem is called a '''mixed integer programming''' (MIP) problem. These are generally also [[NP-hard]].
 
There are however some important subclasses of IP and MIP problems that are efficiently solvable, most notably problems where the constraint matrix is [[totally unimodular]] and the right-hand sides of the constraints are integer.
 
Advanced algorithms for solving integer linear programs include:
* [[branch and bound]]
* [[branch and cut]]
* [[branch and price]]
* Se a estrutura do problema permitir é também possivel se aplicar um algorithmo de [[geração de colunas]]
* if the problem has some extra structure, it may be possible to apply [[delayed column generation]].
 
▲<!--
▲In [[1984]], [[Narendra Karmarkar|N. Karmarkar]] proposed the [[projective method]]. This is the first algorithm performing well both in theory and in practice: Its worst-case complexity is polynomial and experiments on practical problems show that it is reasonably efficient compared to the simplex algorithm. Since then, many interior point methods have been proposed and analysed. A popular interior point method is the [[Mehrotra predictor-corrector method]], which performs very well in practice even though little is known about it theoretically.
 
▲The current opinion is that the efficiency of good implementations of simplex-based methods and interior point methods is similar for routine applications of linear programming.
 
▲LP solvers are in widespread use for optimization of various problems in industry, such as optimization of flow in transportation networks, many of which can be transformed into linear programming problems only with some difficulty.
 
-->
 
==Veja também==
*[[Preço sombra]]
Obtida de "https://pt.wikipedia.org/wiki/Programação_linear"