Modelagem
2djnry9.jpg

A pesquisa operacional busca estabelecer um processo de decisão para a escolha da solução ótima dentre as alternativas para resolver o problema. O principal desafio do processo de otimização é modelar o problema que se deseja otimizar. A modelagem é a arte de representar situações reais através de expressões matemáticas. As expressões matemáticas representam uma aproximação da realidade, e por isto chamamos de modelo.
Abaixo será apresentado um breve resumo do que ocorre em um processo de modelagem:

2q9joky.jpg

Resolvendo um problema de otimização:

  1. Definir conceitualmente o problema.
  2. Formular o modelo matemático para representar o problema.
  3. Testar o modelo e aprimorá-lo se necessário (e possível).
  4. Implementar!

Fluxograma para resolver um problema de otimização:

2gxmp12.png

Fonte:Autor
Disponível:http://www.producao.ufrgs.br/arquivos/disciplinas/382_po_apostila_completa_mais_livro.pdf

Para solucionar um problema utilizando-se a programação linear, primeiramente é necessário que o mesmo seja compreendido. A descrição do passo a passo acima é capaz de auxiliar na compreensão e resolução do mesmo. Contudo, é necessário que seja ressaltado a importância da formulação conceitual (F.C), pois as informações que constituirão a base da formulação matemática (função objetivo e as restrições) serão retiradas da F.C. A partir da formulação conceitual é possível ter uma noção de como será a formação da função objetivo e identificar quantas e quais serão as restrições do problema.

Ao modelar um problema para otimização, é importante identificar os seguintes elementos:

e8r8mf.png

A função objetivo é identificada em um problema pelo desejo de maximizar ou minimizar algo. Na programação linear o problema poderá apresentar apenas uma função objetivo.
As restrições são representadas por:

  • $\leq$
  • $\geq$
  • $>$
  • $<$
  • =

Atente-se ao sinal de igualdade (=)! Embora ele seja usado para constituir restrições, o mesmo impõe condições que podem inviabilizar a solução. Tais como, a exigência que um determinado produto tenha exatamente aquela quantia a ser fabricada/distribuída, sendo forçada tal condição e muitas vezes a solução poderia ser melhor caso a restrição não existisse. Então, o sinal de igualdade é utilizado apenas em situações que realmente exigem um número exato do produto.

As restrições possuem a finalidade de não permitir que a solução caminhe para o infinito, elas restringem a busca pelo resultado ótimo, diminuindo o número de soluções.

O processo de identificação e construção de uma variável será através da função objetivo e será construída a partir das restrições. Importante atentar-se que as variáveis utilizadas na função objetivo têm que estar contidas nas restrições, ou seja, uma variável tem que apresentar suas alternativas que irão buscar uma solução.

O problema MatoCerto

A empresa MatoCerto oferece três tipos de controle da mato competição. Cada controle demanda uma determinada quantidade de mão-de-obra (em horas por hectare) e consome uma quantidade de insumo (em litros por hectare):

  • Controle A. M.O.: 7h/ha. Insumo: 3 L/ha.
  • Controle B. M.O.: 4h/ha. Insumo: 4 L/ha.
  • Controle C. M.O.: 4h/ha. Insumo: 2 L/ha.

O lucro que a empresa obtém para cada hectare combatido aplicando o controle A, B e C é de 60 R$/ha, 50 R$/ha e 30 R$/ha respectivamente. O estoque de insumo é de 200 litros e M.O disponível é de 150 horas.
Qual seria a quantidade em hectares de cada tipo de controle que a empresa deveria executar para obter o máximo lucro?

Passo a passo:

Passo 1 Identifique o objetivo e as restrições do problema, e crie a formulação conceitual do problema.

Formulação conceitual

Maximizar o lucro
Sujeito a:
Restrição de horas de mão-de-obra
Restrição de insumo

Passo 2 Transforme as definições em modelos matemáticos.

  • As variáveis da F.O. devem aparecer nas restrições.
  • As unidades devem estar padronizadas.

Formulação matemática

MaxZ = 60 A + 50 B + 30 C
Sujeito a:
7 A + 4 B + 4 C <= 150
3 A + 4 B + 2 C <= 200
1qs414.png

Figura 1 - Partes de um modelo de Programação Linear

Passo 3 Proponha valores para as variáveis da F.O. (cenário) e verifique se a solução é viável ou inviável. Uma solução é viável quando todas as restrições são atendidas.

Problema de Transporte

Uma empresa que produz açúcar tem uma fábrica em São Carlos e outra
em Araraquara (F1 e F2) e 3 clientes espalhados pelo estado de São Paulo,
que chamaremos de C1, C2 e C3.
A fábrica de São Carlos produz (p1) 50 toneladas de açúcar por semana,
enquanto que a fábrica de Araraquara produz (p2) 100 toneladas.
Cada cliente possui uma demanda dj (em toneladas, por semana) por
açúcar, dada pela tabela abaixo:

C1 C2 C3
20 60 40

O custo cij , em reais, de enviar uma tonelada de produto de cada fÁbrica i
para cada cliente j é dado pela tabela abaixo:

C1 C2 C3
F1 35 20 40
F2 90 55 70

O problema É determinar quanto açúcar enviar, em uma semana, de cada
fábrica para cada cliente de modo a satisfazer todas as restrições e
minimizar o custo.

