An
Introduction
to
Optimization
WILEY-INTERSCIENCE
SERIES
IN
DISCRETE
MATHEMATICS
AND
OPTIMIZATION
ADVISORY
EDITORS
RONALD
L.
GRAHAM
University
of
California
at San
Diego, U.S.A.
JAN
KAREL LENSTRA
Department
of
Mathematics
and
Computer Science,
Eindhoven University
of
Technology,
Eindhoven,
The
Netherlands
JOEL
H.
SPENCER
+
Institute,
New
York,
New
York,
U.S.A.
A
complete list
of
titles
in
this series appears
at the end of
this
volume.
An
Introduction
to
Optimization
Second Edition
EDWIN
K. P.
CHONG
STANISLAW
H. ZAK
A
Wiley-lnterscience Publication
JOHN
WILEY
&
SONS,
INC.
New
York
/
Chichester
/
Weinheim
/
Brisbane
/
Singapore
/
Toronto
This
text
is
printed
on
acid-free paper.
@
Copyright
©
2001
by
John
Wiley
&
Sons, Inc.
All
rights reserved.
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 Sections
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,
222
Rosewood Drive, Danvers,
MA
01923,
(978)
750-8400,
fax
(978)
750-4744.
Requests
to the
Publisher
for
permission should
be
addressed
to the
Permissions Department, John Wiley
&
Sons, Inc.,
605
Third Avenue,
New
York,
NY
10158-0012, (212) 850-6011,
fax
(212)
850-6008,
E-Mail: PERMREQ
@
W1LEY.COM.
For
ordering
and
customer
service,
call 1-800-CALL-W1LEY.
Library
of
Congress
Cataloging
in
Publication Data
is
available.
ISBN: 0-471-39126-3
Printed
in the
United States
of
America
10
9876543