PES Pesquisa Operacional

Prof. Milton Procópio de Borba

Originais do Prof. Fernando Deeke Sasse

6. Formulação e Solução de Problemas como Programas Lineares

1. Problema dos Turnos

Planta Química . O gerente de produção de uma planta química está tentando elaborar um esquema de turnos para sua força de trabalho. Cada dia de toda semana de trabalho é dividido em turnos de 8 horas (00:01-08:00, 08:01-16:00, 16:01-24:00) designados por madrugada, dia e noite, respectivamente. A planta deve funcionar continuamente e um número mínimo de trabalhadores requeridos para cada um destes turnos ao longo da semana é especificado abaixo:

O acordo com o sindicato, determinando turnos aceitáveis para os trabalhadores são dados como segue:

1. Cada trabalhador pode ser designado para trabalhar ou um turno da Madrugada, ou Dia ou Noite, e uma vez que a escolha tenha sido feita, ele deve permanecer neste turno em cada dia da semana.

2. Cada trabalhador trabalha 4 dias consecutivos durante um período de 7 dias.

No total há 60 trabalhadores.

- Formule o problema do gerente de produção como um programa linear

Solução :

1. Variáveis

O acordo com o sindicato é tal que cada trabalhador pode somente começar seus 4 dias consecutivos de trabalho em um dos 7 dias da semana e em um dos turnos. Vamos designar os dias da semana e turnos por

Seg será dia 1, Ter será dia 2, etc.

Madrugada será 1, Dia será 2, Noite será 3.

Então as variáveis serão:

- número de trabalhadores começando seus 4 dias consecutivos de trabalho no dia i (i = 1 .. 7) e turno j (j = 1..3).

Estas variáveis são inteiras, mas como é pedida uma formulação de programa linear, vamos permitir inicialmente que elas assumam valores variáveis.

2. Restrições

O limite superior para o número total de trabalhadores é 60:

.

Por outro lado, devemos também considerar o limite inferior para o número total de trabalhadores requeridos para cada turno/dia. Seja o número mínimo de trabalhadores exigidos no dia i e turno j (por exemplo, = 5, quinta, dia). As restrições são então dadas por

Segunda: >=

Terça: >=

Quarta: >=

Quinta: >=

Sexta: >=

Sábado: >=

Domingo: >=

É importante notar que o índice em representa o dia em que o trabalhador começa seus 4 dias consecutivos de trabalho.

3. Objetivo

O objetivo do gerente de produção parece ser simplesmente encontrar um esquema factível, de modo que, a princípio, qualquer solução factível é possível. É natural, no entanto que, para minimizar custos, o gerente esteja interessado em minimizar o número necessário de trabalhadores. Neste caso, a função objetivo seria:

.

Isso completa a formulação do problema como um programa linear. Vamos agora resolver o problema no Maple:

> restart:

> with(linalg):

Warning, the protected names norm and trace have been redefined and unprotected
 

> DD:=matrix([[5,7,9],[3,8,10],[2,9,10],[4,5,7],[3,7,11],[2,2,2],[2,5,2]]);

> DD[5,3];

> for j to 3 do

> e[1,j]:=N[1,j]+N[7,j]+N[6,j]+N[5,j] >= DD[1,j];

> od;

> for j to 3 do

> e[2,j]:=N[2,j]+N[1,j]+N[7,j]+N[6,j] >= DD[2,j];

> od;

> for j to 3 do

> e[3,j]:=N[3,j]+N[2,j]+N[1,j]+N[7,j] >= DD[3,j];

> od;

> for j to 3 do

> e[4,j]:=N[4,j]+N[3,j]+N[2,j]+N[1,j] >= DD[4,j];

> od;

> for j to 3 do

> e[5,j]:=N[5,j]+N[4,j]+N[3,j]+N[2,j] >= DD[5,j];

> od;

> for j to 3 do

> e[6,j]:=N[6,j]+N[5,j]+N[4,j]+N[3,j] >= DD[6,j];

> od;

> for j to 3 do

> e[7,j]:=N[7,j]+N[6,j]+N[5,j]+N[4,j] >= DD[7,j];

> od;

> with(simplex):

Warning, the names basis and pivot have been redefined
 
Warning, the protected names maximize and minimize have been redefined and unprotected
 

> z:=sum(sum(N[m,n],m=1..7),n=1..3);

> v1:=%<=60;

> vinculos:={seq(seq(e[h,k],k=1..3),h=1..7),v1};

> sol:=minimize(z,vinculos,NONNEGATIVE);

> assign(sol):

> z;

Devemos ajustar esta solução de modo que tenhamos somente valores inteiros. Por exemplo, podemos fazer , e .

> N[1,2] := 1;

> N[2,2]:= 4;

> N[5,2] := 3;

O número de trabalhadores será então:

> z;

Notemos que o aparece nas desigualdades:

> e[1,2];

> e[2,2];

> e[3,2];

Isso mostra que podemos tomar , de modo que

> N[1,2]:=0;

> z;

Veremos mais tarde como resolver este problema como uma programa linear inteiro.

2. Problema de Manufatura

Problema de Manufatura. Uma companhia manufatura 4 produtos (P1,P2,P3,P4) em duas máquinas (X e Y). O tempo (em minutos) para processar uma unidade de cada produto em cada máquina é dado abaixo:

O lucro por unidade para cada produto (P1, P2, P3, P4) é $10, $12, $17 e $8, respectivamente. P1 deve ser produzido em ambas máquinas , mas P2, P3 e P4 podem ser produzidos em qualquer máquina.

A fábrica tem um espaço muito limitado. Somente em uma semana de produção é armazenada em 50 , sendo que o espaço ocupado por cada produto é 0.1, 0.15, 0.5 e 0.05 , para os produtos P1, P2, P3 e P4 , respectivamente.

As exigências do cliente são de que a quantidade produzida do produto P3 deve ser relacionada com P2: em uma semana a quantidade de P2 produzido deve ser aproximadamente o dobro de P3.

A máquina X está fora de funcionamento para manutenção durante 5% do tempo e a máquina Y, 7% do tempo.

Assumindo uma semana de trabalho de 35h, formule o problema de como a manufaturar estes produtos, como um programa linear.

Solução :

Inicialmente faremos a formulação matemática.

1. Variáveis

Essencialmente estamos interessados na quantidade produzida em cada máquina. Portanto, sejam

- a quantidade do produto i (i = 1,2,3,4) produzida na máquina X por semana.

- a quantidade do produto i (i = 1,2,3,4) produzida na máquina Y por semana.

2. Restrições

- espaço ( ):

0.1 (2 ) + 0.15 ( ) + 0.5 ( ) +0.05 ( ) <= 50

- exigências do cliente:

= 2 ( )

Notemos que este é somente um vínculo aproximado (digamos, 5%), de modo que este vínculo é melhor expresso como

0.95 [ 2( + ) ]<= <= 1.05 [2( )]

- tempo disponível (minutos por semana):

(35)(60) (máquina X)

(35)(60) (máquina Y)

3. Objetivo

Maximizar o lucro, ou seja,

max 10(2 ) + 12 ( ) +17( ) + 8 ( ) .

Solução no Maple:

> restart:

> with(linalg):

Warning, the protected names norm and trace have been redefined and unprotected
 

> r1:= 0.1 *(2 *x[1]) + 0.15* (x[2]+y[2]) + 0.5 *( x[3]+y[3] ) +0.05 *(x[4]+y[4]) <= 50 ;

> r2:= 0.95 *( 2*(x[3] + y[3]) )-( x[2]+y[2])<=0;

> r3:=x[2]+y[2] - 1.05*(2*(x[3]+y[3]))<=0;

> r4:=10*x[1] + 12*x[2] + 13*x[3] + 8*x[4] <= 0.95*(35)*(60);

> r5:=27*x[1] + 19*y[2] + 33*y[3] + 23*y[4] <= 0.93*(35)*(60);

> z:=10*(2 *x[1]) + 12 *(x[2]+y[2]) +17*(x[3]+y[3]) + 8* (x[4]+y[4]);

