{"id":13736,"date":"2022-01-13T16:44:00","date_gmt":"2022-01-13T11:14:00","guid":{"rendered":"https:\/\/www.mygreatlearning.com\/blog\/introduction-to-linear-programming-for-data-science\/"},"modified":"2024-05-06T23:03:16","modified_gmt":"2024-05-06T17:33:16","slug":"introduction-to-linear-programming-for-data-science","status":"publish","type":"post","link":"https:\/\/www.mygreatlearning.com\/blog\/introduction-to-linear-programming-for-data-science\/","title":{"rendered":"Introduction to Linear Programming for Data Science"},"content":{"rendered":"\n

Contributed by: Sarita Upadhya
LinkedIn Profile: https:\/\/www.linkedin.com\/in\/sarita-upadhya-a7b94922\/ <\/a><\/p>\n\n\n\n

Introduction<\/strong><\/h2>\n\n\n\n

Data Science helps businesses to make informed and data-driven decisions. Current business situations or business scenarios can be explored further using available data, and better insights can be drawn using Descriptive Analytics. Using past data, we can predict the future. Also, the cause and effect relationship between predictors and response variables can be extracted using Predictive Analytics. Predictive models are also used to simulate a future probable outcome by changing and assigning values of the predictors. As a part of Prescriptive Analytics, business starts looking at the different alternatives available to finalise the decision. Along with the available insights, resource constraints are taken into account to get an optimum solution.<\/p>\n\n\n\n

Linear Programming (LP) in Operations Research is one of the scientific techniques that is used to get an optimum solution to the given business problem by taking resource scarcity and constraints into account. When decision making pertains to a continuous variable like sales, profit, cost etc. which has a linear relationship with several input variables, Linear Programming is applied to take into account the limitations or constraints associated, and arrive at the best solution. For e.g. if a business wants to maximise sales, there may be a constraint in terms of the quantum of product available for sale; the business may want to maximise the profit by increasing the production however may have a constraint in terms of the capacity of machines etc. LP provides an approach to the above problems to get an optimum solution by considering the constraints.<\/p>\n\n\n\n

Read More - What is Data Science?<\/a><\/p>\n\n\n\n

LP Application Requirements<\/strong><\/h2>\n\n\n\n

In order to apply Linear Programming for Data Science<\/a>, the below requirements have to be met:<\/p>\n\n\n\n

  1. We should be able to define the objective or the aim clearly in mathematical terms. <\/li>
  2. The input variables that determine the objective should be distinct and quantitative. <\/li>
  3. Limitations or constraints that have to be considered should be quantitative and measurable.<\/li>
  4. Relationship between the objective and the input variables has to be linear in nature.<\/li><\/ol>\n\n\n\n

    Formulation of LP Problems<\/strong><\/h2>\n\n\n\n

    Below are the steps to be followed to formulate LP Problem:<\/p>\n\n\n\n

    1. Identify the decision variables that are used to formulate and achieve the objective function<\/li>
    2. Define the objective function: It defines the business objective in mathematical form<\/li>
    3. List out the constraints or limitations using the decision variables in mathematical form<\/li>
    4. Identify and list out the non-negative constraints <\/li><\/ol>\n\n\n\n

      Let\u2019s understand this with a few examples. Also, we will look at the 3 tools (Graphical method, Excel Solver, R) which can be used to solve LP problems.<\/p>\n\n\n\n

      Linear Programming Examples<\/strong><\/h2>\n\n\n\n

      Here are the Linear Programming Examples:<\/p>\n\n\n\n

      Problem Statement 1<\/strong><\/h3>\n\n\n\n

      The XYZ company during the festival season combines two factors A and B to form a gift pack which must weigh 5 kg. At least 2 kg of A and not more than 4 kg of B should be used. The net profit contribution to the company is Rs. 5 per kg for A and Rs. 6 per kg for B. Formulate LP Model to find the optimal factor mix.<\/p>\n\n\n\n

      LP Formulation:<\/strong><\/h4>\n\n\n\n

      Step 1: Objective Function<\/strong><\/p>\n\n\n\n

      In the above problem, the objective of the company is to maximise the profit. We are given the net profit contribution for factor A and B.<\/p>\n\n\n\n

      • Let x kg of factor A be used<\/li>
      • Let y kg of factor B be used<\/li>
      • Objective Function \u2b04 maximise z = 5x + 6y<\/li><\/ul>\n\n\n\n

        Note: x, y are decision variables and z is the objective function<\/p>\n\n\n\n

        Step 2: Formulate the constraints<\/strong><\/p>\n\n\n\n

        \tWeight of gift pack has to be 5 kg<\/p>\n\n\n\n

        • x + y = 5<\/li><\/ul>\n\n\n\n

          At least 2 kg of A and not more than 4 kg of B has to be used<\/p>\n\n\n\n

          • x >= 2<\/li>
          • y <= 4<\/li><\/ul>\n\n\n\n

            Step 3: Non-negative constraints<\/strong><\/p>\n\n\n\n

            The quantity used for A and B has to be positive<\/p>\n\n\n\n

            • x, y >= 0<\/li><\/ul>\n\n\n\n

              Summarise the LP Problem:<\/strong><\/h4>\n\n\n\n

              Objective: Maximise z = 5x+6y given the constraints<\/p>\n\n\n\n

              1. x + y = 5<\/li>
              2. x >= 2<\/li>
              3. y <= 4<\/li>
              4. x, y >= 0<\/li><\/ol>\n\n\n\n

                Let\u2019s try and solve the above LP problem graphically
                <\/p>\n\n\n\n

                Graphical Solution:<\/strong><\/h4>\n\n\n\n

                Let us consider a 2-dimension graph with x and y-axis:<\/p>\n\n\n\n

                • Plot the constraints formulated in the above problem.
                  • x + y = 5 is a line that cuts x-axis at (5,0) and y-axis at (0,5). As we have a \u201c=\u201d constraint, the feasible region lies on this line.<\/li>
                  • x >= 2 is the line that cuts the x-axis at (2,0). As we have a \u201c>=\u201d constraint, the feasible region lies to the right of this line<\/li>
                  • y <= 4 is the line that cuts the y-axis at (0,4). As we have a \u201c<=\u201d constraint, the feasible region lies to the bottom of this line<\/li>
                  • As x, y >= 0 we have considered only the positive side of the x and y-axis.<\/li><\/ul><\/li>
                  • Combining all the above constraints, from the above graph the line marked in yellow is the final feasible region where all constraints are satisfied. <\/li>
                  • The 2 extreme points on this line are the possible options for consideration to maximise the profit i.e. point A (2,3) and point B (5,0). <\/li>
                  • Let us substitute these values in the objective function to find out which option gives higher profit.
                    • Option A (2,3): z = 5x + 6y \u2b04 z = (5*2) +(6*3) = 28<\/li>
                    • Option B (5,0): z = 5x + 6y \u2b04 z = (5*5) +(6*0) = 25<\/li><\/ul><\/li>
                    • Hence, the optimum solution is Option A i.e. 2kg of factor A and 3kg of factor B to be considered for the gift pack.<\/li><\/ul>\n\n\n\n
                      \n