Goal Programming (Program Optimasi Tujuan Ganda)

GOAL PROGRAMMING

(Program Optimasi Tujuan Ganda)

Yuhka Sundaya

Artikel ini Saya tulis ketika memelajari riset operasi. 

'Cites :

Sundaya, Y. 2005. Teori dan Latihan Metode Optimasi : Linear Programming. Perpustakaan Pribadi. Cimahi.

Meskipun saat ini solusi masalah optimasi dengan jumlah tujuan yang banyak telah disupport oleh banyak perangkat, namun logika dibalik cara kerja perangkat tersebut perlu dipahami logikanya. Artikel ini semoga bisa membantu memahami logika atau cara kerja optimasi tersebut. Materi pada artikel ini disadur dari :

Taha, H. 1997. Operations Research an Introduction Sixth Edition. Prentice-Hall International. London.

Pendahuluan

Linear Programming berfungsi untuk mencari solusi optimum dengan fungsi tujuan tunggal. Terdapat situasi dimana sebuah sistem mungkin memiliki tujuan berganda. Sebagai contoh, seorang politikus berjanji untuk mengurangi pinjaman nasional dan secara simultan mengurangi penerimaan pajak. Dalam situasi itu tidak mungkin menemukan soulsi tunggal yang mengoptimisasi tujuan yang bertolak belakang. Kita dapat mencari solusi yang kompromis didasarkan pada kepentingan relatif dari masing-masing tujuan.

Teknik goal programming digunakan untuk memecahkan masalah dengan model tujuan berganda. Ide prinsipnya adalah mengkonversi tujuan ganda awal ke dalam sebuah tujuan tunggal. Lebih lanjut, modal akan menghasilkan solusi efisien sebab hal itu tidak mungkin optimum yang terkait dengan masalah yang memiliki tujuan yang saling bertolak belakang.

Formulasi Goal Programming

Gagasan Goal Programming diilustrasikan dengan sebuah contoh. Misalnya, Bandung yang memiliki penduduk sebanyak 20 000 orang. Dewan kota kemudian sedang merumuskan pengembangan penerimaan pajak. Pajak tahunan yang diperoleh dari perumahan sebesar Rp 550 juta. Pajak tahunan dari makanan dan minuman dan penjualan umum sebesar Rp 35 juta dan Rp 55 juta, secara berurutan. Konsumsi gas lokal tahunan diperkirakan sebesar 7.5 juta galon. Dewan kota ingin mengembangkan tingkat pajak di dasarkan atas empat tujuan utama, yaitu :

Penerimaan pajak harus sekurang-kurangnya sebesar Rp 16 juta untuk memenuhi komitmen keuangan kota;

Pajak makanan dan minuman tidak lebih dari 10% dari seluruh pajak yang dikumpulkan;
Pajak penjualan umum tidak lebih dari 20% dari seluruh pajak yang dikumpulkan; dan
Pajak gas tidak lebih dari 0.2 rupiah per galon.

Misalnya, variabel xp, xf, dan xs menunjukkan tingkat pajak (dinyatakan sebagai proporsi) untuk perumahan, makanan dan minuman, serta penjualan umum dan variabel xg sebagai paja gas dalam rupiah per galon.

Tujuan dewan kota dapat dinyatakan sebagai berikut :

550x_p + 35x_f + 55x_s + 0.075x_g ³ 16 ... penerimaan pajak

35x_f ≤ 0.1(550x_p + 35x_f + 55x_s + 0.075x_g) ... pajak makanan dan minuman

55x_s ≤ 0.2(550x_p + 35x_f + 55x_s + 0.075x_g) ... pajak penjualan umum

x_g ≤ 2 ... pajak gas

x_p, x_f, x_s, x_g ³ 0

Kendala tersebut diringkas sebagai berikut :

550x_p +    35x_f + 55x_s + 0.075x_g ³ 16

  55x_p – 31.5x_f + 5.5x_s + 0.0075x_g ³ 0

110x_p + 7x_f – 44x_s + 0.015x_g ³ 0

x_g ≤ 2

x_p, x_f, x_s, x_g ³ 0

Masing-masing ketidaksamaan dari model menunjukkan sebuah tujuan yang mana aspirasi dewan kota terpenuhi. Bagaimanapun tujuan tersebut saling bertolak belakang dan pekerjaan yang terbaik adalah mencoba untuk mencapai solusi yang kompromis.

