Cap tulo 2 Programa˘c~ao Linear - dt.fee.unicamp.brvalente/capt21_044.pdf · problema da dieta visavam oferecer uma dieta di aria de baixo custo para o Ex ercito Americano e a dieta

Capıtulo 2

Programacao Linear

2.1 Introducao

Modelos lineares de otimizacao aos quais eventualmente se incorporam res-tricoes de integralidade das variaveis de decisao sao os mais utilizados em plane-jamento. Quando do surgimento do metodo Simplex para Programacao Linear,argumentava-se que modelos lineares nao seriam adequados para representar pro-blemas reais, uma vez que quase todos os problemas de interesse possuiam ca-racterısticas nao–lineares. Entretanto, o metodo Simplex tornou possıvel resolverproblemas relativamente grandes (em termos de numero de variaveis e restricoes),o que nenhum outro metodo era capaz a epoca. Uma melhor compreensao das po-tencialidades e limitacoes da modelagem linear levou a inumeras aplicacoes praticasdo metodo.

Rapidamente constatou-se que a aplicabilidade da modelagem linear poderiaser substancialmente espandida se fosse possıvel tratar problemas com variaveis dedecisao restritas a valores inteiros ou binarios (0 ou 1), o que permitiria incorporar amodelagem de problemas de planejamento um tipo importante de nao–linearidade.Desenvolvimentos nesta linha deram origem as Programacoes Inteira, Inteira/Mistae Combinatoria, cujos metodos podem ser vistos como extensoes dos metodos daProgramacao Linear.

A modelagem linear e a solucao de problemas de producao por meio do metodoSimplex sao os principais objetivos deste capıtulo. Por conveniencia, modelos comvariaveis de decisao inteiras ou binarias sao tambem considerados; metodos adequa-dos para tratar estes modelos serao discutidos a partir do Capıtulo 3.

2.2 Hipoteses basicas

Uma empresa pode ser vista como um sistema que transforma recursos emprodutos por meio de metodos ou tecnologias adequadas. Tipicamente os recursosconsistem de materias–primas, forca de trabalho (homens/hora), disponibilidade deequipamentos e bens intermediarios, adquiridos de outras empresas. Os produtos

9

10 Capıtulo 2. Programacao Linear

podem ser bens ou servicos acabados para consumo, ou intermediarios, a seremcomercializados com outras empresas.

Certas hipoteses sao necessarias para que modelos lineares representem ade-quadamente problemas de producao.

Proporcionalidade

Modelos lineares adotam a hipotese de que se o custo de producao de umaunidade (custo unitario) de um produto j e cj , entao xj unidades do produto cus-tam cjxj . Se pj e o preco unitario de venda do produto j, entao xj unidades doproduto sao vendidas por pjxj . Na modelagem linear, se a producao de uma uni-dade do produto j consome aij unidades do recurso i, entao xj unidades do produtoconsomem aijxj do recurso i.

A hipotese de proporcionalidade pode deixar de corresponder a realidade.Exemplo: o custo (preco) unitario de producao (venda) pode decrescer a partir deum significativo aumento da quantidade produzida (vendida).

Aditividade

Pela hipotese da aditividade, se os custos unitarios de producao de dois pro-dutos, j e k, sao cj e ck, respectivamente, entao o custo total para produzir xj exk unidades dos produtos e cjxj + ckxk, o mesmo aplicando-se ao valor total devenda de produtos. Se a producao de uma unidade do produto j e de uma unidadedo produto k consomem aij e aik unidades do recurso i, respectivamente, entao oconsumo total do recurso i e aijxj + aikxk.

A hipotese de aditividade implica que produtos podem ser produzidos inde-pendentemente. Pode deixar de ser valida se houver interacao entre producoes.Exemplo: dois produtos utilizam um mesmo recurso com diferentes eficiencias

Divisibilidade

Significa que as variaveis de decisao podem assumir qualquer valor real, istoe, valores fracionarios (nao–inteiros) representam decisoes viaveis.

A hipotese de divisibilidade pode ser adotada quando as variaveis de decisaosignificam, por exemplo, quanto produzir de cada produto, e produtos nao–acabadosdurante um perıodo de producao (dia, semana, mes, ano, etc.) podem ser acabadosno perıodo seguinte. Entretanto, se significarem quantidades de produtos paraentregas em datas pre–determinadas, variaveis de decisao assumindo apenas valoresinteiros podem ser necessarias.

Existem ainda situacoes nas quais deve-se selecionar que produtos produzirdentro de uma lista de produtos possıveis. Para indicar selecao ou atribuicao, usa-segeralmente variaveis de decisao binarias: valores iguais a 1 indicam que os custosde producao e recursos utilizados pelos produtos assim selecionados devem ser con-

2.3. Modelos lineares 11

tabilizados; valores iguais a 0 indicam exatamente o contrario.

Determinismo

Os parametros presentes no modelo – custos, precos unitarios, recursos –sao precisamente conhecidos. Assume-se que eventuais incertezas quanto a estesparametros foram eliminadas e que dispoe-se de um modelo determinıstico equiva-lente.

A hipotese de determinismo costuma ser afetada pelo perıodo de planejamento.Em perıodos longos, as previsoes de demandas e recursos tornam-se mais imprecisas,dificultando a determinacao de custos de producao e precos de venda de produtos.

2.3 Modelos lineares

As hipoteses de proporcionalidade e aditividade levam a modelos de otimi-zacao integralmente representados por funcoes lineares. Uma funcao z = z(x) elinear nas variaveis de decisao x1, x2, . . . , xn quando existem coeficientes α1, α2,. . . , αn tais que

z(x) = α1x1 + α2x2 + · · · + αnxn.

Supondo que x1, x2, . . . , xn sao as quantidades produzidas de n produtos ec1, c2, . . . , cn sao os custos unitarios de producao associados, entao o custo totalde uma empresa pode ser expresso por meio da funcao linear

zc(x) = c1x1 + c2x2 + · · · + cnxn.

A rigor, zc(x) e o custo total variavel (com as quantidades produzidas) daempresa. Geralmente existe uma segunda parcela de custo, chamada de custo totalfixo, incorrido pela empresa independentemente das quantidades produzidas, quedeve ser somado a zc para se obter o custo total de producao. Entretando, aexistencia de custos fixos nao gera dificuldades para a solucao de problemas deprogramacao linear.

De forma analoga, a receita total e o lucro total da empresa sao expressospelas funcoes lineares

zr(x) = p1x1 + p2x2 + · · · + pnxn

e

zl(x) = zr(x) − zc(x),

respectivamente. As funcoes zc, zr e zl sao exemplos de funcoes–objetivos paraproblemas de producao modelados por meio da abordagem linear.

As hipoteses de proporcionalidade e aditividade permitem que as restricoes doproblema sejam representadas por equacoes e/ou inequacoes lineares nas variaveisde decisao. Especificamente, se aij denota a quantidade de um recurso i utilizado


para produzir uma unidade do produto j, e bi e a quantidade total disponıvel dorecurso, entao a escolha das quantidades a produzir deve respeitar a desigualdade

ai1x1 + ai2x2 + · · · + ainxn ≤ bi.

Deve haver uma desigualdade deste tipo para cada tipo de recurso utilizado.Se bi, i = 1, 2, . . . ,m denotarem as quantidades totais de m recursos disponıveise o objetivo do problema for maximizar a receita total decorrente da producao daempresa, entao o problema de otimizacao linear correspondente sera dado por∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

maximizar z = c1x1 + c2x2 + · · · + cnxn

sujeito a a11x1 + a12x2 + · · · + a1nxn ≤ b1,a21x1 + a22x2 + · · · + a2nxn ≤ b2,

......

......

am1x1 + am2x2 + · · · + amnxn ≤ bm,x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0.

(2.1)

No problema (2.1) adota-se a hipotese da divisibilidade: as variaveis de decisaosao quaisquer reais nao–negativos. Formulacoes similares, mas envolvendo diferentesinterpretacoes para variaveis de decisao e restricoes a serem satisfeitas sao muitofrequentes em programacao linear.

Exemplo 2.1 (Problema da dieta) O chamado problema da dieta foi o primeiroproblema linear formulado e resolvido com o uso de metodos de programacao linear.Assume-se que estejam disponıveis n diferentes alimentos (carne, leite, ovos, sucode laranja, . . . ) e que o custo unitario do i-esimo alimento e ci, i = 1, 2, . . . , n. Adieta deve atender a exigencias diarias mınimas de m diferentes nutrientes (vita-minas, proteınas, carboidratos, . . . ). Os nıveis mınimos de nutrientes sao represen-tados por bj , j = 1, 2, . . . ,m; supoe-se que cada alimento i possui aij unidades donutriente j por unidade do alimento i. Se as quantidades totais (nao-negativas) dosn alimentos forem representadas por x1, x2, . . . , xn, o problema da dieta assume aforma

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

minimizar c1x1 + c2x2 + · · · + cnxn

sujeito a a11x1 + a12x2 + · · · + a1nxn ≥ b1,a21x1 + a22x2 + · · · + a2nxn ≥ b2,

......

......

am1x1 + am2x2 + · · · + amnxn ≥ bm,x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0.

A formulacao do problema da dieta pode ser refinada de varias maneiras. Epossıvel, por exemplo, que a solucao de mınimo custo seja tal que poucos alimentos(apenas os mais baratos) facam parte da dieta diaria. Uma forma de evitar asaturacao do indivıduo com uma dieta muito simples e incorporar restricoes comvalores maximos para as quantidades de alimentos, isto e, incorporar restricoes dedesigualdade do tipo xi ≤ xi, i = 1, 2, . . . , n. A nova dieta sera, provavelmente,mais diversificada, embora tambem mais cara do que a original.

2.4. Forma padrao 13

Uma hipotese mais realista seria imaginar que as quantidades dos alimentosdevem ser determinadas na forma de porcoes (porcoes de carne, porcoes de arroz,. . . ), ao inves de quantidades arbitrarias de alimentos. (As primeiras aplicacoes doproblema da dieta visavam oferecer uma dieta diaria de baixo custo para o ExercitoAmericano e a dieta deveria ser servida em porcoes.) Se levarmos em conta estahipotese, o problema passa a envolver variaveis de decisao inteiras nao-negativas. 2

2.4 Forma padrao

Para modelos de programacao linear e possıvel estabelecer uma formulacaomatematica geral conhecida como forma padrao: qualquer problema de progra-macao linear pode ser convenientemente manipulado e colocado nesta forma. Apartir de uma forma padrao torna-se mais facil desenvolver e implementar metodoscomo o Simplex, a ser discutido neste capıtulo. A forma padrao de um problemade programacao linear e a seguinte:

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

minimizar z = c1x1 + c2x2 + · · · + cnxn

sujeito a a11x1 + a12x2 + · · · + a1nxn = b1,a21x1 + a22x2 + · · · + a2nxn = b2,

......

......

am1x1 + am2x2 + · · · + amnxn = bm,x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0.

(2.2)

As constantes ci, bj e aij , i = 1, 2, . . . , n, j = 1, 2, . . . ,m caracterizam umproblema particular de programacao linear. Um problema na forma padrao (2.2)possui n variaveis de decisao, m restricoes de igualdade e a funcao–objetivo deveser minimizada. Assume-se ainda que bj ≥ 0 para j = 1, 2, . . . ,m

Procedimentos simples podem ser adotados para se chegar a forma padrao deum problema de programacao linear qualquer.

Variaveis de excesso

Suponha que o problema linear original apresenta uma restricao de desigual-dade do tipo

aj1x1 + aj2x2 + · · · + ajnxn ≥ bj .

A restricao de desigualdade pode ser substituıda por uma restricao de igual-dade introduzindo-se uma variavel adicional xn+1, nao-negativa, conhecida comovariavel de excesso:

aj1x1 + aj2x2 + · · · + ajnxn − xn+1 = bj .

Introduz-se tantas variaveis de excesso quantas forem as restricoes do tipo”≥” presentes no modelo original. Um novo conjunto de variaveis sera formadopelas variaveis de decisao originais mais as variaveis de excesso.


Variaveis de folga

Suponha agora que o problema linear original apresenta uma restricao dedesigualdade do tipo

aj1x1 + aj2x2 + · · · + ajnxn ≤ bj .

A restricao de desigualdade pode ser substituıda por uma restricao de igual-dade introduzindo-se uma variavel adicional xn+1, nao-negativa, conhecida comovariavel de folga:

aj1x1 + aj2x2 + · · · + ajnxn + xn+1 = bj .

Do mesmo modo, introduz-se tantas variaveis de folga quantas forem as res-tricoes do tipo ”≤” presentes no modelo original. O novo conjunto de variaveis seraformado pelas variaveis de decisao originais mais as eventuais variaveis de excessoe de folga.

Variaveis livres

Pode ocorrer da formulacao original do problema apresentar uma ou maisvariaveis de decisao irrestritas ou livres, isto e, sem sinal definido. Entretanto, aforma padrao exige variaveis nao–negativas. Essa dificuldade pode ser contornadareescrevendo-se cada variavel livre xj como a diferenca de duas outras variaveisnao-negativas, xj1 e xj2, ou seja

xj = xj1 − xj2.

A ideia e que qualquer quantidade (positiva, nula ou negativa) pode ser re-presentada como a diferenca de duas quantidades nao-negativas. Faz-se entao asubstituicao de cada variavel livre por uma diferenca de variaveis nao-negativas eincorpora-se as novas variaveis a lista de variaveis de decisao do problema.

Nao-negatividade dos bj’s

Por razoes a serem detalhadas oportunamente, exige-se que as constantes bj ,j = 1, 2, . . . ,m nos lados direitos das restricoes do problema (2.2) sejam todas nao-negativas. Esta exigencia pode ser atendidad multiplicando-se por −1 ambos oslados de todas restricoes tais que bj < 0. O resultado sao novas restricoes com ladosdireitos positivos.

Problemas de maximizacao

Certos problemas de programacao linear envolvem maximizar funcoes–objeti-vos, como a receita de uma empresa. O objetivo do problema se expressaria como

maximizar z(x) = p1x1 + p2x2 + · · · + pnxn, (2.3)

sujeito as restricoes.

2.5. Exemplos ilustrativos 15

Assuma que x? = (x?1, x

?2, . . . , x

?n) e uma solucao otima para o problema (2.3).

Da otimalidade de x? conclui-se que

z(x?) ≥ z(x)

para toda solucao viavel x. Neste caso,

−z(x?) ≤ −z(x)

e x? e tambem uma solucao otima para o problema de minimizar −z(x) sujeitoas mesmas restricoes. Portanto, a substituicao de maximizar por minimizar, se-guida da troca dos sinais dos coeficientes da funcao–objetivo, fornece problemasequivalentes do ponto de vista das variaveis de decisao. Os valores absolutos dasfuncoes–objetivos serao iguais, porem com sinais trocados.

Constante na funcao–objetivo

A soma de uma constante qualquer a uma funcao objetivo nao altera o pro-blema do ponto de vista das variaveis de decisao. De fato, se x? e uma solucaootima para o problema de minimizar

z(x) = c1x1 + c2x2 + · · · + cnxn,

sujeito as restricoes, entao x? tambem e uma solucao otima para o problema deminimizar z(x) + c0, sendo c0 uma constante qualquer, uma vez que

z(x?) + c0 ≤ z(x) + c0

para toda solucao viavel x. Constantes em funcoes–objetivos geralmente surgem daconsideracao de custos fixos ou de reformulacoes visando formas padroes. Podemser desconsideradas para a obtencao de solucoes otimas e entao somadas aos valoresotimos das funcoes–objetivos.

2.5 Exemplos ilustrativos

Embora seja possıvel colocar qualquer problema de programacao linear naforma padrao (2.2), nao existe um procedimento sistematico para obter o modelo deotimizacao basico do problema. Uso criterioso das hipoteses e treinamento exaustivosao essenciais para se ganhar habilidade em modelagem de problemas de producao.

Exemplo 2.2 Uma joalheria produz dois diferentes tipos de estojos de madeirapara jogos de xadrez. O primeiro, menor, requer 3 horas de trabalho de tornea-mento; o segundo, maior, requer 2 horas. A empresa possui 4 tornos operados portrabalhadores treinados, os quais trabalham, cada, 40 horas por semana. O estojomenor demanda 1 kg de madeira; o maior demanda 3 kg. A empresa pode obter nomaximo 200 kg de madeira por semana. Os lucros unitarios da empresa sao de $20 e$5 por unidade de estojo maior e menor, respectivamente. Deseja-se prescrever um


programa de producao que vise maximizar o lucro total da empresa com a vendados estojos.

Sejam x1 e x2 as quantidades (nao–negativas) de estojos de menor e maiordimensoes, respectivamente, produzidas durante uma semana. Para obter umarestricao sobre horas trabalhadas, observa-se que a empresa possui 4 operadoresque trabalham, cada, 40 horas por semana nos tornos. Portanto, a empresa dispoede 160 horas de torneamento por semana. Dadas as diferentes quantidades de horasnecessarias para tornear os estojos, obtem-se a restricao de capacidade

3x1 + 2x2 ≤ 160.

A segunda restricao de capacidade, envolvendo as quantidades de madeirautilizadas por unidade de estojos e a disponibilidade semanal de madeira paraproducao, e dada por

x1 + 3x2 ≤ 200.

O modelo de otimizacao para a empresa entao seria∣

∣

∣

∣

∣

∣

maximizar z = 5x1 + 20x2

sujeito a 3x1 + 2x2 ≤ 160,x1 + 3x2 ≤ 200,

com x1 ≥ 0 e x2 ≥ 0. Para obter a forma padrao do problema, introduz-se duasvariaveis de folga adicionais, x3 e x4, transforma-se maximizar em minimizar etrocam-se os sinais dos coeficientes da funcao–objetivo. O problema resultante sera

∣

∣

∣

∣

∣

∣

minimizar −z = −5x1 − 20x2

sujeito a 3x1 + 2x2 + x3 = 160,x1 + 3x2 + x4 = 200,

com x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 e x4 ≥ 0.

As hipoteses de proporcionalidade, aditividade e divisibilidade, implıcitas nadescricao textual do problema, tornaram mais simples sua formulacao matematica.Na pratica, um operador de torno provavelmente levaria mais tempo para tornearas primeiras unidades de estojos dos que as subsequentes. Com a hipotese de pro-porcionalidade, assume-se tempos iguais para todas as unidades de um mesmo tipo.Alem disto, nao sao considerados os tempos necessarios para ajustes dos tornos(desligamento, limpeza, instalacao de novas ferramentas, religamento) quando es-tes passam a tornear estojos de tipos diferentes. Com a hipotese da aditividade,assume-se que os tempos de ajustes podem ser desprezados, e os tempos de torne-amento efetivos, simplesmente somados. Finalmente, como se trata da producaosemanal da empresa e nao existem prazos para entrega de estojos, estojos nao-acabados numa semana podem ser acabados na semana seguinte, o que valida ahipotese de divisibilidade. 2

Exemplo 2.3 Um fazendeiro utiliza no mınimo 400 kg de racao especial por dia.A racao e uma mistura de milho e soja com as composicoes indicadas na tabela 2.1.


Tabela 2.1: Dados do problema de dieta.kg/kg de alimento

Alimento Proteına Fibra Custo ($/kg)Milho 0.09 0.02 0.60Soja 0.60 0.06 1.80

Um mınimo de 30% e um maximo de 5% da quantidade total de alimentoconsumida por dia sao estabelecidos para as quantidades totais de proteına e fibrapresentes na dieta. O fazendeiro deseja determinar a mistura de milho e soja queproduz uma dieta diaria de mınimo custo.

Sejam x1 e x2 as quantidades (nao–negativas) em kg de milho e soja na dietadiaria procurada pelo fazendeiro. Como no mınimo 400 kg de racao sao utilizados,

x1 + x2 ≥ 400.

A prescricao para consumo de proteınas implica numa restricao do tipo

0.09x1 + 0.60x2 ≥ 0.30(x1 + x2),

ou ainda

0.21x1 − 0.30x2 ≤ 0.

Do mesmo modo, para fibra,

0.02x1 + 0.06x2 ≤ 0.05(x1 + x2),

ou seja,

0.03x1 − 0.01x2 ≥ 0.

O modelo linear de otimizacao para a dieta diaria seria

∣

∣

∣

∣

∣

∣

∣

∣

minimizar z = 0.60x1 + 1.80x2

sujeito a 0.21x1 − 0.30x2 ≤ 0,0.03x1 − 0.01x2 ≥ 0,

x1 + x2 ≥ 400,

com x1 ≥ 0 e x2 ≥ 0. A forma padrao do problema e obtida introduzindo-se umavariavel de folga na primeira restricao e variaveis de excesso na segunda e terceirarestricoes. 2

Exemplo 2.4 Um restaurante fast–food vende dois tipos de sanduıches. Os san-duıches utilizam 120 g e 90 g de carne, respectivamente. O restaurante abre asportas com 90 kg de carne em estoque, mas pode comprar mais carne a $0.50/kg,preco que inclui o custo de entrega. Qualquer excesso de carne no final do dia edoado para uma instituicao de caridade. Os lucros do restaurante com os sanduıchessao de $0.20 e $0.15 por unidade, respectivamente; o restaurante nao espera vendermais do que 900 sandıches por dia. Quantos sanduıches de cada tipo o restaurantedeveria produzir para maximizar seu lucro diario?


Sejam x1 e x2 as quantidades (nao–negativas) de sanduıches dos tipos 1 e 2 aserem produzidas. Se o restaurante se mantiver dentro do limite de 90 kg de carnepor dia, entao

0.12x1 + 0.09x2 ≤ 90.

Porem, o restaurante pode adquirir mais carne, e, neste caso,

0.12x1 + 0.09x2 ≥ 90.

A princıpio, nao se sabe qual das alternativas sera mais vantajosa para o res-taurante: operar com folga ou excesso de carne. Uma solucao e introduzir umavariavel adicional x3, livre, representando quantidade de carne, e escrever a res-tricao sobre utilizacao de carne como

0.12x1 + 0.09x2 + x3 = 90.

A variavel x3 pode ser representada como a diferenca de variaveis nao–negativas:x3 = x31 − x32. A restricao e entao reescrita como

0.12x1 + 0.09x2 + x31 − x32 = 90.

Se x3 ≥ 0, o restaurante opera com folga de carne e o lucro total sera0.20x1 + 0.15x2. Por outro lado, se x3 < 0, o restaurante incorrera num custo adi-cional por comprar carne. Por motivos que serao detalhados quando da discussaodo metodo Simplex, as variaveis x31 e x32 nao poderao assumir valores positivossimultaneamente. Neste caso, se x3 < 0, entao x31 = 0 e x32 > 0, de tal forma queo lucro total do restaurante pode ser escrito como

0.20x1 + 0.15x2 − 0.50x32.

O modelo linear de otimizacao para o restaurante seria∣

∣

∣

∣

∣

∣

maximizar z = 0.20x1 + 0.15x2 − 0.50x32

sujeito a 0.12x1 + 0.09x2 + x31 − x32 = 90,x1 + x2 ≤ 900,

com x1 ≥ 0, x2 ≥ 0, x31 ≥ 0 e x32 ≥ 0. Para obter a forma padrao do problema,deve-se introduzir uma variavel de folga na ultima restricao, substituir maximizarpor minimizar, e trocar os sinais dos coeficientes da funcao–objetivo. 2

Exemplo 2.5 Um banco precisa formular uma polıtica de emprestimos envolvendouma quantia maxima de $12 milhoes. A tabela 2.2 apresenta os parametros utili-zados nos diferentes tipos de emprestimos com os quais o banco opera.

Tabela 2.2: Parametros utilizados pelo banco.Tipo de Taxa Probabilidade

Emprestimo de Juros de default

Pessoal 0.140 0.10Automotivo 0.130 0.07Habitacional 0.120 0.03

Agrıcola 0.125 0.05Comercial 0.100 0.02


Probabilidade de default significa probabilidade de que o emprestimo nao sejarecuperado, e que portanto tambem nao renda juros. A concorrencia com outrasinstituicoes financeiras obriga o banco a alocar no mınimo 40% dos recursos paraemprestimos agrıcolas e comerciais. Para apoiar a industria civil da regiao, os re-cursos alocados para emprestimos habitacionais devem corresponder a, no mınimo,50% dos recursos alocados para emprestimos pessoais, automotivos e habitacionais.A polıtica de banco estabelece que razao entre o montante total de emprestimosdefault e o total de emprestimos deve ser de 0.04. O objetivo do banco e distribuiros recursos disponıveis entre as diferentes formas de emprestimos de forma a obtero maior lucro possıvel, entendido como a diferenca entre a receita total decorrentede juros e o montante total perdido por default.

As quantidades (nao–negativas) abaixo representam os montantes (em milhoes)a serem empregados em cada tipo de emprestimo.

x1 : pessoais;x2 : automotivos;x3 : habitacionais;x4 : agrıcolas;x5 : comerciais.

Como o maximo disponıvel para emprestimos e $12 (em milhoes),

x1 + x2 + x3 + x4 + x5 ≤ 12.

Emprestimos agrıcolas e comerciais devem representar no mınimo 40% domaximo disponıvel:

x4 + x5 ≥ 4.8.

Emprestimos habitacionais devem corresponder a no mınimo 50% dos empres-timos pessoais, automotivos e habitacionais:

x3 ≥ 0.50(x1 + x2 + x3),

ou seja,0.50x1 + 0.50x2 − 0.50x3 ≤ 0.

A polıtica da empresa quanto a emprestimos default pode ser expressa como

0.10x1 + 0.07x2 + 0.03x3 + 0.05x4 + 0.02x5

x1 + x2 + x3 + x4 + x5

≤ 0.04. (2.4)

O numerador de (2.4) e quanto o banco espera perder com a alocacao derecursos. A desigualdade (2.4) e equivalente a

0.06x1 + 0.03x2 − 0.01x3 + 0.01x4 − 0.02x5 ≤ 0.

O lucro total do banco e dado por

z = 0.14(0.90x1) + 0.13(0.93x2) + 0.12(0.97x3) + 0.125(0.95x4)

+ 0.10(0.98x5) − (0.10x1 + 0.07x2 + 0.03x3 + 0.05x4 + 0.02x5) (2.5)


A primeira parcela do lado direito de (2.5) e quanto o banco espera receberde juros sobre os emprestimos; a segunda parcela contabiliza a perda devida aemprestimos default. A funcao–objetivo (2.5) pode ser simplificada para

z = 0.026x1 + 0.0509x2 + 0.0864x3 + 0.06875x4 + 0.078x5.

O modelo linear de otimizacao para o problema do banco seria∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

maximizar z = 0.026x1 + 0.0509x2 + 0.0864x3 + 0.06875x4 + 0.078x5

sujeito a 0.06x1 + 0.03x2 − 0.01x3 + 0.01x4 − 0.02x5 ≤ 0,0.50x1 + 0.50x2 − 0.50x3 ≤ 0,

x4 + x5 ≥ 4.8,x1 + x2 + x3 + x4 + x5 ≤ 12,

com x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 e x5 ≥ 0. A forma padrao do problema efacilmente obtida introduzindo-se variaveis de folga na primeira, segunda e quartarestricoes, uma variavel de excesso na terceira restricao, alterando-se maximizarpara minimizar, e trocando-se os sinais dos coeficientes da funcao–objetivo. 2.

2.6 Modelos com variaveis inteiras

Alguns modelos importantes de planejamento exigem que parte ou todas asvariaveis de decisao sejam variaveis inteiras, isto e, variaveis que podem assumirsomente valores inteiros. Como caso especial, variaveis binarias assumem apenasos valores inteiros 0 ou 1. Costuma-se referir a um modelo linear com variaveisinteiras como um modelo de programacao linear inteira, embora, rigorosamentefalando, um modelo deste tipo nao seja mais linear. Um modelo de programacaolinear inteira e puro se contem somente variaveis inteiras; misto, se parte dasvariaveis assume valores inteiros e a parte complementar, reais.

Certos modelos de programacao linear inteira podem ser abordados por meiodo metodo Simplex, na qual a hipotese de divisibilidade e adotada, e ainda assimobter-se decisoes otimas inteiras. Alem disso, quando o modelo linear exibe cer-tas propriedades estruturais, e possıvel obter solucoes otimas inteiras por meio demetodos especializados de programacao linear, discutidos no Capıtulo 3 do curso.No caso geral sera necessario utilizar metodos especıficos para resolver problemasde programacao linear inteira. Alguns destes metodos, os mais simples e gerais, saotratados no Capıtulo 4 do curso.

A modelagem de problemas de planejamento que envolvam variaveis inteirassera introduzida neste capıtulo.

Exemplo 2.6 Uma empresa de planejamento de transportes urbanos esta anali-sando a implantacao de um novo sistema de transporte de massa por onibus. Umestudo inicial visa determinar a quantidade mınima de onibus que devem ser coloca-dos em operacao para atender a demanda de passageiros. Apos coletar informacoes,o engenheiro de trafego da empresa observou que o numero mınimo de onibus ne-cessarios para atender a demanda varia conforme a hora do dia, como ilustra afigura 2.1, permanecendo constante a cada perıodo de 4 horas, ou turnos. Cada

2.6. Modelos com variaveis inteiras 21

onibus deve comecar a circular no inıcio de um dos turnos indicados e permanecercirculando por 8 horas consecutivas. Deseja-se determinar a quantidade mınima deonibus em operacao por dia que atenda a demanda de passageiros.

Uma primeira abordagem seria imaginar tres perıodos de oito horas (doisturnos), de 8h as 16h, de 16h as 24h e de 24h as 8h, e definir x1, x2 e x3 como osnumeros de onibus comecando o circular nos inıcios destes perıodos. O modelo deotimizacao correspondente seria: minimizar

z = x1 + x2 + x3

sujeito ax1 ≥ 10, x2 ≥ 12 e x3 ≥ 8,

com x1, x2 e x3 representando variaveis inteiras nao-negativas. O numero mınimode onibus por dia seria 30. Entretanto, a abordagem adotada introduz uma restricaoque o problema original nao possui, uma vez que os onibus podem comecar a circularnos inıcios de quaisquer turnos.

PSfrag replacements

44

4

4

8

8

8

10

7

1212

1224 2416 20

No. de Onibus

Hora do Dia

Figura 2.1: Demanda de onibus por turnos.

Sejam entao 1, 2, 3, 4, 5 e 6 ındices indicativos dos turnos comecando as 24h,4h, 8h, 12h, 16h e 20h. Seja xi o numero de onibus que comecam a circular no inıciodo turno i = 1, 2, 3, 4, 5, 6. Aos onibus x1 que comecam a circular as 24h somam-seos onibus que comecam as 20h, e para atender a demanda do turno de 4 horas quecomeca as 24h, deve-se impor que

