Algoritmos de Programacao Linear-libre

5/28/2018 Algoritmos de Programacao Linear-libre

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 deprogramao linear1 consiste no seguinte: dada uma matrizAe vetores be 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, bec) 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 implementaesaproximadasdo 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 termoprogramaosignificaplanejamento. 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 precisoo quecada algoritmo faz e no apenascomofaz 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 nmerosracionais. 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 usaaritmticainteira. 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 degraduaoeps-graduao em Cin-cia da ComputaonoInstituto de Matemtica e EstatsticadaUniversidade deSo Paulo. O subttulo do livro Programao Linear Concreta uma alusoaoConcrete 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 ageneration 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/dcc/grad/http://www.ime.usp.br/dcc/posgrad/http://www.ime.usp.br/dcc/posgrad/http://www.ime.usp.br/http://www.usp.br/http://www.usp.br/http://www.ime.usp.br/~cris/gcomb/tem-fapesp/index.htmlhttp://www.ime.usp.br/~cris/gcomb/tem-fapesp/index.htmlhttp://www.ime.usp.br/~yoshi/pronex/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 teiaWWW.

So Paulo, 19992005

P. F.
http://www.ime.usp.br/~pf/prog-lin/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 122 Algoritmo de Gauss-Jordan 13

2.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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 747.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 CDao PV . . . . . . . . . . . . . . . . . . . . . . . . . 13514.3 Reduo do PVao V . . . . . . . . . . . . . . . . . . . . . . . . . . 13614.4 Reduo do Vao 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 deb 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 exerccio2.5 . . . . . . . . . . . . . . . . . . . . . . . . 192E.2 Soluo do exerccio2.11 . . . . . . . . . . . . . . . . . . . . . . . . 192E.3 Soluo do exerccio2.13 . . . . . . . . . . . . . . . . . . . . . . . . 194E.4 Soluo do exerccio4.2 . . . . . . . . . . . . . . . . . . . . . . . . 196E.5 Soluo do exerccio4.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

Umvetor 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 quex est definidosobreN.

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

x[Q]

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

Um vetorxsobreNnulosex [n] = 0para todonem N. O vetor nulo ser vetor nuloodenotado poro , qualquer que seja o seu conjunto de ndices.Sex 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 dex .

Sex e y so vetores sobre um mesmo conjunto de ndices e x [n] y [n]paracadan , dizemos quex y . Analogamente, dizemos que x y

1


11/215

Feofiloff cap. 1 Vetores e Matrizes 2

x > y

sex [n] > y [n]para todon . 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 ,3e 4de cima para baixo.

1.2 Matrizes

Umamatriz 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 queM o conjunto den-dices de linhaseN o conjunto dendices de colunasdeA . Dizemos tambmqueA uma matriz definidasobreM N.

Se me nso elementos de M e Nrespectivamente ento A[m, n] denota o A[m, n]componente m, nde A , ou seja, o valor de A em m, n. Se P e Qso partes deMeNrespectivamente ento

A[P, Q]

a restrio deAaP Q. Usaremos a abreviaturaA[P, ](leia A Ptudo) para A[P, ]

A[P, N]e a abreviaturaA [, Q]paraA [M, Q] . Sem um elemento deMento A[, Q]

A[m, Q]

ovetorsobre Qcujo componente q A[m, q] para todo qem Q. Usaremos aabreviaturaA [m, ]paraA [m, N]e diremos que esse vetor a linham de A . A[m, ]

linhaAnalogamente, para qualquer parte PdeMe qualquer elementonde N, aexpressoA [P, n]denota o vetor cujo componente p A [p, n]para cadap 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 colunasso1, 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 matrizA[, Q] , ondeQ o conjunto compostopelos ndicesb, d,e.

Usaremos a abreviatura A [, n]paraA[M, n]e diremos que este vetor acoluna A[, n]colunande 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 nulase A [m, n] = 0para todo par m, n. A matriz nula ser matriz nulaOdenotada porO , quaisquer que sejam os seus conjuntos de ndices.Se A uma matriz e um nmero ento A a matriz que se obtm A

quando cada componente de A multiplicado por . Analogamente, A/ o A/vetor que se obtm dividindo por cada componente deA .


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 mesmoconjuntoN, oprodutodex por y o nmero

nN

x[n]y [n] ,

que denotaremos por x y . bvio que x y = y x. Ademais, para qualquer x yparteQ 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 quea,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 modelonentox y o lucro total.

Produtos matriz-por-vetor e vetor-por-matriz. Para qualquer matrizAso- produtomatriz porvetor

breM Ne qualquer vetor xsobre N, oproduto de Apor x o vetor A x

A xdefinido pela expresso

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

para cadam em M. claro queA x um vetor sobre M. Analogamente, para produto vepor matrizqualquer vetor ysobre M, oproduto de y porA o vetor y Adefinido pelay Aexpresso

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

para cadanemN. fcil verificar que, para qualquer parte PdeMe qualquer

parteQ 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 Me qual-quer matrizB sobreM N, oproduto deAporB a matriz A BsobreL N A Bdefinida pela expresso

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

para cadal em Le cadanem N. fcil verificar que, para qualquer parte PdeLe qualquer parteQ de N,

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

menos fcil verificar a propriedade associativa propriedadassociativa

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

vlida para quaisquer matrizes A, Be Ccujos 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 xe y , desde que cada um dosprodutos faa sentido.

Notao. Vamos apelar, muitas vezes, ao princpio universal da preguia xye escreverxy ,Ax,yA eABno lugar dex y ,A x,y AeA Brespectivamente. Ax yA

ABO operador de indexao [, ] tem precedncia sobre o operador de multi-plicao. Assim, expresses da formaBA[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 produtosBAe yAfazem 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 matrizAe um vetor b ,

encontrar um vetorx tal queAx = b .

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

problemas levam naturalmente aos seguintes conceitos.Uma matrizIsobre M N aidentidadese M = Ne, para cada par i, j identidade

de elementos deM,

I[i, j] = sei = j ento1 seno0 .

Toda matriz identidade ser denotada porI, 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.

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

A inversa direita de uma matrizA uma matrizDtal queAD = I. Uma matriz inversadireitaAinversvel pela direitase possui uma inversa direita.

Se uma matriz tem uma inversa esquerda e uma inversa direita ento asduas inversas so iguais. De fato, seAD = Ie EA= Iento

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

Ademais, as inversas so nicas. De fato, para qualquer matrizD tal queAD =Item-se D = (EA)D = E(AD) = E = D . Analogamente, para qualquer E

tal queEA= Item-seE =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

Atem uma inversa esquerda e direitaE, ento o vetorx= Ebsatisfaz 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 matrizAsobreMN a matrizAdefinida 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 deA 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 matrizB 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 JsobreM Nde bijeo1 se existe uma funo bijetora de Mem matriz

de bijeoNtal queJ[m, n] = se(m) =nento1seno0 .

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 um1 . bvio que |M| = |N| se existe uma matriz de bijeo sobre M N.

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

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

ponentei, jde J

J o produto de duas linhas de J:

(JJ)[i, j] = J[i, ] J[, j] = J[i, ]J[j, ] .ComoJ matriz de bijeo, J[i, ]J[j, ] igual a1ou0conformei = j ou i =j .Isso mostra queJJ=I. O mesmo raciocnio, comJno papel deJ, mostra queJ J=I.

1 Generaliza o conceito de matriz de permutao; umamatriz 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 queJ uma matriz de bijeo sobreM N. Digamos queJ[m, n] = 1para algumm em Me algum n em N. Ento, para qualquer matrizAcujo conjunto de ndices de linhas seja N, a linham de J A idntica linhan

deA

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

Analogamente, para qualquer matrizB que tenha colunas indexadas por M, acolunande BJ idntica coluna m de B . Em suma, a pr-multiplicao deApor Japenas redefine os nomes das linhas de A , e a ps-multiplicao de BporJapenas 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 Dsobre M N diagonalse M = N e D [m, n] = 0sempre que diagonalm =n . Em particular, toda matriz identidade diagonal.

SeD uma matriz diagonal tal queD [m, m]= 0para todomento a matriz

diagonalEdefinida pelas equaes

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

uma inversa esquerda e tambm uma inversa direita de D . Portanto, E anicainversa de D . Por outro lado, seD uma matriz diagonal e D [m, m] = 0para algumm ento fcil verificar queD no tem inversa.

1.8 Matrizes elementares

Umamatriz-colunacoincide com a identidade em todas as colunas, exceto tal- matriz-colunavez uma. Em outras palavras, uma matriz FsobreM M uma matriz-coluna

se existek em Mtal que

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

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

da matriz.


18/215


Fato Para qualquer matriz-colunaFcom coluna salientek, 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 cadamemM k . Portanto, a colunakde GF igual colunak 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 definemG a partir de Ftambm geramFa partir de G .

Nas condies da proposio acima, G a nica inversa (esquerda e direita)deF. Tambm fcil verificar que se F[k, k]= 0 para algumk entoFno 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 matrizFsobre M M umamatriz-linhase existe h em Mtal que matriz-linhaF[Mh, M] = I[Mh, M] . Diremos que h alinha salientede F. Uma obser-

vao anloga que demonstramos acima vale para matrizes-linha: se F umamatriz-linha com linha salientehe F[h, h]= 0ento a matriz-linhaGcom linhasalienteh definida pelas equaes

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


19/215


para cadanemMh a nica inversa esquerda deFe tambm a nica inversadireita deF.

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 lineardesses vetores qualquer vetor da forma

1a1+ +kak ,

onde 1, . . , k so nmeros. Esses nmeros so os coeficientesda combinao

linear.Suponha que A uma matriz sobre M N. Para todo vetor x sobre N, o

vetorAx uma combinao linear das colunas deAcom coeficientesx [j] , isto ,

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

Analogamente, para todo vetor y sobreM, o vetoryA uma combinao lineardas linhas deA , isto ,

yA =

iM y [i]A[i, ] .

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

(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 deBA(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 queAB = Ie BC=I. Mostre queB inversa direita de C.


20/215


1.5 Seja Aa primeira das matrizes abaixo. Encontre uma matriz de bijeo Jtal queAJseja a segunda das matrizes. Encontre uma matriz de bijeo Jtal queJ Aseja 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 SejamFeGmatrizes sobreMMe Duma matriz sobreMN. SuponhaqueF G= Ie que a matrizE=GD de bijeo. Verifique queD EG = I.

1.7 Suponha queA uma matriz de bijeo sobre M Neb um vetor arbi-trrio sobreM. Verifique que existe um e um s vetorx tal queAx = b .


21/215

Parte I

Algoritmos Bsicos

12


22/215

Captulo 2

Algoritmo de Gauss-Jordan

Encontre nmerosx1 ,x2 ,x3e x4que satisfaam as equaes

d11x1+d12x2+d13x3+d14x4 = b1

d21x1+d22x2+d23x3+d24x4 = b2

d31x1+d32x2+d33x3+d34x4 = 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 seo2.1.

Ao estudar qualquer algoritmo, preciso enfrentar duas perguntas: o queo algoritmo faz? comofaz 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 comoo algoritmo

funciona.

2.1 Matrizes escalonadas

Uma matrizEsobreM Nescalonadase existem uma partePdeMe uma matrizescalonadaparteQ de Ntais que

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

Os conjuntosPeQso as bases da matriz; o conjuntoQ a base de colunas eP bases abase 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 MouN.)

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.htmlhttp://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 P

0 1 0 0 01 0 0 0 00 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, 4e base decolunas1, 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 Ne transforma DM NDnuma matriz escalonada. Cada iterao do algoritmo comea com uma parte

PdeMe uma matrizE. A primeira iterao comea comP = eE=D . Cada PEiterao consiste no seguinte:

CASO1: E[MP, ]=O.Escolhahem M Pek em Nde modo que E[h, k]= 0.SejaE 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 cadai em M h.Comece nova iterao com P+he E nos papis dePeE.

CASO2: E[MP, ]=O.DevolvaEe pare.

A expressoP+h uma abreviatura deP {h}. claro que seP =Mnoincio de uma iterao ento aplica-se o caso 2.

No incio de cada iterao existe uma parte Qde Ntal 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 Eno 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 12 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 4

0 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 matrizesG e D e exibeGD . Observe queGD escalonada mas no existe Ftal que F G= I.


25/215


2.3 Algoritmo

Para dizer, exatamente, o queo algoritmo faz preciso especificar a relao entreas matrizes Ee D. A matriz E equivalente matrizD no seguinte sentido:

existe uma matriz inversvelG tal queE = GD .

O esboo da seo anterior no devolve G , o que impede o usurio de conferir aequivalncia entreEe D . A verso do algoritmo que descreveremos abaixo de-volveGe sua inversaF; o usurio pode ento, ao preo de duas multiplicaesde matrizes, verificar que G inversvel e queGD escalonada.

Algoritmo de Gauss-Jordan Recebe uma matrizD sobreM Ne de-volve matrizesF eG sobreM Mtais queF G= IeGD escalonada.

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

no seguinte:

CASO1: E[h, ]=o para algumh em M P . hEscolhak em Ntal queE[h, k]= 0. kSejaF, G, E o resultado da pivotao deF,G, Eem torno deh, k.Comece nova iterao com F ,G ,E eP+hnos papis deF,G ,Ee P.

CASO2: E[MP, ]=O.DevolvaF,Ge pare. 2

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

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

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

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

para cadai 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 Paumenta a cada ocorrncia do caso 1. O nmero total de iteraes , nomximo, |M|.

2 Veja exerccio2.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,Ge Eno 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 deGeEno incio de sucessivas iteraes (Ffoi omitida porfalta de espao). Observe como a matriz identidade que estava inicialmente emGmove-se para a direita, invadindoE.


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 chamarbase de colunasdaiterao).

Q

0 0 1P 0 1 0

1 0 00 0 00 0 00 0 0

Figura 2.8:MatrizEno 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= Iem virtude de (i2). Portanto, ao devol-verFeGo algoritmo estar se comportanto como prometeu.

DEMONSTRAO DOS INVARIANTES: evidente que as propriedades va-lem no incio da primeira iterao (comP e Qvazios). 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:MatrizE 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 iem 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 seo1.8) sobreM Mcuja coluna saliente, h , igual aE[, k] , isto ,

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

Seja Ga 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 cadai em M h. Observe que F

G=

G

F =I. Observe tambm que

F = FF , G = GG e E = GE .

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

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,Eem torno de h, k o terno dematrizesFF, GG, GE.

Agora podemos cuidar das demonstraes de (2.b) a (2.d). A demonstraode (2.b) decorre das igualdades GF =Ie E = GE: para cadai 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.

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,

ondeJ 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 01 0 0 0 0 00 1 0 0 0 0 M P0 0 1 0 0 0

Figura 2.10: Matrizes G e Eno incio de uma iterao do algoritmode Gauss-Jordan. A justaposio de G e Econtm 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 temosG [, MPh] = G [, MPh] ,

ondeM 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 Fem cada iterao. A multiplicao por

Japenas troca os nomes das

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


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

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

DEMONSTRAO: Seja i um elemento de M P. Em virtude de (i4), paracadai 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] .MasF[P, P]G[P, P] = Ipor fora de (i2), (i4) e da primeira parte de (i5).

O invariante (i6) mostra que, para cada iem 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 deD [P, Q] . A propsito, os invariantes (i3) e (i4)mostram queJ G [P, P] uma inversa esquerda deD [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 exerccio2.6,pgina24) de modo que cada pivotao exija apenasmnmultiplicaes e divises e menos que mn adies e subtraes. Como o


31/215


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

2m2n .

(A ttulo de comparao, observe que a multiplicao de Gpor 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 dasmatrizesF,Ge Esero 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 onumeradore o segundo o denominadorda representa- numerador

denominado. 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-ptulo11. 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= IeGD escalonada.

Vale tambm o seguinte adendo: se os componentes deDso nmeros racionaisento existem matrizesracionais FeGcom 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/126691 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 deG . A terceira matriz GD .

2.8 Aplicao: Sistemas de equaes

Considere o seguinte problema: Dada uma matrizA sobreM Ne um vetorb sobre M, encontrar um vetorx tal queAx = b. Para resolver o problema,comece por submeter A ao algoritmo de Gauss-Jordan. O algoritmo devolvermatrizesFeG tais queF G= IeGA escalonada.

Digamos que as bases de GAso PeQe suponha inicialmente que o vetor(Gb)[MP] nulo. Sejax 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 hem M P. claro quenesse caso no existe xtal que(GA)x= Gb . Nosso problema original tambmno tem soluo, como passamos a demonstrar. Seja go 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 comomtodo de eliminaode 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 vetorg constitui, portanto, um certificado facilmente verificvel de quea equaoAx = bno 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 = Ino incio de cada iterao do algoritmo de Gauss-Jordan.

2.3 O algoritmo descrito no texto devolve apenas as matrizesF e G . Escrevauma verso que devolva tambm a matriz escalonada Ee suas bases PeQ .

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

2.5 Escreva o algoritmo de Gauss-Jordan em uma linguagem mais formal,mais prxima de PASCALou C. (Veja soluo parcialE.1no apndiceE.)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 Qe a colunak .

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 seE[h, k]= 0. Qual o efeito de tal pi-votao? A execuo do algoritmo pode ser retomada depois da pivotaoexcepcional?

2.8 Suponha queAeB so matrizes sobreM Me queP uma parte deM.Suponha ainda que AB = Ie A [, MP] = B [, MP] = I[, MP] . Mostre

queA [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 Qos valores das variveis G , P eQ no incio de uma itera-o. Sejam G, P e Qos valores das variveis G , P e Q no incio de outraiterao. Mostre que se P= Pe Q= Qento G[M P , ] = 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 opostoda matrizD . A propsito, diz-se que D temposto

pleno se seu posto igual ao nmero de linhas da matriz. (Soluo noapndiceE, pgina192.)

2.12 Encontre nmerosx1, . . , x4que 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 matrizAsobreM N, um vetorbsobreMe um vetorcsobreN, encontrarxtal queAx= becx mnimo.O problema sempre tem soluo? (Veja apndiceE,pgina192.)


35/215

Captulo 3

Introduo ao Simplex

Encontre nmeros no-negativosx1 ,x2 ,x3e x4que satisfaam as equaes

d11x1+d12x2+d13x3+d14x4 = d15

d21x1+d22x2+d23x3+d24x4 = d25

d31x1+d32x2+d33x3+d34x4 = d35

e minimizem a soma d41x1+d42x2+d43x3+d44x4

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 seo3.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 quefaz 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 captulo7,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 elementon de Ne um n melemento mde M. Diremos quen acoluna especiale que m alinha es- coluna

especial

linhaespecial

pecialda 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 MouN.

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 Esimples com relao ao parn, m matriz

simplesde ndicesse for de um dos trs tipos definidos abaixo: simples solvel, simplesinvivel ou simples ilimitada. No vamos nos preocupar, por enquanto, com as

conotaes das palavras solvel, invivel e ilimitada; elas sero justifica-das no captulo7. As definies podero parecer indigestas, mas devero ficarmais naturais depois que fizermos um esboo do Simplex.

Matriz simples solvel. Dada uma matrizEsobreM Ne elementos ne m de NeMrespectivamente, diremos que Esimples solvelcom relaoao parn, mse existem partes PdeM me Q de N ntais que

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

E[MmP, N]= O ,

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

A expressoM m P uma abreviatura de (M {m}) P; analogamente, M m PNnQ uma abreviatura de(N{n})Q. bvio que a matrizE[Mm, Nn] N n Q escalonada. O conjunto P abase de linhase o conjunto Q umabase de basescolunasda 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] ocorresponde condio E[m, Q] =o ; e acondioE[MmP, n] = o corresponde condio E[m, NnQ] o.

Matriz simples invivel. Uma matrizEsobreM Nsimples invivelcom relao colunane linham se existehem M mtal que linha de

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

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

O elementoh de M m o ndice de umalinha de inviabilidade.

Matriz simples ilimitada. Uma matrizEsobreMN simples ilimitadacom relao colunane linhamse existe uma partePdeM m, uma parteQdeN ne um elemento k de N n Qtais 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 asbasesda 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] oeE[h, n] > 0ouE[h, Nn]oe E[h, n] < 0 da primeira corresponde condio E[Mm, k] oe 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 matrizE simples com relao aos ndicesnemsefor 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 matrizDsobre M Ne elementos ne mde 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 coluna9 e linha6 . A base de linhas com-posta de 1, 2, 4, 5. H duas bases de colunas: umacontm1, 3, 6, 7e outra contm1, 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-cial9e linha especial6). 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 0

0 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 Ee uma parte P de E

PM mtais que

f[P] o ,

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

ondefdenota o vetorE[, n]eQ uma parte deNn. As operaes executadas fQdurante uma iterao modificamEePde modo a preservar essas propriedades.

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

CASO1: E[h, k] > 0 ef[h] 0 ou E[h, k] < 0 ef[h] 0para algum h em M m Pe algumk emN n. h

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

CAS O1A: f[h]/E[h, k] f[p]/E[p, k] para todop em P .SejaE o resultado da pivotao deEem torno deh, k.Comece nova iterao com P+he E nos papis dePeE.

CAS O1B: f[h]/E[h, k] > f[p]/E[p, k] para algump em P .Escolhapem P de modo quef[p]/E[p, k]seja mnimo. pSejaE o resultado da pivotao deEem torno dep, k.Comece nova iterao com E no papel de E(sem alterarP).

CASO2: E[h, Nn] oef[h] > 0 ou E[h, Nn] oef[h] < 0para algum h em M m P . h

DevolvaEe pare (a matriz E simples invivel).

CASO3: E[MmP, N]= O, f[MmP] = o e E[m, k] < 0paraalgumk emN n. k

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

CAS O3A: P vazio .DevolvaEe pare (a matriz E simples ilimitada).

CAS O3B: P no vazio .Escolhapem P de modo quef[p]/E[p, k]seja mnimo. pSejaE o resultado da pivotao deEem torno dep, k.Comece nova iterao com E no papel de E(sem alterarP).

CASO4: E[MmP, N]= O, f[MmP] = o e E[m, Nn] o.DevolvaEe pare (a matriz E simples solvel).

A operao de pivotao a que se referem os casos 1A, 1Be 3B definidacomo no algoritmo de Gauss-Jordan (seo2.3): dados elementos hde M me kde N n(as pivotaes jamais ocorrem na linha me jamais na coluna n),oresultado da pivotao de Eem 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 cadai em M h. claro que os casos 1Ae 1Bdevem ser entendidos como subcasos do caso 1;analogamente, 3A e 3Bso subcasos de 3. Os casos 1Be 3Bso formalmenteidnticos. A definio depnesses casos deve ser entendida da seguinte maneira:escolha qualquerpemP que satisfaa a condiof[p]/E[p, k] f[i]/E[i, k]paratodoi 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:MatrizEno 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 elementohde M m Pento

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

Por outro lado, se essa condio verdadeira para todo hem M m Pento 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 Xe Y ou We Z que aparecemna definio de alguns casos devem ser entendidas como ( XeY) ou (WeZ).


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 matrizEno incio de sucessivas iteraes. Neste exemplo, a primeira iterao comeacomP = {1}e Q = {1}. O subcaso 1Ase aplica com h, k = 2, 2. Na segundaiterao, o caso 1 se aplica comh, k = 3, 3; o subcaso 1Ano se aplica, mas osubcaso 1Bvale comp = 1. No incio da terceira iterao, a matrizEno maissimples que no incio da iterao anterior, mas em algum sentido melhor queaquela: depois de uma pivotao em torno de3, 4obtemos 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 colunakentra na base. Nos casos 1Be 3B, dizemos quesai da basea colunaqdefinidapela relaoE[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 ef[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 qquedever sair da base nos casos 1Be 3B? Como a matriz E[P, Q] estabelece umabijeo entre P e Q, o critrio de escolha de qse confunde com o critrio deescolha dep e p escolhido emP de modo que f[p]/E[p, k]seja mnimo.

A propsito, o esboo que fizemos acima corresponde, essencialmente, chamadaverso tabulardo Simplex.

1 Dizer quenegativo 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 Eno 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 seo2.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 PeQ 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 docaso 1Aos invariantes permanecem vlidos com E , P+he Q+k nos papisdeE,P eQ e que no fim dos casos 1Be 3Bos invariantes permanecem vlidoscomE eQ q+ knos papis deEe Q , ondeq o nico elemento de Qtal queE[p, q] = 1. Trocando em midos, basta mostrar que no fim do caso 1Atemos

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

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

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

e que no fim dos casos 1Be 3Btemos

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 depnos 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 1Aocorre em torno de h, ktemosf [h] =f[h]/E[h, k]e portanto f [h] 0. Resta considerar f [i] com iem P. Suponha inicialmentequeE[i, k]no positivo. Ento f [i] 0pois

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:MatrizE no fim do caso 1A.

ef[i] 0em virtude de (i0). Suponha agora queE[i, k] positivo. Ento f [i]0porque

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] 0para cadai em P+h .

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

f [p] 0 .

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

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

E[p, k]

ef[i] 0. Suponha agora queE[i, k] positivo. Ento f [i] 0porque

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 comopfoiescolhido.

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] = 0em 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 cadai em M 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:MatrizE no fim dos casos 1Be 3B.

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

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

