Setiap perusahaan dituntut mampu untuk produktif dalam menjalankan usahanya supaya

mereka tetap bisa bertahan dalam tantangan globalisasi. Untuk itulah perusahaan pun harus mampu
menganalisis dan memecahkan setiap masalah yang dihadapinya. Permasalahan penentuan jumlah
produksi di suatu perusahaan sering dihadapi oleh manajer produksi sehingga perusahaan dapat
mengalami kerugian. Hal itu disebabkan karena jumlah barang yang diproduksi tidak sesuai dengan
kebutuhan konsumen. Sehingga terjadi penumpukan stok barang yang dapat mengakibatkan kerugian
perusahaan.

Penentuan jumlah produksi untuk memaksimalkan keuntungan perusahaan dengan melihat

keterbatasan sumber daya perusahaan tersebut dapat diselesaikan dengan menggunakan model
program linier. Ada beberapa cara menyelesaikan masalah dengan model program linier, diantaranya
yaitu diselesaikan dengan Metode Simpleks. Metode Simpleks adalah penyelesaian model program
linier yang penyelesaiannya disajikan dalam bentuk grafik yang sebelumnya dilakukan perhitungan-
perhitungan untuk mencari titik-titik temu pada masing-masing sumbu. Prosedur umumnya adalah
untuk mengubah suatu situasi deksriptif kedalam bentuk masalah program linier dengan menentukan
variabel, konstanta, fungsi objektif, dan kendalanya sehingga masalah tersebut dapat disajikan dalam
bentuk grafik dan diinterpretasikan solusinya.

Metode ini dikembangkan oleh George Dantzig pada 1946 dan sepertinya cocok untuk
komputerisasi masa kini. Pada 1946 Narendra Karmarkar dari Bell Laboratories menemukan suatu
cara untuk memecahkan masalah program linear yang lebih besar, sehingga memperbaiki dan
meningkatkan hasil dari metode simpleks. Metode ini menyelesaikan masalah program linear melalui
perhitungan berulang-ulang (iteration) yang langkah-langkah perhitungan yang sama diulang
berkalikali sebelum solusi optimum dicapai. Dantzig (2002) mempublikasikan Linear Programming
dalam suatu jurnal ilmiah.
Metode simpleks merupakan prosedur algoritma yang digunakan untuk menghitung dan
menyimpan banyak angka pada iterasi-iterasi yang sekarang dan untuk pengambilan keputusan pada
iterasi berikutnya. Metode simpleks merupakan suatu metode untuk menyelesaikan masalah-masalah
program linear yang meliputi banyak pertidaksamaan dan banyak variabel. Dalam menggunakan
metode simpleks untuk menyelesaikan masalah-masalah program linear, model program linear harus
diubah ke dalam suatu bentuk umum yang dinamakan ”bentuk baku”. Ciri-ciri dari bentuk baku model
program linear adalah semua kendala berupa persamaan dengan sisi kanan nonnegatif, fungsi tujuan
dapat memaksimumkan atau meminimumkan.
Salah satu teknik penentuan solusi optimal yang digunakan dalam pemrograman linear adalah
metode simpleks. Penentuan solusi optimal menggunakan metode simpleks didasarkan pada teknik
eleminasi Gauss Jordan. Penentuan solusi optimal dilakukan dengan memeriksa titik ekstrem satu per
satu dengan cara perhitungan iteratif. Sehingga penentuan solusi optimal dengan simpleks dilakukan
tahap demi tahap yang disebut dengan iterasi. Iterasi ke-i hanya tergantung dari iterasi sebelumnya.
Persyaratan Metode Simpleks
 1. Semua kendala pertidaksamaan harus dinyatakan sebagai persamaan.
2. Sisi kanan (the right side) dari sebuah kendala tidak boleh ada yang negatif.
3. Nilai kanan (NK/RHS) fungsi tujuan harus nol (0).
4. Semua variabel dibatasi nilai nilai non-negatif.
Problem Maksimisasi

Perusahaan Brilliant menghasilkan 2 jenis sepatu yaitu sepatu dengan merk italy dan felix.
Merk italy dibuat dengan sol dari bahan karet. Sedangkan felix dibuat dengan sol dari bahan kulit.
Untuk membuat sepatu tersebut diperlukan 3 jenis mesin yaitu A (khusus untuk sol karet), B (khusus
untuk sol kulit), dan C (untuk finishing). Untuk setiap lusin sepatu dibutuhkan waktu, Italy dikerjakan
pada mesin A selama 2 jam tanpa melalui mesin B dan di mesin C selama 6 jam. Felix dikerjakan
tanpa melalui mesin A, melalui mesin B selama 3 jam dan mesin C selama 5 jam. Jam kerja
maksimum setiap hari untuk mesin A = 8 jam, melalui mesin B = 15 jam, dan mesin C = 30 jam.
Perolehan keuntungan untuk setiap lusin sepatu italy Rp. 30.000,00 dan felix Rp. 50.000,00. Tentukan
jumlah produksi sepatu yang menghasilkan laba maksimal.
jawab...... 
1. Merumuskan masalah
Tujuan : Zmax
Variabel : Italy = x1
Felix = x2
Kendala : Waktu dari masing-masing mesin.
2.        Menentukan model matematik

3.        Menentukan persamaan simpleks

4.        Membentuk tabel simpleks

Dengan demikian, nilai negatif terbesar terletak pada kolom x2, maka kolom kunci terlelak
pada kolom x2. Hasil pembagian nilai kanan dengan kolom kunci terdapat nilai positif terkecil pada
baris s2, maka baris kunci terletak pada baris s2, dan angka kunci terletak pada kotak x2s2.
a.    Angka baru baris kunci (ABBK)

b. Angka baru baris z

c.    Angka baru baris s1

Angka baru baris s1 ini masih tetap, karena pada persilangan antara baris s1 dengan
kolom x2 nilainya sudah nol (0).
d.    Angka baru baris s3  
 

Pada iterasi 1 ini belum optimal, karena nilai pada baris z masih ada yang negatif. Dengan
demikian, pengoptimalan masih dilanjutkan. Nilai negatif terbesar terlatak pada kolom x1, maka
kolom kunci terletak pada kolom x1. Hasil pembagian antara nilai kanan dangan kolom kunci terdapat
nilai positif terkecil pada baris s3, maka baris kunci terletak pada baris s3, dan angka kunci terletak
pada kotak x1s3.
 d.    Angka baru baris x2
Angka baru baris x2 ini masih tetap, karena pada persilangan antara baris x2 dengan kolom x1
nilainya sudah nol (0).

Pada iterasi 2, nilai pada baris z sudah tidak ada yang bernilai negatif, maka tabel sudah
optimal, sehingga perhitungan iterasi dihentikan.
Solusi optimal : x1 = 5/6, x2 = 5 dan Z = 275.000, artinya untuk mendapatkan keuntungan
maksimum sebesar Rp. 275.000,00, maka perusahaan Brilliant sebaiknya menghasilkan produk sepatu
merk italy sebesar 5/6 lusin dan produk sepatu felix sebesar 5 lusin.
Status sumber daya dilihat dari keberadaan variabel basis awal dari setiap fungsi kendala pada
tabel optimal. Dalam kasus diatas, untuk fungsi kendala pertama, keberadaan s1 pada variabel basis
tabel optimal adalah 19/3, maka sumber daya ini disebut berlebihan (abundant), keberadaan s2 dan s3
pada variabel basis tabel optimal adalah 0, maka sumber daya ini disebut habis terpakai (scarce).
Harga bayangan ini dilihat dari koefisien variabel slack atau surplus pada baris fungsi tujuan.
Koefisien s1 pada baris fungsi tujuan tabel optimal adalah 0, dengan demikian harga bayangan sumber
daya pertama adalah 0. Koefisien s2 pada baris fungsi tujuan tabel optimal adalah 25.000/3, dengan
demikian harga bayangan sumber daya kedua adalah 25.000/3. Koefisien s3 pada baris fungsi tujuan
tabel optimal adalah 5.000, dengan demikian harga bayangan sumber daya ketiga adalah 5.000.

Problem minimisasi

Galuh Chemical Company. Galuh Chemical Company harus membuat 1000 unit campuran
phospate dan postassium. Biaya per unit phospate adalah $5, sedangkan biaya per unit postassium
$6. Jumlah phospate yang dapat digunakan tidak lebih dari 300 unit sedangkan postassium harus
digunakan minimal 150 unit. Berapa masing-masing jumlah phospate dan postassium yang harus
digunakan agar biaya total minimum?

Minimisasikan Cost Z = 5X1 + 6X2

Fungsi kendala :

X1 + X2 = 1000
 X1 ≤ 300
X2 ≥ 150
X1, X2 ≥ 0
X1 = jumlah phospate dalam unit
X2 = jumlah postassium dalam unit
Formulasi sesuai standard simpleks artinya kita harus merubah tanda pertidaksamaan (≤ maupun ≥)
menjadi persamaan. Untuk kendala dengan tanda = kita hanya menambahkan artificial variabel
saja. Sehingga kendala yang pertama akan menjadi :
X1 + X2 + A1 = 1000
Kendala kedua, X1 ≤ 300
tambahkan slack variabel sehingga menjadi : X1 + S1 = 300
Sedangkan kendala ketiga, X2 ≥ 150, harus dikurangi dengan surplus variabel dan ditambah
dengan artificial variabel, sehingga menjadi :
X2 – S2 + A2 = 150
Fungsi Tujuan :
Minimisasikan biaya Z = 5X1 + 6X2 + 0S1 + 0S2 + MA1 + MA2

Fungsi kendala :
X1 + X2 + A1 = 1000 X1 + S1 = 300
X2 – S2 + A2 = 150
X1, X2, S1, S2, A1, A2 ≥ 0

Cj 5 6 0 0 +M +M
Product Mix X1 X2 S1 S2 A1 A2 Q
A1 +M 1 1 0 0 1 0 1000
S1 0 1 0 1 0 0 0 300
A2 +M 0 1 0 -1 0 1 150
Zj +M 2M 0 -M +M +M 1050M
Cj-Zj 5-M 6-2M 0 M 0 0

Angka pada baris Cj (5, 6, 0, 0, +M, +M) tersebut adalah koefisien pada fungsi tujuan.
Sedangkan angka (1, 1, 0, 0, 1, 0) pada baris A1 serta angka (1, 0, 1, 0 0, 0) pada baris S1 dan
angka (0, 1, 0, -1, 0, 1) pada baris A2 adalah koefisien pada kendala 1, 2 dan 3. Angka pada baris
Zj (+M, 2M, 0, -M , +M, +M ) diperoleh dari penjumlahan hasil kali kolom Cj dengan kolom
yang bersesuaian. Sebagai contoh kita akan menentukan nilai Zj kolom X1 = (M x 1) + (0 x 1) +
(M x 0) = M. Dengan cara yang sama kita peroleh nilai Zj pada kolom yang lain. Angka pada baris
Cj – Zj diperoleh dari angka pada baris Cj dikurangi dengan angka pada baris Zj. Sebagai contoh
kita akan menghitung nilai Cj – Zj pada kolom X1 = 5 (yaitu angka pada baris Cj) – M (angka pada
baris Zj) = 5 - M . Demikian juga untuk menghitung nilai Cj – Zj untuk kolom-kolom yang lain
digunakan cara yang sama.

Tipe Irregular dalam Linear Programming

[Link] Optimal Majemuk
Misalkan dari kasus PT XYZ fungsi tujuannya diubah dari Z = 4x1 + 5x2 menjadi Z = 4x1 + 3x2.
Formulasi modelnya adalah
Memaksimumkan Z = 4x1 + 3x2 Terbatas pada
1x1 + 2x2 ≤ 40
4x1 + 3x2 ≤ 120
x1 , x2 ≥ 0
Perubahan pada fungsi tujuan membuat garis fungsi tujuan menjadi sejajar dengan
garis batasan 4x1 + 3x2 ≤ 120. Kedua garis ini mempunyai kemiringan yang sama.

Solusi optimalnya berada di garis B dan C, sehingga terdapat beberapa pilihan solusi
optimalnya.
x1

40

30
A

20 B
C
10

0 10 20 30 40 x2

Tabel Simplek Optimalnya:

cj 4 5 0 0
Variabel Kuantitas
Dasar x1 x2 s1 s2
0 s1 10 0 5/4 1 -1/4
4 x1 30 1 3/4 0 ¼
zj 120 4 3 0 1
 cj - zj 0 0 0 -1
Bukti adanya solusi optimum majemuk untuk masalah ini dapat ditentukan pada baris cj – zj.
Solusi optimal majemuk diindikasikan oleh nilai 0 (nol) pada baris cj - zj (atau zj - cj) untuk
variabel bukan dasar. Solusi optimal alternatif.

cj 4 5 0 0
Variabel Kuantitas
dasar x1 x2 s1 s2
5 x2 8 0 1 4/5 -1/5
4 x1 24 1 0 -3/5 2/5
zj 120 4 3 0 1
cj - zj 0 0 0 -1

