Embed Size (px)
Citation preview
GSI027 � Otimização
Prof. Renato Pimentel
2oSemestre � 2019
Sumário
1 Pesquisa Operacional e Tomada de Decisões 51.1 De�nição e Origens da Pesquisa Operacional . . . . . . . . . . . 61.2 Fases de Resolução de Problemas . . . . . . . . . . . . . . . . . . 71.3 Principais Áreas da Pesquisa Operacional . . . . . . . . . . . . . 10
I Programação Linear 12
2 Introdução à programação linear 122.1 De�nições e exemplos . . . . . . . . . . . . . . . . . . . . . . . . 132.2 Problemas clássicos . . . . . . . . . . . . . . . . . . . . . . . . . . 172.3 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Solução grá�ca 223.1 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4 O método simplex 344.1 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
II Dualidade 51
5 Dual e sua relação com o primal 515.1 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
III Problemas de transporte 58
6 Introdução a problemas de transporte 58
7 Problema de transporte 587.1 Modelagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587.2 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617.3 Resolução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
1
7.4 Problemas desbalanceados . . . . . . . . . . . . . . . . . . . . . . 747.5 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
8 Problema de transbordo 768.1 Modelagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
9 Problema de designação 789.1 Modelagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 789.2 Resolução algébrica . . . . . . . . . . . . . . . . . . . . . . . . . . 799.3 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
IV Otimização em redes 83
10 Introdução a problemas em redes 83
11 Problema do menor caminho 8511.1 Formulação matemática . . . . . . . . . . . . . . . . . . . . . . . 8711.2 Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . 8811.3 Exercício . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9111.4 Algoritmo de Floyd . . . . . . . . . . . . . . . . . . . . . . . . . . 9211.5 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
12 Problema do �uxo máximo 9612.1 Formulação matemática . . . . . . . . . . . . . . . . . . . . . . . 9812.2 Algoritmo de �uxo máximo . . . . . . . . . . . . . . . . . . . . . 10112.3 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
Apresentação
Objetivos e Ementa
Objetivo
• Ao término da disciplina, o aluno deve estar apto a corretamente aplicaros métodos, técnicas e ferramentas da pesquisa operacional na modelageme solução de problemas relacionados a sistemas de informação.
Ementa do curso
• Fundamentos da Pesquisa Operacional
• Modelagem
• Programação linear, método simplex, dualidade.
• Otimização em Redes, problemas de transporte.
2
Bibliogra�a
Bibliogra�a básica
• TAHA, Hamdy. Pesquisa operacional. 8a. ed. São Paulo: Prentice Hall,2008.
• LACHTERMACHER, Gerson. Pesquisa operacional na tomada de deci-sõ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: ElsevierBrasil, 2006.
• Recomendação: MARINS, Fernando Augusto Silva. Introdução à pesquisaoperacional. São Paulo: Cultura Acadêmica, 2011.
Disponível gratuitamente (mediante cadastro) em: http://www.culturaacademica.com.br/catalogo/introducao-a-pesquisa-operacional
Conteúdo previsto1
1. Introdução à Pesquisa Operacional: Origem / principais aplicações.
2. Programação Linear (PL):
• Características gerais e modelagem de um problema de PL;
• Problemas típicos;
• Resolução grá�ca;
• Método simplex.
3. Dualidade:
• O modelo dual de um PL;
• Analogia entre as soluções primal e dual.
4. Problema de transporte:
• Algoritmos para o problema de transporte;
• O problema de designação.
5. Otimização em redes
• Problema de caminho mínimo;
• Problema de �uxo máximo.1Nova ementa (Reform. Proj. Pedagógico BSI)
3
Avaliação: aproveitamento e frequência
• 3 provas teóricas: 35, 35 e 30 pontos.
� 10/09 (P1)
� 22/10 (P2)
� 26/11 (P3)
• Nota �nal (aproveitamento):
NF = P1 + P2 + P3
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 3 anteriores,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 atinja namesma a pontuação necessária para ser aprovado.
Frequência
• O aluno que tiver frequência inferior a 75% é reprovado por faltas.
• A chamada será feita em sala, pelo professor, sempre que decorridos emtorno de 15 minutos do início da mesma. O aluno que chegar após achamada, ou não respondê-la, �cará com falta.
• Falta em dia de prova: o aluno somente terá direito a fazer prova em novadata caso apresente justi�cativa no setor de graduação e/ou coordenaçãodo curso, que encaminhará comunicação por escrito ao professor quandojulgá-la plausível.
• É responsabilidade do aluno controlar sua frequência, de modo a evitarreprovação por falta.
4
Logística
Aulas
• Segundas-feiras: 19:00 até 20:40 � Sala 1B104
• Terças-feiras: 20:50 até 22:30 � Sala 1B104
Atividades extra-classe
• Listas de exercícios (�xação)
Atendimento e outras informações
• Professor: Renato Pimentel
� Página: http://www.facom.ufu.br/∼rpimentel
� E-mail: rpimentel @ ufu . br
� Sala 1B139
• Atendimento (agendar previamente através de e-mail):
� Terças-feiras, 18:00 até 19:50, sala 1B139
� Quartas-feiras, 16:00 até 17:40, sala 1B139
� Sextas-feiras, 18:10 até 19:00, sala 1B139
• Material da disciplina:
� http://www.facom.ufu.br/∼rpimentel > Ensino > 2019/2 > GSI027� Otimização
1 Pesquisa Operacional e Tomada de Decisões
Tomada de Decisões
• Tarefa básica da gestão
• Alternativas viáveis
Tomada de Decisões
1. Identi�car o problema
2. Formular objetivos
3. Analisar limitações
4. Avaliar alternativas
5
1.1 De�nição e Origens da Pesquisa Operacional
O que é a Pesquisa Operacional
Segundo Marins (2011)�É o uso do método cientí�co com o objetivo de prover departamentos executivosde elementos quantitativos para a tomada de decisões com relação a operaçõessob seu controle�
Origens
• Termo Pesquisa Operacional: tradução direta de Operational research.
• Inglaterra (1934): invenção do radar.
• 1936: Estação de Pesquisa Manor Bawdsey (Su�olk) � como interceptaraviões inimigos?
• A. P. Rowe (1938), superintendente da estação: criação do termo.
� E�ciência de técnicas de operações a partir de experimentos cominterceptação.
� Análise cientí�ca do uso operacional de recursos militares: II GuerraMundial.
• Pós-Guerra: rápida ascensão Inglaterra e EUA
• EUA (1947): SCOOP (Scienti�c Computation of Optimal Programs) �Pentágono
� Marshall Wood (economista) e George Dantzig (matemático � mé-todo simplex).
� Programação linear
• 1952: ORSA (Sociedade Americana de Pesquisa Operacional)
• 1953: ORS (Sociedade de Pesquisa Operacional) � Inglaterra
Focos distintos
• Pesquisa inglesa: estudos de caso, problemas especí�cos
• Pesquisa americana: modelos e métodos matemáticos
Alguns temas pesquisados pelos americanos:
• Teoria de estoques
• Teoria de �las
• Reposição de equipamentos
6
• Agendamento de tarefas em máquinas
• Teoria de jogos
• Fluxos de redes
• Otimização linear
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
1.2 Fases de Resolução de Problemas
Fases da PO
Formulação do problema
• Problemas reais: forma vaga e imprecisa
• Algumas questões:
� Quem tomará decisões?
� Quais os objetivos?
� Que aspectos estão sujeitos ao controle dos decisores (variáveis dedecisão) e sob quais limitações (restrições)?
� Quais aspectos fogem do controle dos decisores?2www.sobrapo.org.br
7
Construção do modelo
• Modelos: representações simpli�cadas da realidade
• Modelagem: 2 características importantes:
� Permite analisar o problema, indicando relações entre variáveis, quaisdados relevantes e variáveis de maior importância
� Permite estudo de alternativas de ação sem interromper sistema emestudo.
• Podem ser físicos (ex.: maquetes), analógicos (ex.: organograma) e mate-máticos.
Mundo real
Mundo realconsiderado
Modelo
Obtenção da solução
• Típico de PO: modelo matemático.
• Varia conforme a área (programação linear, programação em redes, teoriade �las, etc.)
• Técnicas novas surgem constantemente
• Softwares:
� Solver do Excel
� LINDO � Linear Discrete Optimizer (www.lindo.com)
� ILOG (www.ibm.com/products/ilog-cplex-optimization-studio)
� Simulações: PROMODEL (www.belge.com.br/promodel.php) e ARENA(www.paragon.com.br)
� etc.
8
Teste do modelo e da solução obtida
• O modelo precisa ser testado.
� Teste permite identi�car problemas na criação do modelo (ex.: as-pecto importante omitido, re�namento de aspecto incluído etc.)
� Em alguns casos, teste pode ser comparado com dados anteriores.
Implementação
• Implantação da solução �nal ao sistema.
• Intervenções podem ser necessárias no caso de alguma falha não prevista.
Exemplo de problema: cerca (Taha)
Exemplo 1.1. Um fazendeiro comprou L metros de uma tela e pretende cercaruma pequena á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.
• Área deve ser retangular (ângulos retos)
• Se l e c são respectivamente a largura e o comprimento do retângulo,queremos maximizar
z = l × c ,
sujeita às restrições:
� 2(l + c) = L,
� l ≥ 0, c ≥ 0.
In�nitas soluções
• viáveis: atendem a todas restrições
• ótima: melhor solução viável
Formato geralMaximizar ou minimizar umafunção objetivo sujeita arestrições
9
Problema linear
Exemplo 1.2. maximizar z = 2x1 + 3x2 + 4x3
3x1 + 2x2 + 1x3 ≤ 102x1 + 3x2 + 3x3 ≤ 151x1 + 1x2 − 1x3 ≥ 4
x1, x2, x3 ≥ 0
Obtenção da Soluçãoz = 15.55
x1 =1
3, x2 =
5
9, x3 =
38
9
Problema de transporte
Exemplo 1.3. O modelo de transporte visa minimizar o custo total do trans-porte necessário para abastecer n centros consumidores (destinos) a partir de mcentros fornecedores (origens)
1.3 Principais Áreas da Pesquisa Operacional
Grandes Áreas
Programação Linear
• Mix de produção
• Mistura de matérias-primas
10
• Modelos de equilíbrio econômico
• Carteiras de investimentos
• Roteamento de veículos
• Jogos entre empresas
Modelos em Redes
• Rotas econômicas de transporte
• Distribuição e transporte de bens
• Alocação de pessoal
• Monitoramento de projetos
Teoria das Filas
• Congestionamento de tráfego
• Operações de hospitais
• Dimensionamento de equipes de serviço
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
11
Referências
1. ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H.Pesquisa operacional: para cursos de engenharia. Rio de Janeiro: ElsevierBrasil, 2006.
2. MARINS, F. A. S. Introdução à pesquisa operacional. São Paulo: CulturaAcadê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
Parte I
Programação Linear
2 Introdução à programação linear
Nesta seção, Será considerada uma subclasse particular de problemas de PO,a dos problemas de programação linear.
A característica que de�ne tal subclasse está no modelo matemático.
Equação linear
• Equação da forma
c1 x1 + c2 x2 + · · ·+ cn xn = c0
• Elementos:
� c0, c1, . . . , cn: coe�cientes (conhecidos)
� 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.
12
2.1 De�nições e exemplos
O modelo matemáticoModelo de PL � como qualquer modelo de PO � possui 3 componentes
bá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).
Variáveis de DecisãoAs variáveis de decisão são as incógnitas a serem determinadas pela solução domodelo e os parâmetros (coe�cientes) são valores �xos no problema
RestriçõesDe modo a levarmos em conta as limitações físicas do sistema, o modelo deveincluir restrições que limitam as variáveis de decisão a seus valores possíveis (ouviáveis)
Função ObjetivoÉ uma função matemática que de�ne a qualidade da solução em função das va-riáveis de decisão; é um critério de escolha das variáveis de decisão representadopor uma função
Estrutura de Modelos Matemáticos
Pode-se dizer que:
O problema do modelo matemático de Pesquisa Operacional é escolher os valoresdas variáveis de decisão de forma a obter o melhor resultado da função objetivosujeita às restrições especi�cadas.
Recomendações
• O decisor tem autoridade para escolher a quantidade (valor numérico) doitem? Se sim, esta é uma variável de decisão;
• Ser preciso com relação às unidades de cada variável de decisão (ex.: sealguma moeda, alguma medida de comprimento, volume, massa ou tempo,etc.);
• Não confundir variáveis de decisão com os parâmetros do problema, comoex.: número de máquinas na fábrica, quantidade de cada recurso usado nafabricação de um produto, custos de produção, custos de transporte, etc.
Exemplo 2.1. Um investidor possui $90.000, 00 para investir em ações. Eleestá interessado em duas empresas:
13
• 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 única empresa.Como ele deve planejar seu investimento, de modo a maximizar seu lucro anual?
• Variáveis de decisão: Correspondem às quantidades de ações em cadaempresa (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 pela quantidadede dinheiro disponível para investir; além disso, por uma questão de lógica,ele não pode investir um valor negativo em cada ação;
• Função Objetivo: é a Função matemática que determina o retorno emfunção das variáveis de decisão e que (neste caso) deve ser maximizada.
Função objetivomax L = 6TM + 4CF
Restrições50TM + 30CF ≤ 90.000
50TM ≤ 60.000
30CF ≤ 60.000
Condições de não-negatividadeTM ≥ 0
CF ≥ 0
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 em re-lação ao modelo que está sendo usado;
• Como o modelo é apenas uma representação da realidade, não há garan-tia de que a solução ótima para o modelo se comprovará como a melhorpossível que poderia ter sido implementada para o problema real;
• Entretanto, se o modelo for bem formulado e experimentado, as soluçõestendem a ser uma boa representação para a solução a ser adotada no casoreal.
14
Outro Exemplo
Exemplo 2.2. Uma empresa precisa decidir quais modelos de geladeira produ-zir em sua nova planta. Existem dois modelos disponíveis: luxo e básico. Nomáximo, 1500 unidades do modelo luxo e 6000 unidades do modelo básico po-dem ser vendidas por mês. Empresa contratou 25000 homens-hora de trabalhopor mês. Os modelos luxos precisam de 10 homens-hora de trabalho para seremproduzidos e os modelos básicos, 8 homens-hora. A capacidade da linha de mon-tagem é de 4500 geladeiras por mês, pois as geladeiras dividem a mesma linha.O lucro unitário do modelo luxo é $100, 00 por mês, enquanto o modelo básicolucra $50, 00 durante o mesmo período.
Determine quanto produzir de cada geladeira, de modo a satisfazer todas asrestrições e maximizar o lucro da empresa.
Variáveis de DecisãoSejam x1 e x2 as quantidades (unidades) produzidas dos modelos luxo e básico,respectivamente.
Função ObjetivoAdmitindo que a função lucro é uma função linear de x1 e x2, esse lucro deveser maximizado por uma escolha de x1 e x2, tal que:
max L = 100x1 + 50x2
Como existem recursos limitados, há restrições:
Restrições
1. 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)
Problemas de Programação Linear
De�nição FormalUm 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
15
sujeito a:n∑j=1
aijxj , para i = 1, 2, . . . ,m
xi ≥ 0, ∀i
Algumas De�nições
SoluçãoQualquer especi�cação de valores para as variáveis de decisão, independente dese 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 de todos ospontos que satisfazem todas as restrições é chamado de Conjunto 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 únicaou não.
Hipóteses da Programação Linear
ProporcionalidadeA contribuição de cada variável ao valor da função objetivo é diretamente pro-porcional ao valor da variável, conforme representado pelo termo cjxj na funçãoobjetivo.
De modo semelhante, a contribuição de cada variável às restrições é propor-cional ao valor da variável xj , como representado pelo termo aijxj na restrição.
AditividadeToda função em um modelo de programação linear é a soma das contribuiçõesindividuais das respectivas variáveis.
DivisibilidadeAs variáveis de decisão em um modelo de programação linear podem assumirquaisquer valores, inclusive valores não-inteiros, que satisfaçam as restriçõesfuncionais 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.
16
2.2 Problemas clássicos
Problemas de mistura
Problemas de mistura consistem em combinar materiais obtidos da natureza(ou sobras de outros já previamente combinados) para gerar novos materiais ouprodutos com características convenientes.
Exemplos de problema de mistura
1. Rações: Fábricas de rações produzem variados tipos de rações para de-terminados animais (bovinos, equinos, caprinos, caninos de pequenos egrande portes etc.)
• Mistura de alimentos ou farinhas de restos de alimentos (milho, farelode arroz, etc.)
• Preços de mercados destes produtos são conhecidos
• Composição nutricional é conhecida. Nutrição veterinária especi�canecessidades mínimas e máximas dos nutrientes por kg para cadaespécie de animal.
• Problema de minimizar custo: quais devem ser as quantidades ideaisde cada ingrediente por kg de modo que necessidades nutricionais se-jam atendidas e o custo total dos ingredientes seja o menor possível?
2. Ligas metálicas: Fundições produzem diversos tipos de aço a partir dediversos insumos: lingotes de ferro, gra�te, sucatas industriais, etc.
• Forno de alta temperatura para permitir a mistura
• A composição, em termos de elementos como carbono, silício, man-ganês etc. é determinada por normas técnicas da metalurgia, bemcomo composição dos produtos a serem misturados.
• Preços dos insumos podem variar substancialmente. Entretanto, sãoconhecidos.
• 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 menorpossível
3. Areias para �ltro (ETA)
• Permeabilidade: areias usadas em estações de tratamento de águapara interceptar impurezas da água a�uente
• Unidades de �ltração: areias de portos passíveis de exploração comcomposições distintas
• Custos de dragagem, transporte, seleção e preparo variam p/ cadaporto
17
• Areias dispostas em camadas, devendo obedecer composições estabe-lecidas em norma
• Como combinar os volumes de areia de cada porto, de modo a atenderàs especi�cações, com menor custo possível?
Formulação matemática do problema da mistura
• Obtenção de produto (mistura), combinando-se materiais disponíveis
• Materiais (ingredientes) possuem os componentes desejados na mistura
• Produtos devem satisfazer determinadas especi�cações
• Objetivo: determinar as quantidades dos ingredientes para criar misturacom composição especi�cada com menor custo possível (minimização).
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.
Exemplo: ração
Exemplo 2.3. Queremos saber quais as quantidades ideais de cada ingredientepara fazer uma quantidade de ração para aves, com as necessidades nutricionaisatendidas e o custo total dos ingredientes seja o menor possível. Temos dispo-níveis dois ingredientes (milho e farinha de osso), cujos custos (em $ por Kg)e ingredientes (em unidades por Kg) estão listados na tabela a seguir:
Vitamina A Vitamina B Proteínas CustoMilho 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, 9 devitamina B e 1 de proteína.
18
Modelo Matemático
min C = 65x1 + 30x2
sujeito a:2x1 + 3x2 ≥ 7
3x1 + 2x2 ≥ 9
1x1 + 0x2 ≥ 1
x1 ≥ 0;x2 ≥ 0
Mix de produção
Problemas de mix de produção envolvem decidir quais produtos, e quanto fabri-car de cada produto em um certo período.
Formulação matemática do mix de produção
• Tendo em vista a capacidade limitada de produção � máquinas, RH, ca-pital, armazenagem, etc. � e os diversos produtos que a empresa podefabricar e vender, deseja-se determinar quais fabricar e quanto fabricar decada produto, de modo a maximizar o lucro, num determinado período.
Maximizarf(x1, . . . , xn) = `1x1 + `2x2 + · · ·+ `nxn
Sujeito às restrições:
a11x1+ a12x2+· · ·+ a1nxn ≤ C1
a21x1+ a22x2+· · ·+ a2nxn ≤ C2
. . .
am1x1+am2x2+· · ·+amnxn ≤ Cmdj ≤ 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.
O Exemplo 2.2 visto anteriormente (problema das geladeiras) é um exemplode problema de mix de produção.
19
Outro exemplo (MARINS, 2011)
Exemplo 2.4. Uma empresa deseja programar a produção de um utensílio decozinha e requer o uso de 2 recursos: mão-de-obra e material. Ela está consi-derando a 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 o suprimentode material é 200 kg/dia.
ModeloA B C
Mão-de-obra (horas/unidade) 7 3 6Material (kg/unidade) 4 4 5Lucro ($/unidade) 4 2 3
Modelagem
• xa, xb, xc: produções diárias de A, B e C.
• Restrições:
� 7xa + 3xb + 6xc ≤ 150 (limitação de mão-de-obra)
� 4xa + 4xb + 5xc ≤ 200 (limitação de material)
� xa ≥ 0, xb ≥ 0, xc ≥ 0 (não-negatividade)
• Função objetivo: maximização do lucro total
L = 4xa + 2xb + 3xc
20
2.3 Exercícios
1. Um sapateiro faz 6 sapatos por hora, se �zer somente sapatos, e 5 cintospor hora, se �zer somente cintos. Ele gasta 2 unidades de couro para fabri-car 1 unidade de sapato e 1 unidade de couro para fabricar uma unidadede cinto. Sabendo-se que o total disponível de couro é de 6 unidades e queo lucro unitário por sapato é de $5,00 e o do cinto é de $2,00, pede-se: omodelo do sistema de produção do sapateiro, se o objetivo é maximizarseu 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,00de lucro por caixa, pelo menos 100 caixas de pêssegos a $10,00 de lucropor caixa, e no máximo 200 caixas de tangerinas a $30,00 de lucro porcaixa. De que forma deverá ele carregar o caminhão para obter o lucromáximo? Construa o modelo do problema.
3. Uma fundição tem de produzir 10 toneladas de um tipo de liga metálica e,para isso, tem disponível: lingotes de ferro, gra�te e sucata. 2 componentessão relevantes para a liga: carbono e silício. A tabela fornece a fraçãodestes elementos nos ingredientes disponíveis, seus custos unitários, suasdisponibilidades em estoque, bem como a composição da liga de acordocom as especi�cações. Quais quantidades dos ingredientes devem compor aliga, de modo que as especi�cações sejam satisfeitas e o custo seja mínimo?
Ingredientes Especi�cações liga
Composição (%) Lingotes Gra�te Sucata Mínimo Máximo
Carbono 0,0050 0,90 0,090 0,00 0,095
Silício 0,14 - 0,27 0,19 0,20
Custos (R$/ton) 90 180 25
Estoque (ton) 5 5 12
Referências
1. ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H.Pesquisa operacional: para cursos de engenharia. Rio de Janeiro: ElsevierBrasil, 2006.
2. MARINS, F. A. S. Introdução à pesquisa operacional. São Paulo: CulturaAcadêmica, 2011.
3. NOGUEIRA, F. Pesquisa Operacional, UFJF.
4. TAHA, H. Pesquisa operacional. 8a. ed. São Paulo: Prentice Hall, 2008.
21
Os materiais de parte desta seção foram gentilmente cedidos por Paulo H.R. Gabriel (FACOM/UFU)
Adaptações: Renato Pimentel, FACOM/UFU
3 Solução grá�ca
• A visualização de soluções de um problema pode ser útil para melhorar aintuição sobre o mesmo.
• Mesmo quando somente limitada a um desenho esquematizado sobre oplano.
• No caso de PL, permite delinear um método de solução � i.é., encontrar asolução ótima.
• Consideram-se aqui problemas com apenas duas variáveis
• (Representação das soluções factíveis e da solução ótima num plano car-tesiano)
NotaVamos considerar, por questões de conveniência, todas as restrições sob a formade inequações.
Exemplo 3.1. Maximizar f(x1, x2) = x1 + 2x2 sujeito a:
x1 + x2 ≤ 4
x1 ≤ 2
x2 ≤ 3
x1 ≥ 0, x2 ≥ 0
• Condições de não-negatividade:
0 1 2 3 4 5 6 70
1
2
3
4
5
6
x1
x2
22
• 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
x2
• Adicionando a restrição x1 ≤ 2 às anteriores:
0 1 2 3 4 5 6 70
1
2
3
4
5
6
x1
x2
23
• Por �m, adicionando a restrição x2 ≤ 3 às anteriores: obtém-se a regiãofactí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
x2
Determinação da solução ótimaConsiderando 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 reta x1 + 2x2 = 0.
Esta reta de�ne a curva de nível 0 da função.
Curva de nívelA curva de nível f0 de uma função f é dada pelo conjunto de pontos no R2 osquais, aplicados à função f , resultam em f = f0.
• Representando a curva de nível 0 no grá�co, junto com o sentido de cres-cimento.
1 2 3 4 5 6 7
1
2
3
4
5
6
x1
x2
24
Vetor gradienteO 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, ogradiente será constante (a direção e o sentido não variam)
• Consequentemente, indica a direção onde as curvas de f assumem valoresmaiores.
• No caso de retas, é constante e perpendicular às mesmas.
ObservaçãoNa prática, também podemos testar tomando pontos de um lado e de outro deuma curva de nível, e veri�cando o valor de f .
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.Como se deseja maximizar a função objetivo, busca-se o maior valor possível
de f dentro da região viável. Portanto, �caminha-se� no sentido para o qual ovetor gradiente aponta.
• 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.
25
• 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.
Considerações
1. O conjunto de todas as soluções viáveis de um modelo de PL é um conjuntoconvexo.
2. Toda solução viável básica do sistema de equações lineares de um modelode 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ão esteé 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 do con-junto de soluções viáveis (soluções múltiplas), então ela assume este valorpara pelo menos dois pontos extremos do conjunto convexo e para qual-quer combinação convexa desses pontos extremos, isto é, todos os pontosdo segmento de reta que une estes dois pontos (em outras palavras, aaresta do polígono que contém estes dois pontos).
Solução do problema das geladeirasVoltando 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
26
x2 ≤ 6000
x1 ≥ 0;x2 ≥ 0
• 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
• 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
27
• 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
• max f(x1, x2) = 100x1 + 50x2
� 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)
28
• max f(x1, x2) = 100x1 + 50x2
� 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
• max f(x1, x2) = 100x1 + 50x2
� 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ção objetivo, em relaçãoà curva de nível.
• Logo, a empresa deve produzir 1500 geladeiras do modelo luxo, e 1250 domodelo básico por mês, maximizando o lucro, que será de $ 212 500.
Solução do problema da raçãoVoltando ao modelo da ração (problema de mistura):
min C = 65x1 + 30x2
29
sujeito a:2x1 + 3x2 ≥ 7
3x1 + 2x2 ≥ 9
1x1 + 0x2 ≥ 1
x1 ≥ 0;x2 ≥ 0
• Não-negatividade
1 2 3 4
1
2
3
4
x1
x2
• 1x1 + 0x2 ≤ 1.
1 2 3 4
1
2
3
4
x1
x2
30
• 2x1 + 3x2 ≥ 7.
1 2 3 4
1
2
3
4
x1
x2
• 3x1 + 2x2 ≥ 9.
1 2 3 4
1
2
3
4
x1
x2
• minC = 65x1 + 30x2
� 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 deminimização: caminha-se no sentido oposto ao de crescimentode C.
31
• minC = 65x1 + 30x2
� 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
• minC = 65x1 + 30x2
� Na solução viável básica (1, 3), temos C = $155.
1 2 3 4
1
2
3
4
Solução ótima
x1
x2
• (1, 3) é a solução ótima do problema da ração. Neste ponto, o custo totalé o menor possível, $ 155.
Outras situações
Exemplo 3.2. Maximizar f(x1, x2) = x1 + 2x2 sujeito a:
−3x1 + x2 ≤ 2
x2 ≤ 3
x1 + 2x2 ≤ 9
3x1 + x2 ≤ 18
x1 ≥ 0, x2 ≥ 0
32
• max f(x1, x2) = x1 + 2x2
1 2 3 4 5 6 7 8
1
2
3
4 Múltiplassoluçõesótimas
x1
x2
Região viável ilimitada
• In�nitas soluções ótimas (minimização)
x1
x2
• Não existe solução ótima (minimização)
x1
x2
33
Região vazia
• Região viável vazia: não existe solução ótima (restrições con�itantes)
x1
x2
3.1 Exercícios
1. Faça a solução grá�ca do exercício do sapateiro e do exercício das frutasvistos anteriormente. Dica: no problema das frutas, a quantidade delaranjas é conhecida (dada).
Referências
1. ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H.Pesquisa operacional: para cursos de engenharia. Rio de Janeiro: ElsevierBrasil, 2006.
2. MARINS, F. A. S. Introdução à pesquisa operacional. São Paulo: CulturaAcadê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
4 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 (como nasolução grá�ca)
• 1o passo: Criação de Variáveis de folga ou excesso: transformam o modelonum sistema linear de equações a ser resolvido.
34
Eliminação das desigualdades
• Inicialmente, é preciso eliminar as desigualdades presentes nas restriçõesdo modelo.
� 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, por exemplo, x3, querepresente tal diferença, permite que a inequação seja escrita como umaequação:
2x1 + x2 + x3 = 5
• x3 ≥ 0 é denominada variável de folga.
• 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 re-presentar a diferença pela subtração de uma variável de folga não-negativa:
x1 + 3x2 − x4 = 7 .
• Algumas referências chamam neste caso a nova variável de variável deexcesso.
ObservaçãoApenas as restrições técnicas são reescritas como equações.
As restrições de não-negatividade são mantidas.
Exemplo
maxZ(x1, x2) = 5x1 + 2x2
sujeito a
x1 ≤ 3
x2 ≤ 4
x1 + 2x2 ≤ 9
x1 ≥ 0, x2 ≥ 0
35
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ária aintrodução de variáveis de folga na mesma.
• Note que a função objetivo foi reescrita, de modo a deixar o lado direitonulo.
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ção obje-tivo.
Solução viável básica inicial
x3 = 3 x1 = 0
x4 = 4 x2 = 0
x5 = 9 Z = 0
Algoritmo
1. A solução já é a ótima? Se sim, o problema encontra-se resolvido, e oalgoritmo se encerra nesta etapa.
• Este é um problema de maximização. A solução será ótima se nãohouver coe�cientes negativos na linha L0 da função objetivo.
36
• Caso haja � este é o caso do exemplo � é preciso passar à etapaseguinte, iterativa.
2. As variáveis de folga formam uma base do Rm (m é o número de restrições),pois a matriz m×m formada pelas linhas Li, i = 1, . . . ,m e as respectivascolunas é uma matriz identidade, portanto com determinante diferente de0.
• As variáveis de folga são chamadas portanto de básicas (representadasna coluna à esquerda na tabela), e as variáveis de decisão originaisdo problema, não básicas.
• Esta etapa do algoritmo consiste em colocar na base uma variávelde decisão, retirando da mesma uma das variáveis de folga (deve serrepetida até que a condição da etapa 1 seja satisfeita)
Etapas do passo 2
1. Identi�car quem entrará na base (condição de otimalidade):
Regra de Dantzig: Procura-se, na linha L0, qual o coe�ciente negativo demaior valor absoluto (i.é., o menor valor). A variável associada a ele é aque entrará na base.
• 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
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 omenor de todos � apenas divisões não-negativas e �nitas são consideradas.Esta é a Condição de viabilidade.
• No caso, temos m = 3, j = 1 (selecionou-se x1 para deixar a base) eas divisões
b1c11
=3
1= 3
b2c21
=4
0=∞ (ignora-se)
b3c31
=9
1= 9
3Linha L0 da função objetivo não é considerada neste trecho
37
• Portanto, x3 (associada a linha L1) deixará a base e a linha L1 passaa ser a linha pivô desta iteração � razão mínima não-negativa nestalinha.
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
• O elemento c11 = 1, dado pelo cruzamento das linhas e colunas pivô,é o número pivô da iteração.
3. Rede�ne-se a linha pivô, dividindo-se a mesma pelo número pivô.
• No caso,
L(1)1 =
L(0)1
c11=L
(0)1
1
• 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
4. As demais linhas (incluindo a da função objetivo) são também rede�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.
• 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
• Linha 2: L(1)2 = L
(0)2 − 0 L
(1)1 = L
(0)2 (inalterada)
38
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
• 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 6
• 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
Nova iteração do passo 2
• Como se pode observar na tabela anterior, ainda há um coe�ciente nega-tivo na linha L0.
• Portanto, repete-se o passo 2.
� Agora x2 entrará na base, e x5 sairá. Portanto, o número pivô éC23 = 2.
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
39
Situações especiais
1. Empate na entrada da baseNa condição de otimalidade, quando se busca a variável que entrará na base, sehouver empate escolhe-se arbitrariamente qual deverá de fato entrar.
Ú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 e x2).Na 1a. iteração, deve-se escolher qual das duas entrará (aparecerão como -4 noquadro inicial).
2. Empate na saída da baseNa condição de viabilidade, quando se busca a variável que sairá na base, sehouver empate em geral também se escolhe arbitrariamente qual deverá de fatosair.
Exemplo:maxZ = 5x1 + 2x2, sujeito a
x1 ≤ 3
x2 ≤ 4
4x1 + 3x2 ≤ 12
x1 ≥ 0, x2 ≥ 0
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ão não-negativa):
x3 :b1c11
=3
1= 3 x5 :
b3c31
=12
4= 3
Escolhe-se, por exemplo, x3 para deixar a base:
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
40
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.
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 objetivo nãomelhora, sendo possível que o método entre em uma sequência de iterações semnunca melhorar tal valor e satisfazer a condição de otimalidade. Neste exemplo,esta última foi satisfeita (encontrou-se solução ótima).
Exemplo de caso em que ocorre ciclagem (Taha, 2008):
maxZ =3
4x1 − 20x2 +
1
2x3 − 6x4
sujeito a
1
4x1 − 8x2 − x3 + 9x4 ≤ 0
1
2x1 − 12x2 −
1
2x3 + 3x4 ≤ 0
x3 ≤ 1
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
Exercício: http://simplex.tode.cz/en/
3. Soluções múltiplasModelo 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
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
41
↓ 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, demodo que o valor da função objetivo �que inalterado � apenas os valores dasvariáveis se alteram.
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-se novasolução em x1 = 3, x2 = 1 e Z = 10.
Qualquer combinação convexa desta solução e da anterior também será umasolução ótima. Gra�camente: segmento de reta entre os pontos (0, 5/2) e (3, 1)
4. Função objetivo ilimitada
• Outro resultado possível é aquele no qual nenhuma variável se quali�capara ser a variável básica a deixar a base.
• Este resultado ocorre quando a variável que entra na base pode ser aumen-tada inde�nidamente sem dar valores negativos a qualquer das variáveisbásicas atuais. Na forma tabular, isso signi�ca que todos os coe�cientesda coluna pivô (excluindo-se a linha L0) são negativos ou zero.
• 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, seja poromitir restrições relevantes, seja por declará-las de modo incorreto.
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
42
Todos os coe�cientes das restrições sob x2 são negativos ou zero. Note que x2
pode ser aumentada inde�nidamente sem desobedecer nenhuma das restrições.
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
. . .
5. Problema de minimizaçãoQuando a função objetivo tiver de ser minimizada pode-se fazer duas coisas,
a saber:
• Inverter o teste de otimização e o critério de entrada na base. Assim, setodos os coe�cientes da linha L0 forem negativos, ou nulos, a solução éótima. Caso contrário, escolha a variável xj para entrar que apresente omaior valor.
• Transformar o problema de minimização em um problema de maximiza-ção. Sabe-se que achar o mínimo de uma função é equivalente a encontraro máximo do simétrico desta função.
� Exemplo: minW = 2x1 + 3x2 ⇔ maxZ = −2x1 − 3x2. Depois, nasolução �nal, fazer W = −Z.
• 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 de maximiza-ção, onde as restrições são do tipo
ci1x1 + ci2x2 + · · ·+ cinxn ≤ bi,
onde a constante do lado direito bi é tal que bi ≥ 0.
� Sob esta forma, as variáveis acrescentadas são de folga e o problemapode ser resolvido como visto.
� Problemas com restrições envolvendo a desigualdade ≥ ou mesmoigualdade (=) exigem etapas adicionais.
43
Lado direito negativo
• Para que a resolução vista possa ser empregada, é preciso que o lado direitodas 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 .
• O problema é resolvido fazendo-se a multiplicação de ambos os lados por−1:
x1 − x2 − x3 = 3 .
• Neste caso, o coe�ciente de x3 é −1. Logo, esta não pode entrar na base(na equação reescrita é variável de excesso). Isto equivale a partirmos dainequação
x1 − x2 ≥ 3 .
(nada mais do que a inequação original multiplicada por −1 � a desigual-dade é invertida).
Solução inicial arti�cial
• Para se iniciar a resolução de problemas de PL �mal comportados� (comrestriçõ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:
� Método do M -grande;
� Método das duas fases.
Considere o seguinte problema:
maxZ = 5x1 + 2x2 sujeito a:
x1 ≤ 3
x2 ≤ 4
x1 + 2x2 ≥ 9
x1 ≥ 0, x2 ≥ 044
maxZ tal que Z − 5x1 − 2x2 = 0 sujeito 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.
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, mas permitema inicialização do processo de maneira automática.
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:
� As punições visam zerar tais variáveis na solução ótima.
� Isto sempre ocorrerá se houver solução viável.
Regra de penalização das variáveis arti�ciais
DadoM > 0, valor su�cientemente alto (M →∞), o coe�ciente na funçãoobjetivo representa uma punição adequada quando igual a:
� −M , em problemas de maximização;
� 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 ter valornulo no ótimo.
Retornando ao exemplo anterior:
45
maxZ = 5x1 + 2x2 −Mt1
sujeito a:
x1 + x3 = 3
x2 + x4 = 4
x1 + 2x2 − x5 + t1 = 9
x1, . . . , x5, t1 ≥ 0
maxZ tal que Z − 5x1 − 2x2 +100t1 = 0
sujeito 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ável de�nirM = 100.
• 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 (t1está na base) e portanto Z = −900.
• Para empregar a resolução do simplex, é preciso que os coe�cientes dasvariáveis básicas na linha L0 sejam todos nulos. Este ajuste inicial podeser feito rede�nindo-se esta linha como sendo a soma dela mesma com alinha associada a t1 multiplicada por −M :
L(0)0 = L
(0)0 −ML
(0)3 = L
(0)0 − 100L
(0)3
• 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
46
↓ 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
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
O método doM -grande pode resultar em erros de arredondamento durante afase de punição do valorM � de�nido sempre de forma relativamente arbitrária.
• Na prática, usa-se o método das duas fases, desenvolvido posteriormente.
• O método das duas fases está implementado em praticamente todos ospacotes comerciais para resolução de problemas de PL.
Método das duas fases
• Alternativa ao método doM -grande, contornando a di�culdade do mesmopor eliminar o uso da constante M .
• Inicialmente, variáveis arti�ciais são introduzidas ao modelo, como no mé-todo anterior.
• Como o nome sugere, há duas fases ou etapas:
� Fase I: consiste em resolver um problema de minimização cuja funçãoobjetivo é dada pelo somatório das variáveis arti�ciais. Espera-seque o mínimo seja zero (requisito para Fase II).
47
ObservaçãoCaso o valor mínimo da soma seja diferente de zero, o problemanão tem nenhuma solução viável, o que encerra o processo � variávelarti�cial positiva indica que restrição original não foi satisfeita.
� Fase II: Usa-se a solução da Fase I como solução viável básica inicialpara o problema original.
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
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
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 .
48
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
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
• No quadro (2), −W = 0, e não há coe�cientes negativos para as variáveisfora 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 objetivoW sãonulas.
• Neste momento, pode-se eliminar totalmente as colunas das variáveis ar-ti�ciais t1 e t2 e passar à fase II.
� Eliminam-se também as linhas, quando for o caso (variáveis arti�ciaisfora da base).
49
Fase IIApós eliminar as colunas das variáveis arti�ciais, reescreve-se o problema
original como:
maxZ = 4x1 + x2
sujeito a
x1 + 1/5x3 = 3/5
x2 − 3/5x3 = 6/5
x3 + x4 = 1
x1 ≥ 0, . . . , x4 ≥ 0 .
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
4.1 Exercícios
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 .
50
Parte II
Dualidade
5 Dual e sua relação com o primal
• Modelo dual: de�nido diretamente a partir do modelo original (ou primal)do problema de PL.
• Forte relação com o problema de origem:
� 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 se gerarum problema menor, cuja solução seja mais rápida/menos cara que nomodelo original.
• Outra vantagem: transformar um problema de minimização num de ma-ximização � o que permite aplicação direta do algoritmo simplex.
Forma de equações do modelo primalA construção do modelo dual será baseada na chamada forma de equações
(TAHA, 2008) do modelo original, usada para a resolução pelo algoritmo dosimplex. Na forma de equações:
1. Todas as restrições técnicas � isto é, excluindo-se as de não-negatividade� são dadas como equações, com o lado direito não negativo.
2. Todas as variáveis são maiores ou iguais a zero.
Construção do modelo dual com base no primal
1. O dual de um problema de maximização (minimização) é um problema deminimizaçã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 primalde�nirão os coe�cientes da j-ésima restrição primal;
4Não se consideram as de não-negatividade
51
5. Os coe�cientes da função objetivo do dual são dados pelas constantes (ladodireito) das restrições do primal;
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
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 .
• 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 for deminimização, todas as restrições serão (≥).
• Outro fato é que as variáveis duais yi são não negativas, mas nem sempreisto ocorre.
• Casos mais gerais, onde no modelo primal há restrições (≥) e (=), ouhá variáveis irrestritas (podem assumir valores negativos), levam a outrassituações no dual.
52
Regras para construção do dual
• Restrições de sinal das variáveis duais: de acordo com os coe�cientes dasvariáveis de folga do primal.
• Exemplo:
minZ = 15x1 + 12x2
sujeito a
x1 + 2x2 ≥ 3
2x1 − 4x2 ≤ 5
x1 ≥ 0, x2 ≥ 0 .
• 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 e x4.Note que todas são do tipo (≤) pois o dual é de maximização.
Reescrevendo as duas últimas restrições, temos:
maxD = 3y1 + 5y2
sujeito a
y1 + 2y2 ≤ 15
−2y1 − 4y2 ≤ 12
y1 ≥ 0
y2 ≤ 0 .
ExercícioVeri�que, para o exemplo de maximização visto anteriormente, que as res-
trições de não negatividade para y1, y2 e y3 são coerentes com os coe�cientesdas variáveis de folga do problema.
53
• Restrição do tipo igualdade (=) no primal: variável irrestrita no dual
• Variáveis irrestritas: podem assumir qualquer valor real, mesmo valoresnegativos
maxZ = 5x1 + 12x2 + 4x3
sujeito a
x1 + 2x2 + x3 ≤ 10
2x1 − x2 + 3x3 = 8
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 .
• 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.
• Variável irrestrita no primal: restrição associada no dual é de igualdade(=).
maxZ = 5x1 + 6x2
sujeito a
x1 + 2x2 = 5
−x1 + 5x2 ≥ 3
4x1 + 7x2 ≤ 8
x1 irrestrita, x2 ≥ 0 .
• Uma situação não apresentada no modelo primal é a de variável irrestrita.
• Nesta situação, se xi é irrestrita, então de�nem-se duas variáveis não-negativas, x−i e x+
i , cuja diferença entre ambas resulta na irrestrita:
xi = x−i − x+i
54
• Sendo assim:
� Se xi ≥ 0, então x−i ≥ x+i ≥ 0;
� Se xi < 0, então x+i > x−i ≥ 0.
• 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 ≥ −5
2y1 + 5y2 + 7y3 ≥ 6
−y2 + 0y3 ≥ 0
0y2 + y3 ≥ 0
Das 2 primeiras restrições, obtém-se y1 − y2 + 4y3 = 5 � basta multiplicar asegunda por −1.
Reescrevendo:
minD = 5y1 + 3y2 + 8y3
sujeito a
y1 − y2 + 4y3 = 5
2y1 + 5y2 + 7y3 ≥ 6
y1 irrestrita, y2 ≤ 0, y3 ≥ 0 .
Teoremas
Teorema I (Dualidade fraca)Se ambos o primal e o dual possuem soluções viáveis, então Z ≤ D para
qualquer solução viável do primal de maximização e qualquer solução viável dodual 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ão
as mesmas constituem soluções ótimas
55
• 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
• Temos, portanto Z ≤ D.
• Considere agora o par de soluções viáveis (x1, x2) = (3, 3) para o primal 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 ótimas parao primal e dual.
Teorema da folga complementarSeja 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.
56
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 ótimaassociado à 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 ao coe�cientena linha L0 ótima da variável xj do primal:
y∗m+j = pj − cj , j = 1, . . . , n.
Uma vez que o dual do dual é o próprio problema primal, pode-se determinara solução do primal a partir da solução do dual.
5.1 Exercícios
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 .
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
57
Parte III
Problemas de transporte
6 Introdução a problemas de transporte
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:
� Problemas de transporte;
� Problemas de transbordo;
� Problemas de designação.
• Referem-se, por exemplo, ao transporte ou distribuição de mercadorias,dos centros de produção aos mercados consumidores;
• Problemas de minimização do custo � impacto direto no lucro de cadaproduto;
• Limitações de oferta e demanda devem ser respeitadas � admite-se seremconhecidas.
7 Problema de transporte
7.1 Modelagem
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
......
......
58
Componentes do modelo
ai : as quantidades disponíveis, ou ofertadas, em cada origem i
bj : as quantidades requeridas (demandadas) , em cada destino 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 destinos nãopode 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 sejam satis-feitas:
m∑i=1
xij = bj
• 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
Exemplo: construção de rodovia5
• Na construção de uma rodovia, empregam-se jazidas de rochas para ob-tenção de pedra britada.
• É conveniente transportar este material de jazidas em pedreiras localizadasnas proximidades para alguns pontos preestabelecidos ao longo do caminhoem que passará a estrada.
5Adaptado de ARENALES (2006)
59
D1
D2
P1
D3
P4
P2
P3
Esquema param = 4 pedreiras en = 3 depósitos
• A tabela a seguir contém os dados do problema. Os custos e demandassã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
Se xij é a quantidade (em toneladas) da pedreira i para o depósito j, pode-seformular 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
60
Distribuição para centros de consumo
• Uma empresa fabrica um determinado produto em três cidades P1, P2 eP3; o produto destina-se a quatro centros de consumo C1 , C2, C3 e C4.O custo estimado de transportar o produto das fábricas para os centrosconsumidores, assim como a demanda de cada centro e a oferta de cadafá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 que tornamínimo o custo total de transporte entre as quatro cidades e os três centrosconsumidores.
Se xij ≥ 0 é a quantidade de produtos transportados da unidade i, 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
7.2 Exercícios
1. Uma rede de depósitos de material de construção tem 4 lojas que devemser abastecidas com 50 m3 (L1), 80 m3 (L2), 40 m3 (L3), 100 m3 (L4) deareia grossa. Essa areia pode ser encarregada em 3 portos P1, P2 e P3,cujas distâncias às lojas estão no quadro (em km):
61
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 total percor-rida entre os portos e as lojas e supra as necessidades das lojas. Construao modelo linear do problema.
2. Um dado produto é produzido em diferentes fábricas do país com capa-cidades de produção limitadas e deve ser levado a centros de distribuição(depósitos) em regiões onde há demandas a serem satisfeitas. O custo detransporte de cada fábrica a cada depósito é proporcional à quantidadetransportada. A tabela a seguir fornece os custos unitários de transportede cada fábrica para cada depósito, bem como as demandas em cada de-pó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.
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: uma emDenver e outra em Miami. As capacidades das três fábricas para o próximotrimestre são 1000, 1500 e 1200 carros. As demandas trimestrais nas duascentrais de distribuição são 2300 e 1400 carros. O mapa de distânciasentre 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.
62
7.3 Resolução
Resolução de problemas de transporte
• Os problemas de transporte vistos são casos particulares de problemas deprogramação linear
• Como todo problema de PL, é possível a resolução algébrica via algoritmosimplex.
• Entretanto, é possível aproveitar as particularidades do problema de trans-porte para resolvê-lo de forma mais e�ciente que o caso geral do simplex.
Equilíbrio entre oferta e demanda
• Vamos considerar a priori que existe igualdade entre a oferta e a demanda,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.
Exemplo
• Vamos retomar um exemplo visto anteriormente � o de distribuição paracentros de consumo:
• Uma empresa fabrica um determinado produto em três cidades P1, P2 eP3; o produto destina-se a quatro centros de consumo C1 , C2, C3 e C4.O custo estimado de transportar o produto das fábricas para os centrosconsumidores, assim como a demanda de cada centro e a oferta de cadafá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), por-tanto o problema está em equilíbrio.
63
• 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 por igualdades� simpli�cação que reforça o conceito do equilíbrio.
Quadro de soluções
• O quadro de soluções de um problema de transporte é um esquema derepresentação do problema em forma de tabela, para a metodologia deresolução a ser usada.
• Para um problema geral, é dado como
Origem
Destino1 2 . . . n Oferta
1
c11 c12 . . . c1na1
2
c21 c22 . . . c2na2
... . . . . . .. . . . . .
...
m
cm1 cm2 . . . cmn
am
Demanda b1 b2 . . . bn
Voltando ao exemplo anterior, o quadro de soluções é dado por
64
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
Método stepping stone
• Um método bastante usado na resolução de problemas de transporte é ochamado stepping stone
• Esse 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, evolte ao passo anterior;
4. Se for ótima, interrompa.
Solução Inicial
• Sabe-se que uma solução inicial deverá ser uma solução básica viável dosistema formado pelas restrições do modelo
• Além disso:
Teorema
Qualquer 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á formada por(m+ n− 1) variáveis básicas;
• Existem diferentes critérios para encontrarmos a solução básica inicial.
Serão vistas duas maneiras de encontrar a solução inicial:
1. Regra do canto Noroeste
2. Processo de custo mínimo
65
Regra do canto NoroesteA 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 qua-dro), associado ao custo c11;
2. Coloque nessa célula a maior quantidade permitida pela oferta (linha) edemanda (coluna) correspondentes;
3. Atualize os valores da oferta e da demanda que foram modicados pelopasso (2);
4. Siga para a célula à direita se houver alguma oferta restante e volte aopasso (2); Caso contrário, siga para a célula inferior e volte ao passo (2).
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 é a quantidademáxima de demanda do destino 1;
• Assim, toda demanda do destino 1 foi atendida e ainda restaram 2 unida-des 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.
Regra do Canto Noroeste
• O processo se repete até alcançarmos a célula inferior direita do quadrode 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
66
• No caso, temos
x11 = 7, x12 = 2, x22 = 4, x23 = 6, x33 = 4, x34 = 4 e C = 218
Observação
É importante observar que na regra do canto Noroeste a solução inicial é ob-tida sem levar em consideração os custos dos transportes cij , isto é, dependeexclusivamente das ofertas das origens e das demandas dos destinos.
Processo de Custo Mínimo
• Este processo para fornecer uma solução inicial leva em consideração, alémdas ofertas e das demandas, os valores dos custos
• Os seguintes passos devem ser seguidos:
1. Localize no quadro o menor cij que não tenha oferta ou demandanula
2. Coloque na célula a maior quantidade permitida pela oferta e de-manda correspondente
3. Atualize os valores da oferta e da demanda que foram modicadas pelopasso (2) e volte ao passo (1).
• O processo se repete até que sejam esgotadas as ofertas e suprimidas asdemandas de todos os destinos
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 unidades permitida,levando em conta a restrição de oferta e demanda;
• Insere-se, assim, 4 unidades nesta célula, que é a demanda do destino 4,e atualiza-se a oferta da origem 2 para 6 unidades uma vez que 4 foramconsumidas.
67
Processo de Custo Mínimo
• Eliminando o destino 4 do quadro, o menor custo é igual a 2 e correspondeà célula (2, 1);
• A esta célula, serão atribuídas 6 unidades, esgotando-se a oferta da origem2 e diminuindo a demanda do destino 1 para 1 unidade.
• Este processo se repete até que todas as ofertas sejam consumidas e todasas demandas atendidas, quando então encontramos uma solução inicialfactí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
• 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
Teste de otimalidade
• Conhecida uma solução básica viável inicial, devemos obter a função obje-tivo somente em função das variáveis não básicas, para saber se a presentesolução já é ótima.
• Da mesma forma como é feito no método simplex, caso a solução aindanão seja ótima devemos determinar a variável que entra e a que sai dabase.
Método u− v
• É necessário eliminar as variáveis básicas da função objetivo e, para isso,devemos somar a ela múltiplos das restrições do modelo.
68
• Sejam u1, u2, . . . , um os valores que irão multiplicar as equações de oferta,antes de somá-las à função objetivo;
• Sejam v1, v2, . . . , vn os múltiplos análogos para cada restrição de demanda:
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, . . . , n
• 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 a eliminá-lasda função objetivo.
• Uma vez que o número de variáveis básicas é igual a (m + n − 1) vamoster (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 uma dessas variáveissem violar as equações.
• Como exemplo, considere o quadro de soluções do método do custo mí-nimo.
69
• 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
• Atribuindo um valor arbitrário a u1, descobrimos os demais valores de uie vj .
• Por exemplo, para u1 = 0, temos:
v1 = 9 v2 = 10 v3 = 6 v4 = 8
u1 = 0 u2 = −7 u3 = 2
• A partir dos valores de ui e vj , calcularemos os coe�cientes das variáveisnã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 = −3
x14 : 5− 0− 8 = −3
x22 : 8 + 7− 10 = 5
x23 : 9 + 7− 6 = 10
x34 : 4− 2− 8 = −6
• Uma solução viável básica é ótima se, e somente se, cij − ui− vj ≥ 0 paratodo i, j tal que xij seja uma variável não básica.
• Sendo assim, como as variáveis x12, x14 e x34 apresentaram coe�cientesnegativos a solução ainda não é ótima.
Construindo uma Nova Solução Factível
• Uma vez aplicado o Método u − v, podemos dizer se uma solução básicaé ótima ou não;
• Caso não seja ótima, iniciamos a busca por uma nova solução.
70
• Como acontece com o método simplex tradicional devemos:
1. Determinar a variável que entra na base
2. Determinar variável que sai da base
3. Identi�car a nova solução factível
Passo 1: Encontrar a variável que entra na base
• Considerando apenas as variáveis não básicas, devemos escolher aquelastais 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 de menorvalor, ou seja, x34, cujo coe�ciente é −6.
Passo 2: Encontrar a variável que sai da base
• O aumento do valor da variável que entra na base dispara uma reação emcadeia para compensar mudanças nas demais variáveis básicas, de modoa continuar satisfazendo as restrições de oferta e demanda.
• A primeira variável básica que chegar a zero se torna a variável que deixaa base.
• Suponha que a variável x34 entrará na base com um valor θ ≥ 0, que deveser o maior possível.
Passo 2 (continuação)
• Estabelecemos, então, um valor θ para variável x34, o que signi�ca diminuirx24 na mesma quantidade para restabelecer a demanda igual a 4 (coluna4)
• 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 (linha3)
71
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
Passo 2 (continuação)
• Devemos, agora, determinar o maior valor permitido a θ, isto é, o valorde θ 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.
Passo 3: Encontrar a nova solução básica
• A 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
• 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
72
• Fazendo u3 = 0, temos:
u1 = −2 u2 = −3
v4 = 4 v1 = 5 v3 = 8 v2 = 12
• 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 = −3
x14 : 5 + 2− 4 = 3
x22 : 8 + 3− 12 = −1
x23 : 9 + 3− 8 = 4
x31 : 11− 0− 5 = 6
• Como há coe�cientes negativos, a solução não é ótima e a variável que deveentrar na base é x12 por apresentar o menor coe�ciente negativo (−3)
• 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 que devedeixar a base é x32
• 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
73
• 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
• 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
7.4 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 ou dummy)cujos custos unitários de transporte sejam todos zero, independente daorigem; e com demanda igual à diferença entre o total ofertado e o totaldemandado.
• Demanda maior que oferta (∑i ai <
∑j bj):
Introduzir uma fonte de oferta fantasma (fonte dummy), com custos uni-tários zero para todos os destinos, e com oferta igual à diferença entre ototal demandado e o total ofertado.
74
7.5 Exercícios
1. Busque a solução do problema 3 de transporte anteriormente (MG Auto).
2. Considere que um produto é fabricado em 3 unidades F1, F2, F3, sendoposteriormente estocado em 4 depósitos D1, D2, D3 e D4. As capacidadesfabris são a1 = 40, a2 = 80 e a3 = 110, respectivamente para F1, F2 e F3.Nos depósitos devem se atender as demandas: b1 = 20, b2 = 30, b3 = 100e 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
Faça a modelagem do problema, e em seguida, usando o método stepping-stone.
3. Determine a solução do exemplo da construção da rodovia visto anteri-ormente, substituindo as desigualdades por igualdades nas restrições deoferta.
4. Resolva o exercício 2 de modelagem visto anteriormente, recorrendo aospontos dummy apropriados.
Referências
1. ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H.Pesquisa operacional: para cursos de engenharia. Rio de Janeiro: ElsevierBrasil, 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: CulturaAcadê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 da Profa.Alane A. Silva (UFPE).
Adaptações: Renato Pimentel, FACOM/UFU
75
8 Problema de transbordo
Introdução
• Em determinadas situações, podem-se usar localidades intermediárias en-tre a origem e o destino dos produtos a serem transportados
� Tais localidades são denominadas de transbordo;
� Podem representar, por exemplo, depósitos ou centros de distribuiçãoregionais;
� Problemas de transporte contendo estes pontos intermediários sãochamados de problemas de transbordo.
8.1 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.
� A quantidade transportada de cada unidade de transbordo aos mer-cados consumidores deve ser igual a que chega à mesma dos centrosde produção. Logo, deve-se adicionar o modelo de transporte umarestrição ∑
i
xij =∑k
xjk
para cada unidade de transbordo j.
1
2
j
3
4
5
x1j + x2j = xj3 + xj4 + xj5 .
76
Exemplo
• (ARENALES, 2006) Considere uma empresa de bebidas com 2 centros deprodução (Araraquara e S. José dos Campos, com um suprimento de 800e 1 000 unidades, respectivamente) e 3 mercados consumidores principais� S. Paulo, Belo Horizonte e R. de Janeiro, com demandas respectivas de500, 400 e 900 unidades.
• A empresa dispõe de 2 depósitos para abastecer tais mercados, localizadosem Campinas e Barra Mansa. Suponha que os mercados sejam abastecidossomente a partir de tais depósitos.
Os custos unitários de transporte de cada centro de produção para cadadepósito, e de cada depósito para cada mercado consumidor é dado pelastabelas que seguem.
• 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
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 .
77
Referências
1. ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H.Pesquisa operacional: para cursos de engenharia. Rio de Janeiro: ElsevierBrasil, 2006.
Os materiais de parte desta seção foram gentilmente cedidos por Paulo H. R.Gabriel (FACOM/UFU). Material desenvolvido com base no trabalho da Profa.Alane A. Silva (UFPE).
Adaptações: Renato Pimentel, FACOM/UFU
9 Problema de designação
Introdução
• Um caso especial do modelo de transportes é aquele em que cada origemtem uma unidade disponível e cada destino requer, também, uma unidade.
• Por exemplo:
� Escalar vendedores para pontos de venda;
� Distribuir atividades entre membros de uma equipe;
� Alocar máquinas para resolver diferentes tarefas.
9.1 Modelagem
ExemploDeseja-se designar quatro operários para quatro tarefas, de maneira que o nú-mero total de homens-hora seja mínimo. Cada homem desempenha cada tarefaem um determinado número de horas, conforme indicam os dados da matriz decustos 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
• Diferente dos problemas de transporte tradicionais, temos apenas 1 naorigem e 1 no destino.
• Assim, pelas arestas (�caminhos�) devemos apenas transferir uma ou ne-nhuma �carga�.
• Logo, nossa variável de decisão pode assumir apenas dois valores: 0 ou 1.
78
• De�nimos, então:
xij =
{1, se a tarefa i for atribuída ao operário j;
0, caso contrário.
• 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}
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}
9.2 Resolução algébrica
Algoritmo de Designação
• Devido às suas particularidades, a resolução do problema de designaçãotorna-se complexa por meio do método simplex.
• De fato, não temos mais variáveis de decisão contínuas, mas discretas
79
� Somente valores inteiros válidos, mais especi�camente, somente 0 ou1.
• No entanto, existe um método bastante e�ciente (baseado no método step-ping 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.
� No modelo de designação, o número de origens deve ser igual aonúmero de destinos � Matriz quadrada;
� Caso isso não ocorra, devemos construir origens ou destinos auxilia-res, com custo de transferência zero.
Passos do Método Húngaro
1. Subtrair de cada linha seu menor valor; em seguida fazer o mesmo comas colunas; cada linha e cada coluna deverá, então, apresentar pelo menosum 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 um zerodisponível; cada designação efetuada invalida os outros zeros na linha e nacoluna da célula designada; se a designação se completa, o problema estáresolvido.
3. Se não estiver resolvido, devemos:
(a) Cobrir os zeros da tabela com o menor número de traços � horizontaise verticais � possível;
(b) Subtrair o menor valor dentre os números não cobertos, de todos oselementos da tabela;
(c) Retornar ao item (2).
Exemplo
• Para a matriz de custos do exemplo anterior:10 12 15 16
14 12 13 18
10 16 19 15
14 12 13 15
• Subtraindo o menor elemento das linhas (respectivamente: 10, 12, 10, 12):
0 2 5 6
2 0 1 6
0 6 9 5
2 0 1 3
80
• Subtraindo o menor elemento das colunas (respectivamente: 0, 0, 1, 3):0 2 4 3
2 0 0 3
0 6 8 2
2 0 0 0
• Designando nos zeros de linhas ou colunas (de preferência, linhas ou colu-nas com apenas um zero) e anulando os outros zeros:
0 2 4 3
2 0 X 3
X 6 8 2
2 X X 0
• Não encontramos uma solução ótima, pois a terceira linha não apresentauma designação válida.
• 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 3
6 8 2
)cujo menor valor é 2
• Subtraímos 2 de toda matriz resultante:(0 2 1
4 6 0
)• E �recolocamos� essa matriz na original:
0 0 2 1
2 0 0 3
0 4 6 0
2 0 0 0
(note que os valores que havíamos eliminado não são modi�cados)
81
• Finalmente, designando novamente nos zeros de linhas ou colunas (depreferência, linhas ou colunas com apenas um zero) e anulando os outroszeros:
0 X 2 1
2 0 X 3
X 4 6 0
2 X 0 X
• Como resultado, temos: x11 = 1, x22 = 1, x34 = 1, x43 = 1, ou seja:
� Tarefa 1 é atribuída ao Operário 1
� Tarefa 2 é atribuída ao Operário 2
� Tarefa 3 é atribuída ao Operário 4
� Tarefa 4 é atribuída ao Operário 3
• Os demais valores de xij são nulos
9.3 Exercícios
1. (TAHA, 2008) Os três �lhos de Joe Klyne � John, Karen e Terri � queremganhar algum dinheiro para gastar durante uma excursão da escola. O Sr.Klyne escolheu três tarefas para seus �lhos: 1) cortar grama; 2) pintar aporta da garagem; e 3) lavar os carros da família. Para evitar concorrênciaentre os �lhos, ele pediu que cada um apresentasse propostas fechadas doque fosse considerado um pagamento justo para realizar cada uma dastarefas. Ficou combinado que os três concordariam com a decisão do paisobre quem executaria qual tarefa. A tabela a seguir resume as propostasrecebidas, em $:
Cortar Pintar LavarJohn 15 10 9Karen 9 15 10Terri 10 12 8
Como o Sr. Klyne deve designar as tarefas?
2. Um treinador precisa formar um time de nadadoras para competir emuma prova olímpica de 400 metros medley. As nadadoras apresentam asseguintes médias de tempo (em segundos) em provas individuais de 100metros, em cada estilo:
Livre Peito Borboleta CostasFlor 54 54 51 53Gabriela 51 57 52 52Teresa 50 53 54 56Tieta 56 54 55 53
82
Modele esse problema e resolva-o pelo método húngaro.
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 da Profa. AlaneA. Silva (UFPE).
Adaptações: Renato Pimentel, FACOM/UFU
Parte IV
Otimização em redes
10 Introdução a problemas em redes
Aplicações tradicionaisProblemas 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 a satisfazerrequisitos de oferta e demanda em diferentes locais;
• Programar atividades de um projeto.
Algumas de�nições
1. Um grafo ou rede é um conjunto de nós ou vértices conectados ou nãopor arestas (também chamadas arcos ou ramos), que representam algumaforma de relacionamento entre os mesmos.
• As arestas podem conter um peso (valor numérico) associado, repre-sentando uma grandeza associado ao relacionamento dos 2 nós queinterliga (ex.: a distância entre os nós).
Notação: (N,A), onde N é o conjunto de nós e A é o conjunto de arestas.
83
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
2. Todo grafo possui um �uxo associado às suas arestas. A aresta é dirigidaou orientada se permitir o deslocamento somente numa direção. Ex.: nografo visto existe �uxo do nó 1 para o nó 2, mas não vice-versa. A rede édirigida (dígrafo) se todas as suas arestas forem dirigidas.
3. Caminho: sequência de arestas distintas que ligam 2 nós quaisquer darede. Um caminho forma um ciclo ou loop se conectar um nó a si mesmo,passando por outros nós. Ex.: (2, 3), (3, 4) e (4, 2) formam um ciclo.
4. Rede conectada: rede onde todos os pares de nós são conectados por umcaminho (como no exemplo visto).
Exemplo clássico
Pontes de Königsberg, PrússiaVisitar todas as quatro partes A, B, C e D da cidade (atual Kaliningrado, naRússia), voltando ao ponto de partida e passando apenas uma vez por cada umadas sete pontes (a a g) sobre o Rio Prególia.
• Leonhard Euler (séc. XVIII): não há solução possível.
84
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 por todosos outros nós sem passar mais de uma vez por uma mesma aresta.
11 Problema do menor caminho
• Um dos problemas mais comuns em grafos: determinar o menor caminho(ou o de menor custo) entre 2 nós.
• Problema bastante comum em aplicações práticas.
Exemplos
• Entrega de uma mercadoria do depósito de uma fábrica até o endereço deum cliente : Qual o menor caminho a percorrer?
• Pode ser modelado como problema de otimização em redes.
� Nós correspondem às esquinas das ruas � esquinas interligadas porarestas.
� 2 nós para o depósito (A) e o endereço do cliente (B).
� Qualquer caminho interligando A e B é um caminho real pela cidade.
� Se o peso de cada aresta corresponder a distância entre esquinas, ocomprimento do caminho é a soma dos pesos das arestas entre A eB.
• (ARENALES, 2006) Vendedor se desloca de São Paulo a Fortaleza paralevar 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 principais rodovias� e as arestas, portanto, os trechos de rodovia entre dois nós � é possívelde�nir o peso de cada aresta como sendo o custo líquido esperado no trecho.
85
• Custo líquido: custo das despesas rodoviárias (combustível, pedágios, ma-nutençã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� (me-nor custo líquido possível) entre os nós correspondentes às duas cidades.
Outras situações podem ser representadas pelo problema do menor cami-nho.
• (TAHA, 2008): A RentCar está desenvolvendo uma política de reposiçãopara sua frota de carros considerando uma projeção de planejamento de4 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 no máximotrês anos.
• A tabela a seguir dá o custo de reposição em função do ano que o carrofoi 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 800
2 4 300 6 200 8 700
3 4 800 7 100 −4 4 900 − −
• O problema pode ser formulado como um grafo onde os nós 1 a 5 repre-sentam os anos 1 a 5. As arestas a partir do nó 1 podem chegar somenteaos nós 2, 3 e 4 porque o carro pode operar entre 1 e 3 anos, e assim pordiante. O peso de cada aresta corresponde ao custo de reposiçã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.
86
11.1 Formulação matemática
• Problema de encontrar o caminho mais curto entre o nó 1 e o nó n6 deum grafo G = (N,A), onde N = {1, 2, . . . , n}: caso de problema detransbordo, com única origem no nó 1, e único destino o nó n. Demais:todos de transbordo.
• 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
� S(j), P (j) são, respectivamente, o conjunto dos sucessores e prede-cessores de um nó j.
• xij = 1 indica que a aresta de i a j faz parte do menor caminho entre 1 en;
• xij = 0 indica que a mesma não faz parte.
• A 1a. restrição está relacionada ao nó de origem 1, indicando que o menorcaminho 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 seus antecessores.
• As demais n−2 restrições � dos nós intermediários � indica que no menorcaminho apenas uma aresta chegará e uma aresta sairá de cada um dosmesmos (os dois somatórios se igualam a 1).
6Sem perda de generalidade, formulação pode ser estendida para o problema de menorcaminho entre dois nós quaisquer.
87
• Retornando ao exemplo anterior (da reposição de carros):
minC = 4 000x12 + 5 400x13 + · · ·+ 4 900x45
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
• Na solução ótima (menor caminho):
x13 = x35 = 1,
x12 = x23 = x24 = · · · = x45 = 0,
C = 5 400 + 7 100 = 12 500
• Num problema pequeno (grafo com poucos nós/poucas arestas), o menorcaminho pode ser obtido rapidamente.
• Entretanto, muitos problemas envolvem um grande número de possibili-dades
• O caminho é a implementação de algoritmos para resolução do problema,tais como:
1. Algoritmo de Dijkstra;
2. Algoritmo de Floyd.
11.2 Algoritmo de Dijkstra
• Caminho mais curto entre um nó de origem especí�co e qualquer outronó.
• 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.
88
• 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 .
� O rótulo do nó inicial é [0,−], já que este não possui nenhum prede-cessor.
� Os rótulos podem ser temporários � podem ser modi�cados, se pos-sível achar rota melhor � e permanentes.
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:
(a) 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] quandoui + cij < uj .
(b) 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çãoi.
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 (último rotuladopermanentemente):
89
Nó Rótulo Condição1 [0,−] Permanente2 [0 + 100, 1] = [100, 1] Temporário3 [0 + 30, 1] = [30, 1] Temporário
• 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.
• 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 um caminhomais 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.
• 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 agora rótulodo nó 2 passa a ser permanente.
• Único nó com rótulo temporário: 5.
� Como não há arestas partindo do nó 5, seu rótulo se torna perma-nente, e o algoritmo se encerra.
90
• O caminho mais curto entre o nó 1 e qualquer outro nó da rede é determi-nado começando do nó de destino desejado e percorrendo a rota 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.
11.3 Exercício
(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
91
11.4 Algoritmo de Floyd
• Também chamado de Floyd-Warshall
• Mais geral que Dijkstra:
� 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.
� Inicialmente, entrada (i, j) dá o peso cij da aresta entre i e j, casoexista; ou ∞ caso contrário.
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
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
... −
92
� Ou seja, s(0)ij =
{j, i 6= j;
não de�nido, i = j.
• Etapa geral k (k = 1, . . . , n): Atualização da matriz de distâncias, deDk−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:
� Em Dk: d(k)ij = d
(k−1)ik + d
(k−1)kj .
� Em Sk: s(k)ij = k.
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 j
2. A partir de Sn, determine o nó intermediário k = sij , que dá comoresultado a rota i→ k → j:
� Se sik = k e skj = j, pare (todos os nós intermediários foramencontrados);
� Senão, repita o procedimento entre os nós i e k e entre os nós ke j.
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 os sen-tidos. Somente não há ligação direta do nó 5 para o nó 3.
• Iteração 0: matrizes D0 e S0.
93
D0 =
− 3 10 ∞ ∞3 − ∞ 5 ∞10 ∞ − 6 15
∞ 5 6 − 4
∞ ∞ ∞ 4 −
S0 =
− 2 3 4 5
1 − 3 4 5
1 2 − 4 5
1 2 3 − 5
1 2 3 4 −
• Iteração 1: k = 1⇒ Linha pivô 1 e coluna pivô 1 (sombreadas em D0).
Nas operações triplas, os únicos elementos atualizados são d23 e d32 (des-tacados 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 5
1 − 1 4 5
1 1 − 4 5
1 2 3 − 5
1 2 3 4 −
• Iteração 2: k = 2⇒ Linha pivô 2 e coluna pivô 2 (sombreadas em D1).
Nas operações triplas, os únicos elementos atualizados são d14 e d41 (desta-cados 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 15
8 5 6 − 4
∞ ∞ ∞ 4 −
S2 =
− 2 3 2 5
1 − 1 4 5
1 1 − 4 5
2 2 3 − 5
1 2 3 4 −
• Iteração 3: k = 3. Atualizando-se os itens em destaque nas matrizes D2 eS2, obtém-se D3 e S3:
D3 =
− 3 10 8 25
3 − 13 5 28
10 13 − 6 15
8 5 6 − 4
∞ ∞ ∞ 4 −
S3 =
− 2 3 2 3
1 − 1 4 3
1 1 − 4 5
2 2 3 − 5
1 2 3 4 −
94
• Iteração 4: k = 4. Atualizando-se os itens em destaque nas matrizes D3 eS3, obtém-se D4 e S4:
D4 =
− 3 10 8 12
3 − 11 5 9
10 11 − 6 10
8 5 6 − 4
12 9 10 4 −
S4 =
− 2 3 2 4
1 − 4 4 4
1 4 − 4 4
2 2 3 − 5
4 4 4 4 −
• Iteração 5: k = 5 (linhas e coluna em destaque em D4). Porém, nenhumamelhoria é adicional.
• Mesmo que modi�cações fossem necessárias para k = 5, esta seria a últimaiteração, pois o grafo possui 5 nós.
• As matrizes D4 e S4 contêm tudo que precisamos para determinar o ca-minho ótimo entre 2 nós quaisquer do grafo.
• Exemplo: nó 1 ao nó 5:
� De D4: custo ótimo 12 � menor distância, dada por d(4)15 .
� 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.
11.5 Exercícios
1. (TAHA, 2008) Use o algoritmo de Floyd para determinar, a partir doexemplo anterior, as distâncias mais curtas:
(a) Do nó 5 ao nó 1;
(b) Do nó 3 ao nó 5;
(c) Do nó 5 ao nó 3;
(d) Do nó 5 ao nó 2;
95
2. (TAHA, 2008) A empresa de telefonia Tell-All atende seis áreas. As dis-tâncias via satélite estão no grafo abaixo. Quais as rotas mais e�cientesque devem ser estabelecidas entre quaisquer duas áreas?
3
2
4
6700
200
200
5
300700
600300
100
500
400
1
Referências
1. ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H.Pesquisa operacional: para cursos de engenharia. Rio de Janeiro: ElsevierBrasil, 2006.
2. TAHA, H. Pesquisa operacional. 8a. ed. São Paulo: Prentice Hall, 2008.
12 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 de umnó a outro do grafo.
• Única origem e único destino.
Exemplos
• Qual a capacidade máxima de produção de um determinado bem por umaempresa?
� Roteiros distintos durante o processo
� Diferentes centros de fabricação, cada qual com uma certa capacidadeinstalada.
• Redes de tubulações. Exemplo, de petróleo:Qual a capacidade máxima darede entre poços e re�narias?
� Produto bruto (petróleo cru) transportado de poços para re�narias.
� Estações intermediárias de impulsores e de bombeamento instaladas
� Cada segmento tem uma taxa de descarga máxima de �uxo.
96
� Segmento pode ser unidirecional ou bidirecional, dependendo do pro-jeto.
• (TAHA, 2008) Uma rede típica para o problema do escoamento do petróleoé dada pelo grafo abaixo:
2
1
3
4
5
6
9
7
8
Origem Destino
Poços Impulsores Re�narias
• Representação: a solução do problema exige o acréscimo de uma origemúnica e um destino único, usando as arestas unidirecionais de capacidadein�nita tracejadas no grafo.
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→ j ej → i.
• Para eliminar ambiguidades, pode-se representar tais capacidades numgrafo, colocando-se
C̄ij próximo ao nó i e
C̄ij próximo ao nó j, como na �gura abaixo.
i j
C̄ij C̄ji
Cortes
CorteConjunto de arestas que, se eliminado do grafo, causa um rompimento total do�uxo entre o nó de origem e o nó de destino.
• A capacidade do corte corresponde à soma das capacidades de suas arestas;
• O corte com menor capacidade determina o �uxo máximo da rede.
� Devem ser considerados todos os cortes possíveis.
97
Exemplo
• Considere o grafo que segue:
1
2 3
4
5
1030
20
30
400
0010
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 = 602 (1, 3), (1, 4), (2, 3), (2, 5) 30 + 10 + 40 + 30 = 1103 (2, 5), (3, 5), (4, 5) 30 + 20 + 20 = 70
• Pelos cortes ilustrados, conclui-se que o �uxo máximo da rede não podeexceder 60 unidades.
• Para determinar o �uxo máximo, entretanto, todos os cortes precisam serencontrados.
ExercícioEncontre no grafo anterior 2 cortes adicionais, e determine sua capacidade.
12.1 Formulação matemática
• Seja o problema de se determinar o �uxo máximo entre o nó 1 e o nó nde um grafo G(N,A) com n nós.
� Sem perda de generalidade, pois a interpretação se estende paraquaisquer dois nós em questão.
• (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
98
∑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 .
� S(i) e P (i) são o conjunto dos sucessores e predecessores do nó i.
• Isto é, deseja-se determinar xij para toda (i, j) ∈ E que maximize o �uxoentre origem e destino.
• Reescrevendo-se as restrições técnicas, com as variáveis do lado esquerdo:
∑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,
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 mesma forma, P (1) =P (1) + {n}, e podemos reescrever o problema como
maxxn1
sujeito a
∑j∈S(i)
xij −∑
k∈P (i)
xki = 0, i = 1, . . . , n
0 ≤ xij ≤ C̄ij , ∀(i, j) ∈ E .
99
Exemplo
• Representando a aresta de retorno no grafo visto anteriormente, temos:
1
2 3
4
5
1030
20
30
400
0010
20
205
0
000
0
C̄51
Modelagem do problema de �uxo máximo:
maxx51
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
Formulação alternativa
• TAHA (2008) propõe uma formulação mais simples, dispensando a ideiada aresta de retorno.
• Basta considerar o problema de maximização de uma das duas funçõesobjetivo:
1. z1 =∑j∈S(1) x1j (maximização da saída do nó de origem), ou
2. 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ão con-sideradas.
100
• As duas funções objetivo acima são equivalentes.
• As duas formulações (com e sem aresta de retorno) são equivalentes:
� No exemplo visto, basta isolar x51 na restrição do nó de origem (ounó de destino), e na função objetivo.
Por exemplo, considerando-se o problema de maximizar a saída do nó 1:
maxx12 + 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
12.2 Algoritmo de �uxo máximo
• (TAHA, 2008) Encontrar rotas de passagem com �uxo líquido positivoentre nós de origem e destino
• Cada caminho compromete parte ou toda a capacidade das suas arestasao �uxo do grafo.
• Por exemplo, numa aresta (i, j) com capacidade inicial (C̄ij , C̄ji) (a má-xima), quando parte desta capacidade é usada numa rota de escoamento,temos uma capacidade residual (cij , cji).
� À medida que as arestas são reutilizadas, os valores cij , cji são atua-lizados.
• 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.
101
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 = 1 e passe paraa etapa seguinte.
Etapa 2 : seja S̄(i) o conjunto dos sucessores do nó i ainda não rotulados,ligados a ele por arestas com capacidades residuais não nulas (ainda podemser 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.
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 passagem foiobtida. Siga para a etapa 5.
• Caso contrário, faça i = k e retorne à etapa 2.
Etapa 4 : (Percorrer a rota inversa).
• Se i = 1, nenhuma rota de passagem é possível: prossiga para etapa6.
• Caso contrário, seja r ∈ P (i) o nó rotulado imediatamente antes donó i. Elimine i temporariamente dos nós adjacentes a r, determinei = r e volte à etapa 2.
Etapa 5 : (Capacidades residuais).
De�na os nós da p-ésima rota de passagem do nó origem 1 ao nó destinon 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 dadireção do �uxo e aumentada de fp na direção contrária:
102
• (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. Determine i = 1 e volte àetapa 2 para tentar uma nova rota de passagem.
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).
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
� Na rede (a), �uxo máximo é 5, e as arestas que de�nem a rota têmseu �uxo alterado de (5, 0) para (0, 5).
� O mesmo vale para a rota em (b), e, após as alterações, não há maisrota possível.
• O que houve de (b) para (c) foi o cancelamento de um �uxo anteriormentecomprometido na direção 2→ 3.
• O algoritmo �lembra� que este �uxo foi previamente usado pois aumenta-mos a capacidade na direção inversa de 0 para 5 (pela etapa 5).
103
Exemplo
• Considere a rede de 5 nós vista previamente, no exemplo dos cortes:
1
2 3
4
5
10
30
20
30
40
0
0
010
20
205
0
0
0
0
• Determinar o �uxo máximo da rede.
Iteração 1Inicialmente, iguale as capacidades residuais iniciais às capacidades iniciais
(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 [∞,−]. Determine i = 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.
Etapa 5 : Rota determinada pelo caminho inverso a partir do nó de destino 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 rota N1 são
(c13, c31) = (30− 20, 0 + 20) = (10, 20)
(c35, c53) = (20− 20, 0 + 20) = (0, 20)
104
Rota encontrada na iteração 1 (capacidades residuais ainda não ilustradas).
1
2 3
4
5
10
30
20
30
40
0
0
010
20
205
0
0
0
0
f1 = 20
[∞,−]
[30, 1]
[20, 3]
Iteração 2
Etapa 1 : Determine a1 =∞, e rotule nó 1 com [∞,−]. Determine i = 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.
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)
105
Rota encontrada na iteração 2 (capacidades residuais ainda não ilustradas).
1
2 3
4
5
10
10
20
30
40
0
0
2010
0
205
0
0
0
20
f2 = 10
[∞,−]
[20, 1]
[20, 4]
[40, 2]
[10, 3]
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.
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)
106
Rota encontrada na iteração 3 (capacidades residuais ainda não ilustradas).
1
2 3
4
5
10
10
10
30
30
10
10
200
0
1015
0
10
0
20
f3 = 10
[∞,−]
[10, 1]
[30, 2]
���XXX[30, 2]
Iterações 4 a 6
ExercícioEncontre as rotas N4 e N5 (ambas com �uxo 10)7.
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
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→ 57Nó 3 está novamente à disposição para as rotas N4 e N5
107
12.3 Exercícios
1. Determine a capacidade excedente de todas as arestas do exemplo, apósa 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.
Referências
1. ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H.Pesquisa operacional: para cursos de engenharia. Rio de Janeiro: ElsevierBrasil, 2006.
2. TAHA, H. Pesquisa operacional. 8a. ed. São Paulo: Prentice Hall, 2008.
108
