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.
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 –
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
I would like to express My Teacher and thanks to my friends for their support and advice in completing this paper successfully.
This research is contributed by all authors and no potential conflict of interest to publish it.
Academic Editor
Dr. Toansakul Tony Santiboon, Professor, Curtin University of Technology, Bentley, Australia.
Center for Multidisciplinary Research, Gono Bishwabidyalay, Savar, Dhaka-1344, Bangladesh
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