Network Optimization
Assignment
- This part of the assignment is based on the paper Jean-Claude Pi-card, Maximal Closure of a Graph and Applications to Combinatorial Problems, Management Science, v 22, no 11, pp 1268 - 1272.
- Students can do this part of the assignment in group of three.
- This part of the assignment should be submitted as a LINGO file.
QUESTION Consider an open pit mine partitioned into blocks. Let B be the set of all blocks. For each block b ∈ B, let
- x(b), y(b), and z(b) be the coordinates of this block;
- p(b) be the profit associated with this block.
For each block b, the coordinates x(b), y(b), z(b) are positive integers and the profit p(b) is either positive or negative integer (for simplicity it is assumed that the profit p(b) cannot be zero). If block b is excavated, then the blocks with coordinates
x(b) -1 y(b) +1 z(b) +1
x(b) y(b) +1 z(b) +1
x(b) +1 y(b) +1 z(b) +1
x(b) - 1 y(b) z(b) +1
x(b) y(b) z(b) +1
x(b) +1 y(b) z(b) +1
x(b) -1 y(b) -1 z(b) +1
x(b) y(b) -1 z(b) +1
x(b) +1 y(b) -1 z(b) +1
also must be excavated. Develop a LINGO program that determines what blocks should be excavated in order to maximise the total profit.
Your LINGO program should be able
to read from the Excel file OpenPitMine.xls the following data:
- the set of blocks (the range BLOCKS in the Excel file OpenPit-Mine.xls);
- the coordinates x(b) (the range X in the Excel file OpenPitMine.xls, where the kth cell in X contains the coordinate of the block in the kth cell of the range BLOCKS);
- the coordinates y(b) (the range Y in the Excel file OpenPitMine.xls, where the kth cell in Y contains the coordinate of the block in the kth cell of the range BLOCKS);
- the coordinates z(b) (the range Z in the Excel file OpenPitMine.xls, where the kth cell in Z contains the coordinate of the block in the kth cell of the range BLOCKS);
- the profits p(b) (the range PROFIT in the Excel file OpenPit-Mine.xls, where the kth cell in PROFIT contains the profit asso-ciated with the block in the kth cell of range BLOCKS).
- to generate the corresponding maximal flow network model;
- to determine an optimal production plan and to write this plan into the range PLAN of the Excel file OpenPitMine.xls, where the kth cell in PLAN contains 1 if the block in the kth cell in BLOCKS should be excavated and 0 otherwise.