capitulo 009 david lay

8/18/2019 Capitulo 009 David Lay

http://slidepdf.com/reader/full/capitulo-009-david-lay 1/52



MATERIAL SUPLEMENTAR PARA ACOMPANHAR

QUARTA EDIÇÃO

Álgebra Lineare Suas Aplicações

David C. LayUniversity of Maryland − College Park

Tradução e Revisão Técnica

Valéria de Magalhães IorioFundação Educacional Serra dos Órgãos (UNIFESO) – Teresópolis



Este Material Suplementar contém os Capítulos 9 e 10 que podem ser usados como apoio para o livroÁLGEBRA LINEAR E SUAS APLICAÇÕES, Quarta Primeira Edição, 2013. Este material é delivre acesso para os leitores que adquiriram o livro.

Material Suplementar Capítulos 9 e 10 traduzidos do material original:Authorized translation from the English language edition, entitled LINEAR ALGEBRA AND ITSAPPLICATIONS, 4th Edition by DAVID LAY, published by Pearson Education, Inc, publishing as

Pearson, Copyright © 2012 by Pearson Education, Inc.All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means,electronic or mechanical, including photocopying, recording or by any information storage retrievalsystem, without permission from Pearson education, Inc.

PORTUGUESE language edition published by LTC – LIVROS TÉCNICOS E CIENTÍFICOSEDITORA, Copyright © 2013.

Tradução autorizada da edição em língua inglesa intitulada LINEAR ALGEBRA AND ITSAPPLICATIONS, 4th Edition by DAVID LAY, published by Pearson Education, Inc, publishing asPearson, Copyright © 2012 by Pearson Education, Inc.Reservados todos os direitos. Nenhuma parte deste livro pode ser reproduzida ou transmitida sobquaisquer formas ou por quaisquer meios, eletrônico ou mecânico, incluindo fotocópia, gravação, ou porqualquer sistema de armazenagem e recuperação de informações sem permissão da Pearson Education,Inc.

Edição em língua PORTUGUESA publicada por LTC – LIVROS TÉCNICOS E CIENTÍFICOSEDITORA LTDA.,Copyright © 2013.

Obra publicada pela LTC Editora:ÁLGEBRA LINEAR E SUAS APLICAÇÕES, QUARTA EDIÇÃODireitos exclusivos para a língua portuguesaCopyright © 2013 byLTC __ Livros Técnicos e Científcos Editora Ltda.

Uma editora integrante do GEN | Grupo Editorial Nacional

Capa: Lucas AlvesEditoração Eletrônica: Alsan - Serviços de Editoração Eletrônica Ltda



Crédito das Fotos

Capítulo 9 Otimização 1EXEMPLO INTRODUTÓRIO: O Transporte Aéreo de Berlim 1

9.1 Jogos Matriciais 29.2 Programação Linear – Método Geométrico 139.3 Programação Linear – Método Simplex 219.4 Dualidade 33

Respostas dos Exercícios Ímpares do Capítulo 9 41

Capítulo 10 Cadeias de Markov de Estados Finitos 48EXEMPLO INTRODUTÓRIO: Google e Cadeias de Markov 48

10.1 Introdução e Exemplos 4910.2 O Vetor Estado Estacionário e o PageRank da Google 5810.3 Classes de Comunicação 6810.4 Classicação de Estados e Periodicidade 7410.5 A Matriz Fundamental 8210.6 Cadeias de Markov e Estatísticas de Beisebol 92

Apêndices 1 Demonstração do Teorema 1 101 2 Probabilidade 104

Respostas dos Exercícios Ímpares do Capítulo 10 111

Sumário



Capítulo 9 (Online): Página 1 O Transporte Aéreo de Berlim: Everett Collection Inc./Alamy.Capítulo 10 (Online): Página 1 Fundadores do Google: Kim Kulish/Corbis.

Crédito das Fotos



9Otimização

EXEMPLO INTRODUTÓRIO

O Transporte Aéreo de Berlim

Depois da segunda Guerra Mundial, a cidade de Berlim erauma “ilha” cercada pela zona soviética da Alemanha ocupada.A cidade estava dividida em quatro seções, com os ingleses,franceses e americanos tendo jurisdição sobre Berlim Ocidentale os soviéticos sobre Berlim Oriental. Mas os russos queriammuito que as outras três nações abandonassem Berlim.Depois de meses de assédio, no dia 24 de junho de 1948, elesimpuseram um bloqueio sobre Berlim Ocidental, impedindotodos os acessos por terra, inclusive por trem. Com uma

população civil em torno de 2,5 milhões de pessoas, os setoresisolados no ocidente tornaram-se dependentes de estoques dereserva e reposição por transporte aéreo.

Quatro dias depois, os primeiros aviões americanos

pousaram em Berlim com suprimentos de comida. Tinhacomeçado a “Operação Abastecimento”. No início, o transporteaéreo parecia fadado ao fracasso, já que as necessidadesda cidade eram muito grandes. Os russos tinham cortado ofornecimento de toda a eletricidade e de todos os carregamentos

de carvão, deixando a cidade literalmente sitiada. Masos aliados ocidentais responderam enviando milhares detoneladas de alimentos, carvão, remédios e outros suprimentosdiariamente por avião. Em maio de 1949, Stalin entregou os

pontos e levantou o bloqueio. O transporte aéreo, no entanto,continuou por mais quatro meses.

O Transporte Aéreo de Berlim foi muito bem-sucedidoao usar um número relativamente pequeno de aviões paraentregar uma quantidade enorme de suprimentos. A logísticae o comando dessa operação necessitaram de planejamentoe cálculos intensos, que levaram ao desenvolvimento teóricode programação linear e do método simplex desenvolvido

por George Dantzig. O potencial dessa nova ferramenta foi

rapidamente reconhecido pelos negócios e pela indústria. Hojeem dia, essa ferramenta é usada para alocar recursos, planejar a produção, programar os turnos dos trabalhadores, organizar os portfólios de investimento, formular estratégias de marketing efazer muitas outras tarefas envolvendo otimização.

WEB

Existem muitas situações em negócios, política, economia, estratégia militar e outras áreas nas quaisse tenta otimizar determinado benefício. Isso pode envolver maximizar um lucro ou o pagamento emuma competição, ou minimizar um custo ou outras perdas. Este capítulo apresenta dois modelos que

tratam problemas de otimização.

1

Os resultados fundamentais em ambos os casos dependem das propriedades de conjuntos convexos e hiperplanos. A Seção 9.1 introduz a teoria de jogos e desenvolveestratégias baseadas em probabilidade. As Seções de 9.2 a 9.4 exploram técnicas de programaçãolinear e as usam para resolver uma gama de problemas, inclusive jogos matriciais maiores que os naSeção 9.1.

1Agradeço a meu irmão, Dr. Steven R. Lay, por ter projetado e escrito a maior parte deste capítulo, e por tê-lo testado

em sala de aula na Universidade Lee. Eu também o testei em sala de aula e z algumas modicações/adições. Ele fun -

ciona bem e os alunos gostaram. No entanto, agradeceria receber comentários de qualquer pessoa que o utilize, profes-

sores ou estudantes.



2 CAPÍTULO 9

9.1 JOGOS MATRICIAISA teoria de jogos analisa fenômenos competitivos e procura fornecer uma base para a tomada de de-cisões racionais. Sua importância crescente foi destacada em 1994 quando o Prêmio Nobel de Eco-nomia foi dado a John Harsanyi, John Nash e Reinhard Selten pelo trabalho pioneiro na teoria de

jogos não cooperativos.2

Os jogos nesta seção são jogos matriciais

, cujos resultados variados estão listados em uma matrizde pagamentos. Dois jogadores competem em um jogo de acordo com um número xo de regras. OJogador L (de linha) tem uma escolha de m movimentos possíveis (ou escolhas de ação) e o Jogador C (de coluna) tem n movimentos. Por convenção, a matriz de pagamentos A = [a

ij] lista as quantias que

o jogador linha L ganha do jogador C , dependendo das escolhas de L e de C . O elemento aij mostra a

quantia que L ganha quando L escolhe a ação i e C escolhe a ação j. Um valor negativo de aij indica

uma perda de L, o valor que L tem de pagar a C . Os jogos são chamados, muitas vezes, jogos de somazero com duas pessoas, porque a soma algébrica das quantidades ganhas por L e C é zero.

EXEMPLO 1 Cada jogador tem um suprimento de moedas de um, cinco e dez centavos. A um dadosinal, ambos mostram (ou “jogam”) uma moeda. Se as moedas mostradas não forem iguais, o jogadorque mostra a moeda de valor mais alto cará com as duas. Se ambas as moedas forem de um ou decinco centavos, então o jogador C cará com as duas; mas se ambas as moedas forem de dez centavos,o jogador L cará com elas. Construa uma matriz de pagamentos usando p (do inglês penny) para a

moeda de um centavo, n (do inglês nickel ) para moedas de cinco centavos e d (do inglês dime) paramoedas de dez centavos.

SOLUÇÃO Cada jogador tem três escolhas, p, n e d , de modo que a matriz de pagamentos é uma ma-triz 3 × 3:

Considere uma linha para L e preencha o que L recebe (ou paga) dependendo da escolha feita porC . Suponha, primeiro, que L mostre um centavo. Se C também mostrar um centavo, L perderá umcentavo, já que as moedas são iguais. O elemento (1, 1) é −1. Se C jogar uma moeda de cinco ou de

dez centavos, L também perderá um centavo, já que C mostrou a moeda de valor mais alto. Esta in-formação vai para a linha 1:

A seguir, suponha que L jogue cinco centavos. Se C jogar um centavo, L ganhará esse centavo. Casocontrário, L perderá os cinco centavos, pois a moeda de C ou era igual a cinco centavos ou era dezcentavos, portanto de maior valor. Finalmente, quando L jogar dez centavos, L ganhará um ou cincocentavos se C mostrar uma dessas moedas, já que a moeda de L tinha valor maior. Além disso, se am-

bos mostrarem dez centavos, L ganhará de C por causa da regra especial neste caso.

■

Olhando a matriz de pagamentos no Exemplo 1, os jogadores descobrem que algumas jogadassão melhores que outras. Ambos os jogadores sabem que L deverá escolher uma linha com elemen-tos positivos, enquanto C deverá escolher uma coluna com elementos negativos (um pagamento de L

para C ). O jogador L nota que todos os elementos na linha 3 são positivos e escolhe jogar dez centa-

2

O lme popular de 2002, Uma Mente Brilhante ( A Beautiful Mind , no original em inglês), conta a história comoventeda vida de John Nash.



Otimização 3

vos. Não importa o que C faça, o pior que pode acontecer com L é ganhar só um centavo. O jogadorC nota que todas as colunas têm elementos positivos e, portanto, nunca pode ganhar nada. Então o

jogador C decide jogar um centavo, que irá minimizar sua perda.De um ponto de vista matemático, o que cada jogador fez? O jogador L encontrou o mínimo em

cada linha (o pior que poderia acontecer para aquela jogada) e escolheu a linha na qual esse mínimoé maior. (Veja a Figura 1.) Ou seja, L calculou

i jaij

–1

1

1

–1

5

–5

–1

10

–5

–1

1

1 5 10

–5

JogadorC Mínimo das linhas

Jogador L

Máximo das colunas

Máximo dos mínimos

Mínimo dos máximos

FIGURA 1

Note que, para C , um pagamento positivo alto para R é pior que um pagamento positivo pequeno.Então C encontrou o máximo de cada coluna (o pior que pode acontecer a C para aquela jogada) eescolheu a coluna para a qual esse máximo é menor. O jogador C encontrou

Para essa matriz de pagamentos [aij],

DEFINIÇÃO Se a matriz de pagamentos de um jogo matricial contiver um elemento aij que é, ao mesmo tem-

po, o mínimo da linha i e o máximo da linha j, então aij será chamado um ponto de sela.

No Exemplo 1, o elemento a

31 é um ponto de sela para a matriz de pagamentos. Enquanto ambos

os jogadores continuam a buscar a jogada mais vantajosa, o jogador L sempre vai mostrar dez centa-vos (linha 3) e o jogador C sempre vai mostrar um centavo (coluna 1). Alguns jogos podem ter maisde um ponto de sela.

A situação no próximo exemplo não é tão simples.

EXEMPLO 2 Suponha, novamente, que cada jogador tenha um suprimento de moedas de um, cincoe dez centavos, mas, agora, a matriz de pagamentos é a seguinte:

Se o jogador L raciocinar como no primeiro exemplo e considerar os mínimos das linhas, L vai es-colher mostrar cinco centavos maximizando, assim, o ganho mínimo (a perda de 1 neste caso). O

jogador C , considerando os máximos das colunas, também vai selecionar cinco centavos para mini-mizar sua perda para L.



4 CAPÍTULO 9

Então, no início do jogo, ambos L e C continuarão a jogar cinco centavos. Depois de um tempo,no entanto, C começará a pensar: “Se L vai car jogando cinco centavos, então vou jogar dez paraganhar um.” No entanto, quando C começar a jogar dez centavos repetidamente, L começará a pen-sar: “Se C vai continuar jogando dez centavos, vou jogar um centavo para ganhar cinco.” Depoisque L começar a fazer isso, C mudará para cinco centavos (para ganhar cinco) e então L começaráa jogar cinco … e assim por diante. Parece que nenhum dos jogadores pode desenvolver uma es-tratégia vencedora. ■

Do ponto de vista matemático, a matriz de pagamentos para o jogo no Exemplo 2 não tem um ponto de sela. De fato,

enquanto

Isso signica que nenhum dos jogadores pode jogar a mesma moeda repetidamente e ter a garan-tia de otimizar seus ganhos. De fato, qualquer estratégia previsível pode ser combatida pelo seuoponente. Mas é possível formular alguma combinação de jogadas que, em longo prazo, produ-zirá um retorno ótimo? A resposta é sim (como o Teorema 3 irá mostrar mais tarde), quando cadamovimento é feito de maneira aleatória, mas com determinada probabilidade associada a cadaescolha possível.

Eis um modo de imaginar como o jogador L poderia desenvolver uma estratégia para jogar um jogo matricial. Suponha que L tenha um instrumento que consiste em uma echa horizontal de metalcujo centro de gravidade está apoiado em uma barra vertical no meio de uma região circular plana.Essa região está dividida em setores em formato de fatias de pizza, um para cada uma das linhas namatriz de pagamentos. O jogador L dá um peteleco inicial para rodar a seta e espera até ela parar. A

posição da ponta da seta em repouso determina a jogada de L no jogo matricial.Se a área do círculo for considerada como tendo 1 unidade, então a soma das áreas dos diversos se-

tores será igual a 1. Essas áreas fornecem as frequências relativas, ou probabilidades, de se selecionardiversas jogadas no jogo matricial, quando o jogo é jogado muitas vezes. Por exemplo, se existiremcinco setores de áreas iguais e se a seta for girada muitas vezes, o jogador L irá selecionar cada umadas cinco jogadas possíveis 1/5 das vezes. Essa estratégia é especicada pelo vetor em ℝ5 que temtodos os elementos iguais a 1/5. Se os cinco setores não forem do mesmo tamanho, no longo prazoalgumas jogadas serão escolhidas com mais frequência que outras. A estratégia correspondente para

L é especicada por um vetor em ℝ5 que lista as áreas dos cinco setores.

DEFINIÇÃO Um vetor de probabilidade emℝm é um vetor x pertencente a ℝm tal que todas as componentessão não negativas e sua soma é igual a um. Tal x é da forma

Seja A uma matriz de pagamentos m × n para um jogo. O espaço estratégico para o jogador L éo conjunto de todos os vetores de probabilidade em ℝm, e o espaço estratégico para o jogador C é o conjunto de todos os vetores de probabilidade em ℝn. Um ponto em um espaço estratégico échamado uma estratégia. Se uma componente em uma estratégia for 1 (e todas as outras foremnulas), essa estratégia será chamada uma estratégia pura.

As estratégias puras em ℝm são os vetores da base canônica e1, …, e

m. Em geral, cada estratégia

x é uma combinação linear x1e

1 + … + x

me

m dessas estratégias puras com coecientes não negativos,

cuja soma é igual a 1.3

Suponha, agora, que L e C estejam jogando um jogo matricial com matriz A = [aij] m × n, no qual

aij é o elemento na linha i e coluna j de A. Existem mn resultados possíveis do jogo, dependendo da

3Mais precisamente, cada estratégia é uma combinação convexa do conjunto de estratégias puras – ou seja, um ponto no

fecho convexo dos vetores da base canônica. Esse fato liga a teoria dos conjuntos convexos ao estudo dos jogos matri-

ciais. O espaço estratégico para L é um simplex em ℝm de dimensão m – 1, e o espaço estratégico para C é um simplex

em ℝn de dimensão n – 1. Veja as Seções 8.3 e 8.5 para as denições.



Otimização 5

linha escolhida por L e da coluna escolhida por C . Suponha que L use a estratégia x e C use a estra-tégia y, em que

Como L joga a primeira linha com probabilidade x1, C joga a primeira coluna com probabilidade y1 e suas escolhas são feitas de maneira independente, pode-se mostrar que a probabilidade de que L escolha a primeira linha e C escolha a primeira coluna é x

1 y

1. Depois de muitos jogos, o pagamento

esperado para L em um jogo é a11 x

1 y

1. Um cálculo análogo pode ser feito para cada par de escolhas

possíveis de L e C . A soma de todos os pagamentos esperados para L, para todos os pares de esco-lhas possíveis, é o pagamento esperado E (x, y) do jogo para o jogador L para as estratégias x e y.Ou seja,

Grosso modo, o número E (x, y) é a quantia média que C pagará a L por jogo quando L e C jogam umagrande quantidade de jogos usando as estratégias x e y, respectivamente.

Vamos denotar por X o espaço estratégico para L e por Y o espaço estratégico para C . Se L esco-lhesse uma determinada estratégia, digamos x, e se C descobrisse essa estratégia, então C certamenteescolheria y que minimizasse

O valor de usar uma estratégia x é o número v(x) denido por

(1)

Como xT Ay é uma matriz 1 × n, a aplicação y ↦ E (x, y) = xT Ay é um funcional linear no espaçoestratégico Y . Usando esse fato, pode-se mostrar que E (x, y) atinge seu mínimo quando y é uma dasestratégias puras e

1, …, e

n para C .4

Lembre-se de que Ae j é a j-ésima coluna da matriz A, normalmente denotada por a

j. Como o míni-

mo em (1) é atingido quando y = e j para alguma j, (1) pode ser escrito, com x no lugar de x, como

(2)

Ou seja, v(x) é o mínimo de todos os produtos internos de x com cada uma das colunas de A. O objetivo de L é escolher x que maximize v(x).

DEFINIÇÃO O número v L, denido por

com a notação descrita anteriormente, é chamado valor do jogo para o jogador linha L. Umaestratégia x para L é dita ótima se v(x) = v

L.

É claro que E (x, y) pode ser maior que v L para algum x e y se C jogar mal. Assim, x é ótimo para L

se E (x, y) ≥ v L para todo y em Y . Pode-se pensar neste valor v

L como o máximo que o jogador L pode

ter certeza de que vai receber de C , independente das jogadas de C . Uma análise semelhante para o jogador C , usando as estratégias puras para x, mostra que uma es-tratégia particular y terá um valor v(y) dado por

(3)

já que eT i A = linha

i( A). Ou seja, o valor da estratégia y para C é o máximo dos produtos internos de y

com cada linha de A. O número vC , denido por

4Um funcional linear em Y é uma transformação linear de Y emℝ. As estratégias puras são os pontos extremos do espaço

estratégico para um jogador. O resultado enunciado segue diretamente do Teorema 16 na Seção 8.5.



6 CAPÍTULO 9

é chamado valor do jogo para o jogador coluna C. Este é o mínimo que C irá perder, independentedas jogadas de L. Uma estratégia y para C é dita ótima se v(y) = v

C . Equivalentemente, y é ótimo se

E (x, y) ≤ vC para todo x em X .

TEOREMA 1 Em um jogo matricial, v L ≤ v

C .

DEMONSTRAÇÃO Para qualquer x em X , a denição v(x) = min y∈Y

E (x, y) implica ser v(x) ≤ E (x, y) para todo y em Y . Além disso, como v(y) é o máximo de E (x, y) quando x percorre X , v(y) ≥ E (x, y) para todo x. Essas duas desigualdades mostram que

para todo x ∈ X e todo y ∈Y . Para qualquer y xo, a desigualdade à esquerda implica ser maxx∈ X

v(x)≤ E (x, y). Analogamente, para cada x, E (x, y) ≤ min

y∈Y v(y). Portanto,

o que prova o teorema. ■

EXEMPLO 3 Sejam em que A vem do Exem-

plo 2. Calcule E (x, y) e verique que esse número está entre v(x) e v(y).

SOLUÇÃO Calcule

A seguir, de (2), v(x) é o mínimo de E (x, e j) para 1 ≤ j ≤ 3. Então calcule

Logo, Analogamente, E (e2, y)5

0 e E (e3, y) = −5, de modo que Portanto, E (x, y) ≤ v(y), como espe-

rado. ■

No Teorema 1, a demonstração de que v L ≤ v

C foi simples. Um resultado fundamental em te-

oria dos jogos é que v L = v

C , mas isso não é fácil de provar. A primeira demonstração, feita em

1928 por John Von Neumann, era tecnicamente difícil. A demonstração que talvez seja a mais

conhecida depende muito de determinadas propriedades de conjuntos convexos e hiperplanos.Ela apareceu no livro clássico de Von Neumann e Oskar Morgenstern, Theory of Games and

Economic Behavior .5

5De forma mais precisa, a demonstração envolve encontrar um hiperplano que separa estritamente a origem do fecho

convexo de {a1, …, a

n, e

1, …, e

m}, em que a

1, …, a

n são as colunas de A e e

1, …, e

m são os vetores da base canônica para

ℝm

. Os detalhes podem ser encontrados em Steven R. Lay, Convex Sets and Their Applications (Nova York: John Wiley& Sons, 1982; Mineola, NY: Dover Publications, 2007), pp. 159-163.



Otimização 7

6 A demonstração baseada no Teorema Minimax é a seguinte: A função v(x) é contínua no conjunto compacto X , logoexiste um ponto x em X tal que

Analogamente, existe y em Y tal que

De acordo com o Teorema Minimax, v L = v

C = v.

TEOREMA 2 Teorema Minimax

Em qualquer jogo matricial, v L = v

C . Ou seja,

DEFINIÇÃO O valor comum v = v L = v

C é chamado valor do jogo. Qualquer par de estratégias ótimas (x, y)é chamado uma solução para o jogo.

Quando (x, y) é uma solução para o jogo, v L = v(x) ≤ E (x, y) ≤ v(y) = v

C , o que mostra que

E (x, y) = v.O próximo teorema é o resultado teórico principal desta seção. Uma demonstração pode estar ba-

seada no Teorema Minimax ou na teoria de programação linear (na Seção 9.4).6

TEOREMA 3 Teorema Fundamental para Jogos Matriciais

Em qualquer jogo matricial, sempre existem estratégias ótimas. Em outras palavras, todo jogo

matricial tem solução.

Jogos Matriciais 2 × n

Quando um jogo matricial tem duas linhas e n colunas, é bem fácil calcular uma estratégia ótima paraas linhas e v

L. Suponha que

O objetivo do jogador L é escolher x em ℝ2 que maximiza v(x). Como x só tem duas componentes,o espaço estratégico X para L pode ser parametrizado por uma variável t , com um x típico tendo a

forma para 0 ≤ t ≤ 1. Da fórmula (2), v(x(t )) é o mínimo dos produtos internos de x(t ) com

cada uma das colunas de A, ou seja,

(4)

Logo, v(x(t )) é o valor mínimo de n funções lineares de t . Quando os grácos dessas funções são co-locados em um sistema de coordenadas para 0 ≤ t ≤ 1, o gráco de z = v(x(t )) ca evidente e o valormáximo de v(x(t )) é fácil de encontrar. O processo é ilustrado melhor por um exemplo.

EXEMPLO 4 Considere o jogo cuja matriz de pagamentos é

a. Em um sistema de coordenadas tz, esboce os quatro segmentos de reta z = a1 j(1 – t ) + a2 jt para 0 ≤ t ≤ 1 e escureça os segmentos de reta que correspondem ao gráco de z = v(x(t )), de (4).

b. Identique o ponto mais alto M = (t , z) no gráco de v(x(t )). A coordenada z de M é o valor v L do

jogo para L e a coordenada t determina uma estratégia ótima x (t ) para L.



8 CAPÍTULO 9

7Resolva simultaneamente as equações para as colunas 1 e 3:

SOLUÇÃO

a. As quatro retas são

Veja a Figura 2. Note que a reta z = a1 j ⋅ (1 – t ) + a

2 j ⋅ t contém os pontos (0, a

1 j) e (1, a

2 j). Por exem-

plo, a reta z = 6 ⋅ (1 – t ) + 2 ⋅ t para a coluna 4 contém os pontos (0, 6) e (1, 2). O caminho poligonalmais grosso na Figura 2 representa v(x) como função de t , já que a coordenada z de um ponto nestecaminho é o mínimo das coordenadas z correspondentes dos pontos nos quatro segmentos de reta naFigura 2.

t 1

3

2

c o l u n a 2

c o l u n a 3

c o l u n a 4

c o l u n a 1

1

M

0

z

6

5

4

2

5

11

5

FIGURA 2

b. O ponto mais alto M no gráco de v(x) é a interseção dos segmentos de reta correspondentes à

primeira e à terceira colunas de A. As coordenadas de M são ( 2 – 5, 11 –

5).7 O valor do jogo para L é 11 –

5.

Esse valor é atingido em t =2

– 5 , de modo que a estratégia ótima para L é■

O Exemplo 4 ilustra um método para encontrar uma solução ótima para o jogador L em qualquer

jogo matricial 2 × n. O teorema 3 garante que também existe uma estratégia ótima para o jogadorC e o valor do jogo é o mesmo para L e para C . Com esse valor disponível, uma análise da soluçãográca para L, como na Figura 2, revelará como produzir uma estratégia ótima y para C . O próximoteorema fornece a informação-chave sobre y.

TEOREMA 4 Sejam x e y estratégias ótimas para um jogo matricial m × n cujo valor é v e suponha que

(5)

Então y é uma combinação convexa das estratégias puras e j emℝn , para as quais E (x, e j) = v. Alémdisso, y satisfaz a equação

(6)

para cada i tal que x i ≠ 0.

DEMONSTRAÇÃO Escreva y = y1e1 + … + y

ne

n em ℝn e note que v = E (x, y) = v(x ) ≤ E (x, e

j) para

j = 1, …, n. Então existem números não negativos ε j tais que



Otimização 9

Então

já que a soma dos y j é um. Essa igualdade só é possível se y

j = 0 sempre que ε

j > 0. Logo, y é uma

combinação linear dos e j para os quais ε

j = 0. Para tais j, E (x, e

j) = v.

A seguir, note que E (ei, y) ≤ v(y) = E (x, y) para i = 1, …, m. Então existem números não negati-

vos δ i tais que

(7)

A Equação (5) fornece

já que a soma dos x i é um. Essa igualdade só é possível se δ

i = 0 quando x i ≠ 0. De (7), E (ei, y) = v

para todos os i tais que x i ≠ 0. ■

EXEMPLO 5 O valor do jogo no Exemplo 4 é 11 – 5, atingido quando Use esse fato para

encontrar uma estratégia ótima para o jogador coluna C .

SOLUÇÃO A coordenada z do ponto máximo M na Figura 2 é o valor do jogo, e a coordenada t iden-tica a estratégia ótima x( 2 –

5) = x. Lembre que as coordenadas z dos segmentos de reta na Figura 2

representam E (x(t ), e j) para j = 1, …, 4. Só os segmentos de reta correspondentes às colunas 1 e 3

contêm o ponto M , o que signica que

enquanto E (x, e2) e E (x, e

4) são maiores que 11 –

5. Pelo Teorema 4, a estratégia ótima y para C é uma

combinação linear das estratégias puras e1 e e

3 em ℝ4. Assim, y é da forma

na qual c1 + c

3 = 1. Como ambas as coordenadas do x ótimo são diferentes de zero, o Teorema 4 mostra

que E (e1, y) = 11 –

5e E (e2

, y) = 11 – 5. Cada condição, por si só, determina y. Por exemplo,

Substitua c3 = 1 – c1 para obter 4c1 + (1 – c1) =11 – 5,, c1 =

2 – 5 e c3 =3 – 5 . A estratégia ótima para C é

■

Reduzindo o Tamanho de um Jogo

Um jogo matricial geral com matriz m × n pode ser resolvido usando-se técnicas de programaçãolinear, e a Seção 9.4 descreve um método para isso. Em alguns casos, no entanto, um jogo matricial



10 CAPÍTULO 9

pode ser reduzido a um jogo “menor” cuja matriz tem apenas duas linhas. Se isso acontecer, o métodográco dos Exemplos 4 e 5 estarão disponíveis.

DEFINIÇÃO Dados a e b em n, com coordenadas ai e b

i respectivamente, o vetor a domina o vetor b se

ai ≥ b

i para todo i = 1, …, n e a

i > b

i para pelo menos um i. Se a dominar b, b será dito recessi-

vo em relação a a.

Suponha que, no jogo matricial A, a linha r domine a linha s. Isso signica que, para L, a estra-tégia pura de escolher a linha r é pelo menos tão boa quanto a estratégia pura de escolher a linha s,independente da escolha de C , e, para algumas escolhas de C , r é melhor que s. Segue que a linharecessiva s (a “menor”) pode ser ignorada por L sem prejuízo para o pagamento esperado de L. Umaanálise semelhante pode ser aplicada às colunas de A e, nesse caso, a coluna dominante “maior” podeser ignorada. Essas observações estão resumidas no teorema a seguir.

TEOREMA 5 Seja A um jogo matricial m × n. Se a linha s na matriz A for recessiva em relação a outra linha, seja A

1 a matriz (m – 1) × n obtida de A eliminando-se a linha s. Analogamente, se a coluna t dominar

outra coluna, seja A2 a matriz m × (n – 1) obtida de A eliminando-se a coluna t . Em qualquer dos

casos, qualquer estratégia ótima do jogo matricial reduzido A1 ou A2 determinará uma estratégiaótima para A.

EXEMPLO 6 Use o processo descrito no Teorema 5 para reduzir de tamanho o jogo matricial a seguir.Depois, encontre o valor do jogo e estratégias ótimas para ambos os jogadores no jogo original.

SOLUÇÃO Como a primeira coluna domina a terceira, o jogador C não vai querer usar a primeiraestratégia pura. Então, elimine a primeira coluna para obter

Nessa matriz, a linha 2 é recessiva em relação à linha 3. Elimine a linha 2 para obter

Essa matriz reduzida 2 × 3 pode ser ainda mais reduzida eliminando-se a última coluna, já que eladomina a coluna 2. Assim, o jogo com matriz original A foi reduzido a

