Chuong 1

CHƯƠNG I:
BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
A - NỘI DUNG LÝ THUYẾT
1.1 Khái niệm
1.2 Một số bài toán QHTT trong thực tế
1.3 Giải bài toán QHTT đơn giản bằng PPHH
1.4 Một số khái niệm về giải tích lồi trong
1.5 Tính chất các phương án của bài toán QHTT
1.6 Phương án cực biên của QHTT dạng chính tắc
B – BÀI TẬP
1.1 Phân loại bài tập
1.2 Hướng dẫn giải

A - NỘI DUNG LÝ THUYẾT

1.1 KHÁI NIỆM

Để giải quyết một công việc trong một số điều kiện nào đó, chẳng hạn một vấn đề trong lĩnh vực kinh tế, quản lý hay khoa học kỹ thuật, người ta đưa ra một cách thức (phương án) hành động. Khi có nhiều phương án khả thi, điều tự nhiên là người ta muốn tìm phương án tốt nhất (tối ưu), theo một tiêu chuẩn chất lượng định trước nào đó. Bài toán điều khiển một quá trình với yêu cầu tìm phương án tốt nhất được gọi là “Bài toán điều khiển tối ưu”.

Bài toán điều khiển tối ưu được đặc trưng bởi:
- Một tập các điều kiện (còn gọi là các ràng buộc) cần phải tôn trọng khi xây dựng phương án.
- Mục tiêu điều khiển, tức là tiêu chuẩn chất lượng, mà theo đó, phương án này được đánh giá
tốt hơn phương án khác.

Quy hoạch toán học là một ngành của bộ môn toán nghiên cứu mô hình của lớp các bài toán điều khiển tối ưu, trong đó các ràng buộc được mô tả bởi một hệ phương trình và bất phương trình, còn mục tiêu điều khiển được biểu thị dưới dạng tìm giá trị lớn nhất hoặc nhỏ nhất của một hàm trên tập các nghiệm của của hệ phương trình và bất phương trình đó.
1.1.1 ĐỊNH NGHĨA BÀI TOÁN QUY HOẠCH TOÁN HỌC:
Bài toán quy hoạch toán học là bài toán:
 Hàm f cho trước được gọi là hàm mục tiêu của bài toán. Nếu:

Như vậy (2) là một hệ gồm các phương trình hay bất phương trình bậc
nhất theo các ẩn của bài toán và được gọi là các ràng buộc cưỡng bức của bài toán.
Ta có (3) và (4) là các điều kiện về dấu của ẩn số và được gọi là các
ràng buộc về dấu. Các điều kiện (2), (3), (4) được gọi chung là các
ràng buộc của bài toán.
Phương án X* mà tại đó hàm f đạt cực đại (hoặc cực tiểu) được gọi là một Phương án tối ưu (PATƯ) hay một nghiệm của bài toán. Giá trị f (X*) được gọi là Giá trị mục tiêu tối ưu (GTMTTƯ). Ta có:
* Đối với bài toán quy hoạch max:
* Đối với bài toán quy hoạch min:
Tập hợp các phương án tối ưu được gọi là Miền tối ưu của bài toán.
1.1.2 ĐỊNH NGHĨA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH:
(a) Bài toán quy hoạch tuyến tính dạng tổng quát
Một bài toán QHTT tổng quát có dạng:

Phương án X thoả mãn ràng buộc i với dấu “ = “ được gọi là thoả mãn chặt ràng buộc i, hay ràng buộc i được gọi là chặt đối với phương án X.

Phương án X thoả mãn ràng buộc i với dấu bất đẳng thức thực sự được gọi là thoả mãn lỏng ràng buộc i, hay ràng buộc i được gọi là lỏng đối với phương án X.

Một bài toán có ít nhất một một PATƯ được gọi là bài toán giải được. Một bài toán không có phương án hoặc có phương án nhưng không có PATƯ được gọi là không giải được hay vô nghiệm.
(b) Bài toán quy hoạch tuyến tính dạng chính tắc:
Cụ thể, một bài toán QHTT chính tắc có dạng:
 Với các kí hiệu ma trận trên, QHTT dạng chính tắc được viết lại như sau:
(c) Bài toán quy hoạch tuyến tính dạng chuẩn:
Nếu I1 = I (hoặc I2 = I) và J1 = J tức là hệ ràng buộc cưỡng bức là một hệ bất phương trình tuyến tính với các ẩn đều không âm thì bài toán QHTT được gọi là có dạng chuẩn.
Bài toán QHTT dạng chuẩn được viết dưới dạng:
1.1.3 ĐỊNH NGHĨA HAI QHTT TƯƠNG ĐƯƠNG:
Hai bài toán QHTT được gọi là tương đương nếu chúng cùng vô nghiệm hoặc nếu một trong hai bài toán có một nghiệm thì, bằng một cách nào đó, chúng ta cũng tìm được một nghiệm tương ứng của bài toán kia, và giá trị mục tiêu tối ưu của chúng bằng nhau hoặc đối nhau.
1.1.4 BIẾN ĐỔI DẠNG MỘT BÀI TOÁN QHTT:
Đôi khi, để tiện việc giải một bài toán QHTT, người ta biến đổi bài toán đã cho thành một bài toán dạng khác tương đương với bài toán đã cho. Chúng ta luôn có thể đưa một bài toán QHTT bất kỳ về dạng chính tắc hoặc dạng chuẩn tương đương bằng các phép biến đổi sau:
(a) Bài toán quy hoạch max có thể chuyển thành bài toán quy hoạch min, và ngược lại, bằng cách giữ nguyên tập các phương án và đổi dấu hàm mục tiêu. Tức là nếu (, f) là bài toán quy hoạch max thì (,- f) sẽ là bài toán quy hoạch min có cùng PATƯ với (, f) và ngược lại.
Thật vậy, giả sử X* là một phương án tối ưu của bài toán quy hoạch max ( , f )
Vậy X* là một phương án tối ưu của bài toán quy hoạch min (  , -f ).


1.2 MỘT SỐ BÀI TOÁN QHTT TRONG THỰC TẾ
1.2.1 BÀI TOÁN LẬP KẾ HOẠCH SẢN XUẤT
Giải: Gọi x1 và x2 theo thứ tự là số lượng (tính theo tấn) sản phẩm S1 và S2 cần sản xuất trong ngày. Khi đó doanh thu trong ngày là: z = 6x1 + 9x2 (đơn vị: 106 VNĐ)

Các ràng buộc trên các biến x1 và x2:
1.2.2 BÀI TOÁN KHẨU PHẦN ĂN:
Giả sử người ta cần tạo một hỗn hợp gồm hai loại thực phẩm T1 và T2. Hỗn hợp đó cần có 60 đơn vị chất dinh dưỡng D1, 160 đơn vị chất dinh dưỡng D2 và 180 đơn vị chất dinh dưỡng D3. Một kilôgam T1 chứa 3 đơn vị D1, 4 đơn vị D2, 3 đơn vị D3 và giá 15 ngàn đồng. Một kilôgam T2 chứa 1 đơn vị D1, 4 đơn vị D2, 6 đơn vị D3 và giá 12 ngàn đồng.

Hãy viết mô hình toán học cho bài toán: Xác định thành phần của T1 và T2 sao cho hỗn hợp được tạo ra bảo đảm nhu cầu về các chất dinh dưỡng và có giá thành rẻ nhất.
Giải: Gọi xj là số đơn vị (khối lượng) loại thực phẩm Tj (j = 1,…, n) cần mua.
Mô hình toán học phải tìm là QHTT:

1.2.3 BÀI TOÁN VẬN TẢI

Vì điều kiện là mỗi điểm tiêu thụ đều nhận đủ hàng theo nhu cầu và mỗi kho đều xuất hết hàng. Do đó, tổng số hàng vận chuyển sẽ bằng tổng số hàng ở các kho i và bằng tổng số hàng tiêu thụ ở các điểm thu j.
1.3 GIẢI BÀI TOÁN QHTT ĐƠN GIẢN BẰNG PPHH
1.3.1 PHƯƠNG PHÁP GIẢI
* Để giải bài toán này theo phương pháp hình học, trước tiên ta phải xác định miền ràng buộc  dựa vào hệ ràng buộc. Từ m ràng buộc cưỡng bức và các ràng buộc về dấu ta xác định được miền ràng buộc    là giao của m nửa mặt phẳng, giới hạn bởi các đường thẳng ai1x1 + ai2x2 = bi (i = 1, …, m) với góc phần tư thứ nhất của hệ trục toạ độ trong mặt phẳng toạ độ Ox1x2.
* Tập hợp những điểm có toạ độ (x1, x2), tại đó hàm mục tiêu f nhận giá trị z cho trước là đường thẳng (dz) có phương trình c1x1 + c2x2 = z, gọi là một đường mức với giá trị mức z (cũng chính là giá trị của hàm mục tiêu). Khi z nhận những giá trị khác nhau, chúng ta có một họ các đường mức song song.
.

* Để tìm phương án tối ưu của bài toán, chúng ta bắt đầu từ một đường mức có điểm chung với miền ràng buộc  , với một giá trị mức z nào đó. Tịnh tiến đường mức này theo hướng tăng (hay giảm) giá trị mức, tuỳ theo bài toán max (hay bài toán min). Việc tịnh tiến được tiến hành cho đến một vị trí giới hạn, mà khi vượt qua vị trí đó, đường mức sẽ không có điểm chung nào với  nữa. Toạ độ của những điểm thuộc  nằm trên đường mức cuối cùng này là những phương án tối ưu của bài toán.
Trong trường hợp đường mức có thể tịnh tiến ra vô tận mà vẫn không rời  thì hàm mục tiêu của bài toán không bị chặn; khi đó, bài toán không có phương án tối ưu.
Lưu ý: PPHH được dùng để giải những bài toán QHTT 2 ẩn. Tuy nhiên, PP này vẫn được dùng để giải những bài toán có nhiều hơn 2 ẩn nhưng có thể quy về 2 ẩn.
1.3.2 CÁC VÍ DỤ:
Giải: Trong mặt phẳng toạ độ Ox1x2, miền ràng buộc  được biểu diễn bởi tứ giác lồi có các đỉnh là các điểm O(0,0); (4,0); (0,7/2) và A(3,2) (Phần tô đen trong hình).
Vậy, bài toán có phương án tối ưu duy nhất là X* = (3, 2) và giá trị mục tiêu tối ưu là z* = 22.
Giải: Trong mặt phẳng toạ độ Ox1x2, miền ràng buộc  là tập lồi đa diện không giới nội trong góc phần tư thứ nhất của mặt phẳng toạ độ Ox1x2, với các đỉnh là các điểm: (0, 60); (10, 30); (20, 20) và (60, 0) (trong hình vẽ là vùng trắng trong góc phần tư thứ nhất).
Xét một đường mức (d900) có phương trình 15x1 + 12x2 = 900 đi qua đỉnh (60,0) của  (Trong hình vẽ là đường đứt đoạn).Tịnh tiến đường mức theo hướng giảm của giá trị mức, Điểm cuối cùng của  mà đường mức gặp trước khi rời  là đỉnh (10, 30).
Vậy, bài toán có phương án tối ưu duy nhất là X* = (10, 30), và giá trị mục tiêu tối ưu là f (X*) = 510
Chú ý: Phương pháp hình học được dùng để giải những bài toán QHTT hai ẩn. Tuy nhiên, phương pháp này vẫn được dùng để giải những bài toán có nhiều hơn 2 ẩn nhưng có thể quy về 2 ẩn.

Giải. Biểu diễn x3, x4 và x5 theo x1 và x1 chúng ta được:
và hàm mục tiêu trở thành: z = 15x1 + 12x2 - 220
Miền ràng buộc và hàm mục tiêu của bài toán này giống bài toán trong Ví dụ 2 nhưng là bài toán max. Do đó ta tịnh tiến đường mức theo hướng ngược với hướng bài toán trước, chúng ta nhận thấy giá trị của hàm mục tiêu có thể lớn tuỳ ý. Vậy bài toán này vô nghiệm. Do đó, bài toán đã cho vô nghiệm.
1.3.3 CHÚ Ý.
(a) Phương pháp hình học không những được dùng để giải một lớp bài toán QHTT, mà còn giúp chúng ta nhận ra được một số tính chất quan trọng và từ đó, có phương hướng giải bài toán QHTT. Chẳng hạn như:
* Miền ràng buộc của một QHTT là một tập lồi đa diện. Nếu nó giới nội, tức là miền ràng buộc là một đa diện lồi, thì có ít nhất một đỉnh là một phương án tối ưu của bài toán.
* Trường hợp bài toán không có phương án tối ưu thì hàm mục tiêu không bị chặn trên miền ràng buộc.
(b) Một phương pháp cổ, gọi là phương pháp Fourier - Motzkin, cũng được dùng để giải một số bài toán QHTT cỡ nhỏ. Nội dung của phương pháp này là khử dần ẩn cho đến khi không còn khử được nữa. Nhược điểm lớn nhất của phương pháp này là sau mỗi bước, tuy giảm được một ẩn, nhưng số ràng buộc lại tăng lên khá nhiều. Phương pháp này nằm ngoài phạm vi chương trình của chúng ta.
1.4 MỘT SỐ KHÁI NIỆM VỀ GIẢI TÍCH LỒI TRONG Rn
1.4.1 ĐỊNH NGHĨA:

(a) Siêu phẳng - Nửa không gian đóng - Tập lồi đa diện – Đa diện lồi
(b) Tổ hợp lồi - Tập hợp lồi

(c) Điểm cực biên – Phương án cực biên (PACB) - Đỉnh tối ưu
* Cho tập lồi L trong Rn. Một điểm X thuộc L được gọi là một điểm cực biên (hay một đỉnh ) nếu X không thể là một điểm trong của một đoạn thẳng nào nối hai điểm khác nhau bất kỳ của L.
Với các tập lồi đa diện trong R2 hoặc R3, chúng ta dễ nhận dạng ra một điểm cực biên: Nó là giao, theo thứ tự, của hai đường thẳng không cùng phương hoặc là giao của ba mặt phẳng, đôi một cắt nhau, không thuộc cùng một chùm mặt phẳng.
Khái quát hoá ra không gian Rn, một điểm X thuộc một tập lồi đa diện D là một điểm cực biên nếu và chỉ nếu X thoả mãn chặt n ràng buộc độc lập tuyến tính trong số các ràng buộc xác định D.
* Cho bài toán QHTT (  , f ). Nếu X là một điểm cực biên của  thì X được gọi là một phương án cực biên(PACB) của bài toán. Một PACB tối ưu còn được gọi là một đỉnh tối ưu.
(d) Hà m lồi – Hàm lõm
VD: Hàm f xác định trên Rn bởi f (X) = CX là một hàm vừa lồi vừa lõm
(e) Cực tiểu (cực đại) tuyệt đối - Cực tiểu (cực đại) địa phương
Cho một tập lồi L trong Rn và một hàm f xác định trên L.

1.4.2 ĐỊNH LÝ
Chứng minh:
Ta sẽ chứng minh Y thuộc L bằng phương pháp quy nạp theo k.
Định lý 2:
Trong Rn, một siêu phẳng, một nửa không gian đóng là các tập hợp lồi.
(b) Giao của một số hữu hạn các tập hợp lồi là một tập hợp lồi.
(c) Tập các phương án của một bài toán QHTT là một tập hợp lồi.
Chứng minh.
Chứng minh tương tự cho một nửa không gian đóng.
.
Lấy hai điểm X và Y bất kỳ thuộc D. Khi đó:
(c) Tập các phương án của bài toán QHTT là giao hữu hạn của các siêu phẳng và các nửa không gian đóng trong Rn mà các siêu phẳng và các nửa không gian đóng là các tập hợp lồi (theo câu (a)). Do đó tập phương án của bài toán QHTT là giao hữu hạn các tập hợp lồi nên tập phương án cũng là một tập hợp lồi (theo câu(b)).
Định lý 3:
Nếu một hàm lồi f đạt cực tiểu địa phương tại điểm X* thuộc tập lồi L thì X* cũng là điểm cực tiểu tuyệt đối của f.
(b) Nếu một hàm lồi f đạt cực đại địa phương tại điểm X* thuộc tập lồi L thì X* cũng là điểm cực đại tuyệt đối của f.
Chứng minh:
Vậy f đạt cực tiểu tuyệt đối tại điểm X*.
(b) Chứng minh tương tự.
1.5 TÍNH CHẤT CÁC PHƯƠNG ÁN CỦA BÀI TOÁN QHTT
1.5.1 ĐỊNH NGHĨA
* Định nghĩa: Cho phương án X của QHTT (, f )
1.5.2 ĐỊNH LÝ
Chứng minh:
Ò
Vậy H là một hướng giảm.
Chứng minh.
Giả sử bài toán đã cho là bài toán min, và giá trị mục tiêu tối ưu là m
Vì  là một tập hợp lồi, nên X thuộc  (theo định lý 1 (1.4.2))
Vậy X là một PATƯ
Chứng minh tương tự cho bài toán max.
Chứng minh: Thật vậy, nếu một bài toán QHTT có nhiều hơn một nghiệm tức là có nhiều hơn một PATƯ thì tổ hợp lồi của các PATƯ đó lại là một PATƯ tức là nghiệm của bài toán QHTT. Do đó, bài toán QHTT sẽ có vô số nghiệm.
Nhận xét: Từ định định lý và hệ quả trên, ta nhận thấy rằng tập hợp nghiệm của bài toán QHTT chỉ có thể là một trong 3 trường hợp sau: bằng rỗng, chỉ có một phần tử hoặc có vô số phần tử.
Chứng minh.
Giả sử f bị chặn dưới rên . Ta sẽ chứng bài toán có phương án cực biên tối ưu.
Xem một phương án X bất kỳ, và giả sử hạng của X là k < n.
Vì k < n nên các vectơ Hi với i thuộc I’ nằm trong một không gian con thực sự của Rn. Do đó, có một vectơ V thuộc Rn {On} sao cho HiV = 0 với mọi i thuộc I’. Không mất tính tổng quát, giả sử CV < 0 (nếu CV > 0 thì lấy -V thay cho V).
Trường hợp CV < 0:
Trường hợp CV = 0:

Vậy, Zk là một PACB tối ưu.
Nhận xét: Từ định lý trên, ta thấy rằng đối với một bài toán QHTT có tập phương án khác rỗng và hàm mục tiêu bị chặn (bị chặn dưới đối với bài toán min, bị chăn trên đối với bài toán max) thì sẽ có PATƯ.
1.6 PHƯƠNG ÁN CỰC BIÊN CỦA QHTT DẠNG CHÍNH TẮC
1.6.1 ĐỊNH NGHĨA
Bài toán (T) được gọi là không suy biến nếu tất cả các phương án cực biên của nó đều không suy biến.
1.6.2 ĐỊNH LÝ
Chứng minh:
(i) Giả sử L(X) phụ thuộc tuyến tính.
(ii) Bây giờ, giả sử X không phải là một PACB.
Chứng minh:
(a) Ta có m là số ràng buộc cưỡng bức cũng chính là số dòng của ma trận A, cũng chính là số chiều của vectơ Aj. Phương án là cực biên tức là hệ vectơ liên kết với phương án đó phải độc lập tuyến tính. Mà một hệ vectơ m chiều độc lập tuyến tính có không quá m véctơ. Do vậy, số thành phần dương của một phương án cực biên không lớn hơn m.
(b) Thật vậy, vì số hệ con độc lập tuyến tính được thiết lập từ hệ A1,A2,…,An là hữu hạn.
Nhận xét: Định lý trên đã chỉ ra cách tìm các phương án cực biên của bài toán QHTT dạng chính tắc. Trước hết, giả sử rằng hạng của ma trận trong bài toán bằng m (điều này không làm mất tính tổng quát). Từ các vectơ A1,A2,…,An lấy ra tất cả các hệ con gồm đủ m véctơ độc lập tuyến tính rồi khai triển vectơ B qua mỗi hệ con đó. Mỗi phương án cực biên ứng với một hệ con mà các hệ số trong khai triển nói trên đều không âm (các hệ số chính là giá trị của các ẩn dương, các ẩn còn lại sẽ có giá trị bằng 0) . Mỗi hệ con như vậy được gọi là cơ sở liên kết của phương án cực biên tương ứng.
Từ các vectơ trên ta có được 6 hệ con độc lập tuyến tính, mỗi hệ có 2 vectơ.
Loại bỏ các vectơ có ít nhất một thành phần âm ta thu được 4 PACB là x1, x3, x4, x6.
Chứng minh: Cho bài toán QHTT (T).
Giả sử X = (x1, x2, . . ., xn) là một phương án của (T).
Nếu X khác On và không là một phương án cực biên thì JX khác rỗng và giả sử
L(X) phụ thuộc tuyến tính.
Nếu Y là một phương án cực biên thì định lý đã được chứng minh.
Chứng minh:
Theo định lý 2 (1.5.2) thì Y và Z cũng là các PATƯ. Nếu Y vẫn chưa là một PACB thì chúng ta lại chó thể biễu diễn Y qua hai PATƯ Y1 và Z1 với số thành phần dương của Y1 ít hơn số thành phần dương của Y…Quá trình trên sẽ dẫn đến một PACB và PACB này cũng là một PATƯ của bài toán nên sẽ là PACBTƯ.
Chứng minh.
Chúng ta đưa bài toán về dạng chính tắc tương đương với nó. Vì tập phương án khác rỗng nên theo định lý 2 ở trên thì bài toán sẽ có phương án cực biên, tức là miền ràng buộc có điểm cực biên. Khi đó, áp dụng định lý 3 (1.5.2), chúng ta có điều phải chứng minh.
Tịnh tiến đường mức theo hướng giảm của giá trị mức, điểm cuối cùng của  mà đường mức gặp trước khi rời  là đỉnh A(4;6)
Vậy bài toán có PATƯ duy I là X* = (4 ;6) và giá trị mục tiêu tối ưu là f(X*) = 23
Vậy X*=(5,3,8,-1) là PACB.
Vì đây là bài toán min và hàm mục tiêu không bị chặn dưới nên . Do đó bài toán không có PATƯ do đó không giải được.
Vậy hàm f bị chặn dưới nên X* = (5,3,8,-1) là PACBTƯ.