2/12/2017
GV.ThS.HuỳnhĐỗBảoChâu 1
CHƯƠNG 3
LẬP TRÌNH TUYẾN TÍNH
(Linear Programming)
1
TRƯỜNG ĐẠI HỌC NGÂN HÀNG TP.HCM
KHOA HỆ THỐNG THÔNG TIN QUẢN LÝ
KHOA HỌC QUẢN LÝ ỨNG DỤNG
GV. ThS. Huỳnh Đỗ Bảo Châu
Mục tiêu bài học
GV. Huỳnh Đỗ Bảo Châu2
Trình bày đặcđiểmcủa bài toán QHTT
Phân biệtcácdạng bài toán QHTT
Ứng dụng cách xây dựng mô hình cho bài toán QHTT
Sửdụng mộtsốcông cụmáy tính để giải bài toán QHTT
Giải thích kếtquảsau khi giải bài toán QHTT
Nội dung chính
GV. Huỳnh Đỗ Bảo Châu3
1.
Mô hình hóa bài toán QHTT
2.
Phương pháp đồ thị
3.
Giải pháp máy tính
4.
Phân tích độ nhạy
5.
Các mô hình ví dụ
Các giảđịnh cho quy hoạch tuyếntính
GV. Huỳnh Đỗ Bảo Châu4
Các giá trịtham sốlà chắcchắn
Không đổitheoquymô
VD:1spthêm4$lợi nhuận, đòi hỏi3giờ
để sảnxuất, vậy 500 sp thêm $ 4x500, cần
3x500 giờ
Không có tương tác giữacácbiếnquyếtđịnh
2/12/2017
GV.ThS.HuỳnhĐỗBảoChâu 2
1. Mô hình hóa bài toán QHTT
GV. Huỳnh Đỗ Bảo Châu5
Giới thiệu về Bài toán QHTT
GV. Huỳnh Đỗ Bảo Châu6
Xác định x
1
, x
2
, …, x
n
sao cho:
Cực đại (hay Cực tiểu) hàm mục tiêu Z:
Z = z(x
1
, x
2
, …, x
n
)
Đồng thời thỏa mãn các ràng buộc R
j
:
R
j
= r
j
(x
1
, x
2
, …, x
n
)
Trong đó, z và r
j
là biểu thức tuyến tính
đối với x
1
, x
2
, …, x
n
.
Các bước áp dụng kỹ thuật QHTT
GV. Huỳnh Đỗ Bảo Châu7
B1: Xác định vấn đề cần giải quyết mối quan hệ theo
mô hình tuyến tính không.
B2: Nếu là vấn đề không có cấu trúc, cần phân tích và
xây dựng như 1 mô hình toán học
B3: Giải mô hình và tìm ra kết quả bằng cách sử dụng
các kỹ thuật toán học
2 kỹ thuật phổ biến là Đồ thị và Đơn hình.
Xây dựng mô hình QHTT
GV. Huỳnh Đỗ Bảo Châu8
Xác định:
Số biến cần tìm
Hàm mục tiêu (MAX, hoặc MIN)
Các ràng buộc của các biến (các mối quan hệ tuyến tính)
2/12/2017
GV.ThS.HuỳnhĐỗBảoChâu 3
Các dạng bài toán QHTT
GV. Huỳnh Đỗ Bảo Châu9
Cực đại chuẩn ∑

Ràng buộc: ∑



∀1,2,…,
0∀1,2,…
0
Cực tiểu chuẩn ∑

Ràng buộc: ∑



∀1,2,…,
0∀1,2,…
0
Bài toán cực đại (hay cực tiểu) với ràng buộc có dấu ≥và cả dấu ≤.
2. Phương pháp đồ thị
GV. Huỳnh Đỗ Bảo Châu10
Phương pháp đồ thị
GV. Huỳnh Đỗ Bảo Châu11
Sử dụng khi:
Có nhiều ràng buộc dưới dạng bất phương trình
Số biến cần tìm là 2
Cung cấp bức tranh toàn cục về giải pháp bài toán.
Thuận lợi để thực hiện phân tích độ nhạy.
Giải bài toán QHTT bằng PP đồ thị
GV. Huỳnh Đỗ Bảo Châu12
Nghiệmkhảdĩ(Feasible solution): 1 bộgiá trịcác
biếnthỏa mãn các ràng buộc.
Vùng khảdĩ(Feasible region): Tậptấtcảcác
nghiệmkhảdĩ.
2/12/2017
GV.ThS.HuỳnhĐỗBảoChâu 4
Các bước thực hiện (áp dụng cho bài toán 2 biến)
GV. Huỳnh Đỗ Bảo Châu13
B1: Biểu diễn các dữ kiện của bài toán dưới dạng phương
trình hoặc bất phương trình
B2: Giải các phương trình và bất phương trình bằng đồ thị,
kết quả sẽ nhận được 1 vùng khả dĩ
B3: Vẽ 1 đường thẳng biểu diễn hàm mục tiêu và tịnh tiến
đường này tiến về miền nghiệm khả dĩ. Điểm đầu tiên mà
đường hàm mục tiêu chạm với miền nghiệm chính là kết
quả bài toán.
Ví dụ minh họa
(MÔ HÌNH BÀI TOÁN CỰC ĐẠI)
GV. Huỳnh Đỗ Bảo Châu14
Công ty Gốm Beaver Creek sảnxuấtthủcông quy mô
nhỏ,sửdụng các nghệnhân có tay nghềcao để sản
xuấtchénvàly bằng đất sét theo thiếtkếvà màu sắc
củaMỹ.Hainguồnlực chính của công ty là đấtsét
(clay), và lao động có tay nghềcao (labor).
Vớinguồnlựccóhạn, công ty mong muốnbiếtbao
nhiêu cái chén và ly cầnsảnxuấtmỗingàyđể tốiđa
hóa lợinhuận?
Ví dụ minh họa (tt)
GV. Huỳnh Đỗ Bảo Châu15
Ví dụ minh họa (tt)
GV. Huỳnh Đỗ Bảo Châu16
Gọi
: sốchén (bowl) cầnsảnxuất
Gọi
: sốly (mug) cầnsảnxuất
HÀM MỤC TIÊU LỢI NHUẬN:
40
50
→
RÀNG BUỘC:
󰇫1
2
40
4
3
120
với
,
0, int
2/12/2017
GV.ThS.HuỳnhĐỗBảoChâu 5
Ví dụ minh họa (tt)
GV. Huỳnh Đỗ Bảo Châu17
Đường biểu diễn ràng buộc về người lao động
1
2
40
Vùng ràng buộc
nguồn lực lao động
Ví dụ minh họa (tt)
GV. Huỳnh Đỗ Bảo Châu18
Đường biểu diễn ràng buộc về lượng đất sét nguyên liệu
4
3
120
Kết hợp 2 ràng buộc
có vùng khả dĩ
Vùng ràng buộc
nguyên liệu đất sét
Ví dụ minh họa (tt)
GV. Huỳnh Đỗ Bảo Châu19
Vẽ đường hàm mục tiêu với giá trị F bất kỳ
40
50
Đường hàm mục tiêu
với F = 800
Ví dụ minh họa (tt)
GV. Huỳnh Đỗ Bảo Châu20
Tìm giá trị của kết quả
,
24,
8→ 1.360
Tịnh tiến
đường hàm mục tiêu
Kết quả tại
B (24,8)