BAB III SOLUSI GRAFIK DAN METODE PRIMAL SIMPLEKS

Solusi Grafik dan Metode Primal Simpleks

BAB III SOLUSI GRAFIK DAN METODE PRIMAL SIMPLEKS

A. Metode Simpleks Metode simpleks yang sudah kita pelajari, menunjukkan bahwa setiap perpindahan tabel baru selalu membawa semua elemen yang terdapat dalam tabel. Dalam metode simpleks yang diperbaiki, setiap perpindahan tabel baru tidak semua elemen diperlukan. Informasi yang sangat diperlukan untuk berpindah dari satu tabel ke tabel berikutnya adalah : (1) Nilai pada baris Zj – Cj. (2) Kolom kunci (variabel yang akan masuk basis). (3) Variabel basis. (4) Nilai konstanta ruas kanan (b i) yang berkorespondensi dengan variabel basis. Selain keempat informasi tersebut, sebenarnya yang lain tidak diperlukan (tidak memiliki peran) dalam proses perpindahan tabel simpleks. Jika persoalan linier program cukup besar, hal ini akan menjadi tidak efisien jika membawa semua elemen ke dalam tabel berikutnya. Cara yang lebih efisien yang dapat digunakan untuk mengatasi permasalahan seperti diatas adalah dengan metode simpleks yang diperbaiki atau simpleks multiplier. Matriks dari bentuk standar linier program adalah sebagai berikut : Maksimum dk

Z

=

cx

Ax

=

bi

x

≥

0

di mana,

A= (m x m)

bi =

(m x 1)

a11 a21 .. .. am1

a12 a22 .. .. am2

b1 b2 .. .. bi

…. ….

….

x= (n x 1)

a1n a2n .. .. amn

x1 x2 .. .. xn

dan, c = (1 x n)

Teknik Riset Operasi- GRR

[ c1, c2, …….cn]

Page 14


Misalkan kolom yang berkorespondensi dengan matriks (A) dinyatakan dengan : Y1, Y2, …, Yn, di mana, a11 a21 .. .. am1

Y1 =

(m x 1)

a12 a22 .. .. am2

Y2 =

;

(m x 1)

a 1n a 2n .. .. amn

Y3 =

;

(m x 1)

Misalkan kita memiliki variabel basis x1, x2, …, xm, maka matriks basisnya adalah : a11 a21 .. .. am1

B = Y1, Y2, …Ym =

(m x n)

B invers = B

-1

B11 B21 .. .. Bm1

B =

Misalkan vektor (B) dipecah menjadi

…. ….

a12 a22 .. .. am2

B12 B22 .. .. Bm2

….

…. ….

….

a 1m a 2m .. .. amm

B 1m B 2m .. .. Bmm

B1

(n x 1)

BN

di mana B1 berkorespondensi dengan variabel basis, dan BN merupakan variabel nonbasis, maka :

B1 = (m x 1)


b1 b2 .. .. bm

dan

BN =

(n - mx1)

xm+1 xm+2 .. .. xm+n

Page 15


dengan demikian solusi basis optimum adalah :

-1

BI = B b i =

B11b1 + B21b1 + .. .. Bm1b1 +

B 12b2 + B 22b2 + .. .. Bm2b2 +

…. ….

….

+ B1m bm + B2m bm .. .. + Bmmbm

Misalkan CB merupakan koefisien fungsi tujuan untuk variabel basis, maka fungsi tujuan dari variabel basis adalah : Z = Cx = CB B I = c1b1 + c2b2 + … + cmbm

Untuk menguji apakah solusi telah optimum, perlu dihitung simpleks multiplier (π) = CBB-1. Koefisien fungsi tujuan yang baru = ĉj = πYi – cj. Oleh karena fungsi tujuan berbentuk maksimum, maka solusi optimum akan dicapai apabila ĉj ≥ 0. Jika solusi belum optimum, maka pilih salah satu nilai ĉj yang memiliki negatif terbesar, sebagai variabel masuk basis. Sedangkan variabel yang akan keluar basis perlu ditentukan kolom pivot dengan menggunakan rumus berikut :

Yjn = B-1Yjn =

â 1n â 2n .. .. âmn

Setelah itu uji perbandingan minimum untuk menentukan variabel yang akan keluar basis dengan rumus :

b2

b2 , untuk , i = 1,2, …, m.

= Minimum â2n

â2n

Proses ini diulangi sampai solusi optimum tercapai.


Page 16

Solusi Grafik dan Metode Primal Simpleks Contoh 1 :

Penyelesaian LP dengan Rivised Simpleks, pada prinsipnya sama dengan metode simpleks terdahulu. Akan tetapi kita hanya menghitung informasi yang penting saja pada setiap perpindahan tabel baru. Maksimum Z = 40X1 + 25X2 + 0S 1 + 0S2 Dk.

[1]

3X1 + 2X2 + S1 =

[2]

8X 1501 + 2X2 + S2 =

[3] 200 Untuk melihat hasil perhitungan dengan Rivised Simpleks, terlebih dahulu kita akan X1, X2, S1, S2 ≥ 0 selesaikan dengan metode simpleks biasa, sebagai perbandingan. Cj

CB

Basis

0

S1

150

S2

200

Zj-Cj

0

0

bi

Cj

40 X1

25 X2

0 S1

0 S2

Indeks

3

2

1

0

150:3=50

8

2

0

1

200:8=25

-40

-25

0

0

40 X1

25 X2

0 S1

0 S2

Indeks

CB

Basis

0

S1

75

0

5/4

1

-3/8

75:1,25=60

40

X1

25

1

¼

0

1/8

25:0,25=100

Zj-Cj

1000

0

-15

0

5

40 X1

25 X2

0 S1

0 S2

bi

Cj

CB

Basis

25

X2

60

0

1

0,8

-0,3

40

X1

10

1

0

-0,2

0,2

Zj-Cj

1900

0

0

12

0,5

bi

Indeks

Solusi optimum permasalahan diatas adalah X1 = 10, X2 = 60 dengan nilai Z = 1.900. Dalam rivised simpleks, tidak semua angka yang terdapat dalam tabel diatas kita perlukan. Jika, kolom X1, X2, S1 dan S2 kita kita sebut Y1, Y2, Y3 dan Y4. Konstanta nilai kanan kita sebut bi, dan koefisien fungsi tujuan kita sebut C1, C2, C3, dan C4, maka angka-angka tersebut dapat dibuat sebagai berikut : Y1 =

3 8

, Y2 =

2 2

, Y3 =

1 0

, Y4 =

0 1

.

; C1 = [40], C2 = [25], C3 = [0], C4 = [0]. bi =

150 200


Page 17


Sehingga tabel awal metode rivesed simpleks adalah : basis

B

-1

bi

S1

1

0

150

S2

0

1

200

Dalam tabel 1 variabel basis adalah S1 dan S2 dengan koefisien fungsi tujuan C3 dan C4. Simpleks multiplier = π = CBB-1, dimana CB = [C3,C4] = [0,0]. Simpleks multiplier = π = [0,0] 3

C1 = π Y1 – C1 = [0,0]

8 2

C2 = π Y2 – C2 = [0,0]

2

1 0 0 1

= [0,0]

- 40 = - 40.

- 25 = - 25.

Oleh karena C1 memiliki angka negatif terbesar, maka X1 masuk basis (menjadi kolom kunci). Untuk menentukan variabel yang akan keluar basis (baris kunci) adalah memilih angka terkecil dari (aturan perbandingan minimum) bi : Y1. bi Minimum =

Y1

S1

150 3 50 : = 200 8 25

S 2 Keluar basis

Pada tabel berikutnya, variabel basis menjadi S 1 dan X1, oleh karena itu matriks basis berubah menjadi : B = [Y3,Y1] =

1 3 0 8

Invers matriks basisnya adalah : 8

1

-1

B =

1x8

0x3

0

3 1

=

1 0

3 1

8

8

Berdasarkan teori matriks, setiap nilai pada tabel berikutnya dapat diperoleh dengan mengalikan kolom persamaan asal dengan invers matriks basisnya.

bi = B-1bi =

1 0

3 1

8

8

150 200

=

75

S1

25

X1

Perhitungan diatas menghasilkan tabel kedua simpleks yang diperbaiki berikut : Teknik Riset Operasi- GRR

Page 18

Solusi Grafik dan Metode Primal Simpleks basis

©

B

-1

bi

S1

1

-3/8

75

X1

0

1/8

25

Apakah tabel dua tersebut sudah optimum ? Untuk menjawab pertanyaan tersebut,

perlu dihitung nilai Cj

baru yang berkorespondensi dengan variabel non basis

yaitu X2 dan S2 sebagai berikut. Simpleks multiplier = π = CBB-1, dimana CB = [0,40]. π = [0,40]

1

3

0

1

8

= [0,5]

8

C2 = π Y1 – C1 = [0,5]

2

C4 = π Y2 – C2 = [0,5]

0

2

1

- 25 = - 15.

- 0 = 5.

Tabel akan optimum apabila nilai C j ≥ 0. Berarti tabel 2 belum optimum, karena nilai C2 yang baru masih negatif 15 yang berkorespodensi dengan variabel keputusan X2. Pada tabel selanjutnya X2 masuk basis (kolom kunci). Untuk menentukan variabel mana diantara S1

dan X1 yang akan keluar basis (baris kunci), dipilih dari hasil

minimum bi : Y2. Nilai vektor kolom baru yang berkorespondensi dengan X2 adalah Y2 = B-1Y2.

Y2 =

1 0

3 1

2

8

2

8

5

=

4

1 4

Variabel yang akan keluar basis adalah : bi Minimum =

75 : 25

Y2 5 1

4

=

4

60 100

S1 Keluar basis X1

Variabel basis yang baru menjadi X2 dan X1, dan menghasilkan matriks basis seperti berikut : B = [Y2,Y1] =

2 3 2 8

Invers matriks basisnya adalah : Teknik Riset Operasi- GRR

Page 19

Solusi Grafik dan Metode Primal Simpleks 8

1

B-1 =

2x8

2x3

2

3

4

=

2

3

5 1

5

10

1 5

Nilai konstanta ruas kanan yang baru (bi ) untuk tabel berikutnya adalah :

bi = B-1bi =

4

5 1 5

3

10

150 200

1 5

=

60

X2

10

X1

Hasil perhitngan diatas dapat dibuat dalam tabel simpleks yang diperbaiki seperti berikut ini : Tabel 3. Tabel ketiga simpleks diperbaiki basis

©

B

-1

bi

X2

4/5

-3/10

60

X1

-1/5

1/5

10

Apakah tabel tiga tersebut sudah optimum ? Untuk menjawab pertanyaan tersebut,

perlu dihitung nilai Cj baru yang berkorespondensi dengan variabel non basis (S1 dan S2). Simpleks multiplier = π = CBB-1, dimana CB = [25,40]. 4

π = [25,40]

5 1 5

3

10

1 5

C3 = π Y3 – C3 = [12;0,5] C4 = π Y4 – C4 = [12;0,5]

= [12;0,5]

1 0 0 1

- 0 = 12.

- 0 = 0,5.

Tabel akan optimum apabila nilai Cj ≥ 0. Oleh karena nilai baru dari C3 dan C4 yang baru positif 12 dan 0,5, maka tabel 3 adalah optimum, dengan nilai X1 dan X2 masing-masing adalah 10 dan 60. Sehingga nilai Z maksimum adalah 40(10) + 25(60) = 1.900.

Solusi optimum metode simpleks diperbaiki sama dengan solusi optimum metode simpleks biasa. Akan tetapi penggunaan

metode simpleks yang diperbaiki jauh

lebih efisien jika dikerjakan secara manual.


Page 20

Solusi Grafik dan Metode Primal Simpleks Contoh 2 :

Maximum Z = 50X1 + 80X2 + 0S1 + 0S2 - MA1 - MA2 Dk.

[1] X1 + S1 X 2 - S 2 + A1 = 20 [3] X2 + A2 = 50 [4] S1, S2, A1, A2 ≥ 0

= 40 [2] X1 + X1, X 2,

Misalkan Y1, …, Y6 menunjukkan kolom yang berkorespondensi dengan X1, X2, S1, S2, A1, A2 dan bi berkorespondensi dengan konstanta ruas kanan, maka : 1

0

Y1 = 0 , Y2 =

1

0

1 , Y3 = 0 , Y4 =

1

1

0

0

1 , Y5 =

0

40

1 , Y6 = 0 , dan bi = 20

0

0

1

50

Variabel basis awalnya adalah S 1, A1 dan A2, sehingga tabel awal simpleks yang diperbaiki adalah sebagai berikut : Tabel 1. Tabel awal simpleks diperbaiki basis

B

-1

bi

S1

1

0

0

40

A1

0

1

0

20

A2

0

0

1

50

