Bài toán quy hoạch tuyến tính có lời giải

Tại trường bay Tân đánh Nhất có nhu cầu vận đưa 1200 quý khách và 120 tấnhàng bằng máy bay.

Bạn đang xem: Bài toán quy hoạch tuyến tính có lời giải

Trả sử có 2 một số loại máy bay rất có thể sử dụng với kĩ năng vận chuyểncủa mỗi nhiều loại như sau:Máy bay loại A: 01 máy bay có thể chở 150 quý khách và 20t hàng với chi phítương ứng 240 triệu đồng.



CHƯƠNG I BÀI TOÁN QUY HOẠCH TUYẾN TÍNH1.1/ MỘT SỐ VÍ DỤ DẪN ĐẾN BÀI TOÁN QUY HOẠCH TUYẾN TÍNH: 1.1.1. Việc vận chuyển: Tại sân bay Tân sơn Nhất mong muốn vận đưa 1200 quý khách và 120 t ấnhàng sử dụng máy bay. Mang sử có 2 một số loại máy bay có thể sử dụng với tài năng vận chuyểncủa mỗi loại như sau: Máy cất cánh loại A: 01 vật dụng bay có thể chở 150 quý khách và 20t hàng với đưa ra phítương ứng 240 triệu đồng. Máy bay loại B: 01 máy cất cánh chở có thể chở 180 quý khách và 16 tấn hàng với chiphí tương ứng là 220 triệu đồng. Hãy lập mô hình tìm phương án thực hiện số máy cất cánh mỗi loại làm sao để cho phải thỏamãn yêu mong vận gửi với tổng túi tiền ít nhất.Lập tế bào hình: gọi x1 là số lượng máy cất cánh loại A hotline x2 là số lượng máy bay loại B Tổng chi tiêu (triệu đồng): Z = 240 x1 + 220x2 Đảm bảo về hành khách: 150 x1 + 180x2 = 1200 Đảm bảo về sản phẩm hóa: trăng tròn x1 + 16 x2 = 120 Đảm bảo thực tế: x1,x2 ≥ 0Giải bài bác toán: Z = 240 x1 + 220x2 → min (*) 150 x1 + 180 x2 = 1200   trăng tròn x1 + 16 x2 = 120  x ≥ 0; j = 1, 2 () j Giải hệ phương trình trên  x1 = 2, x2 = 5 nỗ lực x1 với x2 vào (* ) → Z = 1580 1.1.2/ câu hỏi khẩu phần thức ăn : Để nuôi một một số loại gia súc người ta áp dụng 3 loại thức ăn uống A, B, C. Tỷ l ệ % theokhối lượng các chất bổ dưỡng P1, P2 có trong các loại thức nạp năng lượng như sau : Thức ăn Chất dinh dưỡng P1 P2 A trăng tròn 10 B 10 10 C 10 20Yêu ước trong thực đơn thức ăn uống của một số loại gia súc này: - Chất bồi bổ P1 đề nghị có tối thiểu là 70g và các nhất là 80g - Chất dinh dưỡng P2 có ít nhất là 90g - giá 1kg thức nạp năng lượng A,B,C tương ứng là 2.000đ, 1.000đ, 2.000đ Yêu cầu : Hãy lập quy mô bài toán xác minh khố i lượng thức ăn cần cài saocho tổng túi tiền ít nhất.Lập mô hình bài toán : gọi x1, x2, x3 tương xứng là số g thức ăn uống A, B, C buộc phải mua - Tổng giá cả Z = 2x1 + x2 + 2x3 - Hàm lượng các chất bồi bổ P1: 0,2x1 + 0,1x2 + 0,1x3 ở trong < 70,80> (g) P2: 0,1 x1 + 0,1x2 + 0,2 x3 ≥ 90 (g) x j ≥ 0 ( j = 1, 2,3)Bài toán: tìm kiếm xj (j= 1,2,3) làm thế nào cho Z = 2x1+ x2 + 2x3 → min 2 x1 + x 2 + 2 x3 ≥ 700 2 x + x + x ≤ 800 1 2 3  x1 + x 2 2 x3 ≥ 900 x1 , x 2 , x3 ≥ 0 1.1.3/ vấn đề thời gian thi công ngắn nhất: Để đảm bảo hoàn thành kế hoạch, đơn vị sửa chữa thay thế và bảo trì đường nhựa Acần vội vàng rút xong 50km sơn vạch mặt đường, trong số ấy số km mặt đường được đánh kẻvạch của đường cung cấp I không bé dại hơn 20% tổng chiều nhiều năm được tô kẻ vạch củađường cung cấp II và cấp III. Đơn vị A chỉ có 1 dây chuyền ( người, máy) để triển khai việc này. Trong lúc đ ể thờigian chấm dứt 1km đường cấp I, II, III tương ứng là 12 ngày, 8 ngày và 6 ngày. Định mức chi phí sơn cho 1km đường cấp I, II, III tương xứng là 30, trăng tròn và 15 triệuđồng, trong lúc kinh chi phí dành cho công việc này trong thời gian tới chỉ còn 120 (triệuđồng). Hãy lập tế bào hình khẳng định chiều nhiều năm sơn kẻ vạch cho mỗi cấp đường làm sao cho tổngthời gian triển khai là ngắn nhất, đồng thời bảo đảm an toàn về kinh phí đầu tư mua sơn.Lập mô hình: hotline x1, x2, x3 là chiều nhiều năm (km) dự định tiến hành trong tương xứng cấp con đường loạiI, II, III khi đó. Phương châm thời gian: Z = Yêu cầu khối lượng: Yêu mong chủng loại: yêu thương cầu kinh phí Điều khiếu nại tất yếu: x1, x2, x3 ≥ 0 bài xích toán:1.2/ ĐỊNH NGHĨA VÀ CÁC DẠNG BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1.2.1/ Định nghĩa: việc quy hoạch tuyến tính dạng tổng quát: kiếm tìm (x1, x2, …, xn) làm thế nào để cho n ∑c x j → min (max) (1) f (x) = c1x1+ c2x2 + cnxn = j j =1 Với đk n ≤   ∑   aij x j  bi (i = 2,.., m)(2) = 1, j =1  ≥    ≥  0    0  j =(1, 2,..., n)(3) ≤ x j   Tùyý   + những bi điện thoại tư vấn là các hệ số từ bỏ do+ các cj điện thoại tư vấn là thông số hàm kim chỉ nam ( hệ số)+ aij call là hệ số những ràng buộc chung+ f(x) hotline là hàm mục tiêu+ Hệ (*) gọi là hệ buộc ràng (2) hotline là ràng buộc thông thường (có m ràng buộc) (3) hotline là ràng buộc trở thành (có n ràng buộc) Vector x = (x1, x2, … xn) hotline là phương pháp (P.A) nếu x thỏa (*) tập hợp toàn bộ cácphương án điện thoại tư vấn là miền ràng buộc kí hiệu là D - Một phương án tạo nên hàm phương châm đạt rất tiểu ( ứng với vấn đề tìm min của f (min f) hoặc cực lớn (max f) điện thoại tư vấn là phương án tối ưu được ký kết hiệu là xoptNghĩa là: BT min: ∀ x ∈ D : f (x) ≥ f (xopt) BT max: ∀ x ∈ D : f (x) ≤ f (xopt)Giải việc quy hoạch đường tính là tìm các bộ phận tối ưu (nếu có) + Hai bài toán quy hoạch tuyến tính gọi là tương đương nhau ví như chúng bao gồm chungphần tử buổi tối ưu. Mệnh đề : quan hệ tình dục giữa max f với min f  f ( x ) ⇒ max  g ( x ) = − f ( x ) ⇒ min  x ∈ D ⇔  x ∈ D  1.2.2/ màn biểu diễn bài toán quy hoạch con đường tính dưới dạng ma trận:Gọi  a11 a12 ... A1n  a A =  21   ...    am1 amn  là ma trận cung cấp m*n những hệ số những ràng buộc chung x1 , CT = (c1, c2, …,cn)X= … xn b1B= …. BmLúc đó vấn đề quy hoạch tuyến đường tính được phát biểuTìm x = ( x1, x2, …, xn) làm sao cho f(x) = CT x → min (max)thỏa mãn: A.X  B ≥ X≥0 ; trong  ≤ =1.2.3/ những dạng của việc quy hoạch tuyến tính và những quy tắc biến đổi đổi.1.2.3.1: Dạng thiết yếu tắc n f ( x) = ∑ c j x j → min ( max ) j =1 n  ∑ aij x j = bi (i = 1, 2..., m)  j =1 x ≥ 0 ( j = 1, 2,..., n ) j Ta dấn xét rằng, ngẫu nhiên bài toán quy hoạch tuyến đường tính như thế nào cũng rất có thể đưa vềdạng thiết yếu tắc nhờ những quy tắc biến hóa sau: • nếu như ràng buộc bao gồm dạng : n ∑ x j ≥bi a ij j=1thì ta mang về dạng tương đương : n ∑a x j − x n +1 = bi ij j =1với xn+1 ≥ 0 là ẩn phụ) • ví như ràng buộc bao gồm dạng : n ∑ xj ≤ i a b ij j=1thì ta mang đến dạng tương tự n ∑a x j + xn +1 = bi ij j =1với xn+1 ≥ 0 là ẩn phụ)Chú ý: - hệ số của ẩn phụ vào hàm mục tiêu f(x) là 0. - Nếu đổi thay xj ≤ 0 thì ta thay bởi xj’ : xj’ = - xj (xj’ ≥ 0) - Nếu phát triển thành xj không ràng buộc về lốt ta thay bởi hiệu của 2 đổi mới không, tức làđặtxj = xj’ - xj’’ với xj’ ≥ 0, xj’’ ≥ 0 chăm chú rằng: Đây chưa phải là trở nên phụ đề xuất phải tính lại hàm kim chỉ nam theo cácbiến mới. Các ví dụ: đưa những bài toán QHTT sau về dạng bao gồm tắc 1/ f(x) = -2x1 +3x2 - 2x3 → min 2 x1 + x 2 − 2 x3 = 2  3 x1 + x3 = −3 x , x , x ≥ 0 1 2 3 lấy một ví dụ 1 này là dạng bao gồm tắc vì xẩy ra dấu = cùng x1, x2, x3 ≥ 02/ f(x) = x1 + x2 + x3 - 2x4 → max  x1 − x2 + 2 x3 ≥ 2  5 x1 − x2 − 3 x3 = 3 x , x , x , x ≤ 0 1 2 3 4 Giải ví dụ 2: VD2 không hẳn là chính tắc vì vi phạm luật 2 chỗ: ≥ 2; x1, x2, x3, x4 ≤0 Ta có: f(x) = x1 + x2 + x3 - 2x4 + 0 . X5 → max  x1 − x2 + 2 x3 − x5 = 2  (1) 5 x1 − x2 − 3 x3 = 3 x1 = - x1’ ; x2 = -x2’ ; x3 = -x3’, x4 = -x4’ (với x1’, x2’, x3’, x4’ ≥ 0) Ta nỗ lực x1, x2, x3, x4 vào (1)  x1 "+ x2 "−2 x3 "+ x5 " = 2  − 5 x1 "+ x2 "+3 x3 " = 3 kiếm tìm x1, x2, x3, x4, x5, x1’, x2’, x3’, x4’ (x5 là ẩn phụ) 3/ f(x) = - x1 + 2x2 +1/3 x3 - 2x4 → min tra cứu x1, x2, x3, x4  x1 − x2 − 3 x3 = −7  x + 2 x − x 4 ≤ −2 2 3   x1 + x3 + 2 x 4 = 1 / 2  x1 , x2 , x3 , x4 ≥ 0  Giải VD3 : VD3 này chưa phải chính tắc vì vi phạm luật một khu vực là ≤ -2 f (x) = -x1 + 2x2 + 1/3 x3 - 2x4 + 0 . X5 → min x1 − x2 −3 x3 = −7 x + 2 x − x 4 + x = 2 2 3 5  x1 + x3 + 2 x 4 =1 / 2   tìm kiếm x1, x2, x3, x4, x5 ≥0, (x5 là ẩn phụ) 4/ f(x) = x1 + 3x2 -2x3 → min tìm kiếm x1, x2, x3, x2’, x2’’, x3’, x4, x5 3 x1 + x2 − 2 x3 ≤ 7 − 2 x − 4 x + x =12  2 2 3  4 x1 + 3 x2 −8 x3 ≥10 x1 ≥ 0, x3 ≤ 0  Giải bài 4: Để đưa vấn đề trên về dạng chủ yếu tắc, ta yêu cầu đưa hồ hết ràng buộcbất phương trình về phương trình, đồng thời phần đông ẩn số đề nghị không âm. Tức là ràngbuộc thứ nhất được thêm vào đó ẩn phụ x4 ≤ 0, ràng buộc máy 3 được trừ đi một ẩn phụx5 ≥ 0Thay x3 = - x3’ (x3’ ≥ 0) x2 = x2’-x2’’(x2 ≥0, x2’’ ≥0) vậy việc trở thành f(x) = x1 + 3x3 + 2x3’ → min 3 x1 + x2 + 2 x3 "+x4 = 7  − 2 x1 − 4 x2 − x3 " =12 (1) 4 x +3 x +8 x "−x =10 1 2 3 5 cụ x2 vào (1) ta gồm 3x1 + x2 "− x2 " "+ 2 x3 "+ x4 = 7   − 2 x1 − 4 x2 "+ 4 x2 " "− x3 = 12  4 x + 3x "− 3x " "+ 8 x "− x = 10 1 2 2 3 5 x1, x2’, x2’’, x3’ ≥ 0; x4, x5 ≥ 0 (x4, x5 là ẩn phụ)1.2.3.2/ Dạng chuẩn chỉnh (chuẩn tắc ) : việc quy hoạch tuyến tính là dạng chuẩn chỉnh BT QHTT dạng bao gồm tắc thỏa cácđiều khiếu nại sau: - những bi mặt vế phải của các ràng buộc phổ biến ≥ 0 - mỗi ràng buộc chung tất cả biến cửa hàng tương ứng. Trở nên cơ sở là biến chuyển có hệ số là+1 tại một ràng buộc chung và hệ số là 0 ở những ràng buộc còn lại. (Tức là các biến cơsở sẽ khởi tạo thành một ma trận đối chọi vị). - những biến không cửa hàng ( không phải là thay đổi cơ sở) điện thoại tư vấn là biến tự do thoải mái Ví dụ 1: coi xét bài bác toán sau đây đã chuẩn chỉnh tắc không, tìm phương pháp cơ phiên bản banđầu f = x1 + 2x2 + x3 + x4 → min  x1 + x2 − x3 = 7(1)   2 x2 + x3 + x4 = 5(2)  x ≥ 0; j = (1,2,3, 4) j việc này là dạng chuẩn tắc bởi vì phương trình (1,2) đều xẩy ra dấu bằng, ràng buộcbiến xj ≥0 - hệ số hàm kim chỉ nam : c1 = 1, c2 = 2, c3 = 1, c4 = 1 - Ràng buộc phổ biến : m = 2 - Ràng buộc phát triển thành : n = 4 - thông số ràng buộc phổ biến : a11 = 1, a12 = 1, a13 = 1, a21 = 0, a22 = 1, a23 = 1, a24 = 1 - những hệ số tự do: b1 = 7, b2 = 5 Ta có hệ số ma trận A= x1 x2 x3 x4 1 1 -1 0 0 2 1 1 Ta bao gồm x1, x4 là biến cơ sở ; x2, x3 là trở nên tự vì vậy phương án cơ bản ban đầu : x2 = x3 = 0 vắt vào (1) cùng (2) của hệ bên trên tađược x1 = 7, x4 = 5. Phương pháp cơ bản ban sơ x = (7,0,0,5)Ví dụ 2 : f(x) = x2 - x5 → min  x1 + x2 − 2 x5 = 1(1)   3x2 − x3 + x5 = − 3(2)   − 2 x2 + x4 + x5 = 2(3)  x j ≥ 0; j = (1, 2,...,5) Đây không phải là vấn đề dạng chuẩn:Phương trình bên trên có thông số tự vì bi = -3 buộc phải ta nhân 2 vế cùng với -1  x1 + x2 − 2 x5 = 1(1)  − 3x + x − x = 3(2) 235   − 2 x2 + x4 + x5 = 2(3)  x j ≥ 0; j = (1,5)  - hệ số hàm kim chỉ nam : c1 = 1, c2 = -1 - Ràng buộc phổ biến : m = 3 - Ràng buộc trở thành : n = 5 - hệ số ràng buộc chung: a11 = 1, a12 = 1, a13 = 1, a14 = 1, a15 = -2, a21 = 0, a22 = -3, a23 = 1, a24 = 0, a25 = -1, a31 = 0; a32 = -2, a33 = 0, a34 = 1, a35 = 1 - những hệ số từ do: b1 = 1, b2 = 3, b3 = 2 - buộc ràng biến: xj≥0 Ta có hệ số ma trận: x1 x2 x3 x4 x5 A= 1 1 0 0 -2 0 -3 1 0 -1 0 -2 0 1 1 Ta bao gồm x1, x3, x4 là biến chuyển cơ sở x2, x5 là biến thoải mái Thay x2 = x5 = 0 vào (3) → x4 = 2 nỗ lực x2, x5 = 0 vào (2) → x3 = 3 vậy x2, x5 = 0 vào (1) → x1 =1 Vậy cách thực hiện cơ bản thuở đầu là: x = (1,0,3,2,0)1.3/ Giải vấn đề quan hệ con đường tính 2 biến đổi bằng cách thức hình học : vào trường hợp câu hỏi QHTT bao gồm 2 thay đổi ta có thể giải bằng cách thức hìnhhọc, ta áp dụng kết quả sau trên đây : 1/ Đường thẳng ax + by = c phân tách mặt phẳng tọa độ thành 2 miền, một miền là tậptất cả điểm M(x,y) thỏa ax + by > c một miền là tập toàn bộ các điểm M(x,y) : ax + by ví dụ 4: f(x) = 3x1 + 4x2 → max 2 x1 − 3x2 ≥ 2 − x1 + x2 ≤ 1x , y ≥ 01 1Để làm rõ hơn chân thành và ý nghĩa của bài toán giải bài toán bằng ph ương pháp hình h ọc ta xétví dụ thực tiễn sau đây:Ví dụ (5): Một công ty có 2 phân xưởng P1, P2 cùng cấp dưỡng 2 loại thành phầm A, B. Sốđơn vị sản phẩm các loại được cung cấp ra và giá thành mỗi giờ đồng hồ hoạt đông P1, P2 như sau: Phân xưởng 1 Phân xưởng 2Sản phẩm A 250 250Sản phẩm B 100 200Chi chi phí 600.000 1.000.000 công ty nhận được yêu cầu mua hàng là 5.000 solo vị thành phầm A cùng 3.000 đối kháng vịsản phẩm B. Hãy tra cứu cách triển lẵm thời gian cho mỗi phân xưởng vận động sao mang lại thỏamãn yêu cầu mua hàng và chi phí ít nhất. Call x1, x2 lần lượt là thời gian cần sắp xếp cho P1, P2 hoạt động.1.4/ phương pháp đơn hình1.4.1/ các đại lý của phương thức đơn hình: Tập lồi: Tập G ∈ ℜ n được điện thoại tư vấn là tập lồi giả dụ 2 điểm x, y nằm trong G thì cả đoạn cũng ở trong GTập lồi:Không là tập lồi:Điểm rất biên : Điểm x ∈ G được gọi là vấn đề cực biên của G nếu trong G không một đoạn thẳngnào thừa nhận x là điểm trong.

Xem thêm: Nhà Đất Cho Thuê Tại Ngõ 2 Vương Thừa Vũ Thanh Xuân, Hà Nội

Trở lại ví dụ ** ta thấy D gồm 3 điểm rất biên A 1, A2, A3 ta hotline chúng là phươngán cực biên (pacb) ( phương pháp cơ sở, phương án cơ bản). Nhận xét : bởi tính quan trọng của cách thực hiện cực biên ta thấy nhằm giải toán quanhệ đường tính ta chỉ cần xét trên tập hữu hạn những phương án cực biên.Cơ sở của phương pháp đơn hình : Để tìm phương án buổi tối ưu của bài xích tập quan lại hệ tuyến tính ta chỉ việc xét nhữngphương án cơ bản. Khởi nguồn từ một phương án cơ bản ban sơ x o như thế nào đó. Ta search cáchđánh giá nó. Nếu nó vẫn chưa phải là phương án về tối ưu thì ta tìm giải pháp chuyển thanh lịch mộtphương án cơ bản mới x1 tốt hơn. Quy trình này được lập lại chừng nào còn có khảnăng tiến hành sự di chuyển ấy và vị số phương pháp cơ bản là hữu hạn nên sau một s ốhữu hạn bước lặp hoặc sẽ thu được phương án buổi tối ưu của câu hỏi hoặc sẽ tóm lại vìhàm mục tiêu không trở nên chặt. Ta trả sử câu hỏi đang sống dạng (chuẩn- fmin) n f ( x ) =∑ j x j → in a m j=1 n ∑  aij x j = bi (i =1, m)  j =1 x ≥ 0, b ≥ 0 j i1.4.2/Bảng đối chọi hình Hệ Hệ ẩn P.án c1 c2 ..... Centimet cm+1 cs ...... Công nhân số cơ cơ phiên bản bản x1 x2 ... Xm xm+1 xs ..... Xnc1 x1 b1 a11 a12 a1nc2 x2 b2............cr xr br ar1 ar2 arm arn...............cm xm bm am1 am2 amm amm+1 amn ∆1 ∆2 ∆m ∆m +1 ∆m +n f(xo) f(x)Trong n ẩn ta cóx1, x2, ..., xm : các ẩn cơ bảnxm+1, ..,xn : những ẩn không cơ bản.Giá trị của f(x0) được tính như sau: f(x0) = c1b1+ .....+cmbmCác thông số kiểm tra được tính bằng phương pháp sau n ∆ j = ∑a j aij − ci (i = 1, m) j =1Chú ý rằng 1=2=…m =0.1.4.3/ Thuật toán 1-1 hình chi tiết : (sau khi có bảng đối chọi hình) bước 1: - kiểm tra tính buổi tối ưu của cách thực hiện : - giả dụ j 0 thì chuyển sang bước 2 bước 2: - Nếu có một j >0 mà với mọi aij ≤ 0 ( ∀ i =1,m) nghĩa là mọi phần tử trên cột xjđều ko dương. Xong xuôi thuật toán. Kết luận bài toán không giải được - nếu như với mỗi j > 0 đều phải sở hữu ít tốt nhất một aij > 0 thì chuyển sang cách 3 bước 3: ( chọn ẩn gửi vào, ẩn đưa ra khỏi hệ ẩn cơ bản) - Ẩn xs là ẩn đưa vào trường hợp s = maxj >0.- Ẩn đưa ra xr bi br λ = min (ars ≥ 0 ) = ais ars thành phần ars nằm trong cột xs ( ứng với ẩn gửi vào) và dòng x r (ứng cùng với ẩn chuyển ra)gọi là thành phần trục ( để ý rằng ars >0). Sau khi khẳng định được ần chuyển vào và giới thiệu ta gửi sang bước 4. Cách 4: (Cải tiến : tìm cách thực hiện cơ bản mới giỏi hơn) tạo bảng đơn hình mới tương ứng với hệ ẩn cơ bản mới thu được từ hệ ẩncơ bản trước bằng cách thay xr vị xs ( trên cột hệ số ta cầm cố cr bởi cs) - Để thu được cái xs (mới được gửi vào) ta chia dòng xr cho ars - Bảng đơn hình bắt đầu : Trên cái xs cũ thì ars = 1 các phân tử còn lại bằng 0, s = 0. Các thành phần còn lại (kể cả loại j) ta tính theo quy tắc hình chữ nhật ajk (mới) = ajk (cũ) ark. Ajs ars Cột k cột sDòng r ark ars phân tách nhânDòng j zjk? ajsSau đó quay trở về bước 1Cứ tiếp tục chạy thuật toán như bên trên theo vật dụng tự bước 1 -> bước 2->bước 3->bước 4->bước 1->,,,vv. Và vấn đáp yêu cầu bài toán.Ví dụ 1: Giải bài toán quan hệ tuyến đường tính sau: f(x) = 6x1 + x2 + x3 + 3x4 + x5 - 7x6 + 6x7 → min  − x1 + x 2 − x 4 + x6 + x7 = 3 − 2x + x − 4x + 2x − x = 9  1 3 4 6 7   4 x1 + 2 x 4 + x5 − 3x6 = 2  x j ≥ 0; ( j = 1,7 )  việc có dạng chuẩn với phương pháp cơ bản ban sơ x0 = (0,3,9,0,2,0,0) tất cả cácẩn cơ bạn dạng x2, x3, x5 (n=7, m=3) ta gồm bảng đối kháng hình.Hệ số Hệ ẩn P.án 6 1 1 3 1 -7 6 cơ x1 x2 x3 x4 x5 x6 x7 bản 1 x2 3 -1 1 0 -1 0 <1> 1 1 x3 9 -2 0 1 -4 0 2 -1 1 x5 2 4 0 0 2 1 -3 0 f(x) 14 -5 0 0 -6 0 7 -6Với f(x0) = C1b1 + c2b2 + c3b3 = 1.3 + 1.9 + 1.2 = 14 2 = 3 = 5 = 0 (vì x2, x3, x5 là ẩn cơ bản) 2 = 1 * 1 + 1 * 0 + 1 * 0 - 1 = 0 4 = 1 * (-1) + 1 * (-4) + 1*2 - 3 = - 6 6 = 1*1+1*2+1*(-3) - (-7) = 7 7 = 1*1+1*(-1) + 1*0 -6 = -6 Ta đang có tương đối đầy đủ thông tin bên trên bảng 1-1 hình, phải ta bước đầu dùng thuật toán đơnhình với bước bắt đầu là bước 1 cách 1: Ta thấy gồm 6 = 7 > 0 chuyển sang bước 2 cách 2: Ta thấy 6 > 0 có a16, a26 > 0 chuyển sang cách 3 cách 3: chọn ẩn đưa vào ta đi tìm kiếm các cột tất cả j >0, mặc dù ở ví dụ này chỉ gồm 6> 0 đề xuất x6 là ẩn đưa vào.Chọn ẩn giới thiệu :Ta có : a16 =1, a26 = 2, (a16, a26 >0) 3 9  3λ = min  ;  = suy ra x2 là ẩn cơ bản bị loại khỏi hệ ẩn cơ phiên bản phần tử a16 = 1 1 2  1được đóng khung ars = a16 = 1 chuyển sang bước 4 cách 4: kiến tạo bảng đối kháng hình mớiHệ số Hệ ẩn P.án 6 1 1 3 1 -7 6 cơ X1 X2 X3 X4 X5 X6 X7 bản -7 X6 3 -1 1 0 -1 0 1 1 1 X3 3 0 -2 1 -2 0 0 -3 1 X5 11 1 3 0 -1 1 0 3 f(x) -7 2 -7 0 1 0 0 -13 Ta cụ x2 bởi x6 với hệ số của x6 là -7 ta buộc phải tính lại 8*4 = 32 đại lượng trongbảng mới theo các công thức trong cách 4. Sau khoản thời gian tính tổng thể các cực hiếm trong bảng 1-1 hình mới ta quay trở lại bước 1: Tathấy 1 > 0; 4 > 0 suy ra cách 2. Trên 4 = 1 > 0 có toàn bộ a14, a24, a34 suy ra xong xuôi thuật toán. Kết luận bài toán đang cho không có phương án tối ưu:Ví dụ 2: Giải câu hỏi quan hệ đường tính sau: f(x) = x1+ 4x2 - x3 - x4 + x5 + 3x6 → min  2 x1 − x 2 + 5 x3 + x 4 = 1 2x + 4x − 2x + x = 2 1 2 3 5   x1 + 2 x 2 + x3 + x6 = 5  x j ≥ 0; ( j = 1,6) Bài toán tất cả dạng chuẩn , với giải pháp cơ bản thuở đầu x0 = (0,0,0,1,2,5)Các ẩn cơ bạn dạng x4, x5, x6 ( n = 6, m = 3)Ta có bảng 1-1 hình:Hệ số Hệ ẩn P.án 1 4 -1 -1 1 3 cơ bạn dạng x1 x2 x3 x4 x5 x6 -1 x4 1 2 -1 5 1 0 0 1 x5 2 2 <4> -2 0 1 0 3 x6 5 1 2 1 0 0 1 f(x) 16 2 7 -3 0 0 0Với f(x0) = c1b1 + c2b2 + c3b3 = (-1) * 1 + 1 * 2 + 3 * 5 = 164 = 5 = 6 = 0 (vì x4, x5, x6 là ẩn cơ bản)1 = (-1) * 2 + 1 * 2 + 3 * 1 - 1 = - 2 + 2 + 3 - 1 = 22 = (-1) * (-1) + 1 * 4 + 3 * 2 - 4 = 1 + 4 + 6 - 4 = 73 = ( -1) * 5 + 1 * (-2) + 3 * 1 - (-1) = - 5 -2 + 3 + 1 = - 3 Ta sẽ có không thiếu thốn thông tin trên bảng đối chọi hình, bắt buộc ta ban đầu dùng thuật toán đơnhình với bước đầu tiên là cách 1. Bước 1 : gồm 2 = 7 > 0 đưa sang bước 2 cách 2 : Ta thấy gồm 2 >0 và gồm a22 cùng a32 >0 chuyển sang cách 3 cách 3 : chọn ẩn chuyển vào : - Ta đi kiếm các cột j >0; tuy vậy ở bài này có 2 > 0 đề nghị x2 là ẩn đưa vào - lựa chọn ẩn giới thiệu : Ta gồm a22 = 4, a32 = 2 (a22, a32 > 0) γ = min  2 , 5  = 2 → x5 là ẩn cơ phiên bản bị nhiều loại khỏi hệ ẩn cơ bạn dạng   4 2 4Phần tử a22 = 4 được đóng khung ars = a22 = 4 đưa sang bước 4 bước 4: Xây dựng solo hình mới thông số Hệ ẩn P.án 1 4 -1 -1 1 3 cơ X1 X2 X3 X4 X5 X6 bản -1 X4 3/2 5/2 0 9/2 1 ¼ 0 4 X2 ½ ½ 1 -1/2 0 ¼ 0 3 X6 4 0 0 2 0 -1/2 1 F(x) 25/2 -3/2 0 50% 0 -7/4 0 - chọn ẩn gửi vào: ta gồm 3 > 0; lại sở hữu a13 cùng a33 > 0 → chọn x3 là ẩn chuyển vào  6 4 6 - chọn ẩn gửi ra: γ = min  → x4 là ẩn chuyển ra. Thành phần a13 là phần tử , = 18 2  18đóng khung; vậy ars = a13 = 9/2Hệ số Hệ ẩn P.án 1 4 -1 -1 1 3 cơ X1 X2 X3 X4 X5 X6 bản -1 X3 1/3 5/9 0 1 2/9 1/18 0 4 X2 2/3 7/9 1 0 1/9 5/18 0 3 X6 10/3 -10/9 0 0 -4/9 -11/18 1 f(x) 37/3 -16/9 0 0 -1/9 -16/9 01= (-1) * 5/9 + 4 * 7/9 + 3 * (-10)/9 - 1= - 16/94= - (-1) * 2/9 + 4 * 1 /9 +3 * (-4/9) - (-1) = - 1/95= (-1) * 1/18 + 4 * 5/18 + 3 * (-11/18) - 1 = - 16/9  10  21Vậy câu hỏi có phần tử tối ưu là xopt =  0, , ,0,0,  ; f(min) =37/3  3 33Chú ý : vấn đề dạng chuẩn f max.Cách 1 : ( con gián tiếp : đem về dạng chuẩn f → min)BT1 f → Max  g=-f → min BT2X∈D X∈D giả dụ xopt là bộ phận tối ưu của bài tập 1 ⇔ x cũng là phần tử tối ưu của bài xích toán2. Và quý giá của hàm phương châm là fmax = - gmin.Cách 2: (Trực tiếp)Thuật toán tương tự như thuật toán sinh sống dạng f → min. Chỉ chuyển đổi Bước 1: nếu như j ≥ 0 ∀ j thì phương pháp là tối ưu cách 2: Nếu gồm một j hệ số Hệ ẩn cơ P.án -1 4 2 -1 phiên bản cơ bạn dạng X1 X2 X3 X4 2 X3 4 2 -1 1 0 -1 X4 7 3 1 0 1 F(x) 1 2 -7 0 0 2 X3 11 5 0 1 1 4 X2 7 3 1 0 0 f(x) 50 23 0 0 7⇒ xopt = (0,7,11,0) ; fmax = 501.5/ Thuật toán đối chọi hình giải việc QHTT dạng tổng quát Khi xuất bản thuật toán 1-1 hình ta trả thiết là sẽ biết một phương pháp cơ bảntức là việc có dạng chuẩn. Tuy vậy trong thực tiễn không phải bài toán quan hệtuyến tính nào cũng đều có dạng chuẩn. Đó là vì sao người ta bắt buộc một thuật toán giải đ ượcbài toán QHTT dạng tổng quát.1.5.1/ Đưa việc QHTT dạng bao quát về dạng chuẩn chỉnh (bài toán M) Nếu việc QHTT (dạng thiết yếu tắc, bi ≥ 0) không có ngay phương pháp cơ bản banđầu thì ta thêm một số trong những biến mang vào để sở hữu ngay cách thực hiện cơ bản ban đầu. Vấn đề cóbiến giả điện thoại tư vấn là vấn đề (M).Ví dụ: Cho việc gốc (p) f = x1 - 2x2 +3x3 + x4 → min 4 x1 + x2 + 2 x3 + 2 x4 = 1   x1 − 2 x2 + 5 x3 − 4 x4 = 6  x ≥ 0; ( j = 1,4 ) jHãy viết việc M

Leave a Reply

Your email address will not be published. Required fields are marked *

  • Nam người mẫu khoả thân

  • Điền từ vào chỗ trống tiếng anh

  • Giá gỗ trắc đỏ đen

  • Tìm gái goi trên mạng

  • x

    Welcome Back!

    Login to your account below

    Retrieve your password

    Please enter your username or email address to reset your password.