Optimal Assignment Problem
Find the amount of electricity a company must send from its four power plants to five cities so as to maximize profit and minimize cost while meeting the cities' peak demands.
This example demonstrates how LinearFractionalOptimization may be used to minimize the ratio of cost to profit within given constraints. Use of a matrix-valued variable makes the modeling relatively simple.
Let represent the amount of electricity sent by plant to city . The total cost of transporting electricity is , where is the cost of transporting electricity from plant to city . Total[m, 2] gives the total of all elements of a matrix .
The total profit made by the power company is , where is the profit made by plant selling electricity to city .
The total electricity sent by each plant is given by and must be greater than or equal to the minimum electricity that plant can supply. Total[x, {2}] gives the total for each row of .
The total electricity sent to each city is given by and must be greater than the minimum demand and less than or equal to the peak demand. Total[x, 1] gives the total of the columns of .
The plants can only give and not receive power from the cities. VectorGreaterEqual can be used to indicate that all elements of the matrix variable should be greater than or equal to zero.
As an example, here is the cost of transporting one million kilowatt hours (kWh) of electricity from four plants to five cities.
The profit that each power plant generates by selling 1 million kWh to each city is shown here.
The cities have a peak demand of 45, 20, 30, 30 and 40 million kWh, respectively, and a minimum demand of 5 million kWh.
The power plants can supply a minimum of 35, 50, 40 and 40 million kWh of electricity, respectively.
The optimal amount of electricity to send each city by each plant can be found by minimizing the ratio of cost to profit.
The breakdown of electricity supplied is shown.