Question

Ottawa Art Gallery (OAG) has four valuable paintings that are up for sale to raise funds for the future building expansion. Four customers are bidding for the paintings. Customer 1 is willing to buy two paintings, but each other customer is willing to purchase at most one painting. The prices (in thousands) that each customer is willing to pay are given in the table below.
Bid for ($):
Painting 1 Painting 2 Painting 3 Painting 4

Customer 1 8 11 - -

Customer 2 9 13 12 7

Customer 3 9 - 11 -

Customer 4 - - 12 9

Note: “ - “ indicates that customer has not placed a bid for a painting OAG is interested in maximizing total revenue received from the sale of the paintings.

1. Formulate this problem as an assignment problem.

2. Use Excel Solver to solve the resulting LP (Include both formulation and answer report)

3. Describe clearly the optimal solution to this problem using a managerial statement to make a recommendation to the leadership of the OAG.

Answer 1

Formulation

Xij is the decision variable that says

Xij= 1 if painting j is assigned to customer i

=0 otherwise

Objective function

Cij= the price that the customer i will pay for painting j

Objective Function

Maximize Cij*Xij

Maximize 8X11+11X12+9X21+13X22+12X23+7X24+9X31+11X33+12X43+9X44

Subject to

Customer 1 is willing to buy two paintings

X11+X12+X13+X14=2

Each other customer will buy at most 1 painting

X21+X22+X23+X24<=1

X31+X32+X33+X34+X35<=1

X41+X42+X43+X45<=1

Next constraint is that each painting should be assigned only 1 customer

X11+X21+X31+X41=1

X12+X22+X32+X42=1

X13+X23+X33+X43=1

X14+X24+X34+X44=1

Xij={0,1}

solver model

3. The Solver model says the painting 1 and 2 should be assigned to customer 1 as e wants 2 paintings

Painting 3 to customer 2 and painting 4 to customer 3 as it gives the highest revenue

The total value is 40

Please comment if any doubt

Rate me

Thanks