TK5207 – REKONSILIASI DATA

LATIHAN - TOOLS FOR

OPTIMIZATIONS
Institut Teknologi Bandung

Lecturer: Aqsha, Sanggono Adisasmito

Institut Teknologi Bandung
2024

Image Souurce: Licdn.com

Linear Programming Method
LINEAR PROGRAMMING
Problem Statement
The following problem is developed from the area of chemical or petroleum engineering. However, it
is relevant to all areas of engineering that deal with producing products with limited resources.

Develop a linear programming formulation to maximize the profits for this operation.
Image:
LINEAR PROGRAMMING
Develop a linear programming formulation to maximize the profits for
this operation!

Solution
The engineer operating this plant must decide how much of each gas
to produce to maximize profits. If the amounts of regular and premium
produced weekly are designated as x1 and x2, respectively, the total
weekly profit can be calculated as:

Image:
LINEAR PROGRAMMING
The constraints can be developed in a similar fashion. For example,
the total raw gas used can be computed as

This total cannot exceed the available supply of 77 m 3/week and

working hour 80 hr/week, so the constraint can be represented as

Image:
LINEAR PROGRAMMING
First, the constraints can be plotted on the
solution space. For example, the first
constraint can be reformulated as a line by
replacing the inequality by an equal sign and
solving for x2

Next, the objective function can be added to

the plot. To do this, a value of Z must
be chosen. For example, for Z = 0, the
objective function becomes

Image:
LINEAR PROGRAMMING
Now, since we are interested in maximizing
Z, we can increase it to say, 600, and the
objective function is

Increasing the value of the objective function

moves the line away from the origin.
Because the line still falls within the solution
space, our result is still feasible. Z can keep
increasing until a further increase will take
the objective beyond the feasible region.

Image:
LINEAR PROGRAMMING
The maximum value of Z corresponds to approximately 1400. At this
point, x1 and x2 are equal to approximately 4.9 and 3.9, respectively.
Thus, the graphical solution tells us that if we produce these quantities
of regular and premium, we will reap a maximum profit of about 1400.

Image:
THE SIMPLEX METHOD
Now let us suppose that our problem
involves a unique solution. The graphical
approach might suggest an enumerative
strategy for hunting down the maximum.

From Fig. X, it should be clear that the

optimum always occurs at one of the
corner points where two constraints meet.
Such a point is known formally as an
extreme point. Thus, out of the infinite
number of possibilities in the decision
space, focusing on extreme points clearly
narrows down the possible options.

Image:
THE SIMPLEX METHOD
The simplex method is predicated on the assumption that the optimal solution will be
an extreme point. To do this, the constraint equations are reformulated as equalities
by introducing what are called slack variables.
As the name implies, a slack variable measures how much of a constrained resource
is available, that is, how much “slack” of the resource is available.

7𝑥1 + 11𝑥2 ≤ 77

We can define a slack variable S1 as the amount of raw gas that is not used for a
particular production level (x1, x2). If this quantity is added to the left side of the
constraint, it makes the relationship exact

7𝑥1 + 11𝑥2 + 𝑆1 ≤ 77

Image:
THE SIMPLEX METHOD
A different slack variable is developed for each constraint equation, resulting in what
is called the fully augmented version,
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑍 = 150𝑥1 + 175𝑥2
Constraints

Notice how we have set up the four equality equations so that the unknowns are
aligned in columns.
Image:
THE SIMPLEX METHOD
Normally we had n equations with n unknowns, to solve the system (Algebraic Soln)

The system of equations below is underspecified or underdetermined, that is, it has

more unknowns than equations. In general terms, there are n structural variables
(that is, the original unknowns), m surplus or slack variables (one per constraint),
and n 1 m total variables (structural plus surplus). For the gas production problem
we have 2 structural variables, 4 slack variables, and 6 total variables. Thus, the
problem involves solving 4 equations with 6 unknowns.
Image:
THE SIMPLEX METHOD
Specifically, every feasible point has 2
variables out of 6 equal to zero. For
example, the five corner points of the area
ABCDE have the following zero values:

