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

48 views2 pages

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