[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ
Chương 1
TỔNG QUAN VỀ LÝ THUYẾT PHÂN TÍCH HỆ THỐNG
Tài liệu chính:
“Phân tích và tối ưu hóa hệ thống” – NXB Nông nghiệp năm 2007 của PGS. Phó Đức Anh
Ba chương chính
I.
II.
III.

Tổng quan về PTHT
Mô hình hóa hệ thống
Tối ưu hóa

I. Giới thiệu chung.
Lý thuyết phân tích hệ thống ra đời do nhu cầu giải quyết các vấn đề liên qua đến các hệ thống bao gồm
con người với các sản phẩm do họ tạo ra trong mối kiên kết với môi trường tự nhiên, chẳng hạn như
- Gia tăng tai nạn giao thông
- Nhu cầu năng lượng của con người trong xã hội ngày càng phát triển
- Bài toán đô thị hóa
- Quản lý vốn, sức lao động, tài nguyên…trong kinh doanh.
- Vấn đề quản lý nhà nước…
Thực tế:
- Đối tượng nghiên cứu ngày càng phức tạp:
+ Từ đơn lẻ đến nhiều thành phần
+ Từ một vùng sang nhiều vùng
+ Từ trạng thái tĩnh sang trạng thái động
+ Số lượng và tính chất ngành nghế thay đổi
- Đặc trưng liên ngành ngày càng rõ nét:
+ Cần sự hợp tác của nhiều chuyên gia trong nhiều lĩnh vực khác nhau
+ Làm việc theo nhóm…

Tuy nhiên: Máy tính đã và đang giúp con người giải quyết một số quá trình trong việc tìm lời giải. Và
đích tới của mọi vấn đề chính là : Bài toán tối ưu
Mục đích chính của PTHT:
+ Trợ giúp cho các nhà làm chính sách và ra quyết định giải quyết và quản lý ngày càng tốt hơn các
vấn đề mà họ đang đảm trách.
+ Nhà phân tích cần đưa ra các thông tin, bằng chứng và cơ sở lý luận liên quan đến hệ thống, sau đó
phải đưa ra được các giải pháp và tiên lượng được các hậu quả có thể xảy ra.
1|P a g e


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ
II. Đặc điểm chính của PTHT
1. Đối tượng nghiên cứu
2. Cấu trúc hệ thống
3. Cần nhìn nhận vấn đề trong sự vận động của sự việc
4. Trong nhiều phương án khả thi cần lựa chọn quyết định tối ưu
5. Tính liên ngành
6. Tính bất định.
III. Phương pháp luận
Các bước và các giai đoạn của quá trình PTHT
- Đặt bài toán
- Nhận dạng, thiết kế và sang lọc các phương án khả thi
- Dự báo tình trạng
- Nhận dạng kết quả
- So sánh và xếp hạng các phương án
- Viết tài liệu
Ví dụ: Vấn đề giảm tai nạn giao thông trên các tuyến đường cao tốc
+ Mục tiêu: Quốc hội cần đưa ra một đạo luật mới để nâng cao mức độ an toàn giao thông, giảm thiểu
các tai nạn trên các tuyến đướng với các tiêu chí cụ thể.
+ Các giải pháp:

- Quy định về thắt dây an toàn khi lái xe ô tô, đội mũ bảo hiểm đúng chuẩn khi điều khiển xe gắn
máy.
- Quy định lại về tố độ tối đã trên các tuyến đường
- Nâng cao chuẩn cấp bằng lái xe
Sau đó cần phân tích tỷ mỷ ba phươn án vừa nêu:
-

Thấy rõ chi tết các điểm mạnh, điểm yếu, các tác động tích cực cũng như tiêu cực của mỗi giải
pháp.
Dự kiến được các hậu quả có thể xảy ra sau khi thực hiện các phương án (chẳng hạn: khi đưa ra
phương án “Toàn dân đội mũ bảo hiểm, các nhà hochj định chính sách cần hình dung được các
ảnh hưởng tích cực của giải pháp này ra sao, cũng như thấy được những khó khăn và phản ứng
tiêu cực của một bộ phận dân chúng như: Cho thuê mũ, đội mũ không đạt chuẩn vì muốn mũ bảo
hiểm phải mang tính thời trang…)

Nhà phân tích cần phải:
-

2|P a g e

Định lượng và đưa ra các tiêu chuẩn đánh giá để xếp hạng 3 phương án đưa ra
Thu thập tương đối đầy đủ và chính xác các số liệu cần thiết
Nắm vững mối tương quan giũa các thành phần trong hệ thống (Ví dụ: tốc đọ tối đa được quy định
theo các thời kỳ; Xét tương quan(quan hệ thống kê) giữa tốc độ quy định và số tai nạn giao thông
trong từng năm, tính trạng làm việc của cảnh sát giao thông, các trạm kiểm soát giao thông…)
Chẳng hạn: nếu giảm tốc độ tối đa thì sẽ kéo theo: Tăng số trạm xăng trên đường cao tốc, Tăng
cường lược lượng CSGT, Tăng quỹ lương cho các nhân viên bán xăng và CSGT…


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ

Chương 3
TỐI ƯU HÓA
Bài số 1: CỰC TRỊ TỰ DO CỦA HÀM NHIỀU BIẾN
I. Các định nghĩa.
1. Cực tri của hàm hai biến f (x , y )
Định nghĩa 1: Cho hàm số u = f (x, y ) xác định trong lân cận của P0 (x 0, y 0 ) .
a) Nếu f (x , y ) < f (x 0 , y0 ) với mọi (x , y ) trong lân cận của P0 (x 0, y 0 ) trừ đi điểm đó thì ta nói rằng
hàm số u = f (x, y ) đạt cực đại tại P0 (x 0, y 0 ) và (x 0, y0 ) gọi là điểm cực đại của hàm số, u0 = f (x 0, y0 )
gọi là giá trị cực đại của hàm số đó.
b) Nếu f (x , y ) > f (x 0 , y0 ) với mọi (x , y ) trong lân cận của P0 (x 0, y 0 ) trừ đi điểm đó thì ta nói rằng
hàm số u = f (x, y ) đạt cực tiểu tại P0 (x 0, y 0 ) và (x 0, y0 ) gọi là điểm cực tiểu của hàm số, u0 = f (x 0, y0 )
gọi là giá trị cực tiểu của hàm số đó.
Nếu hàm số đạt cực đại (hoặc cực tiểu) tại (x 0, y0 ) (điểm này phải là điểm trong của MXD của z = f (x, y ) )
thì ta gọi chung đó là điểm cực trị của hàm số và giá trị của hàm số lúc này gọi là cực trị của hàm số đó.

Định nghĩa 2: Cho hàm số u = f (x, y) = f (P ) có miền xác định D.
2

f (x, y ) ≥ m ) với mọi (x , y ) trong miền D ⊆ ℝ , hơn nữa tồn tại

Nếu

f (x, y ) ≤ M

(t.ư.

P0 = (x 0, y 0 ) thuộc D sao cho

M = f (x 0, y0 ) (t.ư. m = f (x 0 , y0 ) ) thì ta nói rằng hàm số u = f (x, y ) đạt giá trị lớn nhất (t.ư. nhỏ nhất) tại
(x 0, y0 ) và u0 = f (x 0, y0 ) là giá trị lớn nhất (t.ư. giá trị nhỏ nhất) của hàm số đó trên miền D.

Chú ý: Giá trị bé nhất (cực tiểu tuyệt đối) và giá trị lớn nhất (cực đại tuyệt đối) không nhất thiết phải đạt
được tại điểm trong của MXĐ (nếu MXĐ là miền đóng), nó có thể đạt được tại một điểm biên của MXĐ.
2. Điều kiện cần của cực trị tự do
Nếu hàm u = f (x, y) = f (P ) đạt cực đại hoặc cực tiểu (tương đối) tại P0 = (x 0, y 0 ) và có các ĐHR fx và
fy tại P0 = (x 0, y 0 ) thì ta có:

3|P a g e


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ

 f
 x (x ,y ) = 0
⇔ gradf (x 0, y 0 ) = 0 .
 0 0
 fy
=0
 (x 0 ,y0 )
Như vậy: Cực trị tự do của hàm hai biến (nếu có) chỉ có thể đạt tại các điểm tới hạn của nó.
Điểm tới hạn là một điểm thuộc MXĐ mà tại đó các ĐHR triệt tiêu (điểm dừng) hoặc ít nhất một trong các
ĐHR không xác định. Trong chương trình, chúng ta chỉ xét cực trị tại các điểm dừng, tức là chỉ xét cực trị tại
các điểm là nghiệm của hệ:

 f (x , y ) = 0
x
.

 fy (x , y ) = 0

3. Điều kiện đủ của cực trị tự do.

a) Đối với hàm một biến y = f (x ) : Nếu x 0 là một điểm dừng của hàm số ( f '(x 0 ) = 0 ), khi đó tiêu chuẩn
nào để khẳng định x 0 là điểm cực trị của hàm số đó?
+ Quy tắc 1: Nếu có sự đổi dấu của đạo hàm cấp một f '(x ) khi qua x 0 .
+ Nếu f "(x 0 ) ≠ 0 và từ dấu của f "(x 0 ) ta suy ra kết luận:

f "(x 0 ) > 0 : x 0 là điểm cực tiểu
f "(x 0 ) < 0 : x 0 là điểm cực đại.
b) Đối với hàm hai biến
Nếu f (x, y ) có đạo hàm riêng đến cấp hai liên tục trong một lân cận của điểm tới hạn (x 0 , y 0 ) và nếu số D
(gọi là biệt số) xác định bởi:

D = fxx (x 0, y0 ) fyy (x 0, y 0 ) −  fxy (x 0 , y0 )



2

(2)

thì (x 0 , y 0 ) là
i) Điểm cực đại nếu D>0 và fxx (x 0 , y 0 ) < 0 ;
ii) Điểm cực tiểu nếu D>0 và fxx (x 0 , y 0 ) > 0 ;
iii) Điểm yên ngựa nếu D<0.
Hơn nữa, nếu D=0 thì chưa thể đưa ra kết luận, và bất kì khả năng nào từ (i) đến iii) đều có thể xảy ra.
Đặt A = fxx (x 0, y 0 ), B = fxy (x 0, y 0 ), C = fyy (x 0 , y 0 ) , khi đó ta có bảng tổng kết sau:

4|P a g e

D = AC − B 2


A

Kết luận về (x 0 , y 0 )

>0

<0

Cực đại

>0

>0

Cực tiểu

<0

Điểm yên ngựa

=0

Chưa có kết luận


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ
4. Đối với hàm n-biến
a) Định nghĩa.
Định nghĩa 1: Cho hàm số u = f (x 1, x 2,..., x n ) có tập xác định Df ⊆ ℝn , M 0 là một điểm trong của


Df .
a) Nếu f (M ) < f (M 0 ) với mọi M trong lân cận của M 0 trừ đi điểm đó thì ta nói rằng hàm số

u = f (.) đạt cực đại tại M 0 và M 0 gọi là điểm cực đại của hàm số, u0 = f (M 0 ) gọi là giá trị cực đại
của hàm số đó.
b) Nếu f (M ) > f (M 0 ) với mọi M trong lân cận của M 0 trừ đi điểm đó thì ta nói rằng hàm số

u = f (.) đạt cực tiểu tại M 0 và M 0 gọi là điểm cực tiểu của hàm số, u0 = f (M 0 ) gọi là giá trị cực tiểu
của hàm số đó.

Định nghĩa 2: Nếu f (M ) ≤ K (t.ư. f (M ) ≥ k ) với mọi M thuộc miền D ⊆ ℝ n , hơn nữa tồn tại

M 0 thuộc D sao cho K = f (M 0 ) (t.ư. k = f (M 0 ) ) thì ta nói rằng hàm số u = f (.) đạt giá trị lớn nhất (t.ư.
nhỏ nhất) tại M 0 và u0 = f (M 0 ) là giá trị lớn nhất (t.ư. giá trị nhỏ nhất) của hàm số đó trên miền D.

