College aantekeningen
Engineering Optimization Study Notes - ENGG1400 - UNSW
- Vak
- Instelling
Full set of study notes for engineering optimizations (ENGG1400).
[Meer zien]Voorbeeld 2 van de 7 pagina's
Voorbeeld 2 van de 7 pagina's
In winkelwagen
In winkelwagen
Verkoper
Volgen
callumfisher
Voorbeeld van de inhoud
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
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
√ Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, Bancontact of creditcard voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper callumfisher. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €8,56. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 82265 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen