Exercício de PO (Programação Linear Inteira)

Era uma vez um capitão de um navio mercante que queria recompensar três membros de sua tripulação pela coragem que haviam tido em salvar a carga do navio durante uma tempestade inesperada em alto-mar. O capitão reservou certa soma de dinheiro na tesouraria e instruiu o imediato a distribuí-la igualmente entre os três marinheiros após a chegada do navio ao litoral. Uma noite, sem que os outros soubessem, um dos marinheiros foi à tesouraria e decidiu pedir um adiantamento de um terço (equitativo) do valor que lhe cabia. Após o imediato ter dividido o dinheiro em três partes iguais, sobrou uma moeda, que o marinheiro resolveu conservar com ele (além do um terço do dinheiro que lhe cabia).

Na noite seguinte, o segundo marinheiro teve a mesma ideia e, repetindo a mesma divisão em três partes do dinheiro que restou, também ficou com uma moeda extra.

Na terceira noite, o terceiro marinheiro também pegou um terço do que sobrou e mais uma moeda extra que não podia ser dividida. Quando o navio chegou ao litoral, o imediato dividiu o restante do dinheiro igualmente entre os três marinheiros e novamente sobrou uma moeda.

Para simplificar as coisas, o imediato deixou a moeda extra de lado e deu aos marinheiros suas quotas iguais designadas. No início, quanto dinheiro havia no cofre? Formule a questão como um problema de PLI e ache a solução. (Sugestão:o problema tem um número infinito contável de solução inteiras. Por conveniência, considere que estamos interessados em determinar a menor soma de dinheiro que satisfaça as condições do problema. Então, incrementando a soma resultante com a adição de 1, adicione-o como um limite inferior e obtenha a menor soma seguinte. Continuando dessa maneira, será desenvolvido um padrão geral de solução.)

Resolução:

y=soma original de dinheiro

xj= quantia tomada na noite j

j= 1, 2, 3

x4=quantia dada a cada marinheiro pelo primeiro oficial.

Minimizar: z=y

Sujeito a: 3x1 – y = 2

x1 + 3x2 – y = 2

x1 + x2 + 3x3 – y = 2

y – x1 – x2 – x3 – 3x4 = 1

Todas as variáveis são inteiras não negativas

Solução: y= 79 + 81n, n=0, 1, 2,...