Bài toán quy hoạch nguyên, thuật toán gomory và ứng dụng trong cắt thép xây dựng

ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
VÀ TRUYỀN THÔNG

HOÀNG QUANG HƯNG

BÀI TOÁN QUY HOẠCH NGUYÊN, THUẬT TOÁN
GOMORY VÀ ỨNG DỤNG TRONG CẮT THÉP XÂY DỰNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên 2015

ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
VÀ TRUYỀN THÔNG

HOÀNG QUANG HƯNG

BÀI TOÁN QUY HOẠCH NGUYÊN, THUẬT TOÁN
GOMORY VÀ ỨNG DỤNG TRONG CẮT THÉP XÂY DỰNG
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƯỜI HƯỚNG DẪN KHOA HỌC
TS. NGUYỄN HẢI MINH

Thái Nguyên 2015

LỜI CAM ĐOAN
Tôi xin cam đoan luận văn “Bài toán quy hoạch nguyên, thuật toán
Gomory và ứng dụng trong cắt thép xây dựng” là công trình nghiên cứu do tôi
thực hiện dưới sự hướng dẫn của TS. Nguyễn Hải Minh và TS. Vũ Vinh Quang.
Các nội dung được trình bày trong luận văn là những kết quả đạt được trong thời tôi
gian thực đề tài dưới sự hướng của tập thể giáo viên hướng dẫn, tôi không sao chép
nguyên bản lại kết quả của các nghiên cứu đã từng được công bố và đây cũng là kết
quả của quá trình nghiên cứu, học tập và làm việc nghiêm túc của tôi trong quá trình
học cao học. Bên cạch đó, trong một số nội dung luận văn là kết quả phân tích,
nghiên cứu, tổng hợp từ nhiều nguồn tài liệu khác. Các thông tin tổng hợp hay các
kết quả lấy từ nhiều nguồn tài liệu khác đã được tôi trích dẫn một cách đầy đủ và
hợp lý. Nguồn tài tài liệu tham khảo có xuất xứ rõ ràng và được trích dẫn hợp pháp.
Các số liệu và thông tin sử dụng trong luận văn này là trung thực.
Thái Nguyên, ngày

tháng

năm 2015

Người cam đoan

Hoàng Quang Hưng

LỜI CẢM ƠN
Tôi xin chân thành cảm ơn các thầy, cô trong Viện Công nghệ thông tin,
Trường Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên đã
tham gia giảng dạy, giúp đỡ tôi trong suốt quá trình học tập nâng cao trình độ kiến
thức để phục vụ cho công tác giảng dạy của tôi hiện tại và sau này.
Tôi xin bày tỏ lòng biết ơn chân thành tới TS. Nguyễn Hải Minh và TS.Vũ Vinh
Quang, các Thầy đã tận tình hướng dẫn hướng dẫn tôi trong suốt thời gian thực hiện luận
văn.
Vì điều kiện thời gian và trình độ có hạn nên luận văn cũng không thể tránh
khỏi những thiếu sót. Tôi xin kính mong các Thầy, Cô giáo, các bạn đồng nghiệp
đóng góp ý kiến để đề tài được hoàn thiện hơn.
Tôi xin chân thành cảm ơn!

i

MỤC LỤC

MỞ ĐẦU ................................................................................................................ 1
NỘI DUNG ............................................................................................................. 2
Chương 1
CÁC KIẾN THỨC CƠ BẢN VỀ BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ......... 3
1.1. Mô hình tổng quát về bài toán quy hoạch tuyến tính ..................................... 3
1.1.1. Giới thiệu bài toán quy hoạch tuyến tính ................................................. 3
1.1.2. Bài toán tổng quát ................................................................................... 3
1.1.3. Dạng chuẩn và dạng chính tắc ................................................................ 4
1.1.4. Đưa quy hoạch tuyến tính về dạng chuẩn hoặc dạng chính tắc ................ 4
1.2. Thuật toán đơn hình ...................................................................................... 5
1.2.1. Đường lối chung và cơ sở của thuật toán ................................................ 6
1.2.2. Cơ sở của thuật toán ............................................................................... 6
1.2.3. Thuật toán đơn hình ................................................................................ 8
1.2.4. Công thức đổi cơ sở, bảng đơn hình........................................................ 9
1.3. Lý thuyết đối ngẫu ...................................................................................... 12
1.3.1. QHTT dưới dạng chuẩn, cặp bài toán tuyến tính đối ngẫu đối xứng ...... 12
1.3.2. Ý nghĩa cặp bài toán đối ngẫu ............................................................... 15
1.3.3. Phương pháp đơn hình đối ngẫu từ vựng .............................................. 15
Chương 2
BÀI TOÁN QUY HOẠCH NGUYÊN VÀ THUẬT TOÁN GOMORY ................ 19
2.1. Mô hình tổng quát ....................................................................................... 19
2.2. Một số mô hình thực tế ............................................................................... 20
2.2.1. bài toán với điều kiện không chia cắt được ........................................... 20
2.2.2. Bài toán với điều kiện logic .................................................................. 20
2.2.3. Bài toán với biến số rời rạc ................................................................... 21
2.2.4. Bài toán với vốn đầu tư ban đầu............................................................ 21
2.3. Cơ sở lý thuyết về thuật toán nhát cắt Gomory ............................................ 22

ii

2.3.1. Tư tưởng ............................................................................................... 22
2.3.2. Khái niệm lát cắt đúng .......................................................................... 24
2.3.3. Tư tưởng phương pháp cắt Dantzig....................................................... 24
2.4. Thuật toán Gomory giải bài toán quy hoạch nguyên ................................... 25
2.4.1. Thuật toán Gomory thứ nhất ................................................................. 25
2.4.2. Thuật toán Gomory thứ hai ................................................................... 36
2.4.3. Thuật toán Gomory thứ ba .................................................................... 44
Chương 3
CÀI ĐẶT BÀI TOÁN CẮT THÉP TRONG XÂY DỰNG .................................... 60
3.1. Đánh giá thuật toán Gomory ....................................................................... 60
3.2. Ứng dụng giải bài toán cắt thép trong xây dựng .......................................... 61
3.2.1 Mô hình bài toán thực tế ........................................................................ 61
3.2.2 Mô hình toán học ................................................................................... 61
3.2.3 Thuật toán giải bài toán ......................................................................... 61
3.3. Cách sử dụng chương trình.......................................................................... 64
3.3.1. Các biến sử dụng trong chương trình .................................................... 64
3.3.2. Cách sử dụng chương trình ................................................................... 64
3.4. Kết quả cài đặt ............................................................................................ 65
KẾT LUẬN ........................................................................................................... 71
TÀI LIỆU THAM KHẢO ..................................................................................... 72
PHẦN PHỤ LỤC .................................................................................................. 73

1

MỞ ĐẦU

Kể từ khi máy vi tính xuất hiện thì công nghệ thông tin và toán học luôn là
hai lĩnh vực song song cùng phát triển. Trước đây, việc giải các bài toán, đặc biệt là
các bài toán phức tạp thường tốn rất nhiều thời gian và công sức, thì ngày nay, việc
giải các bài toán đó, có thể diễn ra nhanh chóng trên máy vi tính bằng cách sử dụng
các thuật giải. Việc giải các bài toán một cách nhanh chóng trên máy tính không
những giúp cho toán học phát triển mà nó còn giúp cho rất nhiều ngành khác cùng
phát triển theo. Một trong các lĩnh vực của toán học thường ứng dụng công nghệ
thông tin để giải quyết đó là các bài toán về quy hoạch tuyến tính. Mô hình bài toán
quy hoạch tuyến tính là một mô hình đã được phát triển từ rất lâu. Trong mô hình
tổng quát, đã xuất hiện rất nhiều các thuật toán nổi tiếng để xác định phương án tối
ưu như, thuật toán đơn hình gốc của Dantzig, thuật toán đơn hình cải biên hay thuật
toán đối ngẫu. Trong mô hình bài toán tổng quát nếu thêm vào điều kiện ràng buộc
là các nghiệm của bài toán phải thỏa mãn nguyên, thì chúng ta nhận được bài toán
quy hoạch nguyên. Do tính chất nguyên của nghiệm nên bài toán quy hoạch nguyên
có rất nhiều ứng dụng trong thực tế, như bài toán vận tải, bài toán lập lịch biểu, bài
toán cái túi, bài toán pha cắt vật tư…Để tìm nghiệm của bài toán quy hoạch nguyên
thì thuật toán Gomory đóng vai trò quan trọng đặc biệt là trong công nghệ thông tin.
Nhận thấy tính thiết thực của vấn đề này và được sự gợi ý của giảng viên
hướng dẫn, tôi đã chọn đề tài “Bài toán quy hoạch nguyên, thuật toán Gomory và
ứng dụng trong cắt thép xây dựng” làm đề tài cho luận văn tốt nghiệp của mình.

