Linear and Network Programming
A
AY22/23 S2
This courses is all about solving linear problems. In 3D space, this means finding the most optimal point on a particular polyhedron.
We first learn how to model the problem in terms of linear equations and inequalities. This creates our polyhedron. From here, we apply something known as the Simplex Method, which is a systematic way to solve a system such as this. There's quite a lot of edge cases you need to be aware of, such as degeneracy, unboundedness, and infeasibility. These are all very important concepts, and you'll need to be able to identify them quickly, as they can affect the way you solve the problem.
The next part of the lecture deals with Duality theorems. Basically, when solving a linear problem, you need to strive for two things. Firstly, your solution needs to be feasible, which means it obeys all the constraints you give. Secondly, your solution needs to be optimal, which means it is the best solution you can get. Essentially, the conventional Simplex method will ensure that your solution is always feasible, and we just need to nudge it to be an optimal solution, On the other hand, the dual method will ensure that your solution is always optimal, and we just need to nudge it to be a feasible solution. You need lots of practice with the two methods, as they are both important for the next topic.
Combining what you've learnt so far, you'll be able to solve sensitivity analysis problems. This topic deals with understanding how the optimal solution changes when you change the coefficients of the problem. For example, if you shift this constraint, how does the solution change? On the other hand, if you change the objective function, how does the solution change? For this, you'll need to run the Simplex or the Dual Simplex method a few times to find your answer. Your job is to find out which one.
The question design is very based in the real-world, so you'll need to master the art of mathematical modeling. Identify the constraints, objective function, and variables, and you'll be fine. No non-standard questions, but just be sure to be accurate with your calculations, as the questions are quite long and tedious.
Otherwise, workload is fine, with a few assignments, and exams.
Oh did I forget about Network Programming? Yes (in Uncle Roger voice).
Loading comments...