Prova Pesquisa Operacional 2-2023 1

Observações: i) Utilize somente técncias e algoritmos vistos em sala de aula ii) Se empregar o algoritmo incorretamente, mesmo obtendo a solução, a resolução será totalmente anulada. Questão 1: Seja o pli e o quadro ótimo associado ao primeiro nó da árvore branch and bound (E1 e E2 variáveis de excesso das duas primeiras restrições, F variável de folga da 3ª restrição) min Z = 2X1 + X2 sa 4X1 + 3X2  6 3X1 + X2  3 X1 + X2  3 X1, X2 Z+ Base X1 X2 E1 E2 F b Z 1/5 2/5 -12/5 X2 1 -3/5 4/5 6/5 X1 1 1/5 -3/5 3/5 F 2/5 -1/5 1 6/5 i) Indique no gráfico todas as soluções viáveis do pli (não precisa calcular). .................................. (1,0 pontos) ii) Aplique mais duas etapas do algoritmo branch and bound a partir da variável X1 gerando 2 nós da árvore na resolução do pli. ............................................................................................................................... (3,0pontos) X1 <= 0 X1 + F2 = 0 Base X1 X2 E1 E2 F1 F2 b Z 1/5 2/5 -12/5 X2 1 - 3/5 4/5 6/5 X1 1 1/5 - 3/5 3/5 F1 2/5 - 1/5 1 6/5 F2 1 0 0 1 0 Base X1 X2 E1 E2 F1 F2 b Z 1/5 2/5 -12/5 X2 1 - 3/5 4/5 6/5 X1 1 1/5 - 3/5 3/5 F1 2/5 - 1/5 1 6/5 F2 - 1/5 3/5 1 - 3/5 Base X1 X2 E1 E2 F1 F2 b Z 1 1 -3 X2 1 -1 -3 3 X1 1 0 1 0 F1 1 1 2 0 E1 1 -3 -5 3 X1 >= 1 -X1 <= -1 -X1 + E3 = -1 Base X1 X2 E1 E2 F1 E3 b Z 1/5 2/5 -12/5 X2 1 - 3/5 4/5 6/5 X1 1 1/5 - 3/5 3/5 F1 2/5 - 1/5 1 6/5 E3 -1 0 0 1 -1 Base X1 X2 E1 E2 F1 E3 b Z 1/5 2/5 -12/5 X2 1 - 3/5 4/5 6/5 X1 1 1/5 - 3/5 3/5 F1 2/5 - 1/5 1 6/5 E3 1/5 -3/5 1 -2/5 Base X1 X2 E1 E2 F1 E3 b Z 1/3 2/3 -8/3 X2 1 - 1/3 4/3 2/3 X1 1 0 -1 1 F1 1/3 1 - 1/3 4/3 E2 - 1/3 1 -5/3 2/3 Questão 2: Verifique a validade/viabilidade da solução de um problema de transporte. Se a solução não for válida/viável gere uma que seja sem alterar os valores já transportados (em parênteses) a partir da solução inicial dada. Utilize os métodos u-v e stepping stone para determinar a solução ótima. .................. (3,0 pontos) Κ1 Κ2 Κ3 Κ4 Κ5 Oferta L1 3 (100) 2 3 4 1 100 L2 4 1 (60) 2 (40) 4 (25) 2 125 L3 1 0 5 3 (50) 2 (25) 75 Demanda 100 60 40 75 25 Κ1 Κ2 Κ3 Κ4 Κ5 Oferta L1 3 (100) 2 3 4 1 100 L2 4 (0) 1 (60) 2 (40) 4 (25) 2 125 L3 1 0 5 3 (50) 2 (25) 75 Demanda 100 60 40 75 25 3 (100) 2 (2) 3 (2) 4 (1) 1 (-1) U1=-1 100 4 (0) 1 (60) 2 (40) 4 (25) 2 (-1) U2=0 0-T 60 40 25+T 1 (-2) 0 (0) 5 (4) 3 (50) 2 (25) U3=-1 +T 50-T 25 V1=4 V2=1 V3=2 V4=4 V5=3 T=0 3 (100) 2 (0) 3 (0) 4 (-1) 1 (-3) U1=1 100-T +T 4 (2) 1 (60) 2 (40) 4 (25) 2 (-1) U2=0 60 40 25 1 (0) 0 (0) 5 (4) 3 (50) 2 (25) U3=-1 0+T 50 25-T V1=2 V2=1 V3=2 V4=4 V5=3 T=25 3 (75) 2 (0) 3 (0) 4 (-1) 1 (25) U1=1 75-T +T 25 4 (2) 1 (60) 2 (40) 4 (25) 2 (2) U2=0 60 40 25 1 (25) 0 (0) 5 (4) 3 (50) 2 (3) U3=-1 25+T 50-T V1=2 V2=1 V3=2 V4=4 V5=0 T=50 3 (25) 2 (1) 3 (1) 4 (50) 1 (25) U1=0 25 50 25 4 (1) 1 (60) 2 (40) 4 (25) 2 (1) U2=0 60 40 25 1 (75) 0 (1) 5 (5) 3 (1) 2 (3) U3=-2 75 V1=3 V2=1 V3=2 V4=4 V5=1 Questão 3: O Xoping aposta na segurança. Para isso dispõe de seguranças privados colocados em pontos estratégicos dentro do Xoping de modo a, ao serem vistos, inibirem o furto e controlarem a maior área possível. No setor térreo foram determinadas 6 localizações possíveis para os seguranças. No entanto, é claro para o responsável pela segurança, de que o Patolino, o Zezão, o Botas e o Galhardo são suficientes para vigiar o setor térreo. Dadas as características dos seguranças mencionados (peso, força, agilidade, etc.) e dos locais de vigilância, o responsável pela segurança construiu um índice (consta na tabela) que indica o proveito/benefício de um dado segurança estar “parado" num dado local (quanto mais vantajoso alocar um segurança a um determinado local, maior o índice): .......................................................... (3,0 pontos) Local No entanto, após uma inspeção aos locais, o responsável decidiu que o Patolino não poderia ficar no local A nem no local B, por serem adjacentes a lojas de bebidas. Determine quais locais devem ser ocupados e por quais seguranças. (PS.: problema de maximização!!!!!) A B C D E F Patolino 5 6 4 4 6 2 Zezão 4 1 5 3 5 2 Botas 3 4 2 3 1 3 Galhardo 5 2 1 4 6 4 maximização A B C D E F Patolino 5 6 4 4 6 2 Zezão 4 1 5 3 5 2 Botas 3 4 2 3 1 3 Galhardo 5 2 1 4 6 4 Máximo: 6 minimização A B C D E F min Patolino 1 0 2 2 0 4 0 Zezão 2 5 1 3 1 4 1 Botas 3 2 4 3 5 3 2 Galhardo 1 4 5 2 0 2 0 Ficticio1 0 0 0 0 0 0 0 Ficticio2 0 0 0 0 0 0 0 * * inf inf 2 2 0 4 1 4 0 2 0 3 1 0 2 1 3 1 * 1 4 5 2 0 2 0 0 0 0 0 0 0 0 0 0 0 0 mínimo: 1 inf inf 1 1 0 3 1 4 0 2 1 3 1 0 2 1 4 1 0 3 4 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0