INTRODUCTION TO
OPTIMIZATION
TECHNIQUES
BLOCK VIII: M&S IV
,INTRODUCTION TO OPTIMIZATION TECHNIQUES M&S 4
TABLE OF CONTENT
WOORDENLIJST......................................................................................................................................3
1. HC: INTRODUCTION TO LP, GRAPHICAL METHOD..............................................................................6
1.1 WS: INTRODUCTION TO LP, GRAPHICAL METHOD...........................................................................7
1.2 WS: DEFINING LP PROBLEMS, INTEGER PROGRAMMING.................................................................9
2.1 WS: INTRODUCTION TO SIMPLEX...................................................................................................11
3.1 WS: SIMPLEX METHOD...................................................................................................................13
3.2 WS: SIMPLEX METHOD...................................................................................................................18
4.1 WS: BIG M METHOD.......................................................................................................................21
6.1. WS: TRANSPORTATION PROBLEM.................................................................................................23
6.2. WS: SHORTEST PATH PROBLEM.....................................................................................................25
7.1. WS: MAXIMUM FLOW ALGORITHM..............................................................................................27
7.2 WS: MIN COST FLOW PROBLEM.....................................................................................................28
8. WS: TRAVELING SALESMAN PROBLEM.............................................................................................30
2
AMSTERDAM UNIVERSITY OF APPLIED SCIENCES
,INTRODUCTION TO OPTIMIZATION TECHNIQUES M&S 4
WOORDENLIJST
WEEK 1
TERM EXPLANATION
A method to achieve the best outcome in a mathematical
• Linear Programming
model whose requirements are represented by linear
Problem
relationships.
Mathematical function of the decision variables which
• Objective
represents a measure of performance.
Variables which represent the decisions to be made whose
• Decision Variable
values need to be determined.
Mathematical expression of the restrictions on the values
• Constraint
that can be assigned to the decision variables.
• Feasible Solution A solution for which all constraints are satisfied.
• Infeasible Solution A solution for which at least one constraint in violated.
• Feasible Region The collection of all feasible solutions.
Feasible solution that has the most favorable value of the
• Optimal Solution
objective.
• Corner-Point Feasible
Solution that lies at the corner of the feasible region.
Solution
WEEK 1 WS 2
TERM EXPLANATION
• Integer A whole number e.g. 1, 7 or 420.
• Binary Variable Whole number equal to 0 or 1.
• BIP Problem Binary Integer Problem: LP Problem where variables are
binary.
• Integer LP Problem LP Problem where variables are integer.
• Mixed Integer LP LP Problem where some variables are integer.
Problem
• Node Vertices or points in a network problem, shown by circles.
• Directed Arc Line or edge between two nodes , where the flow is allowed
in only one direction.
• Undirected Arc Line or edge between two nodes , where the flow is allowed
in either direction.
• Path A chain of directed arcs, where the terminal node of each
arc is the initial node of the succeeding arc.
• Supply Fixed amount of units to be distributed to the destinations,
the entire supply must be distributed to the destinations.
• Demand Fixed amount of units to be received from the sources, the
entire demand must be received from the sources.
WEEK 2
TERM EXPLANATION
The tabular form of the simplex records all essential
information, namely:
• Simplex Tableau (1) The coefficients of the variables.
(2) The solutions on the right hand sides of the equations.
(3) The basic variable appearing on each equation.
An augmented solution is a solution for the original
variables (the decision variables) that has been augmented
• Augmented Solution
(aangevuld) by the corresponding values of the slack
variables.
3
AMSTERDAM UNIVERSITY OF APPLIED SCIENCES
, INTRODUCTION TO OPTIMIZATION TECHNIQUES M&S 4
Represents unused resources to convert inequality ( < ) to
• Slack Variable
equality ( = ) constraints.
• Basic Variable A variable with a certain value
A variable with value equal to 0, this restricts the search to
• Nonbasic Variable
corner point solutions.
WEEK 3
TERM EXPLANATION
Column with one cell equal to 1 and all other values 0. A
• Pivot Column new pivot column is determined by the most negative
number in row (0).
Test performed to determine the
pivot row, calculated by (see RHS
• Minimum Ratio Test
formula). The lowest value of this Pivot Column
calculation is the new pivot.
An element in the Simplex Tableau that forms the central
element in the pivot operation. It is the intersection of the
• Pivot
pivot column and the pivot row, and identifies the entering
variable and exit variable at mean time.
Test to see whether there is an improvement in the
• Optimality Test objective possible . If there are no negative numbers in row
(o), the optimum is reached and the procedure stops.
WEEK 4
TERM EXPLANATION
•M Very large positive number.
Procedure to handle ≥ and = sign in the constraints of an LP
• Big M Method
Problem.
Subtracted from the artificial problem for each ≥ constraint, 𝒙𝒋 ≥
• Surplus Variable
𝟎.
Added to the artificial problem in each ≥ constraint, x i ≥ 0.
• Artificial Variable Always comes together with adding penalty term −M x i to the
objective function.
Added to the objective function in case a of a ≥ and = sign in a
• Penalty Term
constraint, −M x i .
WEEK 5 (???)
TERM EXPLANATION
The analysis done after an optimal solution is obtained for
• Postoptimality analysis
the initial version of the model.
¿
The shadow price for resource i (denoted by y i ) measures
the marginal value of this resource, i.e. the rate at which Z
could be increased by (slightly) increasing the amount of
• Shadow price
this resource (b i) being made available. The simplex
¿
method identifies this shadow price by y i = coefficient of
the i th slack variable in row o of the final simplex tableau.
• Binding constraints Constraints that hold with equality at the optimal solution.
A main purpose of sensitivity analysis is to identify the
• Sensitivity analysis
sensitive parameters.
Those parameters that cannot be changed without
• Sensitive parameters
changing the optimal solution.
• Allowable range For any c j, its allowable range is the range of values for
this coefficient over which the current optimal solution
remains optimal, assuming no change in the other
4
AMSTERDAM UNIVERSITY OF APPLIED SCIENCES
OPTIMIZATION
TECHNIQUES
BLOCK VIII: M&S IV
,INTRODUCTION TO OPTIMIZATION TECHNIQUES M&S 4
TABLE OF CONTENT
WOORDENLIJST......................................................................................................................................3
1. HC: INTRODUCTION TO LP, GRAPHICAL METHOD..............................................................................6
1.1 WS: INTRODUCTION TO LP, GRAPHICAL METHOD...........................................................................7
1.2 WS: DEFINING LP PROBLEMS, INTEGER PROGRAMMING.................................................................9
2.1 WS: INTRODUCTION TO SIMPLEX...................................................................................................11
3.1 WS: SIMPLEX METHOD...................................................................................................................13
3.2 WS: SIMPLEX METHOD...................................................................................................................18
4.1 WS: BIG M METHOD.......................................................................................................................21
6.1. WS: TRANSPORTATION PROBLEM.................................................................................................23
6.2. WS: SHORTEST PATH PROBLEM.....................................................................................................25
7.1. WS: MAXIMUM FLOW ALGORITHM..............................................................................................27
7.2 WS: MIN COST FLOW PROBLEM.....................................................................................................28
8. WS: TRAVELING SALESMAN PROBLEM.............................................................................................30
2
AMSTERDAM UNIVERSITY OF APPLIED SCIENCES
,INTRODUCTION TO OPTIMIZATION TECHNIQUES M&S 4
WOORDENLIJST
WEEK 1
TERM EXPLANATION
A method to achieve the best outcome in a mathematical
• Linear Programming
model whose requirements are represented by linear
Problem
relationships.
Mathematical function of the decision variables which
• Objective
represents a measure of performance.
Variables which represent the decisions to be made whose
• Decision Variable
values need to be determined.
Mathematical expression of the restrictions on the values
• Constraint
that can be assigned to the decision variables.
• Feasible Solution A solution for which all constraints are satisfied.
• Infeasible Solution A solution for which at least one constraint in violated.
• Feasible Region The collection of all feasible solutions.
Feasible solution that has the most favorable value of the
• Optimal Solution
objective.
• Corner-Point Feasible
Solution that lies at the corner of the feasible region.
Solution
WEEK 1 WS 2
TERM EXPLANATION
• Integer A whole number e.g. 1, 7 or 420.
• Binary Variable Whole number equal to 0 or 1.
• BIP Problem Binary Integer Problem: LP Problem where variables are
binary.
• Integer LP Problem LP Problem where variables are integer.
• Mixed Integer LP LP Problem where some variables are integer.
Problem
• Node Vertices or points in a network problem, shown by circles.
• Directed Arc Line or edge between two nodes , where the flow is allowed
in only one direction.
• Undirected Arc Line or edge between two nodes , where the flow is allowed
in either direction.
• Path A chain of directed arcs, where the terminal node of each
arc is the initial node of the succeeding arc.
• Supply Fixed amount of units to be distributed to the destinations,
the entire supply must be distributed to the destinations.
• Demand Fixed amount of units to be received from the sources, the
entire demand must be received from the sources.
WEEK 2
TERM EXPLANATION
The tabular form of the simplex records all essential
information, namely:
• Simplex Tableau (1) The coefficients of the variables.
(2) The solutions on the right hand sides of the equations.
(3) The basic variable appearing on each equation.
An augmented solution is a solution for the original
variables (the decision variables) that has been augmented
• Augmented Solution
(aangevuld) by the corresponding values of the slack
variables.
3
AMSTERDAM UNIVERSITY OF APPLIED SCIENCES
, INTRODUCTION TO OPTIMIZATION TECHNIQUES M&S 4
Represents unused resources to convert inequality ( < ) to
• Slack Variable
equality ( = ) constraints.
• Basic Variable A variable with a certain value
A variable with value equal to 0, this restricts the search to
• Nonbasic Variable
corner point solutions.
WEEK 3
TERM EXPLANATION
Column with one cell equal to 1 and all other values 0. A
• Pivot Column new pivot column is determined by the most negative
number in row (0).
Test performed to determine the
pivot row, calculated by (see RHS
• Minimum Ratio Test
formula). The lowest value of this Pivot Column
calculation is the new pivot.
An element in the Simplex Tableau that forms the central
element in the pivot operation. It is the intersection of the
• Pivot
pivot column and the pivot row, and identifies the entering
variable and exit variable at mean time.
Test to see whether there is an improvement in the
• Optimality Test objective possible . If there are no negative numbers in row
(o), the optimum is reached and the procedure stops.
WEEK 4
TERM EXPLANATION
•M Very large positive number.
Procedure to handle ≥ and = sign in the constraints of an LP
• Big M Method
Problem.
Subtracted from the artificial problem for each ≥ constraint, 𝒙𝒋 ≥
• Surplus Variable
𝟎.
Added to the artificial problem in each ≥ constraint, x i ≥ 0.
• Artificial Variable Always comes together with adding penalty term −M x i to the
objective function.
Added to the objective function in case a of a ≥ and = sign in a
• Penalty Term
constraint, −M x i .
WEEK 5 (???)
TERM EXPLANATION
The analysis done after an optimal solution is obtained for
• Postoptimality analysis
the initial version of the model.
¿
The shadow price for resource i (denoted by y i ) measures
the marginal value of this resource, i.e. the rate at which Z
could be increased by (slightly) increasing the amount of
• Shadow price
this resource (b i) being made available. The simplex
¿
method identifies this shadow price by y i = coefficient of
the i th slack variable in row o of the final simplex tableau.
• Binding constraints Constraints that hold with equality at the optimal solution.
A main purpose of sensitivity analysis is to identify the
• Sensitivity analysis
sensitive parameters.
Those parameters that cannot be changed without
• Sensitive parameters
changing the optimal solution.
• Allowable range For any c j, its allowable range is the range of values for
this coefficient over which the current optimal solution
remains optimal, assuming no change in the other
4
AMSTERDAM UNIVERSITY OF APPLIED SCIENCES
