CU-BBA-SEM-V-Operation Research-Second Draft

X2 = Amount invested in Security B Objective Function The objective is to maximise the return on total investment. ⸫ Max Z = 0.09 X1 + 0.015 X2 ((% = 0.09, 15% = 0.15) Constraints 1. Related to Total Investment: X1 + X2 = 5, 00, 000 2. Related to Risk: 5X1 + 8X2 = (6 X 5, 00, 000) 5X1 + 8X2 = 30, 00, 000 3. Related to Returns: 0.09X1 + 0.15X2 = (0.12 X 5, 00, 000) ⸫0.09X1 + 0.15X2 = 60, 000 4. Non-negativity X1, X2 ≥ 0 Example 5: Inspection Problem A company has two grades of inspectors, I and II to undertake quality control inspection. At least 1, 500 pieces must be inspected in an 8-hour day. Grade I inspectors can check 20 pieces in an hour with an accuracy of 96%. Grade II inspector checks 14 pieces an hour with an accuracy of 92%. Wages of grade I inspector are Rs. 5 per hour while those of grade II inspector are Rs. 4 per hour. Any error made by an inspector costs Rs. 3 to the company. If there are, in all, 10 grade I inspectors and 15 grade II inspectors in the company, find the optimal assignment of inspectors that minimise the daily inspection cost. Solution Let x1 and x2 denote the number of grade I and grade II inspectors that may be assigned the job of quality control inspection. The objective is to minimise the daily cost of inspection. Now the company has to incur two types of costs; wages paid to the inspectors and the cost of their inspection errors. The cost of a grade I inspector/hour is Rs. (5 + 3 X 0.04 X 20) = Rs. 7.40. Similarly, the cost of a grade II inspector/hour is Rs. (4 + 3 X 0.08 X 14) = Rs. 7.36. ⸫ The objective function is minimised Z = 8(7.40x1 + 7.36x2) = 59.20 x1 + 58.88x2. 51 CU IDOL SELF LEARNING MATERIAL (SLM)

Constraints are on the number of grade I inspectors: x1 ≤ 10, on the number of grade II inspectors: x2 ≤ 15 on the number of pieces to be inspected daily: 20 x 8x1 + 14 x 8x2 ≥ 1500 or 160x1 + 112x2 ≥ 1500 where, x1, x2 ≥ 0. Example 6: Trim Loss Problem A manufacturer of cylindrical containers receives tin sheets in widths of 30 cm and 60 cm respectively. For these containers the sheets are to be cut to three different widths of 15 cm, 21 cm and 27 cm respectively. The number of containers to be manufactured from these three widths are 400, 200 and 300 respectively. The bottom plates and top covers of the containers are purchased directly from the market. There is no limit on the lengths of standard tin sheets. Formulate the LPP for the production schedule that minimises the trim losses. Solution Key decision is to determine how each of the two standard widths of tin sheets be cut to the required widths so that trim losses are minimum. From the available widths of 30 cm and 60 cm, several combinations of the three required widths of 15 cm, 21 cm and 27 cm are possible. Let xij represent these combinations. Each combination results in certain trim loss. Constraints can be formulated as follows: The possible cutting combinations (plans) for both types of sheets are shown in the table below: Table 3.4: The possible cutting combinations (plans) for both types of sheets Thus, the constraints are: 2x11 + 4x21 + 2x22 + 2x23 + x24 ≥ 400 x12 + x22 + 2x24 + x25 ≥ 200 x13 +x23 + x25 + x26 ≥ 300 Objective is to maximise the trim losses. i.e., minimise Z = 9x12 + 3x13 + 9x22 + 3x23 + 3x24 + 12x25 + 6x26 where x11, x12, x13, x21, x22, x23, x24, x25, x26 ≥ 0. Example 7: Media Selection An advertising agency is planning to launch an ad campaign. Media under consideration are T.V., Radio & Newspaper. Each medium has different reach potential and different cost. 52 CU IDOL SELF LEARNING MATERIAL (SLM)

Minimum 10, 000, 000 households are to be reached through T.V. Expenditure on newspapers should not be more than Rs. 10, 00, 000. Total advertising budget is Rs. 20 million. Following data is available: Medium Cost Per Unit (Rs.) Reach Per Unit (No. of Households) Television 2,00,000 20,00,000 Radio 80,000 10,00,000 Newspaper 40,000 2,00,000 Table 3.5: Advertising budget data Solution Decision Variables: x1 = Number of units of T.V. ads, x2 = Number of units of Radio ads x3 = Number of units of Newspaper ads. Objective function: (Maximise reach) Max. Z = 20, 00, 000 x1 + 10, 00, 000 x2 + 2, 00, 000x3 Subject to constraints: 20, 00, 000 x1 ≥ 10, 000, 000 ........ (For T.V.) 40, 000 x3 ≤ 10, 00, 000 ........... (For Newspaper) 2, 00, 000x1 + 80, 000x2 + 40, 000x3 ≤ 20, 000, 000 .......... (Ad. budget) x1, x2, x3 ≥ 0 ⸫ Simplifying constraints: for T.V. 2 x1 ≥ 10 ⸫ x1 ≥ 5 for Newspaper 4 x3 ≤ 100 ⸫ x3 ≤ 25 53 CU IDOL SELF LEARNING MATERIAL (SLM)

Ad. Budget 20 x1 + 8 x2 + 4 x3 ≤ 2000 5 x1 + 2x2 + x3 ≤ 500 x1, x2, x3 ≥ 0 Example 8: Diet Problem Vitamins B1 and B2 are found in two foods F1 and F2. 1 unit of F1 contains 3 units of B1 and 4 units of B2. 1 unit of F2 contains 5 units of B1 and 3 units of B2 respectively. Minimum daily prescribed consumption of B1 & B2 is 50 and 60 units respectively. Cost per unit of F1 & F2 is Rs. 6 & Rs. 3 respectively. Formulated as LPP. Solution Table 3.6: Vitamins, Foods and Minimum Consumption Decision Variables: x1 = No. of units of P1 per day. x2 = No. of units of P2 per day. Objective function: Min. Z = 100 x1 + 150 x2 Subject to constraints: 3x1+ 5x2 ≥ 30 (for N1) 5x1+ 7x2 ≥ 40 (for N2) x1, x2 ≥ 0 Example 9: Blending Problem A manager at an oil company wants to find an optimal mix of two blending processes. Formulate LPP. Data Table 3.7: Process, Input and Output 54 Profit per operation: Process 1 (P1) = Rs. 4, 000 CU IDOL SELF LEARNING MATERIAL (SLM)

Process 2 (P2) = Rs. 5, 000 Maximum availability of crude oil: Grade A = 500 units Grade B = 400 units Minimum Demand for Gasoline: X = 300 units Y = 200 units Solution Decision Variables: x1 = No. of operations of P1 x2 = No. of operations of P2 Objective Function: Max. Z = 4000 x1 + 5000 x2 Subjective to constraints: 6x1+ 5x2 ≤ 500 4x1+ 6x2 ≤ 400 6x1+ 5x2 ≥300 9x1+ 5x2 ≥200 x1, x2 ≥ 0 Example 10: Farm Planning A farmer has 200 acres of land. He produces three products X, Y & Z. Average yield per acre for X, Y & Z is 4000, 6000 and 2000 kg. Selling price of X, Y & Z is Rs. 2, 1.5 & 4 per kg respectively. Each product needs fertilizers. Cost of fertilizer is Rs. 1 per kg. Per acre need for fertilizer for X, Y & Z is 200, 200 & 100 kg respectively. A labour requirement for X, Y & Z is 10, 12 & 10 man hours per acre. Cost of labour is Rs. 40 per man hour. Maximum availability of labour is 20, 000 man hours. Formulate as LPP to maximise profit. Solution Decision variables: The production/yield of three products X, Y & Z is given as per acre. Hence, x1 = No. of acres allocated to X x2 = No. of acres allocated to Y x3 = No. of acres allocated to Z Objective Function: Profit = Revenue - Cost 55 CU IDOL SELF LEARNING MATERIAL (SLM)

Profit = Revenue - (Fertiliser Cost + Labour Cost) Product X Y Z Revenue 2 (400)x1 1.5 (600)x2 4 (200)x3 (-) Less: Fertiliser Cost 1 (200)x1 1(200)x2 1(100)x3 Labour Cost 40 (10)x1 40 (12)x2 40 (10)x3 Profit 7400x1 8320x2 7500x3 Table 3.8: Product, Revenue, Cost and Profit ⸫ Objective function Max. = 7400 x1 + 8320 x2 + 7500 x3 Subject to constraints: x1 + x2 + x3 = 200 (Total Land) 10 x1 + 12 x2 + 10 x3 ≤ 20, 000 (Max Man hours) x1, x2, x3 ≥ 0 Merits of LPP 1. Helps management to make efficient use of resources. 2. Provides quality in decision making. 3. Excellent tools for adjusting to meet changing demands. 4. Fast determination of the solution if a computer is used. 5. Provides a natural sensitivity analysis. 6. Finds solutions to problems with a very large or infinite number of possible solutions. 3.2.1 Types of Constraints 56 CU IDOL SELF LEARNING MATERIAL (SLM)

Possible constraint types include resource limitations, minimum requirements, supply- demand balances, ratio controls, upper/lower bounds, accounting relations, deviation constraints, and approximation or convexity constraints. Resource Limitations Resource limitations depict relationships between endogenous resource usage and exogenous resource endowments. A resource limitation restricts endogenous resource use to be less than or equal to an exogenous resource endowment. An example of a resource limitation constraint is 3X1 + 4X2 ≤7 This constraint requires the sum of resources used in producing X1, which uses 3 resource units per unit, plus those used in producing X2, which uses 4 resource units per unit, to be no greater than an exogenous resource endowment of 7 units. Resource usage depends on the values of X1 and X2 determined by the model and thus is an endogenous quantity. Minimum Requirements Minimum requirement constraints require an endogenously determined quantity to be greater than or equal to an exogenously specified value. A simple illustration is X1 + 2X2 ≥ 4 In this case the endogenous sum of X1 plus two times X2 is constrained to be greater than or equal to the exogenously imposed requirement of four. One may also express this constraint in less-than-or-equal-to form as X1 2X2 ≤ -4 The minimum requirement often specifies that the model must meet exogenous demand through the endogenous supply of goods. This kind of constraint is present in many different types of programming models. Supply and Demand Balance The supply-demand balance requires that endogenous supply be balanced with endogenous demand. A typical example is X1≤ X2. This equation requires the endogenous demand for a good (X1) to be less than or equal to the endogenous supply of that good (X2). After moving all the variables to the left hand side, the constraint becomes X1- X2 ≤ 0. More generally, supply demand balances may involve exogenous quantities. Consider the inequality 2X1- X2 ≤ 3. Here, the difference between endogenous demand (2X1) and supply (X2) is less than or equal to an exogenous supply of 3 units. This inequality can also be expressed in the following form: 2X1≤ X2 + 3 57 CU IDOL SELF LEARNING MATERIAL (SLM)

which says that the endogenous demand (2X1) must be less than or equal to total supply, which consists of endogenous supply (X2) plus exogenous supply (3). A related situation occurs under the constraint X1- 4X2 ≤ -2 Here, the difference between endogenous supply and endogenous demand is less than or equal to minus 2. This can be rewritten as X1 + 2 ≤ 4X2 which states that endogenous demand (X1) plus exogenous demand (2) is less than or equal to endogenous supply (4X2). In general, supply-demand balances are used to relate endogenous supply and demand. The general case is given by DemandEn + DemandEx≤ Supply En + SupplyEx. Here, the sum of demand over endogenous and exogenous sources (respectively denoted by the subscripts En and Ex) must be less than or equal to the supply from endogenous and exogenous sources. Manipulating the endogenous variables to the left hand side and the exogenous items to the right hand side gives DemandEn - SupplyEnSupplyEx - DemandEx. Here endogenous demand minus endogenous supply is less than or equal to exogenous supply minus exogenous demand. This constraint contains the resource limitation and minimum requirement constraints as special cases. The resource limitation constraint exhibits zero endogenous supply and exogenous demand. The minimum requirement constraint exhibits zero endogenous demand and exogenous supply. Ratio Control Ratio control constraints require the ratio of certain endogenous variables to be no more than an endogenous sum, possibly influenced by exogenous factors. Specifically, suppose that a number of units of X1 have to be supplied with every unit of X2. For example, a LP formulation of an automobile manufacturer might require a constraint to ensure that there are four tires for every car sold. Such a situation would be modelled by 4X2 - X1 ≤ 0 where X1 is the number of tires and X2 the number of cars sold. In order for one unit of X2 to be sold, 4 units of X1 must be supplied. The general case is depicted by ENrat≤ p (wENENrat + ENother + EXother). where the left-hand side elements are denoted with the subscript \"rat,\" and the right-hand side elements with \"other.\" EN denotes endogenous variables and EX denotes exogenous 58 CU IDOL SELF LEARNING MATERIAL (SLM)

constants. The parameter wEN is nonzero only when the endogenous variables (ENrat) are part of the right hand side. The constraint requires that the endogenous \"rat\" expression be less than or equal to p times the sum of the \"rat\" term or variables plus the \"other.\" Manipulating this constraint so that all the endogenous variables are on the left hand side gives (1 - pwEN) ENrat - p ENother≤ pEXother This expression is rather abstract and is perhaps best seen by the example. Suppose we wish the variable X1 to be no more than 25 percent of X1 + X2. Thus X ≤ 25 (X1 + X2) Placing all the endogenous variables on the left hand side yields .75X1- .25X2 ≤ 0 Consider another example which includes exogenous factors. Suppose that (X1 + 3) ≤.25 (2X1 + 3X2 + 10). This can be written as .50X1 - .75X2 ≤ .5 Here we have a requirement between X1 and X2 and an exogenous constant appearing on the right hand side. Finally, if the endogenous variables do not appear on the right hand side (for example, where X1 is less than or equal to one-third the sum of X2 + 4X3) then the inequality would be manipulated to state: X1 - 1/ 3X2 - 4 / 3X3 ≤ 0 This is an example where the w's in the ratio control constraint are zero. This particular constraint type is a special case of the supply/demand balances. It is not used explicitly in any of the general formulations, but would also be used in a feed problem formulation where the quantity of feed to be produced was not exogenously given (i.e., on the right hand side) but rather was an endogenous variable. Bounds Upper and lower bounds have important implications for the performance of the simplex algorithm. Upper bounds are resource limitation constraints; however, they only involve a single variable. Similarly, lower bounds are minimum requirement constraints on a single variable. Examples are: X1 ≤ 4 X1 ≥2. Such constraints are usually exploited by LP solvers so that they do not enter the basis inverse. 59 CU IDOL SELF LEARNING MATERIAL (SLM)

Accounting Relations Accounting relations are used to add endogenous sums for model solution summary purposes. These relations are used for modeler convenience in summarizing a solution (i.e., adding up total labour utilized by crop). Accounting relations can be depicted as either In the first case the surplus variable would equal the sum of AX (assuming AX is always non-negative). The second form of the equation simply introduces an accounting variable which takes on the value of the sum. Accounting relations are discussed in the purposeful modelling section. Deviation Constraints Deviation constraints are used to develop the endogenous deviation of a particular sum from a target level. The general format of these constraints is as follows: Here Ti is a target level and Devi is a deviation variable indicating the amount the endogenous sum (gijxj) deviates (as measured by the deviation variable Devi) from the target level (Ti). The deviation constraint concept is utilized in the nonlinear transformations involving absolute value, multi-objective programming, and risk modelling. Approximation or Convexity Constraints A convexity constraint requires the sum of a set of variables to be equal to or possibly less than or equal to one. These are commonly used in approximations. 3.3 GRAPHICAL METHOD A linear program can be solved by multiple methods. In this section, we are going to look at the Graphical method for solving a linear program. This method is used to solve a two- variable linear program. If you have only two decision variables, you should use the graphical method to find the optimal solution. A graphical method involves formulating a set of linear inequalities subject to the constraints. Then the inequalities are plotted on an X-Y plane. Once we have plotted all the inequalities on a graph the intersection region gives us a feasible region. The feasible region explains what all values our model can take. And it also gives us the optimal solution. 3.3.1 Graphical Analysis of Linear Programming 60 CU IDOL SELF LEARNING MATERIAL (SLM)

Let’s understand this with the help of an example. Example: A farmer has recently acquired a 110 hectares piece of land. He has decided to grow Wheat and barley on that land. Due to the quality of the sun and the region’s excellent climate, the entire production of Wheat and Barley can be sold. He wants to know how to plant each variety in the 110 hectares, given the costs, net profits and labour requirements according to the data shown below: Variety Cost (Price/Hec) Net Profit (Price/Hec) Man-days/Hec Wheat 100 50 10 Barley 200 120 30 Table 3.9: Cost, profit and effort required for each plant The farmer has a budget of US$10,000 and availability of 1,200 man-days during the planning horizon. Find the optimal solution and the optimal value. Solution: To solve this problem, first we are going to formulate a linear program. Formulation of Linear Problem Step 1: Identify the Decision Variables The total area for growing Wheat = X (in hectares) The total area for growing Barley = Y (in hectares) X and Y are my decision variables. Step 2: Write the Objective Function Since the production from the entire land can be sold in the market. The farmer would want to maximize the profit for his total produce. We are given net profit for both Wheat and Barley. The farmer earns a net profit of US$50 for each hectare of Wheat and US$120 for each Barley. Our objective function (given by Z) is, Max Z = 50X + 120Y Step 3: Writing the Constraints 1. It is given that the farmer has a total budget of US$10,000. The cost of producing Wheat and Barley per hectare is also given to us. We have an upper cap on the total cost spent by the farmer. So our equation becomes: 61 CU IDOL SELF LEARNING MATERIAL (SLM)

100X + 200Y ≤ 10,000 2. The next constraint is the upper cap on the availability of the total number of man- days for the planning horizon. The total number of man-days available is 1200. As per the table, we are given the man-days per hectare for Wheat and Barley. 10X + 30Y ≤ 1200 3. The third constraint is the total area present for plantation. The total available area is 110 hectares. So the equation becomes, X + Y ≤ 110 Step 4: The Non-Negativity Restriction The values of X and Y will be greater than or equal to 0. This goes without saying. X ≥ 0, Y ≥ 0 We have formulated our linear program. It’s time to solve it. Solving an LP through Graphical method Since we know that X, Y ≥ 0. We will consider only the first quadrant. To plot the graph for the above equations, first the need is to simplify all the equations. 100X + 200Y ≤ 10,000 can be simplified to X + 2Y ≤ 100 by dividing by 100. 10X + 30Y ≤ 1200 can be simplified to X + 3Y ≤ 120 by dividing by 10. The third equation is in its simplified form, X + Y ≤ 110. Plot the first 2 lines on a graph in the first quadrant (like shown below) The optimal feasible solution is achieved at the point of intersection where the budget & man-days constraints are active. This means the point at which the equations X + 2Y ≤ 100 and X + 3Y ≤ 120 intersect gives us the optimal solution. The values for X and Y which give the optimal solution is at (60,20). To maximize profit the farmer should produce Wheat and Barley in 60 hectares and 20 hectares of land respectively. The maximum profit the company will gain is, Max Z = 50 * (60) + 120 * (20) = US$5400 62 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 3.10 Solving an LP through graphical method 3.3.2 Graphical Linear Programming Solution Owing to the importance of linear programming models in various industries, many types of algorithms have been developed over the years to solve them. Some famous mentions include the Simplex method, the Hungarian approach, and others. Here we are going to concentrate on one of the most basic methods to handle a linear programming problem i.e. the graphical method. In principle, this method works for almost all different types of problems but gets more and more difficult to solve when the number of decision variables and the constraints increases. Therefore, we’ll illustrate it in a simple case i.e. for two variables only. So let’s get started with the graphical method! The Graphical Method We will first discuss the steps of the algorithm: Step 1: Formulate the LP (Linear programming) Problem 63 CU IDOL SELF LEARNING MATERIAL (SLM)

We have already understood the mathematical formulation of an LP problem in a previous section. Note that this is the most crucial step as all the subsequent steps depend on our analysis here. Step 2: Construct a Graph and Plot the Constraint Lines The graph must be constructed in ‘n’ dimensions, where ‘n’ is the number of decision variables. This should give you an idea about the complexity of this step if the number of decision variables increases. One must know that one cannot imagine more than 3-dimensions anyway! The constraint lines can be constructed by joining the horizontal and vertical intercepts found from each constraint equation. Step 3: Determine the Valid Side of Each Constraint Line This is used to determine the domain of the available space, which can result in a feasible solution. How to check? A simple method is to put the coordinates of the origin (0,0) in the problem and determine whether the objective function takes on a physical solution or not. If yes, then the side of the constraint lines on which the origin lies is the valid side. Otherwise it lies on the opposite one. Step 4: Identify the Feasible Solution Region The feasible solution region on the graph is the one which is satisfied by all the constraints. It could be viewed as the intersection of the valid regions of each constraint line as well. Choosing any point in this area would result in a valid solution for our objective function. Step 5: Plot the Objective Function on the Graph It will clearly be a straight line since we are dealing with linear equations here. One must be sure to draw it differently from the constraint lines to avoid confusion. Choose the constant value in the equation of the objective function randomly, just to make it clearly distinguishable. Step 6: Find the Optimum Point Optimum Points An optimum point always lies on one of the corners of the feasible region. How to find it? Place a ruler on the graph sheet, parallel to the objective function. Be sure to keep the orientation of this ruler fixed in space. We only need the direction of the straight line of the objective function. Now begin from the far corner of the graph and tend to slide it towards the origin. 64 CU IDOL SELF LEARNING MATERIAL (SLM)

 If the goal is to minimize the objective function, find the point of contact of the ruler with the feasible region, which is the closest to the origin. This is the optimum point for minimizing the function.  If the goal is to maximize the objective function, find the point of contact of the ruler with the feasible region, which is the farthest from the origin. This is the optimum point for maximizing the function. 3.4 SIMPLEX METHODS The Simplex method is an approach to solving linear programming models by hand using slack variables, tableaus, and pivot variables as a means to finding the optimal solution of an optimization problem. A linear program is a method of achieving the best outcome given a maximum or minimum equation with linear constraints. Most linear programs can be solved using an online solver such as MATLAB, but the Simplex method is a technique for solving linear programs by hand. To solve a linear programming model using the Simplex method the following steps are necessary:  Standard form  Introducing slack variables  Creating the tableau  Pivot variables  Creating a new tableau  Checking for optimality  Identify optimal values Simplex Method is one of the most powerful & popular methods for linear programming. The simplex method is an iterative procedure for getting the most feasible solution. In this method, we keep transforming the value of basic variables to get maximum value for the objective function. A linear programming function is in its standard form if it seeks to maximize the objective function. 65 CU IDOL SELF LEARNING MATERIAL (SLM)

66 CU IDOL SELF LEARNING MATERIAL (SLM)

are called slack variables. They are non-negative numbers that are added to remove the inequalities from an equation. The above explanation gives the theoretical explanation of the simplex method. Let’s understand it through an example. Example: The advertising alternatives for a company include television, newspaper and radio advertisements. The cost for each medium with its audience coverage is given below. Table 3.11the cost for each medium with its audience coverage The local newspaper limits the number of advertisements from a single company to ten. Moreover, in order to balance the advertising among the three types of media, no more than half of the total number of advertisements should occur on the radio. And at least 10% should occur on television. The weekly advertising budget is $18,200. How many advertisements should be run in each of the three types of media to maximize the total audience? Step 1: Identify Decision Variables Let , , represent the total number of ads for television, newspaper, and radio respectively. Step 2: Objective Function The objective of the company is to maximize the audience. The objective function is given by: Step 3: Write down the constraints 67 CU IDOL SELF LEARNING MATERIAL (SLM)

It is clearly given that we have a budget constraint. The total budget which can be allocated is $18,200. And the individual costs per television, newspaper and radio advertisement is $2000, $600 and $300 respectively. This can be represented by the equation, For a newspaper advertisement, there is an upper cap on the number of advertisements to 10. My first constraints are, The next constraint is the number of advertisements on television. The company wants at least 10% of the total advertisements to be on television. So, it can be represented as: The last constraint is the number of advertisements on the radio cannot be more than half of the total number of advertisements. It can be represented as Now, we have formulated my linear programming problem. We are using the simplex method to solve this. We will take you through the simplex method one by one. To reiterate all the constraints are as follows. We have simplified the last two equations to bring them in standard form. We have a total of 4 equations. To balance out each equation, we are introducing 4 slack variables, S1, S2, S3, S4. So the equations are as follows: 68 CU IDOL SELF LEARNING MATERIAL (SLM)

Hope now you are making sense of the entire advertising problem. All the above equations are only for your better understanding. Now if you solve these equations, you will get the values for X1= 4, X2= 10 and X3= 14. On solving the objective function you will get the maximum weekly audience as 1,052,000. 3.4.1 Two Phase Method In this method, the problem is solved in two phases as given below. First Phase a. All the terms on R.H.S. should be non-negative. If some are -ve then they must be made +ve as explained earlier. b. Express constraints in standard form. c. Add artificial variables in equality constraints or (>) type constraints. d. Form a new objective function W which consisted of the sum of all the artificial variables W = A1 + A2 + …………………… + Am Function (W) is known as infeasibility form. e. Function W is to be minimized subject to constraints of the original problem and the optimum basic feasible solution is obtained. Any of the following three cases may arise: i. Min. W > 0 and at least one artificial variable appears in column “Basic variables” at Positive level. In such cases, no feasible solution exists for the original L.P.P. and the procedure is stopped. ii. Min. W = 0 and at least one artificial variable appears in column “Basic Variables” at zero level. In such a case, the optimum basic feasible solution to the infeasibility form may or may not be a basic feasible solution to the given (original) L.P.P. To obtain a basic feasible solution, we continue phase I and try to drive all artificial variables out of the basis and then proceed to phase II. 69 CU IDOL SELF LEARNING MATERIAL (SLM)

iii. Min. W=0 and no artificial variable appears in the column “Basic variables” current solution’. In such a case a basic feasible solution to the original L.P.P. has been found. Proceed to phase II. Second Phase Use the optimum basic feasible solution of phase I as a starting solution for the original L.P.P. Using simplex method; make iterations till an optimal basic feasible solution for it is obtained. It may be noted that the new objective function W is always of minimization type regardless of whether the given (original) L.P.P. is of maximization or minimization type. Let us take the following example. Example 1 (Two phase simplex Method): Use two-phase simplex Method to Minimize Z =-3X – 2Y – 2Z Subject to 5X + 7Y + 4Z < 7 -4X + 7Y+ 5Z > –2 3X + 4 V – 6Z > 29/7 X, Y, Z >0 Solution: First Phase It consists of the following steps. i. In second constraint, R.H.S. is -ve, therefore it is made +ve by multiplying with minus sign on both sides 4X – 7Y – 5Z < 2 ii. Adding slack variables in the constraints 5X + 7Y + 4Z + S1 =7 4X – 7Y – 5Z + S2 =2 3X + 4Y – 6Z – S3 = 29/7 where X, Y, Z, S1, S2, S3 > 0 iii. Put X = Y= Z = 0, we get S1 = 7, S2 = 2, S3 = -29/7. as an initial solution. But series S3 is -ve , we will add artificial variable A,i.e. 3X+ 4Y- 6Z- S3+ A1 =29/7 iv. Objective function which is minimization type is made maximization type i.e. 70 CU IDOL SELF LEARNING MATERIAL (SLM)

Maximize Z = 3X + 2Y + 2Z v. We introduce a new objective function W = A1 for the first phase which is to be minimized. vi. Substituting X = Y = Z = S3 = 0 in the constraints we get S1 = 7, S2 = 2, /A1 = 29/7 as initial basic feasible solution Table 1 if formed. Preformed optimality test Table 3.12: Initial basic feasible solution for phase-I As Cj-Ej is negative under the same columns (minimization problem) the current basic feasible solution can be improved. Iterate Towards and Optimal Solution: Performing iterations to get an optimal solution. Table 3.13: Key element utility 71 Replace S1 by X2. This is shown in table below CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 3.14 Second feasible solution for phase - I In the table there is a tie for the key row X column is the key column and y column is the first column of the identity. Following the method for tie breaking we find that y column does not break the tie. The next column of the identity i.e. S2-column yields A1-row as the key row. Thus (1/7) is the key element is made unity in table Table 3.15 Key element unity Replace A1 by X as shown in table below 72 CU IDOL SELF LEARNING MATERIAL (SLM)

Table 3.16: Optimal solution for phase I Table 5 gives the optimal solution. Also since minimum W=0 and there is no artificial variable in the basic variables i.e. in the current solution, Table5 gives a basic feasible solution for the Phase-ll. Second Phase The original objective function is Maximize Z = 3x + 2y + 2Z + OS, + 0S2 + 0S3 It is to be maximized using original constraints. Using solution of phase I as the starting solution for phase II and carrying out computation using simplex algorithm, we get the following table. Table3.17: Carrying out computation using simplex algorithm Key element is made unity in the following table. 73 CU IDOL SELF LEARNING MATERIAL (SLM)

Table3.18: Key element unity Replace S2 by X3. Table 3.19 Optimal basic feasible solution 3.4.2 M Method Linear Programming (LP) is a branch of optimization theory which studies the minimization (or maximization) of a linear objective function, subject to linear equality and/or linear inequality constraints. LP has found a lot of successful applications both in theoretical and real world contexts, especially in countless engineering applications. Most of the algorithms 74 CU IDOL SELF LEARNING MATERIAL (SLM)

developed so far to solve LP problems fall in one of the two following categories: basis exchange methods and interior point methods. Researchers argued a lot about the pros and the cons of these approaches, ending up asserting the equal dignity of both. The best choice depends on the characteristics of the problem at hand. Concerning this work, we decided to focus on the class of basis exchange methods and, in particular, on it’s probably most famous member: the Simplex algorithm firstly proposed in 1939 by Kantorovič and independently rediscovered by Dantzig during the 1940s. This algorithm needs a feasible basic solution to start from, an input which is not trivial to generate for complex real-world problems. The main ways to overcome this difficulty are: the two-phaseapproach and the Big-M method. The former splits the optimization in two-phases, and in each it runs the Simplex algorithm on a phase-specific problem. In the first one, the problem is a simple task for which a feasible starting point is known, and whose optimum is a valid basic solution for the original problem. The second one is the original problem itself. In spite of the guarantee of convergence to the optimum (if it exists), such an approach wastes a lot of time, having to run the Simplex algorithm twice rather than once. The other possibility is diametrically opposed to the previous one, indeed, it requires just one run of the Simplex algorithm, though on a problem different from the original one. The latter approach is known as Big-M method, since it requires a big parameter M: it consists of applying the Simplex algorithm to a modified and parameterized version of the original problem for which a feasible initial basic solution is known. In particular, the big constant M (along with some auxiliary variables) is added to the original problem; a good tuning of such constant also guarantees that the original problem and the modified one share the same optimum. Thus, the drawback of the Big-M method is that it adds a new parameter, which also needs to be properly set: a too small value does not guarantee the convergence to the same optimum of the original problem, while a too big value may generate loss of precision and numerical instabilities. The actual goal of this work is to overcome the Big-M method issues by means of a non-Archimedean modification of the original method that is converting the LP problem at hand into a new one where the cost function involves infinite and infinitesimal quantities too. In order to realize such non- Archimedean extension, we exploited the Grossone Methodology proposed by Y.D. Sergeyev, a powerful framework which lets one numerically manipulate infinite and infinitesimal quantities. Even more interestingly, algorithms involving the Grossone Methodology can run on a hardware computing engine, called Infinity Computer, which is a completely new kind of supercomputer. Once opportunely modified, the new problem can be solved by a recent extension of the Simplex algorithm due to Cococcioni et al. namely the gross-Simplex algorithm (in brief, G-Simplex). The latter is an improved Simplex algorithm able to solve non-Archimedean LP problems too. Together, the G-Simplex algorithm and the non-Archimedean modified problem give birth to the parameter-less procedure presented in this work, called by us the Infinitely-Big-M method (abbreviated I-Big-M), since it relies on the use of an infinitely big constant, which is the same for all the problems and thus does not have to be specified by the user. 75 CU IDOL SELF LEARNING MATERIAL (SLM)

The Linear Programming Problems and theBig-M Method A possible representation of an LP problem, which may be a little complex at first sight, is shown in Eq. (1): As said, the Simplex algorithm requires a feasible basic solution to start from which may not be easy to find by hand. The Big-M method tackles the problem transforming the original problem by adding some auxiliary variables which guarantee the existence of an initial feasible basic solution. However, not being part of the original problem, all of them must be equal to zero in the optimal solution of the modified problem. In order to guide the optimizer towards this annihilation, the Big-M method adds the auxiliary variables to the cost function and weights them with a big penalty M. The form of the modified problem is shown in Eq. (2): 76 CU IDOL SELF LEARNING MATERIAL (SLM)

However, the Big-M method has a couple of relevant drawbacks. Actually, it turns a parameter-less problem into a parametric one, adding the scalar factor M. In addition, such parameter needs to be a-priory carefully set, in order to guarantee the correctness of the optimization process. Indeed, a too low value could lead to a non-zeroing of the auxiliary variables (and, thus, to no feasible solutions, even if they exist), a too high value could lead to a loss of precision and to numerical instabilities. Such setting issues, along with the need of re-tuning M for each different problem to solve, are crucial and struggling aspects from a practical point of view, sometimes limiting the applicability of the method in real contexts at all. 3.4.3 Solutions In this unit, a systematic procedure for solving linear programs has been presented. This procedure, called the simplex method, proceeds by moving from one feasible solution to another, at each step improving the value of the objective function. Moreover, the method terminates after a finite number of such transitions. Two characteristics of the simplex method have led to its widespread acceptance as a computational tool. First, the method is robust. It solves any linear program; it detects redundant constraints in the problem formulation; it identifies instances when the objective value is unbounded over the feasible region; and it solves problems with one or more optimal solutions. The method is also self- initiating. It uses itself either to generate an appropriate feasible solution, as required, to start the method, or to show that the problem has no feasible solution. Second, the simplex method provides much more than just optimal solutions. As by-products, it indicates how the optimal solution varies as a function of the problem data (cost coefficients, constraint coefficients, and right hand-side data). This information is intimately related to a linear program called the dual to the given problem, and the simplex method automatically solves this dual problem along with the given problem. These characteristics of the method are of primary importance 77 CU IDOL SELF LEARNING MATERIAL (SLM)

for applications, since data rarely is known with certainty and usually is approximated when formulating a problem. 3.5 SUMMARY  Optimization is the way of life. We all have finite resources and time and we want to make the most of them. From using your time productively to solving supply chain problems for your company – everything uses optimization.  Linear programming (LP) is one of the simplest ways to perform optimization. It helps to solve some very complex optimization problems by making a few simplifying assumptions. Many problems can be solved by Linear Programming.  Applications of linear programming are everywhere. One can use linear programming at personal and professional fronts. For example, you can use linear programming when you are driving from home to work and want to take the shortest route. Or when you have a project delivery you make strategies to make your team work efficiently for on-time delivery.  Moreover, linear programming is used for obtaining the most optimal solution for a problem with given constraints. In linear programming, you can formulate your real- life problem into a mathematical model. It involves an objective function, linear inequalities subject to constraints.  Formulation of the LPP Problem i. Recognize the decision variables and assign symbols to them like X, Y, Z & so on). Now these are the quantities we wish to find out. ii. Express all the constraints in terms of inequalities in relation to the decision variable. iii. Formulate the objective function in terms of the decision variables. iv. Add the non-negativity condition/constraints.  Graphical Method to Solve an LPP - The graphical method of solving a linear programming problem can be used when there are only two decision variables. If the problem has three or more variables, the graphical method is not suitable. In that case the SIMPLEX METHOD should be used.  Two characteristics of the simplex method have led to its widespread acceptance as a computational tool. First, the method is robust. It solves any linear program; it detects redundant constraints in the problem formulation; it identifies instances when the objective value is unbounded over the feasible region; and it solves problems with one or more optimal solutions. 78 CU IDOL SELF LEARNING MATERIAL (SLM)

 The method is also self-initiating. It uses itself either to generate an appropriate feasible solution, as required, to start the method, or to show that the problem has no feasible solution.  Second, the simplex method provides much more than just optimal solutions. As by- products, it indicates how the optimal solution varies as a function of the problem data (cost coefficients, constraint coefficients, and right hand-side data).  This information is intimately related to a linear program called the dual to the given problem, and the simplex method automatically solves this dual problem along with the given problem. These characteristics of the method are of primary importance for applications, since data rarely is known with certainty and usually is approximated when formulating a problem. 3.6 KEYWORDS  Simplex Method- The simplex method is a systematic procedure for testing the vertices as possible solutions. Some simple optimization problems can be solved by drawing the constraints on a graph. However, this method is useful only for systems of inequalities involving two variables.  M Method- In operations research, the Big M method is a method of solving linear programming problems using the simplex algorithm. The Big M method extends the simplex algorithm to problems that contain \"greater-than\" constraints.  Two Phase Method- In Two Phase Method, the whole procedure of solving a linear programming problem (LPP) involving artificial variables is divided into two phases. In phase I, we form a new objective function by assigning zero to every original variable (including slack and surplus variables) and -1 to each of the artificial variables.  Blending Problems- Blending problems are a typical application of mixed integer- linear programming (MILP). They involve blending several resources or materials to create one or more products corresponding to a demand. Mixed integer-linear programs are linear programs in which some variables are required to take integer values.  Deviation Constraints- The deviation constraint concept is utilized in the nonlinear transformations involving absolute value, multi-objective programming, and risk modelling. A convexity constraint requires the sum of a set of variables to be equal to or possibly less than or equal to one. 3.7 LEARNING ACTIVITY 79 CU IDOL SELF LEARNING MATERIAL (SLM)

