View
0
Download
0
Category
Preview:
Citation preview
Universidade Federal de UberlândiaFaculdade de Computação
GSI027 � Otimização
Prof. Renato Pimentel
2o Semestre � 2019
GSI027 Otimização 2o Semestre � 2019 1 / 355
Objetivo
Ao término da disciplina, o aluno deve estar apto a corretamenteaplicar os métodos, técnicas e ferramentas da pesquisa operacional namodelagem e solução de problemas relacionados a sistemas deinformação.
GSI027 Otimização 2o Semestre � 2019 2 / 355
Ementa do curso
Fundamentos da Pesquisa Operacional
Modelagem
Programação linear, método simplex, dualidade.
Otimização em Redes, problemas de transporte.
GSI027 Otimização 2o Semestre � 2019 3 / 355
Bibliogra�a básica
TAHA, Hamdy. Pesquisa operacional. 8a. ed. São Paulo: PrenticeHall, 2008.
LACHTERMACHER, Gerson. Pesquisa operacional na tomada dedecisões. 4a. ed. São Paulo: Prentice Hall. 2009.
ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H.Pesquisa operacional: para cursos de engenharia. Rio de Janeiro:Elsevier Brasil, 2006.
GSI027 Otimização 2o Semestre � 2019 4 / 355
Recomendação: MARINS, Fernando Augusto Silva. Introdução àpesquisa operacional. São Paulo: Cultura Acadêmica, 2011.
Disponível gratuitamente (mediante cadastro) em:http://www.culturaacademica.com.br/catalogo/
introducao-a-pesquisa-operacional
GSI027 Otimização 2o Semestre � 2019 5 / 355
Conteúdo previsto1
1 Introdução à PesquisaOperacional: Origem /principais aplicações.
2 Programação Linear (PL):
I Características gerais emodelagem de umproblema de PL;
I Problemas típicos;
I Resolução grá�ca;
I Método simplex.
3 Dualidade:
I O modelo dual de um PL;
I Analogia entre as soluçõesprimal e dual.
4 Problema de transporte:
I Algoritmos para oproblema de transporte;
I O problema de designação.
5 Otimização em redes
I Problema de caminhomínimo;
I Problema de �uxo máximo.
1Nova ementa (Reform. Proj. Pedagógico BSI)GSI027 Otimização 2o Semestre � 2019 6 / 355
Avaliação
3 provas teóricas: 35, 35 e 30 pontos.I 10/09 (P1)I 22/10 (P2)I 26/11 (P3)
Nota �nal (aproveitamento):
NF = P1 + P2 + P3
GSI027 Otimização 2o Semestre � 2019 7 / 355
Avaliação substitutiva
Alunos que obtiverem ao �nal das três provas 50 ≤ NF < 60(somente) terão direito a uma prova substitutiva (SUB)
Data: 10/12
O conteúdo da prova será o visto ao longo de todo o semestre
A prova substitutiva vale 100 pontos, eliminando a soma das 3anteriores, caso maior, até o limite de 60
A NF neste caso será dada por
NF =
{60, se SUB ≥ 60
max (P1 + P2 + P3, SUB), caso contrário,
ou seja, o aluno que �cou de SUB terá nota máxima 60, caso atinjana mesma a pontuação necessária para ser aprovado.
GSI027 Otimização 2o Semestre � 2019 8 / 355
Frequência
O aluno que tiver frequência inferior a 75% é reprovado por faltas.
A chamada será feita em sala, pelo professor, sempre que decorridosem torno de 15 minutos do início da mesma. O aluno que chegar apósa chamada, ou não respondê-la, �cará com falta.
Falta em dia de prova: o aluno somente terá direito a fazer provaem nova data caso apresente justi�cativa no setor de graduação e/oucoordenação do curso, que encaminhará comunicação por escrito aoprofessor quando julgá-la plausível.
É responsabilidade do aluno controlar sua frequência, de modo a evitarreprovação por falta.
GSI027 Otimização 2o Semestre � 2019 9 / 355
Aulas
Segundas-feiras: 19:00 até 20:40 � Sala 1B104
Terças-feiras: 20:50 até 22:30 � Sala 1B104
Atividades extra-classeListas de exercícios (�xação)
GSI027 Otimização 2o Semestre � 2019 10 / 355
Atendimento e outras informações
Professor: Renato PimentelI Página: http://www.facom.ufu.br/∼rpimentelI E-mail: rpimentel @ ufu . brI Sala 1B139
Atendimento (agendar previamente através de e-mail):I Terças-feiras, 18:00 até 19:50, sala 1B139I Quartas-feiras, 16:00 até 17:40, sala 1B139I Sextas-feiras, 18:10 até 19:00, sala 1B139
Material da disciplina:I http://www.facom.ufu.br/∼rpimentel > Ensino > 2019/2 > GSI027 �
Otimização
GSI027 Otimização 2o Semestre � 2019 11 / 355
Sumário
1 Pesquisa Operacional e Tomada de Decisões
GSI027 Otimização 2o Semestre � 2019 12 / 355
Tomada de Decisões
Tarefa básica da gestão
Alternativas viáveis
GSI027 Otimização 2o Semestre � 2019 13 / 355
Tomada de Decisões
1 Identi�car o problema2 Formular objetivos3 Analisar limitações4 Avaliar alternativas
GSI027 Otimização 2o Semestre � 2019 14 / 355
O que é a Pesquisa Operacional
Segundo Marins (2011)
�É o uso do método cientí�co com o objetivo de prover departamentosexecutivos de elementos quantitativos para a tomada de decisões comrelação a operações sob seu controle�
GSI027 Otimização 2o Semestre � 2019 15 / 355
Origens
Termo Pesquisa Operacional: tradução direta de Operationalresearch.
Inglaterra (1934): invenção do radar.
1936: Estação de Pesquisa Manor Bawdsey (Su�olk) � comointerceptar aviões inimigos?A. P. Rowe (1938), superintendente da estação: criação do termo.
I E�ciência de técnicas de operações a partir de experimentos cominterceptação.
I Análise cientí�ca do uso operacional de recursos militares: II GuerraMundial.
GSI027 Otimização 2o Semestre � 2019 16 / 355
Pós-Guerra: rápida ascensão Inglaterra e EUAEUA (1947): SCOOP (Scienti�c Computation of Optimal Programs)� Pentágono
I Marshall Wood (economista) e George Dantzig (matemático � métodosimplex).
I Programação linear
1952: ORSA (Sociedade Americana de Pesquisa Operacional)
1953: ORS (Sociedade de Pesquisa Operacional) � Inglaterra
Focos distintosPesquisa inglesa: estudos de caso, problemas especí�cos
Pesquisa americana: modelos e métodos matemáticos
GSI027 Otimização 2o Semestre � 2019 17 / 355
Alguns temas pesquisados pelos americanos:
Teoria de estoques
Teoria de �las
Reposição de equipamentos
Agendamento de tarefas em máquinas
Teoria de jogos
Fluxos de redes
Otimização linear
GSI027 Otimização 2o Semestre � 2019 18 / 355
No Brasil
1o. Simpósio: ITA � S. José dos Campos (1968)
Criação do curso de Engenharia de Produção (ITA)
SOBRAPO: Sociedade Brasileira de Pesquisa Operacional2
2www.sobrapo.org.brGSI027 Otimização 2o Semestre � 2019 19 / 355
Fases da PO
GSI027 Otimização 2o Semestre � 2019 20 / 355
Formulação do problema
Problemas reais: forma vaga e imprecisaAlgumas questões:
I Quem tomará decisões?I Quais os objetivos?I Que aspectos estão sujeitos ao controle dos decisores (variáveis de
decisão) e sob quais limitações (restrições)?I Quais aspectos fogem do controle dos decisores?
GSI027 Otimização 2o Semestre � 2019 21 / 355
Construção do modelo
Modelos: representações simpli�cadas da realidadeModelagem: 2 características importantes:
I Permite analisar o problema, indicando relações entre variáveis, quaisdados relevantes e variáveis de maior importância
I Permite estudo de alternativas de ação sem interromper sistema emestudo.
Podem ser físicos (ex.: maquetes), analógicos (ex.: organograma) ematemáticos.
GSI027 Otimização 2o Semestre � 2019 22 / 355
Mundo real
Mundo realconsiderado
Modelo
GSI027 Otimização 2o Semestre � 2019 23 / 355
Obtenção da solução
Típico de PO: modelo matemático.
Varia conforme a área (programação linear, programação em redes,teoria de �las, etc.)
Técnicas novas surgem constantementeSoftwares:
I Solver do ExcelI LINDO � Linear Discrete Optimizer (www.lindo.com)I ILOG
(www.ibm.com/products/ilog-cplex-optimization-studio)I Simulações: PROMODEL (www.belge.com.br/promodel.php) e
ARENA (www.paragon.com.br)I etc.
GSI027 Otimização 2o Semestre � 2019 24 / 355
Teste do modelo e da solução obtida
O modelo precisa ser testado.I Teste permite identi�car problemas na criação do modelo (ex.: aspecto
importante omitido, re�namento de aspecto incluído etc.)I Em alguns casos, teste pode ser comparado com dados anteriores.
GSI027 Otimização 2o Semestre � 2019 25 / 355
Implementação
Implantação da solução �nal ao sistema.
Intervenções podem ser necessárias no caso de alguma falha nãoprevista.
GSI027 Otimização 2o Semestre � 2019 26 / 355
Exemplo de problema: cerca (Taha)
Exemplo
Um fazendeiro comprou L metros de uma tela e pretende cercar umapequena área da fazenda para criação de gado. O fazendeiro somente sabefazer ângulos retos. O fazendeiro quer que a área cercada seja a maior
possível.
GSI027 Otimização 2o Semestre � 2019 27 / 355
Área deve ser retangular (ângulos retos)
Se l e c são respectivamente a largura e o comprimento doretângulo, queremos maximizar
z = l × c ,
sujeita às restrições:I 2(l + c) = L,I l ≥ 0, c ≥ 0.
In�nitas soluçõesviáveis: atendem a todas restrições
ótima: melhor solução viável
GSI027 Otimização 2o Semestre � 2019 28 / 355
Formato geral
Maximizar ou minimizar umafunção objetivo sujeita arestrições
GSI027 Otimização 2o Semestre � 2019 29 / 355
Problema linear
Exemplomaximizar z = 2x1 + 3x2 + 4x3
3x1 + 2x2 + 1x3 ≤ 10
2x1 + 3x2 + 3x3 ≤ 15
1x1 + 1x2 − 1x3 ≥ 4
x1, x2, x3 ≥ 0
GSI027 Otimização 2o Semestre � 2019 30 / 355
Obtenção da Solução
z = 15.55
x1 =13, x2 =
59, x3 =
389
GSI027 Otimização 2o Semestre � 2019 31 / 355
Problema de transporte
Exemplo
O modelo de transporte visa minimizar o custo total do transporte
necessário para abastecer n centros consumidores (destinos) a partir de mcentros fornecedores (origens)
GSI027 Otimização 2o Semestre � 2019 32 / 355
GSI027 Otimização 2o Semestre � 2019 33 / 355
Grandes Áreas
Programação Linear
Mix de produção
Mistura de matérias-primas
Modelos de equilíbrio econômico
Carteiras de investimentos
Roteamento de veículos
Jogos entre empresas
GSI027 Otimização 2o Semestre � 2019 34 / 355
Modelos em RedesRotas econômicas de transporte
Distribuição e transporte de bens
Alocação de pessoal
Monitoramento de projetos
GSI027 Otimização 2o Semestre � 2019 35 / 355
Teoria das FilasCongestionamento de tráfego
Operações de hospitais
Dimensionamento de equipes de serviço
GSI027 Otimização 2o Semestre � 2019 36 / 355
Alguns Links Interessantes
O que é a PO?
Vídeo da OR Society:https://youtu.be/tX6Rw7KJGjE
Empresas de PO
Reportagem da Revista Época de 19/01/2017:https://goo.gl/dYch4k
GSI027 Otimização 2o Semestre � 2019 37 / 355
Referências
1 ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H.Pesquisa operacional: para cursos de engenharia. Rio de Janeiro:Elsevier Brasil, 2006.
2 MARINS, F. A. S. Introdução à pesquisa operacional. São Paulo:Cultura Acadêmica, 2011.
3 TAHA, H. Pesquisa operacional. 8a. ed. São Paulo: Prentice Hall,2008.
Os materiais de parte desta seção foram gentilmente cedidos por Paulo H.R. Gabriel e Ivan Sendin (FACOM/UFU)Adaptações: Renato Pimentel, FACOM/UFU
GSI027 Otimização 2o Semestre � 2019 38 / 355
Sumário
2 Introdução à programação linear
GSI027 Otimização 2o Semestre � 2019 39 / 355
Introdução
Nesta seção, Será considerada uma subclasse particular de problemas dePO, a dos problemas de programação linear.A característica que de�ne tal subclasse está no modelo matemático.
GSI027 Otimização 2o Semestre � 2019 40 / 355
Equação linear
Equação da forma
c1 x1 + c2 x2 + · · ·+ cn xn = c0
Elementos:I c0, c1, . . . , cn: coe�cientes (conhecidos)I x1, x2, . . . , xn: variáveis (desconhecidos)
Um conjunto de equações lineares relacionadas a um mesmo grupo devariáveis recebe o nome de sistema linear.
GSI027 Otimização 2o Semestre � 2019 41 / 355
O modelo matemático
Modelo de PL � como qualquer modelo de PO � possui 3 componentesbásicos:
1 Variáveis de decisão, que se deseja determinar;2 Uma ou um conjunto de restrições que a solução deve satisfazer;3 Um objetivo (meta) a ser otimizado (maximizado ou minimizado).
GSI027 Otimização 2o Semestre � 2019 42 / 355
Variáveis de DecisãoAs variáveis de decisão são as incógnitas a serem determinadas pelasolução do modelo e os parâmetros (coe�cientes) são valores �xos noproblema
RestriçõesDe modo a levarmos em conta as limitações físicas do sistema, o modelodeve incluir restrições que limitam as variáveis de decisão a seus valorespossíveis (ou viáveis)
Função Objetivo
É uma função matemática que de�ne a qualidade da solução em funçãodas variáveis de decisão; é um critério de escolha das variáveis de decisãorepresentado por uma função
GSI027 Otimização 2o Semestre � 2019 43 / 355
Estrutura de Modelos Matemáticos
Pode-se dizer que:
O problema do modelo matemático de Pesquisa Operacional é escolher osvalores das variáveis de decisão de forma a obter o melhor resultado dafunção objetivo sujeita às restrições especi�cadas.
GSI027 Otimização 2o Semestre � 2019 44 / 355
Recomendações
O decisor tem autoridade para escolher a quantidade (valor numérico)do item? Se sim, esta é uma variável de decisão;
Ser preciso com relação às unidades de cada variável de decisão (ex.:se alguma moeda, alguma medida de comprimento, volume, massa outempo, etc.);
Não confundir variáveis de decisão com os parâmetros do problema,como ex.: número de máquinas na fábrica, quantidade de cada recursousado na fabricação de um produto, custos de produção, custos detransporte, etc.
GSI027 Otimização 2o Semestre � 2019 45 / 355
Exemplo
Um investidor possui $90.000, 00 para investir em ações. Ele estáinteressado em duas empresas:
Tele Mundo, cujas ações custam $50, 00 cada e o retorno esperado éde $6, 00 ao ano;
Cosmo Fonte, cujas ações custam $30, 00 cada e o retorno esperado éde $4, 00 ao ano.
Além disso, ele não quer investir mais que $60.000, 00 em uma únicaempresa. Como ele deve planejar seu investimento, de modo a maximizarseu lucro anual?
GSI027 Otimização 2o Semestre � 2019 46 / 355
Variáveis de decisão: Correspondem às quantidades de ações emcada empresa (por exemplo: TM e CF , ou x1 e x2);
Parâmetros: São os preços e retorno de cada ação;
Restrições: São as limitações impostas pelo investidor e pelaquantidade de dinheiro disponível para investir; além disso, por umaquestão de lógica, ele não pode investir um valor negativo em cadaação;
Função Objetivo: é a Função matemática que determina o retornoem função das variáveis de decisão e que (neste caso) deve sermaximizada.
GSI027 Otimização 2o Semestre � 2019 47 / 355
Função objetivo
max L = 6TM + 4CF
Restrições
50TM + 30CF ≤ 90.000
50TM ≤ 60.000
30CF ≤ 60.000
Condições de não-negatividade
TM ≥ 0
CF ≥ 0
GSI027 Otimização 2o Semestre � 2019 48 / 355
Algumas observações
Um tema comum na PO é a busca de uma solução ótima;
É necessário que �que claro que essas soluções são ótimas apenas emrelação ao modelo que está sendo usado;
Como o modelo é apenas uma representação da realidade, não hágarantia de que a solução ótima para o modelo se comprovará como amelhor possível que poderia ter sido implementada para o problemareal;
Entretanto, se o modelo for bem formulado e experimentado, assoluções tendem a ser uma boa representação para a solução a seradotada no caso real.
GSI027 Otimização 2o Semestre � 2019 49 / 355
Outro Exemplo
Exemplo
Uma empresa precisa decidir quais modelos de geladeira produzir em suanova planta. Existem dois modelos disponíveis: luxo e básico. No máximo,1500 unidades do modelo luxo e 6000 unidades do modelo básico podemser vendidas por mês. Empresa contratou 25000 homens-hora de trabalhopor mês. Os modelos luxos precisam de 10 homens-hora de trabalho paraserem produzidos e os modelos básicos, 8 homens-hora. A capacidade dalinha de montagem é de 4500 geladeiras por mês, pois as geladeirasdividem a mesma linha. O lucro unitário do modelo luxo é $100, 00 pormês, enquanto o modelo básico lucra $50, 00 durante o mesmo período.Determine quanto produzir de cada geladeira, de modo a satisfazer todasas restrições e maximizar o lucro da empresa.
GSI027 Otimização 2o Semestre � 2019 50 / 355
Variáveis de DecisãoSejam x1 e x2 as quantidades (unidades) produzidas dos modelos luxo ebásico, respectivamente.
Função Objetivo
Admitindo que a função lucro é uma função linear de x1 e x2, esse lucrodeve ser maximizado por uma escolha de x1 e x2, tal que:
max L = 100x1 + 50x2
Como existem recursos limitados, há restrições:
Restrições1 10x1 + 8x2 ≤ 25000 (homens-hora)2 x1 + x2 ≤ 4500 (linha de montagem)3 x1 ≤ 1500 (máximo a ser vendido do luxo)4 x2 ≤ 6000 (máximo a ser vendido do básico)5 x1 ≥ 0; x2 ≥ 0 (não-negatividade)
GSI027 Otimização 2o Semestre � 2019 51 / 355
Problemas de Programação Linear
De�nição Formal
Um problema de Programação Linear (PL) é um problema de programaçãomatemática em que as Funções Objetivos e de Restrição são lineares.
Forma Geral:
max(min) Z =n∑
j=1
cjxj
sujeito a:n∑
j=1
aijxj , para i = 1, 2, . . . ,m
xi ≥ 0, ∀i
GSI027 Otimização 2o Semestre � 2019 52 / 355
Algumas De�nições
SoluçãoQualquer especi�caçã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ávelUma solução em que todas as restrições são satisfeitas. O conjunto detodos os pontos que satisfazem todas as restrições é chamado deConjunto Viável (S).
Solução ÓtimaUma 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.Pode ser única ou não.
GSI027 Otimização 2o Semestre � 2019 53 / 355
Hipóteses da Programação Linear I
Proporcionalidade
A contribuição de cada variável ao valor da função objetivo é diretamenteproporcional ao valor da variável, conforme representado pelo termo cjxjna 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 narestrição.
AditividadeToda função em um modelo de programação linear é a soma dascontribuições individuais das respectivas variáveis.
GSI027 Otimização 2o Semestre � 2019 54 / 355
Hipóteses da Programação Linear II
DivisibilidadeAs variáveis de decisão em um modelo de programação linear podemassumir quaisquer valores, inclusive valores não-inteiros, que satisfaçam asrestrições funcionais e de não-negatividade.Quando as variáveis do modelo de programação linear só puderem assumirvalores inteiros, deve-se impor esta condição ao próprio modelo. Passa-se,então, a lidar com um modelo de programação linear inteira.
CertezaO valor atribuído a cada parâmetro de um modelo de programação linear éassumido como uma constante conhecida.
GSI027 Otimização 2o Semestre � 2019 55 / 355
Problemas de mistura
Problemas de mistura consistem em combinar materiais obtidos danatureza (ou sobras de outros já previamente combinados) para gerarnovos materiais ou produtos com características convenientes.
GSI027 Otimização 2o Semestre � 2019 56 / 355
Exemplos de problema de mistura I
1 Rações: Fábricas de rações produzem variados tipos de rações paradeterminados animais (bovinos, equinos, caprinos, caninos depequenos e grande portes etc.)
I Mistura de alimentos ou farinhas de restos de alimentos (milho, farelode arroz, etc.)
I Preços de mercados destes produtos são conhecidosI Composição nutricional é conhecida. Nutrição veterinária especi�ca
necessidades mínimas e máximas dos nutrientes por kg para cadaespécie de animal.
I Problema de minimizar custo: quais devem ser as quantidades ideais
de cada ingrediente por kg de modo que necessidades nutricionais
sejam atendidas e o custo total dos ingredientes seja o menor possível?
GSI027 Otimização 2o Semestre � 2019 57 / 355
Exemplos de problema de mistura II
2 Ligas metálicas: Fundições produzem diversos tipos de aço a partirde diversos insumos: lingotes de ferro, gra�te, sucatas industriais, etc.
I Forno de alta temperatura para permitir a misturaI A composição, em termos de elementos como carbono, silício,
manganês etc. é determinada por normas técnicas da metalurgia,bem como composição dos produtos a serem misturados.
I Preços dos insumos podem variar substancialmente. Entretanto, sãoconhecidos.
I deve-se determinar as quantidades de cada insumo a serem fundidas,
de modo que a composição atenda as normas e preço �nal seja menor
possível
GSI027 Otimização 2o Semestre � 2019 58 / 355
Exemplos de problema de mistura III
3 Areias para �ltro (ETA)I Permeabilidade: areias usadas em estações de tratamento de água
para interceptar impurezas da água a�uenteI Unidades de �ltração: areias de portos passíveis de exploração com
composições distintasI Custos de dragagem, transporte, seleção e preparo variam p/ cada
portoI Areias dispostas em camadas, devendo obedecer composições
estabelecidas em normaI Como combinar os volumes de areia de cada porto, de modo a atender
às especi�cações, com menor custo possível?
GSI027 Otimização 2o Semestre � 2019 59 / 355
Formulação matemática do problema da mistura
Obtenção de produto (mistura), combinando-se materiais disponíveis
Materiais (ingredientes) possuem os componentes desejados namistura
Produtos devem satisfazer determinadas especi�cações
Objetivo: determinar as quantidades dos ingredientes para criarmistura com composição especi�cada com menor custo possível(minimização).
GSI027 Otimização 2o Semestre � 2019 60 / 355
Minimizarf (x1, . . . , xn) = c1x1 + c2x2 + · · ·+ cnxn
Sujeito às restrições:
a11x1+ a12x2+· · ·+ a1nxn = b1
a21x1+ a22x2+· · ·+ a2nxn = b2
. . .
am1x1+am2x2+· · ·+amnxn = bm
x1+ x2+ . . . +xn = 1
x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0
xj : quantidade do ingrediente j por unidade da mistura;
aij : fração do componente i no ingrediente j ;
bi : fração do componente i na mistura;
cj : custo unitário do ingrediente j .
GSI027 Otimização 2o Semestre � 2019 61 / 355
Exemplo: ração
Exemplo
Queremos saber quais as quantidades ideais de cada ingrediente para fazeruma quantidade de ração para aves, com as necessidades nutricionaisatendidas e o custo total dos ingredientes seja o menor possível. Temosdisponíveis dois ingredientes (milho e farinha de osso), cujos custos (em $por Kg) e ingredientes (em unidades por Kg) estão listados na tabela aseguir:
Vitamina A Vitamina B Proteínas Custo
Milho 2 3 1 65
Farinha de osso 3 2 30
Deseja-se que a ração contenha, no mínimo, 7 unidades de vitamina A, 9de vitamina B e 1 de proteína.
GSI027 Otimização 2o Semestre � 2019 62 / 355
Modelo Matemático
min C = 65x1 + 30x2
sujeito a:2x1 + 3x2 ≥ 7
3x1 + 2x2 ≥ 9
1x1 + 0x2 ≥ 1
x1 ≥ 0; x2 ≥ 0
GSI027 Otimização 2o Semestre � 2019 63 / 355
Mix de produção
Problemas de mix de produção envolvem decidir quais produtos, equanto fabricar de cada produto em um certo período.
GSI027 Otimização 2o Semestre � 2019 64 / 355
Formulação matemática do mix de produção
Tendo em vista a capacidade limitada de produção � máquinas, RH,capital, armazenagem, etc. � e os diversos produtos que a empresapode fabricar e vender, deseja-se determinar quais fabricar e quantofabricar de cada produto, de modo a maximizar o lucro, numdeterminado período.
GSI027 Otimização 2o Semestre � 2019 65 / 355
Maximizarf (x1, . . . , xn) = `1x1 + `2x2 + · · ·+ `nxn
Sujeito às restrições:
a11x1+ a12x2+· · ·+ a1nxn ≤ C1
a21x1+ a22x2+· · ·+ a2nxn ≤ C2
. . .
am1x1+am2x2+· · ·+amnxn ≤ Cm
dj ≤ xj ≤ vj , j = 1, 2, . . . , n
xj : quantidade do produto j a ser produzida por período;
Ci : capacidade do recurso i , i = 1, 2, . . . , m no período.
aij : unidades do recurso i usadas para produzir uma unidade de j ;
dj (vj): produção mínima (máxima) do produto j no período;
`j : lucro obtido pela empresa por cada unidade de j .
GSI027 Otimização 2o Semestre � 2019 66 / 355
O Exemplo 3.2 visto anteriormente (problema das geladeiras) é umexemplo de problema de mix de produção.
GSI027 Otimização 2o Semestre � 2019 67 / 355
Outro exemplo (MARINS, 2011)
Exemplo
Uma empresa deseja programar a produção de um utensílio de cozinha erequer o uso de 2 recursos: mão-de-obra e material. Ela está considerandoa fabricação de 3 modelos de acordo com os dados da tabela que segue,sendo que a disponibilidade diária de mão-de-obra é 150 horas, e osuprimento de material é 200 kg/dia.
Modelo
A B C
Mão-de-obra (horas/unidade) 7 3 6
Material (kg/unidade) 4 4 5
Lucro ($/unidade) 4 2 3
GSI027 Otimização 2o Semestre � 2019 68 / 355
Modelagem
xa, xb, xc : produções diárias de A, B e C.Restrições:
I 7xa + 3xb + 6xc ≤ 150 (limitação de mão-de-obra)I 4xa + 4xb + 5xc ≤ 200 (limitação de material)I xa ≥ 0, xb ≥ 0, xc ≥ 0 (não-negatividade)
Função objetivo: maximização do lucro totalL = 4xa + 2xb + 3xc
GSI027 Otimização 2o Semestre � 2019 69 / 355
Exercícios I
1 Um sapateiro faz 6 sapatos por hora, se �zer somente sapatos, e 5cintos por hora, se �zer somente cintos. Ele gasta 2 unidades de couropara fabricar 1 unidade de sapato e 1 unidade de couro para fabricaruma unidade de cinto. Sabendo-se que o total disponível de couro éde 6 unidades e que o lucro unitário por sapato é de $5,00 e o docinto é de $2,00, pede-se: o modelo do sistema de produção dosapateiro, se o objetivo é maximizar seu lucro por hora.
2 Um vendedor de frutas pode transportar 800 caixas de frutas para suaregião de vendas. Ele necessita transportar 200 caixas de laranjas a$20,00 de lucro por caixa, pelo menos 100 caixas de pêssegos a $10,00de lucro por caixa, e no máximo 200 caixas de tangerinas a $30,00 delucro por caixa. De que forma deverá ele carregar o caminhão paraobter o lucro máximo? Construa o modelo do problema.
GSI027 Otimização 2o Semestre � 2019 70 / 355
Exercícios II
3 Uma fundição tem de produzir 10 toneladas de um tipo de ligametálica e, para isso, tem disponível: lingotes de ferro, gra�te esucata. 2 componentes são relevantes para a liga: carbono e silício. Atabela fornece a fração destes elementos nos ingredientes disponíveis,seus custos unitários, suas disponibilidades em estoque, bem como acomposição da liga de acordo com as especi�cações. Quaisquantidades dos ingredientes devem compor a liga, de modo que asespeci�cações sejam satisfeitas e o custo seja mínimo?
Ingredientes Especi�cações ligaComposição (%) Lingotes Gra�te Sucata Mínimo Máximo
Carbono 0,0050 0,90 0,090 0,00 0,095Silício 0,14 - 0,27 0,19 0,20
Custos (R$/ton) 90 180 25Estoque (ton) 5 5 12
GSI027 Otimização 2o Semestre � 2019 71 / 355
Referências
1 ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H.Pesquisa operacional: para cursos de engenharia. Rio de Janeiro:Elsevier Brasil, 2006.
2 MARINS, F. A. S. Introdução à pesquisa operacional. São Paulo:Cultura Acadêmica, 2011.
3 NOGUEIRA, F. Pesquisa Operacional, UFJF.4 TAHA, H. Pesquisa operacional. 8a. ed. São Paulo: Prentice Hall,
2008.
Os materiais de parte desta seção foram gentilmente cedidos por Paulo H.R. Gabriel (FACOM/UFU)Adaptações: Renato Pimentel, FACOM/UFU
GSI027 Otimização 2o Semestre � 2019 72 / 355
Sumário
3 Solução grá�ca
GSI027 Otimização 2o Semestre � 2019 73 / 355
Solução grá�ca
A visualização de soluções de um problema pode ser útil paramelhorar a intuição sobre o mesmo.
Mesmo quando somente limitada a um desenho esquematizado sobreo plano.
No caso de PL, permite delinear um método de solução � i.é.,encontrar a solução ótima.
GSI027 Otimização 2o Semestre � 2019 74 / 355
Consideram-se aqui problemas com apenas duas variáveis
(Representação das soluções factíveis e da solução ótima num planocartesiano)
NotaVamos considerar, por questões de conveniência, todas as restrições sob aforma de inequações.
GSI027 Otimização 2o Semestre � 2019 75 / 355
Exemplo
Maximizar f (x1, x2) = x1 + 2x2 sujeito a:
x1 + x2 ≤ 4
x1 ≤ 2
x2 ≤ 3
x1 ≥ 0, x2 ≥ 0
GSI027 Otimização 2o Semestre � 2019 76 / 355
Condições de não-negatividade:
0 1 2 3 4 5 6 70
1
2
3
4
5
6
x1
x 2
GSI027 Otimização 2o Semestre � 2019 77 / 355
Adicionando a restrição x1 + x2 ≤ 4 às de não-negatividade:
0 1 2 3 4 5 6 70
1
2
3
4
5
6
x1
x 2
GSI027 Otimização 2o Semestre � 2019 78 / 355
Adicionando a restrição x1 ≤ 2 às anteriores:
0 1 2 3 4 5 6 70
1
2
3
4
5
6
x1
x 2
GSI027 Otimização 2o Semestre � 2019 79 / 355
Por �m, adicionando a restrição x2 ≤ 3 às anteriores: obtém-se aregião factível ou região viável do problema:qualquer ponto da região é uma solução viável do mesmo.
0 1 2 3 4 5 6 70
1
2
3
4
5
6
x1
x 2
GSI027 Otimização 2o Semestre � 2019 80 / 355
Determinação da solução ótima
Considerando o exemplo, a função objetivo
f (x1, x2) = x1 + 2x2,
pode assumir in�nitos valores � qualquer par (x1, x2).Os pontos (x1, x2) do R2 que resultam em f = 0 estão na retax1 + 2x2 = 0. Esta reta de�ne a curva de nível 0 da função.
Curva de nível
A curva de nível f0 de uma função f é dada pelo conjunto de pontos no R2
os quais, aplicados à função f , resultam em f = f0.
GSI027 Otimização 2o Semestre � 2019 81 / 355
Representando a curva de nível 0 no grá�co, junto com o sentido decrescimento.
1 2 3 4 5 6 7
1
2
3
4
5
6
x1
x2
GSI027 Otimização 2o Semestre � 2019 82 / 355
Vetor gradiente
O vetor gradiente de uma função f (x1, x2), dado por
∇f (x1, x2) =
(∂f
∂x1,∂f
∂x2
)indica o sentido de maior crescimento da função. Se a função for linear,o gradiente será constante (a direção e o sentido não variam)
Consequentemente, indica a direção onde as curvas de f assumemvalores maiores.
No caso de retas, é constante e perpendicular às mesmas.
ObservaçãoNa prática, também podemos testar tomando pontos de um lado e deoutro de uma curva de nível, e veri�cando o valor de f .
GSI027 Otimização 2o Semestre � 2019 83 / 355
Temos, para a função objetivo do problema,
∇f (x1, x2) =
(∂
∂x1(x1 + 2x2),
∂
∂x2(x1 + 2x2)
)= (1, 2),
indicado pelo vetor representado no grá�co anterior.
GSI027 Otimização 2o Semestre � 2019 84 / 355
Como se deseja maximizar a função objetivo, busca-se o maior valorpossível de f dentro da região viável. Portanto, �caminha-se� no sentidopara o qual o vetor gradiente aponta.
GSI027 Otimização 2o Semestre � 2019 85 / 355
Acrescentando-se agora ao grá�co a curva de nível 2:
1 2 3 4 5 6 7
1
2
3
4
5
6
x1
x2
Ainda não se chegou à solução ótima.
GSI027 Otimização 2o Semestre � 2019 86 / 355
Acrescentando-se a curva de nível 7:
1 2 3 4 5 6 7
1
2
3
4
5
6
Solução ótima
x1
x2
Solução ótima obtida (f (x1, x2) = 7).
Portanto, a solução do problema existe e é única: (x1, x2) = (1, 3) �maximiza f , respeitando as restrições.
GSI027 Otimização 2o Semestre � 2019 87 / 355
Considerações
1 O conjunto de todas as soluções viáveis de um modelo de PL é umconjunto convexo.
2 Toda solução viável básica do sistema de equações lineares de ummodelo de PL é um ponto extremo do conjunto de soluções viáveis.
3 Se uma função objetivo possui um único ponto de ótimo �nito, entãoeste é um ponto extremo do conjunto convexo de soluções viáveis.
4 Se a função objetivo assume o valor ótimo em mais de um ponto doconjunto de soluções viáveis (soluções múltiplas), então ela assumeeste valor para pelo menos dois pontos extremos do conjuntoconvexo e para qualquer combinação convexa desses pontosextremos, isto é, todos os pontos do segmento de reta que une estesdois pontos (em outras palavras, a aresta do polígono que contémestes dois pontos).
GSI027 Otimização 2o Semestre � 2019 88 / 355
Solução do problema das geladeiras
Voltando ao modelo da produção de geladeiras (mix de produção):
max L = 100x1 + 50x2
sujeito a
10x1 + 8x2 ≤ 25000
x1 + x2 ≤ 4500
x1 ≤ 1500
x2 ≤ 6000
x1 ≥ 0; x2 ≥ 0
GSI027 Otimização 2o Semestre � 2019 89 / 355
Restrições de não-negatividade e demanda máxima:
2 000 4 000 6 000 8 000
2 000
4 000
6 000
8 000
0 ≤ x1 ≤ 1 5000 ≤ x2 ≤ 6 000
x1
x2
GSI027 Otimização 2o Semestre � 2019 90 / 355
x1 + x2 ≤ 4 500 (capacidade da linha de montagem)
2 000 4 000 6 000 8 000
2 000
4 000
6 000
8 000
x1
x2
GSI027 Otimização 2o Semestre � 2019 91 / 355
10x1 + 8x2 ≤ 25 000 (limitação da mão-de-obra)
2 000 4 000 6 000 8 000
2 000
4 000
6 000
8 000
x1
x2
GSI027 Otimização 2o Semestre � 2019 92 / 355
max f (x1, x2) = 100x1 + 50x2I Sentido de crescimento: ∇f = (100, 50)
2 000 4 000 6 000 8 000
2 000
4 000
6 000
8 000
x1
x2
Candidatos a solução ótima: pontos (1500, 0), (1500, 1250) e(0, 3125) (pontos extremos na direção do crescimento)
GSI027 Otimização 2o Semestre � 2019 93 / 355
max f (x1, x2) = 100x1 + 50x2I Na solução viável básica (1500, 0), temos f = 150 000.
2 000 4 000 6 000 8 000
2 000
4 000
6 000
8 000
x1
x2
GSI027 Otimização 2o Semestre � 2019 94 / 355
max f (x1, x2) = 100x1 + 50x2I Na solução viável básica (1500, 1250), temos f = 212 500.
2 000 4 000 6 000 8 000
2 000
4 000
6 000
8 000
Solução ótima
x1
x2
Esta é a solução ótima, pois a solução viável básica não testada �(0, 3125) � está no sentido oposto ao de crescimento da funçãoobjetivo, em relação à curva de nível.
GSI027 Otimização 2o Semestre � 2019 95 / 355
Logo, a empresa deve produzir 1500 geladeiras do modelo luxo, e 1250do modelo básico por mês, maximizando o lucro, que será de $212 500.
GSI027 Otimização 2o Semestre � 2019 96 / 355
Solução do problema da ração
Voltando ao modelo da ração (problema de mistura):
min C = 65x1 + 30x2
sujeito a:2x1 + 3x2 ≥ 7
3x1 + 2x2 ≥ 9
1x1 + 0x2 ≥ 1
x1 ≥ 0; x2 ≥ 0
GSI027 Otimização 2o Semestre � 2019 97 / 355
Não-negatividade
1 2 3 4
1
2
3
4
x1
x2
GSI027 Otimização 2o Semestre � 2019 98 / 355
1x1 + 0x2 ≤ 1.
1 2 3 4
1
2
3
4
x1
x2
GSI027 Otimização 2o Semestre � 2019 99 / 355
2x1 + 3x2 ≥ 7.
1 2 3 4
1
2
3
4
x1
x2
GSI027 Otimização 2o Semestre � 2019 100 / 355
3x1 + 2x2 ≥ 9.
1 2 3 4
1
2
3
4
x1
x2
GSI027 Otimização 2o Semestre � 2019 101 / 355
minC = 65x1 + 30x2I Na solução viável básica (7/2, 0), temos C = $227, 5.
1 2 3 4
1
2
3
4
(7/2,0)x1
x2
Problema de minimização: caminha-se no sentido oposto ao decrescimento de C .
GSI027 Otimização 2o Semestre � 2019 102 / 355
minC = 65x1 + 30x2I Na solução viável básica (13/5, 3/5), temos C = $187.
1 2 3 4
1
2
3
4
(13/5,3/5)x1
x2
GSI027 Otimização 2o Semestre � 2019 103 / 355
minC = 65x1 + 30x2I Na solução viável básica (1, 3), temos C = $155.
1 2 3 4
1
2
3
4Solução ótima
x1
x2
(1, 3) é a solução ótima do problema da ração. Neste ponto, o custototal é o menor possível, $ 155.
GSI027 Otimização 2o Semestre � 2019 104 / 355
Outras situações
Exemplo
Maximizar f (x1, x2) = x1 + 2x2 sujeito a:
−3x1 + x2 ≤ 2
x2 ≤ 3
x1 + 2x2 ≤ 9
3x1 + x2 ≤ 18
x1 ≥ 0, x2 ≥ 0
GSI027 Otimização 2o Semestre � 2019 105 / 355
max f (x1, x2) = x1 + 2x2
1 2 3 4 5 6 7 8
1
2
3
4 Múltiplassoluçõesótimas
x1
x2
GSI027 Otimização 2o Semestre � 2019 106 / 355
Região viável ilimitada
In�nitas soluções ótimas (minimização)
x1
x2
GSI027 Otimização 2o Semestre � 2019 107 / 355
Não existe solução ótima (minimização)
x1
x2
GSI027 Otimização 2o Semestre � 2019 108 / 355
Região vazia
Região viável vazia: não existe solução ótima (restrições con�itantes)
x1
x2
GSI027 Otimização 2o Semestre � 2019 109 / 355
Exercícios
1 Faça a solução grá�ca do exercício do sapateiro e do exercício dasfrutas vistos anteriormente. Dica: no problema das frutas, aquantidade de laranjas é conhecida (dada).
GSI027 Otimização 2o Semestre � 2019 110 / 355
Referências
1 ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H.Pesquisa operacional: para cursos de engenharia. Rio de Janeiro:Elsevier Brasil, 2006.
2 MARINS, F. A. S. Introdução à pesquisa operacional. São Paulo:Cultura Acadêmica, 2011.
Os materiais de parte desta seção foram gentilmente cedidos por Paulo H.R. Gabriel (FACOM/UFU)Adaptações: Renato Pimentel, FACOM/UFU
GSI027 Otimização 2o Semestre � 2019 111 / 355
Sumário
4 O método simplex
GSI027 Otimização 2o Semestre � 2019 112 / 355
O método simplex
O método simplex visa a resolução algébrica de um problema de PL.
Problemas agora não se limitam mais a 2 variáveis de decisão (comona solução grá�ca)
1o passo: Criação de Variáveis de folga ou excesso: transformam omodelo num sistema linear de equações a ser resolvido.
GSI027 Otimização 2o Semestre � 2019 113 / 355
Eliminação das desigualdades
Inicialmente, é preciso eliminar as desigualdades presentes nasrestrições do modelo.
I Criam-se assim novas equações lineares no problema, a partir dasinequações anteriores.
Exemplo:2x1 + x2 ≤ 5
Como o lado esquerdo é menor ou igual a 5 (a diferença édesconhecida), a adição de uma variável não-negativa, chamada, porexemplo, x3, que represente tal diferença, permite que a inequaçãoseja escrita como uma equação:
2x1 + x2 + x3 = 5
x3 ≥ 0 é denominada variável de folga.
GSI027 Otimização 2o Semestre � 2019 114 / 355
De modo similar, no caso da inequação
x1 + 3x2 ≥ 7,
onde tem-se o lado esquerdo maior ou igual ao lado direito, épossível representar a diferença pela subtração de uma variável defolga não-negativa:
x1 + 3x2 − x4 = 7 .
Algumas referências chamam neste caso a nova variável de variávelde excesso.
GSI027 Otimização 2o Semestre � 2019 115 / 355
ObservaçãoApenas as restrições técnicas são reescritas como equações.As restrições de não-negatividade são mantidas.
GSI027 Otimização 2o Semestre � 2019 116 / 355
Exemplo
maxZ (x1, x2) = 5x1 + 2x2
sujeito a
x1 ≤ 3
x2 ≤ 4
x1 + 2x2 ≤ 9
x1 ≥ 0, x2 ≥ 0
GSI027 Otimização 2o Semestre � 2019 117 / 355
maxZ (x1, x2, x3, x4, x5)− 5x1 − 2x2 = 0
sujeito a
x1 + x3 = 3
x2 + x4 = 4
x1 + 2x2 + x5 = 9
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0
Como a função objetivo é dada como uma equação, não é necessáriaa introdução de variáveis de folga na mesma.
Note que a função objetivo foi reescrita, de modo a deixar o ladodireito nulo.
GSI027 Otimização 2o Semestre � 2019 118 / 355
Quadro inicial
A tabela ou quadro abaixo auxilia na resolução:
x1 x2 x3 x4 x5 b
L(0)0 Z -5 -2 0 0 0 0
L(0)1 x3 1 0 1 0 0 3
L(0)2 x4 0 1 0 1 0 4
L(0)3 x5 1 2 0 0 1 9
Na linha L0 encontram-se os coe�cientes da função objetivo.
Nas linhas Li , i = 1, . . . , 3 os coe�cientes das restrições.
O vetor b contém as constantes das restrições, bem como da funçãoobjetivo.
GSI027 Otimização 2o Semestre � 2019 119 / 355
Solução viável básica inicial
x3 = 3 x1 = 0
x4 = 4 x2 = 0
x5 = 9 Z = 0
GSI027 Otimização 2o Semestre � 2019 120 / 355
Algoritmo I
1 A solução já é a ótima? Se sim, o problema encontra-se resolvido, e oalgoritmo se encerra nesta etapa.
I Este é um problema de maximização. A solução será ótima se nãohouver coe�cientes negativos na linha L0 da função objetivo.
I Caso haja � este é o caso do exemplo � é preciso passar à etapaseguinte, iterativa.
GSI027 Otimização 2o Semestre � 2019 121 / 355
Algoritmo II
2 As variáveis de folga formam uma base do Rm (m é o número derestrições), pois a matriz m ×m formada pelas linhas Li , i = 1, . . . ,me as respectivas colunas é uma matriz identidade, portanto comdeterminante diferente de 0.
I As variáveis de folga são chamadas portanto de básicas(representadas na coluna à esquerda na tabela), e as variáveis dedecisão originais do problema, não básicas.
I Esta etapa do algoritmo consiste em colocar na base uma variável dedecisão, retirando da mesma uma das variáveis de folga (deve serrepetida até que a condição da etapa 1 seja satisfeita)
GSI027 Otimização 2o Semestre � 2019 122 / 355
Etapas do passo 2 I
1 Identi�car quem entrará na base (condição de otimalidade):Regra de Dantzig: Procura-se, na linha L0, qual o coe�cientenegativo de maior valor absoluto (i.é., o menor valor). A variávelassociada a ele é a que entrará na base.
I No exemplo, entrará na base x1, pois | − 5| > | − 2|. A coluna emdestaque é a coluna pivô da iteração.
x1 x2 x3 x4 x5 b
L(0)0 Z -5 -2 0 0 0 0
L(0)1 x3 1 0 1 0 0 3
L(0)2 x4 0 1 0 1 0 4
L(0)3 x5 1 2 0 0 1 9
GSI027 Otimização 2o Semestre � 2019 123 / 355
Etapas do passo 2 II
2 A variável básica que sairá da base é aquela cuja divisão da constantebi , i = 1, . . . ,m3 pelo coe�ciente correspondente cij da coluna pivôseja o menor de todos � apenas divisões não-negativas e �nitassão consideradas. Esta é a Condição de viabilidade.
I No caso, temos m = 3, j = 1 (selecionou-se x1 para deixar a base) e asdivisões
b1c11
=31
= 3b2c21
=40
=∞ (ignora-se)b3c31
=91
= 9
I Portanto, x3 (associada a linha L1) deixará a base e a linha L1 passa aser a linha pivô desta iteração � razão mínima não-negativa nestalinha.
GSI027 Otimização 2o Semestre � 2019 124 / 355
Etapas do passo 2 III
x1 x2 x3 x4 x5 b
L(0)0
Z -5 -2 0 0 0 0
L(0)1
x3 1 0 1 0 0 3
L(0)2
x4 0 1 0 1 0 4
L(0)3
x5 1 2 0 0 1 9I O elemento c11 = 1, dado pelo cruzamento das linhas e colunas pivô, é
o número pivô da iteração.
GSI027 Otimização 2o Semestre � 2019 125 / 355
Etapas do passo 2 IV
3 Rede�ne-se a linha pivô, dividindo-se a mesma pelo número pivô.I No caso,
L(1)1
=L
(0)1
c11=
L(0)1
1
I Note que agora x1 faz parte da base, e x3 passou a ser não-básica.
x1 x2 x3 x4 x5 b
L(0)0
Z -5 -2 0 0 0 0
L(1)1
x1 1 0 1 0 0 3
L(0)2
x4 0 1 0 1 0 4
L(0)3
x5 1 2 0 0 1 9
GSI027 Otimização 2o Semestre � 2019 126 / 355
Etapas do passo 2 V
4 As demais linhas (incluindo a da função objetivo) são tambémrede�nidas:
L(1)k = L
(0)k − ckj L
(1)i , k = 0, . . . ,m, k 6= i ,
onde i e j são os índices da linha pivô e coluna pivô, respectivamente.
GSI027 Otimização 2o Semestre � 2019 127 / 355
Etapas do passo 2 VI
I Linha 0 (função objetivo): L(1)0
= L(0)0− (−5) L
(1)1
x1 x2 x3 x4 x5 b
L(1)0
Z 0 -2 5 0 0 15
L(1)1
x1 1 0 1 0 0 3
L(0)2
x4 0 1 0 1 0 4
L(0)3
x5 1 2 0 0 1 9
GSI027 Otimização 2o Semestre � 2019 128 / 355
Etapas do passo 2 VII
I Linha 2: L(1)2
= L(0)2− 0 L(1)
1= L
(0)2
(inalterada)
x1 x2 x3 x4 x5 b
L(1)0
Z 0 -2 5 0 0 15
L(1)1
x1 1 0 1 0 0 3
L(1)2
x4 0 1 0 1 0 4
L(0)3
x5 1 2 0 0 1 9
GSI027 Otimização 2o Semestre � 2019 129 / 355
Etapas do passo 2 VIII
I Linha 3: L(1)3
= L(0)3− 1 L(1)
1
x1 x2 x3 x4 x5 b
L(1)0
Z 0 -2 5 0 0 15
L(1)1
x1 1 0 1 0 0 3
L(1)2
x4 0 1 0 1 0 4
L(1)3
x5 0 2 -1 0 1 6I A primeira iteração está concluída.
Solução viável básica após iteração 1
x1 = 3 x2 = 0
x4 = 4 x3 = 0
x5 = 6 Z = 15
3Linha L0 da função objetivo não é considerada neste trechoGSI027 Otimização 2o Semestre � 2019 130 / 355
Nova iteração do passo 2
Como se pode observar na tabela anterior, ainda há um coe�cientenegativo na linha L0.Portanto, repete-se o passo 2.
I Agora x2 entrará na base, e x5 sairá. Portanto, o número pivô éC23 = 2.
GSI027 Otimização 2o Semestre � 2019 131 / 355
x1 x2 x3 x4 x5 b
L(2)0 Z 0 0 4 0 1 21
L(2)1 x1 1 0 1 0 0 3
L(2)2 x4 0 0 1/2 1 -1/2 1
L(2)3 x2 0 1 -1/2 0 1/2 3
Solução viável básica após iteração 2 (solução ótima)
x1 = 3 x3 = 0
x4 = 1 x5 = 0
x2 = 3 Z = 21
GSI027 Otimização 2o Semestre � 2019 132 / 355
Situações especiais
1. Empate na entrada da base
Na condição de otimalidade, quando se busca a variável que entrará nabase, se houver empate escolhe-se arbitrariamente qual deverá de fatoentrar.Única implicação: pode-se escolher um caminho mais longo ou mais curto� dependendo da escolha � para se chegar à solução ótima
Exemplo: problema envolvendo maximização da função objetivo
Z = 4x1 + 4x2 + 3x3
Note que o maior coe�ciente é 4, e está associado a duas variáveis (x1 ex2). Na 1a. iteração, deve-se escolher qual das duas entrará (aparecerãocomo -4 no quadro inicial).
GSI027 Otimização 2o Semestre � 2019 133 / 355
2. Empate na saída da base
Na condição de viabilidade, quando se busca a variável que sairá na base,se houver empate em geral também se escolhe arbitrariamente qual deveráde fato sair.
Exemplo:maxZ = 5x1 + 2x2, sujeito a
x1 ≤ 3
x2 ≤ 4
4x1 + 3x2 ≤ 12
x1 ≥ 0, x2 ≥ 0
GSI027 Otimização 2o Semestre � 2019 134 / 355
x1 x2 x3 x4 x5 b
L(0)0 Z -5 -2 0 0 0 0
L(0)1 x3 1 0 1 0 0 3
L(0)2 x4 0 1 0 1 0 4
L(0)3 x5 4 3 0 0 1 12
x1 entrará na base. As candidatas a sair da base (menor razãonão-negativa):
x3 :b1c11
=31
= 3 x5 :b3c31
=124
= 3
Escolhe-se, por exemplo, x3 para deixar a base:
GSI027 Otimização 2o Semestre � 2019 135 / 355
x1 ↓ x2 x3 x4 x5 b
L(1)0 Z 0 -2 5 0 0 15
L(1)1 x1 1 0 1 0 0 3
L(1)2 x4 0 1 0 1 0 4
L(1)3 ← x5 0 3 -4 0 1 0
Note que x5 é nula, mesmo sendo variável básica. Isto ocorre devido àcondição de empate e a solução viável encontrada é dita degenerada.
GSI027 Otimização 2o Semestre � 2019 136 / 355
x1 x2 x3 x4 x5 b
L(2)0 Z 0 0 7/3 0 2/3 15
L(2)1 x1 1 0 1 0 0 3
L(2)2 x4 0 0 4/3 1 -1/3 4
L(2)3 x2 0 1 -4/3 0 1/3 0
Pode ocorrer a ciclagem (ou retorno cíclico) � o valor da função objetivonão melhora, sendo possível que o método entre em uma sequência deiterações sem nunca melhorar tal valor e satisfazer a condição deotimalidade. Neste exemplo, esta última foi satisfeita (encontrou-se soluçãoótima).
GSI027 Otimização 2o Semestre � 2019 137 / 355
Exemplo de caso em que ocorre ciclagem (Taha, 2008):
maxZ =34x1 − 20x2 +
12x3 − 6x4
sujeito a
14x1 − 8x2 − x3 + 9x4 ≤ 0
12x1 − 12x2 −
12x3 + 3x4 ≤ 0
x3 ≤ 1
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
Exercício: http://simplex.tode.cz/en/
GSI027 Otimização 2o Semestre � 2019 138 / 355
3. Soluções múltiplas
Modelo de PL apresenta mais de uma solução ótima.
Exemplo:maxZ = 2x1 + 4x2, sujeito a
x1 + 2x2 ≤ 5
x1 + x2 ≤ 4
x1 ≥ 0, x2 ≥ 0
GSI027 Otimização 2o Semestre � 2019 139 / 355
x1 ↓ x2 x3 x4 b
L(0)0 Z -2 -4 0 0 0
L(0)1 ← x3 1 2 1 0 5
L(0)2 x4 1 1 0 1 4
↓ x1 x2 x3 x4 b
L(1)0 Z 0 0 2 0 10
L(1)1 x2 1/2 1 1/2 0 5/2
L(1)2 ← x4 1/2 0 -1/2 1 3/2
A solução é ótima, e tem-se x1 = 0, x2 = 5/2 e Z = 10. O coe�ciente dex1 (não-básica) em L0 é zero, indicando que a mesma pode entrar na base,de modo que o valor da função objetivo �que inalterado � apenas osvalores das variáveis se alteram.
GSI027 Otimização 2o Semestre � 2019 140 / 355
x1 x2 x3 x4 b
L(2)0 Z 0 0 2 0 10
L(2)1 x2 0 1 1 -1 1
L(2)2 x1 1 0 -1 2 3
Forçando-se a saída de x4 da base, inserindo-se x1 em seu lugar, tem-senova solução em x1 = 3, x2 = 1 e Z = 10.Qualquer combinação convexa desta solução e da anterior também seráuma solução ótima. Gra�camente: segmento de reta entre os pontos(0, 5/2) e (3, 1)
GSI027 Otimização 2o Semestre � 2019 141 / 355
4. Função objetivo ilimitada
Outro resultado possível é aquele no qual nenhuma variável sequali�ca para ser a variável básica a deixar a base.
Este resultado ocorre quando a variável que entra na base pode seraumentada inde�nidamente sem dar valores negativos a qualquer dasvariáveis básicas atuais. Na forma tabular, isso signi�ca que todos oscoe�cientes da coluna pivô (excluindo-se a linha L0) são negativos ouzero.
Neste caso, as restrições não impedem que o valor da função objetivocresça inde�nidamente.
Isto ocorre, provavelmente, porque o modelo foi mal formulado, sejapor omitir restrições relevantes, seja por declará-las de modo incorreto.
GSI027 Otimização 2o Semestre � 2019 142 / 355
Exemplo:maxZ = 2x1 + x2 sujeito a
x1− x2 ≤ 10
2x1 ≤ 40
x1 ≥ 0, x2 ≥ 0
↓ x1 x2 x3 x4 b
L(0)0 Z -2 -1 0 0 0
L(0)1 ← x3 1 -1 1 0 10
L(0)2 x4 2 0 0 1 40
Todos os coe�cientes das restrições sob x2 são negativos ou zero. Note quex2 pode ser aumentada inde�nidamente sem desobedecer nenhuma dasrestrições.
GSI027 Otimização 2o Semestre � 2019 143 / 355
x1 ↓ x2 x3 x4 b
L(1)0 Z 0 -3 2 0 20
L(1)1 x1 1 -1 1 0 10
L(1)2 ← x4 0 2 -2 1 20
x1 x2 ↓ x3 x4 b
L(2)0 Z 0 0 -1 3/2 50
L(2)1 ← x1 0 0 0 1/2 30
L(2)2 x2 0 1 -1 1/2 10
. . .
GSI027 Otimização 2o Semestre � 2019 144 / 355
5. Problema de minimizaçãoQuando a função objetivo tiver de ser minimizada pode-se fazer duascoisas, a saber:
Inverter o teste de otimização e o critério de entrada na base. Assim,se todos os coe�cientes da linha L0 forem negativos, ou nulos, asolução é ótima. Caso contrário, escolha a variável xj para entrar queapresente o maior valor.
Transformar o problema de minimização em um problema demaximização. Sabe-se que achar o mínimo de uma função éequivalente a encontrar o máximo do simétrico desta função.
I Exemplo: minW = 2x1 + 3x2 ⇔ maxZ = −2x1 − 3x2. Depois, nasolução �nal, fazer W = −Z .
GSI027 Otimização 2o Semestre � 2019 145 / 355
Um aspecto de problemas de minimização é que em geral as restriçõescontém desigualdades do tipo ≥ (maior-ou-igual).
Os exemplos abordados com o simplex são todos problemas demaximização, onde as restrições são do tipo
ci1x1 + ci2x2 + · · ·+ cinxn ≤ bi ,
onde a constante do lado direito bi é tal que bi ≥ 0.I Sob esta forma, as variáveis acrescentadas são de folga e o problema
pode ser resolvido como visto.I Problemas com restrições envolvendo a desigualdade ≥ ou mesmo
igualdade (=) exigem etapas adicionais.
GSI027 Otimização 2o Semestre � 2019 146 / 355
Lado direito negativo
Para que a resolução vista possa ser empregada, é preciso que o ladodireito das restrições seja não-negativo.
Por exemplo, a restrição
−x1 + x2 ≤ −3
leva ao surgimento da equação
−x1 + x2 + x3 = −3, x3 ≥ 0 .
GSI027 Otimização 2o Semestre � 2019 147 / 355
O problema é resolvido fazendo-se a multiplicação de ambos os ladospor −1:
x1 − x2 − x3 = 3 .
Neste caso, o coe�ciente de x3 é −1. Logo, esta não pode entrar nabase (na equação reescrita é variável de excesso). Isto equivale apartirmos da inequação
x1 − x2 ≥ 3 .
(nada mais do que a inequação original multiplicada por −1 � adesigualdade é invertida).
GSI027 Otimização 2o Semestre � 2019 148 / 355
Solução inicial arti�cial
Para se iniciar a resolução de problemas de PL �mal comportados�(com restrições do tipo ≥ e =) é adotar variáveis arti�ciais
Estas desempenham o papel de folgas na primeira iteração.
São descartadas em iterações posteriores.Dois métodos:
I Método do M-grande;I Método das duas fases.
GSI027 Otimização 2o Semestre � 2019 149 / 355
Considere o seguinte problema:
maxZ = 5x1 + 2x2sujeito a:
x1 ≤ 3
x2 ≤ 4
x1 + 2x2 ≥ 9
x1 ≥ 0, x2 ≥ 0
maxZ tal que Z − 5x1 − 2x2 = 0sujeito a:
x1 + x3 = 3
x2 + x4 = 4
x1 + 2x2 − x5 = 9
x1, . . . , x5 ≥ 0
Variáveis não-básicas: x1 = x2 = 0.
Variáveis básicas: x3 = 3, x4 = 4, x5 = −9.Não é solução viável, pois x5 deveria ser não-negativa.
GSI027 Otimização 2o Semestre � 2019 150 / 355
Pode-se acrescentar uma variável arti�cial na equação problemática. Estavariável ocupará o lugar de x5 na base inicial. Logo:
maxZ tal que Z − 5x1 − 2x2 = 0sujeito a:
x1 + x3 = 3
x2 + x4 = 4
x1 + 2x2 − x5 + t1 = 9
x1, . . . , x5, t1 ≥ 0
Variáveis não-básicas:x1 = x2 = x5 = 0.
Variáveis básicas:x3 = 3, x4 = 4, t1 = 9.
Os sistemas somente se equivalem se a variável arti�cial t1 for nula.
As variáveis arti�ciais não têm signi�cado no problema real, maspermitem a inicialização do processo de maneira automática.
GSI027 Otimização 2o Semestre � 2019 151 / 355
Método do M-grande
Como as variáveis arti�ciais não fazem parte do modelo, estas sofrerãopunições na função objetivo:
I As punições visam zerar tais variáveis na solução ótima.I Isto sempre ocorrerá se houver solução viável.
Regra de penalização das variáveis arti�ciais
Dado M > 0, valor su�cientemente alto (M →∞), o coe�ciente na funçãoobjetivo representa uma punição adequada quando igual a:
I −M, em problemas de maximização;
I M, em problemas de maximização.
O valor de M deve ser su�cientemente grande em relação aos demaiscoe�cientes da função objetivo, de modo a forçar as variáveis a tervalor nulo no ótimo.
GSI027 Otimização 2o Semestre � 2019 152 / 355
Retornando ao exemplo anterior:
maxZ = 5x1 + 2x2 −Mt1sujeito a:
x1 + x3 = 3
x2 + x4 = 4
x1 + 2x2 − x5 + t1 = 9
x1, . . . , x5, t1 ≥ 0
maxZ tal queZ − 5x1 − 2x2 + 100t1 = 0sujeito a:
x1 + x3 = 3
x2 + x4 = 4
x1 + 2x2 − x5 + t1 = 9
x1, . . . , x5, t1 ≥ 0
Como os coe�cientes na função objetivo são 5 e 2, parece razoávelde�nir M = 100.
GSI027 Otimização 2o Semestre � 2019 153 / 355
Quadro inicial:
x1 x2 x3 x4 x5 t1 b
L(0)0 Z -5 -2 0 0 0 100 0
L(0)1 x3 1 0 1 0 0 0 3
L(0)2 x4 0 1 0 1 0 0 4
L(0)3 t1 1 2 0 0 -1 1 9
A linha L0 é inconsistente com o resto da tabela, uma vez que t1 = 9(t1 está na base) e portanto Z = −900.Para empregar a resolução do simplex, é preciso que os coe�cientesdas variáveis básicas na linha L0 sejam todos nulos. Este ajuste inicialpode ser feito rede�nindo-se esta linha como sendo a soma delamesma com a linha associada a t1 multiplicada por −M:
L(0)0 = L
(0)0 −ML
(0)3 = L
(0)0 − 100L(0)
3
GSI027 Otimização 2o Semestre � 2019 154 / 355
O quadro inicial então se torna
x1 ↓ x2 x3 x4 x5 t1 b
L(0)0 Z -105 -202 0 0 100 0 -900
L(0)1 x3 1 0 1 0 0 0 3
L(0)2 ← x4 0 1 0 1 0 0 4
L(0)3 t1 1 2 0 0 -1 1 9
Solução viável básica inicial
x3 = 3 x1 = 0
x4 = 4 x2 = 0
t1 = 9 x5 = 0
Z = −900
GSI027 Otimização 2o Semestre � 2019 155 / 355
↓ x1 x2 x3 x4 x5 t1 b
L(1)0 Z -105 0 0 202 100 0 -92
L(1)1 x3 1 0 1 0 0 0 3
L(1)2 x2 0 1 0 1 0 0 4
L(1)3 ← t1 1 0 0 -2 -1 1 1
x1 x2 x3 ↓ x4 x5 t1 b
L(2)0 Z 0 0 0 -8 -5 105 13
L(2)1 ← x3 0 0 1 2 1 -1 2
L(2)2 x2 0 1 0 1 0 0 4
L(2)3 x1 1 0 0 -2 -1 1 1
GSI027 Otimização 2o Semestre � 2019 156 / 355
x1 x2 x3 x4 ↓ x5 t1 b
L(3)0 Z 0 0 4 0 -1 101 21
L(3)1 ← x4 0 0 1/2 1 1/2 -1/2 1
L(3)2 x2 0 1 -1/2 0 -1/2 1/2 3
L(3)3 x1 1 0 1 0 0 0 3
x1 x2 x3 x4 x5 t1 b
L(4)0 Z 0 0 5 2 0 100 23
L(4)1 x5 0 0 1 2 1 -1 2
L(4)2 x2 0 1 0 1 0 0 4
L(4)3 x1 1 0 1 0 0 0 3
GSI027 Otimização 2o Semestre � 2019 157 / 355
O método do M-grande pode resultar em erros de arredondamentodurante a fase de punição do valor M � de�nido sempre de formarelativamente arbitrária.
Na prática, usa-se o método das duas fases, desenvolvidoposteriormente.
O método das duas fases está implementado em praticamente todosos pacotes comerciais para resolução de problemas de PL.
GSI027 Otimização 2o Semestre � 2019 158 / 355
Método das duas fases
Alternativa ao método do M-grande, contornando a di�culdade domesmo por eliminar o uso da constante M.
Inicialmente, variáveis arti�ciais são introduzidas ao modelo, como nométodo anterior.Como o nome sugere, há duas fases ou etapas:
I Fase I: consiste em resolver um problema de minimização cujafunção objetivo é dada pelo somatório das variáveis arti�ciais.Espera-se que o mínimo seja zero (requisito para Fase II).
ObservaçãoCaso o valor mínimo da soma seja diferente de zero, o problema não temnenhuma solução viável, o que encerra o processo � variável arti�cial positivaindica que restrição original não foi satisfeita.
I Fase II: Usa-se a solução da Fase I como solução viável básica inicialpara o problema original.
GSI027 Otimização 2o Semestre � 2019 159 / 355
Seja o problema:
maxZ = 4x1 + x2
sujeito a
3x1 + x2 = 3
4x1 + 3x2 ≥ 6
x1 + 2x2 ≤ 4
x1 ≥ 0, x2 ≥ 0
Variáveis de folga:
maxZ = 4x1 + x2
sujeito a
3x1 + x2 = 3
4x1 + 3x2 − x3 = 6
x1 + 2x2 + x4 = 4
x1 ≥ 0, . . . , x4 ≥ 0
GSI027 Otimização 2o Semestre � 2019 160 / 355
Como não há uma solução viável básica são inseridas as variáveis arti�ciaist1 e t2 às restrições envolvendo ≥ e =:
maxZ = 4x1 + x2
sujeito a
3x1 + x2 + t1 = 3
4x1 + 3x2 − x3 + t2 = 6
x1 + 2x2 + x4 = 4
x1 ≥ 0, . . . , x4 ≥ 0, t1 ≥ 0, t2 ≥ 0 .
A função objetivo inicial será portanto
W = t1 + t2
GSI027 Otimização 2o Semestre � 2019 161 / 355
Fase I
minW = t1 + t2
sujeito a
3x1 + x2 + t1 = 3
4x1 + 3x2 − x3 + t2 = 6
x1 + 2x2 + x4 = 4
x1 ≥ 0, . . . , x4 ≥ 0, t1 ≥ 0, t2 ≥ 0 .
GSI027 Otimização 2o Semestre � 2019 162 / 355
x1 x2 x3 x4 t1 t2 b
L(0)0 −W 0 0 0 0 1 1 0
L(0)1 t1 3 1 0 0 1 0 3
L(0)2 t2 4 3 -1 0 0 1 6
L(0)3 x4 1 2 0 1 0 0 4
Como a linha L0 possui coe�cientes para variáveis t1 e t2 da base, faz-seL
(0)0 = L
(0)0 − L
(0)1 − L
(0)2 :
1 ↓ x1 x2 x3 x4 t1 t2 b
L(0)0 −W -7 -4 1 0 0 0 -9
L(0)1 ← t1 3 1 0 0 1 0 3
L(0)2 t2 4 3 -1 0 0 1 6
L(0)3 x4 1 2 0 1 0 0 4
GSI027 Otimização 2o Semestre � 2019 163 / 355
x1 ↓ x2 x3 x4 t1 t2 b
L(1)0 −W 0 -5/3 1 0 7/3 0 -2
L(1)1 x1 1 1/3 0 0 1/3 0 1
L(1)2 ← t2 0 5/3 -1 0 -4/3 1 2
L(1)3 x4 0 5/3 0 1 -1/3 0 3
x1 x2 x3 x4 t1 t2 b
L(2)0 −W 0 0 0 0 1 1 0
L(2)1 x1 1 0 1/5 0 3/5 -1/5 3/5
L(2)2 x2 0 1 -3/5 0 -4/5 3/5 6/5
L(2)3 x4 0 0 1 1 1 1 1
GSI027 Otimização 2o Semestre � 2019 164 / 355
No quadro (2), −W = 0, e não há coe�cientes negativos para asvariáveis fora da base. Portanto, a fase I está concluída.
A solução básica viável é dada por:
x1 = 3/5 x2 = 6/5 x4 = 1
(apenas variáveis básicas). As demais, bem como a função objetivo Wsão nulas.
Neste momento, pode-se eliminar totalmente as colunas das variáveisarti�ciais t1 e t2 e passar à fase II.
I Eliminam-se também as linhas, quando for o caso (variáveis arti�ciaisfora da base).
GSI027 Otimização 2o Semestre � 2019 165 / 355
Fase II
Após eliminar as colunas das variáveis arti�ciais, reescreve-se o problemaoriginal como:
maxZ = 4x1 + x2
sujeito a
x1 + 1/5x3 = 3/5
x2 − 3/5x3 = 6/5
x3 + x4 = 1
x1 ≥ 0, . . . , x4 ≥ 0 .
GSI027 Otimização 2o Semestre � 2019 166 / 355
Quadro inicial desta fase � note que é preciso adequar a linha L0 antes deprosseguir para o algoritmo do simplex:
x1 x2 x3 x4 b
L(0)0 Z -4 -1 0 0 0
L(0)1 x1 1 0 1/5 0 3/5
L(0)2 x2 0 1 -3/5 0 6/5
L(0)3 x4 0 0 1 1 1
GSI027 Otimização 2o Semestre � 2019 167 / 355
Exercícios I
1 Determine a solução ótima a partir do quadro anterior (Fase II).2 Usando simplex, determine a solução do problema
min f (x1, x2) = 65x1 + 30x2
sujeito a
2x1 + 3x2 ≥ 7
3x1 + 2x2 ≥ 9
x1 ≥ 1
x1 ≥ 0, x2 ≥ 0 .
GSI027 Otimização 2o Semestre � 2019 168 / 355
Sumário
5 Dual e sua relação com o primal
GSI027 Otimização 2o Semestre � 2019 169 / 355
Dualidade
Modelo dual: de�nido diretamente a partir do modelo original (ouprimal) do problema de PL.Forte relação com o problema de origem:
I Solução ótima de um problema fornece automaticamente a soluçãoótima do outro.
Vantagens
Uma vantagem do uso do modelo dual está na possibilidade de segerar um problema menor, cuja solução seja mais rápida/menos caraque no modelo original.
Outra vantagem: transformar um problema de minimização num demaximização � o que permite aplicação direta do algoritmo simplex.
GSI027 Otimização 2o Semestre � 2019 170 / 355
Forma de equações do modelo primal
A construção do modelo dual será baseada na chamada forma deequações (TAHA, 2008) do modelo original, usada para a resolução peloalgoritmo do simplex. Na forma de equações:
1 Todas as restrições técnicas � isto é, excluindo-se as denão-negatividade � são dadas como equações, com o lado direitonão negativo.
2 Todas as variáveis são maiores ou iguais a zero.
GSI027 Otimização 2o Semestre � 2019 171 / 355
Construção do modelo dual com base no primal
1 O dual de um problema de maximização (minimização) é um problemade minimização (maximização);
2 Uma variável yi do dual é de�nida para cada restrição4 do primal;3 Uma restrição dual é de�nida para cada variável xj primal;4 Os coe�cientes associados à variável xj das restrições do modelo
primal de�nirão os coe�cientes da j-ésima restrição primal;5 Os coe�cientes da função objetivo do dual são dados pelas
constantes (lado direito) das restrições do primal;
4Não se consideram as de não-negatividadeGSI027 Otimização 2o Semestre � 2019 172 / 355
No caso de um problema de maximização � somente com restrições do tipo≤, temos:
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
ajiyi ≥ cj , (j = 1, . . . , n)
yi ≥ 0
GSI027 Otimização 2o Semestre � 2019 173 / 355
Exemplo
Primal:
maxZ = 25x1 + 20x2
sujeito a
x1 + x2 ≤ 50
2x1 + x2 ≤ 80
2x1 + 5x2 ≤ 220
x1 ≥ 0, x2 ≥ 0 .
Dual:
minD = 50y1 + 80y2 + 220y3
sujeito a
y1 + 2y2 + 2y3 ≥ 25
y1 + y2 + 5y3 ≥ 20
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0 .
GSI027 Otimização 2o Semestre � 2019 174 / 355
Note pelo caso geral e exemplo vistos que o sinal de desigualdade dasrestrições duais está associado ao tipo de otimização: se o dual forde minimização, todas as restrições serão (≥).Outro fato é que as variáveis duais yi são não negativas, mas nemsempre isto ocorre.
Casos mais gerais, onde no modelo primal há restrições (≥) e (=), ouhá variáveis irrestritas (podem assumir valores negativos), levam aoutras situações no dual.
GSI027 Otimização 2o Semestre � 2019 175 / 355
Regras para construção do dual
Restrições de sinal das variáveis duais: de acordo com os coe�cientesdas variáveis de folga do primal.
Exemplo:
minZ = 15x1 + 12x2
sujeito a
x1 + 2x2 ≥ 3
2x1 − 4x2 ≤ 5
x1 ≥ 0, x2 ≥ 0 .
GSI027 Otimização 2o Semestre � 2019 176 / 355
Na forma de equações:
minZ = 15x1+12x2+0x3+0x4
sujeito a
x1 + 2x2 − x3 + 0x4 = 3 (y1)
2x1 − 4x2 + 0x3 + x4 = 5 (y2)
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 .
Dual:
maxD = 3y1 + 5y2
sujeito a
y1 + 2y2 ≤ 15
−2y1 − 4y2 ≤ 12
−1y1 + 0y2 ≤ 0
0y1 + 1y2 ≤ 0 .
As 2 últimas restrições duais estão associadas às variáveis de folga x3 ex4. Note que todas são do tipo (≤) pois o dual é de maximização.
GSI027 Otimização 2o Semestre � 2019 177 / 355
Reescrevendo as duas últimas restrições, temos:
maxD = 3y1 + 5y2
sujeito a
y1 + 2y2 ≤ 15
−2y1 − 4y2 ≤ 12
y1 ≥ 0
y2 ≤ 0 .
GSI027 Otimização 2o Semestre � 2019 178 / 355
Exercício
Veri�que, para o exemplo de maximização visto anteriormente, que asrestrições de não negatividade para y1, y2 e y3 são coerentes com oscoe�cientes das variáveis de folga do problema.
GSI027 Otimização 2o Semestre � 2019 179 / 355
Restrição do tipo igualdade (=) no primal: variável irrestrita no dual
Variáveis irrestritas: podem assumir qualquer valor real, mesmovalores negativos
maxZ = 5x1 + 12x2 + 4x3
sujeito a
x1 + 2x2 + x3 ≤ 10
2x1 − x2 + 3x3 = 8
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 .
GSI027 Otimização 2o Semestre � 2019 180 / 355
Na forma de equações:
maxZ = 5x1 +12x2 +4x3 +0x4
sujeito a
x1 + 2x2 + x3 + x4 = 10 (y1)
2x1 − x2 + 3x3 + 0x4 = 8 (y2)
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 .
Dual:
minD = 10y1 + 8y2
sujeito a
y1 + 2y2 ≥ 5
2y1 − y2 ≥ 12
y1 + 3y2 ≥ 4
y1 + 0y2 ≥ 0 .
Da última restrição, obtém-se y1 ≥ 0. Não há restrições sobre y2, portantoesta é irrestrita.
GSI027 Otimização 2o Semestre � 2019 181 / 355
Variável irrestrita no primal: restrição associada no dual é deigualdade (=).
maxZ = 5x1 + 6x2
sujeito a
x1 + 2x2 = 5
−x1 + 5x2 ≥ 3
4x1 + 7x2 ≤ 8
x1 irrestrita, x2 ≥ 0 .
GSI027 Otimização 2o Semestre � 2019 182 / 355
Uma situação não apresentada no modelo primal é a de variávelirrestrita.
Nesta situação, se xi é irrestrita, então de�nem-se duas variáveisnão-negativas, x−i e x+
i , cuja diferença entre ambas resulta nairrestrita:
xi = x−i − x+i
Sendo assim:I Se xi ≥ 0, então x−i ≥ x+
i ≥ 0;I Se xi < 0, então x+
i > x−i ≥ 0.
GSI027 Otimização 2o Semestre � 2019 183 / 355
Logo, na forma de equações:
maxZ = 5x−1 − 5x+1 + 6x2
sujeito a
x−1 − x+1 + 2x2 = 5 (y1)
− x−1 + x+1 + 5x2 − x3 = 3 (y2)
4x−1 − 4x+1 + 7x2 + x4 = 8 (y3)
x−1 ≥ 0, x+1 ≥ 0,
x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 .
Dual:
minD = 5y1 + 3y2 + 8y3
sujeito a
y1 − y2 + 4y3 ≥ 5
−y1 + y2 − 4y3 ≥ −52y1 + 5y2 + 7y3 ≥ 6
−y2 + 0y3 ≥ 0
0y2 + y3 ≥ 0
Das 2 primeiras restrições, obtém-se y1 − y2 + 4y3 = 5 � basta multiplicara segunda por −1.
GSI027 Otimização 2o Semestre � 2019 184 / 355
Reescrevendo:
minD = 5y1 + 3y2 + 8y3
sujeito a
y1 − y2 + 4y3 = 5
2y1 + 5y2 + 7y3 ≥ 6
y1 irrestrita, y2 ≤ 0, y3 ≥ 0 .
GSI027 Otimização 2o Semestre � 2019 185 / 355
Teoremas
Teorema I (Dualidade fraca)
Se ambos o primal e o dual possuem soluções viáveis, então Z ≤ D paraqualquer solução viável do primal de maximização e qualquer solução viáveldo dual de minimização.
Se o primal é de minimização, então o dual é de maximização e temosZ ≥ D.
Teorema II (Dualidade forte)
Se ambos o primal e dual possuírem soluções viáveis tais que Z = D, entãoas mesmas constituem soluções ótimas
GSI027 Otimização 2o Semestre � 2019 186 / 355
Exemplo: primal
maxZ = 5x1 + 2x2
sujeito a
x1 ≤ 3
x2 ≤ 4
x1 + 2x2 ≤ 9
x1 ≥ 0, x2 ≥ 0 .
Dual:
minD = 3y1 + 4y2 + 9y3
sujeito a
y1 + y3 ≥ 5
y2 + 2y3 ≥ 2
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0 .
Dadas duas soluções viáveis, (x1, x2) = (2, 3) para o primal e(y1, y2, y3) = (3, 3, 2) para o dual, temos
Z = 5(2) + 2(3) = 16
D = 3(3) + 4(3) + 9(2) = 39
GSI027 Otimização 2o Semestre � 2019 187 / 355
Temos, portanto Z ≤ D.
Considere agora o par de soluções viáveis (x1, x2) = (3, 3) para oprimal e (y1, y2, y3) = (4, 0, 1) para o dual:
Z = 5(3) + 2(3) = 21
D = 3(4) + 4(0) + 9(1) = 21 .
Como Z = D = 21, pode-se a�rmar que as duas soluções são ótimaspara o primal e dual.
GSI027 Otimização 2o Semestre � 2019 188 / 355
Teorema da folga complementar
Seja o problema primal representado pelo quadro inicial:x1 x2 . . . xn xn+1 xn+2 . . . xn+m b
L(0)0 Z −c1 −c2 . . . −cn 0 0 . . . 0 0
L(0)1 xn+1 a11 a12 . . . a1n 1 0 . . . 0 b1
L(0)2 xn+2 a21 a22 . . . a2n 0 1 . . . 0 b2...
......
. . . . . ....
......
. . . 0...
L(0)m xn+m am1 am2 . . . amn 0 0 . . . 1 bm
xj , j = 1, . . . , n: variáveis de decisão primais;xn+i , i = 1, . . . ,m: variáveis de folga do primal.
No caso do dual:yi , i = 1, . . . ,m: variáveis de decisão duais.ym+j , j = 1, . . . , n: variáveis de folga do dual.
GSI027 Otimização 2o Semestre � 2019 189 / 355
No quadro ótimo:x1 x2 . . . xn xn+1 xn+2 . . . xn+m b
L(p)0 Z c̄j = pj − cj c̄n+i = pn+i
O valor ótimo de yi do dual corresponde ao coe�ciente na linha L0ótima associado à variável de folga xn+i do primal:
y∗i = pn+i , i = 1, . . . ,m.
O valor ótimo da variável de folga dual ym+j corresponde aocoe�ciente na linha L0 ótima da variável xj do primal:
y∗m+j = pj − cj , j = 1, . . . , n.
GSI027 Otimização 2o Semestre � 2019 190 / 355
Uma vez que o dual do dual é o próprio problema primal, pode-sedeterminar a solução do primal a partir da solução do dual.
GSI027 Otimização 2o Semestre � 2019 191 / 355
Exercício I
1 Usando dualidade, determine a solução do problema
min f (x1, x2) = 65x1 + 30x2
sujeito a
2x1 + 3x2 ≥ 7
3x1 + 2x2 ≥ 9
x1 ≥ 1
x1 ≥ 0, x2 ≥ 0 .
GSI027 Otimização 2o Semestre � 2019 192 / 355
Referências
1 TAHA, H. Pesquisa operacional. 8a. ed. São Paulo: Prentice Hall,2008.
Os materiais de parte desta seção foram gentilmente cedidos por Paulo H.R. Gabriel (FACOM/UFU)Adaptações: Renato Pimentel, FACOM/UFU
GSI027 Otimização 2o Semestre � 2019 193 / 355
Sumário
6 Introdução a problemas de transporte
GSI027 Otimização 2o Semestre � 2019 194 / 355
Problemas de transporte, transbordo e designação
Dentro da PL, existem diversos modelos obtidos a partir de problemasreais
Com relação a problemas de logística, podemos destacar:I Problemas de transporte;I Problemas de transbordo;I Problemas de designação.
Referem-se, por exemplo, ao transporte ou distribuição demercadorias, dos centros de produção aos mercados consumidores;
Problemas de minimização do custo � impacto direto no lucro decada produto;
Limitações de oferta e demanda devem ser respeitadas � admite-seserem conhecidas.
GSI027 Otimização 2o Semestre � 2019 195 / 355
Sumário
7 Problema de transporte
GSI027 Otimização 2o Semestre � 2019 196 / 355
Formulação matemática do problema de transporte
m centros de produção (origens);
n centros consumidores (destinos);
1
2
m
1
2
n
a1
a2
am
b1
b2
bn
c11
cmn
......
......
GSI027 Otimização 2o Semestre � 2019 197 / 355
Componentes do modelo
ai : as quantidades disponíveis, ou ofertadas, em cada origem i
bj : as quantidades requeridas (demandadas) , em cadadestino j
cij : o custo unitário de transporte da origem i ao destino j
xij : a quantidade a ser transportada da origem i ao destino j
O que é transportado a partir de cada origem i para todos os destinosnão pode ultrapassar a quantidade disponível do produto na mesma:
n∑j=1
xij ≤ ai
Da mesma forma, espera-se que as demandas de cada destino sejamsatisfeitas:
m∑i=1
xij = bj
GSI027 Otimização 2o Semestre � 2019 198 / 355
O problema consiste em
minC (x11, x12, . . . , xmn) =m∑i=1
n∑j=1
cijxij (custo total)
sujeito às restrições
n∑j=1
xij ≤ ai i = 1, . . . , m
m∑i=1
xij = bj j = 1, . . . , n
xij ≤ 0 i = 1, . . . , m; j = 1, . . . , n
GSI027 Otimização 2o Semestre � 2019 199 / 355
Exemplo: construção de rodovia5
Na construção de uma rodovia, empregam-se jazidas de rochas paraobtenção de pedra britada.
É conveniente transportar este material de jazidas em pedreiraslocalizadas nas proximidades para alguns pontos preestabelecidos aolongo do caminho em que passará a estrada.
D1
D2
P1
D3
P4
P2
P3
Esquema param = 4 pedreiras en = 3 depósitos
5Adaptado de ARENALES (2006)GSI027 Otimização 2o Semestre � 2019 200 / 355
A tabela a seguir contém os dados do problema. Os custos edemandas são dados por tonelada de pedra britada.
DepósitosPedreiras 1 2 3 Oferta
1 30 13 21 4332 12 40 26 2153 27 15 35 7824 37 25 19 300
demanda 697 421 612
GSI027 Otimização 2o Semestre � 2019 201 / 355
Se xij é a quantidade (em toneladas) da pedreira i para o depósito j ,pode-se formular o problema como:
minC = 30x11 + 13x12 + 21x13 + 12x21 + 40x22 + 26x23+ 27x31 + 15x32 + 35x33 + 37x41 + 25x42 + 19x43
sujeito a
x11 + x12 + x13 ≤ 433
x21 + x22 + x23 ≤ 215
x31 + x32 + x33 ≤ 782
x41 + x42 + x43 ≤ 300
x11 + x21 + x31 + x41 = 697
x12 + x22 + x32 + x42 = 421
x13 + x23 + x33 + x43 = 612
x11 ≥ 0, x12 ≥ 0, . . . , x43 ≥ 0
GSI027 Otimização 2o Semestre � 2019 202 / 355
Distribuição para centros de consumo
Uma empresa fabrica um determinado produto em três cidades P1, P2
e P3; o produto destina-se a quatro centros de consumo C1 , C2, C3 eC4. O custo estimado de transportar o produto das fábricas para oscentros consumidores, assim como a demanda de cada centro e aoferta de cada fábrica é dado na tabela a seguir:
DestinoOrigem C1 C2 C3 C4 Oferta
P1 10 7 6 5 9P2 2 8 9 1 10P3 11 12 8 4 8
Demanda 7 6 10 4
Formule o modelo de transporte para se determinar o programa quetorna mínimo o custo total de transporte entre as quatro cidades e ostrês centros consumidores.
GSI027 Otimização 2o Semestre � 2019 203 / 355
Se xij ≥ 0 é a quantidade de produtos transportados da unidadei , i = 1, . . . , 3 para o centro j , j = 1, . . . , 4, obtém-se:
minC = 10x11 + 7x12 + 6x13 + 5x14 + 2x21 + 8x22+ 9x23 + x24 + 11x31 + 12x32 + 8x33 + 4x34
sujeito a
x11 + x12 + x13 + x14 ≤ 9
x21 + x22 + x23 + x24 ≤ 10
x31 + x32 + x33 + x34 ≤ 8
x11 + x21 + x31 = 7
x12 + x22 + x32 = 6
x13 + x23 + x33 = 10
x14 + x24 + x34 = 4
x11 ≥ 0, x12 ≥ 0, . . . , x34 ≥ 0
GSI027 Otimização 2o Semestre � 2019 204 / 355
Exercícios I
1 Uma rede de depósitos de material de construção tem 4 lojas quedevem ser abastecidas com 50 m3 (L1), 80 m3 (L2), 40 m3 (L3), 100m3 (L4) de areia grossa. Essa areia pode ser encarregada em 3 portosP1, P2 e P3, cujas distâncias às lojas estão no quadro (em km):
L1 L2 L3 L4P1 30 20 24 18P2 12 36 30 24P3 8 15 25 20
O caminhão pode transportar 10 m3 por viagem. Os portos tem areiapara suprir qualquer demanda.Estabelecer um plano de transporte que minimize a distância totalpercorrida entre os portos e as lojas e supra as necessidades das lojas.Construa o modelo linear do problema.
GSI027 Otimização 2o Semestre � 2019 205 / 355
Exercícios II
2 Um dado produto é produzido em diferentes fábricas do país comcapacidades de produção limitadas e deve ser levado a centros dedistribuição (depósitos) em regiões onde há demandas a seremsatisfeitas. O custo de transporte de cada fábrica a cada depósito éproporcional à quantidade transportada. A tabela a seguir fornece oscustos unitários de transporte de cada fábrica para cada depósito, bemcomo as demandas em cada depósito e as produções de cada fábrica.
Depósitos/Fábricas
FlorianópolisRio deJaneiro
Salvador Manaus Produções
Curitiba 1 0,8 3 4,5 470São Paulo 1,5 0,6 2,5 3 400Aracaju 6 5 1,2 2,8 400Demanda 350 300 300 120
Faça a modelagem do problema.
GSI027 Otimização 2o Semestre � 2019 206 / 355
Exercícios III
3 A MG Auto tem três fábricas: uma em Los Angeles, uma em Detroit eoutra em Nova Orleans, e duas grandes centrais de distribuição: umaem Denver e outra em Miami. As capacidades das três fábricas para opróximo trimestre são 1000, 1500 e 1200 carros. As demandastrimestrais nas duas centrais de distribuição são 2300 e 1400 carros. Omapa de distâncias entre as fábricas e as centrais de distribuição édado na tabela a seguir.
Distância Denver MiamiLos Angeles 1000 mi 2690 miDetroit 1250 mi 1350 mi
Nova Orleans 1275 mi 850 mi
A empresa encarregada do transporte cobra 8 centavos por milha porcarro. Formule o problema de transporte.
GSI027 Otimização 2o Semestre � 2019 207 / 355
Resolução de problemas de transporte
Os problemas de transporte vistos são casos particulares de problemasde programação linear
Como todo problema de PL, é possível a resolução algébrica viaalgoritmo simplex.
Entretanto, é possível aproveitar as particularidades do problema detransporte para resolvê-lo de forma mais e�ciente que o caso geraldo simplex.
GSI027 Otimização 2o Semestre � 2019 208 / 355
Equilíbrio entre oferta e demanda
Vamos considerar a priori que existe igualdade entre a oferta e ademanda, ou seja:
m∑i=1
ai =n∑
j=1
bj
Quando isso ocorre, dizemos que o problema está em equilíbrio;
Outros casos serão discutidos adiante.
GSI027 Otimização 2o Semestre � 2019 209 / 355
Exemplo
Vamos retomar um exemplo visto anteriormente � o de distribuiçãopara centros de consumo:
Uma empresa fabrica um determinado produto em três cidades P1, P2
e P3; o produto destina-se a quatro centros de consumo C1 , C2, C3 eC4. O custo estimado de transportar o produto das fábricas para oscentros consumidores, assim como a demanda de cada centro e aoferta de cada fábrica é dado na tabela a seguir:
DestinoOrigem C1 C2 C3 C4 Oferta
P1 10 7 6 5 9P2 2 8 9 1 10P3 11 12 8 4 8
Demanda 7 6 10 4
Note que a quantidade ofertada e a demandada são as mesmas (27),portanto o problema está em equilíbrio.
GSI027 Otimização 2o Semestre � 2019 210 / 355
O modelo é dado por:
minC = 10x11 + 7x12 + 6x13 + 5x14 + 2x21 + 8x22+ 9x23 + x24 + 11x31 + 12x32 + 8x33 + 4x34
sujeito ax11 + x12 + x13 + x14 = 9
x21 + x22 + x23 + x24 = 10
x31 + x32 + x33 + x34 = 8
x11 + x21 + x31 = 7
x12 + x22 + x32 = 6
x13 + x23 + x33 = 10
x14 + x24 + x34 = 4
x11 ≥ 0, x12 ≥ 0, . . . , x34 ≥ 0
Nas restrições de oferta, substituíram-se as desigualdades porigualdades � simpli�cação que reforça o conceito do equilíbrio.
GSI027 Otimização 2o Semestre � 2019 211 / 355
Quadro de soluções
O quadro de soluções de um problema de transporte é um esquemade representação do problema em forma de tabela, para a metodologiade resolução a ser usada.
Para um problema geral, é dado como
OrigemDestino
1 2 . . . n Oferta
1c11 c12 . . . c1n
a1
2c21 c22 . . . c2n
a2... . . . . . .
. . . . . ....
mcm1 cm2 . . . cmn
amDemanda b1 b2 . . . bn
GSI027 Otimização 2o Semestre � 2019 212 / 355
Voltando ao exemplo anterior, o quadro de soluções é dado por
OrigemDestino
1 2 3 4 Oferta
110 7 6 5
9
22 8 9 1
10
311 12 8 4
8Demanda 7 6 10 4
GSI027 Otimização 2o Semestre � 2019 213 / 355
Método stepping stone
Um método bastante usado na resolução de problemas de transporte éo chamado stepping stoneEsse método segue os mesmos passos do método simplex:
1 Encontre uma solução básica (factível) inicial;2 Veri�que se a solução é ótima;3 Se não for ótima, encontre uma nova solução, a partir da atual, e volte
ao passo anterior;4 Se for ótima, interrompa.
GSI027 Otimização 2o Semestre � 2019 214 / 355
Solução Inicial
Sabe-se que uma solução inicial deverá ser uma solução básica viáveldo sistema formado pelas restrições do modelo
Além disso:
TeoremaQualquer equação do sistema formado pelas restrições do modelo pode serobtida por uma combinação linear das demais, indicando que só existem(m + n − 1) equações independentes naquele sistema.
A consequência (corolário) desse teorema é que a base será formadapor (m + n − 1) variáveis básicas;
Existem diferentes critérios para encontrarmos a solução básica inicial.
GSI027 Otimização 2o Semestre � 2019 215 / 355
Serão vistas duas maneiras de encontrar a solução inicial:1 Regra do canto Noroeste2 Processo de custo mínimo
GSI027 Otimização 2o Semestre � 2019 216 / 355
Regra do canto Noroeste
A regra será aplicada ao quadro de soluções segundo os seguintes passos:1 Comece pela célula superior esquerda (ou seja, o �canto Noroeste�
do quadro), associado ao custo c11;2 Coloque nessa célula a maior quantidade permitida pela oferta
(linha) e demanda (coluna) correspondentes;3 Atualize os valores da oferta e da demanda que foram modicados pelo
passo (2);4 Siga para a célula à direita se houver alguma oferta restante e volte
ao passo (2); Caso contrário, siga para a célula inferior e volte aopasso (2).
GSI027 Otimização 2o Semestre � 2019 217 / 355
Regra do Canto Noroeste
Considere o quadro do exemplo anterior:
Origem
Destino1 2 3 4 Oferta
1
10 7 6 5
9
2
2 8 9 1
10
3
11 12 8 4
8
Demanda 7 6 10 4
Na célula (1, 1) (canto noroeste) atribuímos 7 unidades, que é aquantidade máxima de demanda do destino 1;
Assim, toda demanda do destino 1 foi atendida e ainda restaram 2unidades na origem 1.
Devemos, então, seguir para a célula (1, 2) e atribuir-lhe 2 unidades,que é o máximo valor que a origem 1 tem disponível.
GSI027 Otimização 2o Semestre � 2019 218 / 355
Regra do Canto Noroeste
O processo se repete até alcançarmos a célula inferior direita doquadro de soluções
Assim, encontraremos uma solução inicial factível
Origem
Destino1 2 3 4 Oferta
1
10
7→7
2↓6 5
�9 �2
2
2 8
4→9
6↓1
��10 �6
3
11 12 8
4→4
4 �8 �4Demanda �7 �6 �4 ��10 �4 �4
No caso, temos
x11 = 7, x12 = 2, x22 = 4, x23 = 6, x33 = 4, x34 = 4 e C = 218
GSI027 Otimização 2o Semestre � 2019 219 / 355
Observação
É importante observar 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 dosdestinos.
GSI027 Otimização 2o Semestre � 2019 220 / 355
Processo de 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 custosOs seguintes passos devem ser seguidos:
1 Localize no quadro o menor cij que não tenha oferta ou demanda nula2 Coloque na célula a maior quantidade permitida pela oferta e
demanda correspondente3 Atualize os valores da oferta e da demanda que foram modicadas pelo
passo (2) e volte ao passo (1).
O processo se repete até que sejam esgotadas as ofertas e suprimidasas demandas de todos os destinos
GSI027 Otimização 2o Semestre � 2019 221 / 355
Processo de Custo Mínimo
No exemplo, o menor cij que aparece é 1, na célula (2, 4).
Origem
Destino1 2 3 4 Oferta
1
10 7 6 5
9
2
2 8 9 1
10
3
11 12 8 4
8
Demanda 7 6 10 4
Logo, nesta célula, atribui-se a quantidade máxima de unidadespermitida, levando em conta a restrição de oferta e demanda;
Insere-se, assim, 4 unidades nesta célula, que é a demanda do destino4, e atualiza-se a oferta da origem 2 para 6 unidades uma vez que 4foram consumidas.
GSI027 Otimização 2o Semestre � 2019 222 / 355
Processo de Custo Mínimo
Eliminando o destino 4 do quadro, o menor custo é igual a 2 ecorresponde à célula (2, 1);
A esta célula, serão atribuídas 6 unidades, esgotando-se a oferta daorigem 2 e diminuindo a demanda do destino 1 para 1 unidade.
Este processo se repete até que todas as ofertas sejam consumidas etodas as demandas atendidas, quando então encontramos uma soluçãoinicial factível.
Origem
Destino1 2 3 4 Oferta
1
10 7 6
9
5
�9
2
2
6
8 9 1
4 ��10 �6
3
11
1
12
6
8
1
4
�8 �7 �1Demanda �7 �1 �6 ��10 �1 �4
GSI027 Otimização 2o Semestre � 2019 223 / 355
Origem
Destino1 2 3 4 Oferta
1
10 7 6
9
5
�9
2
2
6
8 9 1
4 ��10 �6
3
11
1
12
6
8
1
4
�8 �7 �1Demanda �7 �1 �6 ��10 �1 �4
No exemplo, a solução inicial obtida foi:
x13 = 9 x21 = 6 x24 = 4 x31 = 1 x32 = 6 x33 = 1
Nesse caso, o custo da solução inicial será C = 161
GSI027 Otimização 2o Semestre � 2019 224 / 355
Teste de otimalidade
Conhecida uma solução básica viável inicial, devemos obter a funçãoobjetivo somente em função das variáveis não básicas, para saber se apresente solução já é ótima.
Da mesma forma como é feito no método simplex, caso a soluçãoainda não seja ótima devemos determinar a variável que entra e a quesai da base.
GSI027 Otimização 2o Semestre � 2019 225 / 355
Método u − v
É necessário eliminar as variáveis básicas da função objetivo e, paraisso, devemos somar a ela múltiplos das restrições do modelo.
Sejam u1, u2, . . . , um os valores que irão multiplicar as equações deoferta, antes de somá-las à função objetivo;
Sejam v1, v2, . . . , vn os múltiplos análogos para cada restrição dedemanda:
GSI027 Otimização 2o Semestre � 2019 226 / 355
minZ −m∑i=1
n∑j=1
cijxij = 0
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, i = 1, . . . , m, j = 1, . . . , nGSI027 Otimização 2o Semestre � 2019 227 / 355
Conhecida uma solução viável básica, devemos ter:
cij − ui − vj = 0
para cada uma das (m + n − 1) variáveis básicas, de modo aeliminá-las da função objetivo.
Uma vez que o número de variáveis básicas é igual a (m + n − 1)vamos ter (m + n − 1) equações desse tipo;
Uma vez que o número de incógnitas ui e vj é (m + n), temos(m + n − 1) equações, podemos atribuir um valor arbitrário a umadessas variáveis sem violar as equações.
GSI027 Otimização 2o Semestre � 2019 228 / 355
Como exemplo, considere o quadro de soluções do método do customínimo.
Temos as seguintes equações, para as 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
GSI027 Otimização 2o Semestre � 2019 229 / 355
Atribuindo um valor arbitrário a u1, descobrimos os demais valores deui e vj .
Por exemplo, para u1 = 0, temos:
v1 = 9 v2 = 10 v3 = 6 v4 = 8
u1 = 0 u2 = −7 u3 = 2
GSI027 Otimização 2o Semestre � 2019 230 / 355
A partir dos valores de ui e vj , calcularemos os coe�cientes dasvariáveis não-básicas da função objetivo.
Ou seja:xij : cij − ui − vj .
Para este exemplo, temos:
x11 : 10− 0− 9 = 1
x12 : 7− 0− 10 = −3x14 : 5− 0− 8 = −3x22 : 8 + 7− 10 = 5
x23 : 9 + 7− 6 = 10
x34 : 4− 2− 8 = −6
GSI027 Otimização 2o Semestre � 2019 231 / 355
Uma solução viável básica é ótima se, e somente se, cij − ui − vj ≥ 0para todo i , j tal que xij seja uma variável não básica.
Sendo assim, como as variáveis x12, x14 e x34 apresentaramcoe�cientes negativos a solução ainda não é ótima.
GSI027 Otimização 2o Semestre � 2019 232 / 355
Construindo uma Nova Solução Factível
Uma vez aplicado o Método u − v , podemos dizer se uma soluçãobásica é ótima ou não;
Caso não seja ótima, iniciamos a busca por uma nova solução.Como acontece com o método simplex tradicional devemos:
1 Determinar a variável que entra na base2 Determinar variável que sai da base3 Identi�car a nova solução factível
GSI027 Otimização 2o Semestre � 2019 233 / 355
Passo 1: Encontrar a variável que entra na base
Considerando apenas as variáveis não básicas, devemos escolheraquelas tais que
cij − ui − vj < 0
.
No exemplo, escolhemos x12, x14 e x34;
Garantimos, assim, que o custo total seja reduzido.
Seguindo esse raciocínio, dentre as candidatas, escolhemos a demenor valor, ou seja, x34, cujo coe�ciente é −6.
GSI027 Otimização 2o Semestre � 2019 234 / 355
Passo 2: Encontrar a variável que sai da base
O aumento do valor da variável que entra na base dispara uma reaçãoem cadeia para compensar mudanças nas demais variáveis básicas, demodo 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 quedeixa a base.
Suponha que a variável x34 entrará na base com um valor θ ≥ 0, quedeve ser o maior possível.
GSI027 Otimização 2o Semestre � 2019 235 / 355
Passo 2 (continuação)
Estabelecemos, então, um valor θ para variável x34, o que signi�cadiminuir x24 na mesma quantidade para restabelecer a demanda iguala 4 (coluna 4)
Essa mudança requer, então, aumentar x21 na mesma quantidade paracontinuar obedecendo a oferta (linha 2)
Mais uma vez, tal mudança requer diminuir a variável x31 na mesmaquantidade para restabelecer a demanda 7 (coluna 1)
Esse decrescimento também restabelece a oferta da origem 3 igual 8(linha 3)
GSI027 Otimização 2o Semestre � 2019 236 / 355
Origem
Destino1 2 3 4 Oferta
1
10 7 6
9
5
9
2
2
6 + θ8 9 1
4− θ 10
3
11
1− θ12
6
8
1
4
θ 8
Demanda 7 6 10 4
GSI027 Otimização 2o Semestre � 2019 237 / 355
Passo 2 (continuação)
Devemos, agora, determinar o maior valor permitido a θ, isto é, ovalor de θ que gera a variável básica que se anula mais rapidamente.
Do quadro anterior, temos:
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 seanular.
GSI027 Otimização 2o Semestre � 2019 238 / 355
Passo 3: Encontrar a nova solução básicaA nova solução viável básica é identi�cada adicionando-se o valor de θno último quadro.
O valor da variável que sai é x31 = 1, e o quadro �cará:
Origem
Destino1 2 3 4 Oferta
1
10 7 6
9
5
9
2
2
7
8 9 1
3 10
3
11
0
12
6
8
1
4
1 8
Demanda 7 6 10 4
E o custo dessa solução será: C = 155
GSI027 Otimização 2o Semestre � 2019 239 / 355
Precisamos, agora, saber se a nova solução é ótima.
Para isso, calculamos novamente os valores de ui e vj :
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, temos:
u1 = −2 u2 = −3
v4 = 4 v1 = 5 v3 = 8 v2 = 12
GSI027 Otimização 2o Semestre � 2019 240 / 355
Em seguida, encontramos o valor de cada coe�ciente das variáveis nãobásicas (cij − ui − vj):
x11 : 10 + 2− 5 = 7
x12 : 7 + 2− 12 = −3x14 : 5 + 2− 4 = 3
x22 : 8 + 3− 12 = −1x23 : 9 + 3− 8 = 4
x31 : 11− 0− 5 = 6
Como há coe�cientes negativos, a solução não é ótima e a variávelque deve entrar na base é x12 por apresentar o menor coe�cientenegativo (−3)
GSI027 Otimização 2o Semestre � 2019 241 / 355
Finalmente, calculamos o valor de θ:
Origem
Destino1 2 3 4 Oferta
1
10 7
θ6
9− θ5
9
2
2
7
8 9 1
3 10
3
11 12
6− θ8
1 + θ4
1 8
Demanda 7 6 10 4
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 quedeve deixar a base é x32
GSI027 Otimização 2o Semestre � 2019 242 / 355
O valor da variável que sai é x31 = 1 o quadro �cará:
Origem
Destino1 2 3 4 Oferta
1
10 7
6
6
3
5
9
2
2
7
8 9 1
3 10
3
11 12
0
8
7
4
1 8
Demanda 7 6 10 4
GSI027 Otimização 2o Semestre � 2019 243 / 355
Ao �nal desse passo, calculamos novamente os valores de ui e vj :
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
Para u1 = 0, temos:
v2 = 7 u3 = 2 u2 = −1
v1 = 1 v3 = 6 v4 = 2
GSI027 Otimização 2o Semestre � 2019 244 / 355
E os valores dos coe�cientes:
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á coe�ciente negativo a solução é ótima:
x12 = 6 x13 = 3 x21 = 7 x24 = 3 x33 = 7 x34 = 1
C = 137
GSI027 Otimização 2o Semestre � 2019 245 / 355
Problemas desbalanceados
Para a resolução de problemas desbalanceados usando o stepping-stone:
Oferta maior que a demanda (∑
i ai >∑
j bj):Introduzir um destino fantasma (também chamado sentinela oudummy) cujos custos unitários de transporte sejam todos zero,independente da origem; e com demanda igual à diferença entre ototal ofertado e o total demandado.
Demanda maior que oferta (∑
i ai <∑
j bj):Introduzir uma fonte de oferta fantasma (fonte dummy), comcustos unitários zero para todos os destinos, e com oferta igual àdiferença entre o total demandado e o total ofertado.
GSI027 Otimização 2o Semestre � 2019 246 / 355
Exercícios I
1 Busque a solução do problema 3 de transporte anteriormente (MGAuto).
2 Considere que um produto é fabricado em 3 unidades F1, F2, F3,sendo posteriormente estocado em 4 depósitos D1, D2, D3 e D4. Ascapacidades fabris são a1 = 40, a2 = 80 e a3 = 110, respectivamentepara F1, F2 e F3. Nos depósitos devem se atender as demandas:b1 = 20, b2 = 30, b3 = 100 e b4 = 80, respectivamente, para D1, D2,D3 e D4.Os custos unitários de transportes são dados na tabela:
D1 D2 D3 D4
F1 10 5 12 4F2 2 0 1 9F3 13 11 14 6
GSI027 Otimização 2o Semestre � 2019 247 / 355
Exercícios II
Faça a modelagem do problema, e em seguida, usando o métodostepping-stone.
3 Determine a solução do exemplo da construção da rodovia vistoanteriormente, substituindo as desigualdades por igualdades nasrestrições de oferta.
4 Resolva o exercício 2 de modelagem visto anteriormente, recorrendoaos pontos dummy apropriados.
GSI027 Otimização 2o Semestre � 2019 248 / 355
Referências
1 ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H.Pesquisa operacional: para cursos de engenharia. Rio de Janeiro:Elsevier Brasil, 2006.
2 LACHTERMACHER, G. Pesquisa operacional na tomada de decisões,2a. ed. Rio de Janeiro: Elsevier, 2004.
3 MARINS, F. A. S. Introdução à pesquisa operacional. São Paulo:Cultura Acadêmica, 2011.
4 NOGUEIRA, F. Pesquisa Operacional, UFJF.5 TAHA, H. Pesquisa operacional. 8a. ed. São Paulo: Prentice Hall,
2008.
Os materiais de parte desta seção foram gentilmente cedidos por Paulo H.R. Gabriel (FACOM/UFU). Material desenvolvido com base no trabalho daProfa. Alane A. Silva (UFPE).Adaptações: Renato Pimentel, FACOM/UFU
GSI027 Otimização 2o Semestre � 2019 249 / 355
Sumário
8 Problema de transbordo
GSI027 Otimização 2o Semestre � 2019 250 / 355
Introdução
Em determinadas situações, podem-se usar localidadesintermediárias entre a origem e o destino dos produtos a seremtransportados
I Tais localidades são denominadas de transbordo;I Podem representar, por exemplo, depósitos ou centros de distribuição
regionais;I Problemas de transporte contendo estes pontos intermediários são
chamados de problemas de transbordo.
GSI027 Otimização 2o Semestre � 2019 251 / 355
Modelagem
Em problemas de transbordo, consideram-se alguns aspectos:
O que é transportado das unidades intermediárias (de transbordo) aosmercados consumidores não deve ultrapassar a quantidade de produtoque chega a tais pontos;Transportar além do necessário pode ser mais caro do que transportarsomente o necessário.
I A quantidade transportada de cada unidade de transbordo aosmercados consumidores deve ser igual a que chega à mesma doscentros de produção. Logo, deve-se adicionar o modelo de transporteuma restrição ∑
i
xij =∑k
xjk
para cada unidade de transbordo j .
GSI027 Otimização 2o Semestre � 2019 252 / 355
1
2
j
3
4
5
x1j + x2j = xj3 + xj4 + xj5 .
GSI027 Otimização 2o Semestre � 2019 253 / 355
Exemplo
(ARENALES, 2006) Considere uma empresa de bebidas com 2 centrosde produção (Araraquara e S. José dos Campos, com um suprimentode 800 e 1 000 unidades, respectivamente) e 3 mercados consumidoresprincipais � S. Paulo, Belo Horizonte e R. de Janeiro, com demandasrespectivas de 500, 400 e 900 unidades.
A empresa dispõe de 2 depósitos para abastecer tais mercados,localizados em Campinas e Barra Mansa. Suponha que os mercadossejam abastecidos somente a partir de tais depósitos.Os custos unitários de transporte de cada centro de produção paracada depósito, e de cada depósito para cada mercado consumidor édado pelas tabelas que seguem.
GSI027 Otimização 2o Semestre � 2019 254 / 355
Custos unitários de transporte de centros de produção aos depósitos
Centros de suprimentoDepósitos
Campinas (3) Barra Mansa (4)Araraquara (1) 1 3
S. José dos Campos (2) 1 2
Custos unitários dos depósitos aos mercados consumidores
DepósitosMercados consumidores
São Paulo (5) B. Horizonte (6) R. Janeiro (7)Campinas (3) 1 3 3
Barra Mansa (4) 3 4 1
GSI027 Otimização 2o Semestre � 2019 255 / 355
Sendo xij a quantidade transportada do ponto i ao ponto j :
min f (x13, . . . , x47) = x13 + 3x14 + x23 + 2x24+ x35 + 3x36 + 3x37 + 3x45 + 4x46 + x47
sujeito a
x13 + x14 ≤ 800
x23 + x24 ≤ 1000
x35 + x45 = 500
x36 + x46 = 400
x37 + x47 = 900
x13 + x23 = x35 + x36 + x37
x14 + x24 = x45 + x46 + x47
x13 ≥ 0, x14 ≥ 0, . . . , x47 ≥ 0 .
GSI027 Otimização 2o Semestre � 2019 256 / 355
Referências
1 ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H.Pesquisa operacional: para cursos de engenharia. Rio de Janeiro:Elsevier Brasil, 2006.
Os materiais de parte desta seção foram gentilmente cedidos por Paulo H.R. Gabriel (FACOM/UFU). Material desenvolvido com base no trabalho daProfa. Alane A. Silva (UFPE).Adaptações: Renato Pimentel, FACOM/UFU
GSI027 Otimização 2o Semestre � 2019 257 / 355
Sumário
9 Problema de designação
GSI027 Otimização 2o Semestre � 2019 258 / 355
Introdução
Um caso especial do modelo de transportes é aquele em que cadaorigem tem uma unidade disponível e cada destino requer, também,uma unidade.Por exemplo:
I Escalar vendedores para pontos de venda;I Distribuir atividades entre membros de uma equipe;I Alocar máquinas para resolver diferentes tarefas.
GSI027 Otimização 2o Semestre � 2019 259 / 355
Modelagem
Exemplo
Deseja-se designar quatro operários para quatro tarefas, de maneira que onúmero total de homens-hora seja mínimo. Cada homem desempenha cadatarefa em um determinado número de horas, conforme indicam os dados damatriz de custos a seguir:
Operário 1 Operário 2 Operário 3 Operário 4Tarefa 1 10 12 15 16Tarefa 2 14 12 13 18Tarefa 3 10 16 19 15Tarefa 4 14 12 13 15
GSI027 Otimização 2o Semestre � 2019 260 / 355
Diferente dos problemas de transporte tradicionais, temos apenas 1 naorigem e 1 no destino.
Assim, pelas arestas (�caminhos�) devemos apenas transferir umaou nenhuma �carga�.
Logo, nossa variável de decisão pode assumir apenas dois valores: 0ou 1.
De�nimos, então:
xij =
{1, se a tarefa i for atribuída ao operário j ;
0, caso contrário.
GSI027 Otimização 2o Semestre � 2019 261 / 355
Assim, o modelo de designação pode ser escrito da seguinte maneira:
Função Objetivo
minC =m∑i=1
n∑j=i
cijxij
Restriçõesn∑
j=1
xij = 1, i = 1, 2, . . . ,m
m∑i=1
xij = 1, j = 1, 2, . . . , n
xij ∈ {0, 1}
GSI027 Otimização 2o Semestre � 2019 262 / 355
Retornando ao exemplo (m = 4 tarefas para n = 4 operários):
minC = 10x11 + 12x12 + 15x13 + 16x14 + 14x21 + 12x22 + 13x23 + 18x24+
10x31 + 16x32 + 19x33 + 15x34 + 14x41 + 12x42 + 13x43 + 15x44
sujeito a:
x11 + x12 + x13 + x14 = 1
x21 + x22 + x23 + x24 = 1
x31 + x32 + x33 + x34 = 1
x41 + x42 + x43 + x44 = 1
x11 + x21 + x31 + x41 = 1
x12 + x22 + x32 + x42 = 1
x13 + x23 + x33 + x43 = 1
x14 + x24 + x34 + x44 = 1
xij ∈ {0, 1}
GSI027 Otimização 2o Semestre � 2019 263 / 355
Algoritmo de Designação
Devido às suas particularidades, a resolução do problema dedesignação torna-se complexa por meio do método simplex.De fato, não temos mais variáveis de decisão contínuas, mas discretas
I Somente valores inteiros válidos, mais especi�camente, somente 0 ou
1.
No entanto, existe um método bastante e�ciente (baseado no métodostepping stone) para resolução do problema.
Esse método é chamado método húngaro.Antes de aplicá-lo, porém, devemos veri�car se o modelo estáequilibrado.
I No modelo de designação, o número de origens deve ser igual aonúmero de destinos � Matriz quadrada;
I Caso isso não ocorra, devemos construir origens ou destinos auxiliares,com custo de transferência zero.
GSI027 Otimização 2o Semestre � 2019 264 / 355
Passos do Método Húngaro
1 Subtrair de cada linha seu menor valor; em seguida fazer o mesmocom as colunas; cada linha e cada coluna deverá, então, apresentarpelo menos um elemento nulo (zero).
2 Designar origens para destinos nas células em que aparece o elementonulo; dar preferência às linhas ou colunas que tenham apenas umzero disponível; cada designação efetuada invalida os outros zeros nalinha e na coluna da célula designada; se a designação se completa, oproblema está resolvido.
3 Se não estiver resolvido, devemos:1 Cobrir os zeros da tabela com o menor número de traços � horizontais
e verticais � possível;2 Subtrair o menor valor dentre os números não cobertos, de todos os
elementos da tabela;3 Retornar ao item (2).
GSI027 Otimização 2o Semestre � 2019 265 / 355
Exemplo
Para a matriz de custos do exemplo anterior:10 12 15 1614 12 13 1810 16 19 1514 12 13 15
Subtraindo o menor elemento das linhas (respectivamente:10, 12, 10, 12):
0 2 5 62 0 1 60 6 9 52 0 1 3
GSI027 Otimização 2o Semestre � 2019 266 / 355
Subtraindo o menor elemento das colunas (respectivamente: 0, 0, 1, 3):0 2 4 32 0 0 30 6 8 22 0 0 0
Designando nos zeros de linhas ou colunas (de preferência, linhas oucolunas com apenas um zero) e anulando os outros zeros:
0 2 4 32 0 X 3X 6 8 22 X X 0
Não encontramos uma solução ótima, pois a terceira linha nãoapresenta uma designação válida.
GSI027 Otimização 2o Semestre � 2019 267 / 355
Cobrimos, então, os zeros, usando o menor número possível de traços.| 2 4 3| − − −| 6 8 2| − − −
A matriz resultante dessa eliminação é:(
2 4 36 8 2
)cujo menor valor é 2
Subtraímos 2 de toda matriz resultante:(0 2 14 6 0
)
GSI027 Otimização 2o Semestre � 2019 268 / 355
E �recolocamos� essa matriz na original:0 0 2 12 0 0 30 4 6 02 0 0 0
(note que os valores que havíamos eliminado não são modi�cados)
Finalmente, designando novamente nos zeros de linhas ou colunas (depreferência, linhas ou colunas com apenas um zero) e anulando osoutros zeros:
0 X 2 12 0 X 3X 4 6 02 X 0 X
GSI027 Otimização 2o Semestre � 2019 269 / 355
Como resultado, temos: x11 = 1, x22 = 1, x34 = 1, x43 = 1, ou seja:I Tarefa 1 é atribuída ao Operário 1I Tarefa 2 é atribuída ao Operário 2I Tarefa 3 é atribuída ao Operário 4I Tarefa 4 é atribuída ao Operário 3
Os demais valores de xij são nulos
GSI027 Otimização 2o Semestre � 2019 270 / 355
Exercícios I
1 (TAHA, 2008) Os três �lhos de Joe Klyne � John, Karen e Terri �querem ganhar algum dinheiro para gastar durante uma excursão daescola. O Sr. Klyne escolheu três tarefas para seus �lhos: 1) cortargrama; 2) pintar a porta da garagem; e 3) lavar os carros da família.Para evitar concorrência entre os �lhos, ele pediu que cada umapresentasse propostas fechadas do que fosse considerado umpagamento justo para realizar cada uma das tarefas. Ficou combinadoque os três concordariam com a decisão do pai sobre quem executariaqual tarefa. A tabela a seguir resume as propostas recebidas, em $:
Cortar Pintar LavarJohn 15 10 9Karen 9 15 10Terri 10 12 8
Como o Sr. Klyne deve designar as tarefas?
GSI027 Otimização 2o Semestre � 2019 271 / 355
Exercícios II
2 Um treinador precisa formar um time de nadadoras para competir emuma prova olímpica de 400 metros medley. As nadadoras apresentamas seguintes médias de tempo (em segundos) em provas individuais de100 metros, em cada estilo:
Livre Peito Borboleta CostasFlor 54 54 51 53Gabriela 51 57 52 52Teresa 50 53 54 56Tieta 56 54 55 53
Modele esse problema e resolva-o pelo método húngaro.
GSI027 Otimização 2o Semestre � 2019 272 / 355
Referências
1 TAHA, H. Pesquisa operacional. 8a. ed. São Paulo: Prentice Hall,2008.
Os materiais desta seção foram gentilmente cedidos por Paulo H. R.Gabriel (FACOM/UFU). Material desenvolvido com base no trabalho daProfa. Alane A. Silva (UFPE).Adaptações: Renato Pimentel, FACOM/UFU
GSI027 Otimização 2o Semestre � 2019 273 / 355
Sumário
10 Introdução a problemas em redes
GSI027 Otimização 2o Semestre � 2019 274 / 355
Aplicações tradicionais
Problemas de otimização em redes incluem algumas aplicações comuns,como (TAHA, 2008):
Encontrar o modo mais e�ciente de interconectar localidades direta ouindiretamente;
Determinar a rota ou caminho mais curto entre duas localizações;
Determinar o �uxo máximo permitido em uma rede, de modo asatisfazer requisitos de oferta e demanda em diferentes locais;
Programar atividades de um projeto.
GSI027 Otimização 2o Semestre � 2019 275 / 355
Algumas de�nições I
1 Um grafo ou rede é um conjunto de nós ou vértices conectados ounão por arestas (também chamadas arcos ou ramos), querepresentam alguma forma de relacionamento entre os mesmos.
I As arestas podem conter um peso (valor numérico) associado,representando uma grandeza associado ao relacionamento dos 2 nósque interliga (ex.: a distância entre os nós).
Notação: (N,A), onde N é o conjunto de nós e A é o conjunto dearestas.
GSI027 Otimização 2o Semestre � 2019 276 / 355
Algumas de�nições II
Exemplo: N = {1, 2, 3, 4, 5},A = {(1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 5)}
1
2
3
4
5
GSI027 Otimização 2o Semestre � 2019 277 / 355
Algumas de�nições III
2 Todo grafo possui um �uxo associado às suas arestas. A aresta édirigida ou orientada se permitir o deslocamento somente numadireção. Ex.: no grafo visto existe �uxo do nó 1 para o nó 2, mas nãovice-versa. A rede é dirigida (dígrafo) se todas as suas arestas foremdirigidas.
3 Caminho: sequência de arestas distintas que ligam 2 nós quaisquerda rede. Um caminho forma um ciclo ou loop se conectar um nó a simesmo, passando por outros nós. Ex.: (2, 3), (3, 4) e (4, 2) formamum ciclo.
4 Rede conectada: rede onde todos os pares de nós são conectadospor um caminho (como no exemplo visto).
GSI027 Otimização 2o Semestre � 2019 278 / 355
Exemplo clássico
Pontes de Königsberg, Prússia
Visitar todas as quatro partes A, B, C e D da cidade (atual Kaliningrado,na Rússia), voltando ao ponto de partida e passando apenas uma vez porcada uma das sete pontes (a a g) sobre o Rio Prególia.
GSI027 Otimização 2o Semestre � 2019 279 / 355
Leonhard Euler (séc. XVIII): não há solução possível.
Representação do problema como uma rede:
A
B
C
D
Nós são as partes de terra e arestas representam as pontes.
Para qualquer nó, não é possível encontrar um ciclo que passe portodos os outros nós sem passar mais de uma vez por uma mesmaaresta.
GSI027 Otimização 2o Semestre � 2019 280 / 355
Sumário
11 Problema do menor caminho
GSI027 Otimização 2o Semestre � 2019 281 / 355
Problema do menor caminho
Um dos problemas mais comuns em grafos: determinar o menorcaminho (ou o de menor custo) entre 2 nós.
Problema bastante comum em aplicações práticas.
GSI027 Otimização 2o Semestre � 2019 282 / 355
Exemplos
Entrega de uma mercadoria do depósito de uma fábrica até o endereçode um cliente : Qual o menor caminho a percorrer?Pode ser modelado como problema de otimização em redes.
I Nós correspondem às esquinas das ruas � esquinas interligadas porarestas.
I 2 nós para o depósito (A) e o endereço do cliente (B).I Qualquer caminho interligando A e B é um caminho real pela cidade.I Se o peso de cada aresta corresponder a distância entre esquinas, o
comprimento do caminho é a soma dos pesos das arestas entre A eB.
GSI027 Otimização 2o Semestre � 2019 283 / 355
(ARENALES, 2006) Vendedor se desloca de São Paulo a Fortalezapara levar produtos a um cliente importante.
Ao longo do caminho, visitará outros clientes.
Se a rede for tal que os nós correspondam às junções das principaisrodovias � e as arestas, portanto, os trechos de rodovia entre dois nós� é possível de�nir o peso de cada aresta como sendo o custo líquidoesperado no trecho.
Custo líquido: custo das despesas rodoviárias (combustível, pedágios,manutenção) menos a comissão esperada no respectivo trecho.
Algumas arestas podem ter valor negativo, indicando lucro ao invés decusto.
O vendedor deve escolher a rota correspondente ao �menor caminho�(menor custo líquido possível) entre os nós correspondentes às duascidades.
GSI027 Otimização 2o Semestre � 2019 284 / 355
Outras situações podem ser representadas pelo problema do menorcaminho.
GSI027 Otimização 2o Semestre � 2019 285 / 355
(TAHA, 2008): A RentCar está desenvolvendo uma política dereposição para sua frota de carros considerando uma projeção deplanejamento de 4 anos.Ao início de cada ano, é tomada uma decisão sobre a conservação emoperação ou a reposição de um carro.
Um carro deve permanecer em serviço por no mínimo um ano e nomáximo três anos.
A tabela a seguir dá o custo de reposição em função do ano que ocarro foi adquirido e do número de anos em operação.
Adquirido no anoCusto de reposição por anos em operação1 2 3
1 4 000 5 400 9 8002 4 300 6 200 8 7003 4 800 7 100 −4 4 900 − −
GSI027 Otimização 2o Semestre � 2019 286 / 355
O problema pode ser formulado como um grafo onde os nós 1 a 5representam os anos 1 a 5. As arestas a partir do nó 1 podem chegarsomente aos nós 2, 3 e 4 porque o carro pode operar entre 1 e 3 anos,e assim por diante. O peso de cada aresta corresponde ao custo dereposição.
Solução: caminho mais curto entre os nós 1 e 5.
5
5 400
4 000 4 300 4 800 4 900
7 100
6 200
9 800
8 700
42 31
Menor caminho: 1→ 3→ 5.
GSI027 Otimização 2o Semestre � 2019 287 / 355
Formulação matemática
Problema de encontrar o caminho mais curto entre o nó 1 e o nó n6
de um grafo G = (N,A), onde N = {1, 2, . . . , n}: caso de problemade transbordo, com única origem no nó 1, e único destino o nó n.Demais: todos de transbordo.
6Sem perda de generalidade, formulação pode ser estendida para o problema demenor caminho entre dois nós quaisquer.
GSI027 Otimização 2o Semestre � 2019 288 / 355
Se a cada aresta entre i e j temos um custo (peso) associado cij ,deseja-se
minC =n∑
i=1
∑j∈S(i)
cijxij
sujeito a
∑j∈S(1)
x1j = 1,
∑j∈P(n)
xin = 1,
∑i∈P(j)
xij =∑
k∈S(j)
xjk j = 2, . . . , n − 1
xij ∈ {0, 1}, i = 1, . . . , n, j = 1, . . . , n
I S(j), P(j) são, respectivamente, o conjunto dos sucessores epredecessores de um nó j .
GSI027 Otimização 2o Semestre � 2019 289 / 355
xij = 1 indica que a aresta de i a j faz parte do menor caminho entre1 e n;
xij = 0 indica que a mesma não faz parte.
A 1a. restrição está relacionada ao nó de origem 1, indicando que omenor caminho passará por um único sucessor.
A 2a. restrição está relacionada ao nó de destino n, indicando que nomenor caminho encontrado passará por apenas um de seusantecessores.
As demais n − 2 restrições � dos nós intermediários � indica que nomenor caminho apenas uma aresta chegará e uma aresta sairá de cadaum dos mesmos (os dois somatórios se igualam a 1).
GSI027 Otimização 2o Semestre � 2019 290 / 355
Retornando ao exemplo anterior (da reposição de carros):
5
5 400
4 000 4 300 4 800 4 900
7 100
6 200
9 800
8 700
42 31
minC = 4 000 x12 + 5 400 x13 + · · ·+ 4 900 x45
sujeito a
x12 + x13 + x14 = 1
x25 + x35 + x45 = 1
x12 = x23 + x24 + x25
x13 + x23 = x34 + x35
x14 + x24 + x34 = x45
xij ∈ {0, 1}, i = 1, . . . , n, j = 1, . . . , n
GSI027 Otimização 2o Semestre � 2019 291 / 355
Na solução ótima (menor caminho):
x13 = x35 = 1,
x12 = x23 = x24 = · · · = x45 = 0,
C = 5 400 + 7 100 = 12 500
GSI027 Otimização 2o Semestre � 2019 292 / 355
Num problema pequeno (grafo com poucos nós/poucas arestas), omenor caminho pode ser obtido rapidamente.
Entretanto, muitos problemas envolvem um grande número depossibilidadesO caminho é a implementação de algoritmos para resolução doproblema, tais como:
1 Algoritmo de Dijkstra;2 Algoritmo de Floyd.
GSI027 Otimização 2o Semestre � 2019 293 / 355
Algoritmo de Dijkstra
Caminho mais curto entre um nó de origem especí�co e qualqueroutro nó.Um rótulo é associado a cada nó j , contendo duas informações:
1 O menor custo já encontrado, a partir do nó de origem;2 Qual o predecessor de j , neste caminho.
Assim, se ui é a menor distância (ou custo) entre o nó de origem 1 e onó i , e de�nindo-se cij ≤ 0 como o comprimento da aresta (i , j), entãoé de�nido um rótulo de um nó imediatamente posterior, j :
[uj , i ] = [ui + cij , i ], cij ≥ 0 .
I O rótulo do nó inicial é [0,−], já que este não possui nenhumpredecessor.
I Os rótulos podem ser temporários � podem ser modi�cados, sepossível achar rota melhor � e permanentes.
GSI027 Otimização 2o Semestre � 2019 294 / 355
Passo a passo (TAHA, 2008)
1 Iteração 0: Rotule o nó de origem (nó 1) com o rótulo � permanente� [0,−]. Determine i = 1.
2 Iteração i :1 Calcule os rótulos temporários [ui + cij , i ] para cada nó j sucessor i ,
contanto que j não tenha rótulo permanente:
AtualizaçãoCaso j já esteja rotulado com [uj , k] � i.é., passando por outro nó k � atualiza-se
o rótulo, substituindo [uj , k] por [ui + cij , i ] quando ui + cij < uj .
2 Se todos os rótulos forem permanentes, pare.Caso contrário, selecione rótulo [ur , s] cuja distância ur é a menordentre todos os temporários (empates resolvidos arbitrariamente).Sinalize o mesmo como permanente, de�na i = r e repita a iteração i .
GSI027 Otimização 2o Semestre � 2019 295 / 355
Exemplo
Determine os caminhos mais curtos entre a cidade 1 e as demais:
1
2
3
4
5
100
30
20
15
10
60
50
Iteração 0: Rótulo permanente [0,−] para o nó 1.
Iteração 1: Nós 2 e 3 podem ser alcançados pelo nó 1 (últimorotulado permanentemente):
Nó Rótulo Condição1 [0,−] Permanente2 [0 + 100, 1] = [100, 1] Temporário3 [0 + 30, 1] = [30, 1] Temporário
GSI027 Otimização 2o Semestre � 2019 296 / 355
Da tabela anterior, o nó 3 resulta na menor distância (u3 = 30). Logo,seu rótulo se torna permanente.
Iteração 2: 4 e 5 podem ser alcançados com base no nó 3:
Nó Rótulo Condição1 [0,−] Permanente2 [0 + 100, 1] = [100, 1] Temporário3 [30, 1] Permanente4 [30 + 10, 3] = [40, 3] Temporário5 [30 + 60, 3] = [90, 3] Temporário
A condição do do rótulo [40, 3] do nó 4 é alterada para permanente.
GSI027 Otimização 2o Semestre � 2019 297 / 355
Iteração 3: 2 e 5 podem ser alcançados com base no nó 4:
Nó Rótulo Condição1 [0,−] Permanente2 [40 + 15, 4] = [55, 4] Temporário3 [30, 1] Permanente4 [40, 3] Permanente5 [90, 3] ou [40 + 50, 4] = [90, 4] Temporário
O rótulo temporário do nó 2 foi alterado, pois se encontrou umcaminho mais curto do nó 1 para o mesmo.
O nó 5 possui dois rótulos alternativos, indicando a mesma distância,u5 = 90.
A condição do do rótulo [55, 4] do nó 2 é alterada para permanente.
GSI027 Otimização 2o Semestre � 2019 298 / 355
Iteração 4: há somente uma aresta a partir do nó 2, para o nó 3.Contudo, este já possui rótulo permanente.
A lista permanece inalterada em relação à da iteração 3, mas agorarótulo do nó 2 passa a ser permanente.Único nó com rótulo temporário: 5.
I Como não há arestas partindo do nó 5, seu rótulo se torna permanente,e o algoritmo se encerra.
GSI027 Otimização 2o Semestre � 2019 299 / 355
O caminho mais curto entre o nó 1 e qualquer outro nó da rede édeterminado começando do nó de destino desejado e percorrendo arota inversa, usando a informação dos rótulos permanentes.
1
2
3
4
5
100
30
20
15
10
60
50
�����[100, 1](1)
[55, 4](3)
[0,−](1)
( ) = iteração
[30, 1](1)
[40, 3](2)
[90, 3](2)
[90, 4](3)
Por exemplo, o menor caminho do nó 1 ao nó 2:
2©→ [55, 4]→ 4©→ [40, 3]→ 3©→ [30, 1]→ 1©
Ou seja, 1→ 3→ 4→ 2, com distância 55.
GSI027 Otimização 2o Semestre � 2019 300 / 355
Exercício I
(TAHA, 2008) Use o algoritmo de Dijkstra para determinar o caminho maiscurto entre:
1 1 e 8;2 1 e 6;3 2 e 6.
1
2
3
4
5
6
7
8
2
1
1
1
2
22
3
3
4
5
56
67
8
GSI027 Otimização 2o Semestre � 2019 301 / 355
Algoritmo de Floyd
Também chamado de Floyd-WarshallMais geral que Dijkstra:
I Determina o caminho mínimo entre quaisquer dois nós do grafo.
Representação do grafo de n nós: matriz de distâncias n × n.I Inicialmente, entrada (i , j) dá o peso cij da aresta entre i e j , caso
exista; ou ∞ caso contrário.
GSI027 Otimização 2o Semestre � 2019 302 / 355
Operação tripla de Floyd
Base do algoritmo de Floyd
Dados 3 vértices i , j e k como na �gura abaixo, sempre que
wik + wkj < wij ,
otimiza-se a distância entre i e j pela troca da rota direta i → j pori → k → j .
i
k
j
wik
wij
wkj
GSI027 Otimização 2o Semestre � 2019 303 / 355
Algoritmo
Etapa 0: De�ne-se a matriz de distâncias inicial, D0, onde:
d(0)ij =
{wij , se j é sucessor de i ;
∞, caso contrário
De�ne-se também a matriz de sequência de nós S0:
S0 =
− 2 . . . j . . . n
1 − . . . j . . . n...
......
......
...
1 2... j
... −
I Ou seja, s(0)
ij =
{j , i 6= j ;
não de�nido, i = j.
GSI027 Otimização 2o Semestre � 2019 304 / 355
Etapa geral k (k = 1, . . . , n): Atualização da matriz de distâncias,de Dk−1 para Dk .
1 De�nem-se a linha k e a coluna k como linha pivô e coluna pivô.2 Aplica-se a operação tripla para todo i e j , testando-se a condição
d(k−1)ik + d
(k−1)kj < d
(k−1)ij , i 6= j , i 6= k, j 6= k.
Caso a condição seja satisfeita:F Em Dk : d
(k)ij = d
(k−1)ik + d
(k−1)kj .
F Em Sk : s(k)ij = k.
GSI027 Otimização 2o Semestre � 2019 305 / 355
Resultado
Após n etapas, pode-se determinar o menor caminho entre os nós i e jcom base nas matrizes Dn e Sn:
1 A partir de Dn, dij dá a menor distância entre i e j2 A partir de Sn, determine o nó intermediário k = sij , que dá como
resultado a rota i → k → j :F Se sik = k e skj = j , pare (todos os nós intermediários foram
encontrados);F Senão, repita o procedimento entre os nós i e k e entre os nós k e j .
GSI027 Otimização 2o Semestre � 2019 306 / 355
Exemplo
Encontrar os caminhos mais curtos entre quaisquer dois nós do grafo:
3
2 4
5
3
10
5
615
41
Todas as arestas, com exceção de uma, permitem �uxo em ambos ossentidos. Somente não há ligação direta do nó 5 para o nó 3.
GSI027 Otimização 2o Semestre � 2019 307 / 355
Iteração 0: matrizes D0 e S0.
D0 =
− 3 10 ∞ ∞3 − ∞ 5 ∞10 ∞ − 6 15∞ 5 6 − 4∞ ∞ ∞ 4 −
S0 =
− 2 3 4 51 − 3 4 51 2 − 4 51 2 3 − 51 2 3 4 −
GSI027 Otimização 2o Semestre � 2019 308 / 355
Iteração 1: k = 1⇒ Linha pivô 1 e coluna pivô 1 (sombreadas emD0).Nas operações triplas, os únicos elementos atualizados são d23 e d32(destacados em D0 e S0):
1 Substitui-se d(1)23
= d(0)21
+ d(0)13
= 3 + 10 = 13. Logo, s(1)23
= 1.2 Substitui-se d
(1)32
= d(0)31
+ d(0)12
= 10 + 3 = 13. Logo, s(1)32
= 1.
Logo:
D1 =
− 3 10 ∞ ∞3 − 13 5 ∞10 13 − 6 15∞ 5 6 − 4∞ ∞ ∞ 4 −
S1 =
− 2 3 4 51 − 1 4 51 1 − 4 51 2 3 − 51 2 3 4 −
GSI027 Otimização 2o Semestre � 2019 309 / 355
Iteração 2: k = 2⇒ Linha pivô 2 e coluna pivô 2 (sombreadas emD1).Nas operações triplas, os únicos elementos atualizados são d14 e d41(destacados em D1 e S1). Logo, de forma análoga à iteração anterior,obtém-se:
D2 =
− 3 10 8 ∞3 − 13 5 ∞10 13 − 6 158 5 6 − 4∞ ∞ ∞ 4 −
S2 =
− 2 3 2 51 − 1 4 51 1 − 4 52 2 3 − 51 2 3 4 −
GSI027 Otimização 2o Semestre � 2019 310 / 355
Iteração 3: k = 3. Atualizando-se os itens em destaque nas matrizesD2 e S2, obtém-se D3 e S3:
D3 =
− 3 10 8 253 − 13 5 2810 13 − 6 158 5 6 − 4∞ ∞ ∞ 4 −
S3 =
− 2 3 2 31 − 1 4 31 1 − 4 52 2 3 − 51 2 3 4 −
GSI027 Otimização 2o Semestre � 2019 311 / 355
Iteração 4: k = 4. Atualizando-se os itens em destaque nas matrizesD3 e S3, obtém-se D4 e S4:
D4 =
− 3 10 8 123 − 11 5 910 11 − 6 108 5 6 − 412 9 10 4 −
S4 =
− 2 3 2 41 − 4 4 41 4 − 4 42 2 3 − 54 4 4 4 −
Iteração 5: k = 5 (linhas e coluna em destaque em D4). Porém,nenhuma melhoria é adicional.
GSI027 Otimização 2o Semestre � 2019 312 / 355
Mesmo que modi�cações fossem necessárias para k = 5, esta seria aúltima iteração, pois o grafo possui 5 nós.
As matrizes D4 e S4 contêm tudo que precisamos para determinar ocaminho ótimo entre 2 nós quaisquer do grafo.
Exemplo: nó 1 ao nó 5:I De D4: custo ótimo 12 � menor distância, dada por d (4)
15.
I De S4: Qual a rota? (a rota mais curta só é direta se s(4)ij = j)
1 Como s(4)15 = 4 6= 5, a rota inicialmente é dada como 1→ 4→ 5.
2 Como s(4)14 = 2 6= 4, o segmento (1, 4) não é uma conexão direta entre
1 e 4, e a rota agora se torna 1→ 2→ 4→ 5.3 Como s
(4)12 = 2, s
(4)24 = 4 e s
(4)45 = 5, nenhum desmembramento é
desnecessário e portanto 1→ 2→ 4→ 5 é o caminho ótimo.
GSI027 Otimização 2o Semestre � 2019 313 / 355
Exercícios I
1 (TAHA, 2008) Use o algoritmo de Floyd para determinar, a partir doexemplo anterior, as distâncias mais curtas:
1 Do nó 5 ao nó 1;2 Do nó 3 ao nó 5;3 Do nó 5 ao nó 3;4 Do nó 5 ao nó 2;
2 (TAHA, 2008) A empresa de telefonia Tell-All atende seis áreas. Asdistâncias via satélite estão no grafo abaixo. Quais as rotas maise�cientes que devem ser estabelecidas entre quaisquer duas áreas?
3
2
4
6700
200
200
5
300700
600300
100
500
400
1
GSI027 Otimização 2o Semestre � 2019 314 / 355
Referências
1 ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H.Pesquisa operacional: para cursos de engenharia. Rio de Janeiro:Elsevier Brasil, 2006.
2 TAHA, H. Pesquisa operacional. 8a. ed. São Paulo: Prentice Hall,2008.
GSI027 Otimização 2o Semestre � 2019 315 / 355
Sumário
12 Problema do �uxo máximo
GSI027 Otimização 2o Semestre � 2019 316 / 355
Problema do �uxo máximo
Outro problema bastante comum que pode ser modelado por grafos;
Deseja-se determinar o maior �uxo possível que pode ser enviado deum nó a outro do grafo.
Única origem e único destino.
GSI027 Otimização 2o Semestre � 2019 317 / 355
Exemplos
Qual a capacidade máxima de produção de um determinado bempor uma empresa?
I Roteiros distintos durante o processoI Diferentes centros de fabricação, cada qual com uma certa capacidade
instalada.
Redes de tubulações. Exemplo, de petróleo:Qual a capacidademáxima da rede entre poços e re�narias?
I Produto bruto (petróleo cru) transportado de poços para re�narias.I Estações intermediárias de impulsores e de bombeamento instaladasI Cada segmento tem uma taxa de descarga máxima de �uxo.I Segmento pode ser unidirecional ou bidirecional, dependendo do
projeto.
GSI027 Otimização 2o Semestre � 2019 318 / 355
(TAHA, 2008) Uma rede típica para o problema do escoamento dopetróleo é dada pelo grafo abaixo:
2
1
3
4
5
6
9
7
8Origem Destino
Poços Impulsores Re�narias
Representação: a solução do problema exige o acréscimo de umaorigem única e um destino único, usando as arestas unidirecionais decapacidade in�nita tracejadas no grafo.
GSI027 Otimização 2o Semestre � 2019 319 / 355
Representação do �uxo
Dada uma aresta (i , j), com i < j , pode-se usar a notação
(C̄ij , C̄ji )
para representar as respectivas capacidades de �uxo nas direções i → je j → i .
Para eliminar ambiguidades, pode-se representar tais capacidades numgrafo, colocando-seC̄ij próximo ao nó i eC̄ij próximo ao nó j , como na �gura abaixo.
i j
C̄ij C̄ji
GSI027 Otimização 2o Semestre � 2019 320 / 355
Cortes
CorteConjunto de arestas que, se eliminado do grafo, causa um rompimentototal do �uxo entre o nó de origem e o nó de destino.
A capacidade do corte corresponde à soma das capacidades de suasarestas;O corte com menor capacidade determina o �uxo máximo da rede.
I Devem ser considerados todos os cortes possíveis.
GSI027 Otimização 2o Semestre � 2019 321 / 355
Exemplo
Considere o grafo que segue:
1
2 3
4
5
1030
20
3040
000 10
20
205
0
000
corte 1corte 2
corte 3
Capacidades dos cortes representados:Corte Arestas associadas Capacidade
1 (1, 2), (1, 3), (1, 4) 20+ 30+ 10 = 60
2 (1, 3), (1, 4), (2, 3), (2, 5) 30+ 10+ 40+ 30 = 110
3 (2, 5), (3, 5), (4, 5) 30+ 20+ 20 = 70
GSI027 Otimização 2o Semestre � 2019 322 / 355
Pelos cortes ilustrados, conclui-se que o �uxo máximo da rede nãopode exceder 60 unidades.
Para determinar o �uxo máximo, entretanto, todos os cortes precisamser encontrados.
GSI027 Otimização 2o Semestre � 2019 323 / 355
Exercício
Encontre no grafo anterior 2 cortes adicionais, e determine sua capacidade.
GSI027 Otimização 2o Semestre � 2019 324 / 355
Formulação matemática
Seja o problema de se determinar o �uxo máximo entre o nó 1 e o nón de um grafo G (N,A) com n nós.
I Sem perda de generalidade, pois a interpretação se estende paraquaisquer dois nós em questão.
GSI027 Otimização 2o Semestre � 2019 325 / 355
(ARENALES, 2006) Seja y a quantidade a ser enviada de 1 para n.Se xij é a quantidade de �uxo da aresta (i , j), então deseja-se
max y
sujeito a
∑j∈S(1)
x1j −∑
k∈P(1)
xk1 = y , nó fonte 1
∑j∈S(i)
xij =∑
k∈P(i)
xki , i = 2, . . . , n − 1
∑j∈S(n)
xnj −∑
k∈P(n)
xkn = −y , nó destino n
0 ≤ xij ≤ C̄ij , ∀(i , j) ∈ E .
I S(i) e P(i) são o conjunto dos sucessores e predecessores do nó i .
GSI027 Otimização 2o Semestre � 2019 326 / 355
Isto é, deseja-se determinar xij para toda (i , j) ∈ E que maximize o�uxo entre origem e destino.
Reescrevendo-se as restrições técnicas, com as variáveis do ladoesquerdo:
∑j∈S(1)
x1j −∑
k∈P(1)
xk1 − y = 0,
∑j∈S(i)
xij −∑
k∈P(i)
xki = 0, i = 2, . . . , n − 1
∑j∈S(n)
xnj −∑
k∈P(n)
xkn + y = 0,
GSI027 Otimização 2o Semestre � 2019 327 / 355
Aresta de retorno
Das restrições anteriores, podemos associar a coluna correspondente àvariável y a uma nova aresta (n, 1), chamada aresta de retorno.
A aresta de retorno (n, 1) tem �uxo C̄n1 = y (com C̄1n = 0) e 1,portanto, passa a ser sucessor de n, ∴ S(n) = S(n) + {1}. Da mesmaforma, P(1) = P(1) + {n}, e podemos reescrever o problema como
max xn1
sujeito a
∑j∈S(i)
xij −∑
k∈P(i)
xki = 0, i = 1, . . . , n
0 ≤ xij ≤ C̄ij , ∀(i , j) ∈ E .
GSI027 Otimização 2o Semestre � 2019 328 / 355
Exemplo
Representando a aresta de retorno no grafo visto anteriormente, temos:
1
2 3
4
5
1030
20
3040
000 10
20
205
0
000
0
C̄51
GSI027 Otimização 2o Semestre � 2019 329 / 355
Modelagem do problema de �uxo máximo:
max x51
sujeito a
x12 + x13 + x14 − x51 = 0
x23 + x25 − x12 = 0
x34 + x35 − x13 − x23 = 0
x43 + x45 − x14 − x34 = 0
x51 − x25 − x35 − x45 = 0
0 ≤ x12 ≤ 20
0 ≤ x13 ≤ 30
0 ≤ x14 ≤ 10
0 ≤ x23 ≤ 40
0 ≤ x25 ≤ 30
0 ≤ x34 ≤ 10
0 ≤ x35 ≤ 20
0 ≤ x43 ≤ 5
0 ≤ x45 ≤ 20
0 ≤ x51 ≤ C̄51
GSI027 Otimização 2o Semestre � 2019 330 / 355
Formulação alternativa
TAHA (2008) propõe uma formulação mais simples, dispensando aideia da aresta de retorno.Basta considerar o problema de maximização de uma das duasfunções objetivo:
1 z1 =∑
j∈S(1) x1j (maximização da saída do nó de origem), ou2 z2 =
∑k∈P(n) xkn (maximização de entrada no nó de destino).
Em ambos os casos, somente as restrições dos nós intermediários sãoconsideradas.
As duas funções objetivo acima são equivalentes.As duas formulações (com e sem aresta de retorno) são equivalentes:
I No exemplo visto, basta isolar x51 na restrição do nó de origem (ou nóde destino), e na função objetivo.
GSI027 Otimização 2o Semestre � 2019 331 / 355
Por exemplo, considerando-se o problema de maximizar a saída do nó 1:
max x12 + x13 + x14
sujeito a
x23 + x25 − x12 = 0
x34 + x35 − x13 − x23 = 0
x43 + x45 − x14 − x34 = 0
0 ≤ x12 ≤ 20
0 ≤ x13 ≤ 30
0 ≤ x14 ≤ 10
0 ≤ x23 ≤ 40
0 ≤ x25 ≤ 30
0 ≤ x34 ≤ 10
0 ≤ x35 ≤ 20
0 ≤ x43 ≤ 5
0 ≤ x45 ≤ 20
GSI027 Otimização 2o Semestre � 2019 332 / 355
Algoritmo de �uxo máximo
(TAHA, 2008) Encontrar rotas de passagem com �uxo líquidopositivo entre nós de origem e destino
Cada caminho compromete parte ou toda a capacidade das suasarestas ao �uxo do grafo.Por exemplo, numa aresta (i , j) com capacidade inicial (C̄ij , C̄ji ) (amáxima), quando parte desta capacidade é usada numa rota deescoamento, temos uma capacidade residual (cij , cji ).
I À medida que as arestas são reutilizadas, os valores cij , cji sãoatualizados.
Rótulos: quando um nó j recebe um �uxo aj de algum nó i ∈ P(j),de�nimos um rótulo ao mesmo,
[aj , i ],
de modo similar ao visto no algoritmo de Dijkstra.
GSI027 Otimização 2o Semestre � 2019 333 / 355
Etapas (do nó 1 ao nó n)
Etapa 1 : Para cada aresta (i , j), iguale à capacidade residual à inicial:
(cij , cji ) = (C̄ij , C̄ji )
Rotule o nó de origem com o rótulo [∞,−]. Determine i = 1e passe para a etapa seguinte.
GSI027 Otimização 2o Semestre � 2019 334 / 355
Etapa 2 : seja S̄(i) o conjunto dos sucessores do nó i ainda nãorotulados, ligados a ele por arestas com capacidades residuaisnão nulas (ainda podem ser usadas).
Se há pelo menos um nó em S(i) nesta situação(S̄(i) 6= ∅), passe à etapa 3.Caso contrário, passe à etapa 4.
GSI027 Otimização 2o Semestre � 2019 335 / 355
Etapa 3 : Determine k ∈ S̄(i) tal que:
cik = maxj∈S̄(i)
{cij} .
Ou seja, qual dos sucessores permite a passagem com maior �uxo possível.Determine ak = cik e rotule o nó k com [ak , i ].
Se k = n, o nó destino foi rotulado, portanto uma rota de passagemfoi obtida. Siga para a etapa 5.
Caso contrário, faça i = k e retorne à etapa 2.
GSI027 Otimização 2o Semestre � 2019 336 / 355
Etapa 4 : (Percorrer a rota inversa).
Se i = 1, nenhuma rota de passagem é possível: prossigapara etapa 6.Caso contrário, seja r ∈ P(i) o nó rotuladoimediatamente antes do nó i . Elimine itemporariamente dos nós adjacentes a r , determinei = r e volte à etapa 2.
GSI027 Otimização 2o Semestre � 2019 337 / 355
Etapa 5 : (Capacidades residuais).De�na os nós da p-ésima rota de passagem do nó origem 1ao nó destino n como Np = (1, k1, k2, . . . , n).O �uxo máximo ao longo da rota é dado por
fp = min{a1, ak1, ak2, . . . , an}
A capacidade residual de cada aresta ao longo da rota éreduzida de fp da direção do �uxo e aumentada de fp nadireção contrária:
(cij − fp, cji + fp) se o �uxo for de i para j ;(cij + fp, cji − fp) caso contrário.
Restaure quaisquer nós eliminados na etapa 4. Determinei = 1 e volte à etapa 2 para tentar uma nova rota depassagem.
GSI027 Otimização 2o Semestre � 2019 338 / 355
Etapa 6 : (Solução).1 Se m rotas de passagem são encontradas, o �uxo
máximo da rede é dado por
F = f1 + f2 + · · ·+ fm
2 Para toda aresta (i , j) ∈ E , dadas as capacidades iniciais(C̄ij , C̄ji ) e �nais (cij , cji ), o �uxo ótimo é dado por:
xij =
{C̄ij − cij , se C̄ij > cij ;
C̄ji − cji , se C̄ji > cji .
(os dois casos não ocorrem simultaneamente).
GSI027 Otimização 2o Semestre � 2019 339 / 355
Ajuste da etapa 5
Explicado pelo exemplo que segue:
1
2
3
4
Rota: 1→ 2→ 3→ 4f1 = 5(a)
5[∞,−]
0
[5, 1]
[5, 2]
[5, 3]
5
55
0 0 05
1
2
3
4
Rota: 1→ 3→ 2→ 4f2 = 5(b)
0[∞,−]
5
[5, 3]
[5, 1]
[5, 2]
5
05
0 5 50
0 01
2
3
4
Nenhuma rotade passagem
(c)
0
5
0
50
5 0 50
5
I Na rede (a), �uxo máximo é 5, e as arestas que de�nem a rota têm seu�uxo alterado de (5, 0) para (0, 5).
I O mesmo vale para a rota em (b), e, após as alterações, não há maisrota possível.
GSI027 Otimização 2o Semestre � 2019 340 / 355
1
2
3
4
Rota: 1→ 2→ 3→ 4f1 = 5(a)
5[∞,−]
0
[5, 1]
[5, 2]
[5, 3]
5
55
0 0 05
1
2
3
4
Rota: 1→ 3→ 2→ 4f2 = 5(b)
0[∞,−]
5
[5, 3]
[5, 1]
[5, 2]
5
05
0 5 50
0 01
2
3
4
Nenhuma rotade passagem
(c)
0
5
0
50
5 0 50
5
O que houve de (b) para (c) foi o cancelamento de um �uxoanteriormente comprometido na direção 2→ 3.
O algoritmo �lembra� que este �uxo foi previamente usado poisaumentamos a capacidade na direção inversa de 0 para 5 (pela etapa5).
GSI027 Otimização 2o Semestre � 2019 341 / 355
Exemplo
Considere a rede de 5 nós vista previamente, no exemplo dos cortes:
1
2 3
4
5
10
3020
30
40
0
0
010
20
205
0
00
0
Determinar o �uxo máximo da rede.
GSI027 Otimização 2o Semestre � 2019 342 / 355
Iteração 1
Inicialmente, iguale as capacidades residuais iniciais às capacidadesiniciais (C̄ij , C̄ji ) de cada aresta.Este passo somente é feito antes da iteração 1 (primeira rota).
Etapa 1 : Determine a1 =∞, e rotule nó 1 com [∞,−]. Determinei = 1.
Etapa 2 : S̄(1) = {2, 3, 4} 6= ∅. Passar para etapa 3.
Etapa 3 : k = 3, pois c13 = max{c12, c13, c14} = 30.Determine a3 = c13 = 30 e rotule o nó 3 com [30, 1].Determine i = 3 e volte à etapa 2.
Etapa 2 : S̄(3) = {4, 5} 6= ∅. Passar para etapa 3.
Etapa 3 : k = 5 e a5 = c35 = max{10, 20} = 20.Rotule o nó 5 com [20, 3].Uma rota de passagem foi obtida. Passe para a etapa 5.
GSI027 Otimização 2o Semestre � 2019 343 / 355
Etapa 5 : Rota determinada pelo caminho inverso a partir do nó dedestino 5:
5©→ [20, 3]→ 3©→ [30, 1]→ 1©
Logo, N1 = {1, 3, 5} e f1 = min{a1, a3, a5} = 20.As capacidades residuais das arestas utilizadas na rotaN1 são
(c13, c31) = (30− 20, 0 + 20) = (10, 20)
(c35, c53) = (20− 20, 0 + 20) = (0, 20)
GSI027 Otimização 2o Semestre � 2019 344 / 355
Rota encontrada na iteração 1 (capacidades residuais ainda não ilustradas).
1
2 3
4
5
10
3020
30
40
0
0
010
20
205
0
00
0
f1 = 20[∞,−]
[30, 1]
[20, 3]
GSI027 Otimização 2o Semestre � 2019 345 / 355
Iteração 2
Etapa 1 : Determine a1 =∞, e rotule nó 1 com [∞,−]. Determinei = 1.
Etapa 2 : S̄(1) = {2, 3, 4}.Etapa 3 : k = 2 e a2 = max{20, 10, 10} = 20.
Rotule o nó 2 com [20, 1] e repita a etapa 2, com i = 2.
Etapa 2 : S̄(2) = {3, 5}.Etapa 3 : k = 3 e a3 = c23 = 40.
Rotule o nó 3 com [40, 2] e repita a etapa 2, com i = 3.
Etapa 2 : S̄(3) = {4} (pois c35 = 0).
Etapa 3 : k = 4 e a4 = c34 = 10.Rotule o nó 4 com [10, 3] e repita a etapa 2, com i = 4.
Etapa 2 : S̄(4) = {5} (pois nós 1 e 3 já foram rotulados).
Etapa 3 : Temos k = 5 e rótulo [20, 4]. Nova rota: passe à etapa 5.
GSI027 Otimização 2o Semestre � 2019 346 / 355
Etapa 5 : Rota N2 = {1, 2, 3, 4, 5} ef2 = min{∞, 20, 40, 10, 20} = 10.As capacidades residuais das arestas utilizadas na rota N2 são
(c12, c21) = (20− 10, 0 + 10) = (10, 10)
(c23, c32) = (40− 10, 0 + 10) = (30, 10)
(c34, c43) = (10− 10, 5 + 10) = (0, 15)
(c45, c54) = (20− 10, 0 + 10) = (10, 10)
GSI027 Otimização 2o Semestre � 2019 347 / 355
Rota encontrada na iteração 2 (capacidades residuais ainda não ilustradas).
1
2 3
4
5
10
1020
30
40
0
0
2010
0
205
0
00
20
f2 = 10[∞,−]
[20, 1]
[20, 4]
[40, 2]
[10, 3]
GSI027 Otimização 2o Semestre � 2019 348 / 355
Iteração 3
Etapa 1 : nó 1: a1 =∞, [∞,−]. Determine i = 1.
Etapa 2 : S̄(1) = {2, 3, 4}.Etapa 3 : k = 2 e a2 = c12 = max{10, 10, 10} = 10.
Rotule o nó 2 com [10, 1] e repita a etapa 2, com i = 2.
Etapa 2 : S̄(2) = {3, 5}.Etapa 3 : k = 3 e a3 = c23 = 30.
Rotule o nó 3 com [30, 2] e repita a etapa 2, com i = 3.
Etapa 2 : S̄(3) = ∅ (pois c34 = c35 = 0). Vá para a etapa 4.
Etapa 4 : Rota inversa � [30, 2] indica o antecessor r = 2.Elimine o nó 3 desta iteração, determine i = r = 2 e volte àetapa 2.
Etapa 2 : S̄(2) = {5} (pois nó 3 foi temporariamente eliminado).
Etapa 3 : Temos k = 5 e rótulo [30, 2]. Nova rota: passe à etapa 5.
GSI027 Otimização 2o Semestre � 2019 349 / 355
Etapa 5 : Rota N3 = {1, 2, 5} ef3 = min{∞, 10, 30} = 10.As capacidades residuais das arestas utilizadas na rota N3 são
(c12, c21) = (10− 10, 10 + 10) = (0, 20)
(c25, c52) = (30− 10, 0 + 10) = (20, 10)
GSI027 Otimização 2o Semestre � 2019 350 / 355
Rota encontrada na iteração 3 (capacidades residuais ainda não ilustradas).
1
2 3
4
5
10
1010
30
30
10
10
200
0
1015
0
100
20
f3 = 10[∞,−]
[10, 1]
[30, 2]
���XXX[30, 2]
GSI027 Otimização 2o Semestre � 2019 351 / 355
Iterações 4 a 6
ExercícioEncontre as rotas N4 e N5 (ambas com �uxo 10)a.
aNó 3 está novamente à disposição para as rotas N4 e N5
Iteração 6: Todas as arestas partindo do nó 1 têm residual 0.Portanto, todas as rotas possíveis foram encontradas. Passa-se à Etapa 6
GSI027 Otimização 2o Semestre � 2019 352 / 355
Etapa 6: Solução do problema
Fluxo máximo da rede:
F = f1 + f2 + · · ·+ f5 = 20 + 10 + 10 + 10 + 10 = 60
Fluxos xij nas arestas: consideram-se as capacidades residuais iniciais eas �nais (cij , cji ) encontradas na etapa 5 das iterações:
Aresta (C̄ij , C̄ji )− (cij , cji ) Fluxo Direção(1, 2) (20, 10)− (0, 20) = (20,−20) 20 1→ 2(1, 3) (30, 0)− (0, 30) = (30,−30) 30 1→ 3(1, 4) (10, 0)− (0, 10) = (10,−10) 10 1→ 4(2, 3) (40, 0)− (40, 0) = (0, 0) 0 −(2, 5) (30, 0)− (10, 20) = (20,−20) 20 2→ 5(3, 4) (10, 5)− (0, 15) = (10,−10) 10 3→ 4(3, 5) (20, 0)− (0, 20) = (20,−20) 20 3→ 5(4, 5) (20, 0)− (0, 20) = (20,−20) 20 4→ 5
GSI027 Otimização 2o Semestre � 2019 353 / 355
Exercícios I
1 Determine a capacidade excedente de todas as arestas do exemplo,após a solução do problema.
2 Determine qual o �uxo máximo, para a rede exempli�cada,considerando-se agora como origem o nó 2 e destino o nó 4.
GSI027 Otimização 2o Semestre � 2019 354 / 355
Referências
1 ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H.Pesquisa operacional: para cursos de engenharia. Rio de Janeiro:Elsevier Brasil, 2006.
2 TAHA, H. Pesquisa operacional. 8a. ed. São Paulo: Prentice Hall,2008.
GSI027 Otimização 2o Semestre � 2019 355 / 355
Recommended