Tài liệu Bài toán vận tải ba chỉ số (solid transport problem)

ĐỀ TÀI: Bài toán vận tải ba chỉ số (solid transport problem)

LỜI MỞ ĐẦU
Cùng với sự phát triển mạnh mẽ của khoa học kỹ thuật, các bài toán tối ưu xuất hiện ngày càng nhiều và tính phức tạp của chúng ngày càng lớn. Phạm vi và khả năng ứng dụng của các bài toán tối ưu cũng ngày càng đa dạng và phong phó.
Lớp bài toán tối ưu quan trọng được nghiên cứu đầu tiên và được ứng dụng nhiều nhất là bài toán quy hoạch tuyến tính (linear programming). Đó là mô h́nh toán học của một lớp rộng lớn các bài toán ứng dụng trong kinh tế và kỹ thuật. Do đó cấu trúc của lớp bài toán quy hoạch tuyến tính có nhiều tính chất rất tốt về mặt toán học, người ta đă t́m được các thuật giải rất hữu hiệu cho bài toán này. Năm 1947 nhà toán học Mỹ G.B. Dantzig đă nghiên cứu và đề xuất ra thuật toán đơn h́nh (simplex method) để giải bài toán quy hoạch tuyến tính. Thuật toán đơn h́nh được phát triển mạnh mẽ trong những năm sau đó và được xem là một phương pháp kinh điển để giải các bài toán quy hoạch tuyến tính. Đây là một phương pháp được sử dụng có thể nói là rộng răi nhất. Có ba lư do chính:
Một là: Rất nhiều vấn đề thực tế, trong nhiều lĩnh vực khác nhau có thể đưa về bài toán quy hoạch tuyến tính.
Hai là: Trong nhiều phương pháp giải các bài toán phi tuyến, bài toán tuyến tính xuất hiện nh­ là một bài toán phụ cần phải giải trong nhiều bước lặp.
Ba là: Phương pháp đơn h́nh là phương pháp hiệu quả để giải bài toán quy hoạch tuyến tính.
Ngày nay, bằng thuật toán đơn h́nh và các dạng cải biên của chúng, người ta có thể giải rất nhanh các bài toán QHTT cỡ lớn.
Lớp các bài toán vận tải là trường hợp đặc biệt của quy hoạch tuyến tính, bởi vậy có thể dùng các phương pháp của quy hoạch tuyến tính để giải. Tuy nhiên, do tính chất đặc thù riêng của nó, người ta xây dựng các phương pháp giải riêng.
Thông thường khi nói đến bài toán vận tải ta thường liên hệ ngay đến bài toán vận tải hai chỉ số, bởi đây là bài toán vận tải kinh điển có những phương pháp giải hay. Bên cạnh đó, người ta c̣n xét một số các bài toán vận tải mở rộng như bài toán vận tải ba chỉ số, bài toán vận tải khoảng, bài toán vận tải đa mục tiêu và rất nhiều bài toán khác, đó là các biến thể của bài toán vận tải kinh điển trên.
Trong khuôn khổ khoá luận này, em xem xét và nghiên cứu một số bài toán mở rộng trong lớp các bài toán vận tải mở rộng đó. Đó là các bài toán: Bài toán vận tải ba chỉ số (solid transport problem) không hạn chế và có hạn chế khả năng thông qua, Bài toán vận tải ba chỉ số khoảng (interval solid transport problem) và giới thiệu một số Bài toán vận tải đa mục tiêu.
Cuối cùng, em xin bày tỏ ḷng biết ơn sâu sắc nhất đối với thày giáo hướng dẫn Thạc sỹ Vũ Tiến Việt, người đă tận t́nh chỉ bảo, giúp đỡ em trong quá tŕnh hoàn thành khoá luận này. Em c̣ng xin chân thành cảm ơn sự giúp đỡ nhiệt t́nh của các thầy cô trong khoa Toán - Tin, Học viện An ninh Nhân dân.