Tahapan untuk mencapai solusi yang kompromis tersebut adalah pertama, masing-masing ketidaksamaan dikonversi ke dalam tujuan yang fleksibel yang mana kendala dapat dilanggar, jika diperlukan. Dalam kasus Kota Bandung, tujuan yang fleksibel dapat dinyatakan sebagai berikut :

550x_p +    35x_f + 55x_s + 0.075x_g + S₁⁺ - S₁^- = 16
  55x_p – 31.5x_f + 5.5x_s + 0.0075x_g + S₂⁺ - S₁^- = 0
110x_p + 7x_f – 44x_s + 0.015x_g + S₃⁺ -  S₃^- = 0
x_g + S₄⁺ - S₄^- = 2
x_p, x_f, x_s, x_g ³ 0
s_i⁺, s_i^- ³ 0, i = 1, 2, 3, 4

Variabel non negatif Si+ dan Si- disebut dengan variabel deviasional sebagai mereka menunjukkan diviasi (penyimpangan) di atas dan di bawah sisi kanan kendala ke “i”. Variabel deviasional Si+ dan Si- bersifat dependen, dan karenanya tidak dapat menjadi variabel basic secara simultan. Artinya bahwa setiap iterasi simplex, satu dari dua variabel deviasional dapat diasumsikan bernilai positif. Jika, ketidaksamaan “i” semula berbentuk ≤ dan si+ nya > 0, kemudian tujuan ke “i” akan dipenuhi, dengan cara lain, jika si- > 0, maka tujuan ke “i” tidak dapat dipenuhi. Esensinya, pengertian variabel deviasional memutuskan kita untuk memenuhi atau melanggar tujuan ke “i”. Inilah bentuk fleksibilitas dari goal programming ketika mencoba untuk mencapai solusi yang kompromis. Secara alamiah salah satu solusi kompromis yang baik adalah menemukan minimisasi dari jumlah dengan mana masing-masing jumlah dilanggar.

Dalam model Kota Bandung sebelumnya, tiga kendala pertama berbentuk “³” dan kendala keempat berbentuk “≤”, keempat variabel deviasional menunjukkan jumlah dengan mana tujuan yang saling terkait dapat dilanggar. Kemudian, solusi kompromis yang harus ditemukan untuk memenuhi keempat tujuan yang memungkinkan sebagai berikut :

Minimisasi G1 = S₁⁺
Minimisasi G2 = S₂⁺
Minimisasi G3 = S₃⁺
Minimisasi G4 = S₄^-

Fungsi tersebut adalah minimisasi syarat ikatan terhadap kendala persamaan dari model.

Bagaimana kita dapat mengoptimisasi model tujuan ganda dengan tujuan yang bertolak belakang ? Dua metode telah dikembangkan untuk memenuhi tujuan ini, yaitu [1] metode pembobotan (weighting method) - WM dan [2] metode pengutamaan (preemtif method) - PM. Masing-masing metode didasarkan atas konversi tujuan berganda ke dalam tujuan tunggal.

Melalui WM, sebuah fungsi tujuan tunggal dibentuk sebagai jumlah bobot dari fungsi yang menunjukkan tujuan dari masalah. Sedangka dalam PM dimulai dengan memprioritaskan atau mengutamakan tujuan dalam susunan yang terpenting. Model kemudian dioptimisasi dengan menggunakan satu tujuan pada suatu waktu, dan dalam beberapa cara bahwa nilai optimum dari tujuan prioritas tertinggi tidak dikurangi oleh tujuan prioritas terendah.

Tujuan kedua metode berbeda. Dalam pengertian bahwa kedua metode tersebut tidak akan secara umum menghasilkan solusi yang sama. Masing-masing metode, bagaimanapun, dapat diklaim superior sebab masing-masing teknik didesain untuk memenuhi kencenderungan pembuatan keputusan tertentu.

Sebagai ilustrasi dikemukakan salah satu contoh persoalan yang diselesaikan dengan menggunakan kedua metode tersebut. Perusahaan TopAd merupakan perusahan periklanan baru dengan 10 orang tenaga kerja telah menerima kontrak untuk mempromosikan produk baru. Agen tersebut dapat mengiklankan melalui radio dan televisi. Tabel berikut menyajikan data mengenai jumlah orang yang dapat dicapai oleh masing-masing bentuk iklan dan biaya serta tenaga kerja yang dibutuhkan.

	Data/Iklan Minimal
	Radio	Televisi
