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

Identificar novas soluções viáveis melhores ou iguaisà cor rente

Identificar se uma dada solução viável é, ou não, um vértice ótimo

Fundamentos Teóricos do

Simplex Simplex

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 1

Otimizar [Max/Min] Q(X) = Σcj.x

n j sujeito a n

Σ a ij

i = 1, 2,, m
≥0j = 1, 2,, n
M = {1, 2,, m }, o conjunto dos índices das

xj restrições

N = {1, 2,, n }, conjunto dos índices das variáveis

Formulação Algébrica Geral

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 12

–Forma Canônica –Forma Padrão

–Forma Matricial

For mulações Equivalentes

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 13

Padrão Padrão

Canôni ca Canôni ca

Matricial Matricial

Todas as formulações são equivalentes !

For mulações Equivalentes

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 14

Otimizar [MIN]Q(X) = C.X sujeito a

Forma Padrão

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 15

Qualquer PPL pode ser escrito numa das formas anteriores por meio das seguintes operações:

Opera Operaçç ão 1 ão 1: Mudança de critério de otimização

Maximizar Q(X)

Minimizar - Q(X)

Mini mizar Q(X)

Maximizar - Q(X)

Operações Ele mentares

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 16

Opera Operaçç ão 2 ão 2: Transformação de termo independente negativo b i

Basta multiplicar toda a restrição por –1.

Operações Ele mentares

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 17

Opera Operaçç ão 3 ão 3: Transformação de desigualdades em igualdades (e vice-versa)

++ x

≤ ≤b (inequação original)

++ xn

+ x

Variável de folga

Operações Ele mentares

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 18

Opera Operaçç ão 4 ão 4: Transformação de desigualdades em igualdades (e vice-versa)

++ x

≥ ≥b (inequação original)

++ xn

Variável de excesso

Operações Ele mentares

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 19

Opera Operaçç ão 5 ão 5: Transformação de uma variável livre em variável não-negativa, ou seja, uma variável ésubstituída por duas variáveis auxiliares, ambas positivas xn = x

X n

Operações Ele mentares

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 20

Opera Operaçç ão 6 ão 6: Transformação de uma variável negativa em variável não-negativa, ou seja, uma variável ésubstituída por uma auxiliar, positiva x n

Operações Ele mentares

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 21 sujeito a

Exemplo 1

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 2 sujeito a

Exemplo 1

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 23

Multiplicar a restrição -x1 - 2x

Adicionar uma variável de excesso, x3 :

Exemplo 1

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 24

Introduzir uma variável de excessoem x1 + x

Exemplo 1

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 25

Forma Padrão Forma Padrão --

Min Min) sujeito a

Exemplo 1

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 26

2

Forma Padrão Forma Padrão --

Max Max) sujeito a

Exemplo 1

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 27

Obtenha a forma padrão associada:

sujeito a

2x 1 + 3x

Exercício

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 28

s. a

A éa matriz dos coeficientesdas variáveis nas restrições

Xéa matriz das variáveis (coluna)

Céa matriz dos coeficientes das variáveis na FO(linha) Béa matriz dos termos independentes

Forma Matricial

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 29

Escreva a forma padrão abaixo na notação matricial.

s. a

Exemplo 1

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 30

s. a A . X = B

Exemplo 1 x x

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 31

Exemplo 1 x x

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 32

Exemplo 1 x x

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 3

Exercício

Escreva a forma matricial associada a forma padrão obtida no exercício anterior.

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 34

Método Simplex

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 35

Resolva o seguinte PPL por meio do emprego do Método Simplex:

MaxQ(X) = 5x1 + 3x s.a

Exemplo 1

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 36

Visualizando Grafica mente

Região Viável

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 37

Max Q(X) = -5x1-3x 2 s.a

5x1+ 2x 2

1) Obter Forma Padrão

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 38

2) Colocar o PPL no Quadro Simplex

Variáveis

Restrições

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 39

3) Determinar as variáveis básicas e uma solução básica viável inicial

Básicas

Variáveis básicas são aquelas cujas colunas têm 1 numa posição e 0 nas demais.

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 40

No Simplex as Variáveis Não Básicas (VNB) sempre valem 0:

Logo, as Variáveis Básicas (VB) valem: x3 = 15; x4

Corresponde ao vértice A (0,0,15,10).

Valor da função objetivo (F.O.) nesta base:

+ 0.x

4 = -5 . 0 -3 . 0 + 0 . 15 + 0 . 10 = 0

3) Determinar as variáveis básicas e uma solução básica viável inicial

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 41

Visualizando Grafica mente

Região Viável

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 42

4) Essa solução éótima?

Este quadro não éótimo pois existem variáveis com coeficientes negativos na linha da FO.

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 43

Fazendo uma mudança de base. Para isso precisamos definir quem entra e quem sai da base.

5) Como encontrar um novo vértice?

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 4

Qual, entre as variáveis não básicas, deve entrarpara a base ?

Resposta:

Deve entrar para a base a variável que possuir o COEFICIENTE MAIS NEGATIVO na linha da FO.

Se duas ou mais variáveis têm o mesmo coeficiente negativo, você pode escolher qualquer uma delas.

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 45

Resposta (continuação):

Se todas as variáveis tiverem coeficientes positivos então atingimos o ponto de ÓTIMOda função objetivo e, conseqüentemente, o processo do Método Simplexchegou ao seu final.

Os valores assumidos pelas variáveis são os que corresponderão ao ótimoda F.O.

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 46

X1 entra na base pois éa que tem o coeficiente mais negativo na linha da FO.

5.1) Quem entra na base?

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 47

5.2) Quem sai da base?

Resposta:

Deve sair da base a variável cujo coeficiente RHS (termo independente), em relação àvariável que estáentrando para a base, for MÍNIMO.

O coeficiente RHSsomente pode ser calculado se o mesmo for resultar em número positivo pois caso contrário teremos uma inconsistência ou seja uma variável assumindo um valor ne gativo.

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 48

3x

Min {15/3,10/5} = 10/5, logo x4 sai da base

5.2) Quem sai da base?

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 49

Denominamos de pivôao elemento que se encontra na interseção entre a linhada variável que irásairda base e a coluna da variável que deveráentrarpara a base ou ao denominador do menor quociente. Na linha do pivô temos a variável que deixa a ba se.

Assim temos que...

5.3) Determinando o elemento pivô da base atual

Pesquisa Operacional

Prof. Luciano Lessa Lorenzoni 50

5.3) Determinando o elemento pivô da base atual

Elemento pivô 5

Comentários