EXERCICIOS

1. introducao2. modelagem3. otimalidade4. simplex5. pontos interiores6. geometria7. redes

EXERCICIOS I

1 Liste as principais ferramentas da pesquisa operacional.

2 Busque por pacotes computacionais para resolver problemas de programacaolinear e por ambientes computacionais de desenvolvimento de modelos deprogramacao matematica.

3 Escreva uma sequencia de etapas para resolver problemas que na suaopiniao representa uma aplicacao de pesquisa operacional, de tecnologia dedecisoes, de matematica aplicada ou investigacao operativa.

4 Compare o significado de problema em: problema de transporte, pro-blema no transporte, e sem problema (nao existe versus insignificante versusperdoado).

5 Compare o significado de modelo em: Programacao Linear, Simulacao deSistemas, Sistema Educacional, Parada Modelo e desfile de modas.

6 Compare o significado de metodo em: pesquisa operacional, abordagemde analise e solucao de problemas (MASP).

EXERCICIOS II

Modele como Programas Lineares – Defina as Variaveis de Decisao

1 Empresa trabalha com 3 produtos, P1..P3, e 4 materias primas, M1..M4.Um mınimo de aj unidades dos produtos Pj devem ser produzidos com nomaximo de bi unidades das materias primas Mi. O custo unitario de Mi e cie preco unitario de venda de Pj e dj . Cada unidade de Pj e produzida comeij unidades de Mi. Deseja-se determinar um plano de producao de lucromaximo.

2 Fabrica dispoe de de 300h de maquina, 350h de mao de obra e 400kgde materia prima para fabricar 2 produtos. Cada unidade do produto P1

consome 1h de maquina, 2h de mao de obra e 2kg de materia prima e cadaunidade do produto P2 consome 2h de maquina 1h de mao de obra e 3kgde materia prima. O lucro unitario de P1 e estimado em $5 enquanto que olucro de P2 e $12 para as primeiras 100 unidades e $10 para as unidades de P2

acima de 100 (caso existam). Alem disto, por razoes trabalhistas, a mao deobra alocada na producao de P2 nao pode ser superior a mais da metade damao de obra utilizada na producao dos dois produtos em conjunto. Deseja-semaximizar o lucro total estimado.

3 A previsao de vendas de uma empresa para os proximos 6 meses e 4000,5000, 6000, 7000, 7000, 5000. A capacidade mensal e 6000 (producao) e3000 (estoque). O custo unitario e estimado em $8 (producao) e $3 (estoquemensal). O estoque inicial e 2000 e deseja-se um estoque final de 2000.Determinar um esquema mensal de producao e estoque que minimize o custototal.

4 Deseja-se um plano de 12 meses de producao de custo mınimo para pro-cessamento de um produto a partir da materia prima. Com referencia aomes i, os custos unitarios sao: processamento ai, materia prima bi, estoqueci (mes i para mes i+1); a demanda a ser satisfeita e di, a disponibilidade demateria prima e ei. Cada unidade de produto requer α unidades de materiaprima. A capacidade mensal de producao e β e a capacidade mensal de es-toque e γ. O estoque inicial e δ e deseja-se este mesmo estoque no final. Oproduto pode ser estocado por um mes no maximo e a materia prima naopode ser estocada.

5 Fabrica de suco de laranja com capacidade para espremer c caixas delaranjas por semana esta associada a m pomares da regiao. Cada pomar item ci caixas de laranjas, encontra-se a uma distancia di da fabrica e espera-se uma produtividade de aij toneladas de suco por caixa de laranjas para oprocessamento das laranjas da fazenda i na semana j, j = 1 . . . n. Deseja-se determinar um esquema semanal de colheita e transporte das laranjasdos pomares para a fabrica de modo a produzir a maior quantidade de sucoesperada desde que a distancia total percorrida pelos caminhoes de transportea cada semana nao ultrapasse d. Suponha que cada caminhao transporta ccaixas de laranjas em media.

6 Usina de cana de acucar dispoe de m1 caminhoes pequenos e m2 ca-minhoes grandes para fazer o transporte de cana para a usina a partir den diferentes plantacoes com quantidades bj e distancias dj da usina. Os ca-minhoes pequenos transportam ate a quantidade a1 por viagem a um custoc1/km com velocidade media f1km/h. Os caminhoes grandes transportamate a quantidade a2 por viagem a um custo c2/km com velocidade mediade f2km/h. Determine o numero de viagens que cada caminhao deve fazera cada plantacao de tal modo que o custo total de transporte seja o menorpossıvel e que nenhum caminhao faca mais de 4 viagens, percorra mais de 400km, ultrapasse 8 h de transporte e que a nenhuma plantacao sejam enviadosmais de 10 caminhoes. Suponha que a garagem dos caminhoes e na usina.

7 Determinar coeficientes a, b, c, d de polinomios de terceiro grau y(x) =ax3 + bx2 + cx + d que melhor se ajustam as observacoes (xi, yi) obtidasem um experimento cientıfico. O erro (valor absoluto) de uma observacao eexpresso por | y(xi)− yi |.a) minimizar o erro maximob) minimizar o erro total

x −2 −1 0 1 2y −13 2 3 2 11

8 Fabrica produz bobinas de papel de acordo com pedidos caracterizadospor largura (mm) e quantidade (ton). Estas bobinas sao cortadas a partirde uma esteira de papel com uma largura padrao de 4200mm produzidapor uma unica maquina. As larguras dos pedidos sao combinadas lado alado procurando atingir a largura padrao de 4200mm. Este processo podeproduzir refilos (fitas de papel) causados pela combinacao de larguras que naosomam 4200mm exatamente. Deseja-se determinar um esquema de producao

que atenda aos pedidos com uma tolerancia de ate 10% (em peso) e queminimize a perda total de papel proveniente dos refilos.

largura 1300 1400 1600quantidade 100 150 120

9 Mina a ceu aberto: extracao de blocos de 1m3 Cada bloco de minerioi = 1..n tem um valor vi: valor do minerio menos o custo de extracao.Blocos mais profundos necessitam da extracao de 5 blocos adjacentes nonıvel superior e formam uma rede de predecessores na extracao; consideretais arcos com capacidade cij ilimitada. Considere dois nos adicionais: aorigem 0 e o destino n + 1. Acrescente arcos com capacidade c0i = −vi daorigem a cada bloco com valor ci < 0, e arcos com capacidade cin = vin+1 decada bloco i com valor ci > 0. O fluxo maximo da origem ao destino, quedefine um corte mınimo de valor x0, identifica os blocos a serem extraıdoscom valor total

∑[vi > 0]−x0: todos aqueles com arcos do corte mınimo da

origem e os seus sucessores. Os demais blocos nao devem ser extraıdos.

10 Empresa trabalha com m pontos de origem com quantidades ai demateria prima, n fabricas de processamento com capacidades cj e p cen-tros de distribuicao com demandas bk. Suponha que cada fabrica converte1 unidade de materia prima em 1 unidade de produto. Deseja-se minimi-zar o custo total calculado com os custos unitarios: fij de transporte, gj deprocessamento, hjk de transporte, envolvendo cada do ponto i=1..m, fabricaj=1..n e centro k=1..p.

11 Deseja-se um plano de producao de custo mınimo para os produtosP1..P3 nas maquinas M1..M4. Uma unidade de cada um dos produtosrequer horas de maquina e tem custos de acordo com as tabela abaixo. Ademanda e de 4000, 5000, 3000 unidades dos produtos e a ha a disponibilidadede 1500, 1200, 1500, 2000 horas de maquinas.

custo unitario consumo unitarioM1 M2 M3 M4 M1 M2 M3 M4

P1 4 4 5 7 P1 .3 .25 .2 .2P2 6 7 5 6 P2 .2 .3 .2 .25P3 12 10 8 11 P3 .8 .6 .6 .5

12 Maximizar o lucro lıquido de producao de 2 tipos de fertilizantes (Hi-Fosfato e Lo-Fosfato) utilizando 3 tipos de materias primas de acordo com

os dados da tabela abaixo.

Materia Prima HI-Fosfato LO-Fosfato disponibilidade1 2t/t 1t/t 1500t2 1t/t 1t/t 1200t3 1t/t 0t/t 500t

Lucro($/t) 15 10

13 Minimizar o custo total de producao de J bens produzidos emK fabricasa partir de I recursos. Suponha que sao conhecidos os coeficientes (parai=1..I, j=1..J , k=1..K): aij (quantidade do recurso i necessaria para pro-duzir uma unidade do produto j), cik (custo do recurso i na fabrica k), dik(disponibilidade do recurso i na fabrica k), bj (demanda do produto j), fk(capacidade de producao da fabrica k).

14 A tabela abaixo apresenta a estimativa do numero mınimo de enfer-meiros necessarios para o atendimento em um perıodo de 24 horas em umhospital. O horario de trabalho e de 8 horas para quem entra nos turnos2,3,4,5,6 e de 4 horas para o turno 1. O turno 6 paga uma gratificacao de50%. Elabore um modelo de programacao linear que minimize o gasto coma mao-de-obra.

turno horario enfermeiros1 00− 04 302 04− 08 203 08− 12 504 12− 16 605 16− 20 506 20− 24 40

15 Fazendeiro dispoe de uma area de 200 acres e ja contratou 18000 homens-horas. Ele deseja determinar areas para plantar milho, trigo, quiabo, tomatee feijao para produzir no mınimo 250 toneladas de milho e no mınimo 80toneladas de trigo. A tabela abaixo apresenta os dados que ele considerarelevantes.

Milho Trigo Quiabo Tomate Feijaotonelada/acre 10 4 4 8 6

homem-hora/acre 120 150 100 80 120$/tonelada 120 150 60 80 55

16 Laminadora pretende maximizar o lucro de sua producao semanal (40h)de molas e laminas de aco a partir de placas de aco considerando os dadosabaixo.

Produto Producao(t/h) Preco($/t) Prd. Maxima(t)Molas 200 25 6000

Laminas 140 30 4000

17 PapelBras vende rolos de papel nas larguras 3dm, 5dm e 9dm cortadosa partir de bobinas com 17dm de largura. No momento a empresa tem umacarteira de pedidos de clientes para ser atendida de rolos: 25t de 3dm, 20tde 5dm e 15t de 9dm. As larguras destes rolos devem ser combinadas empadroes de corte com no maximo 17dm causando, em geral, a perda de umrolo de papel ou refilo (um padrao de corte com 2 larguras de 3dm e 2 largurasde 5dm tem um refilo de 17 − 2 × 3 − 2 × 5 = 1dm de largura. Escreva umproblema de programacao linear para:a) minimizar a quantidade total de bobinas de 17dmb) minimizar o desperdıcio total de papel.

Respostas:

01. xj : producao de Pj .02. x1: producao de P1; x2: producao de P2 ate 100t; x3: producao P2 acima de 100t.03. xj : producao do mes j; sj: estoque do mes j para j+1.04. xj : producao do mes j; sj: estoque do mes j para j+1.05. xijk: no. caminhoes do pomar i para fabrica j na semana k.06. xij (yij): no. viagens do caminhao pequeno (grande) i para a plantacao j.07. a, b, c, d: coeficientes do polinomio08. xj : ton. produzidas com a combinacao de corte j09. xi = 0: nao extrair bloco i10. xij , yj, zjk: transporte/producao/transporte11. xij : producao de Pi em Mj12. xj : producao de Hi e Lo-fosfato13. xik, yik: bens e recursos nas fabricas14. xj , sj: enfermeiros iniciando na hora j e total em j15. xj : area para cada cultura.16. xj : producao de molas e laminas17. xj : qtde de corte do padrao j (listar os padroes de corte)

99 Problema de Corte. Carteira de encomendas de bobinas de papel aserem cortadas de uma bobina padrao de 100mm com 100kg:• 40mm com 10kg, • 55mm com 20kg, • 60mm com 15kg.

x1: kg com cortes 40 + 40 ≤ 100 (perde 20)x2: kg com cortes 40 + 55 ≤ 100 (perde 5)x3: kg com cortes 40 + 60 ≤ 100 (perde 0)x4: kg com cortes 55 ≤ 100 (perde 45)x5: kg com cortes 60 ≤ 100 (perde 40)× x6: kg com cortes 40 ≤ 100 (perde 60)

min (20x1 + 5x2 + 0x3 + 45x4 + 40x5)[1/100] (perda)suj (2x1 + x2 + x3) [40/100] ≥ 10 (cliente 1)

(x2 + x4) [55/100] ≥ 20 (cliente 2)(x3 + x5) [60/100] ≥ 15 (cliente 3)x1, x2, x3, x4, x5 ≥ 0

98 Ajuste de Curvas. Deseja-se ajustar um polinomio de terceiro grau

v(t) ≈ a + bt + ct2 + dt3

as observacoes de um fenomeno fısico anotadas a diferentes temperaturas emum experimento cientıfico.

Temperatura t1 t2 · · · tn var. controladaViscosidade v1 v2 · · · vn var. observada

Ou seja, deseja-se determinar a, b, c, d de tal forma que o erro cometido peloajuste seja o menor possıvel. Denote a i-esima observacao por (ti, vi), i =1 . . . 7. Assim, o erro correspondente a esta observacao e

ei = a+ bti + ct2i + dt3i − vi

a) min {∑

e2i } ( quadrados mınimos ) norma L2

equacoes normais:∂∑

e2i∂(a, b, c, d)

= 0

b) min {∑

i |ei| } ( PL ) norma L1

min∑

i(xi + yi)suj (xi − yi) = (a + bti + ct2i + dt3i )− vi ∀i

xi, yi ≥ 0

c) min { maxi |ei| } ( PL ) norma L∞

min zsuj z ≥ (a + bti + ct2i + dt3i )− vi ∀i

z ≥ vi − (a+ bti + ct2i + dt3i ) ∀i

97 Funcao Linear por Partes.a) Minimizar Valor Absoluto.

min{ f(x) + 5y : 3x+ 2y = 60, y ≥ 0 } onde f(x) = 2|x|

a) trocar x pela diferenca de duas variaveis nao negativasb) trocar |x| pela soma destas duas variaveis

min{ 2(x1 + x2) + 5y : 3(x1 − x2) + 2y = 60, x1, x2, y ≥ 0 }

min 2(x1 + x2) + 5ysuj 3(x1 − x2) + 2y = 60

x1, x2, y ≥ 0

(y, x)min⇐⇒ (y, x1, x2)

x1 = +max{0, x} x2 = −min{0, x}

b) Minimizar o Maximo de Funcoes Lineares

min{ f(x) + 5y : 3x+ 2y = 60, y ≥ 0 }

onde f(x) = max{ 2x+ 3, −3x− 2 }

a) trocar f(x) por uma variavel zb) inserir z≥fk(x) para cada fk em f

min z + 5ysuj 3x+ 2y = 60

z ≥ 2x+ 3z ≥ −3x− 2y ≥ 0

(y, x)min⇐⇒ (y, x, z)

z = max{2x+ 3,−3x− 2}

c) Funcao Linear por Partes I

min{ f(x)+5y : 3x+2y = 60, x, y≥0 }, f(x)=

2x x ∈ [ 0, 10]3x+10 x ∈ [10, 25]4x+20 x ∈ [25,∞)

x← x1 + x2 + x3, f(x)← 2x1 + 3x2 + 4x3

min (2x1 + 3x2 + 4x3) + 5ysuj 3(x1 + x2 + x3) + 2y = 60

x1 ∈ [0, 10], x2 ∈ [0, 15=25+10], x3 ≥ 0, y ≥ 0

(y, x)min⇐⇒ (y, x1, x2, x3)

x1 = max{0,min{10, x}}

x2 = max{0,min{15, x-x1}}

x3 = max{0, x− (x1+x2)}

d) Funcao Linear por Partes II

min { f(x)+5y : 3x+2y = 60, x, y≥0 } , f(x)=

2x x ∈ [ 0, 10]3x+10 x ∈ [10, 25]4x+20 x ∈ [25,∞)

f(x)← 2x+ (3-2) δx2 + (4-3) δx3

min 2x+ (3− 2) δx2 + (4− 3) δx3 + 5ysuj 3x+ 2y = 60, x2 ≥ x-10, x3 ≥ x-25

x, δx2, δx3, y ≥ 0

(y, x)min⇐⇒ (y, x, δx2, δx3)

δx2 = max{0, x-10}

δx3 = max{0, x-25}

96 Racao em percentagens (∑

xj = 1)

EXERCICIOS III

A. Mostre que ambos os problemas do par primal-dual de programas line-ares abaixo sao infactıveis.

max x1 + x2

suj x1 − x2 = 1− x1 + x2 = 1

x1 , x2 ≥ 0

min y1 + y2suj y1 − y2 ≥ 1

− y1 + y2 ≥ 1

B. Mostre que para qualquer par primal-dual de problemas:• ou ambos sao factıveis com sol. otimas de mesmo valor,• ou ambos sao infactıveis,• ou um e factıvel com otimo ilimitado e o outro e infactıvel.

Dual.Fac. Dual.Infac.Prim.Fac. otimo finito otimo ilimitadoPrim.Infac. otimo ilimitado sem otimo

1. Escreva o problema dual e as folgas complementares e verifique se x=(0, 1, 2)e uma solucao otima.

min 2x2 + x3

suj x1 + 2x2 + 3x3 = 8x1 + x2 + x3 ≥ 2x1 + x2 = 1x1 , x2 ≥ 0

2. Escreva o problema dual e as folgas complementares e verifique se x=(1, 0, 1)e uma solucao otima.

min 2x1 + 5x2 + 3x3

suj x2 + 2x2 + 3x3 ≥ 4x1 + x3 ≥ 1x1 + x2 = 1x1 , x2 ≥ 0

3. Escreva o problema dual e as folgas complementares e verifique se x=(2, 0, 4, 0)e uma solucao otima.

max 10x1 + 16x2 + 12x3 + 3x4∗suj 3x1 + 4x2 + 2x3 + x4 ≤ 12

5x1 + 3x3 + 2x4 ≥ 20x1 + 2x2 + 2x3 − x4 = 8

x3 , x4 ≥ 0

4. Escreva o problema dual e as folgas complementares e verifique se x=(2, 0,−1)e uma solucao otima.

min 6x1 + 10x2 + 3x3

suj 2x1 + x2 − 2x3 ≥ 62x1 + 2x2 + x3 ≥ 1x1 + 3x2 − x3 = 32x1 + 4x2 + x3 = 3x1 , x2 ≥ 0

5. Escreva o problema dual e as folgas complementares e verifique se x=(α, 1, 2)e uma solucao otima para algum α.

max 3x1 + 4x2 + 3x3

suj x1 + 2x2 + 2x3 ≤ 62x1 + 2x2 + x3 ≤ 2x1 + 2x2 + x3 = 4x1 , x2 ≥ 0

6. Escreva o problema dual e as folgas complementares e verifique se x=(0, 1, α)e uma solucao otima para algum α.

min 3x1 + 4x2 + 3x3

suj x1 + 2x2 + 2x3 ≥ 62x1 + 2x2 + x3 ≥ 2x1 + 2x2 + x3 = 4x1 , x2 ≥ 0

7. Escreva o problema dual e as folgas complementares e verifique se x=(2, 0, α, 0)e uma solucao otima para algum α.

min 2x1 + 4x2 + 3x3 + 3x4

suj x1 + 2x2 + x3 + 2x4 ≥ 32x1 + x2 + x3 + x4 ≥ 4x1 + 2x2 + 2x3 + x4 = 4x1 , x2 ≥ 0

8. Escreva o problema dual e as folgas complementares e verifique se x=(0, α, 2)e uma solucao otima para algum α.

max 2x1 + 4x2 + 5x3

suj 2x1 + x2 + 3x3 ≤ 7x1 + 3x2 + 2x3 ≤ 6x1 + 2x2 + 3x3 = 83x1 + 2x2 + 2x3 = 6x1 , x2 ≥ 0

9. Escreva o problema dual e as folgas complementares e verifique se x=(0, 1, 2, α)e uma solucao otima para algum α.

min 10x1 + 8x2 + 6x3 + 5x4

suj 2x1 + 2x2 + x3 + x4 ≥ 53x1 + 2x2 + 2x3 + x4 ≥ 93x1 + 3x2 + 2x3 + 2x4 = 13x1 , x2 ≥ 0

Respostas:

1. solucao dual infactıvel2. solucao dual infactıvel3. solucao primal infactıvel4. solucao otima5. solucao primal infactıvel6. α = 27. α = 18. solucao primal infactiıvel9. α = 3

99 Problema de regressao L∞ pode ser modelado como:

max{ δ : Ax+ bδ + w = 1, 0 ≤ w ≤ 2, δ, x livres }

onde δ ∈ ℜ, A ∈ ℜm×n, b, x, w, 1, 2 sao vetores com as dimensoes apropriadase m > n.a) Encontre o dual deste problema.b) Determine as condicoes de otimalidade para os problemas primal e dual.c) Escreva o sistema linear que determina as direcoes do metodo primal-dual.

98 Mostre que os dois problemas abaixo sao equivalentes

min{ c′x : b ≤ Ax ≤ b, x ≥ 0 }

min{ c′x : Ax+ s = b, 0 ≤ s ≤ b− b, x ≥ 0 }

97 Mostre que os dois problemas abaixo sao equivalentes

min{ c′x : Ax = b, 0 ≤ x ≤ d }

min{ c′x : Ax = b, x+ s = d, x ≥ 0, s ≥ 0 }

EXERCICIOS IV

A Verifique se os sistemas sao equivalentes (i.e., mesmo conjunto de solucoes)a)

{E1 : x1 + x2 = 4E2 : x1 − x2 = 1

{2E1 + E2 : 3x1 + x2 = 9E1 + 2E2 : 3x1 − x2 = 7

b) (mostre que (x1, x2)=(-1,2) pertence apenas ao 2o. sistema).

{I1 : x1 ≥ 0I2 : x2 ≥ 0

{2I1 + I2 : 2x1 + x2 ≥ 0I1 + 2I2 : x1 + 2x2 ≥ 0

B Obtenha as matrizes inversas de:a) matriz de operacao elementarb) matriz de pivoteamentoc) matriz de permutacao de linhasd) matriz de permutacao de colunas

e)

[1 c′B0 B

]

onde B−1 e conhecida.

C Mostre quea) a inversa da base B e o produto das matrizes de pivoteamento P1, P2, P3b) P1 e o produto das matrizes de operacoes elementares O1, O2, O3c) P2 e o produto das matrizes de operacoes elementares O4, O5, O6d) P3 e o produto das matrizes de operacoes elementares O7, O8, O9e) entao B−1 = O9..O1

xB B−1 x1 x2 x3 x4 x5 b Bx3 1 0 0 1 2 1 600 1 0 0

◦ x4 0 1 0 2 1 1 600 0 1 0x5 0 0 1 1 0 1 250 0 0 1x2 1/2 0 0 1/2 1 1/2 300 2 0 0

• x4 -1/2 1 0 3/2 -1/2 1 300 1 1 0x5 0 0 1 1 0 1 250 0 0 1x2 2/3 -1/3 0 1 2/3 -1/3 200 2 1 1

∗ x1 -1/3 2/3 0 1 -1/3 2/3 200 1 2 1x5 1/3 -2/3 1 1/3 -2/3 1 50 0 1 1

• Matrizes de Operacoes Elementares e de Pivoteamentos • → ∗P: Pivo (3/2) com coluna 1/2, 3/2, 1

O1 : L2′ ← L2/(3/2) (linha do pivo)

O2 : L1′ ← L1− (1/2)L2′

O3 : L3′ ← L3− (1)L2′

O1=

1 0 00 2/3 00 0 1

, O2=

1 -1/2 00 1 00 0 1

, O3=

1 0 00 1 00 -1 1

P=

1 -(1/2)/(3/2) 00 1/(3/2) 00 -1/(3/2) 1

, P−1=

1 1/2 00 3/2 00 1 1

P [ I|A|b ] = O3O2O1 [ I|A|b ]

• Matrizes de Pivoteamentos e Inversas ◦ → • → ∗P1: Pivo 2 na coluna 2, 1, 0 P2: pivo 3/2 na coluna 1/2, 3/2, 1

P1 =

1/2 0 0-1/2 1 0-0/2 0 1

P2 =

1 -(1/2)/(3/2) 00 1/(3/2) 00 -1/(3/2) 1

P−11 =

2 0 01 1 00 0 1

P−12 =

1 1/2 00 3/2 00 1 1

B−1 =

2/3 -1/3 0-1/3 2/3 01/3 -2/3 1

2 1 11 2 10 1 1

= B

B−1 [ I|A|b ] = P2P1 [ I|A|b ]

D Mostre que a inversa da nova base B• pode ser obtida a partir da inversade B◦ com um pivoteamento.

pivo ars : pij =

0 r 6= i 6= j 6= r1 i = j 6= r

1/ars i = j = r−ais/ars i 6= j = r

matriz de pivoteamento

1 0 · · · −a1s/ars · · · 00 1 · · · −a2s/ars · · · 0...

......

......

...0 0 · · · 1/ars · · · 0...

......

......

...0 0 · · · −ams/ars · · · 1

=

1 0 · · · a1s · · · 00 1 · · · a2s · · · 0...

......

......

...0 0 · · · ars · · · 0...

......

......

...0 0 · · · ams · · · 1

−1

pivoteamento: (βij) = B−1 ← P B−1

βij ← βij − βrj ∗ ais/ars i 6= r ∀jβrj ← βrj/ars ∀jbi ← bi − br ∗ ais/ars i 6= rbr ← br/ars

Br ← BP−1r = BAs = BB−1As = As

Bj ← BP−1j = BIj = Bj j 6= r

b ← PB−1b = P b [ b = B−1b ]

P1 0 -1/3 00 1 -2/3 00 0 1/3 00 0 -4/3 1

×

B−1 b As

0 0 0 1 2 10 0 1 0 3 26 3 0 -3 3 31 0 0 0 5 4

→

B−1 b-2 -1 0 2 1 0-4 -2 1 2 1 02 1 0 -1 1 1-7 -4 0 4 1 0

E Problema Canonico min{ c′x : Ax=b, x≥0 }A = B−1A, b = B−1b, c′ = c′ − c′BB

−1AxN = 0, xB = b, y′ = c′BB

−1, z = c = c− A′y

A

c′

b

-b′y

=0

1

B−1

−y′

×A

c′

b

0

︸ ︷︷ ︸

corrente (canonico)

︸ ︷︷ ︸

inverso

︸ ︷︷ ︸

original

! b = B−1b ⇒ b =∑

biBi = Bb As = B−1As ⇒ As = BAs

B, base de A, gera o espaco das colunas de [A|b]

1 Dado o sistema Ax=b, x≥0, determine:a) a inversa da base de xB = (x1, x5, x3)b) a solucao basica associada (e factıvel?).c) as matrizes de operacoes elementares e suas inversas.d) as matrizes de pivoteamento e suas inversas.e) a inversa da base de (x1, x4, x3) com apenas um pivoteamento.f) a solucao basica associada (e factıvel?).g) a equacao da aresta deste pivoteamento.h) a matriz deste pivoteamento e a sua inversa.

2 Considere a solucao basica da base xb = (x1, x2, x3). E factıvel? Escrevaa direcao associada a variavel nao-basica x4 e verifique se e uma direcaode descida. Determine o maior tamanho do passo que pode ser dado nestadirecao sem perder a factibilidade primal e determine a nova solucao basica.Houve reducao no valor da funcao objetivo?

min ( 0 0 0 -2 3 -1 ) xsuj ( 1 0 0 2 -1 -2 ) x = 4

( 0 1 0 -1 2 -1 ) x = 3( 0 0 1 3 -2 0 ) x = 5

x ≥ 0

3 Considere a solucao basica da base xB = (x1, x2, x3). E factıvel? Escrevaa direcao associada a variavel nao-basica x4 e verifique se e uma direcaode descida. Determine o maior tamanho do passo que pode ser dado nestadirecao sem perder a factibilidade primal e determine a nova solucao basica.Houve reducao no valor da funcao objetivo?

min ( -1 0 3 5 -2 1 ) xsuj ( 1 -1 0 3 -3 -1 ) x = 1

( 0 1 -1 -4 4 -1 ) x = -2( -1 1 1 0 1 1 ) x = 4

x ≥ 0

4 Considere a solucao basica da base xB = (x1, x2, x3). E factıvel? Escrevaa direcao associada a variavel nao-basica x5 e verifique se e uma direcaode subida. Determine o maior tamanho do passo que pode ser dado nestadirecao sem perder a factibilidade primal e determine a nova solucao basica.Houve aumento no valor da funcao objetivo?

max ( -1 0 3 5 -2 1 ) xsuj ( 1 -1 0 3 -3 -1 ) x = 1

( 0 1 -1 -4 4 -1 ) x = -2( -1 1 1 0 1 1 ) x = 4

x ≥ 0

5 Resolver pelo metodo simplex a partir de x = (0, 2, 5, 0, 0, 0) associado abase xB = (x1, x2, x3).

min ( 3 3 3 4 3 1 ) xsuj ( 1 1 0 1 0 0 ) x = 2

( -1 0 0 0 1 -1 ) x = 0( 0 -1 1 0 0 1 ) x = 3

x ≥ 0

6 Resolver pelo metodo simplex.

min ( -1 0 0 ) xsuj ( 1 1 -1 ) x ≤ 1

( 1 -1 0 ) x ≤ 2x ≥ 0

7 Resolver pelo metodo simplex dual.

min ( 3 4 2 1 5 ) xsuj ( 1 -2 -1 1 1 ) x ≤ -3

( -1 -1 -1 1 1 ) x ≤ -2( 1 1 -2 2 -3 ) x ≤ 4

x ≥ 0

8 O problema min{c′x : Ax = b, x ≥ 0} tem solucao otima:

min(35 30 60 50 27 22 0 0

)x

suj

[1 0 2 2 1 2 -1 00 1 3 1 3 2 0 -1

]

x =

[919

]

B−1 =

[1 23 2

]−1

=

[−1/2 1/23/4 −1/4

]

xB = (x5, x6)′ = (5, 2)′ y = (3, 8)′ x = (0, 0, 0, 0, 5, 2, 0, 0)′

a) Realizar a analise de pos-otimizacao nesta base otima.b) Obter uma solucao otima depois da inclusao de um novo alimento comc9 = 32 e A9 = (2, 4)′.c) Obter uma solucao otima depois da inclusao de um novo nutriente coma3 = (2, 3, 5, 2, 1, 1, 0, 0) e b3 = 10.d) Qual e o custo marginal de aumentar a quantidade mınima do segundonutriente em 1 unidade? Quanto custa aumentar a quantidade mınima dosegundo nutriente de 19 para 39?e) Suponha que cada unidade adicional do primeiro nutriente traga umareducao de 10 unidades monetarias em despesas medicas. Qual e a novasolucao otima e qual e o nıvel mınimo do primeiro nutriente neste caso?

9 α, β? min{c′x : Ax = b, x≥0} tem base otima B = [A1, A2]

c′ =(4 α 0 0 0

)

A =

[1 1 1 2 20 1 2 1 2

]

b =

[2β

]

B−1 =

[1 10 1

]−1

=

[1 −10 1

]

10 α, β, γ? min{c′x : Ax = b, x≥0} tem base otima xB = (x1, x2, x3)

c′ =(α 1 0 γ 4

)

A =

1 0 0 1 21 1 0 2 21 1 1 1 1

b =

β46

B =

1 0 01 1 01 1 1

1 0 0-1 1 00 -1 1

= B−1

11 Considere o programa min{c′x : Ax = b, x ≥ 0}:

c′ = ( 0 1 0 1 1 )

A =

1 1 0 1 10 1 1 0 11 0 −1

20 1

863

= b

a) Construir um programa linear artificial com no maximo 2 variaveis artifici-ais que tenha uma base factıvel formada pela matriz identidade que pode serusada na fase 1 do metodo simplex. Identifique a solucao basica primal-dualb) Aplicar o metodo simplex a partir da base formada pelas colunas dexB = (x2, x1, x5) onde a base inversa e

B−1 =

1 1 11 0 10 1 1

−1

=

1 0 −11 −1 0−1 1 1

14 O problema min{c′x : Ax = b, x ≥ 0}

c′ = ( 3 +3 1 5 +3 )

A =

1 0 1 1 00 0 1 0 −10 −1 0 1 1

611

= b

tem base otima xB = (x3, x5, x1) com inversa

B−1 =

1 0 11 −1 00 1 0

−1

=

0 1 10 0 11 −1 −1

a) escrever o problema canonico de B e a sua solucao basica.b) obter valores de b3(= 1) onde B permanece otima.c) obter valores de c1(= 3) onde B permanece otima.d) obter uma solucao otima para c4 = −3 (atual 5).

15 O problema min{c′x : Ax = b, x ≥ 0}

c′ = ( +2 +5 +5 +2 +2 +1 )

A =

+3 +3 +3 0 0 0+1 +1 0 0 −1 −10 +2 0 +2 0 −2

+15+1+6

= b

tem base otima xB = (x1, x4, x5) com inversa

B−1 =

+3 0 0+1 0 −10 +2 0

−1

=

1/3 0 00 0 1/2

1/3 −1 0

a) escrever o problema canonico de B e a sua solucao basica.b) obter valores de b1(= 15) onde B permanece otima.c) obter valores de c5(= 2) onde B permanece otima.d) obter uma solucao otima para c2 = 2 (atual 5).

e

16 O problema min{c′x : Ax = b, x ≥ 0}

c′ = ( +2 +6 +5 +3 +2 +1 )

A =

−1 −1 0 0 +1 +1+2 +1 +1 −1 −1 00 +1 0 +1 0 −1

+1+2+3

= b

tem base otima xB = (x1, x4, x5) com inversa

B−1 =

−1 0 +1+2 −1 −10 +1 0

−1

=

+1 +1 +10 0 +1

+2 +1 +1

a) escrever o problema canonico de B e a sua solucao basica.b) obter valores de b1(= 1) onde B permanece otima.c) obter valores de c4(= 3) onde B permanece otima.d) obter uma solucao otima para c2 = 2 (atual 6).e) escrever o problema artificial e a solucao basica inicial do metodo simplexde 2 fases.

17 Resolver o programa linear canalizado

min{ c′x : Ax = b, 0 ≤ x ≤ 10 }

ondec′ = ( +2 +2 +2 +3 +2 )

A =

+1 +1 0 0 0−1 0 +1 +1 00 −1 −1 0 +1

682

= b

a partir da solucao basica x = (6, 0, 4, 10, 6)′ associada a base de trabalho Bformada por {x1, x3, x5}

B−1 =

1 0 0−1 1 00 −1 1

−1

=

1 0 01 1 01 1 1

18 Resolver o programa linear canalizado (0 ≤ x ≤ 5) a partir da solucaobasica x = (3, 0, 2, 5, 3)′ associada a base B formada por xB = (x1, x3, x5)

min(

2 2 2 3 2)

x

suj

1 1 0 0 0−1 0 1 1 00 −1 −1 0 1

x =

341

B−1 =

1 0 0−1 1 00 −1 1

=

1 0 01 1 01 1 1

19 Descrever o metodo simplex especializado para o programa linear padraocom algumas variaveis canalizadas

min

{

c′(

xt

)

: A

(xt

)

= b, x ≥ 0, 0 ≤ t ≤ d

}

20 Descrever o metodo simplex especializado para o programa linear comrestricoes canalizadas.(Sugestao: usar a forma padrao com variaveis canalizadas).

min{c′x : b1 ≤ Ax ≤ b2, x ≥ 0

}

21 Determinar as solucoes factıveis basicas e homogeneas extremas de:a) x1 − x2 ≤ 2, x1 − x2 ≥ −2, x1 + x2 ≥ 1b) x1 − 2x2 ≤ 2, 2x1 − x2 ≥ −2c) x1 + x2 ≥ 4, x1 − 2x2 ≤ 1, x1 − x2 ≥ −2

22 Obter uma solucao basica factıvel a partir da solucao factıvel x =(4, 9, 0, 3) para o sistema Ax = b, x ≥ 0 onde

A =

1 1 0 −31 2 0 −50 −1 1 2

b =

47−3

23 Obter uma solucao basica factıvel a partir da solucao factıvel x =(1, 2, 1, 1) para o sistema Ax = b, x ≥ 0 onde

A =

1 −3 0 −80 0 −2 −2−1 −4 0 −100 0 3 3

b =

−13−4−19

6

24 Obter uma solucao (otima) basica a partir da solucao otima x = (1, 2, 1, 1)para o programa min{ c′x : Ax = b, x ≥ 0 } onde

c 0 0 0 0 b1 −3 0 −8 −13

A 0 0 −2 −2 −4−1 −4 0 −10 −190 0 3 3 6

EXERCICIOS V

1 Mostre que a direcao de Newton aplicada as condicoes de otimalidadecom tamanho de passo α reduz as infactibilidades primal e dual em 1 − αpara o problema canalizado. Ou seja, mostre que:

b−A(x+ αdx) = (1− α)rp

u− x− αdx− v − αdv = (1− α)ru

c− At(y + αdy)− z − αdz + w + αdw = (1− α)rd

para as direcoes dadas pelo metodo primal dual afim escala (µ = 0) canali-zado.

2 Descrever o metodo da trajtoria central para PL na forma

max{ c′x : Ax ≤ b, x ≥ 0 }

3 No desenvolvimento de um metodo primal-dual de pontos interiores parao par primal-dual de programas lineares

min{ c′x : Ax ≥ b } max{ b′y : A′y = c, y ≥ 0 }

e necessario resolver a cada iteracao o sistema

A∆x − ∆s = 0

A′∆y = 0

S∆y + Y∆s = µ1 − SY 1

onde A e uma m × n-matriz de posto completo, s e um vetor de variaveisde folga, µ > 0 e o parametro de centragem que e decrescido a cada iteracaoe as matrizes diagonais S, Y sao construıdas a partir da solucao primal-dualinterior factıvel corrente x, s, y. Suponha que n < m e observe que ∆x e umn-vetor e ∆y,∆s saom-vetores. Obter expressoes para os vetores ∆x,∆s,∆ycujo calculo tenha um esforco computacional limitado pela resolucao de umunico sistema (definido positivo) com n equacoes lineares.

4 No desenvolvimento de um metodo primal-dual de pontos interiores parao par primal-dual de programas lineares na forma canonica

min{ c′x : Ax ≥ b, x ≥ 0 } max{ b′y : A′y ≤ c, y ≥ 0 }

e necessario resolver a cada iteracao o sistema

A∆x − ∆s = 0

A′∆y + ∆z = 0

S∆y + Y∆s = µ1 − SY 1

X∆z + Z∆x = µ1 − XZ1