(8)

e qualquer estratégia ótima para B produzirá uma estratégia ótima para A com zeros nos elementos

correspondentes às linhas ou colunas eliminadas.Uma vericação rápida da matriz B mostra que o jogo não tem ponto de sela (pois 3 é o máximo

dos mínimos das linhas e 5 é o mínimo dos máximos das colunas). Então, é necessário o método grá-co de solução. A Figura 3 mostra os segmentos de reta correspondentes às duas colunas de B, cujasequações são z = 4t + 1 e z = −3t + 6. Eles se intersectam em t = 5 –

7; o valor do jogo é 27 –

7 e a estratégia

ótima para linhas da matriz B é

Como o jogo não tem ponto de sela, a estratégia ótima para colunas tem de ser uma combinação lineardas duas estratégias puras. Escreva y = c

1e1 + c

2e2 e use a segunda parte do Teorema 4 para escrever



Otimização 11

t 1

3

c o l u n a 2

c o l u n a 1

1

M

0

z

6

5

5

7

27

7

FIGURA 3

Resolvendo, obtém-se 5c2 = 20 –

7, c

2 = 4 –

7 e c

1 = 1 – c

2 = 3 –

7. Assim, Para vericar, calcule E (e2

,y ) = 5( 3 –

7) + 3(

4 – 7

) = 27 – 7 = v.

O passo nal é construir a solução para a matriz A da solução para a matriz B (dada por x e y an-teriores). Olhe para a matriz em (8) para ver onde os zeros devem ser colocados. As estratégias para

linhas e colunas de A são, respectivamente,

■

PROBLEMA PRÁTICO

Encontre as estratégias ótimas e o valor do jogo matricial

9.1 EXERCÍCIOS Nos Exercícios 1 a 4, escreva a matriz de pagamentos para cada jogo.

1. O jogador L tem um suprimento de moedas de dez e de vinte e cinco

centavos. O jogador L escolhe uma das moedas e o jogador C temde adivinhar o valor da moeda escolhida por L. Se C acertar, carácom a moeda. Se C errar, pagará a L uma quantia igual ao valor damoeda.

2. Cada jogador mostra um, dois ou três dedos. Se o número total N dededos mostrados for par, C pagará N reais para L. Se N for ímpar,

L pagará N reais para C .

3. No jogo infantil tradicional japonês janken (ou “pedra, tesoura, papel”), a um sinal dado, cada um dos dois jogadores mostra a mãofechada (pedra), dois dedos (tesoura) ou todos os cinco dedos (pa-

pel). Pedra ganha de tesoura, tesoura ganha de papel e papel ganhade pedra. Em caso de empate, não há pagamento. Quando um jo-gador ganha, ele recebe 5 ienes. (No dia 10 de dezembro de 2004,a estação de televisão de esportes da Fox mostrou o CampeonatoMundial de Pedra, Papel e Tesoura de 2004. Veja www.worldrps.com.)

4. O jogador L tem três cartas: um 3 vermelho, um 6 vermelho e um7 preto. O jogador C tem duas cartas: um 4 vermelho e um 9 preto.

Cada um mostra uma de suas cartas. Se as cartas forem da mesmacor, L receberá o valor correspondente ao maior dos dois números.

Se as cartas forem de cores diferentes, C receberá o valor correspondente à soma dos dois números.

Encontre todos os pontos de sela nos jogos matriciais nos Exercícios 5a 8.

5.

7.

9. Seja M o jogo matricial com matriz de pagamentos

Encontre E (x, y), v(x) e v(y) para os vetores x e y dados.



12 CAPÍTULO 9

10. Seja M o jogo matricial com matriz de pagamentos

Encontre E (x, y), v(x) e v(y) para os ve-

tores x e y dados.

Nos Exercícios de 11 a 18, encontre as estratégias ótimas para linhas ecolunas e o valor de cada jogo matricial.

19. Um determinado exército está envolvido em uma guerrilha. Exis-tem duas maneiras para receber suprimentos para as tropas: pode-se mandar um comboio pelo rio ou através da selva. Em cada dia,os guerrilheiros só conseguem observar um dos dois caminhos. Seo comboio for pelo rio e os guerrilheiros estiverem lá, o comboioterá de voltar e o exército perderá quatro soldados. Se o comboiofor pela selva e encontrar guerrilheiros, metade dos suprimentosconseguirão passar, mas o exército perderá sete soldados. A cadadia, um comboio de suprimentos vem por um dos caminhos e, seos guerrilheiros estiverem observando o outro caminho, o comboiochegará sem perdas. Escreva e resolva os jogos matriciais a seguir,com L sendo o exército.

a. Qual é a estratégia ótima para o exército se o objetivo for maxi-mizar a quantidade de suprimentos que chega à tropa? Qual é aestratégia ótima para os guerrilheiros se eles quiserem impedir

a maioria dos suprimentos de chegar ao destino? Se essas estra-tégias forem seguidas, que porção dos suprimentos chegará aodestino?

b. Qual é a estratégia ótima para o exército se o objetivo for mini-mizar as baixas? Qual é a estratégia ótima para os guerrilheirosse eles quiserem inigir o maior número de baixas? Se essas

estratégias forem seguidas, que porção dos suprimentos chegará

ao destino?

20. Suponha, no Exercício 19, que sempre que o comboio for pela sel-va, dois soldados acabarão pisando em minas terrestres, quer sejam

atacados ou não. Assim, se o comboio encontrar com guerrilheiros,serão nove baixas. Se não encontrar, serão duas baixas.

a. Encontre as estratégias ótimas para o exército e para os guerri-lheiros em relação ao número de baixas.

b. No item (a), qual é o “valor” do jogo? O que isso representa para

as tropas?

Nos Exercícios 21 e 22, marque cada armação como Verdadeira ou Fal-

sa. Justique cada resposta.21. a. A matriz de pagamentos de um jogo matricial indica o ganho de

L para cada combinação de jogadas.

b. Com uma estratégia pura, um jogador faz a mesma escolha cada

vez que joga.

c. O valor v(x) de uma estratégia particular x para o jogador L éigual ao máximo dos produtos internos de x com cada uma dascolunas da matriz de pagamentos.

d. O Teorema Minimax diz que todo jogo matricial tem solução.

e. Se a linha s for recessiva em relação a outra linha na matrizde pagamentos A, então a linha s não será usada (ou seja, tem

probabilidade zero) em uma estratégia ótima para o jogador(linha) L.

22. a. Se aij for um ponto de sela, então a

ij será o menor elemento na

linha i e o maior elemento na coluna j.

b. Cada estratégia pura é uma estratégia ótima.

c. O valor v L do jogo para o jogador L é o máximo dos valores das

diversas estratégias possíveis para L.

d. O Teorema Fundamental para os Jogos Matriciais mostra comoresolver cada jogo matricial.

e. Se a coluna t dominar alguma outra coluna na matriz de pagamen-

tos A, então a coluna t não será usada (ou seja, tem probabilidadezero) em uma estratégia ótima para o jogador (coluna) C .

23. Encontre as estratégias ótimas e o valor do jogo no Exemplo 2.

24. Bill e Wayne estão jogando um jogo no qual cada jogador tem umaescolha de duas cores: vermelho ou azul. A matriz de pagamentoscom Bill sendo o jogador linha é dada a seguir.

Por exemplo, isso signica que, se ambos escolherem vermelho,

Bill pagará Wayne uma unidade.

a. Usando os mesmos pagamentos para Bill e Wayne, escreva a ma-

triz que mostra os ganhos com Wayne sendo o jogador linha.

b. Se A for a matriz com Bill sendo o jogador linha, escreva suaresposta no item (a) em função de A.

25. Considere o jogo matricial A = no qual A não tem ponto

de sela.

a. Encontre uma fórmula para as estratégias ótimas x para L e y

para C . Qual é o valor do jogo?

b. Seja e sejam α e β números reais, com α ≠ 0.

Use sua resposta no item (a) para mostrar que as estratégias óti-mas para o jogo matricial B = α A + β J são as mesmas para A.Em particular, note que as estratégias para A e para A + β J sãoas mesmas.

26. Seja A um jogo matricial com valor v. Encontre um exemplo paramostrar que E (x, y) = v não implica, necessariamente, x e y seremestratégias ótimas.



Otimização 13

SOLUÇÃO DO PROBLEMA PRÁTICO

A primeira linha é recessiva em relação à terceira, de modo que pode ser eliminada. As segunda e

quarta colunas dominam, respectivamente, a primeira e a terceira. Eliminando a segunda e a quartacolunas, obtém-se a matriz B:

O jogo para B não tem pontos de sela, mas uma análise gráca irá funcionar. As duas colunas de B determinam os dois segmentos de reta ilustrados a seguir, cujas equações são z = 2 ⋅ (1 – t ) + 1 ⋅ t e

z = −1 ⋅ (1 – t ) + 2 ⋅ t .

t

22

1

–1

z

3

4

5

4

Esses segmentos de reta se intersectam no ponto ( 3 – 4, 5 –

4). O valor do jogo é 5 –

4e a estratégia ótima para

linhas para o jogo matricial B é

Pelo Teorema 4, a estratégia ótima para colunas, satisfaz as duas equações E (e1, y) = 5 –

4

e E (e2, y) = 5 –

4, já que x é uma combinação linear de e1

e e2. Cada uma dessas equações determina y.

Por exemplo,

Logo, c1 = 3 –

4, c

2 = 1 –

4 e Para conrmar, calcule

Isso resolve o jogo para B. A estratégia ótima para linhas x para A tem zero na primeira coordenada(para a primeira linha eliminada); a estratégia ótima para colunas y para A tem zeros na segunda e naquarta componentes. Portanto,

9.2 PROGRAMAÇÃO LINEAR – MÉTODO GEOMÉTRICODesde a década de 1950, a variedade e tamanho de problemas de programação linear industriaiscresceram junto com o aumento dramático do poder computacional. Ainda assim, em seu âmago,

problemas de programação linear têm uma descrição matemática concisa discutida nesta seção. Oexemplo nal desta seção apresenta uma visão geométrica da programação linear que é importante

para a visualização da abordagem algébrica necessária para problemas maiores.Em geral, um problema de programação linear envolve um sistema de desigualdades lineares nas

variáveis x1, …, x

n e um funcional linear f de ℝn em ℝ. O sistema, tipicamente, tem muitas variáveis

livres, e o problema é encontrar uma solução x que maximiza ou minimiza f (x).



14 CAPÍTULO 9

EXEMPLO 1 A companhia de sementes de grama Pista Esperta mistura dois tipos de sementes, aSempreVerde e a VerdeRápido. Cada saco de SempreVerde contém 3 kg de sementes de festuca, 1 kgde sementes de centeio e 1 kg de sementes de capim-do-campo. Cada saco de VerdeRápido contém2 kg de sementes de festuca, 2 kg de sementes de centeio e 1 kg de sementes de capim-do-campo. Acompanhia tem 1200 kg de sementes de festuca, 800 kg de sementes de centeio e 450 kg de capim-do-campo disponíveis para colocar em suas misturas. A companhia tem um lucro de R$2,00 em cadasaco de SempreVerde e de R$3,00 em cada saco de VerdeRápido que produz. Escreva o problemamatemático que determina o número de sacos de cada mistura que a Pista Esperta deve produzir paramaximizar seu lucro.

SOLUÇÃO A frase “maximizar … lucro” identica o objetivo do problema. O primeiro passo, en-tão, é estabelecer uma fórmula para o lucro. Comece nomeando as quantidades variáveis. Seja x

1 o

número de sacos de SempreVerde e x2 o número de sacos de VerdeRápido produzidos. Como o lucro

em cada saco de SempreVerde é de R$2,00 e o lucro em cada saco de VerdeRápido é de R$3,00, olucro total (em reais) é

O próximo passo é escrever as desigualdades ou igualdades que x1 e x

2 têm de satisfazer, uma para

cada um dos ingredientes com suprimento limitado. Cada saco de SempreVerde usa 3 kg de sementesde festuca e cada saco de VerdeRápido usa 2 kg, logo a quantidade total necessária de sementes defestuca é 3 x

1 + 2 x

2. Como a companhia só tem 1200 kg disponíveis, x

1 e x

2 têm de satisfazer

Analogamente, as necessidades de sementes de centeio são de 1 kg por saco de SempreVerde e 2 kg por saco de VerdeRápido, enquanto existem apenas 800 kg disponíveis. Logo, a quantidade total ne-cessária de sementes de centeio é x

1 + 2 x

2 e x

1 e x

2 têm de satisfazer

As necessidades de sementes de capim-do-campo são de 1 kg por saco de SempreVerde e 1 kg porsaco de VerdeRápido. Como estão disponíveis 450 kg,

É claro que x1 e x

2 não podem ser negativos, logo também têm de satisfazer

O problema é resumido matematicamente na forma

■

EXEMPLO 2 Uma companhia de reno de petróleo tem duas renarias que produzem três tipos degasolina sem chumbo. A cada dia, a renaria A produz 12.000 galões (aproximadamente 45.360 litros)de gasolina comum, 4.000 galões de gasolina aditivada e 1.000 galões de gasolina super, a um custo deR$3.500,00. A cada dia, a renaria B produz 4.000 galões (aproximadamente 15.120 litros) de gasolinacomum, 4.000 galões de gasolina aditivada e 5.000 galões de gasolina super, a um custo de R$3.000,00.A companhia recebe um pedido de 48.000 galões de gasolina comum, 32.000 galões de aditivada e20.000 de super. Escreva um problema matemático que determina o número de dias que cada renaria

deveria funcionar para produzir as quantidades pedidas com um custo mínimo.

SOLUÇÃO Suponha que a renaria A funcione x1 dias e a renaria B, x2 dias. O custo disso é de3.500 x

1 + 3.000 x

2. O problema é encontrar um esquema de produção ( x

1, x

2) que minimize esse custo

e garanta que as quantidades necessárias serão produzidas.Como a renaria A produz 12.000 galões de gasolina comum cada dia e a renaria B produz 4.000,

o total produzido é 12.000 x1 + 4.000 x

2. O total deve ser no mínimo de 48.000 galões, ou seja,

Analogamente, para a aditivada,

e, para a super,

Como no Exemplo 1, x1 e x2 não podem ser negativos, logo x1 ≥ 0 e x2 ≥ 0.



Otimização 15

(1)

(2)

(3)

O problema pode ser resumido em termos matemáticos como

■

Os exemplos mostram como um problema de programação linear envolve encontrar o máximo(ou mínimo) de uma função linear, chamada função objetivo, sujeita a determinadas restrições ouvínculos lineares. Em muitas situações, as restrições são desigualdades lineares e as variáveis camrestritas a valores não negativos. Veja a seguir uma armação precisa da chamada forma canônica deum problema de programação linear.

DEFINIÇÃO Dados em ℝm, em ℝn e uma matriz m × n A = [aij], o problema de pro-

gramação linear canônico é o seguinte:

Encontrar uma n-upla em ℝn que maximize

sujeita às restrições

Isso pode ser escrito em notação vetor-matricial como

em que uma desigualdade entre dois vetores aplica-se a cada uma das suas coordenadas.Qualquer vetor x que satisfaça (2) e (3) é dito uma solução factível e o conjunto ℱ de todas

as soluções factíveis é chamado conjunto factível. Um vetor x – em ℱ é uma solução ótima se f (x – ) = max

x∈ℱ f (x).

O enunciado canônico do problema não é tão restritivo como pode parecer. Substitua um problemade minimizar uma função h(x) pelo de maximizar a função −h(x). Uma desigualdade da forma

pode ser substituída por

Uma restrição em forma de igualdade, como

pode ser substituída por duas desigualdades,

Duas coisas podem dar errado com um problema de programação linear canônico arbitrário. Se asdesigualdades que fornecem as restrições forem inconsistentes, então ℱ será o conjunto vazio. Se afunção objetivo assumir valores arbitrariamente grandes em ℱ , então o máximo desejado não existirá.

No primeiro caso, o problema é dito não factível; no último caso, o problema é dito ilimitado.

(1)

(2)

(3)



16 CAPÍTULO 9

1O conjunto factível é o conjunto solução de um sistema de desigualdades lineares. Em termos geométricos, isso corresponde à interseção de um número nito de semiespaços (fechados), algumas vezes chamado conjunto poliedral. Intuiti-

vamente, os pontos extremos correspondem a “quinas” ou vértices desse conjunto poliedral.Uma demonstração do Teorema 6 pode ser encontrada em Steven R. Lay, Convex Sets and Their Applications (NovaYork: John Wiley & Sons, 1982; Mineola, NY: Dover Publications, 2007), p. 171.

EXEMPLO 3 O problema

não é factível, já que não existe x tal que x ≤ 3 e x ≥ 4. ■EXEMPLO 4 O problema

é ilimitado. Os valores de 5 x cam de maneira arbitrária grandes, já que x só precisa satisfazer x ≥ 0(e x ≥ −3). ■

Felizmente, só essas duas coisas podem dar errado.

TEOREMA 6 Se o conjunto factível ℱ não for vazio e se a função objetivo for limitada superiormente em ℱ ,

então o problema de programação linear canônico terá pelo menos uma solução ótima. Além disso, pelo menos uma solução ótima será um ponto extremo deℱ .1

O Teorema 6 descreve quando existe uma solução ótima e sugere uma técnica que pode ser usada para encontrá-la, ou seja, calcule a função objetivo em cada um dos pontos extremos deℱ e sele-cione o ponto correspondente ao maior valor. Isso funciona bem em casos simples, como nos dois

próximos exemplos. A abordagem geométrica é limitada a duas ou três dimensões, mas fornece umavisualização importante da natureza do conjunto solução e de como a função objetivo interage como conjunto factível para a identicação dos pontos extremos.

EXEMPLO 5

SOLUÇÃO A Figura 1 mostra o conjunto factível pentagonal sombreado obtido por meio do gráco de

cada uma das desigualdades. (Para simplicar a notação, os pontos nesta seção são denotados por pares outriplas ordenadas.) Existem cinco pontos extremos, correspondendo aos cinco vértices do conjunto factível.Eles podem ser encontrados resolvendo-se os pares apropriados de equações lineares. Por exemplo, o pontoextremo (14, 20) é a solução do sistema linear x

1 + 2 x

2 = 54 e x

2 = 20. A tabela a seguir mostra o valor da

função objetivo em cada ponto extremo. É claro que o máximo é 96, atingido em x1 = 30 e x

2 = 12.

x 1(0, 0) (30, 0)

(30, 12)

(0, 20) (14, 20)

x 2

(0, 0)

(30, 0)

(30, 12)

(14, 20)

(0, 20)

0

60

96

88

60

( x

1, x

2) 2 x

1 + 3 x

2

FIGURA 1



Otimização 17

Outra técnica geométrica que pode ser usada quando o problema envolve duas variáveis é fazer ográco de diversas curvas de nível da função objetivo. Essas são retas paralelas, e a função objetivoé constante em cada uma delas. (Veja a Figura 2.) Os valores da função objetivo f ( x

1, x

2) aumentam

quando ( x1, x

2) se movem da esquerda para a direita. A curva de nível mais à direita que ainda inter -

secta o conjunto factível é a reta que contém o vértice (30, 12). Logo, o ponto (30, 12) fornece o valormáximo de f ( x

1, x

2) no conjunto factível. ■

x 1

f ( x 1, x 2) = 30 f ( x 1, x 2) = 60

f ( x 1, x 2) = 96

x 2

FIGURA 2

EXEMPLO 6

SOLUÇÃO Cada uma das cinco desigualdades determina um “semiespaço” em ℝ3 – um plano juntocom todos os pontos de um dos lados do plano. O conjunto factível desse problema de programação

linear é a interseção desses semiplanos, que é um conjunto convexo no primeiro octante deℝ3

.Quando a primeira igualdade correspondente à primeira desigualdade é escrita, seu gráco é um plano que intersecta cada eixo coordenado a 50 unidades da origem e determina a região triangularequilátera ilustrada na Figura 3. Como (0, 0, 0) satisfaz a desigualdade, ela também é satisfeita portodos os outros pontos “debaixo” do plano. De maneira semelhante, a segunda (des)igualdade deter-mina uma região triangular em outro plano (ilustrado na Figura 4) que ca um pouco mais perto daorigem. Os dois planos se intersectam em uma reta que contém o segmento EB.

A superfície quadrilátera BCDE forma uma parte da fronteira do conjunto factível, já que estáabaixo da região triangular equilátera. Passando do segmento EB, no entanto, os dois planos mudamsuas posições relativas em relação à origem. De modo que a região planar ABE forma outra parteda fronteira do conjunto factível. Os vértices do conjunto factível são os pontos A, B, C , D, E e O (aorigem). Veja a Figura 5, que tem todos os lados do conjunto factível sombreado, com exceção do“topo”. Para encontrar as coordenadas de B, resolva o sistema

Obtenha x2 = 30 e encontre B = (20, 30, 0). Para E , resolva

Obtenha x3 = 10 e encontre E = (40, 0, 10).

Agora que o conjunto factível e seus pontos extremos estão vistos claramente, o próximo passo éexaminar a função objetivo f ( x

1, x

2, x

3) = 2 x

1 + 3 x

2 + 4 x

3. Os conjuntos em que f é constante são planos,

em vez de retas, todos tendo o vetor (2, 3, 4) como vetor normal. Esse vetor normal tem uma direção

diferente dos vetores normais (1, 1, 1) e (1, 2, 4) das duas faces BCDE e ABE . Então os conjuntosde nível de f não são paralelos a nenhuma das faces do conjunto factível. A Figura 6 mostra apenas o

x 1

x 2

x 3

50

050

50

x 1

x 2

x 3

E B

80

20

0 40

FIGURA 3

FIGURA 4



18 CAPÍTULO 9

conjunto factível e uma superfície de nível de f na qual f tem valor 120. Esse plano contém C , E e o ponto (30, 20, 0) na aresta do conjunto factível entre A e B, o que mostra que o vértice B está “acima”desse plano de nível. De fato, f (20, 30, 0) = 130. Logo, a única solução do problema de programaçãolinear está em B = (20, 30, 0). ■

FIGURA 6

PROBLEMAS PRÁTICOS

1. Considere o seguinte problema:

Escreva esse problema na forma de um problema de programação linear canônico: maximizar cT x sujeito a Ax ≤ b e x ≥ 0. Especique A, b e c.

2. Faça o gráco do conjunto factível para o Problema Prático 1.3. Encontre os pontos extremos do conjunto factível no Problema Prático 2.4. Use a resposta do Problema Prático 3 para encontrar a solução do problema de programação linear

no Problema Prático 1.

FIGURA 5



Otimização 19

9.2 EXERCÍCIOS 1. Beth planeja investir um total de R$12.000,00 em fundos mútuos

de investimento, certicados de depósitos bancários (CDBs) e uma poupança que renda juros maiores. Em vista do risco envolvido emfundos mútuos de investimento, ela não quer investir neles mais quea soma dos outros dois investimentos. Ela também quer que a quantia

investida em poupança seja pelo menos metade dos investimentos emCDBs. Os retornos esperados são de 11% nos fundos, 8% nos CDBse 6% na poupança. Quanto Beth deve investir em cada um para obtero maior retorno possível em seus investimentos? Escreva este pro-

blema como um problema de programação linear da seguinte forma:maximizar cT x sujeito a Ax ≤ b e x ≥ 0. Não encontre a solução.

2. Um criador de cachorros decide alimentar seus cães com uma com- binação de duas rações: Potência dos Duendes e Poder Nebuloso.Ele deseja que os cães recebam quatro fatores nutricionais cada mês.

As quantidades desses fatores (a, b, c e d) contidas em um saco decada tipo de ração estão na tabela a seguir, junto com as quantiastotais necessárias.

O custo de cada saco é de R$50,00 para a Potência dos Duendese R$40,00 para o Poder Nebuloso. Quantos sacos de cada tipo deração o criador deve misturar para obter os ingredientes nutricio-nais necessários ao menor custo? Escreva este problema como um

problema de programação linear da seguinte forma: minimizar cT x sujeito a Ax ≥ b e x ≥ 0. Não encontre a solução.

Nos Exercícios de 3 a 6, encontre vetoresb ec e uma matriz A de modo que

cada problema que na forma de um problema de programação linear canô-

nico: maximizar cT x sujeito a Ax ≤ b e x ≥ 0. Não encontre a solução.

Nos Exercícios 7 a 10, resolva os problemas de programação linear.

Nos Exercícios 11 e 12, marque cada armação como Verdadeira ou Fal-sa. Justique cada resposta.

11. a. Em um problema de programação linear canônico, um vetor não

negativo x é uma solução factível se satiszer Ax ≤ b.

b. Um vetor x – é uma solução ótima de um problema de programa-ção linear canônico se f (x – ) for igual ao valor máximo do fun-cional linear f no conjunto factível ℱ .

12. a. Se um problema de programação linear canônico não tiver so-lução ótima, então a função objetivo não é limitada no conjuntofactívelℱ ou ℱ é o conjunto vazio.

b. Se x – for uma solução ótima de um problema de programaçãolinear canônico, então x

– será um ponto extremo do conjuntofactível.

13. Resolva o problema de programação linear no Exemplo 1.

14. Resolva o problema de programação linear no Exemplo 2.

15. A Companhia Benri fabrica dois tipos de aparelhos para cozinha:Produto A e Produto B. O processo de produção é dividido em trêsdepartamentos: fabricação, empacotamento e expedição. As horasde trabalho necessárias para cada operação e as horas disponíveisem cada departamento por dia estão na tabela a seguir.

Suponha que o lucro em cada Produto A seja de R$20,00 e o lucroem cada Produto B seja de R$26,00. Quantos Produtos A e B devem

ser produzidos para maximizar o lucro da companhia?

Os Exercícios 16 a 19 usam a noção de conjunto convexo, estudada naSeção 8.3. Um conjunto S em ℝn é convexo se, para todos os pontos p e q em S , o segmento de reta que liga p a q estiver inteiramente conti-do em S . [Esse segmento é o conjunto de pontos da forma (1 – t )p + t q

para 0 ≤ t ≤ 1.]

16. Seja ℱ o conjunto factível de um problema de programação linear Ax ≤ b com x ≥ 0. Suponha que ℱ não seja vazio. Mostre que ℱ é um conjunto convexo em ℝn. [Sugestão: Considere pontos p

e q em ℱ e seja t tal que 0 ≤ t ≤ 1. Mostre que (1 – t )p + t q estáem ℱ .]

17. Sejam e A desigualdade ax1 + bx

2 ≤ c para

algum número real c pode ser escrita como vT x ≤ c. O conjunto S de todos os x que satisfazem essa desigualdade é chamado um se-miespaço fechado deℝ2. Mostre que S é convexo. [Veja a Sugestão

para o Exercício 16.]

18. O conjunto factível no Exemplo 5 é a interseção de cinco semiespa-

ços fechados. Pelo Exercício 17, esses cinco semiespaços fechadossão convexos. Mostre que a interseção de cinco conjuntos convexos

quaisquer S 1, …, S

5 em ℝn é um conjunto convexo.



20 CAPÍTULO 9

19. Se c estiver emℝn e se f estiver denido emℝn por f (x) = cT x, então

f será chamado um linear funcional e, para qualquer número reald , {x: f (x) = d } será um conjunto de nível de f . (Veja conjuntos de

nível na Figura 2 do Exemplo 5.) Prove que todos os conjuntos denível são convexos.

SOLUÇÕES DOS PROBLEMAS PRÁTICOS

1. A primeira desigualdade está ao contrário, logo a multiplique por −1. Isso nos dá o seguinte problema:

Isso corresponde à forma canônica

2. Para fazer o gráco da desigualdade− x1 + 2 x2 ≤ 8, faça o gráco primeiro da igualdade correspon-dente, − x

1 + 2 x

2 = 8. As interseções com os eixos são fáceis de encontrar: (0, 4) e (−8, 0). A Figura

7 mostra a reta que contém esses pontos. O gráco da desigualdade consiste nessa reta junto com todos os pontos de um dos lados da

reta. Para determinar qual lado, escolha um ponto qualquer fora da reta para ver se suas coorde-nadas satisfazem a desigualdade. Tente a origem (0, 0), por exemplo. A desigualdade

é válida, logo a origem e todos os pontos abaixo da reta satisfazem a desigualdade. Como outroexemplo, substitua as coordenadas do ponto (0, 8) na desigualdade para produzir uma armaçãofalsa:

Assim, (0, 8) e todos os pontos acima da reta não satisfazem a desigualdade. A Figura 7 mos-

tra setas pequenas abaixo do gráco da reta − x1 + 2 x2 = 8 para indicar o lado que deve serincluído.

x 2

x 1

16

8

8 16–8

–8

FIGURA 7 Gráco de − x1 + 2 x2 ≤ 8.

Para a desigualdade

desenhe o gráco de 3 x1 + 2 x

2 = 24 usando as interseções com os eixos (0, 12) e (8, 0) ou dois ou-

tros pontos quaisquer convenientes. Como (0, 0) satisfaz a desigualdade, o conjunto factível estádo lado da reta que contém a origem. A desigualdade x

1 ≥ 0 corresponde ao semiplano à direita

do eixo dos x1, e a desigualdade x

2 ≥ 0 corresponde ao semiplano superior. Todas as retas estão na

Figura 8 e a interseção das regiões é o conjunto factível sombreado.



Otimização 21

x 2

x 1

16

8

8 16–8

–8

FIGURA 8 Gráco do conjunto factível.

3. O conjunto factível tem quatro pontos extremos: 1. A origem: (0, 0) 2. A interseção com o eixo dos x

2 da primeira desigualdade: (0, 4)

3. A interseção com o eixo dos x1 da segunda desigualdade: (8, 0)

4. A interseção das duas desigualdades

Para o quarto ponto extremo, resolva o sistema de equações − x1

+ 2 x2

= 8 e 3 x1

+ 2 x2

= 24 paraobter x1 = 4 e x2 = 6.

4. Para encontrar o valor máximo da função objetivo 2 x1 + x

2, calcule-a em cada um dos pontos ex-

tremos do conjunto factível.

O valor máximo é 16, atingido quando x1 = 8 e x

2 = 0.

9.3 PROGRAMAÇÃO LINEAR – MÉTODO SIMPLEX Problemas de transporte tiveram um papel importante no início da programação linear, incluindo otransporte aéreo de Berlim descrito no Exemplo Introdutório deste capítulo. Eles são até mais impor-tantes hoje em dia. O primeiro exemplo é simples, mas sugere como um problema desse tipo poderiaenvolver centenas, ou até milhares de variáveis e equações.

EXEMPLO 1 Uma companhia de vendas no varejo tem dois armazéns e quatro lojas. Um determinadomodelo de banheira de água quente para ser usada do lado de fora da casa é vendido pelas quatro lojas,e cada uma delas fez um pedido para certa quantidade de banheiras. A matriz vericou que os armazénstêm quantidade suciente de banheiras que podem ser transportadas imediatamente. As distâncias entreos armazéns e as lojas variam e o custo de transporte de uma banheira de um armazém para uma loja

