Application of Linear Programming to Profit Maximization.

Application of Linear Programming to Profit Maximization.

Michael Kwofie

Northern Arizona University

Godfred Akwasi Afrifa

Ohio University

Abstract

This study applies linear programming to determine the profit-maximizing product mix for Seth Kojos (S.K.) Bakery in Ghana. A mathematical model is formulated to allocate limited raw materials among four products: banana, coconut, wheat, and but-ter bread, subject to ingredient availability constraints. Using the linprog function in MATLAB, the model identifies the optimal monthly production levels and correspond-ing maximum profit. The results show that wheat and butter bread dominate the optimal solution, while coconut bread is excluded due to its inefficient resource-profit trade-off. The optimal mix yields a maximum monthly profit of GH¢407,350. Sen-sitivity analysis further reveals that butter- and flour-related constraints are binding, indicating that expanding these resources would generate the greatest marginal gains. The findings demonstrate the value of linear programming as a decision-support tool for small-scale enterprises and highlight how quantitative optimization can improve production planning, resource utilization, and profitability in bakery operations.

1. Introduction

   In a competitive business environment, efficient resource allocation is essential for maximizing profitability and ensuring sustainability. Many small and medium-scale enterprises (SMEs), particularly in developing economies, often rely on intuitive or trial-and-error methods for

   production planning. Such approaches may lead to suboptimal decisions, inecient use of resources, and reduced protability. Consequently, there is a growing need for the adoption of quantitative techniques that support informed and optimal decision-making.

   Linear programming (LP) is a widely used optimization technique in operations research that enables decision-makers to determine the best possible outcome, such as maximum prot or minimum cost, subject to a set of linear constraints. Since the development of the simplex algorithm by George Dantzig in 1947, linear programming has been successfully applied in various elds, including manufacturing, transportation, agriculture, and energy management. Its strength lies in its ability to handle multiple constraints while providing optimal solutions in a systematic and ecient manner.

   In the context of production planning, linear programming is particularly useful for deter-mining the optimal product mix when resources are limited. By formulating the problem as a mathematical model, businesses can identify which products to produce and in what quantities in order to maximize prot. This is especially relevant for bakeries and similar production-oriented enterprises, where multiple products compete for shared raw materials. This study focuses on the application of linear programming to maximize prot in Seth Kojos (S.K) Bakery. The bakery produces four types of bread: banana bread, coconut bread, wheat bread, and butter bread using a xed quantity of raw materials each month. The central problem addressed in this research is how to eciently allocate these limited resources across the dierent products in order to achieve maximum prot.

   The main objective of this study is to develop and solve a linear programming model that determines the optimal production levels for each type of bread. Specically, the study aims to

   1. formulate an objective function that represents total prot.

   2. incorporate resource constraints based on available raw materials.

   3. compute the optimal solution using the simplex algorithm.

   By doing so, the study provides practical insights into how mathematical optimization tech-niques can enhance decision making in real-world business environments.

   The ndings of this research are expected to contribute to both academic and practical domains. Academically, the study demonstrates the application of linear programming in a real-life context. Practically, it oers a decision-support framework that can assist business managers in improving production eciency and protability.

2. Literature Review

   Linear programming (LP) has been widely recognized as one of the most powerful optimiza-tion techniques in operations research, with extensive applications across various sectors including manufacturing, agriculture, transportation, and energy management. Its primary strength lies in its ability to model complex decision-making problems involving multiple constraints and limited resources while providing optimal solutions in a systematic and com-putationally ecient manner. Several studies have demonstrated the applicability of linear programming in production planning and prot maximization. For instance, [1] highlighted the importance of optimization models in production planning, emphasizing that incorporat-ing uncertainty into linear programming models can signicantly improve decision quality. Similarly, [2] applied mixed-integer linear programming to aggregate production planning, showing how rms can determine optimal workforce levels and production quantities under varying constraints.

   According to [3], linear programming is a linear algebra generalization used in modeling many real-life problems ranging from scheduling airline routes to shipping oil from reneries to cities. The author argued that the great versatility of linear programming lies in the ease with which constraints can be incorporated into optimization models. [2] further reported that mixed integer linear programming plays an important role in aggregate production planning, particularly in determining workforce levels and optimal product mixes. In addition, [4] described linear programming as a revolutionary development that enables organizations to set goals and make decisions directed toward maximizing prot. Similarly, [5] observed that linear programming contributes signicantly to improving management decisions in areas such as production planning, resource allocation, inventory control, and advertisement.

   In the context of business prot maximization, linear programming has proven to be an

   eective decision-support tool. [6] utilized linear programming to optimize production in a beverage company, demonstrating that an optimal product mix can substantially increase protability. Likewise, [7] applied LP techniques to a manufacturing rm and identied optimal production quantities that maximized monthly prot. These studies reinforce the practical relevance of LP in guiding managerial decisions regarding resource allocation and production strategies.

   According to [1], production planning problems represent one of the most important applica-tions of optimization tools using linear programming. They emphasized that incorporating uncertainty into LP models is essential in avoiding inferior planning decisions, a concept closely related to sensitivity analysis. [8] recognized LP as an important tool in energy man-agement despite the nonlinear nature of many energy systems, arguing that nonlinearities can often be transformed into linear forms using Taylor series approximations. Furthermore,

   [9] reported that business success depends greatly on eective decision-making and applied LP techniques to optimize the use of resources for sta training.

   Applications of linear programming are also prominent in agriculture and small-scale en-terprise management. [10] employed LP to maximize returns in agricultural prouction systems, while [11] developed a model for optimizing crop allocation among rural farmers. In a similar vein, [12] applied linear programming to a local soap production company and demonstrated how optimal resource allocation could improve protability. These studies indicate that LP is not only applicable to large-scale industries but is also highly relevant for small and medium-scale enterprises.

   [10] further reported that linear programming is an eective technique for agricultural pro-duction planning and gross return maximization. [6] used LP to determine the optimal pro-duction process for the Coca-Cola Company by considering constraints such as sugar content, water volume, and carbon dioxide concentration, concluding that concentrating on certain products yielded maximum prot. [7] applied LP to optimize prot in the Golden Plastic Industry and identied the most protable pipe sizes for production. [13] also demonstrated the application of LP models to product-mix prot maximization using an R-statistical package. In addition, [14] highlighted optimization as a crucial science in high-performance reneries where maximizing protability is a key objective. [11] formulated an LP model to

   maximize the income of rural farmers, while [12] applied LP models to maximize prot in a local soap production company and recommended increased production of white soap due to its higher protability.

   Despite the widespread use of linear programming, many existing studies primarily focus on obtaining optimal solutions without adequately exploring the broader implications of these solutions. Several works rely on deterministic models that assume xed input parameters, thereby ignoring real-world uncertainties such as uctuations in raw material availability, market demand, and production costs. Additionally, many studies emphasize methodolog-ical application without providing sucient interpretation of results in a business context, limiting their practical usefulness for decision-makers.

   Furthermore, while prior research has extensively applied linear programming to manufac-turing and agricultural systems, relatively fewer studies have focused on small-scale bakery operations, particularly in developing economies. Such enterprises often operate under sig-nicant resource constraints and informal decision-making processes, making them ideal can-didates for the application of optimization techniques. However, there remains a gap in the literature regarding the integration of linear programming models into the decision-making frameworks of these businesses.

   This study seeks to address these gaps by applying linear programming to a real-world bakery production problem. Unlike many previous studies that emphasize theoretical applications, this research focuses on a practical case study and provides a detailed interpretation of the results in the context of business decision-making. By doing so, it contributes to the growing body of literature on the application of optimization techniques in small and medium-scale enterprises and demonstrates how linear programming can be eectively utilized to enhance protability and operational eciency.

   In conclusion, the literature demonstrates that linear programming is a powerful tool for prot maximization across various industries and sectors. Its ability to optimize complex decision-making processes while considering multiple constraints makes it a valuable tech-nique for organizations seeking to improve operational eciency and protability.

3. Methodology

   This section presents the mathematical formulation of the linear programming model used to determine the optimal production strategy for Seth Kojos (S.K) Bakery. The method-ology involves dening decision variables, constructing the objective function, specifying constraints based on available resources, and solving the model using the simplex algorithm.

   1. Model Formulation

      The problem is formulated as a linear programming model in which the goal is to maximize total prot subject to resource constraints. The formulation consists of decision variables, an objective function, and a set of linear constraints.

      1. Decision Variables

         Let

         x1 = number of loaves of banana bread produced per month, (1) x2 = number of loaves of coconut bread produced per month, (2) x3 = number of loaves of wheat bread produced per month, (3) x4 = number of loaves of butter bread produced per month. (4)

      2. Objective Function

         The objective is to maximize total monthly prot generated from the production of the four types of bread. Based on the prot contribution per unit of each product, the objective function is given by:

         Maximize Z = 200×1 + 125×2 + 350×3 + 560×4. (5)

      3. Constraints

         The production process is subject to limitations in the availability of raw materials. Each type of bread requires specic quantities of ingredients, and the total consumption must not exceed the available supply. The constraints are expressed as follows:

         Flour Constraint

         400×1 + 250×2 + 400×3 + 450×4 428600. (6)

         Milk Constraint

         30×1 + 40×2 + 5×3 + 10×4 9595. (7)

         Butter Constraint

         20×1 + 15×2 + 10×3 + 70×4 29510. (8)

         Flavour Constraint

         70×1 + 40×2 + 90×3 + 10×4 66720. (9)

         Vegetable Oil Constraint

         10×1 + 30×2 + 20×3 + 15×4 18010. (10)

         Baking Powder Constraint

         5×1 + 35×2 + 20×3 + 10×4 15925. (11)

         Salt Constraint

         20×1 + 25×2 + 10×3 + 15×4 13010. (12)

         Sugar Constraint

         30×1 + 10×2 + 20×3 + 5×4 17350. (13)

         Yeast Constraint

         25×1 + 20×2 + 10×3 + 50×4 24095. (14)

         Water Constraint

         70×1 + 90×2 + 30×3 + 50×4 41700. (15)

         Egg Constraint

         20×1 + 30×2 + 40×3 + 10×4 30020. (16)

      4. Non-negativity Constraints

         All decision variables must be non-negative:

         x1, x2, x3, x4 0. (17)

         Table 1: Resource Requirements and Availability

         Resource	Banana(x1)	Coconut(x2)	Wheat(x3)	Butter(x4)	Availability(g)
         Flour	400	250	400	450	428,600
         Milk	30	40	5	10	9,595
         Butter	20	15	10	70	29,510
         Flavour	70	40	90	10	66,720
         Vegetable Oil	10	30	20	15	18,010
         Baking Powder	5	35	20	10	15,925
         Salt	20	25	10	15	13,010
         Sugar	30	10	20	5	17,350
         Yeast	25	20	10	50	24,095
         Water	70	90	30	50	41,700
         Egg	20	30	40	10	30,020

   2. Solution Method

      The formulated linear programming model is solved using the simplex algorithm, a well-established iterative procedure for determining the optimal solution to linear optimization problems. Due to the presence of multiple decision variables and constraints, the simplex mehod is more appropriate than graphical approaches.

      In this study, the model is implemented and solved using the linprog function in MATLAB, which provides an ecient computational framework for linear optimization. The linprog function applies the simplex algorithm to evaluate feasible solutions and identify the optimal production levels that maximize the objective function while satisfying all constraints.

   3. Model Assumptions

      The formulation of the linear programming model is based on the following assumptions:

      • Linearity: Both the objective function and constraints are linear in terms of the decision variables.

      • Divisibility: The decision variables can take any non-negative real values, implying that production quantities are continuous.

      • Certainty: All coecients in the model, including prot contributions and resource availability, are known with certainty and remain constant during the planning period.

      • Non-negativity: Negative production levels are not feasible.

4. Results and Discussion

   1. Optimal Solution

      The model is solved using the linprog function in MATLAB, which implements the simplex algorithm for linear optimization problems.

      The optimal production quantities obtained are as follows:

      x1 = 117 (banana bread), (18)

      x2 = 0 (coconut bread), (19)

      x3 = 617 (wheat bread), (20)

      x4 = 300 (butter bread). (21) The corresponding maximum monthly prot is:

      Z = 407,350. (22)

   2. Interpretation of Results

      The results indicate that wheat bread (x3) and butter bread (x4) constitute the most sig-nicant portion of the optimal production mix. In particular, wheat bread has the highest production quantity, suggesting that it provides a strong balance between resource consump-tion and prot contribution.

      Butter bread, despite its relatively high consumption of certain resources such as butter, is also produced in substantial quantities due to its high unit prot. This highlights its impor-tance as a key driver of protability for the bakery.

      Table 2: Prot Contribution per Product

      Product	Unit Prot (GH¢)	Quantity	Total Prot
      Banana Bread	200	117	23,400
      Coconut Bread	125	0	0
      Wheat Bread	350	617	215,950
      Butter Bread	560	300	168,000
      Total			407,350

      On the other hand, coconut bread (x2) is not included in the optimal solution. This implies that its production is not economically viable under the current resource constraints and prot structure. In other words, the resources required to produce coconut bread can be more protably allocated to other products.

      Banana bread (x1) is produced in moderate quantities, indicating that while it contributes positively to prot, it is less ecient compared to wheat and butter bread in terms of resource utilization.

   3. Resource Utilization and Constraints

      The optimal solution reects the ecient allocation of limited resources. Although detailed slack values are not explicitly presented, it can be inferred that some constraints are binding, meaning that the available quantities of certain resources are fully utilized in the optimal solution.

      Resources that are heavily consumed in the production of wheat and butter bread, such as butter, avour, and baking powder, are binding constraints. These resources therefore play a critical role in limiting further increases in production and prot.

      Non-binding constraints, on the other hand, represent resources that are not fully utilized. These unused resources suggest potential ineciencies or opportunities for increasing pro-duction if other limiting factors are addressed.

   4. Managerial Implications

      The ndings of this study provide important insights for decision-making at Seth Kojos Bakery. First, management should prioritize the production of wheat and butter bread, as

      these products contribute most signicantly to overall protability.

      Second, the complete exclusion of coconut bread from the optimal solution suggests that the bakery should reconsider its production strategy for this product. This may involve reducing its production, improving its eciency, or adjusting its pricing strategy to enhance protability.

      Furthermore, the identication of binding constraints highlights the need for strategic in-vestment in critical resources. For example, increasing the availability of key inputs such as our or butter could enable the bakery to expand production and achieve higher prot levels.

      Overall, the results demonstrate that the application of linear programming provides a sys-tematic and eective approach to optimizing production decisions and improving operational performance in small-scale enterprises.

5. Sensitivity Analysis

   Sensitivity analysis evaluates how changes in resource availability and prot coecients aect the optimal solution. This section presents shadow prices, reduced costs, binding constraints, and managerial implications based on the MATLAB output.

   1. Binding and Non-Binding Constraints

      A constraint is binding if its left-hand side equals its right-hand side at optimality, meaning the resource is fully utilized. A non-binding constraint has slack, indicating unused capacity. Based on the MATLAB solution, the following constraints are binding:

      • Constraint 3 (Butter)

      • Constraint 4 (Flavour)

      • Constraint 6 (Baking Powder)

      These constraints have zero slack and directly restrict further increases in production. All other constraints exhibit positive slack and are therefore non-binding.

   2. Shadow Prices

      Shadow prices represent the marginal increase in prot resulting from a one-unit increase in the availability of a resource.

      The MATLAB output indicates:

      • Constraint 6 (Baking Powder): Shadow price 13.7973 (most critical resource).

      • Constraint 3 (Butter): Shadow price 6.0068 (major bottleneck).

      • Constraint 4 (Flavour): Shadow price 0.1554 (weakly binding).

      All other constraints have shadow prices of zero, conrming they are non-binding.

      Table 3: Shadow Prices for Resource Constraints

      Constraint	Shadow Price	Interpretation
      1	0	Not binding (no impact on prot)
      2	0	Not binding (no impact on prot)
      3	6.0068	Highly binding (prot increases signicantly)
      4	0.1554	Weakly binding (small impact on prot)
      5	0	Not binding
      6	13.7973	Most critical constraint (highest impact)
      7	0	Not binding
      8	0	Not binding
      9	0	Not binding
      10	0
      11	0	Not binding

   3. Reduced Costs

      Reduced costs indicate how much the objective coecient of a non-produced variable must improve before it becomes protable to include in the solution.

      The reduced cost of coconut bread conrms that it is excluded from the optimal solution because its current prot contribution (GH¢125) is insucient relative to its resource con-sumption. To enter the optimal basis, its unit prot must increase or its ingredient usage must decrease.

   4. Allowable Ranges

      For binding constraints (3, 4, and 6), shadow prices remain valid within the allowable range of the right-hand side. For non-binding constraints, allowable increases are eectively un-bounded until the constraint becomes binding.

      Thus:

      • Increasing our, milk, sugar, yeast, or water will not aect prot unless the increase is large enough to make these constraints binding.

      • Increasing butter, avour, or baking powder will immediately increase prot.

   5. Managerial Implications

      • Invest in baking powder and butter rst, as these yield the highest marginal returns.

      • Flavour is a weak bottleneck but still worth expanding if inexpensive.

      • Coconut bread should not be produced unless its prot margin improves or its recipe is reformulated.

      • Non-binding resources represent slack, indicating potential over-purchasing relative to optimal production needs.

   6. Summary

      The sensitivity analysis conrms that the optimal solution is stable and identies the key resources limiting protability. These insights strengthen the practical relevance of the model and guide strategic investment decisions for the bakery.

      The results indicate that Constraints 3, 4, and 6 are binding and directly inuence the optimal solution. In particular, Constraint 6 has the highest shadow price, making it the most critical resource. Increasing its availability would yield the greatest increase in prot. All other constraints have zero shadow prices, indicating that they are non-binding and do not limit production under the current solution.

6. Conclusion

   This study applied linear programming techniques to determine the optimal production strategy for Seth Kojos (S.K) Bakery under multiple resource constraints. The objective was to maximize prot by identifying the most ecient combination of products given the available inputs.

   The results revealed that the optimal production mix consists of 117 units of banana bread, 617 units of wheat bread, and 300 units of butter bread, while coconut bread is excluded from production. This combination yields a maximum monthly prot of 407,350, demonstrating the eectiveness of linear programming as a decision-support tool.

   The ndings further indicate that wheat and butter bread contribute most signicantly to protability, while coconut bread is not economically viable under current conditions. This highlights the importance of ecient resource allocation and product prioritization in maximizing returns.

   Overall, the study demonstrates that linear programming provides a systematic and reliable framework for optimizing production decisions in small-scale enterprises. Its application enables managers to make informed decisions, improve operational eciency, and enhance protability.

7. Recommendations

Based on the ndings of this study, the following recommendations are proposed.

• The bakery should prioritize the production of wheat and butter bread, as these prod-ucts contribute signicantly to overall prot.

• Management should reconsider the production of coconut bread. This may involve reducing its cost of production, improving its eciency, or adjusting its pricing strategy to make it more competitive.

• The bakery should invest in increasing the availability of critical resources such as our and butter, as these are likely limiting factors in production.

• The use of optimization tools such as linear programming should be integrated into routine decision-making processes to enhance planning and resource allocation.

• Future studies should incorporate uncertainty factors such as uctuating demand and variable input costs to develop more robust and realistic models.

1. Contribution of the Study

   This study makes several contributions to the literature on production optimization and the application of linear programming in small and medium-scale enterprises:

   1. Real-world, data-driven optimization model. Unlike many LP studies that rely on hypothetical datasets, this work uses actual ingredient usage and production infor-mation from Seth Kojos Bakery. This provides an empirically grounded demonstra-tion of how optimization can support decision-making in resource-constrained environ-ments.

   2. Integration of LP with sensitivity analysis. Beyond identifying an optimal prod-uct mix, the study incorporates shadow prices, reduced costs, and binding-constraint identication. This level of interpretive depth is rarely included in SME-focused LP studies.

   3. Managerial insights tailored to small-scale food production. The results trans-late mathematical outputs into actionable recommendations, such as prioritizing wheat and butter bread, reconsidering coconut bread, and investing in critical inputs like our and butter.

   4. Advancing quantitative decision-support for SMEs in developing economies. The study highlights how small enterprises often operating with informal planning methods can benet from structured optimization techniques. This contributes to the growing literature advocating quantitative tools for improving eciency and protabil-ity in developing-country contexts.

Together, these contributions position the study as both academically relevant and practi-cally impactful, oering a replicable framework for similar enterprises seeking to optimize production under resource constraints.

References

1. J. Mula, R. Garcia-Sabater, and F. Lario, Models for production planning under un-certainty, International Journal of Production Economics, 2005.

2. Veli Ulu¸cam, Aggregate production planning model based on mixed integer linear pro-gramming, European Journal of Industrial Engineering, 2010.

3. C. D. Miller, Linear Programming and Its Applications. McGraw-Hill, 2007.

4. A. Stephanos and B. Dimitrios, Linear programming and prot maximization, Inter-national Journal of Business Optimization, 2010.

5. A. Maryam et al., Linear programming and management decision improvement, In-ternational Journal of Applied Management Science, 2013.

6. O. S. Balogun, E. T. Jolayemi, T. J. Akingbade, and H. G. Muazu, Use of linear pro-gramming for optimal production in a production line in coca-cola bottling company, International Journal of Engineering Research and Application, vol. 2, 2012.

7. B. I. Ezema and O. Amaken, Optimizing prot with the linear programming model: A focus on golden plastic industry limited, Interdisciplinary Journal of Research in Business, vol. 2, 2012.

8. M. Snezanza and B. Milorad, Linear programmin applications in energy manage-ment, Energy Systems Journal, 2009.

9. I. S. Fagoynbo and I. A. Ajibode, Application of linear programming techniques to eective resource utilization, Journal of Management and Decision Making, 2010.

10. K. C. Igwe, C. E. Onyenweaku, and J. C. Nwaru, Application of linear programming to semi-commercial agriculture, International Journal of Economics and Management Sciences, vol. 1, 2011.

11. F. Majeka, Incorporating crop rotation requirements in a linear programming model,

    International Researchers, vol. 2, 2013.

12. E. M. Igbinehi, A. O. Oyebode, and F. A. Taofeek-Ibrahim, Application of linear programming in manufacturing of local soap, International Journal of Management, 2015.

13. W. B. Yahya, M. K. Garba, S. O. Ige, and A. E. Adeyosoye, Prot maximization in a product mix company using linear programming, European Journal of Business and Management, vol. 4, no. 17, pp. 126131, 2012.

14. M. Joly, Optimization in high-performance reneries, Journal of Petroleum Optimiza-tion, 2012.

A MATLAB Code

The following MATLAB code was used to solve the linear programming model:

% Objective function

f = [-200; -125; -350; -560];

% Constraint matrix A = [

400 250 400 450;

% RHS

b = [ 428600;

9595;

29510;

66720;

18010;

15925;

13010;

17350;

24095;

41700;

30020

];

lb = [0; 0; 0; 0];

x

-fval lambda.ineqlin

…