Math 407 review
Terms
-
Linear function
-
A linear function on R^n is any function of the form
f(x) - a^t*x = a_1*x_1 _ ... + a_n*x_n
where a = [a1,....,an]^t E R^n
- Linear Inequality
-
an ienequality that can be written in one of th e following two ways
a^T*x <= b or a^T*x >= b
where a E R^n and b E R
- The solution set of a system of linear inequalities
-
Given A E R^{m*n} and b E R^{m*n} we write Ax<=b to denote the system of linear inequalities
n
SUM a_{ij}*x_{j} <= b_i i = 1, .. m
j-1
The set of the solutions of this system is
- Linear Programming
-
- Study of linear programs: modeling, formulation, algorithms, and analysis
- A LP is an optimization problem wherein one either minimizes or maximizes a linear objective function in a
- Objective Function
- in an optimization problem is the real-valued function of the decision variables that is to be either maximized or minimized.
- Optimal Value
- value of the objective function at an optimal solution
- optimal solution
-
min{ f(x) : x E X ( R^n }
is any point x^* E X s.t. f(x^*) <= f(x) for all x E X
- Feasible Solution
-
min{ f(x) : x E X ( R^n }
is any point x E X.
-
Infeasible LP
-
An LP whose constraint region or feasible set is empty
- Unbouned LP
- an LP which there is a sequence of feasible points whose objective value diverges to +Inf in the case of a max and -Inf in the case of a min
- Slack Variables
-
Slack variables are introduced into an LP formulation in order to turn linear inequalities into linear equalities. For example, the constraint region for an LP in standard form is into system of equations involving n + m variables by setting:
&nb
- LP in Standard Form
-
max c^T*x
s.t. A*x <= b, 0 <= x
-
Inital dictionary for Std. LP
-
D_I
x_n+i = sum a_ij * x_j, i = 1,2,..m
z = sum c_j*x_j
-
Feasible Solution for an LP
- any point in the feasible region for the LP
-
Optimal Solution for an LP
-
An optimal solution for an LP is any solution whose objective value equals the optimal value of the LP
-
Unbounded LP
- any feasible LP whose optimal value is +Inf if Max or -Inf if min
- LP with feasible Origin
- Lp whose feasible region contains the origin. For an Lp in standard form, this implies that b_i >= 0, i = 1,..,m
-
Basic Rule for chosing the entering varible
- choose any one of the currently non-basic variables whose cost row coefficient is positive
-
Basic Rule for Choosing the Leaving Varible
-
choose any one of the currently basic variables whose non-negativity places the greatest restriction on increasing the balue of the entering varible
- Degeneracy
- occurs when a simplex pivot does not change either the current value of the objective or the point identified by the dictornay. A dict is said to be degenerate if one of the currently basic variables in the basic fesiable solution has the value zero.
- Degenerate basic solution
- any feasible solution identified by a feasible dictionary for the LP. such a solution is said to be degenerate if one of the currently basic variables in the basic feasible solution has the alue zero
- Degenerate Simplex Iteration
-
any simplex iteration that does not change the value of the objective
-
smallest subscript rule
-
the entering and eaving varialbes