Modelagem em Programação Linear

Prévia do material em texto

UNIVERSIDADE FEDERAL DO PARÁ
INSTITUTO DE CIÊNCIAS SOCIAIS APLICADAS
FACULDADE DE ADMINISTRAÇÃO
Pesquisa Operacional
Modelagem em Programação Linear
Prof. MSc. André Luiz Ferreira e Silva1
1Universidade Federal do Pará - UFPA.
Instituto de Ciências Sociais Aplicadas - ICSA.
metrica2011@yahoo.com.br
Belém-Pa, 23/02/2014
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 1 / 50
Modelagem em Programação Linear
Sumário
1 Modelagem em Programação Linear
Especificação do modelo de PL
Solução gráfica do PPL
Aplicações
2 O Método Simplex
Introdução
Forma padrão do PPL
Cálculo do algoritmo simplex
Forma Geral do PPL
Aplicações
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 2 / 50
Modelagem em Programação Linear Especificação do modelo de PL
Modelo de PL de duas variáveis
Nesta seção discutiremos a solução gráfica de um Problema de
Programação Linear (PPL) a partir de um modelo com duas variáveis de
decisão (TAHA, 2008, cap.2)[1].
Ainda que na prática modelos de duas variáveis sejam poucos utilizados,
esta abordagem proporciona, do ponto de vista didático, boas condições
de aprendizagem.
Além disso, a solução do modelo de duas variáveis torna-se importante
para a compreensão da solução generalizada dos modelos de PL, pois
são as bases para o desenvolvimento do algoritmo simplex, assunto que
será tratado na próxima seção.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 3 / 50
Modelagem em Programação Linear Especificação do modelo de PL
Considerações gerais para solução do PPL
O modelo de PL, como em qualquer problema de PO, têm três componentes
básicos:
1 Variáveis de decisão: são os valores que o modelo deve determinar.
2 Objetivo (meta): é o valor que o modelo de PL precisa otimizar. O
Objetivo pode estar voltado a maximizar ou minimizar a função objetivo.
3 Restrições: é o conjunto de regras que o PPL deve satisfazer.
A definição das variáveis de decisão é a primeira etapa para especificação
adequada do PPL. Uma vez concluída, a tarefa de construir a função objetivo
e as restrições torna-se mais direta.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 4 / 50
Modelagem em Programação Linear Especificação do modelo de PL
O caso da companhia TNBRAS S/A.
Exemplo (1)
A companhia TNBRAS S/A produz tintas para interiores e exteriores com base
em duas matérias-primas, M1 e M2. A tabela a seguir (1) demonstra os
dados básicos do problema.
Uma pesquisa de mercado indica que a demanda diária de tintas para
interiores não pode ultrapassar a de tintas para exteriores por mais de 1
tonelada. Além disso, a demanda máxima diária de tintas para exteriores é de
2 toneladas.
A companhia precisa determinar o mix ótimo (o melhor) de tintas para
interiores e exteriores que maximize o lucro total diário.
Para tratar do problema (do modelo) da companhia TNBRAS S/A, vamos
utilizar a metodologia antes sugerida.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 5 / 50
Modelagem em Programação Linear Especificação do modelo de PL
Produção de tintas da companhia TNBRAS S/A
Figura: Dados técnicos da produção de tintas da companhia TNBRAS S/A
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 6 / 50
Modelagem em Programação Linear Especificação do modelo de PL
Especificação do modelo de PL: caso da companhia TNBRAS S/A.
1. Identificação das variáveis de decisão
O problema da companhia TNBRAS S/A consiste em determinar as
quantidades diárias a ser produzidas de tintas para interiores e exteriores.
Assim, as variáveis de decisão do PPL podem ser definidas como
x1 = quantidade (em toneladas) de tintas para exteriores produzidas
diariamente.
x2 = quantidade (em toneladas) de tintas para interiores produzidas
diariamente.
Observe como foi fácil identificar as variáveis de decisão. Seus valores
precisam ser determinados de modo a atingir certo objetivo.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 7 / 50
Modelagem em Programação Linear Especificação do modelo de PL
Especificação do modelo de PL: caso da companhia TNBRAS S/A.
2. Definição da função objetivo
Observe que se trata de um modelo de maximização do lucro diário da
companhia TNBRAS S/A, de modo que cada tonelada vendida de tinta para
exterior e interior deixa uma margem de lucro (margem de contribuição
unitária) de R$ 5,00 e R$ 4,00 (mil), respectivamente.
Assim, a função objetivo pode ser representada como
Maximizar z = 5x1 + 4x2. (1)
No entanto, a companhia TNBRAS S/A sabe que para maximizar seu lucro
diário (a função objetivo z) ele precisar atender algumas restrições, as quais
serão formalizadas no passo seguinte.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 8 / 50
Modelagem em Programação Linear Especificação do modelo de PL
Especificação do PPL: o caso da companhia TNBRAS S/A.
3. Definição das restrições
Observe na tabela (1) que a companhia TNBRAS S/A enfreta restrições, entre as
quais cabe destacar a disponibilidade máxima de matéria-prima que é limitada em 24
e 6 toneladas diárias de uso das matérias-prima M1 e M2, respectivamente. Em
termos matemáticos, é possível representar estas restrições como
6x1 + 4x2 ≤ 24 matéria-prima M1 (2)
1x1 + 2x2 ≤ 6 matéria-prima M2 (3)
Outra duas restrições estão relacionadas a demanda de mercado. A pesquisa de
mercado afirma que a demanda diária de tintas para interiores não pode ultrapassar a
de tintas para exteriores por mais de 1 tonelada. Formalmente, temos
x2 − x1 ≤ 1 demanda de mercado (4)
Além disso, a demanda máxima diária de tintas para exteriores é de 2 toneladas
x2 ≤ 2 demanda de mercado (5)
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 9 / 50
Modelagem em Programação Linear Especificação do modelo de PL
Especificação do PPL: o caso da companhia TNBRAS S/A.
Agora devemos consolidar a função objetivo e as restrições em um só modelo,
chamado de especificação de modelo. Para o caso da companhia TNBRAS S/A o
modelo do PPL pode ser representado por.
Função objetivo:
Maximizar z = 5x1 + 4x2.
Sujeito a
6x1 + 4x2 ≤ 24 (R1)
1x1 + 2x2 ≤ 6 (R2)
−x1 + x2 ≤ 1 (R3)
x2 ≤ 2 (R4)
x1, x2 ≥ 0 (R5)
Observe atentamente a restrição (R5), ela é uma restrição implicita e chamada de
retrição de não-negatividade, pois indica que as variáveis x1 e x2 não podem assumir
valores negativos.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 10 / 50
Modelagem em Programação Linear Especificação do modelo de PL
Solução para o PPL: o caso da companhia TNBRAS S/A.
Após obter a especificação do PPL, surgem naturalmente, algumas questões. Por
exemplo, Quais são os valores assumidos por x1 e x2 que satisfaçam todas as
restrições? Será que este sistemas possui única solução (unicidade), múltiplas
soluções ou é indeterminado (sem solução)?
Vamos, arbitrariamente, atribuir os seguintes valores para x1 e x2:
Solução 1(S1) : (x1, x2) = (3, 1)
Solução 2(S2) : (x1, x2) = (4, 1)
Substituindo os valores nas restrições do modelo, você verá que os valores da S2 não
satisfazem a condição (R1). Neste caso, a S2 é uma solução inviável para o sistema.
Porém, se analisarmos atentamente, S1 satisfaz todas as restrições do modelo,
portanto, pode-se afirmar que S1 é uma uma solução viável para o sistema.
No entanto, resta saber agora se S1 proporciona o lucro máximo para a companhia?
Se sim, então, S1 é o ponto ótimo do sistema, o ponto onde nenhum outro consegue
produzir um resultado tão bom (o melhor) quanto ao produzido por S1. Se S1 não for
ponto ótimo, então, precisamos encontrar tal ponto.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 11 / 50
Modelagem em Programação Linear Solução gráfica do PPL
Definições
A solução gráficado PPL é a primeira sistemática que devemos compreender
para obtermos a solução ótima para o sistema.
Já sabemos que uma solução viável é aquela que satisfaz todas as restrições
do PPL. Sabemos também que, se dada solução não satisfaz pelo menos uma
restrição do PPL, então, estamos diante de uma solução inviável.
Portanto, toda solução ótima necessariamente é uma solução viável; porém,
nem toda solução viável é, a rigor, uma solução ótima.
É importante destacar que nos PPL que estudaremos vamos nos deparar com
apenas uma solução ótima.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 12 / 50
Modelagem em Programação Linear Solução gráfica do PPL
Etapas solução gráfica do PPL
No exemplo (1), a companhia TNBRAS S/A precisa determinar os valores de x1∗ e
x2∗ que proporcione o lucro máximo por dia. Tais pontos podem ser encrontrado por
meio da solução gráfica, a qual pode ser sistematizada em 3 etapas.
1 Coordenadas do gráfico. Como estamos lidando com duas variáveis, podemos
encontrar a solução ótimo com auxílio de um gráfico bidimensional, onde
devemos plotar os valores de x2 no eixo vertical e os valores de x1 no eixo
horizontal.
2 Designação das restrições. Em seguida, precisamos analisar a designação de
cada uma das restrições do modelo até chegarmos a área ou espaço de solução
viável.
3 Determinação do ponto ótimo. A partir da determinação do espaço de solução
viável, localizaremos os pontos de interseção entre as restrições. Os valores de
x1 e x2 associados a estes pontos são soluções viáveis para o problema de PL.
Substituindo tais valores na função objetivo, encontraremos aquele (x1∗, x2∗)
que proporciona o lucro máximo, o ponto ótimo do PPL.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 13 / 50
Modelagem em Programação Linear Solução gráfica do PPL
Solução viável para o PPL da companhia TNBRAS S/A (1)
(0, 0) x1
x2
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 14 / 50
Modelagem em Programação Linear Solução gráfica do PPL
Solução viável para o PPL da companhia TNBRAS S/A (2a)
(0, 0) x1
x2
(0, 6)
(4, 0)
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 15 / 50
Modelagem em Programação Linear Solução gráfica do PPL
Solução viável para o PPL da companhia TNBRAS S/A (2b)
(0, 0) x1
x2
(0, 6)
(4, 0)
(0, 3)
(6, 0)
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 16 / 50
Modelagem em Programação Linear Solução gráfica do PPL
Solução viável para o PPL da companhia TNBRAS S/A (2c)
(0, 0) x1
x2
(0, 6)
(4, 0)
(0, 3)
(6, 0)
(0, 1)
(5, 6)
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 17 / 50
Modelagem em Programação Linear Solução gráfica do PPL
Solução viável para o PPL da companhia TNBRAS S/A (2d)
(0, 0) x1
x2
(0, 6)
(4, 0)
(0, 3)
(6, 0)
(0, 1)
(5, 6)
(0, 2)
(5, 2)
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 18 / 50
Modelagem em Programação Linear Solução gráfica do PPL
Solução viável para o PPL da companhia TNBRAS S/A (2e)
(0, 0) x1
x2
(0, 6)
(4, 0)
(0, 3)
(6, 0)
(0, 1)
(5, 6)
(0, 2)
(5, 2)(1, 2) (2, 2)
(3, 1.5)
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 19 / 50
Modelagem em Programação Linear Solução gráfica do PPL
Solução viável para o PPL da companhia TNBRAS S/A (3a)
O exágono na figura anterior delimita os segmentos de reta que unem as restrições.
Pontos dentro e sobre o exágono percetencem ao espaço de solução viável.
À medida que nos afastamos da origem do gráfico (mantendo-se nos limites do
espaço de solução viável) maiores serão os resultados de z. Assim, para encontrar o
ponto ótimo (x1∗, x2∗), vamos calcular os valores do lucro a partir de uma solução
inicial viável S0 : (0, 0). Os resultado estão na tabela abaixo.
Tabela: Determinação da solução ótima
Solução (x1, x2) z(x1, x2)
S0 (0; 0) 0
S1 (0; 1) 4.000
S2 (1; 2) 13.000
S3 (2; 2) 18.000
S4 (3; 1, 5) 21.000
S5 (4; 0) 20.000
Agora não é difícil determinar qual a solução ótima, (x1∗, x2∗) = (3; 1, 5).
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 20 / 50
Modelagem em Programação Linear Solução gráfica do PPL
Solução viável para o PPL da companhia TNBRAS S/A (3b)
x1
x2
S0 : (0, 0)
S1 : (0, 1)
S2 : (1, 2) S3 : (2, 2)
S4 : (3, 1.5)
S5 : (4, 0)
z = 13.000
z = 18.000
z = 21.000
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 21 / 50
Modelagem em Programação Linear Solução gráfica do PPL
Solução viável para o PPL da companhia TNBRAS S/A (3c)
Considerações Finais
A determinação da solução ótima requer identificar a direção na qual a
função objetivo aumenta (lembre-se que estamos maximizando z).
A solução ótima é estabelecida no ponto de tangência da função objetivo
com o vertice extremo da área de solução viável. Para o caso da
companhia TNBRAS S/A, tal ponto é (x1∗, x2∗) = (3; 1, 5). Se a
companhia prodizir diariamente 3 toneladas de tinta para exterior e 1,5
tonelada de tinta para interior, estará operando no ponto de lucro máximo
(z = R$21.000 por dia).
Uma característica importante nos problemas de PL é que a solução
ótima está sempre relacionada a um ponto extremo da região de solução
viável. Isso é válido até se, por acaso, a função objetivo for paralela a
uma restrição. Neste caso, qualquer ponto sobre determinado segmento
será uma alternativa ótima.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 22 / 50
Modelagem em Programação Linear Aplicações
Aplicações
1. Uma empresa Alpha que funciona 10 horas por dia fabrica dois produtos em três
processos sequenciais. A tabela abaixo resume os dados do problema.
Tabela: Dados técnicos da empresa Alpha
Produto Processo 1 Processo 2 Processo 3 LPU (R$)
1 10 6 8 2
2 5 20 10 3
LPU representa lucro por unidade (R$ 1,00) e os demais dados representam o tempo,
em minutos, que cada produto consome em cada processo. Determine o mix ótimo
dos dois produtos.
2. A Alumco fabrica chapas e barras de alumínio. A capacidade máxima de produção
estimada são 800 chapas ou 600 barras por dia. A demanda máxima diária são 550
chapas e 580 barras. O lucro por tonelada é de R$ 40 por chapa e R$ 35 por barra.
Determine o mix ótimo de produção diária.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 23 / 50
Modelagem em Programação Linear Aplicações
Aplicações
3. (WEBER, 1986, p.600)[2] Um fabricante produz bicicletas e motocicletas, cada
uma delas devendo ser processada em duas oficinas. A oficina 1 dispõe de no
máximo 120 horas e a oficina 2 dispõe de no máximo 180 horas. A fabricação de
uma bicicleta requer 6 horas na ofocina 1 e 3 horas na oficina 2. A fabricação de um
motocicleta requer 4 horas na ofocina 1 e 10 horas na oficina 2. Se o lucro médio de
uma bicicleta é de R$45, 00 e de uma motocicleta é de R$55, 00, determine o número
de bicicletas e motocicletas que devem ser fabricadas de forma a maximizar o lucro
total da empresa.
4. Um fabricante de móveis produz mesas e cadeiras. O departamento de serraria
corta madeira para ambos os produtos, que então é enviado separadamente para os
respectivos departamentos de montagem. Os itens montados são enviados ao
departamento de pintura para acabamento. A capacidade diária do departamento de
serraria é de 200 cadeiras e 80 mesas. O departamento de montagem de cadeiras pode
produzir 120 cadeiras por dia e o de montagem de mesas tem uma capacidade diária
de montagem de 60 mesas. A capacidade diária do departamento de pintura é de 150
cadeiras ou 110 mesas. Dado que o lucro por cadeira é de R$ 50 e o de cada mesa é
de R$ 100, determine o mix de produção ótimo para a empresa.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa OperacionalBelém-Pa, 23/02/2014 24 / 50
O Método Simplex
Sumário
1 Modelagem em Programação Linear
Especificação do modelo de PL
Solução gráfica do PPL
Aplicações
2 O Método Simplex
Introdução
Forma padrão do PPL
Cálculo do algoritmo simplex
Forma Geral do PPL
Aplicações
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 25 / 50
O Método Simplex Introdução
Introdução
O método simplex resolve PPL, melhorando o resultado da função objetivo (z),
a partir de uma solução viável inicial, que a rigor é o ponto de origem do plano
carteziano.
Em vez de enumerar todas as soluções básicas (conforme a solução gráfica) do
PPL, método simplex seleciona apenas algumas para ser investigadas.
Como se trata de um processo interativo, o método simplex também é chamado
de algoritmo simplex.
Para iniciar a interação do algoritmo simplex, o PPL deve estar escrito na forma
padrão, isto é, precisamos transformar as desigualdades das restrições em
igualdades. Isso pode ser feito com a adição de variáveis de folga.
O termo variável de folga está associado à folga na utilização do recurso. Por
exemplo:
Utilização de recurso ≤ Disponilidade
então,
Utilização de recurso + folga = Disponilidade
Portanto, a folga ≥ 0.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 26 / 50
O Método Simplex Forma padrão do PPL
Modelo na forma padrão
Vamos escrever o PPL da companhia TNBRAS S/A na forma padrão, introduzindo o
conceito de variável de folga.
Função objetivo:
Maximizar z = 5x1 + 4x2 + 0s1 + 0s2 + 0s3 + 0s4.
Sujeito a
6x1 + 4x2 + 1s1 + 0s2 + 0s3 + 0s4 = 24 (R1)
1x1 + 2x2 + 0s1 + 1s2 + 0s3 + 0s4 = 6 (R2)
−1x1 + 1x2 + 0s1 + 0s2 + 1s3 + 0s4 = 1 (R3)
0x1 + 1x2 + 0s1 + 0s2 + 0s3 + 1s4 = 2 (R4)
x1, x2, s1, s2, s3, s4 ≥ 0 (R5)
As variáveis s1, s2, s3 e s4 são as folgas associadas às respectivas restrições. Note a
função das folgas, elas servem para transformar inequações em equações; além disso,
sua inclusão no modelo permite tratar o PPL sob o cálculo matricial.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 27 / 50
O Método Simplex Forma padrão do PPL
Solução incial do PPL na forma padrão
Observe que o PPL forma padrão contém 4 equações de restrições e 6 variáveis
de decisão (inclusive as folgas).
Então, para obtermos uma solução para o sistema, é preciso atribuir valor zero
para algumas variáveis, as quais são chamadas de variáveis não-básicas. As
variáveis cujo valor é determinado pelo sistema (valores positivos) são
chamadas de variáveis básicas.
Veja o seguinte, partindo do ponto (x1, x2) = (0, 0), temos a seguinte solução
incial determinada pelo sistema:
z = 0
s1 = 24
s2 = 6
s3 = 1
s4 = 2
Portanto, as variáveis (zero) não básicas são: (x1, x2); e as variáveis básicas:
(s1, s2, s3, s4).
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 28 / 50
O Método Simplex Cálculo do algoritmo simplex
Cálculo do algoritmo simplex
Todo cálculo do algoritmo simplex é desenvolvido com base na tabela simplex.
A tabela simplex reflete a estrutura de uma matriz e para construí-la é preciso
igualar a função objetivo a zero.
Considerando:
variáveis (zero) não básicas: (x1, x2);
variáveis básicas: (s1, s2, s3, s4); e
substituindo (x1, x2) = (0, 0) no PPL, chegaremos à seguinte matriz.
Tabela: Algoritmo simplex - Solução inicial
Base z x1 x2 s1 s2 s3 s4 Solução
z 1 -5 -4 0 0 0 0 0
s1 0 6 4 1 0 0 0 24
s2 0 1 2 0 1 0 0 6
s3 0 -1 1 0 0 1 0 1
s4 0 0 1 0 0 0 1 2
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 29 / 50
O Método Simplex Cálculo do algoritmo simplex
Cálculo do algoritmo simplex
Observe que a solução inical (x1, x2) = (0, 0) está longe de ser ótima, mas é um
ponto de partida.
Afim de melhorar o desempenho da função objetivo, resta saber agora, qual
variável devemos primeiramente aumentar, x1 ou x2? Em outras palavras, qual
delas deve, nesse momento, ser introduzida à Base?
Esta é uma pergunta fácil de ser respondida, pois, intuitivamente, a variável que
deve ser introduzida à Base é aquela que proporciona o maior lucro por unidade
vendida (ou, a com maior coeficiente positivo). Esta é a condição de
otimalidade. Neste caso, a x1.
Então, se x1 deve entrar na Base, quem deve sair para dar lugar a x1?
Esta também é outra questão de fácil resposta. A determinação de quem sai da
Base segue a regra do cálculo das razões não negativas. Este cálculo é obtido
pela razão entre os valores da coluna Solução e o coeficiente de restrição
correspondente à variável que entra na Base. Neste caso, x1. Veja o cálculo na
tabela a seguir.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 30 / 50
O Método Simplex Cálculo do algoritmo simplex
Cálculo do algoritmo simplex
Tabela: Algoritmo simplex - Cálculo das razões não negativas
Base z x1 ↓ x2 s1 s2 s3 s4 Solução Teste da Razão Mínima
z 1 -5 -4 0 0 0 0 0 ...
← s1 0 6 4 1 0 0 0 24 x1 = 24/6 = 4 (mínimo)
s2 0 1 2 0 1 0 0 6 x1 = 6/1 = 6
s3 0 -1 1 0 0 1 0 1 x1 = 1/− 1 = −1 (ignorar)
s4 0 0 1 0 0 0 1 2 x1 = 2/0 =∞ (ignorar)
A razão mínima não negativa identifica automaticamente a variável s1 como a
variável que deve sair da Base e designa à variável x1 que entra na Base.
A interação é baseada na operação de Gauss-Jordan, que identifica a coluna da
variável que entre na Base (x1), chamada de coluna do pivô, e a linha da variável que
saí, chamada linha do pivô. A interseção da coluna do pivô com a linha do pivô é
chamada de elemento pivô. Neste caso, o elemento pivô = 6.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 31 / 50
O Método Simplex Cálculo do algoritmo simplex
Cálculo do algoritmo simplex
Os cálculos por Gauss-Jordan necessários para produzir a nova solução básica são de
dois tipos.
1 Linha do pivô
Substituir a variável que sai da base, na coluna Base, pela variável que
entra na base.
Nova linha do pivô = Linha do pivô atual× 1elemento pivô
2 Todas as outras linhas, inclusive z
Nova Linha = Linha Atual− (Seu coeficiente da coluna do pivô×
Nova linha do pivô).
Com base nestas regras e nas informações da tabela anterior, podemos proceder a
primeira interação para o algoritmo simplex. Os cálculos de Gauss-Jordan são
aplicados à tabela anterior da seguinte maneira.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 32 / 50
O Método Simplex Cálculo do algoritmo simplex
Cálculo do algoritmo simplex
Cálculo da primeira interação do algoritmo simplex
1b’) Nova Linha x1 = Linha s1 atual × 16
=
1
6
× [0 6 4 1 0 0 0 24]
= [0 1
2
3
1
6
0 0 0 4]
2a’) Nova Linha z = Linha z atual − (−5)× Nova Linha x1
= [1 − 5 − 4 0 0 0 0 0]− (−5)× [0 1 2
3
1
6
0 0 0 4]
= [1 0 − 2
3
5
6
0 0 0 20]
2b’) Nova Linha s2 = Linha s2 atual − (1)× Nova Linha x1
= [0 1 2 0 1 0 0 6]− (1)× [0 1 2
3
1
6
0 0 0 4]
= [0 0
4
3
− 1
6
1 0 0 2]
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 33 / 50
O Método Simplex Cálculo do algoritmo simplex
Cálculo do algoritmo simplex
Cálculo da primeira interação do algoritmo simplex
2c’) Nova Linha s3 = Linha s3 atual − (−1)× Nova Linha x1
= [0 − 1 1 0 0 1 0 1]− (−1)× [0 1 2
3
1
6
0 0 0 4]
= [0 0
5
3
1
6
0 1 0 5]
2d’) Nova Linha s4 = Linha s4 atual − (0)× Nova Linha x1
= [0 0 1 0 0 0 1 2]− (0)× [0 1 2
3
1
6
0 0 0 4]
= [0 0 1 0 0 0 1 2]
Com base nos resultados dos cálculos de Gauss-Jordan, podemos preencher a nova
tabela com a nova solução básica para (x1, s2, s3, s4).
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 34 / 50
O Método Simplex Cálculo do algoritmo simplex
Cálculo do algoritmo simplex
Tabela: Algoritmo simplex - Primeira interação
Base z x1 x2 ↓ s1 s2 s3 s4 Solução Teste da Razão Mínima
z 1 0 − 23 560 0 0 20 ...
x1 0 1 23
1
6 0 0 0 4 x2 = 4÷ 23 = 6
← s2 0 0 43 − 16 1 0 0 2 x2 = 2÷ 43 = 1, 5
s3 0 0 53
1
6 0 1 0 5 x2 = 5÷ 53 = 3
s4 0 0 1 0 0 0 1 2 x1 = 2/1 = 2
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 35 / 50
O Método Simplex Cálculo do algoritmo simplex
Cálculo do algoritmo simplex
Cálculo da segunda interação do algoritmo simplex
1b”) Nova Linha x2 = Linha s2 atual × 34
=
3
4
× [0 0 4
3
− 1
6
1 0 0 2]
= [0 0 1 − 1
8
3
4
0 0
3
2
]
2a”) Nova Linha z = Linha z atual − (−2
3
)× Nova Linha x2
= [1 0 − 2
3
5
6
0 0 0 20]− (−2
3
)× [0 0 1 − 1
8
3
4
0 0
3
2
]
= [1 0 0
3
4
1
2
0 0 21]
2b”) Nova Linha x1 = Linha x1 atual − (23 )× Nova Linha x2
= [0 1
2
3
1
6
0 0 0 4]− (2
3
)× [0 0 1 − 1
8
3
4
0 0
3
2
]
= [0 1 0
1
4
− 1
2
0 0 3]
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 36 / 50
O Método Simplex Cálculo do algoritmo simplex
Cálculo do algoritmo simplex
Cálculo da segunda interação do algoritmo simplex
2c”) Nova Linha s3 = Linha s3 atual − (53 )× Nova Linha x2
= [0 0
5
3
1
6
0 1 0 5]− (5
3
)× [0 0 1 − 1
8
3
4
0 0
3
2
]
= [0 0 0
3
8
− 5
4
1 0
5
2
]
2d”) Nova Linha s4 = Linha s4 atual − (1)× Nova Linha x2
= [0 0 1 0 0 0 1 2]− (1)× [0 0 1 − 1
8
3
4
0 0
3
2
]
= [0 0 0
1
8
− 3
4
0 1
1
2
]
Com base nos resultados dos cálculos de Gauss-Jordan, podemos preencher a nova
tabela com a nova solução básica para (x1, x2, s3, s4).
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 37 / 50
O Método Simplex Cálculo do algoritmo simplex
Cálculo do algoritmo simplex
Base z x1 x2 s1 s2 s3 s4 Solução Teste da Razão Mínima
z 1 0 0 34
1
2 0 0 21 ...
x1 0 1 0 14 − 12 0 0 3 x2 = 4÷ 23 = 6
x2 0 0 1 − 18 34 0 0 32 x2 = 2÷ 43 = 1, 5
s3 0 0 0 38 − 54 1 0 52 x2 = 5÷ 53 = 3
s4 0 0 0 18 − 34 0 1 12 x1 = 2/1 = 2
Tabela: Algoritmo simplex - Segunda interação
Com base na condição de otimalidade, em que nenhum dos coeficientes da linha z
associados com as variáveis não básicas, s1 e s2, é negativo; então, podemos concluir
que esta tabela simplex demonstra o resultado ótimo.
Outra fonte de indicação para o fim da interação está associada à presença da matriz
identidade relacionado ao vetor [z x1 x2].
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 38 / 50
O Método Simplex Cálculo do algoritmo simplex
Cálculo do algoritmo simplex
Considerações Finais
A solução ótima da tabela simplex mostra que a companhia TNBRAS
S/A deve diariamente 3 toneladas de tinta para exterior e 1,5 tonelada de
tinta para interior, para obter o lucro máximo (z = R$21.000 por dia).
Substitua os valores s1 = s2 = 0, s3 = 52 e s4 =
1
2 e verifique que os
valores de x1 e x2 são consistentes com o resultado da tabela simplex.
Se a folga de um dado recurso for zero, então o mesmo está sendo
totalmente utilizado e é classificado como um recurso escasso. Caso
contrário, se a folga é positiva, então o recurso é considerado abundante.
No caso da companhia TNBRAS S/A as matérias-prima M1 e M2 devem
ser consideradas escassas, pois s1 = s2 = 0. Por outro lado, há espaço
para explorar a demanda de mercado, pois s3 = 52 , s4 =
1
2 .
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 39 / 50
O Método Simplex Cálculo do algoritmo simplex
Etapas do método simplex
1 Determine a solução básica inicial viável.
2 Selecione a primeira variável que deve entrar na Base usando o critério
de otimalidade. Pare aqui se não houver nenhuma variável pra entrar na
base; a última solução é a ótima. Se não, passe ao próximo passo.
3 Selecione uma variável para sair da base usando a condição de
viabilidade, com base no cálculo das razões não negativas.
4 Determine a nova solução básica usando os cálculos de Gauss-Jordan
adequados. Passe para o passo 2.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 40 / 50
O Método Simplex Forma Geral do PPL
Forma generalizada do PPL
A generalização do PPL pode ser representada por.
Maximizar (Minimizar) z = c1x1 + c2x2 + · · ·+ cmxm =
m∑
j=1
cjxj. (6)
Sujeito às restrições
a11x1 + a12x2 + · · ·+ a1nxm ≤ b1 (7)
a21x1 + a22x2 + · · ·+ a2nxm ≤ b2
...
...
...
... ≤ ...
an1x1 + an2x2 + · · ·+ anmxm ≤ bn
x1, x2, · · ·, xm ≥ 0
b1, b2, · · ·, bn ≥ 0.
Em (6), z é o lucro (ou custo em casos de minimização), que depende das variáveis de
decisão xj e dos coeficientes cj, que representa o retorno líquido de cada produto. Em
(7), os elementos aij (sendo i = 1, ..., n a referência linha e j = 1, ...,m da coluna)
formam um conjunto de coeficientes técnicos; expressam o consumo de cada recurso
por unidade de produto. Os termos bi representam os recursos disponíveis.SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 41 / 50
O Método Simplex Forma Geral do PPL
Forma matricial do PPL
O modelo na forma generalizada pode ser representado na forma matricial.
Maximizar (Minimizar) z = CX′. (8)
Sujeito às restrições
AX′ ≤ B (9)
X ≥ 0
B ≥ 0
Em que:
C é o vetor (1× m) de margem de contribuição unitária.
X é o vetor (1× m) de variáveis de decisão.
A é a matriz (n× m) de coeficientes técnicos.
B é o vetor (n× 1) de demandas de recursos disponíveis (constantes independentes).
n é o número de restrições e m o número de variáveis de decisão.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 42 / 50
O Método Simplex Forma Geral do PPL
Modelo para utilização do Solver no Excel
Os PPL podem ser resolvidos com auxílio da rotina computacional Solver do MS
Excel, mas para tanto, é preciso estruturar os parâmetros de entrada (imput) do PPL,
bem como, os resultados de otimização (output), em uma planilha do MS Excel.
A tabela a seguir expõe um modelo alternativo para tratar da solução de PPL.
Tabela: Modelo para utilização do Solver no Excel
Função objetivo x1 x2 . . . xm Total
LPU (CPU) c1 c2 . . . cm
Lucro (Custo) z1 z2 . . . zm z
Restrições x1 x2 . . . xm AX′ Operador B
R1 a11 a12 . . . a1m
∑
a1x1 ≤,≥, <,>,= b1
R2 a21 a22 . . . a2m
∑
a2x2 ≤,≥, <,>,= b2
...
...
...
...
...
...
...
...
Rn an1 an2 · · · anm
∑
anxn ≤,≥, <,>,= bn
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 43 / 50
O Método Simplex Aplicações
Orientações para exercícios
Tente resolver os PPL relacionados aos exercícios de número 1 a 8 seguindo a
seguinte sistemática:
O problema. Descreva sucintamente o problema por que se depara a
empresa.
Identificação das variáveis. Identifique e descreve as variáveis de
decisão do problema.
Especificação do modelo. Especifique a função objetivo e as restrições
do modelo de programação linear.
Solução. Com auxílio do rotina computacional Solver do MS Excel
determine a solução ótima do PPL.
Conclusão. Interprete economicamente o resultado.
Obs.: nos exercícios 6 e 7 construa um gráfico bidimensional para
demosntrar o processo de interação até o ponto de solução ótima do PPL.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 44 / 50
O Método Simplex Aplicações
Exercícios
1) Uma pequena fábrica de papel toalha manufatura três tipos de produtos A, B e C.
A fábrica recebe o papel em grandes rolos. O papel é cortado, dobrado e empacotado.
Dada a pequena escala da fábrica, o mercado absorverá qualquer produção a um
preço constante. O lucro líquido de cada produto é respectivamente R$ 1,00, R$ 1,50,
e R$ 2,00. O quadro abaixo identifica o tempo requerido para operação (em horas)
em cada seção da fábrica, bem como a quantidade de máquinas disponíveis, que
trabalham 40 horas por semana. Planeje a produção semanal da fábrica.
Seção Produto A Produto B Produto C Qtde. MáquinasCorte 8 5 2 3
Dobra 5 10 4 10
Empacotamento 0,7 1 2 2
2) Uma fábrica de computadores produz dois modelos de microcomputadores, tipo A
e B. O modelo A fornece um lucro de R$ 180,00 e B, de R$ 300,00. O modelo A
requer, na sua produção, um gabinete pequeno e uma unidade de disco. O modelo B
requer 1 gabinete grande e 2 unidades de disco. Existem no estoque 60 do gabinete
pequeno, 50 do gabinete grande e 120 unidades de disco. Pergunta-se, qual deve ser o
esquema de produção que maximiza o lucro?
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 45 / 50
O Método Simplex Aplicações
Exercícios
3) Uma microempresa tem disponíveis os seguintes tecidos: 16 m2 de algodão, 11 m2
de seda e 15 m2 de lã. Para confeccionar um terno padrão, são necessários 2 m2 de
algodão, 1 m2 de seda e 1 m2 de lã. Para um vestido padrão, são necessários 1 m2 de
algodão, 2 m2 de seda e 3 m2 de lã. Se o lucro líquido de um terno é de R$ 300 e de
um vestido de R$ 500, quantas peças de cada tipo a microempresa deve fabricar para
ter o maior lucro possível?
4) Uma fábrica produz dois artigos A e B, que devem passar por duas máquinas
diferentes M1 e M2. M1 tem 12 horas de capacidade diária disponível e M2 tem 5
horas. Cada unidade de produto A requer 2 horas em ambas as máquinas. Cada
unidade de produto B requer 3 horas em M1 e 1 hora em M2. O lucro líquido de A é
de R$ 60,00 por unidade e o de B, R$ 70,00 por unidade. Determinar a quantidade a
ser produzida de A e B a fim de se ter um lucro máximo.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 46 / 50
O Método Simplex Aplicações
Exercícios
5) Uma oficina mecânica deseja alocar o tempo ocioso disponível em suas máquinas
para a produção de 3 produtos. A tabela abaixo dá as informações sobre as
necessidades de horas de máquina para produzir uma unidade de cada produto, assim
como a disponibilidade das máquinas, o lucro dos produtos e a demanda máxima
existente no mercado. Deseja-se o esquema semanal de produção de lucro máximo.
Tipo Máquina Produto A Produto B Produto C Tempo Disp.
Torno 5 3 5 400
Fresa 8 4 0 500
Furaeira 2 5 3 300
Lucro 20 15 18 ...
Demanda 40 50 20 ...
6) A Ozark Farms usa no mínimo 800 kg de ração especial por dia. Essa ração
especial é uma mistura de milho e soja com as seguintes composições:
Ração Proteina Fibra Custo (R$/kg)
Milho 0,09 0,02 0,30
Soja 0,60 0,06 0,90
Os requisitos nutricionais da ração especial são de no mínimo de 30% de proteína e
de no máximo de 5% de fibra. Determine a mistura que gera a ração de mínimo custo
diário.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 47 / 50
O Método Simplex Aplicações
Exercícios
7) Um pecuarista deseja obter uma dieta a base de ração para o gado, mas que
contenha os seguintes nutrientes: N1, N2, N3 e N4. A indústria local oferece dois tipos
de ração para gado, as do tipo R1 e R2. A tabela abaixo demonstra a quantidade de
nutriente por kg de ração.
Tipo de ração N1 N2 N3 N4
R1 0,10 0,00 0,10 0,20
R2 0,00 0,10 0,20 0,10
Sabe-se que o gado deve consumir diariamente, pelo menos 0,4 kg de N1, 0,6 Kg de
N2, 2 Kg de N3 e 1,7 kg de N4. A ração R1 custa R$ 80,00/kg e a ração R2 custa R$
32,00/kg. Determine as quantidades diárias consumidas de R1 e R2 por animal, de
modo a se obter o menor custo.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 48 / 50
O Método Simplex Aplicações
Exercícios
8) Um criador de coelhos alimenta os animais com cinco tipos de ração, cuja
composição de nutrientes (unidades/Kg) está demosntrada na tabela abaixo.
Nutrientes Ração A Ração B Ração C Ração D Ração E
Proteínas 30 20 15 80 20
Carboidratos 60 20 60 20 20
Gordura 5 10 5 3 2
Custo (R$/Kg) 0,20 0,30 0,40 0,50 0,25
Ele calculou as necessidades diárias de alimentação de cada animal, em pelo menos,
80 unidades de proteína, 120 unidades de carboidratos e 30 unidades de gordura.
Qual deve ser a mistura das rações que proporciona o menor custo para o criador?
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 49 / 50
O Método Simplex Aplicações
Bibliografia
TAHA, H. A.
Pesquisa operacional.
Pearson Prentice Hall, 2008.
WEBER, J., AND HARIKI, S.
Matemática para economia e administração.
Harbra, 1986.
SILVA,A.L.F. (UFPA/ICSA) Pesquisa Operacional Belém-Pa, 23/02/2014 50 / 50
	Modelagem em Programação Linear
	Especificação do modelo de PL
	Solução gráfica do PPL
	Aplicações
	O Método Simplex
	Introdução
	Forma padrão do PPL
	Cálculo do algoritmo simplex
	Forma Geral do PPL
	Aplicações