# MGOC10H3 Chapter Notes - Chapter 2: Slack Variable, Feasible Region

48 views2 pages
School
Course
Professor Chapter 2 An Introduction to Linear Programming
constraints an equation or inequality that rules out certain combinations of decision variables as feasible solutions
2.1 A Simple Maximization Problem
Problem Formulation
problem formulation (modeling) the process of translating the verbal statement of a problem into a mathematical
statement called the mathematical model
even though every problem has some unique features, most problems also have common features
decision variable a controllable input for a linear programming model
non-negativity constraints a set of constraints that requires all variables to be non-negative
mathematical model a representation of a problem where the objective and all constraint conditions are described by
mathematical expressions
linear programming model (linear program) a mathematical model with a linear objective function, a set of linear
constraints, and non-negative variables
linear functions mathematical expressions in which variables appear in separate terms and are raised to the 1st power
2.2 Graphical Solution Procedure
feasible solution a solution that satisfies all the constraints
feasible region the set of all feasible solutions
Summary of the Graphical Solution Procedure for Maximization Problems
the steps of the graphical solution procedure for a maximization problem are summarized here:
1. prepare a graph of the feasible solutions for each of the constraints
2. determine the feasible region by identifying the solutions that satisfy all the constraints simultaneously
3. draw an objective function line showing the values of the decision variables that yield a specified value of the
objective function
4. move parallel objective function lines toward larger objective function values until further movement would take
the line completely outside the feasible region
5. any feasible solution on the objective function line with the largest value is an optimal solution
Slack Variables
slack variable a variable added to the left-hand side of a less-than-or-equal-to constraint to convert the constraint
into an equality; the value of this variable can usually be interpreted as the amount of unused resource
standard form a linear program in which all the constraints are written as equalities; the optimal solution of the
standard form of a linear program is the same as the optimal solution of the original formulation of the linear program
redundant constraint a constraint that does not affect the feasible region; if a constraint is redundant, it can be
removed from the problem without affecting the feasible region
2.3 Extreme Points and the Optimal Solution
extreme point feasible solution points occurring at the vertices or “corners” of the feasible region; with 2-variable
problems, extreme points are determined by the intersection of the constraint lines
the optimal solution to a linear program can be found at an extreme point of the feasible region
2.5 A Simple Minimization Problem
Summary of the Graphical Solution Procedure for Minimization Problems
the steps of the graphical solution procedure for a minimization problem are summarized here:
1. prepare a graph of the feasible solutions for each of the constraints
2. determine the feasible region by identifying the solutions that satisfy all the constraints simultaneously
3. draw an objective function line showing the values of the decision variables that yield a specified value of the
objective function
4. move parallel objective function lines toward smaller objective function values until further movement would take
the line completely outside the feasible region
5. any feasible solution on the objective function with the smallest value is an optimal solution
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.