1. A company makes two products (say, P and Q) using two machines (say, A and B). Each unit of P that is produced requires 50 minutes processing time on machine A and 30 minutes processing time on machine B. Each unit of Q that is produced requires 24 minutes processing time on machine A and 33 minutes processing time on machine B. Machine A is going to be available for 40 hours and machine B is available for 35 hours. The profit per unit of P is $25 and the profit per unit of Q is $30. Company policy is to determine the production quantity of each product in such a way as to maximize the total profit given that the available resources should not be exceeded. Now formulate the problem of deciding how much of each product to make in the current week as an LP. ___________________________________________________________________________ ___________________________________________________________________________ 2. A municipality has two incinerators for burning trash. Incinerator A costs $3 .80 per ton of trash to operate, and has a capacity of 28 tons per day. Incinerator B costs $4 .25 per ton to operate, and has a capacity of 30 tons per day. The municipality produces over 100 tons of trash per day, and all trash not burned in the incinerators must be buried in a landfill at a cost of $5 .00 per ton. The city manager wants to minimize costs by burning as much trash as possible. However, the city must conform to environmental regulations limiting production of pollutants from burning in the incinerators to 180 pounds of hydrocarbons and 640 pounds of particulates a day. Incinerator A produces 3 pounds of hydrocarbons and 20 pounds of particulates for every ton of trash burned, and incinerator B produces 5 pounds of hydrocarbons and 10 pounds of particulates for every ton of trash. Determine the optimum amount of trash to burn in each incinerator. ___________________________________________________________________________ ___________________________________________________________________________ 3.8 UNIT END QUESTIONS A. Descriptive Question Short Questions 1. What is the blending problem? 2. What are the steps involved in the formulation of LPP? 3. What are the advantages of LPP? 4. What are the types of constraints? 5. How does a graphical method help in solving a linear program? 80 CU IDOL SELF LEARNING MATERIAL (SLM)

Long Questions 1. Write a note on the M method? 2. What are the conditions of the first phase involving two phase method? 3. Why is the simplex method very popular in linear programming? 4. How would you find optimum points? 5. Explain the constraint of supply and demand balance. B. Multiple Choice Questions 1. Which are the components involved in linear programming problems? a. Decision variable b. Environment parameters c. Result variable d. All of these 2. Which doesn’t belong to the merits of LLP? a. Helps management to make efficient use of resources b. Doesn’t provide quality in decision making c. Excellent tools for adjusting to meet changing demands d. Fast determination of the solution if a computer is used 3. Which is not a constraint? a. Resource limitations b. Supply and demand balance c. Maximum requirements d. Ratio control 4. Which method of LP reflects constructing a graph and plotting the constraint lines? a. Graphical method b. Simplex method c. Two phase method d. None of these 5. Which method has the attribute that all the terms on R.H.S should be non-negative? a. Two phase method b. Simplex method 81 CU IDOL SELF LEARNING MATERIAL (SLM)

c. Graphical method d. Perfect method Answers 1-d 2-b 3-c 4-a 5-a 3.9 REFERENCES References  ArimitraMaitiElements of a Linear Programming Problem (LPP) |Towards Data Science  Baker, T. and B.A. McCarl, \"Representing Farm Resource Availability over Time in Linear Programs: A Case Study.\" North Central Journal of Agricultural Economics, 4(1982):59-68.  Linear Programming | Applications Of Linear Programming (analyticsvidhya.com)  Two Phase Methods of Problem Solving in Linear Programming: First and Second Phase (yourarticlelibrary.com)  The Big-M method with the numerical infinite M | SpringerLink Textbooks  Anderson, Sweeney, Williams, Camm, Cochran, Fry, OhlmanAn introduction to Management Science  Dantzig, G.B. \"Linear Programming Under Uncertainty.\" Management Science. 1(1955):197-206.  Dantzig, G.D. and R.M. Van Slyke. \"Generalized Linear Programming.\" Chapters in Optimization Methods for Large Scale Systems, D.A. Wisner, (ed.). McGraw-Hill: New York, 1970.  Heady, E.O. and W.V. Candler. Linear Programming Methods. Ames, IA: Iowa State University Press, 1958. Websites  dormsem1linearprogramming.pdf (mu.ac.in)  new10.pdf (tamu.edu)  Graphical Method for Linear Programming Problems - Videos (toppr.com)  AMP-Chapter-02.pdf (mit.edu) 82 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 4 – TRANSPORTATION PROBLEMS PART 1 STRUCTURE 4.0 Learning Objectives 4.1 Introduction 4.2 Concepts 4.2.1 Transportation Algorithm 4.3 Solutions 4.3.1 Basic Feasible Solution 4.4 Summary 4.5 Keywords 4.6 Learning Activity 4.7 Unit End Questions 4.8 Reference 4.0 LEARNING OBJECTIVES After studying this unit, you will be able to:  Elucidate solving transport problem from the perspective of operational research.  Calculate transport algorithm as per the requirement.  Find possible solutions to minimize the cost of transportation and make it hassle free. 4.1 INTRODUCTION The transportation problem in operational research is concerned with finding the minimum cost of transporting a single commodity from a given number of sources (e.g. factories) to a given number of destinations (e.g. warehouses). These types of problems can be solved by general network methods, but here we use a specific transportation algorithm. The data of the model include 1. The level of supply at each source and the amount of demand at each destination. 2. The unit transportation cost of the commodity from each source to each destination. Since there is only one commodity, a destination can receive its demand from more than one source. The objective is to determine how much should be shipped from each source to each destination so as to minimise the total transportation cost. 83 CU IDOL SELF LEARNING MATERIAL (SLM)

The transportation problem itself was first formulated by Hitchcock (1941), and was independently treated by Koopmans and Kantorovich .In fact Monge (1781) formulated it and solved it by geometrical means. Hitchaxic (1941) developed the basic transportation problem; however it could be solved for optimally as answers to complex business problems only in 1951, when George B. Dantizig applied the concept of Linear programming in solving the transportation model. Dantzing (1951) gave the standard LP-formulation TP and applied the simplex method to solve it. Since then the transportation problem has become the classical common subject in almost every textbook on operation research and mathematical programming. The transportation problem can be described using linear programming mathematical models and usually it appears in a transportation tableau. Transportation problems thus typically arise in situations involving physical movement of goods from plants to warehouses, warehouses to warehouses, wholesalers to retailers and retailers to customers. Solution of the transportation problems requires the determination of how many units should be transported from each supply origin to each demand destination in order to satisfy all the destination demands while minimizing the total associated cost of transportation. The easiest way to recognise a transportation problem is to consider a typical situation as shown in the following figure. Assume that a manufacturer has three factories F1, F2 and F3 producing the same product. From these factories, the product is transported to three warehouses W1, W2, and W3. Each factory has a limited supply and each warehouse has specific demand. Each factory can transport to each warehouse but the transportation costs vary for different combinations. The problem is to determine the quantity each factory should transport to each warehouse in order to minimize total transportation costs. 84 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 4.1: Example of a transport problem The important feature of the standard transportation problem is that it can be expressed in the form of a table, which displays the values of all the data coefficients (si, dj, cij) associated with the problem. In-fact, the constraints and the objective function of the transportation model can be read off directly from the table. The supply constraints can be obtained by merely equating the sum of all the variables in each row to the factory capacities, similarly the demand constraints are obtained by equating the sum of all the variables in each column to the warehouse demands. 4.2 CONCEPTS Transportation problem is a particular class of linear programming, which is associated with day to-day activities in our real life and mainly deals with logistics. It helps in solving problems on distribution and transportation of resources from one place to another. The goods are transported from a set of sources (e.g., factory) to a set of destinations (e.g., warehouse) to meet the specific requirements. There is a type of linear programming problem that may be solved using a simplified version of the simplex technique called transportation method. Because of its major application in solving problems involving several product sources and several destinations of products, this type of problem is frequently called the transportation problem. It gets its name from its application to problems involving transporting products from several sources to several destinations. Although the formation can be used to represent more general assignment and scheduling problems as well as transportation and distribution problems. The two common 85 CU IDOL SELF LEARNING MATERIAL (SLM)

objectives of such problems are either (1) minimizing the cost of shipping m units to n destinations or (2) maximize the profit of shipping m units to n destinations. The concept is to look principally at a specific type of Linear Programming Problem, known as the Transportation Problem. Transportation theory is the name given to the study of optimal transportation and allocation of resources. 4.2.1 Transportation Algorithm In the application of linear programming techniques, the transportation problem was probably one of the first significant problems studied. The problem can be expressed by the formulation of a linear model, and it can be solved using the simplex algorithm. However, and because of the special structure of the linear model, it can be solved with a more efficient method. The transportation problem deals with the transportation of any product from m origins, O1, . . ., Om, to n destinations, D1, . . .,Dn, with the aim of minimizing the total distribution cost, where:  The origin Oi has a supply of ai units, i = 1, . . ., m.  The destination Dj has a demand for bj units to be delivered from the origins, j = 1, . . ., n.  cij is the cost per unit distributed from the origin Oi to the destination Dj,i = 1, . . ., m, j = 1, . . ., n. In mathematical terms, the above problem can be expressed as finding a set of xij ’s, i = 1, . . ., m, j = 1, . . ., n, to meet supply and demand requirements at a minimum distribution cost. The corresponding linear model is Thus, the problem is to determine xij, the number of units to be transported from Oi to Dj, so that supplies will be consumed and demands satisfied at an overall minimum cost. 86 CU IDOL SELF LEARNING MATERIAL (SLM)

The first m constraints correspond to the supply limits, and they express that the supply of commodity units available at each origin must not be exceeded. The next n constraints ensure that the commodity unit requirements at destinations will be satisfied. The decision variables are defined positively, since they represent the number of commodity units transported. The transportation problem in standard form is shown below: Example. Two bread factories, O1 and O2, make the daily bread in a city. The bread is delivered to the three bakeries of the city: D1, D2 and D3. Figure 4.2: Supplies of bread factories, the demands of bakeries and the per unit transportation costs We define the following decision variables: 87 CU IDOL SELF LEARNING MATERIAL (SLM)

xij: the number of loaves of bread to be distributed from the bread factory Oi to the bakery Dj,i = 1, 2, j = 1, 2, 3. The corresponding linear model is the following: We can write the constraints in equation form, because the total supply is equal to the total demand. In order to analyse the structure of matrix A, we write the model in matrix form. 88 CU IDOL SELF LEARNING MATERIAL (SLM)

In this example, we have two origins, m = 2, and three destinations, n = 3. Matrix A has 2 + 3 rows and 2 × 3 columns. It can be verified that the rank of the matrix is 4. Note that each column of the matrix has only two 1’s and 0’s elsewhere. We use two subscripts to denote each one of the columns of matrix A, as we did when we defined the decision variables for the transportation problem. Thus, in this example we denote by a11, a12, a13, a21, a22, a23 the six column vectors of the matrix. If we observe the positions at which the 1’s can be found, we can easily see that, vector a11 for instance has a 1 in the 1st row and the other in the m + 1th row, vector a21 has the 1’s in the 2nd and m + 1th rows and vector a23 has the 1’s in the 2nd and m + 3th rows. In general, we can state that the two 1’s of vector aij of matrix A are in rows i and m + j. Therefore, the structure of matrix A depends on the number of origins and the number of destinations of the problem; any transportation problem having m origins and n destinations has the same matrix A. This matrix has m + n rows and m × n columns. The rank of matrix A is m + n − 1, that is, any basis consists of m + n − 1 vectors. There are only two 1’s in each column vector aij of matrix A, and they are located in rows i and m + j, being 0 the rest of the values of the column vector. Thus, a transportation problem is specified by the number of origins, the number of destinations, the supplies, the demands and the per-unit transportation costs. All this information can be abbreviated in the form of a rectangular array. Consider a transportation problem which has as objective the minimization of the total transportation cost. The transportation algorithm consists of the following steps: Step 1. Balance the transportation problem. Step 2. Compute an initial basic feasible solution. Step 3. Compute the values u1, . . ., um and v1, . . .,vn associated with the current basis. Step 4. Compute the reduced cost coefficient zij − cij = ui + vj − cij for every non-basic variable xij:  If there is one or more zij − cij> 0, then the current solution may be improved. Select the variable with the most positive zij − cij to enter the basis, and go to Step 5.  If zij−cij< 0 for all non-basic variables, then the current basic feasible solution is optimal and unique. Stop.  If zij − cij ≤ 0 for all non-basic variables, and for one or more of the non-basic variables zij − cij = 0 holds, then the optimal solution is multiple. Select anyone of those non-basic variables to enter the basis, and go to Step 5 Step 5. Find the cycle which includes some of the current basic variables and the entering variable. Recompute the values of the variables in the cycle to obtain a new basic feasible solution. Go to Step 3. 89 CU IDOL SELF LEARNING MATERIAL (SLM)

4.3 SOLUTIONS Feasible Solution: A feasible solution to a transportation problem is a set of non-negative values xij (i=1, 2, m, j=1, 2…n) that satisfies the constraints. Basic Feasible Solution: A feasible solution is called a basic feasible solution if it contains not more than m+n–1 allocations, where m is the number of rows and n is the number of columns in a transportation problem. Optimal Solution: Optimal Solution is a feasible solution (not necessarily basic) which optimizes (minimize) the total transportation cost. Non degenerate basic feasible Solution: If a basic feasible solution to a transportation problem contains exactly m+n–1 allocation in independent positions, it is called a Non degenerate basic feasible solution. Here m is the number of rows and n is the number of columns in a transportation problem. Degeneracy: If a basic feasible solution to a transportation problem contains less than m+n–1 allocations, it is called a degenerate basic feasible solution. Here m is the number of rows and n is the number of columns in a transportation problem. 4.3.1 Basic Feasible Solution The number of basic variables of the general transportation problem at any stage of feasible solution must be (m + n – 1). Now a degenerate basic feasible solution (a feasible solution) involving exactly (m + n – 1) positive variables is known as non-degenerate basic feasible solution otherwise it is said to be degenerate basic feasible solution. These allocations should be independent positions in case of non-degenerate basic feasible solutions. Key Points Optimum Solution: A feasible solution is said to be optimal, if it minimizes the total transportation cost. Unbalance TP If total supply is not equal to total demand, then it balances with dummy source or destination. Finding an Initial Basic Feasible Solutions There are three methods as given below: 1. Northwest corner method 2. Least cost method 3. Vogel’s approximation method (or Penalty method) Steps for North-West Corner Method 90 CU IDOL SELF LEARNING MATERIAL (SLM)

Allocate the maximum amount allowable by the supply and demand constraints to the variable x11 (i.e. the cell in the top left corner of the transportation tableau). If a column (or row) is satisfied, cross it out. The remaining decision variables in that column (or row) are non-basic and are set equal to zero. If a row and column are satisfied simultaneously, cross only one out (it does not matter which). Adjust supply and demand for the non-crossed out rows and columns. Allocate the maximum feasible amount to the first available non-crossed out element in the next column (or row). When exactly one row or column is left, all the remaining variables are basic and are assigned the only feasible allocation. Example: The ICARE Company has three plants located throughout a state with production capacity 50, 75 and 25 gallons. Each day the firm must furnish its four retail shops R1, R2, R3, & R4 with at least 20, 20, 50, and 60 gallons respectively. Table 4.1: The transportation costs (in Rs.) The economic problem is to distribute the available product to different retail shops in such a way so that the total transportation cost is minimum? Solution: Starting from the North West corner, we allocate min (50, 20) to P1R1, i.e., 20 units to cell P1R1. The demand for the first column is satisfied. The allocation is shown in the following table. 91 CU IDOL SELF LEARNING MATERIAL (SLM)

Table 4.2: Allocation Now we move horizontally to the second column in the first row and allocate 20 units to cell P1R2. The demand for the second column is also satisfied. Proceeding in this way, we observe that P1R3 = 10, P2R3 = 40, P2R4 = 35, P3R4 = 25. The resulting feasible solution is shown in the following. Here, number of retail shops (n) = 4, and Number of plants (m) = 3.Number of basic variables = m + n – 1 = 3 + 4 – 1 = 6. Initial basic feasible solution The initial basic feasible solution is x11=20, x12=5, x13=20, x23=40, x24=35, x34=25 and minimum cost of transportation=20 X 3 + 20 X 5 + 10 X 7 + 40 X 8 + 35 X 2 + 25 X 2 = 670 Steps for Least Cost Method Assign as much as possible to the cell with the smallest unit cost in the entire tableau. If there is a tie then choose arbitrarily. 1. Cross out the row or column which has satisfied supply or demand. If a row and column are both satisfied then cross out only one of them. 2. Adjust the supply and demand for those rows and columns which are not crossed out. 3. When exactly one row or column is left, all the remaining variables are basic and are assigned the only feasible allocation. Steps for Vogel’s Approximation Method (VAM) Determine a penalty cost for each row (column) by subtracting the lowest unit cell cost in the row (column) from the next lowest unit cell cost in the same row (column). 1. Identify the row or column with the greatest penalty cost. Break the ties arbitrarily (if there are any). Allocate as much as possible to the variable with the lowest unit cost in the selected row or column. Adjust the supply and demand and cross out the row or column that is already satisfied. If a row and column are satisfied simultaneously, only cross out one of the two and allocate a supply or demand of zero to the one that remains. 2. If there is exactly one row or column left with a supply or demand of zero, stop. 3. If there is one row (column) left with a positive supply (demand), determine the basic variables in the row (column) using the Minimum Cell Cost Method. Stop. 4. If all of the rows and columns that were not crossed out have zero supply and demand (remaining), determine the basic zero variables using the Minimum Cell Cost Method. Stop. 5. In any other case, continue with Step 1. 92 CU IDOL SELF LEARNING MATERIAL (SLM)

Example: Obtain an Initial BFS to the following Transportation problem using VAM method? Table 4.3: Transportation problem Solution: Since 3 1 4 1 j jiaib, the given problem is balanced TP. Therefore, there exists a feasible solution. Step -1: Select the lowest and next to lowest cost for each row and each column, then the difference between them for each row and column displayed within the first bracket against respective rows and columns. Here all the differences have been shown within the first compartment. Maximum difference is 15 which occurs at the second column. Allocate min (40,120) in the minimum cost cell (1,2). Step -2: Applying the same techniques we obtained the initial BFS. Where all capacities and demand have been exhausted. Table 4.4: Initial basic feasible solution The initial basic feasible solution is x12=40, x14=40, x21=10, x23=30, x24=30, x31=50.and minimum cost of transportation=22 X 40 + 4 X 80 + 24 X 10 + 9 X 30 + 7 X 30 + 32 X 50 = 3520. 93 CU IDOL SELF LEARNING MATERIAL (SLM)

