Class notes
Engineering Optimization Study Notes - ENGG1400 - UNSW
- Course
- Institution
Full set of study notes for engineering optimizations (ENGG1400).
[Show more]
Seller
Follow
callumfisher
Content preview
ENGG1400 Study NotesINTRODUCTION TO OPTIMIZATION
• Optimization is required to maximise profits, reduce costs and improve
service quality
• There is usually a trade-off between supply of resources and demand for
service
• The decision-making process in engineering is known as operations
research
• An optimization problem is composed of:
o Variables
o Objectives
o Constraints
o Sets and parameters
• It is possible for problems to have no constraints or no objectives
• Problems with convex or concave constraint curves are much simpler to
optimize than those with curves which are neither convex or concave
o This is because the local maximum is the same as the global
maximum on a convex function
• Some optimization problems are intractable, meaning they require large
time and data resources for computers
o For example, the route to visit all ‘N’ nodes on a network has (N-1)!
combinations, known as the Travelling Salesman problem
o Unfortunately it would take around 6.4 years to calculate the
possible routes for a network of just 20 nodes
o To compute the optimal route in modern computing, algorithms
have been developed to calculate the result in a fraction of the time
INTRODUCTION TO AMPL
• AMPL software is used to solve real-world decision based problems
• Main topics studied in ENGG1400 include:
o Production problems
o Assignment problems
o Facility location problems
o Network problems
o Vehicle routing problems
o Scheduling problems
• AMPL operates using 3 types of files:
o Data file – contains numerical values
o Model file – contains instructions and coding to formulate an
output
o Script file – executes the output of the problem
LINEAR AND INTEGER PROGRAMMING
• A linear program is an optimization problem with the following
attributes:
o Single objective function
o Objective function is linear in terms of decision variables
, o Constraint is also linear in terms of decision variables
o Decision variables are not restricted to integer values
• Matrix theory is commonly used to output objective functions
• The most efficient way of solving a linear program is with the simplex
algorithm, which is the one of the 20th centuries’ most famous
technological feats
• The constraints of a linear program define a feasible region
• If a problem is unbounded, the objective value can tend to infinity
• The optimal solution to a linear program always occurs at one of the
extreme points of the feasible region (polyhedron)
• If the objective function is parallel to a constraint feasibility region, there
will be an infinite number of solutions
• If the objective function and constraints are both linear, then the problem
can be optimized via standard optimization algorithms
• A program may use binary variables, which can only take up the value of
0 or 1
• An integer program has far less degrees of freedom than a
corresponding linear program, since variables can only take up integer
values
o For a maximise objective, the optimal value for an IP will always be
less than or equal to the optimal value of a corresponding LP
• Variables and constraints can be grouped in a meaningful way using a set
or quantifier
• The index of a variable acts as an identifier for this variable
• The size of a set of indices is known as its cardinality
• The process of using indices to manipulate variables is known as
indexing
• Indices help greatly for writing large sums of variables (summation)
• Quantifiers allow us to index a variable over a set, which is useful for
writing an entire group of variables/constraints in a single line
TRANSPORTATION PROBLEM
• This is a design problem associated with transporting goods to various
locations in the most effective manner (minimal driving distance)
• A firm produces a given supply of goods and the demand for these goods
is distributed randomly between ‘n’ market places. The cheapest manner
(least driving distance) of shipping all goods to the market places from
the factory must be determined.
• If there were 3 factories and 3 market places, the travel cost of each
delivery could be expressed in a 3x3 matrix
• A heuristic is a strategy with a proven strategy which can be undertaken
manually without the use of a computer
o For this problem, the heuristic method would be to start by
prioritizing short links and then assigning low-supply factories to
their nearest market places
• This problem becomes infeasible if supply is less than demand
ASSIGNMENT PROBLEM
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 callumfisher. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $8.99. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
77254 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now