Pular para o conteúdo
21 de junho de 2011 / lucastdcj

Programação Linear – Simplex

Programação Linear

Um problema de programação linear consiste em uma função objetivo, que é maximizar ou minimizar algo, sendo que as variáveis estão sujeitas a restrições.

Forma Padrão

A cara de um problema de programação linear é:

Maximizar: c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}

Sujeito a: \left\{\begin{matrix} a_{1,1}x_{1}+a_{1,2}x_{2} +...+ a_{1,n}x_{n} \leq b_{1} \\ a_{2,1}x_{1} + a_{2,2}x_{2}+...+a_{2,n}x_{n} \leq b_{2} \\ ... \\ a_{m,1}x_{1}+a_{m,2}x_{2} +...+ a_{m,n}x_{n} \leq b_{m} \end{matrix}\right.

Para simplificar o estudo de um algoritmo que se aplique a resolução de problemas de Programação Linear, definimos uma forma Padrão. Ou seja, a função objetivo tem o objetivo de maximizar, as desigualdades tem sinal de menor ou igual e as variáveis tem a condição de serem maiores ou iguais a zero.

Mas raramente os problemas obedecem todas essas restrições. Podemos ter como objetivo minimizar uma função linear, podemos ter uma variável podendo ser negativa, podemos ter que as desigualdades tenham sinal de maior ou igual ou ainda podemos ter relações de igualde.Porém, para cada um desses casos conseguimos transformar na forma padrão, é o que veremos a seguir:

Transformando na Forma Padrão

Primeiramente irei escrever como que faz, teoricamente, em cada caso e depois darei um exemplo utilizando todas as transformações. Caso não entenda lendo as explicações teóricas, veja como se aplica no exemplo.

  • Problemas de minimização

Para converter um problema cuja função objetivo é minimizar em um que é maximizar, basta trocar o sinal dos coeficientes da função objetivo. Uma vez que quanto menor for c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}, maior será: -c_{1}x_{1}-c_{2}x_{2}-...-c_{n}x_{n}.Ou seja, ao minimizarmos a primeira equação, estaremos maximizando a segunda.

  • Variáveis negativas

Caso tenhamos uma varíavel sem a restrição de não-negativadade, expressamos essa variável como subtração de duas variáveis e substiuimos em todas as relações em que aparece essa variável. Ou seja, se tivermos uma variavel x podendo ser negativa, expressamos ela como x = x’ – x”. Onde x’ e x” são não-negativos, podemos fazer isso, pois um número negativo pode ser expresso como subtração de números não-negativos. É importante observar, que devemos substituir x por x’ – x” em todas as relações.

  • Relações com sinal de maior ou igual

Caso tenhamos uma relação da forma: a_{k,1}x_{1}+a_{k,2}x_{2}+...+a_{k,n}x_{n} \geq b_{k}, basta mudarmos o sinal de todos os coeficientes, ficando: -a_{k,1}x_{1}-a_{k,2}x_{2}-...-a_{k,n}x_{n} \leq -b_{k}. Atendendo assim a exigência da forma padrão.

  • Relações de igualdade

É fácil observar de igualdade: a_{k,1}x_{1}+a_{k,2}x_{2}+...+a_{k,n}x_{n} = b_{k} é atendida quando obedecer duas relações ao mesmo tempo:a_{k,1}x_{1}+a_{k,2}x_{2}+...+a_{k,n}x_{n} \leq b_{k} e a_{k,1}x_{1}+a_{k,2}x_{2}+...+a_{k,n}x_{n} \geq b_{k}. E essa segunda equação com relação de maioridade utilizamos o que foi explicado no item anterior.

Exemplo

Como exemplo, vamos utilizar o exercício (29.1-4) de [1], modificado.

Converta o seguinte programa linear para a forma padrão:

Minimizar: 2x_{1}+7x_{2}

Sujeito a: \left\{\begin{matrix} x_{1} = 7 \\ 3x_{1}+x_{2} \geq 24 \\ x_{2} \geq 0 \end{matrix}\right.

Primeiramente transformamos o problema de minimização em maximização:

Maximizar: -2x_{1}-7x_{2}

Sujeito a: \left\{\begin{matrix} x_{1} = 7 \\ 3x_{1}+x_{2} \geq 24 \\ x_{2} \geq 0 \end{matrix}\right.

Como x_{1} pode ser negativo, devemos transformar como subtração de duas variáveis: x_{1} = x_{1}' - x_{1}''.

Maximizar: -2x_{1}' + 2x_{1}''-7x_{2}

Sujeito a: \left\{\begin{matrix} x_{1}' - x_{1}'' = 7 \\ 3x_{1}' -3x_{1}'' +x_{2} \geq 24 \\ x_{1}',x_{1}'',x_{2} \geq 0 \end{matrix}\right.

Como temos na segunda equação um desigualdade de maior ou igual, devemos transformá-la numa desigualdade de menor ou igual.

Maximizar: -2x_{1}' + 2x_{1}''-7x_{2}

Sujeito a: \left\{\begin{matrix} x_{1}' - x_{1}'' = 7 \\ -3x_{1}' +3x_{1}'' -x_{2} \leq -24 \\ x_{1}',x_{1}'',x_{2} \geq 0 \end{matrix}\right.

Por útlimo, modificamos a relação de igualdade em duas desigualdades

Maximizar: -2x_{1}' + 2x_{1}''-7x_{2}

Sujeito a: \left\{\begin{matrix} x_{1}' - x_{1}'' \leq 7 \\ -x_{1}' + x_{1}'' \leq -7 \\ -3x_{1}' +3x_{1}'' -x_{2} \leq -24 \\ x_{1}',x_{1}'',x_{2} \geq 0 \end{matrix}\right.

Forma Relaxada

Estando o problema modelado na forma Padrão, devemos passá-lo para a Forma Relaxada, para podermos utilizar o algoritmo Simplex, para isso utilizamos variável de folga:

Variável de folga

Dada a desigualdade: a_{1}.x_{1}+a_{2}.x_{2}+...+a_{m}.x_{m} \leq b, definimos a variável de folga (y) como a diferença entre o maior e o menor lado: y = b - a_{1}.x_{1}-a_{2}.x_{2}-...-a_{m}.x_{m}.

Forma relaxada

Agora para chegarmos na forma relaxada devemos criar uma variável de folga para cada desigualdade que temos na forma padrão e definimos uma variável z sendo igual a função objetivo. Utilizando este conceito no exemplo anterior, temos:

Maximizar: z = -2x_{1}' + 2x_{1}''-7x_{2}

Sujeito a: \left\{\begin{matrix} x_{3} = 7 - x_{1}' + x_{1}'' \\ x_{4} = -7 +x_{1}' - x_{1}'' \\ x_{5} = -24 +3x_{1}' -3x_{1}'' +x_{2} \end{matrix}\right.

http://latex.codecogs.com/gif.latex?x_{1}=&space;x_{1}’&space;-&space;x_{1}”
About these ads

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

Seguir

Obtenha todo post novo entregue na sua caixa de entrada.

%d blogueiros gostam disto: