Summary M&S4: Introduction to Optimization Techniques
7 purchases
Course
M&S4: Introduction to Optimization Techniques
Institution
Hogeschool Van Amsterdam (HvA)
It is a summary of M&S4: Introduction to Optimization Techniques. It contains all the theoretical knowledge needed for the exam. Included are also templates which can be used to fill in to execute the different techniques.
Subjects Subject Details
Linear Programming o Linear Programming (LP) Problem
o Graphical Method
Simplex Method - Simplex Tableau
- Simplex Method
- Big M Method
Network Problems Terminology of Network Problems
Transportation Problem (week 6)
o North-west Corner Method (week 6)
Shortest Path (week 6)
o Dijkstra’s Algorithm
o Hillier and Lieberman Method
Maximum Flow Problem (week 7)
Minimum Cost Problem (week 7)
Travelling Salesman Problem (week 8)
o Nearest Neighbor
Definitions - Terms with explanation (week 1 – week 8)
Templates (which can be 1. Simplex Tableau
used for the exam) 2. Dijkstra’s Algorithm
3. Hillier and Lieberman Method
4. Minimum Cost Flow Problem
5. Nearest Neighbor Algorithm
1
, M&S 4
Introduction to Optimization Techniques
Linear Programming
Linear Programming is maximizing or minimizing a linear goal
function subject to linear constraints.
The LP Problem is allocating limited resources among competing activities in a best possible
way.
For example. Hit the target by using maximum 3 arrows form minimal 5 meters distance.
Decision Variables
o Which units do you change in order to reach your objective?
o For example. x 1 , x 2
Objective Function
o Goal of the problem.
o Maximum or minimum.
o For example. Maximize profit or minimize costs.
Constraints
o Restrictions or limitations on the decision variables.
o For example. 5 x 1+ 9 x 2 ≤35 .
Steps in Linear Programming
1. Determine the variables.
2. Formulate the objective.
3. Write the constraints.
4. Solve the LP problem.
Linear Programming – Graphical Method
The graphical method is best explained using an example.
Acme Bicycle Company (ABC) produces two kinds of bicycles:
- Mountain bikes; profit €15 per bicycle. X1
- Street racers; profit €10 per bicycle. X2
Which amount of each type of bicycle should be produced to maximize profit?
Two teams of producers with maximum production rate: 2 mountain bikes per day and 3
street racers per day respectively.
Metal finishing machine requires the same amount of time for both type of bikes and can
produce in total 4 bikes per day, of either type.
1. Determine the variables.
x 1 = Amount of produced mountain bikes per day.
x 2 = Amount of produced street racers per day.
2. Give the objective function.
Maximum z=15 x 1+10 x 2.
3. Formulate the constraints.
x1 ≤ 2 Mountain bike production limit.
x2≤ 3 Street racers production limit.
x 1+ x2 ≤ 4 Metal finishing machine production limit.
x1, x2≥ 0 There can be no negative production.
2
, M&S 4
Introduction to Optimization Techniques
The limiting value of each constraint is shown as a line. Each constraint
eliminates part of the plan. See graph on the right.
Terminology solution space
Terminology for possible solutions:
o Feasible solution; all constraints are satisfied.
o Optimal solution; feasible solution with most favorable value
of the objective.
o Corner-point feasible (CPF) solution; solution at the corner of the feasible
region.
Find the optimum
The optimum is always a corner point. Two ways to find the optimum:
Option 1. Calculate the objective value for each CPF. The most favorable outcome of the
objective is the optimum.
a. Calculate the intersections of the constraints and their objective value.
Option 2. Use the objective line. The optimum is where the objective function
has only one point in the feasible region left when moving it from left to right.
1. Choose a random number. (Hint; choose an easy multiplier of both
coefficients.
For example. Objective z=15 x 1+10 x 2. Easy to multiplier is 30.
2. Draw the objective line for the chosen number.
For example. z (2,0 )=30∧z ( 0,3 )=3.
3. Shift the objective line such that the objective line touches only
one point of the feasible region, this will be the optimum.
For example. z (2,2 )=50.
Excel Solver - Brightspace
How to use the LP solver in Excel, see video on Brightspace.
3
, M&S 4
Introduction to Optimization Techniques
Special types of LP problems
1. Pure integer programming. All variables integer.
2. Mixed integer programming. Some but not all variables integer.
3. Binary integer programming. All variables are binary (0 or 1).
An integer solution can never be better than the LP solution and is usually a worse solution.
A rounded optimal solution of the non-integer problem is not necessary the optimal solution
of the integer problem. The graphical method does not always lead to the optimal integer
solution.
When integer programming in Excel, go to data tab Analyze group solver.
Example 1. Production parts
Step 1. Variables:
x 1 = Amount of produced parts A.
x 2 = Amount of produced parts B.
Step 2. Objective: Max. z=30 x 1+ 20 x 2
Step 3. Constraints:
2 x1 +1 x 2 ≤ 140 Max. available capacity for drilling.
1 x1 +2 x 2 ≤ 160 Max. available capacity for
1 x1 +1 x2 ≤ 900 Max. available capacity for
x1, x2≥ 0 There can be no negative production.
Example 2. Rolls Royce
Step 1. Variables:
x 1 = Number of aircraft engines.
x 2 = Number of train engines.
Step 2. Objective: Max. z=14 x 1 +12 x 2
Step 3. Constraints:
2 x1 +3 x 2 ≤ 12 Wiring hours production limit.
6 x 1+ 5 x 2 ≤30 Assembly hours production limit.
x1, x2≥ 0 There can be no negative production.
Example 3. Copier Machine
Step 1. Variables:
x 1 = Number of high-speed copiers.
x 2 = Number of low speed copiers.
Step 2. Objective: Min. z=6,000 x 1+ 4,000 x 2
Step 3. Constraints:
x 1+ x2 ≥6 At least six copiers.
x1≥ 1 At least one high speed copier.
20,000 x 1+10,000 x 2 ≥ 75,000 A and B need to handle at least 75,000 per day.
x1, x2≥ 0 There can be no negative production.
4
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller CocodB. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $11.73. You're not tied to anything after your purchase.
