Modul 5 Model Transportasi 2007

MODUL V MODEL TRANSPORTASI LINIER PRAYUDI

Riset Operasi Prayudi

Modul V : Solusi Program

1

MODEL TRANSPORTASI

LINIER Karakteristik model transportasi linier :

§Adanya barang (produk) yang dipindahkan dari sejumlah

sumber ke tempat tujuan §Adanya biaya yang timbul akibat memindahkan sejumlah barang tersebut, sehingga menimbulkan masalah untuk meminimalkan biaya transportasi §Jumlah barang (produk) yang disediakan di setiap sumber sifatnya tetap pada periode waktu tertentu §Jumlah barang (produk) yang diminta setiap tempat tujuan sifatnya tetap pada periode waktu tertentu. Riset Operasi Prayudi

Modul V : Solusi Program

2

CONTOH KASUS Perhatikanlah data kebutuhan batu bara dan ketersediaan dari tambang berikut ini Pembangkit Kebutuhan Tambang Jumlah UP-Banten 350 ribu ton PT. Adaro 700 ribu ton UP-Cirebon 450 ribu ton PT. BA 500 ribu ton UP-Madiun 550 ribu ton PT. KPC 400 ribu ton UP-Surabaya 650 ribu ton PT. Unacol 400 ribu ton Berdasarkan analisis PT. Hasanun biaya transportasi adalah sebagai berikut Tujuan (Biaya dalam $ juta per ribu ton) Dari UP-Banten UP-Cirebon UP-Madiun UP-Surabaya PT Adaro 12 11 18 22 PT. BA 18 20 15 14 PT. KPC 16 14 13 19 PT. Unacol 21 17 12 15 Berdasarkan data tersebut saudara diminta untuk membuat rancangan pemenuhan kebutuhan batu bara pembangkit agar biaya minimum Riset Operasi Prayudi

Modul V : Solusi Program

3

LANGKAH-LANGKAH SOLUSI METODE TRANSFORTASI 1.Buatlah tabel awal masalah transportasi, model programa linier 2.Tentukan solusi awal transportasi : a. Metode Pojok Kiri Atas (Metode Northwest Corner) b. Metode sel biaya minimum c. Metode VOGEL (finalty cost) 3.Uji optimasi : a. Metode Batu Loncatan (Stepping Stone) b. Metode MODI Tabel dikatakan optimum bilamana semua perubahan biaya (c-ij) lebih besar atau sama dengan nol 4. Solusi program komputer Riset Operasi Prayudi

Modul V : Solusi Program

4

MODEL TABEL AWAL TRANSPORTASI D1 S1

D2 11

x11 S2

x12

x21

S4

18

20

16

x23

x32

x33 12

x42

x43

x44

350

450

550

650

Modul V : Solusi Program

700

14

500

19

400

15

400

x34

x41

Riset Operasi Prayudi

22

x24 13

17

Jumlah

x14 15

14

21

D4

x13

x22

x31

Jumlah

12

18

S3

D3

2.000 5

FORMULASI MODEL VARIABEL KEPUTUSAN xij : Jumlah batu bara yang dikirimkan dari sumber (tambang) ke tujuan (pembangkit)

BATASAN-BATASAN Kapasitas Tambang (Penawaran) x11 + x12 + x13 + x14 x21 + x22 + x23 + x24 x31 + x32 + x33 + x34 x41 + x42 + x43 + x44 Kebutuhan Pembangkit (Permintaan)

FUNGSI TUJUAN Meminimalkan biaya : Z =  c-ij x-ij = 11x11 + 12x12 + 18x21 + 20x22 + 16x31 + 14x32 + 21x41 + 17x42 Riset Operasi Prayudi

+ + + +

18x13 15x23 13x33 12x43

+ + + +

22x14 14x24 19x34 15x44

x11 x12 x13 x14

Modul V : Solusi Program

+ + + +

x21 x22 x23 x24

+ + + +

x31 x32 x33 x34

+ + + +

x41 x42 x43 x44

= = = =

700 500 400 400

= = = =

350 450 550 650 6

LANGKAH-LANGKAH SOLUSI METODE TRANSFORTASI 1.Buatlah tabel awal masalah transportasi 2.Tentukan solusi awal transportasi : a. Metode Pojok Kiri Atas (Metode Northwest Corner) b. Metode sel biaya minimum c. Metode VOGEL (finalty cost) 3.Uji optimasi : a. Metode Batu Loncatan (Stepping Stone) b. Metode MODI Tabel dikatakan optimum bilamana semua perubahan biaya (c-ij) lebih besar atau sama dengan nol Riset Operasi Prayudi

Modul V : Solusi Program

7

SOLUSI AWAL : METODE NORTHWEST CORNER Langkah-langkah : 1.Alokasikan sebanyak mungkin ke sel pojok kiri atas, yang disesuaikan dengan batasan permintaan dan penawaran 2.Alokasikan sebanyak mungkin ke sel fisibel berikutnya yang berdekatan, dengan memperhatikan batasan permintaan dan penawaran 3.Ulangi langkah (2) sampai semua kebutuhan terpenuhi

Riset Operasi Prayudi

Iterasi

Xij

cij

cij xij

1

x11=350

c11=11

3.850

2

x12=350

c12=12

4.200

3

x22=100

c22=20

2.000

4

x23=400

c23=15

6.000

5

x33=150

c33=13

1.950

6

x34=250

c34=18

4.500

7

x44=400

c44=15

6.000

2.000

28.500

Jumlah

Modul V : Solusi Program

8

Hasil iterasi solusi awal Metode Pojok Kiri Atas Total Biaya Metode Pojok Kiri Atas : $ 28.500 juta D1 S1

D2

D3

11 x11=350

S2

12 x12=350

18 X

S3 S4 Jumlah 350 Riset Operasi Prayudi

x23=400

XXX

x33=150

700

14

500

19

400

15

400

x34=250

12

XXX

XXXXX

x44=400

450

550

650

Modul V : Solusi Program

22

XXXX

13

17

Jumlah

XX 15

14

21 X

XX

x22=100

X

18

20

16

D4

2.000 9

SOLUSI AWAL : METODE SEL BIAYA MINIMUM Langkah-langkah Metode Sel Biaya Minimum

Iterasi

1 1.Tentukanlah sel yang memiliki 2 biaya terendah 2.Alokasikan sebanyak mungkin ke sel yang memiliki biaya 3 minimum pada langkah (1), yang disesuaikan dengan 4 batasan permintaan dan penawaran 3.Ulangi langkah (2) sampai semua5 kebutuhan terpenuhi Jumlah

Riset Operasi Prayudi

cij

xij

c11=11

x11=350 3.850

c12=12

x12=350 4.200

c43=12

x43=400 4.800

c33=13

x33=150 1.950

c24=14

x24=500 7.000

c32=14

x32=100 1.400

c34=19

x34=150 2,850

Modul V : Solusi Program

2.000

cij xij

26.050

10

Hasil Iterasi Metode Sel Biaya Minimum Total Biaya Metose Sel Biaya Minimum : $ 26.050 juta D1 S1 S2 S3

D2

11 x11=350 18 X 16 X

S4 X Jumlah 350 Riset Operasi Prayudi

D3 12

x12=350

18 XX

20 XXXX x32=100 17 XX 450

15 13 x33=150 12 x43=400 550

Modul V : Solusi Program

Jumlah 22

700

14

500

19

400

15

400

XX

XXX 14

21

D4

x24=500 x34=150 XX 650

2.000 11

SOLUSI AWAL METODE VOGEL Langkah-langkah Iterasi 1.Untuk setiap baris atau kolom tentukanlah biaya finalti dengan cara mengurangkan dua biaya terendah dari masing-masing baris atau kolom 2.Pilih satu baris atau kolom yang memiliki biaya finalti terbesar 3.Alokasikan sebanyak mungkin ke sel yang memiliki biaya terendah pada baris atau kolom yang memiliki biaya finalti terbesar, disesuaikan dengan batasan permintaan dan penawaran 4.Ulangi langkah (2) sampai semua kebutuhan terpenuhii Riset Operasi Prayudi

Modul V : Solusi Program

12

VOGEL (2) Langkah-langkah Iterasi Iterasi

Finalty cost

cij

xij

cij xij

1

fc-K1=16-11=5

c11=11

x11=350

3.850

2

fc-B1=18-12=6

c12=12

x12=350

4.200

3

fc-B4=15-12=3

c43=12

x43=400

4.800

fc-K2=17-14=3

c32=14

x32=100

1.400

4

fc-B3=19-13=6

c33=13

x33=150

1.950

5

fc-K4=19-14=5

c24=14

x24=500

7.000

c34=19

x34=150

2,850

5 Jumlah Riset Operasi Prayudi

26.050 Modul V : Solusi Program

13

VOGEL (3) Hasil Iterasi Metode Finalty Cost D1 S1

D2

D3

11 x11=350

S2

12 x12=350

18 X

S3

20

x32=100 21

X Jumlah 350 Riset Operasi Prayudi

15

14

x33=150

700

14

500

19

400

15

400

x34=150

12

XXX

x43=400

XXX

450

550

650

Modul V : Solusi Program

22

x24=500 13

17

Jumlah

XX

XXXX

16

S4

18 XX

XXX

X

D4

2.000 14

METODE BATU LONCATAN (STEPPING STONE) 1.Selidikilah apakah jumlah sel ini = m+n-1. Jika jumlah sel ini < m+n-1, buatlah jumlah sel isi menjadi m+n-1, dengan menambahkan sembarang 1 (satu) sel isi semu (dummy), x-ij = 0. 2.Untuk setiap sel non fisibel (sel kosong), tentukanlah lintasan stepping stone, dan hitung perubahan biaya yang sesuai lintasan stepping stone 3.Lakukan uji optimasi. Selidikilah apakah semua perubahan biaya k-ij  0. Jika k-ij  0 , maka tabel sudah optimum, dan jika terdapat k-ij <0, tabel belum optimum. 4.Jika tabel belum optimum, pilih sel non fisibel yang memiliki perubahan biaya terbesar (k-ij < 0), dan lakukan alokasi sebanyak mungkin ke sel non fisibel sesuai dengan lintasan stepping stone-nya. 5.Hitung perubahan biaya total yang terjadi 6.Ulangi kembali langkah (2) sampai (5), sampai diperoleh solusi optimal

Riset Operasi Prayudi

Modul V : Solusi Program

15

SOLUSI AWAL : METODE SEL MINIMUM Contoh Lintasan Stepping Stone X13 D1 S1

D2 11

x11=350 S2

12 x12=350

18 X21

S3

18

20

15

14 X32=100

21

x33=150 12

X42

x43=400

X44

350

450

550

650

Modul V : Solusi Program

700

14

500

19

400

15

400

x34=150

X41

Riset Operasi Prayudi

22

x24=500 13

17

Jumlah

X14

X23

16

S4

D4

X13

X22

X31

Jumlah

D3

2.000 16

SOLUSI AWAL : METODE SEL MINIMUM Contoh Lintasan Stepping Stone X21 D1 S1

D2 11

x11=350 S2

12 x12=350

18 X21

S3

18

20

15

14 X32=100

21

x33=150 12

X42

x43=400

X44

350

450

550

650

Modul V : Solusi Program

700

14

500

19

400

15

400

x34=150

X41

Riset Operasi Prayudi

22

x24=500 13

17

Jumlah

X14

X23

16

S4

D4

X13

X22

X31

Jumlah

D3

2.000 17

SOLUSI AWAL : METODE SEL MINIMUM Contoh Lintasan Stepping Stone X41 D1 S1

D2 11

x11=350 S2

12 x12=350

18 x21

S3

18

20

15

14 x32=100

21

x33=150 12

x42

x43=400

x44

350

450

550

650

Modul V : Solusi Program

700

14

500

19

400

15

400

x34=150

x41

Riset Operasi Prayudi

22

x24=500 13

17

Jumlah

x14

x23

16

S4

D4

x13

x22

x31

Jumlah

D3

2.000 18

UJI OPTIMASI 1 : METODE STEPPING STONE (ITERASI I) No

Sel Kosong

Lintasan Stepping Stone

Perubahan Biaya

1

x13

x13-x33-x23-x12

k13=18-13+14-12= 7

2

x14

x14-x34-x32-x12

k14=22-19+14-12=5

3

x21

x21-x11-x12-x32-x34-x24

k21=18-11+12-14+19-14=10

4

x22

x22-x24-x34-x32

k22=20-14+19-14=11

5

x23

x23-x24-x34-x33

k23=15-14+19-13=7

6

x31

x31-x11-x12-x32

k31=16-11+12-14=3

7

x41

x41-x11-x12-x32-x33-x43

k41=21-11+12-14+13-12=9

8

x42

x42-x32-x33-x43

k42=17-14+13-12=4

8

x44

x44-x43-x33-x34

k44=15-12+13-19=–3

Riset Operasi Prayudi

Modul V : Solusi Program

19

HASIL UJI OPTIMASI DAN PERUBAHAN ALOKASI Uji optimasi. Karena terdapat perubahan biaya, k44 = -3<0, maka tabel belum optimum Perubahan alokasinya adalah sebagai berikut : Tabel Awal : z = 26.050 Tabel Baru : Z = 25.600

(+)

13

(-)

19

(+)

13

(-)

x33=150

x34=150

x33=300

x34=0

(-)

12

(+)

(-)

(+)

x43=400

x44

Riset Operasi Prayudi

15

12

x43=250 Modul V : Solusi Program

19 15

x44=150 20

Iterasi II : Metode Stepping Stone Z=26.050 D1 S1

Z=26.050-3(150) = 25.600

D2

D3

11 x11=350

S2

12 x12=350

18 x21

S3

20

15

14 x32=100

21

x33=300 12

x42

x43=250

x44=150

Jumlah 350

450

550

650

Modul V : Solusi Program

700

14

500

19

400

15

400

x34

x41

Riset Operasi Prayudi

22

x24=500 13

17

Jumlah

x14

x23

16

S4

18 x13

x22

x31

D4

2.000 21

UJI OPTIMASI 2 : METODE STEPPING STONE (ITERASI II) No

Sel Kosong

Lintasan Stepping Stone

Perubahan Biaya

1

x13

x13-x33-x23-x12

k13=18-13+14-12= 7

2

x14

x14-x44-x43-x33-x32-x12

k14=22-15+12-13+14-12=8

3

x21

k21=18-11+12-14+13-12+15-14=7

4

x22

x21-x11-x12-x32-x33-x43x44-x24 x22-x24-x44-x43-x33-x32

5

x23

x23-x24-x44-x43

k23=15-14+15-12=4

6

x31

x31-x11-x12-x32

k31=16-11+12-14=3

7

x34

x34-x44-x43-x33

k34=19-15+12-13=3

8

x41

x41-x11-x12-x32-x33-x43

k41=21-11+12-14+13-12=9

8

x42

x42-x43-x33-x32

k42=17-12+13-14=4

Riset Operasi Prayudi

Modul V : Solusi Program

k22=20-14+15-12+13-14=8

22

HASIL UJI OPTIMASI ITERASI II (1) Uji optimasi. Karena semua nilai perubahan biaya, k-ij > 0, tabel optimum Total biaya transportasinya adalah $ 25.600 juta Rencana pemenuhan batu bara dari sisi pembangkit

Nilai x-ij

Interpretasi hasil

x11=350 x12=350 x32=100

Kebutuhan batu bara dari UP Banten diperoleh dari tambang PT. Adaro Kebutuhan batu bara dari UP Cirebon disuplay dari tambang PT. Adaro dan PT. KPC

x33=300 x43=250

Kebutuhan batu bara dari UP Madiun diperoleh dari tambang PT. KPC dan PT. Unacol

x24-=500 x44=150

Kebutuhan batu bara dari UP Surabaya disuplay tambang PT. BA dan PT. Unacol

Riset Operasi Prayudi

Modul V : Solusi Program

23

HASIL UJI OPTIMASI ITERASI II (2) Ditunjau dari sisi tambang :

Nilai x-ij

Interpretasi hasil

x11=350 x12=350

PT. Adaro mensuplay kebutuhan batu bara UP Banten dan UP Cirebon

x24=500

PT. BA hanya mensuplay kebutuhan batu bara UP Surabaya

x32=350 x33=300

PT. KPC mensuplay kebutuhan batu bara UP Cirebon dan UP Madiun

x43=250 x44=150

PT. Unacol mensuplay kebutuhan batu bara UP Madiun dan UP Surabaya

Riset Operasi Prayudi

Modul V : Solusi Program

24

METODE MODI (1) Langkah-langkah metode MODI adalah : 1.Selidikilah apakah jumlah sel ini = m+n-1. Jika jumlah sel ini < m+n-1, oleh karena itu buatlah jumlah sel isi menjadi m+n-1, dengan menambahkan sembarang 1 (satu) sel isi semu (dummy), x-ij =0. 2.Dari sel isi (fisibel) hitung nilai ui dan vj dengan menggunakan persamaan, ui+vj = cij 3.Untuk setiap sel kosong (non fisibel), hitung perubahan biaya, kij dengan rumus : kij = cij-ui-vj 4.Lakukan uji optimasi. Selidikilah apakah semua perubahan biaya kij  0. Jika kij  0, maka tabel sudah optimum. 5.Jika belum optimum, pilih sel non fisibel yang memiliki perubahan biaya terbesar (kij <0), dan lakukan alokasi sebanyak mungkin ke sel non fisibel sesuai lintasan Stepping Stone 6.Hitung perubahan biaya total yang terjadi 7.Ulangi kembali langkah (2) sampai (5), sampai diperoleh solusi optimal Riset Operasi Prayudi

Modul V : Solusi Program

25

METODE MODI : LANGKAH OPTIMASI, Hitung nilai ui dan vi

u1=-2 u2=-5

S1

v1=13

v2=14

v3=13

v4=19

D1

D2

D3

D4

11 x11=350

12 x12=350

18

20

S2 x21

u3=0

S3

16 x31

u4=-1

S4 Jumlah

Riset Operasi Prayudi

21 x41 350

18 x13

Jumlah 22

700 500 400

x14 15

x22

x23

14 x24=500

14 x32=100 17 x42 450

13 x33=150 12 x43=400 550

19 x34=150 15 x44 650

Modul V : Solusi Program

400 2.000

26

MODI : Menghitung nilai ui dan vj Iterasi ke Sel Isi

Persamaan

x11

u1+v1=11

x12

u1+v2=12

v1=-2

x24

u2+v4=14

u2=-5

x32

u3+v2=14

x33

u3+v3=13

v3=13

x34

u3+v4=19

v4=19

x43

u4+v3=12

Riset Operasi Prayudi

i=1

i=2

i=3

i=4 v1=13

u3=0

v2=14

u4=-1 Modul V : Solusi Program

27

MODI : Evaluasi Sel Kosong Sel Kosong x13 x14 x21 x22 x23 x31

Perubahan Biaya k13 = c13 – u1 – v3 = 18 – (-2) – 13 = 7 k14 = c14 – u1 – v4 = 22 – (-2) – 19 = 5 k21 = c21 – u2 – v1 = 18 – (-5) – 13 = 10 k22 = c22 – u2 – v2 = 20 – (-5) – 14 = 11 k23 = c23 – u2 – v3 = 15 – (-5) – 13 = 7 k31 = c31 – u3 – v1 = 16 – 0 – 13 = 3

x41 x42 x44

k41 = c41 – u4 – v1 = 21 – (-1) – 13 = 9 k42 = c42 – u4 – v2 = 17 – (-1) – 14 = 4 k44 = c44 – u4 – v4 = 15 – (-1) – 19 = - 3

Karena terdapat perubahan biaya, k44 = -3 < 0, tabel belum optimum Riset Operasi Prayudi

Modul V : Solusi Program

28

HASIL UJI OPTIMASI DAN PERUBAHAN ALOKASI Uji optimasi. Karena terdapat perubahan biaya, k44 = -3<0, maka tabel belum optimum Perubahan alokasinya adalah sebagai berikut : Tabel Awal : z = 26.050 Tabel Baru : Z = 25.600

(+)

13

(-)

19

(+)

13

(-)

x33=150

x34=150

x33=300

x34=0

(-)

12

(+)

(-)

(+)

x43=400

x44

Riset Operasi Prayudi

15

12

x43=250 Modul V : Solusi Program

19 15

x44=150 29

MODI : Iterasi II Hitung nilai ui dan vj

u1=11

v1=0

v2=1

v3=0

v4=3

D1

D2

D3

D4

S1

11 x11=350

u2=11

S2 S3

16

S4 Jumlah

Riset Operasi Prayudi

18 x13

20 x22

x31 u4=12

x12=350

18 x21

u3=13

12

x23

x32=100 21

700

14

500

x24=500 13

x33=300

17

22 x14

15

14

Jumlah

19

400

15

400

x34

12

x41

x42

x43=250

x44=150

350

450

550

650

Modul V : Solusi Program

2.000 30

MODI : ITERASI II Menghitung nilai ui dan vj Iterasi ke Sel Isi Persamaan

i=1

i=2

i=3

i=4

x11

u1+v1=11

x12

u1+v2=12

u1=11

x24

u2+v4=14

u2=11

x32

u3+v2=14

x33

u3+v3=13

x43

u4+v3=12

x44

u4+v4=15

Riset Operasi Prayudi

i=5 v1=0

v2=1 v3=0

u3=13 u4=12 v4=3 Modul V : Solusi Program

31

MODI : ITERASI II Evaluasi Sel Kosong Sel Kosong x13 x14 x21 x22 x23 x31 x34 x41 x42

Perubahan Biaya k13 = c13 – u1 – v3 = 18 – 11 – 0 = 7 k14 = c14 – u1 – v4 = 22 – 11 – 3 = 8 k21 = c21 – u2 – v1 = 18 – 11 – 0 = 7 k22 = c22 – u2 – v2 = 20 – 11 – 1 = 8 k23 = c23 – u2 – v3 = 15 – 11 – 0 = 4 k31 = c31 – u3 – v1 = 16 – 13 – 0 = 3 k34 = c34 – u3 – v4 = 19 – 13 – 3 = 3 k41 = c41 – u4 – v1 = 21 – 12 – 0 = 9 k42 = c42 – u4 – v2 = 17 – 12 – 1 = 4

Karena semua perubahan biaya, k-ij > 0, maka tabel sudah optimum Riset Operasi Prayudi

Modul V : Solusi Program

32

INPUT PROGRAM LINDO Min 11x11 + 12x12 + 18x13 + 22x14 + 18x21 + 20x22 + 15x23 + 14x24 + 16x31 + 14x32 + 13x33 + 19x34 + 21x41 + 17x42 + 12x43 + 15x44 Subject to ! Kapasitas Tambang (Penawaran) x11 x21 x31 x41

+ + + +

x12 x22 x32 x42

+ + + +

Riset Operasi Prayudi

x13 x23 x33 x43

+ + + +

x14 x24 x34 x44

! Kebutuhan Pembangkit (Permintaan) = = = =

700 500 400 400

x11 x12 x13 x14

+ + + +

Modul V : Solusi Program

x21 x22 x23 x24

+ + + +

x31 x32 x33 x34

+ + + +

x41 x42 x43 x44

= = = =

350 450 550 650 33

SOLUSI PROGRAM KOMPUTER - LINDO LP OPTIMUM FOUND AT STEP 5 OBJECTIVE FUNCTION VALUE 1) 25600.00 VARIABLE VALUE REDUCED COST X11 350.000000 0.000000 X12 350.000000 0.000000 X13 0.000000 7.000000 X14 0.000000 8.000000 X21 0.000000 7.000000 X22 0.000000 8.000000 X23 0.000000 4.000000 X24 500.000000 0.000000 X31 0.000000 3.000000 X32 100.000000 0.000000 X33 300.000000 0.000000 X34 0.000000 3.000000 X41 0.000000 9.000000 X42 0.000000 4.000000 X43 250.000000 0.000000 X44 150.000000 0.000000

Riset Operasi Prayudi

Modul V : Solusi Program

34

SOLUSI PROGRAM DS-2 Source 1 Source 2 Source 3 Source 4 DEMAND

Dest 1 Dest 2 Dest 3 Dest4 SUPPLY 11 12 18 22 700 18 20 15 14 500 16 14 13 19 400 21 17 12 15 400 350 450 550 650

Optimal = $25,600 Dest1 Dest2 Dest3 Dest4 cost Source 1 350 350 Source 2 500 Source 3 100 300 Source 4 250 150

Riset Operasi Prayudi

Modul V : Solusi Program

35

KASUS KHUSUS MODEL TRANSPORTASI 1.Degenerasi Kejadian ini terjadi, bilamana jumlah sel isi < m+n-1. Solusinya adalah model dibuat seimbang dengan cara menambahkan 1 (satu) sel ini dummy yakni sel isi dengan alokasi 0, x-ij = 0 2. Model Tak Seimbang Jika terjadi model tidak seimbang antara permintaan dan penawaran, maka model harus dibuat menjadi setimbang. Kejadian ini terjadi bila : a)Permintaan < penawaran. Dibuat permintaan semu sehingga setimbang, dimana permintaan semu adalah selisih antara penawaran – permintaan, dengan biaya transportasi semua adalah 0 b)Permintaan > jumlah penawaran. Dibuat penawaran semu sehingga setimbang, dimana jumlah penawaran semu adalah selisih antara permintaan – penawaran, dengan biaya transportasi semu adalah 0 Riset Operasi Prayudi

Modul V : Solusi Program

36

CONTOH KASUS Perhatikanlah data kebutuhan pembangkit dan penawaran dari tambang adalah sebagai berikut : Pembangkit Kebutuhan Tambang Jumlah UP-Banten 400 ribu ton PT. Adaro 800 ribu ton UP-Cirebon 450 ribu ton PT. BA 600 ribu ton UP-Madiun 550 ribu ton PT. KPC 550 ribu ton UP-Surabaya 600 ribu ton Jumlah 2.000 ribu ton Jumlah 1.950 ribu ton Berdasarkan analisis PT. Agak Montok biaya transportasi sebagai berikut : Tujuan (Biaya dalam $ juta per ribu ton) Dari UP-Banten UP-Cirebon UP-Madiun UP-Surabaya PT Adaro 12 11 16 19 PT. BA 18 12 15 14 PT. KPC 16 17 13 11 Berdasarkan data tersebut saudara diminta untuk membuat rancangan pemunuhan kebutuhan batu bara pembangkit agar biaya minimum Riset Operasi Prayudi

Modul V : Solusi Program

37

MODEL TAK SEIMBANG PERMINTAAN > PENAWARAN : PENAWARAN SEMU D1 S1

D2 12

x11 S2

11 x12

18 x21

S3

x13

x22

x31

x23

x32

x33 0

x42

x43

x44

Jumlah 350

450

550

650

Modul V : Solusi Program

800

14

600

11

550

0

50

x34

x41

Riset Operasi Prayudi

19

x24 13

0

Jumlah

x14 15

17

0

D4 16

12

16

SD

D3

2.000 38

SOLUSI AWAL : METODE SEL BIAYA MINIMUM Iterasi

cij

xij

cij xij

1

c12=11

x12=450

4.950

c34=11

x34=550

6.050

2

c11=12

x11=350

4.200

3

c24=14

x24=100

1.400

4

c23=15

x23=500

7.500

5

c34= 0

x34=50

0

2.000

24.100

Jumlah

Catatan : Alokasi pengisian sel dummy, dengan biaya semu 0, dilakukan pada saat terakhir Riset Operasi Prayudi

Modul V : Solusi Program

39

SOLUSI AWAL : METODE SEL BIAYA MINIMUM, z = 22.900 D1 12 x11=350 S2 18 X S3 16 X SD 0 X Jumlah 350

D2

D3

S1

Riset Operasi Prayudi

11 x12=450

16 X

12 X 17 X 0 X 450

D4

15 x23=500 13 X 0 x43=50 550

Modul V : Solusi Program

Jumlah 19

800

14

600

11

550

0

50

X x24=100 x34=550 X 650

2.000 40

LANGKAH OPTIMASI : METODE MODI

Jumlah sel ini = 6 < m+n-1=7, timbul degenerasi. Ambil sel semu x22=0

u1=0

v1=12

v2=11

v3=14

v4=13

D1

D2

D3

D4

S1

12 x11=350

u2=1

S2 S3

16

SD Jumlah

Riset Operasi Prayudi

16 X

12 X22=0

X u4=-14

x12=450

18 X

u3=-2

11

X 0

x23=500 X

14

600

11

550

x34=550 0

0

X

X

x43=50

X

350

450

550

650

Modul V : Solusi Program

800

x24=100

13

0

19 X

15

17

Jumlah

50 2.000 41

LANGKAH OPTIMASI : METODE MODI Iterasi Menghitung ui dan vj Sel Isi Persamaan x11

u1+v1=12

x12

u1+v2=11

x22

u2+v2=12

x23

u2+v3=15

v3=14

x24

u2+v4=14

v4=13

x34

u3+v4=11

u3=-2

x43

u4+v3=0

u4=-14

Riset Operasi Prayudi

u1=0

v1=12 v2=11 u2=1

Modul V : Solusi Program

42

LANGKAH OPTIMASI : METODE MODI Evaluasi Sel Kosong Sel Kosong x13 x14 x21 x31 x32 x33

Perubahan Biaya k13 = c13 – u1 – v3 = 16 – 0 – 14 = 2 k14 = c14 – u1 – v4 = 19 – 0 – 13 = 6 k21 = c21 – u2 – v1 = 18 – 1 – 12 = 5 k22 = c22 – u2 – v2 = 16 – 1 – 11 = 4 k32 = c32 – u3 – v2 = 17 – (-2) – 11 = 8 k33 = c33 – u3 – v3 = 13 – (-2) – 14 = 1

x41

k41 = c41 – u4 – v1 = 0 – (-14) – 12 = 2

x42 x44

k42 = c42 – u4 – v2 = 0 – (-14) – 11 = 3 k44 = c44 – u4 – v4 = 0 – (-14) – 13 = 1

Karena semua perubahan biaya, k-ij > 0, maka tabel sudah optimum Riset Operasi Prayudi

Modul V : Solusi Program

43

INPUT PROGRAM LINDO Min 12x11 + 11x12 + 16x13 + 19x14 + 18x21 + 12x22 + 15x23 + 14x24 + 16x31 + 17x32 + 13x33 + 11x34 Subject to ! Kapasitas Tambang (Penawaran)

! Kebutuhan Pembangkit (Permintaan)

x11 + x12 + x13 + x14 = 800 x21 + x22 + x23 + x24 = 600 x31 + x32 + x33 + x34 = 550

Riset Operasi Prayudi

x11 x12 x13 x14

+ + + +

Modul V : Solusi Program

x21 x22 x23 x24

+ + + +

x31 x32 x33 x34

<= <= <= <=

350 450 550 650 44

SOLUSI PROGRAM LINDO OBJECTIVE FUNCTION VALUE 1) 24100.00 VARIABLE VALUE X11 350.000000 X12 450.000000 X13 0.000000 X14 0.000000 X21 0.000000 X22 0.000000 X23 500.000000 X24 100.000000 X31 0.000000 X32 0.000000 X33 0.000000 X34 550.000000

Riset Operasi Prayudi

REDUCED COST 0.000000 0.000000 2.000000 6.000000 5.000000 0.000000 0.000000 0.000000 6.000000 8.000000 1.000000 0.000

Modul V : Solusi Program

45

