[Math] Linear Programming with target values.

linear programming

I'm trying to figure out the general solution to a min-max problem. The general form of the problem is as follows:

  x1 +   x2 + ... +   xn  = T
a1x2 + a2x2 + ... + anxn  = At * T
  x1                     >= 0
  x1                     <= T1
         x2              >= 0
         x2              <= T2
            ...
                      xn >= 0
                      xn <= Tn

Where T and At are target values supplied by the user.

a1..an are known multipliers for the variables x1..xn respectively.

T1..Tn are known maximum values for each variable x1..xn respectively.

This is essentialy a Multi-Objective Linear Programming problem. My objective is to get a value as close as possible to the target values T and At. The problem is, most linear programming problems try to maximize or minimize the result (in this case, it would be T and At), however my objective is to provide values for x1..xn that are as close to the particular values as possible.

My background in math isn't as strong as it probably should be, but I've been doing some research in order to solve this problem.

Would the best approach be to move the T and At * T values to the left hand side as constants, and try to minimize the function (ie. as close to zero as possible)? If that's the case, how would I approach this for a solution? Most of the examples for this kind of problem that I've seen do not have constants within the objective function. Are they just ignored in terms of the solution matrix? That means it's not that useful. Perhaps, ignore the constants, and compare the proposed solutions to those constant, and recalculate if they are outside of a basic tolerance, by adding additional constraints?

— EDIT —
based on @calculus suggestions, I have come up with the following.

I'm trying to use a simplex algorithm to solve this problem. The algorithm takes an MxN matrix of constraint coefficients ([A]), an M-length vector of constraint upper limits ([b]) and an N-Length vector of objective coefficients.

Can anyone confirm that the objects I'm using are correct:

c = [0, 0, ... 0, 1, 1, 1, 1]  

where the first part corresponds to the coefficients for x1..xn, and the last 4 1's correspond to the coefficients for y3+, y3-, y4+ and y4-.

b = [T1, T2, ..., Tn, T, AtT] 

where these are the upper limits for each individual x1..xn, and the solutions for the sum(xn), and sum(anxn) equations respectively.

A = 1, 0, ... 0,  0,  0,  0,  0
    0, 1, ... 0,  0,  0,  0,  0
          ...
    0, 0, ... 1,  0,  0,  0,  0
    1, 1, ... 1, -1,  1,  0,  0
   a1, a2,...an,  0,  0, -1,  1

where the first batch of rows correspond to the xn <= Tn rows, then 2nd last line corresponds to x1 + .. xn – y3+, + y3- = T and the last line corresponds to a1x1 + … anxn – y4+ + y4- = AtT

Does this make sense?

— Edit 2 —

I used a known problem with a solution to test this out.

T = 1000, At = 1.5, a1 = 5, a2 = 1, T1 = 500, T2 = 1000.

This can be solved arithmetically:

x + y = 1000,       (x1+..+xn = T)
5x + y = 1500       (a1x1+...+anxn = AtT)

results in x = 125, y = 875

so I created the matricies necessary:

b = [500, 1000, 1000, 1500]
c = [0, 0, 1, 1, 1, 1]
A = |1, 0,  0, 0,  0, 0|
    |0, 1,  0, 0,  0, 0|
    |1, 1, -1, 1,  0, 0|
    |5, 1,  0, 0, -1, 1|

but the solver I'm using says the program is unbounded.

Best Answer

Let

$x_1 + x_2 + ... + x_n=y_1$

and $a_1x_2 + a_2x_2 + ... + a_nx_n = y_2$ the two addtional constraints.

The provisional objective function would be $|y_1-T|+|y_2-At\cdot t|$ to calculate the sum of the two differences. It doesn´t play a role wether the differences are positive or negative or not.

To get rid off the absolute values, you have to define:

  1. $y_3=y_1-T$ and $y_4=y_2-At\cdot t$

The objective function is now $|y_3|+|y_4|$

  1. $|y_3|=y_3^++y_3^-$ and $|y_4|=y_4^++y_4^-$

And finally the objective function is

$\texttt{min} \ \ y_3^++y_3^-+y_4^++y_4^-$

Transforming $y_3$ and $y_4$

$y_3=y_3^+-y_3^-$ and $y_4=y_4^+-y_4^-$

The two additional constraints are

$x_1 + x_2 + ... + x_n=y_3^+-y_3^-+T$

$a_1x_2 + a_2x_2 + ... + a_nx_n = y_4^+-y_4^-+At\cdot t$

The variables are $x_i, y_3^+,y_3^-, y_4^+,y_4^- \geq 0$