2014/9/17

1

PROGRAM LINIER / PROGRAM LINIER / LINEAR PROGRAMMING LINEAR PROGRAMMING

AudityaAuditya PurwandiniPurwandini SutartoSutarto, PhD, PhD

1

2

Program Linier

Solusi GrafisMetode

SimpleksDualitas danSensitivitas

Tipe-tipeKhusus

Integer Programming

2014/9/17

2

Pendahuluan

Masalah Program Linier

Asumsi dalam Porgram Linier

Formulasi Masalah

Contoh Masalah Maksimasi Sederhana

Prosedur Penyelesaian Secara Grafis

Titik Ekstrim dan Solusi Optimum

Solusi Komputasi

Masalah Minimasi Sederhana

Kasus-kasus Khusus

PROGRAM LINIER PROGRAM LINIER –– SOLUSI SOLUSI GRAFISGRAFIS

PendahuluanPendahuluan

ProgramaPrograma Linier Linier tidaktidak adaada hubungannyahubungannya dengandenganpemrogramanpemrograman komputerkomputer..

KataKata “program/“program/programmingprogramming” ” bermaknabermakna memilihmemilihserangkaianserangkaian tindakantindakan

Program linier Program linier melibatkanmelibatkan pemilihanpemilihan serangkaianserangkaiantindakantindakan ketikaketika model model matematisnyamatematisnya hanyahanya berupaberupafungsifungsi linierlinier

PelopornyaPelopornya adalahadalah George B. George B. DantzigDantzig seorangseorang ilmuwanilmuwanahliahli teknikteknik matematikamatematika yang yang dipekerjakandipekerjakan militermiliter AS AS selamaselama PD II PD II untukuntuk memecahkanmemecahkan masalahmasalah logistiklogistikmilitermiliter

4

2014/9/17

3

5

MasalahMasalah ProgramaPrograma LinierLinier BertujuanBertujuan untukuntuk mmaksimasimmaksimasi atauatau minimasiminimasi

SemuaSemua permasalahanpermasalahan memilikimemiliki konstrainkonstrain//kendalakendala yang yang membatasimembatasi seberapaseberapa banyakbanyak fungsifungsi obyektifobyektif dapatdapatdicapaidicapai

SolusiSolusi LAYAK (LAYAK (feasible solution) feasible solution) memenuhimemenuhi semuasemuakonstrainkonstrain masalahmasalah..

SolusiSolusi OPTIMUM OPTIMUM adalahadalah solusisolusi layaklayak yang yang menghasilkanmenghasilkan nilainilai fungsifungsi obyektifobyektif maksimasimaksimasi terbesarterbesar((atauatau minmasiminmasi terkecilterkecil))

MetodeMetode solusisolusi grafisgrafis dapatdapat digunakandigunakan untukuntukmemecahkanmemecahkan masalahmasalah program linier program linier dengandengan duaduavariabelvariabel..

6

Asumsi dalam Model Program Linier

LinierityLinierity & & AdditivityAdditivity

FungsiFungsi tujuantujuan dandan semuasemua konstrainkonstrain harusharus linier. linier. SuatuSuatu kendalakendala yang yang melibatkanmelibatkan nn variabelvariabel akanakanmenghasilkanmenghasilkan hyperplanehyperplane ((bentukbentuk geometrisgeometris yang rata) yang rata) dalamdalam ruangruang berdimensiberdimensi nn

JumlahJumlah variabelvariabel keputusankeputusan dandan jumlahjumlah penggunaanpenggunaansumberdayasumberdaya bersifatbersifat aditifaditif

DivisibilityDivisibility

NilaiNilai solusisolusi yang yang diperolehdiperoleh tidaktidak harusharus berupaberupabilanganbilangan bulatbulat, , dapatdapat berupaberupa pecahanpecahan. . JikaJika nilainilai bulatbulatmutlakmutlak diperlukandiperlukan integer programminginteger programming

2014/9/17

4

AsumsiAsumsi

DeterministikDeterministik

Parameter model Parameter model diasumsikandiasumsikan diketahuidiketahui konstankonstan, , deterministikdeterministik. .

DalamDalam kenyataannyakenyataannya jarangjarang bersifatbersifat deterministikdeterministik analisisanalisis sensitivitassensitivitas

7

FormulasiFormulasi MasalahMasalah

FormulasiFormulasi MasalahMasalah atauatau Modeling Modeling adalahadalah prosesprosesmenerjemahkanmenerjemahkan masalahmasalah dalamdalam pernyataanpernyataanverbal verbal keke dalamdalam pernyataanpernyataan//bentukbentuk matematismatematis

FormulasiFormulasi model model merupakanmerupakan suatusuatu seniseni yang yang hanyahanya dapatdapat dikuasaidikuasai dengandengan banyakbanyak praktekpraktek dandanpengalamanpengalaman

SetiapSetiap masalahmasalah LP LP memilikimemiliki beberapabeberapa sifatsifat//fiturfiturunikunik, , tetapitetapi sebagiansebagian besarbesar masalahmasalah jugajuga memilikimemilikisifatsifat--sifatsifat yang yang umumumum ((miripmirip))

8

2014/9/17

5

9

FormulasiFormulasi ModelModel

MemahamiMemahami problem problem secarasecara keseluruhankeseluruhan..

MendeskripsikanMendeskripsikan tujuantujuan..

MendeskripsikanMendeskripsikan variabelvariabel..

MendefinisikanMendefinisikan variabelvariabel keputusankeputusan

MenulisMenulis fungsifungsi obyektifobyektif dalamdalam terminilogiterminilogivariabelvariabel keputusankeputusan..

MenulisMenulis konstrainkonstrain dalamdalam terminologiterminologi variabelvariabelkeputusankeputusan..

ContohContoh 1: 1: MasalahMasalah MaksimasiMaksimasiSederhanaSederhana

10

Max 5Max 5xx11 + 7+ 7xx22

s.t. s.t. xx11 << 66

22xx11 + 3+ 3xx22 << 1919

xx11 + + xx22 << 88

xx11 >> 0 and 0 and xx22 >> 00

FungsiFungsiObyektifObyektif

KonstrainKonstrain““RegularRegular””

KonstrainKonstrain non non negatifnegatif

2014/9/17

6

ContohContoh 11: : SolusiSolusi GrafisGrafis

11

GrafikGrafik untukuntuk KendalaKendala PertamaPertamaxx22

xx11

xx11 = 6= 6

(6, 0)(6, 0)

88

77

66

55

44

33

22

11

1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 109 10

Area Area iniinimengandungmengandung

semuasemua titiktitik layaklayakuntukuntuk kendalakendala

pertamapertama

12

GrafikGrafik untukuntuk konstrainkonstrain keduakedua

22xx11 + 3+ 3xx22 = 19 = 19

xx22

xx11

(0, 6(0, 6 1/31/3))

(9(9 1/21/2, , 0)0)

88

77

66

55

44

33

22

11

1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 109 10

Area Area iniinimengandungmengandungsemuasemua titiktitiklayaklayak untukuntukkendalakendala keduakedua

2014/9/17

7

13

GrafikGrafik untukuntuk KonstrainKonstrain KetigaKetigaxx22

xx11

xx11 + + xx22 = 8= 8

((00, , 88))

(8, 0)(8, 0)

88

77

66

55

44

33

22

11

1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 109 10

Area Area iniinimengandungmengandungsemuasemua titiktitik layaklayakuntukuntuk konstrainkonstrainketigaketiga

14

xx11

xx22

88

77

66

55

44

33

22

11

1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 109 10

22xx11 + 3+ 3xx22 = 19= 19

xx11 + + xx22 = 8= 8

xx11 = 6= 6

KombinasiKombinasi GrafikGrafik konstrainkonstrain yang yang menunjukkanmenunjukkanarea area solusisolusi yang yang layaklayak

Area Area LayakLayak

2014/9/17

8

15

GarisGaris FungsiFungsi ObyektifObyektif

xx11

xx22

(7, 0)(7, 0)

(0, 5)(0, 5)

FungsiFungsi ObyektifObyektif55xx11 + + 7x7x2 2 = 35= 35FungsiFungsi ObyektifObyektif55xx11 + + 7x7x2 2 = 35= 35

88

77

66

55

44

33

22

11

1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 109 10

16

GarisGaris terpilihterpilih untukuntuk FungsiFungsi ObyektifObyektif

xx11

xx22

55xx11 + + 7x7x2 2 = 35= 3555xx11 + + 7x7x2 2 = 35= 35

88

77

66

55

44

33

22

11

1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 109 10

5x1 + 7x2 = 425x1 + 7x2 = 42

5x1 + 7x2 = 395x1 + 7x2 = 39

2014/9/17

9

17

SolusiSolusi OptimumOptimum

xx11

xx22 GarisGaris fungsifungsi ObyektifObyektif MaksimumMaksimum5x1 + 7x2 = 46GarisGaris fungsifungsi ObyektifObyektif MaksimumMaksimum5x1 + 7x2 = 46

SolusiSolusi OptimumOptimum((x1 = 5, x2 = 3))SolusiSolusi OptimumOptimum((x1 = 5, x2 = 3))

88

77

66

55

44

33

22

11

1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 109 10

18

TitikTitik EkstrimEkstrim dandan SolusiSolusiOptimumOptimum

TitikTitik pojokpojok padapada daerahdaerah layaklayak disebutdisebut titiktitikekstrimekstrim

SolusiSolusi optimum optimum suatusuatu masalahmasalah LP LP dapatdapatditemukanditemukan didi salahsalah satusatu titiktitik ekstrimekstrim daridari daerahdaerahlayaklayak..

KetikaKetika mencarimencari solusisolusi optimal optimal tidaktidak perluperlu tidaktidakperluperlu mengevaluasimengevaluasi semuasemua titiktitik didi daerahdaerah solusisolusilayaklayak melainkanmelainkan cukupcukup mempertimbangkanmempertimbangkan titiktitik--titiktitik kritiskritis sajasaja

2014/9/17

10

19

ContohContoh : : TitikTitik KritisKritis

xx11

Daerah Daerah LayakLayak

11 22

33

44

55

xx22

88

77

66

55

44

33

22

11

1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 109 10

(0, 6 (0, 6 1/31/3))

(5, 3)(5, 3)

(0, 0)(0, 0)

(6, 2)(6, 2)

(6, 0)(6, 0)

20

SolusiSolusi MenggunakanMenggunakanKomputerKomputer

MasalahMasalah LP LP dengandengan 100 100 variabelvariabel dandan 1000 1000 konstrainkonstrain sekarangsekarang dapatdapat dipecahkandipecahkanmenggunakanmenggunakan bantuanbantuan program program komputerkomputer

Microsoft Excel.Microsoft Excel.

CPLEX, LINGO, MOSEK, XpressCPLEX, LINGO, MOSEK, Xpress--MP, and MP, and Premium Solver for Excel.Premium Solver for Excel.

The Management ScientistThe Management Scientist

2014/9/17

11

ContohContoh 2: 2: MasalahMasalah MinimasiMinimasiSederhanaSederhana

FormulasiFormulasi LPLP

21

Min 5Min 5xx11 + 2+ 2xx22

s.t. 2s.t. 2xx11 + 5+ 5xx22 >> 1010

44xx11 -- xx22 >> 1212

xx11 + + xx22 >> 44

xx11, , xx22 >> 00

GrafikGrafik untukuntuk KonstrainKonstrain KonstrainKonstrain 11: : JikaJika xx11 = 0, = 0, makamaka xx22 = 2; = 2; jikajika xx22 = 0, = 0,

makamaka xx11 = 5. = 5. HubungkanHubungkan (5,0) and (0,2). (5,0) and (0,2). TandaTanda">" side is ">" side is menyatakanmenyatakan daerahdaerah diatasdiatas garisgaris tersebuttersebut..

