Programa˘c~ao Linear { PL - Unesp · Cap tulo 1. Introdu˘c~ao a Pesquisa Operacional PL 1.1Otimiza˘c~ao (C alculo Diferencial) e Sistemas de equa˘c~oes (Algebra Linear) na PO

Programacao Linear – PL

Luiza Amalia Pinto Cantao

[email protected]

Felipe Sanches Stark

[email protected]

Sumario

1 Introducao a Pesquisa Operacional 4

1.1 Otimizacao (Calculo Diferencial) e Sistemas de equacoes (Algebra Linear) na PO . . . . . . . . . . 5

1.2 Metodologia da PO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3 Tipos basicos de modelo de PO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3.1 Solucao em PO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3.2 Mais do que matematica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4 Solucao Geometrica ou grafica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.4.1 Introducao - Descrevendo um problema anterior . . . . . . . . . . . . . . . . . . . . . . . 11

1.4.2 Tipos de solucao e visualizacao grafica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.5 Exercıcios Propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 Revisao Matematica 21

2.1 Equacoes lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.1.1 Solucao de um Sistema de Equacoes Lineares . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.1.2 Operacoes elementares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.1.3 Solucao de Sistema de Equacoes Lineares, caso m = n . . . . . . . . . . . . . . . . . . . . 22

2.1.4 Metodo de Gauss-Jordan, caso m = n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.1.5 Solucao de Sistema de Equacoes Lineares, caso n > m . . . . . . . . . . . . . . . . . . . . 24

2.2 Mudanca de Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.2.1 O Pivoteamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.2.2 Selecao das variaveis basicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.2.3 Construcao da Variaveis Basicas e Variaveis Artificiais . . . . . . . . . . . . . . . . . . . . 27

2.3 Espacos Vetoriais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.3.1 Definicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.3.2 Operacoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.3.3 Combinacao Linear de Vetores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.3.4 Dimensao de um Espaco Vetorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.3.5 Base e Coordenadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.3.6 Posto (ra) de uma matriz como um Conjunto de Vetores . . . . . . . . . . . . . . . . . . . 30

2.4 Conjuntos Convexos e Combinacao Convexa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.4.1 Conjunto Convexo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.4.2 Combinacao Convexa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.4.3 Interpretacao Geometrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.4.4 Ponto Extremo de um Conjunto Convexo . . . . . . . . . . . . . . . . . . . . . . . . . . . 33


1

SUMARIO SUMARIO

3 Metodo Simplex 36

3.1 Teorema Fundamental da Programacao Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.1.1 Transicao da solucao grafica para a solucao algebrica . . . . . . . . . . . . . . . . . . . . 37

3.2 Metodo Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.2.1 Modelo de Programacao Linear em forma de equacao - Forma Padrao . . . . . . . . . . . 37

3.2.2 Forma Padrao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.2.3 Forma Canonica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.2.4 Conversao de desigualdades em equacoes com o lado direito nao negativo . . . . . . . . . 39

3.2.5 Como lidar com variaveis irrestritas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.2.6 Variaveis Nao Positivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.2.7 Transformando o Problema de Maximizacao em Minimizacao . . . . . . . . . . . . . . . . 41

3.2.8 Princıpios do Metodo Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.2.9 Metodo Simplex na forma de quadros - Tableau Simplex . . . . . . . . . . . . . . . . . . . 46

3.2.10 Analise de Casos Especiais. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.2.11 Base Artificial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.2.12 O Metodo do M-Grande . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.2.13 O Metodo das Duas Fases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

3.3 Analise de Sensibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.3.1 Analise de Sensibilidade grafica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.3.2 Analise de Sensibilidade algebrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59


4 Dualidade 69

4.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

4.2 Definicao do Problema Dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

4.2.1 Propriedades da Dualidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

4.2.2 Teoremas Fundamentais da Dualidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

4.3 Metodo Dual Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

4.3.1 Resumo do Metodo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75


5 Metodos de Pontos Interiores 80

5.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

5.2 Notacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

5.3 Metodo Primal-Dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

5.3.1 A Trajetoria Central . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

5.3.2 Estrutura Primal-Dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

5.4 Metodo de Reducao de Potencial (RP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

5.5 Implementacao de Algoritmos de Pontos Interiores . . . . . . . . . . . . . . . . . . . . . . . . . . 88

5.5.1 Solucao Inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

5.5.2 Criterio de Parada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

5.5.3 Algoritmo Primal-Dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

2

SUMARIO SUMARIO

6 Programacao Linear Inteira 91

6.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

6.2 Algoritmo Branch-And-Bound (B&B) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

6.2.1 Resumo do algoritmo Branch-And-Bound (B&B) . . . . . . . . . . . . . . . . . . . . . . . 96

6.3 Problema do Caixeiro-Viajante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

6.4 Problema da Mochila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

6.4.1 Mochila 0-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

6.4.2 Mochila Inteira . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

6.4.3 Multiplas Mochilas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

6.4.4 Empacotamento de Mochilas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100


7 O Uso de Excel e do lp solve para Problemas de Programacao Linear 104

7.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

7.2 MS-Excel Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

7.3 lp solve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

Referencias Bibliograficas 111

3

CAPITULO 1

Introducao a Pesquisa Operacional

Historico da Pesquisa Operacional

A Pesquisa Operacional (PO) e um ramo da ciencia que cuida da criacao de metodologias especıficas para

promover o gerenciamento de decisoes. A origem da PO data da Segunda Guerra Mundial (1939-1945) e tem

relacao com o esforco 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 interceptacao de avioes inimigos, estudos dentro das

divisoes aereas aliadas, para melhorar a manutencao e inspecao dos avioes, na escolha dos melhores modelos para

cada tipo de missao e no aumento da probabilidade de alvejar um submarino.

A evolucao da PO se deu de forma rapida no pos-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 gestao aerea militar e contava com a participacao do matematico George Dantzig. Durante o projeto SCOOP,

Dantzig desenvolveu um dos metodos primordiais para a resolucao de problemas envolvendo a otimizacao linear:

o SIMPLEX. Com a publicacao do metodo, a Programacao Linear (PL) tornou-se a primeira tecnica explıcita,

permanecendo ate hoje a mais fundamental das tecnicas 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 decada de 50 e 60 observado o crescimento no numero

de grupos de pesquisas operacionais e suas aplicacoes tanto em setores publicos quanto privados ao redor do globo.

E por volta do fim da decada de 60 que surgem as questoes educacionais envolvendo a PO, principalmente no

tocante da maior publicacao literaria do assunto e na presenca em cursos de pos-graduacao. Nessa epoca aparece

a area de programacao matematica, tendo como premissa casos de otimizacao de funcoes lineares sujeitos as

restricoes lineares. No Brasil, a PO iniciou-se nessa decada tambem. O primeiro simposio de PO ocorreu em 1968

no ITA, em Sao Jose dos Campos, SP. Em seguida, foi fundada a SOBRAPO (Sociedade Brasileira de Pesquisa

Operacional) que publica o periodico Pesquisa Operacional ha mais de 25 anos.

Atualmente, a PO tem sido chamada de ciencia e tecnologia de decisao. O componente cientıfico e ligado

as ideias e processos para modelar os problemas de tomada de decisao (objetivos e restricoes da operacao),

a matematica se enquadra aqui na medida em que os modelos para otimizar sistemas numericos resultam de

insercoes de dados nos modelos. A tecnologia compreende a relacao software-hardware, podendo ser generalizada

como uma tecnologia da informacao (armazenamento, comunicacao e transmissao - tanto de dados inseridos nos

modelos de otimizacao quanto nos resultados obtidos).

4

Capıtulo 1. Introducao a Pesquisa Operacional PL

1.1 Otimizacao (Calculo Diferencial) e Sistemas de equacoes

(Algebra Linear) na POOra, se a Pesquisa Operacional em seus primordios historicos era sinonimo de Otimizacao, temos entao uma

primeira ligacao com o Calculo Diferencial. Trata-se dos chamados Problemas de Valores de Maximos e Mınimos,

isto e, o ponto no qual a funcao tem sua imagem no maior e no menor valor possıvel. O grande entrave na PO

e muitas vezes a mecanizacao de como tais problemas sao passados, tornando a aprendizagem superficial e o

emprego de tais tecnicas 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 maximo, isto e,

a area da base seja a maior possıvel com um comprimento L de material (estipulado com base nos lucros e no

transporte), esse procedimento de otimizacao envolve reducao de custos, resıduos e impacto ao meio ambiente.

1. Primeiro, como trata-se de um retangulo, os lados opostos devem ter o mesmo tamanho, identificaremos a

largura de w e comprimento de l.

2. Com base na definicao 2w + 2l = L, ou seja,

w + l =L

2(1.1)

3. Por serem dimensoes fısicas da materia, tanto w quanto l devem ser positivos. Como h e estabelecido pelo

fornecedor do fabricante, nao entra nos calculos do volume, pois se acharmos a maior area teremos o maior

volume para h.

4. A area e A = wl.

Nossa questao entao e maximizar A sujeita a equacao (1.1) e das restricoes do item 3. Para tanto, devemos

proceder como um problema de valor maximo do calculo:

• Como L e um numero dado, pode ser tratado como constante, deste modo podemos deixar w em funcao de

l , ou vice-versa.

w + l =L

2=⇒ w =

L− 2l

2

• Portanto a regiao do domınio de w e l e a reta

w =L− 2l

2

na qual a imagem esta no plano z como a area A. Assim, da mesma maneira que deixamos w em funcao de

l, podemos deixar agora a area A em funcao apenas de l, substituindo o valor de w. Obtemos:

A =

(L− 2l

2

)l

Distribuindo l, temos:

A =Ll − 2l2

2

L. A. P. Cantao & F. S. Stark 5


• Agora para achar um ponto maximo (ou mınimo) executamos a derivacaoδA

δl= 0

δA

δl=

1

2(L− 4l)

Portanto se1

2(L− 4l) = 0 =⇒ L = 4l =⇒ l =

L

4

Se

w + l =L

2

Chegamos finalmente na solucao (S):

w =L

4e l =

L

4

• Concluımos que a maior area e obtida quando o retangulo e um quadrado de ladoL

4, e que seu volume

V =L2h

16

O exemplo acima (Exemplo 1) e simples, contudo, grande parte dos problemas de PO envolve numero maior

tanto de equacoes (e inequacoes) quanto de variaveis, incluindo restricoes dos valores que as variaveis podem

assumir. Como no exemplo a seguir, trabalharemos muitos conceitos de Algebra Linear (tratada na Programacao

Linear) ao longo da formulacao dos modelos e na obtencao das respostas. Nestes problemas, as variaveis e as

restricoes podem estar envolvidas em desigualdades, ou seja: o problema torna-se cada vez mais complexo a medida

em que esse fenomeno, a ser modelado, sofre diversas influencias importantes. Para efeito ilustrativo, podemos

tomar um sistema mais restrito e apenas interpretativo, vejamos entao.

Exemplo 2. Uma empresa produz dois produtos, P e Q, em cada uma de suas fabricas, X e Y. Ao fabricar tais

produtos, os poluentes dioxido de enxofre (SO2), oxido nıtrico (NOx) e material particulado (MP) sao produzidos.

As quantidades de poluentes foram monitoradas e quantificadas ( em quilogramas) e estao dispostas pela matriz:

SO2 NOx MP

P =

[300 100 150

200 250 400

]Produto P

Produto Q

O custo diario para remover cada quilograma de poluente e (em reais) dado pela matriz:

X Y

C =

16 24

14 18

30 20

Dioxido de Enxofre

Oxido nıtrico

Material Particulado

Qual o significado, por exemplo, do produto matricial de P.C ? Qual fabrica polui mais, isto e, gera mais efluente

e consequentemente tem seu tratamento encarecido?



1.2 Metodologia da POA metodologia da PO segue etapas definidas como em qualquer projeto, podendo ser decomposto em 5 estagios

basicos segundo [14]:

1. Identificacao do problema - “envolve definir o escopo do problema sob investigacao. Essa funcao deve ser

executada por toda a equipe de PO” [14]. Em PO quanto mais complexo e multidisciplinar e um problema,

maior abrangencia de conhecimento e necessaria e por consequencia uma equipe mais especializada. Nesta

etapa buscamos tres elementos basicos:

(a) descricao das alternativas de decisao;

(b) determinacao do objetivo de estudo;

(c) as limitacoes sobre as quais o modelo esta imposto.

2. Construcao do modelo -“implica uma tentativa de traduzir a definicao do problema em relacoes ma-

tematicas”[14]. Se o modelo for simples e se ajustar a um dos metodos padroes, como a programacao

linear, entao podemos chegar em solucoes com os algoritmos disponıveis. Ja se o modelo for complexo, a

equipe pode simplificar a situacao tendendo a uma abordagem heurıstica ou de simulacao. Em alguns casos,

ocorre a combinacao dos modelos matematicos, heurısticos e simuladores.

3. Determinacao da solucao do modelo -“e de longe a fase mais simples ... porque se baseia na utilizacao

de algoritmos”[14]. Neste estagio ocorre o que se chama de analise de sensibilidade, essencial quando os

parametros do modelo nao podem ser aferidos com precisao.

4. Teste e validacao da solucao proposta -“verifica se o modelo proposto ... preve adequadamente o com-

portamento do sistema em estudo” [14]. Em sistemas com uma base de dados historica (p.e. pluviosidade

em uma regiao), o modelo e valido se, sob condicoes similares de entrada, reproduz relativamente bem as

saıdas anteriores. Porem, como geralmente a analise leva em conta os dados anteriores, o parecer tende a ser

favoravel, o que exige cuidado com eventos futuros imprevisıveis. Em sistemas sem base de dados, tende-se

a comparar o modelo com simulacoes.

5. Implementacao da solucao -“envolve a traducao dos resultados em instrucoes operacionais inteligıveis ...

emitidas as pessoas que administrarao o sistema recomendado”[14].

1.3 Tipos basicos de modelo de POO uso de modelos e a essencia da propria PO, ocorrendo quando ha alta complexidade e elevado potencial de

retorno do investimento. Desta maneira, justifica-se a contratacao de uma equipe de especialistas, alocacao de

recursos disponıveis e o desenvolvimento do projeto de PO.

A criacao de um modelo implica em algo simbolico, que simplifica a realidade mediante o uso de relacoes

matematicas de algumas variaveis envolvidas, porem mantem as essencias de causa-efeito do problema estudado.

No que tange a PO, podemos ter varios exemplos classicos de modelos, entre um dos mais basicos e interessantes

temos os problemas que envolvem misturas (racoes, fertilizantes, concreto, alimentos, poluentes, entre outros).

Esses tipos de problemas consistem em combinacao de materiais (naturais ou nao) para gerar novos materiais ou

produtos com caracterısticas desejaveis, como e o caso por exemplo das misturas de massa de reboco (cal, areia,

cimento e agua) ou de concreto (areia, brita, cimento e agua), que em proporcoes diferentes ou com a adicao de

alguma substancia adquirem propriedades para um fim especıfico, como acabamento e fundacao, respectivamente.



Figura 1.1: Estrutura basica envolvida na metodologia dos modelos da PO

Exemplo 3. Na implantacao de um barragem de grande consumo de concreto, decidiu-se utilizar como fontes de

agregrados graudos:

1. britas granıticas pelo desmonte (desagregacao por explosivo) da rocha local;

(a) A composicao granulometrica 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 proximos a barrragem;

(a) A composicao granulometrica 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 composicao granulometrica 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 previo, chegou-se em uma faixa de composicao granulometrica ideal, sendo:

• 10% da faixa de 2.4-19 mm

• 20% da faixa de 19-38 mm



O problema consiste em determinar as fracoes de cada fonte para a composicao ideal, de forma a minimizar o

custo de producao do concreto. As variavies de decisao sao:

x1 quantidade (m3) de britas granıticas.



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 restricoes, custos e porcentagens de cada em cada fracao , 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

restricoes, temos as condicoes de nao negatividade das variaveis: x1 ≥ 0,x2 ≥ 0 e x3 ≥ 0. O modelo matematico

completo e dado por:

Minimizar 6x1 + 7x2 + 18x3

Sujeito a: 0.05x2 + 0.10x3 ≥ 0.10

0.10x1 + 0.35x2 + 0.78x3 ≥ 0.20

0.20x1 + 0.60x2 + 0.02x3 ≥ 0.35

0.70x1 ≥ 0.35

x1 + x2 + x3 = 1

x1 ≥ 0 x2 ≥ 0 x3 ≥ 0

Outro exemplo comum e o de planejamento de producao por varios ciclos de tempo (meses,semanas e dias).Vejamos

um exemplo deste tipo:

Exemplo 4. Durante o proximo semestre, uma fabricante textil deve atender aos seguintes compromissos de sua

secao de malharia:

Jan. 4000 pecas Abr. 1000 pecas

Fev. 2000 pecas Mai. 4000 pecas

Mar. 5000 pecas Jun. 2000 pecas

Tabela 1.1: Dados do Planejamento.

Ao final de dezembro, ha 500 pecas em estoque e a empresa so tem capacidade para produzir 3000 pecas

mensais. Entretanto, usando horas extras, a empresa pode produzir ate 600 pecas a mais que sua capacidade

nominal.

O custo variavel de produzir uma peca e de R$ 3 por peca, e o custo de produzir em horas extras e de R$ 3.4

por peca. Alem disso, pecas que ficam em estoque de um mes para outro provocam custo aproximado de R$ 0.25

por peca.

Monte um modelo linear que satisfaca a demanda, mas com minimizacao dos custos de producao.

A solucao esta em se definir xt , yt e et para t = 1:6, para indicarem respectivamente a producao nominal, em

horas extras, e estoque ao final de cada mes.



Min f (x) = 3(x1 + · · ·+ x6) + 3.4(y1 + · · ·+ y6) + 0.25(e1 + · · ·+ e6)

Suj. a: 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 ≤ 600

xt , yt , et ≥ 0 para t = 1 : 6

Problemas de transporte ou alocacao de recursos em determinados percursos tambem sao alvos comuns de

estudos da PO.

Exemplo 5. Considere uma companhia distribuidora de bebidas que tem 2 centros de producao (m = 2) - Arara-

quara e Sao Jose dos Campos - e 3 mercados consumidores principais (n = 3) - Sao Paulo, Belo Horizonte e Rio

de Janeiro. O custo unitario (ci j) de se transportar uma unidade do produto de cada centro de producao a cada

mercado consumidor, bem como as demandas (bj) de cada mercado e a quantidade disponıvel do produto em cada

centro de producao (ai) no proximo perıodo, sao dados pela tabela abaixo.

Mercado

Centro de Producao Sao Paulo(1) Belo Horizonte(2) Rio de Janeiro(3) Suprimento(ai)

Araraquara (1) 4 2 5 800

S. J. Campos (2) 11 7 4 1000

Demanda(mercado) 500 400 900

Tabela 1.2: Dados da producao, distribuicao e consumo.

Como ficaria o sistema deste problema se quisessemos minimizar o custo do processo?

1.3.1 Solucao em PO

Como dito no final do item anterior, nem sempre um problema tem uma solucao possıvel, em contrapartida,

surgem problemas que aceitam diversos conjuntos de valores como solucao do sistema. Deste modo devemos

expressar algumas terminologias importantes quanto ao assunto solucao, como:

1. Solucao - Qualquer especificacao de valores, dentro do domınio da funcao objetivo f(x), para as variaveis de

decisao, independentemente de se tratar de uma escolha desejavel ou permissıvel.

2. Solucao viavel - solucao que satisfaz todas as restricoes do problema.

3. Solucao otima - e aquela que permite a ocorrencia do melhor valor da f(x), isto e, maximiza ou minimiza

seu valor de acordo com o desejado. Pode ser unica ou nao.

1.3.2 Mais do que matematica

Ate agora, a PO parece apenas uma aplicacao matematica que tenta modelar numericamente o mundo real por

meio de aproximacoes de suas variaveis, contudo a pesquisa envolve muito do conhecimento do decisor.



Nao e raro encontrar a PO como tema de trabalho de uma equipe inteira de profissionais de diversas areas (ma-

tematicos, engenheiros, biologos, administradores, economistas, sociologos e ate psicologos) pois, a complexidade

ou mesmo a incerteza envolvida na situacao e tamanha que requer um tratamento sobre divesos pontos de vista.

A exemplo disso, podemos considerar um acontecimento em um predio comercial. As pessoas comecaram

a reclamar na gerencia sobre o fato de esperarem muito tempo o elevador instalado no empreendimento. A

construcao de mais um elevador seria inviavel, o mesmo poderia ser dito de se aumentar a velocidade do elevador

(comprometendo a estrutura da construcao ou a seguranca das pessoas a bordo do elevador).

O que fazer entao?

A resposta e simples! Um dos profissionais contratados foi um psicologo. 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 acao, a primeira vista estranha, a gerencia

do predio parou de receber tantas reclamacoes.

Sendo assim, afirmamos que deve haver atencao quando o assunto do problema e algo que envolve opinioes

humanas ou variaveis muito incertas. Neste caso, pode ser necessario o auxılio de funcoes nao lineares (funcao

objetivo e/ou restricoes, nos levando a aplicacao de tecnicas da Programacao Nao Linear), ou mesmo do emprego

de outras teorias, como a Teoria Fuzzy, por exemplo.

1.4 Solucao Geometrica ou grafica

1.4.1 Introducao - Descrevendo um problema anterior

Ao se trabalhar com equacoes lineares um dos modos de visualizar a solucao e o de criar graficamente as retas

que cada equacao representa, sobretudo em equacoes de problemas pequenos (duas variaveis). Deste modo, as

interseccoes das equacoes sao os possıveis pontos de solucao, vejamos o Exemplo 1 do inıcio deste capıtulo, se

fizermos a reta de w em funcao de l, teremos uma reta no plano xy (figura 1.2).

Figura 1.2: Grafico de w versus l (ou l versus w )



Sabemos entao que a solucao esta sobre a reta, porem, nao podemos afirmar quais valores fornecem a solucao

do sistema. Contudo, temos a funcao area A = wl no plano z, devemos entao com o auxılio de um programa

computacional “chutar ” os valores de w e l para entao gerar o grafico de A versus l e A versus w, com isso vemos

uma parabola (figura 1.3).

Figura 1.3: Grafico de A versus l (ou A versus w )

Pela figura 1.3, fica evidente que a solucao de valor mais alto dentro do espaco da solucao e proximo a metade

do valor possıvel das variaveis, tanto para w quanto l. Este valor e 0.25, ou 25% de L.

Devemos ressaltar que neste caso, como a funcao objetivo era uma variavel multiplicada pela outra, o grafico

resultante foi uma parabola, o que nao configura em um caso de otimizacao linear (Programacao Linear), sendo

apenas uma maneira ilustrativa sobre o uso grafico dentro dos modelos de Pesquisa Operacional.

1.4.2 Tipos de solucao e visualizacao grafica

Nesta subsecao estao apresentados, e resolvidos de forma grafica, alguns exemplos de Programacao Linear con-

tendo duas variaveis. Apesar de ser restrita a problemas pequenos, a solucao grafica oferece elementos facilitadores

para a compreensao dos procedimentos do metodo que sera exposto nos proximos capıtulos.

Ilustremos as seguintes situacoes: solucao unica, solucao multipla, solucao ilimitada e solucao infactıvel a partir

do texto de [11].

Solucao unica

Exemplo 6. Seja o problema de 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: Solucao unica

Na ilustracao, cada restricao esta graficamente representada com sua respectiva reta (a),(b) e (c). Como sao

inequacoes, os pontos que as satisfazem definem semi-espacos, isto e, a regiao acima ou abaixo da reta, a direita

ou a esquerda da reta. Por outro lado, a restricao (d) informa que a regiao esta no primeiro quadrante do plano.

Logo, tem-se a regiao factıvel (regiao escurecida da figura 1.4).

Tomando-se a funcao objetivo como um tracejado, se a deslocarmos na regiao solucao desde o vertice (0,0)

teremos um maximo no vertice (4,2).

Identificacao do ponto otimo

Uma vez que a regiao factıvel foi encontrada, o ponto otimo do exemplo 6 pode ser encontrado de duas maneiras

equivalentes, de acordo com a figura 1.5

Temos entao, na situacao (a) foram tracadas duas retas paralelas a funcao objetivo, com valores de Z = 9 e

Z = 12, respectivamente e averiguamos em qual direcao a funcao objetivo cresce, isto e, no mesmo sentido dos

eixos no primeiro quadrante.

Ja na segunda situacao (b), encontramos o gradiente da funcao (derivadas parciais em cada variavel), o vetor

(2, 3), que e exatamente normal a funcao objetivo. O vetor normal indica a direcao de crescimento da funcao.

Analogamente ao caso (a), a funcao e deslocada ate alcancar o(s) ponto(s) da regiao viavel com maior valor de Z.

Solucao multipla

Exemplo 7. Seja o problema apresentado anteriormente, porem com mudanca na funcao objetivo:



Figura 1.5: Famılia de retas (a) e Vetor normal e direcao de Crescimento (b)

Maximizar x1 + 2x2


−2x1 + 3x2 ≤ 5 (b)

x1 + x2 ≤ 6 (c)

x1 ≥ 0 x2 ≥ 0 (d)

Note que para este caso o problema passa a ter um conjunto de multiplas solucoes, consistindo nos pontos do

segmento da reta x1 + 2x2 entre os pontos (2, 3) e (4, 2).

Observe que a funcao objetivo e paralela a inequacao apresentada na restricao (a), presente na figura 1.6) .

Solucao ilimitada

Exemplo 8. Seja o problema de PL (Exemplo 6), com uma insero de uma restrio (d) :

Maximizar 2x1 + 3x2

Sujeito a: x1 + 2x2 ≥ 8 (a)

−2x1 + 3x2 ≤ 5 (b)

x1 + x2 ≥ 6 (c)

x1 ≥ 0 x2 ≥ 0 (d)

Observe, na Figura 1.7, que o espaco de solucoes passa a ser ilimitado por todo o espaco a direita da reta (a)

e abaixo da reta (b). Portanto, nesta situacao, o problema tem uma solucao tendendo ao infinito, pois a funcao

objetivo pode se deslocar para a direita sem limitacoes e aumentar o valor de Z indefinidamente.



Figura 1.6: Multiplas solucoes

Figura 1.7: Solucao ilimitada

Solucao infactıvel

Exemplo 9. Seja o problema de PL (Exemplo 6), contudo com as restricoes (a) e (c) modificadas nos sinais de

desigualdade :

Maximizar 2x1 + 3x2


−2x1 + 3x2 ≤ 5 (b)

x1 + x2 ≤ 6 (c)

x1 + x2 ≥ 7 (d)

x1 ≥ 0 x2 ≥ 0 (e)

Com a adicao de uma nova restricao ao problema do Exemplo 9, temos um conjunto vazio de solucao, pois



Figura 1.8: Solucao inconsistente

nao e possıvel satisfazer a funcao objetivo quanto as restricoes (c) e (d) ao mesmo tempo.

1.5 Exercıcios Propostos1. Determine a regiao de solucoes viaveis para cada uma das seguintes restricoes independentes, dado x1, x2 ≥ 0

(a) −3x1 + x2 ≤ 6

(b) x1 − 2x2 ≥ 5

(c) 2x1 − 3x2 ≤ 12

(d) x1 + x2 ≤ 0

(e) −x1 + x2 ≥ 0

2. Identifique a direcao de crescimento de z em cada um dos seguintes casos:

(a) Maximizar f (x) = x1 − x2

(b) Maximizar f (x) = −5x1 − 6x2

(c) Maximizar f (x) = −x1 + 2x2

(d) Maximizar f (x) = −3x1 + x2

3. Dado o sistema de expressoes lineares:

−x1 +2x2 ≤ 0

2x1 −3x2 ≤ 3

x1 +3x2 ≤ 6

x1 ,x2 ≥ 0

Determine graficamente a solucao otima nos casos :

a. Min f (x) = 2x1 ; b. Max f (x) = −4x2 ; c. Max f (x) = 3x1 + 3x2.

4. Suponha um modelo de programacao linear:



Max x1 +2x2

Sujeito a −6x1 +10x2 ≤ 30

4x1 +3x2 ≥ −12

x1 +2x2 ≤ 10

x1 ≤ 6

x1, x2 ≥ 0

Utilize o metodo grafico para resolver o sistema.

5. A Roda S.A produz dois modelos de automoveis: seda e utilitario. A tabela a seguir mostra o numero maximo

de veıculos que podem ser vendido em cada um dos proximos tres meses:

Sedas Uilitarios

Mes 1 1200 600

Mes 2 1600 700

Mes 3 1300 500

Tabela 1.3: Dados da producao.

Sabe-se que cada seda e vendido a $ 8.000 e custa $ 6.000 para produzi-lo. O utilitario 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 utilitario. Durante cada

mes, no maximo 1500 veıculo podem ser produzidos e, por restricoes de producao, pelo menos 2/3 dos carros

produzidos devem ser sedas.

No inıcio do mes 1, ha 300 sedas e 200 utilitarios em estoque.

(a) Formule um problema de programacao linear que maximize o lucro da companhia.

(b) Suponha que exista a possibilidade deproduzir ate 600 veıculos em horas extras. Entretanto, tal producao

provoca um aumento de $ 800 no custo de cada unidade.

Mostre como incorporar tal decisao ao modelo de programacao linear.

6. Seja uma empresa que produz quatro produtos, A, B, C e D. A fabricacao de cada unidade desses produtos

exige mao-de-obra, materia-prima e processamento mecanico, gerando um certo lucro, de acordo com a

tabela:

Recurso A B C D Disponbilidade

Mao-de-obra (homens-hora/unidade) 8 3 5 6 15.000 h

Materia-prima (kg/unidade) 5 7 4 5 20.000 kg

Processamento mecanico (horas-maquina) 12 9 8 7 40.000 hm

Lucro (R$/unidade) 3 6 5 4 –/–

Tabela 1.4: Dados do problema.

Dadas as disponibilidades e os requerimentos para cada produto, como determinar um plano de producao

semanal, de forma a maximizar o lucro? Tente escrever o sistema na forma padrao.

7. Este problema envolve um processo de transporte de agragados para a construcao de uma rodovia. Suponha

que, para a construcao de uma rodovia, nao estejam disponıveis na regiao das jazidas de richas adequadas a



obtencao de pedra britada. Faz-se necessario, portanto, o transporte desse material de jazidas mais proximas

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 deposito de material D1, D2, D3

e do trajeto da rodovia R.

Nesse problema, temos m = 4 jazidas correspondentes as origens e n = 3 depositos correspondentes aos

destinos, cujos dados estao na tabela a seguir.

Pedreiras Deposito 1 Deposito 2 Deposito 3 Oferta ai1 30 13 21 433

2 12 40 26 215

3 27 15 35 782

4 37 25 19 300

Demanda bj 697 421 612 –/–

Tabela 1.5: Dados do problema de transporte.

As quantidades ofertadas (ai - ultima coluna) e demandas (bj - ultima linha), em toneladas, bom como os

custos de transportar 1 tonelada de pedra da pedreira i para o deposito j (ci j - que e funcao de varios fatores,

como tempo de viagem, condicoes das estradas de acesso, condicoes dos veıculos que servem a trajetoria

em questao etc.), sao as representacoes do que esta envolvido no problema.

Se xi j e a variavel de decisao que representa a quantidade transportada de rochas da jazida i para o ponto

de deposito j , podemos formular este problema da seguinte maneira:



Minf (xi j) = 30x11 +13x12 +21x13 +40x21 40x22 +26x23

+27x31 15x32 +35x33 +37x41 25x42 +19x43

Suj. a x11 +x12 +x13 ≤ 433

x21 +x22 +x23 ≤ 215

x31 +x32 +x33 ≤ 782

x41 +x42 +x43 ≤ 300

x21 +x31 +x41 = 697

x12 +x22 +x32 +x42 = 421

x13 +x23 +x33 +x43 = 612

xi j ≥ 0

Para verificar uma mudanca no problema, imagine se por um problema estrutural, o Deposito 2 tenha de

ser fechado. Como ficaria o modelo se 45% da demanda deste deposito tenha de ir para o Deposito 1 e o

restante para o Deposito 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 maximo 1500 unidades do modelo Luxo e 1600 do

Basico por mes que vira. A fabrica dispoe de 25000 homens-hora por mes, sendo que cada modelo Luxo

precisa de 10 homens-hora e o Basico 8 homens-hora. A linha de montagem e integrada (produz os dosi

modelos em conjunto) e pode produzir ate 4500 unidades por mes, com lucro sobre o modelo Luxo de $ 100

e o Basico de $ 50.

Deseja-se maximizar os lucros da venda dos produtos desta fabrica. Como seria o modelo de PL para este

problema?

9. Quatro cidades descarregam aguas 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 agua, as

distancias entre as cidades sao de aproximadamente 15 milhas entre si. Um dos parametros de medida em

aguas servidas e a demanda bioquımica de oxigenio (DBO), que e a quantidade de oxigenio requerida para

estabilizar os poluentes presentes na agua.

A Agencia de Protecao Ambiental estabeleceu um maximo de carga de DBO, expressaem lb de DBO por

galao. A remocao de poluentes das aguas servidas ocorre de duas formas: depuracao natural e tratamento de

esgoto antes do despejo nos corpos de agua. O objetivo entao, e determinar a melhor eficiencia economica

de cada umas das estacoes localizadas nas quatro cidades (a eficiencia maxima possıvel de uma estacao e de

99%).

Para montarmos um modelo, devemos citar as variaveis como:

• Q1 - fluxo da corrente (galoes/hora) na saıda da cidade 1;

• p1 - taxa de descarga deDBO (lb/hora);

• x1 - eficiencia da estacao 1 (≤ 0.99);

• b1 - maxima carga de DBO permissıvel na cidade 1 (lb.DBO/galao).

Para satisfazer o requisito de carga de DBO na descarga da cidade 1 para a 2, precisamos ter:

p1(1− x1) ≤ b1Q1



De modo semelhante, no fim da cidade 2:

(1− r12)(Descarga de DBO no trecho 1 - 2) + (Descarga de DBO no trecho 2 - 3) ≤ b2Q2

ou

(1− r12)p1(1− x1) + p2(1− x2) ≤ b2Q2

O coeficiente r12 (≤ 1) representa a fracao de resıduos removida no trecho 1 - 2 por decomposicao. Para a

descarga da cidade 3, a restricao e:

(1− r23)[(1− r12)p1(1− x1) + p2(1− x2)] + p3(1− x3) ≤ b3Q3

A partir do que foi apresentado (usando os dados da tabela abaixo e considerando a remocao por decomposicao

de 6% para os quatro trechos da corrente) determine a maior eficiencia economica para as quatro estacoes.

Caracterıstica Cidade 1 Cidade 2 Cidade 3 Cidade 4

(i = 1) (i = 2) (i = 3) (i = 4)

Qi (galao/hora) 215000 220000 200000 210000

pi (lb/hora) 500 3000 6000 1000

bi (lb.DBO/galao) 0.00085 0.0009 0.0008 0.0008

Custo do tratamento

($/lb.DBO removida) 0.20 0.25 0.15 0.18

Tabela 1.6: Dados do problema de gerenciamento de agua.


CAPITULO 2

Revisao Matematica

Conceitos BasicosAs obras literarias de Programacao Linear, escritas na decada de 60, traziam revisoes extensas de algebra

linear, determinantes, matrizes, espacos vetoriais, convexidade etc. Essas revisoes eram essenciais, pois na epoca

os conteudos visados no curso nao eram devidamente estudados nos cursos de graduacao da epoca.

Desde entao, houve significativa mudanca no currıculo dos cursos de administracao, economia e engenharia.

Ja no ensino medio, por exemplo, o aluno toma contato com as matrizes, e tem um aprofundamento de algebra

linear colocada como elemento dos currıculos mınimos dos cursos de graduacao na area de Exatas.

A apresentacao de conceitos basicos passa a ter proposito de unificacao do conhecimento, de nomenclatura

e fixacao da notacao usada. A revisao a seguir tem um ponto de vista da Programacao Linear, de modo que a

mesma e orientada para antecipar o entendimento dos metodos de otimizacao.

2.1 Equacoes linearesUm sistema de m equacoes linerares e n variaveis tem a seguinte representacao algebrica:

a11 + a12x2 + ... + a1nxn = b1

a21 + a22x2 + ... + a2nxn = b2...

am1 + am2x2 + ... + amnxn = bm

Podemos escrever o sistema na notacao Ax = b, isto e, na forma matricial, como :a11 a12 . . . a1n

a21 a22 . . . a2n

. . . . . .. . . . . .

am1 am2 . . . amn

·x1

x2

...

xn

=

b1

b2

...

bn

Um sistema de equacoes lineares (SEL) e denominado homogeneo se b = 0.

Capıtulo 2. Revisao Matematica PL

2.1.1 Solucao de um Sistema de Equacoes Lineares

Uma solucao de um SEL e um conjunto de valores xj (j = 1, ..., n) se satisfaz simultaneamente todas as

equacoes do sistema. Pela resolucao de um sistema, temos 3 alternativas de solucoes:

• Tem uma unica solucao;

• Possui um conjunto infinito de solucoes, ou multiplas solues;

• Nao tem solucao para o sistema;

Quando o sistema apresentar m = n (matriz quadrada), a indicacao de qual dessas alternativas ocorre e dada

pelo determinante (D) da matriz, a saber:

• Quando D = 0 , indica indeterminacao (infinitas solucoes) ou um sistema sem solucao;

• Quando D 6= 0 , indica que o sistema e crameriano 1 e portanto, possui uma unica solucao possıvel.

2.1.2 Operacoes elementares

As operacoes elementares, conforme ([11]), de um sistema consistem em transformacoes realizadas no sistema.

Sao elas:

I. Troca de linhas;

II. Multiplicacao de uma linha por escalar nao nulo;

III. Combinacoes lineares de linhas;

A seguir veremos os casos de solucao dos SEL onde m = n e m 6= n

2.1.3 Solucao de Sistema de Equacoes Lineares, caso m = n

Nesta subsecao, podemos resumir a forma de algumas solucoes para alguns tipos de sistemas Ax = b, assim:

• Todo sistema homogeneo tem solucao x = 0, chamada solucao trivial;

1. Se a matriz A e nao singular e o sistema homogeneo, so existe a solucao trivial (x = 0);

2. Se a matriz A e singular, o sistema homogeneo e indeterminado, pois D = 0.

• Se a matriz A e nao singular e o sistema nao homogeneo, a solucao e unica e o sistema e textitcrameriano.

Como A e nao singular, sua inversa (A−1) existe. Assim:

Ax = b ⇒ A−1(Ax) = A−1b ⇒ Ix = A−1b ⇒ x = A−1b.

Exemplo 10. Seja o sistema na forma matricial:

1Um sistema crameriano e aquele o qual tem um determinante da matriz A um numero diferente de zero, significando que o sistema

tem solucao unica - tal resultado tem ligacao com a regra de Cramer.



2 1 −3

1 −1 2

2 2 1

x1

x2

x3

=

−2

7

−1

Calculando-se a matriz inversa de A, e aplicando-a como visto, obtem-se a solucao: x1

x2

x3

=

5/19 7/19 1/19

−3/19 −8/19 7/19

−4/19 2/19 3/19

−2

7

−1

=

2

−3

1

A solucao do sistema e entao x1 = 2, x2 = −3 e x3 = 1.

Devemos entao encontrar a matriz inversa para obter a solucao de um sistema? A resposta pratica e nao,

pois computacionalmente este metodo e caro devido ao excesso de calculos necessarios para a determinacao de

matrizes inversas de sistemas complexos, alem disto, a inversa so e passıvel de calculo em matrizes quadradas e

com determinante diferente de zero, sendo assim inviavel metodologicamente como visto no capıtulo de Introducao

a Pesquisa Operacional. Nos proximos topicos explicaremos alguns metodos mais praticos na obtencao de solucoes

para os sistemas lineares, sejam eles casos m = n ou n > m.

2.1.4 Metodo de Gauss-Jordan, caso m = n

Tendo como finalidade a construcao, atraves de operacoes elementares, de uma matriz unitaria, e um metodo

adequado para as rotinas computacionais para a resolucao dos sistemas lineares, uma vez que envolve um algoritmo

mais rapido de ser implementado e calculado pelo processador. Considere o Exemplo 10:2x1 + x2 − 3x3 = −2

x1 − x2 + 2x3 = 7

2x1 + 2x2 − x3 = −1

a. operacoes 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 + x2/2 − 3x3/2 = −1

− 3x2/2 + 7x3/2 = 8

x2 + 3x3 = 1

b. operacoes elementares sobre x2: Dividir a 2a linha por(− 3

2

), adicionar a 1a linha a 2a multiplicada por(

− 12

)e adicionar a 3a linha a 2a vezes (−1).

x1 − x3/3 = 5/3

x2 − 7x3/3 = −16/3

19x3 = 19/3

c. operacoes elementares sobre x3: Dividir a 3a linha por 39 , resultando em x3 = 1. Somar a 1a linha a

3a multiplicada por 13 e somar a 2a linha a 3a multiplicada por 7

3 .x1 = 2

x2 = −3

x3 = 1



Deste modo, chegamos a mesma solucao do Exemplo 10, como x1 = 2, x2 = −3 e x3 = 1. Fica a observacao

de que a maneira mais facil para nao se perder durante os calculos e realiza-los com o auxılio da matriz ampliada

da forma A = (A|b).

Este metodo de transformacao da A para a identidade (I) tambem e chamada de Escalonamento.

2.1.5 Solucao de Sistema de Equacoes Lineares, caso n > m

Se considerarmos o sistema matricial, com Am×n com n > m :a11 a12 . . . a1n

a21 a22 . . . a2n

......

. . ....

am1 am2 . . . amn

.x1

x2

...

xn

=

b1

b2

...

bm

De uma matriz retangular como esta, podemos encontrar diversas solucoes com as aplicacoes anteriormente

discutidas, pois e possıvel obter varias submatrizes quadradas. Como nota, o numero superior de variaveis em

relacao as equacoes e o que de mais comum ocorre no processo de modelagem, dada a complexidade da realidade,

mesmo que reduzida.

Vamos explicitar alguns conceitos e definicoes, mediante um exemplo, dados pela Programacao Linear.

Exemplo 11. Seja um sistema x1 −2x2 + x3 + x4 = 2

x1 −x2 − x3 + x5 = 2

A partir desse sistema (e todos os casos n > m, podemos realizar diversas consideracoes e generalizacoes, a

saber:

1. Em notacao matricial (Ax = b), temos:

[1 −2 1 1 0

1 −1 −1 0 1

].

x1

x2

x3

x4

x5

=

[2

4

]

2. O sistema anterior possui cinco variaveis e duas equacoes, portanto, oferece uma infinidade de solucoes.

Podem-se arbitrar valores para 5−2 = 3 variaveis e resolver o sistema em relacao as duas variaveis restantes.

Para o sistema original ter solucao, pelo menos um dos subsistemas sera crameriano.

3. O sistema tem uma solucao trivial (chamada de basica), que consiste em atribuir o valor nulo em tres das

variaveis 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 sao chamadas variaveis nao basicas, e x4, x5 sao ditas variaveis basicas.

4. Variavel basica e uma variavel responsavel por uma equacao na qual ela tem coeficiente 1, enquanto nas

demais equacoes seu coeficiente e 0.



5. Sistema canonico e um sistema no qual a cada equacao temos uma variavel basica associada. Visto de forma

matricial, tal sistema remete a uma matriz identidade embutida na matriz A (nao obstante fora de ordem).

6. Uma base B do sistema e dada pelo conjunto de vetores coluna correspondentes as variaveis basicas. No

exemplo, a base e formada pelos vetores coluna A4 e A5, ou B = [A4A5]. Como x4 e x5 sao as variaveis

associadas a base, e comum referir-se a base B = x4x5

7. Em um sistema de cinco variaveis e duas equacoes, a variedade de solucoes triviais, ou basicas e dada pela

permutacao:

(5

2

)=

5!

3!2!= 10

8. As solucoes triviais distintas, se existentes, podem ser obtidas por processos de mudanca de base (conforme

sera explicado na proxima subsecao).

2.2 Mudanca de Base

2.2.1 O Pivoteamento

A operacao de mudar a base e feita segundo operacoes elementares, sendo equivalente a um conjunto de

operacoes do tipo Gauss-Jordan, aplicada a uma variavel qualquer do problema (escolhida como basica).

Supondo que a variavel xi seja basica e pertenca a linha r do sistema, a acao de pivotear, tendo em vista a

insercao de xj no lugar, consiste nos passos:

1. Dividir por ar j a r-esima equacao, resultando em ar j = 1 no sistema modificado;

2. Adicionar a k-esima equacao k = 1, 2, . . . , m, k 6= r ,−akjar j

=−akj

1= −akj , de modo a zerar o coeficiente

de xj nessa k-esima linha.

Exemplo 12. Com o exemplo 11 podemos ilustrar o pivoteamento, substituindo x1 por x4 na base. Temos entao

i = 4 e j = 1 com r = 2, e deste modo como a11 = 1, nao precisamos fazer a divisao por a11; da mesma maneira

como a21 = 1, basta somar a 2 equacao a 1 multiplicada por (−1) para se obter uma nova base, B = [A1,A5], e

o sistema resultante: x1 −2x2 +x3 +x4 = 2

x2 −23 −x4 +x5 = 2

Se prosseguirmos para B = [A1,A2], o sistema resultante seria:x1 −3x3 −x4 +2x5 = 6

x2 −2x3 −x4 +x5 = 2

Obs: Utilizaremos este resultado a seguir.

O Pivoteamento em Notacao Matricial

A mudanca de base pode ser vista como uma multipicacao matricial, exemplificada na situacao a seguir:



1. Suponha que a matriz A, do sistema linear A = bx, possa ser escrita pela composicao de tres colunas

A = [B|N|I], sendo B e a base atual, I a base original e N os demais vetores (contendo as variaveis nao

basicas).

2. Seja B−1 a inversa da base atual, entao podemos escrever a sequencia:

B−1[B|N|I]x = B−1b ⇒ [I|B−1N|B−1]x = B−1b

No exemplo 11 aplicamos os conceitos anteriores, para chegar-se ao resultado apresentado no exemplo 12:

[|1 −2| | 1| |1 0||1 −1| | − 1| |0 1|

]×

x1

...

x5

=

[2

4

]

B N I

Explicitando na base mudada por pivoteamento, temos analogamente:

[|1 0| | − 3| | − 1 2||0 1| | − 2| | − 1 1|

]×

x1

...

x5

=

[6

2

]

B−1B = I B−1N B−1

Portanto a nova base B = [a1 a2] pode ser obtida a partir do sistema original por dois modos:

a. operacoes elementares (metodo Gauss-Jordan);

b. sejam a base desejada B =

[1 −2

1 −1

]e sua inversa B−1 =

[−1 2

−1 1

]; pre-multiplicando o sistema

original por B−1, obtendo-se B−1Ax = B−1b.

2.2.2 Selecao das variaveis basicas

Em problemas de Programacao Linear, existe a restricao suplementar de que x ≥ 0, isto e, todas as variaveis

devem ser nao negativas. Assim, possivelmente, nem todas as solucoes basicas de um sistema serao factıveis

(possıveis de serem aplicadas ao modelo), na medida em que nem todas virao a satisfazer a restricao adicional.

Definicoes

Por se tratar de uma revisao para a PO, devemos focar a mesma sobre os atributos e conhecimentos que serao

exigidos a seguir, para tanto, apresentamos um resumo das definicoes introduzidas ate este ponto:

• Variavel basica: e uma variavel relacionada a uma equacao com coeficiente 1 nesta equacao e 0 nas demais;

• Solucao basica: e aquela obtida fazendo-se as variaveis nao basicas iguais a zero e identificando-se a solucao

do sistema linear;

• Solucao basica viavel: e uma solucao basica na qual todas as variaveis basicas satisfazem a restricao

suplementar x ≥ 0;



• Base do Sistema: e dada pelo conjunto das variaveis basicas, ou seja, pelos vetores coluna associados aos

coeficientes das variaveis basicas de todas as equacoes;

• Operacao Pivotar - Pivot Operation: e uma sequencia de operacoes elementares que fazem uma variavel

tornar-se basica;

• Conjunto Viavel: e dado por todas as solucoes viaveis do sistema linear, incluindo-se a restricao suplementar

x ≥ 0.

2.2.3 Construcao da Variaveis Basicas e Variaveis Artificiais

Forma Geral

Dado um sistema linear padrao, uma forma de se obter um conjunto de variaveis basicas desenvolvida pela

Programacao Linear e de realizar-se o acrescimo ao sistema de um conjunto de variaveis basicas (xa), denominadas

artificiais, ou seja:

Ax + Ixa = b ou[A|I

] [ x

xa

]= b

Neste caso, uma solucao inicial consistiria em anular as variaveis originais e deixar as variaveis artificiais na base

do sistema. Esse metodo cria uma solucao basica para o sistema de equacoes, embora a custa da introducao de

mais variaveis, inexistentes originalmente, contudo, por meio de operacoes elementares para sucessivas trocas de

base, as mesmas podem ser colocadas como variaveis nao basicas e anuladas.

Podemos acrescentar ainda que, a respeito deste metodo, temos:

• Se o sistema for incompatıvel o metodo falha;

• Se houver uma equacao redundante (dependencia linear), a solucao de base encontrada tera uma variavel

artificial na base com valor nulo.

Forma Canonica

Sistema canonico e aquele em que cada equacao linear possui uma variavel basica associada a ela e o sistema

de equacoes identifica um solucao trivial. Um caso particular, porem frequente, e aquele que o sistema original e

dado na forma de desigualdade, Ax ≤ b. Neste caso, introduzem-se variaveis de folga, xf , que medem a diferenca

entre o lado direito e o lado esquerdo (como veremos nos modelos de PO, tambem teremos variaveis de excesso

quando Ax ≥ b).

Matricialmente a situacao seria:

Ax ≤ b→ Ax + Ixf = b ou[

A|I] [ x

xf

]= b

Uma solucao inicial viavel basica e quando xf = b e x = 0. Ao contrario das variaveis artificiais do caso geral,

as variaveis de folga (ou excesso) tem sua interpretacao como a quantidade dos valores de b nao utilizadas.

Vamos exemplificar este sistema e a explicacao anterior mediante um exemplo.

Exemplo 13. Suponha o sistema de restricoes:

x1 ≤ 400

x2 ≤ 500

x1 + 2x2 ≤ 900



Aplicando-se tres variaveis de folga (x3, x4 e x5), temos:

x1 + x3 = 400

x2 + x4 = 500

x1 + 2x2 + x5 = 900

Se as variaveis do sistema original representarem:

x1= numero de bolos do tipo 1 a serem produzidos;

x2= numero de bolos do tipo 2 a serem produzidos;

b1= 400 = quantidade de ovos disponıveis;

b2= 500 = quantidade de acucar disponıvel;

b3= 900 = quantidade de farinha disponıvel.

Nessas condicoes, as variaveis de folga significam

x3= quantidade de ovos nao utilizados;

x4= quantidade de acucar nao utilizado;

x5= quantidade de farinha nao utilizada.

Com isto, encerramos a subsecao de Mudanca de Base.

2.3 Espacos Vetoriais

2.3.1 Definicao

Um espaco vetorial V e um conjunto de elementos denominados vetores, tal que a soma de dois de seus

elementos ou a multiplicacao de um de seus elementos por escalar (λ ∈ R) tambem pertence a V.

Alem disso, todo espaco vetorial contem 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 Operacoes

Algumas operacoes basicas dos vetores de um espaco vetorial sao, como ja ditas, a adicao de um elemento a

outro e a multiplicacao por um numero escalar real. Em notacao matematica, se tivermos dois vetores (C e D) e

um escalar (λ), demonstramos as operacoes como:

C + D = (c1, c2) + (d1, d2) = (c1 + d1, c2 + d2);

λC = ˘(c1, c2) = (λc1, λc2).

Podemos ver as operacoes representadas nas figuras 2.1 e 2.2.

2.3.3 Combinacao Linear de Vetores

Se A1,A2,A3 . . . ,An sao vetores pertencentes ao espaco vetorial Rm e se x1, x2, . . . , xn sao numeros reais,

entao o vetor b ∈ Rm, obtido por:

b = A1x1 + A2x2 + · · ·+ Anxn

e chamado de combinacao linerar dos vetores A1,A2,A3, . . . ,An.

Da combinacao linear podemos tirar duas conclusoes sobre os vetores, a saber:



Figura 2.1: Soma de vetores

Figura 2.2: Muiltiplicacao de vetores (com λ = −1)



• Vetores Linearmente Independentes: Suponha um conjunto de vetores nao nulos A1,A2,A3 . . . ,An per-

tencentes ao espaco vetorial Rm e x1, x2, x3 . . . , xn numeros reais. Se a equacao vetorial:

A1x1 + A2x2 + · · ·+ Anxn = 0

so for satisfeita para x1 = x2 = · · · = xn = 0, entao dizemos que os vetores A1,A2, . . . ,An sao linearmente

independentes (LI)

• Vetores Linearmente Dependentes: Suponha um conjunto de vetores nao nulos A1,A2,A3 . . . ,An perten-

centes ao espaco vetorial Rm e x1, x2, x3 . . . , xn numeros reais. Se a equacao vetorial:

A1x1 + A2x2 + · · ·+ Anxn = 0

for satisfeita para algum xk com k ∈ (1, 2, . . . , n) diferente de zero, entao dizemos que os vetores A1,A2, . . . ,An

sao linearmente dependentes (LD).

2.3.4 Dimensao de um Espaco Vetorial

Um espaco vetorial Rm e de dimensao m se:

• Existirem m vetores v1, v2, . . . , vm linearmente independentes pertencentes a Rm.

• Nao 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 combinacao linear desses vetores, isto e:

y = y1v1 + y1v1 + · · ·+ ymvm

Desta maneira, os coeficientes (y1, y2, . . . , ym), unicamente definidos, sao as coordenadas do vetor y em

relacao 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 numero de linhas (ou colunas) nao nulas de B.

Exemplo 14. Seja a matriz

A =

1 0 2 0

−1 5 0 1

2 0 6 −2

Empregando-se o conceito de vetores LI, primeiro aos vetores coluna e depois aos vetores linha, temos:



• Aplicando aos vetores coluna:

1

−1

2

x1 +

0

5

0

x2 +

2

0

6

x3

0

1

−2

x4 =

0

0

0

Note que o sistema admite uma infinidade de solucoes nao triviais; portanto, o posto e inferior a quatro. Ao

escolhermos apenas tres vetores quaisquer, encontramos um posto igual a 3 (ra = 3).

• Aplicando aos vetores linha:

[1 0 2 0

]x1 +

[−1 5 0 1

]x2

[2 0 6 −2

]x3 =

[0 0 0 0

]Essa equacao vetorial fornece o sistema de equacoes:

x1 −x2 +2x3 = 0

5x2 = 0

2x1 +6x3 = 0

x2 −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 sao linearmente

independentes, entao a matriz quadrada B = [Ar ,As , . . . ,Ap], de ordem m, e uma base de A.

Mudanca de Base

Seja uma base no espaco Rm constituıda pelos vetores e1, e2, . . . , em. Nessa base, qualquer vetor y ∈ Rm e

expresso por uma combinacao linear definida univocamente 2, sendo y1, y2, . . . , ym as coordenadas do vetor y, isto

e:

y = y1e1 + y2e2 + · · ·+ ykek + . . .+ ymem

Podemos permutar, na base, o vetor ek pelo vetor y (somente se yk 6= 0). Assim:

ek = −y1

yke1 −

y2

yke2 − · · ·+

1

ykyky − · · · −

ymyk

em

Essa expressao 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 expressoes sao importantes para casos de mudanca de base, pois, imagine algum outro vetor x ∈ Rm.

Como exemplo, na base original, esse vetor seria representado por:

x = x1e1 + x2e2 + · · ·+ xkek + · · ·+ xmem

2Diz-se da relacao, ou da correspondencia, entre dois conjuntos em que a cada elemento do primeiro conjunto corresponde apenas

um elemento do segundo, isto , uma funo injetora entre os conjuntos.



Em relacao a uma nova base (que inclui y), basta realizar uma substituicao de ek na expressao anterior com a

resultante de ek :

x =

(x1 − xk

y1

yk

)e1 +

(x2 − xk

y2

yk

)e2 + · · ·+

xkyk

y + · · ·+(xm − xk

ymyk

)em

O processo de mudar a base de um espaco e tambem denominado pivoteamento, exatamente analogo ao

discutido anteriormente.

Produto Escalar (Interno) entre Dois Vetores

Sejam os vetores A1 e A2 pertencentes a um espaco vetorial Rm. O produto escalar, ou produto interno,

desses dois vetores pode ser definido pela expressao a seguir, envolvendo a soma dos produtos dos componentes

correspondentes. Quando dois vetores A1 e A2 sao ortogonais, entao o produto escalar sera nulo.

A1.A2 = a11a21 + a12a22 + · · ·+ a1na2n =

n∑i

a1ja2j

2.4 Conjuntos Convexos e Combinacao 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 entao, diz-se que X e um conjunto convexo. Nao obedecendo a relacao, entao e dito nao

convexo.

2.4.2 Combinacao Convexa

De forma analoga, podemos definir uma combinacao convexa de vetores. Dados n vetores A1,A2, . . . ,An

pertencentes a um espaco vetorial Rn e λi para i = 1 : n, temos:

y = λ1A1 + λ2A2 + . . . λnAn sendo

n∑i

λi = 1

e uma combinacao convexa dos vetores Ai , para i = 1, . . . , n.

Exemplo 15. Sejam os vetores A1 =

[1

0

]e A3 =

[3

0

]∈ R2. Seja o vetor b = λA1 + (1 − λ)A3, com

0 ≤ λ ≤ 1, representando uma combinacao 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 combinacao convexa do exemplo.

2.4.3 Interpretacao Geometrica

Portanto, pela definicao anterior, um conjunto convexo tem como interpretacao geometrica a seguinte situacao:

quaisquer pontos no segmento de reta formado por dois pontos quaisquer do conjunto X tem de pertencer a ele.

Em termos geometicos, como exemplo um conjunto do R2 temos a figura 2.4.

Esta interpretacao geometrica pode ser generalizada para outras dimensoes. Temos ainda duas propriedades

dos conjuntos convexos:



Figura 2.3: Combinacao convexa do exemplo 15.

1. A interseccao de conjuntos convexos tambem e um conjunto convexo;

2. A soma (ou a subtracao) de dois conjuntos convexos e tambem 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 nao convexo no R2.

2.4.4 Ponto Extremo de um Conjunto Convexo

Suponha C um conjunto convexo. Entao A ∈ C e um ponto extremo de C se nao for possıvel expressa-lo como

uma combinacao convexa de quaisquer outros dois pontos distintos pertencentes aos conjunto.

2.5 Exercıcios Propostos1. Determine a inversa da matriz A usando os recursos do Metodo de Gauss-Jordan. Para tanto, escreva a

matriz identidade I com a mesma dimensao, ao lado direito. Em seguida aplique operacoes elementares no

sistema expandido que transformem a matriz A na matriz I, e verifique que a matriz I se transforma na

inversa A−1:

a. A =

2 1 −3

1 −1 2

2 2 1



b. A =

1 0 1

0 1 0

1 2 0

2. Verifique que os seguintes conjuntos de vetores formam uma base no R3:

a. (1, -1, 2); (0, 5, 0); (2, 0, 6);

b. (-1, 5, 1); (2, 0, -2); (1, 0, 4);

c. (1, 0, 0); (1, 1, 0); (1, 1, 1);

3. Expresse o vetor (1, 1, 1) em cada base existente do exercıcio anterior.

4. Encontre todas as solucoes basicas dos sistemas

a.x1 −2x2 +2x3 −4x4 = 2

3x1 −5x2 +x3 +3x4 = 4b.

2x1 +3x2 +5x3 = 5

x1 −4x2 −2x3 = 3

5. Dada a matriz A com cinco colunas A1,A2,A3,A4,A5:

A =

1 2 1 0 0

−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:

A =

1 1 1 1

−2 1 −1 0

0 3 1 1

7. Nos problemas de (a) ate (e), resolver os sistemas pelo metodo de eliminacao de Gauss.

−2x +3y −z = b1

x −3y +z = b2

−x +2y −z = b3

(a) Para b1 = 2, b2 = 5 e b3 = 7.

(b) Para b1 = 1, b2 = 6 e b3 = 0.

(c) Para b1 = 2, b2 = −8 e b3 = 9.

(d) Para b1 = −4, b2 = −3 e b3 = −2.

(e) Para b1 = 4, b2 = 7 e b3 = 9.

8. (Engenharia de Controle e Automacao) 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Ω.

Dispoe-se de uma tabela de precos de varios tipos de resistencias; assim como as correntes que elas suportam

sem queimar.

De que tipo devemos escolher cada resistencia para que o circuito funcione com seguranca e a sua fabricacao

seja a de menor custo possıvel?



Figura 2.5: Sistema de circuito

Resistencias

20Ω 30Ω 40Ω 50Ω 100Ω

10 10 15 15 20 0.5 A Corrente

15 20 15 15 25 1.0 A Maxima

20 22 20 20 28 3.0 A Suportada

30 30 34 34 37 5.0 A

Tabela 2.1: Dados das resistencias disponıveis.

9. (Engenharia Ambiental) Necessita-se adubar um terreno, de acordo com um plano de recuperacao, acres-

centado a cada 10m2: 140 g de nitrato, 190g de fosfato e 205 g de potassio.

Dispoe-se de quatro qualidade de adubo com as respectivas caracterısticas, incluindo sua unidade de custo

de producao (u.c.p):

(a) Cada quilograma do adubo I custa 5 u.c.p e contem 10 g de nitrato, 10 g de fostato e 100 g de potassio;

(b) Cada quilograma do adubo II custa 6 u.c.p e contem 10 g de nitrato, 100 g de fostato e 30 g de

potassio;

(c) Cada quilograma do adubo III custa 5 u.c.p e contem 50 g de nitrato, 20 g de fostato e 20 g de potassio;

(d) Cada quilograma do adubo IV custa 15 u.c.p e contem 20 g de nitrato, 40 g de fostato e 35 g de

potassio;

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 adubacao?


CAPITULO 3

Metodo Simplex

3.1 Teorema Fundamental da Programacao LinearNo Capıtulo 1, o metodo de resolucao grafica de um problema foi utilizado apenas para casos de duas ou tres

variaveis. Para problemas maiores, este metodo torna-se impraticavel, nesta situacao precisamos de uma tecnica

eficiente para resolver problemas de Programacao Linear (PL) com mais de tres variaveis. Uma dessas tecnicas

chama-se Metodo Simplex.

Para melhor compreender este metodo, devemos observar algumas consideracoes sobre as solucoes dos sistemas

que representam os modelos, tomando como exemplo o item “Identificacao do ponto otimo” do Capıtulo 1. Vimos

que:

(i) A funcao objetivo assume necessariamente um valor maximo e um valor mınimo quando a regiao poliedral

convexa (factıvel) for limitada;

(ii) Os vertices desempenham um papel fundamental na procura de maximos e mınimos para a funcao objetivo.

O primeiro resultado acima nos diz que os valores extremos de uma funcao afim1 sao assumidos nos pon-

tos extremos dos segmentos (vertices). Daı, podemos fazer colocacoes e generalizacoes2, obtendo o Teorema

Fundamental da Programacao Linear:

Teorema 1. Seja f (x1, . . . , xn) = a1x1 + · · · + anxn + b, onde b uma constaante qualquer, definida numa regiao

poliedral convexa A do Rn. Suponha que f assuma um valor maximo (ou mınimo) nesta regiao. Entao, se A possui

vertice(s), este valor maximo (ou mınimo) sera assumido num vertice.

Considerando um problema de Programacao Linear na forma padrao:

min f (x)

Sujeito a Ax = b

x ≥ 0

onde A e uma matriz m × (n +m) de posto m, entao:

i) se ha uma solucao factıvel, ha uma solucao basica factıvel.

ii) se ha uma solucao factıvel otima, ha uma solucao basica facıvel otima.

