Sistemas de Apoio à Decisão 1 Modelos de decisão

Sistemas de Apoio à Decisão 1

Modelos de decisão


Modelos de decisão

Um modelo é uma representação simplificada da realidade.

• A realidade é demasiado complexa para poder ser representada na sua totalidade.

• Parte dessa complexidade é irrevelante para a resolução do problema especifico.

A maior característica de um SAD é a inclusão de modelos.


Modelos de decisão

Descreve

Explica

Prevê

Objectivo

Função

Estado

Forma

Porque é que o sistema existe?

Como é que funciona?

O que está a fazer?

Qual é o seu aspecto?


Modelos de decisão

Um modelo é um mecanismo para prever o resultado de saída de um sistema real, sob determinadas condições especificadas pelos dados de entrada do modelo, sem que se tenha que usar o próprio sistema real.

A estrutura do modelo descreve a forma do sistema e o comportamento do modelo explica o seu funcionamento.


Modelos de decisão

De acordo com o seu grau de abstracção, os modelos podem ser classificados em 3 grupos diferentes:

• Icónicos

• Analógicos

• Matemáticos ou quantitativos

Ab

stra

cção


Modelos de decisão• Icónicos - os menos abstractos - constituem uma réplica física

do sistema, normalmente a uma escala diferente da original.

Exemplos: 3D (um automóvel, uma maquete de um edifício) e 2D (fotografias).

• Analógicos - não se parecem com o sistema real, mas comportam-se da mesma forma. São mais abstractos e constituem representações simbólicas da realidade.

Exemplos: gráficos de barras, organogramas, mapas.

• Matemáticos ou quantitativos - a complexidade das relações existentes entre as diversas componentes de um sistema não pode muitas vezes ser representadas através de imagens, sendo necessárias formas mais abstractas de representação matemática. A maior parte dos SADs usam modelos matemáticos.


Vantagens do uso de modelos• Permitem a compressão do tempo - actividades que em tempo real

demorariam anos podem ser simuladas em alguns minutos.

• Os custos de uma análise do modelo são muito reduzidos em relação aos custos de uma experiência similar conduzida no sistema real.

• Os custos dos erros produzidos durante as experiências são mais reduzidos quando se usam modelos, evitando as mudanças irreversiveis.

• Permitem uma manipulação mais fácil e segura do sistema.

• Permitem o cálculo do risco, devido à incerteza, envolvido em certas acções.

• Permitem a análise de um número quase infinito de possíveis soluções.

• Favorecem a aprendizagem.


Modelos quantitativos

Componentes básicas:

• Variáveis de decisão,

• Parâmetros,

• Resultados ou variáveis de saída.

As variáveis de decisão descrevem as possíveis alternativas.

Os parâmetros representam factores que influenciam os resultados, mas que estão fora do controlo do decisor, pois são determinados por factores externos ao sistema.

Exemplo: manufactura - Custo total ou lucro, Quanto produzir?, capacidade da máquinas e preço das matérias primas.



Os componentes dos modelos quantitativos estão relacionados por relações matemáticas expressas por equações ou inequações.

Exemplos:

• Modelo financeiro Lucro = Ganhos – Custos

• Modelos de programação linear

• ...



Componentes básicas dos modelos de investigação operacional:

• Variáveis de decisão – cujos valores, que descrevem as possíveis alternativas, se pretende determinar.

• Função objectivo – que corresponde a uma função matemática das variáveis de decisão e que mede a performance de cada alternativa.

• Restrições – funções matemáticas que restringem os valores que cada variável de decisão pode tomar.

• Parâmetros – correspondem às contantes existentes nas expressões matemáticas das restrições ou da função objectivo e representam factores que influenciam os resultados, mas que podem estar fora do controlo do decisor, pois são determinados por factores externos ao sistema.



Ao utilizar um modelo matemático de investigação operacional na resolução de um problema, este resume-se a escolher um conjunto de valores para as variáveis de decisão que maximize (minimize) o valor da função objectivo, respeitando as restrições impostas.


Programação linear

A programação linear é uma técnica matemática que permite resolver problemas de alocação de recursos escassos entre actividades em competição por esses mesmos recursos.

O problema consiste em encontrar o valor das variáveis de decisão que garantem a maximização (ou minimização) do resultado, estando sujeitas a algumas restrições (expressões lineares) que dependem de determinados parâmetros.

As relações matemáticas entre estas variáveis são todas funções lineares. A palavra programação, neste contexto, significa planeamento.

Processo de resolução: Método simplex (George Dantzig, 1947).


Programação linearExemplo:Uma fábrica pretende produzir dois produtos, o produto 1 e o produto 2. Ambos os produtos passam por três fases de desenvolvimento durante o processo de manufactura, cada uma das quais se realiza num departamento diferente. No próximo mês, cada um dos departamentos tem um determinado números disponível de horas por máquina, para ser utilizado na concepção destes dois produtos. Por sua vez, cada um dos produtos requer, por unidade, um dado tempo de utilização de cada máquina.

Tempo disponível (h)

Tempo requerido por unidade (h)Produto 1

Produto 2

1 0

0 2 2

3

4 12 18

Departamentos1 2 3

Para manter o problema simples, vamos assumir que os custos de produção de cada produto são constantes, independentemente da quantidade produzida.

Supondo que o lucros, por unidade, de cada produto são de € 3 para o produto 1 e € 5 para o produto 2, queremos determinar qual o número de unidades de cada um dos produtos que a fábrica deve produzir, no próximo mês, de modo a obter o maior lucro possível.



Formulação matemática do problema:

Variáveis de decisão: x1 e x2 representam o número de unidades dos produtos 1 e 2 respectivamente, a serem produzidas.

Função objectivo: Maximizar Z = 3x1 + 5x2

Restrições: x1 <= 4

2x2<= 12

3x1 + 2x2 <= 18

x1, x2 >= 0



Representação gráfica do problema

x1

x2

2 4

6

8

2

4

6 8

x1 = 4

2x2 = 12

3x1 + 2x2 = 18




x1

x2

2 4

6

8

2

4

6 8

Z = 10 = 3x1 + 5x2

Z = 20 = 3x1 + 5x2

Z = 36 = 3x1 + 5x2

(2, 6)



Formulação standard

Max Z = c1x1+c2x2+...+cnxn

sujeito às restrições:

a11x1+a12x2+...+a1nxn b1

a21x1+a22x2+...+a2nxn b2

.

.

.

am1x1+am2x2+...+amnxn bm

e x1 0, x2 0,... xn 0

Restrições funcionais

Restrições de não negatividade



Outras formas

1. Minimização da função objectivo:

Min Z = c1x1+c2x2+...+cnxn

2. Restrições funcionais da forma

ai1x1+ai2x2+...+ainxn bi

3. Restrições funcionais de igualdade

ai1x1+ai2x2+...+ainxn = bi

4. Inexistência de restrições de não-negatividade para algumas variáveis de decisão.



Qualquer conjunto de valores assumidos pelas variáveis de decisão (x1, x2,...,xn) é considerado uma solução.

Tipos de soluções

• Solução admissível – que satisfaz todas as restrições.

Um problema pode não ter nenhuma solução admissível.

• Solução óptima – é a solução admissível que corresponde ao valor mais favorável da função objectivo.

É possível existir mais do que uma solução óptima para o mesmo problema. (se no exemplo a função objectivo fosse alterada para Z = 3x1 + 2x2).

Também pode acontecer que não exista nenhuma solução óptima (se não haver nenhuma solução admissível ou se as restrições não evitarem o crescimento infinito da função objectivo).



Método simplexEstrutura algorítmica

Inicialização

Iteração

Teste de optimização

Fim

Processo algébrico em que cada iteração envolve a resolução de um sistema de equações de modo a obter uma nova solução que será testada através do teste de optimização.




Soluções admissíveis correspondentes a um vértice da região de soluções admissíveis:(0, 0), (0, 6), (2, 6), (4, 3) e (4, 0)

Soluções não admissíveis correspondentes a um vértice fora da região de soluções admissíveis :(0, 9), (4, 6) e (6, 0)

x1

x2

2 4

6

8

2

4

6 8

(4, 6)

(4, 3)

(0, 9)

(6, 0)

(4, 0)

(2, 6)(0, 6)

(0, 0)

As soluções admissíveis correspondentes a um vértice da região de soluções admissíveis dizem-se adjacentes quando se podem ligar através de um único segmento de recta.


Programação linearPropriedades das soluções admissíveis correspondentes a vértices da região de soluções admissíveis:

1. Se houver uma solução óptima ela corresponde a um vértice da região de soluções admissíveis.

2. Se houver múltiplas soluções óptimas, então pelo menos duas correspondem a vértices adjacentes da região de soluções admissíveis.

3. Há apenas um número finito de vértices da região de soluções admissíveis (e, portanto das correspondentes soluções admissíveis).

4. Considerando um vértice da região de soluções admissíveis e a correspondente solução admissível, se a nenhum dos vértices a ele adjacentes corresponder uma solução melhor (medida através de Z), então não existe nenhuma solução melhor e, portanto esta é uma solução óptima.



Propriedade 1 e 2

A busca da solução óptima resume-se à análise de apenas as soluções admissíveis correspondentes a vértices da região de soluções admissíveis.

Propriedade 3

Portanto apenas existe um número finito de soluções a considerar.

Propriedade 4

Fornece um conveniente teste de optimização.



Método simplex

Examina apenas um número relativamente pequeno de soluções admissíveis e pára assim que alguma satisfizer o teste de optimização expresso pela propriedade 4.

1. Inicialização: Começa por uma solução admissível correspondente a um vértice da região de soluções admissíveis.

2. Iteração: Passa para outra solução admissível correspondente a um vértice adjacente da região de soluções admissíveis. (Passo repetido até a solução corrente satisfazer o teste de optimização).

3. Teste de optimização: A solução corrente é uma solução óptima se nenhuma das soluções adjacentes for melhor.



Percurso do método simplex para o exemplo:

1. Inicialização: Começa em (0, 0)

2a. Iteração 1: Passa para (0, 6)

2b. Iteração 2: Passa para (2, 6)

3. Teste: Nem (0, 6) nem (4, 3) são melhores que (2, 6). Pára. (2, 6) é solução óptima.


Método simplex

Procedimento algébrico

- Conversão de restrições de desigualdade em restrições de igualdade.

- Introdução de variáveis de desvio

X1 4 X1 + X3 = 4

X3 ≥ 0


Método simplex

Forma aumentada

Maximizar Z = 3x1 + 5x2

Restrições: x1 + x3 = 4

2x2+ x4 = 12

3x1 + 2x2 + x5 = 18

x1, x2, x3, x4, x5 >= 0


Uma solução aumentada é uma solução original à qual foram acrescentados os valores correspondentes às variáveis de desvio.

Exemplo:Solução (3, 2) Solução aumentada (3, 2, 1, 8, 5)

Uma solução aumentada correspondentes a um vértice dentro ou fora da região de soluções admissíveis designa-se solução básica.

Exemplo:Solução (4, 3) Solução aumentada (4, 3, 0, 6, 0)

Uma solução aumentada correspondente a um vértice dentro da região de soluções admissíveis designa-se solução básica admissível.

Método simplex


No exemplo, após a introdução das variáveis de desvio (forma aumentada):

sistema de restrições funcionais - 5 variáveis e 3 equações

2 graus de liberdade na resolução do sistema de equações

Simplex atribui o valor arbitrário 0 a essas variáveis (variáveis não-básicas). As restantes são chamadas variáveis básicas. A solução resultante da resolução do sistema de equações designa-se solução básica. Se todas as variáveis básicas forem não-negativas, a solução obtida chama-se solução básica admissível.

Método simplex


Duas soluções básicas admissíveis são adjacentes se têm as mesmas variáveis não-básicas excepto uma (o mesmo se aplica às suas variáveis básicas).

Assim, para passar de uma solução básica admissível para outra adjacente basta apenas trocar uma variável básica para não-básica e vice-versa em relação a outra variável.

Método simplex


Exemplo:

Soluções adjacentes (0, 0) (0, 6)

Soluções básicas admissíveis correspondentes

(0, 0, 4, 12, 18) (0, 6, 4, 0, 6)

Variáveis não-básicas (x1, x2) (x1, x4)

Para passar de uma para outra basta trocar x2 por x4 como variavél não-básica e vice-versa.

O número de variáveis não básicas numa solução básica é igual ao número de graus de liberdade de um sistema de equações.

O número de variáveis básicas é igual ao número de restrições funcionais.

Método simplex


Método simplex

Inicialização

Teoricamente, podemos começar por qualquer solução básica admíssível.

• Se o problema não se encontrar na forma standard, procede-se a alguns ajustamentos.

• Introduzem-se as variáveis de desvio.• Seleccionam-se as variáveis originais como as variáveis não-

básicas (=0) e as variáveis de desvio como as variáveis básicas para a solução inicial.

• Aplica-se o teste de optimização.


Iteração

Passar para uma solução básica admissível adjacente que seja melhor em termos do valor da F.O. (Z).

– Conversão de uma variável não-básica em básica (variável de entrada)

– Conversão de uma variável básica em não-básica (variável de saída)

Qual o critério para seleccionar a variável de entrada?

Candidatas: Todas as váriáveis não-básicas da solução corrente.

Método simplex


Importa escolher a que mais contribui para melhorar (maximizar) o valor de Z.

– Aquela que possui o maior coeficiente positivo na expressão da F.O.

Exemplo:

Z = 3x1 + 5x2

Variáveis não-básicas: x1 e x2.

x2 tem o maior coeficiente positivo variável de entrada.

Método simplex


Como identificar a variável de saída?

Ignorando as variáveis de desvio, incrementando x2 e deixando x1=0, significa que nos estamos a deslocar ao longo do eixo x2.

A solução admissível correspondente ao vértice da região de soluções admissíveis encontrado será (0, 6) que se alcança ao atingir a recta da restrição 2x2=12.

Solução básica admissível adjacente é alcançada quando a 1ª variável básica (variável de saída) atinge o valor 0. Parar para evitar sair da região de soluções admissíveis (por incumprimento das restrições de não-negatividade).

A variável de saída não se escolhe .

Método simplex


Exemplo:

Candidatas: x3, x4 e x5.

mínimo

X3 x3 = 4 – x1 Não limita

X4 x4 = 12 - 2x2 x2 = 12/2 = 6

X5 x5 = 18 – 3x1 -2x2 x2 = 18/2 = 9

Quando x4= 0, x2 =6

Quando x5= 0, x2 =9

Limite superior para x2 = 6 x4 – variável de saída

Método simplex


Como identificar a nova solução básica admissível?

Sabendo o valor da nova variável não-básica (x4 = 0) e da nova variável básica (x2 = 6), basta resolver o sistema de equações e obtemos os valores das restantes variáveis.

No entanto, para que o sistema fique preparado para a próxima iteração, devemos mante-lo na forma inicial:

• 1 variável básica com coeficiente = 1 em cada equação e que não aparece em nenhuma outra equação.

Método simplex


Operações algébricas para resolver o sistema de equações lineares:

• Multiplicar (ou dividir) uma equação por uma constante não-negativa.

• Adicionar (ou subtrair) um múltiplo de uma equação a outra equação.

Método simplex


Exemplo:

Z -3x1 -5x2 = 0

x1 +x3 = 4

2x2 +x4 = 12

3x1 +2x2 + x5 = 18

x2 +1/2x4 = 6

Para colocar o

coeficiente de x2 = 1:

Div 2

Método simplex


Exemplo:

x2 precisa ainda ser eliminado das outras equações em que aparece:

Z -3x1 -5x2 , 0

+5 ( x2 +1/2x4 , 6)

Z -3x1 +5/2 x4 , 30)

3x1 +2x2 , 18

- 2 ( x2 +1/2x4 , 6)

3x1 -x4 +x5 , 6)

Método simplex


Exemplo:

Resultado da iteração:

Z -3x1 +5/2x4 = 30

x1 +x3 = 4

x2 +1/2x4 = 6

3x1 - x4 + x5 = 6

Nova solução = (0, 6, 4, 0, 6)

Variáveis não-básicas = 0

Variáveis básicas = lado direito da respectiva restrição.

Método simplex


Teste de optimização

Z = 30 + 3x1 -5/2x4

Como x1 tem coeficiente positivo, se aumentarmoso seu valor é possível aumentar o valor de Z e atingir outra solução básica admissível adjacente melhor.

Portanto, esta não é uma solução óptima.

Uma solução básica admissível é óptima se e só se todas as variáveis não-básicas tiverem coeficientes não-positivos ( ≤ 0) na forma corrente da F.O. (resolvida em função de Z).

Método simplex


Forma tabular

• Coeficientes das variáveis• Constantes lado direito das restrições• Variáveis básicas de cada equação

Var.

básicas

Eq.

Nº

CoeficientesLado

direitoZ x1 x2 x3 x4 X5

Z 0 1 -3 -5 0 0 0 0

X3 1 0 1 0 1 0 0 4

X4 2 0 0 2 0 1 0 12

X5 3 0 3 2 0 0 1 18

Método simplex


A solução básica admissível corrente é óptima se e só se todos os coeficientes da F.O. forem não–negativos ( ≥0).

Variáveis não-básicas (x1 e x2 ) têm coeficientes negativos na F.O., logo a solução inicial não se trata de uma solução óptima.

Método simplex


Iteração 1

1. Variável de entrada: variável não-básica com coeficiente negativo de maior valor absoluto – x2.

Var.

básicas

Eq.

Nº

CoeficientesLado


Z 0 1 -3 -5 0 0 0 0

X3 1 0 1 0 1 0 0 4

X4 2 0 0 2 0 1 0 12

X5 3 0 3 2 0 0 1 18

Coluna pivot

Método simplex


Iteração 12. Variável de saída:

• Seleccionar os coeficientes positivos ( >0 )da coluna pivot;• Dividir cada um deles pelo lado direito da respectiva linha da tabela;• Identificar a equação com o menor valor obtido;• Seleccionar a variável básica correspondente a essa equação: x4.

Var.

básicas

Eq.

Nº

CoeficientesLado


Z 0 1 -3 -5 0 0 0 0

X3 1 0 1 0 1 0 0 4

X4 2 0 0 2 0 1 0 12

X5 3 0 3 2 0 0 1 18

Coluna pivot

Linha pivot

Número pivot

12/2 = 6

18/2 = 9

Método simplex


Iteração 13. Nova solução básica admissível (1):

Para modificar o coeficiente da nova variável básica na linha pivot para 1, divide-se toda a linha pelo nº pivot.

Var.

básicas

Eq.

Nº

CoeficientesLado


Z 0 1

X3 1 0 1 0 1 0 0 4

X2 2 0 0 1 0 ½ 0 6

X5 3 0

nova linha pivot = linha pivot antiga

número pivot

Método simplex



Falta ainda colocar os coeficientes da nova variável básica (x2) a 0 nas outras equações.

• linha 0 : coeficiente da coluna pivot = -5• linha 3: coeficiente da linha pivot = 2

nova linha = linha antiga – (coeficiente linha pivot * nova linha pivot)

linha 0:-3 -5 0 0 0, 0

+5 ( 0 1 0 1/2 0, 6)

-3 0 0 5/2 0, 30)

Método simplex



linha 3:3 2 0 0 1, 19

-2 ( 0 1 0 1/2 0, 6)

3 0 0 -1 1, 6)

Var.

básicas

Eq.

Nº

CoeficientesLado


Z 0 1 -3 0 0 5/2 0 30

X3 1 0 1 0 1 0 0 4

X2 2 0 0 1 0 ½ 0 6

X5 3 0 3 0 0 -1 1 6

Nova solução básica admissível =(0, 6, 4, 0, 6)

Método simplex


Iteração 2Variável de entrada = x1

Variável de saída = x5

Número pivot = 3

Solução = (2, 6, 2, 0, 0) Z = 36Solução óptima - nenhum dos coeficientes da F.O. é negativo.

Var.

básicas

Eq.

Nº

CoeficientesLado


Z 0 1 0 0 0 3/2 1 36

X3 1 0 0 0 1 1/3 -1/3 2

X2 2 0 0 1 0 ½ 0 6

X1 3 0 1 0 0 -1/3 1/3 2

Método simplex


Múltiplas soluções (1)

Se a função objectivo do nosso exemplo fosse Z = 3 x1 + 2 x2 todos os pontos do segmento de recta entre (2, 6) e (4, 3) correspondiam a soluções óptimas.

F. O. e a restrição 3 correspondiam a rectas paralelas.

O método pára assim que encontra a 1ª solução óptima.

Em certos casos pode ser importante conhecer e poder optar entre soluções óptimas alternativas.

Método simplex


Múltiplas soluções (2)

Quando um problema tem mais do que 1 solução óptima, pelo menos 1 das variáveis não-básicas tem coeficiente = 0 na equação da F.O. final. Assim, incrementando essa variável, o valor de Z não é alterado.

Outras soluções óptimas podem ser alcançadas executando iterações adicionais do método simplex e escolhendo de cada vez uma variável não-básica com coeficiente = 0 como variável de entrada.

Em geral, podemos identificar 2 soluções óptimas. As restantes podem ser identificadas usando a média ponderada destas duas:

(sol1) + (1-) (sol2) 0 ≤ ≤ 1

Se ignorarmos as variáveis de desvio, esta é a fórmula do segmento de recta definido entre (2, 6) e (4, 3).

Método simplex


Outras formasQuando o problema não se encontra na forma standard (restrições =, ≥ ou bi ≤ 0) temos que proceder a alguns ajustamentos, na fase de inicialização, de forma a que o resto do método simplex possa prosseguir como usualmente.

ai1x1+ai2x2+...+ainxn = bi

ai1x1+ai2x2+...+ainxn bi

ai1x1+ai2x2+...+ainxn ≥ bi

Para evitar aumentar o número de restrições utilizam-se variáveis artificiais.

Método simplex


Outras formas (restrições de igualdade)

Supondo que a 3ª restrição do nosso exemplo era 3x1 + 2 x2 = 18:

A região de soluções admissíveis passa a ser apenas o segmento de recta entre (2, 6) e (4, 3).

Como não precisamos adicionar nenhuma variável de desvio para a equação 3, a solução inicial deixa de ser óbvia (na solução inicial as variáveis de decisão tomam valor 0 e as variáveis de desvio ficam iguais ao lado direito das restrições).

Introduz-se uma variável artificial ( ), tal como se fosse uma variável de desvio, e a respectiva restrição de não-negatividade.

(x1, x2, x3, x4, ) = (0, 0, 4, 12, 18)A variável artificial alarga a região de soluções admissíveis.

Método simplex

5x

5x


Outras formas (restrições de igualdade)

As soluções admissíveis para o problema revisto também são soluções admissíveis para o problema original desde que as variáveis artificiais tomem o valor 0.

Para garantir que a variável artificial ( ) é 0 na solução óptima, temos que introduzi-la na F.O. com um coeficiente negativo extremamente elevado, de modo a que um aumento em provoque uma diminuição enorme no valor de Z. Assim,

Z = 3x1 + 5x2 – M

Método simplex

5x

5x

5x


Outras formas (restrições de igualdade)Agora há que eliminar o coeficiente M de na equação da F.O.:

-3 -5 0 0 M ,0-M ( 3 2 0 0 1 ,18)

(-3M-3) (-2M-5) 0 0 0 ,-18M

Para determinar a variável de entrada compara-se o factor multiplicativo de M (uma vez que o factor aditivo pode ser desprezado, por M ser tão grande).

Neste caso, a variável de entrada seria x1.

Método simplex

5x


Exemplo 2:

Função objectivo: Minimizar Z = o.4x1 + 0.5x2

Restrições: 0.3x1 + 0.1x2 ≤ 2.70.5x1 + 0.5x2 = 60.6x1 + 0.4x2 ≥ 6x1, x2 >= 0

Minimizar Z = o.4x1 + 0.5x2 + M x4

0.3x1 + 0.1x2 + x3 ≤ 2.70.5x1 + 0.5x2 + x4 = 60.6x1 + 0.4x2 ≥ 6x1, x2, x3, x4 >= 0

Método simplex


Exemplo 2:

Método simplex

x1

x2

2 4

6

8

2

4

6 8

(6, 6)

(7.5, 4.5)

0.5x1 + 0.5x2 = 6

10 12

10

12

14

0.6x1 + 0.4x2 ≥ 6

0.3x1 + 0.1x2 ≤ 2.7

(8, 3)


Caso das restrições ≥

Multiplicam-se ambos os lados da inequação por -1:

0.6x1 + 0.4x2 ≥ 6

- 0.6x1 - 0.4x2 ≤ - 6

- 0.6x1 - 0.4x2 + x5 = - 6

Método simplex


Lados direitos da restrições < 0

- 0.6x1 - 0.4x2 + x5 = - 6

No caso de x1, x2 = 0 (solução básica admissível inicial) x5 = -6, o que não estaria de acordo com as restrições de não-negatividade.Se voltarmos a multiplicar ambos os lados da equação por -1:

0.6x1 + 0.4x2 – x5 = 6Torna o lado direito positivo, mas continuamos a ter x5 negativo para o caso de x1, x2 = 0.A equação agora pode ser vista como uma restrição de igualdade e aplicar-se as técnicas das variáveis artificiais:

0.6x1 + 0.4x2 – x5 + x6 = 6

Onde x6 seria usada como variável básica inicial.

Método simplex


Exemplo 2:

Função objectivo: Minimizar Z = o.4x1 + 0.5x2

Restrições: 0.3x1 + 0.1x2 ≤ 2.70.5x1 + 0.5x2 = 60.6x1 + 0.4x2 ≥ 6x1, x2 >= 0

Minimizar Z = o.4x1 + 0.5x2 + M x4 + M x6

0.3x1 + 0.1x2 + x3 ≤ 2.70.5x1 + 0.5x2 + x4 = 60.6x1 + 0.4x2 - x5 + x6 ≥ 6x1, x2, x3, x4, x5, x6 >= 0

Método simplex


Minimização

Minimizar Z =

Maximizar - Z =

Exemplo:Max - Z = - 0.4x1 - 0.5x2 – M - M

Método simplex

n

iiixc

1

n

iii xc

1

4x 6x


Minimização

As variáveis básicas (x3, , ) necessitam ainda de ser eliminadas da F.O.

e têm coeficientes M

0.4 0.5 0 M 0 M ,0

-M ( 0.5 0.5 0 1 0 0 ,6)-M ( 0.6 0.4 0 0 -1 1 ,6)

(-1.1M+0.4) (-0.9M+0.5) 0 0 0 M ,-12M

Método simplex

6x4x

6x4x


Inexistência de soluções admissíveis

A escolha de solução básica admissível inicial pode não ser óbvia pelo facto do problema não possuir nenhuma solução admissível.

Pela técnica das variáveis artificiais:

Se o problema original não tiver nenhuma solução admissível, então na solução final existe pelo menos uma variável artificial > 0. De outro modo todas serão 0 na solução final.

Método simplex


Variáveis que podem tomar valores negativos

xi >= Li Li < 0

xi’ = xi – Li xi’ ≥ 0

(xi’ + Li) será substituido por xi em todo o modelo, de modo a que xi’ não possa ser negativo.

Método simplex


Variáveis que podem tomar valores negativos

Exemplo: x1 ≥ -10

x1 = x1’ - 10

Método simplex

Z = 3x1 + 5x2

x1 ≤ 42x2 ≤ 123x1 + 2x2 ≤ 18x1 ≥ -10, x2 ≥ 0

Z = 3(x1’ - 10) + 5x2

(x1’ – 10) ≤ 42x2 ≤ 123(x1’ - 10) + 2x2 ≤ 18(x1’ - 10) ≥ -10, x2 ≥ 0

Z = -30 + 3x1’ + 5x2

x1’ ≤ 142x2 ≤ 123x1’ + 2x2 ≤ 48x1’ ≥ 0, x2 ≥ 0

Documents

Sistemas de Apoio à Decisão 1 Modelos de decisão