OPERATION RESEARCH

I.              PROGRAM LINEAR

1.1 Definisi Program Linier

Pemograman linier menggunakan model matematika untuk menggambarkan suatu masalah. Sifat linier di sini berarti semua fungsi matematika harus berupa fungsi linier, sedangkan kata pemrograman berarti perencanaan. Sehingga pemrograman linier meliputi perencanaan aktivitas untuk mendapatkan hasil optimal, yaitu sebuah hasil yang mencapai tujuan yang terbaik (menurut model matematika) diantara semua kemungkinan alternative yang ada. Hal terpenting yang perlu kita lakukan adalah mencari tahu tujuan penyelesaian masalah dan apa penyebab masalah tersebut.

1.2 Istilah untuk Solusi Model

Solusi dalam pemrograman linier adalah nilai untuk variabel keputusan (x₁, x₂, ...,x_n), tanpa menghiraukan apakah solusi tersebut merupakan pilihan yang diinginkan maupun yang diperbolehkan. Tipe solusi yang berbeda akan diidentifikasi dengan menggunakan sifat yang tepat.

a.    Solusi layak (feasible solution) adalah solusi dimana semua kendala yang ada terpenuhi.

b.    Solusi tak layak(infeasible solution) adalah solusi dimana sedikitnya satu kendala tidak terpenuhi atau dengan kata lain dilanggar.

c.    Solusi optimal adalah solusi layak yang memiliki nilai fungsi tujuan terbaik. Permasalahan pemrograman linier tidak mempunyai solusi optimal terjadi hanya jika:

-          Tidak ada solusi layak

-          Kendala-kendala tidak mencegah naiknya nilai fungsi tujuan (Z)  ke arah yang tidak terdefinisi, baik ke arah positif atau negatif.

d.    Solusi corner-point feasible (CPF) adalah solusi yang ada di setiap sudut daerah layak.

1.3 Model Pemrograman Linier

Kunci terpenting dalam model pemrograman linier adalah sumber daya dan aktivitas dimana m merupakan jenis sumber daya yang berbeda yang dapat digunakan serta n yang merupakan jumlah aktivitas yang dipertimbangkan.

Ada beberapa simbol yang digunakan untuk menunjukkan berbagai komponen model pemrograman linier. Berikut adalah daftar simbol dengan tafsirannya untuk permasalahan umum pengalokasian sumber daya ke aktivitas.

Z = nilai dari semua standar performansi

X_i = tingkat aktivitas j ( untuk j = 1, 2, ..., m)

C_j = Penambahan terhadap Z yang diakibatkan oleh peningkatan tiap unit di tingkat aktivitas j.

B_i = jumlah sumber daya i yang tersedia untuk aktivitas ( untuk i = 1, 2, ..., m)

A_ij = jumlah sumber daya i yang dipakai tiap unit aktivitas j

Suatu model akan membuat permasalahan menjadi suatu bentuk pengambilan keputusan mengenai tingkat aktivitas sehingga x₁, x₂, ...,x_n disebut variabel keputusan. Nilai c_j, b_i, dan a_ij (untuk i=1,2,...,m dan j=1,2,...,n) adalah input konstan untuk suatu model. Serta c_j, b_i, dan a_ij  disebut parameter model.

1.4 Bentuk Permasalahan Pemrograman Linier Model

a.    Mengoptimalkan fungsi tujuan

Maksimalisasi : Z= c₁x₁+c₂x₂+...+c_nx_n

Minimalisasi : Z= a₁x₁+c₂x₂+...+c_nx_n

b.    Beberapa kendala fungsional pertidaksamaan dengan tanda lebih besar ( untuk meminimalkan fungsi tujuan) dan tanda kurang dari (untuk memaksimalkan fungsi tujuan) atau sama dengan.

Maksimalisasi: c_i1x₁+c_i2x₂+...+c_inx_n ≤ b_i (untuk beberapa nilai i)

Minimalisasi : c_i1x₁+c_i2x₂+...+c_inx_n ≥ b_i (untuk beberapa nilai i)

c.    Beberapa kendala fungsional dengan bentuk persamaan

c_i1x₁+c_i2x₂+...+c_inx_n = b_i untuk beberapa nilai i

d.    Menghilangkan kendala nonnegativitas untuk beberapa variabel keputusan

X_j tidak dibatasi (unrestricted) untuk beberapa nilai j.

1.5 Karakteristik atau Asumsi Dasar Program Linear

1.    Proporsionalitas

Asumsi ini berarti naik turunnya nilai Z dan penggunaan sumber atau fasilitas yang tersedia akan berubah secara sebanding (proporsional) dengan perubahan tingkat kegiatan.

2.    Additivitas

Asumsi ini berarti setiap fungsi dalam model pemrograman linear (baik fungsi tujuan maupun fungsi disebelah kiri kendala fungsional) adalah jumlah kontribusi individu pada masing-masing aktivitas.

3.    Divisibilitas

Asumsi ini menyatakan bahwa keluaran (output) yang dihasilkan oleh setiap kegiatan dapat berupa bilangan pecahan.

4.    Kepastian

Asumsi ini menyatakan bahwa semua parameter yang terdapat dalam model program linear dapat diperkirakan dengan pasti, meskipun jarang tepat.

1.6 Metoda Grafis

Cara ini dapat digunakan untuk menyelesaikan permasalahan pemrograman linier dengan dua variable keputusan. Walaupun akan timbul banyak kesulitan, metode ini masih memungkinkan untuk menyelesaikan permasalahan yang mempunyai tiga variable keputusan.

Contoh Soal:

PT Iguana Tekstil memiliki sebuah pabrik yang akan memproduksi 2 jenis produk, yaitu kain sutera dan kain wol. Untuk memproduksi kedua produk diperlukan bahan baku benang sutera, bahan baku benang wol dan tenaga kerja. Maksimum penyediaan benang sutera adalah 60 kg per hari, benang wol 30 kg per hari dan tenaga kerja 40 jam per hari. Kedua jenis produk memberikan keuntungan sebesar Rp 40 juta untuk kain sutera dan Rp 30 juta untuk kain wol. Masalahnya adalah bagaimana menentukan jumlah unit setiap jenis produk yang akan diproduksi setiap hari agar keuntungan yang diperoleh bisa maksimal?

Jawab:  Langkah-langkah:

1. Tentukan variabel: X₁=kain sutera ; X₂=kain wol

2.  Fungsi tujuan : Zmax= 40X₁ + 30X₂

3. Fungsi kendala / batasan:   1) 2X₁ + 3X₂ ≤ 60    (benang sutera)

2)           2X₂ ≤30     (benang wol)

3) 2X₁ + X₂ ≤ 40      (tenaga kerja)

4. Membuat grafik

   Pers (1)   2X₁ + 3X₂ = 60   

X₁=0, X₂ =60/3 = 20                  

X₂=0, X₁= 60/2 = 30

   Pers (2)    2X₂ = 30            ;      X₂=15

   Pers (3)   2X₁ + X₂ = 40

X₁=0, X₂ = 40

                  X₂=0, X₁= 40/2 = 20

 

                                 Daerah penyelesaian

Gambar 2.1 Grafik Daerah Penyelesaian

Dari gambar 2.1 dapat kita ketahui bahwa titik ekstrim yang optimal berada pada titik C, yaitu titik potong antara persamaan (1) dan (3), sehingga:

Titik potong (1) dan (3) :

2X₁ + 3X₂ = 60

2X₁ + X₂    = 40 -

2X₂=20 ó X₂=10

Masukkan X₂ ke kendala (1)

2X₁ + 3X₂   = 60

2X₁ + 3.10 = 60

2X₁ + 30    = 60

2X₁ = 30 ó X1 = 15

Masukkan nilai X₁ = 15 dan X₂=10 ke Z

Zmax = 40X₁ + 30X₂

          = 40.15 + 30.10 = 600 + 300 = 900 (optimal)

Kesimpulan :

Untuk memperoleh keuntungan optimal, maka X₁ = 15 dan X₂ = 10 dengan keuntungan sebesar Rp 900 juta.

II.            METODE SIMPLEKS

Metode simpleks adalah salah satu teknik penyelesaian pemrograman linier selain menggunakan metode grafis. Metode simpleks diaplikasikan pada komputer dan metode tersebut sangat membantu untuk permasalahan pemrograman linier yang rumit karena menggunakan fungsi dan variabel yang banyak dan tak mampu diselesaikan oleh metode grafis. 

2.1 Beberapa istilah dalam metode simpleks:

1.    Solusi augmentasi merupakan sebuah solusi untuk variabel-variabel asli (variabel-variabel keputusan) yang telah diaugmentasi dengan nilai variabel-variabel slack yang bersesuaian.

2.     Solusi titik sudut layak  (corner-points feasible solution) atau CPF adalah titik perpotongan dari persamaan fungsi batasan yang memenuhi daerah fesibel.

3.    Iterasi adalah tahapan perhitungan dimana nilai dalam perhitungan itu tergantung dari nilai tabel sebelumnya.

4.    Variabel non basis adalah variabel yang nilainya diatur menjadi nol pada sembarang iterasi. Dalam terminologi umum, jumlah variabel non basis selalu sama dengan derajat bebas  dalam sistem persamaan.

5.    Variabel basis merupakan variabel yang nilainya bukan nol pada sembarang iterasi. Pada solusi awal, variabel basis merupakan variabel slack (jika fungsi kendala merupakan pertidaksamaan ≤ ) atau variabel buatan (jika fungsi kendala menggunakan  pertidaksamaan ≥ atau =). Secara umum, jumlah variabel basis selalu sama  dengan  jumlah fungsi pembatas (tanpa fungsi non negatif).

6.    Variabel slack adalah variabel yang ditambahkan ke model matematik kendala untuk mengkonversikan  pertidaksamaan ≤ menjadi persamaan (=). Penambahan variabel ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel slack akan berfungsi sebagai variabel basis.

7.    Variabel surplus adalah variabel yang dikurangkan  dari model matematik kendala untuk mengkonversikan  pertidaksamaan ≥ menjadi persamaan (=). Penambahan ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel surplus tidak dapat berfungsi sebagai variabel basis

2.2 Solusi basis layak (Basic Feasible Solution)

Solusi basis layak atau basic feasible solution merupakan solusi dari titik sudut layak (CPF) dimana nilai variabel-variabel asli (variabel-variabel keputusan) telah diagumentasi dengan nilai dari variabel-variabel slack yang bersesuaian.

Sifat-sifat solusi basis:

a.    Setiap variabel ditunjuk sebagai variabel nonbasis atau sebagai variabel basis

b.    Jumlah variabel basis sama dengan jumlah fungsi kendala (disebut persamaan). Oleh karena itu, jumlah variabel nonbasis sama dengan total jumlah variabel dikurangi jumlah fungsi kendala.

c.    Variabel-variabel non basis ditetapkan sama dengan nol.

d.    Nilai-nilai variabel basis ditetapkan sebagai solusi simultan dari sistem persamaan (fungsi kendala pada bentuk yang diaugmentasi)

e.    Jika variabel basis memenuhi kendala nonnegatif, solusi basis adalah solusi BF.

2.3 Prosedur penyelesaian program linear dengan Metode Simpleks BFS

1.    Formulasikan persoalan menjadi model linear

2.    Tambahkan variabel Slack pada masing-masing constraint (pembatas) untuk memperoleh bentuk standar. Model ini digunakan untuk identifikasi solusi feasible awal dari pembatas bertanda lebih kecil atau sama dengan.

3.    Inisialisasi : pemilihan x₁ dan x₂ sebagai variabel nonbasis (variabel diberi nilai nol) sebagai solusi BF awal didasarkan pada konsep semua variabel keputusan sama dengan nol sebagai solusi CPF awal. Pemilihan ini menghilangkan pekerjaan yang diperlukan untuk menyelesaikan variabel basis dari sistem pemrograman linier.

4.    Uji optimalitas digunakan untuk menguji apakah variabel nonbasis menunjukkan laju perbaikan pada nilai Z jika variabel tersebut ditingkatkan nilainya dari nol (sementara ini variabel basis disesuaikan nilainya agar memenuhi sistem persamaannya). Jika laju perbaikan dari variabel tersebut positif maka solusi CPF yang bersebrangan memiliki penyelesaian lebih baik daripada CPF saat ini sehingga disimpulkan tidak optimal dan berlanjut ke langkah iterasi selanjutnya. Jika tidak ditemukan laju pergerakan ke arah positif maka solusi CPF saat ini merupakan solusi yang optimal dan prosedur pun selesai. Iterasi untuk menemukan BF yang baru dengan prosedur pencarian solusi simultan pada sistem pemrograman linier atau disebut metode eliminasi Gauss-Jordan. Kemudian melakukan uji optimalitas sampai tercapai solusi optimal.

2.4 Metode Simpleks Tabel

Metode simpleks adalah teknik untuk menyelesaikan program linier yang tidak mampu diselesaikan oleh metode grafis. Metode simpleks sendiri memiliki kerangka berpikir beberapa macam yaitu dengan menggunakan BFS (basis fesibel solution) dan metode simpleks dengan menggunakan tabel. Metode simpleks dengan menggunakan tabel hanya memuat tiga informasi penting yaitu koefisien pada variabel, konstanta pada ruas kanan persamaan dan variabel basis yang muncul untuk setiap persamaan.

Langkah langkah metode simpleks tabel:

1)    Inisialisasi

Langkah pertama yaitu memasukkan variabel slack. Kemudian pilihlah variabel keputusan yang kemudian akan dijadikan sebagai variabel nonbasis awal. Lalu pilihlah varibel slack yang akan dijadikan sebagai variabel basis awal.

2)    Uji Optimalitas

Dalam uji optimalitas, BFS saat ini dapat dikatakan optimal apabila setiap koefisien dalam baris nol adalah nonnegatif, sehingga langkah-langkah dalam metode simpleks tabel dapat selesai. Namun apabila setiap koefisien dalam baris nol adalah  bukan nonnegatif, maka langkah selanjutnya adalah iterasi untuk mendapatkan BFS berikutnya.

3)    Iterasi

• Langkah 1:

Tentukanlah variabel basis yang masuk dengan memilih variabel dengan koefisien negatif yang mempunyai nilai absolut paling besar (paling negatif). Kemudian letakkanlah kotak di sekitar kolom dibawah koefisien tersebut, kolom ini sering disebut kolom sumbu atau pivot column.

• Langkah 2:

Langkah selanjutnya yaitu dengan menentukan variabel basis yang keluar. Hal ini dapat dilakukan dengan menerapkan uji rasio minimum yaitu dengan cara:

~        Mengambil masing-masing koefiien dalam kolom sumbu yang positif

~        Membagi masing-masing angka pada ruas kanan dengan koefisien pada kolom sumbu dalam baris yang sama

~        tentukanlah baris mana yang mempunyai rasio yang paling kecil

~        variabel basis pada baris adalah variabel basis yang keluar, kemudian gantilah variabel itu dengan variabel basis yang masuk dalam kolom variabel basis tabel simpleks yang berikutnya.

Kemudian letakkanlah kota disekitar baris ini yang biasa disebut baris sumbu (pivot row) dan angka yang berada dalam baris sumbu dan kolom sumbu disebut angka sumbu (pivot number).

• Langkah 3:

Langkah selanjutnya adalah carilah BFS baru dengan   menggunakan operasi baris dasar. Hal ini dimaksudkan untuk membentuk tabel simpleks yang baru.

2.5 Metode Big M

Metode Big M digunakan untuk menyelesaikan fungsi-fungsi dalam program linier yang tidak berada dalam bentuk baku atau standar  ( bentuk standar adalah memaksimalkan Z sesuai dengan kendala fungsional dalam bentuk  ≤ dan kendala nonegativitas di semua variabel) dan salah satu contoh masalah dalam kendala funsional adalah bila fungsi dalam bentuk-bentuk = atau ≥ atau bahkan ruas kanan yang negatif.

Masalah ini akan muncul bila kita akan mencari basis fesibel awal sehingga sebelum mencari variabel apa yang akan menjadi variabel nonbasis bahkan basis perlu dilakukan suatu teknik pendekatan khusus untuk mengubah fungsi tersebut ke bentuk baku atau standar. Teknik pendekatan khusus tersebut dengan cara menambahkan variabel dummy (variabel artifisial) pada kendala fungsional dan teknik ini disebut dengan teknik variabel artifisial.

Ada pun prosedur mendapatkan BF awal pada kendala fungsional adalah

1. Gunakan teknik variabel artifisial

Tambahkan variabel artifisal nonegatif pada fungsi kendala yang belum baku, dan anggaplah variabel artifial tersebut sebagai salah satu variabel slack

2. Tugaskan pinalty yang besar

Berilah nilai variabel artifisial dengan nilai > 0 sehingga koefisien variabel artifisial menjadi M (big m) secara simbolik yang menunjukkan bahwa variabel artifisial tersebut memiliki angka positif raksasa ( dan pengubahan atas variabel artifisial bernilai 0 (variabel nonbasis) dalam solusi optimal disebut metode big m).

2.6 Metode Dua Phase     

Dalam menyelesaiakan suatu persoalan dimana variabelnya lebih dari dua, juga menggunakan suatu metode yang bertahap. Metode ini disebut sebagai metode dua phase.

Pada dasarnya Metode dua fase (phase) sama seperti metode big M yang juga digunakan untuk menyelesaikan persoalan pemrograman linier yang memiliki bentuk yang tidak standar.  Berikut ini adalah prosedur menggunakan metode dua fase.

1.    Inisialisasi

Menambahkan variabel-variabel artifisal pada fungsi kendala yang memiliki bentuk tidak standar. Variabel artificial ini ditambahkan pada fungsi batasan yang pada mulanya memiliki tanda (³). Hal ini digunakan agar dapat mencari solusi basic fesibel awal.

2.    Fase 1

Digunakan untuk mencari basic fesibel awal.  Pada fase 1 memiliki langkah-langkah dimana tujuannya adalahm meminimalkan variabel artifisial ( Min Y= Xa)

s.t : Ax = b

           X = 0

Pada fase pertama bertujuan untuk memperoleh penyelesaian yang optimum dari suatu permasalahan. Pada fase pertama fungsi tujuan selalu minimum variabel artificial, meskipun permasalahan yang ada adalah permasalahan yang maksimum. Dalam meyelesaiakan pada fase pertama, yaitu membuat nilai nol dulu pada variabel artifisial, kemudian melanjutkan iterasi seperti proses iterasi biasanya(dengan aturan meminimumkan). Berhenti ketika pada baris ke-0 bernilai £ 0.

Fase pertama dianggap telah selesai atau memperoleh penyelesaian yang optimal adalah apabila variabel artifisial adalah merupakan variabel basis. Sedangkan apabila variabel artifisial adalah variabel non basis, maka masalah dianggap tidak mempunyai penyelesaian yang optimal, sehingga harus dilanjutkan ke fase yang kedua.

Pada fase kedua, tujuannya sama seperti fase pertama, yaitu untuk mendapatkan penyelesaian yang optimal dari suatu permasalahan yang ada. Fase dua berhenti sesuai dengan tujuan awal permasalahan.

3.    Fase 2

Digunakan untuk mencari solusi optimum pada permasalahan riil. Karena variabel artifisial bukan merupakan termasuk variabel dalam permasalahan riil, variabel artifisial tersebut dapat dihilangkan ( Xa=0). Bermula dari solusi BF yang didapatkan dari akhir fase 1. Pada fase 2 ini memiliki langkah-langkah sebagai berikut:

1.    Fungsi tujuan bisa memaksimalkan dan juga bisa meminimalkan tergantung pada permasalahan yang dihadapi.

2.    Menggunakan fungsi batasan (s.t) dari fase 1, melakukan proses iterasi seperti biasanya dan berhenti sesuai funsi obyektif awal

2.7 Interpretasi Tabel Simpleks

Dalam membaca dan menginterpretasikan tabel simpleks, langkah yang harus diperhatikan pada awalnya yaitu memeiksa apakah tabel sudah optimal atau belum. Hal ini dapat dilihat dari koefisien fungsi tujuan yang berada pada baris ke 0. Untuk permasalahan yang maksimal, tabel simpleks dapat dipastikan sudah optimal apabila semua nilai pada baris ke 0 adalah positif atau bernilai 0. Sedangkan untuk permasalahan yang minimal, tabel simpleks dapat dipastikan sudah optimal apabila semua nilai pada baris ke 0 adalah negatif atau bernilai 0.

Setelah itu, barulah tabel simpleks dapat dibaca dan diinterpretasikan. Beberapa hal yang dapat dibaca dan diinterpretasikan dari tabel simpleks adalah:

1.    Penyelesaian yang optimal bagi variabel keputusan

Apabila tabel sudah optimal, kita dapat mengetahui bagaimana penyelesaian yang optimal untuk permasalahan yang ada. Dengan demikian, kita dapat mengetahui berapa nilai dari masing-masing variabel keputusan yang dibutuhkan agar dapat memperoleh hasil yang optimal, baik maksimal maupun minimal.

2.    Status Sumber Daya yang tersedia

Hal ini dapat dilihat dari masing-masing variabel basis dari fungsi batasan yang ada. Disamping itu, dalam fungsi batasan juga dilihat batasan mana yang harus ditambah varibael artifical, variabel slack, dan variabel surplus. Untuk batasan yang memiliki tanda ³, maka ditambah dengan variabel surplus dan variabel slack. Untuk batasan yang memiliki tanda £, ditambah variabel slack, dan untuk batasan dengan tanda =, ditambah varibel arttificial

3.    Harga bayangan yang ada

Hal ini dapat dilihat dari koefisien yang dimiliki oleh variabel surplus dan variabel slack dari baris fungsi tujuan yang ada, terletak pada baris ke 0.

           

Berdasarkan penjelasan diatas, maka juga bisa ditunjukkan ,mengenai penjelasan dalam bentuk tabelnya.

Tabel 3.1 tabular simplek awal

Variabel basis	Bentuk Tabular
	Z	x1   x2 ... xj... xn    xn+1... xn+m	RHS
Z xn+1 ... n+i ... Xn+m	1 0 ... 0 ... 0	-c1 -c2 ... –cj... –cn    0 ....   0 a11 a12 ...  a1j...a1n    1 ....    0 ... ai1  ai2 ...  aij... ain    0 ....    0 ... am1 am2 ... amj... amn  0 ....    1	0 b1 ... bi ... bm

Interpretasi tabel simpleks:

RHS: nilai yang berada di kanan persamaan yaitu nilai dibelakang tanda sama dengan (=). Perubahan nilai-nilai konstanta x₁ sampai dengan x_n+m akan berhenti setelah baris ke-0 (fungsi tujuan) tidak ada yang bernilai negatif yang memiliki fungsi tujuan awal memaksimalkan dan juga mempunyai arti fungsi tujuan telah mencapai optimum. x₁ sampai dengan x_n merupakan variabel dasar yaitu variabel yang diperoleh dari fungsi kendala permasalahan riil. Begitupun sebaliknya perubahan nilai-nilai konstanta x₁ sampai dengan x_n+m akan berhenti setelah baris ke-0 (fungsi tujuan) ada yang bernilai negatif atau lebih tepatnya £ 0, yang memiliki fungsi tujuan awal memimimumkan dan juga mempunyai arti fungsi tujuan telah mencapai optimum Sedangkan x_n+1 sampai dengan x_n+m merupakan variabel slack , variabel surplus, dan variabel artificial yaitu variabel yang ditambahkan ke fungsi batasan, variabel ini berjumlah sebanyak jumlah fungsi batasan.

III.           DUALITAS

3.1 Hubungan Primal Dual

3.2 Complementary Basic Solution

Karena suatu dual berwujud masalah program linier, maka memiliki corner point solution. Tetapi karena fungsi-fungsi batasan mengandung tanda ³ maka untuk mengubahny menjad persamaan, harus dikurangi dengan surplus variabel. Dengan kata lain dapat ditulis berikut :

WA ³ c                                      WA – variabel surplus = c

Z_j-C_j ³ 0             Z_j ³ C_j             Z_j – variabel surplus = C_j

Maka variabel surplus = Z_j-C_j

Hubungan antara variabel-variabel primal dual dalam program linier:

Variabel Primal	Variabel Dual
Variabel Asli : Xj Variabel Slack : Xn+1	Variabel Surplus : Zj-Cj Variabel Asli : Wi

Berdasarkan tabel diatas, variabel surplus pada dual adalah variabel asli pada masalah primalnya. Sebaliknya variabel slack pada primal adalah variabel asli pada masalah dualnya.

Dalam tabel, dapat dituliskan sebagai berikut :

X₁        X₂        . . .       X_n        X_n+1     X_n+2     . . .       X_n+m

baris 0 :          Z₁-C₁   Z₂-C₂  . . .       Z_n-C_n  W₁      W₂      . . .       W_n

Karena X_j merupakan komplemen dari Z_j-C_j, maka X_j (Z_j-C_j) = 0

Sehingga apabila X_j = 0 maka Z_j-C_j ¹0 dan bila X_j ¹0 maka Z_j-C_j = 0

Sedangkan X_n+i merupakan komplemen dari W_i, maka X_n+1 W_i = 0

Sehingga apabila X_n+i = 0 maka W_i ¹0 dan bila X_n+i ¹0 maka W_i = 0

3.3 Metode Dual Simpleks

Metode dual simpleks digunakan jika tabel optimal tidak layak. Jika fungsi kendala ada yang menggunakan pertidaksamaan ≥ dan tidak ada = dalam bentuk umum PL, maka metode dual simpleks dapat digunakan. Ada pun langkah-langkah dalam simpleks dual adalah:

-          Untuk persamaan pemrograman linier dengan kasus minimize dan dengan fungsi batasan ≥

a.    Cari basis B sedemikian hingga Z_j-C_j = C_BB^-1a_j-c_j≤0, untuk semua j

b.    Buat tabel simpleks seperti pada primal

c.    Jika b=B^-1b≥0, berhenti dan penyelesaian optimal

d.    Pilih pivot pada baris ke-r, dimana br = min (bi), (bi<0)

e.    Jika Yr_j≥ 0, _j, berhenti (D tidak terbatas)

f.     Pilih pivot pada kolom ke k dimana

                               = min

g.    Pivot pada Yr_k dan kembali ke-c

KESIMPULAN

Ada pun kesimpulan yang dapat diperoleh dari makalah ini adalah:

1.    Pemograman linier menggunakan model matematika untuk menggambarkan suatu masalah. Sifat linier di sini berarti semua fungsi matematika harus berupa fungsi linier, sedangkan kata pemrograman berarti perencanaan. Dari pengertian kata linier dan program tersebut dapat ditarik kesimpulan bahwa pengertian program linier adalah perencanaan yang berupa fungsi linier.

2.    Kunci terpenting dalam model pemrograman linier adalah sumber daya dan aktivitas dimana m merupakan jenis sumber daya yang berbeda yang dapat digunakan serta n yang merupakan jumlah aktivitas yang dipertimbangkan sehingga dapat membentuk suatu permodelan matematika dua jenis fungsi yaitu fungsi tujuan dan fungsi batasan dari permasalahan di dunia real.

3.    Metode simpleks digunakan jika suatu permodelan linier memiliki lebih dari dua variabel. Solusi untuk mendapatkan nilai yang optimum dalam tabel simpleks menggunakan solusi basis fesibel, metode simpleks tabel, metode big m dan metode dua fase. Dua metode terakhir, metode big m dan metode dua fase digunakan apabila model pemrograman linier tidak dalam bentuk standar. Dan untuk mendapatkan solusi optimum dalam metode simpleks memiliki beberapa prosedural umum seperti inisialisasi, iterasi dan uji optimalitas.

4.    Pemrogramragaman linier dalam bentuk dualitas digunakan untuk melihat keterkaitan masalah primal dan dualnya seperti pada hubungan variabel, nilai tengah, dan fungsi batasan. Masalah dualitas sendiri dapat diselesaikan oleh dua solusi yaitu complementary basic solution dan dual simpleks.