Bài giảng môn Quy hoạch tuyến tính | Trường Đại học Công nghiệp Thành phố Hồ Chí Minh

Bài giảng môn Quy hoạch tuyến tính | Trường Đại học Công nghiệp Thành phố Hồ Chí Minh. Tài liệu gồm 141 trang giúp bạn tham khảo, củng cố kiến thức và ôn tập đạt kết quả cao trong kỳ thi sắp tới. Mời bạn đọc đón xem!

Môn:
Thông tin:
141 trang 5 tháng trước

Bình luận

Vui lòng đăng nhập hoặc đăng ký để gửi bình luận.

Bài giảng môn Quy hoạch tuyến tính | Trường Đại học Công nghiệp Thành phố Hồ Chí Minh

Bài giảng môn Quy hoạch tuyến tính | Trường Đại học Công nghiệp Thành phố Hồ Chí Minh. Tài liệu gồm 141 trang giúp bạn tham khảo, củng cố kiến thức và ôn tập đạt kết quả cao trong kỳ thi sắp tới. Mời bạn đọc đón xem!

47 24 lượt tải Tải xuống
Quy hoạch
tuyến tính
Nguyễn Đức Phương
TP. HCM, Ngày 4 tháng 1 năm 2016
Bài giảng đang được chỉnh sửa
Bài giảng
Bảng hiệu
R Tập số thực
A Ma trận hệ số vế phải của các ràng buộc
b Vector hệ số vế phải
c Vector hệ số hàm mục tiêu
x Phương án chấp nhận được
N
x Phương án tối ưu
x
T
Phép chuyển vị
jAj Định thức ma trận A
Œx
T
Tọa độ của vector theo x theo sở T
A
j
Cột j của ma trận hệ số A
e
j
Vector đơn vị thứ j
j
ước lượng của vector cột A
j
hxI yi Tích hướng của x y
B D fA
k
1
I : : : I A
k
m
g Hệ vector liên kết
c
B
D fc
k
1
I : : : I c
k
m
g Hệ số hàm mục tiêu chỉ số k
1
; : : : ; k
m
B Ma trận các cột các vector của B
A
B
j
Biểu diễn cột A
j
theo sở B
Mục lục
Mục lục ii
1 Giới thiệu quy hoạch tuyến tính 1
1.1 Một số dụ . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Các dạng bài t oán quy hoạch tuyến tính . . . . . . . . . . 5
1.2.1 Dạng tổng quát . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Dạng chuẩn . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Dạng chính t ắc . . . . . . . . . . . . . . . . . . . . 6
1.3 Chuyển bài toán quy hoạch sang dạng chính tắc . . . . . 8
1.3.1 Đổi chiều bất đẳng thức của các ràng buộc . . . . . 8
1.3.2 Biến không ràng buộc . . . . . . . . . . . . . . . . . 9
1.3.3 Chuyển dạng chuẩn sang chính tắc . . . . . . . . . 10
1.4 Dạng ma trận của bài toán quy hoạch . . . . . . . . . . . 13
1.5 Phương án chấp nhận được . . . . . . . . . . . . . . . . . . 14
1.6 Ý nghĩa hình học . . . . . . . . . . . . . . . . . . . . . . . 16
1.6.1 Phương pháp đồ thị . . . . . . . . . . . . . . . . . . 16
1.6.2 Tính chất của t ập phương án chấp nhận được . . . 19
1.7 Phương án cực biên . . . . . . . . . . . . . . . . . . . . . . 21
1.7.1 Thành lập phương án bản chấp nhận . . . . . . 23
1.7.2 Thành lập phương án cực biên . . . . . . . . . . . . 27
1.7.3 Tìm phương án tối ưu từ phương án cực biên . . . 30
1.8 Bài tập chương 1 . . . . . . . . . . . . . . . . . . . . . . . . 32
2 Phương pháp đơn hình 34
2.1 Phương pháp đơn hình cho bài toán chính tắc . . . . . . . 34
2.1.1 Phương pháp đơn hình . . . . . . . . . . . . . . . . 34
2.1.2 Dấu hiệu tối ưu . . . . . . . . . . . . . . . . . . . . 36
2.1.3 Thành lập phương án cực biên mới . . . . . . . . . 38
2.2 Bảng đơn hình . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.3 Thuật toán đơn hình cho bài toán min . . . . . . . . . . . 52
2.4 Bài toán chính tắc khôn g sẵn ma trận đơn vị . . . . . . 53
Trang iii Mục lục
2.5 Bài tập chương 2 . . . . . . . . . . . . . . . . . . . . . . . . 59
3 Lý thuyết đối ngẫu 64
3.1 Định nghĩa bài toán đối ngẫu . . . . . . . . . . . . . . . . 64
3.1.1 Đối ngẫu của bài to án max . . . . . . . . . . . . . . 68
3.1.2 Đối ngẫu của bài to án min . . . . . . . . . . . . . . 71
3.2 Các định v đối ngẫu . . . . . . . . . . . . . . . . . . . . 74
3.3 Phương án tố i ưu của bài toán đối ngẫu . . . . . . . . . . 81
3.3.1 Biết phương án tối ưu bài toán gốc . . . . . . . . . 81
3.3.2 bảng đơn hình của phương án tối ưu . . . . . . 85
3.4 Bài tập chương 3 . . . . . . . . . . . . . . . . . . . . . . . . 89
4 Bài toán vận tải 93
4.1 Bài toán vận tải cân bằng thu phát . . . . . . . . . . . . . 93
4.2 Phương án cực biên . . . . . . . . . . . . . . . . . . . . . . 95
4.3 Thành lập phương án cực biên . . . . . . . . . . . . . . . . 98
4.3.1 Phương pháp cước phí thấp nhất . . . . . . . . . . 98
4.3.2 Phương pháp góc y - Bắc . . . . . . . . . . . . . 100
4.3.3 Phương pháp Vogel (Fo gel) . . . . . . . . . . . . . . 102
4.4 Thuật toán thế vị giải bài toán vận tải . . . . . . . . . . . 104
4.4.1 Thuật toán quy không cước phí ô chọn . . . . . . . 104
4.4.2 y dựng phương án cực biên mớ i . . . . . . . . . 109
4.5 Một số trường hợp đặc biệt . . . . . . . . . . . . . . . . . . 114
4.5.1 Bài toán vận tải không cân bằng thu phát . . . . . 114
4.5.2 Bài toán vận tải ô cấm . . . . . . . . . . . . . . . 116
4.6 Bài toán vận tải cực đại cước phí . . . . . . . . . . . . . . 117
4.7 Bài tập chương 4 . . . . . . . . . . . . . . . . . . . . . . . . 118
A Đề thi mẫu 121
A.1 Đề học III năm 2010-2011 . . . . . . . . . . . . . . . . . 121
A.2 Đề học I năm 2011-2012 . . . . . . . . . . . . . . . . . . 122
A.3 Đề thi học kỳ II năm 2011-2012 . . . . . . . . . . . . . . . 123
A.4 Đề học III năm 2011-2012 . . . . . . . . . . . . . . . . . 124
B Bài giải đề mẫu 126
B.1 Bài giải học III năm học 2010-2011 . . . . . . . . . . . 126
B.2 Bài giải học I năm học 2011-2012 . . . . . . . . . . . . 129
B.3 Bài giải học II năm học 2011-2012 . . . . . . . . . . . . 132
B.4 Bài giải học III năm học 2011-2012 . . . . . . . . . . . 135
Tài liệu tham khảo 137
Chương 1
Giới thiệu quy hoạch tuyến
tính
Mục lục chương 1
1.1 Một số dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Các dạng bài toán quy hoạch tuyến tính . . . . . . . . . 5
1.3 Chuyển bài toán quy hoạch sang dạng chính tắc . . . . 8
1.4 Dạng ma trận của bài toán quy hoạch . . . . . . . . . . . 13
1.5 Phương án chấp nhận được . . . . . . . . . . . . . . . . . 14
1.6 Ý nghĩa hình học . . . . . . . . . . . . . . . . . . . . . . . . 16
1.7 Phương án cực biên . . . . . . . . . . . . . . . . . . . . . . 21
1.8 Bài tập chương 1 . . . . . . . . . . . . . . . . . . . . . . . . 32
1.1 Một số dụ dẫn đến i toá n quy hoạch
tuyến tính
dụ 1.1 (Bài t oán lập kế ho ạch sản xuất). Một trại cưa cưa các khúc
gỗ thành các tấm ván. h ai loại ván: ván thành phẩm ván sử dụng
trong y dựng. Giả sử, đối với:
Ván t h ành phẩm cần 2 giờ để cưa 5 giờ để bào 10m ván.
Ván dùng trong y dưng cần 3 giờ để cưa 3 giờ để bào 10m
ván.
1.1 Một số dụ Trang 2
y cưa làm việc tối đa 8 giờ trong ngày, y bào làm việc tối đa 15
giờ trong ngày. Nếu lợi nhuận của 10m ván th ành phẩm 120 (ngàn
đồng), và lợi nhuận của 10m ván y dựng 100 (ngàn đồng). Trong
ngày, trại cưa phải cưa bao nhiêu ván mỗi loại để lợi nhuận lớn nhất?
Giải. Gọi x
1
; x
2
0 lượng ván thành phẩm và ván sử dụng trong y
dựng.
Thời gian
Loại
Thành phẩm - x
1
y dựng - x
2
Cưa 2 3 8
Bào 5 3 15
Lợi nhuận 120 100
Tổng lợi nhu ận
z D 120 x
1
C 100x
2
! max
khi đó x
1
; x
2
thỏa điều kiện thời gian làm việc y cưa
2x
1
C 3x
2
8
và điều kiện về th i gian làm việc y bào
5x
1
C 3x
2
15
Tóm lại cần tìm x
1
; x
2
sao cho
z D 120 x
1
C 100x
2
! max
Với các ràng buộc
2x
1
C 3x
2
8
5x
1
C 3x
2
15
x
1
0; x
2
0
dụ 1.2 (Bài toán khẩu phần ăn). Chuyên gia dinh dưỡng định thành
lập một thực đơn gồm 2 loại thực phẩm chính A B. Cứ một (trăm
gram):
Thực phẩm A chứa 2 đơn vị chất béo, 1 đơn vị carbohydrate 4
đơn vị protein.
Thực phẩm B chứa 3 đơn vị chất béo, 3 đơn vị carbohydrate 3
đơn vị protein.
Trang 3 Chương 1. Giới thiệu quy hoạch tuyến tính
Nếu một (trăm gram) thực phẩm A giá 20 (ngàn đồng) một (trăm
gram) thực phẩm B giá 25 (ngàn đồng). Nhà dinh dưỡng muốn thức ăn
phải cung cấp ít nhất 18 đơn vị chất béo, 12 đơn vị carbohydrate và 24
đơn vị protein. Bao nhiêu (trăm gram) thực phẩm mỗi loại để giá nhỏ
nhất nhưng vẫn cung cấp đủ dinh dưỡng?
Giải. Gọi x
1
; x
2
lần lượt lượng thực phẩm A B.
Thành phần
Loại
TP
A - x
1
TP B - x
2
Chất béo 2 3 18
Carbohydrate 1 3 12
Protein 4 3 24
Giá mua 20 25
tổng số tiền mua x
1
; x
2
thực phẩm A và B
z D 20x
1
C 25x
2
! min
Yêu cầu lượng thực phẩm phải đảm bảo nhu cầu chất béo
2x
1
C 3x
2
18
nhu cầu Carbohydrate
x
1
C 3x
2
12
nhu cầu Protein
4x
1
C 3x
2
24
Vy ta cần tìm x
1
; x
2
sao cho
z D 20x
1
C 25x
2
! min
Với các ràng buộc
8
<
:
2x
1
C 3x
2
18
x
1
C 3x
2
12
4x
1
C 3x
2
24
x
1
0; x
2
0
dụ 1.3 (Bài toán vận tải). Một nhà sản xuất 2 nhà y: Một nhà
y Vĩnh Phúc một nhà y Bình Dương. 3 kho hàng phân
phối sản phẩm đặt Nội, TP. HCM và Cần Thơ. Nhà y Vĩnh
TP: Thực phẩm
1.1 Một số dụ Trang 4
phúc; Bình Dương, khả năng cung cấp t i đa 100; 140 tấn mỗi tuần.
Lượng cầu của các kho Nội, TP. HCM Cần Thơ lần lượt từ 100;
60 80 t ấn trở lên. Chi phí vận chuyển (trăm ngàn) mỗi tấn cho như
bảng bên dưới. Hỏi cần vận chuyển bao nhiêu tấn hàng hóa từ nhà sản
xuất đến các kho hàng Nội, TP. HCM cần thơ để chi phí nhỏ
nhất nhưng vẫn đáp ứng đủ nhu cầu?
Trạm phát
Trạm thu
Nội TP. HCM Cần Thơ
W
1
:100 W
2
:60 W
3
:80
Vĩnh Phúc-Q
1
: 100 5 7 9
Bình Dươn g-Q
2
:140 8 7 10
Giải. Gọi x
ij
lượng hàng vận chuyển từ trạm phát thứ i I i D 1; 2 đến
trạm thu thứ j I j D 1; 2; 3: Tổng chi phí vận chuyển
z D x
11
C x
12
C C x
23
! min
Trạm phát thì phát hết hàng trạm thu thì nhận đủ hàng:
Trạm phát 1 phát hết hàng
x
11
C x
12
C x
13
D 100
Trạm phát 2 phát hết hàng
x
21
C x
22
C x
23
D 140
Trạm thu 1 thu đủ hàng x
11
C x
21
D 100
Trạm thu 2 thu đủ hàng
x
12
C x
22
D 60
Trạm thu 3 thu đủ hàng x
13
C x
23
D 80
Vy ta cần tìm x
ij
sao cho
z D x
11
C x
12
C C x
23
! min
Với các ràng buộc
8
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
<
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
:
x
11
C x
12
C x
13
D 100
x
21
C x
22
C x
23
D 140
x
11
C x
21
D 100
x
12
C x
22
D 60
x
13
C x
23
D 80
x
ij
0 i D 1; 2I j D 1; 2; 3
Trang 5 Chương 1. Giới thiệu quy hoạch tuyến tính
1.2 Các dạng i toá n quy hoạch tuyến tính
1.2.1 Dạng tổng quát
Từ các dụ mục 1.1, bài toán quy hoạch tuyến tính dạng tổng quát
được phát biểu như sau:
z D c
1
x
1
C c
2
x
2
C C c
n
x
n
! max .hay min/ (1.1)
Với các ràng buộc
8
ˆ
ˆ
ˆ
<
ˆ
ˆ
ˆ
:
a
11
x
1
C a
12
x
2
C C a
1n
x
n
./.D/ b
1
a
21
x
1
C a
22
x
2
C C a
2n
x
n
./.D/ b
2
:
:
:
:
:
:
:
:
:
:
:
:
a
m1
x
1
C a
m2
x
2
C C a
mn
x
n
./.D/ b
m
(1.2)
Hàm tuyế n tính (1.1) gọi hàm mục tiêu.
Hệ bất phương trình, bất phương trình tuyến tính (1.2) gọi các
ràng buộc. Vế trái của các ràng buộc các hàm tuyến t ính v i
x
1
; x
2
; : : : ; x
n
các biến số.
1.2.2 Dạng chuẩn
Ta nói bài toán quy hoạch tuyến tính dạng chuẩn nếu dạng
như sau:
z D c
1
x
1
C c
2
x
2
C C c
n
x
n
! max; .hay min/ (1.3)
Với các ràng buộc
8
ˆ
ˆ
ˆ
<
ˆ
ˆ
ˆ
:
a
11
x
1
C a
12
x
2
C C a
1n
x
n
b
1
a
21
x
1
C a
22
x
2
C C a
2n
x
n
b
2
:
:
:
:
:
:
:
:
:
:
:
:
a
m1
x
1
C a
m2
x
2
C C a
mn
x
n
b
m
(1.4)
x
j
0; j D 1; 2; : : : ; n (1.5)
1.2 Các dạng bài toán quy hoạch tuyến tính Trang 6
1.2.3 Dạng chính tắc
Ta nói bài t oán quy hoạch tuyến tính dạng chính tắc
nếu dạng
như sau:
z D c
1
x
1
C c
2
x
2
C C c
n
x
n
! max; .hay min/ (1.6)
Với các ràng buộc
8
ˆ
ˆ
ˆ
<
ˆ
ˆ
ˆ
:
a
11
x
1
C a
12
x
2
C C a
1n
x
n
D b
1
a
21
x
1
C a
22
x
2
C C a
2n
x
n
D b
2
:
:
:
:
:
:
:
:
:
:
:
:
a
m1
x
1
C a
m2
x
2
C C a
mn
x
n
D b
m
(1.7)
x
j
0; j D 1; 2; : : : ; n (1.8)
dụ 1.4. Nhận dạng các bài toán quy hoạch tuyến tính sau:
a. z D 3x
1
C 2x
2
! min
Với các ràng buộc
2x
1
C x
2
4
3x
1
2x
2
6
x
1
0; x
2
0
dạng chuẩn.
b. z D 2x
1
C 3x
2
C 4x
3
! max
Với các ràng buộc
8
<
:
3x
1
C 2 x
2
3x
3
4
2x
1
C 3 x
2
C 2x
3
6
3x
1
x
2
C 2x
3
8
x
1
0; x
2
0; x
3
0
dạng t ng quát
.
c. z D 3x
1
C 2x
2
C 3x
3
2x
4
! max
Với các ràng buộc
8
<
:
2x
1
C 6 x
2
C 2x
3
4x
4
D 7
3x
1
C 2 x
2
5x
3
C x
4
D 8
6x
1
C 7 x
2
C 2x
3
C 5x
4
4
x
1
0; x
2
0; x
3
0; x
4
0
dạng t ng quát.
Một số sách định nghĩa khác về dạng chuẩn dạng chính tắc. Các bạn c ần đọc
kỹ định nghĩa khi tham khảo các tài liệu khác.
thể dễ dàng chuyển sang dạng chính tắc bằng cách nhân hai vế ràng buộc thứ
3 với 1
Trang 7 Chương 1. Giới thiệu quy hoạch tuyến tính
d. z D 2x
1
C 5x
2
C x
3
C x
4
C 4x
5
! min
Với các ràng buộc
3x
1
C 2x
2
x
3
C 2 x
5
D 4
4x
1
C 5x
2
C 3x
3
C 2x
4
D 7
x
1
0; x
2
0; x
3
0; x
4
0; x
5
0
dạng chính tắc.
e. z D 2x
1
C 5x
2
! max
Với các ràng buộc
3x
1
C 2x
2
6
2x
1
C 9x
2
8
x
1
0
dạng t ng quát.
f. z D 2x
1
C 3x
2
! min
Với các ràng buộc
8
<
:
2x
1
C x
2
x
3
D 4
3x
1
C 2x
2
C x
3
D 8
x
1
x
2
D 6
x
1
0; x
2
0
dạng t ng quát
Chú ý. Bài toán tìm giá tr nhỏ nhất của hàm mục tiêu thể viết
thành bài toán tìm giá tr lớn nhất của hàm mục tiêu và ngược lại bằng
quan h :
max
n
X
j D1
c
j
x
j
D min
0
@
n
X
j D1
c
j
x
j
1
A
(1.9)
tương đương
max z D min.z/ (1.10)
Do đó, kh ông mất tính tổng quát t ron g phần lý thuyết ta chỉ phát biểu
bài toán tìm giá tr lớn nhất hàm mục t iêu .max z/. Bài toán tìm giá
trị nhỏ nhất hàm mục tiêu .min z/ th ì thể sử dụng (1.10) để chuyển
sang bài toán tìm giá trị lớn nhất của hàm mục tiêu .
dụ 1.5. Chuyển các bài toán quy hoạch tuyến tính tìm max hàm
mục tiêu thành tìm m in hàm mục tiêu hay ngược lại
a. z D 2x
1
C 3x
2
C 4x
3
! max
Với các ràng buộc
1.3 Chuyển bài toán quy hoạch sang dạng chính tắc Trang 8
8
<
:
3x
1
C 2 x
2
3x
3
4
2x
1
C 3 x
2
C 2x
3
6
3x
1
x
2
C 2x
3
8
x
1
0; x
2
0; x
3
0
b. z D 3x
1
C 2x
2
! min
Với các ràng buộc
2x
1
C x
2
4
3x
1
2x
2
6
x
1
0; x
2
0
Giải.
a. Bài toán trong câu a t ương đương với
z D 2x
1
3x
2
4x
3
! min
Với các ràng buộc
8
<
:
3x
1
C 2x
2
3x
3
4
2x
1
C 3x
2
C 2x
3
6
3x
1
x
2
C 2x
3
8
x
1
0; x
2
0; x
3
0
b. Bài toán trong câu b tương đương với
z D 3x
1
2x
2
! max
Với các ràng buộc
2x
1
C x
2
4
3x
1
2x
2
6
x
1
0; x
2
0
1.3 Chuyển bài toán quy hoạch sang dạng
chính tắc
1.3.1 Đổi chiều bất đẳng thức của các ràng buộc
Nếu ta nhân hai vế của bất phương trình
k
1
x
1
C k
2
x
2
C C k
n
x
n
b
với 1 ta được bất phương trình
k
1
x
1
k
2
x
2
k
n
x
n
b
Trang 9 Chương 1. Giới thiệu quy hoạch tuyến tính
dụ 1.6. Chuyển bài toán quy hoạch tuyến tính sau sang dạng chuẩn:
z D 2x
1
C 3x
2
C 4x
3
! max
Với các ràng buộc
8
<
:
3x
1
C 2 x
2
3x
3
4
2x
1
C 3 x
2
C 2 x
3
6
3x
1
x
2
C 2 x
3
8
x
1
0; x
2
0; x
3
0
Giải. Ta nhân ràng buộc thứ ba
3x
1
x
2
C 2x
3
8
với 1; ta bài toán quy hoạch dạng chuẩn tương đươ n g:
z D 2x
1
C 3x
2
C 4x
3
! max
Với các ràng buộc
8
<
:
3x
1
C 2 x
2
3x
3
4
2x
1
C 3 x
2
C 2x
3
6
13x
1
C x
2
2x
3
8
x
1
0; x
2
0; x
3
0
1.3.2 Biến không ràng buộc
Ta biết, một số bất kỳ chính hiệu của hai số không âm. Giả sử x
j
không ràng buộc không âm, ta thể thay x
j
bằng hai biến x
C
j
0
và x
j
0 sao cho
x
j
D x
C
j
x
j
Với cách n ày, ta thể chuyển bài toán không ràng buộc không âm
thành bài to án ràng buộc không âm.
÷
dụ 1.7. Chuyển bài toán quy hoạch tuyến tính sau sang dạng chuẩn
z D 2x
1
C 5x
2
! max
Với các ràng buộc
3x
1
C 2x
2
6
2x
1
C 9x
2
8
x
1
0
÷
đây dấu C; trong x
C
j
; x
j
không thể hiện số lớn, số chỉ x
C
j
số trừ
x
j
số bị trừ.
1.3 Chuyển bài toán quy hoạch sang dạng chính tắc Trang 10
Giải. Biến x
2
không ràng buộc không âm. Đặt x
2
D x
C
2
x
2
; .x
C
2
; x
2
0/ bài toán quy hoạch trở thành:
z D 2x
1
C 5x
C
2
5x
2
! max
Với các ràng buộc
3x
1
C 2 x
C
2
2x
2
6
2x
1
C 9 x
C
2
9x
2
8
x
1
0; x
C
2
0; x
2
0
1.3.3 Chuyển dạng chuẩn san g dạng chính tắc
Xét ràng buộc thứ i trong bài toán quy hoạch tuyến tính dạng chuẩn
a
i1
x
1
C a
i2
x
2
C C a
in
x
n
b
i
(1.11)
Ta thể chuy n ràng buộc (1.11) dạng bất phương trình thành phương
trình bằng cách thêm vào biến phụ x
nCi
0
a
i1
x
1
C a
i2
x
2
C C a
in
x
n
C x
nCi
D b
i
(1.12)
Bài toán quy hoạch tuyến tính dạng chuẩn chuyển thành dạng chính
tắc dạng như sau:
z D c
1
x
1
C c
2
x
2
C C c
n
x
n
! max
Với các ràng buộc
8
ˆ
ˆ
ˆ
<
ˆ
ˆ
ˆ
:
a
11
x
1
C C a
1n
x
n
C x
nC1
D b
1
a
21
x
1
C C a
2n
x
n
C x
nC2
D b
2
:
:
:
:
:
:
:
:
:
a
m1
x
1
C C a
mn
x
n
C x
nCm
D b
m
x
1
0; : : : ; x
n
0; x
nC1
0; : : : ; x
nCm
0
dụ 1.8. Chuyển bài toán sau sang dạng chính t ắc
z D 120 x
1
C 100x
2
! max
Với các ràng buộc
2x
1
C 3x
2
8
5x
1
C 3x
2
15
x
1
0; x
2
0
Trang 11 Chương 1. Giới thiệu quy hoạch tuyến tính
Giải. Ta thêm hai biến phụ x
3
0 x
4
0 o ràng buộc thứ nhất và
thứ hai thì được bài toán quy hoạch dạng chính tắc như sau:
z D 120 x
1
C 100x
2
! max
Với các ràng buộc
2x
1
C 3 x
2
C x
3
D 8
5x
1
C 3 x
2
C x
4
D 15
x
j
0; j D 1; : : : ; 4
dụ 1.9. Chuyển các bài toán quy hoạch tuyến tính sau sang dạng
chính tắc
a. z D 3x
1
C 2x
2
! min
Với các ràng buộc
2x
1
C x
2
4
3x
1
2x
2
6
x
1
0; x
2
0
Giải. Ta thêm vào hai ẩn phụ x
3
và x
4
. Bài toán dạng chính tắc
z D 3x
1
C 2x
2
! min
Với các ràng buộc
2x
1
C x
2
C x
3
D 4
3x
1
2x
2
C x
4
D 6
x
j
0; j D 1; : : : ; 4
b. z D 2x
1
C 3x
2
C 4x
3
! max
Với các ràng buộc
8
<
:
3x
1
C 2x
2
3x
3
4
2x
1
C 3x
2
C 2 x
3
6
3x
1
x
2
C 2 x
3
8
x
1
0; x
2
0; x
3
0
Giải. Cộng hai ẩn phụ x
4
; x
5
vào ràng buộc 1 và 2, riêng ràng buộc
1.3 Chuyển bài toán quy hoạch sang dạng chính tắc Trang 12
thứ 3 tr ẩn phụ x
6
: Bài t oán dạng chính tắc
z D 2x
1
C 3x
2
C 4x
3
! max
Với các ràng buộc
8
<
:
3x
1
C 2 x
2
3x
3
C x
4
D 4
2x
1
C 3 x
2
C 2x
3
C x
5
D 6
3x
1
x
2
C 2x
3
x
6
D 8
x
j
0; j D 1; : : : ; 6
c. z D 3x
1
C 2x
2
C 3x
3
2x
4
! max
Với các ràng buộc
8
<
:
2x
1
C 6 x
2
C 2x
3
4x
4
D 7
3x
1
C 2 x
2
5x
3
C x
4
D 8
6x
1
C 7 x
2
C 2x
3
C 5x
4
4
x
1
0; x
2
0; x
3
0; x
4
0
Giải. Thêm ẩn phụ x
5
vào ràng buộc thứ 3
z D 3x
1
C 2x
2
C 3x
3
2x
4
! max
Với các ràng buộc
8
<
:
2x
1
C 6 x
2
C 2x
3
4x
4
D 7
3x
1
C 2 x
2
5x
3
C x
4
D 8
6x
1
C 7 x
2
C 2x
3
C 5x
4
C x
5
D 4
x
j
0; j D 1; : : : ; 5
d. z D 2x
1
C 5x
2
! max
Với các ràng buộc
3x
1
C 2x
2
6
2x
1
C 9x
2
8
x
1
0
Giải. Biến x
2
không ràng buộc không âm. Thay x
2
D x
C
2
x
2
bài toán quy hoạch trở th ành:
z D 2x
1
C 5x
C
2
5x
2
! max
Với các ràng buộc
3x
1
C 2 x
C
2
2x
2
6
2x
1
C 9 x
C
2
9x
2
8
x
1
0; x
C
2
0; x
2
0
Trang 13 Chương 1. Giới thiệu quy hoạch tuyến tính
Thêm hai ẩn phụ x
3
; x
4
z D 2x
1
C 5x
C
2
5x
2
! max
Với các ràng buộc
3x
1
C 2x
C
2
2x
2
C x
3
D 6
2x
1
C 9x
C
2
9x
2
C x
4
D 8
x
1
0; x
C
2
0; x
2
0; x
3
0; x
4
0
e. z D 2x
1
C 3x
2
! min
Với các ràng buộc
8
<
:
2x
1
C x
2
x
3
D 4
3x
1
C 2x
2
C x
3
D 8
x
1
x
2
D 6
x
1
0; x
3
0
Giải. Biến x
2
không ràng buộc không âm. Thay x
2
D x
C
2
x
2
bài toán tươ n g đương với
z D 2x
1
C 3x
C
2
3x
2
! min
Với các ràng buộc
8
<
:
2x
1
C x
C
2
x
2
x
3
D 4
3x
1
C 2x
C
2
2x
2
C x
3
D 8
x
1
x
C
2
x
2
D 6
x
1
0; x
3
0; x
C
2
0; x
2
0
1.4 Dạng ma trận của i toán quy hoạch
Xét bài toán quy hoạch dạng chuẩn:
z D c
1
x
1
C c
2
x
2
C C c
n
x
n
! max
Với các ràng buộc
8
ˆ
ˆ
ˆ
<
ˆ
ˆ
ˆ
:
a
11
x
1
C a
12
x
2
C C a
1n
x
n
b
1
a
21
x
1
C a
22
x
2
C C a
2n
x
n
b
2
:
:
:
:
:
:
:
:
:
:
:
:
a
m1
x
1
C a
m2
x
2
C C a
mn
x
n
b
m
x
j
0; j D 1; 2; : : : ; n
1.5 Phương án chấp nhận được Trang 14
Đặt
A D
0
B
B
B
@
a
11
a
12
a
1n
a
21
a
22
a
2n
:
:
:
:
:
:
:
:
:
a
m1
a
m2
a
mn
1
C
C
C
A
I x D
0
B
B
B
@
x
1
x
2
:
:
:
x
n
1
C
C
C
A
I b D
0
B
B
B
@
b
1
b
2
:
:
:
b
m
1
C
C
C
A
I c D
0
B
B
B
@
c
1
c
2
:
:
:
c
n
1
C
C
C
A
Ta thể viết bài toán quy hoạch trên thành dạng ma trận:
z D c
T
x ! max
Với các ràng buộc
Ax b
x 0
dụ 1.10. Viết bài toán quy ho ạch tuyến tính sau dưới dạng ma trận.
z D 120 x
1
C 100x
2
! max
Với các ràng buộc
2x
1
C 3x
2
8
5x
1
C 3x
2
15
x
1
0; x
2
0
Giải. Đặt
A D
2 3
5 3
I x D
x
1
x
2
I c D
120
100
I b D
8
15
Bài toán y giờ tìm x sao cho
z D c
T
x ! max
Với các ràng buộc
Ax b
x 0
1.5 Phương án chấp nhận được
Định nghĩa 1.1 (Phương án chấp nhận được). Vector x 2 R
n
thỏa tất
cả các ràng buộc của bài toán quy hoạch tuyến tính được gọi phương
án chấp nhận được.
Trang 15 Chương 1. Giới thiệu quy hoạch tuyến tính
dụ 1.11. Cho bài toán quy hoạch tuyến tính:
z D 120x
1
C 100x
2
! max
Với các ràng buộc
2x
1
C 3 x
2
8
5x
1
C 3 x
2
15
x
1
0; x
2
0
và các phương án:
x
1
D
1
2
I x
2
D
2
1
I x
3
D
1
3
I x
4
D
2
2
Phương án nào phương án chấp nhận được?
Giải. Ràng buộc được viết lại
2 3
5 3
x
1
x
2
8
15
Ta t lần lượt các phương án x
i
0; i D 1; : : : ; 4:
Với phương án x
1
2 3
5 3
1
2
D
8
11
8
15
Vy x
1
phương án chấp nhận được.
Với phương án x
2
2 3
5 3
2
1
D
7
13
8
15
Vy x
2
phương án chấp nhận được.
Với phương án x
3
2 3
5 3
1
3
D
11
14
8
15
Vy x
3
không phương án chấp nhận được.
1.6 Ý nghĩa hình học Trang 16
Với phương án x
4
2 3
5 3
2
2
D
10
16
8
15
Vy x
4
không phương án chấp nhận được.
Định nghĩa 1.2 (Phương án tối ưu). Phương án chấp nhận được làm
cho hàm m c tiêu giá trị lớn nhất (nếu bài toán max) hay nhỏ nhất
(nếu bài toán min) thì được gọi phương án tối ưu.
1.6 Ý nghĩa hình học của bài toán quy hoạch
tuyến tính
Trong phần y ta t đến phương pháp giải bài toán quy hoạch tuyến
tính bằng hình học. Phương pháp hình học chỉ giải những bài toán
quy hoạch tuyến tính hai hoặc ba biến. Tuy nhiên, ý nghĩa của phương
pháp y cho ta ý tưởn g để y dựng thuật toán thể giải được bài
toán nhiều biến hơn sẽ được trình y trong chương 2.
1.6.1 Phương pháp đồ thị giải bài toán quy hoạch
tuyến tính
dụ 1.12. Giải bài toán quy hoạch tuyến tính
z D 4x C 3y ! max
Với các ràng buộc
x C y 4
5x C 3y 15
x 0; y 0
Giải. Tập các phương án chấp nhận được như hình 1.1b. Hàm mục tiêu
được viết lại
y D 4=3x C z=3 (d)
trong đó (d) một đường thẳng song song với y D 4=3x và cắt trục
tung tại z=3:
Ta nhận thấy z ! max khi chỉ khi z=3 ! max : Như h ình 1.2a, để
tăng giá trị z=3 ta tịnh tiến đường (d) th eo phương của đường thẳng
y D 4=3x sao cho đường (d) vẫn cắt tập chấp nhận được OABC.
| 1/141

