Question

Sally, a used-car broker needs to transport her inventory of cars from Irvine and Santa Ana to used-car auctions being held in Anaheim and Huntington Beach. Sally currently uses a trucking company that charges her for each car shipped. The transportation costs from each origin city and destination city are:

Origin	Destination	Cost per Car Shipped	Capacity (# Cars)
Irvine	Costa Mesa	$8	10
Irvine	Santa Ana	$5	10
Santa Ana	Costa Mesa	$9	10
Santa Ana	Huntington Beach	$20	20
Costa Mesa	Anaheim	$6	No limit
Costa Mesa	Huntington Beach	$7	No limit
Huntington Beach	Anaheim	$6	10

Sally has 15 cars in Irvine and 15 cars in Santa Ana. She wants to ship 20 cars to Anaheim and 10 cars to Huntington Beach in the cheapest way possible. She knows that it might make sense to ship some cars through Costa Mesa; there is a parking lot there where cars can be transferred from one truck to the next.

Formulate this problem as a linear program (algebraically define all decision variables, all constraints and the objective function). Do not solve it.

Answer 1

LP model is formulated as below:

Decision variables:

Let Xij be the number of cars to be transported from city i to city j, where i,j={1,2,3,4,5} for {Irvine, SantaAna, CostaMesa, HuntingtonBeach, Anaheim}

Objective function:

Minimize 8X13+5X12+9X23+20X24+6X35+7X34+6X45

Constraints:

X13+X12 = 15 (Total cars shipped out from Irvine)

X23+X24 = 15 (Total cars shipped out from Santa Ana)

X13+X23-X34-X35 = 0 (Net flow of cars To and From Costa Mesa)

X24+X34 = 10    (Inflow of cars into Huntington Beach)

X35+X45 = 20    (Inflow of cars into Anaheim)

X13 <= 10 (capacity of cars to be shipped from Irvine to Costa Mesa)

X12 <= 10 (capacity of cars to be shipped from Irvine to Santa Ana)

X23 <= 10 (capacity of cars to be shipped from Santa Ana to Costa Mesa)

X24 <= 20 (capacity of cars to be shipped from Santa Ana to Huntington Beach)

X45 <= 10 (capacity of cars to be shipped from Huntington Beach to Anaheim)

Xij <= 0