# Linear Programming

This is a discussion on Linear Programming within the A Brief History of Cprogramming.com forums, part of the Community Boards category; So I just got out of an exam, and one of the problems basically just killed me. It had to ...

1. ## Linear Programming

So I just got out of an exam, and one of the problems basically just killed me. It had to do with linear programming and the simplex method.

I know how to do the simplex method really well (like a pro), but for the life of me I couldn't formulate a linear system from the problem that was given to us!

Here is the problem (don't worry the exam is over for all students so I can talk about the problem just fine):

We have a factory that makes Medicine 1 and Medicine 2. There are 3 chemicals that go into these medicines: A, B, and C. The factory has 10 units of A, 6 units of B, and 7 units of C in stock. To use a unit of A, B, or C it costs \$10, \$20, and \$30 respectively. One unit of Medicine 1 takes 1 unit of A and one unit of B. One unit of Medicine 2 takes one unit of A and one unit of C. Medicine 1 thus costs \$30 to make, and Medicine 2 thus costs \$40 to make. Each medicine is then sold at a price of \$50.

What is the maximum profit that factory can make?
It is a linear programming maximization problem. I need to first form a linear system out of it, and then use the simplex method to solve....but I no matter how hard I tried I couldn't form a linear system.

Here is what I tried:

We are maximizing profit, so I said:

max: p = 50x - 30y - 40z

Because we want to maximize profit (p) where x is the number of medicine units we sell total, y is the units of medicine 1 produce, and z is the units of medicine 2 produced. Does that seem correct, or did I do that wrong?

Then after thinking about for about 30 minutes, I put these constraints in:

x <= 10
y <= 7
z <= 6

But even after adding those constraints....it just doesn't seem right.

Does anyone else here have an idea on how to form the correct linear system?

2. You could do it like this:
Code:
`p = 20m + 10n`
where p is maximum profit, m is Medicine 1, and n is Medicine 2. So, \$20 is earned for each M1 sold, and \$10 for each M2.

Because you can basically ignore how much B and C you have -- the quantity of A dictates what you can make, because M1 and M2 both need A -- you'd need something like this:
Code:
`m + n = 10`
There m is the number of M1s and n is number of M2s. 10 is the quantity of A.

Ah, never mind.

To solve this problem, you actually only have to notice that because of A, you can only make 10 medicines, each of which can be M1 or M2. Since you make the most profit making M1, make all M1s!

Assuming I haven't overlooked something . . . .

3. Well that's the answer I put down in the end. I said they should make 7 M1s and 3 M2s....because we only have enough of chemical B to produce 7 M1s total...and then we use the rest of the A's along with some of chemical C to make some M2s.

Even though I believe it to be correct, I still wasn't able to get a correct linear system going with a correct maximization problem and constraints, and I would really like to figure that out.

4. Actually, there's only enough of B to make 6 M1s -- but I know what you mean.

5. So the target function is right: 20x+10y (to maximize). Constraints: x+y<=10; x<=6; y<=7; and of course x,y>=0. So corners are (0,0), (6,0), (0,7), (6,4), and (3,7).

6. Ah I see. Thanks.

Man....that question was worth a lot of points....grrr

If I had been able to form the target function and get the constraints right, running the simplex method is easy.

7. The rule of thumb I always give students is that, whatever they're asking for as the answers have to be the variables (in this case production/sales of medicine), and everything else leads to a constraint (A, B, and C, so three constraints).