7.1. Introduction to Linear Programming

So, the types of problems we looked at so far are largely optimization type of tasks. So, we are looking for shortest paths in a graph or we are trying to identify the minimum cost spanning tree or we are looking for the longest common subsequence. So, 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 then this optimization takes place subject to a constraint.

This chunk introduces the idea of optimization, which is about making the best possible decision within a set of defined parameters or rules, known as constraints. In the context of graph theory, optimization might involve finding the shortest path between two points or the least expensive way to connect various vertices in a graph. Each optimization problem is governed by constraints, which limit the possible solutions. For instance, if you are trying to find the shortest path in a city, the roads themselves serve as constraints on the paths you can take.

Imagine you are trying to plan a road trip with friends. You want to minimize travel time (optimization) while also ensuring you only use highways (constraint). Each route you consider will be influenced by the roads available, just like optimization problems are influenced by their constraints.

In linear programming, we are given some variables, some quantities that we want to calculate and then there are some linear functions that constrain these quantities. So, linear functions of a variable x is something of the form ax + b. If we have multiple variables x, y, z, then we could have a constraint of the form ax + by + something is less than or equal to some constant, or ax + by + something is greater than or equal to some constant.

This part explains how to formulate a linear programming problem mathematically. You start with variables (like x, y, z, etc.) that represent the quantities you want to optimize. Then, you define constraints that are represented by linear functions. A linear function connects the variables in a way that respects the limitations of the problem. For example, if you are trying to optimize the production of two products, 'x' might represent the number of product A produced and 'y' might represent the number of product B, with constraints determining how many of each can be produced.

Think of a bakery that produces cakes and cookies. Let 'x' be the number of cakes, and 'y' the number of cookies. The bakery can bake at most 50 items in total per day, leading to the constraint x + y ≤ 50. Here, the linear function represents the relationship between the quantities produced, and the constraint reflects the bakery's production capacity.

Suppose we are running a sweets shop called grandiose sweets and 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. On a given day, we cannot sell more than 200 barfi boxes and 300 halwa boxes, and together the staff can only produce 400 boxes.

Here, a practical example is presented to help illustrate linear programming in a real-world context. The sweets shop must determine how many boxes of each sweet to produce to maximize profit while adhering to sales and production limits. In this situation, barfis (b) and halwa (h) are variables, with constraints based on maximum sales and total production capacity.

Imagine a local bakery that can only bake a certain number of cupcakes and muffins each day due to oven space and ingredient availability. By calculating expected profits from each item, the bakery can use linear programming to decide how many batches of each to make to maximize profits while still respecting the constraints of their kitchen.

There is a feasible region, any point in this region represents a combination of b and h that satisfies all constraints. We can visualize this by determining the boundaries represented by the constraints, leading to a closed area where solutions can be found.

The concept of a feasible region is central to understanding linear programming. The feasible region is essentially the set of all possible solutions that meet the constraints outlined. By graphing the constraints, we can see where the feasible region lies on a coordinate plane, helping us identify potential solutions that optimize our objective function.

Think of a property line where a homeowner can plant flowers. The garden has boundaries set by the property line (constraints) and within this space, the homeowner is free to design the garden however they wish (feasible region). The area inside this boundary is where all allowed garden designs will be and represents potential solutions for the layout.

The optimal value will always occur at a vertex of the feasible region. The simplex algorithm finds the optimal value by navigating through the vertices of the feasible area to identify the best outcome based on the objective function.

This chunk discusses the process of finding the optimal solution in linear programming. When the objective function is graphed against the constraints, it will touch the feasible region's edges, or vertices. The simplex algorithm incrementally examines these vertices, moving to an adjacent vertex if it identifies a better outcome until it reaches the vertex that provides the highest or lowest value, depending on the goal.

Imagine a hiker trying to reach the highest point on a mountain only navigating the rocky edges and peaks (vertices), rather than traveling through the valleys. The fasted route is likely to follow the peaks while testing each to find the highest one – in much the same way, the simplex method tests vertices to find the optimal function outcome.

--