Elementary Linear Programming with Applications

Bernard Kolman, Robert E. Beck

• Publisher: Academic Press
• Year: 1995
• ISBN:
  9780080530796
• Edition: 2
• Topic: Matemáticas
• Subtopic: Optimización

Linear programming finds the least expensive way to meet given needs with available resources. Its results are used in every area of engineering and commerce: agriculture, oil refining, banking, and air transport. Authors Kolman and Beck present the basic notions of linear programming and illustrate how they are used to solve important common problems. The software on the included disk leads students step-by-step through the calculations.

The Second Edition is completely revised and provides additional review material on linear algebra as well as complete coverage of elementary linear programming. Other topics covered include: the Duality Theorem; transportation problems; the assignment problem; and the maximal flow problem. New figures and exercises are provided and the authors have updated all computer applications.

• More review material on linear algebra
• Elementary linear programming covered more efficiently
• Presentation improved, especially for the duality theorem, transportation problems, the assignment problem, and the maximal flow problem
• New figures and exercises
• Computer applications updated
• New guide to inexpensive linear programming software for personal computers

1

Introduction to Linear Programming

This chapter and the next two, which represent the heart of this book, introduce the basic ideas and techniques of linear programming. This area of applied mathematics was developed in the late 1940s to solve a number of resource allocation problems for the federal government. It has become an essential tool in operations research and has been applied to a remarkably varied number of real problems, producing enormous savings in money and resources. In this chapter we first introduce the linear programming problem and then discuss a simple geometric solution for small problems. Finally, we connect the algebraic and geometric descriptions of the solutions of a linear programming problem.

1.1 THE LINEAR PROGRAMMING PROBLEM

We start by giving several examples of linear programming problems.

EXAMPLE 1. (ACTIVITY ANALYSIS OR PRODUCT MIX)

A lumber mill saws both finish-grade and construction-grade boards from the logs that it receives. Suppose that it takes 2 hr to rough-saw each 1000 board feet of the finish-grade boards and 5 hr to plane each 1000 board feet of these boards. Suppose also that it takes 2 hr to rough-saw each 1000 board feet of the construction-grade boards, but it takes only 3 hr to plane each 1000 board feet of these boards. The saw is available 8 hr per day, and the plane is available 15 hr per day. If the profit on each 1000 board feet of finish-grade boards is $120 and the profit on each 1000 board feet of construction-grade boards is $100, how many board feet of each type of lumber should be sawed to maximize the profit?

MATHEMATICAL MODEL

Let x and y denote the amount of finish-grade and construction-grade lumber, respectively, to be sawed per day. Let the units of x and y be thousands of board feet. The number of hours required daily for the saw is

2x + 2y.

Since only 8 hours are available daily, x and y must satisfy the inequality

2x + 2y ≤ 8;

Similarly, the number of hours required for the plane is

5x + 3y,

so x and y must satisfy

5x + 3y ≤ 15.

Of course, we must also have

x ≥ 0 y ≥ 0.

The profit (in dollars) to be maximi...