onde A e uma m × n-matriz de posto completo, s, t sao variaveis de folga,µ > 0 e o parametro de centragem que e decrescido a cada iteracao e asmatrizes diagonais X,S, Y, Z sao construıdas a partir da solucao primal-dual interior factıvel corrente x, s, y, z. Observe que ∆x,∆z sao n-vetorese ∆y,∆s sao m-vetores. Obter expressoes para os vetores ∆x,∆s,∆y,∆zcujo calculo tenha um esforco computacional limitado pela resolucao de umunico sistema (definido positivo) com min{m,n} equacoes lineares (diferentesexpressoes sao obtidas sob cada uma das hipoteses: m < n e m > n).

5 Mostre que uma solucao otima para o programa linear padrao com variaveiscanalizadas

min { c′x : Ax = b, 0 ≤ x ≤ d }

pode ser obtida resolvendo o sistema de equacoes abaixo com µ = 0

Ax = bx+ s = dA′y + z − w = cXZ1 = µ1SW1 = µ1x, s, z, w ≥ 1

6 Obtenha as expressoes utilizadas a cada iteracao do metodo primal dualde pontos interiores para as direcoes de deslocamento das variaveis primaise duais do programa linear padrao com variaveis canalizadasa) a partir de um ponto interior factıvelb) a partir de um ponto interior nao-factıvel

7 Idem para o problema de multiproduto

8 No desenvolvimento de um metodo primal dual de pontos interiores parao programa linear Min{c′x : Ax ≥ b, x ≥ 0} e necessario resolver um sistemade equacoes em ∆x,∆s,∆y,∆z onde A e uma m×n-matriz de posto m(m <n), X,S, Y, Z sao matrizes diagonais conhecidas, 0 = (0, 0..0)′, 1 = (1, 1..1)′ eµ e o parametro de centragem. Obter expressoes para os n-vetores ∆x,∆s e

para os m-vetores ∆y,∆z com esforco computacional limitado pela resolucaode um m×m-sistema de equacoes (definido positivo).

9 O par primal-dual de programas lineares

min{ c′x : b ≤ Ax ≤ d } max{ b′z − d′w : A′z − A′w = c, z, w ≥ 0 }

onde A e uma m×n-matriz vertical (m > n) de posto completo pode ser re-solvido pelo metodo primal-dual de pontos interiores obtendo a cada iteracaoa solucao do sistema

A∆x + ∆s = 0

A∆x − ∆t = 0

A′∆z − A′∆w = 0

S∆z + Z∆s = µ1 − SZ1T∆w + W∆t = µ1 − TW1

onde s, t sao variaveis primais de folga, µ > 0 e um parametro de cen-tragem que e decrescido a cada iteracao e as matrizes diagonais S, T, Z,Wsao construıdas com os elementos da solucao primal-dual interior factıvelx, s, t, z, w corrente. Obtenha as expressoes das direcoes de deslocamento∆x,∆s,∆t,∆z,∆w cujo calculo requeira um esforco computacional limitadopela resolucao de um sistema de equacoes lineares definido positivo em ∆xcom n (n < m) equacoes.

EXERCICIOS VI

1 Determinar as solucoes factıveis basicas e as homogeneas extremas de:a) x1 − x2 ≤ 2, x1 − x2 ≥ −2, x1 + x2 ≥ 1b) x1 − 2x2 ≤ 2, 2x1 − x2 ≥ −2c) x1 + x2 ≥ 4, x1 − 2x2 ≤ 1, x1 − x2 ≥ −2

2 Obter uma solucao basica factıvel a partir da solucao factıvel x = (4, 9, 0, 3)para o sistema Ax = b, x ≥ 0 onde

A =

1 1 0 −31 2 0 −50 −1 1 2

b =

47−3

3 Obter uma solucao basica factıvel a partir da solucao factıvel x = (1, 2, 1, 1)para o sistema Ax = b, x ≥ 0 onde

A =

1 −3 0 −80 0 −2 −2−1 −4 0 −100 0 3 3

b =

−13−4−19

6

4 Obter uma solucao (otima) basica a partir da solucao otima x = (1, 2, 1, 1)para o programa min{ c′x : Ax = b, x ≥ 0 } onde

c 0 0 0 0 b1 −3 0 −8 −13

A 0 0 −2 −2 −4−1 −4 0 −10 −190 0 3 3 6

5 Determine todos os pontos extremos do conjunto poliedrico

{ x1 − x2 + x3 ≤ 1; −x1 + 2x2 ≤ 4; x1, x2, x3 ≥ 0 }

6 Determine todos os pontos extremos da regiao definida pelas inquacoes

x1 + x2 + x3 ≤ 5−x1 + x2 + 2x3 ≤ 6

x1, x2, x3 ≥ 0

7 O conjunto abaixo tem direcoes extremas? Obtenha todos os pontosextremos.

−x1 + x2 = 4x1 − 2x2 + x3 ≤ 6

x3 ≥ 1x1, x2, x3 ≥ 0

8 Identifique as faces, pontos extremos, direcoes extremas e raios extremosdo conjunto abaixo

x1 − x2 + x3 ≤ 102x1 − x2 + 2x3 ≤ 403x1 − 2x2 + 3x3 ≤ 50

x1, x2, x3 ≥ 0

9 Considere o problema

max x1 + 3x2

suj x1 − 3x2 ≤ 3−2x1 + x2 ≤ 2−3x1 + 4x2 ≤ 123x1 + x2 ≤ 9x1, x2 ≥ 0

a) desenhe a regiao factıvel e ache a solucao otimab) identifique todos os pontos extremos e reformule o problema em termosde uma combinacao convexa destes pontos extremosc) elimine a quarta restricao. Identifique os pontos extremos e as direcoesextremas e reformule o problema em termos de uma combinacao convexados pontos extremos e de uma combinacao positiva das direcoes extremas.Resolva o problema resultante.d) O procedimento adotado em b),c) pode ser utilizado para resolver proble-mas grandes?

10 Considere as restricoes abaixo

x1 + x2 ≤ 3−2x1 + x2 ≤ 2x1 − 2x2 ≤ 0x1, x2 ≥ 0

a) desenhe a regiao factıvelb) Identifique os pontos extremos e para cada ponto extremo identifique as

possıveis variaveis basicas e nao-basicasc) Suponha que um movimento seja feito do ponto extremo (2,1) para o pontoextremo (0,0). Especifique as variaveis que entram e as que saem da base.

11 Considere o programa linear:

max 2x1 + x2 − x3

suj x1 + x2 + 2x3 ≤ 6x1 + 4x2 − x3 ≤ 4

x1, x2 ≥ 0

