March 19, 2017 at 21:11

A man was selling a cow in the market (optimally)

    On March 14, 2017 Sergey_Kovalenko published a task that excited the minds of the hawkers. Over the course of a couple of evenings, many copies were broken and surely many goals would have been broken if the meeting had been full-time.

    Below you will find the condition of the problem and the 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 a rubles from the local population and tries to sell them at a premium to market visitors. For simplicity's sake, suppose that buyers are divided into n classes by their solvency, and that to anyone who approached a guy from the k-th class, he sells any of his cows with an extra charge of xk-th rubles. We assume that the appearance of a customer of each class is described by a Poisson process with a certain load parameter lk-th characteristic of this class. If at the time of the appearance of the buyer, the Muzhik does not have cows, then the first one does not stand in line, but is removed and is no longer returned.

    1. Each cow bought by a Man from the population eats feed for u rubles per unit time, so keeping a large supply of cows is not profitable;
    2. A man can always send with a fellow traveler a request to bring more cows to the village, however, the fulfillment of this request, although free, takes T time;
    3. In view of the reservations made, the Man may not sell the cow if he has few of them, and the chance to meet the client richer is large enough, or vice versa - to sell at a loss from the surplus stock, if only not to feed in vain.

    What is the optimal peasant strategy for a long period with an almost infinite initial capital?

    Decision


    To shoot this problem, we will get one of the most wonderful guns, which has long been used by mathematicians and programmers - the "teapot method".

    Suppose there is a Poisson flow of customers with parameter I, each customer pays a mark-up x for a cow, a man always sells a cow when it is.

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

    The crib on the market can be very large, but still the final size is m. Customers remain customers. Cows, on the other hand, turn into service devices as follows: when a cow is in the crib on the market, the service device is not occupied, when a man sells a cow, the service device becomes busy until a new cow comes to the place from the village.

    Now, let at the moment in time t there are i cows in the stable and a cow is being sold. A peasant needs to decide whether to order a cow immediately or to postpone a demand. The important point is that no matter what decision he makes to the cow before he receives through T. Thus, the delivery time of the cow to the vacated seat is a random variable t taking values ​​from the interval$ [T, + \ infty) $ and mathematical expectation $ \ overline T $. The distribution of this value depends on the strategy for ordering cows.

    As rightly noted in the comments, unfortunately, you will have to demand independence of service times.

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

    Then you can calculate the likelihood that the buyer will leave with the cow.

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



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

    Now let the barn consume u rubles per unit of time, not per cow, but per stall. But, when a customer buys a cow, he “pays” on top$ ut $rubles.

    Then the average profit per unit 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 upon the sale.

    You can’t try to change the value of m, because, due to the properties of the Poisson stream, you can cut out time intervals where m is not optimal and glue them. And as a result, the result is worse than optimal.

    Tags:

    Also popular now: