CENTRO UNIVERSITÁRIO FUNDAÇÃO SANTO ANDRÉ
FACULDADE DE ENGENHARIA “ENGENHEIRO CELSO DANIEL”
RELATÓRIO DE ATIVIDADES
UMA APLICAÇÃO DE PROGRAMAÇÃO LINEAR EM UMA EMPRESA DE
SERVIÇOS
Aluna:
Fabiana Miki dos Santos
Orientadora:
Lílian Kátia de Oliveira
Janeiro de 2012
Sumário
1. Introdução ....................................................................................................... 1
2. Programação Linear ....................................................................................... 3
2.1. Resolução gráfica de um problema de PL (Lachtermacher, 2004) .......... 5
3. Exemplos de modelos de otimização linear (Arenales et al., 2007) ......... 14
3.1. Problema de mistura ................................................................................. 14
3.2. Problema de transporte ............................................................................. 17
3.3. Problema de meio ambiente ..................................................................... 18
4. Método simplex ............................................................................................. 20
4.1. Teoremas fundamentais do Método Simplex (Puccini, 1980) ................ 20
4.2. Solução Algébrica (Puccini, 1980) ...........................................................21
4.3. Solução em quadros .................................................................................. 25
4.4. Casos Especiais......................................................................................... 29
4.4.1. Problema de Minimização ...................................................................... 29
4.4.2. Empate na entrada para o critério da variável básica ......................... 29
4.4.3. Empate na saída para o critério da variável básica ............................. 29
4.4.4. Múltiplas soluções .................................................................................. 31
4.4.5. Solução ilimitada .................................................................................... 33
5. Utilizando o Solver do Excel (Lachtermacher, 2004) ................................. 34
6. Utilizando o Lindo (Hillier e Lieberman, 2006)............................................ 44
7. Descrição e formulação dos estudos de caso ........................................... 47
7.1. Estudo de caso I ........................................................................................ 47
7.1.1 Formulação do problema I ...................................................................... 49
7.1.2 Resolução do problema I utilizando o Lindo ......................................... 51
7.1.3 Conclusão da análise dos resultados I...................................................53
7.2. Estudo de caso II ....................................................................................... 54
7.2.1 Formulação do problema II ..................................................................... 54
7.2.2 Resolução do problema II utilizando o Lindo ........................................ 56
7.2.3 Conclusão da análise dos resultados II................................................. 57
8.Conclusão...................................................................................................... 57
Bibliografia ........................................................................................................ 59
1
1. Introdução
O estudo de Pesquisa Operacional surgiu com o advento da Revolução
Industrial, em função do crescimento acelerado no tamanho e na complexidade
das organizações. O aumento no número de trabalhos e na segmentação das
responsabilidades
gerenciais
na
organização
foi
significativo
(Hillier
e
Lieberman, 2006). Sendo constatada uma desestruturação no foco das
organizações, ou seja, havia setores nas empresas que tinham objetivos e
valores autônomos.
Percebendo a necessidade de solucionar os problemas de necessidade
de alocar recursos disponíveis para as diversas atividades de maneira mais
eficiente para organização como um todo, a pesquisa operacional ganhou
espaço no mercado. Mas foi a partir da Segunda Guerra Mundial, que o estudo
de PO ganhou uma importância significativa, pois havia a necessidade premente
de se alocar de forma eficiente os recursos escassos para as diversas
operações militares
e
atividades internas a cada
operação.
Após o
empreendimento bélico o interesse pela Pesquisa Operacional fora desse
ambiente, foi umas das ferramentas que fundamental para a expansão industrial
pós-guerra (Hillier e Lieberman, 2006).
A própria natureza do nome sugere que a pesquisa operacional envolve
pesquisa em operações, sejam elas na área governamental, industrial, etc. A
pesquisa operacional pode ser considerada como um conjunto de ferramentas
que auxiliam a conduzir e coordenar atividades dentro de uma organização; daí
ser também chamada de abordagem científica de apoio às decisões em um
sistema (Hillier e Lieberman, 2006).
Assim a pesquisa operacional é a aplicação de métodos científicos a problemas
complexos para auxiliar no processo de tomada de decisões tais como projetar,
planejar e operar em situações que requerem alocações eficientes de recursos
escassos (Arenales et al., 2007).
A PO foi desenvolvida rapidamente devido a dois fatores importantes. O
primeiro deles foi George Dantzig que em 1947 desenvolveu um progresso
substancial feito no início em termos de melhoria técnica: a criação do método
2
simplex para solucionar os problemas com a programação linear. O segundo
fator foi à revolução computacional, com a sua capacidade de realizarem
cálculos milhões de vezes mais rápido que o humano, deu um enorme impulso
para PO. Em 1980 estimulado com o desenvolvimento de computadores
pessoais munidos de excelentes pacotes de software de PO (Hillier e
Lieberman, 2006).
O estudo de PO busca soluções que são ótimas para a organização como
um todo em vez de soluções que beneficiam apenas um membro. Considerando
um problema optamos por escolher o melhor caminho, sendo que podem
aparecer varias soluções ótimas, optando pela melhor solução ótima
dependendo das necessidades administrativas (Hillier e Lieberman, 2006). .
Para que o estudo de PO seja devidamente aplicado à exigência de uma
equipe formada por indivíduos experientes, capacitados e treinados em áreas de
exatas como matemática, estatística, probabilidade, economia, informática, etc.,
para que possa dar a devida atenção para as ramificações do problema que
permeiam a organização (Hillier e Lieberman, 2006).
Podemos dizer que a pesquisa operacional tem tido um impacto crescente
nas áreas administrativas, recentemente (tanto o número quanto a variedade de
aplicações continuam a crescer).
Na indústria, as aplicações são cada vez mais notáveis: aviação e
mísseis,
automóveis,
comunicações,
computadores,
energia
elétrica
e
eletrônica, alimentos, metalurgia, mineração, petróleo, transportes, papéis,
móveis, metais, etc. Empresas prestadoras de serviço como agências
financeiras, bancos, postos de correios, e até mesmo um sistema de delivery
também utiliza as ferramentas de pesquisa operacional na gerência de seus
sistemas. Outro setor que tem se beneficiado muito com aplicações de técnicas
de pesquisa operacional é o setor público (ou governamental). Serviços como
coleta de lixo, bombeiros, polícia e saúde apresentam um aumento elevado no
nível de serviço oferecido à população devido a estudos aplicados em suas
organizações.
3
Dessa forma, podemos dizer que a Pesquisa Operacional causou um
impacto para a melhoria da eficiência, além da contribuição para o aumento da
produtividade pelas organizações no mundo todo.
2. Programação Linear
A programação linear (PL) envolve um bom entendimento de conceitos
matemáticos como matrizes e sistemas de equações lineares, sendo que os
problemas de PL se referem à distribuição eficiente de recursos limitados entre
atividades competitivas, atendendo um determinado objetivo, como exemplo,
maximizar os lucros e minimizar os custos, ou seja, são problemas de
programação matemática em que funções objetiva de restrição são lineares.
(Puccini, 1980; Lachtermacher, 2004).
Os modelos podem ser utilizados como ferramentas consistentes para a
avaliação e a divulgação de diferentes políticas empresariais. Existem
basicamente três tipos de modelos (os físicos, análogos e matemáticos ou
simbólicos). Tendo como exemplos de modelo físico os modelos de aeronaves
e casas utilizados por engenheiros, para os modelos análogos podem ser
representados por modelos de mapas rodoviários que simula as rodovias de
uma região através de traços sobre o papel e um marcador do tanque de
gasolina que representa através de uma escala circular, a quantidade de
gasolina existente no tanque (Puccini, 1980).
O modelo matemático é o mais utilizado na modelagem de situações
gerenciais, as grandezas são representadas por variáveis de decisão, logo os
modelos
matemáticos
necessitam
de
informações
quantificáveis
(Lachtermacher, 2004).
As restrições dos modelos são formadas por equações e inequações
lineares sendo estas definidas uma para cada recurso. Normalmente há a
satisfação da restrição do problema pelas inúmeras maneiras de distribuição
desses recursos entre as diversas atividades.Essas distribuições devem estar de
acordo com as equações de cada recurso para alcançar o objetivo, ou seja,
4
maximização do lucro ou a minimização do custo, sendo nomeada como solução
ótima.
Para o problema matemático em que as funções objetivo e as restrições
sejam lineares temos (Puccini, 1980; Lachtermacher, 2004):
Otimizar: Z= f  x1, x2,..., xn 
sujeito a:
g1  x1, x2 ,..., xn 
 b1
 
g2  x1, x2,..., xn   b2
 
 
gm  x1, x2,..., xn   bn
Ou para sua forma reduzida:
n
Otimizar: Z   ci x j
i 1
sujeito a:
n
c x
i 1
i
j
 bi  i  1,2,..., m 
x1, x2,...xn  0
onde:

f  x1, x2,..., xn   c1x1  c2x2  ...  cn xn ;

gi  x1, x2,..., xn   ai 1x1  ai 2x2  ...  ain xn , para i  1,...,m ;

Z é o valor da medida de desempenho;

n é o número de variáveis;

m é o número de restrições do problema;

i é o índice de uma determinada restrição;

j é o índice de uma determinada variável.
5
A terminologia solução no campo da programação linear significa que
qualquer especificação de valores para as variáveis de decisão
 x1, x2,...xn  ,
independe de ela ser desejável ou até mesmo ser uma opção admissível.
Diferentes tipos de soluções são então identificados usando-se um adjetivo
apropriado (Hillier e Lieberman, 2006):

Solução viável: é aquela para qual todas as restrições são
satisfeitas. É possível que não haja nenhuma solução viável no
problema.

Solução inviável: é aquela para qual pelo menos uma das
restrições é violada.

Região de soluções viáveis: é o conjunto de todas as soluções
viáveis.

Solução ótima: é a solução viável que tem o valor mais favorável
da função objetivo. Possível encontrar nenhuma solução ótima no
problema.

Soluções ótimas múltiplas: apresenta um numero infinito delas,
cada uma com o mesmo valor ótimo da função objetivo.

Valor mais favorável: é o maior valor se a função objetivo tiver de
ser maximizada, ao passo que será o menor valor caso ela deva
ser minimizada.
2.1. Resolução gráfica de um problema de PL (Lachtermacher, 2004)
Quando um problema de PL envolve apenas duas variáveis de decisão a
solução ótima de um problema de programação linear pode ser encontrada
graficamente.
Consideremos o seguinte problema de PL:
Max Z  5x1  3x2
Sujeito a :
6
x1
5
(a)
x2  4
(b)
2x1  3 x2  12
(c)
x1  0, x2  0
(d)
O primeiro passo para resolver o problema graficamente é estabelecer os
dois eixos que irão representar as quantidades de x1 e x2 . Em seguida deve-se
encontrar o conjunto de regiões viáveis do problema e, para isso, pode-se
utilizar a representação gráfica imposta por cada uma das restrições (ou seja,
determinar qual área do subespaço x1  x2 seria aceito por cada restrição).
Observando a Figura 1, nota-se o conjunto de soluções viáveis considerando as
restrições (a), (b) e (d) do problema acima.
Figura 1- Representação gráfica do conjunto de soluções viáveis para (a), (b) e (d).
A restrição (c) não tem representação imediata. Para representá-la
considere x1 como variável independente e x 2 como variável dependente. A
equação da reta é dada por x2  ax1  b onde a é o coeficiente angular da reta e
b é o coeficiente linear. Como a inequação é do tipo menor ou igual, todos os
pontos abaixo e acima da reta satisfazem a restrição. Assim graficamente será
representada pela Figura 2 e analiticamente temos:
7
2 x1  3 x2  12
3 x2  12  2 x1
12 2 x1

3
3
2x
x2  4  1
3
x2 
Figure 2- Representação gráfica do conjunto de soluções viáveis para (a),(b),(c),(d).
Para encontrar o valor máximo da função objetivo, deve-se encontrar o
maior valor possível de Z, a partir de um procedimento simples, porém não muito
funcional, onde atribuem valores a Z, tornando a função-objetivo em uma
equação de uma reta, simbolizada pelo tracejado na Figura 3. Por um processo
de tentativa e erro, podemos chegar ao valor ótimo verificando a existência de
pontos de reta que fazem parte do conjunto de soluções viáveis.
8
Figura 3 – Procedimento de procura da solução ótima.
Neste caso, o máximo valor de Z é igual a 27 cuja solução ótima é dada
por x1  5 e x2 
2
.
3
O mesmo procedimento pode ser utilizado para de obter uma solução
ótima para um processo de minimização.
Min Z = 5 x1  7 x2
Sujeito a:
4
(a)
x2  4
(b)
 x1  x2  4
(c)
2 x1  3 x2  12
(d)
2 x1  6 x2  18
(e)
x1  0, x2  0
( f)
x1
Encontrando o conjunto de soluções viáveis a partir do conjunto de
restrições temos a Figura 4 representando o conjunto de soluções viáveis.
9
Figura 4 – Procedimento de procura da solução ótima para o problema de minimizar.
Como no problema de maximização, é utilizado o mesmo procedimento
de tentativa e erro para determinar a solução mínima do problema de
minimização, obtendo o seguinte valor para Z=28 quando x1  0 e x2  4 .
Em alguns casos uma ou mais restrições podem não participar da
determinação do conjunto de soluções viáveis, sendo denominadas de
restrições redundantes, ou seja, a exclusão dessa restrição do conjunto de
restrições de um problema não afetara a solução final do problema. Toda vez
que existirem restrições redundantes em um problema de PL, existira outro
problema sem esta restrição com o mesmo conjunto de soluções viáveis e a
mesma solução ótima.
Adicionando uma nova restrição ao problema de minimização anterior
temos:
Min Z = 5 x1  7 x2
Sujeito a:
10
x1
4
(a)
x2  5
(b)
2 x1  3 x2  12
(c)
3 x1  4 x2  12
(d)
x1  0, x2  0
(e)
Determinando o conjunto de soluções viáveis do problema representado
na Figura 5, nota-se que a restrição x1  x2  2 não participa da determinação do
conjunto de soluções viáveis, já que, neste caso, a restrição 2 x1  5 x2  20 é
dominante sobre a mesma.
Figura 5 – Problema de minimização com uma restrição redundante.
Existe também a possibilidade de um problema de PL apresentar mais de
uma solução ótima, ou seja, um ou mais valores produzem igual valor máximo
na função objetivo. Considere o problema a seguir:
11
Min Z = 6 x1  10 x2
Sujeito a:
5
(a)
x2  6
(b)
x2  2
(c)
x1
 x1 
3 x1  5 x2  15
(d)
x1  0, x2  0
(e)
A partir dos procedimentos realizados até agora a representação das
soluções ótimas encontradas pode ser observada na Figura 6.
Figura 6 – Problema de minimização com múltiplas soluções ótimas.
Nota-se
que
o
coeficiente
angular da
reta
limite
da
restrição
3 x1  5 x2  15 é igual a -0,6, o que coincide com o coeficiente angular da reta
função-objetivo, sendo assim, neste caso todos os pontos que formarem este
lado do polígono serão as soluções ótimas do problema.
12
Entretanto para a resolução dos problemas de Programação Linear deve
se levar em consideração mais dois casos especiais. Um deles ocorre no
problema a seguir.
Max Z = 6x1  10x2
Sujeito a:
x2  6
(a)
3 x1  5 x2  15
(b)
 x1  x2  2