2

NỘI DUNG
Chương 1: Chương này trình bày nhưng kiến thức cơ bản về quy hoạch
tuyến tính, bài toán tổng quát, dạng chuẩn và dạng chính tắc của bài toán quy hoạch
tuyến tính. Cách đưa bài toán về dạng chuẩn hoặc dạng chính tắc. thuật toán đơn
hình giải bài toán quy hoạch tuyến tính.
Chương 2: Chương này trình bày về bài toán quy hoạch nguyên, một số bài
toán trong thực tế. Cơ sở lý thuyết của ba thuật toán Gomory để giải bài toán quy
hoạch nguyên.
Chương 3: Chương này là kết quả cài đặt bài toán cắt thép trong xây dựng
dựa vào thuật toán Gomory.

3

Chương 1

CÁC KIẾN THỨC CƠ BẢN VỀ BÀI TOÁN QUY HOẠCH TUYẾN
TÍNH
1.1. Mô hình tổng quát về bài toán quy hoạch tuyến tính
1.1.1. Giới thiệu bài toán quy hoạch tuyến tính
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ọn vẹn cả về phương diện lý thuyết lẫn thực hành.
Quy hoạch tuyến tính 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ĩ Kantorovich L.V được nêu trong một loạt công trình về bài toán kế
hoạch hóa sản xuất, công bố năm 1938. Năm 1947 nhà toán học Mỹ Dantzig đã
nghiên cứu và đề xuất phương án đơn hình để giải bài toán quy hoạch tuyến tính.
Năm 1952 phương pháp đơn hình đã được chạy trên máy tính điện tử ở Mỹ.
Quy hoạch tuyến tính là lĩnh vực toán học nghiên cứu các bài toán tối ưu mà
hàm mục tiêu và các ràng buộc đều là hàm và các phương trình hoặc bất phương
trình tuyến tính.
Các bước nghiên cứu và ứng dụng một bài toán quy hoạch tuyến tính điển
hình như sau:
- Xác định vấn đề cần giải quyết, thu thập dữ liệu.
- Lập mô hình toán học.
- Xây dựng các thuật toán để giải bài toán đã mô hình hóa bằng ngôn ngữ
thuận lợi cho việc lập trình cho máy tính.
- Tính toán thử và điều chỉnh mô hình nếu cần.
- Áp dụng giải các bài toán thực tế.
1.1.2. Bài toán tổng quát
Ta xét bài toán tìm cực đại, sau đó ta sẽ 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 quy hoạch tuyến tính có dạng:

4

n

å

c j x j ® max

j= 1

ìï n
ïï
å aij x j (£ , = , ³ )bi , i = 1,m
D ïí j = 1
ïï
ïïî x j ³ 0, j = 1, n
Nếu gặp bài toán min tức là:
n

f (x ) =

å

c j x j ® min

j= 1

xÎ D

thì giữ nguyên ràng buộc ta đưa nó về dạng bài toán max:
n

f (x ) = -

å

c j x j ® max

j= 1

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 tối ưu là x * và. fmin = - f m ax .
1.1.3. Dạng chuẩn và dạng chính tắc
người ta xét quy hoạch tuyến tính dưới 2 dạng sau đây:
Dạng chuẩn
n

