This site uses cookies for learning about our traffic, we store no personal details. ACCEPT COOKIES DECLINE COOKIES What are cookies?
univerge site banner
Original Article | Open Access | Int. J. Mat. Math. Sci., 2022; 4(1), 15-34. | doi: 10.34104/ijmms.022.015034

Solution of Large-Scale Linear Programming Problem by Using Computer Technique

Shohal Hossain* Mail Img Orcid Img ,
Shamima Aktar Mail Img Orcid Img ,
Samme Akter Mithy Mail Img Orcid Img

Abstract

Linear programming (LP) is an important part of applied mathematics. This method has found its applications in important areas of product mix, blending, and diet problems. Steel, chemical, food processing industries and Oil refineries industry are also using LP with considerable success. But in practice LP can be very large. In this paper, our intent is to formulate an LP model of some large-scale real-life-oriented problems and to apply computer techniques for solving these problems. Starting with the graphical procedure which provides an ample amount of understanding of some fundamental concepts, the simple procedure of solving LP problems is developed. Finally, a special class of LP problem, namely Transportation is taken up and solved. We also solved the simplex system by using FORTRAN programming. 

INTRODUCTION

Linear programming (LP) is also called linear optimi-zation its applies to optimization models inside of which the objective and constraint functions are strictly linear. The technique are used in large range of applications, including food and agriculture, different type of industry, transportation, economics, health care systems, military, behavioral sciences and the social sciences, etc. It also boasts efficient computation algorithms for problems with a great constraints and variables. 

Actually, by reason of its tremendous computation efficiency, LP forms the spine of the solution algo-rithms for operations research model, including with stochastic, integer and non-linear programming. In this paper, our intent is to formulate LP problem of a size-able large-scale real life oriented problems and to develop FORTRAN computer program for solving it and analyses the solution of the problem. To do this we have to talk about the following prerequisites. 

Programming problem

Programming problem is said to efficient and easy to use of little resources. By resources, we have a tendency to mean personnel material, machine, land and capital, and so on. These problems are extre-mely useful nowadays because of their applicability to real-world problems in industry, government offices, military management, and business establish- ments. Programming problem is sometimes dubbed as optimization problems. In a number of problems, we would like to attenuate or maximize a numerical function subject to certain constraints or restrict-tions. There are many classical systems are avail-able to solve such problems. But theyre not enough, as more and sophisticated problems arise. Hence new methods are being developed from time to time. The type of programming problems can be separated into two sub-classes: 1st LP and 2nd non-LP problems. In this paper, we shall discuss the linear programming problem in detail. In applied mathematics, the target function and constraints are all linear expressions in some unknown variables. The great mathematician G. B. Dantzig formulated the general linear programming problem and devi-sed the most popular simplex method for solving such problems in 1947. Scientists have been using this method since 1951.

Basic form of mathematical programming problem

The Basic form of mathematical programming problem from Rao, (2005) is given below:

Optimize Z=f(X)

Subject to g_i (X)≤0,i=1,2,………,m

X≥0

Where, f(X) and g(X) can be taken to be general functions if the vector  X=(x_1,x_2,x_3,……,x_n )  εR^n. Frequently these functions are taken to be continuous or continuously differentiable. Thus we will have to find a column vector X which optimizes (minimizes or maximizes) the objective or targeted function f(X) subject to the m  constraints – 

g_i (X)≤0,i=1,2,………,m. 

In the function f and all g_i are linear functions of X, then the problem is called to linear programming. Yet, if any one of these functions is non-linear, then it is said a non-linear programming problem. For our purpose well stick on to a maximizing problem. Note that minf (X)=-max⁡〖 (-f(X))〗. Therefore minimize problem can be change to a maximizing problem. If we run into equality constraints like h(X)=0, it can be changed to a set inequalities: h(X)≤0, and  h(X)≥0. This is turn is equal to a pair of constraints like  h(X)≤0 and -h(X)≥0. Hence, with none loss of generality, we will write the mathematical program-ming problem as follows:

maximizeZ=f(X)

Subjecttog_i (X)≤0,i=1,2,………,m

X≥0. 

General form of linear programming Problem (LPP)

A LP problem is abbreviated by LPP mathematically; a general LPP can be stated as follows:

OptimizeZ=c_1 x_1+c_2 x_2+⋯………c_n x_n  ,

Subject to the conditions

a_11 x_1+a_12 x_2+⋯+a_1j x_j+⋯+  a_1n x_n (≤,=,≥)b_1

a_21 x_1+a_22 x_2+⋯+a_2j x_j+⋯+  a_2n x_n (≤,=,≥)b_2

⋮⋮⋮⋮

a_i1 x_1+a_i2 x_2+⋯+a_ij x_j+⋯+  a_in x_n (≤,=,≥)b_i

⋮⋮⋮⋮

a_m1 x_1+a_m2 x_2+⋯+a_mj x_j+⋯+  a_mn x_n (≤,=,≥)b_m

And non-negativity restrictions x_j≥0,j=1,2,………..n.

Here in the set of conditions we have written (≤,=,≥)  which means that any of the three signs may be there. Also optimize means either maximize or mini-mize. The linear function which is to be optimized called the target function. The conditions are referred as constraints. Any problem which can be formulated in the in excess of form is called a L.P.P. By finding a solution to (1.3) we mean to find the non-negative values of variables x_1+x_2+⋯+x_nwhich optimize Zand assure all the constraints.

The Standard form of LP problem

The characteristics of standard form are as follows as –

  1. All constraints are equations apart from the non-negativity restrictions that stay inequalities.
  2. The right-hand side element of each constraints equation is non-negativity.
  3. All variables are non-negativity.
  4. The targeted of the maximization or the minimization type.

METHOLODOGY

One of the main point of LP is recognize a problem which can be handed by LP and then to formulate the mathematical model of it. The most steps to represent a linear program in symbols are as follows:

Step1. Establish the unknown decision variables to be determined and assign symbol to them.

Step2. Establish all the restrictions in the problem and show them as linear equations.

Step3. Establish the objective or aim and represent it as a linear function of selection variables.

The procedures are going to be clearer by the sub-sequent examples. Formulation of models is not any science but an art, which can be more refined to you by practice.

Requirements for formulating a Linear Problem

There are six basic necessary requirements for the formulation of a linear programming problem (LPP) –

Well defined linear impartial function. A linear impartial function should be clearly defined mathe- matically.

Alternative courses of action. There should be different courses of action so that a problem of choosing best may arise.

The limitation is obliged to effective of being ex-pressed mathematically in the form of linear equ- ation or inequalities.

Linear constraint must be expressed mathematic-cally. The constraints have to be effective of being expressed mathematically in the form of linear equation or inequalities.

Variables in the problem have to be interrelated, so that it can be possible to formulate mathematical relationship among them.

Resources must be limited i.e. they must be finite and economically quantifiable.     

Uses of LP in Business and industry

We can use the advantage of LP problem in the section of business and industry. Now we discuss some uses of LPP in the above section. Linear programming may be applied to many fields of study. It is used most ex-tensively in business and economics, but also can be utilized for a few engineering problems. Industries use linear programming (LP) models including manu-facturing, telecommunications, transportation, and energy. It has proved useful in modeling diverse sorts of problems in planning, routing, scheduling, assign-ment, and design/style. Metal working industries use linear programming (LP) for shop loading and for determining the section between producing and buying a selected or specific part. Paper and textile industries have used LP to define the optimal cutting method in order to minimize trim losses. LP has also been used in determining the best route for aircrafts and ships. Another uses of LP is in the food processing industry that is to establish the optimal mix of feeds, optimal allocation of crates from various plants to different ware houses etc. LP has also been used in establishing the best route for aircrafts and ships. Application of LP has also been made within the service industries. Accounting firms use it for asset valuation and for assigning auditors to tasks in an optimal way. Finan-cial institutions and firms have used LP for evaluating investment plans, for the choice of Bond or Mutual Funds Portfolios, for Capital budgeting and for long- range financial planning, etc. Similarly, in advertising media, LP has been employed for assigning advertising dollars to different media plans. Thus we see that we will the LPP within the various sections of business and industry. So its crucial method and its applications are in worldwide (Niazai et al., 2021; Sami et al., 2021). 

