23/10/2013
Lecture 5
LINEAR PROGRAMMING
PENELITIAN OPERASIONAL I (TIN 4109)
Simplex Method:
Lecture 5 • Outline: – Simplex Method: Metode 2 Fase – Special Case dalam Simplex
Two-Phase Method • Membagi penyelesaian LP dalam 2 fase: – Fase 1: • mencari basic feasible solution awal, dengan me-nol kan artificial variable
• References: – Frederick Hillier and Gerald J. Lieberman. Introduction to Operations Research. 7th ed. The McGraw-Hill Companies, Inc, 2001. – Hamdy A. Taha. Operations Research: An Introduction. 8th Edition. Prentice-Hall, Inc, 2007.
– Fase 2: • menyelesaikan permasalahan original dengan persamaan baru berdasarkan hasil dari Fase 1
• Tetap menggunakan artificial variable
Two-Phase Method: Contoh Soal
FASE 1
Two-Phase Method: Contoh Soal 𝒙𝟏
𝒙𝟐
𝒙𝟑
𝑹𝟏
𝑹𝟐
𝒙𝟒
Solusi
𝒓
0
0
0
-1
-1
0
0
𝑹𝟏
3
1
0
1
0
0
3
𝑹𝟐
4
3
-1
0
1
0
6
𝒙𝟒
1
2
0
0
0
1
4
𝑁𝑒𝑤 𝑟 − 𝑟𝑜𝑤 = 𝑂𝑙𝑑 𝑟 − 𝑟𝑜𝑤 + (1𝑥𝑅1 − 𝑟𝑜𝑤 + 1𝑥𝑅2 − 𝑟𝑜𝑤) 𝒙𝟏
𝒙𝟐
𝒙𝟑
𝑹𝟏
𝑹𝟐
𝒙𝟒
Solusi
𝒓
7
4
-1
0
0
0
9
𝑹𝟏
3
1
0
1
0
0
3
𝑹𝟐
4
3
-1
0
1
0
6
𝒙𝟒
1
2
0
0
0
1
4
𝑯𝒂𝒔𝒊𝒍 𝑶𝒑𝒕𝒊𝒎𝒂𝒍: 𝟑 𝟔 𝒙𝟏 = , 𝒙𝟐 = ,𝒙𝟒 = 𝟏 𝟓
𝟓
1
23/10/2013
Two-Phase Method: Contoh Soal
Two-Phase Method: Contoh Soal
𝒙𝟏
𝒙𝟐
𝒙𝟑
𝑹𝟏
𝑹𝟐
𝒙𝟒
Solusi
𝒙𝟏
𝒙𝟐
𝒙𝟑
𝒙𝟒
𝒓
0
0
0
-1
-1
0
0
𝒛
-4
-1
0
0
0
𝒙𝟏
1
0
1/5
3/5
-1/5
0
3/5
𝒙𝟏
1
0
1/5
0
3/5
𝒙𝟐
0
1
-3/5
-4/5
3/5
0
6/5
𝒙𝟐
0
1
-3/5
0
6/5
𝒙𝟒
0
0
1
1
-1
1
1
𝒙𝟒
0
0
1
1
1
Solusi
𝑁𝑒𝑤 𝑟 − 𝑟𝑜𝑤 = 𝑂𝑙𝑑 𝑟 − 𝑟𝑜𝑤 + (4 ∗ 𝑥1 − 𝑟𝑜𝑤 + 1 ∗ 𝑥2 − 𝑟𝑜𝑤)
FASE 2
𝒙𝟏
𝒙𝟐
𝒙𝟑
𝒙𝟒
Solusi
𝒓
0
0
0
0
0
𝒙𝟏
1
0
1/5
0
3/5
𝒙𝟐
0
1
-3/5
0
6/5
𝒙𝟒
0
0
1
1
1
𝒙𝟏
𝒙𝟐
𝒙𝟑
𝒙𝟒
Solusi
𝒛
0
0
1/5
0
18/5
𝒙𝟏
1
0
1/5
0
3/5
𝒙𝟐
0
1
-3/5
0
6/5
𝒙𝟒
0
0
1
1
1
Two-Phase Method: Contoh Soal
Two-Phase Method
𝒙𝟏
𝒙𝟐
𝒙𝟑
𝒙𝟒
Solusi
𝒛
0
0
1/5
0
18/5
𝒙𝟏
1
0
1/5
0
3/5
𝒙𝟐
0
1
-3/5
0
6/5
𝒙𝟒
0
0
1
1
1
𝒙𝟏
𝒙𝟐
𝒙𝟑
𝒙𝟒
Solusi
𝒛
0
0
0
-1/5
17/5
𝒙𝟏
1
-1/5
0
-1/5
2/5
𝒙𝟐
0
-8/5
0
3/5
9/5
𝒙𝟑
0
0
1
1
1
𝑯𝒂𝒔𝒊𝒍 𝑶𝒑𝒕𝒊𝒎𝒂𝒍: 𝟐 𝟗 𝒙𝟏 = , 𝒙𝟐 = ,𝒛 = 𝟓
𝟓
z
z
x2 3 2 (3/5,6/5)
(0,0)
(2/5,9/5)
1
2,5
4
x1
𝟏𝟕 𝟓
Simplex Method:
Simplex Method:
Two-Phase Method
Two-Phase Method
• Langkah-langkah: – Fase 1: • Buat bentuk persamaan pada permasalahan LP dengan menambah artificial variable untuk semua kontrain atau kendala yang ada. • Bentuk fungsi tujuan menjadi: 𝑴𝒊𝒏𝒊𝒎𝒊𝒛𝒆 𝒓 = 𝑹𝒊 . Berlaku untuk fungsi tujuan maksimasi ataupun minimasi. • Jika hasil penjumlahan artificial variable bernilai positif, artinya permasalahan LP tidak memiliki feasibel solution. • Optimal solution diperoleh pada saat 𝒓 = 𝟎. • Hasil dari solusi optimal Fase 1 menjadi Basic Feasible real problem yang diselesaikan pada Fase 2.
• Langkah-langkah: – Fase 2: • Bertujuan untuk memperoleh optimal solution real problem. • Drop artificial variable (telah bernilai nol pada Fase 1). • Basic Feasible dari Fase 1 diselesaikan dengan metode simplex.
2
23/10/2013
Two-Phase Method: Catatan!!!
Latihan Soal
• Menghilangkan artificial variable pada Fase 2 hanya bisa dilakukan jika artificial variable menjadi non basic variable. • Jika tidak (salah satu atau lebih dari artificial variable masih menjadi basic variable dengan nilai 0), lakukan langkah berikut: – Langkah 1: Pilih nol artificial variable tersebut sebagai leaving variable, dan menunjuk baris tersebut sebagai baris pivot. Pilih nonbasic (nonartificial) variable dengan nonzero (+ / -) koefisien sebagai entering variable. Lakukan iterasi simplex. – Langkah 2: Hilangkan kolom artificial variable yang baru dari tabel. Jika semua nol artificial variable dihilangkan, lanjutkan ke Fase 2. Jika belum, kembali ke Langkah 1.
• • • •
1.
s.t.
2.
s.t.
Simplex Method:
Simplex Method:
Special Cases
Special Cases – Degeneracy • Degeneracy
Degeneracy Alternative optima Unbounded solutions Nonexisting (or infeasible) solutions
– Terjadi cycling dalam iterasi metode simplex – Sedikitnya terdapat satu redundant constraint – Contoh: Maximize z = 3x1 + 9x2 Subject to x1 + 4x2 8 x1 + 2x2 1
x1 , x2 0
Simplex Method: Special Cases – Degeneracy z
x1
x2
x3
x4
Solusi
z
1
-3
-9
0
0
0
x3
0
1
4
1
0
8
x4
0
1
2
0
1
4
z
1
-3/4
0
9/4
0
18
x2
0
¼
1
¼
0
2
x4
0
½
0
-½
2
0
1
0
0
3/2
3/2
18
x2
0
0
1
½
-½
2
x1
0
1
0
-1
2
0
Simplex Method: Special Cases – Degeneracy x2
z 3 x1 9 x 2
x1 4 x2 8 redundant
x1 2 x 2 4
x1
3
23/10/2013
Simplex Method:
Simplex Method:
Special Cases – Alternative optima
Special Cases – Alternative optima
• Alternative optima – Fungsi tujuan paralel dengan salah satu konstrain yang paling menentukan solusi – Terdapat lebih dari satu solusi optimal – Contoh Maximize z = 2x1 + 4x2
z
x1
x2
x3
x4
Solusi
z
1
-2
-4
0
0
0
x3
0
1
2
1
0
5
x4
0
1
1
0
1
4
z
1
0
0
2
0
10
x2
0
½
1
½
0
5/2
x4
0
½
0
-½
1
3/2
Subject to x1 + 2x2 5 x1 + x2 4 x1 , x2 0
1
0
0
2
0
10
x2
0
0
1
1
-1
1
x1
0
1
0
-1
2
3
Simplex Method:
Simplex Method:
Special Cases - Alternative optima
Special Cases – Unbounded solution • Unbounded solution
𝑥2
– Tidak ada variabel pembatas – Hasil fungsi tujuan bertambah (maksimasi) atau berkurang (minimasi) tanpa batas – Contoh
B
Maximize z = 2x1 + x2
Optimal basic solution
Subject to
C
x1 - x2 10 A
𝑥2
𝑥1
D
2x1
40
x1 , x2 0
Simplex Method:
Simplex Method:
Special Cases – Unbounded solution
Special Cases – Infeasible solution
z
x1
x2
x3
x4
z
1
-2
-1
0
0
0
x3
0
1
-1
1
0
10
x4
0
2
0
0
1
40
2x1 40
Solusi
• Infeasible solution – Inconsistent constraints – Tidak terjadi bila semua kontrain bertanda – Contoh Maximize z = 3x1 + 2x2 Subject to 2x1 + x2 2
𝑥1
3x1 + 4x2 12 x1 , x2 0
4
23/10/2013
Simplex Method:
Simplex Method:
Special Cases – Infeasible solution
Special Cases – Infeasible solution
z
x1
x2
x4
x3
R
Solusi
z
x1
x2
x4
x3
R
Solusi
z
1
-303
-402
100
0
0
-1200
z
1
-303
-402
100
0
0
-1200
x3
0
2
1
0
1
0
2
x3
0
2
1
0
1
0
2
R
0
3
4
-1
0
1
12
R
0
3
4
-1
0
1
12
z
1
501
0
100
402
0
-396
z
1
501
0
100
402
0
-396
x2
0
2
1
0
3
0
2
x2
0
2
1
0
3
0
2
R
0
-5
0
-1
-4
1
4
R
0
-5
0
-1
-4
1
4
Simplex Method: Special Cases – Infeasible solution
TUGAS •
Tugas: – Tentukan satu studi kasus yang dapat diselesaikan dengan menggunakan ILP. – Selesaikan permasalahan tersebut dengan menggunakan software lindo/lingo, excel, dan matlab
•
Dasar Penilaian: – – – –
•
Kompleksitas kasus Ketepatan langkah Hasil akhir Pemahaman (dinilai pada saat presentasi)
Ketentuan: – Tugas kelompok. Anggota maksimal 3 orang. – Obyek kasus dan nilai parameter ataupun koefisien tidak boleh sama antar kelompok. – Format laporan: PPT (kasus, langkah-langkah, kode (bahasa program yang digunakan) – Pengumpulan tugas: email ke
[email protected] – Deadline: 31 oktober 2013, jam 00.00 am
Lecture 6 – QUIZ 1 • Materi: – Linier Programming: • Metode grafis • Metode simplex: – – – –
Konsep dasar M-Method Two-phase Method Kasus khusus
5
