Linear Programming (LP): Formulation
Learn about linear programming (LP) and explore the method of solving it through a brute-force approach.
In this chapter, we will discuss how to solve constrained optimization problems. We will start with understanding and solving linear programs.
Linear Programming (LP)
Consider the diet problem, where the task is to find the optimal combination of foods that satisfy the nutritional requirements of a person at a minimum cost. Let’s say we have the following four foods to choose from:
Food | Cost per Unit ($) | Calories per Unit | Protein per Unit (g) | Fat per Unit (g) |
Rice | 0.12 | 130 | 2.7 | 0.3 |
Beans | 0.18 | 120 | 7.5 | 0.5 |
Milk | 0.23 | 150 | 8 | 8 |
Bread | 0.05 | 75 | 2 | 1 |
We want to meet the following nutritional requirements for a person per day:
Calories: At least 2000, i.e.,
Protein: At least 55 g, i.e.,
Fat: At most 70 g, i.e.,
Here,