PO_Geral

Prévia do material em texto

Pesquisa Operacional
Alane Alves Silva
alaneaas@yahoo.com.br
2010
Alane Alves () P.O 2010 1 / 162
Pesquisa Operacional Introdução
Pesquisa Operacional
A análise científica do uso operacional de recursos militares de maneira
sistemática foi iniciada na Segunda Guerra Mundial. As equipes
estavam envolvidas em problemas de operações de guerra, como
manutenção e inspeção de aviões, escolha do tipo de avião para uma
missão e melhoria na probabilidade de destruição de submarinos. Além
do controle de artilharia antiaérea e dimensionamento de frota.
A aplicação do método científico e de ferramentas matemáticas em
operações militares passou a ser chamado de Pesquisa Operacional.
Hoje em dia, Pesquisa Operacional é enfoque científico para
Problemas de Decisão.
Alane Alves () P.O 2010 2 / 162
Pesquisa Operacional Introdução
Pesquisa Operacional
Dois fatores se destacam para o rápido crescimento da pesquisa
operacional nesse período.
Melhorias das técnicas da pesquisa operacional.
Revolução computacional.
Alane Alves () P.O 2010 3 / 162
Pesquisa Operacional Introdução
Definições
Desenvolvimento de métodos científicos de sistemas complexos, com a
finalidade de prever e comparar estratégias ou decisões alternativas. O
objetivo é dar suporte à definições de políticas e determinações de
ações de forma científica.
A Pesquisa Operacional significa abordagem científica para tomada de
decisões, que procura determinar como melhor projetar e operar um
sistema usualmente sob condições que requerem a alocação de
recursos escassos.
De forma sucinta, pode-se dizer que a pesquisa operacional é um
enfoque científico sobre a tomada de decisões.
Alane Alves () P.O 2010 4 / 162
Pesquisa Operacional Introdução
Denominação
A denominação pesquisa operacional é comumente motivo de críticas e
reflexões, pois não revela a abrangência da área e pode dar a falsa
impressão de estar limitada à análise de operações. Existem diversos
sinônimos para Pesquisa Operacional. Os ingleses gostam de operational
research (pesquisa operacional), enquanto os americanos usam
operations research (pesquisa de operações). Um outro termo usado
pelos americanos é management science (ciência da administração).
Alane Alves () P.O 2010 5 / 162
Pesquisa Operacional Introdução
Exemplos de Problemas de Decisão
Em diversas áreas do mundo real existe escassez de um certo produto ou
matéria-prima por sua dificuldade de produção e/ou de obtenção, entre
outras razões.
Busca-se maximizar ou minimizar uma quantidade (Lucro, Receita, Custo,
número de produtos, etc.) chamada de objetivo, que depende de um ou
mais recursos escassos.
Determinação de Mix de Produtos.
Escalonamento de Produção.
Roteamento e Logística.
Planejamento Financeiro.
Carteira de Investimento.
Análise de Projetos.
Alocação de Pessoas.
Designação de Equipes.
Alane Alves () P.O 2010 6 / 162
Pesquisa Operacional Introdução
Modelo
Um modelo é uma representação de um sistema real, que pode já existir ou
ser um projeto aguardando execução. No primeiro caso, o modelo pretende
reproduzir o funcionamento do sistema, de modo a aumentar sua
produtividade. No segundo caso, o modelo é utilizado para definir a
estrutura ideal do sistema.
A confiança na solução obtida através do modelo depende da validação do
modelo na representação do sistema real.
Alane Alves () P.O 2010 7 / 162
Pesquisa Operacional Introdução
Estrutura dos Modelos Matemáticos
Num modelo matemático são incluídos três conjuntos de elementos:
• Variáveis de Decisão e Parâmetros: as variáveis de decisão são as
incógnitas a serem determinadas pela solução do modelo e os
parâmetros são valores fixos no problema.
• Restrições: de modo a levarmos em conta as limitações físicas do
sistema, o modelo deve incluir restrições que limitam as variáveis de
decisão a seus valores possíveis (ou viáveis).
• Função Objetivo: é uma função matemática que define a qualidade
da solução em função das variáveis de decisão. É um critério de
escolha das variáveis de decisão representado por uma função.
Alane Alves () P.O 2010 8 / 162
Pesquisa Operacional Introdução
Estrutura dos Modelos Matemáticos
Pode-se dizer que:
O problema do modelo matemático de Pesquisa Operacional é escolher os
valores das variáveis de decisão de forma a obter o melhor resultado da
função objetivo sujeita às restrições especificadas.
Alane Alves () P.O 2010 9 / 162
Pesquisa Operacional Introdução
Estrutura dos Modelos Matemáticos
Vejamos o seguinte exemplo para melhor compreendermos os conjuntos de
elementos:
Situação Atual: R$ 90.000,00 no Caixa
Situação Desejada: R$ 90.000,00 bem aplicados
Ações da Tele Mundo custam R$ 50,00 e o retorno esperado é de R$
6,00/ano.
Ações da Cosmo Fone custam R$ 30,00 e o retorno esperado é de R$
4,00/ano.
A Diretoria não quer que se aplique mais de R$ 60.000,00 em ações de
uma só companhia.
Alane Alves () P.O 2010 10 / 162
Pesquisa Operacional Introdução
Estrutura dos Modelos Matemáticos
Variáveis de decisão
As quantidades investidas em cada ação (CF e TM).
Parâmetros
Os preços e retorno de cada ação.
Restrições
São as limitações impostas pela diretoria e pela quantidade de dinheiro
disponível para investir.
Função Objetivo
Função matemática que determine o retorno em função das variáveis de
decisão e que deve ser maximizada.
Alane Alves () P.O 2010 11 / 162
Pesquisa Operacional Introdução
Estrutura dos Modelos Matemáticos
Max 4, 00CF+ 6, 00TM (1)
sujeito a:
30, 00CF + 50, 00TM ≤ 90.000, 00 (2)
30, 00CF ≤ 60.000, 00 (3)
50, 00TM ≤ 60.000, 00 (4)
TM ≥ 0 (5)
CF ≥ 0 (6)
Alane Alves () P.O 2010 12 / 162
Pesquisa Operacional Introdução
Técnicas Matemáticas em PO
A formulação do modelo depende diretamente do sistema a ser
representado.
A função objetivo e as funções de restrições podem ser lineares
ou não-lineares.
As variáveis de decisão podem ser contínuas ou discretas e os
parâmetros podem ser determinísticos ou probabilísticos.
Alane Alves () P.O 2010 13 / 162
Pesquisa Operacional Introdução
Técnicas Matemáticas em PO
Existem muitas técnicas de otimização para resolver os diferentes tipos de
modelos existentes:
Programação linear
Programação inteira
Programação dinâmica
Programação estocástica
Programação não-linear
Alane Alves () P.O 2010 14 / 162
Pesquisa Operacional Introdução
Fases de estudo em Pesquisa Operacional
1 Definição do problema
2 Construção do Modelo
3 Solução do modelo
4 Validação do Modelo
5 Implementação do Modelo
A definição do problema baseia-se em três aspectos principais:
descrição exata dos objetivos do estudo
identificação das alternativas de decisão existentes
reconhecimento das limitações, restrições e exigências do sistema
Alane Alves () P.O 2010 15 / 162
Pesquisa Operacional Introdução
Fases de estudo em Pesquisa Operacional
Construção do Modelo
A escolha apropriada do modelo é fundamental para a qualidade da solução
fornecida. Se o modelo elaborado tem a forma de um modelo conhecido, a
solução pode ser obtida através de métodos matemáticos convencionais.
Por outro lado, se as relações matemáticas são muito complexas, talvez
seja necessário a utilização de combinações de metodologias.
Solução do Modelo
O objetivo desta fase é encontrar uma solução para o modelo proposto
através da utilização das técnicas mais adequadas e que forneçam o
resultado “ótimo” em menor tempo possível.
Alane Alves () P.O 2010 16 / 162
Pesquisa Operacional Introdução
Fases de estudo em Pesquisa Operacional
Validação do Modelo
Há necessidade de validar os modelos de modo a poder se aceitar as
soluções propostas. Um modelo é valido, dentro de limites razoáveis, se ele
for capaz de fornecer uma previsão aceitáveldo comportamento do sistema.
Implementação da Solução
Avaliadas as vantagens e a validação da solução obtida, esta deve ser
convertida em regras operacionais. A implementação é uma das etapas
críticas do estudo.
Alane Alves () P.O 2010 17 / 162
Pesquisa Operacional Introdução
Observação
Um tema comum na PO é a busca de uma solução ótima. É necessário que
fique claro que estas soluções são ótimas apenas em relação ao modelo que
está sendo usado. Como o modelo é apenas uma representação da
realidade não existe nenhuma garantia que a solução ótima para o modelo
se comprovará como a melhor solução possível que poderia ter sido
implementada para o problema real. Porém, se o modelo for bem
formulado e testado, as soluções tendem a ser uma boa representação para
a solução a ser adotada no caso real.
Alane Alves () P.O 2010 18 / 162
Pesquisa Operacional Introdução
Outros Exemplos
Exemplo 1
Uma empresa pode fabricar dois produtos (1 e 2). Na fabricação do
produto 1 a empresa gasta nove horas-homem e três horas-máquina (a
tecnologia utilizada é intensiva em mão-de-obra). Na fabricação do
produto 2 a empresa gasta uma hora-homem e uma hora-máquina (a
tecnologia é intensiva em capital). Sendo x1 e x2 as quantidades fabricadas
dos produtos 1 e 2 e sabendo-se que a empresa dispõe de 18 horas-homem
e 12 horas-máquina e ainda que os lucros dos produtos são $4 e $1
respectivamente, quanto deve a empresa fabricar de cada produto para
obter o maior lucro possível (ou o lucro máximo ou ainda maximizar o
lucro) ?
Alane Alves () P.O 2010 19 / 162
Pesquisa Operacional Introdução
Transformando os Dados em Expressões
Matemáticas
A Função Lucro
Admitindo que a função lucro é uma função linear de x1 e x2 ou seja:
L = 4x1 + x2
esse lucro deve ser maximizado por uma escolha de x1 e x2
Max
x1,x2
L = 4x1 + x2
Se o problema parasse aqui o lucro seria ilimitado. Porém, existem recursos
limitados.
Restrições
H-H 9x1 + x2 ≤ 18
H-M 3x1 + x2 ≤ 12
x1 ≥ 0; x2 ≥ 0
Alane Alves () P.O 2010 20 / 162
Pesquisa Operacional Introdução
Exemplo 2
Uma empresa fabril está interessada em maximizar o lucro mensal
proveniente de quatro de seus produtos, designados por I , II , III e IV . Para
fabricar esses quatro produtos, ele utiliza dois tipos de máquinas (M1 e
M2) e dois tipos de mão-de-obra (MO1 e MO2) com as seguintes
disponibilidades:
Máquinas Tempo disponível a
M1 800
M2 200
aMáquina-hora/mês
Mão-de-Obra Tempo disponível a
MO1 12000
MO2 16000
aHomem-hora/mês
Alane Alves () P.O 2010 21 / 162
Pesquisa Operacional Introdução
O setor técnico da empresa fornece os seguintes quadros de produtividade:
a) Número de máquinas-hora para
produzir uma unidade de cada
produto:
Máquina Produto
I II III IV
M1 5 4 8 9
M2 2 6 — 10
Para se produzir uma unidade do
produto I consome-se 5
máquinas-hora da M1 e 2
máquinas-hora da máquina M2.
b) Número de homem-hora para
produzir uma unidade de cada
produto:
Mão-de-obra Produto
I II III IV
MO1 2 4 2 8
MO2 7 3 — 7
Alane Alves () P.O 2010 22 / 162
Pesquisa Operacional Introdução
O setor comercial da empresa fornece as seguintes informações:
Produtos Potencial de Vendas Lucro Unitário
I 70 10
II 60 8
III 40 9
IV 20 7
Deseja-se saber a produção mensal dos produtos I , II , III e IV para que o
lucro mensal da empresa, proveniente desses quatro produtos, seja máximo.
Formule um modelo de programação linear que expresse o objetivo e as
restrições dessa empresa.
Alane Alves () P.O 2010 23 / 162
Pesquisa Operacional Introdução
Solução
Sejam x1, x2, x3, x4 as produções mensais dos produtos I , II , III e IV ,
respectivamente. O modelo será:
MaxZ = 10x1 + 8x2 + 9x3 + 7x4
sujeito a:
x1 ≤ 70
x2 ≤ 60
x3 ≤ 40
x4 ≤ 20
5x1 + 4x2 + 8x3 + 9x4 ≤ 800
2x1 + 6x2 + 10x4 ≤ 200
2x1 + 4x2 + 2x3 + 8x4 ≤ 12000
7x1 + 3x2 + 7x4 ≤ 16000
x1 ≥ 0 x2 ≥ 0 x3 ≥ 0 x4 ≥ 0
Alane Alves () P.O 2010 24 / 162
Programação Linear
Programação Linear
Alane Alves () P.O 2010 25 / 162
Programação Linear Introdução
Programação Linear
Um problema de Programação Linear(PL) é um problema de programação
matemática em que as Funções Objetivos e de Restrição são lineares.
O problema geral pode se definido por
Maximizar(ou Minimizar)
Z = c1x1 + c2x2 + · · ·+ cnxn
sujeito a:
a11x1 + a12x2 + · · ·+ a1nxn ≤ b1(ou ≥, ou =)
a21x1 + a22x2 + · · ·+ a2nxn ≤ b2(ou ≥, ou =)
. . . . . . . . .
am1x1 + am2x2 + · · ·+ amnxn ≤ bm(ou ≥, ou =)
x1, x2, . . . , xn ≥ 0
Alane Alves () P.O 2010 26 / 162
Programação Linear Introdução
Forma Reduzida
Max(Min)Z =
n∑
j=1
cjxj (7)
sujeito a:
n∑
j=1
aijxj ≤ bi (i = 1, 2, 3, . . .m) (8)
x1, x2, . . . , xn ≥ 0 (9)
Alane Alves () P.O 2010 27 / 162
Programação Linear Introdução
Algumas Definições
Solução
Qualquer especificação de valores para as variáveis de decisão,
independente de se tratar de uma escolha desejável ou permissível.
Solução Viável
Uma solução em que todas as restrições são satisfeitas.
O conjunto de todos os pontos que satisfazem todas as restrições é
chamado de Conjunto Viável.
Solução Ótima
Uma solução viável que tem o valor mais favorável da função objetivo, isto
é, maximiza ou minimiza a função objetivo em toda a região viável,
podendo ser única ou não.
Alane Alves () P.O 2010 28 / 162
Programação Linear Solução Gráfica
Solução Gráfica
Quando o problema envolve apenas duas variáveis de decisão, a solução
ótima de um problema de PL pode ser encontrado graficamente.
MaxZ = 5x1 + 2x2
sujeito a:
x1 ≤ 3
x2 ≤ 4
x1 + 2x2 ≤ 9
x1, x2 ≥ 0
x1 + 2x2 ≤ 9
Solução
Viável
x1 ≤ 3
x2 ≤ 4
x2 ≥ 0
x1 ≥ 0
x1
x2
A(0, 0)
E(0, 4)
D(1, 4)
C(3, 3)
B(3, 0)
Alane Alves () P.O 2010 29 / 162
Programação Linear Solução Gráfica
Procura da Solução Ótima
b
bb b b
bb
bbb
x1
x2
A(0, 0)
E(0, 4)
D(1, 4)
C(3, 3)
B(3, 0)
Z = 0
Z = 10
Z = 20
Alane Alves () P.O 2010 30 / 162
Programação Linear Hipótese
Hipóteses da Programação Linear
Proporcionalidade
A contribuição de cada variável ao valor da função objetivo é proporcional
ao valor da variável, conforme representado pelo termo cjxj na função
objetivo.
De modo semelhante, a contribuição de cada variável às restrições é
proporcional ao valor da variável xj , como representado pelo termo aijxj na
restrição.
Aditividade
Toda função em um modelo de programação linear é a soma das
contribuições individuais das respectivas variáveis.
Alane Alves () P.O 2010 31 / 162
Programação Linear Hipótese
Hipóteses da Programação Linear
Divisibilidade
As variáveis de decisão em um modelo de programação linear podem
assumir quaisquer valores, inclusive valores não-inteiros, que satisfaçam as
restrições funcionais e de não-negatividade.
Quando as variáveis do modelo de programação linear só puderem assumir
valores inteiros, deve-se impor estas condições no próprio modelo.
Passa-se, então, a lidar com um modelo de programação linear inteira.
Certeza
O valor atribuído a cada parâmetro de um modelo de programação linear é
assumido como uma constante conhecida.
Alane Alves () P.O 2010 32 / 162
Programação Linear Teoremas
Teoremas
Teorema
O conjunto de todas as soluções viáveis de um modelo de PL é um conjunto
convexo.
Teorema
Toda solução viável básica do sistema de equações lineares de um modelo de PL é
um ponto extremo do conjunto de soluções viáveis.
Teorema
Se uma função objetivo possui um único ponto de ótimo finito, então este é um
ponto extremo do conjunto convexo de soluções viáveis.
Teorema
Se a função objetivo assume o valor ótimo em mais de um ponto do conjunto de
soluções viáveis (soluções múltiplas), então ela assume este valor para pelo menosdois pontos extremos do conjunto convexo e para qualquer combinação convexa
desses pontos extremos, isto é, todos os pontos do segmento de reta que une
estes dois pontos, ou seja, a aresta do polígono que contém estes dois pontos.
Alane Alves () P.O 2010 33 / 162
Programação Linear Teoremas
Problema de Mistura
O problema da mistura consiste em obter uma mistura que contenha os
nutrientes necessários e apresente o mínimo custo.
Suponha que um agricultor queira adubar a sua plantação e disponha de dois
tipos de adubo. O adubo tipo A possui 6g de fósforo, 2g de nitrogênio e 16g de
potássio para cada kg , a um custo de $20 por kg . Já o adubo B possui 4g de
fósforo, 6g de nitrogênio e 4g de potássio para cada kg , a um custo de $16 por
kg .
Sabe-se que o solo em que estão as suas plantações necessita de pelo menos 60g
de fósforo, 30g de nitrogênio e 80g de potássio a cada 100m2 de terra.
Desenvolver um modelo matemático de programação linear que permita
determinar quantos kg de cada tipo de adubo são necessários para adubar 100m2
de terra a um mínimo custo.
Alane Alves () P.O 2010 34 / 162
Programação Linear Teoremas
MinZ = 20x1 + 16x2
sujeito a:
6x1 + 4x2 ≥ 60
2x1 + 6x2 ≥ 30
16x1 + 4x2 ≥ 80
x1, x2 ≥ 0
Solução
Viável
I
II
III
x1
x2
Alane Alves () P.O 2010 35 / 162
Programação Linear Teoremas
Solução
Vértices Adubo A Adubo B Custo Total
(0;20) 0 20 320
(2;12) 2 12 232
(8,57;2,14) 8,57 2,14 205,6
(15;0) 15 0 300
Alane Alves () P.O 2010 36 / 162
Programação Linear Teoremas
Restrições Redundantes
Uma restrição é dita redundante quando sua exclusão do conjunto de
restrições, de um problema, não altera o conjunto de soluções viáveis deste.
MaxZ = 4x1 + 3x2
sujeito a:
x2 ≤ 2
x1 + 3x2 ≤ 7
2x1 + 2x2 ≤ 8
x1 + x2 ≤ 3
x1, x2 ≥ 0
Solução
Viável
x1 + x2 ≤ 3
x1 + 3x2 ≤ 7
2x1 + 2x2 ≤ 8
x2 ≥ 2
x1
x2
Alane Alves () P.O 2010 37 / 162
Programação Linear Teoremas
Procura da Solução Ótima
b
bb b b
bbb
x1
x2
Z = 0
Z = 12
Alane Alves () P.O 2010 38 / 162
Programação Linear Teoremas
Problema com Múltiplas Soluções
Um problema de programação linear pode também apresentar mais de uma
solução ótima, um ou mais conjuntos de valores produzem igual valor
máximo (ou mínimo) na função objetivo.
MaxZ = x1 + x2
sujeito a:
x2 ≤ 2
x1 + 3x2 ≤ 7
x1 + x2 ≤ 3
x1, x2 ≥ 0
Solução
Viável
x1 + 3x2 ≤ 7
x1 + x2 ≤ 3
x2 ≥ 2
x1
x2
Alane Alves () P.O 2010 39 / 162
Programação Linear Teoremas
Procura da Solução Ótima
b
bb b b
b
Soluções
Ótimas
bb
x1
x2
Z = 0
Z = 3
Alane Alves () P.O 2010 40 / 162
Programação Linear Teoremas
Exemplo
A Whitt Window é uma empresa com apenas três funcionários que fazem
dois tipos de janelas feitas à mão: uma com esquadria de alumínio e outra
com esquadria de madeira. Eles têm um lucro de R$60 por janela com
esquadria de madeira e de R$30 para janela com esquadria de alumínio.
João faz as de esquadria de madeira e é capaz de construir seis delas por
dia. Maria faz as janelas com esquadrias de alumínio e é capaz de fazer
quatro delas por dia. Roberto monta e corta os vidros e é capaz de fazer
48m2/dia. Cada janela com esquadria de madeira usa 6m2 de vidro e cada
janela com esquadria de alumínio usa 8m2 de vidro.
A empresa quer determinar quantas janelas de cada tipo de esquadria
podem ser fabricadas diariamente para maximizar o lucro total.
Alane Alves () P.O 2010 41 / 162
Programação Linear Teoremas
Exemplo
A Agro Industria SA produz três tipos de enlatados, cada um exigindo um
tratamento industrial semelhante, mas que difere na sua duração. Assim,
cada 1000 caixas de sopa de tomate exigem 200 horas de mão-de-obra e 6
horas de operação dos equipamentos; cada 1000 caixas do suco de tomate
exigem 80 horas de mão-de-obra e 4 horas dos equipamentos, e cada 1000
caixas do molho de tomate exigem 300 horas de mão-de-obra e 7 horas de
equipamentos. Sabe-se que a empresa tem disponível, por semana, 5000
horas de mão-de-obra e 168 de equipamentos disponíveis. Sabe-se que o
lucro por cada caixa produzida da sopa, suco e molho, é de R$ 3, R$2,5 e
R$ 1, respectivamente.
Supondo-se que a empresa deseja maximizar seu lucro, pede-se a
formulação do problema de programação linear.
Alane Alves () P.O 2010 42 / 162
Método Simplex
Método Simplex
Alane Alves () P.O 2010 43 / 162
Método Simplex Introdução
Método Simplex
Algoritmo criado para se obter a solução algebricamente.
Seqüência finita de passos que se seguidas levam ao objetivo
procurado.
É necessário conhecer o método para se interpretar melhor os
resultados.
Se as desigualdades fossem igualdades, as restrições seriam um
conjunto de equações lineares e essa nós sabemos resolver.
Consegue-se isso acrescentando a cada restrição uma variável a mais,
essas novas variáveis são chamadas de variáveis de folga, para
restrições do tipo ≤. (Existem também as chamadas variáveis de
excesso, para restrições do tipo ≥).
Alane Alves () P.O 2010 44 / 162
Método Simplex Introdução
MaxZ = 5x1 + 2x2
sujeito a:
x1 ≤ 3
x2 ≤ 4
x1 + 2x2 ≤ 9
x1, x2 ≥ 0
MaxZ = 5x1 + 2x2
sujeito a:
x1 + x3 = 3
x2 + x4 = 4
x1 + 2x2 + x5 = 9
x1, x2, x3, x4, x5 ≥ 0
1 As variáveis originais do problema são as não básicas e as variáveis de folga
são as básicas.
2 Essas novas variáveis, também devem ser maiores ou iguais a zero para
garantir a exigência das restrições.
3 Caso a restrição fosse, por exemplo, x1 + 2x2 ≥ 9 a introdução seria
x1 + 2x2 − x5 = 9, com x5 ≥ 0.
Alane Alves () P.O 2010 45 / 162
Método Simplex Introdução
A função objetivo é uma equação e não uma inequação logo não
precisamos introduzir variáveis de folga.
Pode-se reescrever o sistema da seguinte forma:
Z − 5x1 − 2x2 = 0
x1 + x3 = 3
x2 + x4 = 4
x1 + 2x2 + x5 = 9
Alane Alves () P.O 2010 46 / 162
Método Simplex Introdução
x1 x2 x3 x4 x5 Constantes
Z -5 -2 0 0 0 0
x3 1 0 1 0 0 3
x4 0 1 0 1 0 4
x5 1 2 0 0 1 9
Solução Viável Básica Inicial
x3 = 3 x1 = 0
x4 = 4 x2 = 0
x5 = 9 Z = 0
Alane Alves () P.O 2010 47 / 162
Método Simplex Introdução
O próximo passo é verificar se a solução encontrada já é a solução ótima.
A solução será ótima se não houver coeficientes com valores negativos na
linha correspondente a função objetivo.
No exemplo, como tem-se −5 e −2 a solução ainda não é ótima.
Deve-se encontrar a variável fora da base que tenha o coeficiente mais
negativo.
Logo quem deve entrar na base é x1 que tem o coeficiente mais negativo
entre as variáveis não básicas (x1 e x2).
Para determinar a variável que irá sair da base, precisa-se conhecer a variável
que mais restringe o crescimento da variável que entrará na base.
Como apenas uma variável não básica trocará de valor de cada vez, o que
importa são os coeficientes da coluna da variável que vai entrar na base.
Calcula-se, para essas linhas, a divisão do valor da constante pelo coeficiente
correspondente. O resultado que apresentar o menor valor apontará a
variável a sair da base.
Alane Alves () P.O 2010 48 / 162
Método Simplex Introdução
x1 x2 x3 x4 x5 Constantes Divisão
Z -5 -2 0 0 0 0
x3 1 0 1 0 0 3 3
x4 0 1 0 1 0 4
x5 1 2 0 0 1 9 9
x3 será a variável que vai sair da base pois na divisão apresentou o menor
valor.
Nova Linha Pivô =
Antiga Linha Pivô
Num. Pivô
x1 x2 x3 x4 x5 Constantes Divisão
Z
x1 1 0 1 0 0 3 3
x4
x5
Alane Alves () P.O 2010 49 / 162
Método Simplex Introdução
Nova Linha 1 = Antiga Linha 1− (Coef. da Col. Pivô)(Nova linha Pivô)
Nova l1 = Antiga l1 − 5l2
x1 x2 x3 x4 x5 Constantes
Z 0 -2 5 0 0 15
x1 1 0 1 0 0 3
x4
x5
Nova Linha 3 = Antiga Linha 3− (Coef. da Col. Pivô)(Nova linha Pivô)
Nova l3 = Antiga l3 − 0l2
Vamosrepetir a linha 3 pois o coeficiente da linha pivô é zero.
x1 x2 x3 x4 x5 Constantes
Z 0 -2 5 0 0 15
x1 1 0 1 0 0 3
x4 0 1 0 1 0 4
x5
Alane Alves () P.O 2010 50 / 162
Método Simplex Introdução
Nova Linha 4 = Antiga Linha 4− (Coef. da Col. Pivô)(Nova linha Pivô)
Nova l4 = Antiga l4 − 1l2
x1 x2 x3 x4 x5 Constantes
Z 0 -2 5 0 0 15
x1 1 0 1 0 0 3
x4 0 1 0 1 0 4
x5 0 2 -1 0 1 6
A nova tabela ainda tem um coeficiente negativo na linha 1 (−2). Logo, essa
ainda não é a solução ótima. Assim, tem-se que repetir os passos anteriores.
Dessa vez a variável que entra na base é x2, pois tem o coeficiente negativo e a
variável que sai é x5.
O quadro ótimo será:
x1 x2 x3 x4 x5 Constantes
Z 0 0 4 0 1 21
x1 1 0 1 0 0 3
x4 0 0 0,5 1 -0,5 1
x2 0 1 -0,5 0 0,5 3
Alane Alves () P.O 2010 51 / 162
Método Simplex Introdução
Como todos os coeficientes da linha 1 são não negativos, isto significa que
atingiu-se a solução ótima para o problema. A solução encontrada foi:
x1 = 3, x2 = 3, x3 = 0, x4 = 1, x5 = 0 e Z = 21
Alane Alves () P.O 2010 52 / 162
Método Simplex Introdução
Resumo do Método
1.Inicialização
Introduza variáveis de folga. Selecione as variáveis de decisão para serem
variáveis não-básicas (configure-as para ficarem iguais a zero) e as variáveis
de folga para serem variáveis básicas.
2.Teste de Otimalidade
A atual solução básica viável é ótima se e somente se todos os coeficientes
da primeira linha forem não-negativos (≥ 0). Se verdadeiro pare; caso
contrário, realize uma iteração para obter a próxima solução básica viável,
que envolve mudar uma variável não-básica para uma variável básica e
vice-versa e depois se chegar a nova solução.
Alane Alves () P.O 2010 53 / 162
Método Simplex Introdução
Resumo do Método
3.Iteração
Passo 1
Determinar a variável básica que entra na base selecionando aquela com o
coeficiente “mais negativo” (maior valor absoluto). A coluna
correspondente a esta variável será denominada coluna pivô.
Alane Alves () P.O 2010 54 / 162
Método Simplex Introdução
Resumo do Método
3.Iteração
Passo 2
Determine a variável que básica que sai da base aplicando o teste da razão
mínima.
Selecione cada coeficiente na coluna pivô que seja estritamente
positivo (> 0).
Divida cada um dos elementos da coluna das constantes pelos
coeficientes da coluna pivô nas respectivas linhas.
Identifique a linha que possui a menor dessas razões.
A variável básica para esta linha é a variável básica que sai.
Passo 3
Encontre a nova solução básica usando operações elementares em linhas
Alane Alves () P.O 2010 55 / 162
Método Simplex Adaptando a Outras Formas do Modelo
Adaptando a Outras Formas do Modelo
Variável Sem Restrição de Sinal
Suponha que uma certa variável x1 possa assumir valores positivos ou
negativos. Nesse caso deve-se substituí-la por:
x1 = x
′
1 + x
′′
1
onde: x ′1 ≥ 0 e x
′′
1 ≥ 0
Lado Direito Negativo
Basta multiplicar a expressão por −1.
Transformação de uma Igualdade
Uma igualdade pode ser reescrita como duas desigualdades. Por exemplo:
x1 = 10
equivale a: x1 ≤ 10 x1 ≥ 10
Alane Alves () P.O 2010 56 / 162
Método Simplex Casos Especiais
Casos Especiais
1.Empate na Entrada
Quando houver empate na escolha da variável que entra na base, deve-se
tomar a decisão arbitrariamente. A única implicação envolvida é que se
pode escolher uma caminho mais longo ou mais curto para se chegar à
solução ótima.
Alane Alves () P.O 2010 57 / 162
Método Simplex Casos Especiais
Casos Especiais
2.Empate na Saída
Como no caso anterior, a decisão deve ser também arbitrária. Observe o
exemplo a seguir:
MaxZ = 5x1 + 2x2
sujeito a:
x1 ≤ 3
x2 ≤ 4
4x1 + 3x2 ≤ 12
x1, x2 ≥ 0
Alane Alves () P.O 2010 58 / 162
Método Simplex Casos Especiais
Casos Especiais
x1 ↓ x2 x3 x4 x5 Constantes
Z -5 -2 0 0 0 0
x3 1 0 1 0 0 3
x4 0 1 0 1 0 4
x5 4 3 0 0 1 12
Para escolher a variável que sai da base deve-se fazer:
x3 ⇒
3
1
x5 ⇒
12
4
Nos dois casos tem-se o resultado da divisão igual a 3. Escolhe-se
arbitrariamente, x3 para sair da base.
Alane Alves () P.O 2010 59 / 162
Método Simplex Casos Especiais
Casos Especiais
x1 x2 ↓ x3 x4 x5 Constantes
Z 0 -2 5 0 0 15
x1 1 0 1 0 0 3
x4 0 1 0 1 0 4
← x5 0 3 -4 0 1 0
Note que no quadro anterior a variável básica x5 é nula. Isso sempre
ocorrerá quando houver empate na saída. Quando isso ocorre diz-se que a
solução viável encontrada é degenerada.
Alane Alves () P.O 2010 60 / 162
Método Simplex Casos Especiais
Casos Especiais
x1 x2 x3 x4 x5 Constantes
Z 0 0 7/3 0 2/3 15
x1 1 0 1 0 0 3
x4 0 0 4/3 1 -1/3 4
x2 0 1 -4/3 0 1/3 0
Do ponto de vista teórico, a degeneração tem duas implicações.
Fenômeno da ciclagem ou retorno cíclico — ao realizar-se as
iterações no método simplex o valor da função objetivo não melhora,
sendo possível que o método entre em uma seqüência de iterações sem
nunca melhorar o valor da função objetivo e nunca satisfazer a
condição de otimalidade.
Iterações distintas, embora com classificações diferentes de suas
variáveis como básicas e não básicas, resultam em valores idênticos
para o valor da função objetivo.
Alane Alves () P.O 2010 61 / 162
Método Simplex Casos Especiais
Casos Especiais
3.Soluções Múltiplas
Em algumas situações um modelo de programação linear pode apresentar
mais de uma solução ótima.
Considere o seguinte exemplo:
MaxZ = 2x1 + 4x2
sujeito a:
x1 + 2x2 ≤ 5
x1 + x2 ≤ 4
x1, x2 ≥ 0
Alane Alves () P.O 2010 62 / 162
Método Simplex Casos Especiais
Casos Especiais
x1 x2 ↓ x3 x4 Constantes
Z -2 -4 0 0 0
← x3 1 2 1 0 5
x4 1 1 0 1 4
x1 ↓ x2 x3 x4 Constantes
Z 0 0 2 0 10
x2 1/2 1 1/2 0 5/2
← x4 1/2 1 -1/2 1 3/2
A solução é ótima e tem-se x1 = 0, x2 = 5/2 e Z = 10
Observe os coeficientes das variáveis não básicas da linha (0). O
coeficiente de x1 (não básica) é zero, o que indica que a variável x1 pode
entrar na base, e qualquer que seja o valor que ela assuma, a função
objetivo ficará com seu valor inalterado, mas causando uma mudança nos
valores das variáveis.
Alane Alves () P.O 2010 63 / 162
Método Simplex Casos Especiais
Casos Especiais
x1 x2 x3 x4 Constantes
Z 0 0 2 0 10
x2 0 1 1 -1 1
x1 1 0 -1 2 3
Deixando x1 entrar na base e forçando x4 a sair a nova solução ocorre em
x1 = 3, x2 = 1 e Z = 10. Ou seja, para pontos distintos o valor da função
objetivo não se altera.
Por um dos teoremas visto anteriormente pode-se afirmar que qualquer
combinação convexa dessas duas soluções também será uma solução ótima
para o modelo.
Alane Alves () P.O 2010 64 / 162
Método Simplex Casos Especiais
Casos Especiais
4. Função Objetivo Ilimitado
Outro resultado possível é aquele no qual nenhuma variável se
qualifica para ser a variável básica a deixar a base.
Este resultado poderia ocorrer se a variável que entra na base pudesse
ser aumentada indefinidamente sem dar valores negativos a qualquer
uma das variáveis básicas atuais. Na forma tabular, isso significa que
todos os coeficientes da coluna pivô (excluindo-se a linha a linha do
funcional objetivo) são negativos ou então zero.
Neste caso, as restrições não impedem que o valor da função objetivo
cresça indefinidamente.
Isto ocorre, provavelmente, porque o modelo foi mal formulado, seja
por omitir restrições relevantes, seja por declará-las de modo incorreto.
Alane Alves () P.O 2010 65 / 162
Método Simplex Casos Especiais
Casos Especiais
5.Problema de Minimização
Quando a função objetivo tiver de ser minimizada pode-se fazer duas
coisas, a saber:
Inverter o teste de otimização e o critério de entrada na base. Assim,
se todos os coeficientes da linha (0) forem negativos, ou nulos, a
presente solução é ótima. Caso contrário, escolha a variável xj para
entrarna base que apresente o maior valor.
Transformar o problema de minimização em um problema de
maximização. Sabe-se que achar o mínimo de uma função é
equivalente a achar o máximo do simétrico dessa função.
MinW = 2x1 + 3x2 − 5x3
equivale a: MaxZ = −2x1 − 3x2 + 5x3 e depois, na solução final,
fazer W = −Z
Alane Alves () P.O 2010 66 / 162
Método Simplex Solução Inicial Artificial
Solução Inicial Artificial
Suponha o seguinte problema:
MaxZ = 5x1 + 2x2
sujeito a:
x1 ≤ 3
x2 ≤ 4
x1 + 2x2 ≥ 9
x1, x2 ≥ 0
MaxZ = 5x1 + 2x2
sujeito a:
x1 + x3 = 3
x2 + x4 = 4
x1 + 2x2 − x5 = 9
x1, x2 . . . , x5 ≥ 0
Variáveis não-básicas: x1 = x2 = 0
Variáveis básicas: x3 = 3; x4 = 4 e x5 = −9
Essa não é uma solução viável pois x5 deveria ser maior que zero.
Alane Alves () P.O 2010 67 / 162
Método Simplex Solução Inicial Artificial
Solução Inicial Artificial
Para se obter uma solução inicial viável pode-se acrescentar uma variável
artificial na última equação. Essa variável x6 tomará o lugar de x5 na base
inicial. Assim, obtém-se:
MaxZ = 5x1 + 2x2
sujeito a:
x1 + x3 = 3
x2 + x4 = 4
x1 + 2x2 − x5 + t1 = 9
x1, x2, . . . x5, t1 ≥ 0
Variáveis não-básicas:
x1 = x2 = x5 = 0
Variáveis básicas:
x3 = 3; x4 = 4 e t1 = 9
Obs.:
1 Os sistemas só serão equivalentes se a variável artificial t1 for nula.
2 As variáveis artificiais não têm significado algum para o problema real,
mas permitem a inicialização do processo de maneira automática.
Alane Alves () P.O 2010 68 / 162
Método Simplex Método do M-Grande
Processo do M Grande
Como as variáveis artificiais não são parte do modelo original, recebem
punições muito altas na função objetivo, o que as força a ter valor igual a
zero na função objetivo.
Regra de Penalização das Variáveis Artificiais
Dado M, um valor positivo suficientemente alto (M →∞), o coeficiente
na função objetivo de uma variável artificial representa uma punição se:
Coeficiente na função objetivo da variável artificial ={
M em problemas de minimização
−M em problemas de maximização
Alane Alves () P.O 2010 69 / 162
Método Simplex Método do M-Grande
Processo do M Grande
Qual o valor de M que deve ser utilizado?
Vai depender dos dados do problema original. O valor de M deve ser
suficientemente grande em relação aos coeficientes da função objetivo
original, de modo que agirá como uma punição que força as vaiáveis
artificiais a ter valor zero na solução ótima.
Alane Alves () P.O 2010 70 / 162
Método Simplex Método do M-Grande
Processo do M Grande
Considere o exemplo anterior:
MaxZ = 5x1 + 2x2 −Mt1
sujeito a:
x1 + x3 = 3
x2 + x4 = 4
x1 + 2x2 − x5 + t1 = 9
x1, x2, . . . x5, t1 ≥ 0
MaxZ = 5x1 + 2x2 − 100t1
sujeito a:
x1 + x3 = 3
x2 + x4 = 4
x1 + 2x2 − x5 + t1 = 9
x1, x2, . . . x5, t1 ≥ 0
No exemplo, os coeficientes de x1 e x2 na função objetivo são 5 e 2,
respectivamente. Portanto, parece razoável estabelecer M = 100.
Alane Alves () P.O 2010 71 / 162
Método Simplex Método do M-Grande
x1 x2 x3 x4 x5 t1 cte
Z -5 -2 0 0 0 100 0
x3 1 0 1 0 0 0 3
x4 0 1 0 1 0 0 4
t1 1 2 0 0 -1 1 9
Na solução inicial x3 = 3, x4 = 4 e t1 = 9. Como
Z = 5x1 + 2x2 − 100t1 tem-se Z = −900.
Como t1 é uma variável básica tem-se o elemento pivô igual a um e
todos os elementos da coluna pivô iguais a zero.
x1 x2 ↓ x3 x4 x5 t1 cte
Z -105 -202 0 0 0 0 -900
x3 1 0 1 0 0 0 3
← x4 0 1 0 1 0 0 4
t1 1 2 0 0 -1 1 9
Alane Alves () P.O 2010 72 / 162
Método Simplex Método do M-Grande
x1 ↓ x2 x3 x4 x5 t1 cte
Z -105 0 0 202 100 0 -92
x3 1 0 1 0 0 0 3
x2 0 1 0 1 0 0 4
← t1 1 0 0 -2 -1 1 1
x1 x2 x3 x4 ↓ x5 t1 cte
Z 0 0 0 -8 -5 105 13
← x3 0 0 1 2 1 -1 2
x2 0 1 0 1 0 0 4
x1 1 0 0 -2 -1 1 1
Alane Alves () P.O 2010 73 / 162
Método Simplex Método do M-Grande
x1 ↓ x2 x3 x4 x5 t1 cte
Z 0 0 4 0 -1 101 21
← x4 0 0 1/2 1 1/2 -1/2 1
x2 0 1 -1/2 0 -1/2 1/2 3
x1 1 0 1 0 0 0 3
x1 x2 x3 x4 x5 t1 cte
Z 0 0 5 2 0 100 23
x5 0 0 1 2 1 -1 2
x2 0 1 0 1 0 0 4
x1 1 0 1 0 0 0 3
Alane Alves () P.O 2010 74 / 162
Método Simplex Método das Duas Fases
Método das Duas Fases
Quando uma solução viável básica não é encontrada facilmente, o método
das Duas fases mostra-se como uma alternativa ao método do M-Grande.
No método das Duas Fases variáveis artificiais são introduzidas às
restrições da mesma forma que é feito no método do M-grande.
Fase I
A primeira fase consiste em resolver um problema de minimização cuja
função objetivo é a soma de todas as variáveis artificiais e esta sujeita às
restrições do problema original. Quando a solução ótima for atingida, duas
situações podem ocorrer:
Resolvendo este problema encontra-se uma solução viável básica para o
problema de PL original.
Fase II
Use a solução viável da Fase I como uma solução básica viável inicial para
o problema original.
Alane Alves () P.O 2010 75 / 162
Método Simplex Método das Duas Fases
Método das Duas Fases
Considere o seguinte exemplo:
MaxZ = 4x1 + x2
sujeito a:
3x1 + x2 = 3
4x1 + 3x2 ≥ 6
x1 + 2x2 ≤ 4
x1, x2 ≥ 0
MaxZ = 4x1 + x2
sujeito a:
3x1 + x2 = 3
4x1 + 3x2 − x3 = 6
x1 + 2x2 + x4 = 4
x1, x2, . . . x4 ≥ 0
Alane Alves () P.O 2010 76 / 162
Método Simplex Método das Duas Fases
Método das Duas Fases
Como o problema não apresenta uma solução viável básica as variáveis
artificiais serão introduzidas para todas as restrições do tipo (≥) ou =.
MaxZ = 4x1 + x2
sujeito a:
3x1 + x2+t1 = 3
4x1 + 3x2 − x3+t2 = 6
x1 + 2x2 + x4 = 4
x1, x2, . . . x4, t1, t2 ≥ 0
t1 e t2 são as variáveis artificiais.
Alane Alves () P.O 2010 77 / 162
Método Simplex Método das Duas Fases
Método das Duas Fases
O funcional objetivo original será então:
W = t1 + t2
Fase I
MinW = t1 + t2
sujeito a:
3x1 + x2 + t1 = 3
4x1 + 3x2 − x3 + t2 = 6
x1 + 2x2 + x4 = 4
x1, x2, . . . x4, t1, t2 ≥ 0
Alane Alves () P.O 2010 78 / 162
Método Simplex Método das Duas Fases
Método das Duas Fases
Exemplo
x1 x2 x3 x4 t1 t2 cte
-W 0 0 0 0 1 1 0
t1 3 1 0 0 1 0 3
t2 4 3 -1 0 0 1 6
x4 1 2 0 1 0 0 4
Como t1 e t2 estão na base alguns ajustes precisam ser feitos antes de dar
início ao método simplex.
↓ x1 x2 x3 x4 t1 t2 cte
-W -7 -4 1 0 0 0 -9
← t1 3 1 0 0 1 0 3
t2 4 3 -1 0 0 1 6
x4 1 2 0 1 0 0 4
Alane Alves () P.O 2010 79 / 162
Método Simplex Método das Duas Fases
Método das Duas Fases
x1 ↓ x2 x3 x4 t1 t2 cte
-W 0 -5/3 1 0 7/3 0 -2
x1 1 1/3 0 0 1/3 0 1
← t2 0 5/3 -1 0 -4/3 1 2
x4 0 5/3 0 1 -1/3 0 3
x1 x2 x3 x4 t1 t2 cte
-W 0 0 0 0 1 1 0
x1 1 0 1/5 0 3/5 -1/5 3/5
x2 0 1 -3/5 0 -4/5 3/5 6/5
x4 0 0 1 1 1 1 1
Alane Alves () P.O 2010 80 / 162
Método Simplex Método das Duas Fases
Método das Duas Fases
Note-se que no último quadro o valor mínimo de W é igual a zero.
A fase I produz a seguinte solução básica viável:
x1 = 3/5 x2 = 6/5 x4 = 1
Neste ponto as variáveis artificiais concluíram sua missão e pode-se
eliminar totalmente suas colunas(e linhas quando for o caso) da última
tabela e passar para a Fase II.
Alane Alves () P.O 2010 81 / 162
Método Simplex Método das Duas Fases
Método das Duas Fases
Fase II
Após eliminar as colunas artificiais, reescrevesse o problema original como:
MaxZ = 4x1 + x2
sujeito a:
x1 + 1/5x3 = 3/5
x2 − 3/5x3 = 6/5
x3 + x4 = 1
x1, x2, . . . x4 ≥ 0
Alane Alves () P.O 2010 82 / 162
Método Simplex Método das Duas Fases
Método das Duas Fases
x1 x2 x3 x4 cte
Z -4 -1 0 0 0
x1 1 0 1/5 0 3/5
x2 0 1 -3/5 0 6/5
x4 0 0 1 1 1
Alane Alves () P.O 2010 83 / 162
Programação Linear Método Simplex usando Excel
Programação Linear
Método Simplex usando Excel
Alane Alves () P.O 2010 84 / 162
Programação Linear Método Simplex usando Excel
MaxZ = 10x1 + 5x2 + 5, 5x3
sujeito a:
30x1 + 10x2+ 50x3 ≤ 1500
5x1 + 3x3 ≤ 200
0, 2x1 + 0, 1x2 + 0, 5x3 ≤ 12
0, 1x1 + 0, 2x2 + 0, 3x3 ≤ 9
x1, x2, x3 ≥ 0
Alane Alves () P.O 2010 85 / 162
Programação Linear Método Simplex usando Excel
Figure: Procedimento de procura da solução ótima.
Alane Alves () P.O 2010 86 / 162
Programação Linear Método Simplex usando Excel
Fórmulas inseridas na tabela do excel.
Célula = Fórmula
B6 = B3 ∗ B5 + C3 ∗ C5 + D3 ∗ D5
E10 = B10 ∗ B5 + C10 ∗ C5 + D10 ∗ D5
E11 = B11 ∗ B5 + C11 ∗ C5 + D11 ∗ D5
E12 = B12 ∗ B5 + C12 ∗ C5 + D12 ∗ D5
E13 = B13 ∗ B5 + C13 ∗ C5 + D13 ∗ D5
Alane Alves () P.O 2010 87 / 162
Programação Linear Método Simplex usando Excel
Para resolver o problema escolha Solver no menu Ferramentas:
Figure: Tela de ativação da ferramenta solver.
Alane Alves () P.O 2010 88 / 162
Programação Linear Método Simplex usando Excel
–Indicar a célula que contém a função objetivo e informar se queremos
maximizar, minimizar ou atingir valor pré-determinado:
Figure: Janela da ferramenta solver.
– Indicar as células que contém as variáveis:
Alane Alves () P.O 2010 89 / 162
Programação Linear Método Simplex usando Excel
–Informar as restrições: na área entitulada Adicionar Restrições clique no
botão Adicionar.
Figure: Janela de entrada de restrições.
O passo seguinte será o de clicar em OK, no caso de não haver mais
restrições a serem adicionadas ou Adicionar caso ainda existam restrições
a adicionar.
Figure: Restrições de não-negatividade.
Alane Alves () P.O 2010 90 / 162
Programação Linear Método Simplex usando Excel
Figure: Janela de entrada de parâmetros do solver.
Alane Alves () P.O 2010 91 / 162
Programação Linear Método Simplex usando Excel
— Finalizar a descrição do problema: clique no botão Opções para
terminar a especificação do modelo. Você deverá selecionar as opções
presumir modelo linear e presumir não negativos:
Figure: Opção de não negatividade.
Alane Alves () P.O 2010 92 / 162
Programação Linear Método Simplex usando Excel
Uma vez inserido o modelo e suas características, deve-se efetivamente
resolve-lo. Para tanto basta clicar no botão Resolver na janela de
parâmetros da ferramenta Solver.
Se o modelo foi corretamente inserido, será processado e o resultado
será automaticamente exibido na planilha.
Se observarmos valores incoerentes ou inesperados, devemos neste
ponto clicar na opção Restaurar Valores Originais para restaurar os
valores e iniciais do modelo.
Figure: Opções de resultado da ferramenta.
Alane Alves () P.O 2010 93 / 162
Programação Linear Método Simplex usando Excel
Figure: Resultado inserido na planilha.
Alane Alves () P.O 2010 94 / 162
Programação Linear Método Simplex usando Excel
Decisões do Tipo Fazer ou Comprar
A LCL Motores, uma fábrica de motores especiais, recebeu recentemente
R$900.000,00 em pedidos de seus três tipos de motores. Cada motor
necessita de um determinado número de horas de trabalho no setor de
montagem e de acabamento. A LCL pode terceirizar parte da sua
produção. A tabela a seguir resume estes dados. A LCL deseja determinar
quantos motores devem ser produzidos em sua fábrica e quantos devem ser
produzidos de forma terceirizada para atender a demanda de pedidos.
Modelo 1 2 3 Total
Demanda 3000 unid 2500 unid 500 unid 6000 unid
Montagem 1h/unid 2h/unid 0,5h/unid 60000h
Acabamento 2,5h/unid 1h/unid 4h/unid 10000h
Custo Produção 50 90 120
Terceirizado 65 92 140
Alane Alves () P.O 2010 95 / 162
Programação Linear Método Simplex usando Excel
MinZ = 50x1 + 90x2 + 120x3 + 65t1 + 92t2 + 140t3
sujeito a:
x1 + 2x2 + 0, 5x3 ≤ 6000
2, 5x1 + x2 + 4x3 ≤ 10000
x1 + t1 = 3000
x2 + t2 = 2500
x3 + t3 = 500
x1, x2, x3, t1, t2, t3 ≥ 0
Alane Alves () P.O 2010 96 / 162
Programação Linear Método Simplex usando Excel
Alane Alves () P.O 2010 97 / 162
Programação Linear Método Simplex usando Excel
Fórmulas inseridas na tabela do excel.
Célula = Fórmula
B7 = B4 + B5
C7 = C4 + C5
D7 = D4 + D5
E17 = B17 ∗ B4 + C17 ∗ C4 + D17 ∗ D4
E18 = B18 ∗ B4 + C18 ∗ C4 + D18 ∗ D4
B20 = B12 ∗ B4 + C12 ∗ C4 + D12 ∗ D4 + B13 ∗ B5 + C13 ∗ C5 + D13 ∗ D5
Alane Alves () P.O 2010 98 / 162
Programação Linear Método Simplex usando Excel
Escolha da Carteira de Investimentos
A LCL Investimentos gerencia recursos de terceiros através da escolha de carteiras
de investimentos para diversos clientes, baseados em bonds de diversas empresas.
Um de seus clientes exige que:
Não mais de 25% do total aplicado deve ser investido em um único
investimento;
Um valor superior a 50% do total aplicado dever ser investido em títulos de
maturidade maiores que dez anos;
O total aplicado em títulos de alto risco deve ser, no máximo, de 50% do
total investido.
A tabela mostra os dados dos títulos selecionados. Determine qual o percentual
do total deve ser aplicado em cada tipo de título.
Título Retorno Anual Anos para Vencimento Risco
1 8,7% 15 1–Muito Baixo
2 9,5% 12 3– Regular
3 12% 8 4–Alto
4 9% 7 2–Baixo
5 13% 11 4–Alto
6 20% 5 5–Muito Alto
Alane Alves () P.O 2010 99 / 162
Programação Linear Método Simplex usando Excel
Solução
x1 = Percentual aplicado no título do tipo 1
x2 = Percentual aplicado no título do tipo 2
x3 = Percentual aplicado no título do tipo 3
x4 = Percentual aplicado no título do tipo 4
x5 = Percentual aplicado no título do tipo 5
x6 = Percentual aplicado no título do tipo 6
A Função Objetivo deverá ser dada por
MaxZ = 0, 087
( x1
100
)
+ 0, 095
( x2
100
)
+ 0, 12
( x3
100
)
+ 0, 09
( x4
100
)
+ 0, 13
( x5
100
)
+ 0, 2
( x6
100
)
Alane Alves () P.O 2010 100 / 162
Programação Linear Método Simplex usando Excel
Restrição de Orçamento
x1 + x2 + x3 + x4 + x5 + x6 = 100
Restrição de Aplicação Máxima por Tipo de Título
x1 ≤ 25; x2 ≤ 25; x3 ≤ 25; x4 ≤ 25; x5 ≤ 25; x6 ≤ 25
Restrição de Aplicação Mínima em Títulos com Maturidade Maior
que 10 anos
x1 + x2 + x5 ≥ 50
Restrição de Aplicação Máxima em Títulos de Alto Risco
x3 + x5 + x6 ≤ 50
Alane Alves () P.O 2010 101 / 162
Programação Linear Método Simplex usando Excel
MODELO
MaxZ = 0, 087
( x1
100
)
+ 0, 095
( x2
100
)
+ 0, 12
( x3
100
)
+ 0, 09
( x4
100
)
+ 0, 13
( x5
100
)
+ 0, 2
( x6
100
)
x1 + x2 + x3 + x4 + x5 + x6 = 100
x1 ≤ 25; x2 ≤ 25; x3 ≤ 25; x4 ≤ 25; x5 ≤ 25; x6 ≤ 25
x1 + x2 + x5 ≥ 50
x3 + x5 + x6 ≤ 50
x1, x2, x3, x4, x5, x6 ≥ 0
Alane Alves () P.O 2010 102 / 162
Programação Linear Método Simplex usando Excel
Alane Alves () P.O 2010 103 / 162
Programação Linear Método Simplex usando Excel
Célula = Fórmula
B10 = B3 ∗ D3 + B4 ∗ D4 + B5 ∗ D5 + B6 ∗ D6 + B7 ∗ D7 + B8 ∗ D8
D11 = SOMA(B3:B8)
F10 = B3 + B4 + B7
H10 = B5 + B7 + B8
Alane Alves () P.O 2010 104 / 162
Dualidade
Dualidade
Alane Alves () P.O 2010 105 / 162
Dualidade Introdução
A cada modelo de PL corresponde um outro modelo denominado DUAL.
O problema DUAL é um modelo associado ao original, que traz uma
interpretação econômica para os valores de recursos e para os coeficientes
da função objetivo.
Os dois problemas guardam uma relação tão estreita que a solução ótima
de um problema fornece automaticamente a solução ótima do outro.
Alane Alves () P.O 2010 106 / 162
Dualidade Introdução
Construção
1 As variáveis de decisão do Dual: a cada restrição do primal será
associado uma variável yi .
2 A função objetivo do Dual é de minimização ao passo que a Primal é
de maximização.
3 Os coeficientes da função objetivo do dual são os termos constantes
das restrições do primal.
4 Os termos constantes das restrições do dual são os coeficientes da
função objetivo do primal.
5 As restrições do dual são do tipo ≥, ao passo que as do primal são de
≤.
6 O númerode variáveis do dual é igual ao número de restrições do
primal.
7 O número de restrições do dual é igual ao número de variáveis do
primal.
Alane Alves () P.O 2010 107 / 162
Dualidade Introdução
PRIMAL
MaxZ = 25x1 + 20x2
sujeito a:
x1 + x2 ≤ 50 (y1)
2x1 + x2 ≤ 80 (y2)
2x1 + 5x2 ≤ 220 (y3)
x1, x2 ≥ 0
DUAL
MinZ = 50y1 + 80y2 + 220y3
sujeito a:
y1 + 2y2 + 2y3 ≥ 25
y1 + y2 + 5y3 ≥ 20
y1, y2, y3 ≥ 0
Alane Alves () P.O 2010 108 / 162
Dualidade Introdução
PRIMAL
MaxZ =
n∑
j=1
cjxj
sujeito a:
n∑
j=1
aijxj ≤ bi (i = 1, . . . ,m)
xj ≥ 0
DUAL
MinD =
m∑
i=1
biyi
sujeito a:
m∑
i=1
aijyi ≥ cj(j = 1, . . . , n)
yi ≥ 0
Alane Alves () P.O 2010 108 / 162
Dualidade Introdução
Razões para o Estudo dos Problemas Duais
1 A primeira e mais importante são as interpretações econômicas que
pode-se obter dos valores das variáveis do Dual na solução ótima.
2 Algumas vezes é mais eficiente resolver o problema dual do que o
primal correspondente, já que, obtendo a solução ótima de um, esta-se
obtendo a do outro.
Alane Alves () P.O 2010 108 / 162
Dualidade Propriedades
Propriedades
1 O dual do dual é o primal.
2 Se a restrição k do primal é de igualdade, então a variável yk do dual
é sem restrição de sinal.
3 Se a restrição k do primal é maior ou igual a variável yk do dual é não
positiva.
4 Se a variável xp do primal é não positiva, então a restrição p do dual é
menor ou igual.
5 Se a variável xp do primal é sem restrição de sinal, então a restrição p
do dual é uma igualdade.
Alane Alves () P.O 2010 109 / 162
Dualidade Teoremas
Teoremas
Teorema I
Se o problema Primal e o Dual tiveram soluções viáveis, então Z ≤ D para
qualquer solução viável do primal e qualquer solução viável do Dual.
Teorema II (Propriedade Forte da Dualidade)
Se tanto o Primal quanto o Dual tiverem soluções viáveis tais que Z = D,
então elas constituem soluções ótimas.
Alane Alves () P.O 2010 110 / 162
Dualidade Teoremas
PRIMAL
MaxZ = 5x1 + 2x2
sujeito a: x1 ≤ 3 (y1)
x2 ≤ 4 (y2)
x1 + 2x2 ≤ 9 (y3)
x1, x2 ≥ 0
DUAL
MinZ = 3y1 + 4y2 + 9y3
sujeito a: y1 + y3 ≥ 5
y2 + 2y3 ≥ 2
y1, y2, y3 ≥ 0
Considere as seguintes soluções viáveis para o dual e para o primal.
x1 = 2 y1 = 3
x2 = 3 y2 = 3
y3 = 2
Z = 5(2) + 2(3) = 16 Z = 16 ≤ 39 = D
D = 3(3) + 4(3) + 9(2) = 39
Z ≤ D
Alane Alves () P.O 2010 111 / 162
Dualidade Teoremas
Considere agora as seguintes soluções viáveis para o dual e para o primal.
x1 = 3 y1 = 4
x2 = 3 y2 = 0
y3 = 1
Z = 5(3) + 2(3) = 21
D = 3(4) + 4(0) + 9(1) = 21
Como Z = D = 21 pode-se afirmar que essas duas soluções são ótimas
para o primal e dual
x∗1 = 3 y
∗
1 = 4
x∗2 = 3 y
∗
2 = 0
Z ∗ = 21 y∗3 = 1
D∗ = 21
Alane Alves () P.O 2010 112 / 162
Dualidade Teoremas
Teorema da Folga Complementar
Seja o problema primal representado pelo seguinte quadro inicial:
x1 x2 . . . xn xn+1 xn+2 . . . xn+m cte
Z −c1 −c2 . . . −cn 0 0 0 0 0
xn+1 a11 a12 . . . a1n 1 0 . . . 0 b1
xn+2 a21 a22 . . . a2n 0 1 0 0 b2
...
...
...
...
...
xn+m am1 am2 . . . amn 0 0 . . . 0 bm
xj , j = 1, . . . , n → são as variáveis do primal.
xn+i , i = 1, . . . ,m → são as variáveis de folga do primal.
Para o dual tem-se
yi , i = 1, . . . ,m → são as variáveis do dual.
ym+j , j = 1, . . . , n → são as variáveis de folga do primal.
Alane Alves () P.O 2010 113 / 162
Dualidade Teoremas
Teorema da Folga Complementar
Seja o problema primal representado pelo seguinte quadro inicial:
x1 x2 . . . xn xn+1 xn+2 . . . xn+m cte
Z c j = pj − cj cn+i = pn+i
Obtida a solução ótima do primal pelo método Simplex, então, o teorema
da folga complementar será:
O valor ótimo da variável yi do dual é igual ao coeficiente na linha
zero ótima da variável de folga xn+i do primal, isto é
y∗i = p
∗
n+i (i = 1, 2, . . . ,m)
O valor ótimo da variável de folga ym+j do dual é igual ao coeficiente
na linha zero ótima, da variável xj do primal, isto é,
y∗m+j = p
∗
j − cj (j = 1, 2, . . . , n)
Alane Alves () P.O 2010 114 / 162
Análise de Sensibilidade
Relatórios do Excel
Considere o problema a seguir:
MaxZ = 40x1 + 50x2
sujeito a:
x1 + 2x2 ≤ 10
2x1 + 5x2 ≤ 16
x1, x2 ≥ 0
Sua modelagem no Excel e os parâmetros e opções do Solver utilizados
para resolvê-lo estão apresentados nas figuras a seguir.
Alane Alves () P.O 2010 115 / 162
Análise de Sensibilidade
Análise de Sensibilidade
Alane Alves () P.O 2010 116 / 162
Análise de Sensibilidade
Análise de Sensibilidade
Alane Alves () P.O 2010 117 / 162
Análise de Sensibilidade
Análise de Sensibilidade
Após o comando de otimização ter sido dado, a seguinte janela será
apresentada para o usuário. Deve-se marcar os relatórios, clicando com o
mouse nos três relatórios disponíveis para obter-se as análises de
sensibilidade.
Alane Alves () P.O 2010 118 / 162
Análise de Sensibilidade
Análise de Sensibilidade
Existem três relatórios no Excel. São eles:
Relatório de Respostas (Answer Report)
Relatório de Sensibilidade (Sensitivity Report)
Relatório de Limites (Limits Report)
Alane Alves () P.O 2010 119 / 162
Análise de Sensibilidade
Relatório de Respostas
A figura a seguir mostra o Relatório de Respostas do problema que acabou
de ser otimizado.
Figure: Relatório de Respostas.
Alane Alves () P.O 2010 120 / 162
Análise de Sensibilidade
Relatório de Respostas
O relatório tem três partes distintas.
Célula de Destino
Indica o tipo de problema de otimização tratado (Máx ou Mín).
Valor original (inicial) e final da função objetivo.
Bem como a célula utilizada para representá-la.
Células ajustáveis
Apresenta os valores iniciais e finais das variáveis de decisão e as
células utilizadas para defini-las.
Alane Alves () P.O 2010 121 / 162
Análise de Sensibilidade
Restrições
A terceira parte do Relatório de Respostas diz respeito às restrições.
A coluna das células indica as células utilizadas para representar os
lados esquerdos de cada uma das restrições.
A coluna de valor das células indica os valores dos lados esquerdos de
cada uma das restrições.
A coluna Fórmula indica as fórmulas utilizadas nas restrições.
A coluna Status pode apresentar-se de duas formas:
Agrupar – significa que os lados direito e esquerdo das restrições são
iguais quando os valores da solução são substituídos na fórmula das
restrições.
Sem agrupar – ocorre quando os lados direito e esquerdo das
restrições não são iguais ao substituir os valores ótimos da solução.
Pode ocorrer o caso em que os valores dos lados da restrição são
diferentes e constar como Sem Agrupar, isso é um indicativo da
existência de soluções múltiplas.
Alane Alves () P.O 2010 122 / 162
Análise de Sensibilidade
Relatório de Limites
O Relatório de Limites do problema em estudo é apresentado na figura a
seguir.
Figure: Relatório de Limites.
Alane Alves () P.O 2010 123 / 162
Análise de Sensibilidade
Relatório de Limites
Primeira Parte
Apresenta a célula utilizada para representar a função objetivo e seu valor
na solução ótima.
Segunda Parte
O lado esquerdo apresenta as células utilizadas para representar as variáveis
de decisão e seus valores na solução ótima.
O lado direito diz respeito à variação possível dos valores das variáveis de
decisão e da função objetivo.
Os Limites Inferiores significam os menores valores que as variáveis de
decisão podem assumir ( mantidas todas as outras variáveis constantes)
mantendo a solução viável. A coluna seguinte indica o valor da função
objetivo, caso a variável em questão assuma seu menor valor e as outras
permaneçam constantes.
As outras colunas são de interpretação análoga assumindo apenas que a
variável de decisãoe a função objetivo irão assumir seus maiores valores.
Alane Alves () P.O 2010 124 / 162
Análise de Sensibilidade
Relatório de Sensibilidade
Alane Alves () P.O 2010 125 / 162
Análise de Sensibilidade
Relatório de Sensibilidade
Custos Reduzidos
Os custos reduzidos são os valores das variáveis de folga/excesso do
problema dual. Como estes valores estão associados aos coeficientes da
função objetivo do problema primal as colunas Permissível Acréscimo e
Permissível Decréscimo dos coeficientes formam um intervalo no qual os
coeficientes da função objetivo podem sofrer alterações sem que a solução
ótima seja alterada, assumindo que todos os demais coeficientes
permaneçam constantes.
Por exemplo: O coeficiente de x1 na função objetivo(c1) é 40 e os valores
permissíveis de acréscimo e decréscimo para este coeficiente são
respectivamente 10+30 e 20. Logo,
40− 20 ≤ c1 ≤ 40+ 10
+30
20 ≤ c1 ≤ 40+ 10
+30
Alane Alves () P.O 2010 126 / 162
Análise de Sensibilidade
Relatório de Sensibilidade
Preço Sombra
Os valores dos preços sobras são os valores da variáveis do dual. Seu
significado é:
A quantidade pela qual a função objetivo é alterada quando é dado
um incremento de uma unidade na constante da restrição, assumindo
que todos os outros coeficientes permanecem inalterados.
Interpretação aqui para os valores Permissíves de Acréscimos e Decréscimo
é análogo ao que foi feito para o caso dos custo reduzidos sendo que agora
o interesse é no intervalo de variação das constantes das restrições (ou
disponibilidade dos recursos).
Por exemplo, o coeficiente da segunda restrição é 16 e os valores dos
Acréscimos e Decrécimos Pemissíveis são, respectivamente, 4 e 16. Sendo
assim, o recurso dois(b2) poderá variar dentro do seguinte intervalo:
16− 16 ≤ b2 ≤ 16+ 4 ⇒ 0 ≤ b2 ≤ 20
O raciocínio é o mesmo para as demais restrições.
Alane Alves () P.O 2010 127 / 162
Modelo de Transporte
Modelo de Transporte
Alane Alves () P.O 2010 128 / 162
Modelo de Transporte Introdução
Introdução
O modelo de transporte visa minimizar o custo total do transporte
necessário para abastecer n centros consumidores(destinos) a partir de m
centros fornecedores(origens).
a1
b1
a2
b2
am bn
.
.
.
.
.
.
F
o
rn
eced
o
res
D
isp
o
n
ív
eis
P
o
ss
ív
ei
s
D
es
ti
n
o
s
Alane Alves () P.O 2010 129 / 162
Modelo de Transporte Introdução
Formulação do Problema
bj → as quantidades requeridas, ou demandadas, em cada destino.
ai → as quantidades disponíveis, ou ofertadas em cada origem.
cij → custo unitário de transporte entre a origem i e o destino j .
xij → a quantidade a ser transportada da origem i ao destinoj .
A fábrica i pode remeter no máximo ai itens, e o destino j necessita de
pelo menos bj itens.
Alane Alves () P.O 2010 130 / 162
Modelo de Transporte Introdução
Formulação do Problema
MinZ =
m∑
i=1
n∑
j=1
cijxij
sujeito a:
n∑
j=1
xij = ai (i = 1, 2, . . . ,m)
m∑
i=1
xij = bj (j = 1, 2, . . . , n)
xij ≥ 0
Note que nas restrições do modelo todos os coeficientes das variáveis são
iguais a um.
Alane Alves () P.O 2010 131 / 162
Modelo de Transporte Introdução
Formulação do Problema
Ao se somar as m restrições de ofertas obtém-se:
m∑
i=1
n∑
j=1
xij =
m∑
i=1
ai
Ao se somar as n restrições de demanda vem-se:
n∑
j=1
m∑
i=1
xij =
n∑
j=1
bj
Pode-se concluir, então, que a oferta é igual a demanda
m∑
i=1
ai =
n∑
j=1
bj
indicando que o modelo exige uma igualdade entre oferta total e demanda
total.
Alane Alves () P.O 2010 132 / 162
Modelo de Transporte Introdução
Formulação do Problema
Para aplicar o algoritmo do transporte é preciso apresentar as restrições do
modelo por meio do quadro a seguir:
cm1
. . .
c21
c11
. . .
. . .
. . .
. . .
. . .
. . .. . .
a1
a2
am
1
2
m
b1 b2 bn
. . .
1 2 n. . .
cm2
. . .
c22
c12
cmn
. . .
c2n
c1n
Demanda
Oferta
Destino
Origem
Alane Alves () P.O 2010 133 / 162
Modelo de Transporte Introdução
Formulação do Problema
Uma outra forma de apresentar o modelo é a seguinte:
MinZ =
m∑
i=1
n∑
j=1
cijxij
sujeito a: n∑
j=1
xij ≤ ai (i = 1, 2, . . . ,m)
m∑
i=1
xij ≤ bj (j = 1, 2, . . . , n)
xij ≥ 0
Neste modelo está-se considerando que a quantidade transportada da
origem i , para todos os possíveis destinos, é menor ou igual a quantidade
disponível (primeira restrição). Além disso, a segunda restrição diz que a
quantidade recebida pelo destino j , de todas as possíveis origens, é maior
ou igual a quantidade requerida.
Alane Alves () P.O 2010 134 / 162
Modelo de Transporte Introdução
Formulação do Problema
O algoritmo utilizado para resolver o modelo de transporte, exige que
a igualdade
∑m
i=1 ai =
∑n
j=1 bj seja respeitada. Isso pode ser
alcançado definindo-se um centro consumidor fictício, cuja demanda
seja exatamente a diferença entre o total da oferta e o total da
demanda, enquanto que os custos de transporte de cada origem ao
depósito fictício são tomados iguais a zero.
Na solução obtida, quantidades transportadas da origem i ao
consumidor fictício representam excedente de produção na origem i .
(Produção ≥ Demanda)
Outra situação hipotética é aquela em que a oferta é menor que a
demanda. Para alcançar o equilíbrio (demanda=Produção) defini-se
uma origem fictícia com custos de transporte a cada depósito iguais a
zero. Na solução obtida, a quantidade transportada da origem fictícia
ao consumidor j representará a demanda não satisfeita do
consumidor j .
Alane Alves () P.O 2010 135 / 162
Modelo de Transporte Introdução
Exemplo
Uma firma fabrica um determinado produto em quatro cidade A,B ,C e D;
o produto destina-se a três centros de consumo I , II e III . O custo
estimada de transportar o produto das fábricas para os centros
consumidores, assim como a demanda de cada centro consumidor e a
oferta de cada fábrica é dado na tabela abaixo.
Destino
Origem I II III Oferta
A 1 2 3 30
B 10 — 8 20
C 3 4 2 50
D 5 2 1 10
Demanda 20 40 50
Formule o modelo de transporte para se determinar o programa que torna
mínimo o custo total de transporte entre as quatro cidades e os três
centros consumidores.
Alane Alves () P.O 2010 136 / 162
Modelo de Transporte Introdução
Exemplo
MinZ = xAI + 2xAII + 3xAIII + 10xBI +MxBII + 8xBIII + 3xCI
+4xCII + 2xCIII + 5xDI + 2xDII + xDIII
sujeito a: xAI + xAII + xAIII = 30
xBI + xBII + xBIII = 20
xCI + xCII + xCIII = 50
xDI + xDII + xDIII = 10
xAI + xBI + xCI + xDI = 20
xAII + xBII + xCII + xDII = 40
xAIII + xBIII + xCIII + xDIII = 50
xij ≥ 0
Alane Alves () P.O 2010 137 / 162
Modelo de Transporte Introdução
Solução Inicial
Sabe-se que uma solução inicial deverá ser uma solução viável básica
do sistema formado pelas restrições do modelo.
Teorema
Qualquer equação do sistema formado pelas restrições do modelo pode ser
obtida por uma combinação linear das demais, indicando que só existem
(m + n − 1) equações independentes naquele sistema.
A conseqüência desse teorema é que a base será formada por (m + n − 1)
variáveis básicas.
Há uma série de critérios diversos para selecionar as variáveis básicas.
Alane Alves () P.O 2010 138 / 162
Modelo de Transporte Regra do Canto Noroeste
Regra do Canto Noroeste
A regra será aplicada ao quadro de soluções segundo os seguintes passos:
1 Comece pela célula superior esquerda
2 Coloque nessa célula a maior quantidade permitida pela oferta e
demanda correspondentes.
3 Atualize os valores da oferta e da demanda que foram modificados
pelo passo 2.
4 Siga para a célula da direita se houver alguma oferta restante e volte
ao passo2. Caso contrário, siga para célula inferior e volte ao passo 2.
Alane Alves () P.O 2010 139 / 162
Modelo de Transporte Regra do Canto Noroeste
Exemplo – Regra do Canto Noroeste
11
10
1 Oferta
9
10
8
1
2
3
7 6 10 4
1 2 3 4
12
8
7
4
6
9 12
8
5
Demanda
Destino
Origem
Na célula (1, 1) atribuem-se 7 unidades que é a quantidade máxima de
demanda do destino 1. Assim toda demanda do destino 1 foi atendida e
ainda restaram 2 unidades na origem 1. Deve-se então seguir para a célula
(1,2) e atribuí-la 2 unidades, que é o máximo valor que a origem 1 tem
disponível.
Alane Alves () P.O 2010 140 / 162
Modelo de Transporte Regra do Canto Noroeste
Exemplo – Regra do Canto Noroeste
11
10
1
7 2
4 6
4 4
Oferta
9 2
10 6
8 4
1
2
3
7 6 4 10 4 4
1 2 3 4
12
8
7
4
6
9 12
8
5
Demanda
Destino
Origem
O processo se repete até se alcançar a célula inferior direita do quadro de
soluções, quando contar-se-á com uma solução inicial.
Alane Alves () P.O 2010 141 / 162
Modelo de Transporte Regra do Canto Noroeste
Exemplo – Regra do Canto Noroeste
No exemplo a solução inicial foi
x11 = 7 x12 = 2 x22 = 4 x23 = 6 x33 = 4 x34 = 4
(Variáveis Básicas)
Z = 218
Note que na Regra do canto Noroeste a solução inicial é obtida sem levar
em consideração os custos dos transportes cij , isto é, depende
exclusivamente das ofertas das origens e das demandas dos destinos.
Alane Alves () P.O 2010 142 / 162
Modelo de Transporte Processo do Custo Mínimo
Processo do Custo Mínimo
Este processo para fornecer uma solução inicial leva em consideração além
das ofertas e das demandas os valores dos custos.
Os seguintes passos devem ser seguidos:
1 Localize no quadro o menor cij que não tenha oferta ou demanda nula.
2 Coloque na célula a maior quantidade permitida pela oferta e
demanda correspondente.
3 Atualize os valores da oferta e da demanda que foram modificadas
pelo passo 2 e volte ao passo 1.
O processo se repete até que sejam esgotadas as ofertas e suprimidas as
demandas de todos os destinos.
Alane Alves () P.O 2010 143 / 162
Modelo de Transporte Processo do Custo Mínimo
Exemplo – Processo do Custo Mínimo
11
10
1
4
9
1 6 1
6
Oferta
9
10 6
8 71
1
2
3
71 6 10 1 4
1 2 3 4
12
8
7
4
6
9 12
8
5
Demanda
Destino
Origem
O menor cij que aparece é 1 referente a célula (2,4). Logo nesta célula
vai-se atribuir a quantidade máxima de unidades permitida levando em
conta a restrição de oferta e demanda. Coloca-se, assim, 4 unidades nesta
célula que é a demanda do destino 4 e atualiza-se a oferta da origem 2
para 6 unidades uma vez que 4 foram consumidas.
Alane Alves () P.O 2010 144 / 162
Modelo de Transporte Processo do Custo Mínimo
Exemplo – Processo do Custo Mínimo
Eliminando-se o destino 4 do quadro o menor custo é igual a 2 e
corresponde a célula (2,1). A esta célula serão atribuídas 6 unidades
esgotando-se a oferta da origem 2 e diminuindo a demanda do destino 1
para 1 unidade.
Este processo se repete até que todas as ofertas sejam consumidas e todas
as demandas atendidas, quando então encontra-se uma solução inicial. No
exemplo a solução inicial foi de:
x13 = 9 x21 = 6 x24 = 4 x31 = 1 x32 = 6 x33 = 1
(Variáveis Básicas)
Z = 161
Alane Alves () P.O 2010 145 / 162
Modelo de Transporte Processo do Custo Mínimo
Solução Ótima
Conhecida uma solução viável básica inicial, deve-se obter a função
objetivo somente em função das variáveis não básicas, para saber se a
presente solução já é ótima.
Da mesma forma como é feito no método simplex, caso a solução ainda
não seja ótima deve-se determinar a variável que entra e a que sai da base.
Alane Alves () P.O 2010 146 / 162
Modelo de Transporte Processo do Custo Mínimo
Obter a função objetivo somente em função das variáveis
não-básicas: Método “u − v”
MinZ −
m∑
i=1
n∑
j=1
cijxij = 0
sujeito a:
n∑
j=1
x1j = a1 (u1)
. . . . . . . . .
n∑
j=1
xmj = am (um)
m∑
i=1
xi1 = b1 (v1)
. . . . . . . . .
m∑
i=1
xin = bn (vn)
xij ≥ 0
Alane Alves () P.O 2010 147 / 162
Modelo de Transporte Processo do Custo Mínimo
É necessário eliminar as variáveis básicas da função objetivo e, para isso,
deve-se somar a ela múltiplos das restrições do modelo. Sejam
u1, u2, . . . um os valores que irão multiplicar as equações de oferta, antes de
somá-la a função objetivo. Sejam v1, v2, . . . vn os múltiplos análogos para
cada restrição de demanda.
Alane Alves () P.O 2010 148 / 162
Modelo de Transporte Processo do Custo Mínimo
Conhecida uma solução viável básica, deve-se ter:
cij − ui − vj = 0 (10)
para cada uma das (m + n − 1) variáveis básicas, de modo a eliminá-las da
função objetivo que ficará expressa somente em função das variáveis
não-básicas.
Uma vez que o número de variáveis básicas é igual a (m + n − 1) vai-se ter
(m + n − 1) equações do tipo (10). Uma vez que o número de incógnitas
(ui e vj ) é m + n e tem-se m + n − 1 equações, pode-se atribuir um valor
arbitrário a uma dessas variáveis sem violar as equações.
Alane Alves () P.O 2010 149 / 162
Modelo de Transporte Processo do Custo Mínimo
Como exemplo, considere o quadro de soluções do método do custo
mínimo. As equações são:
Variáveis Básicas


x13 = 6− u1 − v3 = 0
x21 = 2− u2 − v1 = 0
x24 = 1− u2 − v4 = 0
x31 = 11− u3 − v1 = 0
x32 = 12− u3 − v2 = 0
x33 = 8− u3 − v3 = 0
Fazendo u1 = 0 tem-se:
v3 = 6 v1 = 9 v4 = 8
u3 = 2 u2 = −7 v2 = 10
Alane Alves () P.O 2010 150 / 162
Modelo de Transporte Processo do Custo Mínimo
Determinando os ui e vj pode-se escrever a função objetivo em função das
variáveis não básicas.
Coeficientes da Função Objetivo
xij : cij − ui − vj

x11 : 10− 9 = 1
x12 : 7− 10 = −3
x14 : 5− 8 = −3
x22 : 8+ 7− 10 = 5
x23 : 9+ 7− 6 = 10
x34 : 4− 2− 8 = −6
A função objetivo será, então:
Z = 161+ x11 − 3x12 − 3x14 + 5x22 + 10x23 − 6x34
Alane Alves () P.O 2010 151 / 162
Modelo de Transporte Processo do Custo Mínimo
Teste de Otimalidade
Uma solução viável básica é ótima se e somente se cij − ui − vj ≥ 0 para
todo i , j tal que xij seja não básica.
Sendo assim, como as variáveis x12, x14 e x34 apresentaram coeficientes
negativos a solução ainda não é ótima.
Iteração
Como acontece com o método simplex tradicional tem-se que determinar a
variável que entra na base (passo 1) e uma variável que sai da base (passo
2) e depois identificar a nova solução viável (passo 3).
Alane Alves () P.O 2010 152 / 162
Modelo de Transporte Processo do Custo Mínimo
Teste de Otimalidade
Passo 1 – Encontrar a variável que entra na base
Obtida a função objetivo somente em função das variáveis não-básicas a
variável que entra na base deve ter um valor de cij − ui − vj negativo para
diminuir o custo total. Portanto, no exemplo as candidatas a entrar na
base são x12, x14 e x34.
Para escolher entre as candidatas, selecione aquela com menor valor de
cij − ui − vj negativo como variável que entra na base, nesse caso x34 pois
apresenta coeficiente −6.
Alane Alves () P.O 2010 153 / 162
Modelo de Transporte Processo do Custo Mínimo
Teste de Otimalidade
Passo 2 – Encontrar a variável que sai da base
Aumentando-se o valor da variável que entra na base dispara uma reação
em cadeia para compensar mudanças nas demais variáveis básicas de modo
a continuar satisfazendo as restrições de oferta e demanda. A primeira
variável básica que chegar a zero se torna a variável que deixa a base.
Imagine que a variável x34 entrará na base com valor θ ≥ 0, que deve ser o
maior possível.
Estabelecer um valor θ para variável x34, requer diminuir x24 na mesmaquantidade para restabelecer a demanda igual a 4 na coluna 4. Essa
mudança requer então aumentar x21 na mesma quantidade para continuar
obedecendo a oferta da linha 2. Mais uma vez, tal mudança requer
diminuir a variável x31 na mesma quantidade para restabelecer a demanda
7 da coluna 1. Esse decrescimento também restabelece a oferta da origem
3 igual 8 na linha 3.
Alane Alves () P.O 2010 154 / 162
Modelo de Transporte Processo do Custo Mínimo
11
10
1
9
4− θ
6 1 θ
6+θ
1−θ
Oferta
9
10
8
1
2
3
7 6 10 4
1 2 3 4
12
8
7
4
6
9 12
8
5
Demanda
Destino
Origem
Alane Alves () P.O 2010 155 / 162
Modelo de Transporte Processo do Custo Mínimo
Teste de Otimalidade
Passo 2 – Encontrar a variável que sai da base
Deve-se agora, determinar o maior valor permitido a θ, isto é, o valor de θ
que gera a variável básica que se anula mais rapidamente.
Do quadro anterior tem-se:

x21 = 6+ θ
x24 = 4− θ ≥ 0 ∴ θ ≤ 4
x31 = 1− θ ≥ 0 ∴ θ ≤ 1
Então θ = 1 e x31 é a variável que sai da base por ser a primeira a se anular.
Alane Alves () P.O 2010 156 / 162
Modelo de Transporte Processo do Custo Mínimo
Passo 3 – Encontrar a nova solução viável básica
A nova solução viável básica é identificada adicionando-se o valor de θ no último
quadro.
O valor da variável que sai é x31 = 1 o quadro ficará:
11
10
1
3
9
0 6 1 1
7
Oferta
9
10
8
1
2
3
7 6 10 4
1 2 3 4
12
8
7
4
6
9 12
8
5
Demanda
Destino
Origem
Como cada variável tem um custo na função objetivo, o efeito da entrada de x34
pode ser assim calculado:
∆Z = c34 − c24 + c21 − c31 = 4− 1+ 2− 11 = −6
Alane Alves () P.O 2010 157 / 162
Modelo de Transporte Processo do Custo Mínimo
Continuando com o algoritmo resta saber se a solução é ótima, para isso
calcula-se ui e vj e reinicia-se o processo.
Variáveis Básicas 

x13 = 6− u1 − v3 = 0
x21 = 2− u2 − v1 = 0
x24 = 1− u2 − v4 = 0
x32 = 12− u3 − v2 = 0
x33 = 8− u3 − v3 = 0
x34 = 4− u3 − v4 = 0
Fazendo u3 = 0 tem-se:
u1 = −2 u2 = −3 v4 = 4
v1 = 5 v3 = 8 v2 = 12
Alane Alves () P.O 2010 158 / 162
Modelo de Transporte Processo do Custo Mínimo
Calculando-se ui e vj deve-se calcular os coeficientes das variáveis não
básicas (cij − ui − vj) 

x11 : 10+ 2− 5 = 7
x12 : 7+ 2− 12 = −3
x14 : 5+ 2− 4 = 3
x22 : 8+ 3− 12 = −1
x23 : 9+ 3− 8 = 4
x31 : 11− 0+ 5 = 6
Como há coeficientes negativos a solução não é ótima e a variável que deve
entrar na base é x12 por apresentar o menor coeficiente negativo (−3).
Alane Alves () P.O 2010 159 / 162
Modelo de Transporte Processo do Custo Mínimo
11
10
1
3
9−θ+θ
6− θ 1 + θ 1
7
Oferta
9
10
8
1
2
3
7 6 10 4
1 2 3 4
12
8
7
4
6
9 12
8
5
Demanda
Destino
Origem


x13 = 9− θ ≥ 0 ∴ 9
x32 = 6− θ ≥ 0 ∴ 6
x33 = 1+ θ ≥ 0
Sendo assim, o valor máximo que θ pode assumir é 6 e a variável que deve
deixar a base é x32.
Alane Alves () P.O 2010 160 / 162
Modelo de Transporte Processo do Custo Mínimo
Para determinar a variação na função objetivo
∆Z = 6(c12 − c13 + c33 − c32) = 6(7− 6+ 8− 12) = −18
11
10
1
3
36
0 7 1
7
Oferta
9
10
8
1
2
3
7 6 10 4
1 2 3 4
12
8
7
4
6
9 12
8
5
Demanda
Destino
Origem
Alane Alves () P.O 2010 161 / 162
Modelo de Transporte Processo do Custo Mínimo
Variáveis Básicas

x12 = 7− u1 − v2 = 0
x13 = 6− u1 − v3 = 0
x21 = 2− u2 − v1 = 0
x24 = 1− u2 − v4 = 0
x33 = 8− u3 − v3 = 0
x34 = 4− u3 − v4 = 0
Fazendo u1 = 0 tem-se:
v2 = 7 u3 = 2 u2 = −1
v1 = 1
v3 = 6 v4 = 2
Variáveis Não-Básicas

x11 = 10− 0− 1 = 9
x14 = 5− 0− 2 = 3
x22 = 8+ 1− 7 = 2
x23 = 9+ 1− 6 = 4
x31 = 11− 2− 1 = 8
x32 = 12− 2− 7 = 3
Como não há coeficiente negativos a solução é ótima.
x12 = 6 x13 = 3 x21 = 7 x24 = 3 x33 = 7 x34 = 1
Z ∗ = 137
Alane Alves () P.O 2010 162 / 162
	Pesquisa Operacional
	Introdução
	Programação Linear
	Introdução
	Solução Gráfica
	Hipótese
	Teoremas
	Método Simplex
	Introdução
	Adaptando a Outras Formas do Modelo
	Casos Especiais
	Solução Inicial Artificial
	Método do M-Grande
	Método das Duas Fases
	Programação Linear Método Simplex usando Excel
	Dualidade
	Introdução
	Propriedades
	Teoremas
	Análise de Sensibilidade
	Modelo de Transporte
	Introdução
	Regra do Canto Noroeste
	Processo do Custo Mínimo