# Stochastic Fractional Programming Approach to a Mean and Variance Model of a Transportation Problem

Authors: V. Charles; V. S. S. Yadavalli; M. C. L. Rao; P. R. S. Reddy
Journal: Mathematical Problems in Engineering
 (2011)

---

## Abstract

In this paper, we propose a stochastic programming model, which considers a ratio of two nonlinear functions and probabilistic constraints. In the former, only expected model has been proposed without caring variability in the model. On the other hand, in the variance model, the variability played a vital role without concerning its counterpart, namely, the expected model. Further, the expected model optimizes the ratio of two linear cost functions where as variance model optimize the ratio of two non-linear functions, that is, the stochastic nature in the denominator and numerator and considering expectation and variability as well leads to a non-linear fractional program.  In this paper, a transportation model with stochastic fractional programming (SFP) problem approach is proposed, which strikes the balance between previous models available in the literature.


---

## Body

## 1. Introduction

The transportation engineering problem is one of the most primitive applications of linear programming problems. The basic transportation problem was initially developed by Hitchcock [1] and has grown to the stage wherein supply chain management uses it significantly. Even one can say that supply chain’s success is closely linked to the appropriate use of transportation. Linear fractional transportation problem was first discussed by Swarup [2] and since then it did not receive much attention.  This paper deals with a fractional transportation model in which parameters involved in the model are probabilistic in nature.When the market demands for a commodity are stochastic in nature, the problem of scheduling shipments to a number of demand points from several supply points is a stochastic transportation problem [3]. Jörnsten et al. [4, 5] studied stochastic transportation model for petroleum transport and proposed a cross-decomposition algorithm to solve the said problem. The stochastic transportation problem can be formulated as a convex transportation problem with nonlinear objective function and linear constraints. Holmberg [6] compared different methods based on decomposition techniques and linearization techniques for this problem; Holmberg tried to find the most efficient method or combination of methods. Holmberg also discussed and tested a separable programming approach, the Frank-Wolfe method with and without modifications, the new technique of mean value cross-decomposition, and the more well-known Lagrangian relaxation with subgradient optimization, as well as combinations of these approaches.Ratio optimization problems are commonly called fractional programs. One of the earliest fractional programs is an equilibrium model for an expanding economy introduced by Von Neumann in 1937, at a time when linear programming hardly existed. The linear and nonlinear models of fractional programming problems have been studied by Charnes and Cooper [7] and Dinkelbach [8]. The fractional programming problems have been studied extensively by many researchers. Mjelde [9] maximized the ratio of the return and the cost in resource allocation problems; Kydland [10], on the other hand, maximized the profit per unit time in a cargo-loading problem. Arora and Ahuja [11] discussed a fractional bulk transportation problem in which the numerator is quadratic in nature and the denominator is linear.Stochastic fractional programming (SFP) offers a way to deal with planning in situations where the problem data is not known with certainty. Such situations arise where technological aspects of the system under study may be highly complicated or incapable of being observed completely. Stochastic Programming and Fractional Programming constitute two of the more vibrant areas of research in optimization. Both areas have blossomed into fields that have solid mathematical foundations, reliable algorithms and software, and a plethora of applications that continue to challenge current state-of-art computing resources. For various reasons, these areas have matured independently.  Many of the existing procedures that are of practical importance for solving stochastic programming and fractional programming problems rely mostly on simplified assumptions. Wide range of applications of stochastic and fractional programming can be seen in [12–17].A constrained linear stochastic fractional programming (LSFP) problem involves optimizing the ratio of two linear functions subject to some constraints in which at least one of the problem data is random in nature with nonnegative constraints on the variables. In addition, some of the constraints may be deterministic.The LSFP framework attempts to model uncertainty in the data by assuming that the input or a part thereof is specified by a probability distribution, rather than being deterministic. Gupta [18] described a model on capacitated stochastic transportation problem, which maximizes profitability. LSFP has been extensively studied by Gupta et al. [19, 20] and Charles et al. [14–17, 21–31], the concepts of LSFP are available in [21, 22], various algorithms to solve LSFP have been discussed in [23, 26, 28, 29], financial derivative applications of nonlinear SFP are studied in [25, 27], and multiobjective LSFP problems are discussed in [24, 30]. Charles and Dutta [30] discusses an application to assembled printed circuit board of multi-objective LSFP, and an algorithm to identify redundant fractional objective function in multi-objective SFP is clearly discussed in [31, 32].In this paper, a special class of transportation problems has been considered wherein the stochastic fractional programming (SFP) is the handy technique to optimize the transportation problem. The said special class of uncapacitated transportation problems has two distinct cost matrices in which costs involved in the problem are random in nature and are assumed to follow normal distribution, and the demand vector under study is also random wherein the demand vector is assumed to follow probability distributions like normal and uniform. The proposed mean-variance model attempts to optimize the profit over shipping cost under uncertain environment, subject to regular supply constraints along with stochastic demand constraints.The organization of this paper is as follows. Section2 discusses the uncapacitated transportation problem of SFP along with some basic assumptions. A deterministic equivalent of probabilistic demand constraints are described in Section 3 along with explanation for some of the preliminary properties of transportation problem of SFP and expectation, and also variance and mean-variance models for the uncapacitated transportation problem of SFP are established.  In this Section 4 provides an algorithm to solve this problem. Discussion on this paper with a summary and recommendations for future research is in Section 5.


