Kolman B., Beck R. - Elementary Linear Programming with Applications (Elsevier, 1995).pdf - Algebra - besia86

Elementary Linear Programming with

Applications

by Bernard Kolman , Robert E. Beck

• Textbook Hardcover - REV

• ISBN: 012417910X; ISBN-13: 9780124179103

• Format: Textbook Hardcover, 449pp

• Publisher: Elsevier Science & Technology Books

• Pub. Date: June 1995

Preface

Classical optimization techniques have been widely used in engineering

and the physical sciences for a long time. They arose from attempts to

determine the "best" or "most desirable" solution to a problem. Toward

the end of World War II, models for many problems in the management

sciences were formulated and algorithms for their solutions were devel-

oped. In particular, the new areas of linear, integer, and nonlinear pro-

gramming and network flows were developed. These new areas of applied

mathematics have succeeded in saving billions of dollars by enabling the

model builder to find optimal solutions to large and complex applied

problems. Of course, the success of these modem optimization techniques

for real problems is due primarily to the rapid development of computer

capabilities in the past 40 years. Computational power has doubled every

12 months since 1964 (Moore's Law, Joy's Law) allowing the routine

solution today of problems whose complexity was overwhelming even a few

years ago.

With the increasing emphasis in mathematics on relevance to real-world

problems, some of the areas of modem optimization mentioned above

xii

Preface

have rapidly become part of the undergraduate curriculum for business,

engineering, computer science, and mathematics students.

This book presents a survey of the basic ideas in linear programming

and related areas and is designed for a one-semester or one-quarter course

that can be taken by business, engineering, computer science, or mathe-

matics majors. In their professional careers many of these students will

work with real applied problems; they will have to formulate models for

these problems and obtain understandable numerical answers. Our pur-

pose is to provide such students with an impressive illustration of how

simple mathematics can be used to solve difficult problems that arise in

real situations and to give them some tools that will prove useful in their

professional work.

A significant change that has taken place in the general teaching of this

course has been the introduction of the personal computer. This edition

takes due cognizance of this new development.

WHAT IS NEW IN THE SECOND EDITION

We have been very pleased by the widespread acceptance of the first

edition of this book since its publication 15 years ago. Although many

changes have been made in this edition, our objectives remain the same as

in the first edition: to provide a textbook that is readable by the student,

presents the basic notions of linear programming, and illustrates how this

material is used to solve, some very important problems that arise in our

daily lives. To achieve these objectives we have made use of many faculty

and student suggestions and have developed the following features for this

edition.

FEATURES

9 Some more review material on linear algebra has been added in

Chapter 0.

9 Chapters 1 and 2 of the first edition have been modified. In the

revised Chapters 1 and 2, the material on the Extreme Point Theo-

rem, basic solutions, and the Duality Theorem are now presented in

separate sections. Moreover, the important elementary aspects of

linear programming and its applications are covered more quickly and

more directly.

9 In Chapter 3, the presentation of the Duality Theorem has been

rewritten, and now appears as Section 3.2.

9 In Chapter 5, the presentations of the transportation problem, assign-

ment problem, and maximal flow problem have been rewritten for

greater clarity.

Preface

xiii

9 New exercises have been added.

9 New figures have been added.

9 Throughout the book, the material on computer aspects has been

updated.

9 A computer disk containing the student-oriented linear programming

code SMPX, written by Professor Evar D. Nering, Arizona State

University, to be used for experimentation and discovery, is included

with the book. Its use is described in Appendix C.

9 Appendix A, new to this edition, provides a very elementary introduc-

tion to the basic ideas of the Karmarkar algorithm for solving linear

programming problems.

9 Appendix B has been added to this edition to provide a guide to some

of the inexpensive linear programming software available for personal

computers.

PRESENTATION

The Prologue gives a brief survey of operations research and discusses

the different steps in solving an operations research problem. Although we

assume that most readers have already had some exposure to linear

algebra, Chapter 0 provides a quick review of the necessary linear algebra.

The linear algebra requirements for this book are kept to a minimum.

Chapter 1 introduces the linear programming problem, provides examples

of such a problem, introduces matrix notation for this problem, and

discusses the geometry of linear programming problems. Chapter 2 pre-

sents the simplex method for solving the linear programming problem.

Chapter 3 covers further topics in linear programming, including duality

theory and sensitivity analysis. Chapter 4 presents an introduction to

integer programming, and Chapter 5 discusses a few of the more important

topics in network flows.

The approach in this book is not a rigorous one, and proofs have been

kept to a minimum. Each idea is motivated, discussed, and carefully

illustrated with examples. The first edition of this book is based on a

course developed by one of us (Bernard Kolman) under a College Science

Improvement Program grant from the National Science Foundation.

EXERCISES

The exercises in this book are of three types. First, we give routine

exercises designed to reinforce the mechanical aspects of the material

under study. Second, we present realistic problems requiring the student to

formulate a model and obtain solutions to it. Third, we offer projects,

xiv

Preface

some of which ask the student to familiarize himself or herself with those

journals that publish papers in the subject under study. Most of the

projects are realistic problems, and they will often have some vagueness in

their statement; this vagueness must be resolved by the student as he or

she formulates a model.

COMPUTERS

The majority of students taking this course will find that after having

solved a few linear programming problems by hand, they will very much

appreciate being able to use a computer program to solve such problems.

The computer will reduce the computational effort required to solve linear

programming problems and will make it possible to solve larger and more

realistic problems. In this regard, the situation is different from when the

first edition of this book appeared. Nowadays, there are inexpensive

programs that will run on modest personal computers. A guide to some of

these is provided in Appendix B. Moreover, bound with this book is a disk

containing the program SMPX, developed by Evar D. Nering, Arizona

State University, as courseware for a typical course in linear programming.

This courseware allows the student to experiment with the simplex method

and to discover the significance of algorithm choices.

Complementing SMPX courseware is LINDO, an inexpensive and pow-

erful software package designed to solve linear programming problems. It

was first developed in 1983 and is now available in both PC and Macintosh

versions.

The final sections in each of Chapters 3, 4 and 5 discuss computer

aspects of the material in the chapter. These sections provide an introduc-

tion to some of the features available in the linear programming codes

used to solve large real problems and an introduction to the considerations

that enter into the selection of a particular code.

Kolman B., Beck R. - Elementary Linear Programming with Applications (Elsevier, 1995).pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: