-
Notifications
You must be signed in to change notification settings - Fork 1
/
NorthwestCornerMethrd.m
118 lines (99 loc) · 2.24 KB
/
NorthwestCornerMethrd.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
format short
clear all
clc
tic
%Input
cost = [2 3 11 7; 1 0 5 1; 5 8 15 9]
fprintf('Supply\n');
A = [6 1 10]
fprintf('Demand\n');
B = [7 5 3 2]
%Check BALANCED/UNBALANCED
if sum(A) == sum(B)
fprintf('Transportation Problem is Balanced\n');
else
fprintf('Unbalanced\n');
if sum(A) < sum(B)
cost(end + 1, :) = zeros(1, size(A, 2));
A(end + 1) = sum(B) - sum(A);
elseif sum(B) < sum(A)
cost(:, end + 1) = zeros(1, size(A, 2))
end
end
x = zeros(size(cost));
[m, n] = size(cost);
BFS = m + n - 1;
i = 1;
j = 1;
l = 0;
while (l < BFS)
if A(i) <= B(j)
x(i, j) = A(i);
B(j) = B(j) - A(i);
i = i + 1;
l = l + 1;
elseif B(j) <= A(i)
x(i, j) = B(j);
A(i) = A(i) - B(j);
j = j + 1;
l = l + 1;
else
break;
end
end
fprintf('Initial BFS = \n');
IB = array2table(x);
disp(IB);
TotalBFS = length(nonzeros(x));
if TotalBFS == BFS
1
if sum(A) == sum(B)
fprintf('Transportation Problem is Balanced\n');
else
fprintf('Unbalanced\n');
if sum(A) < sum(B)
cost(end + 1, :) = zeros(1, size(A, 2));
A(end + 1) = sum(B) - sum(A);
elseif sum(B) < sum(A)
cost(:, end + 1) = zeros(1, size(A, 2))
end
end
x = zeros(size(cost));
[m, n] = size(cost);
BFS = m + n - 1;
i = 1;
j = 1;
l = 0;
while (l < BFS)
if A(i) <= B(j)
x(i, j) = A(i);
B(j) = B(j) - A(i);
i = i + 1;
l = l + 1;
elseif B(j) <= A(i)
x(i, j) = B(j);
A(i) = A(i) - B(j);
j = j + 1;
l = l + 1;
else
break;
end
end
fprintf('Initial BFS = \n');
IB = array2table(x);
disp(IB);
TotalBFS = length(nonzeros(x));
if TotalBFS == BFS
fprintf('Initial BFS is Non-Degenerate \n');
else
fprintf('Initial BFS is Degenerate \n');
end
Initialcost = sum(sum(cost .* x));
fprintf('Initial BFS Cost = %d\n', Initialcost);
else
fprintf('Initial BFS is Degenerate \n');
end
Initialcost = sum(sum(cost .* x));
fprintf('Initial BFS Cost = %d\n', Initialcost);
Elapsed_time = toc
fprintf('Ishan Gupta-19BCE7467')