Introdução aos Computadores e à Programação 2007/2008, 2º Semestre 1º Trabalho de OCTAVE Planeamento de um Posto de Abastecimento de Combustível 1. Introdução Pretende-se instalar um posto de abastecimento de combustível numa estrada bastante movimentada mas onde só existem espaços para 6 veículos. Destes alguns serão utilizados nas bombas de abastecimento (entre 1 e 4) e os restantes para os veículos esperarem por uma bomba livre. Como a estrada é muito movimentada, se os 6 lugares estiverem ocupados, então clientes que gostariam de abastecer têm de renunciar ao abastecimento, não entrando no posto e assim se perdendo as respectivas receitas. Existem 3 tipos bombas de abastecimento, rápidas, normais e lentas, com diferentes velocidades de enchimento (e diferentes custos). O objectivo deste trabalho é ajudar o dono do posto de abastecimento a tomar as melhor opção, no que respeita quer à quantidade quer ao tipo das bombas de gasolina a instalar no posto. Para esse efeito deverá ter em conta os seguintes factos: a) O posto funciona diariamente, fechando às 22 h e reabrindo às 6 horas da manhâ seguinte, devendo pois funcionar durante 16 horas seguidas. b) Prevê-se que o tempo entre chegadas de veículos para abastecer siga uma distribuição exponencial (ver abaixo), com tempo médio de 1 minuto entre chegadas consecutivas. c) As bombas normais permitem abastecimentos entre 2 e 4 minutos, enquanto que as rápidas permitem tempos de abastecimento entre 1 e 2 minutos e as lentas entre 3 e 6 minutos. Em qualquer dos casos, admite-se que os abastecimentos tem uma distribuição uniforme entre os limites referidos. d) Os custos/benefícios das bombas são naturalmente diferentes. Mais precisamente: a. As bombas do tipo rápidas têm um custo de 22€ /hora, independente do número de bombas instaladas, a que acresce um custo de 44€ /hora/ bomba e dão um lucro de 2€ por cada minuto de abastecimento (independente da bomba em que o serviço ocorre). b. As bombas normais têm custos/benefícios com a mesma estrutura mas cujos valores são, respectivamente, 10 € / hora, 20 € /hora/ bomba e 1 € /min de abastecimento. c. As bombas lentas têm custos/benefícios com a mesma estrutura mas cujos valores são, respectivamente, 6.5 € / hora, 13 € /hora/ bomba e 0.66 € /min de abastecimento. e) Para além destes custos deve considerar-se um custo associado a cada automóvel que não entra no posto, que reflicta a futura “má-vontade” do respectivo automobilista. De uma forma simplista, pode considerar-se este custo com um valor fixo de 0.5€ por cada automóvel que não chegue a entrar no posto por este estar totalmente preenchido. Adicionalmente deverá ser obtida alguma informação adicional do funcionamento do posto, nomeadamente um gráfico do número de clientes no posto ao longo do tempo e algumas estatísticas, nomeadamente o comprimento médio da bicha, o tempo médio de espera na bicha e o número de clientes que renuncia (isto é, que não entra no posto por este não ter espaço disponível. 2. Especificação do problema O problema deverá então ser resolvido com a definição e utilização das seguintes componentes 1. Simulação do funcionamento do posto de abastecimento; 2. Implementação do gráfico de variação do número de clientes ao longo do tempo; 3. Determinação de estatísticas de funcionamento; 4. Comparação das alternativas existentes de forma a determinar a mais favorável. 2.1 . Simulação do funcionamento do posto Esta função é a componente fundamental do trabalho, e recebe os seguintes parâmetros de entrada: • s: numero de bombas instaladas (parâmetro); • b: número de lugares de fila; • tmin: Tempo mínimo de serviço; • tmax: tempo máximo de serviço; • tmed: tempo médio entre chegadas de viaturas ao posto; • tf: tempo máximo admitido para chegada do último cliente; Sugere-se que a função mantenha (pelo menos) um conjunto de variáveis adicionais, com o seguinte significado: • S: vector com s elementos, numerados de 1 a s. O valor de S(i) será o instante da próxima saída da viatura que ocupa a bomba com número i. Se bomba estiver vazia, S(i) = inf. • to: tempo de saída do primeiro cliente de qualquer das bombas do posto onde possa estar; • so: número da bomba onde se encontra o primeiro cliente a sair do posto; • sl: número de uma bomba livre. Caso nenhuma esteja livre, será sl = 0. • Ti: tempo de chegada ao posto do próximo cliente, que renunciar se o posto estiver cheio. • nr: número de clientes que renunciam a entrar no posto. • ev: contador de eventos. O evento inicial é a abertura do posto, e os restantes eventos são as entradas, renúncias e saídas de viaturas. O último evento é a saída da última viatura do posto; • T: Vector que mantem os instantes em que ocorrem os vários eventos. A abertura do posto, que é o primeiro evento, ocorre no instante 0, pelo que T(1) = 0. • N: Vector que mantem o número de clientes no posto. Mais precisamente, N(ev) é o número de clientes no posto imediatamente a seguit ao evento ev. Por exemplo, se o sexto evento corresponder à entrada de viatura no posto onde se encontram 2 viaturas, teremos T(6) = 3.15 ; N(5) = 2 e N(6) = 3. • ts: tempo total de serviço dos clientes, i.e. a soma dos tempos de utilização de cada uma das bombas do posto; • ni: Número de clientes que já entrou no posto após o último evento; • no: Número de clientes que já saiu do posto após o último evento; Nestas condições, a função de simulação deve ter a seguinte estrutura: function [T, N, ns, nr, ts, tt] = simula_posto(s,b,tmin,tmax,tmed,tf); ... = posto_inicial(s, tmed, tf); while < condição de ciclo > if <evento de entrada> ... = analisa_entrada(...); else % evento de saída ... = processa_saida(...); endif; endwhile; ns = ...; tt = ...; endfunction; devendo ser implementadas as seguintes funções auxiliares: Q1 (1 val) : Especifique a função [ev,T,N,S,so,sl,ti,to,ts,nr, ni,no] = posto_inicial(s,tmed,tf) que inicializa os valores das variáveis [ev,T,N,S,so,sl,ti,to,ts,nr,ni,no] a partir dos argumentos s, tmed e tf. Em particular, deve inicializar-se o primeiro evento (variáveis ev, N e T), o vector S com s elementos correspondentes a bombas vazias, bem como os números ni e no de clientes já entrados e posto e saídos do posto, respectivamente, no instante 0, correspondente ao evento inicial. O tempo ti em que chega a primeira viatura para abastecimento pode utilizar a função t_proximo, descrita abaixo. Os valores de so, sl, e to deverão ser obtidas com a função bombas, definida abaixo. Q2 (1 val) : Especifique as funções t2 = t_proximo(t1, med, tf) Esta função deve ser usada no instante t1 em que chega uma viatura, para determinar o instante t2 em que chegará a viatura seguinte. Mais precisamente, deverá ser t2 = t1 + td, sendo td a solução da equação (onde r é um número aleatório, de 0 a 1) r = 1 − e − td / med Se t1 +td for superior ao tempo tf, admitido para a última entrada, a função deverá retornar inf. Q3 (1 val) : Especifique a função [sl, so, to] = bombas(S) Esta função deve analisar o estado das bombas, retornando os correspondentes valores de sl, so e to. Como indicado anteriormente to será o tempo de saída de um cliente de qualquer das bombas do posto onde possa estar (ou inf se nehuma bomba tiver clientes a abastecer); so será a bomba de onde sairá o primeiro cliente a sair do posto (sendo so = 0 se a bomba estiver sem clientes); e sl é o número de uma bomba livre (caso nenhuma esteja livre, será sl = 0). Q4 (1 val) : Especifique a função t = t_servico(tmin, tmax) Esta função deverá ser usada no instante em que uma viatura entra numa bomba livre, e tem como valor um número aleatório, entre tmin e tmax, obtido a partir dum número aleatório gerado entre 0 e 1 pela função rand(). Q5 (3 val) : Especifique a função [ev,T,ts,N,nr,S,sl,so,ti,to,ni] = analisa_entrada(ev,ni,no,s,b,T,ts,N,nr,S,sl,so,ti,to,tmin,tmax,tmed,tf) que é chamada sempre que o evento corrente for a chegada de um potencial cliente. A função deverá actualizar o contador de eventos, e os vectores T e N. Este último, deverá ser actualizado a partir do novo valor de ni (número de clientes entrado no posto), tendo em atenção que se o posto estiver cheio, a entrada do cliente não se realiza, incrementando-se nr, o contador de renúncias de clientes. De notar, que se a entrada se efectuar com alguma bomba livre, esta deverá ser imediatamente ocupada (actualizando-se naturalmente os valores de sl, so e to, e actualizando-se o valor do tempo de serviço, ts). Q6 (3 val) : Especifique a função [ev, T, N, S, so, sl, to, ts, no] = processa_saida(ev, ni, no, s, b, T, ts, N, to, S, so, tmin, tmax, tf) que é chamada sempre que o evento corrente for a saída de um cliente. A função deverá actualizar o contador de eventos, e os vectores T e N. Este último, deverá ser actualizado a partir do novo valor de no (número de clientes saídos do posto). De notar, que se a saída se efectuar com clientes em espera, um dos clientes deverá ser imediatamente ocupar a bomba libertada (actualizando-se naturalmente os valores de sl, so e to, e actualizando-se o valor do tempo de serviço, ts). Q7 (1 val) : Termine a especificação da função cuja estrutura foi apresentada anteriormente [T, N, ns, nr, ts, tt] =simula_posto(s,b,tmin,tmax,tmed,tf) Especificamente, indique quais as condições de entrada no ciclo e de detecção de um evento de entrada, e ainda a determinação do número total de clientes atendidos, ns, bem como o tempo total, tt, entre a entrada do primeiro cliente e a saída do último cliente. 3. Gráfico de Variação do Número de Clientes no Posto Uma vez feita a simulação, poderá mostrar-se o gráfico de variação dos clientes no posto. Q8 (3 val) : Especifique a função [] = mostra_posto(T, N) A função deverá fazer o gráfico do número de clientes em função do tempo. A informação necessária está contida nos vectores T e N determinados na função simula_posto. No entanto, sendo a função uma função escalão, sugere-se que se adapte as séries de T e N de forma a que cada valor do número de clientes ocorra não só quando se inicia mas até onde se termina. Por exemplo, a partir dos vectores T=[0 0.5 1.1 N=[0 1 2 1.7 1 2.3] ; e 0], correspondentes a entradas nos instantes 0.5 e 1.1 e saídas nos instantes 1.7 e 2.3 deverão criarse os vectores X = [ 0 0.5-δ 0.5 1.1- δ 1.1 1.7- δ 1.7 2.3- δ 2.3] ; e Y= [ 0 0 1 1 2 2 1 1 0 ] a partir do qual se pode usar a função plot do Octave. Q9 (1 val) : Especifique a função [T, N, ns, nr, ts, tt] = posto(s,b,tmin,tmax,tmed,tf, sh) A função recebe os parâmetros s,b,tmin,tmax,tmed e tf com o significado anterior, e mostra ou não os resultados de uma simulação do posto de acordo consoante o parâmetro sh tiver o valor 1 ou 0, respectivamente. Os valores a mostrar são • o gráfico da variação dos clientes (ver função anterior), • os valores das variáveis ns, nr, ts e tt obtidas na simulação do posto • os valores estatísticos obtidos com a função agregar (especificada de seguida). 4. Estatísticas de Funcionamento Q10 (2 val) : Especifique a função [cm_bch, tm_ocp, tm_svc, tm_esp] = agregar(s, ts, tt, ns, T, N) A função deverá calcular os seguintes valores agregados • cm_bch – comprimento médio das bichas. Para a determinar tem de se calcular o tempo total perdido pelos clientes nas bichas, tb, e dividi-lo pelo tempo total tt. • tm_esp – tempo médio de espera nas bichas, determinado através da divisão de tb pelo número de clientes servidos, ns. • tm_ocp – taxa média de ocupação das bombas, obtido pela divisão do tempo de serviço, ts, pelo produto do número de bombas pelo tempo total tt. • tm_svc – tempo médio de serviço, obtido pela divisão do tempo de serviço, ts, pelo número de clientes servidos, ns. 5. Apoio à Decisão Q11 (3 val) : Especifique a função [Lucros, melhor, mb, mn] = plano_posto(tf) A função deverá a partir do tempo, tf, em que são admitidos clientes, simular o posto para os vários cenários, variando o tipo de bombas e o seu número. Para cada simulação deverá ser calculado o lucro obtido tendo em atenção os custos (que requerem o conhecimento do tempo total de abertura do posto, tf, e do número de clientes que renunciam, nr) e os benefícios (que requer o tempo total de serviço, ts). A função deverá assim retornar uma tabela, Lucros, com 3 linhas (uma para cada tipo de bomba) e tantas colunas quantos o número de bombas testado. Dessa matriz Lucros, deverá ser obtido o maior valor (melhor), bem como a linha mb (tipo de bomba) e coluna nb (número de bombas) correspondentes à decisão mais conveniente. 6. Conclusão Como poderá verificar, cada vez que executar a função plano_posto obterá valores (ligeiramente) diferentes para os lucros nas várias configurações do posto, já que a simulação tem componentes aleatórias nas entradas e saídas. Verifique, se a decisão que deverá tomar é robusta, isto é se o número e tipo de bombas que aconselha é o mesmo para várias execuções, ou se se verificam variações significativas da decisão que as várias execuções consideram mais adequada.