1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Optimization Problem. Hard!

  1. May 15, 2010 #1
    Goal: You want to train your Senior Manager. He needs skills:
    x1, x2, x3, x4, x5, x6, x7, x8, x9, x10.

    You are to choose from the following programs/courses that fulfills all the senior manager's skill needs at the cheapest cost.
    p1 has x1, x3, x4 at $500
    p2 has x3, x5, x9, x10 at $1000
    p3 has x2 at $ 600
    p15 has ......

    p1 conflicts with p2, p8.
    p2 conflicts with p1, p4, p10.
    . (.. This part can probably be inputted into our program later on, if we try and formulate the whole thing at once our brains will probably asplode.)

    3. attempt at a solution.

    Sorry, no deal! Have no idea how to formulate into a program :)
  2. jcsd
  3. May 15, 2010 #2
    This seems kind of standard for these types of problems, which have the form:

    Maximize/Minimize [itex] f(x_1,x_2,...,x_n) [/itex]
    subject to:

    You have something you want to minimize/maximize. What is it?

    You have constraints. Here you have two types of constraints. What are they? How can you write them down as equations in the usual constraint form?

    Then it's just a typical linear program.

    Try and work some of it out for us and then we can help you further.
  4. May 15, 2010 #3
    Thankyou for replying.

    If xi are the skills, MAXing or MINing f(x1,x2,x3...) doesn't work. The programs/courses (px) will have to be the decision variables. Beyond that and I'm wholly unsure.

    I've been trying for over a week, and have gotten zip. I can't do it.
  5. May 15, 2010 #4
    Yes, that's right. Programs should be the decision variables.

    Each one will be a 0 or 1 integer variable, right? If you take that class, then it's 1, if you don't then it's zero.

    Now you can write down an expression in terms of px that we are trying to minimize.
  6. May 15, 2010 #5
    Yep I've gotten this far.

    Constaints are confounding me, at the moment.

    I have:
    z = cost1*p1 + cost2*p2 + cost3*p3 + ... + cost15*p15,


    px = 0 or 1 (Binary).
  7. May 15, 2010 #6
    Yes, all that is right. Now you have two types of constraints.

    One type is that you need to make sure that each skill is covered.
    Now suppose we consider the first skill. If px are our decision variables, what equation can we write that ensures that x1 will be covered?

    If there are ten skills, that's ten constraints.

    The other type of constraint is the conflict of various classes with each other.
    Consider the first class. It says that p1 conflicts with p2 and p8. What equation can we write that ensures that we won't take both p1 and p2, for example?

    All these should just be in terms of px; there's no need to make explicit reference to the skills at all.
  8. May 15, 2010 #7
    SIGMApi1 = 1, where pi1 = all the programs that have skill x1 inside of it.
    SIGMApi2 = 1,

    I think you're a genius...


    Wow that's a real brain buster.

    p1 = 2y;
    p2 = 2(1-y);


    That doesn't work for this problem though.


    Last edited: May 15, 2010
  9. May 15, 2010 #8
    Almost right. But what if class 1 and class 2 both have skill x1 but are otherwise the most efficient setup because of the other skills they contain and their cost? Then the sum of p1 and p2 will be more than one, but that's okay. This is easily rectified by changing those constraints to inequalities, however.

    If we did pick two conflicting classes, what would be true of the sum of the p-values of those classes? Write inequalities that prevent us from picking more than one conflicting class.
  10. May 15, 2010 #9
    You are amazing. I'll deal with the other part of your post after this bit.



    Then the middle of the output is like this:

    10 2.000000 0.000000
    11 1.000000 0.000000
    12 1.000000 0.000000
    13 1.000000 0.000000
    14 0.000000 0.000000
    15 0.000000 0.000000
    16 1.000000 0.000000
    17 1.000000 0.000000
    18 1.000000 0.000000"

    How are some of the constraints 0? I put >=1 ?

    It's presented like this.
    ................... Programs that Interfere
    Program 1...... 3 5 8
    Program 2...... 3 7 10

    p1 + p3<=1;
    p1 + p5<=1;
    p1 + p8<=1;


    ^^ Infeasible. What the ef :(

    Those constraints are correct... wowowowowowow

    Last edited: May 15, 2010
  11. May 15, 2010 #10
    Hard for me to evaluate why that might be happening, what your software is doing, etc. It seems you are on the right track now, though, as far as formulating the linear program.
  12. May 16, 2010 #11
    It turns out that I had made mistakes in typing the correct constraints.
    I fixed them up, AND IT WORKED, PERFECTLY.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook