11/5/2008
LINEAR PROGRAMMING-1 DR.MOHAMMAD ABDUL MUKHYI, SE., MM
Rabu, 05 Nopember 2008
METODE KUANTITATIF
1
Perumusan PL Ada tiga unsur dasar dari PL, ialah: 1. Fungsi Tujuan 2. Fungsi Pembatas (set ketidak samaan/pembatas strukturis) 3. Pembatasan selalu positip.
Rabu, 05 Nopember 2008
METODE KUANTITATIF
2
1
11/5/2008
Bentuk umum persoalan PL Cari : x1 , x2 , x3 , …………… , xn. Fungsi Tujuan : Z = c1x1 + c2x2 + c3x3 + …… + cnxn optimum (max/min) (srs) Fungsi Kendala : a11x1 + a12x2 + a13x3 + …………… + a1nxn >< h1. (F. Pembatas) a21x1 + a22x2 + a23x3 + …………… + a2nxn >< h2. (dp) a31x1 + a32x2 + a33x3 + …………… + a3nxn >< h3. ↓
…. ↓
…. ↓
...…………
↓
.. ↓
am1x1 + am2x2 + am3x3 + ….……… + amnxn >< hm. xj > 0
j = 1 , 2, 3 ………n nonnegativity consraint
srs : sedemikian rupa sehingga dp : dengan pembatas Rabu, 05 Nopember 2008
METODE KUANTITATIF
3
ada n macam barang yg akan diproduksi masing-masing sebesar x1,x2, … , xn xj : banyaknya barang yang diproduksi ke j , j = 1, 2, 3, …. , n cj : harga per satuan barang ke j , j = 1, 2, 3, ……………. , n ada m macam bahan mentah, masing-masing tersedia h1, h2, h3, .., hm hi : banyaknya bahan mentah ke i , i = 1, 2, 3, ……………. , m aij : banyaknya bahan mentah ke i yg digunakan utk memproduksi 1 satuan barang ke j xj > 0 , j = 1, 2,…,n ; cj tidak boleh negatif, paling kecil 0 (nonnegativity consraint) Maksimum dp < h1 artinya, pemakaian input tidak boleh melebihi h1 Minimum dp > h1 artinya, pemakaian input paling tidak dipenuhi h1
Rabu, 05 Nopember 2008
METODE KUANTITATIF
4
2
11/5/2008
Langkah-langkah dan teknik pemecahan Dasar dari pemecahan PL adalah suatu tindakan yang berulang (Inter-active search) dengan sekelompok cara untuk mencapai suatu hasil optimal. Tidakan dilakukan dengan cara sistimatis. Selanjutnya langkah-langkah dari tindakan berulang adalah sebagai: 1. Tentukan kemungkinan-kemungkinan kombinasi yang baik dari sumber daya alam yang terbatas atau fasilitas yang tersedia, yang disebut sebagai initial feasible solution. 2. Selesaikan persamaan pembatasan struktural untuk mendapatkan titik-titik ekstreem (disebut sebagai ‘basic feasible solution’). 3. Tentukanlah nilai dari titik-titik ekstreem yang akan merupakan nilai-nilai pilihan, yang telah disesuaikan dengan nilai tujuan dari permasalahan. 4. Ulanglah langkah 3 hingga tercapai tujuan optimal (ha-nya satu yang bernilai tertinggi atau terendah). Rabu, 05 Nopember 2008
METODE KUANTITATIF
5
Ada 3 (tiga) cara pemecahan PL 1. Cara dengan menggunakan grafik 2. Cara dengan substitusi (cara matematik/Aljabar) 3. Cara simplex
Rabu, 05 Nopember 2008
METODE KUANTITATIF
6
3
11/5/2008
Tujuan Model LP Dengan Grafik Mengetahui hubungan-hubungan kendala dalam model LP dan mengetahui konsep-konsep pemecahan LP yang akan digunakan dalam pembahasan analisis sensitivitas dangan program komputer.
Rabu, 05 Nopember 2008
METODE KUANTITATIF
7
Kendala Aktif dan Tak Aktif: Kendala aktif adalah kendala bila dievaluasi pada tingkat solusi optimal, nilai disebelah kiri sama dengan nilai disebelah kanan. Kendala tak aktif adalah kendala jika dievaluasi pada tingkat optimal, nilai disebelah kiri tidak sama dengan nilai disebelah kanan Kendala Berlebihan (Redundansi): Jika suatu kendala tidak menentukan bagian dari batas daerah yang feasibel.
Rabu, 05 Nopember 2008
METODE KUANTITATIF
8
4
11/5/2008
General Form of an Optimization Problem MAX (or MIN): f0(X1, X2, …, Xn) Subject to: f1(X1, X2, …, Xn)<=b1 : fk(X1, X2, …, Xn)>=bk : fm(X1, X2, …, Xn)=bm Note: If all the functions in an optimization are linear, the problem is a Linear Programming (LP) problem Rabu, 05 Nopember 2008
METODE KUANTITATIF
9
Linear Programming (LP) Problems MAX (or MIN): c1X1 + c2X2 + … + cnXn Subject to:
Rabu, 05 Nopember 2008
a11X1 + a12X2 + … + a1nXn <= b1 : ak1X1 + ak2X2 + … + aknXn >=bk : am1X1 + am2X2 + … + amnXn = bm
METODE KUANTITATIF
10
5
11/5/2008
An Example LP Problem Blue Ridge Hot Tubs produces two types of hot tubs: Aqua-Spas & Hydro-Luxes. Pumps Labor Tubing Unit Profit
Aqua-Spa 1 9 hours 12 feet $350
Hydro-Lux 1 6 hours 16 feet $300
There are 200 pumps, 1566 hours of labor, and 2880 feet of tubing available. Rabu, 05 Nopember 2008
METODE KUANTITATIF
11
5 Steps In Formulating LP Models: 1. Understand the problem. 2. Identify the decision variables. X1=number of Aqua-Spas to produce X2=number of Hydro-Luxes to produce
3. State the objective function as a linear combination of the decision variables. MAX: 350X1 + 300X2
Rabu, 05 Nopember 2008
METODE KUANTITATIF
12
6
11/5/2008
5 Steps In Formulating LP Models (continued)
4. State the constraints as linear combinations of the decision variables. 1X1 + 1X2 <= 200 } pumps 9X1 + 6X2 <= 1566 } labor 12X1 + 16X2 <= 2880 } tubing 5. Identify any upper or lower bounds on the decision variables. X1 >= 0 X2 >= 0 Rabu, 05 Nopember 2008
METODE KUANTITATIF
13
LP Model for Blue Ridge Hot Tubs MAX: 350X1 + 300X2 S.T.: 1X1 + 1X2 <= 200 9X1 + 6X2 <= 1566 12X1 + 16X2 <= 2880 X1 >= 0 X2 >= 0
Rabu, 05 Nopember 2008
METODE KUANTITATIF
14
7
11/5/2008
Solving LP Problems: An Intuitive Approach • Idea: Each Aqua-Spa (X1) generates the highest unit profit ($350), so let’s make as many of them as possible! • How many would that be? – Let X2 = 0 • 1st constraint: 1X1 <= 200 • 2nd constraint: 9X1 <=1566 or X1 <=174 • 3rd constraint: 12X1 <= 2880 or X1 <= 240 • If X2=0, the maximum value of X1 is 174 and the total profit is $350*174 + $300*0 = $60,900 • This solution is feasible, but is it optimal? • No! Rabu, 05 Nopember 2008
METODE KUANTITATIF
15
Solving LP Problems: A Graphical Approach • The constraints of an LP problem defines its feasible region. • The best point in the feasible region is the optimal solution to the problem. • For LP problems with 2 variables, it is easy to plot the feasible region and find the optimal solution.
Rabu, 05 Nopember 2008
METODE KUANTITATIF
16
8
11/5/2008
Plotting the First Constraint
X2 250
(0, 200) 200
boundary line of pump constraint X1 + X2 = 200
150
100
50 (200, 0) 0 0
50
Rabu, 05 Nopember 2008
100
150
200
250
X1
METODE KUANTITATIF
17
Plotting the Second Constraint
X2
(0, 261)
250 boundary line of labor constraint 9X1 + 6X2 = 1566
200
150
100
50 (174, 0) 0 0
Rabu, 05 Nopember 2008
50
100
150
200
METODE KUANTITATIF
250
X1
18
9
11/5/2008
Plotting the Third Constraint
X2 250
(0, 180) 200
150 boundary line of tubing constraint 12X1 + 16X2 = 2880
100 Feasible Region
50 (240, 0) 0 0
Rabu, 05 Nopember 2008
50
100
150
200
METODE KUANTITATIF
250
X1
19
Plotting A Level Curve of the Objective Function
X2 250
200 (0, 116.67)
objective function
150
350X1 + 300X2 = 35000 100 (100, 0)
50
0 0
Rabu, 05 Nopember 2008
50
100
150
200
METODE KUANTITATIF
250
X1
20
10
11/5/2008
A Second Level Curve of the Objective Function
X2 250
(0, 175)
objective function 350X1 + 300X2 = 35000
200
objective function 350X1 + 300X2 = 52500
150
100 (150, 0)
50
0 0
Rabu, 05 Nopember 2008
50
100
150
200
METODE KUANTITATIF
250
X1
21
Using A Level Curve to Locate the Optimal Solution
X2 250
objective function 350X1 + 300X2 = 35000
200
150 optimal solution 100 objective function 350X1 + 300X2 = 52500
50
0 0
Rabu, 05 Nopember 2008
50
100
150
200
METODE KUANTITATIF
250
X1
22
11
11/5/2008
Calculating the Optimal Solution • The optimal solution occurs where the “pumps” and “labor” constraints intersect. • This occurs where: X1 + X2 = 200 (1) and 9X1 + 6X2 = 1566 (2) • From (1) we have, X2 = 200 -X1 (3) • Substituting (3) for X2 in (2) we have, 9X1 + 6 (200 -X1) = 1566 which reduces to X1 = 122 • So the optimal solution is, X1=122, X2=200-X1=78 Total Profit = $350*122 + $300*78 = $66,100
Rabu, 05 Nopember 2008
METODE KUANTITATIF
23
Enumerating The Corner Points
X2 250
obj. value = $54,000 (0, 180)
200
Note: This technique will not work if the solution is unbounded.
obj. value = $64,000
150
(80, 120) obj. value = $66,100 (122, 78)
100
50
obj. value = $60,900 (174, 0)
obj. value = $0 (0, 0)
0 0
50
Rabu, 05 Nopember 2008
100
150
200
METODE KUANTITATIF
250
X1
24
12
11/5/2008
Summary of Graphical Solution to LP Problems 1. Plot the boundary line of each constraint 2. Identify the feasible region 3. Locate the optimal solution by either: a. Plotting level curves b. Enumerating the extreme points
Rabu, 05 Nopember 2008
METODE KUANTITATIF
25
Special Conditions in LP Models • A number of anomalies can occur in LP problems: – Alternate Optimal Solutions – Redundant Constraints – Unbounded Solutions – Infeasibility
Rabu, 05 Nopember 2008
METODE KUANTITATIF
26
13
11/5/2008
Example of Alternate Optimal Solutions X2 250
objective function level curve 450X1 + 300X2 = 78300
200
150
100
alternate optimal solutions
50
0 0
100
50
Rabu, 05 Nopember 2008
150
200
METODE KUANTITATIF
250
X1
27
Example of a Redundant Constraint X2 250 boundary line of tubing constraint 200 boundary line of pump constraint 150 boundary line of labor constraint
100 Feasible Region
50
0 0
Rabu, 05 Nopember 2008
50
100
150
200
METODE KUANTITATIF
250
X1
28
14
11/5/2008
Example of an Unbounded Solution X2 1000
objective function X1 + X2 = 600
800
-X1 + 2X2 = 400
objective function X1 + X2 = 800
600
400
200 X1 + X2 = 400
0 0
Rabu, 05 Nopember 2008
200
400
600
800 METODE KUANTITATIF
1000
X1
29
Example of Infeasibility
X2 250
200
X1 + X2 = 200
feasible region for second constraint
150
100 feasible region for first constraint
50
X1 + X2 = 150
0 0
Rabu, 05 Nopember 2008
50
100
150
200
METODE KUANTITATIF
250
X1
30
15
11/5/2008
Masalah Khusus LP 1. Unbounded : bila satu atau lebih fungsi kendala tidak dimasukkan dalam formulasi modelnya, dengan laba yang diperoleh menjadi tak terhingga dan tidak mempunyai solusi optimal 2. Infeasible : tidak terdapat daerah yang feasibel Max Z = 3X1 + 4X 2
Max Z = X 1 + X 2 s/t :
4X 1 + 2X 2 ≥ 8
s/t :
5X1 + 10X 2 ≤ 30
5X 1 + 15X 2 ≥ 30
2X1 + 2X 2 ≤ 8
X1, X 2 ≥ 0
X1 + X 2 ≥ 7 X1 , X 2 ≥ 0
Rabu, 05 Nopember 2008
METODE KUANTITATIF
31
Literatur • •
Cliff T. Ragsdale, A Practical Introduction to Management Science 5th edition M. Muslich, Metode Kuantitatif, Lembaga Penerbit Fakultas Ekonomi Universitas Indonesia
Rabu, 05 Nopember 2008
METODE KUANTITATIF
32
16
