In this video, I'll talk about how to formulate typical linear programming problems.
Linear programming is widely used in many real-world applications.
There are well developed algorithms that can solve linear programming problems to optimality.
Here is the definition of linear programming.
A linear programming or LP problem is an optimization problem for which the objective function must
be a linear function of the decision variables.
Every constraint must be a linear equation or linear inequality.
A sign restriction is associated with each decision variable.
For any variable xi, it must be greater than or equal to 0 or it is unrestricted in sign
(URS), which means xi can take positive numbers, negative numbers, or 0.
Let's see an example.
A company manufactures two types of products, P1 and P2.
Producing each P1 will need $2000 worth of raw material, $5000 worth of labor, 2 hours
of machining time, and 1 hour of packaging time.
The selling price of each P1 is $10,000.
For P2, these values are listed in this column accordingly.
Each day, the demand for P1 and P2 are unlimited.
There are only 9 hours of machining time and 9 hours of packaging time available per day.
The company wants to know how many units of P1 and how many units of P2 to make each day
to maximize the profit.
To formulate the optimization problem, we need to identify three components: decision
variables, the objective function, and the constraints.
It is straightforward to define the decision variables for this example.
Let x1 be the units of P1 produced each day, and x2 be the units of P2 produced each day.
We assume x1 and x2 can take fractional numbers.
We want to maximize the daily profit, so the objective function is equal to the total revenue
minus the total cost.
The total revenue is equal to the selling price times the quantity for both P1 and P2.
The total cost is the unit raw material cost plus the unit labor cost times the quantity
for both P1 and P2.
It is equal to 3x1+2x2.
We use z to represent the objective function.
It should be mentioned that the unit is in $1000.
We have a set of constraints.
No more than 9 hours of machining time is available each day.
The total machining time is equal to the unit machining time times the quantity for both
P1 and P2: 2x1 + x2 ≤ 9.
No more than 9 hours of packaging time is available each day.
The total packaging time is equal to the unit packaging time times the quantity for both
P1 and P2: x1 + 2x2 ≤ 9.
Lastly, sign restrictions x1 and x2 should be greater than or equal to 0.
They cannot take negative numbers.
Usually, we write the complete problem formulation in a compact form like this.
max is short for maximize.
After that we list the objective function.
s.t. is short for subject to.
After that we list the constraints and sign restrictions.
This is a maximization problem.
We will focus on maximization problems in general in this course.
If we have a minimization problem, we can convert it to a maximization problem by taking
the opposite of the objective function.
For example, if this is a minimization problem.
min is short for minimize.
We can take the opposite of z and give it to y.
Now we can maximize y and it is a maximization problem.
There is no change in the constraints or sign restrictions.
Okay, that is how to formulate typical LP problems.
Thanks for watching.