Finding different solutions to Linear programming problems

Question

I'm working on a program where I want to solve problems of the type:

$$Ax\leq b $$

Where $A$ is a $m\times n$ matrix with $a_{ij} \in \mathbb{R}$, $x \in \mathbb{R^n} $ and $b \in \mathbb{R^m} $.

With the following conditions:

• $\sum_{j=0}^n x_j= 1$
• $x_j\geq 0, \forall \,j\in J$
• $b_i\geq 0, \forall \, i\in I$

There's three kind of solutions i want to find:

• The one(s) that minimizes $x$
• The one(s) that maximizes $x,$ along with some indication of which $x_j$ that make it be maxed - see the example below I don't know how to describe this properly.
• The solution that is the closest to $x_j = \frac{1}{n}, \: \forall \,j\in J $

A very simple example:
given:
$\:A = (1.5, 0.2)$
$\:b=1$
I would want to find the following solutions:

• $S_1=\{x_1=0\quad \wedge\quad x_2=1\} $
• $S_2 =\{x_1=0.615\quad \wedge\quad x_2=0.385\},\quad$ "$x_1$ is the variable that makes this meet the limit".
• $S_3=\{x_1=0.5\quad \wedge\quad x_2=0.5\} $

I thought it would be straight forward by implementing the Simplex algorithm. But then i would need to have an objective function (don't I?) which I can't see that i have.
Can I construct Objective functions for the different cases I want to solve or any good suggestions on how to do this?
It might be worth mentioning that $\#J, \#I \leq 20$ and that I have never worked with linear programming before :)
Thanks.

*Edit*, yea what do i mean about max/minimizing..

Something like this:
$min\{c^T x\,|\, x\in \mathbb{R^n} \wedge Ax \leq b \wedge x,b \geq 0\}$
$max\{c^T x\,|\, x\in \mathbb{R^n} \wedge Ax \leq b \wedge x,b \geq 0\}$

I'm not really sure about the c vector but as far as i understand it's the one I'm missing? Most of what i know about LP is from here:
https://en.wikipedia.org/wiki/Linear_programming#

Answer 1

As pointed out by @Joppy and myself -- your objectives need to tweaked a bit to get this to an LP-formulation -- specifically the $L_1$ norm of $x-(1/n)\mathbf{1}$ seems to be what you are trying to get at with your examples.

$$L_1(x) = \sum_{i=1}^n|x_i-1/n|$$

With constraints:

$Ax\leq b$

$\sum_1^n x_i = 1$

$x_i \geq 0 \; \forall i \in 1..n$

You give a "constraint" for $b$ but I don't think this is what you want, as it will just set $b_i$ such that the constraint is never tight over the feasible region (effectively removing it from consideration). I think you meant that the RHS is a parameter that is always a non-negative vector (in non-negative orthant of $\mathbb{R^m}$)

With this there are two objectives we can pursue:

1. $\max L_1$: Maximize the extremeness/variability of the $x_i$ -- we want them as far from $1/n$ as possible. Since the components must sum to 1 and are positive, this will lead to most $x_i$ being close to $0$ and a few close to $1$ so $L_1$ is large. This will simultaneously maximize and minimize components of $x$, to your first two objectives.
2. $\min L_1$: Minimize the extremeness/variability of the $x_i$ -- this is precisely your third objective and minimizing $L_1$ above will get you there.