A programação linear é um método matemático usado para otimizar (maximizar ou minimizar conforme apropriado) uma função cujas variáveis são restritas, desde que a função e as restrições sejam variáveis linearmente dependentes.
Geralmente, a função a ser otimizada modela uma situação prática, como o lucro de um fabricante cujos insumos, mão de obra ou maquinaria são limitados.
Um dos casos mais simples é o de uma função linear a ser maximizada, que depende apenas de duas variáveis, chamadas variáveis de decisão . Pode ser da forma:
Z = k 1 x + k 2 y
Com k 1 e k 2 constantes. Essa função é conhecida como a função objetivo . Evidentemente, existem situações que merecem mais de duas variáveis para estudo, sendo mais complexas:
Z = k 1 x 1 + k 2 x 2 + k 3 x 3 +….
E as restrições também são modeladas matematicamente usando um sistema de equações ou desigualdades, igualmente lineares em x e y .
O conjunto de soluções nesse sistema é chamado de soluções viáveis ou pontos possíveis . E entre os pontos possíveis, há pelo menos um que otimiza a função objetivo.
A programação linear foi desenvolvida independentemente pelo físico e matemático americano George Dantzig (1914-2005) e pelo matemático e economista russo Leonid Kantorovich (1912-1986) logo após a Segunda Guerra Mundial.
O método de solução de problemas conhecido como método simplex é a criação de Dantzig, que trabalhou para a Força Aérea Americana, a Universidade de Berkeley e a Universidade de Stanford.
Modelos de programação linear
Os elementos necessários para estabelecer um modelo de programação linear, apropriado para uma situação prática, são:
-Função objetiva
Variáveis de decisão
-Restrições
A função objetivo define o que você deseja alcançar. Por exemplo, suponha que você queira maximizar os lucros da fabricação de certos produtos. Em seguida, a função “lucro” é estabelecida, de acordo com o preço pelo qual os produtos são vendidos.
Em termos matemáticos, essa função pode ser expressa em abreviação usando a notação de soma:
Z = ∑k i x i
Nesta equação, k i são coeficientes e x i são as variáveis de decisão.
Variáveis de decisão são os elementos do sistema cujo controle você tem e seus valores são números reais positivos. No exemplo proposto, as variáveis de decisão são a quantidade de cada produto a ser fabricado para obter o lucro máximo.
Finalmente, temos as restrições, que são equações lineares ou desigualdades em termos das variáveis de decisão. Eles descrevem as limitações do problema, que são conhecidas e podem ser, por exemplo, as quantidades de matéria- prima disponíveis na fabricação.
Tipos de restrições
Pode ter um número M de limitações, a partir de j = 1 para j = M . Matematicamente, as restrições são de três tipos:
- A j = ∑ a ij . x i
- B j ≥ ∑ b ij . x i
- C j ≤ i c ij . x i
A primeira restrição é do tipo de equação linear e significa que o valor A j , que é conhecido, deve ser respeitado.
As duas restrições restantes são desigualdades lineares e significa que os valores conhecidos B j e C j podem ser respeitados ou excedidos, quando o símbolo que aparece é ≥ (maior que ou igual a) ou respeitado ou não excedido, se o símbolo for ≤ (menos que ou igual a).
Exemplo de modelo
Os campos de aplicação são muito diversos, variando de administração de empresas a nutrição, mas, para entender o método, é proposto abaixo um modelo simples de uma situação prática com duas variáveis.
Uma pastelaria local é conhecida por duas especialidades: o bolo da floresta negra e o bolo sacripantino.
Na elaboração, eles precisam de ovos e açúcar. Para a floresta negra são necessários 9 ovos e 500 g de açúcar, enquanto para o sacripantino são necessários 8 ovos e 800 g de açúcar. Os respectivos preços de venda são US $ 8 e US $ 10.
O problema é: quantos bolos de cada tipo a massa deve produzir para maximizar seu lucro, sabendo que possui 10 quilos de açúcar e 144 ovos?
Variáveis de decisão
As variáveis de decisão são “x” e “y”, que recebem valores reais:
-x: a quantidade de bolos do tipo floresta negra
-y: bolos do tipo sacripantina.
Restrições
As restrições são dadas pelo fato de que o número de bolos é uma quantidade positiva e há quantidades limitadas de matéria-prima para prepará-los.
Portanto, matematicamente, essas restrições assumem a forma:
- x ≥ 0
- e ≥0
- 9x + 8y ≤ 144
- 0,5 x + 0,8y ≤ 10
As restrições 1 e 2 constituem a condição de não negatividade descrita acima, e todas as desigualdades levantadas são lineares. Nas restrições 3 e 4 estão os valores que não devem ser excedidos: 144 ovos e 10 kg de açúcar.
Função objetiva
Finalmente, a função objetivo é o lucro obtido pela fabricação de “x” número de bolos da floresta negra mais “y” número de sacripantinos. É construído multiplicando o preço pelo número de bolos feitos e adicionando para cada tipo. É uma função linear que chamaremos de G (x, y):
G = 8x + 10y
Métodos de solução
Entre as várias metodologias de solução estão os métodos gráficos, o algoritmo simplex e o método do ponto interior, para citar alguns.
– método gráfico ou geométrico
Quando você tem um problema de duas variáveis como o da seção anterior, as restrições determinam uma região poligonal no plano xy , chamada região viável ou região de viabilidade .
Essa região é construída usando as linhas de restrição , que são as linhas obtidas das desigualdades das restrições, trabalhando apenas com o sinal de igual.
No caso da padaria que deseja otimizar lucros, as linhas de restrição são:
- x = 0
- y = 0
- 9x + 8y = 144
- 0,5 x + 0,8y = 10
Todos os pontos da região delimitados por essas linhas são possíveis soluções, portanto existem infinitos deles. Exceto no caso de a região viável estar vazia, caso em que o problema apresentado não tem solução.
Felizmente, para o problema da pastelaria a região viável não está vazia, temos abaixo.
A solução ideal, se existir, é encontrada com a ajuda da função objetivo. Por exemplo, ao tentar encontrar o lucro máximo G, temos a seguinte linha, chamada linha iso-profit :
G = k 1 x + k 2 y → y = -k 1 x / k 2 + G / k 2
Com esta linha, obtemos todos os pares (x, y) que fornecem um determinado ganho G, de modo que há uma família de linhas de acordo com o valor de G, mas todas com a mesma inclinação -k 1 / k 2 , de modo que elas são linhas paralelas.
A solução ideal
Agora, pode ser demonstrado que a solução ideal de um problema linear é sempre um ponto final ou vértice da região viável. Assim:
A linha de solução é a mais distante da origem e tem pelo menos um ponto em comum com a região viável.
Se a linha mais próxima da origem tem um segmento inteiro em comum com a região viável, diz-se que existem infinitas soluções. Este caso ocorre se a inclinação da linha iso-benefícios for igual à de qualquer uma das outras linhas que limitam a região.
Para nossa pastelaria, os vértices candidatos são A, B e C.
– método simplex de Dantzig
O método gráfico ou geométrico é aplicável a duas variáveis. No entanto, é mais complicado quando existem três variáveis e impossível de usar para um número maior de variáveis.
Ao lidar com problemas de mais de duas variáveis, é utilizado o método simplex , que consiste em uma série de algoritmos para otimizar as funções objetivas. Matrizes e aritmética simples são frequentemente usadas para realizar os cálculos.
O método simplex começa escolhendo uma solução viável e verificando se é ideal. Se for, já resolvemos o problema, mas se não for, continuamos em direção a uma solução mais próxima da otimização. Se a solução existe, o algoritmo encontra-o em algumas tentativas.
Formulários
A programação linear e não linear é aplicada em muitos campos para tomar as melhores decisões em termos de redução de custos e aumento de lucros, que nem sempre são monetários, pois podem ser medidos no tempo, por exemplo, se você quiser minimizar o tempo necessário para realizar uma série de operações.
Aqui estão alguns campos:
– No marketing, é usado para encontrar a melhor combinação de mídia (redes sociais, televisão, imprensa e outras) para anunciar um determinado produto.
-Para a atribuição de tarefas adequadas ao pessoal de uma empresa ou fábrica ou de horários a eles.
– Na seleção dos alimentos mais nutritivos e com o menor custo nas indústrias pecuária e avícola.
Exercícios resolvidos
– Exercício 1
Resolva graficamente o modelo de programação linear proposto nas seções anteriores.
Solução
É necessário representar graficamente o conjunto de valores determinado pelo sistema de restrição especificado no problema:
- x ≥ 0
- e ≥0
- 9x + 8y ≤ 144
- 0,5 x + 0,8y ≤ 10
A região dada pelas desigualdades 1 e 2 corresponde ao primeiro quadrante do plano cartesiano. Quanto às desigualdades 3 e 4, começamos por encontrar as linhas de restrição:
9x + 8y = 144
Qual é o valor de x?
A região viável é um quadrilátero cujos vértices são os pontos A, B, C e D.
O ganho mínimo é 0, portanto, a linha 8x + 10y = 0 é o limite inferior e as linhas iso-profit têm uma inclinação -8/10 = – 0,8.
Esse valor é diferente das inclinações das outras linhas de restrição e, como a região viável é limitada, existe a única solução.
Essa solução corresponde a uma linha da inclinação -0,8 que passa por um dos pontos A, B ou C, cujas coordenadas são:
A (11; 5.625)
B (0; 12,5)
C (16, 0)
Solução ideal
Calculamos o valor de G para cada um destes pontos:
– (11; 5.625): G A = 8 x 11 + 10 x 5.625 = 144,25
– (0; 12,5): G B = 8 x 0 + 10 x 12,5 = 125
– (16, 0): G C = 8 x 16 + 10 x 0 = 128
O maior ganho é encontrado na fabricação de 11 bolos da floresta negra e 5.625 bolos sacripantinos. Esta solução está de acordo com a encontrada no software.
– Exercício 2
Verifique o resultado do exercício anterior usando a função Solver disponível na maioria das planilhas, como Excel ou Calc de LibreOffice, que incorporam o algoritmo Simplex para otimização em programação linear.
Solução
Referências
- Brilhante. Programação linear. Recuperado de: shiny.org.
- Eppen, G. 2000. Pesquisa Operacional em Ciências Administrativas. 5 ª. Edição. Prentice Hall.
- Haeussler, E. 1992. Matemática para Administração e Economia. 2nd. Edição. Grupo de Publicações Ibero-americanas.
- Hiru.eus. Programação linear. Recuperado de: hiru.eus.
- Wikipedia. Programação linear. Recuperado de: es. wikipedia.org.