Some example of applications of linear program-ming technique

Major areas of the application of LP technique are as mentioned below:

Production planning

Feed mix and Transportation

Stock cutting or slitting

Water quality management

Oil drilling and production

Rally line balancing

Advertising media selection

Site location & Applications in agriculture

Assignment of jobs.

FORTRAN computer program for linear program-ming

Although very small LP models are often solved with simply a pencil and paper, by methods described in any textbook; this would never be done for practical problems, the amount of calculation involved in solved in solving a realistic model always necessitates the use of a computer. Practical LP models can be very large. Most models have a few hundred limitations and variables and solve a matter of minutes on most com-puters sizeable number of large models involving thousands of limitations and variables have also been built. With this model the solution times are usually measured in hours. There also exist a few models with hundreds of limitations and variables. Such models can take days to solve on a computer. The largest liner programming model reported to date has a hundred thousand limitations. For a LP model the number of limitations is a fairly good indicator of its compu-tational difficulty. As a very rough rule of thumb he time to solve liner programs model increase as the cube of the number of limitations. By doubling the number of limitations one would therefore expect to multiply the solution time by eight. There is clearly great virtue in organizing a mathematical programming calculation as efficiently as possible on a computer. One of the major characteristics of practical model which is exploited in the calculations in sparsely. If one examines the coefficients in a realistic sized model one will almost always find that the great majority of them are zero. For a thousand limitations model, for example, one would probably only find that about 1% of the coefficients were non-zero. The dominant feature of sparsely in practical models is often over-looked when mathematical programming is studied theoretically through small-contrived examples. Com-puter programs which we solve practical mathematical programming models almost always make use of sparsely. 

Mathematical Formation and Graphical Repre-sentation of LPP

Graphical Procedure

The graphical ways for determination LPP are pre-dicated on a well-defined set of logical steps. Fol-lowing this systematic procedure, the given LP pro-blems is often solved with a lowest amount of com-putational effort. We shall explain the procedure by taking a simple problem given below

Working procedure

Working procedure to solve a LPP graphically from Grewal, (1998) is given bellow:

Step 1: Construct the given problem as a LPP.

Step 2: Plot of the specified limitations as equalities on x_1 〖-x〗_2co-ordinate plane and determined the convex     region formed by them.

Step 3: Determine the vertices of the convex region and find the worth of the objective or aimed function at each vertex. The vertex provides the prime value of the objective function gives the specified prime solution to the problem. Otherwise: Draw the dotted line through the origin representing the targeted function with Z=0. As Z is increased from zero, this line moves to the right remaining parallel to itself. We continue sliding this line till its farthest far away from the origin and passes through just one vertex of the convex region. This is the vertex where the utmost highest value of Z is attained. When its required to attenuate Z, value of Z is increased till the line passes through the closest vertex of the convex region. The drawback of this method is that the problem of higher dimensionality cant be solved by this method. A problem of three dimensions can also be handled by this method but it is complicated enough.

Limitations of the graphical procedure

As mentioned before this system can be applied to problems involving only two variables while the lions share of the practical situations do involved over than two variables. Therefore it is not a heavy tool of LP. But the method is really useful to explain LP technique to the persons who are not familiar with this. It is easy to understand even to school students. In a class room, this system can be used as a first sight method to explain “how to solve a LPP”. The various conse-quences of the optimal solutions and the simplex sys-tem can be demonstrated with the help of graphical method.  

Some real life linear programming problems

By using Mathematica from Don, (2004) we can solved any LP problem with two or three variables and draw a physical picture. Some practical problem is showed below.

Production Problem

Hasim food limited company produced two different types of Seejan juices (250ml pack and 200ml pack). Each unit of 250ml pack has 36 pices and each unit of 200ml pack has 48 pieces. The company builds profit of 3tk and 2tk each unit of products of 250ml and 200ml pack respectively. The products are produced in a common production process and are sold in two separate markets. Machine works 20hours in a day. It takes 1 minute to produce 72 pieces of 250ml pack and takes 1 minute to produce 144 pieces of 200ml pack. The market has been surveyed and company officially feels that the highest number of units 250ml pack that can be sold is 2300 and the highest number of units 200ml pack is 3000 units. Subject to these limitations the products can be cold in any convex combination. We formulate the overhead problem as a LP problem and solve it graphically by using mathe-matica.

Solution

Formulation of LP problem of the problem: 

Let x_1 and x_2 be the number of unit of product 250ml pack and 200ml pack respectively.

Objective function

The company makes profit of 3tk and 2tk per pieces of products of 250ml pack and 200ml pack respectively and each unit of 250ml pack has 36 pices and each unit of 200ml pack has 48 pieces.

So the overall profit -

Maximize Z=3×36x_1+2×48x_2

Subject to the constraints

It takes 1 minute to produce 72 pieces of 250ml pack and takes 1 minute to produce 144 pieces of 200ml pack. So it takes 36⁄72  or  1⁄2 minute to produce 1 unit of 250ml pack and takes 48⁄144  or  1⁄3 minute to pro-duce 1 unit of 200ml pack.

So that -

1⁄2 x_1+1⁄3 x_2≤20×60

or,1⁄2 x_1+1⁄3 x_2≤1200          

And the highest number of units 250ml pack that can be sold is 2300 and the highest number of units 200ml pack is 3000 units.  

So that -

x_1≤2300 

And x_2≤3000          

So the LP model as

Maximize Z=3×36x_1+2×48x_2

Subject to  (  1)⁄2 x_1+1⁄3 x_2≤1200 

x_1≤2300 

x_2≤3000          

Where,x_1≥0 &〖 x〗_2≥0

Solution by mathematica

Input

Maximize[{108 x_1+96 x_2,{(1/2) x_1+(1/3) x_2≤1200,

x_1≤2300,x_2≤3000,x_1≥0,x_2≥0}},{x_1,x_2}]

Output 

{331200,{x_1→400,x_2→3000}}

Input

RegionPlot[{(1/2) x_1+(1/3) x_2≤1200,x_1≤2300,x_2≤3000,x_1≥0,x_2≥ 0},

  {x_1,-1000,4000},{x_2,-1000,4000}]

Output

The prime solution is the intersection of the two line(  1)⁄2 x_1+1⁄3 x_2≤1200 & x_2≤3000 which yields x_1=400 & x_2=3000 the associated minimum value of the feed mix is -

Z=108×400+96×3000

=331200tk

Fig. 1: Feasible Region of the example.

Problem 2.2 (Diet Problem)

Zakir Farms uses at least 800 lb of particular feed daily. The particular feed is a mixture of corn and soybean flour meal with the following compositions Taha, (2003):

Table 1:  lb per lb feedstuff.

The dietary requirements of the particular feed are minimum 30% protein and at most 5% fiber. Zakir Farms wishes to work out the daily minimum-cost feed mix.

Solution

Because the feed mix consists of corn and soybean flour meal, the choice variables are defined as:

〖 x〗_1=lb of corn within the daily mix

x_2=lb of Soybean flour meal within the daily mix

The targeted function seeks to shorten the total every day price of the feed mix and is thus indicate as

Minimize Z=.3x_1+.9x_2

The obstruction of the model reflect the per day amount needed and therefore the dietary demand. Because Zakir Farms needs at minimum 800 lb of feed each day, the related constraint are often expressed as -

x_1+x_2≥800

As for the protein dietary demand constraint, the amount of protein take in x_1 lb of corn and x_2  lb of soybean flour meal is (.09x_1+.6x_2)lb. This quantity must equal a lowest of 30% of the total feed mix (x_1+x_2)lb; thats

.09x_1+.6x_2≥.3(x_1+x_2)