> vinculos:={r1,r2,r3,r4,r5};

> with(simplex):

Warning, the names basis and pivot have been redefined
 
Warning, the protected names maximize and minimize have been redefined and unprotected
 

> sol:=maximize(z,vinculos,NONNEGATIVE);

> assign(sol):

Vemos assim que nesta solução o produto P1 não é produzido. Se a produção de P1 for exigida, já sabemos que ela diminui o lucro e portanto deveria ser mínima. Qualquer alteração deste tipo (por exemplo, ) é facilmente introduzida no problema. Como os valores na solução devem ser inteiros, tomamos,

> y[2]:=102;x[3]:=52;x[4]:=163;

O lucro será:

> z;

Podemos verificar que todos os vínculos são satisfeitos:

> r1;

> r2;

> r3;

> r4;

> r5;

3. Problemas propostos

3.1 Montagem

Uma companhia monta 4 produtos (1,2,3,4) a partir de peças importadas. O lucro por unidade para cada produto (1,2,3,4) é $10, $15, $22 e $17, respectivamente. A demanda máxima na próxima semana para cada produto (1,2,3,4) é 50, 60, 85 e 70 unidades, respectivamente. Há três estágios (A, B, C) na montagem manual de cada produto e as horas/homem necessárias para cada estágio por unidade do produto são mostradas abaixo:

O tempo nominal disponível na próxima semana para a montagem em cada estágio (A, B, C) é de 160, 200 e 80 homens-hora, respectivamente.

É possível variar o tempo em homens/hora gasta na montagem em cada estágio de tal modo que trabalhadores previamente empregados no estágio B da montagem possam gastar 20% do seu tempo no estágio A, e trabalhadores previamente empregados no estágio C de montagem, podem gastar 30% do seu tempo no estágio A.

As restrições de produção também requerem que a razão de fabricação (unidades de produto 1)/(unidades de produto 4) deve estar entre 0.9 e 1.15.

Formule e resolva o problema de decidir quanto produzir na próxima semana como um programa linear.

3.2 Avião de carga

Um avião de carga tem três compartimentos de carga: Frente, Centro e Traseira. Estes compartimentos têm os seguintes limites de peso e espaço:

Compartimento	Peso max. (toneladas)	Espaço max. (m³)
Frente	10	6800
Centro	16	8700
Traseira	8	5300

Além disso, o peso da carga nos respectivos compartimentos deve estar na mesma proporção que a capacidade de peso, para manter o balanço do avião.

As seguintes cargas estão disponíveis para o próximo vôo:

	Carga Peso(ton.)	Volume (m³/ton.)	Lucro ($/ton.)
C1	18	480	310
C2	15	650	380
C3	23	580	350
C4	12	390	285

Qualquer proporção destas cargas é aceitável. O objetivo é determinar quanto de carga (C1, C2, C3, C4) deve ser aceita e como distribui-las nos compartimentos de modo que o lucro por vôo seja maximizado. Proceda através das seguintes etapas:

(i) Formule o problema como um programa linear;

(ii) Descreva as suposições feitas na formulação deste problema como um programa linear.

3.3 Manufatura de três produtos

. Uma companhia manufatura três produtos, P1, P2 e P3, e tem disponível 4 máquinas, M1, M2, M3 e M4. O tempo de produção (em minutos) por unidade varia de uma máquina a outra, como mostrado na tabela abaixo:

	M1	M2	M3	M4
P1	5	7	4	10
P2	6	12	8	15
P3	13	14	9	17

Similarmente a contribuição de lucro ($) por unidade varia uma máquina a outra, de acordo com a tabela:

	W1	W2	W3	W4
P1	10	8	6	9
P2	18	20	15	17
P3	15	16	13	17

Se em uma semana há 35 horas de trabalho disponíveis em cada máquina, quanto de cada produto deve ser produzido de modo que tenhamos uma produção semanal de ao menos 100 unidades de P1, 150 unidades de P2 e 100 unidades de P3 ? Obviamente queremos maximizar o lucro.