Como Resolver Problemas de Programação Linear Usando Simplex

A fim de descobrir a maior quantidade de dinheiro que você poderia fazer sujeita a algumas restrições, você pode usar o método simplex. Originalmente descoberto por um engenheiro da Força Aérea, George B. Dantzig , em 1947 , o método simplex é um método de programação linear que maximiza (ou minimiza ) uma função sujeita a restrições na forma de desigualdades lineares. Geometricamente, as desigualdades formar uma região poligonal. O método simplex tenta todos os vértices da região até encontrar aquele que faz a função de assumir o maior valor. Instruções

1

Determinar se o problema é um problema de maximização padrão. Nestes tipos de problemas, as seguintes condições devem ser satisfeitas: A função deve ser maximizada , as constantes nas desigualdades devem todos ser não- negativo , as variáveis ​​devem ser todos não- negativo e as desigualdades devem todos ser menor ou igual a . Por exemplo , o seguinte é um problema de maximização padrão :

Maximize F = 5x + 6y sujeito às restrições

4x + 2y

3x + y

x + 2y

onde x e y são ambos não -negativos

2

Converta cada desigualdade em uma igualdade , acrescentando . uma variável de folga para cada desigualdade. Por exemplo, após a adição de variáveis ​​de folga , as desigualdades se tornam :

4x + 2y + u = 10

3x + y + v = 5

x + 2y + w = 8

3

Assegurar todas as equações , incluindo a função , tem as variáveis ​​do lado esquerdo e as constantes na direita. Por exemplo , no exemplo todas as equações já tem a forma correta , exceto para a função. Reescreva a função , como indicado :

-5x – 6y + F = 0

4

Converter o sistema de equações em uma matriz chamada de tableau simplex inicial. Cada linha da matriz corresponde aos coeficientes das equações . Coloque os números da função na linha de fundo. Por exemplo, o quadro simplex inicial do exemplo é :

xyuvw F

4 2 1 0 0 0 10

3 1 0 1 0 0 5

1 2 0 0 1 0 8

-5 -6 0 0 0 -1 0

5

Encontre o indicador mais negativo no quadro simplex inicial. Os “indicadores ” são os números na parte inferior (exceto para o mais baixo número). No exemplo , o indicador mais negativo é -6 na segunda coluna . Esta coluna é chamada de coluna pivô.

6

Encontre o menor proporção na coluna pivô. Relações formulário tomar mais à direita número em cada linha e dividindo por um número correspondente na coluna pivô . Faça isso para cada linha, exceto a linha indicadora. Por exemplo , as proporções no exemplo são :

10/2 = 5

5/1 = 5

8/2 = 4

A menor proporção na coluna pivô é 4 , que corresponde à terceira fileira .

7

usar operações de linha de matriz de alterar todos os outros números na coluna pivô para 0 . Por exemplo , subtrair a primeira linha pela linha de articulação , para formar um 0 na primeira fileira . Subtrair o dobro da segunda linha para a linha de articulação , para formar um 0 na segunda fila . O resultado é mostrado abaixo :

xyuvw F

3 0 1 0 0 2 -1

5 0 0 2 -1 0 2

1 2 0 0 1 0 8

-8 0 0 0 -3 -1

-24

8

Verifique se todos os indicadores são não- negativo. Se sim, então você está feito. Caso contrário, vá para a Etapa 5 .

9

Ler a solução a partir da matriz final. Por exemplo , se a matriz final, é

xyuvw F

1 0 0 3 4 0 4

0 3 0 4 0 4 6 0 0

2 4 3 0 4

0 0 0 3 3 1 5

olhar para as colunas com um único número não- zero. Esta coluna dá-lhe o valor dessa variável na solução. Para encontrar o valor , divida o mais à direita número pelo número diferente de zero . Nesta matriz final , a solução é :

x = 4/1 ou 4

y = 6/3 ou 2

u = 4/2 ou 2

eo valor máximo da função F é 5.