IO

Bases teóricas do método Simplex

III.

Bases Teóricas do Método do Simplex
Em variados domínios de aplicação há modelos matemáticos com a seguinte estrutura:
•

um conjunto de "n" variáveis x1 , x2 , ... , xn

•

um conjunto de "m" condições lineares (m<n) relacionando as variáveis por meio de desigualdades do tipo a11 x1 + a12x2 + ... + a1n xn ≤ b1

•

uma função linear f(X) = c1 x1 + c2 x2 + ... + cn xn da qual se pretende determinar o Máximo ou
Mínimo

•

a condição de não negatividade das variáveis x1 ≥ 0 , x2 ≥ 0 , ... , xn ≥ o

Este tipo de modelo, denominado Modelo de Programação Linear, pode ser generalizado relativamente ao sentido das desigualdades e ao domínio das variáveis.
O matemático americano George Dantzig, em 1947, estabeleceu uma forma sistemática de resolução do modelo de programação linear recorrendo à teoria das equações lineares, ao conceito de independência de vectores e à álgebra matricial. Neste capítulo são abordados os aspectos essenciais para compreender o
Método do Simplex.
1. Modelo de Programação Linear
Admita-se uma empresa que pretende Optimizar o plano de produção dos bens A e B na situação seguinte:
Recursos críticos disponíveis:

Consumos unitários previstos:

Madeira
Horas de trabalho
Produto
A
B

Lucro unitário da venda (u.m.)

300 metros
110 horas

Madeira (metros)
30
20

A
6

Horas de Trabalho (h)
5
10

B
8

O Modelo Matemático para Optimizar a Produção de A e B é o seguinte:
Max f(X) = 6x1 + 8x2 sujeito a:

30x1

+

20x2

≤

300

5x1

+

10x2

≤

110

x1 , x2

≥

0

em que:
•

as variáveis x1 e x2 representam respectivamente os níveis de produção de A e B;

•

as relações de tipo “≤” garantem que os consumos de madeira e horas de trabalho não ultrapassam as disponibilidades existentes;

•

a função linear f(x1 , x2 ) representa o lucro que se pretende maximizar;

•

as variáveis só podem tomar valores não negativos;

INVESTIGAÇÃO OPERACIONAL (MS – edição de 2006)

III-1

Bases teóricas do método Simplex

2. Sistemas de