x1 + x6 ≥ 4.

Procedendo da mesma maneira nos turnos subsequentes de 4 horas, obtem-seo seguinte modelo de otimizacao para o problema da empresa de transportes:

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

minimizar z = x1 + x2 + x3 + x4 + x5 + x6

sujeito a x1 + x6 ≥ 4,x1 + x2 ≥ 8,x2 + x3 ≥ 10,x3 + x4 ≥ 7,x4 + x5 ≥ 12,x5 + x6 ≥ 4,

(2.6)


com x1, x2, x3, x4, x5 e x6 variaveis inteiras nao-negativas. (Observe que a formapadrao da programacao linear nao se aplica a problemas com variaveis inteiras.) Epossıvel mostrar que por meio do modelo (2.6), chega-se ao numero mınimo de 26onibus em circulacao por dia. 2

Exemplo 2.7 Cinco projetos estao sendo avaliados num horizonte de planejamentode tres anos. A tabela 2.3 fornece as receitas esperadas de cada projeto, juntamentocom o gasto previsto e o capital disponıvel para investimento por ano. Os valoresencontram-se em $ milhoes. Deseja-se determinar quais projetos devem ser execu-tados no horizonte de 3 anos de forma obter a maior receita possıvel.

O problema se resume a determinar se um projeto sera ou nao executado, oque pode ser convenientemente representado por uma variavel binaria: para i =1, 2, 3, 4, 5, define-se

xi =

1, se o projeto i e executado,

0, caso contrario.

Tabela 2.3: Parametros dos cinco projetos.Despesa Anual

Projeto 1 2 3 Receita1 5 1 8 202 4 7 10 403 3 9 2 204 7 4 1 155 8 6 10 30

Capital 25 25 25

O modelo de programacao linear inteira a ser utilizado para determinar queprojetos executar seria

∣

∣

∣

∣

∣

∣

∣

∣

maximizar z = 20x1 + 40x2 + 20x3 + 15x4 + 30x5

sujeito a 5x1 + 4x2 + 3x3 + 7x4 + 8x5 ≤ 25,x1 + 7x2 + 9x3 + 4x4 + 6x5 ≤ 25,8x1 + 10x2 + 2x3 + x4 + 10x5 ≤ 25,

(2.7)

com x1, x2, x3, x4 e x5 variaveis binarias. E interessante notar que existem 25 = 32maneiras de se atribuir valores iguais a 0 ou 1 para x1, x2, x3, x4 e x5, e assim obterdiferentes solucoes para o problema. Um metodo simples, que funcionaria para omodelo (2.7) seria:

1. Determine todas as possıveis combinacoes de x1, x2, x3, x4 e x5:

{(0, 0, 0, 0, 0), (1, 0, 0, 0, 0), . . . , (1, 1, 1, 1, 1)};

2.6. Modelos com variaveis inteiras 23

2. Dentre as combinacoes obtidas, descarte as que nao sejam viaveis, como porexemplo, (1, 1, 1, 1, 1);

3. Dentre as combinacoes viaveis, obtenha uma – pode existir mais de uma –que forneca o maior valor para z.

Este tipo de estrategia, chamada de solucao por enumeracao, e claramentelimitada a modelos que apresentem um pequeno numero de variaveis binarias. 2

Exemplo 2.8 Tres companhias telefonicas estao disputando sua preferencia parachamadas de longa distancia. Os servicos oferecidos pelas companhias envolvemum custo fixo mensal – assinatura – e um custo variavel por minuto, resumidos natabela 2.4.

Tabela 2.4: Custos em $ por companhia.Companhia Mensal Por Minuto

1 16 0.252 25 0.213 18 0.22

Voce utiliza uma media de 200 minutos em chamadas de longa distancia pormes, nao paga a assinatura da companhia caso nao faca nenhuma chamada por meiodela, e pode distribuir livremente suas chamadas entre as tres companhias. Comovoce deve utilizar os servicos das companhias de forma a minimizar o valor da suaconta telefonica mensal?

O modelo para este problema envolve custos fixos e custos variaveis, que preci-sam ser refletidos nas variaveis de decisao. Sejam entao x1, x2 e x3 as quantidadesem minutos utilizadas com ligacoes por meio das companhias 1, 2 e 3. Definatambem, para i = 1, 2, 3,

yi =

1, se xi > 0,

0, se xi = 0.

As variaveis binarias y1, y2 e y3 indicam em que situacao os custos fixos dascompanhias devem ser levados em conta. Uma maneira de garantir que yi = 1 sexi > 0 e definindo um numero positivo M suficientemente grande e introduzindo adesigualdade

xi ≤ Myi, i = 1, 2, 3.

Como x1 ≤ 200, i = 1, 2, 3, uma escolha conveniente e M = 200. (Valoresmenores introduziriam restricoes adicionais no modelo.) O modelo de otimizacaoque voce deveria utilizar seria

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

minimizar z = 0.25x1 + 0.21x2 + 0.22x3 + 16y1 + 25y2 + 18y3

sujeito a x1 + x2 + x3 = 200,x1 ≤ 200y1,x2 ≤ 200y2,x3 ≤ 200y3,

(2.8)


com x1, x2 e x3, variaveis nao-negativas, e y1, y2 e y3, variaveis binarias. O mo-delo de programacao inteira (2.8) e misto, pois envolve variaveis reais e inteiras(binarias). Existem 23 = 8 combinacoes de valores para y1, y2 e y3; somente(0, 0, 0) nao e viavel. Como para cada combinacao viavel (2.8) transforma-se nummodelo de programacao linear, uma estrategia de solucao seria: resolva os proble-mas de programacao linear viaveis e determine a solucao otima que forneca o menorvalor. Como comentado anteriormente, estrategias de enumeracao sao limitadas aproblemas com poucas variaveis binarias. 2

Exemplo 2.9 O departamento responsavel pela seguranca de uma universidadeesta discutindo a instalacao de telefones publicos em localizacoes apropriadas docampus. O departamento deseja instalar o menor numero de telefones possıvel,mas de forma que cada uma das ruas principais seja atendida por no mınimo umtelefone. A figura 2.2 e um mapa com as principais ruas do campus, indicadas porletras de A a K. Como o departamento deve alocar os telefones ?

Um telefone localizado em cruzamentos de ruas serve a no mınimo duas ruas.Como existem 8 cruzamentos, numeradas de 1 a 8 na figura 2.2, no maximo 8 tele-fones serao necessarios. E conveniente entao definir as seguintes variaveis binarias:para i = 1, 2, . . . , 8,

xi =

1, se um telefone e instalado no cruzamento i,

0, caso contrario.

PSfrag replacements

1 2 3

4 5

6 7 8

A B

C

DE

FG

H

I

J

K

Figura 2.2: Mapa do campus – principais ruas.

No mınimo um telefone deve atender cada uma das 11 ruas, identificadas porA, B, . . . , K. Para atender a rua A, por exemplo, e possıvel instalar um telefoneno cruzamento 1 ou no cruzamento 2. Uma maneira de indicar esta restricao e pormeio da desigualdade

x1 + x2 ≥ 1.

2.7. Solucao grafica de problemas lineares 25

Restricoes similares sao obtidas para cada uma das ruas do compus. O modelode programacao linear inteira que o departamento de seguranca do campus deveresolver e

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

minimizar z = x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8

sujeito a x1 + x2 ≥ 1, (A)x2 + x3 ≥ 1, (B)x4 + x5 ≥ 1, (C)x7 + x8 ≥ 1, (D)x6 + x7 ≥ 1, (E)x2 + x6 ≥ 1, (F )x1 + x6 ≥ 1, (G)x4 + x7 ≥ 1, (H)x2 + x4 ≥ 1, (I)x5 + x8 ≥ 1, (J)x3 + x5 ≥ 1, (K)

(2.9)

com x1, i = 1, 2, . . . , 8, variaveis binarias. Problemas da forma (2.9) sao chamadosde problemas de cobertura. Um problema geral de cobertura apresenta zeros ouuns como coeficientes dos lados esquerdos das restricoes, restricoes do tipo ”≥ 1” ,e eventualmente custos nao unitarios. No modelo (2.9) admite-se implicitamenteque os custos de instalacao dos telefones sao iguais. 2

2.7 Solucao grafica de problemas lineares

Problemas de programacao linear com ate duas variaveis de decisao podem serrepresentados e resolvidos graficamente. Embora limitada, a representacao graficapermite evidenciar propriedades e as diversas situacoes que podem ser encontra-das ao se resolver problemas com um numero maior de variaveis. Para efeito deexposicao, considere o seguinte problema de programacao linear:

∣

∣

∣

∣

∣

∣

∣

∣

maximizar z = x1 + 2x2

sujeito a x1 + x2 ≤ 8,−x1 + 2x2 ≤ 4,2x1 − x2 ≤ 12,

(2.10)

com x1 ≥ 0 e x2 ≥ 0.

Considere o plano x1 × x2, com os eixos das abcissas e das ordenadas re-presentando possıveis valores para as variaveis de decisao x1 e x2. Cada uma dasrestricoes descreve uma regiao do plano. Para obter a regiao associada a restricaox1 + x2 ≤ 8, descreve-se inicialmente a reta x1 + x2 = 8, que passa pelos pontos(0, 8) e (8, 0). A reta x1 +x2 = 8 divide o plano em dois semiplanos, x1 +x2 ≤ 8 ex1+x2 ≥ 8. A regiao x1+x2 ≤ 8 corresponde ao semiplano que contem a origem doplano, pois 0 + 0 ≤ 8. Repete-se o procedimento para todas as restricoes presentesno modelo. A intersecao das regioes descritas pelos semiplanos representa a regiaoviavel do problema, ilustrada na figura 2.3.


PSfrag replacements

x1

x2

2

20−4

4

41

6

6

8

8

x1 + x2 = 8 −x1 + 2x2 = 4

2x1 − x2 = 12

z = 0

z = 4

z = 8

z = 12

z = 16

z = −4

20

3

4

3

c

Figura 2.3: Representacao grafica do problema (2.10).

A regiao viavel possui infinitos pontos e, em princıpio, qualquer um deles podeser uma solucao otima do problema. Para determinar qual deles produz o maiorvalor para z, usa-se o fato de que x1+2x2 = z descreve uma famılia de retas paralelasde inclinacao −0.5 parametrizada pelo valor de z. Diferentes valores de z levama diferentes pontos de cruzamento com os eixos x1 e x2. Retas correspondentes avalores selecionados de z encontram-se representadas na figura 2.3. Para determinaro sentido de crescimento de z, utiliza-se o conceito de gradiente de uma funcaonum ponto. O vetor gradiente de qualquer funcao diferenciavel z = z(x) de nvariaveis num ponto x = (x1, x2, . . . , xn), denotado por ∇z(x), e o vetor formadopelas primeiras derivadas parciais da funcao no ponto considerado:

∇z(x) =

(

∂z(x)

∂x1

,∂z(x)

∂x2

, . . . ,∂z(x)

∂xn

)

.

O vetor gradiente indica o sentido de maior crescimento da funcao no entornodo ponto considerado. Observa-se que o vetor gradiente de uma funcao linear,

z = c1x1 + c2x2 + · · · + cnxn,

e constante e dado por

c = (c1, c2, . . . , cn).

No caso do exemplo ilustrativo, c = (1, 2). O sentido do gradiente esta indicadona figura 2.3. O vetor gradiente e ortogonal a qualquer reta que descreva um valorpara a funcao objetivo. Dois vetores x, y de n componentes sao ortogonais se o seu

2.7. Solucao grafica de problemas lineares 27

produto escalar, definido por

x1y1 + x2y2 + · · ·xnyn,

e igual a zero. Sejam entao x, y dois pontos quaisquer pertencentes a reta correspon-dente a um valor z = z0 para a funcao objetivo. Neste caso, x1+2x2 = y1+2y2 = z0,e portanto

(x1 − y1) + 2(x2 − y2) = 0,

indicando que os vetores c e x − y, este ultimo sobre a reta associada a z0, saoortogonais.

A maximizacao do valor da funcao-objetivo no problema (2.10) pode ser con-duzida da seguinte forma: percorre-se a regiao viavel do problema no sentido dogradiente (aumentando continuamente o valor da funcao-objetivo) ate que a fron-teira da regiao seja eventualmente atingida. O valor maximo da funcao-objetivo naregiao viavel e dado pelo valor da reta que toca a fronteira, no caso z? = 12. Qual-quer ponto pertencente a reta de valor z? = 12 que tambem pertenca a fronteirae uma solucao otima do problema. No caso do exemplo ilustrativo (2.10), existeapenas uma solucao otima, x? = (4, 4).

Se o objetivo do problema (2.10) fosse, ao inves de maximizar, minimizaro valor de z, adotar-se-ia a direcao contraria a do gradiente – aquela de maiordecrescimento da funcao. O valor mınimo da funcao-objetivo seria z? = 0, obtidono ponto x? = (0, 0). As analises de situacoes mais gerais, a seguir, aplicam-setambem a problemas de minimizacao.

Solucoes otimas unicas e multiplas

A resolucao grafica do problema (2.10) conduz a uma solucao otima unica.Entretanto, e possıvel que exista mais de uma solucao otima para um dado problemade programacao linear. Considere novamente o problema (2.10), mas suponha quea funcao-objetivo foi alterada para

z = x1 + x2.

O procedimento grafico sugerido fara entao com que a reta correspondente aomaior valor de z toque a fronteira em multiplos pontos sobre a reta x1 + x2 = 8.O valor maximo da funcao-objetivo sera z? = 8 e qualquer ponto no segmento dereta que liga os pontos (4, 4) e (20/3, 4/3) e uma solucao otima do problema.

Problemas ilimitados

Nos exemplos tratados ate o momento foi possıvel obter valores maximos li-mitados para a funcao-objetivo por meio de uma ou mais solucoes otimas. Existemsituacoes, quase sempre decorrentes de formulacoes inadequadas do problema, nasquais nao e possıvel limitar superiormente o valor da funcao-objetivo. Suponha queas restricoes x1 + x2 ≤ 8 e 2x1 − x2 ≤ 12 do problema (2.10) sao removidas, comoilustra a figura 2.4. A regiao viavel torna-se aberta na direcao do gradiente, e


sempre sera possıvel obter um valor para a funcao objetivo maior do que o anterior.Um problema linear com essa caracterıstica e chamado de ilimitado. O valor de ztende a +∞ e nao e possıvel caracterizar uma solucao otima para o problema.

PSfrag replacements

x1

x2

2

20−4

4

4

1

6

6

8

8

x1 + x2 = 8−x1 + 2x2 = 4

2x1 − x2 = 12

z = 0

z = 4

z = 8

z = 12

z = 16

z = −420

34

3

c

Figura 2.4: Representacao grafica – problema ilimitado.

Problemas inviaveis

Diz-se que um problema de programacao linear e viavel se existe pelo menosum ponto que satisfaz todas as restricoes do problema, ou seja, se a regiao viaveldo problema e nao-vazia. Caso contrario, diz-se que o problema e inviavel. Todosos exemplos discutidos ate agora referem-se a problemas viaveis. Entretanto, for-mulacoes inadequadas podem levar a problemas inviaveis. Considere, por exemplo,o problema (2.10) com os sinais da segunda e terceira restricoes lineares invertidos:

∣

∣

∣

∣

∣

∣

∣

∣

maximizar z = x1 + 2x2

