Bản thảo được tìm thấy ở Zaragoza

10

Hướng dẫn sử dụng được tìm thấy ở Zaragoza

Gần đây, trong cuộc khai quật ở thành phố Zaragoza của Tây Ban Nha, người ta đã phát hiện ra một thư viện cổ thuộc về gia đình buôn bán nổi tiếng một thời Suarskoe. Trong số những cuốn sách khác có lịch sử gia đình. Bây giờ chúng tôi sẽ giới thiệu với người đọc một trong những đoạn của bản thảo này, vì nó chứa công thức toán học hiện đại và thú vị bài toán. Vì thế…

“Đã đến tuổi mà một người thận trọng phải chăm sóc người kế nhiệm và tiếp tục công việc kinh doanh, Suarrez quyết định nhận các con trai của mình, Alonso và Lopez, để tìm hiểu xem chúng có khả năng thay thế ông như thế nào. Các con trai không xuất hiện, và Suarrez nói với họ bằng những lời sau: “Các con! Tôi dự định thay mặt mỗi bạn đóng góp 100.000 reais trong thời hạn mười năm cho một doanh nghiệp đáng tin cậy nào đó. Hoạt động kinh doanh này sẽ mang lại cho mọi người mức tăng 20% ​​mỗi ngày và bạn chỉ có thể quản lý số tiền này chứ không phải bản thân vốn. Bạn có thể thêm một phần số tiền này vào vốn của mình vào cuối năm và chi tiêu phần còn lại tùy ý. Mục tiêu của bạn sẽ là chi tiêu càng nhiều tiền càng tốt cho nhu cầu của bạn trong 10 năm, hoặc kiếm tiền chỉ để tiêu sau này. Hãy cho tôi biết, bạn sẽ quản lý thu nhập của mình như thế nào?”

đáp số đầu tiên là con trai cả Alonso, người nổi tiếng xa ngoài thành phố vì sự phù phiếm và ngông cuồng: “Cha ơi! Con sẽ tiêu hết thu nhập của mình ngay lập tức vì con không

11

Tôi thấy chẳng ích gì khi phải lo lắng về việc tăng thêm số vốn không thuộc về mình!”

Ngược lại, Lopez là một thanh niên khiêm tốn và đức độ. Anh ấy đã trả lời cha mình như thế này: “Trong 9 năm, con sẽ chỉ làm những gì chúng con đang làm ở nhà, thưa cha, và thêm thu nhập của con vào vốn của con. Trong năm thứ 10, con sẽ dành 20% cho việc chuẩn bị. Con hy vọng rằng đây sẽ là một số tiền đáng kể, vì vốn, nhờ các khoản đầu tư của con, sẽ tăng lên đáng kể.”

Thính giác đáp số Các con trai, thương gia đáng kính cau mày, rõ ràng là ông ta không hài lòng với câu trả lời. Khi các con trai ông bắt đầu xin lời khuyên, ông nói: “Hỡi các con, sự lãng phí tột độ cũng vô lý như sự cực kỳ tằn tiện, nhưng đúng đấy. lời giải tìm thấy giữa những thái cực này. Nếu tính đến điều này, tôi sẽ thêm một nửa thu nhập vào vốn, lo phần tăng thêm và chi một nửa cho nhu cầu của mình. Như tôi đã phát hiện ra, bạn vẫn chưa đủ thông minh và than ôi, không có khả năng thay thế tôi trong công việc kinh doanh ”. Ngày hôm sau, Suarez ra lệnh cho các con trai chuẩn bị cho cuộc hành trình xuyên dãy Pyrenees, đến Paris xa xôi, học toán và các ngành khoa học khác từ các nhà khoa học nổi tiếng người Paris…”

Ở đây chúng tôi sẽ dịch trích dẫn từ “tài liệu lịch sử”, vì bài toán mà chúng tôi quan tâm đã được xây dựng và thậm chí ba phiên bản khác nhau của lời giải của nó đã được đề xuất. Đầu tiên, chúng ta hãy so sánh hiệu quả của những lời giải này. Thật dễ dàng để tính toán (tốt nhất là họ có thể tự mình làm việc này, còn lại có thể sử dụng công thức (2) và (3) của bài viết này) số tiền mà Oto (S), Alonso (A) và Lopez (L) đã bỏ ra trong hơn 10 năm. Cụ thể là,

$$S = \left( \left( 1 + \frac{1}{10} \right)^{10} - 1 \right) 10^5 \approx 159374 \text{ реал},$$
$$A = 2 \cdot 10^5 = 200000 \text{ реал}$$
$$L = \frac{1}{6} \left( \left( 1 + \frac{1}{5} \right)^5 \right)^2 10^5 \approx 103169 \text{ реал}.$$

Kết quả so sánh thật nghịch lý. Hóa ra, Lopez tiết kiệm lại đưa ra mức lời giải tồi tệ nhất, và Alonso phù phiếm xử lý thu nhập của mình tốt hơn người cha mẹ khôn ngoan và giàu kinh nghiệm của mình! Hãy chắc chắn rằng những lập luận có vẻ hợp lý hóa ra lại là lừa đảo. Có lẽ lời giải tốt nhất khác với cả ba đề xuất? Hãy thử tìm hiểu điều này.

Vì vậy, chúng ta hãy biểu thị số vốn (sau khi không có lãi và có thể là một khoản đóng góp bổ sung) vào cuối năm $k$ (tính từ thời điểm gửi tiền đầu tiên) đến $x_k$, $k=0, \dots, N$. Ở chúng tôi, bài toán $N=10$ và giá trị đóng góp ban đầu là $x_0=10^5$. Vào năm $(k+1)$, giá trị $ax_k$ sẽ đạt tới (chúng ta có $a=\frac{1}{5}$) và nếu $\lambda_k$ phần của giá trị này được thêm vào vốn vào cuối năm $(k+1)$, thì mức tăng của nó trong năm là $x_{k+1}-x_k=\lambda_k ax_k$ ($k=0, \dots, N$). (1) Phần còn lại của phép tính gần đúng $(1-\lambda_k)ax_k$ sẽ được sử dụng.

Khả năng tác động đến quá trình tăng trưởng vốn hay nói cách khác là kiểm soát quá trình này của chúng ta là khả năng chọn một vectơ - một tập hợp các số có thứ tự $\bar{\lambda} = (\lambda_0, \dots, \lambda_{N-1})$, $0 \leqslant \lambda_i \leqslant 1$. Các vectơ như vậy sẽ còn được gọi là điều khiển $\bar{\lambda}$ và sẽ xác định hoàn toàn giá trị của hàm mục tiêu $F$ - tổng số tiền đã chi trong $N$ năm:

$$F(\bar{\lambda}) = (1-\lambda_0)ax_0 + (1-\lambda_1)ax_1 + \dots + (1-\lambda_{N-1})ax_{N-1}.$$ (2) Bài toán bao gồm việc tìm kiếm điều khiển tốt nhất, tối ưu $\lambda^{\text{опт}}$, tức là điều khiển như vậy $\lambda^{\text{опт}}$ sao cho đối với bất kỳ điều khiển nào khác $\bar{\lambda}$

$$F(\bar{\lambda}) \leqslant F(\bar{\lambda}^{\text{опт}}).$$

Chúng ta hãy nhớ rằng phương pháp kiểm soát tối ưu đã được đề xuất bởi Alonso $(0, \dots, 0)$, Lopez - $(1, \dots, 1, 0)$ và người thương gia đáng kính - $\left(\frac{1}{2}, \dots, \frac{1}{2}\right)$.

Có lẽ người đọc có ấn tượng bên ngoài rằng những kho tàng quản lý như vậy chỉ cần đến những người nhận được tài sản thừa kế phong phú? Tất nhiên là không! Đây là một ví dụ khác. Trang trại nuôi giống Blackburg Lips. Chúng ta sẽ biểu thị số lượng trang trại bằng $x_k$, trong đó $k=0, 1, \dots, N$ là số năm (chúng ta quan tâm đến số phận của trang trại trong thời gian tới

12

N năm). Con non vào đầu năm $(k+1)$ là $ax_k$ (trong đó $a > 0$ là một con số đã biết), và $\lambda_k$ phần của con non này vẫn còn ở trang trại, phần còn lại được đưa đi khai thác rừng. Do đó, mối quan hệ (1) là hợp lệ và số lượng da thu được trong $N$ năm được biểu thị bằng công thức (2). Như bạn có thể thấy, ở đây chúng ta cũng có một quy trình được kiểm soát, trạng thái của quy trình này tại mỗi thời điểm $k = 0, 1, \dots, N$ được đặc trưng bởi giá trị $x_k$ và chúng ta có thể tác động đến tiến trình của quy trình này bằng cách chọn hành động điều khiển $\lambda_k$ từ “vùng kiểm soát”, trong trường hợp này là phân đoạn [0, 1]. Nhiệm vụ là tìm ra một biện pháp kiểm soát trong đó mục tiêu đã đặt ra sẽ đạt được theo cách tốt nhất có thể - hàm mục tiêu $F$ sẽ đạt mức tối đa. Tương tự bài toán “kiểm soát tối ưu” các quy trình xảy ra trong “thời gian riêng biệt” phát sinh khi nghiên cứu sản xuất bài toán tại các nhà máy (trong trường hợp này $k$ là số của một chu kỳ sản xuất đã hoàn thành hoặc một tháng theo kế hoạch, v.v.), khi mô tả hoạt động của một số lò phản ứng hóa học được nối nối tiếp ($k$ là số lò phản ứng), v.v.