E[, k] . Seja Ga 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 cadaiemM p. Observe que

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

Agora, para cadai em M,

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

Logo,E [, k] = I[, 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 Eque 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 (combasesPeQ).

3.4 Convergncia

Nosso esboo do Simplex freqentemente no converge, ou seja, freqente-

mente no atinge um dos casos terminais (2, 3Aou 4). Enquanto estiver ocor-rendo o caso 1A, bvio que estamos fazendo progresso, poisPaumenta. Mas possvel que haja uma seqncia infinita de ocorrncias dos casos 1 Bou 3B. Istoacontece, em especial, se o caso 1 ocorre em duas iteraes consecutivas com ummesmo valor dePe valores distintos de h , como mostra a figura3.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 naseo3.2. A figura registra o valor deEno incio de trs iteraes con-secutivas. Em todas, 1 o nico elemento de P. Na primeira iterao,

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

acontecendo o caso 1 com um mesmo valor dePe um mesmo valor de h , o va-lor absoluto def[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 matrizE simples comrelao a um dado par n, mde ndices.

3.2 Considere o esboo do Simplex feito na seo3.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 = 6em= 2. (Veja tambm o exerccio4.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 edecrescentese1 2 3 .


47/215


3.4 Aplique o Simplex descrito na seo3.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 ek escolhido, por engano, de modo queE[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 algoritmopois nem sempre converge.1 Masos exemplos de no-convergncia so muito mais raros que os do esboo quefizemos no captulo anterior (seo3.2). O prximo captulo mostrar comorefinar a heurstica para transform-la num algoritmo.

4.1 Introduo

A heurstica Simplex recebe uma matriz D , o ndicen de uma coluna e o ndicemde uma linha e calcula uma matriz Eque simples com relao ao par n,m .Para dizero que, exatamente, o Simplex faz preciso especificar a relao entreas matrizes Ee D . Essa relao um pouco mais restritiva que a do algoritmode Gauss-Jordan (captulo2): existem matrizes FeG tais que

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

ondeI a matriz identidade. A verso da heurstica que descreveremos a seguirdevolveFeG. De posse dessas matrizes, basta calcular os produtosF GeGDeverificar se, de fato, o primeiro igual matriz identidade e o segundo simplescom relao an,m .

ComoE=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 Umaheurstica 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-onalconvergese sua execuo termina depois de um nmero finito de iteraes, quaisquer quesejam os dados.

39


49/215

Feofiloff cap. 4 Heurstica Simplex 40

1 2 2 0 1 2 0 0 2 2 4 0 240 1 1 0 0 1 1/2 0 1 1 2 0 120 0 2 0 0 0 1/2 0 2 0 5 1 100 1 1 1 0 1 1 1 1 1 3 1 2

Figura 4.1:A figura especifica matrizesF,GeD . Verifique queF G = I, que G[, 4] = I[, 4] e que a matriz GD simples comrelao coluna5 e linha4 .

4.2 A heurstica

A heurstica Simplex adota a poltica, j sugerida no captulo anterior (veja se-o3.4), de insistir numa mesma linha henquanto isso fizer sentido. Essa po-ltica melhora muito a convergncia, embora no seja suficiente para garanti-la.Para implementar a poltica, introduzimos duas novas variveis: Le h .

Heurstica Simplex Recebe uma matrizD sobreM N e elementos Dnem deN eMrespectivamente; se convergir, devolve matrizesF eG n

msobreM Mtais queF G= I,G [, m] = I[, m] eGD simples (solvel,invivel, ou ilimitada) com relao ao parn, m.

Cada iterao comea com uma parteLdeMm, um elementohdeML, Lhe matrizesF,GeE. A primeira iterao comea comF =G = I,E= D ,L =

e com hem M, se possvel2 distinto de m. Cada iterao adota a abreviaturaf=E[, n]e consiste no seguinte: f

ALTERNATIVAI: h diferente dem.

CASOI.1: E[h, k] > 0 ef[h] 0 ou E[h, k] < 0 ef[h] 0para algum k em N n. k

SejaL o conjunto de todos os p em L para os quaisE[p, k]> 0 . L

CAS OI.1A: f[h]/E[h, k] f[p]/E[p, k] para todop em L .SejaF, G, E o resultado da pivotao deF,G, Eem torno deh, k.SejaL o conjuntoL+h.Escolhah emM L , se possvel distinto de m .Comece nova iterao com L ,h ,F ,G ,E

nos papis deL ,h ,F,G ,E.CAS OI.1B: f[h]/E[h, k] > f[p]/E[p, k] para algump em L .Escolha qualquerpem L tal quef[p]/E[p, k] mnimo. pSejaF, G, E o resultado da pivotao deF,G, Eem torno dep, k.Comece nova iterao com F ,G eE nos papis de F,Ge E.

2 Ou seja, seM mno vazio.


50/215


CASOI.2: E[h, Nn] oef[h]>0 ou E[h, Nn] oef[h] < 0.DevolvaFeG e pare.

CASOI.3: E[h, Nn] = o e f[h] = 0.SejaL o conjuntoL+h.

Escolhah emM L , se possvel distinto de m .Comece nova iterao com L eh nos papis deL e h .

ALTERNATIVAII: h igual am.

CASOII.1: E[h, k] < 0 para algumk em N n. kSejaL o conjunto de todos os p em L para os quaisE[p, k]> 0 . L

CAS OII.1A: L vazio .DevolvaFeGe pare.

CAS OII.1B: L no vazio .Escolha qualquerpem L tal quef[p]/E[p, k] mnimo. p

SejaF

, G

, E

o resultado da pivotao deF,G, Eem torno dep, k.Comece nova iterao com F ,G eE nos papis de F,Ge E.

CASOII.2: E[h, Nn] o.DevolvaFeG e pare. 3

A operao de pivotao definida como no algoritmo de Gauss-Jordan:dados elementoshde M me kde N n, oresultado da pivotao de F,G, E pivotaoem torno deh, k o terno F, G, E de matrizes definido pelas equaes

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

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

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

ondeh= 1/E[h, k]e i= E[i, k]/E[h, k]para cadaiemMh. Como j vimosem captulos anteriores,

F =FF , G = GG e E = GE ,

onde F a matriz elementar com coluna saliente h definida pela equao FF[, h] = E[, k]e G a inversa de F. G

Observaes. bvio que uma das duas grandes alternativas se aplica emcada iterao. Dentro de cada alternativa pelo menos um dos casos se aplica,

como verificamos no captulo anterior.A escolha de h no incio da primeira iterao e nos casos I.1Ae I.3 deve serentendida assim: escolhah de modo queh = msomente seM L= {m}.

A definio de p nos casos I.1B e II.1B deve ser entendida da seguintemaneira: escolha qualquer p em L que satisfaa a condio f[p]/E[p, k] f[i]/E[i, k]para todoi em L .

3 Ver soluo do exerccio4.2no apndiceE,pgina192.


51/215


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 L

1 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, Ge Eno incio de cada iterao. O rtulo L indica as linhas que estoemL . A ltima matrizE 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 9

1 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 1

Documents

Algoritmos de Programacao Linear-libre