Pembukaan (dalam juta orang)	4	8
Biaya (dalam juta dollar)	8	24
Tenaga Bantuan	1	2

Selanjutnya, dalam kontrak TopAd dilarang untuk menggunakan lebih dari 6 menit dari iklan radio. Dengan penambahan, iklan dalam radio dan televisi perlu untuk mencapai sekurang-kurangnya 45 juta orang. TopAd telah menyusun anggaran untuk proyek tersebut sebesar $100 000. Berapa menit iklan di radio dan iklan di televisi yang harus digunakan oleh TopAd ?

Katakanlah, x1 dan x2 adalah jumlah menit yang dialokasilan untuk iklan di radio dan iklan di televisi secara berurutan. Formulasi goal programming untuk masalah tersebut dinyatakan sebagai berikut :

Minimisasi G1 = S1+ (penuhi tujuan pembukaan)
Minimisasi G2 = S2- (penuhi anggaran tujuan)
Syarat Ikatan :
4x1 + 8x2 + S1+ - S1- = 45 (tujuan pembukaan) ... [1]
8x1 + 24x2 + S2+ - S2- = 100 (tujuan anggaran) ... [2]
x1 + 2x2 ≤ 10 (batasan tenaga kerja) ... [3]
x1 ≤ 6 (batasan radio) ... [4]
x1, x2, S1+, S2+, S1-, S2- ³ 0 ... [5]

Kemudian, TopAd menganggap bahwa tujuan pembukaan dua kali lebih penting dari tujuan anggaran, maka kombinasi fungsi tujuan tersebut dinyatakan sebagai berikut :

Minimisasi Z = 2G1 + G2 = 2S1+ + S2-

Dengan syarat ikatan [1] s.d [5]

Solusi dengan menggunakan program Lindo menghasilkan Z = 10, x1 = 5 menit, x2 = 2.5 menit dan S1+ = 5 juta orang. Seluruh variabel sisanya sama dengan nol.

Dengan demikian, alokasi iklan untuk radio sebanyak 5 menit dan ilan di televisi sebanyak 2.5 menit akan menjaring orang sebanyak [(4x5) + (8x2.5) = 40 juta orang] dengan biaya atas kedua jenis ilan tersebut sebesar [(8x5) + (24x2.5) = 100 ribu).

Kenyataannya bahwa nilai optimum dari Z tidak sama dengan nol, hal itu menunjukkan bahwa sekurang-kurangnya salah satu dari tujuan tidak tercapai. Secara khusus, S1+ = 5, artinya bahwa tujuan pembukaan (dari sekurang-kurangnya 45 juta orang) adalah kehilangan 5 juta individu. Sebaliknya, tujuan anggaran (tidak melebihi $100 000).

Goal Programming hanya menghasilkan sebuah solusi yang efisien terhadap masalah, yang mana tidak secara perlu mencapai optimum. Sebagai contoh, jika misalnya x1 = 6 dan x2 = 2, makaakan menghasilkan tujuan pembukaan yang sama [(4x6) + (8x2) = 40 juta orang), sedangkan biaya akan menurun [(8*6) + (24*2) = 96 ribu). Esensinya, Goal Programming hanya menemukan solusi yang hanya memenuhi tujuan dari model. Beberapa kekurangan dalam mencapai solusi oprimum memunculkan pertanyaan mengenai kemungkinan Goal Programming sebagai sebuah teknik optimasi.

Contoh Aplikasi

           

 

TEORI DAN LATIHAN METODE OPTIMASI : LINEAR PROGRAMMING

Yuhka Sundaya

Artikel ini Saya tulis ketika memelajari riset operasi. 

'Cites :

Sundaya, Y. 2005. Teori dan Latihan Metode Optimasi : Linear Programming. Perpustakaan Pribadi. Cimahi.

Meskipun saat ini solusi masalah optimasi telah disupport oleh banyak perangkat, namun logika dibalik cara kerja perangkat tersebut perlu dipahami logikanya. Artikel ini semoga bisa membantu memahami logika atau cara kerja optimasi tersebut. Materi pada artikel ini disadur dari :

Taha, H. 1997. Operations Research an Introduction Sixth Edition. Prentice-Hall International. London.

1. Pendahuluan

Tiga komponen pokok situasi yang dibutuhkan oleh pengambil keputusan untuk mengidentifikasi solusi atau pemecahan masalah :

[1] Alternatif keputusan;

[2] Di bawah batasan atau restriksi apa keputusan itu dibuat; dan

[3] Kriteria objektif apa yang tepat untuk mengevaluasi alternative keputusan tersebut.

Hasil akhirnya adalah model matematis yang terkait dengan variable keputusan, kendala, dan fungsi tujuan. Solusi atas model kemudian menghasilkan nilai variable keputusan yang mengoptimisasi (maksimisasi atau minimisasi) nilai fungsi tujuan yang memenuhi seluruh kendala. Hasil daripada solusi disebut dengan solusi optimum fisibel (optimum feasible solution).

Model matematika RO berbentuk sebagai berikut :

• Maksimisasi atau minimisasi ⇢ fungsi tujuan
• Syarat ikatan⇢kendala

Menentukan model matematik adalah pekerjaan utama di dalam RO.

1.1. Teknik Riset Operasi

Dalam model matematika RO, variable keputusan dapat bersifat bilangan bulat (integer) atau kontinyu (discreate), dan fungsi tujuan serta kendala dapat berbentuk linear atau non linear. Masalah optimisasi dihadapkan pada fitur model ini yang memunculkan keragaman metode/teknik solusi yang masing-masing didesain untuk menghitung sifat matematis khusus dari model. Teknik-teknik tersebut antara lain :

[1] Linear Programming;
[2] Dynamic Programming;
[3] Integer Programming;
[4] Non Linear Programming;
[5] Goal Programming;
[6] Network Programming;

Dan masih banyak lagi teknik-teknik lainnya untuk mencari pemecahan optimum. Diantara teknik-teknik tersebut Linear Programming lebih menonjol, yang mana seluruh fungsi tujuan dan kendala bersifat linear dan seluruh variable bersifat kontinyu.

Masalah RO diselesaikan secara iterative dengan menggunakan program computer khusus.

1.2. Model Simulasi

Sebuah pendekatan alternative untuk pemodelan system yang komplek adalah simulasi. Model simuasi dapat mengamati sebuah system yang nyata.

1.3. Seni Pemodelan

Sebuah kajian RO harus didasarkan pada kerja tim, dimana masing-masing analisis RO dan rekan mengerjakan sisi demi sisi. Analisis RO membutuhkan pengalaman dan kerjasama dari rekan untuk siapa kajian ini ditujukan.

Sebagai sebuah alat pengambilan keputusan, RO harus dipandang sebagai ilmu dan seni. Sebagai ilmu melekat dengan teknik matematika yang digunakan, sedangkan sebagai seni, kesuksesan seluruh tahapannnya bergantung pada kreatifitas dan pengalaman dari tim kerja RO.

Prinsip tahapan/langkah yang diterapkan dalam praktek RO mencakup :

[1] Definisi masalah;
[2] Konstruksi/membangun model;
[3] Solusi model;
[4] Validasi model; dan
[5] Penerapan/implementasi solusi.

Tahapan [1] s.d [3] terkait dengan teori matematika, sedangkan kedua tahapan berikutnya terkait dengan seni.

Definisi masalah mencakup definisi ruang lingkup masalah yang diselidiki. Ini adalah fungsi yang harusnya dibatasi oleh tim RO. Hasil akhir dari penyelidikan adalah mengidentifiasi tiga komponen utama dari pengambil keputusan.

Konstruksi model menterjemahkan definisi masalah ke dalam hubungan matematis, sehingga tim RO dapat menentukan jenis teknik pemecahan yang tepat.

Solusi model adalah tahapan yang mudah dalam seluruh tahapan RO sebab tahapan ini dibantu oleh optimisasi aljabar dan program komputasi computer. Aspek penting dalam tahapan ini adalah analisis sensitifitas. Hal ini terkait dengan tambahan informasi tentang perilaku solusi optimum. Analisis sensitifitas dibutuhkan ketika parameter dari model tidak dapat diestimasi secara akurat.