(c)
x1  0, x2  0
(d)
Usando o mesmo procedimento anterior, podemos encontrar o conjunto
de soluções viáveis representado na Figura 7.
Figura 7 – conjunto de região viável de um PL com solução ilimitada.
13
Como observado na Figura 7 o limite para o crescimento de x1 não
existe, concluindo que não existirá um limite de crescimento do valor de Z
(função-objetivo). Como não se consegue determinar a solução ótima deste
problema, considerando a presença de infinitas soluções, a solução existe,
porém, o problema é dito como ilimitado.
Por fim, o ultimo caso, que é o oposto do caso anterior. Neste caso, em
vez de existirem infinitas soluções, o conjunto de soluções é vazio, não existindo
soluções para o problema. Considere o seguinte problema:
Max Z = x1  x2
Sujeito a:
x1  x2  3
(a)
x1  x2  6
(b)
x1  0, x2  0
(c)
Analisando graficamente (Figura 8), observa-se que o conjunto de
soluções viáveis é vazio.
14
Figura 8 – Conjunto de soluções viáveis (vazio) de um PL inviável.
3. Exemplos de modelos de otimização linear (Arenales et al., 2007)
Nas mais variadas áreas encontraram diversos exemplos de problemas
que podem ser formulados como um problema de otimização linear.
3.1. Problema de mistura
Os problemas de mistura consistem na combinação de materiais obtidos
na natureza (ou restos de outro já combinado anteriormente) para a geração de
novos produtos com características convenientes.
Descrição de um possível problema de mistura de rações
As fábricas de rações produzem vários tipos de rações para determinados
animais, como bovinos, caninos (pequeno, médio e grande porte), felinos etc.
Essas rações são produzidas pela mistura de alimentos ou farinhas de restos de
alimentos como milhos, farelo de arroz, farinha de osso (entre outras dezenas de
ingrediente), cujo preço de mercado são conhecidos. A composição nutricional
desses ingredientes também é conhecida, isto é, quantidade de proteína,
manganês, ferro, cálcio, etc. (na prática o número de nutrientes é de cerca de
15
duas dezenas). A nutrição veterinária especifica as necessidades mínimas e
máximas desses nutrientes por quilo de ração para cada tipo de animal. Um
problema de otimização surge para determinar quais devem ser as quantidades
ideais de cada ingrediente por quilo de cada ração de modo que as
necessidades nutricionais impõem restrições, de modo que nem toda mistura de
ingredientes é aceitável, e o custo é o critério para se caracterizar a melhor
solução.
Os problemas de mistura surgem em vários outros processos industriais
como na produção de adubos, sucos concentrados de laranja, ligas metálicas,
composição de areias para filtro, etc.; geralmente são partes de um problema
mais geral de planejamento e controle da produção.
O processo de formulação matemática do problema de mistura consiste
na obtenção ou fabricação de um produto, ou no caso a mistura, combinando-se
alguns materiais disponíveis na natureza ou disponíveis no mercado. A mistura é
produzida a partir de ingredientes que possuem os componentes desejados no
novo produto (na ração, os componentes são proteínas, vitaminas, etc.) e que
devem satisfazer determinadas especificações (por exemplo, a pesquisa em
nutrição animal).
A composição de cada ingrediente é conhecida, isto é, as proporções dos
componentes de cada ingrediente são dadas, como também o seu custo
unitário. Deseja-se determinar as quantidades de cada ingrediente que deve ser
utilizado para obter uma mistura com a composição especificada e com o menor
custo possível.
Seja n é o número de ingredientes que são utilizados na produção da
mistura, m é o número de componentes relevantes para a mistura. Um dos
passos fundamentais para se escrever um modelo matemático é identificar as
incógnitas (variáveis do problema), ou seja, o que se deseja determinar. No caso
do problema da mistura, as variáveis são as quantidades dos ingredientes, logo
definimos a variável:
16
x j : a quantidade do ingrediente j que deve ser utilizado em uma unidade de mistura
j = 1,2,3,...,n.
As variáveis devem ser não negativas, caso haja um valor negativo par x j
não será possível, pois x j  0, j  1,2,3,..., n sendo a restrição do problema não
permite que isso ocorra. Para descrever as demais restrições sendo elas a
composição da mistura e seu custo, utiliza a seguinte notação:
aij é a fração do componente i no ingrediente j, i  1,...,m e j  1,...,n ;
bi é a fração do componente i na mistura, i  1,..., m ;
c j representa o custo de uma unidade do ingrediente j, j  1,..., n
A restrição aij será a quantidade do componente i em uma unidade da
mistura, então aij x j é a quantidade do componente i em x j unidades do
ingrediente j , então ai 1x1  ai 2 x2  ...  ain xn é a quantidade total do componente i
em uma unidade de mistura e quantidade i em uma unidade da mistura deve
ser bi :
ai 1x1  ai 2 x2  ...  ain xn  bi
i  1,2,3,...,m.
Nas m equações anteriores supõem-se que há alterações na composição
dos ingredientes quando estes se misturam, como por exemplo, a quantidade de
produção de sódio na mistura de um produto deve ser a soma das quantidades
de cálcio presentes nos ingredientes.
Como x j , j  1,...,n , são as quantidades dos ingredientes a serem
utilizadas em uma mistura, então a soma dessas quantidades deve resultar em
uma unidade da mistura, ou seja, x1  ...  xn  1.
O custo de uma unidade da mistura é a soma dos custos de todos os
ingredientes utilizados para sua obtenção, ou seja, c1x1  c2 x2  ...  cn xn .
Desejamos minimizar esse custo, portanto, o problema da mistura é
escrito como:
17
Minimizar f(x1,x 2 ,...,x n ) = c1x1  c2 x2  ...  cn xn
a11x1  a12 x2  ...  a1n xn  b1
a21x1  a22 x2  ...  a2 n xn  b1
...
am1x1  am 2 x2  ...  amn xn  b1
x1  x2  ...  xn  1
x1  0, x2  0,..., xn  0.
3.2. Problema de transporte
Os problemas de transporte referem-se ao transporte ou distribuição de
produtos dos centros de produção aos mercados consumidores. De maneira que
os produtos podem ser os mais variados possíveis, desde equipamentos,
maquinário, produção agrícola, energia elétrica até o petróleo. Esse problema
consiste em transportar o produto dos centros de produção aos mercados
consumidores de modo que o custo total de transporte seja o menos possível.
Admitindo geralmente que as quantidades produzidas ou ofertadas em casa
centro e as quantidades demandadas em cada mercado consumidor são
conhecidas. O transporte deve ser efetuado respeitando as limitações de oferta
e atendendo à demanda.
Para a formulação matemática do problema de transporte denominamos
centros de produção de origens e os mercados consumidores, de destinos.
Suponha que existam m origens e n destinos para um produto e que o custo de
transportar uma unidade desse produto da origem i para o destino j é c ij . Além
disso a oferta do produto na origem i é a i e a demanda do produto no destino j é
b j . As variáveis do problema são as quantidades transportadas das origens aos
destinos:
x ij quantidade transportada do produto da origem i para o destino j.
Essas quantidades não podem ser negativas, portanto, as restrições
xij  0, i  1,..., m e j  1,..., n, fazem parte do modelo matemático. Se x ij é a
18
quantidade transportada do produto da origem i para o destino j, então cij xij é o
custo incorrido para se realizar o transporte. O custo total de transporte é a
soma dos custos de transporte de todas as quantidades transportadas de todas
m
as origens i para todos os destinos j, ou seja,
n
 c x
i 1 j 1
ij
ij
. Esse custo deve ser
minimizado. Sabendo que o que é transportado de cada origem i a todos os
destinos j, j  1,2,..., n, não pode ultrapassar a quantidade disponível de produto
n
na origem i, ou seja
x
j 1
ij
 aij .
Desejamos também que as quantidades transportadas das diversas
origens ao destino j satisfaçam a demanda requerida neste destino, ou seja,
m
x
i 1
ij
 bij .
O modelo completo do modelo de transporte é definido por:
m
n
Minimizar f ( x11, x12 ,..., xmn )   cij xij
i 1 j 1
sujeito a:
n
x
j 1
ij
 aij
i  1,..., m
ij
 bij
j  1,..., n
m
x
i 1
xij  0
i  1,..., m e j  1,..., n.
3.3. Problema de meio ambiente
A preservação do meio ambiente tem sido de grande importância
atualmente. Uma maneira de preservar o meio ambiente é cuidar para que a
poluição dos recursos naturais esteja sobre controle.
Descrição de um possível problema de meio ambiente
19
Uma fábrica desvia parte da água de um rio para ser utilizada em seu
processo produtivo. Durante a produção, componentes químicos poluidores A e
B são adicionados à água desviada, que depois retorna ao rio, poluindo assim o
rio. Há níveis intoleráveis desses poluentes e o processo produtivo não acarreta
mudanças no fluxo de água. A adição dos poluentes também não afetas esse
volume.
As concentrações de poluentes consideradas aceitáveis pela Companhia
Estadual de Controle Ambiental são de a0 e b0 gramas por ML (milhões por
litros) de água por dia para os componentes A e B, respectivamente. A vazão do
rio é V ML por dia e a fábrica precisa de pelo menos U ML de água por dia para
sua produção. Existem 3 tipos de tratamento que a empresa pode utilizar para
diminuir a concentração dos poluentes resultantes de seu processo de
produção.
Esses tratamentos tem custos diferenciados ($/ML) e resultam, após o
tratamento, em níveis de concentração diferentes (gramas por ML) de cada um
dos poluentes.
O problema consiste em determinar a quantidade de agra a ser tratada
em cada tipo de tratamento, de modo que as exigências ambientais
regulamentadas em lei sejam atendidas e o custo total de tratamento seja
mínimo. Defina a variável de decisão xi , i  1, 2, 3, como a quantidade de água
(em ML) por dia a ser tratada pelo tratamento 1, 2 e 3, respectivamente. Pela
própria definição, essas variáveis devem ser não – negativas. Tendo como
objetivo a minimização do custo do tratamento da água, ou seja minimizar
( c1x1  c2 x2  c3 x3 ), que é a soma dos custos de cada um dos tratamentos a
serem efetuados. A quantidade diária de água (em ML) desviada para a
produção é simplesmente  x1  x2  x3  , e essa quantidade deve ser no mínimo
U, a quantidade mínima necessária para a fábrica funcionar em cada dia.
Portanto temos, a seguinte restrição:  x1  x2  x3   U
Dessa forma a, a quantidade desviada não pode superar a vazão do rio.
Assim, temos:  x1  x2  x3   V
20
Após o tratamento de x i milhões de litros de água, retornam ao rio ai xi e bi xi
gramas do poluente A e B, respectivamente, por dia. O total de poluentes (em
gramas) resultantes dos tratamentos é:
a1x1  a2 x2  a3 x3 do poluente A
b1x1  b2 x2  b3 x3 do poluente B.
A concentração de poluentes no rio deve ficar abaixo dos limites
considerados aceitáveis. Assim, devemos ter:
a1x1  a2 x2  a3 x3  / V  a0
b1x1  b2 x2  b3 x3  / V  b0
Portanto o modelo completo fica:
Miniminizar f ( x1, x2 , x3 )  c1x1  c2 x2  c3 x3
x1 
x2 
x3
U
x1 
x2 
x3
V
a1x1  a2 x2  a3 x3  / V  a0
b1x1  b2 x2  b3 x3  / V  b0
x1  0, x2  0, x3  0.
4. Método simplex
O método simplex desenvolvido por George Dantzig em 1947 provou ser
um método eficiente para solucionar problemas de programação linear
complexos, que são executados no computador usando pacotes de softwares
sofisticados ou, quando resolvido manualmente, é conveniente utilizar a forma
tabular do Método Simplex. O quadro Simplex é utilizado para registrar apenas
as informações essenciais no caso são os coeficientes das variáveis, as
constantes das restrições e as variáveis básicas e as não básicas. (Hillier e
Lieberman, 2006; Lachtermacher, 2004).
4.1. Teoremas fundamentais do Método Simplex (Puccini, 1980)
Teorema 1: O conjunto de todas as soluções compatíveis do modelo de
programação linear é um conjunto convexo.
21
Teorema 2: Toda função compatível básica do sistema Ax  b é um ponto
extremo do conjunto das soluções compatíveis, isto é, do conjunto convexo C do
Teorema 1.
Teorema 3:
1) Se a função objetiva possui um máximo (mínimo) finito, então pelo
menos uma solução ótima é um ponto extremo do conjunto convexo C do
Teorema 1.
2) Se a função objetiva assume o máximo (mínimo) em mais de um ponto
extremo, então ela toma o valor para qualquer combinação convexa desses
pontos extremos.
4.2. Solução Algébrica (Puccini, 1980)
Observando o modelo a seguir, lembrando que este foi resolvido
graficamente (Figura 3) como um problema de Maximizar
Max Z  5 x1  3 x2
Sujeito a :
x1
5
(a)
x2  4
(b)
2x1  3 x2  12
(c)
x1  0, x2  0
(d)
(1)
Introduzindo as variáveis de folga ( x3 , x4 e x5 ) ao sistema, temos:
22
Max Z  5 x1  3 x2
Sujeito a :
x1
 x3
5
 x4
x2
2 x1  3 x2
(2)
4
 x5  12
x1  0, x2  0, x3  0, x4  0, x5  0
Quando as restrições forem do tipo menor ou igual
 
e os bi não-
negativos, como no caso do sistema (1), sempre terá uma base formada pelas
variáveis de folga. Para o sistema de equações do sistema (2) apresenta as
seguintes características:
a. Todas as variáveis são não-negativas;
b. Todos bi são não-negativos;
c. Tem uma base obvia.
Quando o sistema de equações apresenta apenas as características a. e
b., diz que ela se encontra na forma padrão. Assim para que o sistema (2)
(forma canônica) apresente uma solução compatível básica, apresenta-se as
seguintes variáveis:
Variáveis não básicas: x1  x2  0 .
x3  5
Variáveis básicas: x4  4
x5  12
O sistema (2) correspondera a solução básica factível inicial. Tendo como
solução compatível óbvia para este sistema, o vértice (0,0) da Figura 2.
O próximo passo é verificar a solução ótima atual identificando o valor da
função objetivo (Z  5 x1  3 x2 ) que será zero, já que x1  x2  0 . Qualquer uma
das variáveis não-básicas que entrar na base assumira algum valor positivo, o
que fará com que o valor da função objetivo aumente. A solução ainda não foi
alcançada.
23
Para determinar a solução ótima é preciso saber qual variável não-básica
( x1 ou x2 ) deve entrar na base. O método simplex determina que a variável x1
deve entrar na base, pois é a que possui o maior coeficiente na função objetivo.
O critério de entrada na base visa crescer o valor da função objetivo o mais
rápido possível.
Sendo assim, para determinar a variável que devera sair da base, é
preciso colocar todas as variáveis básicas em função das variáveis não-básicas.
x3  5  x1
 x1  5
x 4  4  x2
(3)
x5  12  2 x1  3 x2
 x1  6
Observando que x1 influencia os valores das variáveis básicas x3 , x4 e x5 ,
conclui-se que em (3) quando a variável x1 entra na base assumindo algum
valor positivo, as variáveis x3 e x5 diminuirão de tamanho e a variável x 4 ficara
inalterada. Lembrando que a variável x 2 permanecerá fora da base com o valor
nulo. Desejando aumentar o tanto quanto possível o valor de x1 , respeitando as
restrições de não-negatividade das variáveis. Dessa forma a variável que mais
rapidamente se anular com o crescimento de x1 sairá da base, no caso a
variável x 3 , sai da base.
A nova base então será formada pelas variáveis x1, x 4 e x5 . É necessário
atualizar o sistema (2) para outra forma canônica, de maneira que a nova base
seja formada por essas variáveis. Basta multiplicar à primeira da equação por
(-2) e somar à terceira equação.
 x3
x1
x2
3 x2 -2x3
5
 x4
(4)
4
 x5  2
A solução básica compatível obvia de (4) é a seguinte:
Variáveis não básicas: x2  x3  0 .
24
x1  5
Variáveis básicas: x4  4
x5  2
Esta situação corresponde ao vértice (3,0) do trapézio, adjacente ao
vértice (0,0). É necessário agora testar se a solução é ótima. Não poderá ser
feito com a função objetivo Z  5 x1  3 x2 , pois:

Não se pode avaliar a influência da variável não-básica
x3
no
comportamento da função objetivo;

Não se pode afirmar que a função objetivo aumentará de valor com a
entrada de x 2 na base, pois a variável x1 poderá diminuir de valor,
mesmo permanecendo na base.
Deverá obter a função objetivo somente em termos das variáveis não-
básicas. Sabendo que (4) x1  5  x3 , então:
Z  5 x1  3 x2  5(3  x3 )  3 x2  15  3 x2  5 x3
Agora pode se afirmar que a presente solução ainda não é ótima, pois se
x 2 entrar na base, aumentara o valor da função objetivo. A variável x 3 não deve
entrar na base, pois caso ocorra o valor de Z será decrementado. Visando a
entrada de x 2 na base, deve-se colocar as variáveis básicas em função das
não-básicas. Para (4) obter:
x1  5  x1
x 4  4  x2
 x2  4
x5  2  3 x2 +2x 3
 x2 
(5)
2
3
A variável x 5 , sendo que se anula mais rapidamente com o crescimento
de x 2 , é que deve sair da base. Agora ao transformar (4) em uma nova forma
canônica de tal forma que a nova base formada pelas variáveis x1, x2 e x 4 . É
necessário dividir á terceira equação de (4) por 3 ,multiplicar á terceira equação
por -1/3 e somá-la à segunda equação de (4), repetir a primeira equação e
somar à terceira equação com a linha (0).
25
x1 
5
x3
2
1
10
x3  x 4  x5 
3
3
3
2
1
2
x 2  x3 
x5 
3
3
3
(6)
De (6) tem-se a seguinte solução compatível básica:
Variáveis não básicas: x3  x5  0 .
x1  5
2
3
10
x4 
3
Variáveis básicas: x2 
 2
Esta solução corresponde ao ponto extremo  5,  do conjunto de soluções
 3
compatíveis de (1). Deve-se colocar a função objetivo somente em termos das
variáveis não-básicas. De (6) se obtém x2 
2 2
1
 x3  x5 , o qual fornece:
3 3
3
1 
2 2
Z  15  3 x2  5 x3  15  3   x3  x5   5 x3
3 
3 3
Z  15  2  2 x3  x5  5 x3
Z  17  2 x3  x5
 2
O valor da função objetivo no vértice  5,  pode ser calculado de duas
 3
formas:
a) Z *  5 x1 * 3 x2 *  17
b) Z *  17  2 x3 *  x5 *
Agora pode-se afirmar que esta é a solução ótima, pois se x3 ou x5 entrarem
na base o valor da função objetivo será decrementado.
4.3. Solução em quadros
A solução em quadros visa simplificar os cálculos da maneira da solução
algébrica.
26
Utilizando novamente o sistema (1) como exemplo,temos:
Max Z  5 x1  3 x2
Sujeito a :
x1  5
(a)
x2  4
(b)
2 x1  3 x2  12
(c)
x1  0, x2  0
(d)
Reescrevendo o sistema da seguinte maneira :
Z  5 x1  3 x2
 x3
x1
x2
(7)
=0
5
 x4
2 x1  3 x2
4
 x5  12
O sistema (7) pode ser representado na forma de quadro abaixo:
Z
x1
x2
x3
x4
x5
b
Base
1
-5
-3
0
0
0
0
(0)
x3
0
1
0
1
0
0
5
(1)
x4
0
0
1
0
1
0
4
(2)
x5
0
2
3
0
0
1
12
(3)
Nota-se que os coeficientes da função objetiva na linha (0) sofrem
inversões de sinais.
Para os coeficientes nulos x3, x4 , x5 na linha (0), a função objetiva se
encontra somente em termos das variáveis não básicas x1 e x 2 . Afirmando que a
27
solução não é ótima, pois no caso existem coeficientes negativos, sendo assim,
a variável a entrar na base é x1 por ter o maior coeficiente negativo. E para
descobrir qual variável irá sair da base calculamos a divisão do valor da
constante (representado pela coluna b) pelo coeficiente correspondente.
Linha (1): x1 
5
1
Linha (3): x1 
12
2

Z
x1
x2
x3
x4
x5
b
Base
1
-5
-3
0
0
0
0
(0)
x3
0
1
0
1
0
0
5
(1) 
x4
0
0
1
0
1
0
4
(2)
x5
0
2
3
0
0
1
12
(3)
A divisão de menor valor representara a variável que sairá da base, neste
caso será a linha (1), ou seja, x 3 . Igualando x1 =0, e repetir as linhas (2) e (3);
multiplicar a linha (1) por (-2) e somar à linha (3); e multiplicar a linha (1) por 5 e
somar com a linha (0).
Veja o quadro a seguir:

