9. penentuan solusi optimal

7/24/2019 9. Penentuan Solusi Optimal

1/25

PENENTUAN SOLUSIOPTIMAL


2/25

Metode

Ada dua metode yang dapat digunakanuntuk menentukan solusi optimal, yaitu :

Metode Stepping Stone Metode Modifed Distribution (Modi)

Prinsip perhitungan kedua metode untukmenentukan sel masuk adalah sama.

Perbedaannya adalah metode Modi

menggunakan prinsip dasar primal-dualmetode simpleks, sedangkan metodestepping stone tidak.


3/25

Metode Modifkasi Distribusi (Modi)

ontoh :


4/25


5/25


6/25

Solusi optimal ter!apai "ika untuk :

Maksimasi, ui# $"% !i"& '

Minimasi , ui# $"% !i" '

angkah-langkah penyelesaian :

*. Penentuan sel masuk+ntuk setiap sel basis, hitung ui# $" !i".ui

menun"ukkan baris ke-i, $"menun"ukkan kolom

ke-" dan !i"adalah biaya pada sel i" (baris i

kolom ") karena "umlah $ariabel yang tidakdiketahui (uidan $") lebih banyak

dibandingkan "umlah persamaan yangdibentuk, maka salah satu $ariabel

diasumsikan bernilai '.


7/25

+ntuk setiap sel non basis, hitung !p ui# $"% !i" +ntuk maksimasi, sel masuk adalah sel dengan nilai

!ppaling negati/ sedangkan untuk minimasi, selmasuk adalah sel dengan nilai !ppaling positi/.

0. Penentuan sel keluar

penentuan sel keluar dilakukan denganmenggunakan loop tertutup. A1al dan akhir loopadalah sel masuk. 2aris-garis hori3ontal ataupun$ertikal yang membentuk loop harus berakhir (u"unga1al ataupun akhir garis) pada sel basis, ke!ualia1al dan akhir loop pada sel masuk.

4. Periksa apakah sudah optimal. Syarat optimaldipenuhi "ika !ptidak ada yang bernilai negati/

untuk maksimasi dan tidak ada yang bernilai positi/untuk minimasi.


8/25

Contoh Kasus

Solusi a1al yang digunakan adalah solusi yangdiperoleh dengan menggunakan sudut barat lautsebelumnya. Solusi a1al adalah sbb :


9/25

5terasi * :

Sel basis adalah sel **, *0, 00, 04, 44, 46,

47, sel non basis adalah *4, *6, *7, 0*, 06,07, 4*,40.

*. Penentuan sel masuk

+ntuk setiap sel basis :u*# $* 0 u*# $0 7 u0# $0 *'

u0# $4 4 u4# $4 8 u4# $6 8

u4# $7 6Misalkan u* ' maka $* 0 $0 7 u0

7 $4 -0 u4 9 $6 -0 $7 -6.


10/25

0. +ntuk setiap sel non basis :

!*4 u*# $4% !*4 ' % 0 % 8 -9

!*6 u*# $6% !*6 ' % 0 % 4 -7

!*7 u*# $7% !*7 ' % 6 % 7 -

!0* u0# $*% !0* 7 # 0 % 8 *

!06 u0# $6% !06 7 % 0 % 4 '

!07 u0# $7% !07 7 % 6 % ; -8

!4* u4# $*% !4* 9 # 0 % ** - *

!40 u4# $0% !40 9 # 7 % 9 7


11/25

0. Penentuan Sel


12/25


13/25

Alokasi pada iterasi pertama adalah : Dari pabrik A ke gudang * sebesar 4'' unit, biaya

?p.8'.'''.''' Dari pabrik A menu"u gudang 0 sebesar 0'' unit,

biaya ?p.*''.'''.''' Dari pabrik @ menu"u gudang 0 sebesar *'' unit,

biaya ?p.*''.'''.''' Dari pabrik @ menu"u gudang 4 sebesar 0'' unit,

biaya ?p.8'.'''.''' Dari pabrik menu"u gudang 0 sebesar *'' unit,

biaya ?p.*''.'''.''' Dari pabrik menu"u gudang 6 sebesar 4'' unit,

biaya ?p.*9'.'''.''' Dari pabrik menu"u gudang 7 sebesar 0'' unit,

biaya ?p.9'.'''.'''

otal biaya ?p. 89'.'''.'''


14/25

5terasi 0 :

*.Penentuan sel masuk. Sel basis adalah sel **,*0,00, 04, 40, 46dan 47

u*# $* 0 u*# $0 7 u0# $0 *'

u0# $4 4 u4# $4 7 u4# $6 8u4# $7 6

Misal u* ' maka $* 0 $0 7 u0 7

$4 -0 u4 ' $6 8 $7 6.


15/25

0. +ntuk setiap sel non basis adalah sel*4,*6,*7, 0*, 06, 07, 4*, dan 44

!*4 u*# $4% !*4 ' % 0 % 8 -9!*6 u*# $6% !*6 ' # 8 % 4 4

!*7 u*# $7% !*7 ' # 6 % 7 -*

!0* u0# $*% !0* 7 # 0 % 8 *!06 u0# $6% !06 7 # 8 % 4 9

!07 u0# $7% !07 7 # 6 % ; 0

!4* u4# $*% !4* ' # 0 % ** - !40 u4# $0% !40 ' % 0 % 8 -9


16/25



17/25

Dari pabrik A menu"u gudang * sebesar 4'' unit,biaya ?p.8'.'''.'''

Dari pabrik A menu"u gudang 0 sebesar 0'' unit,biaya ?p.*''.'''.'''

Dari pabrik @ menu"u gudang 4 sebesar 0'' unit,biaya ?p.8'.'''.'''

Dari pabrik @ menu"u gudang 6 sebesar *'' unit,biaya ?p.4'.'''.'''

Dari pabrik menu"u gudang 0 sebesar 0'' unit,biaya ?p.*''.'''.'''

Dari pabrik menu"u gudang 6 sebesar 0'' unit,biaya ?p.*0'.'''.'''

Dari pabrik menu"u gudang 7 sebesar 0'' unit,biaya ?p.9'.'''.'''

otal biaya ?p 77'.'''.'''


18/25

5terasi 4 :

*.Penentuan sel masuk

. Sel basis adalah sel **, *0, 04, 06, 40,46 dan 47

u*# $* 0 u*# $0 7 u0# $4 4

u0# $6 4 u4# $0 7 u4# $6 8u4# $7 6

Misal u* ' maka $* 0 $0 7 u0 -4

$4 8 u4 ' $6 8 $7 6.


19/25

0. +ntuk setiap sel non basis adalah sel *4,*6, *7, 0*, 00, 07, 4*, dan 44

!*4 u*# $4% !*4 ' % 8 % 8 - *0!*6 u*# $6% !*6 ' # 8 % 4 4

!*7 u*# $7% !*7 ' # 6 % 7 -*

!0* u0# $*% !0* -4 # 0 % 8 - ;!06 u0# $0% !00 -4 # 7 % *' - 9

!07 u0# $7% !07 -4 # 6 % ; - 8

!4* u4# $*% !4* ' # 0 % ** - !40 u4# $4% !44 ' % 8 % 8 - *0


20/25



21/25


Dari pabrik A menu"u gudang 6 sebesar 0'' unit,

biaya ?p.8'.'''.''' Dari pabrik @ menu"u gudang 4 sebesar 0'' unit,

biaya ?p.8'.'''.''' Dari pabrik @ menu"u gudang 6 sebesar *'' unit,

biaya ?p.4'.'''.''' Dari pabrik menu"u gudang 0 sebesar 6'' unit,

biaya ?p.0''.'''.''' Dari pabrik menu"u gudang 7 sebesar 0'' unit,


biaya ?p.9'.'''.''' otal biaya ?p 6'.'''.'''


22/25

5terasi 6 :

*.Penentuan sel masuk

. Sel basis adalah sel **, *0, *6, 04, 06,40 dan 47

u*# $* 0 u*# $0 7 u*# $6 4

u0# $4 4 u0# $6 4 u4# $0 7u4# $7 6

Misal u* ' maka $* 0 $0 7 u0 '

$4 4 u4 ' $6 4 $7 6.


23/25

0. +ntuk setiap sel non basis adalah sel *4, *7,0*, 00, 07, 4*, 44 dan 46

u*# $4% !*4 ' # 4 % 8 - 4

u*# $7% !*7 ' # 6 % 7 -*

u0# $*% !0* ' # 0 % 8 -6

u0# $0% !00 ' # 7 % *' - 7

u0# $7% !07 ' # 6 % ; - 4u4# $*% !4* ' # 0 % ** -

u4# $4% !44 ' # 4 % 8 - 4

u4# $6% !46 ' # 6 % 8 - 0


24/25


Dari pabrik A menu"u gudang 6 sebesar 0'' unit,

biaya ?p.8'.'''.''' Dari pabrik @ menu"u gudang 4 sebesar 0'' unit,

biaya ?p.8'.'''.''' Dari pabrik @ menu"u gudang 6 sebesar *'' unit,

biaya ?p.4'.'''.''' Dari pabrik menu"u gudang 0 sebesar 6'' unit,

biaya ?p.0''.'''.''' Dari pabrik menu"u gudang 7 sebesar 0'' unit,


biaya ?p.9'.'''.''' otal biaya ?p 6'.'''.'''


25/25

Kesi!u"an

Solusi a1al yang dihasilkanmenggunakan metode biaya terke!il danpendekatan $ogel.

Solusi optimal pada Modi sama dengansolusi a1al yang dihasilkan dengan keduametode tersebut.

Metode pendekatan $ogel dapatmenghasilkan solusi a1al yang "auh lebihbaik dibandingkan dengan metode biayaterke!il untuk kasus yang lebih kompleks

9. penentuan solusi optimal

Documents