HAND OUT PENELITIAN OPERASIONAL II
Oleh : Tim Dosen Penelitian Operasional Program Studi Teknik Industri
Fakultas Teknik Universitas Wijaya Putra 2009
Game Theory The study of rational behavior among interdependent agents Agents have a common interest to make the pie as large as possible, but
Agents have competing interests to maximize their own share of the pie. An agent’s rational decisions require anticipating rivals’ responses These expectations are not perfect, so uncertainty is a necessary feature of games
Prisoner’s Dilemma During the Stalinist Era Russian Conductor studying Tchaikovsky score on the train to Minsk Arrested by the KGB Thrown into prison For three days, he is told nothing ………….Then……………
Prisoner’s Dilemma “We have your friend Tchaikovsky and he is starting to talk”
Should the conductor confess?
Prisoner’s Dilemma Tchaikovsky Confess
Don’t Confess
Conductor
Confess
Don’t Confess
( -8,
-8)
( -15, 0)
( 0, -15)
( -1, -1)
Prisoner’s Dilemma Tchaikovsky Don’t Confess
Confess Conductor
Confess
Don’t Confess
( -8,
-8)
( -15, 0)
( 0, -15)
( -1, -1)
Prisoner’s Dilemma Tchaikovsky Confess
Don’t Confess
Conductor
Confess
Don’t Confess
( -8,
-8)
( -15, 0)
( 0, -15)
( -1, -1)
Prisoner’s Dilemma Conclusion:
The Conductor will confess
And Tchaikovsky?
Prisoner’s Dilemma Tchaikovsky Confess
Don’t Confess
Conductor
Confess
Don’t Confess
( -8,
-8)
( -15, 0)
( 0, -15)
( -1, -1)
Prisoner’s Dilemma Tchaikovsky Confess
Don’t Confess
Conductor
Confess
Don’t Confess
( -8,
-8)
( -15, 0)
( 0, -15)
( -1, -1)
Prisoner’s Dilemma Conclusion: Tchaikovsky confesses also Both get 8 years, even though if they cooperated, they could get off with one year each For both, confession is a dominant strategy: a strategy that yields a better outcome regardless of the opponent’s choice
Prisoner’s Dilemma What would the Conductor and Tchaikovsky decide if they could negotiate? They could both become better off if they reached the cooperative solution…. which is why police interrogate suspects in separate rooms. Equilibrium need not be efficient. Noncooperative equilibrium in the Prisoner’s dilemma results in a solution that is not the best possible outcome for the parties.
Equilibrium Nash Equilibrium: Neither player has an incentive to change strategy, given the other player’s choice Both confess is a Nash Equilibrium Both don’t confess is not a Nash Equilibrium, rival will always want to renege
Dominant Firm Game Two firms, one large and one small
Either firm can announce an output level (lead) or else wait to see what the rival does and then produce an amount that does not saturate the market.
Dominant Firm Game Dominant Lead
Follow
Subordinate
Lead
Follow
( 0.5,
4)
( 1, 8)
( 3, 2)
( 0.5, 1)
Dominant Firm Game Dominant Lead
Follow
Subordinate
Lead
Follow
( 0.5,
4)
( 1, 8)
( 3, 2)
( 0.5, 1)
Dominant Firm Game Dominant Lead
Follow
Subordinate
Lead
Follow
( 0.5,
4)
( 1, 8)
( 3, 2)
( 0.5, 1)
Dominant Firm Game Conclusion: Dominant Firm will always lead…..
But what about the Subordinate firm?
Dominant Firm Game Dominant Lead
Follow
Subordinate
Lead
Follow
( 0.5,
4)
( 1, 8)
( 3, 2)
( 0.5, 1)
Dominant Firm Game Dominant Lead
Follow
Subordinate
Lead
Follow
( 0.5,
4)
( 1, 8)
( 3, 2)
( 0.5, 1)
Dominant Firm Game Conclusion: No dominant strategy for the Subordinate firm. Does this mean we cannot predict what they will do?
Dominant Firm Game Dominant Lead
Follow
Subordinate
Lead
Follow
( 0.5,
4)
( 1 , 8)
( 3, 2)
( 0.5, 1)
Dominant Firm Game Conclusion: Subordinate firm will always follow, because dominant firm will always lead.
Equilibrium Nash Equilibrium: Neither player has an incentive to change strategy, given the other player’s choice Dominant: Lead & Subordinate Follow is a Nash Equilibrium
A player’s best option may be dictated by anticipating the rival’s best option
Timing and Ending Two Stage Game between A and B who are dividing $1.00 1)
2)
Player A moves first and proposes how to split the dollar. Player B either accepts the split in which case the game ends, or we move to round 2. The pie drops to $.90. Player B proposes a split. Player A accepts or the game ends and both get 0.
Timing and Ending What should A do?
Timing and Ending The timing of the end of the game can dictate the strategy employed. If the game went past round 2, A’s strategy would change.
Go back to Prisoner’s Dilemma: Is there a way to generate the cooperative solution? Tchaikovsky Confess
Don’tConfess
Conductor
Confess
Don’tConfess
( -8,
-8)
( 0, -15)
( -15, 0)
( -1, -1)
Go back to Prisoner’s Dilemma: Is there a way to generate the cooperative solution? Not a Nash Equilibrium If Conductor commits to “Don’t Confess”, Tchaikovsky has an incentive to confess If Tchaikovsky commits to “Don’t Confess”, Conductor has an incentive to confess Role of a contract—to commit parties to actions they would not undertake voluntarily Alternative: Implied contract if there were a long relationship between the parties—(partners in crime) are more likely to back each other
Application to Collective Bargaining Two agent game Uncertainty Each party has to anticipate what the other will do Time limit matters Ability to contract affects outcome A long, continuing relationship can enhance the efficiency of the outcome
Complicating the game Suppose there is a range of outcomes Wage WM : Firm maximum wage Wm : Union minimum wage Union WM Contract Zone Wm Firm
Where we end up in the contract zone depends on bargaining power Bargaining power depends on
Alternative opportunities if no bargain is reached (outside option)
Relative cost of delay
Union: alternative employment Firm: Substitute for union workers
Union: Strike fund Firm: Inventory, strength of sales demand
Commitment strategy
Extent to which you can make the other party believe you will not budge
Example of a more complicated Bargaining Simulation Two teams: Union(U); Management (M) Each team gets a suit of 13 cards The cards correspond to wage thresholds: Wage 15 14 13 12 11 10 9 8 7 6
M 2 3-4 5-7 8-10 J-K A
U
A J-K 8-10 5-7 3-4 2
Each team draws one card that will set their reservation wage. This must not be shown to the other team except for the full information game. Through the remaining rounds, teams will reveal additional cards at random Teams can reveal other cards if they wish Teams can make statements about their bargaining objectives to the other team
Bargaining Techniques
Distributive Bargaining: View bargaining as a zero sum game
—split of the pie: what one party gains, the other loses Example—our game Often accompanied by pressure tactics Threats Bluffs Bullying/
Bargaining Techniques
Interest-Based Bargaining
Attempt to arrive at efficient outcome No relevant information privileged Focus on solving mutual problem of making the firm as successful as possible Requires long-standing bargaining relationship between parties
Bargaining Techniques
Principled Negotiations
Both parties start with perceptions of the economic climate and their goals Alternative mechanisms to reach these goals are presented Options are evaluated against some objective criteria or by a third party expert No private information
Bargaining Techniques
Collective Bargaining by Objectives
Each party lists its objectives Objectives are prioritized Areas of agreement are identified, while the remaining areas of disagreement are ranked by their importance to the parties Parties can withhold information
Bargaining Techniques
Note the similarity between these techniques and the games
Role of information Role of history Role of the other party’s objectives, actions Role of cooperative vs competitive bargaining environment
Game Theory • Developed to explain the optimal strategy in two-person interactions. • Initially, von Neumann and Morganstern – Zero-sum games
• John Nash – Nonzero-sum games
• Harsanyi, Selten – Incomplete information
An example: Big Monkey and Little Monkey • Monkeys usually eat ground-level fruit • Occasionally climb a tree to get a coconut (1 per tree) • A Coconut yields 10 Calories • Big Monkey expends 2 Calories climbing the tree. • Little Monkey expends 0 Calories climbing the tree.
An example: Big Monkey and Little Monkey • If BM climbs the tree – BM gets 6 C, LM gets 4 C – LM eats some before BM gets down
• If LM climbs the tree – BM gets 9 C, LM gets 1 C – BM eats almost all before LM gets down
• If both climb the tree – BM gets 7 C, LM gets 3 C – BM hogs coconut
• How should the monkeys each act so as to maximize their own calorie gain?
An example: Big Monkey and Little Monkey • Assume BM decides first – Two choices: wait or climb
• LM has four choices: – Always wait, always climb, same as BM, opposite of BM.
• These choices are called actions – A sequence of actions is called a strategy
An example: Big Monkey and Little Monkey
Little monkey
c
w
Big monkey w
c
w
c
0,0 9,1 6-2,4 7-2,3 What should Big Monkey do? • If BM waits, LM will climb – BM gets 9 • If BM climbs, LM will wait – BM gets 4 • BM should wait. • What about LM? • OppositeofBM(eventhoughwe’llnevergettotherightside of the tree)
An example: Big Monkey and Little Monkey • These strategies (w and cw) are called best responses. – Given what the other guy is doing, this is the best thing to do.
• A solution where everyone is playing a best response is called a Nash equilibrium. – No one can unilaterally change and improve things.
• This representation of a game is called extensive form.
An example: Big Monkey and Little Monkey • What if the monkeys have to decide simultaneously?
Little monkey
c
w
Big monkey w 0,0
c
w
c
9,1 6-2,4 7-2,3
Now Little Monkey has to choose before he sees Big Monkey move Two Nash equilibria (c,w), (w,c) Also a third Nash equilibrium: Big Monkey chooses between c & w with probability 0.5 (mixed strategy)
An example: Big Monkey and Little Monkey • It can often be easier to analyze a game through a different representation, called normal form Little Monkey
Big Monkey
c
v
c
5,3
4,4
v
9,1
0,0
Choosing Strategies • Inthesimultaneousgame,it’shardertosee what each monkey should do – Mixed strategy is optimal.
• Trick: How can a monkey maximize its payoff, given that it knows the other monkeys will play a Nash strategy? • Oftentimes, other techniques can be used to prune the number of possible actions.
Eliminating Dominated Strategies • The first step is to eliminate actions that are worse than another action, no matter what. Big monkey
c
w
w Little monkey 0,0 Little Monkey will Never choose this path.
c
w
c
9,1 6-2,4 7-2,3 Or this one
w
c
9,1
4,4
We can see that Big Monkey will always choose w. So the tree reduces to: 9,1
Eliminating Dominated Strategies • We can also use this technique in normalform games: Column a
b
a
9,1
4,4
b
5,3
0,0
Row
Eliminating Dominated Strategies • We can also use this technique in normalform games: a
b
a
9,1
4,4
b
5,3
0,0
For any column action, row will prefer a.
Eliminating Dominated Strategies • We can also use this technique in normalform games: a
b
a
9,1
4,4
b
5,3
0,0
Given that row will pick a, column will pick b. (a,b) is the unique Nash equilibrium.
Prisoner’sDilemma • Each player can cooperate or defect Column
cooperate
defect
cooperate
-1,-1
-10,0
defect
0,-10
-8,-8
Row
Prisoner’sDilemma • Each player can cooperate or defect Column
cooperate
defect
cooperate
-1,-1
-10,0
defect
0,-10
-8,-8
Row
Defecting is a dominant strategy for row
Prisoner’sDilemma • Each player can cooperate or defect Column
cooperate
defect
cooperate
-1,-1
-10,0
defect
0,-10
-8,-8
Row
Defecting is also a dominant strategy for column
Prisoner’sDilemma • Even though both players would be better off cooperating, mutual defection is the dominant strategy. • What drives this? – One-shot game – Inability to trust your opponent – Perfect rationality
Prisoner’sDilemma • Relevant to: – – – –
Arms negotiations Online Payment Product descriptions Workplace relations
• How do players escape this dilemma? – Play repeatedly – Findawayto‘guarantee’cooperation – Change payment structure
Tragedy of the Commons • Game theory can be used to explain overuse of shared resources. • ExtendthePrisoner’sDilemmatomorethantwo players. • A cow costs a dollars and can be grazed on common land. • The value of milk produced (f(c) ) depends on the number of cows on the common land. – Per cow: f(c) / c
Tragedy of the Commons • To maximize total wealth of the entire village: max f(c) – ac. – Maximized when marginal product = a – Adding another cow is exactly equal to the cost of the cow.
• What if each villager gets to decide whether to add a cow? • Each villager will add a cow as long as the cost of adding that cow to that villager is outweighed by the gain in milk.
Tragedy of the Commons • When a villager adds a cow: – Output goes from f(c) /c to f(c+1) / (c+1) – Cost is a – Notice: change in output to each farmer is less than global change in output.
• Each villager will add cows until output- cost = 0. • Problem: each villager is making a local decision (will I gain by adding cows), but creating a net global effect (everyone suffers)
Tragedy of the Commons • Problem: cost of maintenance is externalized – Farmersdon’tadequatelypayfortheirimpact. – Resources are overused due to inaccurate estimates of cost.
• Relevant to: – – – –
IT budgeting Bandwidth and resource usage, spam Shared communication channels Environmental laws, overfishing, whaling, pollution, etc.
Avoiding Tragedy of the Commons • Private ownership – Prevents TOC, but may have other negative effects.
• Social rules/norms, external control – Nice if they can be enforced.
• Taxation – Try to internalize costs; accounting system needed.
• Solutions require changing the rules of the game – Change individual payoffs – Mechanism design
Coming next time • How to select an optimal strategy • How to deal with incomplete information • How to handle multi-stage games
Program Dinamis (Dynamic Programming)
Program Dinamis • Program Dinamis (dynamic programming): metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan.
Pada penyelesaian persoalan dengan metode ini: 1. terdapat sejumlah berhingga pilihan yang mungkin, 2. solusi pada setiap tahap dibangun dari hasil solusi tahap sebelumnya, 3. kita menggunakan persyaratan optimasi dan kendala untuk membatasi sejumlah pilihan yang harus dipertimbangkan pada suatu tahap.
Tinjau grafik di bawah ini. Kita ingin menemukan lintasan terpendek dari 1 ke 10. 7 2
5 4
2
3
1 4
8
6 6
4 1
3
2
3
4
3
6
9
3 1
4
4 7
5
10
3
3
4
Prinsip Optimalitas • Pada program dinamis, rangkaian keputusan yang optimal dibuat dengan menggunakan Prinsip Optimalitas. • Prinsip Optimalitas: jika solusi total optimal, maka bagian solusi sampai tahap ke-k juga optimal.
• Prinsip optimalitas berarti bahwa jika kita bekerja dari tahap k ke tahap k + 1, kita dapat menggunakan hasil optimal dari tahap k tanpa harus kembali ke tahap awal. • ongkos pada tahap k +1 = (ongkos yang dihasilkan pada tahap k ) + (ongkos dari tahap k ke tahap k + 1)
• Dengan prinsip optimalitas ini dijamin bahwa pengambilan keputusan pada suatu tahap adalah keputusan yang benar untuk tahap-tahap selanjutnya. • Pada metode greedy hanya satu rangkaian keputusan yang pernah dihasilkan, sedangkan pada metode program dinamis lebih dari satu rangkaian keputusan. Hanya rangkaian keputusan yang memenuhi prinsip optimalitas yang akan dihasilkan.
Karakteristik Persoalan Program Dinamis 1. Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya diambil satu keputusan.
2. Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan dengan tahap tersebut. Secara umum, status merupakan bermacam kemungkinan masukan yang ada pada tahap tersebut.
Grafik multitahap (multistage graph). Tiap simpul di dalam grafik tersebut menyatakan status, sedangkan V1, V2, … menyatakan tahap. V1
V2
V3
V4
V5
2 9 6 3 7 1
10
4 8 11
5
12
3. Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan dari status yang bersangkutan ke status berikutnya pada tahap berikutnya. 4. Ongkos (cost) pada suatu tahap meningkat secara teratur (steadily) dengan bertambahnya jumlah tahapan. 5. Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap yang sudah berjalan dan ongkos pada tahap tersebut.
6. Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan yang dilakukan pada tahap sebelumnya. 7. Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap status pada tahap k memberikan keputusan terbaik untuk setiap status pada tahap k + 1. 8. Prinsip optimalitas berlaku pada persoalan tersebut.
Dua pendekatan PD • Dua pendekatan yang digunakan dalam PD: maju (forward atau backward) dan mundur (up-down atau bottom-up).
•
Misalkan x1, x2, …, xn menyatakan peubah (variable) keputusan yang harus dibuat masing-masing untuk tahap 1, 2, …, n. Maka,
1. Program dinamis maju. Program dinamis bergerak mulai dari tahap 1, terus maju ke tahap 2, 3, dan seterusnya sampai tahap n. Runtunan peubah keputusan adalah x1, x2, …, xn.
2. Program dinamis mundur. Program dinamis bergerak mulai dari tahap n, terus mundur ke tahap n – 1, n – 2, dan seterusnya sampai tahap 1. Runtunan peubah keputusan adalah xn, xn-1, …, x1.
Langkah-langkah Pengembangan Algoritma Program Dinamis 1. Karakteristikkan struktur solusi optimal. 2. Definisikan secara rekursif nilai solusi optimal. 3. Hitung nilai solusi optimal secara maju atau mundur. 4. Konstruksi solusi optimal.
Lintasan Terpendek (Shortest Path) • Tentukan lintasan terpendek dari simpul 1 ke simpul 10: 7 2
5 4
2
3
1 4
8
6 6
4 1
3
2
3
4
3
6
9
3 1
4
4 7
5
10
3
3
4
Penyelesaian dengan Program Dinamis Mundur • Misalkan x1, x2, …, x4 adalah simpulsimpul yang dikunjungi pada tahap k (k = 1, 2, 3, 4). • Maka rute yang dilalui adalah 1x1x2x3x4 , yang dalam hal ini x4 = 10.
Pada persoalan ini, • Tahap (k) adalah proses memilih simpul tujuan berikutnya (ada 4 tahap). • Status (s) yang berhubungan dengan masing-masing tahap adalah simpulsimpul di dalam grafik.
Relasi rekurens berikut menyatakan lintasan terpendek dari status s ke x4 pada tahap k:
f ( s) c 4
(basis)
sx4
f ( s) min{c f ( x )}, k
xk
sxk
k 1
k
(rekurens)
k = 1, 2, 3 Keterangan: a. xk : peubah keputusan pada tahap k (k = 1, 2, 3). b. c : bobot (cost) sisi dari s ke xk c. fk(s, xk) : total bobot lintasan dari s ke xk d. fk(s) : nilai minimum dari fk(s, xk) sxk
Tujuan program dinamis mundur: mendapatkan f1(1) dengan cara mencari f4(s), f3(s), f2(s) terlebih dahulu.
Tahap 4:
f ( s) c 4
s 8 9
sx4
Solusi Optimum f4(s) x4* 3 10 4 10
Catatan: xk* adalah nilai xk yang meminimumkan fk(s, xk).
Tahap 3: f ( s) min{c f ( x )} 3
x3 s 5 6 7
x3
sx3
4
f3(s, x3) = cs,x3 + f4(x3) 8 9 4 8 9 7 6 7
3
Solusi Optimum f3(s) x3* 4 8 7 9 6 8
Tahap 2: f ( s) min{c f ( x )} 2
x2 s 2 3 4
x2
sx2
3
f2(s, x2) = cs,x2 + f3(x2) 5 6 7 11 11 12 7 9 10 8 8 11
2
Solusi Optimum f2(s) x2* 11 5 atau 6 7 5 8 5 atau 6
Tahap 1: f ( s) min{c f ( x )} 1
x1 s 1
x1
sx1
2
1
f1(s, x1) = cs,x1 + f2(x1) 2 3 4 13 11 11
Solusi Optimum f1(s) x1* 11 3 atau 4
Solusi optimum dapat dibaca pada tabel di bawah ini: x1
x2
x3
x4
3
5
8
10
Panjang Lintasan Terpendek 11
5
8
10
11
6
9
10
11
1 4
Jadi ada tiga lintasan terpendek dari 1 ke 10, yaitu 1 3 5 8 10 1 4 5 8 10 1 4 6 9 10 Panjang ketiga lintasan tersebut sama, yaitu 11.
Penganggaran Modal (Capital Budgeting) • Sebuah perusahaan berencana akan mengembangkan usaha (proyek) melalui ketiga buah pabrik (plant) yang dimilikinya. Setiap pabrik diminta mengirimkan proposal (boleh lebih dari satu) ke perusahaan untuk proyek yang akan dikembangkan. Setiap proposal memuat total biaya yang dibutuhkan (c) dan total keuntungan (revenue) yang akan diperoleh (R) dari pengembangan usaha itu. Perusahaan menganggarkan Rp 5 milyar untuk alokasi dana bagi ketiga pabriknya itu.
• Tabel berikut meringkaskan nilai c dan R untuk masing-masing proposal proyek. Proposal proyek bernilai-nol sengaja dicantumkan yang berarti tidak ada alokasi dana yang diberikan ntuk setiap pabrik. Tujuan Perusahaan adalah memperoleh keuntungan yang maksimum dari pengalokasian dana sebesar Rp 5 milyar tersebut. Selesaikan persoalan ini dengan program dinamis.
Peubah status yang terdapat pada tahap 1, 2, dan 3: x1 = modal yang dialokasikan pada tahap 1 x2 = modal yang dialokasikan pada tahap 1 dan 2 x3 = modal yang dialokasikan pada tahap 1, 2, dan 3 x3 x2 x1 Tahap 1
Tahap 2
Tahap 3
Kemungkinan nilai-nilai untuk x1 dan x2 adalah 0, 1, 2, 3, 4, 5 (milyar), sedangkan nilai untuk x3 adalah 5
Proyek 1 2 3 4
Pabrik 1 c1 R1 0 0 1 5 2 6 -
Pabrik 2 c2 R2 0 0 2 8 3 9 4 12
Pabrik 3 c3 R3 0 0 1 3 -
Penyelesaian dengan Program Dinamis Maju.
Misalkan, Rk(pk) = keuntungan dari alternatif pk pada tahap k fk(xk) = keuntungan optimal dari tahap 1, 2, …, dan k yang diberikan oleh status xk
Relasi rekurens keuntungan optimal:
f ( x ) max {R1(p1)}
(basis)
f ( x ) max
(rekurens)
1
k
1
k
feasible proposal_ p1
feasible proposal_ pk
{Rk(pk) + fk-1(xk-1) }
k = 2, 3 Catatan: 1. xk – 1 = xk – ck(pk) c(pk) adalah biaya untuk alternatif pk pada tahap k. 2. Proposal pk dikatakan layak (feasible) jika biayanya, c(pk), tidak melebihi nilai status xk pada tahap k.
Relasi rekurens keuntungan optimal menjadi
f ( x ) max {R1(p1)} 1
1
c1 ( p1 ) x1
(basis)
f ( x ) max {Rk(pk) + fk-1[xk – ck(pk)] } (rekurens) k
k
ck ( p k ) x k
k = 2, 3
Tahap 1
f ( x ) max {R1(p1)} 1
x1 0 1 2 3 4 5
1
p1 = 1 0 0 0 0 0 0
c1 ( p1 ) x1 p1 1 , 2 , 3
R1(p1) p1 = 2 5 5 5 5 5
p1 = 3 6 6 6 6
Solusi Optimal f1(x1) p1* 0 1 5 2 6 3 6 3 6 3 6 3
Tahap 2
f ( x ) max {R2(p2) + f1[(x2 – c2(p2)]}, 2
2
c2 ( p2 ) x 2 p2 1 , 2 , 3 , 4
R2(p2) + f1[(x2 – c2(p2)] x2 p2 = 1 0 1 2 3 4 5
p2 = 2
p2 = 3
p2 = 4
0+0=0 0+5=5 0+6=6 8+0=8 0 + 6 = 6 8 + 5 = 13 9 + 0 = 9 0 + 6 = 6 8 + 6 = 14 9 + 5 = 14 12 + 0 = 12 0 + 6 = 6 8 + 6 = 14 9 + 6 = 15 12 + 5 = 17
Solusi Optimal f2(x2) p2* 0 5 8 13 14 17
1 1 2 2 2 atau 3 4
Tahap 3
f ( x ) max {R3(p3) + f2[(x3 – c3(p3)]}, 3
x3 5
3
c3 ( p 3 ) x 3 p3 1 , 2
R3(p3) + f2[(x3 – c3(p3)] p3 = 1 p3 = 2 0 + 17 = 17 3 + 14 = 17
Solusi Optimal f3(x3) p3* 17 1 atau 2
Rekonstruksi solusi: x3
p3* 1
x2 (5 – 0 = 5)
p2* 4
(5 – 4 = 1)
2
(p1*, p2*, p3*) (2, 4, 1)
2
(4 – 2 = 2)
3
(3, 2, 2)
3
(4 – 3 = 1)
3
(2, 3, 2)
x1
p1*
1
2
(5 – 1 = 4)
Integer (1/0) Knapsack Pada persoalan ini, 1. Tahap (k) adalah proses memasukkan barang ke dalam karung (knapsack) (ada 3 tahap). 2. Status (y) menyatakan kapasitas muat karung yang tersisa setelah memasukkan barang pada tahap sebelumnya. Dari tahap ke-1, kita masukkan objek ke-1 ke dalam karung untuk setiap satuan kapasitas karung sampai batas kapasitas maksimumnya. Karena kapasitas karung adalah bilangan bulat, maka pendekatan ini praktis.
• Misalkan ketika memasukkan objek pada tahap k, kapasitas muat karung sekarang adalah y – wk. • Untuk mengisi kapasitas sisanya, kita menerapkan prinsip optimalitas dengan mengacu pada nilai optimum dari tahap sebelumnya untuk kapasitas sisa y – wk ( yaitu fk-1(y – wk)).
Penyelesaian dengan Program Dinamis •
Tahap (k) adalah proses mengalokasikan dana untuk setiap pabrik (ada 3 tahap, tiap pabrik mendefinisikan sebuah tahap).
•
Status (xk) menyatakan jumlah modal yang dialokasikan pada pada setiap tahap (namun terikat bersama semua tahap lainnya).
•
Alternatif (p) menyatakan proposal proyek yang diusulkan setiap pabrik. Pabrik 1, 2, dan 3 masingmasing memiliki 3, 4 dan 2 alternatif proposal.
• Selanjutnya, kita bandingkan nilai keuntungan dari objek pada tahap k (yaitu pk) plus nilai fk-1(y – wk) dengan keuntungan pengisian hanya k – 1 macam objek, fk-1(y). • Jika pk + fk-1(y – wk) lebih kecil dari fk-1(y), maka objek yang ke-k tidak dimasukkan ke dalam karung, tetapi jika lebih besar, maka objek yang ke-k dimasukkan.
Relasi rekurens untuk persoalan ini adalah f0(y) = 0, y = 0, 1, 2, …, M fk(y) = -, y < 0
(basis) (basis)
fk(y) = max{fk-1(y), pk + fk-1(y – wk)}, (rekurens) k = 1, 2, …, n
• fk(y) adalah keuntungan optimum dari persoalan 0/1 Knapsack pada tahap k untuk kapasitas karung sebesar y. • f0(y) = 0 adalah nilai dari persoalan knapsack kosong (tidak ada persoalan knapscak) dengan kapasitas y, • fk(y) = - adalah nilai dari persoalan knapsack untuk kapasitas negatif. Solusi optimum dari persoalan 0/1 Knapsack adalah fn(M).
Contoh: n = 3 M=5 Barang ke-i 1 2 3
wi 2 3 1
pi 65 80 30
Tahap 1: f1(y) = max{f0(y), p1 + f0(y – w1)} = max{f0(y), 65 + f0(y – 2)}
y 0 1 2 3 4 5
f0(y) 0 0 0 0 0 0
65 + f0(y – 2) - - 65 65 65 65
Solusi Optimum f1(y) (x1*, x2*, x3*) 0 (0, 0, 0) 0 (0, 0, 0) 65 (1, 0, 0) 65 (1, 0, 0) 65 (1, 0, 0) 65 (1, 0, 0)
Tahap 2: f2(y) = max{f1(y), p2 + f1(y – w2)} = max{f1(y), 80 + f1(y – 3)}
y 0 1 2 3 4 5
f1(y) 0 0 65 65 65 65
80 + f1(y – 3) 80 + (-) = - 80 + (-) = - 80 + (-) = - 80 + 0 = 80 80 + 0 = 80 80 + 65 = 145
Solusi Optimum f2(y) (x1*, x2*, x3*) 0 (0, 0, 0) 0 (0, 0, 0) 65 (1, 0, 0) 80 (0, 1, 0) 80 (0, 1, 0) 145 (1, 1, 0)
Tahap 3: f3(y) = max{f2(y), p3 + f2(y – w3)} = max{f2(y), 30 + f2(y – 1)}
y 0 1 2 3 4 5
f2(y) 0 0 65 80 80 145
30 + f2(y – 1) 30 + (-) = - 30 + (-) = - 30 + 0 = 30 30 + 65 = 95 30 + 80 = 110 30 + 80 = 110
Solusi Optimum f3(y) (x1*, x2*, x3*) 0 (0, 0, 0) 0 (0, 0, 0) 65 (1, 0, 0) 95 (1, 0, 1) 110 (0, 1, 1) 145 (1, 1, 0)
Solusi optimum X = (1, 1, 0) dengan p = f = 145.
