Bài giảng Tin học ứng dụng trong kinh doanh - Chương 6: Bài toán tối ưu

Chương 6

Bài toán tối ưu

GV: Nguyễn Thị Thùy Liên

Email: lien.nguyenthithuy@phenikaa-uni.edu.vn

Bài toán tối ưu

❖ Trong toán học, thuật ngữ tối ưu hóa chỉ việc nghiên cứu

cá bài toán có dạng: Cho trước một hàm f: A->R từ tập hợp A tới tập số thực. Tìm: một phần từ x0 thuộc A:

sao cho f(x0)≤f(x) với mọi x thuộc A(“cực tiểu hóa”) hoặc sao cho f(x0)≥f(x) với mọi x thuộc A(“cực đại hóa”)

❖ Một phát biểu bài toán như vậy đôi khi được gọi là một

quy hoạch toán học. Nhiều bài toán thực tế và lý thuyết có thể được mô hình theo cách tổng quát trên.

Tin học ứng dụng

Bài toán tối ưu

❖ Miền xác định A của hàm f được gọi là không gian tìm

kiếm. Thông thường là tập con của Rn , thường được xác định bởi một tập các ràng buộc, các đẳng thức, bất đẳng thức mà các thành viên của A phải thỏa mãn.

❖ Các phần tử của A được gọi là các lời giải khả thi. ❖ Hàm f được gọi là hàm mục tiêu hoặc hàm chi phí cực tiểu hóa(hoặc cực đại hóa) hàm mục tiêu được gọi là lời giải tối ưu.

❖ Các lĩnh vực con chính: ▪ Quy hoạch tuyến tính ▪ Quy hoạch phi tuyến

Tin học ứng dụng

Bài toán quy hoạch tuyến tính

❖Mô hình bài toán quy hoạch tuyến tính (QHTT) ❖Hàm mục tiêu: f(x1,.. xn ) =

Hệ ràng buộc

: ràng buộc quản lý (=, >=, <=)

Xi là các số thực

Tin học ứng dụng

Bài toán quy hoạch tuyến tính

❖Phương án: Một véc tơ x=(x1 , x2 ,….xn) thỏa mãn hệ

ràng buộc phương án của bài toán

❖Phương án tối ưu: Một phương án mà tai đó hàm mục

tiêu đạt giá trị cực tiểu (hoặc cực đại)

=> Giải bài toán tối ưu chính là đi tìm phương án tối ưu

Tin học ứng dụng

Quy trình giải bài toán tối ưu trong Excel

❖Mô tả bài toán – Lập mô hình

❖Tổ chức dữ liệu trong Excel

❖Giải bài toán bằng Solver

Tin học ứng dụng

Lập mô hình

❖B1: Xác định và đặt tên biến

▪ Biến quyết định: nhà quản lý “kiểm soát được”

▪ Biến ngoài: ảnh hưởng nhưng không kiểm soát

được -> tham số bài toán

▪ Biến trung gian: làm rõ ý nghĩa hơn bài toán

Phải đặt tên cho các biến

Ví dụ: x1- chọn xe đạp; c1- chi phí xe đạp, v- giá vé

xe bus…

Tin học ứng dụng

Lập mô hình

❖B2: Xác định mục tiêu => hàm mục tiêu

Xác định mục tiêu và biểu diễn dưới dạng hàm mục tiêu (hàm theo biến quyết định ở bước 1 và dạng mục tiêu -> min/max)

Z(X) = CX =>min/max/const

Ví dụ: Cực đại hóa lợi nhuận

Lợi nhuận = Z(x) = c1x1+ c2x2 + c3x3 ->max

Ví dụ: Cực tiểu hóa chi phí

Tin học ứng dụng

