Difference between revisions of "Simplex algorithm"

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
Line 4: Line 4:
  
 
== Introduction ==
 
== Introduction ==
Simplex algorithm (or Simplex method) is a widely-used algorithm to solve the Linear Problem (LP). Simplex algorithm can be thought as one of the elementary steps for solving the inequality problem since many of those will be converted to LP and solved via Simplex algorithm. Simplex algorithm has been proposed by [[wikipedia:George_Dantzig|George Dantzig]]
+
Simplex algorithm (or Simplex method) is a widely-used algorithm to solve the Linear Programming(LP). Simplex algorithm can be thought as one of the elementary steps for solving the inequality problem, since many of those will be converted to LP and solved via Simplex algorithm<sup>[1]</sup>. Simplex algorithm has been proposed by [[wikipedia:George_Dantzig|George Dantzig]], initiated from the idea of step by step downgrade to one of the vortices on the convex polyhedral<sup>[2]</sup>. "Simplex" could be possibly referred as the top vertex on the simplicial cone which is the geometric illustration of the constraints within Linear Problem<sup>[3]</sup>.
 +
 
 +
== Algorithmic Discussion ==
 +
 
 +
=== Background Theorem ===
 +
There are two theorem in LP:
 +
 
 +
# The feasible region for any LP problem is a convex set. If an LP has an optimal solution, there must be an extreme point of the feasible

Revision as of 21:18, 17 November 2020

Author: Guoqing Hu (SysEn 6800 Fall 2020)

Steward: Allen Yang, Fengqi You

Introduction

Simplex algorithm (or Simplex method) is a widely-used algorithm to solve the Linear Programming(LP). Simplex algorithm can be thought as one of the elementary steps for solving the inequality problem, since many of those will be converted to LP and solved via Simplex algorithm[1]. Simplex algorithm has been proposed by George Dantzig, initiated from the idea of step by step downgrade to one of the vortices on the convex polyhedral[2]. "Simplex" could be possibly referred as the top vertex on the simplicial cone which is the geometric illustration of the constraints within Linear Problem[3].

Algorithmic Discussion

Background Theorem

There are two theorem in LP:

  1. The feasible region for any LP problem is a convex set. If an LP has an optimal solution, there must be an extreme point of the feasible