Feasible Solution Definition

The definition of feasible solution In linear programming, any group of values for the variables xj,j= 1, 2, …,n, that (1) accomplish the set of restrictions where them bi  are numerical constants known collectively as the right-hand side and the aij are coefficients of the variables xj, and (2) satisfy the restrictions xj≥ 0. Simple problem in linear programming definition in which it is necessary to find the maximum or minimum value of a simple function subject to certain constraints.

Conditionas

Conditions

Consider Gauss Jordan elimination on a matrix and then group of all variables that are not part of the identity sub matrix equal to zero. We are read out values for the remaining variables. Basic feasible solution all the variables are positive. Definition of basic feasible solutions equate to corners. Pre-multiplying by the matrix AB−1 is equivalent to doing the row operations that transform AB into the identity matrix.

At once fix a matrix A ∈ Rmxn with rank m ≤ n and a vector b ∈ Rm. A function B from 1…..m to 1…..n is indicates which columns to find the identity matrix. In very particular B(i) = j means , the jth column is intended to be all zeros except for a one in row i. The function N from 1….m-n to 1..n indicates which columns are not used in the identity matrix. Each column should be used exactly once, so assume that the union of the ranges of N and M is 1..n. Let AB denote the sub matrix of A corresponding to the columns indicated by B, that is AB = (aB(1) …. aB(m)  ) where at denotes the tth column of A. In order for row operations to produce the identity matrix it is necessary and sufficient that AB be invertible.

Example

Given a combination of functions significant these conditions one can build a definition and basic solution as follows. Set xN = 0 and xB = AB−1  b, where xB and xN are defined analogously to AB. Let x be the vector with component xi equal to the appropriate component of xB or xN depending on which the corresponding column belongs to. Functioning a vector is a basic solution. If it is nonnegative it is feasible and is therefore called a definition of basic feasible solution.