Module 3 Flashcards
A method of dealing with decision problems that can be expressed as constrained linear models.
Linear programming
result of Air Force research project concerned with computing the most efficient and economical way to distribute men, weapons and supply from different fronts during World War I
Linear Programming
Who suggested renaming “programming in a linear structure” as “linear programming”
Tjalling Koopmans
producing a plan or procedure that determines the solution to a problem
Programming
a two-dimensional geometric analysis of LP problems with two decision variables
Graphical Solution Method
American mathematical scientist who created linear programming
George Bernard Dantzig
an expression, which shows the relationship between the variables in the problem and the firm’s goal
Objective Function
(or explicit constraint) is a limit on the availability of resources.
Structural Constraint
(or implicit constraint) it restricts all the variables to zero and positive solution
Non-negativity constraint
the highest (for maximization problem) or lowest value (for minimization problem) of the objective function.
Optimal Value
combination of decision variable amounts that yields the best possible value of the objective function and satisfies all the constraints.
Optimal solution
the set of combinations of values for the decision variables that satisfy the non-negativity conditions and all the constraints simultaneously that is the allowable decisions
Feasible Region
the corner of the feasible region
Extreme Point
Special cases in Linear Programming (Graphical Method)
Multiple Optimal Solution
Infeasibility
Redundancy
Unbounded
An LP model that has a multiple optimal solution or more than one optimal solution.
Multiple optimal solution
A case where an LP model contains no feasible solution even though all constraints are being satisfied; that is, there no are points which satisfy all constraints.
Infeasibility
A condition of an LP model wherein there is a constraint which does not affect the feasible region
Redundancy
A condition of an LP model when the objective function of a linear programming problem can be made infinitely large without violating any of the constraints.
Unbounded
An iterative technique that begins with a feasible solution that is not optimal, but serves as a starting point.
Simplex Method
is a simplex method which consists of the sequence of steps (row operations) performed in moving one basic feasible solution to another.
Iteration
the column in a simplex tableau indicating the quantities of the variables is in a solution
Right Hand Side (RHS)
the variables included in a basic solution.
Basic Variables
a table used to keep track of the calculations made when the simplex method is employed.
Simplex Tableau
the column in any solution to a maximization problem which has the lowest negative value in the last row
Pivot Column
the row in the simplex tableau corresponding to the basic variable that will leave the solution
Pivot Row
elements common to both the pivot column and the rows representing variables in the solution
Intersectional Elements
the element of the simplex tableau that is in both the pivot row and the pivot column.
Pivot
Special cases in Linear Programming (Simplex Method)
Multiple Optimal Solution
Infeasibility
Unbounded Solution
Degeneracy (Tie in pivot row)
Tie for the optimum column
It arises if there is a zero entry in the final tableau where the variable column is located, this indicates an alternative solution
Multiple Optimal Solution
This is a condition resulting from a tie in the test ratios determining the replaced row, which produces a basic variable with a zero value. It may develop when a problem contains redundant constraints, that is, one or more of the constraints in the formulation make it unnecessary
Degeneracy
This is a condition where the greatest positive or least negative entries in the last row have the same values; thus there is a tie in the pivot column. One of two tied columns should be selected arbitrarily. Although one choice may require fewer iterations than the other, there is also no way of knowing this beforehand.
Tie for the optimum column
