7. Linear Programming

The last week of this course, we looked at some advance topics. So let us begin with Linear Programming. So, the types of problems we are looking at so far are largely optimization type tasks. We are trying to optimize and quantify the length of the path or the cost of the tree or the length of the subsequence, and this optimization takes place subject to a constraint.

Linear Programming (LP) is a method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. This section starts by emphasizing the importance of optimization in fields like graphs and sequences, where we are often seeking the shortest path or the least cost. These optimization problems are subject to constraints, such as the limitations of the graph's edges in a path or the availability of resources in other contexts.

Imagine you're planning a road trip. You want to take the shortest path between cities while also considering factors like fuel limits (constraints) and your total travel budget. Linear programming effectively helps in making these types of decisions by formalizing the constraints and optimizing the overall journey.

In general, if we have multiple variables x, y, z, we could have a constraint of the form a x + b y + something is less than or equal to some constant or a x + b y + something is greater than or equal to some constant. These are the constraints on the values that the variables can take.

In LP, we define constraints that restrict the possible values of the variables. These constraints can take the form of inequalities involving linear functions of the variables (e.g., ax + by ≤ c). This means that the variables cannot just be anything; they must satisfy these mathematical conditions which reflect real-world limitations, such as resource availability.

Think of constraints as the budget for your shopping. If you have allocated a fixed amount of money to buy groceries, you cannot spend more than that amount (e.g., spending no more than $50). Constraints in linear programming function similarly by limiting the possible values of your decision variables.

Our aim is to optimize some quantity, whether we want to minimize or maximize some cost or weights, and that quantity is expressed in terms of the variable by yet another linear function.

In linear programming, the objective function is the function that we want to maximize or minimize. This function is typically represented as a linear combination of the decision variables. In the previous example, our goal might be to maximize profits based on the production quantities of different items. Properly formulating this objective function is critical as it directly influences the optimal solution we are seeking.

Imagine you're running a lemonade stand. Your goal is to maximize your profit based on how many cups of lemonade you sell. If you earn $2 per cup, your objective function would be to calculate 2 times the number of cups sold. Using LP, you would determine how many cups to prepare to reach maximum profit given your constraints of supplies and time.

Suppose we are running a sweets shop called Grandiose Sweets. We sell two types of sweets, barfis and halwa. Each box of barfis earns a profit of 100 rupees, and each box of halwa earns a profit of 600 rupees. Given constraints on maximum production, the question becomes what combination of barfis and halwa should we make.

In this example, we start by identifying the decision variables — the number of boxes of barfis (b) and halwa (h) we want to produce. Moreover, we have constraints stating that we cannot produce more than 200 barfis and 300 halwas, with a total limit of 400 boxes. Our goal is to maximize our profit given these constraints. By setting up inequalities and the objective function (maximizing profit = 100b + 600h), we can systematically explore the feasible solutions.

Think of this as planning your menu for a party. You want to prepare dishes (barfis and halwa) while keeping within limitations (guest preferences and overall preparation time). You want to serve the best mix to maximize satisfaction (profit), and you can calculate the best combination of each dish accordingly.

We can visualize this quite easily because there are two quantities (b and h) that we want to compute and a set of facts about them. This gives us a feasible region where any point represents a combination of b value and h value which meets all constraints.

The feasible region in linear programming refers to the set of all possible points (combinations of variables) that satisfy all the constraints simultaneously. This region can be graphed on a coordinate system, and it represents all the feasible solutions for the problem. Our optimal solution will lie somewhere within this feasible region, typically at one of the corners or boundaries of the defined space.

Consider a plot of land where you can set up a community garden. You have restrictions on how much space you can use for different plants (constraints). The area that fits within these restrictions is your feasible region where you can plant. Finding the best location (optimal solution) will help you maximize the plants you can grow.

The optimal value will generally occur at a vertex of the feasible region. The best way to find this value is through algorithms like the Simplex method, which explores the vertices of the feasible region to locate the maximum or minimum value.

When solving a linear programming problem graphically, the optimal solution can be found at the vertices of the feasible region. This is because as we evaluate the objective function, it will increase or decrease at the edges until it reaches its highest or lowest point at a vertex. The Simplex algorithm is a systematic approach that efficiently navigates these vertices to find the best solution.

Picture a hiker trying to find the highest peak in a mountainous landscape. The hiker explores different routes (vertices) and consistently checks the elevation (profit/optimal value) until they reach the summit (optimal solution). The Simplex method is like guiding the hiker to the best path efficiently.

--