Faculdade de Engenharia - Campus de Guaratinguetá
Pesquisa Operacional
Livro: Introdução à Pesquisa Operacional
Capítulo 2 - Programação Linear
Fernando Marins – [email protected]
Departamento de Produção
1
Sumário
• Modelagem e limitações da Programação Linear.
• Resolução Gráfica.
• Forma padrão de um modelo de Programação Linear.
• Definições e Teoremas.
• Forma canônica de um sistema de equações lineares.
• Método Simplex.
• Exercícios
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
2
Programação Linear
Programação Linear:
Preocupação em encontrar a melhor solução para problemas
associados com modelos lineares.
Modelo de Programação Linear:
Maximização (ou minimização) de uma função objetivo linear com
relação as variáveis de decisão do modelo.
Respeitando-se as limitações (restrições) do problema expressas por
um sistema de equações e inequações associadas com as variáveis de
decisão do modelo.
3
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Razões para o uso da Programação Linear:
1. Grande variedade de situações podem ser aproximadas por
modelos lineares.
2. Existência de técnicas (algoritmos) eficientes para a solução
de modelos lineares.
3. Possibilidade de realização de análise de sensibilidade nos
dados do modelo.
4. Estágio de desenvolvimento da tecnologia computacional.
4
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Passos básicos na obtenção de modelos de PL:
1. Identificar as variáveis de decisão, representá-las em simbologia
algébrica.
2. Identificar as restrições do problema, expressá-las como
equações ou inequações lineares em termos das variáveis de
decisão.
3. Identificar o objetivo de interesse no problema, representá-lo
como função linear em termos das variáveis de decisão, que
deverá ser maximizada ou minimizada.
5
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Construção de modelos não é uma ciência, mas uma
arte, podendo ser melhorada com a prática.
Exemplos a serem trabalhados:
Determinação do mix de produção
Seleção de mídia para propaganda
Um problema de treinamento
Uma indústria química
Uma oficina mecânica
Dimensionamento de equipes de inspeção
6
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Determinação do mix de produção
Uma companhia deseja programar a produção de um utensílio de cozinha
que requer o uso de dois tipos de recursos – mão-de-obra e material. A
companhia está considerando a fabricação de três modelos e o seu
departamento de engenharia forneceu os dados a seguir:
O suprimento de material é de
Modelo
200
kg
por
dia.
A
A
B
C
disponibilidade diária de mãode-obra é 150 horas. Formule
Mão-de-obra
7
3
6
um modelo de Programação
(horas por unidade)
Linear para determinar a
Material
4
4
5
produção diária de cada um dos
(kg por unidade)
modelos de modo a maximizar
Lucro
4
2
3
o lucro total da companhia.
($ por unidade)
7
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Formulação do modelo
1. Identificação das variáveis de decisão:
XA – produção diária do modelo A
XB – produção diária do modelo B
XC – produção diária do modelo C
2. Identificação das restrições:
(Limitação de mão-de-obra)
(Limitação de material)
(Não-negatividade)
7XA + 3XB + 6XC  150
4XA + 4XB +5XC  200
XA  0, XB 0, XC  0.
3. Identificação do objetivo: maximização do lucro total
Lucro Total = L = 4XA + 2XB +3XC
Max L = 4XA + 2XB +3XC
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
8
Modelagem em Programação Linear
Modelo
Encontrar números XA, XB, XC tais que:
Max L= 4XA + 2XB +3XC
Sujeito as restrições:
7XA + 3XB +6XC  150
4XA + 4XB +5XC  200
XA  0, XB 0, XC  0
9
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Seleção de mídia para propaganda
Uma companhia de propaganda deseja planejar uma campanha em 03
diferentes meios: TV, rádio e revistas. Pretende-se alcançar o maior
número de clientes possível. Um estudo de mercado resultou em:
TV
horário
TV
horário
Rádio
Revistas
normal
nobre
Custo
40.000
75.000
30.000
15.000
Clientes
Atingidos
400.000
900.000
500.000
200.000
Mulheres
Atingidas
300.000
400.000
200.000
100.000
0bs: valores válidos para cada veiculação da propaganda.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
10
Modelagem em Programação Linear
A companhia não quer gastar mais de $ 800.000 e, adicionalmente,
deseja:
(1) Que no mínimo 2 milhões de mulheres sejam atingidas;
(2) Gastar no máximo $ 500.000 com TV;
(3) Que no mínimo 03 veiculações ocorram no horário normal TV;
(4) Que no mínimo 02 veiculações ocorram no horário nobre TV;
(5) Que o nº. de veiculações no rádio e revistas fiquem entre 05 e 10, para
cada meio de divulgação.
Formular um modelo de PL que trate este problema,
determinando o nº. de veiculações a serem feitas em cada meio de
comunicação, de modo a atingir o máximo possível de clientes.
11
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Resolução do exemplo “seleção de mídia para propaganda”
Variáveis de decisão:
X1 = nº. de exposições em horário normal na tv.
X2 = nº. de exposições em horário nobre na tv.
X3 = nº. de exposições feitas utilizando rádio
X4 = nº. de exposições feitas utilizando revistas.
Função-objetivo:
“Maximizar nº. de clientes atingidos”
Max Z = 400.000X1 + 900.000X2 + 500.000X3 + 200.000X4
12
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Restrições:
Orçamento:
40.000X1 + 75.000X2 + 30.000X3 + 15.000X4  800.000
Mulheres atingidas:
300.000X1 + 400.000X2 + 200.000X3 + 100.000X4  2.000.000
Gasto com TV
40.000X1 + 75.000X2  500.000
Nº. de veiculações em TV, rádio e revistas
X1  3, X2  2, 5  X3  10, 5  X4  10
Não-negatividade
X1, X2, X3, X4  0.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
13
Modelagem em Programação Linear
Um problema de treinamento
Uma empresa de máquinas ferramentas tem um programa
de treinamento para operadores de máquinas. Alguns operadores
já treinados podem trabalhar como instrutores neste programa
ficando responsáveis por 10 trainees cada. A empresa pretende
aproveitar apenas 07 trainees de cada turma de 10.
Estes operadores treinados também são necessários na
linha de fabricação, e sabe-se que serão necessários para os
próximos meses: 100 operadores em janeiro, 150 em fevereiro,
200 em março, e 250 em abril. Atualmente há 130 operadores
treinados disponíveis na empresa.
14
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Os custos associados a cada situação são:
Trainees ...........................................................................$ 400.
Operador treinado trabalhando ........................................$ 700.
Operador treinado ocioso..................................................$ 500.
Encontrar um modelo de PL que forneça um programa de
treinamento de custo mínimo e satisfaça os requisitos da empresa
em termos de nº. de operadores treinados disponíveis a cada mês.
Observação: acordo firmado com o sindicato proíbe demissões de
operadores treinados no período.
15
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Resolução do exemplo: Um problema de treinamento
Observe que a cada mês um operador treinado está: operando
máquina, trabalhando como instrutor, ou está ocioso. Além disto, o
nº. de operadores treinados trabalhando nas máquinas é fixo e
conhecido: 100 em janeiro, 150 em fevereiro, 200 em março e 250
em abril.
Variáveis de decisão:
X1 = operadores trabalhando como instrutores em janeiro
X2 = operadores ociosos em janeiro
X3 = operadores trabalhando como instrutores em fevereiro
X4 = operadores ociosos em fevereiro
X5 = operadores trabalhando como instrutores em março
X6 = operadores ociosos em março
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
16
Modelagem em Programação Linear
Função-objetivo:
“Custo total = custo trainees + custo instrutores + custo ociosos +
custo operadores trabalhando em máquinas”.
Min C = 400(10X1 + 10X3 + 10X5) + 700(X1 + X3 + X5) +
+ 500(X2 + X4 + X6) + 700(100 + 150 + 200)
Min C = 4700X1 +500X2 + 4700X3 +500X4 +4700X5 +500X6 + 315.000
17
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Restrições: X1, X2, X3, X4, X5, X6  0 (não-negatividade)
Equação de balanço mensal:
operadores treinados no início do mês = operadores nas máquinas
+ instrutores + operadores ociosos.
Janeiro: 130 = 100 + X1 + X2  X1 + X2 = 30
Fevereiro: 130 + 7X1 = 150 + X3 + X4  7X1 - X3 - X4 = 20
Março: 130 + 7X1 + 7X3 = 200 + X5 + X6  7X1 + 7X3 - X5 - X6 = 70
Abril: 250 = 130 + 7X1 + 7X3 + 7X5  7X1 + 7X3 + 7X5 = 120.
18
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Uma indústria química
Dois produtos, A e B, são feitos a partir de duas operações
químicas. Cada unidade do produto A requer 02 horas da operação 1 e 03
horas da operação 2. Cada unidade do produto B requer 03 horas da
operação 1 e 04 horas da operação 2. O tempo total disponível para a
realização da operação 1 é de 16 horas, e o tempo total para a operação 2
é de 24 horas.
A produção do produto B resulta, também, num subproduto C
sem custos adicionais. Sabe-se que parte do produto C pode ser vendido
com lucro, mas o restante deve ser destruído. Previsões mostram que no
máximo 05 unidades do produto C serão vendidas, e sabe-se que cada
unidade do produto B fabricada gera 02 unidades do produto C.
19
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Sabe-se que:
Produto A gera um lucro de $ 4 por unidade.
Produto B gera um lucro de $ 10 por unidade.
Produto C gera um lucro de $ 3 por unidade se for vendido.
Produto C gera um custo de $ 2 por unidade se for destruído
Determinar um modelo de PL para tratar este problema, e
encontrar quanto produzir de cada produto, de modo a maximizar
o lucro da indústria química.
20
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Resolução do exemplo: Uma indústria química - produto A
Observe que o lucro da venda do produto A é uma função linear,
mas com respeito ao produto C isto não ocorre.
Produto B
Produto A
Lucro
Produto C
Lucro
10
4
-2
3
5
Quantidade
Quantidade
21
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Artifício: considerar as variáveis de decisão como sendo
X1 = quantidade produto A produzida
X2 = quantidade produto B produzida
X3 = quantidade produto C vendida
X4 = quantidade produto C destruída
Função-objetivo:
Max Z = 4 X1 + 10 X2 + 3 X3 – 2 X4
Restrições:
2 X1 + 3 X2  16 (disponibilidade de tempo para operação 1)
3 X1 + 4 X2  24 (disponibilidade de tempo para operação 2)
X3 + X4 = 2 X2 (produção do produto C a partir do produto B)
X3  5 (previsão de produto C que pode ser vendido)
X1, X2, X3, X4  0 (não-negatividade)
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
22
Modelagem em Programação Linear
Oficina mecânica
Uma oficina mecânica tem 01 furadeira vertical e 05 fresas,
que são usadas para a produção de conjuntos formados de 2 partes.
Sabe-se qual é a produtividade de cada máquina na fabricação destas
partes do conjunto:
Furadeira
Fresa
Parte 1
03
20
Parte 2
05
15
Obs: tempo para produzir as partes dado em minutos.
23
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
O encarregado pela oficina deseja manter uma carga balanceada
nas máquinas de modo que nenhuma delas seja usada mais que 30
minutos por dia que qualquer outra, sendo o carregamento de
fresamento dividido igualmente entre as 05 fresas.
Achar um modelo de PL para dividir o tempo de trabalho entre as
máquinas de modo a obter o máximo de conjuntos completos ao
final de um dia, num total de 08 horas de trabalho.
24
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Resolução do exemplo: Oficina mecânica
Variáveis de decisão:
X1 = número de partes 1 produzidas por dia
X2 = número de partes 2 produzidas por dia
Restrições:
3X1 + 5X2  480
(minutos por dia disponíveis para a furadeira)
(20X1 + 15X2)/5 = 4X1 + 3X2  480
(minutos por dia disponíveis para cada fresa)
25
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
|(4X1 + 3X2) - (3X1 + 5X2)| = |X1 -2X2|  30
(Balanceamento de carga entre as máquinas)
Observe que esta última restrição não é linear, mas é equivalente
a duas equações lineares que podem substituí-la:
X1 - 2X2  30
e
-X1 + 2X2  30
X1, X2  0 (não-negatividade).
26
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Função-objetivo:
“maximização do número de conjuntos completos por dia”
Max Z = min (X1, X2)
Observe que esta função não é linear, mas pode ser linearizada
utilizando-se uma nova variável, da forma:
Seja Y = min (X1, X2), Y  0, naturalmente tem-se duas novas
restrições
Dadas por: Y  X1 e Y  X2.
A função-objetivo linear fica sendo: Max Z = Y
27
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Problema de dimensionamento de equipes de inspeção
Uma companhia deseja determinar quantos inspetores alocar
à uma dada tarefa do controle da qualidade. As informações
disponíveis são:
Há 08 inspetores do nível 1 que podem checar as peças a
uma taxa de 25 peças por hora, com uma acuracidade de 98%, sendo
o custo de cada inspetor deste nível $4 por hora;
Há 10 inspetores do nível 2 que podem checar as peças a
uma taxa de 15 peças por hora, com uma acuracidade de 95%, sendo
o custo de cada inspetor deste nível $3 por hora.
28
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
A companhia deseja que no mínimo 1800 peças sejam
inspecionadas por dia (= 08 horas).
Sabe-se, ainda, que cada erro cometido por inspetores no controle
da qualidade das peças acarreta um prejuízo à companhia de $2 por
peça mal inspecionada.
Formular um modelo de PL para possibilitar a designação ótima do
nº. de inspetores de cada nível de modo a otimizar o custo da
inspeção diária da companhia.
29
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Resolução do exemplo: Dimensionamento de equipes de inspeção
Variáveis de decisão:
Xi = nº. de inspetores do nível i (= 1, 2) alocados à inspeção.
Função objetivo:
Minimizar C = custo total diário de inspeção ($/dia)
onde : custo total = custo do salário dos inspetores + custo dos erros
Min C = 8 *[(4X1 + 3X2) + 2 * (25*0,02X1 + 15*0,05X2)]
Min C = 40X1 + 36X2
30
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelagem em Programação Linear
Restrições:
1. Quanto ao nº. de inspetores disponíveis:
X1  8
(inspetores do nível 1)
X2  10
(inspetores do nível 2)
2. Quanto ao nº. de peças inspecionadas por dia:
8 * (25X1 + 15X2)  1800

5X1 + 3X2  45
3. Restrições implícitas de não negatividade:
X1  0
X2  0.
31
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Resolução gráfica de modelos de PL
Aplicável para modelos com 02 variáveis de decisão
Útil para a ilustração de alguns conceitos básicos utilizados na
resolução de modelos de maior porte.
Etapas a serem seguidas na resolução gráfica
1º Passo: identificar a região viável do modelo, isto é, quais são os
pares (X1, X2) que satisfazem a todas as restrições.
2º Passo: achar a melhor solução viável, denominada Solução
Ótima e denotada por (X1*, X2*), que leva ao valor ótimo da
função-objetivo Z*.
32
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Resolução gráfica de modelos de PL
Problema de mix de Produção
Fabricação de dois modelos de brinquedos: B1 e B2.
• Lucros unitários/dúzia: $8 para B1 e $5 para B2
• Recursos disponíveis:
1000 kg de plástico especial.
40 horas para produção semanal.
• Requisitos do Departamento de Marketing:
Produção total não pode exceder 700 dúzias;
A quantidade de dúzias de B1 não pode exceder em 350 a
quantidade de dúzias de B2.
• Dados técnicos:
B1 requer 2 kg de plástico e 3 minutos por dúzia.
B2 requer 1 kg de plástico e 4 minutos por dúzia.
33
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Resolução gráfica de modelos de PL
A Gerência está procurando um
programa de produção que aumente
o lucro da Companhia.
34
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Resolução gráfica de modelos de PL
Variáveis de decisão:
X1: produção semanal de B1 (em dúzias).
X2: produção semanal de B2 (em dúzias).
Função Objetivo: Maximizar o Lucro semanal
35
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Resolução gráfica de modelos de PL
Max 8X1 + 5X2 (Lucro semanal)
sujeito a:
2X1 + 1X2 ≤ 1000
3X1 + 4X2 ≤ 2400
X1 + X2 ≤ 700
X1 - X2 ≤ 350
Xj  0, j = 1,2
(Plástico - Kg)
(Tempo de produção - minutos)
(Produção total)
(mix)
(Não negatividade)
36
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Resolução gráfica de modelos de PL
Conceitos importantes:
Os pontos (X1, X2) que satisfazem todas as restrições do
modelo formam a Região Viável.
Esses pontos são chamados de Soluções Viáveis.
Usando a resolução gráfica pode-se representar todos as
restrições (semi-planos), a função objetivo (reta) e os três
tipos de pontos viáveis.
37
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Resolução gráfica de modelos de PL
1º Passo:
Traçar eixos cartesianos, associando a cada um deles uma
variável de decisão.
No exemplo de fabricação de brinquedos: X1 para o eixo
das abscissas e X2 para o eixo das ordenadas.
As restrições de não-negatividade, X1  0 e X2  0,
implicam que os pares (X1, X2) viáveis estão no 1º quadrante
dos eixos considerados.
38
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Resolução gráfica de modelos de PL
2º Passo:
Observar que a função-objetivo, ao se fixar um valor para Z,
representa uma reta. Alterações neste valor de Z gera uma família de
retas paralelas.
No exemplo dos brinquedos: considere a reta obtida fazendo
Z= 2000, isto é , a reta dada por 8X1 + 5X2 = 2000. Percebe-se que ao se
traçar retas paralelas no sentido de ficar mais afastado da origem (0, 0), o
valor de Z aumenta.
De fato pode-se verificar que a reta paralela, que contém algum
ponto da região viável, no caso o ponto ótimo X* = (320, 360), e está
mais afastada da origem, corresponde a um valor ótimo da função
objetivo Z* = 4360.
39
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Resolução gráfica de modelos de PL
Representando as condições de não negatividade
X2
X1
40
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Resolução gráfica de modelos de PL
Observar que no exemplo dos brinquedos, as restrições correspondem a
semi-planos associados, respectivamente, às retas suportes dadas por:
2X1 + 1X2 = 1000
3X1 + 4X2 = 2400
X1 + X2 = 700
X1 - X2 = 350
Xj  0, j = 1,2
Notar que cada reta suporte define dois semi-planos no espaço (X1, X2).
Para identificar qual destes semi-planos é de interesse no caso, ou seja,
contém os pontos que satisfazem a desigualdade da restrição, basta testar
algum ponto à esquerda ou à direita (acima ou abaixo) da reta suporte da
desigualdade.
Um ponto que torna isto fácil é a origem (0, 0), mas poderia ser qualquer
41
outro.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Resolução gráfica de modelos de PL
X2
Restrição do plástico
2X1+X2  1000
1000
Restrição da produção total
X1+X2  700 (redundante)
700
500
Inviável
Tempo de
produção
3X1+4X2  2400
Viável
500
700
X1
42
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Resolução gráfica de modelos de PL
X2
1000
Restrição do plástico
2X1+X2 1000
Restrição da produção total:
X1+X2 700 (redundante)
700
500
Tempo de Produção
3X1+4X2  2400
Inviável
Viável
Restrição do mix da produção:
X1-X2  350
X1
43
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Resolução gráfica de modelos de PL
X2
1000
700
500
Inviável
Viável
500
700
X1
Pontos interiores. Pontos na fronteira. Pontos extremos.
Há três tipos de pontos viáveis.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
44
Resolução gráfica de modelos de PL
A busca por uma Solução Ótima:
X2
1000
Começar com algum valor de lucro arbitrário,
Por exemplo $2000...
Depois aumentar o lucro, se possível...
...e continuar até que seja inviável
700
600
X* = (320, 360)
com Z* = 4.360
X1
500
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
45
Resolução gráfica de modelos de PL
Pontos extremos e Soluções Ótimas
Se o problema de Programação Linear tem uma Solução
Ótima, um ponto extremo é Solução Ótima.
46
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Resolução gráfica de modelos de PL
Visualização de situações possíveis
X2
X2
Z
Z*
Z
Solução
única
X1
Solução
ilimitada
X1
47
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Resolução gráfica de modelos de PL
Soluções Ótimas Múltiplas
Quando a função objetivo é paralela a alguma restrição.
Todos os pontos do segmento de
reta serão Soluções Ótimas.
X*1
X* = X*1 + (1 - )X*2, com 0    1
X*2
48
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Resolução gráfica de modelos de PL
X2
X2
Z
*
X*
Z
X*
Múltiplas Soluções
Ótimas 1 –
Segmento de Reta
Ótimo
X1
X1
Z*
Múltiplas
Soluções Ótimas 2
Semi-reta Ótima
49
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Resolução gráfica de modelos de PL
X2
O conjunto
viável é vazio.
Há restrições
incompatíveis.
Problema
inviável
X1
50
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Forma padrão de modelo de PL
Um modelo de PL com m restrições e n variáveis está na
forma padrão se possuir as características abaixo:
1. A função-objetivo é de minimização ou maximização;
2. Todas as restrições estão na forma de igualdade;
3. Todas as variáveis são não-negativas;
4. As constantes de cada restrição são não-negativas.
51
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Forma padrão de modelo de PL
Modelo na forma padrão:
Minimizar (ou maximizar) Z = C1 X1 + C2 X2 + ... + Cn Xn
Sujeito a:
A11 X1 + A12 X2 + ... + A1n Xn = b1
A21 X1 + A22 X2 + ... + A2n Xn = b2

 ...
