Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam (JURRIMIPA) Vol.
No.
2 Oktober 2023 p-ISSN: 2828-9382.
e-ISSN: 2828-9390-0143.
Hal 53-64 DOI: https://doi.
org/ 10.
55606/jurrimipa.
Application Of Thebranch And Bound In Optimizing The Amount Of Bread Production In CV.
Zuhro Bakery Perbaungan Novita Sari Dewi1.
James Piter Marbun2 Departement Of Mathematics.
Universitas Sumatera Utara.
Medan.
Indonesia Email: Novitasaridewi275@gmail.
Abstract.
CV.
Zuhro Bakery is baking factory producing various kinds of bread.
In this research, there were three kinds of bread that were studied, they were chocolate, mocha and strawberry flavored bread.
The problem in optimalization of the production was modeled into a mathematic model which was the linear program in the form obstacle function and objective function.
It was then continued by the deciding variable in integer number as the linear program.
Then, it was solved by using Branch and Bound method which previously had counted the variable by using the symplex method.
From the simplex method, an integer number result was not found, so the Branch and Bound method was used.
QM software was chosen in the research to solve the integer problem.
A profit was earned with a sale margin of Rp39.
000 or 0,42% from the coorporationAos expected profit by using the Branch and Bound method.
The amount of bread produced in the periode of three days were 5.
400 consosted of 3.
060 chocolate flavored bread, 440 mocha flavored bread and 900 strawberry flavored bread with the total profit of Rp9.
Keywords: Branch and Bound Method.
Simplex Method.
Integer Programming.
Liniear Programming INTRODUCTION Industrial development has increased very rapidly.
This can be seen from the increasing number of industrial companies in Indonesia every year.
The increasing number of industrial companies has created competitive competition among industrial companies in Indonesia, especially companies engaged in the same field.
Therefore, everyone must have good product management to compete with other industrial companies to optimize the company's income for industrial companies.
North Sumatra is the third-largest province in Indonesia.
Medan City is a city that is ranked as the 7th largest economy in Indonesia and controls around 1.
41% of RI's The city of Medan also has many industrial companies in it.
One of them is an industrial company in the food sector, namely a bread manufacturing industry company.
CV.
Zuhro Bakery is a company engaged in the production of bread.
CV.
Zuhro Bakery Received April 30, 2023.
Revised Mei 30, 2023.
Accepted Juni 12, 2023 * Novita Sari Dewi.
Novitasaridewi275@gmail.
Application Of Thebranch And Bound In Optimizing The Amount Of Bread Production In CV.
Zuhro Bakery Perbaungan was founded in 1980.
CV.
Zuhro Bakeri produces various types of bread and various types of bread flavors.
The problem faced by this company is the difficulty of determining the optimal amount of production with various constraints, such as the absence of a certain method of producing bread, the use of raw materials, and others.
This of course has an impact on company profits that are erratic and less than optimal.
So that the number of products produced is optimal, the Linear Programming approach can be used as a way of making decisions in terms of optimizing production, namely by using the Simplex method.
Making a Linear Program is making a plan of activities to obtain optimal results, namely a result that achieves the specified goals in the best way .
ccording to a mathematical mode.
among all possible alternatives.
Integer Linear Program or Integer Linear Program is a linear programming model that is used to adapt a problem to a linear program where the decision variables in the optimal solution must be integers.
The characteristics of the Linear Integer Program mathematical model are the same as the ordinary linear model, but the Linear Integer Program must contain an additional requirement that the decision variable must be an integer number.
In this case, the problem-solving method used is the Branch and Bound method.
Examines the calculation of optimum profit in CV.
XYZ which in the conclusion of the study it is known that the benefits obtained by CV.
XYZ will reach 53,292,000.
00 per month if pants production reaches the optimal target and there is no increase in raw materials.
The application of knowledge about research operations in everyday life is very widely used by humans, for example in the economic field.
Factors in the field of production are increasingly sophisticated, human needs are increasing due to increasing population growth which is the cause of the increasing production of needed goods.
Minimal capital can generate a lot of profit, so optimization problems arise.
Drinking or maximizing profits with the capacity of existing resources to achieve optimal results is a problem that often arises in optimization problems.
Optimization is the process of finding the optimal solution to a problem using linear programming.
The linear program invented by George Dantzig .
was originally often used in the field of military planning, especially in World War II by the armed forces of the United States and Britain.
JURRIMIPA: Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam- Vol.
No.
2 Oktober 2023 p-ISSN: 2828-9382.
e-ISSN: 2828-9390-0143.
Hal 53-64 The branch and bound method are one of the approaches used in solving linear programming problems, which is a development of linear programming where the decision variable must be an integer.
Integer programming is needed when decisions must be made in integer form .
ot fractions which often occurs when we use the simplex The mathematical model of integer programming is the same as the linear programming model, with the additional restriction that the variables must be integers.
LITERATURE REVIEW
Liner Programming The linear program is a mathematical model to explain the problems it faces.
the operational research process is generally establishing a model and then developing that model.
The model is a system in which the elements influence each other.
A linear program is planning activities to obtain an optimum result .
Linear programming is an optimal solution technique for a decision problem by first determining the objective function .
aximizing or minimizin.
and the existing constraints into a mathematical model of linear equations.
Linear programming is often used in solving resource allocation problems .
suggests that the most important main idea in using linear programming is to formulate the problem using the amount of information available.
Then translate the problem into a mathematical model, which is an easier and more structured way to solve the problem to get the solution.
Linear Program Model The general equation in a Linear Program can be formulated as follows:
Maximize/minimize .
Application Of Thebranch And Bound In Optimizing The Amount Of Bread Production In CV.
Zuhro Bakery Perbaungan With xj Ou 0.
and i = 1,2,3,.
,m.
j=1,2,3,.
,n.
Assuming that aij, bi, cj is the known model coefficient.
Z = The objective function for optimal value .
aximum or minimu.
xj = Decision variable j-th cj = An increase in the value of Z occurs when there is an increase in the level of activity xj by one unit or the contribution of each unit of output of activity Z to aij = The number of sources needed to produce each unit of activity output j bi= The available i resource capacity to be allocated to each activity unit n = Types of activities that use available resources or facilities m = Kinds of limitations on the resources or facilities available Linear Programming Solution Generally linear programming problems can be solved using two methods, namely .
Graph Method Linear programming problems can be illustrated and physically solved if they have only two decision variables.
Although problems with two variables are rare in the real world, the geometric interpretation of this graphical method is very useful.
The search for the optimal solution is carried out by finding the optimal settlement point in the feasibility area.
Simplex Method This method can be used for the number of decision variables of two or more and the number of constraints of two or more.
The simplex method is a repeat procedure that moves from one basic feasible answer to the next in such a way that the value of the objective function continues to increase .
n the maximization proble.
and will continue until an optimal answer .
f an.
is obtained that gives the maximum value.
Integer Linear Programming An integer program is a linear program with the additional requirement that all or some of the variables have non-negative integer values, but it does not require that the model parameters also have integer values.
There are many cases in the integer programming problem where model variables are restricted to zero or one.
Partial .
acceptance or rejection is not allowed.
If the decision variable has a value of one, the activity is accepted.
If the variable is zero, the activity is rejected.
JURRIMIPA: Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam- Vol.
No.
2 Oktober 2023 Branch and Bound Method p-ISSN: 2828-9382.
e-ISSN: 2828-9390-0143.
Hal 53-64 The Branch and Bound method was first introduced by .
The basic idea is to divide the feasible solution area into smaller feasible solution areas.
It is a simple procedure that assigns higher and lower constraints to the solution when solving subproblems in a systematic way.
Later this method was modified by Dakin .
and successfully applied it in commercial law codes which are widely used in solving integer programming problems.
The Branch and Bound method is often used to solve a linear integer programming problem because the results obtained in solving the optimization are more thorough.
The weakness of this method is that the procedure for achieving optimal results is very long.
Apart from completing it manually with the simple method and Branch and Bound, it can also be completed with the help of QM For Windows .
Branch and Bound Method Procedure Integer program maximization problem solving algorithm with method Branches and Bound are as follows .
Optimal completion with the usual linear program method The problem is first solved by Linear Programming .
raph or simple.
until the optimum result is obtained.
Optimum finish check The optimal results in step 1 are checked whether the decision variables obtained are integer or fractional.
If the value turns out to be all the decision variables are positive integers .
on-negative integer.
, then the optimal solution has been achieved.
If not, then the iteration process is continued.
Preparation of subproblems .
If the optimal solution has not been reached, then the problem is modified into two sub-problems .
by incorporating new constraints into each of these subproblems.
The new trick variables must be mutually exclusive constraints so that they meet the integer completion requirements.
Determine the limit value .
The optimal result obtained by the usual linear programming method .
on-intege.
is the upper bound value for each subproblem.
While the optimal result with integer solutions is the lower limit value .
ower limi.
for each subproblem.
Furthermore, if Application Of Thebranch And Bound In Optimizing The Amount Of Bread Production In CV.
Zuhro Bakery Perbaungan a sub-problem has an upper limit that is lower than the applicable lower limit, then the sub-problem does not need to be analyzed again.
If the solution to integers produces results that are equal to or better than the upper limit value of each problem, then the optimal integer solution has been reached.
If not, then the subproblem that has the best upper bound value is selected and then becomes a new subproblem.
This iterative process returns to step 2, and so on .
RESEARCH METHOD
The data used in this study are secondary data obtained from CV.
Zuhro Bakery Perbaungan.
The branch and bound method is used because in processing data at CV.
Zuhro Bakery Perbaungan must produce integer decision variables so that the final results obtained in this study are more optimal to maximise profits in the amount of bread production at CV.
Zuhro Bakery Perbaungan.
Testing will be assisted by POM QM software so that data processing will be easier.
RESULT AND DISCUSSION
In this study, the branch and bound method was used because in processing the data on the CV.
Zuhro Bakery Perbaungan must produce integer decision variables so that the final results obtained in this study are more optimal to maximize profits in the number of bread production in CV.
Zuhro Bakery Perbaungan.
Tabel 1 Bread Type Bread Type Chocolate Bread Mocca Bread Strawberry Bread JURRIMIPA: Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam- Vol.
No.
2 Oktober 2023 p-ISSN: 2828-9382.
e-ISSN: 2828-9390-0143.
Hal 53-64 Tabel 2 Bread Raw Materials Bread Type .
Raw Material Chocolate Mocca Strawberry Wheat Sugar Butter Salt Softener Developer 1,25 0,18 0,16 0,14 0,18 0,16 0,14 1,35 0,18 0,16 0,14 Raw Material Inventory per 3 days .
Tabel 3 Product Profit Data Bread Type Chocolate Mocca Strawberry Cost of goods Rp360.
Rp387.
Rp333.
Selling price Profit Rp2.
Rp2.
Rp2.
Rp307.
Rp320.
Rp300.
Tabel 4 Decision Variable Symbol Bread Type Chocolate Bread Mocca Bread Strawberry Bread Variabel Based on the data obtained, it can be formulated as follows:
= 307000
Contstrains:
= 10,5x 10,5x 11x O 320
= 2,5
= ,
= ,
= ,
= ,
Ou .
O 77
= , , , ,
O ,
Application Of Thebranch And Bound In Optimizing The Amount Of Bread Production In CV.
Zuhro Bakery Perbaungan Solution Using the Simplex Method Tabel 5 Simplex Table Iteration 1 Basic Variables 1,25 0,18 0,16 0,14 0,18 0,16 0,14 1,35 0,18 0,16 0,14 Because negative values are still found in the objective function, the iteration The iteration will stop if all values are not found to be negative in the objective The following is a picture of using the QM Software with the Simplex Method which produces several iterations to obtain optimal results.
Figure 1Solutions from iterations with QM software.
Then the initial solution of this problem is x1 = 18,421 x2 = 6,7752 x3 = 5,2117 Solution Using the Branch and Bound Method The first step is to determine the upper limit (BA) and lower limit (BB).
The results obtained earlier, namely x1 = 18.
241 , x2 = 6.
7752 , x3 = 5.
2117, with a profit of Rp.
9,331,596 are not valid solutions because x1, x2 and x3 are not integers.
However, the profit value is IDR 9,331,596 which is the upper limit (BA).
With the method of rounding JURRIMIPA: Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam- Vol.
No.
2 Oktober 2023 p-ISSN: 2828-9382.
e-ISSN: 2828-9390-0143.
Hal 53-64 down, we get: x1 = 18, x2 = 6 , x3 = 5.
with a profit of IDR 9,331,596.
Profit value rounded down is used as the lower limit (BB).
After the upper and lower limits are determined, then the next step is to choose a decision variable for branching.
The decision variable has the largest fractional value.
The largest fraction is at x2, which is 6.
7752, so x2 is branched into sub-problem 1, namely x2 Ou 7 and for sub-problem 2, namely x2O 6.
So obtained:
Iteration 1 Sub Problem 1 Maximize Equation 1 Constraint Equation 2.
x2 Ou 7 By using the simplex method obtained:
Solution to subproblem 1: x1 = 18,0818, x2 = 7, x3 = 5,1094.
Z = 9.
Sub Problem 2 Maximize Equation 1 Constraint Equation 2 x2 O 6 By using the simplex method obtained:
Solution to sub problem 2: x1 = 19,3103, x2 = 6, x3 = 4,931.
Z = 9.
Iteration 2 Sub Problem 3 Maximize Equation 1 Constraint Equation 2.
x2Ou 7.
x3Ou 6 By using the simplex method obtained:
Solution to sub problem 3 : x1 = 17,12, x2 = 7, x3 = 6.
Z = 9.
Sub Problem 4 Maximize Equation 1 Constraint Equation 2.
x2 Ou7.
x3 O 5 By using the simplex method obtained:
Solution to sub problem 4 : x1 = 18,1716, x2 = 7, x3 = 5.
Z = 9.
Iteration 3 Sub Problem 5 Maximize Equation 1 Constraint Equation 2.
x_2 O 6.
x3 Ou 5 Application Of Thebranch And Bound In Optimizing The Amount Of Bread Production In CV.
Zuhro Bakery Perbaungan By using the simplex method obtained:
Solution to sub problem 5 : x1 = 19,2381, x2 = 6, x3 = 5.
Z = 9.
Sub Problem 6 Maximize Equation 1 Constraint Equation 2.
x2 O 6.
x3 O 4 By using the simplex method obtained:
Solution to sub problem 6 : x1 = 22,8571, x2 = 3,4286, x3 = 4.
Z = 9.
The above solution can be explained in the Branch and Bound method in the QM software seen in Figure 2 as follows:
Figure 2 Branch and Bound Solutions.
From the results of calculations using the Branch and Bound method, optimal results are obtained in the 15th iteration of Subproblem 29 with a value of x1=17, x2=8, x3=5.
with Z= 9,279,000.
Thus, each flavor is produced as much as 17 chocolate mixtures, 8 mocca mixtures, and 5 strawberry mixtures.
Where each dough produces 180 loaves of bread, the amount obtained for each loaf is:
The taste of brown bread is 17 pieces of dough $\times$ 180 pieces of bread = 3,060 The taste of mocca bread is 8 pieces of dough $\times$ 180 pieces of bread = 1,440 pieces of bread The taste of strawberry bread is 5 pieces of dough $\times$ 180 pieces of bread = 900 pieces of bread So the number of loaves that can be produced from available materials is 5,400 loaves of bread with a profit of IDR 9,279,000.
Profit Comparison Comparison of company profits and profits using the Branch and Bound method can be seen in Table 6 JURRIMIPA: Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam- Vol.
No.
2 Oktober 2023 p-ISSN: 2828-9382.
e-ISSN: 2828-9390-0143.
Hal 53-64 Tabel 6 Decision Variable Symbol Bread Type Chocolate Bread Mocca Bread Strawberry Bread Total Company Production Number of Profit Bread Rp6.
Branch and Bound Method Number Profit of Bread Rp5.
Rp1.
Rp2.
Rp1.
Rp1.
Rp9.
Rp9.
The company's profit amounted to IDR 9,240,000 using the Branch and Bound method, and the profit increased by IDR 9,279,000.
If profits are converted into percent, profits using the Branch and Bound method increase by 0.
42% or IDR 39,000 of the company's total profits in 3 days by producing 5,400 loaves of bread, namely 3,060 chocolate loaves, 1,440 Mocca loaves and 900 strawberry loaves.
CONCLUSION
From the description and calculations, it can be concluded that:
From the analysis using Branch and Bound, the optimal number of loaves to produce within 3 days was 5,400 loaves, namely 3,060 loaves of chocolate flavored bread, 1,440 loaves of mocca bread and 900 loaves of strawberry bread with a profit of IDR 9,279,000.
The company's profits increased using the Branch and Bound Method, namely by 42%, namely IDR 39,000 from the previous profit of IDR 9,240,000 to IDR 9279,000 within 3 days.
Application Of Thebranch And Bound In Optimizing The Amount Of Bread Production In CV.
Zuhro Bakery Perbaungan REFERENCES