1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding the maximum value of a sum involving several parameters

  1. Jun 7, 2017 #1
    1. The problem statement, all variables and given/known data
    Given that
    a1+a2+a3+... +a7=1 and that all aj is smaller than 1 and greater than 0 and variable , find the maximum value of

    6a1+5a2+4a3+...+ a6

    2. Relevant equations
    no further constraints

    3. The attempt at a solution
    I have no idea how to solve this problem specifically, but I do recall a technique called lagrange multipliers that may come in handy. If anyone could direct me to a computer program that would do the calculations for me or help me solve this problem non-numerically I would be very grateful. Thank you!
     
    Last edited: Jun 7, 2017
  2. jcsd
  3. Jun 7, 2017 #2

    Charles Link

    User Avatar
    Homework Helper

    Please clarify, because I think you had posted a similar problem yesterday. Is it ## 5a_2 ## or ## 5/a_2 ## etc.? Also, I think your sum should be ## a_1 ## to ## a_6 ## is equal to ## 1 ##. ## \\ ## Anyway, Lagrange multipliers should work. With Lagrange multipliers you let ## f(a_1, a_2,...,a_6, \lambda)=6/a_1+5/a_2+...+\lambda (a_1+...+a_6-1) ##. You then take a partial derivative of ## f(a_1,..., a_6,\lambda) ## w.r.t. each variable and set to zero to get you an equation, and you take the partial w.r.t. ## \lambda ## and set to zero, which essentially gives you your constraint equation. The solution is straightforward. 7 equations and 7 unknowns.
     
  4. Jun 7, 2017 #3
    Yes I did post a similar thread yesterday, but it was deleted by the moderators. I mean 5a and not 5/a as I wrote in my previous thread. Sorry, if that caused any confusion. The sum from 1-6 equals one and not 1-7. I understand why you would think so, but I eliminated a7 in a previous step. Is there anyway I could simply let a computer solve this problem for me, without having to do the calculations myself or coding or downloading a suitable Programm? Thanks for the reply!
     
  5. Jun 7, 2017 #4

    Charles Link

    User Avatar
    Homework Helper

    In the form that you have it, clearly ## a_1=0 ## gives a maximum, (## 6/a_1= +\infty ##), so that there is no good numerical solution of any kind.
     
  6. Jun 7, 2017 #5
    Sorry my mistake it is 6a1 and not 6/a1. I am sorry, this is turning out to be quite a mess...
     
  7. Jun 7, 2017 #6

    Charles Link

    User Avatar
    Homework Helper

    That also has a simple answer: ## a_1 =1 ##; ## a_2=a_3=a_4=a_5=a_6=0 ##. The maximum value is ## 6 ##. And Lagrange multiplier method does not get the solution, because in this case the derivatives are not equal to zero. The solution can be seen by inspection.
     
  8. Jun 7, 2017 #7

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    As written your problem has NO solution. If you have strict inequalities ##0 < a_i < 1, \: i = 1, \ldots, 7## your constraint set is open and the function ##f(a) = 6 a_1 + 5 a_2 + \cdots + a_6## does not have a maximum on that constraint set. It has a supremum, but not a maximum. A simpler, similar example would be ##\max x## on ##0 < x < 1##, which has no solution.

    However, if you make the inequalities non-strict (so ##0 \leq a_i \leq 1, \; i = 1, \ldots, 7##) you get a standard linear programming problem that can be solved quite easily by the bounded-variable simplex method. Alternatively, you can use a Lagrange multiplier method, but you need to use the so-called Karush-Kuhn-Tucker conditions instead of just setting derivatives to zero---it is NOT the standard Lagrange-multiplier method that you are probably thinking of!

    You can easily get a numerical solution in EXCEL, using the Solver Tool. Other spreadsheets have similar tools available.There are also numerous free on-line linear programming solvers that can solve small problems like yours.
     
  9. Jun 7, 2017 #8
    Thanks! Could you link me to the websites you suggested?If I were interested in the suprememum how would I go about that? The same way?
     
  10. Jun 7, 2017 #9

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    The supremum (in the open-set version) is just the maximum in the closed-set version.

    Google "on-line linear programming solvers" to see what is available. Some of them solvers are not particularly user-friendly, but if you just need to solve one or two problems that is not really a big issue.
     
  11. Jun 7, 2017 #10
    Thank you so much!
     
  12. Jun 7, 2017 #11

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Just as a matter of interest, the Lagrange multiplier solution is as follows. Let
    $$L = \sum_{i=1}^7 (7-i) x_i + \lambda(1-\sum_{i=1}^7 x_i).$$
    For the maximization problem with bound constraints ##0 \leq x_i \leq 1## for all ##i##, the (Karush-Kuhn-Tucker) optimality conditions are:
    (1) If ##x_i = 0## then ##\partial L / \partial x_i \leq 0##.
    (2) If ##x_i = 1## then ##\partial L / \partial x_i \geq 0## .
    (3) If ##0 < x_i < 1## then ##\partial L / \partial x_i = 0##.

    Let us guess the solution ##x_1 = 1## all other ##x_i = 0##.
    $$\begin{array}{l}
    \partial L/ \partial x_1 = 6 - \lambda \geq 0\\
    \partial L / \partial x_2 = 5 - \lambda \leq 0 \\
    \hspace{1cm} \vdots \\
    \partial L / \partial x_6 = 1 - \lambda \leq 0 \\
    \partial L / \partial x_7 = - \lambda \leq 0
    \end{array}
    $$
    These conditions are satisfied by choosing any ##\lambda## between 5 and 6. Since the problem is a so-called "convex programming problem" the conditions are also sufficient to guarantee a global constrained maximum. In other words, the intuitive solution ##x = (1,0,0,0,0,0,0)## is provably optimal.

    Much simpler, however, is to note that the constraints ##x_i \leq 1## are redundant because if ##\sum_i x_i = 1## and each ##x_i \geq 0## then each ##x_i## is automatically ##\leq 1##. Therefore, the original problem is equivalent to
    $$\begin{array}{rcl}
    \max Z &=& \sum_{i=1}^7 (7-i) x_i \\
    \text{s.t.}&& \sum_{i=1}^7 x_i = 1 \\
    &&x_i \geq 0, \; i = 1,2, \ldots, 7
    \end{array}
    $$

    That makes the problem almost trivial: the simplex method takes just one step: use the equality constraint to write
    $$x_1 = 1 - \sum_{i=2}^7 x_i ,$$
    giving
    $$Z = 6 - 1x_2 - 2 x_3 - 3 x_4 - 4 x_5 - 5 x_6 - 6 x_7.$$
    We obtain ##Z = 6## if we set all ##x_2 = \cdots = x_7## equal to zero, but get ##Z < 6## if any of the variables ##x_2, \cdots, x_7## is ##> 0##. Therefore, the optimal solution is obtained as ##x = (1,0,,0,0,0,0).##
     
    Last edited: Jun 7, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Finding the maximum value of a sum involving several parameters
  1. Finding maximum value (Replies: 21)

Loading...