ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
-------------------------------

LÊ ĐÌNH THẢN

THUẬT TOÁN GIẢI MỘT SỐ BÀI TOÁN TỐI ƯU
PHÂN THỨC TUYẾN TÍNH VÀ PHI TUYẾN

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN - 2018


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
-------------------------------

LÊ ĐÌNH THẢN

THUẬT TOÁN GIẢI MỘT SỐ BÀI TOÁN TỐI ƯU
PHÂN THỨC TUYẾN TÍNH VÀ PHI TUYẾN
Chuyên ngành: Toán ứng dụng
Mã số
: 8460112

LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC

GS.TS. Trần Vũ Thiệu


2.1.3. Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . 20
2.2. PHƯƠNG PHÁP ĐƯA VỀ HAI BÀI TOÁN (LP) . . . . . 25
2.2.1. Cơ sở của phương pháp . . . . . . . . . . . . . . . . 26
2.2.2. Phương pháp hạn chế hàm mục tiêu ở mẫu số . . . 27
2.2.3. Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . 28
2.2.4. Bài toán cực tiểu . . . . . . . . . . . . . . . . . . . 29
3 TIẾP CẬN THAM SỐ GIẢI QUY HOẠCH PHÂN THỨC
PHI TUYẾN
32


iv

3.1. THUẬT TOÁN DINKELBACH . . . . . . . . . . . . . . . 32
3.1.1. Ký hiệu và kết quả chuẩn bị . . . . . . . . . . . . . 32
3.1.2. Sự hội tụ toàn cục của thuật toán . . . . . . . . . . 34
3.2. THUẬT TOÁN DINKELBACH RÚT GỌN . . . . . . . . 36
3.3. ÁP DỤNG GIẢI QUY HOẠCH PHÂN TUYẾN TÍNH . . 39
Kết luận
Tài liệu tham khảo

44
45


1

DANH MỤC CÁC KÝ HIỆU
R
Rn


x≥y

Véctơ x lớn hơn hay bằng véctơ y,
(xi ≥ yi , ∀i = 1, ... , n)

x∈X
x∈
/X

x là một phần tử của tập X
x không là phần tử của tập X

int X

Phần trong của tập X

C
∅

Bao đóng của tập C
Tập hợp rỗng

A+B
A∪B

Tổng véctơ của hai tập A và B
Hợp của hai tập A và B

A∩B

- Hình 2.2. Tập ràng buộc S của bài toán ở Ví dụ 2.2
- Hình 2.3. Tập ràng buộc S của bài toán ở Ví dụ 2.6
Chương 3:
- Hình 3.1. Sơ đồ khối thuật toán Dinkelbach


4

MỞ ĐẦU
Quy hoạch phân tuyến tính (Linear Fractional Programming, viết
tắt LFP), rộng hơn là quy hoạch phân thức phi tuyến, là một mở rộng
trực tiếp của quy hoạch tuyến tính (Linear Programming, viết tắt LP),
với đối tượng nghiên cứu là các bài toán tìm cực tiểu (cực đại) một hàm
phân tuyến tính (tỉ số hai hàm tuyến tính afin), trên một tập ràng buộc
được xác định bởi các đẳng thức hay bất đẳng thức tuyến tính.
Các bài toán quy hoạch phân tuyến tính thường dùng để mô tả
toán học cho nhiều bài toán thực tế với các hàm mục tiêu phân thức,
chẳng hạn: lợi nhuận/chi phí, sản phẩm/số lao động, v.v ... và được ứng
dụng rộng rãi trong nhiều lĩnh vực khác nhau của kinh tế, tài chính, kỹ
thuật, v.v...
Quy hoạch phân tuyến tính có nhiều điểm tương đồng với quy
hoạch tuyến tính, cả về lý thuyết lẫn phương pháp giải. Trong một số
trường hợp riêng, bài toán quy hoạch phân tuyến tính trở thành bài toán
quy hoạch tuyến tính và do đó có thể giải theo thuật toán đơn hình quen
thuộc của quy hoạch tuyến tính. Trong trường hợp tổng quát, nhiều tác
giả cũng đã tìm cách đưa việc giải quy hoạch phân tuyến tính về giải
một hay nhiều bài toán quy hoạch tuyến tính.
Luận văn với đề tài "Thuật toán giải một số bài toán tối ưu
phân thức tuyến tính và phi tuyến" nhằm tìm hiểu và trình bày
một số thuật toán mới gần đây, nêu ở các tài liệu tham khảo [5] - [7],