depende da distância. O problema é planejar um itinerário que minimize o custo de transporte. Sejam xij o número de unidades (de banheiras) que serão transportadas do armazém i para a loja j.

Armazém 1 Armazém 2

Loja Lo a

Loja 1 Loja 4

x 11 x 24

x 14

x 21

x 12 x 23

x 22 x 13



22 CAPÍTULO 9

Sejam a1 e a

2 o número de unidades disponíveis nos armazéns 1 e 2, respectivamente, e sejam

r 1, …, r

4 os números de unidades pedidas pelas diversas lojas. Então, os x

ij têm de satisfazer as

equações

e xij ≥ 0 para i = 1, 2 e j = 1, …, 4. Se o custo de transportar uma unidade do armazém i para a loja j

for cij, então o problema será minimizar a função

sujeita às quatro igualdades e dez desigualdades listadas anteriormente. ■

O método simplex, discutido a seguir, pode tratar com facilidade problemas do tamanho do Exemplo

1. Para introduzir o método, no entanto, esta seção focaliza principalmente o problema de programa-ção linear canônico da Seção 9.2, no qual a função objetivo tem de ser maximizada. Eis um esboçodos passos no método simplex.

1. Selecione um ponto extremo x do conjunto factível ℱ .2. Considere todas as arestas de ℱ que têm x como vértice. Se a função f não puder ser aumentada

ao se mover ao longo de qualquer uma dessas arestas, então x será uma solução ótima.3. Se f puder ser aumentada ao se mover ao longo de uma ou mais arestas, siga o caminho corres-

pondente ao aumento máximo e considere o ponto extremo na extremidade oposta da aresta.4. Repita o processo, começando no Passo 2.

Como o valor de f aumenta em cada passo, o caminho não passará pelo mesmo ponto extremo duasvezes. Como existe apenas um número nito de pontos extremos, esse processo irá terminar em umasolução ótima (se existir) em um número nito de passos. Se o problema for ilimitado, o caminho

nalmente alcançará uma aresta ilimitada no Passo 3, ao longo da qual f aumenta sem limite.

Os cinco exemplos a seguir tratam de problemas de programação linear nos quais todas as coor-denadas da m-upla b são positivas:

Aqui c e x estão em ℝn, A é uma matriz m × n e b está em ℝm.O método simplex começa pela transformação de cada desigualdade na restrição em uma igual-

dade. Isto é feito adicionando-se uma nova variável a cada desigualdade. Essas novas variáveis nãofazem parte da solução nal; elas aparecem apenas nos cálculos intermediários.

DEFINIÇÃO Uma variável de folga é uma variável não negativa que é somada ao lado menor de uma desi-gualdade para convertê-la em uma igualdade.

EXEMPLO 2 Transforme a desigualdade

na igualdade

adicionando a variável de folga x3. Note que x

3 = 80 – (5 x

1 + 7 x

2) ≥ 0. ■

Se A é m × n, a soma de m variáveis de folga em Ax ≤ b produz um sistema linear com m equa-ções e m + n variáveis. Uma solução desse sistema é chamada uma solução básica se não mais quem das variáveis forem diferentes de zero. Como na Seção 9.2, uma solução do sistema é dita factívelse cada variável for não negativa. Portanto, em uma solução factível básica, cada variável tem deser não negativa e no máximo m delas podem ser positivas. Geometricamente, essas soluções básicasfactíveis correspondem a pontos extremos do conjunto factível.



Otimização 23

EXEMPLO 3 Encontre uma solução factível básica para o sistema

SOLUÇÃO Adicione variáveis de folga para obter um sistema de três equações:

(1)

O sistema original tinha três desigualdades, de modo que uma solução básica de (1) tem no máximotrês valores não nulos para as variáveis. A solução simples a seguir é chamada uma solução factível

básica associada a (1):

Essa solução corresponde ao ponto extremo 0 no conjunto factível (em ℝ3). ■

É costume se referir às variáveis não nulas x4, x

5 e x

6 no sistema (1) como variáveis básicas ou

dependentes porque cada uma tem um coeciente 1 e ocorre em apenas uma equação.1 As variáveis básicas estão “dentro” da solução de (1). As variáveis x

1, x

2 e x

3 estão “fora” da solução. Em um pro-

blema de programação linear, essa solução particular provavelmente não seria ótima, já que só asvariáveis de folga são diferentes de zero.

Um procedimento padrão no método simplex é mudar o papel de uma variável em uma solução.Por exemplo, embora x

2 esteja fora da solução em (1), ela pode ser trazida para “dentro” por meio de

operações elementares. O objetivo é pivotar no elemento x2 na terceira equação de (1) para criar um

novo sistema no qual x2 só aparece na terceira equação.2

Primeiro, divida a terceira equação pelo coeciente de x2 para obter uma nova terceira equação:

Segundo, some múltiplos dessa nova equação às equações 1 e 2 em (1) para eliminar x2. Isso produz

o sistema

A solução básica associada a esse novo sistema é

A variável x2 aparece agora na solução e a variável x

6 saiu. Infelizmente, essa solução básica não é

factível, já que x4 < 0. Esse problema foi causado por uma escolha inconveniente da equação do pivô.

O próximo parágrafo mostra como evitar esse problema.Em geral, considere o problema

e suponha que o próximo passo seja introduzir a variável xk na solução usando a equação p para pivo-

tar no elemento a pk

xk . A solução básica correspondente ao sistema resultante será factível se as duas

condições a seguir forem satisfeitas:

1. O coeciente a pk

de xk tem de ser positivo. (Quando a p-ésima equação for dividida por a

pk , o novo

termo b p tem de ser positivo.)

1Essa terminologia generaliza a usada na Seção 1.2, na qual variáveis básicas também tinham de corresponder a posições pivôs em uma matriz em forma escalonada. Aqui o objetivo não é resolver para as variáveis dependentes em termos das va-riáveis livres, mas sim obter uma solução particular do sistema quando as variáveis independentes (livres) são nulas.2“Pivotar” em um termo particular aqui signica transformar seu coeciente em 1 e, depois, usá-lo para eliminar o termocorrespondente em todas as outras equações, não apenas nas equações a seguir, como foi feito na Seção 1.2.



24 CAPÍTULO 9

2. A razão b p/a

pk tem de ser a menor entre todas as razões b

i/a

ik para as quais a

ik > 0. (Isso irá garantir

que, quando a p-ésima equação for usada para eliminar xk da i-ésima equação, o termo resultante

bi será positivo.)

EXEMPLO 4 Determine qual linha usar como pivô para introduzir x2 na solução no Exemplo 3.

SOLUÇÃO Calcule as razões bi/a

i2:

Como a primeira razão é a menor, use a primeira equação para pivotar em x2. Isso produz o sis-

tema

Agora, a solução factível básica é

■

Um formato matricial pode simplicar muitos cálculos desse tipo. Por exemplo, o sistema (1) noExemplo 3 é representado pela matriz aumentada

As variáveis estão sendo usadas para nomear as colunas, com as variáveis de folga coloridas. Lembre-se de que a solução factível básica associada a essa matriz é

O círculo em volta do 3 na coluna x2 indica que esse elemento será usado como pivô para introduzir

x2 na solução. (Os cálculos das razões no Exemplo 4 identicam esse elemento como o pivô apropria-

do.) Complete o escalonamento na coluna 2 para produzir a matriz nova que corresponde ao sistemanovo no Exemplo 4:

Como no Exemplo 4, a solução factível básica é

A discussão precedente preparou o caminho para uma demonstração completa do método simplex baseada nas restrições no Exemplo 3. Em cada passo, a função objetivo no Exemplo 5 indicará a es-colha da variável para incluir na solução do sistema.

EXEMPLO 5

SOLUÇÃO Primeiro, adicione as variáveis de folga, como antes. Depois, transforme a função objetivo25 x

1 + 33 x

2 + 18 x

3 em uma equação, introduzindo uma nova variável M dada por M = 25 x

1 + 33 x

2 +

18 x3. Agora, o objetivo é maximizar a variável M , na qual M satisfaz a equação



Otimização 25

O problema original pode ser enunciado agora da seguinte maneira: Entre todas as soluções do sis-tema de equações

encontre uma solução com x j ≥ 0 ( j = 1, …, 6) e para a qual M é o maior possível.A matriz aumentada para esse novo sistema é chamada quadro simplex inicial. Ele é escrito com

duas linhas na matriz:

A reta horizontal acima da última linha isola a equação correspondente à função objetivo. Essa últi-ma linha tem um papel especial no que segue. (A última linha só é usada para decidir qual variávelserá introduzida na solução. As posições de pivô nunca são escolhidas na última linha.) Os nomesdas colunas associadas às variáveis de folga estão coloridas para lembrar que, ao nal dos cálculos,só as variáveis originais fazem parte da solução nal do problema.

Olhe as linhas de 1 a 3 no quadro anterior para encontrar a solução factível básica. As colunas

da matriz identidade 3 × 3 nessas três linhas identifca as variáveis básicas – a saber, x4, x

5 e x

6. A

solução básica é

Essa solução não é ótima, no entanto, já que só as variáveis de folga são diferentes de zero. A últimalinha implica

O valor de M aumenta quando qualquer uma das variáveis x1, x

2 ou x

3 aumenta. Como o coecien-

te de x2 é o maior dos três coecientes, introduzir x

2 na solução causará o aumento maior possível

em M .Para introduzir x

2 na solução, siga o procedimento de pivô já esboçado. No quadro anterior, com-

pare as razões bi/ai2 para cada linha, exceto a última. Elas são 60/3, 46/1 e 50/2. A menor é 60/3, logoo pivô deve ser o elemento 3 dentro do círculo na primeira linha.

O resultado da operação de pivô é

(2)

Agora, as colunas da matriz identidade 3 × 3 estão nas colunas 2, 5 e 6 do quadro. Logo, a soluçãofactível básica é

Então M aumentou de 0 para 660. Para ver se M pode aumentar ainda mais, olhe a última linha doquadro e resolva a equação para M :

(3)

Como cada uma das variáveis x j é não negativa, o valor de M só aumentará se x

1 aumentar (a partir

de 0). (Como os coecientes de x3 e x

4 são ambos negativos neste ponto, aumentar um deles diminui-



26 CAPÍTULO 9

ria M .) Então precisamos introduzir x1 na solução. Compare as razões (da coluna aumentada com a

coluna 1):

A segunda razão é a menor, logo o próximo pivô deve ser o elemento 7 –

3 na linha 2.

Depois do pivô, o quadro resultante é

A solução factível básica correspondente é

A última linha mostra que

Os coecientes negativos das variáveis aqui mostram que M não pode ser maior que (pois x3, x

4

e x5 são não negativos), de modo que a solução é ótima. O valor máximo de 25 x

1 + 33 x

2 + 18 x

3 é

e esse máximo ocorre quando x1 = , x

2 = e x

3 = 0. A variável x

3 é zero porque, na solução óti-

ma, x3 é uma variável livre, não uma variável básica. Note que o valor de x

6 não faz parte da solução

do problema original, pois x6 é uma variável de folga. O fato de que as variáveis de folga x

4 e x

5 são

nulas signica que as duas desigualdades listadas no início desse exemplo são ambas igualdades nosvalores ótimos de x1, x

2 e x

3. ■

Vale a pena reler o Exemplo 5 cuidadosamente diversas vezes. Em particular, note que um elementonegativo na última linha de qualquer coluna x

j se tornará um coeciente positivo quando aquela equação

for resolvida para M , indicando que M ainda não atingiu seu máximo. Veja o quadro (2) e a equação (3).Resumindo, eis o método simplex para resolver um problema de programação linear canônico

quando todos os coecientes do vetor b são positivos.

O ALGORITMO SIMPLEX PARA UM PROBLEMA DE PROGRAMAÇÃO LINEARCANÔNICO

1. Transforme as restrições dadas por desigualdades em igualdades adicionando variáveis de folga.Seja M a variável igual à função objetivo e escreva, depois das equações das restrições, uma

equação da forma− (função objetivo) + M = 0.

2. Monte o quadro simplex inicial. As variáveis de folga (e M ) fornecem a solução factível básicainicial.

3. Verique se a solução é ótima analisando a última linha do quadro. Se todos os elementos à esquerdada linha vertical forem não negativos, então a solução será ótima. Se alguns forem negativos, entãoescolha a variável x

k para a qual o elemento na última linha será o mais negativo possível.3

3O objetivo do Passo 3 é produzir o maior aumento possível no valor de M . Isso só acontece quando uma variável xk

satisfaz essas condições. Suponha, entretanto, que o elemento mais negativo na última linha apareça em duas colunas j e k . O Passo 3 diz que x

j ou x

k deve ser introduzido na solução e isto está correto. Em algumas situações, pode-se evitar

alguns cálculos usando primeiro o Passo 4 para calcular a “menor razão” para ambas as colunas j e k e, depois, escolhera coluna para a qual essa “menor razão” é maior. Esta situação vai aparecer na Seção 9.4.



Otimização 27

4. Introduza a variável xk na solução. Faça isso pivotando no elemento positivo a

pk para o qual a

razão não negativa bi/a

ik é menor. A nova solução factível básica inclui um valor aumentado

para M .5. Repita o processo, começando no Passo 3, até todos os elementos na última linha carem não

negativos.

Duas coisas podem dar errado no algoritmo simplex. No Passo 4, pode haver um elemento negati-vo na última linha na coluna xk , mas não haver elemento positivo a

ik acima dele. Nesse caso, não será

possível encontrar um pivô para introduzir xk na solução. Isso corresponde ao caso em que a função

objetivo é ilimitada e não existe solução ótima.O segundo problema em potencial também ocorre no Passo 4. A menor razão b

i/aik pode ocorrer emmais de uma linha. Quando isso acontece, o próximo quadro terá pelo menos uma variável básica iguala zero e, em quadros subsequentes, o valor de M pode permanecer constante. Na teoria, é possível ocor-rer uma sequência innita de pivôs que não levam a uma solução ótima. Tal fenômeno é denominadociclismo. Felizmente, o ciclismo só ocorre de forma rara em aplicações práticas. Na maioria dos casos,

pode-se escolher com arbitrariedade qualquer linha com razão mínima como linha do pivô.

EXEMPLO 6 Uma loja de alimentos naturais vende duas misturas diferentes de grãos. Uma caixada primeira mistura contém 1 kg de castanhas de caju e 1 kg de amendoins. Uma caixa da segundamistura contém 1 kg de avelãs e 2 kg de amendoins. A loja tem disponíveis 30 kg de castanhas de caju,

20 kg de avelãs e 54 kg de amendoins. Suponha que o lucro em cada caixa da primeira mistura seja deR$2,00 e, em cada caixa da segunda mistura, seja de R$3,00. Se a loja puder vender todas as caixas

produzidas das misturas, quantas caixas de cada mistura ela deve fazer para maximizar o lucro?

SOLUÇÃO Sejam x1 o número de caixas produzidas da primeira mistura e x

2 o número de caixas da

segunda mistura. O problema pode ser expresso matematicamente como

Esse é o mesmo problema resolvido de forma gráca no Exemplo 5 da Seção 9.2. Ao ser resolvido pelo método simplex, a solução factível básica de cada quadro corresponde a um ponto extremo da

região factível. Veja a Figura 1.

x 1

(0, 20)

(0, 0) (30, 0)

(30, 12)

x 2

(14, 20)

FIGURA 1

Para construir o quadro inicial, adicione variáveis de folga e escreva a função objetivo como uma

equação. O problema agora é encontrar uma solução não negativa do sistema

para a qual M é máximo. O quadro simplex inicial é