å

Dạng chính tắc
n

c j x j ® max

j= 1

å

c j x j ® max

j= 1

ìï n
ïï
ïí å aij x j £ bi , i = 1,m
j= 1
ïï
x
ïïî j ³ 0, j = 1,n

ìï n
ïï
ïí å a ij x j = bi , i = 1,m
j= 1
ïï
x
ïïî j ³ 0, j = 1, n

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

5

n

1. Một ràng buộc

å

n

aij x j ³ bi có thể đưa về ràng buộc -

j= 1

å

a ij x j £ - bi

j= 1
n

å

bằng cách nhân hai vế với (-1), và viết lại

aij' x j ³ bi'

j= 1
n

å

2. Một ràng buộc đẳng thức

aij x j = bi , có thể thay thế bằng 2 ràng buộc

j= 1
n

bất đẳng thức:

å

n

aij x j £ bi ;

-

j= 1

å

aij x j £ - bi

j= 1

3. Một biến x j không bị ràng buộc dấu có thể thay thế bởi hiệu của 2 biến
không âm bằng cách đặt: x j = x j+ - x -j vơi x j+ ³ 0 và x -j ³ 0
n

4. Một ràng buộc bất đẳng thức

å

aij x j £ bi có thể đưa về ràng buộc đẳng

j= 1

thức bằng cách đưa vào biến phụ y i ³ 0
n

å

aij + y i = bi

j= 1

Về nguyên tắc, áp dụng nhiều lần các phép biến đổi 1, 2 và 3 ta có thể đưa
một quy hoạch tuyến tính bất kỳ về dạng chuẩn, sau đó áp dụng nhiều lần phép biến
đổi 4 ta sẽ đưa nó về dạng chính tắc.
1.2. Thuật toán đơn hình
Cơ sở của phương pháp này được 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 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:
n

å

x j = 1, x j > 0, j = 1, n

j= 1

mà tập các điểm x Î R n thỏa mãn các ràng buộc trên là một đơn hình trong không
gian n chiều.

6

1.2.1. Đường lối chung và cơ sở của thuật toán
Đườ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 quy hoạch tuyến tính có phương án tối ưu thì có ít nhất một
đỉnh của D là 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 một thuật toán hữu hạn. Thuật toán gồm 2 giai đoạn:
- Giai đoạn I: Trước hết tìm một phương án cực biên (một đỉnh).
- Giai đoạn II: Kiểm tra điều kiện tối ưu với phương án đó.
- Nếu điều kiện tối ưu được thỏa 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
- 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.
1.2.2. Cơ sở của thuật toán
Xét bài toán quy hoạch tuyến tính dưới dạng chính tắc.

< c, x > ® m ax
ìï Ax = b
ï
í
ïï x ³ 0
î
Trong đó A là ma trận kích thước m ´ n 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).
Giả sử x là một phương án cực biên nào đó.
Ta ký hiệu: J * = { j | x j > 0}
Vì rằng các vectơ A j , j Î J * là độc lập tuyến tính nên | J * | £ m
 Định nghĩa: Phương án cực biên x được gọi là không thoái hóa nếu

| J * |= m , thoái hóa nếu | J * |< m .

7

Ta chọn một hệ thống m vectơ độc lập tuyến tính Î {A j , j Î J } sao cho

j Ê J * . Hệ thống đó là cơ sở của x , các vectơ A j , j Î J và biến x j , j Î J được
gọi là các vectơ và các biến cơ sở tương ứng. Các vectơ và các biến A j , x j ( j Ï J )
gọi là vectơ và các biến phi cơ sở.
Nếu x không thoái hóa thì tồn tại một cơ sở duy nhất, đó là j = J * .
Mọi vectơ Ak phi cơ sở có thể biểu diễn dưới dạng tổ hợp tuyến tính của các
vectơ cơ sở:
Ak =

å

z jk A j

jÎ J

Trong đó các hệ số z ik được xác định duy nhất bởi việc giải hệ phương trình

a jk =

å

z jka ij , i = 1,m

jÎ J

Bài toán quy hoạch tuyến tính được gọi là không thoái hóa nếu tất cả các
phương án cực biên của nó đều không thoái hóa.
giả sử bài toán không thoái hóa và ta đã tìm được một phương án cực biên

x = (x 1, x 2 , ..., x m , 0, ..., 0) và cơ sở của nó A1, A2, ..., Am .
Đối với phương án cực biên này ta có:
m

å

x j A j = b, x j > 0, j = 1, m

j= 1

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

å

c j x j = z 0, x j > 0, j = 1, m

j= 1

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

å
j= 1

Ký hiệu:

z jkc j = z k

8

m

D k = z k - ck =

å

z jkc j - ck

j= 1

 Định lý 1: Nếu đối với phương án cực biên

x = (x 1, x 2 , ..., x m , 0, ..., 0)
Các điều kiện sau được thỏa mãn

Vk ³ 0, " k = 1, n
thì x là phương án tối ưu.
 Định lý 2: Nếu tồn tại một chỉ số k sao cho Vk < 0 thì ta có thể tìm được ít
nhất một phương án x ' mà đối với nó z ' > z .
1.2.3. Thuật toán đơn hình
Giả sử ta đã đưa quy hoạch tuyến tính về dạng chính tắc:

cx = z (max)

ìï A x = b
ï
í
ïï x ³ 0
î
Giai đoạn 1: Tìm một phương án cực biên xuất phát x và cơ sở của nó

Aj , j Î J
Giai đoạn 2: xác định các số z jk bởi hệ thống Ak =

å

z jk A j

jÎ J

Đối với mỗi k Ï J tính các ước lượng : D k =

å

z jkc j - ck

jÎ J

1) Nếu ( " k Ï J ) D k ³ 0 Þ

x là nghiệm tối ưu. Dừng.

2) Nếu không x không phải là nghiệm tối ưu.
- ( $ k Ï J ) D k < 0 và z jk £ 0, " j Î J Þ bài toán quy hoạch tuyến tính
không có nghiệm tối ưu ( z không bị chặn trên). Dừng thuật toán.
- Đối với mỗi k Ï J sao cho D k < 0 , đều tồn tại j Î J : z jk > 0 Þ chọn

D s = min {D k | D k < 0}

9

Đưa vectơ As vào cơ sở.

ìï x
ü
ï
x
j
ï
Xác định: q = min í
| z js > 0ïý = r
ïï z rs
ïï
z rs
î
þ
Đưa vectơ Ar ra khỏi cơ sở. Ta được phương án cực biên mới x ' với
cơ sở J ' = J \ {r } È {s } . Quay trở lại khởi đầu của giai đoạn 2.
1.2.4. Công thức đổi cơ sở, 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 ' .

ìï
ïï x - x r z nÕu j ¹ r
ï j z js'
rs
Ta có công thức x j' = ïí
ïï x r
nÕu j = r
ïï
ïïî z rs
Bây giờ ta thiết lập công thức tính các số z jk
Ta có:

As =

å

z ij A j Þ

1
(A z rs s

Ar =

jÎ J

å

(1.1)

z js A j )

jÎ J
j¹ r

Mặt khác: Ak =

å

(1.2)

(z jk A j + z rk Ar )

jÎ J

Thay biểu thức của Ar từ (1.1) vào (1.2) ta có

Ak =

å

z jk A j +

jÎ J

z rk
(A z rs s

å

z js A j )

jÎ J
j¹ r

Ak =

å
jÎ J
j¹ r

( z jk A j -

z rk
z
z js )A j + sk
z rs
z rs

Đây là công thức biểu diễn Ak qua cơ sở mới J ' = J \ {r } È {s } . bởi vậy ta
có:

10

z 'jk

ìï
ïï z - z rk z , nÕu j ¹ r
ï jk z js
rs
= ïí
ïï z rk
, nÕu j = r
ïï
ïïî z rs

Sau khi có z jk ta tính: D k' =

å

z'jkc j - ck

jÎ J

Để dễ tính toán trong mỗi bước lặp ta thiết lập bảng đơn hình
 Nếu tất cả các số trong dòng cuối (trừ f ) đều ³ 0, nghĩa là D k ³ 0 " k , khi
đó x là phương án tối ưu.
 Nếu dòng cuối không (kể f ) có những số âm thì xem thử có cột nào cắt
dòng cuối ở một số âm mà mọi số trong cột đó đều £ 0 hay không ?
- Nếu có thì bài toán không có phương án tối ưu.
- Nếu không thì chọn cột s sao cho D s = min {D k | D k < 0}
rồi chọn trong số những dòng cắt cột s ở những số dương dòng r mà tỉ số

qr =

x
xr
= min{ j | z js > 0}
z rs
z js

Cột s gọi là cột xoay, vectơ A đưa vào cơ sở.
Dòng r gọi là dòng xoay. Vectơ A , bị đưa ra khỏi cơ sở.
Phần tử z rs > 0 là giao của cột xoay và dòng xoay gọi là phần tử trục. Các
phần tử z js , j ¹ r gọi là phẩn tử xoay.
Theo các công thức :

ìï
ïï x - x r z nÕu j ¹ r
ï j z js'
rs
x j' = ïí
ïï x r
nÕu j = r
ïï
ïïî z rs

A j , j Î J ' = J \ {r } È {s }
D k' =

å
jÎ J

z jk' c j - ck

11

gọi là các công thức đổi cơ sở
bảng đơn hình mới được suy từ bảng cũ bằng cách thay cr , Ar trong dòng
xoay bằng cs , As . Sau đó thực hiện phép biến đổi dưới đây:
1) Chia mỗi phần tử dòng xoay cho phần tử trục (được số 1 ở vị trí trục), kêt
quả thu được gọi là dòng chính.
2) Lấy mỗi dòng khác trừ đi tích của dòng chính nhân với phần tử xoay
tương ứng (được số 0 ở mọi vị trí còn lại của cột xoay).
Dòng mới = dòng cũ tương ứng - dòng chính ´ phần tử xoay.
Lưu ý rằng sau phép xoay thì ở vị trí D s ta thu được số 0 vì lúc này As trở
thành vectơ đơn vị cơ sở, nghĩa là ta đã làm mất số âm nhỏ nhất ở dòng cuối của
bảng cũ.
Toàn thể phép biến đổi trên gọi là phép xoay xung quanh trục z rs . Sau khi
thực hiện phép xoay ta có một phương án mới và một cơ sở mới . Nếu chưa đạt yêu
cầu nghĩa là còn D k <0 thì ta lại tiếp tục quá trình.
Chú ý : trong bảng đơn hình ở bảng 1.1, không giảm tổng quát ta coi các
vectơ cơ sở được đánh số A1, A2, ..., Am nghĩa là: J = {1, 2, ...m }

12

bảng 1.1
Cơ
sở

Phương
án

c1

c2 ...

c j ...

cr ...

cm ...

ck

... cs

... cn

A1

A2 ...

A j ...

Ar ...

Am ...

Ak

... As

... An

A1

x1

1

0 ...

0...

0...

0

z 1k

... z 1s

... z 1n

c2 . A 2

x2

0

1

0

0

0

z 2k

... z 2s

... z 2n

.

.
.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Aj .

xj

0

0

1

0

0

z jk

... z js

... z jn

.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

cr

Ar

xr

0

0

1

0

0

z rk

... z rs

... z m

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

cm

Am

xm

0

0

0

0

1

z mk

.. z ms

.
.
...

cj

c1

.
cj . .

.

z mn

f

0

0 ...

0...

0...

0 ...

Dk

... D s

... D n

1.3. Lý thuyết đối ngẫu
Ta chứng tỏ ở đây rằng đối với mọi bài toán quy hoạch tuyến tính ta có thể
thiết lập tương ứng cho nó một bài toán khác gọi là bài toán đối ngẫu của nó. Khái
niệm đối ngẫu là một trong các khái niệm cơ bản của quy hoạch tuyến tính. Trong
rất nhiều trường hợp để có được những kết luận chấp nhận được cho một trong các
bài toán trên thì việc nghiên cứu bài toán đối ngẫu của nó lại tỏ ra thuận tiện hơn.
Hơn nữa khi ta phân tích song song một cặp bài toán đối ngẫu ta có thể nhận được
những kết luận hay cả về toán học cả về ý nghĩa kinh tế.
1.3.1. QHTT dưới dạng chuẩn, cặp bài toán tuyến tính đối ngẫu đối xứng
 Định nghĩa 1. Cho QHTT dưới dạng chuẩn.

< c, x > = z (min)

13

ìï A x ³ b
( p) ïí
ïï x ³ 0
î
Ta gọi đối ngẫu của nó là bài toán QHTT dạng:

< b, y > = w(max)

ìï A y £ c
( p) ïí
ïï y ³ 0
î
Ở đây A là ma trận chuyển vị của A , y là vectơ cột.
Ta chú ý rằng các biến đổi ngẫu tương ứng một – một với các ràng buộc của
quy hoạch ban đầu (mà ta sẽ gọi là quy hoạch gốc), trong khi những ràng buộc của
bài toán đối ngẫu tương ứng một – một các biến của quy hoạch gốc. Điều đó thể
hiện rõ trong sơ đồ sau:
x1
x2
x 3 ... x n

y1

a11

a12

a13

... a1n



y2
.
ym

a21
....
am 1

a21

a22

... a

am 2

am 3 ... amn

 b2
.

bm

/

/

/

c1

c2

c3

2n

b1

min
... cn

max

Khi đọc theo hàng của sơ đồ này ta được các ràng buộc (ngoài x ³ 0 ) và
hàm mục tiêu của quy hoạch gốc.
Khi đọc theo cột ta được các ràng buộc (ngoài y  0 ) và hàm mục tiêu của
quy hoạch đối ngẫu.
Ví dụ: quy hoạch đối ngẫu của bài toán

8x 1  7x 2  3x 3  z (min)

ìï 2x + x ³ 4
ïï 1
2
ïí x + 2x + x ³ 5
2
3
ïï 1
ïï x 1, x 2 , x 3 ³ 0
î

14

là quy hoạch

4y 1 + 5y 2 = W (max)

ìï 2y + y
2
ïï 1
ïï y + 2y
2
ïí 1
ïï
y3
ïï
ïïî y 1, y 2

£ 8
£ 7
£ 3
³ 0

 Định lý 1. Cho ( p) và ( p ' ) là một cặp quy hoach tuyến tính đối ngẫu:

< c, x > = z (min)
ìï A x ³ b
( p) ïí
ïï x ³ 0
î

< b, y > = W (max)
ìï A 'y £ c
( p' ) ïí
ïï y ³ 0
î

Đối với mọi cặp phương án chấp nhận được x , y tương ứng của ( p) và ( p ' ) ta có:

< b, y > £ < c, x >
Hệ quả: Nếu x là các phương án chấp nhận được tương ứng của cặp quy
hoạch tuyến tính đối ngẫu ( p ) và nếu < c, x'>   b, y  thì :
(1) < c, x'> = < b, y >
(2) x và y là các phương án tối ưu tương ứng của ( p ) và ( p ’).
 Định lý 2. Cho 1 quy hoạch tuyến tính.
- Nếu nó có phương án chấp nhận được thì nó có phương án cực biên.
- Nếu nó có phương án tối ưu thì nó có phương án cực biên tối ưu.
- Nếu nó có phương án chấp nhận được và nếu giá trị hàm mục tiêu chặn
(chặn trên nếu là bài toán cực đại hoá, chặn dưới nếu là bài toán cực tiểu hoá), thì nó
có phương án cực biên tối ưu.
 Định lý 3. Nếu 2 QHTT đối ngẫu ( p ) và ( p ’) đều có phương án chấp nhận
được thì chúng đều có phương án tối ưu và giá trị tối ưu của các hàm mục tiêu bằng
nhau.