...
...
...

...
...
...
 ...
Am1 X1 + Am2 X2 + ... + Amn Xn = bm

X1  0, X2  0, ..., Xn  0
b1  0, b2  0, ..., bm  0.

52
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Forma padrão de modelo de PL
Notação matricial para um modelo na forma padrão:
Minimizar (ou maximizar) Z = C X
Sujeito a:
 AX  b

X  0
b  0 .

Onde: A (m x n)  matriz de coeficientes tecnológicos
X (n x 1)  vetor das variáveis de decisão
b (m x 1)  vetor de demandas
C (1 x n)  vetor de custos (lucros)
53
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Forma padrão de modelo de PL
Redução de um modelo geral para a forma padrão
O Método Simplex exige que o modelo esteja na forma padrão.
Tratando com restrições na forma de inequações:
Estas restrições são transformadas em equações através da
introdução de novas variáveis (não-negativas), chamadas de
“variáveis de folga”.
54
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Forma padrão de modelo de PL
Tratando com variáveis não-positivas:
 0.
Suponha que num determinado modelo há uma variável X1
Basta substituí-la no modelo por uma nova variável nãonegativa X1’  0, dada por X1’ = – X1.
55
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Forma padrão de modelo de PL
Exemplo:
Considere o problema de dimensionamento de equipes de
inspeção:
X1  8  X1 + X3 = 8, X3  0 é uma variável de folga.
X2  10  X2 + X4 = 10, X4  0 é uma variável de folga.
5 X1 + 3 X2  45  5 X1 + 3 X2 – X5 = 45, X5  0 é uma variável
de folga.
56
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Forma padrão de modelo de PL
Interpretação das variáveis de folga no exemplo:
X3 = número de inspetores do nível 1 não utilizados.
X4 = número de inspetores do nível 2 não utilizados.
X5 = número (extra) de peças inspecionadas por dia, acima da
quantidade mínima (1800) especificada pela empresa
Variáveis de folga fornecem informações úteis sobre o problema.
57
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Forma padrão de modelo de PL
Tratando com variáveis livres (irrestritas em sinal):
Em algumas situações exige-se o uso de variáveis que podem
assumir tanto valores positivos, nulos, e negativos. Estas variáveis
são chamadas de livres (free) ou irrestritas em sinal.
Exemplo: Modelo de Planejamento Macroeconômico
Uma das Variáveis de Decisão é a Taxa de Inflação que pode
assumir qualquer valor positivo, nulo ou negativo (neste caso é
conhecida como Deflação).
58
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Tratando com variáveis livres (irrestritas em sinal):
Estas variáveis devem ser eliminadas do modelo na forma padrão. Há,
pelo menos, duas maneiras de se fazer isto:
1. Por substituição – utilizando uma das restrições do modelo,
já na forma padrão (igualdade), procura-se expressar a variável livre
como função das demais variáveis (não negativas) do modelo. A seguir
eliminar a variável livre do modelo substituindo-a pela função
escolhida na etapa anterior. A equação utilizada para expressar a
variável livre como função das demais variáveis também será
eliminada do modelo.
2. Por transformação – Suponha que a variável livre é S. Basta
substituir em todas as restrições, e na função objetivo, a variável S por
S = S’ – S”, com S’  0 e S”  0 sendo duas novas variáveis (auxiliares)
no modelo.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
59
Forma padrão de modelo de PL
Exemplo Completo
Obtenha a forma padrão do modelo abaixo:
Maximizar Z = X1 – 2X2 + 3X3
1
 X1 + X2 + X3  7
 X1  X2 + X3  2
