# Optimization problem

• December 14th 2008, 02:12 AM
Rapha
Optimization problem
Hello everybody!

I could really use some help here:

$a \in \mathbb{R}^n, \ e^T = (1,...,1) \in \mathbb{R}^n, \ x \in \mathbb{R}^n$
$b \in \mathbb{R}$

Solve the following optimization problem

$\max \ e^T x$, where $a^T x \le b \mbox{ and } x \ge 0$

I hope, someone knows how to do this.

Best wishes,
Rapha
• December 14th 2008, 10:59 AM
CaptainBlack
Quote:

Originally Posted by Rapha
Hello everybody!

I could really use some help here:

$a \in \mathbb{R}^n, \ e^T = (1,...,1) \in \mathbb{R}^n, \ x \in \mathbb{R}^n$
$b \in \mathbb{R}$

Solve the following optimization problem

$\max \ e^T x$, where $a^T x \le b \mbox{ and } x \ge 0$

I hope, someone knows how to do this.

Best wishes,
Rapha

This is a linear program and the maximum occurs at a vertex of the simplex defined by the constraints:

$a^T x \le b \mbox{ and } x \ge 0$

(it may occur at multiple vertices, and so on the line, surface or whatever conecting those vertices, but that is not needed to find the maximum)

CB
• December 15th 2008, 03:33 AM
Rapha
Hello CaptainBlack,
$\max \ e^T x = \max \ (1,…,1)^T \begin{pmatrix} x_1 ; x_2 ; ... ; x_n \end{pmatrix} = \max \ (x_1 + x_2 + ... +x_n)$
$a^T x = a_1 x_1 + a_2 x_2 + … a_n x_n \le b$