# Linear Programming: An Introduction to Finite Improvement Algorithms

## Second Edition

## Daniel Solow

- 432 pages
- English
- ePUB (mobile friendly)
- Available on iOS & Android

# Linear Programming: An Introduction to Finite Improvement Algorithms

## Second Edition

## Daniel Solow

## About This Book

Suitable for undergraduate students of mathematics and graduate students of operations research and engineering, this text covers the basic theory and computation for a first course in linear programming. In addition to substantial material on mathematical proof techniques and sophisticated computation methods, the treatment features numerous examples and exercises.

An introductory chapter offers a systematic and organized approach to problem formulation. Subsequent chapters explore geometric motivation, proof techniques, linear algebra and algebraic steps related to the simplex algorithm, standard phase 1 problems, and computational implementation of the simplex algorithm. Additional topics include duality theory, issues of sensitivity and parametric analysis, techniques for handling bound constraints, and network flow problems. Helpful appendixes conclude the text, including a new addition that explains how to use Excel to solve linear programming problems.

## Frequently asked questions

## Information

**Chapter 1**

**Problem Formulation**

**1.1. WHAT IS A LINEAR PROGRAMMING PROBLEM?**

*x*

_{1}and

*x*

_{2}represent the number of pounds, respectively, of each of the two ores to be loaded on the ship. The variables

*x*

_{1}and

*x*

_{2}are sometimes called

*decision variables*.

*x*

_{1}pounds of gold ore would be 3

*x*

_{1}credits. Similarly, the worth of

*x*

_{2}pounds of silver ore would be 2

*x*

_{2}credits since each pound is worth 2 credits. Therefore, Mr. Minerâs total profit would be 3

*x*

_{1}+ 2

*x*

_{2}credits. The function 3

*x*

_{1}+ 2

*x*

_{2}is called the

*objective function*because the objective of the problem is to find values for

*x*

_{1}and

*x*

_{2}that maximize this function. Suppose, for instance, that

*x*

_{1}and

*x*

_{2}are chosen to be 40 pounds and 50 pounds, respectively. The corresponding profit would be 3(40) + 2(50) = 220 credits. On the other hand, if

*x*

_{1}is 60 pounds and

*x*

_{2}is 80 pounds, then the total profit would be 3(60) + 2(80) = 340 credits. Evidently, as

*x*

_{1}and

*x*

_{2}are increased, so are the profits. What is it, then, that prevents Midas from making an infinite profit? Evidently, it is the limited capacity of his cargo space.

*x*

_{l}pounds of gold ore and

*x*

_{2}pounds of silver ore, then the total weight of the cargo will be

*x*

_{1}+

*x*

_{2}pounds. Similarly, since each pound of gold ore requires 2 cubic feet of space and each pound of silver ore requires 1 cubic foot, the total volume of the cargo will be 2

*x*

_{l}+

*x*

_{2}cubic feet. For the specific case in which

*x*

_{1}and

*x*

_{2}are chosen to be 40 and 50 pounds, respectively, the corresponding total weight of the cargo would be

*x*

_{1}+

*x*

_{2}= 40 + 50 = 90 pounds, and the volume of this cargo would be 2

*x*

_{1}+

*x*

_{2}= 2(40) + (50) = 130 cubic feet. Since the ship can indeed hold 100 pounds and 150 cubic feet of cargo, Mr. Miner will have no trouble taking off with 40 pounds of gold ore and 50 pounds of silver ore. For this reason, the choice of

*x*

_{1}= 40,

*x*

_{2}= 50 is said to be

*feasible*.

*x*

_{l}is 60 and

*x*

_{2}is 80. The weight and volume of the resulting cargo are 140 pounds and 200 cubic feet, respectively. Since these quantities exceed the shipâs capacity, it is not possible to take 60 pounds of gold ore and 80 pounds of silver ore aboard the ship. For this reason, the choice

*x*

_{1}= 60,

*x*

_{2}= 80 is said to be

*infeasible*.

*x*

_{1}+

*x*

_{2}â€ 100

*x*

_{1}+

*x*

_{2}â€ 150

*x*

_{1}and

*x*

_{2}should satisfy, but are there any other restrictions on the variables? Although there are none explicitly stated in the problem, there is an implied understanding that the values of

*x*

_{1}and

*x*

_{2}should be â„ 0 because it is not possible to have negative quantities of rocks. These implicit nonnegativity constraints can be made explicit by writing the inequalities

*x*

_{1}â„ 0,

*x*

_{2}â„ 0