Hi, it's Sir Rob. Today I'm going to talk about linear programming, also called linear optimization, and solving problems using linear programming. Linear programming is a method to achieve the best outcome, such as maximize profit or lower the cost, in a mathematical model whose Requirements are represented by linear relationships. As always, in the practice of financial management, we should remember to be professional, perform effectively and efficiently, follow standards, and document our work adequately and properly. Topics in this discussion include, 1. The definition of linear programming, and 2. We will look at The common terminology is used in linear programming like decision variables and objective function.
And also we will take a look at the areas where linear programming may be practically applied. And lastly, we will look at the same real-life problems and how to solve them using linear programming. Off to our first topic, what is linear programming?
Optimization is a way of life. According to vocabulary.com, optimization means to make the best use of something. If you optimize your home storage capacity, you clean and organize your closets and drawers to be able to fit the most in.
In a more technical sense, optimization methods are used in many areas of study to find solutions. that maximize or minimize some study parameters or problems such as minimize costs in the production of a goods or delivery of a service maximize profits minimize raw materials in a development of a good or maximize production we all have finite resources and time we want to make the most of them From using your time productively to solving supply chain problems for a company, everything uses optimization. It is also a very interesting topic.
It starts with simple problems, but it can get very complex. For example, sharing a bar of chocolate between siblings is a simple optimization problem. We don't think in mathematical terms in solving it.
who gets the bigger chunk of the chocolate and who gets a smaller piece depends not so much on mathematical models but maybe on a biological psychological or emotional factor on the other hand devising inventory and warehousing strategies for an e-tailer like amazon or the e-tailers that have Stores in Shopee or Lazada can be very complex. Millions of storekeeping units or SKUs with varying demand levels in different locations to be delivered in defined time and resources. Linear programming is a simple technique where we depict complex relationships through linear functions and then...
find the optimum points the important word in the previous sentence is depict or represent in its visual context and representation as seen on the slide the variables are represented by straight lines hence the word linear the optimum points are where the lines intersect And that is how to simplify the relationship between elements. The real relationships might be much more complex, but we just simplified them to linear relationships to find a linear or simple solution. Later when we are doing the activities, you will better understand this idea.
Linear programming is one of the simplest ways to perform optimization in operations. It helps entities solve some very complex linear optimization problems by making a few simplifying assumptions. Applications of linear programming are everywhere around us. Use linear programming at personal and professional fronts.
People are using linear programming when driving from one point to another, for example, home to work and want to take the shortest route. Optimization apps like Google Map or Waze are available to provide the solution to the problem of how to get to our destination in the shortest possible time. considering our origin, destination, traffic along segments of the route, and even the method of how you want to get there by foot, bicycle, or a four-wheeled vehicle.
Optimization is also employed when a team has a project delivery and makes strategies to make their team work efficiently for on-time delivery. Applications also include production scheduling, inventory policies, allocation of advertising budget, construction of warehouses, and so on. As financial management students, you might be interested to know that you can also apply linear programming in determining the optimal portfolio mix and also determining who you will grant the loans to, assuming that you have an available budget for loans. As human resource students, there are a lot of manpower problems that you can solve using linear programming, like determining the best route that the delivery personnel on various types of vehicles can take to maximize their time and minimize fuel consumption, like what they're doing in UPS or the Universal Parcel Service. Also, you can use linear programming when determining the number of personnel to hire for the production department or any other department in a organization or finding the optimum number of police and police cars to go on patrol in some location at specific shifts of the day let us look at one theoretical problem that is solvable using linear programming let's say a jnt delivery rider has six packages left To deliver in a day, the warehouse or depot is located at Bantai.
The six delivery destinations are as shown on the slide. The numbers on the lines indicate the time in minutes it takes to go from one destination to another. To save on fuel and time, the delivery person wants to take the shortest route.
And let's say he has an hour left before he calls it a day. So the JNT delivery rider will calculate different routes for going to all of the six destinations and then come up with the shortest route within the allotted time. In this case, the objective of the delivery person is to deliver the parcel on time at all six destinations within the hour left.
This process of choosing the best route is called the delivery model. Is the linear representation of the six points above representative of the real world yes and no it is an oversimplification as the real route would not be a straight line it would likely have multiple turns even new turns and traffic jams especially when the travel time is during rush hour But with a simple assumption, we have reduced the complexity of the problem drastically and are creating a solution that should work in most scenarios. Let's look at another simpler example.
Say, a chocolate factory, which we will call Wonka, manufactures only two types of chocolate, the dark variety and the light variety. Both the chocolates require milk and choco only the ingredients to manufacture each unit of dark and light chocolate the following quantities are required each unit of dark chocolate bar requires one unit of milk and three units of choco each unit of light chocolate bar requires one unit of milk and two units of choco The factory, let's say, has a total of 5 million units of milk and 12 million units of chocolate. On each sale, the company makes a profit of 6 pesos per unit of dark chocolate bars sold and 5 pesos per unit of light chocolate bars sold. Now the company wishes to maximize its profit.
How many units of dark and light chocolate should the factory produce respectively? Before we solve the problem, let us first discuss the common terminologies in linear programming using the chocolate problem as our Remember, Reference. The first term is decision variables.
We have to identify them foremost as they are the ultimate decision factors. In research, we call them the independent variables. In a linear program, the variables are a set of quantities to be determined for solving the problem. That is, the problem is solved when the best values of the variables have been identified.
the variables are called decision variables because the problem is to decide what value each variable should take usually the variables represent the amount of a resource to use or the level of some activity in our example the total number of chocolate bars an amount for the light over the dark and light varieties are the decision variables The second term is objective function. It is defined as a means to maximize or minimize something. This something is a numeric value.
In the real world, it could be the cost of a project, a production quantity, a profit value like our problem, or even materials saved from a streamlined process. With the objective function, you are trying to arrive at a target for output, profit, resource use, etc. In our example, the chocolate factory wishes to maximize the total profit.
So the maximum profit is our objective function. The third term is constraint. The constraints are the restrictions or limitations on the decision variables. Thanks for watching. usually limit the value of the decision variables.
For example, a cost constraint means that you're limited to a specific project budget, while a manpower constraint means that you're limited to a number of people who could work on a project. A universal constraint that all organizations and individuals possess is time. We are all given an equal amount of it. 24 hours a day.
However, we divide this time amongst the different activities that we plan to do. Most project constraints impact one another, which is why constraint management is crucial for project success. In the above example, the limit on the availability of resources, the ingredients, which are chocolate and milk, are our constraints. The last term is non-negativity restriction.
For all linear problems, the decision variable should always take non-negative values. This means that the values for decision variable should be greater than or equal to zero. Now, let's try to solve our linear problem of the dark chocolate and the light chocolate production.
How many units of each type of chocolate bar should we produce to maximize our profit? First, let us represent the problem in a tabular form for better understanding. The table shows the same problem in a data matrix. I have also named the decision variables as x and y and the objective function as z.
however you can use any letter or any character you want use ones that are comfortable to you so let the total number of units of dark chocolate bars produced be x and let the total number of units of light chocolate bars produced be y now let the unknown total profit be z which is the total profit the company makes from the total number of units of X and Y produced multiplied by their per unit profit of six and five passes respectively. Thus in a mathematical Equation the objective function can be written as Max Z equals 6x plus 5y Which means we have to maximize Z from the individual profits of both X and Y The company will try to produce as many units of X and Y to maximize profit But the resources built and Choco are available in a limited amount as for the above table each unit of x and y requires one unit of milk the total amount of milk available is 5 million units to represent this mathematically x plus y is greater than or equal to 5 the numerical coefficient understood to be 1. Also, each unit of X and Y requires 3 units and 2 units of Choco respectively. The total amount of Choco available is 12 million units. To represent this mathematically, we say 3X plus 2Y is greater than or equal to 12. Lastly, the values for units of x and y can only be integers. So we have two more constraints.
x is greater than or equal to 0 and y is greater than or equal to 0. For the company to make maximum profit, the above inequalities have to be satisfied. What we have just done is formulating a real-world problem into a mathematical model. Now let's try to solve the linear programming problem.
A linear problem can be solved by multiple methods. In this section, we are going to look at the graphical method for solving a linear problem. This method is used to solve a two-variable linear problem to find the optimal solution. A graphical method involves formulating a set of linear inequalities subject to the constraint. Then, the inequalities are plotted on an x-y plane.
Once we have plotted all the inequalities on a graph, the intersection region gives us a feasible region. The feasible region explains what all values our model can take. and it also gives us the best solution. Let's apply this technique, the graphical technique, to solve our chocolate bar problem. First, let's plot the X and Y axis.
These will represent variables for our dark and light chocolate bar products. Next, we plot the minimum demand for each product. The problem is silent so we assume one for each and mark the intersection with a dot now we plot the constraints which are the units available for each ingredient first we plot milk the available units for milk is 5 million if we used all the milk ingredients and made 5 million dark chocolate bars how many light chocolate bars can we make? Zero. None.
So we plot that point along the x-axis as shown on the slide. Conversely if we use all the milk ingredients and made five light chocolate bars, how many light chocolate bars can we make? None. So we plot that point along the y-axis as shown on the slide. Then we connect the two dots together forming a straight line.
Next we plot the ingredient Choco. The available units for Choco is 12 million. If we use all the Choco ingredients and made just dark chocolate bars, how many chocolate bars can we make?
To make a unit of dark chocolate bar, we need three units of the ingredients Choco. Divide 12 by 3 and we get 4. So we can make 4 million units of dark chocolate bars if we used all the chocolate ingredients. And there will be none. left for making light chocolate bars so we plot for zero along the x-axis if we used all the chocolate ingredients and made just light chocolate bars how many chocolate bars can we make to make a bar of light chocolate we need two units of the ingredients chocolate divide 12 by 2 and we get 6 so we can make 6 million light chocolate bars if we use all the chocolate ingredients and there will be none left for making dark chocolate bars so we plot along the y-axis again we connect the two dots together forming a straight line now notice the area now bounded by the constraints This is the visible region. In mathematical equation, a visible region, also called visible set, search space, or solution space, is the set of all possible points, sets of values of the choice variables of an optimization problem that satisfy the problem's constraints.
In a linear programming problem, a series of linear constraints produce a convex visible region of possible values for those variables in the two variable case this region is the shape is in the shape of a convex simple polygon in our visible region we have eight vertices that represent possible mixes of dark and light chocolate bars that satisfy the constraints. But we will focus our attention on the vertices where the lines meet. These are 1, 1, 3, 1, 2, 3, and 1, 4. Vertex will of course yield the least profit among the four vertices because it did not maximize use of the available ingredients and selling just one of its chocolate bars will yield only 11 million pesos in profit So let's narrow down our focus further to the three remaining vertices or mixes What combination will give us the maximum profit and our goal is not to minimize but to maximize profit First let's use the mix or coordinate or vertex 1,4 which is 1 dark and 4 light chocolate bars.
Substituting for the equation we have 6x will become 6 times 1 which is equal to 6 and 5y will become 5 times 4 which is equal to 20. We add... 6 and 20 and we get a total profit of 26 million pesos let's say the sale is in million of pesos thus we get 26 million profit now let's use the mix 2 3 which is 2 dark and 3 light chocolate bars substituting for the equation we have 6x will become 6 times 2 which is equal to 12 and 5y will become 5 times 3 which is equal to 15. We add 12 and 15 together and we get a total profit of 27 million. A million peso higher than the previous. We still have one last remaining optimal point to consider though. Lastly, let's use the mix 3, 1. which is 3 dark and 1 light chocolate bars.
We have 6x will become 6 times 3 which is equal to 18 and 5y will become 5 times 1 which is equal to 5. We add 18 and 5 together and we get a total profit of 23 million. The least profit yield Among the three optimal points. Thus the solution to our problem Which is maximizing profit using available units to produce a mix of two products and satisfying all Constraints is producing two million dark chocolate bars and three million light chocolate bars. There it is chapter two linear programming the next This problem will be assigned to you to solve in graphical method after you have watched this video. After the graphical method, we will use MS Excel to solve the same linear programming problems.
Listed on the slide are the references used in the production of this topic discussion video, including the online references. Also be sure to check out and watch the supplementary videos accessible from the group chat. Thank you and stay safe always.