Edwin K. P. Chong - An Introduction to Optimization

AN INTRODUCTION TO OPTIMIZATION

WILEY SERIES IN DISCRETE MATHEMATICS AND OPTIMIZATION

AARTS AND KORST Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing

AARTS AND LENSTRA Local Search in Combinatorial Optimization

ALON AND SPENCER The Probabilistic Method, Third Edition

ANDERSON AND NASH Linear Programming in Infinite-Dimensional Spaces: Theory and Application

ARLINGHAUS, ARLINGHAUS, AND HARARY Graph Theory and Geography: An Interactive View E-Book

AZENCOTT Simulated Annealing: Parallelization Techniques

BARTHLEMY AND GUNOCHE Trees and Proximity Representations

BAZARRA, JARVIS, AND SHERALI Linear Programming and Network Flows

BRUEN AND FORCINITO Cryptography, Information Theory, and Error-Correction: A Handbook for the 21st Century

CHANDRU AND HOOKER Optimization Methods for Logical Inference

CHONG AND K An Introduction to Optimization, Fourth Edition

COFFMAN AND LUEKER Probabilistic Analysis of Packing and Partitioning Algorithms

COOK, CUNNINGHAM, PULLEYBLANK, AND SCHRIJVER Combinatorial Optimization

DASKIN Network and Discrete Location: Modes, Algorithms and Applications

DINITZ AND STINSON Contemporary Design Theory: A Collection of Surveys

DU AND KO Theory of Computational Complexity

ERICKSON Introduction to Combinatorics

GLOVER, KLINGHAM, AND PHILLIPS Network Models in Optimization and Their Practical Problems

GOLSHTEIN AND TRETYAKOV Modified Lagrangians and Monotone Maps in Optimization

GONDRAN AND MINOUX Graphs and Algorithms (Translated by S. Vajd)

GRAHAM, ROTHSCHILD, AND SPENCER Ramsey Theory, Second Edition

GROSS AND TUCKER Topological Graph Theory

HALL Combinatorial Theory, Second Edition

HOOKER Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction

IMRICH AND KLAVAR Product Graphs: Structure and Recognition

JANSON, LUCZAK, AND RUCINSKI Random Graphs

JENSEN AND TOFT Graph Coloring Problems

KAPLAN Maxima and Minima with Applications: Practical Optimization and Duality

LAWLER, LENSTRA, RINNOOY KAN, AND SHMOYS, Editors The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization

LAYWINE AND MULLEN Discrete Mathematics Using Latin Squares

LEVITIN Perturbation Theory in Mathematical Programming Applications

MAHMOUD Evolution of Random Search Trees

MAHMOUD Sorting: A Distribution Theory

MARTELLI Introduction to Discrete Dynamical Systems and Chaos

MARTELLO AND TOTH Knapsack Problems: Algorithms and Computer Implementations

McALOON AND TRETKOFF Optimization and Computational Logic

MERRIS Combinatorics, Second Edition

MERRIS Graph Theory

MINC Nonnegative Matrices

MINOUX Mathematical Programming: Theory and Algorithms (Translated by S. Vajd)

MIRCHANDANI AND FRANCIS, Editors Discrete Location Theory

NEMHAUSER AND WOLSEY Integer and Combinatorial Optimization

NEMIROVSKY AND YUDIN Problem Complexity and Method Efficiency in Optimization (Translated by E. R. Dawson)

PACH AND AGARWAL Combinatorial Geometry

PLESS Introduction to the Theory of Error-Correcting Codes, Third Edition

ROOS AND VIAL Ph. Theory and Algorithms for Linear Optimization: An Interior Point Approach

SCHEINERMAN AND ULLMAN Fractional Graph Theory: A Rational Approach to the Theory of Graphs

SCHIFF Cellular Automata: A Discrete View of the World

SCHRIJVER Theory of Linear and Integer Programming

SPALL Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control

STIEBITZ, SCHEIDE, TOFT, AND FAVRHOLDT Graph Edge Coloring: Vizings Theorem and Goldbergs Conjecture

SZPANKOWSKI Average Case Analysis of Algorithms on Sequences

TOMESCU Problems in Combinatorics and Graph Theory (Translated by R.A. Melter)

TUCKER Applied Combinatorics, Second Edition

WOLSEY Integer Programming

YE Interior Point Algorithms: Theory and Analysis

Copyright 2013 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New Jersey

Published simultaneously in Canada

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com . Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission .

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com .

Library of Congress Cataloging-in-Publication Data

Chong, Edwin Kah Pin.
An introduction to optimization / Edwin K. P. Chong, Colorado State University, Stanislaw H. Zak, Purdue University. Fourth edition.
pages cm
Summary: The purpose of the book is to give the reader a working knowledge of optimization theory and methods Provided by publisher.
Includes bibliographical references and index.
ISBN 978-1-118-27901-4 (hardback)
1. Mathematical optimization. I. Zak, Stanislaw H. II. Title.
QA402.5.C476 2012
519.6dc23
2012031772

To my wife, Yat-Yee,
and to my parents, Paul
and Julienne Chong.
Edwin K. P. Chong

To JMJ; my wife,
Mary Ann; and my
parents, Janina and
Konstanty ak.
Stanislaw H. ak

PREFACE

Optimization is central to any problem involving decision making, whether in engineering or in economics. The task of decision making entails choosing among various alternatives. This choice is governed by our desire to make the best decision. The measure of goodness of the alternatives is described by an objective function or performance index. Optimization theory and methods deal with selecting the best alternative in the sense of the given objective function.