Image:
THE SIMPLEX METHOD
This observation leads to the conclusion that the extreme points can be determined
from the standard form by setting two of the variables equal to zero. In our example,
this reduces the problem to a solvable form of 4 equations with 4 unknowns.
For example, for point E, setting x1 = S4 = 0 reduces the standard form to

Which can be solved for x2 = 6, S1 = 11, S2 = 32, and S3 = 9.Together with x1 = S4 =

0, these values define point E.

Image:
THE SIMPLEX METHOD

Image:
THE SIMPLEX METHOD
% Inputs
n = 16; % Total number of unknowns
m = 10; % Number of equations

% Compute the number of combinations

C_mn = factorial(n) / (factorial(m) * factorial(n - m));
% Display the result
fprintf('The number of combinations (C_%d^%d) is: %.0f\n', m, n, C_mn);

% Additional example: C_4^6

n2 = 6; % Total items
m2 = 4; % Chosen items
C_mn2 = factorial(n2) / (factorial(m2) * factorial(n2 - m2));
% Display the second result
fprintf('The number of combinations (C_%d^%d) is: %.0f\n', m2, n2, C_mn2);

Image:
THE SIMPLEX METHOD
% Example 1: Calculate the combination C_10^16
n = 16; % Total number of elements
m = 10; % Number of elements to choose

% Calculate the combination

C = nchoosek(n, m);
% Display the result
fprintf('The number of combinations C_%d^%d is: %d\n', m, n, C);

% Example 2: Calculate the combination C_4^6

n2 = 6; % Total number of elements
m2 = 4; % Number of elements to choose
C2 = nchoosek(n2, m2);
% Display the result
fprintf('The number of combinations C_%d^%d is: %d\n', m2, n2, C2);

Image:
THE SIMPLEX METHOD

Image:
THE SIMPLEX METHOD
Before proceeding to the next step, the beginning information can now be
summarized in a convenient tabular format called a tableau. As shown below, the
tableau provides a concise summary of the key information constituting the linear
programming problem.

Notice that for the purposes of the tableau, the objective function is expressed as
Z - 150x1 - 175x2 - 0S1 - 0S2 - 0S3 - 0S4 = 0
Image:
THE SIMPLEX METHOD

In order to solve this set of equations, similar algorithm such as Gauss-Jordan

elimination is used. It involves a series of iterations until the final solution is reached.

Image:
THE SIMPLEX METHOD
Recall that the basic strategy behind Gauss-Jordan involved converting the pivot element to 1 and
then eliminating the coefficients in the same column above and below the pivot element.
For this example, the pivot row is S2 (the leaving variable) and the pivot element is 10 (the coefficient
of the entering variable, x1). Dividing the row by 10 and replacing S2 by x1 gives

Next, the x1 coefficients in the other rows can be eliminated. For example, for the objective function
row, the pivot row is multiplied by -150 and the result subtracted from the first row to give

Image:
THE SIMPLEX METHOD
Similar operations can be performed on the remaining rows to give the new tableau,

This tableau can then be used to chart our next, and in this case final, step. Only one more variable,
x2, has a negative value in the objective function, and it is therefore chosen as the entering variable.
According to the intercept values (now calculated as the solution column over the coefficients in the x 2
column), the first constraint has the smallest positive value, and therefore, S1 is selected as the
leaving variable.

Image:
THE SIMPLEX METHOD
Start Excel Spreadsheet to solve the linear programming problem

Image:
THE SIMPLEX METHOD
Input all the available data including its constraint and set the solver

Image:
THE SIMPLEX METHOD
Input all the available data including its constraint and set the solver

Image:
MATLAB: LINPROG
x = linprog(f,A,b) solves min f'*x such that A*x ≤ b.
% Coefficients of the objective function
f = [-150, -175]; % Negative because linprog minimizes by default

