0

In a linear programming problem, how to define an optimzation function so that solution is equally distributed between the variables. For example, x + y = 10, I want an optimization function to make sure that x and y are close, here it will be 5, 5.

I'll give an example, there are x_n type of cars, each car requires a component in variable amount, the total number of available components is C, the equation representing this can be: 2x_1 + 3x_2 = C,

I want a solution where the x_1 and x_2 are evenly distributed.

Suppose

2x_1 + 3x_2 = 8

, solutions can be:

x_1 = 4, x_2 = 0

x_1 = 1, x_2 = 2

I want to optimize the problem to get the second solution, because the values are more close to each other. Or the deviation between the variables is less. Can I use LP to solve this.

Aravinda Kumar
  • 1
  • 1
    (1) Add the Criteria that $x=y$ (2) Add the Criteria : $\min |x-y|$ (3) Add the Criteria $x-y=z$ with $\min |z|$ (4) There are too many variations (5) You might give some Concrete Example in your Post then we can try to give Concrete Solution. – Prem Nov 10 '22 at 07:59
  • I'll give an example, there are x_n type of cars, each car requires a component in variable amount, the total number of available components is C, the equation representing this can be: 2x_1 + 3x_2 = C, I want a solution where the x_1 and x_2 are evenly distributed.

    Suppose 2x_1 + 3x_2 = 8, solutions can be: x_1 = 4, x_2 = 0 x_1 = 1, x_2 = 2

    I want to optimize the problem to get the second solution, because the values are more close to each other. Or the deviation between the variables is less. Can I use LP to solve this. Updated the question body also.

     – Aravinda Kumar Nov 10 '22 at 08:16
  • In that Case , my Previous Comment is satisfactory , where (2) & (3) will work. You want Integer values hence Integer Programming might be necessary here. – Prem Nov 10 '22 at 08:35

1 Answers1

0

You cannot use pure linear programming for this kind of problem, because variables are requested to have integer values. As was said in a comment, this requires integer programming, or mixed integer programming (MIP) if you also have continuous variables.

However this is not a major problem because most LP solvers also deal with MIP. Performance will be degraded, but if your problems are those of car equipment, you will have a few hundreds variables and constraints, which is nothing for most solvers.

Now, the way to deal with constraints "these resources shall be as evenly distributed as possible". We cannot put $\min |x-y|$ in the objective function because this is not linear. But we can make it linear by introducing variables such as $a$ and $b$ below:
$x - y - a \le 0$
$y - x - b \le 0$
$a \ge 0$
$b \ge 0$
and put $a$ and $b$ in the linear objective function with some coefficient. The coefficients can be be different between $a$ and $b$ if there is some dissymetry in the preferences; they can also be different from the coefficients of variables introduced for other car components, if equal distribution is more important for some components.

Jean-Armand Moroni
  • 5,632