Linear Programming and Transportation Methods in Operations Research

Slide1  6s-1Linear Programming William J. Stevenson Operations Management 8 th  edition OPERATIONS RESEARCH OPERATIONS RESEARCH Rosihan  A smara Rosihan  A smara http://lecture.brawijaya.ac.id/rosihan http://rosihan.com http://lecture.brawijaya.ac.id/rosihan http://rosihan.com

Slide2  6s-2Linear Programming METODE  TRANSPORTASI METODE  TRANSPORTASI suatu  metode  yang  digunakan  untuk  mengatur  distribusi  dari sumber-sumber  yang  menyediakan  produk  yang  sama,  ke tempat-tempat  yang  membutuhkan  secara  optimal suatu  metode  yang  digunakan  untuk  mengatur  distribusi  dari sumber-sumber  yang  menyediakan  produk  yang  sama,  ke tempat-tempat  yang  membutuhkan  secara  optimal

Slide3  6s-3Linear Programming Metode  Stepping-Stone Metode  Stepping-Stone  Suatu perusahaan yang mempunyai 3 buah pabrik di W, H, P. Perusahaan menghadapi masalah alokasi hasil produksinya dari pabrik-pabrik tersebut ke gudang- gudang penjualan di A, B, C Contoh  : Contoh  :

Slide4  6s-4Linear Programming Tabel  Kapasitas  pabrik Tabel  Kapasitas  pabrik Pabrik Kapasitas produksi tiap bulan W 90 ton H 60 ton P 50 ton Jumlah 200 ton

Slide5  6s-5Linear Programming Tabel  Kebutuhan  gudang Tabel  Kebutuhan  gudang Gudang Kebutuhan tiap bulan A 50 ton B 110 ton C 40 ton Jumlah 200 ton

Slide6  6s-6Linear Programming Tabel  Biaya  pengangkutan  setiap  ton dari  pabrik  W,  H,  P,  ke  gudang  A,  B,  C Tabel  Biaya  pengangkutan  setiap  ton dari  pabrik  W,  H,  P,  ke  gudang  A,  B,  C Dari Biaya tiap ton (dalam ribuan Rp) Ke gudang  A Ke gudang  B Ke gudang  C Pabrik  W 20 5 8 Pabrik H 15 20 10 Pabrik P 25 10 19

Slide7  6s-7Linear Programming Penyusunan  Tabel  Alokasi Penyusunan  Tabel  Alokasi 1. jumlah  kebutuhan  tiap-tiap  gudang diletakkan  pada  baris  terakhir 2. kapasitas  tiap  pabrik  pada  kolom  terakhir 3. biaya  pengangkutan  diletakkan  pada  segi empat  kecil Gudang A Gudang B Gudang C Kapasitas Pabrik Pabrik X 11 20 X 12 5 X 13 8 90 W Pabrik X 21 15 X 22 20 X 23 10 60 H Pabrik X 31 25 X 32 10 X 33 19 50 P Kebutuhan Gudang 50 110 40 200 Ke Dari A A t t u u r r a a n n

Slide8  6s-8Linear Programming Penggunaan  Linear  Programming  dalam Metode  Transportasi Penggunaan  Linear  Programming  dalam Metode  Transportasi Gudang A Gudang B Gudang C Kapasitas Pabrik Pabrik X 11 20 X 12 5 X 13 8 90 W Pabrik X 21 15 X 22 20 X 23 10 60 H Pabrik X 31 25 X 32 10 X 33 19 50 P Kebutuhan Gudang 50 110 40 200 Ke Dari Tabel Alokasi Minimumkan Z = 20 X WA  + 15X HA  + 25X PA  + 5X WB  + 20X HB  + 10X PB  +   8X WC  + 10X HC  + 19X PC Batasan X WA  + X WB  + X WC  = 90  X WA  + X HA  + X PA  = 50 X HA  + X HB  + X HC    = 60  X WB  + X HB  + X PB  = 110 X PA  + X PB  + X PC    = 50  X WC  + X HC  + X PC  = 40

Slide9  6s-9Linear Programming Prosedur  Alokasi Prosedur  Alokasi 1. Mulai  dari  sudut  kiri  atas  dari  X 11   dialokasikan sejumlah  maksimum  produk  dengan  melihat kapasitas  pabrik  dan  kebutuhan  gudang 1. Mulai  dari  sudut  kiri  atas  dari  X 11   dialokasikan sejumlah  maksimum  produk  dengan  melihat kapasitas  pabrik  dan  kebutuhan  gudang 2. Kemudian  setelah  itu,  bila  X ij   merupakan  kotak terakhir  yang  dipilih  dilanjutkan  dengan mengalokasikan  pada  X i,j+1  bila  i  mempunyai kapasitas  yang  tersisa 2. Kemudian  setelah  itu,  bila  X ij   merupakan  kotak terakhir  yang  dipilih  dilanjutkan  dengan mengalokasikan  pada  X i,j+1  bila  i  mempunyai kapasitas  yang  tersisa 3. Bila  tidak,  alokasikan  ke  X i+1,j ,  dan  seterusnya sehingga  semua  kebutuhan  telah  terpenuhi 3. Bila  tidak,  alokasikan  ke  X i+1,j ,  dan  seterusnya sehingga  semua  kebutuhan  telah  terpenuhi 1. Mulai  dari  sudut  kiri  atas  dari  X 11   dialokasikan sejumlah  maksimum  produk  dengan  melihat kapasitas  pabrik  dan  kebutuhan  gudang 1. Mulai  dari  sudut  kiri  atas  dari  X 11   dialokasikan sejumlah  maksimum  produk  dengan  melihat kapasitas  pabrik  dan  kebutuhan  gudang 2. Kemudian  setelah  itu,  bila  X ij   merupakan  kotak terakhir  yang  dipilih  dilanjutkan  dengan mengalokasikan  pada  X i,j+1  bila  i  mempunyai kapasitas  yang  tersisa 2. Kemudian  setelah  itu,  bila  X ij   merupakan  kotak terakhir  yang  dipilih  dilanjutkan  dengan mengalokasikan  pada  X i,j+1  bila  i  mempunyai kapasitas  yang  tersisa 3. Bila  tidak,  alokasikan  ke  X i+1,j ,  dan  seterusnya sehingga  semua  kebutuhan  telah  terpenuhi 3. Bila  tidak,  alokasikan  ke  X i+1,j ,  dan  seterusnya sehingga  semua  kebutuhan  telah  terpenuhi pedoman  sudut  barat  laut (nortwest  corner  rule) . pedoman  sudut  barat  laut (nortwest  corner  rule) .

Slide10  6s-10Linear Programming Tabel  Alokasi  tahap  pertama dengan  pedoman  sudut  barat  laut Tabel  Alokasi  tahap  pertama dengan  pedoman  sudut  barat  laut Gudang A Gudang B Gudang C Kapasitas Pabrik Pabrik 20 5 8 90 W Pabrik 15 20 10 60 H Pabrik 25 10 19 50 P Kebutuhan Gudang 50 110 40 200 Ke Dari 50 40 60 10 40

Slide11  6s-11Linear Programming Metode  MODI (Modified  Distribution) Metode  MODI (Modified  Distribution) Formulasi R i   +  K j   =  C ij R i   +  K j   =  C ij R i = nilai baris i R i = nilai baris i K j = nilai kolom j K j = nilai kolom j C i j = biaya pengangkutan dari    sumber  i  ke tujuan  j C i j = biaya pengangkutan dari    sumber  i  ke tujuan  j

Slide12  6s-12Linear Programming Metode  MODI (Modified  Distribution) Metode  MODI (Modified  Distribution) 1. Isilah  tabel  pertama  dari  sudut  kiri  atas  ke  kanan  bawah 1. Isilah  tabel  pertama  dari  sudut  kiri  atas  ke  kanan  bawah 2. Menentukan  nilai  baris  dan  kolom   dengan  cara: 2. Menentukan  nilai  baris  dan  kolom   dengan  cara: • Baris   pertama  selalu  diberi  nilai  0 • Baris   pertama  selalu  diberi  nilai  0 • Nilai  baris  yang  lain  dan  nilai  semua  kolom  ditentukan berdasarkan  rumus  R i   +  K j   =  C ij . • Nilai  baris  yang  lain  dan  nilai  semua  kolom  ditentukan berdasarkan  rumus  R i   +  K j   =  C ij . Nilai  baris  W  =  R W   =  0 Nilai  baris  W  =  R W   =  0 Mencari  nilai  kolom  A: Mencari  nilai  kolom  A: R W   +  K A   =  C WA R W   +  K A   =  C WA 0    +   K A   =   20,    nilai  kolom  A  =   K A   =  20 0    +   K A   =   20,    nilai  kolom  A  =   K A   =  20 Mencari  nilai  kolom  dan  baris  yg  lain: Mencari  nilai  kolom  dan  baris  yg  lain: R W   +  K B   =  C WB ;   0   +   K B    =  5;    K B   =  5 R W   +  K B   =  C WB ;   0   +   K B    =  5;    K B   =  5 R H   +  K B   =  C HB ;   R H    +  5   =  20;    R H   =  15 R H   +  K B   =  C HB ;   R H    +  5   =  20;    R H   =  15 R P   +  K B   =  C PB ;   R P    +   5   =  10;    R P   =   5 R P   +  K B   =  C PB ;   R P    +   5   =  10;    R P   =   5 R P   +  K C   =  C PC ;   5   +   K C    =  19;    K C   =  14 R P   +  K C   =  C PC ;   5   +   K C    =  19;    K C   =  14 Langkah  Penyelesaian Langkah  Penyelesaian

Slide13  6s-13Linear Programming Tabel  Pertama Tabel  Pertama Gudang            A Gudang             B Gudang            C Kapasitas Pabrik Pabrik 20   5 8 90   W Pabrik 15 20 10 60    H Pabrik 25 10 19 50     P Kebutuhan Gudang 50 110 40 200 Ke Dari 50 40 60 10 40 =  0 = 15 = 5 = 20 = 5 = 14 R i  + K j  = C ij FORMULASI Baris  pertama  =  0 Baris  pertama  =  0 R W   +  K A   =  C WA R W   +  K A   =  C WA 0     +   K A   =  20;    K A   =  20 0     +   K A   =  20;    K A   =  20 R W   +  K B   =  C WB R W   +  K B   =  C WB 0   +   K B    =  5;    K B   =  5 0   +   K B    =  5;    K B   =  5 R H    +  K B   =  C HB R H    +  K B   =  C HB R H    +  5    =  20;    R H   =  15 R H    +  5    =  20;    R H   =  15 R P    +  K B   =  C PB R P    +  K B   =  C PB R P    +   5   =  10;    R P   =   5 R P    +   5   =  10;    R P   =   5 R P   +  K C  =  C PC ; R P   +  K C  =  C PC ; 5    +  K C    =  19;   K C   =  14 5    +  K C    =  19;   K C   =  14

Slide14  6s-14Linear Programming 3.   Menghitung  Indeks  perbaikan 3.   Menghitung  Indeks  perbaikan Indeks perbaikan adalah nilai dari segi empat air (segi empat yang kosong). Segi empat air C ij  - R i  - K j indeks perbaikan HA 15  –  15 - 20 -20 PA 25  –  5  –  20 0 WC 8  –  0  –  14 -6 HC 10  –  15  –  14 -19 Tabel Indeks Perbaikan : Rumus : C ij   C ij   -  -  R i   R i   -  -  K j   K j   =  =  indeks  indeks  perbaikan perbaikan

Slide15  6s-15Linear Programming 4.  Memilih  titik  tolak  perubahan 4.  Memilih  titik  tolak  perubahan Segi empat yang merupakan titik tolak perubahan adalah segi empat yang indeksnya bertanda  negatif  dan bertanda  negatif  dan angkanya  terbesar angkanya  terbesar yang memenuhi syarat adalah segi empat  HA  dan  dipilih sebagai segi empat yang akan diisi Segi empat air C ij  - R i  - K j indeks perbaikan HA 15  –  15 - 20 -20 PA 25  –  5  –  20 0 WC 8  –  0  –  14 -6 HC 10  –  15  –  14 -19

Slide16  6s-16Linear Programming 5.  Memperbaiki  alokasi 5.  Memperbaiki  alokasi 1. Berikan tanda positif pada     terpilih (HA) 2. Pilihlah 1     terdekat yang mempunyai isi dan sebaris (HB), 3. Pilihlah 1     terdekat yang mempunyai isi dan sekolom (WA); berilah tanda negatif keduanya 4. Pilihlah 1     sebaris atau sekolom dengan 2    yang bertanda negatif tadi (WB), dan berilah     ini tanda positif 5. Pindahkanlah alokasi dari     yang bertanda negatif ke yang bertanda positif sebanyak isi terkecil dari     yang bertanda positif (50) Jadi    HA kemudian berisi 50,    HB berisi 60 – 50 = 10,     WB berisi 40 + 50 = 90,    WA menjadi tidak berisi

Slide17  6s-17Linear Programming Tabel  Perbaikan  Pertama Tabel  Perbaikan  Pertama Gudang            A Gudang             B Gudang            C Kapasitas Pabrik Pabrik 20   5 8 90   W Pabrik 15 20 10 60    H Pabrik 25 10 19 50     P Kebutuhan Gudang 50 110 40 200 Ke Dari (-) (+) (+) (-) 50 40 90 50 60 10 10 40 =  0 = 15 = 5 = 20 = 5 = 14

Slide18  6s-18Linear Programming A)  Tabel  Pertama  Hasil  Perubahan A)  Tabel  Pertama  Hasil  Perubahan Gudang            A Gudang             B Gudang            C Kapasitas Pabrik Pabrik 20   5 8 90   W Pabrik 15 20 10 60    H Pabrik 25 10 19 50     P Kebutuhan Gudang 50 110 40 200 Ke Dari 90 50 10 10 40 =  0 = 15 = 5 = 20 = 5 = 14 Biaya transportasi = 90(5) + 50(15) + 10(20) + 10(10) + 40(19)  = 2260

Slide19  6s-19Linear Programming 6.  Ulangi  langkah-langkah  tersebut  mulai  langkah  nomor  2        sampai  diperoleh  biaya  terendah 6.  Ulangi  langkah-langkah  tersebut  mulai  langkah  nomor  2        sampai  diperoleh  biaya  terendah Tabel Kedua Hasil Perubahan Gudang            A Gudang             B Gudang            C Kapasitas Pabrik Pabrik 20   5 8 90   W Pabrik 15 20 10 60    H Pabrik 25 10 19 50     P Kebutuhan Gudang 50 110 40 200 Ke Dari (-) (+) (+) (-) 90 50 10 10 10 40 =  0 = 15 = 5 = 20 = 5 = 14 20 30

Slide20  6s-20Linear Programming B)  Tabel  Kedua  Hasil  Perubahan B)  Tabel  Kedua  Hasil  Perubahan Gudang            A Gudang             B Gudang            C Kapasitas Pabrik Pabrik 20   5 8 90   W Pabrik 15 20 10 60    H Pabrik 25 10 19 50     P Kebutuhan Gudang 50 110 40 200 Ke Dari 90 50 10 =  0 = 15 = 5 = 20 = 5 = 14 20 30 Biaya transportasi = 90(5) + 50(15) + 10(10) + 20(10) + 30(19)  = 2070

Slide21  6s-21Linear Programming C)  Tabel  Ketiga  Hasil  Perubahan C)  Tabel  Ketiga  Hasil  Perubahan Gudang            A Gudang             B Gudang            C Kapasitas Pabrik Pabrik 20   5 8 90   W Pabrik 15 20 10 60    H Pabrik 25 10 19 50     P Kebutuhan Gudang 50 110 40 200 Ke Dari (-) (+) (+) (-) 60 50 90 10 20 30 =  0 = 15 = 5 = 20 = 5 = 14 50 30 Biaya transportasi = 60(5) + 30(8) + 50(15) + 10(10) + 50(10)  = 1890

Slide22  6s-22Linear Programming D)  Tabel  Keempat  Hasil  Perubahan D)  Tabel  Keempat  Hasil  Perubahan Gudang            A Gudang             B Gudang            C Kapasitas Pabrik Pabrik 20   5 8 90   W Pabrik 15 20 10 60    H Pabrik 25 10 19 50     P Kebutuhan Gudang 50 110 40 200 Ke Dari 60 50 10 30 =  0 = 15 = 5 = 20 = 5 = 14 50 Segi empat air C ij  - R i  - K j indeks perbaikan WA 20 – 0 – 5 15 HB 20 – 2 – 5 13 PA 25 – 5 – 13 7 PC 19 – 5 – 8 6 Tabel Indeks perbaikan Tabel D. tidak bisa dioptimalkan lagi, karena indeks perbaikan tidak ada yang negatif

Slide23  6s-23Linear Programming TERIMAKASIH TERIMAKASIH

Slide24  6s-24Linear Programming TUGAS TUGAS  Pelajari  :  Metode  Vogel  atau  Vogel’s  Approximation Method  (VAM)

Slide25  6s-25Linear Programming Metode  Vogel’s  Approximation Metode  Vogel’s  Approximation Langkah-langkah  nya: Langkah-langkah  nya: 1. Susunlah  kebutuhan,  kapasitas  masing-masing  sumber,  dan  biaya pengangkutan  ke  dalam  matrik 1. Susunlah  kebutuhan,  kapasitas  masing-masing  sumber,  dan  biaya pengangkutan  ke  dalam  matrik 2. Carilah  perbedaan  dari  dua  biaya  terkecil  (dalam  nilai  absolut),  yaitu biaya  terkecil  dan  terkecil  kedua  untuk  tiap  baris  dan  kolom  pada matrik  (Cij) 2. Carilah  perbedaan  dari  dua  biaya  terkecil  (dalam  nilai  absolut),  yaitu biaya  terkecil  dan  terkecil  kedua  untuk  tiap  baris  dan  kolom  pada matrik  (Cij) 3. Pilihlah  1  nilai  perbedaan-perbedaan  yang  terbesar  di  antara  semua nilai  perbedaan  pada  kolom  dan  baris 3. Pilihlah  1  nilai  perbedaan-perbedaan  yang  terbesar  di  antara  semua nilai  perbedaan  pada  kolom  dan  baris 4. Isilah  pada  salah  satu  segi  empat  yang  termasuk  dalam  kolom  atau baris  terpilih,  yaitu  pada  segi  empat  yang  biayanya  terendah   di antara  segi  empat  lain  pada  kolom/baris  itu.  Isiannya  sebanyak mungkin  yang  bisa  dilakukan 4. Isilah  pada  salah  satu  segi  empat  yang  termasuk  dalam  kolom  atau baris  terpilih,  yaitu  pada  segi  empat  yang  biayanya  terendah   di antara  segi  empat  lain  pada  kolom/baris  itu.  Isiannya  sebanyak mungkin  yang  bisa  dilakukan

