Modelos de optimização

Modelos de Optimização Maria Antónia Carravilla Julho 1997 Modelos de Optimização 1. PROGRAMAÇÃO LINEAR .................................................................................... 1 2. PROBLEMAS DE TRANSPORTES............................................................................ 8 2.1 Tipos de problemas de transportes................................................................... 8 2.2 Exemplo de Problema de Transportes:............................................................... 9 2.2.1 Formulação do problema: ......................................................................... 9 2.3 Regras para a obtenção de uma solução (básica) inicial .........................................11 2.3.1 Regra do canto NW ................................................................................11 2.3.2 Regra dos custos mínimos ........................................................................11 2.3.3 Exemplo .............................................................................................12 2.4 Desequilíbrio entre a oferta e a procura ...........................................................14 2.4.1 Caso 1 - Oferta excessiva.........................................................................14 2.4.2 Caso 2 - Procura excessiva .......................................................................14 2.4.3 Problemas de Maximização.......................................................................15 3. PROBLEMAS DE AFECTAÇÃO..............................................................................16 3.1 Algoritmo Húngaro .....................................................................................19 3.1.1 Aplicação do Algoritmo Húngaro na resolução de um problema de afectação: .........20 3.2 “The Bottleneck assignment problem”..............................................................22 4. ALGUNS PROBLEMAS EM REDES..........................................................................24 4.1 Determinação do caminho mais curto...............................................................24 4.1.1 Algoritmo de Ford..................................................................................24 4.2 Árvore de Suporte de Comprimento Mínimo .......................................................26 4.2.1 Algoritmo guloso (“greedy procedure”)........................................................26 4.3 Determinação do fluxo máximo numa rede de transportes (the maximal flow problem)..27 4.4 Determinação de CIRCUITOS EULERIANOS ..........................................................30 4.4.1 O problema das pontes de Königsberg..........................................................30 4.4.2 O problema do carteiro chinês (chinese postman problem CPP)...........................31 4.5 Determinação de CIRCUITOS HAMILTONIANOS .....................................................31 4.5.1 Definição de Circuitos Hamiltonianos ..........................................................31 4.5.2 O problema do Caixeiro Viajante (travelling salesman problem TSP).....................32 5. PROGRAMAÇÃO DINÂMICA ................................................................................33 Modelos de Optimização 1. PROGRAMAÇÃO LINEAR Consideremos o caso, extremamente simplificado de uma empresa que pretende fabricar dois produtos A e B, usando os recursos que tem disponíveis, que são trabalho e materiais. Para produzir uma unidade de A ou de B, são necessários as quantidades de cada um dos recursos apresentadas na tabela seguinte: Trabalho (horas/home m) Materiais (kg) A 2 4 B 1 5 Numa semana estão disponíveis as seguintes capacidades: Trabalho 125 hom. . 40 horas Materiais 15 000 kg Admite-se que tudo o que é produzido será vendido, e que os lucros unitários para A e para B são respectivamente de 10 e de 7 conto (isto é, uma unidade vendida de A corresponde a um lucro de 10 contos). Pretende-se saber quanto deve ser fabricado de cada um dos produtos, se quisermos, por exemplo, maximizar o lucro semanal. Para isso vamos definir duas variáveis (correspondentes às decisões a tomar): x1 - quantidade a fabricar de A por semana; x2 - quantidade a fabricar de B por semana. A quantidade de trabalho necessário para produzir x1 unidades de A e x2 unidades de B, será: 2x1 + x2 quantidade esta que não poderá ultrapassar a disponibilidade semanal do recurso trabalho. A quantidade de materiais necessários para produzir x1 unidades de A e x2 unidades de B, será: Maria Antónia Carravilla - FEUP 1 Modelos de Optimização 4 x1 + 5 x2 quantidade esta que não poderá ultrapassar a disponibilidade semanal do recurso materiais. lucro obtido será: f = 10x1 + 7x2 Obtém-se assim um modelo de optimização, da classe designada por programação linear, consistindo em: maximizar: f = 10 x1 + 7 x2 sujeito a: 2 x1 + x2 ≤ 5000 4 x1 + 5 x2 ≤ 15000 x1 , x2 ≥ 0 A região das soluções admissíveis para este problema (isto é, possíveis de serem implementadas na prática) está representada graficamente a escuro na Figura 1.1 (onde os eixos representam as quantidades a produzir): 5000 3000 2500 3750 x2 x1 Figura 1.1Região das soluções admissíveis No quadro seguinte apresentam-se algumas soluções possíveis para este problema, e que coincidem com os vértices do polígono representado: x1 2500 1666 0 0 x2 0 1666 3000 0 lucro 25000 28322 21000 0 2 Maria Antónia Carravilla - FEUP Modelos de Optimização A solução óptima encontra-se entre as soluções apresentadas no quadro, e é a que está a carregado (a essa solução corresponde obviamente o lucro máximo). Neste caso os valores óptimos para as quantidades de A e de B são inteiros; no entanto podia não ter acontecido isso, isto é, as soluções podiam ser fraccionárias. Nesse caso, se não fossem permitidas soluções fraccionárias, seria necessário usar Programação Inteira. Para resolver problemas de programação linear, podemos utilizar o algoritmo do SIMPLEX que se encontra disponível no mercado implementado em inúmeros “packages” de software (como é o caso do Sistema de Apoio ao Planeamento STORM). Na Figura 1.2 apresenta-se a recta (a tracejado) da solução do problema com lucro=21 000. 5000 3000 2500 3750 x2 x1 Figura 1.2 - Solução do problema com lucro = 21 000 Para resolver um problema pelo método Simplex, é necessário começar por passar o problema para a forma canónica. Na forma canónica as restrições terão que ser igualdades, sendo necessário introduzir variáveis de folga (slack). Para passar as desigualdades de ≤ para igualdades, é necessário introduzir uma variável de folga si, para passar as desigualdades de ≥ para igualdades, é necessário introduzir uma variável de folga -si. Neste caso teremos que introduzir uma variável de folga s1, correspondente à quantidade de material não usado e uma variável de folga s2, correspondente à quantidade de trabalho não usado. Forma canónica do problema de P.L.: maximizar: Maria Antónia Carravilla - FEUP 3 Modelos de Optimização f = 10 x1 + 7 x2 sujeito a: 2 x1 + x2 + s1 = 5000 4 x1 + 5 x2 + s2 = 15000 x1, x2, s1 , s2 ≥ 0 Forma tabular: BASE x1 x2 s1 s2 s1 2 1 1 0 5000 s2 4 5 0 1 15000 f 10 7 0 0 0 Neste momento s1, s2 estão na base e por isso são diferentes de 0, e x1, x2 estão fora da base e por isso são =0. Uma solução básica admissível para este problema seria:     s1=5 s2=15000 x1=0 x2=0 , que corresponde a um vértice (a origem) do polígono das soluções admissíveis. Inicia-se agora um processo iterativo, em que por cada iteração uma variável entra na base (vértice adjacente do poliedro), com aumento do valor de f, até se atingir o óptimo. Exercício: Resolver este problema , utilizando o algoritmo SIMPLEX Regras: • Entra na base a variável com coeficiente mais positivo em f, x1 neste caso. • Sai da base a variável que primeiro se anula, quando a que entra vai aumentando de valor, s1neste caso. Ir resolvendo o sistema de equações para as variáveis que estão na base BASE x1 x2 s1 s2 <- s1 2 1 1 0 5000 4 Maria Antónia Carravilla - FEUP Modelos de Optimização s2 4 5 0 1 15000 f 10 7 0 0 0 î A variável que entra na base é x1, e a variável que sai da base é s1, dado que: s1=5000 - 2x1 - x2 s2=15000 - 4x1 - 5x2 BASE x1 x2 s1 s2 x1 1 0.5 0.5 0 2500 <- s2 0 3 -2 1 5000 f 10 2 -5 0 -25000 î A variável que entra na base é x2, e a variável que sai da base é s2. BASE x1 x2 s1 s2 x1 1 0 5 6 1 6 1666 x2 0 1 -2 3 1 3 1666 f 10 2 -11 3 2 3 85000 3 Solução óptima:     x1=1666 x2=1666 s1=0 s2=0 No caso de se tratar de um problema de minimização, pode-se fazer min f = max (-f) ou usar um critério inverso de entrada das variáveis na base, (entra a que tem um coeficiente mais negativo) Situações especiais que podem surgir na resolução de um problema de programação linear: 1. Inexistência de soluções admissíveis; 2. Solução óptima não limitada; 3. Mais do que uma solução óptima; 4. Empate no critério de entrada na base; Maria Antónia Carravilla - FEUP 5 Modelos de Optimização 5. Degenerescência. No caso de haver desigualdades de ≥ ou igualdades, devem-se introduzir variáveis artificiais, para obtenção de uma solução inicial. Exemplo: x1 x2 A B C D maximizar: 2x1 + x2 sujeito a: x1 ≥ 1 x1 + x2 ≤ 3 x1 ; x2 ≥ 0 Forma canónica: maximizar: 2x1 + x2 sujeito a: x1 - s1 + a1 = 1 x1 + x2 + s2 = 3 onde a1 é uma variável artificial, que se introduz apenas para obter uma solução básica admissível. Assim o problema será dividido em duas fases: Numa primeira fase vamos minimizar uma função objectivo igual ao somatório das variáveis artificiais: fase 1 min F= _ai =a1 O mínimo corresponderá a ∀ai=0 e F=0. 6 Maria Antónia Carravilla - FEUP Modelos de Optimização Numa segunda fase vamos então maximizar a função objectivo f: fase 2 max f Segue-se o primeiro quadro simplex para o problema do exemplo: x 1 x2 s1 s2 a1 a1 1 0 -1 0 1 1 s2 1 1 0 1 0 3 min F 0 0 0 0 1 0 -1 0 1 0 0 -1 max f 2 1 0 0 0 0 Para resolver a fase 1, vamos começar por minimizar F. Nesse caso, x1 entra na base e a1 sai da base. Como todas as variáveis artificiais já saíram da base (F=0), pode-se eliminar a linha de F e a coluna de a1 do quadro, e passamos a ter um problema semelhante ao do primeiro exemplo, podendo prosseguir agora na tentativa de maximizar f. Maria Antónia Carravilla - FEUP 7 Modelos de Optimização ui\vj C 1 C 2 C 3 F1 1 - 1 2 7 3 4 F2 3 - - 3 2 1 3 F3 - 1 4 5 3 4 6 4 1 5 Custo da nova solução: 1x7 + 1x4 + 3x2 + 1x4 + 4x6 = 45. 2.4 Desequilíbrio entre a oferta e a procura 2.4.1 Caso 1 - Oferta excessiva É necessário considerar um consumidor fictício que absorva o excesso de oferta. Para isso, introduz-se uma coluna adicional com custos de transporte adequados. No exemplo anterior, considere-se agora que F1 produz 5 unidades em vez de 2: C 1 C 2 C 3 C * F1 5 7 3 4 F2 3 3 1 3 F3 5 3 4 6 4 1 5 (3) 2.4.2 Caso 2 - Procura excessiva É necessário considerar uma origem (fábrica) fictícia que produza a quantidade em falta. Para tal, introduz-se no quadro uma linha adicional com custos de transporte adequados, e função da situação particular em estudo. Ainda no exemplo anterior, considere-se agora que C2 consome 3 unidades em vez de 1: 14 Maria Antónia Carravilla - FEUP Modelos de Optimização C 1 C 2 C 3 F1 2 7 3 4 F2 3 3 1 3 F3 5 3 4 6 F* (2) 4 3 5 2.4.3 Problemas de Maximização Existem problemas de planeamento com a estrutura de problemas de transporte, em que, em vez de se procurar minimizar custos, se procura maximizar uma dada medida de eficiência (como, por exemplo, o lucro). Nesse caso, para utilizar os procedimentos standard de resolução, deve-se: • fazer Cij=lucro unitário associado à utilização emparelhada de Fi e de Cj • usar um critério de entrada na base inverso (isto é, passar a utilizar estradas que induzam um aumento no valor da função objectivo). Maria Antónia Carravilla - FEUP 15 Modelos de Optimização 3. PROBLEMAS DE AFECTAÇÃO Considere-se, a título de exemplo, o seguinte problema de optimização, representativo da classe designada por Problemas de Afectação (“assignment problems”): Uma companhia tem m tarefas para serem realizadas, e m empregados que as podem executar (possivelmente gastando tempos diferentes, em função da sua diferente especialização). Que empregado deverá ser afectado a cada tarefa, de modo a minimizar o tempo global para completar todas as m tarefas (e considerando que cada empregado só pode ser afectado a uma tarefa)? Numa matriz dos custos de afectação, representar-se-ão os custo das diferentes afectações (emparelhamentos) dos operários às tarefas. Em termos gerais, poderá considerar-se a afectação de quaisquer recursos a diferentes actividades. Os custos de afectação podem ser: • positivos, correspondendo a custos efectivos de operação, tempo gasto, etc., e nesse caso trata-se de um problema de minimização; • negativos, correspondendo a lucros, produtividade, ou quaisquer outras medidas de eficiência, tratando-se nesse caso de um problema de maximização. Continuando a apresentar o exemplo inicial, consideremos que a seguinte matriz dos custos de afectação, representa correctamente os tempos (em semanas), gastos por cada operário a realizar cada tarefa: Tarefas I II III IV A 2 10 9 7 Operários B 15 4 14 8 C 13 14 16 11 D 4 15 13 9 16 Maria Antónia Carravilla - FEUP Modelos de Optimização Este problema pode ser formulado como um problema de programação linear: Maria Antónia Carravilla - FEUP 17 Modelos de Optimização Seja : xij =   0, se o recurso i não for afectado à actividade j 1, se o recurso i for afectado à actividade j cij = custo associado à afectação de i a j sendo neste caso i = A, B, C, D e j = I, II, III, IV. O que se pretende é: minimizar Zc ij ij ji =∑∑ x 1 sujeito a : x x x ij j ij i ij = = =∨        ∑ ∑ 1 1 10 Este problema é obviamente um caso particular de Problema de Transportes, se se considerarem as restrições mais fracas 0 ≤ ≤ xij , em vez de impor que ou 0. Permitir que tal aconteça não altera, neste caso, a solução óptima (ou seja, é possível “relaxar” a restrição de integridade das variáveis sem que isso “piore” o resultado obtido). xij =1 EXEMPLO: minZx x x x x x x AI AII AIII AIV BI BII DIV =+ + + + + + 210 9 7 154 9L sujeito a : xx x x xx x x xxxx xxxx x AI AII AIII AIV B BII BIII BIV AI BI CI DI AIVBIVCIVDIV ij ij ++ + = ++ + = +++= +++= ∀=∨            1 1 1 1 01 1 M M 18 Maria Antónia Carravilla - FEUP Modelos de Optimização 3.1 Algoritmo Húngaro Trata-se de um algoritmo muito eficiente em termos computacionais, que tira partido das características estruturais particulares do problema de afectação. Propriedades da matriz dos custos de afectação: A. Pode-se somar ou subtrair uma constante a cada linha ou coluna, sem alterar a conjunto das afectações óptimas; B. Se, por transformações sucessivas, obtivermos pelo menos um "0" em cada linha ou coluna, a afectação que corresponde a esses "0", resulta no custo global mínimo. Definição: Um conjunto de elementos da matriz das eficiências diz-se independente se não existirem 2 elementos na mesma linha ou coluna. Algoritmo (processo iterativo): 1. Com o mínimo de “traços”, tentar cobrir todos os zeros da matriz; 2. O número de traços feitos, corresponde ao número de zeros independentes. Se o número de traços feitos for igual a m, está encontrada nesses zeros a afectação óptima (nesses zeros); 3. Dos elementos não “traçados”, escolhe-se o menor; 4. Subtrai-se esse elemento a todos os “não traçados”; 5. Soma-se esse elemento aos que estão “traçados duas vezes”; Voltar a 1. Note-se que os passos 4. e 5., são uma aplicação directa da propriedade A. e equivalem a : 1. Subtrair o elemento escolhido a todas as linhas; 2. Somá-lo às linhas e colunas “traçadas”. Maria Antónia Carravilla - FEUP 19 Modelos de Optimização 3.1.1 Aplicação do Algoritmo Húngaro na resolução de um problema de afectação: I II III IV A B C D 210 9 7 15 4 14 8 13 14 16 11 41513 9 PASSO 0: "Baixar" o mais possível os valores da matriz eficiência Subtrair o menor elemento de cada linha a todos os elementos dessa linha: I II III IV () () () () − − − − 20875 4110104 11 2 3 5 0 401195 Subtrair o menor elemento de cada coluna, a todos os elementos dessa coluna: () − 5 08 2 11 0 5 4 23 0 011 4 5 A B C D 5 0 PASSO 1: "Traçar" todos os zeros com o menor número possível de traços: 0 8 (2) 5 11 0 5 4 2 3 0 0 0 11 4 5 PASSO 2: Quantos “traços” (zeros independentes)? 3 < m = 4 20 Maria Antónia Carravilla - FEUP Modelos de Optimização PASSO 3: Qual o menor elemento dos não traçados? a = 2 PASSO 4: Subtrair a a todos os não traçados *; PASSO 5: Somar a aos traçados 2 vezes º: 0 8 *0 *3 11 0 *3 *2 º4 º5 0 0 0 11 *2 *3 PASSO 1: "Traçar" os zeros com o menor número possível de traços: 0 8 0 3 11 0 3 2 4 5 0 0 0 11 2 3 PASSO 2: Quantos "traços" (zeros independentes)? 4 = m (existem 4 zeros independentes) Logo: escolhendo quatro zeros independentes, isto é, que não pertençam a linhas ou colunas comuns, fica determinada a afectação óptima, que terá alternativas no caso de existirem outros conjuntos de zeros independentes. Maria Antónia Carravilla - FEUP 21 Modelos de Optimização Neste caso: I II III IV A 0 8 (0) 3 B 11 (0) 3 2 C 4 5 0 (0) D (0) 11 2 5 Ao empregado A é atribuída a tarefa III, ao empregado B é atribuída a tarefa II, ao empregado C é atribuída a tarefa IV, e ao empregado D é atribuída a tarefa V; sendo a "custo" mínimo obtido (ou seja, o tempo gasto globalmente na realização das tarefas).de 9 + 4 + 11 + 4 = 28. 3.2 “The Bottleneck assignment problem” Pretende-se, nesta variante do problema de afectação, que a tarefa mais demorada demore o menos tempo possível. Este problema corresponde, por exemplo, à situação em que se pretende realizar um projecto constituído por um conjunto de tarefas, para cuja execução se dispõe de uma equipa permanentemente disponível. Considere-se, para os dados do problema anterior, uma afectação qualquer (), assinalada sobre a matriz dos custos de afectação: I II III IV A 2 9 2 (7) B 6 (8) 7 6 C 4 6 (5) 3 D (4) 2 7 3 O tempo de execução mais demorado é 8. Vejamos se é possível fazer uma afectação só com valores inferiores a 8 (vamos assinalar esses valores com φ ): 22 Maria Antónia Carravilla - FEUP Modelos de Optimização I II III IV A φ 9 φ (φ)7 B (φ)6 8 φ φ C φ φ (φ)5 φ D φ (φ)2 φ φ É óbvio que se podem definir imensas afectações com os pontos assinalados com φ (uma é por exemplo a indicada, cuja tarefa mais demorada tem uma duração de 7). E com valores inferiores a 7, será possível fazer uma afectação? Vamos novamente assinalar esses valores com φ: I II III IV A φ 9 (φ)2 7 B (φ)6 8 7 φ C φ φ φ (φ)3 D φ (φ)2 7 φ A afectação assinalada é uma das possíveis, sendo a duração da actividade mais demorada igual a 6. Com valores inferiores a 6, não é possível definir qualquer afectação, pelo que a solução óptima segundo o critério definido, será a dada pelo quadro acima indicado, ou por qualquer das alternativas que dele se podem extrair. Este critério usa-se quando se pretende minimizar a ineficiência individual, e não o conjunto da afectação. Maria Antónia Carravilla - FEUP 23 Modelos de Optimização 1 2 4 3 7 6 5 8 9 (+) (+1) (-6) (-3) (+4) 6 16 6 2 4 5 6 6 2 5 1 5 11 2 8 9 8 6 4 (-6) 4.4 Determinação de CIRCUITOS EULERIANOS 4.4.1 O problema das pontes de Königsberg O rio Pregel banha a cidade de Königsberg, na Prússia Oriental, e rodeia a ilha de Kneiphof. A ligar os vários pontos das margens, havia 7 pontes dispostas como na figura: No seu passeio dominical, os habitantes da cidade procuravam voltar ao ponto de partida, passando uma só vez por todas as pontes. Leonard Euler estudou o problema e demonstrou a sua impossibilidade (1736). Definição de Circuito Euleriano: Um Circuito Euleriano, é um caminho finito em que o nó inicial coincide com o nó final e que passa uma única vez por todos os arcos da rede. 30 Maria Antónia Carravilla - FEUP Modelos de Optimização Teorema de Euler Um grafo admite um circuito euleriano se e só se for conexo e o número de vértices de grau impar for zero. (o grau de um vértice, corresponde ao número de arcos incidente no vértice) 4.4.2 O problema do carteiro chinês (chinese postman problem CPP) Considerem-se redes de distribuição linear, como por exemplo: • a recolha de lixo numa cidade; • a distribuição domiciliária do correio; • a inspecção periódica de redes de energia, de telefones, etc. O problema consiste em definir circuitos que se aproximem do Circuito Euleriano ideal (repetindo arcos em número mínimo ou de modo a tornar mínimo o aumento de percurso). 4.5 Determinação de CIRCUITOS HAMILTONIANOS 4.5.1 Definição de Circuitos Hamiltonianos Um circuito diz-se Hamiltoniano, se passar uma e uma só vez por todos os vértices de uma rede. A designação provém de um passatempo imaginado pelo islandês Hamilton (1859), no qual se procurava encontrar um caminho que percorresse 20 cidades de todo o mundo, representadas pelos vértices de um dodecaedro de madeira, voltando ao ponto inicial. (grafo plano na figura) Maria Antónia Carravilla - FEUP 31 Modelos de Optimização 4.5.2 O problema do Caixeiro Viajante (travelling salesman problem TSP) Um caixeiro viajante sai de uma cidade, visita n outras cidades e volta àquela de onde partiu, sem repetir nenhuma das cidades visitadas. De todos os circuitos possíveis de estabelecer, qual é o mais curto? Trata-se da pesquisa do circuito hamiltoniano mais curto num grafo de (n+1) vértices -> número de soluções possíveis = n! Algoritmos conducentes à solução óptima Pouco eficientes; Baseados num método de branch and bound como o de Little, 1963 . Algoritmos que levam a soluções quase óptimas Muito eficientes; Baseiam-se em regras heurísticas como a de Cicero-Ruggiero, 1972 32 Maria Antónia Carravilla - FEUP Modelos de Optimização 5. PROGRAMAÇÃO DINÂMICA A utilização da programação dinâmica em sequências de decisões inter-relacionadas, permite determinar a combinação daquelas que maximiza a eficiência global. Vamos agora descrever o problema da diligência: Exemplo 1: A diligência, para chegar ao seu destino, tinha que atravessar territórios de perigosos índios. A viagem (entre as cidades 1 e 10 ), a ser feita em 4 etapas, podia ser feita por diferentes percursos (diferentes cidades de passagem). A segurança de cada estrada intermédia era razoavelmente bem medida pelo custo da apólice de seguro respectiva. 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 tempos: estádios (stages) estados possíveis (states) O custo da apólice de seguro para ir de i para j é cij: 2 3 4 5 6 7 8 9 10 1 2 4 3 2 7 4 6 5 1 4 8 3 3 3 2 4 6 6 3 9 4 4 4 1 5 7 3 3 Que percurso fazer, por forma a minimizar o custo total do seguro? Variáveis de decisão: xndestino imediato decidido no estádio (tempo) n (n=1,2,3,4) Maria Antónia Carravilla - FEUP 33 Modelos de Optimização Vamos supor que a diligência, no tempo n está no estado s e selecciona como destino imediato xn. Seja fn(s,xn) o custo total da melhor política para os estádios restantes. Seja x*n o valor que minimiza fn(s,xn) e f*n(s) o correspondente valor mínimo de fn(s,xn), [f*n(s) = fn(s,x*n)]. O objectivo é encontrar f*1(1) e a correspondente política. A programação dinâmica consegue-o calculando sucessivamente f*4(s), f*3(s), f*2(s) e f*1(s). Resolução do problema n=4 (último estádio) s f*4(s) x*4 8 3 10 9 4 10 n=3 f 3(s,x3) = csx3+f*4(x3) s\x3 8 9 f*3(s) x*3 5 4 8 4 8 6 9 7 7 9 7 6 7 6 8 n=2 f 2(s,x2) = csx2+f*3(x2) s\x2 5 6 7 f*2(s) x*2 2 11 1 12 11 5 ou 6 3 7 9 10 7 5 4 8 8 11 8 5 ou 6 n=1 (primeiro estádio) f 1(s,x1) = csx1+f*2(x1) s\x1 2 3 4 f*1(s) x*1 1 13 11 11 11 3 ou 4 Solução óptima: 1ª decisão (n=1): ir para as cidades 3 ou 4 (estados 3 e 4) 34 Maria Antónia Carravilla - FEUP Modelos de Optimização Alternativa 1 : x*1=3 para s=3 -> x*2=5 [x*2(3)=5] para s=5 -> x*3=8 para s=8 -> x*4=10 Um percurso óptimo será então: 1 -> 3 -> 5 -> 8 -> 10 Alternativa 2 : 1 -> 4 -> 5 -> 8 -> 10 Alternativa 3 : 1 -> 4 -> 6 -> 9 -> 10 Características dos problemas de programação dinâmica: 1. 1] O problema pode ser dividido em ESTÁDIOS (stages), sendo tomada uma DECISÃO em cada estádio; 2. 2] A cada estádio estão associados determinados ESTADOS (states); 3. 3] O efeito da decisão tomada em cada estádio é transformar o estado actual num estado associado com o estádio seguinte, possivelmente de acordo com uma distribuição de probabilidades; 4. 4] Dado o estado actual, a política óptima para os restantes estádios é independente da política adoptada nos estádios prévios; (PRINCÍPIO DE OPTIMALIDADE DE BELLMAN); 5. 5] O processo de resolução começa pela determinação da decisão óptima para cada estado do ÚLTIMO ESTÁDIO; 6. É possível definir uma RELAÇÃO RECURSIVA que identifica a política óptima para cada estado no estádio n, dada a política óptima para cada estado no estádio (n+1). Exemplo: Maria Antónia Carravilla - FEUP 35 Modelos de Optimização f*n(s)= min xn{csxn+f*n+1(xn)} 7. Usando esta RELAÇÃO DE RECURSIVIDADE, a resolução do problema processa-se para trás (backward) estádio a estádio - em cada momento determina-se a decisão óptima para cada estado daquele estádio - até se encontrar a decisão óptima para o estádio inicial. Exemplo 2: (distribuir 5 equipas médicas por 5 países) max ∑ i=1 3 pi(xi) sujeito a: ∑ i=1 3 xi=5 xi_0 e inteiros xi - número de equipas afectadas ao país i País nº equipas médicas 1 2 3 0 0 0 0 1 45 20 50 2 75 45 70 3 90 75 80 4 105 110 100 5 120 150 130 pi(xi): 1000 de anos de vida/homem adicionais estados do sistema - nº de equipas disponíveis em cada estádio solução óptima: x1=3 x2=3 x3=3 Exemplo 3 36 Maria Antónia Carravilla - FEUP Modelos de Optimização max ∑ i=1 3 Ui(xi,Di) Xi Xi+1 Di Ui A] Transformações de estado x2=x2(x1,D1) x1\D1 1 2 3 4 1 3 2 1 4 2 4 3 3 4 3 3 1 2 4 4 2 4 2 1 x3=x3(x2,D2) x2\D2 1 2 3 4 1 - 2 5 1 2 3 4 3 - 3 4 5 4 - 4 3 4 2 3 B] Utilidade U1=U1(x1,D1) x1\D1 1 2 3 4 1 3 4 1 4 2 2 4 3 3 3 3 4 5 4 4 4 2 3 2 U2=U2(x2,D2) x2\D2 1 2 3 4 1 - 1 5 4 2 5 4 2 - 3 2 3 3 - 4 3 5 4 2 U3=U3(x3,D3) x2\D2 1 2 3 4 Maria Antónia Carravilla - FEUP 37 Modelos de Optimização 38 Maria Antónia Carravilla - FEUP 1 2 1 3 - 2 4 3 2 - 3 3 5 4 3 4 - 4 3 5 5 4 2 4 3