Tạp chí Thông tin toán học - Tập 12 Số 3 Tháng 10 Năm 2008

g đẳng cấp bậc 3
Kết quả nghiên cứu hồi đó về “qui hoạch và
đồ thị” được đúc kết trong các giáo trình: Đồ
thị hữu hạn và ứng dụng trong vận trù học
(H. Tụy, 1964); Phương pháp sơ đồ mang lưới
PERT (N. Q. Thái, H. P. Oanh, 1968); Lý
thuyết qui hoạch - Tập I (H. Tụy, 1968).
•Tối ưu toàn cục. Qui hoạch tuyến tính và lồi
thuộc lớp bài toán một cực trị. Một thành tựu
đáng chú ý là lần đầu tiên nghiên cứu các bài
toán tối ưu không lồi (nhiều cực trị) và mở ra
một hướng nghiên cứu mớt “tối ưu toàn cục”.
Ta bắt đầu từ các bài toán cơ bản:
- Qui hoạch lõm (BCP): min{f(x) : x ∈
D}, trong đó f(x) là hàm lõm, D là tập lồi
đóng. Đặc biệt quan trọng là trường hợp D
là tập lồi đa diện. Đây là bài toán cơ bản
của tối ưu toàn cục, vì tính phổ biến của
nó và vì nhiều bài toán tối ưu toàn cục qui
về nó hoặc dựa ít nhiều trên phép giải nó.
f(x) = x1/2 g(x) =
[
m + cx, x > 0
0, x ≤ 0
a) Hàm lõm b) Hàm lõm với
phụ phí cố định
-Qui hoạch lồi đảo (CDC): min{f(x) : x ∈
D,h(x) ≥ 0}, trong đó f(x), h(x) là hàm
lồi, D là tập lồi đóng.
Bài toán này chỉ khác qui hoạch lồi ở chỗ
có thêm ràng buộc lồi đảo h(x) ≥ 0. Đặt
C = {x : h(x) ≤ 0} thì C là tập lồi
đóng và bài toán (CDC) có thể viết thành:
min{f(x) : x ∈ D \ int C}.
Ví dụ về bài toán qui hoạch lồi đảo: Tìm vị
trí bắc một cây cầu ngắn nhất nối đất liền với
đảo D ở giữa hồ nước H: min{d(x,D) : x ∈
R
n \ int H} (D,H lồi và hàm khoảng cách
d(x,D) lồi ∀x ∈ Rn).
-Qui hoạch d.c.: min{f(x) : x ∈ D,h(x) ≥
0}, trong đó f(x), h(x) đều là hàm d.c. –
hiệu hai hàm lồi, D là tập lồi đóng.
- Bài toán tối ưu không lồi bất kỳ: Cả hàm
mục tiêu và các hàm ràng buộc đều bất kỳ
(d.c. hoặc không d.c.). Hai trường hợp riêng
đáng chú ý:
- Tối ưu liên tục (hàm mục tiêu và các hàm
ràng buộc đều liên tục): bài toán có dạng
min{f(x) : x ∈ D}, trong đó D là một tập
đóng, f là một hàm liên tục. Có thể chứng
minh rằng mọi bài toán tối ưu liên tục qui
được về bài toán tối ưu d.c.
- Tối ưu 0 − 1: bài toán có những ràng buộc
dạng xj ∈ {0; 1}, j = 1, . . . , n. Các ràng
buộc này cũng có thể viết lại thành ràng buộc
d.c., vì
xj ∈ {0; 1} ⇐⇒
0 ≤ xj ≤ 1 và xj(xj − 1) ≥ 0
(ràng buộc lồi đảo). Như vậy, trên nguyên tắc
mọi bài toán tối ưu rời rạc (tối ưu tổ hợp) đều
có thể phát biểu lại thành bài toán tối ưu d.c.
Lần đầu tiên H. Tụy đề xuất phương pháp cắt
giải bài toán qui hoạch lõm (Concave pro-
gramming under linear constraints. Soviet
Math. 5(1964), 1437-1440). Tiếp sau là các
phương pháp chia nón, nhánh và cận, phương
pháp xấp xỉ ngoài, xấp xỉ trong, phương pháp
hạ thấp thứ nguyên bài toán, phương pháp
12
phân rã... Đã có những nghiên cứu các dạng
bài toán tối ưu không lồi khác nhau: qui
hoạch song tuyến tính, bài toán bù tuyến tính,
qui hoạch lồi - lõm, qui hoạch với ràng buộc
lồi đảo, qui hoạch tích các hàm tuyến tính,
qui hoạch toàn phương không lồi, v.v... Các
kết quả nghiên cứu của nhóm tối ưu toàn cục
Viện Toán học được phản ánh, tổng kết trong
các sách chuyên khảo, xuất bản nhiều lần ở
nước ngoài: Global Optimization (Determin-
istics Approaches), chủ biên: R. Horst & H.
Tụy (1990, 1993, 2004) và Convex Analysis
and Global Optimization (H. Tụy, 1998). Về
sự phát triển tiếp theo của hướng tối ưu hoá
ở Viện Toán học, xin xem thêm các bài viết
của GS Lê Dũng Mưu và GS Nguyễn Đông
Yên đăng trên “Thông tin Toán học” Tập 12,
Số 1 - Tháng 3/2008.
4. Hoạt động ứng dụng thực tiễn • Ứng
dụng vận trù học trong vận tải dân sự, chủ
yếu ở các xí nghiệp vận tải Hà Nội, Vinh,
Vĩnh Yên... và quân sự (ở Cục vận tải C27 -
Bộ quốc phòng). Xin nêu một vài hồi ức thời
đó: 5 cán bộ Viện toán, gồm:
1. Phan Van Chương (giải tích hàm, trưởng
nhóm);
2. Trần Văn Nho (toán học tính toán);
3. Hồ Thuần (toán học tính toán);
4. Phạm Hữu Sách (phương trình vi phân);
5. Trần Vũ Thiệu (tối ưu)
và 2 cán bộ giảng dạy của Khoa toán, Đại học
tổng hơp Hà Nội:
1. Nguyễn Hữu Ngự (lôgíc toán, trưởng
nhóm);
2. Trần Đức Long (giải tích hàm)
được biệt phái sang Cục vận tải, Tổng cục
hậu cần, nhằm nghiên cứu ứng dụng toán
trong công tác vận tải quân sự, do yêu cầu
của ông Đinh Đức Thiện (nguyên Tổng cục
trưởng Tổng Cục hậu cần, Bộ quốc phòng).
Vào tuyến lửa Binh trạm 10 (Thanh Hoá),
Binh trạm 12 (Quảng Bình) và Binh trạm 15
(Quảng Trị) trong các năm Mỹ đánh phá ác
liệt miền Bắc (1966 - 1968). Có thể nói đóng
góp về khoa học không nhiều, chủ yếu thể
hiện tinh thần tham gia chống Mỹ, cứu nước
của cán bộ toán hồi đó. Nhân đây, cũng xin
kể một chi tiết đáng ghi nhớ về tinh thần cán
bộ khoa học ta: vào khoảng 5/1966, trước
khi sang Liên Xô (cũ) học tập, công tác, một
đoàn cán bộ khoa học trẻ của ủy ban khoa học
nhà nước còn đi vào tuyến lửa miền Trung
(bến phà Ghép), nơi địch đang đánh phá rất
ác liệt, để tìm hiểu thực tế cuộc chiến đấu của
quân và dân ta. Dẫn đầu đoàn là anh Nguyễn
Đình Tứ (lúc đó Phụ trách Ban Toán lý), trong
đoàn có anh Đỗ Long Vân (Chủ tịch Hội Toán
học Việt Nam sau này).
• Pha cắt tiết kiệm vật liệu thanh ở Công
ty gang thép Thái Nguyên, 1963 (nhóm tối
ưu Viện Toán học, gồm các anh Đỗ Long
Vân, trưởng nhóm, Phạm Hữu Sách, Phạm
Trà Ân, Trần Vũ Thiệu), vật liệu tấm ở nhà
máy Hoa quả hộp Hà Nội, 1963 (H. Tụy, T.
V. Thiệu), nhà máy sắt tráng men Hải Phòng,
1965 (nhóm toán tối ưu Khoa toán Đại học
tổng hơp Hà Nội, anh Nguyễn Quý Hỷ phụ
trách). . .
• Vận dụng phương pháp sơ đồ mạng lưới
PERT ở nhà máy phân đạm Bắc Giang
(1965), ở Sở xây dựng và kiến trúc Hà Nội
(1967-1968): Tổ vận trù học Hà Nội (nòng
cốt là các anh Nguyễn Văn Sinh, Nguyễn
Minh Tuân...). Xin kể mẩu chuyên vui: 3 thày
trò chúng tôi (thày H. Tụỵ, anh N. Q. Thái và
tôi), lên tàu đi Phủ Lạng Thương (Bắc Gi-
ang), xe nhà máy ra ga đón. Cùng chuyến
công tác có nguyên Chủ nhiệm ủy ban kiến
thiết cơ bản Nhà nước (tôi không nhớ rõ tên),
khi tiếp Ban giám đốc nhà máy, ông ta giới
thiệu thày Tụy là “Giáo sư” đại học tổng hợp,
còn anh Thái và tôi (lúc đó chưa đầy 24 tuổi,
không có chức trách gì) được giới thiệu là
“Giảng sư” đại học (!). Chúng tôi ở lại làm
việc khoảng một tuần, tìm hiểu tình hình xây
dựng nhà máy, ghi chép số liệu cần thiết rồi
trở về Hà Nội xử lý.
5. Phổ biến kiến thức, đào tạo đội ngũ
• Ấn phẩm (lưu hành nội bộ, trong gần 30
năm): Tập tài liệu Vận trù học (Số 1/1965 –
13
22/1972) Nội san Toán kinh tế và Vận trù học
(Số 23/1973 – 35/1985) Nội san Vận trù học
và Nghiên cứu hệ thống (Số 36 – 44/1992)
(chủ yếu in rônêô), được cấp giấy phép xuất
bản, dùng làm tài liệu học tập, tham khảo nội
bộ trong giới tối ưu. Đáng chú ý:
- Tập tài liệu Vận trù học dành trọn Số 1
(1965) in bài dịch từ bản gốc tiếng Nga giới
thiệu “Phương pháp sơ đồ mạng PERT”, Trần
Văn Nho dịch.
- Nội san Vận trù học dành Số 19 (1971) in
giáo trình “Qui hoạch phi tuyến” gồm Phần
1: Qui hoạch lồi (H. Tụy viết), Phần 2. Qui
hoạch hình học (T. V. Thiệu trích dịch cuốn
“Geometric Programming - Theory and Ap-
plications” (R.J. Duffin, E.L. Peterson và C.
Zener.. New York, 1967).
- Nội san Toán kinh tế và Vận trù học dành
trọn số 31 (1980) in bản dịch cuốn V. G.
Karmanov. Qui hoạch toán học (tiếng Nga).
“Hayka” Mátxcơva, 1975.
• Sách phổ biến kiến thức: đông đảo cán bộ
viết sách giới thiệu về vận trù - tối ưu nhằm
truyền bá, thúc đẩy ứng dụng môn khoa học
này vào thực tiễn: Vận trù học là gì? (H.Tụy,
T. V. Thiệu, 1967), Tìm hiểu về vận trù học
(T. V. Thiệu, N. Q. Thái, 1976), Thuật toán
và chương trình máy tính trong kinh tế (T.
V. Thiệu, Ng. V. Thiều và B. T. Tâm, 1987),
Vận trù học phổ thông (Hoàng Kỳ - ĐHSP
Vinh), Vận trù học trong giao thông vận tải
(Nguyễn Công Thuý - ĐHTH HN), Vận trù
học trong công nghiệp (Phạm Xuân Ninh -
ĐHBK HN), Vận trù học trong nông nghiệp
(Ngô Hân - ĐHSP HN), v.v... Ngoài ra, còn
có một số ấn phẩm dịch từ tiếng Nga làm tài
liệu tham khảo, tra cứu: Từ điển tra cứu toán
học và điều khiển học trong kinh tế (nhóm
tối ưu Viện toán học dịch, H. Tụy hiệu đính,
1980), Cơ sở điều khiển học kinh tế (N. E.
Kobrinski, 1981), Nhập môn điều khiển học
kinh tế (O. Lange, 1973)...
• Đào tạo đội ngũ
- Mở được nhiều lớp bồi dưỡng kiến thức về
vận trù học, toán kinh tế cho cán bộ vận trù,
tối ưu thời đó. Có những anh, chị ở rất xa Hà
Nội cũng về dự thường xuyên, ghi chép bài
vở đầy đủ. Trong số đó chị Đàm Lê Đức (cựu
sinh viên toán tổng hợp khoá I (1956-1959)
nêu tấm gương sáng về chịu khó và bền bỉ
học tập, ai biết cũng phải thán phục.
- Từ thời kháng chiến gian khổ, nhà nước đã
chủ trương gửi nhiều cán bộ trẻ ra nước ngoài
đào tạo PTS, TS nhằm chuẩn bị đội ngũ cán
bộ khoa học cho tương lai (nhờ đó tôi và anh
Phạm Hữu Sách được rút từ Bộ quốc phòng
về, cho đi nghiên cứu sinh ở Liên Xô đầu
năm 1967). Mặt khác, sau 1975 ở ta thực hiện
thí điểm đào tạo nghiên cứu sinh trong nước
(N. Q. Thái, Đ. V. Lưu, N. V. Thoại, L. D.
Mưu...).
6. Hội nghị. Hội thảo khoa học, trường hè.
- Hội nghi vận trù học toàn miền Bắc lần thứ
nhất (1964) tổng kết hoạt động ứng dụng vận
trù học giai đoạn 1960-1964. Bộ trưởng giao
thông vận tải Phan Trọng Tuệ đến dự và phát
biểu động viên phong trào.
- Hội nghi vận trù học toàn miền Bắc lần thứ
hai (1968) tổng kết thành tích ứng dụng vận
trù học và PERT giai đoạn 1965 – 1968.
- Trường hè vận trù Đồ Sơn (1971, Sở giáo
dục Hải Phòng).
- Trường hè tối ưu Tam Đảo (1983, Học Viện
Kỹ thuật quân sự). Tấm ảnh dưới đây chụp
tại Trường hè Tam Đảo thấm thoát đã một
phần tư thế kỷ, tuy vậy ta vẫn có thể nhận ra
nhiều gương mặt quen thuộc: các GS Hoàng
Tụy, Phạm Hữu Sách, Phạm Thế Long, Phan
Quốc Khánh, Lê Dũng Mưu, Nguyễn Đông
14
Yên, các PGS Bùi Thế Tâm, Phan Huy Khải,
Trương Xuân Đức Hà, Nguyễn Văn Châu, Tạ
Duy Phượng, Nguyễn Đức Hiếu, Phạm Văn
Ất và nhiều bạn đồng nghiệp khác.
Bài viết này chủ yếu dựa trên trí nhớ còn sót
lại sau gần 45 năm hoạt động trong lĩnh vực
tối ưu. Hoàn toàn không có sự ghi chép nào
từ trước, vì thế chắc chắn có những điểm sai
sót. Rất mong các bạn đồng nghiệp cùng thời
thông cảm và lượng thứ. Kết thúc bài viết này,
tác gi