Preview text:

Bài giảng đang được chỉnh sửa Quy hoạch tuyến tính ảng Nguyễn Đức Phương gi ài B
TP. HCM, Ngày 4 tháng 1 năm 2016 Bảng ký hiệu R Tập số thực
A Ma trận hệ số vế phải của các ràng buộc
b Vector hệ số vế phải
c Vector hệ số hàm mục tiêu
x Phương án chấp nhận được N
x Phương án tối ưu xT Phép chuyển vị jAj
Định thức ma trận A Œx
Tọa độ của vector theo x theo cơ sở T T A Cột j
j của ma trận hệ số A e Vector đơn vị thứ j j
Là ước lượng của vector cột A j j hxI yi
Tích vô hướng của x y
B D fAk I : : : I A g Hệ vector liên kết 1 km
cB D fck I : : : I c g Hệ số hàm mục tiêu có chỉ số k 1 km 1; : : : ; km
B Ma trận có các cột là các vector của B
AB Biểu diễn cột A theo cơ sở B j j Mục lục Mục lục ii
1 Giới thiệu quy hoạch tuyến tính 1
1.1 Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Các dạng bài toán quy hoạch tuyến tính . . . . . . . . . . 5
1.2.1 Dạng tổng quát . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Dạng chuẩn . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Dạng chính tắc . . . . . . . . . . . . . . . . . . . . 6
1.3 Chuyển bài toán quy hoạch sang dạng chính tắc . . . . . 8
1.3.1 Đổi chiều bất đẳng thức của các ràng buộc . . . . . 8
1.3.2 Biến không ràng buộc . . . . . . . . . . . . . . . . . 9
1.3.3 Chuyển dạng chuẩn sang chính tắc . . . . . . . . . 10
1.4 Dạng ma trận của bài toán quy hoạch . . . . . . . . . . . 13
1.5 Phương án chấp nhận được . . . . . . . . . . . . . . . . . . 14
1.6 Ý nghĩa hình học . . . . . . . . . . . . . . . . . . . . . . . 16
1.6.1 Phương pháp đồ thị . . . . . . . . . . . . . . . . . . 16
1.6.2 Tính chất của tập phương án chấp nhận được . . . 19
1.7 Phương án cực biên . . . . . . . . . . . . . . . . . . . . . . 21
1.7.1 Thành lập phương án cơ bản chấp nhận . . . . . . 23
1.7.2 Thành lập phương án cực biên . . . . . . . . . . . . 27
1.7.3 Tìm phương án tối ưu từ phương án cực biên . . . 30
1.8 Bài tập chương 1 . . . . . . . . . . . . . . . . . . . . . . . . 32
2 Phương pháp đơn hình 34
2.1 Phương pháp đơn hình cho bài toán chính tắc . . . . . . . 34
2.1.1 Phương pháp đơn hình . . . . . . . . . . . . . . . . 34
2.1.2 Dấu hiệu tối ưu . . . . . . . . . . . . . . . . . . . . 36
2.1.3 Thành lập phương án cực biên mới . . . . . . . . . 38
2.2 Bảng đơn hình . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.3 Thuật toán đơn hình cho bài toán min . . . . . . . . . . . 52
2.4 Bài toán chính tắc không có sẵn ma trận đơn vị . . . . . . 53 Trang iii Mục lục
2.5 Bài tập chương 2 . . . . . . . . . . . . . . . . . . . . . . . . 59
3 Lý thuyết đối ngẫu 64
3.1 Định nghĩa bài toán đối ngẫu . . . . . . . . . . . . . . . . 64
3.1.1 Đối ngẫu của bài toán max . . . . . . . . . . . . . . 68
3.1.2 Đối ngẫu của bài toán min . . . . . . . . . . . . . . 71
3.2 Các định lý về đối ngẫu . . . . . . . . . . . . . . . . . . . . 74
3.3 Phương án tối ưu của bài toán đối ngẫu . . . . . . . . . . 81
3.3.1 Biết phương án tối ưu bài toán gốc . . . . . . . . . 81
3.3.2 Có bảng đơn hình của phương án tối ưu . . . . . . 85
3.4 Bài tập chương 3 . . . . . . . . . . . . . . . . . . . . . . . . 89
4 Bài toán vận tải 93
4.1 Bài toán vận tải cân bằng thu phát . . . . . . . . . . . . . 93
4.2 Phương án cực biên . . . . . . . . . . . . . . . . . . . . . . 95
4.3 Thành lập phương án cực biên . . . . . . . . . . . . . . . . 98
4.3.1 Phương pháp cước phí thấp nhất . . . . . . . . . . 98
4.3.2 Phương pháp góc Tây - Bắc . . . . . . . . . . . . . 100
4.3.3 Phương pháp Vogel (Fogel) . . . . . . . . . . . . . . 102
4.4 Thuật toán thế vị giải bài toán vận tải . . . . . . . . . . . 104
4.4.1 Thuật toán quy không cước phí ô chọn . . . . . . . 104
4.4.2 Xây dựng phương án cực biên mới . . . . . . . . . 109
4.5 Một số trường hợp đặc biệt . . . . . . . . . . . . . . . . . . 114
4.5.1 Bài toán vận tải không cân bằng thu phát . . . . . 114
4.5.2 Bài toán vận tải có ô cấm . . . . . . . . . . . . . . . 116
4.6 Bài toán vận tải cực đại cước phí . . . . . . . . . . . . . . 117
4.7 Bài tập chương 4 . . . . . . . . . . . . . . . . . . . . . . . . 118 A Đề thi mẫu 121
A.1 Đề học kì III năm 2010-2011 . . . . . . . . . . . . . . . . . 121
A.2 Đề học kì I năm 2011-2012 . . . . . . . . . . . . . . . . . . 122
A.3 Đề thi học kỳ II năm 2011-2012 . . . . . . . . . . . . . . . 123
A.4 Đề học kì III năm 2011-2012 . . . . . . . . . . . . . . . . . 124
B Bài giải đề mẫu 126
B.1 Bài giải học kì III năm học 2010-2011 . . . . . . . . . . . 126
B.2 Bài giải học kì I năm học 2011-2012 . . . . . . . . . . . . 129
B.3 Bài giải học kì II năm học 2011-2012 . . . . . . . . . . . . 132
B.4 Bài giải học kì III năm học 2011-2012 . . . . . . . . . . . 135 Tài liệu tham khảo 137 Chương 1
Giới thiệu quy hoạch tuyến tính Mục lục chương 1
1.1 Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Các dạng bài toán quy hoạch tuyến tính . . . . . . . . . 5
1.3 Chuyển bài toán quy hoạch sang dạng chính tắc . . . . 8
1.4 Dạng ma trận của bài toán quy hoạch . . . . . . . . . . . 13
1.5 Phương án chấp nhận được
. . . . . . . . . . . . . . . . . 14
1.6 Ý nghĩa hình học
. . . . . . . . . . . . . . . . . . . . . . . . 16
1.7 Phương án cực biên
. . . . . . . . . . . . . . . . . . . . . . 21
1.8 Bài tập chương 1
. . . . . . . . . . . . . . . . . . . . . . . . 32
1.1 Một số ví dụ dẫn đến bài toán quy hoạch tuyến tính
Ví dụ 1.1 (Bài toán lập kế hoạch sản xuất). Một trại cưa cưa các khúc
gỗ thành các tấm ván. Có hai loại ván: ván thành phẩm và ván sử dụng
trong xây dựng. Giả sử, đối với:
Ván thành phẩm cần 2 giờ để cưa và 5 giờ để bào 10m ván.
Ván dùng trong xây dưng cần 3 giờ để cưa và 3 giờ để bào 10m ván. 1.1 Một số ví dụ Trang 2
Máy cưa làm việc tối đa 8 giờ trong ngày, và máy bào làm việc tối đa 15
giờ trong ngày. Nếu lợi nhuận của 10m ván thành phẩm là 120 (ngàn
đồng), và lợi nhuận của 10m ván xây dựng là 100 (ngàn đồng). Trong
ngày, trại cưa phải cưa bao nhiêu ván mỗi loại để lợi nhuận lớn nhất?
Giải. Gọi x1; x2 0 là lượng ván thành phẩm và ván sử dụng trong xây dựng. ❳❳❳❳❳❳ Loại ❳❳❳ Thành phẩm - Xây dựng - Thời gian x x ❳ 1 2 ❳❳ Cưa 2 3 8 Bào 5 3 15 Lợi nhuận 120 100 Tổng lợi nhuận z D 120x1 C 100x2 ! max khi đó x
thỏa điều kiện thời gian làm việc máy cưa 1; x2 2x1 C 3x2 8
và điều kiện về thời gian làm việc máy bào 5x1 C 3x2 15 Tóm lại cần tìm x sao cho 1; x2 z D 120x1 C 100x2 ! max Với các ràng buộc 2x1 C 3x2 8 5x1 C 3x2 15 x1 0; x2 0
Ví dụ 1.2 (Bài toán khẩu phần ăn). Chuyên gia dinh dưỡng định thành
lập một thực đơn gồm 2 loại thực phẩm chính A và B. Cứ một (trăm gram):
Thực phẩm A chứa 2 đơn vị chất béo, 1 đơn vị carbohydrate và 4 đơn vị protein.
Thực phẩm B chứa 3 đơn vị chất béo, 3 đơn vị carbohydrate và 3 đơn vị protein. Trang 3
Chương 1. Giới thiệu quy hoạch tuyến tính
Nếu một (trăm gram) thực phẩm A giá 20 (ngàn đồng) và một (trăm
gram) thực phẩm B giá 25 (ngàn đồng). Nhà dinh dưỡng muốn thức ăn
phải cung cấp ít nhất 18 đơn vị chất béo, 12 đơn vị carbohydrate và 24
đơn vị protein. Bao nhiêu (trăm gram) thực phẩm mỗi loại để có giá nhỏ
nhất nhưng vẫn cung cấp đủ dinh dưỡng? Giải. Gọi x
lần lượt là lượng thực phẩm A và B. 1; x2 ❳❳❳❳❳❳ Loại ❳❳❳ TP A - TP B - Thành phần x x ❳ 1 2 ❳❳ Chất béo 2 3 18 Carbohydrate 1 3 12 Protein 4 3 24 Giá mua 20 25 tổng số tiền mua x thực phẩm A và B là 1; x2 z D 20x1 C 25x2 ! min
Yêu cầu lượng thực phẩm phải đảm bảo nhu cầu chất béo 2x1 C 3x2 18 nhu cầu Carbohydrate x1 C 3x2 12 nhu cầu Protein 4x1 C 3x2 24 Vậy ta cần tìm x sao cho 1; x2 z D 20x1 C 25x2 ! min Với các ràng buộc 8 2x < 1 C 3x2 18 x1 C 3x2 12 : 4x1 C 3x2 24 x1 0; x2 0
Ví dụ 1.3 (Bài toán vận tải). Một nhà sản xuất có 2 nhà máy: Một nhà
máy ở Vĩnh Phúc và một nhà máy ở Bình Dương. Có 3 kho hàng phân
phối sản phẩm đặt ở Hà Nội, TP. HCM và Cần Thơ. Nhà máy ở Vĩnh TP: Thực phẩm 1.1 Một số ví dụ Trang 4
phúc; Bình Dương, có khả năng cung cấp tối đa 100; 140 tấn mỗi tuần.
Lượng cầu của các kho ở Hà Nội, TP. HCM và Cần Thơ lần lượt từ 100;
60 và 80 tấn trở lên. Chi phí vận chuyển (trăm ngàn) mỗi tấn cho như
bảng bên dưới. Hỏi cần vận chuyển bao nhiêu tấn hàng hóa từ nhà sản
xuất đến các kho hàng ở Hà Nội, TP. HCM và ở cần thơ để chi phí nhỏ
nhất nhưng vẫn đáp ứng đủ nhu cầu?
❵❵❵❵❵❵❵ Trạm thu Hà Nội TP. HCM Cần Thơ ❵❵❵❵❵ Trạm phát ❵❵❵ W :100 :60 :80 1 W2 W3 Vĩnh Phúc-Q : 100 5 7 9 1 Bình Dương-Q :140 8 7 10 2
Giải. Gọi x là lượng hàng vận chuyển từ trạm phát thứ ij i I i D 1; 2 đến
trạm thu thứ j I j D 1; 2; 3: Tổng chi phí vận chuyển z D x11 C x12 C C x23 ! min
Trạm phát thì phát hết hàng và trạm thu thì nhận đủ hàng:
Trạm phát 1 phát hết hàng x11 C x12 C x13 D 100
Trạm phát 2 phát hết hàng x21 C x22 C x23 D 140 Trạm thu 1 thu đủ hàng x11 C x21 D 100 Trạm thu 2 thu đủ hàng x12 C x22 D 60 Trạm thu 3 thu đủ hàng x13 C x23 D 80 Vậy ta cần tìm x sao cho ij z D x11 C x12 C C x23 ! min Với các ràng buộc 8 ˆx ˆ 11 C x12 C x13 D 100 ˆ ˆ ˆ ˆx < 21 C x22 C x23 D 140 x11 C x21 D 100 ˆ ˆ ˆx ˆ 12 C x22 D 60 ˆ ˆ :x13 C x23 D 80 xij 0 i D 1; 2I j D 1; 2; 3 Trang 5
Chương 1. Giới thiệu quy hoạch tuyến tính
1.2 Các dạng bài toán quy hoạch tuyến tính
1.2.1 Dạng tổng quát
Từ các ví dụ mục 1.1, bài toán quy hoạch tuyến tính dạng tổng quát
được phát biểu như sau:
z D c1x1 C c2x2 C C cnxn ! max .hay min/ (1.1) Với các ràng buộc 8 ˆ a11x1 C a12x2 C C a1nxn ./.D/ b1 ˆ ˆ < a21x1 C a22x2 C C a2nxn ./.D/ b2 : (1.2) : :: :: :: ˆ : : : : ˆ ˆ
: am1x1 C am2x2 C C amnxn ./.D/ bm
Hàm tuyến tính (1.1) gọi là hàm mục tiêu.
Hệ bất phương trình, bất phương trình tuyến tính (1.2) gọi là các
ràng buộc. Vế trái của các ràng buộc là các hàm tuyến tính với x là các biến số. 1; x2; : : : ; xn 1.2.2 Dạng chuẩn
Ta nói bài toán quy hoạch tuyến tính có dạng chuẩn nếu nó có dạng như sau:
z D c1x1 C c2x2 C C cnxn ! max; .hay min/ (1.3) Với các ràng buộc 8 ˆ a11x1 C a12x2 C C a1nxn b1 ˆ ˆ < a21x1 C a22x2 C C a2nxn b2 : (1.4) : :: :: :: ˆ : : : : ˆ ˆ : am1x1 C am2x2 C C amnxn bm xj 0; j D 1; 2; : : : ; n (1.5)
1.2 Các dạng bài toán quy hoạch tuyến tính Trang 6 1.2.3 Dạng chính tắc
Ta nói bài toán quy hoạch tuyến tính có dạng chính tắc nếu nó có dạng như sau:
z D c1x1 C c2x2 C C cnxn ! max; .hay min/ (1.6) Với các ràng buộc 8 ˆ a11x1 C a12x2 C C a1nxn D b1 ˆ ˆ < a21x1 C a22x2 C C a2nxn D b2 : (1.7) : :: :: :: ˆ : : : : ˆ ˆ : am1x1 C am2x2 C C amnxn D bm xj 0; j D 1; 2; : : : ; n (1.8)
Ví dụ 1.4. Nhận dạng các bài toán quy hoạch tuyến tính sau: a. z D 3x1 C 2x2 ! min Với các ràng buộc 2x1 C x2 4 3x1 2x2 6 x1 0; x2 0 Có dạng chuẩn.
b. z D 2x1 C 3x2 C 4x3 ! max Với các ràng buộc 8 3x < 1 C 2x2 3x3 4 2x1 C 3x2 C 2x3 6 : 3x1 x2 C 2x3 8 x1 0; x2 0; x3 0 Có dạng tổng quát.
c. z D 3x1 C 2x2 C 3x3 2x4 ! max Với các ràng buộc 8 2x < 1 C 6x2 C 2x3 4x4 D 7 3x1 C 2x2 5x3 C x4 D 8 : 6x1 C 7x2 C 2x3 C 5x4 4 x1 0; x2 0; x3 0; x4 0 Có dạng tổng quát.
Một số sách có định nghĩa khác về dạng chuẩn và dạng chính tắc. Các bạn cần đọc
kỹ định nghĩa khi tham khảo các tài liệu khác.
Có thể dễ dàng chuyển sang dạng chính tắc bằng cách nhân hai vế ràng buộc thứ 3 với 1 Trang 7
Chương 1. Giới thiệu quy hoạch tuyến tính
d. z D 2x1 C 5x2 C x3 C x4 C 4x5 ! min Với các ràng buộc 3x1 C 2x2 x3 C 2x5 D 4 4x1 C 5x2 C 3x3 C 2x4 D 7 x1 0; x2 0; x3 0; x4 0; x5 0 Có dạng chính tắc. e. z D 2x1 C 5x2 ! max Với các ràng buộc 3x1 C 2x2 6 2x1 C 9x2 8 x1 0 Có dạng tổng quát. f. z D 2x1 C 3x2 ! min Với các ràng buộc 8 2x < 1 C x2 x3 D 4 3x1 C 2x2 C x3 D 8 : x1 x2 D 6 x1 0; x2 0 Có dạng tổng quát
Chú ý. Bài toán tìm giá trị nhỏ nhất của hàm mục tiêu có thể viết
thành bài toán tìm giá trị lớn nhất của hàm mục tiêu và ngược lại bằng quan hệ: 0 1 n n max X X cj xj D min @ cj xj A (1.9) j D1 j D1 tương đương max z D min. z/ (1.10)
Do đó, không mất tính tổng quát trong phần lý thuyết ta chỉ phát biểu
bài toán tìm giá trị lớn nhất hàm mục tiêu .max z/. Bài toán tìm giá
trị nhỏ nhất hàm mục tiêu .min z/ thì có thể sử dụng (1.10) để chuyển
sang bài toán tìm giá trị lớn nhất của hàm mục tiêu .
Ví dụ 1.5. Chuyển các bài toán quy hoạch tuyến tính tìm max hàm
mục tiêu thành tìm min hàm mục tiêu hay ngược lại
a. z D 2x1 C 3x2 C 4x3 ! max Với các ràng buộc
1.3 Chuyển bài toán quy hoạch sang dạng chính tắc Trang 8 8 3x < 1 C 2x2 3x3 4 2x1 C 3x2 C 2x3 6 : 3x1 x2 C 2x3 8 x1 0; x2 0; x3 0 b. z D 3x1 C 2x2 ! min Với các ràng buộc 2x1 C x2 4 3x1 2x2 6 x1 0; x2 0 Giải.
a. Bài toán trong câu a tương đương với z D 2x1 3x2 4x3 ! min Với các ràng buộc 8 3x < 1 C 2x2 3x3 4 2x1 C 3x2 C 2x3 6 : 3x1 x2 C 2x3 8 x1 0; x2 0; x3 0
b. Bài toán trong câu b tương đương với z D 3x1 2x2 ! max Với các ràng buộc 2x1 C x2 4 3x1 2x2 6 x1 0; x2 0
1.3 Chuyển bài toán quy hoạch sang dạng chính tắc
1.3.1 Đổi chiều bất đẳng thức của các ràng buộc
Nếu ta nhân hai vế của bất phương trình k1x1 C k2x2 C C knxn b
với 1 ta được bất phương trình k1x1 k2x2 knxn b Trang 9
Chương 1. Giới thiệu quy hoạch tuyến tính
Ví dụ 1.6. Chuyển bài toán quy hoạch tuyến tính sau sang dạng chuẩn: z D 2x1 C 3x2 C 4x3 ! max Với các ràng buộc 8 3x < 1 C 2x2 3x3 4 2x1 C 3x2 C 2x3 6 : 3x1 x2 C 2x3 8 x1 0; x2 0; x3 0
Giải. Ta nhân ràng buộc thứ ba 3x1 x2 C 2x3 8
với 1; ta có bài toán quy hoạch dạng chuẩn tương đương: z D 2x1 C 3x2 C 4x3 ! max Với các ràng buộc 8 3x < 1 C 2x2 3x3 4 2x1 C 3x2 C 2x3 6 : 13x1 C x2 2x3 8 x1 0; x2 0; x3 0
1.3.2 Biến không ràng buộc
Ta biết, một số bất kỳ chính là hiệu của hai số không âm. Giả sử xj
không có ràng buộc không âm, ta có thể thay x bằng hai biến j xC 0 j và x 0 sao cho j xj D xC x j j
Với cách này, ta có thể chuyển bài toán không có ràng buộc không âm
thành bài toán có ràng buộc không âm.÷
Ví dụ 1.7. Chuyển bài toán quy hoạch tuyến tính sau sang dạng chuẩn z D 2x1 C 5x2 ! max Với các ràng buộc 3x1 C 2x2 6 2x1 C 9x2 8 x1 0 ÷Ở đây dấu C;
trong xC; x không thể hiện số lớn, số bé mà chỉ là xC là số trừ và j j j x là số bị trừ. j
1.3 Chuyển bài toán quy hoạch sang dạng chính tắc Trang 10
Giải. Biến x không có ràng buộc không âm. Đặt 2 x2 D xC x ; .xC; x 2 2 2 2
0/ bài toán quy hoạch trở thành: z D 2x1 C 5xC 5x ! max 2 2 Với các ràng buộc 3x1 C 2xC 2x 6 2 2 2x1 C 9xC 9x 8 2 2 x1 0; xC 0; x 0 2 2
1.3.3 Chuyển dạng chuẩn sang dạng chính tắc
Xét ràng buộc thứ i trong bài toán quy hoạch tuyến tính dạng chuẩn a (1.11) i1x1 C ai 2x2 C C ai nxn bi
Ta có thể chuyển ràng buộc (1.11) dạng bất phương trình thành phương
trình bằng cách thêm vào biến phụ xnCi 0 a (1.12)
i1x1 C ai 2x2 C C ai nxn C xnCi D bi
Bài toán quy hoạch tuyến tính dạng chuẩn chuyển thành dạng chính tắc có dạng như sau: z D c1x1 C c2x2 C C cnxn ! max Với các ràng buộc 8 ˆ a11x1 C C a1nxn C xnC1 D b1 ˆ ˆ < a21x1 C C a2nxn C xnC2 D b2 :: :: :: ˆ : : : ˆ ˆ : am1x1 C C amnxn C xnCm D bm
x1 0; : : : ; xn 0; xnC1 0; : : : ; xnCm 0
Ví dụ 1.8. Chuyển bài toán sau sang dạng chính tắc z D 120x1 C 100x2 ! max Với các ràng buộc 2x1 C 3x2 8 5x1 C 3x2 15 x1 0; x2 0 Trang 11
Chương 1. Giới thiệu quy hoạch tuyến tính
Giải. Ta thêm hai biến phụ x3 0 và x4 0 vào ràng buộc thứ nhất và
thứ hai thì được bài toán quy hoạch dạng chính tắc như sau: z D 120x1 C 100x2 ! max Với các ràng buộc 2x1 C 3x2 C x3 D 8 5x1 C 3x2 C x4 D 15 xj 0; j D 1; : : : ; 4
Ví dụ 1.9. Chuyển các bài toán quy hoạch tuyến tính sau sang dạng chính tắc a. z D 3x1 C 2x2 ! min Với các ràng buộc 2x1 C x2 4 3x1 2x2 6 x1 0; x2 0
Giải. Ta thêm vào hai ẩn phụ x và
. Bài toán có dạng chính tắc 3 x4 z D 3x1 C 2x2 ! min Với các ràng buộc 2x1 C x2 C x3 D 4 3x1 2x2 C x4 D 6 xj 0; j D 1; : : : ; 4
b. z D 2x1 C 3x2 C 4x3 ! max Với các ràng buộc 8 3x < 1 C 2x2 3x3 4 2x1 C 3x2 C 2x3 6 : 3x1 x2 C 2x3 8 x1 0; x2 0; x3 0
Giải. Cộng hai ẩn phụ x
vào ràng buộc 1 và 2, riêng ràng buộc 4; x5
1.3 Chuyển bài toán quy hoạch sang dạng chính tắc Trang 12
thứ 3 trừ ẩn phụ x6: Bài toán có dạng chính tắc z D 2x1 C 3x2 C 4x3 ! max Với các ràng buộc 8 3x < 1 C 2x2 3x3 C x4 D 4 2x1 C 3x2 C 2x3 C x5 D 6 : 3x1 x2 C 2x3 x6 D 8 xj 0; j D 1; : : : ; 6
c. z D 3x1 C 2x2 C 3x3 2x4 ! max Với các ràng buộc 8 2x < 1 C 6x2 C 2x3 4x4 D 7 3x1 C 2x2 5x3 C x4 D 8 : 6x1 C 7x2 C 2x3 C 5x4 4 x1 0; x2 0; x3 0; x4 0
Giải. Thêm ẩn phụ x vào ràng buộc thứ 3 5 z D 3x1 C 2x2 C 3x3 2x4 ! max Với các ràng buộc 8 2x < 1 C 6x2 C 2x3 4x4 D 7 3x1 C 2x2 5x3 C x4 D 8
: 6x1 C 7x2 C 2x3 C 5x4 C x5 D 4 xj 0; j D 1; : : : ; 5 d. z D 2x1 C 5x2 ! max Với các ràng buộc 3x1 C 2x2 6 2x1 C 9x2 8 x1 0
Giải. Biến x không có ràng buộc không âm. Thay 2 x2 D xC x 2 2
bài toán quy hoạch trở thành: z D 2x1 C 5xC 5x ! max 2 2 Với các ràng buộc 3x1 C 2xC 2x 6 2 2 2x1 C 9xC 9x 8 2 2 x1 0; xC 0; x 0 2 2 Trang 13
Chương 1. Giới thiệu quy hoạch tuyến tính Thêm hai ẩn phụ x3; x4 z D 2x1 C 5xC 5x ! max 2 2 Với các ràng buộc 3x1 C 2xC 2x C x 2 2 3 D 6 2x1 C 9xC 9x C x 2 2 4 D 8 x1 0; xC 0; x 0; x 2 2 3 0; x4 0 e. z D 2x1 C 3x2 ! min Với các ràng buộc 8 2x < 1 C x2 x3 D 4 3x1 C 2x2 C x3 D 8 : x1 x2 D 6 x1 0; x3 0
Giải. Biến x không có ràng buộc không âm. Thay 2 x2 D xC x 2 2
bài toán tương đương với z D 2x1 C 3xC 3x ! min 2 2 Với các ràng buộc 8 2x x x < 1 C xC 2 2 3 D 4 3x1 C 2xC 2x C x 2 2 3 D 8 : x1 xC x D 6 2 2 x1 0; x3 0; xC 0; x 0 2 2
1.4 Dạng ma trận của bài toán quy hoạch
Xét bài toán quy hoạch dạng chuẩn: z D c1x1 C c2x2 C C cnxn ! max Với các ràng buộc 8 ˆ a11x1 C a12x2 C C a1nxn b1 ˆ ˆ < a21x1 C a22x2 C C a2nxn b2 :: :: :: :: ˆ : : : : ˆ ˆ : am1x1 C am2x2 C C amnxn bm xj 0; j D 1; 2; : : : ; n
1.5 Phương án chấp nhận được Trang 14 Đặt 0 1 0 1 0 1 0 1 a11 a12 a1n x1 b1 c1 B a C B x C B b C B c C A 21 a22 a2n 2 2 2 D B C B C B C B C B : I x D I b D I c D : :: :: C B :: C B :: C B :: C @ : : : A @ : A @ : A @ : A am1 am2 amn xn bm cn
Ta có thể viết bài toán quy hoạch trên thành dạng ma trận: z D cT x ! max Với các ràng buộc Ax b x 0
Ví dụ 1.10. Viết bài toán quy hoạch tuyến tính sau dưới dạng ma trận. z D 120x1 C 100x2 ! max Với các ràng buộc 2x1 C 3x2 8 5x1 C 3x2 15 x1 0; x2 0 Giải. Đặt A 2 3 x 120 8 D I x D 1 I c D I b D 5 3 x2 100 15
Bài toán bây giờ là tìm x sao cho z D cT x ! max Với các ràng buộc Ax b x 0
1.5 Phương án chấp nhận được
Định nghĩa 1.1 (Phương án chấp nhận được). Vector x 2 Rn thỏa tất
cả các ràng buộc của bài toán quy hoạch tuyến tính được gọi là phương
án chấp nhận được.
Trang 15
Chương 1. Giới thiệu quy hoạch tuyến tính
Ví dụ 1.11. Cho bài toán quy hoạch tuyến tính: z D 120x1 C 100x2 ! max Với các ràng buộc 2x1 C 3x2 8 5x1 C 3x2 15 x1 0; x2 0 và các phương án: x 1 2 1 2 1 D I x I x I x 2 2 D 1 3 D 3 4 D 2
Phương án nào là phương án chấp nhận được?
Giải. Ràng buộc được viết lại 2 3 x1 8 5 3 x2 15
Ta xét lần lượt các phương án xi 0; i D 1; : : : ; 4: Với phương án x1 2 3 1 8 8 D 5 3 2 11 15
Vậy x là phương án chấp nhận được. 1 Với phương án x2 2 3 2 7 8 D 5 3 1 13 15
Vậy x là phương án chấp nhận được. 2 Với phương án x3 2 3 1 11 8 D — 5 3 3 14 15
Vậy x không là phương án chấp nhận được. 3
1.6 Ý nghĩa hình học Trang 16 Với phương án x4 2 3 2 10 8 D — 5 3 2 16 15
Vậy x không là phương án chấp nhận được. 4
Định nghĩa 1.2 (Phương án tối ưu). Phương án chấp nhận được làm
cho hàm mục tiêu có giá trị lớn nhất (nếu là bài toán
max) hay nhỏ nhất
(nếu là bài toán
min) thì được gọi là phương án tối ưu.
1.6 Ý nghĩa hình học của bài toán quy hoạch tuyến tính
Trong phần này ta xét đến phương pháp giải bài toán quy hoạch tuyến
tính bằng hình học. Phương pháp hình học chỉ giải những bài toán
quy hoạch tuyến tính hai hoặc ba biến. Tuy nhiên, ý nghĩa của phương
pháp này cho ta ý tưởng để xây dựng thuật toán có thể giải được bài
toán nhiều biến hơn sẽ được trình bày trong chương 2.
1.6.1 Phương pháp đồ thị giải bài toán quy hoạch tuyến tính
Ví dụ 1.12. Giải bài toán quy hoạch tuyến tính z D 4x C 3y ! max Với các ràng buộc x C y 4 5x C 3y 15 x 0; y 0
Giải. Tập các phương án chấp nhận được như hình 1.1b. Hàm mục tiêu được viết lại y D 4=3x C z=3 (d)
trong đó (d) là một đường thẳng song song với y D 4=3x và cắt trục tung tại z=3:
Ta nhận thấy z ! max khi và chỉ khi z=3 ! max : Như hình 1.2a, để
tăng giá trị z=3 ta tịnh tiến đường (d) theo phương của đường thẳng y D
4=3x sao cho đường (d) vẫn cắt tập chấp nhận được OABC.