Problema de Pizza

Pedir uma pizza seria uma tarefa trivial se não fosse a opção de escolher dois sabores. Neste texto vamos explicar como esta liberdade dada ao cliente transforma a “simples” ação de pedir uma pizza em um grave problema de otimização.

Primeiro vamos definir esta opção de sabor da seguinte maneira: para cada pizza podemos escolher até dois sabores {x; y} de modo que o valor total da pizza será Max {preço(x); preço(y)}. Para simplificar a comunicação, trabalharemos com o dinheiro imaginário “zero-coin” ou apenas Z$. Assim, surge o desafio ao cliente de encontrar sabores {x; y} tal que minimize a função |preço(x) – preço(y)|/2 (pois a metade mais cara da pizza foi devidamente paga pelo seu valor correto). Por exemplo, tomemos a seguinte lista de pizzas:

1) calabresa, mussarela, cebola, alho frito / 20Z$ 2) calabresa, mussarela, cebola, alho frito, cheddar, bacon / 25Z$ 3) atum, mussarela, cebola, alho frito, cheddar / 25Z$ 4) frango, mussarela, cebola, alho frito, cheddar / 24Z$ 5) frango, mussarela, cebola, alho frito, cheddar, bacon / 26Z$ 6) atum, mussarela, cebola, alho frito / 22Z$ 7) brócolis, mussarela, cebola, alho frito, cheddar / 26Z$ 8) calabresa, mussarela, cebola, alho frito, cheddar / 23Z$ 9) atum, mussarela, cebola, alho frito, cheddar, bacon / 27Z$ 10) brócolis, mussarela, cebola, alho frito / 23Z$ 11) brócolis, mussarela, cebola, alho frito, cheddar, bacon / 28Z$ 12) frango, mussarela, cebola, alho frito / 21Z$

Podemos simplificar este cardápio organizando-o a partir de fatores comuns, como por exemplo todas as pizzas vêm com mussarela, cebola e alho frito, podemos omitir esta informação na análise. Vamos distribuí-las em dois subgrupos, como ingrediente principal e preço. Para facilitar nossa análise, vamos considerar que o acréscimo de ingrediente sempre deixa a pizza melhor. Assim, uma pizza de calabresa+cheddar+bacon será melhor que uma pizza de calabresa+cheddar, que será melhor do que uma pizza de calabresa.

Distribuição por sabor: 1) calabresa / 20Z$ 8) calabresa, cheddar / 23Z$ 2) calabresa, cheddar, bacon / 25Z$ 12) frango / 21Z$ 4) frango, cheddar / 24Z$ 5) frango, cheddar, bacon / 26Z$ 6) atum / 22Z$ 3) atum, cheddar / 25Z$ 9) atum, cheddar, bacon / 27Z$ 10) brócolis / 23Z$ 7) brócolis, cheddar / 26Z$ 11) brócolis, cheddar, bacon / 28Z$

Distribuição por preço: 1) calabresa / 20Z$ 12) frango / 21Z$ 6) atum / 22Z$ 10) brócolis / 23Z$ 8) calabresa, cheddar / 23Z$ 4) frango, cheddar / 24Z$ 2) calabresa, cheddar, bacon / 25Z$ 3) atum, cheddar / 25Z$ 5) frango, cheddar, bacon / 26Z$ 7) brócolis, cheddar / 26Z$ 9) atum, cheddar, bacon / 27Z$ 11) brócolis, cheddar, bacon / 28Z$

Assim, a partir do critério de qualidade, se pediremos por exemplo metade da pizza do sabor 5 (frango, cheddar, bacon) e queremos a outra metade com ingrediente base de calabresa, temos as seguintes situações:

Max {preço(sabor5); preço(sabor1)} =

= Max {26Z$; 20Z$} = 26Z$.

Max {preço(sabor5); preço(sabor8)} =

= Max {26Z$; 23Z$} = 26Z$.

Max {preço(sabor5); preço(sabor2)} =

= Max {26Z$; 25Z$} = 26Z$.

Analisando a função |preço(x) – preço(y)| a ser minimizada para cada caso, temos:

|preço(sabor5) – preço(sabor1)|/2 = 3Z$.

|preço(sabor5) – preço(sabor8)|/2 = 1,5Z$.

|preço(sabor5) – preço(sabor2)|/2 = 0,5Z$.

Logo, o sabor2 minimiza o custo neste caso. Por outro lado, se apenas o sabor5 estivesse definido, ou seja, a outra metade da pizza não tivesse restrição sobre sabor, teríamos uma solução melhor ao escolher o sabor7.

Max {preço(sabor5); preço(sabor7)} =

= Max {26Z$; 26Z$} = 26Z$.

|preço(sabor5) – preço(sabor7)| = 0Z$.

Agora no caso de duas pizzas serem pedidas, temos a possibilidade de escolher até 4 sabores. Seu custo será dado pela expressão:

[Max {preço(x); preço(y)} + Max {preço(w); preço(z)}].

Assim, surge o desafio ao cliente de encontrar sabores {x; y; w; z} e rearranjá-los de forma que minimize a função [|preço(x) – preço(y)| + |preço(w) – preço(z)|]/2. Neste caso, temos além do problema de escolher, o problema de rearranjar. Pois 4 sabores (chamados de 1, 2, 3 e 4) poderiam ser arranjados de 3 formas:

{1; 2} & {3; 4} // {1; 3} & {2; 4} // {1; 4} & {2; 3}

Considerando o mesmo cardápio usado no caso de apenas uma pizza, suponhamos que os clientes desejem respectivamente um sabor principal de cada tipo (calabresa, frango, atum e brócolis), e não façam questão de adicionais (mas se possível, desejam). Temos então sabor1 (calabresa / 20Z$), sabor12 (frango / 21Z$), sabor6 (atum / 22Z$) e sabor10 (brócolis / 23Z$).

{sabor1; sabor12} & {sabor6; sabor10} = total a pagar 44Z$

{sabor1; sabor6} & {sabor12; sabor10} = total a pagar 45Z$

{sabor1; sabor10} & {sabor6; sabor12} = total a pagar 45Z$

Agora calculando as diferenças de cada opção, temos:

[|preço(sabor1)–preço(sabor12)|
+|preço(sabor6)–preço(sabor10)|]/2 = 1Z$.

[|preço(sabor1)–preço(sabor6)|
+|preço(sabor12)–preço(sabor10)|]/2 = 2Z$.

[|preço(sabor1)–preço(sabor10)|
+|preço(sabor6)–preço(sabor12)|]/2 = 2Z$.

A primeira opção pode parecer a mais interessante, porém a terceira opção nos permite melhorar a pizza de calabresa, pedindo em seu lugar o sabor8 (calabresa, cheddar).

{sabor8; sabor10} & {sabor6; sabor12} = total a pagar 45Z$

[|preço(sabor8)–preço(sabor10)|
+|preço(sabor6)–preço(sabor12)|]/2 = 0,5Z$.

Assim, se pensarmos em qual opção gastaremos menos, na primeira opção gastamos 44Z$, contudo o desperdício (valor a mais pago pela pizza) é de 1Z$. Enquanto que na quarta opção gastamos 45Z$, mas o desperdício neste caso é de 0,5Z$.