Khoa Khoa học Tự nhiên và Xã hội – Đại học Thái Nguyên
Bài giảng: Toán Quy hoạch 03/2008 Ths. Ngô Văn Định
Chương 1. Bài toán Quy hoạch tuyến tính
1.1. Khái niệm bài toán QHTT
1.2. Cơ sở Giải tích lồi

Khoa Khoa học Tự nhiên và Xã hội – Đại học Thái Nguyên
Bài giảng: Toán Quy hoạch 03/2008 Ths. Ngô Văn Định
1.1. Khái niệm bài toán QHTT
1.1.1. Bài toán tối ưu
1.1.2. Một số ví dụ về QHTT
1.1.3. Bài toán QHTT

Khoa Khoa học Tự nhiên và Xã hội – Đại học Thái Nguyên
Bài giảng: Toán Quy hoạch 03/2008 Ths. Ngô Văn Định
1.1.1. Bài toán tối ưu
a) Bài toán
Tìm x=(x
1
,x
2
,…,x
n
) sao cho
f(x)=f(x
1
,x
2
,…,x
n

(1.2) : Các ràng buộc BĐT
(1.3) : Các ràng buộc đẳng thức

Khoa Khoa học Tự nhiên và Xã hội – Đại học Thái Nguyên
Bài giảng: Toán Quy hoạch 03/2008 Ths. Ngô Văn Định
Phương án, phương án tối ưu
Tập hợp
D={xєX: g
i
(x)≤0, i=1,…,m; h
j
(x)=0, j=1,…,p}
Được gọi là Miền ràng buộc, hoặc Miền chấp
nhận được, hoặc Tập các phương án.
Mỗi x∈D là một phương án hay một điểm chấp
nhận được
Một phương án x*∈D đạt cực tiểu (hay cực đại)
của hàm mục tiêu là một phương án tối ưu
f(x*) là giá trị tối ưu của bài toán.

Khoa Khoa học Tự nhiên và Xã hội – Đại học Thái Nguyên
Bài giảng: Toán Quy hoạch 03/2008 Ths. Ngô Văn Định
Nhận xét:
Có ba khả năng có thể xảy ra:
a. Miền ràng buộc là tập rỗng.
b. Cực tiểu (cực đại) của f trên D bằng -∞ (+∞).
c. f đạt cực tiểu (cực đại) hữu hạn trên D.

Khoa Khoa học Tự nhiên và Xã hội – Đại học Thái Nguyên
Bài giảng: Toán Quy hoạch 03/2008 Ths. Ngô Văn Định

và V
2
. Các số liệu
được cho bởi bảng:
Lập kế hoạch sx sao cho
tổng thu lớn nhất.
SP
VL
S
1
S
2
Số VL
có
V
1
4 3 120
V
2
5 2 108
Giá
SP
50tr 30tr

Khoa Khoa học Tự nhiên và Xã hội – Đại học Thái Nguyên
Bài giảng: Toán Quy hoạch 03/2008 Ths. Ngô Văn Định
Lập mô hình toán
Gọi x
1
, x

1 2
1 2
( ) 50 30 ax,
4x 3 120,
5x 2 108,
x 0, 0.
f x x x m
x
x
x
= + →
+ ≤


+ ≤


≥ ≥


Khoa Khoa học Tự nhiên và Xã hội – Đại học Thái Nguyên
Bài giảng: Toán Quy hoạch 03/2008 Ths. Ngô Văn Định
Tổng quát
Nếu xí nghệp cần sx n sp từ m vật liệu
a
ij
: số VL i cần để sx 1 đơn vị sp j
b
i
: lượng VL i mà xí nghiệp có

Bài giảng: Toán Quy hoạch 03/2008 Ths. Ngô Văn Định
b) Bài toán vận tải:
Cần vận chuyển một loại mặt hàng nào đó từ m kho
chứa A
1
, A
2
, …, A
m
với trữ lượng tương ứng là a
1
,
a
2
, …, a
m
(đv) đến n cửa hàng tiêu thụ B
1
, B
2
, …, B
n

với nhu cầu tương ứng là b
1
, b
2
,…, b
n
(đv). Giả

1
B
2
b
2
B
3
b
3
c
11
c
21
c
12
c
23
c
22
c
13
x
13
x
11
x
12
x
21
x