Modelos de decisão
Sistemas de Apoio à Decisão
1
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.
Sistemas de Apoio à Decisão
2
Modelos de decisão
Objectivo
Porque é que o sistema existe?
Função
Como é que funciona?
Estado
O que está a fazer?
Forma
Qual é o seu aspecto?
Descreve
Explica
Prevê
Sistemas de Apoio à Decisão
3
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.
Sistemas de Apoio à Decisão
4
Modelos de decisão
Abstracçã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
Sistemas de Apoio à Decisão
5
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.
Sistemas de Apoio à Decisão
6
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.
Sistemas de Apoio à Decisão
7
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.
Sistemas de Apoio à Decisão
8
Modelos quantitativos
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
• ...
Sistemas de Apoio à Decisão
9
Modelos quantitativos
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.
Sistemas de Apoio à Decisão
10
Modelos quantitativos
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.
Sistemas de Apoio à Decisão
11
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).
Sistemas de Apoio à Decisão
12
Programação linear
Exemplo:
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.
Departamentos
1
2
3
4
12
18
Produto 1
1
0
3
Produto 2
0
2
2
Tempo disponível (h)
Tempo requerido por unidade (h)
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.
Sistemas de Apoio à Decisão
13
Programação linear
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
Restrições:
x1 <= 4
Z = 3x1 + 5x2
2x2<= 12
3x1 + 2x2 <= 18
x1, x2 >= 0
Sistemas de Apoio à Decisão
14
Programação linear
Representação gráfica do problema
x2
x1 = 4
3x1 + 2x2 = 18
8
2x2 = 12
6
4
2
2
Sistemas de Apoio à Decisão
4
6
8
x1
15
Programação linear
Representação gráfica do problema
x2
Z = 36 = 3x1 + 5x2
8
(2, 6)
6
Z = 20 = 3x1 + 5x2
4
Z = 10 = 3x1 + 5x2
2
2
Sistemas de Apoio à Decisão
4
6
8
x1
16
Programação linear
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
Sistemas de Apoio à Decisão
Restrições funcionais
Restrições de
não negatividade
17
Programação linear
Outras formas
1.
Minimização da função objectivo:
Min
2.
Z = c1x1+c2x2+...+cnxn
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.
Sistemas de Apoio à Decisão
18
Programação linear
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).
Sistemas de Apoio à Decisão
19
Programação linear
Método simplex
Estrutura 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.
Sistemas de Apoio à Decisão
20
Programação linear
Representação gráfica do problema
x2
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)
(0, 9)
8
6
(0, 6)
(2, 6)
(4, 6)
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)
4
(4, 3)
2
(6, 0)
(0, 0)
2
4
(4, 0)
6
8
x1
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.
Sistemas de Apoio à Decisão
21
Programação linear
Propriedades 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.
Sistemas de Apoio à Decisão
22
Programação linear
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.
Sistemas de Apoio à Decisão
23
Programação linear
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.
Sistemas de Apoio à Decisão
24
Programação linear
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.
Sistemas de Apoio à Decisão
25
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 
Sistemas de Apoio à Decisão
X 1 + X3 = 4
X3 ≥ 0
26
Método simplex
Forma aumentada
Maximizar
Z = 3x1 + 5x2
Restrições:
x1 +
x3
2x2+
3x1 + 2x2 +
=4
x4
= 12
x5 = 18
x1, x2, x3, x4, x5 >= 0
Sistemas de Apoio à Decisão
27
Método simplex
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.
Sistemas de Apoio à Decisão
28
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.
Sistemas de Apoio à Decisão
29
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.
Sistemas de Apoio à Decisão
30
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.
Sistemas de Apoio à Decisão
31
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, procedese a alguns ajustamentos.
• Introduzem-se as variáveis de desvio.
• Seleccionam-se as variáveis originais como as variáveis nãobá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.
Sistemas de Apoio à Decisão
32
Método simplex
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.
Sistemas de Apoio à Decisão
33
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.
Sistemas de Apoio à Decisão
34
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 .
Sistemas de Apoio à Decisão
35
Método simplex
Exemplo:
Candidatas: x3, x4 e x5.
X3
x3 = 4 – x1
Não limita
X4
x4 = 12 - 2x2
x2 = 12/2 = 6
X5
x5 = 18 – 3x1 -2x2
x2 = 18/2 = 9
Limite superior para x2 = 6
Sistemas de Apoio à Decisão
Quando x4= 0, x2 =6
mínimo
Quando x5= 0, x2 =9
x4 – variável de saída
36
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.
Sistemas de Apoio à Decisão
37
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ãonegativa.
• Adicionar (ou subtrair) um múltiplo de uma equação a outra
equação.
Sistemas de Apoio à Decisão
38
Método simplex
Exemplo:
Z
Para
colocar o
coeficiente
de x2 = 1:
-3x1
x1
3x1
Div 2
Sistemas de Apoio à Decisão
-5x2
+x3
2x2
+2x2
+x4
x2
+1/2x4
+ x5
=0
=4
= 12
= 18
=6
39
Método simplex
Exemplo:
x2 precisa ainda ser eliminado das outras equações em que aparece:
Z
-3x1
+5 (
Z
-5x2
x2
-3x1
3x1
-2(
3x1
Sistemas de Apoio à Decisão
+2x2
x2
,0
+1/2x4
, 6)
+5/2 x4
, 30)
18
, 6)
,
+1/2x4
-x4
+x5 , 6)
40
Método simplex
Exemplo:
Resultado da iteração:
Z
-3x1
x1
+5/2x4
+x3
x2
3x1
= 30
=4
+1/2x4
=6
- 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.
Sistemas de Apoio à Decisão
41
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).
Sistemas de Apoio à Decisão
42
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º
Z
Coeficientes
Lado
direito
Z
x1
x2
x3
x4
X5
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
Sistemas de Apoio à Decisão
43
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.
Sistemas de Apoio à Decisão
44
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º
Z
Coeficientes
Lado
direito
Z
x1
x2
x3
x4
X5
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
Sistemas de Apoio à Decisão
45
Método simplex
Iteração 1
2. 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º
Z
Coeficientes
Lado
direito
Z
x1
x2
x3
x4
X5
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
12/2 = 6
X5
3
0
3
2
0
0
1
18
18/2 = 9
Linha pivot
Número pivot Coluna pivot
Sistemas de Apoio à Decisão
46
Método simplex
Iteração 1
3.
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.
linha pivot antiga
nova linha pivot =
Coeficientes
Var.
básicas
Eq.
Nº
Z
0
1
X3
1
X2
X5
Sistemas de Apoio à Decisão
número pivot
Z
Lado
direito
x1
x2
x3
x4
X5
0
1
0
1
0
0
4
2
0
0
1
0
½
0
6
3
0
47
Método simplex
Iteração 1
3.
Nova solução básica admissível (2):
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:
+5 (
-3
0
-5
1
0
0
0
1/2
0,
0,
0
6)
-3
0
0
5/2
0,
30)
Sistemas de Apoio à Decisão
48
Método simplex
Iteração 1
3.
Nova solução básica admissível (3):
linha 3:
-2 (
Var.
básicas
Eq.
Nº
3
0
2
1
0
0
0
1/2
1,
0,
19
6)
3
0
0
-1
1,
6)
Coeficientes
Z
x1
x2
x3
x4
X5
Lado
direito
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
Sistemas de Apoio à Decisão
Nova solução básica
admissível =
(0, 6, 4, 0, 6)
49
Método simplex
Iteração 2
Variável de entrada = x1
Variável de saída = x5
Número pivot = 3
Var.
básicas
Eq.
Nº
Z
Coeficientes
Lado
direito
Z
x1 x 2 x3
x4
X5
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
Solução = (2, 6, 2, 0, 0) 
Z = 36
Solução óptima - nenhum dos coeficientes da F.O. é negativo.
Sistemas de Apoio à Decisão
50
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.
Sistemas de Apoio à Decisão
51
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).
Sistemas de Apoio à Decisão
52
Método simplex
Outras formas
Quando 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.
Sistemas de Apoio à Decisão
53
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 ( x5), tal como se fosse uma
variável de desvio, e a respectiva restrição de não-negatividade.
(x1, x2, x3, x4, x5) = (0, 0, 4, 12, 18)
A variável artificial alarga a região de soluções admissíveis.
Sistemas de Apoio à Decisão
54
Método simplex
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 ( x5 ) é 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 x5 provoque
uma diminuição enorme no valor de Z. Assim,
Z = 3x1 + 5x2 – M x
5
Sistemas de Apoio à Decisão
55
Método simplex
Outras formas (restrições de igualdade)
Agora há que eliminar o coeficiente M de x5 na equação da F.O.:
0
0
0
0
M
1
,0
,18)
(-3M-3) (-2M-5) 0
0
0
,-18M
-M (
-3
3
-5
2
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.
Sistemas de Apoio à Decisão
56
Método simplex
Exemplo 2:
Função objectivo:
Minimizar
Z = o.4x1 + 0.5x2
0.3x1 + 0.1x2 ≤ 2.7
0.5x1 + 0.5x2 = 6
0.6x1 + 0.4x2 ≥ 6
x1, x2 >= 0
Restrições:
Minimizar
Z = o.4x1 + 0.5x2 + M x4
0.3x1 + 0.1x2 + x3 ≤ 2.7
0.5x1 + 0.5x2 + x4 = 6
0.6x1 + 0.4x2 ≥ 6
x1, x2, x3, x4 >= 0
Sistemas de Apoio à Decisão
57
Método simplex
x2
Exemplo 2:
14
0.6x1 + 0.4x2 ≥ 6
12
10
8
0.3x1 + 0.1x2 ≤ 2.7
6
(6, 6)
(7.5, 4.5)
4
(8, 3)
0.5x1 + 0.5x2 = 6
2
2
Sistemas de Apoio à Decisão
4
6
8
10
12
x1
58
Método simplex
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
Sistemas de Apoio à Decisão
59
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 = 6
Torna 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 aplicarse as técnicas das variáveis artificiais:
0.6x1 + 0.4x2 – x5 + x6 = 6
Onde x6 seria usada como variável básica inicial.
Sistemas de Apoio à Decisão
60
Método simplex
Exemplo 2:
Função objectivo:
Minimizar
Z = o.4x1 + 0.5x2
0.3x1 + 0.1x2 ≤ 2.7
0.5x1 + 0.5x2 = 6
0.6x1 + 0.4x2 ≥ 6
x1, x2 >= 0
Restrições:
Minimizar
Z = o.4x1 + 0.5x2 + M x4 + M x6
0.3x1 + 0.1x2 + x3 ≤ 2.7
0.5x1 + 0.5x2 + x4 = 6
0.6x1 + 0.4x2 - x5 + x6 ≥ 6
x1, x2, x3, x4, x5, x6 >= 0
Sistemas de Apoio à Decisão
61
Método simplex
Minimização
n
Minimizar
Z=
c x
i 1
i i
n
Maximizar
-Z=
  c x
i 1
i
i
Exemplo:
Max
- Z = - 0.4x1 - 0.5x2 – M x4 - M x6
Sistemas de Apoio à Decisão
62
Método simplex
Minimização
As variáveis básicas (x3, x4 , x6 ) necessitam ainda de ser eliminadas
da F.O.
x4 e x6 têm coeficientes M
0.4
0.5
0
M
0
M
,0
-M ( 0.5
-M ( 0.6
0.5
0.4
0
0
1
0
0
-1
0
1
,6)
,6)
0
M
,-12M
(-1.1M+0.4) (-0.9M+0.5) 0 0
Sistemas de Apoio à Decisão
63
Método simplex
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.
Sistemas de Apoio à Decisão
64
Método simplex
Variáveis que podem tomar valores negativos
xi >= Li
Li < 0
x i’
x i’ ≥ 0
=
xi – Li
(xi’ + Li) será substituido por xi em todo o modelo, de modo a que xi’
não possa ser negativo.
Sistemas de Apoio à Decisão
65
Método simplex
Variáveis que podem tomar valores negativos
Exemplo:
x1 ≥ -10
x1 = x1’ - 10
Z = 3x1 + 5x2
x1
≤ 4
2x2
≤ 12
3x1 + 2x2 ≤ 18
x1 ≥ -10, x2 ≥ 0
Sistemas de Apoio à Decisão
Z = 3(x1’ - 10) + 5x2
(x1’ – 10)
≤ 4
2x2
≤ 12
3(x1’ - 10) + 2x2
≤ 18
(x1’ - 10) ≥ -10, x2 ≥ 0
Z = -30 + 3x1’ + 5x2
x1’
≤ 14
2x2
≤ 12
3x1’ + 2x2 ≤ 48
x1’ ≥ 0, x2 ≥ 0
66