O paradoxo do acondicionamento de esferas

Todos sabemos que os paradoxos são objetos estranhos. Normalmente não gostamos muito de paradoxos porque não percebemos bem o que a natureza nos quer dizer com eles. Neste exemplo, a noção de distância é a usual euclidiana; as esferas são centradas num ponto e têm um raio constante; os cubos são de ângulos retos e de unidades normalizadas.

Espaço bidimensional

Para simplificar, partimos do exemplo 2D, onde 2²=4 circunferências estão centradas nos pontos {(1,1),(1,-1),(-1,1),(-1,-1)} e cada uma tem raio r=1, compactamente acondicionados e inscritos num quadrado 4x4 centrado em (0,0). É sempre possível encaixar o círculo vermelho centrado em O=(0,0) inscrito e portanto tangente às 4 circunferências.

Aqui o raio do círculo vermelho é menor do que meio lado do quadrado L=4/2=2, e por isso o círculo vermelho está contido no quadrado.


Todavia, qual é o raio do círculo vermelho?

O Teorema de Pitágoras (T.P.) aqui diz-nos que a distância de O ao centro de cada uma das 4 circunferências é . Como cada circunferência tem raio r=1, então o círculo vermelho tem raio menor que L=2.

Espaço tridimensional

No caso de dimensão 3D, onde as circunferências passam a esferas teremos 2³=8 esferas centradas nos pontos {(1,1,1),(1,1,-1),(1,-1,1),(1,-1,-1),(-1,1,1),(-1,1,-1),(-1,-1,1),(-1,-1,-1)} e cada uma tem raio r=1, compactamente acondicionadas e inscritas num cubo 4x4x4. É sempre possível encaixar uma esfera púrpura centrada em O=(0,0,0) inscrita e portanto tangente às 8 esferas.

Aqui o raio da esfera púrpura é menor do que meia aresta do cubo L=4/2=2, e por isso a esfera púrpura está contida no cubo.

Todavia, qual é o raio da esfera púrpura?

Mais uma vez podemos responder, com o apoio do T.P., referindo que a esfera púrpura tem raio , ou seja a esfera púrpura tem um raio menor que L=2.

E para esferas no espaço hiperdimensional?

No caso de dimensão 9D, onde as esferas passam a hiper-esferas em 9D teremos 2⁹=512 hiper-esferas centradas nos pontos {(1,1,1,1,1,1,1,1,1),(1,1,1,1,1,1,1,1,-1), ... ,(-1,-1,-1,-1,-1,-1,-1,-1,1),(-1,-1,-1,-1,-1,-1,-1,-1,-1)} e cada uma tem raio r=1, compactamente acondicionadas e inscritas num hipercubo 4x4x4x4x4x4x4x4x4. É sempre possível encaixar uma hiper-esfera negra centrada em O=(0,0,0,0,0,0,0,0,0) inscrita e portanto tangente às 512 hiper-esferas.

Aqui ocorre o início do paradoxo. O raio da hiper-esfera negra é igual à meia aresta L do hipercubo, sendo L=4/2=2, e por isso a hiper-esfera negra está contida no cubo mas é tangente também a ele.

Todavia qual é o raio da hiper-esfera negra?

Mais uma vez podemos responder, com o apoio do T.P., concluindo que a hiper-esfera negra terá um raio igual a:

A partir da nona dimensão em diante, ou seja, para n>9, constata-se todavia que

e por isso a hiper-esfera negra ultrapassará os limites das faces do hipercubo que contém as 2ⁿ hiper-esferas e que inscrevem a hiper-esfera negra. Esta extravasação das faces do hipercubo em nD, acabará por envolver e imergir o hipercubo, fazendo-o quase desaparecer dentro da hiper-esfera negra. 

A partir de n=9 em diante, o raio da hiper-esfera interior, extravasa a face do hipercubo

Todavia, interessantemente, como cada um dos 2ⁿ vértices do hipercubo está à distância da origem O, de

os vértices do hipercubo estarão sempre mais longe da Origem do que os centros das hiper-esferas estão à origem. Por isso, ao acrescentarmos dimensões, a hiper-esfera negra continuará se expandindo contra os vértices nunca extravasando nenhum, porque cada hiper-esfera emparelha com cada um dos vértices do hipercubo. 

A hiper-esfera negra extravasa as faces do hipercubo por entre os interstícios das hiper-esferas.

Programação Linear - Apresentação nas formas Geral, Canónica e Standard

Como foi visto no anterior artigo de Programação Matemática, um Problema de Programação Linear (PPL) após a sua formulação apresenta-se na forma:

Max (ou Min) z = F(x₁, x₂, ..., x_n) = c₁ x₁ + c₂ x₂ + ... + c_n x_n
s.a.
    g₁(x₁, x₂, ..., x_n) = a₁₁ x₁ + a₁₂ x₂ + ... + a_1n x_n, =,b₁
    g₂(x₁, x₂, ..., x_n) = a₂₁ x₁ + a₂₂ x₂ + ... + a_2n x_n, =,b₂

 ...

    g_m(x₁, x₂, ..., x_n) = a_m1 x₁ + a_m2 x₂ + ... + a_mn x_n, =,b_m

Mas esta forma na maior parte das vezes não é adequada como ponto de partida para uma resolução. Existem muitos métodos para resolver problemas de programação linear, e a maior parte deles requer uma simplificação que se traduz na adaptação à notação matricial, e que esta facilmente pode ser introduzida em qualquer aplicação ou folha de cálculo que possua algoritmos de resoluções deste tipo de problemas. Assim, dever-se-á determinar todos os coeficientes efectivos necessários ao uso de qualquer método e algoritmo.

Forma Geral

Aos coeficientes c_i dá-se geralmente o nome de custos.

Este PPL diz-se estar na forma geral porque a função objectivo (f.o.) pode ser maximizada ou minimizada e as restrições podem apresentar qualquer das três formas {,=,}.

Nesta forma admite-se que um PPL possa apresentar variáveis,

não negativas:

não positivas:

livres ou independentes:

Um PPL diz-se estar na forma canónica quando:

- pretende-se maximizar a função objectivo;

- as restrições forem do tipo;

- todas as variáveis forem não negativas:

Ainda, diz-se que um PPL encontra-se na forma standard quando:

- pretende-se maximizar a função objectivo;

- as restrições forem do tipo  = ;

- todas as variáveis forem não negativas:

Para resolver um PPL, é geralmente necessário que se encontre na sua forma mais amigável - a forma standard.

Forma Canónica

Em ordem a transformar um problema na forma geral para a forma canónica, deve tornar-se o problema numa maximização com restrições de sinale variáveis não negativas.

1. No caso de o problema ser uma minimização pode dizer-se que minimizar uma função é equivalente a maximizar a sua simétrica, isto é,

    Min F = Max G (em que G = -F).

2. Para esta forma, pretende-se que todas as restrições figurem com o sinal. Quando as restrições tiverem sinalou  = , deveremos rescrevê-las:

- Se se tiver uma restrição com sinaldevemos multiplicar toda a restrição por -1 (Esta operação nem sempre será útil, pois afectará também o termo independente que poderá ficar negativo).

- Se se tiver uma restrição com sinal  =  é possível rescrevê-la,

a_i1 x₁ + a_i2 x₂ +...+ a_in x_n = b_i <=>

a_i1 x₁ + a_i2 x₂ +...+ a_in x_n <= b_i  e  a_i1 x₁ + a_i2 x₂ +...+ a_in x_n >= b_i

3. Quanto à imposição de não negatividade das variáveis:

- Quando se tem uma variável não positiva x_i <= 0, deve considerar-se y_i = - x_i >= 0, e assim substituir todos os  x_i  por  -y_i  tanto na f.o. como em todas as restrições.

- Quando se tem uma variável livre, deve tomar-se em conta que pode escrever-se x_i como diferença de duas variáveis artificiais não negativas: x_i = y_i - z_i , com  y_i , z_i >= 0  (observe-se que  x_i  permanece livre).

Forma Standard

A passagem à forma standard é mais simples por não envolver mais alterações na f.o. nem nas variáveis, ficando apenas por transformar todas as restrições em igualdades. Este procedimento é conseguido com a introdução de novas variáveis designadas por folgas ou desvios ( f_i >= 0).

Com efeito, verifica-se facilmente que para a restrição i existe um real  f_i >= 0, tal que,

a_i1 x₁ + a_i2 x₂ + ... + a_in x_nb_i  <=>  a_i1 x₁ + a_i2 x₂ + ... + a_in x_n + f_i = b_i     (*)

Em notação matricial, pode escrever-se um PPL na forma standard:

    s.a.

      

      

onde X é vector-coluna das variáveis incluindo as folgas e outras variáveis artificiais que mais tarde poderão figurar no sistema; C^T é o vector-linha dos custos correspondentes; A é matriz de coeficientes das restrições; B é o vector-coluna dos termos independentes (t.i.) das equações das restrições.

Usualmente a resolução por qualquer método de programação linear parte de uma solução inicial ou de arranque, que no caso da Origem do referencial ser uma solução admissível, será poderá ser essa a solução inicial; fazendo x₁, x₂, ..., x_n = 0  então tem-se X = 0 e em (*) f_i = b_i o que significa que se X_f  for o vector-coluna apenas das variáveis de folga e artificiais então X_f = B.

Exemplo 2: Colocar o seguinte programa na forma standard:

       

Pode observar-se que de facto o problema encontra-se na forma geral de acordo com o que se dispôs anteriormente. Mas devem ser feitas algumas alterações para reformulá-lo, primeiro para a forma canónica e depois para a forma standard: 

Na função objectivo: uma vez que Min F = Max G (com G = -F),

    Min  F =  8 x₁ + 4 x₂ - 5 x₃     <=>    Max  G =  - 8 x₁ - 4 x₂ + 5 x₃     

Quando for determinado o valor óptimo G*, então ter-se-á também F* = -G*

Nas restrições

A primeira restrição já está com o tipo que se pretende para a forma canónica.

A segunda restrição será multiplicada por -1, e obter-se-á,

     -3 x₁ + 2 x₂ - 5 x₃-12

A terceira restrição poderá ser rescrita como o sistema,

    - x₁ + 2 x₂ + 2 x₃   = 10  <=>  - x₁ + 2 x₂ + 2 x₃10    e   - x₁ + 2 x₂ + 2 x₃10

e portanto

    - x₁ + 2 x₂ + 2 x₃   = 10  <=>  - x₁ + 2 x₂ + 2 x₃10    e     x₁ - 2 x₂ - 2 x₃-10

Nas variáveis

A variável x₁ é não negativa e não precisa de ser alterada.

A variável x₂ é não positiva, logo devemos considerar y₂ = - x₂0    que é não negativa.

A variável x₃ é livre, mas podemos rescrevê-la como diferença entre duas outras variáveis não negativas: x₃ = y₃ - z₃ , y₃0 , z₃0.

Em resumo, apresenta-se o problema na forma canónica,

Finalmente para concretizar o problema na forma standard, quanto à função objectivo e quanto às variáveis não há nada a alterar; bastará portanto transformar as restrições de  para  = , bastando introduzir as variáveis folga respectivas em cada equação:

Em resumo, apresenta-se o problema na forma standard,

Programação Matemática. Uma introdução à programação linear - Formulação

Problemas de Optimização

Num problema de optimização procura-se maximizar ou minimizar uma quantidade específica que se designa objectivo, a qual depende de um número finito de variáveis iniciais (ou de input). Estas variáveis podem ser independentes entre si ou podem encontrar-se relacionadas através de uma ou mais restrições.

Exemplo 1: O seguinte é um problema de optimização para o objectivo z. (Obs. s.a. = sujeito a...)

Min z = x² + 2 x y + y²
s.a.
    x + y = 2
    x, y >= 0

As variáveis iniciais são x e y, que se encontram restringidas de três formas: x e y devem sempre totalizar 2 e tanto x como y devem ser não negativos. Pretende-se encontrar valores para as variáveis iniciais que minimizem z, o quadrado da sua soma, sujeitos às limitações impostas pelas restrições.

Um Problema de Programação Matemática (PPM) é um problema de optimização no qual o objectivo e as restrições são apresentados como funções matemáticas e relações funcionais. É usual representar um PPM na forma

optimizar: z = f(x₁, x₂, ..., x_n)
s.a.
    g₁(x₁, x₂, ..., x_n) <=, =, >=    b₁
    g₂(x₁, x₂, ..., x_n) <=, =, >=    b₂
    ...
    g_m(x₁, x₂, ..., x_n) <=, =, >=   b_m

onde cada uma das m restrições envolve um dos três sinais de relação <=, =, >=.

Problema de Programação Linear (PPL)

Um problema de programação matemática diz-se linear se f e todas as g_i , i =1, 2, ..., m são funções lineares para todas as variáveis iniciais. Isto é, se

    f(x₁, x₂, ..., x_n) = c₁ x₁ + c₂ x₂ + ... + c_n x_n
e
    g_i(x₁, x₂, ..., x_n) = a_i1 x₁ + a_i2 x₂ + ... + a_in x_n

com  c_i e a_ij (i =1, 2, ..., m ; j =1, 2, ..., n) constantes conhecidas.

Qualquer outro problema que não esteja nesta forma diz-se não linear. Então, o exemplo 1 descreve um problema de programação não linear, na função objectivo z.

Programação Linear Inteira (PPLI)

Um problema de programação linear inteira é um PPL com restrições adicionais que obrigam as variáveis iniciais a serem valores inteiros. Não é necessário que os coeficientes  c_i e a_ij (i =1, 2, ..., m ; j =1, 2, ..., n) da função objectivo e das restrições sejam inteiros, apesar de muitas vezes o serem.

Programação Quadrática (PQ)

Um problema de programação quadrática é um problema de programação matemática no qual cada restrição g_i é uma função linear e a função objectivo é da forma

com c_ij , d_i constantes conhecidas.

O Exemplo 1 é um problema de programação quadrática. As três restrições são lineares, e a função objectivo segue a forma quadrática com n=2 e (fazendo x = x₁ e y = x₂) c₁₁ = c₂₂ = 1  e  c₁₂ = c₂₁ = 1  e  d₁ = d₂ = 0.

Formulação de Problemas

Quase sempre os problemas de optimização académicos são apresentados de forma verbal ou escrita, definindo a optimização pretendida e descrevendo as relações entre as variáveis iniciais. A determinação da solução começa por formular o problema em programação matemática e resolvê-lo recorrendo a técnicas e métodos que serão descritos futuramente em outros artigos neste blog. Para transformar um problema verbal em um problema de programação matemática geralmente seguem-se três passos fundamentais:

1. Determinar a quantidade a ser optimizada e expressá-la numa função matemática. Aqui se definem as variáveis iniciais e a função objectivo.

2. Indentificar todos os requisitos, constragimentos e limitações sobre as variáveis iniciais e expressá-los matematicamente. Estes requisitos constituirão as restrições.

3. Expressar todas as condições ocultas. Estas condições não são estipuladas explicitamente no problema na forma verbal mas são aparentes na situação física que se propõe modelar. Geralmente, envolvem requisitos de não negatividade ou de integridade (valores inteiros) sobre as variáveis iniciais.

Solução

Num problema de programação matemática pretende-se encontrar solução, e se forem encontradas várias soluções igualmente optimais então qualquer uma servirá como solução optimal. Cada conjunto de restrições definirá um espaço de soluções admissíveis designado por poliedro de admissibilidade. A solução optimal do PPM estará sempre sobre a fronteira deste espaço que separa as soluções admissíveis das não admissíveis.

Problema 1

Consideremos que num talho onde se fazem diferentes rolos de carne, se pretende optimizar o custo e a quantidade de gordura no rolo de carne tradicional que consiste numa mista de carne de bovino e de porco. As peças de carne de bovino contêm 75% de carne e 25% de gordura e custa 3 €/kg; as peças de porco contêm 65% de carne e 35% de gordura e custa 3,5 €/kg. Quanto de cada tipo de carne deverá o talho usar em cada kg de rolo de carne se pretender minimizar o custo e manter a quantidade de gordura máxima em 30%?

O objectivo será a minimização do custo z (€) de cada kg de rolo de carne, onde z = 3 x peso de carne bovina + 3,5 x peso de carne de porco.
Definindo

    x = peso de carne bovina usada em cada kg de rolo de carne
    y = peso de carne de porco usada em cada kg de rolo de carne

a função objectivo então será

    Min z = 3 x + 3,5 y

Cada kg de rolo de carne conterá 0,25 x  de gordura de bovino e 0,35 y de gordura de porco. O total de gordura contida em cada kg de rolo de carne não deverá conter mais de 0,30 kg. Logo,

    0,25 x + 0,35 y <= 0,30

As quantidades de carne de vaca e de porco que serão usadas em cada kg de rolo de carne deve portanto somar 1 kg.

    x + y =1

Por fim, uma vez não é concebível e portanto não é admissível usar quantidades negativas de carne, ter-se-á as duas restrições escondidas adicionais x >= 0 e y >=0.

Então tem-se a formulação do PPM seguinte:

Min z = 3 x + 3,5 y
s.a.
    0,25 x + 0,35 y <= 0,30
    x + y =1
    x >= 0, y >=0

Como se pode entender este é um problema de programação linear de apenas 2 variáveis pelo que poderá recorrer-se a uma resolução gráfica.

Observando a figura anexa, a região de admissibilidade - conjunto dos pontos (x,y) que satisfazem todas as restrições é o segmento de recta a cheio. Para determinar o valor minimal de z (z*) deve representar-se graficamente as restrições e a função objectivo. Atribuindo os valores arbitrários z = 2,5 e z = 3,5, obtém-se os objectivos respectivamente

    2,5 = 3 x + 3,5 y    e    3,5 = 3 x + 3,5 y

representados pelas linhas tracejadas.



Assim, pode perceber-se que a solução minimal z* será atingida na extremidade alta do segmento de admissibilidade, e que é o ponto de intersecção das duas linhas

    0,25 x + 0,35 y = 0,30    e    x + y =1

Logo z* = 3,25€ onde x* = 0,5 kg e y* = 0,5 kg é o ponto solução do sistema linear destas duas equações.

Sobre a circularidade da vida

   Ferécides e o seu aluno passeavam desde o meio-dia, conversando sobre temas muito diversos, quando decidiram deter-se para se consolarem e contemplarem melhor a paisagem, recostando-se sobre a erva de um prado numa pequena colina.

