Linear Programming: An Introduction to Finite Improvement Algorithms
eBook - ePub

Linear Programming: An Introduction to Finite Improvement Algorithms

Second Edition

Daniel Solow

Share book
  1. 432 pages
  2. English
  3. ePUB (mobile friendly)
  4. Available on iOS & Android
eBook - ePub

Linear Programming: An Introduction to Finite Improvement Algorithms

Second Edition

Daniel Solow

Book details
Book preview
Table of contents

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

How do I cancel my subscription?
Simply head over to the account section in settings and click on “Cancel Subscription” - it’s as simple as that. After you cancel, your membership will stay active for the remainder of the time you’ve paid for. Learn more here.
Can/how do I download books?
At the moment all of our mobile-responsive ePub books are available to download via the app. Most of our PDFs are also available to download and we're working on making the final remaining ones downloadable now. Learn more here.
What is the difference between the pricing plans?
Both plans give you full access to the library and all of Perlego’s features. The only differences are the price and subscription period: With the annual plan you’ll save around 30% compared to 12 months on the monthly plan.
What is Perlego?
We are an online textbook subscription service, where you can get access to an entire online library for less than the price of a single book per month. With over 1 million books across 1000+ topics, we’ve got you covered! Learn more here.
Do you support text-to-speech?
Look out for the read-aloud symbol on your next book to see if you can listen to it. The read-aloud tool reads text aloud for you, highlighting the text as it is being read. You can pause it, speed it up and slow it down. Learn more here.
Is Linear Programming: An Introduction to Finite Improvement Algorithms an online PDF/ePUB?
Yes, you can access Linear Programming: An Introduction to Finite Improvement Algorithms by Daniel Solow in PDF and/or ePUB format, as well as other popular books in Mathematics & Linear & Nonlinear Programming. We have over one million books available in our catalogue for you to explore.



Chapter 1

Problem Formulation

The success and survival of any organization depend on the quality of the decisions made by its managers. The central issue in many problems arising in business, industry, and government is that various activities compete for limited resources. It is the responsibility of the decision maker to allocate the resources among the competing activities so as to achieve the best results for the organization. The decision maker needs tools and techniques that can help in the quest for the optimal allocation of resources. Linear programming is the study of a large and important class of these problems together with the procedures currently available for obtaining their solutions. In this chapter, you will learn what a linear programming problem is, how to identify and to formulate one, and what distinguishes it from other types of problems.


To understand what a linear programming problem is, consider the dilemma of Midas M. Miner. One day he was traveling through the galaxy in his luxury spaceship when he developed minor engine trouble and was forced to land on a nearby asteroid. After making the necessary repairs, he was astounded (and delighted) to discover that the asteroid contained large quantities of silver ore and gold ore. Naturally, Midas wanted to take the whole asteroid with him, but practical considerations dictated otherwise. He knew that his ship could carry up to 100 pounds of extra cargo as long as it did not take up more than 150 cubic feet of space. After some measurements, Midas calculated that each pound of gold ore requires 2 cubic feet but each pound of silver ore requires only 1 cubic foot. Given that each pound of gold ore is worth 3 intergalactic credits (each credit being equivalent to approximately $10,000) and each pound of silver ore is worth 2 credits, how many pounds of each type of ore should Midas put on his ship so as to maximize his profit and still be able to take off?
In this problem, it is necessary to determine the quantities of gold and silver ore that Midas should take so as to achieve the maximum possible profit. Since it is not known in advance what these quantities should be, let x1 and x2 represent the number of pounds, respectively, of each of the two ores to be loaded on the ship. The variables x1 and x2 are sometimes called decision variables.
Since each pound of gold ore is worth 3 intergalactic credits, the worth of x1 pounds of gold ore would be 3x1 credits. Similarly, the worth of x2 pounds of silver ore would be 2x2 credits since each pound is worth 2 credits. Therefore, Mr. Miner’s total profit would be 3x1 + 2x2 credits. The function 3x1 + 2x2 is called the objective function because the objective of the problem is to find values for x1 and x2 that maximize this function. Suppose, for instance, that x1 and x2 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 x1 is 60 pounds and x2 is 80 pounds, then the total profit would be 3(60) + 2(80) = 340 credits. Evidently, as x1 and x2 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.
If Midas decides to take xl pounds of gold ore and x2 pounds of silver ore, then the total weight of the cargo will be x1 + x2 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 2xl + x2 cubic feet. For the specific case in which x1 and x2 are chosen to be 40 and 50 pounds, respectively, the corresponding total weight of the cargo would be x1 + x2 = 40 + 50 = 90 pounds, and the volume of this cargo would be 2x1 + x2 = 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 x1 = 40, x2 = 50 is said to be feasible.
In contrast, consider the case in which xl is 60 and x2 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 x1 = 60, x2 = 80 is said to be infeasible.
The conclusion is that Midas is constrained by the limited cargo capacity, and so his profits are limited also. The constraint on the total weight of the cargo can be expressed mathematically by the inequality
x1 + x2 ≤ 100
Similarly, the total volume of the cargo should be less than or equal to 150 cubic feet, so
2x1 + x2 ≤ 150
These are two constraints that x1 and x2 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 x1 and x2 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
x1 ≥ 0, x2 ≥ 0
Such constraints should be included in the formulation of any real world problem whenever appropriate.
In mathematical terms, Mr. Miner’s problem can be stated as follows:
The above problem is a linear programming problem (hereafter referred to as an LP). I...

Table of contents