# Minimizing shipping cost under given constraints

I have a question that has been bugging me for about a day now.

A manufacturing company receives orders for engines from two assembly plants. Plant I needs at least 45 engines and Plant II needs at least 32 engines. The company can send at most 120 engines to these assembly plants. It costs 35 per engine to ship to Plant I and 40 per engine to ship to plant II. Plant I gives the manufacturing company 20 in rebates towards its products for each engine they buy, while plant II gives similar 15 rebates. The manufacturer estimates that they need at least $1500 in rebates to cover products they plan to buy from the two plants. How many engines should be shipped to each plant to minimize shipping costs? What is the minimum cost? How many engines should be shipped to each plant to minimize shipping costs, subject to the given constraints The number of engines to send to plant I is? The number of engines to send to plant II is? What is the minimum shipping cost? • The company receives orders for engines, but plant I needs engines? I'm confused. Is the plant making engines, or consuming engines? – Emily Feb 17 '14 at 17:14 • This is what was confusing me as well. I think I have a start here. I believe, the manufacturer is selling the engines, and they are trying to reach 1500 in rebates. So the question wants to know how much engines it should send to each plant to reach 1500, while minimizing costs. – Aszula Feb 17 '14 at 17:37 • So the plants are consuming engines. – Aszula Feb 17 '14 at 17:45 • Ok, I understand more now. Let me try to formulate the answer. – Emily Feb 17 '14 at 17:47 ## 1 Answer Let's define two variables,$C$representing cost, and$R$representing rebate. Define$P_1$as the number of engines sent to plant 1, and$P_2$as the number sent to plant 2. We can write cost as: $$C = 30P_1 + 40P_2.$$ Likewise, we can write rebates as: $$R = 20P_1+10P_2.$$ We want to minimize$Csuch that: $$P_1 + P_2 \le 120, \\ 20P_1+10P_2 \ge 1500.$$ This gives us a linear program: \begin{align*} \textrm{minimize:} & 30P_1+40P_2 \\ \textrm{subject to:} & P_1 +P_2 \le 120 \\ & 20P_1+10P_2 \ge 1500. \\ & P_1 \ge 45 \\ & P_2 \ge 32 \end{align*} We could introduce slack variables and change the inequality constraints to equality constraints, but this is a pretty simple 2-variable case. Let's draw a cartesian plane, withP_1$as the$x$-axis, and$P_2$as the$y$-axis. The first constraint can be written as: $$P_2 \le 120-P_1,$$ and the second as $$P_2 \ge 150-2P_1.$$ Plotting all of these curve to generate the feasibility region gives us: Since we know that the linear program has solutions only at the vertices of the feasibility region, we can simply check all points:$(45,75), (88, 32), (59,32), (45,60)$. It should be clear that$(45,60)$will have less cost than$(45,75)$, and it should also be clear that$(59,32)$will have less cost than$(88,32)$. It is a simple task to see that$(59,32)$has less cost than$(45,60)$. For$(59,32)$we get a rebate of$20\cdot 59+10\cdot 32 = 1500$for a cost of$30\cdot 59+40\cdot 32 = 3050\$.

• You can easily solve for all the vertices of the feasibility region by solving a few linear equations. I skipped that step. – Emily Feb 17 '14 at 18:41
• Thanks for this, much easier to follow than the textbook for this course. – Aszula Feb 17 '14 at 18:43
• Note: For some reason, I had put the rebates from plant 2 at 10 per engine, instead of 15. But the idea is the same. – Emily Feb 17 '14 at 21:10