Thus, the transportation problem not only solves the problem but also helps us to understand how the model works and what can be changed, and to what extent to modify the solution which in turn helps to determine the cost and an optimal supplier. 4.4 SUMMARY  One of the most important and successful applications of quantitative analysis to solving business problems has been in the physical distribution of products, commonly referred to as transportation problems.  Basically, the purpose is to minimize the cost of shipping goods from one location to another so that the needs of each arrival area are met and every shipping location operates within its capacity.  However, quantitative analysis has been used for many problems other than the physical distribution of goods. For example, it has been used to efficiently place employees at certain jobs within an organization.  We could set up a transportation problem and solve it using the simplex method as with any LP problem. However, the special structure of the transportation problem allows us to solve it with a faster, more economical algorithm than simplex.  Problems of this type, containing thousands of variables and constraints, can be solved in only a few seconds on a computer.  In fact, we can solve a relatively large transportation problem by hand. There are some requirements for placing an LP problem into the transportation problem category.  Transportation problems can be solved using the simplex method; however, the simplex method involves time-consuming computations.  An advantage to the transportation method is that the solution process involves only the main variables; artificial variables are not required, as they are in the simplex process. In fact, after applying the northwest corner rule, the problem is as far along as it would be using simplex after eliminating the artificial variables.  Simplex requires a minimum of iterations (each represented by another simplex tableau) equal to the number of rows plus columns minus 1.  This is the minimum; many problems require more iterations. Finally, some LP computer programs are set up to solve both simplex and transportation problems.  When the problems are introduced as transportation problems, the computer algorithms can solve them much faster. Although developed to solve problems in transporting goods from one location to another, the transportation method can be 94 CU IDOL SELF LEARNING MATERIAL (SLM)

used to solve other problems—such as the assignment example above—as long as the problem can be set up in the transportation problem form. 4.5 KEYWORDS  Transportation Tableau- Determination of an Initial Feasible Solution (IFS) to a transportation problem plays an important role in obtaining a minimal total transportation cost solution. Better initial feasible solution can result in a smaller number of iterations in attaining the minimal total cost solution.  Unbalanced Transport Problem- Unbalanced transportation problem is a transportation problem where the total availability at the origins is not equal to the total requirements at the destinations.  North West Corner Method- The North-West Corner Rule is a method adopted to compute the initial feasible solution of the transportation problem. The name North- west corner is given to this method because the basic variables are selected from the extreme left corner.  Least Cost Method- The Least Cost Method is another method used to obtain the initial feasible solution for the transportation problem. Here, the allocation begins with the cell which has the minimum cost. The lower cost cells are chosen over the higher-cost cell with the objective to have the least cost of transportation.  Approximation Method- A method for finding a first feasible solution to a transportation problem. The procedure begins by finding the two lowest cost cells for each row and column in the transportation problem array. 4.6 LEARNING ACTIVITY 1. Express the given transportation problem as an LP problem. 95 CU IDOL SELF LEARNING MATERIAL (SLM)

___________________________________________________________________________ ___________________________________________________________________________ 2. Find the optimum transportation schedule and minimum total cost of transportation. ___________________________________________________________________________ ___________________________________________________________________________ 4.7 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. What is a transportation algorithm? 2. What are the methods of basic feasible solutions? 3. When is it suitable to use Vogel’s approximation method? 4. What kind of transportation problem gets solved through linear programming? 5. What is the optimal solution? Long Questions 1. What are the steps involved in the transportation algorithm? 2. Write all the steps involving the north- west corner method? 3. Analyse the steps involving Vogel’s approximation method? 4. What is the concept behind the application of linear programming to sort out transport problems? 5. Explain least cost method. B Multiple Choice Questions 1. Who did formulate the transport problem first? a. Hitchcock a. Monge b. Hitchaxic 96 CU IDOL SELF LEARNING MATERIAL (SLM)

c. George B. Dantizig 2. Which is not an objective of transport problem? a. Minimize the cost of shipping b. Minimize the profit of shipping c. Minimize the transportation distance d. Quicken the supply of materials 3. Which is not a step of transportation algorithm? a. Balance the transportation problem b. Compute an initial basic feasible solution c. Miscompute the values d. Compute the reduced cost coefficient 4. Which are solutions related to transport problems? a. Feasible solution b. Optimal solution c. Degeneracy d. All of these 5. Which is not a step of the north-west corner method? a. Allocate the minimum amount allowable by the supply and demand constraints b. If a column (or row) is satisfied, cross it out c. Adjust supply and demand for the non-crossed out rows and columns d. Allocate the maximum feasible amount to the first available non-crossed out element in the next column Answers 1-a 2-b 3-c 4-d 5-a 4.8 REFERENCES Reference  Essay on Transportation Problem| Operations Research | Linear Programming (engineeringenotes.com) 97 CU IDOL SELF LEARNING MATERIAL (SLM)

 1 (knust.edu.gh)  (1) New Messages! (mygreatlearning.com) Textbooks  Andersion. R.D, Sweeney.J.D, Williams.A.T&Martin.K. R (2010).: An introduction to Management Science: Quantitative Approach to Decision.  Eykhoff, (1974): System Identification: Parameter and State Estimation, Wiley & Sons,  Kumar .T, and Schilling S.M (2010). : Comparison of optimization Technique in large scale Transportation Problem Websites  [PDF] Transportation Problem in Operational Research - Download (gatexplore.com)  Transportation Problem - Definition and formulation, Structure | Operations Research (brainkart.com)  Transportation Problem (hithaldia.in)  5_Transportation.pdf (ehu.eus) Transportation Problem: A Special Case for Linear Programming Problems (oregonstate.edu) 98 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 5 –TRANSPORTATION PROBLEMS PART 2 STRUCTURE 5.0 Learning Objectives 5.1 Introduction 5.2 NWCM 5.3 LCM and VAM 5.4 Optimality Tests 5.5 MODI Method 5.6 Stepping Stone Technique 5.7 Summary 5.8 Keywords 5.9 Learning Activity 5.10 Unit End Questions 5.11 References 5.0 LEARNING OBJECTIVES After studying this unit, you will be able to:  Identify the best method for solving transport problems.  Explain why MODI method is mostly used.  Differentiate between LCM and VAM.  Appreciate the advantages of stepping stone technique. 5.1 INTRODUCTION The transportation problem is a special type of LPP where the objective is to minimise the cost of distributing a product from a number of sources or origins to a number of destinations. Sources: Distributing any commodity from any group of supply centres Destinations: Sending to any group centres Objectives: To find out optimum transportation schedule keeping in mind cost of transportation to be minimized. Characteristics of Transportation Problems 99 CU IDOL SELF LEARNING MATERIAL (SLM)

The Requirements Assumption: – Each source has a fixed supply of units, where this entire supply must be distributed to the destinations. – Each destination has a fixed demand for units, where this entire demand must be received from the sources. The Feasible Solutions Property: – A transportation problem will have feasible solutions if and only if the sum of its supplies equals the sum of its demands. The Cost Assumption: – The cost of distributing units from any particular source to any particular destination is directly proportional to the number of units distributed. – This cost is just the unit cost of distribution times the number of units distributed. Assumptions of Transportation Problems Transportation of commodity/terms: the model assumes that the commodities are being transported from the source to the destination very conveniently. The certainty of per unit transportation cost: obviously there is some transportation cost between the sources and destination. Independent per cost unit: per cost unit does not depend on the quantity being transported from source to destination. A number of units being transported are proportional to the transportation cost of any route. The objective is to minimize the transportation cost for transporting commodities between two places. Though transportation problems are linear programming problems, they are not solved using simplex algorithm for the following two reasons: 1. The balanced transportation problem has all its constraints in equation form and since ∑ai = ∑bj, the system pf equations (constraints) is linearly dependent. This gives rise to degeneracy and limitations of the simplex algorithm resulting in more iteration for degenerate problems are well known. 2. The balanced transportation problem by its structure allows the formation of good basic feasible solutions that are close to optimal, while simplex starts with a basic feasible solution that is quite far away from the optimal. Balanced transportation problems are solved by creatin an initial basic feasible solution, that is close to optimum and then reaching the optimum in very few iterations. We discuss three methods to create basic feasible solutions to balanced transportation problems. These are: i. North West Corner rule ii. Minimum cost method iii. Vogel’s approximation method 100 CU IDOL SELF LEARNING MATERIAL (SLM)