FATEC-SB- FACULDADE DE TECNOLOGIA DE SO BERNARDO DO CAMPO
PESQUISA OPERACIONAL
PROFa LGIA CONCEIO PEREIRA
CURSO SUPERIOR DE TECNOLOGIA EM INFORMTICA PARA GESTO DE
NEGCIOS1
A Pesquisa Operacional (PO) uma cincia que objetiva fornecer
ferramentas quantitativas ao processo de tomada de decises.
constituda por um conjunto de disciplinas isoladas, tais como
Programao Linear, Teoria das Filas, Simulao, Programao Dinmica,
Teoria dos Jogos, etc. O termo Pesquisa Operacional (em ingls:
Operations Research) foi empregado pela primeira vez em 1939 como
uma tentativa de englobar, sob uma nica denominao, todas as tcnicas
existentes ou que viriam a ser desenvolvidas e que tinham o mesmo
objetivo citado. De uma maneira geral, todas as disciplinas que
constituem a PO se apiam em quatro cincias fundamentais: Economia,
Matemtica, Estatstica e Informtica. As reas de aplicao abrangem
fbricas,escritrios, hospitais, fazendas, estradas, etc. Dentre as
diversas disciplinas que compe a PO, o INDG atua em Programao
Linear e Simulao. Denominamos Management Sciences (MS) a rea de
estudos que utiliza computadores, estatstica e matemtica para
resolver problemas de negcios. Esta rea considerada uma sub-rea da
Pesquisa Operacional (PO), por tratar-se de modelagem atemtica
aplicada rea de negcios. H poucos anos nos EUA, as duas sociedades
que estudavam separadamente MS e PO se fundiram em uma sociedade
denominada INFORMS. No Brasil a contraparte desta instituio a
SOBRAPO-Sociedade Brasileira de Pesquisa Operacional
(www.sobrapo.org.br) - que mantm anualmente simpsios cientficos.
Entre os tipos de problemas em que MS-PO pode ser utilizada para
ajudar no processo de deciso, encontra-se: Problemas de otimizao de
recursos. Problemas de Localizao Problemas de Roteirizao Problemas
de Carteiras de Investimento Problemas de Alocao de Pessoas
Problemas de Previso e Planejamento
Com o aumento da velocidade de processamento e quantidade de
memria dos computadores atuais, houve um grande progresso na
Pesquisa Operacional. Este progresso devido tambm larga utilizao de
microcomputadores, que se tornaram unidades isoladas dentro de
empresas. Isso faz com que os modelos desenvolvidos pelos
profissionais de Pesquisa Operacional sejam mais rpidos e versteis,
alm de serem tambm interativos, possibilitando a participao do
usurio ao longo do processo de clculo. A definio de Pesquisa
Operacional nos leva a trs objetivos inter-relacionados: a-
converter dados em informaes significativas- transformar dados
brutos (nmeros e fatos) em dados, atravs de seu armazenamento de
forma organizada., para que sejam transformados em Informaes
Gerenciais que podem ser utilizadas no processo de tomada de
deciso.
2
b- Apoiar o Processo de Tomada de deciso de formas transferveis
e independentes, dar o suporte s decises para que estas sejam
independentes do decisor e assegurar que o processo de deciso seja
claro e transparente. c- Criar sistemas computacionais teis para os
usurios no-tcnicos, facilitar , atravs de4 sistemas de fcil
utilizao, os processos de tomada de deciso operacional, gerencial e
estratgico. Modelagem Um modelo uma representao de um sistema real,
que pode j existir ou ser um projeto aguardando execuo. No primeiro
caso, o modelo pretende reproduzir o funcionamento do sistema, de
modo a aumentar sua produtividade. No segundo caso, o modelo
utilizado para definir a estrutura ideal do sistema. A
confiabilidade da soluo obtida atravs do modelo depende da validao
do modelo na representao do sistema real. A validao do modelo a
confirmao de que ele realmente representa o sistema real. A
diferena entre a soluo real e a soluo proposta pelo modelo depende
diretamente da preciso do modelo em descrever o comportamento
original do sistema. Um problema simples pode ser representado por
modelos tambm simples e de fcil soluo. J problemas mais complexos
requerem modelos mais elaborados, cuja soluo pode vir a ser
bastante complicada. A Tomada de Deciso Podemos entender a tomada
de deciso como o processo de identificar um problema ou uma
oportunidade e selecionar uma linha de ao para resolv-lo. Um
problema ocorre quando o estado atual de uma situao diferente do
estado desejado. Vrios fatores afetam a tomada de deciso e entre
eles podemos destacar; Tempo disponvel para a Tomada de Deciso A
importncia da deciso O Ambiente Certeza/incerteza e risco Agentes
decisores Conflito de interesse. Os modelos podem ser utilizados
como ferramentas consistentes para a avaliao e a divulga de
diferentes polticas empresariais. Estrutura de Modelos Matemticos
Em um modelo matemtico, so includos trs conjuntos principais de
elementos: (1) variveis de deciso e parmetros: variveis de deciso
so as incgnitas a serem determinadas pela soluo do modelo.
Parmetros so valores fixos no problema; (2) restries: de modo a
levar em conta as limitaes fsicas do sistema, o modelo deve incluir
restries que limitam as variveis de deciso a seus valores possveis
(ou viveis); (3) funo objetivo: uma funo matemtica que define a
qualidade da soluo em funo das variveis de deciso. Para melhor
ilustrar ao conjuntos acima, considere o seguinte exemplo: "Uma
empresa de comida canina produz dois tipos de raes: Tobi e Rex.
Para a manufatura dasraes so utilizados cereais e carne. Sabe-se
que:
3
a rao Tobi utiliza 5 kg de cereais e 1 kg de carne, e a rao Rex
utiliza 4 kg de carne e 2 kg de cereais; o pacote de rao Tobi custa
$ 20 e o pacote de rao Rex custa $ 30; o kg de carne custa $ 4 e o
kg de cereais custa $ 1; esto disponveis por ms 10 000 kg de carne
e 30 000 kg de cereais. Deseja-se saber qual a quantidade de cada
rao a produzir de modo a maximizar o lucro." Neste problema as
variveis de deciso so as quantidades de rao de cada tipo a serem
produzidas. Os parmetros fornecidos so os preos unitrios de compra
e venda, alm das quantidades de carne e cereais utilizadas em cada
tipo de rao. As restries so os limites de carne e cereais e a funo
objetivo uma funo matemtica que determine o lucro em funo das
variveis de deciso e que deve ser maximizada. Tcnicas Matemticas em
Pesquisa Operacional A formulao do modelo depende diretamente do
sistema a ser representado. A funo objetivo e as funes de restries
podem ser lineares ou no- lineares. As variveis de deciso podem ser
contnuas ou discretas (por exemplo, inteiras) e os parmetros podem
ser determinsticos ou probabilsticos. O resultado dessa diversidade
de representaes de sistemas o desenvolvimento de diversas tcnicas
de otimizao, de modo a resolver cada tipo de modelo existente.
Estas tcnicas incluem, principalmente: programao linear, programao
inteira, programao dinmica, programao estocstica e programao no-
linear. Programao linear utilizada para analisar modelos onde as
restries e a funo objetivo so lineares; programao inteira se aplica
a modelos que possuem variveis inteiras (ou discretas); programao
dinmica utilizada em modelos onde o problema completo pode ser
decomposto em subproblemas menores; programao estocstica aplicada a
uma classe especial de modelos onde os parmetros so descritos por
funes de probabilidade; finalmente, programao no-linear utilizada
em modelos contendo funes nolineares. Uma caracterstica presente em
quase todas as tcnicas de programao matemtica que a soluo tima do
problema no pode ser obtida em um nico passo, devendo ser obtida
iterativamente. escolhida uma soluo inicial (que geralmente no a
soluo tima). Um algoritmo especificado para determinar, a partir
desta, uma nova soluo, que geralmente superior anterior. Este passo
repetido at que a soluo tima seja alcanada (supondo que ela
existe). Fases do Estudo de Pesquisa Operacional Um estudo de
pesquisa operacional geralmente envolve as seguintes fases: (1)
definio do problema; (2) construo do modelo; (3) soluo do modelo;
(4) validao do modelo; (5) implementao da soluo. Apesar da seqncia
acima no ser rgida, ela indica as principais etapas a serem
vencidas. A seguir, apresentado um resumo da cada uma das fases.
4
Definio do problema A definio do problema baseia-se em trs
aspectos principais: descrio exata dos objetivos do estudo;
identificao das alternativas de deciso existentes; reconhecimento
das limitaes, restries e exigncias do sistema. A descrio dos
objetivos uma das atividades mais importantes em todo o processo do
estudo, pois a partir dela que o modelo concebido. Da mesma forma,
essencial que as alternativas de deciso e as limitaes existentes
sejam todas explicitadas, para que as solues obtidas ao final do
processo sejam vlidas e aceitveis. Construo do modelo A escolha
apropriada do modelo fundamental para a qualidade da soluo
fornecida. Se o modelo elaborado tem a forma de um modelo
conhecido, a soluo pode ser obtida atravs de mtodos matemticos
convencionais. Por outro lado, se as relaes matemticas so muito
complexas, talvez se faa necessria a utilizao de combinaes de
metodologias. Soluo do modelo O objetivo desta fase encontrar uma
soluo para o modelo proposto. Ao contrrio das outras fases, que no
possuem regras fixas, a soluo do modelo baseada geralmente em
tcnicas matemticas existentes. No caso de um modelo matemtico, a
soluo obtida pelo algoritmo mais adequado, em termos de rapidez de
processamento e preciso da resposta. Isto exige um conhecimento
profundo das principais tcnicas existentes. A soluo obtido, neste
caso, dita "tima". Validao do modelo Nessa altura do processo de
soluo do problema, necessrio verificar a validade do modelo. Um
modelo vlido se, levando-se em conta sua inexatido em representar o
sistema, ele for capaz de fornecer uma previso aceitvel do
comportamento do sistema. Um mtodo comum para testar a validade do
sistema analisar seu desempenho com dados passados do sistema e
verificar se ele consegue reproduzir o comportamento que o sistema
apresentou. importante observar que este processo de validao no se
aplica a sistemas inexistentes, ou seja, em projeto. Nesse caso, a
validao feita pela verificao da correspondncia entre os resultados
obtidos e algum comportamento esperado do novo sistema .MODELAGEM
MATEMTICA PROBLEMA DE PRODUOUma empresa produz trs tipos de portas
a partir de um determinado material. Sabendo que diariamente a
empresa dispe de 500 kg de material e 600 horas de trabalho,
determinar um plano ptimo de produo que corresponda ao maior lucro.
A tabela
5
seguinte indica a quantidade de material e horas de trabalho
necessrias para a produo de uma porta de cada tipo, assim como o
lucro unitrio de cada uma delas
RecursosQuantidade de material
Porta 18 kg 7 horas 50reais
Porta 24kg 6 horas 40reais
Porta 33 kg 8 horas 55 reais
Horas de Trabalho Lucro Unitrio
Exerccios Fazer a modelagem matemtica dos seguintes problemas:
1. Uma fabrica quer saber quantas canetas de cada tipo ( standard,
luxo e esferogrfica ) devero ser produzidas, para que o lucro seja
mximo, tendo as seguintes informaes: a) Departamento de Produo
Produo mximas mensais possveis para cada tipo ( se produzir um nico
tipo) Standard 15.000 Luxo 10.000 Esferogrfica 20.000 b)
Departamento de Vendas Mximas Vendas mensais possveis para cada
tipo Standard 12.000 Luxo 8.000 Esferogrfica 30.000 c) Departamento
Contbil Lucro unitrio para cada tipo) Standard Luxo
Esferogrfica
15.000 10.000 20.000
2. Uma pequena indstria usa 3 tipos de matrias primas, P,Q,R
para a fabricao de 2 produtos A e b. as matrias primas em
disponibilidade na fbrica so: 20 unidades de p 6
12 unidades de Q 16 unidades de R Por razes tecnolgicas, uma
unidade do produto A necessita respectivamente de 2,2,4 unidades de
matrias primas P, Q,R. Para o produto B esses coeficientes tcnicos
so 4,2 e 0, respectivamente. O fabricante, sabe que o lucro na
produo de A de $0,50 e de B $1,00. qual o lucro mximo e quais as
Quantidades a serem produzidas das mercadorias A e B para obter o
lucro mximo. 3. Suponha que se queira distribuir uma certa
quantidade de material e mo de obra disponveis na construo de armas
anti-areas de defesa: canhes, avies de caa e foguetes teleguiados.
As quantidades de material e mo de obra requerida por 1000 unidades
de cada um destes tipos de armas esto indicadas no quadro abaixo.Na
ltima coluna desse quadro, encontra-se as probabilidades de xito da
cada tipo: As quantidades disponveis de material e mo de obra so
iguais a 25 e 50 unidades respectivamente. ARMAS UNIDADES UNIDADES
DE PROBABILIDADE MATERIAL MO DE OBRA DE EXITO CANHES 3 1 40% CAAS 1
1 30% TELEGUIADOS 1 3 40% Quantas unidades se devem produzir de
cada arma, a fim de que a probabilidade de xito seja mxima? 4 Um
revendedor de chapas e perfis metlicos recebe da usina siderrgica
determinado tipo de chapa em rolos padronizados de 0,80 m e 1,50 m
de largura.Os clientes compram na largura que necessitam e o
revendedor corta as chapas conforme o pedido. Para a prxima semana,
recebeu trs pedidos com as seguintes especificaes:
5
PEDIDO 1 2 3
LARGURA (M) 0,40 0,60 0,70
COMPRIMENTO (M) 10 30 20
O problema do revendedor e programar o corte das chapas
originais de modo a atender aos trs pedidos, com o mnimo desperdcio
de aparas e sobras na largura das chapas. As dimenses do
comprimento no criam grandes inconvenientes, porque as chapas podem
ser emendadas para outras aplicaes. 6 O departamento de marketing
de uma empresa estuda a forma mais econmica de aumentar em 30% as
vendas de seus dois produtos P1 e P2. As alternativas so: a)
Investir em um programa institucional com outras empresas do mesmo
ramo. Esse programa requer um investimento mnimo de $ 3.000,00, e
deve 7
proporcionar um aumento de 3% nas vendas de cada produto, para
cada $ 1.000,00 investidos. b) Investir diretamente na divulgao dos
produtos. Cada $ 1.000,00 investidos em P1 retornam um aumento de
4% nas vendas, enquanto que P2 o retorno de 10%. A empresa dispe de
$10.000,00 para esse empreendimento. Quanto dever destinar a cada
atividade? Construa o modelo do sistema descrito. PROGRAMAO LINEAR
OU MODELOS DE OTIMIZAO LINEAR
um subitem de programao matemtica um dos elementos utilizados em
pesquisa operacional. um modelo de otimizao.
Objetivo: "Alocar recursos escassos (ou limitados) a atividades
em concorrncia (em competio)" . Dificuldades: "Modelar
corretamente". A arte de modelar adquirida com experincia e aptido
a parte mais difcil da anlise.
EXEMPLO INICIAL Uma empresa pode fabricar dois produtos (1 e 2).
Na fabricao do produto 1 a empresa gasta nove horas-homem e trs
horas-mquina (a tecnologia utilizada intensiva em mo-de-obra). Na
fabricao do produto 2 a empresa gasta uma hora-homem e uma
hora-mquina (a tecnologia intensiva em capital). Sendo x1 e x2 as
quantidades fabricadas dos produtos 1 e 2 e sabendo-se que a
empresa dispe de 18 horas-homem e12 horasmquina e ainda que os
lucros dos produtos so $4 e $1 respectivamente, quanto deve a
empresa fabricar de cada produto para obter o maior lucro possvel
(ou o lucro mximo ou ainda maximizar o lucro) ? TRANSFORMANDO OS
DADOS EM EXPRESSES MATEMTICAS A FUNO LUCRO Admitindo que no h
economia de escala mas quantidades fabricadas quanto ao lucro, a
funo lucro uma funo linear de x1 e x2 ou seja:
L = 4 x1 + x 28
esse lucro deve ser maximizado por uma escolha de x1 e x2 Max
x1, x2 L = 4 x1 + x2
Se o problema parasse aqui o lucro seria ilimitado. Porm,
existem recursos limitados. As Restries: O que limita as
quantidades fabricadas aqui so as horas-homem e horas-mquina
disponveis. Assim, as quantidades fabricadas e as horas utilizadas
de cada recursos no podem ultrapassar as quantidades de recursos
disponveis ou seja: H-H H-M 9x1 + x2 18 e 3 x1 + x2 12 Assim, o
lucro s poder crescer at esses limites. O PROBLEMA O problema ento:
Max L = 4 x1 + x2 x1, x2 sujeito a horas-homem 9x1 + x2 18
horas-mquina 3 x1 + x2 12 x1 0 e x2 0 Como o problema de Segunda
dimenso e as funes e inequaes so lineares, podemos obter uma soluo
fcil graficamente.
SOLUO GRFICA Primeiro precisamos saber, dado as restries, quais
as possveis combinaes dos produtos que se pode fabricar. Isso ,
precisamos verificar qual ou quais as reas que satisfazem as
restries, pois a empresa s pode dispor dos recursos "disponveis".
H-H 9x1 + x2 18
9
20 18 16 14 12 10 8 6 4 2 0 -1 -0.5 0 0.5 1 1.5 2 2.5 3 3.5
4
H-M 3x1 + x2 1220 18 16 14 12 10 8 6 4 2 0 -1 0 1 2 3 4 5
Como a empresa no pode violar nenhuma das restries precisamos
saber a rea onde as duas restries so vlidas, isso , a interseo das
duas regies de restrio, chamada de conjunto de possibilidades ou
conjunto vivel. Conjunto Vivel
10
20 18 16 14 12 10 8 6 4 2 0 -1 0 1 2 3 4 5
Resta agora maximizar o Lucro. L = 4 x1 + x2 Ora, o lucro uma
constante para cada uma das combinaes da x1 e x2. Assim, lucros
diferentes geram retas paralelas onde o lucro constante em cada
reta ou seja, as retas so iso-lucros.20 18 16 14 12 10 8 6 4 2 0 -1
0 1 2 3 4 5
Ento s traar iso-lucros no grfico do conjunto vivel e obter a
iso-lucro de maior lucro que seja possvel de se fabricar das
restries. Assim,
11
20 18 16 14 12 10 8 6 4 2 0 -1 0 1 2 3
L=13 4
5
Logo, o lucro mximo 13 e deve-se fabricar x1 = 1 e x2 = 9 para
obt-lo. Esses valores so fixados diretamente do grfico. Veja o que
acontece com as restries nesses valores, no h sobras. Como
poderamos conseguir essa soluo analiticamente?
O MTODO SIMPLEX
O mtodo simplex um algoritmo criado para se obter a soluo
algebricamente. Um algoritmo um conjunto de regras que devem ser
seguidas passo a passo para se obter, no final, o resultado
desejado. Nessa parte do curso daremos uma pequena noo do mtodo
simplex e sua soluo, depois formalizaremos os conceitos envolvidos
e generalizaremos para n-variveis e m-restries. A idia a seguinte:
Dado o problema na forma matemtica
Max Forma Padro x1 x2 s. a
L = 4 x1 + x2
9x1 + x2 18 3 x1 + x2 12
Precisamos arranj-lo de tal forma que possamos resolv-lo. Bem,
se as desigualdades fossem igualdades, as restries seriam um
conjunto de equaes lineares e essa ns sabemos resolver.
12
Consegue-se isso acrescentando a cada restrio uma varivel a
mais, essas novas variveis so chamadas de variveis de folga, para
restries do tipo . (Existem tambm as chamadas variveis de excesso,
para restries do tipo , mais isso outra histria). Assim podemos
escrever : (1) 9x1 + x2 + x3 = 18 pois, caso 9x1 + x2 no seja igual
a 18, x3 est l para garantir a igualdade. (2) 3x1 + x2 + x4 = 12
pois, caso 3x1 + x2 no seja igual a 12, x4 est l para garantir a
igualdade. Essas novas variveis, tambm devem ser maiores ou igual a
zero para garantir a exigncia das restries. OBS: Caso a restrio
fosse por exemplo 9x1 + x2 18 a introduo seria 9x1 + x2 -x3 = 18,
com x3 0. Ou multiplicaria-se a restrio por menos 1 transformando-a
numa restrio de desigualdade . S nos resta o lucro. O lucro uma
equao e no uma inequao, logo no precisamos introduzir variveis. O
sistema linear fica assim: (l0) (l1) (l2) L - 4x1 - x2 9x1 + x2 +
x3 3x1 + x2 = 0 = 18
+ x4 = 12
Feito isso podemos proceder com o algoritmo simplex. As etapas
so: 1. Ache uma soluo vivel para o sistema linear. (A soluo vivel
mais fcil no caso x1= 0, x2= 0 , x3 = 18, x4 = 12; chamada de soluo
trivial). Definir as variveis usadas na soluo como VB e as no
usadas como VNB. VB = Varivel Bsica e VNB = Variveis no Bsicas. 2.
Identifique a varivel que tem o maior impacto na funo objetivo.
Isso , a que tem o coeficiente mais negativo (devido nova arrumao
feita na funo objetivo) na equao correspondente a funo objetiva.
(No exemplo x1, com o coeficiente - 4 ) 3. Aumentar o valor da
varivel (de maior impacto) identificada no item 2 em todas as
restries at que esse aumento seja limitado por algum recurso. ( No
exemplo podemos aumentar x1 at 2 em l1 e at 4 em l2. Assim, x1 deve
ser igual a 2 pois um valor maior do que 2 viola l2). 4.
Identificar em que linha esse valor limite ocorre. (No caso em
l1)
13
5. Identificar a varivel bsica com a qual a varivel identificada
no item 2 pode trocar quantidades. ( No exemplo x3 ) 6. Fazer a
varivel bsica igual a zero. 7. Definir a varivel identificada no
item 2 como varivel bsica entrando (VBE) e definir a varivel bsica
no item 5 como varivel bsica saindo (VBS). ( x1 e VBE e x3 e VBS )
8. Fazer o coeficiente de VBE igual a 1 na linha da VBS.(No exemplo
9x1 + x2 + x3 =18 torna-se: x1 +1/9x2 + 1/9x3 = 2. 9. Zerar os
coeficientes de VBE nas demais equaes do sistema atravs de operaes
elementares e apresentar o novo sistema. 10. Redefinir como varivel
bsica todas as variveis bsicas anteriores menos a VBS mais a VBE e
as no-bsicas como as VNB Anteriores mais a VBS menos a VBE e
identificar o lucro e os valores das variveis ( x1 = 2 ; x4 = 6 ;
x2 = 0 ; x3=0 ; L=8). 11. Existe algum coeficiente negativo na
equao da funo objetivo(l0) ? Se sim, v para o passo 2, se no, pare,
essa a soluo vivel tima.
Dado o algoritmo vamos aplic-lo ao exemplo. Passo 1:
(l0) (l1) (l2)
L - 4x1 - x2 9x1 + x2 + x3 3x1 + x2
= 0 = 18
+ x4 = 12
A soluo vivel trivial (mais fcil ) : x1= x2 = 0 ; x3 = 18 ; x4 =
12; L = 0. As variveis x1 e x2 no bsicas e as variveis x3 e x4 so
bsicas. Passo 2: x1 com o coeficiente -4. Passo 3: x1 pode ir at 2.
Passo 4: ocorre em l1. Passo 5: x3. Passo 6: x3 = 0. Passo 7: x1
=> VBE x3 => VBS Passo 8: (l0) (l'1) L - 4x1 - x2 x1 + 1/9x2
+ 1/9x3 = 0 = 2 14
(l2)
3x1 +
x2
+ x4
= 12
Passo 9: Multiplicando l'1 por 4 e somando a l0 obtemos l'0
Multiplicando l'1 por -3 e somando a l2 obtemos l'2 (l'0) (l'1)
(l'2) L -5/9x2 + 4/9x3 x1 + 1/9x2 + 1/9x3 2/3x2 - 1/3x3 + x4 = 8 =
2 = 6
Passo 10: x1 e x4 so bsicas x2 e x3 so no bsicas Passo 11:
Existe Passo 2: x2 nica. Passo 3: em l'1 x2 pode ir at 18 Em l'2 x2
pode ir at 9 ; x2 = 9 Passo 4: ocorre em l'2. Passo 5: x4. Passo 6:
x4 = 0. Passo 7: x2 => VBE x4 => VBS Passo 8: (l'0) (l'1)
(l2) L - 5/9x2 +4/9x3 x1 + 1/9x2 + 1/9x3 x2 - 1/2x3 + 3/2x4 = 8 = 2
= 9
Passo 9: -1/9l''2 + l'1 = l''1 -1/5l''2 + l'0 = l''0 L + 3/18x3
+ 15/18x4 = 13 15
x1 x2
+ 3/18x3 - 1/3 x3
- 1/6x4 = 1 + 3/2x4 = 9
Passo 10: x1 e x2 so bsicas x3 e x4 so no bsicas Passo 11: No. A
soluo tima . L = 13 ; x1 = 1 ; x2 = 9 ; x3 = x4 = 0 QUADRO FINAL DA
SOLUO
L R1 R2
x1 0 1 0
x2 0 0 1
x3 1/6 1/6 -1/2
x4 5/6 -1/6 3/2
bi 13 1 9
Existem 3 Teoremas fundamentais que tornam o mtodo simplex
vlido. Esses teoremas sero apresentados sem demonstrao. Para
detalhes ver PUCINNI, 1942 Introduo Programao Linear. TEOREMA I: "O
conjunto de todas as solues compatveis do modelo de programao
linear um conjunto convexo C." TEOREMA II: "Toda soluo compatvel
bsica do sistema Ax = b um ponto extremo do conjunto das solues
compatveis, isto , do conjunto convexo C do teorema I .
16
TEOREMA III: a) "Se a funo objetiva possui um mximo (mnimo)
finito, ento pelo menos uma soluo tima um ponto extremo do conjunto
convexo C do teorema I" b) "Se a funo objetiva assume o mximo
(mnimo) em mais de um ponto extremo, ento ela forma o mesmo valor
para qualquer combinao convexa desses pontos extremos."
LIMITAES DA PROGRAMAO LINEAR:
1) Coeficientes Constantes Quando o grau de incerteza dos
parmetros muito grande necessrio trat-los como variveis aleatrias.
a ij, bi e cj so consideradas como constantes conhecidas. Na
realidade podem ser variveis. Incerteza envolvidas ou variveis
aleatrias. Os modelos de Programao Linear usualmente so formulados
no sentido de selecionar algum curso de ao futura . Por isso os
parmetros usados seriam baseados em numa predio de condies futuras,
os quais introduzem inevitavelmente algum grau de incerteza. 2)
Divisibilidade Valores fracionrios as vezes no fazem sentido.
Assim, quando no for possvel estabelecer essa divisibilidade
parte-se para programao inteira. 3) Proporcionalidade Assumi-se que
o lucro proporcional a x, sendo c; o coeficiente de
proporcionalidade. Assim, no h economia de escala. Para vencer isso
considera-se intervalos de produo onde no existem tais economias de
escala. Proporcionalidade uma suposio sobre atividades individuais
consideradas independentes umas das outras. 4) Aditividade
Considera as atividades do modelo como entidades totalmente
independentes, no havendo interdependncia entre elas. o caso da
manteiga e margarina. A proporcionalidade e a Aditividade garantem
a linearidade da funo-objetiva e das restries. DUALIDADE: "A cada
modelo de programao linear, contendo coeficiente aij , bi e cj
corresponde um outro modelo, denominado Dual, formado por esses
mesmos coeficientes, porm dispostos de maneira diferente."
(PUCCINI, 1942) 17
Na forma padro um modelo de P.L escrito da seguinte forma:
Max s. a
Z = c1 x1 + c2 x2 + .................+ cn xm (y1) a11x1 + a12x2
+ ........ + a1nxm b1 (y2) a21x1 + a22x2 + ........ + a2nxm b2 . .
. . . . . . . . (ym) am1x1 + am2x2 + ........ + amnxm bm xj 0 ( j =
1,....., n )
Se for associado a cada restrio uma varivel yi, o problema dual
pode ser escrito como: Min s. a D = b1 y1 + b2 y2 +
...............+ bm ym (y1) a11y1 + a21y2 + ........ + am1ym c1
(y2) a12y1 + a22y2 + ........ + am2ym c2 . . . . . . . . . . (ym)
a1ny1 + a2ny2 + ........ + amnym cn yi 0 ( i = 1,....., n )
Exemplo: 1) PRIMAL Max L = 4 x1 + x2 s. a 9x1 + x2 18 y1 3x1 + x2
12 y2 x1 e x2 0 DUAL Min s. a D = 18y1 + 12y2 9y1 + 3y2 4 x1 y1 +
y2 1 x2 y1 e y2 0
2) PRIMAL
Max P = 5 x1 + 2x2 ( PUCCINI, pag.136) s. a x1 3 y1 x2 4 y2 x1 +
2x2 9 y3 Min s. a D = 3y1 + 4y2 + 9y3 y1 + y3 5 x1 y2 + 2y3 2
x2
DUAL
18
Com a dualidade surgem vrios novos conceitos e construtos na
programao linear. Resolver o Primal atravs do Mtodo Simplex faz com
que o dual seja resolvido automaticamente. O quadro final do Mtodo
Simplex traz a soluo dos dois problemas, o Primal e o Dual. No
exemplo visto anteriormente, tens-se, como ltimo quadro (ou ltimo
modelo equivalente) o seguinte:
L R1 R2
x1 0 1 0
x2 0 0 1
x3 1/6 1/6 -1/2
x4 5/6 -1/6 3/2
bi 13 1 9
Ou seja, L = 13 ; x1 = 1 e x2 = 9. Se resolvemos o Dual,
graficamente acharamos no nosso 1) exemplo:
Conjunto Vivel
Agora s necessrio trocar as curvas de nvel de D = 18y1 + 12y2 e
traar paralelas at se atingir o mnimo:
Conjunto Vivel
L=13 19
INTERPRETAO DO PROBLEMA DUAL
PRIMAL
Max z c j x js. a j1
m
a xDUAL
ij j
bi (i 1,...,m)
x 0 j
Min D b i yis. a
m
a
i 1
ij i
y c j (j 1,..., m)
yi 0 iSe xj a quantidade de um determinado produto j z o lucro
bi a quantidade de um determinado recurso i ento:
$ unidade do produto j unidade do recursoi a ij unidade do
produto j $ yi unidade do recursoi cj
20
logo yi um preo (no necessariamente de mercado) No ponto timo
yi* representa a taxa pela qual a funo lucro ser aumentada ou
diminuda, se a quantidade disponvel do recurso i (bi) for aumentada
ou diminuda dentro de um certo limite. O limite determinado pelos
valores de bi para os quais a base de soluo tima permanece a mesma.
Observe o ltimo quadro do exemplo dado:
L 0 0 1/6 5/6 | 13 1 0 1/6 -1/6 | 1 0 1 -1/2 3/2 | 9 Observe o
quadro inicial L -4 -1 0 9 1 1 3 1 0 0 | 0 0 | 18 1 | 12
Se bi = 18 for aumentado para 19 qual a nova soluo ? ( lembre-se
que as operaes so as mesmas pois a matriz tecnolgica no mudou). L
-4 -1 0 9 1 1 3 1 0 L 0 | 0 0 | 18 + 1 1 | 12 0 | 8 + 4/9 0 | 2 +
1/9 1 | 6 - 1/3 13 + 1/6 1 + 1/6 9 - 1/2
0 -5/9 4/9 1 1/9 1/9 0 2/3 -1/3 0 1 0
L
0 1/6 5/6 | 0 1/6 -1/6 | 1 -1/2 3/2 |
E se aumentssemos b2 de 12 para 13: L -4 -1 0 9 1 1 3 1 0 L 0 |
0 0 | 18 1 | 12 + 1 0 | 8 0 | 2 1 | 6 + 1 13 + 5/6 1 - 1/6 21
0 -5/9 4/9 1 1/9 1/9 0 2/3 -1/3 0 1
L
0 1/6 5/6 | 0 1/6 -1/6 |
0 1 -1/2 3/2 | 9 + 3/2 Dessa forma os limites que b1 e b2 podem
variar sem mudar a base so: b1 at 18 unidades a mais b2 at 6
unidades a mais O que acontece quando se ultrapassa esses limites?
A base muda, existir excessos. Como yi um preo e representa o
quanto se ganharia se existisse mais do recurso i ento yi um custo
de oportunidade por no se ter mais do recurso i. Na literatura yi
designado por vrios nomes os mais comuns so: Preo sombra ( shadon
price ) Valor implcito Preo interno ( internal price ) Efficiency
price Intrisic value Incremental value Pode-se usar agora os
conhecimentos econmicos para se interpretar os diversos resultados
matemticos que podem ocorrer na soluo de um problema de programao
linear. Por exemplo: Se um yi = 0 significa que o recurso i, se for
acrescido de uma unidade no afetar em nada o lucro, assim, seu preo
zero logo existe recursos i em excesso (matematicamente a varivel
de folga no nula ). Se um yi 0 significa que o recurso i tem um
certo valor para a empresa, a empresa pagaria at yi para ter mais
do recurso e incrementar seu lucro de yi. Como o preo positivo o
recurso escasso, no existe desperdcio, todo recurso est sendo
utilizado logo, matematicamente, a varivel de folga nula. Essas
interpretao so conseqncias do teorema de folga complementar. Existe
muito mais interligaes entre os problemas Primal e Dual que podem
ser vistas com mais detalhes em PUCCINI, 1972.
22