2

Sujeito a: 
3
3X1  X2  2X3 =  5
X1  0, X2  0, X3 livre
60
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Forma padrão de modelo de PL
1. Introduzir variáveis de folga nas restrições (1) e (2):
X1 + X2 + X3 + X4 = 7 (1’) com X4  0.
X1 – X2 + X3 – X5 = 2 (2’) com X5  0.
2. Multiplicar a restrição (3) por (– 1) para eliminar b3 = – 5 < 0:
–3X1 + X2 + 2X3 = 5
(3’)
3. Substituir X2 0 por X2’  0 através de X2’ = – X2:
Max Z = X1+ 2 X2’ + 3 X3
=7
 X1  X2' + X3 + X4
Sujeito a: 
 X5 = 2
 X1  X2' + X3
 3X1  X2' + 2X3
=5

Pesquisa Operacional - UNESP / Campus de Guaratinguetá
1''
2''
3''
61
Forma padrão de modelo de PL
4. Eliminar X3:
4.1. Substituição
ou
4.2. Transformação
Max Z = -2X1 + 5X2’ - 3X4 + 21
ou
Max Z = X1 + 2X2’ + 3X3’ - 3X3’
 2X2'  X4 + X5 = 5

s. a: 
=9
5X1  X2' + 2X4
 X 1, X 2' , X 4, X 5  0

=7
 X1  X2'+ X3'  X3' '  X4
s. a:  X1 + X2'+ X3'  X3' '
 X5 = 2

=5
 3X1  X2'+2X3'  2X3' '
X1, X2' , X3' , X3' ' , X4, X5  0
Usando
De (1’’): X3 = 7 – X1 + X2’ – X4
ou
X3 = X3’ – X3’’
62
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Definições e Teoremas em PL
Ponto central na resolução de modelos de PL é a solução de
sistemas de equações lineares.
Apresenta-se a seguir o Método de Eliminação de Gauss Jordan.
Considere o sistema de equações abaixo:
(S1)
X1  2X2  X3  4X4  2X5  2

X1  X2  X3  3X4  X5  4
1
2
(nº variáveis >> nº equações)
63
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Definições e Teoremas em PL
• Conjunto solução de (S1) é a coleção de todos os valores de
(X1, X2, X3, X4, X5) que satisfazem as equações (1) e (2)
conjuntamente.
• Dois sistemas são equivalentes se possuem o mesmo conjunto
solução.
• Sistemas equivalentes podem ser obtidos por meio de
operações elementares sobre as linhas do sistema:
1. Multiplicar (dividir) qualquer equação por um nº.
2. Adicionar à qualquer equação uma Combinação Linear das
demais equações.
64
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Forma Canônica
Um sistema (S2) equivalente a (S1) pode ser obtido
multiplicando-se a equação (1) por – 1 e adicionando-se o
resultado à equação (2):
(S2)
X1  2X2  X3  4X4  2X5  2

X2  2X3 + X4  3X5  2

(3)
(4)
Um sistema (S3) equivalente a (S1) pode ser obtido
multiplicando-se equação (4) por 2 e adicionando-se o resultado à
equação (3):
(S3)
 3X3  2X4  4X5 = 6
X1

X2  2X3 + X4  3X5 = 2

(5)
(6)
(S3) é denominado uma forma canônica do sistema original (S1).
65
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Forma Canônica
Considere uma forma canônica de um sistema de equações lineares:
(como (S3) anteriormente obtido)
• Uma variável é dita ser variável básica para uma dada equação do
sistema se ela possuir coeficiente 1 nesta equação e coeficientes
nulos nas demais equações do sistema.
Exemplo: em (S3) X1 e X2 são variáveis básicas
• Variáveis que não satisfazem a condição acima são chamadas de
variáveis não-básicas.
Exemplo: em (S3) X3, X4, X5 são variáveis não-básicas.
66
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Solução Básica
A solução de um sistema na forma canônica, obtida fazendo-se as
variáveis não-básicas iguais a zero, é chamada de uma solução
básica (SB).
Nº máximo de soluções básicas =  N 
M
 
Exemplo:
Em (S3) fazendo-se X3 = X4 = X5 = 0  X1 = 6 e X2 = 2 formam
uma solução básica.
Nº de soluções básicas =  5  = 10
 
 2
Uma Solução Básica Viável (SBV) de um sistema é uma solução
básica onde todas as variáveis assumem valores não-negativos.
Exemplo: a solução básica do exemplo anterior é uma SBV.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
67
Pivoteamento
Operações de Pivoteamento são as operações elementares
aplicadas à um sistema para transformar uma dada variável em
variável básica. São usadas pelo método de eliminação de
Gauss Jordan. Deve-se identificar o elemento Pivô – que deve
ser transformado em 1 e os demais elementos da sua coluna
que devem ser transformados em 0.
Para obter uma forma canônica de um sistema basta aplicar
uma sequência de operações de pivoteamento (método de
Gauss Jordan) de modo se conseguir uma variável básica
associada com cada equação.
68
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método de Eliminação de Gauss Jordan
Artifício para a realização de operações de pivoteamento:
Considere o sistema (S) abaixo:
(S)
2X1  2X2 + 6X3 = 4

 X1 + 4X2  X3 = 2
(1)
(2)
Achar (S’) uma forma canônica de (S) de modo que X1 seja a
variável básica associada com a equação (1), e X3 seja a variável
básica associada com a equação (2).
69
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método de Eliminação de Gauss Jordan
VB
X1
X2
X1
2
X3
Operações Elementares Feitas
X3
b
-2
6
4
(1) - Pivô em azul
-1
4
-1
2
(2)
X1
1
-1
3
2
(1’) = (1)/2 - Equação do Pivô
X3
0
3
2
4
(2’) = (2) + (1’) – Pivô em Azul
X1
1
-11/2
0
-4
(1’’) = (1’) - 3*(2’’)
X3
0
3/2
1
2
(2’’) = (2’)/2 – Equação do Pivô
= 4
X1  11/ 2X2

3/2X2 + X3 = 2

Solução básica (não é viável): X1 = – 4 (Variável básica)
X3 = 2 (Variável básica)
X2 = 0 (Variável não básica)
(S’)
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
70
Teoremas em PL
Teorema 1
Dado um modelo já na forma padrão, as soluções básicas viáveis do
sistema de equações, correspondente às restrições do modelo, estão
associadas a pontos extremos do conjunto de soluções viáveis do
modelo original.
Teorema 2
Se um modelo de Programação Linear possui Solução Ótima então
pelo menos um ponto extremo, do conjunto de soluções viáveis do
modelo original, corresponde a uma Solução Ótima.
71
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Comentários Gerais
Procedimento simplista para resolver um modelo de PL
• Gerar todas as possíveis soluções básicas viáveis.
• Determinar qual das soluções básicas viáveis corresponde ao
melhor valor da função-objetivo.
Problemas:
1. Nº de soluções básicas viáveis pode ser excessivo.
2. Modelo pode apresentar solução ilimitada ou ainda ser inviável.
Observe que problemas de médio porte, que aparecem na prática,
costumam envolver centenas de variáveis (valor de n) e milhares de
restrições (valor de m).
72
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Comentários Gerais
Linhas de Pesquisa
• Algoritmos de pontos interiores e suas derivações.
• Implementações de algoritmos para processamento em paralelo.
• Linguagens de modelagem: ajudar no desenvolvimento e aplicação de
modelos de Pesquisa Operacional.
Exemplos:
• AMPL - Modeling Language for Mathematical Programming - R. Fourer, D.
M. Gay, and B. W. Kerningham, 1993.
• GAMS - General Algebraic Modeling System - J. Bisschop and A. Meeraus,
1982.
• What’s best - The ABC of Optimization - S. L. Savage, 1992.
73
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex
Procedimento iterativo que resolve qualquer modelo de PL num
número finito de iterações. Indica a ocorrência de múltiplas Soluções
Ótimas, solução ilimitada, e problema inviável.
Etapas de aplicação do Método Simplex
Considere um modelo de PL que esteja na forma padrão, e uma Solução
Básica Viável inicial.
O Método Simplex consiste basicamente da aplicação sucessiva de duas
etapas:
Etapa A: Identificação de uma Solução Ótima.
Etapa B: Melhoria de uma Solução Básica Viável.
74
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex
Etapa A: Identificação de uma Solução Ótima.
Verificar se a Solução Básica Viável atual satisfaz o critério de
otimalidade do algoritmo:
• Se o critério for satisfeito termina a aplicação do método;
• Caso contrário deve-se aplicar a etapa B.
Etapa B: Melhoria de uma Solução Básica Viável.
Procurar obter uma Solução Básica Viável melhor que a atual:
• Determinação da variável não-básica que deve entrar;
• Determinação da variável básica que será substituída;
• Obtenção da nova Solução Básica Viável - através de
operações de pivoteamento.
75
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex - Minimização
Desenvolvimento do Método Simplex
Seja um modelo de PL (minimização) colocado na forma padrão:
Min Z = C1 X1 + C2 X2 + ... + Cn Xn
s. a:
A11 X1 + A12 X2 + ... + A1n Xn = b1
A21 X1 + A22 X2 + ... + A2n Xn = b2

 ...
...
...
...

...
...
...
 ...
Am1 X1 + Am2 X2 + ... + Amn Xn = bm

X1  0, X2  0, ... , Xn  0
b1  0, b2  0, ... , bm  0

76
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex - Minimização
Considere o sistema (S) abaixo:
s. a:
A11 X1 + A12 X2 + ... + A1n Xn = b1
(1)


A21 X1 + A22 X2 + ... + A2n Xn = b2
(2)


...
...
...
...
...


...
...
...
...
...


Am1 X1 + Am2 X2 + ... + Amn Xn = bm
(m)


(m + 1)
- Z + C1 X1 + C2 X2 + ... + Cn Xn = 0
Obter, aplicando o método de eliminação de Gauss-Jordan, o sistema
equivalente (S’) = uma forma canônica de (S) onde:
X1
X2
...
Xm
–Z
seja a variável básica referente a equação (1),
seja a variável básica referente a equação (2),
seja a variável básica referente a equação (m),
seja a variável básica referente a equação (m+1).
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
77
Método Simplex - Minimização
O sistema (S’), que é uma forma canônica de (S), foi obtido
pelas operações de pivoteamento aplicadas às variáveis X1, X2,
..., Xm, e –Z, é dado por:

X1
+ A1, m + 1 Xm + 1 + ... + A1, n Xn = b1

X2 + A2, m + 1 Xm + 1 + ... + A2, n Xn = b2


 .......

Xm + Am, m + 1 Xm + 1 + ... + Am, n Xn = bm


+ C m + 1 Xm + 1 + .... + C n Xn =  Zo (I)
 Z
78
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex - Minimização
Em (S’) :
(1) Ai , j , bj, Cj são respectivamente os novos coeficientes das variáveis
nas equações de (S’), as novas constantes nestas mesmas equações, e
os novos coeficientes das variáveis na função objetivo (expressão (I)),
obtidos pelas operações de pivoteamento no sistema (S).
(2) Os coeficientes Cj são denominados coeficientes de custo relativo (ou
reduzido) das variáveis não-básicas da solução atual.
(3) Há uma Solução Básica Viável explícita em (S’), onde:
• Variáveis básicas: X1  b1, X2  b2, ... , Xm  bm;
• Variáveis não-básicas: Xm  1  Xm  2  ...  Xn  0
• Valor da função objetivo: Zo  C1 b1  C2 b 2  ...  Cnbn
79
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex - Minimização
Visualização da etapa A do Método Simplex:
Teste de otimalidade da Solução Básica Viável atual.
Min Z = 4X1 + X2 + X3
s. a:
(S):
2X1  X2  2X3  4

3X1  3X2  X3  3
Xi  0, i  1,3

2X1 + X2 + 2X3 = 4


3X1 + 3X2 + X3 = 3

 Z  4X1  X 2  X 3  0

(1)
(2)
(3)
80
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex - Minimização
Aplicando o método de eliminação de Gauss Jordan para obter uma
forma canônica (S’) associando X3 como variável básica para a
equação (1), X1 para a equação (2) e –Z para a equação (3), tem-se:
(S’):
 3/4 X2 + X3 = 3/2


X1 + 5/4 X2
= 1/2

 Z
 13/4 X2
=  7/2

(I)
Solução básica viável atual
• Variáveis básicas: X1 = 1/2, X3 = 3/2
• Variáveis não-básicas: X2 = 0
• Função objetivo: Z = Z0 = 7/2
81
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex - Minimização
De (I):
Z = 7/2 – 13/4 X2
Análise de otimalidade da Solução Básica Viável (SBV) atual:
X2 = 0 é variável não básica
Se X2 se tornar VB o valor de X2
Se X2
o valor de Z
o que é desejável pois a função
objetivo é
de minimização
Conclusão: A SBV atual não é ótima e X2 deve se tornar VB numa
próxima SBV melhor que a atual.
Assim X2 deve Entrar. Ir a etapa (B).
82
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex - Minimização
Etapa (A) do Método Simplex
Questão:
Como verificar se a Solução Básica Viável explicitada em (S’) é
ótima para o modelo em estudo?
Resposta:
Considere a expressão (I) em (S’), dada por:
Z
Onde
+ Cm  1 X m + 1 + ....+ Cn Xn =  Zo,
 Zo = C1 b1 + C2 b2 + ... + Cm bm.
83
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex - Minimização
Analisando (I) há duas possibilidades:
• Se não há Cj  0  então a solução atual é ótima. Não
haverá a aplicação da etapa (B). Fim da aplicação do
Método Simplex.
• Se há Cj  0  a solução atual não é ótima.
Uma
variável não-básica XS, associada
com
um
coeficiente de custo relativo negativo, deve ser
transformada em variável básica numa próxima solução
básica viável . Esta nova Solução Básica Viável terá um
valor para a função objetivo melhor (no caso do modelo de
minimização, menor) que o valor da função objetivo atual Z0.
Aplicar a etapa (B).
84
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex - Minimização
Visualização da etapa B do Método Simplex (PL de Minimização):
Seja uma Solução Básica Viável disponível dada por,
X1 = 5, X2 = 6, X3 = X4 = 0, Z = 4,
Associada ao sistema (S) abaixo:
(S):
X1
+ 2X3 + 3X4 = 5


X2 + 2X3  2X4 = 6

 Z
 4X3 + 5X4 =  4

(1)
(2)
(3)
Aplicando a etapa (A) tem-se:
Como
C 3 = - 4 < 0  se o valor de X3  o valor de Z  .
Desta maneira X3 deve Entrar e seu valor deverá aumentar. Observe-se
que X4 não deve Entrar pois piorará o valor da F. O.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
85
Método Simplex (minimização)
Problema:
Até quanto aumentar o valor de X3?
Análise: como X4= 0 (permanece variável não-básica), tem-se:
De (1): X1 = 5 – 2X3
De (2): X2 = 6 – 2X3
ou seja
ou seja
se X3   X1 
se X3   X2 
Sabe-se que X1  0  X3  5/2 

  X3 = Min 5/2, 6/2 = 5/2
Sabe-se que X2  0  X3  6/2 
Portanto X3 substituirá X1 no conjunto das variáveis básicas da
nova Solução Básica Viável dada por:
X3 = 5/2, X2 = 1, X1 = X4 = 0, Z = 4 - 4X3 = -6
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
86
Método Simplex - Minimização
Etapa (B) do Método Simplex
Hipótese:
Há um coeficiente de custo relativo CS < 0  deve-se achar uma
nova Solução Básica Viável onde XS seja variável básica.
Problema:
Qual das atuais variáveis básicas será substituída por XS na
próxima Solução Básica Viável?
87
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex - Minimização
Solução:
A i,s os coeficientes de XS nas equações do sistema de
• Sejam
restrições, onde i = 1, ..., m.
• Procurar a equação r do sistema de restrições onde ocorra:
Min  bi 
br
=


A r , s Ai, s > 0  Ai, s 
• A variável básica da Solução Básica Viável atual associada
com a equação r acima será substituída por XS.
88
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex - Minimização
Artifício para aplicar as etapas (A) e (B) do Método Simplex.
Considere o exemplo de minimização usado na visualização da
etapa (B), já colocado numa forma canônica:
X1
+ 2X3 + 3X4 = 5


X2 + 2X3  2X4 = 6

 Z
 4X3 + 5X4 =  4

(1)
(2)
(3)
89
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex - Minimização
Operacionalização da aplicação das etapas (A) e (B):


VB
X1
X2
X3
X4
X1
X2
1
0
0
1
2
2
3
-2
5
6
-Z
0
0
5
-4
-4
b
 X3 entra
X3
X2
1/2
-1
0
1
1
0
3/2
-5
5/2
1
-Z
2
0
0
11
6
Não há Cj < 0 , assim a
solução atual é ótima.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
(5/2)  menor quociente X1 sai
(6/2)
 X 1*   0 

  
 X 2 *  1 
X*  
= 

X 3*
5/2

  
 X 4 *  0 

  
Z* = - 6
90
Método Simplex - Maximização
Modelo de Programação Linear com função objetivo de
maximização.
Etapa (A):
Solução básica viável atual será ótima   Cj > 0.
Etapa (B):
A variável XS que entra terá C S > 0, para possibilitar uma
melhoria (aumento) no valor da função objetivo associado com a
Solução Básica Viável atual.
Importante: as operações de pivoteamento não se alteram.
91
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex (maximização)
Exemplo de modelo de maximização resolvido pelo Método
Simplex.
Modelo original
Max Z = 3X1 + 5X2
 4
X1
s. a: 
X2  6


3X1 + 2X2  18
X1  0, X2  0


Modelo na forma padrão
Max Z = 3X1 + 5X2
+ X3
= 4
X1
s. a: 
X2
+ X4
= 6


+ X5 = 18
3X1 + 2X2
Xi  0, i = 1,5
92
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex
VB
X1
X2
X3
X4
X5
b
X3
X4
X5
1
0
3
0
1
2
1
0
0
0
1
0
0
0
1
4
6
18
-Z
3
5
0
0
0
0
X3
X2
X5
1
0
3
0
1
0
1
0
0
0
1
-2
0
0
1
4
6
6
-Z
3
0
0
-5
0 -30
X3*
X2*
X1*
0
0
1
0
1
0
1
0
0
2/3
1
-2/3
-1/3
0
1/3
2
6
2
-Z*
0
0
0
-3
-1
-36
Entra X2, Sai X4
Entra X1, Sai X5
Solução Ótima
X*1 = 2, X*2 = 6,
X*3 = 2, X*4 = X*5 = 0,
Z* = 36
93
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex
Comentários Gerais
Considere um modelo de Programação Linear na forma padrão que
seja de minimização.
(1) Ocorrência de “Empate na Entrada”:
Escolher para entrar a variável não-básica Xs associada ao
menor valor de coeficiente de custo relativo C S < 0.
(Regra de entrada de Dantzig)
94
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex
(2) Identificação de Solução Ilimitada:
Pode ser feita a identificação de solução ilimitada durante a
aplicação da etapa (B).
Se houver alguma variável não-básica Xs para entrar que tenha
A i , s  0, em todas as equações i (= 1,..., m) do
coeficientes
sistema de restrições.
95
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex
Exemplo de Modelo com Solução Ilimitada:
Seja a Solução Básica Viável abaixo, associada a forma canônica (S):
X1 = 5, X2 = 6, X3 = X4 = 0, Z = – 4
(S):
X1
 2X3 + 3X4 = 5


X2  2X3  2X4 = 6

 Z
 4X3 + 5X4 =  4

(1)
(2)
(3)
Observar que C 3 = – 4 < 0  X3 deve entrar. Quem vai sair?
De (1): X1 = 5 + 2X3
quando X3   X1 , X2 e Z
De (2): X2 = 6 + 2X3
Assim o modelo apresenta solução ilimitada com Z  – .
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
96
Método Simplex
(3) Interpretação geométrica do Método Simplex:
Em cada iteração do Método Simplex (Etapa (A) + Etapa
(B)) há um deslocamento de uma Solução Básica Viável para
outra que apresenta um valor para a função objetivo melhor.
Em termos da resolução gráfica: numa iteração há a
locomoção de um ponto extremo para outro ponto extremo
adjacente na região viável do modelo em questão.
97
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex
Exemplo:
Modelo original
Min Z = –3X1 – 5X2
s. a:
4
X1

X2  6


3X1 + 2X2  18

Xi  0, i = 1, 2
X2
Região
viável
X1
98
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex
Exemplo:
Modelo original

Min Z = –3X1 – 5X2

s. a:
4
X1

X2  6


3X1 + 2X2  18
Xi  0, i = 1, 2
Modelo na forma padrão
Min Z = –3X1 – 5X2
+ X3
= 4
X1

X2
+ X4
= 6
s. a: 