CHƯƠNG I. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
Trong việc nghiên cứu các bài toán tối ưu nói chung, giải tích lồi giữ một vai tṛ rất quan trọng. Nó được sử dụng làm cơ sở toán học trong việc xây dựng các thuật toán.
Quy hoạch tuyến tính là một trong những lớp bài toán tối ưu được nghiên cứu trọng vẹn cả về phương diện lư thuyết lẫn thực hành, Bài toán vận tải là một dạng đặc biệt của QHTT. Do đó chương này nhằm giới thiệu một số khái niệm và kiến thức cơ bản về giải tích lồi và QHTT.
1.1 Một số khái niệm về giải tích lồi
1.1.1 Không gian Euclude
Mét vector n chiều trên trường số thực là một bộ được sắp thứ tự gồm n số thực x=(x[SUB]1[/SUB], x[SUB]2[/SUB], ., x[SUB]n[/SUB]). Các x[SUB]i[/SUB], i =1, ., n gọi là các thành phần hay toạ độ của vector. Ví dụ x=(4,5,10,20).
Hai vectơ x và y gọi là bằng nhau x=y, nếu x[SUB]i[/SUB]=y[SUB]i[/SUB], i =1, ., n.
Xét hai phép toán trên các vector:
Phép cộng: x+y=(x[SUB]1[/SUB]+y[SUB]1[/SUB], x[SUB]2[/SUB]+y[SUB]2[/SUB], ., x[SUB]n[/SUB]+y[SUB]n[/SUB])
Phép nhân: ax=(ax[SUB]1[/SUB], ax[SUB]2[/SUB], ., ax[SUB]n[/SUB]), a Î R
Khi đó tập hợp tất cả các vector n chiều trong đó xác định phép cộng các vector, nhân một số thực với vector như trên tạo thành không gian tuyến tính n chiều trên trường số thực R, kư hiệu R[SUP]n[/SUP].

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Các vector x[SUP](i)[/SUP] ÎR[SUP]n[/SUP], i =1, ., m được gọi là độc lập tuyến tính nếu:
Nếu: với Ưt nhất một a[SUB]i[/SUB] ¹ 0 th́ x gọi là tổ hợp tuyến tính của các x[SUP](i)[/SUP], i =1, ., m. Hơn nữa nếu a[SUB]i[/SUB] > 0, i =1, ., m và th́ x gọi là tổ hợp lồi của các x[SUP](i)[/SUP], i =1, ., m.
Trong R[SUP]n[/SUP] có n vector độc lập tuyến tính lập thành cơ sở của nó.
Giả sử e[SUP](1)[/SUP], e[SUP](2)[/SUP], ., e[SUP](n)[/SUP] là một cơ sở của R[SUP]n[/SUP] th́ bất kỳ một vector x Î R[SUP]n[/SUP] đều là tổ hợp tuyến tính của các vector e[SUP](1)[/SUP], e[SUP](2)[/SUP], ., e[SUP](n)[/SUP]. Ta gọi tích vô hướng của hai vector x=(x[SUB]1[/SUB], x[SUB]2[/SUB], ., x[SUB]n[/SUB]) và y=(y[SUB]1[/SUB], y[SUB]2[/SUB], ., y[SUB]n[/SUB]), kư hiệu, , là một số bằng.

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Tích vô hướng là một dạng song tuyến tính, đối xứng, không âm, tức là:
1. = . x,y Î R[SUP]n[/SUP]
2. (1) + x[SUP](2)[/SUP], y >=< x[SUP](1)[/SUP], y >+< x[SUP](2)[/SUP], y>. x[SUP](1)[/SUP], x[SUP](2)[/SUP], y Î R[SUP]n[/SUP]
3. <lx,y> = l. x,y Î R[SUP]n[/SUP]
4. ³ 0, xÎ R[SUP]n[/SUP] dấu bằng xẩy ra khi và chỉ khi x= 0.

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Độ dài của vector x=(x[SUB]1[/SUB], x[SUB]2[/SUB], ., x[SUB]n[/SUB]) là một số xác định bởi.

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Khoảng cách giữa hai vector x và y là một số xác định bởi:
Không gian vector trong đó có tích vô hướng và khoảng cách nh­ trên gọi là không gian Euclude.

1.1.2 Tập compact
Dăy {x[SUP](k)[/SUP] }̀R[SUP]n[/SUP] k=1, 2, . được gọi là có giới hạn x[SUP](0)[/SUP] khi k ® ¥ và viết

[TABLE]
[TR]
[TD][TABLE=width: 100%]
[TR]
[TD]k ® ¥
[/TD]
[/TR]
[/TABLE]
[/TD]
[/TR]
[/TABLE]
[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

lim x[SUP](k) [/SUP]= x[SUP](0)[/SUP], nếu
H́nh cầu tâm a bán kính r là tập S={xÎR[SUP]n[/SUP] :½x-a½£ r }. H́nh cầu này tạo nên r- lân cận của điểm a, hay gọi là lân cận của a.
* Nếu tập ÀR[SUP]n[/SUP] chứa cùng với điểm x một lân cận của nó th́ x gọi là điểm trong của A. Nếu trong lân cận bất kỳ của x Î A có các điểm của A và các điểm không thuộc A th́ x gọi là điểm biên của tập hợp A.
* Một tập ÀR[SUP]n[/SUP] gọi là giới nội nếu nó được chứa trong một h́nh cầu tâm O nào đó, tức là tồn tại số r đủ lớn sao cho với mọi xÎA,½x½£ r. Một dăy {x[SUP](k)[/SUP]} hội tụ th́ bao giờ cũng giới nội.
* Một tập hợp G̀R[SUP]n[/SUP] được gọi là mở nếu với mọi xÎG đều tồn tại một h́nh cầu tâm x nằm gọn trong G. Một tập F̀R[SUP]n[/SUP] được gọi là đóng nếu với mọi dăy hội tụ{x[SUP](k)[/SUP]}̀ F ta đều có:
Một tập chứa mọi điểm biên của nó là tập đóng.
* Tập C được gọi là tập Compact nếu từ mọi dăy vô hạn {x[SUP](k)[/SUP]} thuộc C đều có thể trích ra một dăy con {x[SUP](ki)[/SUP]} hội tụ tới phần tử thuộc C. Tập C là Compact khi và chỉ khi C đóng và giới nội. Tập Compact M của tập đóng C cũng đóng trong C. Tập con đóng M của tập Compact c̣ng Compact.
Hàm f(x) liên tục trên tập Compact C th́ sẽ đạt cực trị trên tập Êy.
1.1.3 Tập lồi
Cho hai điểm a, b ÎR[SUP]n[/SUP]. Ta gọi đường thẳng qua a, b là tập điểm có dạng
xÎR[SUP]n[/SUP] : x = la + (1-l)b, l Î R.
Đoạn thẳng nối hai điểm a, b là tập lồi các điểm có dạng
xÎR[SUP]n[/SUP] :x = lx + (1-l)y, 0 £ l £ 1
* Một tập M̀R[SUP]n[/SUP] được gọi là một đa tạp affine nếu với hai điểm bất kỳ
x, y ÎM th́ toàn bộ đường thẳng đi qua hai điểm đó cũng thuộc M.
Tức là lx + (1-l)y ÎM : x,y ÎM, lÎR.
* Một siêu phẳng trong không gian R[SUP]n[/SUP] là tập hợp tất cả các điểm
x=(x[SUB]1[/SUB], x[SUB]2[/SUB], ., x[SUB]n[/SUB]) ÎR[SUP]n[/SUP] thỏa măn phương tŕnh tuyến tính
a[SUB]1[/SUB]x[SUB]1[/SUB]+ a[SUB]2[/SUB]x[SUB]2[/SUB]+ . + a[SUB]n[/SUB]x[SUB]n[/SUB] = a trong đó a[SUB]1[/SUB], a[SUB]2[/SUB], ., a[SUB]n[/SUB] , a ÎR
* Tập hợp các điểm x=(x[SUB]1[/SUB], x[SUB]2[/SUB], ., x[SUB]n[/SUB]) ÎR[SUP]n[/SUP] thoản măn bất phương tŕnh tuyến tính a[SUB]1[/SUB]x[SUB]1[/SUB]+ a[SUB]2[/SUB]x[SUB]2[/SUB]+ . + a[SUB]n[/SUB]x[SUB]n[/SUB] £ a được gọi là nửa không gian đóng.
* Nửa không gian được cho bởi a[SUB]1[/SUB]x[SUB]1[/SUB]+ a[SUB]2[/SUB]x[SUB]2[/SUB]+ . + a[SUB]n[/SUB]x[SUB]n[/SUB] < a được gọi là nửa không gian mở.
* Tập X̀R[SUP]n [/SUP]được gọi là tập lồi nếu cùng với việc chứa hai điểm x, y nó chứa cả đoạn thẳng chứa hai điểm Êy, tức là chứa tất cả các điểm có dạng:
lx + (1-l)y, 0 £ l £ 1
Ví dụ về các tập lồi: Không gian Euclide, các nửa không gian, mặt phẳng, nửa mặt phẳng, h́nh chữ nhật, h́nh vuông, h́nh elip, h́nh hộp, h́nh cầu .
* Một tập hợp là giao của một số hữu hạn các nửa không gian đóng được gọi là tập lồi đa diện.
Mệnh đề: Giao của hai tập lồi là một tập lồi.

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Hệ quả 1. Giao của một số bất kỳ tập hợp lồi là tập lồi.
Hệ quả 2. Miền chứa nghiệm của một hệ bất phương tŕnh tuyến tính dạng.
là một tập lồi (đa diện lồi). Một tập lồi đa diện giới nội gọi là một đa diện. Giao của tất cả các tập lồi chứa tập X gọi là bao lồi của nó, kư hiệu [X]
1.1.4 Hàm lồi
* Một hàm số f(x) xác định trên tập lồi C ̀ R[SUP]n [/SUP]được gọi là hàm lồi trên C, nếu với mọi x, y ÎC và 0 £ l £ 1 ta có f(lx + (1-l)y) £lf(x) + (1-l)f(y).
* Hàm f(x) được gọi là hàm lồi chặt nếu với mọi x, y ÎC và 0 £ l £ 1 ta có. f(lx + (1-l)y) < lf(x) + (1-l)f(y).
* Hàm f(x) được gọi là hàm lơm (lơm chặt) nếu - f(x) là hàm lồi (lồi chặt)
* Hàm f(x) xác định trên C đạt cực tiểu tuyệt đối tại x* ÎC nếu
f(x[SUP]*[/SUP]) £ f(x): xÎC
* Hàm f(x) đạt cực tiểu địa phương tại x* Î C nếu tồn tại lân cận mở U của x* sao cho f(x*) £ f(x): xÎC ÇU
Mệnh đề 1: Bất kỳ điểm cực tiểu địa phương nào của hàm lồi trên tập lồi cũng là điểm cực tiểu tuyệt đối.
Hệ quả: Bất kỳ điểm cực đại địa phương nào của hàm lơm cũng là cực đại tuyệt đối.
Mệnh đề 2: Cực đại của một hàm lồi (nếu có) trên một tập lồi có điểm cực biên bao giờ cũng đạt tại một điểm cực biên.
1.2 Bài toán Quy hoạch tuyến tính
QHTT bắt nguồn từ những nghiên cứu của nhà toán học Nga nổi tiếng, Viện sỹ L.V. Kantorovich trong một loạt các công tŕnh về bài toán kế hoạch hoá sản xuất, công bố năm 1938. Năm 1947 nhà toán học Mỹ G.B. Dantzig đă nghiên cứu và đề xuất phương pháp đơn h́nh (Simplex method) để giải bài toán QHTT. Năm 1952 phương pháp đơn h́nh đă được chạy trên máy tính điện tử của Mỹ.
1.2.1 Bài toán quy hoạch tuyến tính
v Bài toán tổng quát.

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Để nhất quán lập luận ta xét bài toán t́m cực đại, sau đó ta xét cách chuyển bài toán t́m cực tiểu sang t́m cực đại. Bài toán tổng quát của QHTT có dạng:
Kư hiệu: A=(a[SUB]ij[/SUB])[SUB]mxn[/SUB] là ma trận với các phần tử a[SUB]ij[/SUB]

(1.1) gọi là hàm mục tiêu, (1.2) là các rằng buộc.
Nếu gặp bài toán Min, tức là

[TABLE=align: left]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]



Th́ giữ nguyên ràng buộc và đưa về bài toán Max bằng cách


Nếu bài toán Max có phương án tối ưu là x* th́ bài toán min cũng có phương án là x* và f[SUB]min[/SUB]=-`f[SUB]max[/SUB]
Thật vậy, v́ x* là phương án tối ưu của bài toán Max nên ta có:




Chứng tá x* là phương án tối ưu của bài toán Min và

[TABLE=align: left]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]



v Dạng chuẩn và dạng chính tắc.
Người ta thường xét bài toán quy hoạch tuyến tính dưới hai dạng sau:
-Dạng chuẩn:

[TABLE=align: left]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]






-Dạng chính tắc:

[TABLE=align: left]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]






v Đưa bài toán QHTT về dạng chuẩn hoặc dạng chính tắc.
Bất kỳ QHTT nào cũng có thể đưa về một trong hai dạng chuẩn hoặc chính tắc nhờ các phép biến đổi tuyến tính sau:
i) Một ràng buộc


[TABLE=align: left]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]


Có thể đưa về ràng buộc bằng cách nhân hai vế với (-1) và viết lại
ii) Một ràng buộc đẳng thức




[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

có thể thay bằng hai ràng buộc bất đẳng thức:

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

iii) Một biến x[SUB]j[/SUB] không bị ràng buộc dấu có thể thay thế bởi hiệu của hai biến không âm bằng cách đặt:
iv) Một ràng buộc bất đẳng thức

[TABLE=align: left]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]



[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Có thể đưa về ràng buộc đẳng thức bằng cách đưa vào biến phụ y[SUB]i[/SUB] ³ 0:

[TABLE=align: left]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]



Về nguyên tắc, áp dụng nhiều lần các phép biến đổi (i), (ii) và (iii) ta có thể đưa một bài toán QHTT bất kỳ về dạng chuẩn, sau đó áp dụng nhiều lần phép biến đổi (iv) ta sẽ đưa nó về dạng chính tắc.
v Giải bài toán QHTT bằng phương pháp h́nh học.

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Xét bài toán QHTT dưới dạng chuẩn với hai biến số:
Từ ư nghĩa h́nh học ta biết rằng mỗi bất phương tŕnh tuyến tính a[SUB]i1[/SUB]x[SUB]1[/SUB]+a[SUB]i2[/SUB]x[SUB]2 [/SUB]£ b[SUB]i[/SUB] xác định một nửa mặt phẳng.
Nh­vậy miền ràng buộc D được xác định nh­ là giao của một nửa mặt phẳng và sẽ là một đa giác lồi trên mặt phẳng. Phương tŕnh c[SUB]1[/SUB]x[SUB]1[/SUB]+c[SUB]2[/SUB]x[SUB]2[/SUB]=a khi a thay đổi sẽ xác định trên mặt phẳng các đường thẳng song song với nhau mà ta sẽ gọi là các đường mức (với giá trị mức a). Mỗi điểm ÎD sẽ nằm trên một đường mức với mức
Bài toán đặt ra có thể phát biểu theo ngôn ngữ h́nh học như sau: trong số các đường mức cắt tập D, hăy t́m đường mức với gía trị lớn nhất.
Nếu dịch chuyển song song các đường mức theo hướng vector pháp tuyến của
chóng th́ giá trị mức sẽ tăng, nếu dịch chuyển theo hướng ngược lại th́ giá trị mức sẽ giảm. V́ vậy để giải bài toán đặt ra, ta có thể tiến hành nh­ sau.
Bắt đầu từ một đường mức cắt D, ta dịch chuyển song song các đường mức theo hướng vector pháp tuyến (c[SUB]­1­[/SUB],c[SUB]2[/SUB]) cho đến khi việc dịch chuyển tiếp theo làm cho đường mức không c̣n cắt D nữa th́ dừng. Điểm của D (có thể nhiều điểm) nằm trên đường mức cuối cùng này sẽ là lời giải tối ưu cần t́m, c̣n giá trị của hàm mục tiêu tại đó chính là giá trị tối ưu của bài toán.
Ví dụ: Xét bài toán:

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

f(x)= 4x[SUB]1[/SUB]+5x[SUB]2[/SUB]®max
Xét đường mức: 4x[SUB]1[/SUB]+5x[SUB]2[/SUB]=10. Đường mức này đi qua hai điểm (0,2) và (2.5,0). Ta có x*=(3,2), f[SUB]max[/SUB]=22

[TABLE=align: left]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]








và x* là một đỉnh của D. Qua phương pháp h́nh học ta thấy rằng:
- Nếu quy hoạch tuyến tính có phương án tối ưu th́ có Ưt nhất một đỉnh là tối ưu. Sở dĩ nói Ưt nhất v́ có trường hợp đường mức ở vị trí giới hạn trùng với một cạnh của D th́ tất cả các điểm trên cạnh này là phương án tối ưu, trong đó có hai đỉnh.
- Nếu miền ràng buộc D giới nội và khác rỗng th́ chắc chắn có phương án tối ưu.
- Nếu miền ràng buộc không giới nội nhưng hàm mục tiêu bị chặn trên ở trên miền ràng buộc th́ cũng chắc chắn có phương án tối ưu.
1.2.2 Một số tính chất chung
Mệnh đề 1: Tập hợp tất cả các phương án của một bài toán QHTT là tập lồi.
Tập lồi D các phương án của một bài toán QHTT xác định bởi toàn bộ các ràng buộc (1.2) và (1.3). Tập D có thể là rỗng, hoặc là một đa diện lồi hoặc là một tập lồi đa diện không giới nội.
Nếu D là một đa diện lồi th́ bài toán có phương án, hơn nữa giá trị tối ưu của hàm mục tiêu trên đa diện lồi là hữu hạn và việc t́m phương án tối ưu đưa đến việc chọn các điểm của đa diện D có số đỉnh (điểm cực biên hay phương án cực biên) hữu hạn.
Mệnh đề 2: Hàm mục tiêu của bài toán QHTT sẽ đạt Max tại điểm cực biên của tập D. Nếu hàm mục tiêu không chỉ nhận Max tại một điểm cực biên của tập lồi D mà tại nhiều điểm cực biên th́ nó sẽ đạt giá trị cực đại tại những điểm là tổ hợp lồi của các điểm đó.
Kư hiệu A[SUB]j[/SUB], j=1, ., n là các vector cột của ma trận A.
Khi Êy hệ ràng buộc Ax =b có thể viết:
x[SUB]1[/SUB]A[SUB]1[/SUB] + x[SUB]2[/SUB]A[SUB]2[/SUB] + . + x[SUB]n[/SUB]A[SUB]n[/SUB] = b (1.4)
Mệnh đề 3: Nếu các vector A[SUB]1[/SUB], A[SUB]2[/SUB], ., A[SUB]k[/SUB] là độc lập tuyến tính và thoả măn
x[SUB]1[/SUB]A[SUB]1[/SUB]+x[SUB]2[/SUB]A[SUB]2[/SUB]+ .+x[SUB]n[/SUB]A[SUB]n[/SUB]=b
trong đó x[SUB]j [/SUB]> 0, j=1, .k th́ điểm
x=(x[SUB]1[/SUB],x[SUB]2[/SUB], .,x[SUB]k[/SUB],0, .,0)
là điểm cực biên của tập lồi đa diện D.
Mệnh đề 4: Nếu x =(x[SUB]1[/SUB],x[SUB]2[/SUB], .,x[SUB]n[/SUB]) là điểm cực biên của tập lồi đa diện D th́ các vector A[SUB]j[/SUB] trong biểu diễn (1.4) ứng với các thành phần x[SUB]j [/SUB]> 0 lập thành hệ độc lập tuyến tính. V́ ma trận A có m ḍng nên từ đây suy ra rằng điểm cực biên không có quá m thành phần dương.
Các mệnh đề 3 và mệnh đề 4 có thể gộp lại thành một mệnh đề sau:
Mệnh đề 5: Để x =(x[SUB]1[/SUB],x[SUB]2[/SUB] .,x[SUB]n[/SUB]) là phương án cực biên của QHTT dưới dạng chính tắc th́ cần và đủ là các vector cột A[SUB]j[/SUB] của ma trận A ứng với các thành phần x[SUB]j [/SUB]> 0 là độc lập tuyến tính.
1.2.3 Phương pháp đơn h́nh giải bài toán QHTT
Cơ sở của phương pháp này đươc G.B. Dantzig công bố năm 1947 có tên gọi là phương pháp đơn h́nh. Sở dĩ có tên gọi nh­ vậy là v́ những bài toán đầu tiên được giải bằng phương pháp đó có các ràng buộc dạng:

Mà tập hợp các điểm xÎR[SUP]n[/SUP] thoả măn các ràng buộc trên là một đơn h́nh trong không gian n chiều.
v Đường lối chung và cơ sở của thuật toán.
i) Đường lối chung.
Phương pháp đơn h́nh dựa trên hai nhận xét sau: nếu bài toán QHTT có phương án tối ưu, đa diện lồi D có một số hữu hạn đỉnh. Nh­ vậy phải tồn tại thuật toán hữu hạn. Thuật toán gồm hai giai đoạn:
- Giai đoạn 1: T́m một phương án cực biên (một đỉnh).
- Giai đoạn 2: Kiểm tra điều kiện tối ưu đối phương án t́m được ở giai đoạn 1. Nếu điểu kiện tối ưu được thoả măn th́ phương án đó là tối ưu. Nếu không, ta chuyển sang phương án cực biên mới sao cho cải tiến giá trị hàm mục tiêu. Tiếp theo lại kiểm tra điều kiện tối ưu đối với phương án mới.
Người ta thực hiện một dăy các thủ tục như vậy cho đến khi nhận được phương án tối ưu, hoặc đến t́nh huống bài toán không có phương án tối ưu.
ii) Cơ sở của thuật toán.
Xét bài toán QHTT dưới dạng chính tắc:
< c, x > ® max (1.6)
Ax = b (1.7)
x ³ 0 (1.8)
Trong đó A là ma trận kích thước mxn và giả sử rằng hạng của ma trận A là m (điều này không làm mất tính tổng quát). x là một vector.
Giả sử x là một phương án cực biên nào đó. Ta kư hiệu:
J* = {j| x[SUB]j [/SUB]> 0} (1.9)
V́ các vector A[SUB]j[/SUB], jÎJ* là độc lập tuyến tính nên |J*| £ m (|J*| là sè sè phần tử
x[SUB]j[/SUB] >0).
* Phương án cực biên x được gọi là không thoái hoá nếu | J* |= m, thoái hoá nếu |J*| < m.
Ta chọn một hệ thống m vector độc lập tuyến tính {A[SUB]j[/SUB], j Î J}sao cho J Ê J*. Hệ thống đó gọi là cơ sở của x, các vector {A[SUB]j[/SUB], j Î J} và các biến {x[SUB]j[/SUB], j Î J} được gọi là các vector và các biến cơ sở tương ứng. Các vector và các biến A[SUB]j[/SUB], x[SUB]j[/SUB], jÏ J gọi là các vector và các biến phi cơ sở tương ứng.
Nếu x không thoái hoá th́ tồn tại một cơ sở duy nhất, đó là J=J*.
Mỗi vector A[SUB]k [/SUB] phi cơ sở có thế biểu diễn dưới dạng tổ hợp tuyến tính của các vector cơ sở:

Trong đó các hệ số z[SUB]jk[/SUB] được xác định duy nhất bởi việc giải hệ phương tŕnh:

[TABLE=align: left]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]



Bài toán QHTT được gọi là không thoái hoá nếu tất cả các phương án cực biên của nó đều không thoái hoá.
Giả sử bài toán không thoái hoá và ta đă t́m được một phương án cực biên x=(x[SUB]1[/SUB], x[SUB]2[/SUB], .x[SUB]m[/SUB], 0, .0) và cơ sở của nó A[SUB]1,[/SUB], A[SUB]2[/SUB], .A[SUB]m[/SUB].
Đối với phương án cực biên này ta có:

[TABLE=align: left]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]



với giá trị của hàm mục tiêu:

Ta tính các đại lượng sau:


Kí hiệu:

Định lư 1.1: (Tiêu chuẩn tối ưu). Nếu đối với phương án cực biên x=(x[SUB]1[/SUB],x[SUB]2[/SUB], .,x[SUB]m[/SUB],0 .0) các điều kiện sau được thỏa măn

[TABLE=align: left]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]


th́ x* là phương án tối ưu.
Chó ư:
· Trong (1.10) nếu A[SUB]j[/SUB] là một vector cơ sở, khi đó tồn tại chỉ một hệ số z[SUB]jj[/SUB]=1, tất cả các hệ số khác đều bằng 0 và ta có:

[TABLE=align: left]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]


và trong thực hành để kiểm tra điều kiện tối ưu của phương pháp cực biên x ta chỉ cần kiểm tra
D[SUB]k [/SUB]³ 0, kÏJ (1.18)
· Người ta có thể chứng minh rằng nếu bài toán không thoái hoá th́ (1.16) cũng là điều kiện cần của tối ưu.
Định lư 1.2: Nếu tồn tại một chỉ số k sao cho D[SUB]k [/SUB]< 0 th́ người ta có thể t́m được Ưt nhất một phương án x’ mà đối với nó Z’> Z[SUB]0[/SUB].

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Công thức t́m phương án x’:
Nhân (1.10) với q nào đó ta có:

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Lấy (1.12) trừ đi (1.19) từng vế ta có:

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Nếu các hệ số của các vector A[SUB]j[/SUB], j=1, .,m và A[SUB]k[/SUB] trong (1.20) không âm, khi đó ta có một phương án mới x’ mà đối với nó hàm mục tiêu f có giá trị
Trong (1.12) tất cả các biến x[SUB]j[/SUB], j=1, .,m đều dương. V́ vậy có thể t́m được q > 0 sao cho

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Nếu đối với chỉ số k mà D[SUB]k [/SUB]< 0, tồn tại z[SUB]jk[/SUB]> 0, jÎJ th́ giá trị q lớn nhất c̣n thoả măn (1.22) có thể xác định bởi hệ thức :


Nếu ta thay q trong (1.20) và (1.21) bởi q[SUB]o[/SUB] th́ thành phần thứ r sẽ bằng 0:
x[SUB]r[/SUB]­- q[SUB]o[/SUB]z[SUB]rk[/SUB]=0.
Nh­ vậy ta nhận được phương án mới x’ với cơ sở A[SUB]j[/SUB], jÎJ {r}È{k}=J’.
Nếu z[SUB]jk [/SUB]£ 0, jÎ J th́ tất cả các thành phần x[SUB]j[/SUB]- q z[SUB]jk[/SUB] trong (1.22) sẽ không âm q >0, nghĩa là ta luôn có phương án q >0, nhưng từ (1.21) ta dễ thấy giá trị hàm mục tiêu tiến tới +¥ khi q tiến tới +¥.

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Trong thực hành Dantzig đă chứng minh rằng các bước lặp sẽ giảm đáng kể nếu ta thay vector A[SUB]s[/SUB] thoả măn:

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

và khi đó vector A[SUB]r [/SUB]được xác định theo công thức:
Ta có phương án cực biên mới x’ mà các thành phần của nó có dạng:
nếu j ¹ r
nếu j=r

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

và cơ sở của nó là
Trên cơ sở lư thuyết đă nhận được, ta chuyển sang xét thuật toán đơn h́nh.
v Thuật toán đơn h́nh
Giả sử ta đă đưa QHTT về dạng chính tắc:

cx=Z® max
Ax=b
x³0
Bước 1: Xây dựng bảng đơn h́nh xuất phát. T́m một phương án cực biên xuất phát x và cơ sở của nó A[SUB]j[/SUB], jÎJ.
·
[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Xác định các số z[SUB]jk[/SUB] bởi hệ phương tŕnh:
·
[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Đối với mỗi k Ï J , tính các ước lượng:
C̣n với jÎJ th́ D[SUB]j [/SUB]= 0.
·
[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Tính giá trị hàm mục tiêu
Bước 2: Kiểm tra tối ưu.
Nếu D[SUB]k [/SUB]³ 0, k Ï J th́ x là phương án tối ưu, dừng thuật toán. Trái lại, chuyển sang bước 3.
Bước 3: T́m vector đưa vào cơ sở. Có hai khả năng xảy ra:
· Tồn tại kÏJ sao cho D[SUB]k[/SUB]< 0 và z[SUB]jk [/SUB]£ 0, jÎJ th́ bài toán QHTT không có lời giải tối ưu (Z không bị chặn trên). Dừng thuật toán.
·
[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Đối với mỗi kÏJ sao cho D[SUB]k[/SUB]< 0 đều tồn tại j Î J: z[SUB]jk[/SUB]> 0. Khi đó chọn chỉ số s theo tiêu chuẩn:
Đưa vector A[SUB]s[/SUB] vào cơ sở.

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Bước 4: T́m vector loại khỏi cơ sở. Xác định
Và đưa vector A[SUB]r [/SUB]ra khỏi cơ sở.
Bước 5: Chuyển sang phương án cực biên mới và cơ sở mới. Cơ sở mới là {A[SUB]j[/SUB],j ÎJ’} với J’= J{r} È z{s}. Phương án cực biên mới x’ được tính theo (1.26), khai
triển của các véc tơ A[SUB]k[/SUB] theo các cơ sở mới được tính theo công thức (1.28). Quay lên bước 2.

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]

Chó ư. Đối với bài toán min th́ tiêu chuẩn tối ưu là D[SUB]k[/SUB]£ 0 (k) và vector A[SUB]s[/SUB] được chọn đưa vào cơ sở theo công thức:
v Công thức đổi cơ sở và bảng đơn h́nh.
Ta xét các công thức chuyển từ phương án cực biên x với cơ sở J sang phương án cực biên x’ với cơ sở J’.

[TABLE]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD]
[/TD]
[/TR]
[/TABLE]