Dwijanto
Jakarta
300
Program Linear Pontianak
400
250
400
200
Berbantuan Komputer: Surabaya Lindo, Lingo dan Solver Balikpapan 200
600 Makasar
450
400
Manado 450 Jayapura
Dwijanto
Program Linear Berbantuan Komputer: Lindo, Lingo dan Solver
PENDAHULUAN
Buku ini berjudul Program Linear Berbantuan Komputer: Lindo, Lingo dan Solver akan membahas masalah-masalah optimasi yang berbentuk liniear yaitu memaksimumkan atau meminimumkan masalah dalam dalam bentuk fungsi linear dengan persyaratan atau fungsi pembatas sebuah sistem pertidaksamaan linear. Bentuk umum masalah program linear adalah sebagai berikut: Maksimumkan atau minimumkam : F ( xi ) = a1 x1 + a 2 x 2 + ... + a n x n Dengan syarat : g1 ( xi ) = a11 x1 + a12 x 2 + ...a1n x n € b1 g 2 ( xi ) = a 21 x1 + a 22 x 2 + ...a 2 n x n € b2 …. g m ( xi ) = a m1 x1 + a m 2 x 2 + ...a mn x n € bm dengan € diganti ≤ atau = atau ≥ . Kajian pada buku ini terdiri dari 6 Bab, yaitu: Tinjauan Teori-teori sebagai Dasar Program Linear, Pengenalan Program Linear, Transportasi, Penugasan dan Transshipment, Analisis Jaringan, dan Program Linear Bilangan Bulat, yang memuat berbagai masalah yang akan diselesaikan dengan cara manual, dan dengan bantuan program komputer. Program komputer yang digunakan untuk menyelesaikan masalah program liniear di sini adalah program lindo, program lingo, dan Solver yang berada di bawah program excel. Tidak semua masalah pada program linear dapat diselesaikan dengan sebuah program, jadi sangat mungkin sebuah masalah akan dapat cocok diselesaikan dengan suatu program tertentu tetapi tidak tepat apabila digunakan program lain meskipun bisa. Dengan menggunakan komputer sebagai alat bantu dalam menyelesaikan masalah program linear, maka kendala banyaknya variabel sudah bukan menjadi masalah lagi. Ini memberikan kesempatan kepada pembaca (mahasiswa) untuk melakukan kajian sebuah masalah secara lebih mendalam.
Kajian masing masing Bab Bab I.
Teori-teori sebagai Dasar Program Linear Tinjauan Teori-teori sebagai Dasar Program Linear Pada bagian ini akan membahas beberapa teori yang berhubungan dengan program linear khususnya teori yang menyangkut geometri bidang banyak. Teori ini diperlukan khususnya kepada pembaca yang menggemari matematika atau mahasiswa matematika, sedangkan untuk mahasiswa bukan matematika, bab ini dapat dilompati.
Bab II.
Pengenalan Program Linear Pengenalan Program Linear Bagian ini akan membahas Program Linear secara umum, yaitu masalah program linear yang dapat diselesaikan secara manual atau dengan bantuan program komputer. Penyelesaian secara manual dapat digunakan cara grafik ataupun dengan metode simpleks, sedangkan dengan bantuan program komputer sebuah masalah akan diselesaikan dengan tiga program yaitu program lindo, program lingo, dan solver.
Bab III. Transportasi Masalah transportasi disini adalah masalah pemindahan sejumlah barang sejenis dari beberapa tempat (sumber) dengan jumlah barang yang bervariasi kemudian dikirim ke beberapa tempat (tujuan) dengan jumlah kebutuhan yang bervariasi pula. Masalah utama dari transportasi di sini adalah meminimumkan total biaya transportasi. Bab IV.
Penugasan dan Transshipment Penugasan adalah kajian khusus dari masalah transportasi dimana banyaknya sumber sama dengan banyaknya tujuan dengan banyaknya produksi di masing-masing sumber maupun banyaknya permintaan di masing-masin tujuan adalah satu. Sedangkan Transshipment adalah masalah transportasi dimana permintaan tidak dapat dilayani langsung dari produsen. Dalam hal ini pelayanan harus melalui beberapa agen.
Bab V.
Analisis Jaringan Pada Bab Analisis Jaringan ini akan membahas 4 masalah yaitu Masalah Lintasan Terpendek , Masalah Diagram Pohon Terpendek,
Masalah Aliran Maksimum, Menyelesaikan proyek dengan PERT dan CPM. Bab VI. Program Linear Bilangan Bulat Pada bagian ini akan membahas masalah program linear yang khusus dengan solusi bilangan bulat atau bilangan biner. Masalah penyelesaian dengan bilangan bulat ini sering muncul ketika seseorang harus meproduksi barang dengan satuan bilangan bulat, seperti membuat kursi, meja, atau menghitung banyaknya mesin yang akan digunakan. Sedangkan bilangan biner digunakan untuk menentukan sebuah keputusan yaitu apakah suatu pekerjaan atau proyek harus dikerjakan atau tidak.
DAFTAR ISI
Kata Pengantar Pendahuluan Bab I. Tinjauan Teori-teori sebagai Dasar Program Linear 1. 2. 3. 4. 5. 6. 7. 8.
Himpunan Konveks ................................................................................... 1 Titik Ekstrim ............................................................................................. 2 Sinar dan Arah Himpunan Konveks ......................................................... 2 Arah Ekstrim Himpunan Konveks ............................................................. 4 Bidang Banyak dan Ruang Paruh ............................................................. 5 Fungsi Konveks dan Fungsi Konkav ......................................................... 6 Representasi Himpunan Polihedral (Polihedron) ...................................... 8 Teorema Representasi Bentuk Umum ..................................................... 9
Bab II. Pengenalan Program Linear ..................................................................... 13 1. Penyelesaian dengan Metode Grafik ...................................................... 13 2. Penyelesaian dengan Metode Simpleks .................................................. 19 a. Kasus masalah dengan fungsi tujuan maksimum ....................... 19 b. Kasus masalah dengan fungsi tujuan minimum .......................... 27 3. Primal dan Dual ...................................................................................... 31 a. Masalah Primal dan Dual ......................................... 31 b. Hubungan Primal dan Dual ......................................................... 34 4. Program Komputer Lindo, Lingo, dan Solver ........................................ 36 a. Lindo ........................................................................................... 36 b. Menyelesaikan Masalah Program Linear dengan Lindo ............. 43 c. Lingo untuk Menyelesaikan Program Linear ............................. 48 d. Solver untuk Menyelesaikan Program Linear ............................. 50
Bab III. Transportasi ........................................................................................... 60 1. Metode Transportasi ...................................................................................... 60 2. Permasalahan dalam Metode Transportasi .................................................... 60 a. Beberapa Metode dalam Penyelesaian Masalah Transportasi (Penyelesaian awal) ................................................................................. 62 i. North West Corner (NWC) ......................................................... 62 ii. Metode Inspeksi ......................................................................... 63 iii. Metode VAM ( Vogel Approximation Method) ......................... 67 b. Menentukan Nilai Optimal ...................................................................... 74 i. Metode Steppingstone ................................................................ 74 ii. Modified Distribution Method (MODI) ...................................... 79
c. Penyelesaian Masalah dengan Program Komputer ................................. 83 i. Program Lindo untuk Menyelesaikan Masalah Transportasi ..... 83 ii. Program Lingo untuk Menyelesaikan Masalah Transportasi ..... 88 iii. Program Solver untuk Menyelesaikan Masalah Transportasi ..... 92 d. Masalah Transportasi Pasar Tidak Seimbang ........................................ 95
Bab IV. Penugasan dan Transshipment ........................................................... 108 1. Penugasan ............................................................................................. 108 i. Menyelesaikan Masalah Penugasan dengan Metode Hongaria 108 ii. Menyelesaikan Masalah Penugasan dengan Program Komputer111 iii. Program Lindo untuk Menyelesaikan Masalah Penugasan . . 111 iv. Program Solver untuk Menyelesaikan Masalah Penugasan . . 113 2. Transshipment ....................................................................................... 117 i. Program Lingo untuk Menyelesaikan Masalah Transshipment 119 ii. Program Solver untuk Menyelesaikan Masalah Transshipment 122 Bab V. Analisis Jaringan ................................................................................... 125 1. 2. 3. 4.
Masalah Lintasan Terpendek ................................................................ 127 Masalah Diagram Pohon Terpendek ................................................... 133 Masalah Aliran Maksimum .................................................................. 135 Menyelesaikan proyek dengan PERT dan CPM .................................... 140
Bab VI. Program Linear Bilangan Bulat ........................................................... 149 1. Metode Branch and Bound ................................................................... 151 2. Penyelesaian Program Linear Bilangan Bulat dengan Program Lindo.. 154 3. Penyelesaian Program Linear Bilangan Bulat dengan Program Solver . 155 Daftar Pustaka .................................................................................................... 166 Indeks ................................................................................................................. 167
KATA PENGANTAR
Puji Syukur Kehadirat Ilahi yang telah memberi karuniaNya sehingga buku Program Linear Berbantuan Komputer: Lindo, Lingo dan Solver dapat terselesaikan. Buku ini ditujukan kepada mahasiswa matematika, ekonomi dan teknik terutama mahasiswa yang mempelajari program linear dan memanfaatkan komputer sebagai alat bantu dalam menyelesaikan masalah program linear. Buku ini ditulis bertujuan untuk melengkapi buku-buku program linear yang perhitungannya mengunakan perhitungan manual. Akibatnya dalam pengambilan masalah sering membatasi dengan sedikit variabel. Dalam buku ini, penyelesaian suatu masalah akan dikerjakan dengan cara perhitungan manual, kemudian diselesaikan dengan bantuan komputer khususnya program Lindo, Lingo atau Solver. Dengan menggunakan komputer sebagai alat bantu hitung, maka masalah perhitungan dan banyaknya variabel bukan menjadi kendala lagi. Untuk mahasiswa ekonomi maupun teknik, dapat langsung memulai dari Bab II dan seterusnya, sedangkan mahasiswa matematika perlu memahami terlebih dulu teori yang berada pada Bab I. Ucapan terima kasih kami sampaikan kepada Penjaminan Mutu Universitas Negeri Semarang yang telah memberikan kesempatan kepada Penulis untuk penulisan buku ini. Selanjutnya saran dan kritik dari pembaca sangat diharapkan guna penyempurnaan buku ini.
Semarang, Agustus 2007 Penulis
BAB I Sekilas tentang Teori-teori sebagai Dasar Program Linear 1. Himpunan konveks Sebuah himpunan X dalam Rn disebut himpunan konveks apabila memenuhi sifat berikut: jika diberikan sebarang dua titik x1 dan x2 di dalam X, maka λx1 + (1- λ)x2 ∈ X untuk setiap λ ∈ [0 , 1]. Selanjutnya kita ketahui bahwa λx1 + (1 - λ)x2 untuk λ dalam interval [0 , 1], menggambarkan titik-titik yang terletak pada ruas garis yang menghubungkan x1 dan x2. Sebarang titik dalam bentuk λx1 + (1- λ)x2 dengan 0 ≤ λ ≤ 1 disebut kombinasi konveks dari x1 dan x2. Jika λ ∈ (0 , 1), maka bentuk λx1 + (1- λ)x2 disebut kombinasi konveks sempurna. Dalam pengertian geometri, himpunan konveks dan himpunan tidak-konkveks dapat digambarkan sebagai berikut:
a. Himpunan konveks
b. Himpunan tidak-konveks
Gambar 1.1. Contoh himpunan konveks dan himpunan tidak konveks. Pada gambar sebelah kiri (Gambar 1.1.a), untuk semua kombinasi konveks dari x1 dan x2 berada dalam X, sedangkan pada gambar sebelah kanan (Gambar 1.1.b), terdapat kombinasii konveks dari x1 dan x2 yang berada diluar X. Jadi gambar sebelah kiri adalah menggambarkan himpunan konveks, sedangkan himpunan gambar sebelah kanan adalah menggambarkan himpunan tidak-konveks. Berikut adalah contoh-contoh himpunan konveks:
{
}
1. ( x1 , x 2 ) : x12 + x 2 2 ≤ 1
1 1 0 2. x : x = λ1 0 + λ 2 1 + λ 3 1, λ1 + λ 2 + λ 3 = 1, λ1 , λ 2 , λ 3 ≥ 0 0 0 1
1
2
2. Titik Ekstrim Dalam kajian pada program linear, titik ekstrim sangat berperan dalam menentukan nilai optimum suatu masalah. Sebuah titik dalam himpunan konveks X disebut titik ekstrem dari himpunan X, jika titik x tersebut tidak dapat dinyatakan dengan kombinasi konveks sempurna dari dua titik yang berbeda dalam X. Dengan kata lain jika x titik ekstrim dan x = λx1 + (1- λ)x2, dengan λ ∈ (0 , 1) dan x1, x2 ∈ X, maka x = x1 = x2. Gambar berikut memperlihatkan titik ekstrim dan bukan titik ekstrim.
Gambar 1. 2. Titik-titik pada himpunan konveks X. Titik x1 adalah titik ekstrimdari X, sedangkan x2 dan x3 bukan titik ekstrim dari X. 3. Sinar dan Arah Himpunan Konveks Sinar pada Himpunan Konveks Misalkan X himpunan konveks. Sinar adalah himpunan titik-titik yang berbentuk {x0 + λd : λ ≥ 0} dimana d vektor tak-nol. Dalam hal ini, x0 disebut titik ujung dari sinar, dan d adalah arah sinar.
Arah Himpunan Konveks Misalkan X himpunan konveks, vektor tak-nol d disebut arah suatu himpunan X, jika untuk setiap x0 di X, {x0 + λd : λ ≥ 0} juga di X. Oleh karena itu seseorang dapat mengambil sebarang titik x0 di X, dan menariknya dengan memperpanjang atau memperpendek (recede) d dengan λ ≥ 0 , maka akan tetap berada di X. Jelas apabila X terbatas, maka X tidak mempunyai arah.
3
Contoh 1.1 Tentukan arah himpunan polihedral X = {x : Ax ≤ b, x ≥ 0}. Jawaban Misalkan d arah himpunan X, maka untuk setiap λ ≥ 0 dan x ∈ X, d ≠ 0 dan memenuhi A(x + λd) ≤ b
.... (1)
x + λd ≥ 0
.... (2)
Karena x ∈ X, maka memenuhi Ax ≤ b. Dari (1) dengan mengambil λ ≥ 0 cukup besar (lim λ →∞) diperoleh Ad ≤ 0. Dengan cara serupa dari (2) akan diperoleh d ≥ 0. Jadi d arah himpunan X jika dan hanya jika d ≥ 0, d ≠ 0, dan Ad ≤ 0. Dengan cara serupa untuk X = {x : Ax = b, x ≥ 0} dan d arah himpunan X, maka d ≥ 0, d ≠ 0 dan Ad ≤ 0.
Contoh 1. 2. Tentukan arah himpunan X = {(x1,x2) : x1 + x2 ≥ 1, x1 - x2 ≥ -2, x1 ≥ 0, dan x2 ≥ 0 }. Jawaban
d1
d
d2 ≤d1
d1
Gambar 1. 3. Himpunan X = {(x1,x2) : x1 + x2 ≥ 1, x1 - x2 ≥ -2, x1 ≥ 0, dan x2 ≥ 0 } Misalkan x0 = (x1,x2) sebarang titik di X dan d = (d1,d2) arah himpunan X.
4
Karena d = (d1,d2) arah himpunan X, maka d ≠ 0 dan untuk setiap λ ≥ 0, berlaku x0 + λd = (x1 + λd1 , x2 + λd2) ∈ X akibatnya: x1 + λd1 + x2 + λd2 ≥ 1
... (1)
x1 + λd1 - x2 - λd2 ≥ -2
... (2)
x1 + λd1 ≥ 0
... (3)
x2 + λd2 ≥ 0
... (4)
Dari (1) dapat dubah menjadi x1 + x2 + λ(d1 + d2) ≥ 1 Karena x1 dan x2 tetap dan dengan λ sebarang, maka untuk λ yang cukup besar berlaku d1 + d2 ≥ 0 atau d2 ≥ -d1. Persamaan (2) juga dapat diubah menjadi x1 - x2 + λ(d1 - d2) ≥ -2. Dari persamaan terakhir ini dengan mengambil x1 dan x2 tetap dan dengan λ sebarang, maka untuk λ yang cukup besar berlaku d1 – d2 ≥ 0 atau d2 ≤ d1. Dengan cara serupa dari (3) dan (4) kita peroleh d1 ≥ 0 dan d2 ≥ 0. Sehingga secara keseluruhan diperolah d2 ≥ - d1, d2 ≤ d1, d1 ≥ 0 dan d2 ≥ 0. Dari keempat hasil ini dapat disederhanakan menjadi d1 ≥ 0 dan 0 ≤ d2 ≤ d1.
4. Arah Ekstrim Himpunan Konveks Pendefinisian arah ekstrim himpunan mirip dengan titik ekstrim. Suatu arah ekstrim himpunan konveks adalah arah suatu himpunan konveks yang tidak dapat di representasikan dengan kombinasi positif dari dua arah himpunan yang berbeda. Dua vektor d1, d2 dikatakan berbeda atau tidak ekivalen jika d1 tidak dapat direpresentasikan dengan perkalian positif dengan kelipatan d2. Pada Contoh 2 di atas, maka d1 = (1,0) dan d2 = (√2/2 , √2/2) adalah arah ekstrim yang telah di normalkan. Untuk setiap arah himpunan konveks dapat dinyatakan sebagai kombinasi dari d1 dan d2 yaitu dalam bentuk λ1d1 + λ2d2, dengan λ1, λ2 > 0. Dengan demikian setiap arah himpunan yang berbentuk d = (d1 , d2) dengan d1 ≥ 0 dan 0 ≤ d2 ≤ d1 dapat ditulis dalam bentuk λ1d1 + λ2d2. Misalnya arah d = (5, 2) adalah memenuhi syarat untuk arah dari X, maka apabila kita tuliskan dalam bentuk kombinasi linear λ1d1 + λ2d2, λ1 = 3 dan λ2 = 2√2.
diperoleh
5
5. Hyperplane dan Halfspace Bidang banyak (Hyperplane) di Rn adalah bentuk generalisasi dari garis di R2 atau sebuah bidang di R3. Bidang banyak H di Rn adalah himpunan yang berbentuk {x:px = k} dimana p vektor tak nol di Rn dan k suatu skalar. Disini p disebut normal dari bidang banyak. Bidang banyak terdiri dari semua titik x = (x1, x2, ..., xn) yang memenuhi persamaan n
∑ p j x j = k . Konstan k dapat dieliminasikan dengan menggunakan suatu titik tertentu j =1
misalnya x0 di H. Jika x0 ∈ H, maka akan memenuhi px0 = k, dan setiap x ∈ H, kita miliki px = k. Jadi dengan proses mengurangkannya kita peroleh p(x - x0) = 0, dimana x0 sebarang titik tetap di H. Bidang banyak adalah konveks. Gambar berikut adalah bidang banyak dan vektor normal p, dimana p ortogonal terhadap x - x0.
Gambar 1.4. Bidang banyak Bidang banyak membagi Rn dalam dua daerah, yang disebut ruang paruh (halfspaces). Dengan demikian ruang paruh adalah himpunan titik-titik yang berbentuk {x: px ≥ k}, dimana p vektor tak-nol di Rn dam k skalar. Sedangkan ruang paruh yang satunya akan berbentuk
6
{x: px ≤ k}. Irisan kedua ruang paruh adalah bidang banyak dan gabungan kedua ruang paruh tersebut adalah Rn.
Gambar 1.5. Ruang Paruh. Berkaitan dengan x0 titik tetap di bidang banyak, maka kedua ruang paruh dapat dinyatakan dengan {x : p(x – x0) ≥ 0} atau {x : p(x – x0) ≤ 0}. Gambar di atas memperlihatkan ruang paruh yang pertama yang terdiri dari titik-titik x sedemikian hingga (x – x0) membentuk sudut lancip (≤ 90°) terhadap p, dan ruang paruh yang kedua terdiri dari titik-titik x sedemikian hingga (x – x0) membentuk sudut tumpul (≥ 90°) terhadap p.
6. Fungsi konveks dan fungsi konkav Fungsi f : Rn → R disebut konveks jika untuk dua vektor x1 dan x2 di Rn berlaku: f (λx1 + (1- λ)x2) ≤ λ f (x1) + (1- λ) f (x2), untuk semua λ ∈ [0 , 1]. Selanjutnya fungsi f : Rn → R disebut konkav jika -f adalah fungsi konveks. Jadi fungsi f adalah konkav jika memenuhi pertidaksamaan berikut: f (λx1 + (1- λ)x2) ≥ λ f (x1) + (1- λ) f (x2), untuk semua λ ∈ [0 , 1]. Fungsi konveks dan fungsi konkav dapat diilustrasikan seperti gambar berikut:
7
(a)
(b)
(c)
Gambar 1.6. Contoh fungsi konveks dan fungsi konkav Gambar (a) adalah fungsi konveks, λ f (x1) + (1- λ) f (x2) digambarkan sebagai titik pada tali busur yang menghubungkan f (x1) dan f (x2), sedangkan f (λx1 + (1- λ)x2) adalah titik pada f yang menghubungkan f (x1) dan f (x2). Dapat dilihat dari gambar bahwa λ f (x1) + (1- λ) f (x2) berada diatas f (λx1 + (1- λ)x2). Jadi f (λx1 + (1- λ)x2) ≤ λ f (x1) + (1- λ) f (x2), yang berarti f konveks. Dengan analogi yang sama, maka dapat dilihat bahwa gambar (b) adalah fungsi konkav dan gambar (c) menggambarkan fungsi yang bukan konveks maupun konkav.
8
7. Representasi Himpunan Polihedral (Polihedron) Polihedral adalah sebuah bangun yang dibentuk oleh beberapa halfspace atau sebuah bangun yang dibentuk oleh oleh sistem pertidaksamaan linear. Misalnya, X adalah Polihedral yang dibatasi oleh: -3x1 + x2 ≤ -2 - x1 + x2 ≤ 2 -x1 + 2x2 ≤ 8 -x2 ≤ -2 x1 ≥ 0, x2 ≥ 0. Polihedral dapat merupakan hipunan terbatas, dan dapat pula tak terbatas. a. Himpunan Polihedral terbatas Himpunan Polihedral terbatas adalah himpunan polihedral yang memenuhi kriteria bahwa terdapat bilangan k sehingga untuk setiap x pada himpunan berlaku x < k. Gambar 5 adalah polihedral terbatas dengan enam halfspace dan memiliki enam titik ekstrim, yaitu x1, x2, x3, x4, x5, x6. x adalah titik di dalam polihedral, maka x dapat dinyatakan dengan kombinasi konveks y dan x1 : x = λ y + (1 – λ) x1, dengan λ ∈ (0 , 1). Selanjutnya y itu sendiri merupakan kombinasi konveks dari x3 dan x4: y = ηx3 + (1 – η) x4, dengan η∈ (0 , 1).
Gambar 1.7. Representasi sebuah titik dalam polihedral terbatas terhadap titik-titik ekstrem
9
Dengan mensubstitusikan x3 dan x4 kedalam y maka kita peroleh: x = ληx3 + λ (1 – η) x4 + (1 – λ) x1 Karena λ ∈ (0 , 1) dan η∈ (0 , 1), maka λη, λ (1 – η) , (1 – λ) ∈ (0 , 1). Juga memenuhi λη+ λ (1 – η) + (1 – λ). Dengan kata lain, x dapat direpresentasikan sebagai kombinasi konveks terhadap titik-titik ekstrim x1, x3, x4. Hal ini dapat diambil genaralisasi bahwa setiap titik dalam himpunan polihedral terbatas, dapat dinyatakan sebagai kombinasi konveks dari titik-titik ekstrimnya.
b. Himpunan Polihedral tak-terbatas Dalam polihedral tak-terbatas, maka sebuah titik dapat di representasikan dalam kombinasi titik ekstrim dan arah ekstrim himpunan. Gambaran berikut adalah sebuah titik representasi sebuah titik pada polihedral tak terbatas.
Gambar 1.8. Repesentasi titik pada Polihedral tak-terbatas Misalkan x ∈ X sebarang, maka x = s + d, s dapat dinyatakan dengan kombinasi konveks dari x2 dan x4 yaitu s = λ1x1 + λ2x2 sedangkan d dapat dinyatakan dengan kombinasi dari d1 dan d2, yaitu d = η1d1 + η2d2. Jadi x = λ1x1 + λ2x2 + η1d1 + η2d2.
10
8. Teorema Representasi Bentuk Umum Misalkan X = {x : Ax ≤ b, x ≥ 0} himpunan tak-kosong (polihedron). Maka himpinan titik-titik ekstrim tak-kosong dan banyaknya titik-titik tersebut berhingga, sebut x1, x2, x3, . . . , xk. Selanjutnya himpunan arah adalah kosong jika dan hanya jika X terbatas. Jika X tak-terbatas, maka himpunan arah tak-kosong dan memiliki sejumlah berhingga vektor, sebut d1, d2, . . ., dm. Kemudian, x ∈ X jika dan hanya jika x dapat dinyatakan sebagai kombinasi konveks dari x1, x2, x3, . . . , xk ditambah dengan kombinasi linear tak negatif dari d1, d2, . . ., dm yaitu, x=
k
∑ λ j x j + ∑ η jd j
m
k
∑ λ j = 1,
j =1
j =1
j =1
λ j ≥ 0, j = 1,2,..., k η j ≥ 0, j = 1,2,..., m
Bukti. Tidak dibuktikan dalam buku ini.
Akibat. Untuk sebarang x*∈X dapat direpresentasikan sebagai x* =
k
∑ λ j x j + ∑ η jd j ,
m
k
∑ λ j = 1,
j =1
j =1
j =1
λ j ≥ 0, j = 1,2,..., k , η j ≥ 0, j = 1,2,..., m .
Soal-soal 1. Tunjukkan bahwa hyperplane H = {x : px = k} dan halfspace H*= {x : px ≥ k} adalah himpunan konveks. 2. Buatlah grafik yang menggambarkan himpunan yang memenuhi {(x1,x2) : -x1 + x2 ≤ 2, x1 + 2x2 ≤ 8, x1 ≥ 0, x2 ≥ 0}. Apakah himpunan ini konveks ? 3. Buatlah grafik yang menggambarkan himpunan yang memenuhi {(x1,x2) : x1 + x2 ≥ 2, x1 ≤ 8, x1 ≥ 0, x2 ≥ 0}. Apakah himpunan ini konveks ?
11
4. Misalkan a1 = (1 , 0), a2 = (2 , 3), a3 = (-1 , 4), a4 = (5 , -3), a5 = (-4 , 4). Ilustrasikan secara geometri kombinasi konveks dari ke-lima titik ini. 5. Tentukan fungsi-fungsi berikut konveks, konkaf atau tidak keduanya. a. f(x) = 2x b. f(x) = x2 c. f(x) = x3 d. f(x1,x2) = x1 2 + 3 x2 6. Misalkan himpunan X = {(x1,x2) : x1 + 2x2 ≥ 2, x1 - 2x2 ≥ -6, x1 ≥ 0, dan x2 ≥ 1}. Tentukan arah himpunan X ini. 7. Diketahui himpunan X = {(x1,x2) : x1 + 2x2 ≥ 2, x1 - 2x2 ≥ -6, x1 ≥ 0, dan x2 ≥ 1}. Nyatakan titik-titik berikut sebagai kombinasi konveks dan arah himpunan: a. (1 , 1) b. (1 , 2) c. (2 , 1) d. (3 , 2) e. (6 , 3)
BAB III Transportasi 1. Metode Transportasi Metode transportasi adalah suatu metode yang digunakan untuk mengatur distribusi dari sumber-sumber yang menyediakan produk yang sama atau sejenis ke tempat tujuan secara optimal. Distribusi ini dilakukan sedemikian rupa sehingga permintaan dari beberapa tempat tujuan dapat dipenuhi dari beberapa tempat asal yang masing-masing dapat memiliki permintaan atau kapasitas yang berbeda. Dengan menggunakan metode transportasi, dapat diperoleh suatu alokasi distribusi barang yang dapat meminimalkan total biaya transportasi. Selain untuk mengatur distribusi pengiriman barang, metode transportasi juga dapat digunakan untuk masalah lain, seperti penjadwalan dalam proses produksi agar memperoleh total waktu proses pengerjaan yang terendah, penempatan persediaan agar mendapatkan total biaya persediaan terkecil, atau pembelanjaan modal agar mendapatkan hasil investasi yang terbesar. Dalam kaitannya dengan perencanaan fasilitas, metode transportasi dapat digunakan untuk memilih suatu lokasi yang dapat meminimalkan total biaya operasi. Suatu perusahaan memerlukan pengelolaan data dan analisis kuantitatif yang akurat, cepat serta praktis dalam penggunaannya. Dalam perhitungan secara manual membutuhkan waktu yang lebih lama, sementara pertimbangan efisiensi waktu dalam perusahaan sangat diperhatikan. Dengan demikian diperlukan adanya suatu alat, teknik maupun metode yang praktis, efektif dan efisien untuk memecahkan permasalahan tersebut.
2. Permasalahan dalam Metode Transportasi Masalah ini merupakan masalah pengangkutan sejenis barang dari beberapa sumber ke beberapa tujuan. Pengalokasian produk dari sumber yang bertindak sebagai penyalur ke tujuan yang membutuhkan barang bertujuan agar biaya pengangkutannya seminimal mungkin dari seluruh permintaan dari tempat tujuan dipenuhi. Model transportasi
60
61
digunakan untuk menyelesaikan masalah distribusi barang dari beberapa sumber ke beberapa tujuan. Asumsi sumber dalam hal ini adalah tempat asal barang yang hendak dikirim, sehingga dapat berupa pabrik, gudang, grosir, dan sebagainya. Sedangkan tujuan diasumsikan sebagai tujuan pengiriman barang. Dengan demikian informasi yang harus ada dalam masalah transportasi meliputi: banyaknya daerah asal beserta kapasitas barang yang tersedia untuk masing tempat, banyaknya tempat tujuan beserta permintaan (demand) barang untuk masing-masing tempat dan jarak atau biaya angkut untuk setiap unit barang dari suatu tempat asal ke tempat tujuan. Untuk lebih jelasnya marilah kita bahas contoh masalah transportasi yang terlihat pada Tabel 1.1. berikut: Tabel 1.1 Kapasitas pabrik, Permintaan di Lapangan (Demand), dan biaya satuan pengangkutan Origin (Tempat
Kapasitas
Destination (Tempat Tujuan) D1
D2
D3
D4
Pabrik
D5
Asal) 12
4
9
5
9 100
O1 8
1
6
6
7 90
O2 1
12
4
7
7 70
O3 10
15
6
9
1 90
O4 Demand (Permin-
80
50
90
60
70
350
taan) Tabel 1.1. di atas menggambarkan bahwa jumlah kapasitas pabrik O1, O2, O3, dan O4 berturut-turut: 100, 90, 70, dan 90, sedangkan permintaan pasar di lapangan D1, D2, D3, D4, dan D5 berturut-turut 80, 50, 100, 60, dan 70. Biaya satuan dari pabrik O1 ke
62
permintaan D1 adalah 12, biaya satuan dari pabrik O1 ke permintaan D2 adalah 4, dan seterusnya, sampai biaya satuan dari pabrik O3 ke permintaan D5 adalah 1. Untuk menyelesaikan permasalahan transportasi ini ada beberapa metode antara lain: Metode North West Corner (NWC), metode Inspeksi, dan metode pendekatan Vogel (Vogel Approximation Methods atau disingkat VAM).
a. Beberapa Metode dalam Penyelesaian Masalah Transportasi (Penyelesaian awal) i.
North West Corner (NWC) Sesuai nama aturan ini, maka penempatan pertama dilakukan di sel paling kiri dan
paling atas (northwest) matriks kemudian bergerak ke kanan atau ke bawah sesuai permintaan dan kapasitas produksi yang sesuai. Besar alokasi ini akan mencukupi salah satu, kapasitas tempat asal baris pertama dan atau permukaan tempat tujuan dari kolom pertama. Jika kapasitas tempat asal pertama terpenuhi kita bergerak ke bawah menyusur kolom pertama dan menentukan alokasi yang akan mencukupi atau kapasitas tempat asal baris kedua atau mencukupi tujuan yang masih kurang dari kolom pertama. Di lain pihak, jika alokasi pertama memenuhi permintaan tempat tujuan di kolom pertama, kita bergerak ke kanan di baris pertama dan kemudian menentukan alokasi yang kedua atau yang memenuhi kapasitas tersisa dari baris satu atau memenuhi permintaan tujuan dari kolom dua dan seterusnya. Untuk masalah seperti pada Table 1.1 di atas, maka apabila diselesaikan dengan metode NWC akan melakukan langkah-langkah sebagai berikut: Penggunaan metode NWC mengharuskan sel O1 D1, yang terletak di sudut kiri atas diisi. Alokasi diterapkan X11 = 80 unit untuk memenuhi permintaan yang ternyata lebih kecil dari kapasitas O1. Ini berarti permintaan tujuan D1= 80 dapat dipenuhi dari O1. Ternyata produksi O1 masih mempunyai (100 - 80) = 20 unit kapasitas yang belum disalurkan. Sisa yang 20 unit ini di alokasikan kepada permintaan D2 yang permintaannya 50 unit. Untuk memenuhi kekurangan kebutuhan D2, yaitu kurang 30 unit maka diambil dari D2 dengan demikian maka sel O1D2 atau X12 = 20 dan sel O2D2 atau X22 = 30. Sisa produksi D2 setelah dikurangi 30 unit adalat 60 unit, sisa ini di alokasikan ke sel O2D3 atau X23 yang secara keseluruhan. Permintaan D3 adalah 90 unit dan telah tersedia 60 unit dari O2.
63
Kekurangan 30 unit diambilkan dari produksi O3 sehingga X23 = 70 dan X33 = 30. Sisa produksi O3 sebanyak 40 unit yaitu (70-30) di alokasikan ke permintaan D4 dan permintaan D4 sebanyak 60 unit dilengkapi dengan mengambil 20 unit dari produksi O4. Dengan demikian produksi O4 tersisa 70 unit dialokasikan ke permintaan D5. Tabel 2.1. Matriks biaya transportasi tiap barang dan jumlah alokasi distribusi barang dari tempat asal (pabrik) ke tempat tujuan (kota tujuan) Destination (Tempat Tujuan) Tempat Kapasitas D1 D2 D3 D4 D5 Asal Pabrik 12 O1
80
4
9
5
9 100
20 8
O2
1 30
1
6
7 90
60 12
O3
4 30
10
6
15
7
70
40 6
O4
7
9
1
20
70
90
60
70
350
Permintaan
80
50
90
Berdasarkan Tabel 2.1 di atas diperoleh sistem transportasi sebagai berikut: Sel O1D1 atau X11 = 80, sel O1D2 atau X12 = 20, sel O2D2 atau X22 = 30, sel O2D3 atau X23 = 60, sel O3D3 atau X33 = 30, sel O3D4 atau X34 = 40, sel O4D4 atau X44 = 20, dan sel O4D5 atau X45 = 70. Besarnya biaya transportasi dengan metode NWC adalah 80 (12) + 20 (4) + 30 (1) + 60 (6) + 30 (4) + 40 (7) + 20 (9) + 70 (1) = 2.080.
ii. Metode Inspeksi Metode ini untuk persoalan transportasi berdimensi kecil, hal ini akan memberikan pengurangan waktu. Alokasi pertama dibuat terhadap sel yang berkaitan dengan biaya pengangkutan terendah. Sel dengan ongkos terendah ini diisi sebanyak mungkin dengan mengingat persyaratan kapasitas produksi (origin) maupun permintaan tempat tujuan.
64
Kemudian beralih ke sel termurah berikutnya dan mengadakan alokasi dengan memperhatikan kapasitas yang tersisa dari permintaan baris dan kolom. Dalam perhitungannya metode ini membuat matriks sesuai dengan persyaratan. Untuk permasalahan transportasi di atas apabila dilakukan dengan metode Inspeksi maka langkah-langkahnya sebagai berikut: Biaya terkecil adalah 1 yaitu pada sel O2D2, O3D1, dan O4D5. Sel-sel ini kita isi dengan memperhatikan kapasitas dan permintaan, yaitu dengan mencari nilai minimum dari keduanya. Sel O2D2 kita isi 50, sehingga kapasitas O2 menjadi 40 dan permintaan D2 menjadi 0, kemudian kolom D2 kita tandai dan tidak kita olah pada program selanjutnya. Sel O3D1 kita isi 70, sehingga kapasitas O3 menjadi 0 dan permintaan D2 menjadi 10, kemudian baris O3 kita tandai dan tidak kita olah pada program selanjutnya. Sel O4D5 kita isi 70, sehingga kapasitas O4 menjadi 20 dan permintaan D5 menjadi 0, kemudian kolom D5 kita tandai dan tidak kita olah pada program selanjutnya. Hasil perhitungan di atas ini dapat dilihat pada Tabel 2.2. Tabel 2.2. Destination (Tempat Tujuan)
Tempat Asal
D1
D2
D3
12
4
Kapasitas
D4 9
Pabrik
D5 5
9 100
O1 8 O2
1
6
4
7
7
15
6
9
O4
1
10
0 50
20 90
70
80
0 70
70
Permin-
40 90
12
10
taan
7
50 1
O3
6
0 90
60
70
350
65
Biaya terkecil selanjutnya adalah 5 yang terletak pada sel O1D4. Sel O1D4 kita isi minimum dari kapasitas O1dan permintaan D4, sehingga kita isi dengan 60 unit. Dengan pengisian 60 unit pada sel O1D4 maka kapasitas O1 menjadi 40 dan permintaan D4 menjadi 0, kemudian kolom D4 kita tandai dan tidak kita olah pada program selanjutnya. Hasil perhitungan ini dapat kita hihat pada Tabel 2.3. Tabel 2.3.
Asal
D1
D2
D3
12
4
D4 9
O1
O2
1
5
9
6
6
7
12
4
7
7
0 70
10
15
6
9
O4
1
10
0 50
50
30
90
0 60
20 90
70
80
40 90
70
Permin-
40 100
50 1
taan
Pabrik
D5
60 8
O3
Kapasitas
Destination (Tempat Tujuan)
Tempat
0 70
350
Biaya terkecil selanjutnya adalah 6 yang terletak pada sel O2D3. dan sel O4D3. Sel O2D3 kita isi minimum dari sisa kapasitas O2 dan permintaan D3, sehingga kita isi dengan 40 unit. Dengan pengisian 40 unit pada sel O2D3 maka kapasitas O2 menjadi 0 dan permintaan D3 menjadi 50, kemudian baris O2 kita tandai dan tidak kita olah pada program selanjutnya. Sel O4D3 kita isi minimum dari sisa kapasitas O4 dan sisa permintaan D3, sehingga kita isi dengan 20 unit. Dengan pengisian 20 unit pada sel O4D3 maka kapasitas O4 menjadi 0 dan permintaan D3 menjadi 30, kemudian baris 42 kita tandai dan tidak kita olah pada program selanjutnya. Hasil perhitungan ini dapat kita hihat pada Tabel 2.4.
66
Tabel 2.4. Destination (Tempat Tujuan)
Tempat Asal
D1
D2
D3
12
4
D4 9
O1
O2
1 50
5
9
6
6
7
40 90
12
4
7
7
0 70
70 10
15
O4
6
9
20 10
Permin-
40 100
40
1
taan
Pabrik
D5
60 8
O3
Kapasitas
80
0
20 90
70
50
50
1
30
0
90
60
70
350
Selanjutnya kekurangan dari permintaan D1 sebanyak 10 unit, dan kekurangan permintaan D2 sebanyak 30 unit di alokasikan dari sisa produksi D1 yang besarnya 40 unit. Dengan demikian maka semua permintaan maupun pemawaran telah selesai dan diperoleh Tabel 2.5 berikut. Tabel 2.5. Destination (Tempat Tujuan)
Tempat Asal
D1
D2
D3
12 O1
4 30
8 O2
1
9
6
7
4
7
7
0 70
15
6
O4
9
20 10 80
40 90
70
Permin-
40 100
60
40 12
10
taan
Pabrik
D5 5
6
50 1
O3
D4 9
10
Kapasitas
0 50
0 60
20 90
70
50 30 90
1
0 70
350
67
Berdasarkan Tabel 2.5 di atas diperoleh sistem transportasi sebagai berikut: X11 = 10, X13 = 30, X14 = 60, X22 = 50, X23 = 40, X31 = 70, X43 = 20, dan X45 = 70. Besarnya biaya transportasi dengan metode Inspeksi adalah 10 (12) + 30 (9) + 60 (5) + 50 (1) + 40 (6) + 70 (1) + 20 (6) + 70 (1) = 1240. iii. Metode VAM ( Vogel Approximation Method) Metode VAM ini didasarkan atas “beda kolom” dan “beda baris” yang menentukan perbedaan antara dua ongkos termurah dalam satu kolom atau satu baris. Setiap perbedaan dapat dianggap sebagai “penalti”, karena menggunakan route termurah. Beda baris atau beda kolom berkaitan dengan penalti tertinggi, merupakan baris atau kolom yang akan diberi alokasi pertama. Alokasi pertama ini, atau menghabiskan tempat Kapasitas produksi, atau menghabiskan permintaan tujuan atau kedua-duanya. Untuk memperjelas metode ini, marilah kita mengerjakan soal yang sama dengan diatas dengan menggunakan metode VAM. Masalah transportasi ini adalah: Tabel 2.6. Destination (Tempat Tujuan)
Tempat Asal
D1
D2 12
D3 4
D4 9
D5 5
Kapasitas
Beda
Pabrik
Baris
9 100
O1 8
1
6
6
7 90
O2 1
12
4
7
7 70
O3 10
15
6
9
1 90
O4 Permintaan Beda Kolom
80
50
90
60
70
350
68
Besarnya beda baris dan beda kolom adalah sebagai berikut. Tabel 2.7. Beda baris dan beda kolom. Baris atau kolom
Dua biaya termurah
Baris O1 Baris O2 Baris O3 Baris O4 Kolom D1 Kolom D2 Kolom D3 Kolom D4 Kolom D5
4 1 1 1 1 1 4 5 1
dan dan dan dan dan dan dan dan dan
Beda baris atau beda kolom 1 5 3 5 7 3 2 1 6
5 6 4 6 8 4 6 6 7
Beda baris atau beda kolom terbesar adalah 7 yaitu pada kolom D1, biaya termurah kolom D1 adalah 1 yaitu pada sel O3D1. Oleh karena itu sel O3D1 ini diisi terlebih dahulu, yang besarnya adalam minimum kapasitas O3 dan permintaan D1 yaitu 70. Dengan mengisi sel O3D1 sebesar 70, maka kapasitas O3 menjadi 0 dan permintaan D1 menjadi 10. Dengan demikian baris O3 kita tandai dan tidak dimasukkan dalam program selanjutnya. Hasil perhitungan ini dapat kita lihat pada Tabel 2.8. Tabel 2.8. Origin (Tempat Asal)
Kapasitas Pabrik
Destination (Tempat Tujuan) D1
D2 12
D3 4
D4 9
D5 5
9
O1 8
1
6
6
O3
12
4
7
15
6
9
90
5
70
3
90
5
1
O4 Demand (Permintaan) Beda Kolom
1
7
70 10
100 7
O2 1
10 80 7
Beda Baris
50
90
60
70
3
2
1
6
350
69
Besarnya beda baris dan beda kolom berikutnya adalah sebagai berikut. Tabel 2.9. Beda baris dan beda kolom Baris atau kolom
Dua biaya termurah
Baris O1 Baris O2 Baris O4 Kolom D1 Kolom D2 Kolom D3 Kolom D4 Kolom D5
Beda baris atau beda kolom 1 5 5 2 3 0 1 6
4 dan 5 1 dan 6 1 dan 6 8 dan 10 1 dan 4 6 dan 6 5 dan 6 1 dan 7
Beda baris atau beda kolom terbesar adalah 6 yaitu pada kolom D5, biaya termurah kolom D5 adalah 1 yaitu pada sel O4D5. Oleh karena itu sel O4D5 ini diisi terlebih dahulu, yang besarnya adalam minimum kapasitas O4 dan permintaan D5 yaitu 70. Dengan mengisi sel O4D5 sebesar 70, maka kapasitas O4 menjadi 20 dan permintaan D5 menjadi 0. Dengan demikian kolom D5 kita tandai dan tidak dimasukkan dalam program selanjutnya. Hasil perhitungan ini dapat kita lihat pada Tabel 2.10. Tabel 2.10. Destination (Tempat Tujuan)
Tempat Asal
D1
D2 12
D3 4
D4 9
D5 5
1
6
6
Beda Kolom
5
4
7
7
0 70
10
15
6
9
1 70
20 90 350
10 2
90 12
70
80
1
1
O4 Permintaan
100 7
O2 O3
Beda Baris
9
O1 8
Kapasitas Pabrik
50
90
60
0 70
3
0
1
6
5
70
Besarnya beda baris dan beda kolom berikutnya adalah sebagai berikut. Tabel 2.11. Beda baris dan beda kolom Baris atau kolom
Dua biaya termurah
Baris O1 Baris O2 Baris O4 Kolom D1 Kolom D2 Kolom D3 Kolom D4
Beda baris atau beda kolom 1 5 3 2 3 0 1
4 dan 5 1 dan 6 6 dan 9 8 dan 10 1 dan 4 6 dan 6 5 dan 6
Beda baris atau beda kolom terbesar adalah 5 yaitu pada baris O2, biaya termurah kolom O2 adalah 1 yaitu pada sel O2D2. Oleh karena itu sel O2D2 ini diisi terlebih dahulu, yang besarnya adalam minimum kapasitas O2 dan permintaan D2 yaitu 50. Dengan mengisi sel O2D2 sebesar 50, maka kapasitas O2 menjadi 40 dan permintaan D2 menjadi 0. Dengan demikian kolom D2 kita tandai dan tidak dimasukkan dalam program selanjutnya. Hasil perhitungan ini dapat kita lihat pada Tabel 2.12. Tabel 2.12. Kapasitas Pabrik
Destination (Tempat Tujuan)
Tempat Asal
D1
D2 12
D3 4
D4 9
D5 5
9
O1 8 O2 O3
1
6
6
Permintaan Beda Kolom
7
50
80 2
1
40 90
5
12
4
7
7
0 70
10
15
6
9
1 70
20 90 350
70
10
100
1
O4 0 50
Beda Baris
90
60
0 70
0
1
6
3
71
Besarnya beda baris dan beda kolom berikutnya adalah sebagai berikut. Tabel 2.13. Beda baris dan beda kolom. Baris atau kolom
Beda baris atau beda kolom 4 0 3 2 0 1
Dua biaya termurah
Baris O1 Baris O2 Baris O4 Kolom D1 Kolom D3 Kolom D4
4 dan 9 6 dan 6 6 dan 9 8 dan 10 6 dan 6 5 dan 6
Beda baris atau beda kolom terbesar adalah 4 yaitu pada baris O1, biaya termurah baris O1 adalah 5 yaitu pada sel O1D4. Oleh karena itu sel O1D4 ini diisi terlebih dahulu, yang besarnya adalam minimum sisa kapasitas O1 dan permintaan D4 yaitu 60. Dengan mengisi sel O1D4 sebesar 60, maka kapasitas O1 menjadi 40 dan permintaan D4 menjadi 0. Dengan demikian baris O4 kita tandai dan tidak dimasukkan dalam program selanjutnya. Hasil perhitungan ini dapat kita lihat pada Tabel 2.14. Tabel 2.14.
D1
D2 12
D3 4
D4 9
O1 O2
5
1
6
Beda Kolom
9
6
7
50 1
12
4
7
7
10
15
6
9
1 70
10 80 2
0 50
0 90
60 0
1
0 70
Beda Baris
40 100
4
40 90
0
0 70
70
O4 Permintaan
D5
60 8
O3
Kapasitas Pabrik
Destination (Tempat Tujuan)
Tempat Asal
20 90
3 350
72
Besarnya beda baris dan beda kolom berikutnya adalah sebagai berikut. Tabel 2.15. Beda baris dan beda kolom. Baris atau kolom
Dua biaya termurah
Baris O1 Baris O2 Baris O4 Kolom D1 Kolom D3
Beda baris atau beda kolom 3 2 4 2 0
9 dan 12 6 dan 8 6 dan 10 8 dan 10 6 dan 6
Beda baris atau beda kolom terbesar adalah 4 yaitu pada baris O4, biaya termurah baris O4 adalah 6 yaitu pada sel O4D3. Oleh karena itu sel O4D3 ini diisi terlebih dahulu, yang besarnya adalam minimum sisa kapasitas O4 dan permintaan D3 yaitu 20. Dengan mengisi sel O4D3 sebesar 20, maka kapasitas O4 menjadi 0 dan permintaan D2 menjadi 80. Dengan demikian baris O4 kita tandai dan tidak dimasukkan dalam program selanjutnya. Hasil perhitungan ini dapat kita lihat pada Tabel 2.16. Tabel 2.16. Destination (Tempat Tujuan)
Tempat Asal
D1
D2 12
D3 4
D4 9
O1 O2
1
Beda Kolom
9
6
6
7
50
2
40 100
3
40 90
2
4
7
7
0 70
10
15
6
9
1 70
20 0 90
0 70
350
20 80
Beda Baris
12
70
10
Kapasitas Pabrik
1
O4 Permintaan
5 60
8
O3
D5
0 50
70 90 0
0 60 1
4
73
Besarnya beda baris dan beda kolom berikutnya adalah sebagai berikut. Tabel 2.17. Beda baris dan beda kolom. Baris atau kolom
Beda baris atau beda kolom 3 2 4 3
Dua biaya termurah
Baris O1 Baris O2 Kolom D1 Kolom D3
9 dan 12 6 dan 8 8 dan 12 6 dan 9
Beda baris atau beda kolom terbesar adalah 4 yaitu pada kolom D1, biaya termurah kolom O1 adalah 8 yaitu pada sel O2D1. Oleh karena itu sel O2D1 ini diisi terlebih dahulu, yang besarnya adalam minimum sisa kapasitas O2 dan permintaan D1 yaitu 10. Dengan mengisi sel O2D1 sebesar 10, maka kapasitas O2 menjadi 30 dan permintaan D1 menjadi 0. Dengan demikian baris D1 kita tandai dan tidak dimasukkan dalam program selanjutnya. Hasil perhitungan ini dapat kita lihat pada Tabel 2.18. Tabel 2.18.
D1
D2 12
D3 4
O1
O3
Beda Kolom
9
10
50
D5 5
9
60
1
6
6
7
30
80 4
40 30 90
2
4
7
7
0 70
10
15
6
9
1
20 0
20 10
3
12
70
0
0 50
70 90
70 0 60
0 70
Beda Baris
40 0 100
1
O4 Permintaan
D4
40 8
O2
Kapasitas Pabrik
Destination (Tempat Tujuan)
Tempat Asal
90 350
3
Terakhir kekurangan kebutuhan D3 dicukupi oleh sisa dari O1 sebanyak 40 dan sisa O2 sebanyak 30. Dengan demikian kita peroleh sistem transportasi sebagai berikut: X13 = 40,
74
X14 = 60, X21 = 10, X22 = 50, X23 = 30, X31 = 70, X43 = 20, dan X45 = 70. Besarnya biaya transportasi dengan metode VAM adalah 40 (9) + 60 (5) + 10 (8) + 50 (1) + 30 (6) + 70 (1) + 20 (6) + 70 (1) = 1230. b. Menentukan Nilai Optimal Dari ketiga metode tersebut di atas dapat kita lihat bahwa metode yang paling sederhana adalah metode NWC, tetapi hasil dari metode ini umumnya kurang memuaskan. Sedangkan dengan metode VAM hasilnya paling baik, tetapi perhitungannya cukup rumit. Metode Inspeksi secara perhitungan sederhana, tetapi hasilnya mendekati dengan matode VAM. Jika kita diberi pertanyaan, metode mana yang akan dipakai untuk menyelesaikan masalah transportasi?. Maka jawabnya tergantung banyaknya sumber (banyaknya tempat produksi), banyaknya tempat tujuan serta waktu yang disediakan untuk memutuskan. Bilamana diberi waktu yang cukup, maka akan digunakan metode VAM, tetapi apabila waktu untuk memutuskan sempit maka metode Inspeksi sudah cukup baik. Masalah yang perlu ditanyakan lagi ialah apakah dengan metode Inspeksi atau VAM telah mencapai biaya optimum?. Untuk menjawab pertanyaan ini, ada dua metode untuk mengetahui apakah sudah optimum atau belum, untuk mengetahui optimalitas model transportasi digunakan metode Steppingstone atau metode Modi. i.
Metode Steppingstone
Metode Steppingstone bekerja dengan mempertimbangkan ”opportinity cost” dari sel kosong, yaitu berkurangnya biaya akibat pemindahan model pengangkutan bilamana sel kosong itu diisi satu barang. Sebagai ilustrasi perhatikan contoh berikut: Tabel 2.19. Menghitung opportunity cost sel kosong Destination ( Tujuan)
Tempat Asal
D1
D2 10
O1
60
5 10
6 O2 Permintaan
60
7 30
4 50 60
Kapasitas
D3
100 9 50
30
75
Dari Tabel 2.19 di atas, sel kosong adalah sel O2D1 dan sel O2D3, dengan biaya transportasi = 60 (10) + 10 (5) + 30 (7) + 50 (4) = 1.060 Untuk sel O2D1. Tabel 2.19.a. D1 O1 O2
D2 10
-1
5 +1
6 +1
4 -1
Andaikan sel O2D1 ini diisi satu barang, maka supaya kondisi seimbang sel O1D1 dan sel O2D2 dikurangi satu dan sel O1D2 ditambah satu. Sekarang perhatikan loop O2D1 → O1D1 → O1D2 → O2D2. Berturut-turut tambah 1, kurang 1, tambah 1, kurang 1. Perubahan biaya adalah = 6 - 10 + 5 – 4 = -3. Jadi opportunity cost sel O2D1 adalah 3. Ini artinya bahwa apabila kita mengisi sel O2D1 satu barang, maka terjadi pengurangan biaya sebesar 3. Untuk sel O2D3. Andaikan sel O2D3 ini diisi satu barang, maka supaya kondisi seimbang sel O2D2 dan sel O1D3 dikurangi satu dan sel O2D1 ditambah satu. Sekarang perhatikan loop O2D3 → O2D2 → O1D2 → O1D3. Berturut-turut tambah 1, kurang 1, tambah 1, kurang 1. Perubahan biaya adalah = 9 - 4 + 5 – 7 = 3. Jadi opportunity cost sel O2D3 adalah -3. Ini artinya bila kita mengisi sel O2D3 satu barang, maka terjadi penambahan biaya sebesar 3. Dari perhitungan di atas, maka sel O2D1 harus diisi sebanyak mungkin, sedangkan sel O2D3 tidak perlu diisi sebab apabila diisi akan menambah biaya (merugi). Banyaknya barang yang dapat diisikan pada sel O2D1 adalah minimum isi sel yang terkurangi yaitu O1D1 dan O2D2, jadi sel O2D1 dapat diisi sebesar 50, sehingga terbentuk Tabel 2.19.b.
76
Tabel 2.19.b. Tempat Asal O1 O2 Permintaan
Destination (Tujuan) D1
D2 10
10
D3 5
60 6
50 60
Kapasitas
7 30
4 60
9
100 50
30
Dari Tabel 2.19.b di atas, sel kosong adalah sel O2D2 dan sel O2D3. Untuk sel O2D2. Andaikan sel O2D2 ini diisi satu barang, maka supaya kondisi seimbang sel O2D1 dan sel O1D2 dikurangi satu dan sel O1D1 ditambah satu. Sekarang perhatikan loop O2D2 → O2D1 → O1D1 → O1D2. Berturut-turut tambah 1, kurang 1, tambah 1, kurang 1. Perubahan biaya adalah = 4 - 6 + 10 – 5 = 3. Jadi opportunity cost sel O2D1 adalah -3. Ini artinya bila kita mengisi sel O2D2 satu barang, maka terjadi penambahan biaya sebesar 3. Untuk sel O2D3. Andaikan sel O2D3 ini diisi satu barang, maka supaya kondisi seimbang sel O2D1 dan sel O1D3 dikurangi satu dan sel O1D1 ditambah satu. Sekarang perhatikan loop O2D3 → O2D1 → O1D1 → O1D3. Berturut-turut tambah 1, kurang 1, tambah 1, kurang 1. Perubahan biaya adalah = 9 - 6 + 10 – 7 = 6. Jadi opportunity cost sel O2D3 adalah -6. Ini artinya bila kita mengisi sel O2D3 satu barang, maka terjadi penambahan biaya sebesar 6. Dari perhitungan ini, semua opportunity cost sel kosong adalah negatif, maka Tabel 2.19.b. di atas telah optimal, dengan biaya transportasi = 10 (10) + 60 (5) + 30 (7) + 50 (6) = 910. Ini cocok bila kita hitung dari 1060 – 910 = 150, berasal dari pemindahan 50 satuan barang dengan opportunity cost 3. Untuk kasus di atas, kita dapat bekerja mulai hasil dari NWC, Inspeksi, atau VAM. Apabila kita mulai dari NWC, langkah pada metode NWC nya mudah, tetapi akan menjadi sukar pekerjaan di Steppingstone, apabila kita mulai dari VAM, maka akan sukar pada langkah di VAM nya, tetapi mudah pada langkah Steppingstone. Langkah yang cukup bijaksana
77
(meskipu tidak harus), adalah langkah awalnya dengan metode Inspeksi, sebab metode Inspeksi perhitungannya mudah dan hasilnya sudah dekat dengan langkah pada VAM. Dari langkah awal metode Inspeksi diperoleh hasil seperti Tabel 2.19.c. Tabel 2.19.c Tempat Asal
D1
D2 12
O1
D3 4 30
O2
1 50
D5 5
9
60 6
100 6
7
40
90
1
12
4
7
7
10
15
6
9
1
70
70
O4 Permintaan
D4 9
10 8
O3
Kapasitas Pabrik
Destination (Tempat Tujuan)
20 80
50
90
60
70
90
70
350
Dari Tabel 2.19.c di atas kita buat tabel opportunity cost sel kosong seperti pada Tabel 2.19.d berikut: Tabel 2.19.d. Hasil perhitungan opportunity cost sel kosong No 1 2 3 4 5 6 7 8 9 10 11 12
Sel kosong O1D2 O1D5 O2D1 O2D4 O2D5 O3D2 O3D3 O3D4 O3D5 O4D1 O4D2 O4D4
Loop
Perubahan biaya
O1D2→O1D3→O2D3→O2D2 O1D5→O4D5→O4D3→O1D3 O2D1→O1D1→O1D3→O2D3 O2D4→O2D3→O1D3→O1D4 O2D5→O4D5→O4D3→O2D3 O3D2→O3D1→O1D1→O1D3→O2D3→O2D2 O3D3→O3D1→O1D1→O1D3 O3D4→O3D1→O1D1→O1D4 O3D5→O4D5→O4D3→O1D3→O1D1→O3D1 O4D1→O1D1→O1D3→O4D3 O4D2→O2D2→O2D3→O4D3 O4D4→O4D3→O1D3→O1D4
4-9+6-1=0 9-1+6-9=5 8-12+9-6=-1 6-6+9-5=4 7-1+6-6=6 12-1+12-9+6-1=19 4-1+12-9=6 7-1+12-5=13 7-1+6-9+12-1=14 10-12+9-6=1 15-1+6-6=14 9+6+9-5=7
Opportunity cost 0 -5 1 -4 -6 -19 -6 -13 -14 -1 -14 -7
78
Dari tabel 2.19.d. di atas, terlihat bahwa opportunity cost terbesar adalah pada sel O2D1 sehingga sel ini harus diisi sebanyak mungkin. Sel ini diisi sebanyak minimun dari sel O1D1 dan O2D3 yaitu sebanyak 10. Sehingga Tabel 2.19.d. menjadi Tabel 2.19.e berikut: Tabel 2.19.e. Tempat Asal
D1
D2 12
D3 4
10
1 50
1
9
6
6
7
4
7
7
60
100
30 12
90
70
70 10
15
6
9
20
O4 Permintaan
D5 5
40 8
O3
D4 9
O1 O2
Kapasitas Pabrik
Destination (Tempat Tujuan)
80
50
90
1 70
60
70
90 350
Dari Tabel 2.19.e. di atas kita buat tabel opportunity cost semua sel kosong sehingga diperoleh Tabel 2.19.f berikut: Tabel 2.19.f. No 1 2 3 4 5 6 7 8 9 10 11 12
Sel kosong O1D1 O1D2 O1D5 O2D4 O2D5 O3D2 O3D3 O3D4 O3D5 O4D1 O4D2 O4D4
Loop
Perubahan biaya
O1D2→O1D3→O2D3→O2D1 O1D2→O1D3→O2D3→O2D2 O1D5→O4D5→O4D3→O1D3 O2D4→O2D3→O1D3→O1D4 O2D5→O4D5→O4D3→O2D3 O3D2→O3D1→O2D1→O2D3 O3D3→O3D1→O2D1→O2D3 O3D4→O3D1→O2D1→O2D3→O1D3→O1D4 O3D5→O4D5→O4D3→O2D3→O2D1→O3D1 O4D1→O2D1→O2D3→O4D3 O4D2→O2D2→O2D3→O4D3 O4D4→O4D3→O1D3→O1D4
12-9+6-8=1 4-9+6-1=0 9-1+6-9=5 6-6+9-5=3 7-1+6-6=6 12-1+8-1=18 4-1+8-6=5 7-1+8-6+9-5=12 7-1+6-6+8-1=13 10-8+6-6=2 15-1+6-6=14 9+6+9-5=7
Opportunity cost -1 0 -5 -3 -6 -18 -5 -12 -13 -2 -14 -7
79
Dari Tabel 2.19.f. terlihat bahwa tidak ada lagi sel kosong yang mempunyai opportunity cost positif, ini berarti bahwa Tabel 2.4.f telah optimal, dengan biaya transportasi =40 (9) + 60 (5) + 10 (8) + 50 (1) + 30 (6) + 70 (1) + 20 (6) + 70(1) = 1.230. Sebagai catatan bahwa opportunity cost sel O1D2 adalah nol, ini berarti bahwa sel ini diisi maupun tidak, tidak akan menambah atau mengurangi biaya transportasi.
ii. Modified Distribution Method (MODI) Pada penyelesaian metode Steppingstone umumnya akan mengalami kesulitan utama pada menentukan “loop”, apalagi kalau banyaknya sumber (tempat asal) atau tempat tujuan banyak. Metode Modi meniadakan loop yang banyak, dimana pada metode Modi ini setiap langkah mencari opportunity cost terbesar hanya memerlukan satu kali loop. Untuk membahas metode ini, perlu dikenalkan beberapa istilah / singkatan yang akan digunakan untuk merumuskan masalah transportasi. Misalkan banyaknya tempat asal adalah m dan banyaknya tempat tujuan n, dan misalkan Oi = tempat asal ke i, dimana i = 1, 2, ..., m. Dj = tempat tujuan ke j, dimana j = 1, 2, ..., n. Cij = besarnya biaya satuan pengiriman barang dari Oi ke Dj. Vi = bilangan baris, dimana i = 1, 2, ..., m. Uj = bilangan kolom, dimana j = 1, 2, ..., n. Kij = bilangan sel kosong. Langkah-langkah menghitung opportunity cost sel kosong. 1. Menghitung Vi dan Uj berdasarkan sel yang telah terisi sehingga dengan hubungan Cij = Vi + Uj. Dimana pertama kali kita dapat memberikan sebarang bilangan pada salah satu Vi atau Uj. 2. Menghitung Kij pada sel kosong dengan ketentuan Kij = Vi + Uj. 3. Menghitung opportunity cost sel kosong dengan ketentuan Opportunity cost = Kij – Cij. Sebagai ilistrasi perhatikan tabel berikut:
80
Tabel 2.19.f Destination ( Tujuan)
Tempat Asal
D1 10
O1
O2
D2
60
7
10
30 4
6
Bil Baris (Vi)
100
0
50
–1
D3 5
K21
Kapasitas
K23
9
50
Permintaan
60
60
30
Bil Kolom (Uj)
10
5
7
Misalkan kita ambil sebarang bilangan untuk V1 = 0, maka kita kita peroleh: U1 = C11 – V1 = 10 – 0 = 10 U2 = C12 – V1 = 5 – 0 = 5 U3 = C13 – V1 = 7 – 0 = 7 V2 = C22 – U2 = 4 – 5 = –1 K21 = V2 + U1 = (–1) + 10 = 9 K23 = V2 + U3 = (–1) + 7 = 6 Opportunity cost sel O2D1 = K21 – C21 = 9 – 6 = 3 Opportunity cost sel O2D3 = K23 – C23 = 6 – 9 = –3 Selanjutnya kita akan menghitung opportunity cost sel kosong pada masalah di atas dengan Modi. Pertama misalkan kita ambil Tabel hasil dari metode Inspeksi yaitu seperti Tabel 2.19.g berikut:
81
Tabel 2.19.g. Tempat Asal
D1
D2 12
D3 4
D4 9
10
O1
Kapasitas Pabrik
Destination (Tempat Tujuan)
30 8
1
5
9
60 6
50
O2
D5
12
6
7 90
4
7
7
70
O3
70 10
15
6
9
20
O4 Perminta an Bil. Kolom
0
100
40
1
Bil Baris (Vi)
80
50
1 70
90
60
90 350
70
Misalkan kita ambil V1 = 0, maka U1 = 12, U3 = 9, U4 = 5. Dari U1 = 12, diperoleh V3 = -11, dari U3 = 9, diperoleh V2 = -3, dan V4 = -3, dari V2 = -3, diperoleh U2 = 4, dan dari V4 = -3, diperoleh U5 = 4. Selanjutnya dengan menghitung Kij = = Vi + Uj, maka kita peroleh Tabel 2.19.h. Tabel 2.19.h. Tempat Asal
D1
D2 12
O1
D4 9
10
30 1
1
D5 5
9
60 6
50
O2
100 6
7
40 12
90 4
7
7
70
70 10
O4 Perminta an Bil. Kolom
D3 4
8
O3
Kapasitas Pabrik
Destination (Tempat Tujuan)
15
6
9
20 80 12
50 4
90 9
1 70
60 5
70 4
90 350
Bil Baris (Vi) 0 -3 -11 -3
82
Tabel 2.19.i. Hasil Perhitungan Opportunity cost sel kosong No Sel kosong Opp cost
1
2
3
4
5
6
7
8
9
10
11
12
O1D2 O1D5 O2D1 O2D4 O2D5 O3D2 O3D3 O3D4 O3D5 O4D1 O4D2 O4D4 0
-5
1
-4
-6
-19
-6
Dari hasil ini, bandingkan dengan Tabel 2.19.d. Perhitungan selanjutnya sama dengan metode Steppingstone.
-13
-14
-1
-14
-7
83
c. Penyelesaian Masalah Transportasi dengan Program Komputer i. Program Lindo Seperti pada penyelesaian program Linear dengan Lindo, masalah transportasi juga dapat dikerjakan dengan Lindo, yaitu dengan memandang masalah transportasi sebagai program Linear. Berikut akan dibahas masalah transportasi yang sama di atas, tetapi solusinya dengan Program Lindo. Tempat Asal
Destination (Tempat Tujuan) D1
D2 12
D3 4
D4 9
Kapasitas Pabrik
D5 5
9 100
O1 8
1
6
6
7
O2
90 1
12
4
7
7
10
15
6
9
1
O3
70
O4
90
Permintaan 80
50
90
60
70
350
Misalkan banyaknya barang pada sel Xij yaitu banyaknya barang yang dikirim dari pabrik Oi ke permintaan Dj, dan cij adalah biaya satuan pengiriman dari pabrik Oi ke permintaan Dj, maka basarnya biaya pengiriman adalah: Z = ∑ X ijcij
∑ X = per min taan D Untuk setiap i, ∑ X ij = kapasitas O i .
Dengan syarat untuk setiap j,
ij
j
, dan
Dari ketentuan ini, untuk kasus masalah transportasi ini, maka kita peroleh model. Minimumkan biaya: 12X11 + 4X12 +9 X13 + 5X14 + 9X15 + 8X21 + 1X22 + 6X23 + 6X24 + 7X25 + 1X31 + 12X32 + 4X33 + 7X34 + 7X35 + 10X41 + 15 X42 + 6X43 + 9X44 + 1X45 Dengan syarat X11 + X21 + X31 + X41 = 80 X12 + X22 + X32 + X42 = 50 X13 + X23 + X33 + X43 = 90
84
X14 + X24 + X34 + X44 = 60 X15 + X25 + X35 + X45 = 70 Dan
X11 + X12 + X13 + X14 + X15 =100 X21 + X22 + X23 + X24 + X25 = 90 X31 + X32 + X33 + X34 + X35 =70 X41 + X42 + X43 + X44 + X45 = 90 Xij ≥ 0, untuk setiap i dan j.
Dalam menyelesaikan program linear maupun masalah transportasi, indeks ditulis sejajar dengan variabelnya sehingga dalam penulisan pada Lindo sebagai berikut. MIN
12X11+4X12+9X13+5X14+9X15+8X21+1X22+6X23+6X24+7X25 +1X31+12X32+4X33+7X34+7X35+10X41+15X42+6X43+9X44+1X45
SUBJECT TO X11+X12+X13+X14+X15=100 X21+X22+X23+X24+X25=90 X31+X32+X33+X34+X35=70 X41+X42+X43+X44+X45=90 X11+X21+X31+X41=80 X12+X22+X32+X42=50 X13+X23+X33+X43=90 X14+X24+X34+X44=60 X15+X25+X35+X45=7 END
Setelah program Lindo dijalankan, maka akan diperoleh hasil sebagai berikut. LP OPTIMUM FOUND AT STEP
8
OBJECTIVE FUNCTION VALUE 1) VARIABLE X11 X12 X13 X14 X15 X21 X22 X23 X24 X25
1230.000 VALUE 0.000000 40.000000 0.000000 60.000000 0.000000 10.000000 10.000000 70.000000 0.000000 0.000000
REDUCED COST 1.000000 0.000000 0.000000 0.000000 5.000000 0.000000 0.000000 0.000000 4.000000 6.000000
85
X31 X32 X33 X34 X35 X41 X42 X43 X44 X45
ROW 2) 3) 4) 5) 6) 7) 8) 9) 10)
70.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 20.000000 0.000000 70.000000
0.000000 18.000000 5.000000 12.000000 13.000000 2.000000 14.000000 0.000000 7.000000 0.000000
SLACK OR SURPLUS 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
NO. ITERATIONS=
DUAL PRICES 0.000000 3.000000 10.000000 3.000000 -11.000000 -4.000000 -9.000000 -5.000000 -4.000000
8
RANGES IN WHICH THE BASIS IS UNCHANGED:
VARIABLE X11 X12 X13 X14 X15 X21 X22 X23 X24 X25 X31 X32 X33 X34 X35 X41 X42 X43 X44 X45
ROW 2
CURRENT COEF 12.000000 4.000000 9.000000 5.000000 9.000000 8.000000 1.000000 6.000000 6.000000 7.000000 1.000000 12.000000 4.000000 7.000000 7.000000 10.000000 15.000000 6.000000 9.000000 1.000000
CURRENT RHS 100.000000
OBJ COEFFICIENT RANGES ALLOWABLE ALLOWABLE INCREASE DECREASE INFINITY 1.000000 0.000000 4.000000 INFINITY 0.000000 4.000000 INFINITY INFINITY 5.000000 1.000000 5.000000 4.000000 0.000000 0.000000 2.000000 INFINITY 4.000000 INFINITY 6.000000 5.000000 INFINITY INFINITY 18.000000 INFINITY 5.000000 INFINITY 12.000000 INFINITY 13.000000 INFINITY 2.000000 INFINITY 14.000000 2.000000 5.000000 INFINITY 7.000000 5.000000 INFINITY RIGHTHAND SIDE RANGES ALLOWABLE INCREASE 0.000000
ALLOWABLE DECREASE 0.000000
86
3 4 5 6 7 8 9 10
90.000000 70.000000 90.000000 80.000000 50.000000 90.000000 60.000000 70.000000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
Tampilan yang muncul pada layar editor di atas merupakan penyelesaian suatu masalah transportasi yang dapat diartikan sebagai berikut. 1. Biaya minimum yang diperlukan untuk pengangkutan barang adalah 1.230 yang dapat dibaca dari OBJECTIVE FUNCTION VALUE 1)
1230.000
2. Alokasi pengiriman barang dapat diketahui dari nilai value pada hasil berikut. VARIABLE X11 X12 X13 X14 X15 X21 X22 X23 X24 X25 X31 X32 X33 X34 X35 X41 X42 X43 X44 X45
VALUE 0.000000 40.000000 0.000000 60.000000 0.000000 10.000000 10.000000 70.000000 0.000000 0.000000 70.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 20.000000 0.000000 70.000000
REDUCED COST 1.000000 0.000000 0.000000 0.000000 5.000000 0.000000 0.000000 0.000000 4.000000 6.000000 0.000000 18.000000 5.000000 12.000000 13.000000 2.000000 14.000000 0.000000 7.000000 0.000000
a. Dari O1 (tempat asal) dikirimkan ke D2 (tempat tujuan) sebanyak 40 unit, dan ke D4 sebanyak 60 unit. b. Dari O2 dikirimkan ke D1 sebanyak 10 unit, ke D2 sebanyak 10 dan dikirim ke D3 sebanyak 70
87
c. Dari O 3 dikirimkan sebanyak 70 unit ke D1. d. Dari O 4 dikirimkan sebanyak 20 unit ke D3, dan 80 unit ke D5 Reduced Cost adalah lawan dari opportunity cost, jadi apabila Reduced Cost = 4, maka opportunitu costnya = -4. Dengan demikian dari hasil di atas, tidak ada opportunity cost yang positif, jadi program optimal. Pada masalah transportasi keadaan pasar seimbang artinya jumlah permintaan akan barang sama dengan jumlah kapasitas produksi, maka dual price tidak memiliki makna khusus. Selanjutnya hasil berikut menunjukkan perubahan yang dibolehkan agar sistem transportasi tetap, dengan biaya optimal. RANGES IN WHICH THE BASIS IS UNCHANGED:
VARIABLE X11 X12 X13 X14 X15 X21 X22 X23 X24 X25 X31 X32 X33 X34 X35 X41 X42 X43 X44 X45
CURRENT COEF 12.000000 4.000000 9.000000 5.000000 9.000000 8.000000 1.000000 6.000000 6.000000 7.000000 1.000000 12.000000 4.000000 7.000000 7.000000 10.000000 15.000000 6.000000 9.000000 1.000000
OBJ COEFFICIENT RANGES ALLOWABLE ALLOWABLE INCREASE DECREASE INFINITY 1.000000 0.000000 4.000000 INFINITY 0.000000 4.000000 INFINITY INFINITY 5.000000 1.000000 5.000000 4.000000 0.000000 0.000000 2.000000 INFINITY 4.000000 INFINITY 6.000000 5.000000 INFINITY INFINITY 18.000000 INFINITY 5.000000 INFINITY 12.000000 INFINITY 13.000000 INFINITY 2.000000 INFINITY 14.000000 2.000000 5.000000 INFINITY 7.000000 5.000000 INFINITY
Misalnya c11 dapat turun sampai 11 atau naik sampai tak berhingga, c12 dapat turun sampai 0 dan tidak boleh naik, dan seterusnya.
88
Hasil terakhir yaitu ROW
CURRENT RHS
2 3 4 5 6 7 8 9 10
100.000000 90.000000 70.000000 90.000000 80.000000 50.000000 90.000000 60.000000 70.000000
RIGHTHAND SIDE RANGES ALLOWABLE INCREASE
ALLOWABLE DECREASE
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
Menunjukkan bahwa jumlah produksi maupun jumlah permintaan adalah tetap karena memang keadaan pasar seimbang.
ii. Program Lingo untuk Menyelesaikan Masalah Transportasi Lingo adalah salah satu program (software) dibawah Winston satu set bersama-sama dengan Lindo. Program Lingo lebih luas cakupannya, namun output (hasil keluaran) nya tidak selengkap program Lindo. Pada program Lingo, dapat mengolah data atau rumusan non-linear, seperti membuat grafik fungsi sinus, fungsi logarirmis, fungsi eksponen, dan lain-lain. Bentuk pemrograman Lingo juga lebih rumit sedikit, tetapi akan lebih efisien apabila digunakan untuk menyelesaikan masalah transportasi dengan banyak variabel. Karena pada program Lingo disediakan perintah (command) looping dengan perintah for ... loop. Sebagai contoh masalah transportasi yang sudak kita bahas di atas akan dikerjakan dengan program Lingo. Permasalahan transportasi di atas supaya lebih jelas, kita tulis lkembali tabelnya sebagai berikut.
89
Tabel Trasportasi Tempat Asal
Kapasitas Pabrik
Destination (Tempat Tujuan) D1
D2 12
D3 4
D4 9
D5 5
9 100
O1 8
1
6
6
7
O2
90 1
12
4
7
7
O3
70 10
15
6
9
1
O4 Permintaan
90 80
50
90
60
70
350
Dengan program Lingo, maka perintah untuk menyelesaikan masalah transportasi ini adalah. Model: Sets: ariable /O1, O2, O3, O4/:Asal; Permintaan/D1, D2, D3, D4, D5/ :Demand ; Links(Kapasitas,Permintaan) :Ship, Cost ; Endsets Min=@sum(Links:Ship*Cost); @for(Permintaan(j) :@sum(Kapasitas(i) :Ship(i,j))>Demand(j)) ; @for(Kapasitas(i) :@sum(Permintaan(j) :Ship(i,j))
Dari program di atas nampak bahwa, program Lingo ini sangat baik untuk masalah transportasi khususnya untuk banyak ariable, karena dengan Lingo, kita tidak usah mendefinisikan nama ariable. Perhatikan bahwa bentuk program Lingo untuk menyelesaikan masalah transportasi ini. Bentuk program sudah baku dan tidak perlu mengganti variabel/ menambah variabel. Perubahan program hanya mengubah banyaknya Kapasitas, Permintaan, dan perubahan pada data saja.
90
Setelah program dijalankan, maka akan diperoleh hasil sebagai berikut. Rows = 10 Vars = 20 No. integer vars = 0 ( all are linear) Nonzeros= 69 Constraint nonz= 40( 40 are +- 1) Density=0.329 Smallest and largest elements in absolute value = 1.00000 100.000 No. < : 4 No. =: 0 No. > : 5, Obj=MIN, GUBs <= 5 Single cols= 0 Optimal solution found at step: 15 Objective value: 1230.000 Variable ASAL( O1) ASAL( O2) ASAL( O3) ASAL( O4) DEMAND( D1) DEMAND( D2) DEMAND( D3) DEMAND( D4) DEMAND( D5) SHIP( O1, D1) SHIP( O1, D2) SHIP( O1, D3) SHIP( O1, D4) SHIP( O1, D5) SHIP( O2, D1) SHIP( O2, D2) SHIP( O2, D3) SHIP( O2, D4) SHIP( O2, D5) SHIP( O3, D1) SHIP( O3, D2) SHIP( O3, D3) SHIP( O3, D4) SHIP( O3, D5) SHIP( O4, D1) SHIP( O4, D2) SHIP( O4, D3) SHIP( O4, D4) SHIP( O4, D5) COST( O1, D1) COST( O1, D2) COST( O1, D3) COST( O1, D4) COST( O1, D5) COST( O2, D1) COST( O2, D2) COST( O2, D3) COST( O2, D4) COST( O2, D5) COST( O3, D1) COST( O3, D2) COST( O3, D3) COST( O3, D4) COST( O3, D5) COST( O4, D1) COST( O4, D2) COST( O4, D3) COST( O4, D4) COST( O4, D5)
Value 100.0000 90.00000 70.00000 90.00000 80.00000 50.00000 90.00000 60.00000 70.00000 0.0000000E+00 0.0000000E+00 40.00000 60.00000 0.0000000E+00 10.00000 50.00000 30.00000 0.0000000E+00 0.0000000E+00 70.00000 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 20.00000 0.0000000E+00 70.00000 12.00000 4.000000 9.000000 5.000000 9.000000 8.000000 1.000000 6.000000 6.000000 7.000000 1.000000 12.00000 4.000000 7.000000 7.000000 10.00000 15.00000 6.000000 9.000000 1.000000
Reduced Cost 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 1.000000 0.0000000E+00 0.0000000E+00 0.0000000E+00 5.000000 0.0000000E+00 0.0000000E+00 0.0000000E+00 4.000000 6.000000 0.0000000E+00 18.00000 5.000000 12.00000 13.00000 2.000000 14.00000 0.0000000E+00 7.000000 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00
91
Row
Slack or Surplus
1 2 3 4 5 6 7 8 9 10
1230.000 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00
Dual Price 1.000000 -11.00000 -4.000000 -9.000000 -5.000000 -4.000000 0.0000000E+00 3.000000 10.00000 3.000000
Makna hasil keluaran Lingo mirip dengan hasil keluaran dari Lindo, pembaca dipersilahkan mengartikan makna hasil keluaran di atas (sebagai latihan)
92
iii. Program Solver untuk Menyelesaikan Masalah Transportasi Untuk menyelesaikan masalah transportasi dengan Solver, maka kita buat tabel biaya, kapasitas, dan permintaan pada lembar kerja excel seperti berikut.
Langkah awal adalah membuat Tabel biaya pengiriman, kapasitas produksi dan permintaan. Tabel ini kita copy dan diletakkan dibawahnya, dengan mengganti menjadi Tabel Benyaknya Pengiriman Barang. Nilai awal yang diberikan kepada banyaknya barang yang dikirim dari Oi ke Dj adalah 0. Sedangkan banyaknya barang yang dikirim dari Oi adalah jumlah banyaknya barang yang dikirim dari Oi ke Dj untuk suatu i. Jadi dalam hal ini sel G16 ditulis dengan formula “=SUM(B16:F16)”. Formula ini di-copy-kan ke sel G17 sampai G19. Selanjutnya banyaknya Penerimaan Barang adalah jumlah barang yang
93
diterima dari Oi ke Dj untuk suatu j. Jadi dalam hal ini sel B20 ditulis dengan formula “=SUM(B16:B19)”. Formula ini di-copy-kan ke sel C20 sampai F20. Biaya Pengiriman merupakan kelipatan yang seletak antara banyaknya barang yang dikirim dengan biaya satuan pengiriman. Oleh karena itu pada sel B22 kita tuliskan formula “ =SUMPRODUCT(B6:F9,B16:F19)”.
Menjalankan Solver Setelah persiapan pada lembar kerja Excel selesai, saatnya menjalankan Solver, yaitu Tools, Solver, maka akan keluar menu Solver.
Hasil perhitungan total biaya kita letakkan pada sel B2, dan ini tidak diubah ke sel lain oleh karena itu semua hasil kita tetapkan dengan menambahkan tanda $ pada sel tempat perumusan hasil atau sumber. Sehingga untuk sel Set Target Cell kita ini dengan $B$22. Masalah yang kita cari adalah masalah minimumkan biaya transportasi, sehingga pada Equal To kita pilih Min. Selanjutnya pada By Changing Cells meminta bagian (kelompok) sel yang merupakan variabel. Pada masalah ini adalah menentukan banyaknya barang pada sistem transportasi, oleh karena itu kita isikan B18 sampai F19 sehingga kita tulis $B$16:$F$19. Subject to the Constraints meminta syarat pembatas. Dalam masalah ini ada dua syarat pembatas yaitu pembatas permintaan (penerimaan barang) dan Kapasitas Pabrik (Banyaknya barang yang dikirim), oleh karena itu. Pembatas permintaan yaitu permintaan harus dipenuhi, jadi permintaan kurang dari atau sama dengan penerimaan barang. Sehingga $B10:$F$10 <= $B20:$F$20.
94
Pembatas kapasitas menyatakan bahwa barang yang dikirim akan kurang dari atau sama dengan kapasitas pabrik. Sehingga $G$16:$G$19 <= $G$6:$G$9. Selanjutnya dengan memilih/mengisikan keterangan berikut pada menu solver, dan dengan mengisi options asumsi linear dan non-negatif variable. maka setelah dijalankan atau meng-klik Solve akan diperoleh hasil berikut.
Hasil ini menunjukkan bahwa Biaya Pengiriman sebesar 1.230, dengan sistem pengiriman: Produksi dari O1 sebanyak 100 unit, dikirim ke D2 sebanyak 40 unit, dan ke D4 sebanyak 60 unit. Produksi dari O2 sebanyak 90 unit, dikirim ke D1 sebanyak 10 unit, ke D2 sebanyak 10 unit, dan ke D3 sebanyak 70 unit. Produksi dari O3 sebanyak 70 unit, dikirim semuanya ke D3 yaitu sebanyak 70 unit. Produksi dari O4 sebanyak 90 unit, dikirim ke D3 sebanyak 20 unit dan ke D5 sebanyak 70 unit.
95
d. Masalah Transportasi Pasar Tidak Seimbang Kenyataan di lapangan, keadaan seimbang sangatlah langka. Keadaan yang sering terjadi adalah tidak seimbang. Ini desebabkan karena sangat sukar menentukan secara tepat kebutuhan lapangan yang sebenarnya. Ketidak seimbangan ada dua macam yaitu keadaan jumlah barang yang diproduksi lebih besar daripada kebutuhan lapangan atau sebaliknya kebutuhan di lapangan yang lebih besar daripada jumlah barang yang diproduksi.
Penyelesaian Masalah Transportasi Pasar Tidak Seimbang 1. Jumlah produksi lebih besar daripada permintaan pasar Apabila jumlah produksi lebih besar daripada jumlah permintaan di pasar, maka perlu ditambah tempat permintaan dummy yaitu permintaan yang tidak sebenarnya yang besarnya sama dengan selisih antara jumlah produksi dan jumlah permintaan, dan dalam tabel transportasi diberi biaya transportasi sebesar 0. Dalam kenyataan permintaan dummy ini adalah gudang perusahaan. Sebagai contoh, perhatikan masalah transportasi berikut: PT “Cocacola” memproduksi Coco cola, Fanta, dan Sprite di empat kota di Pulau Jawa untuk memenuhi permintaan masyarakat, yaitu kota P, Q, R, dan S berturut-turut 50, 70, 30, dan 80 truk setiap hari. Untuk mempermudah pemasaran, barang-barang produksi tersebut dikirim ke lima agen besar yaitu Agen A, B, C, D, dan E berturut-turut 40, 60, 30, 45, dan 50 truk. Jarak antara pabrik dan agen terlihat pada tabel berikut: Tabel Jarak antara Pabrik dan Agen (dalam km) Kota Tujuan / Permintaan A
B
C
D
E
P
40
105
70
20
40
Q
60
80
80
20
60
R
90
30
40
25
70
S
130
100
60
25
45
96
Dalam rangka penghematan penggunaan bahan bakar minyak (BBM), perusahaan akan mengirimkan barang-barang produksi tersebut dengan biaya terkecil, yaitu dengan meminimumkan jarak tempuh armada truknya. Di lain pihak, perusahaan ini memberi pelayanan kepada masyarakat sebaik mungkin, sehingga setiap truk hanya digunakan untuk mengirim satu kali. Buatlah sistem Transportasi untuk PT Cocacola ini dan berikan komentar saudara tentang sistem produksi pada perusahaan ini?. Dari masalah di atas, apabila tabel dilengkapi dengan permintaan virtual maka akan diperoleh tabel berikut. Kota Tujuan / Permintaan A
B
C
D
E
Dummy
Produksi
P
40
105
70
20
40
0
50
Q
60
80
80
20
60
0
70
R
90
30
40
25
70
0
30
S
130
100
60
25
45
0
80
Permintaan
40
60
30
45
50
5
230
Penyelesaian masalah ini deserahkan kepada pembaca. 2. Jumlah produksi lebih kecil daripada permintaan pasar Dalam hal jumlah produksi lebih kecil daripada permintaan pasar, maka ada tempat permintaan yang tidak dikirim barang secara penuh. Dalam menyelesaikan masalah ini, dapat ditambahkan pabrik dummy yang memproduksi sebanyak selisih antara jumlah permintaan dan jumlah kapasitas produksi, pada tabel biaya transportasi, kapasitas produksi dan permintaan dilengkapi dengan pabrik virtual dengan biaya transportasi 0. Kemudian tempat permintaan yang dikirim dari pabrik dummy ini akan mengalami kekurangan barang sebanyak produksi virtual tersebut. Contoh masalah dan penyelesaiannya diserahkan kepada pembaca.
97
Penerapan Metode Transportasi Selanjutnya kita bahas masalah transportasi pada PT Aqua Golden Mississippi di Jawa Barat. Data Permintaan dan penawaran adalah sebagai berikut: Tabel 2.5.a. Data Lokasi Pabrik dan Kapasitas Produksi di Jawa Barat dalam 1 Tahun No
Lokasi Pabrik
Aktivitas
Kapasitas Produksi
1
Bekasi
Produksi AQUA
250.000.000 Liter
2
Citeurep (Bogor)
Produksi AQUA
200.000.000 Liter
3
Cimelati (Sukabumi)
Produksi AQUA
200.000.000 Liter
4
Kuningan
Produksi AQUA
100.000.000 Liter
Kapasitas Produksi dalam 1
Tahun
750.000.000 Liter
Sumber: PT. Tirta Babakan Pari Cimelati (Sukabumi) Produksi AQUA
Tabel 2.5.b Data Jarak Lokasi Pabrik dengan 12 kota Daerah Pemasaran dan Demand Tujuan Pengiriman Lokasi
1
2
3
4
5
6
7
8
9
10
11
12
Bekasi
119
140
29
0
84
87
148
154
217
261
260
229
Citeurep (Bogor)
148
118
58
87
163
0
61
129
192
194
235
259
Cimelati (Sukabumi)
209
179
119
148
136
61
0
96
159
261
202
226
Kuningan
383
404
293
261
235
194
261
165
192
0
185
35
40
40
195
50
55
40
35
145
35
30
35
50
Pabrik
Kebutuhan Permin taan (Demand)
Keterangan : Angka pada kolom 1 sampai dengan kolom 12 adalah nama kota tujuan pengiriman: 1) Serang; 2) Pandeglang; 3) Jakarta; 4) Bekasi; Sukabumi; 8) Bandung; 9) Garut
5. Purwakarta; 6. Bogor ; 7.
; 10) Kuningan; 11) Tasikmalaya; 12) Cirebon.
98
Angka yang ada dalam kolom dibawah kolom nama kota adalah angka jarak antara pabrik dengan kota tujuan pengiriman dalam kilometer ( Km ), sedangkan biaya angkut dihitung dalam puluhan ribu rupiah (Rp 10.000,-) per satu juta liter kilometer. Jumlah kebutuhan atau permintaan dalam juta liter per tahun untuk tiap kota yang menjadi tujuan pengiriman. Setelah informasi/data di atas tersedia maka langkah selanjutnya menuliskan permasalahan yang ada ke dalam bentuk tabel biaya pengangkutan atau jarak. Pada PT.AQUA di Jawa Barat seperti terlihat pada tabel 4. untuk kapasitas produksi per tahun dan pada tabel 5. untuk jarak antara lokasi pabrik dengan kota tujuan pengiriman, sedangkan biaya dihitung dalam Rp 10.000,- per satu juta liter kilometer. Kemudian merumuskan dan menuliskannya pada papan editor dalam bentuk persamaan linear untuk fungsi tujuan, fungsi kendala, dan penyelesaian non negatif. Data pada PT.AQUA Golden Mississippi Jawa Barat seperti tercantum pada tabel 2.5.a. dan tabel 2.5.b
bentuk
penulisan pada papan editor LINDO untuk diolah sebagai berikut: MIN 119X11+140X12+29X13+84X15+87X16+148X17+154X18+217X19+261X110 +260X111+229X112+148X21+118X22+58X23+87X24+163X25+61X27+129X28 +192X29+194X210+235X211+259X212+209X31+179X32+119X33+148X34 +136X35+61X36+96X38+159X39+261X310+202X311+226X312+383X41 +404X42+293X43+261X44+235X45+194X46+261X47+165X48+192X49 +185X411+35X412 SUBJECT TO X11+X12+X13+X14+X15+X16+X17+X18+X19+X110+X111+X112 = 250 X21+X22+X23+X24+X25+X26+X27+X28+X29+X210+X211+X212 = 200 X31+X32+X33+X34+X35+X36+X37+X38+X39+X310+X311+X312 = 200 X41+X42+X43+X44+X45+X46+X47+X48+X49+X410+X411+X412 = 100 X11+X21+X31+X41
=
40
X12+X22+X32+X42
=
40
X13+X23+X33+X43
=
X14+X24+X34+X44
=
50
X15+X25+X35+X45
=
55
X16+X26+X36+X46
=
40
X17+X27+X37+X47
=
35
195
99
X18+X28+X38+X48
=
X19+X29+X39+X49
=
145 35
X110+X210+X310+X410 = 30 X111+X211+X311+X411 = 35 X112+X212+X312+X412 = 50 End
Jika tidak ada kesalahan, maka proses dapat dilanjutkan untuk mencari jawaban yang optimal. Langkah untuk mencari jawaban optimal adalah dengan menggunakan Solve Solve. Kemudian secara otomatis LINDO akan membuka papan editor report. Pada kasus PT.AQUA Golden Mississippi di atas akan muncul tampilan sebagai berikut. LP OPTIMUM FOUND AT STEP
17
OBJECTIVE FUNCTION VALUE 1) VARIABLE X11 X12 X13 X15 X16 X17 X18 X19 X110 X111 X112 X21 X22 X23 X24 X25 X27 X28 X29 X210 X211 X212 X31 X32 X33 X34 X35 X36 X38 X39 X310
51320.00 VALUE 0.000000 0.000000 145.000000 55.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 40.000000 40.000000 50.000000 0.000000 0.000000 0.000000 0.000000 30.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 145.000000 5.000000 0.000000
REDUCED COST 0.000000 51.000000 0.000000 0.000000 116.000000 144.000000 54.000000 54.000000 240.000000 54.000000 173.000000 0.000000 0.000000 0.000000 58.000000 50.000000 28.000000 0.000000 0.000000 144.000000 0.000000 174.000000 94.000000 94.000000 94.000000 152.000000 56.000000 94.000000 0.000000 0.000000 244.000000
100
X311 X312 X41 X42 X43 X44 X45 X46 X47 X48 X49 X411 X412 X14 X26 X37 X410 ROW 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17)
15.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 20.000000 50.000000 50.000000 40.000000 35.000000 30.000000
0.000000 174.000000 285.000000 336.000000 285.000000 282.000000 172.000000 244.000000 278.000000 86.000000 50.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
SLACK OR SURPLUS 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
NO. ITERATIONS=
DUAL PRICES 29.000000 0.000000 33.000000 50.000000 -148.000000 -118.000000 -58.000000 -29.000000 -113.000000 0.000000 -33.000000 -129.000000 -192.000000 -50.000000 -235.000000 -85.000000
17
RANGES IN WHICH THE BASIS IS UNCHANGED:
VARIABLE X11 X12 X13 X15 X16 X17 X18 X19 X110 X111 X112 X21 X22
CURRENT COEF 119.000000 140.000000 29.000000 84.000000 87.000000 148.000000 154.000000 217.000000 261.000000 260.000000 229.000000 148.000000 118.000000
OBJ COEFFICIENT RANGES ALLOWABLE ALLOWABLE INCREASE DECREASE INFINITY 0.000000 INFINITY 51.000000 0.000000 50.000000 50.000000 INFINITY INFINITY 116.000000 INFINITY 144.000000 INFINITY 54.000000 INFINITY 54.000000 INFINITY 240.000000 INFINITY 54.000000 INFINITY 173.000000 0.000000 INFINITY 51.000000 INFINITY
101
X23 X24 X25 X27 X28 X29 X210 X211 X212 X31 X32 X33 X34 X35 X36 X38 X39 X310 X311 X312 X41 X42 X43 X44 X45 X46 X47 X48 X49 X411 X412 X14 X26 X37 X410
58.000000 87.000000 163.000000 61.000000 129.000000 192.000000 194.000000 235.000000 259.000000 209.000000 179.000000 119.000000 148.000000 136.000000 61.000000 96.000000 159.000000 261.000000 202.000000 226.000000 383.000000 404.000000 293.000000 261.000000 235.000000 194.000000 261.000000 165.000000 192.000000 185.000000 35.000000 0.000000 0.000000 0.000000 0.000000
ROW
CURRENT RHS 250.000000 200.000000 200.000000 100.000000 40.000000 40.000000 195.000000 50.000000 55.000000 40.000000 35.000000 145.000000 35.000000 30.000000 35.000000 50.000000
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
50.000000 INFINITY INFINITY INFINITY INFINITY 0.000000 INFINITY INFINITY INFINITY INFINITY INFINITY INFINITY INFINITY INFINITY INFINITY 0.000000 50.000000 INFINITY 0.000000 INFINITY INFINITY INFINITY INFINITY INFINITY INFINITY INFINITY INFINITY INFINITY INFINITY 50.000000 173.000000 58.000000 94.000000 28.000000 144.000000 RIGHTHAND SIDE RANGES ALLOWABLE INCREASE 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 58.000000 50.000000 28.000000 0.000000 56.000000 144.000000 0.000000 174.000000 94.000000 94.000000 94.000000 152.000000 56.000000 94.000000 INFINITY 0.000000 244.000000 50.000000 174.000000 285.000000 336.000000 285.000000 282.000000 172.000000 244.000000 278.000000 86.000000 50.000000 144.000000 INFINITY INFINITY INFINITY INFINITY INFINITY
ALLOWABLE DECREASE 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
102
Hasil pengolahan data tersebut di atas, dapat diartikan sebagai berikut: 1. Biaya minimum yang diperlukan untuk pengangkutan dan distribusi air mineral AQUA di Jawa Barat dalam satu tahun sebesar Rp 513.200.000,2. Alokasi pengiriman barang (air AQUA) dari lokasi pabrik sampai ke tempat tujuan pengiriman dapat digambarkan dalam Tabel 2.5.c berikut: Keterangan Tabel 2.5.c 1) Bilangan dalam kolom kanan atas adalah data jarak pabrik dengan kota tujuan pengiriman (dalam Km); 2) Angka yang dicetak merah dalam kolom adalah alokasi pengiriman ke kota tujuan selama satu tahun (dalam juta liter); 3) Biaya dalam puluhan ribu rupiah per juta liter kilometer; 4) Kapasitas pabrik dalam juta liter per tahun; 5) Kebutuhan permintaan dalam juta liter per tahun Proporsi pengiriman barang atau alokasi pengiriman barang yang diperlukan agar biaya yang ditanggung oleh PT. AQUA minimal/ efisien adalah sebagai berikut: a. Dari lokasi pabrik Bekasi di kirim ke Jakarta sebanyak 145 juta liter, untuk kota Bekasi sendiri dipenuhi oleh pabrik Bekasi sebanyak 50 juta liter dan sebanyak 55 juta liter dikirim ke kota Purwakarta. b. Dari lokasi pabrik Citeurep (Bogor) dikirim ke Serang sebanyak 40 juta liter, dikirim ke Pandeglang sebanyak 40 juta liter, dan kekurangan kebutuhan kota Jakarta sebanyak 50 juta liter dipenuhi oleh pabrik Bogor, untuk kota Bogor dipenuhi dari Bogor sendiri sebanyak 40 juta liter, dan sebanyak 30 juta liter dikirim ke Garut. c. Dari lokasi pabrik
Cimelati (Sukabumi) untuk memenuhi permintaan kota
Sukabumi sendiri sebanyak 35 juta liter, dikirim ke Bandung sebanyak 145 juta liter, dikirim ke Garut sebanyak 5 juta liter dan 15 juta liter dikirim ke Tasikmalaya. d. Dari lokasi pabrik
Kuningan untuk memenuhi kebutuhan permintaan kota
Kuningan sendiri sebanyak 30 juta liter, dikirim ke Tasikmalaya sebanyak 20 juta liter dan 50 juta liter dikirim ke Cirebon.
103
Tabel 2.5.c Hasil Akhir Perhitungan dengan LINDO dan Alokasi Pengiriman Barang
Lokasi Pabrik
Tujuan Pengiriman Serg
Pandl
Jakt
119
140
29
Bekasi
145
Citeurep
148
118
58
(Bogor)
40
40
50
Cimelati
209
179
119
Bks
Pwkt 0
50 87
84
Bgr
Skb 87
Bdg
148
163
0
61
404
293
129
40 148 261
217
Kng
Tasik
261
260
Cirb
136 235
Pabrik
229 250
61 194
192
194
235
259
30 0 35
383
154
Gart
55
(Sukabumi) Kuningan
Kapasitas
261
96 145 165
159
200 261
5 192
202
226
15 0
185
200 35
30
20
50
100
30
35
50
750
Kebutuhan Permintaan (Demand)
40
40
195
50
55
40
35
145
35
104 Penyelesaian dengan Solver seperti terlihat berikut. Tabel Awal Lokasi
Tujuan Pengiriman
Kapasitas
Serg
Pandl
Jakt
Bks
Pwkt
Bgr
Skb
Bdg
Gart
Kng
Tasik
Cirb
Pabrik
Bekasi
119
140
29
0
84
87
148
154
217
261
260
229
250
Citeurep
148
118
58
87
163
0
61
129
192
194
235
259
200
Cimelati
209
179
119
148
136
61
0
96
159
261
202
226
200
Kuningan
383
404
293
261
235
194
261
165
192
0
185
35
100
(Demand)
40
40
195
50
55
40
35
145
35
30
35
50
750
Pabrik
Penyelesaian sistem transportasi Lokasi
Tujuan Pengiriman
Dikirim
Serg
Pandl
Jakt
Bks
Pwkt
Bgr
Skb
Bdg
Gart
Kng
Tasik
Cirb
Pabrik
Bekasi
0
0
145
50
55
0
0
0
0
0
0
0
250
Citeurep
40
40
50
0
0
40
0
0
15
0
15
0
200
Cimelati
0
0
0
0
0
0
35
145
20
0
0
0
200
Kuningan
0
0
0
0
0
0
0
0
0
30
20
50
100
Diterima
40
40
195
50
55
40
35
145
35
30
35
50
750
Pabrik
Total Biaya
51320
Bandingkan hasil ini dengan penggunaan Lindo, selanjutnya perhitungan secara konvensional atau dengan program Lingo diserahkan kepada pembaca sebagai latihan.
Soal-soal 1. CV “Aneka Ukir” membuat sejumlah ukiran di empat kota dan akan dikirim ke empat kota lain. Dari keempat kota pembuat itu berturut-turut membuat 18, 4, 6, dan 12 set ukiran. Permintaan ke empat kota itu berturut-turut 6, 14, 15, dan 5 set ukiran. Biaya transportasi dari kota pembuat ke kota permintaan terlihat pada Tabel 1 berikut: Tabel 1. Biaya pengiriman tiap set ukiran (dalam ribuan rupiah) Kota
Kota Tujuan / Permintaan
105 Pembuat
A
B
C
D
P
9
7
12
8
Q
15
12
12
15
R
8
6
9
12
S
14
12
11
12
Tentukan sistem pengiriman ukir agar diperoleh biaya pengiriman minimum. 2. Tabel 2 dan Tabel 3 berikut adalah hasil perhitungan suatu model transportasi. Tabel 2. Hasil perhitungan I.
Kota A
Kota B 6
Pabrik I
30
8
Kapasitas 10
40 11
Pabrik II Kebutuhan
Kota C
30
70 6
8
20
30
60
30
50
Tabel 3. Hasil perhitungan II.
Kota A
Kota B 6
Pabrik I
30
8 10
11 Pabrik II
Kebutuhan
Kota C 10 30
70
6
8
50
30
60
Kapasitas
50
30
Manakah hasil yang paling menguntungkan dari hasil perhitungan model transportasi di atas. Berikan komentar saudara tentang hasil kedua perhitungan tersebut (Tabel 2 dan Tabel 3)!
106 3. Perusahaan Karoseri Mobil “Arifin” akan membuat sejumlah mobil pengangkut untuk melayani sebuah perusahaan Travel. Mesin yang digunakan adalah mesin jenis mesin disel seri ENG450, mesin ini harus didatangkan dari perusahaan ”ANY”. Perusahaan Arifin membuat kontrak kerja dengan perusahaan pengangkutan untuk mengambil mesin dan menyimpanya bila tidak segera dipasang (diinstall). Semua mobil tersebut harus diselesaikan sampai akhir bulan keempat. Perusahaan pengangkutan itu menjadwalkan pengantaran mesin jet seperti pada Tabel 2 di bawah. Secara komulatif pada akhir bulan ke 1, 2, 3, dan 4 berturut-turut sekurangkurangnya 10, 25, 50, dan 70 buah mesin. Jumlah mesin yang didatangkan tiap bulan paling banyak terlihat pada kolom ketiga pada Tabel 2. Sedangkan biaya produksi (dalam ratusan juta rupiah) tiap mobil tiap bulannya berbeda dan terlihat pada kolom keempat. Biaya penyimpanan mesin yang tidak dipasang pada bulan yang bersangkutan 150,000 tiap bulannya, dan terlihat pada kolom paling kanan pada Tabel 2. Tabel 2. Data jadwal dan biaya produksi mobil Pemasangan
Produksi
Biaya satuan
Biaya satuan
yang dijadwalkan
maksimum
produksi
penyimpanan
1
10
25
1.08
0.015
2
15
35
1.11
0.015
3
25
30
1.10
0.015
4
20
10
1.13
Bulan ke
Manajer perusahaan ingin membuat jadwal pembuatan pesawat, agar biaya produksi dan biaya penyimpanan minimum. 4. Perusahaan mobil akan menanamkan modalnya untuk membuat tiga pabrik di kota A, B, dan C berturut-turut mempunyai kapasitas produksi 2000, 1300, dan 1600 unit setiap tahunnya. Mobil-mobil itu akan dijual di kota-kota P, Q, R, dan S dengan permintaan berturut-turut 1000, 1500, 1200, dan 700 unit tiap tahunnya. Biaya pengiriman tiap unit dari pabrik ke tempat penjualan terlihat pada Tabel 3 berikut:
107 Tabel 3. Biaya pengiriman tiap-tiap unit mobil (dalam ribuan rupiah) Pabrik pembuat-an Mobil
Kota Penjualan Mobil P
Q
R
S
A
1000
8000
1800
2000
B
400
700
900
1400
C
800
1200
900
1100
Tentukan model trasnportasi agar diperoleh biaya pengiriman mobil minimal. 5. Perusahaan Motor Nasional akan dibuat di tiga kota yaitu Kota A, Kota B dan Kota C. Hasil Produksi Motor tersebut akan disalurkan ke 4 Agen besar, yaitu Agen W, Agen X, Agen Y dan Agen X. Biaya satuan pengiriman Motor, Jumlah produksi dan Jumlah kebutuhan Agen terlihat pada tebel berikut. Tabel Biaya satuan pengiriman Motor, Jumlah produksi dan Jumlah kebutuhan Agen Agen W
Agen X
Agen Y
Agen Z
Kapasitas Produksi
Kota A
100
800
180
200
20000
Kota B
40
70
90
140
13000
Kota C
80
120
90
110
16000
10000
15000
12000
7000
Permintaan
Buatlah sistem transportasi agar biaya pengiriman Motor minimum!
108 F. Penugasan Masalah penugasan bermula dari penempatan para pekerja pada bidang yang tersedia agar biaya yang ditanggung perusahaan dapat diminimalkan. Jika pekerja dianggap sebagai sumber dan pekerjaan dianggap sebagai tujuan, maka model transportasi akan sama dengan masalah transportasi, dimana jumlah sumber dan tujuan sama, setiap sumber hanya menghasilkan satu demikian pula setiap tujuan hanya memerlukan satu. Untuk lebih mudah memahami, marilah kita perhatikan contoh berikut: Sebuah perusahaan yang berada di tiga kota yaitu Banjarmasin, Solo, dan Denpasar memerlukan tenaga ahli untuk menyelesaikan pekerjaan tertentu. Ketiga ahli itu berada di Jakarta, Surabaya, dan Ujung Pandang. Biaya ketiga orang ahli tersebut adalah seperti Tabel 2.6.a. Tabel 2.6.a.
Asal Ahli
Tujuan Banjarmasin
Solo
Denpasar
Jakarta
30
36
40
Surabaya
20
25
29
Ujung Pandang
27
24
22
Cara menentukan total biaya minimum adalah dengan mengurangkan setiap baris dengan bilangan terkecil dari baris itu sendiri, sehingga kita peroleh tabel berikut: 0
6
10
0
5
9
5
2
0
Selanjutnya dikurangi dengan bilangan terkecil menurut kolom-kolomnya, sehingga diperoleh tabel berikut: 0
4
10
0
3
9
5
0
0
109 Selanjutnya dibuat garis sesedikit mungkin menurut baris atau kolom sehingga menutup semua bilangan nol (0). Bilamana jumlah garis masih lebih kecil dari banyaknya baris atau kolom, maka belum dapat disusun tabel optimalnya. Dalam hal diatas diperlukan dua garis, sehingga harus dilakukan langkah berikutnya yaitu: Mengurangi semua bilangan yang tidak tertutup garis dengan bilangan terkecil, dan menambahkan bilangan tersebut kepada persilangan garis penutup. Pada masalah diatas, diperoleh tabel berikut: 0
1
7
0
0
6
8
0
0
Dari tabel di atas, bagaimanapun caranya mencoret bilangan nol, paling sedikit diperlukan tiga buah garis. Langkah selanjutnya memilih sel nol untuk setiap baris atau kolom. Caranya ialah ada dua yaitu menurut baris atau menurut kolom. Pilih sel yang baris/kolom yang bilangan nolnya hanya satu (paling sedikit) Buang baris dan kolom pada sel yang terpilih. Lakukan terus sampai selesai. Dari tabel diatas misalnya kita lakukan pada baris, maka sel pada baris 1 kolom 1 adalah set pertama yang dipilih, jadi baris 1 dan kolom 1 dibuang (diabaikan) 0 0 8
*
1 0 0
7 *
6 0
*
Setelah kita lakukan proses diatas, maka sel yang terpilih adalah sel (1,1), (2,2), dan (3,3). Sehingga total biaya minimal yang diperlukan adalah 30 + 25 + 22 = 77. Dimana Banjarmasin mendatangkan ahli dari Jakarta, Solo mendatangkan ahli dari Surabaya, dan Denpasar mendatangkan ahli dari Ujung Pandang.
110 Masalah penugasan ini juga dapat digunakan untuk masalah maksimum, yaitu dengan mengubah sedikit masalah maksimum ke minimum. Untuk lebih mudahnya kita ambil contoh berikut: Sebuah Perusahaan akan memberi tugas kepada tiga orang ( A, B, C) untuk menduduki jabatan tertentu (X,Y, Z). Keuntungan dari ketiga orang pada ketiga jabatan tersebut sebagai berikut: Jabatan
Pekerja
X
Y
Z
A
20
26
30
B
10
15
19
C
17
14
12
Langkah pertama adalah membuat tabel regrete, yaitu tabel karena tidak mengambil tindakan terbaik. Cara membuat adalah dengan mengurangkan setiap sel dengan bilangan terbesar tiap barisnya. Langkah ini menghasilkan tabel berikut: 10
4
0
9
4
0
0
3
5
Selanjutnya kita lakukan langkah-langkah seperti pekerjaan minimum, sehingga kita peroleh tabel berikut: 6
0
0
4
0
0
0
3
9
Penugasan optimal dicapai pada 6
0
4
0
0
*
3
0 *
0 9
*
Pekerja A pada jabatan Z, Pekerja B pada jabatan Y, Pekerja C pada jabatan X, dengan keuntungan = 30 + 15 + 17 = 62
111 Atau 6
0
4
0
0
3
9
0
*
*
Pekerja A pada jabatan Y, Pekerja B pada jabatan Z, Pekerja C pada jabatan X, dengan keuntungan = 26 + 19 + 17 = 62
0 *
Tabel Pekerja dan Jabatan Jabatan
Pekerja
X
Y
Z
A
20
26
30
B
10
15
19
C
17
14
12
Penyelesaian dengan Lindo. Dengan komputer (program Lindo) juga dapat digunakan untuk menyelesaikan masalah penugasan ini yaitu seperti permasalahan pada transportasi. Program perhitungan dipersilahkan kepada pembaca sebagai latihan. MAX
20 AX + 26 AY + 17 CX + 14 SUBJECT TO 2) AX + 3) BX + 4) CX + 5) AX + 6) AY + 7) AZ + END
+ 30 AZ + 10 BX + 15 BY + 19 BZ CY + 12 CZ AY BY CY BX BY BZ
+ + + + + +
AZ BZ CZ CX CY CZ
= = = = = =
1 1 1 1 1 1
Hasil perhitungan dengan Lindo diperoleh sebaga berikut: LP OPTIMUM FOUND AT STEP
7
OBJECTIVE FUNCTION VALUE 1) VARIABLE AX AY AZ
62.00000 VALUE 0.000000 0.000000 1.000000
REDUCED COST 9.000000 0.000000 0.000000
112 BX BY BZ CX CY CZ
ROW 2) 3) 4) 5) 6) 7)
0.000000 1.000000 0.000000 1.000000 0.000000 0.000000
8.000000 0.000000 0.000000 0.000000 0.000000 6.000000
SLACK OR SURPLUS 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
LP OPTIMUM FOUND AT STEP
DUAL PRICES 0.000000 -11.000000 -12.000000 29.000000 26.000000 30.000000 3
OBJECTIVE FUNCTION VALUE 1)
62.00000
VARIABLE BX BY BZ CX CY CZ AX AY AZ
ROW 2) 3) 4) 5) 6) 7)
VALUE 0.000000 0.000000 1.000000 1.000000 0.000000 0.000000 0.000000 1.000000 0.000000
SLACK OR SURPLUS 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
NO. ITERATIONS=
REDUCED COST 0.000000 0.000000 0.000000 0.000000 8.000000 14.000000 1.000000 0.000000 0.000000
DUAL PRICES 0.000000 5.000000 9.000000 21.000000 10.000000 17.000000
3
Diselesaikan dengan Solver, maka kita buat tabel dan hasilnya sebagai berikut. Seperti pada penyelesaian masalah transportasi, masalah Penugasan dikerjakan dengan memulai mengisi nilai awal = 0. sehingga tabel awalnya sebagai berikut
113
Setelah solver dijalankan dengan mengisi / memilih seperti gambar berikut.
Selanjutnya dengan memilih Solve, maka akan diperoleh hasil seperti berikut.
114
Dari hasil ini dapat disimpulkan bahwa Pendapatan optimun terjadi apabila A ditempatkan pada jabatan Z, B pada jabatan Y dan C pada jabatan X. Dengan pendapatan sebesar 62.
Soal-soal 1.
Suatu perusahaan memerukan 4 orang untuk 4 pekerjaan, sebut saja pekerjaan P, Q, R, dan S. Pekerjaan-pekerjaan itu akan diisi oleh 4 calon, yaitu: A1, A2, A3, dan A4. Prediksi pendapatan tiap bulan yang diperoleh apabila pekerjaan diserahkan kepada pekerja tersebut adalah seperti Tabel 3 berikut: Tabel 3. Prediksi pendapatan dari Pekerjaan Pekerjaan
Kode Pelamar A1
A2
A3
A4
P
100
120
85
100
Q
70
110
70
80
R
95
110
90
90
S
90
115
80
100
115 Gaji yang diminta tiap bulan dari pekerja tersebut adalah seperti Tabel 4 berikut: Tabel 4. Data permintaan gaji pelamar Pekerjaan
Gaji
Kode Pelamar A1
A2
A3
A4
50
60
50
45
Berikan penyelesaian tentang posisi pekerjaan para pekerja tersebut agar pendapatan perusahaan maksimum.
2.
Sebuah Kantor akan mengangkat empat Kepala SubBagian (Kasubag) dari empat orang, yaitu Keuangan, Rumah Tangga, Pelayanan Masyarakat, dan Kerja Sama. Keempat calon adalah A1, A1, A3, dan A4. Dari keempat orang tersebut mengajukan anggaran seperti terlihat pada Tabel 4 berikut: Tabel 4. Usulan dana berkenaan jabatan Jabatan
Calon Pejabat Kasubag A1
A2
A3
A4
Keuangan
100
90
90
100
Rumah Tangga
70
65
85
90
Pelayanan Masyarakat
80
70
70
90
Kerja Sama
75
65
80
95
Tentukan posisi jabatan masing-masing agar biaya pengelolaan pekerjaan minimal. Adakah posisi lain yang sama-sama menguntungkan?.
3.
Untuk melayani transportasi Anak Sekolah/Pegawai Kantor, sebuah perusahaan kereta api listrik akan membeli empat buah lokomotif yang akan ditempatkan pada tiga tempat yang menyebar dalam kota itu, yaitu tempat I, II, dan III, masing-masing sebuah lokomotif kecuali tempat III sebanyak dua buah lokomotif. Lokomotif-lokomotif itu akan melayani perjalanan dari kota asal menuju tempat tujuan di pagi hari, dan pulang di siang hari. Jarak antara tempat asal dan tempat tujuan terlihat pada Tabel 2 berikut:
116 Tabel 2. Jarak antara tempat asal dengan tempat tujuan.
Tempat Asal
Tempat tujuan A
B
C
D
I
13
35
42
9
II
6
61
18
30
III
15
10
5
9
Tentukan jaringan rel kereta api, agar total panjang rel minimum. 4.
Suatu perusahaan memerlukan 5 orang untuk 5 pekerjaan, sebut saja pekerjaan P, pekerjaan Q, pekerjaan R, pekerjaan S, dan pekerjaan T. Untuk memenuhi pekerjaan itu, perusahaan membuka lowongan kerja, dan ternyata yang melamar ada 7 orang, kemudian diberi kode: A1, A2, ..., A7. Prediksi pendapatan tiap bulan yang diperoleh apabila pekerjaan diserahkan kepada pelamar adalah seperti Tabel 2 berikut: Tabel 2. Prediksi pendapatan dari Pekerjaan Pekerjaan
Kode Pelamar A1
A2
A3
A4
A5
A6
A7
P
100
120
85
100
90
130
90
Q
70
110
70
80
100
120
90
R
95
110
90
90
60
140
100
S
90
115
80
100
80
150
80
T
70
100
80
75
100
120
75
Para pelamar disuruh mengajukan gaji yang diminta setiap bulannya. Hasil permintaan gaji pelamar adalah seperti Tabel 3 berikut: Tabel 3. Data permintaan gaji pelamar Pekerjaan
Gaji
Kode Pelamar A1
A2
A3
A4
A5
A6
A7
50
60
50
45
45
60
35
Tentukan 5 calon yang harus diterima agar keuntungan perusahaan maksimum.
BAB IV Penugasan dan Transshipment 1. Penugasan Masalah penugasan bermula dari penempatan para pekerja pada bidang yang tersedia agar biaya yang ditanggung pemberi tugas/perusahaan dapat diminimalkan. Jika dalam hal ini, pekerja dianggap sebagai sumber dan pekerjaan dianggap sebagai tujuan, sehingga masalah penugasan akan sama dengan masalah transportasi, dimana banyaknya sumber dan banyaknya tujuan adalah sama, setiap sumber hanya menghasilkan satu demikian pula setiap tujuan hanya memerlukan satu. a. Menyelesaikan Masalah Penugasan dengan Algoritma Hungaria Untuk lebih mudah memahami, marilah kita perhatikan contoh masalah berikut: Sebuah perusahaan yang berada di tiga kota yaitu Banjarmasin, Solo, dan Denpasar memerlukan tenaga ahli untuk menyelesaikan pekerjaan tertentu. Ketiga ahli itu berada di Jakarta, Surabaya, dan Ujung Pandang. Biaya ketiga orang ahli tersebut adalah seperti Tabel 2.6.a. Tabel 2.6.a.
Asal Ahli
Tujuan Banjarmasin
Solo
Denpasar
Jakarta
30
36
40
Surabaya
20
25
29
Ujung Pandang
27
24
22
Untuk menyelesaikan masalah ini akan digunakan sebuah metode yang disebut dengan Metode Hongaria, Langkah-langkah menyelesaikan masalah penugasan dengan algoritma Hungaria adalah sebagai berikut:
108
109 Cara menentukan total biaya minimum adalah dengan mengurangkan setiap baris dengan bilangan terkecil dari baris itu sendiri, sehingga kita peroleh tabel berikut:
0
6
10
0
5
9
5
2
0
Selanjutnya dikurangi dengan bilangan terkecil menurut kolom-kolomnya, sehingga diperoleh tabel berikut: 0
4
10
0
3
9
5
0
0
Selanjutnya dibuat garis sesedikit mungkin menurut baris atau kolom sehingga menutup semua bilangan nol (0). Bilamana jumlah garis masih lebih kecil dari banyaknya baris atau kolom, maka belum dapat disusun tabel optimalnya. Dalam hal diatas diperlukan dua garis, sehingga harus dilakukan langkah berikutnya yaitu: Mengurangi semua bilangan yang tidak tertutup garis dengan bilangan terkecil, dan menambahkan bilangan tersebut kepada persilangan garis penutup. Pada masalah diatas, diperoleh tabel berikut: 0
1
7
0
0
6
8
0
0
Dari tabel di atas, bagaimanapun caranya mencoret bilangan nol, paling sedikit diperlukan tiga buah garis. Langkah selanjutnya memilih sel nol untuk setiap baris atau kolom. Caranya ialah ada dua yaitu menurut baris atau menurut kolom. Pilih sel yang baris/kolom yang bilangan nolnya hanya satu (paling sedikit) Buang baris dan kolom pada sel yang terpilih. Lakukan terus sampai selesai.
110 Dari tabel diatas misalnya kita lakukan pada baris, maka sel pada baris 1 kolom 1 adalah set pertama yang dipilih, jadi baris 1 dan kolom 1 dibuang (diabaikan)
0
*
1
0
0
8
7 *
6
0
0
*
Setelah kita lakukan proses diatas, maka sel yang terpilih adalah sel (1,1), (2,2), dan (3,3). Sehingga total biaya minimal yang diperlukan adalah 30 + 25 + 22 = 77. Dimana Banjarmasin mendatangkan ahli dari Jakarta, Solo mendatangkan ahli dari Surabaya, dan Denpasar mendatangkan ahli dari Ujung Pandang.
Masalah penugasan ini juga dapat digunakan untuk masalah maksimum, yaitu dengan mengubah sedikit masalah maksimum ke minimum. Untuk lebih mudahnya kita ambil contoh berikut: Sebuah Perusahaan akan memberi tugas kepada tiga orang ( A, B, C) untuk menduduki jabatan tertentu (X,Y, Z). Keuntungan dari ketiga orang pada ketiga jabatan tersebut sebagai berikut: Jabatan
Pekerja
X
Y
Z
A
20
26
30
B
10
15
19
C
17
14
12
Langkah pertama adalah membuat tabel regrete, yaitu tabel karena tidak mengambil tindakan terbaik. Cara membuat adalah dengan mengurangkan setiap sel dengan bilangan terbesar tiap barisnya. Langkah ini menghasilkan tabel berikut: 10
4
0
9
4
0
0
3
5
111
Selanjutnya kita lakukan langkah-langkah seperti pekerjaan minimum, sehingga kita peroleh tabel berikut: 6
0
0
4
0
0
0
3
9
Penugasan optimal dicapai pada 6
0
4
0
0
*
0 *
3
Pekerja A pada jabatan Z, Pekerja B pada jabatan Y, Pekerja C pada jabatan X, dengan keuntungan = 30 + 15 + 17 = 62
*
0 9
Atau 6
0
4
0
0
3
9
0
*
*
Pekerja A pada jabatan Y, Pekerja B pada jabatan Z, Pekerja C pada jabatan X, dengan keuntungan = 26 + 19 + 17 = 62
0 *
Tabel Pekerja dan Jabatan Jabatan
Pekerja
X
Y
Z
A
20
26
30
B
10
15
19
C
17
14
12
b. Menyelesaikan Masalah Penugasan dengan Program Komputer i.
Program Lindo untuk Menyelesaikan Masalah Penugasan
Dengan komputer (program Lindo) juga dapat digunakan untuk menyelesaikan masalah penugasan ini yaitu seperti permasalahan pada transportasi. Program perhitungan dipersilahkan kepada pembaca sebagai latihan.
112 MAX
20 AX + 26 AY + 30 AZ + 10 BX + 15 BY + 19 BZ + 17 CX + 14 CY + 12 CZ SUBJECT TO 2) AX + AY + AZ = 1 3) BX + BY + BZ = 1 4) CX + CY + CZ = 1 5) AX + BX + CX = 1 6) AY + BY + CY = 1 7) AZ + BZ + CZ = 1 END
Hasil perhitungan dengan Lindo diperoleh sebaga berikut:
LP OPTIMUM FOUND AT STEP
7
OBJECTIVE FUNCTION VALUE 1) VARIABLE AX AY AZ BX BY BZ CX CY CZ ROW 2) 3) 4) 5) 6) 7)
62.00000 VALUE 0.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 0.000000
REDUCED COST 9.000000 0.000000 0.000000 8.000000 0.000000 0.000000 0.000000 0.000000 6.000000
SLACK OR SURPLUS 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
LP OPTIMUM FOUND AT STEP
DUAL PRICES 0.000000 -11.000000 -12.000000 29.000000 26.000000 30.000000 3
OBJECTIVE FUNCTION VALUE 1) VARIABLE BX BY BZ CX CY CZ AX AY AZ
62.00000 VALUE 0.000000 0.000000 1.000000 1.000000 0.000000 0.000000 0.000000 1.000000 0.000000
REDUCED COST 0.000000 0.000000 0.000000 0.000000 8.000000 14.000000 1.000000 0.000000 0.000000
113
ROW 2) 3) 4) 5) 6) 7)
SLACK OR SURPLUS 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
NO. ITERATIONS=
DUAL PRICES 0.000000 5.000000 9.000000 21.000000 10.000000 17.000000
3
ii. Program Solver untuk Menyelesaikan Masalah Penugasan Diselesaikan dengan Solver, maka kita buat tabel dan hasilnya sebagai berikut. Seperti pada penyelesaian masalah transportasi, masalah Penugasan dikerjakan dengan memulai mengisi nilai awal = 0. sehingga tabel awalnya sebagai berikut
Setelah solver dijalankan dengan mengisi / memilih seperti gambar berikut.
114 Selanjutnya dengan memilih Solve, maka akan diperoleh hasil seperti berikut.
Dari hasil ini dapat disimpulkan bahwa Pendapatan optimun terjadi apabila A ditempatkan pada jabatan Z, B pada jabatan Y dan C pada jabatan X. Dengan pendapatan sebesar 62. Soal-soal 1.
Suatu perusahaan memerukan 4 orang untuk 4 pekerjaan, sebut saja pekerjaan P, Q, R, dan S. Pekerjaan-pekerjaan itu akan diisi oleh 4 calon, yaitu: A1, A2, A3, dan A4. Prediksi pendapatan tiap bulan yang diperoleh apabila pekerjaan diserahkan kepada pekerja tersebut adalah seperti Tabel 3 berikut: Tabel 3. Prediksi pendapatan dari Pekerjaan Pekerjaan
Kode Pelamar A1
A2
A3
A4
P
100
120
85
100
Q
70
110
70
80
R
95
110
90
90
S
90
115
80
100
115 Gaji yang diminta tiap bulan dari pekerja tersebut adalah seperti Tabel 4 berikut: Tabel 4. Data permintaan gaji pelamar Pekerjaan
Gaji
Kode Pelamar A1
A2
A3
A4
50
60
50
45
Berikan penyelesaian tentang posisi pekerjaan para pekerja tersebut agar pendapatan perusahaan maksimum.
2.
Sebuah Kantor akan mengangkat empat Kepala SubBagian (Kasubag) dari empat orang, yaitu Keuangan, Rumah Tangga, Pelayanan Masyarakat, dan Kerja Sama. Keempat calon adalah A1, A1, A3, dan A4. Dari keempat orang tersebut mengajukan anggaran seperti terlihat pada Tabel 4 berikut: Tabel 4. Usulan dana berkenaan jabatan Jabatan
Calon Pejabat Kasubag A1
A2
A3
A4
Keuangan
100
90
90
100
Rumah Tangga
70
65
85
90
Pelayanan Masyarakat
80
70
70
90
Kerja Sama
75
65
80
95
Tentukan posisi jabatan masing-masing agar biaya pengelolaan pekerjaan minimal. Adakah posisi lain yang sama-sama menguntungkan?.
3.
Untuk melayani transportasi Anak Sekolah/Pegawai Kantor, sebuah perusahaan kereta api listrik akan membeli empat buah lokomotif yang akan ditempatkan pada tiga tempat yang menyebar dalam kota itu, yaitu tempat I, II, dan III, masing-masing sebuah lokomotif kecuali tempat III sebanyak dua buah lokomotif. Lokomotif-lokomotif itu akan melayani perjalanan dari kota asal menuju tempat tujuan di pagi hari, dan pulang di siang hari. Jarak antara tempat asal dan tempat tujuan terlihat pada Tabel 2 berikut:
116 Tabel 2. Jarak antara tempat asal dengan tempat tujuan.
Tempat Asal
Tempat tujuan A
B
C
D
I
13
35
42
9
II
6
61
18
30
III
15
10
5
9
Tentukan jaringan rel kereta api, agar total panjang rel minimum. 4.
Suatu perusahaan memerlukan 5 orang untuk 5 pekerjaan, sebut saja pekerjaan P, pekerjaan Q, pekerjaan R, pekerjaan S, dan pekerjaan T. Untuk memenuhi pekerjaan itu, perusahaan membuka lowongan kerja, dan ternyata yang melamar ada 7 orang, kemudian diberi kode: A1, A2, ..., A7. Prediksi pendapatan tiap bulan yang diperoleh apabila pekerjaan diserahkan kepada pelamar adalah seperti Tabel 2 berikut: Tabel 2. Prediksi pendapatan dari Pekerjaan Pekerjaan
Kode Pelamar A1
A2
A3
A4
A5
A6
A7
P
100
120
85
100
90
130
90
Q
70
110
70
80
100
120
90
R
95
110
90
90
60
140
100
S
90
115
80
100
80
150
80
T
70
100
80
75
100
120
75
Para pelamar disuruh mengajukan gaji yang diminta setiap bulannya. Hasil permintaan gaji pelamar adalah seperti Tabel 3 berikut: Tabel 3. Data permintaan gaji pelamar Pekerjaan
Gaji
Kode Pelamar A1
A2
A3
A4
A5
A6
A7
50
60
50
45
45
60
35
Tentukan 5 calon yang harus diterima agar keuntungan perusahaan maksimum.
117
2. Transshipment Transshipment adalah masalah transportasi tetapi untuk mengirim barang dari tempat produksi ke tempat permintaan tidak dapat dilakukan secara langsung. Barang yang diangkut harus mengalami dua atau lebih cara pengangkutan. Misalnya Seorang petani tidak dapat memperoleh pupuk dari Pabrik langsung, tetapi harus melalui agen daerah, bahkan agen daerah harus memalui agen pusat baru dari Pabrik. Jadi proses penangkutan barang dari tempat produksi ke tempat permintaan harus melalui semacam agen terlebih dahulu. Sebagai contoh perhatikan masalah transshipment berikut.
Sebuah Perusahaan Alat Berat “Arifin” memiliki 14 alat berat yang berada di Jakarta sebanyak 6 buah dan di Surabaya 8 buah. Alat berat tersebut akan dipakai di 6 kota, yaitu Tasikmalaya 2 buah, Cirebon 1 buah, Jogja 4 buah, Solo 4 buah, Madiun 3 buah, dan Jember 2 buah. Karena kondisi jalan, pengangkutan tidak dapat langsung dari kota asal ke kota tujuan dan harus melalui kota Transit yaitu Kota Bandung, Kota Semarang, dan Kota Malang. Alur pengiriman barang dan Biaya pengangkutan sebuah alat berat terlihat pada Gambar 1 dan tabel berikut.
Tabel Biaya Satuan Pengangkutan dari Kota Asal ke Kota Transit BDG
SMG
MALANG
JKT
10
15
25
SBY
20
15
10
Tabel Biaya Satuan Pengangkutan Kota Transit ke Tempat Tujuan TASIK BDG SMG MALANG
10
CRB
JOGJA
SOLO
MADIUN JEMBER
15 15
10
10
20
15
10
10
118
Gambar 1. Alur Pengiriman Barang, Perasediaan Barang, Kebutuhan Barang, dan Biaya Satuan Pengangkutan Masalah. Tentukan sistem Transshipment agar biaya pengiriman barang minimum.
Penyelesaian. Untuk menyelesaikan masalah transshipment ini, pada setiap kota transit harus dibuat atau disediakan barang (alat) dummy yang besarnya sama dengan jumlah semua kapasitas produk atau persediaan barang. Tabel Transportasi dibuat dengan menggabung kedua tabel tersebut dan memberikan biaya yang cukup besar (M) kepada semua yang tidak mempunyai jalur transportasi, sehingga pada masalah diatas diperoleh tabel transportasi sebagai berikut.
119 Tabel Transportasi Gabungan BDG
SMG MALANG TASIK CRB JOGJA SOLO MADIUN JEMBER Kapasitas
JKT
10
15
25
M
M
M
M
M
M
6
SBY
20
15
10
M
M
M
M
M
M
8
BDG
0
M
M
10
15
M
M
M
M
14
SMG
M
0
M
M
15
10
10
M
M
14
MALANG
M
M
0
M
M
20
15
10
10
14
14
14
14
2
1
3
4
2
2
14
Permintaan
Dari tabel ini, maka sistem transportasi dapat dicari, dan akhirnya sistem transshipment dapat ditentukan. i. Program Lingo untuk Menyelesaikan Masalah Transshipment Masalah transshipmen ini apabila diselesaikan dengan Lingo, maka kita memberikan nilai M yang cukup besar, misalnya 1000, maka program Lingo untuk masalah ini adalah sebagai berikut. Model: Sets: Kapasitas/JKT, SBY, BDG, SMG, MLG/:Asal; Permintaan/BDG1, SMG1, MLG1, TASIK, CRB, JOGJA, SOLO, MADIUN, JEMBER/:Demand; Links(Kapasitas,Permintaan):Ship, Cost; Endsets Min=@sum(Links:Ship*Cost); @for(Permintaan(j):@sum(Kapasitas(i):Ship(i,j))>Demand(j)); @for(Kapasitas(i):@sum(Permintaan(j):Ship(i,j))
1000, 1000, 1000, 10, 15,
1000, 1000, 1000, 1000, 10,
1000, 1000, 1000, 1000, 10;
Enddata End
Setelah program kita jalankan dan kita ambil data yang diperlukan, maka akan kita peroleh.
120
Rows=
15 Vars=
Nonzeros=
45 No. integer vars=
149 Constraint nonz=
90(
0
90 are +- 1) Density=0.216
Smallest and largest elements in absolute value= No. < :
5 No. =:
Single cols=
0 No. > :
( all are linear)
1.00000
9, Obj=MIN, GUBs <=
1000.00
9
0
Optimal solution found at step: Objective value:
24 320.0000
Variable
Value
Reduced Cost
SHIP( JKT, BDG1)
3.000000
0.0000000E+00
SHIP( JKT, SMG1)
3.000000
0.0000000E+00
SHIP( JKT, MLG1)
0.0000000E+00
15.00000
SHIP( JKT, TASIK)
0.0000000E+00
980.0000
SHIP( JKT, CRB)
0.0000000E+00
975.0000
SHIP( JKT, JOGJA)
0.0000000E+00
975.0000
SHIP( JKT, SOLO)
0.0000000E+00
975.0000
SHIP( JKT, MADIUN)
0.0000000E+00
980.0000
SHIP( JKT, JEMBER)
0.0000000E+00
980.0000
SHIP( SBY, BDG1)
0.0000000E+00
10.00000
SHIP( SBY, SMG1) SHIP( SBY, MLG1)
4.000000
0.0000000E+00
4.000000
0.0000000E+00
SHIP( SBY, TASIK)
0.0000000E+00
980.0000
SHIP( SBY, CRB)
0.0000000E+00
975.0000
SHIP( SBY, JOGJA)
0.0000000E+00
975.0000
SHIP( SBY, SOLO)
0.0000000E+00
975.0000
SHIP( SBY, MADIUN)
0.0000000E+00
980.0000
SHIP( SBY, JEMBER)
0.0000000E+00
980.0000
SHIP( BDG, BDG1)
11.00000
0.0000000E+00
SHIP( BDG, SMG1)
0.0000000E+00
995.0000
SHIP( BDG, MLG1)
0.0000000E+00
1000.000
SHIP( BDG, TASIK) SHIP( BDG, CRB)
2.000000
0.0000000E+00
1.000000
0.0000000E+00
SHIP( BDG, JOGJA)
0.0000000E+00
985.0000
SHIP( BDG, SOLO)
0.0000000E+00
985.0000
SHIP( BDG, MADIUN)
0.0000000E+00
990.0000
SHIP( BDG, JEMBER)
0.0000000E+00
990.0000
SHIP( SMG, BDG1)
0.0000000E+00
1005.000
SHIP( SMG, SMG1) SHIP( SMG, MLG1)
7.000000 0.0000000E+00
0.0000000E+00 1005.000
121 SHIP( SMG, TASIK)
0.0000000E+00
SHIP( SMG, CRB)
0.0000000E+00
995.0000 5.000000
SHIP( SMG, JOGJA)
3.000000
0.0000000E+00
SHIP( SMG, SOLO)
4.000000
0.0000000E+00
SHIP( SMG, MADIUN)
0.0000000E+00
995.0000
SHIP( SMG, JEMBER)
0.0000000E+00
995.0000
SHIP( MLG, BDG1)
0.0000000E+00
1000.000
SHIP( MLG, SMG1)
0.0000000E+00
995.0000
SHIP( MLG, MLG1)
10.00000
0.0000000E+00
SHIP( MLG, TASIK)
0.0000000E+00
990.0000
SHIP( MLG, CRB)
0.0000000E+00
985.0000
SHIP( MLG, JOGJA)
0.0000000E+00
SHIP( MLG, SOLO)
0.0000000E+00
5.000000 0.0000000E+00
SHIP( MLG, MADIUN)
2.000000
0.0000000E+00
SHIP( MLG, JEMBER)
2.000000
0.0000000E+00
Hasil ini apabila kita pindah kedalam tabel, maka akan kita peroleh tabel berikut. Biaya Trashipment 320.
JKT SBY
BDG
SMG
3
3 4
MLNG
TSIK
CRB JGJA SOLO MDIUN
JBER
Kapasitas 6
4
BDG
8 3
1
SMG
3
4
MALANG Permintaan
2
1
3
4
2
2
2
2
14
Dari tabel ini, dapat disimpulkan bahwa, Dari Jakarta terdapat 6 buah alat berat, 3 buah dikirim ke Bandung, dan 3 buah ke Semarang. Dari Surabaya terdapat 8 buat alat berat, 4 buah dikirim ke Semarang, dan 4 buah dikirim ke Malang. Kota Bandung mendapat kiriman dari Jakarta 3 buah alat berat, dikirim ke Tasikmalaya 2 buah dan dikirim ke Cirebon 1 buah.
122 Kota Semarang mendapat kiriman dari Jakarta 3 buah dan dari Surabaya 4 buah alat berat, dikirim ke Jogja 3 buah dan dikirim ke Solo 4 buah. Kota Malang mendapat kiriman dari Surabaya 4 buah alat berat, dikirim ke Madiun 2 buah dan dikirim ke Jember 2 buah.
ii. Program Solver untuk Menyelesaikan Masalah Transshipment Masalah Transshipment ini apabila dikerjakan dengan Solver, maka kita buat tabel awal sebagai berikut.
Setelah Solver dijalankan dengan mengisi menu solver (Solver Parameter) berikut.
123
Maka akan kita peroleh hasil sebagai berikut.
124 Dari hasil ini, maka kesimpulan dapat diambil sama seperti kesimpulan pada penyelesaian dengan Lingo di atas.
Soal-soal 1. Dua pabrik batu bara terletak di Pontianak dan Balikpapan masing-masing dapat menghasilkan 300 ton setiap bulannya. Sementara Perusahaan yang memerlukan batu bara berada di pulau Jawa, yaitu di 10 kota: Banten, Jakarta, Cirebon, Tegal, Pekalongan, Semarang, Kudus, Surabaya, Malang, dan Banyuwangi. Dari kota-kota tersebut berturut-turut memerlukan bata-bara (dalam ton): 50, 100, 50, 75, 60, 40,40, 50, 30, dan 30. Pengangkutan batu bara dilakukan dengan dua tahap, yaitu dari Pontianak dan Balikpapan ke pelabuhan di Jakarta, Semarang, dan Surabaya menggunakan kapal, Sedangkan dari Pelabuhan ke kota-kota tujuan menggunakan Truk. Biaya Pengangkutan tiap ton batu bara terlihat pada tabel berikut. Biaya Pengiriman batu bara Dengan Kapal Jakarta Semarang Surabaya Pontianak
50
60
70
Balikpapan
80
70
60
Dengan Truk Banten Jakarta
20
Semarang
Jakarta Cirebon Tegal Pklongan Smrang 5
25
30
25
20
Surabaya
15
Kdus
Srbaya
5
10
20
20
15
5
Mlang Bnywngi
15
20
Buatlah sistem transshipment agan biaya pengiriman batu bara minimum.
2. Bagaimana sistem transshipment pada soal no 1 ini bilamana kebutuhan batu bara di Tegal, Surabara, dan Banyuwangi masing-masing naik 25 ton sebulan, sementara kebutuhan di Jakarta turun 25 ton sebulannya.
125 3. Bagaimana sistem transshipment pada contoh soal di atas (tentang alat berat) bilamana jumlah alat berat di Jakarta ada 10 buah, dan di surabaya ada 6 buah.
BAB V Analisis Jaringan Jaringan lahir karena berbagai keperluan seperti: transportasi, listrik, komunikasi, perencanaan proyek, aliran air, pembuatan jalan, dan lain-lain. Saat ini jaringan sangat penting, sebab dengan jaringan maka masalah yang besar dan rumit dapat disederhanakan. Ada beberapa jaringan yang dapat diselesaikan dengan permasalahan program linear. Pada kajian di sini akan dibahas empat masalah jaringan, yaitu: permasalahan lintasan terpendek, masalah diagram pohon terpendek, masalah aliran maksimum, dan penyelesaian proyek dengan Program Evaluation and Review Technique (PERT), dan Critical-Path Method (CPM).
Beberapa Istilah yang dipakai dalam Analisis Jaringan Jaringan didefinisikan sebagai gabungan dua himpunan yaitu himpunan node dan himpunan arc. Himpunan node dilambangkan dengan V dan himpunan arc dilambangkan dengan A. Arc terdiri dari pasangan terurut dari node dan menggambarkan arah gerakan yang mungkin. Untuk tujuan ini, misalkan jaringan memuat arc(j, k), maka arah gerakan yang mungkin adalah dari node j ke node k. V = {1, 2, 3, 4, 5} himpunan node
Perhatikan jaringan berikut.
A = {(1, 5), (5, 4), (4, 3), (3, 2), (2, 1), (3, 1), (2, 3), (4, 5) } himpunan arc. Misalkan
arc(j,
k)
berada
di
jaringan, maka j disebut node awal atau node pangkal, dan k disebut node akhir atau node ujung. Gambar contoh sebuah Jaringan 125
126
Rangkaian arc sedemikian hingga untuk setiap arc mempunyai tepat satu node persekutuan bersama dengan arc sebelumnya disebut chain (rantai).
Lintasan adalah rantai yang memenuhi pernyaratan bahwa untuk setiap node akhir suatu arc adalah node awal dari arc sebelumnya. Pada contoh jaringan di atas, (3, 1) – (1, 5) – (4, 5) adalah rantai tetapi bukan lintasan, sedangkan (3, 1) – (1, 5) – (5, 4) adalah lintasan. Lintasan ini menggambarkan perjalanan (gerak) dari node 3 ke node 4.
Selanjutnya kita perhatikan contoh permasalahan berikut.
7
Gambar 3.1 Jarak antar tempat peristirahatan (dalam kilometer)
Sebuah lokasi sebut saja “Taman Sari” akan dijadikan sebagai taman wisata yang sejuk, nyaman, dan lingkungan yang terlindungi termasuk satwa di dalamnya. Pada node (bertanda huruf O, A, B, C, D, E, T) dibuat tempat peristirahatan. Jarak antar tempat peristirahatan seperti terlihat pada gambar di atas (dalam kilometer) lihat gambar 3.1. Untuk melindungi satwa dan kesejukan Taman Sari tersebut semua mobil pribadi, termasuk angkutan umum dilarang masuk. Sistem transportasi yang akan dibuat adalah kereta listrik, banyaknya kereta yang lewat setiap jalur dibatasi. Banyaknya kereta yang lewat maksimum setiap harinya terlihat pada Gambar 3.2, Ini diperlukan untuk menjaga ketenangan taman. Pintu masuk adalah node O, dan pintu keluarnya node T. Kembalinya kereta dari T ke O melalui jalur luar taman. Selanjutnya untuk kebutuhan air, akan dibuat jaringan pipa air dari O ke masing-masing tempat peristirahatan.
127
Gambar 3.2 Maksimum banyaknya kereta yang boleh lewat setiap harinya Permasalahan yang muncul ada tiga yaitu: 1. Lewat jalur mana dari O menuju ke T sehingga diperoleh jarak terpendek, berapa jaraknya. 2. Buatlah jaringan air yang menghubungkan semua tempat peristirahatan agar panjang pipa yang digunakan minimum. 3. Buatlah jalur kereta, agar banyaknya lintasan maksimum. Masalah yang pertama disebut sebagai masalah lintasan terpendek, masalah kedua disebut masalah diagram pohon terpendek, dan masalah ke tiga disebut masalah aliran maksimum. 1. Masalah Lintasan Terpendek Masalah lintasan terpendek adalah masalah yang menyangkut node, panjang jalur, arah lintasan. Dalam lintasan ini perlu diperhatikan khusus yaitu node supply (node awal) dan node demand (node akhir). Dalam hal masalah di atas, node supply adalah node O, dan node demand adalah node T. Untuk menyelesaikan masalah lintasan terpendek ada algoritma yang bisa dipakai yaitu: Algoritma masalah lintasan terpendek a. Tujuan pada iterasi ke-n: Tentukan node terdekat dari titik awal (node awal). b. Input pada iterasi ke-n: node terdekat ke n-1 ke node awal, termasuk di dalamnya lintasan terpendek dan jarak dari node awal. (node-node ini ditambah dengan node awal disebut node terselesaikan, yang lain node belum terselesaikan).
128
c. Kandidat untuk node terdekat ke-n: Setiap node terselesaikan yang langsung berhubungan dengan satu atau lebih node belum terselesaikan sebagai kandidatnode belum terselesaikan yang mempunyai hubungan terpendek. d. Perhitungan node terdekat ke-n: Untuk setiap node terselesaikan dan node kandidat, ditambah dengan jarak diantaranya. Kandidat yang mempunyai total jarak terpendek ke-n.
Untuk masalah lintasan terpendek pada Taman Sari di atas adalah sebagai berikut:
Node awal adalah node O dan node akhir adalah node T. Perhitungan lintasan dapat dilihat pada Tabel 3.3 berikut: Tabel 3.3 Penerapan Algoritma lintasan terpendek pada Taman sari
n
1 2,3 4
5 6
Node terselesaikan Tersambung langsung dengan Node belum terselesaikan O O A A B C A B E D E
Sambungan terpendek node belum terselesaikan A C B D E E D D D T T
Total jarak
2 4 2+2=4 2+7=9 4+3=7 4+4=8 2+7=9 4+4=8 7+1=8 8 + 5 = 13 7 + 7 = 14
Node terde - kat ke-n
Jarak Minimum
Sambungan terakhir
A C B
2 4 4
OA OC AB
E
7
BE
D D T
8
BD ED DT
13
129
Jarak minimum dari node O ke node T adalah 13 kilometer dengan jalur •
O → A → B → E → D → T atau
•
O→A→B→D→T
Masalah jaringan terpendek di atas dapat kita pandang sebagai masalah transshipment yaitu dengan mengisikan bilangan besar M pada jalur yang tidak ada, oleh karena itu tabel transportasi dari masalah jaringan ini adalah sebagai berikut. Tabel Jarak antar tempat A
B
C
D
E
T
O
2
5
4
M
M
M
A
0
2
M
7
M
M
B
M
0
1
4
3
M
C
M
M
0
M
4
M
D
M
M
M
0
1
5
E
M
M
M
1
0
7
Apabila kita kerjakan dengan Solver, yaitu dengan menggantikan M menjadi 1000 dan masing-masing kapasitas 1 serta permintaan 1, maka akan diperoleh hasil berikut. Tabel Hasil perhitungan dengan Solver A
B
C
D
E
T
O
1
0
0
0
0
0
1
A
0
1
0
0
0
0
1
B
0
0
0
1
0
0
1
C
0
0
1
0
0
0
1
D
0
0
0
0
0
1
1
E
0
0
0
0
1
0
1
1
1
1
1
1
1
Total
13
130
Dari tabel hasil di atas, diperoleh bahwa total jarak adalah 13 dengan lintasan O – A – B – D – T.
Catatan. Dengan Solver, lintasan yang diperoleh hanya tunggal (1 macam). Contoh 2. Sebuah Toko Bangunan akan menggunakan mobil Pickup untuk melayani pengiriman bahan bangunan kepada pembeli. Harga mobil Pickup baru Rp 60 juta. Mobil tersebut setelah dipakai semakin lama semakin turun harganya, sedangkan biaya perwatannya semakin lama semakin besar. Besarnya biaya perawatan dan harga jual mobil terlihat pada tabel berikut. Tabel Biaya perawatan dan Harga Jual Kembali Mobil Pickup Umur
Biaya
Harga Jual
Mobil (Th)
Perawatan (Jt)
(Trade In /Jt)
0
2
1
5
45
2
9
35
3
13
30
4
18
25
5
22
20
6
25
15
7
28
10
Dengan asumsi harga mobil Pickup baru tetap, pada tahun ke-berapa mobil harus diganti agar biaya total yang dikeluarkan minimum?
Penyelesaian Pada masalah jaringan ini, kita akan melibatkan delapan node V= {1, 2, 3, 4, 5, 6, 7, 8}. Node i menggambarkan awal tahun ke-i. Untuk setiap i < j, arc(i, j) menggambarkan pembelian mobil baru pada awal tahun ke-i dan tetap memakainya sampai awal tahun ke-j.
131
Panjang arc (i, j) atau cij adalah total pengeluaran biaya penggunaan mobil dari awal tahun ke-i sampai awal tahun ke-j jika mobil dibeli pada awal tahun ke-i dan mobil akan ditukar mobil baru lagi pada awal tahun ke-j. Jadi Cij = biaya perawatan tahun ke-i, i+1, ..., j-1 + biaya pembelian mobil baru pada awal tahun ke-i - harga jual mobil pada awal tahun ke-j.
Dengan menerapkan bentuk ini pada masalah di atas, maka diperoleh. C12 = 2 + 60 – 45 = 17 C13 = 2 + 5 + 60 – 35 = 32 C14 = 2 + 5 + 9 + 60 – 30 = 46 C15 = 2 + 5 + 9 + 13 + 60 – 25 = 64 C16 = 2 + 5 + 9 + 13 + 18 + 60 – 20 = 87 C17 = 2 + 5 + 9 + 13 + 18 + 22 + 60 – 15 = 114 C18 = 2 + 5 + 9 + 13 + 18 + 22 + 25 + 60 – 10 = 144 C23 = 2 + 60 – 45 = 17 C24 = 2 + 5 + 60 – 35 = 32 C25 = 2 + 5 + 9 + 60 – 30 = 46 C26 = 2 + 5 + 9 + 13 + 60 – 25 = 64 C27 = 2 + 5 + 9 + 13 + 18 + 60 – 20 = 87 C28 = 2 + 5 + 9 + 13 + 18 + 22 + 60 – 15 = 114 C34 = 2 + 60 – 45 = 17 C35 = 2 + 5 + 60 – 35 = 32 C36 = 2 + 5 + 9 + 60 – 30 = 46 C37 = 2 + 5 + 9 + 13 + 60 – 25 = 64 C38 = 2 + 5 + 9 + 13 + 18 + 60 – 20 = 87 Dst
132
Dari data masalah Jaringan ini dapat dibuat tabel sebagai berikut. Tabel Total Pengeluaran penggunaan Mobil Pickup Awal tahun ke
2
3
4
5
6
7
8
1
17
32
46
64
86
114
144
2
0
17
32
46
64
86
114
0
17
32
46
64
86
0
17
32
46
64
0
17
32
46
0
17
32
0
17
3 4 5 6 7
Dengan melengkapi tabel, yaitu memberi nilai besar pada sel kosong dan menggunakan Solver akan diperoleh hasil 2
3
4
5
6
7
8
1
0
0
1
0
0
0
0
1
2
1
0
0
0
0
0
0
1
3
0
1
0
0
0
0
0
1
4
0
0
0
0
0
1
0
1
5
0
0
0
1
0
0
0
1
6
0
0
0
0
1
0
0
1
7
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
Total
109
133
Atau hasil 2
3
4
5
6
7
8
1
1
0
0
0
0
0
0
1
2
0
0
0
1
0
0
0
1
3
0
1
0
0
0
0
0
1
4
0
0
1
0
0
0
0
1
5
0
0
0
0
0
0
1
1
6
0
0
0
0
1
0
0
1
7
0
0
0
0
0
1
0
1
1
1
1
1
1
1
1
Total
109
Hasil pertama: 1 – 4 – 7 – 8 Hasil kedua : 1 – 2 – 5 – 7 Dengan mengambil waktu yang cukup, maka akan diperoleh bahwa periode terbaik untuk ganti mobil baru adalah 3 tahunan.
2. Masalah Diagram Pohon Terpendek Kembali pada masalah induk di atas, yaitu pada masalah jaringan untuk menentukan jaringan pipa air terpendek. Masalah ini termasuk dalam masalah diagram pohon terpendek. Untuk menyelesaikan masalah ini digunakan algoritma untuk masalah diagram pohon terpendek sebagai berikut: a. Pilih sebarang node, dan hubungkan node tersebut dengan node berbeda yang terdekat. b. Kenali node taktersambung yaitu yang disambungkan dengan node terdekat, dan hubungkan kedua node tersebut. Ulangi sampai semua node tersambung. Untuk permasalahan jaringan pipa air tersebut kita perhatikan langkah-langkah berikut:
134
Misalkan kita memulai dengan node B, maka node terdekat adalah C, hubungkan BC, maka diperoleh diagram berikut:
Node terdekat dengan BC adalah A, kemudian sambungkan titik A ke B, maka diperoleh diagram berikut:
135
Selanjutnya berturut-turut node O ke node A, node E ke node B, node D ke node E, dan node T ke node D, sehingga diperoleh jaringan lengkap sebagai berikut:
Jumlah panjang pipa air bersih yang diperlukan adalah 2 + 2 + 1 + 3 + 1 + 5 = 14 km.
3. Masalah Aliran Maksimum
Diagram kapasitas maksimum dari transportasi kereta dari node awal O ke node akhir T.
Untuk membahas aliran maksimum, ada beberapa terminology yang harus kita pahami terlebih dahulu.
136
Perhatikan arah dan sambungan jaringan. Arah jaringan dari node awal O dan node akhir T. Diberikan kapasitas lintasan dan kita bertujuan memaksimumkan total lintasan dari node O ke node T. Kita menggunakan algoritma yang disebut residual network dan augmenting path. Dari jaringan asli, residual network menunjukkan kapasitas sisa yaitu setelah adanya aliran. Sebagai contoh, kapasitas jalur dari O ke A adalah 5.
Bilamana ada aliran dari node O ke node A sebanyak 2, maka residual network adalah sebagai berikut:
Augmenting path adalah arah lintasan dari node awal ke node akhir pada residual network sedemikian hingga setiap jalur mempunyai kapasitas sisa positif.
Algoritma masalah aliran maksimum adalah sebagai berikut: a. Identifikasi (kenali) augmenting path yang mempunyai kapasitas sisa positif. b. Sebut kapasitas sisa c* dari augmenting path, yaitu minimum dari kapasitas setiap jalur (arc) yang dilalui. c. Kurangkan dengan c* pada setiap awal jalur kapasitas sisa, dan tambahkan c* pada arah yang berlawanan. Selanjutnya kembali ke langkah a.
Selanjutnya marilah kita bahas masalah aliran maksimum pada Taman Sari dengan algoritma ini:
Iterasi 1. Augmenting path O → A → D → T adalah min {5,3,9} = 3. Dengan lintasan ini maka diperoleh residual network
137
Iterasi 2. Augmenting path O → B → D → T adalah min {7,4,6} = 4. Dengan lintasan ini maka diperoleh residual network
4
Iterasi 3. Augmenting path O → C → E → T adalah min {4,4,6} = 4. Dengan lintasan ini maka diperoleh residual network
0
138
Iterasi 4. Augmenting path O → B → E → D → T adalah min {3,5,1,2} = 1. Dengan lintasan ini maka diperoleh residual network
Iterasi 5. Augmenting path O → B → E → T adalah min {2,4,2} = 2. Dengan lintasan ini maka diperoleh residual network
Dari gambar jaringan yang terakhir ini terlihat bahwa, sudah tidak ada augmenting path yang positif lagi, sehingga aliran telah mencapai optimal yaitu sebanyak 14 perjalanan dari node awal O ke node akhir T dengan lintasan: •
O → A → D → T sebanyak 3 buah;
•
O → B → D → T sebanyak 4 buah;
•
O → C → E → T sebanyak 4 buah;
•
O → B → E → D → T sebanyak 1 buah; dan
•
O → B → E → T sebanyak 2 buah.
Masalah aliran maksimum ini apabila diselesaikan dengan program Lingo, maka programnya sebagai berikut.
139
MODEL: SETS: NODES/O A B C D E T/; ARCS(NODES,NODES)/O,A O,B O,C A,B A,D B,C B,D B,E C,E D,T E,D E,T T,O/:CAP,FLOW; ENDSETS MAX=FLOW(T,O); @FOR(ARCS(I,J):FLOW(I,J)
Setelah dijalankan, maka akan diperoleh hasil sebagai berikut. Optimal solution found at step: Objective value: Variable CAP( O, A) CAP( O, B) CAP( O, C) CAP( A, B) CAP( A, D) CAP( B, C) CAP( B, D) CAP( B, E) CAP( C, E) CAP( D, T) CAP( E, D) CAP( E, T) CAP( T, O) FLOW( O, A) FLOW( O, B) FLOW( O, C) FLOW( A, B) FLOW( A, D) FLOW( B, C) FLOW( B, D) FLOW( B, E) FLOW( C, E) FLOW( D, T) FLOW( E, D) FLOW( E, T) FLOW( T, O)
3 14.00000 Value 5.000000 7.000000 4.000000 1.000000 3.000000 2.000000 4.000000 5.000000 4.000000 9.000000 1.000000 6.000000 1000.000 4.000000 7.000000 3.000000 1.000000 3.000000 1.000000 4.000000 3.000000 4.000000 8.000000 1.000000 6.000000 14.00000
Reduced Cost 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00 0.0000000E+00
Hasil di atas menunjukkan bahwa, total aliran maksimum adalah 14, dengan aliran OA sebesar 4, OB sebesar 7, dan seterusnya (lihat hasil FLOW(i ,j) di atas).
140
4. Menyelesaikan proyek dengan PERT dan CPM a. PERT dengan Waktu Tepat Keberhasilan pengelolaan proyek skala besar adalah kehati-hatian dalam perencanaan, penjadwalan, dan koordinasi antar kegiatan (aktivitas) yang terkait. Prosedur yang cukup terkenal adalah prosedur Program Evaluation and Review Technique (PERT) dan CriticalPath Method (CPM). Sistem PERT dirancang untuk membantu di dalam perencanaan dan kontrol, sehingga tidak dibuat secara langsung untuk mengoptimalkan. Namun demikian dapat digunakan untuk menentukan dead line suatu pekerjaan. Sistem PERT menggunakan jaringan proyek (project network) untuk melukiskan secara grafik hubungan antar unsur dalam suatu proyek.
Terminologi yang digunakan dalam PERT ini mirip dengan sistem jaringan sebelumnya, dimana garis/lintasan (arc) menggambarkan aktivitas, node menggambarkan peristiwa (event), dan anak panah menggambarkan arah jalannya aktivitas. Contoh: Dalam membuat sebuah rumah sederhana, ada beberapa kegiatan / aktivitas yang menyangkut pekerjaan pembuatan rumah. Pekerjaan ini ada yang menuntut secara urut ada pula yang dapat dilaksanakan secara bersamaan. Aktivitas-aktivitas itu terlihat pada Tabel 3.4 berikut: Tabel 3.4 Aktivitas Pembuatan Rumah No
Aktivitas
Lama (hari)
Prasyarat
1
Persiapan / perataan tanah
2
-
2
Fondasi
4
No 1.
3
Dinding kasar (pemasangan batu bata/batako)
10
No 2.
4
Pemasangan atap
6
No 3.
5
Pemasangan pipa ledeng bagian luar rumah
4
No 3.
6
Pemasangan pipa ledeng bagian dalam rumah
5
No 5.
7
Pemasangan Jaringan listrik
7
No 3.
8
Pemasangan dinding papan
8
No 6, dan No 7.
9
Pemasangan keramik lantai
4
No 8.
141
10
Pengecatan bagian dalam rumah
5
No 8.
11
Pemasangan papan bagian luar rumah
7
No 4.
12
Pengecatan bagian luar rumah
9
No 4, dan No 11.
13
Pengaturan Interior rumah
6
No 9, dan No 10.
14
Pengaturan eksterior rumah
2
No 12.
15 SELESAI Berapa lama pembuatan rumah tersebut, bilamana lama aktivitas-aktivitas tersebut di atas bersifat tepat (fix). Pada kajian ini perlu diperkenalkan lagi dua istilah yaitu waktu paling cepat dan waktu paling lambat. Waktu paling cepat adalah waktu (dari awal) paling cepat (earliest time) yang dibutuhkan untuk berakhirnya aktivitas dan atau akan dimulainya aktivitas selanjutnya. Waktu paling lambat adalah waktu (dari awal) paling lambat (latest time) yang dibutuhkan untuk berakhirnya aktivitas dan atau akan dimulainya aktivitas selanjutnya. Pada setiap node terdapat pasangan waktu, yaitu pasangan waktu paling cepat, dan waktu paling lambat. Untuk memudahkan dalam pembacaan diagram, Sebuah peristiwa (event) dilambangkan dengan huruf kapital (A, B, C, …), sebuah aktivitas dengan nomor aktivitas (No 1, No 2, …), lama aktivitas ditulis dalam tanda kurung sesudah aktivitas dalam bentuk bilangannya saja (1, 2, …). Pembuatan rumah sederhana tersebut diatas dapat digambarkan seperti Diagram berikut: Dari diagram di bawah, terlihat bahwa lama pembuatan rumah adalah 44 hari. Aktivitas kritis terjadi bilamana waktu paling cepat sama dengan waktu paling lambat, artinya adalah apabila sebuah aktivitas telah selesai, maka aktivitas selanjutnya harus segera dilaksanakan dan tidak boleh ditunda, sedangkan apabila waktu paling cepat tidak sama dengan waktu paling lambat, maka bilamana sebuah aktivitas selesai, maka aktivitas selanjutnya bisa ditunda sejauh perbedaan antara kedua waktu tersebut. Perbedaan waktu paling cepat dan waktu paling lambat disebut waktu slack. Sebuah aktivitas digambarkan dengan garis putus-putus artinya aktivitas dummy yaitu tidak ada aktivitas, namun perlu digambarkan karena akan menggambarkan prasyarat suatu aktivitas yang lain, sebagai contoh aktivitas No 13 dapat dilakukan setelah aktivitas no 9 dan aktivitas No 10. Demikian pula aktivitas No 12 dapat dilakukan setelah aktivitas No 5 dan aktivitas no 11 selesai.
142
Diagram pembuatan rumah sederhana.
b. PERT dengan pendekatan tiga-waktu Sampai sejauh ini, kita menganggap bahwa perkiraan/perhitungan waktu adalah tepat, namun demikian kenyataan di lapangan tidaklah demikian. Ada kalanya waktunya lebih panjang dari perkiraan tetapi ada kalanya waktunya lebih cepat selesainya sebuah aktivitas. Untuk keperluan ini ada tiga macam waktu yang sering digunakan untuk memperkirakan penyelesaian sebuah aktivitas, yaitu: perkiraan tercepat (optimistic estimate) dinotasikan dengan a, perkiraan ter-lambat (pessimistic estimate) dinotasikan
143
dengan b, dan perkiraan yang kebanyakan terjadi (most likely estimate) yang dinotasikan dengan m. Model hubungan antara a, b, dan m biasanya berdistribusi beta dimana a ujung kiri, b di ujung kanan dan m modusnya. Secara grafik dapat digambarkan sebagai berikut:
Model probabilitas suatu aktivitas dapat diselesaikan. Selanjutnya di dalam Program Evaluation and Review Technique (PERT), untuk menyelesaikan proyek ada beberapa asumsi tentang estimasi (perkiraan waktu). Asumsi 1. Penyebaran antara a (optimistic estimate) dan b ( pessimistic estimate) adalah enam simpangan baku, sehingga diperoleh hubungan 6σ = b − a . Akibatnya varian dari aktivitas adalah σ
2
1 = (b − a) 6
2
Asumsi 2. Distribusi probabilitas setiap aktivitas adalah (sekurang-kurangnya mendekati) distribusi beta. Berdasarkan ke dua asumsi diatas, estimasi waktu ( t e ) dapat didekati dengan te =
1 1 2 m + ( a + b) 3 2
Perhatikan bahwa
1 (a + b) adalah titik tengah antara a dan b. 2
Selanjutnya kita memisalkan ketiga waktu untuk proyek pembuatan rumah sederhana diatas seperti Tabel 3. 5 berikut:
144
Tabel 3. 5 Perkiraan waktu penyelesaian suatu aktivitas Aktivitas
Optimistic
Most likely
Pessimistic
Expected
Variance
No
estimate (a)
estimate (m)
estimate (b)
estimate t e
σ2
1 (A,B)
1
2
3
2
1/9
2 (B,C)
2
3,5
8
4
1
3 (C,D)
6
9
18
10
4
4 (D,K)
4
5,5
10
6
1
5 (D,F)
1
4,5
5
4
4/9
6 (F,G)
4
4
10
5
1
7 (D,G)
3
7,5
9
7
1
8 (G,H)
3
9
9
8
1
9 (H,I)
4
4
4
4
0
10 (H,J)
1
5,5
7
5
1
11 (K,L)
5
6,5
11
7
1
12 (L,M)
5
8
17
9
4
13 (J,N)
5
5,5
9
6
4/9
14 (M,N)
1
2
3
2
1/9
Kita perhatikan bahwa dari diagram di atas, lintasan A → B → C → D → F → G → H → J → N adalah lintasan kritis.
Asumsi 3 Waktu aktivitas adalah bebas secara statistik dan merupakan peubah acak.
Asumsi 4 Lintasan kritis selalu mempunyai total waktu lebih panjang dari pada lintasan yang lain. Dari asumsi 3, asumsi 4, dan dari keterangan wantu di atas, maka didapat lintasan kritis seperti tabel berikut:
145
Tabel Lintasan Kritis Aktivitas pada
Expected value
Variance
lintasan kritis
te
σ2
1 (A,B)
2
1/9
2 (B,C)
4
1
3 (C,D)
10
4
5 (D,F)
4
4/9
6 (F,G)
5
1
8 (G,H)
8
1
10 (H,J)
5
1
13 (J,N)
6
4/9
Jumlah
44
9
Dari tabel lintasan kritis diatas, diperoleh: Expected project time = 44 hari Variance of project time = 9.
Asumsi 5 Distribusi probabilitas project time adalah distribusi normal. Jadi Penyelesaian rumah sederhana di atas selama 44 hari dengan simpangan baku = 3.
146
Soal-soal 1. Seseorang dari Jakarta akan menuju ke Jayapura dengan pesawat terbang. Jalur dan biaya (dalam ribuan rupiah) perjalanan dari Jakarta ke Jayapura adalah sebagai berikut.
Tentukan lintasan perjalanan agar biaya yang dikeluarkan minimum.
147
2. Sebuah Motel dibangun di daerah pegunungan yang sejuk dan nyaman, dengan denah sebagai berikut. Untuk pelayanan kebutuhan listrik Motel, akan dibuat sistem jaringan listrik sendiri agar tidak terganggu kestabilan tenaganya. Buatlah jaringan kabel listrik, agar kabel yang dipakai minimum! 50
40
Km 1
Km 3
Km 2
30
75
60
25
40
Km 4
Km 5
50 20
40
40
100 30
Km 7
Km 9
30
Kantor
20
Km 6
Km 8
Denah Motel, jarak diukur dalam meter. 3. Pada Pembangunan Motel di atas, akan dibangun sistem aliran air yang terletak di dekat Km 6 dan berakhir di Km 1. Besarnya ukuran pipa berbeda-beda dan kapasitas aliran air (liter per menit) terlihat pada gambar berikut. 150
200
Km 1 150
Km 9
200
100 150
Km 4 100
Km 3
Km 2 250
Km 5
500 100
100 Km 7
200
300
Kantor
100
200
Km 6
Km 8
Gambar Kapasitas Aliran Air (liter per menit). Tentukan basarnya aliran air maksimum dalam sistem jaringan aliran air pada Motel ini.
148
4. Dalam pembangunan Motel ini, waktu yang diperlukan terlihat pada tabel berikut. No
Aktivitas
Lama (minggu)
Prasyarat
1
Persiapan / perataan tanah
4
-
2
Fondasi
4
No 1.
3
Dinding kasar (pemasangan batu bata)
18
No 2.
4
Pemasangan atap
4
No 3.
5
Pemasangan pipa ledeng bagian luar kamar
4
No 3.
6
Pemasangan pipa ledeng bagian dalam kamar
7
No 5.
7
Pemasangan Jaringan listrik
3
No 3.
8
Pemasangan dinding papan untuk peredam suara
6
No 6, dan No 7.
9
Pemasangan keramik lantai
4
No 8.
10
Pengecatan bagian dalam kamar
4
No 8.
11
Pengaturan Taman (diluar kamar)
6
No 4.
12
Pengecatan bagian luar kamar
6
No 4, dan No 11.
13
Pengaturan Interior kamar
6
No 9, dan No 10.
14
Pengaturan eksterior kamar
2
No 12.
15 SELESAI Tentukan berapa lama pembuatan Motel tersebut, dengan asumsi bahwa pelaksanaan pembangunan sesuai dengan perencaraan waktu yang tepat.
BAB VI Program Linear Bilangan Bulat Permasalahan program linear bilangan bulat muncul ketika kita harus memutuskan jumlah barang yang kita perlukan berbentuk bilangan bulat, seperti menentukan banyaknya mesin untuk suatu pabrik, banyaknya foto copy untuk layanan di suatu kantor, banyaknya komputer di suatu ruangan untuk mengerjakan sejumlah pekerjaan, banyaknya orang yang mengerjakan suatu proyek, dan sebagainya. Tidaklah mungkin banyaknya mesin giling padi di suatu pabrik 2,38 buah untuk menggiling padi di suatu wilayah tertentu, keputusan akan menjadi 3 buah, atau 2 buah dengan kerja lembur, dan sebagainya.
Program linear bilangan bulat dikatakan pure integer programming (program linear bilangan bulat murni) apabila semua variabel adalah bilangan bulat. Ada kalanya sebagian variabel bukan bilangan bulat, bisa jadi sebagian variabel bilangan real. Bilamana variabelnya bilangan bulat dan bilangan biner (nol, satu), maka masalah program linear ini disebut mix integer programming (program linear bilangan bulat campuran) atau program linear bilangan bulat nol satu (zero one integer programming). Masalah zero one integer programming biasanya digunakan untuk pengambilan keputusan. Bernilai 1 bila harus melakukan suatu pekerjaan (menerima keputusan) dan bernilai 0 berarti harus menolak suatu pekerjaan (keputusan).
Untuk lebih jelasnya marilah kita lihat beberapa contoh masalah berikut: Masalah 1
Masalah 2 Minimumkan Z = 200 x1 + 400 x2
Maksimumkan Z = 100 x1 + 90 x2
Dengan pembatas:
Dengan pembatas:
10 x1 + 25 x2 ≥ 100
10 x1 + 7 x2 ≤ 70
3 x1 + 2 x2 ≥ 12
5 x1 + 10 x2 ≤ 50
x1 ≥ 0, x2 ≥ 0
x1 ≥ 0, x2 ≥ 0
149
150
Masalah 3 Maksimumkan Z = 80 x1 + 100 x2 4 x1 + 2 x 2 ≤ 15 x1 + 5 x 2 ≤ 16 x1 ≥ 0, x 2 ≥ 0
x1 + 5 x 2 ≤ 16
Selanjutnya apabila kita hitung dengan metode simpleks dengan bilangan real, maka kita peroleh: Masalah 1
Masalah 2
Masalah 3
x1 = 5.38
x1 = 1.82
x1 = 2.388889
x2 = 2.31
x2 = 3.27
x 2 = 2.722222
Z = 746.15
Z = 1,672.73
Z = 463.3333
Misalnya kita diminta untuk menjawab dengan bilangan bulat, kemudian kita bulatkan begitu saja, misalnya menjadi: Masalah 1
Masalah 2
Masalah 3
x1 = 5
x1 = 2
x1 = 2
x2 = 2
x2 = 3
x2 = 3
Z = 680
Z = tak layak
Z = tak layak
Pembulatan yang dilakukan begitu saja, akan mengakibatkan solusi tidak optimal, bahkan dapat menghasilkan jawaban yang tak layak (tidak masuk dalam jawaban yang mungkin). Oleh karena itu pembulatan pada program linear bilangan bulat tidak sesederhana membulatkan menjadi bilangan bulat. Sebab beberapa persyaratan mesti dipenuhi.
Pada masalah diatas bila kita lakukan dengan program linear bilangan bulat akan menghasilkan jawaban:
151
Masalah 1
Masalah 2
Masalah 3
x1 = 7
x1 = 3, x2 = 3 atau
x1 = 1
x2 = 0
x1 = 5, x2 = 2
x2 = 3
Z = 700
Z = 1,800
Z = 360
Bagaimana cara menentukan solusi program linear bilangan bulat?
Ada beberapa cara untuk menentukan (menghitung) solusi program linear bilangan bulat, antara lain: metode grafik, metode cutting plan algorithm, metode branch and bound, dan penyelesaian dengan program komputer. Pada kajian di sini hanya akan dibahas dua cara yaitu metode branch and bound, dan penyelesaian dengan program komputer.
1. Metode Branch and Bound Metode branch and bound mempunyai beberapa langkah: 1. Selesaikan masalah program linear dengan metode biasa (simpleks) yaitu dengan bilangan real (biasa). 2. Teliti solusi optimumnya. Apabila variabel basis yang diharapkan berbentuk bilangan bulat, maka pekerjaan telah selesai. Solusi itu adalah solusi optimum. Tetapi bila solusinya bukan bilangan bulat, maka lakukan langkah selanjutnya. 3. Nilai solusi yang tidak bulat yang layak dicabangkan ke dalam sub-sub masalah, dengan tujuan untuk menghilangkan solusi yang tidak memenuhi persyaratan bilangan bulat. Pencabangan ini dilakukan dengan kendala-kendala mutually exclusive yang perlu untuk memenuhi persyaratan bulat. 4. Untuk setiap sub masalah, nilai solusi optimum kontinu (tak bulat) fungsi tujuan dijadikan sebagai batas atas. Solusi bulat terbaik menjadi batas bawah (pada awalnya ini adalah solusi kontinu yang dibulatkan kebawah). Sub-sub masalah yang mempunyai batas atas kurang dari batas bawah yang ada tidak diikut sertakan dalam analisis selanjutnya. Suatu solusi bulat, layak adalah sama baik atau lebih baik dari batas atas untuk semua sub masalah yang dicari. Jika solusi
152
demikian ada, suatu sub masalah dengan batas atas terbaik dipilih untuk dicabangkan, kemudian kembali ke langkah 3.
Untuk melihat lebih jelas, kita perhatikan contoh berikut: Maksimumkan Z = 150 x1 + 175 x2 Dengan pembatas: 6 x1 + 8 x2 ≤ 99 8 x1 + 4 x2 ≤ 87 x1 ≥ 0, x2 ≥ 0 Dengan metode simpleks biasa atau metode grafik, maka diperoleh. x1 = 7.5
Nampak disamping bahwa semua solusi bilangan pecah (tidak
x2 = 6.75
bulat) maka harus kita lakukan pencabangan.
Z = 2205
Perhatikan grafik berikut.
Masalah diatas dicabang menjadi 3 bagian yaitu: Bagian 1.
Bagian 2.
Bagian 3.
x1 ≤ 7
x1 ≥ 8, x 2 ≥ 0
x1 ≥ 0, x 2 ≥ 7
x2 ≤ 6
8 x1 + 4 x 2 ≤ 87
6 x1 + 8 x 2 ≤ 99
x1 ≥ 0, x2 ≥ 0
153
Bagian 1 Pada bagian 1 memberikan batas bawah (7,6) dengan Z = 150 • 7 + 175 • 6 = 2100
Bagian 2 Pada bagian 2 memberikan batas atas (8,5) dengan Z = 150•8 + 175•5=2075 (dibawah batas bawah).
Bagian 3
154
Pada bagian 3 memberikan batas atas (7,7) dan (0,12) yang memberikan nilai
Z1 = 150 . 7 + 175 . 7 = 2170, Z 2 = 150 . 0 + 175 . 12 = 2100 Dari perhitungan diatas, terlihat bahwa nilai maksimum tercapai pada titik (7,7) dengan nilai Z = 2170. Jadi
solusi
program
linear
bilangan
bulat
diatas
adalah
x1 = 7, x 2 = 7, dengan Z = 2.170 .
2. Penyelesaian Program Linear Bilangan Bulat dengan Program Lindo Untuk menyelesaikan masalah diatas dengan komputer, dalam hal ini kita gunakan program lindo, maka masalah tersebut kita tuliskan pada papan lindo sebagai berikut: Apabila masalah program linear yang tidak harus bilangan bulat kita tuliskan dengan, Max 150x1+175x2 Subject to 6x1+8x2<=99 8x1+4x2<=87 End
Sedangkan untuk masalah program linear bilangan bulat, kita tambahkan gin x1 dan gin x2 untuk memberitahu bahwa x1 adalah bilangan bulat, dan x2 juga bilangan bulat. Atau langsung ditulis dengan gin 2. Sehingga program menjadi: Max 150x1+175x2 Subject to 6x1 + 8x2 <= 99 8x1 + 4x2 <= 87 End Gin x1 Gin x2
atau cukup ditulis dengan max 150x1+175x2 subject to 6x1+8x2<=99 8x1+4x2<=87 end gin 2
155
Maka setelah program Lindo dijalankan akan diperoleh hasil keluaran seperti berikut: LP OPTIMUM FOUND AT STEP 0 OBJECTIVE VALUE = 2306.25000 NEW INTEGER SOLUTION OF 2275.00000 AT BRANCH 2 BOUND ON OPTIMUM: 2275.000 ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 2
0 PIVOT
LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION... OBJECTIVE FUNCTION VALUE 1) 2275.000 VARIABLE X1 X2
ROW 2) 3)
VALUE 7.000000 7.000000
SLACK OR SURPLUS 1.000000 3.000000
NO. ITERATIONS= 2 BRANCHES= 0 DETERM.=
1.000E
REDUCED COST -150.000000 -175.000000
DUAL PRICES 0.000000 0.000000
0
Dari hasil diatas dapat dilihat bahwa, solusi tercapai dengan Z = 2.275, dengan X1 = 7, dan X2 = 7.
3. Penyelesaian Program Linear Bilangan Bulat dengan Program Solver Untuk menyelesaikan Masalah program linear bilangan bulat Dengan solver prinsipnya sama dengan penyelesaian program linear, hanya ditambah syarat (constrain) yaitu sel banyaknya barang adalah bilangan bulat (integer), maka program awal yang kita isikan ke dalam Excel adalah sebagai berikut.
156
Program awal pada lembar kerja Excel. Setelah menjalankan Solver dengan mengisi Parameter Solver berikut.
Maka akan diperoleh hasil berikut ini.
157
Tabel Kebutuhan Bahan Barang (Variabel) Barang 1
Barang 2
Pembatas
Bahan 1
6
8
99
Bahan 2
8
4
87
150
175
7
7
Koef. fungsi Tujuan Banyaknya
Bahan yang dipakai Barang Barang 1
Barang 2
Dipakai
Bahan 1
42
56
98
Bahan 2
56
28
84
Fungsi Tujuan
2275
Hasil di atas menunjukkan bahwa Z optimal terjadi pada x1 = 7, dan x2 = 7 dengan Z = 2275. Pengerjaan dengan program Lingo diserahkan kepada pembaca.
Pengerjaan dengan cara konvensional memerlukan waktu yang cukup lama dan cukup sukar, apalagi apabila banyaknya variabel banyak. Sebagai contoh perhatikan masalah berikut. Sebuah Home Industri “Dynamics Bag Collection” membuat lima macam barang, yaitu Tas Remaja, Tas Ibu-ibu, Tas Sekolah, Dompet Wanita, dan Dompet Pria. Kebutuhan bahan, harga bahan, harga jual, biaya tenaga setiap harinya adalah sebagai berikut:
158
Tabel Kebutuhan Bahan, Persediaan bahan dan Harga Barang Bahan bahan
Tas Remaja
Tas Ibuibu
Tas Sekolah
Imitasi
4m
5m
6m
1m
1m
65 m
Benang
2 rol
3 rol
3 rol
1 rol
1 rol
25 rol
Resliting
2,5 m
3,6 m
2,8 m
0,5 m
0,25 m
90 m
Lem Latex
0,75 kg
0,5 kg
0
0,25 kg
0,25 kg
7 kg
Lem PC
0,25 kg
0,2 kg
0
0,2 kg
0,2 kg
3 kg
2,5 m
7m
0
1,25 m
1m
34 m
36 buah
24 buah
0
10 buah
0
198 buah
Karton
5 lbr
1 lbr
0
0
0
20 lembar
Busa
3m
5m
0
0
0
30 m
Furing Asesoris
Dompet Wanita
Dompet Pria
Persediaan
Harga jual 276.000 300.000 276.000 144.000 123.000 (rupiah) .Pengerjaan secara konvensional hampir tidak mungkin dilakukan, karena menyangkut lima buah variabel.
Masalah ini apabila dikerjakan dengan Solver, maka akan diperoleh hasil berikut. Bahan keperluan Bahan bahan
Tas
Tas
Dompet Dompet
Remaja Tas Ibu-ibu Sekolah
Wanita
Pria
Persediaan
Imitasi
4
5
6
1
1
65
Benang
2
3
3
1
1
25
2.5
3.6
2.8
0.5
0.25
90
Lem Latex
0.75
0.5
0
0.25
0.25
7
Lem PC
0.25
0.2
0
0.2
0.2
3
Furing
2.5
7
0
1.25
1
34
Asesoris
36
24
0
10
0
198
Resliting
159
Karton
5
1
0
0
0
20
Busa
3
5
0
0
0
30
276
300
276
144
123
2
0
3
12
0
Harga jual (rupiah) Banyaknya
Bahan yang terpakai
Bahan -
Tas
Tas
Tas
Dompet Dompet
bahan
Remaja
Ibu-ibu
Sekolah
Wanita
Pria
Sisa Digunakan
bahan
Imitasi
8
0
18
12
0
38
27
Benang
4
0
9
12
0
25
0
Resliting
5
0
8.4
6
0
19.4
70.6
Lem Latex
1.5
0
0
3
0
4.5
2.5
Lem PC
0.5
0
0
2.4
0
2.9
0.1
5
0
0
15
0
20
14
Asesoris
72
0
0
120
0
192
6
Karton
10
0
0
0
0
10
10
Busa
6
0
0
0
0
6
24
Furing
Penghasilan kotor
3108
Hasil ini menunjukkan bahwa Home Industri tersebut harus membuat 2 tas remaja, 3 tas sekolah, dan 12 dompet wanita. Dengan pendapatan kotor Rp 3.108.000,-. Apabila kita cermati hasil di atas, khususnya bahan yang tersisa, maka kekurangan bahan yang menonjol adalah benang dan Lem PC yang kedua bahan tersebut harganya murah dan mudah di dapat. Oleh karena itu ada baiknya persediaan kedua bahan tersebut ditambah.
160
Misalkan benang kita tambah menjadi 50 dan Lem PC kita tambah menjadi 7, maka apabila kita selesaikan akan menghasilkan pendapatan yang cukup melonjak.
Bahan keperluan Tas Bahan -
Tas
Ibu-
Tas
Dompet Dompet
bahan
Remaja
ibu
Sekolah
Wanita
Pria
Persediaan
Imitasi
4
5
6
1
1
65
Benang
2
3
3
1
1
50
2.5
3.6
2.8
0.5
0.25
90
Lem Latex
0.75
0.5
0
0.25
0.25
7
Lem PC
0.25
0.2
0
0.2
0.2
7
Furing
2.5
7
0
1.25
1
34
Asesoris
36
24
0
10
0
198
Karton
5
1
0
0
0
20
Busa
3
5
0
0
0
30
276
300
276
144
123
0
0
6
19
9
Resliting
Harga jual (rupiah) Banyaknya
161
Bahan yang terpakai
Tas Bahan -
Tas
Ibu-
Tas
Dompet Dompet
bahan
Remaja
ibu
Sekolah
Wanita
Pria
Sisa Digunakan bahan
Imitasi
0
0
36
19
9
64
1
Benang
0
0
18
19
9
46
4
Resliting
0
0
17
10
2
29
61
Lem
0
0
0
5
2
7
0
Lem PC
0
0
0
4
2
6
1
Furing
0
0
0
24
9
33
1
Asesoris
0
0
0
190
0
190
8
Karton
0
0
0
0
0
0
20
Busa
0
0
0
0
0
0
30
Penghasilan kotor
5499
Latex
Kita perhatikan pendapatan menjadi Rp 5.499.000,--. Yaitu dengan membuat 9 tas sekolah, 19 dompet wanita, dan 9 dompet pria. Sebuah kenaikan penghasilan yang luar biasa.
Bagaimana kalau Home Industri tersebut sekurang-kurangnya membuat 2 tas wanita dan 3 tas ibu-ibu?
Untuk menyelesaikan masalah ini, cukup menambah pada constrais sel tas remaja >= 2 dan sel tas ibu-ibu >= 3 seperti berikut.
162
Dari Parameter di atas, maka akan diperoleh hasil sebagai berikut.
163
Hasil terakhir menyarankan untuk membuat 2 tas ramaja, 3 tas ibu-ibu, 6 tas sekolah, 4 dompet wanita, dan 2 dompet pria, dengan penghasilan kotor Rp 3.930.000,--.
Penyelesaian masalah dengan Lindo maupun Lingo diserahkan kepada pembaca sebagai latihan.
Soal-soal 1. Seorang Pasien di rumah sakit setiap harinya memerlukan tiga macam zat, sebut saja zat A, zat B, dan zat C, berturut-turut paling sedikit sebanyak 16 satuan, 18 satuan, dan 17 satuan. Zat-zat tersebut terdapat dalam tiga macam obat yaitu obat P, obat Q, dan obat R. Setiap obat P mengandung 2 zat A, 1 zat B, dan 2 zat C. Setiap obat Q mengandung 4 zat A, 1 zat B, dan 1 zat C. Dan setiap obat R mengandung 1 zat A, 3 zat B, dan 2 zat C. Harga obat P, obat Q, dan obat R berturut-turut Rp 1000, Rp 1500, dan Rp 1250. Tentukan banyaknya masing-masing obat untuk memenuhi kebutuhan pasien tersebut agar dicapai biaya minimum.
2. Perusahaan mobil akan mengeksport 400 mobil model A, dan 500 mobil model B. Mobil model A memerlukan tempat 12 m3 dan mobil model B memerlukan tempat 15 m3. Pada jadwal pelayaran terdapat tiga pengangkutan yaitu pada awal bulan Januari, pertengahan bulan Februari dan akhir bulan Maret. Ada pengangkutan pertama hanya membuat mobil model A dengan biaya Rp 450.000,- tiap-tiap mobil. Pada pengangkutan mobil yang kedua dan ketiga membawa kedua model tersebut dengan biaya angkut berturut-turut Rp 35.000,- dan Rp 40.000,- tiap meter kubik. Kapasitas kapal pertama hanya 200 mobil. Pengangkitan kedua dan ketiga berturut-turut sebesar 4500 dan 6000 meter kubik. Pada pertengahan Februari harus terkirim sekurang-kurangnya 250 mobil model A, dan 300 mobil model B. Buatlah model pengangkutan agar diperoleh biaya transportasi minimal.
164
3. Rapi Alumunium adalah pengusaha kecil yang membuat beberapa barang yang berbasis alumunium. Kebutuhan bahan dan persediaan, serta harga jual terlihat pada tabel berikut ini: Jenis barang
Meja
dan bahan
Setrika
Alumunium □ 1” x 1”
Jemuran
Jemuran
handuk
handuk
sayap
engkel
650 cm
Alumunium □
3/4” x 3/4” Alumunium ○ 3/8” Alumunium ○ 3/4”
80 cm
756 cm
75 cm
27 cm
570 cm
25 x 25
360 cm
360 cm
640 cm
640 cm
400 cm
4 bh
O 2800 cm2
4 bh
Persediaan
24000 cm
12000 cm
36000 cm
60000 cm
2540 cm
60000 cm
60000 cm
400 cm
4 bh
Karet Sepatu
Partikel
1386 cm
2214 cm
Lis M 1”
Karet Sepatu
1780 cm
298 cm
Alumunium
Karet Plane
Pakaian
639 cm
5/8”
Lis M 3/4”
Piring
654 cm
Alumunium ○
Alumunium
Jemuran
234 cm
1” x ½ ” Alumunium □
Rak
30000 cm
660 cm
640 cm
30000 cm
660 cm
640 cm
70000 cm
4 bh
4 bh
250 bh
250 bh 60000 cm2
165
Busa Kain Tripek Melamin
2800 cm2
24000 cm2
2800 cm2
50000 cm2
6000 cm2
60000 cm2
Alumunium
20 cm
Gate Rel Alumunium Rel
21 cm
600 cm
Alumunium U
162 cm
3/8” Plat Alumunium Spigot Harga satuan Barang
500 cm
157.000
125.000
100000
315.000
3000 cm
90 cm
1000 cm
130 cm
3000 cm
270.000
Tentukan banyaknya masing-masing barang agar diperoleh pendapatan terbesar?.
DAFTAR ISI
Kata Pengantar Pendahuluan Bab I. Tinjauan Teori-teori sebagai Dasar Program Linear 1. 2. 3. 4. 5. 6. 7. 8.
Himpunan Konveks ................................................................................... 1 Titik Ekstrim ............................................................................................. 2 Sinar dan Arah Himpunan Konveks ......................................................... 2 Arah Ekstrim Himpunan Konveks ............................................................. 4 Bidang Banyak dan Ruang Paruh ............................................................. 5 Fungsi Konveks dan Fungsi Konkav ......................................................... 6 Representasi Himpunan Polihedral (Polihedron) ...................................... 8 Teorema Representasi Bentuk Umum ..................................................... 9
Bab II. Pengenalan Program Linear ..................................................................... 13 1. Penyelesaian dengan Metode Grafik ...................................................... 13 2. Penyelesaian dengan Metode Simpleks .................................................. 19 a. Kasus masalah dengan fungsi tujuan maksimum ....................... 19 b. Kasus masalah dengan fungsi tujuan minimum .......................... 27 3. Primal dan Dual ...................................................................................... 31 a. Masalah Primal dan Dual ......................................... 31 b. Hubungan Primal dan Dual ......................................................... 34 4. Program Komputer Lindo, Lingo, dan Solver ........................................ 36 a. Lindo ........................................................................................... 36 b. Menyelesaikan Masalah Program Linear dengan Lindo ............. 43 c. Lingo untuk Menyelesaikan Program Linear ............................. 48 d. Solver untuk Menyelesaikan Program Linear ............................. 50
Bab III. Transportasi ........................................................................................... 60 1. Metode Transportasi ...................................................................................... 60 2. Permasalahan dalam Metode Transportasi .................................................... 60 a. Beberapa Metode dalam Penyelesaian Masalah Transportasi (Penyelesaian awal) ................................................................................. 62 i. North West Corner (NWC) ......................................................... 62 ii. Metode Inspeksi ......................................................................... 63 iii. Metode VAM ( Vogel Approximation Method) ......................... 67 b. Menentukan Nilai Optimal ...................................................................... 74 i. Metode Steppingstone ................................................................ 74 ii. Modified Distribution Method (MODI) ...................................... 79
c. Penyelesaian Masalah dengan Program Komputer ................................. 83 i. Program Lindo untuk Menyelesaikan Masalah Transportasi ..... 83 ii. Program Lingo untuk Menyelesaikan Masalah Transportasi ..... 88 iii. Program Solver untuk Menyelesaikan Masalah Transportasi ..... 92 d. Masalah Transportasi Pasar Tidak Seimbang ........................................ 95
Bab IV. Penugasan dan Transshipment ........................................................... 108 1. Penugasan ............................................................................................. 108 i. Menyelesaikan Masalah Penugasan dengan Metode Hongaria 108 ii. Menyelesaikan Masalah Penugasan dengan Program Komputer111 iii. Program Lindo untuk Menyelesaikan Masalah Penugasan . . 111 iv. Program Solver untuk Menyelesaikan Masalah Penugasan . . 113 2. Transshipment ....................................................................................... 117 i. Program Lingo untuk Menyelesaikan Masalah Transshipment 119 ii. Program Solver untuk Menyelesaikan Masalah Transshipment 122 Bab V. Analisis Jaringan ................................................................................... 125 1. 2. 3. 4.
Masalah Lintasan Terpendek ................................................................ 127 Masalah Diagram Pohon Terpendek ................................................... 133 Masalah Aliran Maksimum .................................................................. 135 Menyelesaikan proyek dengan PERT dan CPM .................................... 140
Bab VI. Program Linear Bilangan Bulat ........................................................... 149 1. Metode Branch and Bound ................................................................... 151 2. Penyelesaian Program Linear Bilangan Bulat dengan Program Lindo.. 154 3. Penyelesaian Program Linear Bilangan Bulat dengan Program Solver . 155 Daftar Pustaka .................................................................................................... 166 Indeks ................................................................................................................. 167
KATA PENGANTAR
Puji Syukur Kehadirat Ilahi yang telah memberi karuniaNya sehingga buku Program Linear Berbantuan Komputer: Lindo, Lingo dan Solver dapat terselesaikan. Buku ini ditujukan kepada mahasiswa matematika, ekonomi dan teknik terutama mahasiswa yang mempelajari program linear dan memanfaatkan komputer sebagai alat bantu dalam menyelesaikan masalah program linear. Buku ini ditulis bertujuan untuk melengkapi buku-buku program linear yang perhitungannya mengunakan perhitungan manual. Akibatnya dalam pengambilan masalah sering membatasi dengan sedikit variabel. Dalam buku ini, penyelesaian suatu masalah akan dikerjakan dengan cara perhitungan manual, kemudian diselesaikan dengan bantuan komputer khususnya program Lindo, Lingo atau Solver. Dengan menggunakan komputer sebagai alat bantu hitung, maka masalah perhitungan dan banyaknya variabel bukan menjadi kendala lagi. Untuk mahasiswa ekonomi maupun teknik, dapat langsung memulai dari Bab II dan seterusnya, sedangkan mahasiswa matematika perlu memahami terlebih dulu teori yang berada pada Bab I. Ucapan terima kasih kami sampaikan kepada Penjaminan Mutu Universitas Negeri Semarang yang telah memberikan kesempatan kepada Penulis untuk penulisan buku ini. Selanjutnya saran dan kritik dari pembaca sangat diharapkan guna penyempurnaan buku ini.
Semarang, Agustus 2007 Penulis
