Tài liệu Giáo trình quy hoạch tuyến tính bài tập ứng dụng có lời giải

TRƯỜNG ĐẠI HỌC DUY TÂN ThS. N guyễn Đức Hiến Giáo trình Q U Y H O Ạ G H T U Y Ế N T ÍN H (BÀI TẬP ỨNG DỤNG CÓ LỜI GIẢI) NHÀ XUẤT BẢN THÔNG TIN VÀ TRUYỀN THÔNG Hà Nội - 2009 LỜI NÓI ĐẦU Toán Quy hoạch tuyên tính được ứng đụng rộng rãi trong kinh tế, kỹ thuật và nhiều lĩnh vực khác. Bài toán quy hoạch tuyến tính rất đa dạng như: lập kế hoạch sản xuất, kế hoạch vận chuyển hàng hóa, quy hoạch nông trang, quy hoạch sử dụng đất, rừng, đầu tư tài chính, điều chế vận tải... Mục tiêu của bài toán quy hoạch tuyến tính là tìm ra phương án tối ưu mà chúng ta đặt ra trong những điều kiện nhất định nhằm đạt lợi nhuận cao nhất, cni phí thấp nhất, sử dụng lao động họp lý nhất, sử dụng nguyên liệu và các nguồn tài nguyên khác như thế nào để đạt hiệu quả cao nhất... Quy hoạch tuyến tính là môn học bắt buộc đối với các trường đại học thuộc khối ngành khoa học tự nhiên, sư phạm, kinh tế ... và là môn thi tuyên sau đại học đối với khối ngành kinh tế. Nội dưng cuốn 'Giáo trình Quy hoạch tuyến tính" gồm 5 chương: C hương 1: Bài toán quy hoạch tuyến tính tống quát và các mô hình toán học Chương 2: Phương pháp đơn hình Chương 3: Quy hoạch đối ngẫu Chương 4: Bài toán vận tải Chương 5: Bài toán luồng cực đại trong mạng... Cuốn sách với nhũng nội dung căn bản nhất của quy hoạch tuyến tính như cấu trúc đa dạng của bài toán và cách chuyển đổi sang cấu trúc chính tắc, chuẩn tắc của bài toán quy hoạch tuyến tính, cấu trúc bài toán đối ngẫu của bài toán quy hoạch tuyến tính, các phương pháp giải bài toán quy hoạch tuyến tính... được trình bày trong sách cùng với các ví dụ minh họa, đặc biệt nhiều bài toán ứng dụng trong nhiều lĩnh vực khác nhau sẽ giúp ích nhiều cho các bạn sinh viên, nghiên cứu sinh cũng như các nhà quản lý, các nhà nghiên cứu kinh tế và khoa học. Cuốn sách được biên soạn với sự tham khảo, cập nhật tài liệu chuân quốc tế, nhiều tài liệu trong nước cùng với sự giúp đỡ của các đồng nghiệp, đặc biệt các thầy Nguyễn Quảng, Lê Dũng Mưu, Phạm Ngọc Anh, Nguyễn Vũ Tiến... Cuốn sách sẽ không tránh khỏi thiếu sót; tác giả rất mong nhận được ý kiến đóng góp của đồng nghiệp và bạn đọc. Mọi góp ý xin gửi về: Nguyễn Đức Hiền, Bộ môn Toán, Trường Đại học Duy Tân, TP. Đà Nang.. TÁC GIA BÀI TOÁN QUY HOẠCH TOÁN HỌC TỔNG QUÁT VÀ CAC MO HĨNH HOA TOẢN HOC 1.1. BAI TOAN QUY HOẠCH TOAN HỌC TO N G Q U Á T VÀ PHÂN LOẠI CÁC BÀI TOÁN 1.1.1. Bài toán tối ưu tổng quát Bài toán tối ưu tông quát là bài toán có dạng: Cực đại (cực tiếu) hóa hàm: f(x) —> max (min) ( 1 . 1) với các điều kiện: gi(x) (< >. =) bi, i=l,m ( 1.2 ) X e X c R" (1.3) trong đó cac hàm f(x), gi (x) ( i = \ j n ) là các hàm số; X là biến số có n thành phần. ( 1. 1) gọi là hàm mục tiêu (objective function). ( 1.2 ) gọi là điều kiện ràng buộc (contraint conditions). - Tập hợp: D = {x e X\gi(x) (<, >, =) b„ / = l,m } gọi là miền phương án (alternative region) hay miền chấp nhận (feasilhe region) - Mỗi điểm X = (X 1,X2,...,X„) e D được gọi là một phương án (alternative) hay lời giải chấp nhận được (feasible solution). - Phương án X* e D dùng cho hàm mục tiêu đạt cực đại (hay cực tiểu), cụ thế là: f(x*) > f(x) Vx e D (đối với bài toán max) f(x*) < f(x) Vx e D (đối với bài toán min) 6 Giáo trình Ouy hoạch tuyến t inh được gọi là phương án tối ưu (optimal alternative hoặc lời giải tối uuoptimal solution). Khi đó, giá trị f(x*) được gọi là giá trị tối ưu (o p tim a l value) của bài toán. Ví dụ I: Bài toán sau đây là bài toán tối ưu: (1) Xị > 0; X, < 0; X, tuỳ ý 6 x , + 4 X; + X, < 5 (2 ) X, + 2 x, = 5 XI + x , + 4 x , > 3 ( 3 ) f ( x ) = 2X| + 18 X2 +17 \ 3 —» m i n 1.1.2. Phân loại các bài toán Căn cứ vào tính chất của các hàm trong hàm mục tiêu và điều kiện ràng buộc mà người ta phân loại các bài toán khác nhau: Quy hoạch tuyến tính (program m ing): là bài toán tối ưu mà f(\i. gj(x) là các hàm tuyến tính ( V/ = 1, m ). Quy hoạch p h ỉ tuyến (nonlinear program m ing-NLP): nếu f(Xj hoặc có ít nhât một trong các hàm gi(x) là phi tuyến hoặc cà hai trường hợp đá cùng xảy ra. Quy hoạch tham số (parametric program m ing): nếu các hệ số trong biểu thức của các hàm mục tiêu và các điều kiện ràng buộc phụ thuc'c vào tham số. Quy hoạch động (dynamic programming)', nếu đổi tượng xét à cá: quá trình có nhiều giai đoạn nói chung hay các quá trình phát triển theo thời gian. Quy hoạch đa mục tiêu (multiobject program m ing): nếu trên cùng một miền ràng buộc ta xét nhiều hàm mục tiêu khác nhau. Quy hoạch rời rạc (discrete programming)', nếu miền D là rci rạc Nếu các biến chỉ nhận giá trị nguyên thì gọi là quy hoạch nguyên (intege' programming). Chươmỉ l: Bài loán quy hoạch toán học lông quái 7 Tất cả các loại bài toán trên gọi chung là bài toán Ouv hoạch toán học (hay íiọi là phạm trù học-Operation Research) (Bạn đọc xem thêm troníỉ [3], [5]. [6 ]). 1.2. GIẢI BÀI TOÁN QUY HOẠCH TUYÉN TÍNH ĐƠN GIẢN BẰNG PHƯƠNG PHÁP HÌNH HỌC 1.2.1. Xây dựng mô hình toán học cho một số vấn đề thực tế Các bước thực hiện để lập mô hình toán học cho vấn đề thực tế. Bước 1: Tìm kiếm thông tin gốc: Đây là quá trình thu thập các số liệu kinh tế - kỹ thuật. Bước này khá quan trọne vì tất cả các bước sau dựa vào các số liệu này đê tính toán. Nó quyết định tính chính xác của kết quả thu được. Mỗi bài toán kinh tế cụ thể đòi hỏi các thông tin gốc khác nhau. Bước 2: X ư ìỷ sô liệu: Bước này có thê chia thành hai giai đoạn. (Ị) Lập mô hình toán: Từ những số liệu và các yêu cầu về mặt kinh tế - kỹ thuật, ta chuyển thành mô hình toán học. Đòi hỏi ở bước này là phải thiết lập chính xác và đầy đù các điều kiện của bài toán. (2) Lựa chọn thuật toán thích hợp vù giải bài toán: Đây là quá trình tính toán trên mô hình toán dựa vào các thành tựu mà toán học đã đạt được. Kết quả ở bước này chính là lời giải cơ bản để đưa ra giải pháp tối ưu về mặt kinh tế. Vì vậy đây là bước rất quan trọng. B ước 3: Thông tin kết quá: Thực chất của bước này là sự diễn giải các thông tin về mặt toán học thành các thông tin về mặt kinh tế. Nghĩa là, dựa vào các kết quả tính toán đã có để những nhà làm chính sách đưa ra các quyết định kinh tế. 1.2.2. Môt số mô hình thưc tế • • 1.2.2.1. Bài toán lập k ế hoạch sản xuất: (Production planning problem) Bài toán tông quát: Trong một chu kì sản xuất một doanh nghiệp sử dụng m loại nhân tố sản xuất khác nhau để sản xuất ra n loại sản phẩm khác nhau E | . E ; ..... E n. Giáo trình Ouy hoạch tuyên tính 8 Tiêm năng vê các nhân tô sản xuât này của doanh nghiệp là có hạn cho bời véc-tơ b = (b|. ồ 2,.., bm) 1• Biết rằng để sản xuất ra một đơn vị sản phẩm Ej (với ị = 1.2.....n) cần chi phí hết a,j đơn vị nhân tố sán xuất thứ i (với i = 1.2 .....m). lọi nhuận khi bán sản phẩm được cho bởi véc-tơ c = (C|. c2,.., c n)'. Đật A - (ây)mn. Vậy doanh nghiệp cần phải lập kế hoạch sán không bị động về xuất bao nhiêu đê tiềm năng các nhân tố sản xuất và thu được lợinhuận lớn nhất. P hân tích: Gọi Xi, x 2..... xn lần lượt là số sản phẩm E|, E 2..... E„ (trong ke hoạch cần sản xuất). Theo đề bài ta có mô hình toán học như sau: Tìm X = (xI, X?,..., x„) thoá mãn: x,> 0 (7 = 1,« ) a n Xj + â|2 *2 + •••• + a i»*n - ,D1 < a 21x, + a 22 x 2 +.... + a 2(ixn < b 2 .a mixi + a n,2 x2 +•••• + a „„,xn ^ b ,„ f(x) = C| X\ + C2 X2 +... + c nx n- > max hay ta viết gọn dưới dạng ma trận: X>0 m ax Ví dụ 2: Một công ty phần mềm chuyên sản xuất 2 loại phần mềm A và B. Với đội ngũ gồm: 6 thạc sỳ và 8 kỹ sư tin học. ( 'ha/nạ 1: Bùi toán quy hoạch loàn học tòng quát 9 Biêt rănu: Đê san xuàt hoàn thành 1 phân mêm A cân 2 thạc sỹ và 1 k sư. đè san xuât hoàn thành 1 phân mêm [ỉ cân 1 thạc SV và 3 kỳ sư. Qua tiếp thị trên thị trườnc được biết nhu cầu cực đại cua ca 2 phần mền. Giá bán ra cho một loại phần mềm A là: 2000USD và cho một loại phái mêm B là: 3000USD. Hãy lập kể hoạch sán xuất cho mỗi tháng đê thoa mãn yêu cầu thị trường, không bị động về đội ngũ. doanh thu đem về cho công tv lớr nhất. Giải: Gọi X|, X: lần lượt là số lượng phần mềm A và B cần sản xuất. Theo đề bài ta có mô hình toán học: Tìm x = ( x p x 2): X, > 0 , x 2 > 0 2x, + X 2 < 6 .V, + 3x: < 8 f ( x ) = 2.V, + 3x: -> max ( 1 0 0 0 USD) 1.22.2. B ài toán vận tải (Transportation problem) Bài toán: Ta cần vận chuyển một loại mặt hàng nào dó (chẳng hạn như: máy tínl . linh kiện điện tử. gạo, gồ, xi măng, xăng dầu, ...) gồm có m trạm phá hàng Ả ị ,A 2.....Ả m vói lưựng hàng yêu cảu phái đi tương ứng là ữ ,. 7: .....am đơn vị hàng, n trạm thu hàng B ị. B2 Bn với lượng hàng y êi cầu chuyến đến tương ứng là bị ,b 2,...,bn đơn vị hàng và ma trận cưcc phí vận chuyền (chi phí vận chuyển một đơn vị hàng). c Cm\ Cml c 11111 10 Giáo trình Oiiy hoạch tuyến tín h Ớ đây C'(; ụ = \,m : j = 1,«) là cước phí vận chuyển cho mồi đơ n vị hàng ho á được chuvển từ trạm phát A đến trạm thu B . Bài toán đặt ra với điều kiện: HI n (ỉ .4) (1.4) gọi là điều kiện căn bằng th u p h á t tức là: tổng lượng h àn g phát đáp ứng đầy đủ cho tống lượng hàng thu (cung hằng Cầu). Hãy lập kê hoạch vận chuyên hàng sao cho: - Các trạm phát (cung) hết lượng hàng hiện có. - Các trạm thu (cần) nhận đủ lượng hàng yêu cầu. - Tổng chi phí vận chuyển nhỏ nhất. Plìăn tích: Gọi x n (/' = l,m ; j = \.n ) là lượng hàng vận chuyển ưr A, đến B r Thây ràng x n > 0 , V/ = \ . m ; V/ = l ,/7 trong đó X > 0 khi A, phát hàng cho B Ị ; còn x v = 0 khi A1 không phát hàng cho B . Khi đó mô hình của bài toán nói trên là: Tìm một ma trận phàn phối và vận chuyển hàng: x \n X -)Ị X-)2 x 2n .1 viêtgọn = ( x iJ)mn thỏa mãn các điều kiện sau: (1) Xy > 0 , v / = l , w; v / = l , « y ' j x tị = a l (tổng lượng hàng phát đi từ trạm A,), / = 1, m 7= 1 (1.5 ^ x ụ = bj (tổng lượng hàng chuyển đến trạm B .). / = 1, n m n O ) A X ) = ỵ ĩ , v , —> min (tổng chi phí v c bé nhất) /= l 7=1 Chcơrìg 1: Bài loàn quy hoạch toán học tônạ quái Vi dụ 3: Ta cân vận chuyên máy tính từ 2 công ty (trạm phút)'. C |, Ci_ đên 3 nơ tiêu thụ (trạm thu) T |. ị 2 và T 3. s ố lượng máy tính ở mồi công ty cần chuyên, nhu câu máy tính tại các nơi tiêu thự cũnQ như cước phí vận ch.ivển cho mỗi máy tính được chuyên từ công ty C| đến nơi tiêu thụ Tị V/ = 1.2. V/ = 1.3). được cho trong bảng sau: Hãy lập kế hoạch vận chuyển máy tính như thế nào để: - Các công ty phải phân phối hết số máy tính hiện có. - Các nơi tiêu thụ nhận đủ số máy theo nhu cầu. - Tổng cước phí vận chuyển là thấp nhất. Giải: Gọi Xjj là số máy tính sẽ vận chuyển từ cảng (Cj) đến nơi tiêu thụ (T ,)(/ = Ũ ý=ũ) Với điều kiện: X j j > 0 (i = 1,2, j = 1,3). Số máy tính vận chuyển từ Ci đến 3 nơi tiêu thụ là: X ì \ + X i2 + SỐ máy tính vận chuyển từ C 2 đến 3 nơi tiêu thụ là: X 2I + x 22 + x 23 SỐ máy tính vận chuyển đến tiêu thụ Ti từ 2 cảng là: x n + x 2| Tổng sổ máy tính vận chuyển đến tiêu thụ T 2 từ 2 cảng là: x 12+ x 22 12 Giáo trình Quv hoạch luyen tính Tông sô máv tính vận chuyên đên tiêu thụ T;, từ 2 cang là: *.3+*23 Tồng cước phí phải chi trả là: (tổng này càng nhỏ cànạ tốt), 5 x ,, + 7 x |: + 2 x |3 + 4 x 21 + 3 x 22 + 6 x ZĨ Theo đề bài ta có mô hình toán học của bài toán là: Tìm X = (xụ) với (/' = 1. . m : / X >0 = 1. . r i ) thoả mãn: (/ = 1 2 . 7 = Ũ ) x 2ì +X22+X2Ĩ = 4Ũ = 15 20 x ]2+ x 22 = a - , + x 23 = 25 f ( x ) = 5 x u + 7 x |2 + 2 x |? + 4 x 2| + 3 x 22 + 6 x 23 —> min ịl Ma trận hệ số A = 1 1 0 0 0' ' 20 ' 0 0 0 1 1 1 40 1 0 0 1 0 0 ;B = 15 0 1 0 0 1 0 20 v0 0 1 0 0 b v25y / X XM V X 2I \ X I2 xu x 22 x 23/ ở đây thay vì viết X = (x 11; X12; X 13; X21; X22; X23) ta viết thành ma trận như trên đe ứng với một trạm phát và mồi cột ứng với một trạm thu cho dề hình dung. 1.2.2.3. B à i toán n g ư ờ i du licit (Travelling salesm an problem ) Một người du lịch được phép mang theo một cái túi nặng khóng quá bkg. Anh ta dự định đem theo n loại đồ vật. Mỗi một đồ vật loại / có ('hum ií' 1: Bài toán quy hoạch loàn học IÔIÌỊỊ quái 13 khỏi lượtm a,ku và có uiá trị la C|. Nmrời du lịch muôn săp \'ào túi các đô vật mang theo sao cho: - Khôi lưạnu tôim cộng khônu được vượt quá khôi lượrm cho phép bke. - Nhưnẹ có tông giá trị lớn nhất. Ký hiệu X| ( / = \,n) là số lượng dô vật loại ị sẽ sấp vào túi du lịch. Mỏ hình cua bài toán là: Tìm một ma trận X = ( x r x 2.....x n ) thỏa mãn các điều kiện sau: (1) X J > 0 . V/ = 1. n ; Xị nguyên, ị = \ . n n n (3) f ( X ) = Y JCIXI -> max Bài toán người đi du lịch (còn được gọi là bài toán cái túi) loại bài toán này được gọi là quy hoạch nguyên. Nhận định chung: Qua các ví dụ được trình bày ở phần trên, ta thấy rằng trong nhiều lĩnh vực khác nhau có những yêu cầu khác nhau trong việc đề ra các quyết định định lượng nhàm tối ưu hóa sán xuất. Nhưng những yêu cầu này có thê được diễn giải thành mô hình toán và được tông quát hóa như sau: (1) Điều kiện tối ưu hóa: Đòi hỏi thởa mãn yêu cầu về mặt kinh tế bao gồm hai trường hợp cực đại hóa hoặc cực tiểu hóa. (2) Điều kiện ràng buộc: Bao gồm một hệ gồm các phương trình hoậc bất phương trình bậc nhất. Hệ thống các ràng buộc này xuất phát từ những đòi hỏi cần được thỏa mãn về mặt kỹ thuật. (3) Điều kiện về dấu: Xuất phát từ yêu cầu thực tiễn là các biến quyết định đòi hói không âm. Giáo trình Quy hoạch luyến lính 14 1.2.3. Phương pháp hình học 1.2.3.1 Các cách biểu diễn của bài toán quy hoạch tuyến tinh n h ư sau. Tìm X = (xp x , .....x n) e R" thỏa mãn: (1) X > 0 (j =ỉ, n) a u Xị + a n x 2 + . . . . + a Ulx n ( < > = ) / > ! a 2íx ] + a 22 X, + .... + a 2nx n ( < > = ) / > , (2) l «„,1*1 + a „,2 x2 +.... + amnxn (<>=)/>„, (3) f(x)= XI c I + X 2C2 +.. + x ncn —r min (max). Hay viết gọn: T ìm x = (x 1,x 2,...,xn) với x : e R , V / = 1,0 thoa mãn (1) X ỉ > 0; \/j= ỉ,n (2) X " ' / * / ( - ’ = hoặc <)b,; V/ = 1, m ./=! n (3) / ( * ) = y^ c Jx J -> min (max) ./=1 D ạng ma trận của bùi toán: Gọi A = (ayVn, c = (c I, C2,...,Cn)‘, X = (X|, .........?:n)' b = (bi, b 2,...,bm) r Khi đó: Bài toán quan hệ tuyến tính tổng quan có thể viết: (1) -V> 0 (2) Ax (>, = hoặc <)b (3) f(x) = CTX —> min (max) Trong đó V(/ = l,/w; j = \,rí) các a , ố, và các c còn X (j = 1,«) là các ân số. đêu đã liêt 15 ( 'hianiiỉ I : Hùi Itìán quy hoạch toán học tông quái 1.2.ĩ . 2. M ột sô kêt (¡lid trong đại sô và giải tích Tập D được gọi là tập lồi nếu Vx. y e M ta có Ằ.X + ( 1- À.)y €E D. Có nghĩa raim: với 2 điếm bất kì thuộc D thì tất ca các diêm năm trên đoạn thăng nối hai điểm dỏ cũng thuộc D và ngược lại. Ví dụ: Miền phương án của bài toán quy hoạch tuyến tính D- j.Y 6 R" \ Ax < (hay >, hay =)h. X > ()| là tập lồi. Thật vậy. lieu ta lấy 2 điếm bất kì X. y 6 D nghĩa là: X > 0 ( ễ R"). y > 0 ( e R n) Ax < b. A y < b Ta chứng minh: z = Ằx + ( 1- x.)y với mọi 0 < X < 1 cũng thuộc D hay z > 0, Az > 0 Ta có: z > 0 (hiển nhicn) Az = A [X.x+(l-X)y] = XAx + (l-X )A y < X b + (l - l)b = b => z e D =ì> D là tập lồi. Vi dụ: Siêu phẳng (hyperplane): H (a, d ):- Ị x e R " \ a ' x - d ; a t R", d fc R) cũng làtập lồi. Cụ thể: n = 2: H (a,d) ={(xi,x2) \ ai X, + a 2 x2= dj đây chính là đường thăng. n = 3: H (a,d) ={(xi,x 2,x3) \ ai Xi + a 2 x 2 + a 3 X3= dj đây chính là mặt phẳng. Chú ỷ: Mỗi siêu phẳng H(a,d) chia không gian R" ra làm hai phần, ta gọi tương ứng là nửa không gian đúng dương và nửa không gian đủng âm lần lượt là: Giáo Irình Quy hoạch tuyến tín h 16 H+ (a.d) = {x e R n \ a' X > d; a e R n, d e R ) H. (a.d) = {x g R" \ a 1 X < d; a eR". d eR Ị là các tập lồi. (Các đường thẳng, hình tròn, tam giác, tứ giác lồi. hình tứ diện,. . là các tập lồi). H ệ quả: Giao hữu hạn các nua không gian đóng của R" là tập lồi. Khi đó ta gọi là một tập lồi đa diện (polyhedron) hay khối da ciện (chứng minh xem [3]). Do đó miền phương án D của bài toán QHTT là một tập hợp lồ: có đỉnh (vertex) tạo bởi giao của các nửa siêu phăng: Ỵ j ai x Ị(<,>)bi i = ỉ,m 7= 1 Các đỉnh của miền phương án D còn được gọi là phương án cực biên (điểm cực biên_ extreme point) của bài toán QHTT. (xem [3]) Định lý 1: Bùi toán Q H huy bài toán Q H TT nếu thoa mãn 2 điều kiện sau đáy. - Điều kiện 1: Miền phương án D ± ộ - Điều kiện 2: Hàm mục tiêu f ( x ) (với f là hàm liên tục) bị chận (chặn dưới đối với bài toán min, chặn trẽn đối với bài toán max) trên D thì tồn tại phư ơ ng ủn tối ưu. Định lý 2: Bài toán QHTT, nếu có phương án tối ưu, thì có phư ơ ng án cực biên tối ưu. Định lý 3: Mỗi hệ ràng buộc tuyến tính chi cỏ hữu hạn đinh (ãiêm cực biên cỏn gọi là nghiệm cơ sờ chấp nhận) ([3]) ( 'hu rniỊ 1: Bùi toán quy hoạch toán học lôm ' quát 17 1.2.ỉ . 3. Phương pháp hình học Xét bài toán quy hoạch tuyến tính dưới dạng chuán với hai biến số: f\x) = Cị.v, + C'r v: —> min(max) V/ = 1,2 Từ ý imhĩa hình học ta biết ràng mỗi bất phương trình: + a l2x 2 < h xác định một nửa mặt phăne. Như vậy: miền D (miền chấp nhận) được xác định như là giao của các nủa mặt phang và sẽ là một đa giác lồi trên mặt phẳng. Phương trình c 1X1 + C2X2 = oc • Khi a thay đôi sẽ xác định trên mặt phăng các đường song song với nhau và ta sẽ gọi là các đường mức (level curxe) với giá trị mức (X . Mỗi điềm X* =(X|*. X2*) e D sẽ nằm trên đường mức với giá trị mức a* = Ci Xi* + C2 X2*. Bài toán đặt ra có thế phát biểu theo ngôn ngữ hình học như sau: Trong số các đường mức cắt D. hãy tìm đường mức với giá trị mức nhỏ nhất (lớn nhất). Neu dịch chuyến song song các đường mức theo hưóng véc-tơ pháp tuyến của chúng n = (Cị,c2) thì giá trị mức sẽ tăng (hoặc giảm nếu dịch chuyển theo hướng ngược lại). Do đó để giải bài toán ta tiến hành như sau: Bước 1: Vẽ miên châp nhận được D. Bước 2: Băt đâu từ một đường mức căt D ta dịch chuyên song song các đường mức theo hướng (hay ngược hướng) véc-tơ pháp tuyến của chúng n - (c,, c2) cho đến khi nào việc dịch chuyến tiếp theo làm cho đường mức không cắt D nữa thì dừng. Điêm căt D (có thê nhiêu điêm) năm trên đường mức cuôi cùng này sẽ là lời giải tối ưu. Còn giá trị của hàm mục tiêu (tức là giá trị mức) tại đó là giá trị tôi ưu cân tìm của bài toán. ----- ----- - ........ ......... i ẼAI HOC QUOC GIA HA NOI ỊI [3UNG.Ĩ ẨM rH Ồ N G .TIN ĨHƯ VIỆN r V • Ù C / £.H 3C Giáo trình Q uy hoạch tuyến tính 18 Nhận xét: Do trong quá trình vẽ miền D không thể tránh khỏi sai số (mà phần chính là khi vẽ, xác định tọa độ, xác định vuông g ó c , . . . ) nên việc tin cậy để xác định tọa độ tối ưu không cao. Nên không mất tính chính xác của bài toán, ta có thể giải bài toán quy hoạch tuyến tính dạng hai biến hay 3 biến được tóm tắt theo các bước sau: B ư ớ c 1: Vẽ miền chấp nhận được D (tức là ta xác định miền giao nhau của các nứa mặt phẳng hay nửa không gian do điều kiện ràng buộc). B ư ớ c 2: Nếu D ;É 0 v à bị chặn (chặn dưới đối với bài toán ta xét là dạng min, chặn trên đối với bài toán ta xét là dạng max) thì khi đó bài toán có phương án tối ưu. Ta xác định toạ độ các đỉnh (sang bước 3). Ngược lại, kết luận bài toán vô nghiệm. Dừng B ư ớc 3: Tính giá trị của f tại các đinh đó rồi kết luận (tức là tìm giá trị lớn nhất hay nhó nhất của f ) . Vỉ dụ 6: Xét lại bài toán. Tìm X = (Xi, X2) thỏa mãn: Â'| > 0 , X-Ị > 0 9x, + 3 x 2 < 2 7 (v dl) 2x, + x 2 < 7 2Xị + 2 x 2 < 12 / (x) = 5.X, + 3x 2 -> max Giải: * Vẽ miền phư ơ ng án D: Gọi: d i: là đường thẳng 9x, + 3*2 = 27 d 2: là đường thẳng 2 x t + x 2 = 7 (Ì3: là đường thẳng 2 x ] + 2 x 2 = 12 Chưrng 1: Bài toán quy hoạch toán học tỏng q u á i... Khi đó từ ( v d l 19 ) ta được miền phương án D của bài toán là hình đa giácOABCE. Đó là một đa giác lồi kín, nên bài toán có phương án tối Thấy rằng điểm: 9x. A = dị n ( O X ị) : 9*! B = d]n d2: c = d2n í/,: + 3 x = 2 7 . ' ; x2 = 0 . => 4 0 , 3 ) ; / ( / ( ) = 9 4- 3 x 2 = 2 7 5(2,3); f(B ) = 19 2xị + x 2 = 7 2-t, + x2 = 7 => 4 , 5 ) ; / ( £ ) = 20 2 x, + 2 x 2 = 12 2 x, + 2 x 2 = 12 £ = <Ị, n ( ỡ x 2) F ( 0 ,6 ); / ( £ ) = 18 X, = 0 0 ( 0 ,0 ) ; / ( ơ ) = 0 Từ đó max f = max {9; 19; 20; 18; 0} = 20 = f(B). Vậy x° = (1, 5) là nghiệm tối ưu của bài toán. Giáo trình Ouy hoạch tuyến tinh 20 Vỉ dụ 3: Tìm X = (X|, X2, X3) thỏa mãn: (1) X, > 0 , .V, > 0 , Xy > 0 (2 ) + x 2 + X, < 4 X, < 2 (3) f (x) = X\ + 2 x 2 + 3x, - 20 —» max Giải: * Vẽ miền p h ư ơ ng án D: Từ (1) và (2) ta thấv miền phương án D là hình chóp cụt A B C O B ’C \ Đó là một đa diện lồi kín, nên bài toán đã cho có phương án tối un. * Tìm phư ơ ng án tối ưu x°: Thấy ngay rằng các điểm: A (2, 0, 0) có f(A) = - 18 o ( 0 , 0 , 0 ) có f( 0 ) = - 20 ( 'hương ỉ: Bùi toán quy hoạch toán học tông quái 21 B' (0, 4. 0) có f(B') = -12 C" ( 0 . 0 . 4 ) c ó f ( C ') = - 8 Ký hiệu (P) là mặt phăng X| + X2 + X.1 = 4; (Q) là mặt phăng Xi = 2; (K) là mặt phăng tọa độ ( x i O x 2) và (J) là mặt phắng tọa độ (xịOx-ị) thì điểm: X, + x 2 + X, - 4 B(2. 2, 0) với f(B) = -14 B = ( P ) n ( Q ) n ( K ) 0 , x 2 > 0 Xj + 5x 2 > 10 3 x ] + 2 x 2 > 12 ( 2 ) 2x , + 4 x 2 > 16 2 x ị + 2 x 2 > 10 X, >1 (3) f \ x ) = 2x] + 3x 2 + 7 -> min Giai: * Vẽ miền phư ơng án D: Gọi các đường thẳng: