Undergraduate
  1. Algebra  1.1. Linear Algebra  1.1.1. Matrices  1.1.2. Determinants  1.1.3. Systems of Linear Equations  1.1.4. Vector Spaces  1.1.5. Linear Transformations  1.1.6. Eigenvalues and Eigenvectors  1.1.7. Diagonalization  1.1.8. Inner Product Spaces  1.1.9. Orthogonality and Orthonormal Bases  1.1.10. Singular Value Decomposition  1.2. Abstract Algebra  1.2.1. Groups  1.2.2. Subgroups  1.2.3. Cyclic Groups  1.2.4. Permutation Groups  1.2.5. Homomorphisms  1.2.6. Normal Subgroups  1.2.7. Rings  1.2.8. Fields  1.2.9. Ideals and Quotient Rings  1.2.10. Polynomial Rings  1.2.11. Vector Spaces over Fields  1.2.12. Modules  1.2.13. Galois Theory
  2. Calculus  2.1. Differential Calculus  2.1.1. Limits  2.1.2. Continuity  2.1.3. Derivatives  2.1.4. Chain Rule  2.1.5. Implicit Differentiation  2.1.6. Applications of Derivatives  2.1.7. Optimization Problems  2.1.8. Mean Value Theorem  2.2. Integral Calculus  2.2.1. Definite Integrals  2.2.2. Indefinite Integrals  2.2.3. Techniques of Integration  2.2.4. Improper Integrals  2.2.5. Applications of Integration  2.2.6. Arc Length and Surface Area  2.3. Multivariable Calculus  2.3.1. Partial Derivatives  2.3.2. Gradient  2.3.3. Divergence and Curl  2.3.4. Multiple Integrals  2.3.5. Line Integrals  2.3.6. Surface Integrals  2.3.7. Green's Theorem  2.3.8. Stokes' Theorem  2.3.9. Divergence Theorem  2.3.10. Jacobians
  3. Differential Equations  3.1. Ordinary Differential Equations  3.1.1. First Order Differential Equations  3.1.2. Higher Order Differential Equations  3.1.3. Systems of Differential Equations  3.1.4. Series Solutions  3.1.5. Numerical Methods for ODEs  3.2. Partial Differential Equations  3.2.1. Heat Equation  3.2.2. Wave Equation  3.2.3. Laplace Equation  3.2.4. Separation of Variables  3.2.5. Fourier Transform Methods
  4. Real Analysis  4.1. Sequences and Series  4.1.1. Convergence of Sequences  4.1.2. Series Tests  4.1.3. Power Series  4.1.4. Uniform Convergence  4.2. Functions of Real Variables  4.2.1. Limits and Continuity  4.2.2. Uniform Continuity  4.2.3. Differentiation in Functions of Real Variables  4.2.4. Riemann Integration  4.2.5. Lebesgue Integration
  5. Complex Analysis  5.1. Complex Numbers  5.1.1. Polar Form  5.1.2. Exponential Form  5.2. Functions of a Complex Variable  5.2.1. Analytic Functions  5.2.2. Cauchy-Riemann Equations  5.2.3. Contour Integrals  5.2.4. Cauchy's Integral Theorem  5.2.5. Residue Theorem  5.2.6. Conformal Mapping
  6. Probability and Statistics  6.1. Probability Theory  6.1.1. Basic Probability Concepts  6.1.2. Random Variables  6.1.3. Probability Distributions  6.1.4. Expectation and Variance  6.1.5. Conditional Probability and Bayes' Theorem  6.2. Statistics  6.2.1. Descriptive Statistics  6.2.2. Inferential Statistics  6.2.3. Hypothesis Testing  6.2.4. Regression Analysis  6.2.5. ANOVA
  7. Numerical Methods  7.1. Root-Finding Algorithms  7.2. Numerical Integration  7.3. Numerical Differentiation  7.4. Numerical Solutions to Differential Equations  7.5. Matrix Computations  7.6. Interpolation and Extrapolation
  8. Discrete Mathematics  8.1. Logic and Proof  8.2. Combinatorics  8.3. Graph Theory  8.4. Boolean Algebra  8.5. Recurrence Relations
  9. Linear Programming and Optimization  9.1. Simplex Method  9.2. Duality  9.3. Integer Programming  9.4. Nonlinear Optimization
  10. Topology  10.1. Metric Spaces  10.2. Topological Spaces  10.3. Continuity and Homeomorphisms  10.4. Compactness  10.5. Connectedness
  11. Geometry  11.1. Euclidean Geometry  11.2. Differential Geometry  11.3. Non-Euclidean Geometry  11.4. Projective Geometry
  12. Mathematical Physics  12.1. Fourier Series  12.2. Laplace Transforms  12.3. Applications of Differential Equations  12.4. Special Functions
  13. Set Theory and Logic  13.1. Sets and Subsets  13.2. Relations and Functions  13.3. Cardinality  13.4. Formal Logic  13.5. Zermelo-Fraenkel Set Theory
  14. Functional Analysis  14.1. Normed Spaces  14.2. Banach Spaces  14.3. Hilbert Spaces  14.4. Linear Operators

Undergraduate → Linear Programming and Optimization ↓


Simplex Method


Introduction to linear programming

Linear programming is a mathematical technique for optimizing a linear objective function, subject to linear equality and inequality constraints. It is a way to achieve the best result in a mathematical model whose requirements are represented by linear relationships. This kind of optimization is important in various fields such as economics, engineering, military, and business planning.

Objective function and constraints

In linear programming, our goal is to maximize or minimize a linear objective function. A general linear programming problem can be stated as:

Maximum or minimum: Z = c 1 x 1 + c 2 x 2 + ... + c n x n
subject to:
a 11 x 1 + a 12 x 2 + ... + a 1n x n ≤ b 1
a 21 x 1 + a 22 x 2 + ... + a 2n x n ≤ b 2
,
a m1 x 1 + a m2 x 2 + ... + a mn x n ≤ b m
x 1 , x 2 , ..., x n ≥ 0

Here, x 1 , x 2 , ..., x n are variables, c 1 , c 2 , ..., c n are the coefficients of the objective function, a ij are the coefficients of the constraints, and b i are constants in the constraint equations.

The simplex method: An overview

The simplex method is a popular algorithm used to solve linear programming problems. It was developed by George Dantzig in 1947. This method consists of the following main steps:

  • Converting a linear programming problem to the standard form.
  • Finding an initial feasible solution.
  • Working iteratively to improve the objective function until the optimal solution is reached.

Converting to standard form

Before applying the simplex method, one must transform the given linear programming problem into standard form. This involves ensuring that all constraints are in the form of equality and adding relaxations, superpositions, or artificial variables if necessary.

Suppose we have a constraint like: 
a 11 x 1 + a 12 x 2 ≤ b 1

To turn this into equality, we introduce a loose variable s 1 :

a 11 x 1 + a 12 x 2 + s 1 = b 1

Finding the initial feasible solution

Once the problem is in standard form, we need to find a basic feasible solution. This involves setting the non-basic variables to zero and solving the system of equations to find the values of the basic variables.

Iterative process

The basic purpose of the simplex method is to improve the value of the objective function by processing through the feasible solutions to identify the optimal solution. This is done by pivoting.

Example

Let's look at a visual example of a linear programming problem. Let's say we have the following problem:

Maximize: Z = 3x 1 + 5x 2
subject to:
x 1 + 2x 2 ≤ 8
3x 1 + 2x 2 ≤ 12
x 1 , x 2 ≥ 0
x 1 x 2 x 1 + 2x 2 = 8 3x1 + 2x2 = 12

In the above example, the constraints x 1 + 2x 2 = 8 and 3x 1 + 2x 2 = 12 are drawn as lines. The feasible region bounded by the green polygon shows where all the conditions are met.

Pivoting in the simplex method

To improve the objective function, we will choose pivot elements. Entry criteria and exit criteria help to identify which variable enters the basis and which exits. Pivoting modifies our basis so that it moves to an adjacent feasible solution with a higher value (in case of maximization) for the objective function.

Steps involved in pivoting

The pivoting process includes these main steps:

  1. Identify the entering variable:
    • Look at the objective row (also called the cost row) in the simplex tableau. Choose the variable whose coefficient is most positive (for maximization problems). This is our entering variable.
  2. Determine the departure variable:
    • To find the leaving variable, calculate the minimum ratio of the right-hand side to the positive coefficients of the entering variable in each restriction line.
  3. Perform row operations:
    • Adjust the table to reflect this new basis. This involves the pivot element row operation to set the other elements in the column of the entering variable to zero.

Continuation of the example

Let's apply these steps to our previous example.

Simplex tableau for initial basis

The initial table for converting inequalities to equalities is set up with relaxed variables s 1 and s 2 for each constraint:

| x 1 | x 2 | s 1 | s 2 | right hand side | 
,
, 1 | 2 | 1 | 0 | 8 |
, 3 | 2 | 0 | 1 | 12 |
,
, -3 | -5 | 0 | 0 | 0 |

Let us identify the entering and exiting variables:

For maximization, the most negative coefficient in the objective row is -5 (under x 2 ). This means that x 2 is our entry variable.

To find the departure variable, we calculate the ratio of the RHS to the positive coefficient of x 2 :

8/2 = 4 (for the first row)
12/2 = 6 (for the second row)
The minimum ratio is 4, which indicates that the first line will depart.

Perform row operations to create the original variable x 2 in the first row.

Update the rest of the table accordingly.

Optimal solution

Continue similar pivoting steps until there are no negative coefficients in the objective row (for maximization), indicating that the optimal solution has been found.

Conclusion

The simplex method is an efficient algorithm that works by iterating over the vertices of the feasible region in a systematic manner. It is particularly efficient for linear problems involving a large number of variables and constraints, proving its utility in both theoretical mathematics and practical decision-making scenarios. Through careful implementation and understanding of each step, students can effectively harness the power of the simplex method to find optimal solutions to complex problems.


Undergraduate → 9.1


U
username
0%
completed in Undergraduate

← Prev (9)
Linear Programming and Optimization
Next (9.2) →
Duality

Comments 



Simplex Method

https://www.buddymath.com/ug/9.1?bmal=en