Linear programming is used to solve an optimization problem wherein the objective function is the liner function which is essentially referred to as the optimization equation. Discrete optimization is a branch of optimization methodology containing discrete quantities which are non-continuous functions.
It is quite ubiquitous in as diverse applications such as financial investment, diet planning, manufacturing processes, and player or schedule selection for professional sports.It is useful for data scientists and machine learning (ML) practitioners because discrete and continuous optimization is crucial for ML and AI systems.
Linear programming is also used in organized retail used for shelf space optimization at supermarkets. Since the number of products in the market has increased in leaps and bounds, it is important to understand what the customer wants. Optimization is aggressively used in stores like Walmart, Amazon, Big Bazaar, etc. The objective is to help a customer to locate & select the right products which are subject to constraints like limited shelf space, the variety of products, etc. Similarly, with the help of clustering and the greedy algorithm, the delivery routes are decided by companies like FedEx, Amazon, etc to minimize the operation cost and time.
Example: A company wants to develop a high energy snack food for athletes that contains at least 20 grams of protein, 40 grams of carbohydrates and 900 calories. It contains three ingredients, denoted A, B and C. Each oz of ingredient A costs $0.20 and provides 8 grams of protein, 3 grams of carbohydrates and 150 calories. Each oz of B costs $0.10 and provides 2 grams of protein, 7 grams of carbohydrates and 80 calories. Each ozof C costs $0.15 and provides 5 grams of protein, 6 grams of carbohydrates and 100 calories. Use LP to determine the quantity of each ingredient used to minimize the cost of the snack food.
Number of products: 1
Number of ingredients: 3
Attributes: 3
Variables: xi = Number of oz of ingredient in snack food.i = 1 is A; i = 2 is B; i = 3 is C
Optimization equation:
Minimize: 0.2x1 + 0.1x2 + 0.15x3
Subject to:
8x1 + 2x2 + 5x3 20 (protein)
3x1 + 7x2 + 6x3 40 (carbs.)
150x1 + 80x2 + 100x3 900 (calories)
x1, x2, x3 0
Additional constraints:
1. At most 20% of the calories from ingredient A.
calories from A = 150x1
total calories =150x1 + 80x2 + 100x3
2. The snack food must include at least 1 oz of A and 2 oz of B.
3. The snack food must have twice as much A for B.
4. The snack food must have twice as much A for B and C.
x1 = 2x2 x1 = 2x3 or x1 = 2(x2 + x3)
5. The snack food must have twice as much A and B for C.
x1 = 2x3 x2 = 2x3or x1 + x2 = 2x3