PROBLEM :
In his previous life, Dr. Konur was a shepherd in Anatolia. He had 50 sheep that he used to shepherd. In one of those days, Dr. Konur needed to direct these 50 sheep (on the left side) across the river so that his sheep can meet with the grass (on the right side).
Even if Dr. Konur was a shepherd, Dr. Konur always had some engineering skills and he spotted four points, A and B are on the left side, and C and D are on the right side of the river. Dr. Konur can build a bridge between the points on different sides of the river. That is, he can build a bridge between A and C, A and D, B and C, and B and D. However, different bridges can carry different number of sheep and it takes Dr. Konur different times to build the bridges. The table below shows the number of sheep each bridge can carry and the time required to build each bridge.
Since Dr. Konur's sheep were very hungry, Dr. Konur wanted to build bridges as soon as possible (that is, the total time to build the bridges needed to be minimized) so that there were sufficient bridges that could carry these 50 sheep to the other side of the river. That is, Dr. Konur wanted to decide on which bridges to build so that the total time to build the bridges is minimized and the total capacity of the bridges is at least enough to carry 50 sheep to the other side. However, while solving his problem, Dr. Konur needed to be careful about the following engineering design requirements:
- From a point on the left side, there can be built at most 1 bridge to the other side.
- There can be built at most one bridge to the points on the right side of the river.
As Dr. Konur's new student in his current life, you are asked to formulate a binary-integer linear programming problem for Dr. Konur's problem as a shepherd in his previos life. Define you decision variables, and express your objectives and constraints as functions of the decision variables, and combine everything.