Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
1 Coursework
This coursework is linked to the Simplex Method. In theory the worst case complexity of the
Simplex Method is 𝒪(𝑛!). That is, the computational cost grows factorially with the number of
decision variables. However, in practical cases the complexity is often much less. Here we will study
how much less.
You will
1. code, in Python, alternative pivoting rules for the Simplex Method;
2. run the different rules on multiple different linear programs with different numbers of decision
variables, outputting the run-time data as an Excel spreadsheet;
3. within Excel, compute the average and worst case run-time as a function of the instance size;
4. within Excel, produce plots showing (quantitatively) the complexity;
5. within LaTeX, write a report analysing the pivoting rules, including your analysis using tables
and plots.
1.1 Algorithms
The Simplex Method performs pivoting operations swapping an index between the basic set 𝐵
and its complement 𝑁. The pivoting rule chooses a (row, column) pair (𝑟, 𝑠). Given that pivot
entry, row operations are performed so that the tableau entry 𝑟𝑠̄𝑎 → 1, and all other entries in that
column, 𝑖𝑠̄𝑎 , 𝑖 ≠ 𝑟 → 0.
In the theory part of the course the pivoting rule shown was Bland’s rule, also called the smallest
subscript rule. This first chooses 𝑠 to be the smallest (column) index with negative reduced costs
𝑠 ̄𝑐 < 0. The rule next chooses 𝑟 to be the smallest (row) index that satisfies the minimum ratio
test.
1.1.1 Largest subscript rule
Symmetry suggests there should be nothing special about using the smallest subscript. A first
guess suggests that using the largest subscript should work just as well.
In the largest subscript rule, we first choose 𝑠 to the the largest column index with negative reduced
costs. The rule next chooses 𝑟 to be the largest row index that satisfies the minimum ratio test.