simplex method case study

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to  upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

• We're Hiring!
• Help Center

Application of the simplex method on profit maximization in Baker's Cottage

2022, Indonesian Journal of Electrical Engineering and Computer Science

Linear programming is an operational research technique widely used to identify and optimize management decision. Its application encourages businesses to increase their output. Instead, however, many organizations most commonly adopt the trial-and-error method. As such, companies find it challenging to distribute scarce resources in a manner that maximizes profit. This study focuses on implementing linear programming to optimize the profit of a manufacturing sector based on the optimized (best possible, efficient) use of raw materials. Our study uses the data gathered on five market bread types from Baker's Cottage reports, i.e., chicken floss, spicy floss, Frank Cheese, Mexico bun, and doughnut. This attribute has been recognized as a linear programming problem mathematically built that was solved using Excel software. The result showed that the Baker's Cottage unit had to produce 332 loaves of Chicken Floss and 196 loaves of Frank Cheese, as these products objectively contributed to the profit. In contrast, other types of bread did not have to be produced, as their value turned to zero to achieve the maximum monthly profit.

RELATED TOPICS

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024

Simplex Method for Solution of L.P.P (With Examples) | Operation Research

After reading this article you will learn about:- 1. Introduction to the Simplex Method 2. Principle of Simplex Method 3. Computational Procedure 4. Flow Chart.

Introduction to the Simplex Method :

Simplex method also called simplex technique or simplex algorithm was developed by G.B. Dantzeg, An American mathematician. Simplex method is suitable for solving linear programming problems with a large number of variable. The method through an iterative process progressively approaches and ultimately reaches to the maximum or minimum values of the objective function.

Principle of Simplex Method :

It has not been possible to obtain the graphical solution to the LP problem of more than two variables. For these reasons mathematical iterative procedure known as ‘Simplex Method’ was developed. The simplex method is applicable to any problem that can be formulated in-terms of linear objective function subject to a set of linear constraints.

ADVERTISEMENTS:

The simplex method provides an algorithm which is based on the fundamental theorem of linear programming. This states that “the optimal solution to a linear programming problem if it exists, always occurs at one of the corner points of the feasible solution space.”

The simplex method provides a systematic algorithm which consist of moving from one basic feasible solution to another in a prescribed manner such that the value of the objective function is improved. The procedure of jumping from vertex to the vertex is repeated. The simplex algorithm is an iterative procedure for solving LP problems.

It consists of:

(i) Having a trial basic feasible solution to constraints equation,

(ii) Testing whether it is an optimal solution,

(iii) Improving the first trial solution by repeating the process till an optimal solution is obtained.

Computational Procedure of Simplex Method :

The computational aspect of the simplex procedure is best explained by a simple example.

Consider the linear programming problem:

Maximize z = 3x 1 + 2x 2

Subject to x 1 + x 2 , ≤ 4

x 1 – x 2 , ≤ 2

x 1 , x 2 , ≥ 4

< 2 x v x 2 > 0

The steps in simplex algorithm are as follows:

Formulation of the mathematical model:

(i) Formulate the mathematical model of given LPP.

(ii) If objective function is of minimisation type then convert it into one of maximisation by following relationship

Minimise Z = – Maximise Z*

When Z* = -Z

(iii) Ensure all b i values [all the right side constants of constraints] are positive. If not, it can be changed into positive value on multiplying both side of the constraints by-1.

In this example, all the b i (height side constants) are already positive.

(iv) Next convert the inequality constraints to equation by introducing the non-negative slack or surplus variable. The coefficients of slack or surplus variables are zero in the objective function.

In this example, the inequality constraints being ‘≤’ only slack variables s 1 and s 2 are needed.

Therefore given problem now becomes:

The first row in table indicates the coefficient c j of variables in objective function, which remain same in successive tables. These values represent cost or profit per unit of objective function of each of the variables.

The second row gives major column headings for the simple table. Column C B gives the coefficients of the current basic variables in the objective function. Column x B gives the current values of the corresponding variables in the basic.

Number a ij represent the rate at which resource (i- 1, 2- m) is consumed by each unit of an activity j (j = 1,2 … n).

The values z j represents the amount by which the value of objective function Z would be decreased or increased if one unit of given variable is added to the new solution.

It should be remembered that values of non-basic variables are always zero at each iteration.

So x 1 = x 2 = 0 here, column x B gives the values of basic variables in the first column.

So 5, = 4, s 2 = 2, here; The complete starting feasible solution can be immediately read from table 2 as s 1 = 4, s 2 , x, = 0, x 2 = 0 and the value of the objective function is zero.

Flow Chart of Simplex Method :

• Mission & Scope
• Editorial Board
• Peer-Review Policy
• Publication Ethics Policy
• Journal Policies
• Join as Reviewer
• Conference Partners
• Call for Papers
• Journal Statistics – 2023-2024
• Submit Manuscript
• Journal Charges (APC)
• Register as Volunteer
• Upcoming Conferences
• CONFERENCE PROCEEDINGS
• Thesis Archive
• Thesis Publication FAQs
• Thesis Publication Charges
• Author Login
• Reviewer Login

Volume 02, Issue 06 (June 2013)

Optimization of workplace layout by using simplex method: a case study.

• Article Download / Views: 368
• Total Downloads : 756
• Authors : Kaustubh N. Kalaspurkar, Ravikant V. Paropate, Kapil B. Salve, Vaibhav R. Pannase
• Paper ID : IJERTV2IS60370
• Volume & Issue : Volume 02, Issue 06 (June 2013)
• Published (First Online): 26-06-2013
• ISSN (Online) : 2278-0181
• Publisher Name : IJERT

Optimization Of Workplace Layout By Using Simplex Method: A Case Study Kaustubh N. Kalaspurkar1, Ravikant V. Paropate2, Kapil B. Salve3, Vaibhav R. Pannase4 Department of Mechanical Engineering1, 2, 3,4

Jagadamba College of Engineering & Technology, Yavatmal1,4

Jawaharlal Darda Institute of Engineering & Technology, Yavatmal.2,3.

Now a day there is competition in market to make available the product in a optimum quantity and within a forecasted dates with a good quality. To fulfill this condition we need to install new quality tools available in market which are costly and forced to uninstall the unnecessary operations. In this paper the case study is discussed which helps to optimize the workplace layout by using method study & Ergonomics for the human comfort. Case study is carried out on Assembly of rear axle carrier of a tractor from Automobile Industry.

Key word:- Time and Motion Study, Workstation Design, Ergonomics, Rear Axle Carrier, Stop Watch.

INTRODUCTION:-

The productivity improvement is the vital part of manufacturing system to satisfy the market demand which will be based on the efficiency of man i.e. operator is highly depending on how well the workstation is designed ergonomically, where as the efficiency of machine is more depends upon its utilization. Whereas the efficiency of both i.e. man and machine is highly affected by methodology adopted in the manufacturing system. As unnecessary and unproductive movements and operation will cause the fatigue to operator as well as improper machine utilization. To analyzed the task in the manufacturing, proper production scheduling is very important.

Time study and motion study is widely used in industries. Time study is defined as It is a work measurement technique for recording the times and rates of working for the elements of a specified job carried out under specified conditions, and for analyzing the data so as to determine the time necessary for carrying out the job at a defined level of performance. Motion study is defined as It is the systematic recording and critical examination of existing and proposed ways of doing work, as a means of developing and applying easier and more effective methods and reducing costs. In the present work, assembly task at one of the leading tractor manufacturing company in India is studied to achieve optimum performance evaluation of the productivity. In the present work the study regarding the workplace layout, number of components involved, movement of workers, available tools and their location etc. were analyzed.

This layout critically analyzed and found the scope of implementation. In reduction to time study we have again analyzed the system in total and divided into parts and tried to record the time for every operation. In flow process chart the analysis of work station has been carried out and in this analysis we found that in critical analysis helped us to remove unwanted activities. Work ergonomics study revealed that the Heart rates and total comfort of worker is higher level as compared to existing one.

Lastly we have tried to check our results through simulation in which we have used Simulation Software and found very satisfactory and incoming result that our suggested techniques reduces time and improve the productivity.

LITERATURE REVIEW:-

A significant amount of research work on Time study and Motion study, Modeling and Simulation, Productivity improvement and Ergonomic study has been published Mr. Gurunath V Shinde 1, Prof.V.S.Jadhav *2, investigate lots of money on man, machine, material, method (4m),improving ergonomics of workplaces is cost saving. Ergonomics found great need when market demand is high and manufacturers need more output within short period. This study was conducted on assembly workstation of welding shop. This work was conducted on an assembly station in welding shop. The shop was facing problem of less efficiency of workers due to poor ergonomics and in some severe cases hazardous health issues are found. This work was conducted on an assembly station in welding shop. The shop was facing problem of less

efficiency of workers due to poor ergonomics and in some severe cases hazardous health issues are found [1]. Baba Md Deros 1 , Nor Kamaliana Khamis 1,Ahmad Rasdan Ismail 2, suggested the concept of high demand for products in the manufacturing industry had driven the human workers to work faster and adapt to their un-ergonomically designed workstation. This study was conducted at an automotive component manufacturer and shows current assembly workstation at company a need to be redesign to eliminate awkward postures and anthropometric mismatches to lower MSDs problem and improve productivity among assembly workers [2]. Mr. Gurunath V. Shinde 1, Prof.V.S.Jadhav 2, identify complex tasks which lead to less efficiency of worker. Various approaches had been develop including direct observations, questionnaires, interview, etc. for ergonomic evaluation of workstation. This technique of ergonomic analysis is very useful to identify complex tasks and root cause of each complex task which is useful in simplifying it and hence to reduce stress on various workers movements [3]. Ibrahim H. Garbie, investigate the effects of assembly of a product on operator performance. Workstations for assembly tasks should be designed so that any operator can adjust to his/her comfort to relieve stress and improve performance. The main contribution of this work has how to measure the production rate of manual assembly lines based on design ergonomically assembly workstation [4]. Paul

H.P. Yeowa,_, Rabindra Nath Senb, improving productivity and quality, increasing revenue and reducing rejection cost of the manual component insertion (MCI) lines in a printed circuit assembly (PCA) factory. Live experiments were conducted on production lines. Eleven problems were identified, i.e., long search for materials from the stores, unproductive manual component counting, obstructions during insertions, component fall-off while the PCA board was traveling on a U-shaped conveyor, etc. increasing profit for the company owners, providing price reductions to the customers, and giving large bonus and annual increment to their employees [5].

Ashraf A. Shikdar, Mohamed A. Al-Hadhrami, conducted Smart workstation design: an ergonomics and methods engineering approach and this research was to design and develop a smart workstation for performing industrial assembly tasks. A fully adjustable ergonomically designed workstation was developed [6]. Javier Santos_, Jose M. Sarriegi, Nicola´ s Serrano, Jose M. Torres, conducted Using ergonomic software in non-repetitive manufacturing processes: A case study This paper uncovers, by means of a case study based on a real process, the advantages and the practical barriers involved in the implementation of 3D simulation tools in SMEs. The chosen case study is based on a non-repetitive manufacturing process [7]. D.

Battini a,*, M. Faccio b, A. Persona a, F. Sgarbossa a, conducted New methodological framework to improve productivity and ergonomics in assembly system design this work analyse how ergonomics and assembly system design techniques are intimately related. It also develops a new theoretical framework to assess a concurrent engineering approach to assembly systems design problems, in conjunction with an ergonomics optimization of the workplace. This work provides an extremely valuable methodological framework to companies who recognize the link between ssembly and ergonomics [8]. Adi Saptari, Wong Soon Lai, Mohd. Rizal Salleh, conducted Jig Design, Assembly Line Design and Work Station Design and their Effect to Productivity the most productive assembly line design which achieved the lowest assembly time is the combination of one operator, with rectangular jig and work station design sitting. This assembly station determines the sequences of operations to manufacture of components as well as the final product [9]. Francesco Longo Giovanni Mirabelli Enrico Papoff, conducted

EFFECTIVE DESIGN OF AN ASSEMBLY LINE USING MODELING & SIMULATION

invented work regarding the effective design of an assembly line for heaters production. The effective design of assembly line workstations by means of integration between ergonomic analyses and Modeling & Simulation. Modeling & simulation in combination with ergonomic analyses is a powerful tool for analyzing assembly line and providing effective design and optimal ergonomic solutions [10].

For problem identification time study and motion study technique is used. Using this time study and motion study technique time required for each operation is calculated by using stop watch technique for existing setup. After calculating of time for each operation, flow process chart has been prepared. From study of flow process chart the unwanted activity where critically analyzed.

Work study, as it stands today to provide us with a scientific approach to investigation into all form of work, with a view to increase productivity. While many techniques for raising productivity are available today that qualify as a scientific approach, not all of them fall under domain of work study. It is one of the tools in the managers tool kit. This is particularly true for work study where the major focus is the investigation of human work, with an aim to improve the efficiency of the same.

Total parts for assembly station 1

Table 1:- Total Parts for Station 1

This study was conducted at a workstation for the assembly of Rear Axle Carrier. This assembly operation involves 27 components. The entire component was assembled by manual process. The total assembly process was carried out on three different process stations. The assembly of the component of each as follows:

Total parts for assembly station 2

Table 2:- Total Parts for Station 2

Total parts for assembly station 3

Table 3:- Total Parts for Station 3 Total Part for Station 1, 2 & 3:- (6+13+8) = 27.

Assembly process consist of parts of different sizes and weight kept in different bins around the workplace four operators, one operator on workstation 1, two operators on workstation 2 and one operator workstation 3 are working. The main focus of the study is to find out the task of assembly which leads to high cycle time. Hence each operation involved in the assembly where analyzed critically using time study and motion study. Stop watch technique was used to determine the time for each activity.

ANALYSIS OF WORK PLACE LAYOUT

The existing layout for the assembly of Rear Axle Carrier (RAC) is as shown in Figure 1.

Fig. 1:- Rear Axle Carrier Assembly of Tractor (Existing)

As shown in Figure No. 1 it consists of three in line assembly workstation namely station 1, 2 and 3. Material flow was successive from station 1 to station 2 then from station 2 to station

3. To assist the operator for the material flow roller conveyor (manually operated), and cranes are used.

Assembly operation at station 1 involves the assembly of 6 components as shown in table no.1 out of which retainers are stores in the retainer rack which was located just behind the operator as shown in Fig. No.1. Also the oil seal, gasket, bearing and the axle are located surrounding the workplace as shown in Fig. No.1. During each assembly operator has to move at each of these locations and collects the parts for the assembly. Similarly the components required assembly station 2 and 3 is to be connected by the operator from the various storage locations surrounding the workplace as shown in the Fig. No.1.

FLOW PROCESS CHARTS

From the above workplace layout and the nature of assembly involved requires several activity at each station 1, 2 and 3. For example at assembly station 1 total 51 activities of the time 6.04 min are involved. At assembly station 2 total 38 activities of the time 5.21 min and 24 activities of the 4.02 min are involves at station 3. Accordingly the flow process chart of the material for each of the assembly station is developed. The sample flow process chart for station 1 is shown in Table No. 4.

FLOW PROCESS CHART – MATERIAL TYPE (STATION 1)

TABLE 4:- Sample Flow Process Chart – Material Type (Assembly Station 1)

Similarly material flow process chart for the assembly station 2 and assembly station 3 is also developed. In the same way for Assembly station 1 total 8 readings are taken and the mean is taken as follows:

The mean time required per day is as follows

Table 5:- Eight reading mean time for assembly station 1 Total mean time required for station 1 = 5.633 min.

Similarly mean time required for the assembly station 2 and assembly station 3 are determined.

Mean Total time required for the operation =

= Time of Station 1 + Time of Station 2 + Time of Station 3

= 5.633 + 4.825 + 3.513

= 14.37 min.

CRITICAL ANALYSIS BY USING FLOW PROCESS CHARTS

From the above developed flow process chart each of the activity involved at all the 3 station were critically analyzed for the evaluation of the purpose of the each activity. This

evaluation is done by finding the answers to the Primary and Secondary questions such as what is achieved through that activity, is that activity is necessary, can it be eliminated, what else might be done etc. from this critically analysis unnecessary and unproductive activities for the assembly operation at each of the workstation is determined. Accordingly the critical analysis charts for unnecessary and unproductive activities are developed. The sample critical analysis chart for station1 in table no. 6. Similarly critical analysis chart for the assembly station 2 is also developed.

TABLE 6:- Sample Critical Analysis Chart (Assembly Station 1)

PROPOSED IMPROVEMENT IN THE WORKPLACE LAYOUT

On the critical analysis for assembly station 1 it was found that activity no. 2, 3, 4, 5, 6, 39, and 40 where unnecessary and can be replaced by making certain suitable arrangement in the workplace layout. For example activity no. 2 to 6 involves movement of the worker from the workstation to the storage location for picking and transporting retainers and oil seals to assembly station 1. This amount of the worker can be eliminated by gravity conveyor for the retainer located near the station 1 which will make constant supply of retainer at the assembly station; similarly special storage bin for the oil seal can be located within the reach of the operator near the assembly station 1. This will eliminate the need of movement of worker for each assembly operation and will result in saving of time. Similarly activity 39 and 40 involved movement and pickup of the bearing of the worker. This unnecessary movement can be eliminated in similar way by making provision of storage bin of bearing nearer to assembly station 1. Similarly for the station 2 and station 3 unnecessary activities were found out and they are eliminated by making required alteration in the workplace. This activity was consuming the total time of 1.481 min. These are tabulated below:

Previous layout:-

From this table it is seen that

Table 7:- Existing layout unnecessary operation for station 1 and Station 2

Previous layout can be reduced by making the suitable arrangements as:-

By changing previous process as

Table 8:- Existing layout unnecessary operation for station 1 and Station 2 After critical analysis total mean time required as given in the table:-

Table 9:- Eight reading mean time for assembly station 1 and assembly station 2 After critical analysis total mean time required for station 1, 2 and 3 = 1.481min.

From the above suggested changes the proposed improved workplace layout is as shown in Fig. No. 2.

Fig. 2:- Rear Axle Carrier Assembly of Tractor (Proposed)

Total time for whole activity by using stop watch = 14.37 min. Total time after critical analysis which can be reduced = 1.48 min. Time can be reduced = 14.37 – 1.48 = 12.49 min.

Previous total time for whole activity (Company Data) = 13.37 min.

Total time save after implementing the suggestion = 13.37 – 12.49 = 48 sec.

Total time saves for 8 hour shift:-

Total time save after implementing the suggestion for one RAC assembly = 48 sec.

Total time save for assembly of two RAC assembly = 1.36 min.

For 8 hour shift 70 tractors assemble.

Total time optimize (1.36 x 70) = 1 hour 35 min time save for 8 hour shift. ERGONOMICS CONSIDERATION

It is scientific, in that Ergonomists measure human characteristics and human function, and establish the way that human body and human mind work. It is also technological, in that the results of scientific work in the human sciences are applied by ergonomists in the solution of practical problems in the design and manufacture of products and system.

For Ergonomics we have count the Heart Rate of worker. From Heart Rate reading, by using formula we calculate Oxygen Consumption and Energy Consumption reading of worker for Existing Layout. After making some improvement in layout of Existing Rear Axle Carrier (RAC). There is reduction in Heart Rate count and accordingly there is less Oxygen and Energy Consumption. For suggested Proposed Layout of Rear Axle Carrier (RAC). All these location of the suggested bins are kept within the reach of the operator by considering the anthropometric dimension of the operator as shown in Fig. No.3.

Fig. 3:- Recommended working distance for the arms

For the ergonomic consideration we count the heart rate reading of a worker for both the condition ,after counting it is observed that in the suggested improvement condition the heart rate readings are minimum than previous. Following graph shows the decrease in heart rate of suggested changes in workplace layout of RAC assembly.

Fig. 4:- Existing condition heart rate reading

Fig. 5:- Proposed condition heart rate reading

OPTIMIZATION THROUGH SIMPLEX METHOD

In the simplex method we have optimize the time for existing work layout and the proposed work layout. The simplex method in which we have obtained the result for minimizing time and improve the production. This result calculated by using simplex method for existing layout and proposed layout.

The optimal solution for existing layout is reached with S1 = 0, X1 = 5.633, and S3 = 0. Zmax = 0 X 5.39 + 5.633 X 2.93 + 0 X 7.78

= 16.50 ..(For existing layout completing operation for assembly station 1 maximum time required is 16.50.)

The optimal solution for proposed layout is reached with X1 = 4.5, X2 = 4.32, and S3 = 0. Zmax = 4.5 X 1.003 + 4.32 X 2.06 + 0 X 1.48

= 13.41 ..(For proposed layout completing operation for assembly station 1 and assembly station 2 maximum time required is 13.41.)

For existing layout completing operation for assembly station 1 maximum time required is Zmax = 16.50 and for proposed layout completing operation for assembly station 1 and assembly station 2 maximum time required is Zmax = 13.41. By solving optimization through simplex method we have tried for increasing the production rate for proposed layout.

COMPARISON BETWEEN EXISTING LAYOUT AND PROPOSE LAYOUT BY USING SIMPLEX METHOD

In this present work we have suggested to incorporate new improved layout in which the production rate per day for assembling component for assembly station one and assembly station two is maximize up to certain level without disturbing another assembly station or production layout unit. In this work we have found that the production rate is very much depends on travelling time of assemble component. So by reducing the extra time and extra effort we have found this result for the optimize layout. Overall increases the production rate as compare to existing one.

The time consume in existing layout is maximum as where the time consume in proposed layout is minimum up to a certain level. The existing layout required the maximum time of Zmax

= 16.50 while for proposed layout it would be found Zmax = 13.41. CONCLUSION

In my project work in which I have theoretically studied time study, motion study and ergonomics on the leading tractor manufacturing company. The result I found in critical analysis is that by the time study and motion study some of the unnecessary operations are combined and modified the flow process in proposed one helps us to reduce time by certain modification in nearby assembly station.

These said modifications in workplace layout are designed ergonomically as well. With this improved layout the total time 48 sec per cycle was found to be reduced. Hence the above result helped us to reduce time and motion ultimately improves production.

LITERATURE CITED:-

Mr. Gurunath V Shinde1, Prof. V. S. Jadhav , Ergonomic analysis of an assembly workstation to identify time consuming and fatigue causing factors using application of motion study, International Journal of Engineering and Technology (IJET), ISSN : 0975-4024 Vol 4 No 4 Aug Sep 2012.

1Baba Md Deros, 1Nor Kamaliana Khamis, 2Ahmad Rasdan Ismail, , An Ergonomics Study on Assembly Line Workstation Design, American Journal of Applied Sciences 8 (11): 1195- 1201, 2011, ISSN 1546-9239, © 2011 Science Publications.

Mr. Gurunath V. Shinde1, Prof. V. S. Jadhav2 , A Computer based novel approach of ergonomic study and analysis of a workstation in a manual process, International Journal of Engineering Research & Technology (IJERT) Vol. 1 Issue 6, August 2012, ISSN: 2278-0181.

Ibrahim H. Garbie, AN EXPERIMENTAL STUDY ON ASSEMBLY WORKSTATION CONSIDERING ERGONOMICALLY ISSUES, Proceedings of the 41st International Conference on Computers & Industrial Engineering.

Yeow P.H.P., Sen R.N., (2006), Productivity and quality improvements, revenue increment, and rejection cost reduction in the manual component insertion lines through the application of ergonomics International Journal of Industrial Ergonomics 36:367377.

Shikdar A., Al-Hadhrami M.,( 2007 ). Smart workstation design: an ergonomics and methods enginering approach. International Journal of Industrial and Systems Engineering. 2(4), 363-374.

Santos J, Sarriegi J.M.( 2007). Using ergonomic software in non-repetitive manufacturing processes: A case study. International Journal of Industrial Ergonomics 37: 267-275.

Battini D., Faccio M., (2011), New methodological framework to improve productivity and ergonomics in assembly system design, International Journal of industrial ergonomics 41 (30- 32).

Adi Saptari, Wong Soon Lai, Mohd. Rizal Salleh, Jig Design, Assembly Line Design and Work Station Design and their Effect to Productivity, 2011 Jordan Journal of Mechanical and Industrial Engineering. All rights reserved – Volume 5, Number 1 (ISSN 1995-6665)

Francesco Longo, Giovanni Mirabelli, Enrico Papoff, EFFECTIVE DESIGN OF AN ASSEMBLY LINE USING MODELING & SIMULATION, Proceedings of the 2006 Winter Simulation Conference, L. F. Perrone, F. P. Wieland, J. Liu, B. G. Lawson, D. M. Nicol, and R.

M. Fujimoto, eds.

Leave a Reply

You must be logged in to post a comment.

Chapter: Operations Research: An Introduction : The Simplex Method and Sensitivity Analysis

Special cases in the simplex method.

SPECIAL CASES IN THE SIMPLEX METHOD

This section considers four special cases that arise in the use of the simplex method.

1.      Degeneracy

2.      Alternative optima

3.      Unbounded solutions

4.      Nonexisting (or infeasible) solutions

Our interest in studying these special cases is twofold: (1) to present a theoretical explanation of these situations and (2) to provide a practical interpretation of what these special results could mean in a real-life problem.

1. Degeneracy

In the application of the feasibility condition of the simplex method, a tie for the mini-mum ratio may occur and can be broken arbitrarily. When this happens, at least one basic variable will be zero in the next iteration and the new solution is said to be degenerate.

There is nothing alarming about a degenerate solution, with the exception of a small theoretical inconvenience, called cycling or circling, which we shall discuss short-ly. From the practical standpoint, the condition reveals that the model has at least one redundant constraint. To provide more insight into the practical and theoretical im-pacts of degeneracy, a numeric example is used.

Example 3.5-1        (Degenerate Optimal Solution)

Given the slack variables x 3 and x 4 , the following tableaus provide the simplex iterations of the problem:

In iteration 0, x 3 and x 4 tie for the leaving variable, leading to degeneracy in iteration 1 because the basic variable x 4 assumes a zero value. The optimum is reached in one additional iteration.

What is the practical implication of degeneracy? Look at the graphical solution in Figure 3.7. Three lines pass through the optimum point (x 1 = 0, x 2 = 2). Because this is a two-dimensional problem, the point is overdetermined and one of the constraints is redundant? In practice, the mere knowledge that some resources are superfluous can be valuable during the implementa-tion of the solution. The information may also lead to discovering irregularities in the construc-tion of the model. Unfortunately, there are no efficient computational techniques for identifying the redundant constraints directly from the tableau.

From the theoretical standpoint, degeneracy has two implications. The first is the phe-nomenon of cycling or circling. Looking at simplex iterations 1 and 2, you will notice that the objective value does not improve (z = 18). It is thus possible for the simplex method to enter a repetitive sequence of iterations, never improving the objective value and never satisfying the optimality condition (see Problem 4, Set 3.5a). Although there are methods for eliminat-ing cycling, these methods lead to drastic slowdown in computations. For this reason, most LP codes do not include provisions for cycling, relying on the fact that it is a rare occurrence in practice.

The second theoretical point arises in the examination of iterations 1 and 2. Both iterations, though differing in the basic-nonbasic categorization of the variables, yield identical values for all the variables and objective value-namely,

x 1 =0, x 2 = 2, x 3 = 0, x 4 =0,  z=18

Is it possible then to stop the computations at iteration 1 (when degeneracy first appears), even though it is not optimum? The answer is no, because the solution may be temporarily de-generate as Problem 2, Set 3.5a demonstrates.

PROBLEM SET 3.5A

*1. Consider the graphical solution space in Figure 3.8. Suppose that the simplex iterations start at A and that the optimum solution occurs at D. Further, assume that the objective function is defined such that at A, x I enters the solution first.

a. Identify (on the graph) the corner points that define the simplex method path to the optimum point.

b. Determine the maximum possible number of simplex iterations needed to reach the optimum solution, assuming no cycling.

2. Consider the following LP:

a. Show that the associated simplex iterations are temporarily degenerate (you may use TORA for convenience).

