you are right John....
SET TARGET : MIN
orig data 4x4 : named as Data
another 4x4 : named as CHG ----as the changing cells
another cell : named SUM ----FORMULA IS "=SUM(CHG)"
SAME OPTIONS
CONSTRAINTS
CHG=BIN
SUM=4
...thanks...
--
"Bright minds are blessed to those who share them.."-rsb.
:
Dana DeLouis wrote:
Hi Rick. Solver can do this, but you need helper cells.
Your data is in a 4*4 grid. (Let's name it "Data")
Make another 4*4 area nearby, and name it "Chg" (The Changing
cells)
Fill each cell in Chg with 1 for now.
Add a Target cell with the formula
=SUMPRODUCT(Data,Chg)
(We note that Target should now show the total of all the cells in
Data).
For Solver, minimize the Target cell, by changing the Chg cells.
Add the constraint that the Chg cells are Binary (Bin).
Not needed here, and (since this looks like homework for an OR/MS
course) possibly not desired. Assignment problems like this are a
special case of a network flow problem, and it is known that if all
constraints for such a problem are integral then the corresponding LP
has integral solutions, so you don't need to model it as an ILP.
But -
you would still need to check assume nonnegative and assume linear in
the options menu.
This limits the
cells to either 0 or 1. A "1" means that Solver picked that
combination.
However, we need to add Constraints to Chg cells. Each Row, and
each Column
in Chg can have only one "1".
Select the Chg table, but expand it by 1 column to the right, and 1
row
down. Hit the Autosum button, and delete the sum formula in the
lower right
corner.
You now have Sum formulas for each Row, and each Column.
For the vertical Sum formulas, add two constraints that this area
is <1.01,
and >0.99
For example, and the constraints like:
F7:F10 < 1.01
F7:F10 > 0.99
The reason for not using just F7:F10 =1 is that Solver can't really
work
with exact integers, so we allow for a little slack.
If the solver really can't handle equality constraints in a linear
integer programming problem
(which your formulation gives) then its implementation of the
branch-and-bound algorithm is seriously defective. Doesn't the Solver
have slack built in? I thought that was what the precision and
tolerance boxes in the options menu were for. I don't think there is
really any need to detract from the elegance of the model.
This doesn't affect
any results.
Also, you do not need to do this for each individual cell. Solver
applies
the constraint to each cell in Range F7:F10.
Now, add the same constraint for the horizontal sum Formulas.
Under Solver's options, place a check on "Assume linear model."
This allows
Solver to work faster on these problems.
I get the same results as Gary's Student.
I like to add Conditional Formatting to my Data area. I like to
use a
formula that if the corresponding cell in Chg is >0.5, then add
formatting
(Bold, Color, etc).
It's easier for me to see who does what, then looking at the table
of 1's &
0's.
Note that Excel's Solver is limited to only 200 changing cells.
This limits
an area to about 14*14 (=196). Solver is not very good using this
technique
when the problem is large.
You can write macros that can loop to find slightly larger
problems, but
it's not easy.
Let's look at 1 possible problem if we "assign the task to the most
efficient worker for that task."
These are hard to spot when the problem is large.
Two people (A & B), and 2 tasks.
A can do each task in {3,5} minutes.
B can do each task in {7,1000} minutes.
A is more efficient at the first task. B gets remaining task.
Total time: 3+1000 = 1003 minutes.
However, if we start by looking at the most inefficient, and give
the first
task to B, and the remaining task 2 to A, then total time is 7+5 =
12
minutes.
This is what makes it difficult.
Anyway, hope this helps.
--
Dana DeLouis
Windows XP & Office 2003
Hello, I am new to this group and hope you can help me. I have a
problem that I am trying to solve.
I am trying to use solver but not sure if I am setting up the
model
correctly.
I have 4 workers Sam, Avery, Ben, and Steve and 4 different
duties
(Engine, Trans, Alignment, & Brakes) that the can be performed.
Each
person has a different average time(mins) to complete each task.
I am
trying to develop the formula to optimize who should do what to
get the
lowest amount of time.
Engine Transmission Alignment Brakes
Sam 45 34 23 45
Avery 48 30 36 37
Ben 30 48 40 41
Steve 38 34 30 31
Thoughts on the formula and contraints?