## 2. The UnCapacitated Transportation Problem of LSFP

This section deals with the uncapacitated TP of LSFP for the distribution of a single homogenous commodity fromm sources to n destinations, where the demand for the commodity at each of the n destinations is a random variable. An uncapacitated TP of LSFP in a criterion space is defined as follows:  (2.1)maximizeR(X)=N(X)+αD(X)+β=∑i=1m∑j=1npijxij+α∑i=1m∑j=1ncijxij+β,
subject to
(2.2)∑j=1nxij≤ai,i=1,2,…,m,(2.3)∑i=1mxij=rj,j=1,2,…,n,
where 0≤Xm×n=∥xij∥∈Rm×n is a feasible set, S={X∣(2.2)-(2.3),X≥0,X∈Rm×n} is nonempty, convex, and compact set in Rm×n, xij is an unknown quantity of the good shipped from supply point i to demand point j, profit matrix Nm×n=∥pij∥ which  determines the profit pij~N(upij,spij2) gained from shipment from i to j, cost matrix Dm×n=∥cij∥ which  determines the cost  cij~N(ucij,scij2) per unit of shipment from i to j, the denominator function D(X)+β is assumed to be positive throughout the constraint set, scalars α,β, which determines some constant profit and cost, respectively, supply point i must have ai units available, stochastic demand point j must obtain 1-lj level of rj units, and 1-lj(0<lj<1)  is the least probability with which jth stochastic demand constraint is satisfied.Stochastic equation (2.3) can be rewritten as follows:(2.4)Pr[∑i=1mxij≥rj]≥1-lj,j=1,2,…,n,(2.5)Pr[∑i=1mxij≤rj]≥1-lj,j=1,2,…,n.Assumption 2.1.
(a) The values of every point of supply and demand are positive.
(b) Total supply is not less than total demand.
(c) Noninteger solutions are acceptable.


## 3. Deterministic Equivalents of Probabilistic Demand Constraints and E-Model

Letrj be a random variable in constraint (2.4) that follows N(urj,srj2),j=1,2,…,n, where urj is the jth mean and srj2 is the jth variance.  The jth deterministic demand constraint (2.4) is obtained from Charles and Dutta [21] and is given as follows:(3.1)Pr[∑i=1mxij≥rj]≥1-lj(or)Pr[rj≤∑i=1mxij]≥1-lj(or)Pr(Zj≤zj)≥1-lj,
where Zj=(rj-urj)/srj follows standard normal distribution and  zj=(∑i=1mxij-urj)/srj.  Thus, ϕ(zj)≥ϕ(K1-lj), where 1-lj=ϕ(K1-lj), is the cumulative distribution function of standard normal distribution. Clearly, ϕ(·) is a nondecreasing continuous function, hence zj≥K1-lj. The jth deterministic demand constraint (2.4) is as follows:  (3.2)∑i=1mxij≥urj+K1-ljsrj.
Similar to constraint (3.2), one can obtain the constraint given below from (2.5): (3.3)∑i=1mxij≤urj+Kljsrj.
Inequalities (3.2) and (3.3) can be combined as follows:(3.4)urj+K1-ljsrj≤∑i=1mxij≤urj+Kljsrj.
Let rj be the uniform random variable which ranges from ujlow to ujup, that is, rj~U(ujlow,ujup),the probabilistic demand constraint in system (2.1) is equivalent to∑i=1mxij≥τj, where lj′=1-lj, and ∫τjujup(dx/(ujup-ujlow))=lj′, that is, τj=ljujup+lj′ujlow. Hence, the deterministic equivalent of the jth probabilistic demand constraint (2.4) is(3.5)∑i=1mxij≥ljujup+lj′ujlow.
Similar to (3.5) one can obtain the constraint given below from (2.5): (3.6)∑i=1mxij≤ljujlow+lj′ujup.
Constraints (3.5) and (3.6) can be combined as follows:(3.7)ljujup+lj′ujlow≤∑i=1mxij≤ljujlow+lj′ujup.Definition 3.1.
If the total supply lies in the interval of total deterministic demand, the transportation problem of SFP has feasible solutions.Case 1.
The normally distributed demand is∑j=1n(urj+K1-ljsrj)≤∑i=1mai≤∑j=1n(urj+Kljsrj).Case 2.
Uniformly distributed demand the∑j=1n(ljujup+lj′ujlow)≤∑i=1mai≤∑j=1n(ljujlow+lj′ujup).Lemma 3.2.
The transportation problem of SFP always has a feasible solution, that is, feasible setS is nonempty.Lemma 3.3.
The set of feasible solutions is bounded.Lemma 3.4.
The transportation problem of SFP is solvable.The proof of the above said properties when demand follows normal distribution are as follows: Letxij* be defined as    (3.8)ai(urj+K1-ljsrj)T1≤xij*≤ai(urj+Kljsrj)T2,i=1,2,…,m,j=1,2,…,n,
where T1=∑j=1n(urj+K1-ljsrj),T2=∑j=1n(urj+Kljsrj) are positive.Substitutingxij* for the supply and demand constraints, that is, from constraints (2.2) and (2.4), the following can be obtained:(3.9)∑j=1nxij*≤∑j=1nai(urj+K1-ljsrj)T1=aiT1∑j=1n(urj+K1-ljsrj)=ai,i=1,2,…,m,∑j=1nxij*≥∑j=1nai(urj+Kljsrj)T2=aiT2∑j=1n(urj+Kljsrj)=ai,i=1,2,…,m,
and hence ∑j=1nxij*=ai.From (3.8), one can obtain(3.10)∑i=1mai(urj+K1-ljsrj)T1≤∑i=1mxij*≤∑i=1mai(urj+Kljsrj)T2,(urj+K1-ljsrj)T1∑i=1mai≤∑i=1mxij*≤(urj+Kljsrj)T2∑i=1mai,urj+K1-ljsrj≤(urj+K1-ljsrj)T1∑i=1mai≤∑i=1mxij*≤(urj+Kljsrj)T2∑i=1mai≤urj+Kljsrj,urj+K1-ljsrj≤∑i=1mxij*≤urj+Kljsrj,j=1,2,…,m.Hence, constraints  (2.2) and (2.4) are satisfied by xij*. Since from Assumption 2.1(a)-(b) the constraint (3.2) it follows that xij*>0,i=1,2,…,m, j=1,2,…,n, it becomes obvious that x*=(xij*) is a feasible solution of the transportation problem of stochastic fractional programming. Thus it has been clearly shown that the feasible set S is not empty.Further, from (2.2), (3.4), and (3.7) along with nonnegativity constraints, it is clear that 0≤xij*≤ai,i=1,2,…,m;j=1,2,…,n.Expectation and variance of the profit and cost function of the probabilistic fractional objective function are defined as follows:(3.11)E(N(X))=∑i=1m∑j=1nE(pij)xij+α=∑i=1m∑j=1nupijxij+α,E(D(X))=∑i=1m∑j=1nE(cij)xij+β=∑i=1m∑j=1nucijxij+β,V(N(X))=∑i=1m∑j=1nV(pij)xij=∑i=1m∑j=1nSpij2xij2,V(D(X))=∑i=1m∑j=1nV(cij)xij=∑i=1m∑j=1nScij2xij2.
Hence the deterministic fractional objective function is as follows:(3.12)REV(X)=w1(∑i=1m∑j=1nupijxij+α)+w2∑i=1m∑j=1nSpij2xij2w1(∑i=1m∑j=1nucijxij+β)+w2∑i=1m∑j=1nScij2xij2,
where w1 and w2 are preselected nonnegative numbers indicating the relative importance for optimization of the mean and the square root of the variance covariance matrix. The special cases corresponding to w2=0 and w1=0 are, respectively, known as the E-model and the V-model. The objective function (3.12) is very a well-known mean-variance model.Since the numerator and denominator functions of the fractional objective function (3.12) are in Kataoka’s [32] form and the denominator is assumed to be positive over the bounded feasible set S, it means that fractional objective function REV(X) is also bounded over the same feasible set S, and hence it can be concluded that transportation problem of SFP is solvable.TheE-model for the uncapacitated TP of LSFP when demand follows normal distribution is as follows:
(3.13)maximizeRE(X)=∑i=1m∑j=1nupijxij+α∑i=1m∑j=1nucijxij+β,subject to∑j=1nxij≤ai,i=1,2,…,m,urj+K1-ljsrj≤∑i=1mxij≤urj+Kljsrj,j=1,2,…,n,
where 0≤Xm×n=∥xij∥∈Rm×n is a feasible set, S={X|(2.2)and(3.4),X≥0,X∈Rm×n} is nonempty, convex and compact set in Rm×n,xij is an unknown quantity of the good shipped from supply point i to demand point j, RE(X)  is the fractional objective function defined as ratio of the profit function over the cost function, the profit and cost function is assumed to be positive throughout the constraint set, supply point i must have at most ai units, deterministic demand point j must obtain at least urj+K1-ljsrj units and at most urj+Kljsrj units. Similarly one can define E-model of system (2.1), when demand follows uniform distribution or/and normal distribution.Lemma 3.5.
This lemma is proposed with theRE(·) being defined in the earlier section as the fractional objective function:(1.1)
RE(λ) is a convex function for λ∈R.(1.2)
RE(λ) is strictly decreasing function on R.(1.3)
RE(λ) is continuous function on R.(1.4)
The equationRE(λ)=0 has unique solution, say λ*.(1.5)
RE(λ)≥0 for all x∈S.Theorem 3.6.
A necessary and sufficient condition for(3.14)λ*=∑i=1m∑j=1nupijxij*+α∑i=1m∑j=1nucijxij*+β=maximizex∈S∑i=1m∑j=1nupijxij+α∑i=1m∑j=1nucijxij+β
is
(3.15)RE(λ*)=RE(x*,λ*)=maximizex∈S[∑i=1m∑j=1nupijxij+α-λ*(∑i=1m∑j=1nucijxij+β)]=0.Note 3.
It may be noted that optimal solutionx*may not be unique for the extremes (i.e., max/min). The V-model for the uncapacitated TP of SFP when demand follows normal distribution is as follows:
(3.16)maximizeRV(X)=∑i=1m∑j=1nSpij2xij2∑i=1m∑j=1nScij2xij2
subject to ∑j=1nxij≤ai,i=1,2,…,m,urj+K1-ljsrj≤∑i=1mxij≤urj+Kljsrjj=1,2,…,n, where 0≤Xm×n=||xij||∈Rm×n is a feasible set, S={X|(2.2)and(3.4),X≥0,X∈Rm×n} is nonempty, convex, and compact set in Rm×n, xij is an unknown quantity of the good shipped from supply point i to demand point j, RV(X)  is the fractional objective function defined as ratio of standard deviation of the profit function over standard deviation of the cost function, the profit and cost function is assumed to be positive throughout the constraint set, supply point i must have at most ai units, deterministic demand point j must obtain at least urj+K1-ljsrj units and at most urj+Kljsrj units. Similarly one can define V-model of system (2.1) when demand follows uniform distribution or/and normal distribution.Lemma 3.7 ..
The following results are true.(2.1)
RV2(λ) is a convex function for λ∈R.(2.2)
RV2(λ) is strictly decreasing function on R.(2.3)
RV2(λ) is continuous function on R.(2.4)
The equationRV2(λ) = 0 has unique solution, say λ*.(2.5)
RV2(λ)≥0 for all x∈S.Theorem 3.8 ..
A necessary and sufficient condition for(3.17)λ*=∑i=1m∑j=1nSpij2xij2*∑i=1m∑j=1nScij2xij2*=maximizex∈S∑i=1m∑j=1nSpij2xij2∑i=1m∑j=1nScij2xij2
is
(3.18)RV2(λ*)=RV2(x*,λ*)=optimizex∈S[∑i=1m∑j=1nSpij2xij2-λ*∑i=1m∑j=1nScij2xij2]=0.Note 3.
It may be noted that optimal solutionx* may not be unique for the extremes (i.e., max/ min). The mean-variance model for the uncapacitated TP of SFP when demand follows normal distribution is as follows:
(3.19)maximizeREV(X)=w1(∑i=1m∑j=1nupijxij+α)+w2∑i=1m∑j=1nSpij2xij2w1(∑i=1m∑j=1nucijxij+β)+w2∑i=1m∑j=1nScij2xij2,
subject to ∑j=1nxij≤ai,i=1,2,…,m,urj+K1-ljsrj≤∑j=1mxij≤urj+Kljsrj,j=1,2,…,n,                                                                                                     where 0≤Xm×n=∥xij∥∈Rm×n is a feasible set, S={X|(2.2)and(3.4),X≥0,X∈Rm×n} is nonempty, convex, and compact set in Rm×n, and xij is an unknown quantity of the good shipped from supply point i to demand point j. Similarly one can define mean-variance model of system (2.1) when demand follows uniform distribution or/and normal distribution.Theorem 3.9.
A necessary and sufficient condition for(3.20)λ*=w1(∑i=1m∑j=1nupijxij*+α)+w2∑i=1m∑j=1nSpij2xij2*w1(∑i=1m∑j=1nucijxij*+β)+w2∑i=1m∑j=1nScij2xij2*=maximizex∈Sw1(∑i=1m∑j=1nupijxij+α)+w2∑i=1m∑j=1nSpij2xij2w1(∑i=1m∑j=1nucijxij+β)+w2∑i=1m∑j=1nScij2xij2
is
(3.21)REV(λ*)=REV(x*,λ*)=maximizex∈S[w1(∑i=1m∑j=1nupijxij+α)+w2∑i=1m∑j=1nSpij2xij2-λ*(w1(∑i=1m∑j=1nucijxij+β)+w2∑i=1m∑j=1nScij2xij2)]=0.


## 4. Algorithm: Sequential Linear Programming for TP of SFP

(1)
Start with an initial pointX(0) and set the iteration number t=0 (there are many ways to get the initial guess X(0), one among is to solve maximizex∈S∑i=1m∑j=1nupijxij).(2)
Decide the importance of mean and variance by means of assigning values tow1 andw2.(3)
Obtain(4.1)λ(0)=w1(∑i=1m∑j=1nupijxij+α)+w2∑i=1m∑j=1nSpij2xij2w1(∑i=1m∑j=1nucijxij+β)+w2∑i=1m∑j=1nScij2xij2.(4)
Linearize the constraint form of objective function about the points(X(t),λ(t)) as REV(X,λ)≈REV(X(t),λ(t))+∇REV(X(t),λ(t))T(X-X(t),λ-λ(t))T.(5)
Formulate the approximate TP of LSFP as(4.2)maximizex∈Sλsubject toREV(X(t),λ(t))+∇REV(X(t),λ(t))T(X-X(t),λ-λ(t))T=0.(6)
Solve the approximating TP of SFP to obtain the solution vectorX(t+1) and scalar λ(t+1).(7)
FindREV(X(t+1),λ(t+1)).(8)
If|REV(X(t+1),λ(t+1))|≤ε, whereε is a prescribed small positive tolerance, all the demand and supply  constraints can be assumed to have been satisfied. Hence stop the procedure by considering  optimal X is approximately equal to X(t+1), that is,Xopt=X(t+1).(9)
Else,  once again linearize the constraint form of objective function about the points(X(t+1),λ(t+1)) as REV(X,λ)≈REV(X(t+1),λ(t+1))+∇REV(X(t+1),λ(t+1))T(X-X(t+1),λ-λ(t+1))T   and add this as an  additional constraint to TP of SFP defined in step (4).(10)
Increment the iteration number by 1 and go to step (4).


## 5. Discussion and Future Research

A transportation model with stochastic programming approach is considered, and an algorithm to this effect has been presented.  The reason to use SFP was to deal with planning in situations where the problem data is known only in the stochastic environment.  Such situations arise in high technological complex systems.  This proposed model would provide useful solution under those circumstances when the company likes to optimize the ratio of profit over the cost per unit of shipment in a way to meet the stochastic demands with a clear account for variation. This paper can be extended to an integer solution using branch and bound technique. Mixed model for TP of SFP and stochastic fractional recourse programming may be the interest of future research.



---

*Source: 657608-2011-06-06.xml*