It is known:
Objective function: maximum Z = 25X1 + 25X2, and Constraints:
- 3X1 + 2X2 ≤ 6
- 2X1 + 4X2 ≤ 8
- X1, X2 ≥ 0
Simplex vs. Graphical Method Solution Example
A. Simplex Method Solution
1. Changing the Objective Function and Its Constraints
Converted to an implicit function, meaning all CjXij are shifted to the left.
Purpose Function:
Z = 25X1 + 25X2 menjadi → Z - 25X1 - 25X2 = 0
Limitation Function:
Because the constraint function is in the form of an inequality, the way to change it to an implicit form is by adding a Slack Variable.
3X1 + 2X2 ≤ 6 menjadi → 3X1 + 2X2 + X3 = 6
2X1 + 4X2 ≤ 8 menjadi → 2X1 + 4X2 + X4 = 82. Arrange the equations into a table
- Z - 25X1 - 25X2 = 0
- 3X1 + 2X2 + X3 = 6
- 2X1 + 4X2 + X4 = 8
| Variabel Dasar | Z | X1 | X2 | X3 | X4 | NK |
|----------------|---|-----|-----|----|----|----|
| Z | 1 | -25 | -25 | 0 | 0 | 0 |
| X3 | 0 | 3 | 2 | 1 | 0 | 6 |
| X4 | 0 | 2 | 4 | 0 | 1 | 8 |3. Selecting Key Columns
In row Z there are two values (-) that are the same size, so one of them must be chosen, and it is free. In this case I choose -25 in column X1.
4. Selecting Key Rows
Before determining the key row, first calculate the basic variable index, except for row Z. So the following results are obtained:
5. Changing Key Row Values
The key value obtained = 3.
6. Change values other than key rows
Then the results obtained:
The first table (white) is the old values and the second table (colored) is the new values,
7. Re-Optimization
Because row Z in the second table (colored) still contains negative values (-), further optimization is needed by repeating steps 3 to 6.
Optimization table 1
| Variabel Dasar | Z | X1 | X2 | X3 | X4 | NK | Indeks |
|----------------|---|----|-------|------|----|----|--------|
| Z | 1 | 0 | -25/3 | 25/3 | 0 | 50 | |
| X1 | 0 | 1 | 2/3 | 1/3 | 0 | 2 | |
| X4 | 0 | 0 | 8/3 | -2/3 | 1 | 4 | |7.3. Selecting Key Columns
7.4. Selecting Key Rows
7.5. Changing Key Row Values
7.6. Changing values other than key rows
Table obtained from the first table up to the last fix/change:
Conclusion
Because in the objective function row (Z) there are no negative values (-), it is considered optimal with the values X1 = 1, X2 = 3/2 and Z max = 125/2.
Graphical Method Solution
1. Determine the variables
| - | Variabel |
|---|----------|
| - | X1 |
| - | X2 |2. Determine the Objective Function (Z)
Z = 25X1 + 25X2
3. Determining the Limit Function
- 3X1 + 2X2 ≤ 6
- 2X1 + 4X2 ≤ 8
4. Minimize Z
Two limitation functions have been obtained, including;
- 3X1 + 2X2 ≤ 6
- 2X1 + 4X2 ≤ 8
1). 3X1 + 2X2 ≤ 6
If, X1 = 0, then X2 = 6/2 = 3
If, X2 = 0, then X1 = 6/3 = 2
So, (X1, X2) = (2, 3)
2). 2X1 + 4X2 ≤ 8
If, X1 = 0, then X2 = 8/4 = 2
If, X2 = 0, then X1 = 8/2 = 4
So, (X1, X2) = (4, 2)
5. Drawing Graphs and Declaring Feasible Regions
Drawing Graphs and Declaring Feasible Regions
6. Finding the Optimal Z Value
The case study asks about the MAXIMUM of the objective function (Z).
To find the optimal Z value, 2 methods can be used:
1. By comparing the Z value at each alternative point
The method is to calculate the Z value at each alternative point, by substitution.
Point A
Since point A is the intersection of limits 1 and 2, it is necessary to use both inequalities/functions,
Elimination:
3X1 + 2X2 ≤ 6 | kalikan 2
2X1 + 4X2 ≤ 8 | kalikan 1
------------------------------
6X1 + 4X2 ≤ 12
2X1 + 4X2 ≤ 8
------------------------------ (-)
4X1 + 0 = 4
X1 = 4/4
X1 = 1Substitute into one of the inequalities:
3X1 + 2X2 ≤ 6
3*1 + 2X2 ≤ 6
3 + 2X2 ≤ 6
2X2 ≤ 6 - 3
2X2 ≤ 3
X2 ≤ 3/2So that point A (1, 3/2) is obtained. Next, substitute it into the objective function (Z), then;
Z = 25X1 + 25X2
Z = 25*1 + 25*3/2
Z = 25 + 75/2
Z = 50/2 + 75/2
Z = 125/2
Z = 125/2 (max)7. Making Conclusions
So it can be concluded that, X1 = 1 and X2 = 3/2 and Z Max = 125/2.
Guide:
- Getting to Know the Simplex Method
- Getting to Know Graphic Methods
- Example of Solving Problems Using the Graphical Method
Graphical vs Simplex Method UTS Operations Research
Known PL issues:
The Kemripik Potato Chips Company makes two types of chips, Nikmat and Enak, which are sold for Rp. 130,000 and Rp. 120,000 per kilo (10 packages). In each production, a maximum of 4 kg of medium quality potatoes and 4 kg of super quality potatoes are provided.
To make Delicious Chips, 1 kg of medium quality potatoes and 4 kg of super quality potatoes are needed. To make Delicious Chips, 4 kg of medium quality potatoes and 1 kg of super quality potatoes are needed. How many Delicious and Delicious Potato Chips should be made to get the most profit if the cost of making each chip is known to be Rp. 100,000,-/kg.
Graphical vs Simplex Method Solution - Operations Research Midterm Exam
Solve the PL problem above using:
- Graphical Method
- Simplex Method
1. Graphical Method Solution
1. Determine the variables
| Keripik | Variabel |
|---------|----------|
| Nikmat | X1 |
| Enak | X2 |2. Determine the Objective Function (Z)
Z = ...X1 + ...X2
| Keripik | Jual | Keuntungan | Biaya |
|---------|--------------|-------------|--------------|
| Nikmat | Rp.130.000,- | Rp.30.000,- | Rp.100.000,- |
| Enam | Rp.120.000,- | Rp.20.000,- | Rp.100.000,- |Because the question is how much profit is the greatest, the value used for the objective variable is the value in the profit column, so it becomes;
Z = 30.000 X1 + 20.000 X2
Z = 3X1 + 2X2 → (Menggunakan skala 1:10.000).3. Determining the Limit Function
| Bahan | Fungsi | Batasan |
|---------------------|----------|---------|
| Kentang mutu SEDANG | X1 + 4X2 | ≤ 4 |
| Kentang mutu SUPER | 4X1 + X2 | ≤ 4 |4. Minimize Z
Two limitation functions have been obtained, including;
- X1 + 4X2 ≤ 4
- 4X1 + X2 ≤ 4
1). X1 + 4X2 ≤ 4
If, X1 = 0, then X2 = 4/4 = 1
If, X2 = 0, then X1 = 4/1 = 4
So, (X1, X2) = (4, 1)
2). 4X1 + X2 ≤ 4
If, X1 = 0, then X2 = 4/1 = 4
If, X2 = 0, then X1 = 4/4 = 1
So, (X1, X2) = (1, 4)
5. Drawing Graphs and Declaring Feasible Regions
6. Finding the Optimal Z Value
The case study asks about the maximum profit (MAXIMUM) , then the optimal objective function (Z) can be found by:
Using alternative point (Point A)
Since point A is the intersection of limits 1 and 2, it is necessary to use both inequalities/functions,
Elimination:
X1 + 4X2 ≤ 4 || kalikan 4
4X1 + X2 ≤ 4 || kalikan 1
------------------------------
4X1 + 16X2 ≤ 16
4X1 + X2 ≤ 4
------------------------------ (-)
0 + 15X2 ≤ 12
X2 ≤ 12
X2 ≤ 12/15
X2 ≤ 4/5Substitute into one of the inequalities:
X1 + 4X2 ≤ 4
X1 + 4*4/5 ≤ 4
X1 + 16/5 ≤ 4
X1 ≤ 4 - 16/5
X1 ≤ (60 - 48) /15
X1 ≤ 12/15
X1 ≤ 4/5So that point A (4/5,4/5) is obtained. Next, substitute it into the objective function (Z), then;
Z = 3X1 + 2X2
Z = 3*4/5 + 2*4/5
Z = 12/5 + 8/5
Z = 20/5
Z = 4 (max)7. Making Conclusions
So it can be concluded that, X1 = 4/5 and X2 = 4/5 and Z Max = 4. In other words, to be able to obtain maximum profit from making chips, each kilogram is sufficient with 4/5 Nikmat chips, 4/5 Enak chips and the resulting profit is 4 x Rp. 10,000,- = Rp. 40,000,-
2. Simplex Method Solution
It is known that the objective function (Z) = 3X1 + 2X2 (scale 1:10,000).
Limitation function:
- X1 + 4X2 ≤ 4
- 4X1 + X2 ≤ 4
1. Changing the Objective Function and Its Constraints
Converted to an implicit function, meaning all CjXij are shifted to the left.
Purpose Function:
Z = 3X1 + 2X2 menjadi → Z - 3X1 - 2X2 = 0
Limitation Function:
Because the constraint function is in the form of an inequality, the way to change it to an implicit form is by adding a Slack Variable.
X1 + 4X2 ≤ 4 menjadi → X1 + 4X2 + X3 = 4
4X1 + X2 ≤ 4 menjadi → 4X1 + X2 + X4 = 42. Arrange the equations into a table
- Z - 3X1 - 2X2 = 0
- X1 + 4X2 + X3 = 4
- 4X1 + X2 + X4 = 4
| Variabel Dasar | Z | X1 | X2 | X3 | X4 | NK |
|----------------|---|----|----|----|----|----|
| Z | 1 | -3 | -2 | 0 | 0 | 0 |
| X3 | 0 | 1 | 4 | 1 | 0 | 4 |
| X4 | 0 | 4 | 1 | 0 | 1 | 4 |3. Selecting Key Columns
In row Z, the largest negative value is selected, so that it can be determined that the key column falls in column X1.
4. Selecting Key Rows
Before determining the key row, first calculate the basic variable index, except for row Z. So the following results are obtained:
5. Changing Key Row Values
Key value obtained = 4
| Variabel Dasar | Z | X1 | X2 | X3 | X4 | NK |
|----------------|---|----|-----|----|-----|----|
| Z | | | | | | |
| X3 | | | | | | |
| X1 | 0 | 1 | 1/4 | 0 | 1/4 | 1 |6. Change values other than key rows
Then the results obtained:
So we get the First Change Table:
| Variabel Dasar | Z | X1 | X2 | X3 | X4 | NK |
|----------------|---|----|------|----|------|----|
| Z | 1 | 0 | -5/4 | 0 | 3/4 | 3 |
| X3 | 0 | 0 | 15/4 | 1 | -1/4 | 3 |
| X1 | 0 | 1 | 1/4 | 0 | 1/4 | 1 |7. Re-Optimization
Because row Z in the First Change Table still contains negative values (-), further optimization is required by repeating steps 3 to 6.
7.3. Selecting Key Columns
7.4. Selecting Key Rows
7.5. Changing Key Row Values
| Variabel Dasar | Z | X1 | X2 | X3 | X4 | NK |
|----------------|---|----|----|------|-------|-----|
| Z | | | | | | |
| X2 | 0 | 0 | 1 | 4/15 | -1/15 | 4/5 |
| X1 | | | | | | |7.6. Changing values other than key rows
So we get the Second Change Table:
| Variabel Dasar | Z | X1 | X2 | X3 | X4 | NK |
|----------------|---|----|----|-------|-------|-----|
| Z | 1 | 0 | 0 | 1/3 | 2/3 | 4 |
| X2 | 0 | 0 | 1 | 4/15 | -1/15 | 4/5 |
| X1 | 0 | 1 | 0 | -1/15 | 4/15 | 4/5 |Conclusion
Because in the objective function row (Z) there are no negative values (-), it is considered optimal with the X1 = 4/5, X2 = 4/5 dan Z max = 4 * Rp.10.000,- = Rp.40.000,-. result value being the same as the Graphic method, thus mutually reinforcing the results obtained.