Một số bài toán tối ưu và ý nghĩa
Ví dụ bài toán tối ưu
Bài toán 1.1 Vẽ nội tiếp trong hình tròn với bán kính cho trước một hình chữ nhật có diện tích lớn nhất.
Bài toán 1.2 Cho tam giác ABC Hãy tìm điểm E trên cạnh BC sao cho hình bình hành ADEF, với D, F nằm trên AB và AC có diện tích lớn nhất.
Để tối ưu hóa việc xây dựng một nhà kho hình hộp chữ nhật với thể tích lớn nhất, cần xác định cách sử dụng hiệu quả một lượng vật liệu nhất định Bài toán 1.3 đặt ra yêu cầu tìm ra phương án thiết kế nhằm tối đa hóa thể tích kho chứa, từ đó nâng cao hiệu suất sử dụng không gian lưu trữ.
Ý nghĩa thực tiễn
Các bài toán tối ưu trong lý thuyết và thực tiễn có thể được giải quyết bằng nhiều phương pháp khác nhau Bên cạnh việc sử dụng phương pháp hình học thuần túy, chúng ta cũng có thể mô hình hóa các bài toán này dưới dạng giải tích để tìm ra các giải pháp hiệu quả hơn.
Quay lại với Bài toán 1.1 Ta có thể mô hình hóa lại bài toán trên dưới dạng giải tích như sau:
Giả sử đường tròn được mô tả bởi phương trình x 2 + y 2 = r 2 (r > 0 cho trước), vẽ các trụcOx và Oy song song với các cạnh của hình chữ nhật.
Kí hiệu (x, y) là tọa độ của đỉnh hình chữ nhật tại góc phần tư thứ nhất (hình 1.1).
Khi đó diện tích hình chữ nhật bằng 4xy.
Từ đó ta có bài toán: tìm cực đại của hàm hai biếnf (x, y) = 4xy với các điều kiện: i) g 1 (x, y ) = x 2 + y 2 − r 2 = 0; ii) g 2 (x, y) = x> 0 ; ii) g 3 (x, y) = y> 0
Bài toán hình học có thể được chuyển đổi sang ngôn ngữ giải tích, giúp dễ dàng tiếp cận và giải quyết nhờ vào các công cụ khác Tất cả các bài toán đã được hình thức hóa đều có thể xây dựng theo cách tương tự, bao gồm những yếu tố quan trọng.
Phiếm hàm f được định nghĩa từ X đến R ∪ {−∞; +∞}, trong đó f là phiếm hàm và D là ràng buộc thuộc X Bài toán có thể được phát biểu lại như sau: f: R² → R, với max f(x, y) = max 4xy, và ràng buộc x² + y² = r², x > 0, y > 0 Ràng buộc D được xác định là tập hợp các điểm (x, y) thuộc R² thỏa mãn điều kiện x² + y² = r² và x, y đều dương.
Hình chữ nhật cần tìm trong bài toán này chính là hình vuông cạnh bằng √ r
√ 2 và f max = 2r 2 tương ứng diện tích hình chữ nhật lớn nhất khi đó là 2r 2
Mô hình và phương pháp giải bài toán tối ưu
Tập lồi
Định nghĩa 1.4 Đường thẳng đi qua hai điểm a, b trong không gian Euclid n-chiều
R n là tập hợp các điểm x ∈R x = λa + (1 − λ) b, λ ∈R Định nghĩa 1.5 Đoạn thẳng nối hai điểm a, b trong R n là tập hợp các điểm x ∈ R có dạng x = λa + (1 − λ) b, 06 λ61. Định nghĩa 1.6 Siêu phẳng trong R n là tập
{ x = (x 1 , x 2 , x n ) | x 1 a 1 + x 2 a 2 + + x n a n = α, a i ∈R , ∀ i = 1 n, α ∈ R } Định nghĩa 1.7 (Tập lồi) Tập D ⊂R n được gọi là tập lồi nếu
∀ a, b ∈ D và λ ∈ [0; 1] ta có λa + (1 − λ) b ∈ D. Định nghĩa 1.8 (Nón lồi) Tập D ⊂R n được gọi là nón lồi nếu
∀ a, b ∈ D thì x + y ∈ D vàtx ∈ D, ∀ t > 0 Định nghĩa 1.9 (Bao lồi) Bao lồi của tập A là tập lồi nhỏ nhất chứa A Kí hiệu CovA. Định nghĩa 1.10 (Tổ hợp lồi của hai tập hợp)
Tập hợp lồi của hai tập A và B trong R^n được định nghĩa là tập hợp các điểm x có dạng x = λa + (1 − λ)b, với a thuộc A, b thuộc B và 0 ≤ λ ≤ 1 Định lý 1.1 chỉ ra rằng tập lồi là đóng với các phép toán như giao, cộng, nhân với một số, và tổ hợp tuyến tính Cụ thể, nếu A và B là hai tập lồi trong R^n, thì các tập hợp sau đây cũng sẽ là tập lồi: i) Giao của A và B, ký hiệu A ∩ B, là tập hợp các điểm x thuộc cả A và B ii) Tập hợp αA + βB, được định nghĩa là tập hợp các điểm x = αa + βb, với a thuộc A, b thuộc B và α, β thuộc R.
Hàm lồi
Trong luận văn này chỉ xét các hàm số thực và nhận giá trị hữu hạn. Định nghĩa 1.11 ∀ x, y ∈ A, 06 λ 6 1
• Hàm số f xác định trên tập lồi A được gọi là hàm lồi trên A nếu: f (λx + (1 − λ) y)6 λf (x) + (1 − λ) f (y) , ∀ x, y ∈ A, 0 6 λ 6 1
• Hàm f được gọi là lồi chặt nếu : f (λx + (1 − λ) y) < λf (x) + (1 − λ) f (y) , ∀ x, y ∈ A, 0 < λ < 1.
• Hàm f được gọi là tựa lồi (quasi convex) trên A nếu:
∀ λ ∈R, tập mức { x ∈ A | f (x)6 λ } là một tập lồi.
• Hàm f được gọi là tựa lõm (quasi concave) trên A nếu − f tựa lồi. Định nghĩa 1.12 Các hàm λf, f + g và max (f, g) được định nghĩa như sau:
Định nghĩa hàm lồi được thể hiện qua các công thức: (λf) := λf(x), (f + g)(x) := f(x) + g(x), và max(f, g) := max{f(x), g(x)} Theo Định lý 1.2, nếu f là hàm lồi trên tập lồi A và g là hàm lồi trên tập lồi B, thì trên giao của hai tập A ∩ B, các hàm λf + βg (với λ, β > 0) và max(f, g) cũng là hàm lồi Định lý 1.3 khẳng định rằng một hàm lồi xác định trên tập lồi A sẽ liên tục tại mọi điểm trong tập đó.
• Chú ý: Hàm lồi xác định trên tập lồi thì liên tục tại mọi điểm trong, chưa chắc liên tục trên điểm biên.
• Kí hiệu: f ′ (a) hoặc ∇ f (a) là đạo hàm của f tại a. Định lý 1.4.
1 Cho f : A →R là một hàm khả vi trên tập lồi mở A Điều kiện cần và đủ để f lồi trên A là: f (x) + h∇ f (x) , y − x i6f (y) , ∀ x, y ∈ A.
2 Nếu f khả vi hai lần thì f lồi trên A khi và chỉ khi ∀ x ∈ A ma trận Hesse H (x) của f tại x xác định không âm, tức là: y T H (x) y> 0, ∀ x ∈ A, y ∈R n
Tính khả vi của hàm lồi là yếu tố quan trọng trong tối ưu hóa Đạo hàm theo hướng d của hàm số f tại điểm x được định nghĩa là: f ′ (x, d) := lim λ →0 + f (x + λd) − f (x) λ, nếu giới hạn tồn tại Định lý cho biết rằng nếu f là hàm lồi trên tập A, thì với mọi x ∈ A và mọi d ∈ R^n sao cho x + d ∈ A, đạo hàm theo hướng d của f tại x luôn tồn tại và thỏa mãn f ′ (x, d) ≤ f (x + d) − f (x) Hơn nữa, với mỗi x cố định, f ′ (x, ) là một hàm lồi trên tập lồi { d : x + d ∈ A }.
Từ định lí trên ta rút ra được nhận xét:
• Hàm lồi chưa chắc khả vi tại mọi điểm. Định nghĩa 1.14 Cho f là một hàm lồi trên tập lồi A Một vector y ∗ ∈R n được gọi là dưới vi phân tại x ∗ ∈ A nếu f(x)> f (x ∗ ) + h y ∗ , x − x ∗ i , ∀ x ∈ A
Tập các điểm y ∗ thỏa mãn bất đẳng thức này được kí hiệu ∂f(x ∗ ).
Trường hợp ∂f(x ∗ ) chỉ có một điểm ta nói f khả vi tại x ∗
1 Tương tự trường hợp hàm một biến, bất đẳng thức f(x)> f(x ∗ ) + h y ∗ , x − x ∗ i , ∀ x ∈ A, có nghĩa rằng siêu phẳng đi qua điểm (x ∗ , f (x ∗ )) nằm dưới đồ thị hàm số.
2 Tập ∂f(x ∗ ) có thể rỗng, tuy nhiên với hàm lồi thì khác rỗng. Định lý 1.6 Cho f là hàm lồi (hữu hạn) trên tập lồi A Khi đó f có dưới vi phân tại mọi điểm trong tương đối riA
Tính chất cực trị
Cho D ⊂ R^n, với D khác rỗng và hàm số f : D → R (không nhất thiết phải lồi) Một điểm x∗ ∈ D được gọi là cực tiểu địa phương của f trên D nếu tồn tại một lân cận mở U của x∗ sao cho f(x∗) ≤ f(x) với mọi x ∈ D ∩ U Nếu f(x∗) ≤ f(x) với mọi x ∈ D, thì x∗ được gọi là cực tiểu tuyệt đối (toàn cục) của f trên D.
Hai tính chất cơ bản về cực trị của hàm lồi bao gồm: Định lý 1.7 khẳng định rằng mọi điểm cực tiểu địa phương của hàm lồi trên tập lồi đều là điểm cực tiểu tuyệt đối, và nếu x∗ là điểm cực tiểu trong tập lồi D với x∗ ∈ intD, thì 0 ∈ ∂f(x∗) Định lý 1.8 chỉ ra rằng cực đại của hàm lồi, nếu có, trên tập lồi sẽ đạt tại một điểm cực biên Theo Định lý 1.9 (Định lý Weierstrass), một hàm liên tục f trên D compact, khác rỗng, sẽ đạt cực tiểu và cực đại trên D Cuối cùng, Định lý 1.10 cho biết nếu x ∈ Rn là điểm cực tiểu địa phương của hàm f(x) khả vi trên Rn, thì ∇²f(x) < 0, tức là ma trận ∇²f(x) nửa xác định dương.
Ngược lại, nếu x ∈R n là một điểm tại đó f(x) hai lần khả vi và
∇ f (x) = 0, ∇ 2 f (x)f (x) , ∀ x ∈ D được gọi là nghiệm tối ưu toàn cục.
7 Nếu D = X (X là một không gian nào đó) thì bài toán tối ưu trên được gọi là bài toán tối ưu không ràng buộc, ngược lại gọi là bài toán tối ưu ràng buộc. Để tổng quát, nhiều khi người ta còn thay inf cho min vàsup cho max.
Những nguyên lí cơ bản của các phương pháp tối ưu
Điều kiện tối ưu
Một vector d khác không được gọi là hướng chấp nhận được của tập D tại điểm x ∗ nếu tồn tại một số thực λ > 0 sao cho x ∗ + λd thuộc D với mọi 0 < λ ≤ λ Tập hợp các hướng chấp nhận được tại x ∗ được ký hiệu là D(x ∗ ) và bao đóng của nó là D(x ∗ ) Theo định lý 1.11, nếu hàm f khả vi trong một tập mở chứa D và x ∗ là cực tiểu địa phương trên D, thì điều kiện d T ∇ f (x ∗ ) > 0 sẽ đúng với mọi vector d thuộc D(x ∗ ) Ngoài ra, một vector x ∗ thuộc D được gọi là điểm dừng của hàm f trên D nếu d T ∇ f (x ∗ ) > 0 với mọi d thuộc D(x ∗ ).
2 Từ Định lí 1.10 nếu x ∗ là cực tiểu địa phương thì x ∗ là điểm dừng Tuy nhiên điều ngược lại không đúng Ví dụ:0 là điểm dừng của f(x) = x 3 nhưng nó không phải là cực tiểu trên đoạn [a; b] chứa điểm0 nào Tuy vậy, với quy hoạch lồi điểm dừng chính là điểm cực tiểu. Định lý 1.12 Giả sử D là một tập lồi, f là một hàm lồi khả vi trên tập mở chứa D. Lúc đó, điều kiện cần và đủ cho x ∗ làm hàm f đạt cực tiểu trên D là x ∗ là điểm dừng của f trên D.
Để đảm bảo bài toán có nghiệm tối ưu, chúng ta cần xem xét một số điều kiện mở rộng Hàm f : D → R được gọi là nửa liên tục dưới tại điểm x ∈ D nếu với mỗi ǫ > 0 tồn tại một δ > 0 sao cho f(x - ǫ) ≤ f(x) với mọi x ∈ D, |x - x| < δ Hàm f được coi là nửa liên tục trên D khi nó nửa liên tục dưới trên D Nếu hàm f vừa nửa liên tục dưới vừa nửa liên tục trên D, thì nó được gọi là liên tục trên D Theo định lý 1.13, một hàm f(x) nửa liên tục dưới trên tập compact D (D ≠ ∅) phải đạt cực tiểu trên D Tương tự, một hàm f(x) nửa liên tục trên cũng có tính chất này trên tập compact.
D 6 = ∅ phải đạt cực đại trên D.
Nếu tập D là một tập đóng và không rỗng, thì một hàm nửa liên tục dưới f: D → R sẽ có cực tiểu trên D nếu f bị chặn trên D và f(x) tiến tới +∞ khi x thuộc D Tương tự, một hàm nửa liên tục trên f: D → R sẽ có cực đại trên D nếu -f bị chặn trên D và f(x) tiến tới -∞ khi x thuộc D.
Đối ngẫu Lagrange
Trong bài viết này, chúng ta sẽ khám phá phương pháp nhân tử Lagrange để xác định điểm cực trị trong các bài toán tối ưu có ràng buộc đẳng thức, được trình bày dưới dạng hàm Lagrange Định nghĩa 1.19 nêu rõ rằng chúng ta sẽ xem xét bài toán tối thiểu hóa hàm f₀(x) với điều kiện rằng x thuộc tập D.
Định lý 1.15, hay còn gọi là quy tắc nhân tử Lagrange, khẳng định rằng nếu hàm f i, với i = 0, , m, khả vi liên tục trong lân cận V ⊂ R n của x ∗, và x ∗ là nghiệm cực tiểu địa phương của bài toán, thì tồn tại các nhân tử Lagrange λ i > 0, với i = 0, 1, , m Các nhân tử này không cùng triệt tiêu và thỏa mãn các điều kiện cần thiết.
Nếu f 1 ′ (x ∗ ), f 2 ′ (x ∗ ), , f m ′ (x ∗ ) độc lập tuyến tính thì λ 0 6 = 0 và có thể chọn bằng 1. Đề hiểu rõ hơn định lí trên ta xét ví dụ sau:
Ví dụ: Cho hai số thực x, y thỏa mãn điều kiện x + y = 10 Tìm giá trị nhỏ nhất của biểu thức: f (x; y) = x 2 + y 2 Giải:
Bước 1: Thiết lập bài toán cực tiểu đối với hàm f (x; y) = x 2 + y 2 thỏa mãn điều kiện φ(x; y) = x + y − 10 = 0.
Bước 2: Thiết lập hàm Lagrange
Bước 3: Tính các đạo hàm riêng của hàm f và cho bằng 0
2 2 = 10 ⇔ λ = − 10. Tìm được điểm dừng có tọa độ (5; 5; − 10).
Phương pháp thiết lập hàm Lagrange là một công cụ quan trọng trong việc tìm cực trị Qua ví dụ đã nêu, chúng ta có thể hiểu rõ hơn về ý tưởng của phương pháp này Bây giờ, chúng ta sẽ trở lại với Bài toán 1 để áp dụng những kiến thức đã học.
Sau khi đã mô hình hóa lại bài toán về dạng giải tích, để giải bài toán ta sẽ đi tìm cực đại của hàm f (x; y) = 4xy với ràng buộc φ(x; y) = 0.
Vì là hàm hai biến x; y nên ta thiết lập hàm Lagrange như sau:
L(x; y; λ) = 4xy + λ(x 2 + y 2 − r 2 ) thỏa mãn điều kiện φ(x; y) = 0.
Khi đó điểm cực trị của hàm số sẽ là nghiệm của hệ phương trình:
Giải hệ phương trình trên ta được nghiệm x = y = r
√ 2. Vậy hình chữ nhật có diện tích lớn nhất cần tìm ở đây chính là hình vuông có cạnh bằng √ r
2 với r là bán kính cho trước của hình tròn.
Từ đây về sau ta có thể sử dụng phương pháp nhân tử Lagrange để giải các bài toán tối ưu với ràng buộc đẳng thức.
Áp dụng phương pháp tối ưu giải các bài toán cực trị hình học phổ thông 21 2.1 Áp dụng trong hình học phẳng
Một số bài toán cực trị về khoảng cách
Bài toán 2.1 (Bài toán Steiner) Tìm trong mặt phẳng một điểm sao cho tổng khoảng cách từ điểm đó tới ba điểm khác nhau đã cho là nhỏ nhất?
Gọi 3 điểm đã cho có dạng: x 1 = (x 1 1 , x 1 2 ), x 2 = (x 2 1 , x 2 2 ), x 3 = (x 3 1 , x 3 2 ), ∈ R 2 và cho điểm tối ưu cần tìm là x = (x 1 , x 2 ) ∈ R 2 Khi đó tổng khoảng cách từ điểm cần tìm tới 3 điểm đã cho là: k x − x 1 k + k x − x 2 k + k x − x 3 k Lúc này ta sẽ giải tích hóa lại bài toán dưới dạng như sau: min f (x) = k x − x 1 k + k x − x 2 k + k x − x 3 k
Bài toán tối ưu lồi không ràng buộc được xác định bởi hàm mục tiêu f(x) liên tục và bức trên R2, đảm bảo tồn tại nghiệm cực tiểu tại x = (x1, x2) Điều kiện tối ưu trong trường hợp này là 0 thuộc ∂f(x).
Ta chia bài toán trên thành hai trường hợp như sau:
1 Điểm cần tìm x không trùng với ba điểm đã cho: x 6 = x i , i = 1, 2, 3.
2 Điểm cần tìm x trùng với một trong ba điểm đã cho: x ∈ { x 1 , x 2 , x 3 }.
Với trường hợp 1, từ điều kiện tối ưu ta có:
Để đảm bảo đẳng thức ∂f (x) = 0 được thỏa mãn, cần chọn ba vector đơn vị từ điểm x tới các điểm x1, x2, x3 sao cho tổng của chúng bằng vector 0 Điều này dẫn đến việc từ điểm x, các đoạn thẳng x1, x2, x2, x3 và x1, x3 phải tạo với nhau một góc 120 độ Nếu góc lớn nhất của tam giác có ba đỉnh x1, x2, x3 không vượt quá 120 độ, có thể xác định điểm x thông qua phương pháp hình học.
1 Cho tam giác ABC dựng các tam giác đều ABO, BCN, ACM bên ngoài tam giác ABC.
Dựng các đường tròn ngoại tiếp các tam giác đều ABO, BCN, ACM, ba đường tròn này cắt nhau tại một điểm T Điểm T là điểm có tổng khoảng cách đến ba điểm A, B, C ngắn nhất, được gọi là điểm Torricelli Trong trường hợp 2, giả sử x = x1, từ điều kiện tối ưu ta có.
Đạo hàm của hàm số f(x) được biểu diễn bởi phương trình ∂f(x) = p + x − x² k x − x² k + x − x³ k x − x³ k = 0, trong đó p thuộc ∂ | x | tại điểm x = 0, tức là | p | < 1 Khi đó, tổng của hai vector đơn vị từ x₁ tới x₂ và từ x₁ tới x₃ với vector thứ ba có chuẩn nhỏ hơn 1 bằng vector 0 Điều này dẫn đến kết quả x₂ x₁ x₃ ≤ 120°.
Nếu các góc của tam giác được tạo bởi ba điểm x1, x2 và x3 đều nhỏ hơn 120 độ, nghiệm tối ưu của bài toán sẽ là điểm Torricelli Ngược lại, nếu tam giác có một góc lớn hơn 120 độ, thì điểm tối ưu sẽ nằm tại đỉnh của góc lớn đó.
Hình 2.1 hơn hoặc bằng120 o thì nghiệm tối ưu là một trong ba đỉnh của tam giác.
Bài toán 2.2, hay còn gọi là bài toán Steiner mở rộng, yêu cầu tìm một điểm trong mặt phẳng sao cho tổng khoảng cách có trọng số dương từ điểm đó đến ba điểm đã cho là nhỏ nhất.
Trong bài toán này, các yếu tố được định nghĩa tương tự như bài toán trước, với x 1 = (x 1 1 , x 1 2 ), x 2 = (x 2 1 , x 2 2 ), x 3 = (x 3 1 , x 3 2 ) thuộc R 2 Điểm tối ưu cần tìm là x = (x 1 , x 2 ) thuộc R, với trọng số m i > 0 cho i = 1, 3 Bài toán được tối ưu hóa với hàm mục tiêu là min f(x) = m 1 k x − x 1 k + m 2 k x − x 2 k + m 3 k x − x 3 k Điều kiện và phương pháp giải của bài toán này tương tự như bài toán trước, với nghiệm cực tiểu x thuộc một trong các điểm dừng 0 ∈ ∂f (x).
Giả sử có một tam giác với ba cạnh có độ dài m1, m2 và m3 Góc αij là góc giữa hai cạnh mi và mj, với i, j thuộc {1, 2, 3} Chúng ta vẽ các cung tròn từ hai điểm xi và xj tạo thành một góc π - αij tương ứng.
Nếu các cung tròn này cắt nhau tại một điểm bên trong tam giác thì giao điểm đó chính là nghiệm tối ưu cần tìm.
Nếu các cung tròn cắt nhau bên ngoài tam giác hoặc không có tam giác với độ dài các cạnh m1, m2 và m3, thì nghiệm tối ưu của bài toán sẽ trùng với một trong các đỉnh của tam giác, tức là x ∈ {x1, x2, x3}.
Bài toán 2.3 yêu cầu tìm một điểm trên hình tròn đơn vị, có tâm tại gốc tọa độ và bán kính 1, sao cho tổng khoảng cách từ điểm đó đến hai điểm nằm ngoài hình tròn là nhỏ nhất.
Bài toán có thể được chuyển đổi thành dạng giải tích với mục tiêu tối thiểu hóa hàm f 0 (x) = k x − y k + k x − z k, với điều kiện f 1 (x) = k x k − 1 < 0, trong đó | y | > 1 và | z | > 1 là hai điểm cố định Đây là bài toán cực tiểu của một hàm liên tục trên tập compact với ràng buộc bất đẳng thức, do đó, nghiệm luôn tồn tại.
Vì điều kiện Slater thỏa mãn (f 1 (0) < − 1 < 0) nên ta sử định lí Kuhn-Tucker với λ 0 = 1 Lúc đó tồn tại λ 1> 0 sao cho
Ta biết rằng dưới vi phân của chuẩn trong không gian Euclid là véc-tơ đơn vị từ
0 hướng tới điểm ấy Vì vậy, khi k x ∗ k = 1 ta có: x ∗ − y k x ∗ − y k + x ∗ − z k x ∗ − z k + λ 1 x ∗ = 0. Điều này có nghĩa là góc giữa hai đoạn [0, x ∗ ] và [y, x ∗ ] bằng góc giữa hai đoạn
[0, x ∗ ] và [z, x ∗ ] Như vậy ta được ba phương trình với ba ẩn số, do đó có thể giải đề tìmx ∗
Trong trường hợp k x ∗ k < 1, điều kiện bù kéo theo λ 1 = 0, khi đó x ∗ − y
Điều kiện | x ∗ − z | = 0 cho thấy x ∗ nằm trong đoạn [y, z] Điều này chỉ xảy ra khi đoạn [y, z] cắt đường tròn đơn vị đã cho Khi đó, giao điểm giữa [y, z] và hình tròn đơn vị chính là tập nghiệm tối ưu.
Trong không gian R n, bài toán 2.4 yêu cầu tìm một điểm trên siêu phẳng đã cho, sao cho khoảng cách từ điểm này đến một điểm nằm ngoài siêu phẳng là ngắn nhất.
Thực chất bài toán trên chính là bài toán tìm khoảng cách từ một điểm tới một siêu phẳng cho trước trong không gian R n
Giả sử điểm x ∗ = (x ∗ 1 , x ∗ 2 , , x ∗ n ) ∈R n và một siêu phẳng có dạng :a 1 x 1 + a 2 x 2 + + a n x n = α, với { a 1 , a 2 , , a n } là độc lập tuyến tính và α là một số cho trước.
Ta giải tích hóa lại bài toán như sau: min f(x) = (x 1 − x ∗ 1 ) 2 + + (x n − x ∗ n ) 2 với ràng buộc
H = { a₁x₁ + a₂x₂ + + aₙxₙ = α } là một siêu phẳng trong Rⁿ, do đó H là một tập lồi đóng Kết hợp với hàm f(x) = kx - x*², là một hàm lồi chặt, nghiệm cực tiểu (nếu có) sẽ là duy nhất Chúng ta thiết lập hàm Lagrange để giải quyết bài toán này.
Ta có điều kiện tối ưu của bài toán như sau:
Tiếp theo ta sẽ đi tìm điểm dừng của bài toán dựa vào hai điều kiện tối ưu trên.
Ta nhân hai vế của (1) với a i rồi cộng lại theo mọi i, kết hợp với điều kiện (2) ta được:
Ta tìm được một điểm dừng duy nhất đó là x = (x 1 ; x 2 ; ; x n ), với mỗi x i = x ∗ i − λ
Ta tìm được f min = α − a T x ∗ 2 k a k 2 Vậy khoảng cách từ một điểm x ∗ tới siêu phẳng
H đã cho là: d (x ∗ , H ) = α − a T x ∗ k a k Với n = 2 hoặc n = 3 ta sẽ nhận được các công thức tính khoảng cách rất quen thuộc trong chương trình hình học phổ thông.
Chẳng hạn, với n = 2, x ∗ = (1, 2) T , a = (6; 8) T , α = 32, ta được a T x ∗ = 22, k a k = 10. Suy ra α − a T x 0 = 10, d = 1 Điểm trên đường thẳng gần x ∗ nhất là x = ( 8
5 ), hay nói cách khác hình chiếu của điểm x ∗ (1; 2) xuống đường thẳng 6x 1 + 8x 2 = 32 là điểm x = ( 8
Một số bài toán cực trị về chu vi và diện tích
Bài toán 2.5 yêu cầu tính độ dài đoạn DE trong hình vuông ABCD có cạnh a, với các điểm E, F, G, H được xác định trên các cạnh CD, DA, AB, BC sao cho AF = BG = CH = DE Mục tiêu là tìm giá trị của DE sao cho tứ giác EF GH có chu vi nhỏ nhất.
Ta thấy HE = EF = F G = GH nên tứ giác EF GH là hình vuông, từ đó chu vi
EF GH nhỏ nhất khi một trong bốn cạnh là nhỏ nhất Ở đây ta chọn cạnh EF. Đặt DE = x thì DF = a − x, áp dụng định lí Pythagoras ta tính được:
Ta có thể hình thức hóa lại bài toán như sau:
Hình 2.3 min P (x) = 2x 2 − 2ax + a 2 , với ràng buộc bất đẳng thức 0 < x < a
Gọi x là nghiệm tối ưu cần tìm, ta có x 6 = 0, x 6 = a và hàm P (x) > 0, ∀ x ∈ (0; a) Ta thấy hàm S là liên tục và miền tìm nghiệm là một tập compact nên x tồn tại.
Theo điều kiện của hàm liên tục, khả vi và xác định dương nên theo điều kiện tối ưu:
Điểm E là trung điểm của đoạn thẳng CD Bài toán Fermat (Bài toán 2.6) yêu cầu tìm tam giác vuông có diện tích lớn nhất với tổng độ dài hai cạnh góc vuông bằng một số a > 0 cho trước Năm 1638, Fermat đã sử dụng bài toán này để minh họa phương pháp tìm cực tiểu, thể hiện tầm quan trọng của định lý Fermat trong toán học.
Nếu xem độ dài một cạnh góc vuông là x, thì cạnh còn lại sẽ có độ dài a − x (với điều kiện 0 < x < a) Diện tích của tam giác sẽ được xác định là một hàm phụ thuộc vào giá trị của x.
2 (a − x)x, và bài toán cực trị đặt ra có dạng: max S(x) = 1
2 (a − x)x với ràng buộc bất đẳng thức 0 < x < a.
Giả sử x là nghiệm tối ưu cần tìm, hiển nhiên x 6 = 0 , x 6 = a và hàm S(x) > 0, ∀ x ∈ (0; a).
Ta thấy hàm S là liên tục và miền tìm nghiệm là một tập compact nênx tồn tại.
Theo điều kiện của hàm liên tục, khả vi và xác định dương nên theo điều kiện tối ưu S ′ (x) = 0 ⇒ 1
2. Ở đây bài toán chỉ có một điểm dừng là x = a
2 và bài toán luôn có nghiệm nên nghiệm cực đại của nó sẽ là x = a
2. Vậy tam giác cần tìm thỏa mãn đề bài chính là tam giác vuông cân có độ dài cạnh góc vuông là a
2. Bài toán 2.7 Trong các tam giác nội tiếp trong một đường tròn cho trước, hãy tìm tam giác có diện tích lớn nhất.
Trong bài viết này, chúng ta sẽ xem xét tam giác ABC nội tiếp trong một đường tròn đơn vị Để bắt đầu, hãy chọn điểm A cố định nằm trên đường tròn đơn vị với tọa độ xác định.
−→ AB = (x 1 − 1, y 1 ), −→ AC = (x 2 − 1, y 2 ) Ta tính được diện tích của tam giác ABC theo công thức
2 | (x 1 − 1) y 2 − y 1 (x 2 − 1) | , công thức trên có thể coi là một hàm với bốn ẩn
Ta giải tích hóa lại bài toán trên dưới dạng như sau: max S (x 1 , x 2 , y 1 , y 2 ) với ràng buộc x 2 1 + y 2 2 = 1, x 2 2 + y 2 2 = 1.
Bài toán cực trị với bốn biến có thể được đơn giản hóa bằng cách sử dụng lượng giác để chuyển đổi về hai biến Cụ thể, ta đặt x1 = cos α, y1 = sin α, x2 = cos β, y2 = sin β Nhờ đó, bài toán cực trị ban đầu sẽ được biến đổi thành bài toán cực trị tối đa của hàm f(α, β), với f(α, β) = sin α − sin β + sin(β − α).
Giữ α cố định, ta coi α là một hằng số, lúc đó ∂f
Từ đây ta tìm được điểm dừng β = α
Với k là số chẵn thì cos kπ = 1, ta được f 1 (α) = sin α + 2 sin α
2 Với k là số lẻ thì cos kπ = − 1, ta được f 2 (α) = sin α − 2 sin α
2 Giải bài toán trên ta tìm được f max (α, β) = 3 √
2 , với α có thể chọn bằng 2π
3 Lúc này tam giác cần tìm chính là tam giác đều.
Vậy trong các tam giác nội tiếp một đường tròn cho trước thì tam giác đều là tam giác có diện tích lớn nhất.
Bài toán 2.8 Trong các hình chữ nhật nội tiếp trong một Ellipse cho trước, tìm hình chữ nhật có diện tích lớn nhất.
Giả sử có một Ellipse với phương trình x²/a² + y²/b² = 1 Khi xét một điểm (x; y) nằm trong Ellipse và thuộc góc phần tư thứ nhất, diện tích hình chữ nhật tương ứng được xác định bởi hàm f(x; y) = 4xy.
Từ đó ta có bài toán tối ưu hai biến sau max f(x; y) = 4xy với điều kiện x 2 a 2 + y 2 a 2 = 1.
Ta thiết lập hàm Lagrange
Tìm điểm dừng thông qua việc giải hệ phương trình
√ 2 λ = − 2ab Để biết được nghiệm tối ưu
√ 2 là cực đại hay cực tiểu, ta thực hiện đạo hàm cấp hai với hàm Lagrange ở trên, xéth = (h 1 , h 2 ) ∈R 2 :
Thay h = (h 1 , h 2 ) để kiểm tra, ta được
Vậy hình chữ nhật nội tiếp trong một Ellipse cho trước có diện tích lớn nhất bằng
2.1.3 Một số bài toán cực trị về góc
Bài toán 2.9 yêu cầu vẽ một đoạn thẳng qua một điểm nằm trong một góc, sao cho hai đầu mút của đoạn thẳng này nằm trên hai cạnh của góc Mục tiêu là tạo ra một tam giác có diện tích nhỏ nhất có thể.
Gọi M là một điểm cho trước nằm trong góc AOB, điểm C, D nằm trên tia OA,
OB tương ứng và M thuộc đoạn CD Qua M vẽ đường thẳng song song với OA Gọi
F là giao điểm của đường song song này với OB Đặt OF = a, F D = x (x> 0)
Ta thấy hai tam giác OCD và F M D đồng dạng và có có tỉ số đồng dạng a + x x
Ta biết rằng tỉ số diện tích của hai tam giác đồng dạng thì bằng bình phương tỉ số đồng dạng Suy ra [OCD]
Vì S(x) là một hàm liên lục và S(x) → + ∞ khi x → 0 nên S(x) phải đạt cực tiểu trên miền x> 0 Gọi x là nghiệm cực tiểu cần tìm.
Theo điều kiện tối ưu S ′ (x) = 0, từ đó tìm được x = a Chỉ có 1 điểm dừng duy nhất nên x chính là nghiệm cực tiểu cần tìm.
Vậy đường thẳng cần dựng phải thỏa mãn điều kiện: điểm đã cho chia đôi đoạn thẳng giữa hai cạnh của góc ban đầu, tức là: OD = 2OF.
Chúng ta sẽ chứng minh lại định luật khúc xạ ánh sáng, hay còn gọi là định luật Snell, bằng phương pháp tối ưu Định luật Snell phát biểu rằng, đối với hai môi trường và một sóng có tần số duy nhất, tỉ lệ giữa sin của góc tới φ1 và góc khúc xạ φ2 tương ứng với tỷ số vận tốc pha v1 và v2 trong hai môi trường, hoặc tương đương với chiết suất tương đối n2/n1 của hai môi trường này.
Bài toán 2.10 đề cập đến một tia tới xuất phát từ điểm P1 (x1, y1) với vận tốc không đổi v1 trong môi trường có chiết suất n1 Tia khúc xạ sẽ di chuyển với vận tốc không đổi v2 tới một điểm mới.
P 2 (x 2 , y 2 ) trong môi trường có chiết suất n 2 Chứng minh sin φ 1 sin φ 2
Lời giải: Để dễ dàng cho việc hình dung ta có hình vẽ sau:
Hình 2.6: Minh họa định luật khúc xạ ánh sáng
Từ hình vẽ ta nhận thấy thời gian đi từ P 1 tới P 2 của tia sáng sẽ là một hàm phụ thuộc vào φ 1 và φ 2
Ta còn có thêm điều kiện x 1 + x 2 = y 1 tan φ 1 + y 2 tan φ 2 = L, với L là một số cho trước.
Theo nguyên lý Fermat, ánh sáng di chuyển theo đường ngắn nhất, dẫn đến thời gian di chuyển cũng được tối thiểu hóa Bài toán có thể được biểu diễn dưới dạng tối ưu hóa: min T (φ 1 , φ 2 ) với các ràng buộc x 1 + x 2 = y 1 tan φ 1 + y 2 tan φ 2 = L, trong đó L là một hằng số đã cho.
Ta thiết lập hàm Lagrange như sau:
L = (φ 1 , φ 2 , λ) = y 1 v 1 cos φ 1 + y 2 v 2 cos φ 2 + λ (L − y 1 tan φ 1 − y 2 tan φ 2 ) Để tìm điểm dừng ta đi giải hệ phương trình
Ta đi giải (1), vì y 1, v 1 đều khác 0, φ 1 là góc tới và 0 o < φ 1 < 90 o nên sin φ 1 6 = 0, suy ra
(1) ⇔ sin φ 1 = λv 1 Giải tương tự đối với phương trình (2) ta được
Vậy ta được điều phải chứng minh sin φ 1 sin φ 2
Từ định luật trên ta có thể giải quyết 1 bài toán vật lý sau:
Giả sử rằng có 1 người ở A cách bờ sông muốn tớiB ở bờ bên kia như hình vẽ 2.7.
Người đó tới B nhanh nhất khi và chỉ khi người đó chạy theo đường AOB thỏa mãn sin φ 1 sin φ 2 = v 1
Áp dụng trong hình học không gian
2.2.1 Một số bài toán cực trị về thể tích khối chóp
Bài toán 2.11 Cho hình chóp S.ABCD có đáy là hình vuông cạnh a, cạnh bên
SA = h và SA ⊥ (ABCD), M là điểm di động trên cạnh CD, đặt CM = x Xác định
Hình 2.7 vị trí của M để thể tích tứ diện SABH đạt giá trị lớn nhất và tính giá trị lớn nhất ấy.
Kẻ SH ⊥ BM, lại có BM ⊥ SA, nên M B ⊥ (SAH) suy ra M B ⊥ AH.
Vì ABH [ = BM C \, nên sin ABH [ = sin BM C \
√ a 2 + x 2 Dùng định lí Phythagoras ta cũng tính được
Từ đó ta tính được thể tích của tứ diện SABH
Ta thấy thể tích tứ diện là một hàm theo một ẩn x Như vậy ta có thể hình thức hóa lại bài toán dưới dạng như sau max V (x) = 1
6 a 3 h a 2 + x 2 , với ràng buộc bất đẳng thức 06x6a.
Theo điều kiện của hàm liên tục, khả vi và xác định dương nên theo điều kiện tối
V ′ (x) = 0 ⇒ x = a, tức là điểm M trùng với a.
Trong bài toán 2.12, chúng ta xem xét hình chóp S.ABCD với đáy ABCD là hình vuông có cạnh dài a Cạnh SA vuông góc với đáy và có độ dài y, trong khi điểm M nằm trên cạnh AD với AM = x Điều kiện cần thiết là x² + y² = a² Mục tiêu là tìm giá trị lớn nhất của thể tích khối chóp S.ABCM.
Nếu giải theo phương pháp hình học thuần túy ta sẽ giải như sau: Độ dài đoạn M D = a − x, từ đó suy ra diện tích tứ giác AM CB là:
Khi đó thể tích khối chóp SABCM sẽ là:
Khi đánh giá biểu thức, việc áp dụng bất đẳng thức AM-GM có thể gặp khó khăn do cần cân bằng hệ số Do đó, chúng ta sẽ thiết lập lại bài toán với hàm số f: R² → R.
L = max f(x, y) x 2 + y 2 = a 2 (a = const) x> 0, y > 0 Đây là một bài toán tối ưu với ràng buộc đẳng thức nên ta thiết lập một hàm Lagrange như sau:
Khi đó điểm cực trị của hàm số sẽ là nghiệm của hệ phương trình
Ta tìm được nghiệm tối ưu của bài toán trên là V max = a 3 √
8 2.2.2 Một số bài toán cực trị về thể tích hình lăng trụ và hình nón
Bài toán 2.13 Tìm thể tích lớn nhất có thể của một hình hộp chữ nhật không có nắp có diện tích xung quanh không đổi là 27m 2
Gọi x, y, z lần lượt là chiều dài, chiều rộng và chiều cao của hình hộp Khi đó thể tích hình hộp là:
Diện tích xung quanh của hình hộp sẽ là: xy + 2yz + 2xz = 27.
Chúng ta sẽ chuyển đổi bài toán thành một bài toán tối ưu với mục tiêu tối đa hóa V(x, y, z) dưới ràng buộc G(x, y, z) = xy + 2yz + 2xz − 27 = 0 Do ràng buộc là một đẳng thức, phương pháp nhân tử Lagrange sẽ được áp dụng để giải quyết bài toán này.
Ta thiết lập hàm Lagrange: L(x, y, z) = xyz + λ(xy + 2yz + 2xz − 27).
Giải hệ gồm các phương trình:
∂z = 0; xy + 2yz + 2xz = 27. Suy ra yz + λ(y + 2z) = 0; (2.1) xz + λ(x + 2z) = 0; (2.2) xy + λ(2y + 2x) = 0; (2.3) xy + 2yz + 2xz = 27 (2.4)
Nhân cả hai vế của các phương trình (2.1), (2.2) và (2.3) với x, y, z tương ứng, ta thu được các phương trình xyz = − λ(xy + 2xz), xyz = − λ(xy + 2yz) và xyz = − λ(2yz + 2xz) Cần lưu ý rằng λ phải khác 0, nếu không sẽ dẫn đến xy = yz = xz, điều này không thỏa mãn phương trình (2.4) Từ (2.1) và (2.2), ta suy ra xz = yz, và vì z không thể bằng 0 nên x = y Từ (2.2) và (2.3), ta có y = 2z Thay x = y = 2z theo biến z, ta được kết quả mong muốn.
Vậy thể tích lớn nhất đạt được là V = 13.5m 3
Bài toán 2.14, còn được biết đến là bài toán Kepler, đặt ra thách thức tìm kiếm hình trụ có thể tích lớn nhất nằm trong hình cầu đơn vị Bài toán này được Kepler nêu ra và giải quyết bằng phương pháp hình học trong tác phẩm "Hình học không gian các thùng rượu vang" xuất bản năm 1615.
Chiều cao của hình trụ được ký hiệu là \(h\) với điều kiện \(0 < h < 2\), và bán kính mặt đáy là \(r\) Hình trụ này nội tiếp trong một hình cầu đơn vị, do đó có mối quan hệ \(r^2 + h^2 = 1\).
4 Từ đó suy ra thể tích hình trụ là hàm một biến V (h) = πh
. Bài toán trên được viết lại dưới dạng giải tích như sau:
Ta thấy V (h)là một hàm liên tục, khả vi và xác định dương, miền tìm nghiệm là một tập compact nên theo điều kiện tối ưu ta có:
Ta tìm được một điểm dừng h = 2
Do V (h) là hàm lõm trên miền [0; 2] nên điểm dừng duy nhất cũng là điểm cực đại Lúc đó hình trụ có thể tích lớn nhất cần tìmV max = 4π
3 với chiều cao tương ứng h = 2
Bài toán 2.15 (Bài toán Archimedes) Trong số các chỏm cầu có diện tích mặt bên cho trước, hãy tìm chỏm cầu có thể tích lớn nhất?
Từ hình vẽ trên ta ta tính được thể tích của chỏm cầu theo h và r
Diện tích mặt bên của chỏm cầu được tính bằng công thức A = 2πrh, trong đó h là chiều cao chỏm cầu và r là bán kính hình cầu Để biểu diễn diện tích A chỉ theo h, cần khử r khỏi phương trình.
Theo điều kiện tối ưu: ∇ V (h) = 0, ta tìm được điểm dừng h = rA 2π.
Vì V (h) là một hàm liên tục trên miền biến thiên của h là một tập đóng hữu hạn nên theo định lý Weierstrass tồn tại nghiệm cực đại.
Tại hai giá trị biên, ta có V (0) = 0 và V rA 2π
3 √ 2π, dẫn đếnh 6 = 0 và h 6 = rA π nên nghiệm của bài toán sẽ không đạt tại biên.
Từ đó suy ra diện tích mặt bên lúc này A = 2πh 2 , suy ra h = r.
Vậy chỏm cầu có thể tích lớn nhất cần tìm là bán cầu hay là một nửa hình cầu.
Bài toán 2.16 yêu cầu tìm bán kính của một hình quạt cắt từ miếng tôn hình tròn bán kính r để tạo ra một hình nón có thể tích lớn nhất Khi cắt hình quạt và gấp phần còn lại, cần xác định kích thước tối ưu của cung tròn để tối đa hóa thể tích hình nón Nghiên cứu này giúp hiểu rõ hơn về mối quan hệ giữa hình học và tối ưu hóa trong thiết kế hình nón từ vật liệu hình tròn.
Vì độ dài của đường tròn đáy hình nón bằng độ dài cung AB của quạt tròn dùng làm phễu nên ta có:
Từ đó ta tính được thể tích hình nón theo công thức
Xét bài toán max V (x), với ràng buộc bất đẳng thức 0 < x < 2π. Hàm V (x) là một hàm khả vi liên tục, V (x) > 0, ∀ x ∈ (0; 2π) và V (x) → 0 khi x → + ∞, x → 0.
Giả sử x là nghiệm cần tìm Theo điều kiện tối ưu V ′ (x) = 0 ta tìm được điểm dừng x = 2 √
Vậy độ dài cung tròn cần cắt để thể tích hình nón lớn nhất đó là 2 √ 6π
Áp dụng thuật toán tối ưu giải bài toán tìm đường đi ngắn nhất trên mạng giao thông
Trong bài viết này, chúng tôi sẽ giới thiệu về bài toán tìm đường đi ngắn nhất, bài toán quy hoạch tuyến tính và bài toán quy hoạch tuyến tính nguyên Đồng thời, chúng tôi cũng sẽ hướng dẫn cách giải các bài toán này bằng phần mềm Matlab.
Bài toán người bán hàng (TSP) yêu cầu tìm chu trình ngắn nhất để thăm tất cả các thành phố trong danh sách một lần duy nhất, dựa trên khoảng cách giữa các thành phố đã cho.
Bài toán 2.18 đặt ra vấn đề về thị trấn Konisberg, nơi được chia thành 4 khu vực bởi dòng sông Pregel và kết nối bằng 7 cây cầu Câu hỏi đặt ra là liệu có thể đi qua 7 cây cầu mà không đi qua bất kỳ cây cầu nào quá một lần hay không?
Bài toán 2.19 Giả sử có 4 khu chung cư là K 1, K 2, K 3, K 4 Khu K 1 có dạng hình tròn,
K 1 = { (x, y) ∈R 2 | (x − 1) 2 + (y − 4) 2 6 4 } Khu K 2 có dạng hình tròn,
K 2 = { (x, y) ∈R 2 | (x − 9) 2 + (y − 5) 2 6 1 } Khu K 3 có dạng hình chữ nhật,
K 3 = { (x, y) ∈R 2 | 6 6x6 8, − 2 6y6 2 } Khu K 4 có dạng hình vuông,
Bài toán yêu cầu xác định vị trí xây dựng trạm biến áp tổng để cung cấp điện cho bốn khu chung cư, đồng thời xác định vị trí (x i , y i ) ∈ K i cho trạm biến áp phân phối của mỗi khu K i, với i = 1, 4 Mục tiêu là giảm thiểu tổng chiều dài dây dẫn điện kết nối từ trạm biến áp tổng đến các trạm biến áp phân phối của bốn khu chung cư.
Ta có thể hình dung các bài toán trên được phát biểu dưới dạng tổng quát như sau:
Bài toán tìm đường đi ngắn nhất là việc xác định lộ trình giữa hai đỉnh sao cho tổng trọng số của các cạnh trong lộ trình đó là nhỏ nhất.
Cho một đồ thị vô hướng G và hàm trọng số thực f : E → R, bài toán đặt ra là tìm đường đi ngắn nhất từ đỉnh V đến đỉnh V′.
Thuật toán Dijkstra là một phương pháp hiệu quả để tìm đường đi ngắn nhất từ một nguồn đơn trong đồ thị có trọng số dương Trong thuật toán này, mỗi cạnh được gán một trọng số, có thể hiểu là chi phí, chiều dài hoặc thời gian cần thiết để di chuyển giữa các đỉnh.
Chúng ta có thể mô hình hóa các thành phố bằng các đỉnh của đồ thị và các đường nối giữa chúng bằng các cạnh Trọng số của các cạnh thể hiện độ dài của các con đường, với các trọng số luôn không âm Để vận chuyển từ thành phố s đến thành phố t, thuật toán Dijkstra sẽ chỉ ra lộ trình ngắn nhất mà chúng ta có thể đi.
Thuật toán bắt đầu với giả thiết về đồ thị G = (V, E) và chọn một đỉnh s làm điểm nguồn Mục tiêu của thuật toán là xác định đường đi ngắn nhất từ đỉnh s đến tất cả các đỉnh còn lại trong đồ thị.
Ban đầu, khoảng cách từ đỉnh s đến chính nó được xác định là 0, trong khi khoảng cách từ s đến các đỉnh khác là ∞ Việc này không chỉ giúp đánh dấu các đỉnh chưa được thăm mà còn cho phép thay thế giá trị khi thuật toán tìm ra đường đi ngắn hơn sau này.
Thuật toán này dựa trên giả định rằng nếu đường P1 là đường ngắn nhất từ s đến t và đi qua đỉnh v, thì đoạn đường từ s đến v trên P1 phải là đường ngắn nhất từ s đến v Nếu không, sẽ tồn tại một đường ngắn hơn từ s đến v, từ đó kết hợp với đoạn đường từ v đến t để tạo ra một đường mới P2 từ s đến t, ngắn hơn P1, điều này mâu thuẫn với giả thiết ban đầu.
Giả sử đường ngắn nhất từ s đếnt đi qua v, thì đường s đến v cũng là ngắn nhất.
Để tính toán đường ngắn nhất từ điểm s đến một đỉnh xa, trước tiên cần xác định đường ngắn nhất từ điểm s đến một đỉnh gần hơn.
Trong thuật toán, chúng ta thực hiện một vòng lặp để chọn ra đỉnh gần nhất với đỉnh s mà chúng ta đã biết Từ đỉnh này, chúng ta sẽ tính toán quãng đường từ đỉnh s đến các đỉnh kề với đỉnh đang được xem xét.
Khi bắt đầu thuật toán, ta chọn đỉnh s vì đây là đỉnh gần nhất và khoảng cách từ đỉnh s đến chính nó là 0 Tiếp theo, ta tính toán khoảng cách từ đỉnh s đến các đỉnh kề bằng cách sử dụng độ dài các cạnh nối giữa chúng Sau đó, ta cập nhật quãng đường từ s đến các đỉnh kề và đánh dấu đỉnh s là đã được thăm.
Trong các lần tiếp theo, chúng ta lựa chọn đỉnh v gần nhất với đỉnh s đã biết Từ đỉnh v hiện tại, ta sẽ tính toán đường ngắn nhất từ s đến các đỉnh kề t1, t2, t3, Cụ thể, quãng đường ngắn nhất từ s đến t1 được gọi là P1 Sau đó, ta sẽ xem xét quãng đường P2, được tính bằng tổng quãng đường ngắn nhất từ s đến v và độ dài cạnh (v, t1).
• Nếu tổng P 2 này nhỏ hơn quãng đường P 1 hiện tại, ta cập nhật đường ngắn nhất từ s → v bằng P 2 Lúc này ta đánh dấu đỉnh v là đã thăm.
Giải bài toán quy hoạch tuyến tính hai biến bằng phương pháp hình học
Xét bài toán quy hoạch tuyến tính hai biến min { f(x) = h c, x i| x ∈ D } , trong đó c = (c 1 , c 2 ) T ∈R 2 \ { 0 } vàD ⊂R 2 là tập lồi đa diện.
Như đã biết, qua mỗi điểm x = (x 1 , x 2 ) T ∈ R 2 chỉ có duy nhất một đường mức
L (α, f ) = { x ∈ R 2 | h c, x i = α } của hàm f(x) = h c, x i với mức α = h c, x i Do f (x) là hàm tuyến tính nên gradient ∇ f(x) = c tại mọi x ∈ R 2 và c là vector pháp tuyến của mọi đường mức.
Bài toán được diễn đạt theo ngôn ngữ hình học là: Trong các đường mức giao với tập D, hãy xác định đường mức có giá trị nhỏ nhất.
Thuật toán hình học giải quyết bài toán này dựa trên hai yếu tố chính: Thứ nhất, các đường mức của hàm tuyến tính là song song; thứ hai, giá trị của hàm f(x) = h c, x i sẽ tăng theo hướng của vector gradient ∇ f(x) = c và giảm theo hướng ngược lại với vector c.
Bước 1 Vẽ tập chấp nhận được D, vector c và đường mức
L(0, f ) = { x ∈R 2 | h c, x i = 0 } đi qua điểm gốc 0 và vuông góc với c.
Bước 2 Lấy một điểm bất kì x ∈ D Vẽ đường thẳng L đi qua x và song song các đường mức L (α, f) (Đường thẳng L là đường mức { x ∈R 2 | h c, x i = h c, x i} ).
Để tìm nghiệm tối ưu của bài toán, hãy dịch chuyển song song đường mức L theo hướng ngược với vector c cho đến khi đường mức không còn cắt D nữa Các điểm trên đường mức cuối cùng sẽ là nghiệm tối ưu, trong khi giá trị của đường mức này chính là giá trị tối ưu của bài toán.
Trong bài toán quy hoạch tuyến tính hai biến với dạng max { f(x) = h c, x i| x ∈ D }, trong đó D ⊂ R 2 là tập lồi đa diện không rỗng và c ∈ R 2 \ { 0 }, chúng ta sẽ áp dụng các bước tương tự như thuật toán đã nêu, nhưng cần thay thế Bước 3 bằng Bước 3’ để đạt được kết quả chính xác hơn.
Bước 3: Dịch chuyển song song đường mức L theo hướng vector c cho đến khi không còn cắt đường D nữa Các điểm trên đường mức cuối cùng này là nghiệm tối ưu, trong khi giá trị mức đó chính là giá trị tối ưu của bài toán Để hiểu rõ hơn về thuật toán, hãy xem xét các bài toán sau.
2.4.3 Ví dụ cho thuật toán
Bài toán 2.21 Xét bài toán quy hoạch tuyến tính min f(x) = − 2x 1 + x 2 với điều kiện
Bài toán này có tập chấp nhận là đa diện D = conv { v 1 , , v 4 } với các đỉnh v 1 = (0, 0) T, v 2 = (0, 2), v 3 = (2, 3) T, v 4 = (4, 0) T Hướng của vector c = (−2; 1) T xác định đường mức L 0 và L, đi qua một điểm x ∈ D Theo Thuật toán 3.2, khi dịch chuyển song song đường mức L theo hướng ngược với vector c, đường mức cuối cùng của hàm f cắt tập D tại đỉnh (4, 0) T Do đó, bài toán có nghiệm tối ưu duy nhất tại đỉnh (4, 0) T với giá trị tối ưu f min = −8.
Khi thay đổi hàm mục tiêu của bài toán thành f ′ (x) = x 1 − 2x 2, ta thu được tập nghiệm tối ưu bao gồm cả hai điểm ở cạnh { (0, 2) T , (2, 3) T } Trong trường hợp này, bài toán có vô số nghiệm.
Ta có thể lấy một nghiệm tối ưu đại diện là đỉnh (0, 2) T (Hình b)
Hình 3.3(a) Bài toán có duy nhất nghiệm; 3.3(b)- Bài toán có vô số nghiệm.
Phương pháp này rất hiệu quả trong việc giải quyết các bài toán quy hoạch tuyến tính với hai biến Nhiều bài toán sản xuất có nhiều ràng buộc cũng có thể được giải quyết thông qua phương pháp này.
Trong chương trình toán phổ thông, phương pháp giải bài toán quy hoạch tuyến tính đã được giới thiệu, nhưng phần lý thuyết chưa được trình bày chi tiết Do đó, bài viết này sẽ cung cấp một cái nhìn tổng quát và đầy đủ về phương pháp hình học trong việc giải quyết bài toán quy hoạch tuyến tính.
Ngoài ra đối với bài toán quy hoạch tuyến tính hai biến còn có thể dễ dàng giải được thông qua hàm linprog.m trong Matlab như sau:
Ta nhập các input như sau: ằ f = [ − 2 1]; ằ A = [ − 1 2; 1 1; 1 0]; ằ b = [4 5 4]; ằ lb = [0 0]; ằ ub = [4 inf]; ằ options = optimset( ′ display ′ , ′ of f ′ ); ằ [x f val] = linprog (f, A, b, [], [], lb, ub, [], options)
Ta được kết quả như hình 3.4 dưới đây.
Ta được output làx = (4, 0)và f val = − 8Từ đó kết luận được nghiệm tối ưu cần tìm là đỉnh (4, 0) và giá trị tối ưu là f min = − 8.
Bài toán cắt vật liệu tiết kiệm nhất
Bài toán quy hoạch nguyên (Integer Programming - IP) được định nghĩa là tối thiểu hóa hàm mục tiêu f(x) = f(x1, x2, , xn) với điều kiện x = (x1, , xn) thuộc tập D, trong đó D ⊂ R^n là tập hợp các vector x = (x1, x2, , xn)^T mà một số hoặc tất cả các thành phần của x chỉ nhận giá trị nguyên.
Thông thường, tập D ⊂ R n được xác định bởi một hệ các phương trình và bất phương trình với điều kiện bổ sung về tính nguyên của các biến số: g i (x) = 0, i = 1, m 1 g i (x)6 0 , i = m 1 + 1, , m x j nguyên, j = 1, 2, , n 1
Nếu n1 = n (tất cả các biến đều nguyên), bài toán quy hoạch nguyên được gọi là bài toán quy hoạch nguyên hoàn toàn (Pure Integer Programming) Ngược lại, nếu n1 < n (chỉ có một số biến nguyên), bài toán này được gọi là quy hoạch nguyên bộ phận (Mixed Integer Programming) Khi các hàm f(x) và g_i(x) là tuyến tính, bài toán trở thành quy hoạch tuyến tính nguyên Thuật ngữ “quy hoạch nguyên” chủ yếu được sử dụng trong nghiên cứu các lớp bài toán quy hoạch tuyến tính nguyên.
Quy hoạch nguyên nhị phân (Binary Integer Programming - BIP) là một phương pháp giải quyết các bài toán quyết định có dạng "có" hoặc "không" Ví dụ, các quyết định như học Thạc sĩ Toán, mua nhà hay kết hôn đều thuộc loại này Trong quy hoạch nguyên, các biến chỉ nhận giá trị 0 (không) hoặc 1 (có), giúp định hình rõ ràng các lựa chọn trong quá trình ra quyết định.
Bất kỳ bài toán quy hoạch nguyên nào với các biến nguyên bị chặn đều có thể chuyển đổi thành bài toán với các biến nhị phân (0-1) Ví dụ, nếu biến u có giá trị trong tập {1, 2, , k}, ta có thể biểu diễn u dưới dạng tổng các biến nhị phân u = u₁ + u₂ + + uₖ, với uᵢ ∈ {0, 1} cho i = 1, 2, , k Điều này chứng tỏ rằng quy hoạch nguyên 0-1 đóng vai trò quan trọng trong lĩnh vực quy hoạch nguyên.
2.5.2 Thuật toán Đầu tiên ta nêu lại một số khái niệm cơ bản sau:
⋄ Một họ P chưa hữu hạn các tập con của D, P := { D i ⊆ D | i ∈ I }, trong đó I là tập hữu hạn các chỉ số, được gọi là một phân hoạch của D nếu
⋄ Bài toán max f(x) v.đ.k x ∈ D i, (IP i) với D i ⊂ D được gọi là bài toán con của bài toán quy hoạch nguyên IP (cùng hàm mục tiêu nhưng tập chấp nhận được bé hơn).
⋄ Số thực α ∈R được gọi là một cận dưới của bài toán (IP) nếu α 6f opt
Nếu tìm được một giá trị x ∈ D sao cho f(x) ≤ f_opt, thì f(x) được coi là một cận dưới của bài toán (IP) Khi đó, x được gọi là một kỷ lục và f(x) được xem là giá trị kỷ lục.
⋄ Số thực β ∈R được gọi là một cận trên của bài toán (IP) nếu f opt 6 β
Trong quá trình tính toán, nếu xác định được một kỷ lục x và một cận trên β best cho bài toán IP sao cho β best = f(x), thì x opt = x sẽ là nghiệm tối ưu và f opt = f(x) sẽ là giá trị tối ưu của bài toán.
Thuật toán nhánh cận Land - Doig gồm có những bước chính sau:
Sau đây là chi tiết thuật toán nhánh cận Land - Doig giải bài toán quy hoạch tuyến tính nguyên (IP 0).
• Giải bài toán nới lỏng max { f (x) | x ∈ D nl 0 } được phương án tối ưu x 0 ;
• If x 0 nguyên then Dừng thuật toán (x 0 là nghiệm tối ưu của bài toán (IP 0 );
Else đặt β(D 0 ) := f (x 0 ); (cận trên của bài toán)
• If Biết một phương án x ∈ D then Đặt α := f (x);
Else Đặt α = −∞; (α là giá trị kỷ lục, x là một giá trị kỷ lục (nếu có))
• Đặt D = { D 0 }; (danh sách các tập con của D 0 cần xem tiếp).
Bước 1 (Chọn tập để chia)
Chọn tập chấp nhận D k ∈ D cho bài toán quy hoạch nguyên (IP k) với cận trên β(D k ) lớn nhất trong số các bài toán thuộc D Phương án tối ưu x k của bài toán nới lỏng (LP k) tương ứng với (IP k) có giá trị không nguyên.
• Giả sử x k j là một thành phần không nguyên đầu tiên của x k Phân hoạch D k thành hai tập:
• Đặt D := (D \ { D k } ) ∪ { D k 1 , D k 1 } (danh sách các tập con của D cần xem xét tiếp theo).
Bước 2 (Loại các tập con)
(2 1 ) Với mỗi i ∈ { 1, 2 }, giải bài toán quy hoạch tuyến tính nới lỏng (LP k i) Có thể gặp một trong ba tình huống sau:
(2 11 ) Bài toán không chấp nhận được, tức làD k i = ∅ Loại D k i khỏi việc xem xét tiếp theo (theo tiêu chuẩn 1), tức
(2 12 ) Tìm được phương án tối ưu x k i nguyên Khi đó, tính lại giá trị kỷ lục α = max { α, f (x k i ) } - giá trị kỷ lục hiện tại.
Gọi x là kỷ lục hiện tại tương ứng với giá trị kỷ lục hiện tại α = f (x).
Loại D k i khỏi việc xem xét tiếp theo (theo Tiêu chuẩn 2), tức
(2 13 ) Tìm được phương án tối ưu x k i là không nguyên Đặt β (D k i ) = f x k i
Ta có β (D k i ) là một cận trên của bài toán IP k i.
Loại bỏ D (theo Tiêu chuẩn 3) tất cả các tập không đạt yêu cầu, đảm bảo rằng các tập chấp nhận được của bài toán con có cận trên nhỏ hơn hoặc bằng giá trị kỷ lục hiện tại α (nếu có).
Bước 3 (Kiểm tra điều kiện dừng)
Nếu tập D rỗng (D = ∅), thuật toán sẽ dừng lại, với giá trị tối ưu f opt = α và x opt = x, trong đó giá trị tối ưu là kỷ lục hiện tại và phương án tối ưu chính là kỷ lục đó.
Trong quá trình thực hiện thuật toán nhánh cận, việc giải các bài toán quy hoạch tuyến tính con là rất quan trọng Các bài toán này đều có cùng hàm mục tiêu với bài toán ban đầu và có thể được giải bằng các phương pháp quy hoạch tuyến tính, thường sử dụng phương pháp đơn hình.
2.5.3 Ví dụ cho thuật toán
Bài toán 2.22 (Bài toán pha cắt vật liệu)
Trong lĩnh vực xây dựng, việc cắt một thanh thép dài 72m thành các đoạn 16m và 9m là một thách thức quan trọng Mục tiêu là tối ưu hóa số lượng đoạn cắt được, đồng thời giảm thiểu lượng thép thừa Để đạt được điều này, cần đảm bảo rằng mỗi thanh thép 72m phải có ít nhất một đoạn dài 16m hoặc một đoạn dài 9m Việc tìm ra cách cắt hợp lý sẽ giúp tiết kiệm vật liệu và nâng cao hiệu quả trong quá trình xây dựng.
Để giải bài toán, ta đặt x1 là số đoạn thép 16m và x2 là số đoạn thép 9m cắt được, với mục tiêu giảm thiểu số thép thừa Bài toán trở thành việc tìm giá trị lớn nhất của hàm f(x) = 16x1 + 9x2 Tuy nhiên, do chiều dài thanh thép chỉ có 72m, ta cần thỏa mãn ràng buộc 16x1 + 9x2 ≤ 72.
Ngoài ra, các thanh thép phải nguyên và phải có ít nhất một đoạn thép 16m hoặc
1 đoạn thép 9m nên ta có thêm các ràng buộc x 1 , x 2 > 0, x 1 + x 2 6 7 và x 1 , x 2 ∈Z Bài toán cần giải được phát biểu lại như sau: max f (x) = 16x 1 + 9x 2 v.đ.k
Kí hiệu tập chấp nhận được của bài toán này là D 0 ,
Ta sẽ giải bài toán này với thuật toán nhánh cận Land - Doig đã trình bày ở trên x 1 x 2
Bước chuẩn bị Giải bài toán nới lỏng (LP 0 ), với
D nl 0 = { x ∈R 2 | x 1 + x 2 6 7, 16x 1 + 9x 2 6 72, x 1 , x 2 > 0 } ta được nghiệm tối ưu x 0 = 9
T bằng cách sử dụng phương pháp đơn hình giải bài toán quy hoạch tuyến tính (Hình 3.5) Vìx 0 không nguyên nên đặt β(D 0 ) := f(x 0 ) = 72 (cận trên của bài toán (IP 0 )) α = −∞;
D := { D 0 }; (danh sách các tập con cần xem xét)
Bước 1 (lần thứ nhất) Chọn tập D 0 để chia Chia đôi tập D 0 bởi biến chia nhánh x 0 1 = 9
Bước 2 (lần thứ nhất) (xem hình 3.6)
⋄ Giải bài toán nới lỏng (LP 1 ) với D nl 1 := { x ∈ D 0 nl | x 1 6 1 } được nghiệm tối ưu x 1 =
(1, 6) T và giá trị tối ưu f(x 1 ) = 70 Do x 1 nguyên nên đặtα := max { α, f(x 1 ) } = 70.
Ta có kỷ lục đầu tiên x = x 1 = (1, 6) T tương ứng với giá trị kỷ lục α = 70 Loại tập D 1 (theo tiêu chuẩn 2) Khi đó,
⋄ Giải bài toán nới lỏng (LP 2 ) với D 2 nl := { x ∈ D nl 0 | x 1 > 2 } được nghiệm tối ưu x 2 = (2, 40
9 ) T và giá trị tối ưu f(x 2 ) = 72 Ta có β(D 2 ) := f(x 2 ) = 72 > α.Bước 3 (lần thứ nhất) Vì D = { D 2 } 6 = ∅ nên chuyển về Bước 1.
Bước 1 (lần thứ hai) Chọn tập D 2 để chia Chia đôi tập D 2 bởi biến chia nhánh x 2 2 = 40
Bước 2 (lần thứ hai) (xem hình 3.7)
Bài toán nới lỏng (LP 3) với D 3 nl := { x ∈ D nl 2 | x 2 6 3 } có nghiệm tối ưu x 3 = ( 45 16 , 3) T và giá trị tối ưu f (x 3 ) = 72 Cận trên của bài toán (IP 3) được xác định là β(D 3 ) := f (x 3 ) = 72, lớn hơn α Theo tiêu chuẩn 3, cận trên β(D 3) của bài toán con (IP k) không vượt quá giá trị kỷ lục hiện tại, do đó không cần xem xét tập D 3 này nữa.
⋄ Giải Bài toán nới lỏng(LP 4 )với
Giá trị tối ưu đạt được là f(x₄) = 72, lớn hơn α, với nghiệm tối ưu x₄ = (9, 4, 4)T Cận trên của bài toán (IP₄) được xác định là β(D₄) := f(x₄) = 72, cũng lớn hơn α Do đó, theo tiêu chuẩn 3, không cần tiếp tục xét tập D₄.
Ta kết thúc thuật toán và tìm được giá trị kỷ lục α = 70 tại x = (1, 6) T
Kết luận: Để tối ưu hóa việc cắt thanh dài 72m, chúng ta cần cắt thành 1 đoạn 16m và 6 đoạn 9m, nhằm tối đa hóa số lượng đoạn cắt được và tiết kiệm vật liệu, chỉ thừa lại 2m.
Các câu lệnh được viết dựa trên hàm intlinprog của Matlab nhằm giải quyết các bài toán quy hoạch tuyến tính nguyên. x 1 x 2
Hình 2.19 f unction intlinprogloi() thongbao1 = ′ N hap f = ′ ; f = input(thongbao1); thongbao2 = ′ N hap A = ′ ;
