Minha resolução do POW12 da Universidade de Purdue. Maximização e restrição a várias variáveis reais e uma inteira

Posted on Dezembro 6, 2009 por

Tradução da entrada anterior.

A minha  resolução do POW12 foi aceite. [Nota de 19-12-2009: apenas se afirma que foi "completa ou parcialmente resolvida"]

« Problema. Determine, demonstrando, o valor máximo de \displaystyle\prod\limits_{j=1}^{k}x_{j}, em que x_{j}\geq 0,\displaystyle\sum\limits_{j=1}^{k}x_{j}=100, e k é variável. Em particular, a sua resposta deve ser maior ou igual a todos os valores que se obtêm escolhendo outros valores de k. »

Original:

“ Problem. Find, with proof, the maximum value of \displaystyle\prod\limits_{j=1}^{k}x_{j} where x_{j}\geq 0,\displaystyle\sum\limits_{j=1}^{k}x_{j}=100, and k is variable. In particular, your answer must be greater than or equal to all values obtained from other choices of k. “

Eis a resolução submetida.

Resolução:

Sejam \left( x_{1},x_{2},\ldots ,x_{k}\right) \in\mathbb{R}^{k}, f\left( x_{1},x_{2},\ldots ,x_{k}\right) =\displaystyle\prod\limits_{j=1}^{k}x_{j}\in\mathbb{R}, c\left( x_{1},x_{2},\ldots ,x_{k}\right) =\displaystyle\sum_{j=1}^{k}x_{j}-100 \in\mathbb{R} e \lambda\in\mathbb{R}. Para um dado k\in\mathbb{Z}, com k\geq 1, sabemos pelo método dos multiplicadores de  Lagrange que f\left( x_{1}^{\ast },x_{2}^{\ast },\ldots ,x_{k}^{\ast }\right) é um extremo local, se para x^{\ast }=\left( x_{1}^{\ast },x_{2}^{\ast },\ldots,x_{k}^{\ast }\right)

\nabla f\left( x^{\ast }\right) -\nabla c\left( x^{\ast }\right) \lambda^{\ast }=0\quad \quad k\text{ equa\c{c}\~{o}es}

c\left( x^{\ast }\right) =0\quad \quad 1\text{ equa\c{c}\~{a}o}

em que \lambda ^{\ast } é o valor do multiplicador \lambda que é solução destas k+1 equaçoes. Assim temos respectivamente

\displaystyle\prod\limits_{j\neq i}^{k}x_{j}^{\ast }-\lambda ^{\ast }=0\quad\quad 1\leq i\leq k

e

\displaystyle\sum\limits_{j=1}^{k}x_{j}^{\ast}-100=0\text{. }

Resolvendo este sistema de equações achamos

x_{1}^{\ast }=x_{2}^{\ast }=\cdots =x_{i}^{\ast }\cdots =x_{k}^{\ast}=\lambda ^{\ast }=\dfrac{100}{k}

e

\displaystyle\prod\limits_{j=1}^{k}x_{j}^{\ast}=\left( \dfrac{100}{k}\right) ^{k},

sendo este último um extremo local de f\left( x_{1},x_{2},\ldots ,x_{k}\right) , fixado k. Transformámos o problema inicial de maximização em k variáveis contínuas e uma discreta, a variável  k no da maximização de \left( 100/k\right) ^{k}. Agora introduzimos a função seguinte

u\left( t\right) =\left( \dfrac{100}{t}\right) ^{t}\quad\text{com }t\in\mathbb{R}\text{.}

A função u\left( t\right) tem um máximo no mesmo ponto t do da função

v\left( t\right) =\ln u\left( t\right) =t\ln 100-t\ln t\text{.}

Mas v^{\prime }\left( t\right) =0 para t^{\ast }=e^{\ln100-1}\simeq 36.788,v^{\prime }\left( t\right) >0 para t<t^{\ast } e v^{\prime }\left( t\right) <0 para t>t^{\ast }. Assim

u\left( t^{\ast }\right) =\left( \dfrac{100}{t^{\ast }}\right) ^{t^{\ast }}

é um máximo de u\left( t\right) . Dado que u\left( 37\right) >u\left( 36\right) , o máximo ocorre para k=37. Assim, para \sum_{j=1}^{k}x_{j}=\sum_{j=1}^{37}x_{j}=100 tem-se

\max\displaystyle\prod\limits_{j=1}^{k}x_{j}=\displaystyle\prod\limits_{j=1}^{37}x_{j}=\left( \dfrac{100}{37}\right) ^{37}\text{.}

Actualização de 19-12-2009: corrigidos alguns erros assinalados pelo leitor Rod Carvalho.

About these ads

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
Esta entrada foi publicada em Cálculo, Matemática, Problem, Problemas, Purdue University com as tags , . ligação permanente.

14 respostas a Minha resolução do POW12 da Universidade de Purdue. Maximização e restrição a várias variáveis reais e uma inteira

  1. Vishal Lama diz:
    Dezembro 7, 2009 às 1:10 am

    While this problem is a decent one, a much more interesting and challenging version of it reads as follows: Maximize the value of the expression \displaystyle \prod_{j=1}^{k} x_j, for some positive integer k, where \displaystyle \sum_{j=1}^{k} x_j = 100 and x_js are all positive integers.

    Responder
    • Américo Tavares diz:
      Dezembro 7, 2009 às 4:17 am

      Before you added the additional constraint I had thought how to generalize this technique and it came to me the naïve approach as follows:

      (1) start by fixing k and get a “first solution” depending on k.

      (2) Then assuming k were continuous find an “artificial solution”, let’s say f(k^*).

      (3) Finally compute the values of f at the nearest integers to k^* and choose according to the maximizing type of problem.

      This method, if feasible, still needs to be improved because of your new constraint.

      The general method might be in the research domain. I don’t know.

      Prior to your comment John Armstrong suggested I shoud try the Hancock’s Theory of Maxima and Minima in a recent comment to his post Extrema with Constraints I, of November 25, 2009. I have to see if I can find one here, in Lisbon.

      PS. in this post
      http://problemasteoremas.wordpress.com/2009/11/06/a-mathematical-reflections-undergraduate-problem/
      you find a MR Undergraduate Problem.

  2. Vishal Lama diz:
    Dezembro 7, 2009 às 8:55 am

    The approach you outlined would probably be the first line of attack, but there is a slight problem with it. Suppose, as you mentioned, we fix k. Then, in order to maximize the given expression, I am guessing you will argue that we need to have x_1 = x_2 = \ldots = x_k. But that may not be possible at all (because x_i‘s may not be positive integers)! Which means, one will have to look at lots of k‘s, that is, one can’t fix k.

    The reason the “discrete” version is slightly more challenging is due to the fact that the condition “x_1 = x_2 = \ldots = x_k” may no longer hold. So, one will have to come up with a different solution.

    Here’s a hint: Instead of the sum 100, consider the cases when the sum is 8, 9 or 10. (Those are the toy cases.) Then, try and see what the maximizing expression looks like.

    Responder
    • Américo Tavares diz:
      Dezembro 7, 2009 às 10:51 am

      Hi Vishal
      My naïve approach would be for a different general case I thought of in which we had a function f:\mathbb{R}^{n}\times\mathbb{N}\longrightarrow\mathbb{R} subject to constraints g:\mathbb{R}^{m}\times\mathbb{N}\longrightarrow\mathbb{R}, i. e. one of the variables (I denote k) instead of being continuous is discrete.

      In your problem all variables are discrete: function f:\mathbb{N}^{k}\longrightarrow\mathbb{N} and the constraint g:\mathbb{N}^{k}\longrightarrow\mathbb{N}.
      Thanks for your hint.
      Américo

  3. Américo Tavares diz:
    Dezembro 7, 2009 às 10:28 pm

    Vishal,
    The solution to your problem seems to be satisfied by k=33+1=34 variables, such as x_{1}=x_{2}=\ldots =x_{32}=x_{33}=3,x_{34}=1.

    Thus x_{1}x_{2}\cdots x_{32}x_{33}x_{34}=3^{33}\cdot 1=3^{33}.

    If this is correct x_{1}=x_{2}=\ldots =x_{32}=x_{33}=\left\lceil e\right\rceil .

    For x_{1}=x_{2}=\ldots =x_{49}=x_{50}=\left\lfloor e\right\rfloor =2, the
    product is only 2^{50}<3^{33}.

    I noticed that the function x\longmapsto\dfrac{x}{e^{\ln x-1}}=e and 2<e<3. I have not yet a rigorous argument.

    Responder
  4. Rod Carvalho diz:
    Dezembro 19, 2009 às 1:08 am

    Américo,

    Penso que existem alguns erros tipográficos na solução que apresentou. Por exemplo:

    - se a função f : \mathbb{R}^k \to \mathbb{R} retorna um escalar (o produto dos x_j), não entendo a expressão

    f(x_{1}, x_{2},\dots, x_{k}) = \prod\limits_{j=1}^{k}x_{j}\in\mathbb{R}^{k}

    - idem para a expressão

    c ( x_{1}, x_{2}, \dots, x_{k}) = \sum_{j=1}^{k}x_{j}-100 \in\mathbb{R}^{k}

    - em vez de “para um dado k \in \mathbb{Z}, com k \geq 1“, porque não escrever apenas: “para um dado k \in \mathbb{N}“?

    - em vez de x{\ast }= \left( x_{1}^{\ast },x_{2}^{\ast },\ldots,x_{k}^{\ast }\right), devia ser x^{\ast }= \left( x_{1}^{\ast },x_{2}^{\ast },\ldots,x_{k}^{\ast }\right)

    No entanto isto são apenas erros de sintaxe. Apesar de não ser matemático, e apesar de preferir o pragmatismo ao pedantismo intelectual, obter soluções para problemas de optimização em espaços discretos usando técnicas para espaços contínuos, e depois aproximar ao inteiro mais próximo… é algo que me parece potencialmente perigoso!! Tal poderia funcionar para calcular o x \in \mathbb{Z} que minimiza y = x^2, mas para funções-objectivo genéricas, é uma receita para o desastre. Penso que temos que nos restringir a certas classes de funções-objectivo. Exigir continuidade e diferenciabilidade deve ser necessário para se poder usar o método dos multiplicadores de Lagrange. Eu exigiria também convexidade. Por exemplo, a função f(x) = x^2 é convexa, pelo que quando temos um mínimo, sabemos que é global. Podemos então procurar soluções inteiras na vizinhança desse mínimo. Mas se a função não for convexa, pode haver um enorme número de mínimos locais, e aproximar ao inteiro mais próximo não é correcto.

    Responder
    • Américo Tavares diz:
      Dezembro 19, 2009 às 6:03 pm

      Rod

      Obrigado por ter identificado os erros de escrita: corrigi-os, excepto o dos naturais, porque, por vezes, nos livros, encontro uma definição, outra vez outra, começando em 1 ou em 0; a Wikipedia refere estas duas convenções.

      A aproximação aos inteiros mais próximos permitiu encontrar o mesmo valor da solução publicada pela Purdue University, que não usa o método de Lagrange, mas que depois de concluir que x_1=x_2=\dots =x_k, segue essencialmente o mesmo caminho, se estou a ver bem.

      Acrescentei, quanto à resolução, no início do post, a nota referindo que «apenas se afirma que foi “completa ou parcialmente resolvida”».

      Permanece, pois, em aberto a questão que levanta, parecendo-me pertinentes as suas considerações, que agradeço por trazer mais luz a este assunto.

  5. Neil Dickson diz:
    Dezembro 31, 2009 às 6:30 am

    Américo asked me to post my solution to it, so here it is. Apologies for replying in English, but I don’t trust Google Translate enough. :)

    The maximum is 3^{32} 2^2.

    Rough proof:
    It’s definitely the case that no factor can be 1 in the maximum, since the 1 could just be added to any other factor to increase the product. It’s also true that for any integer 5 or greater, 3(n-3)>n, so it could be split into 3 and n-3 to give a larger product and equal sum. Any 4 can be split into 2 and 2 giving the same sum and product. Therefore only 2 and 3 are needed to represent the maximum. Because 2^3<3^2, maximizing the number of 3's should give the maximum product. The maximum number of 3's you can fit into 100 with an even remainder is 32, leaving 4, which is two 2's.

    This turns out to also be equivalent to asking "What's the maximum number of maximal independent sets that can occur in a graph of 100 nodes?" The graph that satisfies this condition is just 32 K_3's and 2 K_2's (it's 34 disconnected components, but it's still a graph). I've been using this lately to construct very bad cases to test out a couple of quantum algorithms I've been working on.

    Responder
  6. Vishal Lama diz:
    Dezembro 31, 2009 às 9:47 am

    Américo,

    First, thanks a ton for the New Year’s wishes. Here’s wishing your family and you, too, a great New Year!

    Coming back to the problem on this thread, Neil’s solution is exactly what I was looking for! (The LaTeX code night still need some correction. As of now, I see {33}^3 {22}^2. As per Neil’s solution, I think the number should be 3^{32}2^2.)

    Responder

Deixar uma resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Gravatar
WordPress.com Logo

Está a comentar usando a sua conta WordPress.com ( Log Out / Modificar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter ( Log Out / Modificar )

Facebook photo

Está a comentar usando a sua conta Facebook ( Log Out / Modificar )

Cancelar

Connecting to %s