28 CAPÍTULO 9

A solução factível básica, na qual x1, x

2, M e 0 são iguais a 0, corresponde ao ponto extremo (0, 0) da

região factível na Figura 1. Na última linha do quadro, o elemento mais negativo é −3, logo o pivôdeve ser um elemento da coluna x

2. As razões 20/1 e 54/2 mostram que o pivô deve ser o elemento

igual a 1 na coluna x2:

Depois da operação de pivô, o quadro ca

Agora, a solução factível básica é

A nova solução está no ponto extremo ( x1, x2) = (0, 20) na Figura 1. O elemento igual a −2 na últimalinha do quadro mostra que o próximo pivô está na primeira coluna, o que produz

Dessa vez, x1 = 14 e x

2 = 20, de modo que a solução se moveu para o ponto extremo (14, 20) na Fi-

gura 1, e a função objetivo aumentou de 60 para 88. Finalmente, o elemento −1 na última linha mos-tra que o próximo pivô está na quarta coluna. Usando o elemento igual a 2 na primeira como pivô,

produz o quadro nal:

Como todos os elementos na última linha são não negativos, a solução agora é ótima, com x1 = 30

e x2 = 12, correspondente ao ponto extremo (30, 12). O lucro máximo é de R$96,00, obtido quando

são produzidas 30 caixas da primeira mistura e 12 caixas da segunda. Note que, embora x4 faça parte

da solução factível básica para esse quadro nal, seu valor não está incluído na solução do problemaoriginal porque x

4 é uma variável de folga. ■

Problemas de MinimizaçãoAté agora, cada problema canônico de maximização envolveu um vetorb cujas coordenadas eram

positivas. O que acontece quando uma das coordenadas de b é nula ou negativa? E os problemas deminimização?

Se algumas das coordenadas de b forem nulas, é possível que ocorra ciclismo e o método simplexnão consiga determinar uma solução ótima. Como já mencionado, no entanto, isso não costuma ocor-rer em aplicações práticas, de modo que a presença de elementos nulos na coluna da extrema direitararamente causa problemas na operação do método simplex.

O caso em que uma das coordenadas de b é negativa pode ocorrer na prática e precisa ser tratadaem separado. A diculdade é que todos os termos b

i têm de ser não negativos para que as variáveis

de folga forneçam uma solução factível básica inicial. Um modo de transformar um bi negativo em

x

1(0, 0)

x 2

x 1

(0, 20)

x 2

x 1

x 2

(14, 20)

x 1

(30, 12)

x 2



Otimização 29

positivo é multiplicar a desigualdade por −1 (antes de introduzir as variáveis de folga). Mas isso in-verteria a desigualdade. Por exemplo,

transformar-se-ia em

Portanto, um termo bi negativo causaria o mesmo problema que uma desigualdade invertida. Comodesigualdades invertidas ocorrem com frequência em problemas de minimização, o exemplo a seguirdiscute esse caso.

EXEMPLO 7

SOLUÇÃO O mínimo de f ( x1, x2) em um conjunto ocorre no mesmo ponto que o máximo de− f ( x

1, x

2) no mesmo conjunto. No entanto, para se usar o algoritmo simplex, a descrição canônica

do conjunto factível tem de usar desigualdades do tipo ≤. Então, a primeira desigualdade anteriortem de ser invertida. A segunda desigualdade já está na forma canônica. Logo, o problema original

é equivalente a

Para resolver esse problema, seja M = − x1 – 2 x

2 e adicione variáveis de folga às desigualdades, como

antes. Isso cria o sistema linear

Para encontrar uma solução não negativa desse sistema para o qual M é máximo, construa o quadrosimplex inicial

A solução básica correspondente é

No entanto, como x3 é negativo, essa solução básica não é factível. Antes que o método simplex padrão

possa começar, cada termo na coluna aumentada acima da reta horizontal tem de ser um número não

negativo. Isso pode ser feito pivotando no elemento negativo.Para substituir um elemento negativo b

i por um número positivo, encontre outro elemento nega-

tivo na mesma linha. (Se todos os outros elementos na mesma linha forem não negativos, então o problema não terá solução factível.) Esse elemento negativo está na coluna correspondente à variável

que deve ser introduzida agora na solução. Neste exemplo, as duas primeiras colunas têm elementosnegativos, de modo que x1 ou x

2 deve ser introduzido na solução.

Para introduzir x2 na solução, por exemplo, selecione como pivô o elementoa

i2 na segunda

coluna, para o qual a razão bi/a

i2 é o menor número não negativo. (A razão é positiva quando am-

bos os bi e a

i2 são negativos.) Neste caso, só a razão (−14)/(−1) é não negativa, logo o elemento

−1 na primeira linha tem de ser o pivô. Depois da operação de pivô na segunda coluna, o quadroresultante é



30 CAPÍTULO 9

Agora, cada elemento na coluna aumentada (com exceção do elemento na última linha) é positivo, eo método simplex pode começar. (Algumas vezes, é preciso pivotar mais de uma vez para tornar cadaum desses termos não negativos. Veja o Exercício 15.) O próximo quadro já é ótimo:

O valor máximo factível de − x1 – 2 x

2 é −20, quando x

1 = 8 e x

2 = 6. Logo, o valor mínimo de x

1 + 2 x

2

é 20. ■

O último exemplo usa a técnica do Exemplo 7, mas o quadro simplex precisa de mais processa-mento antes do início da operação canônica de máximo.

EXEMPLO 8 Minimizar 5 x1 + 3 x2

SOLUÇÃO Converta o problema em um problema de máximo fazendo M = −5 x1 – 3 x

2 e invertendo

as três desigualdades de restrições principais:

Adicione variáveis de folga não negativas e construa o quadro simplex inicial:

Antes de começar o processo simplex de máximo, os três primeiros elementos na coluna aumentada

têm de car não negativos (para tornar a solução factível). Vai ajudar pivotar em um elemento nega-tivo para introduzir x

1 ou x

2 na solução. Tentativa e erro vão funcionar, mas o método mais rápido é

calcular as razões usuais bi/a

ij para todos os elementos negativos nas linhas de 1 a 3 e nas colunas 1 e

2. Escolha como pivô o elemento com a maior razão. Isso fará com que todos os elementos aumenta-dos mudem de sinal (já que a operação de pivô irá somar múltipos da linha do pivô às outras linhas).

Neste exemplo, o pivô deve ser a31

e o novo quadro é

Agora se pode usar o algoritmo simplex para o máximo. O elemento igual a −17 na última linha mos-tra que x2 deve ser introduzido na solução. A menor das razões entre 52/15, 6/2 e 16/4 é 6/2. Um pivô

em 2 na segunda coluna produz



Otimização 31

O elemento – 7 – 2 na última linha mostra que x

5 tem de ser introduzido na solução. O pivô é 7 –

2 na quinta

coluna e o novo quadro (nal) é

A solução ocorre quando x1 = 2 (da linha 3), x

2 = 4 e M =−22, de modo que o valor mínimo da função

objetivo original é 22. ■

O “Simplex” no Algoritmo Simplex

A abordagem geométrica na Seção 9.2 considerou as linhas de uma matriz A m × 2 fazendo o grácode cada desigualdade como um semiespaço em ℝ2 e vendo o conjunto solução como a interseção desemiespaços. Em problemas de dimensão maior, o conjunto solução é, novamente, uma interseçãode semiespaços, mas essa visão geométrica não leva a um algoritmo eciente para encontrar a solu-ção ótima.

O algoritmo simplex considera as colunas de A, em vez das linhas. Suponha que A seja uma ma-triz m × n e denote suas colunas por a1, …, a

n. A inclusão de m variáveis de folga cria um sistema

com n + m equações da forma

em que x1, …, x

n+m são não negativas e {e

1, …, e

m} é a base canônica para ℝm. A solução factível bá-

sica inicial é obtida quando x1, …, x

n são nulos e b

1e1 + … + b

mem = b. Se s = b

1 + … + b

m, então a

equação

mostrará que b pertence ao conjunto conhecido como o simplex gerado por 0, se1, …, se

m. Para sim-

plicar, dizemos que “b pertence ao simplex de dimensão m determinado por e1, …, em“. Esse é o

primeiro simplex no algoritmo simplex.4

Em geral, se v1, …, vm formarem uma base para ℝm

, selecionados das colunas da matriz P = [a1 … an v

1 … v

m] e se b for uma combinação linear desses vetores com coecientes não negativos, então b

pertencerá ao simplex de dimensão m determinado por 0, v1, …, vm

. Uma solução factível básica do problema de programação linear corresponde a uma base particular formada pelas colunas de P . Oalgoritmo simplex muda essa base e, portanto, o simplex correspondente que contém b, uma colunade cada vez. As diversas razões calculadas pelo algoritmo fornecem a escolha das colunas. Como asoperações elementares não mudam as relações de dependência linear entre as colunas, cada soluçãofactível básica diz como construir b das colunas correspondentes de P .

PROBLEMA PRÁTICO

Use o método simplex para resolver o problema de programação linear a seguir:

4Se v1, …, v

m forem vetores linearmente independentes em ℝm, o fecho convexo do conjunto {0, v

1, …, v

m} será

um simplex S de dimensão m. (Veja a Seção 8.5.) Um vetor típico em S é da forma c00 + c

1v

1 + … + c

mv

m, em que

os coecientes são não negativos e sua soma é igual a um. (Equivalentemente, vetores em S são da forma c1v

1 +

… + cmv

m, na qual os coecientes são não negativos e sua soma é, no máximo, um.) Qualquer conjunto formado

pela translação de tal conjunto S também é chamado simplex de dimensão m, mas tais conjuntos não aparecem noalgoritmo simplex.



32 CAPÍTULO 9

9.3 EXERCÍCIOS Nos Exercícios 1 e 2, escreva o quadro simplex inicial para o problemade programação linear dado.

Para cada quadro simplex nos Exercícios 3 a 6, faça o seguinte:

a. Determine qual variável deve ser introduzida na solução.

b. Calcule o próximo quadro.

c. Identique a solução factível básica correspondente ao quadro noitem (b).

d. Determine se a resposta no item (c) é ótima.

Os Exercícios 7 e 8 estão relacionados ao problema de programação li-near canônico com uma matriz de coecientes A m × n na desigualdadede restrição Ax ≤ b. Marque cada armação como Verdadeira ou Falsa e

justique cada resposta.

7. a. Uma variável de folga é usada para transformar uma igualdadeem uma desigualdade.

b. Uma solução é factível se cada variável for não negativa.

c. Se uma das coordenadas do vetor b for negativa, então o problema não será factível.

8. a. Uma solução é dita básica se m ou menos de suas variáveis fo-rem nulas.

b. As soluções factíveis básicas correspondem a pontos extremosda região factível.

c. O último elemento na coluna da extrema direita, em um quadrosimplex, fornece o valor máximo da função objetivo.

Resolva os Exercícios de 9 a 14 usando o método simplex.

15. Resolva o Exemplo 7 introduzindo x1 na solução (em vez de x

2) no

quadro inicial.

16. Use o método simplex para resolver o problema de programaçãolinear no Exercício 1 da Seção 9.2.

17. Use o método simplex para resolver o problema de programaçãolinear no Exercício 15 da Seção 9.2.

18. Use o método simplex para resolver o problema de programaçãolinear no Exemplo 1 da Seção 9.2.

SOLUÇÃO DO PROBLEMA PRÁTICO

Introduza variáveis de folga x3 e x

4 e escreva o problema como



34 CAPÍTULO 9

Suponha que o problema dual anterior possa ser escrito como um problema de maximização ca-nônico:

Então o dual deste problema é

Em forma canônica, esse problema de minimização é equivalente a

Se w for substituído por x, este é precisamente o problema primitivo. Portanto, o dual do problemadual é o problema primitivo original.

O Teorema 7 a seguir é um resultado fundamental de programação linear. Como no caso doTeorema Minimax, a demonstração depende de certas propriedades de conjuntos convexos e hi-

perplanos.2

TEOREMA 7 Teorema de Dualidade

Seja P um problema de programação linear (primitivo) com conjunto factível ℱ e seja P * o problema dual com conjunto factívelℱ *.a. Se ambosℱ eℱ * forem não vazios, então P e P * terão soluções ótimas x – e y – , respectivamente,

com f (x – ) = g (y – ). b. Se um dos problemas P ou P * tiverem soluções ótimas x – ou y – , respectivamente, então o outro

também terá e f (x – ) = g (y – ).

EXEMPLO 2 Escreva e resolva o dual do problema no Exemplo 5 da Seção 9.2.

SOLUÇÃO O problema original é

Os cálculos no Exemplo 5 da Seção 9.2 mostraram que a solução ótima desse problema écom f (x – ) = 96. O problema dual é

O método simplex poderia ser usado aqui, mas o método geométrico da Seção 9.2 não é muito difí-

cil. Grácos das restrições (Figura 1) revelam que ℱ * tem três pontos extremos e que é a

solução ótima. De fato, g (y – ) = 30(1 – 2) + 20(0) + 54(3 –

2) = 96, como esperado. ■

2Se a equação Ax = b tiver solução não negativa, então os conjuntos {b} e S = {z ∈ℝm: z = Ax, x ≥ 0} serão disjun-tos. Não é difícil mostrar que S é um conjunto convexo fechado, logo o Teorema 12 no Capítulo 8 implica existir umhiperplano que separa estritamente {b} e S . Esse hiperplano tem um papel crucial na demonstração. Para os detalhes,

veja Steven R. Lay, Convex Sets and Their Applications (Nova York: John Wiley & Sons, 1982; Mineola, NY: DoverPublications, 2007), pp. 174-178.



Otimização 35

FIGURA 1 O mínimo de g ( y1, y2, y3) = 30 y1 + 20 y2 + 54 y3.

O Exemplo 2 ilustra outra propriedade importante da dualidade e do método simplex. Lembreque esse mesmo problema de maximização foi resolvido no Exemplo 6 da Seção 9.3 pelo métodosimplex. O quadro nal é

Note que a solução ótima do problema dual aparece na última linha. As variáveis x3, x

4 e x

5 são as

variáveis de folga para a primeira, segunda e terceira equações, respectivamente. O último elemento

em cada uma dessas colunas fornece a solução ótima do problema dual. Isso não é uma

coincidência, como mostra o próximo teorema.

TEOREMA 7 Teorema de Dualidade (continuação)

Seja P um problema de programação linear (primitivo) e P * seu problema dual. Suponha que P (ou P *) tenha uma solução ótima.

c. Se P ou P * for resolvido pelo método simplex, então a solução de seu dual estará na últimalinha do quadro nal nas colunas associadas com as variáveis de folga.

EXEMPLO 3 Escreva e resolva o dual do problema no Exemplo 5 da Seção 9.3.

SOLUÇÃO O problema primitivo P é

O problema dual P * é



36 CAPÍTULO 9

Foi encontrado que o quadro nal para a solução do problema primitivo é

As variáveis de folga são x4, x

5 e x

6. Elas fornecem a solução ótima do problema dual P *. Assim,

Note que o valor ótimo da função objetivo no problema dual é

o que está de acordo com o valor ótimo da função objetivo no problema primitivo. ■

As variáveis no problema dual têm interpretações econômicas úteis. Por exemplo, considereo problema da mistura de grãos estudado no Exemplo 5 da Seção 9.2 e no Exemplo 6 da Seção9.3:

Lembre que x1 é o número de caixas da primeira mistura e x

2 é o número de caixas da segunda. O

Exemplo 2 mostrou o problema dual:

Se x – e y – forem soluções ótimas, então, pelo Teorema de Dualidade, o lucro máximo f (x – ) satisfará aequação

Suponha, por exemplo, que a quantidade de castanhas de caju disponíveis aumentou de 30 para30 + h quilos. Então o lucro aumentaria de h y –

1. Analogamente, se a quantidade de castanhas de caju

diminuísse de h quilos, o lucro diminuiria de h y – 1. Logo, y –

1 representa o valor (por quilo) do aumen-

to ou diminuição da quantidade de castanhas de caju disponíveis. Isso é chamado, em geral,valor

marginal das castanhas de caju. De maneira similar, y – 2 e y –

3 são os valores marginais das avelãs e dos

amendoins, respectivamente. Esses valores indicam o quanto a companhia estaria disposta a pagar por suprimentos adicionais dos diversos grãos.2

EXEMPLO 4 O quadro simplex nal para o problema da mistura dos grãos encontrado (no Exemplo6 da Seção 9.3) foi

2Os outros elementos no quadro nal também têm interpretações econômicas. Veja Saul I. Gass, Linear Programming Methods and Applications, 5ª ed. (Danvers, MA: Boyd & Fraser Publishing, 1985), pp. 173-177. Veja, também, Golds-

tein, Schneider e Siegel, Finite Mathematics and Its Applications, 6ª ed. (Upper Saddle River, NJ: Prentice Hall, 1998), pp. 166-185.



Otimização 37

de modo que a solução ótima do problema dual é Logo, o valor marginal das castanhas

de caju é 1 – 2, o valor marginal das avelãs é 0 e o valor marginal dos amendoins é 3 –

2.

Note que o planejamento da produção ótima usa apenas 12 dos 20 kg de avelãs. (Isso

corresponde ao fato de que a variável de folga x4 para a restrição das avelãs tem valor 8 no quadro

nal.) Isso signica que nem todas as avelãs estão sendo usadas, de modo que não há aumento no

lucro se a quantidade de avelãs for aumentada. Ou seja, seu valor marginal é nulo. ■

Programação Linear e Jogos Matriciais

Seja A uma matriz de pagamentos m × n, como na Seção 9.1, e suponha, primeiro, que todos os ele-mentos de A sejam positivos. Sejam u em ℝm e v em ℝn vetores com todas as coordenadas iguais aum e considere o seguinte problema de programação linear P e seu dual P *. (Note que os papéis dex e de y estão trocados, com x em ℝm e y em ℝn.)

O problema primitivo é factível, já que y = 0 satisfaz as restrições. O problema dual P * é factível, já que todos os elementos de AT são positivos e v é um vetor com todas as coordenadas iguais a 1.Pelo Teorema de Dualidade, existem soluções ótimas y – e x – tais que vT y – = uT x – . Dena

Como os elementos em A e em u são positivos, a desigualdade Ay ≤ u tem uma solução não nula y com y ≥ 0. Em consequência, a solução λ do problema primitivo é positiva. Sejam

Pode-se mostrar (Exercícios 23) que y é a estratégia mista (não pura) ótima para o jogador coluna C e x é a estratégia mista ótima para o jogador linha L. Além disso, o valor do jogo é 1/λ .

Finalmente, se a matriz de pagamentos A tiver alguns elementos que não são positivos, some umnúmero xo, digamos k , a cada elemento para tornar todos os elementos positivos. Isso não vai mu-

dar as estratégias de misturas ótimas e somará uma quantidade k ao valor do jogo. [Veja o Exercício25(b) na Seção 9.1.]

EXEMPLO 5 Resolva o jogo cuja matriz de pagamentos é

SOLUÇÃO Para produzir uma matriz B com todos os elementos positivos, some 3 a cada ele-mento:

A estratégia ótima para o jogador coluna C pode ser encontrada resolvendo-se o problema de pro-gramação linear

Introduza variáveis de folga y4 e y5, seja M a função objetivo e construa o quadro simplexinicial:



38 CAPÍTULO 9

Os três elementos iguais a −1 na última linha indicam que qualquer das colunas de 1 a 3 pode ser a primeira coluna pivô. Escolha a coluna 1 e calcule as razõesb

i/a

i1. Para introduzir a variável y

1 na

solução, use o elemento 6 na segunda linha como pivô:

Na última linha, o terceiro elemento é o mais negativo, logo introduza y3 na solução. As razões b

i/a

i3 são

Como a primeira razão é menor, use na primeira linha como pivô.

A solução ótima do problema primitivo é

A estratégia ótima mista correspondente para C é

A solução ótima do problema dual vem dos elementos na última linha nas colunas das variáveis defolga:

o que mostra que a estratégia mista ótima para L é

O valor do jogo com matriz de pagamento B é v = de modo que o valor do jogo original A é

− 3 = 6 – 7. ■

Embora jogos matriciais sejam resolvidos, em geral, por meio de programação linear, é interes-sante observar que um problema de programação linear pode ser reduzido a um jogo matricial. Seo problema tiver uma solução ótima, então essa solução será reetida na solução do jogo matricial.Suponha que o problema seja maximizar a função cT x sujeita às restrições Ax ≤ b e x ≥ 0, em que A é uma matriz m × n com m ≤ n. Sejam

e suponha que M represente um jogo matricial e s seja uma estratégia coluna ótima para M . A matriz M é uma matriz (n + m + 1) × (n + m + 1) antissimétrica, ou seja, M T = − M . Pode-se mostrar que,neste caso, a estratégia ótima para as linhas é igual à estratégia ótima para as colunas, o valor do jogoé 0 e o valor máximo das coordenadas do vetor M s é 0. Note que

Logo, Como a estratégia coluna s é um vetor probabilidade, z ≥ 0. Pode-se mostrar que, se z > 0, então / z será uma solução ótima para o problema (de maximização)

primitivo para Ax ≤ b e / z será uma solução ótima para o problema dual para AT y ≥ c. Além disso,se z = 0, os problemas primitivo e dual não têm soluções ótimas.



Otimização 39

Concluindo, o método simplex é uma ferramenta poderosa para resolver problemas de programa-ção linear. Como se segue um procedimento xo, o método é bastante adequado para a utilização decomputadores para os cálculos tediosos envolvidos. O algoritmo apresentado aqui não é ótimo parautilização computacional, mas muitos programas para computadores implementam variações do mé-todo simplex e alguns até buscam soluções inteiras. Métodos novos, desenvolvidos há poucos anos,usam atalhos através das regiões factíveis, em vez de ir de ponto extremo a ponto extremo. Eles sãoum pouco mais rápidos em determinadas situações (tipicamente quando envolvem milhares de variá-

veis e restrições), mas o método simplex ainda é a abordagem mais utilizada.

PROBLEMAS PRÁTICOS

As questões a seguir estão relacionadas à companhia Pista Esperta de sementes de grama do Exemplo 1na Seção 9.2. O problema de programação linear canônico pode ser enunciado da seguinte maneira:

1. Enuncie o problema dual.

2. Encontre a solução ótima do problema dual dado que o quadro nal no método simplex para aresolução do problema primitivo seja

3. Quais são os valores marginais para a festuca, o centeio e o capim-do-campo na solução ótima?

9.4 EXERCÍCIOS

Nos Exercícios 1 a 4, enuncie o dual do problema de programação li-near dado.

1. Exercício 9 na Seção 9.3.




Nos Exercícios de 5 a 8, use o quadro nal na solução do exercício dado para resolver o problema dual.





Os Exercícios 9 e 10 estão relacionados ao problema primitivo de pro-gramação linear de encontrar x emℝn que maximiza a função f (x) = cT x sujeita a Ax ≤ b e x ≥ 0. Marque cada armação como Verdadeira ou Falsa

e justique cada resposta.

9. a O problema dual é minimizar y emℝm sujeito a Ay ≥ c e y ≥ 0.

b. Se ambos os problemas, primitivo e dual, forem factíveis, entãoambos terão solução ótima.

c. Se x – for uma solução ótima para o problema primitivo e se y foruma solução factível do problema dual tal que g (y) = f (x

– ), então y

será uma solução ótima do problema dual.

d. Se uma variável de folga estiver em uma solução ótima, entãoo valor marginal do item correspondente à sua equação será positivo.

10. a. O dual do problema dual é o problema primitivo. b. Se um dos problemas, primitivo ou dual, tiver solução ótima,

então ambos terão.

c. Se o problema primitivo tiver uma solução ótima, então o qua-dro nal no método simplex também fornecerá a solução ótima do problema dual.

d. Quando um problema de programação linear e seu dual são usa-

dos para resolver um jogo matricial, então os vetores u e v sãovetores unitários.

Algumas vezes, um problema de minimização só tem desigualdades dotipo “≥“. Nesse caso, substitua o problema pelo seu dual. (Multiplicar asdesigualdades originais por −1 para invertê-las não vai funcionar, pois asolução básica do quadro simplex inicial não será factível.) Nos Exercí-cios de 11 a 14, use o método simplex para resolver o problema dual e, a

partir desta solução, resolva o problema original (o dual do dual).

13. Resolva o Exercício 2 na Seção 9.2.

14. Resolva o Exemplo 2 na Seção 9.2.



40 CAPÍTULO 9

Os Exercícios 15 e 16 se referem ao Exercício 15 na Seção 9.2, que foiresolvido usando o método simplex no Exercício 17 da Seção 9.3. Use oquadro nal desse último exercício para responder as perguntas a seguir.

15. Qual o valor marginal de trabalho adicional no setor de fabricação?Dê uma interpretação econômica de sua resposta.

16. Se uma hora extra de trabalho estivesse disponível, em qual depar-tamento deveria ser alocada? Por quê?

Resolva os jogos matriciais nos Exercícios 17 e 18 usando programa -ção linear.

19. Resolva o jogo matricial no Exercício 9 na Seção 9.1 usando pro-gramação linear. Esse jogo e o do Exercício 10 não podem ser re-solvidos pelos métodos da Seção 9.1.

20. Resolva o jogo matricial no Exercício 10 na Seção 9.1 usando pro-gramação linear.

21. Bob deseja investir R$35.000,00 em ações, títulos e ouro. Ele sabeque a taxa de retorno vai depender das condições econômicas do

país, o que é claramente difícil de prever. Depois de uma análisecuidadosa, ele determina o lucro anual, em reais, esperado por cadacem reais em cada tipo de investimento, dependendo se a economiaestiver forte, estável ou fraca:

Como Bob deve investir seu dinheiro para maximizar seu lucro independente do estado da economia? Ou seja, considere o problema comoum jogo matricial no qual Bob, o jogador linha, está jogando contra a“economia”. Qual é o valor esperado de seus investimentos ao nal deum ano?

22. Seja P um problema de programação linear (primitivo) com conjunto factível ℱ e seja P * o problema dual com conjunto factível

ℱ *. Prove o seguinte: a. Se x estiver emℱ e y estiver em ℱ *, então f (x) ≤ g (y). [Suges-

tão: Escreva f (x) na forma xT c e g (y) na forma yT b. Depois, co-mece com a desigualdade c ≤ AT y.]

b. Se f (x) = g (y) para algum x emℱ e y emℱ *, então x será umasolução ótima para P e y será uma solução ótima para P *.

23. Seja A um jogo matricial m × n. Sejam y – e x – soluções ótimas paraos problemas de programação linear primitivo e dual associados,respectivamente, como na discussão antes do Exemplo 5. Seja λ =uT x – = vT y – e dena x = x – /λ , y = y – /λ . Denote por L e C , respecti-vamente, os jogadores linha e coluna.

a. Mostre que x e y são estratégias mistas para L e C , respectiva-mente.

b. Se y for qualquer estratégia mista para C , mostre que E (x, y) ≥

1/λ . c. Se x for qualquer estratégia mista para L, mostre que E (x, y ) ≤ 1/λ .

d. Conclua que x e y são estratégias mistas ótimas para l e C , respectivamente, e o valor do jogo é 1/λ .

SOLUÇÕES DOS PROBLEMAS PRÁTICOS

1.

2. As variáveis de folga são x

3, x

4 e x

5. Os elementos na última linha nessas colunas do quadro sim-

plex nal fornecem a solução ótima do problema dual. Assim,

3. A variável de folga x3 vem da desigualdade para a festuca. Isso corresponde à variável y

1 no pro-

blema dual, de modo que o valor marginal da festuca é 0. De forma análoga, x4 e x

5 vêm do centeio

e do capim-do-campo, respectivamente, de modo que seus valores marginais são iguais a 1.



Capítulo 9

Seção 9.1

Solução:

Dado faça o gráco de

As retas se intersectam em (t , z ) = A estratégia linha óti-

ma é e o valor do jogo é v = .

Pelo Teorema 4, a estratégia coluna ótima y satisfaz E (e1, y) =

e E (e2, y) = , já que x é uma combinação linear de e

1 e e

2. Da

segunda dessas condições,

Então c1 = e Para

vericar, calcule

Solução:

Dado faça o gráco de

As retas se intersectam em A estratégia linha ótima

é e o valor do jogo é v = . Pelo

Respostas dos Exercícios Ímparesdo Capítulo 9

Teorema 4, a estratégia coluna ótima y satisfaz E (e1, y) = e

E (e2, y) = , já que x é uma combinação linear de e1

e e2. Da

primeira dessas condições,

Então Para vericar, calcule

15. ou ou qualquer combinação convexa dessas

estratégias linha, .

Solução: A coluna 2 domina a coluna 3, de modo que o jogador coluna C

nunca irá jogar a coluna 2. O gráco mostra por que a coluna 2

não afetará o jogador coluna e mostra que o valor do jogo é 2. O

novo jogo é Seja

A reta para a coluna 3 é z = 2. Essa reta intersecta a reta para a coluna4, em que z = 0(1 – t ) + 5t = 2 e t = 0,4. Uma estratégia linha ótima

é Outra estratégia linha ótima é deter-

minada pela interseção das retas para as colunas 1 e 3, nas quais

z = 4(1 – t ) + t = 2, t = e Pode-se mostrar que qual-

quer combinação convexa dessas duas estratégias ótimas também éuma estratégia linha ótima.

Para encontrar a estratégia coluna ótima, sejam

2 = E (e1, y) = e

1T By e 2 = E (e

2, y) = e

2T By. Essas duas equações for-

necem 4c1 + 2c

2 = 2 e c

1 + 2c

2 + 5c

3 = 2. Combine isso com o fato

de que c1 + c

2 + c

3 tem de ser 1 e resolva o sistema

Esta é a estratégia coluna para o jogo matricial B. Para A,



42 CAPÍTULO 9

Solução: A linha 2 é recessiva em relação à linha 3, e a linha 4 é recessiva

em relação à linha 1, de modo que o jogador linha L nunca jogaráa linha 2 nem a linha 4. Além disso, a coluna 4 domina a coluna 2,de modo que o jogador coluna C nunca jogará a coluna 4. Assim, o

jogo se reduz a

Seja (Se não fosse notado que a colu-

na 4 em A era dominante, esse fato caria claro depois que as retasassociadas às colunas da matriz reduzida fossem desenhadas.) Asequações das retas que correspondem às colunas de B são

O gráco de v(x(t )) como função de t é o caminho poligonal for-mado pela reta 3 (associada à coluna 3), depois reta 2 (coluna 2)e depois reta 4 (coluna 4). O ponto mais alto nesse caminho ocor-re na interseção das retas 3 e 2. Resolva z = −1 + 5t e z = 1 – 2t para encontrar t = 2 –

7 e z = 3 –

7. O valor do jogo B é z = 3 –

7, atingido

quando

Como as colunas 2 e 3 de B determinam a solução ótima, a

estratégia ótima para o jogador coluna C é uma combinação convexa

y das estratégias puras para as colunas e2 e e

3, digamos, .