Chú ý: Trong bài toán tìm GTLN (cực đại tuyệt đối) hoặc GTNN (cực tiểu tuyệt đối) trên một miềm
đóng thì điểm M 0 có thể là điểm trong hoặc điểm biên của miền đang xét.
b) Điều kiện cần.
Nếu u = f (.) = f (M ) đạt cực trị tương đối tại M 0 và có các đạo hàm riêng theo các biến tại M 0 thì
gradf (M 0 ) = 0 .
c) Điều kiện đủ.
Định nghĩa:
Ma trận Hessian: Xét hàm số u = f (M ) = f (x 1, x 2,..., x n ) có các đạo hàm riêng liên tục tới cấp 2, khi đó
ma trân Hessian được xác định bởi:

 ∂2 f
H (M ) = 
 ∂x ∂x
 i j





i, j =1,2,...,n

 fx x
 11
f
=  x2x1
⋮

 fx x
 n1

fx x

⋯

fx x

⋯

⋮

⋮

1 2

2 2


fx x

⋯

n 2

fx x 
1 n

fx x 
2 n
.
⋮ 

fx x 
n n 

Tử thức chính của một ma trận vuông là định thức con có đường chéo chính nằm trên đường chéo chính của

( )

ma trận. Xét A = aij

i , j =1,...,n

∈ M (n ) , khi đó có n tử thức chính

∆1 = a11; ∆2 =

5|P a g e


a11 a12
a21 a22

a11 a12 a13
; ∆ 3 = a21 a22 a23 ;...
a 31 a 32 a 33


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ
a12

⋯

a1n

a21 a22

⋯

a 2n

⋮

⋮

a11

∆n = det A =


⋮

⋮

.

an 1 an 2 an 3 ann
Khi đó với M 0 ∈ TXD :
+ H (M 0 ) được gọi là xác định dương nếu và chỉ nếu ∆j (M 0 ) > 0, ∀j = 1,2,..., n .
+ H (M 0 ) được gọi là xác định âm nếu và chỉ nếu (−1)j ∆ j (M 0 ) > 0, ∀j = 1,2,..., n .

∆ > 0
1
+ H (M 0 ) được gọi là bán xác định dương nếu và chỉ nếu 
.

∆
 j ≥ 0, ∀j = 2,..., n
∆ < 0
1
+ H (M 0 ) được gọi là bán xác định âm nếu và chỉ nếu 
.

(−1)j ∆ j ≥ 0, ∀j = 2,..., n


Điều kiện đủ: Giả sử u = f (M ) = f (x 1, x 2,..., x n ) có điểm dừng M 0 và tại đó hàm số có đạo hàm liên tục
tới cấp 2. Khi đó
Trường hợp 1: Nếu H (M 0 ) là xác định dương thì M 0 là điểm cực tiểu (tương đối) của hàm số.
Nếu H (M 0 ) là xác định âm thì M 0 là điểm cực đại (tương đối) của hàm số.

Trường hợp 2: Nếu H (M 0 ) là bán xác định dương (hoặc bán xác định âm) thì M 0 là điểm nghi vấn của
hàm số.
Trường hợp 3: Nếu H (M 0 ) không rơi vào các trường hợp trên thì M 0 không phải là điểm cực trị của hàm
số.
d) Cực trị tuyệt đối.
Bài toán: Tìm cực trị tuyệt đối (GTLN, GTNN) của hàm u = f (M ) = f (x 1, x 2,..., x n ) trên miền đóng D .
Giải:
+ Bước 1: Tìm cực trị tương đối trong miền D (chỉ xét những điểm trong của miền)
+ Bước 2: Tìm giá trị của hàm số trên biên
+ Bước 3: So sánh các giá trị để xác định GTLN và GTNN
Chú ý: Nếu ta xét bài toán trên miền mở D (không xác định biên) thì Bước 2 ta sẽ thay bằng: Tìm giới hạn
của hàm số u = f (M ) khi M tiến dần tới biên của miền D .
5. Một số ví dụ.
Ví dụ 1 (VD 1 trang 71)
+ Hàm giá thành sản xuất: C (x 1, x 2 ) = (x 1 + x 2 )2 + 15
6|P a g e


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ
+ Tiền bán hang: p1x 1 + p2x 2
2

+ Hàm lợi nhuận: P (x 1, x 2 ) =

∑px

i i

(


)

− C x 1, x 2 = ???

i =1

{

}

+ Miền quan tâm: D = (x 1, x 2 ) | 0 ≤ x 1 ≤ 12; 0 ≤ x 2 ≤ 10 .
Hướng dẫn giải:
+ Phát biểu bài toán (dạng Toán học)
+ Tìm điểm dừng
+ Lập ma trân Hessian H
+ Tính giá trị các phần tử của H tại điểm dừng
+ Xác định các tử thức chính của H tại điểm dừng
+ Từ điều kiện đủ suy ra kết luận của bài toán.
Bài tập 1: Tìm kích thước của một hình hộp chữ nhật có thể tích V = 4 cho trước sao cho tổng diện tích xung
quanh và một đáy của nó đạt giá trị bé nhất?
Hướng dẫn:
+ Phân tích bài toán, xác định hàm cần tìm
+ Gọi kích thước của hình hộp là: x , y, z trong đó z là chiều cao, x , y, z > 0
+ Diện tích xung quanh và một đáy: S = xy + 2yz + 2zx
+ Từ gt: xyz = 4 ⇒ z =

4
8 8
và do đó: S = xy + +
xy

x y

+ Tìm điểm dừng của S
+ Tìm ma trân Hesian
+ Từ điều kiện đủ suy ra kết luận.
Bài tập 2: Tìm cực trị tự do của hàm hai biến

z (x , y ) = 3x 2 + 2xy + y 2 + 10x + 2y + 1.
Hướng dẫn:
Bài tập về nhà: Dạng I.1 + I.2 +I.5: mỗi dạng làm 5 bài đầu tiên
Đọc trước Mục I.4 trang 74 chuẩn bị cho Bài giảng: Cực trị có điều kiện

7|P a g e


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ
Bài số 2: CỰC TRỊ TỰ CÓ ĐIỀU KIỆN
Bài toán tổng quát: Cho hàm f (M ),

