Apostila

Transcrição

Apostila

Programação Linear – PL
Luiza Amalia Pinto Cantão
[email protected]
Felipe Sanches Stark
[email protected]
Sumário
1
Introdução à Pesquisa Operacional
4
1.1
Otimização (Cálculo Diferencial) e Sistemas de equações (Álgebra Linear) na PO . . . . . . . . . .
5
1.2
Metodologia da PO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.3
Tipos básicos de modelo de PO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.3.1
1.4
1.5
2
Solução em PO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.2 Mais do que matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Solução Geométrica ou gráfica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.1
Introdução - Descrevendo um problema anterior
1.4.2
Tipos de solução e visualização gráfica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Exercı́cios Propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Revisão Matemática
2.1
2.2
2.3
2.4
2.5
. . . . . . . . . . . . . . . . . . . . . . . 11
21
Equações lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.1
Solução de um Sistema de Equações Lineares . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.2
2.1.3
Operações elementares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Solução de Sistema de Equações Lineares, caso m = n . . . . . . . . . . . . . . . . . . . . 22
2.1.4
Método de Gauss-Jordan, caso m = n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1.5
Solução de Sistema de Equações Lineares, caso n > m . . . . . . . . . . . . . . . . . . . . 24
Mudança de Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.1
O Pivoteamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.2
Seleção das variáveis básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.3
Construção da Variáveis Básicas e Variáveis Artificiais . . . . . . . . . . . . . . . . . . . . 27
Espaços Vetoriais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.1
Definição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.2
Operações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.3
Combinação Linear de Vetores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.4
2.3.5
Dimensão de um Espaço Vetorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Base e Coordenadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.6
Posto (ra ) de uma matriz como um Conjunto de Vetores . . . . . . . . . . . . . . . . . . . 30
Conjuntos Convexos e Combinação Convexa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4.1
Conjunto Convexo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4.2
Combinação Convexa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4.3
Interpretação Geométrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4.4
Ponto Extremo de um Conjunto Convexo . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1
SUMÁRIO
3
SUMÁRIO
Método Simplex
3.1
Teorema Fundamental da Programação Linear
3.1.1
3.2
36
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Transição da solução gráfica para a solução algébrica . . . . . . . . . . . . . . . . . . . . 37
Método Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.1
Modelo de Programação Linear em forma de equação - Forma Padrão . . . . . . . . . . . 37
3.2.2
Forma Padrão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.3
Forma Canônica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.4
Conversão de desigualdades em equações com o lado direito não negativo
3.2.5
Como lidar com variáveis irrestritas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2.6
3.2.7
Variáveis Não Positivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Transformando o Problema de Maximização em Minimização . . . . . . . . . . . . . . . . 41
3.2.8
Princı́pios do Método Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2.9
Método Simplex na forma de quadros - Tableau Simplex . . . . . . . . . . . . . . . . . . . 46
. . . . . . . . . 39
3.2.10 Análise de Casos Especiais. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.11 Base Artificial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.2.12 O Método do M-Grande . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2.13 O Método das Duas Fases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3
3.4
4
Análise de Sensibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.3.1
Análise de Sensibilidade gráfica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.3.2
Análise de Sensibilidade algébrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Dualidade
4.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2
Definição do Problema Dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.3
4.2.1
Propriedades da Dualidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.2.2
Teoremas Fundamentais da Dualidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
Método Dual Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.3.1
4.4
5
69
Resumo do Método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
Métodos de Pontos Interiores
80
5.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.2
Notação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.3
Método Primal-Dual
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.3.1
A Trajetória Central . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.3.2
Estrutura Primal-Dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.4
Método de Redução de Potencial (RP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.5
Implementação de Algoritmos de Pontos Interiores . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.5.1
5.5.2
Solução Inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Critério de Parada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.5.3
Algoritmo Primal-Dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
2
SUMÁRIO
6
Programação Linear Inteira
91
6.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2
Algoritmo Branch-And-Bound (B&B) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
6.3
Problema do Caixeiro-Viajante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.4
Problema da Mochila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.2.1
6.5
7
SUMÁRIO
Resumo do algoritmo Branch-And-Bound (B&B) . . . . . . . . . . . . . . . . . . . . . . . 96
6.4.1
Mochila 0-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.4.2
Mochila Inteira . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.4.3
Múltiplas Mochilas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.4.4 Empacotamento de Mochilas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
O Uso de Excel e do lp solve para Problemas de Programação Linear
104
7.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.2
MS-Excel Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.3
lp solve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Referências Bibliográficas
111
3
CAPÍTULO
1
Introdução à Pesquisa Operacional
Histórico da Pesquisa Operacional
A Pesquisa Operacional (PO) é um ramo da ciência que cuida da criação de metodologias especı́ficas para
promover o gerenciamento de decisões. A origem da PO data da Segunda Guerra Mundial (1939-1945) e tem
relação com o esforço envolvido no perı́odo do conflito para otimizar o uso dos recursos. Como exemplos, temos
o estudo do radar (inventado em 1934 na Inglaterra) para a interceptação de aviões inimigos, estudos dentro das
divisões aéreas aliadas, para melhorar a manutenção e inspeção dos aviões, na escolha dos melhores modelos para
cada tipo de missão e no aumento da probabilidade de alvejar um submarino.
A evolução da PO se deu de forma rápida no pós-guerra, em paı́ses como Inglaterra e Estados Unidos. Em
1947, foi implantado o projeto SCOOP (Scientific Computation of Optimal Programs), no qual tinha por objetivo
a gestão aérea militar e contava com a participação do matemático George Dantzig. Durante o projeto SCOOP,
Dantzig desenvolveu um dos métodos primordiais para a resolução de problemas envolvendo a otimização linear:
o SIMPLEX. Com a publicação do método, a Programação Linear (PL) tornou-se a primeira técnica explı́cita,
permanecendo até hoje a mais fundamental das técnicas da PO.
Posteriormente houve surgimentos de sociedades cientı́ficas, como a americana ORSA (Operations Research
Society of America) fundada em 1953; sendo ao longo da década de 50 e 60 observado o crescimento no número
de grupos de pesquisas operacionais e suas aplicações tanto em setores públicos quanto privados ao redor do globo.
É por volta do fim da década de 60 que surgem as questões educacionais envolvendo a PO, principalmente no
tocante da maior publicação literária do assunto e na presença em cursos de pós-graduação. Nessa época aparece
a área de programação matemática, tendo como premissa casos de otimização de funções lineares sujeitos às
restrições lineares. No Brasil, a PO iniciou-se nessa década também. O primeiro simpósio de PO ocorreu em 1968
no ITA, em São José dos Campos, SP. Em seguida, foi fundada a SOBRAPO (Sociedade Brasileira de Pesquisa
Operacional) que publica o periódico Pesquisa Operacional há mais de 25 anos.
Atualmente, a PO tem sido chamada de ciência e tecnologia de decisão. O componente cientı́fico é ligado
às idéias e processos para modelar os problemas de tomada de decisão (objetivos e restrições da operação),
a matemática se enquadra aqui na medida em que os modelos para otimizar sistemas numéricos resultam de
inserções de dados nos modelos. A tecnologia compreende a relação software-hardware, podendo ser generalizada
como uma tecnologia da informação (armazenamento, comunicação e transmissão - tanto de dados inseridos nos
modelos de otimização quanto nos resultados obtidos).
4
Capı́tulo 1. Introdução à Pesquisa Operacional
PL
1.1 Otimização (Cálculo Diferencial) e Sistemas de equações
(Álgebra Linear) na PO
Ora, se a Pesquisa Operacional em seus primórdios históricos era sinônimo de Otimização, temos então uma
primeira ligação com o Cálculo Diferencial. Trata-se dos chamados Problemas de Valores de Máximos e Mı́nimos,
isto é, o ponto no qual a função tem sua imagem no maior e no menor valor possı́vel. O grande entrave na PO
é muitas vezes a mecanização de como tais problemas são passados, tornando a aprendizagem superficial e o
emprego de tais técnicas pouco intuitivo. Vejamos um exemplo simples de valores extremos, em particular o valor
mximo.
Exemplo 1. Considere que um fabricante de produtos de limpeza tenha de calcular qual a melhor maneira de criar
uma embalagem retangular com uma determinada altura h (constante) para que o volume seja máximo, isto é,
a área da base seja a maior possı́vel com um comprimento L de material (estipulado com base nos lucros e no
transporte), esse procedimento de otimização envolve redução de custos, resı́duos e impacto ao meio ambiente.
1. Primeiro, como trata-se de um retângulo, os lados opostos devem ter o mesmo tamanho, identificaremos a
largura de w e comprimento de l.
2. Com base na definição 2w + 2l = L, ou seja,
w +l =
L
2
(1.1)
3. Por serem dimensões fı́sicas da matéria, tanto w quanto l devem ser positivos. Como h é estabelecido pelo
fornecedor do fabricante, não entra nos cálculos do volume, pois se acharmos a maior área teremos o maior
volume para h.
4. A área é A = wl.
Nossa questão então é maximizar A sujeita a equação (1.1) e das restrições do item 3. Para tanto, devemos
proceder como um problema de valor máximo do cálculo:
• Como L é um número dado, pode ser tratado como constante, deste modo podemos deixar w em função de
l, ou vice-versa.
w +l =
L − 2l
L
=⇒ w =
2
2
• Portanto a região do domı́nio de w e l é a reta
w=
L − 2l
2
na qual a imagem está no plano z como a área A. Assim, da mesma maneira que deixamos w em função de
l, podemos deixar agora a área A em função apenas de l, substituindo o valor de w. Obtemos:
A=
L − 2l
2
l
Distribuindo l, temos:
A=
L. A. P. Cantão & F. S. Stark
Ll − 2l 2
2
5
PL
• Agora para achar um ponto máximo (ou mı́nimo) executamos a derivação
δA
=0
δl
1
δA
= (L − 4l)
δl
2
Portanto se
1
L
(L − 4l) = 0 =⇒ L = 4l =⇒ l =
2
4
Se
w +l =
L
2
Chegamos finalmente na solução (S):
L
4
w=
el=
L
4
• Concluı́mos que a maior área é obtida quando o retângulo é um quadrado de lado
V =
L
, e que seu volume
4
L2 h
16
O exemplo acima (Exemplo 1) é simples, contudo, grande parte dos problemas de PO envolve número maior
tanto de equações (e inequações) quanto de variáveis, incluindo restrições dos valores que as variáveis podem
assumir. Como no exemplo a seguir, trabalharemos muitos conceitos de Álgebra Linear (tratada na Programação
Linear) ao longo da formulação dos modelos e na obtenção das respostas. Nestes problemas, as variáveis e as
restrições podem estar envolvidas em desigualdades, ou seja: o problema torna-se cada vez mais complexo à medida
em que esse fenômeno, a ser modelado, sofre diversas influências importantes. Para efeito ilustrativo, podemos
tomar um sistema mais restrito e apenas interpretativo, vejamos então.
Exemplo 2. Uma empresa produz dois produtos, P e Q, em cada uma de suas fábricas, X e Y. Ao fabricar tais
produtos, os poluentes dióxido de enxofre (SO2 ), óxido nı́trico (NOx ) e material particulado (MP) são produzidos.
As quantidades de poluentes foram monitoradas e quantificadas ( em quilogramas) e estão dispostas pela matriz:
P
=
" SO2 NOx MP #
300 100 150
200
250
400
Produto P
Produto Q
O custo diário para remover cada quilograma de poluente é (em reais) dado pela matriz:
X

C
=
16

 14
30
Y

24

18 
20
Dióxido de Enxofre
Óxido nı́trico
Material Particulado
Qual o significado, por exemplo, do produto matricial de P.C ? Qual fábrica polui mais, isto é, gera mais efluente
e consequentemente tem seu tratamento encarecido?
6
PL
1.2 Metodologia da PO
A metodologia da PO segue etapas definidas como em qualquer projeto, podendo ser decomposto em 5 estágios
básicos segundo [14]:
1. Identificação do problema - “envolve definir o escopo do problema sob investigação. Essa função deve ser
executada por toda a equipe de PO” [14]. Em PO quanto mais complexo e multidisciplinar é um problema,
maior abrangência de conhecimento é necessária e por consequência uma equipe mais especializada. Nesta
etapa buscamos três elementos básicos:
(a) descrição das alternativas de decisão;
(b) determinação do objetivo de estudo;
(c) as limitações sobre as quais o modelo está imposto.
2. Construção do modelo -“implica uma tentativa de traduzir a definição do problema em relações matemáticas”[14]. Se o modelo for simples e se ajustar à um dos métodos padrões, como a programação
linear, então podemos chegar em soluções com os algoritmos disponı́veis. Já se o modelo for complexo, a
equipe pode simplificar a situação tendendo à uma abordagem heurı́stica ou de simulação. Em alguns casos,
ocorre a combinação dos modelos matemáticos, heurı́sticos e simuladores.
3. Determinação da solução do modelo -“é de longe a fase mais simples ... porque se baseia na utilização
de algoritmos”[14]. Neste estágio ocorre o que se chama de análise de sensibilidade, essencial quando os
parâmetros do modelo não podem ser aferidos com precisão.
4. Teste e validação da solução proposta -“verifica se o modelo proposto ... prevê adequadamente o comportamento do sistema em estudo” [14]. Em sistemas com uma base de dados histórica (p.e. pluviosidade
em uma região), o modelo é válido se, sob condições similares de entrada, reproduz relativamente bem as
saı́das anteriores. Porém, como geralmente a análise leva em conta os dados anteriores, o parecer tende a ser
favorável, o que exige cuidado com eventos futuros imprevisı́veis. Em sistemas sem base de dados, tende-se
a comparar o modelo com simulações.
5. Implementação da solução -“envolve a tradução dos resultados em instruções operacionais inteligı́veis ...
emitidas as pessoas que administrarão o sistema recomendado”[14].
1.3 Tipos básicos de modelo de PO
O uso de modelos é a essência da própria PO, ocorrendo quando há alta complexidade e elevado potencial de
retorno do investimento. Desta maneira, justifica-se a contratação de uma equipe de especialistas, alocação de
recursos disponı́veis e o desenvolvimento do projeto de PO.
A criação de um modelo implica em algo simbólico, que simplifica a realidade mediante o uso de relações
matemáticas de algumas variáveis envolvidas, porém mantém as essências de causa-efeito do problema estudado.
No que tange a PO, podemos ter vários exemplos clássicos de modelos, entre um dos mais básicos e interessantes
temos os problemas que envolvem misturas (rações, fertilizantes, concreto, alimentos, poluentes, entre outros).
Esses tipos de problemas consistem em combinação de materiais (naturais ou não) para gerar novos materiais ou
produtos com caracterı́sticas desejáveis, como é o caso por exemplo das misturas de massa de reboco (cal, areia,
cimento e água) ou de concreto (areia, brita, cimento e água), que em proporções diferentes ou com a adição de
alguma substância adquirem propriedades para um fim especı́fico, como acabamento e fundação, respectivamente.
7
PL
Figura 1.1: Estrutura básica envolvida na metodologia dos modelos da PO
Exemplo 3. Na implantação de um barragem de grande consumo de concreto, decidiu-se utilizar como fontes de
agregrados graúdos:
1. britas granı́ticas pelo desmonte (desagregação por explosivo) da rocha local;
(a) A composição granulométrica é: 10% (19-38 mm), 20% (38-76 mm) e 70% (76-152 mm)
(b) O custo é $6, 00/m3
2. seixos rolados disponı́veis nos vales próximos à barrragem;
(a) A composição granulométrica é: 5% (2.4-19 mm), 35% (19-38 mm) e 60% (38-76 mm)
(b) O custo é $7, 00/m3
3. pedra britada comercial
(a) A composição granulométrica é: 20% (2.4-19 mm), 78% (19-38 mm) e 2% (38-76 mm)
(b) O custo é $18, 00/m3
Por meio de um estudo prévio, chegou-se em uma faixa de composição granulométrica ideal, sendo:
• 10% da faixa de 2.4-19 mm
• 20% da faixa de 19-38 mm
O problema consiste em determinar as frações de cada fonte para a composição ideal, de forma a minimizar o
custo de produção do concreto. As variávies de decisão são:
x1 quantidade (m3 ) de britas granı́ticas.
8
PL
x2 quantidade (m3 ) de seixo rolado.
x3 quantidade (m3 ) de brita comercial.
Com isso o custo da mistura é dado por f (x1 , x2 , x3 ) = 6x1 + 7x2 + 18x3 .
Pelas restrições, custos e porcentagens de cada em cada fração , obtemos:
0.05x2 + 0.10x3 ≥ 0.10 Faixa (2.4-19 mm)
0.10x1 + 0.35x2 + 0.78x3 ≥ 0.20 Faixa (19-38 mm)
0.20x1 + 0.60x2 + 0.02x3 ≥ 0.35 Faixa (30-76 mm)
0.70x1 ≥ 0.35 Faixa (76-152 mm)
Os ingredientes utilizados produzem uma unidade de mistura, ou seja, x1 + x2 + x3 = 1, e, completando as
restrições, temos as condições de não negatividade das variáveis: x1 ≥ 0,x2 ≥ 0 e x3 ≥ 0. O modelo matemático
completo é dado por:
Minimizar
6x1
+
Sujeito a:
7x2
+
18x3
0.05x2
+
0.10x3
≥ 0.10
0.10x1
+
0.35x2
+
0.78x3
≥ 0.20
0.20x1
+
0.60x2
+
0.02x3
≥ 0.35
0.70x1
x1
+ x2
x1 ≥ 0
+ x3
x2 ≥ 0
≥
0.35
=
1
x3 ≥ 0
Outro exemplo comum é o de planejamento de produção por vários ciclos de tempo (meses,semanas e dias).Vejamos
um exemplo deste tipo:
Exemplo 4. Durante o próximo semestre, uma fabricante têxtil deve atender aos seguintes compromissos de sua
seção de malharia:
Jan.
Fev.
Mar.
4000 peças
2000 peças
5000 peças
Abr.
Mai.
Jun.
1000 peças
4000 peças
2000 peças
Tabela 1.1: Dados do Planejamento.
Ao final de dezembro, há 500 peças em estoque e a empresa só tem capacidade para produzir 3000 peças
mensais. Entretanto, usando horas extras, a empresa pode produzir até 600 peças a mais que sua capacidade
nominal.
O custo variável de produzir uma peça é de R$ 3 por peça, e o custo de produzir em horas extras é de R$ 3.4
por peça. Além disso, peças que ficam em estoque de um mês para outro provocam custo aproximado de R$ 0.25
por peça.
Monte um modelo linear que satisfaça a demanda, mas com minimização dos custos de produção.
A solução está em se definir xt , yt e et para t = 1:6, para indicarem respectivamente a produção nominal, em
horas extras, e estoque ao final de cada mês.
9
Min
Suj. a:
f (x) =
PL
3(x1
+···+
x6 )
+
3.4(y1
+···+
y6 )
+
0.25(e1
x1
+
y1
+
500
=
e1
+
4000
x2
+
y2
+
e1
=
e2
+
2000
x3
+
y3
+
e2
=
e3
+
5000
x4
+
y4
+
e3
=
e4
+
1000
x5
+
y5
+
e4
=
e5
+
4000
x6
+
y6
+
e5
=
e6
+
2000
xt
≤
3000
yt
xt ,
≤
yt ,
600
et
≥
0
para
t
=
1:6
+ · · · + e6 )
Problemas de transporte ou alocação de recursos em determinados percursos também são alvos comuns de
estudos da PO.
Exemplo 5. Considere uma companhia distribuidora de bebidas que tem 2 centros de produção (m = 2) - Araraquara e São José dos Campos - e 3 mercados consumidores principais (n = 3) - São Paulo, Belo Horizonte e Rio
de Janeiro. O custo unitário (cij ) de se transportar uma unidade do produto de cada centro de produção a cada
mercado consumidor, bem como as demandas (bj ) de cada mercado e a quantidade disponı́vel do produto em cada
centro de produção (ai ) no próximo perı́odo, são dados pela tabela abaixo.
Centro de Produção
Araraquara (1)
S. J. Campos (2)
Demanda(mercado)
Mercado
São Paulo(1)
4
11
500
Belo Horizonte(2)
2
7
400
Rio de Janeiro(3)
5
4
900
Suprimento(ai )
800
1000
Tabela 1.2: Dados da produção, distribuição e consumo.
Como ficaria o sistema deste problema se quisessemos minimizar o custo do processo?
1.3.1 Solução em PO
Como dito no final do item anterior, nem sempre um problema tem uma solução possı́vel, em contrapartida,
surgem problemas que aceitam diversos conjuntos de valores como solução do sistema. Deste modo devemos
expressar algumas terminologias importantes quanto ao assunto solução, como:
1. Solução - Qualquer especificação de valores, dentro do domı́nio da função objetivo f(x), para as variáveis de
decisão, independentemente de se tratar de uma escolha desejável ou permissı́vel.
2. Solução viável - solução que satisfaz todas as restrições do problema.
3. Solução ótima - é aquela que permite a ocorrência do melhor valor da f(x), isto é, maximiza ou minimiza
seu valor de acordo com o desejado. Pode ser única ou não.
1.3.2 Mais do que matemática
Até agora, a PO parece apenas uma aplicação matemática que tenta modelar numericamente o mundo real por
meio de aproximações de suas variáveis, contudo a pesquisa envolve muito do conhecimento do decisor.
10
PL
Não é raro encontrar a PO como tema de trabalho de uma equipe inteira de profissionais de diversas áreas (matemáticos, engenheiros, biólogos, administradores, economistas, sociólogos e até psicólogos) pois, a complexidade
ou mesmo a incerteza envolvida na situação é tamanha que requer um tratamento sobre divesos pontos de vista.
A exemplo disso, podemos considerar um acontecimento em um prédio comercial. As pessoas começaram
a reclamar na gerência sobre o fato de esperarem muito tempo o elevador instalado no empreendimento. A
construção de mais um elevador seria inviável, o mesmo poderia ser dito de se aumentar a velocidade do elevador
(comprometendo a estrutura da construção ou a segurança das pessoas à bordo do elevador).
O que fazer então?
A resposta é simples! Um dos profissionais contratados foi um psicólogo. Este sugeriu que fossem espelhadas
as paredes externas da porta de cada andar do elevador, pois com isso as pessoas passariam mais tempo se vendo
diante do espelho e vendo os outros que estavam esperando. Com essa ação, à primeira vista estranha, a gerência
do prédio parou de receber tantas reclamações.
Sendo assim, afirmamos que deve haver atenção quando o assunto do problema é algo que envolve opiniões
humanas ou variáveis muito incertas. Neste caso, pode ser necessário o auxı́lio de funções não lineares (função
objetivo e/ou restrições, nos levando a aplicação de técnicas da Programação Não Linear), ou mesmo do emprego
de outras teorias, como a Teoria Fuzzy, por exemplo.
1.4 Solução Geométrica ou gráfica
1.4.1 Introdução - Descrevendo um problema anterior
Ao se trabalhar com equações lineares um dos modos de visualizar a solução é o de criar graficamente as retas
que cada equação representa, sobretudo em equações de problemas pequenos (duas variáveis). Deste modo, as
intersecções das equações são os possı́veis pontos de solução, vejamos o Exemplo 1 do inı́cio deste capı́tulo, se
fizermos a reta de w em função de l, teremos uma reta no plano xy (figura 1.2).
Figura 1.2: Gráfico de w versus l (ou l versus w )
11
PL
Sabemos então que a solução está sobre a reta, porém, não podemos afirmar quais valores fornecem a solução
do sistema. Contudo, temos a função área A = w l no plano z, devemos então com o auxı́lio de um programa
computacional “chutar ” os valores de w e l para então gerar o gráfico de A versus l e A versus w, com isso vemos
uma parábola (figura 1.3).
Figura 1.3: Gráfico de A versus l (ou A versus w )
Pela figura 1.3, fica evidente que a solução de valor mais alto dentro do espaço da solução é próximo à metade
do valor possı́vel das variáveis, tanto para w quanto l. Este valor é 0.25, ou 25% de L.
Devemos ressaltar que neste caso, como a função objetivo era uma variável multiplicada pela outra, o gráfico
resultante foi uma parábola, o que não configura em um caso de otimização linear (Programação Linear), sendo
apenas uma maneira ilustrativa sobre o uso gráfico dentro dos modelos de Pesquisa Operacional.
1.4.2 Tipos de solução e visualização gráfica
Nesta subseção estão apresentados, e resolvidos de forma gráfica, alguns exemplos de Programação Linear contendo duas variáveis. Apesar de ser restrita a problemas pequenos, a solução gráfica oferece elementos facilitadores
para a compreensão dos procedimentos do método que será exposto nos próximos capı́tulos.
Ilustremos as seguintes situações: solução única, solução múltipla, solução ilimitada e solução infactı́vel a partir
do texto de [11].
Solução única
Exemplo 6. Seja o problema de PL:
12
PL
Maximizar 2x1
+
3x2
Sujeito a:
x1
+
2x2
≤ 8
(a)
−2x1
+
3x2
≤ 5
(b)
x1
+ x2
≤ 6
(c)
x1 ≥ 0
x2 ≥ 0
(d)
Figura 1.4: Solução única
Na ilustração, cada restrição está graficamente representada com sua respectiva reta (a),(b) e (c). Como são
inequações, os pontos que as satisfazem definem semi-espaços, isto é, a região acima ou abaixo da reta, à direita
ou à esquerda da reta. Por outro lado, a restrição (d) informa que a região está no primeiro quadrante do plano.
Logo, tem-se a região factı́vel (região escurecida da figura 1.4).
Tomando-se a função objetivo como um tracejado, se a deslocarmos na região solução desde o vértice (0,0)
teremos um máximo no vértice (4,2).
Identificação do ponto ótimo
Uma vez que a região factı́vel foi encontrada, o ponto ótimo do exemplo 6 pode ser encontrado de duas maneiras
equivalentes, de acordo com a figura 1.5
Temos então, na situação (a) foram traçadas duas retas paralelas à função objetivo, com valores de Z = 9 e
Z = 12, respectivamente e averiguamos em qual direção a função objetivo cresce, isto é, no mesmo sentido dos
eixos no primeiro quadrante.
Já na segunda situação (b), encontramos o gradiente da função (derivadas parciais em cada variável), o vetor
(2, 3), que é exatamente normal à função objetivo. O vetor normal indica a direção de crescimento da função.
Analogamente ao caso (a), a função é deslocada até alcançar o(s) ponto(s) da região viável com maior valor de Z.
Solução múltipla
Exemplo 7. Seja o problema apresentado anteriormente, porém com mudança na função objetivo:
13
PL
Figura 1.5: Famı́lia de retas (a) e Vetor normal e direção de Crescimento (b)
Maximizar x1
+
2x2
Sujeito a:
x1
+
2x2
−2x1
x1
+ 3x2
+ x2
x1 ≥ 0
≤ 8
(a)
≤ 5 (b)
≤ 6 (c)
x2 ≥ 0
(d)
Note que para este caso o problema passa a ter um conjunto de múltiplas soluções, consistindo nos pontos do
segmento da reta x1 + 2x2 entre os pontos (2, 3) e (4, 2).
Observe que a função objetivo é paralela à inequação apresentada na restrição (a), presente na figura 1.6) .
Solução ilimitada
Exemplo 8. Seja o problema de PL (Exemplo 6), com uma insero de uma restrio (d) :
Maximizar 2x1
+
3x2
Sujeito a:
+
2x2
−2x1
+
3x2
x1
+ x2
x1
x1 ≥ 0
x2 ≥ 0
≥ 8
(a)
≤ 5
(b)
≥
(c)
6
(d)
Observe, na Figura 1.7, que o espaço de soluções passa a ser ilimitado por todo o espaço à direita da reta (a)
e abaixo da reta (b). Portanto, nesta situação, o problema tem uma solução tendendo ao infinito, pois a função
objetivo pode se deslocar para a direita sem limitações e aumentar o valor de Z indefinidamente.
14
PL
Figura 1.6: Múltiplas soluções
Figura 1.7: Solução ilimitada
Solução infactı́vel
Exemplo 9. Seja o problema de PL (Exemplo 6), contudo com as restrições (a) e (c) modificadas nos sinais de
desigualdade :
Maximizar
2x1
+
3x2
Sujeito a:
x1
−2x1
+
+
2x2
3x2
≤ 8
≤ 5
(a)
(b)
x1
+
x2
≤ 6
(c)
x1
+
x2
≥ 7
(d)
x1 ≥ 0
x2 ≥ 0
(e)
Com a adição de uma nova restrição ao problema do Exemplo 9, temos um conjunto vazio de solução, pois
15
PL
Figura 1.8: Solução inconsistente
não é possı́vel satisfazer a função objetivo quanto às restrições (c) e (d) ao mesmo tempo.
1.5 Exercı́cios Propostos
1. Determine a região de soluções viáveis para cada uma das seguintes restrições independentes, dado x1 , x2 ≥ 0
(a) −3x1 + x2 ≤ 6
(c) 2x1 − 3x2 ≤ 12
(b) x1 − 2x2 ≥ 5
(d) x1 + x2 ≤ 0
(e) −x1 + x2 ≥ 0
2. Identifique a direção de crescimento de z em cada um dos seguintes casos:
(a) Maximizar f (x) = x1 − x2
(c) Maximizar f (x) = −x1 + 2x2
(b) Maximizar f (x) = −5x1 − 6x2
(d) Maximizar f (x) = −3x1 + x2
3. Dado o sistema de expressões lineares:


−x1



 2x
1

x1



 x
+2x2
≤
0
−3x2
≤
3
+3x2
≤
6
,x2
≥
0
1
Determine graficamente a solução ótima nos casos :
a. Min f (x) = 2x1 ;
b. Max f (x) = −4x2 ;
c. Max f (x) = 3x1 + 3x2 .
4. Suponha um modelo de programação linear:
16
PL
Max
Sujeito a
x1
+2x2
−6x1
+10x2
≤
30
4x1
+3x2
≥
−12
x1
+2x2
≤
10
≤
6
≥
0
x1
x1 ,
x2
Utilize o método gráfico para resolver o sistema.
5. A Roda S.A produz dois modelos de automóveis: sedã e utilitário. A tabela a seguir mostra o número máximo
de veı́culos que podem ser vendido em cada um dos próximos três meses:
Mês 1
Mês 2
Mês 3
Sedãs
1200
1600
1300
Uilitários
600
700
500
Tabela 1.3: Dados da produção.
Sabe-se que cada sedã é vendido a $ 8.000 e custa $ 6.000 para produzi-lo. O utilitário tem venda de $
9.000 e custo de $ 7.500.
O custo de manter os veı́culos em estoque é de $ 250 para o sedã e $ 300 para o utilitário. Durante cada
mês, no máximo 1500 veı́culo podem ser produzidos e, por restrições de produção, pelo menos 2/3 dos carros
produzidos devem ser sedãs.
No inı́cio do mês 1, há 300 sedãs e 200 utilitários em estoque.
(a) Formule um problema de programação linear que maximize o lucro da companhia.
(b) Suponha que exista a possibilidade deproduzir até 600 veı́culos em horas extras. Entretanto, tal produção
provoca um aumento de $ 800 no custo de cada unidade.
Mostre como incorporar tal decisão ao modelo de programação linear.
6. Seja uma empresa que produz quatro produtos, A, B, C e D. A fabricação de cada unidade desses produtos
exige mão-de-obra, matéria-prima e processamento mecânico, gerando um certo lucro, de acordo com a
tabela:
Recurso
Mão-de-obra (homens-hora/unidade)
Matéria-prima (kg/unidade)
Processamento mecânico (horas-máquina)
Lucro (R$/unidade)
A
8
5
12
3
B
3
7
9
6
C
5
4
8
5
D
6
5
7
4
Disponbilidade
15.000 h
20.000 kg
40.000 hm
–/–
Tabela 1.4: Dados do problema.
Dadas as disponibilidades e os requerimentos para cada produto, como determinar um plano de produção
semanal, de forma a maximizar o lucro? Tente escrever o sistema na forma padrão.
7. Este problema envolve um processo de transporte de agragados para a construção de uma rodovia. Suponha
que, para a construção de uma rodovia, não estejam disponı́veis na região das jazidas de richas adequadas à
17
PL
obtenção de pedra britada. Faz-se necessário, portanto, o transporte desse material de jazidas mais próximas
para alguns pontos convenientes preestabelecidos ao longo do caminho onde será implantada a estrada (figura
1.9), ao menor custo.
Figura 1.9: Pedreiras fornecedoras da pedra britada P1, P2, P3, P4; pontos de depósito de material D1, D2, D3
e do trajeto da rodovia R.
Nesse problema, temos m = 4 jazidas correspondentes às origens e n = 3 depósitos correspondentes aos
destinos, cujos dados estão na tabela a seguir.
Pedreiras
1
2
3
4
Demanda bj
Depósito 1
30
12
27
37
697
Depósito 2
13
40
15
25
421
Depósito 3
21
26
35
19
612
Oferta ai
433
215
782
300
–/–
Tabela 1.5: Dados do problema de transporte.
As quantidades ofertadas (ai - última coluna) e demandas (bj - última linha), em toneladas, bom como os
custos de transportar 1 tonelada de pedra da pedreira i para o depósito j (cij - que é função de vários fatores,
como tempo de viagem, condições das estradas de acesso, condições dos veı́culos que servem a trajetória
em questão etc.), são as representações do que está envolvido no problema.
Se xij é a variável de decisão que representa a quantidade transportada de rochas da jazida i para o ponto
de depósito j, podemos formular este problema da seguinte maneira:
18
Minf (xij ) =
Suj. a
PL
30x11
+13x12
+21x13
+40x21
40x22
+26x23
+27x31
15x32
+35x33
+37x41
25x42
+19x43
x11
+x12
+x13
≤ 433
x21
+x22
+x23
≤ 215
x31
+x32
+x33
≤ 782
x41
+x42
+x43
≤ 300
x21
+x31
+x41
x12
+x22
+x32
+x42
= 421
x13
xij
+x23
≥
+x33
0
+x43
= 612
= 697
Para verificar uma mudança no problema, imagine se por um problema estrutural, o Depósito 2 tenha de
ser fechado. Como ficaria o modelo se 45% da demanda deste depósito tenha de ir para o Depósito 1 e o
restante para o Depósito 3?
8. Um fabricante de geladeiras precisa decidir quais modeos deve produzir em uma de suas plantas e de acordo
com uma pesquisa de consumo, o mercado consome no máximo 1500 unidades do modelo Luxo e 1600 do
Básico por mês que virá. A fábrica dispõe de 25000 homens-hora por mês, sendo que cada modelo Luxo
precisa de 10 homens-hora e o Básico 8 homens-hora. A linha de montagem é integrada (produz os dosi
modelos em conjunto) e pode produzir até 4500 unidades por mês, com lucro sobre o modelo Luxo de $ 100
e o Básico de $ 50.
Deseja-se maximizar os lucros da venda dos produtos desta fábrica. Como seria o modelo de PL para este
problema?
9. Quatro cidades descarregam águas servidas na mesma corrente. A cidade 1 está a montante, seguida da
cidade 2, cidade 3 e por fim a cidade 4 à jusante da corrente. Medidas ao longo do corpo de água, as
distâncias entre as cidades são de aproximadamente 15 milhas entre si. Um dos parâmetros de medida em
águas servidas é a demanda bioquı́mica de oxigênio (DBO), que é a quantidade de oxigênio requerida para
estabilizar os poluentes presentes na água.
A Agência de Proteção Ambiental estabeleceu um máximo de carga de DBO, expressaem lb de DBO por
galão. A remoção de poluentes das águas servidas ocorre de duas formas: depuração natural e tratamento de
esgoto antes do despejo nos corpos de água. O objetivo então, é determinar a melhor eficiência econômica
de cada umas das estações localizadas nas quatro cidades (a eficiência máxima possı́vel de uma estação é de
99%).
Para montarmos um modelo, devemos citar as variáveis como:
• Q1 - fluxo da corrente (galões/hora) na saı́da da cidade 1;
• p1 - taxa de descarga deDBO (lb/hora);
• x1 - eficiência da estação 1 (≤ 0.99);
• b1 - máxima carga de DBO permissı́vel na cidade 1 (lb.DBO/galão).
Para satisfazer o requisito de carga de DBO na descarga da cidade 1 para a 2, precisamos ter:
p1 (1 − x1 ) ≤ b1 Q1
19
PL
De modo semelhante, no fim da cidade 2:
(1 − r12 )(Descarga de DBO no trecho 1 - 2) + (Descarga de DBO no trecho 2 - 3) ≤ b2 Q2
ou
(1 − r12 )p1 (1 − x1 ) + p2 (1 − x2 ) ≤ b2 Q2
O coeficiente r12 (≤ 1) representa a fração de resı́duos removida no trecho 1 - 2 por decomposição. Para a
descarga da cidade 3, a restrição é:
(1 − r 23)[(1 − r12 )p1 (1 − x1 ) + p2 (1 − x2 )] + p3 (1 − x3 ) ≤ b3 Q3
A partir do que foi apresentado (usando os dados da tabela abaixo e considerando a remoção por decomposição
de 6% para os quatro trechos da corrente) determine a maior eficiência econômica para as quatro estações.
Caracterı́stica
Qi (galão/hora)
pi (lb/hora)
bi (lb.DBO/galão)
Custo do tratamento
($/lb.DBO removida)
Cidade 1
(i = 1)
215000
500
0.00085
Cidade 2
(i = 2)
220000
3000
0.0009
Cidade 3
(i = 3)
200000
6000
0.0008
Cidade 4
(i = 4)
210000
1000
0.0008
0.20
0.25
0.15
0.18
Tabela 1.6: Dados do problema de gerenciamento de água.
20
CAPÍTULO
2
Revisão Matemática
Conceitos Básicos
As obras literárias de Programação Linear, escritas na década de 60, traziam revisões extensas de álgebra
linear, determinantes, matrizes, espaços vetoriais, convexidade etc. Essas revisões eram essenciais, pois na época
os conteúdos visados no curso não eram devidamente estudados nos cursos de graduação da época.
Desde então, houve significativa mudança no currı́culo dos cursos de administração, economia e engenharia.
Já no ensino médio, por exemplo, o aluno toma contato com as matrizes, e tem um aprofundamento de álgebra
linear colocada como elemento dos currı́culos mı́nimos dos cursos de graduação na área de Exatas.
A apresentação de conceitos básicos passa a ter propósito de unificação do conhecimento, de nomenclatura
e fixação da notação usada. A revisão a seguir tem um ponto de vista da Programação Linear, de modo que a
mesma é orientada para antecipar o entendimento dos métodos de otimização.
2.1 Equações lineares
Um sistema de m equações linerares e n variáveis tem a seguinte representação algébrica:
a11 + a12 x2 + ... + a1n xn = b1
a21 + a22 x2 + ... + a2n xn = b2
..
.
am1 + am2 x2 + ... + amn xn = bm
Podemos escrever o sistema na notação Ax = b, isto é, na forma matricial, como :

a11
a12
...
a1n
 
x1


b1


 a21


 ...
a22
...
...
..
.
 
a2n  
·
 
...  
x2
..
.
 
 
=
 
 
b2
..
.





am1
am2
...
amn
xn
bn
Um sistema de equações lineares (SEL) é denominado homogêneo se b = 0.
Capı́tulo 2. Revisão Matemática
PL
2.1.1 Solução de um Sistema de Equações Lineares
Uma solução de um SEL é um conjunto de valores xj (j = 1, ..., n) se satisfaz simultaneamente todas as
equações do sistema. Pela resolução de um sistema, temos 3 alternativas de soluções:
• Tem uma única solução;
• Possui um conjunto infinito de soluções, ou múltiplas solues;
• Não tem solução para o sistema;
Quando o sistema apresentar m = n (matriz quadrada), a indicação de qual dessas alternativas ocorre é dada
pelo determinante (D) da matriz, a saber:
• Quando D = 0 , indica indeterminação (infinitas soluções) ou um sistema sem solução;
• Quando D 6= 0 , indica que o sistema é crameriano
1
e portanto, possui uma única solução possı́vel.
2.1.2 Operações elementares
As operações elementares, conforme ([11]), de um sistema consistem em transformações realizadas no sistema.
São elas:
I.
Troca de linhas;
II.
Multiplicação de uma linha por escalar não nulo;
III.
Combinações lineares de linhas;
A seguir veremos os casos de solução dos SEL onde m = n e m 6= n
2.1.3 Solução de Sistema de Equações Lineares, caso m = n
Nesta subseção, podemos resumir a forma de algumas soluções para alguns tipos de sistemas Ax = b, assim:
• Todo sistema homogêneo tem solução x = 0, chamada solução trivial;
1. Se a matriz A é não singular e o sistema homogêneo, só existe a solução trivial (x = 0);
2. Se a matriz A é singular, o sistema homogêneo é indeterminado, pois D = 0.
• Se a matriz A é não singular e o sistema não homogêneo, a solução é única e o sistema é textitcrameriano.
Como A é não singular, sua inversa (A−1 ) existe. Assim:
Ax = b
⇒ A−1 (Ax) = A−1 b
⇒ Ix = A−1 b
⇒ x = A−1 b.
Exemplo 10. Seja o sistema na forma matricial:
1 Um
sistema crameriano é aquele o qual tem um determinante da matriz A um número diferente de zero, significando que o sistema
tem solução única - tal resultado tem ligação com a regra de Cramer.
22
PL

1 −3
2
−1

 1
2

x1


−2



 
2   x2  =  7 
−1
1
x3
2
Calculando-se a matriz inversa de A, e aplicando-a como visto, obtem-se a solução:

x1


5/19
7/19

1/19
−2


2


 

7/19   7  =  −3 
1
−1
3/19

 
 x2  =  −3/19 −8/19
−4/19
2/19
x3
A solução do sistema é então x1 = 2, x2 = −3 e x3 = 1.
Devemos então encontrar a matriz inversa para obter a solução de um sistema? A resposta prática é não,
pois computacionalmente este método é caro devido ao excesso de cálculos necessários para a determinação de
matrizes inversas de sistemas complexos, além disto, a inversa só é passı́vel de cálculo em matrizes quadradas e
com determinante diferente de zero, sendo assim inviável metodologicamente como visto no capı́tulo de Introdução
à Pesquisa Operacional. Nos próximos tópicos explicaremos alguns métodos mais práticos na obtenção de soluções
para os sistemas lineares, sejam eles casos m = n ou n > m.
2.1.4 Método de Gauss-Jordan, caso m = n
Tendo como finalidade a construção, através de operações elementares, de uma matriz unitária, é um método
adequado para as rotinas computacionais para a resolução dos sistemas lineares, uma vez que envolve um algoritmo
mais rápido de ser implementado e calculado pelo processador. Considere o Exemplo 10:


 2x1
x1


2x1
+
−
x2
x2
+
2x2
− 3x3
+ 2x3
= −2
=
7
−
= −1
x3
a. operações elementares sobre x1 : Dividir a 1a linha por 2, adicionar à 2a linha a primeira multiplicada
por(-1) e adicionar à 3a linha a 1a vezes (-2).


 x1
− 3x3 /2
=
−1
3x2 /2
+
7x3 /2
=
8
x2
+
3x3
=
3
1
+
x2 /2
−


b. operações elementares sobre x2 : Dividir a 2a linha por − 2 , adicionar à 1a linha a 2a multiplicada por
− 12 e adicionar à 3a linha a 2a vezes (−1).


 x1
x2
−
x3 /3
−
7x3 /3


19x3
=
= −16/3
=
c. operações elementares sobre x3 : Dividir a 3a linha por
3a multiplicada por
1
3
5/3
19/3
3
9,
resultando em x3 = 1. Somar à 1a linha a
e somar à 2a linha a 3a multiplicada por 73 .


 x1


=
2
= −3
x2
x3
=
1
23
PL
Deste modo, chegamos à mesma solução do Exemplo 10, como x1 = 2, x2 = −3 e x3 = 1. Fica a observação
de que a maneira mais fácil para não se perder durante os cálculos é realizá-los com o auxı́lio da matriz ampliada
da forma A = (A|b).
Este método de transformação da A para a identidade (I) também é chamada de Escalonamento.
2.1.5 Solução de Sistema de Equações Lineares, caso n > m
Se considerarmos o sistema matricial, com Am×n com n > m :
a11
a12
...
a1n
 
x1


b1


 a21
 .
 .
 .
a22
..
.
...
..
.
a2n
..
.
 
 
.
 
 
x2
..
.
 
 
=
 
 
b2
..
.





am1
am2
...
amn

bm
xn
De uma matriz retangular como esta, podemos encontrar diversas soluções com as aplicações anteriormente
discutidas, pois é possı́vel obter várias submatrizes quadradas. Como nota, o número superior de váriáveis em
relação às equações é o que de mais comum ocorre no processo de modelagem, dada a complexidade da realidade,
mesmo que reduzida.
Vamos explicitar alguns conceitos e definições, mediante um exemplo, dados pela Programação Linear.
Exemplo 11. Seja um sistema
(
x1
−2x2
+ x3
+ x4
x1
−x2
− x3
+
x5
=
2
=
2
A partir desse sistema (e todos os casos n > m, podemos realizar diversas considerações e generalizações, a
saber:
1. Em notação matricial (Ax = b), temos:

"
1
−2
1
1
1
−1
−1
0
x1
# 
 x2

.
 x3
1

 x4
0

 "
#


= 2

4


x5
2. O sistema anterior possui cinco variáveis e duas equações, portanto, oferece uma infinidade de soluções.
Podem-se arbitrar valores para 5 − 2 = 3 variáveis e resolver o sistema em relação às duas variáveis restantes.
Para o sistema original ter solução, pelo menos um dos subsistemas será crameriano.
3. O sistema tem uma solução trivial (chamada de básica), que consiste em atribuir o valor nulo em três das
variáveis e chegar-se no valor das outras duas. Como exemplo:
x1 = x2 = x3 = 0 e x4 = 2 e x5 = 4.
Neste caso, x1 ,x2 e x3 são chamadas variáveis não básicas, e x4 , x5 são ditas variáveis básicas.
4. Variável básica é uma variável responsável por uma equação na qual ela tem coeficiente 1, enquanto nas
demais equações seu coeficiente é 0.
24
PL
5. Sistema canônico é um sistema no qual a cada equação temos uma variável básica associada. Visto de forma
matricial, tal sistema remete a uma matriz identidade embutida na matriz A (não obstante fora de ordem).
6. Uma base B do sistema é dada pelo conjunto de vetores coluna correspondentes às variáveis básicas. No
exemplo, a base é formada pelos vetores coluna A4 e A5 , ou B = [A4 A5 ]. Como x4 e x5 são as variáveis
associadas à base, é comum referir-se à base B = x4 x5
7. Em um sistema de cinco variáveis e duas equações, a variedade de soluções triviais, ou básicas é dada pela
permutação:
5
!
2
=
5!
= 10
3!2!
8. As soluções triviais distintas, se existentes, podem ser obtidas por processos de mudança de base (conforme
será explicado na próxima subseção).
2.2 Mudança de Base
2.2.1 O Pivoteamento
A operação de mudar a base é feita segundo operações elementares, sendo equivalente a um conjunto de
operações do tipo Gauss-Jordan, aplicada a uma variável qualquer do problema (escolhida como básica).
Supondo que a variável xi seja básica e pertença a linha r do sistema, a ação de pivotear, tendo em vista a
inserção de xj no lugar, consiste nos passos:
1. Dividir por ar j a r-ésima equação, resultando em ar j = 1 no sistema modificado;
2. Adicionar à k-ésima equação k = 1, 2, . . . , m, k 6= r ,
−akj
−akj
= −akj , de modo a zerar o coeficiente
=
ar j
1
de xj nessa k-ésima linha.
Exemplo 12. Com o exemplo 11 podemos ilustrar o pivoteamento, substituindo x1 por x4 na base. Temos então
i = 4 e j = 1 com r = 2, e deste modo como a11 = 1, não precisamos fazer a divisão por a11 ; da mesma maneira
como a21 = 1, basta somar à 2 equação a 1 multiplicada por (−1) para se obter uma nova base, B = [A1 , A5 ], e
o sistema resultante:
(
x1
−2x2
+x3
+x4
x2
−23
−x4
+x5
=
2
=
2
Se prosseguirmos para B = [A1 , A2 ], o sistema resultante seria:
(
x1
x2
−3x3
−x4
+2x5
=
6
−2x3
−x4
+x5
=
2
Obs: Utilizaremos este resultado a seguir.
O Pivoteamento em Notação Matricial
A mudança de base pode ser vista como uma multipicação matricial, exemplificada na situação a seguir:
25
PL
1. Suponha que a matriz A, do sistema linear A = bx, possa ser escrita pela composição de três colunas
A = [B|N|I], sendo B é a base atual, I a base original e N os demais vetores (contendo as variáveis não
básicas).
2. Seja B−1 a inversa da base atual, então podemos escrever a sequência:
B−1 [B|N|I]x = B−1 b
[I|B−1 N|B−1 ]x = B−1 b
⇒
No exemplo 11 aplicamos os conceitos anteriores, para chegar-se ao resultado apresentado no exemplo 12:

"
#
x1
 . 
2
. 
×
 . = 4
x5

"
B
N
|1
−2|
|
1|
|1
0|
|1
−1|
| − 1|
|0
1|
#
I
Explicitando na base mudada por pivoteamento, temos analogamente:

"
|1
0|
| − 3|
|−1
2|
|0
1|
| − 2|
|−1
1|
B −1 B = I
B −1 N
#

"
#
x1
 . 
6


×  ..  =
2
x5
B −1
Portanto a nova base B = [a1 a2 ] pode ser obtida a partir do sistema original por dois modos:
a. operações elementares (método
" Gauss-Jordan);
#
"
1 −2
−1
−1
b. sejam a base desejada B =
e sua inversa B =
1 −1
−1
original por B−1 , obtendo-se B−1 Ax = B−1 b.
2
1
#
; pré-multiplicando o sistema
2.2.2 Seleção das variáveis básicas
Em problemas de Programação Linear, existe a restrição suplementar de que x ≥ 0, isto é, todas as variáveis
devem ser não negativas. Assim, possivelmente, nem todas as soluções básicas de um sistema serão factı́veis
(possı́veis de serem aplicadas ao modelo), na medida em que nem todas virão a satisfazer a restrição adicional.
Definições
Por se tratar de uma revisão para a PO, devemos focar a mesma sobre os atributos e conhecimentos que serão
exigidos a seguir, para tanto, apresentamos um resumo das definições introduzidas até este ponto:
• Variável básica: é uma variável relacionada a uma equação com coeficiente 1 nesta equação e 0 nas demais;
• Solução básica: é aquela obtida fazendo-se as variáveis não básicas iguais à zero e identificando-se a solução
do sistema linear;
• Solução básica viável: é uma solução básica na qual todas as variáveis básicas satisfazem à restrição
suplementar x ≥ 0;
26
PL
• Base do Sistema: é dada pelo conjunto das variáveis básicas, ou seja, pelos vetores coluna associados aos
coeficientes das variáveis básicas de todas as equações;
• Operação Pivotar - Pivot Operation: é uma sequência de operações elementares que fazem uma variável
tornar-se básica;
• Conjunto Viável: é dado por todas as soluções viáveis do sistema linear, incluindo-se a restrição suplementar
x ≥ 0.
2.2.3 Construção da Variáveis Básicas e Variáveis Artificiais
Forma Geral
Dado um sistema linear padrão, uma forma de se obter um conjunto de variáveis básicas desenvolvida pela
Programação Linear é de realizar-se o acréscimo ao sistema de um conjunto de variáveis básicas (x a ), denominadas
artificiais, ou seja:
a
Ax + Ix = b
ou
h
A|I
i
"
x
#
=b
xa
Neste caso, uma solução inicial consistiria em anular as variáveis originais e deixar as variáveis artificiais na base
do sistema. Esse método cria uma solução básica para o sistema de equações, embora à custa da introdução de
mais variáveis, inexistentes originalmente, contudo, por meio de operações elementares para sucessivas trocas de
base, as mesmas podem ser colocadas como variáveis não básicas e anuladas.
Podemos acrescentar ainda que, a respeito deste método, temos:
• Se o sistema for incompatı́vel o método falha;
• Se houver uma equação redundante (dependência linear), a solução de base encontrada terá uma variável
artificial na base com valor nulo.
Forma Canônica
Sistema canônico é aquele em que cada equação linear possui uma variável básica associada a ela e o sistema
de equações identifica um solução trivial. Um caso particular, porém frequente, é aquele que o sistema original é
dado na forma de desigualdade, Ax ≤ b. Neste caso, introduzem-se variáveis de folga, xf , que medem a diferença
entre o lado direito e o lado esquerdo (como veremos nos modelos de PO, também teremos variáveis de excesso
quando Ax ≥ b).
Matricialmente a situação seria:
f
Ax ≤ b → Ax + Ix = b
ou
h
A|I
i
"
x
xf
#
=b
Uma solução inicial viável básica é quando xf = b e x = 0. Ao contrário das variáveis artificiais do caso geral,
as variáveis de folga (ou excesso) têm sua interpretação como a quantidade dos valores de b não utilizadas.
Vamos exemplificar este sistema e a explicação anterior mediante um exemplo.
Exemplo 13. Suponha o sistema de restrições:
≤ 400
x1
x1
+
x2
≤ 500
2x2
≤ 900
27
PL
Aplicando-se três variáveis de folga (x3 , x4 e x5 ), temos:
x1
+
x3
x2
x1
+
=
+ x4
2x2
+
x5
400
=
500
=
900
Se as variáveis do sistema original representarem:
x1 = número de bolos do tipo 1 a serem produzidos;
x2 = número de bolos do tipo 2 a serem produzidos;
b1 = 400 = quantidade de ovos disponı́veis;
b2 = 500 = quantidade de açúcar disponı́vel;
b3 = 900 = quantidade de farinha disponı́vel.
Nessas condições, as variáveis de folga significam
x3 = quantidade de ovos não utilizados;
x4 = quantidade de açúcar não utilizado;
x5 = quantidade de farinha não utilizada.
Com isto, encerramos a subseção de Mudança de Base.
2.3 Espaços Vetoriais
2.3.1 Definição
Um espaço vetorial V é um conjunto de elementos denominados vetores, tal que a soma de dois de seus
elementos ou a multiplicação de um de seus elementos por escalar (λ ∈ R) também pertence a V.
Além disso, todo espaço vetorial contém um vetor nulo 0 e o vetor oposto, sendo:
C + 0 = C, para todo C ∈ V; C + (−C) = 0, com o vetor oposto −C.
2.3.2 Operações
Algumas operações básicas dos vetores de um espaço vetorial são, como já ditas, a adição de um elemento a
outro e a multiplicação por um número escalar real. Em notação matemática, se tivermos dois vetores (C e D) e
um escalar (λ), demonstramos as operações como:
C + D = (c1 , c2 ) + (d1 , d2 ) = (c1 + d1 , c2 + d2 );
λC = ˘(c1 , c2 ) = (λc1 , λc2 ).
Podemos ver as operações representadas nas figuras 2.1 e 2.2.
2.3.3 Combinação Linear de Vetores
Se A1 , A2 , A3 . . . , An são vetores pertencentes ao espaço vetorial Rm e se x1 , x2 , . . . , xn são números reais,
então o vetor b ∈ Rm , obtido por:
b = A 1 x1 + A 2 x2 + · · · + A n xn
é chamado de combinação linerar dos vetores A1 , A2 , A3 , . . . , An .
Da combinação linear podemos tirar duas conclusões sobre os vetores, a saber:
28
PL
Figura 2.1: Soma de vetores
Figura 2.2: Muiltiplicação de vetores (com λ = −1)
29
PL
• Vetores Linearmente Independentes: Suponha um conjunto de vetores não nulos A1 , A2 , A3 . . . , An pertencentes ao espaço vetorial Rm e x1 , x2 , x3 . . . , xn números reais. Se a equação vetorial:
A 1 x1 + A 2 x2 + · · · + A n xn = 0
só for satisfeita para x1 = x2 = · · · = xn = 0, então dizemos que os vetores A1 , A2 , . . . , An são linearmente
independentes (LI)
• Vetores Linearmente Dependentes: Suponha um conjunto de vetores não nulos A1 , A2 , A3 . . . , An pertencentes ao espaço vetorial Rm e x1 , x2 , x3 . . . , xn números reais. Se a equação vetorial:
A 1 x1 + A 2 x2 + · · · + A n xn = 0
for satisfeita para algum xk com k ∈ (1, 2, . . . , n) diferente de zero, então dizemos que os vetores A1 , A2 , . . . , An
são linearmente dependentes (LD).
2.3.4 Dimensão de um Espaço Vetorial
Um espaço vetorial Rm é de dimensão m se:
• Existirem m vetores v1 , v2 , . . . , vm linearmente independentes pertencentes a Rm .
• Não existirem (m + 1) vetores linearmente independentes pertencentes a Rm .
2.3.5 Base e Coordenadas
Um conjunto de vetores v1 , v2 , . . . , vm ∈ Rm é uma base de Rm se:
• Eles forem LI;
• Qualquer vetor y ∈ Rm puder ser obtido por uma combinação linear desses vetores, isto é:
y = y1 v1 + y1 v1 + · · · + ym vm
Desta maneira, os coeficientes (y1 , y2 , . . . , ym ), unicamente definidos, são as coordenadas do vetor y em
relação à base v1 , v2 , . . . , vm .
2.3.6 Posto (ra ) de uma matriz como um Conjunto de Vetores
Dada uma matriz Am×n , seja Bm×n a matriz-linha reduzida à forma escada linha equivalente a A. O posto de
A, denotado por ra = 3, é o número de linhas (ou colunas) não nulas de B.
Exemplo 14. Seja a matriz


1
0
2
0

A =  −1
5
0
2
0
6

1 
−2
Empregando-se o conceito de vetores LI, primeiro aos vetores coluna e depois aos vetores linha, temos:
30
PL
• Aplicando aos vetores coluna:

1


0


2


0


0




 





 −1  x1 +  5  x2 +  0  x3  1  x4 =  0 
0
−2
6
0
2
Note que o sistema admite uma infinidade de soluções não triviais; portanto, o posto é inferior a quatro. Ao
escolhermos apenas três vetores quaisquer, encontramos um posto igual a 3 (ra = 3).
• Aplicando aos vetores linha:
h
1
0
2
0
i
x1 +
h
−1
5
0
1
i
x2
h
2
0
6
−2
i
x3 =
h
0
0
0
0
i
Essa equação vetorial fornece o sistema de equações:






x1

2x1




−x2
+2x3
5x2
x2
=0
=0
+6x3
=0
−2x3
=0
portanto x1 = x2 = x3 = 0, logo ra = 3.
Base de uma Matriz
Se uma matriz Amxn , m ≤ n, tem n colunas A1 , A2 , . . . , An , das quais m linhas Ar , As , . . . , Ap são linearmente
independentes, então a matriz quadrada B = [Ar , As , . . . , Ap ], de ordem m, é uma base de A.
Mudança de Base
Seja uma base no espaço Rm constituı́da pelos vetores e1 , e2 , . . . , em . Nessa base, qualquer vetor y ∈ Rm é
expresso por uma combinação linear definida univocamente 2 , sendo y1 , y2 , . . . , ym as coordenadas do vetor y, isto
é:
y = y1 e1 + y2 e2 + · · · + yk ek + . . . + y m em
Podemos permutar, na base, o vetor ek pelo vetor y (somente se yk 6= 0). Assim:
ek = −
y1
y2
1
ym
e1 − e2 − · · · + yk y − · · · −
em
yk
yk
yk
yk
Essa expressão mostra o vetor ek expresso em uma base constituı́da pelos vetores y e ei , em que i = 1, 2, . . . , m,
e i 6= k.
Estas expressões são importantes para casos de mudança de base, pois, imagine algum outro vetor x ∈ Rm .
Como exemplo, na base original, esse vetor seria representado por:
x = x1 e1 + x2 e2 + · · · + xk ek + · · · + xm em
2 Diz-se da relação, ou da correspondência, entre dois conjuntos em que a cada elemento do primeiro conjunto corresponde apenas
um elemento do segundo, isto , uma funo injetora entre os conjuntos.
31
PL
Em relação à uma nova base (que inclui y), basta realizar uma substituição de ek na expressão anterior com a
resultante de ek :
x=
y1
x1 − xk
yk
xk
ym
y2
e1 + x2 − xk
e2 + · · · + y + · · · + x m − xk
em
yk
yk
yk
O processo de mudar a base de um espaço é também denominado pivoteamento, exatamente análogo ao
discutido anteriormente.
Produto Escalar (Interno) entre Dois Vetores
Sejam os vetores A1 e A2 pertencentes a um espaço vetorial Rm . O produto escalar, ou produto interno,
desses dois vetores pode ser definido pela expressão a seguir, envolvendo a soma dos produtos dos componentes
correspondentes. Quando dois vetores A1 e A2 são ortogonais, então o produto escalar será nulo.
A1 .A2 = a11 a21 + a12 a22 + · · · + a1n a2n =
n
X
a1j a2j
i
2.4 Conjuntos Convexos e Combinação Convexa
2.4.1 Conjunto Convexo
Seja um conjunto X ∈ Rm . Dado dois pontos quaisquer x1 e x2 ∈ X pertencentes ao conjunto e λ ∈ [0, 1]. Se
λx1 + (1 − λ)x2 ∈ X então, diz-se que X é um conjunto convexo. Não obedecendo a relação, então é dito não
convexo.
2.4.2 Combinação Convexa
De forma análoga, podemos definir uma combinação convexa de vetores. Dados n vetores A1 , A2 , . . . , An
pertencentes a um espaço vetorial Rn e λi para i = 1 : n, temos:
y = λ1 A1 + λ2 A2 + . . . λn An sendo
n
X
λi = 1
i
é uma combinação convexa dos vetores Ai , para i = 1, . . . , n.
"
#
"
#
1
3
Exemplo 15. Sejam os vetores A1 =
e A3 =
∈ R2 . Seja o vetor b = λA1 + (1 − λ)A3 , com
0
0
0 ≤ λ ≤ 1, representando uma combinação convexa dos vetores, ou seja, obedecendo à regra de convexidade.
Se fizermos λ variar entre 0 e 1, o vetor b será representado por pontos situados no segmento que une os
pontos A1 e A3 . Deste modo, vemos a figura 2.3 que ilustra a combinação convexa do exemplo.
2.4.3 Interpretação Geométrica
Portanto, pela definição anterior, um conjunto convexo tem como interpretação geométrica a seguinte situação:
quaisquer pontos no segmento de reta formado por dois pontos quaisquer do conjunto X têm de pertencer a ele.
Em termos geométicos, como exemplo um conjunto do R2 temos a figura 2.4.
Esta interpretação geométrica pode ser generalizada para outras dimensões. Temos ainda duas propriedades
dos conjuntos convexos:
32
PL
Figura 2.3: Combinação convexa do exemplo 15.
1. A intersecção de conjuntos convexos também é um conjunto convexo;
2. A soma (ou a subtração) de dois conjuntos convexos é também um conjunto convexo.
C1 + C2 = {A1 + A2 : A1 ∈ C1 , A2 ∈ C2 } é convexo
C1 − C2 = {A1 − A2 : A1 ∈ C1 , A2 ∈ C2 } é convexo
Figura 2.4: Exemplo de um conjunto convexo e outro não convexo no R2 .
2.4.4 Ponto Extremo de um Conjunto Convexo
Suponha C um conjunto convexo. Então A ∈ C é um ponto extremo de C se não for possı́vel expressá-lo como
uma combinação convexa de quaisquer outros dois pontos distintos pertencentes aos conjunto.
1. Determine a inversa da matriz A usando os recursos do Método de Gauss-Jordan. Para tanto, escreva a
matriz identidade I com a mesma dimensão, ao lado direito. Em seguida aplique operações elementares no
sistema expandido que transformem a matriz A na matriz I, e verifique que a matriz I se transforma na
inversa A−1 :


2
1 −3


a. A =  1 −1
2 
2
2
1
33

b.
PL

1
0
1

A= 0
1
1
2

0 
0
2. Verifique que os seguintes conjuntos de vetores formam uma base no R3 :
a. (1, -1, 2); (0, 5, 0); (2, 0, 6);
c. (1, 0, 0); (1, 1, 0); (1, 1, 1);
b. (-1, 5, 1); (2, 0, -2); (1, 0, 4);
3. Expresse o vetor (1, 1, 1) em cada base existente do exercı́cio anterior.
4. Encontre todas as soluções básicas dos sistemas
a.
x1
−2x2
+2x3
−4x4
=2
3x1
−5x2
+x3
+3x4
=4
b.
2x1
+3x2
+5x3
=5
x1
−4x2
−2x3
=3
5. Dada a matriz A com cinco colunas A1 ,A2 ,A3 ,A4 ,A5 :


1 2 1 0 0


A =  −2 3 0 1 0 
1 2 0 0 1
usando os procedimentos de Gauss-Jordan, expresse A nas bases:
a. B1 =(A1 ,A4 ,A5 );
b. B1 =(A1 ,A2 ,A5 );
c. B1 =(A1 ,A2 ,A3 ).
6. Calcule o posto de A:


1 1
1 1


A =  −2 1 −1 0 
0 3
1 1
7. Nos problemas de (a) até (e), resolver os sistemas pelo método de eliminação de Gauss.


 −2x
x


−x
(a) Para b1 = 2, b2 = 5 e b3 = 7.
+3y
−z
=
b1
−3y
+z
=
b2
+2y
−z
=
b3
(d) Para b1 = −4, b2 = −3 e b3 = −2.
(b) Para b1 = 1, b2 = 6 e b3 = 0.
(c) Para b1 = 2, b2 = −8 e b3 = 9.
(e) Para b1 = 4, b2 = 7 e b3 = 9.
8. (Engenharia de Controle e Automação) Deseja-se construir um circuito como o mostrado na figura 2.5.
onde V1 = 280V , V2 = 100V , V3 = 50V , R1 = 20Ω, R2 = 30Ω, R3 = 50Ω, R4 = 40Ω e R5 = 100Ω.
Dispõe-se de uma tabela de preços de vários tipos de resistências; assim como as correntes que elas suportam
sem queimar.
De que tipo devemos escolher cada resistência para que o circuito funcione com segurança e a sua fabricação
seja a de menor custo possı́vel?
34
PL
Figura 2.5: Sistema de circuito
20Ω
10
15
20
30
Resistências
30Ω 40Ω 50Ω
10
15
15
20
15
15
22
20
20
30
34
34
100Ω
20
25
28
37
0.5
1.0
3.0
5.0
A
A
A
A
Corrente
Máxima
Suportada
Tabela 2.1: Dados das resistências disponı́veis.
9. (Engenharia Ambiental) Necessita-se adubar um terreno, de acordo com um plano de recuperação, acrescentado a cada 10m2 : 140 g de nitrato, 190g de fosfato e 205 g de potássio.
Dispõe-se de quatro qualidade de adubo com as respectivas caracterı́sticas, incluindo sua unidade de custo
de produção (u.c.p):
(a) Cada quilograma do adubo I custa 5 u.c.p e contém 10 g de nitrato, 10 g de fostato e 100 g de potássio;
(b) Cada quilograma do adubo II custa 6 u.c.p e contém 10 g de nitrato, 100 g de fostato e 30 g de
potássio;
(c) Cada quilograma do adubo III custa 5 u.c.p e contém 50 g de nitrato, 20 g de fostato e 20 g de potássio;
(d) Cada quilograma do adubo IV custa 15 u.c.p e contém 20 g de nitrato, 40 g de fostato e 35 g de
potássio;
Quanto de cada adubo devemos misturar para conseguir o efeito desejado se estamos dispostos a gastar 54
u.c.p a cada 10m2 com a adubação?
35
CAPÍTULO
3
Método Simplex
3.1 Teorema Fundamental da Programação Linear
No Capı́tulo 1, o método de resolução gráfica de um problema foi utilizado apenas para casos de duas ou três
variáveis. Para problemas maiores, este método torna-se impraticável, nesta situação precisamos de uma técnica
eficiente para resolver problemas de Programação Linear (PL) com mais de três variáveis. Uma dessas técnicas
chama-se Método Simplex.
Para melhor compreender este método, devemos observar algumas considerações sobre as soluções dos sistemas
que representam os modelos, tomando como exemplo o item “Identificação do ponto ótimo” do Capı́tulo 1. Vimos
que:
(i) A função objetivo assume necessariamente um valor máximo e um valor mı́nimo quando a região poliedral
convexa (factı́vel) for limitada;
(ii) Os vértices desempenham um papel fundamental na procura de máximos e mı́nimos para a função objetivo.
O primeiro resultado acima nos diz que os valores extremos de uma função afim1 são assumidos nos pontos extremos dos segmentos (vértices). Daı́, podemos fazer colocações e generalizações2 , obtendo o Teorema
Fundamental da Programação Linear:
Teorema 1. Seja f (x1 , . . . , xn ) = a1 x1 + · · · + an xn + b, onde b uma constaante qualquer, definida numa região
poliedral convexa A do Rn . Suponha que f assuma um valor máximo (ou mı́nimo) nesta região. Então, se A possui
vértice(s), este valor máximo (ou mı́nimo) será assumido num vértice.
Considerando um problema de Programação Linear na forma padrão:
min
Sujeito a
f (x)
Ax
=
b
x
≥
0
onde A é uma matriz m × (n + m) de posto m, então:
i) se há uma solução factı́vel, há uma solução básica factı́vel.
ii) se há uma solução factı́vel ótima, há uma solução básica facı́vel ótima.
1 Função
2 Para
linear mais contantes.
mais informações e deduções do teorema consultar páginas 368/369 em [4].
Capı́tulo 3. Método Simplex
PL
Do teorema anterior e da equivalência entre solução básica factı́vel e vértice temos que o Método Simplex é
finito, pois um sistema linear de m equações com (m + n) incógnitas tem no máximo, por combinação:
m+n
!
m
=
(m + n)!
Logo, o Simplex efetua um número menor que
!
Soluções básicas
m!n!
n+m
!
interações para encontrar a solução ótima, pois o
m
algoritmo Simplex é um procedimento de busca, isto é, move-se de vértice factı́vel em vértice factı́vel até encontrar
a solução básica factı́vel ótima.
3.1.1
Transição da solução gráfica para a solução algébrica
No método gráfico, a região de soluções é delineada pelos meios-espaços (regiões delimitadas pelas restrições),
sendo possı́vel graficamente observar porque a região factı́vel tem um número infinito de pontos de solução, uma
vez que nos exemplos citados, apresentava-se um plano e que por definição compreende infinitos pontos (podendo
ser extendido aos casos do R3 . . . Rn , como volumes e passando para formas não possı́veis de serem representadas
geometricamente).
No Método Simplex, a região de soluções é representada por m equações lineares simultâneas e n variáveis não
negativas. Neste caso, também ocorre um número infinito de pontos de solução, dado que o número de equações
m é sempre menor que ou igual ao número de variáveis n, pois se não fosse assim, terı́amos no mı́nimo (m − n)
equações redundantes, ou seja, linearmente dependentes.
Contudo, antes de vermos como o Simplex atua diante desse fato de infinidade de soluções, vejamos como
trabalhar com os métodos gráfico e algébrico e as mudanças entre ambos. A Figura 3.1 ilustra esta transição, de
um modo comparativo.
3.2 Método Simplex
3.2.1 Modelo de Programação Linear em forma de equação - Forma Padrão
O desenvolvimento do cálculos do Simplex é facilitado pela imposição de dois requisitos às restrições do problema:
1. Todas as restrições (com exceção da não negatividade das variáveis) são equações cujos lados direitos são
não negativos;
2. Todas as variáveis são não negativas.
A finalidade destes dois requisitos é padronizar e tornar mais eficiente os cálculos de método simplex. Contudo,
antes apresentamos as disposições dos problemas na Forma Padrão e na Forma Canônica
3.2.2 Forma Padrão
A forma padrão é aquela em que as restrições são expressas por meio de equações lineares:
37
PL
Figura 3.1: Transição de solução gráfica para algébrica.
max ou min
f (x) = c1 x1
+
c2 x2
+
...
+
cn xn
Sujeito a
a11 x1
+
a12 x2
+
...
+
a1n xn
=
b1
a21 x1
+
..
.
a22 x2
..
.
+
... +
..
.
a2n xn
..
.
=
b2
..
.
am1 x1
+
am2 x2
+
...
amn xn
=
bn
xi
≥
0,
+
(i = 1 : n)
Em termos de matrizes, pode-se representar a forma padrão da PL como:
min
Sujeito a
f (x) = cx
Ax =
b
≥
0
x
em que:
38
PL
A =⇒ matriz m × n dos coeficientes tecnológicos 3 .
b =⇒ matriz m × 1 das constantes do lado direito.
x =⇒ matriz n × 1 das variáveis de decisão.
c =⇒ vetor 1 × n dos coeficientes da função objetivo f (x).
3.2.3 Forma Canônica
Diz-se que o sistema está na forma canônica quando, embutida na matriz dos coeficientes, encontra-se a
matriz identidade. Em consequência, esse sistema admite uma solução trivial em que as variáveis não associadas
às colunas da matriz identidade são nulas.
O sistema a seguir exemplifica um problema de PL com restrições na forma canônica. Além disso, se para todo
i = 1 : m, bi ≥ 0, a solução é também viável, com xn+1 = bi , enquanto as demais variáveis x1 , . . . , xn são nulas.
max ou min f (x) =
Sujeito a
c 1 x1
+
...
+
c2 x2
+
...
+
cn xn
+
(cn+1 xn+1
+
cn+m xn+m )
a11 x1
+
a12 x2
+
...
+
a1n xn
+
xn+1
= b1
a21 x1
..
.
+
a22 x2
..
.
+
... +
..
.
a2n xn
..
.
+
xn+2
..
.
= b2
..
.
am1 x1
+
am2 x2
+
...
+ amn xn
+
xn+m
= bm
x1 : xn+m
≥
0
Note que na função objetivo, temos as variáveis de folga ou excesso representadas dentro do parênteses.
Uma outra situação muito conveniente é quando as restrições originais se apresentam com sinal “≤”, enquanto
o vetor b ≥ 0, o que corresponde, em notação matricial, ao problema de PL:
min
f (x) = cx
Sujeito a
Ax
≤
b
x
≥
0
Nesse caso, todas as restrições transformam-se em equações mediante a inclusão de variáveis de folga (ou
excesso), uma para cada desigualdade, e o sistema para a forma canônica.
A seguir mostraremos como lidar com desigualdades e variáveis irrestritas, convertendo os problemas para a
forma canônica.
3.2.4 Conversão de desigualdades em equações com o lado direito não negativo
Em restrições (≤), o lado direito pode ser considerado como a representação de um limite imposto à disponibilidade de um determinado recurso, enquanto que o esquerdo, a utilização desse recurso limitado pelas variáveis
(operações) do modelo. A diferença entre um lado e outro pode ser interpretado como uma quantidade de recurso
não utilizada ou uma folga.
Deste modo, para eliminarmos a desigualdade, fazemos a adição de uma variável de folga não negativa (xfn )
ao lado esquerdo da inequação. Considere o Exemplo 13 do Capı́tulo 2, que faz uso dessa operação matemática,
contudo, imagine a adição da restrição a seguir:
3 Tais variáveis são chamadas de tecnológicas pois, dependem do modelo segundo o qual temos tecnologia para empregar naquele
instante - seja em aparelhos de medição ou mesmo nos componentes envolvidos em processos de produção, como máquinas que
processam um número máximo ou um número mı́nimo de determinada substância.
39
PL
x1 + x2 ≤ 10 =⇒ x1 + x2 + xf3 = 10, com xf3 ≥ 0·
De forma análoga, se a restrição for (≥) então, conseguimos a igualdade com a subtração de uma variável
de sobra (ou excesso) não negativa ao lado esquerdo da inequação. Temos a restrição:
x1 + x2 ≥ 10 =⇒ x1 + x2 − xf3 = 10, com xf3 ≥ 0·
Agora, o único requisito é deixar o lado direito da inequação resultante não negativo. Como exemplo:
x1 + x2 ≤ −10 =⇒ −x1 − x2 − xf3 = 10, com xf3 ≥ 0·
x1 + x2 ≥ −10 =⇒ −x1 − x2 + xf3 = 10, com xf3 ≥ 0·
Assim, faz-se a transformação em igualdade, e em seguida multiplica-se por (-1).
3.2.5 Como lidar com variáveis irrestritas
Em alguns casos, as variáveis podem oscilar entre positivo e negativo, talvez o melhor exemplo seja a contratação
e a demissão de funcionários em uma linha produtiva.
Se xi (≥ 0) for a quantidade de mão-de-obra no perı́odo i (um mês, uma quinzena etc), então xi+1 (≥ 0), a
quantidade necessária para o próximo perı́odo i + 1 pode ser expresso como:
xi+1 = xi + yi+1
A variável yi+1 deve ser irrestrita ao sinal, para permitir que xi+1 aumente ou diminua em relação a xi , isto é,
dependa do número de contratados e demitidos, respectivamente.
Podemos satisfazer o requisito da variável não negativa com a substituição:
−
+
yi+1 = yi+1
− yi+1
onde
−
yi+1
≥0
e
+
yi+1
≥0
Para mostrar que a substituição é válida, suponha que no perı́odo 1 a mão-de-obra seja x1 = 30 e que no
perı́odo 2 tenha de aumentar em 10 trabalhadores chegando a 40. Em termos da substituição, y2− e y2+ , será
equivalente a y2+ = 0 e y2− = 10 ( resultando em y2 = 10). De maneira semelhante se for reduzida em 10, teremos
y2− = 0 e y2+ = 10 ( resultando em y2 = −10). A substituição também permite a possibilidade de não haver
alteração na mão-de-obra, fazendo com que ambas as variáveis assumam um valor igual a zero.
3.2.6 Variáveis Não Positivas
Suponha um programa linear em que a variável de decisão x não possa ser positiva, ou seja, x ≤ 0. Nesse caso,
faz-se uma troca de variável:
x = −x 1 , em que x 1 ≥ 0
40
PL
3.2.7 Transformando o Problema de Maximização em Minimização
Utilizando-se a relação de max{f (x)} = − min{−f (x)}, uma situação de maximização pode se transformar em
uma de minimização. Como exemplo, considere a parábola:
• Se f (x) = (x − 3)2 + 4 =⇒ min f (x) = 4, no ponto x = 3;
• Se −f (x) = −[(x − 3)2 + 4] =⇒ max {−f (x)} = −4, no ponto x = 3 .
Assim, ao se multiplicar a função por (−1), ela é substituı́da por outra simétrica em relação ao eixo horizontal
e o mı́nimo de uma ocorre na mesma abscissa que o máximo da outra, naturalmente com sinal inverso. Então,
− max{−f (x)} = min{f (x)}.
3.2.8 Princı́pios do Método Simplex
Suponha o modelo do Exemplo 6 do Capı́tulo 1 resolvido graficamente. Com a auxı́lio desse exemplo, serão
expostos, passo a passo, os Princı́pios do Simplex. Seja o modelo:
max
f (x)
=
Sujeito a:
2x1
+
3x2
x1
+
2x2
≤ 8
+ 3x2
+ x2
≤ 5
≤ 6
− 2x1
x1
≥ 0
x1
x2
≥ 0
Como dito, as inequações do tipo (≤) podem ser transformadas em equações pela inserção de três variáveis de
folga, com peso nulo na função objetivo, de modo que obtém-se o sistema na forma canônica.
max
f (x)
Sujeito a:
=
2x1
+
3x2
+
x1
− 2x1
+
+
2x2
3x2
+ x3
0x3
x1
+
x2
xi ≥ 0
para i = 1 : 5
+
0x4
+
0x5
+ x4
+ x5
=
=
8
5
=
6
O sistema acima possui uma solução trivial, ou seja, fazendo x1 = 0 e x2 = 0, temos:


 x3
Variáveis Básicas
x4


x5
=
8
=
5
=
6
(
Variáveis Não básicas
x1
=
0
x2
=
0
As variáveis definidas como nulas são as não básicas; as demais são chamadas de variáveis básicas e formam
a base do sistema linear. A expressão entrar na base significa fazer uma variável não básica deixar o valor nulo e
crescer até o máximo valor que lhe seja possı́vel e, portanto, positiva ou eventualmente nula.
Como primeira solução do sistema, tem-se f (x) = 2(0) + 3(0) = 0. Observando que esse ponto corresponde
ao ponto da origem x1 = 0 e x2 = 0.
A Primeira Iteração
Observando-se os coeficientes da função objetivo, f (x) = 2x1 + 3x2 , vê-se que o aumento de x1 ou x2 , ou seja,
a entrada de qualquer uma delas na base, deverá aumentar o valor de f (x), pois ambos têm coeficientes positivos
41
PL
nessa função. Como se deseja maximizar, parece intuitivo escolher primeiro aquela variável cujo coeficiente é maior,
nesse caso a variável x2 .
Para que a variável x2 entre na base e aumente seu valor ao máximo, é necessário identificar qual variável básica
deve sair da base e, portanto, se anular. Utilizamos o sistema a seguir para verificar as mudanças nos valores das
variáveis básicas x3 , x4 e x5 quando aumentamos o valor de x2 4 .





x1
+
2x2
−2x1
+
3x2
x1
+
x2
+
x3
=
+ x4
+
x5
8
=
5
=
6
Mantendo-se x1 = 0 e deixando o sistema em função de x2 temos:
x3
x4
= (8 − 2x2 ) ≥
= (5 − 3x2 ) ≥
0
0
x5
=
(6 − x2 ) ≥
0
Ao se aumentar o valor de x2 em 1 unidade, o valor de x3 decresce 2 unidades, x4 descrece 3 unidades e x5
decresce 1 unidade. Para anular as outras variáveis e mantê-las ainda não negativa, devemos encontrar os valores
de x2 que façam isso, podendo em seguida em qual destas variáveis x2 apresenta seu valor mı́nimo (denotado por
5 ).
Portanto, = x2 = min{ 82 , 53 , 61 } = 53 , ou seja, para x2 = 53 , obtém-se x4 = 0, enquanto a demais variáveis
permanecem não negativas (são factı́veis ao modelo). Logo, x4 sai da base, entrando x2 com valor 53 , e a função
objetivo passa a : f (x) = 2(0) + 3 53 = 5, isto é, já temos um valor de função objetivo para a comparação com
as próximas iterações.
A nova base será formada por x2 , x3 e x5 . Para representá-la, basta transformar o sistema inicial, expressando-o
na nova base. Para isso, são feitas operações elementares no sistema, tornando os coeficientes de x2 um elemento
da matriz identidade, a saber:
1
5
2
• Dividir a 2a linha por 3, o que resulta em =⇒ − x1 + x2 + x4 =
3
3
3
• Somar à 1a linha a nova 2a linha multiplicada por (−2) =⇒
7
2
14
x1 + (0)x2 + x3 − x4 =
3
3
3
• Somar à 3a linha a nova 2a linha multiplicada por (−1) =⇒
1
13
5
x1 + (0)x2 − x4 + x5 =
3
3
3
Com essas alterações, o sistema é reescrito conforme:















7
x1
3
−2x1
5
x1
3
+ x3
+
x2
−
+
−
2
x4
3
1
x4
3
1
x4
3
+
x5
=
14
3
=
5
=
6
Pelas variáveis, tem-se:
4 Ao
se realizar esse procedimento atente para manter as variáveis x3 , x4 e x5 não negativas.
bi
do sistema, como j sendo o número da variável (coluna) e i o número da equação (linha)
aij
trabalhadas.
5O
pode ser visto como a razão
42
PL



x3





x2






 x5
=
=
=
14
3
5
3
13
3
(
O valor da função objetivo f (x) = 2x1 + 3x2 = 2(0) + 3
5
3
x1
=
0
x4
=
0
= 5. Consultando-se a solução gráfica, o ponto
obtido na segunda iteração corresponde ao vértice (x1 ,x2 ) = 0, 53 . Necessitamos agora saber se a solução
encontrada é ótima, para tanto devemos expressar a função objetivo em termos das variáveis não básicas, nesse
momento sendo x1 e x4 .
Da segunda linha do sistema modificado obtemos x2 em termos das variáveis x1 e x4 , como:
x2 =
5 2
1
+ x 1 − x4
3 3
3
Substituindo na função objetivo:
f (x) = 2x1 + 3x2 =⇒ 2x1 + 3
5 2
1
+ x1 − x4
3 3
3
=⇒ 5 + 4x1 − x4
Desta expressão, vemos que se valor de x4 aumentar, a função decresce; enquanto que um aumento no valor de
x1 aumenta em quatro unidades a função objetivo. Logo, a função objetivo não está no seu valor ótimo, podendo
aumentar caso x1 entre na base (e ainda x4 fique de fora).
Segunda Iteração
Analogamente, para x1 entrar na base e aumentar de valor, é necessário identificar qual variável (x2 , x3 ou x5 )
deverá sair. Para acompanhar o raciocı́nio algébrico, reescrevemos o sistema modificado com x4 nulo:
7
x1
3
−2x1



 5x
1
3





+ x3
=
14
3
5
=
6
=
+ x2
+
x5
Deixando o sistema em função de x1 para todas as variáveis e considerando-as como zero, temos:

14 7


− x1
x3 =


3
3



5 2
x2 = + x1

3 3





 x5 = 13 − 5 x1
3
3
Na primeira restrição, a variável x3 atinge o valor zero quando x1 = 2; na segunda, a variável não atinge o valor
zero pois o coeficiente de x1 é negativo, o que aumenta o valor quando colocado em função de x1 ; na terceira, x5
13
se anula quando x1 = 13
= 2.
5 . Portanto, = x1 = min 2, ∞, 5
Para x1 = 2, as variáveis assumem os valores:
43
PL


x1 = 2





 x2 = 3
x3 = 0




x
4 =0



x5 = 1
Para os valores encontrados das variáveis a função objetivo f (x) = 2(2) + 3(3) = 13, o que é maior que o 5
encontrado na iteração anterior. A nova base será formada agora por x1 , x2 e x5 . Para representá-la é necessário
a aplicação de operações elementares, o que resulta em:



x1




+
+ x2






+
−
3
x3
7
2
x3
7
5
x3
7
−
+
+
2
x4
7
1
x4
7
1
x4
7
+ x5
=
2
=
3
=
1
Em que:


 x1
x2


x5
=
2
=
3
=
1
(
x3
=
0
x4
=
0
Comparando esse resultado com a solução gráfica, nota-se que esta corresponde ao vértice (x1 ,x2 ) = (2, 3).
Agora realizamos o procedimento de colocar a função objetivo em termos das variáveis não básicas, utilizando as
equações que possuem as variáveis x1 e x2 do sistema obtido:
x1
=
x2
=
3
2 − x3 +
7
2
3 − x3 +
7
2
x4
7
1
x4
7
a função objetivo f(x) fica como:
f (x) = 13 −
12
1
x3 + x4
7
7
Terceira Iteração
Pela última expressão da função objetivo, se x3 aumentar, a função decresce; enquanto que se x4 aumentar,
a função cresce, portanto, x4 deve entrar na base do sistema (note que aparentemente ela parecia não ser uma
candidata a entrar na base). Temos o sistema como:



x1





+
+ x2







+
−
3
x3
7
2
x3
7
5
x3
7
−
+
+
2
x4
7
1
x4
7
1
x4
7
+ x5
=
2
=
3
=
1
Fazendo-se as comparações dentro do sistema, com x3 = 0, obtemos para x1 , x2 e x5 respectivamente, um
= x4 = min{∞, 21, 7} = 7, portanto a variável x5 sai da base para a entrada de x4 . Com as alterações de
mudança de base chegamos no sistema:
44
PL


 x1
x2


−
x3
+
2x5
=
4
+
x3
−
x5
=
2
+
7x5
=
7
− 5x3
+ x4
Em que:


 x1
x2


x4
=
4
=
2
=
7
(
x3
=
0
x5
=
0
Chegamos assim à solução ótima no vértice (x1 , x2 ) = (4, 2), com f (x) = 14. Para efeito de confirmação
algébrica, colocamos a função em termos das variáveis não básicas, obtendo:
f (x) = 14 − x3 − x5
Neste caso, verificamos que ambas as variáveis quando aumentadas, reduzem o valor da função objetivo, isto é, a
solução encontrada é a melhor possı́vel.
A solução gráfica e as soluções encontradas
Na Figura 3.2 verificamos os pontos:
Figura 3.2: Solução gráfica, solução única.
• A para a solução trivial;
• B para a primeira iteração;
• C para a segunda iteração;
• D para a terceira iteração, com solução ótima;
45
PL
• E, o ponto E é o ponto o qual irı́amos recair se em vez de x2 na primeira iteração, se tivessemos escolhido
x1 , o que também economizaria uma iteração, já que a segunda iteração dessa escolha passaria ao ponto C
(verifique como exercı́cio).
Aqui, devemos ressaltar que não há uma regra clara para a escolha de qual variável entra e qual sai da base a
priori, como um palpite inicial, isso pode reduzir muitos passos de acordo com a extensão de quantas variáveis se
está trabalhando. Uma possibilidade é a escolha da variável pelo coeficiente mais favorável possı́vel e outra é a de
se escolher aleatoriamente uma das variáveis com coeficiente favorável, independente do valor, contudo, não há
provas de qual das duas seja melhor.
Na próxima subseção veremos como usar o Método Simplex na forma de quadros (tabelas).
3.2.9 Método Simplex na forma de quadros - Tableau Simplex
Utilizar o Tableau Simplex é um modo de visualização mais claro de uma iteração e de melhor identificar os
procedimentos a serem feitos para as iterações subsequentes. Para colocarmos o sistema na forma de quadros,
utilizaremos a função f (x) como uma restrição e realizaremos as transformações pertinentes ao modo canônico.
Tomando o exemplo da subseção anterior, obtemos:
max
f (x) −2x1
−3x2
+0x3
Sujeito a:
x1
+2x2
+x3
−2x1
+3x2
x1
+0x4
+0x5
+x4
+x2
xi ≥ 0
+x5
para
=
0
=
8
=
5
=
6
i =1:5
Dado o sistema acima, podemos escrevê-lo como a tabela 3.1 (tableau):
Base
max
x3
x4
x5
f (x)
1
0
0
0
x1
–2
1
–2
1
x2
–3
2
3
1
x3
0
1
0
0
x4
0
0
1
0
x5
0
0
0
1
b
0
8
5
6
Linha
(0)
(1)
(2)
(3)
Tabela 3.1: Dados apresentados na forma tableau.
Agora devemos iniciar a análise dos dados para efetuar as trocas de base. Começamos com a linha (0), onde
estão os coeficientes de x1 e x2 , verificando que ambas as variáveis, quando aumentados seus valores, obrigam o
aumento da função f (x) para que a equação seja verdadeira (uma vez que os coeficientes de ambas são negativos),
portanto, uma das duas deve entrar na base e uma das variáveis formadoras da atual base deve sair.
Como a variável x2 apresenta maior coeficiente, esta será escolhida para entrar primeiro na base. Procedemos
então com o destaque da coluna na qual está a variável que entrará na base:
Base
max
x3
x4
x5
f (x)
1
0
0
0
x1
–2
1
–2
1
x2
–3
2
3
1
x3
0
1
0
0
x4
0
0
1
0
x5
0
0
0
1
b
0
8
5
6
Linha
(0)
(1)
(2)
(3)
Tabela 3.2: Começo da verificação da troca de variáveis.
46
PL
Para escolhermos a variável que sai da base, realizamos o teste do quociente para verificar qual o menor valor
de e assim selecionar a variável que deverá sair da base. Esse teste consiste em dividir o valor de bi por aij (desde
que aij seja positivo), sendo j a coluna da variável de entrada. Temos então:
Base
max
x3
f (x)
1
0
x1
–2
1
x2
–3
2
x3
0
1
x4
0
0
x5
0
0
b
0
8
Linha
(0)
(1)
Razão: min = -/8/2 = 4
x4
0
-2
3
0
1
0
5
(2)
5/3 = 1.67
x5
0
1
1
0
0
1
6
(3)
6/1 = 6
Tabela 3.3: Teste do quociente para x2 .
A variável que sai da base é x4 e o elemento a22 = 3 é chamado de pivô. Em seguida realizamos as operações
elementares (Método de Gauss-Jordan) para chegarmos a nova tabela:
Base
max
x3
x2
x5
f (x)
1
0
0
0
x1
–4
7/3
–2/3
5/3
x2
0
0
1
0
x3
0
1
0
0
x4
1
–2/3
1/3
-1/3
x5
0
0
0
1
b
5
14/3
5/3
13/3
Linha
(0)
(1)
(2)
(3)
Tabela 3.4: Resultados da primeira iteração.
Após a primeira iteração, constatamos que f (x) = 5, quando as variáveis não básicas forem zero. Entretanto,
como o coeficiente de x1 permanece negativo, se a variável tiver acréscimo em seu valor, teremos um aumento na
função f (x) e podemos melhorar o seu valor.
Para a entrada de x1 na base procedemos analogamente a x2 . A tabela do teste do coeficiente é:
Base
max
f (x)
1
x1
–4
x2
0
x3
0
x4
1
x5
0
b
5
Linha
(0)
Razão: min = -/-
x3
0
7/3
0
1
–2/3
0
14/3
(1)
(14/3)/(7/3) = 2
x2
x5
0
0
–2/3
5/3
1
0
0
0
1/3
–1/3
0
1
5/3
13/3
(2)
(3)
-/(13/3)/(5/3) = 13/5
Com a entrada de x1 , a variável x3 deve sair da base. Realizando as operações elementares pertinentes,
chegamos a tabela 3.6:
Base
max
x1
x2
x5
f (x)
1
0
0
0
x1
0
1
0
0
x2
0
0
1
0
x3
12/7
3/7
2/7
–5/7
x4
–1/7
–2/3
1/7
1/7
x5
0
0
0
1
b
13
2
3
1
Linha
(0)
(1)
(2)
(3)
Tabela 3.6: Resultados da segunda iteração.
Verificando a linha(0) notamos que o coeficiente da variável x4 é negativo, concluı́mos que esta exerce influência
47
PL
positiva sobre o valor de f (x) de modo que x4 deve entrar na base. Com o teste do coeficiente (tabela 3.7) sabemos
qual variável sairá.
Base
max
x1
x2
f (x)
1
0
0
x1
0
1
0
x2
0
0
1
x3
12/7
3/7
2/7
x4
–1/7
–2/3
1/7
x5
0
0
0
b
13
2
3
Linha
(0)
(1)
(2)
Razão: min = -/-/(3)/(1/7) = 21
x5
0
0
0
–5/7
1/7
1
1
(3)
(1)/(1/7) = 7
A variável x5 sai da base, portanto, realizamos novamente algumas operações elementares para chegarmos a
tabela 3.8:
Base
max
x1
x2
x4
f (x)
1
0
0
0
x1
0
1
0
0
x2
0
0
1
0
x3
1
–1
1
–5
x4
0
0
0
1
x5
1
2
–1
7
b
14
4
2
7
Linha
(0)
(1)
(2)
(3)
Tabela 3.8: Resultados da terceira iteração.
Observe que na linha(0) temos apenas termos com coeficientes positivos, sendo assim, o aumento de uma
dessas variáveis resultaria em um valor de f (x) menor que 14, não desejável uma vez que queremos maximizar a
função objetivo.
Então, temos a melhor resposta possı́vel para o caso, isto é, a solução ótima do sistema é f (x) = 14, com os
valores de: x1 = 4, x2 = 2 e x4 = 7. Substituindo na função f (x):
f (x) = 2x1 + 3x2 + 0x3 + 0x4 + 0x5 =⇒ f (x) = 2(4) + 3(2) + 0(0) + 0(7) + 0(0) =⇒ f (x) = 14.
Agora veremos como os quadros se comportam quando temos Múltiplas Soluções e Soluções Ilimitadas.
Também discutiremos Solução Inexistente, Escolha Inicial e Degeneração.
3.2.10 Análise de Casos Especiais.
Múltiplas Soluções.
Seja o modelo proposto:
max
Sujeito a:
f (x)
=
2x1
+
4x2
x1
+
2x2
x1
+ x2
≤ 4
x2
≥ 0
x1 ,
≤ 5
Reescrevendo o sistema para aplicarmos o Simplex, temos:
48
PL
max
− 2x1
f (x)
Sujeito a:
− 4x2
+
0x3
x1
+
+
x3
x1
+ x2
+
+ x4
xi
≥ 0,
p/ i
=
2x2
+
0x4
=
0
=
5
=
4
1:4
Realizando-se a passagem para o quadro:
Base
max
x3
x4
f (x)
1
0
0
x1
–2
1
1
x2
–4
2
1
x3
0
1
0
x4
0
0
1
b
0
5
4
Linha
(0)
(1)
(2)
Tabela 3.9: Dados apresentados na forma de quadro.
Após as operações necessárias, com a entrada de x2 e a saı́da de x3 , obtemos o sistema abaixo:
Base
max
x2
x4
f (x)
1
0
0
x1
0
1/2
1/2
x2
0
1
0
x3
2
1/2
–1/2
x4
0
0
1
b
10
5/2
3/2
Linha
(0)
(1)
(2)
Verificamos que o valor da função f (x) para este caso é 10. A solução é x1 = 0 e x2 =
saber se existem outras tantas soluções?
5
, contudo, como
2
Resposta: Devemos observar que o coeficiente de x1 após a primeira iteração é zero, isto é, a variável x1 pode
entrar na base sem que ocasione mudança na solução encontrada.
Vejamos então se procedermos com uma segunda iteração, inserindo x1 e retirando-se x4 , com resultado
apresentado:
Base
max
x2
x1
f (x)
1
0
0
x1
0
0
1
x2
0
1
0
x3
2
1
–1
x4
0
–1
2
b
10
1
3
Linha
(0)
(1)
(2)
Observe que após a segunda iteração, a variável x4 ficou com coeficiente nulo. Isto indica que o ótimo da
função neste caso está enquadrado na reta x1 + 2x2 = 5, que pertence à primeira restrição do problema.
Resumindo: na Solução Múltipla, ocorre um processo no qual a variável de entrada não ocasiona mudança no
valor da função objetivo. E mesmo após mais uma iteração, a resposta permanece a mesma (exceto se a variável
que for entrada não é condizente com o critério da função objetivo - maximização ou minimização). Para mais
informações, vide [14].
Solução Ilimitada.
Vejamos o problema:
49
PL
max
f (x)
=
Sujeito a:
2x1
+ x2
x1
− x2
≤
≤
40
x2
≥
0
2x1
x1 ,
10
Para aplicarmos o Método Simplex realizamos as mudanças, obtendo:
max
f (x)
− 2x1
Sujeito a:
x1
− x2
− x2
2x1
xi
+
0x3
+
x3
+
≥ 0,
+
0x4
+ x4
p/
i
=
1:4
b
0
5
4
Linha
(0)
(1)
(2)
=
0
=
10
=
40
Na forma de quadro:
Base
max
x3
x4
f (x)
1
0
0
x1
-2
1
2
x2
-1
-1
0
x3
0
1
0
x4
0
0
1
Neste caso, o que ocorre no quadro é que em algum passo do Método Simplex, haverá na linha(0) uma variável
xk com coeficiente indicando melhoria na função objetivo, porém todos os coeficientes da coluna aik dessa variável
são não positivos, não possibilitando o teste do coeficiente (essa variável pode ser aumentada indefinidamente,
uma vez que nenhuma outra se anulará).
Neste exemplo ocorre esse fato antes da primeira iteração. A visualização gráfica é dada pela Figura 3.3.
Da Figura 3.3 (A) é a restrição 2x1 ≤ 40, (B) a reta função objetivo f (x) = 2x1 + x2 e (C) a restrição
x1 − x2 ≤ 10. Note que a função tem como região de solução a intersecção com a região factı́vel.
Solução Inexistente ou Infactı́vel.
Se o conjunto de restrições é incompatı́vel, o que significa conjunto solução vazio, a aplicação do Método
Simplex produzirá uma anomalia que impedirá a identificação da solução básica (pois nenhuma existe). Observe o
problema abaixo:
max
Sujeito a:
f (x)
=
3x1
+
2x2
2x1
+
x2
≤ 2
3x1
x1 ,
+
x2
4x2
≥
≥ 12
0
A função objetivo corta a região fora das duas áreas delimitadas pelas restrições, sendo assim, nenhum ponto
de solução é encontrado.
Escolha Inicial - Empate na Entrada.
Como dito, não há um critério claro quanto à escolha da variável que deverá entrar na base do sistema. Podemos
atentar para os coeficientes das variáveis na função objetivo, isto é, qual a influência deles quando os valores das
variáveis oscilam.
50
PL
Figura 3.3: Região do Exemplo 3.12.
Em alguns casos, na função objetivo pode ocorrer um empate nos coeficientes das variáveis, como por exemplo,
na função 3x1 + 3x2 . Se ocorrer algo assim, tanto no inı́cio quanto em alguma das iterações (há mais de um
coeficiente com custos relativos iguais pleiteando entrada na base), a escolha fica aleatória.
Escolha no Término de uma Iteração - Empate na Saı́da e Degeneração.
A ocorrência deste caso está relacionada com a igualdade do mı́nimo durante o teste do quociente. Como no
empate na entrada, o que devemos fazer é escolher aletoriamente uma das duas variáveis que podem sair da base.
No caso do empate dos quocientes, após se pivotar, a variável mantida na base ficará com valor zero. Dizemos,
então, que a solução básica é degenerada. A degeneração consiste em uma solução básica na qual uma das
variáveis básicas tem o valor zero. No começo do uso do Método Simplex, essa problemática despertava interesse,
uma vez que poderia ocorrer o que se chama de ciclagem ou loop (quando uma variável fica nula e tende a ser
tirada da base, contudo no novo passo a variável que entrou não ocasiona mudança no valor da função, gerando
assim um processo infinito de troca de base).
Em modelos reais, pelo arredondamento e pelos coeficientes menos exatos, esse problema tende a não ocorrer.
Contudo, ressaltamos que se houver algum erro durante o processo de cálculo computacional, esse fenômeno não
deve ser totalmente descartado.
3.2.11 Base Artificial.
Até aqui todos os problemas apresentados estavam na forma canônica (ou pelo menos em uma forma padrão
de fácil transformação) e com uma base inicial. Entretanto, apesar desta ser a condição inicial para a aplicação do
algoritmo, em muitos problemas não se tem uma base inicial, impossibilitando o uso do Método Simplex.
51
PL
Nesta seção serão abordados dois recursos para lidar com a situação descrita anteriormente. Tais métodos
consistem na inserção de variáveis artificiais, produzindo como consequência uma base artificial. Com esse artifı́cio
espera-se que, por meio de pivoteamentos, a base artificial seja substituı́da por uma base com variáveis reais do
modelo.
Variáveis Artificiais.
Para o caso geral, introduzimos m variáveis artificiais a cada equação. Às vezes, o modelo apresenta variáveis
que só figuram em uma equação, constituindo parte de uma base. Nesse caso, podemos economizar nas variáveis
a serem introduzidas, de modo que o número de variáveis artificiais pode ser inferior a m.
Seja o sistema geral:
max
Suj. a:
c1 x1
+
c2 x2
+
...
cn xn
a11 x1
+
a12 x2
+
...
a1n xn
a21 x1
..
.
+
a22 x2
..
.
+
...
..
.
a2n xn
..
.
+
am1 x1
+
am2 x2
+
...
amn xn
x1 ,
...,
xn ,
xa1 ,
...,
xam
xa1
+
xa2
..
.
+xam
=
b1
=
=
b1
..
.
=
b1
≥0
Embora agora o problema esteja na forma esperada para ser utilizado pelo Método Simplex, temos variáveis
que não fazem parte do sistema original. Na solução final desejamos que as variáveis extras sejam retiradas da
base estando no nı́vel zero. Para forçar a saı́da das variáveis artificiais, utilizamos dois métodos: Método do M
Grande e o Método das Duas Fases.
3.2.12 O Método do M-Grande
O Método do M-Grande, ou Big M, consiste em se acrescentar à função objetivo do problema original as
variáveis artificiais com coeficientes negativos muito grandes (−M) nos casos de maximização, ou (+M) no caso
de minimização.
Como se quer aperfeiçoar a função objetivo, as variáveis artificiais deverão ter seus valores reduzidos a zero e
sair da base. Se, ao final das iterações necessárias de otimização, for encontrado um valor ótimo de f (x), e todas
as variáveis artificiais estiverem nulas e fora da base, então este valor será o mesmo do problema original, indicando
também o valor das variáveis de decisão.
Caso a solução ótima contenha uma variável artificial, o problema é infactı́vel, apontando que nem todas as
variáveis artificiais puderam ser retiradas da base. Contudo, se na solução, o ótimo de f (x) conter alguma variável
artificial na base com valor nulo, significa então que as equações nas quais elas estão presentes são redundantes
no sistema, podendo ser eliminadas.
A seguir apresentamos um exemplo de como esse método é utilizado em problemas manuais.
Exemplo 16. Seja o seguinte problema com duas variáveis:
min
Suj. a:
f (x)
=
4x1
3x1
+ x2
=
3
4x1
+
3x2
≥
6
x1
+
2x2
≤
4
x2
≥0
x1 ,
+ x2
52
PL
Acrescentando duas variáveis x3 de sobra e x4 de folga, na forma de equações temos:
min
f (x)
=
Suj. a:
4x1
+
x2
3x1
+
x2
4x1
+
3x2
x1
x1 ,
+
x2 ,
2x2
x3 ,
−
x4
x3
≥
+
0
x4
=
3
=
6
=
4
A terceira equação tem uma variável da folga (x4 ), mas a primeira e a segunda não têm. Colocamos então
variáveis artificiais Xa1 e Xa2 (estão em maiúsculo para destacar que tratam-se de variáveis artificiais) e com os
coeficientes M positivos, pois é um problema de minimização:
min
f (x)
=
Suj. a:
4x1
+
x2
+
MXa1
3x1
4x1
x1
x1 ,
+
x2
+
Xa1
+
3x2
−
+
x2 ,
2x2
x3 ,
x4 ,
+
MXa2
=
3
x3
+
Xa2
=
6
x4
≥
=
0
4
Xa1 ,
+
Xa2 ,
Agora temos uma solução básica inicial dada por (Xa1 , Xa2 , x4 ) = (3, 6, 4). Em muitas obras literárias, M
é manipulado algebricamente (não está associado valor algum à variável, usando-a apenas nos cálculos), contudo,
como é mais usual a implementação dos problemas na forma computacional, utilizaremos um valor numérico para
M.
O valor a ser escolhido deveria ser teoricamente infinito contudo, na rotina dos cálculos em computadores, a
interação entre números muito grandes e outros muito pequenos pode ocasionar erros de arredondamento. Para
evitar que tal fato ocorra, devemos escolher o valor de M suficientemente grande em relação aos coeficientes
da função objetivo, sendo assim, no presente caso utilizaremos M = 100, pois os coeficientes de x1 e x2 são
respectivamente 4 e 1, ou seja, 100 é grande se comparado à esses valores.
O sistema em forma de quadros é:
Base
min
Xa1
Xa2
x4
f (x)
1
0
0
0
x1
-4
3
4
1
x2
-1
1
3
2
x3
0
0
-1
0
Xa1
100
1
0
0
Xa2
100
0
1
0
x4
0
0
0
1
b
0
3
6
4
Linha
(0)
(1)
(2)
(3)
Podemos observar no quadro, que a solução inicial resulta em f (x) = 900 e não zero como mostrado na linha(0),
isto ocorre pois, os coeficientes de Xa1 e Xa2 são nulos. Para colocarmos o sistema com essa caracterı́stica, e
torná-lo consistente, devemos operar com as outras linhas de maneira a anular os coeficientes das variáveis artificiais
na função objetivo.
Fazendo-se a linha(1) e a linha(2) vezes 100 e somando-se a linha(0), obtemos os resultados que seguem na
Tabela 3.14.
Como trata-se de um problema de minimização, o coeficiente de maior valor positivo deverá entrar na base,
neste caso a variável é x1 . A razão mı́nima da condição de viabilidade especifica Xa1 como a variável que sai. Após
as operações pertinentes, temos os resultados da Tabela 3.15.
Agora quem deverá entrar é x2 , saindo Xa2 da base. Após mais duas iterações, a solução será:
53
PL
Base
min
Xa1
Xa2
x4
f (x)
1
0
0
0
x1
696
3
4
1
x2
399
1
3
2
x3
-100
0
-1
0
Xa1
0
1
0
0
Xa2
0
0
1
0
x4
0
0
0
1
b
900
3
6
4
Linha
(0)
(1)
(2)
(3)
Tabela 3.14: Dados transformados para a realização dos passos do Simplex.
Base
min
x1
Xa2
x4
f (x)
1
0
0
0
x1
0
1
0
0
x2
167
1/3
5/3
5/3
x3
-100
0
-1
0
Xa1
-232
1/3
-4/3
-1/3
Xa2
0
0
1
0
x4
0
0
0
1
b
204
1
2
3
Linha
(0)
(1)
(2)
(3)
x1 =
2
9
; x2 =
5
5
com
f (x) =
17
.
5
3.2.13 O Método das Duas Fases
O método das duas fases consiste em:
1. Primeira Fase
Coloque o sistema na forma de resolução do Simplex, incluindo as variáveis não básicas e artificiais. Independentemente do requisito da função objetivo – maximização ou minimização – faça um quadro com uma
função de minimização da soma das variáveis artificiais no lugar da função objetivo.
• Se o valor mı́nimo da soma for positivo, o problema de PL não tem solução viável, ou seja, alguma(s)
das variáveis artificiais não saiu da base;
• Caso contrário, passamos à segunda fase.
2. Segunda Fase
Com a solução encontrada no sistema anterior, substituı́mos r por f (x) no quadro, utilizando posteriormente
essa mesma solução como a solução básica viável inicial para o problema original.
Exemplo 17. Considere o problema de PL do Exemplo 16.
• Fase I
min
r = Xa1 + Xa2
Sujeito a
3x1 + x2 + Xa1
4x1 + 3x2 − x3 + Xa2
x1 + 2x2 + x4
x1 , x2 , x3 , x4 , Xa1 , Xa2
= 3
= 6
=
4
≥ 0
A Tabela 3.16 está associado ao problema acima.
54
PL
Base
r
Xa1
Xa2
x4
x1
-7
3
4
1
x2
-4
1
3
2
x3
1
0
–1
0
Xa1
0
1
0
0
Xa2
0
0
1
0
x4
0
0
0
1
f (x)
9
3
6
4
Como no método M-grande, Xa1 e Xa2 são substituı́das na linha r usando:
rmodificada = rantiga + (1 × linha Xa1 + 1 × linha Xa2 )
A linha rmodificada é usada para resolver a Fase I do problema, fornecendo a Tabela 3.17 ótima.
Base
r
x1
x2
x4
x1
0
1
0
0
x2
0
0
1
0
x3
0
1/5
–3/5
1
Xa1
–1
3/5
–4/5
1
Xa2
–1
-1/5
3/5
–1
x4
0
0
0
1
f (x)
0
3/5
6/5
1
Tabela 3.17: Final da Fase I.
3
6
, x2 =
e x4 = 1. Nesse ponto,
5
5
as variáveis artificiais concluı́ram sua missão e podemos eliminar totalmente suas colunas da tabela (e da
Como mı́nimo r = 0, a Fase I produz a solução básica viável x1 =
formulação do problema de PL) e passar para a Fase II.
• Fase II
Escrevemos o problema original como:
min
Sujeito a
f (x) = 4x1 + x2
1
x1 + x 3
5
3
x2 − x 3
5
x3 + x4
x1 , x 2 , x 3 , x 4
=
=
=
3
5
6
5
1
≥ 0
Em essência, a Fase I é um procedimento que transforma as equações de restrição originais de maneira a
fornecer uma solução básica viável inicial para o problema, se houver.
Agora, aplica-se o método Simplex até obter a solução ótima (verifique como exercı́cio).
3.3 Análise de Sensibilidade
Considere a questão a seguir: dada a solução ótima de um problema de Programação Linear, para quais faixas
de valores dos coeficientes a solução ótima seria mantida? Para responder essa questão, fazemos o que se chama
de Análise de Sensibilidade.
De modo geral, os parâmetros em modelos de PL não são exatos. Com a análise de sensibilidade podemos
averiguar o impacto dessa incerteza sobre a qualidade da solução ótima. Por exemplo, no caso do lucro unitário
55
PL
estimado de um produto, se a análise de sensibilidade revelar que a solução ótima não muda para uma variação de
±10% no lucro unitário, podemos concluir que a solução é mais encorpada do que quando a faixa de indiferença é
de apenas ±1%.
Os tipos de análises a serem feitas podem ser agrupadas de acordo com as alterações em:
• Alterações Simples
– alterações nos coeficientes de custo, cj ;
– alterações nas constantes bi ;
– alterações nas restrições, como adição (ou exclusões) de restrições ou variáveis.
• Alterações Sistemáticas - Programação Paramétrica
– alterações sistemáticas nos cj ;
– alterações sistemáticas nos bi ;
Note que quando falamos de Análise de Sensibilidade, estamos nos referindo às alterações pontuais, uma de
cada vez. Caso existam modificações simultâneas em diversas partes do problema, devemos considerá-lo como
novo, resolvendo-o desde o ı́nicio.
Nesta seção trataremos graficamente e algebricamente dos casos:
1. Alterações nas constantes bi (lado direito das restrições);
2. Alterações nos coeficientes de custo, cj (coeficientes da função objetivo).
Para tanto utilizaremos exemplos.
3.3.1 Análise de Sensibilidade gráfica
Alterações nas constantes bi (lado direito das restrições)
Exemplo 18. A Jobco produz dois produtos em duas máquinas. Uma unidade do produto 1 requer duas horas
na máquina 1 e uma hora na máquina 2. Para o produto 2, uma unidade requer uma hora da máquina 1 e três
horas da máquina 2. As receitas por unidade dos produtos 1 e 2 são $30 e $20, respectivamente. O tempo de
processamento diário disponı́vel para cada máquina é oito.
Representando o número diário de unidade de produtos 1 e 2 por x1 e x2 , respectivamente, o modelo é dado
como:
max f (x) =
30x1
+
20x2
Sujeito a
2x1
+
x2
≤
8
(Máquina 1)
x1
+
3x2
≤
8
(Máquina 2)
x2
≥
0
x1 ,
A figura 3.4 ilustra a variação na solução ótima quando são feitas alterações na capacidade da máquina 1. Se
a capacidade diária for aumentada de oito horas para nove horas, a nova solução ótima ocorrerá no ponto G.
A taxa de variação em f (x) ótima resultante da alteração da capacidade da máquina 1 pode ser calculada da
seguinte maneira:
56
PL
Figura 3.4: Gráfico de análise de sensibilidade da solução ótima a variações na disponibilidade de recursos.

Taxa de variação na

 receita resultante do

 aumento de uma hora na


 capacidade da máquina
(ponto C para ponto G)




=
= 142 − 128 = $14/h.
zg − zc


(Alteração na capacidade)
9−8

A taxa calculada fornece uma ligação direta entre a entrada do modelo (recursos) e sua saı́da (receita total),que
representa o valor unitário equivalente de um recurso (em $/hora), isto é, a variação no valor ótimo da função
objetivo por unidade de variação na disponibilidade do recurso (capacidade da máquina). Isso significa que uma
unidade de aumento (redução) na capacidade da máquina 1 aumentará (reduzirá) a receita em $14. Embora o
valor unitário equivalente de um recurso seja uma descrição adequada da taxa de variação da função objetivo,
o nome técnico, preço dual ou preço sombra, agora é um padrão na literatura de PL, e em todos os pacotes
comerciais.
Examinada a figura 3.4, podemos ver que o preço dual de 14/h permanece válido para variações (aumentos
ou reduções) na capacidade da máquina 1 que deslocam sua restrição paralelamente para qualquer ponto sobre o
segmento de reta BF . Isso significa que a faixa de aplicabilidade de determinado preço dual pode ser calculada da
seguinte maneira:
Capacidade mı́nima da máquina 1 (em B = (0, 2.67)) = 2 × 0 + 1 × 2.67 = 2.67/h
Capacidade máxima da máquina 1 (em E = (8, 0)) = 2 × 8 + 1 × 0 = 16/h
Deste modo, podemos concluir que o preço dual permanecerá válido para a faixa:
2.67/h ≤ Capacidade da máquina 1 ≤ 16/h.
Variações fora dessa faixa produzirão um preço dual (equivalente por unidade) diferente.
57
PL
Usando cálculos semelhantes, você pode verificar que o preço dual para a capacidade da máquina 2 é de $2/h e
permanece válido para variações (aumentos ou reduções) que deslocam sua restrição paralelamente para qualquer
ponto sobre o segmento de reta DE, o que resulta nos seguintes limites:
Capacidade mı́nima da máquina 2 (em D = (4, 0))
=
1 × 4 + 3 × 0 = 4/h
Capacidade máxima da máquina 2 (em D = (0, 8))
=
1 × 0 + 3 × 8 = 24/h
A conclusão é que o preço dual de $2/h para a máquina 2 continuará aplicável para a faixa:
4 horas ≤ Capacidade da máquina 2 ≤ 24 horas
Os limites calculados para as máquinas 1 e 2 são denominados faixas de viabilidade.
Os preços duais permitem tomar decisões econômicas sobre o problema de PL como demonstram as respostas
às perguntas apresentadas a seguir.
1. Se Jobco puder aumentar a capacidade de ambas as máquinas, qual deve receber maior prioridade?
2. É dada uma sugestão para aumentar as capacidades as máquinas 1 e 2 ao custo adicional de $10/h. Isso é
aconselhável?
Pense na resposta e o porque da decisão.
Alterações nos coeficientes de custo, cj (coeficientes da função objetivo)
Exemplo 19. A figura 3.5 mostra o gráfico da região de soluções do problema da Jobco apresentado no Exemplo
18. A solução ótima ocorre no ponto C (x1 = 3.2; x2 = 1.6; f (x) = 128).
Figura 3.5: Análise de sensibilidade da solução ótima às variações nas receitas unitárias (coeficientes da função
objetivo).
58
PL
Alterações nas receitas unitárias (isto é, nos coeficientes da função objetivo) alterarão da inclinação de f (x).
Contudo, como podemos ver pela figura, a solução ótima continuará no ponto C contanto que a função objetivo
esteja entre as retas BF e DE (retas que representam as restrições das máquinas 1 e 2, respectivamente), as duas
restrições que definem o ponto ótimo. Isso significa que há uma faixa para os coeficientes da função objetivo que
manterá inalterada a solução ótima em C.
Podemos escrever a função objetivo no formato geral.
max f (x) = c1 x1 + c2 x2
Agora imagine que a reta f (x) gire em torno de C no sentido horário e anti-horário. A solução ótima permanecerá
no ponto C enquanto f (x) = c1 x1 + c2 x2 estiver entre as duas retas, x1 + 3x2 = 8 e 2x1 + x2 = 8. Isso significa
que a razão
c1
c2
pode variar entre
1
3
e 12 , o que resulta na seguinte condição:
1
c1
2
≤
≤
3
c2
1
ou
0.333 ≤
c1
≤2
c3
Essa informação pode fornecer respostas imediatas referentes à solução ótima, como demonstram as respostas
às perguntas a seguir.
1. Suponha que as receitas unitárias para os produtos 1 e 2 sejam alteradas para $35 e $25, respectivamente.
A solução ótima atual permanecerá a mesma?
2. Suponha que a receita unitária do produto 2 seja fixada em um valor atual de c2 = $20. Qual é a faixa de
variação para c1 , a receita unitária do produto 1, que manterá a solução ótima inalterada?
Tente responder as questões.
3.3.2 Análise de Sensibilidade algébrica
Alterações nas constantes bi (lado direito das restrições)
Esta seção estende a análise ao modelo geral de PL. Um exemplo numérico será usado para facilitar a apresentação.
Exemplo 20. A Toyco monta três tipos de brinquedos – trens, caminhões e carros – usando três operações. Os
limites diários dos tempos disponı́veis para as três operações são 430, 460 e 420 minutos, respectivamente, e as
receitas por unidade de trem, caminhão e carro de brinquedos são $3, $2 e $5 ,respectivamente. Os tempos de
montagem por trem nas três operações são 1, 2 e 1 minutos, respectivamente. Os tempos correspondentes por
caminhão e por carro são (3, 0, 2) e (1, 4, 0) minutos (o tempo zero indica que a operação não foi usada).
Representando o número diário de unidades montadas de trens, caminhões e carros,respectivamente, o problema
de PL associado é dado por:
max f (x) =
3x1
+
2x2
+
5x3
Sujeito a
x1
+
2x2
+
x3
+
2x3
x1
+
4x2
x1 ,
x2 ,
x3
3x1
≤
430 (Operação 1)
≤
≤ 420
≥
(Operação 3)
0
Usando x4 , x5 e x6 como variáveis de folga para as restrições das operações 1, 2 e 3, respectivamente, a tabela
encontrada ao final da resolução é:
59
PL
Base
max
x2
x3
x6
f(x)
1
0
0
0
x1
4
-1/4
3/2
2
x2
0
1
0
0
x3
0
0
1
0
x4
1
1/2
0
-2
x5
2
-1/4
1/2
1
x6
0
0
0
1
b
1350
100
230
20
Linha
(0)
(1)
(2)
(3)
Tabela 3.18: Dados da solução ótima do problema .
A solução recomenda a fabricação de 100 caminhões e 230 carros, mas nenhum trem. A receita associada é
$1350.
Determinação de preços duais
As restrições do modelo após a adição das variáveis de folga x4 , x5 e x6 podem ser expressas como
x1
+
2x2
+
x3
+ x4
=
3x1
+
2x3
+ x5
=
x1
+
4x2
+ x6
=
2x2
+
x3
=
430 − x4
(Operação 1)
3x1
+
2x3
=
460 − x5
(Operação 2)
x1
+
4x2
=
420 − x6
(Operação 3)
ou
x1
+
Com essa representação, as variáveis de folga têm as mesmas unidades (minutos) que os tempos de operação.
Assim, podemos dizer que uma redução de 1 minuto na variável de folga é equivalente ao aumento de 1 minuto
no tempo de operação.
Podemos usar essas informações para determinar os preços duais pela equação de maximização de f (x) na
tabela ótima 3.18 abaixo:
f (x) + 4x1 + x4 + 2x5 + 0x6 = 1350
Essa equação pode ser expressa como:
f (x) + 4x1 + x4 + 2x5 + 0x6 = 1350 =⇒ f (x) = 1350 − 4x1 + 1(−x4 ) + 2(−x5 ) + 0(−x6 )
Dado que um decréscimo no valor de uma variável de folga é equivalente a um aumento em seu tempo de
operação, obtemos:
f (x)
=
1350 − 4x1 + 1 (aumento no tempo de Operação 1)
+
2 (aumento no tempo de Operação 2)
+
0 (aumento no tempo de Operação 3)
Essa equação revela que
1. um aumento de 1 minuto no tempo de operação 1 provoca um aumento de $1 em f (x);
2. um aumento de 1 minuto no tempo de operação 2 provoca um aumento de $2 em f (x);
3. um aumento de 1 minuto no tempo de operação 3 não altera f (x);
60
PL
Resumindo, a linha (0) na tabela simplex ótima fornece diretamente os preços duais, como mostra a Tabela
3.19.
Recurso
Operação 1
Operação 2
Operação 3
Variável
de folga
x4
x5
x4
Coeficiente da variável de
folga na linha (0)
1
2
0
Preço dual
($/minuto)
1
2
0
Tabela 3.19: Preços duais .
Esses cálculos mostram como os preços duais são determinados de acordo com a tabela simplex ótima para
restrições ≤. Para restrições ≥, a mesma idéia continua aplicável, exceto que o preço dual assumirá o sinal oposto
do associado à restrição ≤. Quanto ao caso em que a restrição for uma equação, a determinação do preço dual
com base na tabela simplex ótima requer cálculos mais aprimorados (vide [Taha]).
Determinação das faixas de viabilidade
Agora que já determinamos os preços duais, mostreremos como são determinadas as faixas de viabilidade nas
quais os preços permanecem válidos. Representando as variações (positivas ou negativas) nos tempos diários de
fabricação alocados às operações 1, 2 e 3 por D1 , D2 e D3 , respectivamente, o modelo pode ser expresso da
seguinte maneira:
x1
+
2x2
3x1
+
+
x3
2x3
≤
≤
430 + D1
460 + D2
(Operação 1)
(Operação 2)
x1
+
4x2
≤
420
(Operação 3)
x1 ,
x2 ,
x3
≥
0
+ D3
Consideraremos o caso geral de alterações simultâneas. Os casos especiais de uma alteração por vez são
derivados desses resultados.
O procedimento é baseado em recalcular a tabela simplex ótima com o lado direito modificado, e depois derivar
as condições que manterão a solução viável, isto é, o lado direito da tabela ótima permanecerá não negativo. Para
mostrar como o lado direito é recalculado, começamos modificando a coluna Solução da tabela inicial usando novos
lados direitos. Assim, a tabela simplex inicial terá o seguinte aspecto:
Base
max
x4
x5
x6
f(x)
1
0
0
0
x1
-3
1
3
1
x2
-2
2
0
4
x3
-5
1
2
0
x4
0
1
0
0
x5
0
0
1
0
x6
0
0
0
1
LD
0
430
460
420
D1
0
1
0
0
D2
0
0
1
0
D3
0
0
0
1
Tabela 3.20: Dados para cálculos das faixas de viabilidade.
As colunas sob D1 , D2 e D3 são idênticas às que estão sob as colunas básicas iniciais x4 , x5 e x6 . Isso significa
que, quando executamos as mesmas iterações simplex que as do modelo original, as colunas dos dois grupos devem
ter resultados idênticos também. Na verdade, a nova tabela ótima ficará:
61
Base
max
x2
x3
x6
f(x)
1
0
0
0
PL
x1
4
-1/4
3/2
2
x2
0
1
0
0
x3
0
0
1
0
x4
1
1/2
0
-2
x5
2
-1/4
1/2
1
x6
0
0
0
1
LD
1350
100
230
20
D1
1
1/2
0
-2
D2
2
-1/4
1/2
1
D3
0
0
0
1
Tabela 3.21: Dados finais para os cálculos das faixas de viabilidade.
A nova tabela simplex ótima fornece a seguinte solução ótima:
f (x)
=
x2
=
x3
x6
1350 + D1 + 2D2
1
1
100 + D1 − D2
2
4
1
= 230 + D2
2
=
20 − 2D1 + D2 + D3
A solução atual permanece viável, contanto que todas as variáveis sejam não negativas, o que resulta nas
seguintes condições de viabilidade:
x2
x3
x6
1
1
100 + D1 − D2
2
4
1
= 230 + D2
2
=
=
20 − 2D1 + D2 + D3
≥0
≥0
≥0
Quaisquer variações simultâneas de D1 , D2 e D3 que satisfaçam essas desigualdades manterão a solução viável.
Se todas as condições forem satisfeitas, então a nova solução ótima pode ser encontrada por meio de substituição
direta de D1 , D2 e D3 nas equações dadas anteriormente.
Vejamos três situações sobre o resultado acima:
1. Suponha que o tempo de fabricação disponı́vel para as operações 1, 2 e 3 sejam 480, 440 e 410 minutos,
respectivamente. Para esta situação a solução atual permanece viável?
2. E se os tempos forem 400, 482 e 450 minutos?
3. Como calculamos as faixas de viabilidade individuais que resultam da variação dos recursos um por vez?
Desenvolva cada item.
Alterações nos coeficientes de custo, cj (coeficientes da função objetivo)
Exemplo 21. Definição de custo reduzido. Para facilitar a explicação da análise de sensibilidade da função
objetivo, primeiro precisamos definir custos reduzidos. No modelo da Toyco, a função objetivo f (x) na tabela
ótima é:
f (x) = 1350 − 4x1 − x4 − 2x5
A solução ótima não recomenda a produção de trens de brinquedo (x1 = 0). Essa recomendação é confirmada
pela informação dada por f (x) porque cada unidade de aumento em x1 acima de seu nı́vel zero atual reduzirá o
valor de f (x) em $4.
62
PL
Podemos considerar o coeficiente de x1 como um custo unitário porque ele provoca uma redução na receita f (x).
Mas de onde vem esse ”custo”? Sabemos que x1 tem sua receita unitária de $3 no modelo original. Também
sabemos que cada trem de brinquedo consome recursos (tempos de operações) que, por sua vez, incorrem em
custo. Assim, a ”atratividade” de x1 do ponto de vista da otimização depende dos valores relativos da receita por
unidade e do custo dos recursos consumidos por unidade. Essa relação é formalizada ao se definir custo reduzido
como:
(Custo reduzido por unidade) = (Custo dos recursos consumidos por unidade) − (Receita por unidade)
Para avaliar a relevência dessa definição, no modelo original da Toyco, a receita por unidade para caminhões de
brinquedo (= $2) é menor do que a para trens de brinquedo ($3). Ainda assim, a solução ótima aconselha fabricar
caminhões de brinquedo (x2 = 100 unidades) e nenhum trem. A razão para esse resultado (aparentemente não
intuitivo) é que o custo unitário dos recursos usados para caminhões de brinquedo (isto é, tempos de operações)
é menor do que seu preço unitário. O oposto se aplica ao caso dos trens de brinquedo.
Pela definição dada de custo reduzido, agora podemos ver que uma variável não lucrativa (como x1 ) pode vir
a ser lucrativa de dois modos:
1. Com o aumento da receita unitária;
2. Com a redução de custo unitário dos recursos consumidos.
Em grande parte das situações reais, o preço por unidade pode não ser uma opção viável porque seu valor é
determinado por condições de mercado. Portanto, a opção real é reduzir o consumo de recursos, talvez aumentando
a eficiência do processo de produção.
Determinação das faixas de otimalidade
Agora voltemos nossa atenção à determinação das condições que manterão uma solução ótima inalterada. A
apresentação é baseada na definição de custo reduzido.
No modelo da Toyco, representamos a variação nas receitas unitárias para caminhões, trens e carros de brinquedo
por d1 , d2 e d3 , respectivamente. Desse modo, a função objetivo se torna:
max f (x) = (3 + d1 )x1 + (2 + d2 )x2 + (5 + d3 )x3
O procedimento para a análise de sensibilidade é o mesmo para o lado direito, realizado anteriormente. Com
as variações simultâneas, a linha (0) na tabela simplex inicial aparece como:
Base
max
f(x)
1
x1
−3 − d1
x2
−2 − d2
x3
−5 − d3
x4
0
x5
0
x6
0
Solução
0
Tabela 3.22: Dados da linha (0).
Quando geramos as tabelas simplex usando a mesma sequência das variáveis que entram e que saem do modelo
original (antes da introdução das variáveis dj ), a iteração ótima aparecerá como segue na Tabela 3.23.
Como estamos lidando com um problema de maximização, a solução atual permanece ótima, contanto que os
novos custos reduzidos permaneçam não negativos para todas as variáveis não básicas. Assim, temos as seguintes
condições de otimalidade correspondentes às variáveis não básicas x1 , x4 e x5 :
63
Base
max
x2
x3
x6
f(x)
1
0
0
0
PL
x1
4 − 14 d2 + 32 d3 − d1
-1/4
3/2
-1/4
x2
0
1
0
0
x3
0
0
1
0
x4
1 + 12 d2
1/2
0
-2
x5
2 − 41 d2 + 12 d3
-1/4
0
1
x6
0
0
1/2
1
Solução
1350 + 100d2 + 230d3
100
230
20
Tabela 3.23: Nova tabela simplex.
x1
x4
x5
1
4 − d2 +
4
1
= 1 + d2
2
1
= 2 − d2 +
4
=
3
d3 − d1
2
1
d3
2
≥
0
≥
0
≥
0
Essas condições devem ser satisfeitas simultaneamente para manter a otimalidade da solução ótima atual.
Considere uma modificação como:
1. Para ilustrar a utilização dessas condições, suponha que a função objetivo da Toyco seja alterada de
max f (x) = 3x1 + 2x2 + 5x3
para
max f (x) = 2x1 + x2 + 6x3
A solução ótima será mantida?
1. Resolva o programa linear em uma iteração:
max f (x) =
12x1
+
9x2
+
10x3
x1
1
2 x1
+
+
x3
+
x2
7
4 x2
+
x3
≤ 5
3x1 +
x1 , x2 ,
7x2
x3
+
≥
5x3
0
≤ 5
Sujeito a
≤ 1
2. Resolva o seguinte problema de programação linear utilizando o Método Simplex:
max f (x) =
Sujeito a
x1
+
2x2
6x1
x1
+
10x2
x1 , x2
≥
≤ 30
≤
6
0
64
PL
3. Utilize o Método Simplex para resolver o seguinte problema de Programação Linear:
max f (x) =
5x1
Sujeito a
+
2x2
x1
x2
−2x1 +
x 1 , x2
≤
4
≤
5
x2 ≤ 10
≥ 0
4. Resolva, utilizando o Método das Duas Fases, o seguinte problema de programação linear:
max f (x) =
Sujeito a
x1
+
2x2
+
3x3
x1
−2x1
+
+
2x2
x2
+
+
3x3
5x3
x1
+
2x2
+
x3
x 3 , x4 ≥
0
x1 , x2 ,
− x4
=
15
= −20
+ x4
=
10
5. Resolva o problema de programação linear proposto a seguir e constate que a solução é ilimitada:
max f (x) =
2x1
+
3x2
x1
+
2x2
≥ 8
−2x1
+
3x2
≤ 5
x1
+
x2
≥ 6
x1 , x2
≥
0
Sujeito a
6. Considere o seguinte problema de PL:
max f (x) =
Sujeito a
2x1
+
3x2
x1
+
3x2
≤ 6
3x1
+
2x2
≤ 6
x1 , x2
≥
0
(a) Expresse o problema em forma de equação.
(b) Determine todas as soluções básicas do problema e classifique-as como viáveis básicas e não básicas.
(c) Use a substituição direta na função objetivo para determinar a solução básica viável ótima.
(d) Verifique graficamente que a solução obtida em (c) é a solução ótima do problema de PL – daı́,
conclua que a solução ótima pode ser determinada algebricamente considerando somente soluções
básicas viáveis.
(e) Mostre como as soluções básicas não viáveis são representadas graficamente na região de soluções.
max f (x) =
Sujeito a
2x1
+
3x2
−6x1
+
7x2
− 9x3
≥ 4
x1
+
x2
+
=
x1 , x3
≥
0
∈
R
x2
+
5x3
4x3
6
65
PL
A conversão na forma de equação envolve utilizar a substituição x2 = x2− − x2+ . Mostre que a solução básica
não pode incluir ambas, x2− e x2+ , simultaneamente.
max f (x) =
Sujeito a
x1
x1
+
+
3x2
x2
≤ 2
−x1
+
x2
≤ 4
x1
∈
R
x2
≥
0
(a) Determine todas as soluções básicas viáveis do problema.
(b) Use substituição direta na função objetivo para determinar a melhor solução básica.
(c) Resolva o problema pelo método gráfico e verifique que a solução obtida no item anterior é a ótima.
9. Considere o seguinte conjunto de restrições:
x1
+
2x2
+
2x3
+
4x4
≤ 40
2x1
−
x2
+
x3
+
2x4
≤
4x1
− 2x2
+
x3
−
x4
x3 , x 4
≥
0
x1 , x2 ,
8
≤ 10
Resolva o problema para cada uma das seguintes funções objetivo.
(a) max f (x) = 2x1 + x2 − 3x3 + 5x4 .
(b) max f (x)8x1 + 6x2 + 3x3 − 2x4 .
(c) max f (x) = 3x1 − x2 + 3x3 + 4x4 .
(d) max f (x) = 5x1 − 4x2 + 6x3 − 8x4 .
max f (x) =
x1
Sujeito a
5x1
+
x2
=
4
6x1
+
x3
=
8
3x1
+
x4
=
3
x2 , x 3 , x 4
≥
x1 ,
0
(a) Resolva o problema por inspeção (não use as operações de linha por Gauss-Jordan) e justifique a resposta
em termos das soluções básicas do Método Simplex.
(b) Repita o item anterior considerando que a função objetivo exige min f (x) = x1 .
max f (x) =
16x1
+
15x2
Sujeito a
40x1
+
31x2
≤
124
−x1
+
x2
≤
1
≤
3
≥
0
x1
x1 ,
x2
66
PL
(a) Resolva o problema pelo método simplex, no qual a variável que entra na base é a variável não básica
que tem o coeficiente mais negativo na linha da função objetivo.
(b) Resolva o problema pelo método simplex, sempre selecionando a variável que entra na base como a
variável não básica que tem o coeficiente menos negativo na linha da função objetivo.
(c) Compare o número de iterações dos dois itens anteriores. A seleção da variável que entra na base como
variável não básica que tem o coeficiente mais negativo resulta em um número menor de iterações? A
que conclusão podemos chegar quanto à condição de otimalidade?
(d) Suponha que o sentido de otimização seja mudado para minimização multiplicando f (x) por −1. Como
essa alteração afeta as iterações no método simplex?
12. Considere o seguinte conjunto de restrições:
−2x1
3x2
=
4x1
x1
+ 5x2
+ 2x2
+
≥
≤
6x1
+
7x2
≤
+
8x2
x1 ,
x2
4x1
3
(1)
10 (2)
5 (3)
3
(4)
≥
5
(5)
≥
0
Para cada um dos problemas a seguir, desenvolva a linha f (x) após substituir as variáveis artificiais:
(a) max f (x) = 5x1 + 6x2 sujeito a (1), (3) e (4).
(b) max f (x) = 2x1 − 7x2 sujeito a (1), (2), (4) e (5).
(c) min f (x) = 3x1 + 6x2 sujeito a (3), (4) e (5).
(d) min f (x) = 4x1 + 6x2 sujeito a (1), (2) e (5).
(e) min f (x) = 3x1 + 2x2 sujeito a (1) e (5).
13. Mostre como o método do M-Grande vai indicar que o problema a seguir não tem nenhuma solução viável.
max f (x) =
2x1
+
5x2
Sujeito a
3x1
+
2x2
≥ 6
2x1
+
x2
≤ 2
x1 , x2
≥
0
14. No modelo da Toyco determine se a solução atual mudará em cada umvdos seguintes casos
(a) f (x) = 2x1 + x2 + 4x3
(b) f (x) = 3x1 + 6x2 + x3
(c) f (x) = 8x1 + 3x2 + 9x3
15. A Electra produz quatro tipos de motores elétricos, cada um em uma linha de montagem separada. As
capacidades respectivas das linhas são 500, 500, 800 e 750 motores por dia. O motor do tipo 1 usa oito
unidades de um certo componente eletrônico, o motor do tipo 2 usa cinco unidades, o motor do tipo 3 usa
quatro unidades e o motor do tipo 4 usa seis unidades. O fabricante do componente pode fornecer 8000
peças por dia. Os preços dos componentes para os respectivos tipos de motor são $60, $40, $25 e $30 por
motor.
67
PL
(a) Determine o mix ótimo de produção diário.
(b) A atual programação de produção atende às necessidades da Electra. Contudo, devido à concorrência,
pode ser que a empresa precise reduzir o preço do motor do tipo 2. Qual é a redução que pode ser
efetuada sem alterar a programação da produção atual?
(c) A Electra decidiu reduzir em 25% o preço de todos os tipos de motores. Use análise de sensibilidade
para determinar se a solução ótima permanecerá inalterada.
(d) Atualmente, o motor do tipo 4 não é produzido. De quanto deveria ser o aumento no preço desse motor
para ser incluı́do na programação de produção?
68
CAPÍTULO
4
Dualidade
4.1 Introdução
A cada modelo de PL, a partir de agora denominado Primal (P), corresponde um outro denominado Dual (D). O
relacionamento dos dois modelos é extremamente instigante e capaz de enriquecer a compreensão da Programação
Linear e da sua interpretação econômica.
No problema Primal busca-se a otimização dos nı́veis de atividades das variáveis de decisão, entendidas como as
variáveis reais do problema em análise. No problema Dual a preocupação se dá com recursos disponı́veis, avaliados
a seus preços sombra (preços duais). Desse modo, o presente capı́tulo está fortemente relacionado com o final do
anterior. Além disso, as soluções dos dois problemas estão de tal modo inter-relacionadas pois da solução ótima do
problema Primal é possı́vel reconhecer a solução do Dual. Inversamente, na solução ótima do Dual identificamos
a solução do Primal.
Inicialmente, mostraremos que o Dual é resultado de um problema de Programação Linear, e, por meio de
exemplos simples, apresentamos as propriedades do relacionamento entre os dois problemas. Seguem, sem demonstrações formais, mas por meio de apelos intuitivos, os teoremas básicos da dualidade, completando o capı́tulo
com a apresentação do Método Dual Simplex.
4.2 Definição do Problema Dual
Em grande parte dos tratamentos de PL, o dual é definido para os vários formatos do primal dependendo do
sentido de otimização (maximização ou minimização), dos tipos de restrições (≤, ≥ ou =) e da orientação das
variáveis (não negativas ou irrestrita). Esse tipo de tratamento é um pouco confuso e, por essa razão, oferecemos
uma definição única que abranja todas as formas do primal.
Nossa definição do problema dual requer expressar o problema primal na forma de equações (todas as restrições
são equações cujo lado direito é não negativo e todas as variáveis são não negativas). Esse requisito é consistente
com o formato da tabela simplex inicial. Por consequência, quaisquer resultados obtidos com base na solução
ótima do problema primal se aplicarão diretamente ao problema dual associado.
Para mostrar como o problema dual é construı́do, o problema primal é definido na forma de equações da seguinte
Capı́tulo 4. Dualidade
PL
maneira:
Maximizar ou Minimizar
Sujeito a
f (x)
n
X
=
n
X
cj xj
i=1
aij xj
=
bi ,
i =1:m
xj
≥
0,
j = 1 : n.
i=1
As variáveis xj , j = 1 : n incluem as variáveis de sobra, de folga e artificiais, se houver.
A tabela 4.1 mostra como o problema dual é construı́do com base no problema primal.
Variáveis primais do problema
x1
x2
...
xj
...
xn
Variáveis
duais do
problema
y1
y2
..
.
c1
c2
...
cj
...
cn
Lado
direito
a11
a21
..
.
a12
a22
..
.
...
...
..
.
a1j
a2j
..
.
...
...
..
.
a1n
a2n
..
.
b1
b2
..
.
ym
am1
am2
...
amj
...
amn
bm
Tabela 4.1: Construção do problema dual com base no problema primal.
Efetivamente, temos:
1. Uma variável dual é definida para cada equação (restrição) primal;
2. Uma restrição dual é definida para cada variável primal;
3. Os coeficientes da restrição (coluna) de uma variável primal definem os coeficientes do lado esquerdo da
restrição dual e seus coeficientes na função objetivo definem os coeficientes do lado direito;
4. Os coeficientes da função objetivo do problema dual são iguais aos coeficientes do lado direito das equações
de restrição do problema primal.
As regras para determinar o sentido da otimização (maximização ou minimização), o tipo da restrição (≤, ≥
ou =) e o sinal das variáveis duais estão na tabela 4.2.
Função objetivo do
problema primal
Maximização
Minimização
Problema dual
Objetivo
Tipos de restrições
Minimização
≥
Maximização
≤
Sinal das variáveis
Irrestrita
Irrestrita
Tabela 4.2: Regras para construir o problema dual.
Observe que o sentido da otimização no dual é sempre oposto ao do primal. Os exemplos a seguir demonstram
a utilização das regras de construção do problema dual e também que a definição dada anteriormente incorpora
todas as formas do primal.
Exemplo 22. O Problema Primal é:
max
Sujeito a
f (x)
=
5x1
+
12x2
+
4x3
x1
+
2x2
+
x3
≤
10
x1
−
x2
+
3x3
=
8
x3
≥
0
x1 ,
x2 ,
70
PL
Na forma padrão:
max
f (x)
=
5x1
Sujeito a
+
12x2
x1
+
2x2
x1
−
x2
x1 ,
+
4x3
+
0x4
+
x3
+
x4
+
3x3
x2 ,
x3 ,
x4
=
10
=
8
≥
0
As variáveis duais são 10y1 e 8y2 . O Problema Dual fica como:
min f (y)
=
10y1
+
8y2
y1
+
y2
≥ 5
2y1
−
y2
≥ 12
y1
y1
+
+
3y2
0y2
≥ 4
≥ 0
Sujeito a
y1 ,
y2
irrestritas
Agora utilizaremos um exemplo de minimização como primal.
Exemplo 23. O Problema Primal é:
min
f (x)
=
15x1
+
12x2
x1
+
2x2
≥
3
2x1
−
4x2
≤
5
x2
≥
0
Sujeito a
x1 ,
Na forma padrão:
min
f (x)
=
15x1
+
12x2
+
0x3
+
0x4
x1
+
2x2
−
x3
+
0x4
=
3
2x1
−
4x2
+
0x3
+
x4
=
5
x4
≥
0
Sujeito a
x1 ,
x2 ,
x3 ,
As variáveis duais são 3y1 e 5y2 . O Problema Dual fica como:
max
Sujeito a
f (y)
=
3y1
y1
+ 5y2
+ 2y2
≤ 15
2y1
− 4y2
≤ 12
−y1
≤ 0
y2
y1 ,
y2
≤ 0
irrestritas
4.2.1 Propriedades da Dualidade
A partir do apresentado até aqui, podemos enumerar cinco propriedades que fornecem ao fim um resumo das
regras de construção para o problema dual.
Propriedade 1. “O dual do dual é o primal.”
71
PL
max
f (x)
=
10x1
+
7x2
+
15x3
5x1
+
4x2
+
x3
2x1
+
3x2
+
S. a
x1 ,
≤
80
(y1 )
5x3
≤
30
(y2 )
x3
≥
0
x2 ,
Para a forma dual do problema:
min
f (y)
=
S. a
80y1
+
30y2
5y1
+
2y2
≥ 10
(x1 )
4y1
+
3y2
≥
7
(x2 )
y1
+
5y2
≥ 15
(x3 )
y2
≥
y1 ,
0
Do dual para o primal (ou o processo dual se considerarmos o sistema anterior como um primal):
max
f (x)
=
10x1
+
7x2
+
15x3
5x1
+
4x2
+
x3
≤
80
(y1 )
2x1
+
3x2
+
5x3
≤
30
(y2 )
x3
≥
0
S. a
x1 ,
x2 ,
Propriedade 2. “Se a restrição m do primal é uma igualdade (=), então a variável ym do dual é sem restrição de
sinal.”
max
f (x)
=
S. a
5x1
+
2x2
≤ 3
5x1
x1
+
x1 ,
(y1 )
x2
=
4
(y2 )
2x2
≤ 9
(y3 )
x2
≥ 0
Para a forma padrão:
max
f (x)
=
S. a
5x1
+
2x2
−
x2
≤
≤
+
2x2
≤
9
x2
≥
0
5x1
x1
x1 ,
3
−4
(y1 )
(y2 )
(y3 )
Para o dual:
max
S. a
f (y)
=
3y1
4(y2− − y2+ )
y1
y1 ,
+
(y2− − y2+ )
y2− , y2+ ,
+
9y3
+
y3
≥ 5
+
2y3
≥ 2
y3
≥ 0
72
PL
Propriedade 3. “Se a restrição m do primal é maior que ou igual (≥), então a variável ym do dual é não positiva.”
max
f (x)
S. a
=
5x1
+
2x2
≤
3
x2
≥ 4
2x2
≤ 9
x2
≥ 0
x1
x1
+
x1 ,
Colocando todas as restrições como menor igual (≤):
max
f (x)
=
S. a
5x1
+
2x2
≤
3
(y1 )
−x2
≤
−4
(y2 )
2x2
≤
9
(y3 )
x2
≥
0
x1
x1
+
x1 ,
Construindo o dual:
min f (y)
=
S. a
3y1
− 4y2
y1
−
y1 ,
y2
+
9y3
+
y3
≥ 5
+
2y3
≥ 2
y3
≥ 0
y2 ,
Utilizando uma variável substituta y20 = −y2 , temos:
min f (y)
S. a
=
3y1
− 4y2
y1
y20
y1 ,
y20
+
9y3
+
y3
≥ 5
+
2y3
≥ 2
y3
≥ 0
≤ 0
Propriedade 4. “Se a variável xj do primal é sem restrição de sinal, então a restrição j do dual é uma igualdade
(=).”
Propriedade 5. “Se a variável xj do primal é não positiva, então a restrição j do dual é maior ou igual (≥).”
Sintese das Propriedades
A conclusão geral com base nos exemplos e nas propriedades é que as variáveis e restrições nos problemas
primal e dual são definidas pelas regras na tabela 4.3.
4.2.2 Teoremas Fundamentais da Dualidade
Até agora discutimos os conceitos básicos da dualidade e caracterizamos propriedades importantes para a
construção do par primal-dual. Para completar a importância da dualidade na Programação Linear, faltam os
teoremas fundamentais. A presente seção traz enunciados os teoremas e exemplos de sua aplicabilidade.
73
PL
Primal (max)
k-ésima restrição é (≤)
k-ésima restrição é (=)
k-ésima restrição é (≥)
p-ésima variável primal xp ≥ 0
p-ésima variável primal irrestrita de sinal
p-ésima variável primal xp ≤ 0
Dual (max)
−→
←−
Dual (min)
k-ésima variável dual é positiva yk ≥ 0
k-ésima variável dual irrestrita de sinal
k-ésima variável dual yk ≤ 0
p-ésima restrição é (≥)
p-ésima restrição é (=)
p-ésima restrição é (≤)
Primal (min)
Tabela 4.3: Regras para construir o problema dual.
Teorema da Folga Complementar
Seja xj (j = 1 : n) uma solução ótima para o problema primal de PL e yj (j = 1 : m) uma solução ótima do
problema dual. Então, o seguinte é verdade:
• Se a k-ésima restrição de um dos problemas tem folga não-nula, então a k-ésima variável do outro problema
é zero;
• Se a k-ésima variável de uma solução ótima de um dos problemas é positiva, a k-ésima restrição do outro é
satisfeita com variável de folga igual a zero.
Teorema Fraco da Dualidade
Seja o par primal-dual e seja x um ponto qualquer factı́vel para o problema primal, com o valor correspondente
fp (x) para a função objetivo, e seja y um ponto qualquer factı́vel para o problema dual, com valor correspondente
fd (y) para a função objetivo. Então, para o caso da maximização do problema primal, o Teorema Fraco da
Dualidade afirma que:
fp (x) ≤ fd (y)
Em termos intuitivos, o problema primal (P), que transforma insumos em produtos, busca maximizar a receita
dos produtos, max fp (x). Já o problema dual (D) busca min fd (y), com a receita decorrente da venda das matériasprimas e o seu mı́nimo seria o valor que tornaria sua venda tão atrativa quanto a sua transformação. Cabe relembrar
que, nessa interpretação, os custos administrativos e de transformação fı́sica são ignorados.
Teorema do Critério de Otimalidade
Seja um par primal-dual e seja x a solução ótima para o problema primal, com valor correspondente fp (x) para
a função objetivo, e seja y a solução ótima para o problema dual, com valor correspondente fd (y) para a função
objetivo. Então, o teorema do critério de otimalidade estabelece que:
fp (x) = fd (y)
Corolários dos Teoremas
Abaixo temos alguns corolários pertinentes aos Teoremas.
1. Se o primal é ilimitado (fp (x) =⇒ +∞), o dual não tem solução viável;
74
PL
2. Inversamente, se o dual não tem solução viável, então o primal é ilimitado;
3. Se o dual é ilimitado (fd (y) =⇒ −∞), o primal não tem solução viável;
4. Inversamente, se o primal não tem solução viável, então o dual é ilimitado;
Teorema Principal da Dualidade
Seja um par primal-dual (P) e (D) tal que ambos tenham soluções factı́veis. Então, ambos têm soluções ótimas,
x e y, tais que fp (x) = fd (y)
Quadro-resumo dos Teoremas
Seguindo os teoremas e as propriedades enunciadas anteriormente, podemos escrever o quadro 4.4, que resume
o relacionamento entre as soluções Primal e Dual.
XXX
XXX Primal
Dual XXXX
Tem Solução Factı́vel
Não Tem Solução Factı́vel
Tem solução Factı́vel
Não Tem Solução Factı́vel
max fp = min fd
min fd = −∞
max fp = ∞
Pode ocorrer
Tabela 4.4: Relações entre as soluções primal e dual.
4.3 Método Dual Simplex
O Método Dual Simplex é aplicado em situações em que a solução inicial do primal é infactı́vel, porém os
elementos da linha da função objetivo são todos não negativos, indicando otimalidade. O método procura alcançar
a factibilidade primal tornando as variáveis xj não negativas, mas preservando a factibilidade dual (mantendo a
linha objetivo não negativa).
4.3.1 Resumo do Método
Suponha que o quadro do método apresente as seguintes caracterı́sticas:
• Todos os elementos da linha objetivo são não negativos, ou seja, cj ≥ 0, para j = 1 : m. Esta condição é
denominada otimalidade primal ou solução dual factı́vel;
• A coluna b apresenta pelo menos um elemento negativo, isto é, a condição de não negatividade das variáveis
não é atendida. Diz-se que a solução primal é infactı́vel.
O Método Dual Simplex é aplicado seguindo os passos:
1. Seleção da variável a deixar a base: escolha uma das variáveis negativas, de preferência a mais negativa.
Seja br = min{bi para bi < 0}
Assim, a variável básica correspondente à linha r sai da base e a linha r é a linha do pivô.
2. Seleção da variável que entra na base: introduzir na base aquela variável cujo coeficiente na linha objetivo
atingir zero mais rapidamente, quando um múltiplo da linha r for somado à linha objetivo.
Podem ocorrer dois fatos:
75
PL
(a) A avaliação da variável a entrar na base se restringe às variáveis não básicas que tem um coeficiente
negativo na linha r . A aplicação da lógica anterior conduz à regra dos coeficientes
ck
= max
j
ar j
cj
para ar j < 0
ar j
Assim, a variável xk entra na base. Podemos seguir para o passo 3.
(b) Caso ar j ≥ 0 para todo j = 1 : n, ou seja, a linha r não contém elementos negativos, então o problema
não tem solução factı́vel. Devemos parar então com a tentativa de resolução.
3. Achar uma nova solução básica em que a variável xk se torna básica. Isto equivale a efetuar um pivoteamento simplex em torno do elemento ar k . Vá para o passo 4.
4. Teste da Factibilidade Primal: se todos os bi , i = 1 : m forem não negativos a solução obtida é ótima,
então podemos parar; caso contrário, voltar ao passo 1.
Problemas de Minimização
Há duas formas de tratar problemas deste tipo. São elas:
1. Consiste na conversão do problema de minimização em um problema de maximização.
2. Consiste em inverter o critério de escolha da variável a entrar na base, para o seguinte
cs
= min
j
ar s
cj
para ar j > 0
ar j
Assim, a variável xs entra na base.
Observe o exemplo a seguir.
Exemplo 24. Dado o problema linear
max
f (x)
=
S. a
−x1
+
−
x2
x3
≤ 9
x1
x1
+
x1 ,
x2
+
x2 ,
x3
≤ 2
x3
≥ 0
1. Resolvendo este problema pelo Método Simplex (Primal).
Incluindo as variáveis de excesso.
max
S. a
f (x)
=
−x1
x1
x1
x1 ,
+
+
x2
x2
x2 ,
−
+
x3
+
0x4
+
x4
x3
x3 ,
+
+
x4 ,
0x5
x5
= 9
= 2
x5
≥
0
Após colocar o problema na forma padrão escrevemos o quadro Simplex (Tabela 4.5).
Pela checagem das variáveis vemos que x2 entra, pois o aumento desta resulta em aumento de f (x). Sai x5 ,
uma vez que o teste de coeficiente só é possı́vel para esta (Tabela 4.6).
76
PL
Base
Max
x4
x5
f(x)
1
0
0
x1
1
1
1
x2
-1
0
1
x3
1
0
1
x4
0
1
0
x5
0
0
1
b
0
9
2
Linha
(0)
(1)
(2)
Tabela 4.5: Primeiro quadro com o problema primal.
Base
Max
x4
x2
f(x)
1
0
0
x1
2
1
1
x2
0
0
1
x3
2
0
1
x4
0
1
0
x5
1
0
1
b
2
9
2
Linha
(0)
(1)
(2)
Tabela 4.6: Segundo quadro com o problema primal.
Chegamos no valor máximo de f (x) uma vez que nenhuma outra variável é propicia ao aumento de f (x) (os
coeficientes das variáveis x1 e x3 são positivos).
Então, f (x) = 2 e x = (0, 2, 0, 9, 0).
2. Construindo e resolvendo o Dual.
max
f (x)
=
S. a
−x1
+
x2
−
x3
+
x2
+
x3
≤
9
(y1 )
≤
2
(y2 )
x3 , ≥
0
x1
x1
x1 ,
x2 ,
Na forma dual:
min f (y) =
9y1
+
2y2
S.a
y1
+
y2
y2
y1 ,
≥
≥
−1
1
y2
≥
−1
y2
≥
0
Após colocar na forma padrão temos o quadro Dual Simplex (a coluna b foi renomeada para identificar o
vetor b dual, assim bd ) – Tabela 4.7.
Base
Min
y3
y4
y5
f(y)
1
0
0
0
y1
-9
-1
0
0
y2
-2
-1
-1
-1
y3
0
1
0
0
y4
0
0
1
0
y5
0
0
0
1
bd
0
1
-1
1
Linha
(0)
(1)
(2)
(3)
Tabela 4.7: Primeiro quadro com o problema dual.
Como o caso é de minimização, buscaremos a variável mais positiva (para que o valor de f (y) tenha de ser
o mais negativo possı́vel), sendo que y2 entra na base. A variável que sai da base é y4 pois é a única na qual
podemos aplicar o teste do coeficiente. Após as operações elementares, temos a Tabela 4.8.
77
PL
Base
Min
y3
y2
y5
f(y)
1
0
0
0
y1
-9
-1
0
0
y2
0
0
1
0
y3
0
1
0
0
y4
-2
-1
-1
-1
y5
0
0
0
0
bd
2
2
1
2
Linha
(0)
(1)
(2)
(3)
Tabela 4.8: Primeiro quadro com o problema dual.
Aparentemente y4 poderia entrar na base, contudo os elementos de sua coluna são todos negativos (o mesmo
ocorre com y1 ). Neste caso, paramos os passos e chegamos na solução f (y) = 2 e y = (0, 1, 2, 0, 2).
3. Por fim verificarmos a relação entre as soluções encontradas.
As soluções encontradas são iguais, logo max f (x) = min f (y). Isso ocorre pois ambos os problemas (primal
e dual) são factı́veis.
1. Suponha o problema a seguir:
max
f (x)
=
S. a
3x1
− 2x2
4x1
+
2x1
− 3x2
2x2
x1
x2
≤ 10
≤
7
≥
0
≤
0
Determine o Dual do problema.
max
f (x)
=
2x1
−2x1
x1
S. a
x1
+
3x2
+ 3x2
+ 2x2
≤
≥
6
8
+
x2
≤
6
x2
≥
0
x1 ,
(a) Escreva o problema Dual.
(b) Sabendo que a solução primal é: x1 = 2.4 e x2 = 3.6, use o Teorema da Folga Complementar para
determinar a sua solução dual.
3. Dê o Dual do problema a seguir numa tal forma que as variáveis Duais sejam não-negativas:
max
S. a
f (x)
=
6x1
+
4x2
3x1
+
7x2
− 8x3
+
5x4
+
x5
=
2
2x1
+
x2
+
+
2x4
+
9x5
=
6
x5
≥ 0
∈ R
x1 ,
x2 ,
+
x3
3x3
x3 ,
+
7x4
+
5x5
x4
78
PL
4. Seja o seguinte problema primal:
max
f (x)
=
3x1
S. a
+
x2
+
5x3
6x1
+
3x2
− 5x3
≤ 45
(mão-de-obra)
3x1
+
4x2
+
5x3
≤ 30
(matéria-prima)
x3
≥
x1 ,
x2 ,
0
(a) Resolva o problema Primal pelo Método Simplex.
(b) Escreva o problema Dual e identifique sua solução ótima.
(c) Suponha que 15 unidades adicionais de matéria-prima podem ser obtidas ao custo de $10. É rentável
aceitar essa proposta?
(d) Ache a solução ótima caso a quantidade disponı́vel de matéria-prima passse para 60 unidades.
(e) Para que valores de c1 a solução permanece ótima?
5. Resolver o problema Primal abaixo pelo Método Dual-Simplex, analisando e discutindo em seguida a solução
encontrada.
min
f (x)
=
S. a
x1
+
x2
+
x3
x1
−
2x2
+
x3
≤ 2
x1
+
x2
+
x3
≤ 1
x3
≥ 0
x1 ,
x2 ,
6. Escreva o problema Dual para cada um dos seguintes problemas Primais:
max
(a)
f (x)
=
S. a
−5x1
+
2x2
−x1
+
x2
≤
−2
2x1
+
3x2
≤
5
x2
≥
0
x1 ,
min
(b)
f (x)
=
S. a
6x1
+
6x1
− 3x2
+ x3
≥
2
3x1
+
4x2
+ x3
≥
5
x2 ,
x3
≥
0
x1 ,
max
(c)
S. a
f (x)
=
3x2
x1
+
x2
2x1
+
x2
=
5
3x1
−
x2
=
6
x2
∈
R
x1 ,
7. A BagCo produz jaquetas e bolsas de couro. Uma jaqueta requer 8m2 e uma bolsa, apenas 2m2 . Os requisitos
de mão-de-obra para os dois produtos são 12 e 5 horas, respectivamente. As disponibilidades semanais atuais
de couro e mão-de-obra estão limitadas a 1200m2 e 1850 horas. A empresa vende jaquetas e bolsas a $350 e
$120, respectivamente. O objetivo é determinar a programação de produção que maximize a receita lı́quida.
A BagCo está considerando uma expansão de produção. Qual é o preço máximo de compra que a empresa
deve pagar pelo couro adicional e para a mão-de-obra?
79
CAPÍTULO
5
Métodos de Pontos Interiores
5.1 Introdução
A idéia dos Métodos de Pontos Interiores foi desenvolvida por Karmarkar, em 1984, quando ele publicou um
artigo que buscava a solução de um problema de Programação Linear (PL) através do interior da região viável.
Deste então, houve muitas modificações no método, permanecendo a idéia básica: a de caminhar pelo interior da
região viável .
Atualmente existem três classes de métodos: os que consideram apenas problemas no formato primal, outros
apenas no formato dual e, finalmente métodos que extraem informações dos dois problemas, conhecidos como
Métodos Primais-Duais. Esta última classe será abordada aqui, com base em [12].
5.2 Notação
A maior parte do desenvolvimento teórico de algoritmos para (PL) é feita para problemas com restrições do
tipo igualdade (problemas na forma padrão, como desenvolvido no Capı́tulo 3). No Capı́tulo 4 o denominamos
como Problema Primal (PP). O PL também pode ser formulado com restrições de desigualdades, que se chama
Problema Dual (PD). Os dois problemas (PP e PD) são relacionados por expressões simples, que permitem traduzir
métodos desenvolvidos em um formato para o outro (vide Capı́tulo 4).
Considere o problema no formato primal (ou padrão):
min cT x
(PP)
S. a
Ax
=
b
x
≥
0
onde A ∈ Rn×n , b ∈ Rm e c, x ∈ Rn .
Suporemos que a matriz A tenha posto completo. O conjunto de soluções viáveis de (PP) é definido por:
P = {x ∈ Rn / Ax = b, x ≥ 0}
O interior de P definido por:
P 0 = {x ∈ Rn / Ax = b, x > 0}
é o conjunto das soluções interiores de (PP). Suporemos P 0 6= ∅.
Todo ponto satisfazendo x ∈ P 0 será denominado de ponto interior.
Capı́tulo 5. Métodos de Pontos Interiores
PL
Associado ao (PP) temos o (PD), que consiste basicamente dos mesmos dados organizados de maneira diferente:
max
(PD)
bT y
S. a AT y + z =
c
z ≥
0
y
irrestrito
onde y ∈ Rm e z ∈ Rn . Neste caso, já consideramos o problema dual no formato padrão pela adição da variável z
(variável de folga).
O conjunto de soluções viáveis do (PP) é dado por:
D = (y, z) ∈ Rm × Rn / AT y + z = c, z ≥ 0
O interior de D definido por:
D0 = (y, z) ∈ Rm × Rn / AT y + z = c, z > 0
A teoria da dualidade nos mostra a relação entre os problemas (PP) e (PD), ou seja, o conjunto de soluções
primais nos fornece informação sobre o conjunto de soluções duais e vice-versa. Por exemplo, dados quaisquer
vetores de soluções primais x para (PP) e (y, z) para (PD), temos:
bT y ≥ cT x.
A função objetivo dual fornece um limite inferior para a função objetivo primal, e a função primal fornece um
limite superior para o dual. As duas funções objetivo coincidem no valor, isto é: bT y∗ = cT x∗ se, e somente se x∗
resolve (PP) e (y∗ , z∗ ) resolve (PD).
Considere as condições de otimalidade, para esta classe de métodos, conhecidas como Condições de KarushKuhn-Tucker ou (KKT), estabelecida pelo Teorema 2.
Teorema 2. Considere os problemas (PP) e (PD) acima. O vetor x∗ é uma solução ótima do problema (PP) e
(y∗ , z∗ ) é uma solução ótima do problema (PD) se, e somente se:
AT y + z =
c
z≥0
(viabilidade dual)
Ax
=
b
x≥0
(viabilidade primal)
XZe
=
0
(5.1)
(folgas complementares)
onde X = di ag(x1 , x2 , . . . , xn ), Z = di ag(z1 , z2 , . . . , zn ) e e = (1, 1, . . . , 1)T .
Do Teorema 2, temos que o vetor (x∗ , y∗ , z∗ ) é solução do sistema de equações (5.1) se, e somente se x∗ é
solução do (PP) e (y∗ , z∗ ) é solução do (PD). O vetor (x∗ , y∗ , z∗ ) é chamado de solução primal-dual.
O conjunto de soluções viáveis primais-duais e seu interior podem ser definidos como:
Ω
Ω0
=
=
(x, y, z) / Ax = b, AT y + z = c, (x, z) ≥ 0
(x, y, z) / Ax = b, AT y + z = c, (x, z) > 0
respectivamente. Assumiremos Ω0 6= ∅.
81
PL
5.3 Método Primal-Dual
Os métodos primais-duais estão estritamente relacionados ao consagrado Método de Newton para soluções de
sistemas de equações, lineares ou não. Uma iteração primal-dual é, em última instância, uma iteração adaptada
do método de Newton, proveniente das condições de KKT (5.1).
Podemos escrever as condições de KKT na forma de uma equação, em conjunto com uma restrição. A equação
provém das próprias condições de otimalidade e a restrição continua sendo a de não negatividade. Obtemos então:


Ax − b


F (x, y, z) =  AT y + z − c  = 0,
XZe
(x, y) ≥ 0
(5.2)
com F : R2n+m → R2n+m .
À equação F (x, y, z) = 0 podemos aplicar o método de Newton para encontrar soluções viáveis (x∗ , y∗ , z∗ ),
porém respeitando o limite (x, y) > 0, o que garante estarmos no interior da região viável (Ω0 ).
O método de Newton consiste em gerar uma sequência de pontos {xk } que convirja para a solução de uma
dada equação G(x) = 0, onde G : Rn → Rn , G ∈ C (Rn ) e x ∈ Rn . O método é baseado em uma expansão em
primeira ordem (série de Taylor) da função considerada:
G(x) ≈ G(xk ) + J(xk )(x − xk )
com J sendo o Jacobiano de G. Desta forma, se xk+1 é solução da expansão acima, então vale J(xk )sk = −G(xk ),
com xk+1 = xk + sk . Portanto, o Método de Newton consiste em gerar os passos sk e usá-los para atualizar o
ponto xk .
Uma iteração completa do método de Newton pode ser escrita como
xk+1 = xk − J−1 (xk )G(xk ).
Na aplicação do Método de Newton surgem duas questões: (i) a necessidade de uma solução inicial e, (ii) a
necessidade de exercermos algum controle sobre os passos, já que ele pode convergir para soluções F (x, y, z) = 0
mas que não satisfaçam (x, y) > 0 (ditas soluções espúrias).
O item (i) será abordado na Seção 5.5.1; por isso, consideraremos aqui que já temos uma solução inicial viável.
O item (ii) é o responsável pelos diversos algoritmos que trabalham com a estrutura primal-dual. Cada um deles
possui uma maneira particular de limitar os passos de Newton, ou de alterar sua direção, mantendo a viabilidade
da solução.
Escrevendo uma iteração de Newton para a equação F (x, y, z) = 0, obtemos:

xk+1


xk + ∆xk


xk

 k+1   k
 

 y
 =  y + ∆yk  =  yk  − J−1 (x, y, z)F (x, y, z)
zk+1
zk + ∆zk
zk
(5.3)
ou ainda,

∆xk



 ∆yk  = J−1 (x, y, z)F (x, y, z)
∆zk
82
PL
pré-multiplicando por J(x, y, z):

∆xk



J(x, y, z) =  ∆yk  = −F (x, y, z)
∆zk
sendo:

A
0

J(x, y, z) =  0
AT
Z
0
0


I .
X
Portanto, para obter uma iteração de Newton para a equação F (x, y, z) = 0, rescrevemos J(xk )sk = −G(xk )
como:

A

 0
Z
0
AT
0




Axk − b
∆xk
0




I   ∆yk  = −  AT yk + zk − c 
X k Zk e
∆zk
X
Se o ponto corrente (xk , yk , zk ) é estritamente viável (Axk = b, AT yk + zk = c e (x, z) > 0), então o sistema
acima toma a forma:

A
0

 0
Z
AT
0
0

∆xk


0





I   ∆yk  = 
0

X
∆zk
−Xk Zk e
Atualizando as variáveis (x, y, z) temos:
(xk+1 , yk+1 , zk+1 ) = (xk , yk , zk ) + αk (∆xk , ∆yk , ∆zk ).
Os métodos primais-duais são variações do método de Newton obtidos a partir de modificações na maneira
de calcular (∆xk , ∆yk , ∆zk ), a direção de busca, e αk , o parâmetro que controla o tamanho do passo em cada
iteração. O valor de αk pode atuar no algoritmo de dois modos:
• Mantendo o novo ponto no interior da região viável e.
• Cuidando para que (x, z) permaneça “longe” das fronteiras do quadrante não negativo, (x, z) > 0. Direções
calculadas a partir de pontos próximos a este quadrante tendem a ser distorcidas levando a pouco, se algum,
progresso.
A idéia da trajetória central nos auxı́lia nas questões acima.
5.3.1 A Trajetória Central
Uma das maneiras de manter o algoritmo do tipo primal-dual no interior da região viável é fazer com que a
trajetória gerada pelo método de Newton esteja em alguma vizinhança da denominada trajetória central.
Matematicamente, a trajetória central C é um caminho de pontos estritamente viáveis, (xτ , yτ , zτ ) ∈ C ⊂ Ω0 ,
parametrizado por um escalar τ > 0, de modo que
AT y + z
=
c
z≥0
(viabilidade dual)
Ax
=
b
x≥0
(viabilidade primal)
XZe
=
τe
(x, z) >
(folgas complementares)
(5.4)
0
A trajetória central é um recurso interessante pois quando τ → 0, a equação (5.4) → equação (5.1). Então, se
83
PL
C converge para algum ponto, deve ser para uma solução primal-dual do (PP). Desse modo, C atua como um guia,
evitando soluções espúrias pois mantém os produtos xi zi estritamente positivos, mas tendendo a zero à mesma
velocidade.
Mais ainda: a maioria dos algoritmos primais-duais tomam direções C com τ > 0, ou seja, direções dentro do
quadrante positivo definido por (x, z) > 0. Essa escolha de direções permite que passos maiores sejam dados em
relação às direções de Newton puras, sem violar a condição de positividade, que chamaremos de direção de busca.
Para descrever a direção de busca modificada, introduziremos um parâmetro de centralização σ ∈ [0, 1] e uma
métrica1 dual µ definida por:
n
µ=
1X
xT z
xi z i =
,
n
n
(5.5)
i=1
ou seja, uma média entre os produtos xi zi .
As equações de passo tomam agora a forma:

A

 0
Z
0
AT
0




0
∆xk
0




0
I   ∆yk  = 

k
−Xk Zk e + σµe
∆z
X
(5.6)
Através do controle de σ e µ podemos gerar uma vizinhança da trajetória central em que os novos passos
calculados de acordo com a equação (5.6) tenham melhor progresso do que os passos de Newton puros.
Considere um conjunto estritamente viável H 0 :
H 0 = (x, z) / (x, y, z) ∈ Ω0 para algum y ∈ Rm
e uma função de barreira definida por:
n
fτ (x, z) =
X
1 T
log(xi zi ).
x z−
τ
i=1
Teorema 3. Suponha Ω0 6= ∅ e seja τ um número positivo. Então fτ tem um único mı́nimo local em H 0 , que
satisfaz as condições de trajetória central (5.4).
Retornando às equações de (5.6), podemos escrevê-la na forma de equações, como segue:
AT ∆y + ∆z
A∆x
= 0
= 0
Z∆x + X∆z
= −XZe + σµe
(5.7)
Isolando ∆z da última equação de (5.7), temos:
∆Z = −Ze + σµX−1 e − X−1 Z∆x
(5.8)
Escrevendo (5.8) na primeira equação de (5.7), temos:
AT ∆y − X−1 Z∆x = Ze − σµX−1 e.
1 métrica:
(5.9)
medida.
84
PL
Escrevendo a segunda equação de (5.7) e a equação (5.9) na forma matricial, com ∆z isolado (equação (5.8)):
"
A
0
−X−1 Z
AT
#"
∆x
∆y
#
"
=
#
0
−σµX−1 e + Ze
.
(5.10)
Como X e Z são matrizes diagonais e não singulares, podemos isolar ∆x de (5.10), obtendo assim, um novo
sistema equivalente:
AZ−1 XAT ∆y
∆z
∆x
= A Xe − σµZ−1 e
= −AT ∆y
= −Xe + σµZ
(5.11)
−1
e−Z
−1
X∆z
O passo mais difı́cil é calcular a primeira equação de (5.11), mas o primeiro termo envolve uma matriz definida
positiva AD2 AT , onde D = Z−1/2 X1/2 , podendo então ser aplicada a Fatoração de Cholesky 2 para resolver o
sistema.
5.3.2 Estrutura Primal-Dual
Através dos conceitos apresentados até aqui, podemos definir uma estrutura geral para os algoritmos primaisduais. O método abordado na próxima seção (Seção 5.4) é um caso especial desta estrutura.
Estrutura Primal-Dual
Fase I
Passo 1: (Inicialização) Faça k = 0 e encontre (x0 , y0 , z0 ) ∈ Ω0 uma solução inicial.
Fase II
Passo 2: (Otimalidade) Se o ponto (xk , yk , zk ) satisfaz os critérios de otimalidade, pare.
Passo 3: (Cálculo da direção de busca) Seja σk ∈ [0, 1] e µk =
(xk )T zk
. Calcule:
n
T
k
AZ−1
k Xk A ∆y
=
A Xk e − σk µk Z−1
k e
∆zk
=
−AT ∆yk
∆xk
=
−1
k
−Xk e + σk µk Z−1
k e − Zk Xk ∆z
(5.12)
Passo 4: (Atualização)
xk+1 , yk+1 , zk+1 = xk , yk , zk + αk ∆xk , ∆yk , ∆zk
Faça k = k + 1 e volte ao passo 2.
Na Fase I do algoritmo calculamos uma solução inicial para o problema e na Fase II, calculamos a direção de
busca e atualizamos a solução até obtermos a solução ótima.
5.4 Método de Redução de Potencial (RP)
O Método de Redução de Potencial é uma variante dos algoritmos que usam passos de Newton e parte de uma
classe maior de métodos, denominados Métodos de Penalização. De um modo geral, um método de penalização
2 Método
especı́fico para matrizes do tipo definida positiva.
85
PL
modifica a função objetivo acrescentando um termo que (i) aumente muito seu valor quando determinada condição
de controle é violada e (ii) tende a zero quando nos aproximamos da solução ótima. Este termo é conhecido
usualmente de função de barreira ou função potencial.
Karmarkar usou uma função potencial para a Programação Linear sob a forma:
n
X
ρ log cT x − L −
log xi
i=1
onde ρ = n + 1 e L é um limite inferior para o valor da função objetivo, provando sua convergência e resultados de
complexidade por mostrar que sua função diminui, pelo menos um valor constante em cada iteração. Por exemplo,
para o problema:
min
x1
+
S. a
x1
+
x2
x3
x2
x1 ,
x2 ,
+
x3 ,
=
1
x4
=
1
x4
≥ 0
cujo o tipo é um quadrado de lado 1 no plano (x1 , x2 ), a função de Karmarkar torna-se: Φ(x1 , x2 ) = 3 log(x1 +x2 )−
log x1 − log x2 . Observe a Figura 5.1 como a função decresce rapidamente na imediação do ótimo, x∗ = (0, 0).
1.5
1
0.5
0
-0.5
-1
-1.5
0
0.5
1.5
0.4
1
0.5
0.3
0
0.2
0.1
0.2
0.3
0.4
0.50
0.1
0.2
0.3
0.4
0.5
-0.5
0.1
-1
0
-1.5
0
0.1
0.2
0.3
0.4
0.5
Figura 5.1: Gráfico e curvas de nı́vel de Φ(x1 , x2 ).
Depois da publicação do algoritmo de Karmarkar, houve muitos avanços nos algoritmos que usam esta função;
porém a maioria das novas técnicas ainda baseava-se nos valores das variáveis primais. A partir de 1987 os
algoritmos passaram a utilizar de forma mais balanceada variáveis primais-duais. Nessa linha temos a função de
potencial primal-dual de Tanabe-Todd-Ye, definida por:
Φρ (x, y) = ρ log xT z −
n
X
log xi zi
(5.13)
i=1
para um parâmetro ρ > n.
Os algoritmos baseados em Φρ usam a função potencial apenas para monitorar o “progresso”e provar a convergência. Este progresso refere-se ao potencial atribuı́do a cada ponto de Ω0 por Φρ e que diminui a medida
que nos aproximamos da solução. Como todos os algoritmos baseados na estrutura primal-dual, o algoritmo de
redução de potencial obtém sua direção de busca pela execução de (5.12) para algum σk ∈ (0, 1). O tamanho do
passo αk é escolhido para minimizar Φρ ao longo da direção de busca.
86
PL
Voltando a equação (5.13), faremos algumas modificações algébricas para extrairmos algumas propriedades de
Φρ . Primeiramente vamos somar e subtrair dois novos termos, como segue:
Φρ (x, y) = ρ log xT z − n log xT z −
n
X
log xi zi + n log xT z − n log n + n log n.
i=1
Aplicando as propriedades de logaritmos:
Φρ (x, y)
=
⇒ Φρ (x, y)
=
h
x1 z1
x2 z2
xN zn i
ρ log xT z − n log xT z − log T n + log T n + . . . + log T n + n log n,
x z
x z
x z
n
X
xi zi
(ρ − n) log xT z −
log xT z + n log n
i=1
n
Ou seja, podemos rescrever a função (5.13) da seguinte maneira:
Φρ (x, y) = (ρ − n) log xT z −
n
X
i=1
log
xi zi
xT z
n
+ n log n.
(5.14)
De (5.14) percebemos que Φρ faz o balanceamento entre dualidade e centralidade. Se xT z é pequeno, favorecemos
xT z
a dualidade e se nenhum xi zi é muito menor do que a média µ =
, favorecemos a centralidade.
n
Duas propriedades importantes podem ser então observadas:
1. Φρ → +∞ se xi zi → 0, para algum i , mas µ =
xT z
não tende a zero;
n
2. Φρ → −∞ se, e somente se (x, y, z) → Ω0 .
De acordo com as condições de KKT, só estaremos no ótimo se xT z = 0. Portanto, é desejável que o método
aproveita a função de barreira de modo a forçar µ → 0.
A propriedade (1) é o efeito de barreira, pois para que µ → 0, todas as componentes de xT z devem ir a zero.
Caso só algumas tendam a zero, Φρ → +∞, funcionando
então como uma barreira.
!
n
X
xi zi
log xT z + n log n tem um limite inferior. Portanto, Φρ → −∞ se, e somente
Por outro lado, o termo −
i=1
n
se (ρ − n) log xT z → −∞, o que implica que xT z → 0. Então, o método de Redução de Potencial gera iterações
no sentido de levar µ → 0, usando informações fornecidas por estas duas propriedades.
Algoritmo de Redução de Potencial Primal-Dual
n
, onde ρ < n é o parâmetro de (5.14). O passo αk é escolhido para minimizar
ρ
Φρ (·) ao longo da direção de busca e mantendo a viabilidade.
Este algoritmo toma σk =
Algoritmo RP
Fase I
Passo 1: (Inicialização) Faça k = 0, ρ > n e encontre (x0 , y0 , z0 ) ∈ Ω0 .
Fase II:
Passo 2: (Otimalidade) Se o ponto (xk , yk , zk ) satisfaz os critérios de otimalidade, pare.
87
PL
Passo 3: (Cálculo da direção de busca) Seja σk =
n
e resolva (5.12) para obter (∆xk , ∆yk , ∆zk ).
ρ
Passo 4: (Cálculo do tamanho do passo) Calcule:
αmax = sup {α ∈ [0, 1] / (x, z) + α(∆x, ∆z) ≥ 0} ,
e escolha αk de αk = ar g minα∈(0,αmax ) Φρ (xk + α∆xk , zk + α∆zk ).
(xk+1 , yk+1 , zk+1 ) = (xk , yk , zk ) + αk (∆xk , ∆yk , ∆zk ).
5.5 Implementação de Algoritmos de Pontos Interiores
Na seção 5.3.2 definimos uma estrutura geral para o algoritmo Primal-Dual e na seção 5.4 definimos algumas
variantes desta estrutra. Porém, durante estas seções, tomamos como conhecida uma solução inicial e omitimos
o critério de parada do algoritmo. Trataremos nesta seção destes tópicos, bem como de uma estrutura mais
“completa” para o algoritmo Primal-Dual.
5.5.1 Solução Inicial
Até aqui, discutimos sobre algoritmos de Pontos Interiores, supondo conhecida uma solução inicial. A dificuldade
em obter uma solução inicial é equivalente a de aplicar o algoritmo até a solução ótima; por isso, muitos algoritmos
teóricos assumem a existência de um ponto inicial e o usam para inicializar o algoritmo. O processo de encontrar
uma solução inicial é conhecida como “Fase I” do algoritmo e o processo de resolver o algoritmo até a otimalidade,
de “Fase II”. Então, nesta seção, abordaremos a Fase I do algoritmo Primal-Dual.
Seja (x0 , y0 , z0 ) com (x0 , z0 ) > 0 uma solução primal-dual inicial inviável. Para obter uma solução viável
considere os seguintes problemas primal e dual artificiais:
(PPA)
min
cT x + MP xn+1
S. a
Ax + (b − Ax0 )xn+1
T 0
0
T
(A y + z − c) x + xn+2
=
=
(x, xn+1 , xn+2 ) ≥
b
MD
0
e
max
bT y + MD ym+1
S. a
AT y + (AT y0 + z0 − c)ym+1 + z
(PDA)
(b − Ax0 )T y + zn+1
ym+1 + zn+2
(z, zn+1 , zn+2 )
= c
= MP
=
0
≥ 0
onde xn+1 e ym+1 são variáveis artificiais primal e dual, respectivamente, com seus coeficientes de custo artificiais
MP e MD . O coeficiente dessas variáveis na primeira restrição de (PPA) e na primeira de (PDA) correspondem
a uma medida de inviabilidade da apriximação inicial. A variável xn+2 corresponde à variável dual artificial ym+1 e
zn+1 , zn+2 são variáveis duais de folga correspondentes a xn+1 e xn+2 . Essas variáveis são necessárias para manter
a relação de dualidade entre dois problemas.
Fixando-se MP e MD com valores que dominam a função objetivo primal e dual, garantimos que a direção de
busca é dominada pela direção viável. Se um ponto viável existe, então durante o processo iterativo as variáveis
88
PL
artificiais gradualmente convergem para zero.
Podemos escolher MP e MD de maneira que:
MP > (b − Ax0 )T y0 ,
(5.15)
MD > (AT y + z0 − c)T x0 ,
(5.16)
e
0
0
0
0
0
então (x0 , xn+1
, xn+2
) e (y0 , ym+1
, z0 , zn+1
, zn+2
) são soluções viáveis para os problemas artificiais (PPA) e (PDA),
respectivamente.
0
0
0
0
0
Os valores de xn+1
, xn+2
, ym+1
, zn+1
e zn+2
podem ser obtidos como segue.
Seja Ax + (b − Ax0 )xn+1 = b e tomemos x = x0 . Então:
0
Ax0 + (b − Ax0 )xn+1
=
b
0
=
0
b(1 − xn+1
)
Ax (1 −
0
xn+1
)
(5.17)
Mas a segunda equação de (5.17) só será verdadeira quando:
0
1 − xn+1
0
xn+1
= 0
= 1
(5.18)
Procedendo analogamente para AT y + (AT y0 + z0 − c)ym+1 + z = c, obtemos:
ym+1 = −1.
(5.19)
Das demais restrições obtemos:
0
xn+2
= MD − (AT y0 + z0 − c)T x 0 ,
0
zn+1
= MP − (b − Ax0 )T y 0 ,
0
zn+2
=
(5.20)
1.
A partir daqui, buscamos as soluções de (PPA) e (PDA) de maneira que se relacionam com os problemas
originais (PP) e (PD), respectivamente, de acordo com o Teorema a seguir.
Teorema 4. Sejam x∗ e (y∗ , z∗ ) soluções ótimas dos problemas originais (PP) e (PD), respectivamente. Suponha
que:
MP > (b − Ax0 )T y0 ,
e
MD > (AT y + z0 − c)T x0 .
Então as duas afirmações abaixo são verdadeiras:
1. Uma solução viável (x, x n+1 , x n+2 ) de (PPA) é um ponto de mı́nimo se, e somente se x resolve (PP) e
x n+1 = 0.
2. Uma solução viável (y, y m+1 , z, z n+1 , z n+2 ) de (PDA) é um ponto de máximo se, e somente se (y, z) resolve
(PD) e y m+1 = 0.
Observe que este é exatamente o método do M-Grande, tradicionalmente usado em associação com o Simplex
e aqui adaptado para os métodos primais-duais.
89
PL
5.5.2 Critério de Parada
Ao contrário do método Simplex, o algoritmo de Ponto Interior Primal-Dual nunca encontra uma solução exata
para o problema PL. Por isso, o algoritmo precisa usar um critério de parada para decidir quando a iteração corrente
está próxima o suficiente da solução ótima.
Muitos algoritmos consideram uma boa solução aproximada a solução que possui os resı́duos primal rb = Ax − b
e dual rc = AT y + z − c e a métrica dual µ suficientemente pequenos. Para esse fim pode-se usar medidas relativas
diminuindo os problemas de escala dos dados. Testes tı́picos para uma solução (x, y, z) são:
krb k
1 + kbk
krc k
1 + kck
=
=
kAx − bk
≤ τ1
1 + kbk
kAT y + z − ck
≤ τ1
1 + kck
|cT x − bT y|
≤ τ1
1 + |cT x|
(5.21)
onde τ1 é a tolerância. Naturalmente outros critérios podem ser adotados em concordância com a aplicação a um
problema especı́fico.
5.5.3 Algoritmo Primal-Dual
Como último tópico deste capı́tulo, daremos uma estrutura mais “completa” do algoritmo primal-dual.
Fase I
Passo 1: (Inicialização) Faça k = 0 e encontre (x0 , y0 , z0 ) ∈ Ω0 uma solução inicial e defina τ1 ≥ 0 uma tolerância
suficientemente pequena.
Fase II
Passo 2: (Otimalidade) Se
krb k
1 + kbk
krc k
1 + kck
=
=
kAx − bk
≤ τ1
1 + kbk
kAT y + z − ck
≤ τ1
1 + kck
|cT x − bT y|
≤ τ1
1 + |cT x|
então pare. A solução encontrada é ótima.
Passo 3: (Cálculo da direção de busca) Seja σk ∈ [0, 1] e µk =
(xk )T zk
. Seja σk ∈ [0, 1]. Calcule:
n
T
k
AZ−1
k Xk A ∆y
=
A Xk e − σk µk Z−1
k e
∆zk
=
−AT ∆yk
∆xk
=
−1
k
−Xk e + σk µk Z−1
k e − Zk Xk ∆z
xk+1 , yk+1 , zk+1 = xk , yk , zk + αk ∆xk , ∆yk , ∆zk
90
CAPÍTULO
6
Programação Linear Inteira
6.1 Introdução
Como descrito em [2], problemas de Programação Linear Inteiro (PLI) pertencem a otimização discreta ou
combinatória pois algumas das variáveis fazem parte de um conjunto discreto, tipicamente, um subconjunto dos
números inteiros.
Um problema com variáveis inteiras e reais é denominada de Programação Linear Inteira Mista (PLIM) quando
tem a seguinte forma:
max
f (x, y) =
S. a
cx
+
dy
Ax
+ Dy
x
y
≤
b
∈
Rn+
∈
Zp+
em que A ∈ Rm×n , D ∈ Rm×p , c ∈ R1×n , d ∈ R1×p e b ∈ Rm×1 representando os parâmetros do problema. Os
vetores x ∈ Rn×1 e y ∈ Zp×1 as variáveis do problema. Rn+ representa o espaço dos vetores com n componentes
reais e Zp+ o espaço dos vetores com p componentes inteiras não negativas.
Quando todas as variáveis são inteiras, tem-se o problema de Programação Linear Inteira (PLI):
max
f (x) =
S. a
cx
Ax
≤
b
x
∈
Zn+
e se todas as variáveis assumem valores 0 ou 1, tem-se um problema de Programação 0-1 ou Binária (PB), escrito
como:
max
S. a
f (x) =
cx
Ax
≤
b
x
∈
Bn+
em que Bn+ representa o espaço dos vetores com n componentes binárias.
Os algoritmos de (PLI) são baseados na exploração do sucesso computacional da resolução de problemas de
Programação Linear (PL), uma vez que os problemas que tratam de soluções inteiras fazem uma busca dentro da
região factı́vel. Os algoritmos possuem três passos como estratégia de resolução, sendo:
1. Relaxar a região de soluções de PLI eliminando a restrição inteira imposta a estas variáveis e substituindo
qualquer variável binária y pela contı́nua 0 ≤ y ≤ 1. Neste passo, transformamos um problema linear inteiro
Capı́tulo 6. Programação Linear Inteira
PL
em um problema linear (PL).
2. Faz-se então a resolução do PL relaxado e identifica-se uma solução ótima contı́nua. A resolução desta etapa
pode ser através dos métodos já aprendidos anteriormente, como o Método Simplex.
3. Começando do ponto ótimo contı́nuo, adicionam-se restrições especiais que modifiquem iterativamente a
região de soluções de PL de maneira que, a certa altura, resultará em um ponto extremo ótimo que deverá
satisfazer os requisitos de integralidade.
Os algoritmos existentes desenvolvidos para PLI, executam a etapa 3 acrescentando restrições especiais. São
dois os métodos mais conhecidos: branch-and-bound (B&B) e planos de corte. Apresentaremos aqui uma introdução ao algoritmo B&B.
6.2 Algoritmo Branch-And-Bound (B&B)
Explicaremos neste tópico, com o auxı́lio de um exemplo numérico, os detalhes envolvidos no método do B&B
geral.
Exemplo 25. Seja o PLI abaixo:
max
S. a
f (x) =
5x1
+
4x2
x1
+
x2
≤
5
(R1)
10x1
+
6x2
≤
45
(R2)
x1 ,
x2
≥
0
x1 ,
x2
∈
Z2+
(6.1)
Os pontos de grade da figura 6.1 definem a região de soluções do problema de PLI.
Figura 6.1: Região de soluções de PLI (grade de pontos) e de PL1 (hachura).
A solução do problema (6.1) relaxado, ilustrado pela figura 6.1 (denominado como PL1), é dada pelos vértices
das duas restrições, ou seja, x1 = 3.75; x2 = 1.25 e f (x) = 23.75.
92
PL
Como a solução ótima do problema relaxado não satisfaz a condição de integralidade, o algoritmo B&B modifica
a região de soluções de modo a identificar a solução ótima do problema de PLI. Primeiramente, selecionamos uma
das variáveis inteiras cujo valor ótimo em PL1 seja não inteiro. Selecionamos a variável x1 = 3.75, tomando
3 < x1 < 4 da região de soluções de PL1 com nenhum valor inteiro de x1 , podendo retirá-la da região total. Esse
passo faz surgir dois problemas de PL que são equivalentes ao PL1. A região criada é apresentada na figura 6.2,
elaborada como:
Região PL2 = Região PL1 + (x1 ≤ 3)
Região PL3 = Região PL1 + (x1 ≥ 4)
Figura 6.2: Região de soluções de PL2 e PL3.
Se usarmos esta lógica para eliminar a condição de integralidade gerando regiões relaxadas impondo restrições
adequadas (que cercam a condição de valores inteiros para as variáveis), teremos PLs cujos pontos extremos ótimos
satisfaçam as restrições inteiras. Na verdade, resolveremos o PL1 lidando com uma sequência de PLs contı́nuos.
As novas restrições, x1 ≤ 3 e x1 ≥ 4 são mutuamente exclusivas, de modo que PL2 e PL3 nos “nós” 2 e 3
devem ser tratadas como PLs separadas, como mostra o esquema da figura 6.3.
Essa dicotomização dá origem ao termo ramificação no algoritmo B&B, sendo neste caso, x1 denominada de
variável de ramificação. Como observado, no esquema (figura 6.3) apresentamos a solução de cada ramificação,
entretanto, mostraremos como montar cada um dos PLs.
O PLI ótimo se encontra em PL2 ou em PL3. Em consequência, os dois subproblemas devem ser examinados
e escolhemos arbitrariamente PL2 para ser o primeiro:
max
S. a
f (x) =
5x1
+
4x2
x1
+
x2
≤
10x1
+
6x2
≤ 45
x1
x1 ,
x2
5
≤
3
≥
0
(6.2)
Resolvendo o problema (6.2), chegamos na resposta da ramificação 2 do esquema da figura 6.3.
93
PL
1
PL1
x1 = 3.75, x2 = 1.25
f (x) = 23.75
x1 ≤ 3
x1 ≥ 4
2
PL2
x1 = 3, x2 = 2
f (x) = 23
Limite inferior
3
PL3
x1 = 4, x2 = 0.83
f (x) = 23.33
Figura 6.3: Utilização da variável de ramificação x1 para criar PL2 e PL3.
Note que a solução de PL2 apresenta valores inteiros para as variáveis x1 e x2 , deste modo dizemos que o
problema é incumbente e que não precisa ser mais investigado, pois não pode dar nenhuma solução melhor para
o PLI com esta ramificação. Entretanto, não podemos ainda afirmar que esta solução é a melhor solução para o
problema original pois, o PL3 ainda pode fornecer um valor melhor para f (x).
Afirmamos apenas que f (x) = 23, encontrada em PL2, é o limite inferior do valor ótimo para a função
objetivo, isto é, qualquer subproblema não examinado que apresente um valor menor que este deve ser descartado
como não promissor. Já se ele produzir uma solução melhor, atualizamos o valor do limite inferior como sendo o
desta nova solução.
Como f (x) = 23.75 em PL1 e todos os coeficientes da função objetivo são inteiros, é impossı́vel, para este
caso, que PL3 produza uma solução inteira melhor com f (x) > 23, assim descartamos PL3.
O algoritmo B&B agora está completo porque ambas, PL2 e PL3, foram examinadas e descartadas (a primeira
por produzir uma solução inteira e a segunda por não ser capaz de melhorar tal solução). Assim, concluı́mos que a
solução ótima do PLI está associada com o limite inferior encontrado em PL2, ou seja, x1 = 3; x2 = 2 e f (x) = 23.
Agora poderemos mostrar mais sobre como funciona o algoritmo B&B. Baseado no problema do exemplo 25,
e se:
1. No PL1, em vez de x1 escolhessemos x2 como variável de ramificação?
2. Ao selecionar o próximo subproblema a ser examinado, resolvessemos PL3 em vez de PL2?
Se fizermos a alteração sugerida no item 1 e 2, os cálculos resultantes mudarão, como veremos a seguir. A
figura 6.4 mostra todos os subproblemas envolvidos.
A criação dos subproblemas PL4 e PL5 advém da solução não inteira de PL3. Temos então:
Região PL4 = Região PL3 + (x2 ≤ 0) = Região PL1 + (x1 ≥ 4) + (x2 ≤ 0)
Região PL5 = Região PL3 + (x2 ≥ 1) = Região PL1 + (x1 ≥ 4) + (x2 ≥ 1)
Agora, temos três subproblemas a serem examinados: PL2, PL4 e PL5. Suponha que optemos por examinar
PL5 em primeiro lugar. O PL5 não tem nenhuma solução e, em decorrência, está descartado. Em seguida,
94
PL
1
PL1
x1 = 3.75, x2 = 1.25
f (x) = 23.75
x1 ≥ 4
x1 ≤ 3
2
3
PL2
x1 = 3, x2 = 2
f (x) = 23
Limite inferior
PL3
x1 = 4, x2 = 0.83
f (x) = 23.33
x2 ≤ 0
x2 ≥ 1
4
5
PL4
x1 = 4.5, x2 = 0
f (x) = 22.5
PL5
x1 ≥ 4
Sem solução.
x1 ≤ 5
6
7
PL6
x1 = 4, x2 = 0
f (x) = 20
PL7
Sem solução.
Figura 6.4: Árvore B&B alternativa.
examinamos PL4. A solução ótima é x1 = 4.5; x2 = 0 e f (x) = 22.5. O valor não inteiro de x1 leva a dois ramos
x1 ≤ 4 e x1 ≥ 5, e à criação dos subproblemas PL6 e PL7 com base em PL4.
Região PL6 = Região PL1 + (x1 ≥ 4) + (x2 ≤ 0) + (x1 ≤ 4)
Região PL7 = Região PL1 + (x1 ≥ 4) + (x2 ≤ 0) + (x1 ≥ 5)
Agora, os subproblemas PL2, PL6 e PL7 precisam ser examinados. Selecionando PL7, o problema não tem
nenhuma solução viável e, portanto, está descartado. Em seguida, selecionamos PL6, sendo que este problema dá
a primeira solução inteira (x1 = 4; x2 = 0 e f (x) = 20) e, assim, fornece o primeiro limite inferior para o valor
ótimo da função objetivo para PLI.
Ficamos ainda com PL2, que dá uma solução inteira melhor, como visto no exemplo. Deste modo, o limite
inferior é atualizado e nesse ponto, com todos os subproblemas interpretados, a melhor solução é a encontrada
para PL2. A sequência de solução apresentada na figura 6.4 (PL1 → PL3 → PL5 → PL4 → PL7 → PL6 → PL2)
é a pior hipótese de passos possı́veis para o problema do exemplo 25, pois foram percorridos todos os ramos antes
95
PL
de encontrarmos a solução ótima.
Dos dois cenários apresentados anteriormente, podemos concluir que a execução do método B&B não garante
uma solução PLI global1 , apenas de soluções locais (dependendo do tamanho e complexidade do problema).
Podemos utilizar outros algoritmos matemáticos auxiliares ao B&B, como o algoritmo de Planos de Corte2 , que
atuando em conjunto com algoritmo B&B forma o algoritmo chamado de Branch-and-Cut.Ainda, como visto, o
algoritmo pode caminhar em dois sentidos na procura da soluo tima, isto , verticalmente (busca em profundidade)
e horizontalmente (busca em largura).
Os métodos heurı́sticos3 podem ser aplicados também para melhorar a qualidade da solução e/ou auxiliar na
decisão de qual ramo seguir. Há casos em que aplica-se apenas técnicas heurı́sticas na solução de um problema de
PLI, pois os métodos convencionais não são capazes de fornecerem respostas ao problema.
6.2.1 Resumo do algoritmo Branch-And-Bound (B&B)
Considere um problema de maximização e estabeleça um limite inferior inicial f (x) = −∞ para o valor dos
coeficientes da função objetivo ótima do PLI. Seja i = 0.
1. Selecione um PLi , o próximo subproblema a ser examinado. Resolva o PLi e tente interpretá-lo usando uma
das três condições:
• O valor ótimo de f (x) do PLi não pode dar um valor objetivo melhor do que o limite inferior atual;
• O PLi fornece uma solução inteira viável melhor do que o limite inferior atual;
• O PLi não tem nenhuma solução viável.
Surgem dois casos:
• Se o PLi for interpretado e uma solução for encontrada, atualize o limite inferior. Se todos os subproblemas tiverem sido descartados, pare; o PLI ótimo está associado com o limite inferior finito atual. Se
não existir nenhum limite inferior finito, o problema não tem nenhuma solução viável. Senão, determine
i = i + 1, e repita a etapa 1 novamente.
• Se o PLi não for interpretada, vá para a etapa 2 e ramifique.
2. Selecione uma das variáveis inteiras xj , cujo valor ótimo xj∗ na solução do PLi seja não inteiro. Elimine a
região:
bxj∗ c < xj < bxj∗ c + 1
(onde bv c define o maior inteiro ≤ v 4 ), criando dois subproblemas de PL que correspondem a
bxj∗ c ≥ xj e xj ≥ bxj∗ c + 1
Determine i = i + 1, e vá para a etapa 1.
As etapas dadas se aplicam a problemas de maximização. Para minimização, substituı́mos o limite inferior por
um limite superior (cujo valor inicial é f (x) = +∞).
1 Solução
global: melhor solução para o problema.
Mátodo de Planos de Corte não serão tratados neste texto, porém a idéia do método é a de incorporar restrições que aproximem
a região relaxada ao conjunto de pontos inteiros factı́veis.
3 Métodos heurı́sticos são métodos (ou técnicas) sem um detalhado rigor matemático, podendo ser especı́fico para classes de
problemas.
4 Como exemplo, considere x = 3.8, assim bx ∗ c = 3 e o intervalo 3 < x < 4.
j
j
j
2O
96
PL
O algoritmo B&B pode ser estendido diretamente a problemas mistos (nos quais apenas algumas das variáveis
são inteiras). Se uma variável for contı́nua, simplesmente nunca a selecionamos como uma variável de ramificação.
Um subproblema viável fornece um novo limite para o valor dos coeficientes da função objetivo se os valores das
variáveis discretas forem inteiras e se o valor da função objetivo for melhor em relação ao limite atual.
Após a explicação e a sı́ntese do algoritmo Branch-and-Bound, vamos citar dois grandes tipo de problemas que
fazem uso do algoritmo para suas respectivas resoluções. O primeiro é o problema de circuitos entre cidades, no
qual um caixeiro-viajante faz suas vendas e entregas, isto é, o problema do caixeiro-viajante; o segundo é um
problema de alocação de recursos em um determinado espaço compartimentado, como uma mochila, constituindo
então, o problema da mochila.
6.3 Problema do Caixeiro-Viajante
Historicamente, o problema do caixeiro-viajante5 tenta encontrar uma rota fechada mais curta (ou com menor
custo) entre n cidades, onde cada cidade é visitada exatamente uma vez, evitando subcircuitos, ou seja, dado um
determinado caminho, se este for percorrido poderá apenas chegar em outros caminhos conectados, não sendo
possı́vel excluir ou voltar pelo mesmo caminho. Essa classe de problemas é um dos mais estudados em matemática
computacional e sua aplicação varia entre obter a melhor rota de uma frota de ônibus, logı́stica de embarque e
desembarque de passageiros em aerportos, tráfego de rede de computadores, entre outros.
Especificamente, em uma situação de n cidades, definimos:
(
xij =
1, se o caixeiro vai diretamente da cidade i à cidade j, i 6= j
0, caso contrário
Dado que dij é a distância da cidade i à cidade j, o problema é dado por
min f (x) =
n X
X
dij xij
i=1 j>i
S. a
X
xji
+
j<i
X X
X
xij
=
2
,i =1:n
(6.3)
j>i
xij
+
i∈S j ∈S,
/ j>i
X X
xij
≥
2
, S ⊂ N, 3 ≤|S|≤
i ∈S
/ j∈S, j>i
x
∈
jnk
2
Bn(n−1)/2
A função objetivo do problema (6.3) expressa a minimização da distância total da rota, a primeira restrição impõe
que cada cidade tenha somente uma cidade sucessora imediata e uma cidade predecessora imediata. A segunda
restrição elimina sub-rotas pois para cada conjunto S, existem no mı́nimo duas arestas entre as cidades de S e as
cidades não pertencentes a S. A cardinalidade
de S é no mı́nimo 3 (três), pois um ciclo em um grafo não orientado
jnk
tem pelo menos 3 nós e no máximo
, pois ao se eliminar ciclos com k nós, eliminam-se ciclos com n − k nós
2
(vide figura 6.5 (c)). A última restrição indica o tipo de variáveis.
A figura 6.5 apresenta possı́veis cenários de um TSP com 5 cidades, onde os circulos representam as cidades
e as linhas, conhecidas como arcos, as ligações entre estas cidades, neste caso abordado são rotas de duas vias
(simetria – ida e volta), como mostra a figura 6.5 (a). O item (b) apresenta uma possı́vel solução (ótima ou viável)
para este exemplo gráfico e o item (c) uma solução de subcircuitos (solução inviável).
5 O problema do caixeiro viajante aparece na literatura (estrangeira ou nacional) com a sigla TSP que é a abreviatura de traveling
salesman problem.
97
PL
2
2
3
3
1
1
5
5
4
4
(b) Solução do circuito.
(a) Problema com 5 cidades.
2
3
1
5
4
(c) Solução de subcircuitos.
Figura 6.5: Exemplo do problema do caixeiro-viajante com 5 cidades.
6.4 Problema da Mochila
Este problema lida com uma questão de situação na qual um ı́ndividuo deve decidir quais são os itens mais
valiosos para carregar em uma mochila, podendo se estender a situações de corte e empacotamentos e até carregamentos de veı́culos de determinadas dimensões. Sendo então, uma generalização metafórica para um problema
geral de alocação de recurso no qual um único recurso limitado é designado a várias alternativas com o objetivo
de maximizar o retorno total.
6.4.1 Mochila 0-1
Um exemplo de problema da mochila 0-1 é a seleção de projetos, como descrito em [2]. Considere n projetos
e um capital b para investimento. O projeto j tem um custo aj e um retorno esperado pj . O problema consiste
em selecionar os projetos que maximizam o retorno total esperado sem ultrapassar o limite de capital.
98
Defina as variáveis:
PL
(
xj =
1
0
se o produto j é selecionado
caso contrário
O problema é, então, formulado como:
n
X
max f (x) =
j=1
n
X
S. a
pj xj
(6.4)
aj xj
≤
b
x
∈
Bn
j=1
A função objetivo do problema (6.4) expressa a maximização do retorno esperado, a primeira restrição indica que
o capital b não pode ser excedido e a última restrição representa o tipo de variáveis.
Esse problema é denominado problema da mochila devido à analogia do problema que envolve a decisão de
quais itens carregar em uma mochila sem exceder um dado limite de peso.
Exemplo 26. Considere um capital para investimento b = 100, n = 8 projetos e os seguintes vetores de parâmetros:
p = [pj ] = [41 33 14 25 32 32 9 19]
a = [aj ] = [47 40 17 27 34 23 5 44]
A solução ótima é dada por x2 = x4 = x6 = x7 = 1. Esta solução utiliza 40 + 27 + 23 + 5 = 95 unidades do capital.
6.4.2 Mochila Inteira
Neste problema, a variável de decisão xj ≥ 0, j = 1 : n, pode assumir um valor inteiro não negativo, isto é,
pode-se levar diversas unidades do mesmo item na mochila. A formulação é idêntica à da mochila 0-1, ao substituir
x ∈ Bn por x ∈ Zn+ .
6.4.3 Múltiplas Mochilas
Considere n itens que devem ser colocadas em m mochilas de capacidades distintas bi , i = 1 : m. Cada item
j tem uma lucratividade pj e um peso wj e o problema consiste em selecionar m subconjuntos distintos de itens,
tal que cada subconjunto ocupe uma capacidade de no máximo bi e o lucro total seja maximizado. Este problema
ocorre em situações de carregamento de contêineres e em situações de corte nas indústrias de papel e aço.
(
xij =
1
0
se o item j é colocado na mochila i
caso contrário
O problema é formulado como:
max f (x) =
S. a
n X
n
X
pj xij
i=1 j=1
n
X
wj xij
≤
bi
i =1:n
≤
1
j =1:n
∈
Bmn
(6.5)
j=1
X
xij
i=1
x
99
PL
A função objetivo do problema (6.5) representa a maximização do lucro total, a primeira restrição garante que a
capacidade bi da mochila i não pode ser excedida, a segunda restrição indica que se o item j é escolhido, então ele
é colocado em um única mochila e a última restrição representa o tipo de variáveis.
6.4.4 Empacotamento de Mochilas
No problema anterior, o número de mochilas é dado e alguns itens podem não ser colocados nas mochilas. No
problema de empacotamento em mochilas, conhecido como bin packing, deseja-se determinar o número mı́nimo de
mochilas de mesma capacidade b que empacotem n itens de peso wj , j = 1 : n. Este é um dos diversos problemas
de empacotamento, que envolvem também o arranjo de objetos em dispositivos bidimensionais e tridimensionais6 ,
tais como nos problemas de carregamentos de produtos sobre paletes ou dentro de contêineres ou caminhões.
(
1, se a mochila i é usada
yj =
0, caso contrário
(
e
xij =
1,
se o item j é colocado na mochila i
0, caso contrário
Têm-se, então, a seguinte formulação:
min f (x) =
n
X
yi
i=1
S. a
X
≤ 1
j =1:n
wj xij
≤ byi
i =1:n
x
∈
Bmn
y
∈
Bn
i=1
n
X
xij
(6.6)
j=1
A função objetivo do problema (6.6) minimiza o número de mochilas. Note que o limitante superior do número
de mochilas é igual ao número de itens n. O conjuto de equações expresso pela primeira restrição asseguram que
cada item j é colocado em uma única mochila, o conjunto de equações expresso pela segunda restrição impõem
que se a mochila é usada, então sua capacidade b não pode ser excedida. Finalmente, as duas últimas restrições
indicam o tipo das variáveis.
6 Problemas
de carregamento tridimensionais são complexos e usualmente resolvidos por métodos heurı́sticos.
100
PL
1. Desenvolva a árvore do B&B para cada um dos seguintes problemas. Por conveniência, sempre selecione x1
como a variável de ramificação no primeiro nó.
(c)
(a)
max
f (x) =
S. a
max
5x1
+
7x2
2x1
+
x2
≤
13
9
0
5x1
x1 ,
+
9x2
x2
≤
≥
41
0
Z
x1 ,
x2
∈
Z
3x1
+
2x2
2x1
+
5x2
≤
9
4x1
x1 ,
+
2x2
x2
≤
≥
x2
∈
x1 ,
f (x) =
S. a
(b)
max
f (x) =
S. a
x1
+
x2
2x1
+
5x2
≤ 16
6x1
+
5x2
≤ 27
x1 ,
x2
≥
0
x1 ,
x2
∈
Z
2. Mostre graficamente que o seguinte problema de PLI não tem nenhuma solução viável e então verifique o
resultado usando B&B.
max
f (x) =
S. a
2x1
+
x2
10x1
+
10x2
≤
9
10x1
+
5x2
≤
1
x1 ,
x2
≥
0
x1 ,
x2
∈
Z2+
3. Resolva o problema de programação inteira:
max f (x) =
S. a
x1
+
x2
−2x1
+
2x2
≤
3
7x1
+
3x2
≤
22
x2
∈
Z2+
x1
(a) Graficamente.
(b) Pelo método branch-and-bound.
4. Agora vamos à um problema de um caixeiro-viajante, que na verdade é um representante comercial e vendedor
de publicações literárias. Este profissional mora na cidade de Basin, e deve visitar uma vez por mês quatro
clientes localizados nas cidades de Wald, Bom, Mena e Kiln. A tabela 6.1 dá as distâncias em milhas entre
as diferentes cidades.
O objetivo é minimizar a distância total percorrida pelo vendedor, formule então a questão como um problema
de PLI7 .
7 Se
houver dificuldade na formulação, observe o exemplo da página 172 de [14].
101
PL
Basin
Wald
Bon
Mena
Kiln
Basin
0
120
220
150
210
Milhas entre as cidades
Wald Bon Mena Kiln
120
220
150
210
0
80
110
130
80
0
160
185
110
160
0
190
130
185
190
0
Tabela 6.1: Distâncias entre as cidades.
5. Um ecologista brasileiro, trabalhando na Amazônia, foi contratado para realizar a divisão de parte da floresta
em reservas florestais. Estudos recentes dividiram a floresta em dez regiões. O trabalho do ecologista
consiste em formar cinco reservas a partir dessas informações, observando o número de predadores e presas
que cada região contém. A tabela 6.2 mostra esses dados para cada região (em milhares). Os animais não
podem ser removidos de sua região e cada reserva deve conter entre 80 mil e 130 mil animais. Sabe-se que o
ideal é que o número de presas deve ser maior que o número de predadores em uma reserva, para garantir o
equilı́brio entre as espécies. Formule um problema para ajudar o ecologista a formar cinco reservas garantindo
o equilı́brio.
Região
1
2
3
4
5
6
7
8
9
10
Predadores
40
29
20
25
20
19
37
10
35
35
Presas
17
24
22
22
57
32
7
11
27
32
Tabela 6.2: Número de presas e predadores por região.
6. Um caminhão de entrega de óleo de uma empresa contém cinco compartimentos, com capacidade para 2700,
2800, 1100, 1800 e 3400 galões de combustı́veis, respectivamente. A empresa deve entregar três tipos de
combustı́veis A, B e C para um cliente. Parte da demanda pode não ser atendida, mas, neste caso, a empresa
deve arcar com os custos. As demandas, penalidades por galão não entregue e o número máximo de galões
de demanda não atendidas são descritas na tabela 6.3. Cada compartimento pode levar apenas um tipo de
combustı́vel. Formule o problema de carregar o caminhão de forma a minimizar os custos de não atendimento
da demanda.
Combustı́vel
Demanda
A
B
C
2900
4000
4900
Custo por galão
não entregue
10
8
6
Máximo de demanda
não atendida
500
500
500
Tabela 6.3: Custo de combustı́veis.
102
PL
7. Experimente colocar este problema em um software como o TORA/Solver/AMPL8 . Este problema foi projetado para demonstrar o comportamento bizarro do algoritmo B&B até mesmo para problemas pequenos. Em
particular, observe como muitos subproblemas serão examinados antes do software achar o ótimo e quantos
são necessários para verificar a otimalidade. Seja o problema:
min
f (y) =
S. a
y
2(x1
+ x2
+
x3
+ ...
+ x5 )
+
y
=
15
Todas as variáveis são (0, 1)
(a) Use a opção automática do TORA para mostrar que, embora a solução ótima seja encontrada após 9
subproblemas, mais de 25.000 subproblemas são examinados antes de confirmar a otimalidade.
(b) Mostre que o Solver exibe uma experiência semelhante à do TORA. No Solver, você pode observar a
mudança no número de ramos gerados (subproblemas) na parte inferior da planilha.
(c) Resolva o problema com o AMPL e mostre que a solução obtida instantaneamente com 0 iterações
simplex MIP e 0 nós B&B. A razão para esse desenpenho superior só pode ser atribuı́da às etapas
preparatórias executadas pelo AMPL e/ou pelo resolvedor CPLEX antes de resolver o problema.
8 Para
maiores informações consulte [14].
103
CAPÍTULO
7
O Uso de Excel e do lp solve para Problemas de
Programação Linear
7.1 Introdução
A aplicação bem sucedida da Programação Matemática envolve habilidades tanto em Matemática quanto em
Computação. Neste sentido, alguns softwares foram desenvolvidos para facilitar o uso desta importante ferramenta
de decisão. Para problemas de Programação Linear (PL) podemos contar com os softwares Microsoft Office
r (ou MS-Excel), Planilha Eletrônica do ambiente Open Office, lp solve (vide [9]), CPLEX (vide [5]), entre
Excel outros. Abordaremos aqui as ferramentas para PL dos softwares Microsoft Office Excel e lp solve.
Para auxiliar na manipulação destes softwares26, tomemos o exemplo abaixo (7.1).
max
f (x) =
12x1
+
8x2
+
6x3
S. a
2x1
+
x2
+
x3
≤
3x1
+
4x2
≤
48
4x1
+
x2
+
2x3
≤
24
x3
≥
0
x1 ,
x2 ,
16
(7.1)
7.2 MS-Excel Solver
Segundo [14], no Excel Solver a planilha é o meio de entrada e saı́da para problemas de PL. As figuras 7.1,
7.2, 7.3 e 7.4 mostram as etapas de instalação.
A figura 6.1 mostra em destaque o menu principal da Planilha Excel. Neste menu, selecione o ı́cone abaixo
Opções do Excel.
A figura 7.2 apresenta a janela previamente escolhida. Escolha o ı́cone Suplementos.
Na figura 7.3 utilize a opção Solver e OK.
A figura 7.4 apresenta a Planilha do Excel, cujo menu superior localiza-se em Dados. Neste ambiente, o ı́cone
Solver encontra-se à direita.
Finalizada a etapa de instalação, podemos utilizá-lo para a resolução de problemas de Programação Matemática.
Na figura 7.5 apresentamos os dados de entrada do problema (7.1). Note que a primeira linha e primeira coluna
foram utilizadas apenas para apresentar os tı́tulos. As colunas B, C e D entre as linhas 2 até 5 (células B2:D5) e
coluna G entre as linhas 2 até 4 (células G2:G4) são os dados de entrada do problema.
Capı́tulo 7. O Uso de Excel e do lp solve para Problemas de Programação Linear
PL
Figura 7.1: 1o Passo para instalação do Excel Solver.
105
PL
106
PL
Figura 7.5: Descrição do problema.
A coluna E (células E2:E4) e célula F7 contém as equações relativas às restrições R1, R2, R3 e função objetivo.
A tabela 7.1 mostra as funções do problema (7.1) e seu posicionamento nas células adequadas.
R1
R2
R3
max f (x)
Expressão
algébrica
2x1 + x2 + x3
3x1 + 4x2
4x1 + x2 + 2x3
12x1 + 8x2 + 6x3
=B2*$B$6
=B3*$B$6
=B4*$B$6
=B5*$B$6
Fórmula na
planilha
+ C2*$C$6 +
+ C3*$C$6 +
+ C4*$C$6 +
+ C5*$C$6 +
D2*$D$6
D3*$D$6
D4*$D$6
D5*$D$6
Inserida
na célula
E2
E3
E4
F7
Tabela 7.1: Expressões algébricas.
Na prática, basta que se digite a fórmula para a célula E2 e então copie para as demais células. Para fazer isso
corretamente, devem ser usadas as referências fixas $B$6, $C$6 e $D$6, que representam as variáveis x1 , x2 e x3 .
Para programas maiores é mais eficiente digitar (ou procurar no ı́cone de fórmulas):
=SOMARPRODUTO(B2:D2;$B$6:$D$6)
na célula E2 e copiar para as demais. Agora todos os parâmetros estão prontos para serem vinculados ao solver.
A figura 7.6 mostra a janela aberta após selecionar o ı́cone Solver. Primeiramente, define-se a função objetivo
– célula $F$7, o sentido da otimização – igual a “Máx”, e as células das variáveis – $B$6:$D$6.
Estas informações deixam claro para o Solver que as variáveis definidas pelas células $B$6, $C$6 e $D$6 são
determinadas pela maximização da função objetivo na célula $F$7.
A póxima etapa é estabelecer as restrições dos problemas clicando em Adicionar na caixa de diálogo Parâmetros
do Solver. A caixa Adicionar restrições será exibida, como mostra a figura 7.7 para facilitar a digitação dos
elementos das restrições:
$E$2:$E$4 <= $G$2:$G$4
107
PL
Figura 7.6: Solver.
Figura 7.7: Relacionando as restrições.
Uma maneira de entrar com as restrições de não negatividade é clicar em Opções na caixa de diálogo Parâmetros
do Solver para acessar a caixa de diálogo Opções do Solver, como mostra a figura 7.8, selecionar Presumir não
negatividade. Pode também selecionar Presumir modelo linear.
Para resolver o problema, clique Resolver em Parâmetros do Solver. Uma nova caixa de diálogo, Resultado
do Solver dará o status da solução (figura 7.9). Se a montagem do problema estiver correta, o valor ótimo da
108
PL
Figura 7.8: Opções do Solver.
função objetivo aparecerá na célula $F$7 e os valores de x1 , x2 e x3 irão para as células $B$6, $C$6 e $D$6,
respectivamente.
Figura 7.9: Solução.
Se o problema não tiver solução viável, o Solver emitirá a mensagem explı́cita “Solver não pode achar uma
solução viável”. Se o valor objetivo ótimo for ilimitado, o Solver emitirá uma mensagem ambı́gua “Os valores das
células de destino não convergem”. Em qualquer um dos casos, a mensagem indica que há algo errado com a
109
PL
formulação do modelo.
A caixa de diálogo Resultados do Solver lhe dará oportunidade de requisitar mais detalhes sobre a solução,
incluindo o relatório de sensibilidade, como mostram as figuras 7.10, 7.11 e 7.12.
Figura 7.10: Relatório de sensibilidade.
Figura 7.11: Relatório de resposta.
110
lp solve
Figura 7.12: Relatório de limites.
7.3 lp solve
O software lp solve é um solver para problemas de Programação Linear Inteira Mista, vide [9]. Como o primeiro
passo na resolução de um problema de Programação Inteira é a de relaxar a condição de integralidade das variáveis,
ou seja, resolver um problema de Programação Linear, sua aplicabilidade é direta em PL. O software lp solve é
livre (licensa LGPL), baseado no Método Simplex Revisado (para PL) e Branch-and-Bound (para Programação
Inteira).
Note que, este solver é exclusivo para problemas lineares, ou seja, as equações do problema devem ser de
primeira ordem. Por outro lado, o Excel Solver permite a resolução de problemas não lineares.
Este software foi desenvolvido por Michel Berkelaar na Eindhoven University of Technology. O trabalho de
Jeroen Dirks fez a transição da versão básica 1.5 para a versão completa 2.0. lp solve possui uma comunidade
via Yahoo group http://groups.yahoo.com/group/lp solve/, onde vc encontra as últimas fontes, executáveis
para plataforma comum, exemplos, manuais e mensagens de ajuda sobre o lp sove.
A instalação deste software é relativamente simples e pode ser feita através do site
http://sourceforge.net/projects/lpsolve/.
Após a instalação, em ambiente Windows, aparecerá um ı́cone na sua área de trabalho permitindo o acesso
direto. A figura 7.13 apresenta a tela inicial do solver.
Considere o problema (7.1), sua implementação é direta, como mostra a figura 7.14.
No menu superior, selecione a opção Action e Solve. A tecla F9 é o atalho deste comando, como apresentado
na figura 7.15.
A figura 7.16 mostra a mensagem de resolução do problema em questão.
As janelas apresentadas pelas figuras 7.16 e 7.17 mostram o problema em forma matricial e os valores das
variáveis após o processo de otimização, respectivamente.
111
lp solve
Figura 7.13: O ambiente LP Solve.
Figura 7.14: Descrição do problema (7.1).
112
lp solve
Figura 7.15: O ı́cone de resolução.
Figura 7.16: Mensagem de resolução.
113
lp solve
Figura 7.17: Resolução na forma matricial.
Figura 7.18: Resultados das variáveis de decisão.
114
Referências Bibliográficas
[1] E. L. de Andrade. Introdução à Pesquisa Operacional: Métodos e Modelos para Análise de Decisão. Terceira Edição.
LTC, 2004.
[2] M. Arenales, V. Armentano, R. Morabito e H. Yanasse. Pesquisa Operacional. Elsevier, 2007.
[3] M. S. Bazaraa, J. J. Jarvis e H. D. Sherali. Linear Programming and Network Flows. Second Edition, John Wiley and
Sons, 1990.
[4] J. L. Boldrin, S. I. R. Costa, V. L. Figueiredo e H. G. Wetzler. Álgebra Linear. 3a Edição, Editora Harbra, 1980.
[5] http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/. Último acesso em 03 de novembro de
2010.
[6] G. B. Dantzig. Linear Programming and Extensions. Eleventh Edition, Princeton University Press, 1998.
[7] M. C. Goldbarg e H. P. L. Luna. Otimização Combinatória e Programação Linear. Editora Campus, 2000.
[8] G. Lachtermacher. Pesquisa Operacional. 4a Edição, Pearson Prentice Hall, 2009.
[9] http://lpsolve.sourceforge.net/5.5/. Último acesso em 03 de novembro de 2010.
[10] D. G. Luenberger e Y. Ye. Linear and Nonlinear Programming. Third Edition, Spinger, 2008.
[11] N. D. Pizzolato e A. Gandolpho. Técnicas de Otimização. LTC, 2009.
[12] L. A. Pinto. Métodos de Pontos Interiores para Programação Inteira. UNESP – Campus de São José do Rio Preto,
Dissertação de Mestrado, 1999.
[13] E. M. da Silva, E. M. da Silva, V. Gonçalves e A. C. Murolo. Pesquisa Operacional para os cursos de Economia,
Administraçao e Ciências Contbeis. Terceira Edição, Editora Atlas, 1998.
[14] H. A. Taha. Pesquisa Operacional. 8a Edição, Pearson Prentice Hall, 2008.
[15] R. J. Vanderbei. Linear Programming: Foundations and Extensions. Kluwer Academic Publishers, 1997.
115

Apostila

Transcrição

Documentos relacionados

Gabarito - Profmat

Prova - Profmat

142968

Sermos uma `agência modelo`, formada por um mundo de

Quest˜oes resolvidas

Modelo do trabalho - DT - Home Page

Bolo do Caco Bimby: 27 min Ingredientes: 1 c. café sal

Introdução à Pesquisa Operacional - DT

Baixar Material Teórico

Lista de exercícios 03