TUGAS PROGRAM LINEAR

Nama : 1. Firmawati (1500006105)

2. Risa Setyaningsih (1500006113)

3. habibi Abdurrahman

[Link] putri

Transportasi

A. Model Transportasi

Transportasi membicarakan tentang cara pendistribusian komoditi (barang) tunggal dari

sejumlah sumber (source) ke sejumlah tujuan (destination). Tujuannya adalah untuk menentukan
pola pendistribusian dan banyaknya komoditi/ barang yang di angkut dari masing-masing sumber ke
masing-masing tujuan dengan meminimumkan total ongkos pengangkutan yang memenuhi semua
kendala persediaan dan permintaan.

Model transportasi mengasumsikan hanya ada satu macam komoditi/barang yang diangkut dan
ongkos angkut berbanding lurus (proporsional) dengan banyaknya komoditi yang diangkut dari
sumber ke tujuan.

Contoh model transportasi sebagai berikut :

Misalkan suatu produk yang dihasilkan pada tiga pabrik (sumber) harus didistribusikan ke tiga gudang
(tujuan) seperti berikut :

Sumber (Pabrik) Tujuan (Gudang)

Cirebon Semarang

Bandung Jakarta
Cilacap Purwokerto

3.1 MASALAH TRANSPORTASI SEIMBANG

Contoh masalah transportasi yang mana jumlah supply dari semua sumber sama dengan jumlah
permintaan pada semua tempat tujuan.

Sebuah perusahaan Negara berkepentingan mengangkut pupuk dari tiga pabrik ke tiga pasar. Kapasitas
supply ketiga pabrik, permintaan pada ketiga pasar dan biaya transport per unit adalah sebagai berikut
:

Pasar Penawaran
1 2 3
1 8 5 6 120
Pabrik 2 15 10 12 80
3 3 9 10 80
Permintaan 150 70 60 280

Masalah transportasi diatas dapat gambarkan sebagai suatu model jaringan :

Sumber Volume yang diangkut Tujuan (Gudang)

1 1
S1 = 120 D1 = 150

2 2
S2 = 80 D2 = 70

3 3
S3 = 80 D3 = 60
Masalah ini dapat juga dilihat dalam LP misalkan : Xij : banyaknya unit barang yang di kirim dari pabrik I
(I = 1,2,3) ke pasar j (j = 1,2,3)

Dengan fungsi Tujuan :

Z= 8X11 + 5X12 + 6X13 + 15X21 + 10X22 + 12X23 + 3X31 + 9x32 + 10X33

Dengan batasan :

X11 + X12 + X13 = 120

X21 + X22 + X23 = 80

X31 + X32 + X33 = 80

X11 + X21 + X31 = 150

X12 + X22 + X32 = 70

X13 + X23 + X33 = 60

3.2 TABEL TRANSPORTASI

Masalah transportasi yang khas dapat ditempatkan dalam suatu bentuk table khusus yang dinamakan
table transportasi.

ke
Tujuan
Dari Supply

1 2 …….. j …….. n

C11 C12 C11 C1n

1 …….. …….. S1
X11 X12 X1n
C21 C22 10
2 X21 X22 …….. X21 …….. X2n S2

. . . . . . . .
. . . . . . . .
. . . . . . . .
Ci1 Ci2 Cij Cin
I …….. 30 …….. S1

. . . . . . . .
. . . . . . . .
. . . . . . . .
Cm1 Cm2 Cm1 Cmn
M …….. …….. Sn
Xm1 Xm2 Xm1
 Demand D1 D2 …….. Dj …….. Dn Si = Dj

Sumber ditulis dalam baris-baris dan tujuan dalam kolom – kolom. Biaya transfer per unit (Cij) di catat
pada kotak kecil. Permintaan dari setiap tujuan terdapat pada baris paling bawah, sementara
penawaran setiap sumber dicatat pada kolom paling kanan. Dan kotak pojok kanan bawah
menunjukkan kenyataan bahwa penawaran sama dengan permintaan. Variabel Xij menunjukkan jumlah
barang yang diangkut dari sumber I ke tujuan j (yang akan dicari).

Berikut solusi penyelesaian masalah transportasi, yang dimulai dari mencari sulusi awal (dasar).

Ada tiga metode dalam penyelesaian sulusi awal :

1. Metode North West Corner (NWC) => dari pojok kiri atas ke pojok kanan bawah
Kelemahan : tidak memperhitungkan besarnya biaya sehingga kurang efisien.
2. Metode biaya terkecil (Least Cost)=> mencari dan memenuhi yang biayanya terkecil dulu.
Lebih efisien dibanding metode NWC.
3. Apromasi Vogel
Ada beberapa cara menentukan solusi optimum

1. Metode Stepping Stone

2. Metode Modified Distribution (MODI)
3. Masalah Transportasi Tak Seimbang
4. Degenerasi
5. Solusi Optimum Ganda
6. Rute Terlarang

B. Metode transportasi
1. Tabel awal

Keterangan:
Ai = Daerah asal sejumlah i
Si = Supply, Ketersediaan barang yang diangkut di i daerah asal
Tj = Tempat tujuan sejumlah j
dj = Permintaan (demand) barang di sejumlah j tujuan
xij = Jumlah barang yang akan diangkut dari Ai ke Tj
cij = Besarnya biaya transport untuk 1 unit barang dari Ai ke Tj
Biaya transport = cij . xi
Jumlah permintaan = Jumlah ketersediaan

a. METODE NWC (North West Corner)

Merupakan metode untuk menyusun tabel awal dengan cara mengalokasikan
distribusi barang mulai dari sel yang terletak pada sudut paling kiri atas.
Aturannya:
 Pengisian sel/kotak dimulai dari ujung kiri atas.
 Alokasi jumlah maksimum (terbesar) sesuai syarat sehingga layak untuk
memenuhi permintaan.
 Bergerak ke kotak sebelah kanan bila masih terdapat suplai yang cukup.
Kalau tidak, bergerak ke kotak di bawahnya sesuai demand. Bergerak terus
hingga suplai habis dan demand terpenuhi.

Contoh 1:
 Suatu perusahaan mempunyai 3 pabrik produksi dan 5 gudang penyimpanan hasil
produksi. Jumlah barang yang diangkut tentunya tidak melebihi produksi yang ada
sedangkan jumlah barang yang disimpan di gudang harus ditentukan jumlah
minimumnya agar gudang tidak kosong. Tabel matriks berikut menunjukkan jumlah
produksi paling banyak bisa diangkut, jumlah minimum yang harus disimpan di gudang
dan biaya angkut per unit barang. Dalam smu (satuan mata uang):

Penyelesaian :
• Periksa dulu apakah Total Demand (TD) dengan Total Supply (TS) sama atau tidak.
• Jika TD = TS, maka dikatakan Tabel Transportasi seimbang (equilibrium), jadi tidak perlu
ada kolom dummy (tujuan dummy) maupun baris dummy (sumber dummy).
• Jika TD > TS, maka perlu diseimbangkan dengan menambahkan baris dummy (sumber
dummy).
• Jika TD < TS atau TS > TD, maka perlu diseimbangkan dengan menambahkan kolom
dummy atau tujuan dummy.

b. Metode Inpeksi (Matrik Minimum)

Merupakan metode untuk menyusun tabel awal dengan cara pengalokasian
distribusi barang dari sumber ke tujuan mulai dari sel yang memiliki biaya distribusi
terkecil
Aturannya
1. Pilih sel yang biayanya terkecil
2. Sesuaikan dengan permintaan dan kapasitas
3. Pilih sel yang biayanya satu tingkat lebih besar dari sel pertama yang dipilih
4. Sesuaikan kembali, cari total biaya
c. Metode VAM (Vogel Approkximation Method )
Metode VAM lebih sederhana penggunaanaya, karena tidak memerlukan closed
path (jalur tertutup). Metode VAM dilakukan dengan cara mencari selisih biaya
terkecil dengan biaya terkecil berikutnya untuk setiap kolom maupun baris.
Kemudian pilih selisih biaya terbesar dan alokasikan produk sebanyak mungkin ke
sel yang memiliki biaya terkecil. Cara ini dilakukan secara berulang hingga semua
produk sudah dialokasikan .

• Prosedur Pemecahan:

(1) Hitung perbedaan antara dua biaya terkecil dari setiap baris dan kolom.
(2) Pilih baris atau kolom dengan nilai selisih terbesar, lalu beri tanda kurung. Jika
nilai pada baris atau kolom adalah sama, pilih yang dapat memindahkan barang
paling banyak.
(3) Dari baris/kolom yang dipilih pada (2), tentukan jumlah barang yang bisa
terangkut dengan memperhatikan pembatasan yang berlakubagi baris atau
kolomnya serta sel dengan biaya terkecil.
(4) Hapus baris atau kolom yang sudah memenuhi syarat sebelumnya (artinya
suplai telah dapat terpenuhi).
(5) Ulangi langkah (1) sampai (4) hingga semua alokasi terpenuhi.

• Prosedur Pemecahan:
(1) Hitung perbedaan antara dua biaya terkecil dari setiap baris dan kolom.
(2) Pilih baris atau kolom dengan nilai selisih terbesar, lalu beri tanda kurung. Jika
nilai pada baris atau kolom adalah sama, pilih yang dapat memindahkan barang
paling banyak.
(3) Dari baris/kolom yang dipilih pada (2), tentukan jumlah barang yang bisa
terangkut dengan memperhatikan pembatasan yang berlakubagi baris atau
kolomnya serta sel dengan biaya terkecil.
(4) Hapus baris atau kolom yang sudah memenuhi syarat sebelumnya (artinya
suplai telah dapat terpenuhi).
(5) Ulangi langkah (1) sampai (4) hingga semua alokasi terpenuhi.

Contoh 2:
 Jadi Biaya Total = (400.40) + (800.30) + (400.40) + (500.60) + (200.60) + (200.60)
= 1.100.000
d. Metode Steppingstone (batu loncatan)
Metode Stepping Stone adalah metode untuk mendapatkan solusi optimal
masalah transportasi (TC yang minimum), metode ini bersifat trial and error, yaitu
dengan mencoba-coba memindahkan sel yang ada isinya (stone) ke sel yang kosong
 (water). Tentu saja pemindahan ini harus mengurangi biaya, untuk itu harus dipilih
sedemikian rupa sel-sel kosong yang biaya transportasinya kecil dan memungkinkan
dilakukan pemindahan.

Contoh 3:

Perusahaan memiliki tiga pabrik yang berlokasi di tiga kota yang berbeda dengan
kapasitas produksi per bulan adalah : Pabrik A = 90, Pabrik B = 60, dan Pabrik C = 50.
Perusahaan tersebut juga mempunyai tiga gudang penyimpanan hasil produksinya
yang berlokasi di tiga kota yang berbeda dengan jumlah permintaan per bulan
adalah : Gudang I = 50, Gudang II = 110, dan Gudang III = 40. Diketahui biaya
transportasi dari setiap pabrik ke setiap Gudang adalah sebagai berikut :

Tentukan total biaya transportasi minimum dengan menggunakan metode Stepping

Stone
Tentukan tabel Transportasi awal dengan NWC

e. METODE MODI ( MODIFIED DISTRIBUTION )

Metode ini adalah mirip dengan stepping stone hanya saja dalam mencari biaya minimal
menggunakan cara yang lebih pasti.

Perbaikan Contoh berikut :

A = 20 B=5 C = 14 Kapasitas
W=0 20 5 8
50 40 90

H = 15 15 20 10
60 60

10
 P=5 25 19
10 50

Kebutuhan 50 110 40 200

Langkah penyelesaian MODI

1. Lakukan pengisian awal (Nort West Corner)
2. Memberi bobot dari setiap baris dan setiap kolom.
Ri + Kj = Cij ( Pada kotak-kotak yang terisi)
Ri = Index Baris
Kj = Index Kolom
Cij = Biaya di angkut atau satuan barang dari I ke j
3. Menentukan index perbaikan dengan mengikuti Cij – Ri – Kj (Pada kotak-kotak
yang masih kosong)
4. Menentukan titik awal perubahan
- Bahwa perubahan dilakukan bila masih ada index perbaikan yang
negative
- Bila ada beberapa index perbaikan yang negative maka titik awal
perubahan di mulai pada perbaikan yang paling negative
5. Hitung TC untuk masing-masing perubahan dan perubahan berhenti bila tidak
ada index perbaikan yang negative

Pada contoh tersebut maka :

Langkah 2
RW + KA = CWA atau 0 + KA = 20  KA = 20
RW + KB = CWB atau 0 + KB = 5  KB = 5
RH + KB = CHB atau RH + 5 = 20  RH = 15
RP + KB = CPB atau Rp + 5 = 10  RP = 5
RP + KC = CPC atau 5 + KC = 19  KC = 14

TC = 50 (20) + 40 (5) + 60 (20) + 10 (10) + 40 (19)

= 3260
Langkah 3
Kotak Kosong Cij – Ri – Kj Nilai 1 Perbaikan
HA 15 - 15 – 20 - 20
PA 25 - 5 – 20 0
WC 8 - 0 - 14 -6
HC 10 - 15 - 14 -19
 Langkah 4 memulai pengisian kotak HA

A=0 B=5 C = 14 Kapasitas

20 5 8
W=0 90 90

15 20 10
H = 15 50 10 60

25 10
P=5 10 40 19 50

Kebutuhan 50 110 40 200

TC 2 = 90 (5) + 50(15 + 10 (20) + 10(10) + 40(19) = 2260

Index perbaikan Cij – Ri – Kj hanya untuk kotak yang kosong

Kotak Cij – Ri – Kj Index Perbaikan

WA 20 – 0 – 0 20
WC 8 – 0 – 14 -6
HC 10 – 15 – 14 - 19
PA 25 – 5 – 0 20

Titik awal perbaikan dimulai pada kotak HC dimana kotak HC memiliki tetangga
terdekat (membentuk segi empat dengan tiga kotak lainnya yang terisi)

TC = 90 (5) + 50(15) + 10(10) + 20(10) + 30(19)

= 2070
Karena index perbaikan masih ada yang negative maka :

A=0 B=5 C = 14 Kapasitas

20 5 8
W=0 90 90

15 20 10
H = 15 50 10 60

25 10
P=5 10 40 19 50

Kebutuhan 50 110 40 200

1. Penentuan index baris dan kolom yang baru

 Ri + Kj = Cij  hanya untuk kotak yang terisi

RW + KB = 5  0 + KB = 5 KB = 5
RP + KC = 19  5 + KC = 19 KC = 14
RH + KC = 10  10 + 14 = -4
RH + KA = 15  -4 + KA = 15  KA = 19

2. Index Perbaikan
Kotak Cij – Ri – Kj Index Perbaikan
WA 20 – 0 – 0 20
WC 8 – 0 – 14 -6
HB 20 – 15 – 5 0
PA 25 – 5 – 0 20

A = 19 B=5 C = 14 Kapasitas
20 5 30 8
W=0 60 90

15 20 10
H = -4 50 10 60

25 10
P=5 50 19 50

Kebutuhan 50 110 40 200

TC = 60 (5) + 30(8) + 50(15) + 10(10) + 50(10)

= 1890

1. Karena masih ada yang negative – 6 maka : RW = 0

2. Tentukan lagi index baris dan kolom baru

Ri + kj = Cij

RW + KB = 5  0 + KB = 5 KB = 5
Rp + KB = 10  Rp + 5 = 10  KB = 5
RW + KC = 8  0 + Kc = 8  KC = 8
RH + KC = 10  RH + 8 = 10 RH = 2
RH + KA = 15  2 + KA = 15  KA = 13

3. Kotak Cij – Ri – Kj Index Perbaikan

WA 20 – 0 – 19 1
HB 20 – (-4) – 5 19
PA 25 – 5 – 19 1
PC 19 – 5 – 14 0
Sudah OPTIMAL sebab tidak ada lagi index perbaikan yang negatif