Variabel manakah yang masuk basis ? Karena fungsi tujuan berbentuk maximum, maka variabel yang memiliki nilai Cj negatif terbesar adalah variabel yang akan masuk basis. Simpleks multiplier = π = CBB-1, dimana CB = [0,-M,-M] 1 0 0 π = [0,-M,-M] 0

1 0 = [0,-M,-M]

0 0

1

Cj = π Yj – Cj 1 1.

C 1 = [0,-M,-M] 0

- 50 = - M – 50

1 0 2.

C 2 = [0,-M,-M] 1

- 80 = - 2M – 80

1 Teknik Riset Operasi- GRR

Page 21


1 3.

C 3 = [0,-M,-M] 0

-0=0

0 0 4.

C 4 = [0,-M,-M]

1 -0=M 0

5.

C 5 = [0,-M,-M]

0 1 - (-M) = 0 0 0

6.

C 6 = [0,-M,-M] 0

- (-M) = 0

1

C2 menghasilkan angla negatif terbesar yaitu – 2M – 80, oleh karena itu variabel X2 masuk basis. Variabel manakah diantara S1, A1 dan A2 yang akan keluar basis ? adalah hasil minimum dari bi : Y2, atau 40

0

S1

20 : 1 = 20

Minimum =

50

1

A1 Keluar basis A2

50

Pada tabel pertama variabel basisnya adalah S1, A1 dan A2 yang berarti matriks basisnya adalah Y3, Y5, dan Y6 atau : 1 0 B= 0

0

baris 1

1 0

baris 2

0 0

1

baris 3

Untuk mencari invers matriks basis (B-1) dapat dilakukan dengan operasi pivot, di mana kolom pivotnya adalah kolom Y2. 1. Kalikan baris 2 dengan nol, kemudian hasilnya tambahkan dengan baris 1. Baris 2 = [0 1 0] x 0 Baris 1

= [0 0 0] = [1 0 0]

Nilai baru

= [1 0 0]

+

2. Bagi baris 2 dengan satu. Baris 2 = [0 1 0] : 1

= [0 1 0]

3. Kalikan baris 2 dengan minus satu, kemudian hasilnya tambahkan dengan baris 3. Teknik Riset Operasi- GRR

Page 22

Solusi Grafik dan Metode Primal Simpleks Baris 2 = [0 1 0] x – 1 3

= [0 -1 0] Baris = [0 0 1] + = [0 -1 1]

Nilai baru baris 3

-1

Dengan demikian, B =

1

0

0

0

1

0

0

1 1

Nilai konstanta ruas kanan yang baru dapat dicari dengan cara :

bi = B-1bi 1

bi =

0 0

0

0

40

40

S1

1

0

20 = 20

X2

50

A2

1 1

30

Hasil perhitungan di atas dapat dibuat dalam tabel kedua simpleks diperbaiki seperti berikut : Tabel 2. Tabel kedua simpleks diperbaiki B-1

basis

bi

S1

1

0

0

40

X2

0

1

0

20

A2

0

-1

1

30

Apakah tabel 2 tersebut sudah optimum ?, lihat proses berikut ini : Simpleks multiplier = π = CBB-1, dimana CB = [0,80,-M] 1 [0,80,-M] 0

0

0

0

1

0 = [0, 80+M, -M]

1 1

B. Metode Dual Simpleks

Prosedur perhitungan yang dibicarakan sejauh ini bergerak dari solusi dasar layak yang belum optimum ke solusi layak yang lain. Apakah proses tersebut akhirnya akan mencapai suatu solusi layak optimum, adalah tergantung pada kemampuan

untuk

mendapatkan suatu solusi dasar awal yang layak. Dalam kaitan ini, artificial variabel kadang-kadang digunakan untuk menemukan solusi awal

layak.

Jika

formulasi LP mengandung sejumlah besar artificial variable, maka membutuhkan banyak perhitungan untuk memperoleh solusi awal layak. Teknik Riset Operasi- GRR

Page 23


Karena itu, akan dijelaskan suatu prosedur perhitungan yang memberikan suatu solusi layak dinamakan

optimum,

meskipun

solusi awalnya

dual simplex algorithm yang pertama

tidak

layak. Prosedur

itu

kali disusun oleh Lemke.

Algoritma ini tidak banyak digunakan di antara program-program komputer yang ada. Namun ia memainkan peranan penting dalam post optimality analysis .

Berikut ini disajikan contoh bagaimana metode itu bekerja :

Contoh : Minimumkan

Z

=

4X 1 +

Dengan s yarat

3X 1 X1 X1 X1 Langkah pertama adalah mengubah semua

+ + + ;

2X 2

X2 X2 2X 2 X2 kendala

≥ 27 ≥ 21 ≥ 30 ≥ 0 menjadi pertidaksamaan ≤ (agar

tidak membutuhkan artificial variable) dan kemudian tambahkan variabel slack. Sehingga diperoleh : Minimumkan Dengan syarat

Z

=

4X 1 + - 3X 1 - X1 - X1 -

2X 2 X2 + S1 X2 + S2 2X 2 + S3 X1, X2, S 1, S2, S 3,

≤ ≤ ≤ ≥

- 27 - 21 - 30 0

Jika bentuk baku di atas diekspresikan sebagai suatu tabel simplex awal, maka akan terlihat bahwa variabel slack (S1 , S 2 , S 3) tidak memberikan solusi awal layak. Karena ini merupakan masalah minimisasi sementara semua koefisien pada persamaan Z adalah ≤ 0, maka solusi awal S 1=-27, S 2 =-21, S3 =-30 adalah optimum tetapi tak layak. Masalah ini merupakan c iri khas dari mas alah yang dapat diselesaikan dengan metode dual simplex . Tabel solusi awal optimum tapi tak layak adalah :


Page 24


Tabel 1. Tabel Awal

Basis Z S1

X1 -4 -3

X2 -2 -1

S1 0 1

S2 0 0

S3 0 0

Solusi 0 - 27

S2 S3

-1 -1

-1 -2

0 0

1 0

0 1

- 21 - 30

Seperti dalam metode simplex, metode ini didasarkan pada optimality and feasibility condition. Optimality condition menjamin bahwa solusi selalu tetap optimum,

s

ementara feasibility condition memaks a solusi dasar menc apai ruang layak.

Feasibility Condition : leav ing variable adalah v ariabel basis yang memiliki nilai negatif terbesar (nilai kembar dipilih secara sembarang). Jika semua variabel

basis

non negatif,

proses

berakhir

dan solusi layak yang telah

optimum tercapai.

Optimality Condition : entering v ariable dipilih dari v ariabel non basis dengan cara seperti berikut. Buat rasio antara koefisien pers amaan Z dengan koefisien persamaan yang berhubungan pada leaving variable. Abaikan rasio dengan penyebut positif atau nol. Bagi masalah mini mis asi, entering variable adalah salah satu yang

memiliki

ras io

terkecil,

atau

absolut

rasio

terkecil

untuk mas alah

maksimisasi (rasio kembar dipilih sec ara s embarang). Jika semua penyebut adalah nol atau positif, berarti masalah itu tidak memiliki solusi layak.

Setelah memilih entering and leav ing variable, metode Gauss Jordan (operasi baris) diterapkan seperti biasa untuk memperoleh solusi berikutnya. Leaving variable pada Tabel 1 adalah S 3

(=-30), karena ia memiliki nilai negatif terbesar.

Untuk menentukan entering v ariable, rasionya diperoleh dengan cara berikut :

Variabel Persamaan Z Persamaan S 3

X1 -4 -1

X2 -2 -2

Ras io

4

1


S1 0 0

S2 0 0

S3 0 1

Page 25


Entering v ariable adalah X2 karena ia memiliki ras io terkecil yaitu 1. Dengan menerapkan operasi baris seperti biasa diperoleh tabel berikut :

Tabel 2. Iterasi Pertama

Basis Z S1 S2

X1 -3 - 2,5 - 1/2

X2 0 0 0

S1 0 1 0

S2 0 0 1

S3 -1 -1/2 - 1/2

Solusi 30 - 12 -6

X2

1/2

1

0

0

- 1/2

15

Solusi baru mas ih optimum tetapi tak layak (S 1 =-12, S 2=-6). Kemudian S 1 dipilih sebagai leav ing v ariable dan X1 sebagai entering v ariable. Ini memberikan iterasi seperti berikut :

Tabel 3. Iterasi Kedua

Basis Z X1 S2 X2

X1 0 1 0 0

X2 0 0 0 1

S1 - 1,2 - 0,4 - 0,2 - 0,2

S2 0 0 1 0

S3 - 0,4 0,2 - 0,4 - 0,6

Solusi 44,4 4,8 - 3,6 12,6

