Persoalan transportasi membahas pendistribusian komoditas dari sejumlah sumber (supply) kepada sejumlah tujuan (destination, demand) dengan tujuan meminimumkan ongkos pengangkutan yang terjadi. Ciri-ciri khusus persoalan transportasi adalah sebagai berikut:

  1. Terdapat sejumlah sumber dan sejumlah tujuan tertentu.
  2. Kuantitas komoditas atau barang yang didistribusikan dari setiap sumber dan yang diminta oleh setiap tujuan, besarnya tertentu.
  3. Komoditas yang dikirim atau diangkut dari suatu sumber ke tujuan, besarnya sesuai dengan permintaan atau kapasitas sumber.
  4. Ongkos pengangkutan komoditas dari suatu sumber ke suatu tujuan besarnya tertentu.
Untuk menyelesaikan persoalan transportasi, harus dilakukan langkah-langkah sebagai berikut:
  1. Tentukan solusi fisibel basis awal.
  2. Tentukan entering variabel dari variabel-variabel non basis. Bila semua variabel sudah memenuhi kondisi optimum, maka STOP. Bila belum, lanjutkan ke langkah 3.
  3. Tentukan leaving variabel diantara variabel-variabel basis yang ada, kemudian hitung solusi yang baru. Kembali ke langkah 2.

SUMBER: Dimyati A, Operations Research, Model-Model Pengambilan Keputusan, Sinar Baru Algensindo, Bandung, 2006.

Metode simpleks merupakan prosedur aljabar yang bersifat iterative, yang bergerak selangkah demi selangkah, dimulai dari suatu titik ekstrim pada daerah fisibel (ruang solusi) menuju ke titik ekstrim yang optimum.
Maksimumkan: z = c1x1 + c2x2 + … + cnxn
Berdasarkan pembatas:

a11x1 + a12x2 + … + a1nxn = b1
a21x1 + a22x2 + … + a2nxn = b2
.
.
.
am1x1 + am2x2 + … + amnxn = bm
x1, x2, …, xn >= 0
Definisi:
  1. Solusi basis adalah solusi dimana terdapat sebanyak-banyaknya m variabel berharga bukan nol.
  2. Solusi basis fisibel adalah jika seluruh variabel pada suatu solusi basis berharga non negative.
  3. Solusi fisibel tidak ekstrim adalah solusi fisibel titik ekstrim atau titik sudut yang tidak terletak pada suatu segmen garis yang menghubungkan dua solusi fisibel lainnya.
Ada tiga sifat pokok titik ekstrim ini, yaitu:
Sifat 1.a : jika hanya ada satu solusi optimum, maka pasti ada satu titik ekstrim.
Sifat 1.b : jika solusi optimumnya banyak.
Sifat 2 : hanya ada sejumlah terbatas titik ekstrim pada setiap persoalan.
Sifat 3 : jika suatu titik ekstrim memberikan harga z yang lebih baik dari yang lainnya, maka pasti solusi itu merupakan solusi optimum.
Sifat 3 ini menjadi dasar dari metode simpleks yang prosedurnya meliputi 3 langkah sebagai berikut:
  1. Langkah inisialisasi: mulai dari suatu titik ekstrim (0,0).
  2. Langkah iterative: bergerka menuju titik ekstrim berdekatan yang lebih baik. Langkah ini diulangi sebanyak diperlukan.
  3. Aturan penghentian: memberhentikan langkah ke-2 apabila telah sampai pada titik ekstrim yang terbaik (titik optimum).

SUMBER: Dimyati A, Operations Research, Model-Model Pengambilan Keputusan, Sinar Baru Algensindo, Bandung, 2006.

Teori antrian adalah teori yang menyangkut studi matematis dari antrian-antrian atau baris-baris penunguan. Kebanyakan model antrian menganggap bahwa input dan output dari sistem antrian menurut proses birth and death. Proses birth and death ini terjadi secara random yang rata-rata terjadinya hanya bergantung pada keadaan yang sedang berlangsung (current state) dari sistem (jumlah calling unit dari sistem antrian).
Jelasnya adalah:
  1. Birth postulate adalah sistem pada state En (n = 0, 1, 2, …) pada saat t, kemungkinan bahwa tepat ada satu kelahiran selama interval waktu t sampai dengan (t + Δt) adalah [λn Δt + 0 (Δt)], dimana λn positif konstan.
  2. Death postulate adalah sistem pada state En (n=0, 1, 2, …) pada saat t kemungkinan bahwa tepat ada satu kemataian selama interval waktu t sampai dengan (t + Δt) adalah μ0 = 0 dan μn positif konstan untuk n > 0.
  3. Multiple jump postulate adalh sistem pada state En (n = 0, 1, 2, …) pada saat t, kemungkinan bahwa jumlah kombinasi kelahiran dan kematian lebih dari satu selama interval waktu t s/d (t + Δt) adalah 0 (Δt).
Keterangan: 0 (Δt) adalah fungsi dari Δt yang karena Δt <<< (kecil sekali, mendekati nol), maka fungsi tersebut akan memenuhi persamaan: limΔt0 0(Δt)/Δt = 0

SUMBER: Dimyati A, Operations Research, Model-Model Pengambilan Keputusan, Sinar Baru Algensindo, Bandung, 2006.

Teori dualitas merupakan salah satu konsep program linier yang penting dan menarik ditinjau dari segi teori dan praktisnya. Hal yang melatar belakangi adalah bahwa setiap masalah program linier mempunyai satu program linier lain yang saling berkaitan yang disebut “dual”, sedemikian sehingga solusi pada persoalan semula yang disebut “primal” juga member solusi pada dualnya. Bentuk umum masalah primal dual adalah sebagai berikut:
Primal:
Maksimumkan: z = c1x1 + c2x2 + … + cnxn
Berdasarkan pembatas:
a11x1 + a12x2 + … + a1nxn <= b1 a21x1 + a22x2 + … + a2nxn <= b2 . . . am1x1 + am2x2 + … + amnxn <= bm x1, x2, …, xn >= 0
Dual
Minimumkan: w = b1y1 + b2y2 + … + bmym
Berdasarkan pembatas:

a11y1 + a21y2 + … + am1ym >= c1
a12y1 + a22y2 + … + am2ym >= c2
.
.
.
a1ny1 + a2ny2 + … + amnym >= cn
y1, y2, …, ym >= 0
Jika dibandingkan kedua persoalan tersebut di atas, maka terdapat korespondensi antara primal dengan dual, yaitu sebagai berikut:
  1. Koefisien fungsi tujuan primal menjadi konstanta ruas kanan bagi dual, sedangkan konstanta ruas kanan primal menjadi koefisien fungsi tujuan bagi dual.
  2. Untuk setiap pembatas primal ada satu variabel dual, dan untuk setiap variabel primal ada satu pembatas dual.
  3. Tanda ketidaksamaan pada pembatas akan bergantung pada fungsi tujuannnya.
  4. Fungsi tujuan berubah bentuk (maksimasi menjadi minimasi dan begitu juga sebaliknya).
  5. Setiap kolom pada primal berkorespondensi dengan baris (pembatas) pada dual.
  6. Setiap baris (pembatas) pada primal berkorespondensi dengan kolom pada dual.
  7. Dual dari dual adalah primal.
SUMBER: Dimyati A, Operations Research, Model-Model Pengambilan Keputusan, Sinar Baru Algensindo, Bandung, 2006.