Học phần lí thuyết tối ưu tuyến tính bài tập nhóm chương 1

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (336.59 KB, 38 trang )

Trang 1<div class="page_container" data-page="1">

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINHKHOA TỐN - TIN HỌC

HỌC PHẦN LÍ THUYẾT TỐI ƯU TUYẾN TÍNH

</div>Trang 2<div class="page_container" data-page="2">

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINHKHOA TỐN - TIN HỌC

HỌC PHẦN LÍ THUYẾT TỐI ƯU TUYẾN TÍNH

BÀI TẬP NHĨM CHƯƠNG 1

Giảng viên hướng dẫn: Phạm Duy Khánh

Nhóm thực hiện: Nhóm 3

1. Trần Đặng Minh Tân (nhóm trưởng) MSSV: 47.01.101.123 2. Phạm Lê Hồng Thơng MSSV: 47.01.101.128

5. Trần Quang Minh MSSV: 47.01.101.097 6. Đặng Cơng Minh Khơi MSSV: 47.01.101.091 7. Đồn Cao Minh Trí MSSV: 47.01.101.047

9. Nguyễn Đại Nghĩa MSSV: 47.01.101.102

</div>Trang 3<div class="page_container" data-page="3">

Bảng phân chia nhiệm vụ

1. Trần Đặng Minh Tân Bài tập 1.5 + Tổng hợp 2. Phạm Lê Hồng Thơng Bài tập 1.9

3. Lê Gia Huy Bài tập 1.8 và 1.13 4. Hồ Thị Thu Hồng Bài tập 1.12 5. Trần Quang Minh Bài tập 1.10 6. Đặng Cơng Minh Khơi Bài tập 1.2 7. Đồn Cao Minh Trí Bài tập 1.4 và 1.7 8. Phan Trọng Tín Bài tập 1.1 9. Nguyễn Đại Nghĩa Bài tập 1.3

10. Nguyễn Hữu Quân Bài tập 1.11 và 1.14 11. Trần Hoàng Lộc Bài tập 1.6

</div>Trang 5<div class="page_container" data-page="5">

1Kiến thức chuẩn bị

Định nghĩa 1.1 Xét một tập lồi đa diện P ⊂ Rnđược định bởi các ràng buộc đẳng thức và bất đẳng thức, và x∗là một điểm của Rn.

(a) Ta nói x∗là một phương án cơ sở (basic solution) nếu: (i) Tất cả các ràng buộc đẳng thức đều là ràng buộc hoạt tại x∗;

(ii) Trong tất cả các ràng buộc hoạt tại x∗, có thể trích ra n ràng buộc độc lập tuyến tính.

(b) Nếu x∗ là một phương án cơ sở và thỏa mãn tất cả các ràng buộc thì ta nói nó là một phương án cớ sở chấp nhận được (basic feasible solution).

Định lí 1 Xét bài tốn tìm giá trị nhỏ nhất của hàm chi phí cTxtrên một tập lồi đa diện P . Giả sử P có điểm cực biên và bài tốn có phương án tối ưu. Khi đó, tồn tại một phương án tối ưu là điểm cực biên của P .

Chứng minh. Giả sử P = {x ∈ Rn | Ax ≥ b}. Gọi Q là tập hợp các phương án tối ưu. Gọi v là giá trị nhỏ nhất của hàm cTx. Khi đó, ta có

Q =x ∈ Rn| Ax ≥ b, cTx = v

Suy ra, Q có điểm cực biên. Lấy x∗ là một điểm cực biên bất kỳ của Q. Bằng phản chứng, ta cũng chứng minh được x∗là một điểm cực biên của P .

Định lí 2 Cho P ⊂ Rnlà một tập lồi đa diện khác rỗng và x∗ ∈ P . Khi đó, các mệnh đề sau đây tương đương.

(a) x∗là một đỉnh.

(b) x∗là một điểm cực biên.

Chứng minh. Khơng mất tính tổng qt, giả sử P được biểu diễn bởi các ràng buộc dạng aT

i x ≥ bi. Trước tiên, ta chứng minh "(a) kéo theo (b)".

Giả sử x∗là một đỉnh. Lấy tùy ˆyy, z ∈ P, cả hai đều khác x∗, và λ ∈ (0; 1). Khi đó, tồn tại một vectơ c sao cho cTx∗ < cTyvà cTx∗ < cTz.

Suy ra x∗ ̸= λy + (1 − λ)z, tức là x∗là điểm cực biên. Tiếp theo, ta chúng minh "(b) kéo theo (c)".

Bằng phản chứng, giả sử x∗không phải là phương án cơ sở chấp nhận được. Gọi I =i | aT

i x∗ = bi.

Khi đó, tập sinh của hệ vectơ ai, i ∈ I có số chiều nhỏ hơn n.

Gọi d ̸= 0 là vectơ trong Rntrực giao với tập sinh của hệ vectơ ai, i ∈ I.

Khi đó, tồn tại số dương ε đủ nhỏ sao cho hai điểm y = x∗+ εdvà z = x∗− εd đều thuộc P .

</div>Trang 6<div class="page_container" data-page="6">

Suy ra x∗ = 12y + 12z, do đó x∗khơng phải là điểm cực biên. Cuối cùng, ta chứng minh "(c) kéo theo (a)′′.

Giả sử x* là phương án cơ sở chấp nhận được.

Gọi I là tập gồm n chỉ số của n ràng buộc độc lập tuyến tính hoạt tại x∗.

Hệ quả 1. Xét bài tốn quan hệ tuyến tính ở dạng tổng qt. Nếu bài tốn

có phương án và hàm mục tiêu bị chặn dưới trên tập phương án thì bài tốn có nghiệm.

</div>Trang 7<div class="page_container" data-page="7">

2Bài tập chương 1

2.1Bài tập 1.1

Bài tập 1.1

Giả sử có một mặt hàng được lưu trữ ở m trạm phát P1, P2, ..., Pm, tiêu thụ ở n trạm thu T1, T2, ..., TN. Hãy xác định cách thức vận chuyển hàng từ các trạm phát đến các trạm thu sao cho chi phí tốt nhất với các dữ kiện như sau

(1) Giá vận chuyển một đơn vị hàng từ mỗi trạm phát đến mỗi trạm thu: Gọi cij là chi phí vận chuyển một đơn vị hàng từ trạm phát Piđến trạm thu Tj(i = 1, m; j = 1, n).

(2) Khả năng thu, phát của mỗi trạm: Gọi

- Trạm phát Piđang lưu trữ ai đơn vị hàng i = 1, m. - Trạm thu Tj có thể thu nhận bj đơn vị hàng j = 1, n.

Bài làm

• Có m trạm phát P1, P2, ..., Pm, lưu trữ ai > 0đơn vị hàng, với i = 1, m. • Có n trạm thu T1, T2, ..., TN, thu nhận bj > 0đơn vị hàng, với j = 1, n.

• Chi phí vận chuyển một đơn vị hàng từ trạm phát Pi đến trạm thu Tj là cij (i =

• Do số hàng được chuyển từ các tạm phát Piđến mỗi tạm thu Tjphải không vượt quá số hàng tạm thu Tjcó thể nhận được nên ta có

m X

xij ≤ bj, j = 1, n.

</div>Trang 8<div class="page_container" data-page="8">

Từ phân tích trên, ta đưa ra mơ hình tốn học của bài tốn:

+ Bài tốn trên là dạng đặc biệt của bài toán quy hoạch tuyến tính - mơ hình bài tốn vận tải, thường được áp dụng vào thực tiễn.

+ Bài toán giúp giải quyết vấn đề phân phối hàng hóa từ một số địa điểm cụ thể (điểm nguồn, trạm phát) đến một số địa điểm tiêu thụ (điểm đích, trạm thu) sao cho: tổng chi phí vận chuyển thấp nhất, cự ly vận chuyển nhỏ nhất, hay tổng tiền lời nhiều nhất. Bài tốn trên được xây dựng theo mơ hình bài tốn vận tải với tổng chi phí vận chuyển thấp nhất.

</div>Trang 9<div class="page_container" data-page="9">

Tồn tại hay không ma trận A và vectơ b để bài tốn trên

(a) Có vơ số nghiệm.

(b) Vô nghiệm nhưng tập phương án khác rỗng.

Đặt f (x1, x2, x3) = x1+ 2x2+ x3với mọi (x1, x2, x3) ∈ R3. Ta sẽ chứng minh các vectơ dạng u∗ = (2 − t, 0, t)với t ∈ [0, 2] là phương án tối ưu của bài toán (1).

</div>Trang 10<div class="page_container" data-page="10">

Suy ra u∗ = (2 − t, 0, t)với t ∈ [0, 2] là phương án của bài toán (1). Hơn nữa lấy phương án u = (x1, x2, x3) ∈ R3bất kì, ta có: f (u) = x1+ 2x2+ x3 ⩾ 2 = f (u∗).

Suy ra u∗ = (2 − t, 0, t)là phương án tối ưu của bài toán (1). Mà t ∈ [0, 2] nên bài tốn (1) vơ số nghiệm.

(b) Giả sử tồn tại ma trận A và b để tập phương án khác rỗng thì theo hệ quả 1, bài tốn sẽ có nghiệm do hàm mục tiêu ln bị chặn dưới bởi 0 trên tập phương án khác rỗng (mâu thuẫn). Vậy không tồn tại ma trận A và b để bài tốn vơ nghiệm

Đặt f (x1, x2, x3) = x1+ 2x2+ x3với mọi (x1, x2, x3) ∈ R3. Ta sẽ chứng minh nghiệm u∗ = (0, 0, 0)của bài toán trên là nghiệm duy nhất. Ta có

Vậy (0, 0, 0) là phương án của bài toán.

Hơn nữa lấy phương án u = (x1, x2, x3) ∈ R3bất kì, ta có: f (u) = x1+ 2x2+ x3 ⩾ 0 = f (u∗)

Suy ra u∗ = (0, 0, 0)là nghiệm của bài tốn. Giả sử k = (k1, k2, k3)là nghiệm. Vì giá trị tối ưu của bài toán quy hoạch tuyến tính nếu có là duy nhất nên f (k) = f (u∗) hay k1+ 2k2+ k3 = 0. Suy ra k1 = k2 = k3 = 0(vì k1, k2, k3 ≥ 0). Vậy u∗ = k. Kết luận u∗là nghiệm duy nhất.

Nhận xét:

Để đánh giá nghiệm của bài toán ta xét bài toán trên trong hệ tọa độ Oxyz. Với ràng buộc x ≥ 0 và Ax ≥ b thì tập phương án sẽ là mặt phẳng nằm ở phần dương các

</div>Trang 11<div class="page_container" data-page="11">

trục tọa độ. Với câu a để vơ số nghiệm thì ta có thể chọn tập phương án sao cho mặt phẳng đó khơng giao với điểm gốc. Câu b ta sẽ áp dụng hệ quả 1. Câu c ta sẽ cho mặt phẳng đó giao với gốc tọa độ.

</div>Trang 12<div class="page_container" data-page="12">

2.3Bài tập 1.3

Bài tập 1.3

Cho A là ma trận cấp 2 × 3 với hệ số thực, vectơ b ∈ R2và c = (1, 1, 1). Xét bài toán quy hoạch tuyến tính

Tồn tại hay khơng ma trận A và vevtơ b để bài tốn trên

(a) Có vơ số nghiệm. giá trị tối ưu của bài toán (1) là −4.

Ta sẽ chứng minh các vectơ dạng xt = (t, −4 − t, 0)với t ∈ R là phương án tối ưu của bài toán (1).

</div>Trang 13<div class="page_container" data-page="13">

Suy ra xt = (t, −4 − t, 0)với t ∈ R là phương án của bài toán (1). Hơn nữa với xt= (t, −4 − t, 0), t ∈ R ta có f(t, −4 − t, 0) = t + (−4 − t) + 0 = −4.

Suy ra xt = (t, −4 − t, 0)là phương án tối ưu của bài toán (1). Mà t ∈ R nên bài tốn (1) vơ số nghiệm

Định nghĩa: Đỉnh

P là tập lồi đa diện. Veto x ∈ P được gọi là đỉnh nếu tồn tại vecto c sao cho

⟨c, x⟩ < ⟨c, y⟩ với mọi y ∈ P và y ̸= x.

Định nghĩa: hoạt - buộc

Nếu véctơ x∗thỏa ⟨ai, x∗⟩ = bivới chỉ số i nào đó trong M1, M2hoặc M3ta nói

ràng buộc tương ứng với chỉ số i là hoạt hay buộc tại x∗.

Định nghĩa: Nghiệm cơ sở - Nghiệm cơ sở chấp nhận được

Xét tập lồi đa diện P cho bởi các ràng buộc đẳng thức và bất đẳng thức tuyến tính và x∗ là vecto trong Rn. Vecto x∗gọi là nghiệm cơ sở nếu

(i) Các ràng buộc đẳng thức x là hoạt tại x∗.

(ii) Trong các ràng buộc hoạt tại x∗, tồn tại n ràng buộc độc lập tuyến tính. Vecto x∗ gọi là nghiệm cơ sở chấp nhận được nếu x∗ là nghiệm cơ sở và x∗ thỏa tất cả các ràng buộc

Chứng minh: Đỉnh → Nghiệm cơ sở chấp nhận được

Giả sử x∗ ∈ P không là nghiệm cơ sở chấp nhận được. Ta sẽ chứng minh x∗ không là đỉnh của P . Đặt I = {i : ⟨ai, x∗⟩ = bi}. Do x∗ không là nghiệm cơ sở chấp nhận được nên trong hệ {ai : i ∈ I}không tồn tại n véctơ độc lập tuyến tính. Do đó tồn tại véctơ d ∈ Rn\{0} sao cho ⟨ai, d⟩ = 0với mọi i ∈ I. Chọn ε là số thực dương thỏa ε |⟨ai, d⟩| < ⟨ai, x∗⟩ − bivới mọi i /∈ I. Khi đó y = x∗+ εd, z = x∗− εd ∈ P . Thật vậy, nếu i ∈ I thì

⟨ai, x∗± εd⟩ = ⟨ai, x∗⟩ ± ε ⟨ai, d⟩ = ⟨ai, x∗⟩ = bi

Do đó ⟨ai, y⟩ = ⟨ai, z⟩ = ⟨ai, x∗⟩ = bi với mọi i ∈ I. Chú ý rằng x∗ ̸= y ̸= z do đó x∗khơng là đỉnh của P . Vậy nếu x∗là đỉnh thì x∗ cũng là nghiệm cơ sở chấp nhận được.

</div>Trang 14<div class="page_container" data-page="14">

Với mỗi x = (x1, x2, x3) ∈ P. Ta có x tối đa hai ràng buộc là hoạt, trong khi chiều khơng gian đang xét là 3. Vì vậy tại x khơng thể có đủ 3 ràng buộc hoạt độc lập tuyến tính nên x khơng là nghiệm cơ sở của P . Suy ra khơng có nghiệm cơ sở

Gọi P là tập phương án của bài toán (2). Với mọi xt = (2, 2, t) ∈ P với t ∈ R và t ≥ 0. hàm mục tiêu không bị chặn. Do đó bài tốn vơ nghiệm. Hiển nhiên tập phương án của bài toán khác rỗng.

Nhận xét:

+ Đặt (P ) : x1+ x2+ x3 = avì x1+ x2+ x3 → max

nên ta sẽ trược mặt phẳng (P ) theo chìu vecto c = (1, 1, 1). Với câu a để vơ số nghiệm thì ta phải chọn hai mặt phẳng sao cho giao của hai mặt phẳng chặn trên mặt phẳng (P ) và tập phương án nằm trên các cạnh của mặt phẳng (P ). Với câu c thì ta chọn 2 mặt phẳng sao cho giao của chúng không chặn trên mặt phẳng (P )

+ Từ câu b) ta có thể thấy ko phải bài tốn QHTT nào cũng có nghiệm duy nhất mà tùy thuộc vào rank của ma trận A. Muốn x∗ là vecto trong Rn là nghiệm duy nhất của bài tốn QHTT thì phải tồn tại n ràng buộc độc lập tuyến tính.

</div>Trang 15<div class="page_container" data-page="15">

2.4Bài tập 1.4

Bài tập 1.4

Chứng minh các tính chất sau:

(a) Giá trị tối ưu của bài tốn quy hoạch tuyến tính là duy nhất.

(b) Bài tốn quy hoạch tuyến tính có thể vơ nghiệm, duy nhất nghiệm, vơ số nghiệm.

Bài làm

(a) Giả sử ngược lại bài tốn quy hoạch tuyến tính có nhiều hơn một giá trị tối ưu. Khi đó, tồn tại u1, u2là nghiệm của bài tốn quy hoạch tuyến tính mà φ(u1) ̸= φ(u2). Vì u1là nghiệm của bài tốn quy hoạch tun tính, nên với mọi phương án u, ta có: φ(u) ≥ φ(u1) ⇒ φ(u2) ≥ φ(u1). (1)

Vì u2là nghiệm của bài tốn quy hoạch tun tính, nên với mọi phương án u, ta có: φ(u) ≥ φ(u2) ⇒ φ(u1) ≥ φ(u2). (2)

Từ (1) và (2), ta suy ra: φ(u1) = φ(u2). Điều này mâu thuẫn với giả thiết phản chứng. Vậy giá trị tối ưu của bài toán quy hoạch tuyến tính là duy nhất.

(b) Theo bài tập 1.5, ta thấy bài tốn quy hoạch tuyến tính có thể vơ nghiệm, duy nhất nghiệm, vơ số nghiệm.

Giả sử bài tốn quy hoạch tuyến tính có hữu hạn nghiệm (*). Khi đó, gọi x1, x2 là nghiệm của bài toán quy hoạch tuyến tính.

Khi đó xét các điểm z = λx1+ (1 − λ)x2, λ ∈ [0; 1]. Theo câu (a), ta có giá trị tối ưu của bài tốn quy hoạch tuyến tính là duy nhất, nên φ(x1) = φ(x2) = k.

Lại có: φ(z) = φ(λx1) + φ((1 − λ)x2) = λφ(x1) + (1 − λ)φ(x2) = λk + (1 − λ)k = k. Do đó, z cũng là nghiệm của bài tốn quy hoạch tuyến tính. Nói cách khác, với mọi λ ∈ [0; 1]thì z = λx1+ (1 − λ)x2, λ ∈ [0; 1]là nghiệm của bài toán quy hoạch tuyến tính. Suy ra bài tốn quy hoạch tuyến tính có vơ số nghiệm. (mâu thuẫn với (*)). Vậy bài tốn quy hoạch tuyến tính có thể vơ nghiệm, duy nhất nghiệm, vơ số nghiệm.

Bình luận: Ở câu (b), để chứng minh khơng xảy ra trường hợp bài tốn quy hoạch

tuyến tính có hữu hạn nghiệm. Ta sử dụng mệnh đề "Tập nghiệm của bài toán quy hoạch tuyến tính là tập lồi đa diện" nên nếu gọi M∗là tập tất cả các nghiệm của bài tốn QHTT, thì M∗là một tập lồi. Khi đó lấy hai điểm x1, x2thuộc M∗thì đoạn thẳng nối hai điểm đó cũng nằm trong M∗, hay mọi điểm z = λx1+ (1 − λ)x2, λ ∈ [0; 1] đều là nghiệm. Vì lực lượng của [0;1] là vô hạn nên ta sẽ suy ra được điều vô lý.

</div>Trang 16<div class="page_container" data-page="16">

TH2: 0 ⩽ m < 1. Giả sử bài tốn có nghiệm thỏa mãn ràng buộc. Ta nhận thấy rằng (0, b, 0) với b ≥ 0 là 1 phương án của bài toán do:

Điều ở trên chứng tỏ với mỗi giá trị của b, ta ln tìm được 1 giá trị khác tối ưu hơn nên bài tốn khơng có nghiệm tối ưu.

Như vậy từ 2 trường hợp trên ta có thể kết luận: Với m < 1, bài tốn vơ

</div>Trang 17<div class="page_container" data-page="17">

thì ta nhận thấy u∗ = (a, b + 1, c)cũng là 1 phương án của bài toán do thỏa Suy ra với m < 1, bài tốn vơ nghiệm.

2. Xét m = 1, ta sẽ chỉ ra rằng (0, t, 0) với t ⩾ 0 bất kì là nghiệm của bài tốn. + Chứng minh (0, t, 0) là phương án: Thật vậy, ta ln có:

Giả sử (a, b, c) là phương án bất kì thỏa các ràng buộc của bài tốn. Ta có được: a ⩾ 0 và c ⩾ 0 nên a + c ≥ 0 hay φ(a, b, c) ⩾ φ(0, t, 0) Vậy với m = 1, bài tốn đã cho có vô số nghiệm.

3. Với m > 1, ta sẽ chứng minh (0, 0, 0) là nghiệm duy nhất của bài toán. + Chứng minh (0, 0, 0) là phương án tối ưu của bài toán:

+ Chứng minh (0, 0, 0) là nghiệm duy nhất của bài toán:

Giả sử bài toán có nghiệm (a, b, c) ̸= (0, 0, 0) thì ta có: a2+ b2+ c2 > 0. Khi đó, do giá trị tối ưu của bài toán QHTT là duy nhất nên:

φ(a, b, c) = φ(0, 0, 0) ⇔ a + (m − 1)b + c = 0 ⇔ a = b = c = 0(!) Như vậy với m > 1, bài tốn có nghiệm duy nhất (0, 0, 0)

</div>Trang 18<div class="page_container" data-page="18">

Nhận xét:

+ Trước hết, việc phân chia giá trị của tham số m theo 3 trường hợp so sánh với 1 là do m − 1 là hệ số của biến thứ 2 ở hàm mục tiêu, có tác động đến giá trị của hàm mục tiêu với chú ý rằng hàm này là 1 hàm theo các biến khơng âm.

+ Việc trình bài tốn với m < 1 theo 2 cách giải cho ta thấy sự tối ưu trong việc lựa chọn phương hướng giải.

Ở cách 1 ta cần chia ra 2 trường hợp và rõ ràng nhận thấy rằng sự vô nghiệm của bài toán sẽ rơi vào 2 hướng: Hoặc là tập phương án là rỗng, hoặc là tập phương án tồn tại nhưng không thể chọn ra được phương án tối ưu để trở thành nghiệm của bài toán và kĩ thuật được dùng ở cách 1 là chọn ra 1 dãy nghiệm làm cho hàm mục tiêu tiến đến vô cùng. Và với chú ý về dấu của m − 1 có tác động đến biến 2, ta sẽ chọn dãy sao cho triệt tiêu 2 biến kia và chỉ cho biến 2 chạy.

Ở cách 2, việc chọn phương án thay đổi ở biến thứ 2 để đưa đến điều mâu thuẫn hoàn toàn xuất phát tự nhiên từ định nghĩa của phương án tối ưu:

u∗ ∈ M là nghiệm của bài toán QHTT khi và chỉ khi: ∀u ∈ M, φ(u) ⩾ φ(u∗).

Như vậy với việc xác định đây là trường hợp vơ nghiệm, ta có thể định ra cách giải bằng việc phủ định lại mệnh đề trên. Tức là:

Bài tốn QHTT vơ nghiệm khi và chỉ khi: ∃u ∈ M, φ(u) < φ(u∗) hay ta chỉ ra 1 phương án sao cho khẳng định φ(u) ⩾ φ(u∗)dẫn đến điều vơ lí.

Khi đó, với chú ý rằng m − 1 < 0 sau khi giả sử bộ nghiệm của bài toán tồn tại là (a, b, c)và ta chọn phương án khác sao cho chỉ thay đổi ở thành phần thứ 2 và giá trị này lớn hơn giá trị của bộ nghiệm đã đặt, ta chọn (a, b + 1, c) thì khi đưa vào mệnh đề so sánh giá trị hàm mục tiêu ở trên ta sẽ dẫn đến được sự vơ lí. Tất nhiên khơng chỉ bộ (a, b + 1, c) mà ta có thể chọn nhiều bộ khác (a, b + n, c) với n > 1. a

</div>Trang 19<div class="page_container" data-page="19">

phương án và tập nghiệm của bài toán.

(a) Điểm x ∈ M gọi là nghiệm địa phương của bài toán trên nếu tồn tại

r > 0sao cho

⟨c, x⟩ ≥ ⟨c, x⟩, với mọi x ∈ B(x, r) ∩ M.

(b) Nếu x ∈ M∗ và x = λx + (1 − λ)y với λ ∈ (0, 1), x, y ∈ M thì x, y ∈ M∗. Đặc biệt nếu d là đường thẳng nằm trong M và d cắt M∗thì d nằm trong M∗.

(c) Nếu M∗ ∩ intM ̸= ∅ thì c = 0. Đặc biệt nếu c ̸= 0 thì nghiệm của bài toán QHTT nằm trên biên của tập phương án.

Bài làm

(a) Với mọi y ∈ M , vì x ∈ M và M là tập lồi nên λ.x + (1 − λ)y ∈ M với mọi λ ∈ (0; 1). Từ x là nghiệm địa phương nên tồn tại r > 0 sao cho ⟨c, x⟩ ≥ ⟨c, x⟩, ∀x ∈

</div>