D1 · Decision Mathematics 1

Matemática para Decisão 1 (D1, papel WDM01/01, 1 hora 30 minutos, 75 pontos, primeira avaliação Junho 2019) é a opção discreta do IAL: P1–P2 são assumidas, e cada método é um básicos: os pontos são pela execução precisa de procedimentos e enunciação de resultados na forma exigida. Esta referência cobre algoritmos de ordenação e empacotamento, árvores geradoras mínimas, caminhos mais curtos, problema do correio chinês e do caixeiro viajante, análise de caminho crítico e programação linear. caminhos mais curtos, problema do carteiro chinês e problema do viajante de comércio, análise de caminho crítico e programação linear.

Regras da casa para respostas de algoritmos:

O bubble sort compara itens adjacentes, trocando pares fora de ordem, uma passagem de cada vez; uma passagem sem trocas termina. O quick sort seleciona o item DO MEIO da lista como pivô, particiona os itens restantes em "menores que o pivô", "iguais ao pivô" e "maiores que o pivô" (mantendo todas as cópias); ordena recursivamente os grupos menores e maiores — cite sempre o pivô e o lista após cada partição. A especificação fixa a escolha do item do meio ao método definido no glossário, então listas de exercícios aqui mantêm um número ímpar de itens e o item do meio é o na posição $\tfrac{n+1}2$. Empacotamento em caixas: primeira-caixa coloca cada item na primeira caixa com espaço; primeira-caixa decrescente ordena itens do maior para o menor e aplica primeira-caixa; empacotamento de caixa cheia busca combinações que preencham uma caixa exatamente.

Exemplo resolvido — quick sort (original). Ordene 9, 2, 7, 5, 3, 4, 6. O item central (posição 4 de 7) é 5: menor = 2, 3, 4; maior = 9, 7, 6, resultando em 2, 3, 4, 5, 9, 7, 6. Sublista 2, 3, 4 (pivot 3): 2, 3, 4 — ordenada. Sublista 9, 7, 6 (pivot 7): 6, 7, 9 — ordenado. Lista final: 2, 3, 4, 5, 6, 7, 9.

Exemplo resolvido — empacotamento em recipientes (original). Recipientes de capacidade 10; itens 7, 5, 4, 3, 6, 2 (total 27, portanto pelo menos 3 recipientes). First-fit: 7→b1, 5→b2 (7+5 > 10), 4→b2 (9), 3→b1 (10), 6→b3, 2→b3 (8): caixas (7,3), (5,4), (6,2). First-fit decreasing: 7, 6, 5, 4, 3, 2: 7→b1, 6→b2, 5→b3 (6+5 > 10), 4→b2 (10), 3→b1 (10), 2→b3 (7): recipientes (7,3), (6,4), (5,2) — também 3 recipientes.

Uma árvore geradora mínima (AGM) conecta todos os vértices com menor peso total. Algoritmo de Kruskal: ordenar arestas por peso, adicionar a menor que não forme ciclo (rejeitar e prosseguir se formar). Algoritmo de Prim: expandir uma árvore a partir de qualquer vértice inicial, adicionando repetidamente a aresta mais barata da árvore para um novo vértice. A forma matricial de Prim: riscar a linha inicial, destacar a entrada restante mais barata na coluna do vértice escolhido, e continuar. Kruskal é guiado por arestas (bom em redes desenhadas); Prim é guiado por vértices (bom em matrizes). Ambos dão o mesmo total; as arestas podem diferir apenas quando há empate de pesos. difere apenas quando os pesos empatam.

Exemplo resolvido (original). Arestas AB 4, AC 2, BC 3, BD 5, CD 1: Kruskal pega CD 1, AC 2, BC 3 (B conecta — sem ciclo), rejeita AB 4 e BD 5 (ciclos): MST total 6. Prim de A: AC 2, CD 1 (aresta mais barba de {A,C} a um novo vértice), CB 3: mesma árvore, e o total 6 ✓. Liste sempre as arestas na ordem escolhida e forneça o total.

Para pesos de aresta não negativos, o algoritmo de Dijkstra rotula vértices com a menor distância total encontrada até agora: rótulo do vértice inicial 0; selecione repetidamente o vértice não rotulado de menor rótulo temporário, torne-o permanente e atualize seus vizinhos (novo = permanente + peso, apenas se for menor). Registre a ordem de permanência e os rótulos finais; o caminho é recuperado retrocedendo pelos vértices cujo rótulo seja igual ao rótulo final menos o peso da conexão.

Exemplo resolvido (original). Arestas AB 4, AC 2, BC 1, BD 5, CD 8. Rótulos: A = 0 permanente; C = 2 permanente; B = min(4, 2+1) = 3 permanente; D = min(3+5, 2+8) = 8 permanente. O rota mais curta de A a D tem comprimento 8: A–C–B–D (voltar atrás: 8 = 3 + 5 em B, 3 = 2 + 1 em C).

O problema de inspeção de rotas (carteiro chinês) percorre toda ARESTA pelo menos uma vez e retorna ao ponto de partida. Comprimento total = soma de todas as arestas + o caminho mais curto para duplicar arestas de modo que todos os vértices fiquem de grau par. Encontre os vértices ímpares (no máximo quatro), liste seus pareamentos, escolha o pareamento de menor peso total e duplique essas arestas. Indique o pareamento antes do total.

Exemplo resolvido (original). Arestas AB 4, AC 2, BC 3, BD 5, CD 1 (total 15). Graus: A 2, B 3, C 3, D 2 — os nós ímpares são B e C, portanto duplique BC (peso 3): o caminho fechado mais curto que percorre cada aresta pelo menos uma vez tem comprimento 15 + 3 = 18.

O problema clássico do caixeiro viajante visita cada VÉRTICE exatamente uma vez e retorna, num grafo completo com a desigualdade triangular. Limites: a AMT da rede dobrada é um caminho limite SUPERIOR (percorra cada aresta da AMT duas vezes); atalhos fornecem um melhor limite superior. Limites inferiores provêm de argumentos baseados na AMT (p. ex., a AMT ou removendo um vértice e adicionando suas duas arestas mais baratas). O **algoritmo do vizinho mais próximo constrói uma rota: a partir do vértice inicial, vá repetidamente ao vértice não visitado mais próximo, depois retorne. Converta para uma rede completa de menores distâncias primeiro quando o grafo não for completo (via Dijkstra ou inspeção).

Exemplo resolvido (original). Rede completa: AB 4, AC 2, AD 7, BC 3, BD 5, CD 6 (a desigualdade triangular vale em toda parte). Vizinhança mais próxima partindo de A: A–C (2), C–B (3), B–D (5), D–A (7): comprimento da rota 17 — um limite superior. A AGM é AC + BC + BD = 10, então dobrá-la fornece o limite superior grosseiro 20, melhorado para 17 por atalhos; um limite inferior obtido removendo A (AGM de B, C, D é 3 + 5 = 8, mais as duas arestas mais baratas de A, AC + AB = 2 + 4 = 6) resulta em 14. A rota ótima situa-se entre 14 e 17.

Modelar um projeto como uma rede atividade-aresta baseada em uma tabela de precedência; arestas falsas (arestas de peso zero) resolvem dependências que extremidades compartilhadas não podem expressar. O caminho crítico é a cadeia mais longa através da rede: a duração do projeto. Calcular tempos mais cedo dos eventos (passagem frontal: o máximo das chegadas) e tempos mais tarde dos eventos (passagem traseira: o mínimo das saídas). O holgura total de uma atividade = término mais tardio − início mais cedo − duração; as atividades críticas têm holgura zero. Os gráficos de Gantt (em cascata) representam cada atividade por barras a partir do seu início mais cedo, com a holgura como espaço em branco à direita; o agendamento aloja trabalhadores dia após dia. início mais cedo com seu holgura como espaço à direita; agendamento aloca trabalhadores dia a dia.

Exemplo resolvido (original). Atividades A (3 dias), B (4), C (4 após A), D (1 após B), E (5 após C e D). Caminho A–C–E = 12 dias; caminho B–D–E = 10 dias: o caminho crítico é A–C–E e o projeto dura 12 dias; holgura total de D = 12 − (4 + 1 + 5) = 2 dias.

Formular: definir as variáveis de decisão, escrever o objetivo (maximizar/minimizar) e cada restrição como desigualdade, incluindo $x, y \ge 0$. Resolver problemas de duas variáveis graficamente: gradiente do objetivo) ou o método dos vértices (avaliar o objetivo em cada vértice da região viável). Soluções inteiras: testar pontos inteiros próximos ao vértice ótimo dentro da região. dentro da região.

Exemplo resolvido — programação linear (original). Maximizar $P = 3x + 2y$ sujeito a $x + y \le 10$, $2x + y \le 14$, $x, y \ge 0$. Os vértices da região viável são $(0,0)$, $(7,0)$, $(4,6)$, $(0,10)$; avaliando $P$: 0, 21, 24, 20 — o máximo é $P = 24$ em $(4,6)$, onde ambas as restrições são ativas.

• Encontrar AGPs por Kruskal e por Prim (formas de nó e matriz); desenhar uma rede a partir de uma matriz e vice-versa.
• Executar Dijkstra com rótulos em ordem de permanência; recuperar a rota, não apenas o comprimento.
• Resolver inspeção de rotas: nós ímpares, todos os pareamentos com pesos, menor duplicação, comprimento total do passeio.
• Limitar o TSP clássico: AGP dobrada e atalhos para limites superiores, exclusão de AGP para limites inferiores; executar vizinho mais próximo na rede completa de distâncias mais curtas.
• Limitar o TSP clássico: MST dobrado e atalhos para limites superiores, exclusão de MST para limites inferiores; aplicar vizinho mais próximo na rede completa de menor distância.
• Construa redes de atividades com tarefas fictícias; passe para frente e para trás para tempos dos eventos; folgas totais; identifique o caminho crítico; desenhe o gráfico de Gantt e a programação.
• Formulada programas lineares completamente; resolva graficamente por régua ou método dos vértices; encontre melhores soluções inteiras.