Introduction To optimize the solution of a problem linear programming comes in very handy. It can give you the maximum optimal solution u...
Introduction
To optimize the solution of a problem linear programming comes in very handy. It can give you the maximum optimal solution under some given
constraints. Now, let’s say you want to
minimize a cost function i.e., c₁x₁ + c₂x₂ + … + cₙxₙ. Here, x is a variable, and c_ is similar to co-efficient. In
linear programming a constraint for sum of a variable can be shown as follows:
(a₁x₁ + a₂x₂ + … + aₙxₙ ≤ b) or (a₁x₁ + a₂x₂ + … + aₙxₙ = b).
Here, x_ is a variable with a1_co-efficient
and b is resources.
This report is a part of
Artificial Intelligence course Lab-work under supervision of Nuruzzaman
Faruqui, Lecturer of City University, Bangladesh. This course offers students
various up-to-date AI topics. Students get to explore the real applicable
approaches through AI. From this course, the student acquires better knowledge of
the functionality of AI and how AI is making our daily life easier. This is the
best Artificial Intelligence course in Bangladesh
Problem statement
Consider the following example:
- Two machines, X₁ and X₂.
- X₁ costs $50/hour to run, X₂ costs $80/hour to run. The goal is to minimize cost.
- This can be formalized as a cost function: 50x₁ + 80x₂.
- X₁ requires 5 units of labor per hour.
- X₂ requires 2 units of labor per hour.
- Total of 20 units of labor to spend.
- This can be
formalized as a constraint: 5x₁
+ 2x₂ ≤
20.
- X₁ produces 10 units of output per hour.
- X₂ produces 12 units of output per hour.
- The company needs 90 units of output.
- This is another constraint.
- Literally, it
can be rewritten as 10x₁ + 12x₂
≥
90.
- However,
constraints need to be of the form (a₁x₁
+ a₂x₂
+ …
+ aₙxₙ
≤
b) or (a₁x₁
+ a₂x₂
+ …
+ aₙxₙ
= b).
Therefore, we multiply by (-1) to get to an equivalent equation of the desired form: (-10x₁) + (-12x₂) ≤ -90
Let’s code it on python:
import
scipy.optimize
# Objective Function: 50x_1 + 80x_2
# Constraint 1: 5x_1 + 2x_2 <= 20
# Constraint 2: -10x_1 + -12x_2 <= -90
result = scipy.optimize.linprog(
[50, 80], # Cost function: 50x_1 + 80x_2
A_ub=[[5, 2], [-10, -12]], # Coefficients for inequalities
b_ub=[20, -90], # Constraints for inequalities:
20 and -90
)
if result.success:
print(f"X1: {round(result.x[0],
2)} hours")
print(f"X2: {round(result.x[1],
2)} hours")
else:
print("No solution")
Result
After executing the above code
we get the following output:
Conclusion
An
optimizing algorithm for linear programming requires background knowledge in
geometry and linear algebra that we don’t want to assume. Instead, we can use
algorithms that already exist, such as Simplex and Interior-Point
Computer Science is all about mathematics. To get a better
grasp on linear programming you should definitely have a good working knowledge
in geometry and linear algebra. But for the sake of understanding, we have used already
existing methods in the code such as Simplex and Interior-Point.
No comments