Skip to content

SIMPLEX method

Jump to bottom
andreamendozacruz98 edited this page Oct 21, 2018 · 133 revisions

CONTENT

  1. SIMPLEX METHOD
    1. What is it?
  2. OBJECTIVES
    1. Objective of the group
    2. Objective of the method
  3. THEORETICAL FRAMEWORK
    1. Feasible Solution
    2. Optimal Solution
    3. Multiple Optimal Solution
    4. Unbounded Solution
    5. Infeasible Solution
    6. Basic Variable
    7. Non-basic Variable
    8. Slack Variable
    9. Surplus Variable
    10. Artificial Variable
    11. Big-M Method
  4. PROCESS
  5. EXAMPLES
  6. BIBLIOGRAPHY

SIMPLEX METHOD

https://en.wikipedia.org/wiki/Simplex_algorithm

What is it?

It is an analytic method for solving problems of linear programming using algebraic operations. This method provides a strategy for evaluating the feasible results finding the optimal value of the objective function.

OBJECTIVES

Objective of the group:

Due to the lack of free technological tools that work as a support for teaching industrial engineering's subjects, the objective of SIMPOD group of ALIEN is to design and develop a module that can be used for solving linear programming problems with more than two variables. This module is meant to be part of a program with different engineering techniques, which is hoped to be applied in education, for students to be aware of the scope of the engineering tools, understanding their importance in the industry and in real life situations.

https://codeburst.io/optimizing-compilation-time-for-swift-code-e692376085a6

Objective of the method:

The iterative procedure followed in the Simplex method improves step by step the solution obtained. The purpose of the method is to find the optimal solution that satisfies the constraints of a problem. It is used for maximizing profit, production, minimizing costs, resources, among others.

THEORETICAL FRAMEWORK

  • Feasible solution

A solution where all the constraints are satisfied.

  • Optimal Solution

It is the feasible solution where the objective function reaches the minimum or maximum value depending on the purpose of the problem. The optimal solution can be a globally optimal solution which means that there are no alternative feasible solutions with better values in the objective function.

  • Multiple Optimal Solution

This special case occurs when the objective function is parallel to one of the constraints. It can be noticed if in the z-row value for one or more non-basic variable is zero. This value indicates that the non-basic variable can be made basic altering the value of the variable without changing the value of z.

  • Unbounded Solution

This special case occurs if the value of a variable is increased indefinitely and the constraints are not violated. This means that the feasible region is unbounded at least in one direction. Therefore, the objective function value can be increased indefinitely because there is not a limit. This means that the problem has been poorly formulated or conceived. It can be noticed if there is no positive ratio (the value is either negative or infinitive). This indicates that no variable is ready to leave the basis, though a variable is ready to enter.

  • Infeasible Solution

This special case occurs in the Big-M Method in which artificial variables are used. It can be noticed if at least one artificial variable has a value not equal to zero, the problem would not have a feasible solution because the artificial variables are introduced within an equality and in case of having a value different from 0, it would not be fulfilled.

  • Basic Variable

Is a variable in the basic solution (also called basis) and whose value is not equal to zero.

  • Non-basic Variable

Is a variable not in the basic solution (also called basis) and whose value is equal to zero.

  • Slack Variable

It is added to a less than or equal constraints in order to get a convenient equation for the simplex method, in this case, the convenient equation is an equality constraint.

  • Surplus Variable

This type of variable is also called ‘Negative Slack Variable’. It is added to greater than or equal constraints in order to get a convenient equation for the simplex method, in this case, the convenient equation is an equality constraint.

  • Artificial Variable

This type of variable is used in the "Big M Method" and it is added to greater than or equal and equality constraints to get an initial solution to an LP problem.

  • Big M Method

This method applies to problems with "greater-than" and "equality" constraints. It does so by associating the constraints with large negative constants which would not be part of an optimal solution if it exists.

PROCESS

  • PART 1

  1. Adapt the model

  2. Identify the nature of constraints

  3. Normalize constraints

http://www.phpsimplex.com/en/simplex_method_theory.htm#msimplex

  • PART 2

  • PART 3

EXAMPLES

MAXIMIZATION PROBLEM

DUAL SIMPLEX METHOD PROBLEM

BIBLIOGRAPHY

Mirzaei, S., Special Cases of Linear Programming Problem-Part1:Degeneracy Condition, Obtained from: https://www.youtube.com/watch?v=pVWsXZh81IU (minute 3)

Chinneck, J.W., Practical Optimization: a Gentle introduction, Chapter 4, Obtained from: http://www.sce.carleton.ca/faculty/chinneck/po/Chapter4.pdf

PHP Simplex., Simplex method theory, Obtained from: http://www.phpsimplex.com/en/simplex_method_theory.htm#msimplex

Clone this wiki locally