Slide26  6s-26Linear Programming Gudang Kapasitas Perbedaan baris A B C Pabrik W 20 5 8 90 H 15 20 10 60 P 25 10 19 50 Kebutuhan 50 110 40 Perbedaan Kolom Tabel  5.11.  Feasible  solution  mula-mula  dari  metode  VAM Tabel  5.11.  Feasible  solution  mula-mula  dari  metode  VAM 3 3 5 5 9 9 5 5 5 5 2 2 Pilihan  Pilihan  X PB   X PB   =  =  50 50 Hilangkan  Hilangkan  baris  baris  P P P mempunyai perbedaan baris/kolom terbesar dan B mempunyai biaya angkut terkecil

Slide27  6s-27Linear Programming Tabel  5.11.  Feasible  solution  mula-mula  dari  metode  VAM Tabel  5.11.  Feasible  solution  mula-mula  dari  metode  VAM 3 3 5 5 5 5 15 15 2 2 Pilihan  Pilihan  X WB   X WB   =  =  60 60 Hilangkan  Hilangkan  kolom  kolom  B B Kebutuhan  Gd  B  menjadi  60  krn  telah  diisi kapasitas  pabrik  P=50  (dihilangkan) Kebutuhan  Gd  B  menjadi  60  krn  telah  diisi kapasitas  pabrik  P=50  (dihilangkan) Gudang Kapasitas Perbedaan baris A B C Pabrik W 20 5 8 90 H 15 20 10 60 Kebutuhan 50 60 40 Perbedaan Kolom B mempunyai perbedaan baris/kolom terbesar dan W mempunyai biaya angkut terkecil

Slide28  6s-28Linear Programming Gudang Kapasitas Perbedaan baris A B C Pabrik W 20 8 30 H 15 10 60 Kebutuhan 50 40 Perbedaan Kolom Tabel  5.11.  Feasible  solution  mula-mula  dari  metode  VAM Tabel  5.11.  Feasible  solution  mula-mula  dari  metode  VAM 12 12 5 5 5 5 2 2 Pilihan  Pilihan  X WC   X WC   =  =  30 30 Hilangkan  Hilangkan  baris  baris  W W Kapasitas  Pabrik  W  menjadi  30  krn  telah diangkut  ke  pabrik  B=60  (dihilangkan) Kapasitas  Pabrik  W  menjadi  30  krn  telah diangkut  ke  pabrik  B=60  (dihilangkan) W mempunyai perbedaan baris/kolom terbesar dan C mempunyai biaya angkut terkecil

Slide29  6s-29Linear Programming Tabel  5.11.  Feasible  solution  mula-mula  dari  metode  VAM Tabel  5.11.  Feasible  solution  mula-mula  dari  metode  VAM 5 5 Pilihan  Pilihan  X HA   X HA   =  =  50 50 Pilihan  Pilihan  X HC   X HC   =  =  10 10 H mempunyai perbedaan baris/kolom terbesar dan C mempunyai biaya angkut terkecil Gudang Kapasitas Perbedaan baris A B C Pabrik W H 15 10 60 Kebutuhan 50 10 Perbedaan Kolom Kebutuhan  gudang  C  menjadi  10  krn telah  diisi  pabrik  W=30  (dihilangkan) Kebutuhan  gudang  C  menjadi  10  krn telah  diisi  pabrik  W=30  (dihilangkan)

Slide30  6s-30Linear Programming Matrik  hasil  alokasi  dengan   metode  VAM Matrik  hasil  alokasi  dengan   metode  VAM Gudang            A Gudang             B Gudang            C Kapasitas Pabrik Pabrik 20  60 5 30 8 90   W Pabrik 50 15 20 10 10 60    H Pabrik 25 50 10 19 50     P Kebutuhan Gudang 50 110 40 200 Ke Dari Setelah terisi semua, maka biaya transportasinya yang harus dibayar adalah 60(Rp 5,-) + 30(Rp 8,-) + 50(Rp 15,-) + 50(Rp 15,-) + 10(Rp 10,-) + 50(Rp 10,-) = Rp 1.890,-

Slide31  6s-31Linear Programming TERIMAKASIH TERIMAKASIH