Prefácio |
Sumário |
Bibliografia |
WWW |
Software |
English
Sumário do livro
Algoritmos de Programação Linear
- Preliminares
- cap. 1 Vetores e Matrizes
- Parte I: Algoritmos Básicos
- cap. 2 Algoritmo de Gauss-Jordan
- cap. 3 Introdução ao Simplex
- cap. 4 Heurística Simplex
- cap. 5 Algoritmo Simplex
- cap. 6 Forma tradicional do Simplex
- Parte II: Programação Linear
- cap. 7 Problema canônico primal
- cap. 8 Problema canônico dual e dualidade
- cap. 9 Problema geral de programação linear
- Parte III: Algoritmos para Dados Inteiros
- cap. 10 Determinantes
- cap. 11 Algoritmo de Gauss-Jordan-Edmonds
- cap. 12 Algoritmo Simplex-Edmonds
- cap. 13 Problemas com dados inteiros
- Parte IV: Algoritmos Polinomiais
- cap. 14 Introdução aos algoritmos polinomiais
- cap. 15 Algoritmo de Yamnitsky-Levin
- Apêndices
- ap. A Simplex Dual
- ap. B Análise de sensibilidade
- ap. C Poliedro canônico primal
- ap. D Poliedro canônico dual
- ap. E Exercícios resolvidos
- Referências Bibliográficas
-
- Índice Remissivo
-
Sumário detalhado
- cap. 1 Vetores e Matrizes
- Vetores
- Matrizes
- Produtos
- Matrizes inversíveis
- Transposição
- Matrizes de bijeção
- Matrizes diagonais
- Matrizes elementares
- Combinações lineares
- cap. 2 Algoritmo de Gauss-Jordan
- Matrizes escalonadas
- Esboço do algoritmo
- Algoritmo
- Análise do algoritmo: invariantes
- Mais invariantes
- Número de operações aritméticas
- Conclusão
- Aplicação: Sistemas de equações
- cap. 3 Introdução ao Simplex
- Matrizes simples
- Matriz simples solúvel
- Matriz simples inviável
- Matriz simples ilimitada
- Esboço do Simplex
- A estrutura de casos
- Nossa linguagem algorítmica
- Terminologia tradicional
- Análise
- Convergência
- cap. 4 Heurística Simplex
- Introdução
- Simplex
- Análise: invariantes
- Mais três invariantes
- Convergência
- Conclusão
- Apêndice: Simplex Revisto
- cap. 5 Algoritmo Simplex
- Ordem lexicográfica
- Regra lexicográfica
- Algoritmo
- Análise
- Convergência
- Número de operações aritméticas
- Conclusão
- Apêndice: Segunda fase do Simplex
- Apêndice: Regra de Bland
- cap. 6 Forma tradicional do Simplex
- Sistemas matriz-vetor-vetor
- Algoritmo Simplex
- Conclusão
- cap. 7 Problema canônico primal
- Definição do problema
- Problemas solúveis, inviáveis e ilimitados
- Observação sobre terminologia
- Problemas simples
- Problema simples inviável
- Problema simples solúvel
- Problema simples ilimitado
- Algoritmo baseado no Simplex
- Conclusão
- Exemplo
- cap. 8 Problema canônico dual e dualidade
- Definição do problema
- Problemas solúveis, inviáveis e ilimitados
- Lema da dualidade
- Folgas complementares
- Vetores de inviabilidade
- Algoritmo baseado no Simplex
- Teorema da dualidade
- Conclusão
- Uma interpretação do Simplex
- Apêndice: Problema do vetor viável
- cap. 9 Problema geral de programação linear
- Definição do problema
- Dualidade
- Lema da dualidade
- Construção do dual
- Teorema da dualidade
- Redução ao problema canônico primal
- Conclusão
- Apêndice: Interpretação do dual
- cap. 10 Determinantes
- Sinal de uma matriz de permutação
- Determinante de matriz quadrada
- Três propriedades básicas
- Determinante do produto de matrizes
- Delimitação do determinante
- Conclusão
- cap. 11 Algoritmo de Gauss-Jordan-Edmonds
- Algoritmo
- Análise básica
- Propriedade fundamental
- Delimitação dos números gerados
- Aplicação a matrizes inteiras
- Eficiência
- Matrizes totalmente unimodulares
- Conclusão
- cap. 12 Algoritmo Simplex-Edmonds
- Algoritmo
- Análise
- Aplicação a matrizes inteiras
- Conclusão
- cap. 13 Problemas com dados inteiros
- Sistemas de equações
- Matrizes totalmente unimodulares
- Problemas canônicos
- Matrizes totalmente unimodulares
- Conclusão
- cap. 14 Introdução aos algoritmos polinomiais
- Problemas CD, PV, V e PI
- Redução do CD ao PV
- Redução do PV ao V
- Redução do V ao PI
- Conclusão
- cap. 15 Algoritmo de Yamnitsky-Levin
- Definições básicas
- Tetraedros e seus volumes
- Teorema do tetraedro interior
- Algoritmo
- Invariantes
- O algoritmo está bem definido
- Última iteração
- Demonstração dos invariantes
- Número de iterações
- Número de operações aritméticas
- Conclusão
- Apêndice: Matriz com uma só linha
- ap. A Simplex Dual
- Matrizes simples no sentido dual
- Esboço do Simplex Dual
- Heurística Simplex Dual
- Algoritmo Simplex Dual
- Problema canônico dual
- Sistemas duais simples
- Sistemas duais arbitrários
- ap. B Análise de sensibilidade
- Variação de um só componente
- Exemplo
- Valor ótimo em função de b e c
- Conclusão
- ap. C Poliedro canônico primal
- Dependência linear
- Combinações convexas
- Vértices
- Soluções do problema canônico primal
- Poliedros limitados
- ap. D Poliedro canônico dual
- Conjuntos geradores
- Combinações convexas
- Vetores básicos e faces minimais
- Soluções do problema canônico dual
- Poliedros limitados
- ap. E Exercícios resolvidos
-