Introd_Form_AL_RG_Simplex_PI_PD

Prévia do material em texto

Caṕıtulo 1
Introdução à Pesquisa Operacional
A Pesquisa Operacional, PO, é uma ciência que objetiva fornecer ferramentas quantitati-
vas ao processo de tomada de decisões.
As primeiras atividades formais da Pesquisa Operacional iniciaram na Inglaterra durante a
Segunda Guerra Mundial, quando uma equipe de cientistas britânicos decidiu tomar decisões
com bases cient́ıficas sobre a melhor utilização de material de guerra. Após a guerra, as
ideias propostas para operações militares foram adaptadas para melhorar a eficiência e a
produtividade no setor civil (Taha 2008).
A PO trabalha com problemas de condução e coordenação de operações em organiza-
ções, sendo aplicada em diversas áreas, tais como: indústrias, transportes, telecomunicações,
finanças, sáude, serviços públicos, operações militares, dentre outras (Moreira 2007).
A observação inicial e a formulação do problema estão entre os mais importantes passos
da solução de um problema por PO (Moreira 2007), por isso não se tem uma única técnica
para resolver todos os modelos matemáticos que podem surgir na prática. Em vez disso, o
tipo e a complexidade do modelo matemático é que determinam a natureza do método de
solução.
A Figura 5.2 ilustra um processo simplificado da abordagem de solução de um problema
usando a modelagem matemática.
problema real
sistema ou
Matemático
Conclusões doConclusões
reais
ModeloFormulação/modelagem
A
va
lia
çã
o
Interpretação
modelo
Dedução/Análise
Figura 1.1: Processo de modelagem matemática
(Arenales, Armentano, Morabito e Yanasse 2007)
1
2
A modelagem matemática de um problema qualquer de PO é descrita no seguinte formato
geral:
Maximizar/Minimizar função objetivo
sujeito a: restrições
A técnica mais utilizada da PO é a programação linear (PL), sendo aplicada a modelos
cujas funções objetivo e restrições são lineares. Outras técnicas que se destacam são: a
programação inteira (PI), sendo que as variáveis assumem valores inteiros, a programação
dinâmica (PD), na qual o modelo original pode ser decomposto em subproblemas mais fáceis
de tratar, a otimização em redes, onde o problema pode ser modelado como uma rede, e a
programação não-linear (PNL), tal que as funções do modelo são não lineares (Taha 2008).
As cinco principais fases de implementação da PO incluem a definição do problema, a
construção do modelo, a solução do modelo, a validação do modelo e a implementação da
solução, descritas a seguir (Taha 2008).
• Definição do problema: envolve o escopo do problema sob investigação;
• construção do modelo: implica em uma tentativa de traduzir a definição do problema
em relações matemáticas. Se o modelo resultante se ajustar a um dos métodos mate-
máticos padrão, tal como programação linear, pode-se, em geral, chegar a uma solução
utilizando algoritmos dispońıveis;
• solução do modelo: se baseia na utilização de algoritmos de otimização bem-definidos;
• validação do modelo: verifica se o modelo proposto faz ou não o que diz resolver, isto
é, ele prevê adequadamente o comportamento do sistema de estudo?
• implementação do modelo: envolve a tradução dos resultados em instruções opera-
cionais inteleǵıveis que serão emitidas para as pessoas que administrarão o sistema
recomendado.
As disciplinas que constituem a PO se apóiam na Economia, Matemática, Estat́ıstica e
Informática.
Neste curso serão abordadas as seguintes técnicas de PO: Programação Linear, Progra-
mação Inteira, Programação Dinâmica, Programação Não-Linear, Otimização em Redes e
Simulação de Sistemas.
Caṕıtulo 2
Formulação e Modelagem Matemática
A representação da realidade é uma necessidade da sociedade moderna, seja pela im-
possibilidade de lidar diretamente com a realidade, seja por aspectos econômicos, seja pela
complexidade. Assim, busca-se a representação da realidade por meio de modelos que sejam
bem estruturados e representativos desta realidade (Camponogara 2006).
Modelos são representações simplificadas da realidade que preservam, para determinadas
situações e enfoques, uma equivalência adequada.
A resolução de um problema por meio de um modelo de otimização pressupõe a existência
de um conjunto de decisões a serem tomadas as quais, por sua vez, devem satisfazer um
conjunto de regras. As decisões a serem determinadas são chamadas incógnitas ou variáveis
de decisão e as regras definem as restrições do problema. A modelagem matemática consiste
em tratar as incógnitas simbolicamente por: x, y, etc.
A seguir é apresentado um modelo de formulação de um problema de PO.
Modelo I:
Min/Max f(x1, x2, . . . , xn) = c1x1 + c2x2 + · · ·+ cnxn (1)
s.a : a11x1 + a12x2 + · · ·+ a1nxn = b1
a21x1 + a22x2 + · · ·+ a2nxn = b2 (2)
...
am1x1 + am2x2 + · · ·+ amnxn = bm
xj ≥ 0, j = 1, 2, . . . , n (3)
tal que cj , aij e bi, i = 1, 2, ..., m, j = 1, 2, ..., n são valores conhecidos, sendo chamados de
dados do problema.
As variáveis do problema (incógnitas) são denotadas por x1, x2, ..., xn e devem satisfazer
as restrições e as condições de não-negatividade (restrições de sinal) do Modelo I, (2) e (3)
respectivamente. Se os valores atribúıdos às variáveis satisfazem todas as restrições então
tem-se uma solução fact́ıvel. O conjunto de todas soluções fact́ıveis define uma região no ℜn,
denominada região de factibilidade.
3
4
Se uma solução fact́ıvel particular (x∗1, x
∗
2, . . . , x
∗
n) tal que:
f(x∗1, x
∗
2, . . . , x
∗
n) ≤ f(x1, x2, . . . , xn)
para toda solução fact́ıvel (x1, x2, . . . , xn), então diz-se que (x
∗
1, x
∗
2, . . . , x
∗
n) é uma solução
ótima. Logo, resolver um problema de otimização consiste em determinar uma solução ótima.
As restrições (2 - Modelo I), embora apresentadas como equações, poderiam ter sido
formuladas originalmente como inequações. Isto não representa qualquer dificuldade, pois se
a i-ésima restrição é do tipo:
ai1x1 + ai2x2 + · · ·+ ainxn ≤ bi
esta pode ser escrita equivalentemente por:
xk = bi − (ai1x1 + ai2x2 + · · ·+ ainxn) ≥ 0
ou ainda:
ai1x1 + ai2x2 + · · ·+ ainxn + xk = bi, xk ≥ 0
com k ≥ n + 1. A variável xk é chamada variável de folga. Serão tantas variáveis de folga
quanto forem as restrições de desigualdades.
O exemplo a seguir ilustra como é feita a inclusão de variáveis de folga/excesso quando
se tratar de restrições com inequações.
Exemplo 2.1 Considere o sistema:
3x1 + x2 ≤ 5
x1 + 2x2 ≤ 2
x1, x2 ≥ 0
Este pode ser escrito equivalentemente por:
3x1 + x2 + x3 = 5
x1 + 2x2 + x4 = 2
x1, x2, x3, x4 ≥ 0
Exerćıcio 2.1 Escreva o seguinte problema de otimização linear no formato (1), (2) e (3)
do Modelo I.
max f(x1, x2) = 3x1 − x2
2x1 + x2 ≥ 2
−x1 + x2 ≥ 1
x1 + x2 ≤ 4
x1, x2 ≥ 0
2.1 Formulação Matemática 5
Exerćıcio 2.2 Dado o seguinte problema:
max z = 5x1 + 4x2
s.a : 6x1 + 4x2 ≤ 24
x1 + x2 ≤ 1
x2 ≤ 2
x1, x2 ≥ 0
Escreva-o na forma padrão (Modelo I).
2.1 Formulação Matemática
Nesta seção é abordada a formulação matemática dos problemas de PO, sendo enfatizados
problemas lineares.
Exemplo 2.2 Aplicação de Programação Linear - Planejamento da Produção
Um sapateiro dispõe de poucas unidades de couro, borracha e cola para fabricar sapatos
e botinas. Considerando os dados da Tabela 2.1, formule o problema com o objetivo de
maximizar o lucro do sapateiro.
Mat. Prima/Produtos Sapatos Botinas Disponibilidade
Couro 2 1 8
Borracha 1 2 7
Cola 0 1 3
Lucro (un.) 1 1 -
Tabela 2.1: Disponibilidade de matéria prima
Solução: Modelo Matemático (variáveis):
x1 - quantidade de sapatos a serem fabricados
x2 - quantidade de botinas a serem fabricadas
A formulação do problema com a finalidade de maximizar o lucro é escrito da seguinte forma:
max f(x1, x2) = x1 + x2
s.a : 2x1 + x2 ≤ 8
x1 + 2x2 ≤ 7
x2 ≤ 3
x1, x2 ≥ 0
Exemplo 2.3O problema de transporte (Arenales et al. 2007).
Uma empresa produz latas de conserva em duas fábricas e as vende por meio de três
depósitos, conforme Figura 2.1
2.1 Formulação Matemática 6
1
2
1
2
3
c11
c12c13
c21
c22
c23
a1
a2
b1
b2
b3
Figura 2.1: Rede de transporte
sendo: ai - capacidade de produção da fábrica i; bj - demanda de produtos no depósito j; cij
- custo por produto transportado da fábrica i ao depósito j.
A empresa deseja saber como distribuir a produção pela rede de modo a:
1. respeitar as capacidades produtivas de cada fábrica;
2. respeitar as demandas de cada depósito; e
3. minimizar o custo total de transporte.
Formule o problema.
Solução:
Variável: xij: quantidade de latas transportadas de i para j.
Min Z = c11x11 + c12x12 + c13x13 + c21x21 + c22x22 + c23x23
s.a : x11 + x12 + x13 ≤ a1
x21 + x22 + x23 ≤ a2
x11 + x21 ≥ b1
x12 + x22 ≥ b2
x13 + x23 ≥ b3
xij ≥ 0, i = 1, 2 e j = 1, 2, 3
Exerćıcio 2.3 Dispõe-se de 5 tipos de alimentos com diferentes composições de nutrientes
(protéınas e sais minerais), conforme Tabela 2.2. Uma vez conhecido o custo de cada ali-
mento, deseja-se determinar a dieta que satisfaz os padrões nutritivos e que tenha o custo
mı́nimo. Formule o problema.
Nutrientes/Alimentos 1 2 3 4 5 necessidades-nutrientes
Protéınas 3 4 5 3 6 42
Sais Minerais 2 3 4 3 3 24
Custo 25 35 50 25 36
Tabela 2.2: Composições nutricionais
2.1 Formulação Matemática 7
Variável: xi - quantidade do alimento i presente na dieta. Formule este problema matemati-
camente.
Exerćıcio 2.4 (Arenales et al. 2007) Um fabricante de geladeiras precisa decidir quais mo-
delos deve produzir em uma nova fábrica, recentemente instalada. O departamento de mar-
keting e vendas realizou uma pesquisa de mercado que indicou, no máximo, 1.500 unidades
do modelo de luxo e 6.000 unidades do modelo básico podem ser vendidas no próximo mês.
A empresa já contratou um certo número de empregados e, com isso, dispõe de uma força de
trabalho de 25.000 homens-hora por mês. Cada modelo de luxo requer dez homens-hora e cada
modelo básico requer oito homens-hora para ser montado. Além disso, uma mesma linha de
montagem é compartilhada pelos dois modelos e considere que a capacidade de produção desta
linha seja de 4.500 geladeiras por mês. O lucro unitário do modelo de luxo é de $100,00, e do
modelo básico é de $50,00. Deseja-se determinar quanto produzir de cada modelo de modo a
maximizar o lucro da empresa. Definindo xj como a quantidade de geladeiras do tipo j a ser
produzidas , formule o problema.
Exerćıcio 2.5 (da Silva, da Silva, Gonçalves e Murolo 2010) No programa de produção para
o próximo peŕıodo, a Empresa Beta Ltda., escolheu três produtos P1, P2 e P3. A Tabela 2.3
mostra os montantes solicitados por unidade de produção.
Produto Contribuição Horas de Horas de uso Demanda
(lucro por un.) trabalho de máquina máxima
P1 2100 6 12 800
P2 1200 4 6 600
P3 600 6 2 600
Tabela 2.3: Montantes do problema
Os preços de venda foram fixados por decisão poĺıtica e as demandas foram estimadas
tendo em vista esses preços. A empresa pode obter um suprimento de 4800 horas de trabalho
durante o peŕıodo de processamento e pressupõe-se usar três máquinas que podem provar
7200 horas de trabalho. Formule o problema de modo a maximizar o lucro obedecendo as
restrições.
Exerćıcio 2.6 (Goldbarg e Luna 2005). O problema da dieta. Determinar, em uma dieta
para redução calórica, as quantidades de certos alimentos que deverão ser ingeridos diaria-
mente, de modo que determinados requisitos nutricionais sejam satisfeitos a custo mı́nimo.
Uma certa dieta alimentar é restrita a leite desnatado, carne magra de boi, carne de peixe
e uma salada de composição bem conhecida. Os requisitos nutricionais serão expressos em
termos de vitaminas A, C e D e controlados por suas quantidades mı́nimas (em miligramas),
2.1 Formulação Matemática 8
uma vez que são indispensáveis à preservação da saúde da pessoa que estará se submetendo à
dieta. A Tabela 2.4 resume a quantidade de cada vitamina em disponibilidade nos alimentos
e a sua necessidade diária para a boa saúde de uma pessoa.
Vitamina/ Leite Carne Peixe Salada Requisito Nutricional
Alimento (litro) (kg) (kg) (100g) Mı́nimo
A 2 mg 2 mg 10 mg 20 mg 11 mg
C 50 mg 20 mg 10 mg 30 mg 70 mg
D 80 mg 70 mg 10 mg 80 mg 250 mg
Custo R$2, 00 R$4, 00 R$1, 50 R$1, 00 -
Tabela 2.4: Disponibilidade vitamina x alimento
Deseja-se minimizar o custo financeiro de uma dieta, obedecendo às restrições nutricionais
desta. Formule o problema.
Exerćıcio 2.7 (Goldbarg e Luna 2005). O problema da cooperativa agŕıcola. Uma coopera-
tiva agŕıcola opera três fazendas que possuem produtividades aproximadamente iguais entre
si. A produção total por fazenda depende fundamentalmente da área dispońıvel para o plantio
e da água de irrigação, conforme Tabela 2.5. A cooperativa procura diversificar sua produção
de modo que vai plantar este ano três tipos de cultura em cada fazenda, a saber: milho, arroz
e feijão. Cada tipo de cultura demanda por uma certa quantidade de água. Para reduzir o
conflito no uso das colheitadeiras, que são alugadas pela cooperativa, estabeleceram-se limites
de área de produção dentro de cada tipo de cultura (Tabela 2.6). Para evitar a concorrência
entre os cooperados, acordou-se que a proporção de área cultivada seja a mesma para cada
uma das fazendas. As tabelas a seguir assumem os dados tecnológicos. Pede-se a formulação
de um programa de produção que defina a área de cada cultura que será plantada em cada
fazenda, de modo a otimizar o lucro total da produção da cooperativa.
Fazenda Àrea total para Água dispońıvel
cultivo (alqueire) (litros)
1 400 1800
2 650 2200
3 350 950
Tabela 2.5: Água dispońıvel e área de cultivo por fazenda.
Exerćıcio 2.8 Uma marcenaria que fabrica mesas e cadeiras está equipada com 10 serras,
6 tornos e 18 lixadeiras. Para fazer uma mesa são necessários 5 minutos na serra, 5 minutos
no torno e 20 minutos na lixadeira; para fazer uma cadeira são necessários 15 minutos de
2.2 Notação Matricial 9
Cultura Área máxima de Consumo de água Lucro
cultivo (alqueire) (litros por alqueire) (R$ por alqueire)
Milho 660 5,5 5000
Arroz 880 4 4000
Feijão 400 3,5 1800
Tabela 2.6: Consumo de água, área de cultivo e lucro por cultura.
serra, 5 minutos de torno e 5 minutos de lixadeira. Cada cadeira é vendida a R$10, 00 e
cada mesa por R$20, 00. Quantas mesas e cadeiras, respectivamente, esta marcenaria deve
produzir por hora de maneira a obter a maior receita posśıvel? Ao formula o problema,
despreze o tempo gasto para se passar de uma ferramenta para outra.
2.2 Notação Matricial
O Modelo I (página inicial deste caṕıtulo) pode ser convenientemente escrito em formas
mais compactas.
Sejam:
A =





a11 a12 a13 · · · a1n
a21 a22 a23 · · · a2n
...
...
...
...
am1 am2 am3 · · · amn





, c =





c1
c2
...
cn





, x =





x1
x2
...
xn





, b =





b1
b2
...
bn





.
Diz-se que A ∈ Rmxn (conjunto das matrizes mxn), x ∈ Rn, c ∈ Rn e b ∈ Rn.
O Modelo I pode ser escrito por:
min f(x) = ctx
s.a. : Ax = b
x ≥ 0
(2.1)
O vetor c é chamado de vetor de custos, o vetor b de vetor de recursos, a matriz A de
matriz dos coeficientes e o vetor x de vetor das variáveis ou incógnitas. Em 2.1, x ≥ 0
representa xj ≥ 0, j = 1, 2, ..., n. Durante o curso será adotada esta notação, ou seja, se
x, y ∈ Rn, dize-se que x ≤ y ⇔ xj ≤ yj; j = 1, 2, ..., n.
Outras notações matriciais utilizadas:
aj =





a1j
a2j
...
amj





2.2 Notação Matricial 10
a j-ésima coluna da matriz A, então o Modelo I pode ser escrito por:
min f(x) =
n∑
j=1
cjxj
s.a. :
n∑
j=1
ajxj = b
xj ≥ 0; j = 1, 2, ..., n
(2.2)
De outra maneira, considere a m-ésima linha de A:
ai =(ai1, ai2, ..., ain)
então o Modelo I pode ser equivalentemente escrito por:
min f(x) =
n∑
j=1
cjxj
s.a. : a1x = b1
a2x = b2
...
amx = bm
xj ≥ 0; j = 1, 2, ..., n
(2.3)
Exemplo 2.4 Considere o seguinte Problema de Programação Linear (PPL):
min f(x1, x2) = x1 + 2x2
s.a. : −2x1 + 3x2 ≤ 6
x1 − 2x2 ≤ 4
x1 ≥ 0, x2 ≥ 0
Este sistema pode ser escrito como:
min f(x1, x2) = (1 2)
(
x1
x2
)
s.a. :
(
−2 3
1 −2
)(
x1
x2
)
≤
(
6
4
)
(
x1
x2
)
≥
(
0
0
)
ou
min f(x1, x2) = c
tx
s.a. : Ax ≤ b
x ≥ 0
com:
A =
(
−2 3
1 −2
)
, c =
(
1
2
)
, b =
(
6
4
)
, e x =
(
x1
x2
)
.
2.3 Considerações Finais 11
Exerćıcio 2.9 Considere o seguinte Problema de Programação Linear (PPL):
max f(x1, x2, x3, x4) = 6x1 + 3x2 − 4x3 + x4
s.a. : x1 − 3x2 + x3 ≤ 7
5x1 + 2x2 − x4 ≤ 3
−x1 + x2 + 4x3 − 5x4 ≤ 13
2x1 + 2x2 ≤ 2
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
Escreva-o em notação matricial, semelhante ao exemplo anterior.
2.3 Considerações Finais
Neste caṕıtulo foi abordada a formulação e modelagem matemática de problemas de
Pesquisa Operacional. Também foi discutida sobre a notação matricial dos problemas for-
mulados.
2.4 Exerćıcios
1) Uma fábrica produz 3 tipos de chapas metálicas, A-B-C, que são prensadas e esmaltadas.
A prensa dispõe de 2.000 minutos mensais e cada chapa, A ou B, leva 1 minuto para ser pren-
sada, enquanto a chapa C leva 2 minutos. A esmaltagem nesta última leva apenas 1 minuto,
enquanto as chapas A e B exigem 3 e 4,5 minutos, respectivamente. A disponibilidade da
esmaltagem é de 8.000 minutos mensais. A demanda absorve toda a produção e o lucro por
chapa é de 5, 7 e 8 unidades monetárias, respectivamente, para as chapas A, B e C. Formular
um modelo de PL para a produção de chapas.
2) O setor de transporte de cargas de uma empresa aérea operando em São Paulo dispõe de
8 aviões B-272, 15 aviões Electra e 12 aviões Bandeirante para vôos amanhã. Há cargas para
remeter para o Rio de Janeiro (150ton) e Curitiba (100ton). Os custos operacionais de cada
avião e suas capacidade são:
B-272 Electra Bandeirante
SP → RJ 23 5 1.4
SP → Curitiba 58 10 3.8
Tonelagem 45 7 4
Quantos e quais aviões devem ser mandados para o Rio de Janeiro e Curitiba para satis-
fazer a demanda e minimizar os custos? Formule o PL e deixe-o na forma padrão.
2.4 Exerćıcios 12
3) (da Silva, da Silva, Gonçalves e Murolo 1998) Um sapateiro faz 6 sapatos por hora, se
fizer somente sapatos, e 5 cintos por hora, se fizer somente cintos. Ele gasta 2 unidades de
couro para fabricar 1 unidade de sapato e 1 unidade couro para fabricar uma unidade de
cinto. Sabendo-se que o total dispońıvel de couro é de 6 unidades e que o lucro unitário por
sapato é de 5 unidades monetárias e o do cinto é de 2 unidades monetárias, pede-se: formule
o modelo do sistema de produção do sapateiro, cujo objetivo é maximizar o lucro por hora.
4) (da Silva et al. 1998) Certa empresa fabrica dois produtos P1 e P2. O lucro por unidade de
P1 é de 100 u.m., e o lucro unitário de P2 é de 150 u.m. A empresa necessita de 2 horas para
fabricar uma unidade de P1 e 3 horas para fabricar uma unidade de P2. O tempo mensal
dispońıvel para essas atividades é de 120 horas. As demandas esperadas para os 2 produtos
levaram a empresa a decidir que os montantes produzidos de P1 e P2 não devem ultrapassar
40 unidades de P1 e 30 unidades de P2 por mês. Construa o modelo do sistema de produção
mensal com o objetivo de maximizar o lucro da empresa.
5) (da Silva et al. 1998) Um vendedor de frutas pode transportar 800 caixas de frutas para
sua região de vendas. Ele necessita transportar 200 caixas de laranja a 20 u.m. de lucro
por caixa, pelo menos 100 caixas de pêssegos a 10 u.m. de lucro por caixa, e no máximo
200 caixas de tangerinas a 30 u.m. de lucro por caixa. De que forma deverá ele carregar o
caminhão para obter o lucro máximo? Formule o problema.
6) (Lachtermacher 2009) Um pequeno entregador pode transportar madeira ou frutas em seu
carrinho de mão, mas cobra R$20,00 para cada fardo de madeira e R$35,00 por saco de fru-
tas. Os fardos pesam 1kg e ocupam 2dm3 de espaço. Os sacos de fruta pesam 1kg e ocupam
3dm3 de espaço. O carrinho tem capacidade de transportar 12kg e 10dm3 e o entregador
pode levar quantos sacos e fardos desejar. Formule o problema de forma que o entregador
ganhe o máximo posśıvel.
7) Uma granja quer misturar dois tipos de alimentos para criar um tipo especial de ração
para suas criações. A primeira caracteŕıstica a ser atingida com a nova ração é o menor preço
posśıvel por unidade de peso. Cada um dos alimentos contém os nutrientes necessários à
ração final (denominados de nutrientes X, Y e Z), porém em proporções variáveis. Cada 100g
do Alimento 1, por exemplo, possui 10g do nutriente X, 50g do nutriente Y e 40g do nutriente
Z. O Alimento 2, por sua vez, para cada 100g, possui 20g do nutriente X, 60g do nutriente
Y e 20g do nutriente Z. Cada 100g do alimento 1, custa à granja, R$0,60 e do alimento 2
custa R$0,80. Sabe-se que a ração final deve conter, no mı́nimo, 2g do nutriente X, 64g do
2.4 Exerćıcios 13
nutriente Y e 34g do nutriente Z. É preciso obedecer a essa composição, minimizando ao
mesmo tempo o custo por peso da nova ração. Formule o problema.
8) (Lachtermacher 2009) Uma indústria vende dois produtos, P1 e P2, ao preço por tonelada
de R$70,00 e R$60,00, respectivamente. A fabricação dos produtos é feita em toneladas e
consome recursos que serão chamados de R1 e R2. Esses recursos estão dispońıveis nas quan-
tidades de 10 e 16 unidades, respectivamente. A produção de 1 tonelada de P1 consome 5
unidades de R1 e 2 unidades de R2, e a produção de 1 tonelada de P2 consome 4 unidades de
R1 e 5 unidades de R2. Formule o problema de programação linear para determinar quantas
toneladas de cada produto devem ser fabricadas para se obter o maior faturamento posśıvel.
9) (Taha 2008) A Ozark Farms usa no mı́nimo 800kg de ração especial por dia. Essa ração
especial é uma mistura de milho e soja com as composições (kg por kg de ração) elencadas
na tabela a seguir.
Ração Protéına Fibra Custo (R$)
Milho 0,09 0,02 0,30
Soja 0,60 0,06 0,90
Os requisitos nutricionais da ração especial são de no mı́nimo 30% de protéına e de no
máximo 5% de fibra. A Ozark Farms quer determinar a mistura que gera a ração de mı́nimo
custo diário. Formule o problema.
10) (Lachtermacher 2009) A indústria Alumilâminas S.A. iniciou suas operações há um mês
e vem conquistando espaço no mercado de laminados brasileiro, com contratos fechados de
fornecimento para todos os três tipos diferentes de lâminas de alumı́nio que fabrica: espes-
suras fina, média e grossa. Toda a produção da companhia é realizada nas duas fábricas,
uma localizada em São Paulo e a outra no Rio de Janeiro. Segundo os contratos fechados, a
empresa precisa entregar 16 toneladas de lâminas finas, 6 toneladas de lâminas médias e 28 to-
neladas de lâminas grossas. Devido à qualidade dos produtos da Alumilâminas S.A., há uma
demanda extra para cada tipo de lâmina. A fábrica de São Paulo tem um custo de produção
diária de R$100.000 para capacidade produtiva de 8 toneladas de lâminas finas, 1 tonelada
de lâminas médias e 2 toneladas de lâminas grossas por dia. O custo de produção diário da
fábrica do Rio de Janeiro é de R$200.000 para uma produção de 2 toneladas de lâminas finas,
1 tonelada de lâminas médias e 7 toneladas de lâminas grossas. Quantos dias cada uma das
fáricas deverá operar para atender aos pedidos ao menor custo posśıvel? Formule o problema.
2.4 Exerćıcios 14
11) (Lachtermacher 2009) Um pizzaiolo trabalha 8 horas por dia e faz 16 pizzas por hora, caso
faça somente pizzas, e 9 calzones por hora, se fizer somente calzones. Ele gasta 40g de queijo
para preparar a pizza e 60g de queijo para fazer o calzone. Sabendo que o totaldispońıvel de
queijo é de 5kg por dia, e que a pizza é vendida a R$18,00 e o calzone a R$22,00, pergunta-se:
quantas unidades de pizzas e calzones uma pizzaria deve vender diariamente para maximizar
a sua receita, considerando que ela tem três pizzaiolos? Formule o problema.
12) (Taha 2008) Uma empresa fabrica dois produtos, A e B. O volume de vendas de A
é do mı́nimo 80% do total das vendas de ambos (A e B). Contudo, a empresa não pode
vender mais do que 100 unidades de A por dia. Ambos os produtos usam uma matéria-prima
cuja disponibilidade máxima é 240 lb. As taxas de utilização de matéria-prima são 2 lb por
unidade de A e 4 lb por unidade de B. Os lucros unitários para A e B são de $20 e $50,
respectivamente. Determine o mix de produto ótimo para a empresa. Formule o problema.
13) Uma determinada empresa automobiĺıstica fabrica carros de luxo e caminhonetes. A
empresa acredita que os mais prováveis clientes são homens e mulheres com altos rendimentos.
Para abordar estes grupos, a empresa decidiu por uma campanha de propagandas na TV, e
comprou um minuto do tempo de comercial de 2 tipos de programa: comédia e transmissão
de futebol.
Cada comercial durante o programa de comédias é visto por 7 milhões de mulheres e 2
milhões de homens com grande poder aquisitivo.
Cada comercial durante a transmissão de futebol é visto por 2 milhões de mulheres e 12
milhões de homens com grande poder aquisitivo.
Um minuto de comercial durante o programa de comédias custa R$ 50.000, e durante a
transmissão de futebol R$ 100.000. A empresa gostaria de pelo menos 28 milhões de mulheres
e 24 milhões de homens de grande poder aquisitivo assistissem sua propaganda.
Obter a programação matemática que irá permitir a empresa atender as suas necessidades
de propaganda a um custo mı́nimo e resolver graficamente.
14) (dos Santos 2000) Uma empresa produz 2 produtos em uma de suas fábricas. Na fabrica-
ção dos 2 produtos, 3 insumos são cŕıticos em termos de restringir o número de unidades dos
2 produtos que podem ser produzidas: as quantidades de matéria prima (tipos A e B) dispo-
ńıveis e a mão de obras dispońıvel para a produção dos 2 produtos. Assim, o Departamento
de Produção já sabe que, para o próximo mês, a fábrica terá dispońıvel, para a fabricação
dos 2 produtos, 4900 quilos de matéria prima A e 4500 quilos da matéria prima B.
Cada unidade do produto do tipo I, para ser produzida consome 70 quilos da matéria
2.4 Exerćıcios 15
prima A e 90 quilos da matéria prima B. Por sua vez, cada unidade do produto do tipo II
para ser produzida utiliza 70 quilos da matéria prima do tipo A e 50 quilos da matéria do
tipo B.
Como a produção dos 2 produtos utiliza processos diferentes, a mão de obra é especia-
lizada e diferente para cada tipo de produto, ou seja não se pode utilizar a mão de obra
dispońıvel para a fabricação de um dos produtos para produzir o outro. Assim, para a pro-
dução do produto tipo I a empresa terá dispońıvel, no próximo mês, 80 homens-hora. Já
para o produto tipo II terá 180 homens-hora. Cada unidade do produto tipo I, para ser
produzida, utiliza 2 homens-hora enquanto que cada unidade do produto tipo II utiliza 3
homens-hora. Reduzindo do preço unitário de venda todos os custos, chega-se a conclusão
de que cada unidade do produto tipo I dá um lucro de $20 e cada unidade do produto tipo
II dá um lucro de $60. Dada a grande procura, estima-se que todas as unidades a serem pro-
duzidas, dos 2 produtos, poderão ser vendidas. O objetivo da empresa é obter o maior lucro
posśıvel com a produção e a venda das unidades dos produtos tipo I e II. Formule o problema.
15) (dos Santos 2000) Em uma fazenda deseja-se fazer exatos 10.000 quilos de ração com
o menor custo posśıvel. De acordo com as recomendações do veterinário dos animais da
fazenda,a mesma deve conter:
• 15% de protéına.
• Um mı́nimo de 8% de fibra.
• No mı́nimo 1100 calorias por quilo de ração e no máximo 2250 calorias por quilo.
Para se fazer a ração, estão dispońıveis 4 ingredientes cujas caracteŕısticas técnico-econômicas
estão mostradas abaixo: (Dados em %, exceto calorias e custos)
Protéına Fibra Calorias/kg Custo/kg
Cevada 6,9 6 1.760 30
Aveia 8,5 11 1.700 48
Soja 9 11 1.056 44
Milho 27,1 14 1.400 56
A ração deve ser feita contendo no mı́nimo 20% de milho e no máximo 12% de soja.
Formule um modelo de P.Linear para o problema.
16) (dos Santos 2000) Uma empresa responsável pelo abastecimento semanal de um certo
produto ao Rio de Janeiro e a São Paulo, pretende estabelecer um plano de distribuição
2.4 Exerćıcios 16
do produto a partir dos centros produtores situados em Belo Horizonte, Ribeirão Preto e
Campos. As quantidades semanalmente dispońıveis em B.Horizonte, R.Preto e Campos são
exatamente 70, 130 e 120 toneladas, respectivamente. O consumo semanal exato deste pro-
duto é de 180 toneladas no Rio e 140 toneladas em S.Paulo. Os custos de transporte, em
$ton, de cada centro produtor para cada centro consumidor está dado abaixo:
Rio São Paulo
B.Horizonte 13 25
R.Preto 25 16
Campos 15 40
Considerando que o objetivo da empresa é minimizar seu custo total de transporte, for-
mule um modelo de P.Linear para o problema.
17) Colocar o problema a seguir na forma padrão:
Maximizar f(x1, x2) = 4x1 + 3x2
2x1 + x2 > 60
2x1 + 3x2 ≥ 120
x1 + x2 > 100
x1 ≥ 0, x2 ≥ 0
18) Escreva o seguinte problema de otimização linear na forma padrão.
Minimizar f(x1, x2, x3) = 2x1 − 3x2 + 3x3
x1 + 2x2 − x3 ≥ 3
−2x1 + x2 + x3 ≤ −1
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
19) Colocar o seguinte problema na forma padrão:
Maximizar f(x1, x2, x3, x4) = 3x1 − x2 + 3x3 − x4
3x1 − 2x2 + x3 − x4 ≥ 5
x2 − x3 + x4 ≤ 7
2x1 + x3 − 2x4 ≥ −5
x1 + 3x4 = 3
x1 ≥ 0, x2 ≥ 0 x3 ≥ 0 x4 ≥ 0
Caṕıtulo 3
Revisão de Álgebra Linear
A finalidade deste caṕıtulo é, essencialmente, revisar alguns conceitos de Álgebra Linear
nos quais se apoiam as técnicas estudadas neste curso.
3.1 Matrizes
Matriz é um conjunto de números reais (ou complexos) dispostos ordenadamente na forma
retangular.
A =





a11 a12 a13 · · · a1n
a21 a22 a23 · · · a2n
...
...
...
...
am1 am2 am3 · · · amn





3.1.1 Matrizes Notáveis
Matriz Nula é a matriz que tem todos os elementos iguais a zero.
Matriz Quadrada é aquela que possui o mesmo número de linhas e colunas.
Matriz Diagonal é a matriz quadrada onde todos os elementos que não pertencem à diagonal
principal são iguais a zero.
Matriz Identidade é a matriz diagonal onde todos os elementos da diagonal são iguais a 1.
Matriz Transposta de uma matriz Amxn é a matriz A
T
nxm que obtem-se trocando as linhas
pelas colunas e vice-versa, isto é: aij = a
t
ji.
Exemplo 3.1 Dada a matriz A:
A2x4 =
[
1 2 −3 4
−1 2 0 7
]
Sua transposta é:
17
3.1 Matrizes 18
At4x2 =




1 −1
2 2
−3 0
4 7




3.1.2 Operações com Matrizes
Sendo I o conjunto das linhas e J o conjunto das colunas de uma dada matriz, tem-se as
seguintes operações:
Igualdade de matrizes :
Amxn = Bmxn ⇔ aij = bij , ∀i ∈ I e ∀j ∈ J
Adição de matrizes :
Amxn +Bmxn = Cmxn ⇔ aij + bij = cij, ∀i ∈ I e ∀j ∈ J
Multiplicação de escalar por matriz : o produto de um escalar k por uma matriz Amxn é a
matriz Bmxn que se obtem multiplicando todos os elementos da matriz Amxn por k.
Multiplicação de matrizes :
AmxnBnxp = Cmxp tal que:
cik = ai1b1k + ai2b2k + ai3b3k + ... + aipbpk =
p∑
j=1
aijbjk ∀i ∈ {1, 2, ..., m} e ∀j ∈ {1, 2, ..., n}
Obs: O produto C=AB somente é definido quando o número de colunas de A é igual ao
número de linhas de B: AmxnBnxp = Cmxp
3.1.3 Propriedades de Adição de Matrizes e de Multiplicação por
Escalar
1. (A+B)+C=A+(B+C) (associativa)
2. A+B=B+A (comutativa)
3. a(A+B)=aA+aB (distributiva)
4. a(bA)=(ab)A
5. A(aB)=(aA)B=a(AB)
6. (a+b)A=aA+bA
7. 1A=A
3.2 Determinante 19
3.1.4 Propriedades de Multiplicação de Matrizes1. A(BC)=(AB)C
2. A(B+C)=AB+AC
3. (A+B)C=AC+BC
4. AI=IA=A (Anxn e Inxn)
3.2 Determinante
A toda matriz quadrada Mnxn, cujos elementos aij sejam números reais (ou complexos),
associa-se, por definição, um único número real (ou complexo) que será denominado o seu
determinante e que se denota por det.M.
Pode-se, portanto, definir uma função determinante, onde det.M pode ser calculado de
forma recursiva, da seguinte maneira:
1. n = 1 ⇒ M = |a11| → det.M = a11
2. n ≥ 2
M =
∣
∣
∣
∣
∣
∣
∣
∣
∣
a11 a12 · · · a1n
a21 a22 · · · a2n
...
...
...
an1 an2 · · · ann
∣
∣
∣
∣
∣
∣
∣
∣
∣
obtem-se o det.M pela fórmula de recorrência
detM =
n∑
i=1
(−1)i+jaij(detDij), j = 1, 2, ..., n
tal que: Dij é a matriz resultante de matriz M eliminando a linha i e a coluna j.
Definição 3.1 Uma matriz é dita não singular se seu determinante for diferente de zero.
Exemplo 3.2 Seja a matriz quadrada:
A =
∣
∣
∣
∣
∣
∣
2 1 4
0 2 1
3 0 5
∣
∣
∣
∣
∣
∣
Seu determinante pode ser calculado da seguinte forma:
detA = (−1)1+1.2. det
∣
∣
∣
∣
2 1
0 5
∣
∣
∣
∣
+ (−1)1+2.1. det
∣
∣
∣
∣
0 1
3 5
∣
∣
∣
∣
+ (−1)1+3.4. det
∣
∣
∣
∣
0 2
3 0
∣
∣
∣
∣
=
3.3 Matriz Inversa 20
=2. det
∣
∣
∣
∣
2 1
0 5
∣
∣
∣
∣
+ (−1) det
∣
∣
∣
∣
0 1
3 5
∣
∣
∣
∣
+ 4. det
∣
∣
∣
∣
0 2
3 0
∣
∣
∣
∣
Também
det
∣
∣
∣
∣
2 1
0 5
∣
∣
∣
∣
= (−1)1+12 det |5|+ (−1)1+21 det |0| = 2(5) + 0 = 10
det
∣
∣
∣
∣
0 1
3 5
∣
∣
∣
∣
= (−1)1+10 det |5|+ (−1)1+21 det |3| = 0 + (−1)3 = −3
det
∣
∣
∣
∣
0 2
3 0
∣
∣
∣
∣
= (−1)1+10 det |0|+ (−1)1+22 det |3| = 0 + (−1)6 = −6
Logo, detM = 2(10) + (−1)(−3) + 4(−6) = −1
3.3 Matriz Inversa
Seja A uma matriz quadrada de ordem n. A é inverśıvel (invert́ıvel) se, e somente se,
existir uma matriz A−1, denominada inversa de A, tal que AA−1 = I = A−1A.
Sejam A e B matrizes inverśıveis de mesma ordem, então:
1. (A−1)−1 = A
2. (AB)−1 = B−1A−1
Teorema 3.1 A inversa A−1 de uma matriz A, quando existir, é única.
Teorema 3.2 Uma matriz quadrada A será inverśıvel se, e somente se, A for não singular.
Método prático para a determinação da inversa de uma matriz
Se A for uma matriz inverśıvel e se uma seqüência de operações elementares sobre as
linhas reduzir A à matriz identidade I, então aquela mesma seqüência de operações sobre as
linhas, quando aplicadas a I, produzirá a matriz A−1.
Exemplo 3.3 Determinar a inversa da matriz:
A =


1 2 3
0 1 0
1 0 2


Solução:
A
...I =


1 2 3
0 1 0
1 0 2
∣
∣
∣
∣
∣
∣
1 0 0
0 1 0
0 0 1


L3 → L3 − L1
3.4 Espaços Vetoriais 21


1 2 3
0 1 0
0 −2 −1
∣
∣
∣
∣
∣
∣
1 0 0
0 1 0
−1 0 1


L1 → L1 − 2L2
L3 → L3 + 2L2


1 0 3
0 1 0
0 0 −1
∣
∣
∣
∣
∣
∣
1 −2 0
0 1 0
−1 2 1


L3 → (−1)L3


1 0 3
0 1 0
0 0 1
∣
∣
∣
∣
∣
∣
1 −2 0
0 1 0
1 −2 −1


L1 → L1 − 3L3


1 0 0
0 1 0
0 0 1
∣
∣
∣
∣
∣
∣
−2 4 3
0 1 0
1 −2 −1

 =
[
I
... A−1
]
Logo:
A−1 =


−2 4 3
0 1 0
1 −2 −1


Verificação:
AA−1 =


1 2 3
0 1 0
1 0 2




−2 4 3
0 1 0
1 −2 −1

 =


1 0 0
0 1 0
0 0 1


Exerćıcio 3.1 Determinar a inversa da matriz A.
A =


1 2 3
3 1 −1
0 4 2


3.4 Espaços Vetoriais
Definição 3.2 Vetor é uma n-upla ordenada da forma x = (x1, x2, ..., xn). Um vetor do
tipo (0,0,...,0) é denominado vetor nulo e pode ser representado por ~0 ou simplesmente por
0.
Um vetor pode ser considerado como uma matriz com uma linha (1 x n) ou com uma
coluna (n x 1 ). Tais vetores são chamados vetor-linha e vetor-coluna, respectivamente.
3.4 Espaços Vetoriais 22
Definição 3.3 Um conjunto V de vetores, tal que a soma de quaisquer dois vetores V e
o produto de um vetor qualquer de V por um escalar qualquer k também pertença a V, é
chamado de espaço vetorial. Isto é, V é um espaço vetorial se:
i ∀v1, v2 ∈ V , (v1 + v2) ∈ V
ii ∀v1 ∈ V, ∀k ∈ R, (kv1 ∈ V )
O conjunto de todos os vetores da forma x = (x1, x2, ..., xn), tal que x1, x2, ..., xn ∈ R, levando
em consideração que satisfazem as propriedades definidas anteriormente, constitui o espaço
vetorial Rn.
Definição 3.4 Subespaço Vetorial de um espaço vetorial V é um subconjunto de V que é
um espaço vetorial.
Exemplo 3.4 Seja o espaço vetorial R3.
O conjunto {(x, y, 0)|x ∈ R e y ∈ R} é um subespaço vetorial do R3 porque é um subconjunto
do R3 (plano que contém os eixos x e y) e também é espaço vetorial.
3.4.1 Combinação Linear
Seja V um espaço vetorial e sejam {v1, v2, v3, ..., vm} ∈ V . Qualquer vetor da forma
k1v
1+ k2v
2+ k3v
3 + ...+ kmv
m, ou seja,
m∑
i=1
kiv
i, tal que ki ∈ R, ∀i ∈ {1, 2, ..., m}, é chamado
de combinação linear dos vetores vi, i = 1, 2, ..., m.
Exemplo 3.5 O vetor (-7,7,23) é combinação linear dos vetores (1,2,4) e (-3,1,5), pois
(-7,7,23) = 2(1,2,4) + 3(-3,1,5).
Definição 3.5 Um conjunto de vetores v1, v2, v3, ..., vm será linearmente independente (LI),
se, e somente se:
m∑
i=1
kiv
i = ~0→ ki = 0 (∀i ∈ {1, 2, ..., m})
Caso contrário será linearmente dependente (LD).
Exemplo 3.6 Os vetores v1 = (2, 2, 3), v2 = (3, 2, 5) e v3 = (12, 10, 19) são LD, pois:
3v1 + 2v2 − v3 = 3(2, 2, 3) + 2(3, 2, 5)− (12, 10, 19) = (0, 0, 0) = ~0.
Os vetores v1 = (1, 0, 3), v2 = (0, 1, 0) e v3 = (3, 1, 0) são LI, pois:
k1v
1 + k2v
2 + k3v
3 = ~0→ k1(1, 0, 3) + k2(0, 1, 0) + k3(3, 1, 0) = (0, 0, 0)→
→ (k1, 0, 3k1) + (0, k2, 0) + (3k3, k3, 0) = (0, 0, 0)→ (k1 + 3k3, k2 + k3, 3k1) = (0, 0, 0)→
→



k1 + 3k3 = 0
k2 + k3 = 0
3k1 = 0
→



k1 = 0
k2 = 0
k3 = 0
3.5 Sistemas Lineares 23
Teorema 3.3 Um conjunto finito de n vetores, n ≥ 2, é linearmente dependente se, e
somente se, um dos vetores do conjunto for combinação linear dos outros vetores do conjunto.
Definição 3.6 Posto (ou caracteŕıstica ou rank) de uma matriz A é o número máximo de
linhas ou colunas LI.
Exemplo 3.7 O posto da matriz A, abaixo, é igual a 2.
A =


1 0 3 4
2 1 0 3
4 1 6 11


Teorema 3.4 Se A é uma matriz quadrada n x n, então as seguintes afirmações são equi-
valentes:
i ∃ a inversa A−1;
ii A é não singular; e
iii Posto(A)=n.
Definição 3.7 Um conjunto de vetores {v1, v2, ..., vm} pertencentes a um espaço vetorial V
é uma base para V se:
i {v1, v2, ..., vm} é LI; e
ii ∀v′ ∈ V for obtido como combinação linear dos vi (i = 1, 2, ..., m), isto é, existem ki ∈
R (i = 1, 2, ..., m) tais que:
v′ = k1v
1 + k2v
2 + ... + kmv
m =
m∑
i=1
kiv
i
3.5 Sistemas Lineares
Definição 3.8 Chama-se equação ou igualdade linear a toda equação da forma F (x) = b,
tal que F (x) é um funcional linear e b ∈ R. Toda equação linear pode ser escrita na forma:
k1x1 + k2x2 + ...+ knxn = k0
tal que xi são as variáveis, ki os coeficientes das variáveis e k0 o termo independente.
Atribuindo valores às variáveis de modo a satisfazer a equação, obtém-se uma solução da
equação.
Da mesma forma como define-se igualdade, pode-se definir desigualdade ou inequação
linear como uma desigualdade da forma F (x) ≥ ou ≤ b, tal que F (x) é um funcional linear
e b ∈ R.
3.5 Sistemas Lineares 24
Definição 3.9 Ao conjunto de m equações lineares com n incógnitas:



a11x11 + a12x12 + · · · + a1nx1n = b1
a21x21 + a22x22 + · · · + a2nxn = b2
...
...
...
...
am1xm1 + am2xm2 + · · · + amnxmn = bm
denomina-se sistema de equações lineares.
Uma solução de um sistema de m equações lineares com n incógnitas é uma n-upla orde-
nada da forma (x′1, x
′
2, ..., x
′
n) tal que verifica as m equações simultaneamente.
3.5.1 Notação Matricial
Considere o sistema da Definição 3.9 de m equações lineares e n incógnitas.
Este pode ser escrito da seguinte forma:
A =





a11 a12 · · · a1n
a21 a22 · · · a2n
...
...
...
am1 am2 · · · amn





, x =





x1
x2
...
xn





e b =





b1
b2
...
bm





→ Ax = b
Definição 3.10 Um sistema de m equações lineares com n incógnitas pode ser classificado,
quanto ao número de soluções, em trêscasos:
a) Compat́ıvel determinado: quando admite uma única solução.
b) Compat́ıvel indeterminado: quando admite mais de uma solução.
c) Incompat́ıvel: quando não admite solução.
3.5.2 Resolução de Sistemas de Equações Lineares
Nesta seção é apresentado o método de Gauss-Jordan para resolução de sistemas de equa-
ções lineares.
Seja o sistema Ax=b, tal que A é uma matriz m x n. Como em toda matriz retangular
existe uma submatriz quadrada, não singular B, de ordem m. O sistema Ax=b pode, então,
ser escrito na forma:
BxB +RxR = b
A submatriz B é denominada base. As componentes de x relativas às colunas B e R, isto é,
as componentes relativas a xB e xR são denominadas, respectivamente, variáveis básicas e
variáveis não básicas.
3.5 Sistemas Lineares 25
Como B é não singular, existe a inversa B−1. Logo o sistema pode ser escrito da forma:
xB +B−1RxR = B−1b⇒ xB = B−1(b− RxR)
Exemplo 3.8 Seja o sistema:



x1 − 2x2 + 5x3 + 3x4 − 4x5 = 2
2x1 − 4x2 + 5x3 + 6x4 + 2x5 = −6
2x1 − 5x2 + 7x3 + 7x4 + 3x5 = −7
Resolvendo este sistema, tem-se:
x1 x2 x3 x4 x5
1 -2 5 3 -4 2
2 -4 5 6 2 -6
2 -5 7 7 3 -7
B R b
Fazendo L2 → L2 − 2L1 e L3 → L3 − 2L1, tem-se:
1 -2 5 3 -4 2
0 0 -5 0 10 -10
0 -1 -3 1 11 -11
Fazendo L2 ↔ L3, tem-se:
1 -2 5 3 -4 2
0 -1 -3 1 11 -11
0 0 -5 0 10 -10
Fazendo L1 → L1 − 2L2 e L2 → −L2, tem-se:
1 0 11 1 -26 24
0 1 3 -1 -11 11
0 0 -5 0 10 -10
Fazendo L1 → L1 +
11
5
L3, L2 → L2 +
3
5
L3 e L3 →
1
−5
L3, tem-se:
x1 x2 x3 x4 x5
1 0 0 1 -4 2
0 1 0 -1 -5 5
0 0 1 0 -2 2
I B−1R B−1b
Pode-se então escrever:
3.6 Considerações Finais 26
x1 = 2 − x4 + 4x5
x2 = 5 + x4 + 5x5
x3 = 2 + 2x5
o que implica na solução do sistema de equações.
Exerćıcio 3.2 Resolva o sistema abaixo usando Gauss-Jordan.



2x1 + x2 − x3 = 1
3x1 + 2x2 + x3 = 10
x1 + x2 − 2x3 = −3
Na literatura há diversos métodos para se resolver sistemas lineares, desde métodos di-
retos até métodos iterativos (aproximados). Os métodos computacionais mais utilizados são
Eliminação de Gauss e Fatoração LU.
Exerćıcio 3.3 Resolva o sistema abaixo usando o Método de Eliminação de Gauss.



2x1 + x2 − x3 = 1
3x1 + 2x2 + x3 = 10
x1 + x2 − 2x3 = −3
3.6 Considerações Finais
Neste caṕıtulo foi feita uma revisão geral das principais definições/métodos de Álgebra
Linear que são utilizados em Programação Linear, Inteira e Dinâmica.
3.7 Exerćıcios
1)Dadas as seguintes matrizes:
A =
[
1 2
3 4
]
e B =
[
5 7
6 8
]
Efetue os produtos AB e BA e mostre que são diferentes.
2) Calcule o produto das seguintes matrizes:
A =
[
−8 4 −6 1
2 −5 7 3
]
e B =




0 4
2 −2
1 −5
3 8




3) Dadas as matrizes:
3.7 Exerćıcios 27
A =


−1 −1 0
0 −1 −1
1 −1 −3

 e B =


−2 3 −1
1 −3 1
−1 2 −1


verificar se B é inversa de A.
4) Dadas as seguintes matrizes:
A =




5 0 6
−8 0 3
−2 2 7
1 −1 −5




e B =


1 −3 −2 4
7 8 5 9
0 6 3 −8


Calcule (AB)T .
5) Mostre que o determinante da seguinte matriz A é -55.
A =




−2 −3 −1 −2
−1 0 1 −2
−3 −1 −4 1
−2 2 −3 −1




6) Determine a inversa da seguinte matriz:
A =


2 1 3
4 2 2
2 5 3


7) Mostre que a seguinte matriz é não-singular:
A =


−2 3 −1
1 −3 1
−1 2 −1


8) Resolva o seguinte sistema de equações lineares, utilizando o Método de Eliminação de
Gauss (dúvidas, vide Ruggiero e Lopes (1996))



2x + 4y − 6z = 10
4x + 2y + 2z = 16
2x + 8y − 4z = 24
9) Responda:
• O que é um sistema linear homogêneo?
• O que é uma matriz triangular inferior?
• Na resolução de um sistema linear de equações 3 x 3, quais são os pivôs da matriz na
resolução utilizando o método de Gauss-Jordan?
3.7 Exerćıcios 28
10) Se duas matrizes A e B comutam, isto é, AB=BA, mostrar que:
• (A+B)(A− B) = A2 −B2
• (A−B)(A2 + AB +B2) = A3 − B3
11) Resolva o seguinte sistema de equações lineares:



2x + 4y = 16
5x − 2y = 4
10x − 4y = 3
Caṕıtulo 4
Programação Linear: Solução Gráfica
Quando um problema de Programação Linear, PL, envolver apenas duas variáveis de
decisão, a solução ótima deste pode ser visualizada e resolvida graficamente. Esta visão
geométrica permite introduzir vários resultados válidos para problemas gerais. Logo, neste
caṕıtulo é abordado o Problema de PL por meio da solução gráfica, sendo baseado nos livros
de Arenales et al. (Arenales et al. 2007) e Lachtermacher (Lachtermacher 2009).
4.1 Resolução Gráfica
Por conveniência, será considerado o problema na forma de desigualdades:
min f(x) = ctx
sujeito a : Ax ≤ b
x ≥ 0 x ∈ R2
(4.1)
Inicialmente é representada a região de factibilidade, ou seja, o conjunto de todas as
soluções fact́ıveis, que será denotado por:
S = {x ∈ Rn tal que Ax ≤ b, x ≥ 0} (4.2)
Destaca-se que uma solução fact́ıvel x é uma solução que satisfaz todas as restrições
simultaneamente e, portanto, a região de factibilidade é a intersecção das regiões formadas
por cada restrição em particular.
As restrições x1 ≥ 0 e x2 ≥ 0 (condições de não-negatividade) informam que as soluções
fact́ıveis devem estar no primeiro quadrante formado pelo sistema de coordenadas.
Para representar a restrição aix = b (ou ai1x1 + ai2x2 = bi), o espaço R
2 é dividido em
três partes:
a) x ∈ R2/aix = bi
b) x ∈ R2/aix < bi
29
4.1 Resolução Gráfica 30
c) x ∈ R2/aix > bi
O conjunto de pontos que satisfaz as restrições aix ≤ bi é a reunião definida em a) e b).
Ao se traçar a reta aix = bi a região a) fica representada, dividindo o plano em dois
semi-planos. Resta decidir qual dos dois semi-planos resultantes representa a região b). Para
isto, nota-se que a reta aix = bi pode ser vista como uma curva de ńıvel da seguinte função
linear:
g(x) = aix, (4.3)
ou seja, a reta do conjunto {x ∈ R2/g(x) = bi}.
Considere agora um ponto x sobre a reta: g(x) = bi e um novo ponto dado por:
x′ = x+ ǫ(ai)T , ǫ > 0 (4.4)
(x′ é chamado uma perturbação de x na direção de (ai)T ) satisfaz:
g(x′) = g(x+ ǫ(ai)T ) = g(x) + ǫ ‖ ai ‖2> g(x) = bi (4.5)
(supondo ai 6= 0, ‖ ai ‖=
√
ai(ai)T > 0 é a norma euclediana de ai). Portanto x′ está na
região c).
A desigualdade 4.5 mostra que o gradiente (transposto) ∇g(x) = ai, indica uma direção
de subida, uma vez que o ponto x′ atribui valor maior à função g que x.
Assim, traça-se a reta aix = bi e desenha-se o vetor a
i e tem-se bem definido as três
regiões, conforme ilustra a Figura 4.1.
aix < bi
aix > bi
x1
x2
ai
aix = bi
Figura 4.1: Representação gráfica
A região de factibilidade, que é a reunião de várias regiões do tipo aix ≤ bi pode agora
ser facilmente traçada (Figura 4.2).
De forma análoga, pode-se determinar a solução ótima notando que a curva de ńıvel:
cTx = f̂ (f̂ constante) (4.6)
(ou seja, a equação da reta: c1x1 + c2x2 = f̂) representa pontos que atribuem o mesmo valor
f̂ à função objetivo.
4.1 Resolução Gráfica 31
a3
a2
x1
x2
a1
Figura 4.2: Região de Factibilidade
Resolver um problema de otimização linear consiste em encontrar pontos na região de
factibilidade que atribuam o menor valor a f(x) = cTx. Isto equivale em determinar o menor
valor f̂ tal que a curva de ńıvel {x ∈ R2 tal que f(x) = f̂} tenha intersecção com a região
de factibilidade. Os pontos nesta intersecção são soluções ótimas.
Como o vetor gradiente de f, c, é perpendicular às curvas de ńıvel f(x) = f̂ e indica o
sentido em que f cresce, deve-se traçar retas perpendiculares ao vetor c, deslocando-as no
sentido oposto ao indicado pelo vetor c.
c
cT = f 1
x1
x2
cT = f 2
cT = f ∗
x∗
Figura 4.3: Curvas de ńıvel da função objetivo (f ∗(x) = minf(x) = cTx tal que x ∈ R2)
A solução ótima x∗ da Figura 4.3 é uma solução fact́ıvel muito especial chamada vértice ou
ponto extremo. Para o exemplo na Figura 4.2, percebe-se que os vértices são determinados
pela intersecção de duasretas que definem a fronteira da região de factibilidade (observe
que xi = 0 é uma equação de reta). Desta forma, vértices podem ser obtidos resolvendo-se
sistemas de equações lineares.
Deve-se observar que se o gradiente da função objetivo for modificado, outro vértice pode
ser uma solução, de modo a sugerir o seguinte:
”́e suficiente procurar uma solução ótima entre os vértices da região de factibili-
dade”.
Esta afirmação é verdadeira e consiste num teorema fundamental da otimização linear
que usualmente é enunciado da seguinte maneira:
4.1 Resolução Gráfica 32
Teorema 4.1 Se um problema de otimização linear tem solução ótima, então existe um
vértice ótimo.
OBS: Deve-se ficar atento à seguinte afirmação falsa: se uma solução for ótima, então ela é
um vértice.
Exerćıcio 4.1 Dê um contra exemplo da observação anterior.
O problema representado na Figura 4.4 tem a região de factibilidade ilimitada e apresenta
uma única solução ótima.
c
x1
x2
x∗
Figura 4.4: Região de factibilidade ilimitada e solução ótima única
O problema representado na Figura 4.5 possui infinitas soluções ótimas.
cc
x1
x1
x2x2
x∗x
∗
Figura 4.5: Infinitas soluções ótimas - conjunto limitado de soluções ótimas, conjunto ilimi-
tado de soluções ótimas
.
O problema da Figura 4.6 não possui solução ótima.
c
x1
x2
Figura 4.6: Não existe solução ótima
.
4.1 Resolução Gráfica 33
x∗
x1
x2
Figura 4.7: Solução ótima degenerada
.
A Figura 4.7 mostra uma solução onde o mesmo vértice pode ser obtido como intersecção
de retas diferentes. Esta situação produz um vértice que chamamos de vértice degenerado.
As diversas possibilidades observadas graficamente são posśıveis em problemas de dimen-
sões maiores, os quais não são posśıveis interpretações gráficas.
Exemplo 4.1 Seja o seguinte problema de programação linear com duas variáveis:
max f(x1, x2) = 2x1 + x2
sujeito a : −x1 + 2x2 ≤ 4
3x1 + 5x2 ≤ 15
2x1 − 3x2 ≤ 6
x1 ≥ 0 x2 ≥ 0
(4.7)
Como determinar qual (ou quais) o(s) ponto(s) que pertence(m) ao conjunto fact́ıvel e
que ao mesmo tempo fornece(m) o MAIOR valor para a função objetivo f(x1, x2) = 2x1+x2.
A Figura 4.8 representa a região de factibilidade deste problema.
Como a função objetivo representa uma famı́lia de retas paralelas, basta tomar uma qual-
quer e verificar a relação existente entre a reta e o valor f(x1, x2) correspondente. Fazendo
f(x1, x2) = 6, tem-se a reta 2x1 + x2 = 6, que está tracejada na respectiva figura. É verifi-
cado que ao deslocar a reta, paralelamente a si mesma, para a direita, isto na verdade implica
em fazer crescer o valor de f(x1, x2). Como o problema em questão consiste em procurar
o ponto pertencente ao conjunto fact́ıvel, este ponto é determinado tangenciando o conjunto
das soluções fact́ıveis à direita pela função objetivo.
Portanto, a solução ÓTIMA é:
x1 = 75/19 e x2 = 12/19
MÁX f(x1, x2) = 2.
75
19
+ 1.12
19
→ MÁXf(x1, x2) =
162
19
.
4.1 Resolução Gráfica 34
2x1 + x2 = 6
x1
x2
2x1 − 3x2 = 6
−x1 + 2x2 = 4
3x1 + 5x2 = 15
decresce cresce
região
factibilidade
x∗
Figura 4.8: Região de factibilidade
.
Exerćıcio 4.2 Considere o seguinte problema de otimização linear:
max f(x1, x2) = x1 + 2x2
sujeito a : −x1 + 2x2 ≤ 2
x1 + x2 ≤ 6
x1 ≥ 0 x2 ≥ 0
(4.8)
a) Represente graficamente a região de factibilidade e determine a solução ótima.
b) Coloque o problema no formato padrão (restrições de igualdades).
c) Determine o valor numérico dos vértices e o valor da função objetivo avaliada em cada
vértice.
d) Determine graficamente o conjunto das soluções ótimas quando f(x1, x2) = x1 + x2. Dê
numericamente uma solução ótima que não seja um vértice.
Solução:
a) Representação gráfica (Figura 4.9).
O vértice ótimo é: x∗ = (10
3
, 8
3
) e a solução ótima é S = 26
3
.
4.1 Resolução Gráfica 35
x1 + x2 = 6
−x1 + 2x2 = 2x∗
Figura 4.9: Região de factibilidade
.
b) Forma padrão:
max f(x1, x2) = x1 + 2x2
sujeito a : −x1 + 2x2 ≤ 2
x1 + x2 ≤ 6
x1 ≥ 0 x2 ≥ 0
(4.9)
min f(x1, x2) = −x1 − 2x2 + 0x3 + 0x4
sujeito a : −x1 + 2x2 + x3 = 2
x1 + x2 + x4 = 6
x1 ≥ 0 x2 ≥ 0 x3 ≥ 0 x4 ≥ 0
(4.10)
A =
(
−1 2 1 0
1 1 0 1
)
, c =




−1
−2
0
0




, b =
(
2
6
)
e x =




x1
x2
x3
x4




.
c) Valores numéricos dos vértices.
Os vértices são:
v1 = (0, 0) e f(v1) = 0, v2 = (0, 1) e f(v2) = 2, v3 = (6, 0) e f(v3) = 6
v4 = (
10
3
, 8
3
) e f(v4) =
26
3
d) Solução: S = {(x1, x2) ∈ R
2/x1 + x2 = 6 com x1 ∈ [
10
3
, 6] e x2 ∈ [0,
8
3
]}
4.2 Exerćıcios de Fixação 36
4.2 Exerćıcios de Fixação
Exerćıcio 4.3 Resolva graficamente o seguinte problema:
Max Z = 5x1 + 2x2
s.a : x1 ≤ 3
x2 ≤ 4
x1 + 2x2 ≤ 9
x1, x2 ≥ 0
Exerćıcio 4.4 Resolva graficamente o seguinte problema:
Min Z = −7x1 − 9x2
s.a : − x1 + x2 ≤ 2
x1 ≤ 5
x2 ≤ 6
3x1 + 5x2 ≥ 15
5x1 + 4x2 ≥ 20
x1, x2 ≥ 0
Exerćıcio 4.5 Uma fábrica produz dois produtos, A e B. Cada um deles deve ser processado
por duas máquinas, M1 e M2. Devido à programação de outros produtos, que também utilizam
estas máquinas, a máquina M1 tem 24 horas de tempo dispońıvel para os produtos A e B,
enquanto que a máquina M2 tem 16 horas de tempo dispońıvel. Para produzir uma unidade
do produto A, gastam-se 4 horas em cada uma das máquinas M1 e M2. Para produzir uma
unidade do produto B, gastam-se 6 horas na máquina M1 e 2 horas na máquina M2. Cada
unidade vendida do produto A gera um lucro de R$80 e cada unidade do produto B, um lucro
de R$60. Existe uma previsão máxima de demanda para o produto B de 3 unidades, não
havendo restrições quanto à demanda do produto A. Deseja-se saber quantas unidades de A
e de B devem ser produzidas, de forma a maximizar o lucro e, ao mesmo tempo, obedecer a
todas as restrições desse enunciado.
4.3 Considerações Finais
Neste caṕıtulo foram introduzidos alguns conceitos de programação linear, por meio da
resolução gráfica, que auxiliarão no caṕıtulo seguinte.
4.4 Exerćıcios
1) Resolver graficamente:
Maximizar f(x, y) = 3x+ y
2x+ y ≤ 30
x+ 4y ≤ 40
x ≥ 0, y ≥ 0
4.4 Exerćıcios 37
2) Resolva graficamente o modelo a seguir:
max z = 3x1 + 5x2
s.a : x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
x1, x2 ≥ 0
Indique o espaço solução (hachurando), o ponto ótimo (apontando) e a solução ótima.
3) Resolva graficamente o modelo a seguir:
Min Z = −4x1 − 2x2
s.a : 1x1 + 1x2 ≤ 8
8x1 + 3x2 ≥ −24
−6x1 + 8x2 ≤ 48
3x1 + 5x2 ≤ 15
x1 ≤ 3
x2 ≥ 0
Indique o espaço solução (hachurando), o ponto ótimo (apontando) e as restrições redundan-
tes (pelo número).
4) Considere o problema de otimização linear:
Maximizar f(x1, x2) = x1 + x2
−3x1 + x2 ≤ 2
x1 + 2x2 ≤ 9
3x1 + x2 ≤ 18
x2 ≤ 3
x1 ≥ 0, x2 ≥ 0
Resolva-o graficamente, encontre a solução ótima e informe a partição ótima (vaŕıaveis bási-
cas e não-básicas).
5) Resolver graficamente:
Minimizar f(x1, x2) = 2x1 + 4x2
5x1 + 5x2 ≥ 25
2x1 + 6x2 ≥ 18
x1 ≥ 2
x1 ≥ 0, x2 ≥ 0
6) Na fabricação de dois produtos, X e Y, as seguintes restrições são válidas quanto aos dois
recursos escassos que são utilizados:
4.4 Exerćıcios 38
x+ 2y ≤ 8
2x+ 2y ≤ 12, onde
x = número de unidades produzidas do produto X
y = número de unidades produzidas do produto Y
Sabe-se também que cada unidade do produto X fornece um lucro de R$2,00 e cada
unidade do produto Y leva um lucro de R$30,00. Pede-se:
a) formular o modelo de programação linear apropriado, visando maximizar o lucro;
b) resolver o problema graficamente.
7) Em uma fábrica, existem três recursos em quantidades limitadas, os quais impõem limites
às quantidades que podem ser produzidas de dois produtos, A e B. Existem 1.200 unidades
dispońıveis do recurso 1, 400 unidades dispońıveis do recurso 2 e 80 unidades dispońıveis
do recurso 3. Por outro lado, o produto A proporciona um lucro unitário de R$100, contra
R$300 do produtoB. Sabe-se também que 1 unidade do produto A requer:
• 20 unidades do recurso 1
• 4 unidades do recurso 2
• nenhuma unidade do recurso 3
1 unidade do produto B requer:
• 20 unidades do recurso 1
• 20 unidades do recurso 2
• 4 unidades do recurso 3
Pede-se:
a) formular o problema; e
b) resolvê-lo graficamente.
8) Na fabricação de seus produtos, uma empresa utiliza dois equipamentos que limitam a
produção. Em um dado peŕıodo de tempo, estão dispońıveis 30 horas do equipamento 1 e 80
horas do equipamento 2. Para a fabricação de uma unidade do produto A usa-se 1 hora do
equipamento 1 e 2 horas do equipamento 2. Já para uma unidade do B são gastas 2 horas
do equipamento 2. O equipamento 1 não toma parte na produção do B. Por outro lado, um
unidade do produto A leva um lucro de R$150, enquanto cada unidade do produto B gera
um lucro de R$50. Pede-se:
4.4 Exerćıcios 39
a) colocar o problema como um modelo de programação linear visando maximizar o lucro; e
b) resolvê-lo graficamente.
9) Na formulação de um problema de programação linear, a função objetivo a ser maximizada
é 2x+y. Além das condições de não-negatividade, existe uma só restrição:
x+ y = 4 Pede-se:
a) fazer um gráfico da restrição;
b) à medida que se move a reta da função objetivo a partir da origem, determinar a primeira
solução posśıvel encontrada e a última;
c) determinar qual é a melhor solução (obtida graficamente).
10) (Taha 2008) A Reddy Mikks produz tintas para interiores e exteriores com base em duas
matérias-primas, M1 e M2. A tabela a seguir apresenta os dados básicos do problema:
Tintas para Tintas para Disponibilidade
exteriores Interiores máxima diária (ton)
matéria-prima M1 6 4 24
matéria-prima M2 1 2 6
Lucro por ton ($1.000) 5 4
Uma pesquisa de mercado indica que a demanda diária de tintas para interiores não
pode ultrapassar a de tintas para exteriores por mais de 1 tonelada. Além disso, a demanda
máxima diária de tinta para interiores é 2t.
A Reddy Mikks quer determinar o mix ótimo (o melhor) de produtos de tintas para
interiores e exteriores que maximize o lucro total diário. Formule o problema e resolva-o
graficamente.
Caṕıtulo 5
Programação Linear: Teoria Básica e
o Método Simplex
Este caṕıtulo é baseado em Arenales et al. (2007), sendo apresentadas algumas definições
e propriedades fundamentais da otimização linear e um de seus métodos mais importantes,
o Método Simplex.
Por conveniência, a teoria desenvolvida para o problema é considerada na forma padrão:
Minimizar f(x) = cTx
Ax = b
x ≥ 0
(5.1)
Embora os exemplos ilustrados neste caṕıtulo tenham as restrições na forma de desi-
gualdades, os desenvolvimentos nas seções seguintes utilizam a forma padrão (problema de
minimização com restrições de igualdade e não negatividade sobre as variáveis).
5.1 Soluções básicas
Nesta seção são formalizadas algumas propriedades já intúıdas no caṕıtulo anterior (re-
solução gráfica). Inicialmente é considerado um exemplo simples, tal que a região fact́ıvel
S ⊂ R2 é definida pelo conjunto de restrições descrito na Equação 5.2 e ilustrada na Figura
5.1.
x1 + x2 ≤ 6
x1 − x2 ≤ 4
3x1 + x2 ≥ 3
x1 ≥ 0, x2 ≥ 0
(5.2)
Com a definição das variáveis de folga e excesso tem-se:
x3 = 6− (x1 + x2) ≥ 0
x4 = 4− (x1 − x2) ≥ 0
x5 = −3 + (3x1 + x2) ≥ 0,
(5.3)
40
5.1 Soluções básicas 41
o problema é transformado na forma de igualdade (Ax = b, x ≥ 0):
x1 + x2 + x3 = 6
x1 − x2 + x4 = 4
3x1 + x2 − x5 = 3
x1 ≥ 0 x2 ≥ 0 x3 ≥ 0 x4 ≥ 0 x5 ≥ 0
(5.4)
O problema passa a ter cinco variáveis (x1, x2, x3, x4, x5), em vez de apenas duas. Qual-
quer ponto em R2 determina unicamente essas cinco variáveis, conforme Equação 5.4, ou seja,
dado o par (x1, x2), pode-se determinar unicamente os valores de x3, x4 e x5. Analisando
alguns exemplos numéricos, Figura 5.1-pontos A, B, C, D, E, F, tem-se:
Ponto A Ponto B
x1 = 3 x1 = 1
x2 = 2 x2 = 3
x3 = 6− (3 + 2) = 1 x3 = 6− (1 + 3) = 2
x4 = 4− (3− 2) = 3 x4 = 4− (1− 3) = 6
x5 = (3(3) + 2)− 3 = 8 x5 = (3(1) + 2)− 3 = 3
Ponto C Ponto D
x1 = 2 x1 = 5
x2 = 4 x2 = 1
x3 = 6− (2 + 4) = 0 x3 = 6− (5 + 1) = 0
x4 = 4− (2− 4) = 6 x4 = 4− (5− 1) = 0
x5 = (3(2) + 2)− 3 = 7 x5 = (3(5) + 1)− 3 = 13
B
A
D
E
F
C
x1 + x2 = 6⇔ x3 = 0
x1 − x2 = 4⇔ x4 = 0
x1
x2
3x1 + x2 = 3⇔ x5 = 0
Figura 5.1: Região fact́ıvel
5.1 Soluções básicas 42
Tais soluções são fact́ıveis, pois o sistema Ax=b é satisfeito por construção, além de
respeitarem as condições de não-negatividade.
Lembre-se de que as soluções do sistema Ax=b têm 5 coordenadas x = (x1, x2, x3, x4, x5),
porém, somente as duas primeiras (x1, x2) são visualizadas na Figura 5.1, enquanto as demais
(x3, x4, x5) medem as folgas/excessos em cada restrição. Assim os pontos A e B estão no
interior da região fact́ıvel, pois têm todas as coordenadas positivas, ou seja, todas as restrições
estão folgadas. Por exemplo, no ponto A, x1 + x2 < 6, portanto, x3 > 0 (isto é, a Restrição
1 é folgada no Ponto A). Por outro lado, os Pontos C e D estão sobre a fronteira de S,
pois alguma variável se anula. Por exemplo, no Ponto C, x1 + x2 = 6, portanto, x3 = 0 (a
Restrição 1 é ativa no Ponto C, isto é, tem folga nula).
Examinando agora os Pontos E e F, que não pertencem à região fact́ıvel (Figura 5.1),
verifica-se como esta infactibilidade pode ser detectada sem o aux́ılio da figura.
Ponto E Ponto F
x1 = 4 x1 = 6
x2 = 5 x2 = 0
x3 = 6− (4 + 5) = −3 x3 = 6− (6 + 0) = 0
x4 = 4− (4− 5) = 5 x4 = 4− (6− 0) = −2
x5 = (3(4) + 5)− 3 = 14 x5 = (3(6) + 0)− 3 = 15
Apesar dos Pontos E e F satisfazerem o sistema Ax=b eles não são soluções fact́ıveis,
pois violam uma das condições de não-negatividade.
Na resolução gráfica de um problema de otimização linear pode-se intuir que, para encon-
trar uma solução ótima, basta procurar entre os vértices da região fact́ıvel S. Tais soluções
em R2 são determinadas pela intersecção de duas retas, o que significa que duas variáveis são
nulas. Por exemplo, o Ponto D na Figura 5.1 é caracterizado por:
Fixar
{
x3 = 0
x4 = 0
resulta no sistema :



x1 + x2 = 6
x1 − x2 = 4
3x1 + x2 − x5 = 3
, obtendo o resultado :



x1 = 5
x2 = 1
x5 = 13
(5.5)
Isso mostra uma maneira de se obter soluções para o sistema Ax=b. O referido sistema
tem m = 3 equações e n = 5 variáveis, portanto tem duas variáveis independentes, para os
quais se pode atribuir quaisquer valores. Este sistema pode ser resolvido utilizando o Método
de Gauss ou qualquer outro da literatura.
Por exemplo, a solução obtida ao se fixar x3 = 0 e x4 = 0 é dada por x = (x1, x2, x3, x4, x5) =
(5, 1, 0, 0, 13) e, como já comentado anteriormente, é uma solução fact́ıvel. Porém, ao se fixar
duas variáveis quaisquer em zero, não há garantias de que será obtida uma solução fact́ıvel.
Por exemplo,
5.1 Soluções básicas 43
Fixar
{
x2 = 0
x3 = 0
resulta no sistema :



x1 = 6
x1 + x4 = 4
3x1 − x5 = 3
, com resultado :



x1 = 6
x4 = −2
x5 = 15.
(5.6)
Deve ficar claro que, assim procedendo, o sistema Ax=b é satisfeito por construção,
porém não necessariamente as condições de não-negatividade são verificadas. Este procedi-
mento de obtenção de soluções pode ser estendido para quaisquer sistemas Ax=b, m x n.
Por simplicidade de notação, rearranjando o sistema de forma a agrupar as n-m variáveis
independentes que devem ser fixadas e as m variáveis restantes. Por exemplo, suponha que
as variáveis x3 e x4 sejam escolhidas para serem fixadas, então o sistema Ax=b pode ser
reescrito equivalentemente por:
Ax = b⇔


x1 + x2 + x3
x1 − x2 + x4
3x1 + x2 − x5

 =


6
4
3

⇔
⇔


x1 + x2
x1 − x2
3x1 + x2 − x5

+


x3
x4
0

 =


6
4
3

 (5.7)
ou, em notação matricial:
BxB +NxN = b⇔


1 1 0
1 −1 0
3 1 −1




x1
x2
x5

+

1 0
0 1
0 0


[
x3
x4
]
=


6
4
3

 (5.8)
em que B e N são matrizes formadas pelas colunas da matriz original A do Sistema 5.4.
Essas matrizes e os vetores correspondentes de variáveis xB e xN decorrem de regras de
multiplicação de matrizes. Denotando-se: A = [a1 a2 a3 a4 a5], em que ai é a i-ésima
coluna da matriz A, tem-se:
B =


1 1 0
1 −1 0
3 1 −1

 =
[
a1 a2 a5
]
e N =


1 0
0 1
0 0

 =
[
a3 a4
]
(5.9)
Pode-se, ainda, definir dois vetores de ı́ndices:
B = (B1 B2 B3) : B1 = 1, B2 = 2, B3 = 5,
N = (N1 N2) : N1 = 3, N2 = 4.
Exerćıcio 5.1 Considere o sistema de equações lineares Ax=b dado por 5.4, fixe: x3 = 0 e
x4 = 1 e determine os valores das variáveis restantes. Identifique a solução obtida na Figura
5.1. Além disso, fixe x3 = 0 e x4 = 2. Identifique a solução obtida na Figura 5.1. Repita
com outros valores para x4. Desenhe a reta obtida com a variação de x4, mantendo x3 = 0.
Certifique-se que esta reta, no plano (x1, x2), é dada por: x1 + x2 = 6.
5.1 Soluções básicas 44
Exerćıcio 5.2 Reescreva o sistema de equações lineares Ax=b dado em 5.4, considerando
x2 e x3 como as variáveis independentes, na forma BxB + NxN = b. Explicite os ı́ndices
básicos: B1, B2 e B3 e os ı́ndices não-básicos N1 e N2; as matrizes B e N; e os vetores de
variáveis xB e xN . Fixe xN = 0 (isto é, x2 = x3 = 0) e compare com os sistema de equações
lineares em 5.6.
Exerćıcio 5.3 Repita o exerćıcio anterior, considerando x1 e x2 as variáveis independentes.
Qual é o ponto na Figura 5.1 que corresponde à fixação das variáveis independentes em zero?
É uma solução fact́ıvel.
Definição 5.1 Reorganizando as colunas da matriz da seguinte forma:
A = [B N ]
tal que:
• Bmxm, chamada matriz básica, é formada por m colunas da matriz A e é invert́ıvel,
dada por B = [aB1 , aB2 , ..., aBm ], isto é, B1, B2, ..., Bm são os ı́ndices das colunas da
matriz A que pertencem a B, chamados ı́ndices básicos.
• Nmx(n−m), chamada matriz não-básica, é formada pelas n-m colunas restantes de A.
Essa partição nas colunas da matriz A é chamada partição básica e introduz uma partição
no vetor x:
x =
[
xB
xN
]
tal que:
xB =





xB1
xB2
...
xBm





, chamado vetor das variáveis básicas
xN =





xN1
xN2
...
xNn−m





, chamado vetor das variáveis não-básicas
Considerando uma partição básica A = [B N], o sistema Ax = b pode ser reescrito de
forma equivalente como:
Ax = b⇔ [B N ]
[
xB
xN
]
= b
5.1 Soluções básicas 45
ou
Bxb +NxN = b (5.10)
Portanto,
xB = B
−1b− B−1NxN (5.11)
A Expressão 5.11 é chamada solução geral do sistema, pois com ela pode-se determinar
qualquer solução do sistema, bastando atribuir valores quaisquer às n - m variáveis não-
básicas em xN , de modo que as m variáveis básicas em xB fiquem unicamente determinadas
e a solução resultante satisfaça o sistema Ax = b.
Definição 5.2 Considere uma partição básica A=[B N] e a seguinte solução obtida ao se
fixar as n-m variáveis de xN em zero, isto é:
x̂ =
{
x̂B = B
−1b
x̂N = 0
A solução x̂ assim obtida é denominada solução básica. Se x̂B = B
−1b ≥ 0, ou seja, se todas
as variáveis básicas são não-negativas, diz-se que x̂ é uma solução básica fact́ıvel. Além
disso, se x̂B = B
−1b > 0 (todas as variáveis básicas são positivas), diz-se que a solução
básica fact́ıvel é não-degenerada.
Retornando ao exemplo introduzido no ińıcio deste caṕıtulo, cuja solução fact́ıvel é repre-
sentada na Figura 5.1. Considerando o sistema da Equação 5.8:
BxB +NxN = b⇔


1 1 0
1 −1 0
3 1 −1




x1
x2
x5

+


1 0
0 1
0 0


[
x3
x4
]
=


6
4
3


Assim, fixando as variáveis não-básicas em zero: x̂3 = x̂4 = 0 (isto é, x̂N = 0), tem-se


1 1 0
1 −1 0
3 1 −1




x1
x2
x5

 =


6
4
3

⇔ Bx̂B = b
cuja solução é:
x̂B =


x1
x2
x5

 =


5
1
13


Portanto
x̂ =






x1
x2
x5
x3
x4






=






5
1
13
0
0






resolve o sistema Ax = b e não fere a condição de não-negatividade.
5.2 O método simplex 46
Propriedade 5.1 Considere a região fact́ıvel S = {x ∈ Rn tal que Ax = b, x ≥ 0}. Um
ponto x ∈ S é um vértice de S se, e somente se, x for uma solução básica fact́ıvel.
Propriedade 5.2 Se um problema de otimização linear tem solução ótima, então existe
um vértice ótimo.
Em outras palavras, se existe uma solução ótima, existe uma solução básica fact́ıvel ótima.
Como conseqüência desta propriedade, basta que se procure o ótimo entre todas as soluções
básicas fact́ıveis. Isso sugere um método de solução:
• Determine todas asK soluções básicas fact́ıveis (vértices da região fact́ıvel S ): x1, x2, ..., xK .
• Determine a solução ótima xj tal que f(xj) =mı́nimo {f(xk), k = 1, 2, ..., K}.
Porém, em alguns problemas práticos o número K pode ser muito grande, inviabilizando
computacionalmente este procedimento. Um método mais elaborado que inicia com uma
solução básica fact́ıvel e pesquisa apenas outras soluções básicas melhores que a corrente é o
método simplex, detalhado nas próximas seções.
5.2 O método simplex
O método simplex encontra um vértice ótimo pesquisando apenas um subconjunto (em
geral, pequeno) dos K vértices de S. Para construir um método de resolução de um problema
de otimização linear deve-se responder a duas perguntas-chave:
Dada uma solução fact́ıvel,
1. essa solução é ótima?
2. caso não seja ótima, como determinar uma outra solução básica fact́ıvel melhor?
Resposta à primeira pergunta: a solução é ótima?
Considere uma solução básica fact́ıvel
x̂ =
[
x̂B
x̂N
]
em que
{
x̂B = B
−1b ≥ 0
x̂N = 0
,
e a solução geral (5.11) usando a mesma partição básica, isto é:
x =
[
xB
xN
]
tal que xB = B
−1b− B−1NxN . (5.12)
A função objetivo f(x) pode ser expressa considerando a partição básica:
f(x) = cTx =
[
cTB c
T
N
]
[
xB
xN
]
= cTBxB + c
T
NxN (5.13)
com:
Samsung
Realce
5.2 O método simplex 47
• cTB: coeficientes das variáveis básicas na função objetivo;
• cTN : coeficientes das variáveis não-básicas na função objetivo.
Substituindo (5.12) em (5.13), isto é, restringindo x ao sistema Ax = b, tem-se
f(x) = cTB
(
B−1b−B−1NxN
)
+ cTNxN
= cTBB
−1b− cTBB
−1NxN + c
T
NxN (5.14)
O primeiro termo da Equação 5.14 corresponde ao valor da função objetivo em x̂:
f(x̂) = cTBx̂B + c
T
N x̂N = c
T
B(B
−1b) + cTN(0) = c
T
BB
−1b. (5.15)
Para simplificar a notação e os cálculos, é definido um vetor auxiliar, estudado nas seções
seguintes.
Definição 5.3 O vetor λmx1, dado por
λT = cTBB
−1
é chamado vetor multiplicador simplex (ou também, vetor de variáveis duais).
Nota: O vetor multiplicador simplex pode ser obtido pela resolução do sistema de equações
lineares BTλ = cB, que é obtido ao se tomar a transposta de λ
T = cTBB
−1 e multiplicar ambos
os termos da igualdade por BT , isto é:
λT = cTBB
−1 ⇔ λ = (B−1)T cB ⇔ B
Tλ = cB
Utilizando o vetor multiplicador simplex nas Expressões 5.14 e 5.15 tem-se:
f(x) = f(x̂) + (cTN − λ
TN)xN
ou, ainda, considerando que:
cTN − λ
TN = (cN1 , cN2, .., cNn−m)− λ
T (aN1 , aN2 , .., aNn−m)
= (cN1 − λ
TaN1 , cN2 − λ
TaN2 , .., cNn−m − λ
TaNn−m))
e
xN = (xN1 , xN2, ..., xNn−m)
obtém-se
f(x) = f(x̂) + (cN1 − λ
TaN1)xN1 + (cN2 − λ
TaN2)xN2 + ...+ (cNn−m − λ
TaNn−m)xNn−m (5.16)
5.2 O método simplex 48
Definição 5.4 Os coeficientes ĉNj = (cNj − λ
TaNj) das variáveis não-básicas na função
objetivo, descrita por 5.16, são chamados custos relativos ou custos reduzidos
Com a notação da Definição 5.4, a Equação 5.16 pode ser reescrita:
f(x) = f(x̂) + ĉN1xN1 + ĉN2xN2 + ... + ĉNn−mxNn−m (5.17)
Exemplo 5.1 Considere o seguinte problema de otimização linear:
Minimizar f(x1, x2) = −2x1 − x2
x1 + x2 ≤ 4
x1≤ 3
x2 ≤
7
2
x1 ≥ 0, x2 ≥ 0
que pode ser reescrito na forma padrão:
Minimizar f(x1, x2, x3, x4, x5) = −2x1 − x2 + 0x3 + 0x4 + 0x5
x1 + x2 + x3 = 4
x1 + x4 = 3
x2 + x5 =
7
2
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0
A resolução gráfica é dada na Figura 5.2 e a solução ótima é obtida pela intersecção das
retas x1 + x2 = 4 e x1 = 3. Portanto, x
∗
1 = 3, x
∗
2 = 1 e f(x
∗) = −7. Essas equações da reta
decorrem das restrições anteriores na forma de igualdade com x3 = 0 e x4 = 0, o que resulta
no sistema 3x3:
x1 + x2 = 4
x1 = 3
x2 + x5 =
7
2
cuja solução é: x∗1 = 3, x
∗
2 = 1, x
∗
5 =
5
2
(x∗3 = x
∗
4 = 0).
x2 = 7/2
x1 + x2 = 4
x1
x2
x1 = 3
x∗
Figura 5.2: Região fact́ıvel
Samsung
Realce
5.2 O método simplex 49
A solução ótima é uma solução básica com a seguinte partição básica:
B1 = 1, B2 = 2, B3 = 5, N1 = 3, N2 = 4.
Com essa partição, tem-se:
B =
[
aB1 aB2 aB3
]
=
[
a1 a2 a5
]


1 1 0
1 0 0
0 1 1

 ,
N =
[
aN1 aN2
]
=
[
a3 a4
]


1 0
0 1
0 0

 ,
cTB = ( cB1 cB2 cB3 ) =
(
c1 c2 c5
)
= ( −2 −1 0 ),
cTN = ( cN1 cN2 ) =
(
c3 c4
)
= ( 0 0 ).
Para o cálculo dos custos relativos ĉNj = (cNj − λ
TaNj ), j = 1, 2 (lembre-se de que
n−m = 2), primeiramente o vetor multiplicador simplex é calculado.
• Multiplicador simplex: λT = cTBB
−1.
O vetor multiplicador pode ser calculado por dois procedimentos: (i) explicitando a in-
versa de B; e (ii) resolvendo um sistema linear. Sempre que uma operação envolve o cálculo
de uma inversa de matriz, ela pode ser substitúıda por um sistema linear, para o qual podem
ser desenvolvidas técnicas avançadas de resolução.
(i) usando a inversa: B−1 =


0 1 0
1 −1 0
−1 1 1

 .
λT = cTBB
−1 = ( −2 −1 0 )


0 1 0
1 −1 0
−1 1 1

 = ( −1 −1 0 ).
(ii) resolvendo o sistema de equações lineares: BTλ = cB, isto é:
λ1 + λ2 = −2
λ1 + λ3 = −1
λ3 = 0.
Aplicando o método de Gauss-Jordan tem-se: λT = (−1 − 1 0).
Nota: Para matrizes de ordens pequenas, como no exemplo anterior, é irrelevante o uso
da inversa ou a resolução do sistema linear, mas, para matrizes de porte grande, devem ser
Samsung
Realce
5.2 O método simplex 50
utilizadas técnicas avançadas para resolução de sistemas lineares.
Com o vetor multiplicador simplex calculado, pode-se determinar facilmente os custos
relativos para todas as variáveis não-básicas:
• j = 1 : ĉN1 = ĉ3 = c3 − λ
Ta3 = 0− ( −1 −1 0 )


1
0
0

 = 1
• j = 2 : ĉN2 = ĉ4 = c4 − λ
Ta4 = 0− ( −1 −1 0 )


0
1
0

 = 1
Assim, a função objetivo, quando restrita ao sistema Ax = b (ver Expressão 5.17), é
dada por f(x) = −7 + x3 + x4 e, portanto, f(x) = −7 para toda solução fact́ıvel, uma vez
que x3 ≥ 0 e x4 ≥ 0. Disso, conclúı-se que a solução ótima é obtida com x3 = x4 = 0, ou
seja, a solução básica é ótima.
Retornando as Expressões 5.16 e 5.17, sabe-se que xNj ≥ 0 (todas as variáveis do problema
são não-negativas). Portanto, se (cNj − λ
TaNj) ≥ 0, j = 1, 2, ..., n −m, então f(x) ≥ f(x̂)
para todo xN ≥ 0. Assim, a seguinte propriedade é enunciada:
Propriedade 5.3 (Condição de otimalidade) Considere uma partição básica A=[B N]
em que a solução básica associada x̂B = B
−1b ≥ 0 (isto é, solução básica fact́ıvel), e seja
λT = cTBB
−1 o vetor multiplicador simplex. Se (cNj − λ
TaNj ) ≥ 0, j = 1, 2, ..., n−m (isto é,
todos os custos relativos são não-negativos), então a solução básica é ótima.
A propriedade anterior fornece uma maneira simples de se afirmar a otimalidade de uma
solução básica fact́ıvel: se a condição de otimalidade for verificada, então a solução básica
fact́ıvel é ótima. Se a solução básica fact́ıvel for não-degenerada, a rećıproca da condição
de otimalidade também é verdadeira: se uma solução básica fact́ıvel não-degenerada (isto é,
x̂B = B
−1b ≥ 0) é uma solução ótima, então (cNj − λ
TaNj ) ≥ 0, j = 1, 2, ..., n−m. Porém,
pode-se ter uma solução ótima degenerada em mãos, sem que a condição de otimalidade seja
verificada. Nesse caso, entretanto, é sempre posśıvel identificar outra partição básica para
a mesma solução degenerada que satisfaça a condição de otimalidade (soluções degeneradas
podem ser representadas por diferentes partições básicas).
Resposta à segunda pergunta: como determinar uma solução básica fact́ıvel melhor?
Considere uma solução básica fact́ıvel e suponha que a condição de otimalidade seja
violada (caso contrário, a solução é ótima), isto é, suponha que exista k tal que:
(cNk − λ
TaNk) < 0
5.2 O método simplex 51
ou seja, o custo relativo da variável não-básica xNk é negativo.
Exemplo 5.2 Considere o problema de otimização linear dado no Exemplo 5.1 e a seguinte
partição básica: B1 = 3, B2 = 4, B3 = 5, N1 = 1, N2 = 2.
Com essa partição tem-se:
B =
[
aB1 aB2 aB3
]
=
[
a3 a4 a5
]


1 0 0
0 1 0
0 0 1

 ,
N =
[
aN1 aN2
]
=
[
a1 a2
]


1 1
1 0
0 1

 ,
cTB = ( cB1 cB2 cB3 ) =
(
c3 c4 c5
)
= ( 0 0 0 ),
cTN = ( cN1 cN2 ) =
(
c1 c2
)
= ( −2 −1 ).
Os custos relativos ĉNj = (cNj − λ
TaNj ), j = 1, 2, podem ser calculados:
• Multiplicador simplex:
λT = cTBB
−1 = (0 0 0) (neste caso, B−1 = I)
• Cálculo dos custos relativos:
– j = 1 : ĉN1 = ĉ1 = c1 − λ
Ta1 = −2− ( 0 0 0 )


1
1
0

 = −2
– j = 2 : ĉN2 = ĉ2 = c2 − λ
Ta2 = −1− ( 0 0 0 )


1
0
1

 = −1
Com essa partição, ĉ1 e ĉ2 são negativos e, portanto, não satisfazem a condição de otimali-
dade.
A seguir é verificado como a solução básica fact́ıvel pode ser perturbada de modo a
diminuir o valor da função objetivo, por uma estratégia que fornece o fundamento do método
simplex.
Definição 5.5 Chama-se estratégia simplex a perturbação de uma solução básica fact́ıvel
que consiste em alterar as variáveis não-básicas por:
{
xNk = ε ≥ 0, (variavel com custo relativo negativo)
xNj = 0, j = 1, 2, ..., n−m, j 6= k
5.2 O método simplex 52
Em outras palavras, apenas uma variável não-básica, xNk , deixa de ser nula (por sim-
plicidade, supõe-se que a solução é não degenerada, caso contrário ε > 0 pode levar a uma
solução infact́ıvel, como será visto adiante). Com isso, a função objetivo passa a valer (ver
Equação 5.17):
f(x) = f(x̂) + ĉN10 + ... + ĉNkε+ ...+ ĉNn−m0 =
= f(x̂) + ĉNkε < f(x̂).
Note que a função objetivo decresce quando ε cresce, com a taxa negativa ĉNk , ilustrada
na Figura 5.3. Quanto menor o valor de ĉNk , mais rápido a função objetivo decresce. Isso
justifica a escolha da variável não-básica a ser perturbada com o menor custo relativo (essa
escolha é conhecida na literatura como a regra de Dantzig).
f(x)
εε̂
f(x̂)
f(x̂) + ĉNk ε̂
ĉNk
Figura 5.3: Variação da função objetivo
Como a função objetivo decresce quando ε cresce, logo, o objetivo é determinar o maior
valor posśıvel para ε que mantém fact́ıvel a solução perturbada. A seguir será visto a forma
de como determinar tal valor.
Tamanho do passo ε
Com a alteração nos valores das variáveis não-básicas pela estratégia simplex, as variáveis
básicas xB também devem ser alteradas, de modo que o sistema Ax=b seja satisfeito (reveja
a solução geral 5.11). A estratégia simplex é equivalente a alterar as variáveis não-básicas
para:
xN =







xN1
...
xNk
...
xNn−m







=







0
...
ε
...
0







← k (5.18)
5.2 O método simplex 53
portanto, as variáveis básicas são modificadas por
xB = B
−1b− B−1NxN = x̂B −B
−1aNk
︸ ︷︷ ︸
y
ε = x̂B − yε (5.19)
em que y = B−1aNk . A identidade anterior decorre da definição da matriz não-básica N e da
definição de xN dada em 5.18:
NxN = N(0 ... ε ... 0)
T = [aN1 ... aNk ... aNn−m ](0 ... ε ... 0)
T = aNkε
Definição 5.6 Chama-se direção simplex o vetor y = B−1aNk , o qual fornece os coeficientes
de como as variáveis básicas são alteradas pela estratégiasimplex. A direção simplex é solução
do sistema de equações lineares By = aNk .
Reescrevendo a equação vetorial (5.19) em cada uma de suas coordenadas e considerando
a não-negatividade das variáveis básicas tem-se:
xBi = x̂Bi − yiε ≥ 0, i = 1, 2, ..., m.
Assim,
• se yi ≤ 0, então xBi ≥ 0, para todo ε ≥ 0
• se yi > 0, como xBi = x̂Bi − yiε ≥ 0, então, ε ≤
x̂Bi
yi
.
Logo, o maior valor de ε é dado por
ε̂ =
x̂Bl
yl
= min
{
x̂Bi
yi
tal que yi > 0
}
(5.20)
Solução ótima ilimitada: Se yi ≤ 0 para todo i=1,2,...,m, então (5.20) não se aplica, ou
seja, não há limitante superior para ε, o que significa que a solução perturbada pela estratégia
simplex será sempre fact́ıvel para todo valor de ε ≥ 0. Como a função objetivo decresce com
o crescimento de ε, então f(x) → −∞, com ε → ∞. Disso, conclúı-se que o problema não
tem solução ótima (é comum referir-se a estas situação como solução ótima ilimitada).
Exemplo 5.3 Considere o problema de otimização linear no Exemplo 5.1 e a partição bá-
sica:
(B1, B2, B3) = (3, 4, 5) (N1, N2) = (1, 2)
Calculando a solução básica, verificando sua otimalidade e aplicando a estratégia simplex,
tem-se:
5.2 O método simplex 54
• Solução básica: xB = (x3, x4, x5), a qual é obtida ao se anularem as variáveis não-
básicas.
A solução do sistema BxB = b (ou, x̂B = B
−1b), e neste caso a matriz B é a identidade,
é dada por x̂B =


4
3
7/2

 e o valor da função objetivo avaliada nesta solução é:
f(x̂) = cB1 x̂B1 + cB2 x̂B2 + cB3 x̂B3 = 0(4) + 0(3) + 0(
7
2
) = 0.
• Otimalidade:
– multiplicador simplex: lembre-se que cB = (cB1 , cB2 , cB3) = (c3, c4, c5) = (0, 0, 0)
A solução do sistema BTλ = cB (ou, λ
T = cTBB
−1) é


0
0
0


– custos relativos: as variáveis não-básicas são: N1 = 1, N2 = 2,
ĉ1 = c1 − λ
Ta1 = −1 −
(
0 0 0
)


1
1
0

 = −2 ← k = 1 (x1 é alterada pela
estratégia simplex)
ĉ2 = c2 − λ
Ta2 = −1−
(
0 0 0
)


1
0
1

 = −1
Observação: como os dois custos relativos são negativos, aumentar x1 ou x2 faz
decrescer a função objetivo. A escolha do menor custo relativo, chamada regra de
Dantizg, é bastante utilizada.
– direção simplex: y = (y1, y2, y3) (ver a definição 5.6).
A solução do sistema By = aN1 é


1
1
0

, que proporciona como as variáveis
básicas se modificam: xBi = x̂Bi − yiε (ver expressão 5.19), ou seja,
x3 = 4− ε; x4 = 3− ε; x5 =
7
2
.
O valor máximo para ε deve ser tal que as variáveis básicas sejam não-negativas,
o que define o tamanho do passo.
• Tamanho do passo:
ε̂ = min
{
x̂B1
y1
,
x̂B2
y2
}
=
{
4
1
,
3
1
}
= 3 =
{
x̂B2
y2
}
Com o valor de ε̂ = 3, a variável xB2 = x4 se anula (isto é, x4 = 3− 3 = 0). Por outro lado
a variável não-básica x1 torna-se positiva: x1 = ε̂ = 3.
5.2 O método simplex 55
Retornando a Equação 5.20. Com o valor de ε̂ =
x̂Bl
yl
, a variável xBl se anula e a variável
não-básica xNk torna-se positiva. De fato, da expressão 5.19, tem-se:
• l -ésima variável básica: xBl = x̂Bl − ylε̂ = x̂Bl − yl(
xBl
yl
) = 0,
• k -ésima variável não-básica: xNk = ε̂,
isto é, a nova solução tem a seguinte caracteŕıstica:
(xB1 · · · xBl
︸︷︷︸
=0
· · · xBm | 0 · · · xNk
︸︷︷︸
ε̂
· · · 0)
ou seja, n-m variáveis são nulas: xN1 , ..., xBl , ..., xNn−m , as quais podem ser consideradas
não-básicas. Isso resulta em uma nova partição básica com os ı́ndices trocados:
Bl ↔ Nk
isto é, a variável xNk torna-se básica e a variável xBl não-básica. As matrizes básica e não-
básica são alteradas por apenas uma coluna:
B = [aB1 · · · aBl · · · aBm ] → B
′ = [aB1 · · · aNk
︸︷︷︸
=l−esima coluna
· · · aBm ]
N = [aN1 · · · aNk · · · aNn−m ] → N
′ = [aN1 · · · aBl
︸︷︷︸
=k−esima coluna
· · · aNn−m ]
Diz-se que xNk entra na base e xBl sai da base. A seguinte propriedade garante que a
nova partição é básica.
Propriedade 5.4 A matriz B′, definida anteriormente, é invert́ıvel, de modo que A =
[B′ N ′] é uma partição básica.
A solução básica associada à nova partição é aquela obtida pela estratégia simplex:
xNk = ε̂
xBi = x̂Bi − yiε̂ i = 1, ..., m, i 6= l,
que é uma solução fact́ıvel, por construção.
Com isso, mostra-se que a estratégia simplex produz uma nova solução fact́ıvel (isto é,
um novo vértice), para o qual a função objetivo tem um valor menor:
f(x) = f(x̂) + ĉNk ε̂ < f(x̂),
e este procedimento pode ser repetido algumas vezes, isto é: encontrar outra solução básica
melhor a partir daquela em mãos, enquanto a condição de otimalidade não for verificada.
Este procedimento basicamente consiste no método simplex.
5.2 O método simplex 56
Exemplo 5.4 Considere o problema de otimização linear no Exemplo 5.1 e a partição bá-
sica:
(B1, B2, B3) = (1, 2, 4) (N1, N2) = (3, 5)
Com essa partição, define-se as matrizes B e N e os vetores cB e CN :
B =
[
aB1 aB2 aB3
]
=
[
a1 a2 a4
]
=


1 1 0
1 0 1
0 1 0


N =
[
aN1 aN2
]
=
[
a3 a5
]
=


1 0
0 0
0 1


CTB =
(
cB1 cB2 cB3
)
=
(
c1 c2 c4
)
=
(
−2 −1 0
)
CTN =
(
cN1 cN2
)
=
(
c3 c5
)
=
(
0 0
)
Calculando a inversa de B, tem-se:
B−1 =


1 0 −1
0 0 1
−1 1 1


• Solução básica: xB = (x1, x2, x4) é a solução do sistema BxB = b, ou seja, pode-se
aplicar o método de eliminação de Gauss, operando sobre a matriz aumentada ou, de
forma equivalente, x̂B = B
−1b.
O valor de x̂B obtido é:
x̂B =


1/2
7/2
5/2


O valor da função objetivo: f(x̂) = cB1 x̂B1 + cB2 x̂B2 + cB3 x̂B3 = 2(1/2) + (−1)(7/2) +
0(5/2) = −9/2.
• Otimalidade: primeiro é calculado o vetor multiplicador simplex e, em seguida, os custos
relativos.
i) multiplicador simplex: lembre que: cB = (cB1 , cB2 , cB3) = (c1, c2, c4) = (−2, −1, 0).
O vetor multiplicador do simplex é dado pelo sistema BTλ = cB ou, de forma equi-
valente,
λT = cTBB
−1 =
[
−2 −1 0
]


1 0 −1
0 0 1
−1 1 1

 =
(
−2 0 1
)
.
5.2 O método simplex 57
ii) cálculo dos custos relativos: N1 = 3, N2 = 5
ĉN1 = ĉ3 = c3 − λ
Ta3 = 0− ( −2 0 1 )


1
0
0

 = 2
ĉN2 = ĉ5 = c5−λ
Ta5 = 0−( −2 0 1 )


0
0
1

 = −1← k = 2 (xN2 = x5 entra na base).
A condição de otimalidade não é verificada e a variável x5 pode ser aumentada para
diminuir a função objetivo por f(x) = f(x̂) + ĉNk ε̂ = −
9
2
− ε.
• Cálculo da direção simplex: y = B−1a5 =


1 0 −1
0 0 1
−1 1 1




0
0
1

 =


−1
1
1

.
• Tamanho do passo:
ε̂ = min
{
x̂B2
y2
,
x̂B3
y3
}
=
{ 7
2
1
,
5
2
1
}
=
5
2
=
{
x̂B3
y3
}
(xB3 = x4 sai da base).
Com o valor de ε = 5
2
, a variável x4 se anula e a variável não-básica x5 torna-se positiva
e, portanto, tem-se a nova partição básica:
(B1, B2, B3) = (1, 2, 5) (N1, N2) = (3, 4).
Com essa partição, as novas matrizes básica e não-básica são dadas por:
B =
[
aB1 aB2 aB3
]
=
[
a1 a2 a5
]
=


1 1 0
1 0 0
0 1 1


N =
[
aN1 aN2
]
=
[
a3 a4
]
=


1 0
0 1
0 0


que já foi verificado, no Exemplo 5.1, que corresponde à solução ótima.
5.2.1 O algoritmo simplex
Considere um problema de otimização linear escrito na forma padrão. A seguir, são resu-
midos os procedimentos e definições abordados anteriormente. Note que o desenvolvimento
anterior pressupõe o conhecimento de uma solução básica fact́ıvel inicial. O procedimento
detalhado de como determinar uma solução inicial é chamado Fase I e seus detalhes serão
apresentados mais adiante. O método simplex propriamente dito é chamado de Fase II.
Fase I:
5.2 O método simplex 58
1. Determine inicialmente uma partição básica fact́ıvel A=[B,N]. A rigor, precisa-se de
dois vetores de ı́ndices básicos e não-básicos:
(B1, B2, ..., Bm) e (N1, N2, ..., Nn−m)
Os vetores das variáveis básicas e não-básicas, respectivamente:
xTB = (xB1 , xB2 , ..., xBm) e x
T
N = (xN1 , xN2 , ..., xNn−m).
2. Faça iteração ← 1.
Fase II: {ińıcioda iteração simplex}
Passo 1: {cálculo da solução básica}
{
x̂B ← B
−1b (equivalentemente, resolva o sistema Bx̂B= b)
x̂N ← 0
Passo 2: {cálculo dos custos relativos}
2.1) {vetor multiplicador simplex}
λT ← cTBB
−1 (equivalentemente, resolva o sistema BTλ = cB)
2.2) {custos relativos}
ĉNj ← cNj − λ
TaNj j = 1, 2, ..., n−m
2.3) {determinação da variável a entrar na base}
ĉNk ← min.
{
ĉNj , j = 1, 2, ..., n−m
}
(a variavel xNk entra na base)
Passo 3: {teste de otimalidade}
Se ĉNk ≥ 0, então: pare {solução na iteração atual é ótima}
Passo 4: {cálculo da direção simplex}
y ← B−1aNk (equivalentemente, resolva o sistema: By = aNk)
Passo 5: {determinação do passo e variável a sair da base}
Se y ≤ 0, então: pare {problema não tem solução ótima finita f(x)→ −∞ }
Caso contrário, determine a variável a sair da base pela razão mı́nima:
ε̂←
x̂Bl
yl
= min.
{
x̂Bi
yi
, tal que yi> 0, i = 1, 2, ..., m
}
(a variavel xBl sai da base)
5.2 O método simplex 59
Passo 6: {atualização: nova partição básica, troque a l-ésima coluna de B pela k-ésima
coluna de N}
matriz básica nova: B ← [aB1 ...aBl−1 aNk aBl+1 ...aBm ]
matriz não-básica nova: N ← [aN1 ...aNk−1 aBl aNk+1 ...aNn−m ]
iteração ← iteração + 1
Retorne ao Passo 1
{fim da iteração simplex}
3. Calcule o valor da função objetivo f(x) =⇒ FIM.
Exerćıcio 5.4 Considere o problema de otimização linear:
Minimizar f(x1, x2) = −x1 − 2x2
x1 + x2 ≤ 6
x1 − x2 ≤ 4
−x1 + x2 ≤ 4
x1 ≥ 0, x2 ≥ 0.
Definindo as variáveis básicas como sendo: B1 = 3, B2 = 4 e B3 = 5. Aplique o algoritmo
simplex e encontre a solução ótima, se houver.
Exerćıcio 5.5 Considere o problema linear:
Minimizar f(x1, x2) = −x1 − x2
x1 − x2 ≤ 4
−x1 + x2 ≤ 4
x1 ≥ 0, x2 ≥ 0.
Definindo as variáveis básicas como sendo: B1 = 3 e B2 = 4. Aplique o algoritmo simplex e
encontre a solução ótima, se houver.
Solução do Exerćıcio 5.4:
Introduzindo as variáveis de folga, tem-se o problema na forma padrão (Tabela 5.1).
A seguir será aplicado o algoritmo simplex, com todos os passos explicitados a cada
iteração.
Fase I:
Uma solução básica fact́ıvel inicial é facilmente obtida, pois os coeficientes das variáveis de
folga formam uma matriz identidade que, aliada à não-negatividade dos termos independentes
(e se fossem negativos?), fornece uma partição básica fact́ıvel.
(B1, B2, B3) = (3, 4, 5), (N1, N2) = (1, 2)
5.2 O método simplex 60
Tabela 5.1: Dados do problema.
x1 x2 x3 x4 x5 b
1 1 1 0 0 6
A 1 -1 0 1 0 4
-1 1 0 0 1 4
Min f(x) -1 -2 0 0 0
ou seja, a matriz básica B=I. Fazendo xN = (x1, x2) = (0, 0), tem-se trivialmente os valores
das variáveis básicas.
Fase II:
1a Iteração:
Tabela 5.2: Dados conforme a partição na Iteração 1.
Índices
básicos não-básicos
B1 = 3 B2 = 4 B3 = 5 N1 = 1 N2 = 2 b
1 0 0 1 1 6
[B|N ] 0 1 0 1 -1 4
0 0 1 -1 1 4
[ctB | c
t
N ] 0 0 0 -1 -2 f(x)=0
• Passo 1: {Cálculo da solução básica} = xB=(x3, x4, x5)
Resolva o sistema BxB = b ou xB = B
−1b e obtenha x̂B =


6
4
4


Avaliação da função objetivo: f(x̂) = cB1 x̂B1 + cB2 x̂B2 + cB3 x̂B3 = 0(6) + 0(4) + 0(4)
• Passo 2: {Cálculo dos custos relativos}
2.1) {vetor multiplicador simplex}: (ctB = (cB1 , cB2 , cB3) = (c3, c4, c5) = (0, 0, 0).
A solução do sistema BTλ = cB ou λ
T = cTBB
−1, tem-se: λT = (0, 0, 0)
2.2) {custos relativos}: (N1 = 1, N2 = 2)
ĉ1 = c1 − λ
Ta1 = −1−
(
0 0 0
)


1
1
−1

 = −1
ĉ2 = c2 − λ
Ta2 = −2 −
(
0 0 0
)


1
−1
1

 = −2← k = 2 (xN2 = x2 entra na base).
5.2 O método simplex 61
2.3) {determinação da variável a entrar na base}:
Como ĉN2 = ĉ2 = min.{ĉNj , j = 1, 2} = −2 < 0, então a variável N2 = 2(= x2) entra
na base.
• Passo 3: {teste de otimalidade} Os custos relativos mostram a função objetivo em
termos das variáveis não-básica: f(x) = 0 − 1x1 − 2x2. Como há custos relativos
negativos, a solução atual não é ótima.
• Passo 4: {Cálculo da direção simplex} Resolva o sistema By = a2 ou y = B
−1a2 e
obtenha y =


1
−1
1

 .
O vetor y mostra como as variáveis básicas são alteradas: xB = x̂B − yε, as quais,
nesta iteração são x3, x4 e x5. As variáveis não-básicas x1 e x2 se alteram conforme a
estratégia simplex:
x1 = 0 e x2 = ε
Isso mostra como a solução é alterada no plano (x1, x2), neste caso, sobre o eixo x2.
• Passo 5: {determinação do passo e variável a sair da base}
ε̂ = min.
{
x̂B1
y1
,
x̂B3
y3
}
= min.
{
6
1
,
4
1
}
= 4 =
x̂B3
y3
, (a variavel xB3 = x5 sai da base)
Com esse valor de ε̂, x5 = xB3 = 0 e (x1, x2)=(0,4) é a nova solução obtida pelo método
simplex.
• Passo 6: {atualização: nova partição básica, troque a l-ésima coluna de B pela k-ésima
coluna de N}
(B1, B2, B3) = (3, 4, 2) (N1, N2) = (1, 5),
{novo valor para a função objetivo: f(x) = f(x̂) + ĉNk ε̂ = 0− 2(4) = −8}.
2a Iteração:
• Passo 1: {Cálculo da solução básica} = xB=(x3, x4, x2)
Resolva o sistema BxB = b ou xB = B
−1b e obtenha x̂B =


2
8
4

 .
Avaliação da função objetivo: f(x̂) = cB1 x̂B1+cB2 x̂B2+cB3 x̂B3 = 0(2)+0(8)+(−2)(4) =
−8
5.2 O método simplex 62
Tabela 5.3: Dados conforme a partição na Iteração 2.
Índices
básicos não-básicos
B1 = 3 B2 = 4 B3 = 2 N1 = 1 N2 = 5 b
1 0 1 1 0 6
[B|N ] 0 1 -1 1 0 4
0 0 1 -1 1 4
[ctB | c
t
N ] 0 0 -2 -1 0 f(x)=-8
• Passo 2: {Cálculo dos custos relativos}
2.1) {vetor multiplicador simplex}: (ctB = (cB1 , cB2 , cB3) = (c3, c4, c2) = (0, 0, −2).
A solução do sistema BTλ = cB ou λ
T = cTBB
−1, tem-se: λT = (0, 0, −2)
2.2) {custos relativos}: (N1 = 1, N2 = 5)
ĉ1 = c1 − λ
Ta1 = −1−
(
0 0 −2
)


1
1
−1

 = −3← k = 1 (xN1 = x1 entra na base).
ĉ5 = c5 − λ
Ta5 = 0−
(
0 0 −2
)


0
0
1

 = 2
2.3) {determinação da variável a entrar na base}:
Como ĉN1 = ĉ1 = min.{ĉNj , j = 1, 2} = −3 < 0, então a variável x1 entra na base.
• Passo 3: {teste de otimalidade} Os custos relativos mostram a função objetivo em
termos das variáveis não-básica: f(x) = −8 − 3x1 + 2x2. Como há custos relativos
negativos, a solução atual não é ótima.
• Passo 4: {Cálculo da direção simplex} Resolva o sistema By = a1 ou y = B
−1a1 e
obtenha y =


2
0
−1

 .
O vetor y mostra como as variáveis básicas são alteradas: xB = x̂B − yε, as quais,
nesta iteração são x3, x4 e x2. As variáveis não-básicas x1 e x5 se alteram conforme a
estratégia simplex:
x1 = ε e x5 = 0
Isso mostra como a solução é alterada no plano (x1, x2), neste caso, sobre o eixo x5 = 0
ou, de outra forma, sobre a reta x1 + x2 = 4.
5.2 O método simplex 63
• Passo 5: {determinação do passo e variável a sair da base}
ε̂ = min.
{
x̂B1
y1
}
=
{
2
2
}
= 1 =
x̂B1
y1
Com esse valor de ε̂, segue que x1 = 1 (alteração da variável não-básica) e x2 = xB3 =
x̂B3 − y3ε = 4 + ε = 5 (alteração da variável básica)
• Passo 6: {atualização: nova partição básica, troque a l-ésima coluna de B pela k-ésima
coluna de N}
(B1, B2, B3) = (1, 4, 2) (N1, N2) = (3, 5),
{novo valor para a função objetivo: f(x) = f(x̂) + ĉNk ε̂ = −8− 3(1) = −11}.
3a Iteração:
Tabela 5.4: Dados conforme a partição na Iteração 3.
Índices
básicos não-básicos
B1 = 1 B2 = 4 B3 = 2 N1 = 3 N2 = 5 b
1 0 1 1 0 6
[B|N ] 1 1 -1 0 0 4
-1 0 1 0 1 4
[ctB | c
t
N ] -1 0 -2 0 0 f(x)=-11
• Passo 1: {Cálculo da solução básica} = xB=(x1, x4, x2)
Resolva o sistema BxB = b ou xB = B
−1b e obtenha x̂B =


1
8
5

 .
Avaliação da função objetivo: f(x̂) = cB1 x̂B1 + cB2 x̂B2 + cB3 x̂B3 = (−1)(1) + 0(8) +
(−2)(5) = −11
• Passo 2: {Cálculo dos custos relativos}
2.1) {vetor multiplicador simplex}: (ctB = (cB1 , cB2 , cB3) = (c1, c4, c2) = (−1, 0, −2).
A solução do sistema BTλ = cB ou λ
T = cTBB
−1, tem-se: λT = (−3
2
, 0, −1
2
)
2.2) {custos relativos}: (N1 = 3, N2 = 5)
ĉ3 = c3 − λ
Ta3 = 0−
(
−3
2
0 −1
2
)


1
0
0

 =
3
2
5.3 Determinaçãode uma solução básica fact́ıvel inicial 64
ĉ5 = c5 − λ
Ta5 = 0−
(
−3
2
0 −1
2
)


0
0
1

 =
1
2
.
2.3) {determinação da variável a entrar na base}:
Como ĉNj = min.{ĉNj , j = 1, 2} =
1
2
> 0, segue-se que a solução atual,
x̂B =


x1
x4
x2

 =


1
8
5

 e x̂N =
(
x3
x5
)
=
(
0
0
)
,
ou
x̂ =






x1
x2
x3
x4
x5






=






1
5
0
8
0






,
é a solução ótima para as variáveis.
A solução ótima da função objetivo é f(x) = cB1xB1 + cB2xB2 + cB3xB3 = (−1)(1) +
0(8) + (−2)(5) = −11.
Exerćıcio 5.6 Verificar o desempenho do Exerćıcio 5.4 graficamente.
5.3 Determinação de uma solução básica fact́ıvel inicial
Para que o método simplex possa ser aplicado precisa-se de uma solução básica fact́ıvel
inicial (Fase I do algoritmo simplex). Algumas classes de problemas de otimização linear
oferecem naturalmente essa solução básica fact́ıvel, por exemplo:
Minimizar f(x) = ctx
Ax ≤ b
x ≥ 0
em que b ≥ 0.
Após a introdução das variáveis de folga, diga-se, xf , tem-se:
Minimizar f(x) = ctx
Ax+ xf = b
x ≥ 0, xf ≥ 0
de modo que a matriz dos coeficientes das restrições agora é dada por [A I] e uma partição
básica é dada por:
• B = I: as variáveis básicas são as variáveis de folga xB = xf ;
5.3 Determinação de uma solução básica fact́ıvel inicial 65
• N = A: as variáveis não-básicas são as variáveis originais xN = x,
e a solução básica fact́ıvel é dada por:
{
xB = xf = b ≥ 0
xN = x = 0.
Porém, em geral, uma solução básica fact́ıvel não está dispońıvel e deve ser encontrada.
Considere o problema de otimização linear:
Minimizar f(x) = ctx
Ax = b
x ≥ 0
em que A não tem uma submatriz identidade. Sem perda de generalidade, suponha b ≥ 0,
pois se bi < 0, basta multiplicar a i -ésima restrição por −1. A questão é como encontrar uma
partição de colunas da matriz A, A = [B N ], tal que exista B−1 e xB = B
−1b ≥ 0, isto é,
uma partição básica fact́ıvel.
Para se ter uma ideia dessa dificuldade, suponha, por exemplo, que A seja uma matriz
10x20 (m = 10 e n = 20). É necessário identificar 10 colunas de A que sejam linearmente
independentes para formar a matriz B, e a solução do sistema BxB = b deve satisfazer
xB ≥ 0.
Pode-se fazer uma busca ao acaso, isto é, um algoritmo exaustivo simples do tipo:
• selecione 10 colunas e resolva o sistema resultante;
• se a solução do sistema for única e não-negativa, então há sucesso. Pode-se usar esta
seleção como uma partição básica fact́ıvel e iniciar o simplex;
• senão (B não é invert́ıvel ou a solução única tem coordenadas negativas), selecione
outras 10 colunas até que o sucesso seja obtido ou todas as possibilidades tenham sido
investigadas.
Entretanto, esse procedimento simples para determinar uma partição básica inicial pode
envolver a resolução de C2010 =
20!
10!(20−10)!
= 184.756 sistemas de equações lineares 10x10.
Método das duas fases
Nota-se que as variáveis de folga são úteis para a seguinte classe de problemas:
Ax ≤ b
x ≥ 0
equivalente a
Ax+ xf = b
x ≥ 0, xf ≥ 0
No entanto, se o problema está na forma de igualdade, não há variáveis de folga. Assim,
são introduzidas novas variáveis como se fossem de folga:
5.3 Determinação de uma solução básica fact́ıvel inicial 66
Ax+ y = b
x ≥ 0, y ≥ 0.
Essas novas variáveis são chamadas variáveis artificiais e não fazem parte do problema
original, portanto, devem ser eliminadas. Para eliminar as variáveis artificiais, utiliza-se um
novo objetivo, que resulta no problema artificial :
Mininimar fa(x, y) =
m∑
i=1
yi
Ax+ y = b
x ≥ 0, y ≥ 0
A função objetivo do problema artificial penaliza as variáveis artificiais de modo que a
solução ótima desse problema deve, se posśıvel, ter yi = 0, i = 1, 2, ..., m. Os coeficientes na
função objetivo das variáveis artificiais podem ser quaisquer números positivos (por simplici-
dade, todos foram escolhidos iguais a 1). Caso haja colunas da matriz identidade na matriz
A (geralmente introduzidas por variáveis de folga de algumas restrições de desigualdade), es-
tas podem ser utilizadas na construção da base inicial, sendo complementadas com variáveis
artificiais. O exemplo a seguir esclarece essa observação.
Exemplo 5.5 Considere o seguinte problema de otimização linear:
Mininimar f(x) = x1 − x2 + 2x3
x1 + x2 + x3 = 3
2x1 − x2 + 3x3 ≤ 4
xi ≥ 0, i = 1, 2, 3
o qual pode ser escrito na forma padrão:
Mininimar f(x) = x1 − x2 + 2x3 + 0x4
x1 + x2 + x3 = 3
2x1 − x2 + 3x3 + x4 = 4
xi ≥ 0, i = 1, 2, 3, 4
Por exemplo, os seguintes problemas podem ser utilizados como problemas artificiais:
Caso A: Uma variável artificial é introduzida para cada restrição.
Mininimar fa(x1, ..., x6) = x5 + x6
x1 + x2 + x3 + x5 = 3
2x1 − x2 + 3x3 + x4 + x6 = 4
xi ≥ 0, i = 1, ..., 6
em que x5 e x6 são variáveis artificiais (por conveniência, denota-se as variáveis x5 e x6,
em vez de y1 e y2). Uma base fact́ıvel é formada pelas colunas das variáveis artificiais x5 e x6.
5.3 Determinação de uma solução básica fact́ıvel inicial 67
Caso B: Apenas uma variável artificial é introduzida - uma coluna da matriz identidade
já está dispońıvel.
Mininimar fa(x1, ..., x5) = x5
x1 + x2 + x3 + x5 = 3
2x1 − x2 + 3x3 + x4 =4
xi ≥ 0, i = 1, ..., 5
em que a vairável x5 é a variável artificial. Uma base fact́ıvel é formada pelas colunas das
variáveis x4 (variável de folga) e x5 (variável artificial).
Tanto no Caso A como no Caso B, as matrizes básicas são identidades, ou permutações
destas, dependendo da ordem em que as variáveis básicas são definidas. Por exemplo, pode-se
definir, no Caso B, as variáveis básicas por xB = (x5, x4). O problema artificial tem sempre
uma partição básica fact́ıvel óbvia:
• B = I: variáveis básicas xB = y,
• N = A: variáveis não-básicas xN = x,
portanto, pode-se aplicar o método simplex, que promove as trocas das colunas das variáveis
artificiais por colunas das variáveis originais. Ao final, as variáveis artificiais são não-básicas
(nulas, conforme objetivo) e uma base com as colunas originais de A é obtida. Se o problema
original tem solução fact́ıvel, x̂, então:
Ax̂ = b
x̂ ≥ 0,
e esta solução é ótima para o problema artificial, pois o par (x̂, 0), ou seja, ŷ = 0, é fact́ıvel
para o problema artificial:
Ax̂+ ŷ = b
x̂ ≥ 0, ŷ ≥ 0,
e fa(x̂, ŷ) = 0, que é o mı́nimo posśıvel para o objetivo artificial.
Uma vez encontrada uma solução básica em que todas as variáveis artificiais são não-
básicas, tem-se uma base formada por colunas originais e, portanto, pode-se aplicar o método
simplex para resolver o problema original a partir dessa base. Esse procedimento é chamado
de método das duas fases : Fase I - resolve o problema artificial e Fase II - resolve o problema
original, a partir da base fact́ıvel obtida na Fase I. Se o problema original é infact́ıvel, então
o problema artificial tem solução ótima com y 6= 0.
5.3 Determinação de uma solução básica fact́ıvel inicial 68
Passos do algoritmo simplex (Fase I e Fase II)
1. {Verificação da necessidade da Fase I}
• Se o problema for de ”maximizar”, então multiplique a função objetivo por (-1) e
converta-o em ”minimização”
• Se no vetor b algum ı́ndice for menor que 0, então multiplique toda a restrição por
(-1) e inverta o sentido da desigualdade
• Se há pelo menos uma restrição com sinal >, >= ou =, vá para a Fase I, senão
vá para a Fase II
Fase I:
2. {Formulação do Problema Artificial}
Seja m o número de restrições do problema e n o número de variáveis do problema (já
na forma padrão, contendo as variáveis originais, folga e excesso).
• Função objetivo:
min f(x) =
n∑
i=1
0xi +
n+m∑
i=n+1
1xi
• Restrições:
– Para cada restrição j = 1, ..., m incluir uma variável xn+j.
• Partição básica inicial:
(B1 = n + 1, B2 =n + 2, ..., Bm = n +m) e (N1 = 1, N2 = 2, ..., Nn = n)
Os vetores das variáveis básicas e não-básicas, respectivamente:
xTB = (xB1 , xB2 , ..., xBm) e x
T
N = (xN1 , xN2 , ..., xNn).
• Iteração ← 1.
3. {ińıcio da iteração simplex - Fase I}
Passo 1: {cálculo da solução básica}
{
x̂B ← B
−1b (equivalentemente, resolva o sistema Bx̂B= b)
x̂N ← 0
Passo 2: {cálculo dos custos relativos}
5.3 Determinação de uma solução básica fact́ıvel inicial 69
2.1) {vetor multiplicador simplex}
λT ← cTBB
−1 (equivalentemente, resolva o sistema BTλ = cB)
2.2) {custos relativos}
ĉNj ← cNj − λ
TaNj j = 1, 2, ..., n−m
2.3) {determinação da variável a entrar na base}
ĉNk ← min.
{
ĉNj , j = 1, 2, ..., n−m
}
(a variavel xNk entra na base)
Passo 3: {teste de otimalidade}
Se ĉNk ≥ 0, então:
• Se ainda há variáveis artificiais na base ⇒ Pare {Problema infact́ıvel} ⇒
FIM
• Senão ⇒ Fase II
Passo 4: {cálculo da direção simplex}
y ← B−1aNk (equivalentemente, resolva o sistema: By = aNk)
Passo 5: {determinação do passo e variável a sair da base}
Se y ≤ 0, então: pare {problema não tem solução ótima finita} ⇒ Problema
Original Infact́ıvel ⇒ FIM
Caso contrário, determine a variável a sair da base pela razão mı́nima:
ε̂←
x̂Bl
yl
= min.
{
x̂Bi
yi
, tal que yi> 0, i = 1, 2, ..., m
}
(a variavel xBl sai da base)
Passo 6: {atualização: nova partição básica, troque a l-ésima coluna de B pela k-ésima
coluna de N}
matriz básica nova: B ← [aB1 ...aBl−1 aNk aBl+1 ...aBm ]
matriz não-básica nova: N ← [aN1 ...aNk−1 aBl aNk+1 ...aNn ]
Verificação das variáveis da base:
• Se ainda há variáveis artifiais na base ⇒ Retorne ao Passo 1
• Senão ⇒ Fase II
iteração ← iteração + 1
{fim da iteração simplex - Fase I}
Fase II:
5.3 Determinação de uma solução básica fact́ıvel inicial 70
4. {ińıcio da iteração simplex - Fase II}
Usando a base obtida na Fase I, B = {B1, B2, ...., Bm} e N = {N1, N2, ..., Nn−m} (na
partição não-básica, são eliminadas as variáveis artificiais da Fase I), execute os passos
do algoritmo Simplex a seguir.
Passo 1: {cálculo da solução básica}
{
x̂B ← B
−1b (equivalentemente, resolva o sistema Bx̂B= b)
x̂N ← 0
Passo 2: {cálculo dos custos relativos}
2.1) {vetor multiplicador simplex}
λT ← cTBB
−1 (equivalentemente, resolva o sistema BTλ = cB)
2.2) {custos relativos}
ĉNj ← cNj − λ
TaNj j = 1, 2, ..., n−m
2.3) {determinação da variável a entrar na base}
ĉNk ← min.
{
ĉNj , j = 1, 2, ..., n−m
}
(a variavel xNk entra na base)
Passo 3: {teste de otimalidade}
Se ĉNk ≥ 0, então: pare {solução na iteração atual é ótima}
Passo 4: {cálculo da direção simplex}
y ← B−1aNk (equivalentemente, resolva o sistema: By = aNk)
Passo 5: {determinação do passo e variável a sair da base}
Se y ≤ 0, então: pare {problema não tem solução ótima finita f(x)→ −∞ }
Caso contrário, determine a variável a sair da base pela razão mı́nima:
ε̂←
x̂Bl
yl
= min.
{
x̂Bi
yi
, tal que yi> 0, i = 1, 2, ..., m
}
(a variavel xBl sai da base)
Passo 6: {atualização: nova partição básica, troque a l-ésima coluna de B pela k-ésima
coluna de N}
matriz básica nova: B ← [aB1 ...aBl−1 aNk aBl+1 ...aBm ]
matriz não-básica nova: N ← [aN1 ...aNk−1 aBl aNk+1 ...aNn−m ]
iteração ← iteração + 1
{fim da iteração simplex - Fase II}
5.4 O método simplex em tabelas 71
5. {Solução ótima}
S =
n∑
i=1
cix̂i
Exerćıcio 5.7 Considere o problema de otimização linear:
Mininimar f(x) = x1 − x2 + 2x3
x1 + x2 + x3 = 3
2x1 − x2 + 3x3 ≤ 4
xi ≥ 0, i = 1, 2, 3
Determine uma solução básica fact́ıvel para a Fase II utilizando o Caso B.
Exerćıcio 5.8 Resolva o seguinte problema linear:
Max f(x1, x2) = x1 + x2
−x1 + x2 ≥ 3
x1 + x2 ≤ 27
2x1 − x2 ≤ −3
x1, x2 ≥ 0
5.4 O método simplex em tabelas
As operações realizadas no método simplex podem ser organizadas em tabelas, chamada
tabelas simplex ou tableaux. Embora não seja a forma ideal de se implementar o método
simplex em um computador, essa organização pode ser interessante para manipular problemas
pequenos e compreender mais rapidamente como o método funciona.
Exemplo 5.6 Dado o seguinte problema:
Minimizar f(x1, x2) = −5x1 − 3x2
3x1 + 5x2 ≤ 15
5x1 + 2x2 ≤ 10
x1 ≥ 0, x2 ≥ 0.
Colocando o problema na forma padrão:
Minimizar f(x1, x2, x3, x4) = −5x1 − 3x2 + 0x3 + 0x4
3x1 + 5x2 + x3 = 15
5x1 + 2x2 + x4 = 10
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0.
Resolvendo pelo tableaux tem-se:
1a Solução básica fact́ıvel
5.4 O método simplex em tabelas 72
Tabela 5.5: Iteração 1.
x1 x2 x3 x4
VB/Custos -5 -3 0 0 Z
x3 3 5 1 0 15
x4 5 2 0 1 10
x1 = x2 = 0 (variáveis não-básicas)
x3 = 15, x4 = 10 (variáveis básicas)
Z=0 ⇒ corresponde ao vértice D(0,0).
Esta solução não é ótima, pois a linha que se refere à função objetivo (custos) apresenta
coeficientes negativos. A variável não-básica a entrar na base é aquela que apresenta o menor
coeficiente negativo na linha dos custos, ou seja, a variável x1. Para verificar a variável básica
a sair da base é feito o seguinte:
x1 = min
{
15
3
,
10
5
}
= 2
O pivô será o elemento a21 (5) e fazendo x1 = 2, a variável x4 passa a variável não-básica.
Tem-se, portanto, uma nova solução básica fact́ıvel, tal que x1 e x3 são variáveis básicas
e x2 e x4 são variáveis não-básicas.
O próximo passo é transformar o pivô da coluna da variável x1 em 1 e zerar os demais
elementos daquela coluna, (L1 → L1 + L3, L2 → L2 −
3
5
L3, L3 →
1
5
L3).
Tabela 5.6: Iteração 2.
x1 x2 x3 x4
VB/Custos 0 -1 0 1 Z+10
x3 0
19
5
1 −3
5
9
x1 1
2
5
0 1
5
2
2a Solução básica fact́ıvel
x4 = x2 = 0 (variáveis não-básicas)
x3 = 9, x1 = 2 (variáveis básicas)
Z=-10 ⇒ corresponde ao vértice C(2,0).
Esta solução não é ótima, pois a linha que se refere à função objetivo (custos) apresenta
coeficientes negativos. A variável não-básica a entrar na base é aquela que apresenta o menor
coeficiente negativo na linha dos custos, ou seja, a variável x2. Para verificar a variável básica
5.5 Dualidade 73
a sair da base é feito o seguinte:
x2 = min
{
9
19
5
,
2
2
5
}
=
45
19
O próximo passo é transformar o pivô da coluna da variável x2 em 1 e zerar os demais
elementos daquela coluna, (L1 → L1 +
5
19
L2, L2 →
5
19
L2, L3 → L3 −
2
19
L3).
Tabela 5.7: Iteração 3.
x1 x2 x3 x4
VB/Custos 0 0 5
19
16
19
Z+235
19
x2 0 1
5
19
−3
19
45
19
x1 1 0
−2
19
5
19
20
19
3a Solução básica fact́ıvel
x4 = x3 = 0 (variáveis não-básicas)
x2 =
45
19
, x1 =
20
19
(variáveis básicas)
Z=−235
19
⇒ corresponde ao vértice C(20
19
, 45
19
).
Esta solução é ótima, pois todos os coeficientes das variáveis da função objetivo são não
negativos.
Exerćıcio 5.9 Resolver os seguintes problemas por tableaux.
a)
Minimizar f(x1, x2) = −x1 − 2x2
x1 + x2 ≤ 6
x1 − x2 ≤ 4
−x1 + x2 ≤ 4
x1 ≥ 0, x2 ≥ 0.
b)
Minimizar f(x1, x2) = −x1 − x2
x1 − x2 ≤ 4
−x1 + x2 ≤ 4
x1 ≥ 0, x2 ≥ 0.
5.5 Dualidade
Nas seções anteriores foram estudados problemas de otimização linear que, com simplifi-
cações, modelam situações práticas e suas variáveis significam alguma decisão a ser tormada
(tais como: quantidades de cada ingrediente em uma mistura; ńıveis de estoque de produtos
5.5 Dualidade 74
em um determinado peŕıodo; número de barras a serem cortadas segundo um padrão de
corte, etc). Por outro lado, os valores dessas variáveis (isto é, uma solução do problema de
otimização) dependem dos dados do problema (estoque dispońıvel dos ingredientes; capaci-
dades de máquinas), embora sejam dados, em geral é conveniente um decisor examinar como
as posśıveis variações nos dados interferem na solução do problema.
Questões do seguinte tipo podem ser de interesse: em um problema de planejamento da
produção, se o estoque de uma matéria prima aumentasse, como o custo de produção se
alteraria? (isso poderia sugerir poĺıticasde compras de matérias-primas). Em um problema
de distribuição de água em redes urbanas, se a capacidade de um reservatório de água fosse
ampliada, como o consumo de energia para bombeamento de água seria afetado? (isso po-
deria sugerir investimentos em infra-estrutura). Em um problema de corte de material, se a
demanda por um tamanho de um item fosse maior ou menor, como a perda de material seria
alterada? (isso poderia sugerir poĺıticas de descontos nos preços dos itens). Essas observações
correspondem a analisar o modelo matemático sob outro ponto de vista e introduzem um
novo modelo de otimização linear, chamado problema dual, em correspondência ao original,
que é chamado problema primal. A teoria da dualidade fornece alguns subśıdios para res-
ponder às questões levantadas e, em adição, uma abordagem alternativa para se resolver um
problema de otimização linear, o método dual simplex.
Exemplo 5.7 Considere o problema clássico da dieta (problema primal): quer-se consumir
quantidades de determinados alimentos de tal forma a satisfazer as necessidades mı́nimas
de nutrientes exigidas a um custo mı́nimo dispendido, problema este ilustrado pelo quadro
seguinte.
Tabela 5.8: Problema da dieta.
Comp./Alimento a1 a2 a3 a4 a5 nec. mı́nima
de nutrientes
Protéınas (g) 3 4 5 3 6 42
Sais minerais (g) 2 3 4 3 3 24
Custos (R$) 25 35 50 33 36
Considerando-se:
aij: percentual do componente i presente no alimento j;
xj: quantidade do alimento j presente na dieta a ser feita;
cj: preço por grama de cada alimento;
bi: quantidade mı́nima de cada componente a ser consumida na dieta;
aj: coluna j da matriz do sistema.
5.5 Dualidade 75
Problema Primal:
Minimizar Z = 25x1 + 35x2 + 50x3 + 33x4 + 36x5
s.a : 3x1 + 4x2 + 5x3 + 3x4 + 6x5 ≥ 42
2x1 + 3x2 + 4x3 + 3x4 + 3x5 ≥ 24
xi ≥ 0, i = 1, 2, 3, 4, 5
Suponha que um vendedor de ṕılulas de protéınas e sais minerais propõe substituir a dieta
de alimentos expressa de acordo com a Tabela 5.8, por uma dieta de ṕılulas, com as seguintes
condições:
1. a ṕılula de uma unidade (g) de protéına custará w1;
2. a ṕılula de uma unidade (g) sais minerais custará w2;
3. os preços w1 e w2 serão fixados arbitrariamente;
4. o vendedor garante que as ṕılulas terão preços iguais ou mais baratos que qualquer
alimento;
5. o vendedor pretende, é claro, maximizar sua renda de modo a satisfazer a necessidade
da dieta.
Problema Dual:
Maximizar Z = 42w1 + 24w2
s.a : 3w1 + 2w2 ≤ 25
4w1 + 3w2 ≤ 35
5w1 + 4w2 ≤ 50
3w1 + 3w2 ≤ 33
6w1 + 3w2 ≤ 36
w1 ≥ 0, w2 ≥ 0
Resumo:
Para um problema de otimização linear em sua forma padrão, chamado problema primal,
outro problema de otimização linear é definido, chamado problema dual.
Problema primal:
Minimizar f(x) = ctx
s.a : Ax = b
x ≥ 0
Problema dual:
Maximizar g(λ) = btλ
s.a : Atλ ≤ c
Isto é, o problema dual é constrúıdo da seguinte forma (primal na forma padrão: mini-
mização, restrição de igualdades e variáveis não-negativas):
5.5 Dualidade 76
• Problema dual é maximização.
• O número de variáveis duais λ é igual ao número de restrições do primal.
• O número de restrições duais é igual ao número de variáveis x do primal.
• Os coeficientes da função objetivo dual são os coeficientes do vetor de recursos b do
primal.
• A matriz dos coeficientes das restrições duais é a transporta da matriz dos coeficientes
do primal, AT .
• As restrições duais são do tipo ≤.
• O vetor dos recursos dual é formado pelos coeficientes c da função objetivo primal
(também chamado gradiente do objetivo primal).
Caso o problema primal não esteja na forma padrão (por exemplo, restrições de desi-
gualdade), a Tabela 5.9 fornece as regras de como construir o dual de qualquer problema de
otimização linear.
Primal (dual) Dual (primal)
Minimização Maximização
Vetor de recursos Gradiente do objetivo
Gradiente do objetivo vetor de recursos
Restrições Variáveis
= Livre
≤ ≤
≥ ≥
Variáveis Restrições
Livre =
≤ ≥
≥ ≤
Tabela 5.9: Regras para construção do problema dual
Exemplo 5.8 Considere os problemas primais listados a seguir e seus respectivos problemas
duais, utilizando a Tabela 5.9.
a) Primal:
Minimizar f(x) = x1 + 2x2
−2x1 + x2 ≤ 3
3x1 + 4x2 ≤ 5
x1 − x2 ≤ 2
x1 ≥ 0, x2 ≥ 0
5.5 Dualidade 77
Como o problema primal é do tipo minimização, deve-se seguir a coluna à esquerda da
Tabela 5.9 para escrever as caracteŕısticas do dual à direita.
Dual: (problema de maximização com duas restrições e três variáveis)
Maximizar g(λ) = 3λ1+5λ2+2λ3
−2λ1 + 3λ2 + λ3 ≤ 1
λ1 + 4λ2 − λ3 ≤ 2
λ1 ≤ 0, λ2 ≤ 0, λ3 ≤ 0
b) Primal:
Maximizar f(x) = x1 + 2x2
−2x1 + x2 ≤ 3
3x1 + 4x2 ≤ 5
x1 − x2 ≤ 2
x1 ≥ 0, x2 ≥ 0
Como o problema primal é do tipo maximização, deve-se seguir a coluna à direita da
Tabela 5.9 para escrever as caracteŕısticas do dual à esquerda.
Dual: (problema de minimização com duas restrições e três variáveis)
Minimizar g(λ) = 3λ1+5λ2+2λ3
−2λ1 + 3λ2 + λ3 ≥ 1
λ1 + 4λ2 − λ3 ≥ 2
λ1 ≥ 0, λ2 ≥ 0, λ3 ≥ 0
c) Primal:
Maximizar f(x) = x1 + 2x2
−2x1 + x2 + x3 ≥ 3
3x1 + 4x2 ≤ 5
x1 ≥ 0, x2 livre, x3 ≤ 0
Dual: (problema de minimização com três restrições e duas variáveis)
Minimizar g(λ) = 3λ1+5λ2
−2λ1 + 3λ2 ≥ 1
λ1 + 4λ2 = 2
λ1 ≤ 0
λ1 ≤ 0, λ2 ≥ 0
Observação: Pode-se aplicar a Tabela 5.9 para construir o problema dual de cada um dos
problemas duais anteriores (a), (b) e (c), para concluir que os problemas primais são recons-
trúıdos.
5.5 Dualidade 78
Conclusões:
Os problemas primal e dual mantêm relações estreitas que podem ser resumidas por:
• O problema primal tem solução ótima se, e somente se, o problema dual também tiver
solução ótima.
• O mı́nimo da função objetivo primal é igual ao máximo da função objetivo dual, isto é,
se x∗ é uma solução ótima primal e λ∗ é uma solução ótima dual, então f(x∗) = g(λ∗)
e vice-versa.
• Se f(x)→ −∞ (primal ilimitado), então o problema dual é infact́ıvel.
• Se g(λ)→∞ (dual ilimitado), então o problema primal é infact́ıvel.
• Ambos os problemas, primal e dual, podem ser infact́ıveis.
• O vetor multiplicador simplex na solução básica ótima, dado por λT = cBB
−1, é uma
solução ótima do problema dual.
Exerćıcio 5.10 Escreva o problema dual dos seguintes problemas primais:
a)
Minimizarf(x) = x1 + x2 + x3
s.a : 4
5
x1 +
2
5
x2 = 108
3
2
x2 +
9
10
x3 = 120
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
b)
Minimizarf(x1) = −x1
0x1 = 1
x1 ≥ 0
Exerćıcio 5.11 Considerando o problema do Planejamento da Produção, Tabela 5.10, for-
mule o problema de maximização do lucro.
Mat. Prima/Produtos Sapatos Botinas Disponibilidade
Couro 2 1 8
Borracha 1 2 7
Cola 0 1 3
Lucro (un.) 1 1 -
Tabela 5.10: Planejamento da produção
Após a formulação do problema primal, formule o problema dual, sendo as variáveis o
custo gerado pela perda de uma unidade da matéria prima i.
5.6 Considerações finais 79
Exerćıcio 5.12 Escreva o dual do seguinte problema e os resolva graficamente.
Maximizarf(x) = x1 + x2
−x1 + x2 ≤ 1
x1 − 2x2 ≤ 1
x1 ≥ 0, x2 ≥ 0
Exerćıcio 5.13 Escreva o algoritmo do método dual simplex.
5.6 Considerações finais
Neste caṕıtulo foi abordada a teoria básica da programação linear, bem como estudado o
algoritmo simplex.
5.7 Exerćıcios
1) Resolver os seguintes problemas aplicando o algoritmo Simplex.
a)
Max f(x) = x1 + x2
s.a. : 2x1 + x2 ≤ 18
−x1 + 2x2 ≤ 4
3x1 − 6x2 ≤ 12
x1, x2 ≥ 0
b)
Max f(x) = 6x1 + 2x2
s.a. : 3x1 + x2 ≤ 33
x1 + x2 ≤ 13
x1, x2 ≥ 0
c)
Max f(x) = x1 + x2
s.a. : 2x1 + x2 ≤ 8
x1 + 2x2 ≤ 3
x1, x2 ≥ 0
d)
Max f(x) = 3x1 + x2
2x1 + x2 ≤ 30
x1 + 4x2 ≤ 40
x1 ≥ 0, x2 ≥ 0
e)
Max f(x) = 2x1 + 5x2
3x1 + 10x2 ≤ 600
x1 + 2x2 ≤ 162
x1 ≥ 0, x2 ≥ 0
5.7 Exerćıcios 80
f)
Min f(x) = −x1 + 2x2
s.a. : −2x1 + x2 ≤ 3
3x1 + 4x2 ≤ 5
x1 − x2 ≤ 2
x1, x2 ≥ 0
g)
Min f(x) = −x1 − 2x2
x1 + x2 ≥ 1
−5x1 + 2x2 ≥ −10
3x1 + 5x2 ≥ 15
x1 ≥ 0, x2 ≥ 0
h)
Max f(x1, x2)= 2x1 + 2x2
s.a. : −1
2
x1 + x2 ≤ 2x1 − x2 ≥ −1
x1 ≥ 0, x2 ≥ 0
i)
Max f(x1, x2)= x1 + x2
s.a. : 2x1 + x2 ≤ 18
−x1 + 2x2 ≤ 4
3x1 − 6x2 ≥ −12
x1 ≥ 0, x2 ≥ 0
j)
Min f(x1, x2)= 4x1 − 12x2
s.a. : 2x1 + x2 ≥ 6
x1 + 3x2 ≤ 8
x1 ≥ 4
x1 ≥ 0, x2 ≥ 0
k)
Min f(x) = −x1 − x2 + 0x3
s.a : x1 + x3 ≥ 1
x1 − 3x2 − x3 ≥ 1
x1 − x2 + 5x3 ≥ 5
x1 + x2 + x3 ≤ 5
x1, x2, x3 ≥ 0
l)
Max f(x) = 3x1 + 3x2 + 0x3
s.a : x1 + 3x3 ≤ 5
x2 ≤ 5
3x1 + 2x3 ≥ 6
x1 + x2 ≤ 10
x1, x2, x3 ≥ 0
5.7 Exerćıcios 81
m)
Max f(x) = 4x1 + 3x2
s.a : x1 + 3x2 ≤ 7
2x1 + 2x2 = 8
x1 + x2 ≤ −3
x2 ≤ 2
x1, x2 ≥ 0
2) Resolver em forma de tabelas os seguintes PPLs:
a)
Max f(x1, x2) = 3x1 + x2
2x1 + x2 ≤ 30
x1 + 4x2 ≤ 40
x1 ≥ 0, x2 ≥ 0
b)
Max f(x1, x2) = 2x1 + 5x2
3x1 + 10x2 ≤ 600
x1 + 2x2 ≤ 162
x1 ≥ 0, x2 ≥ 0
c)
Min Q(x) = −x1 + 2x2
s.a. : −2x1 + x2 ≤ 3
3x1 + 4x2 ≤ 5
x1 − x2 ≤ 2
x1, x2 ≥ 0
d)
Max f(x1, x2)= x1 + x2
s.a. : 2x1 + x2 ≤ 18
−x1 + 2x2 ≤ 4
3x1 − 6x2 ≥ −12
x1 ≥ 0, x2 ≥ 0
e)
Max f(x) = 3x1 + 3x2 + 0x3
s.a : x1 + 3x3 ≤ 5
x2 ≤ 5
3x1 + 2x3 ≥ 6
x1 + x2 ≤ 10
x1, x2, x3 ≥ 0
5.7 Exerćıcios 82
f)
Max f(x) = 4x1 + 3x2
s.a : x1 + 3x2 ≤ 7
2x1 + 2x2 = 8
x1 + x2 ≤ −3
x2 ≤ 2
x1, x2 ≥ 0
g)
Max f(x) = 4x1 + 8x2
s.a : 3x1 + 2x2 = 18
x1 + x2 ≤ 5
x1 ≤ 4
x1, x2 ≥ 0
3) Resolva graficamente o dual do seguinte problema primal:
max f(x1, x2, x3) = 3x1 + x2 + 4x3
s.a : 6x1 + 3x2 + 5x3 ≤ 25
3x1 + 4x2 + 5x3 ≤ 20
x1, x2, x3 ≥ 0
4) Escreva o dual do problema primal e verifique se w = (4 5) é solução fact́ıvel.
max f(x1, x2, x3, x4, x5) = 10x1 + 24x2 + 20x3+20x4+25x5
s.a : x1 + x2 + 2x3 + 3x4 + 5x5 ≤ 19
2x1 + 4x2 + 3x3 + 2x4 + x5 ≤ 57
x1, x2, x3, x4, x5 ≥ 0
5) Escreva o dual do seguinte problema primal:
min f(x1, x2, x3, x4, x5, x6, x7) = −2x1 + 13x2 + 3x3 − 2x4+5x5+5x6 + 10x7
s.a : x1 − x2 + 4x4 − x5 + x6 − 4x7 = 5
2x1 + 7x4 − 2x5 + 3x6 − 3x7 ≥ −1
5x2 + x3 − x4 + 2x5 − x6 − 2x7 ≤ 5
3x2 + x3 + x4 + 2x5 + x6 − x7 = 2
x1, x2, x3, x4, x5 ≥ 0, x6 ≤ 0, x7 : irrestrito
6) Dado o seguinte Problema Primal:
max f(x1, x2, x3) = 3x1 + x2 + 4x3
s.a : 6x1 + 3x2 + 5x3 ≤ 25
3x1 + 4x2 + 5x3 ≤ 20
x1, x2, x3 ≥ 0
5.7 Exerćıcios 83
A forma preparada que corresponde à solução ótima do problema anterior é dada por:
f + 2x2 + 1/5x4 + 3/5x5 = 17
s.a : x1 − 1/3x2 + 1/3x4 − 1/3x5 = 5/3
x2 + x3 − 1/5x4 + 2/5x5 = 3
a) Identificar a solução ótima.
b) Escreva o dual e encontre a solução ótima.
c) Sendo o seguinte problema:
max f(x1, x2, x3) = 3x1 + 2x2 + 4x3
s.a : 6x1 + 2x2 + 5x3 ≤ 25
3x1 + 3x2 + 5x3 ≤ 20
x1, x2, x3 ≥ 0
A solução do Ítem (a) continua fact́ıvel? É ótima?
Caṕıtulo 6
Programação Inteira
Em muitos problemas práticos as variáveis de decisão apenas fazem sentido se tiverem
valores inteiros. Por exemplo, a alocação de pessoas, máquinas e véıculos para efetuar deter-
minadas tarefas necessariamente tem que ser em quantidades inteiras, sendo uma restrição
dif́ıcil de ser manipulada matematicamente. Entretanto, para o caso de programação linear
sujeitos a esta restrição adicional, tem-se conseguido algum progresso no desenvolvimento de
procedimentos de solução. Logo, tem-se o seguinte problema:
Maximizar f(x)
sujeito a Ax = b
x ≥ 0 e inteiro
(6.1)
Na prática uma abordagem comum para os problemas de Programação Inteira (também
denotada de Programação Linear Inteira) tem sido usar o método simplex (ignorando, as-
sim, a restrição inteira) e, em seguida, arredondar, na solução, os valores não-inteiros para
inteiros. Embora muitas vezes essa estratégia seja adequada, existem falhas. Uma é que
a solução ótima de programação linear, depois de ser arredondada, não é necessariamente
viável. Freqüentemente é dif́ıcil detectar de que maneira fazer o arredondamento para que
se mantenha a viabilidade. Pode mesmo ser necessário, depois do arredondamento, mudar o
valor de algumas variáveis em uma ou mais unidades.
Por estas razões, seria útil ter um procedimento de soluções eficaz para obter uma solução
ótima para problemas de programação linear inteira. Um considerável número de algoritmos
tem sido desenvolvido para este propósito, porém, infelizmente, nenhum possui uma eficiência
computacional que seja mesmo remotamente comparável a do método simplex (exceto para
tipos especiais de problemas). Portanto, eles estão normalmente limitados a problemas rela-
tivamente pequenos, tendo, talvez, umas poucas dúzias de variáveis. Por isso, esta continua
sendo uma área ativa de pesquisa e continuam a ser feitos progressos no desenvolvimento de
algoritmos eficientes.
Alguns pesquisadores crêem que o modo mais promissor para os algoritmos de programa-
84
6.1 Representação Gráfica 85
ção inteira é usar a técnica de branch and bound e ideias relacionadas à enumeração impĺıcita
das soluções viáveis inteiras.
Neste caṕıtulo é abordada a representação gráfica (considerando o R2) para os problemas
de programação inteira, bem como o algoritmo branch and bound e alguns exerćıcios de
fixação.
6.1 Representação Gráfica
Nesta seção são considerados problemas de programação inteira com apenas duas variá-
veis, permitindo uma visualização e resolução gráfica.
Exemplo 6.1 Considere o seguinte problema de otimização linear:
Minimizar f(x1, x2) = −2x1 − x2
s.a : x1 + x2 ≤ 4
x1 ≤ 3
x2 ≤
7
2
x1 ≥ 0, x2 ≥ 0 e inteiros
que pode ser reescrito na forma padrão:
Minimizar f(x1, x2, x3, x4, x5) = −2x1 − x2 + 0x3 + 0x4 + 0x5
s.a : x1 + x2 + x3 = 4
x1 + x4 = 3
x2 + x5 =
7
2
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0 e inteiros
As soluções fact́ıveis estão na Figura 6.1. Encontre a solução ótima.
x2 = 7/2
x1 + x2 = 4
x1
x2
x1 = 3
x∗
Figura 6.1: Pontos fact́ıveis
Vértice ótimo x∗ = (3, 1) e a solução ótima é S = −7.
6.2 Método Branch and Bound 86
Exerćıcio 6.1 Encontre graficamente as soluções fact́ıveis e a ótima do seguinte problema:
Maximizar f(x1, x2) = 5x1 + 8x2
x1 + x2 ≤ 6
5x1 + 9x2 ≤ 45
x1 ≥ 0, x2 ≥ 0 e inteiros
Exerćıcio 6.2 Encontre graficamente as soluções fact́ıveis e a ótima do seguinte problema:
Maximizar f(x1, x2) = 10x1 + 6x2
9x1 + 5x2 ≤ 45
−4x1 + 5x2 ≤ 5
x1 ≥ 0, x2 ≥ 0 e inteiros
6.2 Método Branch and Bound
O método denominado de Branch and Bound (BB) baseia-se na ideia de desenvolver uma
enumeração inteligente dos pontos candidatos à solução ótima inteira de um problema. O
termo branch refere-se ao fato de que o método efetua partições no espaço das soluções. O
termo bound ressalta que a prova da otimalidade da solução utiliza-se de limites calculados
ao longo da enumeração (Goldbarg e Luna 2005). Definindo:
(P ) = Maximizar{ctx|Ax = b, x ≥ 0, x ∈ Z+} (6.2)
(P̄ ) = Maximizar{ctx|Ax = b, x ≥ 0, x ∈ R+} (6.3)
Definindo ainda V ∗(P ) e V ∗(P̄ ) os valores das funções objetivo no ótimo de (P) e (P̄ ),
respectivamente, tem-se:
V ∗(P ) ≤ V ∗(P̄ ) (6.4)
Considerando ainda qualquer solução viável x̃ de (P), então
V (x̃) ≤ V ∗(P ) (6.5)
e dessa forma V ∗(P̄ ) é um limitante superior para (P) e qualquer de suas soluções viáveis.
Se x̄ é a solução ótima de (P̄ ) tal que x̄j é não inteiro tem-se:
xj ≥ ⌊x̄j⌋+ 1 ou xj ≤ ⌊x̄j⌋ (6.6)
em toda a solução viável de (P). Dessa forma, o problema (P) pode ser dividido em dois
novos problemas (P1) e (P2).
Exemplo 6.2 Goldbarg e Luna (2005)
Maximizar f(x1, x2) = 5x1 + 8x2
x1 + x2 ≤ 6
5x1 + 9x2 ≤ 45
x1 ≥ 0, x2 ≥ 0 e inteiros
6.2 Método Branch and Bound 87
Aplicando o método simplex, tem-se a seguinte solução ótima: x1 =
9
4
; x2 =
15
4
e z = 411
4
.
Desenvolvendo a ideia de separação em relação a variável x2, pode-se organizar a equação
disjuntiva a seguir:
x2 ≥ ⌊15/4⌋+ 1 = 4 ou x2 ≤ ⌊15/4⌋ = 3
A equação anterior produz duas restrições disjuntivas que, quando acrescidas ao problema
original, são capazes de criar dois novos problemas que não possuem a solução ótima cont́ı-
nua.
Com a consideração da disjunção, o problema original será reduzido então em dois novos
problemas a saber:
(P1)Maximizar z = ctx
sujeito a : Ax ≤ b
xi ≤ ⌊x
0
i ⌋
xi ∈ Z
+
(P2)
Maximizar z = ctx
sujeito a : Ax ≤ b
xi ≥ ⌊x
0
i ⌋+ 1
xi ∈ Z
+
A estratégia de separação cria novos e mais restritos problemas que, normalmente, serão
de mais fácil solução. Neste exemplo, o problema (P) é separado em dois problemas (P1)
e (P2). A estratégia de separação pode ser reaplicada a esses problemas em função, por
exemplo, da variável x1. A Figura 6.2 apresenta, em forma de árvore, as possibilidades de
solução dos problemas que serão gerados pela divisão de (P). Na árvore cada ńıvel representa
uma separação ou branch em relação a uma variável.
Logo P5 é a solução do problema.
6.2.1 Algoritmo Branch and Bound
Esta subseção é baseada em Nogueira (–).
Admitindo que o problema de Programação Inteira seja modelado por:
1. Max
n∑
j=1
ctjxj
sujeito a:
2.
n∑
j=1
aijxj ≤ bi para i = 1, 2, ..., m
3. xj ∈ Z para j = 1, 2, ..., p (≤ n)
4. xj ≥ 0 para j = p+ 1, ..., n
6.2 Método Branch and Bound 88
P0
x1 = 2, 25 x2 = 3, 75
z = 41, 25
x2 ≥ 4 x2 ≤ 3
P1
x1 = 3 x2 = 3
z = 39
P2
x1 = 1, 8 x2 = 4
z = 41
x1 ≥ 2 x1 ≤ 1
P3
Inviável
P4
x1 = 1 x2 = 4, 25
z = 40, 4
x2 ≥ 5 x2 ≤ 4
P5
x1 = 0 x2 = 5
z = 40
P6
x1 = 1 x2 = 4
z = 37
Figura 6.2: Árvore branch do Exemplo 6.2
Supondo que para cada variável inteira seja posśıvel fornecer limites inferiores Lj e supe-
riores Uj que seguramente incluam os valores ótimos.
5. Lj ≤ xj ≤ Uj para j = 1, 2, ..., p (≤ n)
A ideia principal do algoritmo Branch and Bound é oriunda de que um valor inteiro T
qualquer contido no intervalo Lj ≤ T ≤ Uj − 1 e xj uma solução ótima também satisfará:
6. xj ≥ T + 1
ou
7. xj ≤ T
Passos do Algoritmo Branch and Bound
Em qualquer iteração t, existe um limitante inferior Zt para o valor da função-objetivo.
Além disto, existe também uma Lista-Mestra de problemas de Programação Linear a serem
resolvidos com diferença entre eles apenas nos limites para as variáveis xj (5). Na Iteração 1
existe um único problema consistindo em (1), (2), (4) e (5). O procedimento na iteração t é:
Passo 1 Termine as computações se a Lista-Mestra estiver vazia, senão tire um problema de
P.L. da Lista-Mestra.
6.3 Considerações Finais 89
Passo 2 Resolva o problema escolhido. Se este não tiver nenhuma solução viável ou se o valor
ótimo Z for menor ou igual Zt, então faça Zt+1 = Zt e retorne ao Passo 1.
Passo 3 Se a solução ótima obtida para o problema de P.L. satisfizer as restrições de inteiros,
então registre-a, faça Zt+1 ser o valor ótimo correspondente da função objetivo X e
retorne ao Passo 1, senão, prossiga ao Passo 4.
Passo 4 Escolha qualquer variável xj , com j = 1, 2, ..., p que não tenha um valor inteiro na
solução ótima obtida para o problema escolhido de P.L. Faça bj denotar este valor e
⌊bj⌋ significa o maior inteiro menor ou igual a bj (arredondar para baixo). Acrescente
dois problemas de P.L. à Lista-Mestra, idênticos ao problema escolhido no Passo 1,
sendo em um o limite inferior Lj para xj é ⌊bj⌋ + 1 e no outro o limite superior Uj
para xj é⌊bj⌋. Faça Z
t+1 = Zt e retorne ao Passo 1.
No fim do algoritmo, se houver registrado uma solução viável com Zt, esta é ótima, caso
contrário não existe nenhuma solução viável.
É bastante comum encontrar uma solução com valores inteiros antes da última iteração,
porém só é posśıvel afirmar que esta é ótima após a iteração final.
O processo no Passo 1 é chamado de ramificação porque ele envolve a seleção de um
problema de P.L. para consideração posterior.
O processo no Passo 2 é conhecido como afrouxamento porque o problema de Progra-
mação Inteira é resolvido como um problema de P.L. ordinário (ignorando a restrição de
inteiros).
O processo no Passo 4 é conhecido como separação, onde um problema é ”genitor” de
P.L. com Z maior que Zt dá origem a dois descendentes.
Exerćıcio 6.3 Aplique o algoritmo de Branch and Bound no seguinte problema (Taha
2008):
Max Z = 5x1 + 4x2
s.a : x1 + x2 ≤ 5
10x1 + 6x2 ≤ 45
x1, x2 ∈ Z
+
6.3 Considerações Finais
A finalidade deste caṕıtulo foi introduzir a Programação Linear Inteira (Programação
Linear). Vale ressaltar que além do Algoritmo Branch and Bound há outros algoritmos na
literatura que tratam do tema.
6.4 Exerćıcios 90
6.4 Exerćıcios
1) Dado o seguinte.
Maximizar f(x1, x2, x3) = 3x1 + 3x2 + 13x3
−3x1 + 6x2 + 7x3 ≤ 8
6x1 − 3x2 + 7x3 ≤ 8
x1, x2, x3 ≥ 0 ∈ Z
Aplicando o algoritmo de Branch and Bound foi obtida a seguinte figura:
x3=0
x2=2.67
x1=2.67
Inviável
x3=0.28
x2=2
x1=2
x3=1
x2=0.33
x1=0.33
z=15 Z=13
x3=0
x2=2.33
x1=2
z=14.86
x2=0
x3=1.14
x2<=0
x3>=1 x3<=0
x1>=3 x1<=2
x2>=1
x1=0
Inviável
x3>=2 x3<=1
x1>=1 x1=0
P6
P9
P11
Inviável
z=15.71
z=16
Figura 6.3: Solução parcial do Exerćıcio 1
Encontre os valores de P6, P9 e P11.
6.4 Exerćıcios 91
2) (Arenales et al., 2007) Resolva o problema abaixo aplicando o algoritmo de Branch and
Bound.
Minimizar f(x) = −5x1 − x2
s.a. : 7x1 − 5x2 ≤ 13
3x1 + 2x2 ≤ 17
x1, x2 ≥ 0 e inteiros
3) Aplique o algoritmo de Branch and Bound no seguinte problema:
Maximizar f(x1, x2) = 5x1 + 8x2
x1 + x2 ≤ 6
5x1 + 9x2 ≤ 45
x1 ≥ 0, x2 ≥ 0 e inteiros
4) (Taha, 2008) Aplique o algoritmo de Branch and Bound no seguinte problema:
Maximizar f(x1, x2) = 5x1 + 4x2
3x1 + 2x2 ≥ 5
2x1 + 3x2 ≥ 7
x1 ≥ 0, x2 ≥ 0 e inteiros
5) Aplique o algoritmo de Branch and Bound no problema:
Maximizar f(x1, x2) = 6x1 + 8x2
30x1 + 20x2 ≤ 310
5x1 + 10x2 ≤ 113
x1 ≥ 0, x2 ≥ 0 e inteiros
6) Escreva um problema de Programação Linear que apresente solução viável se o espaço de
soluções for cont́ınuo e solução inviável se o espaço de soluções for discreto (Prog. Inteira).
Esboce a árvore do procedimento de busca do algoritmo Branch and Bound na resolução do
seu problema.
7) Um casal, Eve e Steven querem dividir suas tarefas domésticas (fazer compras, cozinhar,
lavar louças e lavar roupas) entre eles, de tal maneira que cada um tenha duas tarefas e o
tempo total gasto para realizar tais tarefas seja mı́nimo. Suas eficiências sobre estas tarefas
diferem de acordo com a tabela abaixo, que representa o tempo necessário por semana que
cada um leva para fazer cada tarefa:
Fazer Compras Cozinhar Lavar Louça Lavar Roupa
A B C D
Eve (1) 4.5 7.8 3.6 2.9
Steven (2) 4.9 7.2 4.3 3.1
Formule o modelo de Programação Linear Inteira para este problema.
6.4 Exerćıcios 92
8) Resolva graficamente o seguinte problema de programação inteira:
Maximizar f(x) = 9x1 + 5x2
s.a : 4x1 + 9x2 ≤ 35
x1 ≤ 6
x1 − 3x2 ≥ 1
3x1 + 2x2 ≤ 19
x1, x2 ∈ Z+
9) (Taha, 2008) Resolva graficamente o seguinte problema de programação inteira:
Maximizar f(x) = 3x1 + 2x2
s.a : 2x1 + 5x2 ≤ 9 ,
4x1 + 2x2 ≤ 9 ,
x1, x2 ≥ 0 e inteiras
10) (Lachtermacher, 2013) Uma empresa produz quatro artigos A1, A2, A3 e A4. As exigên-
cias de matéria prima, espaço para estocagem, taxa de produção, assim como os lucros por
artigo, são apresentados na tabela a seguir.
Artigos A1 A2 A3 A4
Matéria prima (kg/artigo) 2 2 1.3 4
Espaço (m3/artigo ) 2 2.5 2 1.5
Taxa de produção (artigo/hora) 15 33 10 15
Lucro (u.m./artigo ) 5 6.5 5 5.5
A quantia total de matéria prima dispońıvel por dia para todos os quatro artigos é de
180kg, o espaço dispońıvel é de 230m3 e utilizam-se 7.5 horas por dia para produção.
Quantas unidades de cada artigo devem ser produzidas por dia para se maximizar o lucro?
Determine a solução inteira para esse problema.
Caṕıtulo 7
Programação Dinâmica
Uma das técnicas que podem ser utilizadas para resolver problemas de otimização é a pro-
gramação dinâmica. Ela tem sido aplicada com sucesso na resolução de problemas originários
das mais diversas áreas. Entre as várias aplicações, incluem-se problemas de planejamento
da produção, gestão de estoques, determinação de tamanhos de lotes de produção, problemasde corte e empacotamento, alocação de recursos limitados, determinação da capacidade de
expansão de usinas geradoras de energia elétrica, gestão de projetos, gestão financeira, deter-
minação da confiabilidade de sistemas de comunicação, programação de tarefas em sistemas
de manufatura flex́ıvel, manutenção e reposição de equipamentos, entre outras (Arenales
et al. 2007).
A programação dinâmica pode ser aplicada na resolução de problemas gerais de otimização
linear ou não-linear, cont́ınua ou discreta, etc. A principal caracteŕıstica da programação
dinâmica consiste na decomposição do problema original em uma seqüência de problemas
menores e mais simples de serem resolvidos. Para alguns problemas, a maneira de realizar
essa decomposição é aparente. É o caso de situações que apresentam seqüências de decisões
a serem tomadas em estágios sucessivos, por exemplo, quando as decisões são definidas ao
longo de uma seqüência de instantes de tempo (Arenales et al. 2007).
7.1 Conceitos Básicos
A resolução do problema original é encontrada por meio da decomposição e resolução de
uma sequência de problemas menores (mais simples).
A seguir são apresentadas as caracteŕısticas da programação dinâmica.
• Estágios : os problemas são decompostos em estágios que são resolvidos sequencial-
mente, sendo um estágio por vez. Cada estágio produz uma solução do problema que
define valores de parâmetros importantes para o problema do estágio seguinte.
93
7.1 Conceitos Básicos 94
• Estados : cada estágio tem um número associado de estados. O estado do sistema é a
informação necessária para a tomada de decisão (Arenales et al. 2007).
• Decisões : as decisões que podem ser tomadas dependem do estado observado do sis-
tema. Uma decisão leva (transforma) o estado do sistema, no qual ele se encontra no
presente estágio, para um novo estado no próximo estágio, e incorre-se em um custo
(Arenales et al. 2007).
Declaração das Variáveis
1. Estágio
2. Variável de estado (ex: ńıvel de estoque): xj (estado inicial - x0)
3. Label (marca, etiqueta, sinal): Fs(xj) = label da variável de estado xj no estágio s
(valor acumulado)
4. Variável de decisão: ys
5. Demanda do estado s : Ds
6. Forward (do começo para o final); backward (do fim para o começo)
7. Equação de recorrência (para calcular o label) do forward
Fs(xj) = max (ou min) {Fs−1(xk) + custo(xk, xj)} → ys(xj)
8. Equação de recorrência do backward
Fs(xj) = max (ou min) {Fs+1(xk) + custo(xk, xj)} → ys(xj)
9. Equiĺıbrio de massa
xs+1 = xs + ys −Ds
xs
ys
xs+1
Ds
10. Recuperação da trajetória no forward
x0, y1, x1, ..., yn−1, xn−1, yn, xn
7.2 Aplicação Prática 95
7.2 Aplicação Prática
Exemplo 7.1 Uma empresa precisa planejar a produção do seu produto para os próximos
quatro meses. Sua demanda é de: no 1◦ mês → 100 unidades, no 2◦ mês → 200 unidades,
no 3◦ mês → 200 unidades e no 4◦ mês→ 100 unidades.
Os custos de produção são apresentados na Tabela 7.1:
Produção/unidade Custo (R$)
0 50
100 90
200 120
300 140
Tabela 7.1: Demanda mensal.
Inicialmente a empresa dispõe de 100 unidades do produto e deseja anular o estoque ao final
do quarto mês.
Custo de estocagem / unidade por mês: $0,10.
Variável de estado - ńıvel do estoque.
Objetivo: atender a demanda solicitada.
1 2 3 4x0 = 100
y1
x1
D1 = 100
y2
x2
D2 = 200
y3
x3
D3 = 200
y4
0
D4 = 100
Estágio 1:
x1 x0 y1 Custo Total F1(x1) y1
0 100 0 10+50+0=60 60 0
100 100 100 10+90=100 100 100
200 100 200 10+120=130 130 200
300 100 300 10+140=150 150 300
Estágio 2:
7.2 Aplicação Prática 96
x2 x1 y2 Custo Total F2(x2) y2
0 0 200 60+120=180
100 100 10+100+90=200 180 200
200 0 20+130+50=200
300 - (inviável)
100 0 300 60+140=200
100 200 10+100+120=230 200 300
200 100 20+130+90=240
300 0 30+150+50=230
200 0 - -
100 300 10+100+140=250 250 300
200 200 20+130+120=270
300 100 30+150+90=270
300 200 300 20+130+140=290 290 300
300 200 30+150+120=300
Estágio 3:
x3 x2 y3 Custo Total F3(x3) y3
0 0 200 180+120=300
100 100 10+200+90=300 300 200
200 0 20+250+50=320
300 - (inviável)
100 0 300 180+140=320
100 200 10+200+120=330 320 300
200 100 20+250+90=360
300 0 30+290+50=370
Estágio 4:
x4 x3 y4 Custo Total F4(x4) y4
0 0 100 300+90=390
100 0 10+320+50=380 380 0
Recuperação da trajetória (Fazer Backward)
x4 y4 x3 y3 x2 y2 x1 y1 x0
0 0 100 300 0 200 0 0 100
x4 = x3 + y4 − 100
0 = x3 + 0− 100
x3 = x2 + y3 − 200
100 = x2 + 300− 200
7.3 Considerações Finais 97
x2 = x1 + y2 − 200
0 = x1 + 200− 200
x1 = x0 + y1 − 100
0 = x0 + 0− 100
7.3 Considerações Finais
A programação dinâmica é uma maneira esperta de transformar recursão em iteração com
o apoio de uma tabela (Salgado –).
O objetivo deste caṕıtulo foi uma breve apresentação sobre programação dinâmica.
7.4 Exerćıcios
1) Dado o seguinte grafo (Figura 7.1):
A
B
C
D
E
F
G
4
5
3
8
6 5
8
97
11
H
I
J
6
10
13
12
9
3
5
8
Figura 7.1: Grafo do Exerćıcio 1
Como este é um grafo em camadas, pode-se decompor o problema de encontrar o caminho
mais curto entre os vértices A e J em um processo de tomada de decisão multiestágio. As
decisões estão mostradas na Figura 7.2
A
B
C
D
E
F
G
4
5
3
8
6 5
8
97
11
H
I
J
6
10
13
12
9
3
5
8
3 2 14
Figura 7.2: Grafo do Exerćıcio 1
7.4 Exerćıcios 98
Utilizando Programação Dinâmica, encontre o caminho mı́nimo entre os nós A e J da
Figura 7.2.
2) Um caminhão pode transportar 10 toneladas de certo produto. Dispõe-se de 3 tipos de
produtos para expedição, A, B e C. Seus pesos e valores são dados pelo quadro:
Tipo Valor Peso (t)
A $20 1
B $50 2
C $60 2
Supondo que pelo menos um produto de cada tipo deve ser expedido, determine a compo-
sição da carga que maximizará o valor total utilizando os conceito de Programação Dinâmica.
3) Um fabricante de vagões ferroviários assina um contrato com uma empresa de transporte
ferroviário para o fornecimento de 100 vagões frigoŕıficos em um peŕıodo de 5 anos. Em janeiro
de cada ano é prevista a entrega de 20 vagões. O custo de produção anual por lote de 10
vagões, segundo as projeções do departamento de engenharia, deve variar como especificado
na tabela abaixo.
Produção anual 0 1 2 3 4 5
Custo (unidade monetária) 5 12 16 19 21 22
A capacidade de armazenagem do fabricante é de 4 lotes (40 vagões) sendo que a estocagem
consome em manutenção, mobilização da área e segurança, uma unidade monetária por lote
armazenado por ano.
O fabricante começa a produção em 10 de janeiro e termina em 31 de dezembro, seno
que os custos de armazenamento do lote ao longo do ano de produção já estão computados
na Tabela anterior. No ińıcio do contrato não existe qualquer vagão frigoŕıfico em esto-
que e não existe qualquer interesse em que permaneçam vagões após o término do contrato.
Estabeleça a poĺıtica ótima de produção, entrega e armazenagem para a indústria contratada.
4) A macaca Chita avisou a Tarzan que Jane se encontra prisioneira na cidade dos Gorilas.
Antes de seguir em encontro de Jane, Tarzan considerou todas às trajetórias de cipós dispo-
ńıveis, e os seus perigos no grafo adiante, onde os valores numéricos representam (em %) a
probabilidade de vir a ser morto por algum animal selvagem.
Sabendo que Tarzan foi educado na Inglaterra e que, portanto, sabe Programação Dinâ-
mica e não perderá a calma numa situação como essa, determine qual será a sua trajetória.
7.4 Exerćıcios 99
A
B
C
D
17
10
20
E
F
10
5
20
25
15
20
35
12
16
11
G
H
I
J
10
5
20
5) A demanda mensal de aço tipo A produzido por uma empresa siderúrgica precisa ser aten-
dida sem atrasos, sob pena de perda de vendas. A siderúrgica não dispõe, no momento, de
nenhum estoque desse tipo de aço, e tem conhecimento de que sua demanda para os próximosquatros meses é de 30, 20, 60 e 10, respectivamente. O custo de produção do aço tipo A
é constante durante os quatro meses e igual a $2 mil por tonelada produzida, enquanto o
custo de estocagem do aço de um mês para outro corresponde a 10% do custo de produção
do aço armazenado. Devido a restrições tecnológicas, a produção do aço tipo A precisa ser
feita em lotes e em quantidades predeterminadas múltiplas de 10 toneladas, ou seja, lotes
de tamanhos 10, 20, 30 toneladas, e assim por diante. Além disso, a cada lote produzido
independentemente de seu tamanho, incorre-se em um custo fixo de preparação de $10 mil.
Qual o plano de podução de aço tipo A que minimiza os custos de produção, estocagem e
preparação para esses quatro meses.
Obs.: O Exerćıcio 4 foi extráıdo do material do Prof. Fernando A. S. Marins (UNESP-
Guaratinguetá), enquanto que o Exerćıcio 5 de
http://wiki.icmc.usp.br/images/f/ff/7bb5dinamica mari.pdf.
Referências Bibliográficas
Arenales, M., Armentano, V., Morabito, R. e Yanasse, H. (2007). Pesquisa Operacional, Rio
de Janeiro: Elsevier.
Camponogara, E. (2006). Métodos de Otimização: teoria e prática, Notas de Aula: UFSC.
da Silva, E. M., da Silva, E. M., Gonçalves, V. e Murolo, A. C. (1998). Pesquisa Operacional,
Editora Atlas.
da Silva, E. M., da Silva, E. M., Gonçalves, V. e Murolo, A. C. (2010). Pesquisa Operacional:
para cursos de Administração e Engenharia, 4a edn, São Paulo: Editora Atlas.
dos Santos, M. P. (2000). Programação Linear: notas de aula, Universidade do Estado do
Rio de Janeiro.
Goldbarg, M. C. e Luna, H. P. L. (2005). Otimização Combinatória e Programação Linear,
Editora Campus: Rio de Janeiro.
Lachtermacher, G. (2009). Pesquisa Operacional na Tomada de Decisões, São Paulo: Pearson
Prentice Hall.
Moreira, D. A. (2007). Pesquisa Operacional: curso introdutório, São Paulo: Thomson
Learning.
Nogueira, F. (–). Programação Inteira - notas de aula, Universidade Federal de Juiz de Fora
- UFJF.
Ruggiero, M. A. G. e Lopes, V. L. R. (1996). Cálculo Numérico: Aspectos Teóricos e Com-
putacionais, 2a edn, São Paulo: Editora Person/Makron Books.
Salgado, L. (–). Programação Dinâmica: notas de aula, UFPE.
Taha, H. A. (2008). Pesquisa Operacional, São Paulo: Pearson Prentice Hall.
100