Results 1 to 4 of 4

Math Help - Optimization Problem. Hard!

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    2

    Optimization Problem. Hard!

    This problem is killing me!

    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.)

    I feel like dying when trying to formulate this.
    Please help ><
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    May 2010
    Posts
    1,030
    Thanks
    28
    I assume your looking for a mathematical solution, rather thanjust gong through the options one a a time and finding the cheapest (that may be quicker)

    You want to minimise the total cost of training subject to a long list of constraints. Define the following variables:

    q_i~~~~~ i=(1,...,n) flags to indicate if each training was purchased
    p_i the cost of each training
    Z_{ij} indicates if training i gives you skill j


    You want to minimise the total cost, subject to having all skills learned.
     min  \sum{q_{i}p_i}

    subject to: Learning every skill
     \sum{q_iZ_{i1}} \ge 1~~~~~ (skill 1 must be learned at least once)
     \sum{q_iZ_{i2}} \ge 1~~~~~ (skill 2 must be learned at least once)
     \sum{q_iZ_{i3}} \ge 1~~~~~ (skill 3 must be learned at least once)
    ...etc

    Subjec to: Constraints for program conflicts:
    q_1+q_2 \le 1~~~~~ (training 1 and 2 cant BOTH be taken)
    q_1+q_8 \le 1~~~~~ (training 1 and 8 cant BOTH be taken)
    q_2+q_4 \le 1~~~~~ (training 2 and 4 cant BOTH be taken)
    q_2+q_{10} \le 2~~~~~ (training 2 and 10 cant BOTH be taken)

    Subject to: More attendance constraints:
    q_1 \le 1~~~~~ (you can take training 1 at most 1 time)
    q_2 \le 1~~~~~ (you can take training 2 at most 1 time)
    q_3 \le 1~~~~~ (you can take training 2 at most 1 time)
    ...etc

    Subject to: No negative answers
    q_1 \ge 0
    q_2 \ge 0
    ..etc

    in principle, you can drop the "more attendance constraints" and get the same answer, because atttending the same program twice wont add any more skills but will increase the cost, so cant be the optimal solution

    Hope that helps, dont ask me to solve it!!
    Last edited by SpringFan25; May 23rd 2010 at 03:41 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    May 2010
    Posts
    43
    Ah... this is actually a trick question.. Senior Managers cannot be trained!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    This seems like a good candidate for a backtracking algorithm. I think you can approach it in a pretty straightforward manner using recursion and returning whenever a condition is not met, or whenever your current total cost exceeds the current minimum you've obtained. You'll probably want to use an array/list or multiple arrays/lists to keep track of things as an argument in your recursive function, and be sure to make deep copies as opposed to shallow copies. I would offer to help with the program itself but I have a busy week and wouldn't be able to help you until the weekend. Good luck.

    Note: If you write some code, I can take a look, but I won't have time to actually produce code for you this week.

    Edit: I used a backtracking approach on this thread, not sure if it would be a useful example for you.
    Last edited by undefined; May 24th 2010 at 06:54 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A really hard Optimization problem
    Posted in the Calculus Forum
    Replies: 7
    Last Post: November 26th 2008, 06:08 PM
  2. this problem is hard see if you can help me out
    Posted in the Trigonometry Forum
    Replies: 7
    Last Post: July 9th 2008, 11:48 PM
  3. HArd problem?
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: February 24th 2008, 07:39 PM
  4. Help Now Please hard problem!!!
    Posted in the Statistics Forum
    Replies: 1
    Last Post: December 11th 2007, 06:28 AM
  5. Hard problem
    Posted in the Algebra Forum
    Replies: 0
    Last Post: December 10th 2007, 12:54 PM

Search Tags


/mathhelpforum @mathhelpforum