Diferenças entre edições de "Programação linear"

991 bytes removidos ,  11h20min de 19 de setembro de 2005
==Variáveis Inteiras ==
 
Se todas as variávies do problema pertencenrempertencerem 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 valorevalores 0 (zero) ou 1, temos um caso especial da PI, que também pode ser classificado como [[NP-dificel]].
 
QuantoQuando somente algumas das variáveis são inteiras e outras permanecendo contínuas, temos a "Programação Inteira Mista" (PIM).
 
Existem no entando algumas classes de problemas que podem ser resolvidos na otimalidade em tempo polinomial, estes têm uma estruturalestrutura matricial própria chamada [[Matrizes totalmente unimodular]].
 
Alguns algorithmosalgoritmos aplicados com sucesso na PI são:
* [[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]]
 
<!--
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==
30

edições