TEKNIK LINIERISASI UNTUK PERSOALAN
PROGRAM KUADRATIK NOL-SATU
TESIS
Oleh
M KHAHFI ZUHANDA
147021004/MT
PROGRAM STUDI MAGISTER MATEMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAMUNIVERSITAS SUMATERA UTARA
MEDAN
2016
TEKNIK LINIERISASI UNTUK PERSOALAN
PROGRAM KUADRATIK NOL-SATU
T E S I S
Diajukan Sebagai Salah Satu SyaratUntuk Memperoleh Gelar Magister Sains dalam
Program Studi Magister Matematika padaFakultas Matematika dan Ilmu Pengetahuan Alam
Universitas Sumatera Utara
OlehM Khahfi Zuhanda
147021004/MT
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAMUNIVERSITAS SUMATERA UTARA
MEDAN
2016
Judul Tesis : TEKNIK LINIERISASI UNTUK PERSOALANPROGRAM KUADRATIK NOL-SATU
Nama Mahasiswa : M Khahfi ZuhandaNomor Pokok : 147021004Program Studi : Matematika
Menyetujui,Komisi Pembimbing
(Prof. Dr. Opim Salim S, MSc) (Dr. Mardiningsih, MSi)Ketua Anggota
Ketua Program Studi Dekan
(Prof. Dr. Herman Mawengkang) (Dr. Sutarman, MSc)
Tanggal lulus: 18 Mei 2016
Telah diuji pada
Tanggal 18 Mei 2016
PANITIA PENGUJI TESIS
Ketua : Prof. Dr. Opim Salim S, MSc
Anggota : 1. Dr. Mardiningsih, MSi
2. Prof. Dr. Saib Suwilo, MSc
3. Dr. Marwan Ramli, MSi
ABSTRAK
Seiring perkembangan zaman, perkembangan ilmu pengetahuan meningkat ta-
jam. Ilmu pengetahuan telah banyak membantu manusia dalam memberikan so-
lusi kompleksnya permasalahan dalam kehidupan sehari-hari. Mulai dari bidang
kedokteran, ekonomi, sosial, politik, sumber daya, dan lain-lain. Permasalahan
optimasi non linier tak luput dalam memberi kontribusi dalam segala aspek.
Dalam beberapa tahun terakhir, telah banyak matematikawan mengembangkan
permasalahan non linier, salah satunya program kuadratik nol-satu. Program
kuadratik nol-satu merupakan kelas khusus dari pemrograman non linier. Pro-
gram kuadratik nol-satu ditujukan untuk meminimalkan subjek fungsi objektif
kuadratik dengan beberapa kendala kuadratik, dengan kondisi bahwa masing-
masing variabel dibatasi nilai nol atau satu.
Kata kunci: program kuadratik, biner, linierisasi, integer.
i
ABSTRACT
Along with the times, the development of science increased sharply. Science hashelped humans in providing solutions to complex problems in everyday life. Start-ing from the fields of medicine, economics, social, political, resources, and others.Non-linear optimization problems did not escape in contributing in all aspects. Inrecent years, many mathematicians have developed a non-linear problems, one ofwhich is a zero-one quadratic programming. Zero-one quadratic programming is aspecial class of non-linear programming. Zero-one quadratic programming aimedat minimizing the quadratic objective function subject to some constraints quadrat-ic, with the condition that each variable is limited by zero or one.
Keyword: quadratic programming, biner, linearization, integer.
ii
KATA PENGANTAR
Setinggi puji dan sedalam syukur penulis serahkan kehadirat Allah SWT
yang telah memberikan berkat dan rahmadNya sehingga penulis dapat menyele-
saikan tesis yang berjudul ”TEKNIK LINIERISASI UNTUK PERSOALAN
PROGRAM KUADRATIK NOL-SATU”. Tesis ini merupakan salah satu
syarat untuk menyelesaikan studi pada Program Studi Magister Matematika Fakul-
tas Matematika dan Ilmu Pengetahuan Alam (FMIPA) Universitas Sumatera
Utara.
Pada kesempatan ini, penulis menyampaikan terimakasih sebesar-besarnya
kepada :
Prof. Dr. Runtung Sitepu, SH, M.Hum selaku Rektor Universitas Sumatera
Utara
Dr. Sutarman, M.Sc selaku Dekan Fakultas Matematika dan Ilmu Penge-
tahuan Alam (FMIPA) Universitas Sumatera Utara.
Prof. Dr. Herman Mawengkang selaku Ketua Program Studi Magister
Matematika FMIPA USU yang telah banyak memberikan bantuan dalam penulisan
tesis ini.
Prof. Dr. Saib Suwilo, M.Sc selaku Sekretaris Program Studi Magister
Matematika FMIPA USU yang telah banyak memberikan bimbingan dan arahan
serta motivasi kepada penulis dalam penulisan tesis ini.
Prof. Dr. Opim Salim Sitompul, M.Sc selaku Pembimbing Utama yang
telah banyak memberikan bimbingan dan arahan serta motivasi kepada penulis
dalam penulisan tesis ini.
Dr. Mardiningsing, M.Si selaku Pembimbing Kedua yang juga telah banyak
memberikan bimbingan dan arahan serta motivasi kepada penulis dalam penulisan
tesis ini.
iii
Seluruh Staf Pengajar pada Program Studi Magister Matematika FMIPA USU
yang telah banyak memberikan ilmu pengetahuan selama masa perkuliahan.
Kak Misiani, S.Si selaku Staf Administrasi Program Studi Magister Matematika
FMIPA USU yang telah banyak memberikan pelayanan yang baik kepada penulis
selama mengikuti perkuliahan.
Seluruh rekan-rekan Mahasiswa Program Studi Magister Matematika FMIPA
USU tahun 2014 genap (Benny, Hafiz, Manuntun, Mahdi, Anil, Petrus, Desni,
Meriandela, Rina, Arie, Fitri, Helmi, Lily, Wita, dan Winda) yang telah mem-
berikan bantuan moril dan dorongan kepada penulis dalam penulisan tesis ini.
Tak lupa penulis mengucapkan terimakasih sebesar-besarnya dan penghar-
gaan setinggi-tingginya kepada ayahanda Zunaidi, SE yang mencurahkan kasih
sayang dan dukungan kepada penulis, terlebih yang dengan setia mendampingi
dan membantu penulis selama mengikuti perkuliahan hingga sampai penulisan
tesis ini. Tak lupa pula kepada adik-adikku Novi Dara Utami, Arbie Saldi Zusri,
dan Pri Zuri Hartadi yang telah memberikan semangat selama penulisan tesis
ini.Terima kasih kepada sahabat-sahabatku serta rekan-rekan lainnya yang tidak
dapat disebutkan satu-persatu. Semoga Allah SWT memberikan balasan atas
jasa-jasa mereka yang telah diberikan kepada penulis.
Penulis menyadari bahwa tesis ini masih jauh dari sempurna, untuk itu
penulis mengharapkan kritik saran untuk penyempurnaan tesis ini. Semoga tesis
ini dapat bermanfaat bagi pembaca dan pihak-pihak lain yang memerlukannya.
Terimakasih.
Medan, 18 Mei 2016
Penulis,
M Khahfi Zuhanda
iv
RIWAYAT HIDUP
M Khahfi Zuhanda dilahirkan di Medan pada tanggal 30 November 1991
dari pasangan Bapak Zunaidi, SE dan Alm. Ibu Sri Rezeki Damayanti. Penulis
menamatkan pendidikan Sekolah Dasar Al-Ittihadiyah pada Tahun 2003, Sekolah
Menengah Pertama (SMP) Negeri 4 Medan tahun 2006, Sekolah Menengah Atas
(SMA) Negeri 6 Medan tahun 2009. Pada tahun 2009 memasuki Perguruan Tinggi
Universitas Sumatera Utara fakultas MIPA jurusan Matematika pada Strata Satu
(S-I) dan lulus tahun 2013.
Pada tahun 2014, penulis melanjutkan pendidikan pada Program Studi Ma-
gister Matematika Universitas Sumatera Utara. Selama perkuliahan penulis aktif
dalam organisasi Himpunan Pengusaha Muda Indonesia Sumatera Utara(HIPMI
SUMUT), Indonesia Future Society Sumatera Utara(IFS SUMUT), Apheresis
Medan, Junior Chambers International Chapter Medan, Assosiasi Pengusaha In-
donesia Medan (APINDO Medan). Penulis juga aktif dalam bisnis wirausaha
salah satunya pendiri Rumah Pajak Medan, Bimbingan Belajar Lagrange.
v
DAFTAR ISI
Halaman
ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1. Latar Belakang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Perumusan Masalah . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3. Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4. Manfaat Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.5. Metodologi Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
BAB 3 PERSOALAN PROGRAM KUADRATIK NOL-SATU . . . . . . . . 6
3.1. Optimasi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2. Permasalahan Optimisasi Berkendala . . . . . . . . . . . . . . . . . 6
3.3. Syarat Optimalitas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.4. Program Linier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.5. Program Bilangan Bulat . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.6. Program Kuadratik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
ii
3.7. Metode Himpunan Aktif . . . . . . . . . . . . . . . . . . . . . . . . . . 18
BAB 4 TEKNIK LINIERISASI UNTUK PERSOALAN PROGAM KUADRATIKNOL-SATU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.1. Teknik Linierisasi Sherali dan Smith . . . . . . . . . . . . . . . . . . 20
4.1..1 Representasi Pendekatan Program Kuadratik nol-satu . 23
4.1..2 Contoh Persoalan dan Penyelesaian Program KuadratikNol-Satu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
BAB 5 KESIMPULAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
iii
BAB 1
PENDAHULUAN
1.1. Latar Belakang
Seiring perkembangan zaman, perkembangan ilmu pengetahuan kini meningkat
tajam. Ilmu pengetahuan telah banyak membantu manusia dalam memberikan
solusi kompleksnya permasalahan dalam kehidupan sehari-hari. Mulai dari bidang
kedokteran, ekonomi, sosial, politik, sumber daya, dan lain-lain. Permasalahan
optimasi non linier tak luput dalam memberi kontribusi dalam segala aspek.
Dalam beberapa tahun terakhir, telah banyak matematikawan mengembangkan
permasalahan non linier, salah satunya program kuadratik nol-satu.
Program kuadratik nol-satu merupakan kelas khusus dari pemrograman
non linier. Program kuadratik nol-satu ditujukan untuk meminimalkan subjek
fungsi objektif kuadratik dengan beberapa kendala kuadratik, dengan kondisi bah-
wa masing-masing variabel dibatasi nilai nol atau satu. Permasalahan program
kuadratik nol-satu sering muncul pada beberapa persoalan seperti telekomunikasi,
manufaktur, penjadwalan, dan lain-lain.
Beberapa literatur strategi linierisasi juga telah dilakukan untuk menyele-
saikan permasalahan program kuadratik nol-satu menjadi bentuk pemrograman
linier integer, mulai dari Gharibi dan Xia (2012), dan berkembang menjadi formu-
lasi yang lebih ringkas dan membutuhkan variabel biner seperti yang dilakukan
Furini dan Traversi (2013), Gharibi (2011) mengembangkan Teknik Linierisasi
Balas dan Mazzolla program kuadratik nol-satu. De Santis dan Rinaldi (2011)
mengembangkan reformulasi persoalan kuadratik nol-satu kontinu. Koncherberg-
er, dkk (2005) mengembangkan algoritma Taboo Search untuk menyelesaikan pro-
gram kuadratik biner.
Permasalahan pemrograman kuadratik nol-satu merupakan salah satu per-
masalahan optimisasi tak linear yang sangat penting, karena muncul dalam berba-
gai aspek, termasuk dalam aspek perekonomian, sains terapan, analisis porto-
folio, dan pengendalian optimal. Salah satu metode yang dapat digunakan un-
tuk menyelesaikan permasalahan pemrograman kuadratik nol-satu adalah dengan
1
2
teknik linierisasi bilinier yaitu dengan mentransformasikan persamaan kuadratik
menjadi bentuk linier. Pada penelitian ini akan dianalisis bagaimana teknik lin-
ierisasi program kuadratik nol-satu yang telah diperkenalkan oleh Sherali dan
Smith (2011) untuk menyelesaikan persoalan program kuadratik nol-satu.
Teknik linierisasi program kuadratik nol-satu lebih efektif dalam menye-
lesaikan program kuadratik yang memiliki batasan masalah variabel nol-satu.
Teknik ini merupakan teknik linieirisasi terbaru untuk persoalan kuadratik nol-
satu yang sebelumnya telah diperkenalkan oleh Sherali dan Smith (2011). Lalu
dikembangkan kembali oleh Gharibi dan Xia (2012) dengan tightness strategy.
Penelitian ini akan menunjukkan secara literatur penerapan linierisasi pro-
gram kuadratik nol-satu dan menyelesaikan beberapa contoh persoalan numerik
program kuadratik nol-satu. Berdasarkan uraian ini, peneliti tertarik untuk memil-
ih judul penelitian ”Teknik Linierisasi untuk Persoalan Program Kuadratik
Nol-Satu”.
1.2. Perumusan Masalah
Permasalahan pemrograman kuadratik merupakan salah satu permasalahan op-
timisasi tak linear yang sangat penting, karena muncul dalam berbagai aspek,
termasuk dalam aspek perekonomian, sains terapan, analisis portofolio, dan pen-
gendalian optimal. Banyak ilmuan meneliti program kuadratik, tetapi untuk ka-
sus persoalan program kuadratik nol-satu, teknik linierisasi Sherali dan Smith
lebih efektif untuk menyelesaikan proram kuadratik nol-satu. Karena solusi yang
dibatasi oleh nol-satu membuat fungsi kuadratik menjadi permasalahan yang
baru. Karena variabel berorde dua akan sama besar pengaruhnya dengan variabel
berorde satu. Andai di berikan persoalan program kuadratik yang fungsi tujuan
dan kendalanya berbentuk persamaan kuadratik dengan variabelnya di batasi oleh
nol dan satu. Dimana persamaan yang berbentuk kuadratik akan di transformasi
menjadi linier. Transformasi program kuadratik berakibat penambahan variabel
dan persamaan kedalam fungsi kendala.
1.3. Tujuan Penelitian
Tujuan dalam penelitian ini adalah menerapkan teknik linierisasi untuk
menyelesaikan persoalan kuadratik nol-satu.
3
1.4. Manfaat Penelitian
Adapun manfaat yang diperoleh pada penelitian ini antara lain sebagai berikut:
1. Akan diperoleh langkah-langkah strategi penerapan linierisasi untuk per-
soalan program kuadratik nol-satu.
2. Hasil yang akan diperoleh pada penelitian ini dapat menambah referensi
untuk menyelesaikan program kuadratik nol-satu.
1.5. Metodologi Penelitian
Penelitian yang penulis lakukan merupakan studi literatur untuk penerapan lin-
ierisasi persoalan program kuadratik nol-satu. Adapun langkah-langkah dalam
menyelesaikan penelitian ini adalah sebagai berikut:
1. Mengumpulkan berbagai literatur yang berhubungan dengan pengenaan
teknik linierisasi untuk permasalahan pemrograman kuadratik nol-satu.
2. Memaparkan berbagai teori-teori mengenai teknik linierisasi dalam per-
masalahan pemrograman kuadratik nol-satu.
3. Menganalisis penerapan linerisasi dalam menyelesaikan permasalahan pem-
rograman kuadratik nol-satu.
4. Menganalisis sifat-sifat program kuadratik nol-satu.
5. Merubah bentuk kuadratik menjadi bentuk bilinier.
6. mentransformasi persamaan fungsi kuadratik kebentuk linier.
7. Menambah variabel dan persamaan kedalam fungsi kendala akibat dari lin-
ierisasi fungsi kuadratik.
8. Mendeskripsikan formulasi permasalahan program kuadratik nol-satu ke
dalam suatu model matematika.
9. Menyelasaikan persoalan numerik dari program kuadratik nol-satu.
BAB 2
TINJAUAN PUSTAKA
Permasalahan pemrograman kuadratik nol-satu merupakan salah satu permasala-
han optimisasi tak linear yang sangat penting, karena muncul dalam berbagai as-
pek, termasuk dalam aspek perekonomian, sains terapan, dan teknik. Salah satu
metode yang dapat digunakan untuk menyelesaikan permasalahan pemrograman
kuadratik nol-satu adalah dengan melinierisasi program kuadratik. Dalam tesis
ini akan diterapkan metode himpunan aktif dalam menyelesaikan permasalahan
pemrograman kuadratik. Problema program kuadratik nol-satu adalah untuk
mencari minimum dari fungsi tujuan dan kendala yang berbentuk kuadratik nol-
satu, dimana masing-masing variabel keputusan nol atau satu.
Ada beberapa algoritma yang telah di sarankan untuk memecahkan per-
masalahan program kuadratik nol-satu. Karena NP-hardness (Nondeterminis-
tic Polynomial), di antaranya dapat diselesaikan dengan cara heuristik. Seba-
gai contoh dari beberapa pendekatan baru tersebut, Burer (2001) menyelesaikan
dengan cara heuristik yang didasarkan rank-two-relaxation untuk kelas program
kuadratik. Ia juga menyajikan langkah-langkah algoritma untuk persoalan pro-
gram kuadratik. Dan Koncherberger (2005) menerapkan pencarian algoritma
yang dibatasi bilangan biner dalam masalah program kuadratik.
Sebaliknya, penulis mempertimbangkan pendekatan optimasi yang tepat
untuk menyelesaikan permasalahan program kuadratik nol-satu. Penelitian se-
belumnya di bidang ini biasanya menyesuaikan terhadap jenis struktur kendala
yang hadir dalam masalah. Misalnya, Pardalos dan Rodgers (1990) mengem-
bangkan algoritma branch and bound untuk menyelesaikan permasalahan program
kuadratik nol-satu, sedangkan Chardaire dan Sutter (1995) memberikan algorit-
ma dekomposisi Lagrangian untuk memecahkan masalah ini. Caprara (1999)
memeriksa program kuadrat biner yang memiliki kendala single knapsack, dan
merancang algoritma branch and bound untuk solusinya nya. Loiola (2006) menye-
diakan sebuah survei terbaru dari literatur yang luas pada metode heuristik yang
tepat untuk menyelesaikan permasalahan penugasan kuadratik. Thoa (1998)
menyajikan algoritma branch and bound untuk meminimalkan fungsi kuadrat yang
4
5
memenuhi solusi integer, dengan kendala linier hypercube.
Beberapa literatur strategi linierisasi juga telah dilakukan untuk menyele-
saikan permasalahan program kuadratik nol-satu menjadi bentuk pemrograman
linier integer, mulai dari Gharibi dan Xia (2012), dan berkembang menjadi formu-
lasi yang lebih ringkas dan membutuhkan variabel biner seperti yang dilakukan
Furini dan Traversi (2013), Gharibi (2012) mengembangkan Teknik Linierisasi
Balas dan Mazzolla program kuadratik nol-satu. De Santis dan Rinaldi (2011)
mengembangkan reformulasi persoalan kuadratik nol-satu kontinu. Koncherberg-
er, dkk (2005) mengembangkan algoritma Taboo Search untuk menyelesaikan pro-
gram kuadratik biner.
Penelitian dalam makalah ini paling erat terkait dengan karya Chaovalit-
wongse (2005), yang menyediakan transformasi program kuadrat nol-satu men-
jadi program linier mixed-integer nol-satu, yang memerlukan sejumlah penam-
bahan variabel dan kendala. Penulis mendemonstrasikan bahwa dengan meny-
atakan kembali masalah sebagai persamaan program bilinear mixed-integer dan
menggunakan serangkaian transformasi variabel, demikian pula struktur tapi erat
kaitannya persamaan persoaalan program linier mixed-integer nol-satu dapat di
turunkan.
BAB 3
PERSOALAN PROGRAM KUADRATIK NOL-SATU
Sebelum mengarah pada bagaimana program kuadratik nol-satu, ada baiknya
terlebih dahulu mengetahui apa itu optimasi, program linier, program nol-satu,
dan program kuadratik.
3.1. Optimasi
Optimasi adalah sarana untuk mengekspresikan model matematika yang
bertujuan memecahkan masalah dengan cara terbaik. Untuk tujuan bisnis, hal
ini berarti memaksimalkan keuntungan dan efisiensi serta meminimalkan keru-
gian, biaya atau resiko. Hal ini juga berarti merancang sesuatu untuk memini-
malisasi bahan baku atau memaksimalisasi keuntungan. Adapun keinginan untuk
memecahkan masalah dengan model optimasi secara umum sudah digunakan pada
banyak aplikasi.
3.2. Permasalahan Optimisasi Berkendala
Menurut Sun dan Yuan (2006), bentuk umum dari permasalahan optimisasi
berkendala tak linear adalah sebagai berikut.
minimumkan f(x) (3.1)
dengan kendala ci(x) = 0, i = 1, ..., me; (3.2)
ci(x) ≥ 0, i = me + 1, ..., m; (3.3)
Di mana fungsi objektif f(x) dan fungsi-fungsi kendala ci(x), (i = 1, ..., m)
seluruhnya merupakan fungsi mulus (smooth), dan paling tidak terdapat satu
fungsi tak linear, serta me dan m merupakan bilangan bulat tak negatif dengan
0 ≤ me ≤ m. Atau dapat juga dinyatakan
E = {1, ..., me} dan I = {me + 1, ..., m}
dengan E dan I masing-masing sebagai himpunan indeks dari kendala-kendala
persamaan dan kendala-kendala pertidaksamaan. Jika m = 0, permasalahan
6
7
(3.1)-(3.3) merupakan suatu permasalahan optimisasi tak berkendala. Namun
jika me = m 6= 0, permasalahan tersebut disebut permasalahan optimisasi berk-
endala. Jika seluruh ci(x)(i = 1, ..., m) merupakan fungsi-fungsi linear, permasala-
han (3.1)-(3.3) disebut permasalahan optimisasi berkendala linear. Permasalahan
optimisasi berkendala linear dengan fungsi objektif f(x) berbentuk kuadratik dise-
but permasalahan pemrograman kuadratik.
Berikut pemaparan beberapa definisi (Sun dan Yuan, 2006).
Definisi 1 Titik x ∈ Rn dikatakan sebagai titik layak jika dan hanya jika memenuhi
(3.2)-(3.3). Himpunan yang seluruh elemennya merupakan titik-titik layak disebut
sebagai himpunan layak (feasible set).
Pada permasalahan (3.1)-(3.3), (3.2)-(3.3) merupakan syarat-syarat berkendala.
Ber dasarkan Definisi 1, suatu titik layak merupakan titik yang memenuhi seluruh
kendala. Himpunan layak X dapat dinyatakan sebagai berikut.
X = {x|ci(x) = 0, i ∈ E ; ci(x) ≥ 0, i ∈ I}
Jadi, permasalahan (3.1)-(3.3) dapat juga dinyatakan sebagai
minimumkanx∈Xf(x)
yang berarti solusi dari permasalahan optimisasi berkendala (3.1)-(3.3) hanya
merupakan pencarian nilai x pada himpunan layak X, sehingga nilai dari fungsi
objektif f(x) minimum.
Definisi 2 Jika x∗ ∈ X dan jika
f(x) ≥ f(x∗), ∀x ∈ X
maka x∗ disebut peminimum global dari permasalahan (3.1)-(3.3). Jika x∗ ∈ X
dan jika
f(x) > f(x∗), ∀x ∈ X, x 6= x∗
maka x∗ disebut peminimum global sempurnal (strict global minimizer).
8
Andaikan bahwa x∗ merupakan suatu peminimum lokal dari permasalahan (3.1)-
(3.3), jika terdapat suatu indeks i0 ∈ I = [me + 1, m] sehingga
ci0(x∗) > 0
kemudian, jika dihapus kendala ke-i0, x∗ masih tetap peminimum lokal dari per-
masalahan yang diperoleh dengan menghapus kendala ke-i0, maka dapat dikatakan
bahwa kendala ke-i0 tidak aktif pada x∗.
Perhatikan bahwa dengan menyatakan
I(x) = {i = |ci(x) = 0, i ∈ I}
Berikut diberikan definisi dari kendala aktif dan kendala tidak aktif.
Definisi 3 Untuk setiap x ∈ Rn, himpunan
A(x) = E ∪ I(x)
merupakan suatu himpunan indeks dari kendala-kendala aktif pada x, ci(x)(i ∈
A(x)) merupakan suatu kendala aktif pada x, ci(x)(i 6∈ A) merupakan suatu
kendala tidak aktif pada x.
3.3. Syarat Optimalitas
Sun dan Yuan (2006) memaparkan syarat optimalitas order pertama sebagai
berikut. Karena arah layak (feasible direction) berperan penting dalam menen-
tukan syarat optimalitas, berikut akan diberikan beberapa definisi dari arah layak.
Definisi 4 Misalkan x∗ ∈ X, 0 6= d ∈ Rn. Jika terdapat δ > 0 sehingga
x∗ + td ∈ X, ∀t ∈ [0, δ]
maka d disebut arah layak dari X pada x∗, Himpunan dari seluruh arah-arah layak
dari Xpada x∗ merupakan
FD(x∗, X) = {d|x∗ + td ∈ X, ∀t ∈ [0, δ]}
9
Definisi 5 Misalkan x∗ ∈ X dan d ∈ Rn. Jika
dT 5 ci(x∗) = 0, i ∈ E
dT 5 ci(x∗) ≥ 0, i ∈ I(x∗)
maka d disebut arah layah yang terlinearkan (linearized feasible direction) dari
X pada x∗. Himpunan dari seluruh arah-arah layak yang terlinearkan dari X
pada x∗ adalah
LFD(x∗, X) = {d | dT 5 ci(x∗) = 0, i ∈ E ; dT 5 ci(x
∗) ≥ 0, i ∈ I(x∗)}
Definisi 6 Misalkan x∗ ∈ X dan d ∈ Rn. Jika terdapat barisan (sequences) dk
(k = 1, 2, ...) dan δk > 0, (k = 1, 2, ...) sehingga x∗ + δkdk ∈ X, ∀k dan dk →
d, δk → 0, maka limit arah (limiting direction) d disebut arah layak sekuensial
(sequential feasible direction) dari X pada x∗. Himpunan dari seluruh arah
arah layak sekuensial dari X pada x∗ adalah
SFD(x∗, X) = {d | x∗ + δkdk ∈ X, ∀k ; dk → d, δk → 0}
Dari definisi tersebut, jika menetapkan xk = x∗ + δk dk, maka {xk} meru-
pakan suatu barisan titik layak (feasible point sequence) yang memenuhi :
1. xk 6= x∗, ∀k;
2. limk→∞ xk = x∗;
3. xk ∈ X untuk semua k yang cukup besar.
Jika menetapkan δk = ||xk − x∗||, maka diperoleh
dk =xk − x∗
||xk = x∗||→ d
yang berarti bahwa xk = x∗ + δkdk merupakan suatu barisan titik layak dengan
arah layak d.
Dengan maksud untuk memaparkan secara jelas syarat perlu untuk solusi
lokal, maka diperkenalkan suatu himpunan
D(x′) = D′ = {d | dT 5 f(x′) < 0} (3.1)
10
yang disebut suatu himpunan arah menurun (descent direction) pada x′. Berikut
akan dipaparkan syarat perlu yang paling dasar, yakni syarat optimalitas geometri
sebagai berikut.
Teorema 3.1 Misalkan x∗ ∈ X merupakan suatu peminimum lokal dari per-
masalahan (3.1)-(3.3). Jika f(x) dan ci(x) (i = 1, 2, ..., m) terdiferensial pada x∗,
maka
dT 5 f(x∗) ≥ 0, ∀d ∈ SFD(x∗, X) (3.2)
yang berarti
SFD(x∗, X) ∩ D(x∗) = φ (3.3)
di mana φ merupakan himpunan kosong (Sun dan Yuan, 2006).
Bukti : Untuk setiap d ∈ SFD(x∗, X) terdapat δk > 0 (k = 1, 2, ...) dan
dk (k = 1, 2, ...) sehingga x∗ + δkdk ∈ X dengan δk → 0 dan dk → d. Karena
x∗ + δkdk → x∗ dan x∗ merupakan suatu peminimum lokal, maka untuk k cukup
besar, diperoleh
f(x∗) ≤ f(x∗ + δkdk) = f(x∗) + δkdTk 5 f(x∗) + o(δk) (3.4)
yang berarti
dT 5 f(x∗) ≥ 0 (3.5)
untuk sembarang d, maka diperoleh (3.5). Selanjutnya, (3.8) juga berarti d 6∈
D(x∗). Jadi SFD(x∗, X) ∩ D(x∗) = φ.
Teorema (3.2.1) menunjukkan bahwa tidak terdapat arah layak sekuensial
pada peminimum lokal x∗.
Lemma 3.2 Suatu himpunan
S = {d | dT 5 f(x∗) < 0 ; dT 5 ci(x∗) = 0, i ∈ E ; dT 5 ci(x
∗) ≥ 0, i ∈ I} (3.6)
merupakan kosong jika dan hanya jika terdapat bilangan real λi, i ∈ E dan bilan-
gan real tak negatif λi ≥ 0, i ∈ I sehingga
5f(x∗) =∑
i∈E
λi 5 ci(x∗) +
∑
i∈I
λi 5 ci(x∗) (3.7)
11
Kenyataannya, himpunan
d = −x, 5f(x∗) = c, A =
5cTi (x∗)...
5cTm(x∗)
, λ = y
Jelas bahwa untuk menyatakan syarat optimalitas dengan memperkenalkan fungsi
Lagrange
L(x, λ) = f(x) −m
∑
i=1
λici(x) (3.8)
di mana λ = (λ1, ..., λn)T ∈ Rm merupakan vektor pengali Lagrange. Lem-
ma 3.2.2 disebut juga sebagai Lemma Farkas.
Teorema 3.3 (Karush-Kuhn-Tucker)
Misalkan x∗ merupakan suatu peminimum lokal bagi permasalahan (3.1)-
(3.3). Jika kualifikasi kendala (constraint qualification)
SFD(x∗, X) = LFD(x∗, X) (3.9)
berlaku, maka terdapat pengali-pengali Lagrange λ∗
i sehingga syarat-syarat berikut
terpenuhi pada (x∗, λ∗):
5f(x∗) −m
∑
i=1
λ∗
i 5 ci(x∗) = 0 (3.10)
ci(x∗) = 0, ∀i ∈ E, (3.11)
ci(x∗) ≥ 0, ∀i ∈ I, (3.12)
λ∗
i ≥ 0, ∀i ∈ I, (3.13)
λ∗
i ci(x∗) = 0, ∀i ∈ I (3.14)
(Sun dan Yuan, 2006)
Bukti : Karena x∗ merupakan suatu peminimum lokal, x∗ merupakan suatu
titik layak dan memenuhi syarat-syarat pada (3.14) dan (3.15). Misalkan d ∈
SFD(x∗, X); karena x∗ merupakan suatu peminimum lokal, maka berdasarkan
12
Teorema (3.2.1) bahwa dT 5 f(x∗) ≥ 0. Oleh kualifikasi kendala pada (3.12),
maka diperoleh d ∈ LFD(x∗, X). Jadi, sistem
dT 5 ci(x∗) = 0, i ∈ E, (3.15)
dT 5 ci(x∗) ≥ 0, i ∈ I(x∗), (3.16)
dT 5 f(x∗) < 0 (3.17)
tidak memiliki solusi. Oleh Lemma Farkas, kemudian diperoleh
5f(x∗) =∑
i∈E
λ∗
i 5 ci(x∗) +
∑
i∈I(x∗)
λ∗
i 5 ci(x∗) (3.18)
di mana λ∗
i ∈ R(i ∈ E) dan λ∗
i ≥ 0(i ∈ I(x∗)). Dengan menetapkan λ∗
i = 0 (i ∈
I \ I(x∗)), ini berarti bahwa
5f(x∗) =∑m
i=1 λ∗
i 5 ci(x∗)
yang merupakan (3.13). Jelas bahwa λ∗
i ≥ 0, ∀i ∈ I . Akhirnya, diperoleh bahwa
ketika i ∈ I(x∗), ci(x∗) = 0 dan λ∗
i ≥ 0, maka λ∗
i ci(x∗) = 0; ketika i ∈ I \
I(x∗), ci(x∗) > 0, namun λ∗
i = 0, maka λ∗
i ci(x∗) = 0. Jadi diperoleh bahwa
λ∗
i ci(x∗) = 0, ∀i ∈ I .
Suatu titik yang memenuhi syarat (3.13)-(3.17) disebut titik KKT. Dalam
syarat KKT, (3.13) disebut sebagai syarat titik stasioner, karena dapat dinyatakan
5xL(x∗, λ∗) = 5f(x∗) −m
∑
i=1
λ∗
i 5 ci(x∗) = 0 (3.19)
Syarat-syarat (3.14) dan (3.15) disebut sebagai syarat-syarat kelayakkan
(feasibility condition), (3.16) merupakan syarat tak negatif untuk pengali-pengali
Lagrange, dan (3.17) sebagai syarat pelengkap (complementary condition) yang
menyatakan kedua nilai, yakni λ∗
i dan ci(x∗) tidak dapat bernilai tak nol, atau
berarti juga bahwa pengali-pengali Lagrange yang bersesuaian pada kendala yang
tidak aktif bernilai nol.
Syarat pelengkap sempurna (strict complementary condition) berlaku jika
tepat salah satu dari λ∗
i dan ci(x) bernilai nol untuk setiap i ∈ I , yakni λ∗
i > 0
untuk setiap i ∈ I ∩ A(x∗).
13
Suatu kendala pertidaksamaan ci merupakan aktif kuat (strongly active)
jika i ∈ I ∩ A(x∗) dan λ∗
i > 0, yakni λ∗
i > 0 dan ci(x∗) = 0. Suatu kendala
pertidaksamaan dikatakan aktif lemah (weakly active) jika i ∈ I ∩ A(x∗) dan
λ∗
i = 0, yakni λ∗
i = ci(x∗) = 0
Syarat pada (3.12) disebut juga sebagai syarat untuk kualifikasi kendala
(constraint qualification). Kualifikasi kendala penting dalam persyaratan KKT.
3.4. Program Linier
Program linier merupakan model umum yang dapat digunakan dalam pe-
mecahan masalah pengalokasian sumber-sumber yang terbatas secara optimal.
Masalah tersebut timbul apabila seseorang diharuskan untuk memilih atau menen-
tukan tingkat setiap kegiatan yang akan dilakukannya, di mana masing-masing
kegiatan membutuhkan sumber yang sama sedangkan jumlahnya terbatas. Se-
cara sederhana, dapat diambil contoh bagian produksi suatu perusahaan yang
dihadapkan pada masalah penentuan tingkat produksi masing-masing jenis pro-
duk dengan memperhatikan batasan faktor-faktor produksi: mesin, tenaga kerja,
bahan mentah, dan sebagainya untuk memperoleh tingkat keuntungan maksimal
atau biaya yang minimal.
Pada masa modern sekarang, program linier masih menjadi pilihan dalam
upaya untuk memperoleh tingkat keuntungan maksimal atau biaya yang mini-
mal. Dalam memecahkan masalah di atas, Program linier menggunakan mod-
el matematis. Sebutan linier berarti bahwa semua fungsi matematis yang dis-
ajikan dalam model ini haruslah fungsi-fungsi linier. Dalam Program linier dike-
nal dua macam fungsi, yaitu fungsi tujuan (objective function) dan fungsi-fungsi
batasan (constraint function). Fungsi tujuan adalah fungsi yang menggambarkan
tujuan/sasaran di dalam permasalahan program linier yang berkaitan dengan pen-
gaturan secara optimal sumber daya-sumber daya, untuk memperoleh keuntungan
maksimal atau biaya minimal. Pada umumnya nilai yang akan dioptimalkan diny-
atakan sebagai Z. Fungsi batasan merupakan bentuk penyajian secara matematis
batasan-batasan kapasitas yang tersedia yang akan dialokasikan secara optimal ke
berbagai kegiatan. Model matematis dari program linier dapat dituliskan sebagai
berikut:
14
Maksimumkan Z = cT x
(minimumkan)
Kendala Ax ≤ 0
x ≥ 0
3.5. Program Bilangan Bulat
Program bilangan bulat dibutuhkan ketika keputusan harus dilakukan dalam
bentuk bilangan bulat (bukan pecahan yang sering terjadi bila kita gunakan
metode simpleks).
Model matematis dari program bilangan bulat sebenarnya sama dengan
model linear programming, dengan tambahan batasan bahwa variabelnya harus
bilangan bulat.
Terdapat 3 macam permasalahan dalam pemrograman bulat, yaitu:
1. Program bilangan bulat murni, yaitu kasus dimana semua variabel keputu-
san harus berupa bilangan bulat.
2. Program bilangan bulat campuran, yaitu kasus dimana beberapa, tapi tidak
semua, variabel keputusan harus berupa bilangan bulat
3. Program bilangan bulat biner, kasus dengan permasalahan khusus dimana
semua variabel keputusan harus bernilai 0 dan 1
Banyak aplikasi kegunaan dari program bilangan bulat, misalnya dalam
penghitungan produksi sebuah perusahaan manufaktur, dimana hasil dari perhi-
tungannya haruslah bilangan bulat, karena perusahaan tidak dapat memproduksi
produknya dalam bentuk setengah jadi.
Model program bilangan bulat dapat juga digunakan untuk memecahkan
masalah dengan jawaban ya atau tidak (yes or no decision), untuk model ini
15
variabel dibatasi menjadi dua, misal 1 dan 0, jadi keputusan ya atau tidak diwakili
oleh variabel.
Model ini seringkali disebut sebagai model program bilangan bulat nol-satu.
Model matematis persoalan program bilangan bulat nol-satu dapat di tuliskan
sebagai berikut:
Maksimumkan Z = cT x
(minimumkan)
Kendala Ax ≤ 0
x ∈ {0, 1}
3.6. Program Kuadratik
Berikut ini pemaparan mengenai pemrograman kuadratik. Program kuadratik
merupakan permasalahan optimisasi tak linear berkendala yang paling sederhana.
Pada permasalahan pemrograman kuadratik melibatkan fungsi objektif berbentuk
kuadratik dan kendala-kendala berbentuk linear. Program kuadratik mempunyai
bentuk umum sebagai berikut.
minimumkan Q(x) = xTGx + gTx (3.1)
dengan kendala aTi x = bi, i ∈ E, (3.2)
aTi x ≥ bi, i ∈ I (3.3)
Di mana G merupakan matriks simetri berukuran n× n, E dan I masing-masing
sebagai himpunan indeks dari kendala-kendala persamaan dan kendala-kendala
pertidaksamaan, E = {1, ..., me} dan I = {me + 1, ..., m}. Jika matriks Hessian
G merupakan semidefinit positif, maka (3.23)-(3.25) merupakan permasalahan
pemrograman kuadratik konveks dan solusi lokal x∗ merupakan suatu solusi glob-
al. Jika G merupakan definit positif, maka (3.23)-(3.25) merupakan pemrogra-
man kuadratik konveks sempurna (strict convex) dan x∗ merupakan solusi global
tunggal. Jika G bersifat tak definit (indefinite), maka (3.23)-(3.25) merupakan
16
permasalahan program kuadratik tak konveks di mana penyelesaian permasala-
han tersebut akan menjadi lebih sulit, karena memiliki beberapa titik stasioner
dan minimum lokal.
17
Teorema 3.2.3 (Karush-Kuhn-Tucker) dapat diterapkan pada (3.23)-(3.25)
dengan menyatakan dalam fungsi Lagrange, yakni
L(x∗, λ∗) = xTGx + xT c −∑
i∈I∪E
λi(aTi )
Sebagaimana pada Definisi 3, yakni A(x∗) mengandung indeks dari kendala-
kendala persamaan berlaku pada x∗ :
A(x∗) = {i ∈ E ∪ I |aTi x∗ = bi}
dengan mengkhususkan syarat KKT (3.2.3) untuk permasalahan ini, dapat dite-
mukan suatu solusi x∗ dari (3.23)-(3.25) yang memenuhi syarat optimalitas order
pertama, untuk beberapa pengali-pengali Lagrange λ∗
i , i ∈ A(x∗) :
g + Gx∗ =m
∑
i=1
λ∗
i ai (3.4)
aTi x∗ = bi, i ∈ E (3.5)
aTi x∗ ≥ bi, i ∈ I (3.6)
λ∗
i (aTi x∗ − bi) = 0, i ∈ I (3.7)
λ∗
i ≥ 0, i ∈ I (3.8)
Syarat-syarat (3.26)-(3.30) disebut juga sebagai syarat optimalitas untuk per-
masalahan (3.23)-(3.25).
18
3.7. Metode Himpunan Aktif
Berikut pemaparan mengenai metode himpunan aktif (Maes, 2010). Metode
himpunan aktif untuk pemrograman kuadratik merupakan suatu algoritma iteratif
yang menghasilkan rangkaian dari estimasi solusi dan menjaga kelayakkan serta
memperbaharui perkiraan himpunan optimal dari kendala-kendala aktif dan tidak
aktif. Suatu kendala pertidaksamaan ci merupakan aktif pada titik x jika berlaku
ci(x) = 0. Sedangkan pada kendala persamaan merupakan kendala aktif.
Algoritma dari metode himpunan aktif menghasilkan rangkaian titik xk yang
merupakan estimasi solusi dari (3.35)-(3.37). Subskrip k digunakan untuk meny-
atakan iterasi ke-x dari algoritma.
Pada metode himpunan aktif primal mengklasifikasikan proses pengerjaan
menjadi dua tahapan. Tahap pertama atau tahap kelayakan (feasibility phase),
merupakan suatu tahapan yang mencoba untuk menemukan suatu titik dengan
mempertahankan kelayakan (feasibility). Tahap 2 merupakan tahap optimalitas,
yakni mencoba menemukan suatu titik yang menghasilkan nilai optimal dengan
tetap mempertahankan kelayakkan.
Pada metode himpunan aktif, langkah atau pergerakkan iterasi xk diny-
atakan
xk+1 = xk + αkpk
di mana arah pencarian (search direction) merupakan suatu vektor yang meru-
pakan arah menurun (direction of descent) untuk fungsi objektif, dan skalar dari
panjang langkah (step length) αk bernilai tak negatif.
Arah pencarian p dihitung dengan menyelesaikan permasalahan berkendala
persamaan, yakni
minp f(x + p) dengan kendala Ap = 0, pN = 0 (3.1)
di mana f(x) merupakan fungsi objektif kuadratik cTx+ 12xT Hx. Kendala Ap = 0
dipilih sehingga A(x + αp) = b untuk setiap α ≥ 0. Jika dikembangkan fungsi
19
objektif dan menghapus istilah cT x dan xT Hx, permasalahan menjadi
minpgT p +
1
2pT p (3.2)
dengan kendala Ap = 0, PN = 0 (3.3)
. di mana g = c + Hx merupakan gradien dari f(x).
BAB 4
TEKNIK LINIERISASI UNTUK PERSOALAN PROGAMKUADRATIK NOL-SATU
4.1. Teknik Linierisasi Sherali dan Smith
Permasalahan pemrograman kuadratik merupakan salah satu permasalahan
optimisasi tak linear yang sangat penting, karena muncul dalam berbagai aspek,
termasuk dalam aspek perekonomian, sains terapan, komputasi, dan komunikasi.
Banyak ilmuan meneliti program kuadratik, akan tetapi, untuk kasus persoalan
program kuadratik nol-satu, teknik linierisasi Sherali dan Smith lebih efektif untuk
menyelesaikan proram kuadratik nol-satu. Karena solusi yang dibatasi oleh nol-
satu membuat fungsi kuadratik menjadi permasalahan yang baru. Berikut ini
adalah bentuk program kuadratik nol-satu
Minimumkan CTx + XT Qx (4.1)
Kendala hT x + xTGx ≥ g (4.2)
x ∈ X ⊆ {x : x adalah bilangan biner} ⊆ Bn (4.3)
Dimana Q dan G adalah matriks dimensi n × n.
Misalkan program kuadratik di transformasi menjadi perkalian antara fungsi
linier. Sehingga dapat dinyatakan dalam proses sebagai berikut
γimin/max =
min
max
{
Qix : x ∈ X̄
}
, ∀i (4.4)
Dan Qi merupkan Q baris ke i, dan X̄ adalah sebuah relaksasi dari X seperti
yang ditunjukkan pada persamaan (4.4). Andaikan didefinisikan γimin/max seba-
gai vektor yang mempunyai anggota-anggota γimin/max = 1, . . . , n dan misalkan
20
21
Γmin/max = diag{γimin/max}. Dan didefinisikan pula bahwa
λimax/min =
min
max
{
Gix : x ∈ X̄
}
, ∀i
Misalkan
λimax/min = (λi
max/min)T dan Γimin/max = diag
{
λimax/min, i = 1, . . . , n
}
Maka di reformulasikan persoalan program kuadratik adalah QP yang juga meru-
pakan bentuk fungsi Bilinear Problem (BP). Maka persoalan QP dapat dinyatakan
kedalam persoalan BP, maka diperoleh persamaan yang dapat dituliskan sebagai
berikut
BP : Minimumkan CTx + xTγ (4.5)
Kendala Qx = γ (4.6)
hTx + xTγ ≥ g (4.7)
Gx = λ (4.8)
x ∈ X (4.9)
Dan diketahui juga bahwa
γmin/max ≤ γmin, λmin ≤ λ ≤ λmax (4.10)
Selanjutnya, proses dilinierisasi kondisi xTγ dan xTλ dengan perkalian per-
samaan (4.10) dengan xi dan (1−xi), dimana persamaan (4.10)i adalah baris ke i
dari salah satu bagian vektor pertidaksamaan di persamaan (4.10), ∀i = 1, . . . , n.
Sehingga diperoleh untuk
xiγi = Si, dan xiλi = Z ′
i, ∀i = 1, . . . , n (4.11)
Misalkan e mempresentasikan sebuah vektor. Maka, BP dapat di transfor-
masikan mengikuti persamaan
22
BP : Minimumkan CTx + eTs′
Kendala Qx = γ
hT x + eT Z ′ ≥ g
Gx = λ (4.12)
γ′
minxi ≤ si ≤ γminxi dan γ′
min(1 − xi) ≤ (γi − si) ≤ γ′
max(1 − xi), ∀i
λ′
minxi ≤ zi ≤ λminxi dan λ′
min(1 − xi) ≤ (λi − zi) ≤ λ′
max(1 − xi), ∀i
Perhatikan bahwa persamaan (4.11) menjamin bahwa persamaan (4.12) berlaku
untuk x bilangan biner. Dengan memperhatikan struktur pertidaksamaan pada
persamaan (4.12) yang dapat dinyatakan sebagai berikut
si = s′i − γiminxi, ∀i
yi = γi − s′i − γimin(1 − xi), ∀i
zi = z′
i − λiminxi, ∀i (4.13)
Sehingga transformasi persamaan yang baru berdasarkan persamaan (4.13) dapat
dinyatakan sebagai berikut
BP : Minimumkan CTx + eTs + γTminx (4.14)
Kendala Qx = y + s + Γmine (4.15)
hT x + eTz + λTminx ≥ g (4.16)
Gx = λ (4.17)
0 ≤ si ≤ (γimax − γi
min)xi dan
0 ≤ yi ≤ (γimax − γi
min)(1 − xi), ∀i (4.18)
0 ≤ zi ≤ (λimax − λi
min)xi dan
λimin ≤ yi ≤ (λi
max − λimin)(1 − xi), ∀i (4.19)
x ∈ X (4.20)
Kemudian, persoalan BP ditunjukkan oleh persamaan (4.14) disederhanakan den-
gan menghapus batas atas pertidaksamaan untuk si di persamaan (4.18) dan
23
untuk (λi − zi) di persamaan (4.19). λ adalah batas bawah pertidaksamaan
λ ≥ z + λmin dimana λ = Gx di persamaan (4.17). Sehingga dapat ditulis
Gx ≥ z + λmin
Sehingga bentuk relaksasi BP ini dapat dinyatakan sebagai berikut:
BP : Minimumkan cT x + eTs + γTminx
Kendala Qx = y + s + Γmine
0 ≤ y ≤ [γmax − Γ](e − x), s ≥ 0
hT x + eTz + λTminx ≥ g
Gx ≥ z + λmin
0 ≤ z ≤ [Λmax − Λmin]x
x ∈ X (4.21)
Maka transformasi persamaan linierisasi program kuadratik nol-satu selesai.
4.1..1 Representasi Pendekatan Program Kuadratik nol-satu
Berdasarkan definisi pada subbab (4.1), maka dapat mempresentasikan hubun-
gan antara persoalan program kuadratik umumnya dengan persoalan program
kuadratik nol-satu.
Lemma 4.1 Andaikan x ∈ X ⊆ {0, 1} untuk i = 1, . . . , n.
xiQix = max
{
γiminxi, Qix + γi
maxxi − γimax
}
(4.22)
xiQix = min
{
γimaxxi, Qix + γi
minxi − γimin
}
(4.23)
memiliki hubungan yang sama antara program kuadratik nol satu dengan program
kuadratik umumnya.
Bukti Andaikan xi = 0, maka xiQix pada persamaan (4.22) jelas bernilai 0
dan sisi kanan max
{
γiminxi, Qix+γi
maxxi−γimax
}
menjadi max{0, Qix−γimax} =
24
0. Dan dalam kaasus lainnya, andaikan xi 6= 0, dengan kata lain xi = 1 maka
sisi kanan persamaan (4.22) dapat dituliskan menjadi max{γimin, Qix} = Qix
dimana sama dengan sisi kirinya yaitu Qix. Dan begitu juga dapat dilakukan
pada persaamaan (4.23)
Akibat 4.2 Andaikan x ∈ X ⊆ {0, 1}
max{γiminxi, Qix + γi
maxxi − yimax} ≤ s′i ≤ min{γi
maxxi, Qix + γiminxi − yi
min}
(4.24)
jika dan hanya jika
S ′
i = xiQix (4.25)
Bukti disubtitusikan persamaan (4.22) dan (4.23), maka dapat diperoleh dan
dinyatakan sebagai berikut
xiQx = max{γiminxi, Qix + γi
maxxi − yimax} = min{γi
maxxi, Qix + γiminxi − yi
min}
(4.26)
Hasil diatas berlaku untuk Gi dan λ yang telah dinyatakan sebelumnya.
Linierisasi berdasarkan Akibat 4.2 merupakan persoalan BP persamaan (4.21), di-
mana pertidaksamaan liner persamaan (4.21) tidak lain adalah persamaan (4.24).
Sebenarnya, tidak semua pertidaksamaan persamaan (4.24) yang diperlukan dalam
model akhir linierisasi. Untuk menunjukkan ini, pertama diperkenalkan berikut
prinsip merumuskan program kuadratik nol-satu kedalam program linear piece-
wise.
25
Proposisi 4.3 Setiap program linier convex atau piece-wise fungsi tujuan linear
piece-wise dan kendala sama dengan program linier dalam arti bahwa ada proyeksi
one-to-one antara kedua solusi layak.
Bukti Ditunjukkan bahwa
Minimumkan f(x)
Adalah sama untuk
Minimumkan tKendala t− f(x) ≥ 0
Diasumsikan bahwa fungsi tujuan merupakan linear. Himpunan kendala
merupakan convex dan dikarakteristik dengan pertidaksamaan linier piece-wise.
Sehingga persamaan tersebut berbentuk polyhedral convex, yang harus memiliki
ekspresi linear. Itu menunjukkan bahwa persamaan Proposisi 4.1 berlaku jika
variabel dibatasi oleh nol atau satu. Selanjutnya ditunjukkan adanya persamaan
program linier piece-wise convex untuk masalah minimisasi kuadratik nol-satu.
Proposisi 4.4 Untuk masalah minimisasi kuadratik nol-satu, ada persamaan pro-
gram linier piece-wise dengan fungsi tujuan dan kendala convex.
Bukti. Maksimum beberapa fungsi linear adalah convex dan minimum con-
cave. Kemudian persamaan (4.22) dan persamaan (4.4) pada Lemma 4.1 menya-
jikan masing-masing formulasi convex dan concave. Oleh karena itu, untuk setiap
diberikan persoalan minimisasi kuadratik nol-satu, maka dapat diperoleh per-
samaan program linier piece-wise convex dengan menggunakan persamaan (4.22)
dan (4.23). Perhatikan bahwa persamaan (4.22) dan persamaan (4.23) digunakan
secara bersamaan ketika memenuhi persamaan kendala.
Maka sekarang dapat ditunjukkan bahwa persamaan (4.1) - (4.3) mengikuti
formulasi persamaan
26
Minimumkan cTx +
n∑
i=1
max{γiminxi, Qix + γi
maxxi − γimax} (4.27)
Kendala hTx +
n∑
i=1
min{λimaxxi, Gix + λi
minxi − λimin} ≥ g (4.28)
x ∈ X ⊆ {0, 1} (4.29)
Linierisasi persamaan (4.27) - (4.29) dapat di tunjukkan dibawah ini. Per-
samaan (4.28) adalah setara dengan
Kendala hTx +n
∑
i=1
zi ≥ g (4.30)
zi ≤ λimaxxi (4.31)
zi ≤ Gix + λiminxi − λi
min (4.32)
Karena persamaan (4.30) - (4.32) adalah relaksasi persamaan (4.27) dan
persamaan (4.30) - (4.2.32) juga terkandung dalam persamaan (4.27). Sekarang
dapat diperoleh linierisasi untuk persamaan (4.26) (4.29), yang setara dengan
B̄P . Selanjutnya, ditunjukkan bahwa non-necessity pertidaksamaan seperti y ≥ 0
dan z ≥ 0 yang juga telah di teliti oleh Adam dan Forrester (2005,2007). Sehingga
linierisasi yang diperoleh dengan pendekatan piece-wise convex adalah tepat.
4.1..2 Contoh Persoalan dan Penyelesaian Program Kuadratik Nol-Satu
Persoalan program kuadratik nol-satu adalah persoalan optimisasi untuk
menyelesaikan persoalan yang terkendala yang memiliki kendala fungsi kuadratik
dan fungsi tujuan berbentuk kuadratik. Dengan solusi yang dibatasi nol dan satu.
27
Berikut diberikan contoh persoalan program kuadratik nol-satu
Minimumkan f(x) = x21 − 3x2
2 + x1 + 2x2
Kendala 2x21 + x2 ≤ 2
x1, x2 ∈ {0, 1}
Berdasarkan dari soal tersebut, sudah terlihat x = {(0, 0), (0, 1), (1, 0)} merupakan
titik layak bagi seluruh kendala serta merupakan solusi dari persoalan program
kuadratik nol-satu.
Persoalan kuadratik diatas dilinierisasi dengan mentranformasikan persamaan
kuadrat pada fungsi tujuan dengan menambah kendala. Sehingga persamaan pro-
gram kuadratik nol-satu menjadi
Minimumkan s1 − s2 + x1 + 2x2
Kendala z + x2 ≤ 2
x1, x2 ∈ {0, 1}
s1 = x21
s2 = 3x22
z = 2x21
Variabel kuadrat pada fungsi objektif diubah menjadi variable berorde satu.
Sehingga persamaan pada fungsi tujuan bertranformasi menjadi persamaan linier.
Dan diperlukan penambahan persamaan pada fungsi kendala. Variabel berorde
dua pada persamaan fungsi kendala juga di ubah menjadi variabel berde satu
sehingga berimplikasi langsung pada penambahan variabel pada fungsi kendala.
Berdasarkan transformasi persamaan diatas, karena nilai xi merupakan bi-
langan biner maka diperoleh rentang s1, s2, dan z sebagai berikut
28
oleh karena itu
0 ≤ s1 ≤ 1
0 ≤ s2 ≤ 3
0 ≤ z ≤ 2
s1, s2, dan z merupakan bilangan bulat.
Sehingga dapat dituliskan sebagai berikut
Minimumkan s1 − s2 + x1 + 2x2
Kendala z + x2 ≤ 2
0 ≤ s1 ≤ 1
0 ≤ s2 ≤ 3
0 ≤ z ≤ 2
x1, x2 ∈ {0, 1}
Berdasarkan kendala diatas maka kombinasi solusi layak untuk persoalan
kuadratik nol-satu diatas adalah (0, 0), (1, 0), (0, 1). Oleh karena itu pula dapat
diperoleh titik x1, x2, s1, s2, dan z sebagai berikut:
(x1, x2, s1, s2, z) f(x)(0, 0, 0, 0, 0) 0(1, 0, 1, 0, 2) 2(0, 1, 0, 3, 0) -1
Berdasarkan tabel diatas solusi minimum dari persoalan kuadratik nol-satu
adalah −1 dengan titik layak x1 = 0, x2 = 1, s1 = 0, s2 = 3, z = 0
BAB 5
KESIMPULAN
Permasalahan pemrograman kuadratik nol-satu merupakan suatu permasala-
han untuk mengoptimalkan suatu fungsi objektif dan kendala berbentuk kuadratik
dengan solusi nol atau satu. Permasalahan pemrograman kuadratik nol-satu
merupakan salah satu permasalahan optimisasi tak linear yang sangat penting,
karena muncul dalam berbagai aspek, termasuk dalam perekonomian, sains tera-
pan, dan teknik. Aplikasi-aplikasi penting dari pemrograman kuadratik termasuk
analisis portofolio, pendukung vektor mesin, analisis struktur, dan pengendalian
optimal.
Salah satu metode yang dapat digunakan untuk menyelesaikan permasala-
han pemrograman kuadratik nol satu adalah dengan melinierisasi persamaan yang
berbentuk kuadratik. Teknik linierisasi program kuadratik lebih efektif untuk
menyelesaikan persoalan program kuadratik nol-satu. Dimana nantinya diper-
lukan penambahan variabel dan kendala.
Tulisan ini menunjukkan bahwa variabel yang berorde dua bergantung pada
variabel berorde satu. Dan metode ini lebih efektif dalam menyelesaikan program
kuadratik nol-satu. Sebab nilai variabel yang berbentuk kuadratik bernilai nol
atau satu dan dipengaruhi oleh variabel berorde satu. Serta tulisan ini juga
mampu menambah referensi untuk menyelesaikan persoalan kuadratik nol-satu.
29
DAFTAR PUSTAKA
Adams W., and Forrester R. 2005. A Simple Approach for Generating Concise Lin-ear Representations of Mixed 0-1 Polynomial Programs. Operations ResearchLetters, vol. 33, no. 1, pp. 55-61.
Adams W., and Forrester R. 2007. Linear Forms of Nonlinear Expressions: NewInsights on Old Ideas. Operations Research Letters, vol. 35, no. 4, pp. 510-518.
Burer S. , Monteiro R. D. C. , dan Y. Zhang Y. 2001. Rank-two relaxation heuris-tics for MAX-CUT and other binary quadratic programs. SIAM Journal onOptimization, 12:503-521.
Caprara, A, Pisinger, D. dan Toth, P. 1999. Exact solution of the qudratic knapsackproblem. INFORMS Journal on Computing, 11(2):125-137.
Chaovalitwongse, W, Pardalos, P. M., Iasemidis, L.D., Shiau, D. S. dan SackellaresJ. C. 2005.Dynamical approaches and multi-quadratic integer programmingfor seizure prediction. Optimization Methods and Software, 20(2-3): 389-400
Chardaire, P and Dan Sutter A. 1995. A decomposition method for quadratic zero-one programming. Management Science, 41(4):704-712.
De Santis M dan Rinaldi F . 2011.Continuous Reformulations for ZeroOne Pro-gramming Problems. Springer Science and Business Media, LLC.
Furini F dan Traversi E. 2013.Extended Linear Formulation for Binary QuadraticProblems. Paris: Universite de Paris Dauphine.
Gharibi W. 2012.Improved Balas and Mazzola Linearization for Quadratic 0-1 Pro-grams with Application in a New Cutting Plane Algorithm. Dept. of ComputerScience, College of Computer Science and Information Systems, Jazan Uni-versity, Jazan 82822-6694, KSA.
Gharibi W dan Xia Y. 2012.A tight linearization strategy for zero-one quadraticprogramming problems. International Journal of Computer Science Issues:294-299
Kochenberger G, Alidaee B, dan Rego C. 2005.An unconstrained quadratic binaryprogramming approach to the vertex coloring problem. Annals of OperationsResearch, 139(1):229241.
Loiola, E.M, de Abreu, N.MM, Boaventura-Netto, P. O., Hahn, P dan QueridoT. 2006.A Survey for the quadratic assignment problem. European JournalOperation Research.
Maes, M. M. (2010). A Regularized Active-Set Method for Sparse Convex QuadraticProgramming.(PhD Dissertation). University of Standford.
30
31
Pardalos P. M. dan Rodgers G. P. 1990. Computational aspects of a branch andbound algorithm for quadratic zero-one programming. Computing, 45:131-144.
Sherali, H.D dan Smith, J.C. 2007.An Improved Linierization Strategy for Zero-One Quadratic Problems. Optimization Letters, vol.1, pp. 33-47.
Sun, W. dan Yuan Y. 2006. Optimization Theory and Methods. New York: Springer
Thoa, N. V. 1998.Global Optimization Technique for Solving the General Quadrat-ic Integer Programming Problem. Computational Optimization and Applica-tions, 10(2):149-163.