Tài liệu toán kinh tế
- 265 trang
- file: .pdf
đang tải dữ liệu....
Tài liệu bị giới hạn, để xem hết nội dung vui lòng tải về máy tính.
Tải xuống - 265 trangNội dung text: Tài liệu toán kinh tế
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
TOÁN KINH TẾ
(Dùng cho sinh viên hệ đào tạo đại học từ xa)
Lưu hành nội bộ
HÀ NỘI - 2007
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
TOÁN KINH TẾ
Biên soạn : PGS.TS. NGUYỄN QUẢNG
TS. NGUYỄN THƯỢNG THÁI
LỜI NÓI ĐẦU
Nhằm đáp ứng nhu cầu giảng dạy và học tập môn học Toán kinh tế dành cho sinh viên hệ
đào tạo đại học từ xa, Học viện Công nghệ Bưu chính Viễn thông (Học viện) tổ chức biên soạn
tập Sách hướng dẫn học tập (Sách HDHT) môn học Toán kinh tế theo đúng chương trình đào tạo
Cử nhân ngành Quản trị kinh doanh của Học viện.
Tập sách được biên soạn trên cơ sở kế thừa, chọn lọc bổ sung tập giáo trình Toán chuyên
ngành đã được Nhà xuất bản Bưu điện ấn hành vào tháng 9 năm 2003 và các bài giảng Toán kinh
tế đã được sử dụng, giảng dạy cho chương trình đào tạo đại học chính quy ngành Quản trị Kinh
doanh tại Học viện.
Nội dung tập sách được cấu trúc gồm 7 chương:
Chương 1. Các kiến thức mở đầu về phương pháp tối ưu
Chương 2. Mô hình tối ưu tuyến tính
Chương 3. Một số mô hình tối ưu tuyến tính khác
Chương 4. Các bài toán tối ưu trên mạng.
Chương 5. Phương pháp mô hình hoá và mô hình toán kinh tế.
Chương 6. Lý thuyết Phục vụ đám đông
Chương 7. Lý thuyết quản lý dự trữ.
Để tạo điều kiện thuận lợi cho sinh viên có khả năng tự học, tự nghiên cứu, các tác giả
không đi sâu vào các vấn đề lý luận và kỹ thuật toán học phức tạp, mà chỉ tập trung trình bày, giới
thiệu những kiến thức cơ bản chủ yếu thiết thực và cập nhật, làm cơ sở cho việc học tập nghiên
cứu phân tích kinh tế nói chung và học tập các môn chuyên ngành Quản trị kinh doanh. Ở cuối
mỗi chương, sau phần khái quát và tóm tắt các vấn đề cơ bản, chủ yếu của lý thuyết, các tác giả
đưa ra các bài tập mẫu và phân tích cách giải để người học có thể tự giải được những bài toán liên
quan đến lý luận đã học. Phần bài tập cuối mỗi chương cũng sẽ giúp người học tự nghiên cứu, vận
dụng các lý luận đã học vào phân tích, lý giải các nội dung thực tiễn liên quan.
Mặc dù các tác giả đã đầu tư nghiên cứu chọn lọc biên soạn nghiêm túc để đáp ứng yêu cầu
giảng dạy và học tập của môn học, nhưng chắc tập sách sẽ không tránh khỏi những thiếu sót nhất
định. Các tác giả rất mong nhận được sự góp ý của bạn bè đồng nghiệp, bạn đọc và các bạn sinh
viên để lần xuất bản sau được hoàn thiện hơn.
CÁC TÁC GIẢ
Chương I: Một số kiến thức mở đầu
CHƯƠNG I: MỘT SỐ KIẾN THỨC MỞ ĐẦU
1.1. ĐỐI TƯỢNG NGHIÊN CỨU CỦA MÔN HỌC
1.1.1. Tổng quan về tối ưu hoá.
Trong hoạt động thực tiễn, nhất là trong quá trình quản lý, điều khiển hệ thống kinh tế - xã
hội, chúng ta luôn mong muốn đạt được kết quả tốt nhất theo các tiêu chuẩn nào đó. Tất cả những
mong muốn đó thường là lời giải của những bài toán tối ưu nào đó. Mỗi vấn đề khác nhau của
thực tế dẫn đến các bài toán tối ưu khác nhau. Để giải các bài toán đó, một loạt các lý thuyết toán
học ra đời để đặt cơ sở lý luận, đề đưa ra các giải pháp tìm lời giải, chứng minh tính hội tụ, tính
khả thi của các bài toán thực tế v.v. Từ đó hình thành một lớp các phương pháp toán học giúp ta
tìm ra lời giải tốt nhất cho các bài toán thực tế, gọi là các phương pháp tối ưu hóa. Lớp các
phương pháp tối ưu hóa bao gồm nhiều lý thuyết toán học khác nhau, tiêu biểu là: Qui hoạch toán
học, lý thuyết trò chơi, lý thuyết đồ thị v.v.
Trong qui hoạch toán học, tiêu biểu là Qui hoạch tuyến tính, Qui hoạch phi tuyến, Qui
hoạch động, Quy hoạch tham số, Qui hoạch nguyên v.v.
Trong lý thuyết trò chơi, tiêu biểu là Lý thuyết lựa chọn quyết định, Bài toán trò chơi chiến
lược, bài toán trò chơi vi phân v.v. Trong Lý thuyết đồ thị có các bài toán tối ưu trên mạng, bài
toán PERT, Các bài toán đường đi v.v.
Các lớp phương pháp toán học thuộc Lý thuyết tối ưu có thể biểu diễn bởi sơ đồ sau:
Lý thuyết tối ưu
Các phương pháp tối ưu Mô hình tối ưu .....
..... Mô Mô .....
Quy Lý Lý Mô hình hình
hoạch thuyết thuyết hình phục quản lý
toán đồ thị trò chơi toán vụ đám dự trữ
học kinh tế đông
1
1 2 3
Quy hoạch toán học
Quy Quy Quy Quy .....
hoạch hoạch phi hoạch hoạch
tuyến tuyến động tham số
tính
3
Chương I: Một số kiến thức mở đầu
3
Lý thuyết trò chơi
Bài toán Bài toán Bài toán .....
lựa chọn trò chơi trò chơi
quyết chiến vi phân
định lược
1.1.2. Bài toán tối ưu tổng quát.
Bài toán quy hoạch toán học tổng quát được phát biểu như sau:
Cực đại hóa (cực tiểu hóa) hàm f (x) → max (min) (1.1)
Với các điều kiện: gi (x) ≤ (=, ≥ ) bi (i = 1, m ) (1.2)
x ∈ X. ⊂ IRn . (1.3)
Hàm f (x) cho ở (1 -1) gọi là hàm mục tiêu.
Các hàm gi (x) (i = 1, m ) gọi là hàm ràng buộc.
Tập hợp D = {x ∈ X | gi (x) ≤ (=, ≥) bi, i = 1,m} (1.4)
Gọi là miền ràng buộc chấp nhận được.
- Mỗi một bất đẳng thức, đẳng thức trong (1.2) gọi là một ràng buộc của bài toán (1.1) -
(1.2) - (1.3)
- Điểm x = (x1, x2, ..., xn) ∈ D gọi là một phương án của bài toán (1.1) - (1.2) - (1.3) hay là
một giải pháp chấp nhận được.
- Một phương án x* ∈ D làm cực đại (cực tiểu) hàm mục tiêu gọi là phương án tối ưu (hay
lời giải hoặc phương án tốt nhất).
Theo định nghĩa trên thì x* ∈ D là phương án tối ưu khi và chỉ khi
f (x*) ≥ f (x), ∀x ∈ D, (đối với bài toán max) hay
f (x*) ≤ f(x), ∀x ∈ D, (đối với bài toán min).
Giá trị f(x*) gọi là giá trị tối ưu (tốt nhất) của hàm mục tiêu, hay là giá trị tối ưu của bài
toán (1.1) - (1.2) - (1.3).
1.1.3. Phân loại các bài toán tối ưu.
a - Nếu hàm mục tiêu f(x) và các ràng buộc gi (x) là hàm tuyến tính (bậc 1) thì bài toán (1.1)
- (1.2) - (1.3) gọi là một Qui hoạch tuyến tính . (trường hợp riêng là bài toán vận tải).
b - Nếu biểu thức hàm mục tiêu f(x) và các ràng buộc gi (x) (i = 1, m ) là hàm phụ thuộc
tham số, thì bài toán (1.1) ÷ (1.3) gọi là qui hoạch tham số.
4
Chương I: Một số kiến thức mở đầu
c - Nếu bài toán (1.1) ÷ (1.3) được xét trong quá trình nhiều giai đoạn hoặc trong quá trình
thay đổi theo thời gian thì gọi là Qui hoạch động.
d - Nếu bài toán (1.1) ÷ (1.3) mà hàm mục tiêu f(x) hoặc có ít nhất một trong các hàm gi
(x), (i = 1, m ) là phi tuyến thì gọi là Qui hoạch phi tuyến, trường hợp riêng là Qui hoạch lồi hoặc
Qui hoạch lõm.
Qui hoạch lồi (lõm) là Qui hoạch toán học mà hàm mục tiêu f(x) là lồi (lõm) trên tập hợp
các ràng buộc D lồi (lõm).
e - Nếu bài toán (1.1) ÷ (1.3) mà miền ràng buộc D là tập rời rạc thì gọi là Qui hoạch rời
rạc.
g - Nếu bài toán(1.1) ÷ (1.3) có các biến xi ∈ IR1 là thành phần i trong véc tơ x ∈ X ⊂ IRn,
chỉ nhận các giá trị nguyên, thì gọi là Qui hoạch nguyên.
h - Nếu bài toán (1.1) ÷ (1.3) mà các biến xi ∈ IR1 chỉ nhận các giá trị O hoặc 1, gọi là Qui
hoạch Bul (xi là thành phần i của véc tơ x).
i - Nếu bài toán (1.1) ÷ (1.3) mà trên miền D ta xét đồng thời nhiều mục tiêu khác nhau,
gọi là Qui hoạch đa mục tiêu v.v.
1.1.4. Nội dung nghiên cứu của môn học.
a. Quy hoạch tuyến tính.
b. Bài toán vận tải.
c. Bài toán tối ưu trên mạng.
d. Mô hình kinh tế và mô hình toán kinh tế.
e. Mô hình phục vụ đám đông.
g. Mô hình quản lý dự trữ.
1.2. CƠ SỞ GIẢI TÍCH LỒI.
1.2.1. Không gian tuyến tính n chiều (Rn).
a. Véc tơ n chiều.
Một hệ thống được sắp , gồm n số thực, dạng x = (x1 x2, ..., xn), gọi là một véc tơ n chiều.
Thí dụ: x = (4, 0, 5, 10, 15) là một véc tơ 5 chiều.
Các số xi, i = 1, n , gọi là thành phần thứ i của véc tơ x.
Hai véc tơ x =(x1, x2, ..., xn) và (y1, y2, ..., yn) gọi là bằng nhau, nếu xi = yi, (i = 1, n ). Khi đó
ta viết x ≡ y.
Vậy x ≡ y ⇔ xi =yi, (i = 1, n ).
Cho hai véc tơ x = (x1, x2, ..., xn)
y = (y1, y2, ..., yn) và α ∈ R1.
Ta định nghĩa phép cộng hai véc tơ x và y là véc tơ x+y, được xác định như sau:
x+y= (x1+ y1, x2 + y2, ..., xn + yn) (1.5)
1
Phép nhân véc tơ x với một số α ∈ R là véc tơ αx, được xác định như sau:
5
Chương I: Một số kiến thức mở đầu
αx = (αx1, αx2, ..., αxn) (1.6)
- Véc tơ θ = (0, 0, ....., 0) gồm các thành phần toàn là số 0, gọi là véc tơ không.
* Các tính chất của phép cộng véctơ và nhân véctơ với một số.
- Nếu x và y là hai véctơ n chiều thì x+y cũng là véc tơ n chiều.
- Với mọi véc tơ n chiều x và y ta đều có: x+y =y+x.
- Với mọi véc tơ n chiều x, y và z ta đều có: x + (y+z) = (x+y) +z.
- Luôn tồn tại véctơ θ n chiều sao cho θ +x = x+ θ =x.
- Mỗi véctơ n chiều x luôn tồn tại véc tơ n chiều -x sao cho: x+ (-x)=(-x) +x = θ
- ∀ k ∈ R và với mọi véc tơ n chiều x thì kx cũng là véc tơ n chiều.
- ∀ k ∈ R và với mọi véc tơ n chiều x và y ta có: k (x+y) = kx+ky.
- ∀ l, k ∈ R và với mọi véc tơ n chiều x ta luôn có: (k +l ) x = kx +lx.
- ∀ l, k ∈ R và với mọi véc tơ n chiều x ta luôn có: k(lx) = (kl) x.
- Mọi véc tơ n chiều ta luôn có: 1.x = x.
b. Không gian tuyến tính n chiều Rn.
Tập hợp tất cả các véc tơ n chiều, trong đó xác lập phép toán cộng Véc tơ và nhân véc tơ
với một số thực như (1.5) và (1.6) và thoả mãn 10 tính chất nêu trên, gọi là một không gian tuyến
tính n chiều. Ký hiệu IRn.
1.2.2. Một số tính chất đối với véc tơ trong Rn.
a. Định nghĩa.
Các véc tơ xi ∈ Rn, i = 1, m , gọi là độc lập tuyến tính nếu
m
∑ αi xi = θ ⇔ αi = 0, ∀i = 1, m .
i =1
m
- Nếu tồn tại ít nhất một số αj ≠ 0 , 1 ≤ j ≤ m, sao cho ∑ αi xi = θ , thì ta nói rằng các
i =1
véc tơ x ∈ Rn, i = 1, m , là phụ thuộc tuyến tính.
m
- Nếu tồn tại véc tơ xi ∈ Rn, sao cho: x = ∑ αixi, với ít nhất một αi ≠ 0, 1≤ i≤ m, thì x gọi
i =1
i
là tổ hợp tuyến tính của các véc tơ x , (i = 1, m ).
m m
- Nếu x = ∑ αi xi với αi ≥ 0, i = 1, m , và ∑ αi = 1 thì x gọi là tổ hợp lồi của các véc tơ
i =1 i =1
xi, i = 1, m .
- Trong không gian véc tơ Rn, hệ n Véc tơ độc lập tuyến tính lập thành cơ sở của IRn.
Giả sử C1, C2, ..., Cn là một cơ sở của Rn, khi đó ∀x ∈ Rn đều có thể biểu diễn tuyến tính
một cách duy nhất qua các Véc tơ cơ sở. Ci, (i = 1, n ).
6
Chương I: Một số kiến thức mở đầu
b. Cho hai véc tơ bất kỳ x, y∈ Rn, x = (x1, x2, ... xn) và y = (y1, y2, ...., yn) , ta gọi tích vô
hướng của hai véc tơ x và y là một số thực, ký hiệu là, được xác định như sau:
m
= ∑ xi yi .
i =1
- Độ dài của Véc tơ x ∈ Rn là số thực, ký hiệu x , được xác định như sau
n
x = < x, x > = ∑ x i2
i =1
- Chú ý: Tích vô hướng hai véc tơ có các tính chất sau:
b1, < x, y > = < y, x >. (Tính giao hoán) ∀ x, y ∈ Rn .
b2, < x1+x2, y > = < x1, y > + < x2, y >, ∀ x1, x2, y ∈ Rn .
(Tính phân phối đối với phép cộng).
b3, < λx, y > = λ < x, y > , ∀λ ∈ R1, ∀ x, y ∈ Rn .
b4> < x, x > ≥ 0 ∀x ∈ Rn, dấu bằng xảy ra khi x = θ .
Với mỗi ∀x, y ∈ Rn, ta định nghĩa khoảng cách giữa hai véc tơ x, y, ký hiệu ρ (x, y) là số
thực, được xác định như sau:
n
ρ ( x, y ) = x− y = < x − y, x − y > = Σ ( xi − y i ) 2 .
i =1
Chú ý: Khoảng cách giữa hai véc tơ x, y ∈ Rn, chính là độ dài của véc tơ hiệu x+ (-1)y: = x
- y. (Hiệu của hai Véc tơ).
1.2.3. Không gian Ơclít.
Một không gian tuyến tính n chiều, trong đó xác định phép toán tích vô hướng, do đó xác
định một khoảng cách giữa hai véc tơ, gọi là không gian Ơclít, ký hiệu IRn.
1.2.4. Tập Compact.
a. Các định nghĩa.
Dãy {xk} ⊂ |Rn, gọi là hội tụ đến điểm xo∈ IRn khi k→∞, nếu lim ρ(xk, xo) = 0. Khi đó ta
k →∞
nói {x } có giới hạn là x khi k → ∞ , và viết: lim x = x .
k o k o
k →∞
- Một tập hợp S = {x∈IR ρ(x, a) ≤ r, a∈ IRn, r ∈ IR1}, gọi là một hình cầu tâm a, bán kính
n:
r trong IRn.
- Hình cầu S nói trên, tạo thành một lân cận của điểm a, gọi là r -lân cận của a.
- Cho tập hợp A ⊂ IRn, điểm x∈ A được gọi là điểm trong của A nếu ∃ ε - lân cận của x
nằm trọn trong A.
- Điểm x ∈ A ⊂ IRn, được gọi là điểm biên của A, nếu mọi lân cận của x đều có chứa các
điểm thuộc A và các điểm không thuộc A.
- Cho tập hợp A ⊂ IRn, ta nói tập hợp A là giới nội nếu ∃ hình cầu chứa trọn nó, nghĩa là ∃
số thực r đủ lớn và điểm a∈ IRn sao cho ∀x∈ A ta đều có ρ(x, a) < r.
7
Chương I: Một số kiến thức mở đầu
* Nhận xét. Từ định nghĩa của dãy hội tụ và tập giới nội, ta suy ra, một dãy {xk} ⊂ IRn, hội
tụ bao giờ cũng giới nội.
- Một tập hợp G ⊂ IRn được gọi là mở, nếu∀x∈ G, tồn tại một hình cầu tâm x chứa trọn
trong G.
- Một tập hợp F ⊂ IRn được gọi là đóng, nếu như mọi dãy hội tụ {xk}⊂ F ⊂ IRn, đều hội tụ
đến một điểm xo ∈ F.
* Nhận xét. Một tập hợp chứa mọi điểm biên của nó là một tập hợp đóng.
b. Tập Compact.
- Tập hợp C ⊂ IRn được gọi là tập hợp Compắct nếu từ mọi dãy vô hạn {xk}⊂ C, đều có
thể trích ra một dãy con {xkn} hội tụ đến một phần tử thuộc C.
- Một tập C là Compact khi và chỉ khi C đóng và giới nội.
- Tập Compact M của tập đóng C cũng đóng trong C.
- Tập con M đóng ⊂ C Compact cũng là tập Compact.
- Hàm f(x) liên tục trên tập Compact C sẽ đạt giá trị lớn nhất, nhỏ nhất trên C.
1.2.5. Đường thẳng, đoạn thẳng, siêu phẳng.
a. Định nghĩa đường thẳng và đoạn thẳng trong IRn.
- Cho hai điểm a, b ∈ |Rn. Ta gọi đường thẳng qua a, b là tập hợp các điểm x ∈ IRn có
dạng: x = λa + (1 - λ)b, λ ∈ IR1
- Nếu 0 ≤ λ ≤ 1 thì ta có đoạn thẳng nối hai điểm a, b, ký hiệu [a, b].
Chú ý - Trong không gian hai chiều IR2, phương trình bậc nhất ax + by = c, xác định một
đường thẳng, một bất phương trình ax+by ≤ c hoặc ax+by ≥ c, xác định nửa mặt phẳng trong IRn.
- Trong không gian ba chiều IR3, một phương trình bậc nhất ax+by+cz=d xác định một mặt
phẳng, một bất phương trình bậc nhất ax+by+cz ≤ d hoặc ax + by + cz ≥ d xác định một nửa
không gian. Ta mở rộng kết quả trên cho không gian IRn.
b. Siêu phẳng trong IRn .
- Siêu phẳng trong không gian IRn là tập hợp tất cả các điểm x = ∈ IRn, thoả
mãn phương trình bậc nhất:
a1 x1 + a2 x2 + ... + an xn = α.
n n
- Một bất phương trình bậc nhất dạng Σ ai xi ≤ α hoặc Σ ai xi ≥ α xác định một nửa không
i =1 i =1
n
gian đóng trong IR .
1.2.6. Tập hợp lồi .
a. Định nghĩa.
Tập hợp x ⊂ IRn được gọi là tập hợp lồi nếu cùng với việc chứa hai điểm x, y, nó chứa cả
đoạn thẳng nối hai điểm ấy.
Điều này có nghĩa là X = {z ∈ |Rn: z = λa + <1- λ > b, a, b∈ IRn, λ ∈ [0, 1]}
8
Chương I: Một số kiến thức mở đầu
Ví dụ. Cả không gian IRn, nửa không gian |Rn, các đa giác trong |Rn, các khoảng,
đoạn [a, b] trong IR1... là các tập hợp lồi.
x
x y x y
A
y
B C
Tập A: lồi Tập B và C: không lồi.
b. Định lý 11.
Giao của hai tập hợp lồi là tập hợp lồi.
Chứng minh. Lấy hai điểm bất kỳ x, y ∈ A ∩ B ⇒ x, y ∈ A và x, y ∈ B
Vì A lồi nên [x, y] ⊂ A.
B lồi nên [x, y] ⊂ B. => [x, y] ⊂ A ∩ B. Vậy A ∩ B lồi.
Hệ quả 1. Giao của một số bất kỳ tập lồi là tập lồi.
Hệ quả 2. Tập hợp các nghiệm của hệ bất phương trình bậc nhất dạng:
a11x1 + a12x2 +........ + amxn ≤ b1
a21x1 + a22x2 +........ + a2nxn ≤ b2
--------------------------------------
am1x1 + am2x2 +........+ amnxn ≤ bm,
là một tập hợp lồi, gọi là khúc lồi đa diện, trong |Rn.
Chú ý . Một khúc lồi đa diện giới nội gọi là đa diện lồi, ký hiệu D. Giao của các tập hợp lồi
chứa D ta gọi là bao lồi của D. Ký hiệu [D].
c. Điểm cực biên.
Đỉnh của đa diện lồi hoặc khúc lồi gọi là điểm cực biên.
Rõ ràng điểm cực biên x không thể là điểm trong của đoạn thẳng nối hai điểm nào đó
thuộc D, nghĩa là không thể tồn tại hai điểm x1, x2∈ D sao cho x= λ x1+(1- λ )x2, λ ∈ (0, 1).
1.2.7. Hàm lồi .
a. Định nghĩa.
Một hàm f(x), xác định trên tập hợp lồi C ⊂ |Rn, được gọi là ∀ hàm lồi nếu ∀ cặp điểm x1,
x2 ∈ C và ∀ số λ ∈ [0, 1] ta luôn luôn có:
9
Chương I: Một số kiến thức mở đầu
f( λx 1 + (1 − λ ) x 2 ) ≤ λ f(x1) + (1 - λ) f(x2) (1.7)
Nếu trong (1.7) xảy ra dấu ≤ thì hàm f(x) gọi là hàm lồi chặt.
Nếu trong (1.7) xảy ra dấu ≤ thì hàm f(x) gọi là hàm lõm, xảy ra dấu > thì hàm f(x) gọi là
hàm lõm chặt.
f(x)
f(x2)
λf(x1) + (1 -λ) f(x2)
f(λx1 + (1 - λx2))
f(x1)
0 x' x x2 x
Chú ý. Nếu hàm f (x) lồi trên tập C ⊂ IRn thì hàm - f (x) lõm trên tập C, ngược lại nếu f (x)
lõm trên tập lồi C ⊂ IRn thì hàm - f (x) lồi trên tập hợp C.
- Ta nói hàm f(x) xác định trên tập lồi C đạt cực tiểu tuyệt đối tại x*∈ C nếu f(x*) ≤ f(x),
∀x∈C, đạt cực đại tuyệt đối tại x* ∈c nếu f(x*) ≥ f(x), ∀x ∈ C.
- Ta nói hàm f (x) xác định trên tập lồi C, đạt cực tiểu địa phương tại x*∈C nếu ∃ lân cận Bε
của x* sao cho f(x) ≤ f(x), ∀x ∈ B ε .
- Ta nói hàm f (x) xác định trên tập lồi C, đạt cực đại địa phương tại x*∈C, nếu ∃ lân cận
B ε của x* sao cho f(x) ≥ f(x), ∀x ∈ B ε .
b. Định lý 1.2.
Mọi điểm cực trị địa phương của hàm lồi trên tập hợp lồi đều là điểm cực trị tuyệt đối.
Chứng minh. Giả sử x* là cực tiểu địa phương nhưng không cực tiểu tuyệt đối trên tập C
lồi, như vậy ∃ x1∈ C sao cho f (x*) ) f(x1). Xét tổ hợp lồi của hai điểm x* và x1:
X = α x* + (1 - α) x1, 0 ≤ α ≤ 1.
Nếu α = 0 thì x ≡ x1. Khi đó ∃ αo ≤ (0, 1) sao cho x≤ B ε , với ε ∈ [0, αo) lấy δ1∈ (0, αo)
1
ta có: x(δ1)= (1-δ1) x* + δ1 x ∈ B ε .
Do f lồi nên có f ((1-δ1) x*+δ1x1) ≤ (1-δ1) f (x*) +δ1 f(x1).
((1-δ1) f (x*) +δ1 f(x*) = f (x*), điều này mâu thuẫn với hàm f (x*) đạt cực tiểu địa
phương tại x*. Từ đó suy ra điều phải chứng minh.
Hệ quả 1.
Mọi điểm cực đại địa phương của hàm lõm trên tập hợp lồi đều là cực đại tuyệt đối.
- Ta gọi đạo hàm theo hướng z của hàm f tại x là đại lượng:
f (x + λz) − f (x)
δf (x, z) = lim , nếu giới hạn này tồn tại.
λ→ 0 λ
10
Chương I: Một số kiến thức mở đầu
c - Bổ đề 1.1.
Nếu hàm f (x) là hàm lồi khả vi trên C lồi. Khi đó ∀x∈ C và với mọi z sao cho x+z ∈ C
thì δf (x, z) tồn tại và nghiệm đúng bất đẳng thức và đẳng thức sau:
i) δf (x, z) ≤ f (x +z) - f (x).
n δf ( x )
ii) δf (x, z) = Σ zi = < Δ f(x), z >.
i =1 δx
1
⎛ δf ( x ) δf ( x ) δf ( x ) ⎞
Trong đó: Véc tơ Δ f (x) = ⎜⎜ , ,..., ⎟ gọi là građient của hàm f(x) tại x,
⎝ δx1 δx 2 δx n ⎟⎠
z = (z1, z2... zn)
1.2.8. Một số tiêu chuẩn nhận biết hàm lồi.
Cho x, z ∈IRn, đặt hàm số ϕ (λ) = f(x+λz), ∀ λ ∈[0, 1], (1.8)
Định lý 1.3.
Hàm f(x) là lồi trên IRn khi và chỉ khi hàm số ϕ (λ) là lồi với λ ∈ [0, 1] và x, z ∈ |Rn .
Định lý 1.4.
a. Hàm f(x) khả vi trên IRn là lồi khi và chỉ khi ∀ x, z ∈ IRn cho trước, hàm ϕ'(λ) = < ∇ f(x
+ λz), z > không giảm theo λ.
b. Hàm f(x) khả vi hai lần trên IRn là lồi khi và chỉ khi ∀ x, y ∈ IRn cho trước, dạng toàn
phương < P(x) z, z > là xác định không âm.
Chú ý. Một dạng toàn phương là xác định không âm khi và chỉ khi
≥ 0, ∀z ∈ IRn .
Hệ quả 1.
1
Một hàm bậc hai dạng f(x) = < c, x > + < Px, x >, trong đó P = (p ij)nxn là ma trân đối
2
xứng cấp nxn, là một hàm lồi khi và chỉ khi ma trân P là xác định không âm.
Chú ý. Để ma trận P là xác định không âm thì điều kiện cần và đủ là tất cả các định thức
con chính của ma trận này không âm, nghĩa là:
a 11 a 12 ........ a 1 n
a 11 a 12
a 21 a 22 ....... a 2 n
Δ1 = a11 ≥ 0 ; Δ2 = ≥ 0, ..., Δn = ≥0
a 21 a 22 .......... .......... ...
a n 1 a n 2 ........ a nn
BÀI TẬP CHƯƠNG I.
Bài 1. Một doanh nghiệp có 300 đơn vị nguyên liệu loại A, 500 đơn vị nguyên liệu loại B
và 200 đơn vị nguyên liệu loại C để sản xuất 4 loại sản phẩm I, II, III, IV. Định mức nguyên liệu
cần thiết và tiền lãi của sản xuất cho bởi bảng 1. Hãy lập kế hoạch sản xuất của xí nghiệp trên sao
cho thu được lãi suất lớn nhất.
Bảng 1
11
Chương I: Một số kiến thức mở đầu
Hàng hoá
I II III IV
Nguyên liệu
A: 300 12 5 15 6
B: 500 14 8 7 9
C: 280 17 13 9 12
Lãi (đơn vị tiền) 5 8 4 6
Bài 2. Cần sản xuất ít nhất 75 sản phẩm loại A, 58 sản phẩm loại B và 64 sản phẩm loại C.
Người ta có thể áp dụng 3 cách sản xuất I, II, III, IV. Trong một đơn vị thời gian, năng suất và chi
phí của từng cách sản xuất cho bởi bảng 2.
Bảng 2
Cách sản xuất I II III
Loại sản phẩm
A ≥ 75 3 6 7
B ≥ 58 5 9 3
C ≥ 64 2 8 4
Chi phí (đơn vị tiền) 2 4 3
Hãy lập kế hoạch sản xuất sao cho chi phí nhỏ nhất mà vẫn đạt được các yêu cầu đặt ra.
Bài 3. Một Công ty có ba xí nghiệp cùng loại: A, B, C có khả năng sản xuất được 3 loại
sản phẩm: I, II, III. Biết rằng nếu đầu tư một đơn vị tiền vào xí nghiệp A trong một năm sẽ sản
xuất được 1200 sản phẩm loại I, 800 sản phẩm loại II và 1050 sản phẩm loại III. Đầu tư vào xí
nghiệp B một đơn vị tiền, được 1000 sản phẩm loại I, 740 sản phẩm loại II, 900 sản phẩm loại III.
Đầu tư vào xí nghiệp C một đơn vị tiền thì sản xuất được 1100 sản phẩm loại I, 600 sản phẩm loại
II, 1000 sản phẩm loại III. Định mức tiêu hao nguyên liệu và lao động của mỗi xí nghiệp trong sản
xuất được cho ở bảng 3. Nguyên liệu, lao động hàng năm Công ty có thể cung cấp cho sản xuất ba
loại sản phẩm này là 390.000 KG và 200.000 giờ công. Theo kế hoạch phải sản xuất ít nhất là
23.000 đơn vị sản phẩm loại I, 18.000 đơn vị sản phẩm loại II, và 21.000 đơn vị sản phẩm loại III.
Hãy tìm một phương án đầu tư sao cho thu được các sản phẩm theo kế hoạch mà vốn đầu tư ít
nhất.
Bảng 3
Định mức hao phí ng. liệu (Kg/sản phẩm) và lao động (g/sản phẩm)
Doanh I II III
nghiệp
Ng. liệu Lao động Ng. liệu Lao động Ng. liệu Lao động
A 4 2 10 4 8 4, 5
B 4, 2 3 9 4, 5 7, 8 5
12
Chương I: Một số kiến thức mở đầu
C 4, 5 2, 5 10, 5 5 8, 4 4
Bài 4. Một xí nghiệp quân đội có 4 loại máy: A, B, C, D, sản xuất ra 6 loại sản phẩm I, II,
III, IV, V, VI. Số giờ của mỗi loại máy để sản xuất mỗi loại sản phẩm và giá tiền mỗi loại sản
phẩm ghi ở bảng 4. Năng lực sản xuất của các l\mãy đều có hạn, nếu dùng quá sẽ bị hỏng. Giả sử
trong 1 tuần, mỗi máy loại A, B, C, D tương ứng làm việc không quá 850, 700, 100 và 900 giờ.
Hãy lập một phương án sản xuất để thu được sản phẩm mỗi loại lớn nhất mà vẫn bảo đảm an toàn
cho máy móc và thiết bị.
Bảng 4
Sản phẩm
Loại Loại Loại Loại Loại
Số giờ sản Loại I
II III IV V VI
xuất 1 sp trên máy.
A 0, 01 0, 01 0, 01 0, 03 0, 03 0, 03
B 0, 02 0, 05
C 0, 02 0, 05
D 0, 03 0, 08
Giá 1 sản phẩm (đ/v tiền) 0, 40 0, 28 0, 32 0, 72 0, 64 0, 60
Bài 5. Một máy bay vận tải quân sự có trọng tải M. Cần chở n loại thiết bị bằng máy bay.
Trọng lượng loại bưu kiện i, (i = 1, n ) là αi, có giá trị βi . Hãy tìm phương án chở mỗi loại thiết bị
bao nhiêu đơn vị lên máy bay để trọng lượng tổng cộng không vượt quá tải trọng của máy bay mà
đạt được tổng giá trị lớn nhất ? (Bài toán Qui hoạch nguyên).
13
Chương II: Quy hoạch tuyến tính
CHƯƠNG II: QUY HOẠCH TUYẾN TÍNH
2.1. MỘT SỐ BÀI TOÁN THỰC TẾ DẪN TỚI MÔ HÌNH QUY HOẠCH
TUYẾN TÍNH
2.1.1. Bài toán lập kế hoạch sản xuất.
Giả sử một Công ty sản xuất n loại sản phẩm và phải sử dụng m loại nguyên liệu khác nhau.
Gọi xj là sản lượng sản phẩm loại j, (j = 1, n ) mà Công ty sẽ sản xuất, cj là tiền lãi (hay giá) một
đơn vị sản phẩm loại j, aij là chi phí nguyên liệu loại i, (i = 1, m ), để sản xuất ra một đơn vị sản
phẩm loại j, bi là lượng nguyên liệu loại i tối đa có thể có.
Trong các điều kiện đã cho, hãy xác định sản lượng xj, j = 1, n sao cho tổng tiền lãi (hay
tổng giá trị sản lượng hàng hoá) là lớn nhất với số nguyên liệu hiện có.
Bài toán thực tiễn trên, có thể mô hình toán học như sau:
Tìm x = (x1, x2, ..., xn) ∈ IRn , làm cực đại hàm mục tiêu:
n
f(x) = ∑ cj xj → max
j =1
với các điều kiện:
n
∑ aij xj ≤ bi, i = 1, m ,
j =1
xj ≥ 0, j = 1, n
Bài toán trên là một bài toán Qui hoạch tuyến tính.
2.1.2. Bài toán vận tải.
Có m kho hàng cùng chứa một loại hàng hoá, Ai , i = 1, m (Ai điểm phát thứ i). Lượng hàng
ở kho Ai là ai, (i = 1, m ). Có n địa điểm tiêu thụ hàng Bj, nhu cầu tiêu thụ ở điểm Bj là bj, j = 1, n
(Bi điểm thu thứ i). Biết rằng cước phí vận chuyển một đơn vị hàng hoá từ điểm phát Ai đến điểm
thu Bj là cij. Hãy lập kế hoạch vận chuyển hàng hoá từ các địa điểm phát đến các địa điểm thu
hàng sao cho tổng chi phí vận chuyển là nhỏ nhất.
Nếu ta ký hiệu xij là lượng hàng vận chuyển từ điểm phát Ai, (i = 1, m ) đến điểm thu Bj, với
(j = 1, n ), thì ta có thể mô hình toán học bài toán thực tế như sau:
Tìm véc tơ x= (x1, x2,..., xn+m) ∈ IRnxm ,sao cho:
m n
F(x) = ∑ ∑ cij xij → min
i =1 j =1
với các điều kiện:
14
Chương II: Quy hoạch tuyến tính
n
∑ xij = ai, i = 1, m
j =1
m
∑ xij = bi, j = 1, n
i =1
xij ≥ 0, i = 1, m , j = 1, n
Ngoài ra bài toán phải thoả mãn điều kiện:
n m
∑ bj = ∑ ai (cân bằng thu và phát).
j =1 i =1
Đây là một dạng của bài toán Quy hoạch tuyến tính.
2.1.3. Bài toán người bán hàng (Bài toán cái túi).
Một cửa hàng cần phải vận chuyển một lượng hàng trên một chuyến nặng không được quá
b kg. Có n loại đồ vật mà cửa hàng cần phải vận chuyển đi bán, mỗi đồ vật loại j, (j = 1, n ), có
khối lượng aj kg. Và có giá trị là cj . Hãy xác định xem trong một chuyến hàng, cửa hàng cần đưa
lên phương tiện vận chuyển các đồ vật nào để tổng giá trị các đồ vật thu được là lớn nhất.
Nếu ta ký hiệu xj là số đồ vật loại j sẽ đưa lên phương tiện vận chuyển, ta có mô hình toán
học bài toán như sau:
Tìm x = (x1, x2,...,xn) ∈ |Rn sao cho:
n
f(x) = ∑ cj xj → max
j =1
Với điều kiện:
n
∑ aj xj ≤ b
j =1
xj ≥ 0, j = 1, n
xj - nguyên, j = 1, n
Đây là bài toán Qui hoạch nguyên.
2.1.4. Bài toán lập kế hoạch đầu tư vốn cho sản xuất.
Cần phải đầu tư vốn vào m xí nghiệp để sản xuất ra n loại sản phẩm. Do trang bị kỹ thuật -
công nghệ và tổ chức sản xuất khác nhau nên hiệu quả của vốn đầu tư vào các xí nghiệp cũng
khác nhau. Qua phân tích, người ta biết rằng khi đầu tư một đơn vị tiền vào xí nghiệp thứ i, i =
1, m , trong một năm sẽ sản xuất ra được bij đơn vị sản phẩm loại j, j = 1, n . Tổng số nguyên liệu
và lao động hàng năm có thể cung cấp là A và C (tính theo giờ/công). Hãy xác định một kế hoạch
đầu tư sao cho đảm bảo sản xuất được ít nhất Bj đơn vị sản phẩm loại j mà tổng số vốn đầu tư nhỏ
nhất, biết rằng các định mức hao phí về nguyên liệu và lao động khi sản xuất ra một đơn vị sản
phẩm loại j ở xí nghiệp i, i = 1, m , tương ứng là aij và cij, i = 1, m , j = 1, n .
15
Chương II: Quy hoạch tuyến tính
Gọi vốn đầu tư vào xí nghiệp i là xi đơn vị tiền. Khi đó số lượng sản phẩm loại j sản xuất ở
xí nghiệp i là bij xi và số nguyên liệu sử dụng ở xí nghiệp này để sản xuất ra các sản phẩm j là aij
n
bij xi .Vậy toàn bộ nguyên liệu sử dụng ở xí nghiệp i là ∑ aij bijxi và tổng số nguyên liệu sử
j =1
m n
dụng cho kế hoạch sản xuất chung là: ∑
i =1
∑ aij bij xi.
j =1
m n
Tương tự, ta suy ra tổng số lao động sử dụng trong kế hoạch sản xuất là: ∑ ∑ cij bij xi
i =1 j =1
m
Tổng số vốn đầu tư, theo bài toán đặt ra, là ∑ xi và tổng số sản phẩm loại j sản xuất được
i =1
m
là ∑ bij xi .
i =1
Theo mục tiêu của bài toán thực tế đặt ra thì bài toán có thể mô hình toán học như sau:
Tìm véc tơ x = (x1, x2 ,..., xn) ∈ IRm sao cho:
m
f(x) = ∑ xi → min
i =1
với điều kiện:
m n
∑ ∑ aij bij xi ≤ A
i =1 j =1
m n
∑ ∑ cij bij xi ≤ C
i =1 j =1
m
∑ bij xi ≥ Bj, j = 1, n
i =1
xi ≥ 0, i = 1, m
Đây là một dạng của bài toán Qui hoạch tuyến tính.
2.2. MÔ HÌNH BÀI TOÁN QUY HOẠCH TUYẾN TÍNH.
2.2.1. Bài toán quy hoạch tuyến tính tổng quát
Tìm x = (x1, x2...xi,...xn) ∈IRn.
n
Sao cho: f(x) = Σ Cj xj → max (min) (2.1)
j = 1
Thỏa mãn điều kiện:
n
Σ aij xj (≤, = ≥ ) bi ( i= 1, m ) (2.2)
j = 1
xj≥ 0 (j = 1, n ) (2.3)
16
Chương II: Quy hoạch tuyến tính
Để xây dựng cơ sở lý luận giải bài toán, chỉ cấn xét một trong hai dạng bài toán, chẳng hạn
bài toán tìm giá trị lớn nhất (f → max ) của hàm mục tiêu, còn bài toán tìm giá trị bé nhất (f →
min ) của hàm mục tiêu có thể chuyển đổi như sau:
* Giữ nguyên hệ ràng buộc ( 2.2 ) và ( 2.3 )
n
* Đưa hàm mục tiêu: f(x) = ∑ C x → min
j =1
j j
n
về f (x) = - f (x) = Σ ( - Cj ) xj → max, ta có mô hình bài toán:
j = 1
Tìm x = ( x1 , x2 , ..., xj ,... xn ) ∈IRn
n
Sao cho: f (x) = Σ (- Cj ) xj → max (2.4)
j = 1
n
Thoả mãn điều kiện: Σ aij xj (≤, =, ≥ ) bi ( i = 1, m ) (2.5)
j = 1
xi ≥ 0 ( j = 1, n ) (2.6)
Bổ đề: Nếu bài toán (2.4) ÷ (2.6) có xopt = x*, thì bài toán (2.1) ÷ (2.3) với
f (x) → min cũng có xopt = x* và fmin = - f max
Thật vậy, theo giả thiết (2.4) ÷ (2.6) có xopt = x* với hàm mục tiêu
n
f (x) = Σ (-cj ). xj→ max , thì:
j = 1
f (x) ≤ f (x*) ( ∀x∈D - tập các phương án )
n n n n
⇔ Σ (-cj ). xj ≤ Σ ( - cj ). x *j ⇔ Σ cj. x *j ≤ Σ cj xj
j = 1 j = 1 j = 1 j = 1
⇔ f (x) ≥ f (x*) (∀x ∈ D) ⇔ x* = xopt của (2.1)⎯(2.3) với f(x) → min.
n n
fmin = Σ cj x *j = - Σ (-cj) x *j = - f max ( đpcm )
j = 1 j = 1
Như vậy mọi bài toán (2.1) - (2.3) với f(x) → min có thể chuyển f (x) → max.
2.2.2. Dạng chuẩn tắc
a- Dạng đầy đủ
Tìm x= (x1 ,.... , xj ,.... xn ) ∈ IRn
Sao cho: f(x) = c1x1 +...+ci xi +...+ cn xn → max (2.7)
17
Chương II: Quy hoạch tuyến tính
Thoả mãn a11 x1 +...+ a1i xi +...+a1n xn ≤ b1
a21 x1 +...+ a21xi +...+a2n xn ≤ b2
------------------------------------
ai1 x1 +...+ aii xi +...+ ain xn ≤ b1 (2.8)
--------------------------------
am1 x1+...+ami xi +...+ amn xn ≤ bm
xi ≤ 0 ( i = 1, n ) (2.9)
b. Dạng rút gọn.
n
f(x) = Σ cixi → max
j = 1
n
Σ aii xi ≤ bi ( i= 1, m )
j = 1
xi ≥ 0 ( δ = 1, n )
Tính chất của hàm mục tiêu (2.7) và dạng bất phương trình của hệ ràng buộc (2.8) xuất phát
từ ý nghĩa thực tiễn của bài toán đặt ra. Chẳng hạn như bài toán lập kế hoạch sản xuất để hiệu quả
kinh tế tổng cộng lớn nhất, khi phải hạn chế chi tiết nguyên liệu sử dụng.
Ngược lại, trong bài toán xác định vốn đầu tư cho sản xuất phải khai thác tối đa trang bị kỹ
thuật - công nghệ để sao cho đạt được yêu cầu về giá trị sản phẩm làm ra mà vốn đầu tư ít nhất.
2.2.3 Dạng chính tắc
a- Dạng đầy đủ
n
f (x) = Σ cixi → max (2.10)
i = 1
n
Σ aiixi = bi (i = 1, m ) (2.11)
i = 1
xi ≥ 0 (i = 1, n ) (2.12)
b. Dạng ma trận:
Gọi ma trận hàng, gồm các phần tử là hệ số các ẩn trong hàm mục tiêu là C:
C = [ c1 c2...cn]
Ma trận cột:
⎡ b1 ⎤ ⎡ x1 ⎤
⎢b ⎥ ⎢ ⎥
B = ⎢ 2 ⎥ , x = ⎢ x2 ⎥
⎢⎣ b m ⎥⎦ ⎢⎣ x n ⎥⎦
18
TOÁN KINH TẾ
(Dùng cho sinh viên hệ đào tạo đại học từ xa)
Lưu hành nội bộ
HÀ NỘI - 2007
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
TOÁN KINH TẾ
Biên soạn : PGS.TS. NGUYỄN QUẢNG
TS. NGUYỄN THƯỢNG THÁI
LỜI NÓI ĐẦU
Nhằm đáp ứng nhu cầu giảng dạy và học tập môn học Toán kinh tế dành cho sinh viên hệ
đào tạo đại học từ xa, Học viện Công nghệ Bưu chính Viễn thông (Học viện) tổ chức biên soạn
tập Sách hướng dẫn học tập (Sách HDHT) môn học Toán kinh tế theo đúng chương trình đào tạo
Cử nhân ngành Quản trị kinh doanh của Học viện.
Tập sách được biên soạn trên cơ sở kế thừa, chọn lọc bổ sung tập giáo trình Toán chuyên
ngành đã được Nhà xuất bản Bưu điện ấn hành vào tháng 9 năm 2003 và các bài giảng Toán kinh
tế đã được sử dụng, giảng dạy cho chương trình đào tạo đại học chính quy ngành Quản trị Kinh
doanh tại Học viện.
Nội dung tập sách được cấu trúc gồm 7 chương:
Chương 1. Các kiến thức mở đầu về phương pháp tối ưu
Chương 2. Mô hình tối ưu tuyến tính
Chương 3. Một số mô hình tối ưu tuyến tính khác
Chương 4. Các bài toán tối ưu trên mạng.
Chương 5. Phương pháp mô hình hoá và mô hình toán kinh tế.
Chương 6. Lý thuyết Phục vụ đám đông
Chương 7. Lý thuyết quản lý dự trữ.
Để tạo điều kiện thuận lợi cho sinh viên có khả năng tự học, tự nghiên cứu, các tác giả
không đi sâu vào các vấn đề lý luận và kỹ thuật toán học phức tạp, mà chỉ tập trung trình bày, giới
thiệu những kiến thức cơ bản chủ yếu thiết thực và cập nhật, làm cơ sở cho việc học tập nghiên
cứu phân tích kinh tế nói chung và học tập các môn chuyên ngành Quản trị kinh doanh. Ở cuối
mỗi chương, sau phần khái quát và tóm tắt các vấn đề cơ bản, chủ yếu của lý thuyết, các tác giả
đưa ra các bài tập mẫu và phân tích cách giải để người học có thể tự giải được những bài toán liên
quan đến lý luận đã học. Phần bài tập cuối mỗi chương cũng sẽ giúp người học tự nghiên cứu, vận
dụng các lý luận đã học vào phân tích, lý giải các nội dung thực tiễn liên quan.
Mặc dù các tác giả đã đầu tư nghiên cứu chọn lọc biên soạn nghiêm túc để đáp ứng yêu cầu
giảng dạy và học tập của môn học, nhưng chắc tập sách sẽ không tránh khỏi những thiếu sót nhất
định. Các tác giả rất mong nhận được sự góp ý của bạn bè đồng nghiệp, bạn đọc và các bạn sinh
viên để lần xuất bản sau được hoàn thiện hơn.
CÁC TÁC GIẢ
Chương I: Một số kiến thức mở đầu
CHƯƠNG I: MỘT SỐ KIẾN THỨC MỞ ĐẦU
1.1. ĐỐI TƯỢNG NGHIÊN CỨU CỦA MÔN HỌC
1.1.1. Tổng quan về tối ưu hoá.
Trong hoạt động thực tiễn, nhất là trong quá trình quản lý, điều khiển hệ thống kinh tế - xã
hội, chúng ta luôn mong muốn đạt được kết quả tốt nhất theo các tiêu chuẩn nào đó. Tất cả những
mong muốn đó thường là lời giải của những bài toán tối ưu nào đó. Mỗi vấn đề khác nhau của
thực tế dẫn đến các bài toán tối ưu khác nhau. Để giải các bài toán đó, một loạt các lý thuyết toán
học ra đời để đặt cơ sở lý luận, đề đưa ra các giải pháp tìm lời giải, chứng minh tính hội tụ, tính
khả thi của các bài toán thực tế v.v. Từ đó hình thành một lớp các phương pháp toán học giúp ta
tìm ra lời giải tốt nhất cho các bài toán thực tế, gọi là các phương pháp tối ưu hóa. Lớp các
phương pháp tối ưu hóa bao gồm nhiều lý thuyết toán học khác nhau, tiêu biểu là: Qui hoạch toán
học, lý thuyết trò chơi, lý thuyết đồ thị v.v.
Trong qui hoạch toán học, tiêu biểu là Qui hoạch tuyến tính, Qui hoạch phi tuyến, Qui
hoạch động, Quy hoạch tham số, Qui hoạch nguyên v.v.
Trong lý thuyết trò chơi, tiêu biểu là Lý thuyết lựa chọn quyết định, Bài toán trò chơi chiến
lược, bài toán trò chơi vi phân v.v. Trong Lý thuyết đồ thị có các bài toán tối ưu trên mạng, bài
toán PERT, Các bài toán đường đi v.v.
Các lớp phương pháp toán học thuộc Lý thuyết tối ưu có thể biểu diễn bởi sơ đồ sau:
Lý thuyết tối ưu
Các phương pháp tối ưu Mô hình tối ưu .....
..... Mô Mô .....
Quy Lý Lý Mô hình hình
hoạch thuyết thuyết hình phục quản lý
toán đồ thị trò chơi toán vụ đám dự trữ
học kinh tế đông
1
1 2 3
Quy hoạch toán học
Quy Quy Quy Quy .....
hoạch hoạch phi hoạch hoạch
tuyến tuyến động tham số
tính
3
Chương I: Một số kiến thức mở đầu
3
Lý thuyết trò chơi
Bài toán Bài toán Bài toán .....
lựa chọn trò chơi trò chơi
quyết chiến vi phân
định lược
1.1.2. Bài toán tối ưu tổng quát.
Bài toán quy hoạch toán học tổng quát được phát biểu như sau:
Cực đại hóa (cực tiểu hóa) hàm f (x) → max (min) (1.1)
Với các điều kiện: gi (x) ≤ (=, ≥ ) bi (i = 1, m ) (1.2)
x ∈ X. ⊂ IRn . (1.3)
Hàm f (x) cho ở (1 -1) gọi là hàm mục tiêu.
Các hàm gi (x) (i = 1, m ) gọi là hàm ràng buộc.
Tập hợp D = {x ∈ X | gi (x) ≤ (=, ≥) bi, i = 1,m} (1.4)
Gọi là miền ràng buộc chấp nhận được.
- Mỗi một bất đẳng thức, đẳng thức trong (1.2) gọi là một ràng buộc của bài toán (1.1) -
(1.2) - (1.3)
- Điểm x = (x1, x2, ..., xn) ∈ D gọi là một phương án của bài toán (1.1) - (1.2) - (1.3) hay là
một giải pháp chấp nhận được.
- Một phương án x* ∈ D làm cực đại (cực tiểu) hàm mục tiêu gọi là phương án tối ưu (hay
lời giải hoặc phương án tốt nhất).
Theo định nghĩa trên thì x* ∈ D là phương án tối ưu khi và chỉ khi
f (x*) ≥ f (x), ∀x ∈ D, (đối với bài toán max) hay
f (x*) ≤ f(x), ∀x ∈ D, (đối với bài toán min).
Giá trị f(x*) gọi là giá trị tối ưu (tốt nhất) của hàm mục tiêu, hay là giá trị tối ưu của bài
toán (1.1) - (1.2) - (1.3).
1.1.3. Phân loại các bài toán tối ưu.
a - Nếu hàm mục tiêu f(x) và các ràng buộc gi (x) là hàm tuyến tính (bậc 1) thì bài toán (1.1)
- (1.2) - (1.3) gọi là một Qui hoạch tuyến tính . (trường hợp riêng là bài toán vận tải).
b - Nếu biểu thức hàm mục tiêu f(x) và các ràng buộc gi (x) (i = 1, m ) là hàm phụ thuộc
tham số, thì bài toán (1.1) ÷ (1.3) gọi là qui hoạch tham số.
4
Chương I: Một số kiến thức mở đầu
c - Nếu bài toán (1.1) ÷ (1.3) được xét trong quá trình nhiều giai đoạn hoặc trong quá trình
thay đổi theo thời gian thì gọi là Qui hoạch động.
d - Nếu bài toán (1.1) ÷ (1.3) mà hàm mục tiêu f(x) hoặc có ít nhất một trong các hàm gi
(x), (i = 1, m ) là phi tuyến thì gọi là Qui hoạch phi tuyến, trường hợp riêng là Qui hoạch lồi hoặc
Qui hoạch lõm.
Qui hoạch lồi (lõm) là Qui hoạch toán học mà hàm mục tiêu f(x) là lồi (lõm) trên tập hợp
các ràng buộc D lồi (lõm).
e - Nếu bài toán (1.1) ÷ (1.3) mà miền ràng buộc D là tập rời rạc thì gọi là Qui hoạch rời
rạc.
g - Nếu bài toán(1.1) ÷ (1.3) có các biến xi ∈ IR1 là thành phần i trong véc tơ x ∈ X ⊂ IRn,
chỉ nhận các giá trị nguyên, thì gọi là Qui hoạch nguyên.
h - Nếu bài toán (1.1) ÷ (1.3) mà các biến xi ∈ IR1 chỉ nhận các giá trị O hoặc 1, gọi là Qui
hoạch Bul (xi là thành phần i của véc tơ x).
i - Nếu bài toán (1.1) ÷ (1.3) mà trên miền D ta xét đồng thời nhiều mục tiêu khác nhau,
gọi là Qui hoạch đa mục tiêu v.v.
1.1.4. Nội dung nghiên cứu của môn học.
a. Quy hoạch tuyến tính.
b. Bài toán vận tải.
c. Bài toán tối ưu trên mạng.
d. Mô hình kinh tế và mô hình toán kinh tế.
e. Mô hình phục vụ đám đông.
g. Mô hình quản lý dự trữ.
1.2. CƠ SỞ GIẢI TÍCH LỒI.
1.2.1. Không gian tuyến tính n chiều (Rn).
a. Véc tơ n chiều.
Một hệ thống được sắp , gồm n số thực, dạng x = (x1 x2, ..., xn), gọi là một véc tơ n chiều.
Thí dụ: x = (4, 0, 5, 10, 15) là một véc tơ 5 chiều.
Các số xi, i = 1, n , gọi là thành phần thứ i của véc tơ x.
Hai véc tơ x =(x1, x2, ..., xn) và (y1, y2, ..., yn) gọi là bằng nhau, nếu xi = yi, (i = 1, n ). Khi đó
ta viết x ≡ y.
Vậy x ≡ y ⇔ xi =yi, (i = 1, n ).
Cho hai véc tơ x = (x1, x2, ..., xn)
y = (y1, y2, ..., yn) và α ∈ R1.
Ta định nghĩa phép cộng hai véc tơ x và y là véc tơ x+y, được xác định như sau:
x+y= (x1+ y1, x2 + y2, ..., xn + yn) (1.5)
1
Phép nhân véc tơ x với một số α ∈ R là véc tơ αx, được xác định như sau:
5
Chương I: Một số kiến thức mở đầu
αx = (αx1, αx2, ..., αxn) (1.6)
- Véc tơ θ = (0, 0, ....., 0) gồm các thành phần toàn là số 0, gọi là véc tơ không.
* Các tính chất của phép cộng véctơ và nhân véctơ với một số.
- Nếu x và y là hai véctơ n chiều thì x+y cũng là véc tơ n chiều.
- Với mọi véc tơ n chiều x và y ta đều có: x+y =y+x.
- Với mọi véc tơ n chiều x, y và z ta đều có: x + (y+z) = (x+y) +z.
- Luôn tồn tại véctơ θ n chiều sao cho θ +x = x+ θ =x.
- Mỗi véctơ n chiều x luôn tồn tại véc tơ n chiều -x sao cho: x+ (-x)=(-x) +x = θ
- ∀ k ∈ R và với mọi véc tơ n chiều x thì kx cũng là véc tơ n chiều.
- ∀ k ∈ R và với mọi véc tơ n chiều x và y ta có: k (x+y) = kx+ky.
- ∀ l, k ∈ R và với mọi véc tơ n chiều x ta luôn có: (k +l ) x = kx +lx.
- ∀ l, k ∈ R và với mọi véc tơ n chiều x ta luôn có: k(lx) = (kl) x.
- Mọi véc tơ n chiều ta luôn có: 1.x = x.
b. Không gian tuyến tính n chiều Rn.
Tập hợp tất cả các véc tơ n chiều, trong đó xác lập phép toán cộng Véc tơ và nhân véc tơ
với một số thực như (1.5) và (1.6) và thoả mãn 10 tính chất nêu trên, gọi là một không gian tuyến
tính n chiều. Ký hiệu IRn.
1.2.2. Một số tính chất đối với véc tơ trong Rn.
a. Định nghĩa.
Các véc tơ xi ∈ Rn, i = 1, m , gọi là độc lập tuyến tính nếu
m
∑ αi xi = θ ⇔ αi = 0, ∀i = 1, m .
i =1
m
- Nếu tồn tại ít nhất một số αj ≠ 0 , 1 ≤ j ≤ m, sao cho ∑ αi xi = θ , thì ta nói rằng các
i =1
véc tơ x ∈ Rn, i = 1, m , là phụ thuộc tuyến tính.
m
- Nếu tồn tại véc tơ xi ∈ Rn, sao cho: x = ∑ αixi, với ít nhất một αi ≠ 0, 1≤ i≤ m, thì x gọi
i =1
i
là tổ hợp tuyến tính của các véc tơ x , (i = 1, m ).
m m
- Nếu x = ∑ αi xi với αi ≥ 0, i = 1, m , và ∑ αi = 1 thì x gọi là tổ hợp lồi của các véc tơ
i =1 i =1
xi, i = 1, m .
- Trong không gian véc tơ Rn, hệ n Véc tơ độc lập tuyến tính lập thành cơ sở của IRn.
Giả sử C1, C2, ..., Cn là một cơ sở của Rn, khi đó ∀x ∈ Rn đều có thể biểu diễn tuyến tính
một cách duy nhất qua các Véc tơ cơ sở. Ci, (i = 1, n ).
6
Chương I: Một số kiến thức mở đầu
b. Cho hai véc tơ bất kỳ x, y∈ Rn, x = (x1, x2, ... xn) và y = (y1, y2, ...., yn) , ta gọi tích vô
hướng của hai véc tơ x và y là một số thực, ký hiệu là
m
i =1
- Độ dài của Véc tơ x ∈ Rn là số thực, ký hiệu x , được xác định như sau
n
x = < x, x > = ∑ x i2
i =1
- Chú ý: Tích vô hướng hai véc tơ có các tính chất sau:
b1, < x, y > = < y, x >. (Tính giao hoán) ∀ x, y ∈ Rn .
b2, < x1+x2, y > = < x1, y > + < x2, y >, ∀ x1, x2, y ∈ Rn .
(Tính phân phối đối với phép cộng).
b3, < λx, y > = λ < x, y > , ∀λ ∈ R1, ∀ x, y ∈ Rn .
b4> < x, x > ≥ 0 ∀x ∈ Rn, dấu bằng xảy ra khi x = θ .
Với mỗi ∀x, y ∈ Rn, ta định nghĩa khoảng cách giữa hai véc tơ x, y, ký hiệu ρ (x, y) là số
thực, được xác định như sau:
n
ρ ( x, y ) = x− y = < x − y, x − y > = Σ ( xi − y i ) 2 .
i =1
Chú ý: Khoảng cách giữa hai véc tơ x, y ∈ Rn, chính là độ dài của véc tơ hiệu x+ (-1)y: = x
- y. (Hiệu của hai Véc tơ).
1.2.3. Không gian Ơclít.
Một không gian tuyến tính n chiều, trong đó xác định phép toán tích vô hướng, do đó xác
định một khoảng cách giữa hai véc tơ, gọi là không gian Ơclít, ký hiệu IRn.
1.2.4. Tập Compact.
a. Các định nghĩa.
Dãy {xk} ⊂ |Rn, gọi là hội tụ đến điểm xo∈ IRn khi k→∞, nếu lim ρ(xk, xo) = 0. Khi đó ta
k →∞
nói {x } có giới hạn là x khi k → ∞ , và viết: lim x = x .
k o k o
k →∞
- Một tập hợp S = {x∈IR ρ(x, a) ≤ r, a∈ IRn, r ∈ IR1}, gọi là một hình cầu tâm a, bán kính
n:
r trong IRn.
- Hình cầu S nói trên, tạo thành một lân cận của điểm a, gọi là r -lân cận của a.
- Cho tập hợp A ⊂ IRn, điểm x∈ A được gọi là điểm trong của A nếu ∃ ε - lân cận của x
nằm trọn trong A.
- Điểm x ∈ A ⊂ IRn, được gọi là điểm biên của A, nếu mọi lân cận của x đều có chứa các
điểm thuộc A và các điểm không thuộc A.
- Cho tập hợp A ⊂ IRn, ta nói tập hợp A là giới nội nếu ∃ hình cầu chứa trọn nó, nghĩa là ∃
số thực r đủ lớn và điểm a∈ IRn sao cho ∀x∈ A ta đều có ρ(x, a) < r.
7
Chương I: Một số kiến thức mở đầu
* Nhận xét. Từ định nghĩa của dãy hội tụ và tập giới nội, ta suy ra, một dãy {xk} ⊂ IRn, hội
tụ bao giờ cũng giới nội.
- Một tập hợp G ⊂ IRn được gọi là mở, nếu∀x∈ G, tồn tại một hình cầu tâm x chứa trọn
trong G.
- Một tập hợp F ⊂ IRn được gọi là đóng, nếu như mọi dãy hội tụ {xk}⊂ F ⊂ IRn, đều hội tụ
đến một điểm xo ∈ F.
* Nhận xét. Một tập hợp chứa mọi điểm biên của nó là một tập hợp đóng.
b. Tập Compact.
- Tập hợp C ⊂ IRn được gọi là tập hợp Compắct nếu từ mọi dãy vô hạn {xk}⊂ C, đều có
thể trích ra một dãy con {xkn} hội tụ đến một phần tử thuộc C.
- Một tập C là Compact khi và chỉ khi C đóng và giới nội.
- Tập Compact M của tập đóng C cũng đóng trong C.
- Tập con M đóng ⊂ C Compact cũng là tập Compact.
- Hàm f(x) liên tục trên tập Compact C sẽ đạt giá trị lớn nhất, nhỏ nhất trên C.
1.2.5. Đường thẳng, đoạn thẳng, siêu phẳng.
a. Định nghĩa đường thẳng và đoạn thẳng trong IRn.
- Cho hai điểm a, b ∈ |Rn. Ta gọi đường thẳng qua a, b là tập hợp các điểm x ∈ IRn có
dạng: x = λa + (1 - λ)b, λ ∈ IR1
- Nếu 0 ≤ λ ≤ 1 thì ta có đoạn thẳng nối hai điểm a, b, ký hiệu [a, b].
Chú ý - Trong không gian hai chiều IR2, phương trình bậc nhất ax + by = c, xác định một
đường thẳng, một bất phương trình ax+by ≤ c hoặc ax+by ≥ c, xác định nửa mặt phẳng trong IRn.
- Trong không gian ba chiều IR3, một phương trình bậc nhất ax+by+cz=d xác định một mặt
phẳng, một bất phương trình bậc nhất ax+by+cz ≤ d hoặc ax + by + cz ≥ d xác định một nửa
không gian. Ta mở rộng kết quả trên cho không gian IRn.
b. Siêu phẳng trong IRn .
- Siêu phẳng trong không gian IRn là tập hợp tất cả các điểm x =
mãn phương trình bậc nhất:
a1 x1 + a2 x2 + ... + an xn = α.
n n
- Một bất phương trình bậc nhất dạng Σ ai xi ≤ α hoặc Σ ai xi ≥ α xác định một nửa không
i =1 i =1
n
gian đóng trong IR .
1.2.6. Tập hợp lồi .
a. Định nghĩa.
Tập hợp x ⊂ IRn được gọi là tập hợp lồi nếu cùng với việc chứa hai điểm x, y, nó chứa cả
đoạn thẳng nối hai điểm ấy.
Điều này có nghĩa là X = {z ∈ |Rn: z = λa + <1- λ > b, a, b∈ IRn, λ ∈ [0, 1]}
8
Chương I: Một số kiến thức mở đầu
Ví dụ. Cả không gian IRn, nửa không gian |Rn, các đa giác trong |Rn, các khoảng
đoạn [a, b] trong IR1... là các tập hợp lồi.
x
x y x y
A
y
B C
Tập A: lồi Tập B và C: không lồi.
b. Định lý 11.
Giao của hai tập hợp lồi là tập hợp lồi.
Chứng minh. Lấy hai điểm bất kỳ x, y ∈ A ∩ B ⇒ x, y ∈ A và x, y ∈ B
Vì A lồi nên [x, y] ⊂ A.
B lồi nên [x, y] ⊂ B. => [x, y] ⊂ A ∩ B. Vậy A ∩ B lồi.
Hệ quả 1. Giao của một số bất kỳ tập lồi là tập lồi.
Hệ quả 2. Tập hợp các nghiệm của hệ bất phương trình bậc nhất dạng:
a11x1 + a12x2 +........ + amxn ≤ b1
a21x1 + a22x2 +........ + a2nxn ≤ b2
--------------------------------------
am1x1 + am2x2 +........+ amnxn ≤ bm,
là một tập hợp lồi, gọi là khúc lồi đa diện, trong |Rn.
Chú ý . Một khúc lồi đa diện giới nội gọi là đa diện lồi, ký hiệu D. Giao của các tập hợp lồi
chứa D ta gọi là bao lồi của D. Ký hiệu [D].
c. Điểm cực biên.
Đỉnh của đa diện lồi hoặc khúc lồi gọi là điểm cực biên.
Rõ ràng điểm cực biên x không thể là điểm trong của đoạn thẳng nối hai điểm nào đó
thuộc D, nghĩa là không thể tồn tại hai điểm x1, x2∈ D sao cho x= λ x1+(1- λ )x2, λ ∈ (0, 1).
1.2.7. Hàm lồi .
a. Định nghĩa.
Một hàm f(x), xác định trên tập hợp lồi C ⊂ |Rn, được gọi là ∀ hàm lồi nếu ∀ cặp điểm x1,
x2 ∈ C và ∀ số λ ∈ [0, 1] ta luôn luôn có:
9
Chương I: Một số kiến thức mở đầu
f( λx 1 + (1 − λ ) x 2 ) ≤ λ f(x1) + (1 - λ) f(x2) (1.7)
Nếu trong (1.7) xảy ra dấu ≤ thì hàm f(x) gọi là hàm lồi chặt.
Nếu trong (1.7) xảy ra dấu ≤ thì hàm f(x) gọi là hàm lõm, xảy ra dấu > thì hàm f(x) gọi là
hàm lõm chặt.
f(x)
f(x2)
λf(x1) + (1 -λ) f(x2)
f(λx1 + (1 - λx2))
f(x1)
0 x' x x2 x
Chú ý. Nếu hàm f (x) lồi trên tập C ⊂ IRn thì hàm - f (x) lõm trên tập C, ngược lại nếu f (x)
lõm trên tập lồi C ⊂ IRn thì hàm - f (x) lồi trên tập hợp C.
- Ta nói hàm f(x) xác định trên tập lồi C đạt cực tiểu tuyệt đối tại x*∈ C nếu f(x*) ≤ f(x),
∀x∈C, đạt cực đại tuyệt đối tại x* ∈c nếu f(x*) ≥ f(x), ∀x ∈ C.
- Ta nói hàm f (x) xác định trên tập lồi C, đạt cực tiểu địa phương tại x*∈C nếu ∃ lân cận Bε
của x* sao cho f(x) ≤ f(x), ∀x ∈ B ε .
- Ta nói hàm f (x) xác định trên tập lồi C, đạt cực đại địa phương tại x*∈C, nếu ∃ lân cận
B ε của x* sao cho f(x) ≥ f(x), ∀x ∈ B ε .
b. Định lý 1.2.
Mọi điểm cực trị địa phương của hàm lồi trên tập hợp lồi đều là điểm cực trị tuyệt đối.
Chứng minh. Giả sử x* là cực tiểu địa phương nhưng không cực tiểu tuyệt đối trên tập C
lồi, như vậy ∃ x1∈ C sao cho f (x*) ) f(x1). Xét tổ hợp lồi của hai điểm x* và x1:
X = α x* + (1 - α) x1, 0 ≤ α ≤ 1.
Nếu α = 0 thì x ≡ x1. Khi đó ∃ αo ≤ (0, 1) sao cho x≤ B ε , với ε ∈ [0, αo) lấy δ1∈ (0, αo)
1
ta có: x(δ1)= (1-δ1) x* + δ1 x ∈ B ε .
Do f lồi nên có f ((1-δ1) x*+δ1x1) ≤ (1-δ1) f (x*) +δ1 f(x1).
((1-δ1) f (x*) +δ1 f(x*) = f (x*), điều này mâu thuẫn với hàm f (x*) đạt cực tiểu địa
phương tại x*. Từ đó suy ra điều phải chứng minh.
Hệ quả 1.
Mọi điểm cực đại địa phương của hàm lõm trên tập hợp lồi đều là cực đại tuyệt đối.
- Ta gọi đạo hàm theo hướng z của hàm f tại x là đại lượng:
f (x + λz) − f (x)
δf (x, z) = lim , nếu giới hạn này tồn tại.
λ→ 0 λ
10
Chương I: Một số kiến thức mở đầu
c - Bổ đề 1.1.
Nếu hàm f (x) là hàm lồi khả vi trên C lồi. Khi đó ∀x∈ C và với mọi z sao cho x+z ∈ C
thì δf (x, z) tồn tại và nghiệm đúng bất đẳng thức và đẳng thức sau:
i) δf (x, z) ≤ f (x +z) - f (x).
n δf ( x )
ii) δf (x, z) = Σ zi = < Δ f(x), z >.
i =1 δx
1
⎛ δf ( x ) δf ( x ) δf ( x ) ⎞
Trong đó: Véc tơ Δ f (x) = ⎜⎜ , ,..., ⎟ gọi là građient của hàm f(x) tại x,
⎝ δx1 δx 2 δx n ⎟⎠
z = (z1, z2... zn)
1.2.8. Một số tiêu chuẩn nhận biết hàm lồi.
Cho x, z ∈IRn, đặt hàm số ϕ (λ) = f(x+λz), ∀ λ ∈[0, 1], (1.8)
Định lý 1.3.
Hàm f(x) là lồi trên IRn khi và chỉ khi hàm số ϕ (λ) là lồi với λ ∈ [0, 1] và x, z ∈ |Rn .
Định lý 1.4.
a. Hàm f(x) khả vi trên IRn là lồi khi và chỉ khi ∀ x, z ∈ IRn cho trước, hàm ϕ'(λ) = < ∇ f(x
+ λz), z > không giảm theo λ.
b. Hàm f(x) khả vi hai lần trên IRn là lồi khi và chỉ khi ∀ x, y ∈ IRn cho trước, dạng toàn
phương < P(x) z, z > là xác định không âm.
Chú ý. Một dạng toàn phương
≥ 0, ∀z ∈ IRn .
Hệ quả 1.
1
Một hàm bậc hai dạng f(x) = < c, x > + < Px, x >, trong đó P = (p ij)nxn là ma trân đối
2
xứng cấp nxn, là một hàm lồi khi và chỉ khi ma trân P là xác định không âm.
Chú ý. Để ma trận P là xác định không âm thì điều kiện cần và đủ là tất cả các định thức
con chính của ma trận này không âm, nghĩa là:
a 11 a 12 ........ a 1 n
a 11 a 12
a 21 a 22 ....... a 2 n
Δ1 = a11 ≥ 0 ; Δ2 = ≥ 0, ..., Δn = ≥0
a 21 a 22 .......... .......... ...
a n 1 a n 2 ........ a nn
BÀI TẬP CHƯƠNG I.
Bài 1. Một doanh nghiệp có 300 đơn vị nguyên liệu loại A, 500 đơn vị nguyên liệu loại B
và 200 đơn vị nguyên liệu loại C để sản xuất 4 loại sản phẩm I, II, III, IV. Định mức nguyên liệu
cần thiết và tiền lãi của sản xuất cho bởi bảng 1. Hãy lập kế hoạch sản xuất của xí nghiệp trên sao
cho thu được lãi suất lớn nhất.
Bảng 1
11
Chương I: Một số kiến thức mở đầu
Hàng hoá
I II III IV
Nguyên liệu
A: 300 12 5 15 6
B: 500 14 8 7 9
C: 280 17 13 9 12
Lãi (đơn vị tiền) 5 8 4 6
Bài 2. Cần sản xuất ít nhất 75 sản phẩm loại A, 58 sản phẩm loại B và 64 sản phẩm loại C.
Người ta có thể áp dụng 3 cách sản xuất I, II, III, IV. Trong một đơn vị thời gian, năng suất và chi
phí của từng cách sản xuất cho bởi bảng 2.
Bảng 2
Cách sản xuất I II III
Loại sản phẩm
A ≥ 75 3 6 7
B ≥ 58 5 9 3
C ≥ 64 2 8 4
Chi phí (đơn vị tiền) 2 4 3
Hãy lập kế hoạch sản xuất sao cho chi phí nhỏ nhất mà vẫn đạt được các yêu cầu đặt ra.
Bài 3. Một Công ty có ba xí nghiệp cùng loại: A, B, C có khả năng sản xuất được 3 loại
sản phẩm: I, II, III. Biết rằng nếu đầu tư một đơn vị tiền vào xí nghiệp A trong một năm sẽ sản
xuất được 1200 sản phẩm loại I, 800 sản phẩm loại II và 1050 sản phẩm loại III. Đầu tư vào xí
nghiệp B một đơn vị tiền, được 1000 sản phẩm loại I, 740 sản phẩm loại II, 900 sản phẩm loại III.
Đầu tư vào xí nghiệp C một đơn vị tiền thì sản xuất được 1100 sản phẩm loại I, 600 sản phẩm loại
II, 1000 sản phẩm loại III. Định mức tiêu hao nguyên liệu và lao động của mỗi xí nghiệp trong sản
xuất được cho ở bảng 3. Nguyên liệu, lao động hàng năm Công ty có thể cung cấp cho sản xuất ba
loại sản phẩm này là 390.000 KG và 200.000 giờ công. Theo kế hoạch phải sản xuất ít nhất là
23.000 đơn vị sản phẩm loại I, 18.000 đơn vị sản phẩm loại II, và 21.000 đơn vị sản phẩm loại III.
Hãy tìm một phương án đầu tư sao cho thu được các sản phẩm theo kế hoạch mà vốn đầu tư ít
nhất.
Bảng 3
Định mức hao phí ng. liệu (Kg/sản phẩm) và lao động (g/sản phẩm)
Doanh I II III
nghiệp
Ng. liệu Lao động Ng. liệu Lao động Ng. liệu Lao động
A 4 2 10 4 8 4, 5
B 4, 2 3 9 4, 5 7, 8 5
12
Chương I: Một số kiến thức mở đầu
C 4, 5 2, 5 10, 5 5 8, 4 4
Bài 4. Một xí nghiệp quân đội có 4 loại máy: A, B, C, D, sản xuất ra 6 loại sản phẩm I, II,
III, IV, V, VI. Số giờ của mỗi loại máy để sản xuất mỗi loại sản phẩm và giá tiền mỗi loại sản
phẩm ghi ở bảng 4. Năng lực sản xuất của các l\mãy đều có hạn, nếu dùng quá sẽ bị hỏng. Giả sử
trong 1 tuần, mỗi máy loại A, B, C, D tương ứng làm việc không quá 850, 700, 100 và 900 giờ.
Hãy lập một phương án sản xuất để thu được sản phẩm mỗi loại lớn nhất mà vẫn bảo đảm an toàn
cho máy móc và thiết bị.
Bảng 4
Sản phẩm
Loại Loại Loại Loại Loại
Số giờ sản Loại I
II III IV V VI
xuất 1 sp trên máy.
A 0, 01 0, 01 0, 01 0, 03 0, 03 0, 03
B 0, 02 0, 05
C 0, 02 0, 05
D 0, 03 0, 08
Giá 1 sản phẩm (đ/v tiền) 0, 40 0, 28 0, 32 0, 72 0, 64 0, 60
Bài 5. Một máy bay vận tải quân sự có trọng tải M. Cần chở n loại thiết bị bằng máy bay.
Trọng lượng loại bưu kiện i, (i = 1, n ) là αi, có giá trị βi . Hãy tìm phương án chở mỗi loại thiết bị
bao nhiêu đơn vị lên máy bay để trọng lượng tổng cộng không vượt quá tải trọng của máy bay mà
đạt được tổng giá trị lớn nhất ? (Bài toán Qui hoạch nguyên).
13
Chương II: Quy hoạch tuyến tính
CHƯƠNG II: QUY HOẠCH TUYẾN TÍNH
2.1. MỘT SỐ BÀI TOÁN THỰC TẾ DẪN TỚI MÔ HÌNH QUY HOẠCH
TUYẾN TÍNH
2.1.1. Bài toán lập kế hoạch sản xuất.
Giả sử một Công ty sản xuất n loại sản phẩm và phải sử dụng m loại nguyên liệu khác nhau.
Gọi xj là sản lượng sản phẩm loại j, (j = 1, n ) mà Công ty sẽ sản xuất, cj là tiền lãi (hay giá) một
đơn vị sản phẩm loại j, aij là chi phí nguyên liệu loại i, (i = 1, m ), để sản xuất ra một đơn vị sản
phẩm loại j, bi là lượng nguyên liệu loại i tối đa có thể có.
Trong các điều kiện đã cho, hãy xác định sản lượng xj, j = 1, n sao cho tổng tiền lãi (hay
tổng giá trị sản lượng hàng hoá) là lớn nhất với số nguyên liệu hiện có.
Bài toán thực tiễn trên, có thể mô hình toán học như sau:
Tìm x = (x1, x2, ..., xn) ∈ IRn , làm cực đại hàm mục tiêu:
n
f(x) = ∑ cj xj → max
j =1
với các điều kiện:
n
∑ aij xj ≤ bi, i = 1, m ,
j =1
xj ≥ 0, j = 1, n
Bài toán trên là một bài toán Qui hoạch tuyến tính.
2.1.2. Bài toán vận tải.
Có m kho hàng cùng chứa một loại hàng hoá, Ai , i = 1, m (Ai điểm phát thứ i). Lượng hàng
ở kho Ai là ai, (i = 1, m ). Có n địa điểm tiêu thụ hàng Bj, nhu cầu tiêu thụ ở điểm Bj là bj, j = 1, n
(Bi điểm thu thứ i). Biết rằng cước phí vận chuyển một đơn vị hàng hoá từ điểm phát Ai đến điểm
thu Bj là cij. Hãy lập kế hoạch vận chuyển hàng hoá từ các địa điểm phát đến các địa điểm thu
hàng sao cho tổng chi phí vận chuyển là nhỏ nhất.
Nếu ta ký hiệu xij là lượng hàng vận chuyển từ điểm phát Ai, (i = 1, m ) đến điểm thu Bj, với
(j = 1, n ), thì ta có thể mô hình toán học bài toán thực tế như sau:
Tìm véc tơ x= (x1, x2,..., xn+m) ∈ IRnxm ,sao cho:
m n
F(x) = ∑ ∑ cij xij → min
i =1 j =1
với các điều kiện:
14
Chương II: Quy hoạch tuyến tính
n
∑ xij = ai, i = 1, m
j =1
m
∑ xij = bi, j = 1, n
i =1
xij ≥ 0, i = 1, m , j = 1, n
Ngoài ra bài toán phải thoả mãn điều kiện:
n m
∑ bj = ∑ ai (cân bằng thu và phát).
j =1 i =1
Đây là một dạng của bài toán Quy hoạch tuyến tính.
2.1.3. Bài toán người bán hàng (Bài toán cái túi).
Một cửa hàng cần phải vận chuyển một lượng hàng trên một chuyến nặng không được quá
b kg. Có n loại đồ vật mà cửa hàng cần phải vận chuyển đi bán, mỗi đồ vật loại j, (j = 1, n ), có
khối lượng aj kg. Và có giá trị là cj . Hãy xác định xem trong một chuyến hàng, cửa hàng cần đưa
lên phương tiện vận chuyển các đồ vật nào để tổng giá trị các đồ vật thu được là lớn nhất.
Nếu ta ký hiệu xj là số đồ vật loại j sẽ đưa lên phương tiện vận chuyển, ta có mô hình toán
học bài toán như sau:
Tìm x = (x1, x2,...,xn) ∈ |Rn sao cho:
n
f(x) = ∑ cj xj → max
j =1
Với điều kiện:
n
∑ aj xj ≤ b
j =1
xj ≥ 0, j = 1, n
xj - nguyên, j = 1, n
Đây là bài toán Qui hoạch nguyên.
2.1.4. Bài toán lập kế hoạch đầu tư vốn cho sản xuất.
Cần phải đầu tư vốn vào m xí nghiệp để sản xuất ra n loại sản phẩm. Do trang bị kỹ thuật -
công nghệ và tổ chức sản xuất khác nhau nên hiệu quả của vốn đầu tư vào các xí nghiệp cũng
khác nhau. Qua phân tích, người ta biết rằng khi đầu tư một đơn vị tiền vào xí nghiệp thứ i, i =
1, m , trong một năm sẽ sản xuất ra được bij đơn vị sản phẩm loại j, j = 1, n . Tổng số nguyên liệu
và lao động hàng năm có thể cung cấp là A và C (tính theo giờ/công). Hãy xác định một kế hoạch
đầu tư sao cho đảm bảo sản xuất được ít nhất Bj đơn vị sản phẩm loại j mà tổng số vốn đầu tư nhỏ
nhất, biết rằng các định mức hao phí về nguyên liệu và lao động khi sản xuất ra một đơn vị sản
phẩm loại j ở xí nghiệp i, i = 1, m , tương ứng là aij và cij, i = 1, m , j = 1, n .
15
Chương II: Quy hoạch tuyến tính
Gọi vốn đầu tư vào xí nghiệp i là xi đơn vị tiền. Khi đó số lượng sản phẩm loại j sản xuất ở
xí nghiệp i là bij xi và số nguyên liệu sử dụng ở xí nghiệp này để sản xuất ra các sản phẩm j là aij
n
bij xi .Vậy toàn bộ nguyên liệu sử dụng ở xí nghiệp i là ∑ aij bijxi và tổng số nguyên liệu sử
j =1
m n
dụng cho kế hoạch sản xuất chung là: ∑
i =1
∑ aij bij xi.
j =1
m n
Tương tự, ta suy ra tổng số lao động sử dụng trong kế hoạch sản xuất là: ∑ ∑ cij bij xi
i =1 j =1
m
Tổng số vốn đầu tư, theo bài toán đặt ra, là ∑ xi và tổng số sản phẩm loại j sản xuất được
i =1
m
là ∑ bij xi .
i =1
Theo mục tiêu của bài toán thực tế đặt ra thì bài toán có thể mô hình toán học như sau:
Tìm véc tơ x = (x1, x2 ,..., xn) ∈ IRm sao cho:
m
f(x) = ∑ xi → min
i =1
với điều kiện:
m n
∑ ∑ aij bij xi ≤ A
i =1 j =1
m n
∑ ∑ cij bij xi ≤ C
i =1 j =1
m
∑ bij xi ≥ Bj, j = 1, n
i =1
xi ≥ 0, i = 1, m
Đây là một dạng của bài toán Qui hoạch tuyến tính.
2.2. MÔ HÌNH BÀI TOÁN QUY HOẠCH TUYẾN TÍNH.
2.2.1. Bài toán quy hoạch tuyến tính tổng quát
Tìm x = (x1, x2...xi,...xn) ∈IRn.
n
Sao cho: f(x) = Σ Cj xj → max (min) (2.1)
j = 1
Thỏa mãn điều kiện:
n
Σ aij xj (≤, = ≥ ) bi ( i= 1, m ) (2.2)
j = 1
xj≥ 0 (j = 1, n ) (2.3)
16
Chương II: Quy hoạch tuyến tính
Để xây dựng cơ sở lý luận giải bài toán, chỉ cấn xét một trong hai dạng bài toán, chẳng hạn
bài toán tìm giá trị lớn nhất (f → max ) của hàm mục tiêu, còn bài toán tìm giá trị bé nhất (f →
min ) của hàm mục tiêu có thể chuyển đổi như sau:
* Giữ nguyên hệ ràng buộc ( 2.2 ) và ( 2.3 )
n
* Đưa hàm mục tiêu: f(x) = ∑ C x → min
j =1
j j
n
về f (x) = - f (x) = Σ ( - Cj ) xj → max, ta có mô hình bài toán:
j = 1
Tìm x = ( x1 , x2 , ..., xj ,... xn ) ∈IRn
n
Sao cho: f (x) = Σ (- Cj ) xj → max (2.4)
j = 1
n
Thoả mãn điều kiện: Σ aij xj (≤, =, ≥ ) bi ( i = 1, m ) (2.5)
j = 1
xi ≥ 0 ( j = 1, n ) (2.6)
Bổ đề: Nếu bài toán (2.4) ÷ (2.6) có xopt = x*, thì bài toán (2.1) ÷ (2.3) với
f (x) → min cũng có xopt = x* và fmin = - f max
Thật vậy, theo giả thiết (2.4) ÷ (2.6) có xopt = x* với hàm mục tiêu
n
f (x) = Σ (-cj ). xj→ max , thì:
j = 1
f (x) ≤ f (x*) ( ∀x∈D - tập các phương án )
n n n n
⇔ Σ (-cj ). xj ≤ Σ ( - cj ). x *j ⇔ Σ cj. x *j ≤ Σ cj xj
j = 1 j = 1 j = 1 j = 1
⇔ f (x) ≥ f (x*) (∀x ∈ D) ⇔ x* = xopt của (2.1)⎯(2.3) với f(x) → min.
n n
fmin = Σ cj x *j = - Σ (-cj) x *j = - f max ( đpcm )
j = 1 j = 1
Như vậy mọi bài toán (2.1) - (2.3) với f(x) → min có thể chuyển f (x) → max.
2.2.2. Dạng chuẩn tắc
a- Dạng đầy đủ
Tìm x= (x1 ,.... , xj ,.... xn ) ∈ IRn
Sao cho: f(x) = c1x1 +...+ci xi +...+ cn xn → max (2.7)
17
Chương II: Quy hoạch tuyến tính
Thoả mãn a11 x1 +...+ a1i xi +...+a1n xn ≤ b1
a21 x1 +...+ a21xi +...+a2n xn ≤ b2
------------------------------------
ai1 x1 +...+ aii xi +...+ ain xn ≤ b1 (2.8)
--------------------------------
am1 x1+...+ami xi +...+ amn xn ≤ bm
xi ≤ 0 ( i = 1, n ) (2.9)
b. Dạng rút gọn.
n
f(x) = Σ cixi → max
j = 1
n
Σ aii xi ≤ bi ( i= 1, m )
j = 1
xi ≥ 0 ( δ = 1, n )
Tính chất của hàm mục tiêu (2.7) và dạng bất phương trình của hệ ràng buộc (2.8) xuất phát
từ ý nghĩa thực tiễn của bài toán đặt ra. Chẳng hạn như bài toán lập kế hoạch sản xuất để hiệu quả
kinh tế tổng cộng lớn nhất, khi phải hạn chế chi tiết nguyên liệu sử dụng.
Ngược lại, trong bài toán xác định vốn đầu tư cho sản xuất phải khai thác tối đa trang bị kỹ
thuật - công nghệ để sao cho đạt được yêu cầu về giá trị sản phẩm làm ra mà vốn đầu tư ít nhất.
2.2.3 Dạng chính tắc
a- Dạng đầy đủ
n
f (x) = Σ cixi → max (2.10)
i = 1
n
Σ aiixi = bi (i = 1, m ) (2.11)
i = 1
xi ≥ 0 (i = 1, n ) (2.12)
b. Dạng ma trận:
Gọi ma trận hàng, gồm các phần tử là hệ số các ẩn trong hàm mục tiêu là C:
C = [ c1 c2...cn]
Ma trận cột:
⎡ b1 ⎤ ⎡ x1 ⎤
⎢b ⎥ ⎢ ⎥
B = ⎢ 2 ⎥ , x = ⎢ x2 ⎥
⎢⎣ b m ⎥⎦ ⎢⎣ x n ⎥⎦
18