In the year 1250 B.C, Egyptian Pharaoh Ramses II commissioned a granite causeway (elevated road) to be built from the gates of the temple at Karnak down to the east bank of the Nile River. The causeway will commemorate the Pharaoh's triumphs at the battle of Kadesh, so he insists it be completed before the scheduled visit of several kings from that region. This means that Imhotep, the Chief architect of Public Works of Ramses II, has exactly six months to finish the project. The project is fairly simple: Imhotep 8 needs to transport a total of 7,000 carefully carved blocks from the granite quarries of Lower Egypt, downstream to the current site at Karnak. The stonemasons at Karnak do not need all 7,000 blocks at once; rather, the monthly requirements of the granite blocks are shown in table 1:

Table 1: Monthly requirements of granite blocks

Month

1

2

3

4

5

6

Blocks Required

700

700

1,000

1,200

2000

1400

The requirements of the stonemasons must be met. Imhotep has a choice of two granite quarries from which to purchase his blocks: the quarry at Deir El Medinah, which can produce a maximum of 800 blocks a month for the next six months, or the quarry near Fayum, which can produce a maximum of 1400 blocks a month during months 1, 2, 3 and 6. Unfortunately, the annual flooding of the Nile River, which will happen during months 4 and 5, makes the Fayum quarry inaccessible during that time. Hence production during those months is zero (at Fayum). In addition, while the stonemasons at Karnak do not mind having more blocks than they need in a given month, they cannot have more than 1,200 blocks "left over" at the end of a month, due to space considerations.

Imhotep needs to decide how many blocks to have delivered to Karnak each month. He also needs to decide on which quarry to order those blocks from - he is free to order blocks from both quarries in the same month, if he wishes. His objective is to minimise the cost of the entire project. The labour costs involved in moving a single block of granite can vary, according to the month. In months 1 through 3, Imhotep must rely primarily on the Pharaoh's military to do the transporting: they will charge the modern day equivalent of Rs 15000 per block moved from either quarry to Karnak. In months 4, 5 and 6, Imhotep does not have to contract with the military; the flooding of the Nile will leave all local farmers idle, they will move as many blocks as he wants for the equivalent of Rs 7500 per block. In addition to the transportation costs, Imhotep must consider the actual purchase price of the blocks: the quarry at Deir El Medinah charges Rs 200,000 per block it produces, while the Fayum quarry charges Rs 225,000 per block it produces. Finally, it costs Rs 1000 per block "left over" at the end of the month in inventory carrying costs.

Assuming that blocks produced during a particular month can be transported and used during the same month, formulate Imhotep's problem as a linear programming model. what will be the decision variables and constraints and how to label them.