KonstrainKonstrain 22: : JikaJika xx22 = 0, = 0, makamaka xx11 = 3. = 3. NamunNamundengandengan men set men set xx11 = 0 = 0 makamaka xx22 = = --12, (12, (diluardiluar grafisgrafis). ). Set Set lahlah xx11 lebihlebih besarbesar daridari 3 3 3 3 lalulalu carilahcarilah xx22: : misalmisal xx11

= 5, = 5, makamaka xx22 = 8. = 8. hubungkanhubungkan (3,0) (3,0) dandan (5,8). (5,8). TandaTanda">“ ">“ didi sisisisi kana.kana.

KonstrainKonstrain 33: : JikaJika xx11 = 0, = 0, makamaka xx22 = 4; = 4; jikajika xx22 = 0, = 0, makamaka xx11 = 4. = 4. hubungkanhubungkan (4,0) (4,0) dandan (0,4). (0,4). TandaTanda

">" ">" beradaberada diatasdiatas garisgaris

22

2014/9/17

12

23

GrafikGrafik KonstrainKonstrainxx22xx22

44xx11 -- xx22 >> 121244xx11 -- xx22 >> 1212

22xx11 + 5+ 5xx22 >> 101022xx11 + 5+ 5xx22 >> 1010

xx11xx11

Area Area LayakLayak

1 1 22 3 3 44 5 5 6 6

66

55

44

33

22

11

xx11 + + xx22 >> 44xx11 + + xx22 >> 44

24

BuatlahBuatlah GrafikGrafik untukuntuk fungsifungsi ObyektifObyektif

TetapkanTetapkan nilainilai fungsifungsi obyektifobyektif samasama dengandengan suatusuatukonstantakonstanta sembarangsembarang ((misalmisal 2020) ) dandan gambarlahgambarlah! ! UntukUntuk55xx11 + + 22xx22 = = 2020, , jikajika xx11 = = 00, , makamaka xx22 = = 1010; ; jikajika xx22= = 00, , makamaka xx11 = = 44. . HubungkanHubungkan ((44,,00) ) dandan ((00,,1010).).

PindahkanPindahkan GarisGaris FungsiFungsi obyektifobyektif menujumenuju optimalitasoptimalitas

PindahkanPindahkan keke araharah dimanadimana nilainyanilainya terusterus menurunmenurun((karenakarena tujuantujuan minimasiminimasi) ) sampaisampai menyentuhmenyentuh titiktitikterakhirterakhir daridari daerahdaerah layaklayak yang yang ditentukanditentukan oleholeh duaduakonstrainkonstrain terakhirterakhir

2014/9/17

13

25

xx22xx22

44xx11 -- xx22 >> 121244xx11 -- xx22 >> 1212

22xx11 + 5+ 5xx22 >> 101022xx11 + 5+ 5xx22 >> 1010

xx11xx111 1 22 3 3 44 5 5 6 6

66

55

44

33

22

11

xx11 + + xx22 >> 44xx11 + + xx22 >> 44

GrafikGrafik FungsiFungsi ObyektifObyektif

Min 5x1 + 2x2Min 5x1 + 2x2

26

CarilahCarilah titiktitik ekstrimekstrim padapada pertemuanpertemuan antaraantara duadua konstrainkonstrain

44xx11 -- xx22 = 12= 12

xx11+ + xx22 = 4= 4

sehinggasehingga diperolehdiperoleh

55xx11 = 16 = 16 atauatau xx11 = 16/5 = 16/5 dandan xx22 = 4/5= 4/5

MasukkanMasukkan nilainilai tersebuttersebut keke dalamdalam fungsifungsi obyektifobyektif

55xx11 + 2+ 2xx22 = 5(16/5) + 2(4/5) = 88/5= 5(16/5) + 2(4/5) = 88/5

2014/9/17

14

27

xx22xx22

44xx11 -- xx22 >> 121244xx11 -- xx22 >> 1212

22xx11 + 5+ 5xx22 >> 101022xx11 + 5+ 5xx22 >> 1010

xx11xx111 1 22 3 3 44 5 5 6 6

66

55

44

33

22

11

xx11 + + xx22 >> 44xx11 + + xx22 >> 44

SolusiSolusi OptimumOptimum

SolusiSolusi Optimal:Optimal:x1 = 16/5, x2 = 4/5,

5x1 + 2x2 = 17.6

SolusiSolusi Optimal:Optimal:x1 = 16/5, x2 = 4/5,

5x1 + 2x2 = 17.6

RingkasanRingkasan ProsedurProsedur PenyelesaianPenyelesaianGrafisGrafis Program LinierProgram Linier

BuatlahBuatlah grafikgrafik yang yang mengandungmengandung solusisolusi yang yang layaklayak untukuntuksetiapsetiap konstrainkonstrain

TentukanTentukan area yang area yang layaklayak yang yang memenuhimemenuhi semuasemua kendalakendalasecarasecara simultansimultan..

GambarkanGambarkan garisgaris fungsifungsi obyektifobyektif

PindahkanPindahkan garisgaris--garisgaris fungsifungsi obyektifobyektif yang yang paralelparalel mengikutimengikutinilainilai fungsifungsi obyektifobyektif yang yang membesarmembesar ((atauatau mengecilmengecil padapadaminimasiminimasi) ) tanpatanpa melanggarmelanggar area area solusisolusi yang yang layaklayak..

SmuaSmua solusisolusi yang yang layaklayak padapada garisgaris fungsifungsi obyektifobyektif dengandengan nilainilaiterbesarterbesar ((atauatau terkecilterkecil padapada minimasiminimasi) ) adalahadalah solusisolusi optimunoptimun

28

2014/9/17

15

KasusKasus--kasuskasus KhususKhusus MasalahMasalah TidakTidak LayakLayak ((UnfeasibleUnfeasible))

Tidak ada solusi atas masalah LP yang mampu memenuhi semua kendala, termasukkondisi non negatif

Secara grafis, daerah layak ini tidak ada

Penyebabnya:

Kesalahan dalam formulasi model

Ekspektasi pihak manajemen terlalu tinggi,

Terlalu banyak batasan pada masalah tersebut(over-constrained)

29

30

ContohContoh 1: 1: MasalahMasalah TidakTidak LayakLayak

TinjauTinjau MasalahMasalah LP LP berikutberikut

Max 2Max 2xx11 + 6+ 6xx22

s.t. 4s.t. 4xx11 + 3+ 3xx22 << 1212

22xx11 + + xx22 >> 88

xx11, , xx22 >> 00

2014/9/17

16

31

Tidak ada titik yang memenuhi kedua konstrain, sehingga tidak ditemukan daerah yang layak (dantidak ada solusi yang layak)

xx22

xx11

44xx11 + 3+ 3xx22 << 1212

22xx11 + + xx22 >> 88

2 2 4 4 6 6 8 8 1010

44

88

22

66

1010

KasusKasus--kasuskasus KhususKhusus

Masalah Tak Terbatas (Unbounded)

Solusi untuk suatu masalah maksimasi LP dapat menjadi tidak terbatas jika nilai solusitersebut dapat dibuat besar tak terbatastanpa melanggar konstrain manapun

Dalam kasus nyata, hal ini dapat terjadikarena formulasi yang tidak tepat(umumnya ada konstrain yang tidakdimasukkan/diabaikan)

32

2014/9/17

17

33

TinjauTinjau MasalahMasalah LP LP berikutberikut

Max 4Max 4xx11 + 5+ 5xx22

s.t. s.t. xx11 + + xx22 >> 55

33xx11 + + xx22 >> 88

xx11, , xx22 >> 00

ContohContoh 2: 2: SolusiSolusi TakTak TerbatasTerbatas

Area yang Area yang layaklayak tidaktidak terbatasterbatas dandan garisgaris fungsifungsiobyektifobyektif dapatdapat dipindahkandipindahkan keluarkeluar daridari asalnyaasalnyatanpatanpa terbatasterbatas sehinggasehingga nilainilai fungsifungsi obyektifobyektif naiknaiktaktak terbatasterbatas

34

xx22

xx11

33xx11 + + xx22 >> 88

xx11 + + xx22 >> 55

66

88

1010

2 2 4 4 6 6 8 8 1010

44

22