Customers arrive at a two-server station in accordance with a Poisson process having rate r. Upon arriving, they join a single queue. Whenever a server completes a service, the person first in line enters service. The service times of server A are exponential with rate u1, and the service times of server B are exponential with rate u2, where u1+u2>r. An arrival finding both servers free is equally likely to go to either one. Define an appropriate continuous-time Markov chain for this model and find the limiting probabilities.

这个模型可以用一个连续时间马尔科夫链来表示。

状态空间可以是三元组 (a, b, c)，其中 a 表示有 a 个人在队伍中排队等待服务，b 表示有 b 个人在服务器 A 中排队等待服务，c 表示有 c 个人在服务器 B 中排队等待服务。

转移率可以用如下方程表示：

(a, b, c) -> (a+1, b, c) 的转移率为 r

(a, b, c) -> (a-1, b-1, c) 的转移率为 u1 * b

(a, b, c) -> (a-1, b, c-1) 的转移率为 u2 * c

当 (a, b, c) = (0, 0, 0) 时，(a, b, c) -> (1, 0, 0) 的转移率为 r/2，(a, b, c) -> (0, 1, 0) 的转移率也为 r/2。

最终的极限概率可以通过求解方程组来解决。

具体地，设 (a, b, c) 的极限概率为 p(a, b, c)，则有如下方程：

p(a, b, c) = r/2 * p(a-1, b, c) + r/2 * p(a-1, b-1, c) + u1 * b * p(a-1, b-1, c) + u2 * c * p(a-1, b, c-1)

对于 a, b, c >= 0 的情况，有 p(a, b, c) = 0。

对于 a < 0 或 b < 0 或 c < 0 的情况，有 p(a, b, c) = 0。

初始条件为 p(0, 0, 0) = 1，其他状态的概率

相关问题

写一段Java实现Input In the first line you are given the number n of billionaires (1 ≤ n ≤ 10000). The following n lines contain information about these people: their names, cities where they were staying at the beginning of the period, and their fortunes. In the next line you are given the number m of days in the period for which you have the information (1 ≤ m ≤ 50000) and the number k of travels of the billionaires (0 ≤ k ≤ 50000). The following k lines contain the list of travels in the following format: the number of the day (from 1 to m−1), the name of the person, and the city of destination. You may assume that billionaires depart late at night and arrive to the destination city on the next day's morning. They cannot make more than one travel each day. The numbers of days in the list are not decreasing. All names of people and cities consist of at most 20 English letters; you must take into consideration the case of the symbols. The fortunes are in the range from 1 to 100 billions (one billion is a thousand million). Output In each line of the output give the name of a city and, after a space, the number of days during which this city was the first with respect to the sum of fortunes of the billionaires staying there. Leave out those cities for which there were no such days. The cities must be sorted alphabetically (with the usual symbol order: ABC...Zabc...z).

以下是Java实现代码：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Map<String, Integer> cityDays = new TreeMap<>();
        Map<String, Integer> cityFortunes = new HashMap<>();
        Map<String, String> billionaireCities = new HashMap<>();

        for (int i = 0; i < n; i++) {
            String name = scanner.next();
            String city = scanner.next();
            int fortune = scanner.nextInt();
            billionaireCities.put(name, city);
            cityFortunes.put(city, cityFortunes.getOrDefault(city, 0) + fortune);
        }

        int m = scanner.nextInt();
        int k = scanner.nextInt();
        for (int i = 0; i < k; i++) {
            int day = scanner.nextInt();
            String name = scanner.next();
            String destCity = scanner.next();
            String origCity = billionaireCities.get(name);
            int fortune = cityFortunes.get(origCity);
            if (cityDays.get(origCity) == null) {
                cityDays.put(origCity, 0);
            }
            if (cityDays.get(destCity) == null) {
                cityDays.put(destCity, 0);
            }
            cityDays.put(origCity, cityDays.get(origCity) + day - cityDays.get(destCity));
            cityDays.put(destCity, day);
            cityFortunes.put(origCity, fortune - cityFortunes.getOrDefault(origCity, 0));
            cityFortunes.put(destCity, cityFortunes.getOrDefault(destCity, 0) + fortune);
            billionaireCities.put(name, destCity);
        }

        List<String> result = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : cityDays.entrySet()) {
            String city = entry.getKey();
            int days = entry.getValue();
            if (days > 0) {
                result.add(city + " " + days);
            }
        }

        for (String s : result) {
            System.out.println(s);
        }
    }
}

解释一下代码：

首先读取输入的数据，使用Map<String, Integer> cityDays记录每个城市的首富天数，Map<String, Integer> cityFortunes记录每个城市的首富总财富，Map<String, String> billionaireCities记录每个亿万富翁所在的城市。

接着，遍历每个亿万富翁，将其所在城市的首富总财富加入到cityFortunes中。然后，读取每个亿万富翁的旅行记录，更新cityDays、cityFortunes和billionaireCities。对于每条旅行记录，先计算出旅行前该亿万富翁所在城市的首富天数，然后将其更新为旅行前最后一次到达该城市的天数减去旅行天数，将目的地城市的首富天数更新为旅行天数，更新原城市和目的地城市的首富总财富，并将该亿万富翁所在城市更新为目的地城市。

最后，遍历cityDays，将首富天数大于0的城市加入到结果列表中，并按照字典序排序输出。

这段代码加注释const int maxn = 10000; int n, q, cnt = 0, sum = 0; int vis[maxn], ans[maxn], arr[maxn], endt[maxn], startt[maxn]; queue<int> qe; struct Process { int id, arrive, left, rest; } p[maxn]; bool cmp(Process a, Process b) { return a.arrive < b.arrive; }

这段代码定义了一些变量和结构体，以及一个比较函数cmp。

- maxn：常量，表示数组最大长度。
- n：表示进程数量。
- q：表示时间片大小。
- cnt：计数器，表示当前已经调度的进程数量。
- sum：表示当前已经运行的时间。
- vis：数组，表示每个进程是否已经被调度过。
- ans：数组，表示每个进程的周转时间。
- arr：数组，表示每个进程的到达时间。
- endt：数组，表示每个进程的结束时间。
- startt：数组，表示每个进程的开始时间。
- qe：队列，用于存储进程id。
- Process：结构体类型，表示一个进程，包括id，到达时间，离开时间和剩余时间。
- cmp：比较函数，用于进程排序，按照到达时间从小到大排序。

该部分代码实现了一个调度算法，具体实现逻辑如下：

1. 按照到达时间从小到大排序所有进程。
2. 将第一个进程的到达时间作为当前时间。
3. 如果当前时间小于进程的到达时间，将当前时间调整为该进程的到达时间。
4. 将所有到达时间小于等于当前时间，且未被调度过的进程加入队列中。
5. 如果队列不为空，从队首取出一个进程。
6. 如果该进程的剩余时间小于等于时间片大小q，将该进程的结束时间设为当前时间加上剩余时间，将该进程的周转时间计算出来并记录在ans数组中，将该进程标记为已调度，并将sum加上剩余时间。
7. 如果该进程的剩余时间大于时间片大小q，将该进程的剩余时间减去时间片大小q，将该进程重新加入队列尾部，将当前时间加上q。
8. 重复步骤5到步骤7，直到所有进程都被调度并记录完毕。