Z
x1
x2
x3
x4
x5
b
Base
1
0
-3
5
0
0
25
(0)
x1
0
1
0
1
0
0
5
(1)
x4
0
0
1
0
1
0
4
(2)
x5
0
0
3
-2
0
1
2
(3) 
28
Restando ainda o coeficiente negativo em x 2 , afirmamos ainda que a
solução não é ótima. Logo será a variável que entrará na base.
Linha (2): x2 
4
1
Linha (3): x2 
2
3
Mas no caso a Linha (3) representada pela variável x5 sai da base.
Multiplicando a linha (3) por -1/3 e somá-la a linha (2); Dividir a linha (3) por 3; e
repetir a linha (1) e somar a linha (3) com a linha (0), temos:
Z
x1
x2
x3
x4
x5
b
Base
1
0
0
3
0
0
27
(0)
x1
0
1
0
1
0
0
5
(1)
x4
0
0
0
2
3
1
10
3
(2)
x2
0
0
1
2
3
(3)

2
3
0

1
3
1
3
Por fim obtemos a solução ótima, sendo que não existe nenhum
coeficiente negativo na linha (0). Comparando com gráfico da Figura 1 nota-se
que a solução ótima é 27
A solução ótima é dada por: x1  0, x2  0, x3  3, x4  0, x5  0 e Z  27 .
Com os novos conceitos que foram introduzidos pode-se reescrever os
cinco passos do método simplex, para o caso de maximização, da seguinte
maneira:
Método Simplex (maximização)
i.
Achar uma solução compatível básica óbvia (forma canônica)
ii.
Colocar a função objetivo somente em termos das variáveis nãobásicas. Se todos os coeficientes dessas variáveis forem negativos
ou nulos a presente solução é ótima. Caso contrario siga para o
passo iii
29
iii.
Colocar na base a variável não-básica que tiver maior coeficiente
positivo na função objetivo do passo ii
iv.
Tirar da base a variável não-básica que se anula mais
rapidamente, quando a variável que entrar for aumentada de valor.
v.
Achar uma outra forma canônica para o sistema de equações,
levando em consideração os passos iii e iv. Voltar par ii.
4.4. Casos Especiais
4.4.1. Problema de Minimização
Quando a função objetivo tiver de ser minimizada pode-se fazer duas
coisas:
a) Mudar o teste para saber se a solução é ótima e o critério de entrada na base.
b) Transformar um problema de minimização num problema de maximização.
Sabendo que a minimização de uma função Z( x) é matematicamente análoga à
maximização
da
negativa
desta
função
(Z( x)) ,
ou
seja,
Min Z( x)  Max(Z( x)) .
4.4.2. Empate na entrada para o critério da variável básica
Quando as divisões da constante pelo coeficiente são iguais deverá
escolher uma das duas, sabendo que a única implicação envolvida é que se
pode escolher um caminho mais longo ou mais curto para chegar à solução
ótima.
4.4.3. Empate na saída para o critério da variável básica
Quando houver empate na escolha da variável que sai da base, deve-se
tomar a decisão arbitrariamente, só que agora a solução básica é degenerada,
isto é, a variável que vai entrar na base com um valor igual a zero.
O seguinte modelo é um exemplo para a análise das implicações do
empate na hora da saída.
30
Max Z=5 x1  2 x2
Sujeito a:
x1  0
x2  0
4 x1  3 x2  12
x1, x2  0
Colocando as variáveis de folga no modelo:
Max Z=5 x1  2 x2
Sujeito a:
x1 
x3
x2 
0
0
x4
4 x1  3 x2 
x5  12
x1, x2 , x3 , x 4 , x5  0

Z
x1
x2
x3
x4
x5
b
Base
1
-5
-2
0
0
0
0
(0)
x3
0
1
0
1
0
0
3
(1) 
x4
0
0
1
0
1
0
4
(2)
x5
0
4
3
0
0
1
12
(3)
Escolhendo a variável que deve sair da base temos:
Linha (1): x1 
3
1
Linha (3): x1 
12
4
31
Nos dois casos o resultado da divisão é 3, portando escolhendo
arbitrariamente x3 para sair da base, temos:

x1
Z
x2
x3
x4
x5
b
Base
1
0
-2
5
0
0
15
(0)
x3
0
1
0
1
0
0
3
(1)
x4
0
0
1
0
1
0
4
(2)
x5
0
0
3
-4
0
1
0
(3) 
A variável básica x5 é nula. Isso sempre ocorrerá quando houver um
empate na saída. As variáveis x3 e x5 se anulam, sendo assim a variável que
fica na base também se anula. Quando isso ocorre se diz que a solução
compatível é degenerada.
4.4.4. Múltiplas soluções
O método simplex é capaz de acusar a ocorrência deste tipo de solução.
Exemplo:
Max Z  x1  2 x2
sujeito a:
x1  3
x2  4
x1  2 x2  9
x1, x2  0
Colocando as variáveis de folga obtém-se:
32
Max z  x1  2 x2
s.a.
 x3
x1
3
 x4
x2
x1  2 x2
4
 x5  9
x1, x2 , x3 , x4 , x5  0

Z
x1
x2
x3
x4
x5
b
Base
1
-1
-2
0
0
0
0
(0)
x3
0
1
0
1
0
0
3
(1)
x4
0
0
1
0
1
0
4
(2) 
x5
0
1
2
0
0
1
9
(3)
A variável que deve entrar na base é x 2 . Para escolher a variável
que sai da base deve-se fazer:
linha (2): x2  4
linha (3): x2 
9
 4,5
2

Z
x1
x2
x3
x4
x5
b
Base
1
-1
0
0
2
0
8
(0)
x3
0
1
0
1
0
0
3
(1)
x2
0
0
1
0
1
0
4
(2)
x5
0
1
0
0
-2
1
1
(3) 
33
A variável que é candidata a entrar na base é x1 . Para escolher a variável
que sai da base deve-se fazer:
linha (1): x1  3
linha (3): x1  1
Z
x1
x2
x3
x4
x5
b
Base
1
0
0
0
0
1
9
x3 *
0
0
0
1
2
-1
2
x2 *
0
0
1
0
1
0
4
x1 *
0
1
0
0
-2
1
1
Assim, temos a seguinte solução ótima:
Z  9 e x1  1, x2  4, x3  2, x4  0, x5  0
Observe que o coeficiente da variável não-básica x 4 na função objetivo é
nulo. A função objetivo é Z  9  0 x4  x5 . A variável x 4 pode entrar na base,
tomando qualquer valor, ficará com seu valor inalterado.
Fazendo x 4 entrar na base, obtém-se:
Z
x1
x2
x3
x4
x5
b
Base
1
0
0
0
0
1
9
x4 *
0
0
0
1/2
1
-1/2
1
x2 *
0
0
1
-1/2
0
1/2
3
x1 *
0
1
0
1
0
10
3
Observe no quadro acima que o coeficiente de x3 na função objetivo é
nula, logo se x3 entrar na base deve-se retornar ao quadro anterior.
4.4.5. Solução ilimitada
Ocorre a partir do momento em que a variável que entra na base não possui
em sua coluna nenhum coeficiente positivo. Para os programas de computador
eles apresentam a última solução básica antes que a solução se torne ilimitada.
34
5. Utilizando o Solver do Excel (Lachtermacher, 2004)
A utilização das planilhas eletrônicas como uma ferramenta, vem ganhando
adeptos por sua facilidade de utilização e por sua participação em todas as
organizações modernas. Neste tópico será introduzido algumas funções básicas
do Solver, uma das ferramentas do Excel, que facilitará a modelagem dos
problemas evitando os cálculos e assim, nos concentraremos na análise de suas
respostas. Observe o problema simples de maximização a seguir:
Max Z  2 x1  3 x2
Sujeito a:
2 x1  5 x2  7
x1  2 x2  6
2 x1  x2  1
x2  4
x1, x2  0
Primeiramente devemos designar uma célula para representar cada uma
das entidades:

A função-objetivo (expressão a ser maximizada ou minimizada)

Variáveis de decisão (variáveis que pode ser alterado o valor)

Para cada restrição:
o Uma para o lado esquerdo da restrição - LHS (left hand side)
o Uma para o lado direito da restrição - RHS (right hand side)
A Figura 9 demonstra a possível maneira de representar o problema em
questão. As células a seguir designam cada uma das entidades citadas
anteriormente:

B5 representa o valor da função-objetivo a ser maximizada;

B4 e C4 serão os valores que as variáveis de decisão assumirão na solução;

D9 até D12 são os LHS das 4 restrições;

