3.2. Modelos matemáticos

Neste item optou-se primeiramente em demonstrar de modo geral o que é a programação linear e sua utilidade na resolução de problemas de localização. Após esta abordagem geral foi apresentado o modelo PLIM utilizado neste trabalho.

Os modelos matemáticos já são utilizados por diversas áreas do conhecimento para resolver questões do cotidiano. Essa análise para tomada de decisões na teoria da localização é importante pelo seu impacto social e econômico, para tanto é necessário um algoritmo de otimização.

3.2.1. Introdução à Programação Linear e sua utilização

Sabe-se que na matemática, uma variável é uma letra do alfabeto que pode assumir diversos valores, quando estes valores são números inteiros, têm-se uma variável discreta, e quando os valores da variável são números reais têm-se uma variável contínua.

Segundo Meza (1988), os dados utilizados na solução e qualquer problema matemático podem ser dados discretos ou contínuos. Uma expressão algébrica da forma

onde os são constantes e os são variáveis para i = 1, 2, 3, . . . , n, é chamada de expressão algébrica linear.

Quando y for uma constante e n = 2, sua representação geométrica é uma reta. Quando n = 3 sua representação é um plano e quando n ≥ 4 sua representação é um hiperplano. Um conjunto de expressões algébricas lineares da mesma natureza com um mesmo número de variáveis determina um sistema de equações lineares. Segundo Teofiloff (2005), um problema da álgebra linear é o da inversão das operações de multiplicação na procura da solução de um sistema de equações lineares.

A Programação Linear (PL) é um ramo da matemática que estuda formas de resolver problemas de otimização cujas condições podem se expressar por inequações lineares, isto é, inequações do primeiro grau. Um problema de Programação Linear que tenha só duas variáveis pode ser resolvido graficamente, representado as soluções de cada uma das inequações, por um semiplano, e procurando o ponto do polígono obtido que mostra a solução ótima. Para resolver problemas de PL se procura a melhor solução (a que dá menor prejuízo, mais lucro, a que é mais eficiente, etc.). Alguns destes problemas resolvem-se procurando máximos ou mínimos de uma função, para resolver seus outros processos.

Segundo Sousa (2005), os principais desenvolvimentos teóricos da programação linear são devidos ao russo L. V. Kantorovich quem deu os primeiros passos na programação linear, em 1939, ao resolver problemas relacionados com a otimização de recursos das organizações. Kantorovich utilizou um algoritmo primitivo de programação linear para aplicação ao planejamento da produção, visava obter maior produção/lucro possível com base na utilização ótima dos recursos disponíveis. No entanto, o trabalho de Kantorovich foi desconhecido durante vinte anos, não tendo tido impacto no desenvolvimento da programação linear após a segunda guerra.

Em 1949, na época áurea, em que se utilizava, a Programação Linear, foi quando George. B. Dantzig inventou e incrementou o Método Simplex, como forma de solucionar problemas de otimização relacionados com questões de logística até de estratégia para o exército americano na segunda guerra mundial. Após a guerra a (PL) foi impulsionada para encontrar formas eficientes de desenvolver esta metodologia. Dantzig foi o primeiro a reconhecer que um programa de planejamento poderia ser expresso por um sistema de inequações lineares assim como foi o primeiro a apresentar, na forma de uma expressão matemática explícita, um critério para seleção do melhor plano ao que hoje chamamos função objetivo.

Segundo Caixeta-Filho (2004) a Programação Linear (PL) é um aprimoramento de uma técnica de resolução do sistema de equações lineares via inversões sucessivas de matrizes, com a vantagem de incorporar uma equação linear adicional representativa de um dado comportamento que deva ser otimizado. O objetivo geral da Programação Linear é otimizar (maximizar ou minimizar) uma função linear de várias variáveis, chamada de "função objetivo", sujeita a uma série de equações ou inequações lineares, chamadas “restrições”.

Um problema de Programação Linear Inteira (PLI) é um problema de Programação Linear (PL) no quais todas ou alguma(s) de suas variáveis são discretas, geralmente estas variáveis são do tipo sim-ou-não, estes problemas são casos particulares de problemas de otimização.

Quando todas as variáveis estão sujeitas à condição de integralidade estamos perante um problema de Programação Linear Inteira Pura (PLIP). Porém, se apenas algumas o estão, trata-se de um problema de Programação Linear Inteira Mista (PLIM). Embora a Programação Inteira (PI) inclua também a Programação Não-Linear Inteira, em praticamente todos os modelos da vida real se preserva a estrutura linear das funções, pelo que quase não existe diferença entre a PI e a PLI (GOLDBARG, 1994).

Os modelos de PLI serão então do tipo dos modelos de PL, sujeitos às restrições adicionais lineares, indicando que algumas ou todas as variáveis são discretas, conforme se pode ver no exemplo seguinte:

(PI) max Z =

sujeito as restrições

, ≥ 0 e são variáveis discretas

Aqui, a função objetivo é do tipo z = f(x1, x2) = , que no espaço tridimensional representa uma superfície plana pontilhada, pois as variáveis são somente números inteiros. As restrições , e , ≥ 0 que também são de números inteiros são limitações para analisar o problema somente numa região limitada e poder assim obter o máximo valor desejado.

O correspondente problema de PL (relaxação do PI, dado que se “estende” o domínio das variáveis de decisão de discreta para contínua) é:

(PL) max Z =

sujeito as restrições

, ≥ 0 são variáveis contínuas.

Neste caso é o mesmo problema anterior, porém as variáveis são todas em números reais, z = f(x1, x2) = , no espaço tridimensional representa uma superfície plana sólida,

Existe um caso especial de variáveis inteiras: as variáveis binárias que apenas podem tomar os valores 0 (zero) ou 1 (um). Quando todas as variáveis de um modelo são binárias, o modelo diz-se de Programação Inteira Binária. As variáveis binárias são muito úteis para expressarem situações dicotômicas (sim-ou-não, fazer ou não fazer, etc.).

A formulação do problema a ser resolvido por programação linear segue alguns passos básicos.

• O objetivo básico do problema em estudo deve ser bem definido, ou seja, a otimização a ser alcançada. Tal objetivo será representado por uma função objetivo (modelo matemático) , a ser maximizada ou minimizada;

• Para que esta função objetivo seja matematicamente especificada, devem ser definidas as variáveis de decisão envolvidas. Normalmente, impões-se que todas estas variáveis possam assumir somente valores positivos;

• As variáveis normalmente estão sujeitas a uma série de restrições, normalmente representadas por inequações.