16/04/2017

Ví dụ 1

CHƯƠNG 5b

• Vậy ta có mô hình bài toán:
f  x   f  x1 , x2 , x3   3x1  2 x2  2,5 x3  max

QUY HOẠCH TUYẾN TÍNH
HAI BIẾN

0,04 x1  0,06 x2  0,05 x3  500

0,07 x1  0,02 x3  300
 x  0 j  1, 2,3


 j

• Đây là bài toán quy hoạch tuyến tính 3 biến, tìm
giá trị lớn nhất của hàm mục tiêu.
Bài giảng Toán Cao cấp 1

Nguyễn Văn Tiến

Bài giảng Toán Cao cấp 1

Ví dụ 1

Nguyễn Văn Tiến


Nguyễn Văn Tiến

Ví dụ 3

• Gọi x1,x2,x3 lần lượt là số bánh đậu xanh, bánh thập
cẩm, bánh dẻo cần phải sản xuất.
• Điều kiện: xj ≥ 0 = 1,2,3
• Tiền lãi thu được (ngàn đồng)

• Một cơ sở sản xuất đồ gỗ dự định sản xuất ba loại sản phẩm là
bàn, ghế và tủ. Định mức sử dụng lao động, chi phí sản xuất và
giá bán mỗi sản phẩm mỗi loại ước tính trong bảng sau:

f  x   f  x1 , x2 , x3   3x1  2 x2  2,5 x3
• Lượng đường sử dụng và điều kiện:

0,04 x1  0,06 x2  0,05 x3  500
• Lượng đậu sử dụng và điều kiện:

0,07 x1  0,02 x3  300
Bài giảng Toán Cao cấp 1

Nguyễn Văn Tiến

• Hãy lập mô hình toán học của bài toán xác định số sản phẩm
mỗi loại cần phải sản xuất sao cho không bị động trong sản xuất
và tổng doanh thu đạt được cao nhất, biết rằng cơ sở có số lao
động tương đương với 500 ngày công, số tiền dành cho chi phí
sản xuất là 40 triệu đồng và số bàn, ghế phải theo tỉ lệ 1/6.

260 x1  120 x2  600 x3  max
2 x1  x2  3 x3  500
100 x  40 x  250 x  40000

1
2
3

6
x

x
2
 1
 x1 , x2 , x3  0

Bài giảng Toán Cao cấp 1

Nguyễn Văn Tiến

Bài toán QHTT tổng quát

Dạng ma trận của bài toán QHTT

1

f  x   c1 x1  c2 x2  ...  cn xn  min (max)

• Xét bài toán QHTT dạng:


(2) là hệ ràng buộc chính
(3) là hệ ràng buộc dấu
(2) Và (3) gọi chung là hệ ràng buộc của bài toán
Bài giảng Toán Cao cấp 1

Nguyễn Văn Tiến

Bài toán dạng chính tắc
n

f  x    c jx j  min (max)
j1

n


 aijx j  bi (i  1,m)
 j1
x  0 (j  1,n)
 j

• Các ràng buộc
chính đều là
phương trình
• Các ẩn đều
không âm

Bài giảng Toán Cao cấp 1

Dạng ma trận của bài toán QHTT

 
c
c 2
 ... 
 
 cn 

• Ta có dạng ma trận của bài toán QHTT:
f  cT x  min  max 

Mọi bài toán quy hoạch tuyến tính đều có thể quy về bài
toán dạng chính tắc tương đương theo nghĩa trị tối ưu
của hàm mục tiêu trong hai bài toán là trùng nhau và từ
phương án tối ưu của bài toán này suy ra phương án tối
ưu của bài toán kia
Bài giảng Toán Cao cấp 1

Nguyễn Văn Tiến

 Ax  b

x  0

Bài giảng Toán Cao cấp 1

Nguyễn Văn Tiến

2



Chú ý:
Các ẩn mới và các ẩn phụ đều không âm.
Hệ số của các ẩn phụ trong hàm mục tiêu là 0.
Khi tìm được PATU của bài toán dạng chính tắc ta chỉ cần
tính giá trị của các ẩn ban đầu và bỏ đi các ẩn phụ thì sẽ
được PATU của bài toán dạng tổng quát đã cho.

Bài giảng Toán Cao cấp 1

Nguyễn Văn Tiến

Ví dụ

Ví dụ

• Cho bài toán QHTT:

• Đưa bài toán sau về dạng chính tắc:

f  x   120 x1  100 x2  max

f  x   2 x1  4 x2  x3  min

 2 x1  3x2  8

5 x1  3x2  15
 x  0, x  0
2
 1



Đưa bài toán về dạng chính tắc
• Bước 1. Kiểm tra ràng buộc chính
• Ràng buộc dạng nhỏ hơn:
ai1 x1  ai 2 x2  ...  ain xn  bi
•
• Ta cộng thêm ẩn phụ:

ai1 x1  ai 2 x2  ...  ain xn  xn k  bi
• Ràng buộc dạng lớn hơn:

ai1 x1  ai 2 x2  ...  ain xn  bi
• Ta trừ đi ẩn phụ:

Bài giảng Toán Cao cấp 1

Nguyễn Văn Tiến

Tính chất của tập phương án
• Định nghĩa. Đoạn thẳng nối hai điểm x1 và x2 được
định nghĩa:

x  R

n



x   x1  1    x2 , 0    1


là đoạn thẳng nối hai điểm x1, x2 thì một điểm biên có
giá trị hàm mục tiêu lớn nhất và điểm biên còn lại có
giá trị hàm mục tiêu nhỏ nhất.
Bài giảng Toán Cao cấp 1

Nguyễn Văn Tiến

Tập lồi và tính chất
• Tập S gọi là tập lồi nếu với hai điểm phân biệt
bất kỳ x1 và x2 thuộc S thì đoạn nối hai điểm x1
và x2 cũng nằm trong tập S.
Tập lồi

Không phải
Tập lồi
Bài giảng Toán Cao cấp 1

Ví dụ

Nguyễn Văn Tiến

Định lý

• Xét bài toán QHTT

• Tập S tất cả các phương án chấp nhận được của
bài toán quy hoạch tuyến tính dạng chính tắc là
một tập lồi.

f  x, y   4 x  3 y  max

bởi:
2

x   x1  1    x2    
3

• Cũng có giá trị hàm mục tiêu
là 9.
Bài giảng Toán Cao cấp 1

Bài giảng Toán Cao cấp 1

Nguyễn Văn Tiến

• Điểm x trong tập lồi S được gọi là điểm cực biên
nếu không thể biểu diễn được dưới dạng tổ
hợp lồi thật sự của hai điểm phân biệt của S.

Bài giảng Toán Cao cấp 1

Nguyễn Văn Tiến

4


16/04/2017

Điểm cực biên của tập hợp lồi

Phương pháp đồ thị


Tính chất tập phương án
• Tập hợp các phương án của một bài toán quy
hoạch tuyến tính là một tập lồi đa diện.
• Nếu tập hợp lồi đa diện này không rỗng và bị
chặn thì đó là một đa diện lồi. Số điểm cực biên
của nó là hữu hạn.

Bài giảng Toán Cao cấp 1

Nguyễn Văn Tiến

Bài giảng Toán Cao cấp 1

Phương pháp đồ thị
• Biểu diễn các ràng buộc lên đồ thị Oxy.
• Xác định phần được giới hạn bởi các ràng buộc là tập
phương án.
• Xác định các điểm cực biên (đỉnh) của tập phương án
thỏa mãn các ràng buộc.
• Xác định giá trị của hàm mục tiêu tại các điểm cực
biên.
• So sánh và suy ra phương án tối ưu

Bài giảng Toán Cao cấp 1

Phương án cực biên
• Định nghĩa. Điểm cực biên của tập các phương
án S trong bài toán QHTT gọi là phương án cực
biên.

 3

Nguyễn Văn Tiến

5


16/04/2017

Ví dụ 1

Ví dụ 3

• Biểu diễn đồ thị các bất đẳng
thức lên hệ trục tọa độ ta
được miền các phương án là
hình ngũ giác ABCDE. Các
điểm có tọa độ như sau A(0,0);
B(0,2); C(1,4); D(4,1); E(2,0) là
các điểm cực biên. lần lượt
thay các cực biên vào hàm
mục tiêu ta có f(A) = 0; f(B) = 2;
f(C) = 3; f(D) = -3; f(E) = -2.
• Vậy phương án tối ưu x*=(4,1)
tại đó hàm mục tiêu đạt giá trị
Min
Bài giảng Toán Cao cấp 1

C


công, thợ sắt có 3000 công, thợ mộc có 1500 công.
Định mức lao động của mỗi loại tàu được cho trong
bản:
100 mã lực

50 mã lực

Thợ sắt (3000)

150

70

Thợ rèn (2000)

120

50

Thợ mộc (1500)

80

40

• Hỏi xí nghiệp nên đóng tàu mỗi loại bao nhiêu để đạt
tổng số mã lực cao nhất?
Bài giảng Toán Cao cấp 1

Nguyễn Văn Tiến

x

40
x
1
2  1500

x1  0, x 2  0
Bài giảng Toán Cao cấp 1

Nguyễn Văn Tiến

Nguyễn Văn Tiến

• Phương trình A.x=b được viết lại dạng:

x1 A1  x2 A2  ...  xn An  0
•
•
•
•
•

Chọn m cột của ma trận A độc lập tuyến tính
Giả sử ta có các cột A1, A2, …, Am
Cho các biến tương ứng với các cột còn lại bằng 0
Giải phương trình ràng buộc với các biến còn lại
Nghiệm tìm được kết hợp với các biến đã cho bằng 0
tạo thành nghiệm cơ bản của bài toán.


• PACB có ít hơn m thành phần dương gọi là PACB suy
biến.
• Định lý. Nếu x=(x1,x2,…,xn) là PACB của tập các phương
án S= {A.x=b, x≥0} thì các cột của A tương ứng với xj>0
là độc lập tuyến tính.

Bài giảng Toán Cao cấp 1

Nguyễn Văn Tiến

Phương án cơ bản

Kiểm tra phương án cực biên

• Xét bài toán QHTT dạng chính tắc có tập các
ràng buộc:

• Chứng minh nó là phương án
• Đặt T={Aj|xj>0} trong đó Aj là các vectơ cột của
ma trận hệ số A.
• Chứng minh các vectơ của T tạo thành hệ vectơ
độc lập tuyến tính

S   x Ax  b, x  0
• Nghiệm cơ bản của hệ phương trình tuyến tính
A.x=b thỏa mãn điều kiện về dấu x≥0 được gọi
là phương án cơ bản của bài toán QHTT.

Bài giảng Toán Cao cấp 1


16/04/2017

Ví dụ
• Tìm tất cả các phương án cực biên của bài toán
QHTT:

f  4 x1  3x2  max
• Với các điều kiện:

Bài giảng Toán Cao cấp 1

Nguyễn Văn Tiến

Ví dụ
Nghiệm cơ bản

Phương án cực biên

Giá trị hàm
mục tiêu

X1=(3/2; 5/2;0;0)
X2=(3;0;1;0)
X3=4;0;0;-5)
X4=(0;5;-1;0)
X5=(0;4;0;3)
X6=(0;0;4;15)

Bài giảng Toán Cao cấp 1