Linear Programming is part of Operations Research approach are widely used for describing problems in allocating limited resources with certain conditions. Linear programming models the problems in the form of linear mathematics functions for each component.
According to Operations Research: Applications and Algorithms (Winston,1987), Linear Programming has three main interests: Optimizing objective function linearly, Satisfying constrains, which they are in equation or linear inequality form, and every variable has a sign restriction. Hence, correctly modelling each component of Linear Programming is very crucial. Generally, Components of Optimization Problems contains five aspects:
These five aspects act as a guide for modelling the problem mathematically since each component has its own mathematical representations. We introduce the modelling step by using an example.
Example Case:
Indemy Coffee Shop brews two type of coffee drinks: Affogato and Café Latte with the price of €6 and €3 respectively. The main ingredients consist of coffee beans, milk, and ice cream. Each affogato costs 9 grams of beans and one scoop worth 50 grams of ice cream while one café Latte costs 5 grams of coffee and 0.1 liters of milk. Each day the coffee shops have supplies of 450 grams of fresh coffee beans, four 500-gram pack of ice cream, and five packs of 1 liter milk. Based on the historical data, Indemy Coffee Shop sells on average 70 cups per day and the owner wants to use this number as the upper limit of sales. The owner wants to maximize daily revenue of the coffee shop based on those two products.
Firstly, derive the problems components:
Problem Entities Two type of drinks: Affogato and Café Latte Three critical resources: Beans, ice cream, and milk
Characteristics of Problem Entities Drinks have selling price, resource consumptions, and maximum sales capacity Critical resources have maximum supply and costs
Problem Decision How many drinks should be sold for each type?
Constraints: Problem characteristics containing limiting impact on decisions The owner unable to sell coffee more than resources bought and max sales capacity
Objectives: Maximization of revenue.
Based on these components, we can create the mathematical model (Note: Sets and constants are explicitly used in the model, hence defining them with symbols are unnecessary).
Decision Variables We define:
𝑥𝑎: number of Affogato drinks brewed
𝑥𝑐: number of Café Latte drinks brewed
𝑥0: total profit
Objective Functions
Consists of total daily sales from both products subtracted by daily costs for
ingredients max
𝑥0 = 6𝑥𝑎 + 3𝑥𝑐
Constraints
Limitation of coffee beans in grams
9𝑥𝑎 + 5𝑥𝑐 ≤ 450
Limitation of ice cream in grams (five packs per day)
50𝑥𝑎 ≤ 4 × 500
Limitation of milk in liter (five packs per day)
0.1𝑥𝑐 ≤ 5 × 1
Limitation of total sales
𝑥𝑎 + 𝑥𝑐 ≤ 70
Logical Limitation for non-negativity
𝑥𝑎 ≥ 0 𝑥𝑐 ≥ 0
Hence the complete model:
(OF) max𝑥0 = 6𝑥𝑎 + 3𝑥𝑐
(1) 9𝑥𝑎 + 5𝑥𝑐 ≤ 450
(2) 50𝑥𝑎 ≤ 2000
(3) 0.1𝑥𝑐 ≤ 5
(4) 𝑥𝑎 + 𝑥𝑐 ≤ 70
(5) 𝑥𝑎 ≥ 0
(6) 𝑥𝑐 ≥ 0
Based on this example, a solution any values combination of decision variables, and the objectives functions value is obtained from plugging in the solutions. Any solution could be included in three possible categories: feasible solution (every constraints satisfied), infeasible solution (at least one constraint violated), and optimal solution (best possible outcome in objective function value). In the next part we will discuss how to solve the problem with graphical method.
Comments