Mathematical Programming Assignment -

Question 1 - Consider the following linear programming problem:

min 4x₁ + 2x₂ + 3x₃ + 6x₄

s.t.

x₁ + x₃ - e₁ = 10

x₂ + x₄ - e₂ = 20

x₃ + x₄ + s₁ = 30

x₁, x₂, x₃, x₄, e₁, e₂, s₁ ≥ 0.

The tableau below was obtained to proceed with finding a solution to the problem above by using the Simplex algorithm:

(a) Proceed with the Simplex algorithm and find an optimal solution to the problem.

The linear programming problem above was formulated to model the following logistic problem: A company needs to deliver goods to two towns by the end of the month. The first town requires 10 units; the second town requires 20 units. There are two warehouses from which the goods will be taken for delivery. Warehouse 1 can provide unlimited number of units, while Warehouse 2 has only 30 units available. The company wants to minimise the total transportation costs. The costs of delivery (in £100) of one unit from each warehouse to each town are shown in the table below:

(b) Explain why the solution found in your answer to question (a) is indeed an optimal solution to this logistic problem. Hint: Formulate the logistic problem as a transportation problem; explain the relationship of your variables with the variables in the model above; relate the solution found in (a) to the variables of the logistic model.

Question 2 -

(a) A game of hide-and-seek is played with n hiding locations i = 1, 2,... , n. If the Hider hides in location j and the Searcher looks in location i then the payoff to the maximizing Searcher (row player) is the probability P(i, j) that he finds the Hider. If i is not equal to j then P(i, j) = 0. If i = j then he finds the Hider with a probability P(j, j) = x_j that depends on the location j. Locations j with small x_j are better for the Hider.

i) Suppose there are n = 2 hiding locations, with x₁ = ½, x₂ = 2/3. Use the graphical method to find the optimal hiding distribution and search distribution in the associated matrix game written below.

ii) Suppose there are n = 3 locations with x₁ = 1/5, x₂ = 2/5, x₃ = 3/5. Write down the 3 by 3 matrix for this game. Are there any dominated rows or columns? Solve this game by finding the hiding distribution (probability q_j of hiding at location j) for which the Hider doesn't care what location is searched. Solve for q₂ and q₃ in terms of q₁. What is the value of this game? (Note that the graphical solution will not work.)

iii) Write down the value and optimal hiding distribution of the general hide-and-seek game for an arbitrary vector (x₁, x₂, ..., x_n) with n hiding locations.

(b) Use the graphical method after eliminating dominated strategies to find the value and optimal strategies for both players in the following matrix game (row player is maximizer). Explain your work.