book-public

8/14/2019 book-public

1/215

ALGORITMOS

DE

PROGRAMAOLINEAR

Programao Linear Concreta

Paulo Feofiloff

Professor do

Departamento de Cincia da Computao do

Instituto de Matemtica e Estatstica da

Universidade de So Paulo

novembro de 1997revisto em 27.7.1999

reformatado em 11.9.2005


2/215

Prefcio

O problema bsico de programao linear1 consiste no seguinte: dada uma matrizA e vetores b e c, encontrar um vetor x tal que

x 0 , Ax = b e cx mnimo.

O livro discute este problema, suas variantes e generalizaes, e a correspon-dente teoria da dualidade.

O que. Nosso ponto de partida o algoritmo de Gauss-Jordan e o algo-ritmo Simplex. Toda a teoria da programao linear deduzida desses doisalgoritmos. Do ponto de vista do Simplex, o problema bsico tem a seguinteforma: transformar uma matriz dada (a matriz resulta da justaposio de A, be c) em outra equivalente que contenha um certo padro ou desenho.

Examinaremos tambm um representante da famlia de algoritmos polino-miais de programao linear que surgiu em meados da dcada . O al-goritmo que discutiremos uma variante do clebre algoritmo do elipside no uma alternativa prtica para o Simplex,2 mas tem profundas implicaestericas.

O livro no trata dos aspectos mais prticos da programao linear. Assim,por exemplo, o livro no se ocupa das implementaes aproximadas do Simplex,que representam nmeros racionais em notao ponto flutuante; em particu-lar, o livro no trata das heursticas que procuram reduzir os erros de arredon-damento de tais implementaes. O livro tambm no trata das dificuldadesprticas associadas com a manipulao de matrizes muito grandes, nem de al-goritmos especiais para matrizes esparsas.3 Finalmente, o livro no trata demodelagem, que a arte de reduzir certos problemas de otimizao a problemasde programao linear. Todos esses tpicos so muito importantes na prtica,mas esto alm dos objetivos do livro (e da competncia do autor).

Como. A atitude do livro mais matemtica e conceitual que tecnolgica.Em outra dimenso, a atitude mais algbrica que geomtrica. O enfoque

1 Neste contexto, o termo programao significa planejamento. No se trata de uma referncia programao de computadores.

2 Outros algoritmos da famlia, entretanto, competem com o Simplex.3 O leitor interessado nesses tpicos deve consultar os livros de Chvtal [Chv83] e Golub e

Van Loan [GL96].

i


3/215

Feofiloff ii

algortmico: toda a teoria derivada dos algoritmos, particularmente do Simplex.Os algoritmos so descritos de maneira precisa, em linguagem razoavel-

mente informal. Para tornar isso possvel, necessrio introduzir definieslimpas para os conceitos de matriz e vetor e uma notao suficientemente pode-

rosa para descrever partes desses objetos.O livro procura dizer com preciso o que cada algoritmo faz e no apenascomo faz o que faz. O comportamento dos algoritmos descrito por meio deinvariantes, e o seu desempenho de pior caso analisado.