... Mantiveram-se em silêncio até o Sol percorrer boa parte do trajecto necessário para consumar a tarde. O rebanho de ovelhas tinha-se aproximado deles. Ferécides, olhando de soslaio para o seu aluno, perguntou-lhe então:

   - Observaste como as ovelhas, vendo-se dispersas, começam a girar em torno do pastor? Este rebanho que temos diante de nós deslocou-se por várias ocasiões. De cada vez que o pastor se sentava num lugar diferente, pouco a pouco, as ovelhas iam criando um círculo novo em seu redor.

   - E que tem isso de particular?

   - É uma demonstração de que a natureza se desenvolve formando círculos.

   - Explica-me isso, mestre, para que possa submeter à minha reflexão.

   Ferécides inclinou-se de novo sobre o prado e, contemplando o infinito, começou a dissertar, lentamente, dando uma entoação poética às suas palavras enquanto se recreava com a sua própria escuta.

   - Tanto o cosmos como a natureza avançam em círculos, ou seja, dando passos que regressam ao mesmo lugar. O final assemelha-se ao início, até se confundem, do mesmo modo que é impossível dizer em que ponto começa e onde termina um círculo. Observa, por exemplo, como os homens, chegados a uma certa idade longeva, se tornam semelhantes às crianças tanto nos seus gostos como no seu comportamento, no seu desamparo e na sua despreocupação pelas coisas do mundo. De um modo inverso, os recém-nascidos assemelham-se a pequenos velhos calvos, enrugados, ausentes do mundo, com a consciência completamente dirigida para o seu interior.

   Observa também de que maneira quem se sente à beira da morte procura regressar, movido por um impulso imperioso, ao sítio onde nasceu.

   Olha como se repetem ao estações: nora que gira ininterruptamente através das idades e que permite à árvore despojar-se das suas folhas para se vestir de novo com elas na Primavera. Contempla a água que desce das montanhas, formando rios até chegar ao mar. Aí, as névoas densas, elevando-se, terminam transformando-se em nuvens; ao viajarem impulsionadas pelo vento, uma vez nas montanhas, descarregam a sua água em forma de neve que, finalmente, depois do Inverno, se derrete dando forma a caudalosos rios que descem até ao oceano, cumprindo assim um rito infatigável.

   Pitágoras interrompeu o discurso do seu mestre.

   - Tudo o que dizes parece-me muito certo, mas, na realidade, não estamos a falar de um círculo.

   - Como assim...? - inquiriu Ferécides, saindo do êxtase que produziam em si as suas próprias palavras.

   Pitágoras insistiu no seu ponto de vista.

   - Não, porque certamente a Primavera regressa depois de cada Inverno, mas não é a mesma Primavera. Para que fosse um círculo deveria ser um retorno ao mesmo lugar e ao mesmo tempo.

   - Vês, Pitágoras, como não sabes interpretar correctamente uma metáfora? De acordo; se falarmos com absoluta precisão, a natureza não descreve um círculo, mas antes uma espiral. Mas por acaso a espiral não é circular? Por favor, meu filho, tem flexibilidade com as imagens metafóricas.

   Pitágoras, como bom discípulo, permaneceu pensativo tentando corrigir o seu erro, o que permitiu a Ferécides embarcar novamente no seu discurso.

   - Os fenómenos próprios da natureza descrevem círculos, mas também os fenómenos cósmicos dispõem do mesmo proceder, uma vez que os planetas e o Sol giram através de um círculo formado pelas constelações zodiacais. Cada dia, a abóbada celeste completa uma rotação em torno da nossa terra. De doze em doze anos, o planeta Júpiter regressa ao mesmo ponto do céu. Para alcançar a mesma estrela que deixou para trás no seu percurso, Saturno precisa de vinte e oito anos. Dois anos necessita Marte para fazer outro tanto.

   Enquanto Ferécides pronunciava estas palavras, a tarde avançava e as andorinhas começavam a apropriar-se do céu. O mestre encontrou a ocasião óptima para relembrar um velho texto poético que escreveu enquanto jovem, e acomodou-o aos seus comentários sobre a circularidade da vida.

   - No mês de Abril regressam as andorinhas. Com o seu ir e vir descrevem anéis cujo perímetro abrange o distante Sul e as nossas latitudes, anéis que enlaçam uma Primavera com a seguinte. Sim, a vida deleita-se expandindo-se ao longo das curvas sensuais que formam os sulcos invisíveis do universo. E tudo quer que cada movimento implique uma partida que não finaliza até regressar ao seu ponto de origem.

   O sol pensava já em retirar-se para a sua mansão subterrânea. Quando se dispuseram a empreender o caminho de regresso, o pastor já se afastava com o seu rebanho.

   - Já não formam um círculo à volta dele - advertiu Pitágoras com ironia!

   - Mas amanhã regressarão ao mesmo prado - respondeu Ferécides, impetuoso.

[...]

E um facto inquestionável é que nada, visto com suficiente distância, se move em linha recta, mas, finalmente, o que julgávamos ser rectilíneo é tão só um segmento de um imenso círculo.

[...]

in Pitágoras, o Filho do Silêncio, Benigno Morilla

Quem era este aluno?

Durante um exame de Física, um professor pôs a seguinte questão aos alunos: 

- "Descreva como determinar a altura de um arranha-céus usando um barómetro". 

Um dos estudantes respondeu: 

- "Amarre uma longa corda à parte mais estreita do barómetro, a seguir faça baixar o barómetro, do telhado do arranha-céus até ao chão. O comprimento da corda mais o comprimento do barómetro será igual à altura do edifício". 

