Tùy chọn tốt nhất

13

3. Litovchenko

Tùy chọn tốt nhất

Hãy tưởng tượng bạn là hiệu trưởng một trường nội trú và bạn cần lập thực đơn cho căng tin trong tuần. Tất nhiên, việc lên thực đơn chi tiết là công việc của người đầu bếp nhưng bạn cần đảm bảo không tiêu tốn quá nhiều tiền.

Bạn biết những sản phẩm bạn có thể mua và giá của chúng. Tuy nhiên, ngoài giá cả, chúng còn có nhiều phẩm chất khác như hàm lượng calo, hàm lượng một số vitamin, v.v. Vì vậy, ngoài giá cả, bạn cần cân nhắc khá nhiều điều kiện khi mua sản phẩm. Hơn nữa, nếu trong kho có rất nhiều sản phẩm thì bài toán sẽ trở nên rất khó hiểu và khó giải quyết nếu không có máy tính. Tuy nhiên, nếu sản phẩm và điều kiện ít thì việc đối phó không khó.

Hãy xem xét ví dụ này. Hãy để thực đơn gần như được chuẩn bị đầy đủ, bạn chỉ cần đảm bảo rằng nó chứa đủ vitamin A và C, trong kho còn có anh đào và mơ. Một bàn có hai quả A (gw1 kg) và C (gw1 kg)

Anh đào 3 150
Quả mơ 24 75

$$\begin{cases} 0,003x + 0,024y \geq 6, \\ 0,15x + 0,075y \geq 75, \\ x \geq 0, y \geq 0, \end{cases}$$

và $z = 0,25x + 0,3y$ sẽ là tối thiểu. Trên mặt phẳng $xOy$ dễ dàng chỉ ra tập hợp các điểm $M$ thỏa mãn hệ (Hình 1). Nó được gọi là đa giác của hệ thống lời giải. Rõ ràng là các đường $z = 0,25x + 0,3y$ ở các $z$ khác nhau song song với cùng một hướng và với mức tăng $z$ chúng sẽ di chuyển ra khỏi gốc. Do đó, chúng ta cần tìm một trong các đường thẳng theo hướng này có điểm chung với đa giác $M$ và gần gốc tọa độ nhất. Có thể dễ dàng nói rằng một đường như vậy không được giao nhau $M$ tại các điểm bên trong - khi đó nó sẽ không phải là “thấp nhất” (Hình 2). Do đó, nó phải đi qua một trong các đỉnh của đa giác. Nhưng điểm này là đỉnh $C$. Vì vậy, bạn cần mua 400 kg chấy và 200 kg mơ - phương án tốt nhất!

Một nhiệm vụ tương tự như nhiệm vụ được phân tích được gọi là lập trình tuyến tính bài toán. Trong đó, bạn cần tìm một đường thẳng (trong không gian ba chiều - một mặt phẳng, trong không gian đa chiều - cái gọi là siêu phẳng), thuộc một tập hợp các đường thẳng song song (mặt phẳng, siêu phẳng), giao nhau với một đa giác (đa giác) nhất định và nằm gần gốc tọa độ nhất. Bạn cũng có thể đưa ra một dạng đại số thuần túy -

14

Hình 1.

Bạn có cần nuôi cáo Bắc Cực và cáo Bắc Cực sao cho chi phí trung bình cho một bộ da là tối thiểu nếu chi phí nuôi một con cáo là 45 rúp và một con cáo Bắc Cực là 25 rúp?

Lời giải. Gọi $x$ là số cáo được nuôi và $y$ là số cáo Bắc Cực. Sau đó

$$\begin{cases} 4x + 5y \leq 80000 \\ \frac{1}{2}x + y \leq 10000 \\ x \geq 3000 \\ y \geq 6000. \end{cases}$$

Chi phí trung bình của một làn da

$$z = \frac{45x + 25y}{x + y}.$$

Muliku: có hệ bất đẳng thức tuyến tính

$$\begin{cases} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \geq b_1, \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n \geq b_2, \\ \dots \\ a_{k1}x_1 + a_{k2}x_2 + \dots + a_{kn}x_n \geq b_k \end{cases}$$

và hàm tuyến tính $z = c_1x_1 + \dots + c_nx_n$. Chúng ta cần tìm lời giải của hệ thống này mà giá trị của hàm $z$ là tối thiểu. Đã có nhiều bài viết về quy hoạch tuyến tính ở «Kvant» (1971 - Số 3, trang 1 và số 4, trang 1, 1974 - Số 7, trang 13, 1975 - Số 10, trang 17, 1976 - Số 7, trang 2, 1977 - Số 8, trang 29).

Hãy giải quyết thêm một câu nữa bài toán: người vận chuyển động vật nuôi cáo Bắc Cực và cáo Bắc Cực; nó có 10.000 tế bào, và hai con cáo hoặc một con cáo Bắc Cực có thể sống trong một tế bào; Theo kế hoạch, phải nuôi ít nhất 3.000 con cáo và ít nhất 6.000 con cáo Bắc Cực; mỗi ngày, một con cáo được cho ăn 4 đơn vị thức ăn và một con cáo Bắc Cực - 5 đơn vị; chỉ trong một ngày được phép loại bỏ không quá 80.000 đơn vị thức ăn chăn nuôi; Bao nhiêu

15

Hình 3.

vị trí của giá trị trên các đường đi qua gốc tọa độ. Chúng ta cần tìm một trong những đường thẳng này cắt đa giác F và trên đó giá trị của hàm z là nhỏ nhất. Cũng như trên, rõ ràng đường thẳng này không chứa các điểm bên trong của đa giác F. Do đó, chỉ cần so sánh các đường OA và OB với nhau là đủ. TRẢ LỜI: $x=3000$ và $y=8500$.

Lưu ý rằng với lời giải cái bài toán này, chúng tôi đã may mắn - chúng tôi có được toàn bộ đáp số. Xét cho cùng, nếu số lượng cáo hoặc cáo Bắc Cực không phải là số nguyên thì chúng ta đã không thể sử dụng đáp số. Hơn nữa, nếu chúng tôi nhận được một đáp số không nguyên, chúng tôi không thể nói bất cứ điều gì về đáp số chính xác. Hóa ra là có thể chọn các điều kiện bài toán sao cho những đáp số này sẽ khác nhau nhiều nhất có thể.

Trong trường hợp đáp số phải được đưa ra dưới dạng số nguyên, chúng ta xử lý bài toán của lập trình số nguyên. Lời giải trong số bài toán này khó hơn nhiều so với lời giải bài toán của ràng buộc này.

Tóm lại, một bài tập dành cho độc giả:

Hai tàu phải chuyển hàng theo Bảng 2.

Được biết, con tàu thứ nhất có thể thực hiện không quá 5 chuyến và chuyến thứ hai - không quá 9. Lập kế hoạch vận chuyển đảm bảo a) xấp xỉ tối đa;
b) Chi phí vận chuyển một tấn hàng hóa là thấp nhất.

Sửa đổi

Ở số 3 của “Quaita” năm 1978 trên trang. Số 11 ở dòng thứ tám tính từ cột trên cùng bên trái là “M. P. Bronstein.”
Ở số 11 của “Quaita” năm 1977 trên trang. Số 27 ở dòng thứ hai từ dưới lên ở cột bên phải là “Năm 1928”.