Avaliação 2 -2023-1

Página 1 de 3 Questão 1: Seja o PLI (3,5 pts) maximize Z = 3x + 2y – 4w sa x + 4w ≤ 5 (variável de folga f1) 2x + 4y – 2w ≤ 5 (variável de folga f2) x + y – 2w ≤ 2 (variável de folga f3) x, y, w ∈ Z+ Seja a árvore parcial da resolução deste PLI via método branch and bound. PL(0) x y w f1 f2 f3 b Z(0) 2/3 1/3 8/3 7 w -1/6 1 1/6 -1/6 1/2 f2 7/3 -1/3 1 -5/3 0 x 1 2/3 1/3 2/3 3 Use a regra da variável mais fracionária para ramificação e resolva o PLI. w  0 (var f4) PL(1) x y w f1 f2 f3 f4 b Z(1) 2/3 1/3 8/3 7 w - 1/6 1 1/6 -1/6 1/2 f2 7/3 - 1/3 1 -5/3 0 x 1 2/3 1/3 2/3 3 f4 1 1 0 PL(1) x y w f1 f2 f3 f4 b Z(1) 2/3 1/3 8/3 7 w - 1/6 1 1/6 -1/6 1/2 f2 7/3 - 1/3 1 -5/3 0 x 1 2/3 1/3 2/3 3 f4 0 1/6 0 - 1/6 0 1/6 1 - 1/2 PL(1) x y w f1 f2 f3 f4 b Z(1) 1 3 2 6 w 0 1 0 1 0 f2 2 1 -2 -2 1 x 1 1 1 2 2 f4 -1 1 -1 -6 3 w  1 (var e) PL(2) x y w f1 f2 f3 e b Z(2) 2/3 1/3 8/3 7 w - 1/6 1 1/6 -1/6 1/2 f2 7/3 - 1/3 1 -5/3 0 x 1 2/3 1/3 2/3 3 e -1 1 -1 PL(2) x y w f1 f2 f3 e b Z(2) 2/3 1/3 8/3 7 w - 1/6 1 1/6 -1/6 1/2 f2 7/3 - 1/3 1 -5/3 0 x 1 2/3 1/3 2/3 3 e 0 - 1/6 0 1/6 0 - 1/6 1 - 1/2 -4 -15,666 PL(2) x y w f1 f2 f3 e b Z(2) 0 -0 0 1 0 2 4 5 w 0 0 1 0 0 0 -1 1 f2 0 -0 0 2 1 -4 14 -7 x 1 -0 0 1 0 -0 4 1 e 0 1 0 -1 0 1 -6 3 PL(2) x y w f1 f2 f3 e b Z(2) 2 1/2 11 3/2 w 1 0 0 -1 1 Página 2 de 3 f3 - 1/2 - 1/4 1 -7/2 7/4 x 1 1 0 4 1 y 1 - 1/2 1/4 -5/2 5/4 Questão 2: (V) Verdadeiro (F) Falso (0,2 pts cada) (3,0 pts) a. ( ) Durante a execução do método branch and bound é modificado o espaço de solução contínuo de uma maneira que produzirá um ótimo contínuo que satisfaça as condições inteiras nas variáveis. b. ( ) O corte(bound) pode eventualmente produzir a solução inteira ótima de um problema no qual todas as variáveis são inteiras. c. ( ) No procedimento branch-and-bound, a etapa delimitadora(bounding) define um limite inferior no valor objetivo no caso de maximização, desde que uma solução inteira viável seja encontrada. d. ( ) No procedimento branch-and-bound, as regras disponíveis para selecionar a variável de ramificação em um nó garantem encontrar um bom limite rapidamente. e. ( ) No procedimento branch-and-bound, uma variável de ramificação em um nó não pode ser ramificada novamente em um nó subsequente gerado a partir do nó atual. f. ( ) Um modelo de transporte inicialmente desequilibrado pode exigir a adição de uma fonte fictícia e de um destino fictício para efetuar o balanceamento. g. ( ) O modelo de transporte é restrito a lidar apenas com uma única unidade de uma mercadoria. h. ( ) Os multiplicadores (u’s e v’s) na técnica de transporte são essencialmente as variáveis duais do PL representando o problema de transporte. i. ( ) Se um valor constante for adicionado a cada elemento de custo Cij no quadro de transporte, os valores ótimos das variáveis xij mudarão. j. ( ) O problema de designação pode ser resolvido pela técnica de transporte. k. ( ) Quando um problema de atribuição de maximização é convertido em problema de minimização, a matriz resultante poderia ser chamada de “matriz de arrependimento”. l. ( ) Para encontrar a solução viável inicial de um problema de transporte, o método que começa a alocação do menor custo é chamada de método de canto noroeste. m. ( ) O método de menor custo considera a diferença entre dois custos mínimos para cada linha e coluna ao encontrar a solução viável básica inicial no transporte. n. ( ) Quando a demanda total é igual à oferta, diz-se que o problema de transporte é de minimização. o. ( ) Para encontrar uma solução ótima no problema de transporte, o método Húngaro é usado. Questão 3: Resolva o seguinte problema de designação (2,5 pts) Minimize Z = 5x11+6x12+6x13+7x21+5x22+6x23+5x31+7x32+6x33+4x41+3x42+4x43 sa x11+x12+x13  1 x21+x22+x23  1 x31+x32+x33  1 x41+x42+x43  1 x11+x21+x31+x41  1 x12+x22+x32+x42  1 x13+x23+x33+x43  1 5 6 6 7 5 6 5 7 6 4 3 4 5 6 6 0 0 2 1 0 7 5 6 0 2 1 1 0 5 7 6 0 1 4 2 0 4 3 4 0 0 0 0 1 4 3 4 0 m 0 2 1 0 1 3 2 0 2 1 1 0 3 2 2 0 1 4 2 0 Página 3 de 3 1 4 2 0 0 0 0 1 0 0 0 0 0 2 1 1 1 3 2 0 1 0 0 0 3 2 2 0 0 3 1 0 1 4 2 0 0 0 0 2 0 0 0 0 0 2 1 1 0 2 1 0 1 0 0 0 2 1 1 0 m 0 3 1 0 1 4 2 0 m 0 0 0 2 Questão 4: Uma empresa precisa planejar sua produção para os quatro trimestres do próximo ano (um trimestre são três meses). Prevê as seguintes demandas: 50 unidades no primeiro trimestre, 100 unidades no segundo, 200 unidades no terceiro e 200 unidades no quarto. Durante cada trimestre, a capacidade de produção é limitada a 150 unidades e no início do primeiro trimestre há em estoque 50 unidades. A demanda de um trimestre não pode ser atendida no próximo. Cada unidade é vendida por R$ 4,00 enquanto que o custo de produção unitário é R$ 2,00. O produto pode ser estocado e ser utilizado para atender a demanda em trimestres subseqüentes. Custa R$ 0,25 por trimestre para armazenar uma unidade (este custo não existe no trimestre da produção). Determine o qto produzir em cada trimestre para atender a demanda a uma receita máxima. Resolva como um problema de transporte e utilize o método do canto sudeste para gerar a solução inicial, ou seja, inicie a determinar a solução inicial a partir da “célula” de baixo para cima e da direita para a esquerda. OBS: o objetivo é maximizar a receita (preço de venda menos os custos de produção e de estocagem). (1,0 pts) Trim 1 Trim 2 Trim 3 Trim 4 Capacidade Trim 1 Trim 2 Trim 3 Trim 4 Capacidade Estoque 0,00 0,25 0,50 0,75 100 Estoque 4,00 4,00 4,00 4,00 100 Trim 1 2,00 2,25 2,50 2,75 150 Trim 1 4,00 4,00 4,00 4,00 150 Trim 2 - 2,00 2,25 2,50 150 Trim 2 - 4,00 4,00 4,00 150 Trim 3 - - 2,00 2,25 150 Trim 3 - - 4,00 4,00 150 Trim 4 - - - 2,00 150 Trim 4 - - - 4,00 150 Demanda 50 100 200 200 150 Demanda 50 100 200 200 150 Trim 1 Trim 2 Trim 3 Trim 4 Trim F Capacidade Estoque 0 (50) 0,25 (50) 0,50 0,75 0,00 100 50 0 50 50 Trim 1 2,00 2,25 (50) 2,5 (100) 2,75 0,00 150 50 0 50 100 Trim 2 10000 2,00 2,25 (100 2,5 (50) 0,00 150 100 0 100 50 Trim 3 10000 10000 2,00 2,25 (150 0,00 150 0 150 Trim 4 10000 10000 10000 2 (0) 0 (150) 150 0 0 150,00 Demanda 50 100 50 0 200100 0 200 50 0 150 0 0,00 0,25 0,5 (0) 0,75 (0) 0 (+) 0,00 50 50 2 (0) 2,25 2,50 2,75 (0) (-0,75) 2,00 50 100-T +T 10000 2 (0) 2,25 2,50 0 (-0,50) 1,75 100+T 50-T 10000 10000 2 (0) 2,25 0 (-0,25) 1,50 150 10000 10000 10000 2,00 0,00 1,25 0+T 150-T 0,00 0,25 0,50 0,75 -1,25 0,00 0,25 0,50 0,75 (+) 0 (+) 0,00 50 50 2 (0) 2,25 2,50 2,75 (+) 0,00 2,00 50 50-T 50+T 10000 2 (0) 2,25 2,5 (+) 0 (+) 1,75 150 10000 10000 2 (-0,75) 2,25 0 (-0,25) 2,25 +T 150-T 10000 10000 10000 2,00 0,00 2,00 50+T 100-T 0 0,25 0,5 0,00 -2,00 0,00 0,25 0,5 (+) 0,75 (+) 0,00 0,00 50 50 Página 4 de 3 2 (0) 2,25 2,5 (+) 2,75 (+) 0,00 2,00 50-T 100+T 10000 2 (-0,75) 2,25 2,50 0 (-0,5) 2,50 +T 150-T 10000 10000 2,00 2,25 0 (-0,25) 2,25 50+T 100-T 10000 10000 10000 2,00 0,00 2,00 100+T 50-T 0 0,25 -0,25 0,00 -2,00 0,00 0,25 0,5 (0) 0,75 (0) 0 (+) 0,00 50 50 2 (+) 2,25 (+) 2,5 (+) 2,75 (+) 0,00 1,25 150 10000 2,00 2,25 2,50 0 (-0,5) 1,75 50 100-T +T 10000 10000 2,00 2,25 0(-0,25) 1,50 100+T 50-T 10000 10000 10000 2,00 0,00 1,25 150+T 0-T 0 0,25 0,5 0,75 -1,25 0,00 0,25 0,5 (+) 0,75 (0) 0,00 0,00 50 50 2 (+) 2,25 (+) 2,5 (+) 2,75 (+) 0,00 1,75 150 10000 2,00 2,25 2,5 (0) 0,00 1,75 50 100 0 10000 10000 2,00 2,25 0 (+) 1,50 100 50 10000 10000 10000 2,00 0 (+) 1,25 150 0 0,25 0,5 0,75 -1,75