Randomised Algorithms

摘要: Randomised Algorithms - Lecture 6-7: Linear Programming Page 1 Randomised Algorithms Lecture 6-7: Linear Programming Thomas Sauerwald (tms41@cam.ac.uk) Lent 2022 Page 2 Outline Introduction A Simple Example of a Linear Program Formulating Problems as Linear Programs Standard and Slack Forms Simplex Algorithm Finding an Initial Solution Linear Programming © Thomas Sauerwald Introduction 2 Page 3 Introduction Extended Example: Visualization of SIMPLEX x1 x2 x3 (0, 0, 0) (9, 0, 0) (8.25, 0, 1.5) (8, 4, 0) (0, 12, 0) (0, 0, 4.8) 0 27 27.75 28 12 9.6 Exercise: How many basic solutions (including non-feasible ones) are there? 11 22 33 44 55 66 77 88 99 1010 1111 1212 1313 1414 1515 1616 1717 1818 1919 2020 2121 2222 2323 2424 2525 2626 2727 2828 2929 3030 3131 3232 3333 3434 3535 3636 3737 3838 3939 4040 4141 4242 1 1 1 1 1 1 1 1 1 0.50 0.50 1 0.50 1 1 1 1 1 0.50 0.50 1 …