Esta resposta altamente original enfureceu o examinador ao ponto de chumbar o estudante. O aluno recorreu, baseando-se no facto de a sua resposta estar indubitavelmente correcta, e a universidade nomeou um árbitro independente para decidir o caso. O árbitro acabou por decidir que a resposta estava correcta, mas que não demonstrava qualquer conhecimento de Física. 

Para resolver este problema foi decidido chamar o estudante e permitir-lhe que em seis minutos providenciasse uma resposta verbal, que mostrasse, pelo menos, uma certa familiaridade com os princípios básicos da Física. Durante cinco minutos o aluno ficou em silêncio, franzindo a testa a pensar. O árbitro lembrou que o tempo estava a passar, ao qual o estudante respondeu que tinha diversas respostas extremamente relevantes, mas que não sabia qual delas utilizar. Sendo avisado para se despachar, o estudante replicou da seguinte forma: 

"Em primeiro lugar, poderia pegar num barómetro, ir até ao telhado do arranha-céus, deixá-lo cair ao longo da parede e medir o tempo que ele demora a atingir o chão. Desta forma, a altura do edifício poderá ser trabalhada a partir da fórmula: H=0,5.g.t². Mas isto seria má sorte para o barómetro. Ou, então, se o sol estivesse a brilhar, poderia medir a altura do barómetro, depois de assentá-lo na extremidade e medir o comprimento da sua sombra. Em seguida, iria medir o comprimento da sombra do arranha-céus e, depois de tudo isto, seria uma simples questão de aritmética proporcional para calcular a altura do arranha-céus. Mas, se quisesse ser rigorosamente científico acerca disto, poderia amarrar uma longa corda ao barómetro e abaná-lo como um pêndulo, primeiro ao nível do chão e depois ao nível do telhado do arranha-céus. A altura é determinada pela diferença na força da gravidade: T = 2p. Ou, se o arranha-céus tiver uma escada exterior de emergência, seria mais fácil usá-la e marcar a altura do arranha-céus em comprimentos do barómetro, e em seguida adicioná-los por aí acima. Se, simplesmente, quisesse ser chato e ortodoxo na resposta, certamente, poderia usar o barómetro para medir a pressão de ar no telhado do arranha-céus e no solo, e converter os milibars em pés para obter a altura do edifício. Mas uma vez que estamos constantemente a ser exortados a exercitar o pensamento independente e a aplicar os métodos científicos, indubitavelmente a melhor forma seria ir bater ao apartamento do porteiro e perguntar: 'Quer ganhar um barómetro bonito?
Ofereço-lho, desde que me diga a altura deste arranha-céus'."

Quem era este aluno?

Redes de Projecto – Técnicas e Metodologias de Optimização

Um projecto é base para a criação ou construção de uma obra a concretizar. Desde o mais simples ao mais complexo, cada projecto ou cada empreitada passa por várias fases de concepção ou construção:

- Plano geral de enquadramento (quadro geral estratégico da utilidade da obra);

- Programas preliminar e base (onde se definem objectivos, características orgânicas e funcionais, condicionamentos financeiros e prazos);

- Estudo-prévio (onde se desenvolvem as soluções programadas para a concepção geral da obra);

- Ante-projecto (projecto-base e de licenciamento, que visam a avaliação dos parâmetros que caracterizam a melhor alternativa para sua implementação - de mercado, localização, técnicos, dimensão e viabilidade);

- Projecto de execução (onde se definem as condições técnicas, os fornecimentos de materiais, serviços e mão-de-obra necessários à boa execução da empreitada e respectivos custos);

- Execução da obra (empreitada de construção). Cada fase é um conjunto de tarefas específicas a cumprir sob restrições de tempo.

A gestão de projectos acompanha a execução e o ambiente em que um projecto opera, e é um processo fundamental, uma vez que o controlo das actividades do dia-a-dia é importante, mas nem sempre é o suficiente para o cumprimento pleno do objectivo.

Projectos complexos compõem-se de uma série de actividades, algumas das quais devem ser executadas em seqüência e outras que podem ser executadas em paralelo com outras actividades. Este conjunto de tarefas em séries ou paralelas pode ser modelado como uma rede.

Em 1957, o Método do Caminho Crítico (CPM) foi desenvolvido como um modelo de rede para a gestão de projectos; é um método determinístico que usa uma estimativa de tempo para cada actividade.

O CPM é fácil de entender e usar, por não considerar o tempo os variações (erros), mas a falta de percepção desses erros, pode ter um grande impacto sobre o tempo de conclusão de um projecto complexo.

A Avaliação do Programa e Análise Técnica (PERT) é um modelo de rede que permite levar em conta a aleatoriedade dos tempos de conclusão na actividade. O PERT foi desenvolvido no final dos anos 1950, para a Marinha dos Estados Unidos da Polaris project tendo milhares de empresas contratadas. Ela tem o potencial para reduzir o tempo e o custo necessários para concluir um projecto.

O diagrama de rede

