# How to solve the following problem with integer programming?

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.

## 2 Answers

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.