The Graphic Palette is a firm in Charleston, South Carolina, that does graphic artwork and produces color and black- and-white posters, lithographs, and banners. The firm's owners, Kathleen and Lindsey Taylor, have been approached by a client to produce a spectacularly colored poster for an upcoming arts festival. The poster is more complex than anything Kathleen and Lindsey have previously worked on. It requires color screening in three stages, and the processing must proceed rapidly to produce the desired color effect.
By suspending all their other jobs, they can devote three machines to the first stage, four to the second stage, and two to the last stage of the process. Posters that come off the machines at each stage can be processed on any of the machines at the next stage. However, all the machines are different models and of varying ages, so they cannot process the same number of posters in the specified time frame necessary to complete the job. The different machine capacities at each stage are as follows:
Stage 1 Stage 2 Stage 3
Machine 1 = 750 Machine 4 = 530 Machine 8 = 620
Machine 2 = 900 Machine 5 = 320 Machine 9 = 750
Machine 3 = 670 Machine 6 = 450
Machine 7 = 250
Because the machines are of different ages and types, the costs of producing posters on them differ. For example, a poster that starts on machine 1 and then proceeds to machine 4 costs $18. If this poster at machine 4 is then processed on machine 8, it costs an additional $36. The processing costs for each combination of machines for stages 1, 2, and 3 are as follows:
Machine (cost)
Machine 4 5 6 7
1 $18 $23 $25 $21
2 20 26 24 19
3 24 24 22 23
Machine (cost)
Machine 8 9
4 $36 $41
5 40 52
6 42 46
7 33 49
Kathleen and Lindsey are unsure how to route the posters from one stage to the next to make as many posters as they possibly can at the lowest cost. Determine how to route the posters through the various stages for Graphic Palette to minimize costs.