Optimization Problem. Hard!

E

endogenous

New member
Joined
May 15, 2010
Messages
6
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 ><
 
Do you have the rest of the constraints?. Excel Solver could be used to solve this.
 
Really! Wowee!

I don't think I need to provide the actual constraints/data, the above is made up anyways. I more have to figure out how to do it in LINGO or Solver. I can't figure out how to formulate it. The actual data can be inputted at any time.

Thanks for any help. :)
 
In LINGO, enter the objective function and constraints like so:

MODEL:
MIN=A+B+C+D+E+F+G+H+I+J;
A+C+D=500;
C+E+I+J=1000;
B=600;
F+G+H=700;
END

I made up a constraint and used yours just to illustrate. Add whichever ones you want.

With this I got, x2=600, x3=500, x6=700, x10=500, z=2300

Of course, add some more constraints to make it more interesting.

Does that help?. I take it 'conflicts' means the same variable is used in those constraints. That does not matter to LINGO when solving.

Perhaps I am misunderstanding.
 
galactus said:
In LINGO, enter the objective function and constraints like so:

MODEL:
MIN=A+B+C+D+E+F+G+H+I+J;
A+C+D=500;
C+E+I+J=1000;
B=600;
F+G+H=700;
END

I made up a constraint and used yours just to illustrate. Add whichever ones you want.

With this I got, x2=600, x3=500, x6=700, x10=500, z=2300

Of course, add some more constraints to make it more interesting.

Does that help?.
Click to expand...

THat's the Model I had, but that doesn't fit the question, which is why it's so hard to formulate.
That model doesn't allocate programs to the manager. We have to allocate the programs to the manager >.<.

I was thinking of an integer program with the courses/programs being the decision variables, but everything i've tried has failed.
 
Oh, I am sorry, I see what you mean now.

Have you tried a Traveling Salesman Problem?. The idea would be to find a tour through all the programs that would minimize cost.

Just a thought. I have a TSP LINGO program from way back if you would like it.
 
galactus said:
Oh, I am sorry, I see what you mean now.

Have you tried a Traveling Salesman Problem?. The idea would be to find a tour through all the programs that would minimize cost.

Just a thought. I have a TSP LINGO program from way back if you would like it.
Click to expand...

Yes! I would love it! Thankyou! How sure are you that this is a TSP program?

I'm don't think they'de give us a TSP problem. That's advanced. All we've done is normal linear programming, integer programming, transportation/transshipment/assignment problems, simulation problems and critical path problems.

I don't think it's transportation/transshippment/assignment (I've already tried transshipment, it didn't work out). I think it's just a standard LP or IP, but I can't figure out how to the constraints.

Could it be
MINIMIZE
z = cost1*p1 + cost2*p2 + ... + cost15*p15

s.t.
"..
..
.."

px = 0 or 1 (binary integer program)

?

What would be the constraints :s
 
I know how it is. You brainstorm trying to figure out whihc model to use. It looks like an assignment model. Perhaps a Knapsack Problem?.

As I get time, I will see what I can come up with. I know a little OR, but it has been a while. Conversely, I would be interested when you finally find it. I have various LINGO programs from some time back. I will look through them and see if any can be adjusted accordingly.

Anyway, here is the TSP program. It is for cities, but can be changed to suit needs

MODEL:
! Traveling Salesman Problem for the cities;
SETS:
CITY : U; ! U( I) = sequence no. of city;
LINK( CITY, CITY):
DIST, ! The distance matrix;
X; ! X( I, J) = 1 if we use link I, J;
ENDSETS
DATA: !Distance matrix. Does not have to be symmetric;
CITY= Gary FortWayne Evansville TerreHaute SouthBend;
DIST = 0 132 217 164 58 !Gary;
132 0 290 201 79 !FW;
217 290 0 113 303 !Evan;
164 201 113 0 196 !TH;
58 79 303 196 0; !SB;
ENDDATA


N = @SIZE( CITY);
MIN = @SUM( LINK: DIST * X);
@FOR( CITY( K):
! It must be entered;
@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;
! It must be departed;
@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;

!@FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:
! U( J) >= U( K) + X ( K, J) -
! ( N - 2) * ( 1 - X( K, J)) +
! ( N - 3) * X( J, K)
!);
);


@FOR( LINK: @BIN( X));

END
 
Thanks for that. I think I got
(A) The objective function
(B) the first constraint (not the one where you can't have interfering programs).

MIN=785.71*p1+2300*p2+900*p3+1325*p4+1200*p5+1150*p6+1450*p7+1166.67*p8+800*p9+1100*p10+985.71*p11+1933.33*p12+828.57*p13+2233.33*p14+2200*p15;

p1+p4+p5+p9>=1;
p1+p4+p5++p7+p9+p10>=1;
p1+p8+p10+p13>=1;
p1+p4+p5+p8+p13>=1;
p1+p9+p12>=1;
p3+p8+p14>=1;
.....................
BIN(p1);
BIN(p2);

(Making it 0 or 1)
...


It's working!!!!!
 
You must log in or register to reply here.
Top