1Funcao linear mais contantes.2Para mais informacoes e deducoes do teorema consultar paginas 368/369 em [4].

Capıtulo 3. Metodo Simplex PL

Do teorema anterior e da equivalencia entre solucao basica factıvel e vertice temos que o Metodo Simplex e

finito, pois um sistema linear de m equacoes com (m + n) incognitas tem no maximo, por combinacao:(m + n

m

)=

((m + n)!

m!n!

)Solucoes basicas

Logo, o Simplex efetua um numero menor que

(n +m

m

)interacoes para encontrar a solucao otima, pois o

algoritmo Simplex e um procedimento de busca, isto e, move-se de vertice factıvel em vertice factıvel ate encontrar

a solucao basica factıvel otima.

3.1.1 Transicao da solucao grafica para a solucao algebrica

No metodo grafico, a regiao de solucoes e delineada pelos meios-espacos (regioes delimitadas pelas restricoes),

sendo possıvel graficamente observar porque a regiao factıvel tem um numero infinito de pontos de solucao, uma

vez que nos exemplos citados, apresentava-se um plano e que por definicao compreende infinitos pontos (podendo

ser extendido aos casos do R3 . . . Rn, como volumes e passando para formas nao possıveis de serem representadas

geometricamente).

No Metodo Simplex, a regiao de solucoes e representada por m equacoes lineares simultaneas e n variaveis nao

negativas. Neste caso, tambem ocorre um numero infinito de pontos de solucao, dado que o numero de equacoes

m e sempre menor que ou igual ao numero de variaveis n, pois se nao fosse assim, terıamos no mınimo (m − n)

equacoes redundantes, ou seja, linearmente dependentes.

Contudo, antes de vermos como o Simplex atua diante desse fato de infinidade de solucoes, vejamos como

trabalhar com os metodos grafico e algebrico e as mudancas entre ambos. A Figura 3.1 ilustra esta transicao, de

um modo comparativo.

3.2 Metodo Simplex

3.2.1 Modelo de Programacao Linear em forma de equacao - Forma Padrao

O desenvolvimento do calculos do Simplex e facilitado pela imposicao de dois requisitos as restricoes do pro-

blema:

1. Todas as restricoes (com excecao da nao negatividade das variaveis) sao equacoes cujos lados direitos sao

nao negativos;

2. Todas as variaveis sao nao negativas.

A finalidade destes dois requisitos e padronizar e tornar mais eficiente os calculos de metodo simplex. Contudo,

antes apresentamos as disposicoes dos problemas na Forma Padrao e na Forma Canonica

3.2.2 Forma Padrao

A forma padrao e aquela em que as restricoes sao expressas por meio de equacoes lineares:



Figura 3.1: Transicao de solucao grafica para algebrica.

max ou min f (x) = c1x1 + c2x2 + . . . + cnxn

Sujeito a a11x1 + a12x2 + . . . + a1nxn = b1

a21x1 + a22x2 + . . . + a2nxn = b2

......

. . ....

...

am1x1 + am2x2 + . . . + amnxn = bn

xi ≥ 0, (i = 1 : n)

Em termos de matrizes, pode-se representar a forma padrao da PL como:

min f (x) = cx

Sujeito a Ax = b

x ≥ 0

em que:



A =⇒ matriz m × n dos coeficientes tecnologicos 3.

b =⇒ matriz m × 1 das constantes do lado direito.

x =⇒ matriz n × 1 das variaveis de decisao.

c =⇒ vetor 1× n dos coeficientes da funcao objetivo f (x).

3.2.3 Forma Canonica

Diz-se que o sistema esta na forma canonica quando, embutida na matriz dos coeficientes, encontra-se a

matriz identidade. Em consequencia, esse sistema admite uma solucao trivial em que as variaveis nao associadas

as colunas da matriz identidade sao nulas.

O sistema a seguir exemplifica um problema de PL com restricoes na forma canonica. Alem disso, se para todo

i = 1 : m, bi ≥ 0, a solucao e tambem viavel, com xn+1 = bi , enquanto as demais variaveis x1, . . . , xn sao nulas.

max ou min f (x) = c1x1 + c2x2 + . . . + cnxn + (cn+1xn+1 +

. . . + cn+mxn+m)

Sujeito a a11x1 + a12x2 + . . . + a1nxn + xn+1 = b1

a21x1 + a22x2 + . . . + a2nxn + xn+2 = b2

......

. . ....

......

am1x1 + am2x2 + . . . + amnxn + xn+m = bm

x1 : xn+m ≥ 0

Note que na funcao objetivo, temos as variaveis de folga ou excesso representadas dentro do parenteses.

Uma outra situacao muito conveniente e quando as restricoes originais se apresentam com sinal “≤”, enquanto

o vetor b ≥ 0, o que corresponde, em notacao matricial, ao problema de PL:

min f (x) = cx

Sujeito a Ax ≤ b

x ≥ 0

Nesse caso, todas as restricoes transformam-se em equacoes mediante a inclusao de variaveis de folga (ou

excesso), uma para cada desigualdade, e o sistema para a forma canonica.

A seguir mostraremos como lidar com desigualdades e variaveis irrestritas, convertendo os problemas para a

forma canonica.

3.2.4 Conversao de desigualdades em equacoes com o lado direito nao negativo

Em restricoes (≤), o lado direito pode ser considerado como a representacao de um limite imposto a disponi-

bilidade de um determinado recurso, enquanto que o esquerdo, a utilizacao desse recurso limitado pelas variaveis

(operacoes) do modelo. A diferenca entre um lado e outro pode ser interpretado como uma quantidade de recurso

nao utilizada ou uma folga.

Deste modo, para eliminarmos a desigualdade, fazemos a adicao de uma variavel de folga nao negativa (xfn)

ao lado esquerdo da inequacao. Considere o Exemplo 13 do Capıtulo 2, que faz uso dessa operacao matematica,

contudo, imagine a adicao da restricao a seguir:

3Tais variaveis sao chamadas de tecnologicas pois, dependem do modelo segundo o qual temos tecnologia para empregar naquele

instante - seja em aparelhos de medicao ou mesmo nos componentes envolvidos em processos de producao, como maquinas que

processam um numero maximo ou um numero mınimo de determinada substancia.



x1 + x2 ≤ 10 =⇒ x1 + x2 + xf3 = 10, com xf3 ≥ 0·

De forma analoga, se a restricao for (≥) entao, conseguimos a igualdade com a subtracao de uma variavel

de sobra (ou excesso) nao negativa ao lado esquerdo da inequacao. Temos a restricao:

x1 + x2 ≥ 10 =⇒ x1 + x2 − xf3 = 10, com xf3 ≥ 0·

Agora, o unico requisito e deixar o lado direito da inequacao resultante nao 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 transformacao em igualdade, e em seguida multiplica-se por (-1).

3.2.5 Como lidar com variaveis irrestritas

Em alguns casos, as variaveis podem oscilar entre positivo e negativo, talvez o melhor exemplo seja a contratacao

e a demissao de funcionarios em uma linha produtiva.

Se xi(≥ 0) for a quantidade de mao-de-obra no perıodo i (um mes, uma quinzena etc), entao xi+1(≥ 0), a

quantidade necessaria para o proximo perıodo i + 1 pode ser expresso como:

xi+1 = xi + yi+1

A variavel yi+1 deve ser irrestrita ao sinal, para permitir que xi+1 aumente ou diminua em relacao a xi , isto e,

dependa do numero de contratados e demitidos, respectivamente.

Podemos satisfazer o requisito da variavel nao negativa com a substituicao:

yi+1 = y−i+1 − y+i+1 onde y−i+1 ≥ 0 e y+

i+1 ≥ 0

Para mostrar que a substituicao e valida, suponha que no perıodo 1 a mao-de-obra seja x1 = 30 e que no

perıodo 2 tenha de aumentar em 10 trabalhadores chegando a 40. Em termos da substituicao, y−2 e y+2 , sera

equivalente a y+2 = 0 e y−2 = 10 ( resultando em y2 = 10). De maneira semelhante se for reduzida em 10, teremos

y−2 = 0 e y+2 = 10 ( resultando em y2 = −10). A substituicao tambem permite a possibilidade de nao haver

alteracao na mao-de-obra, fazendo com que ambas as variaveis assumam um valor igual a zero.

3.2.6 Variaveis Nao Positivas

Suponha um programa linear em que a variavel de decisao x nao possa ser positiva, ou seja, x ≤ 0. Nesse caso,

faz-se uma troca de variavel:

x = −x1, em que x1 ≥ 0



3.2.7 Transformando o Problema de Maximizacao em Minimizacao

Utilizando-se a relacao de maxf (x) = −min−f (x), uma situacao de maximizacao pode se transformar em

uma de minimizacao. Como exemplo, considere a parabola:

• 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 funcao por (−1), ela e substituıda por outra simetrica em relacao ao eixo horizontal

e o mınimo de uma ocorre na mesma abscissa que o maximo da outra, naturalmente com sinal inverso. Entao,

−max−f (x) = minf (x).

3.2.8 Princıpios do Metodo Simplex

Suponha o modelo do Exemplo 6 do Capıtulo 1 resolvido graficamente. Com a auxılio desse exemplo, serao

expostos, passo a passo, os Princıpios do Simplex. Seja o modelo:

max f (x) = 2x1 + 3x2

Sujeito a: x1 + 2x2 ≤ 8

− 2x1 + 3x2 ≤ 5

x1 + x2 ≤ 6

x1 ≥ 0

x2 ≥ 0

Como dito, as inequacoes do tipo (≤) podem ser transformadas em equacoes pela insercao de tres variaveis de

folga, com peso nulo na funcao objetivo, de modo que obtem-se o sistema na forma canonica.

max f (x) = 2x1 + 3x2 + 0x3 + 0x4 + 0x5

Sujeito a: x1 + 2x2 + x3 = 8

− 2x1 + 3x2 + x4 = 5

x1 + x2 + x5 = 6

xi ≥ 0 para i = 1 : 5

O sistema acima possui uma solucao trivial, ou seja, fazendo x1 = 0 e x2 = 0, temos:

Variaveis Basicas

x3 = 8

x4 = 5

x5 = 6

Variaveis Nao basicas

x1 = 0

x2 = 0

As variaveis definidas como nulas sao as nao basicas; as demais sao chamadas de variaveis basicas e formam

a base do sistema linear. A expressao entrar na base significa fazer uma variavel nao basica deixar o valor nulo e

crescer ate o maximo valor que lhe seja possıvel e, portanto, positiva ou eventualmente nula.

Como primeira solucao 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 Iteracao

Observando-se os coeficientes da funcao 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 tem coeficientes positivos



nessa funcao. Como se deseja maximizar, parece intuitivo escolher primeiro aquela variavel cujo coeficiente e maior,

nesse caso a variavel x2.

Para que a variavel x2 entre na base e aumente seu valor ao maximo, e necessario identificar qual variavel basica

deve sair da base e, portanto, se anular. Utilizamos o sistema a seguir para verificar as mudancas nos valores das

variaveis basicas x3, x4 e x5 quando aumentamos o valor de x24.

x1 + 2x2 + x3 = 8

−2x1 + 3x2 + x4 = 5

x1 + x2 + x5 = 6

Mantendo-se x1 = 0 e deixando o sistema em funcao de x2 temos:

x3 = (8− 2x2) ≥ 0

x4 = (5− 3x2) ≥ 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 variaveis e mante-las ainda nao negativa, devemos encontrar os valores

de x2 que facam isso, podendo em seguida em qual destas variaveis x2 apresenta seu valor mınimo (denotado por

ε 5).

Portanto, ε = x2 = min 82 ,

53 ,

61 = 5

3 , ou seja, para x2 = 53 , obtem-se x4 = 0, enquanto a demais variaveis

permanecem nao negativas (sao factıveis ao modelo). Logo, x4 sai da base, entrando x2 com valor 53 , e a funcao

objetivo passa a : f (x) = 2(0) + 3(

53

)= 5, isto e, ja temos um valor de funcao objetivo para a comparacao com

as proximas iteracoes.

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, sao feitas operacoes elementares no sistema, tornando os coeficientes de x2 um elemento

da matriz identidade, a saber:

• Dividir a 2a linha por 3, o que resulta em =⇒ −2

3x1 + x2 +

1

3x4 =

5

3

• Somar a 1a linha a nova 2a linha multiplicada por (−2) =⇒7

3x1 + (0)x2 + x3 −

2

3x4 =

14

3

• Somar a 3a linha a nova 2a linha multiplicada por (−1) =⇒5

3x1 + (0)x2 −

1

3x4 + x5 =

13

3

Com essas alteracoes, o sistema e reescrito conforme:

7

3x1 + x3 −

2

3x4 =

14

3

−2x1 + x2 +1

3x4 = 5

5

3x1 −

1

3x4 + x5 = 6

Pelas variaveis, tem-se:

4Ao se realizar esse procedimento atente para manter as variaveis x3, x4 e x5 nao negativas.

5O ε pode ser visto como a razaobi

ai jdo sistema, como j sendo o numero da variavel (coluna) e i o numero da equacao (linha)

trabalhadas.



Variaveis Basicas

x3 =14

3

x2 =5

3

x5 =13

3


x1 = 0

x4 = 0

O valor da funcao objetivo f (x) = 2x1 + 3x2 = 2(0) + 3(

53

)= 5. Consultando-se a solucao grafica, o ponto

obtido na segunda iteracao corresponde ao vertice (x1,x2) =(

0, 53

). Necessitamos agora saber se a solucao

encontrada e otima, para tanto devemos expressar a funcao objetivo em termos das variaveis nao basicas, nesse

momento sendo x1 e x4.

Da segunda linha do sistema modificado obtemos x2 em termos das variaveis x1 e x4, como:

x2 =5

3+

2

3x1 −

1

3x4

Substituindo na funcao objetivo:

f (x) = 2x1 + 3x2 =⇒ 2x1 + 3

(5

3+

2

3x1 −

1

3x4

)=⇒ 5 + 4x1 − x4

Desta expressao, vemos que se valor de x4 aumentar, a funcao decresce; enquanto que um aumento no valor de

x1 aumenta em quatro unidades a funcao objetivo. Logo, a funcao objetivo nao esta no seu valor otimo, podendo

aumentar caso x1 entre na base (e ainda x4 fique de fora).

Segunda Iteracao

Analogamente, para x1 entrar na base e aumentar de valor, e necessario identificar qual variavel (x2, x3 ou x5)

devera sair. Para acompanhar o raciocınio algebrico, reescrevemos o sistema modificado com x4 nulo:7

3x1 + x3 =

14

3

−2x1 + x2 = 55

3x1 + x5 = 6

Deixando o sistema em funcao de x1 para todas as variaveis e considerando-as como zero, temos:

x3 =14

3−

7

3x1

x2 =5

3+

2

3x1

x5 =13

3−

5

3x1

Na primeira restricao, a variavel x3 atinge o valor zero quando x1 = 2; na segunda, a variavel nao atinge o valor

zero pois o coeficiente de x1 e negativo, o que aumenta o valor quando colocado em funcao de x1; na terceira, x5

se anula quando x1 = 135 . Portanto, ε = x1 = min

2, ∞, 13

5

= 2.

Para x1 = 2, as variaveis assumem os valores:



x1 = 2

x2 = 3

x3 = 0

x4 = 0

x5 = 1

Para os valores encontrados das variaveis a funcao objetivo f (x) = 2(2) + 3(3) = 13, o que e maior que o 5

encontrado na iteracao anterior. A nova base sera formada agora por x1, x2 e x5. Para representa-la e necessario

a aplicacao de operacoes elementares, o que resulta em:x1 +

3

7x3 −

2

7x4 = 2

+ x2 +2

7x3 +

1

7x4 = 3

−5

7x3 +

1

7x4 + x5 = 1

Em que:

Variaveis Basicas

x1 = 2

x2 = 3

x5 = 1


x3 = 0

x4 = 0

Comparando esse resultado com a solucao grafica, nota-se que esta corresponde ao vertice (x1,x2) = (2, 3).

Agora realizamos o procedimento de colocar a funcao objetivo em termos das variaveis nao basicas, utilizando as

equacoes que possuem as variaveis x1 e x2 do sistema obtido:

x1 = 2−3

7x3 +

2

7x4

x2 = 3−2

7x3 +

1

7x4

a funcao objetivo f(x) fica como:

f (x) = 13−12

7x3 +

1

7x4

Terceira Iteracao

Pela ultima expressao da funcao objetivo, se x3 aumentar, a funcao decresce; enquanto que se x4 aumentar,

a funcao cresce, portanto, x4 deve entrar na base do sistema (note que aparentemente ela parecia nao ser uma

candidata a entrar na base). Temos o sistema como:

x1 +3

7x3 −

2

7x4 = 2

+ x2 +2

7x3 +

1

7x4 = 3

−5

7x3 +

1

7x4 + x5 = 1

Fazendo-se as comparacoes dentro do sistema, com x3 = 0, obtemos para x1, x2 e x5 respectivamente, um

ε = x4 = min∞, 21, 7 = 7, portanto a variavel x5 sai da base para a entrada de x4. Com as alteracoes de

mudanca de base chegamos no sistema:



x1 − x3 + 2x5 = 4

x2 + x3 − x5 = 2

− 5x3 + x4 + 7x5 = 7

Em que:

Variaveis Basicas

x1 = 4

x2 = 2

x4 = 7


x3 = 0

x5 = 0

Chegamos assim a solucao otima no vertice (x1, x2) = (4, 2), com f (x) = 14. Para efeito de confirmacao

algebrica, colocamos a funcao em termos das variaveis nao basicas, obtendo:

f (x) = 14− x3 − x5

Neste caso, verificamos que ambas as variaveis quando aumentadas, reduzem o valor da funcao objetivo, isto e, a

solucao encontrada e a melhor possıvel.

A solucao grafica e as solucoes encontradas

Na Figura 3.2 verificamos os pontos:

Figura 3.2: Solucao grafica, solucao unica.

• A para a solucao trivial;

• B para a primeira iteracao;

• C para a segunda iteracao;

• D para a terceira iteracao, com solucao otima;



• E, o ponto E e o ponto o qual irıamos recair se em vez de x2 na primeira iteracao, se tivessemos escolhido

x1, o que tambem economizaria uma iteracao, ja que a segunda iteracao dessa escolha passaria ao ponto C

(verifique como exercıcio).

Aqui, devemos ressaltar que nao ha uma regra clara para a escolha de qual variavel entra e qual sai da base a

priori, como um palpite inicial, isso pode reduzir muitos passos de acordo com a extensao de quantas variaveis se

esta trabalhando. Uma possibilidade e a escolha da variavel pelo coeficiente mais favoravel possıvel e outra e a de

se escolher aleatoriamente uma das variaveis com coeficiente favoravel, independente do valor, contudo, nao ha

provas de qual das duas seja melhor.

Na proxima subsecao veremos como usar o Metodo Simplex na forma de quadros (tabelas).

3.2.9 Metodo Simplex na forma de quadros - Tableau Simplex

Utilizar o Tableau Simplex e um modo de visualizacao mais claro de uma iteracao e de melhor identificar os

procedimentos a serem feitos para as iteracoes subsequentes. Para colocarmos o sistema na forma de quadros,

utilizaremos a funcao f (x) como uma restricao e realizaremos as transformacoes pertinentes ao modo canonico.

Tomando o exemplo da subsecao anterior, obtemos:

max f (x) −2x1 −3x2 +0x3 +0x4 +0x5 = 0

Sujeito a: x1 +2x2 +x3 = 8

−2x1 +3x2 +x4 = 5

x1 +x2 +x5 = 6

xi ≥ 0 para i = 1 : 5

Dado o sistema acima, podemos escreve-lo como a tabela 3.1 (tableau):

Base f (x) x1 x2 x3 x4 x5 b Linha

max 1 –2 –3 0 0 0 0 (0)

x3 0 1 2 1 0 0 8 (1)

x4 0 –2 3 0 1 0 5 (2)

x5 0 1 1 0 0 1 6 (3)

Tabela 3.1: Dados apresentados na forma tableau.

Agora devemos iniciar a analise dos dados para efetuar as trocas de base. Comecamos com a linha (0), onde

estao os coeficientes de x1 e x2, verificando que ambas as variaveis, quando aumentados seus valores, obrigam o

aumento da funcao f (x) para que a equacao seja verdadeira (uma vez que os coeficientes de ambas sao negativos),

portanto, uma das duas deve entrar na base e uma das variaveis formadoras da atual base deve sair.

Como a variavel x2 apresenta maior coeficiente, esta sera escolhida para entrar primeiro na base. Procedemos

entao com o destaque da coluna na qual esta a variavel que entrara na base:


max 1 –2 –3 0 0 0 0 (0)

x3 0 1 2 1 0 0 8 (1)

x4 0 –2 3 0 1 0 5 (2)

x5 0 1 1 0 0 1 6 (3)

Tabela 3.2: Comeco da verificacao da troca de variaveis.



Para escolhermos a variavel que sai da base, realizamos o teste do quociente para verificar qual o menor valor

de ε e assim selecionar a variavel que devera sair da base. Esse teste consiste em dividir o valor de bi por ai j (desde

que ai j seja positivo), sendo j a coluna da variavel de entrada. Temos entao:

Base f (x) x1 x2 x3 x4 x5 b Linha Razao: min = ε

max 1 –2 –3 0 0 0 0 (0) -/-

x3 0 1 2 1 0 0 8 (1) 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 variavel que sai da base e x4 e o elemento a22 = 3 e chamado de pivo. Em seguida realizamos as operacoes

elementares (Metodo de Gauss-Jordan) para chegarmos a nova tabela:


max 1 –4 0 0 1 0 5 (0)

x3 0 7/3 0 1 –2/3 0 14/3 (1)

x2 0 –2/3 1 0 1/3 0 5/3 (2)

x5 0 5/3 0 0 -1/3 1 13/3 (3)

Tabela 3.4: Resultados da primeira iteracao.

Apos a primeira iteracao, constatamos que f (x) = 5, quando as variaveis nao basicas forem zero. Entretanto,

como o coeficiente de x1 permanece negativo, se a variavel tiver acrescimo em seu valor, teremos um aumento na

funcao 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:


max 1 –4 0 0 1 0 5 (0) -/-

x3 0 7/3 0 1 –2/3 0 14/3 (1) (14/3)/(7/3) = 2

x2 0 –2/3 1 0 1/3 0 5/3 (2) -/-

x5 0 5/3 0 0 –1/3 1 13/3 (3) (13/3)/(5/3) = 13/5


Com a entrada de x1, a variavel x3 deve sair da base. Realizando as operacoes elementares pertinentes,

chegamos a tabela 3.6:


max 1 0 0 12/7 –1/7 0 13 (0)

x1 0 1 0 3/7 –2/3 0 2 (1)

x2 0 0 1 2/7 1/7 0 3 (2)

x5 0 0 0 –5/7 1/7 1 1 (3)

Tabela 3.6: Resultados da segunda iteracao.

Verificando a linha(0) notamos que o coeficiente da variavel x4 e negativo, concluımos que esta exerce influencia



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 variavel saira.


max 1 0 0 12/7 –1/7 0 13 (0) -/-

x1 0 1 0 3/7 –2/3 0 2 (1) -/-

x2 0 0 1 2/7 1/7 0 3 (2) (3)/(1/7) = 21

x5 0 0 0 –5/7 1/7 1 1 (3) (1)/(1/7) = 7


A variavel x5 sai da base, portanto, realizamos novamente algumas operacoes elementares para chegarmos a

tabela 3.8:


max 1 0 0 1 0 1 14 (0)

x1 0 1 0 –1 0 2 4 (1)

x2 0 0 1 1 0 –1 2 (2)

x4 0 0 0 –5 1 7 7 (3)

Tabela 3.8: Resultados da terceira iteracao.

Observe que na linha(0) temos apenas termos com coeficientes positivos, sendo assim, o aumento de uma

dessas variaveis resultaria em um valor de f (x) menor que 14, nao desejavel uma vez que queremos maximizar a

funcao objetivo.

Entao, temos a melhor resposta possıvel para o caso, isto e, a solucao otima do sistema e f (x) = 14, com os

valores de: x1 = 4, x2 = 2 e x4 = 7. Substituindo na funcao 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 Multiplas Solucoes e Solucoes Ilimitadas.

Tambem discutiremos Solucao Inexistente, Escolha Inicial e Degeneracao.

3.2.10 Analise de Casos Especiais.

Multiplas Solucoes.

Seja o modelo proposto:

max f (x) = 2x1 + 4x2

Sujeito a: x1 + 2x2 ≤ 5

x1 + x2 ≤ 4

x1, x2 ≥ 0

Reescrevendo o sistema para aplicarmos o Simplex, temos:



max f (x) − 2x1 − 4x2 + 0x3 + 0x4 = 0

Sujeito a: x1 + 2x2 + x3 = 5

x1 + x2 + + x4 = 4

xi ≥ 0, p/ i = 1 : 4

Realizando-se a passagem para o quadro:

Base f (x) x1 x2 x3 x4 b Linha

max 1 –2 –4 0 0 0 (0)

x3 0 1 2 1 0 5 (1)

x4 0 1 1 0 1 4 (2)

Tabela 3.9: Dados apresentados na forma de quadro.

Apos as operacoes necessarias, com a entrada de x2 e a saıda de x3, obtemos o sistema abaixo:


max 1 0 0 2 0 10 (0)

x2 0 1/2 1 1/2 0 5/2 (1)

x4 0 1/2 0 –1/2 1 3/2 (2)


Verificamos que o valor da funcao f (x) para este caso e 10. A solucao e x1 = 0 e x2 =5

2, contudo, como

saber se existem outras tantas solucoes?

Resposta: Devemos observar que o coeficiente de x1 apos a primeira iteracao e zero, isto e, a variavel x1 pode

entrar na base sem que ocasione mudanca na solucao encontrada.

Vejamos entao se procedermos com uma segunda iteracao, inserindo x1 e retirando-se x4, com resultado

apresentado:


max 1 0 0 2 0 10 (0)

x2 0 0 1 1 –1 1 (1)

x1 0 1 0 –1 2 3 (2)


Observe que apos a segunda iteracao, a variavel x4 ficou com coeficiente nulo. Isto indica que o otimo da

funcao neste caso esta enquadrado na reta x1 + 2x2 = 5, que pertence a primeira restricao do problema.

Resumindo: na Solucao Multipla, ocorre um processo no qual a variavel de entrada nao ocasiona mudanca no

valor da funcao objetivo. E mesmo apos mais uma iteracao, a resposta permanece a mesma (exceto se a variavel

que for entrada nao e condizente com o criterio da funcao objetivo - maximizacao ou minimizacao). Para mais

informacoes, vide [14].

Solucao Ilimitada.

Vejamos o problema:



max f (x) = 2x1 + x2

Sujeito a: x1 − x2 ≤ 10

2x1 ≤ 40

x1, x2 ≥ 0

Para aplicarmos o Metodo Simplex realizamos as mudancas, obtendo:

max f (x) − 2x1 − x2 + 0x3 + 0x4 = 0

Sujeito a: x1 − x2 + x3 = 10

2x1 + + x4 = 40

xi ≥ 0, p/ i = 1 : 4

Na forma de quadro:


max 1 -2 -1 0 0 0 (0)

x3 0 1 -1 1 0 5 (1)

x4 0 2 0 0 1 4 (2)


Neste caso, o que ocorre no quadro e que em algum passo do Metodo Simplex, havera na linha(0) uma variavel

xk com coeficiente indicando melhoria na funcao objetivo, porem todos os coeficientes da coluna aik dessa variavel

sao nao positivos, nao possibilitando o teste do coeficiente (essa variavel pode ser aumentada indefinidamente,

uma vez que nenhuma outra se anulara).

Neste exemplo ocorre esse fato antes da primeira iteracao. A visualizacao grafica e dada pela Figura 3.3.

Da Figura 3.3 (A) e a restricao 2x1 ≤ 40, (B) a reta funcao objetivo f (x) = 2x1 + x2 e (C) a restricao

x1 − x2 ≤ 10. Note que a funcao tem como regiao de solucao a interseccao com a regiao factıvel.

Solucao Inexistente ou Infactıvel.

Se o conjunto de restricoes e incompatıvel, o que significa conjunto solucao vazio, a aplicacao do Metodo

Simplex produzira uma anomalia que impedira a identificacao da solucao basica (pois nenhuma existe). Observe o

problema abaixo:

max f (x) = 3x1 + 2x2

Sujeito a: 2x1 + x2 ≤ 2

3x1 + 4x2 ≥ 12

x1, x2 ≥ 0

A funcao objetivo corta a regiao fora das duas areas delimitadas pelas restricoes, sendo assim, nenhum ponto

de solucao e encontrado.

Escolha Inicial - Empate na Entrada.

Como dito, nao ha um criterio claro quanto a escolha da variavel que devera entrar na base do sistema. Podemos

atentar para os coeficientes das variaveis na funcao objetivo, isto e, qual a influencia deles quando os valores das

variaveis oscilam.



Figura 3.3: Regiao do Exemplo 3.12.

Em alguns casos, na funcao objetivo pode ocorrer um empate nos coeficientes das variaveis, como por exemplo,

na funcao 3x1 + 3x2. Se ocorrer algo assim, tanto no inıcio quanto em alguma das iteracoes (ha mais de um

coeficiente com custos relativos iguais pleiteando entrada na base), a escolha fica aleatoria.

Escolha no Termino de uma Iteracao - Empate na Saıda e Degeneracao.

A ocorrencia 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 variaveis que podem sair da base.

No caso do empate dos quocientes, apos se pivotar, a variavel mantida na base ficara com valor zero. Dizemos,

entao, que a solucao basica e degenerada. A degeneracao consiste em uma solucao basica na qual uma das

variaveis basicas tem o valor zero. No comeco do uso do Metodo Simplex, essa problematica despertava interesse,

uma vez que poderia ocorrer o que se chama de ciclagem ou loop (quando uma variavel fica nula e tende a ser

tirada da base, contudo no novo passo a variavel que entrou nao ocasiona mudanca no valor da funcao, gerando

assim um processo infinito de troca de base).

Em modelos reais, pelo arredondamento e pelos coeficientes menos exatos, esse problema tende a nao ocorrer.

Contudo, ressaltamos que se houver algum erro durante o processo de calculo computacional, esse fenomeno nao

deve ser totalmente descartado.

3.2.11 Base Artificial.

Ate aqui todos os problemas apresentados estavam na forma canonica (ou pelo menos em uma forma padrao

de facil transformacao) e com uma base inicial. Entretanto, apesar desta ser a condicao inicial para a aplicacao do

algoritmo, em muitos problemas nao se tem uma base inicial, impossibilitando o uso do Metodo Simplex.



Nesta secao serao abordados dois recursos para lidar com a situacao descrita anteriormente. Tais metodos

consistem na insercao de variaveis artificiais, produzindo como consequencia uma base artificial. Com esse artifıcio

espera-se que, por meio de pivoteamentos, a base artificial seja substituıda por uma base com variaveis reais do

modelo.

Variaveis Artificiais.

Para o caso geral, introduzimos m variaveis artificiais a cada equacao. As vezes, o modelo apresenta variaveis

que so figuram em uma equacao, constituindo parte de uma base. Nesse caso, podemos economizar nas variaveis

a serem introduzidas, de modo que o numero de variaveis artificiais pode ser inferior a m.

Seja o sistema geral:

max c1x1 + c2x2 + . . . cnxn

Suj. a: a11x1 + a12x2 + . . . a1nxn + xa1 = b1

a21x1 + a22x2 + . . . a2nxn + xa2 = b1

......

......

. . . =...

am1x1 + am2x2 + . . . amnxn +xam = b1

x1, . . . , xn, xa1, . . . , xam ≥ 0

Embora agora o problema esteja na forma esperada para ser utilizado pelo Metodo Simplex, temos variaveis

que nao fazem parte do sistema original. Na solucao final desejamos que as variaveis extras sejam retiradas da

base estando no nıvel zero. Para forcar a saıda das variaveis artificiais, utilizamos dois metodos: Metodo do M

Grande e o Metodo das Duas Fases.

3.2.12 O Metodo do M-Grande

O Metodo do M-Grande, ou Big M, consiste em se acrescentar a funcao objetivo do problema original as

variaveis artificiais com coeficientes negativos muito grandes (−M) nos casos de maximizacao, ou (+M) no caso

de minimizacao.

Como se quer aperfeicoar a funcao objetivo, as variaveis artificiais deverao ter seus valores reduzidos a zero e

sair da base. Se, ao final das iteracoes necessarias de otimizacao, for encontrado um valor otimo de f (x), e todas

as variaveis artificiais estiverem nulas e fora da base, entao este valor sera o mesmo do problema original, indicando

tambem o valor das variaveis de decisao.

Caso a solucao otima contenha uma variavel artificial, o problema e infactıvel, apontando que nem todas as

variaveis artificiais puderam ser retiradas da base. Contudo, se na solucao, o otimo de f (x) conter alguma variavel

artificial na base com valor nulo, significa entao que as equacoes nas quais elas estao presentes sao redundantes

no sistema, podendo ser eliminadas.

A seguir apresentamos um exemplo de como esse metodo e utilizado em problemas manuais.

Exemplo 16. Seja o seguinte problema com duas variaveis:

min f (x) = 4x1 + x2

Suj. a: 3x1 + x2 = 3

4x1 + 3x2 ≥ 6

x1 + 2x2 ≤ 4

x1, x2 ≥ 0



Acrescentando duas variaveis x3 de sobra e x4 de folga, na forma de equacoes temos:

min f (x) = 4x1 + x2

Suj. a: 3x1 + x2 = 3

4x1 + 3x2 − x3 = 6

x1 + 2x2 + x4 = 4

x1, x2, x3, x4 ≥ 0

A terceira equacao tem uma variavel da folga (x4), mas a primeira e a segunda nao tem. Colocamos entao

variaveis artificiais Xa1 e Xa2 (estao em maiusculo para destacar que tratam-se de variaveis artificiais) e com os

coeficientes M positivos, pois e um problema de minimizacao:

min f (x) = 4x1 + x2 + MXa1 + MXa2

Suj. a: 3x1 + x2 + Xa1 = 3

4x1 + 3x2 − x3 + Xa2 = 6

x1 + 2x2 + x4 = 4

x1, x2, x3, x4, Xa1, Xa2, ≥ 0

Agora temos uma solucao basica inicial dada por (Xa1, Xa2, x4) = (3, 6, 4). Em muitas obras literarias, M

e manipulado algebricamente (nao esta associado valor algum a variavel, usando-a apenas nos calculos), contudo,

como e mais usual a implementacao dos problemas na forma computacional, utilizaremos um valor numerico para

M.

O valor a ser escolhido deveria ser teoricamente infinito contudo, na rotina dos calculos em computadores, a

interacao entre numeros 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 relacao aos coeficientes

da funcao objetivo, sendo assim, no presente caso utilizaremos M = 100, pois os coeficientes de x1 e x2 sao

respectivamente 4 e 1, ou seja, 100 e grande se comparado a esses valores.

O sistema em forma de quadros e:

Base f (x) x1 x2 x3 Xa1 Xa2 x4 b Linha

min 1 -4 -1 0 100 100 0 0 (0)

Xa1 0 3 1 0 1 0 0 3 (1)

Xa2 0 4 3 -1 0 1 0 6 (2)

x4 0 1 2 0 0 0 1 4 (3)


Podemos observar no quadro, que a solucao inicial resulta em f (x) = 900 e nao zero como mostrado na linha(0),

isto ocorre pois, os coeficientes de Xa1 e Xa2 sao 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 variaveis artificiais

na funcao 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 minimizacao, o coeficiente de maior valor positivo devera entrar na base,

neste caso a variavel e x1. A razao mınima da condicao de viabilidade especifica Xa1 como a variavel que sai. Apos

as operacoes pertinentes, temos os resultados da Tabela 3.15.

Agora quem devera entrar e x2, saindo Xa2 da base. Apos mais duas iteracoes, a solucao sera:




min 1 696 399 -100 0 0 0 900 (0)

Xa1 0 3 1 0 1 0 0 3 (1)

Xa2 0 4 3 -1 0 1 0 6 (2)

x4 0 1 2 0 0 0 1 4 (3)

Tabela 3.14: Dados transformados para a realizacao dos passos do Simplex.


min 1 0 167 -100 -232 0 0 204 (0)

x1 0 1 1/3 0 1/3 0 0 1 (1)

Xa2 0 0 5/3 -1 -4/3 1 0 2 (2)

x4 0 0 5/3 0 -1/3 0 1 3 (3)


x1 =2

5; x2 =

9

5com f (x) =

17

5.

3.2.13 O Metodo das Duas Fases

O metodo das duas fases consiste em:

1. Primeira Fase

Coloque o sistema na forma de resolucao do Simplex, incluindo as variaveis nao basicas e artificiais. Inde-

pendentemente do requisito da funcao objetivo – maximizacao ou minimizacao – faca um quadro com uma

funcao de minimizacao da soma das variaveis artificiais no lugar da funcao objetivo.

• Se o valor mınimo da soma for positivo, o problema de PL nao tem solucao viavel, ou seja, alguma(s)

das variaveis artificiais nao saiu da base;

• Caso contrario, passamos a segunda fase.

2. Segunda Fase

Com a solucao encontrada no sistema anterior, substituımos r por f (x) no quadro, utilizando posteriormente

essa mesma solucao como a solucao basica viavel inicial para o problema original.

Exemplo 17. Considere o problema de PL do Exemplo 16.

• Fase Imin r = Xa1 +Xa2

Sujeito a 3x1 + x2 +Xa1 = 3

4x1 + 3x2 − x3 +Xa2 = 6

x1 + 2x2 + x4 = 4

x1, x2, x3, x4, Xa1, Xa2 ≥ 0

A Tabela 3.16 esta associado ao problema acima.



Base x1 x2 x3 Xa1 Xa2 x4 f (x)

r -7 -4 1 0 0 0 9

Xa1 3 1 0 1 0 0 3

Xa2 4 3 –1 0 1 0 6

x4 1 2 0 0 0 1 4


Como no metodo M-grande, Xa1 e Xa2 sao 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 otima.

Base x1 x2 x3 Xa1 Xa2 x4 f (x)

r 0 0 0 –1 –1 0 0

x1 1 0 1/5 3/5 -1/5 0 3/5

x2 0 1 –3/5 –4/5 3/5 0 6/5

x4 0 0 1 1 –1 1 1

Tabela 3.17: Final da Fase I.

Como mınimo r = 0, a Fase I produz a solucao basica viavel x1 =3

5, x2 =

6

5e x4 = 1. Nesse ponto,

as variaveis artificiais concluıram sua missao e podemos eliminar totalmente suas colunas da tabela (e da

formulacao do problema de PL) e passar para a Fase II.

• Fase II

Escrevemos o problema original como:

min f (x) = 4x1 + x2

Sujeito a x1 +1

5x3 =

3

5

x2 −3

5x3 =

6

5x3 + x4 = 1

x1, x2, x3, x4 ≥ 0

Em essencia, a Fase I e um procedimento que transforma as equacoes de restricao originais de maneira a

fornecer uma solucao basica viavel inicial para o problema, se houver.

Agora, aplica-se o metodo Simplex ate obter a solucao otima (verifique como exercıcio).

3.3 Analise de SensibilidadeConsidere a questao a seguir: dada a solucao otima de um problema de Programacao Linear, para quais faixas

de valores dos coeficientes a solucao otima seria mantida? Para responder essa questao, fazemos o que se chama

de Analise de Sensibilidade.

De modo geral, os parametros em modelos de PL nao sao exatos. Com a analise de sensibilidade podemos

averiguar o impacto dessa incerteza sobre a qualidade da solucao otima. Por exemplo, no caso do lucro unitario



estimado de um produto, se a analise de sensibilidade revelar que a solucao otima nao muda para uma variacao de

±10% no lucro unitario, podemos concluir que a solucao e mais encorpada do que quando a faixa de indiferenca e

de apenas ±1%.

Os tipos de analises a serem feitas podem ser agrupadas de acordo com as alteracoes em:

• Alteracoes Simples

– alteracoes nos coeficientes de custo, cj ;

– alteracoes nas constantes bi ;

– alteracoes nas restricoes, como adicao (ou exclusoes) de restricoes ou variaveis.

• Alteracoes Sistematicas - Programacao Parametrica

– alteracoes sistematicas nos cj ;

– alteracoes sistematicas nos bi ;

Note que quando falamos de Analise de Sensibilidade, estamos nos referindo as alteracoes pontuais, uma de

cada vez. Caso existam modificacoes simultaneas em diversas partes do problema, devemos considera-lo como

novo, resolvendo-o desde o ınicio.

Nesta secao trataremos graficamente e algebricamente dos casos:

1. Alteracoes nas constantes bi (lado direito das restricoes);

2. Alteracoes nos coeficientes de custo, cj (coeficientes da funcao objetivo).

Para tanto utilizaremos exemplos.

3.3.1 Analise de Sensibilidade grafica

Alteracoes nas constantes bi (lado direito das restricoes)

Exemplo 18. A Jobco produz dois produtos em duas maquinas. Uma unidade do produto 1 requer duas horas

na maquina 1 e uma hora na maquina 2. Para o produto 2, uma unidade requer uma hora da maquina 1 e tres

horas da maquina 2. As receitas por unidade dos produtos 1 e 2 sao $30 e $20, respectivamente. O tempo de

processamento diario disponıvel para cada maquina e oito.

Representando o numero diario 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 (Maquina 1)

x1 + 3x2 ≤ 8 (Maquina 2)

x1, x2 ≥ 0

A figura 3.4 ilustra a variacao na solucao otima quando sao feitas alteracoes na capacidade da maquina 1. Se

a capacidade diaria for aumentada de oito horas para nove horas, a nova solucao otima ocorrera no ponto G.

A taxa de variacao em f (x) otima resultante da alteracao da capacidade da maquina 1 pode ser calculada da

seguinte maneira:



Figura 3.4: Grafico de analise de sensibilidade da solucao otima a variacoes na disponibilidade de recursos.

Taxa de variacao na

receita resultante do

aumento de uma hora na

capacidade da maquina

(ponto C para ponto G)

= zg − zc(Alteracao na capacidade)

= 142− 128

9− 8

= $14/h.

A taxa calculada fornece uma ligacao direta entre a entrada do modelo (recursos) e sua saıda (receita total),que

representa o valor unitario equivalente de um recurso (em $/hora), isto e, a variacao no valor otimo da funcao

objetivo por unidade de variacao na disponibilidade do recurso (capacidade da maquina). Isso significa que uma

unidade de aumento (reducao) na capacidade da maquina 1 aumentara (reduzira) a receita em $14. Embora o

valor unitario equivalente de um recurso seja uma descricao adequada da taxa de variacao da funcao objetivo,

o nome tecnico, preco dual ou preco sombra, agora e um padrao na literatura de PL, e em todos os pacotes

comerciais.

Examinada a figura 3.4, podemos ver que o preco dual de 14/h permanece valido para variacoes (aumentos

ou reducoes) na capacidade da maquina 1 que deslocam sua restricao paralelamente para qualquer ponto sobre o

segmento de reta BF . Isso significa que a faixa de aplicabilidade de determinado preco dual pode ser calculada da

seguinte maneira:

Capacidade mınima da maquina 1 (em B = (0, 2.67)) = 2× 0 + 1× 2.67 = 2.67/h

Capacidade maxima da maquina 1 (em E = (8, 0)) = 2× 8 + 1× 0 = 16/h

Deste modo, podemos concluir que o preco dual permanecera valido para a faixa:

2.67/h ≤ Capacidade da maquina 1 ≤ 16/h.

Variacoes fora dessa faixa produzirao um preco dual (equivalente por unidade) diferente.



Usando calculos semelhantes, voce pode verificar que o preco dual para a capacidade da maquina 2 e de $2/h e

permanece valido para variacoes (aumentos ou reducoes) que deslocam sua restricao paralelamente para qualquer

ponto sobre o segmento de reta DE, o que resulta nos seguintes limites:

Capacidade mınima da maquina 2 (em D = (4, 0)) = 1× 4 + 3× 0 = 4/h

Capacidade maxima da maquina 2 (em D = (0, 8)) = 1× 0 + 3× 8 = 24/h

A conclusao e que o preco dual de $2/h para a maquina 2 continuara aplicavel para a faixa:

4 horas ≤ Capacidade da maquina 2 ≤ 24 horas

Os limites calculados para as maquinas 1 e 2 sao denominados faixas de viabilidade.

Os precos duais permitem tomar decisoes economicas sobre o problema de PL como demonstram as respostas

as perguntas apresentadas a seguir.

1. Se Jobco puder aumentar a capacidade de ambas as maquinas, qual deve receber maior prioridade?

2. E dada uma sugestao para aumentar as capacidades as maquinas 1 e 2 ao custo adicional de $10/h. Isso e

aconselhavel?

Pense na resposta e o porque da decisao.

Alteracoes nos coeficientes de custo, cj (coeficientes da funcao objetivo)

Exemplo 19. A figura 3.5 mostra o grafico da regiao de solucoes do problema da Jobco apresentado no Exemplo

18. A solucao otima ocorre no ponto C (x1 = 3.2; x2 = 1.6; f (x) = 128).

Figura 3.5: Analise de sensibilidade da solucao otima as variacoes nas receitas unitarias (coeficientes da funcao

objetivo).



Alteracoes nas receitas unitarias (isto e, nos coeficientes da funcao objetivo) alterarao da inclinacao de f (x).

Contudo, como podemos ver pela figura, a solucao otima continuara no ponto C contanto que a funcao objetivo

esteja entre as retas BF e DE (retas que representam as restricoes das maquinas 1 e 2, respectivamente), as duas

restricoes que definem o ponto otimo. Isso significa que ha uma faixa para os coeficientes da funcao objetivo que

mantera inalterada a solucao otima em C.

Podemos escrever a funcao objetivo no formato geral.

max f (x) = c1x1 + c2x2

Agora imagine que a reta f (x) gire em torno de C no sentido horario e anti-horario. A solucao otima permanecera

no ponto C enquanto f (x) = c1x1 + c2x2 estiver entre as duas retas, x1 + 3x2 = 8 e 2x1 + x2 = 8. Isso significa

que a razao c1

c2pode variar entre 1

3 e 21 , o que resulta na seguinte condicao:

1

3≤c1

c2≤

2

1ou 0.333 ≤

c1

c3≤ 2

Essa informacao pode fornecer respostas imediatas referentes a solucao otima, como demonstram as respostas

as perguntas a seguir.

1. Suponha que as receitas unitarias para os produtos 1 e 2 sejam alteradas para $35 e $25, respectivamente.

A solucao otima atual permanecera a mesma?

2. Suponha que a receita unitaria do produto 2 seja fixada em um valor atual de c2 = $20. Qual e a faixa de

variacao para c1, a receita unitaria do produto 1, que mantera a solucao otima inalterada?

Tente responder as questoes.

3.3.2 Analise de Sensibilidade algebrica

Alteracoes nas constantes bi (lado direito das restricoes)

Esta secao estende a analise ao modelo geral de PL. Um exemplo numerico sera usado para facilitar a apre-

sentacao.

Exemplo 20. A Toyco monta tres tipos de brinquedos – trens, caminhoes e carros – usando tres operacoes. Os

limites diarios dos tempos disponıveis para as tres operacoes sao 430, 460 e 420 minutos, respectivamente, e as

receitas por unidade de trem, caminhao e carro de brinquedos sao $3, $2 e $5 ,respectivamente. Os tempos de

montagem por trem nas tres operacoes sao 1, 2 e 1 minutos, respectivamente. Os tempos correspondentes por

caminhao e por carro sao (3, 0, 2) e (1, 4, 0) minutos (o tempo zero indica que a operacao nao foi usada).

Representando o numero diario de unidades montadas de trens, caminhoes e carros,respectivamente, o problema

de PL associado e dado por:

max f (x) = 3x1 + 2x2 + 5x3

Sujeito a x1 + 2x2 + x3 ≤ 430 (Operacao 1)

3x1 + 2x3 ≤ 460 (Operacao 2)

x1 + 4x2 ≤ 420 (Operacao 3)

x1, x2, x3 ≥ 0

Usando x4, x5 e x6 como variaveis de folga para as restricoes das operacoes 1, 2 e 3, respectivamente, a tabela

encontrada ao final da resolucao e:



Base f(x) x1 x2 x3 x4 x5 x6 b Linha

max 1 4 0 0 1 2 0 1350 (0)

x2 0 -1/4 1 0 1/2 -1/4 0 100 (1)

x3 0 3/2 0 1 0 1/2 0 230 (2)

x6 0 2 0 0 -2 1 1 20 (3)

Tabela 3.18: Dados da solucao otima do problema .

A solucao recomenda a fabricacao de 100 caminhoes e 230 carros, mas nenhum trem. A receita associada e

$1350.

Determinacao de precos duais

As restricoes do modelo apos a adicao das variaveis de folga x4, x5 e x6 podem ser expressas como

x1 + 2x2 + x3 + x4 = 430 (Operacao 1)

3x1 + 2x3 + x5 = 460 (Operacao 2)

x1 + 4x2 + x6 = 420 (Operacao 3)

oux1 + 2x2 + x3 = 430 − x4 (Operacao 1)

3x1 + 2x3 = 460 − x5 (Operacao 2)

x1 + 4x2 = 420 − x6 (Operacao 3)

Com essa representacao, as variaveis de folga tem as mesmas unidades (minutos) que os tempos de operacao.

Assim, podemos dizer que uma reducao de 1 minuto na variavel de folga e equivalente ao aumento de 1 minuto

no tempo de operacao.

Podemos usar essas informacoes para determinar os precos duais pela equacao de maximizacao de f (x) na

tabela otima 3.18 abaixo:

f (x) + 4x1 + x4 + 2x5 + 0x6 = 1350

Essa equacao pode ser expressa como:

f (x) + 4x1 + x4 + 2x5 + 0x6 = 1350 =⇒ f (x) = 1350− 4x1 + 1(−x4) + 2(−x5) + 0(−x6)

Dado que um decrescimo no valor de uma variavel de folga e equivalente a um aumento em seu tempo de

operacao, obtemos:

f (x) = 1350− 4x1 + 1 (aumento no tempo de Operacao 1)

+ 2 (aumento no tempo de Operacao 2)

+ 0 (aumento no tempo de Operacao 3)

Essa equacao revela que

1. um aumento de 1 minuto no tempo de operacao 1 provoca um aumento de $1 em f (x);

2. um aumento de 1 minuto no tempo de operacao 2 provoca um aumento de $2 em f (x);

3. um aumento de 1 minuto no tempo de operacao 3 nao altera f (x);



Resumindo, a linha (0) na tabela simplex otima fornece diretamente os precos duais, como mostra a Tabela

3.19.

Recurso Variavel Coeficiente da variavel de Preco dual

de folga folga na linha (0) ($/minuto)

Operacao 1 x4 1 1

Operacao 2 x5 2 2

Operacao 3 x4 0 0

Tabela 3.19: Precos duais .

Esses calculos mostram como os precos duais sao determinados de acordo com a tabela simplex otima para

restricoes ≤. Para restricoes ≥, a mesma ideia continua aplicavel, exceto que o preco dual assumira o sinal oposto

do associado a restricao ≤. Quanto ao caso em que a restricao for uma equacao, a determinacao do preco dual

com base na tabela simplex otima requer calculos mais aprimorados (vide [Taha]).

Determinacao das faixas de viabilidade

Agora que ja determinamos os precos duais, mostreremos como sao determinadas as faixas de viabilidade nas

quais os precos permanecem validos. Representando as variacoes (positivas ou negativas) nos tempos diarios de

fabricacao alocados as operacoes 1, 2 e 3 por D1, D2 e D3, respectivamente, o modelo pode ser expresso da

seguinte maneira:

x1 + 2x2 + x3 ≤ 430 + D1 (Operacao 1)

3x1 + 2x3 ≤ 460 + D2 (Operacao 2)

x1 + 4x2 ≤ 420 + D3 (Operacao 3)

x1, x2, x3 ≥ 0

Consideraremos o caso geral de alteracoes simultaneas. Os casos especiais de uma alteracao por vez sao

derivados desses resultados.

O procedimento e baseado em recalcular a tabela simplex otima com o lado direito modificado, e depois derivar

as condicoes que manterao a solucao viavel, isto e, o lado direito da tabela otima permanecera nao negativo. Para

mostrar como o lado direito e recalculado, comecamos modificando a coluna Solucao da tabela inicial usando novos

lados direitos. Assim, a tabela simplex inicial tera o seguinte aspecto:

Base f(x) x1 x2 x3 x4 x5 x6 LD D1 D2 D3

max 1 -3 -2 -5 0 0 0 0 0 0 0

x4 0 1 2 1 1 0 0 430 1 0 0

x5 0 3 0 2 0 1 0 460 0 1 0

x6 0 1 4 0 0 0 1 420 0 0 1

Tabela 3.20: Dados para calculos das faixas de viabilidade.

As colunas sob D1, D2 e D3 sao identicas as que estao sob as colunas basicas iniciais x4, x5 e x6. Isso significa

que, quando executamos as mesmas iteracoes simplex que as do modelo original, as colunas dos dois grupos devem

ter resultados identicos tambem. Na verdade, a nova tabela otima ficara:



Base f(x) x1 x2 x3 x4 x5 x6 LD D1 D2 D3

max 1 4 0 0 1 2 0 1350 1 2 0

x2 0 -1/4 1 0 1/2 -1/4 0 100 1/2 -1/4 0

x3 0 3/2 0 1 0 1/2 0 230 0 1/2 0

x6 0 2 0 0 -2 1 1 20 -2 1 1

Tabela 3.21: Dados finais para os calculos das faixas de viabilidade.

A nova tabela simplex otima fornece a seguinte solucao otima:

f (x) = 1350 +D1 + 2D2

x2 = 100 +1

2D1 −

1

4D2

x3 = 230 +1

2D2

x6 = 20− 2D1 +D2 +D3

A solucao atual permanece viavel, contanto que todas as variaveis sejam nao negativas, o que resulta nas

seguintes condicoes de viabilidade:

x2 = 100 +1

2D1 −

1

4D2 ≥ 0

x3 = 230 +1

2D2 ≥ 0

x6 = 20− 2D1 +D2 +D3 ≥ 0

Quaisquer variacoes simultaneas de D1, D2 e D3 que satisfacam essas desigualdades manterao a solucao viavel.

Se todas as condicoes forem satisfeitas, entao a nova solucao otima pode ser encontrada por meio de substituicao

direta de D1, D2 e D3 nas equacoes dadas anteriormente.

Vejamos tres situacoes sobre o resultado acima:

1. Suponha que o tempo de fabricacao disponıvel para as operacoes 1, 2 e 3 sejam 480, 440 e 410 minutos,

respectivamente. Para esta situacao a solucao atual permanece viavel?

2. E se os tempos forem 400, 482 e 450 minutos?

3. Como calculamos as faixas de viabilidade individuais que resultam da variacao dos recursos um por vez?

Desenvolva cada item.

Alteracoes nos coeficientes de custo, cj (coeficientes da funcao objetivo)

Exemplo 21. Definicao de custo reduzido. Para facilitar a explicacao da analise de sensibilidade da funcao

objetivo, primeiro precisamos definir custos reduzidos. No modelo da Toyco, a funcao objetivo f (x) na tabela

otima e:

f (x) = 1350− 4x1 − x4 − 2x5

A solucao otima nao recomenda a producao de trens de brinquedo (x1 = 0). Essa recomendacao e confirmada

pela informacao 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.



Podemos considerar o coeficiente de x1 como um custo unitario porque ele provoca uma reducao na receita f (x).

Mas de onde vem esse ”custo”? Sabemos que x1 tem sua receita unitaria de $3 no modelo original. Tambem

sabemos que cada trem de brinquedo consome recursos (tempos de operacoes) que, por sua vez, incorrem em

custo. Assim, a ”atratividade” de x1 do ponto de vista da otimizacao depende dos valores relativos da receita por

unidade e do custo dos recursos consumidos por unidade. Essa relacao e formalizada ao se definir custo reduzido

como:

(Custo reduzido por unidade) = (Custo dos recursos consumidos por unidade) − (Receita por unidade)

Para avaliar a relevencia dessa definicao, no modelo original da Toyco, a receita por unidade para caminhoes de

brinquedo (= $2) e menor do que a para trens de brinquedo ($3). Ainda assim, a solucao otima aconselha fabricar

caminhoes de brinquedo (x2 = 100 unidades) e nenhum trem. A razao para esse resultado (aparentemente nao

intuitivo) e que o custo unitario dos recursos usados para caminhoes de brinquedo (isto e, tempos de operacoes)

e menor do que seu preco unitario. O oposto se aplica ao caso dos trens de brinquedo.

Pela definicao dada de custo reduzido, agora podemos ver que uma variavel nao lucrativa (como x1) pode vir

a ser lucrativa de dois modos:

1. Com o aumento da receita unitaria;

2. Com a reducao de custo unitario dos recursos consumidos.

Em grande parte das situacoes reais, o preco por unidade pode nao ser uma opcao viavel porque seu valor e

determinado por condicoes de mercado. Portanto, a opcao real e reduzir o consumo de recursos, talvez aumentando

a eficiencia do processo de producao.

Determinacao das faixas de otimalidade

Agora voltemos nossa atencao a determinacao das condicoes que manterao uma solucao otima inalterada. A

apresentacao e baseada na definicao de custo reduzido.

No modelo da Toyco, representamos a variacao nas receitas unitarias para caminhoes, trens e carros de brinquedo

por d1, d2 e d3, respectivamente. Desse modo, a funcao objetivo se torna:

max f (x) = (3 + d1)x1 + (2 + d2)x2 + (5 + d3)x3

O procedimento para a analise de sensibilidade e o mesmo para o lado direito, realizado anteriormente. Com

as variacoes simultaneas, a linha (0) na tabela simplex inicial aparece como:

Base f(x) x1 x2 x3 x4 x5 x6 Solucao

max 1 −3− d1 −2− d2 −5− d3 0 0 0 0

Tabela 3.22: Dados da linha (0).

Quando geramos as tabelas simplex usando a mesma sequencia das variaveis que entram e que saem do modelo

original (antes da introducao das variaveis dj), a iteracao otima aparecera como segue na Tabela 3.23.

Como estamos lidando com um problema de maximizacao, a solucao atual permanece otima, contanto que os

novos custos reduzidos permanecam nao negativos para todas as variaveis nao basicas. Assim, temos as seguintes

condicoes de otimalidade correspondentes as variaveis nao basicas x1, x4 e x5:



Base f(x) x1 x2 x3 x4 x5 x6 Solucao

max 1 4− 14d2 + 3

2d3 − d1 0 0 1 + 12d2 2− 1

4d2 + 12d3 0 1350 + 100d2 + 230d3

x2 0 -1/4 1 0 1/2 -1/4 0 100

x3 0 3/2 0 1 0 0 1/2 230

x6 0 -1/4 0 0 -2 1 1 20

Tabela 3.23: Nova tabela simplex.

x1 = 4−1

4d2 +

3

2d3 − d1 ≥ 0

x4 = 1 +1

2d2 ≥ 0

x5 = 2−1

4d2 +

1

2d3 ≥ 0

Essas condicoes devem ser satisfeitas simultaneamente para manter a otimalidade da solucao otima atual.

Considere uma modificacao como:

1. Para ilustrar a utilizacao dessas condicoes, suponha que a funcao objetivo da Toyco seja alterada de

max f (x) = 3x1 + 2x2 + 5x3

para

max f (x) = 2x1 + x2 + 6x3

A solucao otima sera mantida?

3.4 Exercıcios Propostos1. Resolva o programa linear em uma iteracao:

max f (x) = 12x1 + 9x2 + 10x3

Sujeito a x1 + x2 + x3 ≤ 112x1 + 7

4x2 + x3 ≤ 5

3x1 + 7x2 + 5x3 ≤ 5

x1, x2, x3 ≥ 0

2. Resolva o seguinte problema de programacao linear utilizando o Metodo Simplex:

max f (x) = x1 + 2x2

Sujeito a 6x1 + 10x2 ≤ 30

x1 ≤ 6

x1, x2 ≥ 0



3. Utilize o Metodo Simplex para resolver o seguinte problema de Programacao Linear:

max f (x) = 5x1 + 2x2

Sujeito a x1 ≤ 4

x2 ≤ 5

−2x1 + x2 ≤ 10

x1, x2 ≥ 0

4. Resolva, utilizando o Metodo das Duas Fases, o seguinte problema de programacao linear:

max f (x) = x1 + 2x2 + 3x3 − x4

Sujeito a x1 + 2x2 + 3x3 = 15

−2x1 + x2 + 5x3 = −20

x1 + 2x2 + x3 + x4 = 10

x1, x2, x3, x4 ≥ 0

5. Resolva o problema de programacao linear proposto a seguir e constate que a solucao e ilimitada:

max f (x) = 2x1 + 3x2

Sujeito a x1 + 2x2 ≥ 8

−2x1 + 3x2 ≤ 5

x1 + x2 ≥ 6

x1, x2 ≥ 0

6. Considere o seguinte problema de PL:

max f (x) = 2x1 + 3x2

Sujeito a x1 + 3x2 ≤ 6

3x1 + 2x2 ≤ 6

x1, x2 ≥ 0

(a) Expresse o problema em forma de equacao.

(b) Determine todas as solucoes basicas do problema e classifique-as como viaveis basicas e nao basicas.

(c) Use a substituicao direta na funcao objetivo para determinar a solucao basica viavel otima.

(d) Verifique graficamente que a solucao obtida em (c) e a solucao otima do problema de PL – daı,

conclua que a solucao otima pode ser determinada algebricamente considerando somente solucoes

basicas viaveis.

(e) Mostre como as solucoes basicas nao viaveis sao representadas graficamente na regiao de solucoes.


max f (x) = 2x1 + 3x2 + 5x3

Sujeito a −6x1 + 7x2 − 9x3 ≥ 4

x1 + x2 + 4x3 = 6

x1, x3 ≥ 0

x2 ∈ R



A conversao na forma de equacao envolve utilizar a substituicao x2 = x−2 − x+2 . Mostre que a solucao basica

nao pode incluir ambas, x−2 e x+2 , simultaneamente.


max f (x) = x1 + 3x2

Sujeito a x1 + x2 ≤ 2

−x1 + x2 ≤ 4

x1 ∈ Rx2 ≥ 0

(a) Determine todas as solucoes basicas viaveis do problema.

(b) Use substituicao direta na funcao objetivo para determinar a melhor solucao basica.

(c) Resolva o problema pelo metodo grafico e verifique que a solucao obtida no item anterior e a otima.

9. Considere o seguinte conjunto de restricoes:

x1 + 2x2 + 2x3 + 4x4 ≤ 40

2x1 − x2 + x3 + 2x4 ≤ 8

4x1 − 2x2 + x3 − x4 ≤ 10

x1, x2, x3, x4 ≥ 0

Resolva o problema para cada uma das seguintes funcoes 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

x1, x2, x3, x4 ≥ 0

(a) Resolva o problema por inspecao (nao use as operacoes de linha por Gauss-Jordan) e justifique a resposta

em termos das solucoes basicas do Metodo Simplex.

(b) Repita o item anterior considerando que a funcao objetivo exige min f (x) = x1.


max f (x) = 16x1 + 15x2

Sujeito a 40x1 + 31x2 ≤ 124

−x1 + x2 ≤ 1

x1 ≤ 3

x1, x2 ≥ 0



(a) Resolva o problema pelo metodo simplex, no qual a variavel que entra na base e a variavel nao basica

que tem o coeficiente mais negativo na linha da funcao objetivo.

(b) Resolva o problema pelo metodo simplex, sempre selecionando a variavel que entra na base como a

variavel nao basica que tem o coeficiente menos negativo na linha da funcao objetivo.

(c) Compare o numero de iteracoes dos dois itens anteriores. A selecao da variavel que entra na base como

variavel nao basica que tem o coeficiente mais negativo resulta em um numero menor de iteracoes? A

que conclusao podemos chegar quanto a condicao de otimalidade?

(d) Suponha que o sentido de otimizacao seja mudado para minimizacao multiplicando f (x) por −1. Como

essa alteracao afeta as iteracoes no metodo simplex?

12. Considere o seguinte conjunto de restricoes:

−2x1 + 3x2 = 3 (1)

4x1 + 5x2 ≥ 10 (2)

x1 + 2x2 ≤ 5 (3)

6x1 + 7x2 ≤ 3 (4)

4x1 + 8x2 ≥ 5 (5)

x1, x2 ≥ 0

Para cada um dos problemas a seguir, desenvolva a linha f (x) apos substituir as variaveis 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 metodo do M-Grande vai indicar que o problema a seguir nao tem nenhuma solucao viavel.

max f (x) = 2x1 + 5x2

Sujeito a 3x1 + 2x2 ≥ 6

2x1 + x2 ≤ 2

x1, x2 ≥ 0

14. No modelo da Toyco determine se a solucao 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 eletricos, cada um em uma linha de montagem separada. As

capacidades respectivas das linhas sao 500, 500, 800 e 750 motores por dia. O motor do tipo 1 usa oito

unidades de um certo componente eletronico, 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

pecas por dia. Os precos dos componentes para os respectivos tipos de motor sao $60, $40, $25 e $30 por

motor.



(a) Determine o mix otimo de producao diario.

(b) A atual programacao de producao atende as necessidades da Electra. Contudo, devido a concorrencia,

pode ser que a empresa precise reduzir o preco do motor do tipo 2. Qual e a reducao que pode ser

efetuada sem alterar a programacao da producao atual?

(c) A Electra decidiu reduzir em 25% o preco de todos os tipos de motores. Use analise de sensibilidade

para determinar se a solucao otima permanecera inalterada.

(d) Atualmente, o motor do tipo 4 nao e produzido. De quanto deveria ser o aumento no preco desse motor

para ser incluıdo na programacao de producao?


CAPITULO 4

Dualidade

4.1 Introducao

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 compreensao da Programacao

Linear e da sua interpretacao economica.

No problema Primal busca-se a otimizacao dos nıveis de atividades das variaveis de decisao, entendidas como as

variaveis reais do problema em analise. No problema Dual a preocupacao se da com recursos disponıveis, avaliados

a seus precos sombra (precos duais). Desse modo, o presente capıtulo esta fortemente relacionado com o final do

anterior. Alem disso, as solucoes dos dois problemas estao de tal modo inter-relacionadas pois da solucao otima do

problema Primal e possıvel reconhecer a solucao do Dual. Inversamente, na solucao otima do Dual identificamos

a solucao do Primal.

Inicialmente, mostraremos que o Dual e resultado de um problema de Programacao Linear, e, por meio de

exemplos simples, apresentamos as propriedades do relacionamento entre os dois problemas. Seguem, sem de-

monstracoes formais, mas por meio de apelos intuitivos, os teoremas basicos da dualidade, completando o capıtulo

com a apresentacao do Metodo Dual Simplex.

4.2 Definicao do Problema DualEm grande parte dos tratamentos de PL, o dual e definido para os varios formatos do primal dependendo do

sentido de otimizacao (maximizacao ou minimizacao), dos tipos de restricoes (≤, ≥ ou =) e da orientacao das

variaveis (nao negativas ou irrestrita). Esse tipo de tratamento e um pouco confuso e, por essa razao, oferecemos

uma definicao unica que abranja todas as formas do primal.

Nossa definicao do problema dual requer expressar o problema primal na forma de equacoes (todas as restricoes

sao equacoes cujo lado direito e nao negativo e todas as variaveis sao nao negativas). Esse requisito e consistente

com o formato da tabela simplex inicial. Por consequencia, quaisquer resultados obtidos com base na solucao

otima do problema primal se aplicarao diretamente ao problema dual associado.

Para mostrar como o problema dual e construıdo, o problema primal e definido na forma de equacoes da seguinte

Capıtulo 4. Dualidade PL

maneira:

Maximizar ou Minimizar f (x) =

n∑i=1

cjxj

Sujeito a

n∑i=1

ai jxj = bi , i = 1 : m

xj ≥ 0, j = 1 : n.

As variaveis xj , j = 1 : n incluem as variaveis 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.

Variaveis primais do problema

x1 x2 . . . xj . . . xnVariaveis Lado

duais do c1 c2 . . . cj . . . cn direito

problema

y1 a11 a12 . . . a1j . . . a1n b1

y2 a21 a22 . . . a2j . . . a2n b2

......

.... . .

.... . .

......

ym am1 am2 . . . amj . . . amn bm

Tabela 4.1: Construcao do problema dual com base no problema primal.

Efetivamente, temos:

1. Uma variavel dual e definida para cada equacao (restricao) primal;

2. Uma restricao dual e definida para cada variavel primal;

3. Os coeficientes da restricao (coluna) de uma variavel primal definem os coeficientes do lado esquerdo da

restricao dual e seus coeficientes na funcao objetivo definem os coeficientes do lado direito;

4. Os coeficientes da funcao objetivo do problema dual sao iguais aos coeficientes do lado direito das equacoes

de restricao do problema primal.

As regras para determinar o sentido da otimizacao (maximizacao ou minimizacao), o tipo da restricao (≤, ≥ou =) e o sinal das variaveis duais estao na tabela 4.2.

Funcao objetivo do Problema dual

problema primal Objetivo Tipos de restricoes Sinal das variaveis

Maximizacao Minimizacao ≥ Irrestrita

Minimizacao Maximizacao ≤ Irrestrita

Tabela 4.2: Regras para construir o problema dual.

Observe que o sentido da otimizacao no dual e sempre oposto ao do primal. Os exemplos a seguir demonstram

a utilizacao das regras de construcao do problema dual e tambem que a definicao dada anteriormente incorpora

todas as formas do primal.

Exemplo 22. O Problema Primal e:

max f (x) = 5x1 + 12x2 + 4x3

Sujeito a x1 + 2x2 + x3 ≤ 10

x1 − x2 + 3x3 = 8

x1, x2, x3 ≥ 0



Na forma padrao:

max f (x) = 5x1 + 12x2 + 4x3 + 0x4

Sujeito a x1 + 2x2 + x3 + x4 = 10

x1 − x2 + 3x3 = 8

x1, x2, x3, x4 ≥ 0

As variaveis duais sao 10y1 e 8y2. O Problema Dual fica como:

min f (y) = 10y1 + 8y2

Sujeito a y1 + y2 ≥ 5

2y1 − y2 ≥ 12

y1 + 3y2 ≥ 4

y1 + 0y2 ≥ 0

y1, y2 irrestritas

Agora utilizaremos um exemplo de minimizacao como primal.

Exemplo 23. O Problema Primal e:

min f (x) = 15x1 + 12x2

Sujeito a x1 + 2x2 ≥ 3

2x1 − 4x2 ≤ 5

x1, x2 ≥ 0

Na forma padrao:

min f (x) = 15x1 + 12x2 + 0x3 + 0x4

Sujeito a x1 + 2x2 − x3 + 0x4 = 3

2x1 − 4x2 + 0x3 + x4 = 5

x1, x2, x3, x4 ≥ 0

As variaveis duais sao 3y1 e 5y2. O Problema Dual fica como:

max f (y) = 3y1 + 5y2

Sujeito a y1 + 2y2 ≤ 15

2y1 − 4y2 ≤ 12

−y1 ≤ 0

y2 ≤ 0

y1, y2 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 construcao para o problema dual.

Propriedade 1. “O dual do dual e o primal.”



max f (x) = 10x1 + 7x2 + 15x3

S. a 5x1 + 4x2 + x3 ≤ 80 (y1)

2x1 + 3x2 + 5x3 ≤ 30 (y2)

x1, x2, x3 ≥ 0

Para a forma dual do problema:

min f (y) = 80y1 + 30y2

S. a 5y1 + 2y2 ≥ 10 (x1)

4y1 + 3y2 ≥ 7 (x2)

y1 + 5y2 ≥ 15 (x3)

y1, y2 ≥ 0

Do dual para o primal (ou o processo dual se considerarmos o sistema anterior como um primal):

max f (x) = 10x1 + 7x2 + 15x3

S. a 5x1 + 4x2 + x3 ≤ 80 (y1)

2x1 + 3x2 + 5x3 ≤ 30 (y2)

x1, x2, x3 ≥ 0

Propriedade 2. “Se a restricao m do primal e uma igualdade (=), entao a variavel ym do dual e sem restricao de

sinal.”

max f (x) = 5x1 + 2x2

S. a 5x1 ≤ 3 (y1)

x2 = 4 (y2)

x1 + 2x2 ≤ 9 (y3)

x1, x2 ≥ 0

Para a forma padrao:

max f (x) = 5x1 + 2x2

S. a 5x1 ≤ 3 (y1)

− x2 ≤ −4 (y2)

x1 + 2x2 ≤ 9 (y3)

x1, x2 ≥ 0

Para o dual:

max f (y) = 3y1 + 4(y−2 − y+2 ) + 9y3

S. a y1 + y3 ≥ 5

(y−2 − y+2 ) + 2y3 ≥ 2

y1, y−2 , y+2 , y3 ≥ 0



Propriedade 3. “Se a restricao m do primal e maior que ou igual (≥), entao a variavel ym do dual e nao positiva.”

max f (x) = 5x1 + 2x2

S. a x1 ≤ 3

x2 ≥ 4

x1 + 2x2 ≤ 9

x1, x2 ≥ 0

Colocando todas as restricoes como menor igual (≤):

max f (x) = 5x1 + 2x2

S. a x1 ≤ 3 (y1)

−x2 ≤ −4 (y2)

x1 + 2x2 ≤ 9 (y3)

x1, x2 ≥ 0

Construindo o dual:min f (y) = 3y1 − 4y2 + 9y3

S. a y1 + y3 ≥ 5

− y2 + 2y3 ≥ 2

y1, y2, y3 ≥ 0

Utilizando uma variavel substituta y ′2 = −y2, temos:

min f (y) = 3y1 − 4y2 + 9y3

S. a y1 + y3 ≥ 5

y ′2 + 2y3 ≥ 2

y1, y3 ≥ 0

y ′2 ≤ 0

Propriedade 4. “Se a variavel xj do primal e sem restricao de sinal, entao a restricao j do dual e uma igualdade

(=).”

Propriedade 5. “Se a variavel xj do primal e nao positiva, entao a restricao j do dual e maior ou igual (≥).”

Sintese das Propriedades

A conclusao geral com base nos exemplos e nas propriedades e que as variaveis e restricoes nos problemas

primal e dual sao definidas pelas regras na tabela 4.3.

4.2.2 Teoremas Fundamentais da Dualidade

Ate agora discutimos os conceitos basicos da dualidade e caracterizamos propriedades importantes para a

construcao do par primal-dual. Para completar a importancia da dualidade na Programacao Linear, faltam os

teoremas fundamentais. A presente secao traz enunciados os teoremas e exemplos de sua aplicabilidade.



Primal (max) −→ Dual (min)

k-esima restricao e (≤) k-esima variavel dual e positiva yk ≥ 0

k-esima restricao e (=) k-esima variavel dual irrestrita de sinal

k-esima restricao e (≥) k-esima variavel dual yk ≤ 0

p-esima variavel primal xp ≥ 0 p-esima restricao e (≥)

p-esima variavel primal irrestrita de sinal p-esima restricao e (=)

p-esima variavel primal xp ≤ 0 p-esima restricao e (≤)

Dual (max) ←− Primal (min)

Tabela 4.3: Regras para construir o problema dual.

Teorema da Folga Complementar

Seja xj (j = 1 : n) uma solucao otima para o problema primal de PL e yj (j = 1 : m) uma solucao otima do

problema dual. Entao, o seguinte e verdade:

• Se a k-esima restricao de um dos problemas tem folga nao-nula, entao a k-esima variavel do outro problema

e zero;

• Se a k-esima variavel de uma solucao otima de um dos problemas e positiva, a k-esima restricao do outro e

satisfeita com variavel 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 funcao objetivo, e seja y um ponto qualquer factıvel para o problema dual, com valor correspondente

fd(y) para a funcao objetivo. Entao, para o caso da maximizacao 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 materias-

primas e o seu mınimo seria o valor que tornaria sua venda tao atrativa quanto a sua transformacao. Cabe relembrar

que, nessa interpretacao, os custos administrativos e de transformacao fısica sao ignorados.

Teorema do Criterio de Otimalidade

Seja um par primal-dual e seja x a solucao otima para o problema primal, com valor correspondente fp(x) para

a funcao objetivo, e seja y a solucao otima para o problema dual, com valor correspondente fd(y) para a funcao

objetivo. Entao, o teorema do criterio de otimalidade estabelece que:

fp(x) = fd(y)

Corolarios dos Teoremas

Abaixo temos alguns corolarios pertinentes aos Teoremas.

1. Se o primal e ilimitado (fp(x) =⇒ +∞), o dual nao tem solucao viavel;



2. Inversamente, se o dual nao tem solucao viavel, entao o primal e ilimitado;

3. Se o dual e ilimitado (fd(y) =⇒ −∞), o primal nao tem solucao viavel;

4. Inversamente, se o primal nao tem solucao viavel, entao o dual e ilimitado;

Teorema Principal da Dualidade

Seja um par primal-dual (P) e (D) tal que ambos tenham solucoes factıveis. Entao, ambos tem solucoes otimas,

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 solucoes Primal e Dual.

XXXXXXXXXXDual

PrimalTem solucao Factıvel Nao Tem Solucao Factıvel

Tem Solucao Factıvel max fp = min fd max fp =∞Nao Tem Solucao Factıvel min fd = −∞ Pode ocorrer

Tabela 4.4: Relacoes entre as solucoes primal e dual.

4.3 Metodo Dual SimplexO Metodo Dual Simplex e aplicado em situacoes em que a solucao inicial do primal e infactıvel, porem os

elementos da linha da funcao objetivo sao todos nao negativos, indicando otimalidade. O metodo procura alcancar

a factibilidade primal tornando as variaveis xj nao negativas, mas preservando a factibilidade dual (mantendo a

linha objetivo nao negativa).

4.3.1 Resumo do Metodo

Suponha que o quadro do metodo apresente as seguintes caracterısticas:

• Todos os elementos da linha objetivo sao nao negativos, ou seja, cj ≥ 0, para j = 1 : m. Esta condicao e

denominada otimalidade primal ou solucao dual factıvel;

• A coluna b apresenta pelo menos um elemento negativo, isto e, a condicao de nao negatividade das variaveis

nao e atendida. Diz-se que a solucao primal e infactıvel.

O Metodo Dual Simplex e aplicado seguindo os passos:

1. Selecao da variavel a deixar a base: escolha uma das variaveis negativas, de preferencia a mais negativa.

Seja br = minbi para bi < 0

Assim, a variavel basica correspondente a linha r sai da base e a linha r e a linha do pivo.

2. Selecao da variavel que entra na base: introduzir na base aquela variavel cujo coeficiente na linha objetivo

atingir zero mais rapidamente, quando um multiplo da linha r for somado a linha objetivo.

Podem ocorrer dois fatos:



(a) A avaliacao da variavel a entrar na base se restringe as variaveis nao basicas que tem um coeficiente

negativo na linha r . A aplicacao da logica anterior conduz a regra dos coeficientes

ckar j

= maxj

c jar j

para ar j < 0

Assim, a variavel 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 nao contem elementos negativos, entao o problema

nao tem solucao factıvel. Devemos parar entao com a tentativa de resolucao.

3. Achar uma nova solucao basica em que a variavel xk se torna basica. Isto equivale a efetuar um pivotea-

mento simplex em torno do elemento ark . Va para o passo 4.

4. Teste da Factibilidade Primal: se todos os bi , i = 1 : m forem nao negativos a solucao obtida e otima,

entao podemos parar; caso contrario, voltar ao passo 1.

Problemas de Minimizacao

Ha duas formas de tratar problemas deste tipo. Sao elas:

1. Consiste na conversao do problema de minimizacao em um problema de maximizacao.

2. Consiste em inverter o criterio de escolha da variavel a entrar na base, para o seguinte

csars

= minj

c jar j

para ar j > 0

Assim, a variavel xs entra na base.

Observe o exemplo a seguir.

Exemplo 24. Dado o problema linear

max f (x) = −x1 + x2 − x3

S. a x1 ≤ 9

x1 + x2 + x3 ≤ 2

x1, x2, x3 ≥ 0

1. Resolvendo este problema pelo Metodo Simplex (Primal).

Incluindo as variaveis de excesso.

max f (x) = −x1 + x2 − x3 + 0x4 + 0x5

S. a x1 + x4 = 9

x1 + x2 + x3 + x5 = 2

x1, x2, x3, x4, x5 ≥ 0

Apos colocar o problema na forma padrao escrevemos o quadro Simplex (Tabela 4.5).

Pela checagem das variaveis 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).



Base f(x) x1 x2 x3 x4 x5 b Linha

Max 1 1 -1 1 0 0 0 (0)

x4 0 1 0 0 1 0 9 (1)

x5 0 1 1 1 0 1 2 (2)

Tabela 4.5: Primeiro quadro com o problema primal.

Base f(x) x1 x2 x3 x4 x5 b Linha

Max 1 2 0 2 0 1 2 (0)

x4 0 1 0 0 1 0 9 (1)

x2 0 1 1 1 0 1 2 (2)

Tabela 4.6: Segundo quadro com o problema primal.

Chegamos no valor maximo de f (x) uma vez que nenhuma outra variavel e propicia ao aumento de f (x) (os

coeficientes das variaveis x1 e x3 sao positivos).

Entao, f (x) = 2 e x = (0, 2, 0, 9, 0).

2. Construindo e resolvendo o Dual.

max f (x) = −x1 + x2 − x3

S. a x1 ≤ 9 (y1)

x1 + x2 + x3 ≤ 2 (y2)

x1, x2, x3, ≥ 0

Na forma dual:

min f (y) = 9y1 + 2y2

S.a y1 + y2 ≥ −1

y2 ≥ 1

y2 ≥ −1

y1, y2 ≥ 0

Apos colocar na forma padrao temos o quadro Dual Simplex (a coluna b foi renomeada para identificar o

vetor b dual, assim bd) – Tabela 4.7.

Base f(y) y1 y2 y3 y4 y5 bd Linha

Min 1 -9 -2 0 0 0 0 (0)

y3 0 -1 -1 1 0 0 1 (1)

y4 0 0 -1 0 1 0 -1 (2)

y5 0 0 -1 0 0 1 1 (3)

Tabela 4.7: Primeiro quadro com o problema dual.

Como o caso e de minimizacao, buscaremos a variavel mais positiva (para que o valor de f (y) tenha de ser

o mais negativo possıvel), sendo que y2 entra na base. A variavel que sai da base e y4 pois e a unica na qual

podemos aplicar o teste do coeficiente. Apos as operacoes elementares, temos a Tabela 4.8.



Base f(y) y1 y2 y3 y4 y5 bd Linha

Min 1 -9 0 0 -2 0 2 (0)

y3 0 -1 0 1 -1 0 2 (1)

y2 0 0 1 0 -1 0 1 (2)

y5 0 0 0 0 -1 0 2 (3)

Tabela 4.8: Primeiro quadro com o problema dual.

Aparentemente y4 poderia entrar na base, contudo os elementos de sua coluna sao todos negativos (o mesmo

ocorre com y1). Neste caso, paramos os passos e chegamos na solucao f (y) = 2 e y = (0, 1, 2, 0, 2).

3. Por fim verificarmos a relacao entre as solucoes encontradas.

As solucoes encontradas sao iguais, logo max f (x) = min f (y). Isso ocorre pois ambos os problemas (primal

e dual) sao factıveis.

4.4 Exercıcios Propostos1. Suponha o problema a seguir:

max f (x) = 3x1 − 2x2

S. a 4x1 + 2x2 ≤ 10

2x1 − 3x2 ≤ 7

x1 ≥ 0

x2 ≤ 0

Determine o Dual do problema.


max f (x) = 2x1 + 3x2

S. a −2x1 + 3x2 ≤ 6

x1 + 2x2 ≥ 8

x1 + x2 ≤ 6

x1, x2 ≥ 0

(a) Escreva o problema Dual.

(b) Sabendo que a solucao primal e: x1 = 2.4 e x2 = 3.6, use o Teorema da Folga Complementar para

determinar a sua solucao dual.

3. De o Dual do problema a seguir numa tal forma que as variaveis Duais sejam nao-negativas:

max f (x) = 6x1 + 4x2 + x3 + 7x4 + 5x5

S. a 3x1 + 7x2 − 8x3 + 5x4 + x5 = 2

2x1 + x2 + 3x3 + 2x4 + 9x5 = 6

x1, x2, x3, x4 ≥ 0

x5 ∈ R



4. Seja o seguinte problema primal:

max f (x) = 3x1 + x2 + 5x3

S. a 6x1 + 3x2 − 5x3 ≤ 45 (mao-de-obra)

3x1 + 4x2 + 5x3 ≤ 30 (materia-prima)

x1, x2, x3 ≥ 0

(a) Resolva o problema Primal pelo Metodo Simplex.

(b) Escreva o problema Dual e identifique sua solucao otima.

(c) Suponha que 15 unidades adicionais de materia-prima podem ser obtidas ao custo de $10. E rentavel

aceitar essa proposta?

(d) Ache a solucao otima caso a quantidade disponıvel de materia-prima passse para 60 unidades.

(e) Para que valores de c1 a solucao permanece otima?

5. Resolver o problema Primal abaixo pelo Metodo Dual-Simplex, analisando e discutindo em seguida a solucao

encontrada.

min f (x) = x1 + x2 + x3

S. a x1 − 2x2 + x3 ≤ 2

x1 + x2 + x3 ≤ 1

x1, x2, x3 ≥ 0

6. Escreva o problema Dual para cada um dos seguintes problemas Primais:

(a)

max f (x) = −5x1 + 2x2

S. a −x1 + x2 ≤ −2

2x1 + 3x2 ≤ 5

x1, x2 ≥ 0

(b)

min f (x) = 6x1 + 3x2

S. a 6x1 − 3x2 + x3 ≥ 2

3x1 + 4x2 + x3 ≥ 5

x1, x2, x3 ≥ 0

(c)

max f (x) = x1 + x2

S. a 2x1 + x2 = 5

3x1 − x2 = 6

x1, x2 ∈ R

7. A BagCo produz jaquetas e bolsas de couro. Uma jaqueta requer 8m2 e uma bolsa, apenas 2m2. Os requisitos

de mao-de-obra para os dois produtos sao 12 e 5 horas, respectivamente. As disponibilidades semanais atuais

de couro e mao-de-obra estao limitadas a 1200m2 e 1850 horas. A empresa vende jaquetas e bolsas a $350 e

$120, respectivamente. O objetivo e determinar a programacao de producao que maximize a receita lıquida.

A BagCo esta considerando uma expansao de producao. Qual e o preco maximo de compra que a empresa

deve pagar pelo couro adicional e para a mao-de-obra?


CAPITULO 5

Metodos de Pontos Interiores

5.1 IntroducaoA ideia dos Metodos de Pontos Interiores foi desenvolvida por Karmarkar, em 1984, quando ele publicou um

artigo que buscava a solucao de um problema de Programacao Linear (PL) atraves do interior da regiao viavel.

Deste entao, houve muitas modificacoes no metodo, permanecendo a ideia basica: a de caminhar pelo interior da

regiao viavel .

Atualmente existem tres classes de metodos: os que consideram apenas problemas no formato primal, outros

apenas no formato dual e, finalmente metodos que extraem informacoes dos dois problemas, conhecidos como

Metodos Primais-Duais. Esta ultima classe sera abordada aqui, com base em [12].

5.2 Notacao

A maior parte do desenvolvimento teorico de algoritmos para (PL) e feita para problemas com restricoes do

tipo igualdade (problemas na forma padrao, como desenvolvido no Capıtulo 3). No Capıtulo 4 o denominamos

como Problema Primal (PP). O PL tambem pode ser formulado com restricoes de desigualdades, que se chama

Problema Dual (PD). Os dois problemas (PP e PD) sao relacionados por expressoes simples, que permitem traduzir

metodos desenvolvidos em um formato para o outro (vide Capıtulo 4).

Considere o problema no formato primal (ou padrao):

(PP)

min cT x

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 solucoes viaveis 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 solucoes interiores de (PP). Suporemos P 0 6= ∅.Todo ponto satisfazendo x ∈ P 0 sera denominado de ponto interior.

Capıtulo 5. Metodos de Pontos Interiores PL

Associado ao (PP) temos o (PD), que consiste basicamente dos mesmos dados organizados de maneira dife-

rente:

(PD)

max 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 padrao pela adicao da variavel z

(variavel de folga).

O conjunto de solucoes viaveis 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 relacao entre os problemas (PP) e (PD), ou seja, o conjunto de solucoes

primais nos fornece informacao sobre o conjunto de solucoes duais e vice-versa. Por exemplo, dados quaisquer

vetores de solucoes primais x para (PP) e (y, z) para (PD), temos:

bT y ≥ cT x.

A funcao objetivo dual fornece um limite inferior para a funcao objetivo primal, e a funcao primal fornece um

limite superior para o dual. As duas funcoes objetivo coincidem no valor, isto e: bT y∗ = cT x∗ se, e somente se x∗

resolve (PP) e (y∗, z∗) resolve (PD).

Considere as condicoes de otimalidade, para esta classe de metodos, conhecidas como Condicoes de Karush-

Kuhn-Tucker ou (KKT), estabelecida pelo Teorema 2.

Teorema 2. Considere os problemas (PP) e (PD) acima. O vetor x∗ e uma solucao otima do problema (PP) e

(y∗, z∗) e uma solucao otima do problema (PD) se, e somente se:

AT y + z = c z ≥ 0 (viabilidade dual)

Ax = b x ≥ 0 (viabilidade primal)

XZe = 0 (folgas complementares)

(5.1)

onde X = diag(x1, x2, . . . , xn), Z = diag(z1, z2, . . . , zn) e e = (1, 1, . . . , 1)T .

Do Teorema 2, temos que o vetor (x∗, y∗, z∗) e solucao do sistema de equacoes (5.1) se, e somente se x∗ e

solucao do (PP) e (y∗, z∗) e solucao do (PD). O vetor (x∗, y∗, z∗) e chamado de solucao primal-dual.

O conjunto de solucoes viaveis primais-duais e seu interior podem ser definidos como:

Ω =

(x, y, z) /Ax = b, AT y + z = c, (x, z) ≥ 0

Ω0 =

(x, y, z) /Ax = b, AT y + z = c, (x, z) > 0

respectivamente. Assumiremos Ω0 6= ∅.



5.3 Metodo Primal-DualOs metodos primais-duais estao estritamente relacionados ao consagrado Metodo de Newton para solucoes de

sistemas de equacoes, lineares ou nao. Uma iteracao primal-dual e, em ultima instancia, uma iteracao adaptada

do metodo de Newton, proveniente das condicoes de KKT (5.1).

Podemos escrever as condicoes de KKT na forma de uma equacao, em conjunto com uma restricao. A equacao

provem das proprias condicoes de otimalidade e a restricao continua sendo a de nao negatividade. Obtemos entao:

F (x, y, z) =

Ax− b

AT y + z− c

XZe

= 0, (x, y) ≥ 0 (5.2)

com F : R2n+m → R2n+m.

A equacao F (x, y, z) = 0 podemos aplicar o metodo de Newton para encontrar solucoes viaveis (x∗, y∗, z∗),

porem respeitando o limite (x, y) > 0, o que garante estarmos no interior da regiao viavel (Ω0).

O metodo de Newton consiste em gerar uma sequencia de pontos xk que convirja para a solucao de uma

dada equacao G(x) = 0, onde G : Rn → Rn, G ∈ C(Rn) e x ∈ Rn. O metodo e baseado em uma expansao em

primeira ordem (serie de Taylor) da funcao considerada:

G(x) ≈ G(xk) + J(xk)(x− xk)

com J sendo o Jacobiano de G. Desta forma, se xk+1 e solucao da expansao acima, entao vale J(xk)sk = −G(xk),

com xk+1 = xk + sk . Portanto, o Metodo de Newton consiste em gerar os passos sk e usa-los para atualizar o

ponto xk .

Uma iteracao completa do metodo de Newton pode ser escrita como

xk+1 = xk − J−1(xk)G(xk).

Na aplicacao do Metodo de Newton surgem duas questoes: (i) a necessidade de uma solucao inicial e, (ii) a

necessidade de exercermos algum controle sobre os passos, ja que ele pode convergir para solucoes F (x, y, z) = 0

mas que nao satisfacam (x, y) > 0 (ditas solucoes espurias).

O item (i) sera abordado na Secao 5.5.1; por isso, consideraremos aqui que ja temos uma solucao inicial viavel.

O item (ii) e o responsavel 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 direcao, mantendo a viabilidade

da solucao.

Escrevendo uma iteracao de Newton para a equacao F (x, y, z) = 0, obtemos: xk+1

yk+1

zk+1

=

xk + ∆xk

yk + ∆yk

zk + ∆zk

=

xk

yk

zk

− J−1(x, y, z)F (x, y, z) (5.3)

ou ainda, ∆xk

∆yk

∆zk

= J−1(x, y, z)F (x, y, z)



pre-multiplicando por J(x, y, z):

J(x, y, z) =

∆xk

∆yk

∆zk

= −F (x, y, z)

sendo:

J(x, y, z) =

A 0 0

0 AT I

Z 0 X

.Portanto, para obter uma iteracao de Newton para a equacao F (x, y, z) = 0, rescrevemos J(xk)sk = −G(xk)

como: A 0 0

0 AT I

Z 0 X

∆xk

∆yk

∆zk

= −

Axk − b

AT yk + zk − c

XkZke

Se o ponto corrente (xk , yk , zk) e estritamente viavel (Axk = b, AT yk + zk = c e (x, z) > 0), entao o sistema

acima toma a forma: A 0 0

0 AT I

Z 0 X

∆xk

∆yk

∆zk

=

0

0

−XkZke

Atualizando as variaveis (x, y, z) temos:

(xk+1, yk+1, zk+1) = (xk , yk , zk) + αk(∆xk ,∆yk ,∆zk).

Os metodos primais-duais sao variacoes do metodo de Newton obtidos a partir de modificacoes na maneira

de calcular (∆xk ,∆yk ,∆zk), a direcao de busca, e αk , o parametro que controla o tamanho do passo em cada

iteracao. O valor de αk pode atuar no algoritmo de dois modos:

• Mantendo o novo ponto no interior da regiao viavel e.

• Cuidando para que (x, z) permaneca “longe” das fronteiras do quadrante nao negativo, (x, z) > 0. Direcoes

calculadas a partir de pontos proximos a este quadrante tendem a ser distorcidas levando a pouco, se algum,

progresso.

A ideia da trajetoria central nos auxılia nas questoes acima.

5.3.1 A Trajetoria Central

Uma das maneiras de manter o algoritmo do tipo primal-dual no interior da regiao viavel e fazer com que a

trajetoria gerada pelo metodo de Newton esteja em alguma vizinhanca da denominada trajetoria central.

Matematicamente, a trajetoria central C e um caminho de pontos estritamente viaveis, (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 (folgas complementares)

(x, z) > 0

(5.4)

A trajetoria central e um recurso interessante pois quando τ → 0, a equacao (5.4)→ equacao (5.1). Entao, se



C converge para algum ponto, deve ser para uma solucao primal-dual do (PP). Desse modo, C atua como um guia,

evitando solucoes espurias pois mantem os produtos xizi estritamente positivos, mas tendendo a zero a mesma

velocidade.

Mais ainda: a maioria dos algoritmos primais-duais tomam direcoes C com τ > 0, ou seja, direcoes dentro do

quadrante positivo definido por (x, z) > 0. Essa escolha de direcoes permite que passos maiores sejam dados em

relacao as direcoes de Newton puras, sem violar a condicao de positividade, que chamaremos de direcao de busca.

Para descrever a direcao de busca modificada, introduziremos um parametro de centralizacao σ ∈ [0, 1] e uma

metrica1 dual µ definida por:

µ =1

n

n∑i=1

xizi =xT z

n, (5.5)

ou seja, uma media entre os produtos xizi .

As equacoes de passo tomam agora a forma: A 0 0

0 AT I

Z 0 X

∆xk

∆yk

∆zk

=

0

0

−XkZke + σµe

(5.6)

Atraves do controle de σ e µ podemos gerar uma vizinhanca da trajetoria central em que os novos passos

calculados de acordo com a equacao (5.6) tenham melhor progresso do que os passos de Newton puros.

Considere um conjunto estritamente viavel H0:

H0 =

(x, z) / (x, y, z) ∈ Ω0 para algum y ∈ Rm

e uma funcao de barreira definida por:

fτ (x, z) =1

τxT z−

n∑i=1

log(xizi).

Teorema 3. Suponha Ω0 6= ∅ e seja τ um numero positivo. Entao fτ tem um unico mınimo local em H0, que

satisfaz as condicoes de trajetoria central (5.4).

Retornando as equacoes de (5.6), podemos escreve-la na forma de equacoes, como segue:

AT∆y + ∆z = 0

A∆x = 0

Z∆x + X∆z = −XZe + σµe

(5.7)

Isolando ∆z da ultima equacao de (5.7), temos:

∆Z = −Ze + σµX−1e− X−1Z∆x (5.8)

Escrevendo (5.8) na primeira equacao de (5.7), temos:

AT∆y − X−1Z∆x = Ze− σµX−1e. (5.9)

1metrica: medida.



Escrevendo a segunda equacao de (5.7) e a equacao (5.9) na forma matricial, com ∆z isolado (equacao (5.8)):[A 0

−X−1Z AT

] [∆x

∆y

]=

[0

−σµX−1e + Ze

]. (5.10)

Como X e Z sao matrizes diagonais e nao singulares, podemos isolar ∆x de (5.10), obtendo assim, um novo

sistema equivalente:

AZ−1XAT∆y = A(Xe− σµZ−1e

)∆z = −AT∆y

∆x = −Xe + σµZ−1e− Z−1X∆z

(5.11)

O passo mais difıcil e calcular a primeira equacao de (5.11), mas o primeiro termo envolve uma matriz definida

positiva(AD2AT , onde D = Z−1/2X1/2

), podendo entao ser aplicada a Fatoracao de Cholesky 2 para resolver o

sistema.

5.3.2 Estrutura Primal-Dual

Atraves dos conceitos apresentados ate aqui, podemos definir uma estrutura geral para os algoritmos primais-

duais. O metodo abordado na proxima secao (Secao 5.4) e um caso especial desta estrutura.

Estrutura Primal-Dual

Fase I

Passo 1: (Inicializacao) Faca k = 0 e encontre (x0, y0, z0) ∈ Ω0 uma solucao inicial.

Fase II

Passo 2: (Otimalidade) Se o ponto (xk , yk , zk) satisfaz os criterios de otimalidade, pare.

Passo 3: (Calculo da direcao de busca) Seja σk ∈ [0, 1] e µk =(xk)T zk

n. Calcule:

AZ−1k XkAT∆yk = A

(Xke− σkµkZ−1

k e)

∆zk = −AT∆yk

∆xk = −Xke + σkµkZ−1k e− Z−1

k Xk∆zk(5.12)

Passo 4: (Atualizacao) (xk+1, yk+1, zk+1

)=(xk , yk , zk

)+ αk

(∆xk ,∆yk ,∆zk

)Faca k = k + 1 e volte ao passo 2.

Na Fase I do algoritmo calculamos uma solucao inicial para o problema e na Fase II, calculamos a direcao de

busca e atualizamos a solucao ate obtermos a solucao otima.

5.4 Metodo de Reducao de Potencial (RP)O Metodo de Reducao de Potencial e uma variante dos algoritmos que usam passos de Newton e parte de uma

classe maior de metodos, denominados Metodos de Penalizacao. De um modo geral, um metodo de penalizacao

2Metodo especıfico para matrizes do tipo definida positiva.



modifica a funcao objetivo acrescentando um termo que (i) aumente muito seu valor quando determinada condicao

de controle e violada e (ii) tende a zero quando nos aproximamos da solucao otima. Este termo e conhecido

usualmente de funcao de barreira ou funcao potencial.

Karmarkar usou uma funcao potencial para a Programacao Linear sob a forma:

ρ log(cT x− L

)−

n∑i=1

log xi

onde ρ = n+ 1 e L e um limite inferior para o valor da funcao objetivo, provando sua convergencia e resultados de

complexidade por mostrar que sua funcao diminui, pelo menos um valor constante em cada iteracao. Por exemplo,

para o problema:

min x1 + x2

S. a x1 + x3 = 1

x2 + x4 = 1

x1, x2, x3, x4 ≥ 0

cujo o tipo e um quadrado de lado 1 no plano (x1, x2), a funcao de Karmarkar torna-se: Φ(x1, x2) = 3 log(x1 +x2)−log x1 − log x2. Observe a Figura 5.1 como a funcao decresce rapidamente na imediacao do otimo, x∗ = (0, 0).

0 0.1 0.2 0.3 0.4 0.5 0 0.1

0.2 0.3

0.4 0.5

-1.5-1

-0.5 0

0.5 1

1.5

0 0.1 0.2 0.3 0.4 0.5 0

0.1

0.2

0.3

0.4

0.5

-1.5

-1

-0.5

0

0.5

1

1.5

Figura 5.1: Grafico e curvas de nıvel de Φ(x1, x2).

Depois da publicacao do algoritmo de Karmarkar, houve muitos avancos nos algoritmos que usam esta funcao;

porem a maioria das novas tecnicas ainda baseava-se nos valores das variaveis primais. A partir de 1987 os

algoritmos passaram a utilizar de forma mais balanceada variaveis primais-duais. Nessa linha temos a funcao de

potencial primal-dual de Tanabe-Todd-Ye, definida por:

Φρ(x, y) = ρ log xT z−n∑i=1

log xizi (5.13)

para um parametro ρ > n.

Os algoritmos baseados em Φρ usam a funcao potencial apenas para monitorar o “progresso”e provar a con-

vergencia. Este progresso refere-se ao potencial atribuıdo a cada ponto de Ω0 por Φρ e que diminui a medida

que nos aproximamos da solucao. Como todos os algoritmos baseados na estrutura primal-dual, o algoritmo de

reducao de potencial obtem sua direcao de busca pela execucao de (5.12) para algum σk ∈ (0, 1). O tamanho do

passo αk e escolhido para minimizar Φρ ao longo da direcao de busca.



Voltando a equacao (5.13), faremos algumas modificacoes algebricas 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∑i=1

log xizi + n log xT z− n log n + n log n.

Aplicando as propriedades de logaritmos:

Φρ(x, y) = ρ log xT z− n log xT z−[

logx1z1

xT zn + log

x2z2

xT zn + . . .+ log

xNznxT z

n]

+ n log n,

⇒ Φρ(x, y) = (ρ− n) log xT z−n∑i=1

logxizixT zn

+ n log n

Ou seja, podemos rescrever a funcao (5.13) da seguinte maneira:

Φρ(x, y) = (ρ− n) log xT z−n∑i=1

logxizixT zn

+ n log n. (5.14)

De (5.14) percebemos que Φρ faz o balanceamento entre dualidade e centralidade. Se xT z e pequeno, favorecemos

a dualidade e se nenhum xizi e muito menor do que a media µ =xT z

n, favorecemos a centralidade.

Duas propriedades importantes podem ser entao observadas:

1. Φρ → +∞ se xizi → 0, para algum i , mas µ =xT z

nnao tende a zero;

2. Φρ → −∞ se, e somente se (x, y, z)→ Ω0.

De acordo com as condicoes de KKT, so estaremos no otimo se xT z = 0. Portanto, e desejavel que o metodo

aproveita a funcao de barreira de modo a forcar µ→ 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 entao como uma barreira.

Por outro lado, o termo

(−

n∑i=1

logxizixT zn

+ n log n

)tem um limite inferior. Portanto, Φρ → −∞ se, e somente

se (ρ− n) log xT z→ −∞, o que implica que xT z → 0. Entao, o metodo de Reducao de Potencial gera iteracoes

no sentido de levar µ→ 0, usando informacoes fornecidas por estas duas propriedades.

Algoritmo de Reducao de Potencial Primal-Dual

Este algoritmo toma σk =n

ρ, onde ρ < n e o parametro de (5.14). O passo αk e escolhido para minimizar

Φρ(·) ao longo da direcao de busca e mantendo a viabilidade.

Algoritmo RP

Fase I

Passo 1: (Inicializacao) Faca k = 0, ρ > n e encontre (x0, y0, z0) ∈ Ω0.

Fase II:

Passo 2: (Otimalidade) Se o ponto (xk , yk , zk) satisfaz os criterios de otimalidade, pare.



Passo 3: (Calculo da direcao de busca) Seja σk =n

ρe resolva (5.12) para obter (∆xk ,∆yk ,∆zk).

Passo 4: (Calculo do tamanho do passo) Calcule:

αmax = sup α ∈ [0, 1] / (x, z) + α(∆x,∆z) ≥ 0 ,

e escolha αk de αk = argminα∈(0,αmax ) Φρ(xk + α∆xk , zk + α∆zk).

Passo 5: (Atualizacao)

(xk+1, yk+1, zk+1) = (xk , yk , zk) + αk(∆xk ,∆yk ,∆zk).

Faca k = k + 1 e volte ao passo 2.

5.5 Implementacao de Algoritmos de Pontos InterioresNa secao 5.3.2 definimos uma estrutura geral para o algoritmo Primal-Dual e na secao 5.4 definimos algumas

variantes desta estrutra. Porem, durante estas secoes, tomamos como conhecida uma solucao inicial e omitimos

o criterio de parada do algoritmo. Trataremos nesta secao destes topicos, bem como de uma estrutura mais

“completa” para o algoritmo Primal-Dual.

5.5.1 Solucao Inicial

Ate aqui, discutimos sobre algoritmos de Pontos Interiores, supondo conhecida uma solucao inicial. A dificuldade

em obter uma solucao inicial e equivalente a de aplicar o algoritmo ate a solucao otima; por isso, muitos algoritmos

teoricos assumem a existencia de um ponto inicial e o usam para inicializar o algoritmo. O processo de encontrar

uma solucao inicial e conhecida como “Fase I” do algoritmo e o processo de resolver o algoritmo ate a otimalidade,

de “Fase II”. Entao, nesta secao, abordaremos a Fase I do algoritmo Primal-Dual.

Seja (x0, y0, z0) com (x0, z0) > 0 uma solucao primal-dual inicial inviavel. Para obter uma solucao viavel

considere os seguintes problemas primal e dual artificiais:

(PPA)

min cT x +MP xn+1

S. a Ax + (b− Ax0)xn+1 = b

(AT y0 + z0 − c)T x + xn+2 = MD

(x, xn+1, xn+2) ≥ 0

e

(PDA)

max bT y +MDym+1

S. a AT y + (AT y0 + z0 − c)ym+1 + z = c

(b− Ax0)T y + zn+1 = MP

ym+1 + zn+2 = 0

(z, zn+1, zn+2) ≥ 0

onde xn+1 e ym+1 sao variaveis artificiais primal e dual, respectivamente, com seus coeficientes de custo artificiais

MP e MD. O coeficiente dessas variaveis na primeira restricao de (PPA) e na primeira de (PDA) correspondem

a uma medida de inviabilidade da apriximacao inicial. A variavel xn+2 corresponde a variavel dual artificial ym+1 e

zn+1, zn+2 sao variaveis duais de folga correspondentes a xn+1 e xn+2. Essas variaveis sao necessarias para manter

a relacao de dualidade entre dois problemas.

Fixando-se MP e MD com valores que dominam a funcao objetivo primal e dual, garantimos que a direcao de

busca e dominada pela direcao viavel. Se um ponto viavel existe, entao durante o processo iterativo as variaveis



artificiais gradualmente convergem para zero.

Podemos escolher MP e MD de maneira que:

MP > (b− Ax0)T y0, (5.15)

e

MD > (AT y + z0 − c)T x0, (5.16)

entao (x0, x0n+1, x

0n+2) e (y0, y0

m+1, z0, z0

n+1, z0n+2) sao solucoes viaveis para os problemas artificiais (PPA) e (PDA),

respectivamente.

Os valores de x0n+1, x

0n+2, y

0m+1, z

0n+1 e z0

n+2 podem ser obtidos como segue.

Seja Ax + (b− Ax0)xn+1 = b e tomemos x = x0. Entao:

Ax0 + (b− Ax0)x0n+1 = b

Ax0(1− x0n+1) = b(1− x0

n+1)(5.17)

Mas a segunda equacao de (5.17) so sera verdadeira quando:

1− x0n+1 = 0

x0n+1 = 1

(5.18)

Procedendo analogamente para AT y + (AT y0 + z0 − c)ym+1 + z = c, obtemos:

ym+1 = −1. (5.19)

Das demais restricoes obtemos:

x0n+2 = MD − (AT y0 + z0 − c)T x0,

z0n+1 = MP − (b− Ax0)T y0,

z0n+2 = 1.

(5.20)

A partir daqui, buscamos as solucoes 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∗) solucoes otimas dos problemas originais (PP) e (PD), respectivamente. Suponha

que:

MP > (b− Ax0)T y0,

e

MD > (AT y + z0 − c)T x0.

Entao as duas afirmacoes abaixo sao verdadeiras:

1. Uma solucao viavel (x, xn+1, xn+2) de (PPA) e um ponto de mınimo se, e somente se x resolve (PP) e

xn+1 = 0.

2. Uma solucao viavel (y, ym+1, z, zn+1, zn+2) de (PDA) e um ponto de maximo se, e somente se (y, z) resolve

(PD) e ym+1 = 0.

Observe que este e exatamente o metodo do M-Grande, tradicionalmente usado em associacao com o Simplex

e aqui adaptado para os metodos primais-duais.



5.5.2 Criterio de Parada

Ao contrario do metodo Simplex, o algoritmo de Ponto Interior Primal-Dual nunca encontra uma solucao exata

para o problema PL. Por isso, o algoritmo precisa usar um criterio de parada para decidir quando a iteracao corrente

esta proxima o suficiente da solucao otima.

Muitos algoritmos consideram uma boa solucao aproximada a solucao que possui os resıduos primal rb = Ax−b

e dual rc = AT y + z−c e a metrica dual µ suficientemente pequenos. Para esse fim pode-se usar medidas relativas

diminuindo os problemas de escala dos dados. Testes tıpicos para uma solucao (x, y, z) sao:

‖rb‖1 + ‖b‖ =

‖Ax− b‖1 + ‖b‖ ≤ τ1

‖rc‖1 + ‖c‖ =

‖AT y + z− c‖1 + ‖c‖ ≤ τ1

|cT x− bT y|1 + |cT x| ≤ τ1

(5.21)

onde τ1 e a tolerancia. Naturalmente outros criterios podem ser adotados em concordancia com a aplicacao a um

problema especıfico.

5.5.3 Algoritmo Primal-Dual

Como ultimo topico deste capıtulo, daremos uma estrutura mais “completa” do algoritmo primal-dual.

Fase I

Passo 1: (Inicializacao) Faca k = 0 e encontre (x0, y0, z0) ∈ Ω0 uma solucao inicial e defina τ1 ≥ 0 uma tolerancia

suficientemente pequena.

Fase II

Passo 2: (Otimalidade) Se‖rb‖

1 + ‖b‖ =‖Ax− b‖1 + ‖b‖ ≤ τ1

‖rc‖1 + ‖c‖ =

‖AT y + z− c‖1 + ‖c‖ ≤ τ1

|cT x− bT y|1 + |cT x| ≤ τ1

entao pare. A solucao encontrada e otima.

Passo 3: (Calculo da direcao de busca) Seja σk ∈ [0, 1] e µk =(xk)T zk

n. Seja σk ∈ [0, 1]. Calcule:

AZ−1k XkAT∆yk = A

(Xke− σkµkZ−1

k e)

∆zk = −AT∆yk

∆xk = −Xke + σkµkZ−1k e− Z−1

k Xk∆zk

Passo 4: (Atualizacao) (xk+1, yk+1, zk+1

)=(xk , yk , zk

)+ αk

(∆xk ,∆yk ,∆zk

)Faca k = k + 1 e volte ao passo 2.


CAPITULO 6

Programacao Linear Inteira

6.1 Introducao

Como descrito em [2], problemas de Programacao Linear Inteiro (PLI) pertencem a otimizacao discreta ou

combinatoria pois algumas das variaveis fazem parte de um conjunto discreto, tipicamente, um subconjunto dos

numeros inteiros.

Um problema com variaveis inteiras e reais e denominada de Programacao Linear Inteira Mista (PLIM) quando

tem a seguinte forma:

max f (x, y) = cx + dy

S. a Ax + Dy ≤ b

x ∈ Rn+y ∈ Zp+

em que A ∈ Rm×n, D ∈ Rm×p, c ∈ R1×n, d ∈ R1×p e b ∈ Rm×1 representando os parametros do problema. Os

vetores x ∈ Rn×1 e y ∈ Zp×1 as variaveis do problema. Rn+ representa o espaco dos vetores com n componentes

reais e Zp+ o espaco dos vetores com p componentes inteiras nao negativas.

Quando todas as variaveis sao inteiras, tem-se o problema de Programacao Linear Inteira (PLI):

max f (x) = cx

S. a Ax ≤ b

x ∈ Zn+

e se todas as variaveis assumem valores 0 ou 1, tem-se um problema de Programacao 0-1 ou Binaria (PB), escrito

como:max f (x) = cx

S. a Ax ≤ b

x ∈ Bn+

em que Bn+ representa o espaco dos vetores com n componentes binarias.

Os algoritmos de (PLI) sao baseados na exploracao do sucesso computacional da resolucao de problemas de

Programacao Linear (PL), uma vez que os problemas que tratam de solucoes inteiras fazem uma busca dentro da

regiao factıvel. Os algoritmos possuem tres passos como estrategia de resolucao, sendo:

1. Relaxar a regiao de solucoes de PLI eliminando a restricao inteira imposta a estas variaveis e substituindo

qualquer variavel binaria y pela contınua 0 ≤ y ≤ 1. Neste passo, transformamos um problema linear inteiro

Capıtulo 6. Programacao Linear Inteira PL

em um problema linear (PL).

2. Faz-se entao a resolucao do PL relaxado e identifica-se uma solucao otima contınua. A resolucao desta etapa

pode ser atraves dos metodos ja aprendidos anteriormente, como o Metodo Simplex.

3. Comecando do ponto otimo contınuo, adicionam-se restricoes especiais que modifiquem iterativamente a

regiao de solucoes de PL de maneira que, a certa altura, resultara em um ponto extremo otimo que devera

satisfazer os requisitos de integralidade.

Os algoritmos existentes desenvolvidos para PLI, executam a etapa 3 acrescentando restricoes especiais. Sao

dois os metodos mais conhecidos: branch-and-bound (B&B) e planos de corte. Apresentaremos aqui uma in-

troducao ao algoritmo B&B.

6.2 Algoritmo Branch-And-Bound (B&B)Explicaremos neste topico, com o auxılio de um exemplo numerico, os detalhes envolvidos no metodo do B&B

geral.

Exemplo 25. Seja o PLI abaixo:

max f (x) = 5x1 + 4x2

S. a 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 regiao de solucoes do problema de PLI.

Figura 6.1: Regiao de solucoes de PLI (grade de pontos) e de PL1 (hachura).

A solucao do problema (6.1) relaxado, ilustrado pela figura 6.1 (denominado como PL1), e dada pelos vertices

das duas restricoes, ou seja, x1 = 3.75; x2 = 1.25 e f (x) = 23.75.



Como a solucao otima do problema relaxado nao satisfaz a condicao de integralidade, o algoritmo B&B modifica

a regiao de solucoes de modo a identificar a solucao otima do problema de PLI. Primeiramente, selecionamos uma

das variaveis inteiras cujo valor otimo em PL1 seja nao inteiro. Selecionamos a variavel x1 = 3.75, tomando

3 < x1 < 4 da regiao de solucoes de PL1 com nenhum valor inteiro de x1, podendo retira-la da regiao total. Esse

passo faz surgir dois problemas de PL que sao equivalentes ao PL1. A regiao criada e apresentada na figura 6.2,

elaborada como:

Regiao PL2 = Regiao PL1 + (x1 ≤ 3)

Regiao PL3 = Regiao PL1 + (x1 ≥ 4)

Figura 6.2: Regiao de solucoes de PL2 e PL3.

Se usarmos esta logica para eliminar a condicao de integralidade gerando regioes relaxadas impondo restricoes

adequadas (que cercam a condicao de valores inteiros para as variaveis), teremos PLs cujos pontos extremos otimos

satisfacam as restricoes inteiras. Na verdade, resolveremos o PL1 lidando com uma sequencia de PLs contınuos.

As novas restricoes, x1 ≤ 3 e x1 ≥ 4 sao mutuamente exclusivas, de modo que PL2 e PL3 nos “nos” 2 e 3

devem ser tratadas como PLs separadas, como mostra o esquema da figura 6.3.

Essa dicotomizacao da origem ao termo ramificacao no algoritmo B&B, sendo neste caso, x1 denominada de

variavel de ramificacao. Como observado, no esquema (figura 6.3) apresentamos a solucao de cada ramificacao,

entretanto, mostraremos como montar cada um dos PLs.

O PLI otimo se encontra em PL2 ou em PL3. Em consequencia, os dois subproblemas devem ser examinados

e escolhemos arbitrariamente PL2 para ser o primeiro:

max f (x) = 5x1 + 4x2

S. a x1 + x2 ≤ 5

10x1 + 6x2 ≤ 45

x1 ≤ 3

x1, x2 ≥ 0

(6.2)

Resolvendo o problema (6.2), chegamos na resposta da ramificacao 2 do esquema da figura 6.3.



PL1

f (x) = 23.75

1

x1 = 3.75, x2 = 1.25

2

PL2x1 = 3, x2 = 2f (x) = 23

Limite inferior f (x) = 23.33

x1 ≤ 3

3

PL3

x1 = 4, x2 = 0.83

x1 ≥ 4

Figura 6.3: Utilizacao da variavel de ramificacao x1 para criar PL2 e PL3.

Note que a solucao de PL2 apresenta valores inteiros para as variaveis x1 e x2, deste modo dizemos que o

problema e incumbente e que nao precisa ser mais investigado, pois nao pode dar nenhuma solucao melhor para

o PLI com esta ramificacao. Entretanto, nao podemos ainda afirmar que esta solucao e a melhor solucao 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 otimo para a funcao

objetivo, isto e, qualquer subproblema nao examinado que apresente um valor menor que este deve ser descartado

como nao promissor. Ja se ele produzir uma solucao melhor, atualizamos o valor do limite inferior como sendo o

desta nova solucao.

Como f (x) = 23.75 em PL1 e todos os coeficientes da funcao objetivo sao inteiros, e impossıvel, para este

caso, que PL3 produza uma solucao 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 solucao inteira e a segunda por nao ser capaz de melhorar tal solucao). Assim, concluımos que a

solucao otima 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 variavel de ramificacao?

2. Ao selecionar o proximo subproblema a ser examinado, resolvessemos PL3 em vez de PL2?

Se fizermos a alteracao sugerida no item 1 e 2, os calculos resultantes mudarao, como veremos a seguir. A

figura 6.4 mostra todos os subproblemas envolvidos.

A criacao dos subproblemas PL4 e PL5 advem da solucao nao inteira de PL3. Temos entao:

Regiao PL4 = Regiao PL3 + (x2 ≤ 0) = Regiao PL1 + (x1 ≥ 4) + (x2 ≤ 0)

Regiao PL5 = Regiao PL3 + (x2 ≥ 1) = Regiao PL1 + (x1 ≥ 4) + (x2 ≥ 1)

Agora, temos tres subproblemas a serem examinados: PL2, PL4 e PL5. Suponha que optemos por examinar

PL5 em primeiro lugar. O PL5 nao tem nenhuma solucao e, em decorrencia, esta descartado. Em seguida,



2

PL2x1 = 3, x2 = 2f (x) = 23

Limite inferior

4

PL4

x1 = 4.5, x2 = 0

f (x) = 22.5

5

PL5

Sem solucao.

6

PL6

x1 = 4, x2 = 0

f (x) = 20Sem solucao.

7

PL7

PL1

f (x) = 23.75

1

x1 = 3.75, x2 = 1.25

x1 = 4, x2 = 0.83

f (x) = 23.33

3

PL3

x1 ≤ 3

x2 ≥ 1x2 ≤ 0

x1 ≤ 5x1 ≥ 4

x1 ≥ 4

Figura 6.4: Arvore B&B alternativa.

examinamos PL4. A solucao otima e x1 = 4.5; x2 = 0 e f (x) = 22.5. O valor nao inteiro de x1 leva a dois ramos

x1 ≤ 4 e x1 ≥ 5, e a criacao dos subproblemas PL6 e PL7 com base em PL4.

Regiao PL6 = Regiao PL1 + (x1 ≥ 4) + (x2 ≤ 0) + (x1 ≤ 4)

Regiao PL7 = Regiao PL1 + (x1 ≥ 4) + (x2 ≤ 0) + (x1 ≥ 5)

Agora, os subproblemas PL2, PL6 e PL7 precisam ser examinados. Selecionando PL7, o problema nao tem

nenhuma solucao viavel e, portanto, esta descartado. Em seguida, selecionamos PL6, sendo que este problema da

a primeira solucao inteira (x1 = 4; x2 = 0 e f (x) = 20) e, assim, fornece o primeiro limite inferior para o valor

otimo da funcao objetivo para PLI.

Ficamos ainda com PL2, que da uma solucao inteira melhor, como visto no exemplo. Deste modo, o limite

inferior e atualizado e nesse ponto, com todos os subproblemas interpretados, a melhor solucao e a encontrada

para PL2. A sequencia de solucao apresentada na figura 6.4 (PL1→ PL3 → PL5 → PL4 → PL7 → PL6 → PL2)

e a pior hipotese de passos possıveis para o problema do exemplo 25, pois foram percorridos todos os ramos antes



de encontrarmos a solucao otima.

Dos dois cenarios apresentados anteriormente, podemos concluir que a execucao do metodo B&B nao garante

uma solucao PLI global1, apenas de solucoes locais (dependendo do tamanho e complexidade do problema).

Podemos utilizar outros algoritmos matematicos 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 metodos heurısticos3 podem ser aplicados tambem para melhorar a qualidade da solucao e/ou auxiliar na

decisao de qual ramo seguir. Ha casos em que aplica-se apenas tecnicas heurısticas na solucao de um problema de

PLI, pois os metodos convencionais nao sao capazes de fornecerem respostas ao problema.

6.2.1 Resumo do algoritmo Branch-And-Bound (B&B)

Considere um problema de maximizacao e estabeleca um limite inferior inicial f (x) = −∞ para o valor dos

coeficientes da funcao objetivo otima do PLI. Seja i = 0.

1. Selecione um PLi , o proximo subproblema a ser examinado. Resolva o PLi e tente interpreta-lo usando uma

das tres condicoes:

• O valor otimo de f (x) do PLi nao pode dar um valor objetivo melhor do que o limite inferior atual;

• O PLi fornece uma solucao inteira viavel melhor do que o limite inferior atual;

• O PLi nao tem nenhuma solucao viavel.

Surgem dois casos:

• Se o PLi for interpretado e uma solucao for encontrada, atualize o limite inferior. Se todos os subpro-

blemas tiverem sido descartados, pare; o PLI otimo esta associado com o limite inferior finito atual. Se

nao existir nenhum limite inferior finito, o problema nao tem nenhuma solucao viavel. Senao, determine

i = i + 1, e repita a etapa 1 novamente.

• Se o PLi nao for interpretada, va para a etapa 2 e ramifique.

2. Selecione uma das variaveis inteiras xj , cujo valor otimo x∗j na solucao do PLi seja nao inteiro. Elimine a

regiao:

bx∗j c < xj < bx∗j c+ 1

(onde bvc define o maior inteiro ≤ v 4), criando dois subproblemas de PL que correspondem a

bx∗j c ≥ xj e xj ≥ bx∗j c+ 1

Determine i = i + 1, e va para a etapa 1.

As etapas dadas se aplicam a problemas de maximizacao. Para minimizacao, substituımos o limite inferior por

um limite superior (cujo valor inicial e f (x) = +∞).

1Solucao global: melhor solucao para o problema.2O Matodo de Planos de Corte nao serao tratados neste texto, porem a ideia do metodo e a de incorporar restricoes que aproximem

a regiao relaxada ao conjunto de pontos inteiros factıveis.3Metodos heurısticos sao metodos (ou tecnicas) sem um detalhado rigor matematico, podendo ser especıfico para classes de

problemas.4Como exemplo, considere xj = 3.8, assim bx∗j c = 3 e o intervalo 3 < xj < 4.



O algoritmo B&B pode ser estendido diretamente a problemas mistos (nos quais apenas algumas das variaveis

sao inteiras). Se uma variavel for contınua, simplesmente nunca a selecionamos como uma variavel de ramificacao.

Um subproblema viavel fornece um novo limite para o valor dos coeficientes da funcao objetivo se os valores das

variaveis discretas forem inteiras e se o valor da funcao objetivo for melhor em relacao ao limite atual.

Apos a explicacao e a sıntese do algoritmo Branch-and-Bound, vamos citar dois grandes tipo de problemas que

fazem uso do algoritmo para suas respectivas resolucoes. 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 alocacao de recursos em um determinado espaco compartimentado, como uma mochila, constituindo

entao, 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, nao sendo

possıvel excluir ou voltar pelo mesmo caminho. Essa classe de problemas e um dos mais estudados em matematica

computacional e sua aplicacao varia entre obter a melhor rota de uma frota de onibus, logıstica de embarque e

desembarque de passageiros em aerportos, trafego de rede de computadores, entre outros.

Especificamente, em uma situacao de n cidades, definimos:

xi j =

1, se o caixeiro vai diretamente da cidade i a cidade j, i 6= j

0, caso contrario

Dado que di j e a distancia da cidade i a cidade j , o problema e dado por

min f (x) =

n∑i=1

∑j>i

di jxi j

S. a∑j<i

xj i +∑j>i

xi j = 2 , i = 1 : n

∑i∈S

∑j /∈S, j>i

xi j +∑i /∈S

∑j∈S, j>i

xi j ≥ 2 , S ⊂ N, 3 ≤|S|≤⌊n

2

⌋x ∈ Bn(n−1)/2

(6.3)

A funcao objetivo do problema (6.3) expressa a minimizacao da distancia total da rota, a primeira restricao impoe

que cada cidade tenha somente uma cidade sucessora imediata e uma cidade predecessora imediata. A segunda

restricao elimina sub-rotas pois para cada conjunto S, existem no mınimo duas arestas entre as cidades de S e as

cidades nao pertencentes a S. A cardinalidade de S e no mınimo 3 (tres), pois um ciclo em um grafo nao orientado

tem pelo menos 3 nos e no maximo⌊n

2

⌋, pois ao se eliminar ciclos com k nos, eliminam-se ciclos com n − k nos

(vide figura 6.5 (c)). A ultima restricao indica o tipo de variaveis.

A figura 6.5 apresenta possıveis cenarios de um TSP com 5 cidades, onde os circulos representam as cidades

e as linhas, conhecidas como arcos, as ligacoes entre estas cidades, neste caso abordado sao rotas de duas vias

(simetria – ida e volta), como mostra a figura 6.5 (a). O item (b) apresenta uma possıvel solucao (otima ou viavel)

para este exemplo grafico e o item (c) uma solucao de subcircuitos (solucao inviavel).

5O problema do caixeiro viajante aparece na literatura (estrangeira ou nacional) com a sigla TSP que e a abreviatura de traveling

salesman problem.



2

4

13

5

2

4

13

5

(a) Problema com 5 cidades.

2

4

13

5

(b) Solucao do circuito.

(c) Solucao de subcircuitos.

Figura 6.5: Exemplo do problema do caixeiro-viajante com 5 cidades.

6.4 Problema da MochilaEste problema lida com uma questao de situacao na qual um ındividuo deve decidir quais sao os itens mais

valiosos para carregar em uma mochila, podendo se estender a situacoes de corte e empacotamentos e ate carre-

gamentos de veıculos de determinadas dimensoes. Sendo entao, uma generalizacao metaforica para um problema

geral de alocacao de recurso no qual um unico recurso limitado e designado a varias 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 selecao 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.



Defina as variaveis:

xj =

1 se o produto j e selecionado

0 caso contrario

O problema e, entao, formulado como:

max f (x) =

n∑j=1

pjxj

S. a

n∑j=1

ajxj ≤ b

x ∈ Bn

(6.4)

A funcao objetivo do problema (6.4) expressa a maximizacao do retorno esperado, a primeira restricao indica que

o capital b nao pode ser excedido e a ultima restricao representa o tipo de variaveis.

Esse problema e denominado problema da mochila devido a analogia do problema que envolve a decisao 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 parametros:

p = [pj ] = [41 33 14 25 32 32 9 19]

a = [aj ] = [47 40 17 27 34 23 5 44]

A solucao otima e dada por x2 = x4 = x6 = x7 = 1. Esta solucao utiliza 40 + 27 + 23 + 5 = 95 unidades do capital.

6.4.2 Mochila Inteira

Neste problema, a variavel de decisao xj ≥ 0, j = 1 : n, pode assumir um valor inteiro nao negativo, isto e,

pode-se levar diversas unidades do mesmo item na mochila. A formulacao e identica a da mochila 0-1, ao substituir

x ∈ Bn por x ∈ Zn+.

6.4.3 Multiplas 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 maximo bi e o lucro total seja maximizado. Este problema

ocorre em situacoes de carregamento de conteineres e em situacoes de corte nas industrias de papel e aco.


xi j =

1 se o item j e colocado na mochila i

0 caso contrario

O problema e formulado como:

max f (x) =

n∑i=1

n∑j=1

pjxi j

S. a

n∑j=1

wjxi j ≤ bi i = 1 : n∑i=1

xi j ≤ 1 j = 1 : n

x ∈ Bmn

(6.5)



A funcao objetivo do problema (6.5) representa a maximizacao do lucro total, a primeira restricao garante que a

capacidade bi da mochila i nao pode ser excedida, a segunda restricao indica que se o item j e escolhido, entao ele

e colocado em um unica mochila e a ultima restricao representa o tipo de variaveis.

6.4.4 Empacotamento de Mochilas

No problema anterior, o numero de mochilas e dado e alguns itens podem nao ser colocados nas mochilas. No

problema de empacotamento em mochilas, conhecido como bin packing, deseja-se determinar o numero 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 tambem o arranjo de objetos em dispositivos bidimensionais e tridimensionais6,

tais como nos problemas de carregamentos de produtos sobre paletes ou dentro de conteineres ou caminhoes.


yj =

1, se a mochila i e usada

0, caso contrarioe xi j =

1, se o item j e colocado na mochila i

0, caso contrario

Tem-se, entao, a seguinte formulacao:

min f (x) =

n∑i=1

yi

S. a∑i=1

xi j ≤ 1 j = 1 : n

n∑j=1

wjxi j ≤ byi i = 1 : n

x ∈ Bmn

y ∈ Bn

(6.6)

A funcao objetivo do problema (6.6) minimiza o numero de mochilas. Note que o limitante superior do numero

de mochilas e igual ao numero de itens n. O conjuto de equacoes expresso pela primeira restricao asseguram que

cada item j e colocado em uma unica mochila, o conjunto de equacoes expresso pela segunda restricao impoem

que se a mochila e usada, entao sua capacidade b nao pode ser excedida. Finalmente, as duas ultimas restricoes

indicam o tipo das variaveis.

6Problemas de carregamento tridimensionais sao complexos e usualmente resolvidos por metodos heurısticos.



6.5 Exercıcios Propostos1. Desenvolva a arvore do B&B para cada um dos seguintes problemas. Por conveniencia, sempre selecione x1

como a variavel de ramificacao no primeiro no.

(a)

max f (x) = 3x1 + 2x2

S. a 2x1 + 5x2 ≤ 9

4x1 + 2x2 ≤ 9

x1, x2 ≥ 0

x1, x2 ∈ Z

(b)

max f (x) = x1 + x2

S. a 2x1 + 5x2 ≤ 16

6x1 + 5x2 ≤ 27

x1, x2 ≥ 0

x1, x2 ∈ Z

(c)

max f (x) = 5x1 + 7x2

S. a 2x1 + x2 ≤ 13

5x1 + 9x2 ≤ 41

x1, x2 ≥ 0

x1, x2 ∈ Z

2. Mostre graficamente que o seguinte problema de PLI nao tem nenhuma solucao viavel e entao verifique o

resultado usando B&B.max f (x) = 2x1 + x2

S. a 10x1 + 10x2 ≤ 9

10x1 + 5x2 ≤ 1

x1, x2 ≥ 0

x1, x2 ∈ Z2+

3. Resolva o problema de programacao inteira:

max f (x) = x1 + x2

S. a −2x1 + 2x2 ≤ 3

7x1 + 3x2 ≤ 22

x1 x2 ∈ Z2+

(a) Graficamente.

(b) Pelo metodo branch-and-bound.

4. Agora vamos a um problema de um caixeiro-viajante, que na verdade e um representante comercial e vendedor

de publicacoes literarias. Este profissional mora na cidade de Basin, e deve visitar uma vez por mes quatro

clientes localizados nas cidades de Wald, Bom, Mena e Kiln. A tabela 6.1 da as distancias em milhas entre

as diferentes cidades.

O objetivo e minimizar a distancia total percorrida pelo vendedor, formule entao a questao como um problema

de PLI7.

7Se houver dificuldade na formulacao, observe o exemplo da pagina 172 de [14].



Milhas entre as cidades

Basin Wald Bon Mena Kiln

Basin 0 120 220 150 210

Wald 120 0 80 110 130

Bon 220 80 0 160 185

Mena 150 110 160 0 190

Kiln 210 130 185 190 0

Tabela 6.1: Distancias entre as cidades.

5. Um ecologista brasileiro, trabalhando na Amazonia, foi contratado para realizar a divisao de parte da floresta

em reservas florestais. Estudos recentes dividiram a floresta em dez regioes. O trabalho do ecologista

consiste em formar cinco reservas a partir dessas informacoes, observando o numero de predadores e presas

que cada regiao contem. A tabela 6.2 mostra esses dados para cada regiao (em milhares). Os animais nao

podem ser removidos de sua regiao e cada reserva deve conter entre 80 mil e 130 mil animais. Sabe-se que o

ideal e que o numero de presas deve ser maior que o numero de predadores em uma reserva, para garantir o

equilıbrio entre as especies. Formule um problema para ajudar o ecologista a formar cinco reservas garantindo

o equilıbrio.

Regiao Predadores Presas

1 40 17

2 29 24

3 20 22

4 25 22

5 20 57

6 19 32

7 37 7

8 10 11

9 35 27

10 35 32

Tabela 6.2: Numero de presas e predadores por regiao.

6. Um caminhao de entrega de oleo de uma empresa contem cinco compartimentos, com capacidade para 2700,

2800, 1100, 1800 e 3400 galoes de combustıveis, respectivamente. A empresa deve entregar tres tipos de

combustıveis A, B e C para um cliente. Parte da demanda pode nao ser atendida, mas, neste caso, a empresa

deve arcar com os custos. As demandas, penalidades por galao nao entregue e o numero maximo de galoes

de demanda nao atendidas sao descritas na tabela 6.3. Cada compartimento pode levar apenas um tipo de

combustıvel. Formule o problema de carregar o caminhao de forma a minimizar os custos de nao atendimento

da demanda.

Combustıvel Demanda Custo por galao Maximo de demanda

nao entregue nao atendida

A 2900 10 500

B 4000 8 500

C 4900 6 500

Tabela 6.3: Custo de combustıveis.



7. Experimente colocar este problema em um software como o TORA/Solver/AMPL8. Este problema foi proje-

tado para demonstrar o comportamento bizarro do algoritmo B&B ate mesmo para problemas pequenos. Em

particular, observe como muitos subproblemas serao examinados antes do software achar o otimo e quantos

sao necessarios para verificar a otimalidade. Seja o problema:

min f (y) = y

S. a 2(x1 + x2 + x3 + . . . + x5) + y = 15

Todas as variaveis sao (0, 1)

(a) Use a opcao automatica do TORA para mostrar que, embora a solucao otima seja encontrada apos 9

subproblemas, mais de 25.000 subproblemas sao examinados antes de confirmar a otimalidade.

(b) Mostre que o Solver exibe uma experiencia semelhante a do TORA. No Solver, voce pode observar a

mudanca no numero de ramos gerados (subproblemas) na parte inferior da planilha.

(c) Resolva o problema com o AMPL e mostre que a solucao obtida instantaneamente com 0 iteracoes

simplex MIP e 0 nos B&B. A razao para esse desenpenho superior so pode ser atribuıda as etapas

preparatorias executadas pelo AMPL e/ou pelo resolvedor CPLEX antes de resolver o problema.

8Para maiores informacoes consulte [14].


CAPITULO 7

O Uso de Excel e do lp solve para Problemas de

Programacao Linear

7.1 IntroducaoA aplicacao bem sucedida da Programacao Matematica envolve habilidades tanto em Matematica quanto em

Computacao. Neste sentido, alguns softwares foram desenvolvidos para facilitar o uso desta importante ferramenta

de decisao. Para problemas de Programacao Linear (PL) podemos contar com os softwares Microsoft Office

Excel r© (ou MS-Excel), Planilha Eletronica do ambiente Open Office, lp solve (vide [9]), CPLEX (vide [5]), entre

outros. Abordaremos aqui as ferramentas para PL dos softwares Microsoft Office Excel e lp solve.

Para auxiliar na manipulacao destes softwares26, tomemos o exemplo abaixo (7.1).

max f (x) = 12x1 + 8x2 + 6x3

S. a 2x1 + x2 + x3 ≤ 16

3x1 + 4x2 ≤ 48

4x1 + x2 + 2x3 ≤ 24

x1, x2, x3 ≥ 0

(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 instalacao.

A figura 6.1 mostra em destaque o menu principal da Planilha Excel. Neste menu, selecione o ıcone abaixo

Opcoes do Excel.

A figura 7.2 apresenta a janela previamente escolhida. Escolha o ıcone Suplementos.

Na figura 7.3 utilize a opcao 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 instalacao, podemos utiliza-lo para a resolucao de problemas de Programacao Matematica.

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 (celulas B2:D5) e

coluna G entre as linhas 2 ate 4 (celulas G2:G4) sao os dados de entrada do problema.

Capıtulo 7. O Uso de Excel e do lp solve para Problemas de Programacao Linear PL

Figura 7.1: 1o Passo para instalacao do Excel Solver.








Figura 7.5: Descricao do problema.

A coluna E (celulas E2:E4) e celula F7 contem as equacoes relativas as restricoes R1, R2, R3 e funcao objetivo.

A tabela 7.1 mostra as funcoes do problema (7.1) e seu posicionamento nas celulas adequadas.

Expressao Formula na Inserida

algebrica planilha na celula

R1 2x1 + x2 + x3 =B2*$B$6 + C2*$C$6 + D2*$D$6 E2

R2 3x1 + 4x2 =B3*$B$6 + C3*$C$6 + D3*$D$6 E3

R3 4x1 + x2 + 2x3 =B4*$B$6 + C4*$C$6 + D4*$D$6 E4

max f (x) 12x1 + 8x2 + 6x3 =B5*$B$6 + C5*$C$6 + D5*$D$6 F7

Tabela 7.1: Expressoes algebricas.

Na pratica, basta que se digite a formula para a celula E2 e entao copie para as demais celulas. Para fazer isso

corretamente, devem ser usadas as referencias fixas $B$6, $C$6 e $D$6, que representam as variaveis x1, x2 e x3.

Para programas maiores e mais eficiente digitar (ou procurar no ıcone de formulas):

=SOMARPRODUTO(B2:D2;$B$6:$D$6)

na celula E2 e copiar para as demais. Agora todos os parametros estao prontos para serem vinculados ao solver.

A figura 7.6 mostra a janela aberta apos selecionar o ıcone Solver. Primeiramente, define-se a funcao objetivo

– celula $F$7, o sentido da otimizacao – igual a “Max”, e as celulas das variaveis – $B$6:$D$6.

Estas informacoes deixam claro para o Solver que as variaveis definidas pelas celulas $B$6, $C$6 e $D$6 sao

determinadas pela maximizacao da funcao objetivo na celula $F$7.

A poxima etapa e estabelecer as restricoes dos problemas clicando em Adicionar na caixa de dialogo Parametros

do Solver. A caixa Adicionar restricoes sera exibida, como mostra a figura 7.7 para facilitar a digitacao dos

elementos das restricoes:

$E$2:$E$4 <= $G$2:$G$4



Figura 7.6: Solver.

Figura 7.7: Relacionando as restricoes.

Uma maneira de entrar com as restricoes de nao negatividade e clicar em Opcoes na caixa de dialogo Parametros

do Solver para acessar a caixa de dialogo Opcoes do Solver, como mostra a figura 7.8, selecionar Presumir nao

negatividade. Pode tambem selecionar Presumir modelo linear.

Para resolver o problema, clique Resolver em Parametros do Solver. Uma nova caixa de dialogo, Resultado

do Solver dara o status da solucao (figura 7.9). Se a montagem do problema estiver correta, o valor otimo da



Figura 7.8: Opcoes do Solver.

funcao objetivo aparecera na celula $F$7 e os valores de x1, x2 e x3 irao para as celulas $B$6, $C$6 e $D$6,

respectivamente.

Figura 7.9: Solucao.

Se o problema nao tiver solucao viavel, o Solver emitira a mensagem explıcita “Solver nao pode achar uma

solucao viavel”. Se o valor objetivo otimo for ilimitado, o Solver emitira uma mensagem ambıgua “Os valores das

celulas de destino nao convergem”. Em qualquer um dos casos, a mensagem indica que ha algo errado com a



formulacao do modelo.

A caixa de dialogo Resultados do Solver lhe dara oportunidade de requisitar mais detalhes sobre a solucao,

incluindo o relatorio de sensibilidade, como mostram as figuras 7.10, 7.11 e 7.12.

Figura 7.10: Relatorio de sensibilidade.

Figura 7.11: Relatorio de resposta.


lp solve Capıtulo 7. O Uso de Excel e do lp solve para Problemas de Programacao Linear

Figura 7.12: Relatorio de limites.

7.3 lp solve

O software lp solve e um solver para problemas de Programacao Linear Inteira Mista, vide [9]. Como o primeiro

passo na resolucao de um problema de Programacao Inteira e a de relaxar a condicao de integralidade das variaveis,

ou seja, resolver um problema de Programacao Linear, sua aplicabilidade e direta em PL. O software lp solve e

livre (licensa LGPL), baseado no Metodo Simplex Revisado (para PL) e Branch-and-Bound (para Programacao

Inteira).

Note que, este solver e exclusivo para problemas lineares, ou seja, as equacoes do problema devem ser de

primeira ordem. Por outro lado, o Excel Solver permite a resolucao de problemas nao lineares.

Este software foi desenvolvido por Michel Berkelaar na Eindhoven University of Technology. O trabalho de

Jeroen Dirks fez a transicao da versao basica 1.5 para a versao completa 2.0. lp solve possui uma comunidade

via Yahoo group http://groups.yahoo.com/group/lp solve/, onde vc encontra as ultimas fontes, executaveis

para plataforma comum, exemplos, manuais e mensagens de ajuda sobre o lp sove.

A instalacao deste software e relativamente simples e pode ser feita atraves do site

http://sourceforge.net/projects/lpsolve/.

Apos a instalacao, em ambiente Windows, aparecera um ıcone na sua area de trabalho permitindo o acesso

direto. A figura 7.13 apresenta a tela inicial do solver.

Considere o problema (7.1), sua implementacao e direta, como mostra a figura 7.14.

No menu superior, selecione a opcao 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 resolucao do problema em questao.

As janelas apresentadas pelas figuras 7.16 e 7.17 mostram o problema em forma matricial e os valores das

variaveis apos o processo de otimizacao, respectivamente.

111


Figura 7.13: O ambiente LP Solve.

Figura 7.14: Descricao do problema (7.1).

112


Figura 7.15: O ıcone de resolucao.

Figura 7.16: Mensagem de resolucao.

113


Figura 7.17: Resolucao na forma matricial.

Figura 7.18: Resultados das variaveis de decisao.

114

Referencias Bibliograficas

[1] E. L. de Andrade. Introducao a Pesquisa Operacional: Metodos e Modelos para Analise de Decisao. Terceira Edicao.

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. Algebra Linear. 3a Edicao, Editora Harbra, 1980.

[5] http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/. Ultimo 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. Otimizacao Combinatoria e Programacao Linear. Editora Campus, 2000.

[8] G. Lachtermacher. Pesquisa Operacional. 4a Edicao, Pearson Prentice Hall, 2009.

[9] http://lpsolve.sourceforge.net/5.5/. Ultimo 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. Tecnicas de Otimizacao. LTC, 2009.

[12] L. A. Pinto. Metodos de Pontos Interiores para Programacao Inteira. UNESP – Campus de Sao Jose do Rio Preto,

Dissertacao de Mestrado, 1999.

[13] E. M. da Silva, E. M. da Silva, V. Goncalves e A. C. Murolo. Pesquisa Operacional para os cursos de Economia,

Administracao e Ciencias Contbeis. Terceira Edicao, Editora Atlas, 1998.

[14] H. A. Taha. Pesquisa Operacional. 8a Edicao, Pearson Prentice Hall, 2008.

[15] R. J. Vanderbei. Linear Programming: Foundations and Extensions. Kluwer Academic Publishers, 1997.

115

Documents

Programa˘c~ao Linear { PL - Unesp · Cap tulo 1. Introdu˘c~ao a Pesquisa Operacional PL 1.1Otimiza˘c~ao (C alculo Diferencial) e Sistemas de equa˘c~oes (Algebra Linear) na PO