Robert J. Vanderbei - Linear Programming

The first problem we wish to consider is the one faced by the companys production manager. It is the problem of how to use the raw materials on hand. Let us assume that she decides to produce x j units of the j th product, j =1,2,, n . The revenue associated with the production of one unit of product j is j . But there is also a cost of raw materials that must be considered. The cost of producing one unit of product j is . Therefore, the net revenue associated with the production of one unit is the difference between the revenue and the cost. Since the net revenue plays an important role in our model, we introduce notation for it by setting Now, the net revenue corresponding to the production of x j units of product j is simply c j x j , and the total net revenue is The production planners goal is to maximize this quantity. However, there are constraints on the production levels that she can assign. For example, each production quantity x j must be nonnegative, and so she has the constraints Secondly, she cant produce more product than she has raw material for. The amount of raw material i consumed by a given production schedule is , and so she must adhere to the following constraints: To summarize, the production managers job is to determine production values x j , j =1,2,, n , so as to maximize (). This optimization problem is an example of a linear programming problem. This particular example is often called the resource allocation problem .

In another office at the production facility sits an executive called the comptroller. The comptrollers problem (among others) is to assign a value to the raw materials on hand. These values are needed for accounting and planning purposes to determine the cost of inventory . There are rules about how these values can be set. The most important such rule (and the only one relevant to our discussion) is the following:

The company must be willing to sell the raw materials should an outside firm offer to buy them at a price consistent with these values.

Let w i denote the assigned unit value of the i th raw material, i =1,2,, m . That is, these are the numbers that the comptroller must determine. The lost opportunity cost of having b i units of raw material i on hand is b i w i , and so the total lost opportunity cost is The comptrollers goal is to minimize this lost opportunity cost (to make the financial statements look as good as possible). But again, there are constraints. First of all, each assigned unit value w i must be no less than the prevailing unit market value i , since if it were less an outsider would buy the companys raw material at a price lower than i , contradicting the assumption that i is the prevailing market price. That is, Similarly, To see why, suppose that the opposite inequality holds for some specific product j . Then an outsider could buy raw materials from the company, produce product j , and sell it at a lower price than the prevailing market price. This contradicts the assumption that j is the prevailing market price, which cannot be lowered by the actions of the company we are studying. Minimizing () is a linear programming problem. It takes on a slightly simpler form if we make a change of variables by letting In words, y i is the increase in the unit value of raw material i representing the mark-up the company would charge should it wish simply to act as a reseller and sell raw materials back to the market. In terms of these variables, the comptrollers problem is to minimize