MASALAH TRANSPORTASI

Bentuk Umum Masalah transportasi.

Tabel untuk persoalan angkutan ini adalah sebagai  berikut :

Tujuan Asal	T1		T2		T3		Supply
A1		C11		C12		C1n	a1
	X11		X1j
A2		C21		C22		C2n	a2
	X21		X2j
Ai		Ci1		Cij		Cin	ai
	Xi1		Xij		Xin
Am		C11		C11		C11	am
	Xm1		Xmz		Xmn
Demand	b1		b2		bn

Asumsi

Model matematikanya menjadi :

kendala

untuk menyelesaikan masalah transportasi diatas diperlukan dua langkah yaitu :

1.  menentukan jumlah layak pertama dengan menggunakan metode pojok barat laut (NorthWest Corner Rule)

2.  Menguji apakah penyelesaian awal sudah optimal atau belum (menngunakan metode stepping stone)

Menentukan jawab layak pertama

Langkah-langkah dalam metode NorthWest Corner adalah sebagai berikut :

1.  Pengisian dimulai dari pojok barat laut pada tabel masalah transportasi, yaitu sel (1,1). Bandingkan persediaan di A₁ dengankebutuhan di T₁, yaitu masing-masing a₁ dan b_1. Buat x₁₁ = min (a₁,b₁).

·       Bila a₁ > b₁ , maka x₁₁ = b₁. Teruskan ke sel (1,2) yaitu gerakan mendatar dengan x₁₂ = min (a₁-b₁, b₂)

·       Bila a₁ < b₁ , maka x₁₁ = a₁. Teruskan ke sel (2,1) yaitu gerakan tegak dengan x₂₁ = min (b₁-a₁, a₂)

·       Bila a₁ = b₁ , buatlah  x₁₁ = b₁. Teruskan gerakan ke x₂₂ (gerakan miring)

2.  Teruskan langkah ini, setapak demi setapak, menjauhi pojok barat laut hingga, akahirnya harga telah dicapai pada pojok tenggara dari tabel

Contoh.

Suatu perusahaan mempunyai tiga gudang dan tiga daerah tujuan. Tabel berikut ini menggambarkan ongkos angkut dari tiap gudang ke masing-masing tempat tujuan dan juga jumlah barang yang tersedia di tiap gudang serta kebutuhan tiap daerah.

Tabel data transportasi

Tujuan Asal	T1		T2		T3		Supply
A1		50		100		100	120
	120
A2		200		300		200	170
	30		140
A3		100		200		30	160
			70		90
Demand	150		210		90		450

Langkah-langkahnya.

1. Buat x₁₁ = min (a₁ ,b₁ ) = min (120,150) = 120 dengan a₁ > b₁ . Teruskan ke x₂₁. A₁ sudah dipenuhi.

2. Buat x₂₁        = min (b₁ – a₁,a₂)

= min (150-120,170)

= 30

T₁ sudah terpenuhi. Teruskan ke x₂₂ karena (a₂-30) < b₂

3. Buat x₂₂       = min (a₂ – 30,b₂)

= min (140,210)

= 140

A₂ sudah terpenuhi dan teruskan ke x₃₂ karena T₂ belum tepenuhi

4. Buat x₃₂        = min (b₂ – 140,a₃)

= min (70,160)

= 70

T₂ sudah terpenuhi dan teruskan ke x_33.  x₃₃ dengan sendirinya sama dengan (160 – 70) = 90 dan A₃ pun sudah dipenuhi.

Jadi jawab layak basis adalah;

X₁₁ = 120 ; X₂₁ = 30; X₂₂ = 140; X₃₂ = 70; X₃₃ = 90

Dari  contah  ini, ongkos angkut yang harus dikeluarkan dapat kita hitung sebagai berikut :      

Variabel basis	Banyak	Biaya Satuan	Jumlah
X11 X21 X22 X32 X33	120 30 140 70 90	50 200 300 200 300	6000 6000 42000 14000 27000
			95.000

Menguji keoptimalan penyelesaian awal

        Misalnya kita mempunyai jawab layak  basis  dari  suatu masalah transportasi dengan m asal dan n tujuan. Ini berarti hahwa terdapat m + n - 1 variabel basis x_ij yang  >  0.   kita tidak mengetahui apakah jawab ini sudah optimal atau tidak.

        Untuk menentukan apakah suatu jawab layak  basis  sudah optimal atau tidak, kita  menggunakan  metode  yang  disebut metode batu loncatan atau  stepping  stone  method.  Caranya ialah melalui tabel data transportasi yang  memuat  variabel basis x_ij > 0 dan c_ij.  Kita  menggunakan  analisis   marjinal dengan fnenyhitung z_ij  untuk  setiap  sel  (i,j)  yang   tidak memuat variabel basis x_ij > 0.

