Thuật Toán Đơn Hình

Chương 1. Bài toán Quy hoạch tuyến tính
1.1. Khái niệm bài toán QHTT

1.2. Cơ sở Giải tích lồi
1.1. Khái niệm bài toán QHTT
1.1.1. Bài toán tối ưu

1.1.2. Một số ví dụ về QHTT

1.1.3. Bài toán QHTT
1.1.1. Bài toán tối ưu
Bài toán
Tìm x=(x1,x2,…,xn) sao cho
f(x)=f(x1,x2,…,xn) → min (hay max) (1.1)
Với các điều kiện

(1.1)-(1.4): bài toán Quy hoạch toán học
Trong đó:
f(x) : Hàm mục tiêu
gi, hj : Các hàm ràng buộc
(1.2)-(1.4) : Các ràng buộc
(1.2) : Các ràng buộc BĐT
(1.3) : Các ràng buộc đẳng thức
Phương án, phương án tối ưu
Tập hợp
D={xєX: gi(x)≤0, i=1,…,m; hj(x)=0, j=1,…,p}
Được gọi là Miền ràng buộc, hoặc Miền chấp nhận được, hoặc Tập các phương án.
Mỗi xD là một phương án hay một điểm chấp nhận được
Một phương án x*D đạt cực tiểu (hay cực đại) của hàm mục tiêu là một phương án tối ưu
f(x*) là giá trị tối ưu của bài toán.
Nhận xét:
Có ba khả năng có thể xảy ra:
Miền ràng buộc là tập rỗng.
Cực tiểu (cực đại) của f trên D bằng -∞ (+∞).
f đạt cực tiểu (cực đại) hữu hạn trên D.
b) Phân loại bài toán tối ưu
Quy hoạch tuyến tính
Quy hoạch phi tuyến
Quy hoạch tham số
Quy hoạch động
Quy hoạch lồi
Quy hoạch rời rạc
…
1.1.2 Một số ví dụ về QHTT
a) BT lập kế hoạch sx:
Một xí nghiệp dự định sx hai loại sản phẩm: S1 và S2. Để sx hai loại sp này xí nghiệp cần hai loại vật liệu V1 và V2. Các số liệu được cho bởi bảng:
Lập kế hoạch sx sao cho tổng thu lớn nhất.
Lập mô hình toán
Gọi x1, x2 là số đơn vị sp S1, S2 cần sx. Khi đó:
tổng thu là f(x)=50x1+30x2
Số V1 cần dùng: 4x1+3x2
Số V2 cần dùng: 5x1+2x2
Do đó ta có BT: Tìm x=(x1,x2) sao cho
Tổng quát
Nếu xí nghệp cần sx n sp từ m vật liệu
aij : số VL i cần để sx 1 đơn vị sp j
bi : lượng VL i mà xí nghiệp có
cj : lãi hay giá bán 1 đv sp j
xj : số đv sp j xí nghiệp nên sx
Khi đó ta có BT:
b) Bài toán vận tải:
Cần vận chuyển một loại mặt hàng nào đó từ m kho chứa A1, A2, …, Am với trữ lượng tương ứng là a1, a2, …, am (đv) đến n cửa hàng tiêu thụ B1, B2, …, Bn với nhu cầu tương ứng là b1, b2,…, bn (đv). Giả thiết Σbi= Σaj. Biết rằng cước vận chuyển 1 đv hàng từ Ai đến Bj là cil đv tiền.

Lập kế hoạch vận chuyển sao cho các điểm thu nhận đủ số hàng theo nhu cầu và tổng cước phí là nhỏ nhất.
Sơ đồ và mô hình bài toán
A1
a1
A2
a2
B1
b1
B2
b2
B3
b3
c11
c21
c12
c23
c22
c13
x13
x11
x12
x21
x23
x22
1.1.3. Bài toán QHTT
a) Dạng tổng quát:
b) Dạng chính tắc, chuẩn tắc
Dạng chính tắc:





Dạng chuẩn tắc:





Nhận xét: Ta có thể đưa một bài toán QHTT về dạng chính tắc, hoặc chuẩn tắc.



c) Dạng ma trận
Ký hiệu:
Ma trận hệ số: A=(aij)m×n
Ma trận cột thứ j : Aj=(aij)i=1..m
Ma trận cột biến số: x=(xj)j=1..n
Ma trận cột hệ số: c=(cj)j=1..n
Ma trận cột vế phải: b=(bi)i=1..m
Khi đó, dạng ma trận của BT QHTT chính tắc:
f(x)=ctx → min, hoặc f(x)=ctx → min,
Ax=b, ΣAjxj = b,
x≥0. x≥0.
Tương tự ta có dạng ma trận cho QHTT chuẩn tắc.
1.2. Cơ sở Giải tích lồi
1.2.1. Một số khái niệm trong Rn


