Programação linear: para que serve, modelos, restrições, aplicações

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 ₁ x + k ₂ y

Com k ₁ e k ₂ 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 ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

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:

1. A _j = ∑ a _ij . x _i
2. B _j ≥ ∑ b _ij . x _i
3. 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:

1. x ≥ 0
2. e ≥0
3. 9x + 8y ≤ 144
4. 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:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 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 ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

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 ₁ / k ₂ , 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:

1. x ≥ 0
2. e ≥0
3. 9x + 8y ≤ 144
4. 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

1. Brilhante. Programação linear. Recuperado de: shiny.org.
2. Eppen, G. 2000. Pesquisa Operacional em Ciências Administrativas. 5 ª. Edição. Prentice Hall.
3. Haeussler, E. 1992. Matemática para Administração e Economia. 2nd. Edição. Grupo de Publicações Ibero-americanas.
4. Hiru.eus. Programação linear. Recuperado de: hiru.eus.
5. Wikipedia. Programação linear. Recuperado de: es. wikipedia.org.