Linear Programming (LP): Formulation
Explore the formulation of linear programming problems for constrained optimization. Understand the diet problem example, how to represent constraints and objective functions in matrix form, and how to find optimal solutions using vertex evaluation and numerical methods like SciPy's linprog.
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,