FINAL INDEPENDENT PROJECT
Linear Programming Simplex Method
Objective:- To Write a code for Linear Programming Operators to solve three variable minimization problem while using Simplex Method.
Sub-objectives:- Code will generate each simplex table during every iterations.
Theory:-
Linear Programming:- It is a mathematical method, use for determining a best optimal solution from a number of possible solutions. It is used mainly for optimisation of resources within limited resources.
Requirement of Linear programming :-
1. Objective Function:- the function which is to be optimised is called objective function and it must be clearly identifiable and measurable in quantitative terms like maximization of profit or minimization of cost.
Zmi = C1X1 + C2X2 + --------+ CnXn
2. Constraint/Condition/Restriction:- these are the limited resources within which we need to optimize our objective function.
a(11)X1 + a(12)X2 + -----------+ a(1n)Xn <= b1
a(21)X1 + a(22)X2 + -----------+ a(2n)Xn <= b2
a(31)X1 + a(32)X2 + -----------+ a(3n)Xn <= b3
-------------------------------------------------------
a(m1)X1 + a(m2)X2 + -----------+ a(mn)Xn <= bm
X1,X2,--------------Xn >= 0
3. The objective function and the constraint equation should be linear.
Simplex Method:- Simplex method, standard technique in linear programming for solving an optimization problem, typically one involving a function and several constraints expressed as inequalities. The inequalities define a polygonal region, and the solution is typically at one of the vertices. The simplex method is a systematic procedure for testing the vertices as possible solutions.
Some simple optimization problems can be solved by drawing the constraints on a graph. However, this method is useful only for systems of inequalities involving two variables. In practice, problems often involve hundreds of equations with thousands of variables, which can result in an astronomical number of extreme points.
Conditions:-
1. All the resource value of the constraint equation should be non-negative.
2. Each of the decision variable of the problem should be non-negative.
3. All the inequalities of the constraint equation should be converted into equalities.
3x1 + 5x2 <= 60
3x1 + 5x2 + s = 60
where s = slack variable
If there are 'm' equality constraints and 'n' is the number of variable and n>m then we need to put n-m variables equal to zero and solve the remaining 'n' variables with 'm' equality constraints. The n-m variables which are put equals to zero are called non-basic variable and 'm' variable are called basic variables which gives the basic solution. This step will reduce the number of alternative options whose maximum value is given by nCm = n!/(m!.(n-m)!).
Terms:-
1. Feasible Solution:- All the values of 'xj' which satisfies the given constraint equation along with the non-negative condition is called feasible solution.
2. Basic Solution:- All the values of 'xj' obtained by solving 'm' basic variables when each 'n-m' non basic variable is put equal to zero is called basic solution.
3. Basic feasible solution:- It is abasic solution which also satisfies the non-negative condition i.e., xj>=0.
Special Cases:-
1. Minimization problem can be solved as maximization by multipling the objective function by '-1' and solving as before.
2. Minimization problem can be solved as minimization by selecting the '△j` value with the most negative entry as key column. The optimal solution is achieved when all the '△j` values are either positive or zero.
Method to solve Objective function by using Simplex Method
let us take an objective function
Zmin = x(1) - 3x(2) + 2x(3)
subjected to
3x(1) - x(2) + 2x(3) <= 7;
-2x(1) + 4x(2) <= 12;
-4x(1) + 3x(2) + 8x(3) <=10;
x(1),x(2),x(3) >= 0
we have to minimize our objective function
1. First we will convert our minimization problem into maximization
Zmax = -x(1) + 3x(2) - 2x(3)
2. We will convert our constraint inequality equations into constraint equality equation by introducing slack functions
3x(1) - x(2) + 2x(3) + s(1) = 7;
-2x(1) + 4x(2) + s(2) = 12;
-4x(1) + 3x(2) + 8x(3) + s(3) = 10;
3. then convert our objective function on the basis of slack functions
Zmax = -x(1) + 3x(2) -2x(3) + s(1) + s(2) + s(3)
3. Now we will create Simplex table
| ai/bj | --- | -------------- | b1 | b2 | b3 | b4 | b5 | b6 | b7 | ----------- |
| ----- | --- | cost(cj) | -1 | 3 | -2 | 0 | 0 | 0 | --------- | ----------- |
| ----- | ei | BV | x1 | x2 | x3 | s1 | s1 | s3 | sol |
sol(new) min. ratio (b7/key bj) |
| ----- | --- | zj - cj | 1 | -3 | 2 | 0 | 0 | 0 | 0 | ---------------- |
| a1 | 0 | s1 | 3 | -1 | 2 | 1 | 0 | 0 | 7 | -7 = inf |
| a2 | 0 | s2 | -2 | 4 | 0 | 0 | 1 | 0 | 12 | 3 |
| a2 | 0 | s3 | -4 | 3 | 8 | 0 | 0 | 1 | 10 | 3.333 |
| ----- | --- | zj = ∑ai*bj | 0 | 0 | 0 | 0 | 0 | 0 | --------- | ---------------- |
Table analysis
A simplex table gives an optimal solution if all the zj-cj values in the row are:-
1. zero or negative when linear programming is of maximization.
2. zero or positive when linear programming is of minimization.
so from above table we can conclude that our solution is not optimal
4. now we have to create another simplex table with some replacements. To create new table we need to find key column(pivot column), key row(pivot row), and key element(pivot element)
for maximization, key column will be the column in zj-cj is minimum, in our case it is b2 = z2-c2 = -3
key row will be the row in min. ratio is minimum non negative, in our case it is a2 = b7/b2 = 3
key element is the element in the intersection of key column and key row, in our case it is b2 x a2 = 4
3. now in new table, we will replace a2 i.e., s2 row elments with x2 column elements
| ai/bj | --- | -------------- | b1 | b2 | b3 | b4 | b5 | b6 | b7 |
| ----- | --- | cost(cj) | -1 | 3 | -2 | 0 | 0 | 0 | ----------- |
| ----- | ei | BV | x1 | x2 | x3 | s1 | s2 | s3 |
min. ratio (b7/key bj) |
| ----- | --- | zj - cj | |||||||
| a1 | 0 | s1 | |||||||
| a2 | 12 | x2 | -1 | 4 | 3 | 0 | 1 | 0 | 12 |
| a2 | 0 | s3 | |||||||
| ----- | --- | zj = ∑ai*bj |
now we will convert our key element into unity i.e., a2/4
| ai/bj | --- | -------------- | b1 | b2 | b3 | b4 | b5 | b6 | b7 |
| ----- | --- | cost(cj) | -1 | 3 | -2 | 0 | 0 | 0 | ----------- |
| ----- | ei | BV | x1 | x2 | x3 | s1 | s2 | s3 |
min. ratio (b7/key bj) |
| ----- | --- | zj - cj | |||||||
| a1 | 0 | s1 | |||||||
| a2 | 12 | x2 | -1/4 | 1 | 3/4 | 0 | 1 | 0 | 3 |
| a2 | 0 | s3 | |||||||
| ----- | --- | zj = ∑ai*bj |
now we will convert our key column values into zero by performing certain operations
now again we follow table analysis process find out whether optimal point is reached or not.
if we will not reach the optimal point then again we will create new simplex table by following same procedure as mentioned above and analyse each table until we reached optimal point.
in our case optimal point reached at third simplex table
| ai/bj | --- | -------------- | b1 | b2 | b3 | b4 | b5 | b6 | b7 |
| ----- | --- | cost(cj) | -1 | 3 | -2 | 0 | 0 | 0 | ----------- |
| ----- | ei | BV | x1 | x2 | x3 | s1 | s2 | s3 |
min. ratio (b7/key bj) |
| ----- | --- | zj - cj | 0 | 0 | 2.4 | 0.2 | 0.8 | 0 | 11 |
| a1 | 7 | x1 | 1 | 0 | 0.8 | 0.4 | 0.1 | 0 | 4 |
| a2 | 12 | x2 | 0 | 1 | 0.4 | 0.2 | 0.3 | 0 | 5 |
| a2 | 0 | s3 | 0 | 0 | 10 | 1 | -0.5 | 1 | 11 |
as all the zj-cj values in the row are zero or positive therefore above table is optimal.
Zmax = 11 i.e., Zmin = -11
at variables x1 = 4, x2 = 5 and x3 = 0
Procedure of Coding:-
1. Our primary objective is to write code that will take inputs condition from the users and calculate Minimum optimal solution. The input conditions include:-
(a). Number of variables in the objective function/equation
Noofvariables = input('Number of variables : ');
(b). Providing Coefficients of OPTIMIZATION EQUATION
c = input('Enter optimization Equation coefficients in matrix form : ');
(c). Providing Coefficients of Constraint equations which is in the form of matrix.
Var = input('Enter subjected condition equations coefficient in matrix form : ');
(d). Providing Constants of Constraint equations
b = input('Enter Constants of Constraint equations in matrix form : ');
2. To convert our constraint inequality equations into constraint equality equation by introducing slack functions. Depending upon the input constraint equation, slack function will be an identity matrix. To create an identity matrix of size equal to the size of constraint equation matrix size. In this we will use 'eye' command.
s = eye(size(Var,1));
>> s
s =
1 0 0
0 1 0
0 0 1
3. Now we will arrange all the inputs of constraint equation into a single matrix
A = [Var s b];
4. Now we will introduce slack function in inputed objective function eg. Zmin = x(1) - 3x(2) + 2x(3) + 0*s1 + 0*s2 + 0*s3. In the following code will be add slack coefficient in objective function coefficient matrix. In this we have used 'size' command. sz = size(A)A. For example, if A is a 3-by-4 matrix, then size(A) returns the vector [3 4].
cost = zeros(1,size(A,2));
cost(1:Noofvariables) = c;
5. Now we will provide the values of Basic variables
BV = Noofvariables + 1 : 1 : size(A,2) - 1;
output = 4 5 6 = defines value of BV which is initially the coefficient of slack variables
| b4 | b5 | b6 | |||||||
| 0 | 0 | 0 | |||||||
| ei | BV | x1 | x2 | x3 | s1 | s2 | s3 | ||
| 0 | s1 | ||||||||
| 0 | s2 | ||||||||
| 0 | s3 |
6. Now we will calculate objective function with respect to each cordinates. i.e., Zmax = ZjCj = ei*bj - Cj
ZjCj = cost(BV)*A - cost;
| ai/bj | --- | -------------- | b1 | b2 | b3 | b4 | b5 | b6 | b7 |
| ----- | --- | cost(cj) | |||||||
| ----- | ei | BV | x1 | x2 | x3 | s1 | s2 | s3 | |
| ----- | --- | zj - cj | |||||||
| a1 | s1 | ||||||||
| a2 | s2 | ||||||||
| a2 | s3 | ||||||||
7. Now to print simplex table
ZCj = [ZjCj;A];
SimpTable = array2table(ZCj);
SimpTable.Properties.VariableNames(1:size(ZCj,2)) = {'x1','x2','x3','s1','s2','s3','sol'}
8. As above created simplex table is based on initial values. If it follow Minimization condition i.e., zero or positive when linear programming is of minimization, it will be considered as optimal otherwise new table will be created based on above steps. To provide such condition in our code we will use 'while' loop command.
while RUN
9. Now we will code for conditions of optimal solution. It will check whether above solution is optimal or not. If it not follow the condition the MATLAB will print 'The Current BFS is Not Optimal' and it will initiate next iteration.
if any(ZjCj<0);
%Check if any negative value there
fprintf('The Current BFS is Not Optimal \n');
fprintf('\n===============The Next Iteration Results===============\n');
10. we have to find minimum among ZjCj excluding Sol
disp('OLD Basic Variable (BV) = ');
disp(BV)
11. Findi the entering variables
ZC = ZjCj(1:end);
[Enter_col,pvt_col] = min(ZC)
fprintf('The Minimum element in Zj-Cj row is %d Corresponding to column %d\n',Enter_col,pvt_col)
fprintf('Entering Variable is %d \n',pvt_col)
12. finding the leaving variable
sol = A(:,end);
column = A(:,pvt_col);
13. Now to calculate Ratio we will use 'if else' command to find non negative minimum value
if all(column<=0);
error('LPP is UNBOUNDED. All entries <= 0 in column %d ',pvt_col)
else
for i = 1:size(column,1)
if column(i) > 0
ratio(i) = sol(i)./column(i)
else
ratio(i) = inf;
end
end
14. Finding the minimum
[minRatio,pvt_row] = min(ratio);
fprintf('Minimum Ratio corresponding to Pivot Row is %d\n ',pvt_row)
fprintf('Leaving Variable is %d \n ',BV(pvt_row))
end
BV(pvt_row) = pvt_col;
disp('New Basic Variables (BV) = ')
disp(BV);
15. Pivot Key
pvt_key = A(pvt_row,pvt_col)
16. update the table for next iteration
A(pvt_row,:) = A(pvt_row,:)./pvt_key;
for i = 1:size(A,1)
if i ~= pvt_row
A(i,:) = A(i,:)-A(i,pvt_col).*A(pvt_row,:);
end
ZjCj = ZjCj - ZjCj(pvt_col).*A(pvt_row,:);
end
17. for printing Purpose
ZCj = [ZjCj;A];
Table = array2table(ZCj);
Table.Properties.VariableNames(1:size(ZCj,2)) = {'x1','x2','x3','s1','s2','s3','sol'}
BFS = zeros(1,size(A,2));
BFS(BV) = A(:,end);
BFS(end) = sum(BFS.*cost);
Current_BFS = array2table(BFS);
Current_BFS.Properties.VariableNames(1:size(Current_BFS,2)) = {'x1','x2','x3','s1','s2','s3','sol'}
else
RUN = false;
18. If the iteration reached optimal solution then it will print 'The Current BFS is optimal'
fprintf('===================xxxxxxxxxxxxxxx=====================\n ')
fprintf('The Current BFS is optimal \n')
19. And Current_BFS will represet optmal coridinates and optimal value. eg.,
Current_BFS =
1×7 table
x1 x2 x3 s1 s2 s3 sol
__ __ __ __ __ __ ___
4 5 0 0 0 11 11
end
end
MATLAB Code:-
clc
clear all
close all
%Simplex Method Linear programming
%Number of variables : 3
%Enter optimization Equation coefficients in matrix form : [-1 3 -2]
%Enter subjected condition equations coefficient in matrix form : [3 -1 2; -2 4 0; -4 3 8]
%Enter Constants of Constraint equations in matrix form : [7; 12; 10]
%====================================================================================================
diary SimplexFile
%Providing Input conditions
%Definig Number of Variables
Noofvariables = input('Number of variables : ');
%Providing Coefficients of OPTIMIZATION EQUATION
c = input('Enter optimization Equation coefficients in matrix form : ');
%Providing Coefficients of Constraint equations
Var = input('Enter subjected condition equations coefficient in matrix form : ');
%Providing Constants of Constraint equations
b = input('Enter Constants of Constraint equations in matrix form : ');
%providing slack variables
s = eye(size(Var,1));
%arranging in matrix
A = [Var s b];
cost = zeros(1,size(A,2));
cost(1:Noofvariables) = c;
BV = Noofvariables + 1 : 1 : size(A,2) - 1;
ZjCj = cost(BV)*A - cost;
%for printing the table
ZCj = [ZjCj;A];
SimpTable = array2table(ZCj);
SimpTable.Properties.VariableNames(1:size(ZCj,2)) = {'x1','x2','x3','s1','s2','s3','sol'}
RUN = true;
while RUN
if any(ZjCj<0);
%Check if any negative value there
fprintf('The Current BFS is Not Optimal \n');
fprintf('\n===============The Next Iteration Results===============\n');
%we have to find minimum among ZjCj excluding Sol
disp('OLD Basic Variable (BV) = ');
disp(BV)
%Findin the entering variables
ZC = ZjCj(1:end);
[Enter_col,pvt_col] = min(ZC)
fprintf('The Minimum element in Zj-Cj row is %d Corresponding to column %d\n',Enter_col,pvt_col)
fprintf('Entering Variable is %d \n',pvt_col)
%finding the leaving variable
sol = A(:,end);
column = A(:,pvt_col);
if all(column<=0);
error('LPP is UNBOUNDED. All entries <= 0 in column %d ',pvt_col)
else
for i = 1:size(column,1)
if column(i) > 0
ratio(i) = sol(i)./column(i)
else
ratio(i) = inf;
end
end
%Finding the minimum
[minRatio,pvt_row] = min(ratio);
fprintf('Minimum Ratio corresponding to Pivot Row is %d\n ',pvt_row)
fprintf('Leaving Variable is %d \n ',BV(pvt_row))
end
BV(pvt_row) = pvt_col;
disp('New Basic Variables (BV) = ')
disp(BV);
%Pivot Key
pvt_key = A(pvt_row,pvt_col)
%update the table for next iteration
A(pvt_row,:) = A(pvt_row,:)./pvt_key;
for i = 1:size(A,1)
if i ~= pvt_row
A(i,:) = A(i,:)-A(i,pvt_col).*A(pvt_row,:);
end
ZjCj = ZjCj - ZjCj(pvt_col).*A(pvt_row,:);
end
%for printing Purpose
ZCj = [ZjCj;A];
Table = array2table(ZCj);
Table.Properties.VariableNames(1:size(ZCj,2)) = {'x1','x2','x3','s1','s2','s3','sol'}
BFS = zeros(1,size(A,2));
BFS(BV) = A(:,end);
BFS(end) = sum(BFS.*cost);
Current_BFS = array2table(BFS);
Current_BFS.Properties.VariableNames(1:size(Current_BFS,2)) = {'x1','x2','x3','s1','s2','s3','sol'}
else
RUN = false;
fprintf('===================xxxxxxxxxxxxxxx=====================\n ')
fprintf('The Current BFS is optimal \n')
end
end
diary offYoutube link:-
Simplex Method Operators for 3 variables maximization problem
Results:-
Observations:-
1. Above code will solve 3 variable objective function. It is capable of solving more than 3 variables but it could create irregular table formation. However we can alter it to solve more than 3 variables by altering following codes to show proper simplex table.
Table = array2table(ZCj);
Table.Properties.VariableNames(1:size(ZCj,2)) = {'x1','x2','x3','s1','s2','s3','sol'}
2. Also if we want to solve Maximization objective function then we can multiply objective function with negative sign to convert it into minimization objective function and then use above simplex operator to solve it. The output of the solution is convert into maximization by again multipling negative sign.
References:-
1. https://www.britannica.com/topic/simplex-method
2. Mathworks.com
3. Youtube