O universo natural da programao linear o dos nmeros racionais. O livrosupe, portanto, que dispomos de um agente computacional capaz de executararitmtica racional. Uma das verses do Simplex(captulo 12 manipula em sepa-rado os numeradores e denominadores dos nmeros racionais e portanto s usaaritmtica inteira. Segue da uma verso do Teorema da Dualidade que especi-fica delimitaes superiores para o nmero de dgitos das solues do problemade programao linear.

O livro evita o uso indiscriminado de ferramentas da lgebra linear, porquetais ferramentas so, em geral, mais sofisticadas que as situaes concretas que preciso enfrentar. O livro evita tambm as hipteses simplificadoras (porexemplo, a hiptese de que nossas matrizes tm posto pleno e a hiptese deque dispomos de uma soluo vivel ao iniciar a execuo do Simplex) tocomuns em outros textos sobre o assunto. Tais hipteses pouco contribuiriampara simplificar a discusso.

Para quem. Este livro dirigido a qualquer pessoa que queira compreen-der as interconexes lgicas entre as vrias peas desse quebra-cabeas que aprogramao linear. Em particular, o texto se destina a estudantes de graduao

e ps-graduao em matemtica aplicada, computao e engenharia. O livrono tem pr-requisitos formais, mas exige uma certa maturidade matemtica.Verses preliminares do livro foram usadas em vrios oferecimentos da dis-

ciplina Programao Linear nos cursos de graduao e ps-graduao em Cin-cia da Computao no Instituto de Matemtica e Estatstica da Universidade deSo Paulo. O subttulo do livro Programao Linear Concreta uma alusoao Concrete Mathematics [GKP94] de Graham, Knuth e Patashnik Para explicar ottulo, o prefcio daquele livro diz:

The course title Concrete Mathematics was originally intended as an antidoteto Abstract Mathematics [. . . ]. Abstract mathematics is a wonderful subject,[. . . ] But [. . . ] The goal of generalization had become so fashionable that a

generation of mathematicians has become unable to relish beauty in the parti-cular, to enjoy the challenge of solving quantitative problems, or to appreciatethe value of technique.

Dados tcnicos. A elaborao do livro contou com o apoio dos projetos As-pectos Estruturais e Algortmicos de Objetos Combinatrios (FAPESP 96/04505-2) e Complexity of Discrete Structures (ProNEx 107/97). O livro foi escrito em
http://www.ime.usp.br/~yoshi/pronex/http://www.ime.usp.br/~cris/gcomb/tem-fapesp/index.htmlhttp://www.ime.usp.br/~cris/gcomb/tem-fapesp/index.htmlhttp://www.usp.br/http://www.usp.br/http://www.ime.usp.br/http://www.ime.usp.br/dcc/posgrad/http://www.ime.usp.br/dcc/posgrad/http://www.ime.usp.br/dcc/grad/


4/215

Feofiloff iii

LATEX nas instalaes do Instituto de Matemtica e Estatstica da Universidadede So Paulo. Informaes atualizadas sobre o texto podero ser encontradas noendereo http://www.ime.usp.br/~pf/prog-lin/ da teia WWW.

So Paulo, 19992005

P. F.
http://www.ime.usp.br/~pf/prog-lin/


5/215

Sumrio

Prefcio i

1 Vetores e Matrizes 11.1 Vetores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Produtos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.4 Matrizes inversveis . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.5 Transposio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.6 Matrizes de bijeo . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.7 Matrizes diagonais . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.8 Matrizes elementares . . . . . . . . . . . . . . . . . . . . . . . . . . 81.9 Combinaes lineares . . . . . . . . . . . . . . . . . . . . . . . . . . 10

I Algoritmos Bsicos 12

2 Algoritmo de Gauss-Jordan 132.1 Matrizes escalonadas . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2 Esboo do algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . 142.3 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.4 Anlise do algoritmo: invariantes . . . . . . . . . . . . . . . . . . . 182.5 Mais invariantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.6 Nmero de operaes aritmticas . . . . . . . . . . . . . . . . . . . 212.7 Concluso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.8 Aplicao: Sistemas de equaes . . . . . . . . . . . . . . . . . . . 23

3 Introduo ao Simplex 263.1 Matrizes simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.2 Esboo do Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.3 Anlise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.4 Convergncia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

iv


6/215

Feofiloff SUMRIO v

4 Heurstica Simplex 394.1 Introduo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394.2 A heurstica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.3 Anlise: invariantes . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.4 Mais trs invariantes . . . . . . . . . . . . . . . . . . . . . . . . . . 444.5 Convergncia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454.6 Concluso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.7 Apndice: Simplex Revisto . . . . . . . . . . . . . . . . . . . . . . 47

5 Algoritmo Simplex 505.1 Ordem lexicogrfica . . . . . . . . . . . . . . . . . . . . . . . . . . 505.2 Regra lexicogrfica . . . . . . . . . . . . . . . . . . . . . . . . . . . 515.3 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515.4 Anlise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5.5 Convergncia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.6 Nmero de operaes aritmticas . . . . . . . . . . . . . . . . . . . 605.7 Concluso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615.8 Apndice: Segunda fase do Simplex . . . . . . . . . . . . . . . . . 615.9 Apndice: Regra de Bland . . . . . . . . . . . . . . . . . . . . . . . 62

6 Forma tradicional do Simplex 646.1 Sistemas matriz-vetor-vetor . . . . . . . . . . . . . . . . . . . . . . 646.2 Sistemas simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656.3 Algoritmo Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

6.4 Invariantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666.5 Concluso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

II Programao Linear 68

7 Problema cannico primal 697.1 Definio do problema . . . . . . . . . . . . . . . . . . . . . . . . . 697.2 Problemas simples . . . . . . . . . . . . . . . . . . . . . . . . . . . 717.3 O Simplex resolve o problema . . . . . . . . . . . . . . . . . . . . . 737.4 Concluso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

7.5 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

8 Problema cannico dual 778.1 Definio do problema . . . . . . . . . . . . . . . . . . . . . . . . . 778.2 Lema da dualidade . . . . . . . . . . . . . . . . . . . . . . . . . . . 788.3 Vetores de inviabilidade . . . . . . . . . . . . . . . . . . . . . . . . 80


7/215

Feofiloff SUMRIO vi

8.4 Algoritmo baseado no Simplex . . . . . . . . . . . . . . . . . . . . 818.5 Teorema da dualidade . . . . . . . . . . . . . . . . . . . . . . . . . 838.6 Concluso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 848.7 Apndice: Uma interpretao do Simplex . . . . . . . . . . . . . . 84

8.8 Apndice: Problema do vetor vivel . . . . . . . . . . . . . . . . . 85

9 Problema geral 879.1 Definio do problema . . . . . . . . . . . . . . . . . . . . . . . . . 879.2 Dualidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 889.3 Lema da dualidade . . . . . . . . . . . . . . . . . . . . . . . . . . . 889.4 Construo do dual . . . . . . . . . . . . . . . . . . . . . . . . . . . 909.5 Teorema da dualidade . . . . . . . . . . . . . . . . . . . . . . . . . 929.6 Reduo ao problema cannico primal . . . . . . . . . . . . . . . . 939.7 Concluso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

9.8 Apndice: Uma interpretao do dual . . . . . . . . . . . . . . . . 96

III Algoritmos para Dados Inteiros 99

10 Determinantes 10010.1 Sinal de uma matriz de permutao . . . . . . . . . . . . . . . . . 10010.2 Determinante de matriz quadrada . . . . . . . . . . . . . . . . . . 10210.3 Trs propriedades bsicas . . . . . . . . . . . . . . . . . . . . . . . 10410.4 Determinante do produto de matrizes . . . . . . . . . . . . . . . . 10510.5 Delimitao do determinante . . . . . . . . . . . . . . . . . . . . . 10810.6 Concluso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

11 Algoritmo de Gauss-Jordan-Chio 11111.1 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11111.2 Anlise: preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . 11211.3 Anlise: invariante principal . . . . . . . . . . . . . . . . . . . . . . 11611.4 Delimitao dos nmeros gerados . . . . . . . . . . . . . . . . . . 11911.5 Aplicao a matrizes inteiras . . . . . . . . . . . . . . . . . . . . . 12011.6 Concluso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

12 Algoritmo Simplex-Chio 12412.1 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12412.2 Anlise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12612.3 Aplicao a matrizes inteiras . . . . . . . . . . . . . . . . . . . . . 12612.4 Concluso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

13 Problemas com dados inteiros 129


8/215

Feofiloff SUMRIO vii

13.1 Sistemas de equaes . . . . . . . . . . . . . . . . . . . . . . . . . . 12913.2 Problemas cannicos . . . . . . . . . . . . . . . . . . . . . . . . . . 13013.3 Concluso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

IV Algoritmos Polinomiais 132

14 Introduo aos algoritmos polinomiais 13314.1 Problemas CD, PV, V e PI . . . . . . . . . . . . . . . . . . . . . . . 13414.2 Reduo do CD ao PV . . . . . . . . . . . . . . . . . . . . . . . . . 13514.3 Reduo do PV ao V . . . . . . . . . . . . . . . . . . . . . . . . . . 13614.4 Reduo do V ao PI . . . . . . . . . . . . . . . . . . . . . . . . . . 13814.5 Concluso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

15 Algoritmo de Yamnitsky-Levin 141

15.1 Definies bsicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14115.2 Tetraedros e seus volumes . . . . . . . . . . . . . . . . . . . . . . . 14215.3 Teorema do tetraedro interior . . . . . . . . . . . . . . . . . . . . . 14415.4 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14815.5 Invariantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15015.6 O algoritmo est bem definido . . . . . . . . . . . . . . . . . . . . 15015.7 ltima iterao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15115.8 Demonstrao dos invariantes . . . . . . . . . . . . . . . . . . . . . 15215.9 Nmero de iteraes . . . . . . . . . . . . . . . . . . . . . . . . . . 15415.10 Nmero de operaes aritmticas . . . . . . . . . . . . . . . . . . 15615.11 Concluso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15715.12 Apndice: Matriz com uma s linha . . . . . . . . . . . . . . . . . 157

V Apndices 160

A Simplex Dual 161A.1 Matrizes simples no sentido dual . . . . . . . . . . . . . . . . . . . 161A.2 Esboo do Simplex Dual . . . . . . . . . . . . . . . . . . . . . . . . 162A.3 Heurstica Simplex Dual . . . . . . . . . . . . . . . . . . . . . . . . 164

A.4 Algoritmo Simplex Dual . . . . . . . . . . . . . . . . . . . . . . . . 166A.5 Problema cannico dual . . . . . . . . . . . . . . . . . . . . . . . . 166

B Anlise de sensibilidade 169B.1 Variao de um s componente . . . . . . . . . . . . . . . . . . . . 169B.2 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172B.3 Valor timo como funo de b e c . . . . . . . . . . . . . . . . . . . 174


9/215

Feofiloff SUMRIO viii

B.4 Concluso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

C Poliedro cannico primal 178C.1 Dependncia linear . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

C.2 Combinaes convexas . . . . . . . . . . . . . . . . . . . . . . . . . 179C.3 Vrtices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180C.4 Solues do problema cannico primal . . . . . . . . . . . . . . . . 182C.5 Poliedros limitados . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

D Poliedro cannico dual 185D.1 Conjuntos geradores . . . . . . . . . . . . . . . . . . . . . . . . . . 185D.2 Combinaes convexas . . . . . . . . . . . . . . . . . . . . . . . . . 186D.3 Vetores bsicos e faces minimais . . . . . . . . . . . . . . . . . . . 187D.4 Solues do problema cannico dual . . . . . . . . . . . . . . . . . 188

D.5 Poliedros limitados . . . . . . . . . . . . . . . . . . . . . . . . . . . 189E Exerccios resolvidos 192

E.1 Soluo do exerccio 2.5 . . . . . . . . . . . . . . . . . . . . . . . . 192E.2 Soluo do exerccio 2.11 . . . . . . . . . . . . . . . . . . . . . . . . 192E.3 Soluo do exerccio 2.13 . . . . . . . . . . . . . . . . . . . . . . . . 194E.4 Soluo do exerccio 4.2 . . . . . . . . . . . . . . . . . . . . . . . . 196E.5 Soluo do exerccio 4.3 . . . . . . . . . . . . . . . . . . . . . . . . 197

Referncias Bibliogrficas 199

ndice Remissivo 202


10/215

Captulo 1

Vetores e Matrizes

Vetor? uma espcie de linha reta com uma flecha na ponta.

Matriz? Acho que onde fica a sede da empresa.

Este captulo faz um resumo de conceitos elementares de lgebra linear e intro-duz as convenes de notao que usaremos nos captulos subseqentes. O con-tedo do captulo muito simples, mas algumas das definies e convenes denotao merecem ateno pois so pouco usuais.

1.1 Vetores

Um vetor uma funo que leva um conjunto finito arbitrrio o conjuntode ndices no conjunto dos nmeros reais (mas no h mal em restringir

a ateno aos nmeros racionais). Convm no presumir qualquer relao deordem sobre o conjunto de ndices. Se o conjunto de ndices de um vetor x N,diremos que x est definido sobre N.

Se x um vetor sobre um conjunto N e n um elemento de N ento x[n] x[n]denota o componente n de x, isto , o valor da funo x em n. Se Q uma partede N ento

x[Q]

denota a restrio de x a Q, ou seja, o vetor cujo componente q x[q] para cadaq em Q. Note a distino entre x[n] e x[{n}] : o primeiro um nmero, enquantoo segundo um vetor (com um s componente).

Um vetor x sobre N nulo se x[n] = 0 para todo n em N. O vetor nulo ser vetor nuloodenotado por o, qualquer que seja o seu conjunto de ndices.Se x um vetor e um nmero ento x o vetor que se obtm mediante

multiplicao de cada componente de x por . Analogamente, x/ o vetorque se obtm dividindo por cada componente de x.

Se x e y so vetores sobre um mesmo conjunto de ndices e x[n] y [n] paracada n, dizemos que x y . Analogamente, dizemos que x y

1


11/215

Feofiloff cap. 1 Vetores e Matrizes 2

x > y

se x[n] > y [n] para todo n. As relaes e < so definidas de modo anlogo.

4 3 1 213 22 11 14 11 14 22 13

Figura 1.1: Duas representaes de um vetor sobre 1, 2, 3, 4. Na se-gunda, fica subentendido que os ndices so 1, 2, 3 e 4 da esquerdapara a direita.

1 11

2 14

4 13

3 22

11

14

22

13

Figura 1.2: Mais duas representaes do mesmo vetor. Na segunda,fica subentendido que os ndices so 1, 2, 3 e 4 de cima para baixo.

1.2 Matrizes

Uma matriz uma funo que leva o produto cartesiano de dois conjuntos fini-tos no conjunto dos nmeros reais (poderamos restingir a definio ao conjunto

dos racionais). Convm no presumir qualquer relao de ordem sobre os con-juntos de ndices.Se uma matriz A tem domnio M N, dizemos que M o conjunto de n-

dices de linhas e N o conjunto de ndices de colunas de A. Dizemos tambmque A uma matriz definida sobre M N.

Se m e n so elementos de M e N respectivamente ento A[m, n] denota o A[m, n]componente m, n de A, ou seja, o valor de A em m, n. Se P e Q so partes deM e N respectivamente ento

A[P, Q]

a restrio de A a P Q. Usaremos a abreviatura A[P, ] (leia A P tudo) para A[P, ]

A[P, N] e a abreviatura A[ , Q] para A[M, Q] . Se m um elemento de M ento A[ , Q]

A[m, Q]

o vetor sobre Q cujo componente q A[m, q] para todo q em Q. Usaremos aabreviatura A[m, ] para A[m, N] e diremos que esse vetor a linha m de A. A[m, ]

linhaAnalogamente, para qualquer parte P de M e qualquer elemento n de N, aexpresso A[P, n] denota o vetor cujo componente p A[p,n] para cada p em P. A[P, n]


12/215


1 2 3 4 5 6

7 1 0 0 1 2 38 0 1 0 4 5 69 0 0 1 7 8 9

4 2 5 3 1 6

7 1 0 2 0 1 39 7 0 8 1 0 98 4 1 5 0 0 6

2 4 5 3 1 6

7 1 0 2 0 1 39 7 0 8 1 0 98 4 1 5 0 0 6

Figura 1.3: Representao de trs matrizes sobre os mesmos conjuntos dendices. Os ndices de linhas so 7, 8 e 9. Os ndices de colunas so 1, 2, 3,4, 5 e 6. As duas primeiras figuras representam a mesma matriz; a terceirarepresenta uma matriz diferente.

99 4 12 13 7798 14 19 7 8832 11 22 9 6

Figura 1.4: Quando os ndices de uma matriz no esto indica-dos explicitamente, fica subentendido que os ndices das linhasso 1, 2, 3, . . . de cima para baixo e que os ndices das colunasso 1, 2, 3, . . . da esquerda para a direita.

a b c d e f g

f 3 1 9 0 0 4 9g 4 0 8 1 0 5 9h 5 0 7 0 1 6 9

b d e

f 1 0 0g 0 1 0h 0 0 1

Figura 1.5: A primeira figura representa uma matriz A. A se-gunda representa a matriz A[ , Q] , onde Q o conjunto composto

pelos ndices b,d,e.

Usaremos a abreviatura A[ , n] para A[M, n] e diremos que este vetor a coluna A[ , n]colunan de A.

Convm no confundir as expresses A[P, n] e A[P, {n}] : a primeira denotaum vetor, enquanto a segunda denota uma matriz (com uma s coluna). Algunslivros mais antigos fazem essa confuso conscientemente, e usam a expressovetor coluna para designar qualquer matriz dotada de uma nica coluna e aexpresso vetor linha para uma matriz com uma nica linha.

Uma matrizA

nula seA

[m, n]= 0

para todo parm, n

. A matriz nula sermatriz nulaOdenotada por O, quaisquer que sejam os seus conjuntos de ndices.

Se A uma matriz e um nmero ento A a matriz que se obtm Aquando cada componente de A multiplicado por . Analogamente, A/ o A/vetor que se obtm dividindo por cada componente de A.


13/215


1.3 Produtos

Matrizes e vetores podem ser multiplicados entre si. A verso mais bsica dessaoperao de multiplicao envolve dois vetores.

Produto vetor-por-vetor. Para quaisquer vetores x e y sobre um mesmoconjunto N, o produto de x por y o nmero

nN

x[n] y [n] ,

que denotaremos por x y . bvio que x y = y x. Ademais, para qualquer x yparte Q de N,

x y = x[Q] y [Q] + x[NQ] y [NQ] .

a b c d e

11 22 33 44 55

e b d c a

35 41 37 39 43

Figura 1.6: Se x e y so os vetores definidos pela figura ento x y =11 43 + 22 41 + 33 39 + 44 37 + 55 35 = 6215. Imagine que a,b,c,d,eso os modelos de um produto fabricado por certa empresa e que y[n] olucro sobre cada unidade do modelo n. Se foram fabricadas x[n] unidadesdo modelo n ento x y o lucro total.

Produtos matriz-por-vetor e vetor-por-matriz. Para qualquer matriz A so- produtomatriz porvetor

bre M N e qualquer vetor x sobre N, o produto de A por x o vetor A x

A xdefinido pela expresso

(A x)[m] = A[m, ] x

para cada m em M. claro que A x um vetor sobre M. Analogamente, para produto vetorpor matrizqualquer vetor y sobre M, o produto de y por A o vetor y A definido pelay Aexpresso

(y A)[n] = y A[ , n]

para cada n em N. fcil verificar que, para qualquer parte P de M e qualquer

parte Q de N,(A x)[P] = A[P, ] x e (y A)[Q] = y A[ , Q] .

menos fcil verificar a propriedade associativa

y (A x) = (y A) x .


14/215


Produto matriz-por-matriz. Para qualquer matriz A sobre L M e qual-quer matriz B sobre M N, o produto de A por B a matriz A B sobre L N A Bdefinida pela expresso

(A B)[l, n] = A[l, ] B [ , n]

para cada l em L e cada n em N. fcil verificar que, para qualquer parte P deL e qualquer parte Q de N,

(A B)[P, Q] = A[P, ] B [ , Q] .

menos fcil verificar a propriedade associativa propriedadeassociativa

(A B) C = A (B C) ,

vlida para quaisquer matrizes A, B e C cujos conjuntos de ndices permitamdefinir os produtos A B e B C. Analogamente, A (B x) = (A B) x e

(y A) B = y (A B) para quaisquer vetores x e y , desde que cada um dosprodutos faa sentido.

Notao. Vamos apelar, muitas vezes, ao princpio universal da preguia xye escrever xy , Ax, yA e AB no lugar de x y , A x, y A e A B respectivamente. Ax yA

ABO operador de indexao [ , ] tem precedncia sobre o operador de multi-plicao. Assim, expresses da forma BA [P, Q] e yA [P, Q] devem ser entendidas BA[P, Q]como B (A[P, Q]) e y (A[P, Q]) respectivamente. Em certas condies, os doisoperadores comutam: se os produtos BA e yA fazem sentido ento

(BA)[ , Q] = B (A[ , Q]) e (yA)[ , Q] = y (A[ , Q]) .

1.4 Matrizes inversveis

O problema mais bsico da lgebra linear o da inverso das operaes de mul-tiplicao que definimos acima: dada uma matriz A e um vetor b,

encontrar um vetor x tal que Ax = b .

Analogamente, dado um vetor c, encontrar um vetor y tal que yA = c. Ouainda, dadas matrizes A e B , encontrar uma matriz X tal que AX = B ; analo-gamente, dadas matrizes A e C, encontrar uma matriz Y tal que Y A = C. Estes

problemas levam naturalmente aos seguintes conceitos.Uma matriz I sobre M N a identidade se M = N e, para cada par i, j identidade

de elementos de M,

I[i, j] = se i = j ento 1 seno 0 .

Toda matriz identidade ser denotada por I, quaisquer que sejam seus conjun- Itos de ndices.


15/215


a b d c

a 1 0 0 0b 0 1 0 0c 0 0 1 0

d 0 0 0 1

Figura 1.7: Esta matriz no a identidade.

Uma inversa esquerda de uma matriz A uma matriz E tal que EA = inversaesquerdaI. Uma matriz A inversvel pela esquerda se possui uma inversa esquerda.

A inversa direita de uma matriz A uma matriz D tal que AD = I. Uma matriz inversadireitaA inversvel pela direita se possui uma inversa direita.

Se uma matriz tem uma inversa esquerda e uma inversa direita ento asduas inversas so iguais. De fato, se AD = I e EA = I ento

E = E(AD) = (EA)D = D .

Ademais, as inversas so nicas. De fato, para qualquer matriz D tal que AD =I tem-se D = (EA)D = E(AD) = E = D. Analogamente, para qualquer E

tal que EA = I tem-se E = E.A propsito, eis um fato fundamental mas no-trivial: uma matriz que tenha

o mesmo nmero de linhas e colunas tem inversa direita se e s se tem inversaesquerda. Este fato ser demonstrado, implicitamente, no prximo captulo.

Os problemas que mencionamos no incio da seo podem ser imediata-mente resolvidos se tivermos uma matriz inversa apropriada. Por exemplo, se

A tem uma inversa esquerda e direita E, ento o vetor x = Eb satisfaz a equaoAx = b.

1 2 2 0 00 1 1 0 00 0 2 0 00 1 1 1 0

1 2 0 00 1 1/2 00 0 1/2 00 1 1 11 2 3 4

Figura 1.8: A primeira matriz uma inversa esquerda da se-gunda (e a segunda uma inversa direita da primeira).

1.5 Transposio

A transposta de uma matriz A sobre MN amatriz A definida pelas equaes transpostaAA[n, m] = A[m, n]


16/215


1/2 0 0 00 0 0 00 0 5 00 0 0 2

Figura 1.9: Uma matriz no-inversvel.

para cada par m, n. Portanto, A uma matriz sobre N M. claro que atransposta de A A. fcil verificar que

Ax = x Apara todo vetor x tal que o produto de A por x esteja definido. Tambm fcilverificar que

AB = B Apara toda matriz B tal que o produto de A por B esteja definido.

1.6 Matrizes de bijeo

A seguinte generalizao do conceito de matriz identidade muito til. Umamatriz J sobre M N de bijeo1 se existe uma funo bijetora de M em matriz

de bijeoN tal queJ[m, n] = se (m) = n ento 1 seno 0 .

Portanto, uma matriz com componentes 0 e 1 de bijeo se cada uma de suascolunas tem exatamente um 1 e cada uma de suas linhas tem exatamente um 1. bvio que |M| = |N| se existe uma matriz de bijeo sobre M N.

A transposta de uma matriz de bijeo sobre M N uma matriz de bijeosobre N M. Essa segunda matriz inversa da primeira, como mostraremos aseguir.

Fato SeJ uma matriz de bijeo entoJ J = I e J J = I.DEMONSTRAO: Para qualquer par i, j de ndices de linhas de J, o com-

ponente i, j de JJ o produto de duas linhas de J:(JJ)[i, j] = J[i, ] J[ , j] = J[i, ]J[j, ] .

Como J matriz de bijeo, J[i, ]J[j, ] igual a 1 ou 0 conforme i = j ou i = j .Isso mostra que JJ = I. O mesmo raciocnio, com J no papel de J, mostra queJ J = I. P

1 Generaliza o conceito de matriz de permutao; uma matriz de permutao uma matrizde bijeo cujo conjunto de ndices de linhas idntico ao conjunto de ndices de colunas.


17/215


Qual o resultado da multiplicao de uma matriz arbitrria por uma matrizde bijeo? Suponha que J uma matriz de bijeo sobre M N. Digamos queJ[m, n] = 1 para algum m em M e algum n em N. Ento, para qualquer matrizA cujo conjunto de ndices de linhas seja N, a linha m de J A idntica linhan de A:

(JA)[m, ] = A[n, ] .

Analogamente, para qualquer matriz B que tenha colunas indexadas por M, acoluna n de BJ idntica coluna m de B . Em suma, a pr-multiplicao deA por J apenas redefine os nomes das linhas de A, e a ps-multiplicao de Bpor J apenas redefine os nomes das colunas de B .

0 0 1 01 0 0 00 0 0 10 1 0 0

Figura 1.10: Uma matriz de bijeo.

1.7 Matrizes diagonais

Uma matriz D sobre M N diagonal se M = N e D [m, n] = 0 sempre que diagonalm = n. Em particular, toda matriz identidade diagonal.

Se D uma matriz diagonal tal que D [m, m] = 0 para todo m ento a matriz

diagonal E definida pelas equaes

E[m, m] = 1/D[m, m]

uma inversa esquerda e tambm uma inversa direita de D. Portanto, E anica inversa de D. Por outro lado, se D uma matriz diagonal e D [m, m] = 0para algum m ento fcil verificar que D no tem inversa.

1.8 Matrizes elementares

Uma matriz-coluna coincide com a identidade em todas as colunas, exceto tal- matriz-

colunavez uma. Em outras palavras, uma matriz F sobre M M uma matriz-colunase existe k em M tal que

F[M, Mk] = I[M, Mk] ,

onde M k uma abreviatura de M {k}. Diremos que k a coluna saliente M kcolunasaliente

da matriz.


18/215


Fato Para qualquer matriz-coluna F com coluna saliente k, seF[k, k]no nulo ento a matriz-coluna G com coluna salientek definida pelasequaes

G[k, k] =1

F[k, k]e G[m, k] =

F[m, k]F[k, k]

para cada m em M k uma inversa esquerda e tambm uma inversadireita deF.

DEMONSTRAO: Mostremos inicialmente que GF = I. Na coluna k te-mos (GF)[k, k] = G[k, ]F[ , k] = G[k, k]F[k, k] = F[k, k]/F[k, k] = 1; ademais,

(GF)[m, k] = G[m, ]F[ , k]

= G[m, m] F[m, k] + G[m, k] F[k, k]

= F[m, k] F[k, k] F[m, k]/F[k, k]

= 0

para cada m em M k . Portanto, a coluna k de GF igual coluna k da matrizidentidade. Para concluir, considere as colunas distintas de k:

(GF)[ , Mk] = GF[ , Mk] = GI[ , Mk] = G[ , Mk] = I[ , Mk] .

Portanto, GF = I. Para mostrar que F G = I, basta observar que as mesmasregras que definem G a partir de F tambm geram F a partir de G. P

Nas condies da proposio acima, G a nica inversa (esquerda e direita)de F. Tambm fcil verificar que se F[k, k] = 0 para algum k ento F no tem

inversa.

1 0 0 4 00 1 0 5 00 0 1 6 00 0 0 7 00 0 0 8 1

1 0 0 4/7 00 1 0 5/7 00 0 1 6/7 00 0 0 1/7 00 0 0 8/7 1

Figura 1.11: Matrizes-coluna com coluna saliente 4. Uma in-versa da outra.

Uma matriz F sobre M M uma matriz-linha se existe h em M tal que matriz-linhaF[Mh, M] = I[Mh, M] . Diremos que h a linha saliente de F. Uma obser-

vao anloga que demonstramos acima vale para matrizes-linha: se F umamatriz-linha com linha saliente h e F[h, h] = 0 ento a matriz-linha G com linhasaliente h definida pelas equaes

G[h, h] = 1/F[h, h] e G[h, n] = F[h, n]/F[h, h]


19/215


para cada n em Mh a nica inversa esquerda de F e tambm a nica inversadireita de F.

Diremos que uma matriz elementar se for uma matriz-coluna ou uma matrizelementarmatriz-linha. Note que os conjuntos de ndices de linhas e colunas de uma

matriz elementar so idnticos. Matrizes elementares e suas inversas tero umpapel de destaque nos captulos subseqentes.

1.9 Combinaes lineares

Suponha que a1 , . . , ak so vetores sobre um mesmo conjunto de ndices. Umacombinao linear desses vetores qualquer vetor da forma

1a1 + + kak ,

onde 1, . . , k so nmeros. Esses nmeros so os coeficientes da combinao

linear.Suponha que A uma matriz sobre M N. Para todo vetor x sobre N, ovetor Ax uma combinao linear das colunas de A com coeficientes x[j] , isto ,

Ax =jN A[ , j] x[j] .

Analogamente, para todo vetor y sobre M, o vetor yA uma combinao lineardas linhas de A, isto ,

yA =

iM y [i] A[i, ] .

Se A e B so matrizes tais que o produto AB faz sentido ento cada colunade AB uma combinao linear das colunas de A e cada linha de AB umacombinao linear das linhas de B :

(AB)[ , j] = A B [ , j] e (AB)[i, ] = A[i, ] B .

Exerccios

1.1 Demonstre a propriedade associativa do produto de matrizes: se cada umdos produtos faz sentido, ento A(BC) = (AB)C.

1.2 Mostre que o produto de matrizes no comutativo: AB , em geral, dife-rente de BA (mesmo que os dois produtos estejam definidos).

1.3 Suponha que x e y so vetores e que A e B so matrizes. Quantas opera-es de multiplicao so necessrias para calcular xy? para calcular Ax?yA? AB?

1.4 Suponha que AB = I e BC = I. Mostre que B inversa direita de C.


20/215


1.5 Seja A a primeira das matrizes abaixo. Encontre uma matriz de bijeo Jtal que AJ seja a segunda das matrizes. Encontre uma matriz de bijeo Jtal que J A seja a terceira matriz.

a b c d ef 11 12 13 14 15g 21 22 23 24 25k 31 32 33 34 35

b c a f hf 11 12 13 14 15g 21 22 23 24 25k 31 32 33 34 35

a b c d eg 11 12 13 14 15k 21 22 23 24 25i 31 32 33 34 35

1.6 Sejam F e G matrizes sobre MM e D uma matriz sobre MN. Suponhaque F G = I e que a matriz E = GD de bijeo. Verifique que D EG = I.

1.7 Suponha que A uma matriz de bijeo sobre M N e b um vetor arbi-trrio sobre M. Verifique que existe um e um s vetor x tal que Ax = b.


21/215

Parte I

Algoritmos Bsicos

12


22/215

Captulo 2

Algoritmo de Gauss-Jordan

Encontre nmeros x1 , x2 , x3 e x4 que satisfaam as equaes

d11 x1 + d12 x2 + d13 x3 + d14 x4 = b1

d21 x1 + d22 x2 + d23 x3 + d24 x4 = b2d31 x1 + d32 x2 + d33 x3 + d34 x4 = b3

O algoritmo de Gauss-Jordan1 a ferramenta bsica da lgebra linear. O algo-ritmo transforma qualquer matriz em uma matriz equivalente dotada de umcerto desenho ou padro, que descreveremos na seo 2.1.

Ao estudar qualquer algoritmo, preciso enfrentar duas perguntas: o queo algoritmo faz? como faz o que faz? No caso do algoritmo de Gauss-Jordan,ao contrrio do que ocorre com outros algoritmos clebres, mais fcil tratar dasegunda pergunta. Assim, comearemos com um esboo de como o algoritmo

funciona.

2.1 Matrizes escalonadas

Uma matriz E sobre M N escalonada se existem uma parte P de M e uma matrizescalonadaparte Q de N tais que

E[P, Q] uma matriz de bijeo e E[MP, N] = O .

Os conjuntos P e Q so as bases da matriz; o conjunto Q a base de colunas e P bases a base de linhas. bvio que toda matriz escalonada tem uma nica base de

linhas, mas pode ter vrias bases de colunas distintas. (Convm lembrar que noestamos fazendo quaisquer restries sobre os valores relativos de |M| e |N|.Tambm no estamos presumindo qualquer relao de ordem em M ou N.)

1 Referncias ao clebre Carl Friedrich Gauss() e ao (menos clebre) Wilhelm Jordan(), que popularizou o algoritmo [Jor20].

13
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Gauss.html


23/215

Feofiloff cap. 2 Algoritmo de Gauss-Jordan 14

Q

0 0 0 0 10 0 0 1 00 0 1 0 0 P0 1 0 0 01 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0

Figura 2.1: Matriz escalonada.

0 0 0 00 0 0 00 0 0 0

0 1 0 01 0 0 00 0 1 00 0 0 10 0 0 0

0 0 0 0 0 00 2 1 44 66 11 33 0 55 77 00 0 0 0 0 0

Figura 2.2: Exemplos de matrizes escalonadas. A primeira tembases e . A segunda tem base de linhas 1, 2, 3, 4 e base decolunas 1, 2, 3, 4. Na ltima, a base de linhas {2, 3} e h duas

bases de colunas distintas: {1, 3} e {1, 6}.

2.2 Esboo do algoritmo

O algoritmo de Gauss-Jordan recebe uma matriz D sobre M N e transforma DM ND numa matriz escalonada. Cada iterao do algoritmo comea com uma parte

P de M e uma matriz E. A primeira iterao comea com P = e E = D. Cada PEiterao consiste no seguinte:

CASO 1: E[MP, ] = O .Escolha h em M P e k em N de modo que E[h, k] = 0.Seja E a matriz definida pelas equaes E [h, ] = E[h, ]/E[h, k] eE [i, ] = E[i, ] E[i, k] E[h, ]/E[h, k] para cada i em M h.Comece nova iterao com P + h e E nos papis de P e E.

CASO 2: E[MP, ] = O .Devolva E e pare. P

A expresso P + h uma abreviatura de P {h}. claro que se P = M noincio de uma iterao ento aplica-se o caso 2.

No incio de cada iterao existe uma parte Q de N tal que E[P, Q] umamatriz de bijeo e E[MP, Q] nula. A demonstrao desta propriedade serfeita mais adiante, depois que o algoritmo for reescrito de modo mais completo.Se a propriedade vale no incio da ltima iterao ento bvio que a matriz E escalonada.


24/215


1 1 2 02 1 5 12 2 4 0

1 1 3 1

0 1/2 1/2 1/21 1/2 5/2 1/20 1 1 10 3/2 1/2 1/2

0 1 1 11 0 3 10 0 0 00 0 1 1

0 1 0 01 0 0 20 0 0 0

0 0 1 1

Figura 2.3: Aplicao do esboo do algoritmo de Gauss-Jordan. A figura descreve a matriz E no incio de sucessivasiteraes. A ltima matriz escalonada.

1 1 0 2 1 1 0 1 1 1 2 01 2 0 5 8 5 0 3 2 1 5 1

2 2 1 4 2 0 1 0 2 2 4 01 1 0 3 3 2 0 1 1 1 3 1

Figura 2.4: A figura define matrizes F, G e D . Verifique queF G a identidade e que GD escalonada.

1 0 0 0 1 0 2 3 4 1 0 2 3 40 1 0 0 0 1 4 5 6 0 1 4 5 60 0 0 0 6 7 8 9 0 0 0 0 0 00 0 0 0 9 8 7 6 5 0 0 0 0 0

Figura 2.5: A figura define matrizes G e D e exibe GD. Observe queGD escalonada mas no existe F tal que F G = I.


25/215


2.3 Algoritmo

Para dizer, exatamente, o queo algoritmo faz preciso especificar a relao entreas matrizes E e D. A matriz E equivalente matriz D no seguinte sentido:existe uma matriz inversvel G tal que

E = GD .

O esboo da seo anterior no devolve G, o que impede o usurio de conferir aequivalncia entre E e D. A verso do algoritmo que descreveremos abaixo de-volve G e sua inversa F; o usurio pode ento, ao preo de duas multiplicaesde matrizes, verificar que G inversvel e que GD escalonada.

Algoritmo de Gauss-Jordan Recebe uma matrizD sobreM N e de-volve matrizes F eG sobreM M tais queF G = I eGD escalonada.

Cada iterao comea com matrizes F, G e E e uma parte P de M. No FGincio da primeira iterao, F = G = I, E = D e P = . Cada iterao consiste

no seguinte:

CASO 1: E[h, ] = o para algum h em M P . hEscolha k em N tal que E[h, k] = 0. kSeja F, G, E o resultado da pivotao de F,G,Eem torno de h, k.Comece nova iterao com F , G , E e P + hnos papis de F, G, E e P.

CASO 2: E[MP, ] = O .Devolva F, G e pare. P2

A operao de pivotao a que se refere o texto do algoritmo definida daseguinte maneira: dados elementos h de M e k de N, o resultado da pivota- pivotaoo de F,G,E em torno de h, k o terno F, G, E de matrizes definido pelasequaes

F[ , h] = D[ , k] , F[ , i] = F[ , i] ,

G[h, ] = h G[h, ] , G[i, ] = G[i, ] + i G[h, ] ,

E[h, ] = h E[h, ] , E[i, ] = E[i, ] + i E[h, ] ,

para cada i em M h, onde

h = 1 / E[h, k] e i = E[i, k] / E[h, k] .

Nmero de iteraes. claro que o algoritmo de Gauss-Jordan con-verge ou seja, sua execuo pra depois de um nmero finito de iteraes convergepois P aumenta a cada ocorrncia do caso 1. O nmero total de iteraes , nomximo, |M|.

2 Veja exerccio 2.5.


26/215


1 0 0 0 1 0 0 0 1 1 2 00 1 0 0 0 1 0 0 2 1 5 10 0 1 0 0 0 1 0 2 2 4 00 0 0 1 0 0 0 1 1 1 3 1

1 1 0 0 1 1/2 0 0 0 1/2 1/2 1/20 2 0 0 0 1/2 0 0 1 1/2 5/2 1/20 2 1 0 0 1 1 0 0 1 1 10 1 0 1 0 1/2 0 1 0 3/2 1/2 1/2

1 1 0 0 2 1 0 0 0 1 1 11 2 0 0 1 1 0 0 1 0 3 12 2 1 0 2 0 1 0 0 0 0 01 1 0 1 3 2 0 1 0 0 1 1

1 1 0 2 1 1 0 1 0 1 0 01 2 0 5 8 5 0 3 1 0 0 22 2 1 4 2 0 1 0 0 0 0 01 1 0 3 3 2 0 1 0 0 1 1

Figura 2.6: Exemplo de aplicao do algoritmo de Gauss-Jordan. A fi-gura registra os valores de F, G e E no incio de sucessivas iteraes.

1 0 0 0 2 1 2 4 0 10 1 0 0 1 1 1 2 1 30 0 1 0 2 1 0 5 1 40 0 0 1 1 1 1 2 1 3

1/2 0 0 0 1 1/2 1 2 0 1/21/2 1 0 0 0 1/2 0 0 1 5/2

1 0 1 0 0 0 2 1 1 31/2 0 0 1 0 1/2 2 0 1 7/2

1 1 0 0 1 0 1 2 1 21 2 0 0 0 1 0 0 2 51 0 1 0 0 0 2 1 1 3

0 1 0 1 0 0 2 0 2 6

1/2 1 1/2 0 1 0 0 5/2 3/2 1/21 2 0 0 0 1 0 0 2 5

1/2 0 1/2 0 0 0 1 1/2 1/2 3/21 1 1 1 0 0 0 1 1 9

3 7/2 2 5/2 1 0 0 0 4 231 2 0 0 0 1 0 0 2 5

0 1/2 0 1/2 0 0 1 0 1 31 1 1 1 0 0 0 1 1 9

Figura 2.7: Exemplo de aplicao do algoritmo de Gauss-Jordan. A figuraregistra os valores de G e E no incio de sucessivas iteraes (F foi omitida porfalta de espao). Observe como a matriz identidade que estava inicialmente emG move-se para a direita, invadindo E.


27/215


2.4 Anlise do algoritmo

A chave para entender como e por que o algoritmo funciona est na seguintelista de propriedades. As propriedades valem no incio de cada iterao e so,por isso mesmo, chamadas invariantes.

Invariantes No incio de cada iterao do algoritmo,

(i1) E[P, Q] uma matriz de bijeo eE[MP, Q] = O ,(i2) F G = I e(i3) GD = E,

ondeQ uma parte deN (que poderamos chamar base de colunas daiterao).

Q

0 0 1P 0 1 0

1 0 00 0 00 0 00 0 0

Figura 2.8: Matriz E no incio de uma iterao do algoritmo de Gauss-Jordan.

Essas propriedades valem, em particular, no incio da ltima iterao,quando ocorre o caso 2. Nesse caso, E escalonada em virtude de (i1) e dadefinio do caso 2; alm disso, F G = I em virtude de (i2). Portanto, ao devol-ver F e G o algoritmo estar se comportanto como prometeu.

DEMONSTRAO DOS INVARIANTES: evidente que as propriedades va-lem no incio da primeira iterao (com P e Q vazios). Suponha agora que aspropriedades valem no incio de uma iterao qualquer que no a ltima. Entoocorre o caso 1 (com k em N Q) e as propriedades passam a valer com

F, G, E, P + h e Q + k

nos papis de F, G, E, P e Q. Para demonstrar esta afirmao basta verificarque no fim do caso 1 tem-se

E[ , Q] = E[ , Q] , (2.a)

E[ , k] = I[ , h] , (2.b)

FG = I , (2.c)

E = GD . (2.d)


28/215


Q k

0 0 1 0P 0 1 0 0

1 0 0 0

0 0 0 0h 0 0 0 10 0 0 0

Figura 2.9: Matriz E no fim do caso 1 do algoritmo de Gauss-Jordan.

A demonstrao de (2.a) elementar. Por definio da operao de pivotao,temos

E [h, ] = hE[h, ] e E [i, ] = E[i, ] + iE[h, ]

para cada i em M h. Como o vetor E[h, Q] nulo em virtude de (i1), temosE [ , Q] = E[ , Q] .

Antes de empreender as demonstraes de (2.b) a (2.d), conveniente daruma representao matricial operao de pivotao. Seja F a matriz elementar F(veja seo 1.8) sobre M M cuja coluna saliente, h, igual a E[ , k] , isto ,

F[ , h] = E[ , k] e F[ , Mh] = I[ , Mh] .

Seja G a inversa de F, isto , a matriz elementar com coluna saliente h definida Gpelas equaes

G[h, h] = 1/E[h, k] e G[i, h] = E[i, k]/E[h, k]

para cada i em M h. Observe que

F

G =

G

F = I. Observe tambm queF = FF , G = GG e E = GE .

As duas ltimas identidades so bvias. A primeira merece uma verificaomais cuidadosa: na coluna h temos

F [ , h] = D[ , k] = F G D [ , k] = F E[ , k] = F F[ , h]

e nas demais colunas temos

F [ , Mh] = F[ , Mh] = F I[ , Mh] = F F[ , Mh] .

Portanto, o resultado da pivotao de F,G,E em torno de h, k o terno dematrizes FF, GG, GE.

Agora podemos cuidar das demonstraes de (2.b) a (2.d). A demonstraode (2.b) decorre das igualdades GF = I e E = GE: para cada i em M,

E[i, k] = G[i, ]E[ , k]

= G[i, ]F[ , h]

= (GF)[i, h]

= I[i, h] .


29/215


A demonstrao de (2.c) fcil:

FG = (FF)(GG) = F(FG)G = F G = I .

A prova de (2.d) igualmente fcil: E = GE = G(GD) = (GG)D = GD. P

2.5 Mais invariantes

O algoritmo de Gauss-Jordan tem mais quatro invariantes, alm dos que dis-cutimos na seo anterior. No necessrio ter conscincia desses invariantesadicionais para compreender o funcionamento do algoritmo; mas eles so umprenncio de invariantes fundamentais do Simplex, cujo estudo empreendere-mos a partir do prximo captulo.


(i4) G[ , MP] = I[ , MP] ,(i5) F[ , MP] = I[ , MP] e F[ , P] = D [ , Q] J ,

onde J a transposta da matriz de bijeoE[P, Q] .

P M P Q N Q

0 0 0 0 0 10 0 0 0 1 0 P0 0 0 1 0 0

1 0 0 0 0 0

0 1 0 0 0 0 M P0 0 1 0 0 0

Figura 2.10: Matrizes G e E no incio de uma iterao do algoritmode Gauss-Jordan. A justaposio de G e E contm uma matriz de

bijeo que ocupa todas as linhas.

DEMONSTRAO: bvio que (i4) vale no incio da primeira iterao. Parademonstrar que o invariante permanece vlido no incio das demais iteraes,basta provar que no fim de cada ocorrncia do caso 1 temos

G [ , MPh] = G[ , MPh] ,

onde M Ph uma abreviatura de (MP){h}. A demonstrao anloga de (2.a). Por definio,

G [h, ] = hG[h, ] e G [i, ] = G[i, ] + iG[h, ]


30/215


para cada i em M h. Mas G[h, MPh] nulo em virtude de (i4). Logo,G [ , MPh] = G[ , MPh] .

O invariante (i5) segue imediatamente da maneira como F definida a par-tir de F em cada iterao. A multiplicao por

J apenas troca os nomes das

colunas que esto em Q de modo que E[P, Q] J seja a matriz identidade sobreP P. O invariante mostra que a varivel F no precisa ser atualizada a cadaiterao: ela pode muito bem ser calculada no caso 2, imediatamente antes dofim da execuo do algoritmo. P


(i6) D[MP, Q] = G[MP, P] D[P, Q] e(i7) D[P, Q] J G [P, P] = I,

onde J a transposta da matriz de bijeoE[P, Q] .

DEMONSTRAO: Seja i um elemento de M P. Em virtude de (i4), paracada i em M P,

G[i, P]D[P, Q] + D[i, Q] = G[i, P]D[P, Q] + G[i, MP]D[MP, Q]

= G[i, M]D[M, Q]

= (GD)[i, Q]

= E[i, Q]

= o ,

onde as duas ltimas igualdades so conseqncia de (i3) e (i1) respectivamente.

Logo, G[i, P]D[P, Q] = D [i, Q] . Isto demonstra (i6). Agora considere (i7). Emvirtude da segunda parte de (i5),

D [P, Q] J G [P, P] = F[P, P] G[P, P] .Mas F[P, P]G[P, P] = I por fora de (i2), (i4) e da primeira parte de (i5). P

O invariante (i6) mostra que, para cada i em M P, o vetor D[i, Q] umacombinao linear das linhas da matriz D [P, Q] . O invariante (i7) mostra queJ G [P, P] uma inversa direita de D [P, Q] . A propsito, os invariantes (i3) e (i4)mostram que J G [P, P] uma inversa esquerda de D [P, Q] .

2.6 Nmero de operaes aritmticas

No difcil estimar, em termos dos parmetros m = |M| e n = |N|, o nmerode operaes aritmticas que o algoritmo executa. possvel implementar o al-goritmo (veja exerccio 2.6, pgina 24) de modo que cada pivotao exija apenasmn multiplicaes e divises e menos que mn adies e subtraes. Como o


31/215


algoritmo executa no mximo m tais pivotaes, o nmero total de operaesaritmticas menor que

2m2n .

(A ttulo de comparao, observe que a multiplicao de G por D requer m2nmultiplicaes e outras tantas adies.)

O consumo total de tempo do algoritmo depende no s do nmero de ope-raes aritmticas mas tambm do tempo dispendido em cada operao. Antesde estimar esse tempo, preciso entender que tipo de nmeros o algoritmo ma-nipula. razovel restringir nosso universo aos nmeros racionais: como o nmeros

racionaisalgoritmo envolve apenas as operaes de soma, subtrao, multiplicao e di-viso, ele transforma nmeros racionais em outros nmeros racionais. Assim,se os componentes da matriz dada D so racionais ento os componentes dasmatrizes F, G e E sero sempre racionais.

Cada nmero racional tem a forma /, onde um inteiro e um inteirono-nulo. O nmero / representado pelo par ordenado , ; o primeiroelemento do par o numerador e o segundo o denominador da representa- numerador

denominadoro. O custo de uma operao aritmtica sobre nmeros racionais depende damagnitude dos numeradores e denominadores dos nmeros envolvidos. Sernecessrio, portanto, obter uma delimitao superior para os valores absolutosdos numeradores e denominadores gerados pelo algoritmo. Faremos isto no ca-ptulo 11. Podemos adiantar que esses nmeros so, em geral, muito maioresque os numeradores e denominadores dos componentes da matriz dada D.

2.7 Concluso

O algoritmo de Gauss-Jordan transforma qualquer matriz dada em uma ma-triz escalonada equivalente. O algoritmo, juntamente com sua anlise, constituiprova do seguinte teorema:

Para toda matrizD, existem matrizes F eG tais queF G = I eGD escalonada.

Vale tambm o seguinte adendo: se os componentes de D so nmeros racionaisento existem matrizes racionais F e G com as propriedades citadas.

O algoritmo de Gauss-Jordan muitas vezes executado de modo apenasaproximado: os nmeros so representados em ponto flutuante, com um n-mero fixo de dgitos, e as operaes aritmticas so executadas com erro de arre-dondamento. Os erros podem mascarar completamente os resultados; nmerosque deveriam ser nulos, por exemplo, podem se apresentar como diferentes dezero, e o algoritmo pode deixar de reconhecer o caso 2. H uma grande coleode truques que visam controlar, em alguma medida, tais erros de arredonda-mento [Chv83].


32/215


3 2 1 4 5 6 7 8 9 104 3 2 5 6 7 8 9 73 15 6 3 4 7 9 8 10 1 21 5 4 7 5 10 9 6 2 3

32 6 5 8 9 10 9 2 7 4

8 7 6 9 10 5 2 3 4 59 8 7 11 3 2 1 4 5 8

629/246 39615/16892 6827/25338 1687/12669 298/12669 955/50676 1970/12669173/246 11887/16892 10079/25338 2704/12669 748/12669 5203/50676 2309/12669

2/41 531/8446 3/4223 72/4223 155/4223 113/8446 24/4223130/123 7651/8446 1445/12669 896/12669 52/12669 937/25338 1109/12669

22/123 1281/4223 115/12669 1463/12669 311/12669 1462/12669 920/1266967/82 20105/16892 125/8446 1500/4223 290/4223 1893/16892 500/4223

73/82 20509/16892 75/8446 900/4223 174/4223 2825/16892 300/4223

0 0 1 0 0 0 0 14885/8446 7482125/50676 309364/126690 1 0 0 0 0 0 19365/8446 2279561/50676 91123/12669

1 0 0 0 0 0 0 907/4223 33379/8446 2114/42230 0 0 1 0 0 0 165/4223 1419745/25338 133228/126690 0 0 0 1 0 0 2205/4223 256175/12669 24730/126690 0 0 0 0 1 0 18515/8446 1326005/16892 33380/42230 0 0 0 0 0 1 19555/8446 1344593/16892 36920/4223

Figura 2.11: Ao receber a primeira matriz da figura, digamos D , o algoritmo de Gauss-Jordan poder devolver a segunda matriz no papel de G. A terceira matriz GD .

2.8 Aplicao: Sistemas de equaes

Considere o seguinte problema: Dada uma matrizA sobreM N e um vetorb sobre M, encontrar um vetor x tal que Ax = b. Para resolver o problema,comece por submeter A ao algoritmo de Gauss-Jordan. O algoritmo devolvermatrizes F e G tais que F G = I e GA escalonada.

Digamos que as bases de GA so P e Q e suponha inicialmente que o vetor(Gb)[MP] nulo. Seja x o nico vetor que satisfaz as equaes

x[NQ] = o e (GA)[P, Q] x[Q] = (Gb)[P] .

Este o vetor bsico associado base Q. claro que (GA)x = Gb, donde vetorbsicoF(GA)x = F(Gb) e portanto Ax = b.3

Suponha agora que (Gb)[h] no nulo para algum h em M P. claro quenesse caso no existe x tal que (GA)x = Gb. Nosso problema original tambmno tem soluo, como passamos a demonstrar. Seja g o vetor G[h, ] e observe

3 Esse mtodo de clculo de x no o mais eficiente. possvel obter x com apenas um terodo nmero de multiplicaes se o algoritmo de Gauss-Jordan for modificado de modo a produziruma matriz triangular no lugar da matriz de bijeo (GA)[P, Q] . Essa variante do algoritmo conhecida como mtodo de eliminao de Gauss [Chv83, cap.6] [CLRS01, cap.31].


33/215


quegA = (GA)[h, ] = 0 enquanto gb = (Gb)[h] = 0 .

Se existisse um vetor x tal que Ax = b teramos a contradio 0 = (gA)x =g(Ax) = gb = 0.

O vetor g constitui, portanto, um certificado facilmente verificvel de quea equao Ax = b no tem soluo.

Exerccios

2.1 Escreva um algoritmo que decide se uma dada matriz escalonada e emcaso afirmativo devolve o seu par de bases.

2.2 Mostre que GF = I no incio de cada iterao do algoritmo de Gauss-Jordan.

2.3 O algoritmo descrito no texto devolve apenas as matrizes F e G. Escrevauma verso que devolva tambm a matriz escalonada E e suas bases Pe Q.

2.4 Escreva uma verso do algoritmo de Gauss-Jordan em que a matriz F sejacalculada somente na ltima iterao.

2.5 Escreva o algoritmo de Gauss-Jordan em uma linguagem mais formal,mais prxima de PASCAL ou C. (Veja soluo parcial E.1 no apndice E.)Programe o algoritmo em um computador.

2.6 Escreva uma verso um pouco mais eficiente do algoritmo de Gauss-

Jordan: execute apenas implicitamente a parte da operao de pivotaoque afeta a base de colunas Q e a coluna k.

2.7 Suponha que a execuo do algoritmo de Gauss-Jordan interrompida noincio de uma iterao e que uma pivotao executada em torno de umelemento h de P (e no de M P, como usual) e um elemento k deN Q. claro que isso s faz sentido se E[h, k] = 0. Qual o efeito de tal pi-votao? A execuo do algoritmo pode ser retomada depois da pivotaoexcepcional?

2.8 Suponha que A e B so matrizes sobre M M e que P uma parte de M.Suponha ainda que AB = I e A[ , MP] = B [ , MP] = I[ , MP] . Mostre

que A[P, P]B [P, P] = I.2.9 Mostre que no incio de cada iterao do algoritmo de Gauss-Jordan a ma-

triz G[MP, P] completamente determinada pelas matrizes D [MP, Q] ,E[P, Q] e G[P, P] .

2.10 Sejam G, P e Q os valores das variveis G, P e Q no incio de uma itera-o. Sejam G, P e Q os valores das variveis G, P e Q no incio de outraiterao. Mostre que se P = P e Q = Q ento G[MP , ] = G[MP , ] .


34/215


2.11 Suponha que G1 e G2 so matrizes inversveis tais que G1D e G2D soescalonadas. Mostre que quaisquer bases de colunas, digamos Q1 e Q2 ,das duas matrizes escalonadas tm a mesma cardinalidade. Essa cardinali-dade comum o posto da matriz D. A propsito, diz-se que D tem postopleno se seu posto igual ao nmero de linhas da matriz. (Soluo noapndice E, pgina 192.)

2.12 Encontre nmeros x1, . . , x4 que satisfaam as equaes abaixo.

x1 + x2 + x3 + 3x4 = 63x1 + 4x2 + x3 + 8x4 = 18

x1 + x2 4x3 4x4 = 5

2.13 Resolva o seguinte problema: dada uma matriz A sobre M N, um vetorb sobre M e um vetor c sobre N, encontrar x tal que Ax = b e cx mnimo.O problema sempre tem soluo? (Veja apndice E, pgina 192.)


35/215

Captulo 3

Introduo ao Simplex

Encontre nmeros no-negativos x1 , x2 , x3 e x4 que satisfaam as equaes

d11 x1 + d12 x2 + d13 x3 + d14 x4 = d15

d21 x1 + d22 x2 + d23 x3 + d24 x4 = d25d31 x1 + d32 x2 + d33 x3 + d34 x4 = d35

e minimizem a soma d41 x1 + d42 x2 + d43 x3 + d44 x4

O algoritmo Simplex a ferramenta bsica da programao linear. O objetivo doalgoritmo transformar uma matriz dada em outra equivalente que contenhaum certo desenho ou padro, que descreveremos na seo 3.1.

Este captulo faz um esboo do Simplex, destacando seu parentesco com oalgoritmo de Gauss-Jordan discutido no captulo anterior. Nosso esboo contmtodos os elementos bsicos do Simplex, mas no chega a ser um algoritmo pois

em geral no converge. Os dois prximos captulos mostraro como refinar oesboo para transform-lo num algoritmo.Como no estudo de qualquer algoritmo, preciso enfrentar duas perguntas:

o que faz o Simplex? como faz o que faz? Este captulo trata principalmenteda segunda pergunta. A primeira ser respondida no prximo captulo. Umaterceira pergunta para queserve o Simplex? ser adiada at o captulo 7,ainda que isso possa tornar um tanto rida e indigesta a tarefa de entender oconceito de matriz simples.

3.1 Matrizes simples

Os dados do Simplex so uma matriz sobre M N, um elemento n de N e um n melemento m de M. Diremos que n a coluna especial e que m a linha es- coluna

especial

linhaespecial

pecial da matriz. Nas figuras, a coluna especial ser sempre a que estiver mais direita e a linha especial ser sempre a ltima. A propsito, no estamos fa-zendo quaisquer restries sobre os valores relativos de |M| e |N| e no estamospresumindo qualquer relao de ordem em M ou N.

26


36/215

Feofiloff cap. 3 Introduo ao Simplex 27

Nosso estudo comea com uma descrio das caractersticas da matriz que oSimplex calcula. Diremos que uma matriz E simples com relao ao par n, m matriz

simplesde ndices se for de um dos trs tipos definidos abaixo: simples solvel, simplesinvivel ou simples ilimitada. No vamos nos preocupar, por enquanto, com asconotaes das palavras solvel, invivel e ilimitada; elas sero justifica-das no captulo 7. As definies podero parecer indigestas, mas devero ficarmais naturais depois que fizermos um esboo do Simplex.

Matriz simples solvel. Dada uma matriz E sobre M N e elementos ne m de N e M respectivamente, diremos que E simples solvel com relaoao par n, m se existem partes P de M m e Q de N n tais que

E[P, Q] de bijeo , E[P, n] o ,

E[MmP, N] = O ,

E[m, NnQ] o , E[m, Q] = o .

A expresso M m P uma abreviatura de (M {m}) P; analogamente, M m PNnQ uma abreviatura de (N{n})Q. bvioqueamatriz E[Mm, Nn] N n Q escalonada. O conjunto P a base de linhas e o conjunto Q uma base de basescolunas da matriz. fcil verificar que a base de linhas nica, mas podemexistir vrias bases de colunas.

H uma certa simetria entre E[m, Nn] e E[Mm, n] na definio de matrizsimples solvel: a condio E[P, n] o corresponde condio E[m, Q] = o; e acondio E[MmP, n] = o corresponde condio E[m, NnQ] o.

Matriz simples invivel. Uma matriz E sobre M N simples invivelcom relao coluna n e linha m se existe h em M m tal que linha de

inviabilidadeE[h, Nn] o e E[h, n] > 0 ou

E[h, Nn] o e E[h, n] < 0 .

O elemento h de M m o ndice de uma linha de inviabilidade.

Matriz simples ilimitada. Uma matriz Esobre MN simples ilimitadacom relao coluna n e linha m se existe uma parte P de M m, uma parte Qde N n e um elemento k de N n Q tais que coluna de

ilimitaoE[P, k] o , E[P, Q] de bijeo , E[P, n] o ,

E[MmP, k] = o , E[MmP, Q] = O , E[MmP, n] = o ,

E[m, k] < 0 , E[m, Q] = o .

Os conjuntos P e Q so as bases da matriz e k o ndice de uma coluna deilimitao.

H uma certa simetria entre a definio de matriz simples invivel e a dematriz simples ilimitada: a condio E[h, Nn] o e E[h, n] > 0 ou E[h, Nn] o e E[h, n] < 0 da primeira corresponde condio E[Mm, k] o e E[m, k] h

m

Figura 3.2: Matriz simples invivel.

k Q n

0 0 1 P 0 1 0

1 0 0

0 0 0 0 00 0 0 0 00 0 0 0 0

m < 0 0 0

Figura 3.3: Matriz simples ilimitada.

Matriz simples. Uma matriz E simples com relao aos ndices n e m sefor de um dos trs tipos descritos acima. As trs definies so mutuamente ex-clusivas: uma matriz no pode ser, ao mesmo tempo, simples solvel e invivel,

nem simples solvel e ilimitada, nem simples invivel e ilimitada.

3.2 Esboo do Simplex

Suponha dada uma matriz D sobre M N e elementos n e m de N e M res- Dpectivamente. O objetivo do Simplex transformar D, por meio de sucessivas


38/215


1 99 0 0 99 0 0 99 880 99 0 0 99 0 1 99 88

0 0 0 0 0 0 0 0 00 1/2 0 0 1/2 1 0 1/2 00 99 1 1 99 0 0 99 880 77 0 0 77 0 0 77 66

Figura 3.4: Esta matriz simples solvel com re-lao coluna 9 e linha 6. A base de linhas com-posta de 1, 2, 4, 5. H duas bases de colunas: umacontm 1, 3, 6, 7 e outra contm 1, 4, 6, 7.

1 99 0 99 99 0 0 99 880 99 0 99 99 0 99 99 880 0 0 99 0 0 0 0 00 1/2 0 1/2 1/2 1 0 1/2 00 0 0 0 0 0 0 0 1

99 99 0 99 99 0 0 99 66

Figura 3.5: Matriz simples invivel (coluna espe-cial 9 e linha especial 6). H duas linhas de inviabi-

lidade: 2 e 5.

1 99 0 0 99 0 0 99 880 99 0 99 99 0 1 99 880 0 0 0 0 0 0 0 00 1/2 0 1/2 1/2 1 0 1/2 00 99 1 99 99 0 0 99 880 77 0 77 77 0 0 77 66

Figura 3.6: Matriz simples ilimitada. A coluna deilimitao 4.


39/215


operaes de pivotao, numa matriz que seja simples em relao a n e m.Cada iterao do Simplex comea com uma matriz E e uma parte P de E

PM m tais que

f[P] o ,

E[P, Q] uma matriz de bijeo e E[MP, Q] = O ,

onde f denota o vetor E[ , n] e Q uma parte de Nn. As operaes executadas fQdurante uma iterao modificam Ee P de modo a preservar essas propriedades.

A primeira iterao comea com E = D e P = . Cada iterao consiste noseguinte:

CASO 1: E[h, k] > 0 ef[h] 0 ou E[h, k] < 0 ef[h] 0para algum h em M m P e algum k em N n . h

kSeja P o conjunto de todos os p em P para os quais E[p,k] > 0.P

CAS O 1A: f[h]/E[h, k] f[p]/E[p,k] para todop em P .Seja E o resultado da pivotao de E em torno de h, k.Comece nova iterao com P + h e E nos papis de P e E.

CAS O 1B: f[h]/E[h, k] > f[p]/E[p,k] para algum p em P .Escolha p em P de modo que f[p]/E[p,k] seja mnimo. pSeja E o resultado da pivotao de E em torno de p, k.Comece nova iterao com E no papel de E (sem alterar P).

CASO 2: E[h, Nn] o ef[h] > 0 ou E[h, Nn] o ef[h] < 0para algum h em M m P . hDevolva E e pare (a matriz E simples invivel).

CASO 3: E[MmP, N] = O, f[MmP] = o e E[m, k] < 0paraalgum k em N n . kSeja P o conjunto de todos os p em P para os quais E[p,k] > 0. P

CAS O 3A: P vazio .Devolva E e pare (a matriz E simples ilimitada).

CAS O 3B: P no vazio.Escolha p em P de modo que f[p]/E[p,k] seja mnimo. pSeja E o resultado da pivotao de E em torno de p, k.Comece nova iterao com E no papel de E (sem alterar P).

CASO 4: E[MmP, N] = O, f[MmP] = o e E[m, Nn] o .

Devolva E e pare (a matriz E simples solvel). P

A operao de pivotao a que se referem os casos 1A, 1B e 3B definidacomo no algoritmo de Gauss-Jordan (seo 2.3): dados elementos h de M me k de N n (as pivotaes jamais ocorrem na linha m e jamais na coluna n),o resultado da pivotao de E em torno de h, k a matriz E definida pelas pivotao


40/215


equaes

E [h, ] =1

E[h, k]E[h, ] e E [i, ] = E[i, ]

E[i, k]

E[h, k]E[h, ]

para cada i em M h. claro que os casos 1A e 1B devem ser entendidos como subcasos do caso 1;analogamente, 3A e 3B so subcasos de 3. Os casos 1B e 3B so formalmenteidnticos. A definio de p nesses casos deve ser entendida da seguinte maneira:escolha qualquer p em P que satisfaa a condio f[p]/E[p,k] f[i]/E[i, k] paratodo i em P .

Q n

0 0 1 P 0 1 0

1 0 0

0 0 00 0 00 0 0

m 0 0 0

Figura 3.7: Matriz E no incio de uma iterao.

A estrutura de casos. Em cada iterao, pelo menos um dos quatro casos seaplica, como passamos a mostrar. Se os casos 1 e 2 no valem para um elementoh de M m P ento

E[h, Nn] = o e f[h] = 0 .

Por outro lado, se essa condio verdadeira para todo h em M m P ento bvio que vale o caso 3 ou o caso 4.

Como se v, os quatro casos se complementam naturalmente. Essa comple-mentaridade determina a lgica interna do Simplex e justifica nossas defini-es de matriz simples solvel, invivel e ilimitada.

Nossa linguagem algortmica. Em nossa linguagem de descrio de algo-ritmos, a ordem em que os casos so enunciados irrelevante: em cada iterao,

qualquer dos casos aplicveis pode ser executado. O mesmo vale para os sub-casos dentro de cada caso. Ademais, a definio de um caso no supe que osdemais no se aplicam. possvel mesmo que os casos no sejam mutuamenteexclusivos (embora isso no ocorra no esboo do Simplex acima).

A propsito, as expresses lgicas da forma X e Y ou W e Z que aparecemna definio de alguns casos devem ser entendidas como ( X e Y) ou (W e Z).


41/215


1 1 5 1 50 1 1 1 40 1 3 1 80 1 1 2 3

1 0 6 2 10 1 1 1 40 0 4 0 40 0 0 3 7

1/6 0 1 1/3 1/61/6 1 0 2/3 25/62/3 0 0 4/3 10/3

0 0 0 3 7

0 0 1 0 11/2 1 0 0 5/2

1/2 0 0 1 5/23/2 0 0 0 1/2

Figura 3.8: Exemplo de aplicao do Simplex. A figura registra a matriz Eno incio de sucessivas iteraes. Neste exemplo, a primeira iterao comeacom P = {1} e Q = {1}. O subcaso 1A se aplica com h, k = 2, 2. Na segundaiterao, o caso 1 se aplica com h, k = 3, 3; o subcaso 1A no se aplica, mas osubcaso 1B vale com p = 1 . No incio da terceira iterao, a matriz Eno maissimples que no incio da iterao anterior, mas em algum sentido melhor queaquela: depois de uma pivotao em torno de 3, 4 obtemos uma matriz simplessolvel.

Terminologia tradicional. Convm mencionar alguns termos consagrados entrana basesai da

base

pelo uso em discusses sobre o Simplex. Nos casos 1 e 3, dizemos que a colunak entra na base. Nos casos 1B e 3B, dizemos que sai da base a coluna q definidapela relao E[p,q] = 1.

Qual o critrio para a escolha da coluna k que dever entrar na base? Nocaso 1, basta que E[h, k] no seja nulo e f[h]/E[h, k] no seja negativo; no caso 3,basta que E[m, k] seja negativo.1 Qual o critrio para a escolha da coluna q quedever sair da base nos casos 1B e 3B? Como a matriz E[P, Q] estabelece umabijeo entre P e Q, o critrio de escolha de q se confunde com o critrio deescolha de p e p escolhido em P de modo que f[p]/E[p,k] seja mnimo.

A propsito, o esboo que fizemos acima corresponde, essencialmente, chamada verso tabular do Simplex.

1 Dizer que negativo o mesmo que dizer < 0. Analogamente, positivose > 0.


42/215


2 2 4 0 242 0 5 1 10

1 1 2 1 2

1 1 1 1 0

1 1 2 0 120 2 1 1 340 2 0 1 140 0 1 1 12

1 1 2 0 120 2 1 1 340 0 1 0 200 2 0 0 46

Figura 3.9: Exemplo de aplicao do Simplex. A fi-gura registra a matriz E no incio de sucessivas itera-es. A matriz resultante simples invivel.

2 2 4 0 242 0 5 1 10

1 1 2 1 21 1 1 1 0

1 1 2 0 120 2 1 1 140 2 0 1 140 0 1 1 12

1 0 5/2 1/2 50 1 1/2 1/2 70 0 1 0 00 0 1 1 12

1 0 0 1/2 50 1 0 1/2 70 0 1 0 0

0 0 0 1 12

2 2 4 8 242 0 5 4 10

1 1 2 0 21 1 1 8 0

1 1 2 4 120 2 1 4 140 2 0 4 140 0 1 4 12

1 0 5/2 2 50 1 1/2 2 70 0 1 0 00 0 1 4 12

1 0 0 2 50 1 0 2 70 0 1 0 0

0 0 0 4 12

Figura 3.10: Mais dois exemplos de aplicao do Simplex, ligeiramentediferentes do anterior. No primeiro ( esquerda), a ltima matriz simplessolvel. No segundo, a ltima matriz simples ilimitada.


43/215


3.3 Anlise

Como j anunciamos acima, o Simplex gira em torno de duas propriedades(compare com a seo 2.4:

Invariantes No incio de cada iterao,

(i0) f[P] o ,(i1) E[P, Q] de bijeo e E[MP, Q] = O ,

ondeQ uma parte deN.

Os dois invariantes so trivialmente verdadeiros (com P e Q vazios) no in-cio da primeira iterao. Suponha agora que eles valem no incio de uma ite-rao qualquer que no a ltima. claro que nessa iterao ocorre o caso 1 ouo caso 3 e k est necessariamente em N Q. preciso mostrar que no fim do

caso 1A os invariantes permanecem vlidos com E , P + h e Q + k nos papisde E, P e Q e que no fim dos casos 1B e 3B os invariantes permanecem vlidoscom E e Q q + k nos papis de E e Q, onde q o nico elemento de Q tal queE[p,q] = 1 . Trocando em midos, basta mostrar que no fim do caso 1 A temos

f[P+h] o , (3.a)

E[ , Q] = E[ , Q] , (3.b)

E[ , k] = I[ , h] , (3.c)

e que no fim dos casos 1B e 3B temos

f

[P] o , (3.d)E[ , Qq] = E[ , Qq] , (3.e)

E[ , k] = I[ , p] , (3.f)

onde f = E [ , n] e I a matriz identidade. As demonstraes de (3.a) e (3.d)explicam a estrutura de casos do Simplex e a elaborada escolha de p nos casos 1Be 3B.

DEMONSTRAO DE (3.a): Considere inicialmente o componente h de f .Em virtude da definio do caso 1,

f[h]/E[h, k] 0 .

Como a pivotao no caso 1A ocorre em torno de h, k temos f [h] = f[h]/E[h, k]e portanto f [h] 0. Resta considerar f [i] com i em P. Suponha inicialmenteque E[i, k] no positivo. Ento f [i] 0 pois

f [i] = f[i] E[i, k]f[h]

E[h, k]


44/215


Q k n

0 0 1 0 P 0 1 0 0

1 0 0 0

0 0 0 1 h0 0 0 00 0 0 0

m 0 0 0 0

Figura 3.11: Matriz E no fim do caso 1A.

e f[i] 0 em virtude de (i0). Suponha agora que E[i, k] positivo. Ento f [i] 0 porque

f [i] = E[i, k] (f[i]

E[i, k]

f[h]

E[h, k])

e a expresso entre parnteses no negativa, em virtude da definio docaso 1A. Em suma, f [i] 0 para cada i em P + h . P

DEMONSTRAO DE (3.d): Como a pivotao nos casos 1B e 3B ocorre emtorno de p, k, temos f [p] = f[p]/E[p,k] . Mas f[p] 0 em virtude de (i0) eE[p,k] > 0 pois p P . Logo,

f [p] 0 .

Resta considerar f [i] com i em P p. Suponha inicialmente que E[i, k] no positivo. Ento f [i] 0 pois

f [i] = f[i] E[i, k] f[p]E[p,k]

e f[i] 0. Suponha agora que E[i, k] positivo. Ento f [i] 0 porque

f [i] = E[i, k] (f[i]

E[i, k]

f[p]

E[p,k])

e a expresso entre parnteses no negativa em virtude da maneira como p foiescolhido. P

As demonstraes de (3.b), (3.c), (3.e) e (3.f) so anlogas s demonstraesdas relaes correspondentes no algoritmo de Gauss-Jordan. A ttulo de ilustra-

o, vamos examinar as duas ltimas.

DEMONSTRAO DE (3.e): Como E[p,Qq] = 0 em virtude de (i1), a defini-o da operao de pivotao garante que

E [p,Qq] = E[p,Qq] e E [i, Qq] = E[i, Qq]

para cada i em M p . P


45/215


q k n

0 1 0 P 1 0 0

0 0 1 p

0 0 00 0 00 0 0

m 0 0 0

Figura 3.12: Matriz E no fim dos casos 1B e 3B.

DEMONSTRAO DE (3.f): Convm representar a operao de pivotao deforma matricial, como j fizemos ao analisar o algoritmo de Gauss-Jordan.

Seja F a matriz elementar sobre M M cuja coluna saliente, p, igual a F

E[ , k] . Seja G a inversa de F, isto , a matriz elementar com coluna saliente p Gdefinida pelas equaes G[p,p] = 1/E[p,k] e G[i, p] = E[i, k]/E[p,k] para cada iem M p. Observe que

FG = G F = I e E = G E .

Agora, para cada i em M,

E [i, k] = G[i, ]E[ , k] = G[i, ]F[ , p] = (GF)[i, p] = I[i, p] .

Logo, E [ , k] = I[ , p] . P

Como acabamos de mostrar, os invariantes (i0) e (i1) valem no incio de cadaiterao. Em particular, os invariantes valem no incio da ltima iterao. Por-tanto, a matriz E que o Simplex devolve simples com relao ao par n, m: nocaso 2, E simples invivel (com linha de inviabilidade h); no caso 3A, E sim-ples ilimitada (com coluna de ilimitao k); no caso 4, E simples solvel (combases P e Q).

3.4 Convergncia

Nosso esboo do Simplex freqentemente no converge, ou seja, freqente-mente no atinge um dos casos terminais (2, 3A ou 4). Enquanto estiver ocor-rendo o caso 1A, bvio que estamos fazendo progresso, pois P aumenta. Mas possvel que haja uma seqncia infinita de ocorrncias dos casos 1B ou 3B. Istoacontece, em especial, se o caso 1 ocorre em duas iteraes consecutivas com ummesmo valor de P e valores distintos de h, como mostra a figura 3.13.

A convergncia melhora se insistirmos na mesma linha h, iterao aps ite-rao, enquanto P no se alterar. A justificativa para esta poltica est na se-guinte observao, a ser demonstrada no prximo captulo: enquanto estiver


46/215


1 2 10 20 1 12 20 6 13 30 0 0 0

1/2 1 5 11/2 0 7 1

3 0 43 90 0 0 0

1 2 10 20 1 12 20 6 13 30 0 0 0

Figura 3.13: Exemplo de no-convergncia do esboo do Simplex naseo 3.2. A figura registra o valor de E no incio de trs iteraes con-secutivas. Em todas, 1 o nico elemento de P. Na primeira iterao,

o caso 1 se aplica com h, k = 2, 2 e o subcaso 1B se aplica com p = 1.Na segunda iterao, o caso 1 se aplica com h, k = 3, 1 e o subcaso 1Bse aplica com p = 1. No incio da terceira iterao temos exatamentea mesma configurao que no incio da primeira. Este ciclo poder serepetir ad ternum.

acontecendo o caso 1 com um mesmo valor de P e um mesmo valor de h, o va-lor absoluto de f[h] diminui ou, na pior das hipteses, no aumenta. Em outraspalavras, numa seqncia de ocorrncias do caso 1B, a seqncia de valores def[h] monotnica, isto , crescente ou decrescente.2

Exerccios

3.1 Escreva um algoritmo que decida se uma dada matriz E simples comrelao a um dado par n, m de ndices.

3.2 Considere o esboo do Simplex feito na seo 3.2. Qual dos casos se aplicanuma iterao que comea com P = M m?

3.3 Escreva uma verso especializada do Simplex para matrizes com uma slinha. Escreva uma verso especializada do Simplex para matrizes comapenas duas linhas. Use as duas matrizes abaixo como teste, com n = 6 em = 2. (Veja tambm o exerccio 4.3.)

2 2 2 2 2 02 1 0 1 2 0

2 2 2 2 2 0

2 1 0 1 2 0

2 Diremos que uma seqncia 1, 2, 3, . . . crescentese 1 2 3 e decrescentese 1 2 3 .


47/215


3.4 Aplique o Simplex descrito na seo 3.2 matriz abaixo (como de hbito,a coluna especial a que est mais direita e a linha especial a ltima).Aplique o Simplex vrias vezes, procurando obter solues diferentes.

1 2 1 0 1 0 0 12

2 5 0 1 0 1 0 101 3 1 1 0 0 1 21 2 1 0 0 1 0 0

3.5 Suponha que no incio de uma iterao do Simplex aplica-se o caso 3 e k escolhido, por engano, de modo que E[m, k] 0. Suponha que a iterao executada com este valor de k . Como isso afeta a iterao corrente? Comoisso afeta o andamento das iteraes subseqentes?


48/215

Captulo 4

Heurstica Simplex

Que a heurstica apresente a sua verso dos fatos!

Este captulo faz uma descrio completa da heurstica Simplex. Esta versodo Simplex no merece o rtulo algoritmo pois nem sempre converge.1 Masos exemplos de no-convergncia so muito mais raros que os do esboo quefizemos no captulo anterior (seo 3.2). O prximo captulo mostrar comorefinar a heurstica para transform-la num algoritmo.

4.1 Introduo

A heurstica Simplex recebe uma matriz D, o ndice n de uma coluna e o ndicem de uma linha e calcula uma matriz E que simples com relao ao par n,m.

Para dizer o que, exatamente, o Simplex faz preciso especificar a relao entreas matrizes E e D. Essa relao um pouco mais restritiva que a do algoritmode Gauss-Jordan (captulo 2): existem matrizes F e G tais que

E = GD , G[ , m] = I[ , m] e F G = I ,

onde I a matriz identidade. A verso da heurstica que descreveremos a seguirdevolve F e G. De posse dessas matrizes, basta calcular os produtos F G e GD everificar se, de fato, o primeiro igual matriz identidade e o segundo simplescom relao a n,m.

Como E = GD, cada linha de E uma combinao linear das linhas de D.

Como G[ , m] = I[ , m] , cada linha de E[Mm, ] uma combinao linear daslinhas de D [Mm, ] e o vetor E[m, ] a soma de D[m, ] com uma combinaolinear das linhas de D[Mm, ] .

1 Uma heurstica um procedimento de tentativa-e-erro. No presente texto, o termo usadopara designar um procedimento computacional que (ao contrrio de um algoritmo) nem sempreconverge, mas produz os resultados desejados quando converge. Um procedimento computaci-onal convergese sua execuo termina depois de um nmero finito de iteraes, quaisquer quesejam os dados.

39


49/215


50/215


51/215

Feofiloff cap. 4 Heurstica Simplex 42

1 0 0 0 1 0 0 0 2 2 4 0 240 1 0 0 0 1 0 0 2 0 5 1 100 0 1 0 0 0 1 0 1 1 2 1 20 0 0 1 0 0 0 1 1 1 1 1 0

2 0 0 0 1/2 0 0 0 1 1 2 0 12 L2 1 0 0 1 1 0 0 0 2 1 1 14

1 0 1 0 1/2 0 1 0 0 2 0 1 141 0 0 1 1/2 0 0 1 0 0 1 1 12

2 2 0 0 0 1/2 0 0 1 0 5/2 1/2 5 L2 0 0 0 1/2 1/2 0 0 0 1 1/2 1/2 7 L

1 1 1 0 1/2 1 1 0 0 0 1 0 01 1 0 1 1/2 0 0 1 0 0 1 1 12

2 2 4 0 5/4 2 5/2 0 1 0 0 1/2 5 L2 0 5 0 1/4 0 1/2 0 0 1 0 1/2 7 L

1 1 2 0 1/2 1 1 0 0 0 1 0 0 L1 1 1 1 1 1 1 1 0 0 0 1 12

Figura 4.2: Exemplo de aplicao do Simplex. A figura registra os valores deF, G e E no incio de cada iterao. O rtulo L indica as linhas que estoem L. A ltima matriz E simples solvel com relao coluna 5 e linha 4.

3 2 1 4 5 6 7 8 104 3 2 5 6 7 8 9 115 6 3 4 7 9 8 10 91 5 4 7 5 10 9 6 89 8 7 11 3 2 1 4 0

157/7473 334/7473 277/7473 170/7473 0466/7473 389/7473 13/7473 19/7473 0545/2491 332/2491 514/2491 368/2491 0

1343/7473 1522/7473 1486/7473 1597/7473 07690/7473 12866/7473 12326/7473 13991/7473 1

84/2491 168/2491 686/7473 0 0 1 1773/2491 0 1391/747368/2491 136/2491 275/7473 0 0 0 2147/2491 1 416/7473

2509/2491 5018/2491 49/2491 0 1 0 7271/2491 0 3480/24911258/2491 5007/2491 3631/7473 1 0 0 6364/2491 0 2714/7473

28834/2491 60159/2491 15283/7473 0 0 0 45640/2491 0 65620/7473

Figura 4.3: Exemplo de aplicao do Simplex. Ao receber a matriz D (topoda figura) e os ndices 9 (coluna) e 5 (linha) o Simplex executou 10 iteraes edevolveu a matriz G (meio da figura). A matriz GD (parte inferior da figura) simples solvel com relao coluna 9 e linha 5.


52/215


Fases. Qualquer execuo da heurstica consiste em uma seqncia de fasesocorrncias da alternativa I seguida de uma seqncia de ocorrncias da alter-nativa II. Enquanto estiver acontecendo a alternativa I, dizemos que a heurs-tica est na primeira fase; enquanto estiver acontecendo a alternativa II, dize-mos que a heurstica est na segunda fase. A propsito, a alternativa II ocorrequando e somente quando L = M m.

4.3 Anlise

Para entender como e por que a heurstica Simplex funciona, basta verificar asseguintes propriedades (compare com as sees 3.3, 2.4 e 2.5):

Invariantes No incio de cada iterao da heurstica, existe uma parteP deL e uma parteQ deN n tais que Q

(i0) f[P] o,(i1) E[P, Q] de bijeo, E[MP, Q] = O e E[LP, ] = O ,(i2) F G = I,(i3) G D = E,(i4) G[ , MP] = I[ , MP] ,

ondef o vetorE[ , n] .

P m Q n

0 0 0 0 0 0 1 0 0 0 0 P 0 1 0 0 0 0 0 1 0 0 L1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 0 0 0 0 00 0 1 0 0 0 00 0 0 1 m 0 0 0

Figura 4.4: Matrizes G e E no incio de uma iterao da heurstica Simplex.

evidente que esses invariantes valem (com P e Q vazios) no incio daprimeira iterao. Suponha agora que os invariantes valem no incio de umaiterao qualquer que no a ltima. claro que nessa iterao ocorre o caso I.1A,o caso I.1B, o caso I.3 ou o caso II.1B. bvio que depois de uma ocorrncia docaso I.3 os invariantes permanecem vlidos; para tratar dos demais casos, adotea notao

f = E [ , n] e P = P + h .


53/215


Seja q o nico elemento de Q tal que E[p,q] = 1. Basta mostrar agora que nofim do caso I.1A

f[P] o , (4.a)

E

[ , Q]= E

[ , Q]e E

[ , k]= I

[ , h], (4.b)

E[LP, ] = E[LP, ] , (4.c)

G[ , MP] = G[ , MP] , (4.d)

que no fim dos casos I.1B e II.1B

f[P] o , (4.e)

E[ , Qq] = E[ , Qq] e E[ , k] = I[ , q] , (4.f)

E[LP, ] = E[LP, ] , (4.g)

G[ , MP] = G[ , MP] , (4.h)

e que no fim de quaisquer dos casosF G = I e G D = E . (4.i)

As propriedades (4.c) e (4.g) so triviais. As propriedades (4.a), (4.b), (4.e) e (4.f)j foram demonstradas na seo 3.3. As demonstraes das demais proprieda-des so anlogas s que fizemos ao discutir o algoritmo de Gauss-Jordan.

Os invariantes valem, em particular, no incio da ltima iterao. Portanto,na ltima iterao, a matriz E simples invivel (caso I.2) ou simples ilimitada(caso II.1A) ou simples solvel (caso II.2) com relao ao par n, m. Em qualquerdesses casos, G[ , m] = I[ , m] em virtude de (i4). Alm disso, F G = I em vir-tude de (i2). Assim, ao devolver F e G, a heurstica est se comportando comoprometeu.

4.4 Mais trs invariantes

Os trs invariantes que examinaremos a seguir (compare com a seo 2.5) pa-recem irrelevantes no presente captulo, mas sero importantes para a anlisedo mecanismo de convergncia que introduziremos no prximo captulo (se-o 5.5).

Invariantes No incio de cada iterao da heurstica,

(i5) F[ , MP] = I[ , MP] e F[ , P] = D [ , Q] J,(i6) D[MP, Q] = G[MP, P] D[P, Q] ,(i7) D[P, Q] J G [P, P] = I,

onde J a transposta da matriz de bijeoE[P, Q] . J


54/215


A demonstrao dessas propriedades anloga dos invariantes correspon-dentes do algoritmo de Gauss-Jordan.

O invariante (i5) descreve completamente a matriz F. Em particular, mos-tra que no preciso atualizar F a cada iterao: a matriz pode ser calculada

imediatamente antes do fim da execuo da heurstica. claro que para isso preciso dispor das variveis P e Q.O invariante (i6) mostra que, para cada i em M P, o vetor D[i, Q] uma

combinao linear das linhas da matriz D [P, Q] . O invariante (i7) mostra queJ G [P, P] uma inversa direita de D [P, Q] . A propsito, os invariantes (i3) e (i4)mostram que J G [P, P] uma inversa esquerda de D [P, Q] .

Documents

book-public