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égia