Steps for using the graphic method:
- Determine the objective function and formulate it in mathematical form.
- Identify the applicable limitations and formulate them in mathematical form.
- Describes each of the boundary function lines in one x and y axis system.
- Finding the most profitable (optimal) point is connected with the objective function.
Getting to Know Graphic Methods
Linear Programming Problem Examples
An industrial company has 260kg, 380kg, and 200kg of materials, namely wood, plastic, and steel, respectively. The company will make two types of products, namely P and Q, which respectively require the following materials (in kg):
| Produk | Bahan | | |
|--------|-------|---------|------|
| | Kayu | Plastik | Baja |
| P | 3 | 5 | 4 |
| Q | 5 | 6 | 3 |The selling price of each product P is Rp.140,000.00/unit and Q is Rp.180,000.00/unit. How many products P and Q should be produced to maximize profit, with variable costs of product P of Rp.80,000.00/unit and product Q of Rp.100,000.00/unit.
Completion
The above data can be arranged into a table as follows:
| | | | |
|----------------------------------------|---|---|--------------------|
| Produk -> | P | Q | Kapasitas Maksimum |
| Sumber | | | |
| Kayu | 3 | 5 | 260 |
| Plastik | 5 | 6 | 380 |
| Baja | 4 | 3 | 200 |
| Sumbangan terhadap laba (Rp.10.000,00) | 6 | 8 | |To formulate the problem above, first determine the symbols that will be used:
- X1 = the number of products P to be made.
- X2 = number of products Q to be made.
- Z = total donation of all products A and product B that will be obtained.
Finding the Maximum Objective Function
Steps 1 and 2
Formulating it into mathematical form:
Fungsi Tujuan: Maksimumkan Z = 6X1 + 8X2
Limitation:
- 3X1 + 5X2 ≤ 260
- 5X1 + 6X2 ≤ 380
- 4X1 + 3X2 ≤ 200
Step 3
Describes each of the boundary function lines in one X and Y axis system.
Limitation 1
- 3X1 + 5X2 ≤ 260
- If, X1 = 0, then X2 = 260/5 = 52
- If, X2 = 0, then X1 = 260/3 = 86.67
Limitation 2
- 5X1 + 6X2 ≤ 380
- If, X1 = 0, then X2 = 380/6 = 63.33
- If, X2 = 0, then X1 = 380/5 = 76
Limitation 3
- 4X1 + 3X2 ≤ 200
- If, X1 = 0, then X2 = 200/3 = 66.67
- If, X2 = 0, then X1 = 200/4 = 50
Graph Z Maximum Generated Results QM Application for Windows
Step 4.a
Finding the optimal (maximum) Z value can be done in 2 ways:
Method 1:
By describing the objective function (trial and error method), namely assuming the value of Z in the objective function equation, so that the values of X1 and X2 will be obtained. The purpose of this example is to find out the direction we shift until we meet a point in the feasible area, so that the optimal Z value is obtained, either Maximum or Minimum.
For example (just an example, as an illustration):
- 6X1 + 8X2 = 240
- If, X1 = 0, then X2 = 240/8 = 30
- If, X2 = 0, then X1 = 240/6 = 40
If the example is depicted in the graph above and shifted upwards/rightwards, then a point will be obtained in the feasible region at point B, so that point B is the optimal point with maximum Z. Point B is the meeting point between equation 1 and equation 3, so to calculate the value of Z at point B is:
Elimination:
3X1 + 5X2 ≤ 260 dikalikan 4
4X1 + 3X2 ≤ 200 dikalikan 3
----------------------------
12X1 + 20X2 ≤ 1040
12X1 + 9X2 ≤ 600
---------------------------- (-)
0 + 11X2 ≤ 440
X2 ≤ 440 / 11
X2 ≤ 40Substitute into equation 1:
3X1 + 5*40 ≤ 260
3X1 + 200 ≤ 260
3X1 ≤ 260 - 200
3X1 ≤ 60
X1 ≤ 60 / 3
X1 ≤ 20
Maka, Z optimal (maksimal) di titik B adalah 6X1 + 8X2 = 6*20 + 8*40 = 440Method 2:
By comparing the Z value at each alternative point, namely by calculating the Z value at each alternative point.
Point A
X1 = 50; X2 = 0, maka Z dititik A 6*50 + 8*0 = 300
Point B (same as method 1)
X1 = 20; X2 = 40, maka Z dititik B 6*20 + 8*40 = 440
Point C
X1 = 0; X2 = 52, maka Z dititik C 6*0 + 8*52 = 416
Conclusion:
So, based on method 2, the optimal Z value is at point B, the same as method 1. So product P(X1) is produced as much as 20 units and product Q(X2) is produced as much as 40 units with a maximum profit of 440 x Rp.10,000,- = Rp.4,400,000,-
Finding the Minimum Objective Function
Steps 1 and 2
Formulating it into mathematical form:
Fungsi Tujuan: Minimumkan Z = 6X1 + 8X2
Limitation:
- 3X1 + 5X2 = 260
- 5X1 + 6X2 ≤ 380
- 4X1 + 3X2 ≥ 200
Step 3
Describes each of the boundary function lines in one X and Y axis system.
Limitation 1
- 3X1 + 5X2 = 260
- If, X1 = 0, then X2 = 260/5 = 52
- If, X2 = 0, then X1 = 260/3 = 86.67
Limitation 2
- 5X1 + 6X2 ≤ 380
- If, X1 = 0, then X2 = 380/6 = 63.33
- If, X2 = 0, then X1 = 380/5 = 76
Limitation 3
- 4X1 + 3X2 ≥ 200
- If, X1 = 0, then X2 = 200/3 = 66.67
- If, X2 = 0, then X1 = 200/4 = 50
Graph Z Minimal Generated Results QM Application for Windows
Step 4.b
Finding the optimal (minimum) Z value can be done in 2 ways:
Method 1:
By describing the objective function (trial and error method), namely assuming the value of Z in the objective function equation, so that the values of X1 and X2 will be obtained. The purpose of this example is to find out the direction we shift until we meet a point in the feasible area, so that the optimal Z value is obtained, either Maximum or Minimum.
For example (just an example, as an illustration):
- 6X1 + 8X2 = 240
- If, X1 = 0, then X2 = 240/8 = 30
- If, X2 = 0, then X1 = 240/6 = 40
If the example is depicted in the graph above and shifted upwards/rightwards, then a point will be obtained in the feasible region at point B, so that point B is the optimal point with maximum Z. Point B is the meeting point between equation 1 and equation 3, so to calculate the value of Z at point B is:
Elimination:
3X1 + 5X2 = 260 dikalikan 4
4X1 + 3X2 ≥ 200 dikalikan 3
----------------------------
12X1 + 20X2 = 1040
12X1 + 9X2 ≥ 600
---------------------------- (-)
0 + 11X2 = 440
X2 = 440 / 11
X2 = 40Substitute into equation 1:
3X1 + 5*40 = 260
3X1 + 200 = 260
3X1 = 260 - 200
3X1 = 60
X1 = 60 / 3
X1 = 20
Maka, Z optimal (minimal) di titik B adalah 6X1 + 8X2 = 6*20 + 8*40 = 440Method 2:
By comparing the Z value at each alternative point, namely by calculating the Z value at each alternative point. Because there is only one alternative point, it is the optimal point with minimal Z, and the calculation of that point is the same as method 1.
Conclusion:
So, based on method 2, the optimal Z value is at point B, the same as method 1. So product P(X1) is produced as much as 20 units and product Q(X2) is produced as much as 40 units with a maximum profit of 440 x Rp.10,000,- = Rp.4,400,000,-
Reference:
Operations Research Module, Chapter 2 (A) Graphical Methods, compiled by Minawarti, ST.