Optimization Or Mathematical Programming Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Optimization, or mathematical programming, refers to choosing the best element from some set of available alternatives. In the simplest case, this means solving problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an allowed set. This formulation, using a scalar, real-valued objective function, is probably the simplest example; the generalization of optimization theory and techniques to other formulations comprises a large area of applied mathematics. More generally, it means finding "best available" values of some objective function given a defined domain, including a variety of different types of objective functions and different types of domains.

Decision-making problems may be classified into two categories: deterministic and probabilistic decision models. In deterministic models good decisions bring about good outcomes. You get that what you expect; therefore, the outcome is deterministic (i.e., risk-free). This depends largely on how influential the uncontrollable factors are in determining the outcome of a decision, and how much information the decision-maker has in predicting these factors.

Those who manage and control systems of men and equipment face the continuing problem of improving (e.g., optimizing) system performance. The problem may be one of reducing the cost of operation while maintaining an acceptable level of service, and profit of current operations, or providing a higher level of service without increasing cost, maintaining a profitable operation while meeting imposed government regulations, or "improving" one aspect of product quality without reducing quality in another. To identify methods for improvement of system operation, one must construct a synthetic representation or model of the physical system, which could be used to describe the effect of a variety of proposed solutions.

A model is a representation of the reality that captures "the essence" of reality. A photograph is a model of the reality portrayed in the picture. Blood pressure may be used as a model of the health of an individual. A pilot sales campaign may be used to model the response of individuals to a new product. In each case the model captures some aspect of the reality it attempts to represent.

Since a model only captures certain aspects of reality, it may be inappropriate for use in a particular application for it may capture the wrong elements of the reality. Temperature is a model of climatic conditions, but may be inappropriate if one is interested in barometric pressure. A photograph of a person is a model of that individual, but provides little information regarding his or her academic achievement. An equation that predicts annual sales of a particular product is a model of that product, but is of little value if we are interested in the cost of production per unit. Thus, the usefulness of the model is dependent upon the aspect of reality it represents.

If a model does capture the appropriate elements of reality, but capture the elements in a distorted or biased manner, then it still may not be useful. An equation predicting monthly sales volume may be exactly what the sales manager is looking for, but could lead to serious losses if it consistently yields high estimates of sales. A thermometer that reads too high or too low would be of little use in medical diagnosis. A useful model is one that captures the proper elements of reality with acceptable accuracy.

Mathematical optimization is the branch of computational science that seeks to answer the question `What is best?' for problems in which the quality of any answer can be expressed as a numerical value. Such problems arise in all areas of business, physical, chemical and biological sciences, engineering, architecture, economics, and management. The range of techniques available to solve them is nearly as wide.

A mathematical optimization model consists of an objective function and a set of constraints expressed in the form of a system of equations or inequalities. Optimization models are used extensively in almost all areas of decision-making such as engineering design, and financial portfolio selection. This site presents a focused and structured process for optimization analysis, design of optimal strategy, and controlled process that includes validation, verification, and post-solution activities.

If the mathematical model is a valid representation of the performance of the system, as shown by applying the appropriate analytical techniques, then the solution obtained from the model should also be the solution to the system problem. The effectiveness of the results of the application of any optimization technique, is largely a function of the degree to which the model represents the system studied.

To define those conditions that will lead to the solution of a systems problem, the analyst must first identify a criterion by which the performance of the system may be measured. This criterion is often referred to as the measure of the system performance or the measure of effectiveness. In business applications, the measure of effectiveness is often either cost or profit, while government applications more often in terms of a benefit-to-cost ratio.

The mathematical (i.e., analytical) model that describes the behavior of the measure of effectiveness is called the objective function. If the objective function is to describe the behavior of the measure of effectiveness, it must capture the relationship between that measure and those variables that cause it to change. System variables can be categorized as decision variables and parameters. A decision variable is a variable, that can be directly controlled by the decision-maker. There are also some parameters whose values might be uncertain for the decision-maker. This calls for sensitivity analysis after finding the best strategy. In practice, mathematical equations rarely capture the precise relationship between all system variables and the measure of effectiveness. Instead, the OR/MS/DS analyst must strive to identify the variables that most significantly affect the measure of effectiveness, and then attempt to logically define the mathematical relationship between these variables and the measure of effectiveness. This mathematical relationship is the objective function that is used to evaluate the performance of the system being studied.

Formulation of a meaningful objective function is usually a tedious and frustrating task. Attempts to develop the objective function may fail. Failure could result because the analyst chose the wrong set of variables for inclusion in the model, because he fails to identify the proper relationship between these variables and the measure of effectiveness. Returning to the drawing board, the analyst attempts to discover additional variables that may improve his model while discarding those which seem to have little or no bearing. However, whether or not these factors do in fact improve the model, can only be determined after formulation and testing of new models that include the additional variables. The entire process of variable selection, rejection, and model formulation may require multiple reiteration before a satisfactory objective function is developed. The analyst hopes to achieve some improvement in the model at each iteration, although it is not usually the case. Ultimate success is more often preceded by a string of failures and small successes.

At each stage of the development process the analyst must judge the adequacy and validity of the model. Two criteria are frequently employed in this determination. The first involves the experimentation of the model: subjecting the model to a variety of conditions and recording the associated values of the measure of effectiveness given by the model in each case. For example, suppose a model is developed to estimate the market value of single-family homes. The model will express market value in dollars as a function of square feet of living area, number of bedrooms, number of bathrooms, and lot size. After developing the model, the analyst applies the model to the valuation of several homes, each having different values for the characteristics mentioned above. For this, the analyst finds market value tends to decrease as the square feet of living area increases. Since this result is at variance with reality, the analyst would question the validity of the model. On the other hand, suppose the model is such that home value is an increasing function of each of the four characteristics cited, as we should generally expect. Although this result is encouraging, it does not imply that the model is a valid representation of reality, since the rate of increase with each variable may be inappropriately high or low. The second stage of model validation calls for a comparison of model results with those achieved in reality.

A mathematical model offers the analyst a tool that he can manipulate in his/her analysis of the system under study, without disturbing the system itself. For example, suppose that a mathematical model has been developed to predict annual sales as a function of unit selling price. If the production cost per unit is known, total annual profit for any given selling price can easily be calculated. However, to determine the selling price to yield the maximum total profit, various values for the selling price can be introduced into the model one at a time. The resulting sales are noted and the total profit per year are computed for each value of selling price examined. By trial and error, the analyst may determine the selling price that will maximize total annual profit. Unfortunately, this approach does not guarantee that one obtained the optimal or best price, because the possibilities are enormous to try them all. The trial-and-error approach is a simple example for sequential thinking. Optimization solution methodologies are based on simultaneous thinking that result in the optimal solution. The step-by-step approach is called an optimization solution algorithm.

Progressive Approach to Modeling: Modeling for decision making involves two distinct parties, one is the decision-maker and the other is the model-builder known as the analyst. The analyst is to assist the decision-maker in his/her decision-making process. Therefore, the analyst must be equipped with more than a set of analytical methods.

Specialists in model building are often tempted to study a problem, and then go off in isolation to develop an elaborate mathematical model for use by the manager (i.e., the decision-maker). Unfortunately the manager may not understand this model and may either use it blindly or reject it entirely. The specialist may feel that the manager is too ignorant and unsophisticated to appreciate the model, while the manager may feel that the specialist lives in a dream world of unrealistic assumptions and irrelevant mathematical language.

Such miscommunication can be avoided if the manager works with the specialist to develop first a simple model that provides a crude but understandable analysis. After the manager has built up confidence in this model, additional detail and sophistication can be added, perhaps progressively only a bit at a time. This process requires an investment of time on the part of the manager and sincere interest on the part of the specialist in solving the manager's real problem, rather than in creating and trying to explain sophisticated models. This progressive model building is often referred to as the bootstrapping approach and is the most important factor in determining successful implementation of a decision model. Moreover the bootstrapping approach simplifies otherwise the difficult task of model validating and verification processes.

Subsequent sections consider the most appropriate methods for dealing with linear optimization, with emphasis placed on the formulation, solution algorithm, and the managerial implication of the optimal solution, with sensitivity analysis.


The first optimization technique, which is known as steepest descent, goes back to Gauss. The transportation problem and cycle cancelling methods are classical in optimization.

The usual attributions are to the 1940's and later. However, as early as 1930, A.N. Tolstoi [1930] published, in a book on transportation planning issued by the National Commissariat of Transportation of the Soviet Union, an article called Methods of finding the minimal total kilometer in cargo-transportation planning in space, in which he studied the transportation problem and described a number of solution approaches, including the, now well-known, idea that an optimum solution does not have any negative-cost cycle in its residual graph.

He might have been the first to observe that the cycle condition is necessary for optimality. Moreover, he assumed, but did not explicitly state or prove, the fact that checking the cycle condition is also sufficient for optimality.

Tolstoi illuminated his approach by applications to the transportation of salt, cement, and other cargo between sources and destinations along the railway network of the Soviet Union. In particular, a, for that time large-scale, instance of the transportation problem was solved to optimality.

We briefly review the article. Tolstoi first considered the transportation problem for the case where there are only two sources. He observed that in that case one can order the destinations by the difference between the distances to the two sources. Then one source

can provide the destinations starting from the beginning of the list, until the supply of that source has been used up. The other source supplies the remaining demands. Tolstoi observed that the list is independent of the supplies and demands, and hence it is applicable for the whole life-time of factories, or sources of production. Using this table, one can immediately compose an optimal transportation plan every year, given quantities of output produced by these two factories and demands of the destinations.

Next, Tolstoi studied the transportation problem in the case when all sources and destinations are along one circular railway line, in which case the optimum solution is readily obtained by considering the difference of two sums of costs. He called this phenomenon circle dependency.

Finally, Tolstoi combined the two ideas into a heuristic to solve a concrete transportation problem coming from cargo transportation along the Soviet railway network. The problem has 10 sources and 68 destinations, and 155 links between sources and destinations (all other distances are taken to be infinite).


Optimization problems are ubiquitous in the mathematical modeling of real world systems and cover a very broad range of applications. These applications arise in all branches of Economics, Finance, Chemistry, Materials Science, Astronomy, Physics, Structural and Molecular Biology, Engineering, Computer Science, and Medicine.

Optimization modeling requires appropriate time. The general procedure that can be used in the process cycle of modeling is to: (1) describe the problem, (2) prescribe a solution, and (3) control the problem by assessing/updating the optimal solution continuously, while changing the parameters and structure of the problem. Clearly, there are always feedback loops among these general steps:

Mathematical Formulation of the Problem: As soon as you detect a problem, think about and understand it in order to adequately describe the problem in writing. Develop a mathematical model or framework to re-present reality in order to devise/use an optimization solution algorithm. The problem formulation must be validated before it is offered a solution. A good mathematical formulation for optimization must be both inclusive (i.e., it includes what belongs to the problem) and exclusive (i.e., shaved-off what does not belong to the problem).

Find an Optimal Solution: This is an identification of a solution algorithm and its implementation stage. The only good plan is an implemented plan, which stays implemented!

Managerial Interpretations of the Optimal Solution: Once you recognize the algorithm and determine the appropriate module of software to apply, utilize software to obtain the optimal strategy. Next, the solution will be presented to the decision-maker in the same style and language used by the decision-maker. This means providing managerial interpretations of the strategic solution in layman's terms, not just handing the decision-maker a computer printout.

Post-Solution Analysis: These activities include updating the optimal solution in order to control the problem. In this ever-changing world, it is crucial to periodically update the optimal solution to any given optimization problem. A model that was valid may lose validity due to changing conditions, thus becoming an inaccurate representation of reality and adversely affecting the ability of the decision-maker to make good decisions. The optimization model you create should be able to cope with changes.

The Importance of Feedback and Control: It is necessary to place heavy emphasis on the importance of thinking about the feedback and control aspects of an optimization problem. It would be a mistake to discuss the context of the optimization-modeling process and ignore the fact that one can never expect to find a never-changing, immutable solution to a decision problem. The very nature of the optimal strategy's environment is changing, and therefore feedback and control are an important part of the optimization-modeling process.

The above process is depicted as the Systems Analysis, Design, and Control stages in the following flow chart, including the validation and verification activities:

Fig 1.1: Block diagram description of an Optimization problem


Optimization problems are classified according to the mathematical characteristics of the objective function, the constraints, and the controllable decision variables.

Optimization problems are made up of three basic ingredients:

An objective function that we want to minimize or maximize. That is, the quantity you want to maximize or minimize is called the objective function. Most optimization problems have a single objective function, if they do not, they can often be reformulated so that they do. The two interesting exceptions to this rule are:

The goal seeking problem: In most business applications the manager wishes to achieve a specific goal, while satisfying the constraints of the model. The user does not particularly want to optimize anything so there is no reason to define an objective function. This type of problem is usually called a feasibility problem.

Multiple objective functions: Often, the user would actually like to optimize many different objectives at once. Usually, the different objectives are not compatible. The variables that optimize one objective may be far from optimal for the others. In practice, problems with multiple objectives are reformulated as single-objective problems by either forming a weighted combination of the different objectives or else by placing some objectives as "desirable" constraints.

The controllable inputs are the set of decision variables which affect the value of the objective function. In the manufacturing problem, the variables might include the allocation of different available resources, or the labor spent on each activity. Decision variables are essential. If there are no variables, we cannot define the objective function and the problem constraints.

The uncontrollable inputs are called parameters. The input values may be fixed numbers associated with the particular problem. We call these values parameters of the model. Often you will have several "cases" or variations of the same problem to solve, and the parameter values will change in each problem variation.

Constraints are relations between decision variables and the parameters. A set of constraints allows some of the decision variables to take on certain values, and exclude others. For the manufacturing problem, it does not make sense to spend a negative amount of time on any activity, so we constrain all the "time" variables to be non-negative. Constraints are not always essential. In fact, the field of unconstrained optimization is a large and important one for which a lot of algorithms and software are available. In practice, answers that make good sense about the underlying physical or economic problem, cannot often be obtained without putting constraints on the decision variables.

Feasible and Optimal Solutions: A solution value for decision variables, where all of the constraints are satisfied, is called a feasible solution. Most solution algorithms proceed by first finding a feasible solution, then seeking to improve upon it, and finally changing the decision variables to move from one feasible solution to another feasible solution. This process is repeated until the objective function has reached its maximum or minimum. This result is called an optimal solution.

The basic goal of the optimization process is to find values of the variables that minimize or maximize the objective function while satisfying the constraints. This result is called an optimal solution.

There are well over 4000 solution algorithms for different kinds of optimization problems. The widely used solution algorithms are those developed for the following mathematical programs: convex programs, separable programs, quadratic programs and the geometric programs.


This section aims to summarise the most popular terminology found in the references utilised and present a unified interpretation of what the I believes these terms actually mean.


A vehicle refers to any entity capable of transporting freight, be it a truck, train, boat, plane, bike etc.


Commonly referred to as freight, goods encompass any raw materials or finished product

that is able to be transported from one vertex to another. They usually have a monetary value associated with them, and can often require a specific vehicle for transportation.


Weight is commonly used to describe a broad range of quality factors (these are described later in this section). Formally (but not restricted to), in this field what one tends to think of as the 'length' of an edge is known as its 'weight'. The term 'weight' is used because graphs are not limited to representing locations on a plane or in space; consequently edges could represent time, cost, and so on, generally a quantity which is to be kept minimal when going from any vertex to another.


Cost in most problems is the direct monetary cost of a product or service. Some examples of costs in transportation include:

• Lease, taxation or tolling of infrastructure including roads, train tracks, shipping channels, canals, aeroplane corridors, bridges, etc. these costs occur in transit on the edges (arcs) of a transport network.

• Transfer costs associated with the transfer of goods, usually from one mode of transport to another, or from transit to storage, ship -> truck, truck ->train, plane -> warehouse, etc. These costs occur at the nodes (vertices, cities) of the transport network.

• Storage of goods, often a suitable carrier is not available to transport goods therefore a holding fee or warehouse rental cost may be incurred while the goods are awaiting transfer. This cost will be incurred at a node of the transport network.

• Damage to goods, if goods are soiled or damaged during transportation, insurance or replacement costs may be incurred by the carrier.

• Lease of vehicles and fixed and variable running costs associated with vehicles.


Length is most commonly used to describe a geographical distance; this must not be confused with cost, as cost may often not be directly related to length.


Time constraints in transportation are as follows:

• Goods are often perishable, therefore these goods must be delivered to their destination in less than or equal to the amount of time allocated.

• Some edges have time dependent traffic conditions, meaning it may be quicker to transport at a particular time in the day/week/year. It is often not a simple edge time that will be factored into a quality measurement of a transportation system, rather the door-to-door time. For the case of air transport the longest edge in the total journey may be short, but forwarding the goods to their final destination may involve holding time and more transportation adding considerably to the total time.




ABC is a large, fully integrated petroleum company based in the United Arab Emirates. The company produces most of its oil in its own oil fields and then imports the rest of what it needs from Saudi Arabia. An extensive distribution network is used to transport the oil to the company's refineries and then to transport the petroleum products from the refineries to ABC's distribution centers.

ABC is continuing to increase market share for several of its major products. Therefore, management has made the decision to expand output by building an additional refinery and increasing imports of crude oil from Saudi Arabia. The crucial remaining decision is where to locate the new refinery. The addition of the new refinery will have a great impact on the operation of the entire distribution system, including decisions on how much crude oil to transport from each of its sources to each refinery (including the new one) and how much finished product to transport from each refinery to each distribution center. Therefore, the three key factors for management's decision on the location of the new refinery are

1. The cost of transporting the oil from its sources to all the refineries, including the new one.

2. The cost of transporting finished product from all the refineries, including the new one,

to the distribution centers.

3. Operating costs for the new refinery, including labor costs, taxes, the cost of needed supplies (other than crude oil), energy costs, the cost of insurance, the effect of financial incentives provided by the state or city, and so forth. (Capitol costs are not a factor since they would be essentially the same at any of the potential sites.)

Management has set up a task force to study the issue of where to locate the new refinery.

After considerable investigation, the task force has determined that there are three attractive potential sites.

Other relevant factors, such as standard-of-living considerations for management and employees, are considered reasonably comparable at these sites. Here the availability as well as requirements of the various depots are finite and constitute the limited resources. This type of problem is known as distribution or transportation problem in which the key idea is to minimize the cost or the time of transportation. Transportation problems are also

linear programming problems and can be solved by simplex method but because of practical significance the transportation problems are of special interest and it is tedious to solve them through simplex method.


After completion of this lesson you will be able to:

solve the transportation problems by:

Lowest cost entry method.

Test the optimality of the solution.


Let there be three units, producing oil, say, A1, A2 and A3 from where the oil has to be supplied to four refineries say B1, B2, B3 and B4. B4 being one of the potential sites for the refinery.

Let the amount of oil supplied by A1, A2 and A3 be a1, a2 and a3 respectively and the demands at the refineries be b2, b1, b3 and b4 respectively.

We assume the condition:

a1+a2+a3 = b1+b2+b3+b4

i.e., all oil produced is supplied to the different refineries.

Let the cost of transportation of million barrels of oil from A1 to B1 be c11. Similarly, the cost of transportations in other cases are also shown in the figure.

Let out of a1 amount of oil available at A1, x11 be taken at B1 refinery, x12 be taken at B2 refinery and to other refineries as well, as shown in the following figure.

Fig 1.2: Network diagram for the transportation problem

Total amount of oil to be transported from A1 to all destination, i.e., B1, B2, B3, and B4 must be equal to a1.

x11+x12+x13+x14 =a1 …………………………………………………………………………(1)

Similarly, from A2 and A3 the oil transported must be equal to a2 and a3 respectively.

x21+x22+x23+x24 = a2 ……………………………………………………………………….(2)

and x31+x32+x33+x34 = a3 ………………………………………………………………….(3)

On the other hand it should be kept in mind that the total number of oil delivered to B1 from all units must be equal to b1, i.e.,

x11+x21+x31 = b1 ……………………………………………………………………………...(4)

Similarly, x12+x22+x32 = b2 …………………………………………………………………..(5)

x13+x23+x33 = b3 ……………………………………………………………………………...(6)

x14+x24+x34 = b4 ……………………………………………………………………………...(7)

With the help of the above information we can construct the following table :

Table 2.1: Generalized Transportation problem table

The cost of transportation from Ai (i=1,2,3) to Bj (j=1,2,3,4) will be equal to


Where the symbol put before cij xij signifies that the quantities cij xij must be summed over all i = 1,2,3 and all j = 1,2,3,4.

Thus we come across a linear programming problem given by equations (1) to (7) and a linear function (8).

We have to find the non-negative solutions of the system such that it minimizes the function (8).


We can think about a transportation problem in a general way if there are m sources (say A1, A2, ..., Am) and n destinations (say B1, B2,....,Bn). We can use ai to denote the quantity of oil products concentrated at points Ai(i=1,2,...., m) and bj denote the quantity of oil products expected at points Bj(j =1,2,...,n).

We assume the condition:


implying that the total stock of oil is equal to the summed demand for it.


The following terms are to be defined with reference to the transportation problems:

(A) Feasible Solution (F.S.)

A set of non-negative allocations xij >=0 which satisfies the row and column restrictions is known as feasible solution.

(B) Basic Feasible Solution (B.F.S.)

A feasible solution to a m-origin and n-destination problem is said to be basic feasible solution if the number of positive allocations are (m+n-1).

If the number of allocations in a basic feasible solutions are less than (m+n-1), it is called degenerate basic feasible solution (DBFS) (otherwise non-degenerate).

(C) Optimal Solution

A feasible solution (not necessarily basic) is said to be optimal if it minimizes the total transportation cost.


Gathering the necessary data:

Let us consider the numerical version of the problem stated in the introduction and the mathematical formulation of the same in the next section.

The task force needs to gather a large amount of data, some of which requires considerable digging, in order to perform the analysis requested by management.

Management wants all the refineries, including the new one, to operate at full capacity. Therefore, the task force begins by determining how much crude oil each refinery would need to receive annually under these conditions. Using units of 1 million barrels, these needed amounts are shown on the upper side of Table 2.2. The bottom side of the table shows the current annual output of crude oil from the various oil fields. These quantities are expected to remain stable for some years to come. Since the refineries need a total of 360 million barrels of crude oil, and the oil fields will produce a total of 240 million barrels, the difference of 120 million barrels will need to be imported from Saudi Arabia.

Table 2.2: Production data for the case study

Since the amounts of crude oil produced or purchased will be the same regardless of which location is chosen for the new refinery, the task force concludes that the associated production or purchase costs (exclusive of shipping costs) are not relevant to the site selection decision. On the other hand, the costs for transporting the crude oil from its source to a refinery are very relevant. These costs are shown in Table 2.3 for both the three current refineries and the three potential sites for the new refinery.

Table 2.3: Cost data for transporting crude oil to ABC's refineries

In order to find the solution of this transportation problem we have to follow the steps given below.

(A) Initial basic feasible solution

(B) Test for optimization.

Let us consider these steps one by one.

(A) Initial Basic Feasible Solution :

Lowest cost entry method:

Table 2.4: Oil refinery problem model

Number of constraints = number of rows + number of columns

Total oil field supply must equal total oil refinery demand.

Potential refinery site DUBAI:

In this method we start with the lowest cost position. Here it is (2,4), allocate the smallest amount of supply or demand and then strike off the other positions in row 2, since all the available units are distributed to these positions.

Table 2.5: 1st allocation

(b) Consider the next higher cost positions among the remaining cells, i.e., (1,1) and (4,1) positions, allocate the cell where maximum allocations can be made. That is in (1,1) the amount allocated will be 80 while in (4,1) it will be 100. Therefore allocate (4,1) with the value 100. Hence the allocations in the column 1 is complete, so strike off the remaining cells in column 1.

Table 2.6: 2nd allocation

With the help of the above facts complete the allocation table as given below:

Table 2.7: Final allocations for Dubai

From the above facts, the cost of transportation from the oil fields to the refineries including the dubai site is:

=20*4+60*3+60*1+20*7+80*3+100*2+20*3 = 960

Potential refinery site SHARJAH:

After doing similar operations for the Sharjah site, we get the following cost results:

Table 2.8: Final costs for Sharjah

From the above facts, the cost of transportation from the oil fields to the refineries including the Sharjah site is:



Potential site ABU DHABI:


Table 2.9: Final costs for Abu Dhabi

From the above facts, the cost of transportation from the oil fields to the refineries including the Abu Dhabi site is:



(B) Test for Optimization :

In part (A) of this section we have obtained an initial basic feasible solution. Solutions so obtained may be optimal or may not be optimal, so it becomes essential for us to test for optimization.

For this purpose we first define non-degenerate basic feasible solution.

Definition: A basic feasible solution of an (m & n) transportation problem is said to be non-degenerate if it has following two properties :

(a) Initial basic feasible solution must contain exactly m+n-1 number of individual allocations.

(b) These allocations must be in independent positions. Independent positions of a set of allocations means that it is always impossible to form any closed loop through these allocations.

The following theorem is also helpful in testing the optimality.

Theorem: If we have a B.F.S. consisting of m+n-1 independent positive allocations and a set of arbitrary number ui and vj (i=1,2,...m; j=1,2,...n) such that crs = ur+vs for all occupied cells (r,s) then the evaluation dij corresponding to each empty cell (i, j) is given by

Algorithm for optimality test :

In order to test for optimality we should follow the procedure as given below:

Step 1: Start with B.F.S. consisting of m+n-1 allocations in independent positions.

Step 2: Determine a set of m+n numbers ui (i=1,2,....m) and vj (j=1,2,...n) such that for each occupied cells (r,s) crs = ur+vs

Step 3: Calculate cell evaluations (unit cost difference) dj for each empty cell (i,j) by using the formula,

dij = cij - ( ui+vj )

Step 4: Examine the matrix of cell evaluation dij for negative entries and conclude that

(i) If all dij > 0 , Solution is optimal and unique.

(ii)If all dij < 0 or At least one dij = 0 , Solution is optimal and alternate solution also exists.

(iii) If at least one dij < 0 , Solution is not optimal. If it is so, further improvement is required by repeating the above process. See step 5 and onwards.

Step 5: (i) See the most negative cell in the matrix [ dij ].

(ii) Allocate x to this empty cell in the final allocation table. Subtract and add the amount of this allocation to other corners of the loop in order to restore feasibility.

(iii) The value of x, in general is obtained by equating to zero the minimum of the allocations containing -x (not + x) only at the corners of the closed loop.

(iv)Substitute the value of x and find a fresh allocation table.

Step 6: Again, apply the above test for optimality till you find all dij < 0

Computational demonstration for optimality test:

Stepping stone method:

Consider the initial basic feasible solution as obtained by Least cost method in section (A) of this article.

DUBAI site:

Step 1: (i) In this table number of allocations = 4+4-1=7.

(ii) All the positions of allocations are independent.

Step 2: Determine a set of (m+n), i.e., (4+4) numbers u1, u2, u3,u4 and v1, v2, v3, and v4. for each occupied cells. For this consider the row or column in which the allocations are maximum (here, let us take first row). Now, take u1 as an arbitrary constant (say zero) then by using cij = ui+vj try to find all ui and vj as

Table 2.10: Final allocations for Dubai for

performing the stepping stone method








Thus u1 =0, u2=-2, u3=3 u4=-1 and v1 =3, v2=4, v3=0 and v4=3.

Step 3: Compute the opportunity cost for all the empty cells using ui+vj-cij.

Table 2.11: Opportunity cost calculation

Step 4

Check the sign of each opportunity cost. If the opportunity costs of all the unoccupied cells is negative, the given solution is the optimum solution. On the other hand, if one or more unoccupied cell has either positive or zero opportunity cost, the given solution is not an optimum solution and further savings in transportation cost are possible.

Step 5

Select the unoccupied cell with the largest positive opportunity cost as the cell to be included in the next solution.

Step 6

Assign alternate plus and minus signs at the occupied cells on the corner points of the closed path with a plus sign at the cell being evaluated.

Table 2.12: x determination

x-20=0 => Therefore x=20

The new allocations are:

Table 2.13: Final allocations after 1st iteration of stepping stone method

After repeating the process till we get all negative values in the south west corners, we reach the optimal solution:

Table 2.14: Optimal solution for Dubai

Therefore the optimal cost for the Dubai site is,



After performing the Stepping Stone Method on the Sharjah and Abu Dhabi site data also, the optimal transportation cost for:

The Sharjah site has come down from 960 to 920

The Abu Dhabi site it has come down from 1020 to 960.



The future scope of this project is as follows:

The other factors (such as operating cost etc) responsible for deciding on a potential site are currently being analysed.

The second half of the case study- The analysis of the cost of transporting finished products from refinery to distribution centres.

The stepping stone analysis of the same.

Analysis of the major variable costs.

MS Excel analysis.