M (x 1; x 2 ;...; x n ) ∉ D f ⊆ ℝ n . Tìm cực trị của f (M ) thỏa mãn m

điều kiện sau ( m < n ):

g i (M ) = bi , i = 1, 2,..., m ( bi : là các hằng số).

1. Nếu n = 2, m = 1 : Tìm cực trị của z = f (x 1; x 2 )

(1)

thỏa mãn điều kiện g (x 1; x 2 ) = b


(2)

Giải:
Cách 1: Nếu điều kiện (2) dễ dàng rút được ẩn này theo ẩn kia, khi đó thế lên (1) ta sẽ nhận được bài toán tìm
cực trị của hàm một biến.
Cách 2: Phương pháp nhân tử Lagrange
*) Điều kiện cần:
+ Lập hàm Lagrange: L(x 1; x 2 ; λ) = f (x 1; x 2 ) + λ(g (x 1; x 2 ) − b )

L = 0
 f + λg = 0
x1
 x1
 x1
+ Giải hệ: Lx = 0 ⇔  fx + λ g x = 0 , nếu hệ có nghiệm M 0 (x 01 ; x 02 ; λ 0 )
2
2
2
L = 0
g (x ; x ) − b = 0
 λ
 1 2

*) Điều kiện đủ:
+ Lập ma trận viền Hesian

0

−

H =
g
 x1
g x 2

|

gx

|

−

1

| Lx x

1 1

| Lx x

2 1

gx 
2

− 
.
Lx x 
1 2 

Lx x 
2 2 

+ Xét (n − m ) tử thức chính sau cùng: trường hợp này ta chỉ cần xét ∆ 3 = H (M 0 ) , khi đó:
Trường hợp 1: Nếu H (M 0 ) xác định dương (tức ∆ 3 < 0 ) thì M 0 là điểm cực tiểu (tương đối)
Trường hợp 2: Nếu H (M 0 ) xác định âm (tức ∆ 3 > 0 ) thì M 0 là điểm cực đại (tương đối).

∆ ≤ 0
Trường hợp 3: Nếu H (M 0 ) bán xác định dương (hoặc bán xác định âm):  3
thì điểm M 0 là điểm
∆
≥
0
 3
nghi vấn.
Trường hợp 4: Nếu H (M 0 ) không xác định (trường hợp này ∆ 3 = 0 ) thì điểm M o không phải là điểm
cực trị có điều kiện.

8|P a g e


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ
Ví dụ 4 (Tr.76). (hướng dẫn)
Ví dụ 5(Tr. 77). (hướng dẫn)

2. Nếu n = 3; m = 1 : Tìm cực trị của f (x 1; x 2 ; x 3 )

(1)

thỏa mãn điều kiện g (x 1; x 2 ; x 3 ) = b


(2)

Giải:
*) Điều kiện cần
+ Lập hàm Lagrange: L(x 1; x 2 ; x 3 ; λ) = f + λ(g − b )

Lx = fx + λ g x = 0, j = 1, 2, 3
j
j
+ Xét hệ  j
, nghiệm M 0 (x 01 ; x 02 ; x 03 ; λ 0 ) của hệ (nếu có) là điểm dừng.
Lλ = g − b = 0

*) Điều kiện đủ :
+ Lập ma trận Hesian viền

0

g
HA =  1
g
 2
g 3

gx

1

gx


2

Lx x

Lx x

Lx x

Lx x

Lx x

Lx x

1 1

2 1

3 1

1 2

2 2

3 2



Lx x 

1 3
Lx x 
2 3 
Lx x 
3 3 

gx

3

+ Khi đó xét n − m = 3 − 1 = 2 tử thức chính sau cùng đó là ∆ 3 ; ∆ 4 ; Khi đó

Trường hợp 1: Nếu H (M 0 ) xác định dương (tức ∆ 3 < 0; ∆ 4 < 0 ) thì M 0 là điểm cực tiểu (tương đối).

Trường hợp 2: Nếu H (M 0 ) xác định âm (tức ∆ 3 > 0; ∆ 4 < 0 ) thì M 0 là điểm cực đại (tương đối).

 ∆ ≤ 0; ∆ 4 ≤ 0
Trường hợp 3: Nếu H (M 0 ) bán xác định dương (hoặc bán xác định âm):  3
thì điểm M 0 là
 ∆ 3 ≥ 0; ∆ 4 ≤ 0
điểm nghi vấn.
Trường hợp 4: Nếu H (M 0 ) không xác định thì điểm M o không phải là điểm cực trị có điều kiện.
Ví dụ 6 (Tr.79: (hướng dẫn)

9|P a g e


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ
3. Nếu n = 3; m = 2 : Tìm cực trị của f (x 1; x 2 ; x 3 )


(1)

g (x ; x ; x ) = b1
thỏa mãn 2 điều kiện  1 1 2 3
g 2 (x 1; x 2 ; x 3 ) = b2

(2)

Giải:
*) Điều kiện cần
+ Lập hàm Lagrange: L(x 1; x 2 ; x 3 ; λ1; λ 2 ) = f + λ 1(g 1 − b1 ) + λ 2 (g 2 − b2 )

Lx = fx + λ 1g 1,x + λ 2g 2,x = 0, j = 1, 2, 3
j
j
j
 j
+ Xét hệ Lλ = g1 − b1 = 0
, nghiệm M 0 (x 01 ; x 02 ; x 03 ; λ 1,0 ; λ 2,0 ) của hệ (nếu có) là
1
L = g − b = 0
2
2
 λ2
điểm dừng.

*) Điều kiện đủ :
+ Lập ma trận Hesian viền

0


0
H A = g1,x1

g1,x2
g
 1,x 3

0

g1,x

0

g2,x

1

g2,x

g2,x

1

Lx x

Lx x

2


Lx x

Lx x

3

Lx x

Lx x

g2,x
g2,x

1

1 1

2 1

3 1

g1,x

2

2

1 2

2 2


3 2

g1,x 
3

g2,x 
3
Lx x 
1 3 
Lx x 
2 3
Lx x 
3 3 

+ Khi đó xét n − m = 3 − 2 = 1 tử thức chính sau cùng đó là ∆ 5 ; Khi đó

Trường hợp 1: Nếu H (M 0 ) xác định dương (tức ∆ 5 > 0 ) thì M 0 là điểm cực tiểu (tương đối).
Trường hợp 2: Nếu H (M 0 ) xác định âm (tức ∆ 5 < 0 ) thì M 0 là điểm cực đại (tương đối).

∆ ≥ 0
Trường hợp 3: Nếu H (M 0 ) bán xác định dương (hoặc bán xác định âm):  5
thì điểm M 0 là điểm
 ∆ 5 ≤ 0
nghi vấn.
Trường hợp 4: Nếu H (M 0 ) không xác định (trường hợp này ∆ 5 = 0 ) thì điểm M o không phải là điểm
cực trị có điều kiện.

10 | P a g e



[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ
Ví dụ: Tìm cực trị tương đối của hàm số u = f (x 1 ; x 2 ; x 3 ) = x 2 + y 2 + z 2

x + y + z − 1 = 0
thỏa mãn 2 điều kiện 
.
 3x + 2y + z − 6 = 0
Hướng dẫn: Ở đây n = 3; m = 2
+ Hàm Lagrange: L = x 2 + y 2 + z 2 + λ(x + y + z − 1) + µ(3x + 3y + z − 6)

L
 x
Ly
+ Giải hệ 
Ly
L
 λ
Lµ

=0
=0
 7 1 −5 
= 0 tìm được điểm dừng M 0  ; ;

3 3 3 
=0
=0

+ Xác định ma trận viền Hesian

+ Vì n = 3; m = 2 nên xét tử thức chinh ∆ 5 ....
+ Kết luận,
Ví dụ 7(Tr. 80): hướng dẫn
Ví dụ 8(Tr.81): hướng dẫn

Trường hợp tổng quát: Xét hàm số f (M ),

M (x 1; x 2 ;...; x n ) ∉ D f ⊆ ℝ n . Tìm cực trị của f (M ) thỏa

mãn m điều kiện sau ( m < n ):

g i (M ) = bi , i = 1, 2,..., m ( bi : là các hằng số).
Giải:

*) Điều kiện cần
+ Lập hàm Lagrange: L(M ; Λ ) = f (M ) +

m

∑ λ (g (M ) − b )
i

i

i

i =1

m


Lx j = fx j + ∑ λ i g i ,x j − bi = 0, j = 1, 2, 3,..., n
+ Xét hệ 
, nghiệm M 0 (x 01 ; x 02 ; x 03 ;..., x 0n ; λ 1,0 ;...; λ m ,0 ) của
i =1
Lλ = g i ,x − bi = 0, i = 1, 2,..., m
j
 i
hệ (nếu có) là điểm dừng.

(

11 | P a g e

)


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ
*) Điều kiện đủ :
+ Lập ma trận Hesian viền


O

HA = 
 ℑT



 ∂g
ℑ= i

 ∂x
 j
 ∂ 2L 


 ∂x x 
i
j












+ Tại các điểm dừng xét (n − m ) tử thức chính sau cùng đó là ∆ 2m +1, ∆ 2m +2, ..., ∆ n +m ; Khi đó
Trường hợp 1: Nếu H (M 0 ) xác định dương (tức (n − m ) tử thức chính sau cùng đều dương khi m −
chẵn, hoặc đều âm khi m − lẻ) thì M 0 là điểm cực tiểu (tương đối).

Trường hợp 2: Nếu H (M 0 ) xác định âm (tức (n − m ) tử thức chính sau cùng có dấu xen kẻ và ∆2m +1 < 0

m − chẵn, hoặc ∆2m +1 > 0 khi m − lẻ) thì M 0 là điểm tiểu đại (tương đối).
Trường hợp 3: Nếu H (M 0 ) bán xác định dương (hoặc bán xác định âm): giống 2 trường hợp trên chỉ khác
dấu < , > được thay bởi ≤ , ≥ tương ứng thì điểm M 0 là điểm nghi vấn.
Trường hợp 4: Nếu H (M 0 ) không xác định thì điểm M o không phải là điểm cực trị có điều kiện.


Mặc dù vậy, trong thực tế rất khó sử dụng, chẳng hạn có những trường hợp không tồn tại đạo hàm riêng thì ta
không thế sử dụng phương pháp trên, khi đó ta cần có phương pháp hữu hiệu khác để giải quyết vấn đề đó.

Bài tập về nhà: Dạng I.1 + I.2 +I.5: mỗi dạng làm 3 bài 8, 9, 10
Đọc trước Mục III.1 và III.2 từ trang 89 chuẩn bị cho Bài giảng:
Quy hoạch tuyến tính. Phương pháp hình học

12 | P a g e


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ
CƠ SỞ QUY HOẠCH TUYẾN TÍNH
Bài số 3: PHƯƠNG PHÁP HÌNH HỌC
Xét bài toán: Tìm min (max) của

u(M ) = c1x 1 + c2x 2 + ... + cn x n
thỏa mãn m − điều kiện (m < n ; m , n ∈ ℕ * )

a11x 1 + a12x 2 + ... + a1n x n = (≤)b1

a21x 1 + a22x 2 + ... + a 2n x n = (≤)b2

…
am 1x 1 + am 2x 2 + ... + amn x n = (≤)bn

ở đây ai , j và bj đã biết (i = 1,.., n; j = 1,..., m ) , tìm x i = ?, (x i ≥ 0; i = 1,2,..., n ) .

A.X = B
X ≥ 0


Cách viết khác: Tìm min (max) của hàm L(ℂ; X ) thỏa mãn 

x 
b 
 1
1
với A = (aij )m ×n ; X = ⋮  ; B = ⋮  .
x 
b 
 n
 m
I. MỘT SỐ BÀI TOÁN ĐIỂN HÌNH
Xét bảng dữ liệu sau:

F1

F2

…

Fj

…..

Fn

N1

a11


a12

…..

a1j

…..

a1n

b1

N2

a 21

a 22

…..

a2 j

…..

a2n

b2

…..


…..

…..

…..

…..

…..

…..

…..

Ni

ai 1

ai 2

…..

aij

…..

ain

bi


…..

…..

…..