b. Suatu Masalah Yang Tidak Fisibel

Dalam beberapa kasus masalah Program Linier tidak mempunyai daerah fisibel, jadi
tidak terdapat solusi fisibel dasar pada masalah tersebut.

c. Suatu Masalah Tidak Berbatas

Dalam beberapa kasus masalah daerah solusi yang layak dibentuk oleh batasanbatasan model
tidak tertutup.
Dalam hal ini fungsi tujuan mungkin saja akan naik terus-menerus tidak terbatas tanpa
mencapai nilai maksimum, mengingat fungsi tujuan tidak akan pernah mencapai batas daerah
solusi yang layak.

Penyelesaian Metode Simpleks dengan POM-QM For Windows

 Jalankan program QM For Windows, pilih Module - Linear Programming

 Pilih menu File - New, sehingga muncul tampilan seperti gambar di bawah ini.
 Buat judul penyelesaian soal ini dengan mengisi bagian Title, jika Title tidak diisi, program
QM For Windows akan membuat judul sendiri sesuai default (patokannya). 
 Isikan jumlah kendala dengan cara meng-klik tanda  pada kotak Number of Constraints. 
 Isikan jumlah variabel dengan cara meng-klik tanda   pada kotak Number of Variables. 
 Pilih tujuan yang akan dicari pada bagian Objective, jika tujuan yang akan dicari adalah maksimasi,
pilih Maximize, begitupun sebaliknya, jika tujuan yang akan dicari minimasi, maka pilih Minimize. 
 Kemudian klik OK, dan akan muncul gambar seperti di bawah ini.  

 Isikan angka-angka sesuai soal, pada kotak yang bersesuaian. 

 Selesaikan dengan meng-klik tombol  pada toolbar atau dari menu File - Solve, atau

dengan menekan tombol F9 pada keyboard. 

 Jika ternyata ada data soal  yang  perlu  diperbaiki,  klik  tombol  pada toolbar atau

dari menu File – Edit.
 Jangan lupa simpan (save) file kerja ini dengan menu File - Save atau menekan tombol Ctrl+S.  
Ada 6 output (tampilan) yang dihasilkan dari penyelesaian soal, dapat dipilih untuk
ditampilkan dari menu Windows yaitu :
 Linear Programming Results
 Ranging
 Original Problem w/answers
 Iterations
 Dual
 Graph
 Output-output ini dapat ditampilkan secara bersaman dengan memilih menu Window –
Tile, atau secara bertumpuk dengan menu Window – Cascade.

  
 Tampilan Linear Programming Results menunjukkan hasil perhitungan.
 Tampilan Ranging khususnya pada kolom Lower Bond dan Upper Bond menunjukkan batas
maksimal (minimum dan maksimum) pada koefisien variabel dan pada nilai kendala, dimana
pada rentang nilai antara Lower Bond dan Upper Bond, penambahan atau pengurangan nilai
solusi yang optimal adalah sebanding (linear) dengan penambahan atau pengurangan koefisien
variabel atau nilai kendala.
 Tampilan Original Problem w/answer, menunjukkan hasil perhitungan beserta persoalan yang
diselesaikannya.
 Tampilan Iterations, menunjukkan langkah-langkah dalam metode Simpleks, untuk
menyelesaikan persoalan LP.
  Tampilan Dual, menunjukkan permasalahan dual primal atau penyelesaian dual problem  dari
primal problem atau sebaliknya.
 Tampilan Graph, menunjukkan secara grafik, hasil perhitungan LP. Tampilan ini hanya akan
muncul jika yang diselesaikan persoalan 2 dimensi (bisa digambarkan dengan grafik dengan
sumbu x dan y).
 DAFTAR PUSTAKA
Pengertian Metode Simpleks
[Link]
[Link]
Linear_Programming_Melalui_Metode_Simpleks/fulltext/578802d308aedc252a936fee/Analisis-
[Link]
[Link]

Karakteristik Linear Programming:

Siringoringo, Hotniar. Seri Teknik Riset Operasional. Pemrograman Linear. Penerbit Graha
Ilmu. Yogyakarta. 2005.
4. Taylor III, Bernard W. Sains Manajemen. Pemograman [Link] Salemba [Link]
Jersey. 2019.

Problem Maksimiasi
[Link]

Tipe Irregular dala Linear Porgramming

Subambang : Laporan Akhir Inesntif Buku Ajar Sekolah Tinggi Ilmu Ekonomi Graha Kirana