In the same manner, the fiber constraint is made as 

.02x_1+.06x_2≤.05(x_1+x_2)

The constraints are clarify by grouping all the terms in x_1 and x_2 and moving them to the left side inequality, leaving only a constant on the right-hand side. The complete model will becomes -

Minimize Z=.3x_1+.9x_2

subject to    x_1+x_2≥800                      

.21x_1-.30x_2≤0   

.03x_1-.01x_2≥0   

Where,   x_1,x_2≥0   

Solution by mathematica 

Input

Minimize [{.3 x_1+.9 x_2,{x_1+x_2≥800,.21 x_1-.30 x_2≤0,

.03 x_1-.01 x_2≥0,x_1≥0,x_2≥0}},{x_1,x_2})

Output

{437.647,{x_1→1470.588,x_2→329.412}}

Input

Region Plot [{x_1+x_2≥ 800,.21 x_1-.30x_2≤0,.03 x_1-.01 x_2≥0,

x_1≥0,x_2≥0},{x_1,-500,2000},{x_2,-500,2000}]

Fig. 2: Feasible Region of the example.

The optimal solution is the joining of the two line〖 x〗_1+x_2≥800 & .21x_1-.30x_2≤0 which yields x_1=470.588 lb & x_2=329.412 lb. The associated mini-mum value of the feed mix is -

 Z=.3×470.588+.9×329.412

=437.647tk per day

Simple Method with computer Programming for Solving LPP

Simplex system is the most popular process to solve the general linear programming problem. George B. Dentzing in the year 1947 formulated the general LPP and devised the simplex system for solving these LPP. In 1979, Khachiyan devised the ellipsoid method. More recently, in 1984 N Karmarkar developed a new system to solved LPP. For large problems the system provides solution faster than the previous system. We want to discuss the simplex system in detail and develop FORTRAN computer program for solving problem.

Simplex System

In the previews, we have to formulate the general LP problem which is developed by Rao,(2005). Our aim is to find an n-component vector X=(x_1,x_2,…x_n )^T which optimizes the linear objective function Z=CX subject to the constraints AX=b and X≥0. HereA is am×n matrix where m

The case m>n is similar to the one with m-n. In this case also we get a unique solution provided the system of equations AX=b is consistent.

We rewrite the general LP problem –

Maximize Z=CX

subject to AX=b

X≥0

Working procedure of the simple method

Assuming the existence of a beginning basic feasible solution, and prime solution to any LPP by simplex system is found from Grewal, (1998) as follows:

Step 1.(i)  Check whether the target

function is to be maximized or minimize

If Z=c_1 x_1+c_2 x_2+c_3 x_3+⋯+c_n x_n is to be de-creased, then convert it into a problem of maxi-mization, by writing -

Minimize Z=Maximize (-Z)

(ii) Check whether all bs are non-negative.

If any of the b_i^ s is negative, multiply each side of that constraint by -1 so on make its right hand side posi-tive.

Step 2.Express the issue within the standard form.

Convert all inequalities of constraints into equations by introducing slack/surplus variables within the cons-traints giving equations of the form –

a_11 x_1+a_12 x_2+a_13 x_3+⋯+s_1+0s_2+0s_3+⋯=b_1

Step 3.Find an initial basic feasible solution.

If there are m equations involvingn unknowns, then assign zero values to any (n-m) of the variables for finding a solution. Starting with a basic solution for which x_j:j=1,2,…,(n-m) are each zero, find all〖 s〗_i. If all〖 s〗_i are ≥0, the basic solution is feasible and non-degenerate. If one or more of the〖 s〗_i values are zero, then the solution is degenerate.

Table 2: The above information is conveniently ex-pressed in the following simplex. 

Here, s_1,s_2,s_3, etc. are said to basic variables and x_1,x_2,x_3 etc. are said to non-basic variables. Basis refers to the basic variables〖 s〗_1,s_2,s_3……c_j row in-dicates the coefficients of the variables in the targeted function; while c_B-column indicates the basic variables only in the targeted function. b-column indicates the values of the basic variables while remaining variables will always be zero. The coefficients of x^ s in the constraint equations constitute the body matrix while coefficients of slack variables constitute the unit matrix.

Step 4.  Apply optimality test.

Compute C_j=c_j-Z_j where Z_j=∑▒〖c_B a_ij 〗

C_j-row is called net evaluation row and denotes the per unit increases in the targeted function if the variable heading the column is bought into the solution. If all〖 C〗_j are non-positive, then the primary general feasible solution is prime. If even one〖 C〗_j is non-negative, then the running feasible solution is not prime and proceeds to the next step.

Step 5.  (i)Identify the incoming & outgoing variables.

If there are more than one positive〖 C〗_j, then the in-coming variable is the one that heads the column containing maximum C_j. The column containing its referred to as the lead column which is shown marked with an arrow at rock bottom. If more than one variable has the same maximum, C_j any of these variables may be selected arbitrarily as the incoming variable. Now divide the elements under b-column by the corresponding elements of key column and choose the row containing the lowest nonnegative ratio θ. Then replace the corresponding basic variable. It is named as the outing variable. The corresponding row is termed the main row which is expressed marked with an arrow on its right end. The element at the intersection of the main row and key column is named the main element which is expressed bracketed. If all these ratios are ≤0, the incoming variable may be made as bigger as we please without violating the feasibility condition. Hence the matter problem has a borderless solution and no additional iteration is required.

(ii)  Iterate towards an optimal solution.

Drop the outgoing variable and introduce the incoming variable together with its related value under c_B column. Convert the main element to unity by diverge the main row by the main element. Then make all other elements of the main column 0 (zero) by subtracting proper multiples of main row from the opposite rows.

Step 6. Go to step 4 and repeat the computational procedure up to either an unbounded solution is obtained.

In this paper we like to discuss two-phase simplex method which is given below.  

Two phase method

 After adding non-natural variables to the constraints of the LP problem we can find a pair of m unit vectors which constitute the primary basis. In phase-I we try to find one general feasible solution to the authentic or real problem, if one exists in Phase-II either the prime solution is found out or we come to the conclusion that no finite optimum solution exists.

Flow Chart

Simplex Algorithm for Maximization LPP

In Phase-I, the value of the non-natural variables are taken as -1 and those of other variables as zero. We find the targeted function as -

〖max 〗⁡〖Z^* 〗=(-x_(n+1)-x_(n+2)⋯⋯⋯⋯-x_(n+m) )

The constraints being stable. The problem then is solved by Simplex system. As each X_(n+i),i=1⋯⋯⋯m is non-negative, in the most of the new targeted function is expected to be zero. Now three cases arise:

Max. Z^*=0 And the non-natural variables are all removed from the basis.

Max. Z^*<0 And some the non-natural variables show up in the basis at a positive level.

Max. Z^*=0 And some the non-natural variables show up in the basis with value zero.

In case (1) we get a primary general feasible solution to the given LP problem and then proceed to find outstanding solution in Phase-II. In case (2) no feasible solution exists to the given LPP and hence we do not go to Phase-II to get outstanding solution. In case (3), we may or may not get a best general feasible solution to the real problem. But we move to Phase-II to get a best general feasible solution, if it survives. In Phase-II, we consider the actual costs related with the variables in the targeted function and assign a cost 0 to the non-natural variables. We now use the Simplex system to the modified simplex table obtained at the end of Phase-I.

Properties of the Simplex System

The important properties of the simplex system are summarized as follows. 

The simplex System for minimizing the targeted function starts at a feasible solution for the equivalent model and moves to an adjacent general possible solution that does not increase the value of the targeted function. However, a best solution for the real model has been reached, if such a result doesnt exist. That is, if all of the portions of the non-general variables in the targeted function equation are less than or equal to 0 (zero) at some point, also an opti-mal result for the real model has been reached. If such a result does not keep going or live, a best result for the real model has been reached. Thats, if all coefficients of the non-basic variables in the targeted function equation are bigger than or equal to 0 at some given point, also a best result for the real model has been reached.