…..

…..

…..

…..

…..

Nm

am 1

am 2

…..

amj

…..

amn


bm

c1

c2

…..

cj

…..

cn

1. Bài toán vận tải tĩnh
Với aij = 1; ci , bj đã biết, bài toán vận tải tĩnh được phát biểu như sau:

13 | P a g e


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ

A.X = B

Tìm min (max) của L(ℂ; X ) thỏa mãn 

X ≥ 0

.


2. Bài toán thực dưỡng.

A.X ≥ B, (B ≥ 0)
.
X ≥ 0

Tìm min (max) của L(ℂ; X ) thỏa mãn 
3. Bài toán phân bổ tài nguyên

A.X ≤ B, (B ≥ 0)

Tìm min (max) của L(ℂ; X ) thỏa mãn 

X ≥ 0

.

4. Bài toán hỗn hợp.

A.X ≥ / ≥ B, B ≥ 0
.
X ≥ 0

Tìm min (max) của L(ℂ; X ) thỏa mãn 

II. PHƯƠNG PHÁP HÌNH HỌC GIẢI BÀI TOÁN QHTT.
1. Đường thẳng trong Oxy .
+ Phương trình: Ax + By + C = 0,


(A2 + B 2 ≠ 0) .

+ Đường thẳng chia mặt phẳng thành miền:

{
: {(x , y ) ∈ ℝ
: {(x , y ) ∈ ℝ

}
| Ax + By + C = 0}
| Ax + By + C < 0}

R+ : (x , y ) ∈ ℝ2 | Ax + By + C > 0
R0
R−

2

2

2. Một số khái niệm
+ Miền chấp nhận được là miền thỏa mãn tất cả các điều kiện ràng buộc của bài toán.
+ Bài toán Quy hoạch tuyến tính được xét trên miền chấp nhận được là miền lồi được gọi là bài toán Quy
hoạch tuyến tính lồi.
+ Trong bài toán Quy hoạch tuyến tính lồi, ta gọi mỗi đỉnh của Miền chấp nhận được là một điểm cực
biên.
Ví dụ 1: Xét đường thẳng trong Oxy :

(d ) : 3x + 4y − 12 = 0


+ Vẽ đường thẳng
+ Theo chiều tăng của VTPT n , dấu thay đổi từ < 0 ⇒ = 0 ⇒ > 0.
Ví dụ 2: Tìm min (max) của hàm số

14 | P a g e

L(ℂ; X ) = x + 2y

(1)


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ

3x + 4y − 12 ≤ 0

thỏa mãn hệ điều kiện: 0 ≤ x ≤ 3
0 ≤ y ≤ 2

Giải: + Tìm miền chấp nhận được:

{

(2)
(3)

}

Ω = M (x , y ) | (2) + (3) , đó là ngũ giác lối OABCD trong đó

O(0; 0); A(3; 0); B(3; 3 / 4); C (4 / 3;2); D(0;2) .

+ Đường thẳng tựa (dựa vào hàm mục tiêu): x + 2y = 0 có VTPT là n(1;2) .
+ Cho đường thẳng tựa tịnh tiến theo chiều tăng của VTPT ta nhận thấy:
- Tại O(0; 0) ⇒ L(C , X ) = 0 ⇒ min
- Tại B(3; 3 / 4) ⇒ L(C , X ) = 4, 5
- Tại C (4 / 3;2) ⇒ L(C , X ) =

16
3

+ Kết luận: L(ℂ; X ) đạt max tại C và max(x + 2y ) = L(O ) = 0

min(x + 2y ) = L(C ) =

16
.
3

Ví dụ 3: Tìm min (max) của L1 = 2x − y với điều kiện

3x + 4y − 12 ≤ 0

0 ≤ x ≤ 3
0 ≤ y ≤ 2

Hướng dẫn: Đường thẳng tựa: 2x − y = 0 có VTPT n(2;1) ….

Ví dụ 4: Tìm min (max) của L2 = 3x + 4y với điều kiện như trên…
Ví dụ 5 (Ví dụ 1 tr. 95)
Ví dụ 6 (Ví dụ 2. Tr.95) (Về bài toán xử lý phế thải).
Chú ý: Người ta đã chứng minh được rằng: Đối với bài toán Quy hoạch lồi:

1. Nếu có tối ưu duy nhất thì sẽ đạt được tại một đỉnh nào đó
2. Nếu có nhiều hơn một nghiệm tối ưu thì sẽ có ít nhất 2 nghiệm đạt tại 2 đỉnh kề nhau của miền chấp
nhận được
3. Số điểm cực biên là hữu hạn.
Từ đó chúng ta không cần tịnh tiến đường tựa mà chỉ cần tính giá trị hàm mục tiêu tại các điểm cực biên.

15 | P a g e


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ
2. Điểm cực biên tối ưu: là điểm mà tại đó giá trị của hàm mục tiêu đạt “tốt hơn” tại các điểm kề với điểm
này. Bài toán Quy hoạch lồi có thể:
+ Có nghiệm tối ưu duy nhất
+ Có vô số nghiệm tối ưu
+ Vô nghiệm
3. Phương pháp hình học cho bài toán 3 biến
3

a. Mặt phẳng trong ℝ .
2

2

2

Mặt phẳng Ax 1 + Bx 2 + Cx 3 + D = 0 (với A + B + C ≠ 0 ) sẽ chia không gian thành 3 miền

{
: {(x ; x ; x ) ∈ ℝ
: {(x ; x ; x ) ∈ ℝ


3

}
+ D = 0}
+ D < 0}

+ R+ : (x 1; x 2 ; x 3 ) ∈ ℝ | Ax 1 + Bx 2 + Cx 3 + D > 0
+ R0
+ R−

1

2

3

1

2

3

3

|Ax 1 + Bx 2 + Cx 3

3

| Ax 1 + Bx 2 + Cx 3

3

b. Các bước giải bài toán Quy hoạch lồi trong ℝ .
+ Từ đề bài, xác định miền chấp nhận được
+ Tìm các điểm cực biên
+ So sánh giá trị của hàm mục tiêu tại các điểm cực biên để xác định GTLN và GTNN.
Ví dụ 3(Tr.97) (hướng dẫn giải)
Ví dụ (bài 3 Tr. 99) (hướng dẫn giải)

