Programação linear: para que serve, modelos, restrições, aplicativos - Ciência - 2023

science

Contente

o programação linear é um método matemático usado para otimizar (maximizar ou minimizar conforme necessário) uma função cujas variáveis ​​estão sujeitas a restrições, desde que a função e as restrições sejam linearmente dependentes das variáveis.

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 maquinário 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 no formato:

Z = k1x + k2Y

Com k1 e que2 constante. Esta função é conhecida como Função objetiva. Claro, existem situações que merecem mais de duas variáveis ​​de estudo, sendo mais complexas:


Z = k1x1 + k2x2 + k3x3 +….

E as restrições também são modeladas matematicamente por um sistema de equações ou desigualdades, igualmente lineares em x e Y.

O conjunto de soluções deste sistema é denominado soluções viáveis ou pontos viáveis. E entre os pontos viáveis ​​há pelo menos um, que otimiza a função objetivo.

A programação linear foi desenvolvida de forma independente 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 ideia de Dantzig, que trabalhou para a Força Aérea dos Estados Unidos, 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, adequado a uma situação prática, são:



-Função objetiva

- Variáveis ​​de decisão

-Restrições

Na função objetivo você define o que deseja alcançar. Por exemplo, suponha que você queira maximizar o lucro da fabricação de certos produtos. Então, a função "lucro" é estabelecida, de acordo com o preço pelo qual os produtos são vendidos.

Em termos matemáticos, esta função pode ser expressa de forma abreviada usando a notação de soma:

Z = ∑kEu xEu

Nesta equação, kEu são coeficientes e xEu são as variáveis ​​de decisão.

As variáveis ​​de decisão são os elementos do sistema cujo controle se 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

Você pode ter M número de limitações, começando com j = 1 até j = M. Matematicamente, as restrições são de três tipos:

  1. PARAj = ∑ aeu j . xEu
  2. Bj ≥ ∑ beu j . xEu
  3. Cj ≤ ∑ ceu j . xEu

A primeira restrição é do tipo equação linear e significa que o valor Aj, que é conhecido, tem que ser respeitado.

As duas restrições restantes são desigualdades lineares e isso significa que os valores Bj e Cj, conhecido, pode ser respeitado ou excedido, quando o símbolo exibido for ≥ (maior ou igual a) ou respeitado ou não excedido, se o símbolo for ≤ (menor ou igual a).

Exemplo de modelo

Os campos de aplicação são muito diversos, indo da administração de empresas à nutrição, mas para entender o método, um modelo simples de uma situação prática com duas variáveis ​​é proposto a seguir.


Uma confeitaria local é conhecida por duas especialidades: o bolo da floresta negra e o bolo sacripantino.

Eles requerem ovos e açúcar em sua preparação. Para a floresta negra são necessários 9 ovos e 500 g de açúcar, enquanto para a sacripantina são necessários 8 ovos e 800 g de açúcar. Os respectivos preços de venda são $ 8 e $ 10.

O problema é: quantos bolos de cada tipo a padaria deve fazer para maximizar seu lucro, sabendo que tem 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 assumem valores reais:

-x: o número de bolos da floresta negra

-y: bolos do tipo sacripantina.

Restrições

As restrições se dão pelo fato de o número de bolos ser uma quantidade positiva e as quantidades de matéria-prima para prepará-los são limitadas.

Portanto, na forma matemática, 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 o condição de não negatividade exposto anteriormente, e todas as desigualdades levantadas são lineares. Nas restrições 3 e 4 encontram-se os valores que não devem ser ultrapassados: 144 ovos e 10 kg de açúcar.

Função objetiva

Finalmente, a função objetivo é o lucro obtido na fabricação da quantidade “x” de bolos da floresta negra mais a quantidade “y” de sacripantinos. Ele é feito multiplicando o preço pela quantidade de bolos feitos e somando 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 de pontos interiores, 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, ligar região viável ou região de viabilidade.

Esta região é construída através de linhas de restrição, que são as retas obtidas a partir das desigualdades das restrições, trabalhando apenas com o sinal de igualdade.

No caso da padaria que deseja otimizar os 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 delimitada por essas linhas são soluções possíveis, portanto, há um número infinito deles. Exceto no caso em que a região viável acaba sendo vazia, caso em que o problema colocado 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 ótima, se existir, é encontrada com a ajuda da função objetivo. Por exemplo, ao tentar encontrar o ganho máximo G, temos a seguinte linha, que é chamada linha iso-profit:

G = k1x + k2y → y = -k1x / k2 + G / k2

Com esta reta obtemos todos os pares (x, y) que fornecem um dado ganho G, então existe uma família de retas de acordo com o valor de G, mas todas com a mesma inclinação -k1 / k2, de modo que sejam linhas paralelas.

A solução ótima

Agora, pode-se mostrar que a solução ótima de um problema linear é sempre um ponto extremo ou vértice da região viável. Então:

A linha de solução é a que está mais longe 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 de iso-lucro for igual a 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 para duas variáveis. No entanto, é mais complicado quando há três variáveis ​​e impossível de usar para um número maior de variáveis.

Ao lidar com problemas com mais de duas variáveis, o método simplex, que consiste em uma série de algoritmos para otimizar as funções objetivo. Matrizes e aritmética simples são freqüentemente usadas para realizar os cálculos.

O método simplex começa escolhendo uma solução viável e verificando se ela é ótima. Se for, já resolvemos o problema, mas se não estiver, seguimos em direção a uma solução mais próxima da otimização. Se a solução existe, o algoritmo a encontra 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 se busca minimizar o tempo necessário para realizar uma série de operações.

Aqui estão alguns campos:

-No marketing é utilizado para encontrar a melhor combinação de meios de comunicação (redes sociais, televisão, imprensa e outros) para publicitar um determinado produto.

-Para a atribuição de tarefas adequadas ao pessoal de uma empresa ou fábrica ou horários a eles.

-Na seleção dos alimentos mais nutritivos e com o menor custo na pecuária e avicultura.

Exercícios resolvidos

- Exercício 1

Resolva graficamente o modelo de programação linear levantado nas seções anteriores.

Solução

É necessário representar graficamente o conjunto de valores determinados pelo sistema de restrições 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 inequações 1 e 2 corresponde ao primeiro quadrante do plano cartesiano. Com relação às desigualdades 3 e 4, começamos encontrando as linhas de restrição:

9x + 8y = 144

0,5 x + 0,8y = 10 → 5x + 8y = 100

A região viável é um quadrilátero cujos vértices são os pontos A, B, C e D.

O lucro mínimo é 0, portanto, a linha 8x + 10y = 0 é o limite inferior e as linhas de iso-lucro têm inclinação -8/10 = - 0,8.

Este valor é diferente das inclinações das outras linhas de restrição e, como a região viável é limitada, existe a solução única.

Esta solução corresponde a uma reta de inclinação -0,8 que passa por qualquer um dos pontos A, B ou C, cujas coordenadas são:

A (11; 5,625)

B (0; 12,5)

C (16, 0)

Solução ótima

Calculamos o valor de G para cada um desses pontos:

- (11; 5,625): GPARA = 8 x 11 + 10 x 5,625 = 144,25

- (0; 12,5): GB = 8 x 0 + 10 x 12,5 = 125

- (16, 0): GC = 8 x 16 + 10 x 0 = 128

O lucro mais alto é obtido fabricando 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 LibreOffice Calc, que incorporam o algoritmo Simplex para otimização na programação linear.

Solução

Referências

  1. Brilhante. Programação linear. Recuperado de: brilhante.org.
  2. Eppen, G. 2000. Pesquisa Operacional em Ciências Administrativas. 5 ª. Edição. Prentice Hall.
  3. Haeussler, E. 1992. Mathematics for Management and Economics. 2ª Edição. Grupo Editorial Iberoamericana.
  4. Hiru.eus. Programação linear. Recuperado de: hiru.eus.
  5. Wikipedia. Programação linear. Recuperado de: es. wikipedia.org.