8.4. Formulating the Linear Program

A linear program is an optimization problem, where you have some variables which describe the quantities you want to compute. And 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 (LP) is a mathematical method used for determining the best possible outcome in a given situation, where you have constraints. It involves three main components: variables, constraints, and an objective function. The variables represent the quantities that you want to optimize (like profit or cost). Constraints are the limits on these variables (such as resources or time). The objective function is the formula you want to optimize (maximize or minimize) based on the variables and constraints you have.

Imagine you run a small bakery. Your variables could include the number of cakes and cookies you want to bake. Your constraints might be the amount of flour and sugar you have. The objective function could be maximizing your sales from cakes and cookies. By setting this up in a linear programming model, you can find out how many of each you should make to maximize your profits given your limitations.

One way to solve a linear program is to think of it geometrically and uses simplex algorithm and the simplex algorithm exploits the fact that the optimum value of a linear program is always at the vertex of the feasible region.

The Simplex Algorithm is a method used in linear programming to find the best solution to an LP problem. It works on the principle that the optimal solution lies at the vertex (or corner point) of the feasible region defined by the constraints. The algorithm starts at an initial feasible vertex and moves along the edges of the feasible region to adjacent vertices, looking for a better solution until it finds the optimal vertex.

Picture a game of chess where you're trying to achieve checkmate. You've got various possible moves (vertices) to reach the goal (optimal solution), and each move leads you closer to winning. The Simplex Algorithm intelligently explores these moves, ensuring you don't get stuck on suboptimal plays until you reach checkmate.

So, the next example we are going to look at is the carpet manufacturing company. So, we have a company which makes hand woven carpets and we currently employees 30 employees, each employee produces 20 carpets a month and his pay 20,000 rupees a salary.

In this example, a carpet manufacturing company has 30 employees, and each produces 20 carpets per month, costing the company 20,000 rupees in salaries. They can produce up to 600 carpets a month with their current workforce. However, the demand for carpets varies significantly, ranging from 440 to 920 carpets a month. The company must develop a strategy to meet this fluctuating demand while minimizing costs.

Think of this company like a restaurant that has a fixed number of chefs (employees) and has a varying number of customers each month. Sometimes it is packed, and they need to prepare more dishes, while other times it’s quiet. The restaurant needs to decide whether to hire more chefs, reduce the number of chefs, or find a way to prepare dishes faster during busy times.

I might want to add new workers, in case I have a higher demand projected a month or I might need to terminate some employees in case my demand probes below 600. But, these also come to cost, it goes I have to do some paperwork and also I have to give some compensation and so on.

The company can hire additional workers if demand increases above capacity or fire them if demand falls. However, hiring and firing incur costs such as paperwork and severance pay. In this case, hiring costs 3200 rupees per new worker, and firing costs 4000 rupees per worker.

This can be compared to a sports team that may need to recruit new players (employees) during a promising season or let go of players when their performance or attendance declines. The team faces costs associated with signing contracts (hiring) and settling payouts when releasing players (firing).

Finally, I can store carpets when I made exist and sell them later when I have a demand, but storage also cost something. So, let us assume that storing a carpet costs rupees 80 per month.

The company can store leftover carpets to sell when demand rises - but this incurs storage costs of 80 rupees per carpet per month. As such, they need to consider not only how many carpets to produce monthly but also how many to store for future sales, balancing inventory costs with potential sales.

Think about storing winter clothes during summer. You can keep them for when they are needed again, but it requires space and care to prevent damage, which is like the monthly storage cost. If you have too many clothes stored, the cost of maintaining them might outweigh their usefulness when summer ends.

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. So, it is natural to think of everything as happening within this scope of one month.

To create a linear program for the carpet company, we define variables for each month (January to December). These include numbers of workers, carpets produced, overtime production, and surplus stock. For instance, if 'Wi' represents the number of workers in month 'i', and 'Si' represents surplus carpets at the end of month 'i', these variables help model the operations throughout the year.

This modeling is like creating a budget for your expenses over a year. Each month you account for how many groceries you buy, how many meals you cook, and how much you save - creating a comprehensive plan that helps you manage your finances more effectively.

The first constraint to the usual one, which is there every quantity that we are talking about is strictly greater than equal to 0.

In the formulation of the linear program, all variables must be greater than or equal to zero because negative quantities do not make sense in this context. Additionally, other constraints relate to the production capacity (how much can be produced by the available workers), the storage constraints (what can be safely stored), and demand fulfillment (how many carpets need to be sold).

Think of this like a grocery list where you can’t buy negative amounts of food. If you're tracking how much fruit you have, you can’t have -2 apples. There are limits that ensure practical values reflect reality, just as in the case of the carpet company where they can't produce negative carpets.

So, now given these constraints what we want to do is minimize the total amount of cost that we are going to put up.

The objective function aims to reduce total costs associated with labor, hiring, firing, storage, and overtime. Each of these costs has a specific formula representing its contribution to the total cost based on the variable quantities defined earlier. By minimizing costs while satisfying constraints, the company can improve its profitability.

Inspired by our bakery example, it is like calculating the least amount of money spent on ingredients while still producing enough cakes and cookies to meet demand, ensuring that every dollar spent serves to produce the maximum quantity of good-tasting treats.

So, it turns out that we might come up with an answer which is not something that we can actually use. For instance, we might end up with a value like h3 = 10.6 for hiring workers, which doesn't make sense.

Sometimes linear programming solutions yield non-integer values, such as hiring 10.6 workers. Since you can't hire a fraction of a person, adjustments must be made through processes like rounding to the nearest whole number. However, this can impact the total cost, necessitating careful reevaluation to maintain an optimal solution.

This situation resembles a pizza order where the system indicates you can order 2.5 pizzas. You can't realistically order half a pizza, so you have to decide whether to round down to 2 or up to 3 based on your appetite and whether the rest will go to waste.

--