goptimization

Documentation

Index

• func Simplex(c, A, b *mat.Dense, maxIter int) (int, *mat.Dense, float64, error)
• type CanonicalForm
  • func (cf *CanonicalForm) FindEnteringVariable(y *mat.Dense, forceEnteringVarIndex int) (int, error)
  • func (cf *CanonicalForm) FindLeavingVariable(d *mat.Dense) (float64, int, error)
  • func (cf *CanonicalForm) FindY() (*mat.Dense, error)
  • func (cf *CanonicalForm) GetResults() (*mat.Dense, float64)
  • func (cf *CanonicalForm) Iter(forceEnteringVarIndex int) (bool, error)
  • func (cf *CanonicalForm) New(c, A, b *mat.Dense) error
  • func (cf *CanonicalForm) SolveBd(enteringVarIndex int) (*mat.Dense, error)
  • func (cf *CanonicalForm) Update(d, y *mat.Dense, x float64, enteringVarIndex, leavingVarIndex int) error

Functions

func Simplex

func Simplex(c, A, b *mat.Dense, maxIter int) (int, *mat.Dense, float64, error)

Simplex Solve a linear problem wihtout strict inequality constraints. Input follows standard form: Maximize z = Σ(1<=j<=n) c_j*x_j Constraints: 1<=i<=m, Σ(1<=j<=n) a_i_j*x_j <= b_i 1<=j<=n x_j >= 0 - Define the canonical form of the problem (add slack variables and transfrom inequality constraints to equality constraints) - Check the basic solution is feasible, if not you need to run two phases simplex - Run iterations - Stop when the optimal solution is found or after maxIter Apply - First Danzig critera: for entering variable, pick the nonbasic variable with the largest reduced cost. - Bland's rule to avoid cycles : Choose the entering basic variable xj such that j is the smallest index with c¯j < 0. Also choose the leaving basic variable i with the smallest index (in case of ties in the ratio test)

Types

type CanonicalForm

type CanonicalForm struct {

	// Matrix (m, n+m)
	A *mat.Dense

	// Matrix (m, m)
	B *mat.Dense
	// Matrix (m,n)
	AN *mat.Dense
	// contains filtered or unexported fields
}

CanonicalForm Canonical form of a linear optimizattion problem

func (*CanonicalForm) FindEnteringVariable

func (cf *CanonicalForm) FindEnteringVariable(y *mat.Dense, forceEnteringVarIndex int) (int, error)

FindEnteringVariable Define the best entering varialbe following Danzig criteria and Bland's rule Find one column a^k of A not in B with y*a^k<c^k If there is no entering column, the current solution is optimal

func (*CanonicalForm) FindLeavingVariable

func (cf *CanonicalForm) FindLeavingVariable(d *mat.Dense) (float64, int, error)

FindLeavingVariable Define what is the best leaving variable following Bland's rule Find the biggest x_kStar with x_BStar - x_kStar*d >= 0 If d<=0, the algorithm ends and the problem is unbounded. Otherwise, the biggest x_kStar force one of the components of x_BStar - x_kStar*d to be equal to zero and defines the leaving variable

func (*CanonicalForm) FindY

func (cf *CanonicalForm) FindY() (*mat.Dense, error)

FindY Extract and solve a sub problem of the current dictionary The current dictionary is: (1) xB = xBStar - B^-1*AN*xN (2) z = zStar + (cN - cB*B^-1*AN)xN Set y=cB*B^-1 and solve it

func (*CanonicalForm) GetResults

func (cf *CanonicalForm) GetResults() (*mat.Dense, float64)

GetResults Build the solution. It returns a matrix (n+m,1), the first n components are the best value for the problem and the others are the "leftover" for each constraint. Also returns the maximum score.

func (*CanonicalForm) Iter

func (cf *CanonicalForm) Iter(forceEnteringVarIndex int) (bool, error)

Iter Run one iteration of the simplex algorithm

func (*CanonicalForm) New

func (cf *CanonicalForm) New(c, A, b *mat.Dense) error

New Initialize all the parameters in order to run the simplex algorithm

func (*CanonicalForm) SolveBd

func (cf *CanonicalForm) SolveBd(enteringVarIndex int) (*mat.Dense, error)

SolveBd FindY describes the current dictionary. To find the best leaving variable we start from (1) and set d=B^-1*a^k When we solve it, we get the equation to maximize in order to find the leaving variable

func (*CanonicalForm) Update

func (cf *CanonicalForm) Update(d, y *mat.Dense, x float64, enteringVarIndex, leavingVarIndex int) error

Update Update the dictionary in order to run anotheriteration Replace the leaving variable with the entering variable in xBStar Replace the leaving column in the base B with the entering column