Metodos de pesquisa operacional

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1302 palavras )
  • Download(s) : 0
  • Publicado : 23 de setembro de 2012
Ler documento completo
Amostra do texto
Exemplo 1
Uma grande fábrica de móveis dispõe em estoque de 250m de tábuas, 600m de pranchas e 500m de painéis de conglomerado. A fábrica normalmente oferece uma linha de móveis composta por um modelo de escrivaninha, uma mesa de reunião, um armário e uma prateleira. Cada tipo de móvel consome uma certa quantidade de matéria prima, conforme a tabela abaixo. A escrivaninha é vendida por R$100,a mesa por R$80, o armário por R$120 e a prateleira por R$20. Modele e resolva o problema pelo simplex, de forma a maximizar a receita com a venda dos móveis.
Quantidade de material em metros consumidos por unidade de produto
Disponibilidade do Recurso (m)
Escrivaninha Mesa Armário Prateleira
Tábua 1 1 1 4 250 Prancha 0 1 1 2 600
Painéis 3 2 4 0 500
Valor de
Revenda (R$) 100 80 12020
Considerando as seguintes variáveis de decisão:
xE = Nº de escrivaninhas a ser produzido; xM = Nº de mesas a ser produzido; xA = Nº de armários a ser produzido; xP = Nº de prateleiras a ser produzido.
Podemos então escrever o modelo de PL:

xE + xM + xA + 4xP ≤ 250 xM + xA + 4xP ≤ 600
Passando para a forma padrão, temos:

3xE + 2xM + 4xA + x3 = 500
xE + xM + xA + 4xP + x1 =250 xM + xA + 4xP + x2 = 600
A nossa solução básica viável inicial pode ser obtida, neste caso, de forma trivial: x1 = 250; x2 = 600; x3 = 500; xE = xM = xA = xP = 0.
Podemos agora montar o quadro simplex. Para isso, trataremos a equação da F.O. como se fosse apenas mais uma equação do nosso sistema linear:
– Z + 100xE + 80xM + 120xA + 20xP = 0
xE + xM + xA + 4xP + x1 = 250 xM + xA + 4xP +x2 = 600 3xE + 2xM + 4xA + x3 = 500
Essa linha será destacada no quadro, e sua importância será vista no decorrer do algoritmo. Além disso, usaremos a 1ª coluna para fazer a numeração das linhas, somente para facilitar as explicações a seguir. A 2ª coluna serve para relacionarmos as variáveis básicas (V.B.):
V.B. xE xM xA xP x1 x2 x3 b L0 – Z 100 80 120 20 0 0 0 0 L1 x1 1 1 1 4 1 0 0 250 L2x2 0 1 1 2 0 1 0 600 L3 x3 3 2 4 0 0 0 1 500
Para entrar na base, devemos escolher a variável que possui o maior coeficiente na linha L0. Esses coeficientes indicam a contribuição que cada variável dá à Função Objetivo. para cada unidade de aumento de seus respectivos valores. No quadro acima, vemos que cada unidade de aumento da variável xA resulta em um aumento de 120 unidade no valor da F.O.Essa é a variável que mais contribui localmente para o processo de maximização da F.O., e é portan- to a escolhida para entrar na base. Esse processo de escolha é representado no fluxograma da seguinte maneira:
cj* = max(cj) onde j* representa a coluna correspondente à variável que deve entrar na base.
Para que a variável xA entre na base, é preciso que uma variável básica saia da base (porque?). Para determinar isso, é só fazer com que o valor de xA cresça o máximo possível. Po- demos ver pelos valores do quadro acima que, se xA for maior que 125 (ou 4xA > 500), então teremos para a ultima restrição o seguinte:

e o valor de x3 seria negativo, o que seria inviável. Com isso, o maior valor que xA pode as- sumir sem violar nenhuma das restrições é xA = 125. Nesse caso, o valorde x3 seria igual a zero, e ele então sai da base. Todo esse processo de escolha é representado no fluxograma da seguinte maneira:
Escolher i* | min(bi / aij*), aij* > 0 onde i* representa a linha correspondente à variável que deve sair da base.
O significado desse “procedimento” é bem simples: divida todos os bi pelos valores de aij* que forem maiores que zero, e pegue o menor valor dessadivisão, que corresponderá à linha i*. No caso acima, teríamos:

Agora podemos representar a mudança de base usando setas no quadro:
V.B. xE xM xA xP x1 x2 x3 b L0 – Z 100 80 120 20 0 0 0 0 L1 x1 1 1 1 4 1 0 0 250 L2 x2 0 1 1 2 0 1 0 600
L3 x3 3 2 4 0 0 0 1 500
O elemento destacado representa o nosso pivot. Observe que os vetores-coluna das variáveis básicas na matriz A formam uma matriz...
tracking img