Num projecto, uma actividade é uma tarefa que deve ser realizada e um evento é um marco da realização de uma ou mais actividades. Em geral, antes de uma actividade poder iniciar, todas as actividades suas antecessoras devem estar concluídas. Em modelos de rede de projecto, as actividades e marcos de realização são representadas por arcos e nós.

Um gráfico PERT pode ter várias páginas com muitas sub-tarefas. O exemplo seguinte, representa de um diagrama PERT de um projecto muito simples. As actividades encontram-se ordenadas alfabeticamente e imediatamente junto à letra de ordem figura o tempo de duração da actividade, e nos pares de quadrados junto aos marcos de realização figuram os "tempo mais cedo para início" e "tempo mais tarde para início" das actividades subsequentes.

Os marcos de realização são geralmente numerados por ordem crescente por troço. As actividades no diagrama acima são rotuladas com letras junto com o tempo necessário para concluir a actividade.

Etapas da modelação PERT

1. Identificar as actividades específicas e marcos de realização

As actividades são as tarefas necessárias para concluir o projecto, e os marcos de realização são os acontecimentos que marcam o início e o fim das actividades. A listagem das tarefas numa tabela permite uma boa identificação, e em etapas posteriores poderá ser expandida para incluir as informações de seqüência, duração, e locação de recursos, a que se chama de Cronograma.

2. Determinar a seqüência correta das actividades

Esta etapa pode ser combinada com a etapa de identificação uma vez que a sequência das actividades é evidente para algumas tarefas, mas outras podem exigir mais análise para determinar a ordem exata que devem ser realizadas.

3. Construir um diagrama de rede

Uma vez definida a sequência da actividades e os tempos de duração, pode desenhar-se um diagrama de rede mostrando a ordem das actividades em série e das actividades paralelas. As actividades são representadas por linhas orientadas (com setas) e os marcos de realização são representados por círculos numerados. Feito manualmente, podem ser necessários vários projectos para bem retratar as relações entre as actividades, todavia existem aplicações de software que simplificam esta etapa, convertendo automaticamente uma listagem de actividades num diagrama de rede.

4. Estimar o tempo necessário para cada actividade

É comum utilizar semana ou dia como unidade de tempo para as actividades, mas pode ser usada qualquer unidade de tempo que seja razoável.

Uma característica distintiva da técnica PERT é a sua capacidade de lidar com a incerteza dos tempos de conclusão das actividades. Para cada actividade, o modelo geralmente inclui três estimativas de tempo:

Tempo optimista - geralmente o mais curto período de tempo em que a actividade pode ser concluída. É prática comum, especificar tempos otimistas três desvios-padrão abaixo da média, para que haja cerca de um 1% de probabilidade de que a actividade seja concluída dentro do tempo optimista.

Tempo mais provável – é o tempo de conclusão com maior probabilidade. Note-se que este tempo pode ser diferente do tempo esperado.

Tempo pessimista – é o tempo a mais que uma actividade pode exigir. Três desvios-padrão acima da média é uma estimativa usual deste tempo.

A técnica PERT pode assumir distribuições de probabilidade Normais (gaussianas), Exponenciais, Beta ou mesmo outras desconhecidas para fazer estimativas de tempo de duração. Usando por hipótese a  distribuição Beta, o tempo previsto para cada actividade pode ser aproximado usando a seguinte média ponderada:

Tempo esperado = ( Tempo otimista + 4 x Tempo mais provável + Tempo pessimista ) / 6

Este tempo esperado pode ser exibido no diagrama da rede. Para calcular a variância do tempo de conclusão de cada actividade, no caso de ter-se usado três desvios-padrão para os tempos optimista e pessimista (seis desvios-padrão entre eles), pode usar-se:

[( Tempo pessimista – Tempo optimista ) / 6]^2

5. Determinar o caminho crítico (CPM)

O caminho crítico é determinado somando os tempos de duração das actividades de cada seqüência (troço) e determinando o menor caminho do projecto sem atrasos. O caminho crítico determina, no calendário, o tempo total necessário para a elaboração do projecto. Se as actividades fora do caminho crítico se adiantarem ou atrasarem (dentro dos limites), o tempo total do projecto não se altera. O tempo de duração que uma actividade não crítica (fora do caminho crítico) pode ser atrasado sem atrasar o projecto, é definido como Folga (ou Tempo ocioso). Se o caminho crítico não for imediatamente óbvio, pode ser útil para determinar os seguintes tempo para cada actividade:

CI - tempo mais Cedo para Início

CF – tempo mais Cedo para Fecho

TI – tempo mais Tarde para Início

TF – tempo mais Tarde para Fecho

Estes tempos são calculados usando o tempo esperado das actividades com relevância.

Os tempos mais cedo de início e fim de cada actividade calculam-se sequencialmente em tempo crescente através da rede e são determinados pelo momentos em que a actividade pode iniciar e terminar, e que depende a sua antecessora.