Validitas model menguji apakah model menyajikan prediksi yang reasonable atas perilaku system yang dikaji. Apakah hasilnya dapat diterima secara intuitif. Validitas model dapat dibandingkan dengan data histories.

Akhirnya, pada tahap akhir, penerapan solusi dari model yang valid adalah menterjemahkan hasil model ke dalam perintah operatif dalam bentuk yang dapat dipahami.

2. Linear Programming Dasar

LP adalah teknik pemodelan matematika yang didesain untuk mengoptimisasi penggunaan sumberdaya yang terbatas. Asumsi yang digunakan LP adalah :

[1] Proporsionalitas, dan
[2] Aditivitas

2.1. Konstruksi Model LP

Dalam sub bab ini dikemukakan contoh kasus sederhana untuk membangun model LP. Diketahui Reddy Mikks memproduksi cat interior dan cat exterior dari dua bahan baku, M1 dan M2. Tabel 2.1 menyajikan beberapa data dari permasalahan dasarnya. 

Tabel 2.1. Alokasi dan Ketersediaan Bahan Baku Cat Exterior dan Interior

	Bahan Baku per ton dari :		Ketersediaan Maksimum per hari (ton)
	Cat Exterior	Cat Interior
M1	6	4	24
M2	1	2	6
Keuntungan per ton ($1000)	5	4

Dari survey pasar diketahui ada batasan bahwa permintaan maksimum harian “cat interior” sebesar 2 ton. Dengan tambahan informasi, bahwa permintaan harian “cat interior” tidak lebih dari “cat exterior” dengan lebih dari 1 ton.

Reddy Mikks ingin menentukan kombinasi produk optimum (terbaik) dari kedua produk tersebut yang memaksimumkan keuntungan total per hari.

Model LP mencakup 3 elemen dasar, yaitu :
Variabel keputusan;
Tujuan (objective), yang akan dioptimasi; dan
Kendala (constraints), yang perlu dipenuhi.

Untuk masalah Reddy Mikks, kita perlu menentukan jumlah produksi cat exterior dan cat interior. Dimana :
x1 = produksi harian cat exterior;
x2 = produksi harian cat interior.

Definisi itu digunakan untuk mengkonstruksi fungsi tujuan, yang diekspresikan sebagai berikut :

Maximisasi : Z = 5x1 + 4x2

Elemen terakhir dari model, terkait dengan kendala yang membatasi penggunaan dan permintaan bahan baku. Batasan bahan baku diekspresikan secara verbal sebagai berikut :

(Penggunaan bahan baku untuk masing - masing cat ) ≤ (Ketersediaan maksimum bahan baku)

Dari informasi yang telah ditabulasi sebelumnya, dapat dinyatakan bahwa :
Penggunaan bahan baku, M1 = 6x1 + 4x2 ≤ 24
Penggunaan bahan baku, M2 = x1 + 2x2 ≤ 6

Karena ketersediaan harian, M1 dan M2 dibatasi masing-masing dengan 24 ton dan 6 ton, kendala yang terkait dinyatakan sebagai berikut :

6x1 + 4x2 ≤ 24 …bahan baku M1
x1 + 2x2 ≤ 6 …bahan baku M2

Tedapat dua bentuk kendala permintaan, yaitu [1] permintaan harian maksimum cat interior (x2) dibatasi 2 ton, dan [2] kelebihan produksi harian cat interior (x2) terhadap cat exterior (x1) tidak lebih dari 1 ton. Kendala pertama dapat dinyatakan x2 ≤ 2, sedangkan kendala kedua dinyatakan x2 – x1 ≤  1.

Selain itu, terdapat kendala yang bersifat implicit atas model, yakni varibel x1 dan x2 bukan bilangan negatif (non negativity) yang dinyatakan x1, x2 ³ 0.

Berdasarkan uraian di atas, model Reddy Mikks selengkapnya adalah :

Maximisasi : Z = 5x1 + 4x2
Syarat ikatan :
6x1 + 4x2      ≤ 24
  x1 + 2x2      ≤ 6
 -x1 +   x2     £ 1
             x2     £ 2
  x1, x2          ³ 0

Banyak cara untuk menentukan besarnya x1 dan x2 dalam model Reddy Mikks. Namun terdapat dua langkah yang dipandang efisien, yaitu :

[1] Menentukan ruang solusi yang fisibel, dan
[2] Menentukan solusi optimum.

Kita dapat mengilustrasikan model Reddy Mikks dalam sebuh grafik. Untuk langkah pertama, kita gambarkan semua Kendala dalam model Reddy Mikks dalam grafik 1 berikut.

 

2.3.2 Solusi Model Minimisasi

Contoh 2.3-2 (Masalah Diet)

Pertanian Ozark menggunakan sekurang-kurangnya 800 lb makanan khusus harian. Makanan khusus tersebut adalah kombinasi dari jagung dan sayuran dengan komposisi berikut :

 

	Lb per lb of feedstuff		Cost ($/lb)
Feedstuf	Protein	Fiber
Corn	0.09	0.02	0.30
Soybean meal	0.60	0.06	0.90

Kebutuhan diet dari makanan khusus itu ditentukan sekurang-kurangnya 30% protein dan sebesar-besarnya 5% fiber. Pertaniaan Ozark ingin menentukan biaya minimum per hari dari kombinasi makanan itu.

Karena kombinasi makanan terkait dengan jagung dan sayuran, variable keputusan dari model didefinisikan sebagai berikut :

X1 = lb jagung dalam kombinasi harian

X2 = lb sayuran dalam kombinasi harian

Fungsi tujuan adalah meminimisasi biaya total harian (dalam dollar) dari kombinasi makanan yang diekspresikan sebagai berikut : 

Minimisasi : z = 0.3x1 + 0.9x2

Kendala dari model harus merefleksikan jumlah harian yang diperlukan dan kebutuhan diet. Karena petani Ozark butuh 800 lb dari makanan per hari, kendala yang terkait dapat diekspresikan sebagai berikut :

x1 + x2 ≤ 800 

Kendala kebutuhan diet protein dikembangkan kemudian. Jumlah protein yang ada dalam x1 lb jagung dan x2 lb sayuran adalah (0.09x1 + 0.6x2) lb. Jumlah ini seharusnya sama sekurang-kurangnya 30% dari total kombinasi makanan (x1 + x2) lb, yang kemudian :

0.09x₁ + 0.6x₂ ≥ 0.3(x₁ + x₂)     Û   0.09x₁ + 0.06x₂ ≥ 0.3x₁ + 0.3x₂

                                                            (0.09x₁-0.3x₁)+( 0.6x₂-0.3x₂) ≥ 0

                                                            -0.21x₁+ 0.3 x₂ ≥ 0

                                                             0.21x₁ – 0.3 x₂ ≤ 0                             

Dengan cara yang serupa, kendala fiber dibangun sebagai berikut :

0.02 x₁ + 0.06x₂ ≤ 0.05(x₁ + x₂) Û      0.02 x₁ + 0.06x₂ ≤ 0.05x₁ + 0.05x₂

                                                                (0.02x₁ – 0.05x₁)+( 0.06x₂ – 0.05x₂) ≤ 0

                                                                 -0.03 x₁ + 0.01x₂ ≤ 0

                                                                  0.03 x₁ – 0.01x₂ ≥ 0

Model diet selengkapnya adalah :

Minimisasi : z = 0.3x1 + 0.9x2
Dengan kendala :
x1 + x2 ≤ 800
0.03x1 – 0.01x2 ≥ 0
0.21x1 – 0.3x2 ≤ 0
x1, x2 ≥ 0

3. Metode Aljabar Simplex : Teknik Menentukan Nilai Optimum

Dalam model matematika yang lebih komplek, nilai optimum variable keputusan ditentukan dengan bantuan program komputasi computer. Beberapa diantaranya adalah LINDO, ABQM, dan TORA. Namun bagaimanapun diperlukan pengetahuan bagaimana cara kerja program-program komputasi tersebut. Metode simplex dengan model matematika sederhana berikut ini dapat memberikan gambaran bagaimana program komputasi itu bekerja.

Jika diketahui model matematis RO sebagai berikut :

Maksimisasi         :               Z = 5x₁ + 4x₂

Syarat ikatan        :               6x₁ + 4x₂ £ 24

                                               x₁ + 2x₂ £ 6

                                             -x₁ +   x₂ £ 1

                                                        x₂ £ 2

                                                x₁, x₂ ³ 0

Dalam bentuk standar yang mencerminkan kesamaan dinyatakan sebagai berikut :

Maksimisasi         :               Z = 5x₁ + 4x₂ + 0S₁ + 0S₂ + 0S₃ + 0S₄

Syarat ikatan        :               6x₁ + 4x₂        + S₁                                              = 24

                                                  x₁ + 2x₂                  + S₂                                    = 6

                                                 -x₁ +   x₂                           + S₃                         = 1

                                                            x₂                                     + S₄              = 2

                                                x₁, x_2,  S_1, S_2, S_3, S₄ ³ 0

Dalam bentuk table bentuk standar tersebut dinyatakan dalam table 1 berikut :

Tabel 1 Simplex

Basic	Z	x1	x2	S1	S2	S3	S4	Solution	Rasio [9]:[3]
[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
Z	1	-5	-4	0	0	0	0	0
S1	0	6	4	1	0	0	0	24	4
S2	0	1	2	0	1	0	0	6	6
S3	0	-1	1	0	0	1	0	1	-1
S4	0	0	1	0	0	0	1	2	¥

        

Beberapa hal penting sebelum melakukan operasi aljabar simplex adalah :
[1] Menentukan entering variable untuk menetukan kolom pivot;
[2] Menentukan leaving variable untuk menentukan baris pivot;
[3] Menentukan elemen pivot untuk menentukan table simplex lebih lanjut

Variable x1 dapat dinyatakan sebagai entering variabel. Karena, dalam persamaan keuntungan (z), variable x1 memiliki kontribusi paling besar terhadap keuntungan dibandingkan variable x2. Keuntungan akan meningkat sebesar $5 dengan

kenaikan x1 per satu satuan, sedangkan kenaikan x2 sebesar satu satuan hanya akan meningkatkan keuntungan sebesar $4. Dengan demikian vector kolom x1 dinyatakan sebagai kolom pivot.

Untuk menentukan leaving variable, kita buat dulu kolom rasio dalam table sebelumnya. Rasio diperoleh dari hasil bagi antara vector kolom solusi dengan vector kolom entering variable. Kriteria yang digunakan untuk menentukan leaving variable adalah nilai rasio yang paling kecil tetapi bukan nilai negative (non negativity value). Berdasarkan criteria ini kita dapat menyatakan bahwa baris variable slack S1 sebagai baris pivot yang akan di replace oleh variable x1 dalam table simplex lebih lanjut.

Langkah pertama setelah kita mengidentifikasi baris dan kolom pivot adalah membuat table 2.1. Karena baris S1 memiliki nilai rasio positif yang paling kecil (non negativity value), maka dalam table 2 vektor baris variabel S1 di replace dengan vector baris variable x1 yang baru. Vaktor baris variable x1 yang baru dalam table 2.1 ditentukan dengan cara membagi setiap komponen vector baris pivot dengan elemen pivot. Elemen pivot dalam table 1 terletak pada koordinat antara S1 dengan x1 (entering variable), yakni 6.[1] Dengan demikian vaktor baris x1 yang baru berisi bilangan yang secara berurutan adalah [0/6, 6/6, 4/6, 1/6, 0/6, 0/6, 0/6 dan 24/6].

Tabel 2.1. Simplex 

	Basic	Z	x1	x2	S1	S2	S3	S4	Solution
Langkah 2	Z
Langkah 1	x1	0	1	4/6	1/6	0	0	0	4
Langkah 3	S2
Langkah 4	S3
Langkah 5	S4

Langkah kedua, ketiga, keempat dan kelima secara bertahap adalah mengisi elemen-elemen dalam vector baris Z, S2, S3, dan S4 yang baru dalam table 2.1 simplex yang sumbernya berasal dari table 1. Langkah-langkah ini mengikuti prosedur Gauss-Jordan dalam operasi matriks.

· Vektor baris Z = [vector baris Z table 1] – [EP(Z:X1)*vector baris X1 tabel 2]
· Vektor baris S2 = [vector baris S2 table 1] – [EP(S2:X1)*vector baris X1 tabel 2]
· Vektor baris S3 = [vector baris S2 table 1] – [EP(S3:X1)*vector baris X1 tabel 2]
· Vektor baris S4 = [vector baris S2 table 1] – [EP(S4:X1)*vector baris X1 tabel 2] 

Hasil selengkapnya dari langkah pertama sampai dengan langkah kelima ditampilkan dalam table 2.2 simplex berikut : 

Tabel 2.2. Simplex :

Basic	Z	x1	X2	S1	S2	S3	S4	Solution	Rasio
[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[9]:[4]
Z	1	0	-2/3	5/6	0	0	0	20
x1	0	1	2/3	1/6	0	0	0	4	6
S2	0	0	4/3	-1/6	1	0	0	2	3/2
S3	0	0	5/3	1/6	0	1	0	5	3
S4	0	0	1	0	0	0	1	2	2

Hasil dalam table 2.2 simplex belum optimum, karena variable keputusan x2 belum ditentukan. Selanjutnya dilakukan proses serupa untuk menetukan nilai x2 tersebut. Entering variable selanjutya berdasarkan table 2.2 tersebut adalah x2. Dalam table itu, hanya x2 yang dapat meningkatkan keuntungan (Z).

Untuk menentukan leaving variable lebih lanjut, lihat dulu rasio mana yang paling kecil namun positif. Dalam table 2.2 rasio ditentukan dengan cara membagi nilai solusi dengan vector kolom entering variable (x2), yang hasilnya dapat dilihat dalam table tersebut. Hasilnya, dapat ditentukan bahwa vector baris S2 dinyatakan sebagai leaving variable, karena nilai rasionya paling rendah.

Selanjutnya, dengan proses yang sama seperti dalam langkah pertama hingga kelima di dalam mengisi table 2.2. simplex, hasil selengkapnya ditampilkan dalam table 3. simplex berikut: 

Tabel 3. Simplex :

Basic	Z	X1	X2	S1	S2	S3	S4	Solution
Z	0	0	0	3/4	1/2	0	0	21
X1	0	1	0	1/4	-1/2	0	0	3
X2	0	0	1	-1/8	3/4	0	0	3/2
S3	0	0	0	3/8	-5/4	1	0	5/2
S4	0	0	0	1/8	-3/4	0	1	½

Keterangan :

· Vektor baris Z = [vector baris Z table 1] – [EP(Z:x2) * vector baris X2 tabel 3]
· Vektor baris x1 = [vector baris S2 table 1] – [EP(S2:x2) * vector baris X2 tabel 3]
· Vektor baris S3 = [vector baris S2 table 1] – [EP(S3:x2) * vector baris X2 tabel 3]
· Vektor baris S4 = [vector baris S2 table 1] – [EP(S4:x2) * vector baris X2 tabel 3]

Ketika dalam vector kolom Z tidak nampak lagi variable slack S1 dan S2, maka table 3 itu telah mencapai nilai optimal. Nilai optimal dari x1, x2 dan Z terdapat dalam kolom solusi table 3 simplex.

Interpretasi hasil ini adalah bahwa untuk mencapai keuntungan (Z) sebesar $21, maka X1 dan X2 yang diproduksi masing-masing harus sebesar 3 dan 1.5 satu satuan.

Analisis optimasi model linear ini lebih dari penentuan nilai tujuan yang optimum dan variabel keputusan yang optimal untuk digunakan. Dalam permasalahan Reddy Mix sebelumnya, berarti analisisnya lebih dari menentukan keuntungan optimum dan penentuan besarnya cat interior dan eksterior yang memaksimumkan keuntungan. Informasi selanjutnya yang perlu dikaji oleh perencana adalah reduced cost, shadow price serta analisis sensitivitas. Analisis sensitivitas dibahas dalam sub bab 3.1.

Dari Tabel 3, dapat dimunculkan dua informasi penting mengenai reduced cost (unit worth of resource) dan shadow price (dual price atau simplex multiplier). Reduced cost dalam table itu ditunjukan oleh nilai dalam koordinat Z dengan X1 dan Z dengan X2, dimana keduanya bernilai nol (0) yang menunjukkan bahwa biaya per unit penggunaan M1 dan M2 sama dengan penerimaan per unit penggunaan M1 dan M2.

[1] Elemen pivot ini selanjutnya didenotasikan dengan EP(Z:X1), yang artinya elemen pivot yang terletak pada koordinat atau pertemuan antara baris Z dengan kolom X1.