Os Modelos De Programação Linear, Para Serem Devidamente Solucionados Por Intermédio Do Algoritmo Simplex Que Será Apresentado, Devem Apresentar O Seguinte Formato Padrão: • A Função Objetivo De Maximização (opcional); • Todas As Variáveis D

Os modelos de programação linear, para serem devidamente solucionados por intermédio do algoritmo simplex que será apresentado, devem apresentar o seguinte formato padrão:

• A função objetivo de maximização (opcional);

• Todas as variáveis de decisão não-negativas;

• Constantes do lado direito não-negativas;

• Restrições de igualdade.

Caso isso não aconteça, deve-se procurar um modelo equivalente que possua essas características, para então usar o simplex.

a) Função Objetivo de Minimização

A minimização de uma função f(x) é matematicamente análoga à maximização da negativa desta função (-f(x)).

Exemplo: MIN z=c1x1+ c2x2+...+ cnxn

É equivalente a:

MAX Z = -c1x1- c2x2-...-cnxn

Com z = -Z

Dessa forma: MIN z = -MAX(-Z)

Essa é uma das formas de resolver os problemas de minimização utilizando o mesmo algoritmo dos problemas de maximização. Caso se queira resolver diretamente, devemos alterar o critério de entrada das variáveis na base.

b) Problema da Variável Livre

Entende-se por variável livre as variáveis sem qualquer restrição de sinal, isto é, podem assumir valores positivos, negativos ou zero. Para contornarmos este problema, devemos lembrar que um número qualquer sempre pode ser escrito como a diferença de dois números positivos.

Exemplo: MAX z = x1+2x2+x3

SA x1+x2+x310

2x1+3x220

x1 0 , x2 livre , x3 0

Fazendo x2 = x'2 - x''2, com x'2 0 e x''2 0 e substituindo no modelo anterior, tem-se o modelo equivalente:

MAX z = x1+2(x'2 - x''2)+x3

SA x1+ x'2 - x''2+x310

2x1+3(x'2 - x''2)20

x1 0 , x'2 0, x''2 0, x3 0

Onde todas as variáveis são não-negativas. A solução deste modelo, resolve o anterior.

c) Ocorrência de bi<0

Basta multiplicarmos a restrição i por (-1) pois os coeficientes aij podem ter qualquer sinal.

d) Transformação de Desigualdades em Igualdades

Para a utilização do algoritmo simplex é necessário que todas as desigualdades do conjunto de restrições sejam transformadas em igualdade e que se conheça uma solução inicial viável, não- negativa. Na forma padrão, apenas as restrições de não-negatividade (das variáveis) são desigualdades.

 Variáveis de Folga e Excesso

Outras restrições de desigualdade são transformadas em equações por meio de variáveis de folga ou de excesso (muitas vezes se fala em variáveis de folga mesmo quando se trata de variáveis de excesso) que são sempre não-negativas.

ai1x1 + .... + ainxn  bi  ai1x1 + .... + ainxn + si = bi

si  0 (folga)

ou

ai1x1 + .... + ainxn  bi  ai1x1 + .... + ainxn - si = bi

si  0 (excesso)

A variável de folga é numericamente igual a diferença entre os valores à direita e à esquerda da desigualdade e representa o desperdício acarretado pela parte do sistema modelada pela restrição em pauta.

A