[MAC 315] Re: Dúvidas, muitas dúvidas

[Leonidas O Brandao <leo@ime.usp.br>]

Ola'

Vou aproveitar para "publicar" algumas duvidas do Fabio que podem ser
comuns, alem de apontarem alguns erros de gabarito. Mas nao responderei
parte delas por ja' ter feito ou por estar na apostila. Voces precisam ler
com cuidado o material.

On Sat, 22 Jul 2000, Fabio Silva Dias wrote:

> Olá Professor,
> Estive dando uma re-lida na apostila de MAC-315 e refazendo listas e provas.
> Nisto, surgiram algumas dúvidas:
> 1 - Na lista 3, exercício 1.4(iii) Pede-se para provar ou dar um contra
> exemplo de que se poliedro X, escrito na forma [V(X)] + C é limitado => C =
> {0}. Não consigo achar um contra exemplo. Poderia me ajudar?

Esta questao ja' foi discutida em sala. Voce tambem pode encontrar um
resposta (indireta) no exercicio 2.15 (pagina 19 do capitudo 2).

> 2 - Na correção da prova 1, exercício 1.6 parte 2, pede-se o poliedro
> canônico e os vértices correspondentes em um poliedro dado na forma geral.
> Mas achei estranho a resolução pois na mesma b = (2, -1, -1). Só que nas
> restrições que foram dadas, temos 2, 1 e -1. Por que no vetor b, ambos
> são -1?

OK, existia um erro no gabarito, que ja' corrigi. Na prova 1 o correto
era
y_i >= -1. Logo o lado direito do canonico de fato e' b=(2,-1,-1) - se
nao inverterem algum sinal!!

> 3 - Outra dúvida sobre o mesmo exercício, no vértice x2 correspondente a y2.
> Na solução está como x2 = (0,1,3,0,0,0,4) mas y2 = (-1, 2). Não consigo ver
> o porquê do 3 mostrado na solução, nos meus cálculos, x2 deveria ser
> (0,1,2,0,-1,0,3) assumindo b = (2,-1,-1)

Ok, e' isso mesmo (a menos de um "detalhe": veja que colocou um sinal
negativo!). Realmente o ponto que estava la' estava errado, mas se olhasse
a "formula" de transformacao de Y para X (na coluna da esquerda), veria
que o ponto correto seria: (0,1,2,0,1,0,3).
Tb ja' incorporei esta correcao no arquivo ("puxe" novamente).

> 4 - Na correção da prova 1, exercício 1.7 parte 1, há uma implicação ==>
> x(1,2) = A(2,3)^(-1)*b
> O que é A(2,3)^(-1), cujo valor está diferente para achar x1 e depois x2?

Ok, novo erro de digitacao! Corrigi para:

    x^1(1,2) = A(1,2)^(-1)*b

que significa: faca B=(1,2), entao equivale a x^1_B = A_B^(-1)*b
OK?

> 5 - ¿Qual a diferença entre sup e max, inf e min?

Por favor, procure nas apostilas, se nao coloquei avise-me:

    sup {1/n: n natural} = 0, enquanto max {1/n: n natural} indefinido!

(idem para inf/min)

> 6 - A solução ótima de um PLC sempre é um vértice do poliedro de restrição
> ou há outros casos?

Isto e' parte importante de nossa discussao inicial do curso, voce^ nao
acompanhou? 
A conclusao e': se existe solucao otima, entao existira um vertice otimo.
Mas isso NAO implica que sol. otima => toda solucao e' otima, procure um
contra exemplo.

> 7 - No capítulo 3.2 - Um modelo de algoritmo, onde temos a demonstração do
> Algoritmo 1 - Algoritmo combinatório para resolver o (PLC), no passo 2 está
> escrito "encontre v pertencente a argmin{<c,vi> : ..."
> Não deveria ser argmax???

Acho que este e' um erro bastante "antigo", ja' o arrumei fazem varias
semanas. Por favor, pegue a versao nova da apostila no Xerox, no na
pagina. Acabei de colocar como:

 http://www.ime.usp.br/~leo/mac315/00/html/exercicios/cap2-3.ps.gz

> Obrigado e... bem, creio que é "só" isso.
> 
> Saudações,
> Fabio Silva

OK e obrigado pelas correcoes.
Leonidas
 --------------------------------------------------------------------------
 Leônidas de Oliveira Brandão - Computer Science Dep. of IME-USP  (Brazil)
 leo@ime.usp.br - http://www.ime.usp.br/~leo - +55 (011) 818 [6298 | 6135] 
 Interessado em Matemática?  Visite o "iMatica":  http://www.matematica.br