Chi phí = Z(x = c1x1+ c2x2 + c3x3 ->min 8

Lập mô hình

❖B3: Xác định hệ ràng buộc

Xác định tất cả các hạn chế, ràng buộc đối với bài toán và biểu diễn dưới dạng phương trình hay bất phương trình theo các biến quyết định

AX B

X ≥ 0

Chú ý: Ràng buộc tự nhiên: Giá trị không âm, số

nguyên, chọn. Không chọn

Ví dụ: xi ≥ 0 (i=1,n); xi nguyên, Xi ϵ {0,1}

Tin học ứng dụng

Lập mô hình – ví dụ

B=TR-TC =0

❖Bài tập: mô hình hóa bài toán điểm hòa vốn (BEP) ❖Biến quyết đinh: Q: sản lượng ❖Tham số: F: cp cố định, V cp biến đổi bình quân, P giá ❖Biến trung gian: TC:tổng cp, TR:tổng lợi nhuận ❖Hàm mục tiêu: B: lợi nhuận, ❖Phương tình quan hệ: TR = P*Q, TC = F+V*Q, Q≥0

❖=>giải: B= TR-TC = P*Q – (F+V*Q) = Q(P-V)-F

B = Qhv(P-V) –F =0 (hòa vốn)  Qhv = F/(P-V)

Tin học ứng dụng

Tổ chức dữ liệu trong Excel

❖Ví dụ: tổ chức dữ liệu BEP

Biến quyết định (giá trị hằng)

Giá trị gốc

Hàm mục tiêu (công thức)

Phương trình quan hệ

Tin học ứng dụng

Bài toán

❖Một doanh nghiệp sản xuất quần áo, có một máy sản xuất quần và hai máy sản xuất ao. Công suất tối đa của máy sản xuất quần là 5000 cái/tháng. Công suất tối đa của máy sản xuất áo là 10000 cái/tháng. Tổng vống công ty chi tiêu cho sản xuất hàng tháng là 500 triệu đồng. Chi phí sản xuất 1 quần là 60.000 đ/cái. Chi phí sản xuất áo là: 40.000đ/cái. Giá bán một quần là : 100.000đ/cái. Giá bán một áo là 65.000đ/cái.

❖Mục tiêu của công ty là tối đa hóa lợi nhuận. Anh/chị hãy tính số lượng quần, số lượng áo cần thiết sản xuất và lợi nhuận hàng tháng của công ty.

Tin học ứng dụng

Bài toán

❖B1: Lập mô hình

▪ 1. Xác định biến các biến

• Biến quyết định: Gọi x1 là số lượng quần, x2 là số lượng

áo cần sản xuất

• Xác định tham số: a1: giá quần, a2: giá áo, b1: chi phí

quần, b2: chi phí áo ▪ 2. Xác định hàm mục tiêu • Mục tiêu tối đa lợi nhuận: B = B(quần) + B(áo) -> max => c1.x1+c2.x2 -> max (c1 = a1-b1) (c2 = a2-b2) ▪ 3. Xác định ràng buộc

• Ràng buộc chi phí: 60000x1+40000x2<=500000000 • Công suất : x1<=5000, x2<=10000 • Ràng buộc tự nhiên x1>=0, x2>=0

Tin học ứng dụng

Bài toán

❖B2: Thiết lập dữ liệu cho bài toán

Tin học ứng dụng

Giới thiệu Solver

❖Solver là một công cụ cấp cao của excel, nhưng có ít

người biết đến nó

❖Solver có rất nhiều ứng dụng, từ kinh doanh,

marketing, xây dựng thời gian biểu, đầu tư cổ phiếu, giải bài toán quy hoạch tuyến tính.. Đều có thể sử dụng solver và giải chúng một cách nhanh chóng.

❖Giả sử bạn có một số tiền tiêu vặt hàng tháng, làm sao để cân đối các khoản chi tiêu để ăn sáng, xăng xe, mua sách vở,….

Tin học ứng dụng

Công cụ solver

❖B1: Nhấp chuột vào menu Tools ở trên thanh menu.

❖B2: Nhấp chuột vào chữ Add-Ins, khi đó một cửa sổ

sẽ hiện ra

Tin học ứng dụng

Công cụ solver

❖B3: Nhấp chuột chọn Solver Add-Ins

❖B4: Nhấp chuột vào nút OK, khi đó trong Tools sẽ có

hàng Solver

Tin học ứng dụng

Tìm lời giải bằng Solver

❖B5: Menu Tool -> Solver

Giải quyết

Hàm mục tiêu

Các ẩn

Các ràng buộc

Nhập các ràng buộc

Làm lại

Tin học ứng dụng

Công cụ Solver – solver option

Tham số Giải thích

Max Time Thời gian tối đa để giải bài toán, giá trị mặc định là 100 giây dùng cho các bài toán đơn giản. Thời gian tối đa có thể nhập là 32.767 giây.

Iterations Số lần lặp tối đa để giải bài toán, giá trị mặc định là 100 lần dùng cho các bài toán đơn giản. Thời gian tối đa có thể nhập là 32.767 giây.

Công cụ Solver – solver option

Precision

Độ chính xác của bài toán. Tại đây có thể nhập vào các số trong khoảng 0 và 1. Số càng gần 0 thì độ chính xác càng cao. Giá trị này điều chỉnh độ sai số cho tập ràng buộc. Giá trị mặc định là 1 phần triệu.

Tolerance

Chỉ áp dụng đối với bài toán có ràng buộc nguyên. Nhập vào sai số có thể chấp nhận được, sai số càng lớn thì tốc độ giải càng nhanh. Giá trị mặc định là 5%.

Công cụ Solver – solver option

Convergence

Chỉ áp dụng cho các bài toán không tuyến tính. Tại đây nhập vào các số trong khoảng 0 và 1. Số càng gần 0 thì độ chính xác càng cao và cần nhiều thời gian hơn.

Assume Linear Model

Chọn để tăng tốc độ giải bài toán khi tất cả quan hệ trong mô hình là tuyến tính.

Công cụ Solver – solver option

Chọn tùy chọn này nếu muốn Solver giả định là tất cả các biến là không âm.

Assume Non- Negative

Use Automatic Scaling

Chọn khi bài toán mà các dữ liệu nhập và xuất có sự khác biệt lớn. Ví dụ bài toán tối ưu % lợi nhuận trên hàng triệu USD vốn đầu tư.

Chọn nếu muốn Solver tạm dừng lại và hiển thị kết quả sau mỗi lần lặp.

Show Iteration Results

Công cụ Solver – solver option

Estimates

Derivatives

Chọn phương pháp cho Solver dùng để ước lượng các biến: Tangent: Sử dụng cách xấp xỉ tuyến tính bậc nhất Quadratic: Sử dụng cách xấp xỉ bậc bốn Chọn cách để ưức lượng hàm mục tiêu và các ràng buộc Forward: được dùng phổ biến hơn, khi đó các giá trị của ràng buộc biến đổi chậm. Central: Dùng khi các giá trị của ràng buộc biến đổi nhanh và được dùng khi Solver báo không thể cải tiến kết quả thu được 23

Công cụ Solver – solver option

Quy định giải thuật tìm kiếm kết quả cho bài toán Newton: là phương pháp mặc định, nó sử dụng nhiều bộ nhớ hơn và số lần lặp ít hơn. Conjugate: Cần bộ nhớ ít hơn nhưng số lần lặp nhiều hơn.

Giải bài toán tối ưu bằng Solver

Tin học ứng dụng

Bài toán nguyên vật liệu

Một nhà máy dự định tiến hành sản xuất 5 loại sản phẩm Sj (j = 1,5). Cả 5 loại sản phẩm này đều sử dụng 4 loại nguyên vật liệu chính NVLi (i=1,4). Có mức tiêu hao nguyên vật liệu, lợi nhuận đơn vị thu được và giới hạn dự trữ như sau:

S1 S2 S3 S4 S5 Dự trữ

NVL 1 2 5 8 4 1200 6

NVL 2 3 1 6 1 800 5

NVL 3 7 5 5 2 2000 4

NVL 4 8 5 9 1 1865 7

Hãy xây dựng phương án sản xuất để nhà máy đạt được tổng lợi nhuận lớn nhất

Lợi nhuận đơn vị 300 250 500 150 320

Tin học ứng dụng

B1: Lập mô hình

❖ B1: Xây dựng bài toán

Gọi xj (j=1,5) là sản lượng sản phẩm loại j sẽ sản xuất (xj>0)

Phương án sản xuất của nhà máy là vector x = (x1,x2,x3,x4,x5)

Hàm mục tiêu: f(x) = 300x1+ 250x2+500x3+150x4+320x5->max

Các ràng buộc:

2x1+ 5x2+6x3+8x4+4x5 <= 1200 3x1+ x2+5x3+6x4+x5 <= 800 7x1+ 5x2+4x3+4x4+2x5 <=2000 8x1+ 5x2+7x3+9x4+x5 <=1865

Tin học ứng dụng

B2: Tổ chức dữ liệu

Tin học ứng dụng

B3: giải bài toán bằng solver

Tin học ứng dụng

Solver – Answer report

Tin học ứng dụng

Solver – Answer report

❖Các điều kiện ràng buộc được thỏa mãn

Tin học ứng dụng

Phân tích kết quả

❖Phương án tối ưu (phương án cực biên) là

x=(200, 0 ,0,0,200) với f(x) max = 124 000

❖Hay: phương án sản xuất tối ưu của nhà máy là sản

xuất 200 đơn vị sản phẩm 1 và 200 đơn vị sản phẩm 5 khi đó lợi nhuận tối ưu đạt được là 124 000 đơn vị tiền tệ.

Tin học ứng dụng

Bài toán quy hoạch tuyến tính tổng quát

❖ Các ký hiệu

▪ Ẩn: x = (x1 , x2 ,…. xn ) Với các ràng buộc về ẩn xj>=0 hoặc

xj<=0

▪ Hàm mục tiêu f(x) =c1x1 + c2x2 +…. + cn xn -> max/min

▪ Các ràng buộc phương trình:

ai2x1 + ai2x2 +…. + ain xn –bi <= 0 hoặc >=0 hoặc =0

i= 1, 2,…m

Bài toán tìm x thỏa mãn ràng buộc và làm tối ưu hàm f

Tin học ứng dụng

Bài toán quy hoạch tuyến tính tổng quát

❖ Các bước thực hiện

▪ Phát biểu bài toán

▪ Giải

▪ Kết luận

❖ Ví dụ: Giải bài toán quy hoạch tuyến tính sau

f=2x1 - 3x2 + x3 -> min

2x1 - x2 + 3x3 >=4 -x1 +2x2 + x3 =1 4x1 +2x2 - x3 <=4 xj >=0 (j=1,3)

Tin học ứng dụng

Phát biểu và giải bài toán

❖Ở đây, vế phải được chuyển sang vế trái nhằm đơn

giản khai báo ràng buộc

Các ẩn

Hàm mục tiêu

Các ràng buộc

Tin học ứng dụng

Kết quả

❖Phương án tối ưu tìm được là

(0.951, 0.537, 0.878)

Fmin = 1.1707

Tin học ứng dụng

Bài toán vận tải

❖Có m kho hàng (điểm phát) chứa một loại hàng hoá,

lượng hàng ở kho i là ai

❖Có n nơi tiêu thụ (điểm thu) loại hàng này, nhu cầu

nơi j là bj.

❖Chi phí vận chuyển một đơn vị hàng từ điểm phát i

tới điểm thu j là cij.

❖Xác định các lượng hàng vận chuyển xij từ các

điểm phát i tới các điểm thu j sao cho tổng chi phí là nhỏ nhất và nhu cầu các điểm thu được thoả mãn.

Tin học ứng dụng

Bài toán vận tải- mô tả

Dự trữ

…

C11

C12

C1j

…

C1n

K2 C21 C22 .. C2j .. C2n a2

…… .. … .. .. .. .. ..

Ki Ci1 Ci2 .. Cij .. Cin ai

……… .. .. .. .. .. .. …

… Cmj .. Km Cm1 Cm2 Cmn am

❖ Hãy lập kế hoạch vận chuyển hàng từ các kho đến các điểm

tiêu thu sao cho tổng chi phí vận chuyển là nhỏ nhất

.. bj .. bn Nhu cầu tiêu thụ b1 b2

Tin học ứng dụng

Phân tích

❖Gọi xij là lượng hàng vận chuyển từ kho i đến điểm

tiêu thụ j : xij>=0; i=1,n; j=1,m

❖Tổng chi phí vận chuyển:

❖Lượng hàng vận chuyển khỏi kho i:

❖Lượng hàng vận chuyển đến điểm tiêu thụ j:

Tin học ứng dụng

Mô tả bài toán

❖Mô hình toán học:

▪ Hàm mục tiêu: f(x) =

min

▪ Các ràng buộc:

▪ Ta thấy ngay được điều kiện cần và đủ để bài toán vận tải có phương án tối ưu là tổng tất cả các lượng hàng tiêu thu bằng tổng tất cả các lượng hàng ở các kho

Tin học ứng dụng

Bài toán vận tải – Ví dụ

❖Hãy lập phương án vận chuyển xăng tối ưu từ 3 kho đến 4 trạm bán lẻ xăng của một công ty kinh doanh xăng dầu khu vực V với bảng chi phí vận chuyển như sau: