1
00:00:00,190 --> 00:00:02,620
So, discrete optimization, again, linear 
programming part two. 

2
00:00:02,620 --> 00:00:07,070
Okay, so this is getting really exciting. 
Okay, so what we saw last time was the 

3
00:00:07,070 --> 00:00:10,420
geometric view and linear programming and 
what we going to do now is do the 

4
00:00:10,420 --> 00:00:13,660
connection between this geometric view 
and the algebraic view. 

5
00:00:13,660 --> 00:00:16,890
Okay, so we going to link the two and 
this is where this thing gets really 

6
00:00:16,890 --> 00:00:20,320
nice. 
Okay, so remember what we saw last time, 

7
00:00:20,320 --> 00:00:25,150
is that we could solve this problem from 
a, from a geometry standpoint by simply 

8
00:00:25,150 --> 00:00:28,630
looking at all the vertices, and taking 
the one which is the best value for the 

9
00:00:28,630 --> 00:00:31,510
objective function, okay? 
Of course you know it's like, oh, how do 

10
00:00:31,510 --> 00:00:33,890
I get these vertices? 
You know it's like, hey it's crazy right, 

11
00:00:33,890 --> 00:00:35,700
writing an algorithm to get these 
vertices. 

12
00:00:35,700 --> 00:00:36,990
doesn't seem so simple. 
Okay. 

13
00:00:36,990 --> 00:00:39,460
We can do that by hand. 
But how do we do that, you know, on a 

14
00:00:39,460 --> 00:00:40,990
computer? 
And that's the key point here. 

15
00:00:40,990 --> 00:00:44,200
Okay? 
So the simplex algorithm is essentially 

16
00:00:44,200 --> 00:00:48,280
a, a, an intelligent way of actually 
exploring these vertices. 

17
00:00:48,280 --> 00:00:52,100
And as I told you, you know, this is 
where the connection between the geometry 

18
00:00:52,100 --> 00:00:56,160
and the algebraic view, the, is, is 
really interesting. 

19
00:00:56,160 --> 00:00:58,560
Okay. 
So once again, I told you that, you know, 

20
00:00:58,560 --> 00:01:01,230
this algorithm was invented by Charles 
Dantzig. 

21
00:01:01,230 --> 00:01:04,380
And one of the things you have to 
understand is that this, this algorithm 

22
00:01:04,380 --> 00:01:09,970
is actually still, after, you know, like, 
60, 65 years, actually, wow, this is 65 

23
00:01:09,970 --> 00:01:13,650
years. 
After 65 years it's still a complete 

24
00:01:13,650 --> 00:01:16,900
enigma, right. 
It works incredibly well in practice, 

25
00:01:16,900 --> 00:01:19,820
always solving this problem really fast 
in general. 

26
00:01:19,820 --> 00:01:23,920
But it does an exponential worse case so 
in the worst case it's terrible right. 

27
00:01:23,920 --> 00:01:28,320
But this worst case doesn't seem to 
happen in almost never okay. 

28
00:01:28,320 --> 00:01:31,640
So you have to you can construct an 
example where it can happen but it don't 

29
00:01:31,640 --> 00:01:35,160
seem to happen in practice. 
So from a theoretical standpoint, nobody 

30
00:01:35,160 --> 00:01:39,910
really understands why this is the case. 
And they are really some very nice 

31
00:01:39,910 --> 00:01:43,530
theoretical issue, which are very simply 
state, that nobody knows the answer to. 

32
00:01:43,530 --> 00:01:45,580
Okay? 
So very interesting algorithm. 

33
00:01:45,580 --> 00:01:49,180
And so what I'm going to do today is to 
actually Try to present this thing in an 

34
00:01:49,180 --> 00:01:51,620
intuitive way, what the simplex algorithm 
do. 

35
00:01:51,620 --> 00:01:55,610
And so this is, this is the wa-, this is 
the way I would, you know, I could 

36
00:01:55,610 --> 00:01:57,790
characterize this algorithm. 
Okay. 

37
00:01:57,790 --> 00:02:01,810
It's very simple, right? 
So what you want to do is to be on top of 

38
00:02:01,810 --> 00:02:02,660
the world. 
Okay. 

39
00:02:02,660 --> 00:02:06,220
So that's the goal, okay? 
The goal is to go, to be on top of the 

40
00:02:06,220 --> 00:02:08,580
world. 
Now, I'm going to give you five facts, 

41
00:02:08,580 --> 00:02:12,585
okay, that will allow you to go, to be on 
top of the world, okay? 

42
00:02:12,585 --> 00:02:17,740
The first fact that I'm going to give you 
is that the top of the world is the top 

43
00:02:17,740 --> 00:02:20,844
of a mountain, okay? 
Basic fact, right? 

44
00:02:20,844 --> 00:02:24,740
No, the string in fact, is the most 
interesting one, okay? 

45
00:02:24,740 --> 00:02:29,230
So the top of the mountain is a 
beautiful, fantastic spot, okay? 

46
00:02:29,230 --> 00:02:31,980
We are going to be talking about 
beautiful, fantastic spot all the time. 

47
00:02:31,980 --> 00:02:36,910
And I call this guy BFS, okay? 
So, beautiful, fantastic spot, okay? 

48
00:02:36,910 --> 00:02:40,180
So you have to to know, okay, that the 
top of the world is at the top of a 

49
00:02:40,180 --> 00:02:44,160
mountain, and the top of a mountain is a 
beautiful fantastic spot. 

50
00:02:44,160 --> 00:02:46,280
Okay? 
Now, the third thing that I'm going to 

51
00:02:46,280 --> 00:02:50,500
tell you, okay, the third fact, is that 
you can move from a beautiful fantastic 

52
00:02:50,500 --> 00:02:53,250
point to a neighboring beautiful 
fantastic spot. 

53
00:02:53,250 --> 00:02:55,880
That's easy to do. 
Okay, you are at the beautiful fantastic 

54
00:02:55,880 --> 00:02:57,100
point. 
You see another one. 

55
00:02:57,100 --> 00:02:58,780
You can move there. 
Okay. 

56
00:02:58,780 --> 00:03:02,980
So, and then the fourth fact is that, and 
this is important, when you are at the 

57
00:03:02,980 --> 00:03:05,860
top of the world, you know you are at the 
top of the world. 

58
00:03:05,860 --> 00:03:09,560
Okay, fact four, okay. 
And then the last fact is that if you 

59
00:03:09,560 --> 00:03:14,260
aren't a Beautiful Fantastic Spot, there 
will always be an opportunity to move to 

60
00:03:14,260 --> 00:03:17,190
a higher Beautiful Fantastic Spot. 
Okay? 

61
00:03:17,190 --> 00:03:21,130
So if you understand these five points, 
okay, so you understand linear 

62
00:03:21,130 --> 00:03:22,710
programming. 
Okay? 

63
00:03:22,710 --> 00:03:24,480
So this is as simple as that. 
Okay? 

64
00:03:24,480 --> 00:03:27,200
You know that the top of the world is a 
top of a mountain. 

65
00:03:27,200 --> 00:03:30,510
You know that the top of a mountain is a 
Beautiful Fantastic Spot. 

66
00:03:30,510 --> 00:03:33,880
That you can move from Beautiful 
Fantastic Spot to another neighboring 

67
00:03:33,880 --> 00:03:36,270
Beautiful Fantastic Point. 
When you are on top of the world, you 

68
00:03:36,270 --> 00:03:38,740
know it, okay. 
And then, every time you are at a 

69
00:03:38,740 --> 00:03:44,170
beautiful, fantastic spot, there is a way 
for you to go to a more, to a higher, you 

70
00:03:44,170 --> 00:03:48,360
know, beautiful, fantastic spot. 
Now, so this is too simple, right, and, 

71
00:03:48,360 --> 00:03:51,460
and we have to make it complicated. 
And that's what we're going to, that's 

72
00:03:51,460 --> 00:03:54,610
what I'm going to do, okay. 
I'm going to do on the next slide, okay. 

73
00:03:54,610 --> 00:03:58,730
I'm going to take these facts and make 
them a little bit more complicated, okay. 

74
00:03:58,730 --> 00:04:01,790
Because otherwise, people will say, what 
you do in science is too easy. 

75
00:04:01,790 --> 00:04:03,690
I mean, we're not the only one to do that 
right? 

76
00:04:03,690 --> 00:04:08,020
So you know, a doctor would talk abut the 
distant part of your fibula. 

77
00:04:08,020 --> 00:04:11,110
What is that, right? 
So can't they say, this is the part of 

78
00:04:11,110 --> 00:04:12,690
your fibula next to your ankle? 
No. 

79
00:04:12,690 --> 00:04:16,510
They would say, beautifully, you know the 
distant part of your fibula is the 

80
00:04:16,510 --> 00:04:17,300
problem. 
Right? 

81
00:04:17,300 --> 00:04:19,420
Anyway. 
So, lawyers sound the same right? 

82
00:04:19,420 --> 00:04:22,378
So when you buy a hose in the US they 
would say, they would write things like 

83
00:04:22,378 --> 00:04:26,130
expected performance. 
And you say, wow, what is this expected 

84
00:04:26,130 --> 00:04:28,130
performance? 
That just means you have to buy the host, 

85
00:04:28,130 --> 00:04:30,110
okay? 
But, you know, so we going to do the 

86
00:04:30,110 --> 00:04:31,580
same. 
We're going to take this very simple 

87
00:04:31,580 --> 00:04:35,410
algorithm and make it look complicated, 
such that people believe we are really 

88
00:04:35,410 --> 00:04:36,130
clever. 
Okay? 

89
00:04:36,130 --> 00:04:40,310
So this is what we're going to do, okay? 
So, we, we, instead of saying we want to 

90
00:04:40,310 --> 00:04:42,850
be one top of the world, we want to solve 
a linear program. 

91
00:04:42,850 --> 00:04:45,560
Okay? 
Fact number one, you know, what I told 

92
00:04:45,560 --> 00:04:48,500
you is that the top of the world is at 
the top of the mountain. 

93
00:04:48,500 --> 00:04:51,490
That's basically telling you that the 
optimal solution is located to the 

94
00:04:51,490 --> 00:04:54,160
vertex. 
So when you think of a vertex, think the 

95
00:04:54,160 --> 00:04:55,405
top of a mountain. 
Right? 

96
00:04:55,405 --> 00:05:01,110
Now, a vertex, okay, is actually a 
beautiful, fantastic spot but we can't 

97
00:05:01,110 --> 00:05:05,250
talk about beautiful, fantastic spot so 
we going to say it's a basic feasible 

98
00:05:05,250 --> 00:05:08,200
solution. 
Okay, but let's say BFS, you know, you 

99
00:05:08,200 --> 00:05:11,444
can think BFS, basic feasible solution or 
beautiful fantastic spot. 

100
00:05:11,444 --> 00:05:14,940
Okay, and then the three other facts are 
going to be essentially the same, because 

101
00:05:14,940 --> 00:05:18,870
we are talking about BFSs, right? 
So we can move from a BFS to another one. 

102
00:05:18,870 --> 00:05:22,660
Beautiful fantastic boat to a beautiful 
fantastic boat, a basic feasible solution 

103
00:05:22,660 --> 00:05:25,940
to another basic feasible solution. 
You know that you can detect if a 

104
00:05:25,940 --> 00:05:28,960
beautiful fantastic spot is at the top of 
the world, okay. 

105
00:05:28,960 --> 00:05:32,200
you, you can detect it so basic feasible 
solution is optimal. 

106
00:05:32,200 --> 00:05:36,410
And then you can move from any BFS to a 
not a BFS which has a better cost. 

107
00:05:36,410 --> 00:05:38,970
Okay? 
Well, smaller cost if you minimize, you 

108
00:05:38,970 --> 00:05:40,900
know, higher cost if you maximize. 
Okay. 

109
00:05:40,900 --> 00:05:43,900
So this is once again, a little bit more 
complicated now. 

110
00:05:43,900 --> 00:05:46,990
We are talking about this basic feasible 
solution, that we don't really know what 

111
00:05:46,990 --> 00:05:49,200
they are. 
But this is the same thing as what I've 

112
00:05:49,200 --> 00:05:52,710
shown you on the previous slide, okay? 
But this is the simplex algorithm. 

113
00:05:52,710 --> 00:05:57,370
So, what I'm going to do in the lecture 
is going to, through these various facts 

114
00:05:57,370 --> 00:05:59,650
and telling, and explaining how they 
work. 

115
00:05:59,650 --> 00:06:02,210
Okay? 
So, we know what a linear program is, 

116
00:06:02,210 --> 00:06:04,430
right? 
So, minimizing this linear function and 

117
00:06:04,430 --> 00:06:05,900
then these constraints. 
Okay? 

118
00:06:05,900 --> 00:06:07,690
And all the variables have to be graded 
on 0. 

119
00:06:07,690 --> 00:06:09,930
We'll come back to that, this is an 
important part, okay? 

120
00:06:09,930 --> 00:06:12,850
So, so let's start, let's back up a 
little bit. 

121
00:06:12,850 --> 00:06:16,610
Okay, I'm back, backing up, okay, right? 
And so, what we are looking at here, 

122
00:06:16,610 --> 00:06:19,240
first. 
We have a system of linear equation and 

123
00:06:19,240 --> 00:06:21,230
we want to solve it. 
How do we do that? 

124
00:06:21,230 --> 00:06:23,290
How do we do that, okay. 
Go back to high school. 

125
00:06:23,290 --> 00:06:26,580
That's what we did, right? 
And so essentially what you do is you 

126
00:06:26,580 --> 00:06:30,230
perform you know, Gaussian elimination to 
actually solve a system of linear 

127
00:06:30,230 --> 00:06:33,770
equations like that, right? 
So you basically express some of the 

128
00:06:33,770 --> 00:06:36,270
variables in terms of the other ones, 
okay. 

129
00:06:36,270 --> 00:06:41,040
And so you basically isolate a bunch of 
variables, x one to x n and you express 

130
00:06:41,040 --> 00:06:45,970
them in terms of the other variables. 
And so this is basically what we call a 

131
00:06:45,970 --> 00:06:50,600
basic solution. 
The variable on the left sides are going 

132
00:06:50,600 --> 00:06:54,165
to be called the basic variables. 
Sometimes we tell them they are the basic 

133
00:06:54,165 --> 00:06:56,400
Right? 
So, but they are the basic variable. 

134
00:06:56,400 --> 00:06:58,080
Okay? 
And we going to love these guys. 

135
00:06:58,080 --> 00:06:58,750
Okay? 
You'll see why. 

136
00:06:58,750 --> 00:07:02,390
And the, and the other variables, I call 
the non basic variables. 

137
00:07:02,390 --> 00:07:04,500
Okay? 
They are the guys that we don't really 

138
00:07:04,500 --> 00:07:05,340
care about. 
Okay? 

139
00:07:05,340 --> 00:07:08,290
And then of course you have the bs which 
are the values that we're going to give 

140
00:07:08,290 --> 00:07:09,830
to the basic variables. 
Okay? 

141
00:07:09,830 --> 00:07:11,640
So, this is a basic solution. 
Why? 

142
00:07:11,640 --> 00:07:14,830
Because essentially we're going to take 
the basic variables that you see there, 

143
00:07:14,830 --> 00:07:17,380
we're going to give them as values, the 
b's. 

144
00:07:17,380 --> 00:07:20,180
Okay? 
And then we're going to take the basic 

145
00:07:20,180 --> 00:07:23,750
variable, the nonbasic variables and 
we're going to give them all zeros, okay? 

146
00:07:23,750 --> 00:07:27,000
And if we do that obviously these 
equations are going to be satisfied, 

147
00:07:27,000 --> 00:07:30,410
right? 
I'm basically saying xi is equal to b, x1 

148
00:07:30,410 --> 00:07:34,490
is equal to b1, you know, and xm is equal 
to bm and all these guys are zeros so 

149
00:07:34,490 --> 00:07:37,380
these equations are obviously satisfied. 
Okay? 

150
00:07:37,380 --> 00:07:40,190
So this is a basic solution. 
Okay? 

151
00:07:40,190 --> 00:07:43,450
So I'm basically taking all the xi giving 
them the bi. 

152
00:07:43,450 --> 00:07:46,260
I'm taking out all the non-basic 
variables, assigning them to zero. 

153
00:07:46,260 --> 00:07:49,510
So in a sense, think about this. 
In this is some of equation, there are 

154
00:07:49,510 --> 00:07:53,270
bunch of variables that are all zeros and 
that happens all the time in linear 

155
00:07:53,270 --> 00:07:56,060
programming, right? 
So you will have a massive amount of 

156
00:07:56,060 --> 00:08:00,310
variables typically assigned to zero and 
then these beautiful basic variables are 

157
00:08:00,310 --> 00:08:02,920
going to be assigned the bi's that you 
see there, okay? 

158
00:08:02,920 --> 00:08:06,234
So that's a basic solution, okay? 
We'll talk about basic solution. 

159
00:08:06,234 --> 00:08:09,860
Now remember a beautiful fantastic post 
and this F in there. 

160
00:08:09,860 --> 00:08:12,270
Right. 
So this is feasible or fantastic okay. 

161
00:08:12,270 --> 00:08:17,670
So you going to be fantastic or feasible 
when you satisfy these constraints, okay. 

162
00:08:17,670 --> 00:08:20,470
So you have to make sure that all the 
variables. 

163
00:08:20,470 --> 00:08:24,230
All the variables here have to be greater 
than 0 okay. 

164
00:08:24,230 --> 00:08:26,900
And so how do you that? 
Well, you know for the non-basic 

165
00:08:26,900 --> 00:08:30,130
variables it's easy, right? 
So all these guys are already zero. 

166
00:08:30,130 --> 00:08:34,390
But you want to make sure that these guys 
are assigned non-negative values, okay? 

167
00:08:34,390 --> 00:08:39,920
And so that means testing when you 
actually isolate the X1 to XN, that these 

168
00:08:39,920 --> 00:08:43,860
guys are actually non-negative, okay? 
And if they are non-negative, what you 

169
00:08:43,860 --> 00:08:47,484
have is a beautiful fantastic spot. 
You have a basic feasible solution. 

170
00:08:47,484 --> 00:08:49,535
Okay? 
So that's what you have here. 

171
00:08:49,535 --> 00:08:52,570
Okay? 
So a basic feasible solution is a 

172
00:08:52,570 --> 00:08:56,440
solution where you isolate some of the 
variables, x 1 to x m. 

173
00:08:56,440 --> 00:08:59,400
It can be any one of these variables, 
right? 

174
00:08:59,400 --> 00:09:02,980
So they are called the basic variables. 
They are assigned these bs that, you 

175
00:09:02,980 --> 00:09:06,760
know, that you have, and all of the 
non-basic variables which are there are 

176
00:09:06,760 --> 00:09:09,920
assigned to 0. 
Okay, basic feasible solution, okay. 

177
00:09:09,920 --> 00:09:13,540
You're going to say, why this, this guy 
actually obsessed with this and you'll 

178
00:09:13,540 --> 00:09:17,530
see why in a moment, okay. 
So, how do we find a beautiful, fantastic 

179
00:09:17,530 --> 00:09:20,020
spot? 
We select environments, okay. 

180
00:09:20,020 --> 00:09:22,970
So there will be the basic feasible, the 
basic variables. 

181
00:09:22,970 --> 00:09:25,800
We re express them in terms of the other 
ones, okay. 

182
00:09:25,800 --> 00:09:29,140
Not in terms of each other, right. 
Only in terms of the non basic variables, 

183
00:09:29,140 --> 00:09:31,040
okay. 
We can do that easily by performing 

184
00:09:31,040 --> 00:09:35,065
Gaussian elimination, okay. 
And if all the non, if all the b's are 

185
00:09:35,065 --> 00:09:37,910
nonnegative, we know that we have a basic 
feasible solution. 

186
00:09:37,910 --> 00:09:41,110
Okay. 
So, you're going to tell me yeah, yeah, 

187
00:09:41,110 --> 00:09:43,040
yeah, yeah, yeah. 
But you are dealing with equations now. 

188
00:09:43,040 --> 00:09:46,520
But in my simplex algorithm, I mean 
inequalities, right? 

189
00:09:46,520 --> 00:09:49,180
So what are we going to do? 
Well, you know there is a very simple 

190
00:09:49,180 --> 00:09:50,360
thing that we can do. 
Okay? 

191
00:09:50,360 --> 00:09:53,680
If you have a set of inequalities like 
this, okay? 

192
00:09:53,680 --> 00:09:56,650
What you can do is always you can add 
some new variable okay? 

193
00:09:56,650 --> 00:10:01,170
From S1 to SM, okay? 
And transform this inequalities into, 

194
00:10:01,170 --> 00:10:03,470
into equations. 
okay? 

195
00:10:03,470 --> 00:10:08,180
So this adds one to the left and it has 
to be greater or equal to zero, so you 

196
00:10:08,180 --> 00:10:13,400
add them and there is one for everyone on 
of the contraints. 

197
00:10:13,400 --> 00:10:16,820
They are all forced to be greater than 
zero and we call these guys the slack 

198
00:10:16,820 --> 00:10:20,020
variables. 
And the intuition here is very simple, 

199
00:10:20,020 --> 00:10:24,550
look at the expression you have there. 
They will have a value when you assign 

200
00:10:24,550 --> 00:10:27,830
the basic variables, and then there will 
be the value of the b's. 

201
00:10:27,830 --> 00:10:30,310
Okay. 
So typically they have to be smaller or 

202
00:10:30,310 --> 00:10:33,020
equal to that. 
So they may, so either they are equal, in 

203
00:10:33,020 --> 00:10:36,250
which case the slack variable is going to 
be zero, otherwise the slack variable is 

204
00:10:36,250 --> 00:10:40,440
going to be the difference between the b 
and then the, you know the left hand 

205
00:10:40,440 --> 00:10:41,140
side. 
Okay. 

206
00:10:41,140 --> 00:10:45,750
So essentially they are making, they are 
transforming this inequality, okay. 

207
00:10:45,750 --> 00:10:49,930
They are transforming these inequalities 
into equations by picking up the slack, 

208
00:10:49,930 --> 00:10:52,530
and really having a variable capturing 
that slack, okay? 

209
00:10:52,530 --> 00:10:55,610
So, very simple, right? 
So if you have a long, if you have a 

210
00:10:55,610 --> 00:10:59,520
linear program with inequalities, you can 
transform these inequalities to 

211
00:10:59,520 --> 00:11:03,690
equations, and that's what we want to do, 
when we are actually implementing this 

212
00:11:03,690 --> 00:11:05,430
method on a computer. 
Right? 

213
00:11:05,430 --> 00:11:08,650
Okay? 
So, once again, to summarize, you start 

214
00:11:08,650 --> 00:11:11,440
with your linear programs, you take all 
these inequalities, okay? 

215
00:11:11,440 --> 00:11:15,690
You have slack variables and you have 
equations, and now you select m 

216
00:11:15,690 --> 00:11:18,590
variables, so these are going to be the 
basic variables. 

217
00:11:18,590 --> 00:11:22,270
You re-express them in terms of the 
non-basic variables, performing Gaussian 

218
00:11:22,270 --> 00:11:25,740
elimination and then if all the b's are 
non-negative you have a basic feasible 

219
00:11:25,740 --> 00:11:29,784
solution, you have a beautiful fantastic 
spot, okay? 

220
00:11:29,784 --> 00:11:33,590
So, so, now, this is the key point. 
Okay. 

221
00:11:33,590 --> 00:11:36,270
This is the most important fact that you 
need to know. 

222
00:11:36,270 --> 00:11:40,270
A vertex, in the geometrical sense that 
I've shown you in the last lecture, is 

223
00:11:40,270 --> 00:11:44,100
actually a beautiful, fantastic spot. 
It's a basic feasible solution. 

224
00:11:44,100 --> 00:11:46,370
Okay. 
So in a sense now, we have a beautiful 

225
00:11:46,370 --> 00:11:49,000
algorithm. 
I'm, I'm giving you an algorithm, right, 

226
00:11:49,000 --> 00:11:51,300
that you can actually code in a computer. 
Right? 

227
00:11:51,300 --> 00:11:55,045
So the naive algorithm that we have now 
is that we just want to look at all the 

228
00:11:55,045 --> 00:11:55,900
vertices. 
Okay. 

229
00:11:55,900 --> 00:11:58,990
But the vertices are basically a basic 
feasible solution. 

230
00:11:58,990 --> 00:12:03,330
So you can just enumerate all these basic 
feasible solution, and then take the one 

231
00:12:03,330 --> 00:12:05,780
which is best. 
So you generate all the basic feasible 

232
00:12:05,780 --> 00:12:07,160
solution. 
How do you do that? 

233
00:12:07,160 --> 00:12:09,030
Well that's just what I explained to you, 
right? 

234
00:12:09,030 --> 00:12:11,375
You isolate end variables. 
You express them in terms of the 

235
00:12:11,375 --> 00:12:14,950
non-basic variables, okay? 
And then you perform Gaussian elimination 

236
00:12:14,950 --> 00:12:16,660
and then you can test if this is 
feasible. 

237
00:12:16,660 --> 00:12:19,490
If it is feasible, you have a basic 
feasible solution, okay? 

238
00:12:19,490 --> 00:12:22,920
So I have noticed, you know, naive 
algorithm which you can implement on a 

239
00:12:22,920 --> 00:12:28,320
computer which will generate all these 
basic feasible solutions and for everyone 

240
00:12:28,320 --> 00:12:31,590
on of them you can computer a value of 
the objective function. 

241
00:12:31,590 --> 00:12:37,860
You essnetially plug the values that are 
in that solution Okay? 

242
00:12:37,860 --> 00:12:40,540
And then you select the one which has the 
best cost. 

243
00:12:40,540 --> 00:12:43,540
Now how many of these? 
Well, that's the issue, right? 

244
00:12:43,540 --> 00:12:46,410
So they will be a very large number of 
them, right? 

245
00:12:46,410 --> 00:12:50,710
It's like picking up m variables inside 
the m, and you want to explore all these 

246
00:12:50,710 --> 00:12:51,620
combinations. 
Okay? 

247
00:12:51,620 --> 00:12:52,960
So there are many of them. 
Okay? 

248
00:12:52,960 --> 00:12:58,140
And so, in practice, the naive algorithm 
that I'm showing you here Is not going to 

249
00:12:58,140 --> 00:13:01,450
work you know, nicely from a 
computational standpoint, from a 

250
00:13:01,450 --> 00:13:04,290
performance standpoint. 
But we'll see how to improve it, you 

251
00:13:04,290 --> 00:13:07,260
know, in the next lecture. 
Okay? 

252
00:13:07,260 --> 00:13:09,700
So, basically summarizing what we have 
seen. 

253
00:13:09,700 --> 00:13:12,540
Okay? 
So, what you want to do. 

254
00:13:12,540 --> 00:13:14,500
Okay? 
Is to be on top of the world. 

255
00:13:14,500 --> 00:13:15,890
Is basically a vertex. 
Okay? 

256
00:13:15,890 --> 00:13:19,650
And what you can do To get to. 
And a vertex is a basic feasible 

257
00:13:19,650 --> 00:13:23,290
solution. 
And getting a basic feasible solution is 

258
00:13:23,290 --> 00:13:26,660
actually pretty easy. 
It basically consists in isolated end 

259
00:13:26,660 --> 00:13:30,380
variables, okay, expressing them in terms 
of the other one, and testing the value 

260
00:13:30,380 --> 00:13:32,580
that you assigned to them is actually not 
negative. 

261
00:13:32,580 --> 00:13:34,620
Okay? 
We'll see a more clever way of actually 

262
00:13:34,620 --> 00:13:39,620
exploring all these vertices, basic 
feasible solutions You know next time. 

263
00:13:39,620 --> 00:13:40,770
Thank you very much.