Please enable JavaScript.
Coggle requires JavaScript to display documents.
4363 OPTIMIZATION ANALYTICS - Coggle Diagram
4363 OPTIMIZATION ANALYTICS
Intro
Pitfall
Ill-defined term
Cherry Picking
Undifferentiated middle (most fall middle)
Failure to see system: analysis =is the narrowing of vision
LINEAR PROGRAMING
Resources constraint something something
2 product, each have resources
resources have constraint
Exaple Page 5
assembly hours: 0.1 S +0.2F <=1300
similar to other conditions
properties
infeasibility
redundant constraint
unboundedness
binding constraint = satisfied, touched at optimal
corner points = corner on graph, defied set constraints
ways to find best corner points
best: simplex = find intinal corner, if not optimal move next one
SIMPLEX METHOD
steps
step 1: convert < or > to = (slide 48)
tabular form: 50
Excel Solver
must bring everything so right hand side 0
Duality Theory
SENSITIVITY ANALYSIS
= how much a value change without changing optimal
Means of bounding
objective function = x1+6x2 (slide 35)
if x1<=200, x2<300
figure upper bound constaint
Best bound:
Strong duality
primal = lơer bounds
dual = upper bounds
linear programming: optimal dual = optimal prmal
The solution to the dual problem provides a lower bound to the solution of the primal (minimization) problem
INTERGER PROGRAMMING
Used when var integer, and often in a range. Can be used with binary 1 or 0
Example: slide 6 lesson 4
Binary: slide 14 less 4
easy to implement logical (0,1)
for example, can only choose 2 outa 3 -> x1+x2+x3<=2
LEss 4 includes transportation problem, assignment problem, cutting stock problem
SOLVE DISCRETE OPTIMIZATION PROBLEM: branch and bound
2 main ideas
divide problem into smaller problem - branching
avoid unnecessary work - bounding
in a sense, draw out and divide the thing in different area
DEALING UNCERTAINTY (SECOND HALF)
3 approaches
sensitivity analysis
stochastic optimization: attempt to use known likelihood of outcomes to find sol that works with all outcomes considered
scenario based approach
assumes there are finite future scenarios
robust optimization = mitigate against worst case
Intergral Programming
Branch & Bound Method
OPL
{int} to create a set
instead of many variables, create like Profit[Types]
DEAL LARGE PROBLEM
METHOD 1: Column generation
too many variables
basic idea: solve problem using a subset of DV, then gradually add others in
example: slide 11, lesson 5
how to know when to stop adding
c – yA
c = objective coefficient
y = dual problem
stop when it's non-negative
METHOD 2: cutting plane method
too many constraints
Graph theory (slide 20)
Demonstration example: Network connection problem (slide 24)
Common types of constraints
contain no cycle -> contain at most (Total Edge - 1) edges
Clique constraints --> for every subset, number of clique within it that start and end within S cannot exceed S-1
cutset constraint
METHOD 3: Heuristic Methods
not guaranteed optimality, but "good" solution
basically just search for a number of iteration, then choose best of them
Ways
Tabu Search
?? textbook
Simulated Annealing
move in random directior
GEnetic Algorithms
similar to evolution
operators
reproduction
crossover
mutation