how can we solve linear programming problem using simplex method

• max Z = 3x1 + 5x2 + 4x3 subject to 2x1 + 3x2 2x2 + 5x3 3x1 + 2x2 + 4x3 and x1,x2,x3 >= 0
• max Z = 5x1 + 10x2 + 8x3 subject to 3x1 + 5x2 + 2x3 4x1 + 4x2 + 4x3 2x1 + 4x2 + 5x3 and x1,x2,x3 >= 0
• max Z = 4x1 + 3x2 subject to 2x1 + x2 x1 + x2 x1 x2 and x1,x2 >= 0
• =,>=`4,7`');">min Z = x1 + x2 subject to 2x1 + 4x2 >= 4 x1 + 7x2 >= 7 and x1,x2 >= 0
• =,>=`80,60`');">min Z = 600x1 + 500x2 subject to 2x1 + x2 >= 80 x1 + 2x2 >= 60 and x1,x2 >= 0
• =`12,10,10`');">min Z = 5x1 + 3x2 subject to 2x1 + 4x2 2x1 + 2x2 = 10 5x1 + 2x2 >= 10 and x1,x2 >= 0
• max Z = x1 + 2x2 + 3x3 - x4 subject to x1 + 2x2 + 3x3 = 15 2x1 + x2 + 5x3 = 20 x1 + 2x2 + x3 + x4 = 10 and x1,x2,x3,x4 >= 0
• max Z = 3x1 + 9x2 subject to x1 + 4x2 x1 + 2x2 and x1,x2 >= 0
• max Z = 3x1 + 2x2 + x3 subject to 2x1 + 5x2 + x3 = 12 3x1 + 4x2 = 11 and x2,x3 >= 0 and x1 unrestricted in sign
• max Z = 3x1 + 3x2 + 2x3 + x4 subject to 2x1 + 2x2 + 5x3 + x4 = 12 3x1 + 3x2 + 4x3 = 11 and x1,x2,x3,x4 >= 0
• =`30,24,3`');">max Z = 6x1 + 4x2 subject to 2x1 + 3x2 3x1 + 2x2 x1 + x2 >= 3 and x1,x2 >= 0
• =`6,10,1`');">max Z = 3x1 + 5x2 subject to x1 - 2x2 x1 x2 >= 1 and x1,x2 >= 0
• =`5,8`');">max Z = 6x1 + 4x2 subject to x1 + x2 x2 >= 8 and x1,x2 >= 0
• =,>=`-5,8`');">max Z = 6x1 + 4x2 subject to -x1 - x2 >= -5 x2 >= 8 and x1,x2 >= 0

Chapter 5: Linear Programming with the Simplex Method

One of the most significant advancements in linear programming is the simplex method, developed by George Dantzig. This algorithm provides a systematic approach to finding the optimal solution to linear programming problems. In this article, we will explore the simplex method, its key concepts, and how it is applied to solve linear programming problems.

Overview of the Linear Programming with the Simplex Method

The simplex method is a systematic approach to traverse the vertices of the polyhedron containing feasible solutions in a linear programming problem. It aims to find the optimal solution by iteratively improving the objective function value. This method is considered one of the greatest inventions of modern times due to its broad applicability in solving business-related problems.

Formulating the Original Linear Programming Problem

To illustrate the simplex method, let’s consider a furniture production problem. We want to maximize the revenue generated by producing chairs and tables, subject to constraints on the availability of mahogany and labor. The original problem can be formulated as follows:

• Maximize Revenue = 45×1 + 80×2
• 5×1 + 20×2 ≤ 400 (Mahogany constraint)
• 10×1 + 15×2 ≤ 450 (Labor constraint)
• x1, x2 ≥ 0 (Non-negativity constraint)

In this formulation, x1 represents the number of chairs produced, x2 represents the number of tables produced, and the objective function maximizes the total revenue. The constraints limit the consumption of mahogany and labor within the available capacities.

Transforming into Standard Form

To apply the simplex method, we transform the original problem into the standard form, which involves converting the inequalities into equalities. We introduce slack variables to represent the surplus capacity of each constraint. In this case, we add h1 and h2 as slack variables for the mahogany and labor constraints, respectively. The problem in standard form becomes:

• Maximize Revenue = 45×1 + 80×2 + 0h1 + 0h2
• 5×1 + 20×2 + h1 = 400 (Mahogany constraint)
• 10×1 + 15×2 + h2 = 450 (Labor constraint)
• x1, x2, h1, h2 ≥ 0 (Non-negativity constraint)

The slack variables h1 and h2 represent the unused capacities of mahogany and labor, respectively. We still aim to maximize the revenue while satisfying these transformed equalities.

Basic Feasible Solutions and Canonical Form

A basic feasible solution is an initial production plan that satisfies all the constraints, with some variables set to zero. In our case, the initial solution where no chairs or tables are produced (x1=0, x2=0) represents a basic feasible solution. This solution generates zero revenue, as expected.

The non-basic variables in a basic feasible solution are set to zero, while the basic variables take positive values. In our initial solution, h1 and h2 are the basic variables, representing the unused capacities of mahogany and labor. The non-basic variables are x1 and x2, which are set to zero. This configuration is called a basic feasible solution and is an important concept in linear programming.

To express the problem in canonical form, we represent the basic variables (h1 and h2) in terms of the non-basic variables (x1 and x2). Similarly, we substitute the non-basic variables in the objective function. This process is known as pivoting. The canonical form of the problem becomes:

• Maximize z = 45×1 + 80×2 + 0h1 + 0h2
• x1 = 0 + (1/5)h1 – (4/5)h2 (Transformed mahogany constraint)
• x2 = 0 – (2/5)h1 + (3/5)h2 (Transformed labor constraint)
• x1, x2, h1, h2 ≥ 0

In the canonical form, the objective function and constraints are expressed with respect to the basic variables x1 and x2. The reduced costs associated with the non-basic variables x1 and x2 (coefficients in the objective function) indicate the potential improvement in the objective function value if these variables enter the basis.

Iteration and Optimal Solution

In each iteration of the simplex method, we analyze the non-basic variables and their coefficients. If all the non-basic variables have coefficients ≤ 0, the current solution is optimal. Negative reduced costs associated with the non-basic variables indicate that increasing these variables would decrease the objective function value.

If there is a non-basic variable with a positive reduced cost, we choose the one with the largest coefficient to enter the basis. To determine the maximum value for this variable, we perform the minimum ratio test using the transformed equations. The minimum ratio identifies the constraint that limits the increase of the non-basic variable while staying feasible.

After selecting the entering variable, we perform pivoting to express the problem in canonical form with respect to the new basic variables. This process continues iteratively until we reach an optimal solution or determine that the problem is unbounded.

The simplex method provides a systematic approach to solving linear programming problems by iteratively improving the objective function value. By transforming the problem into the standard form and expressing it in canonical form, we can identify basic feasible solutions and optimize the objective function. The simplex method is a fundamental tool in linear programming, enabling efficient optimization in various industries and applications.

Download the complete  Linear Programming Tutorial Series slide deck .

View the entire series:

• Welcome: Linear Programming Tutorial
• Chapter 1: Mathematical Programming
• Chapter 2: Introduction to Linear Programming
• Chapter 3: Mixed Integer Linear Programming Problems
• Chapter 4: Furniture Factory Problem
• Chapter 5: Simplex Method
• Chapter 6: Modeling and Solving Linear Programming Problems
• Chapter 7: Sensitivity Analysis of Linear Programming Problems
• Chapter 8: Multiple Optimal Solutions
• Chapter 9: Unbounded Linear Programming Problems
• Chapter 10: Infeasible Linear Programming Problems
• Chapter 11: Linear Programming Overview – Further Considerations
• Chapter 12: Duality in Linear Programming
• Chapter 13: Optimality Conditions
• Chapter 14: Dual Simplex Method

Guidance for Your Journey

30 day free trial for commercial users, always free for academics.

GUROBI NEWSLETTER

Latest news and releases

• Linear Programming (LP) – A Primer on the Basics
• Chapter 7: Sensitivity Analysis of Linear…

Try Gurobi for Free

Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.

Evaluation License

Academic license, cloud trial.

Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.

Looking for documentation?

Jupyter Models

Case studies, privacy overview.