Bài tập về nhà: Dạng III.2.3 Tr. 98
Đọc trước Mục III.3 từ trang 101 chuẩn bị cho Bài giảng:
Thuật toán đơn hình trong Quy hoạch tuyến tính

16 | P a g e


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ
Bài số 4: THUẬT TOÁN ĐƠN HÌNH
1. Biến cơ sở và biến tự do:

x + y = 36
, đây là hệ p/trình 2 ẩn, 2 p/trình độc lập: nên rất dễ giải.
2x + 4y = 100

Ví dụ 1: Xét hệ 

x + y = 36
, đây là hệ 2 p/trình không độc lập
x
y

2
+
2
=
72


Ví dụ 2: Xét hệ 

+ Khi đó, hệ ⇔ x = 36 − y , như vậy với mỗi y = y 0 ta có x 0 = 36 − y 0

{

2

}

+ Và tập nghiệm (x ; y ) ∈ ℝ | x + y = 36 .
+ Trong trường hợp này: x được gọi là biến cơ sở và y được gọi là biến tự do.
+ Còn nếu y = 36 − x thì x là biến tự do và y là biến cơ sở.

x + y + z = 36
⇔
2x + 4y + 4z = 100

Ví dụ 3: Xét hệ 

x + y = 36 − z

2x + 4y = 100 − 4z


Khi đó : x và y là biến cơ sở còn z là biến tự do
Chú ý: Số biến cơ sở = số phương tình độc lập.
2. Nghiệm cơ sở: là nghiệm của hệ ứng với các biến tự do bằng 0 .
Chẳng hạn trong
+ Ví dụ 2: Nghiệm cơ sở là (36; 0) và (0; 36)
+ Ví dụ 3: Nghiệm cơ sở là (22;14; 0) và (0; 36)
Về mặt hình học: Tìm nghiệm cơ sở chính là việc tìm những đỉnh nằm trên các trục tọa độ.
Ví dụ 4: Tìm max(L(x 1; x 2 ) = −x 3 + x 4 )

x + 2x − 3x = 2
3
4
 1
thỏa mãn  x 2 − x 3 + 5x 4 = 4
x ≥ 0, i = 1,..., 4
 i

(1)




(2)
(3)
4

Giải: Để ý rằng, VD này dung PP hình học sẽ khó vì phải xét trong ℝ .

x 1 = 2 − 2x 3 + 3x 4

x 2 = 4 + x 3 − 5x 4

+ Chọn biến cơ sở, biến tự do: biến đổi hệ thành 


 (2 ')


Khi đó : Biến cơ sở là: x 1; x 2 và biến tự do là x 3, x 4 .
+ Nghiệm cơ sở đầu tiên: M 1(2; 4; 0; 0) , đây chính là điểm cực biên đầu tiên (phương án cực biên đầu
tiên).
17 | P a g e


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ
Khi đó L1 = L(M 1 ) = −x 3 + x 4 = 0 : dễ thấy đây chưa phải là GTLN của L vì để ý trong công thức của
hàm mục tiêu L = −x 3 + x 4 cùng với điều kiện (3) ta có thể tăng x 4 (khi x 3 = 0 ) để nhận được giá trị mới
của L lớn hơn.
Một vấn đề đặt ra là sẽ cho x 4 tăng tới đâu?

x 1 = 2 + 3x 4

Để ý rằng, khi x 3 = 0 ta dựa vào (2’): 

x = 4 − 5x 4
 2

Do đó ta sẽ tăng x 4 đến

cùng với (3) suy ra 4 − 5x 4 ≥ 0 ⇔ x 4 ≤


4
.
5

4
và khi đó x 3 = 0 .
5

x 2 = 0
Bây giờ lại có: Biến tự do 
và biến cơ sở là
x
=
0
 3


22
x 1 =
5 và nhận được Nghiệm cơ sở (phương án cực

x = 4
 4 5

 22
4
; 0; 0;  , ứng với các phương trình sau:
5
 5


biên) thứ hai: M 2 


22 3
7
− x2 − x3
x 1 =
5 5
5

4
1
1
x = − x + x
 4 5 5 2 5 3
4 1
4
− x 2 − x 3 . Đến đây ta không thể tăng thêm được nữa, và ta nhận được kết quả:
5 5
5
 22
4
4
max L = L(M 2 ) = , khi đó M 2  ; 0; 0;  gọi là nghiệm tối ưu.
5
5
 5

lúc này L =


Quá trình trên có thể được biểu diễn thông qua Bảng đơn hình.
+ Trước hết ta viết lại bài toán dưới dạng bảng sau
Biến cơ sở

x1
x2
L

x1
1

x2
0

x3
2

x4
−3

Hệ số tự do

0

1

−1

5


4

0

0

1

−1

0

2

Ở đây:
+ Hàng cuối cùng ghi lại phương trình rút gọn của hàm mục tiêu: L + x 4 − x 5 = 0 , các hệ số của các biến
bên vế trái gọi là hệ số đánh giá.
+ Giá trị các biến cơ sở chon gay trong cột hệ số tự do, các biến còn lại là biến tự do đều bằng 0
+ Tất cả các hệ số tự do đều không âm
+ Giao của hang, cột chứa biến cơ sở luôn là số 1 , các số khác trong cột biến cơ sở đều bằng 0 .
18 | P a g e


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ
+ Dạng bài toán trên gọi là Dạng chuẩn tắc.
Từ đó ta nhận được phương án cực biên đầu tiên (2; 4; 0; 0) , lúc này L = 0 và chưa phải là GTNN vì ở hàng
cuối (hàng L ) ta nhận thấy hệ số đánh giá của x 4 âm (bằng −1 ) nên x 4 còn có thể tăng lên đến một giá trị
thích hợp. Ta sẽ đưa bảng đơn hình thứ nhất thành bảng đơn hình thứ 2 theo từng bước sau:
+ Chọn cột x 4 (có hệ số đánh giá âm) là cột chọn (tức là x 4 sẽ được chọn làm biến cơ sở mới thay

cho một biến cơ sở cũ), ta cần xét xem x 4 sẽ thay cho biến cơ sở cũ nào.
+ Lập các tỷ số giữa hệ số tự do và hệ số dương tương ứng ở cột chọn. Sau đó chọn hàng có tỷ số nhỏ
nhất làm hàng chọn, và biến cơ sở cũ x 2 tương ứng trở thành biến tự do (nhận giá trị 0 ).
+ Giao giữa cột chọn và hàng chọn được gọi là phần tử chọn : số 5
+ Vị trí của biến cơ sở cũ x 2 được thay bởi biến cơ sở mới x 4 , các giá trị trên hàng của biến cơ sở cũ
được tính lại bằng cách chia tất cả các giá trị cho phần tử chọn.
+ Trong cột chọn chỉ giữ nguyên phần tử chọn, còn các giá trị khác sẽ biến đổi sao cho trở thành số
0 dựa vào giá trị mới thuộc dòng của biến cơ sở mới x 4 .
+ Các giá trị mới của hàng L (hệ số đánh giá mới) bằng hệ số đánh giá cũ + giá trị của dòng biến cơ
sở mới.
Biến cơ sở

x1
1

x2
0

x3
2

x4
−3

Hệ số tự do

x2
L

0


1

−1

5

4

0

0

1

-1

0

x1

1

3/5

7/5

0

22 / 5


x4
L

0

1/ 5

−1 / 5

1

4/5

0

1/ 5

4/5

0

4/5

x1

Tỷ số

2


4/5

Ta biến đổi tiếp cho đến khi các hệ số đánh giá đều không âm thì dừng lại vì khi đó không thể tăng nữa và ta
nhận được nghiệm tối ưu.
Ví dụ 5: Cho bảng đơn hình
Biến cơ sở

x2
0

x3
0

x4
−3

x5
5

Hệ số tự do

x1

x1
1

x2

0


1

0

2

−1

8

x3
L

0

0

1

4

6

7

0

0

0


3

-1

0

Hãy tìm phương án tối ưu (max L ).
19 | P a g e

4

Tỷ số


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ
Giải:
Biến cơ sở

x2
0

x3
0

x4
−3

x5
5


Hệ số tự do

Tỷ số

x1

x1
1

4

4/5

x2

0

1

0

2

−1

8

x3
L


0

0

1

4

6

7

0

0

0

3

-1

0

x5

1/ 5

0


0

−3 / 5

4/5

x2

1/ 5

0

7/5

44 / 5

x3
L

−6 / 5

0

38 / 5

11 / 5

1/ 5


0



Phương án tối ưu M  0;



0

12 / 5

0

6/7

4/5

44 11 4 
4
; ; 0;  và giá trị tối ưu L = .
5
5 5
5

Chú ý:
1. Nếu các hệ số đánh giá trong các cột của biến tự do đều dương: thì phương án tối ưu là duy nhất.
2. Nếu trong các hệ số đánh giá ứng với biến tự do có ít nhất một hệ số bằng 0 : sẽ có vô số phương án tối
ưu.
3. Dạng chính tắc. Dạng chuẩn và Dạng chuẩn tắc của bài toán QHTT

a. Dạng tổng quát của bài toán QHTT
Tìm min (max) của u(M ) = L(C ; X ) = c1x 1 + c2x 2 + ... + cn x n
thỏa mãn m − điều kiện (m < n ; m , n ∈ ℕ * )

a11x 1 + a12x 2 + ... + a1n x n = (≤)b1

a21x 1 + a22x 2 + ... + a 2n x n = (≤)b2

…
am 1x 1 + am 2x 2 + ... + amn x n = (≤)bn

ở đây ai , j và bj đã biết (i = 1,.., n; j = 1,..., m ) , tìm x i = ?, (x i ≥ 0; i = 1,2,..., n ) .

A.X = (≤)B

Cách viết khác: Tìm min (max) của hàm L(ℂ; X ) thỏa mãn 

X ≥ 0

20 | P a g e

.


[BÀI GIẢNG MÔN PHÂN TÍCH VÀ TỐI ƯU HÓA HỆ THỐNG] TS. Nguyễn Hữu Thọ
b. Dạng chính tắc:
Tìm max L(ℂ; X )

Tìm min L(ℂ; X )


(1a )

A.X ≤ B
X ≥ 0

(2a )

thỏa mãn 

(3a )

A.X ≥ B
X ≥ 0

thỏa mãn 

.

(1b)
(2b)
(3b)

.

Các phần tử trong B có dấu tùy ý.
c. Dạng chuẩn:
Tìm max L(ℂ; X )

A.X = B
X ≥ 0


thỏa mãn 

(1)
(2)
(3)

.

Các phần tử trong B có dấu tùy ý.

d. Dạng chuẩn tắc: là dạng chuẩn với ma trận A có chứa r cột (ứng với r biến cơ sở ) chỉ có hệ số của
biến cơ sở là số 1 còn lại đều là số 0 .
Ví dụ 6: Ví dụ 1 (Tr. 105) có dạng chuẩn tắc.
Ví dụ 7: Ví dụ 2 (Tr.105) không là dạng chuẩn tắc, ta đưa về dạng chuẩn tắc bằng cách đưa thêm 3 biến
chênh lệch (hướng dẫn).
+ Điều kiện: • ≤ bk (bk ≥ 0) , ta thêm vào vế trái một biến chênh lệch ( ≥ 0 )
+ Điều kiện: • ≥ bk (bk ≥ 0) , ta trừ đi vào vế trái một biến chênh lệch ( ≥ 0 ) sau đó nhân hai vế với
Ví dụ 8: Bài toán xử lý phế thải (Tr. 94): chưa phải dạng chuẩn tắc, ta đưa về dạng chuẩn tắc và được giải ở
Tr. 105. (hướng dẫn).

Bài tập về nhà: Dạng III.3.4 Tr. 110; 111
Đọc trước Mục III.3.3 + III.4+ III.5 từ trang 107 chuẩn bị cho Bài giảng:
Thuật toán đơn hình cho các bài toán không chuẩn trong Quy hoạch tuyến tính. Bài toán đối ngẫu

21 | P a g e