Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
PDS #8
| Question | Answer |
|---|---|
| What does Linking Constrain mean | in FLP facility can be used to serve costumers only if it has been opened |
| What are 3 reasons to prone a node | 1, Infeasibility = any feasible solution cannot be achieved anymore 2,Integrality = the delivers a feasible solution by LP-Relaxation 3,Bound = Node can no longer imrpove current best solution |
| What is Dynamic Programming (3) | 1, decomposition a problem into stage-by-stage sequence 2, with problem with complexity of at least n>=2 3,delivers optimal solutions |
| What is idea of Multi-Stage Decision-Making (2) | 1, decisions are dependent on the previous ones 2, i stage influence i+1 stage and so on |
| What is General Objective Function of Multi-Stage Decision-Making | G1(s1) = min ∑ gi(si,xi) gi (si,xi) ... cost or profit created at stage i G1(s1) .. optimal solution / optimal value of stage 1 |
| What are the constrains of General Multi-Stage Decision-Making Model (4) | 1, s i+1 = fi(si,xi) >> Next stage is determined by current one 2,s i+1 ∈ S i+1 >>> Next stage is a valid state 3,xi ∈ Xi(si) >>> xi is a feasible domain 4, si given >>> first stage is given |
| What are Decision Variables in Binary Knapsack Problem in Dynamic Programming (2) | 1, xi∈Xi(si) 2,Xi(si)= { {0,1} if wi<=si {0} of wi>si } ..feasable domain at stage i |
| What is s1 in Binary Knapsack Problem in Dynamic Programming | s1=C .. initial capacity si = remaining capacity at stage i |
| What are 3 constrains in Binary Knapsack Problem in Dynamic Programming | 1, s i+1 = si - wi*x1 2,S i+1 ∈ {0,1,...N} hypotetically possible capacity 3,s1=C is given |
| When is a dynamic programming solution feasible | when ALL THE CONSTRAINS in ALL THE STAGES are respected |
| What are further notation in dynamic programming to make it easier to overview | 1, sequence of decision (x1,x2,...xn) 2, sequence of states (s1,s2,..sn) |
| What are 3 important remark to Multiple-Stage Decision-Making Graphinc | 1, arcs should go all possible ways from sn=C up to si-xi*wi= 0 2, above each arcs there should be profit for only current decision 3,S1 should be written separatly |
| What is Bellman´s Optimality Principle | if the whole paths is optimal, then every remaining part also must bo optimal from state it started |
| What is Forward and Backward Recursion | Forward Recursion = calculate optimal solution / path Backward Recursion = recover other optimals paths if there were ties |
Created by:
semester1.IBWL