Thread: Linear Programming

  1. #1
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743

    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?
    My Website

    "Circular logic is good because it is."

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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 . . . .
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    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.
    My Website

    "Circular logic is good because it is."

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Actually, there's only enough of B to make 6 M1s -- but I know what you mean.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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. #6
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    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.
    My Website

    "Circular logic is good because it is."

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linear algebra algorithm
    By Cogman in forum C++ Programming
    Replies: 3
    Last Post: 03-09-2009, 08:53 AM
  2. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  3. Question 39: Quicksort vs Linear Search
    By Kleid-0 in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 04-17-2005, 11:03 AM
  4. Linear Algebra API
    By curlious in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 01-13-2005, 05:34 PM
  5. linear search for structure (record) array
    By jereland in forum C Programming
    Replies: 3
    Last Post: 04-21-2004, 07:31 AM