Tiết 1
Mở đầu
1. Tối ƣu hóa là gì?
a) Định nghĩa
Tối ưu hóa là tác động lên quá trình, sự việc làm cho quá trình, sự việc đó
diễn ra theo một cách tốt nhất (không có phương án nào tốt hơn) theo một ý
nghĩa nào đó.
- Là quá trình tìm kiếm điều kiện tốt nhất (điều kiện tối ưu) của hàm số
được nghiên cứu.
- Là quá trình xác định cực trị của hàm hay tìm điều kiện tối ưu tương ứng
để thực hiện một quá trình cho trước.
- Để đánh giá tối ưu cần chọn chuẩn tối ưu (là các tiêu chuẩn công nghệ).
b) Cách biểu diễn bài toán tối ưu
Giả sử một hệ thống công nghệ được biểu diễn dưới dạng sau:
𝑌 = 𝑓(𝑥1 , 𝑥2 , … , 𝑥𝑘 )
Với 𝑥1 , 𝑥2 , … , 𝑥𝑘 là thành phần của vector thông số đầu vào
Hàm mục tiêu: Z = I (x1, x2,…, xk)
Bài toán được biểu diễn Zopt = optI (x1, x2,…,xk)

hoặc Zopt = max I (

x1,x2,…xk) : đối với bài toán max, hoặc Zopt = min I ( x1,x2,…xk) đối với bài
toán min.
𝑍 𝑜𝑝𝑡 : Hiệu quả tối ưu.
𝐼 𝑜𝑝𝑡 (𝑥1 , 𝑥2 , … , 𝑥𝑘 ): Nghiệm tối ưu hoặc phương án tối ưu của bài toán.
c) Thành phần cơ bản của bài toán tối ưu
 Hàm mục tiêu
- Là hàm phụ thuộc.
- Được lập trên cơ sở tiêu chuẩn tối ưu đã được lựa chọn.
1



- Nếu kết quả không phù hợp  xem lại từng bước hoặc làm lại từ việc đặt
vấn đề.
2. Các ví dụ thực tế
a) Bài toán về lập kế hoạch sản xuất
Ví dụ 1: Một kg nho có giá là 50.000đ, có thể sản xuất được 0,7 lít vang và 0.3
lít giấm. Một kg dứa có giá 20.000đ, có thể sản xuất được 0, 6 lít vang và 0, 1 lít
giấm.
Qua nghiên cứu thị trường, công ty nhận thấy nhu cầu tiêu thụ vang trong
năm 2014 là khoảng 5000 lít vang và 350 lít giấm. Tính số nho và dứa nguyên
liệu cần phải mua để đáp ứng nhu cầu với chi phí thấp nhất?
Gọi x1, x2 lần lượt là số nho và số dứa nguyên liệu cần mua để sản xuất 5000 lít
vang và 350 lít giấm.
Điều kiện: xj ≥0, j =1, 2. Khi đó
1) Chi phí nguyên liệu: f (x) = f (x1, x2) = 50x1 + 20x2 (1000 đ).
2) Lượng vang sản xuất: 0,7x 1 + 0,6x2 (lít)
Để đáp ứng nhu cầu tiêu thụ vang thì: 0,7x 1 + 0,6x2 ≥5000
3) Lượng giấm sản xuất: 0,3x1 + 0,1x2 (lít)
Để đáp ứng nhu cầu tiêu thụ giấm thì: 0,3x 1 + 0,1x2 ≥350
Vậy ta có mô hình bài toán:
(1) f (x) = f (x1, x2) = 50x1 +20x2  min
(2) 0,7x 1 + 0,6x2 ≥ 5000
0,3x 1 + 0,1x2 ≥ 350
(3) xj ≥ 0, j =1,2
Ví dụ 2: Một xí nghiệp cần sản xuất 3 loại bánh: bánh đậu xanh, bánh thập cẩm,
bánh dẻo. Lượng nguyên liệu đường, đậu cho bánh mỗi loại, lượng dự trữ
nguyên liệu, tiền lãi cho mỗi loại bánh được cho trong bảng sau:

3



0 kg

0,02 kg

300 kg

Tiền lãi

3000

2000

2500

Hãy lập mô hình bài toán tìm số lượng mỗi loại bánh cần sản xuất sao cho
không bị động về nguyên liệu mà tiền lãi được cao nhất?
Giải:
Gọi 𝑥1 , 𝑥2 , 𝑥3 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, j =1,2,3. Khi đó
1) Tiền lãi thu được là: f (x) = f (x1, x2, x3) = 3x1 + 2x2 + 2,5x3 (1000 đ).
2) Lượng đường được sử dụng là: 0,04x 1 + 0,06x2 + 0,05x3 (kg)
Để không bị động về nguyên liệu thì: 0,04x 1 + 0,06x2 + 0,05x3 ≤ 500
3) Lượng đậu được sử dụng là: 0,07x1 + 0,02x2 (kg)
Để không bị động về nguyên liệu thì: 0,07x1 + 0,02x2 ≤ 300
Vậy ta có mô hình bài toán:
(1) f (x) = f (x1, x2, x3) = 3x1 + 2x2 + 2,5x3  max
(2) 0,04x 1 + 0,06x2 + 0,05x3 ≤ 500
0,07x1 + 0,02x2 ≤ 300

1

7

C

6

3

4

Yêu cầu tối thiểu trong công thức về thành phần các chất dinh dưỡng A, B, C
trên một kg sản phẩm lần lượt là 17, 14, 14 g. Giá nguyên liệu T1, T2, T3 lần
lượt là 50.000 đ/kg, 40.000 đ/kg, 70.000 đ/kg.
Hãy xác định lượng nguyên liệu mỗi loại cần có trong công thức của sản phẩm
để đảm bảo yêu cầu về chất dinh dưỡng, giá thành sản phẩm là nhỏ nhất?
Gọi xj là lượng nguyên liệu Tj cần cho công thức của một sản phẩm (kg), j  1,3
Vậy ta có mô hình toán:
(1) f (x) = f (x1, x2, x3) = 5x1 + 4x2 + 7x3  min (10.000 đ)
(2) 7x 1 + 2x2 + 6x3 ≥ 17
5x1 + x2 + 7x3 ≥ 14
6x1 + x2 + 4x3 ≥ 14
(3) xj ≥ 0, j =1,2,3

5


CHƢƠNG I. ỨNG DỤNG QUY HOẠCH TUYẾN TÍNH – TÌM PHƢƠNG
ÁN TỐI ƢU TRONG SẢN XUẤT THỰC PHẨM

 Tập hợp tất cả các phương án của bài toán gọi là tập phương án. Ký
hiệu D, X, Y…
 Khái niệm phương án tối ưu (PATU):
 Bài toán minf: Một phương án làm cho hàm mục tiêu đạt cực tiểu gọi là
phương án tối ưu (PATU). Kí hiệu là x*
Nghĩa là: x  D : f ( x)  f ( x * )

6


 Bài toán maxf: Một phương án làm cho hàm mục tiêu đạt cực đại gọi là
PATU. Ký hiệu là x*
Nghĩa là: x  D : f ( x)  f ( x * )
 Bài toán có phương án tối ưu gọi là bài toán giải được.
 Giải bài toán QHTT là tìm các PATU của nó (nếu có) hoặc chỉ ra rằng bài
toán vô ngiệm, nghĩa là bài toán không có PATU.
b) Phương án cực biên (phương án cơ bản) của bài toán QHTT tổng quát
 Khái niệm ràng buộc chặt, lỏng
- Một ràng buộc gọi là chặt đối với phương án x nếu khi ta thay x vào ràng
n

buộc này thì xảy ra dấu bằng. ( aij x j  bi )
j 1

- Một ràng buộc gọi là lỏng đối với phương án x nếu khi ta thay x vào ràng
n

buộc này thì xảy ra dấu bất đẳng thức thực sự: (  aij x j  bi hoặc
j 1


  x1  x 2  x3  2 x 4  1
 x  0, x  0, x  0, x  0
2
3
4
 1

Chứng minh các kết quả sau:
1) x= (0, 1, 2, 0) là phương án cực biên không suy biến?
2) x= (0, 2, 1, 0) là phương án cực biên suy biến?
1.1.2. Dạng chính tắc của bài toán QHTT
a) Bài toán QHTT dạng chính tắc với n ẩn số là bài toán có dạng:
 Dạng đại số:
n

(1) f ( x)  c1 x1  c2 x2  .......  cn xn   c j x j  max(min)
j 1

(2) ai1 x1  ai 2 x2  ...  aim xm   aij x j  bi , i  1,2,..., m
(3) x j  0, j  1,2,..., n
 Dạng ma trận
 a11
a
A   11
 ...

a m1

a12
a 22

- x≥0
- Với quy ước: x=(x1, x1,…, xn) ≥0, xj≥0, j  1, n
Ví dụ: Bài toán sau có dạng chính tắc
(1) f ( x)  2 x1  4 x2  x3  6 x4  min
8


 x1  4 x2  x4  12
(2) 12 x1  3x2  x3  x4  3
 x  x  x  x  6
3
4
 1 2

(3) x j  0, j  1,2,3,4
Nhận xét: Bài toán QHTT dạng chính tắc là bài toán QHTT dạng tổng quát
trong đó
- Các rảng buộc chính đều là phương trình
- Các ẩn đều không âm
b) Phương án cực biên của bài toán dạng chính tắc
Xét bài toán chính tắc dạng ma trận:
- f(x)=<c, x>  min (max) (1)
- A.x=B

(2)

- x≥0

(3)


n

(1) f ( x)  c1 x1  c2 x2  .......  cn xn   c j x j  max(min)
j 1

(2) ai1 x1  ai 2 x2  ...  aim xm   aij x j  bi , i  1,2,..., m
(3) x j  0, j  1,2,..., n
Trong đó:
 Các hệ số tự do đều không âm
 Trong ma trận hệ số tự do có đủ m vector cột đơn vị: e1, e2,…,em

Khi đó:
 Các ẩn ứng với các vector cột đơn vị được gọi là các ẩn cơ bản. Cụ thể ẩn
ứng với vector cột đơn vị ek là ẩn cơ bản thứ k.

10


 Một phương án mà các ẩn cơ bản đều bằng 0 dược gọi là phương án cơ
bản.
 Một phương án cơ bản có đủ m thành phần dương được gọi là không suy
biến.
Ngược lại, một phương án có ít hơn m thành phần dương được gọi là
phương án suy biến.
Ví dụ: Xét bài toán QHTT sau:
(1) f ( x)  2 x1  4 x2  x3  6 x4  min
 x1  x4  x5  12

(2)  12 x1  x3  x6  3
x  x  x  x  6


12


Tiết 3
1.1.

Khái niệm và định nghĩa (tiếp)

1.1.4. Biến đổi dạng bài toán QHTT
1.1.4.1. Dạng tổng quát về dạng chính tắc
Ta có thể biến đổi bài toán dạng tổng quát về dạng chính tắc bằng các
bước sau:
Bước 1: Kiểm tra hệ ràng buộc chính
n

1)

Nếu có ràng buộc chính dạng

a
j 1

ij

x j  bi thì ta cộng vào vế trái ràng buộc
n

đó ẩn phụ xn+k nghĩa là ta thay ràng buộc


j 1

n

buộc dạng

a
j 1

ij

ij

x j  bi trong bài toán bằng ràng

x j  bi .

Chú ý: Các ẩn phụ là không âm và hệ số của các ẩn phụ đó trong hàm mục tiêu
là 0.
Bước 2. Kiểm tra dấu hiệu của ẩn số
1) Nếu ẩn x j  0 thì ta thực hiện phép đổi ẩn số x j   x 'j với x 'j  0
2) Nếu có ẩn x j có dấu tùy ý thì ta thực hiện phép biến đổi ẩn số x j  x 'j  x 'j'
với x 'j , x 'j'  0 .
Chú ý: 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.
13


Ví dụ: Biến đổi bài toán sau về dạng chính tắc

3
3

'
'
''
(3) x1  0, x2  0, x3  0, x3  0, x4  0, x5  0

1.1.4.2. Dạng chính tắc về dạng chuẩn
Từ bài toán dạng chính tắc ta có thể xây dựng dạng bài toán chuẩn như sau:
1) Khi gặp hệ số tự do bi
 2 x1  3x2  5x3  25
Ma trận hệ số của ràng buộc là
 4  6 5 01 0


A 7
0 1 10 0
  2  3 5 00 1



Vì A còn thiếu 2 vector cột đơn vị là e1 và e3 nên bài toán chưa có dạng chuẩn.
Thêm vào bài toán 2 ẩn giả x5 , x6  0 và xây dựng bài toán dạng chuẩn như sau:
(1) f ( x)  3x1  2 x2  2 x3  x4  Mx5  Mx6  min

15


 4 x1  6 x2  5 x3  x5  50

7 x1  x3  x4  0
(2) 
 2 x  3x  5 x  x  25
1
2
3
6


(3) x j  0, j  1,...,6

  9 x1  15 x3  50

(2)   6 x1  2 x4  120
 x  3x  5 x  45
2
3
 1

(3) x j  0, j  1,2,3,4
16


Giải
Thêm vào bài toán 2 ẩn phụ x5 , x6  0 ta được bài toán có dạng chính tắc như
sau
(1) f ( x)  3x1  2 x2  2 x3  x4  min
  9 x1  15 x3  x5  50

(2)   6 x1  2 x4  120
 x  3x  5 x  x  45
2
3
6
 1

(3) x j  0, j  1,...,6
Bài toán chưa có dạng chuẩn
Ta thấy các vế phải của hai phương trình ràng buộc thứ 2 và thứ 3 đều âm nên
bằng cách đổi dấu 2 vế phương trình ta được.
  9 x1  15 x3  x5  50

 1

17


(3) x j  0, j  1,...,7
Chú ý: Quan hệ giữa bài toán xuất phát (A) và bài toán mở rộng (B) được thể
hiện như sau:
- B vô nghiệm suy ra A vô nghiệm
- B có nghiệm có hai trường hợp:
1) Nếu mọi ẩn giả của PATU bằng 0 thì bỏ ẩn giả ta được PATU của A
2) Nếu có ít nhất một ẩn giả >0 thì A không có PATU

18


Tiết 4
1.2.

Phƣơng pháp đơn hình giải bài toán QHTT

1.2.1. Khái niệm và bản chất của phương pháp đơn hình
Năm 1949 nhà toán học người Mỹ D.D. Dantzig đã giải quyết bài toán quy
hoạch tuyến tính dạng chính tắc có ràng buộc:
n

x
j 1

j

trận cột tương ứng đã nằm trong cơ sở sẽ có giá trị khác không, và được xác
định từ điều kiện:
𝐴𝑥 = 𝑏 → 𝑥 = 𝐴−1 𝑏
Từ đây ta đi đến quy tắc tìm phương án cơ sở như sau:
1- Chọn một cơ sở của A bao gồm các ma trận cột
𝐴𝑘 , 𝐴𝑘+1 , … , 𝐴𝑚
2- Đặt 𝑥1 = 𝑥2 = ⋯ = 𝑥𝑘−1 = 𝑥𝑚 +1 = ⋯ = 𝑥𝑛 = 0
3- Xác định xj từ hệ phương trình:
𝐴𝑥𝑗 = 𝑏; 𝑗 = 𝑘, 𝑘 + 1, … , 𝑚
Ví dụ 1: Tìm phương án cơ sở của QHTT có ràng buộc như sau:
 2 x1  x 2  2
x  2x  2
 1
2

 x1  x 2  5
 x1  0, x 2  0

Hệ điều kiện ràng buộc cho dưới dạng bất đẳng thức, vì vậy để đưa bài
toán về dạng chính tắc ta thêm 3 ẩn phụ 𝑥3 , 𝑥4 , 𝑥5 ta có dạng phương trình như
sau:

20


 2 x1  x 2  x 3  2
x  2x  x  2
 1
2
4