% Coefficients of the constraints: Matrix A has size 4x2 (4 rows, 2 columns), Matrix b has size 4x1
A = [7, 11; % Raw gas constraint
10, 8; % Production time constraint
1, 0; % Regular storage constraint
0, 1]; % Premium storage constraint
b = [77; % Raw gas availability
80; % Production time availability
9; % Regular product storage limit
6]; % Premium product storage limit

% Lower bounds (non-negativity constraints)

lb = [0, 0];

% Solve the linear programming problem: Matrix x has size 2x1 (2 rows, 1 column)
[x, fval] = linprog(f, A, b, [], [], lb);

% Display the results

fprintf('Optimal production of Regular product (x1): %.2f tonnes\n', x(1));
fprintf('Optimal production of Premium product (x2): %.2f tonnes\n', x(2));
fprintf('Maximum profit: %.2f\n', -fval); % Negate fval to get the maximized value

Image:
CONTOH: LINPROG
Problem: Power Plant Fuel Optimization
A power plant uses a mix of biomass (2,5 MW of electricity per ton of biomass) and coal (5 MW of electricity
per ton of coal) as fuel for electricity generation. The plant needs to optimize the electricity production while
considering the following constraints:

Constraints
1.Fuel Availability:
1. Biomass supply is limited to 50 tons per day.
2. Coal supply is limited to 40 tons per day.

2. Energy Storage:
•Total energy storage capacity is 300 MW.

3. Cost Efficiency:
•Biomass cost: $100/ton.
•Coal cost: $120/ton.
•Daily fuel budget: $8,000.
Image:
STEPS TO SOLVE
Steps to Solve the Problem
1.Define Variables:
1. x1​: Amount of biomass (tons).
2. x2​: Amount of coal (tons).
2.Set Up the Objective Function:
1. Maximize Z=2.5x1+5x2, but convert to minimization for linprog by using −2.5x1−5x2​.
3.Set Up Constraints:
1. Use the inequalities from the problem statement to define A (constraint coefficients) and b (right-hand side).
4.Solve Using linprog:
1. Call MATLAB's linprog function to find the optimal x1 and x2​.
5.Interpret Results:
1. Display the optimal values of x1 and x2​, and the maximum electricity production.

Image:
JAWABAN
Objective Function
Maximize electricity production:
Z=2.5x1+5x2.

Constraints
1.Fuel Availability:
• x1​≤50 (biomass availability)
• x2≤40 (coal availability)

2. Energy Storage:
2.5x1+5x2 ≤300

3. Cost Efficiency:
100x1+120x2 ≤ 8,000.

4. Non-Negativity:
x1≥0, x2≥0
Image:
MATLAB: LINPROG
% Objective function coefficients (electricity production per ton)
f = [-2.5, -5]; % Negative because linprog minimizes

% Coefficients of the constraints

A = [1, 0; % Biomass availability
0, 1; % Coal availability
2.5, 5; % Energy storage capacity
100, 120]; % Fuel budget
b = [50; % Max biomass supply
40; % Max coal supply
300; % Energy storage capacity
8000]; % Daily fuel budget

% Lower bounds (non-negativity constraints)

lb = [0, 0];

% Solve the linear programming problem

[x, fval] = linprog(f, A, b, [], [], lb);

% Display results
fprintf('Optimal biomass usage (x1): %.2f tons\n', x(1));
fprintf('Optimal coal usage (x2): %.2f tons\n', x(2));
fprintf('Maximum electricity production: %.2f MW\n', -fval);

Image:
PLEASE CONTACT ME!

AQSHA
Assistant (Research) Professor
Dept. of Bioenergy Engineering & Chemurgy
Dept. of Chemical Engineering
Institut Teknologi Bandung, Indonesia

Waste to Energy Conversion | Biofuel & Bio-based Product Development |

CCS/BECCS | Biomimicry Catalyst | Thermochemical Conversion

Cell/WA: +62 813 888 70350 | aqsha@itb.ac.id | aqsha.edu@gmail.com

Program Studi Teknik Kimia, Teknik Pangan, Teknik Bioenergi dan Kemurgi, Institut Teknologi Bandung 31