ệ
ế
ứ
ấ
ượ ề
ươ
ươ
ạ Khái ni m: Bài toán quy ho ch tuy n tính là bài toán ụ ề ố ư i u mà hàm m c tiêu v n đ ệ ủ ộ ề c quan tâm và các ràng bu c đi u ki n c a bài toán ấ ặ ng trình ng trình ho c b t ph
ế
nghiên c u các bài toán t đ đ u là hàm và các ph tuy n tính.
Ộ Ố ƯƠ Ạ Ế M T S PH NG TRÌNH QUY HO CH TUY N TÍNH
Ộ Ố ƯƠ Ạ Ế M T S PH NG TRÌNH QUY HO CH TUY N TÍNH
ạ ộ ứ c nghiên c u và ng d ng m t bài toán quy ho ch
ướ Các b ế
ấ ứ ư ề ầ ụ tuy n tính đi n hình là nh sau : ả ậ ữ ệ ế i quy t, thu th p d li u.
ậ
ự
ể ả ệ ậ ằ i bài toán đã mô hình i cho vi c l p trình cho máy tính.
ế ầ ỉ
ự ế ụ ể ị a Xác đ nh v n đ c n gi b L p mô hình toán h c. c Xây d ng các thu t toán đ gi ữ ử ả i các bài toán th c t ọ ậ ậ ợ hoá b ng ngôn ng thu n l ề d Tính toán th và đi u ch nh mô hình n u c n. e Áp d ng gi .
1. F(X) =2x1 – x2 + 2x3 Min x1 + 4x3 = 7 x2 + x3 = 10 x1,x2,x3 ≥ 0 2. F(X) =2x1 –x2 3x3 Max x1 + x2 x3 = 2 10x2 + 5x3 = 3 3x2 + 2x3 = 4 x1,x2,x3 ≥ 0
Ộ Ố ƯƠ Ạ Ế M T S PH NG TRÌNH QUY HO CH TUY N TÍNH
2.1 BÀI TOÁN PHƯƠNG ÁN SX
̣ ̣ ̣
́
́
́
̣ ̉ ̣
́
̀ ượ
́
̀ ơ
̉ ̣
́
́ ̀ ư
̣ ̉
Công ty may măc Hoa ng Dao hiên đang lâp ̀ kê hoach san xuâ t 3 măc ha ng: A o Jeket, ́ Áo Chemis, A o Bludong. Đ c biê t chi phi ̀ ̉ ư công san xuâ t cua t ng măt ha ng qua 3 gi ̀ công đoan Că t, May, hoa n chinh nh sau:
Chi tiêu Chemis Bludong Jaket
̀ ơ ̣ ̣ Gi ́ công bô phân că t 0.2 0.4 0.3
̀ơ ̣ ̣ Gi công bô phân may 0.3 0.5 0.4
̀ ̀ ơ ̣ ̣ Gi công bô phân hoa n
chinh̉ 0.1 0.2 0.1
́ ơ Đ n gia (USD/1SP) 2.3 3.6 2.8
́
́
ự
̉ ̣ ̣
́
ơ
̣ ̣
Năng l c tô i đa cua ca c bô phân nh sau: ư Bô phân că t 1250 gi
̀
công
̣ ̣
̀
̣ ̣ ̉
́
́
́
̉ ̉
̀ ơ công Bô phân may 1650 gi ̀ ơ công Bô phân hoa n chinh 540 gi ươ ng san Tô i thiêu trong 1 tha ng sô l
́
̃
̉ ̉ ̣ ̉ ̉
phâm san xuâ t mô i loai la 200 san phâm.
̃
́
́
̃
̣ ̉
Yêu câ u:̀
́
̣ ̉ ̣ ̉ ̣ ̉ ̉
̀
́
̉ ̉ ̣
ề ́
̀
ượ
̉ ̣ ̉
̉ ̉
̀ ́ Ha y ti nh kê hoach san xuâ t mô i loai bao nhiêu đê đat tông gia tri san phâm ̀ ̃ ́ ơ l n nhâ t va vâ n đam bao đi u kiên vê ́ ự năng l c san xuâ t va quy đinh sô l ng san ́ phâm tô i thiêu
Gọi x1, x2, x3 lần lượt là số lượng C, B, J ta có
ắ ổ T ng GCBP c t = 0.2x1 + 0.4x2 + 0.3x3 <=1250
ổ T ng GCBP may = 0.3x1 + 0.5x2+ 0.4x3 <=1650
ổ T ng GCBP HC = 0.1x1 = 0.2x2 + 0.1x3 <=540
2.3x1+ 3.6x2+ 2.8x3 Tổng GTSP ===> Max
X1>=
X2>= 200
200
X3>= 200
2.2 SỬ DỤNG SOVER ĐỂ GiẢI BÀI TOÁN
ả
ậ
.
2.2.1 L p mô hình bài toán trên b ng tính Excel
ứ
ể ổ
Chúng ta có th t
ề ủ
ố
ề
ể ch c nhi u ki u mô hình ế ố vùng bàn toán, mô hình nên có đ 3 y u t : thông s , vùng tính toán, và vùng ràng ị bu cộ . Sau đây là mô hình đ ngh :
VÙNG THÔNG SỐ
VÙNG TÍNH TOÁN
Ệ Ề VÙNG ĐI U KI N
2.2 SỬ DỤNG SOVER ĐỂ GiẢI BÀI TOÁN
ử ụ
ị ố ư
ể
ị
2.2.2 S d ng Solver đ xác đ nh giá tr t
i u.
ộ
ấ
ẽ
ệ
ộ
ầ ượ
t
ạ Solver Parameters ta l n l
ệ
ự
ổ
ị
ệ
ề
ậ
ạ Vào Menu Tool\Solver s xu t hi n h p tho i Solver Parameters Trong h p tho i th c hi n các thao tác sau: ậ + Set target cell : ta nh p vào ô: T ng giá tr SP ($B$24) + Equal to : ta ch n ọ Max Click vào ô Guess : ta nh p các đi u ki n sau:
ể ọ
ệ
ị ư
ậ
ạ
+ Sau đó di chuy n qua khung Subject to the ấ ẽ Constraints và ch n Add . Khi đó s xu t hi n ộ h p tho i ta nh p các giá tr nh hình sau:
ề
ệ
ể + Click vào nút Add đ thêm vào đi u ki n.
ự
ạ
ng t
cho các vùng còn l
i ta
ượ
+ Thao tác t đ
ươ c hình sau:
ể ả
i bài toán.
Sau đó ta Click vào nút Solver đ gi