+ X5 = 18
3X1 + 2X2
Xi  0, i = 1, 5
X2
Região
viável
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
X1
99
Método Simplex
Resolução do exemplo para interpretação geométrica do Método Simplex:
VB
X1
X2
X3
X4
X5
b
X3
1
0
1
0
0
4
X4
0
1
0
1
0
6
X5
3
2
0
0
1
18
-Z
-3
-5
0
0
0
0
X3
1
0
1
0
0
4
X2
0
1
0
1
0
6
X5
3
0
0
-2
1
6
-Z
-3
0
0
5
0
30
X3*
0
0
1
2/3
-1/3
2
X2*
0
1
0
1
0
6
X1*
1
0
0
-2/3
1/3
2
-Z*
0
0
0
3
1
36
Quadro 1: Entra X2 Sai X4
Quadro 2: Entra X1 Sai X5
Quadro 3 (ótimo)
Solução básica viável ótima: X1* = 2, X2* = 6, X3* = 2, X4* = X5* = 0, Z* = –36
100
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex
Visualização das iterações
Quadro 3:
X4 *= X5* = 0,
Z* = -36, X1* = 2,
X2* = 6, X3* = 2.
X2
Quadro 2:
X1 = X4 = 0,
Z = -30,
X2 = 6, X3 = 4, X5 = 6.
Região
viável
Quadro 1:
X1 = X2 = 0,
Z = 0, X3 = 4, X4 = 6,
X5 = 18.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
X1
101
Método Simplex
(4) Identificação de Soluções Ótimas Múltiplas:
Considere que há uma Solução Básica Viável ótima para um
modelo de minimização, ou seja, tem-se Z* = Z* e todos C S  0 para toda
variável não-básica X s .
A identificação da ocorrência de Soluções Ótimas múltiplas é feita,
no Quadro Ótimo, quando há alguma variável não-básica Xj com C j = 0.
Assim ao se escolher Xj para entrar no conjunto das variáveis
básicas, não se alterará o valor ótimo Z* da função objetivo.
Desta maneira, pode-se obter uma nova Solução Básica Viável
ótima na qual Xj será uma variável básica.
Fica caracterizada assim a existência de múltiplas Soluções Ótimas.
102
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex
Exemplo:
Modelo original

Modelo na forma padrão
Min Z = – X1 – 2X2

Min Z = – X1 – 2X2
3
X1
S. a: 
X2  4


X1 + 2X2  9

Xi  0, i = 1, 2
+ X3
=3
X1

X2
+ X4
=4
S. a: 

+ X5 = 9
X1 + 2X2

Xi  0, i = 1, 5
A seguir apresenta-se:
A resolução gráfica do modelo original.
A resolução do modelo na forma padrão pelo Método Simplex.
Uma visualização das iterações desenvolvidas pelo Método
Simplex sobre a região viável do modelo original.
103
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex
Resolução gráfica do exemplo com múltiplas Soluções Ótimas
X2
1
4
= XA*
(0,4)
X*
3
3
= XB*
Z* = - 9
Z=-6
(3,0)
X1
Observação: XA* , XB* são soluções básicas viáveis ótimas, Z* = – 9 é
o valor ótimo da função objetivo, a expressão geral da Solução Ótima é:
X* =  XA* + (1 – ) XB* com 0    1.
104
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex
Resolução do modelo na forma padrão
VB
X1
X2
X3
X4
X5
b
X3
1
0
1
0
0
3
X4
0
1
0
1
0
4
X5
1
2
0
0
1
9
-Z
-1
-2
0
0
0
0
X3
1
0
1
0
0
3
X2
0
1
0
1
0
4
X5
1
0
0
-2
1
1
-Z
-1
0
0
2
0
8
X3*
0
0
1
2
-1
2
X2*
0
1
0
1
0
4
X1*
1
2
0
-2
1
1
-Z*
0
0
0
0
1
9
X4*
0
0
1/2
1
-1/2
1
X2*
0
1
-1/2
0
1/2
3
X1*
1
0
1
0
0
3
-Z*
0
0
0
0
1
Quadro 1: Entra X2 e Sai X4
9
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Quadro 2: Entra X1 e Sai X5
Quadro 3: Ótimo (XA*)
Solução ótima geral:
Quadro 4
Ótimo
(XB*)
X* =  XA* + (1 - ) XB*,
com 0    1, e Z* = - 9
105
Método Simplex
Visualização das iterações do Método Simplex
Quadro 3:
X4* = X5* = 0,
X1* = 1, X2* = 4,
X3* = 2, Z* = -9
X2
XA
Quadro 2:
X1 = X4 = 0,
X2 = 4, X3 = 3,
X*
X5 = 1, Z = -8
X* =  XA* + (1 -) XB*,
onde 0    1
Quadro 4:
X3* = X5* = 0,
X1* = 3, X2* = 3,
X4* = 1, Z* = -9
É o caso, em termos
de resolução gráfica,
de um segmento de
reta ótimo.
XB
(0,0)
Quadro 1:
X1
X1 = X2= 0, X3 = 3,
X4 = 4, X5 = 9,
Z=0
106
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Simplex
Observação importante:
Se no Quadro 3, na coluna da variável X4 não houvesse algum
coeficiente Ai , 4 > 0 , não se poderia efetuar o pivoteamento;
Então este é o caso, em termos da resolução gráfica, que a Solução
Ótima é uma semi-reta, da forma X* = XA* com   1 .
107
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Procedimentos de inicialização para o Método
Simplex
Considere um modelo de Programação Linear que esteja na forma
padrão
Se todas as restrições do modelo original (ainda não colocado na forma
padrão) forem desigualdades do tipo “  “, tem-se uma forma canônica
inicial (ou seja, uma Solução Básica Viável inicial) evidente, onde as
variáveis básicas serão as variáveis de folga introduzidas para a redução das
desigualdades para equações equivalentes.
Se alguma restrição do modelo original for uma igualdade “=“, ou ainda
desigualdade do tipo “  “, a condição acima não ocorrerá e não haverá
uma Solução Básica Viável inicial explícita.
Quando não há uma Solução Básica Viável inicial deve-se utilizar algum
procedimento de inicialização para o Método Simplex.
109
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Procedimentos de inicialização para o Método
Simplex
(1) Método das Duas Fases.
Fase 1:
(a) Construção e resolução de um modelo artificial
(b) Análise da Solução Ótima do modelo artificial
Fase 2:
Resolução do modelo original utilizando como solução inicial a Solução
Ótima do modelo artificial.
(2) Método do Big M .
Introduz variáveis artificiais, nas equações do sistema de restrições
(exatamente como o método das duas fases), e na função objetivo original com
coeficientes penalizantes adequados, isto é, M >>0 para minimização e –M <<0
para maximização.
A seguir apresenta-se as bases do Método das Duas Fases para inicialização do
Método Simplex.
110
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Procedimentos de inicialização para o Método
Simplex
Desenvolvimento do Método das Duas Fases
Considere que o modelo de Programação Linear na forma padrão
abaixo não apresenta uma Solução Básica Viável inicial, isto é, não há
uma forma canônica evidente.
Modelo original (na forma padrão)
Min Z = C1 X1 + C2 X2 + ... + Cn Xn
s.a:
A11X1 + .... + A1nXn = b1
........................................


........................................
Am1X1 + ... + AmnXn = bm


Xi  0, i = 1, n
111
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Procedimentos de inicialização para o Método Simplex
Fase 1: Construção e resolução de um modelo artificial
O modelo artificial, a partir das equações do sistema de restrições
do modelo original será:
com Y1, Y2, ..., Ym sendo as variáveis artificiais não negativas.
Min W = Y1 + Y2 + .... + Ym
s. a:
= b1
A11X1 + ... + A1nXn + Y1
A21X1 + ... + A2nXn +
Y2
= b2

........................................................................
Am1X1 + ... + AmnXn +
Ym = bm

 Xi  0, i = 1, n ; Yj  0, j = 1, m