SOAL TUGAS 1 Unit Pembangkit Kebutuhan Pemasok Kapasitas (juta ton/th) (juta ton/th) ========================================== UBP-1 9A0 Andy 800 UBP-2 700 Rose 6A0 UBP-3 500 adit 600 UBP-4. 3B0 Wati 4B0 ========================================== Biaya transportasi batu bara dari masing-masing tambang milik Andy, Rose, Adir dan Wati, disajikan pada tabel berikut ini. (biaya dalam juta rupiah per ribu ton) Dari\ke UBP-1 UBP-2 UBP-3 UBP-4 Andy 11+A 13 13+A 5+2(A+B) Rose 10+B 5+A+B 10+B 10+A+2B Adit 8+2A 10+A 14 10+2A+B Wati 7+2B 9+2B 12+A+B 15 Riset Operasi Prayudi

Modul V : Solusi Program

46

SOAL TUGAS 2 PT. CUP-CUP mempunyai 3 buah Unit Bisnis Pembangkitan berbahan bakar gas. Kebutuhan gas per tahunnya adalah UBP-1 : 9A0 ribu ton, UBP-2 : 900 ributon, UBP-3 : 6B0 ribu ton. Untuk memenuhi kebutuhanmya, gas disuplay Pertamina yang ada di Sumut (S1 : 600), Sumsel (S2: 600), Kaltim (S3:6A0) dan Sumut (S4:8B0). Biaya transportasi gas dari sumber ke pembangkit, disajikan pada tabel berikut ini. (biaya juta rupiah per ribu ton) Dari\ke UBP-1 UBP-2 UBP-3 S1 11+A 13 13+A S2 10+B 5+A+B 10+B S3 8+2A 10+A 14 S4 7+2B 9+B 12+B a). Untuk meminimalkan biaya transportasi tentukanlah alokasi yang optimal b). Dari alokasi optimal tersebut, sumber mana yang mungkin tidak digunakan untuk mensuplay pembangkit CUP-CUP, dan berapa jumlahnya. Riset Operasi Prayudi

Modul V : Solusi Program

47

MODEL TAK SEIMBANG PERMINTAAN < PENAWARAN : PERMINTAAN SEMU D1 S1

D2 12

x11 S2

13 x12

18 x21

S3

x13

x22

x31

x23

x32

x33 14

x42

x43

x44

Jumlah 950

900

550

250

Modul V : Solusi Program

950

0

700

0

550

0

450

X34

x41

Riset Operasi Prayudi

0

X24 13

10

Jumlah

X14 15

17

12

DD 10

12

11

S4

D3

2.650 48

SOLUSI AWAL : METODE SEL BIAYA MINIMUM Iterasi

cij

xij

cij xij

1

c12=11

x12=450

4.950

c34=11

x34=550

6.050

2

c11=12

x11=350

4.200

3

c24=14

x24=100

1.400

4

c23=15

x23=500

7.500

5

c34= 0

x34=50

0

2.000

24.100

Jumlah

Catatan : Alokasi pengisian sel dummy, dengan biaya semu 0, dilakukan pada saat terakhir Riset Operasi Prayudi

Modul V : Solusi Program

49

LANGKAH OPTIMASI : METODE MODI Jumlah sel ini = 6 < m+n-1=7, timbul degenerasi. Ambil sel semu x41=0 D1 V1=0 S1 U1=12 S2 U2=14 S3 U3=11 S4 U4=12

D2 V2=–2

D3 V3=–2

12 X11=400

13 x12 12 X22=450

11 X31=550

Jumlah 950 Riset Operasi Prayudi

x23

x32

x33

950

0

700

0

550

0

450

X34 14

X42=450

x43

x44

900

550

250

Modul V : Solusi Program

0

X24=250 13

10

Jumlah

X14

15

17

12 X41=0

10 X13=550

18 x21

DD V4=–14

2.650 50

LANGKAH OPTIMASI : METODE MODI Jumlah sel ini = 6 < m+n-1=7, timbul degenerasi. Ambil sel semu x12=0 D1 V1=12 S1 U1=0 S2 U2=–1 S3 U3=–1 S4 S4=–3

D2 V2=13

D3 V3=10

12 X11=400

13 X12=0 12 X22=450

11 X31=550

Jumlah 950 Riset Operasi Prayudi

x23

x32

x33

950

0

700

0

550

0

450

X34 14

X42=450

x43

x44

900

550

250

Modul V : Solusi Program

0

X24=250 13

10

Jumlah

X14

15

17

12 X41

10 X13=550

18 x21

DD V4=1

2.650 51

Riset Operasi Prayudi

Modul V : Solusi Program

52