An offset lithographer has to print differnt verions 20 thousand, 74
thousand, 145 thousand, 148 thousand, 278 thousand and 187 thousand
pieces...
He puts these six versions onto three form.
He can put 12 items on a form.
How many of each version does he put on each form and how many of each
form does he print to make the exact count?
Can you create a general solution?

---

Request for Question Clarification by joey-ga on 30 Dec 2004 17:09 PST

Hi there.  Do you think you may be able to better explain the problem?
 Before I can figure out a mathematical solution, it would help to
better understand what you mean by:

* the numbers for each version (is this the # printed, or an item number?)
* "form" (what is this?)

---

Clarification of Question by norman9-ga on 31 Dec 2004 09:46 PST

Let's say a lithographer can print 12 letterheads on a single sheet.
Let's say his customer has 6 offices he wants various quantities of
letterheads for.
Let's say the lithographer does not want 6 different forms, but would
like to reduce his setup costs by printing on 3 forms.
How many sheets of each form would he print and how many up of each
type of letterhead would he impose on each form?
This is a really tough problem, at least for me it is.

---

Request for Question Clarification by joey-ga on 31 Dec 2004 15:57 PST

Do you want this for practical usage or for academic reasons?

I used the Excel solver function to find a possible solution (there
are a number of possible "reasonable" solutions).  If this is for
practical purposes, I can provide you with the solution it suggests. 
It gets some of the quantities exactly equal to those required for
each office, but some are over by a few thousand.  It has managed to
do this while keeping the total number of 12-letterhead sheets printed
to no more than 73,000.

Please let me know if you want this practical result.  As far as an
academically "true" solution, I don't think there is a clear method
for an exact answer.  Any solution will involve a significant number
of iterations through an extended process to narrow down options. 
This is what Excel did, and it took it several thousand iterations.

--Joey

---

Clarification of Question by norman9-ga on 02 Jan 2005 03:26 PST

This is a business problem. I make envelopes for a living and we have
a 28 x 40 5 color offset press. I do need exact or best answers as I
can come up with "good" answers right now by fooling around with a
spreadsheet.

As I mentioned above, this sort of "optimization" problem can't be
reduced to a simple general solution -- instead, they can only be
solved by multiple iterations through a solving process (a
"heuristic").  Luckily computers make this relatively simple and
quick.

In this case, the "optimal" solution appears to be the following:

Assign the six items (offices) letters A-F with the following requirements:
A: 20,000
B: 74,000
C: 145,000
D: 148,000
E: 278,000
F: 187,000


The forms should assign the following number of spots to each of the items:

Form 1:  PRINT 27,177 copies
   C (1 spot)
   E (7 spots)
   F (4 spots)

Form 2:  PRINT 37,000 copies
   B (2 spots)
   C (3 spots)
   D (4 spots)
   E (2 spots)
   F (1 spot)

Form 3: PRINT 6,882 copies
   A (3 spots)
   C (1 spot)
   E (2 spots)
   F (6 spots)

This results in the following number of each item provided:
A: 20646  (over by 646)
B: 74000
C: 145059 (over by 59)
D: 148000
E: 278003 (over by 3)
F: 187000

It requires a total number of 71,059 sheets to be printed (exceeding
the theoretical minimum of 71,000 sheets by only 59).

------

To achieve this result, I downloaded Lindo's free-trial What'sBest
add-in for Excel.  It works like Excel's Solver function to solve this
type of problem, but is far faster and gives better results.  I set up
the spreadsheet as necessary and then let it run for about 40 minutes
(in the background while I did other things), and it came to this
solution.  After about 5 minutes, it had come up with a good solution
that required 71,300 sheets, but over the next 35 minutes it found
ways to reduce that to the optimal values shown above.

This trial version is free and will work forever, but it is limited to
30 integer variables at a time.  This should suit you well, as it only
took 21 integer variables to solve this problem.

It can be downloaded from:
    http://www.lindo.com/cgi/frameset.cgi?leftwb.html;wbf.html

------

The spreadsheet I created and used with the What'sBest add-in can be
found at the following URL:
     http://69.61.18.4/temp/norman-9/lithographers_solution.xls

It will be available until Wednesday, January 5th at 5:00pm EST. 
Please download it before then if you would like it.

If you need some assistance setting up a spreadsheet for use with the
What'sBest software, please let me know, and I can walk you through
how to do it with your next printing problem.

If you have any questions or anything is unclear, please let me know.

--Joey

Strategy:
    My personal knowledge of Excel and optimization strategies
    Google: excel advanced solver freeware

---

Request for Answer Clarification by norman9-ga on 06 Jan 2005 09:37 PST

Joey
Sorry about the delay in responding.
The 100% answer is:
20       1    0    0
74      2    0    2
145    3     1    3
148    4    2    0
278   2    4    6
187    0    5    1
         20  34  17
Your answer is very good, though.
I tried Lindo/What's Best over ten years ago, but could not figure it out.
It is now Thursday, so I may not be able to download your solution.
I'll contact you one way or the other.
Thanks,
Norman

---

Clarification of Answer by joey-ga on 06 Jan 2005 21:49 PST

I'm glad I could help, though I'm sorry I didn't hit on the true
optimal solution (I guess this was more of a test to see how it could
be found).

If I'd let the What'sBest add-in run longer, I imagine it eventually
would have found it, but after forty minutes it wasn't improving much
-- it just hadn't iterated to that point yet.

The spreadsheet I created is still up if you haven't gotten it -- I'll
leave it for a few days.  And please let me know if you have trouble
figuring out how to use the Lindo software -- I can walk you through
it.

Take care.

--Joey

Joey solved a problem I've been screwing around with for about 20 years.
Thank you very much.