Problemas de Programao Linear

Um fabricante produz dois tipos de ao: normal e especial. Uma tonelada de ao normal
requer 2 horas de forno de soleira aberta e 5 horas de molho, uma tonelada de ao especial
requer 2 horas de forno de soleira aberta e 3 horas de molho o forno de soleira aberta est
disponvel 8 horas por dia e o molho est disponvel 15 horas por dia. O lucro em uma
tonelada de ao normal de $120 e de $100 em uma tonelada de ao especial. Determine
quantas toneladas de cada tipo de ao devero ser produzidas para maximizar o lucro.
Como Resolver os problemas de programao linear:
OBS.: Separar os dados em um quadro para entender o que o que (Ex.: Valores com valores,
tido de ao com tipo de ao, tempo com tempo como no ex. acima.)
Forno Soleira
Molho/tonelada Lucro/tonelada
Aberta/tonelada
Ao Normal (x)
Ao Especial (y)
Tempo Disponvel

2
2
8

5
3
15

$120
$100

Ao montar o quadro perceba que tudo que de ao normal est em uma linha, ou seja seu
processo inteiro de fabricao o tempo que ele leva no forno de soleira aberta, o tempo que
leva no molho e o lucro que ele tem naquele tempo de produo.
O mesmo processo descrito acima feito para o ao especial. No entanto o tempo que ambos
podem ficar no forno e molho tem uma restrio e quando h restrio ela representada por
< ou > neste caso < j que o forno e o molho esto disponveis at 8 horas e at 15 horas. Pois
se o texto diz forno de soleira aberta est disponvel 8 horas por dia significa que h um
limite e no pode passar de 8 horas, assim a mesma interpretao feita para disponvel 15
horas... pura questo de interpretao de texto, mas isso deixa para a aula de portugus que
j deveria ter aprendido.
Resolvendo o problema aps identificar os valores:
1 Montar a Estrutura de condio com o MAXIMIZE sempre com <:

Maximize z= QUEM?
Veja que todo e qualquer maximizar e at minimizar que aprendemos Valores como lucro,
pessoas (como telespectadores), produtos etc. Todos sempre visando o lucro. Portanto...
Maximize z= Lucro... que a soma dos valores da produo total neste caso.

Maximize Z= 120x+100y
Sujeito

2x+2y < 8
5x+3y < 15
X> 0
Y>0

2 Calcular valores para cada equao quando variar x e y:

2x+2y < 8
X
0
4

5x+3y < 15

Y
4
0

X
0
3

Y
5
0

Assim para a equao 2x+2y < 8 temos (0,4) e (4,0), para a equao 5x+3y < 15 temos (0,5) e
(3,0). Com tais valores possvel montar o grfico.
6
5
4
2x+2y = 8 => (0,4),(4,0)

5x+3y = 15 => (0,5),(3,0)

2
1
0
0

Lembre-se de pintar a parte que satisfaz no grfico. Se ambas as equaes so < ento ambas
as linhas so traadas cheias e no pontilhadas pois todos os pontos por onde ela passa so
satisfatrios e fazendo o teste com x e y = 0 nas equaes todos os resultados so verdadeiros
ento tudo em direo ao eixo 0 verdade, ou seja, se na equao 2x+2y < 8 x=0 e y=0 ento
teremos 0+0 < 8, o que verdade j que 0 menor que 8.
Veja que o grfico mostra um cruzamento entre as duas linhas (equaes), lembre-se que cada
equao representa uma linha no grfico.
3 Calculando o ponto de cruzamento:
Devemos identificar as linhas que se cruzam, assim sabemos quais as equaes calcularemos
para achar os valores de X,Y.
Neste caso temos:

2x+2y = 8
5x+3y = 15
Assim devemos achar um meio de zerar uma das incgnitas a fim de encontrar o valor de outra
podemos somar os valores das equaes ou subtrair para encontrar X, Y. Mas se no for
possvel zerar nenhum poderemos multiplicar as linhas para que satisfaa nossa condio.
2x+2y = 8
5x+3y = 15

*(-3)
*(2)

Teremos:
-6x - 6y = -24
10x+6y = 30
4x
= 6
Ento: 4x=6
X= 6:2
4:2
X= 3
2
Se X= 3 podemos substituir tal valor em uma das equaes que montamos acima.
4
2x+2y = 8
2* 3 + 2y =8
=>
6 + 2y =8
=>
3+2y=8
2
2
Portanto achamos o Ponto de Cruzamento (X,Y) = 3 , 5
2 2

=> y = 8-3
2

=>

5
2

4 Achar o ponto que satisfaz a Maximizao, ou seja onde o valor maior... assim o lucro ser
maior:
Substituir todos os valores achados de x e y na frmula (equao ou reta) de Z
Z = 120x + 100y
(0,0) = 0
(0,4) = 400
3 , 5 = 430
2 2
(3,0) = 360
Crie vergonha na cara, eu no vou ficar colocando o Z com x e y substitudo por cada valor
acima. J basta o resultado.

Assim: Resposta: Para Maximizar o Lucro em $430 devero ser produzidas 3/2 toneladas de
ao normal e 5/2 toneladas de ao especial.
E isso.... Mas cuidado com os problemas com um monte de condio... isso significa que ter
muitos <= ou >=. Tambm h aqueles em que vai dizer que A vale tanto e B vale tanto, mas
B no pode ser maior que a metade de A ento interprete como se A=10 B= 4 com a condio
que B < A/2. Pay Attention

Resolvendo Problemas de DUALIDADE.

Montar o Dual montar o inverso do problema original.
Onde:
Z passa a ser Resultados
As linhas ou equaes so dispostas em colunas
Resultados passam a ser Z
Usar variveis de folga para cada equao (linha)
1 Alterando colunas para linhas e linhas para colunas.
Resolva: Minimize Z = 30y1 +40y2
Sujeito

2y1 + y2 > 12
y1 + y2 > 9
y1 + 3y2 > 15
y1 >0 e y2>0
H um motivo pra tudo isso estar carnavalescamente gay, pois cada uma dessas cores
corresponde inversamente abaixo:
Montando temos:
Maximize Z = 12x1+9x2+15x3
Sujeito
2x1+x2+x3 < 30
x1+x2+3x3 < 40
x1>0 , x2>0, x3>0
Veja que usamos outra letra para incgnitas, sempre use uma diferente do problema original.
2 Usando o problema de maximize colocando variveis de folga:
Para cada linha adicione 1 varivel de folga (ex.: u,v,w,p...etc.)
Montando temos:
Maximize Z = 12x1+9x2+15x3
Sujeito

2x1+x2+x3+u = 30
x1+x2+3x3+v = 40
x1>0 , x2>0, x3>0, u>0, v>0

No esquea nunca de declarar as variveis iguais ou maiores que zero. E a partir daqui s
trabalhe com a igualdade.

A parte de Dualidade est pronta agora continua a resoluo do problema com o Mtodo
Simplex, rebatizado por mim pelo mtodo Jontex e voc sabe porque; pra foder todo
mundo
Mtodo Simplex:
1 dispor todo o problema de Dualidade com as variveis de folga em um quadro:
x1
2
1
-12

x2
1
1
-9

x3
1
3
-15

u
1
0
0

v
0
1
0

z
0
0
1

30
40
0

Ultima linha encontrada com Z igualado a 0.

Se Z = 12x1+9x2+15x3
Ento : -12x1-9x2-15x3+Z = 0 assim esse zero o que est logo abaixo do valor 40.

2 Resolvendo o Jontex:
1 Verificamos na ultima linha qual o menor valor negativo, ou seja, -15. Faremos assim uma
avaliao com a coluna em que se encontra o valor -15 sendo divisora dos valores que
compem o resultado.
x1

x2

x3

30

40

-12

-9

-15

Assim dividimos o resultado pelos valores correspondentes a linha deles e a coluna do -15;
30/1 = 30 e 40/3 = 13,333...
Portanto o valor que nos interessa o 3 j que a sua diviso apresentou menor valor.
Lembre-se s considere os menores valores POSITIVOS nunca os negativos.... Tambm que o u e v
que se encontra na frente do quadro pra identificar com quem estamos trabalhando neste
momento.
2 Dividir a linha inteira pelo valor 3 pois a inteno que onde est o valor pelo qual
dividimos o 40 fique o nosso PIVO 1. Lembrando que a funo do Jontex ou a sua finalidade
que os valores de z ou da ultima linha fiquem positivos.
u
v

x1

x2

x3

30

1/3

1/3

40/ 3

-12

-9

-15

3 Usar o PIVO que achamos para zerar as variveis acima e abaixo dele.
x1

x2

x3

*(-1) u

30

1/3
1/3
0
1
0
40/ 3
1
x3
*15
-12
-9
-15
0
0
1
0
Observe que o X3 entrou e o V saiu... mas isso no nos interessa tanto neste momento... quem
sai ou quem entra se o quadro for montado e calculado corretamente.
Essa parte de escolher que nmero multiplicaremos a linha j deveramos ter criado vergonha
na cara e saber fazer. Mas vamos l..
Usaremos a linha do PIVO para multiplicar por um valor qualquer que somado ou subtrado
pelos valores das outras linhas poderemos zerar os valores acima do piv e abaixo dele. Sendo
assim multiplicaremos todos os valores da linha do piv por -1 para podermos somar ou
subtrair os valores da linha acima afim de zerar o valor 1 de X2. Tambm multiplicaremos em
outro momento todos os valores da linha do piv por 15 para podermos somar ou subtrair os
valores da linha Abaixo afim de zerar o valor -15 de X2.
Veja:
u
x3

x1
5/3
1/3
-7

x2
2/3
1/3
-4

x3
0
1
0

u
1
0
0

v
-1/3
1/3
5

z
0
0
1

50/3
40/3
200

A partir da repetimos o processo de ver quem o menor valor negativo da linha de z. Se -7

ou -4. Neste caso claro -7 assim consideramos a coluna no -7 para ser o divisor da coluna dos
resultados.
50/3 / 5/3 = 10
40/3 / 1/3 = 40
Portanto o valor que nos interessa o 5/3 j que a sua diviso apresentou menor valor.
Lembre-se s considere os menores valores POSITIVOS nunca os negativos....
Se eu acertei os valores teremos....
Dividindo toda a linha do 5/3 temos:
x1

x2

x3

2/5

3/5

-1/5

10

x3

1/3
-7

1/3
-4

1
0

0
0

1/3
5

0
1

40/3
200

Essa parte de escolher que nmero multiplicaremos a linha j deveramos ter criado vergonha
na cara e saber fazer. Pois demonstrei acima.
Usaremos a linha do PIVO para multiplicar por um valor qualquer que somado ou subtrado
pelos valores das outras linhas poderemos zerar os valores abaixo do pivo. Sendo assim
multiplicaremos todos os valores da linha do piv por -1/3 para podermos somar ou subtrair
os valores da linha abaixo afim de zerar o valor 1/3 de X1. Tambm multiplicaremos em outro

momento todos os valores mais abaixo da linha do piv por 7 para podermos somar ou
subtrair os valores da linha Abaixo afim de zerar o valor -7 de X2.
u
*(-1/3) x3
*7

x1
1
1/3
-7

x2
2/5
1/3
-4

x3
0
1
0

u
3/5
0
0

v
-1/5
1/3
5

z
0
0
1

10
40/3
200

E continua....
IMPORTANTE:
Chegaremos ao final quando a ultima linha estiver com todos os valores positivos
O Resultado ser encontrado vendo as variveis que ficaram, por exemplo no quadro acima
seria u e x3 mas somente x3 faz parte da Maximizao ento x1 =0, x2=0 e x3 =0 para atingir
200. Mas se o problema original de minimizao e as variveis so Y ento U e V so Y1 e Y2.
Assim a resposta final seria O mnimo seria de 200 encontrando y1=0 e y2=5.
Enfim....

Problemas de Transporte
Para resolver os problemas de transporte temos que Montar:
1 Grfico origem/destino
2 A soluo bsica (quadro). Com os valores de transporte dentro dos quadrados menores e o
custo do transporte no final de cada linha e coluna.
3 Custo Total (colocar no quadro os valores que cada um pode atingir considerando os valores
limites de linha e coluna, bloqueando linha ou coluna). H dois jeitos de fazer isso...
Comeando a preencher da esquerda para direita chamado de Canto Noroeste ou pelo Custo
Mnimo (preenchendo pelos menores valores de custo de transporte ou pelo quadradinho de
menor valor)
4 Aps preencher o quadro faa a Avaliao de Preencha os valores de U e V, lembrando que
U0=0 Ex.: U=0 e o quadrado onde est a coluna de est preenchido pego o valor do
quadradinho dele CT subtraio de U0 e obtenho V0, assim a partir desse e dos quadrados
preenchidos possvel achar os Vs existentes. Achando todos os Us e Vs faa a avaliao:
Pegue o valor de custo do transporte (o que fica no quadradinho e subtraia os valores de u e v
) ou seja, CT-U-V. Cuidado pois o valor de U ou V pode ser negativo e com mais
lembra???. Neste caso faa assim se algum U ou V for NEGATIVO some ele sem com o
Quadradinho do Custo sem pensar duas vezes. AHHHH S faa essa prova de CT-U-V para os
quadrados NO preenchidos. Depois de Preenchido todos e no tiver nenhum negativo
acabou-se o que era doce, do contrrio ter que fazer a gambiarra a seguir...
5 caso no chegue a ter os valores dos quadrados vazios todos positivos, Lamente e chore
muito, reze pra ter acertado alguma coisa na prova porque o tempo estar certamente
acabando. Mas pegue o quadrado em que ficou o valor negativo e chame ele de TETA ou Treta
mesmo, a partir dele risque um quadro cada ponta que ele pegar deve estar no quadrado
maior preenchido que dever ser subtrado ou somado ao Teta... Para saber quanto vale o teta
verifique que nmero mximo voc poder ter no quadrado preenchido... geralmente e
quase sempre o menor.

6 encontrando tudo positivo poderemos fazer o calculo do CT= todos os valores dos
quadrados maiores VEZES os valores dos seus quadradinhos correspondentes
LEMBRE_SE se deseja saber quandos quadradinho pode e deve preencher some o numero de
colunas + linhas e subitraia 1
Exemplo 4 colunas 2 linhas
4+2-1= 5 (5 ser o nmero de quadrados obrigatoriamente preenchido)
TRANSBORDO
a mesma coisa que o transporte + Destino como Origem e a Origem como destino ex>:
1

400

600
800

200

Ento fazemos:
A

1400
0

1600
0

1000
0

1000
1000

1000

1800

1200

Lembre-se que no primeiro quadro temos os valores externos de 400,200 e 800,200... se

somarmos os dois ambos do 1000. Esse 1000 servir para compor o novo quadro. Onde Havia
valor agora haver o valor + 1000 onde no havia ser apenas acrescentado 1000... e a
diagonal do quadro sempre ser preenchida por zero pois pra levar voc da sua casa pra sua
casa mesmo no precisa sair do lugar. O resto dos custos de transporte dado. A diagonal fica
fcil pra fazer com o Custo Mnimo que s preencher tudo que estiver com zero primeiro.
Rsrsrs

Acho que s... Qualquer dvida me avise... Ah cai toda a matria na prova... Tente fazer o
que realmente sabe e tiver mais pontos... Acho que se conseguir 4 ou 5 voc passa...
Good Luck!!!!