# Homework Help: Finding the maximum value of a sum involving several parameters

1. Jun 7, 2017

### moriheru

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. Jun 7, 2017

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.

3. Jun 7, 2017

### moriheru

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!

4. Jun 7, 2017

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.

5. Jun 7, 2017

### moriheru

Sorry my mistake it is 6a1 and not 6/a1. I am sorry, this is turning out to be quite a mess...

6. Jun 7, 2017

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.

7. Jun 7, 2017

### Ray Vickson

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.

8. Jun 7, 2017

### moriheru

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?

9. Jun 7, 2017

### Ray Vickson

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.

10. Jun 7, 2017

### moriheru

Thank you so much!

11. Jun 7, 2017

### Ray Vickson

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