A blending problem

Presents the problem of calculating different blends of gasoline according to specific quality criteria.

Blending problems are another typical application of linear programming. Consider the following problem. An oil company manufactures three types of gasoline: super, regular, and diesel. Each type of gasoline is produced by blending three types of crude oil: crude1, crude2, and crude3. Table 1 below depicts the sales price and the purchase price per barrel of the various products. The gasoline must satisfy some quality criteria with respect to their lead content and their octane ratings, thus constraining the possible blendings.

Table 2 describes the relevant instance data.

The company must also satisfy its customer demand, which is 3,000 barrels a day of super, 2,000 of regular, and 1,000 of diesel. The company can purchase 5,000 barrels of each type of crude oil per day and can process at most 14,000 barrels a day. In addition, the company has the option of advertising a gasoline, in which case the demand for this type of gasoline increases by ten barrels for every dollar spent. Finally, it costs four dollars to transform a barrel of oil into a barrel of gasoline. The model is depicted in the example oil.mod and the instance data is shown in oil.dat.

{string} Gasolines = ...;
{string} Oils = ...;
tuple gasType {
  float demand;
  float price;
  float octane;
  float lead;
}

tuple oilType {
  float capacity;
  float price;
  float octane;
  float lead;
}
gasType Gas[Gasolines] = ...;
oilType Oil[Oils] = ...;
float MaxProduction = ...;
float ProdCost = ...;

dvar float+ a[Gasolines];
dvar float+ Blend[Oils][Gasolines];


maximize
  sum( g in Gasolines , o in Oils )
    (Gas[g].price - Oil[o].price - ProdCost) * Blend[o][g] 
    - sum(g in Gasolines) a[g];
subject to {
  forall( g in Gasolines )
    ctDemand: 
      sum( o in Oils ) 
        Blend[o][g] == Gas[g].demand + 10*a[g];
  forall( o in Oils )
    ctCapacity:   
      sum( g in Gasolines ) 
        Blend[o][g] <= Oil[o].capacity;
  ctMaxProd:  
    sum( o in Oils , g in Gasolines ) 
      Blend[o][g] <= MaxProduction;
  forall( g in Gasolines )
    ctOctane: 
      sum( o in Oils ) 
        (Oil[o].octane - Gas[g].octane) * Blend[o][g] >= 0;
  forall( g in Gasolines )
    ctLead:
      sum( o in Oils ) 
        (Oil[o].lead - Gas[g].lead) * Blend[o][g] <= 0;
}

execute DISPLAY_REDUCED_COSTS{
  for( var g in Gasolines ) {
    writeln("a[",g,"].reducedCost = ",a[g].reducedCost);
  }
}

Gasolines = { "Super", "Regular", "Diesel" };
Oils = { "Crude1", "Crude2", "Crude3" };

Gas = [ <3000, 70, 10, 1>,
        <2000, 60, 8, 2>,
        <1000, 50, 6, 1> ];
        
Oil = [ <5000, 45, 12, 0.5>,
        <5000, 35, 6,  2>,
        <5000, 25, 8,  3> ];
        

MaxProduction = 14000;
ProdCost = 4;

The model uses two sets of variables. Variable a[Gasolines] represents the amount spent in advertising gasoline g. Variable Blend[Oils][Gasolines] represents the number of barrels of crude oil o used to produced gasoline g.

The demand constraint:

  forall( g in Gasolines )
    ctDemand: 
      sum( o in Oils ) 
        Blend[o][g] == Gas[g].demand + 10*a[g];

uses both types of variable, since sum(o in Oils) Blend[o][g] represents the amount of gasoline g produced daily.

The capacity constraint:

  forall( o in Oils )
    ctCapacity:   
      sum( g in Gasolines ) 
        Blend[o][g] <= Oil[o].capacity;

enforces the capacity limitation for each type of oil.

The constraints ctOctane and ctLead

  forall( g in Gasolines )
    ctOctane: 
      sum( o in Oils ) 
        (Oil[o].octane - Gas[g].octane) * Blend[o][g] >= 0;
  forall( g in Gasolines )
    ctLead:
      sum( o in Oils ) 
        (Oil[o].lead - Gas[g].lead) * Blend[o][g] <= 0;

enforce the quality criteria for the gasoline.

The objective function has four parts: the sales price of the gasoline, the purchase cost of the crude oils, the production costs, and the advertising costs.

maximize
  sum( g in Gasolines , o in Oils )
    (Gas[g].price - Oil[o].price - ProdCost) * Blend[o][g] 
    - sum(g in Gasolines) a[g];

Final Solution with objective 287750.0000:
  blend = [[2088.8889 2111.1111 800.0000]
            [777.7778 4222.2222 0.0000]
            [133.3333 3166.6667 200.0000]];
  a = [0.0000 750.0000 0.0000];