Como ambas as coordenadas da solução linha ótima são nulas, oTeorema 4 mostra que E (e

i, y) = 3 –

7 para i = 1, 2. Cada condição de-

termina y por si só. Por exemplo,

Substitua c3 = 1 – c

2 e obtenha c

2 = e c

3 = . Logo,

é a estratégia coluna ótima para o jogo B. Para o jogo A,

e e o valor do jogo ainda é .

19. a. Exército: 1/3 pelo rio, 2/3 pela selva; guerrilheiros: 1/3 no rio, 2/3 na selva; 2/3 dos suprimentos passam.

b. Exército: 7/11 pelo rio, 4/11 pela selva; guerrilheiros: 7/11 no rio, 4/11 na selva; 64/121 dos suprimentos passam.

21. a. Verdadeira. Pela denição. b. Verdadeira. Com uma estratégia pura, um jogador escolhe uma

jogada em particular com probabilidade 1. c. Falsa. v(x) é igual ao mínimo do produto interno de x com cada

uma das colunas da matriz de pagamentos. d. Falsa. O Teorema Minimax só diz que o valor de um jogo é o

mesmo para ambos os jogadores. Não garante que existe umaestratégia mista ótima para cada jogador que produza esse valorcomum. É o Teorema Fundamental para Jogos Matriciais quediz que todo jogo matricial tem solução.

e. Verdadeira. Pelo Teorema 5, a linha s pode ser retirada da ma-triz de pagamentos e qualquer estratégia ótima para a nova matrizserá também um estratégia ótima para A. A estratégia ótima nãoenvolverá a linha s.

Seção 9.2

1. Seja x1 a quantidade investida em fundos mútuos, x

2 a quantida-

de investida em CDBs e x3 a quantidade investida em poupança.

Então

Solução: Em primeiro lugar, encontre os pontos de interseção das retas que

limitam a região:



Otimização 43

Até mesmo um esboço grosseiro dos grácos dessas retas revelaráque (0, 0), (16, 0) e (0, 8) são vértices do conjunto factível. Mas eas interseções das retas (1), (2) e (3)?

O método gráco vai funcionar desde que o gráco seja su-

cientemente grande e esteja desenhado com cuidado. Em muitos problemas simples, mesmo um pequeno esboço irá mostrar quais os pontos de interseção que serão vértices do conjunto factível. Neste problema, no entanto, três pontos de interseção estão muito próxi-mos e um pequeno erro em um gráco de tamanho 7 cm × 7 cm oumenor pode levar a uma solução incorreta. Em casos como esse, o

procedimento algébrico descrito a seguir irá funcionar bem:

Quando encontrar um ponto de interseção correspondente a duasdesigualdades, teste-o nas outras desigualdades para vericar se eleestá no conjunto factível.

A interseção de (1) e (2) é (14, 4). Teste na terceira desigualdade:

14 + 3(4) = 26 > 24. Este ponto não satisfaz a desigualdade correspondente a (3), logo ele não está no conjunto factível.

A interseção de (1) e (3) é (14,4, 3,2). Teste na segunda desigual-dade: 14,4 + 3,2 = 17,6 ≤ 18, logo o ponto (14,4, 3,2) pertence aoconjunto factível.

A interseção de (2) e (3) é (15, 3). Teste na primeira desigualdade:2(15) + 3 = 33 > 32, logo (15, 3) não está no conjunto factível.

Agora, liste os vértices do conjunto factível: (0, 0), (16, 0), (14,4,3,2) e (0, 8). A seguir, calcule os valores da função objetivo 80 x

1 +

65 x2 nesses pontos.

Finalmente, selecione o máximo da função objetivo, que é 1360, enote que esse máximo é atingido em (14,4, 3,2).

9. A função objetivo é ilimitada.

11. a. Verdadeira. Pela denição. b. Falsa. O próprio vetor x

– tem de ser factível. É possível que omáximo da função f seja atingido em um vetor que não seja fac-tível (além da solução ótima).

13. Lucro máximo = R$1.250,00 quando x1 = 100 sacos de SempreVerde

e x2 = 350 sacos de VerdeRápido.

Solução: Em primeiro lugar, encontre os pontos de interseção das retas limí-

trofes:

A interseção das retas (1) e (2) é (200, 300). Teste esse ponto nadesigualdade correspondente à reta (3): (200) + (300) = 500 > 450.O ponto de interseção não satisfaz a desigualdade correspondentea (3), logo (200, 300) não está no conjunto factível.

A interseção de (1) e (3) é (300, 150). Teste em (2): (300) + 2(150) =

600 ≤ 800, logo (300, 150) está no conjunto factível. A interseção de (2) e (3) é (100, 350). Teste em (1): 3(100) +

2(350) = 1000 ≤ 1200, logo (100, 350) está no conjunto factível. Os vértices do conjunto factível são (0, 0), (400, 0), (300, 150),

(100, 350) e (0, 400). Calcule a função objetivo em cada vértice:

O máximo da função objetivo 2 x1 + 3 x

2 é R$1.250,00 em (100, 350).

15. Lucro máximo = R$1.180,00 para 20 produtos A e 30 produtos B.

Solução: Em primeiro lugar, encontre os pontos de interseção das retas limí-

trofes:

A interseção das retas (1) e (2) é (30, 25). Teste esse ponto na

terceira desigualdade: 0,2(30) + 0,2(25) = 11 > 10. O ponto de in-terseção não satisfaz a desigualdade correspondente a (3), logo (30,25) não está no conjunto factível.

A interseção de (1) e (3) é (100/3, 100/6). Teste na segunda desi-gualdade: 0,2(100/3) + 0,4(100/6) = 13,3 ≤ 16, logo (100/3, 100/6)está no conjunto factível.

A interseção de (2) e (3) é (20, 30). Teste na primeira desigual-dade: 5(20) + 2(30) = 160 ≤ 200, logo (20, 30) está no conjuntofactível.

Os vértices do conjunto factível são (40, 0), (100/3, 100/6), (20,30) e (0, 40). Calcule a função objetivo em cada vértice:

O lucro máximo é R$1.180,00 quando x

1 = 20 produtos A e x

2 = 30

produtos B.

17. Sejam p e q pontos arbitrários em S , e . Então

vT p ≤ c e vT q ≤ c. Seja t qualquer escalar tal que 0 ≤ t ≤ 1. Então, pela linearidade da multiplicação de matrizes (ou do produto inter-no, se vT p for escrito como v⋅p, e assim por diante),

já que (1 – t ) e t são ambos positivos e p e q estão em S . Então osegmento de reta que une p a q está contido em S . Como p e q são

pontos arbitrários em S , o conjunto S é convexo.

19. Seja S = {x : f (x) = d } e sejam p, q ∈ S . Sejam t e x tais que 0 ≤ t ≤ 1 e x = (1 – t )p + t q. Então

Logo, x ∈ S . Isso mostra que S é convexo.

Seção 9.3



44 CAPÍTULO 9

d. Não é ótimo.

7. a. Falsa. Uma variável de folga é usada para transformar umadesigualdade em uma igualdade.

b. Verdadeira. Pela denição. c. Falsa. A solução básica inicial não será factível, mas ainda pode

existir uma solução factível básica.

9. O máximo é 150 quando x1 = 3 e x2 = 10. Solução: Em primeiro lugar, introduza x

2 na solução; faça o pivô com o ele-

mento na linha 1. Depois, introduza x1 na solução; faça o pivô com

a linha 2. O máximo é 150 quando x1 = 3 e x

2 = 10.

11. O máximo é 56 quando x

1 = 9 e x

2 = 4.

Solução: Em primeiro lugar, introduza x

2 na solução; faça o pivô com o ele-

mento na linha 2. Depois, introduza x1 na solução; faça o pivô com

a linha 3. O máximo é 56 quando x1 = 9 e x

2 = 4.

13. O mínimo é 180, quando x

1 = 10 e x

2 = 12.

Solução: Converta este problema para um problema de maximização para

−12 x1 − 5 x

2 e inverta a primeira desigualdade. Começando com o

primeiro quadro a seguir, introduza x1 na solução usando a linha

1 como pivô. Depois, introduza x2 na solução; use a linha 2 como

pivô. O valor máximo de −12 x1 − 5 x

2 é −180, logo o valor mínimo

da função objetivo original 12 x1 + 5 x

2 é 80, atingida quando x

1 = 10

e x2 = 12.

15. A resposta está de acordo com o Exemplo 7. O mínimo é 20, quando

x1 = 8 e x

2 = 6.

Solução: Comece com o mesmo quadro simplex inicial, introduzindo x

1 na

solução com a linha 2 como a linha pivô. Depois, introduza x2

na solução usando como pivô a linha 1. O máximo de − x1 – 2 x

2 é

−20, logo o mínimo de x1 + 2 x

2 é 20, quando x

1 = 8 e x

2 = 6.

17. O lucro máximo é R$1.180,00, obtido na fabricação de 20 produtosA e 30 produtos B cada dia.

Solução: O quadro simplex a seguir é baseado no problema da Companhia

Benri (Exercício 15 na Seção 9.2) de maximizar a função lucro20 x

1 + 26 x

2 sujeita a diversas quantidades de trabalho disponível

para um processo de produção com três etapas. Para começar o mé-todo simplex, introduza x

2 na solução usando a linha 2 como pivô.

Depois, introduza x1 na solução usando a linha 3. O lucro máximo

é R$1.180,00, obtido com a fabricação de 20 produtos A e 30 pro-dutos B por dia.



Otimização 45

Seção 9.4

5. O mínimo é M = 150, obtido quando y

1 = 20 –

7 e y

2 = 6 –

7.

Solução:

O quadro nal do Exercício 9 na Seção 9.3 é

A solução do problema dual pode ser vista nos elementos da linha3 nas colunas 3, 4 e 6. O mínimo é M = 150, obtido quando y

1 = 20 –

7

e y2 = 6 –

7.

7. O mínimo é M = 56, obtido quando y1 = 0, y

2 = 1 e y

3 = 2.

Solução: O quadro nal do Exercício 11 na Seção 9.3 é

A solução do problema dual pode ser vista nos elementos da linha4 nas colunas 3, 4, 5 e 7. O mínimo é M = 56, obtido quando y

1 =

0, y2 = 1 e y

3 = 2.

9. a. Falsa. Deveria ser AT y ≥ c. b. Verdadeira. Pelo Teorema 7.

c. Verdadeira. Pelo Teorema 7. d. Falsa. O valor marginal é zero se o zero estiver na solução ótima.

Veja o Exemplo 4.

11. O mínimo é 43, quando x1 = 7 –

4, x

2 = 0 e x

3 = 3 –

4.

Solução: O problema dual é maximizar a função 4 y

1 + 5 y

2 sujeita a

e y ≥ 0. Resolva o problema dual pelo

método simplex:

A solução do dual do dual (o primitivo) é x1 = 7 –

4, x

2 = 0 e x

3 = 3 –

4, com

M = 43.

13. O custo mínimo é R$670,00, usando 11 sacos de Potência dos Duen-

des e 3 sacos de Poder Nebuloso.

Solução: O problema no Exercício 2 da Seção 9.2 é minimizar a fun-ção cT x sujeita a Ax ≤ b e x ≥ 0, em que x lista o número de sa-

cos de Potência dos Duendes e de Poder Nebuloso e

O dual de um pro-

blema de minimização envolvendo uma matriz é um problema demaximização envolvendo a transposta da matriz, com o vetor de dados

para a função objetivo e o vetor para as restrições trocados. Comoa notação estabelecida no Exercício 2 foi para um problema deminimização, a notação aqui é “invertida” da notação usual para

um problema primitivo. Portanto, o dual do problema primitivoenunciado anteriormente é maximizar bT y sujeito às condições

AT y ≤ c e y ≥ 0. Ou seja, maximizar a função 28 y1 + 30 y

2 + 20 y

3+ 25 y

4

sujeita a

Eis os cálculos do método simplex para este problema dual:



46 CAPÍTULO 9

Como o problema original é o dual do problema resolvido pelo mé-todo simplex, a solução desejada é dada pelas variáveis de folga y

5 =

11 e y6 = 3. O valor da função objetivo é o mesmo para os dois pro-

blemas, o primitivo e o dual, logo o custo mínimo é R$670,00. Issoé obtido por meio da mistura de 11 sacos de Potência dos Duendese 3 sacos de Poder Nebuloso.

15. O valor marginal é zero. Isso corresponde ao trabalho estar sendosubutilizado no departamento de fabricação. Ou seja, no planeja-mento da produção ótima com x

1 = 20 e x

2 = 30, só são necessárias

160 horas das 200 disponíveis no setor. O trabalho extra é desper-diçado, logo tem valor zero.

Solução:

O jogo é Some 3 para deslocar o jogo:

O quadro para esse problema de programação

linear é

As soluções ótimas, para o problema primitivo e para o dual,são, respectivamente, e x1

com As estratégias mistas ótimas corres-

pondentes para os jogadores coluna e linha são , respectiva-mente,

O valor do jogo com a matriz de pagamentos deslocada é 1/λ = 4,logo o valor do jogo original é 4 – 3 = 1.

21. Transforme esse “jogo” em um problema de programação lineare use o método simplex para analisar o jogo. O valor esperadodo jogo é 38 –

35, baseado em uma matriz de pagamento para um in-

vestimento de R$100,00. Com R$35.000,00 para investir, Bob“joga” esse jogo 350 vezes. Logo, ele espera ganhar R$380,00,e o valor esperado de seus investimentos ao nal de um ano éR$35.380,00. Usando a estratégia ótima para o jogo, Bob deve in-

vestir R$11.000,00 em ações, R$9.000,00 em títulos e R$15.000,00

em ouro.

Solução:

O jogo é Some 3 para deslocar o jogo:

O problema de programação linear é maximizar

a função y1 + y

2 + y

3 sujeita a



Otimização 47

O quadro para este jogo é

Os cálculos do método simplex são

A solução ótima para os dois problemas, o primitivo e o dual, são,respectivamente,

e

As estratégias ótimas mistas correspondentes para os jogadores co-luna e linha são, respectivamente,

O valor do jogo com a matriz de pagamentos deslocada é 1/λ , queé igual a , logo o valor do jogo original é − 3 = 38 –

35. Usando a

estratégia ótima x, Bob deve investir dos R$35.000,00 em ações,

em títulos e em ouro. Ou seja, Bob deve investir R$11.000,00

em ações, R$9.000,00 em títulos e R$15.000,00 em ouro. O valoresperado do jogo é 38 –

35, baseado em R$100,00 para cada jogada. (A ma-

triz de pagamentos lista as quantias recebidas ou perdidas para cadaR$100,00 investidos por um ano.) Com R$35.000,00 para investir, Bob“joga” esse jogo 350 vezes. Logo, ele espera ganhar R$380,00, e o valoresperado de seus investimentos ao nal de um ano é R$35.380,00.

23. a. As coordenadas de x – são todas não negativas. Da denição de u, λ é igual à soma dessas coordenadas. Segue que as coordenadas de x são não negativas e sua soma é igual a um. Logo, x éuma estratégia mista para o jogador linha L. Um argumento se-melhante é válido para y e o jogador coluna C .

b. Se y for qualquer estratégia mista para C , então

c. Se x for qualquer estratégia mista para L, então

d. O item (b) implica v( x) ≥ 1/λ , logo v

L ≥ 1/λ . O item (c) implica

v(y) ≤ 1/λ , logo vC ≤ 1/λ . Segue do Teorema Minimax na Seção

9.1 que x e y são estratégias ótimas para L e C , respectivamente,e o valor do jogo é 1/λ .

capitulo 009 david lay

Documents