Introdução à Pesquisa Operacional

Prévia do material em texto

See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/305729897
INTRODUÇÃO À PESQUISA OPERACIONAL
Book · January 2010
CITATIONS
8
READS
11,192
2 authors, including:
Antonio C. Baleeiro Alves
Universidade Federal de Goiás
14 PUBLICATIONS   13 CITATIONS   
SEE PROFILE
All content following this page was uploaded by Antonio C. Baleeiro Alves on 31 July 2016.
The user has requested enhancement of the downloaded file.
https://www.researchgate.net/publication/305729897_INTRODUCAO_A_PESQUISA_OPERACIONAL?enrichId=rgreq-e939e5a57b50949f0e1349cca68b1518-XXX&enrichSource=Y292ZXJQYWdlOzMwNTcyOTg5NztBUzozODk5MDcyMTk1MzM4MjRAMTQ2OTk3MjUzMzU2MQ%3D%3D&el=1_x_2&_esc=publicationCoverPdf
https://www.researchgate.net/publication/305729897_INTRODUCAO_A_PESQUISA_OPERACIONAL?enrichId=rgreq-e939e5a57b50949f0e1349cca68b1518-XXX&enrichSource=Y292ZXJQYWdlOzMwNTcyOTg5NztBUzozODk5MDcyMTk1MzM4MjRAMTQ2OTk3MjUzMzU2MQ%3D%3D&el=1_x_3&_esc=publicationCoverPdf
https://www.researchgate.net/?enrichId=rgreq-e939e5a57b50949f0e1349cca68b1518-XXX&enrichSource=Y292ZXJQYWdlOzMwNTcyOTg5NztBUzozODk5MDcyMTk1MzM4MjRAMTQ2OTk3MjUzMzU2MQ%3D%3D&el=1_x_1&_esc=publicationCoverPdf
https://www.researchgate.net/profile/Antonio_Alves15?enrichId=rgreq-e939e5a57b50949f0e1349cca68b1518-XXX&enrichSource=Y292ZXJQYWdlOzMwNTcyOTg5NztBUzozODk5MDcyMTk1MzM4MjRAMTQ2OTk3MjUzMzU2MQ%3D%3D&el=1_x_4&_esc=publicationCoverPdf
https://www.researchgate.net/profile/Antonio_Alves15?enrichId=rgreq-e939e5a57b50949f0e1349cca68b1518-XXX&enrichSource=Y292ZXJQYWdlOzMwNTcyOTg5NztBUzozODk5MDcyMTk1MzM4MjRAMTQ2OTk3MjUzMzU2MQ%3D%3D&el=1_x_5&_esc=publicationCoverPdf
https://www.researchgate.net/institution/Universidade_Federal_de_Goias?enrichId=rgreq-e939e5a57b50949f0e1349cca68b1518-XXX&enrichSource=Y292ZXJQYWdlOzMwNTcyOTg5NztBUzozODk5MDcyMTk1MzM4MjRAMTQ2OTk3MjUzMzU2MQ%3D%3D&el=1_x_6&_esc=publicationCoverPdf
https://www.researchgate.net/profile/Antonio_Alves15?enrichId=rgreq-e939e5a57b50949f0e1349cca68b1518-XXX&enrichSource=Y292ZXJQYWdlOzMwNTcyOTg5NztBUzozODk5MDcyMTk1MzM4MjRAMTQ2OTk3MjUzMzU2MQ%3D%3D&el=1_x_7&_esc=publicationCoverPdf
https://www.researchgate.net/profile/Antonio_Alves15?enrichId=rgreq-e939e5a57b50949f0e1349cca68b1518-XXX&enrichSource=Y292ZXJQYWdlOzMwNTcyOTg5NztBUzozODk5MDcyMTk1MzM4MjRAMTQ2OTk3MjUzMzU2MQ%3D%3D&el=1_x_10&_esc=publicationCoverPdf
INTRODUÇÃO À
PESQUISA OPERACIONAL
Grão-Chanceler
Dom Washington Cruz, CP
Reitor
Prof. Wolmir Therezio Amado 
Editora da PUC Goiás
Pró-Reitora da Prope
Presidente do Conselho Editorial
Profa. Dra. Sandra de Faria
Coordenador Geral da Editora da PUC Goiás
Prof. Gil Barreto Ribeiro
Conselho Editorial
Membros
Profa. Dra. Regina Lúcia de Araújo
Prof. Dr. Aparecido Divino da Cruz
Profa. Dra. Elane Ribeiro Peixoto
Profa. Dra. Heloisa Capel
Profa. Dra. Maria do Espírito Santo Rosa Cavalcante
Prof. Dr. Cristóvão Giovani Burgarelli
Ms. Heloísa de Campos Borges
Iúri Rincon Godinho
Maria Luisa Ribeiro
Ubirajara Galli
ANTÔNIO CÉSAR BALEEIRO ALVES
MARCO ANTONIO FIGUEIREDO MENEZES
INTRODUÇÃO À
PESQUISA OPERACIONAL
Copyright © by Antônio César Baleeiro Alves; Marco Antonio Figueiredo Menezes
Editora da PUC Goiás
Rua Colônia, Qd. 240-C, Lt. 26 - 29
Chácara C2, Jardim Novo Mundo
CEP. 74.713-200 – Goiânia – Goiás – Brasil
Secretaria e Fax (62) 3946-1814 – Revistas (62) 3946-1815
Coordenação (62) 3946-1816 – Livraria (62) 3946-1080
Comissão Técnica
Nilton José Rodrigues
Revisão
Biblioteca Central da UCG
Normatização
Félix Pádua
Editoração e Capa
M. C. Escher. Cubic space division, litografia, 1952
Ilustração da Capa
Impresso no Brasil
A474i Alves, Antônio César Baleeiro
 Introdução à pesquisa operacional / Antônio César 
Baleeiro Alves e Marco Antonio Figueiredo Menezes. – 
Goiânia: Ed. da UCG, 2010.
 311 p.
 ISBN 978-85-7103-565-2
 1. Pesquisa operacional. 2. Modelagem. 3. Sistema 
linear. I. Menezes, Marco Antonio Figueiredo. II. 
Título.
CDU: 519.8 
Para minha esposa, Maria Abadia, e para os nossos filhos,
Flávio César, André Vinícius e Pedro.
Antônio César Baleeiro Alves
Para a minha esposa Greice e para a nossa filha Luana.
Marco Antonio Figueiredo Menezes
SUMÁRIO
Prefácio ..................................................................................................................11
I Modelagem em Pesquisa Operacional .........................................................15
1.1 O processo de modelagem .......................................................................15
1.2 Formulação de alguns problemas ...........................................................16
1.2.1 Um problema agrícola ....................................................................16
1.2.2 Um problema de designação ..........................................................20
1.2.3 Um problema de amplificador de tensão ......................................23
1.2.4 Formulação em processos estocásticos ..........................................25
1.3 Exercícios propostos .................................................................................27
II Matrizes e Sistemas Lineares ........................................................................31
2.1 Matrizes .....................................................................................................31
2.1.1 Operações com matrizes .................................................................34
2.1.2 Determinante ...................................................................................38
2.1.3 A inversa de uma matriz ................................................................46
2.1.4 Inversa de uma matriz e determinante .........................................47
2.2 Sistemas lineares algébricos de pequeno porte .....................................49
2.3 Operações elementares sobre matrizes ..................................................51
2.3.1 A forma escalonada .........................................................................54
2.3.2 Posto de uma matriz ........................................................................57
2.3.3 Matrizes elementares .......................................................................60
2.3.4 O método de Gauss-Jordan ............................................................62
2.4 Sistemas lineares algébricos .....................................................................65
2.4.1Sistemas homogêneos .......................................................................68
2.4.2 Sistemas triangulares .......................................................................70
2.4.3 O método de eliminação de Gauss ................................................73
– 8 –
2.4.4 Decomposição LU de matrizes quadradas ...................................77
2.5 Exercícios propostos .................................................................................90
III Programação Linear .......................................................................................95
3.1 O problema de Programação Linear .....................................................95
3.1.1 Obtenção do formato padrão .........................................................96
3.2 A geometria da Programação Linear.....................................................98
3.3 Método simplex primal ..........................................................................106
3.3.1 Mecanismo de mudança de base ..................................................113
3.3.2 O algoritmo simplex ......................................................................121
3.4 Dualidade em Programação Linear .....................................................127
3.4.1 Forma canônica da dualidade ......................................................129
3.4.2 Relações entre os problemas primal e dual .................................130
3.4.3 Relações entre as soluções ótimas dos problemas primal e dual ..134
3.4.4 Regras de escrita do problema dual a partir de um
 problemaprimal ............................................................................137
3.4.5 O teorema fundamental da dualidade ........................................139
3.4.6 Condições de Karush-Kuhn-Tucker para a Programação Linear ...139
3.4.7 Método dual simplex ..........................................................................140
3.5 Exercícios propostos ...............................................................................143
IV Distribuições de Probabilidade ...................................................................147
4.1 Probabilidade ..........................................................................................148
4.1.1 Probabilidade e frequência relativa .............................................152
4.2 Variável aleatória discreta......................................................................153
4.2.1 Esperança matemática e variância de uma variável
 aleatória discreta ............................................................................156
4.3 Distribuições de probabilidade de variáveis aleatórias discretas ......157
4.3.1 Distribuição hipergeométrica .......................................................157
4.3.2 Distribuição binomial ....................................................................159
4.3.3 Distribuição uniforme discreta ....................................................161
– 9 –
4.3.4 Distribuição de Poisson .................................................................163
4.4 Variável aleatória contínua ....................................................................166
4.5 Distribuições de probabilidade de variáveis aleatórias contínuas ....170
4.5.1 Distribuição normal ......................................................................171
4.5.2 Distribuição retangular ou uniforme ..........................................179
4.5.3 Distribuição exponencial ..............................................................180
4.5.4 Distribuição de Erlang ..................................................................182
4.6 Teorema do limite central .....................................................................184
4.7 Exercícios propostos ...............................................................................188
V Processos de Markov ....................................................................................191
5.1 Def inição e caracterização de processos de Markov ..........................191
5.2 Relevância dos processos de Markov e possíveis aplicações ..............193
5.3 Processos de Markov de tempo discreto ..............................................194
5.3.1 Matriz de transição ........................................................................200
5.3.2 Cadeias de Markov ........................................................................202
5.3.3 Classificação das cadeias de Markov ...........................................203
5.3.4 Análise de cadeias finitas irredutíveis
 com estados aperiódicos ................................................................211
5.3.5 Análise de cadeias finitas com estados absorventes ...................216
5.3.6 Tempos médios de recorrência .....................................................223
5.4 Processos de Markov de tempo contínuo ............................................227
5.4.1 Cadeias de Markov homogêneas de tempo contínuo ................231
5.5 Exercícios propostos ...............................................................................243
VI Sistemas de Filas de Espera .........................................................................247
6.1 Elementos básicos de sistemas de f ilas e notação de Kendall-Lee ....248
6.2 Conceitos básicos e parâmetros de sistemas de f ilas ...........................251
6.3 Medidas de efetividade dos sistemas de f ilas .......................................256
6.3.1 Fórmula de Little ...........................................................................257
6.4 Sistemas de f ilas com chegadas e atendimentos do tipo markoviano .....258
– 10 –
6.4.1 Sistema de filas M / M / 1 ..............................................................259
6.4.2 Sistema de filas M / M / s ...............................................................268
6.4.3 Sistema de filas M / M / 1 / C ........................................................272
6.5 Relevância da teoria de filas em sistemas de comunicação ................279
6.6 Exercícios propostos ...............................................................................280
VII Simulação Monte Carlo ..............................................................................285
7.1 Geração de números aleatórios .............................................................287
7.2 Simulação Monte Carlo através da utilização de etiquetas ...............289
7.2.1 Exemplo em Programação Linear ...............................................293
7.2.2 Exemplo em sistemas de filas de espera ......................................294
7.3 Número de simulações necessárias para assegurar
 um erro máximo especif icado ...............................................................296
7.3.1 Confiança e intervalo de confiança ..............................................297
7.3.2 Fórmula para cálculo do número de simulações .......................299
7.4 Simulação Monte Carlo aplicada à solução
 de problema determinístico ...................................................................300
7.5 Exercícios propostos ...............................................................................303
Referências ..........................................................................................................309
– 11 –
S egundo a Sociedade Brasileira de Pesquisa Operacional (SOBRAPO) – www.sobrapo.org.br/o_que_e_po.php –, a Pesquisa Operacional é uma 
ciência aplicada voltada para a resolução de problemas reais que, tendo como 
foco a tomada de decisões, aplica conceitos e métodos de várias áreas científi-
cas na concepção, no planejamento ou na operação de sistemas.
O presente livro apresenta uma introdução ao estudo da Pesquisa Ope-
racional. Baseia-se em cursos que ministramos, nos quais optamos por abor-
dar aqueles temas que, do nosso ponto de vista, fornecem o embasamento 
necessário em modelos determinísticos e probabilísticos para a formação de 
graduandos e pós-graduandos. Atuamos em cursos de graduação em Ciência 
da Computação, Engenharia de Computação, Engenharia Elétrica, Enge-
nharia de Produção e em cursos de mestrado em Engenharia Elétrica e de 
Computação, e Engenharia de Produção e Sistemas. Aqui, incluímos ainda 
a importância para a formação de futuros profissionais de Administração, 
Agronomia, Economia, Estatística e Matemática. Dessa forma, acreditamos 
que este livro pressupõe conhecimentos de programação de computadores 
e de conteúdo de Matemática equivalente ao estudado no primeiro ano de 
cursos de graduação, principalmente, nas áreas de ciências exatas, engenha-
rias e áreas correlatas. A propósito, acreditamos que o diferencial deste livro 
está na forma como os temas são apresentados: primeiro, são estabelecidos 
os conceitos, as definições, as terminologias, para, em um segundo momen-
to, apresentarem-se os procedimentos de cálculo. Ressaltamos, além disso, 
o apelo ao uso do computador, por meio de enunciados de algoritmos e da 
proposição de exercícios.
PREFÁCIO
– 12 –
No Capítulo I, tratamos sobre o processo de modelagem. Em particular, 
sobre a etapa de formulação de problemas. Formulamos problemas de Pro-
gramação Linear, Programação Linear Inteira e de Programação Não Linear, 
e discutimos modelos estocásticos.
No Capítulo II, tratamos sobre matrizes e sistemas lineares e, no Capí-
tulo IV, sobre distribuições de probabilidade. Ambos possuem o caráter de 
revisão de conteúdos para facilitar a compreensão dos temas abordados nos 
capítulos de soluções de modelos.
Introduzimosmodelos determinísticos no Capítulo III, em que trata-
mos sobre Programação Linear, enfatizando os seus fundamentos primal e 
dual, e o método simplex. Omitimos o método de pontos interiores que se 
mostra eficiente – algoritmos polinomiais – para os problemas de Programa-
ção Quadrática, Complementaridade Linear e Programação Semidefinida, 
todos sob certas hipóteses. Todavia, fazemos referência ao Laboratório de 
Programação Linear (LabPL), que possui, além da família de métodos de 
pontos interiores, várias outras famílias de métodos para resolver problemas 
de Programação Linear.
Nos demais capítulos, são apresentados modelos probabilísticos e simu-
lação. No Capítulo V, tratamos sobre processos de Markov com vistas à sua 
aplicação aos sistemas de filas. Os sistemas de filas markovianos são estudados 
no Capítulo VI, e a simulação de Monte Carlo, no Capítulo VII.
A notação utilizada no livro é independente por capítulo. Isto quer di-
zer, por exemplo, que vetores podem aparecer em parênteses em um capítulo, 
ou em colchetes em outro; S, como um conjunto qualquer em um capítulo, 
ou como um espaço amostral em outro; A, como uma matriz qualquer em 
um capítulo, ou como um conjunto de eventos; Z+, o conjunto dos números 
inteiros não negativos em um capítulo, ou Z, como uma variável aleatória da 
distribuição normal padronizada em outro; e, como o número de Euler em 
um capítulo, ou como um número qualquer em outro etc.
Este livro teve seus primeiros manuscritos preparados há vários anos, 
tendo iniciado por volta de 1999. De lá para cá demos vários cursos baseados 
em vários livros como referências básicas. Assim, vários exemplos foram re-
tirados dessas referências e alterados, melhorados. Criamos outros a partir 
desses, desenvolvemos novos. Dessa forma, no que nos foi possível, fizemos 
referência in loco dos exercícios que são de autoria de colegas e, na seção 7.2, 
em particular, referenciamos o livro que apresenta a mesma sequência de ra-
ciocínio e abordagem. 
– 13 –
Iniciamos a escrita deste livro propriamente dita através de um projeto 
entre Baleeiro, Marco e Francisco José Pfeilsticker Zimmermann. Este estu-
dou e nos apresentou o artigo de Wichmann e Hill sobre a geração de núme-
ros aleatórios e foi também quem revisou e discutiu as primeiras versões do 
ainda manuscrito. Agradecemos com carinho ao nosso colega e amigo Zim-
mermann pelas contribuições e pelo estímulo, pois, mesmo em Moçambique, 
ainda pergunta sobre o livro.
Em particular, Baleeiro agradece ao Professor Fujio Sato, pelas primei-
ras lições de Monte Carlo, e também ao Professor Rubén Augusto Romero 
Lázaro, pelas excelentes discussões em Otimização.
Agradecemos aos colegas professores: Edir Lopes de Oliveira, José Elmo 
de Menezes, Leizer de Lima Pinto, Rosângela Nunes Almeida de Castro e 
Thyago Carvalho Marques pelas contribuições valiosas. Não poderíamos nos 
esquecer de reconhecer o profissionalismo com que Nilton José Rodrigues e 
Félix Pádua trataram a revisão e a diagramação do texto e ao coordenador 
geral da Editora da PUC Goiás, o professor Gil Barreto Ribeiro pela atenção. 
Um especial agradecimento a nossos alunos de turmas de outrora que, ao ex-
ternarem suas críticas e dúvidas, trouxeram importantes contribuições.
Os Autores
– 15 –
I
Modelagem em Pesquisa Operacional
N este capítulo será estudado o processo de modelagem em Pesquisa Operacional (PO). O objetivo aqui não é obter soluções de problemas 
de PO, mas modelar problemas, em contraposição ao uso apenas da experiên-
cia e do bom senso.
Como referências básicas, sugerimos Hillier & Lieberman (1995) e 
Taha (2008).
A inf luência da Segunda Guerra Mundial foi decisiva para o res-
surgimento da PO, e os desenvolvimentos que se seguiram nas décadas 
que sucederam ao grande conf lito são devidos especialmente à difusão 
do computador nas universidades e empresas. Havia demandas da parte 
da indústria e dos governos – transportar, planejar, interceptar etc. Novos 
conhecimentos em Matemática, Engenharia, Estatística, Economia e Com-
putação eram publicados, e f inanciamentos de pesquisa nesta área de co-
nhecimento surgiam. O projeto Scientif ic Computation of Optimal Programs 
é um exemplo de relevante f inanciamento ocorrido na ocasião, que resultou 
na formação de um grupo para pesquisar a viabilidade em aplicar a Mate-
mática e técnicas correlacionadas à análise de problemas de planejamento e 
programação militar.
 
 
1.1 O processo de modelagem
 
Os responsáveis pela tomada de decisões nos mais variados campos da 
atividade humana defrontam-se com a necessidade de resolver algum pro-
– 16 –
blema específ ico de PO. A compreensão e a def inição do problema são de 
fundamental importância para o processo de modelagem.
O primeiro passo para a resolução de um problema de PO é a formu-
lação, que consiste em traduzir a realidade empírica para sentenças lógicas e 
dados objetivos, a partir dos quais é possível o estabelecimento de um modelo 
matemático. É aí que devemos decidir – julgamento humano – os aspectos do 
sistema real que devemos incorporar ao modelo e os que podem ser ignora-
dos, as suposições que podem ser consideradas e as que podem ser descarta-
das. Essa tradução está sujeita a erros e falhas de comunicação. Também não 
existem técnicas precisas, capazes de permitir o estabelecimento do modelo 
de um problema. 
O segundo passo é a dedução do modelo, isto é, a sua análise e resolução 
através de algoritmos específ icos. Essa solução, atenta aos métodos numéricos 
em computação, sugere uma tomada de decisão. Para a sua sustentação, recor-
remos ao terceiro passo, que é a interpretação de uma solução do modelo para 
uma solução do sistema real. Se não for validado, o modelo deve ser reformu-
lado, e assim por diante. A esse processo dá-se o nome de modelagem. Para 
maiores detalhes sobre o processo de modelagem, recomendamos Ravindran, 
Phillips & Solberg (1987).
A seguir, estudaremos o primeiro passo do processo, ou seja, a formula-
ção em Programação Matemática e exemplos de modelos probabilísticos, sem 
nos preocuparmos com a solução ou a validação.
1.2 Formulação de alguns problemas
Nesta seção, serão estudados três problemas de PO. Um da área agríco-
la, outro de administração e um de eletricidade. Também serão vistos alguns 
processos estocásticos. Em cada subseção, será enunciado um problema de PO 
e seu modelo correspondente. Ao f inal, com relação aos modelos probabilísti-
cos, apenas serão enunciados alguns problemas.
1.2.1 Um problema agrícola
Este problema foi extraído de Müller (2004) e trata da elaboração de um 
modelo de Programação Linear para planejamento de produção agrícola.
– 17 –
1.2.1.1 O problema
Consideremos um problema na agricultura para decidir que produtos e em 
que quantidade entre soja, milho, arroz e feijão devem ser plantados em uma 
determinada área, de forma a maximizar o lucro líquido de um produtor rural.
Esse produtor precisa colher no mínimo 2.500 sacas de soja, para produ-
zir semente encomendada; 3.000 sacas de milho, para pagar empréstimo em 
milho à cooperativa local; pretende plantar, no mínimo, 150 hectares de arroz 
em terra de primeiro ano (fraca) e, no máximo, 80 hectares de feijão, plantio 
de alto risco de perda, pois prefere, neste ano, não arriscar muito. A tabela 1.1 
resume os dados do problema.
Tabela 1.1: Dados gerais do problema
Gleba
Tamanho
(hectare)
Produção esperada
(sacas/hectare)
Renda líquida esperada
(reais/hectare)
Soja Milho Arroz Feijão Soja Milho Arroz Feijão
1 10 50 130 30 40 1.200 1.040 240 1.450
2 18 48 120 32 55 1.080 910 300 3.380
3 22 48 140 30 43 1.065 1.728 300 1.890
4 49 50 100 28 38 1.320 700 280 1.220
5 51 35 70 36 32 365 -120 600 610
6 54 32 65 37 30 160 -380 595 280
7 77 35 68 37 32 360 -171 620 585
8 69 38 95 39 36 610 410 665 900
Mínimo
(sacas ou hectares)
2.500
(sacas)
3.000
(sacas)
150
(hectares)
Máximo
(hectares)
80
(hectares)
Na tabela 1.1, “Produção esperada” diz respeito ao que se espera,em 
sacas por hectare, de cada gleba (porção de terra) para o cultivo de cada um 
dos alimentos. A “Renda líquida esperada” é a diferença entre o custo de 
produção e a renda bruta esperada por hectare. As duas últimas linhas for-
mam o conjunto de restrições imposto pelo proprietário da fazenda, que cor-
– 18 –
Neste caso, def inimos x
ij
, i = 1, 2, ..., 8 e j = 1, 2, 3, 4, as variáveis de deci-
são que pretendemos encontrar, se existirem, a saber: x
ij
, é a área em hectare por 
região i (i = 1, 2, ..., 8) para o plantio do alimento j ( j = 1, soja; j = 2, milho; j 
= 3, arroz; e j = 4, feijão). Como o que interessa é a maximização da renda da 
fazenda, serão utilizados os dados da “Renda líquida esperada” da tabela 1.1 
para construir o valor da chamada função objetivo do problema, a saber:
11 12 13 14
21 22 23 24
31 32 33 34
41 42 43 44
51 52 53 54
61 62 63 64
71 72
1200 1040 240 1450
1080 910 300 3380
1065 1728 300 1890
1320 700 280 1220
365 120 600 610
160 380 595 280
360 171 62
x x x x
x x x x
x x x x
x x x x
x x x x
x x x x
x x
+ + + +
+ + + + +
+ + + + +
+ + + + +
+ − + + +
+ − + + +
+ − + 73 74
81 82 83 84
0 585
610 410 665 900 .
x x
x x x x
+ +
+ + + +
O objetivo de maximização está sujeito a algumas restrições. A soma das 
áreas para o plantio dos quatro produtos em cada gleba não pode ultrapassar 
o tamanho total da gleba. Tem-se, então:
responde ao mínimo ou ao máximo de sacas que deseja colher de um certo 
tipo de produto, ou ao mínimo ou ao máximo de terra (em hectares) que 
deseja plantar.
1.2.1.2 Um modelo
Como já af irmamos, não existem regras precisas para o processo de mo-
delagem. Por isso, sugerimos a tentativa de encontrar inicialmente as variá-
veis de decisão. Também recomendamos verif icar as unidades de grandeza de 
cada dado, inclusive das variáveis de decisão.
– 19 –
11 12 13 14
21 22 23 24
31 32 33 34
41 42 43 44
51 52 53 54
61 62 63 64
71 72 73 74
81 82 83 84
10
18
22
49
51
54
77
69.
x x x x
x x x x
x x x x
x x x x
x x x x
x x x x
x x x x
x x x x
+ + + ≤
+ + + ≤
+ + + ≤
+ + + ≤
+ + + ≤
+ + + ≤
+ + + ≤
+ + + ≤
Consideremos, ainda, que não pode haver área negativa para plantio. 
Para isso, temos:
0, 1, 2, , 8ijx i≥ = � e 1, 2, 3, 4j = .
Finalmente, devemos considerar as restrições impostas pelo proprietário 
da fazenda – produção para atendimento de encomenda, para pagamento de 
empréstimo e adequação às condições de qualidade do solo e risco de perdas 
em relação ao feijão. Assim, obtemos as seguintes desigualdades:
11 21 31 41 51 61 71 8150 48 48 50 35 32 35 38 2500x x x x x x x x+ + + + + + + ≥ ,
12 22 32 42 52 62 72 82130 120 140 100 70 65 68 95 3000x x x x x x x x+ + + + + + + ≥ , 
13 23 33 43 53 63 73 83
14 24 34 44 54 64 74 84
150
80.
x x x x x x x x
x x x x x x x x
+ + + + + + + ≥
+ + + + + + + ≤
e
Portanto, o nosso modelo matemático que tenta traduzir uma particular 
realidade da agricultura é dado pelo problema de PO:
maximizar
11 12 13 14
21 22 23 24
31 32 33 34
41 42 43 44
51 52 53 54
61 62 63 64
71 72
1200 1040 240 1450
1080 910 300 3380
1065 1728 300 1890
1320 700 280 1220
365 120 600 610
160 380 595 280
360 171 62
x x x x
x x x x
x x x x
x x x x
x x x x
x x x x
x x
+ + + +
+ + + + +
+ + + + +
+ + + + +
+ − + + +
+ − + + +
+ − + 73 74
81 82 83 84
0 585
610 410 665 900
x x
x x x x
+ +
+ + + +
– 20 –
sujeito a: 11 12 13 14
21 22 23 24
31 32 33 34
41 42 43 44
51 52 53 54
61 62 63 64
71 72 73 74
81 82 83 84
10,
18,
22,
49,
51,
54,
77,
69,
x x x x
x x x x
x x x x
x x x x
x x x x
x x x x
x x x x
x x x x
+ + + ≤
+ + + ≤
+ + + ≤
+ + + ≤
+ + + ≤
+ + + ≤
+ + + ≤
+ + + ≤
11 21 31 41 51 61 71 8150 48 48 50 35 32 35 38 2500x x x x x x x x+ + + + + + + ≥
12 22 32 42 52 62 72 82130 120 140 100 70 65 68 95 3000x x x x x x x x+ + + + + + + ≥
13 23 33 43 53 63 73 83
14 24 34 44 54 64 74 84
150 e
80,
x x x x x x x x
x x x x x x x x
+ + + + + + + ≥
+ + + + + + + ≤
0, 1, 2, , 8ijx i≥ = � e 1, 2, 3, 4j = .
A formulação discutida nesta seção refere-se a um modelo com fun-
ções af ins, isto é, lineares. Desta forma, chama-se este problema agrícola 
de Problema de Programação Linear (Contínua), que estudaremos no Ca-
pítulo III. 
1.2.2 Um problema de designação
O problema de designação (assignment problem, em inglês) é um proble-
ma clássico de Programação Linear Inteira.
1.2.2.1 O problema
Quatro pessoas – A, B, C e D – estão designadas para trabalhar em qua-
tro projetos diferentes – 1, 2, 3 e 4. A tabela 1.2 mostra quanto tempo – em 
dias – cada pessoa consegue f inalizar um específ ico projeto.
– 21 –
Tabela 1.2: Dados gerais do problema
Pessoas
Projetos
1 2 3 4
A 5 6 7 4
B 6 5 8 4
C 6 8 9 5
D 7 6 6 3
O pagamento diário, por pessoa, em uma jornada de quatro horas, é de 
60 reais. Suponha que cada pessoa é designada para realizar um projeto, e 
cada projeto só pode ser realizado por uma única pessoa.
1.2.2.2 Um modelo
Neste caso, def inimos ijx , 1, 2, 3, 4i = e j = 1, 2, 3, 4, as variáveis de 
decisão que pretendemos encontrar, se existirem, a saber: 
ijx =
 
Nosso interesse agora é minimizar o custo para a execução dos projetos. 
Assim, utilizamos os dados da tabela 1.2 para construir o valor da função 
objetivo, a saber:
60 5 6 7 4
6 5 8 4
6 8 9
11 12 13 14
21 22 23 24
31 32 3
( x x x x
x x x x
x x x
+ + + +
+ + + + +
+ + + 33 34
41 42 43 44
5
7 6 6 3
+ +
+ + + +
x
x x x x ).
Nosso objetivo de minimização está sujeito a algumas restrições. Sabe-
mos que cada pessoa é designada para realizar um único projeto, isto é,
1, se a pessoa i (i = 1, pessoa A ; i = 2, pessoa B; i = 3, pessoa C e i = 4, 
 pessoa D) for designada para o projeto j (j = 1, 2, 3, 4)
0, caso contrário.
1, se a pessoa i for (i = 1, pessoa ; i = 2, pessoa B; i = 3, pessoa C e i = 4, pessoa D)
 designada para o projeto jj=1, 2, 3, 4
0, caso contrÆrio.




– 22 –
4
1
1ij
j
x
=
=∑ , i = 1, 2, 3, 4;
e que cada projeto só pode ser realizado por uma única pessoa, isto é, 
xij
i=
∑ =
1
4
1 , j = 1, 2, 3, 4.
Portanto, o nosso modelo matemático que tenta traduzir uma particular 
realidade do problema de designação é dado pelo problema de PO:
minimizar
11 12 13 14
21 22 23 24
31 32 33 34
41 42 43 44
60 ( 5 6 7 4
6 5 8 4
6 8 9 5
7 6 6 3 )
x x x x
x x x x
x x x x
x x x x
+ + + +
+ + + + +
+ + + + +
+ + + +
sujeito a: 4
1
1ij
j
x
=
=∑ , i = 1, 2, 3, 4 
xij
i=
∑ =
1
4
1 , j = 1, 2, 3, 4
{ }0, 1ijx ∈ , i = 1, 2, 3, 4 e j = 1, 2, 3, 4.
A formulação discutida nesta seção recebe o nome de Problema de Pro-
gramação Linear Inteira, por tratar-se de um modelo com funções lineares cujas 
variáveis de decisão são inteiras. Esse assunto não será objeto de estudo neste 
livro. Todavia, para os leitores interessados em aprofundar seus conhecimen-
tos nessa área, sugerimos os livros de Goldbarg & Luna (2005), Foulds (1984) e 
Garf inkel & Nemhauser (1972).
– 23 –
1.2.3 Um problema de amplif icador de tensão
A seguir apresentamos um problema de otimização que envolve um cir-
cuito elétrico.
1.2.3.1 O problema
Em Engenharia Elétrica é comum a utilização de circuitos amplif ica-
dores em aparelhos de áudio e vídeo. Esses circuitos recebem em sua entrada 
uma tensão elétrica e aumentam sua amplitude, disponibilizando na saída um 
sinal elétrico amplif icado.
O circuito da f igura 1.1 mostra de maneira simplif icada um amplif ica-
dor em que os estágios de entrada e saída são representados, respectivamente, 
por uma fonte de tensão, v, e por uma resistência de carga, cR , igual a 10 Ω 
( V AΩ = ). Esse circuito, para certos valores do parâmetro α, comporta-se 
como um amplif icador de tensão. Devem ainda ser respeitados os limites in-
ferior e superior de 12 V e 30 V , respectivamente, para a tensão na resistência 
de carga 10c cv i= .
Figura 1.1: Circuito básico para amplif icação da tensão v
– 24 –
A tensão abv é igual a 
61 10 i× , isto é, a queda de tensão no resistor de1 MΩ . A tensão v da fonte está restrita aos limites inferior e superior, res-
pectivamente, de 340 mV e 500 mV . O parâmetro α deve ser no mínimo 
igual a 120.
1.2.3.2 Um modelo
Neste caso, def inimos as variáveis de decisão que se pretende encontrar, 
se existirem, a saber:
i : corrente elétrica em amperes (A) suprida pela fonte;
ci : corrente elétrica em amperes (A) no lado da carga;
 v: tensão elétrica da fonte em volts (V);
α : parâmetro de controle da fonte dependente, que é adimensional.
O nosso interesse é operar o circuito da f igura 1.1 minimizando a perda 
de energia elétrica em watts (W = VA) nos resistores de resistências 0,7 MΩ, 
1 MΩ e 5 Ω, a saber:
6 2 21,7 10 5 ci i× + .
Na expressão da perda de energia elétrica não está incluída a resistência 
R
c
, porque esta representa a carga do circuito.
Nosso objetivo de minimização está sujeito a algumas restrições. De 
acordo com a Segunda Lei de Kirchhoff, que estabelece que a tensão aplicada 
a qualquer percurso fechado de um circuito é igual ao somatório das quedas 
de tensão naquele percurso, temos:
6 60,7 10 1,7 10abv i v i= × + = × ,
substituindo 61 10abv i= × . 
Procedendo de modo análogo para analisar o percurso fechado em que 
se encontra a resistência de carga, obtemos:
5ab c cv i vα = + .
– 25 –
Substituindo 10c cv i= e 
61 10abv i= × na última igualdade e desenvol-
vendo, obtemos
610 15 0ci iα − = .
Além disso, foi dado que:
0, 34 0,50v≤ ≤
e
12 10 30c cv i≤ = ≤ .
Dividindo essa última dupla desigualdade por dez, obtemos:
1, 2 3ci≤ ≤ .
Portanto, o nosso modelo matemático que tenta traduzir uma particular 
realidade do problema de minimização das perdas em um circuito amplif ica-
dor de tensão é dado pelo problema de PO:
minimizar 
6 2 21,7 10 5 ci i× +
sujeito a: 
61,7 10 0v i− × =
 
610 15 0ci iα − =
 1, 2 3ci≤ ≤
 0, 34 0,50v≤ ≤
 120α ≥ .
A formulação discutida nesta seção refere-se a um modelo com pelo me-
nos uma função não linear. Desta forma, chamamos este problema de am-
plif icador de tensão de um problema de Programação Não Linear, que não 
será objeto de estudo neste livro. Todavia, sugerimos a leitura de Bazaraa, 
Sherali & Shetty (2006) e Luenberger (2003).
1.2.4 Formulação em processos estocásticos
Processos estocásticos ou modelos probabilísticos são modelos mate-
máticos desenvolvidos para analisar sistemas dinâmicos sujeitos a incerteza, 
– 26 –
usando-se a linguagem da probabilidade. O termo “dinâmico” signif ica que a 
variável tempo geralmente está envolvida no processo de formulação. A prin-
cipal característica de um problema estocástico é que, associado a pelo menos 
uma de suas variáveis, temos um número que mede o grau de incerteza – ou 
de certeza – da ocorrência do valor da variável, dado pela probabilidade.
A formulação em processos estocásticos normalmente compreende a 
elaboração de sentenças lógicas, a interpretação de dados estatísticos sobre o 
problema e a identif icação da distribuição de probabilidade que governa as 
variáveis. Depois de construído, o modelo pode admitir soluções analíticas. 
Em casos de problemas complexos, a simulação computacional tem-se mos-
trado a melhor alternativa.
No Capítulo IV, serão estudadas distribuições de probabilidades. Assim, 
o passo da formulação será substituído pela descrição em linguagem natural 
para processos de Markov (Capítulo V), sistemas de f ilas de espera (Capítulo 
VI) e simulação Monte Carlo (Capítulo VII).
1.2.4.1 Processos de Markov
Muitos processos que ocorrem em sistemas reais podem ser estudados 
como se o sistema sob análise passasse, a partir de um estado inicial, por uma 
sequência de estados em que a transição de um determinado estado para o 
seguinte ocorreria segundo uma certa probabilidade. No caso em que essa 
probabilidade de transição depende apenas do estado em que o fenômeno se 
encontra e do estado a seguir, o processo será designado processo de Markov 
de primeira ordem, e uma sequência de estados seguindo esse processo será 
denominada cadeia de Markov.
Um conceito fundamental em processos de Markov é a noção de esta-
do. Propriedades em comum entre indivíduos ou objetos caracterizam o que 
chamamos de estado. Podemos apontar associações entre propriedade em co-
mum e estado: uma população da Região Norte que migra para o Sul; veícu-
los estacionados numa determinada área; máquinas numa grande linha de 
produção etc.
1.2.4.2 Sistemas de f ilas de espera
Um processo de f ilas consiste na chegada de usuários, por exemplo, 
a um estabelecimento de prestação de serviços e a consequente espera ali-
– 27 –
nhados em f ila. O usuário que chega ao estabelecimento ou aguarda aten-
dimento, se todos os atendentes estiverem ocupados, ou é prontamente 
atendido em caso contrário. Após receber o serviço, o usuário deixa o esta-
belecimento.
1.2.4.3 Simulação Monte Carlo
A simulação consiste em reproduzir o funcionamento de um sistema com 
o auxílio de um modelo. Toda simulação requer a construção de um modelo 
com o qual são feitos experimentos. No presente caso, esse modelo é def inido 
por um conjunto de relações lógico-matemáticas descritas geralmente por um 
programa de computador. A partir do modelo, as simulações permitirão testar 
algumas hipóteses sobre o valor de variáveis controladas. As conclusões são 
usadas, então, para melhorar o desempenho do sistema em estudo, proporcio-
nando suporte bem fundamentado para a tomada de decisões.
A simulação computacional surgiu a partir da ideia do Método Monte Carlo, 
durante uma conferência em Los Alamos, nos Estados Unidos, após a Segunda 
Guerra Mundial. Naquela ocasião, após serem apresentadas as experiências 
adquiridas com o ENIAC – Electronic Numerical Integrator Analyser and Computer 
–, Stanislaw Ulam pressentiu a potencialidade da nova máquina para técnicas de 
amostragem estocástica. John Von Neumann, pioneiro da Computação, também 
presente na conferência, foi um dos precursores desse método. Monte Carlo baseia-
se essencialmente na geração intensiva de números aleatórios para a solução por 
simulação computacional de problemas estocásticos (ULAM; RICHTMEYER; 
NEUMANN, 1947; METROPOLIS; ULAM, 1949).
Número aleatório é um número de uma sequência, cuja probabilidade 
de ocorrência é a mesma que a de qualquer outro. Métodos de simulação de 
problemas probabilísticos – não determinísticos – exigem a geração de núme-
ros aleatórios.
1.3 Exercícios propostos
1. (BOLDRINI et al., 1986) A Companhia Sovina de Investimentos possui seis 
milhões de reais, quantia que deverá ser aplicada em cinco tipos de investimen-
tos. Os retornos anuais para cada investimento são: investimento 1 (I
1
), 10%; 
investimento 2 ( 2I ), 8%; investimento 3 ( 3I ), 6%; investimento 4 ( 4I ), 5%; e 
investimento 5 ( 5I ), 9%.
– 28 –
O gerente dessa companhia deseja diversif icar os investimentos para ob-
ter o máximo de rendimento possível. Dado o elemento de risco envolvido, 
o gerente restringiu a quantia a ser aplicada em I
1
 a não mais que a soma das 
quantias aplicadas em 3I , 4I e I5. O total a ser aplicado em 2I e 5I , em con-
junto, deve ser pelo menos igual à quantia aplicada em 3I . O 2I deve estar 
limitado a um nível que não exceda à quantia aplicada em 4I . 
É preciso determinar a alocação ótima de investimento entre as cinco 
categorias, de forma que o retorno ao f inal do ano seja o máximo possível. 
Formular o problema.
2. (BOLDRINI et al., 1986) Uma empresa nacional possui fábricas em Cam-
pinas (SP) e em Belo Horizonte (MG). Essa empresa produz e distribui com-
putadores a comerciantes de várias cidades. Em uma determinada semana, 
a empresa tem em estoque: 30 unidades em Campinas e 40 em Belo Hori-
zonte. Nessa mesma semana, a empresa deve atender os seguintes pedidos: 
20 unidades para São Paulo (SP), 25 unidades para o Rio de Janeiro (RJ) e 25 
unidades para Vitória (ES). O problema consiste em distribuir as máquinas 
aos comerciantes de forma a atender os pedidos a um custo mínimo detrans-
porte. Os custos unitários de transporte são R$ 9,00 de Campinas para São 
Paulo; R$ 16,00, de Campinas para o Rio de Janeiro; R$ 25,00, de Campinas 
para Vitória; R$ 27,50 de Belo Horizonte para São Paulo; R$ 22,50 de Belo 
Horizonte para o Rio de Janeiro e R$ 21,00 de Belo Horizonte para Vitória. 
Formular o problema.
3. (HILLIER; LIEBERMAN, 1995) Uma multinacional decide instalar-se 
em Goiás e deve escolher, entre os municípios de Catalão e Rio Verde, aquele 
em que irá construir a fábrica e o armazém. A construção de fábricas e ar-
mazéns nessas cidades resulta nos índices de retornos indicados na tabela 1.3.
Tabela 1.3: Índices de retorno em unidades monetárias
Catalão Rio Verde
Fábrica 72 40
Armazém 48 32
– 29 –
Os seguintes critérios devem ser respeitados no processo de decisão: 
deverá ser escolhida apenas uma cidade para a construção da fábrica e do 
armazém; em unidades monetárias, o investimento requerido na construção 
de uma fábrica em Catalão é de 48 e em Rio Verde é de 24. O investimento 
requerido na construção de um armazém em Catalão é de 40 e em Rio Verde 
é de 16. A empresa dispõe-se a investir no máximo 80 unidades monetárias 
nas construções. Formular o problema de modo a maximizar o retorno do 
investimento. 
4. Considere o problema da seção 1.2.3 sobre a operação do amplif icador de 
tensão com mínimas perdas. Reescreva o modelo em função das variáveis de 
decisão α e v, que, para este problema, são de fato as variáveis de controle.
5. (BAZARAA; JARVIS; SHERALI, 1997) A qualidade do ar em uma re-
gião depende principalmente das emissões de ef luentes – 2CO , 2SO , 4CH 
etc. – na atmosfera pelas n indústrias existentes. Cada instalação industrial 
pode utilizar m diferentes tipos de combustível. Suponha que a energia total 
necessária à indústria j é jb calorias por dia e que ijc é a emissão de ef luentes 
por tonelada do combustível i pela indústria j . Além disso, suponha que o 
combustível do tipo i custa ic dólares por tonelada e que cada tonelada desse 
tipo de combustível gera ijα calorias na indústria j. O nível de poluição do 
ar na região não pode exceder a b microgramas por metro cúbico. Finalmente, 
seja jγ um parâmetro meteorológico que relaciona emissões da indústria j à 
qualidade do ar da região. Escrever o modelo do problema para determinar a 
mistura de combustíveis a ser utilizada em cada indústria. 
6. (ARENALES; ARMENTANO; MORABITO; YANASSE, 2007) Uma 
nova máquina deve ser instalada em uma fábrica cujo piso tem formato retan-
gular e os cantos opostos têm as seguintes coordenadas (unidade em metros): 
(– 40 – 40)T e (40 20) T. Existem quatro máquinas já instaladas nas posições: 
(0 0) T, (– 40 – 40)T, (– 30 – 10)T e (– 35 0)T. Formule um modelo matemáti-
co para determinar a localização ótima da nova máquina, considerando que 
a distância entra a nova máquina e as demais seja mínima. Use a distância 
– 30 –
“reticulada” (como se o deslocamento fosse pelas ruas de uma cidade), isto é, 
se x
1
 e x
2
 são as coordenadas da nova máquina, então a distância entre a nova 
máquina e outra instalada na posição (y
1
 y
2
)T é dada por: |x
1
 – y
1
| + |x
2
 – y
2
|.
7. Consulte a literatura sobre Pesquisa Operacional e forneça um exemplo de 
problema estocástico.
– 31 –
II
Matrizes e Sistemas Lineares
P raticamente em todos os campos de estudo da Pesquisa Operacio-nal utilizam-se matrizes, seja na representação de sistemas algébri-
cos lineares, em expressões contidas em passos de algoritmos de solução 
de problemas, e em representações algébricas de processos de Markov, 
entre tantas outras. A forma adequada de representar e manipular gran-
de quantidade de dados é a utilização de matrizes. Essencialmente, os 
algoritmos que realizam operações numéricas em computador, espe-
cialmente quando manipulam muitos dados, são implementados para 
operar com matrizes. As matrizes também são úteis quando se deseja 
simbolizar de forma concisa uma sequência sistemática de operações 
matemáticas.
Este capítulo aborda noções elementares de álgebra de matrizes que, 
de alguma maneira, estão associados aos tópicos de Pesquisa Operacional 
que serão abordados neste livro. A título de complementação, sugerimos a 
leitura de Boldrini et al. (1986), Campos (2001) e Ruggiero & Lopes (1996).
2.1 Matrizes
Matriz é uma tabela de elementos dispostos em linhas e colunas. Aqui, 
trataremos de matrizes cujos elementos são números. Particularmente, nú-
meros reais. Denotamos uma matriz A que possui m linhas ( 1, 2, ,i m= � ) 
e n colunas ( 1, 2, ,j n= � ) assim:
– 32 –
11 12 13 1 1
21 22 23 2 2
1 2 3
1 2 3
[ ] .
j n
j n
ij
i i i ij in
m m m mj mn
a a a a a
a a a a a
A a
a a a a a
a a a a a
 
 
 
 
= =  
 
 
 
  
� �
� �
� � � � � � �
� �
� � � � � � �
� �
(2.1)
O elemento ija , 1, 2, ,i m= � e 1, 2, ,j n= � , encontra-se situado na 
linha de número i e na coluna de número j.
Duas matrizes A, m n× , e B, p q× , são iguais, A B= , quando o núme-
ro de linhas de A é igual ao número de linhas de B, o número de colunas de 
A é igual ao número de colunas de B e todos os seus elementos correspon-
dentes são iguais.
Serão apresentados agora, alguns tipos de matrizes. Seja dada a matriz A, 
m n× . Diz-se que A é uma matriz quadrada quando m n= . A é uma matriz 
nula quando 0ija = para todo 1, 2, ,i m= � e para todo 1, 2, ,j n= � . Se 
1n = , ou seja, apenas uma coluna existe, chamamos A de matriz coluna. Por 
igual raciocínio, se 1m = , denominamos A matriz linha. 
Um tipo especial de matriz quadrada é a matriz identidade, que possui 
elementos unitários na diagonal e zeros em todas as outras posições, mostrada 
em (2.2) para a ordem n n×
1 0 0 0 0
0 1 0 0 0
0 0 0 1 0
0 0 0 0 1
I
 
 
 
 
=  
 
 
 
  
� �
� �
� � � � � � �
� �
� � � � � � �
� �
. (2.2)
Doravante, representaremos a matriz identidade pelo símbolo I. To-
davia, note que em outras bibliograf ias também se utiliza a notação nI para 
uma matriz identidade de ordem n n× .
Uma matriz quadrada A é dita matriz diagonal quando possui elemen-
tos 0ija = para todo i j≠ . Se A for uma matriz quadrada com 0ija = para 
– 33 –
todo i j> , A é chamada de matriz triangular superior. Se A for uma matriz 
quadrada com 0ija = para todo i j< , A recebe o nome de matriz triangular 
inferior. A seguir, estão mostrados exemplos de matrizes triangulares 4 4× , 
sendo A uma matriz triangular superior e B uma matriz triangular inferior.
1
2
1 1 4 1
0 0 1 3
0 0 1
0 0 0 2
A
− − 
 
 =
 
 
  
e
 
1 0 0 0
0 3 0 0
1 2 1 0
3 1 4 3
B
 
 
 =
 −
 
 
. (2.3)
As matrizes coluna e linha são designadas como vetores. Alguns autores 
as chamam também de vetor coluna ou vetor linha. Neste texto, para ho-
mogeneizar a notação e facilitar a compreensão das expressões que utilizam 
matrizes, a designação vetores será atribuída apenas a matrizes do tipo coluna. 
A expressão mostrada a seguir ilustra essa def inição
1
2
i
m
v
v
v
v
v
 
 
 
 
=  
 
 
 
  
�
�
. (2.4)
Em (2.4) tem-se uma matriz coluna, que é denotada pelo vetor v, com 
suas componentes 1 2, , , , ,i mv v v v� � . 
Quanto à quantidade de elementos não nulos que uma matriz apresen-
ta, é usual designar por matriz densa aquela em que a maior parte dos seus 
elementos é diferente de zero. As matrizes que apresentam grande quanti-
dade de elementos nulos são conhecidas como matrizes esparsas. Matrizes 
que aparecem em modelos de problemas de grande porte do mundo real 
normalmente são esparsas. Por exemplo, em certos estudos da área de En-
genharia Elétrica, matrizes de redes elétricas reais apresentam 99,5% de ele-
mentos nulos.
Uma peculiaridade interessante de matrizes é que essas estruturas de 
dados admitem operações de adição, subtração e multiplicação, praticamente 
– 34 –
como se faz com números; todavia, observam-se certas restrições para a reali-
zação dessasoperações.
2.1.1 Operações com matrizes
Dadas duas matrizes A e B, sob certas condições, as operações de adi-
ção, subtração e multiplicação são def inidas.
Para facilitar a compreensão e tornar a exposição mais didática, serão 
tratadas primeiramente as operações de adição e subtração, que exigem que 
as matrizes sejam de mesma ordem. 
Def inição 2.1 (Adição): Sejam ija o elemento genérico da matriz A e ijb o 
elemento genérico da matriz B, ambos os elementos situados na iésima linha 
e na jotaésima coluna de suas respectivas matrizes. Desde que as matrizes A 
e B tenham a mesma ordem, m n× , a matriz obtida da adição, A B+ , é uma 
matriz também de ordem m n× , tal que seus elementos são obtidos da soma 
do elemento ija de A e o elemento ijb de B. Portanto, a adição resulta numa 
matriz designada por C, de modo que: 
( , ) [ ] [ ] [ ] [ ]A B C A B c a b a bij ij ij ij ij� = + ⇒ = + = + .
Para exemplif icar a operação de adição, consideremos as matrizes dadas a seguir:
3 1
1
0
2
5 1
A
− 
 
 =
 
 −  
e
 
8 1
1
1
4
20 5
B
 
 
 = −
 
  
.
A adição A B+ resulta na matriz C, conforme indicamos a seguir:
3 1 8 1 3 8 1 1 11 0
1 1 1 1 3
0 1 0 1 1
2 4 2 4 4
5 1 20 5 5 20 1 5 15 6
A B C+ =
− + − +       
       
       + − = − + = −
       
       − − + +       
.
Observe que, a partir dos cálculos anteriores, a adição foi efetuada elemento 
a elemento, somando-se apenas elementos que ocupam a mesma posição. 
– 35 –
Def inição 2.2 (Subtração): Sejam ija e ijb , respectivamente, os elementos ge-
néricos das matrizes A e B, tal como estabelece a def inição 2.1. Desde que as 
matrizes A e B tenham a mesma ordem, m n× , a matriz obtida da subtra-
ção, A – B, é uma matriz também de ordem m n× , tal que seus elementos são 
obtidos ao subtrair-se o elemento ijb do elemento ija . Portanto, a subtração 
A – B resulta em uma matriz designada por C, de modo que: 
( , ) [ ] [ ] [ ] [ ]A B C A B c a b a bij ij ij ij ij� = − ⇒ = − = − .
Para exemplif icar a operação de subtração, consideremos as matrizes 
dadas no exemplo referente à def inição 2.1. Então, a subtração A B− resulta 
na matriz C indicada a seguir:
3 1 8 1 3 8 1 1 5 2
1 1 1 1 1
0 1 0 ( 1) 1
2 4 2 4 4
5 1 20 5 5 20 1 5 25 4
A B C− =
− − − − − −       
       
       − − = − − − =
       
       − − − − − −       
.
A operação de multiplicação de matrizes já não é tão trivial quanto as 
operações de adição e subtração.
Primeiramente, a condição de existência da multiplicação da matriz 
A pela B, cujas ordens respectivas são m n× e p q× , é que o número de 
colunas da matriz A precisa ser igual ao número de linhas da matriz B, isto 
é, n p= . A matriz produto, neste caso, tem ordem m q× .
A figura 2.1 ilustra duas situações: no primeiro exemplo, a multiplicação 
é possível e, no segundo, a multiplicação não é def inida, ou seja, é impossível. 
Nessa f igura, o símbolo * indica um elemento qualquer da matriz.
 [ ]
* * *
* * * * *
* * *
   
   =   
      
 3 1× 1 2× 3 2→ × 3 3× 2 2× 
possível impossível
Figura 2.1: Exemplos de situações de multiplicação de matrizes
* * *
* *
* * *
* *
* * *
 
  
      
– 36 –
Def inição 2.3 (Multiplicação de duas matrizes): Dadas duas matrizes A, m n× , e 
B, n q× , observada a condição de existência, a multiplicação de A por B resulta 
em uma matriz designada por C, de modo que: 
( , ) [ ]ilA B AB C c= =� ,
em que
1
n
il ik kl
k
c a b
=
= ∑ ,
 
1, 2, ,i m= �
 
e
 
1, 2, ,l q= � .
Em geral, AB BA≠ . De fato, para
0 0
1 1
A
 
=  −  
e
 
1
1
B
 
=  
 
,
0 0 1 0 1 0 1 0
1 1 1 1 1 1 1 0
AB
× + ×       
= = =       − − × + ×       
,
enquanto que BA não está def inida para a multiplicação de matrizes. Mas,
para 
1 0
0 1
B
 
=  
 
, obtemos AB BA= .
A transposição de matrizes é def inida conforme (2.5),
A A C cT ij� = = [ ], (2.5)
em que
ij jic a= ,
 
sendo
 
TA
 
a notação para a transposta da matriz
 
A.
Dizemos que A é uma matriz simétrica quando A é uma matriz qua-
drada com ij jia a= para todos os is e js. Uma matriz A é antissimétrica 
quando é uma matriz quadrada com elementos ij jia a= − . As matrizes simé-
– 37 –
trica e antissimétrica possuem as propriedades expressas em (2.6) e em (2.7), 
respectivamente,
TA A= (2.6)
e
.TA A= − . (2.7)
Consideremos uma matriz A, m n× , e uma matriz B, n q× . Então,
( ) .T T TAB B A=
Com efeito,
( )TAB =
 
11 12 111 12 1
21 22 221 22 2
1 21 2
T
qn
qn
n n nqm m mn
b b ba a a
b b ba a a
b b ba a a
   
   
    =   
   
     
��
��
� � � �� � � �
��
=
 
1 1 1 2 1
1 1 1
2 1 2 2 2
1 1 1
1 2
1 1 1
Tn n n
k k k k k kq
k k k
n n n
k k k k k kq
k k k
n n n
mk k mk k mk kq
k k k
a b a b a b
a b a b a b
a b a b a b
= = =
= = =
= = =
 
 
 
 
 
  =
 
 
 
 
 
 
∑ ∑ ∑
∑ ∑ ∑
∑ ∑ ∑
�
�
� � � �
�
1 1 2 1 1
1 1 1
1 2 2 2 2
1 1 1
1 2
1 1 1
n n n
k k k k mk k
k k k
n n n
k k k k mk k
k k k
n n n
k kq k kq mk kq
k k k
a b a b a b
a b a b a b
a b a b a b
= = =
= = =
= = =
 
 
 
 
 
 = =
 
 
 
 
 
 
∑ ∑ ∑
∑ ∑ ∑
∑ ∑ ∑
�
�
� � � �
�
– 38 –
=
 
1 1 1 2 1
1 1 1
2 1 2 2 2
1 1 1
1 2
1 1 1
n n n
k k k k k mk
k k k
n n n
k k k k k mk
k k k
n n n
kq k kq k kq mk
k k k
b a b a b a
b a b a b a
b a b a b a
= = =
= = =
= = =
 
 
 
 
 
  =
 
 
 
 
 
 
∑ ∑ ∑
∑ ∑ ∑
∑ ∑ ∑
�
�
� � � �
�
= BT AT.
A multiplicação de um número real por matrizes é def inida por:
( , ) [ ] [ ].ij ijA A a aα α α α= =�
A seguir estudaremos o determinante.
2.1.2 Determinante
Def inição 2.4 (Determinante): Seja nC o conjunto de todas as matrizes qua-
dradas de ordem n. Isto é, matrizes n n× , cujos elementos são números reais. 
Def inimos o determinante como a função
det :
det( ),
nC
A A
→ ℜ
�
em que, det( )A pode ser calculado de forma recursiva, da seguinte maneira:
a) 1n = ,
11 11[ ] det( ) .A a A a= ⇒ = 
b) 2n = ,
– 39 –
11 12
11 22 12 21
21 22
det( ) .
a a
A A a a a a
a a
 
= ⇒ = × − × 
  
c) 3n ≥ ,
1
[ ] det( ) ( 1) ,
n
i j
ij ij ij
j
A a A a M+
=
= ⇒ = −∑ para um dado i com 1, 2, , ,i n= �
em que ijM é o determinante da matriz (submatriz) que se obtém de A, reti-
rando a iésima linha e a jotaésima coluna. 
Exemplo 2.1: Considere
1 2 3
2 1 1
2 1 2
A
− 
 = − 
 − − 
.
Calcule det( )A .
Optaremos por f ixar a linha 1 e calcular o determinante de A aplicando 
a def inição 2.4, do seguinte modo:
1 2 3
det( ) det 2 1 1
2 1 2
A
 − 
  = − =  
  − −  
= × − × + − × − × + × −( ) ×+ + +1 1 2 1 3 11 1 11 1 2 12
1 3
13( ) ( ) ( )M M M
1 (1 2 ( 1) ( 1)) 2 (2 2 ( 2) ( 1)) 3 (2 ( 1) ( 2) 1) 5= × × − − × − + × × − − × − + × × − − − × = .
det( ) 5A∴ = .
A partir da def inição de determinante, não é difícil contar as multipli-
cações necessárias para se calcular o determinante de uma matriz de ordem n: 
– 40 –
para uma matriz de ordem 2, são necessárias 2 multiplicações. Para uma ma-
triz de ordem 3, é preciso calcular 3 determinantes de ordem 2 e multiplicar 
esses determinantes pelos elementos da linha escolhida, perfazendo, neste caso, 9 
multiplicações, e assim por diante. A fórmula recursiva p 
n
=n(p
n–1
+1), iniciando 
com p
1
=0, reproduz a quantidade requerida de multiplicações no cálculo do 
determinante de uma matriz de ordem n, quando aplicamos a def inição 2.4. 
Por exemplo: para matrizes de ordem 1, 2, 3, 4 e 5, obtemos p
1
=0, p
2
=2, p
3
=9, 
p
4
=40, p
5
=205, respectivamente. O número de multiplicações é muito elevado 
para matrizes de porte médio e, por esta razão, qualquer algoritmo que envol-
va o cálculo de determinantes não é praticável em implementações computa-
cionais. Por exemplo, o cálculo do determinantede uma matriz 10×10 exigirá 
6.235.300 multiplicações. Para efeito de comparação, a tabela 2.1 apresenta 
valores de p
n
 e de n!. 
Tabela 2.1: Comparação entre valores do número de multiplicações requeridas no 
cálculo do determinante e o fatorial da ordem da matriz
Ordem da matriz, n np !n
1 0 1
2 2 2
3 9 6
4 40 24
5 205 120
6 1.236 720
7 8.659 5.040
8 69.280 40.320
9 623.529 362.880
10 6.235.300 3.628.800
Podemos utilizar conhecimentos de Matemática Discreta e mostrar que 
1
1
!
( )!
n
n
k
n
p
n k
−
=
=
−∑ , comprovando, assim, que !np n≥ .
A seguir, enunciaremos algumas propriedades de determinante.
Proposição 2.1: Sejam A e B matrizes quadradas de ordem n. 
a) Se todos os elementos da iésima linha (ou coluna) de A forem nulos, então 
det( ) 0A = .
– 41 –
b) det( ) det( )TA A= .
c) det( ) det( ) det( )AB A B= × .
A última propriedade nos proporcionará, adiante, um método ef iciente 
para o cálculo do determinante de uma matriz, que se baseia na sua decom-
posição em duas matrizes triangulares. Uma def inição importante, que nos 
auxiliará na compreensão de outras def inições que têm conexão com determi-
nante, é a de submatriz principal líder.
Def inição 2.5 (Principais líderes): Seja A uma matriz quadrada de ordem n 
com elementos reais. Para 1, 2, ,k n= � , a kaésima submatriz principal líder 
de A é a matriz kA , obtida por meio da interseção das primeiras k linhas e 
colunas de A.
Para evitar ambiguidade na obtenção das submatrizes principais líderes, 
é necessário supor que a permutação de linhas e colunas da matriz A não seja 
admitida. 
A f igura 2.2 ilustra como são obtidas as submatrizes principais líderes de 
uma matriz de ordem 4 4× .
 
2A 3A 4A
Figura 2.2: Submatrizes principais líderes de uma matriz A de ordem 4 em hachura
Consequentemente, a enésima principal líder, nA , é a própria matriz A.
Os determinantes das submatrizes principais líderes são conhecidos 
como menores principais líderes.
Exemplo 2.2: Considere a matriz
4 1 2
1 4 1
3 3 2
A
− 
 =  
  
.
A
1
– 42 –
Determine as submatrizes principais líderes de A e os respectivos deter-
minantes.
Suprimimos a 2a linha e a 2a coluna, e também a 3a linha e a 3a coluna da 
matriz A, e obtemos a principal líder, A
1
:
A
1 
= [4],
o seu determinante é
1det( ) 4A = .
 
Suprimimos a 3a linha e a 3a coluna da matriz A, e obtemos a principal líder, 2A :
2
4 1
1 4
A
− 
=  
 
,
o seu determinante é 
2 2det( ) 4 4 ( 1) 1 det( ) 17A A= × − − × ⇒ = .
A principal líder 3A é a própria matriz A:
3
4 1 2
1 4 1
3 3 2
A A
− 
 = =  
  
.
O determinante de 3A pode ser obtido do seguinte modo:
3det( ) 4 4 2 3 1 2 1 ( 1) 3 3 4 2 ( 1) 1 2 4 3 1 1A = × × + × × + × − × − × × − − × × − × × = .
A def inição 2.5 conduz a outras def inições que são muito úteis em Pro-
gramação Matemática Não Linear, que pode ser considerado um ramo da 
Pesquisa Operacional. Uma dessas def inições é dada a seguir.
– 43 –
Def inição 2.6 (Matriz def inida positiva): Seja A uma matriz de números 
reais, quadrada, n n× , e simétrica. A matriz A é def inida positiva quando 
para todo nx ∈ℜ , com x não nulo, 0Tx Ax > .
Em particular, uma matriz simétrica real 2 2× , 
11 12
21 22
a a
A
a a
 
=  
 
,
é def inida positiva se,
11 12 1 2 2
1 2 11 1 22 2 1 2
21 22 2
[ ] 2 0T
a a x
x Ax x x a x a x x x
a a x
β   = = + + >   
   
, sendo a
12 
= a
21 
=b.
Exemplo 2.3: Mostre que a matriz 
2 1
1 1
A
 
=  
 
 é def inida positiva.
Suponhamos um vetor não nulo, x = [x
1
 x
2
]T, isto é, se uma das compo-
nentes for igual a zero, a outra terá de ser diferente de zero. Então,
1 2 2
1 2 1 2 1 2
2
2 1
[ ] 2 2
1 1
T xx Ax x x x x x x
x
   
= = + +   
   
.
Completando os quadrados, obtemos:
2 2 2 2
1 2 1 2 1 1 22 2 ( ) 0
Tx Ax x x x x x x x= + + = + + > .
A última expressão mostra claramente que, para quaisquer 1x e 2x reais 
diferentes de zero, o produto matricial Tx Ax será positivo. Isto implica que a 
matriz
 
2 1
1 1
A
 
=  
  
é def inida positiva.
Um fato que relaciona uma matriz def inida positiva e suas submatrizes 
principais líderes é expresso na proposição 2.2.
Proposição 2.2: Uma matriz def inida positiva possui todos os determinantes 
dos principais líderes positivos.
– 44 –
No estudo de funções quadráticas de ordem n, a def inição de matriz 
def inida positiva encontra muitas aplicações interessantes. A seguir são dados 
dois exemplos para ilustrar essas aplicações.
Exemplo 2.4: Represente graf icamente a função quadrática def inida como a 
seguir,
2:f ℜ → ℜ ,
 
1 2 2
1 2 1 2 1 2 1 2
2
2 1
( , ) [ ] 2 2 .
1 1
x
f x x x x x x x x
x
   
= = + +   
   
A figura 2.3 ilustra o gráfico da função deste exemplo.
Figura 2.3: Gráf ico da função do exemplo 2.4
O próximo exemplo refere-se a uma função quadrática cuja matriz não 
é def inida positiva. 
Exemplo 2.5: Represente graf icamente a função quadrática def inida como a 
seguir:
– 45 –
f : ℜ → ℜ2 2 , [ ] 1 2 21 2 1 2 1 2 1 2
2
1 1
( , ) 4 2 .
1 4
x
f x x x x x x x x
x
−   
= = − − +   −   
Escrevemos a função completando os quadrados, o que comprova que 
ela será sempre negativa, independentemente dos valores que 1x e 2x assu-
mirem, para x 2 não nulo,
2 2 2 231
1 2 1 2 2 1 12 44 2 (2 ) 0x x x x x x x− − + = − − − < .
Figura 2.4: Gráf ico da função do exemplo 2.5
No exemplo em que a matriz é def inida positiva, a concavidade da fun-
ção está voltada para cima, conforme podemos ver na figura 2.3, enquanto 
que, no exemplo correspondente ao caso em que a matriz não é def inida po-
sitiva – na verdade, a matriz é def inida negativa –, a concavidade da função 
está voltada para baixo (figura 2.4).
Do fato de a matriz ser def inida positiva há importantes implicações 
para estudos em diversas aplicações da Pesquisa Operacional. Tais implica-
ções, porém, não serão tratadas neste livro.
– 46 –
A seguir, trataremos da obtenção da inversa de uma matriz.
2.1.3 A inversa de uma matriz
Def inição 2.7 (Matriz inversa): Seja A uma matriz quadrada de ordem n. 
A é invertível quando existe uma única matriz 1A− , denominada matriz inver-
sa de A, tal que
1 1 .AA A A I− −= =
Exemplo 2.6: Considere
1 0
.
0 2
A
 
=  
 
Calcule 1A− , se existir.
11 12
21 22
1 0 1 0
0 2 0 1
b b
AB I
b b
     
= ⇒ = ⇒     
     
11 12
21 22
1 0
2 2 0 1
b b
b b
   
⇒ =   
   
.
Por igualdade de matrizes, obtemos
11 12 211, 0, 0b b b= = = e 
1
222b = .
Logo,
1
2
1 0 1 0 1 0
0 0 2 0 1
BA I
     
= = =     
     
.
Então,
1
1
2
1 0
0
A B−
 
= =  
 
é a única matriz inversa de A.
– 47 –
A matriz [0]A = não é invertível, uma vez que para 1 10 1AA A I− −= ≠ = , 
portanto, não existe A–1.
Consideremos as matrizes A , n n× , e B , n n× , e A–1 e 1B− as matrizes 
inversas de A e B, respectivamente. Então,
1 1 1( )AB B A− − −= .
Com efeito, usando a associatividade de matrizes, o fato de B ser inver-
tível e de AI A= ,
1 1 1 1 1( )( ) ( ) ( )AB B A A BB A A I A I− − − − −= = =
e, de maneira análoga, 
1 1 1 1 1 1( )( ) ( ) ( )B A AB B A A B B I B B B I− − − − − −= = = = .
Além disso,
1 1( )A A− − = .
Com efeito,
1 1A A I A A− −= = .
Isto é, a matriz inversa da matriz 1A− é a matriz A.
2.1.4 Inversa de uma matriz e determinante
Na def inição de determinante surgiu o número mostrado em (2.8),
( 1)i jij ijM
+∆ = − , (2.8)
em que ij∆ é denominado cofator do elemento ija .
Seja A uma matriz quadrada de ordem n. Chamamos de matriz dos 
cofatores, denotada por A, a matriz obtida de A, em que cada elemento é o 
cofator de seu respectivo em A, isto é:
– 48 –
11 12 1
21 22 2
1 2
n
n
n n nn
A
∆ ∆ ∆ 
 ∆ ∆ ∆ =
 
 ∆ ∆ ∆ 
�
�
� � � �
�
.
Def inição 2.8 (Matriz adjunta): Seja A uma matriz quadrada de ordem n. 
Def inimos a matriz adjunta de A, denotada por adj A, como
Tadj A A= .
Exemplo 2.7:Considere a matriz
1 1
2 1
A
 
=  
 
.
Calcule a matriz adjunta de A.
Temos que
1 1
11 11( 1) 1 det(1) 1,M
+∆ = − = × =
1 2
12 12( 1) ( 1) det(2) 2,M
+∆ = − = − × = −
2 1
21 21( 1) ( 1) det(1) 1,M
+∆ = − = − × = −
e
2 2
22 22( 1) 1 det(1) 1.M
+∆ = − = × =
Então, a matriz dos cofatores é
1 2
1 1
A
− 
=  − 
.
Portanto,
1 1
2 1
Tadj A A
− 
= =  − 
.
– 49 –
O próximo resultado relaciona determinante e matriz adjunta.
Teorema 2.1: Seja A uma matriz quadrada de ordem n. Então,
det( )A adj A A I= .
Agora, relacionamos determinante e matriz inversa, através do teorema 
clássico a seguir.
Teorema 2.2: Uma matriz quadrada A é invertível se, e somente se, det( ) 0A ≠ .
Os teoremas 2.1 e 2.2 propiciam um método de obtenção da inversa de 
uma matriz, a saber:
1
det( )
adj A
A
A
− = . (2.9)
A expressão (2.9) para cálculo da inversa de uma matriz pode ser 
utilizada para solucionar um sistema linear algébrico de poucas equações e 
incógnitas. Isto será tratado na seção a seguir. Nas seções posteriores, serão 
apresentados métodos computacionalmente mais ef icientes para resolver sis-
temas lineares de equações algébricas.
2.2 Sistemas lineares algébricos de pequeno porte
Para sistemas de pequeno porte, o cálculo do determinante é reali-
zável com um número razoável de operações aritméticas. Portanto, tais 
sistemas lineares algébricos podem ser resolvidos utilizando-se a regra de 
Cramer.
Seja A uma matriz quadrada de ordem n invertível. Considere-se nb R∈ . 
O sistema linear
Ax b= (2.10)
pode ser expresso como
1x A b−= , (2.11)
– 50 –
uma vez que A é invertível e, consequentemente, 
det( ) det( )
Tadj A b A b
x
A A
= = , (2.12)
usando-se (2.9) e a def inição de matriz adjunta. A expressão (2.12) para a re-
solução do sistema de equações (2.10) é reconhecida como a regra de Cramer.
Desenvolvendo (2.12),
11 21 1 1
12 22 2 2
1 2
1
det( )
n
n
n n nn n
b
b
x
A
b
∆ ∆ ∆   
   ∆ ∆ ∆   =
   
   ∆ ∆ ∆   
�
�
� � � � �
�
,
para 1, 2, ,j n= � ,
1 1
1 1
( ) ( ( 1) )
det( ) det( )
n n
i j
j ij i i ij
i i
x b b M
A A
+
= =
= ∆ = −∑ ∑ .
De acordo com a def inição de determinante, concluímos que, para se 
obter a incógnita x
j
, basta calcular o determinante da matriz A após a troca da 
jotaésima coluna dessa matriz pelo vetor termo independente, b, e dividir o 
resultado encontrado pelo det( )A . De modo idêntico, devemos proceder para 
todas as demais incógnitas.
As igualdades a seguir ilustram o mecanismo de solução de um sistema 
de três incógnitas pela aplicação da regra de Cramer, a saber:
1 12 13 11 1 13 11 12 1
2 22 23 21 2 23 21 22 2
3 32 33 31 3 33 31 32 3
1 2 3
det det det
, , .
det( ) det( ) det( )
b a a a b a a a b
b a a a b a a a b
b a a a b a a a b
x x x
A A A
          
          
          
                    = = =
Tendo em vista a complexidade dos cálculos de determinantes e, por 
conseguinte, dos métodos de obtenção da inversa de uma matriz e de solução 
– 51 –
de sistemas por Cramer, estudados nas seções anteriores, nos sentimos compe-
lidos a estudar formas mais ef icientes de executar essas operações.
Os métodos computacionalmente mais ef icientes que os estudados até 
agora baseiam-se em operações elementares sobre matrizes, que serão abor-
dados a seguir.
2.3 Operações elementares sobre matrizes
Podemos realizar as seguintes operações, chamadas elementares, sobre 
as linhas ou as colunas de uma matriz.
1. ( )i jl l↔ Permutação das iésima e jotaésima linhas. Por exemplo:
2 3
1 0 1 0
4 1 ~ 3 4 .
3 4 4 1
l l
   
   − ↔ −   
   − −   
2. ( )i il lα← Multiplicação da iésima linha por um número não nulo α . Por 
exemplo:
2 2
1 0 1 0
4 1 3 ~ 12 3 .
3 4 3 4
l l
   
   − ← − × −   
   − −   
3. ( )i i jl l lα← + Substituir a iésima linha pela soma da iésima linha com a 
jotaésima linha multiplicada por um número não nulo α. Por exemplo:
2 2 1
1 0 1 0
4 1 3 ~ 7 1 .
3 4 3 4
l l l
   
   − ← + × −   
   − −   
Resumindo, as operações elementares realizadas sobre uma matriz são: (a) 
a permutação de duas linhas; (b) a multiplicação de uma linha por uma constan-
te diferente de zero; e (c) a adição de uma linha a um múltiplo de outra linha.
– 52 –
Ao utilizarmos as operações elementares, podemos fazê-lo com um pro-
pósito previamente def inido e, neste caso, haverá regras a serem cumpridas. 
Por exemplo, o objetivo pode ser verif icar se dois, dentre três vetores dados, 
são linearmente independentes. Neste caso, as operações serão usadas para 
fazer emergir vetores canônicos, conforme mostra o exemplo 2.8.
Exemplo 2.8: Verif ique, através de operações elementares, se existem dois ve-
tores linearmente independentes dentre os três vetores dados:
2
4
6
u
 
 =  
  
, 
1
2
3
v
 
 =  
  
 e 
1
5
4
w
 
 =  
  
 .
Disporemos os três vetores na forma de uma matriz e efetuaremos ope-
rações elementares sobre ela, assim:
2 1 1
4 2 5
6 3 4
 
 
 
  
.
Inicialmente, o nosso propósito será obter, com operações elementares, 
os vetores [1 0 0]T e [0 1 0]T nos lugares das duas primeiras colunas da 
matriz. Se tivermos sucesso, os vetores u e v são linearmente independentes; 
caso contrário, são dependentes. 
1 1 1
2 21 122 1 1 1
4 2 5 ~ 4 2 5
6 3 4 6 3 4
l l←   
   
   
      
,
1 1 1 1
2 2 2 2
2 2 1
3 3 1
1 1
4 2 5 4 ~ 0 0 3
6 3 4 6 0 0 1
l l l
l l l
   
   ← − ×   
   ← − ×   
.
Podemos ver que a hipótese de os vetores u e v serem linearmente in-
dependentes não se sustentou, porque não foi possível obter vetores canônicos 
nos lugares de suas colunas. O próximo passo é testar, de modo análogo, se 
dois outros vetores – u e w – são linearmente independentes, buscando obter 
– 53 –
vetores canônicos nos lugares de suas colunas. Aproveitando os cálculos já 
realizados, temos:
1 1 1 1
2 2 2 2
1
2 23
1 1
0 0 3 ~ 0 0 1
0 0 1 0 0 1
l l
   
   ←   
      
,
11 1 1
2 2 21 1 22
3 3 2
1 1 0
0 0 1 ~ 0 0 1
0 0 1 0 0 0
l l l
l l l
← −   
   
   
   ← −   
.
A observação das colunas 1 e 3, que correspondem aos vetores u e w, 
comprova que tais vetores são linearmente independentes. De fato, na relação 
entre u e w mostrada a seguir
2 1
4 5
6 4
α
   
   =   
      
,
não existe um número real α que atenda à igualdade.
A lição que f ica do exemplo 2.8 é que as operações elementares foram 
empregadas com um propósito bem def inido – obter vetores canônicos – o 
que conduziu à realização de operações sobre as linhas da matriz em torno de 
elementos pivôs: o número 2 na primeira parte do exemplo e o número 3 na 
segunda, foram os pivôs usados.
A seguir estabeleceremos a def inição de equivalência de matrizes.
Def inição 2.9 (Matriz linha equivalente): Sejam A e B matrizes m n× . B é 
linha equivalente a A quando B é obtida de A através de um número f inito de 
operações elementares sobre as linhas de A.
Exemplo 2.9: Considere
1 0
4 1
3 4
A
 
 = − 
 − 
.
– 54 –
Encontre uma matriz B linha equivalente a A.
1 2
2 2
3 3 2
1 0 4 1 4 1 4 1
4 1 ~ 1 0 ~ 1 0 ~ 1 0
3 4 3 4 2 1 4 1 4
l l
A l l B
l l l
↔ − − −       
       = − ← − − =       
       − − ← + × − −       
.
Neste caso, podemos dizer que:
1 0
4 1
3 4
 
 − 
 − 
 ~ 
4 1
1 0
1 4
− 
 − 
 − 
.
Informações importantes sobre matrizes podem ser extraídas por meio 
da realização de operações elementares sobre suas linhas. Por exemplo, quan-
do precisamos verif icar se há equações redundantes entre as equações lineares 
algébricas que compõem um sistema. Um outro problema é saber se uma 
dada matriz quadrada possui ou não inversa. Nesses casos e em muitas outras 
situações, a forma escalonada de umamatriz A, m n× , será muito útil.
2.3.1 A forma escalonada
Def inição 2.10 (Matriz na forma escalonada): Matriz escalonada é aquela em 
que o primeiro elemento não nulo de cada uma de suas linhas está à esquerda 
do primeiro elemento não nulo de cada uma de suas linhas subsequentes. Em 
decorrência disso, as linhas nulas, se houver, estão abaixo das demais.
As matrizes
1 3 7 2
0 2 5 1
0 0 0 3
 
 
 
   
e
 
8 3 0 2
0 2 5 1
 
 
 
são matrizes escalonadas, enquanto a matriz
8 3 0 2
0 0 0 0
1 2 5 1
 
 
 
   
– 55 –
não é escalonada, porque o primeiro elemento não nulo da primeira linha não 
está à esquerda do primeiro elemento não nulo da terceira linha e, também, 
porque a segunda linha é nula enquanto a terceira não o é.
Exemplo 2.10: Obtenha a forma escalonada da matriz
1 2 3 0 1
4 1 1 4 2
3 1 4 4 3
A
− 
 = − 
  
.
Iniciaremos anulando os elementos da primeira coluna que estão abaixo 
do elemento da posição (1,1), usando 2 2 14l l l← + ×
2 2 1
1 2 3 0 1 1 2 3 0 1
4 1 1 4 2 4 ~ 0 7 13 4 6
3 1 4 4 3 3 1 4 4 3
l l l
− −   
   − ← + ×   
      
,
e 3 3 13l l l← + × , 
3 3 1
1 2 3 0 1
0 7 13 4 6
3 1 4 4 3 3l l l
− 
 
 
  ← + × 
 ~ 
1 2 3 0 1
0 7 13 4 6
0 7 13 4 6
− 
 
 
  
.
Em seguida, anulamos os elementos da segunda coluna que estão abaixo 
do elemento da posição (2,2), usando 3 3 21l l l← − ×
1 2 3 0 1
0 7 13 4 6
0 0 0 0 0
− 
 
 
  
.
A matriz
1 2 3 0 1
0 7 13 4 6
0 0 0 0 0
− 
 
 
  
é, portanto, a forma escalonada da matriz A.
– 56 –
Muitas vezes, é preciso utilizar a operação de permutação de linhas da 
matriz para obtermos a forma escalonada. Vejamos o exemplo a seguir.
Exemplo 2.11: Obtenha a forma escalonada da matriz
1 4 2
2 8 4
3 12 10
A
 
 = − − − 
  
.
Multiplicamos a primeira linha por 2 e adicionamos o resultado à segun-
da linha ( 2 2 12l l l← + × ), obtendo:
1 4 2
0 0 0
3 12 10
 
 
 
  
.
Permutamos as linhas 2 e 3 ( 2 3l l↔ ):
1 4 2
3 12 10
0 0 0
 
 
 
  
.
Em seguida, realizamos a operação elementar 2 2 13l l l← − × para f inal-
mente obtermos a forma escalonada
1 4 2
0 0 4
0 0 0
 
 
 
  
.
Com a forma escalonada, conforme def inida e ilustrada através de 
exemplos, estamos a um passo da def inição de forma escalonada reduzida. 
A partir da forma escalonada de uma matriz, obtém-se a forma escalonada 
reduzida do seguinte modo: tornamos os primeiros elementos não nulos de 
cada linha iguais à unidade e anulamos os elementos que estiverem acima 
desses na mesma coluna. 
Vamos ao exemplo.
– 57 –
Exemplo 2.12: Obtenha a forma escalonada reduzida da matriz
1 2 3 0 1
4 1 1 4 2
3 1 4 4 3
A
− 
 = − 
  
.
Partindo da forma escalonada obtida no exemplo 2.10, temos:
1 1
1 13 64
7 7 72 27
1 2 3 0 1 1 1 2 3 0 1
0 7 13 4 6 ~ 0 1
0 0 0 0 0 0 0 0 0 0
l l
l l
− ← − × − − −   
   ← ×   
      
.
Anulando-se os elementos acima do elemento unitário da posição (2,2), 
temos:
5 8 5
7 7 71 1 2
13 6 13 64 4
7 7 7 7 7 7
1 2 3 0 1 2 1 0
0 1 ~ 0 1
0 0 0 0 0 0 0 0 0 0
l l l− − − ← + ×   
   
   
      
.
A matriz
5 8 5
7 7 7
13 64
7 7 7
1 0
0 1
0 0 0 0 0
 
 
 
  
é, portanto, a forma escalonada reduzida da matriz A.
Na próxima seção, será fornecida uma aplicação da forma escalonada 
que acabamos de estudar.
2.3.2 Posto de uma matriz
Em diversas situações nos deparamos com a necessidade de analisar se 
uma matriz quadrada possui inversa, ou se um sistema linear algébrico de 
equações possui solução única ou uma inf inidade de soluções. Essas questões 
são resolvidas com base na def inição de posto de uma matriz.
Para estabelecer as def inições nesta seção, serão supostos conhecimentos 
prévios em Álgebra Linear, em especial os conceitos de espaço vetorial, de-
– 58 –
pendência linear e subespaços de uma matriz. Além disso, considere a trans-
formação linear def inida pela matriz m nA ×∈ℜ . Dois subespaços importantes 
do espaço vetorial nℜ estão associados com essa transformação: o espaço nulo 
de A, def inido por
 
( ) { ; 0}nN A x Ax= ∈ℜ =
e seu complemento ortogonal, o espaço linha de A, def inido por
( ) { ; , }T n T mR A x x A z z= ∈ℜ = ∈ℜ .
Segue-se que qualquer vetor nv ∈ℜ pode ser unicamente decomposto – 
soma direta – como p pv v v= + � , em que ( )pv N A∈ e ( )
T
pv R A∈� .
Def inição 2.11 (Posto de uma matriz): A dimensão r do espaço linha de A é 
chamada de posto de A.
Para se caracterizar precisamente o espaço linha de uma matriz A, m n× , 
é necessário encontrar um conjunto linearmente independente (LI) de vetores 
linhas dessa matriz. O número desses vetores LI é a dimensão do espaço linha 
e, portanto, o posto de A. O procedimento para se obter a dimensão do espaço 
linha consiste em determinar a forma escalonada da matriz. Regra geral: o 
posto de A é o número de linhas não nulas da matriz na forma escalonada.
Façamos o exemplo a seguir.
Exemplo 2.13: Obtenha o posto da matriz
2 3 1
4 2 2
6 1 1
A
− 
 = − 
  
.
Efetuamos sobre A as operações elementares sobre as linhas de A, como 
indicado a seguir:
2 2 1
2 3 1
4 2 2 2
6 1 1
l l l
− 
 − ← − × 
  
 
3 3 1
2 3 1
~ 0 8 4 ~
6 1 1 3l l l
− 
 − 
  ← − × 
 
– 59 –
3 3 2
2 3 1
~ 0 8 4 ~
0 8 4 1l l l
− 
 − 
 − ← − ×  
2 3 1
0 8 4
0 0 0
− 
 − 
  
.
Concluído o escalonamento, verif icamos que as linhas [2 3 1]− e 
[0 8 4]− são linearmente independentes. Portanto, o posto de A é 2. De 
fato, observando as linhas da matriz A é possível ver que a terceira linha é a 
soma das duas primeiras. 
Uma conclusão interessante é que a matriz A do exemplo 2.13 não possui 
inversa, porque seu posto (2) é inferior ao seu número de linhas (3). Deno-
tamos por ‘posto def iciente’ uma matriz cujo posto é inferior ao número de 
linhas (ou colunas).
Uma aplicação prática da forma escalonada reduzida de uma matriz 
ocorre quando desejamos determinar o espaço coluna dessa matriz. Tal apli-
cação também está associada à determinação de posto. 
Def inição 2.12 (Espaço coluna de uma matriz): Seja A uma matriz m × n. 
Consideremos a transformação linear T, def inida por 
: ( ) ( )n mT V Vℜ → ℜ ,
tal que
( )T x Ax= .
O espaço coluna da matriz A é o subespaço R(A) de ( )mV ℜ gerado pelos veto-
res colunas de A, que identif icamos com o conjunto 
Imagem { ; ( )}nT Ax x V= ∈ ℜ .
Em outras palavras, o conjunto Imagem T é o subespaço de ( )mV ℜ ge-
rado pelos vetores colunas de A. Diante disso, a forma escalonada reduzida 
de uma matriz nos informa os vetores da base do espaço coluna da mesma 
matriz. 
Façamos um exemplo.
– 60 –
Exemplo 2.14: Determine os vetores da base do espaço coluna da matriz
1 2 1 0 1
1 1 0 2 2
2 0 3 2 4
A
− 
 = − − 
 − 
.
O nosso objetivo é eliminar um a um os vetores linearmente depen-
dentes, até que os vetores restantes formem um conjunto linearmente inde-
pendente. A maneira sistemática de se fazer isto é obter a forma escalonada 
reduzida da matriz A. Depois de aplicar operações elementares sobre as linhas 
da matriz A, com vistas à obtenção da forma escalonada reduzida, chegamos 
à seguinte matriz linha equivalente:
11
5
1
5
14
5
1 2 1 0 1 1 0 0 2
1 1 0 2 2 ~ 0 1 0 0
2 0 3 2 4 0 0 1 2
− −   
   − − −   
   − −   
.
Observamos que os vetores canônicos emergiram nas três primeiras co-
lunas da matriz. Isto signif ica que os vetores 
1
1
2
 
 − 
  
, 
2
1
0
− 
 
 
  
 e 
1
0
3
 
 
 
  
são os vetores geradores do espaço coluna da matriz A. Outra observação im-
portante é que são três os vetores. Esse número é o posto da matriz A.
Nas seções posteriores serão discutidas outras aplicações para o posto de 
uma matriz.
2.3.3 Matrizes elementares
Def inição 2.13 (Matriz elementar): Matriz elementar é aquela obtida a partir 
da matriz