On the market, a man sold a cow (optimally)

March 14, 2017 Sergey_Kovalenko published the task of extremely agitating the minds of habrazhiteli. For a couple of evenings many copies were broken and many heads would probably have been broken if the meeting were full-time.

Below you expect the condition of the problem and consideration of one approach to the solution.

Condition

A certain man is engaged in the resale of cows: He buys them for a fixed small price of a rubles from the local population and tries to sell them at a premium to market visitors. Suppose, for simplicity, that buyers are divided into n classes according to their solvency, and that to any buyer who came up to the peasant from the k-th class, he sells any of his available cows with a mark of xk rubles. We assume that the appearance of the buyer of each class is described by the Poisson process with a certain load parameter lk-characteristic for this class. If at the time of the appearance of a buyer, the Peasant has no cows, then the first one does not queue up, but is removed back home and does not return back.

1. Each cow bought by the Peasant from the population eats per unit of time feed for u rubles, so keeping a large supply of cows is not profitable;
2. A man can always send a request to bring more cows with his companion to the village, but the fulfillment of this request, although free, takes T time;
3. Because of the reservations made, the Peasant may not sell the cow if he has few of them, and the chance to meet a richer client is large enough, or vice versa, to sell at a loss from excess stock just to feed for nothing.

What is the optimal long-term strategy for a Man with an almost infinite initial capital?
')

Decision

To shoot this problem, we will get one of the most remarkable guns that has long been used by mathematicians and programmers - the “teapot method”.

Suppose there is a Poisson stream of clients with parameter I, each client pays for the cow a mark-up x, a peasant sells a cow whenever it is.

For further work, we will need several additional considerations that will allow us to successfully "pour out the water from the kettle."

Crib on the market can be very large, but it is certainly the final size m. Customers remain customers. Cows turn into service devices as follows: when a cow stands in a barn on the market, the service device is not occupied, when a peasant sells a cow, the service device becomes busy until a new cow arrives from this village.

Let now at the moment of time t there are i cows in the barn and the sale of the cow takes place. The muzhik needs to decide whether to order the cow immediately or postpone the demand. The important point is that whatever decision he takes a cow earlier than through T he will not receive. Thus, the time of delivery of the cow to the vacant place is a random variable t, which takes values ​​from the interval $$$[T, + \ infty)$and expectation $$$\ overline T$. The distribution of this value depends on the strategy of ordering cows.

As rightly noted in the comments, unfortunately it is necessary to demand the independence of service times.

Thus, we obtain that the original problem, with the indicated restrictions, is equivalent to a queuing mass service system with m service devices.

Then it is possible to calculate the probability that the buyer will leave with the cow.

$$

$$p = 1-p_m (I, \ overline T)$$

Where $$$p_m$calculated by the Erlang formula. Note that the probability of failure does not depend on the distribution t, only the average service time is important.

Suppose now that the barn consumes u rubles per unit of time, not for a cow, but for a stall. But when a customer buys a cow, he pays from above $$$ut$rubles.

Then the average profit per unit of time can be expressed as

$$

$$\ overline r = I \ cdot (x + u \ overline T) \ cdot (1-p_m (I, \ overline T)) - um$$

And the task itself comes down to finding

$$

$$\ max_ {m, \ overline T} r (m, \ overline T)$$

.

Analysis of the results

If the maximum r is reached at $$$\ overline T = T$then the only possible strategy is to order the cows for sale.

You can not try to change the value of m, since, due to the properties of the Poisson flow, you can cut out time intervals where m is not optimal and glue them together. As a result, the result will be worse than optimal.