...

/

Linear Programming (LP): Formulation

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., 130x1+120x2+150x3+75x42000130x_1 + 120x_2 + 150x_3 + 75x_4 \geq 2000

  • Protein: At least 55 g, i.e., 2.7x1+7.5x2+8x3+2x4552.7x_1 + 7.5x_2 + 8x_3 + 2x_4 \geq 55

  • Fat: At most 70 g, i.e., 0.3x1+0.5x2+8x3+x4700.3x_1 + 0.5x_2 + 8x_3 + x_4 \leq 70

Here, x1x_1 ...