raw
Consider the following hypothetical example: A company has two plants, A and B. A and B both make two products, standard and deluxe. To the market, it does not matter where a product is made. It pays $10 for the standard product and $15 for the deluxe one. The company controls a certain raw material, called raw, which might be a required component of the product, manpower, money, or some such thing. Each product (standard or deluxe) requires 4 units of raw. The company has 120 units of .
The divisions are somewhat autonomous, making their own production decisions. It is known that A has newer equipments and can make products faster. Currently the company allocates 75 units of raw to A and 45 to B. The company wants to know if there is a better allocation. n Under the current allocation, A makes 11.25 standard and 7.5 deluxe, for a profit of $225. B makes 11.25 deluxe for a profit of $168.75. The total profit is 393.75. Is there a better split of raw? And do we need more information out of the divisions?
There are algorithms that directly solve this resource splitting
problem. We will address this through a different direction: that of
internal pricing. We need the following from the divisions: we will
vary the cost that we will charge them for . We then need them to
tell us what they propose to produce. This, not surprisingly, is
called a proposal. So, for each division, a proposal is two
numbers: 
, which is the amount they would produce of
standard and deluxe respectively. We also require that if a division
provides two proposals, say 
and 
then the division is also
able and willing to make a combination of the proposals, say 25% of
and 75% of . In this case, our divisions are willing to
give us something stronger: if they make a proposal, they are willing
to do any fraction of the proposal. Our objective is to find an
internal price that will optimize the company's profit without
centralizing all the planning.
Our approach is to tell each division the amount they make on each of standard and deluxe (10 and 15 here) and charge them an amount for each unit of (denoted r). We begin with an amount of 0 (i.e. is free). The production proposals are as follows:
A: 
for a profit of $250. (Proposal 1A)
B: 
for a profit of $187.5. (Proposal 1B)
So far, so good. If we accept these proposals, we make a profit of $437.5. Unfortunately, if we adopt these proposals, the divisions will use 140 units of , more than the 120 the company has. Clearly, the company must increase the cost of to encourage division A to produce fewer standard and more deluxe. How can we decide what to charge?
The key here is to recognize that the company is solving a linear
program. This linear program has a variable for each proposal (the
fact that the divisions will generate proposals is what makes this a
variable generation scheme). For division A's ith proposal, we
will associate a variable 
; for division B's ith proposal
we have a variable 
. Each proposal generates a certain
profit and uses a certain amount of . We want to find a
combination of the proposals that maximizes profit without using too
much . At this point our linear program is
Maximize 
Subject to
Solving this linear program gives us 
for
a profit of 382.5. More importantly, though, we also get a
shadow price on . This gives us an estimate of the marginal
value of , which seems like a natural choice for an internal price
for . This value is 2.78. We now ask the divisions what they
will produce if the profit on standard is -1.12 (=10 - 4*2.78) (i.e.
they take a loss on each standard they produce) and the profit on
deluxe is 3.88 (=15-4*2.78). The proposals are now:
A: 
(Proposal A2)
B:
The proposal for B does not change, but A has decided on a new
plan. This proposal makes the company 180 and uses just 48 units of
. Using variable 
for this, our new linear program is:
Maximize 
Subject to
We can then resolve this linear program. The dual for turns out
to be 1.67 (suggesting we were overcharging at 2.78) with solution
. We then go back to the
divisions with profit on standard of 3.28 and profit on deluxe of
8.28. Their proposals are:
A:
B:
which are identical to the proposals generated before. We therefore conclude that we can get no further information out of the divisions.
The solution we have generated is as follows:
A: 
and 
B: 
and 
The total profit generated is $403.9, based on a split of 70 units of to A and 50 units to B. Our initial allocation over-compensated for B's older machinery.
At this point, we could do two things: we could adopt a 70-50 split, or we could use $1.67 as the internal price for and let the divisions buy from the company. In the second case, we must be careful because division A might use proposal 1 and require too much . The coordinator would then point out that A is indifferent between proposals 1A and 2A (each gives profit of 99.7) and so the division can do as well with the above combination of 1A and 2A. This coordination is a definite drawback to using internal costing methods to control use of resources.
It turns out that A and B were using linear programs to determine their proposals. The linear program for A was:
Maximize 
Subject to
(where the profit on standard was and the profit on
deluxe ) and B used:
Maximize 
Subject to
This means, of course, that we could have written the original problem as one larger linear program:
Maximize 
Subject to
It is not obvious that our technique of requesting proposals is guaranteed to find the optimal solution to the above linear program. It does, however. The proof is not of great interest, so will be omitted.
We will examine the structure of this sort of linear program in detail in generalizing this example.