8.1. Introduction to Linear Programming

Let us look at another example of modeling a problem using Linear Programming. Recall that a linear program is an optimization problem, where you have some variables which describe the quantities you want to compute. You now have linear constraints on these variables, as well as a linear function describing what it is that you want to optimize, maximize or minimize, that is called the objective function.

Linear programming is a mathematical method for determining how to achieve the best outcome in a given mathematical model. This model consists of variables, which are quantities we want to compute (like production levels), constraints (which limit these variables), and an objective function (the goal we want to maximize or minimize). For instance, in a production scenario, we may want to maximize profits while staying within budget or resource constraints.

Imagine you're planning a party and need to decide how many pizzas to order. Your goal is to order enough pizzas to feed everyone (maximizing satisfaction), but you have a strict budget (constraint). The number of pizzas you decide to order becomes your variable, while the expense of the pizzas serves as your constraint affecting your budget.

One way to solve a linear program is to think of it geometrically and use the simplex algorithm. The simplex algorithm exploits the fact that the optimum value of a linear program is always at the vertex of the feasible region. It starts at some vertex and keeps going from one vertex to a neighbor until it finds a vertex whose value is optimum.

The simplex algorithm is a method used to find the optimal solution to a linear programming problem. It works on the principle that the optimal value lies at one of the corner points (vertices) of the feasible region defined by the constraints. By evaluating the values of the objective function at these vertices and moving towards the direction of improvement, the algorithm eventually arrives at the best possible solution.

Think of a treasure map laid out on a grid with several points marked as possible treasure locations. If you start at a point (like the starting vertex) and move to nearby locations (neighboring vertices), checking if you are getting closer to the treasure (better objective function) at each point, you will eventually find the treasure at the best location (optimal solution).

We also said that we can justify that this is the optimum value by constructing the dual, which has how to combine the constraints together to minimize the combination and the solution which solves both the original and the dual is actually an optimum value.

In linear programming, each optimization problem can be associated with a dual problem that provides alternative insights into the constraints and objective function. While the primal problem may focus on maximizing profit given certain constraints, the dual problem may focus on minimizing the cost while ensuring that all resources are utilized effectively. The solution to both problems gives equivalent optimal values, deepening our understanding of the relationship between constraints and the objective.

Imagine you are in charge of a community garden. You want to maximize the variety of plants while dealing with limited space (this is your primal problem). However, you can also think of it as a matter of managing costs to ensure you don't overuse resources like water and soil while still providing enough for all your plants (this represents the dual problem). Both perspectives provide complete information about the garden's potential.

The next example we are going to look at is the carpet manufacturing company. We have a company which makes hand woven carpets and we currently employ 30 employees, each employee produces 20 carpets a month...

In this example, we explore the real-world application of linear programming in production planning within a carpet manufacturing company. The company faces varying monthly demand for carpets and needs to optimize production while managing costs associated with labor, hiring, firing, and storage. The analysis requires setting up a linear program that quantifies these variables and constraints, leading to optimal decision-making.

Imagine the carpet company like a chef managing a restaurant where the number of customers (demand) varies each day. The chef must decide how many dishes to prepare (production) daily while considering how many cooks (employees) to schedule, whether to use overtime, and how to handle leftovers. These decisions must align with the restaurant's budget (cost constraints) to ensure profitability.

So, we want to make a linear program out of this, so we need some variables. So, we are dealing with these 12 months January, February to December. Let us assume that we have Wi workers, initially we have 30 workers...

To formulate the linear program for the carpet manufacturing example, we first identify the relevant variables that need to be tracked over the months. This includes the number of workers, the number of carpets produced, and any changes in workforce. Defining these variables allows us to create a structured model that captures the dynamics of production and demand across the year.

Think of creating a student enrollment form for a school year. You need various fields in that form to capture essential information like the number of teachers (workers), each teacher's capacity, student enrollment in each month, and any hiring or firing requirements throughout the school year. By detailing these variables, you establish a comprehensive overview of staffing needs for effective operation.

--