Section 2.4 Using Sage to Solve Linear Optimization Problems
In practice, most linear algebra computations are done with computers. The presence of tedious technical operations and algorithmic thinking should suggest the same can be done here.
Exploration 2.4.1.
Suppose we wanted to solve the following maximization problem by hand:
|
\(x_1\) |
\(x_2\) |
\(x_3\) |
\(x_4\) |
\(x_5\) |
\(x_6\) |
\(x_7\) |
\(x_8\) |
\(x_9\) |
\(-1\) |
|
|
\(9\) |
\(8\) |
\(3\) |
\(2\) |
\(6\) |
\(6\) |
\(2\) |
\(1\) |
\(4\) |
\(3\) |
\(=-t_1\) |
|
\(5\) |
\(3\) |
\(4\) |
\(4\) |
\(7\) |
\(8\) |
\(1\) |
\(3\) |
\(5\) |
\(5\) |
\(=-t_2\) |
|
\(1\) |
\(1\) |
\(2\) |
\(5\) |
\(4\) |
\(5\) |
\(8\) |
\(4\) |
\(4\) |
\(3\) |
\(=-t_3\) |
|
\(1\) |
\(6\) |
\(2\) |
\(2\) |
\(5\) |
\(5\) |
\(4\) |
\(7\) |
\(3\) |
\(7\) |
\(=-t_4\) |
|
\(5\) |
\(7\) |
\(6\) |
\(8\) |
\(9\) |
\(5\) |
\(4\) |
\(3\) |
\(6\) |
\(5\) |
\(=-t_5\) |
|
\(6\) |
\(2\) |
\(6\) |
\(5\) |
\(8\) |
\(3\) |
\(5\) |
\(5\) |
\(6\) |
\(5\) |
\(=-t_6\) |
|
\(3\) |
\(7\) |
\(5\) |
\(4\) |
\(6\) |
\(3\) |
\(5\) |
\(5\) |
\(6\) |
\(5\) |
\(=-t_7\) |
|
\(8\) |
\(3\) |
\(6\) |
\(4\) |
\(3\) |
\(2\) |
\(2\) |
\(6\) |
\(2\) |
\(8\) |
\(=-t_8\) |
|
\(7\) |
\(7\) |
\(2\) |
\(6\) |
\(5\) |
\(3\) |
\(7\) |
\(8\) |
\(7\) |
\(3\) |
\(=-t_9\) |
|
\(7\) |
\(7\) |
\(2\) |
\(6\) |
\(5\) |
\(3\) |
\(7\) |
\(8\) |
\(7\) |
\(0\) |
\(=f\) |
How annoying would this be?
Very.
Extraordinarily.
Horrifically.
I have nothing to do for the next hour anyway. Hope I don’t forget a minus sign!
Given that we have a developed an algorithm, guaranteed to terminate, using only arithmetic in it’s steps, it seems reasonable to think this can be done via a computer.
Activity 2.4.2.
Let’s start simple, suppose we want to solve:
|
\(x_1\) |
\(x_2\) |
\(-1\) |
|
|
\(2 \) |
\(-1 \) |
\(5\) |
\(=-t_1\) |
|
\(-2 \) |
\(1 \) |
\(2 \) |
\(=-t_2\) |
|
\(3 \) |
\(2 \) |
\(12\) |
\(=-t_3\) |
|
\(5 \) |
\(4 \) |
\(0 \) |
\(=f\) |
(a)
We can enter the above problem into sage via:
(b)
We can plot the feasible region and objective level curves, since this is a 2d problem:
(c)
We could also encode this problem into a dictionary.
We will understand that
\(t_1=x_3, t_2=x_4, t_3=x_5\text{.}\)
(d)
If we want to pivot from
\(x_4\) to
\(x_2\) we can write that as:
Then we can update the dictionary:
We should read this as:
|
\(x_1\) |
\(x_4\) |
\(-1\) |
|
|
\(0 \) |
\(1 \) |
\(7\) |
\(=-x_3\) |
|
\(-2 \) |
\(1 \) |
\(2 \) |
\(=-x_2\) |
|
\(7 \) |
\(=2 \) |
\(8\) |
\(=-x_5\) |
|
\(13 \) |
\(-4 \) |
\(-8 \) |
\(=f\) |
(e)
What pivot should we do next? Encode it below:
(f)
We can check at any point if we have an optimal solution.
Activity 2.4.3.
So if we want to solve:
|
\(x_1\) |
\(x_2\) |
\(x_3\) |
\(x_4\) |
\(-1\) |
|
|
\(8\) |
\(2\) |
\(4\) |
\(5\) |
\(3\) |
\(=-t_1\) |
|
\(-4\) |
\(6\) |
\(2\) |
\(7\) |
\(4\) |
\(=-t_2\) |
|
\(2\) |
\(8\) |
\(4\) |
\(3\) |
\(2\) |
\(=-t_3\) |
|
\(1\) |
\(3\) |
\(2\) |
\(1\) |
\(0\) |
\(=f\) |
(a)
We now encode the above problem in a dictionary.
(b)
We can see who can enter:
If we say, pick
\(x_2\) to enter, see who can legitimately leave:
Then select one to leave
(c)
From here, pick another legitimate pivot and perform it:
(d)
This still seems like a it would be annoying. Why don’t we revisit the original problem?
and then just run the Simplex Algorithm:
Activity 2.4.4.
(a)
Encode the problem into Sage:
(b)
Now let’s run the Simplex Algorithm to see what the deal is:
Activity 2.4.5.
(a)
Encode the problem into Sage:
(b)
We can run the Simplex Algorithm:
(c)
We can also just say what the solution is:
