{"id":543,"date":"2019-09-19T16:16:41","date_gmt":"2019-09-19T19:16:41","guid":{"rendered":"https:\/\/www.blogs.unicamp.br\/zero\/?p=543"},"modified":"2023-08-24T17:07:28","modified_gmt":"2023-08-24T20:07:28","slug":"problema-de-pizza","status":"publish","type":"post","link":"https:\/\/www.blogs.unicamp.br\/zero\/543\/","title":{"rendered":"Problema de Pizza"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

(Translate)<\/a><\/h4>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Pedir uma pizza seria uma tarefa trivial se n\u00e3o fosse a op\u00e7\u00e3o de escolher dois sabores. Neste texto vamos explicar como esta liberdade dada ao cliente transforma a \u201csimples\u201d a\u00e7\u00e3o de pedir uma pizza em um grave problema de otimiza\u00e7\u00e3o.<\/p>\n

Primeiro vamos definir esta op\u00e7\u00e3o de sabor da seguinte maneira: para cada pizza podemos escolher at\u00e9 dois sabores {x; y} de modo que o valor total da pizza ser\u00e1 Max {pre\u00e7o(x); pre\u00e7o(y)}. Para simplificar a comunica\u00e7\u00e3o, trabalharemos com o dinheiro imagin\u00e1rio \u201czero-coin\u201d ou apenas Z$. Assim, surge o desafio ao cliente de encontrar sabores {x; y} tal que minimize a fun\u00e7\u00e3o |pre\u00e7o(x) \u2013 pre\u00e7o(y)|\/2 (pois a metade mais cara da pizza foi devidamente paga pelo seu valor correto). Por exemplo, tomemos a seguinte lista de pizzas:<\/p>\n\n\n<\/colgroup>\n\n\n
\n

1) calabresa, mussarela, cebola, alho frito \/ 20Z$<\/i><\/p>\n

2) calabresa, mussarela, cebola, alho frito, cheddar, bacon \/ 25Z$<\/i><\/p>\n

3) atum, mussarela, cebola, alho frito, cheddar \/ 25Z$<\/i><\/p>\n

4) frango, mussarela, cebola, alho frito, cheddar \/ 24Z$<\/i><\/p>\n

5) frango, mussarela, cebola, alho frito, cheddar, bacon \/ 26Z$<\/i><\/p>\n

6) atum, mussarela, cebola, alho frito \/ 22Z$<\/i><\/p>\n

7) br\u00f3colis, mussarela, cebola, alho frito, cheddar \/ 26Z$<\/i><\/p>\n

8) calabresa, mussarela, cebola, alho frito, cheddar \/ 23Z$<\/i><\/p>\n

9) atum, mussarela, cebola, alho frito, cheddar, bacon \/ 27Z$<\/i><\/p>\n

10) br\u00f3colis, mussarela, cebola, alho frito \/ 23Z$<\/i><\/p>\n

11) br\u00f3colis, mussarela, cebola, alho frito, cheddar, bacon \/ 28Z$<\/i><\/p>\n

12) frango, mussarela, cebola, alho frito \/ 21Z$<\/i><\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

<\/i>Podemos simplificar este card\u00e1pio organizando-o a partir de fatores comuns, como por exemplo todas as pizzas v\u00eam com mussarela, cebola e alho frito, podemos omitir esta informa\u00e7\u00e3o na an\u00e1lise. Vamos distribu\u00ed-las em dois subgrupos, como ingrediente principal e pre\u00e7o. Para facilitar nossa an\u00e1lise, vamos considerar que o acr\u00e9scimo de ingrediente sempre deixa a pizza melhor. Assim, uma pizza de calabresa+cheddar+bacon ser\u00e1 melhor que uma pizza de calabresa+cheddar, que ser\u00e1 melhor do que uma pizza de calabresa.<\/p>\n\n\n\n<\/colgroup>\n\n\n
\n

Distribui\u00e7\u00e3o por sabor:<\/b><\/i><\/p>\n

1) calabresa \/ 20Z$<\/i><\/p>\n

8) calabresa, cheddar \/ 23Z$<\/i><\/p>\n

2) calabresa, cheddar, bacon \/ 25Z$<\/i><\/p>\n

12) frango \/ 21Z$<\/i><\/p>\n

4) frango, cheddar \/ 24Z$<\/i><\/p>\n

5) frango, cheddar, bacon \/ 26Z$<\/i><\/p>\n

6) atum \/ 22Z$<\/i><\/p>\n

3) atum, cheddar \/ 25Z$<\/i><\/p>\n

9) atum, cheddar, bacon \/ 27Z$<\/i><\/p>\n

10) br\u00f3colis \/ 23Z$<\/i><\/p>\n

7) br\u00f3colis, cheddar \/ 26Z$<\/i><\/p>\n

11) br\u00f3colis, cheddar, bacon \/ 28Z$<\/i><\/p>\n<\/td>\n

\n

Distribui\u00e7\u00e3o por pre\u00e7o:<\/b><\/i><\/p>\n

1) calabresa \/ 20Z$<\/i><\/p>\n

12) frango \/ 21Z$<\/i><\/p>\n

6) atum \/ 22Z$<\/i><\/p>\n

10) br\u00f3colis \/ 23Z$<\/i><\/p>\n

8) calabresa, cheddar \/ 23Z$<\/i><\/p>\n

4) frango, cheddar \/ 24Z$<\/i><\/p>\n

2) calabresa, cheddar, bacon \/ 25Z$<\/i><\/p>\n

3) atum, cheddar \/ 25Z$<\/i><\/p>\n

5) frango, cheddar, bacon \/ 26Z$<\/i><\/p>\n

7) br\u00f3colis, cheddar \/ 26Z$<\/i><\/p>\n

9) atum, cheddar, bacon \/ 27Z$<\/i><\/p>\n

11) br\u00f3colis, cheddar, bacon \/ 28Z$<\/i><\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Assim, a partir do crit\u00e9rio 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\u00e7\u00f5es:<\/p>\n

Max {pre\u00e7o(sabor5); pre\u00e7o(sabor1)} =<\/i><\/p>\n

= Max {26Z$; 20Z$} = 26Z$.<\/i><\/p>\n

Max {pre\u00e7o(sabor5); pre\u00e7o(sabor8)} =<\/i><\/p>\n

= Max {26Z$; 23Z$} = 26Z$.<\/i><\/p>\n

Max {pre\u00e7o(sabor5); pre\u00e7o(sabor2)} =<\/i><\/p>\n

= Max {26Z$; 25Z$} = 26Z$.<\/i><\/p>\n

Analisando a fun\u00e7\u00e3o |pre\u00e7o(x) \u2013 pre\u00e7o(y)| a ser minimizada para cada caso, temos:<\/p>\n

|pre\u00e7o(sabor5) \u2013 pre\u00e7o(sabor1)|\/2 = 3Z$.<\/i><\/p>\n

|pre\u00e7o(sabor5) \u2013 pre\u00e7o(sabor8)|\/2 = 1,5Z$.<\/i><\/p>\n

|pre\u00e7o(sabor5) \u2013 pre\u00e7o(sabor2)|\/2 = 0,5Z$.<\/i><\/p>\n

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\u00e3o tivesse restri\u00e7\u00e3o sobre sabor, ter\u00edamos uma solu\u00e7\u00e3o melhor ao escolher o sabor7.<\/p>\n

Max {pre\u00e7o(sabor5); pre\u00e7o(sabor7)} =<\/i><\/p>\n

= Max {26Z$; 26Z$} = 26Z$.<\/i><\/p>\n

|pre\u00e7o(sabor5) \u2013 pre\u00e7o(sabor7)| = 0Z$.<\/i><\/p>\n

Agora no caso de duas pizzas serem pedidas, temos a possibilidade de escolher at\u00e9 4 sabores. Seu custo ser\u00e1 dado pela express\u00e3o:<\/p>\n

[Max {pre\u00e7o(x); pre\u00e7o(y)} + Max {pre\u00e7o(w); pre\u00e7o(z)}].<\/i><\/p>\n

Assim, surge o desafio ao cliente de encontrar sabores {x; y; w; z} e rearranj\u00e1-los de forma que minimize a fun\u00e7\u00e3o [|pre\u00e7o(x) \u2013 pre\u00e7o(y)| + |pre\u00e7o(w) \u2013 pre\u00e7o(z)|]\/2. Neste caso, temos al\u00e9m do problema de escolher, o problema de rearranjar. Pois 4 sabores (chamados de 1, 2, 3 e 4) poderiam ser arranjados de 3 formas:<\/p>\n

{1; 2} & {3; 4} \/\/ {1; 3} & {2; 4} \/\/ {1; 4} & {2; 3}<\/i><\/p>\n

Considerando o mesmo card\u00e1pio usado no caso de apenas uma pizza, suponhamos que os clientes desejem respectivamente um sabor principal de cada tipo (calabresa, frango, atum e br\u00f3colis), e n\u00e3o fa\u00e7am quest\u00e3o de adicionais (mas se poss\u00edvel, desejam). Temos ent\u00e3o sabor1 (calabresa \/ 20Z$), sabor12 (frango \/ 21Z$), sabor6 (atum \/ 22Z$) e sabor10 (br\u00f3colis \/ 23Z$).<\/p>\n

{sabor1; sabor12} & {sabor6; sabor10} = total a pagar 44Z$<\/i><\/p>\n

{sabor1; sabor6} & {sabor12; sabor10} = total a pagar 45Z$<\/i><\/p>\n

{sabor1; sabor10} & {sabor6; sabor12} = total a pagar 45Z$<\/i><\/p>\n

Agora calculando as diferen\u00e7as de cada op\u00e7\u00e3o, temos:<\/p>\n

[|pre\u00e7o(sabor1)\u2013pre\u00e7o(sabor12)|
+|pre\u00e7o(sabor6)\u2013pre\u00e7o(sabor10)|]\/2 = 1Z$.<\/i><\/p>\n

[|pre\u00e7o(sabor1)\u2013pre\u00e7o(sabor6)|
+|pre\u00e7o(sabor12)\u2013pre\u00e7o(sabor10)|]\/2 = 2Z$.<\/i><\/p>\n

[|pre\u00e7o(sabor1)\u2013pre\u00e7o(sabor10)|
+|pre\u00e7o(sabor6)\u2013pre\u00e7o(sabor12)|]\/2 = 2Z$.<\/i><\/p>\n

A primeira op\u00e7\u00e3o pode parecer a mais interessante, por\u00e9m a terceira op\u00e7\u00e3o nos permite melhorar a pizza de calabresa, pedindo em seu lugar o sabor8 (calabresa, cheddar).<\/p>\n

{sabor8; sabor10} & {sabor6; sabor12} = total a pagar 45Z$<\/i><\/p>\n

[|pre\u00e7o(sabor8)\u2013pre\u00e7o(sabor10)|
+|pre\u00e7o(sabor6)\u2013pre\u00e7o(sabor12)|]\/2 = 0,5Z$.<\/i><\/p>\n

Assim, se pensarmos em qual op\u00e7\u00e3o gastaremos menos, na primeira op\u00e7\u00e3o gastamos 44Z$, contudo o desperd\u00edcio (valor a mais pago pela pizza) \u00e9 de 1Z$. Enquanto que na quarta op\u00e7\u00e3o gastamos 45Z$, mas o desperd\u00edcio neste caso \u00e9 de 0,5Z$.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

Voltar para p\u00e1gina inicial<\/a><\/h4>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

Quem escreve os posts?<\/a><\/h4>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"

Como escolher as metades das pizzas reduzindo o preju\u00edzo que teremos com as de menor valor?<\/p>\n","protected":false},"author":434,"featured_media":548,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"pgc_sgb_lightbox_settings":"","_vp_format_video_url":"","_vp_image_focal_point":[],"footnotes":""},"categories":[1208],"tags":[],"class_list":["post-543","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-v-2-ed-1"],"jetpack_featured_media_url":"https:\/\/www.blogs.unicamp.br\/zero\/wp-content\/uploads\/sites\/187\/2019\/09\/pizza-problem.png","_links":{"self":[{"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/posts\/543","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/users\/434"}],"replies":[{"embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/comments?post=543"}],"version-history":[{"count":26,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/posts\/543\/revisions"}],"predecessor-version":[{"id":5203,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/posts\/543\/revisions\/5203"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/media\/548"}],"wp:attachment":[{"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/media?parent=543"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/categories?post=543"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/tags?post=543"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}