Vật lý và bất đẳng thức tuyến tính

Kvant 1975, số 10 tr. 17-22 Thẻ UAXD

Bản dịch tự động sơ bộ, chất lượng thấp: có thể còn lỗi và câu chữ chưa tự nhiên. Bản này sẽ được thay bằng bản dịch tốt hơn. Bản gốc →

Vật lý và bất đẳng thức tuyến tính
Z. Vâng. Tymeladze

Cơ học

Những tiếng đại bác của cuộc cách mạng vang rền trên đường phố Paris. Cú bắn nho của lính canh làm rung chuyển lớp thạch cao ngay cạnh chướng ngại vật.
“Em có bị thương không, Etienne?”

Không có gì, chỉ là một vết xước thôi. Đội Vệ binh Hoàng gia đang bắn từ ngôi biệt thự có cột trụ đó. Nếu không đưa họ ra khỏi đó, chúng ta sẽ không thể cầm cự được cho đến khi đội thợ in đến.
Súng của chúng ta sẽ không chạm tới chúng phải không?
Không, chỉ từ this_maxina thôi là chưa đủ. Bây giờ, giá như cô ấy có thể được lăn lên bục đó! Này, Jean-Baptiste… Ồ, chuyện này nghiêm trọng hơn,” Etienne rên rỉ, ôm chặt lấy ngực anh.
Ông bị sao vậy, thưa ông?
Công dân Etienne, không phải ông! Cậu bé không còn ở tu viện Benedictine nữa mà ở trong quân đội cách mạng. Trong khi họ gọi tôi ra, hãy cùng mọi người lăn khẩu đại bác đến khu vực đằng kia.
Vâng, thưa công dân Etienne!
“Đợi đã,” Pierre cùng nói. - Liệu trang web có trụ vững được không? Nếu nó sụp đổ, chúng ta sẽ mất khẩu súng duy nhất.
“Đây là cơ hội cuối cùng của chúng ta,” Etienne nói, bất tỉnh.
-Bạn đang vẽ gì vậy, Jean-Baptiste? Hình học nữa à? Tốt hơn hết hãy lấy súng của bạn, chúng ta không thể mạo hiểm với súng!
Công dân Pierre! Lợi dụng sự bình tĩnh, tôi sẵn sàng chứng minh cho bạn thấy rằng không có rủi ro. Súng có thể cuộn vào.
Được, tôi sẽ cố gắng! Tôi đến những rào cản từ trường đại học, từ đầm lầy này, nơi sự tầm thường sinh sôi nảy nở. Tôi thề sẽ không quay lại đó cho đến khi các giáo sư bị cấm giảng bài trên giấy gian lận. Vì thế?

— Bệ có dạng hình vuông có cạnh 4 mét, tựa trên bốn cột (xem Hình 1). Mỗi cột bắn ra một tấn, khẩu pháo cùng với tổ lái và đạn đại bác nặng 2,5 tấn. Bản thân nền tảng này đã đáng tin cậy, chỉ có các cột mới có thể bị gãy, phải không, Citizen Pierre?

Hãy nói; nhưng hãy nhớ rằng các cột với nhau sẽ chỉ chịu được 4 tấn nếu tải trọng được đặt ở giữa mặt bằng. Và chúng ta sẽ phải hạ khẩu pháo xuống sao cho trọng tâm của nó ở điểm M - nếu không chúng ta sẽ không thể bắn xuyên qua dinh thự.
Bây giờ hãy xác định lực tối đa có thể tác dụng.

Cơm. 1.

đặt tại điểm $M$ . Nếu lực lượng này lớn hơn khẩu đại bác thì mọi chuyện đã ổn thỏa, và chúng ta sẽ khiến những người lính canh phải trả giá đắt cho cái chết của Etienne. Chúng ta hãy biểu thị các số trên các cột nơi nền tảng nằm trên $R_1, R_2, R_3$ và $R_4$ và yêu cầu phải có

$\begin{cases} R_1 \leqslant 1, \\ R_2 \leqslant 1, \\ R_3 \leqslant 1, \\ R_4 \leqslant 1. \end{cases}$

Giá trị dương của các số biểu thị độ dốc trong các cột, các giá trị được in dấu biểu thị độ giãn dài.

Đúng vậy, nhưng thế thì sao? Rốt cuộc, đây là những bất đẳng thức, không phải phương trình, chúng ta có thể nói gì về chúng? Tôi không nhớ những công dân tốt Lagrange và d’Alembert đã viết gì về họ.

“Và tôi không nhớ, mặc dù tôi đã nghiên cứu tác phẩm của họ.” Nhưng hãy tiếp tục lý luận của chúng tôi. Các lực $R_1, R_2, R_3$ và $R_4$ không thể là bất kỳ lực nào mà chúng phải thỏa mãn điều kiện cân bằng. Hai trong số chúng thu được nếu chúng ta đánh đồng các khoảnh khắc từ tất cả các lực tác dụng lên bệ so với các đường 1-4 và 1-2 bằng 0. Xét rằng mô men là tích của các lực trên bề mặt, chúng ta thu được hai phương trình:

$4R_2 + 4R_3 - P = 0,$

$4R_3 + 4R_4 - 2,5P = 0.$

Phương trình cân bằng thứ ba phải đạt được từ đẳng thức đến 0 của tổng tất cả các lực tác dụng lên bệ - nếu không thì bệ này sẽ rơi xuống hoặc bay lên trời.

Giống như tên lừa bịp đó mà giới tăng lữ rất tôn kính! - Pierre đứng dậy.
Từ đây ta có phương trình

$R_1 + R_2 + R_3 + R_4 = P,$

Jean-Baptiste viết, đỏ mặt vì sự hóm hỉnh phong phú của nhà tư tưởng sóng hơn là vì viên đạn sượt qua tai. Trong ba phương trình (2), (3) và (4), tất nhiên có bốn ẩn số $R_1, R_2, R_3, R_4$ không thể xác định được. Nhưng bạn có thể thêm điều kiện sau: lực $P$ phải lớn nhất. Hãy viết nó như thế này: $P \rightarrow \text{max.} \text{Кроме того, у нас есть еще неравенства (1).}$

— Chudnya bài toán“,” đồng bào Pierre nói với khuôn mặt nhăn nheo. “Tôi sẽ không ngạc nhiên nếu nó không có tên trong năm mươi năm nữa.” Chưa kể đến những công dân của D’Alembert và Lagrange, những người vì lý do nào đó đã có nó…

Jean-Baptiste tiếp tục: “Hãy gạt bỏ cái bóng của những người vĩ đại sang một bên và giải quyết bài toán đơn giản này. “Để làm điều này, hãy biểu thị $R_3$ và $R_4$ từ phương trình (2) và (3):

$R_3 = \frac{1}{4}P - R_2,$

$R_4 = \frac{1}{4}\left(\frac{5}{2}P - 4R_3\right) = \frac{3}{8}P + R_2$

và thay thế các giá trị của chúng vào phương trình (4); chúng tôi nhận được:

$R_1 + R_2 + \frac{1}{4}P - R_2 + \frac{3}{8}P + R_2 = P.$

Từ đây bạn có thể tìm thấy $P$ :

$P = \frac{8}{3}(R_1 + R_2)$

và thay vào phương trình (5):

$R_3 = \frac{2}{3}R_1 - \frac{1}{3}R_2, \quad R_4 = R_1 + 2R_2.$

Bây giờ hệ bất đẳng thức (1) chỉ có thể được viết lại cho hai biến $R_1$ và $R_2$ (các biến còn lại được loại trừ bằng ba phương trình):

$\begin{cases} R_1 \leqslant 1, \\ R_2 \leqslant 1, \\ \frac{2}{3}R_1 - \frac{1}{3}R_2 \leqslant 1, \\ R_1 + 2R_2 \leqslant 1. \end{cases}$

Được rồi, nhưng có thể tranh cãi được không? Ngọn lửa đang ngày càng dữ dội.

Cơm. 2.

Cơm. 3.

Không còn lại nhiều đâu. Hãy mô tả những bất bình đẳng này bằng đồ họa. Hãy để chúng tôi giới thiệu các trục tọa độ $R_1$ và $R_2$ (Hình 2).

Bất đẳng thức $R_1 \leqslant 1$ có nghĩa là các giá trị cho phép $R_1$ không nằm ở bên phải của dòng $R_1 = 1$ , mà là $R_2 \leqslant 1$ , không nằm ở trên dòng $R_2 = 1$ - chúng tôi biểu thị điều này bằng cách tô bóng. Thay $R_1 = 0$ , từ bất đẳng thức thứ ba của hệ (7) ta tìm được $R_2 \geqslant -3$ , và thay $R_2 = 0$ , ta được $R_1 \leqslant 3/2$ . Vẽ một đường thẳng đi qua các điểm có tọa độ $(0, -3)$ và $\left(\dfrac{3}{2}, 0\right)$ và tô bóng từ trên xuống, chúng ta thu được biểu diễn đồ họa của bất đẳng thức thứ ba. Cuối cùng, chúng ta mô tả bất đẳng thức thứ tư theo cách tương tự.

Nhưng có vẻ như không phải tất cả những dòng này đều cần thiết.
Phải! Điều quan trọng nhất được trình bày trong Hình 3, trong đó phạm vi giá trị cho phép của các lực $R_1$ và $R_2$ được tô bóng. Các điểm bên trong miền này, kể cả biên, thỏa mãn mọi bất đẳng thức. Nhưng đó không phải là tất cả. Trong vùng chấp nhận được, chúng ta cần tìm một điểm mà tại đó $P$ , được xác định bởi đẳng thức (6), có giá trị lớn nhất. Đầu tiên, hãy vẽ một đường

$P = \frac{8}{3}\,(R_1 + R_2) = 0.$

Nó đi qua gốc tọa độ như hình 3.

“Nhưng điều này không mang lại cho chúng tôi nhiều điều: rõ ràng là nền tảng sẽ chịu được lực bằng không.”

Tất nhiên rồi. Nhưng tại sao nó sẽ tồn tại? Vì đường $P = 0$ cắt vùng cho phép.
Chờ đợi! Nó không hoàn toàn rõ ràng với tôi. Có những điểm trên đường $P = \dfrac{16}{9}$ nằm ngoài vùng khả thi, chẳng hạn như điểm $K$ . Nếu sự phân bố lực tương ứng với điểm này xảy ra trong các trụ thì bệ sẽ sụp đổ và…
Anh sai rồi. Mặc dù tôi không thể chứng minh điều này nhưng tôi cảm thấy: nếu vật liệu của các trụ cột là nhựa thì kết cấu sẽ không sụp đổ ở $P = \dfrac{16}{9}$ . Sự phân bố lực sẽ xuất hiện trong đó, được biểu thị bằng một điểm nào đó $E$ bên trong vùng chấp nhận được. Đúng là không biết điểm nào, nhưng điều đó không quan trọng.

Bây giờ chúng ta hãy xem xét họ dòng $P = \dfrac{8}{3}\,(R_1 + R_2) = \mathrm{const} > 0$ . Chúng song song với đường thẳng $P = 0$ (xét cho cùng, chúng có cùng hệ số góc). Từ những đường này, bạn cần chọn đường xa nhất với đường $P = 0$ , nhưng đồng thời giao với vùng cho phép. Đây là đường $P = \dfrac{8}{3}\,(1 + 0) = \dfrac{8}{3}$ đi qua điểm $B$ có tọa độ $R_1 = 1$ , $R_2 = 0$ . Rõ ràng chứ?

Thành thật mà nói thì không hẳn. Đã lâu rồi tôi không làm toán. Cuộc cách mạng đòi hỏi tôi phải nhìn vào bản đồ địa lý thường xuyên hơn là nhìn vào sách giáo khoa hình học.
Tuyệt vời! Hãy nhớ địa lý! Hãy tưởng tượng rằng $ABC$ là ranh giới của một địa điểm trên mặt đất tăng dần từ tây nam sang đông bắc và các đường $P = \mathrm{const}$ là các đường đồng mức trên bản đồ địa lý. Độ cao địa hình càng cao thì giá trị $P$ càng lớn. Rõ ràng là điểm cao nhất sẽ ở điểm $B$ , trong đó $P = \dfrac{8}{3} = 2\,\dfrac{2}{3}$ . Cái này nặng hơn khẩu súng $\left(2\,\dfrac{2}{3} > 2\,\dfrac{1}{2}\right)$ của chúng tôi. Điều này có nghĩa là nền tảng sẽ chịu được pháo.
Hãy cuộn súng lên, hỡi các công dân! - Pierre hét lên thay vì đáp số: sự tấn công dữ dội của lính canh ngày càng lớn, và không thể chần chừ được nữa. - Công dân Jean-Baptiste Fourier! Bạn nên là giáo sư toán học! Cái chết cho bạo chúa!

Và Jean-Baptiste Fourier trở thành giáo sư toán học tại một cơ sở giáo dục mới được thành lập vào năm 1794 - Trường học Bình thường! Các đối thủ cạnh tranh không đủ năng lực không thể ngăn cản điều này: cùng năm đó, Công ước mang tính cách mạng đã thực sự thông qua luật cấm các giáo sư sử dụng ghi chú trong các bài giảng.

Sự ra đời của lập trình tuyến tính

Chỉ trong những năm cuối đời, vào năm 1823, nhà toán học được công nhận Jean-Baptiste Fourier (1768-1830), một người bạn cũ của Napoléon, cựu thống đốc khoa Isère và là người sáng tạo ra “Lý thuyết Nhiệt”, đã đưa ra một báo cáo có phần kỳ lạ vào thời đó về các bất đẳng thức tuyến tính tại Học viện Pháp, trong đó ông giải thích công thức và chỉ ra con đường lời giải

được mô tả ở trên bài toán. Nhưng chẳng phải trước đó anh ta đã rõ điều đó khi còn trẻ, khi anh ta đến Paris cách mạng sao? Xét cho cùng, không có gì đặc biệt phức tạp trong bài toán này - trong mọi trường hợp, lý thuyết về chuỗi Fourier, của cùng một tác giả, phức tạp hơn nhiều.

Tuy nhiên, tên của bài toán - lập trình tuyến tính - chỉ ra đời vào những năm bốn mươi của thế kỷ chúng ta. Các ứng dụng nổi tiếng nhất của quy hoạch tuyến tính có liên quan đến kinh tế học *). Tuy nhiên, nhu cầu tìm cực trị của hàm tuyến tính dưới các ràng buộc dưới dạng hệ phương trình tuyến tính và bất đẳng thức nảy sinh trong rất nhiều bài toán, bao gồm cả những bài toán rất xa kinh tế học. Một ví dụ là cơ học được thảo luận ở trên bài toán về tác dụng của một lực tập trung lên một tấm hình vuông - ứng dụng đầu tiên của quy hoạch tuyến tính mà chúng ta biết đến.

Ở dạng tổng quát hơn, quy hoạch tuyến tính bài toán được xây dựng như sau. Có n ẩn số $x_1, x_2, \ldots, x_n$ . Cần phải tìm các giá trị của chúng thỏa mãn hệ giới hạn

$\left\{\begin{array}{l} a_{11}x_1 + \ldots + a_{1n}x_n \leqslant a_1, \\ a_{21}x_1 + \ldots + a_{2n}x_n \leqslant a_2, \\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot \\ a_{r1}x_1 + \ldots + a_{rn}x_n \leqslant a_r, \\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot \\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot \\ a_{m1}x_1 + \ldots + a_{mn}x_n \leqslant a_m \end{array}\right.$

và cung cấp chức năng tối đa

$z = p_1x_1 + p_2x_2 + \ldots + p_nx_n,$

được gọi là “mục tiêu”. Các hệ số $a_{11}, a_{12}, \ldots, a_{mn}$ và số hạng tự do $a_1, \ldots, a_m$ được coi là đã cho.

*) Xem bài: A. B. Katok, Kinh tế học và bất bình đẳng tuyến tính, «Kvant», 1971, số 3, 4.

Đôi khi, cùng với mức tối đa của hàm mục tiêu, cần phải tìm mức tối thiểu của nó - điều này phụ thuộc vào ý nghĩa của bài toán (trong trường hợp này, bạn có thể tìm mức tối đa của hàm $z_1 = -z$ ). Lưu ý rằng cực trị của hàm $z$ (cực tiểu hoặc cực đại) luôn nằm trên biên của vùng chấp nhận được. Tính năng này sử dụng phương pháp lập trình tuyến tính lời giải bài toán phổ biến nhất - phương pháp đơn hình mà chúng tôi sẽ không đề cập ở đây.

Nhưng còn sự biện minh vật lý của bài toán Fourier thì sao? Ông có đúng khi tin rằng chính thiên nhiên đã giúp cấu trúc tìm ra, có lẽ, sự phân bố duy nhất của các điều kiện bên trong mà theo đó cấu trúc có khả năng cô lập tải trọng bên ngoài? Vâng, điều này đúng với vật liệu dày đặc. Trên thực tế, cơ học đã nghi ngờ sự cản trở này ngay cả trước Fourier, nhưng lý thuyết có cấu trúc chỉ được xây dựng vào năm 1936 bởi nhà khoa học Liên Xô A. A. Gvozdev. Theo lý thuyết này, bản thân thiết kế, như thể tuân theo bản chất mỏng, sẽ giải quyết quy hoạch tuyến tính bài toán nêu trên và tự tìm ra sự phân bố hiện có của các điều kiện bên trong. Nó sẽ được tìm thấy, nếu nó tồn tại - với tải trọng 3 tấn trên khu vực được đề cập, phân bố các điều kiện trong các cột, nó sẽ không còn được tìm thấy nữa và nền tảng sẽ sụp đổ.

Điện

Để xác minh khả năng ứng dụng của quy hoạch tuyến tính vào mạng điện, chúng ta hãy chuyển từ đường phố Paris sang quy mô hiện đại. Nhà phát minh Vitya và Kolya lắp ráp một thiết bị bí ẩn (mục đích mà họ yêu cầu không nói đến) theo sơ đồ được trình bày trong Hình 4.

Thiết bị này bao gồm hai nguồn EMF, ba điện trở và ba thiết bị, được gọi là

Cơm. 4.

đại diện cho bí mật nghề nghiệp của nhà phát minh. Chúng tôi chỉ phát hiện ra rằng thiết bị số 1 yêu cầu dòng điện ít nhất là 2 A, thiết bị số 2 - ít nhất là 1 A và trên thiết bị số 3, điện áp phải ít nhất là 1,5 V. Mọi thứ đã sẵn sàng để bắt đầu thử nghiệm khi phát hiện ra khó khăn cần thiết: Viti và Kolya chỉ có 5 pin với mỗi pin có 1 suất điện động. Nỗ lực bật chúng một cách khoa học đã không dẫn đến thành công: các thiết bị không bị hỏng. Các nhà phát minh đã đi vào ngõ cụt, nhưng sau đó Kolya nhớ đến quy hoạch tuyến tính và bắt đầu suy luận.

— Bài toán có thể được hình thành như sau. Cần phải chọn các nguồn EMF sao cho chúng cung cấp dòng điện và hướng được chỉ định trong mạng và lượng EMF ở mức tối thiểu:

$z = E_1 + E_2 \rightarrow \min.$ (8)

Công thức (8) xác định hàm mục tiêu bài toán của quy hoạch tuyến tính. Hãy đưa ra những hạn chế. Tổng dòng điện trong mỗi mạng phải bằng 0:

$-I_1 + I_2 - I_3 = 0.$ (9)

Mạng bao gồm hai mạch, dọc theo mỗi mạch, tổng điện áp được hướng đến tổng của emf:

$I_1 + 2I_2 = E_1 + E_2,$ (10)

$2I_2 + I_3 = E_2.$

Cơm. 5.

Cuối cùng, tính đặc thù của các thiết bị bí mật đòi hỏi dòng điện và điện áp trong chúng phải chịu những hạn chế.
$I_1 \geq 2, I_2 \geq 1, |U_3| \geq 1, 5$ . (11)
Bài toán tìm các giá trị $I_1, I_2, I_3, E_1, E_2$ thỏa mãn các ràng buộc (9)–(11) và cung cấp mức tối thiểu của hàm mục tiêu (8) là bài toán của lập trình tuyến tính. Đã biểu thị từ phương trình (9) và (10) dòng điện chạy qua emf $E_1$ và $E_2$ : $I_1 = \frac{1}{5} (3E_1 + E_2)$ ,
$I_2 = \frac{1}{5} (E_1 + 2E_2)$ , $I_3 = \frac{1}{5} (-2E_1 + E_2)$ và thay thế các giá trị EMF vào các bất đẳng thức (11), chúng ta thu được ba hạn chế:
$\begin{cases} 3E_1 + E_2 \geq 10, \\ E_1 + 2E_2 \geq 5, \\ |-2E_1 + E_2| \geq 7, 5. \end{cases}$

“Anh ấy không hiểu,” Vitya, người cũng quen thuộc với lập trình tuyến tính, nói. - Ở đây có dấu mẫu, bạn sẽ làm gì với nó?

— Tôi sẽ viết ràng buộc thứ ba dưới dạng hai bất đẳng thức
$E_2 - 2E_1 \geq 7, 5; E_2 - 2E_1 \leq -7, 5,$

Kolya gửi. — Bây giờ, hãy vẽ các đường thẳng tương ứng với tất cả các bất đẳng thức-ràng buộc (xem Hình 5) và thu được hai vùng chấp nhận được $\Omega_1$ và $\Omega_2$ ( $E_1$ và $E_2$ dương)

Cơm. 6.

và đường thẳng tương ứng với hàm mục tiêu. Có thể thấy từ hình vẽ rằng lời giải tối ưu đạt được tại điểm $A$ , tại đó $E_1 = 4, E_2 = 0, 5$ .

“Bạn không thể nghiền nát pin,” Vitya, chủ sở hữu pin phản đối. — Lời giải phải là số nguyên. Hãy làm tròn lời giải thành số nguyên: ghép $E_1$ bốn pin lại với nhau và $E_2$ một pin lại với nhau.

“Hãy dành thời gian và đặt mỏ hàn xuống,” Kolya nhạy cảm ngăn anh lại. — Rõ ràng điểm $E_1 = 4, E_2 = 1$ nằm ngoài vùng cho phép, thiết bị thứ ba sẽ không hoạt động.

Đây là cách những người bạn của chúng tôi khám phá ra thuộc tính duy nhất bài toán của lập trình tuyến tính: lời giải không phải lúc nào cũng được làm tròn thành giá trị nguyên. Vì lý do này, lập trình tuyến tính số nguyên phải được phát triển đặc biệt để giải quyết khó khăn này. May mắn thay các bạn