(a) Calcule todos os pontos extremos factıveis da regiao e avalie o valor dafuncao objetivo neste ponto. Qual e a solucao otima ?(b) Argumente porque este procedimento e valido para este problema emparticular.(c) Agora, substitua a primeira restricao por x1 + x2 − 2x3 ≤ 6. Podemosafirmar que o procedimento usado no item (a) pode ser usado neste novo PL?Justifique sua resposta.

12 Considere o PL abaixo:

max 2x1 + x2 + 4x3 + 0x4 + 5x5 + x6

suj 3x1 + 6x2 + 3x3 + 2x4 + 3x5 + 4x6 ≤ 60x1, x2 ≥ 0

Ache todas as solucoes basicas factıveis do problema e ache a solucao otimapor comparacao.

13 Responda as seguintes questoes dando uma explicacao concisa com res-peito ao programa linear para maximizar c′x sujeito a x ∈ X = { x : Ax =b, x ≥ 0 }, onde A e uma matriz m×m de posto m < n.(a) Nas equacoes basicas, se cj − zj = 10 para uma variavel nao-basica xj ,qual e o aumento no valor da funcao-objetivo quando xj entra na base como valor de 2 unidades?(b) Se um ponto extremo e otimo, entao e possıvel que nem todos os cj−zj ≤0 para a base que o representa?(c) Se existe um d tal que Ad = 0, d > 0 e c′d > 0, entao temos uma solucaoilimitada para o problema?(d) Seja uma solucao factıvel com exatamente m componentes positivos. Enecessariamente um ponto extremo de X?(e) Se uma variavel nao-basica xk tem ck − zk = 0 na otimalidade, entaopodemos afirmar que existe uma solucao otima alternativa?

(f) Se xl e x2 sao pontos adjacentes e se Bl e B2 sao as respectivas basesassociadas, entao estas bases diferem em apenas uma coluna. Verdadeiro ouFalso?

14 Considere o PL abaixo:

max 2x1 + x2 + 5x3 − 3x4

suj x1 + 2x2 + 4x3 − x4 ≤ 62x1 + 3x2 − x3 + x4 ≤ 12x1 + 0x2 + x3 + x4 ≤ 4

x1, x2, x3, x4 ≥ 0

(a) Ache a solucao basica factıvel correspondente a base B = [al, a2, a4](b) Esta base e otima? Se nao for, ache a solucao otima a partir desta SBF.

15 Considere o sistema:

x1 + x2 + 2x3 ≤ 2−x1 + 2x2 + 2x3 ≤ 3

xl, x2, x3 ≥ 0

O ponto (1/2,1/2,1/2) e factıvel? Verifique se ele e basico. Se nao, obtenhaa partir deste ponto um ponto basico.

16 Considere o problema abaixo:

max −3xl + 2x2 − x3 + x4

suj 2xl − 3x2 − x3 + x4 ≤ 8−x1 + 2x2 + 2x3 − 3x4 ≤ 10−x1 + x2 − 4x3 + x4 ≤ 3

x1, x2, x3, x4 ≥ 0

Use o metodo simplex para verificar se a solucao otima e ilimitada. Fazendouso da direcao extrema dada pelas equacoes basicas, construa uma solucaofactıvel (nao necessariamente basica) que de um valor para a funcao objetivomaior ou igual a 3000.

17 Considere as equacoes basicas abaixo provenientes de um problema deminimizacao com restricoes do tipo ”≤”(suponha que x3, x4, x5 sao variaveisde folga).

x0 = f − ax2 − bx4

x1 = c+ 2x2 − 1x4

x3 = d+ 1x2 − 2x4

x5 = e +Ox2 − 3x4

Suponha que a < 0, b ≤ 0, c, d, e ≥ 0. Pede-se :(a) Ache B−l.(b) Ache B.(c) Estamos no otimo ?(d) Ache o problema original.(e) Das equacoes dadas, identifique c′BB

−l.Agora suponha que a > 0, b ≤ 0, c, d, e ≥ 0. Pede-se :(f) Estamos no otimo ?(g) De uma direcao extrema.(h) Seja a = 3, f = −8. De uma solucao basica com x0 = −200.

99 Mostre que se o problema

min{ c′x : Ax = b, x ≥ 0 }

tem uma solucao finita, entao o novo problema

min{ c′x : Ax = b, x ≥ 0 }

NAO pode ser ilimitado independentemente do valor que o vetor b.

Respostas:

1 a) x = (0, 2), (0, 1), (1, 0), (2, 0), χ = (1, 1)/31 b) x = (2, 0), (0, 2), χ = (2, 1)/4, (1, 2)/41 c) x = (1, 3), (3, 1), χ = (1, 1)/3, (2, 1)/42. χ = (1, 2, 0, 1), x = (1, 3, 0, 0)

EXERCICIOS VII

1 Suponha que em um tabuleiro de xadrez (8×8) a alocacao de uma pecaem uma casa preta vale o dobro da alocacao em uma casa branca. Determinea alocacao otima de 8 damas de tal forma que nenhuma delas seja ameacadapelas demais.

MS428 WORK 1s04

2/IIa Deseja-se um plano de producao de custo mınimo para os produtosP1..P3 nas maquinas M1..M4. Uma unidade de cada um dos produtosrequer horas de maquina e tem custos de acordo com as tabela abaixo.A demanda e de 4000, 5000, 3000 unidades dos produtos e a ha adisponibilidade de 1500, 1200, 1500, 2000 horas de maquinas.

custo unitario consumo unitarioM1 M2 M3 M4 M1 M2 M3 M4

P1 4 4 5 7 P1 .3 .25 .2 .2P2 6 7 5 6 P2 .2 .3 .2 .25P3 12 10 8 11 P3 .8 .6 .6 .5

9/III Escreva o problema dual e as folgas complementares e verifique sex = (0, α, 2) e uma solucao otima para algum α.

Max 2x1 + 4x2 + 5x3

Suj 2x1 + x2 + 3x3 ≤ 7x1 + 3x2 + 2x3 ≤ 6x1 + 2x2 + 3x3 = 83x1 + 2x2 + 2x3 = 6x1 , x2 ≥ 0

2/IVa Dado o problema abaixo, considere a solucao basica associada a baseB = {x1, x2, x3}. E uma solucao basica primal factıvel? Determine adirecao associada a variavel nao-basica x4 e verifique se e uma direcaode descida. Determine o maior tamanho do passo que pode ser dadonesta direcao sem perder a factibilidade primal e determine a novasolucao basica. Houve reducao no valor da funcao objetivo?

Min ( 0 0 0 -2 3 -1 ) xSuj ( 1 0 0 2 -1 -2 ) x = 4

( 0 1 0 -1 2 -1 ) x = 3( 0 0 1 3 -2 0 ) x = 5