Nhánh toán học trong đó các phương pháp lời giải tương tự như bài toán được phát triển được gọi là lý thuyết điều khiển tối ưu. Trong hai thập kỷ qua, lý thuyết này đã phát triển thành một ngành khoa học toán học hiện đại mạnh mẽ, gây ấn tượng với cả kết quả lý thuyết sâu sắc và tính hiệu quả trong việc áp dụng lời giải điều khiển quá trình bài toán. Sự phát triển của hướng tư duy toán học này gắn liền với tên tuổi của các nhà toán học nổi tiếng như L. S. Pontryagin, R. Bellman, V. G. Boltyansky, R. V. Gamkrelidze, E. F. Mishenko, N. N. Krasovsky. Tuy nhiên, chúng tôi sẽ không trình bày lý thuyết chung về điều khiển tối ưu do các tác giả này tạo ra mà sẽ nghiên cứu bài toán của chúng tôi bằng toán học cơ bản.

Chúng ta hãy biến đổi công thức (1) thành dạng $x_{k+1} = (1 + a\lambda_k)x_k$, $(k = 0, \dots, N-1)$. (3)

Các biến đẳng thức (3) theo từng số hạng cho $k = 0, \dots, n-1$, chúng ta thu được ở dạng rõ ràng sự phụ thuộc của $x_n$ vào điều khiển $\bar{\lambda} = (\lambda_0, \dots, \lambda_{N-1})$
$$x_n = (1 + a\lambda_0)(1 + a\lambda_1) \dots (1 + a\lambda_{n-1})x_0.$$ (4)

Mệnh đề I. Đặt $\bar{\lambda} = (\lambda_0, \dots, \lambda_{i+1}, \dots, \lambda_{N-1})$ là một số điều khiển, $0 \leq i \leq N-2$, $\lambda_i < \lambda_{i+1}$ và đặt điều khiển $\bar{\lambda}$ khác với $\bar{\lambda}$ bằng cách hoán vị các số $\lambda_i$ và $\lambda_{i+1}$. Sau đó $F(\bar{\lambda}) > F(\bar{\lambda})$.

Để chứng minh điều đó, chỉ cần theo dõi xem các số hạng của tổng (2) được biến đổi như thế nào khi chuyển các số $\lambda_i$ và $\lambda_{i+1}$. Theo công thức (4), các số hạng $(1 - \lambda_k)ax_k$ trong $k \leq i-1$ hoàn toàn không phụ thuộc vào $\lambda_i$ và $\lambda_{i+1}$, đồng thời rất tốn kém và không thay đổi khi sắp xếp lại như vậy. Các số hạng $(1 - \lambda_k)ax_k$ với $k > i+1$ theo công thức (4) có dạng:
$$(1 - \lambda_k)ax_0(1 + a\lambda_0) \dots (1 + a\lambda_{i+1}) \times (1 + a\lambda_{i+1}) \dots (1 + a\lambda_{k-1}),$$
và do đó, cũng không thay đổi khi truyền các số $\lambda_i$ và $\lambda_{i+1}$. Vì vậy, ta chỉ cần xét tổng các số hạng còn lại:
$$(1 - \lambda_i)ax_i + (1 - \lambda_{i+1})ax_{i+1} = (1 - \lambda_i)ax_i + (1 - \lambda_{i+1})(1 + a\lambda_i)ax_i = ax_i[(2 - \lambda_i - \lambda_{i+1}) - a\lambda_i\lambda_{i+1}] + a\lambda_i.$$

Giá trị của $x_i > 0$ độc lập với $\lambda_i$ và $\lambda_{i+1}$, biểu thức trong dấu ngoặc đơn không thay đổi khi được truyền và số hạng thứ hai trong dấu ngoặc vuông được trả về. Vì vậy, $F(\bar{\lambda}) > F(\bar{\lambda})$.

Mệnh đề II. Hãy để $\bar{\mu}$ là một sự kiểm soát nào đó. Khi đó, với bất kỳ $n = 0, \dots, N$ nào cũng có một điều khiển tối đa $\bar{\mu}^{(n)} = (\mu_0^{(n)}, \dots, \mu_N^{(n)})$ sao cho $1^\circ \mu_n^{(i)}$ là 0 hoặc 1 đối với bất kỳ $i < n$, $2^\circ F(\bar{\mu}^{(n)}) \geqslant F(\bar{\mu})$ nào.

Hãy chứng minh phát biểu này bằng phương pháp quy nạp toán học. Đối với $n = 0$ tuyên bố này là hiển nhiên, vì chúng ta có thể đặt $\bar{\mu}^{(0)} = \bar{\mu}$ và tuyên bố $1^\circ$ và $2^\circ$ sẽ tự động được đáp ứng.

Giả sử rằng đối với $n = k$ ngoại lệ kiểm soát tồn tại $\bar{\mu}^{(k)} = (\mu_0^{(k)}, \dots, \mu_N^{(k)})$. Chúng ta hãy xem xét hàm $y(t)$ của một biến $t$, có xác định là đoạn [0, 1], được cho bởi công thức
$$y(t) = F(\mu_0^{(k)}, \dots, \mu_{k-1}^{(k)}, t, \mu_{k+1}^{(k)}, \dots, \mu_N^{(k)}).$$
Từ công thức (2) và (4), có thể thấy ngay rằng $y(t)$ là hàm tuyến tính của $t$, tức là
$$y(t) = At + B$$
đối với một số $A$ và $B$. Lưu ý rằng hàm tuyến tính trên khoảng [0, 1] đạt cực đại tại 0 nếu $A < 0$, tại một nếu $A > 0$ và tại $A = 0$ thì đó là hàm không đổi. Qua-

13

đặt nó xuống bây giờ
$$\mu_k^{(k+1)} = \begin{cases} 0, & A \leqslant 0, \\ 1, & A > 0, \end{cases}$$

và $\mu_k^{(k+1)} = \mu_i^{(k)}$ tại $i \neq k$, $0 \leqslant i \leqslant (N-1)$. Điều khiển $\overline{\mu}^{(k+1)}$ thỏa mãn điều kiện $1^\circ$ và $2^\circ$ cho $n = k + 1$. Thật vậy, các số $\mu_k^{(k+1)}$ với $i < k$ là số 0 hoặc số một theo giả định về chỉ báo và $\mu_k^{(k+1)}$ theo định nghĩa là 0 hoặc một. Hơn nữa, vì theo định nghĩa của số $\mu_k^{(k+1)}$ cho mọi $t$, $0 \leqslant t \leqslant 1$
$$y(t) \leqslant y(\mu_k^{(k+1)}),$$
thì $F(\overline{\mu}^{(k+1)}) \geqslant F(\overline{\mu}^{(k)})$. Theo giả định biểu thị $F(\overline{\mu}^{(k)}) \geqslant F(\overline{\mu})$, và do đó $F(\overline{\mu}^{(k+1)}) \geqslant F(\overline{\mu})$. Bằng chứng đã hoàn tất.

Bây giờ chúng ta hãy nêu bật một số loại điều khiển đặc biệt, đơn giản nhất trong số tất cả các điều khiển. Cụ thể, hãy xem xét một điều khiển $\overline{\theta}^{(m)}$ sao cho
$$\theta_i^{(m)} = \begin{cases} 1 & \text{при } i < m, \\ 0 & \text{при } i \geqslant m, \end{cases}$$
đối với một số $m$, $0 \leqslant m \leqslant N$. Một tập hợp các điều khiển thuộc loại này—chúng ta sẽ gọi chúng theo từng bước—chứa phần tử $(N+1)$. Nó chỉ ra rằng trong bài toán của chúng tôi, chỉ cần tìm kiếm sự kiểm soát tối ưu giữa các bước là đủ.

Định lý. Đối với mọi điều khiển $\overline{\lambda}$ đều có điều khiển $\overline{\omega}$ sao cho $F(\overline{\omega}) \geqslant F(\overline{\lambda})$.

Thật vậy, theo Dự luật II, tồn tại một điều khiển $\overline{\mu} = (\mu_0, \dots, \mu_{N-1})$ sao cho $\mu_i$ bằng 0 hoặc một cho bất kỳ $i = 0, \dots, N-1$ và $F(\overline{\mu}) \geqslant F(\overline{\lambda})$ nào. Hơn nữa, chúng tôi lưu ý rằng nếu có số 0 trong số $\mu_0, \dots, \mu_{N-1}$, thì bằng cách hoán đổi nó với số theo sau nó, chúng tôi sẽ không làm giảm giá trị của hàm mục tiêu $F$ nhờ vào Mệnh đề I. Bằng những hoán vị như vậy, tất cả các số 0 có thể được chuyển đến cuối tập xác định điều khiển, tức là đi đến điều khiển bước nào đó $\overline{\omega}$ và các bất đẳng thức sẽ được thỏa mãn $F(\overline{\omega}) \geqslant F(\overline{\mu}) \geqslant F(\overline{\lambda})$. Định lý đã được chứng minh.

Bây giờ chúng ta hãy chọn điều khiển tối ưu trong số các điều khiển bước. Theo công thức (2) và (4)
$$F(\overline{\theta}^{(m)}) = (N - m)a(1 + a)^m x_0.$$
Kích cỡ
$$C_m = \frac{F(\overline{\theta}^{(m+1)})}{F(\overline{\theta}^{(m)})} = (1 + a)\left(1 - \frac{1}{N - m}\right)$$
giảm khi $m$ xảy ra. Chúng ta hãy biểu thị bằng $M$ số nguyên đầu tiên lớn hơn hoặc bằng 0 và $N-1 - \frac{1}{a}$.
Khi đó, do định nghĩa số $C_m$ và cách chọn số $M$ nên bất đẳng thức
$$C_0 > C_1 > \dots > C_{M-1} > 1 \geqslant C_M > C_{M+1} > \dots > C_{N-1}.$$
Kể từ đây,
$$F(\overline{\theta}^{(0)}) < \dots < F(\overline{\theta}^{(M)}) \geqslant F(\theta^{(M+1)}) > F(\overline{\theta}^{(M+2)}) > \dots > F(\overline{\theta}^{(N)}).$$
Do đó, điều khiển $\overline{\theta}^{(M)}$ có thể được chọn là tối ưu.
Hãy quay lại bài toán của chúng ta từ “bản thảo cổ”. Dành cho cô ấy $N = 10$, $u = \frac{1}{5}$ và $M = 4$. Như vậy, điều khiển $\overline{\theta}^{(4)} = (1, 1, 1, 1, 0, \dots, 0)$ sẽ là tối ưu và giá trị của hàm mục tiêu - tổng số tiền bỏ ra trong 10 năm - khi chọn điều khiển theo cách này là
$$F(\overline{\theta}^{(4)}) = \left(1 + \frac{1}{5}\right)^4 \times 10^5 \frac{6}{5} \approx 248832 \text{ реал.}$$

Vì vậy, lời giải bài toán, do các anh hùng vương miện của chúng ta đề xuất, thực sự không phải là tối ưu. Lưu ý rằng điều khiển $\overline{\theta}^{(5)}$ cũng là tối ưu, vì nói chung, các số 0 được chọn trong số các bước, không phải theo cách duy nhất.

Bài toán 1. Điều kiện nào trên $a$ và $N$ đảm bảo tính duy nhất của điều khiển tối ưu giữa các bước?

Vấn đề 2. Có đúng là để điều khiển tối ưu bài toán của chúng ta nhất thiết phải theo từng bước không?

Bài toán 3. Tìm số năm nhỏ nhất $N > 10$ sao cho việc quản lý Lopez tằn tiện $(1, \dots, 1, 0)$ hóa ra vẫn mang lại nhiều lợi nhuận hơn cách quản lý $(0, 0, \dots, 0)$ do Alonso lãng phí đề xuất.