Pada iterasi kedua belum diperoleh solusi layak (S 2 = - 3,6). Karena S 2 adalah satusatunya yang bernilai negatif, dengan sendirinya ia menjadi leaving variabel dan S 3 sebagai entering variabel, ini memberikan iterasi seperti berikut :

Tabel 4. Iterasi Ketiga

Basis Z X1 S3 X2

X1 0 1 0 0

X2 0 0 0 1

S1 -1 - 1/2 1/2 1/2

S2 -1 1/2 - 2,5 - 1,5

S3 0 0 1 0

Solusi 48 3 9 18

Tabel Iterasi Ketiga merupakan tabel optimum dan layak dengan nilai fungsi tujuan adalah 48. Teknik Riset Operasi- GRR

Page 26


C. Metode Simpleks Primal Maksimumkan

: Z = 40X1 + 30X2 + 50X3

Batasan

: 1. 6X1 + 4X2 + X3 ≤ 32000 2. 6X1 + 7X2 + 3X3 ≤ 16000 3. 4X1 + 5X2 + 12X3 ≤ 24000 4. X1, X2, X3 ≥ 0

Langkah-langkah penyelesaian dengan metode simpleks primal: 1. Merubah

model

matematika

menjadi

bentuk

baku

simpleks

dengan

cara

menambahkan batasan dengan variable slack pada pertidaksamaan lebih kecil sama dengan atau mengurangi dengan variable surplus pada pertidaksamaan lebih besar sama dengan. + variable slack pada batasan ≤ - Variable surplus pada batasan ≥ Bentuk baku simpleks: Maksimumkan

: Z - 40X1 - 30X2 - 50X3 – 0S1 - 0S2 – 0S3 = 0

Batasan

: 1. 6X1 + 4X2 + X3 + S1 = 32000 2. 6X1 + 7X2 + 3X3 + S2 = 16000 3. 4X1 + 5X2 + 12X3 + S3 = 24000

2. Buat tabel awal simpleks Dasar

Z

X1

X2

X3

S1

S2

S3

Pemecahan Rasio

Z

1

-40

-30

-50

0

0

0

0

0

S1

0

6

4

1

1

0

0

32000

32000

S2

0

6

7

3

0

1

0

16000

5333

S3

0

4

5

12

0

0

1

24000

2000


Page 27


3. Tentukan kolom masuk. Pada kasus maksimalisasi, kolom masuk merupakan nilai negatif terbesar pada persamaan Z atau baris Z pada table simpleks, sehingga X3 merupakan kolom masuk. 4. Tentukan kolom keluar atau persamaan pivot. Merupakan nilai positif terkecil dari rasio antara pemecahan dengan elemen pada kolom masuk, sehingga: Pemecahan

Kolom masuk (X3)

Rasio

32000

1

32000/1 = 32000

16000

3

16000/3 = 5333

24000

12

24000/12 = 2000

Variable nondasar X3 akan menggantikan variable dasar S3 pada table simpleks iterasi pertama. 5. Tentukan elemen pivot. Merupakan angka pada perpotongan kolom masuk dan kolom keluar, sehingga elemen pivot = 12. 6. Mencari persamaan pivot baru. Persamaan pivot baru = persamaan pivot lama / elemen pivot Persamaan Pivot lama (a) Elemen pivot (b) Persamaan pivot baru (a/b)

0

4

5

12

0

0

1

24000

12

12

12

12

12

12

12

12

0

1/3

5/12

1

0

0

1/12

2000

7. Mencari persamaan variable dasar baru. Pada kasus diatas yang merupakan variable dasar adalah Z, S1, dan S2. Variable dasar baru = variable dasar lama – (elemen kolom masuk x persamaan pivot baru.


Page 28


a. Persamaan Z baru: Persamaan Z lama (a)

1

-40

-30

-50

0

0

0

0

Elemen kolom masuk

-50

-50

-50

-50

-50

-50

-50

-50

Persamaan pivot baru (c)

0

1/3

5/12

1

0

0

1/12

2000

b x c = (d)

0

-50/3

-250/12

-50

0

0

-50/12

-100000

Persamaan Z baru (a-d)

1

-70/3

-55/6

0

0

0

25/6

100000

pada variable dasar Z (b)

b. Persamaan S1 baru: Persamaan S1 lama (a)

0

6

4

1

1

0

0

32000

Elemen kolom masuk

1

1

1

1

1

1

1

1


0

1/3

5/12

1

0

0

1/12

2000

b x c = (d)

0

1/3

5/12

1

0

0

1/12

2000

Persamaan S1 baru (a-d)

0

17/3

43/12

0

1

0

-1/12

30000

Persamaan S2 lama (a)

0

6

7

3

0

1

0

16000

Elemen kolom masuk

3

3

3

3

3

3

3

3


0

1/3

5/12

1

0

0

1/12

2000

b x c = (d)

0

1

5/4

3

0

0

1/4

6000


0

5

23/4

0

0

1

-1/4

10000

pada variable dasar S1 (b)

c. Persamaan S2 baru:


8. Table simpleks iterasi pertama: Dasar

Z

Z

1

S1

X1

X2

Pemecahan Rasio

X3

S1

S2

S3

-70/3 -55/6

0

0

0

25/6

100000

0

17/3

43/12

0

1

0

-1/12

30000

5294

S2

0

5

23/4

0

0

1

-1/4

10000

2000

X3

0

1/3

5/12

1

0

0

1/12

2000

6000

9. Kondisi optimum pada kasus maksimalisasi diperoleh ketika persamaan Z atau baris Z tidak memilik angka yang bernilai negative. Apabila kondisi optimum belum diperoleh maka kembali ke langkah 3. Teknik Riset Operasi- GRR

Page 29


Pemecahan

Kolom masuk (X3)

Rasio

30000

17/3

5294

10000

5

2000

2000

1/3

6000

10. Elemen pivot = 5 11. Persamaan pivot baru Persamaan Pivot lama (a)

0

5

23/4

0

0

1

-1/4

Elemen pivot (b)

5

5

5

5

5

5

5

Persamaan pivot baru (a/b)

0

1

23/20

0

0

1/5

-1/20

10000 5 2000

12. Persamaan variabel dasar baru a. Persamaan Z baru Persamaan Z lama (a)

1

-70/3

-55/6

0

0

0

25/6

100000

Elemen kolom masuk

-70/3

-70/3

-70/3

-70/3

-70/3

-70/3

-70/3

-70/3


0

1

23/20

0

0

1/5

-1/20

2000

b x c = (d)

0

-70/3

-161/6

0

0

-14/3

7/6

-140000/3

Persamaan Z baru (a-d)

1

0

53/3

0

0

14/3

3

440000/3

pada variable dasar Z (b)

b. Persamaan S1 baru Persamaan S1 lama (a)

0

17/3

43/12

0

1

0

-1/12

30000

Elemen kolom masuk

17/3

17/3

17/3

17/3

17/3

17/3

17/3

17/3


0

1

23/20

0

0

1/5

-1/20

2000

b x c = (d)

0

17/3

391/60

0

0

17/15

-17/60

34000/3


0

0

-44/15

0

1

-17/15

1/5

56000/3

0

1/3

5/12

1

0

0

1/12

1/3

1/3

1/3

1/3

1/3

1/3

1/3


0

1

23/20

0

0

1/5

-1/20

2000

b x c = (d)

0

1/3

23/60

0

0

1/15

-1/60

2000/3

Persamaan X3 baru (a-d)

0

0

1/30

1

0

-1/15

1/10

4000/3


c. Persamaan X3 baru Persamaan X3 lama (a) Elemen kolom masuk

2000 1/3

pada variable dasar X3 (b)


Page 30


13. Table simpleks iterasi kedua - optimum Dasar

Z

X1

X2

X3

S1

S2

S3

Pemecahan

Z

1

0

53/3

0

0

14/3

3

440000/3

S1

0

0

-44/15

0

1

-17/15

1/5

56000/3

X1

0

1

23/20

0

0

1/5

-1/20

2000

X3

0

0

1/30

1

0

-1/15

1/10

4000/3

14. Table simplek iterasi kedua diatas sudah optimum karena variable nondasar pada persamaan Z sudah bernilai positif, sehingga: X1 = 2000 X3 = 4000/3 Z = 440000/3 15. Pada table optimum S2 dan S3 = 0. Artinya persediaan sumber daya kedua dan ketiga habis digunakan, tetapi masih memiliki sumber daya pertama (S1) sebesar 56000/3 karena tidak digunakan.


Page 31


Page 32



Page 33

BAB III SOLUSI GRAFIK DAN METODE PRIMAL SIMPLEKS

Recommend Documents