# Linear programming problem

In the next season the harvesting amount is estimated at 900 for farm A, 1200, 1500, 1800 for farm B,C and D respectively.

In this scenario I'm asked to minimize the maintenance costs. Unfortunately I can't solve it.

Denoting $s_i$ as the harvesting machine; senior 1,2,3

I've made the obvious constraint: $$s_1,s_2,s_3 \geq 0$$

But I'm not sure how to handle the fact there are 6 machines of each type and how to involve the estimated amount....

I want to minimize these costs: $$16s_1+13s_2+15s_3$$ $$20s_1+29s_2+25s_3$$ $$40s_1+38s_2+42s_3$$ $$37s_1+49s_2+45s_3$$

Can someone help me out?

Edit: and what is in this case parameter/variable? I seem to mix them up quite often...

I can help you with the constraints.

You can't have more than 6 of any machine:

$$0 \leq s_1,s_2,s_3 \leq 6$$

The machines must be able to harvest at least the estimated amount:

$$250s_1+200s_2+230s_3 \geq 900$$ $$270s_1+350s_2+300s_3 \geq 1200$$ $$490s_1+470s_2+520s_3 \geq 1500$$ $$460s_1+630s_2+550s_3 \geq 1800$$

It seems that a better way to approach this problem is to use a different variable for each machine on each farm. I am going to use the simplex algorithm. So, if $w$ is our total cost, we will be trying to minimize the equation:

$$w = 16x_1+13x_2+15s_3+20x_4+29x_5+25x_6+40x_7+38x_8+42x_9+37x_{10}+49x_{11}+45x_{12}$$

Where $x_1$ is machine type 1 on farm A, $x_2$ is machine type 2 on farm A, etc. By adding "surplus" variables, we can get rid of the inequalities we had above, so:

$$250x_1+200x_2+230x_3-s_1 = 900$$ $$270x_4+350x_5+300x_6-s_2 = 1200$$ $$490x_7+470x_8+520x_9-s_3 = 1500$$ $$460x_{10}+630x_{11}+550x_{12}-s_4 = 1800$$

And since we still can't use the same machine on more than one farm at a time, we have to restate our other constraint, this time with "slack" variables:

$$x_1+x_4+x_7+x_{10}+s_4 = 6$$ $$x_2+x_5+x_8+x_{11}+s_5 = 6$$ $$x_3+x_6+x_9+x_{12}+s_6 = 6$$

We use our original equation with all of the constraints to produce our tableau. It's a big matrix; I'm sorry if it doesn't render correctly.

1   0   0   1   0   0   1   0   0   1   0   0   1  0  0  0  0  0  0  0  6
0   1   0   0   1   0   0   1   0   0   1   0   0  1  0  0  0  0  0  0  6
0   0   1   0   0   1   0   0   1   0   0   1   0  0  1  0  0  0  0  0  6
250 200 230 0   0   0   0   0   0   0   0   0   0  0  0  -1 0  0  0  0  900
0   0   0   270 350 300 0   0   0   0   0   0   0  0  0  0  -1 0  0  0  1200
0   0   0   0   0   0   490 470 520 0   0   0   0  0  0  0  0  -1 0  0  1500
0   0   0   0   0   0   0   0   0   460 630 550 0  0  0  0  0  0  -1 0  1800
16  13  15  20  29  25  40  38  42  37  49  45  0  0  0  0  0  0  0  1  0


By using one of several online calculators, we get the optimal solution $w = \frac{5306}{13}$ when: $x_1 = \frac{14}{9}, x_2 = {23}{9}, x_3 = 0, x_4 = \frac{40}{9}, x_5 = 0, x_6 = 0, x_7= 0, x_8 = 0, x_9 = \frac{75}{26}, x_{10} = 0, x_{11} = \frac{20}{7}, x_{12} = 0$

However, in reality we can't have fractions of a machine, so this answer will have to be further refined by using a cutting plane technique (you can't necessarily just round up). Unfortunately, I did not find a calculator that does this.

• I tried to solve for these constraints but found values that don't fit the 1st constraint. I find something like $s_1=8,....$ so must be doing something wrong by just solving for these inequalities...? – Bob Mar 7 '13 at 11:43
• Are you able to answer my edit? I guess I'll check the actual solving later with my teacher then ;) – Bob Mar 7 '13 at 20:22
• @Bob The solution I found might be overkill, depending on what your teacher had in mind. – Alex Mar 7 '13 at 21:02
• wow i think this indeed is overkill haha. Do you think you can explain me which of the items are variable, and which are a parameter? – Bob Mar 7 '13 at 21:05
• No, I'm not sure what the distinction is in this context. – Alex Mar 7 '13 at 21:22