Origem da Investigação Operacional Para quê a Investigação Operacional (I.O.)? A Investigação Operacional surgiu para resolver, duma forma mais eficiente,

Origem da Investigação Operacional

Para quê a Investigação Operacional (I.O.)?

A Investigação Operacional surgiu para resolver, duma forma mais eficiente, os problemas na administração das organizações, originados pelo acelerado desenvolvimento provocado pela revolução industrial.

Investigação Operacional

A partir da Revolução Industrial aumentam os problemas na gestão das organizações:

• distribuição e utilização óptima dos recursos;

• as diferentes componentes dentro duma organização são sistemas autónomos com objectivos e gestão próprios;

• os objectivos cruzam-se: o que pode ser melhor para uns pode ser prejudicial para outros.

Quando é que surgiu a Investigação Operacional?

A origem da I.O. como ciência é atribuída à coordenação das operações militares durante a 2ª Guerra Mundial.

aplicação de métodos científicos na gestão das organizações:

abordagem quantitativa e qualitativa na tomada de decisões;

orientação sistemática: o problema é analisado no contexto dum

sistema que inclui diversas componentes interrelacionadas entre si;

extensibilidade: pode ser aplicada a um largo número de

organizações.

Características fundamentais da Investigação Operacional

I.O. - Ciência da AdministraçãoA I.O. tem provocado um impacto significativo na gestão e administração de empresas e diferentes organizações, daí ser denominada “a ciência da administração”. A sua utilização e implementação tem sido estendida a áreas como:

negócios,

economia,

indústria,

engenharia civil,

governos,

hospitais, etc.

Problemas de Optimização

Problemas de Optimização Problemas de Optimização

Programação Programação MatemáticaMatemática

ProgramaçãoProgramação Linear Linear

ProgramaçãoProgramação Não Linear Não Linear

Os Ramos da I.O.

Quais são os ramos mais importantes desenvolvidos na I.O.?

PROGRAMAÇÃO MATEMÁTICA

Programação Linear (P. L.)Principais áreas: Económica

MatemáticaMilitar

Programação Não LinearProgramação DinâmicaProgramação InteiraOptimização Global

• na Antiguidade:

Euclides, Newton, Lagrange

• no século XX:

Leontief, Von Neumann, Kantarovich

Recuando no tempo...

Em 1947, George Dantzig com a colaboração de Koopmans, ambos a trabalhar no Departamento da Força Aérea Americana, apresentaram um método denominado Simplex para a resolução dos problemas de Programação Linear (P.L.).

DantzigKoopmans

Programação Linear

ProgramaçãoProgramação

Planeamento de actividades

LinearLinear

O problema é representado

matematicamente pelo modelo de PM

onde todas as funções f (x1, x2 ,… , xn ),

gi(x1, x2 , … , xn ), i=1,…,m são lineares.

Programação Linear

O que são problemas de Programação Linear?

Os problemas de Programação Linear são uma classe particular de Problemas de Programação Matemática (P.M.), onde a função objectivo e as restrições podem ser representadas por funções lineares.

A Programação Linear determina o planeamento óptimo de actividades, ou seja, um plano óptimo que represente a melhor solução entre todas as alternativas possíveis.

1 - Problemas de Transporte

rentabilização de aeroportos;optimização de tráfego interno ou de comunicação de vários tipos;planificação dos semáforos de circulação numa cidade.

2 - Problemas de Composição

composição de medicamentos;blindagem de ligas metálicas e combustíveis; rações de animais e adubos;gelados e produtos alimentares.

3 - Problemas de Formação e Produção

corte de barras e chapas;designação de pessoas e tarefas (composição de tabelas de horários);planeamento da produção de uma empresa têxtil.

Tipos de Problemas de P.L.

Conceitos FundamentaisA função linear a optimizar (maximizar ou minimizar), Z= c1 x1 + c2 x2 + …+ cn xn , designa-se por função objectivo (f.o.).

As variáveis x1 , x2 , ... , xn , designam-se por variáveis de decisão.

As variáveis que se usam para transformar inequações em equações, designam-se por variáveis de folga.

