Paper Of 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, Novemberth 2018

Author

TABLE OF CONTENT

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 how to integer solution by branching and bounding, using linear

programming app.

can

understand

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! 𝑥1 = Drumdryer 𝑥2 = Spraydrayer Max 𝑧 = 7𝑥1 + 6𝑥2 ( x 10 jt ) Fungsi Kendala : 2𝑥1 + 3𝑥2 ≤ 12 6𝑥1 + 25𝑥2 ≤ 30 𝑥1 , 𝑥2 ≥ 0

(Electricity) (Assembly)

Solution Using LingoAplication Tentukan nilai optimum dari masalah program linear yang diberikanmenggunakanaplikasi lingo :

 Membuka lembar kerja baru lingo. Selanjutnya, akan tampil lembar kerja baru seperti gambar di bawah ini



Mengetik fungsi tujuan dan fungsi kendala pada lembar kerja, seperti dibawah ini



Klik ikon “SOLVE”.pada bagian atas lingo untuk menampilkan hasilnya

Jika



Maka setelah program Lingo dijalankan akan diperoleh hasil seperti berikut:



Jadi didapatlah nilai optimum dari masalah program linaer yang diberikan 𝑧 = 35

1 4

𝑥1 = 3

3 4

𝑥2 = 1

1 2

𝑥1 , 𝑥2 𝑑𝑎𝑛 𝑧 bukan bilangan bulat kita selanjutnya mencari nilai optimum dengan menambakan fungsi

kendala yang baru pada masalah program linear yang diberikan.

A

𝑧 = 7𝑥1 + 6𝑥2

𝑥≤3 𝑧 = 7𝑥1 + 6𝑥2 2𝑥1 + 3𝑥2 ≤ 12 6𝑥1 + 5𝑥2 ≤ 30

𝑧 = 33 2A

𝑥1 = 3 𝑥2 = 2

𝑥1 ≤ 3

𝑥1 , 𝑥2 ≥ 0

𝑧 = 35

1 4

𝑥1 = 3

3 4

𝑥2 = 1

1 2

2𝑥1 + 3𝑥2 ≤ 12 6𝑥1 + 5𝑥2 ≤ 30 𝑥1 , 𝑥2 ≥ 0

𝑥≥4 Type equation here. 𝑧 = 32

1 2

𝑧 = 7𝑥1 + 6𝑥2 2𝑥1 + 3𝑥2 ≤ 12

𝑥1 = 4 2 𝑥2 = 1 10

2B

6𝑥1 + 5𝑥2 ≤ 30 𝑥1 ≥ 4 𝑥1 , 𝑥2 ≥ 0

=3

𝑧 = 7𝑥1 + 6𝑥2 2𝑥1 + 3𝑥2 ≤ 12 6𝑥1 + 5𝑥2 ≤ 30 𝑥1 ≤ 3

2A

𝑥1 , 𝑥2 ≥ 0

𝑧 = 7𝑥1 + 6𝑥2 2𝑥1 + 3𝑥2 ≤ 12 6𝑥1 + 5𝑥2 ≤ 30 𝑥1 ≥ 4 𝑥1 , 𝑥2 ≥ 0

2B

Dari hasil proses percabangan, didapat nilai optimum dari 2A nilai optimum sudah merupakan bilangan bulat tetapi masih belum mencapai nilai optimum terdekat dari nilai optimum awal yaitu z . Sedangkan hasil dari proses 1

1

percabangan dari 2B didapat nilai optimum 𝑥1 = 4 , 𝑥2 = 1 10 𝑑𝑎𝑛 𝑍 = 32 2. Karena nilai 𝑥2 tidak bilangan bulat. Maka kita lanjutkan proses percabangan selanjutnya dengan mendapatkan submasalah yang baru, yaitu :

A

𝑧 = 5𝑥1 + 8𝑥2

𝑥≤3

𝑧 = 35

1 4

𝑥1 = 3

3 4

𝑥1 = 1

1 2

𝑥1 + 𝑥2 ≤ 6 5𝑥1 + 9𝑥2 ≤ 45 𝑥1 , 𝑥2 ≥ 0

𝑥≥4 Type equation here.

𝑧 = 5𝑥1 + 8𝑥2

𝑧 = 39

𝑧 = 41

𝑥1 + 𝑥2 ≤ 6

𝑥1 = 3

8 𝑥1 = 1 10

2A

5𝑥1 + 9𝑥2 ≤ 30

𝑥2 = 3

𝑧 = 5𝑥1 + 8𝑥2 𝑥1 + 𝑥2 ≤ 6 2B

5𝑥1 + 9𝑥2 ≤ 45 𝑥2 ≥ 4

𝑥2 = 4

𝑥2 ≤ 3

𝑥1 , 𝑥2 ≥ 0

𝑥1 , 𝑥2 ≥ 0 =3

𝑧 = 40,55

𝑥1 + 𝑥2 ≤ 6

𝑥2 ≥ 4

𝑥≥2 𝑧 = 5𝑥1 + 8𝑥2

𝑧 = 5𝑥1 + 8𝑥2

5𝑥1 + 9𝑥2 ≤ 45

𝑥≤1

𝑥1 = 1 3A

4 𝑥2 = 4 9

𝑥1 + 𝑥2 ≤ 6 𝑁𝑜 𝐹𝑒𝑎𝑠𝑖𝑏𝑙𝑒

3B

5𝑥1 + 9𝑥2 ≤ 45 𝑥2 ≥ 4 𝑥1 ≥ 2

𝑥2 ≤ 1 𝑥1 , 𝑥2 ≥ 0

𝑥1 , 𝑥2 ≥ 0 =3 𝑥1 , 𝑥2 ≥ 0

𝑥2 ≤ 1 𝑥1 , 𝑥2 ≥ 0

𝑥1 , 𝑥2 ≥ 0