Algoritmos de Programação Linear

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