As equações (inequações) que se impõem ao problema, designam-se por restrições.

• As restrições do tipo , = ou que relacionam as variáveis do problema, designam-se por restrições do problema.• As desigualdades do tipo x1 0 , ... , xn 0, designam-se por restrições de não negatividade.

Quando as restrições do problema envolvem apenas equações, este apresenta-se na forma padrão.

Quando as restrições do problema envolvem apenas inequações, este apresenta-se na forma canónica.

Qualquer conjunto de valores para as variáveis(x1, x2,…, xn) que satisfaça as restrições do problema, designa-se por solução.

Qualquer especificação de valores para as variáveis de decisão (x1, x2,…, xn ) que satisfaça as restrições do modelo e as condições de não negatividade, designa-se por solução admissível.

Quando a função objectivo cresce (maximização) ou decresce (minimização), indefinidamente, tendo em conta as restrições do problema, designa-se por solução ilimitada.

O conjunto de todas as soluções admissíveis designa-se por região de admissibilidade.

Uma solução óptima maximiza (minimiza) a função objectivo sobre toda a região de admissibilidade.

Problemas de P. L.

O que são problemas de P.L. ?

Os problemas de P. L. são problemas de maximização ou minimização de funções lineares (funções objectivo), num determinado domínio, normalmente definido por um conjunto de restrições nas variáveis.

Estes problemas são representados matematicamente por modelos que podem ser apresentados na forma padrão ou na forma canónica.

Maximizar(minimizar) Z= c1 x1 + c2 x2 + …+ cn xn

sujeito a a11 x1 + a12 x2 + … + a1 j xj + …+ a1n xn { , =, } b1

a21 x1 + a22 x2 + … + a2 j xj + …+ a2n xn {, =, } b2

…

ai 1 x1 + ai 2 x2 + … + ai j xj + …+ ai n xn {, =, } bi

…am 1 x1 + am 2 x2 + … + am j xj + …+ am n xn {, =, } bm

x1, x2,…, xj ,…, xn 0

onde ai j , bi e cj ( i=1,2,…,m, j=1,2,…,n ) são constantes e em cada

restrição apenas se verifica uma e só uma das relações {, =, }.

Função objectivoFunção objectivo

Condições de nãoCondições de não negatividade negatividade

restriçõesrestrições

Formulação Matemática do Modelo de P.L.

É também frequente o modelo de P. L. ser apresentado utilizando as notações:

• cartesiana

• matricial

• vectorial

Notações do modelo

1º. Forma Cartesiana

Maximizar Z= c1 x1 + c2 x2 + …+ cn xn

sujeito a a11 x1 + a12 x2 + …+ a1nxn b1

a21 x1 + a22 x2 + …+ a2n xn b2

…

am 1 x1 + am 2 x2 + …+ am n xn bm

x1, , x2 ,..., xj ,..., xn 0

n

jjj xcZ

1

n

jijij bxa

1

0jx

mi ,...,2,1nj ,...,2,1

Maximizar

2º. Forma Matricial


sujeito a a11 x1 + a12 x2 + …+ a1n xn b1

a21 x1 + a22 x2 + …+ a2n xn b2

…

am 1 x1 + am 2 x2 + …+ am n xn bm

x1, , x2 ,..., xj ,..., xn 0

Maximizar

bAX

0X

XcZ '

nn xxxXcccc ,...,,,,...,, 21

'

21

'

)(0,...,0,00,

nmijaA

,,...,,'

21 mbbbb

3º. Forma Vectorial


sujeito a a11 x1 + a12 x2 + …+ a1n xn b1

a21 x1 + a22 x2 + …+ a2n xn b2

…

am 1 x1 + am 2 x2 + …+ am n xn bm

x1, , x2 ,..., xj ,..., xn 0

Maximizar

onn PPxPxPx ...2211

0jxnj ,...,2,1

'

21 ,...,, mjjjj aaaP '

210 ,...,, mbbbP

'21

'

21 ,...,,,,...,, nn xxxXcccc

XcZ '

As duas formas apresentadas (padrão e canónica) são equivalentes. Com efeito, mediante as operações a seguir indicadas, é sempre possível dar a qualquer problema uma destas formas, sem que o conjunto de soluções se altere.

Operações de reformulação

1. Qualquer problema de maximização pode converter-se num problema de minimização, pois:

máximo Z = - mínimo (-Z)

2. Qualquer restrição de desigualdade do tipo “” pode ser convertida numa restrição do tipo “”, multiplicando por (-1) ambos os membros:

ai 1 x1 + ai 2 x2 + …+ ai n xn bi

- ai 1 x1 - ai 2 x2 - …- ai n xn - bi

3. Qualquer restrição de igualdade pode ser convertida em duas restrições de desigualdades “ ” equivalentes àquela.

ai 1 x1 + …+ ai n xn = bi ai 1 x1 + …+ ai n xn bi

ai 1 x1 + …+ ai n xn bi


-ai 1 x1 - …- ai n xn - bi

4. Qualquer restrição de desigualdade pode ser convertida numa restrição de igualdade, através da introdução de uma nova variável (variável de desvio ou folga) xn+1 de valor não negativo .


bi - ai 1 x1 - …- ai n xn 0

xn+1 = bi - ai 1 x1 - …- ai n 0

ai 1 x1 + … + ai nxn + xn+1 = bi

xn+1 0

5. Qualquer variável livre xj, (não restringida pela condição de não negatividade) pode ser substituída por um par de variáveis não negativas xj' 0 e xj'' 0, fazendo:

xj = xj' - xj''

e deste modo formulando de novo o problema em função destas duas variáveis.

Hipóteses do modelo de P.L.

Qualquer modelo de P.L. deve cumprir as seguintes hipóteses que garantem a linearidade da função objectivo e das restrições do problema:

» Proporcionalidade

» Aditividade

» Divisibilidade e não negatividade

» Linearidade da função objectivo

- Proporcionalidade

Em cada actividade a quantidade de bens que entram e saem são sempre proporcionais ao nível da mesma.

- Aditividade

Dadas n actividades, o resultado do emprego conjunto das mesmas é a sua adição.

-Divisibilidade e não negatividade

O nível de uma actividade pode assumir qualquer valor positivo de um dado intervalo, o que equivale a supor que os bens são perfeitamente divisíveis, isto é, susceptíveis de variar em quantidades infinitesimais.

-Linearidade da função objectivo

Cada actividade contribui para o objectivo global perseguido pelo sistema (por exemplo, cada actividade normalmente tem associado um certo lucro ou um certo custo). Esta hipótese indica que essa contribuição para a função económica é proporcional ao nível da actividade.

A contribuição total é a soma das contribuições de todas as actividades.

Problema

Custo global: soma dos custos de transporte i para j

em função de xij

Designação de

actividade

Intensidade (incógnita)

Recursos e restrições

Função objectivo

Transporte da unidade i para o

armazém j

Quantidade a transportar de i

para j : xij

Colocação do alimento i na

dieta

Percentagem de i na dieta (xi)

Custo global da composição

Produção do produto j

Quantidade a produzir do produto

j : xj

Quantidade de recurso disponível;Quantidade derecurso i gasto na produção de uma unidade do produto j

Lucro global: soma dos lucros obtidos pela produção dos produtos j em

função de xj

Níveis calóricos e vitamínicos mínimos

A -

Transporte

B -

Composição

C -

Produção

Capacidade de fornecimento em i; quantidade requerida no armazém j

Formulação dos vários tipos de problemas de P.L.

Problema de Transporte

cij - custo de transporte de uma unidade de produto da unidade i para o armazém j

ij

ijij xcmin

s.a.

j

iij axM unidades produtoras M restrições de oferta; ai -OFERTA da unidade produtora i; i=1…m;

N armazéns receptores N restrições de procura;bj- PROCURA do armazém receptor j , j=1,…n;

i

jij bx

0ijx

Problema


em função de xij

Designação de

actividade



Função objectivo


armazém j


para j : xij


dieta





j : xj



função de xj


A -

Transporte

B -

Composição

C -

Produção



Problema de Composição

i

ii xcmin

com

i

ii uxa nível calórico

i

ii vxb nível vitamínico

0ix

sendo: ai e bi - o conteúdo calórico e vitamínico unitário de cada alimento i, ci - o custo unitário de i , e u e v, os níveis mínimos exigidos.

Problema


em função de xij

Designação de

actividade



Função objectivo


armazém j


para j : xij


dieta





j : xj



função de xj


A -

Transporte

B -

Composição

C -

Produção



Problema de Produção

j

jj xcmax

comi

jjij bxa restrições dos recursos

0jx

sendo i=1…m, j=1,…n, cj o lucro obtido por cada unidade do produto j , aij a quantidade de recurso i gasto na produção de uma unidade do produto j, e bi a quantidade de recurso disponível.

A empresa Nova Linha produz artigos de vidro: janelas e portas, em três secções de produção:

Secção de Serralharia: para produzir as estruturas de alumínioSecção de Carpintaria: para produzir as estruturas de madeiraSecção de Vidro e Montagem: para produzir vidro e montar as portas e janelas

Devido à diminuição dos lucros, o gerente decidiu reorganizar a produção, e propõe produzir os 2 produtos que têm uma melhor aceitação entre os clientes.

Estes produtos são:Produto 1: uma porta de vidro com estrutura de alumínioProduto 2: uma janela grande com estrutura de madeira

PROBLEMA DE MAXIMIZAÇÃO

O Departamento de Marketing concluiu que a empresa pode vender tanto de qualquer dos dois produtos, tendo em conta a capacidade de produção disponível. Como ambos os produtos partilham a capacidade de produção da secção nº 3, o gerente solicitou ao Departamento de Investigação Operacional da empresa a resolução deste problema.

O Departamento de I.O. formulou o problema, utilizando os seguintes dados:

• a capacidade de produção por minuto de cada secção a ser utilizada na produção de ambos os produtos;• a capacidade de produção por minuto de cada secção, a ser utilizada para produzir uma unidade de cada produto;• os lucros unitários para cada produto.

Maximizar Z = 3x + 5y

sujeito a x 4 2y 12 3x + 2y 18

x 0, y 0

x , y - o número de unidades do produto 1 e 2 produzidas por minuto.Z - o lucro total por minuto.

Capacidade utilizada por unidade de

produção Secção n.º Produto 1 Produto 2 Capacidade

disponível 1 2 3

1 0 3

0 2 2

4 12 18

Lucros unitários

(em euros)

3 5

Formulação

I. Identificar os valores de (x, y) que satisfaçam todas as restrições (região de admissibilidade)

1º x 4 (x , y) estão situados à esquerda ou sobre a recta x = 4

2º 2 y 12 y 6 (x , y) estão situados abaixo ou sobre a recta y = 6

3º 3 x + 2 y 18 (x , y) estão situados abaixo ou sobre a recta 3x + 2y =18

4º x 0, y 0 (x , y) estão no 1º Quadrante

II. Determinar a solução

A função objectivo Z = 3x + 5y define uma recta que pode ser deslocada paralelamente no sentido do seu gradiente (garantindo o crescimento de Z), até se tornar tangente à região admissível.

Neste caso o ponto de tangência (2,6) optimiza a função objectivo, pelo que a solução pretendida é x = 2, y = 6. O valor óptimo é 36.

Nova Linha deve fabricar duas portas (produto 1) e seis janelas (produto 2) por minuto obtendo um lucro

de 36 euros por minuto.

Problema de Minimização

Um criador de cavalos pretende determinar as quantidades de cada tipo de ração que devem ser dadas diariamente a cada animal por forma a conseguir uma certa quantidade nutritiva a um custo mínimo.

Os dados relativos ao custo de cada tipo de ração, às quantidades mínimas diárias de ingredientes nutritivos básicos a fornecer a cada animal, bem como às quantidades destes existentes em cada tipo de ração (g/kg) constam no seguinte quadro:

FormulaçãoRação

Ingredientesnutritivos

Granulado Farinha Quantidademínima

requeridaCarbohidratos

VitaminasProteínas

205030

501030

200150210

Custos(euros/Kg)

0.05 0.03

Minimizar Z = 0.05x + 0.03ySujeito a

20x + 50y 20050x + 10y 15030x + 30y 210x 0, y 0

x, y - quantidades (em Kg), de granulado e farinha, respectivamente, a fornecer diariamente a cada animal Z - custo total (em euros) a suportar diariamente com a alimentação de cada animal.

I. Identificar os valores de (x, y) que satisfaçam todas as restrições (região de admissibilidade)

1º 20x + 50y 200 2x + 5y 20 (x,y) estão situados acima ou sobre a recta 2x + 5y =20

2º50x + 10y 150 5x + y 15 (x,y) estão situados acima ou sobre a recta 5x + y = 15

3º30x + 30y 210 x + y 7 (x,y) estão situados acima ou sobre a recta x + y = 7;

4º x 0, y 0 (x , y) estão no 1º Quadrante

II. Determinar a solução

A função objectivo Z = 0.05x + 0.03y define uma recta que pode ser deslocada paralelamente no sentido contrário ao do seu gradiente (garantindo o decréscimo de Z), até se tornar tangente à região admissível.

Neste caso o ponto de tangência (2,5) optimiza a função objectivo, pelo que a solução pretendida é x = 2, y =5 . O valor óptimo é 0.25.

Desta “dieta” resulta para cada criador de cavalos um custo de alimentação diário com cada animal de

0,25€.

Um problema de P.L. pode ter:

uma única solução óptimaou

múltiplas soluções óptimas (uma infinidade)ou

não ter óptimo finitoou

não ter nenhuma solução (neste caso o problema é impossível)

Soluções do Problema de P.L.

Casos particulares

•Situações em que a solução não é limitada;

•Situações em que existem soluções óptimas alternativas;

•Situações em que o problema é impossível.

Em qualquer dos problemas anteriores pode afirmar-se que se está perante problemas de P.L. “bem comportados”, uma vez que ambos têm uma única solução óptima. Existe contudo a possibilidade de situações “anómalas” que devem ser consideradas quando, se pretende apresentar uma técnica capaz de resolver qualquer problema de P.L..

No exemplo de maximização, determinamos uma única solução óptima: x = 2 , y = 6, onde a função objectivo alcança o seu valor máximo Z=36 .

Uma Única Solução Óptima

Múltiplas Soluções Óptimas Se um problema de P.L. tem soluções óptimas múltiplas então

tem um número infinito delas.

No exemplo de maximização, mudando o lucro unitário do produto 2 de 5 euros para 2 euros, a função objectivo é agora a recta Z = 3x + 2y (a f.o. tem o mesmo gradiente da recta da 3ª restrição 3x+ 2y = 18). Todos os pontos (uma infinidade) do segmento de recta AB, são soluções óptimas, pois todas alcançam o melhor valor da f.o.: Z = 18

Se as restrições não evitarem o crescimento indefinido do valor da função objectivo Z, então o problema não tem óptimo finito (esta situação não ocorre em problemas de minimização devido ás restrições de não negatividade).

No exemplo de maximização, eliminando as restrições: y 6, 3x +2y 18, a região de admissibilidade fica não limitada e o valor da função objectivo pode crescer indefinidamente nesta região.

O Problema não tem Óptimo Finito

O problema é ImpossívelSe não existissem soluções admissíveis (o conjunto de soluções admissíveis é vazio), então o problema não tem nenhuma solução, o problema é impossível.

No exemplo de maximização, modificando a restrição x 4 para x 7 e mantendo todas as outras, não há nenhuma solução que verifique todas as restrições do problema.

Método Simplex

O primeiro e mais importante passo na sua descoberta foi concluir que a região admissível é um polítopo.

Dantzig

Polítopo: Poliedro Convexo e LimitadoO invólucro convexo de um conjunto S com um número finitos de pontos designa-se por polítopo (poliedro convexo limitado).

x1

x2

K

AA BB

CC

DDEE

FFA região sombreada fornece um poliedro convexo gerado pelos pontos A,B,C,D,E,F

O polítopo gerado por n+1 pontos em n designa-se por simplex.

Exemplo de Polítopo

A região admissível é um polítopo

•A região admissível é um polítopo;

•O ponto óptimo está sobre algum dos vértices da região admissível;

•A função objectivo tem geralmente valores diferentes para cada vértice;

•Pode-se melhorar a função objectivo passando de vértice para vértice.

Ideias importantes

Como determinar uma solução do problema de P.L. na forma Padrão?

Maximizar Z= c1 x1 + c2 x2 + …+ cn xn (3.1)

sujeito a

a11 x1 + a12 x2 + …+ a1n xn = b1 (3.2)a21 x1 + a22 x2 + …+ a2n xn = b2

…am 1 x1 + am 2 x2 + …+ am n xn = bm

x1, x2,…, xm,…, xn 0 (m n ) (3.3)

Maximizar Z= c1 x1 + c2 x2 + …+ cn xn (3.1)

sujeito a

a11 x1 + a12 x2 + …+ a1n xn = b1 (3.2)a21 x1 + a22 x2 + …+ a2n xn = b2

…am 1 x1 + am 2 x2 + …+ am n xn = bm

x1, x2,…, xm,…, xn 0 (m n ) (3.3)

c(A) - característica de uma matriz Amxn que corresponde ao

número máximo de colunas de A linearmente independentes

Este sistema é constituído por m equações e n incógnitas, suponha que a característica da matriz do sistema é igual a m, c(A)=m, e que m n .

Este sistema tem uma infinidade de soluções, tratando-se portanto dum sistema possível e indeterminado de grau n-m. Isto significa que podemos exprimir m variáveis em função das n- m restantes.

Para determinar uma solução do problema de P.L. é preciso resolver o sistema de equações lineares

Base do Sistema.Variáveis básicas e não básicas

Se uma submatriz Bmxm da matriz A do sistema de equações correspondente às restrições é não singular, isto é, o determinante de Bmxm é não nulo, então Bmxm designa-se por base.

As m variáveis x1 , x2 ,…, xm , correspondentes às colunas de Bmxm ,designam-se por variáveis básicas e as restantes n-m variáveis xm+1, xm+2 ,…, xn designam-se por variáveis não básicas.

Solução Básica e Solução Básica Admissível

Sem perda de generalidade, suponha que a base B é composta pelas m últimas colunas, isto é, B= { P1 , P2 ,..., Pm }

como o determinante de B é não nulo (pela definição de base), o sistema de equações BXB =b tem solução

única

Obtém-se uma solução básica para o sistema (3.2) atribuindo o valor 0 às n-m variáveis não básicas xm+1 ,

xm+2 ,…, xn, e determinando uma solução para as restantes m variáveis básicas x1 , x2 ,…, xm , isto é, X = (0, ..., 0, x1 , x2 ,… , xm), onde XB =(x1 , x2 ,…, xm) é a única solução do sistema B XB =b.

Se todas as variáveis básicas da solução básicaX= (0, ..., 0, x1 , x2 ,… , xm) são não negativas então X é uma solução básica admissível (SBA).

Solução Básica DegeneradaSuponha-se X = (0, ..., 0, x1 , x2 , ..., xm) uma solução básica para o sistema (3.2) com as correspondentes variáveis básicas x1 , x2 ,…, xm.

Se alguma variável básica x1 , x2 ,…, xm for igual a zero, a solução básica designa-se por solução básica degenerada.

Se todas as variáveis básicas são não nulas a solução básica designa-se por solução básica não degenerada.

Soluções Básicas Adjacentes

Duas soluções básicas que apenas diferem numa variável básica designam-se por soluções básicas adjacentes.

Uma SBA é óptima quando nenhuma das SBA adjacentes é “melhor”, isto é, nenhuma melhora o valor da função objectivo.

Algoritmo

O que é um algoritmo?

Um algoritmo é um processo que repete (itera) sucessivas vezes um procedimento sistemático até obter um resultado. Além disso, também inclui um procedimento

para iniciar e um critério para terminar.

INÍCIOINÍCIOForma Padrão

Identificar uma SBA inicial.Construir o quadro Simplex correspondente

Análise dos simétricos dos coeficientes da f. o.

A solução é óptima ?

FIMFIMSolução óptima !!!SimSim

critério de optimalidadeNãoNão

Identificar a variável não básica que entra

critério de entrada

Óptimo nãofinito?

FIMFIMO problema não tem

óptimo finitoSimSimcritério de óptimo não finito

NãoNãoIdentificar a variável básica que sai

critério de saída

Actualizar o quadro SimplexCalcular nova SBA

Exemplo Redução à Forma Padrão

Restrição de desigualdade

Variável de folga

Restrição de igualdade

x1 4 xx33 x1 + x3 = 41ª1ª

2 x2 122ª2ª xx44 2 x2 + x4 = 12

3ª3ª 3 x1 + 2 x2 18 xx553 x1 + 2 x2 + x5 = 18

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

x1 x2 x3 x4 x5 b

x3 1 0 1 0 0 4

x4 0 2* 0 1 0 12

x5 3 2 0 0 1 18

Z -3 -5 0 0 0 0

Algoritmo Primal Simplex.Exemplo: 1º quadro

Simétricos dos coeficientes da f.o.

valores das

variáveis básicas

os simétricos dos coeficientes

das variáveis básicas são sempre nulos

Valor da f.o.

Primeira solução básica admissível: (x1, x2, x3, x4, x5) = (0, 0, 4, 12, 8); x1, x2 são variáveis não básicas e x3, x4, x5 são as variáveis básicas; Esta solução não é óptima; A variável a entrar na base é x2 porque, entre as variáveis não básicas

com custo reduzido negativo, é a que tem menor valor; A variável de saída é x4, porque o min 12/2, 18/2 corresponde à linha

definida por esta variável básica; O pivot neste caso é 2 (assinalado com um asterisco); A actualização do quadro simplex é feita utilizando as seguintes

operações elementares:

L1 L1

L2 1/2L2

L3 L3 – L2

L4 L4 + 5/2L2

x1 x2 x3 x4 x5 b

x3 1 0 1 0 0 4

x2 0 1 0 1/2 0 6

x5 3* 0 0 -1 1 6

Z -3 0 0 5/2 0 30


Nova solução básica admissível: (x1, x2, x3, x4, x5) = (0, 6, 4, 0, 6); Esta solução ainda não é óptima; Para esta solução a função objectivo é 30; A variável a entrar na nova base é x1 porque, entre as duas variáveis não

básicas, é a única que tem um custo reduzido negativo; A variável de saída é x5, porque o min {4/1,6/3} corresponde à linha

definida por x5; O novo pivot é 3 (assinalado com um asterisco); A nova actualização do quadro simplex é feita utilizando as seguintes

operações elementares:

L1 L1 – 1/3L3

L2 L2

L3 1/3L3

L4 L4 + L3

x1 x2 x3 x4 x5 b

x3 0 0 1 1/3 -1/3 2

x2 0 1 0 1/2 0 6

x1 1 0 0 -1/3 1/3 2

Z 0 0 0 3/2 1 36


A nova solução básica admissível é (x1, x2, x3, x4, x5) =

(2, 6, 2, 0, 0) ; uma vez que neste último quadro não

existem custos reduzidos negativos, esta solução é

óptima.

O valor máximo da função objectivo é 36.

Conclusão

O Método Simplex :

•Permite passar de uma solução básica admissível para uma outra solução básica admissível que corresponde a um melhor valor da função objectivo.

•Dispondo de um critério que permita saber quando se alcançou a solução óptima sem necessidade de experimentar todas as soluções básicas.

Trabalho realizado no âmbito da cadeira de Fundamentos e Ensino da Álgebra por:

Carla Sofia Monteiro Freitas Henriques

Dina Jacinta Nunes Lopes

Márcio Nuno Loureiro Jesus

Sónia Patrícia Gomes dos Santos

Documents

Origem da Investigação Operacional Para quê a Investigação Operacional (I.O.)? A Investigação Operacional surgiu para resolver, duma forma mais eficiente,