Untuk sel (i,j) kita memerlukan satu  lop  yang  memuat sel (i,j) sendiri dan sel-sel  basis.  Misalkan  urutan  sel dalam lop tersebut ialah ;

{(i,r), (u,r)…..,(s,w),(s,j),(i,j)}

harga Z_ij yang bersesuaian adalah

        z_ij = c_ir – c_ur … + c_sj - c_ij

Untuk menghitung Z_ij untuk tiap sel yang tidak memuat  x_ij > 0 kita memerlukan langkah-langkah sebagai berikut ;

1. Tentukan sel basis pada baris yang sama sedemikian hingga. sel basis lainnya terletak pada kolom yang sama.    

2. Buat gerakan mendatar kemudian gerakan tegak.       

3. Ulangi gerakan ini dari satu sel basis kepada sel basis  lainnya hingga satu ketika tiba pada satu tempat atau sel yang satu kolom dengan sel yang dihitung  Z_ij nya.

4. Terakhir hubungkan sel basis ini dengan sel non basis yang dinilai sehingga terbentuklah suatu lop.

5. Jumlahkan harga semua sel basis dalam lop dengan membuat tanda berganti-ganti positif-negatif dan hasilnya sama Z_ij

Proses ini dapat kita lakukan untuk semua sel yang bukan basis apabila :

1. Z_ij ≤ 0 untuk setiap (i,j) maka jawab layak basis sudah optimal.                                           

2. Z_ij > 0 untuk suatu (i,j) maka jawab layak basis   belum optimal.  

Sesudah Z_ij dihitung untuk semua sel yang bukan   basis, sekarang kita sudah siap menentukan jawab basis yang baru, yaitu denganlangkah-langkah sebagai berikut :

1.  Hitungan atau tetapkan :

Z_st = maks z_ij

Artinya variabel x_st masuk dalam basis dan x_st > 0

2.  Tentukan loop yang memuat x_st

3.  Pandang c_αβ dengan koefisien 1

4.  Tetapkan x_pq = min (x_αβ dengan coef c_αβ = 1) artinya variabel x_pq keluar sebagai variabel basis

5.  Tentukan harga variabe basis untuk jawab basis yang baru dengan cara :

a.  X_st’ = x_pq

b.  Bila koefisien c_αβ = 1 , maka X’_αβ = = x_αβ - x_pq

c.   Bila koefisien c_αβ = -1 , maka X’_αβ = = x_αβ + x_pq

Perhatikan bahwa x_αβ  terdapat dalam loop yang memuat (s,t).

Contoh.

Pandang contoh perusahaan yang mempunyai 3 gudang dan tiga daerah tujuan di atas.                         

Jawab layak basis permulaan kita tentukan dengan metode pojok barat laut seperti kita lihat dalam tabel di atas. Sekarang kita lakukan perhitungan berdasarkan urutan langkah-langkah seperti di atas ;

1. Kita hitung Z_ij dari sel yang tidak memuat variabel basis

a. Sel (1,2). Loop yang bersesuaian (1,1) , (2,1) , (2,2), (1,2)

        Z₁₂    = c₁₁ – c₂₁ +c₂₁ – c₁₂

                = 50 –200 + 300 – 100 = 50

b. Sel (1,3). Loop yang bersesuaian (1,3), (2,1), ( 2,2),( (3,2) ,(3,3), (1,3)

        Z₁₃   = c₁₃ – c₂₁ +c₂₂ – c₃₂ +c₃₃-c₁₃

                = 50-200+300-200+300-100=150

c. Sel (2,3). Loop yang bersesuaian (2,2) , (3,2) , (3,3), (2,3)

        Z₂₃   = c₂₂ – c₃₂ +c₃₃ – c₂₃

                = 300-200+300-200 = 200

d. Sel (3,1). Loop yang bersesuaian (3,2), (2,2), ( 2,1), (3,1)

        Z₃₁   = c₃₂ – c₂₂ + c₂₁ - c₃₁

                = 200-300+200-100 = 0

2. Variabel x_st yang masuk dalam basis

maks {z_ij} = maks { 50, 150,200 }

                        = 200 = z₂₃

Maka z₂₃ masuk kedalam basis

3. Loop yang memuat sel (2,3) ialah :

(2,2) , (3,2) , (3,3), (2,3) karena itu

        Z₂₃   = c₂₂ – c₃₂ +c₃₃ – c₂₃

c_αβ dengan koefisien 1 ialah c₂₂ dan c₃₃, sehingga :

Min { x₂₂, x₃₃} = Min { 140,90} = 90

Maka x₃₃ keluar dari basis

4. Harga variabel basis baru adalah :

        x₂₃’   = x₃₃                                 = 90

        x₃₂’   = x₃₂ + x₃₃ = 70 + 90         = 160

        x₂₂’   = x₂₂ – x₃₃ = 140 – 90       = 50

5. Variabel basis yang lain tetap seperti semula

Sekarang label untuk variabel basis yang baru ialah:

Tujuan Asal	T1		T2		T3		Supply
A1		50		100		100	120
	120
A2		200		300		200	170
	30		50		90
A3		100		200		30	160
			160
Demand	150		210		90		450

Dari tabel diatas menghitung kembali Z_ij 

a. Sel (1,2). Loop yang bersesuaian (1,1) , (2,1) , (2,2), (1,2)

        Z₁₂    = c₁₁ – c₂₁ +c₂₂ – c₁₂

                = 50 –200 + 300 – 100 = 50

b. Sel (1,3). Loop yang bersesuaian (1,1), (2,1), ( 2,3), (1,3)

        Z₁₃   = c₁₁ – c₂₁ +c₂₃ -c₁₃

                = 50-200+200-100=  -50

c. Sel (3,1). Loop yang bersesuaian (3,2), (2,2), ( 2,1), (3,1)

        Z₃₁    = c₃₂ – c₂₂ + c₂₁ - c₃₁

                = 200-300+200-100 = 0

d. Sel (3,3). Loop yang bersesuaian (3,2), (2,2), ( 2,3), (3,3)

        Z₃₃    = c₃₂ – c₂₂ + c₂₃ - c₃₃

                = 200-300+200-100 = 0

1.  Varibael yang masuk dalam basis satu-satuny adalah x₁₂ dengan z₁₂ = 50 > 0. Sedangkan untuk sel non basis lainnya z_ij ≤ 0.

2.  Loop yang memuat  sel (1,2) ialah :

(1,1) , (2,1) , (2,2), (1,2) sehingga :

        Z₁₂   = c₁₁ – c₂₁ +c₂₂ – c₁₂

        Koefisien c_ij = 1 adalah koefisien c₁₁ dan c₂₂, sehinngga variabel basis yang keluar ialah :

    Min { x11, x22} = Min { 120,50} = 50

    Maka x22 keluar dari basis

3.  Harga variabel basis baru adalah :

        x₁₂’   = x₂₂                                 = 50

        x₁₁’   = x₁₁ – x₂₂        = 120 - 50        = 70

        x₂₁’   = x₂₁ + x₂₂ = 30 + 50 = 80

sekarang tabel untuk variabel basis yang baru ialah :

Tujuan Asal	T1		T2		T3		Supply
A1		50		100		100	120
	70		50
A2		200		300		200	170
	80				90
A3		100		200		30	160
			160
Demand	150		210		90		450

Dari tabel ini kita hitung kembali zij untuk sel-sel yang bukan basis  yaitu :

a. Sel (1,3).

        Z₁₃    = c₁₁ – c₂₁ +c₂₃ – c₁₃

                = 50 –200 + 200 – 100 = -50

b. Sel (2,2)

        Z₂₂   = c₁₂ – c₁₁ +c₂₁ –c₂₂

                = 100-50+200-300=  -50

c. Sel (3,1)

        Z₃₁    = c₃₂ – c₁₂ + c₁₁ - c₃₁

                = 200-100+50-100 = 50

d. Sel (3,3)

        Z₃₃    = c₃₂ – c₁₂ + c₁₁ – c₂₁ + c₂₃ - c₃₃

                = 200 – 200 + 50 – 100 + 200 – 300 = -150

kita lihat masih ada sel dengan zij > 0 yaitu sel (3,1) dengan z₃₁ > 0. Karena itu variabel x₃₁ masuk dalam basis. Loop yang memuat sel (3,1) ialah loop (3,2),(1,2),(1,1),(3,1) dengan z₃₁ = c32 – c12 + c11 - c31

            Min { x₃₂, x₁₁} = Min { 160,70} = 70

    Maka x₁₁ keluar dari basis

3.  Harga variabel basis baru adalah :

        x₃₁’   = x₁₁                                 = 70

        x₃₂’   = x₃₂ – x₁₁        = 160 - 70        = 90

        x₁₂’   = x₁₂ + x₁₁        = 50 + 70 = 120

hasil ini kita gambarkan sebagai berikut :

Tujuan Asal	T1		T2		T3		Supply
A1		50		100		100	120
			120
A2		200		300		200	170
	80				90
A3		100		200		30	160
	70		90
Demand	150		210		90		450

Kembali kita hitung zij untuk sel yang bukan basis :

Sel (1,1)   z₁₁    =c₁₂ –c₃₂ +c₃₁-c₁₁= -50

Sel (1,3)   z₁₃    = -100             

Sel (2,2)   z₂₂    = 0

Sel (3,3)   z₃₃    = -200

Sekarang kita lihat semua sel non basis mempunyai harga z_ij ≤ 0. Karena itu kita telah menemukan jawab optimal yaitu :

X₁₂ = 120

X₂₁ = 80

X₂₃ = 90

X₃₁ = 70

X₃₂ = 90

Dengan z = Rp. 71.000,-