b. Verify the result by solving the problem graphically (TORA's Graphic module can be used here).

3. TORA experiment. Consider the LP in Problem 2.

a. Use TORA to generate the simplex iterations. How many iterations are needed to reach the optimum?

b. Interchange constraints (1) and (3) and re-solve the problem with TORA. How many iterations are needed to solve the problem?

c. Explain why the numbers of iterations in (a) and (b) are different.

4. TORA Experiment Consider the following LP (authored by E.M. Beale to demonstrate cycling):

From TORA's SOLVEIMODIFY menu, select Solve => Algebraic. => Iterations => All-slack. Next, "thumb" through the successive simplex iterations using the command Next iteration (do not use All iterations, because the simplex method will then cycle in-definitely). You will notice that the starting all-slack basic feasible solution at iteration 0 will reappear identically in iteration 6. This example illustrates the occurrence of cycling in the simplex iterations and the possibility that the algorithm may never converge to the optimum solution.

It is interesting that cycling will not occur in this example if all the coefficients in this LP are converted to integer values by using proper multiples (try it!).

2. Alternative Optima

When the objective function is parallel to a nonredundant binding constraint (i.e., a constraint that is satisfied as an equation at the optimal solution), the objective function can assume the same optimal value at more than one solution point, thus giving rise to alternative optima. The next example shows that there is an infinite number of such solutions. It also demonstrates the practical significance of encoun-tering such solutions.

Example 3.5-2    (Infinite Number of Solutions)

Figure 3.9 demonstrates how alternative optima can arise in the LP model when the objec-tive function is parallel to a binding constraint. Any point on the line segment Be represents an alternative optimum with the same objective value z == 10.

The iterations of the model are given by the following tableaus.

Iteration 1 gives the optimum solution x 1 = 0, x 2 = 5/2 and z = 10, which coincides with point B in Figure 3.9. How do we know from this tableau that alternative optima exist? Look at the z-equation coefficients of the nonbasic variables in iteration 1. The coefficient of nonbasic x 1 is zero, indicating that x 1 can enter the basic solution without changing the value of z, but causing a change in the values of the variables. Iteration 2 does just that-letting x 1 enter the basic solution and forcing x 4 to leave. The new solution point occurs at C(x I = 3, x 2 = 1, z = 10). (TORA's Iteratioris option allows determining one alternative optimum at a time.)

The simplex method determines only the two corner points Band C. Mathematically, we can determine all the points (x 1 , x 2 ) on the line segment Be as a nonnegative. weighted average of points Band C. Thus, given

Remarks. In practice, alternative optima are useful because we can choose from many solutions without experiencing deterioration in the objective value. For instance, in the present ex-ample, the solution at B shows that activity 2 only is at a positive level, whereas at C both activities are positive. If the example represents a product-mix situation, there may be advan-tages in producing two products rather than one to meet market competition. In this ease, the so-lution at C may be more appealing.

PROBLEM SeT 3.5B

*1. For the following LP, identify three alternative optimal basic solutions, and then write a general expression for all the nonbasic alternative optima comprising these three basic solutions.

Note: Although the problem has more than three alternative basic solution optima, you are only required to identify three of them. You may use TORA for convenience.

2. Solve the following LP:

From the optimal tableau, show that all the alternative optima are not corner points (i.e., nonbasic). Give a two-dimensional graphical demonstration of the type of solu-tion space and objective function that will produce this result. (You may use TORA for convenience.)

3. For the following LP, show that the optimal solution is degenerate and that none of the alternative solutions are corner points (you may use TORA for convenience).

3. Unbounded Solution

In some LP models, the values of the variables may be increased indefinitely without violating any of the constraints-meaning that the solution space is unbounded in at least one variable. As a result, the objective value may increase (maximization case) or decrease (minimization case) indefinitely. In this case, both the solution space and the optimum objective value are unbounded.

Unboundedness points to the possibility that the model is poorly constructed. The most likely irregularity in such models is that one or more nonredundant constraints have not been accounted for, and the parameters (constants) of some constraints may not have been estimated correctly.

The following examples show how unboundedness, in both the solution space and the objective value, can be recognized in the simplex tableau.

In the starting tableau, both x l and x 2 have negative z-equation coefficients. Hence either one can improve the solution. Because x l has the most negative coefficient, it is normally selected as the entering variable. However, all the constraint coefficients under x 2 (Le., the denominators of the ratios of the feasibility condition) are negative or zero. This means that there is no leaving variable and that x 2 can be increased indefinitely without violating any of the constraints (compare with the graphical interpretation of the minimum ratio in Figure 3.5). Because each unit increase in x l will increase z by 1, an infinite increase in x 2 leads to an infinite increase in z.

Thus, the problem has no bounded solution. This result can be seen in Figure 3.10. The solution space is unbounded in the direction of x 2 , and the value of z can be increased indefinitely. Remarks. What would have happened if we had applied the strict optimality condition that 3.5 calls for x l to enter the solution? The answer is that a succeeding tableau would eventually have led to an entering variable with the same characteristics as x 2 . See Problem 1, Set3.5c.

PROBLEM SET 3.5C

1. TORA Experiment. Solve Example 3.5-3 using TORA's Iterations option and show that even though the solution starts with x l as the entering variable (per the optimality condition), the simplex algorithm will point eventually to an unbounded solution.

*2. Consider the LP:

a. By inspecting the constraints, determine the direction (x I . x 2 , or x 3 ) in which the solution space is unbounded.

b. Without further computations, what can you conclude regarding the optimum objective value?

3. In some ill-constructed LP models, the solution space may be unbounded even though the problem may have a bounded objective value. Such an occurrence can point only to irregularities in the construction of the model. In large problems, it may be difficult to detect unboundedness by inspection. Devise a procedure for determining whether or not a solution space is unbounded.

4. Infeasible Solution

LP models with inconsistent constraints have no feasible solution. This situation can never occur if all the constraints are of the type ≤ with nonnegative right-hand sides because the slacks provide a feasible solution. For other types of constraints, we use artificial variables. Although the artificial variables are penalized in the objective function to force them to zero at the optimum, this can occur only if the model has a feasible space. Otherwise, at least one artificial variable will be positive in the optimum iteration. From the practical standpoint, an infeasible space points to the possibility that the model is not formulated correctly.

Example 3.5-4         (Infeasible Solution Space)

Consider the following LP:

Using the penalty M = 100 for the artificial variable R, the following tableaux provide the simplex iterations of the model.

Optimum iteration 1 shows that the artificial variable R is positive (= 4), which indicates that the problem is infeasible. Figure 3.11 demonstrates the infeasible solution space. By allowing

the artificial variable to be positive, the simplex method, in essence, has reversed the direction of the inequality from 3x 1 + 4x 2 ≥ 0: 12 to 3x l + 4x 2 ≤ 12 (can you explain how?). The result is what we may call a pseudo-optimal solution.

PROBLEM SET 3.50

*1. Tooleo produces three types of tools, T1, T2, and T3. The tools use two raw materials, M1 and M2, according to the data in the following table:

The available daily quantities of raw materials M1 and M2 are 1000 units and 1200 units, respectively. The marketing department informed the production manager that according to their research, the daily demand for all three tools must be at least 500 units. Will the manufacturing department be able to satisfy the demand? If not, what is the most Toolco can provide of the three tools?

2. TO RA Experiment. Consider the LP model

Use TORA's Iterations => M-Meth6d to show that the optimal solution includes an artificial basic variable, but at zero level. Does the problem have a feasible optimal solution?

Related Topics

Privacy Policy , Terms and Conditions , DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons
• Download Page (PDF)
• Download Full Book (PDF)
• Periodic Table
• Physics Constants
• Scientific Calculator
• Reference & Cite
• Tools expand_more
• Readability

selected template will load here

This action is not available.

4.2.1: Maximization By The Simplex Method (Exercises)

• Last updated
• Save as PDF
• Page ID 37871

• Rupinder Sekhon and Roberta Bloom
• De Anza College

SECTION 4.2 PROBLEM SET: MAXIMIZATION BY THE SIMPLEX METHOD

Solve the following linear programming problems using the simplex method.

1) \[\begin{array}{ll} \text { Maximize } & \mathrm{z}=\mathrm{x}_{1}+2 \mathrm{x}_{2}+3 \mathrm{x}_{3} \\ \text { subject to } & \mathrm{x}_{1}+\mathrm{x}_{2}+\mathrm{x}_3 \leq 12 \\ & 2 \mathrm{x}_{1}+\mathrm{x}_{2}+3 \mathrm{x}_{3} \leq 18 \\ & \mathrm{x}_{1}, \mathrm{x}_{2}, \mathrm{x}_{3} \geq 0 \end{array} \nonumber \]

2) \[\begin{array}{ll} \text { Maximize } \quad z= & x_{1}+2 x_{2}+x_{3} \\ \text { subject to } & x_{1}+x_{2} \leq 3 \\ & x_{2}+x_{3} \leq 4 \\ & x_{1}+x_{3} \leq 5 \\ & x_{1}, x_{2}, x_{3} \geq 0 \end{array} \nonumber \]

3) A farmer has 100 acres of land on which she plans to grow wheat and corn. Each acre of wheat requires 4 hours of labor and $20 of capital, and each acre of corn requires 16 hours of labor and $40 of capital. The farmer has at most 800 hours of labor and $2400 of capital available. If the profit from an acre of wheat is $80 and from an acre of corn is $100, how many acres of each crop should she plant to maximize her profit?

4) A factory manufactures chairs, tables and bookcases each requiring the use of three operations: Cutting, Assembly, and Finishing. The first operation can be used at most 600 hours; the second at most 500 hours; and the third at most 300 hours. A chair requires 1 hour of cutting, 1 hour of assembly, and 1 hour of finishing; a table needs 1 hour of cutting, 2 hours of assembly, and 1 hour of finishing; and a bookcase requires 3 hours of cutting, 1 hour of assembly, and 1 hour of finishing. If the profit is $20 per unit for a chair, $30 for a table, and $25 for a bookcase, how many units of each should be manufactured to maximize profit?

5). The Acme Apple company sells its Pippin, Macintosh, and Fuji apples in mixes. Box I contains 4 apples of each kind; Box II contains 6 Pippin, 3 Macintosh, and 3 Fuji; and Box III contains no Pippin, 8 Macintosh and 4 Fuji apples. At the end of the season, the company has altogether 2800 Pippin, 2200 Macintosh, and 2300 Fuji apples left. Determine the maximum number of boxes that the company can make.