PROGRAMAÇÃO LINEAR: PARA QUE SERVE, MODELOS, RESTRIÇÕES, APLICATIVOS - MATEMÁTICAS - 2025

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 maquinário são limitados.

Figura 1. A programação linear é amplamente usada para otimizar os lucros. Fonte: Piqsels.

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

Com k ₁ e k ₂ constantes. Essa função é conhecida como função objetivo. Claro, existem situações que merecem mais de duas variáveis ​​de estudo, sendo mais complexas:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

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

O conjunto de soluções neste 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 é ideia de Dantzig, que trabalhou para a Força Aérea dos Estados Unidos, a Universidade de Berkeley e a Universidade de Stanford.

Figura 2. Matemáticos George Dantzig (esquerda) e Leonid Kantorovich (direita). Fonte: F. Zapata.

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. Em seguida, 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 = ∑k _i x _i

Nessa equação, k _i são coeficientes e x _i 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 um número M de limitações, começando de j = 1 a 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 ≤ ∑ c _ij. x _i

A primeira restrição é do tipo 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 isso significa que os valores conhecidos B _j e C _j podem ser respeitados ou excedidos, quando o símbolo que aparece for ≥ (maior ou igual a) ou respeitado ou não ultrapassado, se o símbolo for ≤ (menos que 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.

Na sua preparação requerem ovos e açúcar. 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 são dadas 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 a condição de não negatividade previamente exposta, 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

As várias metodologias de solução incluem 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, chamada de região viável ou região de viabilidade.

Figura 3. A região viável, onde se encontra a solução do problema de otimização. Fonte: Wikimedia Commons.

Essa região é construída a partir das linhas de restrição, que são as linhas 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 é vazia, temos abaixo.

Figura 4. A região viável do problema da pastelaria. A linha com ganho 0 cruza a origem. Fonte: F. Zapata com Geogebra.

A solução ótima, se existir, é encontrada com a ajuda da função objetivo. Por exemplo, ao tentar encontrar o lucro máximo G, temos a seguinte linha, que é chamada de linha iso-lucro:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

Com esta reta obtemos todos os pares (x, y) que fornecem um dado ganho G, então há uma família de retas de acordo com o valor de G, mas todas com a mesma inclinação -k ₁ / k ₂, então elas são 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. Assim:

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-lucro 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 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.

Quando se trata de problemas com mais de duas variáveis, é utilizado 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, 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 você quiser 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 (redes sociais, televisão, imprensa e outros) para anunciar 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.

Figura 5. Solução gráfica do exercício 1, mostrando a região viável e o ponto de solução C em um dos vértices dessa região. Fonte: F. Zapata.

Esta solução corresponde a uma linha 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): L _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 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

Figura 6. Detalhe da solução do exercício 1 por meio da planilha Libre Office Calc. Fonte: F. Zapata.

Figura 7. Detalhe da solução do exercício 1 por meio da planilha Libre Office Calc. Fonte: F. Zapata.

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.