Os tempos mais tarde de início e término são o último momento em que uma actividade pode começar e terminar sem atrasar o projecto. TI e TF são determinados sequencialmente para trás através da rede. A diferença entre o tempo mais tarde e o tempo mais cedo para fecho de cada actividade é a folga da actividade.

O caminho crítico é, então, o caminho através da rede, no qual nenhuma das actividades que o compõem tem folga. A variância do tempo de conclusão do projecto pode ser calculada pela soma das variâncias nos tempos de duração das actividades no caminho crítico. Com esta variância, podem calcular-se várias probabilidades, sendo a mais usual, a de que o projecto esteja concluído numa determinada data, assumindo uma distribuição de probabilidade para o caminho crítico. A suposição de distribuição normal de tempos é usual e é sustentada quando o número de actividades no caminho é grande o suficiente para a aplicação do Teorema do Limite Central. Uma vez que o caminho crítico determina a data de conclusão do projecto, o projecto pode ser acelerado, alocando os recursos necessários para fazer diminuir o tempo de duração das actividades do caminho crítico. Tal abreviamento de um projecto às vezes é referido como Project Craching.

6. Atualizar o gráfico PERT à medida que o projecto avança

Actualizações são quase sempre requeridas ao gráfico PERT à medida que o projecto avança. Com o acumular de informação sobre as durações das actividades, as estimativas podem ser substituídas por tempos reais mais fiáveis. Nos casos em que há atrasos, recursos adicionais podem ser necessários de se alocar para minimizar o atraso e o gráfico PERT pode ser ajustado para refletir a nova situação.

Vantagens da técnica PERT

A utilidade dos gráficos PERT reside na obtenção de melhores estimativas para:

- Tempo esperado para conclusão do projecto;

- Probabilidade de conclusão antes de uma data especificada;

- As actividades do caminho crítico que afetam diretamente o tempo de conclusão;

- As actividades que têm tempo ocioso e que podem emprestar recursos para actividades do caminho crítico;

- Datas de início e de término das actividades.

Limitações da técnica PERT

Alguns dos pontos fracos do recurso ao PERT são:

- As estimativas das durações das actividade são subjectivas e dependem de juízo de valores. Nos casos em que há pouca experiência na realização de certas actividades, ou falta de hábitos de cronometragem de outras, as estimativas de duração podem ser apenas supostas. Noutros casos, se uma pessoa ou um grupo que executam certas actividades podem estimar tempo enviesados com alguma tendência enviezadora;

- Mesmo com boas estimativas sobre durações de actividades, a PERT assume uma distribuição Beta para estas estimativas de tempo, mas a distribuição real pode ser diferente;

- Mesmo que por hipótese a distribuição Beta seja a mais adequada, a PERT assume que a distribuição de probabilidade do tempo de conclusão do projecto é a mesma que a do caminho crítico. Porque outros caminhos podem tornar-se em caminho crítico quando as suas actividades associadas são adiadas, a PERT consistentemente subestima a duração esperada e consequentemente a data estimada de conclusão do projecto.

Esta última subestimação da data de conclusão do projecto devido ao facto de outros caminhos alternativos poderem tornar-se críticos, é, talvez, o mais grave dos problemas. Para superar esta limitação, podem executar-se simulações Monte Carlo sobre a rede para eliminar o mais possível esse enviesamento optimista da duração total esperada do projecto.

Matemática, ADN e Nós

Já são muito vulgarizadas, as imagens de núcleos de células biológicas, sejam em fotografias ou infografias, onde podemos comprovar e aprender sobre a sua constituição – os cromossomas. Num núcleo, com um diâmetro aproximado de 5 milionésimos de metro, estão comprimidos os cromossomas, cada qual uma trança enovelada helicoidal de ADN que esticada pode atingir um metro. No entanto, durante a mitose – a replicação da célula – o ADN divide-se, distribuindo os cromossomas em duas cópias da célula original. Já experimentou dividir um emaranhado de fio de lã em dois iguais, sem danificar nenhuma das duas componentes? Pois as células fazem isso quase sem esforço nem danos, apesar do enorme número de nós contidos em seus núcleos.

Desde os anos 80, biólogos e matemáticos (especialistas em Teoria dos Nós – subramo da Topologia) cooperam para tentar compreender os mecanismos de desembaraço dos nós contidos no ADN mitocondrial e replicação celular. As formas possíveis dos nós de ADN têm sido classificadas segundo os seus padrões e suas propriedades topológicas, com a aplicação de metodologias matemáticas da Teoria dos Nós. Um nó matemático, que difere um pouco dos nós físicos que estamos habituados, é uma imersão (a operação inversa de uma projecção) de um círculo no espaço euclidiano tridimensional IR3, e o ADN pode ser modelado como uma faixa topológica, em que as proteínas que o compõem são estudadas quanto ao seu papel no super-enrolamento e compactação no interior do núcleo.

Nas figuras mostram-se nós trifólios de filamentos de ADN, obtidas por observação em microscópio electrónico.