BAB 2
LANDASAN TEORI
2.1 Analisa Jaringan Kerja
Metode jaringan kerja diperkenalkan menjelang decade 50-an, oleh satu tim engineer dan ahli matematika dari perusahaan Du Pont bekerja sama dengan Rand Corporation, dalam usaha mengembangkan sistem kontrol manajemen. Sistem ini dimaksudkan untuk merencanakan dan mengendalikan sejumlah besar kegiatan yang memiliki hubungan ketergantungan yang kompleks dalam masalah desain, engineering, konstruksi dan pemeliharaan. Usaha-usaha ditekankan untuk mencari metode yang dapat meminimalkan biaya, dalam hubungannya dengan kurun waktu penyelesaian suatu kegiatan.
Jaringan kerja dapat didefenisikan sebagai kumpulan dari kejadian-kejadian dan kegiatan-kegiatan yang menggambarkan tinjauan waktu dari susunan proyek. Jaringan kerja muncul pada sejumlah perencanaan dan dalam berbagai bidang. Perencanaan jaringan kerja merupakan suatu alat manajemen yang memungkinkan dapat lebih luas dan lebih lengkap untuk perencanaan dan pengawasan suatu proyek.
Dalam banyak situasi, manager bertanggung jawab untuk perencanaan dan menjadwalkan dan mengendalikan proyek yang terdiri dari berbagai pekerjaan atau aktivitas terpisah yang dilakukan oleh berbagai departemen dan individu. Dalam hal ini manager harus mengadakan pendekatan secara kuantitatif dalam pengambilan suatu keputusan. Cara ini penting sekali digunakan oleh manager yang bertanggung jawab atas bidang engineering, production, administration, dan penelitian operasional. Penerapan pengambilan keputusan secara pendekatan kuantitatif
dalam berbagai
bidang pada kenyataannya prosedurnya tidaklah begitu kompleks. Oleh karena cara ini dapat dianalisa secara sistematis dan sederhana dengan menggunakan metode analisa jaringan kerja.
Universitas Sumatera Utara
Teknik jaringan kerja menunjukkan manfaat nyata bila digunakan membantu atau melengkapi perencanaan dan pengendalian proyek baru. Sedangkan untuk proyek yang sedang berjalan penerapan analisa jaringan kerja akan terkait pada persyaratan atau ketentuan semula yang ditetapkan atau yang sedang berjalan.
Penggambaran jaringan kerja merupakan suatu teknik jaringan kerja yang digunakan secara luas untuk masalah-masalah seperti produksi, distribusi, perencanaan proyek, perencanaan keuangan dan lain sebagainya. Sesungguhnya penggambaran jaringan kerja menyediakan bantuan secara visual dan konseptual yang sangat berharga dalam menggambarkan hubungan antara komponen-komponen dalam suatu sistem. Hal ini sangat bermanfaat bagi para pengambil keputusan.
Menggambarkan jaringan kerja dari tiap awal kegiatan sangat bermanfaat untuk mempermudah pengawasan serta pengumpulan, penetapan dan penganalisaan informasi yang sesuai dengan tujuan yang diharapkan, sehingga keputusan-keputusan dalam pemilihan alternatif dengan mudah dapat dilaksanakan untuk mencapai tujuan proyek. Didalam penyusunan perencanaan suatu jaringan kerja suatu proyek, harus ada logika ketergantungan dari suatu kegiatan dengan kegiatan yang lain, serta menggunakan simbol-simbol kegiatan maupun simbol-simbol peristiwa. Dengan demikian diharapkan teori jaringan kerja dapat mengatur rangkaian dari kegiatankegiatan, sehingga benar-benar dapat dilaksanakan secara efektif dan efisien.
Pemakaian analisa jaringan kerja dalam suatu proyek dimaksudkan untuk mengkoordinir semua unsur proyek kedalam suatu rencana utama, dengan menciptakan suatu modal kerja untuk melengkapi proyek sehingga diperoleh waktu terbaik melakukan pekerjaan atau kegiatan, penekanan biaya, pengurangan resiko, penggunaan
sumber-sumber
secara
efektif
dan
efisien,
mendapatkan
atau
mengembangkan schedule yang optimum, memudahkan revisi atau perbaikan terhadap penyimpangan yang terjadi.
Jadi, kunci keberhasilan pendekatan jaringan kerja untuk menyelesaikan suatu model masalah adalah mengetahui bagaimana masalah itu dapat disajikan sebagai
Universitas Sumatera Utara
suatu model jaringan. Dengan demikian permasalahan yang kompleks dapat diselesaikan lebih sederhana dan lebih sistematis.
2.2 Sistematika Menyusun Jaringan Kerja
Sistematika lengkap dari proses menyusun jaringan kerja adalah sebagai berikut : 1. Langkah Pertama Mengkaji
dan
mengidentifikasi
lingkup
proyek,
menguraikan
atau
memecahkannya menjadi kegiatan-kegiatan atau kelompok kegiatan yang merupakan komponen proyek. Pengkajian yang dimaksud adalah untuk mengetahui kegiatan-kegiatan apa yang merupakan bagian atau komponen dari proyek yang bisa dibedakan satu sama lain. 2. Langkah kedua Menyusun kembali komponen-komponen tersebut pada butir pertama, menjadi mata rantai dengan urutan yang sesuai dengan logika ketergantungan. Urutan ini dapat berbentuk pararel atau seri. Menyusun urutan ketergantungan dituntut berpikir secara analitis, sehingga akan diperoleh urutan yang benar-benar dapat mempermudah permasalahan. 3. Langkah ketiga Memberikan perkiraan kurun waktu bagi masing-masing kegiatan yang dihasilkan dari penguraian lingkup proyek. Dengan memasukkan unsur kurun waktu ke analisis jaringan kerja, berarti perencanaan telah memasuki taraf yang lebih spesifik, yaitu membuat jadwal kegiatan proyek. 4. Langkah keempat Mengidentifikasi jalur kritis (critical path) pada jaringan kerja. Jalur kritis adalah jalur yang terdiri dari rangkaian kegiatan dari lingkup proyek, yang bila terlambat akan menyebabkan keterlambatan proyek secara keseluruhan. Masalah jalur kritis akan penulis sajikan pada sub bab dalam bagian ini secara lengkap. 5. langkah kelima Bila semua langkah-langkah diatas diselesaikan, dilanjutkan dengan usaha-usaha meningkatkan daya guna dan hasil guna pemakaian sumber daya, yang meliputi kegiatan :
Universitas Sumatera Utara
a. menentukan jadwal yang paling ekonomis b. meminimalkan fluktuasi pemakaian sumber daya
Setelah tersusun rencana dan jadwal proyek yang cukup realistik, kemudian dapat dipakai diantaranya sebagai tolak ukur atau alat pembanding dalam kegiatan pengendalian pada tahap inplementasi fisik, yaitu dengan memperbandingkan antara perencanaan atau jadwal dengan hasil pelaksanaan nyata dilapangan.
2.3 Diagram Jaringan kerja
Diagram jaringan kerja merupakan logika model yang menggambarkan hubungan antara masing-masing kegiatan dan menjelaskan arus dari operasi sejak awal hingga selesainya kegiatan-kegiatan proyek.
Diagram jaringan kerja mempunyai dua peranan. Yakni, pertama sebagai alat perencanaan proyek dan yang kedua sebagai ilustrasi secara grafik dari kegiatankegiatan suatu proyek. Oleh karena itu diagram suatu jaringan kerja harus mampu memberi gambaran tentang dimulainya dari awal kegiatan sampai diselesaikannya kegiatan tersebut.
Untuk itu diagram jaringan kerja memerlukan beberapa lambang khusus untuk memberikan keterangan yang jelas tentang suatu proyek, yaitu : 1.
Anak panah (arrow) menyatakan kegiatan dengan ketentuan bahwa panjang dan arah panah tidak mempunyai arti khusus. Pangkal dan ujung panah menerangkan kegiatan mulai dan berakhir dengan arah kekanan (positif). Kegiatan harus berlangsung terus dalam jangka waktu tertentu (duration) dengan pemakaian sejumlah sumber seperti manusia, alat, bahan dan dana. Pada umumnya kegiatan diberikan huruf kode huruf besar A, B, C, dan seterusnya.
2.
Lingkaran kecil atau node menyatakan suatu kejadian atau peristiwa. Kejadian diartikan sebagai awal atau akhir dari satu atau beberapa
Universitas Sumatera Utara
kegiatan. Umumnya kegiatan diberi kode dengan angka 1, 2, 3, dan seterusnya yang disebut dengan nomor kejadian.
3.
Anak panah terputus-putus menyatakan kegiatan semu atau dummy. Dummy sebagai pemberitahuan bahwa terjadi perpindahan dari satu kejadian ke kejadian yang lain pada saat yang sama. Oleh karena itu dummy tidak memerlukan waktu dan tidak menghabiskan sumber. Panjang dan arah dummy tidak mempunyai arti khusus.
Untuk menyatakan saling ketergantungan logika dari kegiatan-kegiatan berikut ini dijelaskan beberapa ketentuan sebagai berikut : A 1.
1
B 2
3
: Kegiatan B hanya dapat dimulai setelah kegiatan A selesai. Perlu diperhatikan bahwa kejadian merupakan awal dan akhir suatu kegiatan. Jadi kegiatan B mulai pada dimana kejadian A berakhir.
1. kegiatan C hanya dapat dimulai setelah kegiatan A dan selesai. Kegiatan A dan B boleh berlangsung bersama-sama ; A dan B berakhir pada kegiatan yang sama. 1
A
C 3
B
4
2
3. kegiatan C dan D dapat dimulai setelah kegiatan A dan B berakhir, dan selesai pada kejadian yang berbeda. 1
A
C
4
3
B 2
D 5
Universitas Sumatera Utara
4. Dalam diagram ini (a), (b), (c) terdapat dua kejadian yang saling bergantungan tanpa dihubungkan dengan kegiatan, tapi dihubungkan dengan dummy. 1
A
A
1
3
4
3
B
C
C
2
4
5
2
B (a)
D (b)
1
3
2
5
4
6
(c)
5.
1
A 3
C
4
B 2
Dalam hal terdapat kejadian menyatu (merge event) seperti ini maka ada dua pertimbangan yaitu : a. Kegiatan C tergantung pada selesainya seluruh kegiatan A dan B. b. Kegiatan C tergantung pada selesainya kegiatan A dan sebagian kegiatan B atau sebaliknya. Dalam hal seperti ini rangkaian kegiatan dapat disusun dalam bentuk lain yaitu :
Universitas Sumatera Utara
A
1
2
3
C
4
B1
5
6
B2 Atau
A1 1
A2 3
2
B
4
5
C
6
6. Bila ada dua kegiatan berbeda yang mulai pada kejadian yang sama dan berakhir pada kejadian yang sama pula, maka pekerjaan tersebut tidak boleh dibuat berimpit, misalnya 2
A 1
3
B
4
C
7. Dalam suatu jaringan kerja tidak boleh terjadi suatu loop atau arus putar, misalnya 1
A
3
D
5
B 2
C
4
8. Nomor kejadian terkecil adalah nomor dari kejadian awal dan nomor kejadian terbesar adalah nomor kejadian akhir. Nomor kejadian ditulis di dalam lingkaran kejadian.
9. Tiap kegiatan diberi kode berupa huruf besar juga diberi kode dengan simbol (i, j) ; i menyatakan nomor kejadian awal kegiatan dan j menyatakan nomor kejadian akhir kegiatan.
Universitas Sumatera Utara
2.4 Menyusun Urutan Kegiatan
Menyusun urutan kegiatan atau hubungan kegiatan yang satu dengan yang lain dalam proses pembuatan jaringan kerja, didasarkan atas logika ketergantungan. Hal ini merupakan salah satu aturan dasar dalam menyusun jaringan kerja. Ketergantungan ini dikelompokkan menjadi dua golongan yaitu :
a. Ketergantungan Alamiah Sebagian besar ketergantungan disebabkan oleh sifat kegiatan itu sendiri. Misalnya kasus untuk pendirian sebuah rumah. Kegiatan untuk menaikkan atap belum dapat dilakukan
sebelum
pekerjaan
mendirikan
tiang
penyangga
diselesaikan.
Ketergantungan demikian disebut ketergantungan alamiah, karena meskipun seandainya tersedia cukup tenaga atau sumber daya lain, tetapi tiang belum berdiri dan siap menyangga atap, maka pelaksanaan pekerjaan menaikkan atap belum dapat dimulai.
b. Ketergantungan Sumber Daya Jenis lain dari ketergantungan adalah ketergantungan sumber daya. Sebagai contoh pekerjaan membuat pondasi tidak dapat dilakukan bersamaan waktunya dengan pekerjaan pabrikasi tiang atau kerangka atap, karena kurangnya tenaga kerja, sehingga harus dilakukan secara berurutab atau seri. Dalam contoh ini ketergantungan tersebut disebabkan oleh terbatasnya dana atau sumber daya.
Menyusun jaringan kerja pada awalnya hendaknya didasarkan atas ketergantungan alamiah. Pada taraf selanjutnya nanti bila sampai pada analisa keperluan sumber daya, mungkin penyesuaian atau revisi dilakukan.
Usaha menyusun urutan kegiatan yang mengikuti logika ketergantungan akan dipermudah dengan menjawab pertanyaan berikut : •
Kegiatan apa yang dimulai terlebih dahulu
•
Mana kegiatan berikutnya yang akan dilakukan
•
Adakah kegiatan-kegiatan yang berlangsung sejajar
•
Perlukah mulainya kegiatan tertentu menunggu yang lain
Universitas Sumatera Utara
Contoh 1
Sebagai gambaran dalam menyusun komponen-komponen kegiatan proyek menjadi jaringan kerja, berikut ini adalah contoh proyek pembangunan gudang kerangka besi, seperti yang terdapat pada tabel 2.1 dibawah ini.
Tabel 2.1. Proyek Pembangunan Gudang kerangka besi Kegiatan i
j
Kegiatan Keterangan
Yang Mendahului
(1)
(2)
(3)
(4)
1
A
Membuat gambar desain
2
B
Membeli material
A
3
C
Menyiapkan lahan
A
4
D
Pabrikasi (tiang dan atap)
B
5
E
Membuat pondasi
C
6
F
Mendirikan bangunan
B,C
Proyek dipecah menjadi 6 komponen pekerjaan dan ditentukan urutannya. Pada langkah ini, yang diberi perhatian hanyalah menyusun kegiatan-kegiatan tersebut berdasarkan hubungan ketergantungan, sedangkan hal-hal lain akan ditinjau pada tahap berikutnya. Terlihat bahwa kegiatan pembelian material (B) harus menunggu selesainya pembuatan gambar desain (A), karena sebelum desain diselesaikan belum diketahui jumlah maupun macam material secara tepat. Demikian pula halnya dengan pekerjaan menyiapkan lahan (C) harus menunggu sampai gambar desain selesai untuk mengetahui misalnya berapa ukuran penggalian tanah untuk pondasi yang harus disiapkan. Dari analisis diketahui bahwa kegiatan pembelian material (B) dapat dilakukan bersamaan waktunya dengan kegiatan menyiapkan lahan (C). Selanjutnya mudah dimengerti bahwa pekerjaan pabrikasi (3-5) harus menunggu tersedianya material. Sedangkan mengecor pondasi (4-5) menunggu selesainya menyiapkan lahan (C). Pekerjaan mendirikan bangunan (F) baru dapat dimulai bila dua pekerjaan yang mendahuluinya telah selesai, yaitu membuat fondasi (E) dan pabrikasi tiang dan atap
Universitas Sumatera Utara
telah dikerjakan (D). Bila kegiatan-kegiatan diatas disusun dalam diagram jaringan kerja kan terlihat seperti pada gambar 2.3 dibawah ini : 2
A 1
B
D
3
F 4
C
2
E 2
Gambar 2.1. Jaringan Kerja Proyek Pembangunan Kerangka besi
2.5 Metode yang Digunakan
Pengolahan proyek berskala besar membutuhkan suatu perencanaan, penjadwalan dan koordinasi sejumlah kegiatan yang saling berkaitan. Untuk membantu tugas ini, suatu prosedur formal yang didasarkan pada penggunaan jaringan kerja dan teknik jaringan kerja telah dikembangkan sejak akhir tahun 1950 – an. Beberapa teknik berdasarkan analisa jaringan kerja yang sudah berkembang luas diantaranya yang paling terkenal adalah metode lintasan kritis dan teknik penilaian dan peninjauan program serta beberapa modifikasi lain untuk keperluan khusus. Teknik-teknik ini pada umumnya bertujuan menguraikan dan menentukan hubungan antara berbagai kegiatan dalam perencanaan proyek secara menyeluruh untuk merencanakan dan pengendalian proyek.
Dalam tulisan ini penulis menggunakan teknik analisa jaringan kerja yaitu CPM (Critical Path Metod). Untuk lebih jelasnya, CPM akan penulis terangkan dalam sub bab berikut ini.
2.5.1 CPM (Critical Path Method)
Metode CPM adalah metode yang digunakan untuk merencanakan dan mengendalikan proyek, merupakan sistem yang paling banyak dipergunakan diantara sistem lain yang memakai prinsip pembentukan jaringan kerja. Metode CPM sering dipergunakan pada hampir setiap proyek-proyek besar, misalnya pembangunan gedung, pembuatan
Universitas Sumatera Utara
jembatan layang dan lain-lain. Metode CPM lebih menitikberatkan pada persoalan keseimbangan antara biaya dan waktu penyelesaian.
Jika dalam suatu proyek, waktu yang dibutuhkan untuk menyelesaikannya dapat diperkirakan terlebih dahulu dan biaya-biaya proyek dapat dihitung sejak semula, maka dengan mempergunakan metode CPM pelaksanaan proyek akan lebih terarah dan sistematis. Dalam pelaksanaan proyek dengan menggunakan metode CPM dikenal adanya jalur kritis, yaitu jalur yang memiliki rangkaian komponen-komponen kegiatan, dengan total jumlah waktu terlama dan menunjukkan kurun waktu penyelesaian proyek yang tercepat. Jadi jalur kritis terdiri dari rangkaian kegiatan kritis, dimulai dari kegiatan pertama sampai kegiatan terakhir proyek. Makna jalur kritis penting bagi pelaksanaan proyek, karena pada jalur terletak kegiatan-kegiatan yang bila pelaksanaannya terlambat maka akan menyebabkan keterlambatan proyek secara keseluruhan. Maka perlu adanya perhatian penuh pada jalur kritis tersebut, karena cepat lambatnya suatu proyek selesai terletak pada jalur kritis.
Dalam metode CPM digunakan dua buah perkiraan waktu untuk setiap kegiatan yang terdapat pada jaringan kerja yakni: a. Perkiraan Normal (Normal Estimates) Perkiraan normal adalah waktu yang dibutuhkan untuk menyelesaikan aktivitas proyek jika proses pelaksanaannya berjalan normal. b. Perkiraan Cepat. Perkiraan cepat adalah waktu yang dibutuhkan oleh proyek yang sesingkatsingkatnya untuk penyelesaian proyek tanpa memperhitungkan biaya.
A. Terminologi dan Defenisi
Dalam proses identifikasi jalur kritis, dikenal beberapa terminology dan defenisi sebagai berikut : a. ES (Earliest Start Time) Earliest Start time adalah waktu mulai paling awal suatu kegiatan. Bila waktu kegiatan dinyatakan atau berlangsung dalam jam, maka waktu ini adalah jam paling awal kegiatan dimulai.
Universitas Sumatera Utara
b. EF (Earliest Finish Time) Earliest Finish Time adalah waktu selesai paling awal suatu kegiatan.
c. LS (Lates Allowable Start Time) Lates Allowable Start Time adalah waktu paling akhir kegiatan boleh dimulai tanpa memperlambat penyelesaian proyek secara keseluruhan. d. LF (Latest Allowable Finish Time) Latest Allowable Finish Time adalah waktu paling akhir kegiatan boleh selesai tanpa memperlambat penyelesaian proyek. e. Duration Duration adalah waktu kegiatan, umumnya dengan satuan hari, minggu, bulan, dan lain-lain.
B. Pengertian Slack
Slack didefenisikan sebagai panjang waktu suatu aktivitas dapat ditunda tanpa mempengaruhi waktu yang dibutuhkan untuk menyelesaikan suatu proyek. Jumlah waktu slack untuk setiap aktivitas dapat dihitung sebagai berikut : Slack = LS – ES = LF – EF………………………………………………...(2.1)
Pada perencanaan dan penyusunan jadwal proyek, arti penting daripada slack adalah menunjukkan jumlah waktu yang diperkenankan suatu kegiatan boleh ditunda, tanpa mempengaruhi jadwal penyelesaian proyek secara keseluruhan. Jumlah waktu tersebut sama dengan waktu yang didapat bila semua kegiatan terlebih dahulu dimulai seawal mungkin, sedangkan semua kegiatan berikutnya dimulai selambat mungkin.
Universitas Sumatera Utara
Berikut ini ditunjukkan posisi dan hubungan slack dan parameter-parameter yang lain. ES (i,j) Kegiatan A
EF (i,j)
slack
slack
kegiatan A LS (i,j)
LF (i,j) D (i,j)
E (i)
E (j)
L (j)
Gambar 2.2 Posisi dan hubungan antara ES, LS, LF, EF, D dan Slack
Dari gambar diatas terlihat bahwa slack dapat berada dibagian awal mulainya kegiatan (ES) atau di ujung waktu penyelesaian paling akhir (LS), bahkan dapat dipecah-pecah sesuai kebutuhan, asalkan masih dalam batas L (j) dan E (i).
Bagi pengelola proyek memahami pengertian diatas akan sangat berguna, terutama untuk memecahkan masalah pemerataan sumber daya (resource leveling).
C. Perhitungan Maju (Forward Pass)
Dalam mengidentifikasi jalur kritis dipakai suatu cara yang disebut hitungan maju. Hitungan maju dimulai dari kiri kekanan sampai kegiatan terakhir, atau dengan kata lain dimulai dari kegiatan paling awal kegiatan sampai pada kegiatan yang terakhir. Tujuan dari forward pass adalah menghitung earliest start time dan earliest finish time untuk setiap aktivitas dalam suatu proyek. Forward pass kemudian dikerjakan dengan anggapan bahwa aktivitas mulai secepat mungkin yaitu setelah aktivitas-aktivitas yang mendahuluinya selesai.
Universitas Sumatera Utara
Adapun langkah-langkah forward pass adalah : a. Tentukan ES i = 0 untuk kejadian paling awal dari suatu jaringan kerja. Hal ini logis sebab belum ada kegiatan yang sudah dikerjakan, artinya kegiatan pertama baru akan dimulai. b. Aturan selanjutnya adalah menghitung : ES j = maks {ES i + Dij } dan untuk semua kegiatan (i, j ) . Agar dapat menghitung ES j untuk kejadian j, semua ES i harus dihitung terlebih dahulu.
D. Perhitungan Mundur (Backward Pass)
Selain perhitungan maju, akan digunakan perhitungan mundur untuk mengidentifikasi jalur kritis. Perhitungan mundur bergerak dari kanan ke kiri, atau dengan kata lain dari kegiatan paling terakhir sampai kegiatan paling awal. Tujuan dari backward pass adalah untuk menghitung latest alloweable start time dan finish time untuk setiap kegiatan.
Adapun langkah-langkah untuk menghitung backward pass adalah: a. Tentukan harga LF untuk kejadian yang terakhir yang besarnya sama dengan ES pada kejadian tersebut, dimana LFi = ES i . b. Aturan selanjutnya adalah menghitung: LFi = min {LFi − Dij } untuk semua kegiatan (i, j ) .
2.5.1.1 Cara Menghitung Jalur Kritis
Untuk menentukan jalur kritis, harus dilakukan dua macam perhitungan yaitu perhitungan maju (forward pass) dan perhitungan mundur (backward pass). Untuk lebih memahami cara menghitung jalur kritis dengan menggunakan perhitungan maju dan perhitungan mundur yang telah dijelaskan diatas, berikut akan diberikan gambaran suatu kegiatan yang telah dibuat kedalam suatu jaringan kerja. Dari jaringan kerja berikut ini akan ditentukan jalur kritis dengan cara sebagai berikut :
Universitas Sumatera Utara
20 20
3 B
1
0
A
0
12
2
d1
8
12
C
12
4
D
20 20
4
E
6
12 4
32
G
32
4
F 5
7
36 36
4
24 28
Gambar 2.3 Pembentukan Jalur Kritis
2.5.1.1.1 Cara forward pass ES i = 0 dimana kejadian pertama kali belum ada kegiatan, baru akan dimulai. Dij = lamanya waktu yang diperlukan kegiatan (i, j ) ES j = maks {ES i + Dij }
Perhatikan gambar 2.2. diatas, hanya ada satu kegiatan yang mulai dari node 1 menuju ke 2 yaitu kegiatan A. Dimana
ES1 = 0, oleh karena itu hanya ada satu
kegiatan saja dari node 1, yaitu kegiatan A dan D A = 3, maka ES 2 = {ES1 + D12 } = {0 + 12} = 12
Nilai ini dimasukkan dalam bujur sangkar diatas node 2. Event berikutnya adalah event 3 (perhatikan event 4 belum bisa dihitung, sebab untuk menghitung diperlukan nilai ES 3 yang harus dihitung terlebih dahulu. ES 3 = {ES 2 + D23 } = {12 + 8} = 20 (nilai ini dimasukkan dalam node 3).
Universitas Sumatera Utara
Sekarang ES 4 baru bisa dihitung sebab ada dua kegiatan yang menuju kenode 4 yaitu kegiatan B dan C.
ES 4 = maks {ES i + Dij } i = 2,3
= maks {ES 2 + D34 , ES 3 + D24 } = maks {20 + 0 ,12 + 4} = maks {20,16} = 20 (nilai ini dimasukkan kedalam node 4). ES 5 =
{ES
i
+ Dij }
= {ES 4 + D45 } = {20 + 4} = 24 (nilai ini dimasukkan kedalam node 5). ES 6 = maks {ES i + Dij } i = 4,5
= maks {ES 4 + D46 , ES 5 + D56 } = maks {20 + 1 2, 24 + 4} = maks {32,28} = 32 (nilai ini dimasukkan kedalam node 6). ES 7 = {ES i + Dij } = {32 + 4} = 36
Perhitungan dengan forward pass sudah selesai, semua waktu paling awal sudah dihitung.
Universitas Sumatera Utara
2.5.1.1.2. Cara Backward pass Berikut ini adalah menghitung waktu penyelesaian paling akhir dengan cara sebagai berikut :
LFi = min {LF j − Dij }, untuk semua kegiatan (i, j ) j
Semua nilai LFi kemudian dimasukkan dalam masing masing node. LF7 = ES 7 = 36 LF6 = {LF7 − D67 } = {36 − 4} = 32 LF5 = {LF j − Dij } = {LF6 − D56 } = {32 − 4} = 28 LF4 = min {LF j − Dij } i = 5, 6
= min {LF6 − D46 , LF5 − D45 } = min {32 − 12, 28 − 4} = min {20,24} = 20 LF3 = {LF4 − D34 } = {20 − 0} = 20
LF2 = min {LF3 − D23 , LF4 − D24 } = min {20 − 8, 20 − 4} = min {12,16} = 12 LF1 = {LF2 − D12 } = {12 − 12} =0
Universitas Sumatera Utara
Setelah semua nilai ES dan LF sudah dihitung untuk semua node, maka suatu kegiatan (i, j ) dikatakan terletak pada jalur kritis dan merupakan kegiatan kritis jikalau memenuhi syarat berikut : I. ES i = LFi II. ES j = LF j III. ES j − ES i = LF j − LFi = Dij ..........................................................................(2.2)
Dengan menggunakan syarat diatas, ternyata kegiatan atau aktivitas (1,2), (2,3), (3,4), (4,6) dan (6,7) merupakan kegiatan-kegiatan kritis. Ini merupakan waktu yang paling pendek atau paling cepat penyelesaian proyek tersebut, dimana jumlah waktu yang diperlukan = D12 + D23 + D34 + D46 + D67 = 12 + 8 + 0 + 12 + 4 = 36 Yaitu sebesar LF6 yaitu waktu penyelesaian paling akhir atau paling lambat. Perhatikan : kegiatan (2,4), (4,5) dan (5,6) memenuhi syarat I dan II tetapi tidak memenuhi syarat III, jadi tidak merupakan jalur kritis. Jalur kritis selain memenuhi syarat I, II, dan III juga harus membentang (membentuk mata rantai) dari node awal sampai dengan node yang terakhir.
2.5.2 Metode Simpleks
Metode simpleks untuk penyelesaian persoalan optimasi menggunakan tabel terstruktur pengolahan data dengan algoritma khusus penyusunan tabel-tabel optimasi sebagai penjabaran dari langkah-langkah eliminasi Gauss-Jordan dan subtitusi yang digunakan pada teknik program linear.
Tabel simpleks terdiri dari baris dan kolom yang memuat simbol dan nilai koevisien dari variabel-variabel yang digunakan pada fungsi tujuan dan persamaanpersamaan pembatas seperti tabel dibawah ini.
Universitas Sumatera Utara
Tabel 2.2. Bentuk umum tabel Simpleks Cj Variabel basis X B1
Harga basis C B1
X B2 . . . .
C B2 . . . . .
X Bm C Bm C j -Z j
C1
C2
..........................
Cn
X1
X2
..........................
Xn
a 11
a 12
.........................
a 1n
Jawab basis b1
a 21 . . . . . . a m1 C 1 -Z 1
a 22 . . . . . . a m2 C 2 -Z 2
......................... . . . . . . .......................... ..........................
a 2n . . . . . . a mn C n -Z n
b2 . . . . . . bm fm
2.6 Model Linear Programming
Sebagai langkah awal dalam merumuskan model program linier, harus terlebih dahulu ditentukan variabel-variabel keputusan. Penandaan suatu aktivitas dengan angka node awal dan akhirnya, maka suatu aktivitas yang dimulai pada node 1 dan berakhir pada node 2 disebut sebagai aktivitas 1→ 2 . Penandaan seperti ini akan digunakan sebagai penandaan yang sama untuk menentukan variabel-variabel keputusan dari program linear. Untuk aktivitas i → j , waktu untuk kejadian i akan sebesar xi , dan waktu untuk kejadian j akan sebesar x j .
Tujuan dari jaringan proyek adalah untuk menentukan waktu tercepat suatu proyek dapat diselesaikan (waktu garis edar kritis). Waktu garis edar kritis merupakan waktu tercepat kejadian node terakhir. Jika xm adalah waktu tercepat kejadian node terakhir dalam jaringan kerja, ditunjuk pada node m , maka fungsi objektif dapat dinyatakan sebagai : Minimum Z = xm ...........................................................................................(2.3)
Universitas Sumatera Utara
Selanjutnya dapat dikembangkan hambatan model tersebut. Pertama, menentukan waktu aktivitas i → j sebagai t ij , dimana perbedaan antara waktu kejadian pada node j dan waktu kejadian pada node i harus paling tidak sama dengan waktu aktivitas t ij . Sebuah kumpulan hambatan yang menyatakan kondisi adalah : x j − xi ≥ t ij
Model umum program linear untuk perumusan jaringan CPM ini dapat dirangkum sebagai Minimum Z = xm Dengan kendala x j − xi ≥ t ij untuk seluruh aktivitas i → j xi , x j ≥ 0
Diketahui xi
= waktu kejadian pada node i
xj
= waktu kejadian pada node j
t ij
= waktu aktivitas i → j
m
= node terakhir dalam jaringan
Solusi untuk model program linear ini akan mengindikasikan waku tercepat kejadian setiap simpul dalam jaringan serta lamanya waktu proyek tersebut.
2.7 Penentuan Biaya Dalam CPM
Selain CPM dapat digunakan untuk menentukan waktu paling cepat sebuah proyek dapat terselesaikan dan mengidentifikasi waktu kelonggaran (Slack) paling lambat sebuah kegiatan dapat dimulai tanpa menghambat jadwal proyek keseluruhan, metode ini juga mampu melakukan analisis terhadap sumber daya yang dipakai dalam proyek (biaya) agar jadwal yang dihasilkan akan jauh lebih optimal dan ekonomis.
Suatu proyek menggambarkan hubungan antara waktu terhadap biaya. Perlu dicatat bahwa, biaya disini merupakan biaya langsung misalnya biaya tenaga kerja,
Universitas Sumatera Utara
pembelian material dan peralatan) tanpa memasukkan biaya tidak langsung seperti biaya administrasi, dan lain-lain. Adapun istilah-istilah dari hubungan antara waktu penyelesaian proyek dengan biaya yang dikeluarkan adalah sebagai berikut:
1. Waktu Normal Adalah waktu yang diperlukan bagi sebuah proyek untuk melakukan rangkaian kegiatan sampai selesai tanpa ada pertimbangan terhadap penggunaan sumber daya.
2. Biaya Normal Adalah biaya langsung yang dikeluarkan selama penyelesaian kegiatan-kegiatan proyek sesuai dengan waktu normalnya.
3. Waktu Dipercepat Waktu dipercepat atau lebih dikenal dengan Crash Time adalah waktu paling singkat untuk menyelesaikan seluruh kegiatan yang secara teknis pelaksanaannnya masing mungkin dilakukan. Dalam hal ini penggunaan sumber daya bukan hambatan.
4. Biaya untuk Waktu Dipercepat Atau Crash Cost merupakan biaya langsung yang dikeluarkan untuk menyelesaikan kegiatan dengan waktu yang dipercepat.
2.8. Waktu Aktivitas Crashing
Waktu yang sudah dicapai dalam penjadwalan suatu proyek merupakan waktu normal. Namun waktu normal ini masih dapat diperpendek lagi guna mencapai waktu penyelesaian yang paling singkat. Usaha untuk memperpendek waktu aktivitas ini disebut Crashing. Untuk mencapai waktu crashing ini biasanya akan menambah sumber daya seperti tenaga kerja dan lembur, sehingga akan memperbanyak biaya proyek. Semakin cepat suatu proyek selesai maka semakin banyak biaya yang dibutuhkan untuk menyelesaikan proyek tersebut. Oleh karena penambahan sumber daya dengan aktivitas crashing biasanya menghasilkan tambahan biaya proyek, maka
Universitas Sumatera Utara
perlu mengidentifikasi aktivitas yang paling sedikit biayanya untuk dicrash dan kemudian meng-crash aktivitas itu hanya sejumlah yang diperlukan untuk memenuhi waktu penyelesaian proyek yang diinginkan.
Untuk menentukan dimana dan berapa banyak crash waktu aktivitas, maka diperlukan informasi mengenai berapa banyak setiap aktivitas dapat dicrash dan berapa banyak biaya proses crashing itu.
Untuk mendapatkan informasi ini, maka perlu mengistemasi biaya aktivitas di bawah waktu normal, mengistemasi waktu untuk menyelesaikan aktivitas itu dengan crashing maksimum.
Tujuan pokok untuk mempercepat waktu penyelesaian adalah memperpendek waktu penyelesaian proyek dengan kenaikan biaya yang seminimal mungkin. Proses mempercepat waktu penyelesaian proyek dinamakan Crash Program. Akan tetapi, terdapat batas waktu percepatan (crash time) yaitu suatu batas dimana dilakukan pengurangan waktu melewati batas waktu ini akan tidak efektif lagi.
Anggaplah
t ij
= waktu normal untuk aktivitas i → j
tcij
= waktu untuk aktivitas i → j dengan crashing masksimum
τ ij
= kemungkinan maksimum pengurangan waktu untuk aktivitas i → j karena crashing maksimum
Dengan t ij dan tcij diketahui, maka τ ij dapat dihitung sebagai berikut :
τ ij
= t ij - tcij ..............................................................................(2.4)
Berikut jika dianggap : C ij
= menyatakan biaya untuk aktivitas i → j dalam waktu normal.
Ccij
= menyatakan biaya dengan aktivitas i → j dengan crashing maksimum.
Universitas Sumatera Utara
Jadi berdasarkan waktu per unit, biaya crashing (S ij ) untuk setiap aktivitas adalah : S ij
=
Ccij − C ij
τ ij
.......................................................................................(2.5)
Biaya B Titik Dipercepat
Biaya untuk waktu dipercepat
A Titik Normal
Biaya Normal
Waktu Dipercepat
Waktu Waktu Normal
Gambar 2.4. Hubungan antara waktu dan biaya pada keadaan normal dan crash
Dengan menggunakan crash schedule, tentu saja biayanya akan jauh lebih besar dibandingkan dengan normal schedule. Dalam crash schedule akan dipilih kegiatan-kegiatan kritis dengan tingkat kemiringan terkecil untuk mempercepat pelaksanaannya. Langkah ini dilakukan sampai seluruh kegiatan mencapai nilai crash time-nya. Perhitungan yang dilakukan untuk menentukan sudut kemiringan (waktu dan biaya suatu kegiatan) atau lebih dikenal dengan slope adalah:
Biaya Dipercepat – Biaya Normal Slope Biaya = Waktu Normal – Waktu Dipercepat
Universitas Sumatera Utara
2.8.1. Crashing Dengan Model Linear Programming
Untuk jaringan yang besar maka diperlukan prosedur matematis untuk menentukan keputusan crashing optimal. Dalam hal ini pemograman linear dapat digunakan untuk menyelesaikan masalah crashing jaringan. Hal pertama yang dikerjakan dalam menentukan keputusan crashing adalah menentukan variabel-variabel keputusan sebagai berikut : xi
= waktu terjadinya peristiwa i
xj
= waktu terjadinya peristiwa j
xm
= waktu terjadinya peristiwa paling akhir (m )
t ij
= waktu kegiatan i → j
tcij
= waktu crashing maksimum kegiatan i → j
τ ij
= kemungkinan maksimum pengurangan waktu untuk aktivitas i → j karena crashing maksimum
C ij
= menyatakan biaya untuk aktivitas i → j dalam waktu normal.
Ccij
= menyatakan biaya dengan aktivitas i → j dengan crashing maksimum
S i→ j
= Slope biaya untuk kegiatan i → j
i, j
= node (1,2,3,...)
Dimana i → j = nama kegiatan (A,B,C,...)
Oleh karena tujuan yang terutama adalah memperpendek atau mempersingkat waktu penyelesaian proyek dengan meminimalkan biaya crashing, maka fungsi tujuan program linearnya adalah : Min ∑ S mτ m .................................................................................................(2.6) m
Dimana S ij = biaya crash untuk kegiatan i → j berdasarkan waktu per unit. Dan yang menjadi fungsi kendala adalah waktu maksimum untuk crashing.
Universitas Sumatera Utara
Untuk kendala yang menjelaskan struktur jaringan, dimulai dari event i dengan asumsi bahwa xi = 0 Untuk event berikutnya x j ≥ t A − τ A + xi xk ≥ t B − τ B + x j
. . . x m ≥ t Z −τ Z + x m −1 Selanjutnya dengan dengan menggunakan metode simpleks dapat diperoleh jawaban optimalnya.
Kendala untuk model ini mencakup penggambaran jaringan kerja dan pembatasan waktu crash aktivitas. Dari semua ini, kendala yang digunakan untuk menggambarkan jaringan mungkin merupakan kendala yang paling sulit. Kendala kendala itu didasarkan pada persyaratan berikut ini : 1. waktu terjadinya peristiwa i
( xi )
harus lebih besar daripada atau sama dengan
waktu penyelesaian aktivitas untuk semua aktivitas yang menuju node atau peristiwa itu. 2. waktu awal suatu aktivitas sama dengan waktu terjadinya node atau peristiwa pendahulunya. 3. waktu untuk menyelesaikan satu waktu aktivitas adalah sama dengan waktu normalnya dikurang panjang waktu yang dicrash. Dengan menambah batasan bahwa x m ≥ 0 maka dapat dicari waktu crashing optimal dengan menggunakan metode simpleks.
Sebagai contoh diambil sebuah jaringan kerja pembangunan sebuah ruko, dimana akan dicari waktu percepatan optimalnya dengan menggunakan metode simpleks.
Universitas Sumatera Utara
Contoh 2
Tabel 2.3. Logika ketergantungan Pembangunan Ruko Kode
Nama Kegiatan
Waktu
Kegiatan yang mendahului
(hari) A
Pembersihan
7
-
B
Dinding
6
-
C
Atap
8
A
D
Lantai
5
B
E
Cat + Keramik
7
C, D
Dengan estimasi biaya pembangunan ruko adalah sebagai berikut :
Tabel 2.4. Estimasi biaya Kode
Nama kegiatan
Waktu normal Waktu (hari)
Biaya normal
Crash
crashing max Rp. (.000)
cost/hari
(hari)
Rp. (.000)
A
Pembersihan
7
3
800
200
B
Dinding
6
2
1200
300
C
Atap
8
3
500
100
D
Lantai
5
2
360
120
E
Cat + keramik
7
3
600
150
Penyelesaian:
Berdasarkan Tabel Logika ketergantungan diatas maka dapat digambarkan jaringan kerjanya sebagai berikut :
Universitas Sumatera Utara
A
1
7
2
7
C
7
8
0
4
0 B
15
E
15
7
5
22 22
6 3
6
D
10
5
Gambar 2.5. Jaringan kerja pembangunan ruko
(i) Penentuan Jalur Kritis Perhitungan maju - ES1 = 0 - ES 2 = maks (ES1 + D A ) = maks (0 + 7) =7 - ES 3 = maks (ES1 + DB ) = maks (0 + 8) =8 - ES 4 = maks (ES 2 + DC , ES 3 + DD ) = maks (7 + 8, 6 + 5) = maks (15,11) = 15 - ES 5 = maks (ES 4 + DE ) = maks (15 + 7) = 22
Perhitungan mundur - LF5 = ES 5 = 22 - LF4 = min (LF5 − DE ) = min (22 – 7) = 15
Universitas Sumatera Utara
- LF3 = min (LF4 − DD ) = min (15 – 5) = 10 - LF2 = min (LF4 − DC ) = min (15 – 8) =7 - LF1 = min (LF3 − DB , LF2 − D A ) = min (10 − 6, 7 − 7 ) =0 Dengan menggunakan formulasi (2.2) yaitu : ES j − ES i = LF j − LFi = Dij
Maka yang menjadi jalur kritis pada jaringan kerja pembangunan ruko adalah : A–C–E
A
1
7
2
7
C
7
8
0
4
0 B
15
E
15
7
5 22 22
6 3
6
D
10
5
Gambar. 2.6. Jalur kritis Pembangunan ruko
(ii) Penentuan Biaya Crashing Optimum dengan menggunakan pendekatan Program Linear. Data dari tabel dan gambar yang dilengkapi dengan informasi waktu penyelesaian, dapat digunakan untuk memformulasikan model linear programming. Jika xi adalah waktu yang yang dibutuhkan untuk menyelesaikan event - i , dan τ j adalah waktu percepatan yang dapat dilakukan pada aktivitas j , maka untuk proyek pada contoh diatas dapat diformulasikan :
Universitas Sumatera Utara
Min Z = 200.000 τ A + 300.000 τ B + 100.000 τ C + 120.000 τ D + 150.000 τ E Dengan kendala
τ A ≤3 τB ≤2 τC ≤3 τD ≤2 τ E ≤3
kendala selisih normal time dan crash time
x6 ≤13 → kendala batas waktu percepatan Untuk kendala yang menjelaskan struktur jaringan, dimulai dari event -1 dengan asumsi bahwa x1 = 0 Untuk event – 2 :
x2
0 τA waktu normal + Waktu awal untuk ≥ (waktu percepatan ) aktivitas A aktivitas A (x 1 = 0 )
x2
≥ 7- τA +0
atau x 2 + τ A - x1 ≥ 7
Untuk event – 3 : x3
≥ 6 −τ B + 0
atau x3 + τ B − x1 ≥ 6
Untuk event – 4, dibutuhkan dua kendala, yaitu jalur aktivitas C dan jalur aktivitas D :
x4
≥ 8 −τ C + x 2
atau x 4 + τ C − x 2 ≥ 8
x4
≥ 5 − τ D + x3
atau x 4 + τ D − x3 ≥ 5
Untuk event – 5 : x5
≥ 7 −τ E + x4
atau x5 + τ E − x 4 ≥ 7
Dengan menambah batasan x1 , x 2 , x3 , x 4 , x5 ≥ 0 , maka dengan menggunakan metode simpleks waktu yang optimal untuk percepatan akan didapat.
Universitas Sumatera Utara
Tabel 2.5. Tabel Simpleks pertama (pendahuluan)
τ A τB τC τD
τE
x1
x2
x3
x 4 x5
s1
s2
s3
C(j)
200
300
100
120
150
0
0
0
0
0
0
0
s1 s2 s3
0
1
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
s4 s5
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
s6
0
0
0
0
0
0
0
A7
M
0
0
0
0
0
A8
M
1
0
0
0
A9
M
0
1
0
A10
M
0
0
A11 A12 s13
M
0
M
Sol .
s 4 s5
s 6 A7 s8
A8 s9
A9 s10
A10 s11 A11 s12 A12 s13 s14 s15 s16 s17
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
13
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
7
0
0
-1
0
1
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
6
1
0
0
0
-1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
8
0
0
1
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
5
0
0
0
0
1
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
7
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
s14 s15
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
s16
0
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
s17
0
0
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
C(j) – Z(j)
200
300
100
120
150
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
M
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
basis
Universitas Sumatera Utara
Tabel 2.6. Tabel Simpleks kedua
τ A τ B τ C τ D τ E x1 x 2 x3
x 4 x5 s1
C(j)
200
300
100
120
150
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
s4 s5
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
s6
0
0
0
0
0
0
0
0
A7
M
0
0
0
0
0
1
A8
M
1
0
0
0
0
A9
M
0
1
0
0
A10
M
0
0
1
A11 A12 s13
M
0
0
M
0
0
s14 s15
s 2 s3 s 4
s5
s6
A7 s8
A8 s9
A9
s10 A10 s11 A11 s12
A12 s13 s14 s15 s16 s17
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Sol.
Ras.
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
M
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
M
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
13
M
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
M
-1
1
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
7
M
0
-1
0
1
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
6
M
0
0
0
-1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
8
8
0
1
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
5
5
0
0
0
1
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
7
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
M
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
M
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
M
s16
0
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
s17
0
0
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
M
C(j) – Z(j)
200
300
100
120
150
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
M
-1
-1
-1
-1
-1
1
0
0
-1
-1
0
0
0
0
0
0
0
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
33
basis
s1 s2 s3
Masuk :
x 4 ; keluar A11
Universitas Sumatera Utara
Tabel 2.7. Tabel Simpleks ketiga
τ A τB τC τD τE
x1 x 2 x3 x 4 x5 s1 s 2 s3
s 4 s5 s 6 A7
s8
A8 s9
A9 s10 A10 s11 A11
s12 A12 s13 s14 s15 s16 s17
C(j)
200
300
100
120
150
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Sol.
Ras.
s1 s2 s3
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
M
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
s4 s5
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
M
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
s6
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
13
M
A7
M
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
M
A8
M
1
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
7
M
A9
M
0
1
0
0
0
-1
0
1
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
6
6
A10
M
0
0
1
-1
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
3
3
x4 A12 s13
0
0
0
0
1
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
-1
0
0
0
0
0
0
0
5
5
M
0
0
0
1
1
0
0
-1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
-1
1
0
0
0
0
0
12
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
1
0
0
0
0
0
M
s14 s15
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
M
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
M
s16
0
0
0
0
1
0
0
0
-1
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
1
0
5
0
s17
0
0
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
M
C(j) – Z(j)
200
300
100
120
150
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
M
-1
-1
-1
0
-1
1
0
-1
0
-1
0
0
0
0
0
0
0
1
0
1
0
1
0
0
1
1
0
0
0
0
0
0
28
basis
Masuk :
x3 ; keluar A10
Universitas Sumatera Utara
Tabel 2.8. Tabel Simpleks keempat
τ A τB τC τD τE
x1
x 2 x3 x 4 x5 s1
C(j)
200
300
100
120
150
0
0
0
0
0
s1 s2 s3
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
s4 s5
0
0
0
0
1
0
0
0
0
0
0
0
1
s6
0
0
0
0
0
A7
M
0
0
0
A8
M
1
0
A9
M
0
x3
0
x4 A12 s13
s2
s3 s 4
s5 s 6 A7 s8
A8 s9
A9
s10 A10 s11 A11 s12 A12 s13 s14 s15 s16 s17
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Sol
Ras.
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
M
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
M
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
13
M
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
M
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
7
7
1
-1
1
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
1
-1
-1
-1
0
0
0
0
0
0
0
3
3
0
0
1
-1
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
1
1
0
0
0
0
0
0
0
3
3
0
0
0
1
0
0
0
-1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
8
5
M
0
0
1
0
1
0
-1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
-1
1
0
0
0
0
0
15
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
M
s14 s15
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
M
0
0
0
1
-1
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
1
-1
0
0
0
0
1
0
0
3
M
s16
0
0
0
1
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
1
0
8
0
s17
0
0
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
M
C(j) – Z(j)
200
300
100
120
150
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
M
-1
-1
0
-1
-1
1
-1
0
0
-1
0
0
0
0
0
0
0
1
0
1
0
0
1
1
0
1
0
0
0
0
0
0
25
basis
Masuk :
x2 ; keluar A9
Universitas Sumatera Utara
Tabel 2.9. Tabel Simpleks kelima
τ A τB τC τD τE
x1 x 2 x3 x 4 x5
C(j)
200
300
100
120
150
0
0
0
0
s1 s2 s3
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
s4 s5
0
0
0
0
1
0
0
0
0
0
0
s6
0
0
0
0
A7
M
0
0
A8
M
1
x2 x3
0
x4 A12 s13
s1
s2
s3 s 4
s5
s6
A7 s8
A8 s9 A9 s10 A10 s11 A11 s12 A12 s13 s14 s15 s16 s17
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Sol.
Ras.
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
M
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
M
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
13
13
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
M
-1
1
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
1
-1
-1
1
1
-1
0
0
0
0
0
0
0
4
M
0
1
-1
1
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
1
-1
-1
1
0
0
0
0
0
0
0
3
M
0
0
1
0
0
0
-1
0
1
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
6
M
0
0
1
0
1
0
-1
0
0
1
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
-1
1
0
0
0
0
0
0
0
11
M
M
0
1
0
1
1
-1
0
0
0
1
0
0
0
0
0
0
0
0
0
-1
1
0
0
-1
1
-1
1
0
0
0
0
0
18
18
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
M
s14 s15
0
0
1
-1
1
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
1
-1
-1
1
0
0
0
1
0
0
0
3
M
0
0
1
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
1
0
0
6
M
s16
0
0
1
0
1
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
-1
1
0
0
0
0
0
1
0
11
M
s17
0
0
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
M
C(j) – Z(j)
200
300
100
120
150
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
M
-1
0
-1
0
-1
0
0
0
0
-1
0
0
0
0
0
0
0
1
0
0
1
1
0
0
1
1
0
0
0
0
0
0
22
basis
Masuk :
x5 ; keluar s6
Universitas Sumatera Utara
Tabel 2.10. Tabel Simpleks keenam
τ A τB τC τD τE
x1 x 2 x3 x 4 x5 s1 s 2 s3 s 4 s5 s 6
A7 s8
A8
s9
A9 s10 A10 s11 A11 s12 A12 s13 s14 s15 s16
s17
C(j)
200
300
100
120
150
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Sol.
Ras.
s1 s2 s3
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
M
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
3
s4 s5
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
M
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
x5
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
13
M
A7
M
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
M
A8
M
1
-1
1
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
1
-1
-1
1
1
-1
0
0
0
0
0
0
0
4
4
x2 x3
0
0
1
-1
1
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
1
-1
-1
1
0
0
0
0
0
0
0
3
M
0
0
1
0
0
0
-1
0
1
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
6
M
x4 A12 s13
0
0
1
0
1
0
-1
0
0
1
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
-1
1
0
0
0
0
0
0
0
11
M
M
0
1
0
1
1
-1
0
0
0
0
0
0
0
0
0
-1
0
0
0
-1
1
0
0
-1
1
-1
1
0
0
0
0
0
5
M
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
M
0
0
1
-1
1
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
1
-1
-1
1
0
0
0
1
0
0
0
3
M
0
0
1
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
1
0
0
6
M
s16
0
0
1
0
1
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
-1
1
0
0
0
0
0
1
0
11
M
s17
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
13
M
C(j) – Z(j)
200
300
100
120
150
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
M
-1
0
-1
0
-1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
1
0
0
1
1
0
0
0
0
0
0
9
basis
s14 s15
Masuk :
τ C ; keluar s3
Universitas Sumatera Utara
Tabel 2.11. Tabel Simpleks ketujuh
τ A τB τC τD τE
x1 x 2 x3 x 4 x5 s1
s 2 s3
s 4 s5
s 6 A7 s8 A8
s9 A9 s10 A10 s11 A11 s12 A12 s13
s14 s15 s16 s17
C(j)
200
300
100
120
150
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Sol.
Ras.
s1 s2
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
M
τC s4
100
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
M
s5
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
3
x5
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
13
M
A7
M
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
M
A8
M
1
-1
0
-1
0
0
0
0
0
0
0
0
-1
0
0
0
0
-1
1
1
-1
-1
1
1
-1
0
0
0
0
0
0
0
1
4
x2 x3
0
0
1
0
1
0
-1
1
0
0
0
0
0
1
0
0
0
0
0
0
-1
1
1
-1
-1
1
0
0
0
0
0
0
0
6
M
0
0
1
0
0
0
-1
0
1
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
6
M
x4 A12 s13
0
0
1
0
1
0
-1
0
0
1
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
-1
1
0
0
0
0
0
0
0
11
M
M
0
1
0
1
1
-1
0
0
0
0
0
0
0
0
0
-1
0
0
0
-1
1
0
0
-1
1
-1
1
0
0
0
0
0
5
5
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
M
s14 s15
0
0
1
0
1
0
-1
0
0
0
0
0
0
1
0
0
0
0
0
0
-1
1
1
-1
-1
1
0
0
0
1
0
0
0
6
M
0
0
1
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
1
0
0
6
M
s16
0
0
1
0
1
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
-1
1
0
0
0
0
0
1
0
11
M
s17
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
13
M
C(j) – Z(j)
200
300
0
120
150
0
0
0
0
0
0
0
-100
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
300
M
-1
0
0
0
-1
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
1
1
0
0
1
1
0
0
0
0
0
0
6
basis
Masuk :
τ E ; keluar s5
Universitas Sumatera Utara
Tabel 2.12. Tabel Simpleks kedelapan
τ A τ B τ C τ D τ E x1 x 2 x3 x 4 x5 s1 s 2 s3
s4
s5
s6
A7 s8
A8 s9
A9 s10 A10 s11 A11 s12
A12 s13 s14 s15 s16 s17
C(j)
200
300
100
120
150
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Sol.
Ras.
s1 s2
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
3
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
M
τC s4 τE
100
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
M
150
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
x5
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
13
M
A7
M
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
M
A8
M
1
-1
0
-1
0
0
0
0
0
0
0
0
-1
0
0
0
0
-1
1
1
-1
-1
1
1
-1
0
0
0
0
0
0
0
1
1
x2 x3
0
0
1
0
1
0
-1
1
0
0
0
0
0
1
0
0
0
0
0
0
-1
1
1
-1
-1
1
0
0
0
0
0
0
0
6
M
0
0
1
0
0
0
-1
0
1
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
6
M
0
0
1
0
1
0
-1
0
0
1
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
-1
1
0
0
0
0
0
0
0
11
M
M
0
1
0
1
0
-1
0
0
0
0
0
0
0
0
-1
-1
0
0
0
-1
1
0
0
-1
1
-1
1
0
0
0
0
0
2
M
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
M
s14 s15
0
0
1
0
1
0
-1
0
0
0
0
0
0
1
0
0
0
0
0
0
-1
1
1
-1
-1
1
0
0
0
1
0
0
0
6
M
0
0
1
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
1
0
0
6
M
s16
0
0
1
0
1
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
-1
1
0
0
0
0
0
1
0
11
M
s17
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
13
M
C(j) – Z(j)
200
300
0
120
0
0
0
0
0
0
0
0
-100
0
-150
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
750
M
-1
0
0
0
0
0
0
0
0
0
0
0
1
0
1
1
0
1
0
0
1
1
0
0
1
1
0
0
0
0
0
0
3
basis
x4 A12 s13
Masuk :
τ A ; keluar A8
Universitas Sumatera Utara
Tabel 2.13. Tabel Simpleks kesembilan
τ A τ B τ C τ D τ E x1 x 2 x3 x 4 x5 s1 s 2 s3
s 4 s5
s6
A7 s8
A8
s9
C(j)
200
300
100
120
150
0
0
0
0
0
0
0
0
0
0
0
0
0
0
s1 s2
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
τC
100
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
s4
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
τE
150
0
0
0
0
1
0
0
0
0
0
0
0
0
0
x5
0
0
0
0
0
0
0
0
0
0
1
0
0
0
A7
M
0
0
0
0
0
1
0
0
0
0
0
0
τA x2
200
1
-1
0
-1
0
0
0
0
0
0
0
0
0
1
0
1
0
-1
1
0
0
0
x3
0
0
1
0
0
0
-1
0
1
0
x4 A12 s13
0
0
1
0
1
0
-1
0
0
M
0
1
0
1
0
-1
0
0
0
0
0
0
0
-1
s14 s15
0
0
1
0
1
0
0
0
1
0
0
s16
0
0
1
0
s17
0
0
0
C(j) – Z(j)
0
M
0
A9 s10 A10 s11
A11 s12 A12 s13 s14 s15 s16 s17
0
0
0
0
0
0
0
0
0
0
0
0
0
Sol.
Ras.
-1
-1
1
1
-1
-1
1
0
0
0
0
0
0
0
2
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
M
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
M
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
13
M
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
M
0
-1
0
0
0
0
-1
1
1
-1
-1
1
1
-1
0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
0
0
-1
1
1
-1
-1
1
0
0
0
0
0
0
0
6
6
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
6
M
1
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
-1
1
0
0
0
0
0
0
0
11
11
0
0
0
0
0
0
0
-1
-1
0
0
0
-1
1
0
0
-1
1
-1
1
0
0
0
0
0
2
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
M
-1
0
0
0
0
0
0
1
0
0
0
0
0
0
-1
1
1
-1
-1
1
0
0
0
1
0
0
0
6
6
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
1
0
0
6
M
1
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
-1
1
0
0
0
0
0
1
0
11
11
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
13
M
500
0
320
0
0
0
0
0
0
0
0
100
0
-150
0
0
200
-200
-200
200
200
-200
-200
200
0
0
0
0
0
0
0
950
-1
0
-1
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
0
0
1
1
0
1
0
0
0
0
0
0
2
basis
Masuk :
τ D ; keluar s1
Universitas Sumatera Utara
Tabel 2.14. Final tabel
τ A τ B τ C τ D τ E x1
x2
x3 x 4 x5 s1
s 2 s3
s 4 s5
s 6 A7 s8
A8 s9
A9
s10
C(j)
200
300
100
120
150
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Sol.
τD
120
0
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
1
-1
-1
1
1
-1
-1
1
0
0
0
0
0
0
0
2
s2
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
τC s4 τE
100
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
0
-1
0
0
0
0
0
0
0
0
-1
0
-1
1
0
0
0
-1
1
1
-1
-1
1
1
-1
0
0
0
0
0
0
0
0
150
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
x5
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
13
A7
M
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
τA
200
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
x2 x3
0
0
0
0
0
0
-1
1
0
0
0
-1
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
1
0
0
0
-1
0
1
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
6
0
0
0
0
0
0
-1
0
0
1
0
-1
0
-1
0
0
0
0
-1
1
0
0
-1
1
0
0
0
0
0
0
0
0
0
9
M
0
0
0
0
0
-1
0
0
0
0
-1
0
-1
0
-1
-1
0
-1
1
0
0
-1
1
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
s14 s15
0
0
0
0
0
0
-1
0
0
0
0
-1
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
4
0
0
1
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
0
0
1
0
0
6
s16
0
0
0
0
0
0
-1
0
0
0
0
-1
0
-1
0
0
0
0
-1
1
0
0
-1
1
0
0
0
0
0
0
0
1
0
9
s17
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
13
C(j) – Z(j)
0
180
0
0
0
0
0
0
0
0
-320
0
-220
0
-150
0
0
-120
120
120
-120
-120
120
120
-120
0
0
0
0
0
0
0
1590
M
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
1
0
1
0
0
1
1
0
0
1
1
0
0
0
0
0
0
0
A10 s11 A11 s12 A12 s13 s14 s15 s16 s17
basis
x4 A12 s13
Universitas Sumatera Utara
Dengan penggunaan metode simpleks diatas maka didapat : • τ A =3 • τ B =0 • τC =3 • τD =2 • τ E =3 Min Z = Rp. 1.590.000 Maka penambahan biaya untuk percepatan peroyek adalah sebesar Rp. 1.590.000,dengan waktu pengerjaan proyek setelah dipercepat adalah selama 16 hari.
Universitas Sumatera Utara