If anon-natural variable is in a classic solution of the equivalent model at a non-zero level, then no possible solution for the real model exists. On the contrary, if the classical solution of equivalent model does not contain anon-natural variable at a non-zero level, the solution is also classical for the original model.

If all of the slack, surplus, and non-natural are zero when an classical solution of the equivalent model is reached, also all of the constraints in the real model are strict “equivalence” for the values of the variables that optimize the targeted func-tion.

If a non-basic variable has a 0 (zero) coefficient in the targeted function equation when a classic solution is reached, there are multiple classic solutions. In fact, theres perpetuity of optimal result. The simplex system finds only one optimal result and stops.

Once anon-natural variable leaves the pair of general variables (the basis), it will never enter the basis again. So all calculations for that vari-able can be ignored in next steps.

When selecting the variable to leave the current basis:

If two or more ratios are smallest, choose one arbitrary.

If a non-negative ratio does not exist, the targeted function in the real model is not bounded by the constraints. Therefore, a finite optimal result for the real model does not existence.

If a basis has a variable at the 0 (zero) level, it is said a degenerate basis.

While cycling is possible, without any practical problems for which the simplex system break down to converge.

FORTRAN Program for solving simplex method

In this paper, our intent is to formulate linear program-ming model of some large-scale real life oriented pro-blems and to apply computer program for solving these. Computer programs have been written with the help of Ali, (2001), Lipchitz, (2002) and Reddy, (1999) for the simplex algorithm that can take advance of special forms of the model. The FORTRAN com-puter program for solving LP is given bellow. 

FORTRAN Program

!****************************************************************

########LINEAR PROGRAMMING#########

!            **********SIMPLEX METHOD**********

!****************************************************************

!   LIST OF MAIN VARIABLES:                               

!                                                       

!  C:         MAXIMIZE = 1,MINIMIZE = 2               

!  N:         NUMBER OF VARIABLES OF ECONOMIC FUNCTION 

!              (TO MAXIMIZE OR MINIMIZE).               

!  M:         NUMBER OF CONSTRAINTS                    

!  M1:        NUMBER OF <= CONSTRAINTS         

!  M2:        NUMBER OF >= CONSTRAINTS           

!  M3:        NUMBER OF  = CONSTRAINTS                    

!  A,M,N,MP,NP,M1,M2,AND M3 ARE INPUT

 PARAMETERS

!  ICASE,IZROV,AND IPOSV ARE OUTPUT PARAMETERS 

!  MMAX:  IS THE MAXIMUM NUMBER OF 

CONSTRAINTS SXPECTED 

!  MMAX:  IS THE MAXIMUM NUMBER OF VARIABLES SXPECTED 

!  EPS:        IS THE ABSOLUTE PRECISION, 

!  WHICH SHOULD BEADJUSTED TO THE SEALE OF 

YOUR VARIABLES 

!**************************************************************** 

   PARAMETER(MP=100,NP=100)

   REAL X(MP,NP),Y(MP,NP),R

   INTEGER C,N,M,M1,M2,M3,IPOSV(MP),IZROV(NP)

   PRINT *,

   PRINT *,      ############ LINEAR PROGRAMING ###

#########

   PRINT *,       ************* SIMPLEX METHOD ************

   PRINT *,

   WRITE(*,10,ADVANCE=NO); READ *,C

   IF(C.LE.0.OR.C.GE.3) PAUSE Bad input.

   WRITE(*,20,ADVANCE=NO); READ *,N

   WRITE(*,30,ADVANCE=NO); READ *,M1

   WRITE(*,40,ADVANCE=NO); READ *,M2

   WRITE(*,50,ADVANCE=NO); READ *,M3

   M=M1+M2+M3

   X=0.

   PRINT *,Input Economic Function:

   DO i=2,N+1

  WRITE(*,60,ADVANCE=NO) i-1; READ *,X(1,i)

  Y(1,I)=X(1,i)

   END DO

   WRITE(*,61,ADVANCE=NO); READ *,X(1,1)

    Y(1,1)=X(1,1)

   IF(C.EQ.2) then

    DO I=1,N+1

   X(1,I)=-X(1,I)

END DO

   END IF     

   DO i=1,M

   WRITE(*,70) i

   DO j=2,N+1

   WRITE(*,60,ADVANCE=NO) j-1; READ *,R

  X(i+1,j) = -R

  Y(I+1,J) =R

     END DO

    WRITE(*,61,ADVANCE=NO); READ *,X(i+1,1)

Y(I+1,1)=X(i+1,1)   

   END DO

   PRINT *,

   PRINT *, Input Table:

   DO I=1,M+1

   WRITE(*,*) (Y(I,J),J=1,N+1)

   END DO

   CALL MAIN(X,M,N,MP,NP,M1,M2,M3,ICASE,IZROV,IPOSV)

   PRINT *,

   IF(C.EQ.1)THEN

     PRINT *, Maximum of Objective Function= ,X(1,1)

   ELSE IF(C.EQ.2)THEN

   X(1,1)=-X(1,1)

   PRINT *, Minimum of Objective Function = ,X(1,1)

   END IF

   DO I=1,N

   DO J=1,M

   IF (IPOSV(J).eq.I) THEN

  WRITE(*,110) I,X(J+1,1)

 GOTO 28

    END IF

   END DO

    WRITE(*,110) I,0.0 

28 END DO

   PRINT *,

10  FORMAT( Maximize or Minimize? [MAX=1,MIN=2]..: )

20  FORMAT( Number of nonbasic variables: )

30  FORMAT( Number of <= inequalities..: )

40  FORMAT( Number of >= inequalities..: )

50  FORMAT( Number of = equalities.....: )