Resolução:

Para modelar este problema matematicamente, vamos definir variáveis xij
que terão como valor a quantidade de toneladas de açúcar enviadas, em
uma semana, da fábrica Fi para um cliente Cj.
Com as variáveis definidas, podemos definir nossa função objetivo. Esta é
uma função de R¬ em R que, dados os valores das variáveis xij devolve o
custo.
Usando os custos de transporte de cada fábrica para cada cliente,
podemos definir a função objetivo como:
f (x) = 35x11 + 20x12 + 40x13 + 90x21 + 55x22 + 77x23.
No caso deste problema, desejamos minimizar a função objetivo.
Agora precisamos definir quais são as restrições do nosso problema.
Teremos 3 grupos de restrições:
1 - As restrições do primeiro grupo servirão para garantir que uma fábrica
não envia mais produtos do que é capaz de produzir.
2 - As restrições do segundo grupo irão garantir que as demandas de
cada cliente serão atendidas.
3 - As restrições do terceiro grupo irão garantir que a quantidade de
produto enviada de uma fábrica a um cliente nunca é negativa.
Para garantir que fábrica F1 não envia mais produto do que é capaz de produzir (50 toneladas), temos a restrição:
x11 + x12 + x13 ≤ 50.
Analogamente, para garantir que fábrica F2 não envia mais produto do que é capaz de produzir (100 toneladas), temos a restrição:
x21 + x22 + x23 ≤ 100.
Para garantir que o cliente C1 receba a quantidade de produto desejada (20 toneladas), temos a restrição:
x11 + x21 = 20.
Analogamente, para garantir que os clientes C2 e C3 recebam as quantidades de produtos desejadas (60 e 40 toneladas, respectivamente), temos as restrições:
x12 + x22 = 60, x13 + x23 = 40.
Por fim, para garantir que as quantidades de produto enviadas de cada fábrica Fi para cada cliente Cj não seja menor que zero, temos as restrições:
x11 ≥ 0,
x12 ≥ 0,
x13 ≥ 0,
x21 ≥ 0,
x22 ≥ 0,
x23 ≥ 0.
Então, nosso modelo para este problema de transporte fica:
minimizar 35x11 + 20x12 + 40x13 + 90x21 + 55x22 + 77x23
sujeita a: x11 + x12 + x13 ≤ 50,
x21 + x22 + x23 ≤ 100,
x11 + x21 = 20, x12 + x22 = 60,
x13 + x23 = 40,
x11, x12, x13, x21, x22, x23 ≥ 0.
Para este modelo, a solução é:
x11 = 20, x12 = 0, x13 = 30,
x21 = 0, x22 = 60, x23 = 10.
O custo total para enviar todas as toneladas necessárias de açúcar para os clientes será de 5970 reais.

Resolução de problemas:

Vídeo 1 - Programação Linear - Modelagem e Resolução - Exercício 1

Vídeo 2 - PO - Modelo de programação linear - Exemplo 1

Vídeo 3 - PO - 1 - Modelo de programação linear - Exercício resolvido 1

Exercício de Modelagem 1:

O quadro 1 descreve as atividades de uma determinada empresa coletora de resíduos urbanos. A cidade para onde os serviços de coleta estão sendo planejados foi subdividida em blocos, com número variável de quarteirões por bloco. O critério para definição dos blocos foi estabelecido em função do número de quarteirões que uma equipe básica formada por 1 (um) motorista e 2 (dois) auxiliares é capaz de cobrir em um dia de trabalho. A empresa propõe que em alguns desses blocos seja implantado o sistema seletivo de coleta de resíduos, ao invés do sistema padrão. O Quadro 1 resume as informações básicas desses dois sistemas. A empresa decidiu que empregaria uma equipe total de no máximo 120 funcionários. A questão gerencial da empresa, numa primeira etapa, é como alocar esses funcionários nos dois sistemas de coleta de resíduos, de forma a maximizar a receita obtida pela empresa. Apresente a solução do problema.

Tipo de coleta Quadro máximo de funcionários no sistema Funcionários necessários por bloco Receita da empresa por bloco (R$)
Padrão 72 3 90
Seletiva 96 6 120

Resolução utilizando o LPSolve:

Formulação Matemática:

2jfepuf.png

Resultado:

9aoa6a.png

A máxima receita será de R$ 3120,00 e poderá ser obtida ao se optar por 24 conjuntos de coleta padrão e 8 conjuntos de coleta seletiva.

Para melhor aprendizado e memorização do material, a imagem abaixo faz substituição das anotações tradicionais, para que facilite a capacidade de assimilação do conteúdo.

MAPA MENTAL

309n9e1.jpg

Fonte:Autor

Playlist: Video aulas Complementares

GRINGS- Máximos e Mínimos de uma função - Aula 1

Grings - Máximos, Mínimos, Modelagem e Otimização - Aula 2

Grings - Máximos, Mínimos, Modelagem e Otimização - Aula 3

GRINGS - Ponto de Inflexão e Concavidade da função - Aula 4

GRINGS - Máximos, Mínimos e Sela através do Hessiano - Aula 5

Grings - Máximos e Mínimos Condicionados com Multiplicadores de Lagrange - Aula 6

Salvo indicação em contrário, o conteúdo desta página é licenciado sob Creative Commons Attribution-ShareAlike 3.0 License