Lưu ý: Có những phương án tuy là phương án cơ sở nhưng không phải là
phương án cơ sở chấp nhận được vì bản thân phương án đó không là phương án
chấp nhận được.
Ví dụ 2: Xét bài toán QHTT sau:
6𝑥1 + 2𝑥2 − 5𝑥3 + 𝑥4 + 4𝑥5 − 3𝑥6 + 12𝑥7 → 𝑚𝑖𝑛
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4
=4
𝑥1 +
𝑥5
=2
𝑥3 +
𝑥6 = 3
3𝑥2 + 𝑥3 +
𝑥7 = 6
𝑥𝑗 ≥ 0, 𝑗 = 1, 2, . . , 7
Phương trình ràng buộc có thể viết dưới dạng ma trận:
𝐴1 𝑥1 + 𝐴2 𝑥2 + 𝐴3 𝑥3 + 𝐴4 𝑥4 + 𝐴5 𝑥5 + 𝐴6 𝑥6 + 𝐴7 𝑥7 = 𝐵
1 
1 
1 
1 
0 
0 
0 
1 
0 
0 
0 
1 

 
 
 
1 
 3
1 
0 
0 
0 
1 

Ta thấy rằng các vector từ A1 đến A7 là một hệ độc lập tuyến tính, do đó cả
7 biến số đều có quyền đưa vào cơ sở. Nhưng vì số thành phần của 1 cơ sở chỉ
được phép tối đa bằng số ràng buộc m (trong trường hợp này là 4). Vì vậy số cơ
sở có khả năng tạo thành là rất nhiều. Ta chọn ngẫu nhiên 2 cơ sở bất kỳ. Ví
dụ: (𝐴4 , 𝐴5 , 𝐴6 , 𝐴7 ) và (𝐴2 , 𝐴5 , 𝐴6 , 𝐴7 )
 Với cơ sở thứ nhất:
𝑥1 = 𝑥2 = 𝑥3 = 0 → 𝑥4 = 4; 𝑥5 = 2; 𝑥6 = 3; 𝑥7 = 6
Do đó phương án cơ sở tương ứng là:
𝑥 = (0, 0,0,4, 2, 3, 6)
Phương án này thỏa mãn các điều kiện ràng buộc và điều kiện và dấu của
các biến, cho nên nó là phương án cơ sở chấp nhận được.

 Với cơ sở thứ 2:
22


𝑥1 = 𝑥3 = 𝑥4 = 0 → 𝑥2 = 4; 𝑥5 = 2; 𝑥6 = 3; 𝑥7 = −6
Do đó phương án cơ sở tương ứng là:
𝑥 = (0, 4,0,0, 2, 3, −6)

là:
𝑥𝑗𝑘 𝐴𝑗 𝑣à 𝑋𝑘 = 𝐴𝑗−1 𝐴𝑘

𝐴𝑘 =
𝑗 ∈𝐽

Ta sẽ xác định đại lượng ∆𝑘 (𝑘  J) bằng công thức:
∆𝑘 =

𝑐𝑗 𝑥𝑗𝑘 − 𝑐𝑘

∆𝑘 được gọi là ước lượng của biến 𝑥𝑘 theo cơ sở J.
Đối với các biến cơ sở 𝑥𝑗 thì ước lượng của chúng ∆𝑗 = 0
Dựa theo các ước lượng này ta sẽ đánh giá các phương án cơ sở qua 2 định lý
sau đây:
Định lý 2:
Nếu đối với phương án cơ sở 𝑥 0 ứng với cơ sở 𝐽0 của bài toán min dạng
chính tắc mà tồn tại ít nhất một ∆𝑘 > 0 (∆𝑘 < 0 với bài toán Max thì có thể tìm
được phương án khác, chấp nhận được 𝑥 1 với có sở 𝐽1 có giá trị hàm mục tiêu bé
hơn (lớn hơn – với bài toán Max)
Định lý 3 (Tiêu chuẩn tối ưu):
Nếu đối với phương án cơ sở 𝑥 0 ứng với cơ sở 𝐽0 của bài toán Min dạng
chính tắc mà ∆𝑘 ≤ 0 ∀𝑘 𝐽0 (∆𝑘 ≥ 0 ∀𝑘 𝐽0 – Đối với bài toán Max) thì 𝑥 0 là
phương án tối ưu.
Hàm mục tiêu sẽ đạt giá trị Max nếu nó bị chặn trên và đạt giá trị Min nếu
bị chặn dưới.
Để xét hàm mục tiêu có bị chặn không ta sử dụng định lý:
Định lý 4 (Kiểm tra tính không giải được của bài toán):
24