(Parte 1 de 6)

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 1

Método Simplex Prof. DSc. George Dantzig

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 2

Vimos que o modelo de programação linearreduz um sistema real a um conjunto de equações (ou inequações) onde pretendemos otimizar uma fun fun ç ão ão obj etivo obj etivo.

Como fazemos para resolver este problema ?

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 3

Veremos, um método capaz de realizar tal resolução:

Simplex Simplex!!!!!

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 4

Sabemos que a solução ótima (desde de que exista) seráencontrada num ponto extremo do conjunto das soluções viáveis.

Solução Exata para os Modelos de PL

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 5

Dificuldades:

O número de pontos extremos (vértices) é, em geral, exponencialmenteproporcional ao número de variáveis.

Solução Exata para os Modelos de PL

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 6

Dificuldades:

Para resolver um sistema indeterminado de equa equa ç ões ões lineares lineares (PPL na forma padrão), devemos:

Obter soluções básicas viáveispara o sistema.

Evitar o teste de todasas soluções básicas viáveis para garantir a otimização do sistema.

Solução Exata para os Modelos de PL

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 7

Soluç ão:

Usar o algoritmo simplex simplexque é...

Extremamente eficiente para a resolução do siste ma

Adaptávelao cálculo computacional

Solução Exata para os Modelos de PL

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 8

Algoritmo Simplex Algoritmo Simplex

Este algoritmo foi uma das grandes contribuições àProgramação Matemática ocorrida no século X.

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 9

Simplex Simplexé:

Um algoritmo que emprega ferramental da Álgebra Linear

Método iterativo Eficiente

Fundamentos Teóricos do

Simplex Simplex

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 10

A concepção geral do

Simplex Simplexéa seguinte:

Iniciar numa solução básica viável do sistemas de equações formado pelas restrições do PPL

(Parte 1 de 6)

Comentários