Linear programming problem formulation and solution using benders’ decomposition method

Abstract

In this thesis, a large scale linear programming problem consisting several parameters such as labor cost, raw material cost, machine and other cost have been formulated. Then the formulated problem has been solved by using Benders’ Decomposition Method. In order to validate and calibrate the model, real data from a soap industry named MEGA SORNALI SOAP & COSMETICS INDUSTRY have been collected. Soap industry is one of the most feasible business options owing to the straightforward manufacturing process involved starting a soap and detergent manufacturing business in Bangladesh. With significant growth potential, this market is one segment of the Fast Moving Consumer Goods (FMCG) market in Bangladesh. People use it on daily basis for clothes, hand wash, and kitchen utensils and its demand is found in the market all through the year. The formulated large model is divided into master and small sub problem. These models are solved by using a Mathematical Programming Language (AMPL). In order to validate the model, the sensitivity analysis of different cost parameters such as labor cost, raw material cost and machine cost will be considered. From the sensitivity analysis, the decision makers of the factory will be able to find out the ranges of cost coefficients and all the resources. As a result, they will be able to see how any change can affect the profit or loss of the factory. From the numerical results, it is clear that Mega SornaliSobiMarka Soap and Mega Washing Powder (25g) are not more profitable. The most profitable product of the company are found to be Sornali Soap (2015) and Mega Extra Powder (500g). Further, it is clear that raw material cost is the most sensitive cost. If the raw material cost can be decreased the profit will also increase. Finally, the result of the optimal solution will be represented in tabular form in addition to the graphs.