1.2.2. Tính chất của bài toán QHTT
1.2.1. Một số khái niệm trong Rn
a. Tôpô trong Rn
- Điểm x=(x1, x2, …, xn) є Rn.
Tổ hợp tuyến tính, đltt và pttt.
Tổ hợp lồi.
Độ dài, chuẩn, khoảng cách, hình cầu.
Điểm biên, tập mở, tập đóng, tập giới nội.
Tích vô hướng.
Đường thẳng, đoạn thẳng, siêu phẳng, nửa không gian đóng, mở.
b. Tập hợp lồi
Định nghĩa: Một tập hợp CRn được gọi là lồi nếu 
x, yC, 0≤≤1  x+(1-)y C.
- Ví dụ: toàn không gian, siêu phẳng, các đa giác lồi trong R2, hình cầu, …
x
y
x
y
1.2.1. Một số khái niệm trong Rn
b. Tập hợp lồi
Tính chất của tập lồi:
+ Giao của các tập lồi là tập lồi.
+ Nếu C, D lồi thì C+D, C cũng lồi.
+ Bao đóng của tập lồi là tập lồi.
+ Tập hợp tất cả các tổ hợp lồi của một số hữu hạn điểm trong Rn là một tập lồi.
+ Cho CRn, tập lồi nhỏ nhất chứa C được gọi là bao lồi của C, ký hiệu là convC. Đó chính là tập tất cả các tổ hợp lồi của các điểm thuộc C.
c. Điểm cực biên
Định nghĩa: Điểm x0 C (C là tập lồi) là điểm cực biên của C nếu không tồn tại x,x” C; x’ ≠ x” sao cho x0 = x’+ (1-)x” với  nào đó thuộc (0,1).
Ví dụ: Đỉnh các đa giác lồi, các điểm nằm trên đường tròn,…
Nhận xét: Số điểm cực biên của một tập lồi có thể hữu hạn hay vô hạn. Nếu tập lồi không chứa biên thì không có điểm cực biên.
d. Phương vô hạn, phương cực biên
- Cho x0, v Rn, tập {x=x0+a.v, a≥0} gọi là tia xuất phát từ x0, phương v.
Tập lồi C được gọi là không giới nội nếu nó chứa các tia x+av với xC và với v0 nào đó. Vectơ v như vậy được gọi là một phương vô hạn của C.
Một phương vô hạn v của C được gọi là một phương cực biên nếu không tồn tại hai phương vô hạn khác v1v2 của C và hai số dương a, b sao cho: v=av1+bv2.
e. Tập lồi đa diện
Tập lồi đa diện là giao của hữu hạn các nửa không gian đóng. Tức là tập:
{xRn: Ax≤b, A=(aij)m×n, bRm}.
Một tập lồi đa diện giới nội còn được gọi là một đa diện lồi.
Mỗi điểm cực biên của một tập lồi đa diện còn được gọi là một đỉnh. Số đỉnh của một tập lồi đa diện là hữu hạn.
e. Tập lồi đa diện
Mệnh đề: Cho C là một tập lồi đa diện. Gọi u1,u2, …, um là các đỉnh và v1, v2, …,vp là các phương cực biên của C.
a) Nếu C là một đa diện lồi thì
C=conv{u1,u2, …, um}.
b) Nếu C không giới nội thì xC ta có
1.2.2. Tính chất của bài toán QHTT
a. Tính chất chung
Định lý 1:Tập D các phương án của một bài toán qui hoạch tuyến tính là một tập hợp lồi đa diện.

Định lý 2: Nếu một qui hoạch tuyến tính có ít nhất một phương án và hàm mục tiêu bị chặn dưới trong miền ràng buộc (đối với bài toán min) thì bài toán chắc chắn có phương án tối ưu.
Chứng minh:
1.2.2. Tính chất của bài toán QHTT
Định lý 3: Nếu x0 là một phương án tối ưu của bài toán qui hoạch tuyến tính dạng bất kì và nếu x1, x2 (x1 x2) là hai phương án thỏa mãn:
x0 = x1 + (1-)x2,
với 0<  < 1, thì x1, x2 cũng là các phương án tối ưu.

Chứng minh: (coi như bài tập)
1.2.2. Tính chất của bài toán QHTT
b. Phương án cực biên
Định nghĩa: Một phương án xD của bài toán QHTT mà đồng thời là đỉnh của D được gọi là một phương án cực biên.
Xét bài toán QHTT dạng chính tắc:
min{f(x)=: Ax=b, x≥0},
trong đó, A là ma trận cỡ m×n có hạng m.
Định lý 4: Phương án x0 = (x01, …, x0n) của bài toán QHTT dạng chính tắc là phương án cực biên khi và chỉ khi các vectơ cột Aj của ma trận A ứng với các thành phần x0j > 0 là độc lập tuyến tính.
Chứng minh:
Hệ quả 1: Số phương án cực biên của bài toán QHTT dạng chính tắc là hữu hạn.

Hệ quả 2: Số thành phần dương trong mỗi phương án cực biên của bài toán QHTT dạng chính tắc tối đa bằng m (rankA).
1.2.2. Tính chất của bài toán QHTT
Định nghĩa: Nếu một phương án cực biên có số thành phần dương đúng bằng m thì được gọi là một phương án cực biên không suy biến.
Ví dụ: Tìm tất cả các phương án cực biên của bài toán QHTT với hệ ràng buộc:
3x1 – 2x2 + 3x3 = 6,
-x1 + 2x2 - x3 = 4,
xj ≥ 0, j = 1, 2, 3.
Hướng dẫn: Xác định số thành phần dương của phương án cực biên, sau đó giải các hệ PTTT.
1.2.2. Tính chất của bài toán QHTT
Định lý 5: Nếu bài toán QHTT dạng chính tắc có ít nhất một phương án thì bài toán có phương án cực biên.
Chứng minh:

Định lý 6: Nếu bài toán QHTT dạng chính tắc có phương án tối ưu thì nó cũng có phương án cực biên tối ưu.
Chứng minh:
1.2.2. Tính chất của bài toán QHTT
Nội dung chính của chương 1
Khái niệm bài toán tối ưu, bài toán QHTT…

Dạng chính tắc, dạng chuẩn tắc, cách chuyển dạng của bài toán QHTT.

Các tính chất của bài toán QHTT.
Hết chương 1