Craig A. Tovey - Linear Optimization and Duality: A Modern Exposition

First edition published 2021

by CRC Press

6000 Broken Sound Parkway NW, Suite 300, Boca Raton, FL 33487-2742

and by CRC Press

2 Park Square, Milton Park, Abingdon, Oxon, OX14 4RN

2021 Taylor & Francis Group, LLC

CRC Press is an imprint of Taylor & Francis Group, LLC

Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint.

Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers.

For permission to photocopy or use material electronically from this work, access www.copyright.com or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. For works that are not available on CCC please contact mpkbookspermissions@tandf.co.uk

Trademark notice:Product or corporate names may be trademarks or registered trademarks and are used only for identification and explanation without intent to infringe.

ISBN: 978-1-4398-8746-2 (hbk)

ISBN: 978-1-315-11721-8 (ebk

Typeset in Computer Modern font

by KnowledgeWorks Global Ltd.

During the more than 35 years Ive taught linear optimization, Ive found many ways to explain various parts of the material. Eventually, my lectures and in-class activities differed substantially from any of the textbooks available. My students told me that I should write my own book. This text is the result.

It is a classic beginners writing mistake to write a mathematical proof in the order in which one discovered it. (Euler is an exception we learn even from his false starts.) I think it is a similar mistake to write a book in the order in which one learned. All of our standard linear programming textbooks present the material in the order in which it was discovered. First, linear programming formulation. Second, the simplex method. Third, duality and sensitivity analysis. Duality is treated as a difficult add-on to the basic theory. Students end up without knowing duality in their bones. This text brings in duality in are classic dual pairs including the diet problem and 2-person zero sum games. I hope my students will come to know duality in a more profound and instinctive way than I do.

This book departs from convention in another significant way. It is customary when writing a mathematical textbook for all of the results to follow a rigorously proved order. With all due respect to Cauchy et al., however, mathematics is largely empirical. When my students finish the course, I want them to know what is true. At some point they should see rigorous proofs of all results, but the intuitive or empirical knowledge need not come in lockstep with the rigorous derivations. Students see the strong duality theorem in on formulation. They dont see the rigorous proof until chapter 4. Ill state mathematical facts with examples and intuitive explanations pages or chapters before their proofs appear.

When I was in graduate school, I used to argue with my fellow student Richard Stone as to whether algebra or geometry better explained mathematics. According to popular learning mode theories, we were both partly correct: analytic visual learners learn better from algebra; global visual learners learn better from geometry. Thus, a hypothetical student in the room with Richard and me would learn from only one of us. However, the preponderance of independent empirical research contradicts learning mode theory. Instead, people learn the most when they use multiple modes. The hypothetical student would learn more from the two of us than they could from either one. Hence, throughout this book, I explain both visually and algebraically whenever I can. Moreover, I emphasize the relationships between the two, because I believe connecting the two yields an even deeper understanding.