How many slack variables need to be introduced

algorithmsconvex optimizationlinear programmingoptimization

So I was trying to solve this exercise (from DPV book)
enter image description here

I modeled the problem as such:
minimize : $4x_1 + x_2 + 2x_3 + 3x_4 $ s.t:
$ x_1 + x_2 = 8 $ (Mexico's production)
$ x_3 + x_4 = 15 $ (Cansa's production)
$x_1 + x_3 \geq 10$ (delivered to New York , I am not sure about the enequality)
$ x_2 + x_4 \geq 13$ (delivered to Cal , again: I am not sure about the enequality)

My problem is that if I follow this model then in order to convert the LP into standard form I am going to introduce 2 slack variables. But 2 slack variables are less than my number of equations $m = 4$ and my initial base will only have 2 variables meaning that I will never be able to find the values of the 4 (x_1, x_2, x_3, x_4) .
If I try to remove the enequalities (since I know how much product these towns consume I have no reason to deliver more) but then I have no slack variables and the system has a unique solution (or it is impossible) which would not make sense for an optimization problem .
If I try to add enequalities in order to reach 4 slack variables , it does not make conceptual sense to me . Will it be $\geq$ or $\leq$ for the production? I have no clue…

Can you help me identify what I am thinking wrong?
First of all, mathematically speaking in order this LP to be bounded and solvable I need 4 slack variables ?

Best Answer

Let $x_{ij}$ the amount schnuppels of duckwheat which are delivered from location $i$ to location $j$, where $k,n,c,m$ denote the corresponding locations Kansas, New York, California and Mexico. Kansas can deliver at most 15. Thus the tranportation constraints (supply) is $x_{kn}+x_{kc}\leq 15$. Similar for Mexico: $x_{mn}+x_{mc}\leq 8$. For both constraints you need a slack variable each to obtain equalities. For New York and California you have demand constraints, thus at-least-constraints. I agree with your constraints.

$$x_{kn}+x_{mn}\geq 10, \quad x_{kc}+x_{mc}\geq 13$$.

For both constraints you need a surplus variable each and probably artificial variables if you apply the simplex algorithm. I agree with your objective function as well.

Related Question