sujeito a x1 + x2 ≤ 8,−x1 + 2x2 ≥ 4,2x1 − x2 ≥ 12,

(2.11)

com x1 ≥ 0 e x2 ≥ 0. Esta modificacao e suficiente para tornar o problema (2.11)inviavel: a intersecao dos semiplanos gerados pelas tres restricoes e vazia, comoilustra a figura 2.5.

2.8. Revisao de algebra linear e matrizes 29

PSfrag replacements

x1

x2

2

20−4

4

41

6

6

8

8

x1 + x2 = 8 −x1 + 2x2 = 4

2x1 − x2 = 12

z = 0

z = 4

z = 8

z = 12

z = 16

z = −4

20

3

4

3

c

Figura 2.5: Representacao grafica – problema inviavel.

Propriedade fundamental da programacao linear

A intersecao das restricoes do problema (2.10) descreve um polıgono, compontos extremos e arestas conhecidas. A regiao viavel de um problema commais de duas variaveis seria descrita por um poliedro. Os cinco pontos extremosda regiao viavel do problema (2.10) sao (0, 0), (0, 2), (4, 4), (20/3, 4/3), (6, 0). Cincoarestas ligam estes pontos extremos.

A analise grafica do problema (2.10) sugere que solucoes otimas podem sercaracterizadas de duas formas: como um ponto extremo ou como um conjunto depontos sobre uma aresta da regiao viavel. Mas, mesmo neste ultimo caso, pelo menosuma solucao otima e um ponto extremo da regiao viavel. Esta conclusao pode sergeneralizada: se um problema de programacao linear qualquer tiver solucoes viaveisotimas, uma delas sera um ponto extremo da regiao viavel. Assim, embora a regiaoviavel do problema geralmente contenha uma infinidade de pontos, para resolve-lo basta analisar um numero finito de pontos extremos. Para resolver (2.10), porexemplo, bastaria calcular z nos pontos extremos da regiao viavel e declarar solucaootima aquele que produzisse o maior valor. O metodo Simplex para programacaolinear nada mais e do que uma busca orientada de solucoes otimas como pontosextremos da regiao viavel do problema considerado.

2.8 Revisao de algebra linear e matrizes

Interpretacoes geometricas como as apresentadas na secao anterior sao uteis,mas naturalmente limitadas a problemas com duas ou tres variaveis de decisao, nomaximo. Em dimensoes maiores e necessario generalizar nocoes como as de ponto


e reta, e adotar uma representacao adequada para os problemas tratados. Nestasecao sao revistos os principais conceitos de algebra linear e matrizes aplicaveis aoestudo de programacao linear.

Cada conjunto x = (x1, x2, . . . , xn) de valores possıveis para as variaveis dedecisao de um problema linear pode ser visto como um vetor do espaco linear R

n,o que se denota como x ∈ R

n. As quantidades x1, x2, . . . , xn sao as componentesdo vetor x. Dois vetores x, y ∈ R

n sao iguais se xi = yi para todo i = 1, 2, . . . , n.A soma de vetores e a multiplicacao de um vetor por um escalar sao definidasno R

n comox + y = (x1 + y1, x2 + y2, . . . , xn + yn),

αx = (αx1, αx2, . . . , αxn), α ∈ R.

O vetor nulo do Rn e o vetor composto por n valores reais iguais a zero:

0 = (0, 0, . . . , 0).

A distincao entre o vetor nulo do Rn e o real zero sera estabelecida pelo con-

texto. A notacao xji sera empregada para representar a i-esima componente de um

vetor xj . Vetores podem ser representados graficamente associando-se as compo-nentes do vetor a eixos cartesianos. O vetor nulo e representado na interseccaodos eixos, denominada de origem, e um vetor qualquer, como um segmento orien-tado a partir da origem. A figura 2.6 ilustra as operacoes de soma e produto porescalar no R

2.

PSfrag replacements

x1

x2

y1

y2

x1 + y1

x2 + y2 x + y

xx

y

αx

(α > 1)

00

Figura 2.6: Operacoes basicas com vetores do R2.

Combinacao linear

Seja C = {x1, x2, . . . , xk} um conjunto qualquer de k vetores do Rn. Sejam

ainda α1, α2, . . . , αk escalares reais quaisquer. Uma expressao da forma

α1x1 + α2x

2 + · · · + αkxk

e chamada de combinacao linear dos vetores de C, e resulta num vetor do Rn.

Observe o emprego das operacoes de soma, dois-a-dois, e de multiplicacao de vetorespor escalares, introduzidas anteriormente.


Exemplo 2.10 Assuma k = 2, x1 = (1, 0,−1), x2 = (−4, 1, 2), α1 = 1 e α2 = −2.Entao

α1x1 + α2x

2 = 1 · (1, 0,−1) + (−2) · (−4, 1, 2) = (−3,−2,−5).

2

.Uma combinacao linear de vetores pode ser representada graficamente deslo-

cando-se α2x2 para a extremidade de α1x

1, e assim sucessivamente, ate deslocar-seαkxk para a de αk−1x

k−1. A ligacao da origem com a extremidade deslocada deαkxk resulta no vetor gerado pela combinacao linear.

Dependencia linear

Seja C = {x1, x2, . . . , xk} um conjunto qualquer de k vetores do Rn. Diz-se

que C e linearmente dependente se existem escalares α1, α2, . . . , αk, nao todosnulos, tais que

k∑

j=1

αjxj = α1x

1 + α2x2 + · · · + αkxk = 0. (2.12)

Se a igualdade (2.12) for verdadeira somente se α1 = α2 = . . . = αk = 0,diz-se entao que C e linearmente independente.

Exemplo 2.11 Assuma k = 2, x1 = (1, 0,−1) e x2 = (−4, 1, 2). A partir de (2.12),obtem-se

α1x1 + α2x

2 = (α1 − 4α2, α2,−α1 + 2α2) = (0, 0, 0).

Da igualdade de vetores, chega-se ao sistema de equacoes

α1 − 4α2 = 0, (2.13)

α2 = 0, (2.14)

−α1 + 2α2 = 0. (2.15)

Como a unica solucao possıvel para o sistema (2.13)-(2.15) e α1 = α2 = 0, oconjunto C = {(1, 0,−1), (−4, 1, 2)} e linearmente independente. 2

Se um conjunto de vetores e linearmente independente, costuma-se dizer queos vetores do conjunto sao linearmente independentes.

Base e dimensao

Um conjunto C = {x1, x2, . . . , xk}, com xj ∈ Rn, j = 1, 2, . . . , k, e uma base

do Rn se C e linearmente independente e qualquer vetor do R

n pode ser escritocomo uma combinacao linear dos vetores de C. Diz-se neste caso que o conjunto Cgera o R

n.


Exemplo 2.12(a) O conjunto C = {(1, 0, 0), (0, 1, 0} e linearmente independente, mas nem todosos vetores do R

3 podem ser escritos como combinacoes lineares dos vetores de C,como por exemplo x = (0, 0, 1). Logo, C nao e uma base do R

3;

(b) O conjunto C = {1, 0), (0, 1), (1, 1)} nao e linearmente independente, mas gerao R

2. Dado um vetor qualquer x = (x1, x2), basta definir os escalares α1 = x1,α2 = x2 e α3 = 0 para obter x como combinacao dos vetores de C:

x = x1(1, 0) + x2(0, 1) + 0(1, 1).

Entretanto, C nao e uma base do R2;

(c) Os conjuntos C = {(1, 0, 0), (0, 1, 0), (0, 0, 1)} e C = {(1, 0), (0, 1)} sao bases doR

3 e R2, do mesmo modo que C = {(1, 0, 0), (1, 1, 0), (0, 1, 1)} e C = {(1, 1), (0, 1)}.

2

Seja C = {x1, x2, . . . , xk} uma base do Rn. Entao para um dado x ∈ R

n

existem escalares α1, α2, . . . , αk tais que

x = α1x1 + α2x

2 + · · ·αnxk.

Os escalares α1, α2, . . . , αk sao chamados de representacao de x na baseC. A representacao de um vetor varia conforme a base considerada, como ilustra afigura 2.7.

PSfrag replacements

x1

x2

y1

y2

α1x1

α2x2

β1y1

β2y2

x

0

Figura 2.7: Diferentes representacoes para um vetor do R2.

E possıvel mostrar que a representacao de um vetor numa dada base e unica,e que todas as bases possuem exatamente o mesmo numero de vetores. O conjuntode n vetores

C = {(1, 0, . . . , 0), (0, 1, . . . , 0), . . . , (0, 0, . . . , 1)}


e chamado de base canonica do Rn. E linearmente independente e qualquer vetor

pode ser escrito como combinacao linear dos seus vetores. A representacao de umvetor qualquer x na base canonica e α1 = x1, α2 = x2, . . . , αn = xn, se confundindocom o proprio vetor.

Uma vez que o numero de vetores na base canonica e igual a n, e dado quetodas as bases devem conter o mesmo numero de vetores, conclui-se que todas asbases do R

n possuem n vetores. A dimensao de um espaco linear e igual ao numerode vetores nas suas bases. Portanto, a dimensao do R

n e igual a n.

Produto escalar e norma

O produto escalar de dois vetores x, y ∈ Rn e o escalar definido como

〈x, y〉 = x1y1 + x2y2 + · · · + xnyn.

Dois vetores x, y ∈ Rn sao ortogonais se 〈x, y〉 = 0. Um vetor x ∈ R

n eortogonal a um conjunto qualquer de vetores C = {x1, x2, . . . , xk} se 〈x, xj〉 = 0para todo j = 1, 2, . . . , k.

A norma euclidiana de um vetor x ∈ Rn e o escalar definido por

‖x‖ =(

x21 + x2

2 + · · · + x2n

)1/2.

O angulo θ no intervalo [0, π] formado por dois vetores nao-nulos x, y ∈ Rn

pode ser definido como

cos θ =〈x, y〉

‖x‖ ‖y‖.

Conjuntos poliedrais

Seja c ∈ Rn e α ∈ R um vetor nao-nulo e um escalar qualquer, respectivamente.

O conjunto dos pontos

H = {x ∈ Rn : c1x1 + c2x2 + · · · + cnxn = α}

e chamado de hiperplano. Hiperplanos assumem as formas conhecidas de retas eplanos no R

2 e R3, respectivamente. Cada hiperplano determina dois semi-espacos

no Rn:

H− = {x ∈ Rn : c1x1 + c2x2 + · · · + cnxn ≤ α}

e

H+ = {x ∈ Rn : c1x1 + c2x2 + · · · + cnxn ≥ α}.

A interseccao de um numero finito de semi-espacos descreve um poliedro noR

n. A figura 2.8 ilustra poliedros (polıgonos) no R2 descritos por semi-espacos

(semiplanos). As regioes determinadas pelos subespacos estao indicadas por setas.Um poliedro pode ser aberto (figura 2.8(a)) ou fechado (figura 2.8(b)), dependendodos semi-espacos considerados.


Poliedros podem ser caracterizados por meio dos seus pontos extremos,como x1, x2 e x3 nas figuras 2.8(a) e 2.8(b), e direcoes extremas, como d1 e d2

na figura 2.8(a).

PSfrag replacements

d1

d2

x1

x1

x2x2

x3

x3x

x y

y

(a) (b)

Figura 2.8: Poliedros no R2 descritos por semi-espacos.

Poliedros sao conjuntos convexos, no sentido de que se x e y sao vetoresquaisquer contidos num poliedro, entao o vetor

x = λx + (1 − λ)y, λ ∈ [0, 1],

chamado de combinacao convexa de x e y, tambem pertence ao poliedro, qualquerque seja λ ∈ [0, 1]. As combinacoes convexas de dois vetores descrevem um segmentode reta cujas extremidades sao os vetores, como ilustra a figura 2.8.

Matrizes

Uma matriz e qualquer arranjo retangular de numeros. Se o retangulo possuim linhas e n colunas, diz-se que a matriz tem dimensao m × n. O conjunto dasmatrizes reais de dimensao m × n e denotado por R

m×n. Uma matriz A ∈ Rm×n

generica seria

A =

a11 a12 · · · a1n

a21 a22 · · · a2n

......

. . ....

am1 am2 · · · amn

.

Uma matriz A ∈ Rm×n pode tambem ser denotada como A = {aij}. Duas

matrizes A,B ∈ Rm×n sao iguais se aij = bij para todo i = 1, 2, . . . ,m e todo

j = 1, 2, . . . , n. A matriz 0 ∈ Rm×n e a matriz composta apenas por elementos

nulos.


Vetores

Casos especiais importantes sao as matrizes linha e coluna, obtidas quandom = 1 e n = 1, respectivamente. Vetores do R

n podem ser vistos como matrizesx ∈ R

1×n ou x ∈ Rm×1. Neste curso, vetores sao representados por matrizes-colunas

e referenciados na forma usual, x ∈ Rn.

Operacoes basicas

A soma (subtracao) de matrizes A,B ∈ Rm×n e a matriz definida por

A ± B = {aij ± bij}.

A soma de matrizes e comutativa (A+B = B+A) e associativa ((A+B)+C =A + (B + C)).

O produto de uma matriz A ∈ Rm×n por um escalar α ∈ R e a matriz

definida porαA = {αaij}.

O produto de matriz por escalar e comutativo (αA = Aα), associativo ((αβ)A =α(βA)) e distributivo ((α + β)A = αA + βA, α(A + B) = αA + αB.)

O produto de matrizes A ∈ Rm×n e B ∈ R

n×p, de dimensoes compatıveis,e a matriz C ∈ R

m×p definida por

C = AB = {cik =n

∑

j=1

aijbjk}.

O produto de matrizes nao e comutativo, isto e, AB 6= BA, em geral, mesmoquando os dois produtos sao possıveis. O produto de matrizes e associativo ((AB)C =A(BC)) e distributivo com relacao a soma de matrizes (A(B + C) = AB + AC).

A transposta de uma matriz A ∈ Rm×n e a matriz de dimensao n × m

denotada como AT e definida por

AT = {aji}.

Inversa e determinante

Se m = n, diz-se que a matriz e quadrada ou de ordem n. A diago-nal principal de uma matriz quadrada de ordem n e formada pelos elementosa11, a22, . . . , ann. Diz-se que uma matriz quadrada e diagonal se os elementos forada diagonal sao todos nulos. Uma matriz diagonal de ordem n importante e amatriz identidade:

I =

1 0 · · · 00 1 · · · 0...

.... . .

...0 0 · · · 1

.


Dada uma matriz A de ordem n, se existir uma matriz B, tambem de ordemn, tal que

AB = BA = I,

entao que B e a matriz inversa de A. Existindo, a inversa de A e unica. E comumrepresentar a inversa de A como A−1.

O menor ij de uma matriz quadrada A de ordem n e a submatriz denotadapor Aij obtida deletando-se a i-esima linha e a j-esima coluna de A. O determi-nante de A e o escalar representado como det A ou | A |, definido recursivamenteda seguinte forma: se n = 1, entao

det A = a11.

Se n = 2,det A = a11a22 − a21a12.

Se n > 2, seleciona-se qualquer linha i e entao

detA = (−1)i+1ai1(det Ai1) + (−1)i+2ai2(det Ai2)+

· · · + (−1)i+nain(det Ain). (2.16)

Documents

Cap tulo 2 Programa˘c~ao Linear - dt.fee.unicamp.brvalente/capt21_044.pdf · problema da dieta visavam oferecer uma dieta di aria de baixo custo para o Ex ercito Americano e a dieta