1
$\begingroup$

I'm not sure if this question qualifies for this place, but I have a linear equation in the form:

$$\begin{array}{ll} \ Ax \geq b\end{array}$$

In VBA in excel.

with A = 11 rows, 4 columns, with random fractions between 0 and 1.

x = a 4 row, 1 column matrix and each $$\begin{array}{ll}\ x_i >=0 \end{array}$$ B is a 11 rows, 1 column matrix containing only 1's.

It appearently is a [linear program] (LP) and I will look into this.

$$\begin{array}{ll} \text{minimize} & x_1 + x_2 + x_3 + x_4\\ \text{subject to} & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.5 x_4 \geq 1\\ & 0.1 x_1 + 0.4 x_2 + 0.3 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.3 x_3 + 0.4 x_4 \geq 1\\ & 0.4 x_1 + 0.9 x_2 + 0.1 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.6 x_3 + 0.1 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.4 x_2 + 0.9 x_3 + 0.2 x_4 \geq 1\\ & 0.6 x_1 + 0.4 x_2 + 0.1 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.7 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.5 x_3 + 0.6 x_4 \geq 1\end{array}$$ I was wondering what the minimisation procedure whilst satisfying the equation, for the sum of all the x_1 to x_4 was.

I thought of taking the minimized summation of all the fractions in 1 row of matrix A and solving for that = 1, so that one would know all others are at least higher, but I was not sure, whether that is garanteed to provide the minimized sum of x's.

Also, that approach would yield infinitely many solutions with 1 row and 4 variables.

$\endgroup$
  • $\begingroup$ In case of linear (in-)equalities I apply the simplex algorithm. $\endgroup$ – callculus Oct 25 '16 at 23:57
  • 1
    $\begingroup$ What is the domain of $x_1,x_2,x_3$ and $x_4$ ? Is it $x_i \geq 0 \ \forall \ i\in \{1,2,3,4\}$ ? $\endgroup$ – callculus Oct 26 '16 at 0:18
  • $\begingroup$ Yes thank you, I forgot to add the constraints of the x_i's, Each x_i needs to be positive or 0. I am not sure what the upside down A means, but I think the above is what you ask, and that this answers your question. I shall also learn about the simplex algorithm, thank you. $\endgroup$ – Maximilian brutus III Oct 26 '16 at 0:33
  • $\begingroup$ Your guess is right. The meaning of $\forall i \ \in \ \{1,2,3,4\}$ is "for all i with the value of $1,2,3$ or $4$". $\endgroup$ – callculus Oct 26 '16 at 0:38
  • $\begingroup$ Thank you, I think I'm falling in love with this forum <3 $\endgroup$ – Maximilian brutus III Oct 26 '16 at 0:39
1
$\begingroup$

You have the following linear program (LP)

$$\begin{array}{ll} \text{minimize} & x_1 + x_2 + x_3 + x_4\\ \text{subject to} & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.5 x_4 \geq 1\\ & 0.1 x_1 + 0.4 x_2 + 0.3 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.3 x_3 + 0.4 x_4 \geq 1\\ & 0.4 x_1 + 0.9 x_2 + 0.1 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.6 x_3 + 0.1 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.4 x_2 + 0.9 x_3 + 0.2 x_4 \geq 1\\ & 0.6 x_1 + 0.4 x_2 + 0.1 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.7 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.5 x_3 + 0.6 x_4 \geq 1\\ & x_1, x_2, x_3, x_4 \geq 0\end{array}$$

Using PuLP,

from pulp import *

# decision variables
x_1 = LpVariable("x_1")
x_2 = LpVariable("x_2")
x_3 = LpVariable("x_3")
x_4 = LpVariable("x_4")

# define linear problem (LP)
prob = LpProblem("problem", LpMinimize)
prob += x_1 + x_2 + x_3 + x_4   # objective function
# add 4 nonnegativity constraints
prob += x_1 >= 0
prob += x_2 >= 0
prob += x_3 >= 0
prob += x_4 >= 0
# add 11 inequality constraints to the LP
prob += 0.2*x_1 + 0.3*x_2 + 0.9*x_3 + 0.5*x_4 >= 1   
prob += 0.1*x_1 + 0.4*x_2 + 0.3*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.3*x_2 + 0.3*x_3 + 0.4*x_4 >= 1
prob += 0.4*x_1 + 0.9*x_2 + 0.1*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.3*x_2 + 0.9*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.3*x_2 + 0.6*x_3 + 0.1*x_4 >= 1
prob += 0.2*x_1 + 0.3*x_2 + 0.9*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.4*x_2 + 0.9*x_3 + 0.2*x_4 >= 1
prob += 0.6*x_1 + 0.4*x_2 + 0.1*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.7*x_2 + 0.9*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.3*x_2 + 0.5*x_3 + 0.6*x_4 >= 1

# solve ILP
prob.solve()

# print results
print LpStatus[prob.status]
print value(x_1)
print value(x_2)
print value(x_3)
print value(x_4)

we get

Optimal
0.0
0.0
1.4285714
1.4285714
$\endgroup$
  • $\begingroup$ Thank you, I was unfamiliar with the syntax, but I incorporated it reasonably I think. And I will look into the wiki documentation in quest for my answer. $\endgroup$ – Maximilian brutus III Oct 26 '16 at 0:04
  • $\begingroup$ @MaximilianbrutusIII I updated my answer. $\endgroup$ – Rodrigo de Azevedo Oct 26 '16 at 0:13
  • $\begingroup$ Thank you, the curse of knowledge; I forgot to mention each x_i needs to be positive or 0. I added it into the question. At least I shall play with the above program in Python to learn about the algorithm so I can understand it, predict what will happen when I alter parameters, and eventually replicate it in my VBA code. $\endgroup$ – Maximilian brutus III Oct 26 '16 at 0:29
  • $\begingroup$ @MaximilianbrutusIII Excel's Solver can solve linear programs, I believe. $\endgroup$ – Rodrigo de Azevedo Oct 26 '16 at 0:35
  • $\begingroup$ I think indeed it can, but I thought humans would be better at explaining an algorithm than empirical results from a computer program. I would like to understand the logic and reasoning, then I have a higher flexibility in application and future problems. But looking into the simplex algorithm I think I will. Once again thank you for the concise example. $\endgroup$ – Maximilian brutus III Oct 26 '16 at 0:44
0
$\begingroup$

Each row, considered as equality, represents a 4-D plane, normal to the coefficient vector ($\mathbf a$), and the plane is "distant" $1$ from the origin (where "distance" is the dot product of the position vector of the points on the plane with $\mathbf a$ ) .
Each inequality represents then the half-space limited by the plane and containing points at "distance" larger than $1$ from the origin.
Since the coefficients are all positive, then an unlimited region of points whose projection on the various $\mathbf a$ is greater than $1$ surely exists.
On the average, the solution point closest to the origin will lay onto the $(1,1,1,1)$ direction.
So in your case the only simplification that I see feasible is to start and search for a point that lays on the direction of the resultant of the coefficients, and check the inequalities starting from those whose coefficient vector is more far from the average.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.