A F. O. artificial sempre será de Minimização, qualquer que seja o Modelo Original.
112
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Procedimentos de inicialização para o Método
Simplex
Observe que o modelo artificial está na forma padrão com Solução Básica
Viável inicial:
X1 = X2 = ... = Xn = 0
(variáveis não-básicas)
Y1 = b1, Y2 = b2, ..., Ym = bm (variáveis básicas)
W = b1 + b2 + ... + bm.
Analisando o valor ótimo da função objetivo W* do modelo artificial
pode-se concluir:
Caso 1: Se W*  0  há pelo menos uma variável básica artificial Yj com
valor  0.
Nesta situação conclui-se que o sistema de restrições do modelo original
depende destas variáveis artificiais não nulas para ser satisfeito. Assim o
Modelo Original é inviável. Não há a fase 2.
113
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Procedimentos de inicialização para o Método
Simplex
Caso 2: se W* = 0  Y1* = Y2* = ... = Ym* = 0.
Conclui-se que o sistema de restrições do Modelo Original
pode ser satisfeito apenas com as variáveis Xi.
Desta forma o Modelo Original é viável.
Subcaso 2.1: se todas as variáveis artificiais são nãobásicas na Solução Ótima do modelo artificial.
Basta eliminar todas as variáveis artificiais, substituir a
função objetivo artificial pela original, e iniciar a fase 2.
114
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Procedimentos de inicialização para o Método
Simplex
Subcaso 2.2: se alguma variável artificial permanece como variável básica
na Solução Ótima do modelo artificial. Observe que estas variáveis devem
ser nulas, pois W* = 0.
Deve-se, através de operações de pivoteamento, substituir estas variáveis
artificiais básicas por variáveis originais, eliminar todas as variáveis
artificiais não básicas, substituir a função objetivo artificial pela original, e
iniciar a fase 2.
Se não é possível substituir alguma variável artificial básica por uma
variável original (pela inexistência de elemento pivot), basta eliminar a
equação associada com a variável artificial em questão (a equação é uma
combinação linear das demais equações do modelo original).
115
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo de aplicação do Método das Duas Fases
Visualização das iterações
Modelo
Min Z = -3X1 - 5X2
s. a:
 4
X1

X2  6


3X1 + 2X2  18

Xi  0, i = 1,2
(1)
(2)
(3)
(4)
116
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Procedimentos de inicialização para o Método
Simplex
Exemplo de aplicação do Método das Duas Fases
Modelo
Min Z = -3X1 - 5X2
 4
 X1

X2  6
s. a: 

3X1 + 2X2  18
Xi  0, i = 1,2

Modelo na forma padrão

Min Z = -3X1 - 5X2
s. a:
+ X3
=4
X1

X2
+ X4
= 6


- X5 = 18
3X1 + 2X2
Xi  0, i = 1, 5
117
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Procedimentos de inicialização para o Método
Simplex
Fase 1: construção do Modelo Artificial
Min W = Y1
s. a:
X1
+ X3
=4
X2
+X4
=6
3X1 + 2X2
– X5 + Y1 = 18
Xi ≥ 0, i = 1,5; Yi ≥ 0
Solução básica viável inicial para o Modelo Artificial:
X1 = X2 = X5 = 0 (variáveis não-básicas)
X3 = 4, X4 = 6, Y1 = 18 (variáveis básicas)
W = 18
118
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo de aplicação do Método das Duas Fases
Fase 1: Resolução do Modelo Artificial
VB
X1
X2
X3
X4
X5
Y1
b
X3
1
0
1
0
0
0
4
Adequar a
X4
0
1
0
1
0
0
6
função
Y1
3
2
0
0
-1
1
18
objetivo
-W
0
0
0
0
0
1
0
X3
1
0
1
0
0
0
4
X4
0
1
0
1
0
0
6
Y1
3
2
0
0
-1
1
18
-W
-3
-2
0
0
1
0
-18
X1
1
0
1
0
0
0
4
X4
0
1
0
1
0
0
6
Y1
0
2
-3
0
-1
1
6
-W
0
-2
3
0
0
1
-6
X1
1
0
1
0
0
0
4
X4
0
0
3/2
1
1/2
-1/2
3
X2
0
1
-3/2
0
-1/2
1/2
3
-W*
0
0
0
0
0
1
0
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Transformar em
Zeros os coeficientes
das variáveis
artificiais na F. O.
Quadro 1
Quadro 2
Quadro 3
Fase 1: Análise da Solução
Ótima do Modelo Artificial
W* = 0
Caso 2.1: Modelo Original
viável. Não há variáveis
básicas artificiais. Eliminar
variáveis artificiais,
substituir função objetivo
artificial pela original.
Iniciar fase 2.
119
Exemplo de aplicação do Método das Duas Fases
Fase 2: Resolução do Modelo Original
VB
X1
X2
X3
X4
X5
b
X1
1
0
1
0
0
4
Adequar a
X4
0
0
3/2
1
1/2
3
função
X2
0
1
-3/2
0
-1/2
3
objetivo
-Z
-3
-5
0
0
0
0
X1
1
0
1
0
0
4
X4
0
0
3/2
1
1/2
3
X2
0
1
-3/2
0
-1/2
3
-Z
0
0
-9/2
0
-5/2
27
X1*
1
0
0
0
0
4
X5*
0
0
3
2
1
6
Quadro 4
X2*
0
1
0
1
0
6
(Ótimo)
-Z*
0
0
3
5
0
42
Quadro 3’
Coeficientes de
variáveis
básicas na F. O.
devem ser Zero
Solução ótima
(única) do Modelo
Original:
X1* = 4, X2* = 6,
X5* = 6,
X3* = X4* = 0,
Z* = -42
120
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Visualização da Iterações do Método das Duas Fases
Quadro 4: Ótimo,
Z* = -42
X2
(2, 6)
Quadro 1:
W = 18,
Z=0
Região
Viável
Quadro 3=
Quadro 3’:
W = 0,
Z = -27
(4, 6)
(4, 3)
(4, 0)
Quadro 2:
W = 6,
Z = -12
X1
121
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
SIM
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exercícios: Resolver graficamente e pelo
Simplex
1.
s. a:
2.
s. a:
Min Z = X1 + 2 X2
X1 + X2 ≥ 3
2X1 + X2 ≤ 2
X1, X2 ≥ 0
(R: Inviável)
Max Z = 6X1 + 10 X2
3X1 + 5X2 ≤ 15
5X1 + 2X2 ≤ 10
X1, X2 ≥ 0
R: há mais de uma solução ótima
(Segmento de reta ótimo)
123
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exercícios
3.
s. a:
4.
s. a:
Max Z = 2X1 + 2X2
X1 - X2 ≥ -1
- ½ X1 + X2 ≤ 2
X1, X2 ≥ 0
(R: Solução ilimitada)
Max Z = X1 + X2
X1 + 4X2 ≥ 4
3X1 + X2 = 1
X1, X2 ≥ 0
Comentário: Fica a Variável Artificial na solução ótima do
Problema Artificial como Variável Básica, ela sai por
pivoteamento.
124
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exercícios
5.
s. a:
6.
s. a:
Max Z = X1 + X2
2X1 + 3X2 = 5
- 6X1 - 9X2 = - 15
X1 – X2 ≥ 0
X1, X2 ≥ 0
Comentário: 1a. equação é
combinação linear das demais.
Max Z = - 4X1 + X2
3X1 + X2 ≥ 3
X1 - X2 ≤ - 1
4X1 – X2 ≥ - 4
X1, X2 ≥ 0
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
R: Há mais de uma solução
ótima (Semi-reta ótima)
125
Exercícios
7. Max Z = 3X1 – 5X2
s.a: -3X1 + 5X2  0
X1 – 2X2  -2
Xi  0, i = 1,2
R: Há mais de uma solução ótima (Semi-reta ótima)
Pesquisa Operacional - UNESP / Campus de Guaratinguetá