60  FORMAT( Coefficient #,I2,: )

61  FORMAT( Constant term..: )

70  FORMAT( Input constraint #,I2,: )

110 FORMAT(  X,I2, = ,F12.6)

STOP

END

   SUBROUTINE MAIN(X,M,N,MP,NP,M1,M2,M3,

ICASE,IZROV,IPOSV) 

   INTEGER M,N,MP,NP,M1,M2,M3,ICASE,IPOSV(M),

IZROV(N),MMAX,NMAX 

   REAL X(MP,NP),EPS 

   PARAMETER (MMAX=100,NMAX=100,EPS=1.E-6)

   INTEGER I,IP,IS,K,KH,KP,NL1,L1(NMAX),L2(MMAX)

,L3(MMAX) 

   REAL BMAX,Q1 

   IF(M.NE.M1+M2+M3) PAUSE Bad input constraint counts in simplx. 

   NL1=N 

   DO K=1,N 

     L1(K)=K    

     IZROV(K)=K 

   END DO 

   NL2=M

   DO I=1,M 

     IF(X(I+1,1).LT.0.)PAUSE(_^)Bad input tableau in simplx,

 Constants bi must be nonnegative.

     L2(I)=I

     IPOSV(I)=N+I 

!***************************************************************************************

!Initial lefthand variables.m1 type constraints are

 represented by having their slackv ariable 

!initially lefthand,with no non-natural variable.m2

 type constraints have their slack 

!variable initially lefthand,with a minus

 sign,and their non-natural variable handled implicitly 

!during their first exchange.m3 type 

constraints have their non-natural variable initially 

!left-hand.

!********************************************************************************

   END DO

   DO I=1,M2

   L3(I)=1

   END DO

   IR=0

   IF(M2+M3.EQ.0) GOTO 30 

!The origin is a feasible starting solution.Go to

 phase two.

   IR=1

   DO K=1,N+1             

  Q1=0.

  DO I=M1+1,M

  Q1=Q1+X(I+1,K) 

  END DO 

  X(M+2,K)=-Q1 

  END DO 

33 CALL SIMP1(X,MP,NP,M+1,L1,NL1,0,KP,BMAX) 

  IF(BMAX.LE.EPS.AND.X(M+2,1).LT.-EPS)THEN 

  ICASE=-1        

!Auxiliary objective function is still negative and

 cant be improved,

RETURN   !hence no feasible solution exists.

   ELSE IF(BMAX.LE.EPS.AND.X(M+2,1).LE.EPS)THEN 

!Auxiliary objective function is zero and cant be improved;

 we have a feasible starting vector.

!Clean out the non-natural variables corresponding to

 any remaining equality constraints by 

!goto 1s and then move on to phase two by goto 30.

  M12=M1+M2+1

  IF (M12.LE.M) THEN

  DO IP=M12,M 

  IF(IPOSV(IP).EQ.IP+N)THEN 

  CALL SIMP1(X,MP,NP,IP,L1,NL1,1,KP,BMAX) 

  IF(BMAX.GT.EPS) GO TO 29  

   END IF                    

   END DO                     

   END IF

   IR=0

   M12=M12-1

   IF (M1+1.GT.M12) GO TO 30 

   DO I=M1+1,M1+M2               

   IF(L3(I-M1).EQ.1)THEN 

   DO K=1,N+1 

   X(I+1,K)=-X(I+1,K) 

   END DO 

   END IF 

   END DO 

   GO TO 30            !Go to phase two.

   END IF 

  CALL SIMP2(X,M,N,MP,NP,L2,NL2,IP,KP,Q1) 

   IF(IP.EQ.0)THEN                                                 

    ICASE=-1 

  RETURN 

   END IF

 29 CALL SIMP3(X,MP,NP,M+1,N,IP,KP) 

   IF(IPOSV(IP).GE.N+M1+M2+1)THEN   

     DO K=1,NL1 

       IF(L1(K).EQ.KP) GOTO 31 

     END DO 

31 NL1=NL1-1 

    DO IS=K,NL1 

      L1(IS)=L1(IS+1) 

    END DO 

   ELSE

     IF(IPOSV(IP).LT.N+M1+1) GO TO 32

       KH=IPOSV(IP)-M1-N 

     IF(L3(KH).EQ.0) GO TO 32     

       L3(KH)=0                                                     

     END IF   

      X(M+2,KP+1)=X(M+2,KP+1)+1.

    DO I=1,M+2 

      X(I,KP+1)=-X(I,KP+1) 

    END DO 

32 IS=IZROV(KP)                

   IZROV(KP)=IPOSV(IP) 

   IPOSV(IP)=IS  

    IF (IR.NE.0) GO TO 33            

30 CALL SIMP1(X,MP,NP,0,L1,NL1,0,KP,BMAX) 

    IF(BMAX.LE.EPS)THEN           

      ICASE=0 

RETURN 

    END IF

   CALL SIMP2(X,M,N,MP,NP,L2,NL2,IP,KP,Q1)  

   IF(IP.EQ.0)THEN                

     ICASE=1 

RETURN 

   END IF 

   CALL SIMP3(X,MP,NP,M,N,IP,KP)  

   GO TO 32                        

END                            

   SUBROUTINE SIMP1(X,MP,NP,MM,LL,NLL,

IABF,KP,BMAX) 

   INTEGER MP,NP,MM,LL(NP),NLL,IABF,KP,K 

   REAL BMAX,X(MP,NP),TEST

    KP=LL(1) 

    BMAX=X(MM+1,KP+1)

   IF(NLL.LT.2) RETURN 

     DO K=2,NLL 

       IF(IABF.EQ.0)THEN 

         TEST=X(MM+1,LL(K)+1)-BMAX 

       ELSE

        TEST=ABS(X(MM+1,LL(K)+1))-ABS(BMAX) 

     END IF 

      IF(TEST.GT.0.)THEN 

        BMAX=X(MM+1,LL(K)+1) 

        KP=LL(K) 

      END IF 

     END DO 

RETURN

END 

SUBROUTINE SIMP2(X,M,N,MP,NP,L2,NL2,IP,KP,Q1) 

   INTEGER M,N,MP,NP,L2(MP),IP,KP,I,K 

   REAL X(MP,NP),EPS,Q0,Q,Q1,QP 

   PARAMETER (EPS=1.E-6) 

   IP=0 

    IF(NL2.LT.1) RETURN

      DO I=1,NL2 

    IF(X(I+1,KP+1).LT.-EPS) GO TO 56 

      END DO 

RETURN  

56 Q1=-X(L2(I)+1,1)/X(L2(I)+1,KP+1) 

   IP=L2(I)

    IF(I+1.GT.NL2) RETURN 

     DO I=I+1,NL2 

      II=L2(I)

    IF(X(II+1,KP+1).LT.-EPS)THEN 

      Q=-X(II+1,1)/X(II+1,KP+1) 

    IF(Q.LT.Q1)THEN 

      IP=II 

      Q1=Q 

    ELSE IF (Q.EQ.Q1) THEN 

      DO K=1,N 

      QP=-X(IP+1,K+1)/X(IP+1,KP+1) 

      Q0=-X(II+1,K+1)/X(II+1,KP+1) 

       IF(Q0.NE.QP)goto 57 

      END DO 

Some real life problem of LPP

By using above algorithm we can solved any LP problem. Some practical problem is given bellow.

Problem 

Consider the following LPP:

Minimize,    Z=x_1-3x_2+2x_3

 Subject to,    〖3x〗_1-x_2+2x_3≤7

〖-2x〗_1+4x_2≤12

-4x_1+3x_2+8x_3≤10

x_1,x_2,x_3≥0

We like to solve this problem by hand calculation and computer programming. 

Solution: (Analytic solution)

We are now given  Minimize,    Z=x_1-3x_2+2x_3

Subject to the constraints -

〖3x〗_1-x_2+2x_3≤7

〖-2x〗_1+4x_2≤12

-4x_1+3x_2+8x_3≤10           

x_1,x_2,x_3≥0

The given minimization problem can be written as

Maximize Z= -Z=-x_1+3x_2-2x_3

Introducing the unbound variabless_1,s_2,s_3≥0 to the constraints we get the L.P.P. as to

Maximize,〖 Z〗^=-x_1+3x_2-2x_3+0.s_1+0.s_2+〖0.s〗_3

Subject to,    〖3x〗_1-x_2+2x_3+s_1=7

〖-2x〗_1+〖4x〗_2+0.x_3+s_2=12

-4x_1+3x_2+8x_3+s_3=10                     

wherex_1,x_2,x_3,s_1,s_2,s_3≥0     

Construct the 1st simplex Table as Table 3.

Table 3: Since C_j-E_j is non negative under x_2 co-lumn, Table 1 is not optimal. In Table 1 x_2 is in-coming variable,〖 s〗_2 is outgoing variable and (4) is the prime element.

In Table 3 s_2 is restore by x_2 in the basis

Table 4: Since C_j-E_j is positive under x_1 column, second general feasible solution is not classical or optimal. 

In Table 3 s_1 is restored byx_1.

Table 5: Since  C_j-E_j is either negative or zero under all variables, Table 3 is optimal.

The optimal general feasible solution is -    

x_1=4〖,x〗_2=5,〖 x〗_3=0

Z^=-4+3×5-2×0=11 

or〖 Z〗_min=-11                                                    

Computer solution of the problem by using FOR-TRAN program.

Input of the problem:

############ LINEAR 

PROGRAMING ############

        ************* SIMPLEX METHOD ************

Maximize or Minimize? [MAX=1,MIN=2]..:  2

Number of non-basic variables: 3 

Number of <= inequalities..:  3

Number of >= inequalities..: 0 

Number of = equalities.....: 0 

Input Economic Function: 

Coefficient # 1:  1

Coefficient # 2:  -3

Coefficient # 3:  2

Constant term..:  0

Input constraint # 1:

Coefficient # 1:  3

Coefficient # 2:  -1

Coefficient # 3:  2

Constant term..:  7

Input constraint # 2:

Coefficient # 1:  -2

Coefficient # 2:  4

Coefficient # 3:  0

Constant term..:  12

Input constraint # 3:

Coefficient # 1:  -4

Coefficient # 2:  3

Coefficient # 3:  8

Constant term..: 10

Output of the problem

Input Table:

0.0000000E+00   1.000000      -3.000000       2.000000    

7.000000                 3.000000      -1.000000       2.000000    

12.00000            -2.000000       4.000000           0.0000000E+00

10.00000            -4.000000       3.000000           8.000000    

Minimum of Objective Function =   -11.00000    

X 1 =     4.000000

X 2 =     5.000000

X 3 =     0.000000

We concluded that the analytical solution and com-puter solution are same so our program is right for any LPPs. Now we formulate two large size real-life LPPs which are very difficult to calculate by analytical process. But by using computer programming we can solve that problem very easily.  

Problem (Bank Loan Policy)

From the problem 2.2 which is formulated in the previous chapter now we solve this by using FOR-TRAN program.

Solution  

The targeted function is given as

 Maximize Z=.026x_1+.0509x_2+.0864x_3+.06875x_4+.078x_5

Subject to     x_1+x_2+x_3+x_4+x_5≤12

x_4+x_5≥4.8

.5x_1+.5x_2-.5x_3≤0       

.06x_1+.03x_2-.01x_3+.01x_4-.02x_5≤0         

where,x_1≥0,x_2≥0,x_3≥0,x_4≥0,x_5≥0     

############ LINEAR PROGRAMING ####

  ************* SIMPLEX METHOD ************

Maximize or Minimize? [MAX=1,MIN=2]..:  1

Number of non-basic variables:  5

Number of <= inequalities..:  3

Number of >= inequalities..:  1

Number of = equalities.....:  0

Input Economic Function: 

Coefficient # 1: .026 

Coefficient # 2:  .0509

Coefficient # 3:  .0864

Coefficient # 4:  .06875

Coefficient # 5:  .078

Constant term..:  0

Input constraint # 1:

Coefficient # 1:  1

Coefficient # 2:  1

Coefficient # 3:  1

Coefficient # 4:  1

Coefficient # 5:  1

Constant term..:  12 

Input constraint # 2:

Coefficient # 1:  0

Coefficient # 2:  0

Coefficient # 3:  0

Coefficient # 4:  1

Coefficient # 5:  1

Constant term..:  4.8

Input constraint # 3:

Coefficient # 1:  .5

Coefficient # 2:  .5

Coefficient # 3:  -.5

Coefficient # 4:  0

Coefficient # 5:  0

Constant term..:  0

Input constraint # 4:

Coefficient # 1:  .06

Coefficient # 2:  .03

Coefficient # 3:  -.01

Coefficient # 4:  .01

Coefficient # 5:  -.02

Constant term..: 0

Output of the problem

Input Table:

0.0000000E+00  2.6000001E-02  5.0900001E-02  8.6400002E-02  

6.8750001E-02     7.8000002E-02

12.00000       1.000000       1.000000       

1.000000       1.000000    

1.000000    

4.800000      0.0000000E+00  0.0000000E+00  0.0000000E+00   1.000000    

1.000000    

0.0000000E+00  0.5000000      0.5000000     -0.5000000      0.0000000E+00

0.0000000E+00

0.0000000E+00  5.9999999E-02  2.9999999E-02 -9.9999998E-03  

9.9999998E-03 -2.0000000E-02

Maximum of Objective Function =   0.9332572    

X 1 =     1.714287

X 2 =     0.000000

X 3 =    10.285713

X 4 =     0.000000

X 5 =     0.000000

Problem (Car Scheduling Problem)

Progressing City is studying the feasibility of intro-ducing a mass transit car system that will alleviate the smog problem by reducing in city driving. In this study find the resolve of the lowest number of cars that could handle the transportation needs. After taking some necessary information, the town engineers observed that the lowest number of cars needed vary with the time of the day and that the recommended number of cars could be approximated by constant values over successive 4-hour intervals. In the figure summarizes the engineers finding. To carry through the recom-mended daily maintenance, each car can operate only 8 successive hours a day.

Mathematical Representation

Establish the number of operating cars in every switch that will meet the lowest demand while minimizing the all number of cars in operation. You may already have observed that the contrast of the variables is unfixed. We know that every car will run for 8 hours, but we dont know when a switch should start. If we follow a basic 3(three) switch schedule (8:01A.M to 4:00 P.M., 4:01P.M. to 12.00 midnight, and 12.01A.M.to 8:00 A.M.) and take that x_1,x_2 and x_3 are the number of cars starting in the 1st, 2nd and 3rd shifts, we can notice from the top of figure that x_1≥10,x_2≥12 and x_3≥8. The corresponding lowest number of every day cars is x_1+x_2 x_3=10+12+8=30. The given solution is accepted, if the switch should be coincide with the normal 3(three) switch schedule. It can be beneficial, moreover, to allow the optimization process to choose the top beginning time for a switch, a reasonable way to accomplish this is allow a switch to begin every 4 hours. The foot of figure illustrates this idea where overlapping switch can start at 12.01am, 4.01am, 8.01am, 12.01 pm, 4.01 pm and 8.01 pm with every switch spanning 8 successive hours.

Thus, the variables can be defined as –

x_1= number of cars starting at 12.01 A.M.

x_2= number of cars starting at 4.01 A.M.

x_3= number of cars starting at 8.01 A.M.

x_4= number of cars starting at 12.01 P.M.

x_5= number of cars starting at 4.01 P.M.

x_6= number of cars starting at 8.01 P.M.

The mathematical model is written as -

Minimize

 z=x_1+x_2+x_3+x_4+x_5+x_6

Subject to x_1+x_6≥4 (12.01 A.M.-4.00 A.M.)

x_1+x_2≥8(4.01 A.M.-8.01 A.M.)

x_2+x_3≥10(8.01 A.M-12.00 noon)

x_3+x_4≥7(12.01 P.M.-4.01 P.M.)

x_4+x_5≥12(4.01 P.M.-8.00P.M.)

x_5+x_6≥4(8.01 P.M.-12.00P.M.)

x_j≥0,j=1,2,……6    

Computer solution of the problem by using FOR-TRAN program.

Input of the problem

############ LINEAR 

PROGRAMING ############

************* SIMPLEX METHOD ************

Maximize or Minimize? [MAX=1,MIN=2]..:  2

Number of non-basic variables:  6

Number of <= inequalities..:  0

Number of >= inequalities..:  6

Number of = equalities.....:  0

Input Economic Function: 

Coefficient # 1:  1

Coefficient # 2:  1

Coefficient # 3:  1

Coefficient # 4:  1

Coefficient # 5:  1

Coefficient # 6:  1

Constant term..:0

Input constraint # 1:  

Coefficient # 1:  1

Coefficient # 2:  0

Coefficient # 3:  0

Coefficient # 4:  0

Coefficient # 5:  0

Coefficient # 6:  1

Constant term..:  4

Input constraint # 2:

Coefficient # 1:  1

Coefficient # 2:  1

Coefficient # 3:  0

Coefficient # 4:  0

Coefficient # 5:  0

Coefficient # 6:  0

Constant term..:  8

Input constraint # 3:

Coefficient # 1:  0

Coefficient # 2:  1

Coefficient # 3:  1

Coefficient # 4:  0

Coefficient # 5:  0

Coefficient # 6:  0

Constant term..:  10

Input constraint # 4:

Coefficient # 1:  0

Coefficient # 2:  0

Coefficient # 3:  1

Coefficient # 4:  1

Coefficient # 5:  0

Coefficient # 6:  0

Constant term..:  7

Input constraint # 5:

Coefficient # 1:  0

Coefficient # 2:  0

Coefficient # 3:  0

Coefficient # 4:  1

Coefficient # 5:  1

Coefficient # 6:  0

Constant term..:  12

Input constraint # 6:

Coefficient # 1:  0

Coefficient # 2:  0

Coefficient # 3:  0

Coefficient # 4:  0

Coefficient # 5:  1

Coefficient # 6:  1

Constant term..: 4

Output of the problem:

Input Table:

0.0000000E+00   1.000000       1.000000       1.000000   

1.000000    

1.000000       1.000000    

4.000000       1.000000      0.0000000E+00  0.0000000E+00  0.0000000E+00

0.0000000E+00   1.000000    

8.000000       1.000000       1.000000      0.0000000E+00  0.0000000E+00

0.0000000E+00  0.0000000E+00

10.00000      0.0000000E+00   1.000000       1.000000      0.0000000E+00

0.0000000E+00  0.0000000E+00

7.000000      0.0000000E+00  0.0000000E+00   1.000000       1.000000    

0.0000000E+00  0.0000000E+00

12.00000      0.0000000E+00  0.0000000E+00  0.0000000E+00   1.000000    

1.000000      0.0000000E+00

4.000000   0.0000000E+00  0.0000000E+00  0.0000000E+00  0.0000000E+00

1.000000       1.000000    

Minimum of Objective Function = 26.00000    

X 1 =     4.000000

X 2 =    10.000000

X 3 =     0.000000

X 4 =     8.000000

X 5 =     4.000000

X 6 =     0.000000

A Real Life Problem of Transportation Problem and Its Solution 

Transportation Problem

One of the advance and most practical applications of LP techniques has been solution and the formulation of the transportation problem. The mathematical formu-lation of this problem gives us an LPP which in revolve can be solved by the simplex system, revised system or dual simplex system but the special structure of the measure matrix is such that more efficient methods can be used to solve these problems easily. We shall discuss here the Vogels approximation method and the North-West Corner rule to solve such problems. For some other methods like stepping stone algorithm the students can consult Hadley, (1962) and Rao, (2005). The basic transportation problem was originally stated by Hitchcock, (1941) and later dis-cussed in detail by Kopman, (1949). An earlier ap-proach was provided Kantorovich, (1958). The linear programming formulation and the associated syste-matic method for solution were first given in Danzig, (1951)

Formulation of General Transportation Problem

A homogeneous product available at a fixed number of origins is to be transported to a fixed number of desti-nations. All of amount available at every of these origins is known and also the all quantity needed at every destination is known. The unit transportation value from every origin to each destination is given. The question thens to determine the quantum of the products to be transported from these origins to be destinations so, as to minimize the total transportation cost. Ifmis the number of root or origin and nis the number of goal or destinations the value of trans-porting 1 unit of the commodity from rooti to goaljis c_ij. If a_i be the quantity of the commodity available at rooti and b_j be the quantity required at destination j. Thus a_j≥0 for i and b_j≥0 for each j. If x_ij is the quantity transported from origin i to destination j we write the general formulation of the transportation problem as 

Minimize Z=∑_(i=1)^m▒∑_(j=1)^n▒〖c_ij x_ij 〗

Subject to∑_(j=1)^n▒〖x_ij=a_i 〗,i=1,2,…………m

∑_(i=1)^n▒〖x_ij=b_i 〗,i=1,2,…………n

x_ij≥0.                                                     

The above represents a LPP with mn variables and m+n constraints. To see the unique structure of the co-efficient matrix here we take a special case for m=2 and n=3. The mnvariables from a vector X=(x_11,x_12,x_13,x_21,x_22,x_23 )^T. 

The vector b=(a_1,a_2,b_1,b_2,b_3 )^T, and

C=(c_11,c_12,c_13,c_21,c_22,c_23 ). Then the transportation problem may be written as

Min Z=CX

Subject to AX=b

X≥0.

Where A is a 5×6 matrix. The exact form of A is -

Note that, each column of the matrix A contains 1 exactly in two places. For the basic transportation pro-blem the order of matrix A will be (m+n)×(mn), that of the column vector X will be (mn)×1, that of the column vector b will be (m+n)×1 and of the row vector C will be 1×(mn).

Unbalanced Transportation Problem

A transportation problem is claimed to be balanced if

∑_(i=1)^m▒a_i =∑_(j=1)^n▒〖b_j.〗

Else, its said to be unbalanced. Suppose,

∑_(i=1)^m▒a_i >∑_(j=1)^n▒〖b_j.〗

Then a fictitious destination is considered with re-quirement

∑_(i=1)^m▒a_i -∑_(j=1)^n▒〖b_j.〗

The unit cost of transportation to this destination from all the m origins may be taken as zero. On the con-trary, suppose

∑_(i=1)^m▒a_i <∑_(j=1)^n▒〖b_j.〗

Then a fictitious origin can be taken with available quantity -

∑_(i=1)^m▒b_j -∑_(j=1)^n▒〖a_i.〗

The unit cost of transportation from this factious root to all the n goal will be as 0 (zero). This way an un-stable problem can be stable.

Finding Initial general Feasible Solution

The general transportation problem should be repre-sented in a table form -

This Table has mn cells. 

The North-West Rule

Following steps are involved in this method:

Step 1

Make the first assignment to the upper-left hand cell which is called North-West Corner. Take x_11=〖min 〗⁡〖(a_1,b_1)〗

Step 2

If x_11=a_1, then row I can be deleted. If〖 x〗_11=b_1, then column I can be deleted. In the first case replace b_1 by b_1-a_1 and in the second case replace a_1 by a_1-b_1

Step 3

If a_1=b_1, then x_11=a_1=b_1 and row I as well as column I will be deleted. The gives anindication that a degenerate basic feasible solution will be obtained, that is, not more than m+n-1 positive basic variables will be obtained.

Step 4

A new matrix of order (m-1)×n,ormx(n-1)or(m-1)×(n-1) will appear. This are called the reduce matrices. Repeat steps 1-3 till all of the quantities are wasted. This is likely or possible as it is a balanced problem.

The Vogels approximation system

Vogels Approximation system is a heuristic method and is preferred to the methods describe above. In the transportation matrix if an allocation is made in the alternate smallest cost cell rather of the smallest, also this allocation will have associated with it a penalty corresponding to the difference of these two costs due to loss of advantage. That is to say, if we cipher the difference between the two smallest costs for each row and column, we find the occasion cost applicable to each row and column. It would be most provident to make allocation against the row or column with the loftiest occasion cost. For a given row or column, the allocation should obviously be made in the list cost cell of that row or column. Vogels approximation method there for, makes effective use of the cost information and yields a better initial solution then obtained by the other method. 

Some real life problem of LPP

Some practical problem is given bellow.

Problem 

A transportation problem for maximum profits is that

We want to solve this problem by hand calculation.

Solution: (Analytic solution)

By using North-West Corner rule we solved this pro-blem, which given bellow:

Its a balanced transportation problem. Here m+n-1=3+4-1=6. We get the required degenerate general feasible solution as -

=12×180+18×20+7×300+10×100+18×100+20×300

=2160+360+2100+1000+1800+6000

=13420                                            

Problem

A dairy establishment has three shops located throu-ghout a state. Every milk production at each factory is as follows –

Factory 1..........6 million liters,

Factory 2...........1 million liters, and

Factory 3...........10 million liters.

Every day the establishment must fulfill the require-ments of its four Delivery points. Minimum demand at each point is as follows –

Delivery point 1.............7 million liters,

Delivery point 2.............5 million liters,

Delivery point 3.............3 million liters, and

Delivery point 4.............2 million liters.

Cost of dispatching one million liters of milk from each factory to each Delivery point is given in the following -

Solution: (Analytic solution)

By using Vogels approximation method we solved this problem, which is given bellow:

Step 1: Write down the cost matrix.

Enter the difference between the lowest and second lowest elements in each column below the corres-ponding column and the difference between the lowest and second lowest elements in each row to the write of the row put these numbers in brackets as shown. For example, in column 1, the two lowest elements are 1 and 2 and there difference is 1 which is entered (1) below column 1. Similarly, the 2 smallest elements in row 2 are 0 and 1 and their difference 1 is entered as (1) to the right of row 2. A row or column difference indicates the unite plenitude incurred falling to make an allocation to the smallest cost cell in that row or column

Step 2: Select the row or column with the highest difference and allocate as much as possible with in the restrictions of the rim conditions to the smallest cost cell in the row or column selected. In case a tie occurs, assign to the cell related with the smallest cost. Thus since (6) is the largest number in brackets, we choose column 4 and allocate as much as possible to the cell (2, 4) as it has the lowest cost 1 in column 4. Since supply is 1 while the requirement is 2, highest possible allocation is (1).

Step 3: Cross out the row or column fully satisfied by the allocation just made. For the assignment just made at (2, 4), supply of plant 2 is completely satisfied. So row 2 is crossed out and the shrunken matrix is written below.

 This matrix involve of the columns and row where allotment have not been yet made, together with revised column and row summation, which consider the formerly made allocation.

Step 4: Reprise way 1 to 3 until all assignments have been made (a) column 2 exhibits the top most differ-ence of (5). Therefore, we allocate (5) units to cell (1,2), since it has the smallest transportation cost in column 2. Since condition of column 2 are fully satisfied, this column is cross out and the reduced matrix is written.

(b) Difference is recalculated. The maximum dif-ference is (5).Therefore, we allocate (1) to the cell (1, 1) since it has the lowest cost in row 1. Since re-quirements of row 1 are fully satisfied, it is crossed out and the reduced matrix is written below.

 (c) As cell (3, 1) has the smallest cost 5, maximum possible allocation of (6) is made then. Likewise, coming allocation of (1) is made in cell (3, 4) and (3) in cell (3, 3) as shown.

The price of transportation associated with the bellow result is -

Z ꞊ Tk. (2×1+3×5+1×1+5×6+15×3+9×1)×100

=Tk. 10200

Let us represent the example graphically

CONCLUSION

In this paper, we have formulated mathematical programming model of sizeable real life problem and we solved these problems with Mathematica and FOR-TRAN code. First of all we formulate some real life linear programming problems and solved it graphically by using mathematica. There are some large scale real life problems which cannot be solved graphically but we solved this problem by using simplex technique. We solved some problem by hand calculation and again those problem is solved by FORTRAN program. We see that the result is same. Small problems can be solved with the help of pencil and paper but a large scale real life problem is very difficult to solve by hand calculation. So we can solve this problem easily by using FORTRAN program. Here we formulate two large scale linear programming problems which are solved by using FORTRAN program. On the same way we describe one of the earliest and most useful applications of linear programming techniques has been the formulation and solution of the transportation problem. Computer program is a mighty method for large scale optimization problem, where it can be applied for this we have to model the problem and computer based solution procedure saves our time and labor. Thus the optimization method of linear programming will be useful to the society, business, industries and government if one can formulate the linear programming model of it and required computer program can be developed and used to solve the problem.

ACKNOWLEDGEMENT

I would like to express My Teacher and thanks to my friends for their support and advice in completing this paper successfully.

CONFLICTS OF INTEREST

This research is contributed by all authors and no potential conflict of interest to publish it.

Article References:

  1. Ali, S.M.E. (2001). A Text Book of Program-ming in FORTRAN, Beauty Publications, Khulna. http://www.ajer.org/papers/v4(07)/4-7.pdf 
  2. Dantzing, G. B. (1951). Application of the Simplex Method of Transportation Problems, Cowles commission Monograph 13, Wiley New York. https://cowles.yale.edu/sites/default/files/files/pub/mon/m13-all.pdf 
  3. Don, E. (2004). Schaums outline of Theory and Problems of Mathematica, Tata McGraw-Hill Publishing Company Ltd, New Delhi.
  4. Gupta, P.K. and Hira, D.S. (2010). Operations Research, S. Chand & Company Ltd. Publishers, New Delhi.https://content.kopykitab.com/ebooks/2016/07/8067/sample/sample_8067.pdf 
  5. Grewal, B.S. (1998). Higher Engineering Mat-hematics, Thirty Fourth Edition, Khanna Publi-cation, Delhi. https://www.academia.edu/38267463/Higher_engineering_mathematics_bs_grewal 
  6. Gupta, P. K., Molin, M. (2001). Linear Pro-gramming and Theory of games, Thoroughly Revised Edition, Sultan Chand & Sons Educa-tional Publishers, New Delhi
  7. Gupta, R.K. (2006). Krishnas Linear Program-ming, Twentieth Edition, Krishna Prakashan Media (P) Ltd. Delhi.
  8. Hadely, G. (1962). Linear Programming, Addi-sion Wesley, Reading Massachusetts. https://www.worldcat.org/oclc/1176260260 
  9. Hitchcock, F.L. (1941). The Distribution of a Product from several sources to numerals loca-tions, Journal of Mathematical Physics. 20(1-4); 224-230 https://onlinelibrary.wiley.com/doi/10.1002/sapm1941201224 
  10. Kambo, N. S. (1991). Mathematical Program-ming Techniques Affiliated East-West Press, New Delhi.
  11. Kantorovich, L.V. (1942). On the translocations of masses, Doklady Akad, NaukSSr. http://www.math.toronto.edu/mccann/assignments/477/Kantorovich42.pdf 
  12. Koopmans, T.C. (1949). Optimum Utilization of the Transportation systems, Econometrica. https://www.jstor.org/stable/1907301 
  13. Lipschutz, S., Poe, A. (2002). Schaums outline of Theory and Problems of Programming with FORTRAN, McGraw-Hill lnc, New York. https://inc.kmutt.ac.th/inc161/schaum.pdf 
  14. Loomba, N.P. (1971). Linear Programming, TMH Edition, Tata McGraw-Hill Publishing Company Ltd, New Delhi. https://www.worldcat.org/title/linear-programming/oclc/502215637?referer=di&ht=edition  
  15. Niazai S, Rahimzai AA, Danesh M, and Safi B. (2022). Numerical solution of diffusion equation with caputo time fractional derivatives using fi-nite-difference method with Neumann and Robin boundary conditions, Int. J. Mat. Math. Sci., 4(1), 01-14. https://doi.org/10.34104/ijmms.022.010014 
  16. Rao, K.C., Mishra, S.L. (2005). Operations Research, Narosa Publishing House Pvt. Ltd, New Delhi. https://www.bbau.ac.in/dept/UIET/EME-601%20Operation%20Research.pdf  
  17. Reddy, R.N., Ziegler, C. (1990). FORTRAN77 with Applications for Scientists and Engineers, Jaico Publishing House. https://www.amazon.com/Fortran-77-Applications-Scientists-Engineers/dp/0314028617 
  18. Sami HM, Fardous L, and Ruhit DS. (2021). Portfolio optimization in DSE using financial in-dicators, LSTM & PyportfolioOpt, Int. J. Mat. Math. Sci., 3(4), 74-84. https://doi.org/10.34104/ijmms.021.074084 
  19. Taha, A.H. (2003). Operations Research An Introduction, Seventh Edition, Prentice-Hall of India, Private Limited, New Delhi. http://zalamsyah.staff.unja.ac.id/wp-content/uploads/sites/286/2019/11/9-Operations-Research-An-Introduction-10th-Ed.-Hamdy-A-Taha.pdf   

Article Info:

Academic Editor

Dr. Toansakul Tony Santiboon, Professor, Curtin University of Technology, Bentley, Australia.

Received

January 18, 2022

Accepted

February 21, 2022

Published

February 28, 2022

Article DOI: 10.34104/ijmms.022.015034

Corresponding author

Shohal Hossain*

Center for Multidisciplinary Research, Gono Bishwabidyalay, Savar, Dhaka-1344, Bangladesh

Cite this article

Hossain S, Aktar S, and Mithy SA. (2022). Solution of large-scale linear programming problem by using computer technique, Int. J. Mat. Math. Sci., 4(1), 15-34. https://doi.org/10.34104/ijmms.022.015034 

Views
288
Download
940
Citations
Badge Img
Share