Project Linear Programming.docx

Paper of Linear Programming

PROJECT

INTEGER LINEAR PROGRAMMING Budi Halomoan Siregar, S.Pd.,M.Sc

Written By : Meidy Adelina (4163312017) Bilingual Mathematics Education 2016 MATHEMATICS DEPARTEMENT FACULTY OF MATHEMATICS AND NATURAL SCIENCES STATE UNIVERSITY OF MEDAN 2018

PREFACE Praise and gratitude I pray the presence of Allah SWT, because thanks to His grace, I can complete project task course LINEAR PROGRAMMING by lecturer sir Budi Halomoan Siregar, S.Pd.,M.Sc, I hope with the existence of this project can be useful to add insight and our knowledge of Simplex Method But I realize that this project is far from perfection. Therefore, I strongly expect constructive advice and criticism from readers for the perfection of this task. Before I also apologize if there are mistakes - words that are less amused readers heart. Finally I say thank you, hopefully can be useful and can increase knowledge for readers.

Medan, Decemberth 2018

Author

1

TABLE OF CONTEN PREFACE............................................................................................................................................ii CHAPTER I.........................................................................................................................................1 INTRODUCTION...............................................................................................................................1 1.1

BACKGROUND..................................................................................................................1

1.2

PURPOSE............................................................................................................................1

CHAPTER II.......................................................................................................................................2 DISCUSSION......................................................................................................................................2 2.1

PROBLEM 1..........................................................................Error! Bookmark not defined.

2.2

PROBLEM 2......................................................................................................................11

YCHAPTER III..................................................................................................................................20 CONCLUSION..................................................................................................................................20

2

CHAPTER I INTRODUCTION 1.1 BACKGROUND One approach that can be done to solve the problem of linear programs is the branch and bound method, the development of the Linear Program where several or all of the decision variables must be integers. Mapping the need for the process is done in the form of integers (not the fractions that usually occur if we use the simplex method). The mathematical model of programming is the same as the linear programming model, with the additional limitation that the variable must be an integer. For more details, in this paper the author will say branch and bound methods. 1.2 PURPOSE To help the readers of this paper get understand integer programming problem by branching and bounding, specially to help readers get understand easier to integer solution by branching and bounding,

1.3 BENEFITS Readers can know about Integer Progrmming in linear programming problem, readers can understand how to integer solution by branching and bounding, using linear programming app.

1

CHAPTER II DISCUSSION 1. Example From Book

(Tommy Sottinen ,2009)

The Other Question Sebuah perusahaan mesin pengolah pangan “MAJU JAYA” memproduksi 2 jenis produk,yaitu drum dryer dan spraydryer. Masing-masing produk tersebut membutuhkan 2 tahapan produksi,yaitu kelistrikan dan perakitan.Waktu kelistrikan adalah 2 jam untuk drum dryer dan 3 jam untuk spraydryer. Sedangkan waktu perakitan adalah 6 jam untuk drum dryer dan 5 jam untuk spraydryer. Perusahaan tersebut hanya mempunyai waktu untuk kelistrikan 12 jam, dan waktu untuk perakitan 30 jam kerja perminggu. Drum dryer memberikan keuntungan 70 juta per unitnya, sedangkan spraydryer 60 juta perunitnya, tentukan banyaknya drumdryer dan spraydryer yang sebaiknya diproduksi untuk mendapatkan keuntungan yang maksimal! x 1 = Drumdryer x 2 = Spraydrayer

Maximize

z=7 x 1+ 6 x 2 ( x 10 jt )

Subject to : 2 x 1 +3 x 2 ≤ 12 6 x 1+25 x 2 ≤ 30

(Electricity) (Assembly)

x1 , x2 ≥ 0

2

Solution Using LingoAplication Determine optimum value from solve the problem given we use the lingo software, the completion steps are : Open the new lingo worksheet. Next, a new worksheet will appear as shown below

 Open the new lingo worksheet. Next, a new worksheet will appear as shown below



Type the objective function and constraint function on the lingo worksheet will appear as shown



Click icon “SOLVE” for appear shown below.

3



After clicking the solve icon, the lingo screen will then display the following image



So, we find optimum value from solve the problem given are :

z=35 x 1=3

3 4

x 2=1

1 2

Jika

1 4

x 1 , x 2 dan z bukan bilangan bulat kita selanjutnya mencari nilai optimum dengan

menambakan fungsi kendala yang baru pada masalah program linear yang diberikan.

4

A

2A 2B

5

z=7 x 1+ 6 x 2 2 x 1 +3 x 2 ≤ 12 6 x 1+5 x 2 ≤ 30

2A

x1≤ 3 x1 , x2 ≥ 0

z=7 x 1+ 6 x 2 2 x 1 +3 x 2 ≤ 12 6 x 1+5 x 2 ≤ 30 x1 ≥ 4

2B

Dari hasil proses percabangan, didapat nilai optimum dari

x1 , x2 ≥ 0

2A nilai optimum sudah

merupakan bilangan bulat tetapi masih belum mencapai nilai optimum terdekat dari nilai optimum awal yaitu z . Sedangkan hasil dari proses percabangan dari 2B didapat nilai optimum

x 1=4 , x 2=1

1 1 dan Z =32 . Karena nilai 10 2

x 2 tidak bilangan bulat. Maka kita

lanjutkan proses percabangan selanjutnya dengan mendapatkan submasalah yang baru, yaitu :

6

A

2B

2A

3A

3B

7

z=7 x 1+ 6 x 2 2 x 1 +3 x 2 ≤ 12 6 x 1+5 x 2 ≤ 30 x1 ≤ 4 x2≥ 2 3A

x1 , x2 ≥ 0

z=7 x 1+16 x 2 2 x 1 +3 x 2 ≤ 12 6 x 1+5 x 2 ≤ 30 x1 ≥ 4 x2 ≤ 1 3B

x1 ≤ 4 x1 , x2 ≥ 0

Dari proses percabangan diatas kita dapat bahwa 3B “ No Feasible Solution” maka solusi 1 , x2 = 1 sudah optimumnya tidak ada. Dan di 3A kita mendapatkan nilai z=35 6 1 bilangan bulat sedangkan nilai x 1 = 4 bukan merupakan bilangan bulat . Maka kita 4 lanjutkan proses percabangan selanjutnya dengan mendapatkan dua submasalah yang baru, yaitu :

8

A

2B

2A

3B

3A

,

4A

4B

9

z=7 x 1+ 6 x 2 20 x1 + 42 x 2 ≤ 12 6 x 1+7 x 2 ≤ 30 x1 ≥ 4 x2 ≤ 1 x1≥ 5 4A

x1 , x2 ≥ 0

z=7 x 1+ 6 x 2 2 x 1 +3 x 2 ≤ 12 6 x 1+5 x 2 ≤ 30 x1 ≤ 4 x2≥ 1 4B

x1 , x2 ≥ 0

Dari cabang di atas didapat solusi optimal adalah 4B dan dari nilai optimum 4A didapat z = 35. Kita memilih 4B karena nilai opminum z adalah nilai yang paling maksimal. Jadi solusi dari program linear bilangan bulat di atas adalah : z=35

x 1=5 x 2=0

2. Example From Book

Solution Using LingoAplication

10

(Paul R thie,2008)

The Other Question Maximize

z=5 x 1+8 x 2

Subject to :

x 1+ x 2 ≤6

5 x1 +9 x 2 ≤ 45

x1 ,

x 2 ≥ 0 and integral

Determine optimum value from solve the problem given we use the lingo software, the completion steps are :

 Open the new lingo worksheet. Next, a new worksheet will appear as shown below



Type the objective function and constraint function on the lingo worksheet will appear as shown 11



Click icon “SOLVE” for appear shown below.



After clicking the solve icon, the lingo screen will then display the following image :



So, we find optimum value from solve the problem given are : 12

z= x 1=

9 4

x 2=

15 4

Jika

165 4

x 1 , x 2 dan z bukan bilangan bulat kita selanjutnya mencari nilai optimum dengan

menambakan fungsi kendala yang baru pada masalah program linear yang diberikan.

A

2A 2B

13

z=5 x 1+8 x 2 x 1+ x 2 ≤6 5 x1 +9 x 2 ≤ 45 x2≤ 3 x1 , x2 ≥ 0

2A

z=5 x 1+8 x 2 x 1+ x 2 ≤6 5 x1 +9 x 2 ≤ 45 x2 ≥ 4 x1 , x2 ≥ 0

2B

Dari hasil proses percabangan, dari 2A di dapat nilai optimum z=33, x1=3, x 2=3 . Pada masalah bagian 2A sudah didapatkan solusi yang semuanya bulat, Sedangkan hasil dari proses percabangan dari 2B didapat nilai optimum nilai

¿ 41

x 1=1

8 , x =4 . Karena 10 2

x 1 tidak bilangan bulat. sehinga masih memungkinkan untuk dicari solusi bulat

lainnya yang nilainya mungkin lebih besar dari solusi masalah 2A. Dengan demikian masalah 2B dapat dicabangkan lagi menjadi dua bagian dengan menambahkan kendala

x≤1

dan

x1 ≥ 2 .

14

A

2B

2A

3A

3B

15

z=5 x 1+8 x 2 x 1+ x 2 ≤6 5 x1 +9 x 2 ≤ 45 x2 ≥ 4 3A

x1 ≤ 1 x1 , x2 ≥ 0

z=5 x 1+8 x 2 x 1+ x 2 ≤6 5 x1 +9 x 2 ≤ 45 x2 ≥ 4 x1 ≥ 2 3B

x1 , x2 ≥ 0

Dari hasil proses percabangan, dari 3B didapat bahwa“no feasible solution”. Sedangkan hasil dari proses percabangan dari 3A di dapat nilai optimum nilai

x 1=1 , x 2=4

4 dan Z=37 . Karena 9

x 2 tidak bilangan bulat. Maka kita lanjutkan proses percabangan selanjutnya dengan

mendapatkan dua submasalah yang baru, yaitu :

16

A

2B

2A

3B

3A

,

4A

4B

17

z=5 x 1+8 x 2 x 1+ x 2 ≤6 5 x1 +9 x 2 ≤ 45 x2 ≥ 4 x2≤ 1 x1 ≤ 4 , x1 , x2 ≥ 0

4A

z=5 x 1+8 x 2 x 1+ x 2 ≤6 5 x1 +9 x 2 ≤ 45 x2 ≥ 4 x2 ≤ 1 x1≤ 4 , x1 , x2 ≥ 0

4B

Dari hasil proses percabangan, dari 4A didapat nilai optimum x 1=4, x 2=1 dan z =37 . Sedangkan

hasil

dari

proses

percabangan

dari

4B

didapat

nilai

optimum

x 1=0 , ¿ x2=0 dan Z=40 . Dari cabang di atas didapat solusi optimal adalah 4B dan dari nilai optimum 4B didapat z = 40. Kita memilih 4B karena nilai opminum z adalah nilai yang lebihdekatdarisolusi optimum awalyaitu z awal. Jadi solusi dari program linear bilangan bulat di atas adalah : z=40

x 1=0 x 2=5

18

CHAPTER III CONCLUSION

Branch and Bound technique is a suitable solution technique to use to solve a linear program problem that requires each the variable is an integer and is developed on the principle that total a set of feasible solutions can be divided into smaller subsets of solutions. These subset can then be systematically evaluated until the solution the best found. Branch and Bound techniques on linear program issues used together with the simplex method. This technique uses a diagram consisting of nodes and branches as an inner framework the process of obtaining optimal solutions.

19