solusi grafik dan metode primal...

Solusi Grafik dan Metode Primal Simpleks

Teknik Riset Operasi- GRR 4

a11 a12 …. a1n

a21

..

a22

..

…. a2n

..

.. .. ..

am1 am2 …. amn

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 (bi) 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 Z = cx

dk Ax

x

=

≥

bi

0

di mana,

A = (m x m)

b1 x1

b2 x = x2

bi = (m x 1)

.. (n x 1) ..

.. ..

bi xn

dan, c =

(1 x n)

[ c1, c2, …….cn]


Teknik Riset Operasi- GRR Page 15

a11 a12 …. a1m

a21 a22 …. a2m

.. .. ..

.. .. ..

am1 am2 …. amm

..

Misalkan kolom yang berkorespondensi dengan matriks (A) dinyatakan dengan : Y1,

Y2, …, Yn, di mana,

a11 a12 a1n

a21 a22 a2n

Y1 = (m x 1) .. ;

..

Y2 = (m x 1) .. ;

..

Y3 = (m x 1)

..

am1 am2 amn

Misalkan kita memiliki variabel basis x1, x2, …, xm, maka matriks basisnya adalah :

B = Y1, Y2, …Ym = (m x n)

B invers = B-1

B11 B12 …. B1m

B21 B22 …. B2m

.. .. ..

.. .. ..

Bm1 Bm2 …. Bmm

Misalkan vektor (B) dipecah

menjadi

B = B1

(n x 1)

BN

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

b1 xm+1

b2 xm+2

B1 = (m x 1)

.. dan

..

BN = (n - mx1) ..

..

bm xm+n



B11b1 + B12b2 + …. + B1mbm

B21b1 + B22b2 + …. + B2mbm

.. .. ..

.. .. ..

Bm1b1 + Bm2b2 + …. + Bmmbm

bi

dengan demikian solusi basis optimum adalah :

BI = B-1

=

Misalkan CB merupakan koefisien fungsi tujuan untuk variabel basis, maka fungsi tujuan

dari variabel basis adalah :

Z = Cx = CB BI = 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-1

Yjn =

â1n

â2n

..

..

âmn

Setelah itu uji perbandingan minimum untuk menentukan variabel yang akan

keluar basis dengan rumus :

b2 b2

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

â2n â2n

Proses ini diulangi sampai solusi optimum tercapai.



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 + 0S1 + 0S2

Dk. [1] 3X1 + 2X2 + S1 =

150 [2]

[3]

8X1 + 2X2 + S2 =

200

X1, X2, S1, S2 ≥ 0 Untuk melihat hasil perhitungan dengan Rivised Simpleks, terlebih dahulu kita akan

selesaikan dengan metode simpleks biasa, sebagai perbandingan.

CB

Basis Cj

bi

40 25 0 0

Indeks X1 X2 S1 S2

0 S1 150 3 2 1 0 150:3=50

0 S2 200 8 2 0 1 200:8=25

Zj-Cj 0 -40 -25 0 0

CB

Basis Cj

bi

40 25 0 0

Indeks X1 X2 S1 S2

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

CB

Basis Cj

bi

40 25 0 0

Indeks X1 X2 S1 S2

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

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 , Y2 =

8

2 , Y3 =

2

1 0 , Y4 = .

0 1

bi =

150

200

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



8

1

8

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].

1 Simpleks multiplier = π = [0,0]

0

0 = [0,0]

1

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

- 40 = - 40. 8

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

- 25 = - 25. 2

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 Y1

Minimum =

150 3 50 : =

200 8 25

S1

S2 Keluar basis

Pada tabel berikutnya, variabel basis menjadi S1 dan X1, oleh karena itu matriks basis

berubah menjadi :

1 3 B = [Y3,Y1] =

0 8

Invers matriks basisnya adalah :

B-1

=

1x8

1 8 3 1 3 8

= 0x3 0 1 0 1

Berdasarkan teori matriks, setiap nilai pada tabel berikutnya dapat diperoleh

dengan mengalikan kolom persamaan asal dengan invers matriks basisnya.

bi = B-1

bi = 0

3 8 150 75 S1

= 1 200 25 X 1

Perhitungan diatas menghasilkan tabel kedua simpleks yang diperbaiki berikut :



2

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].

1

π = [0,40] 0

3 8

= [0,5] 1

8

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

- 25 = - 15. 2

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

- 0 = 5. 1

Tabel akan optimum apabila nilai Cj ≥ 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.

1 Y2 =

0

3 8 2 5

4

= 1 1

8 4

Variabel yang akan keluar basis adalah :

bi Y2

75 Minimum = :

25

5 4 60

= 1

4 100

S1 Keluar basis

X 1

Variabel basis yang baru menjadi X2 dan X1, dan menghasilkan matriks basis seperti berikut :

2 3 B = [Y2,Y1] =

2 8

Invers matriks basisnya adalah :



5 5

5

B-1 =

1 8 3 4 5

3 10

= 2x8 2x3 2 2 1 1

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

4

bi = B-1

bi = 1

3 10 150 60 X

2

= 1 200 10 X

5 5 1

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

3 10

= [12;0,5] 1

5 5

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

- 0 = 12. 0

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

- 0 = 0,5. 1

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.



Contoh 2 :

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

Dk. [1] X1 + S1 = 40 [2]

X2 - S2 + A1 = 20 [3] X1 +

X2 + A2 = 50 [4] X1, X2,

S1, S2, A1, A2 ≥ 0

Misalkan Y1, …, Y6 menunjukkan kolom yang berkorespondensi dengan X1, X2, S1,

S2, A1, A2 dan bi berkorespondensi dengan konstanta ruas kanan, maka :

Y1 =

1

0 , Y2 =

1

0

1 , Y3 =

1

1

0 , Y4 =

0

0

1 , Y5 =

0

0

1 , Y6 =

0

0 40

0 , dan bi = 20

1 50

Variabel basis awalnya adalah S1, 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. C1 = [0,-M,-M]

2. C2 = [0,-M,-M]

1

0 - 50 = - M – 50

1

0

1 - 80 = - 2M – 80

1



3. C3 = [0,-M,-M]

4. C4 = [0,-M,-M]

1

0 - 0 = 0

0

0

1 - 0 = M

0

0

5. C5 = [0,-M,-M]

6. C6 = [0,-M,-M]

1 - (-M) = 0

0

0

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

Minimum =

40 0

20 : 1 = 20

50 1 50

S1

A1 Keluar basis

A2

Pada tabel pertama variabel basisnya adalah S1, A1 dan A2 yang berarti matriks

basisnya adalah Y3, Y5, dan Y6 atau :

1 0 0 baris 1

B = 0 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 = [0 0 0]

Baris 1 = [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.



Baris 2 = [0 1 0] x – 1 = [0 -1 0] Baris

3 = [0 0 1]

+

Nilai baru baris 3 = [0 -1 1]

1 0 0

Dengan demikian, B-1

= 0 1 0

0 1 1

Nilai konstanta ruas kanan yang baru dapat dicari dengan cara :

bi = B-1bi

1 0 0 40 40 S1

bi = 0 1 0 20 = 20 X 2

0 1 1 50 30 A2

Hasil perhitungan di atas dapat dibuat dalam tabel kedua simpleks diperbaiki seperti

berikut :

Tabel 2. Tabel kedua simpleks diperbaiki

basis B-1

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 0

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

0 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.



Karena itu, akan dijelaskan suatu prosedur perhitungan yang memberikan suatu

solusi layak optimum, meskipun solusi awalnya tidak layak. Prosedur itu

dinamakan dual simplex algorithm yang pertama 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 = 4X1 + 2X2

Dengan s yarat 3X1 + X2 ≥ 27

X1 + X2 ≥ 21

X1 + 2X2 ≥ 30

X1 ; X2 ≥ 0

Langkah pertama adalah mengubah semua kendala menjadi pertidaksamaan ≤ (agar

tidak membutuhkan artificial variable) dan kemudian tambahkan variabel slack.

Sehingga diperoleh :

Minimumkan Z = 4X1 + 2X2

Dengan syarat - 3X1 - X2 + S1 ≤ - 27

- X1 - X2 + S2 ≤ - 21

- X1 - 2X2 + S3 ≤ - 30

X1, X2, S1, S2, S3, ≥ 0

Jika bentuk baku di atas diekspresikan sebagai suatu tabel simplex awal, maka

akan terlihat bahwa variabel slack (S1, S2, S3) tidak memberikan solusi awal

layak. Karena ini merupakan masalah minimisasi sementara semua koefisien

pada persamaan Z adalah ≤ 0, maka solusi awal S1=-27, S2=-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 :



Tabel 1. Tabel Awal

Basis X1 X2 S1 S2 S3 Solusi

Z - 4 - 2 0 0 0 0

S1

S2

- 3

- 1

- 1

- 1

1 0 0 - 27

0 1 0 - 21 S3 - 1 - 2 0 0 1 - 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 S3 (=-30), karena ia memiliki nilai negatif terbesar.

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

Variabel X1 X2 S1 S2 S3

Persamaan Z - 4 - 2 0 0 0

Persamaan S3 - 1 - 2 0 0 1

Ras io 4 1



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


Z - 3 0 0 0 - 1 30

S1 - 2,5 0 1 0 -1/2 - 12

S2

X2

- 1/2

1/2

0 0 1 - 1/2 - 6

1 0 0 - 1/2 15

Solusi baru mas ih optimum tetapi tak layak (S1=-12, S2=-6). Kemudian S1

dipilih sebagai leav ing v ariable dan X1 sebagai entering v ariable. Ini memberi-

kan iterasi seperti berikut :

Tabel 3. Iterasi Kedua


Z 0 0 - 1,2 0 - 0,4 44,4

X1 1 0 - 0,4 0 0,2 4,8

S2 0 0 - 0,2 1 - 0,4 - 3,6

X2 0 1 - 0,2 0 - 0,6 12,6

Pada iterasi kedua belum diperoleh solusi layak (S2 = - 3,6). Karena S2 adalah satu-

satunya yang bernilai negatif, dengan sendirinya ia menjadi leaving variabel dan S3

sebagai entering variabel, ini memberikan iterasi seperti berikut :

Tabel 4. Iterasi Ketiga


Z 0 0 - 1 - 1 0 48

X1 1 0 - 1/2 1/2 0 3

S3 0 0 1/2 - 2,5 1 9

X2 0 1 1/2 - 1,5 0 18

Tabel Iterasi Ketiga merupakan tabel optimum dan layak dengan nilai fungsi tujuan

adalah 48.



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



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) 0 4 5 12 0 0 1 24000

Elemen pivot (b) 12 12 12 12 12 12 12 12

Persamaan pivot baru (a/b) 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.



a. Persamaan Z baru:

Persamaan Z lama (a) 1 -40 -30 -50 0 0 0 0

Elemen kolom masuk

pada variable dasar Z (b)

-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

b. Persamaan S1 baru:

Persamaan S1 lama (a) 0 6 4 1 1 0 0 32000

Elemen kolom masuk

pada variable dasar S1 (b)

1 1 1 1 1 1 1 1


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

c. Persamaan S2 baru:

Persamaan S2 lama (a) 0 6 7 3 0 1 0 16000

Elemen kolom masuk


3 3 3 3 3 3 3 3


b x c = (d) 0 1 5/4 3 0 0 1/4 6000

Persamaan S2 baru (a-d) 0 5 23/4 0 0 1 -1/4 10000

8. Table simpleks iterasi pertama:

Dasar Z X1 X2 X3 S1 S2 S3 Pemecahan Rasio

Z 1 -70/3 -55/6 0 0 0 25/6 100000

S1 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.



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 10000

Elemen pivot (b) 5 5 5 5 5 5 5 5

Persamaan pivot baru (a/b) 0 1 23/20 0 0 1/5 -1/20 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

pada variable dasar Z (b)

-70/3 -70/3 -70/3 -70/3 -70/3 -70/3 -70/3 -70/3

Persamaan pivot baru (c) 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

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


b x c = (d) 0 17/3 391/60 0 0 17/15 -17/60 34000/3

Persamaan S1 baru (a-d) 0 0 -44/15 0 1 -17/15 1/5 56000/3

c. Persamaan X3 baru

Persamaan X3 lama (a) 0 1/3 5/12 1 0 0 1/12 2000

Elemen kolom masuk

pada variable dasar X3 (b)

1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3


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



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.

solusi grafik dan metode primal...

Documents