THE DYNAMIC STOCHASTIC
LINEAR PROGRAMMING MODEL FOR MANAGEMENT IN THE CONSUMPTION OF FUEL IN FLEX
Dn. Paulo César Chagas Rodrigues
Instituto Federal de Educação, Ciência e
Tecnologia de São Paulo - Brazil
E-mail: paulo.rodrigues@ifsp.edu.br
Submission: 12/03/2012
Accept: 17/04/2012
From the amount invested in
fuel prices, the rate of road that owners of vehicles powered by combustion
need to run within the city and on the roads in the region, began a study in
order to allow a better definition as to the cost of supply of vehicle with
Ethanol or gasoline. And to analyze the equation that the government, through Petrobras
announces in the media, because it is mentioned that to obtain the lowest cost
when the supply should divide the value of a liter of Ethanol Gasoline for that
case stay above 0.70 is the ideal fuel to petrol and vice versa.
Keywords: Dynamic
stochastic, linear programming, consumption of fuel, flex car, Ethanol,
Gasoline.
1 INTRODUCTION
With the price of ethanol
and gasoline having a small difference, the users of motor vehicles are in
doubt whether to fill up with ethanol or gasoline.
On this assumption it was
decided to do a search value of ethanol and gasoline in the region of Avaré/SP,
in order to develop a linear programming model in which to obtain the lowest
cost when supplying the vehicle. This research is not measuring how many miles
per gallon the car will do according to the volume of ethanol and gasoline in
the tank.
This research is
exploratory and will use the quantitative method, because if you want to look at
gas stations in the region the charge and record the values that have
variation.
This research will feed the
price linear programming model, so you can have a brief idea of what volume of
ethanol and gasoline, and so put position can know what really gives me the
best option.
Lawrence and Pasternack
(2001) discuss the mathematical programming is the branch of science dealing
with the management of optimization problems, in which we want to maximize a
function (eg as the return of profit, expected, or efficiency) or minimize a
function (such as cost, time or distance), usually in a restricted environment.
According to Goldberg
(2000), the need to represent the context of reality simply gave rise to the
concept of modeling, which is defined as a process of finding a well-structured
view of reality, models are simplified representations of reality, to certain
situations and approaches.
Modeling is a method of
quantitative research of an applied nature, refers to research on models of
causal relationships between control variables and performance variables which
can be developed, analyzed or tested (BERTRAND; FRANSOO, 2002).
Mathematical modeling is
intended to structure and solve quantitative models that can be expressed
mathematically and that within the field of Operations Research, Mathematical
Programming are called. In practice, the Mathematical Programming supports
decision making in managing large systems, especially those related to the
treatment of quantified variables (GOLDBERG, 2000).
Ko, Mehnen and Tiwari
(2010) add that a mathematical structure allows us to treat and represent
uncertainties in the self-perception of uncertainty, imprecision, partial
truth, and lack of information.
Allen and Schuster (2004)
add that mathematical programming is often the tool used for modeling
strategies in conditions of uncertainty. These models are static in nature, assuming
that the probabilities of occurrence are known beforehand and that all
decisions are taken at the same time.
To represent particular
system in formulating a problem with models used is normally a set of equations
or mathematical expressions. There, every decision is taken to be quantifiable
associated with a variable of the model is called the decision variable whose
value should be determined by the model. After formulating the problem it
created an objective function, which is formed by the decision variables and
express the measure of effectiveness sought. Furthermore, from the actual
limitations exist, it creates the model constraints are represented
mathematically by equation and inequalities (Goldberg, 2000).
Bertrand and Fransoo(2002)
explain that modeling can be classified as axiomatic and empirical research:
a) Research indicates the
axiomatic process of obtaining resolutions of the model defined; and
b) The empirical research
indicates that to obtain the results of the empirical process.
2 DYNAMIC Stochastic Programming Model
According to Lawrence and
Pasternack (2001), Dynamic programming can be defined as models that can be
thought of as problems of multiple stages in which a set of decisions is made
"following."
According to García-Dastugue
(2003), the mechanics of the optimization algorithm is based on dynamic
programming. Lambert, Emmelhainz and Gardner (1996) discuss the dynamic
programming is used to solve sequential decision problems in which dynamic
programming starts solving the problem for the last stage and working backwards
to solve the problem for previous stages of each one time.
To Kivinen (2007), the
dynamic programming approach is applied in a solution to the problems that can
be decomposed into a series of different stages (e.g., year 1, 2, 3 or projects
A, B, C, etc.). at each step, the decision maker is a certain situation or
state, which describes the amount of some resource that can be used to this and
all subsequent phases. The challenge to the decision maker is making a series
of decisions that are ideal for the whole process.
Grondin (1998) discuss the
components of a dynamic programming that must be identified for solving
multistage decision may include the following among many others:
a)
A variable stage;
b)
A (set of) state variable;
c)
A (set of) decision
variable;
d)
The return (or cost)
function (or table) for each stage;
e)
An optimal value function
to give the best return for the values of the stage and state variables;
f)
A set of boundary
conditions for the last step;
g)
The stopping rule based on
a value of resources (set of) total available in the first phase; and
h)
The recursion-relation of a
procedure for determining the value of the function, value, ideal for any stage
and state.
2.1 Definitions
In this model the objective
function is to minimize the cost of supply when the car with petrol and
ethanol, for both variables were defined Ethanol and Gasoline and unit of
measure was in liters. The constants that will enable the implementation of the
objective function are viable cost (Y1), desired ethanol consumption (Y2),
gasoline consumption desired (Y3), tank capacity of ethanol (Y4), petrol tank
capacity (Y5), joint capacity (Y6) and fuel costs (Y7).
2.2 Decision
variables
The decision variables are
used in this model ethanol (X11) and petrol (X21), because these two variables
will be displayed volume in liters of each fuel in the tank to be completed and
allow to obtain the lowest cost when the supply.
These variables will be
influenced by the price of fuel, as the fuel station, city, state or even
region of the country, as prices can have a range of up to 100%.
This variation will
exercise some influence on the volume of fuel to be put in the tank, because as
the price change between ethanol and gasoline may inform the model to place
different amounts.
2.3 Constraints
This set of constants will
assist in defining the volume in liters of fuel supply to the vehicle, i.e. the
amount of ethanol and gasoline to be put, as the tank capacity. Note that
implicitly assume the non-negativity of the decision variables and will be
supplemented with 1 or 0, which can be seen in Table 1.
The following features will
equations that will compose the constants:
Equation 1 shows the restriction value, which is the multiplication number of
liters of ethanol and cost of fuel, which must be less than or equal to the
cost of viable * cost of fuel * number
of liters of gasoline.
Y17 * X1 <= Y1 * Y27 * X12 |
(1) |
Equation 2 is the sum of
the multiplication of the number of liters of ethanol * Tank capacity ethanol
and multiplying the quantity of gasoline does * gas tank capacity, which is a
restriction on the ability of ethanol as the fuel tank support. This
restriction has the constant value 1 Y17 and Y27 has constant value 0.
Y14 * X11 + Y24 * X12 <= Y4 |
(2) |
Equation 3 is the sum of
the multiplication of the number of liters of ethanol * Tank capacity ethanol
and multiplying the quantity of gasoline does * gas tank capacity, which is a
restriction on the ability of ethanol as the fuel tank support . This
restriction has the constant value 0 Y17 and Y27 constant has the value 1.
Y15 * X11 + Y25 * X12 <= Y5 |
(3) |
Equation 4 represents the
combined capacity of the two fuel tank which should be less than or equal to
the capacity of the tank and it means the sum of multiplications of constant
joint capacity * variable quantity of gallons of ethanol and constant joint
capacity * variable number of gallons of gasoline.
Y16 * X11 + Y26 * X12 <= Y6 |
(4) |
Equations 5 and 6 are not
to force the negativity of the variables related to the volume in liters of
ethanol and gasoline to be supplied in the car.
X11 >= 0 |
(5) |
X21 >= 0 |
(6) |
Equations 7 and 8, are
responsible for creating Kilometer a delimitation between the minimum and
maximum that the vehicle can make from the formulation amount of each fuel to
be used during fueling of the car. In which the summation is carried out
multiplications between the capacity of the tank with ethanol and the value in
Km / l and that the vehicle is in Gasoline Tank capacity and the value in km /
l that the vehicle is.
X11 * Y2 + X12 * Y3 >= Y4 * Y2 |
(7) |
X11 * Y2 + X12 * Y3 <= Y5 * Y3 |
(8) |
2.4 Objective
function
The objective function of
the model includes two contrasting components. The first measuring the volume
in liters of gasoline and ethanol and second cost would be about the supply of
fuel. From these variables and constants will be the calculation of the total
cost when the supply of fuel in certain gas station.
The objective function of
Equation 7 is to minimize the cost of supply, allowing it to obtain a financial
economics, when supply and have a lead time between a supply and another
constant.
Minimizar (Y17 * X11 + Y27 * X21) |
(7) |
3 Illustrative example
Based on Table 1, is
presented an application example and model validation:
In Cost-effective (Y1) as the value is one way of forcing the supply with both
fuels, the value of 0.6667 signifies the division between the values of Km /
L when the vehicle makes Ethanol and Gasoline, i.e. division between 10 and 15
liters.
In Ethanol Consumption
Desired (Y2) values are 1 and 0 respectively for the X11 and X21 column to
inform you that should only be put Ethanol.
Gasoline Consumption In
Desired (Y3) values are 0 and 1 respectively for the X11 and X21 column to
inform you that should only be put Gasoline.
Already in Ethanol Tank
capacity (Y4) to how many liters of Ethanol can be put in the fuel tank and
should have the values 1 and 0.
To Gasoline Tank Capacity
(Y5) to how many gallons of Gasoline may be placed in the fuel tank and must
have values 0 and 1.
Combined capacity (Y6) will
permit the validation of how many of each fuel tank and will fill the value is
one for both columns.
The Cost of fuel (Y7) be
the price recorded in the fuel pump which will assist in formulation of the
cost of supply.
Table 1: sample run of the model
Ethanol |
Gasoline |
|||
X11 |
X21 |
|||
Liters |
24 |
21 |
||
Cost-effective
(Y1) |
1 |
1 |
0,6667 |
|
Ethanol
Consumption desired (Y2) |
1 |
0 |
10 |
Km/L |
Gasoline
Consumption desired (Y3) |
0 |
1 |
15 |
Km/L |
Tank
capacity Ethanol (Y4) |
1 |
0 |
45 |
L |
Gasoline
Tank Capacity (Y5) |
0 |
1 |
45 |
L |
Combined
capacity (Y6) |
1 |
1 |
45 |
L |
Cost
of fuel (Y7) |
1,570 |
2,690 |
R$ |
|
Objective function: |
94,18 |
|||
Constraints: |
||||
37,671 |
<= |
37,671 |
||
24 |
<= |
45 |
||
21 |
<= |
45 |
||
45,000001 |
<= |
45 |
||
24 |
>= |
0 |
||
21 |
>= |
0 |
||
|
554 |
>= |
450 |
|
|
554 |
<= |
675 |
|
4 Application to the
fUEL fLEX CAR
The application of the
proposed model to a real world problem requires additional assumptions,
complete specification of risk factors "fuel value", how many
Kilometers per liter the vehicle wheel and the inclusion of the total cost of
refueling in the objective function.
These data helped in the
implementation of a mathematical model, which was implemented in the
spreadsheet Microsoft Excel version 2010, with the implementation of Solver
application during its execution sought to observe the variation amount of fuel
as the price of fuel varied according to the fuel station.
In a second step we could
see how many kilometers the vehicle could run as the amount of each fuel, which
allows observing the cost / benefit that the driver may have with this
solution. Mileage values as the vehicle can achieve with the mixture is an estimate,
it would have to observe the condition of the vehicle, location where this is
heading, among others.
The Appendices A, B and C
are respectively presented reports response, and sensitivity limits, so as to
enable the validation of the model.
5 Final Thoughts
Challenges for modeling and
solving mathematical problems, taking into account the dynamics of the
decisions about the uncertainties are many and complex. Since the size of the
problem increases exponentially with the number of steps, computational tractability,
as the first obstacle on the modeling.
With the incorporation of
data from fuel costs, mileage per gallon of each fuel and the fuel tank
capacity, the objective function seeks to minimize the cost of supplying and
allowing the vehicle can run as much as possible, between the pre- established
by the vehicle manufacturer, because as is well known brand and each model may
have very specific details.
The application of this
model in practice has been going through empirical studies, conducted over several
trips, in which the author tries to observe the value of fuel, depending on the
region or city where it passes and observing the behavior of the vehicle during
its operation. Also being done tests and observations, as the condition of the
local road in good repair or bumpy, cities with slow or fast traffic, use of
air conditioning, among other factors.
The development of this
model is part of a project to allow a little more rational consumption of
fossil fuel and Ethanol, allowing the reduction of the emission of toxic gases,
engine durability, reduced spending on fuel, among others. This project seeks
to establish a balance between successful academic innovation and attention to
business requirements. From the use of an application widely used in business
and personal life, the model can be used and tested, but for that you should
have a minimum of knowledge about the use of the spreadsheet in Microsoft Excel
and in the case of Plugin Solver, adding a practical dimension to the
contributions described in this article.
REFERENCES
ALLEN S. J.;
SCHUSTER, E. W. (2004) Controlling the risk for a agricultural harvest. Manufacturing
& Service Opertions Management, v. 6, n. 3, p 225-236.
BERTRAND, J. W. M.; FRANSOO, J. C. (2002) Modeling and
Simulation: Operations management research methodologies using quantitative
modeling. International Journal of
Operations & Production Management, v. 22, n. 02, p. 241-264.
GARCÍA-DASTUGUE, S.
J. (2003) Dynamic time-based postponement: Conceptual development and
empirical test. Ph.D, Ohio: Ohio State University.
GOLDBERG, D. E.
(2000) Genetic algorithms in search, Optimization and Machine Leaning.
Addison Wesley Limited.
GRONDIN, F. (1998)
Improvements of the dynamic programming algorithm for tree bucking. Wood and
Fiber Science, v. 30, n. 1, p. 91-104.
KIVINEN, V. P. (2007) Design and testing of stand-specific bucking instructions for use on
modern cut-to-length harvesters. Dissertação (Department of Forest Resource
Management), Helsinki: University Helsinki.
KO, M.; TIWARI, A.; MEHNEN, J. (2010) A review of soft
computing applications in supply chain management. Applied Soft Computing. V. 10, p. 661-674.
LAMBERT, D. M.; EMMELHAINZ, M. A.; GARDNER, J. T.
(1996) Developing and Implementing Supply Chain Partnerships. The International Journal of Logistics
Management, v. 7, n. 2, p. 1-18.
LAWRENCE, J. A.; PASTERNACK, B. A. (2001) Applied management science: modeling,
spreadsheet analysis, and communication for decision making. 2 ed. New Jersey:
Wiley.
Appendices’ A
Appendices’ B
Appendices’ C