E9 até E12 são os RHS das 4 restrições.
35
Figura 9 - Modelagem de um problema simples no Excel.
Para determinarmos cada célula citada anteriormente, necessitamos
inserir os coeficientes das restrições e da função-objetivo. Para lembrar o
significado de cada célula devem-se colocar títulos que especifiquem o conteúdo
dessa célula. As células B3 e C3 são utilizadas para inserir os valores dos
coeficientes da função-objetivo, enquanto que as células B9 até B12
representam os coeficientes das quatro restrições. Agora devemos definir cada
uma das entradas citadas anteriormente. A Tabela 1 representa as fórmulas
colocadas em cada uma destas células.
Tabela 1 – Descrição das fórmulas utilizadas nas células do Excel
B5
=(B3*B4)+(C3*C4)
Função-objetivo
D9
=B9*$B$4+C9*$C$4
LHS da 1ª restrição
D10 =B10*$B$4+C10*$C$4 LHS da 2ª restrição
D11 =B11*$B$4+C11*$C$4 LHS da 3ª restrição
D12 =B12*$B$4+C12*$C$4 LHS da 4ª restrição
A seguir, avisamos ao Excel quais células são as que representam a
função-objetivo, as variáveis de decisão, as restrições do modelo e, finalmente
para otimizar a função objetivo utilizamos a ferramenta Solver do Excel.
36
Após esse procedimento aparecerá a tabela representada pela Figura 10
Nesta janela serão informadas ao software as células que representam a
função-objetivo, as variáveis de decisão e as de restrições.
Figura 10 - Janela Parâmetros do Solver.
Na parte superior da janela (Figura 10) aparece um campo para entrada
denominado Definir célula de destino que deve representar o valor da funçãoobjetivo. Existem duas maneiras de designar esta célula, a primeira é clicar
sobre o ícone que está do lado direito do campo ou, digitar o nome da célula (B5
no exemplo) no campo. Escolhendo uma das duas maneiras, a janela resultante
para o problema é representado pela Figura 11.
Figura 11 - Escolha da célula.
37
Na linha seguinte são apresentadas as opções de maximizar, minimizar e
atingir o valor. A opção Valor de pode ser utilizada em análise do tipo ponto de
equilíbrio, onde a função Lucro (por Exemplo) atinja o valor zero, nos casos de
Programação Linear esta opção não será utilizada. Como o problema é de
Maximizar seleciona-se a opção Max.
No campo Células de variáveis serão representadas pelas células que
são as variáveis de decisão, no caso no exemplo as células B4 e C4, os valores
podem ser inseridos da mesma maneira como o caso da função-objetivo. Assim,
temos a Figura 12.
Figura 12 - Janela do Solver após a designação das células das variáveis.
O próximo passo é determinar as restrições do problema. Podemos inserir
as restrições uma de cada vez. Primeiramente para inserir a 1ª restrição deve-se
clicar no botão Adicionar, aparecerá uma janela de entrada de restrições como
representada pela Figura 13.
38
Figura 13 - Janela de entrada da restrição.
Essa janela de restrições tem três campos, que representam o LHS Referência de Célula (à esquerda), o sinal de restrição (ao centro) e o RHS –
Restrições (à direita). No caso do LHS e do RHS não é necessário a introdução
de variáveis de folga/excesso, pois o Excel fará isto automaticamente. A Figura
14 representa o formato da entrada da 1ª restrição do problema ( 2 x1  5 x2  7 ).
Figura 14 - Formato da entrada da 1ª restrição.
Vale lembrar que na célula D9 já havia sido colocado a fórmula que
representa 2 x1  5 x2  7 , ou seja, D9= B9*$B$4+C9*$C$4, onde:

B9 representa o coeficiente de x1 (valor = 2);

B4 representa o valor da variável x1 (os $ significam que a linha e a coluna
são fixas);

C9 representa o coeficiente x 2 (valor = 5);

C4 representa p valor da variável x 2 ;

E9 representa o valor RHS (constante = 7).
O próximo passo é clicar no botão OK caso não haja nenhuma restrição,
ou Adicionar para confirmar a restrição e abrir espaço para uma nova entrada.
No caso do exemplo é melhor clicar em Adicionar e inserir as outras restrições.
39
Ao final da entrada de todas as restrições, a janela do Solver terá a forma
representada pela Figura 15.
Figura 15 - Janela de entrada de parâmetros Solver.
Contudo, existe outra maneira mais simples de inserir as quatro
restrições. No campo Referência de célula: é representada pela marcação das
células simultâneas presentes na coluna do LHS e para o campo Restrições:
marcam-se as células que estão na coluna do RHS. A entrada da janela de
restrições deveria se representado pela Figura 16 e a janela do Solver pela
Figura 17.
Figura 16 - Entrada de restrições na forma alternativa.
40
Figura 17 - Janela do Solver na forma alternativa.
Faltam ainda as restrições de não-negatividade, isto é, que as variáveis
de decisão não são negativas. Para introduzi-lo, deve primeiramente clicar no
botão Opções na janela de parâmetros do Solver, e a seguir observe a Figura
18, onde as opções Presumir modelo linear (que caracteriza a implantação do
modelo de Programação Linear) e Presumir não negatividade devem estar
assinaladas. Para sair da janela basta clicar em OK e isto o levará de volta para
a janela de parâmetros.
41
Figura 18 - Opção de não-negatividade.
Por fim para resolver o problema, uma vez inserido o modelo e suas
características, basta clicar no botão Resolver (Figura 17).
Se o modelo foi corretamente inserido, será processado e o resultado
será automaticamente exibido na planilha e a seguinte planilha aparecerá na tela
(Figura 19).
Figura 19 - Opções de resultado da ferramenta Solver.
Levando em conta a mensagem que o Excel está fornecendo, neste caso,
“O Solver encontrou uma solução. Todas as restrições e condições otimizadas
foram atendidas.”, informando que uma solução ótima foi encontrada para o
42
modelo, outras mensagens podem aparecer, indicando que soluções não foram
encontradas por serem inviáveis ou ilimitadas. Caso ocorrer de valores
incoerentes ou inesperados forem observados, deve-se clicar na opção
Restaurar valores originais para restaurar os valores iniciais do modelo. Clique
na opção OK e a função do Solver será concluída obtendo os seguintes
resultados na planilha (Figura 20).
Figura 20 - Resultados inseridos na planilha.
Os resultados que poderão ser lidos na planilha são os valores das
variáveis de decisão na solução ótima e o valor da função-objetivo. Esses
valores são representados na Figura 20 pelas células B4, C4 e B5. Para
visualizar todos os resultados, deve se retornar ao Solver clicar resolver para
voltar à janela de Resultados do Solver onde a opção Resposta deve ser
selecionada, igual à Figura 21 a seguir. O resultado é apresentado em outra
janela do Excel, representado pela Figura 22.
43
Figura 21 - Opção do relatório de respostas.
Figura 22 - Relatório de resultados do Solver.
Analisando o relatório obtido notamos que este é dividido em três partes.
A primeira é a função-objetivo, a segunda tem relação com as variáveis de
decisão e a terceira com as restrições.
A primeira parte mostra no lado esquerdo a célula que foi escolhida para
representar a função-objetivo, depois o valor inicial da função-objetivo (zero no
caso) e, finalmente no extremo direito, o valor da função-objetivo na solução
ótima.
44
A segunda parte mostra no lado esquerdo as células que representam
cada uma das variáveis de decisão, depois do valor inicial das mesmas (zero no
caso) e, finalmente no extremo direito, o valor de cada variável na solução ótima.
A terceira parte mostra às restrições do modelo. Cada linha está
relacionada com uma das restrições. No lado esquerdo, na coluna Valor da
célula aparece cada célula que representa o LHS de cada restrição, nessa
coluna Valor da célula são apresentados os valores das respectivas células na
solução ótima. Sob a coluna Fórmula aparece a fórmula da restrição. Sob a
coluna Status podem aparecer duas opções Agrupar e Sem Agrupar. A opção
Agrupar aparece quando o LHS é igual ao RHS na solução ótima, significa que a
restrição participa da definição da solução ótima, ou seja, limita de alguma
maneira a melhora do valor da função-objetivo. A última coluna representa as
variáveis de folga/excesso (Transigência). Para cada restrição de desigualdade
deve introduzir uma variável de folga ou de excesso de maneira a tornar a
desigualdade em igualdade. Estas variáveis medem a diferença entre o LHS e o
RHS da restrição. Se a diferença entre RHS-LHS for positiva, no caso de
restrições do tipo menos ou igual deve introduzir variáveis de folga. Se RHSLHS for negativa, no caso de restrições do tipo maior ou igual introduz variáveis
de excesso.
6. Utilizando o Lindo (Hillier e Lieberman, 2006)
O software Lindo será utilizado em programação linear para a resolução
em especial de pequenos problemas, pois é um software de fácil aprendizado e
manuseio.
A vantagem que o Lindo oferece é que o modelo de maneira algébrica
pode ser introduzido diretamente.
45
Figure 23 - Descrição do modelo no Lindo.
Observando a Figura 23 nota-se que o símbolo ponto de exclamação
indicara
comentários
esclarecedores.
A
decisão
de
utilizar
maiúsculos ou minúsculos não afetará as variáveis de decisão.
caracteres
Pode-se
também adicionar nomes do produto que esta sendo fabricado ou nomes
sugestivos, desde que não exceda 8 dígitos, e seguindo de ).
A terceira linha da formulação do Lindo mostra que o objetivo do modelo
é o de maximizar a função objetivo 2x1  3 x2 . Nas próximas linhas ocorre a
descrição das restrições. Essas restrições são escritas de maneira usual, exceto
pelos sinais de igualdade. Pelo fato de muitos teclados não incluírem sinais de
 e  ,o Lindo interpreta < ou <= como  e > ou >= como  .
