PROBLEMA DE CARGA FIXA (PLI)

O problema de carga fixa trata de situações para as quais a atividade econômica incorre em dois tipos de custos: uma taxa inicial “fixa”, que deve ser incorrida no início da atividade; e um custo variável, que é diretamente proporcional ao nível de atividade. Por exemplo, a preparação e o ajuste inicial das ferramentas de uma máquina antes de iniciar a produção incorrem em um custo fixo de preparação independentemente da quantidade de unidades fabricadas. Uma vez concluída, o custo da mão-de-obra e material é proporcional à quantidade produzida. Dado que F é a carga fixa, c é o custo unitário variável, e x é o nível de produção, a função custo é expressa como

C(x) = F + cx, se x>0

             0, caso contrário

                                    A função C(x) é intratável analiticamente porque envolve uma descontinuidade em x=0. O exemplo seguinte mostra como variáveis binárias são usadas para eliminar essa intratabilidade.

Exemplo – (Escolha de uma empresa de telefonia):

                                    Três empresas de telefonia me consultaram para que eu assinasse seus serviços de longa distância. A MaBell cobrará uma taxa fixa de $ 16 por mês, mais $ 0,25 por minuto. A PaBell cobrará $ 25 por mês, mas reduzirá o custo por minuto para $ 0,21. Quanto à BabyBell, a taxa fixa mensal é $ 18 e o custo por minuto é $ 0,22. De modo geral, gasto uma média mensal de 200 minutos em chamadas a longa distância. Considerando que eu não pague a taxa fixa mensal, a menos que eu faça chamadas e as distribua entre todas as três empresas à vontade, como eu poderia usar as três empresas para minimizar minha conta telefônica mensal?

Esse problema pode ser resolvido prontamente sem PLI. Entretanto, é instrutivo formulá-lo com um problema de programação inteira.

Definem-se

x1= minutos de chamadas de longa distância por mês pela MaBell

x2= minutos de chamadas de longa distância por mês pela PaBell

x3= minutos de chamadas de longa distância por mês pela BabyBell

-Binário:

y1 = 1 se x1>0; caso contrario x1 = 0

y2 = 1 se x2>0; caso contrário x2 = 0

y3 = 1 se x3>0; caso contrário x3 = 0

Podemos garantir que yj será igual a q se xj for positiva usando a restrição

Xj<= Myj ; j=1, 2, 3

                                    O valor selecionado de M deve ser suficientemente grande, de modo a não restringir a variável xj artificialmente. Como faço aproximadamente 200 minutos de chamadas por mês, então xj <= 200 para todo j, e é seguro selecionar M = 200.

O modelo completo é

Minimizar z = 0,25x1 + 0,21x2 +0,22x3 +16y1 +25y2 +18y3

Sujeito a                     

x1 + x2 + x3 = 200

x1 <= 200y1

x2 <= 200y2

x3 <= 200y3

x1, x2, x3 >= 0

y1, y2, y3 = (0, 1)

                                    A formulação mostra que a j-ésima taxa fixa mensal será parte da função objetivo z semente se yj=1, o que só pode acontecer se xj > 0 (conforme as últimas três restrições do modelo). Se xj = 0 na solução ótima, então a minimização de z, aliada ao fato de que o coeficiente na função objetivo de yj ser estritamente positivo, obrigará yj a ter valor zero, como desejado.

                                    A solução ótima é x3=200, y3=1, e todas as variáveis restantes iguais a zero o que mostra que a BabyBell deve ser selecionada como minha provedora de longa distância. Lembre-se de que a informação transmitida por y3=1 é redundante porque o mesmo resultado por x3>0 (=200). Na verdade, a principal razão para usar y1, y2, y3 é levar em conta a taxa fixa mensal. De fato, as três variáveis binárias convertem um modelo (não linear) mal comportado em uma formulação tratável das variáveis inteiras (binárias) em um problema que, em caso contrário, seria contínuo.