I have an optimization problem, simply:

We have $2$ facilities and $7$ shops such that each facility produces $2000$ TV a month and each shop needs at least $500,100,800,400,700,200,1000$ TVs per month. Transportation from facility $1$ to a shop costs $4$ dollars per TV and from facility $2$ to a shop costs $6$ per TV. So, I have to minimize cost and the conditions must be satisfied.

If I am not wrong, the constraints and objective function must be as below. However, I am not sure how to solve the problem with integer programming without using simplex method. Here is what I wrote:

$x_{ij}$ : Number of TVs transported from facility i to shop j. Then we have,

minimize C = $\displaystyle 4\sum_{j=1}^{7}x_{1j} + 6\sum_{j=1}^{7}x_{2j}$

$x_{ij} \ge 0$

$\displaystyle \sum_{j=1}^{7}x_{1j} \le 2000$

$\displaystyle \sum_{j=1}^{7}x_{2j} \le 2000$

$x_{11} +x_{21} \ge 500$

$x_{12} +x_{22} \ge 100$

$x_{13} +x_{23} \ge 800$

$x_{14} +x_{24} \ge 400$

$x_{15} +x_{25} \ge 700$

$x_{16} +x_{26} \ge 200$

$x_{17} +x_{27} \ge 1000$

Thanks for any help.


This is a transportation problem. It can be solved through a simplified version of the simplex method. Hope the link helps. http://orms.pef.czu.cz/text/transProblem.html

Since this is an unbalanced problem, a dummy destination will have to be taken.


Well, if you don't use the Simplex method, just think of

$x_i$: what is shipped from the $i^{th}$ facility;
$0≤x_i≤2000$ and $x_1+x_2$ ≥ 3700;
Minimize $4*x_1+6*x_2$.

Plot a graph with $x_1$ and $x_2$ axis, draw a few lines, that's it.

A shop does not care where the TV comes from, as far as there are 2000 from the 1st facility and 1700 from the 2nd facility.

Hope this helps!


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.