O final das restrições é representado pela palavra END. Não é declarada
nenhuma
restrição
de
não-negatividade,
porque
o
Lindo
assume
automaticamente que todas as variáveis possuem esse tipo de restrição. Se,
digamos, x1 não tivesse uma restrição de não-negatividade, isso teria de ser
indicado digitando-se FREE X1 na linha seguinte abaixo do END.
Para solucionar esse método versão Windows do Lindo, selecione o
comando Solve no menu Solve ou então pressione o botão Solve na barra de
ferramentas. Numa plataforma diferente do Windows, simplesmente digite GO
seguido de um return no prompt de dois-pontos. A Figura 24 mostra o relatório
de solução resultante gerado pelo Lindo.
46
Figure 24 - Relatório de solução gerado pelo Lindo
A coluna à direita desses valores fornece os custos reduzidos. Quando
a variável é uma variável básica na solução ótima, seu custo reduzido é
automaticamente 0. Quando a variável é uma variável não-básica, seu custo
reduzido fornece alguma informação interessante. Essa variável é zero porque
seu coeficiente na função objetivo é tão pequeno (ao maximizar a função
objetivo) ou tão grande (ao minimizar) para justificar empreender a atividade
representada pela variável. O custo reduzido indica quanto esse coeficiente
pode ser aumentado (ao maximizar) ou diminuído (ao minimizar) antes que a
solução ótima mudasse e essa variável se tornasse uma variável básica.
Lembrando que essa mesma informação se encontra disponível no intervalo
possível para permanecer ótima ao coeficiente dessa variável na função
47
objetivo. O custo reduzido (para uma variável não-básica) é apenas o acréscimo
possível (ao maximizar) do valor atual desse coeficiente para permanecer dentro
de seu intervalo possível para permanecer ótima ou o decréscimo possível (ao
minimizar).
Na Figura 24 temos informações sobre três restrições funcionais. A
coluna capacidade ociosa ou Excedente dá a diferença entre os dois lados de
cada restrição.
Quando o Lindo fornece esse tipo de relatório de solução, o Lindo
também pergunta se você deseja realizar a analise de sensibilidade do intervalo.
Ao responder sim gera o relatório de intervalos adicional mostrado na parte
inferior da Figura 24. Exceto pelo fato de usar unidades de milhares de dólares
em vez de dólares para os coeficientes na função objetivo.
7. Descrição e formulação dos estudos de caso
Para a realização dos estudos de casos a seguir foram contactados cinco
empresas prestadoras de serviços, dentre elas se econtram uma loja de
esportes, uma cantina de colégio, uma academia de ginástica, uma doceria e
uma que empresa do setor têxtil, mas somente as duas últimas empresas foram
utilizadas para a realização do estudo. Das empresas que não foram
selecionadas, os dados fornecidos pelas mesmas não eram suficientes para
alimentar um modelo matemático que determine a maximização do lucro
considerando restrições.
Os dados coletados deveriam ser o preço, e o custo de cada produto
(para calcular a margem de contribuição que será utilizado no estudo), a
capacidade de alocação e as restrições dos produtos. As empresas não
selecionadas nos forneceram tais dados, contudo não haviam restrições
suficientes ou trabalhavam com um preço unificado sendo que para a realização
do estudo de maximização do lucro utiliza-se mais de uma variável.
7.1. Estudo de caso I
48
Uma doceria localizada na grande São Paulo fundada em 2009, participou
do estudo a fim de alocar melhor seus recursos para maximização do lucro. A
proprietária decidiu abrir a loja após adquirir experiência trabalhando durante
cinco anos em uma cantina de colégio. Almejando expandir o negócio a
proprietária mudou o local da cantina para uma rua movimenta no centro da
cidade de Suzano.
A doceria funciona todos os dias da semana e de acordo com a
proprietária seus produtos são sempre fresquinhos, por isso a reposição é
sempre constante. Nos meses que decorrem o final do ano a procura por seus
produtos aumenta. Estudamos qual dos produtos eram mais procurados e suas
respectivas quantidades para suprir a demanda, assim podíamos calcular a
receita máxima durante a semana
Para o estudo de caso a ser analisado foram realizados cerca de 9 visitas,
sendo que a primeira foi para a explicação do projeto. A princípio a proprietária
demonstrou interesse, mas ficou preocupada com o custo de seus produtos,
pois fazia tempo que não os calculava. No decorrer das visitas a proprietária
mostrou-se insegura com a relação de produtos que apresentavam restrições
que poderiam alimentar o modelo, por fim ela escolheu os produtos que mais
vendia.
A proprietária forneceu para a realização do estudo de caso o valor real
de venda dos produtos, e seus respectivos valores de custo (uma média), onde
desses dois valores será utilizado à margem de contribuição ou lucro (valor do
produto menos o custo dos produtos) e sua capacidade de produção. Observase a quantidade produzida e o lucro esperado para cada um dos produtos. A
restrição para o problema se encontra no espaço ocupado pelos produtos na
vitrine.
Tabela 3 – Quantidade e margem de contribuição
Produtos
Cupcake
Bolo
Croassait Enrolado Esfirra Tortinha
Quantidade
44
10
56
56
56
100
Lucro (R$)
2,70
14,00
1,50
1,00
1,00
2,00
49
7.1.1 Formulação do problema I
O problema que a doceria enfrenta é atribuído a quantidade de doces e
salgados que ela deve oferecer a fim de haver a maximização do lucro.
As variáveis de decisão x1, x 2 , x3 , x 4 , x5 , x 6 representam cada produto
escolhido pela loja visando a formulação do problema. Ou seja:
x1  Quantidade máxima de cupcakes produzidos na semana.
x 2  Quantidade máxima de bolos produzidos na semana.
x 3  Quantidade máxima de croassaits produzidos na semana.
x 4  Quantidade máxima de enrolados produzidos na semana.
x 5  Quantidade máxima de esfirras produzidos na semana.
x 6  Quantidade máxima de tortinhas produzidos na semana.
Realizada a análise das variáveis de decisão determinamos a função
objetivo para a maximização da receita, ou seja, desejamos descobrir a
quantidade de produtos necessários para que o valor obtido da receita seja o
maior possível.
Utilizando os dados de lucro da Tabela 3 obtemos somatório da
multiplicação da margem de contribuição pelas variáveis de decisão resulta a
função objetivo, que determinará a receita máxima da doceria. Para visualizar
melhor a função objetivo temos:
Max Z = 2,70x1+14,00x 2 +1,50x3 1,00x 4 +1,00x5 +2,00x 6
Determinando as restrições para a função, temos:

A primeira restrição é relacionada capacidade de produtos que a loja
disponibiliza na vitrine durante a semana. Sabendo que o bolo possui um
tamanho 4 vezes maior que os demais. Logo temos a seguinte restrição:
x1  4x 2  x 3  x 4  x 5  300

A segunda restrição é relacionada com a capacidade máxima de produção
dos cupcakes.
50
x1  44

A terceira restrição é relacionada com a capacidade máxima de produção
dos bolos.
x 2  10

A quarta restrição é relacionada com a capacidade máxima de produção dos
croassaits.
x 3  56

A quinta restrição é relacionada com a capacidade máxima de produção dos
enrolados.
x 4  56

A sexta restrição é relacionada com a capacidade máxima de produção das
esfirras.
x 5  56

A sétima restrição é relacionada com a capacidade máxima de produção das
tortinhas.
x 6  100

A oitava restrição diz respeito a quantidade máxima de esfirras e enrolados
que ocupam o lugar na mesma prateleira durante a semana.
x 4  x 5  70

A nona restrição diz respeito a quantidade máxima de croassaits e tortinhas
que ocupam o lugar na mesma prateleira durante a semana.
x3  x 6  84

A décima restrição é relacionada a máxima quantidade de bolos e cupcakes
que ocupam o lugar na prateleira durante a semana.
x1  x 2  38
Dessa forma a representação matemática do problema é dada por:
51
Max Z = 2,70x1+14,00x 2 +1,50x 3 1,00x 4 +1,00x 5 +2,00x 6
Sujeito a:
x1  4x 2  x 3  x 4  x 5  300
x1  44
x 2  10
x 3  56
x 4  56
x 5  56
x 6  100
x 4  x 5  70
x 3  x 6  84
x1  x 2  38
x1, x 2 , x 3 , x 4 , x 5 , x 6  0
7.1.2 Resolução do problema I utilizando o Lindo
Pelos conhecimentos adquiridos com o projeto, o software selecionado
para a resolução do problema foi o Lindo. O software Lindo oferece a vantagem
de inserir o modelo diretamente na maneira algébrica. Sendo assim, pode
determinar o número ótimo de cada produto para que a receita máxima fosse
encontrada.
Inserindo as informações do problema como na Figura 25, temos:
52
Figura 25-Descrição do modelo da dolceria
Primeiramente foi inserido o ponto de exclamação para indicar alguns
comentários esclarecedores como a definição das variáveis de decisão. Feito
isso, a função objetivo Max Z = 2,70x1+14,00x 2 +1,50x3 1,00x 4 +1,00x5 +2,00x 6 é
adicionada. Próximo passo foi inserir “Subject to” e as restrições destacadas
para a resolução do problema. Pode-se inserir os nomes dos produtos seguido
de ) como o “Bolo)” indicado na Figura 25, lembrando que o programa não
admite mais de 8 caracteres. Ao final das restrições observa-se a palavra “end”.
O software Lindo assume automaticamente que o problema apresenta
uma característica linear e que as variáveis são maiores ou iguais a zero, não
havendo necessidade de declarar nenhuma restrição de não-negatividade
( x1, x 2 , x 3 , x 4 , x 5 , x 6  0 ). O relatório de decisão aparece após a escolha da
opção Solve no menu (Figura 26).
53
Figura 26-Relatório de soluções geradas para a dolceria
Analisando o relatório de soluções gerado (observado na Figura 26) para
o problema o resultado obtido para a função objetivo foi um lucro máximo de
R$453,60. Para obter esse lucro máximo a loja deve vender 28 cupcakes, os 10
bolos, 56 enrolados, 14 esfirras, 84 tortinhas e nenhum croassait.
7.1.3 Conclusão da análise dos resultados I
A proprietária identificou uma necessidade de otimizar a receita através
de seus produtos.
Houve uma dificuldade para o fornecimento dos dados pela proprietária,
que hesitou com a relação de produtos a disponibilizar para o estudo, mas por
54
fim houve um consentimento de que era melhor fornecer os dados produtos de
maior fluxo.
Logo, conclui-se que para a função objetivo atinja o valor máximo a
proprietária deve vender 28 cupcakes, 10 bolos, 56 enrolados, 14 esfirras, 84
tortinhas e nenhum croassait.
Somando o valor dessas quantidades obteve uma receita semanal de
quatrocentos e cinqüenta e três reais e sessenta centavos (R$453,60).
Levando em consideração os resultados, a proprietária reduziu a
produção de cupcakes para 30 e de tortinhas para 90 por semana, contudo a
variedade dos salgados continuou a mesma, adotando uma produção reduzida
e/ou uma reposição dos salgados após o seu término.
7.2. Estudo de caso II
Para a realização deste estudo de caso foi contactada uma pequena loja
do setor têxtil que revende diferentes tipos de tecidos (estampado, xadres, seda,
forros, malhas, sarjas, etc.) normalmente para pequenas confecções. A princípio
foram realizadas poucas visitas, já que o proprietário dispunha dos dados e
decidimos logo quais seriam os produtos e quantidade que possibilitaria a
melhor decisão de compra.
Decidimos que seria melhor selecionar os tecidos mais procurados, como
o forro de alpaseda (100% acetato), o cetim (100% poliéster) e o forro de cetim
para festa sem elastano (100% poliéster), utilizados geralmente em roupas.
Tendo como objetivo a obtenção do maior lucro, gostaríamos de
determinar qual a quantidade certa de tecidos a ser comprada. Contudo de
acordo com o proprietário são comprados cerca de 125 m de alpaseda, 90 m de
cetim e 120 m de cetim para festa mensalmente. Contudo muitas vezes o
espaço reservado (300 m) para os tecidos não era suficiente, e a quantidade ia
diretamente para uma confecção no fundo da loja.
7.2.1 Formulação do problema II
55
Observando a Tabela 5 visualiza-se melhor o lucro obtido por peça, a
quantidade comprada e uma demanda prevista para o mês.
Tabela 4- Dados dos tecidos
Produto
Lucro/m (R$) Quantidade Max (m) Demanda prevista(m)
Alpaseda
10,05
125
100
Cetim
13,15
90
90
Cetim festa
22,15
120
90
A loja de tecidos deseja saber qual a quantidade certa de tecidos precisa
comprar para obterem o maior lucro. Para isso as variáveis de decisão
x1, x 2 , x 3 representaram os tecidos da loja.
x1  metragem máxima do forro de alpaseda.
x 2  metragem máxima do forro de cetim.
x 3  metragem máxima do forro de cetim de festa.
Realizada a análise das variáveis de decisão determinamos a função
objetivo para a maximização da receita, ou seja, descobrir a metragem do forro
necessário para que o valor obtido da receita seja a maior possível.
O somatório da multiplicação da margem de contribuição pelas variáveis
de decisão resulta a função objetivo, que determinará a receita máxima da loja
de tecidos. Para visualizar melhor a função objetivo temos:
Max Z = 10,05x1+13,15x 2 +22,15x 3
Determinando as restrições para a função, temos:

A primeira restrição é relacionada capacidade que a loja disponibilizou para
a venda do tecido e a sua capacidade de compra.
125x1 90x2  120x3  300

A segunda restrição é relacionada com a metragem máxima do forro de
alpaseda.
x1  100

A terceira restrição é relacionada com metragem máxima do forro de cetim.
x 2  90
56

A quarta restrição é relacionada com metragem máxima do forro de cetim de
festa.
x 3  90
A representação matemática do problema é dado por:
Max Z = 10,05x1+13,15x 2 +22,15x 3
Sujeito a :
125x1  90x2  120x3  300
x1  100
x 2  90
x 3  90
x1, x 2 , x 3  0
7.2.2 Resolução do problema II utilizando o Lindo
Utilizando o Lindo para determinar o número ótimo de cada produto para
que a receita máxima seja encontrada, temos a Figura 27.
Figure 27-Descrição do modelo da loja de tecidos
Inserido o ponto de exclamação para indicar alguns comentários como a
definição
das
variáveis
de
decisão.
Feito
isso,
a
função
objetivo
Max Z = 10,05x1+13,15x 2 +22,15x 3 é adicionada. Próximo passo foi inserir
“Subject to” e as restrições destacadas para a resolução do problema. Pode-se
57
inserir os nomes dos produtos seguido de ) como o “cetim)” indicado na Figura
27, lembrando que o programa não admite mais de 8 caracteres. Ao final das
restrições observa-se a palavra “end”.
Não há necessidade de declarar nenhuma restrição de não-negatividade
( x1, x 2 , x 3 , x 4 , x 5 , x 6  0 ), o Lindo assumira automaticamente todas as variáveis
que possuem esse tipo de restrição. O relatório de decisão aparece após a
escolha da opção Solve no menu.
Com base no relatório, na Figura 28 temos:
Figure 28-Relatório de soluções geradas para a loja de tecidos
O lucro Máximo obtido de acordo com o relatório foi de R$2017,62, sendo
que a quantidade máxima em metros do tecido de forro de cetim de festa foi de
90m e que o tecido de alpaseda foi de 2,40m, não houve necessidade da
compra do tecido de forro de cetim.
7.2.3 Conclusão da análise dos resultados II
Ao decidir quais produtos eram os mais procurados da loja de tecidos
identificou-se a necessidade de otimizar a receita. Sendo que o fornecimento
das informações foi facilitado pelo proprietário.
58
De acordo com o estudo para que a maior receita seja atingida o
proprietário deve comprar e revender 90 m de forro de cetim para festa, mais
2,40m de forro de alpaseda e nenhum forro de cetim. Logo a receita é
representada pela quantia de dois mil e dezessete reais e sessenta e dois
centavos (R$2017,62) para o período mensal.
8. Conclusão
A Pesquisa Operacional foi desenvolvida utilizando as ferramentas da
programação linear para solucionar seus problemas, podendo estes ser de
distribuição de recursos escassos, determinação de objetivos de maximização
de lucros e minimização de custos, logo, os problemas de programação
matemática em que funções objetivo de restrição são lineares.
Logo para a realização deste projeto de Iniciação Científica foi utilizado o
conhecimento adquirido do estudo realizado de Pesquisa Operacional e do
software Lindo.
Tendo como objetivo demonstrar a maximização do lucro
considerando suas restrições. Salve duas empresas, uma de serviços e a outra
do setor têxtil, dentre cinco empresas selecionadas. Das empresas visitadas 3
delas não apresentavam restrições ou variáveis necessárias ou suficientes para
a formulação do modelo matemático.
Para o primeiro caso estudado foram feitas várias visitas a loja até que a
proprietária escolhesse os produtos e avaliasse os custos médios de cada um,
fornecido o preço e o custo de cada produto pode-se determinar o lucro que é
utilizado para a formulação da função objetivo (maximizar o lucro), adicionando
as restrições de produção e alocação dos produtos, conclui-se que para a
proprietária garantir sua receita máxima ela deve vender 28 cupcakes, 10 bolos,
56 enrolados, 14 esfirras, 84 tortinhas e nenhum croassait obtendo uma receita
semanal de quatrocentos e cinqüenta e três reais e sessenta centavos
(R$453,60).
Sendo que por fim, a proprietária preferiu manter a variedade de salgados
reduzindo sua produção, ou produzindo-os conforme sua demanda reduziu
também o número de cupcakes e de tortinhas.
59
Já para o segundo caso estudado foram realizadas poucas visitas, pois o
proprietário do setor têxtil forneceu os dados de preço, custo, quantidade, a
disponibilidade do espaço e uma previsão de venda para 3 tecidos, o lucro
Máximo encontrado para o estudo foi de R$2017,62, sendo que a quantidade
máxima em metros do tecido de forro de cetim de festa foi de 90m e o tecido de
alpaseda foi de 2,40m, não houve necessidade da compra do tecido de forro de
cetim.
Referências bibliográficas
HILLIER, F. S., LIEBERMAN, G. J. Introdução à Pesquisa Operacional. 8ª Ed.
São Paulo: McGraw-Hill, 2006.
LACHTERMACHER, G. Pesquisa operacional na tomada de decisões:
modelagem em Excel. 2ª Ed. Rio de Janeiro: Campus, 2004.
PUCCINI, A. L. Introdução à Programação Linear. Rio de Janeiro: LTC, 1980.
ARENALES, M., ARMENTANO, V., MORABITO, R., YANASSE, H. Pesquisa
operacional. Rio de Janeiro: Campus, 2007.