Nghiên cứu phương pháp tính toán lựa chọn mang treo tối ưu cho máy bay khi tiêu diệt các loại mục tiêu mặt đất, mặt nước - Nguyễn Chí Thành

Công nghệ thông tin N.C. Thành, , L.T.T. Hồng, “Nghiên cứu phương pháp mục tiêu mặt đất, mặt nước.” 164 NGHIÊN CỨU PHƯƠNG PHÁP TÍNH TOÁN LỰA CHỌN MANG TREO TỐI ƯU CHO MÁY BAY KHI TIÊU DIỆT CÁC LOẠI MỤC TIÊU MẶT ĐẤT, MẶT NƯỚC Nguyễn Chí Thành*, Phạm Thu Hương, Nguyễn Sinh Huy, Lê Thị Thu Hồng Tóm tắt: Bài toán tính toán các phương án mang treo PTSTHK tối ưu cho các loại máy bay là một trong những nội dung quan trọng trong công tác chuẩn bị bay. Bài báo trình bày kết quả xây dựng mô hình để giải quyết bài toán lựa chọn phương án mang treo tối ưu cho các loại máy bay dựa trên thuật toán nhánh cận. Phương pháp này đã được đưa vào ứng dụng thực tiễn để xây dựng các phần mềm giải quyết các bài toán ứng dụng chiến đấu của phương tiện sát thương hàng không phục vụ công tác dẫn đường của Quân chủng Phòng không - Không quân và cho thấy kết quả khả quan. Từ khóa: Phương tiện sát thương hàng không; Mang treo tối ưu; Tối ưu hóa tổ hợp; Bài toán cái túi. 1. ĐẶT VẤN ĐỀ Những thành tựu của khoa học công nghệ và những phát minh mới về vũ khí trang bị, phương tiện chiến tranh hiện nay đã ảnh hưởng không nhỏ đến tổ chức lực lượng, chiến thuật, chiến lược quân sự của tất cả các nước trên thế giới. Với sự quan tâm, đầu tư nâng cao năng lực chiến đấu, Không quân Việt Nam đã được trang bị nhiều loại máy bay chiến đấu và vũ khí, khí tài hiện đại để trở thành lực lượng hết sức quan trọng trong thế trận bảo vệ an ninh, an toàn cho tổ quốc trước các thế lực thù địch. Trong tác chiến của lực lượng Không quân, mỗi loại vũ khí, phương tiện sát thương hàng không (PTSTHK) có tác dụng phá hủy mục tiêu nhất định, có thể đạt hiệu quả cao với mục tiêu này nhưng lại đạt hiệu quả phá hủy thấp thậm chí không gây nguy hại với loại mục tiêu khác. Bên cạnh đó, mỗi máy bay hiện có khả năng mang theo vũ khí rất đa dạng (tên lửa, bom, đạn pháo...), tuy nhiên khả năng mang theo mỗi loại vũ khí của máy bay là có giới hạn; vì vậy, khi có nhiệm vụ chiến đấu, người chỉ huy phải căn cứ vào yêu cầu nhiệm vụ chiến đấu cụ thể được giao, đặc tính mục tiêu cần đánh, điều kiện và tình hình chiến thuật, số bom đạn có trong kho, loại máy bay sẽ sử dụng mà lựa chọn phương án mang theo vũ khí để hiệu quả phá huỷ mục tiêu là lớn nhất, được gọi là phương án mang treo PTSTHK tối ưu. Bài toán tính toán lựa chọn phương án mang treo PTSTHK tối ưu cho các loại máy bay hiện có tại đơn vị nhằm tiêu diệt mục tiêu theo yêu cầu đặt ra với xác suất lớn nhất là một nội dung hết sức quan trọng trong công tác chuẩn bị tổ chức bay ứng dụng chiến đấu PTSTHK đánh mục tiêu mặt đất, mặt nước [1, 2]. Hiện nay, việc tính toán, giải quyết bài toán này tại các đơn vị được tiến hành chủ yếu bằng phương pháp thủ công, dựa trên việc tra cứu tài liệu sẵn có và kinh nghiệm tổ chức, thực hành tác chiến của cơ quan tham mưu tác chiến và người chỉ huy đơn vị. Với phương pháp này, thời gian tính toán sẽ mất nhiều Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 165 thời gian và không thể tránh khỏi sai sót trong tính toán, ảnh hưởng không nhỏ đến hiệu quả tác chiến. Do đó, việc xây dựng phần mềm tự động tính toán và đưa ra đáp án cho các bài toán trên là hết sức cần thiết nhằm rút ngắn thời gian tính toán, bảo đảm tính chính xác và nâng cao hiệu quả cho công tác chuẩn bị tổ chức chiến đấu. Trong bài báo này, chúng tôi trình bày phương pháp giải quyết bài toán tính toán lựa chọn phương án mang treo PTSTHK tối ưu để tiêu diệt mục tiêu trong tổ chức tiến công đường không ứng dụng chiến đấu PTSTHK đánh mục tiêu mặt đất, mặt nước (trong bài báo này sẽ được gọi là bài toán lựa chọn phương án mang treo PTSTHK tối ưu). Bài báo được trình bày theo thứ tự sau: Phần 2 trình bày nội dung nghiên cứu; Phần 3 trình bày các kết quả thử nghiệm, đánh giá; cuối cùng kết luận được trình bày trong Phần 4. 2. NỘI DUNG CẦN GIẢI QUYẾT 2.1. Bài toán tính toán lựa chọn phương án mang treo PTSTHK tối ưu đánh mục tiêu mặt đất, mặt nước trong tổ chức bay ứng dụng chiến đấu PTSTHK Bài toán tính toán lựa chọn phương án mang treo PTSTHK tối ưu để tiêu diệt mục tiêu là một bài toán quan trọng trong quá trình chuẩn bị tổ chức bay bắn, ném bom, phóng tên lửa vào các mục tiêu điểm, mục tiêu cụm (mục tiêu diện) và các mục tiêu phức hợp trong tấn công đường không. Bài toán lựa chọn phương án mang treo phương tiện sát thương hàng không tối ưu phải thỏa mãn các ràng buộc sau: - Ràng buộc về trọng tải tối đa: Tổng trọng lượng phương tiện sát thương mang theo không vượt quá trọng tải treo ngoài tối đa đối với từng loại máy bay (Đối với MiG-21BIS là 1000kg; Su-22M, Su-22M4 là 4000kg; Su-27SKM là 8000kg và Su-30MK2 là 8000kg). - Ràng buộc về chủng loại vũ khí: Mỗi loại máy bay chỉ có thể mang được một số chủng loại vũ khí sát thương nhất định, phụ thuộc vào thiết kế của máy bay và các hệ thống điều khiển được tích hợp trên máy bay. - Ràng buộc về trang bị hiện có của đơn vị: Mỗi đơn vị được biên chế một số lượng vũ khí nhất định; do đó, khi tính toán phương án mang treo phương tiện sát thương hàng không tối ưu, phải bảo đảm phù hợp với số lượng, chủng loại PTSTHK hiện có của đơn vị. - Ràng buộc về điểm treo, giá treo: Trên các dòng máy bay khác nhau, số lượng điểm treo, vị trí điểm treo trên máy bay khác nhau (Máy bay Su-27SMK có 10 điểm treo, máy bay Su-30MK2 có 12 điểm treo,...); mỗi vị trí mang treo được thiết kế để phù hợp với một số loại vũ khí nhất định với số lượng PTSTHK là hữu hạn (ví dụ trên máy bay Su-30MK2 chỉ có 6 vị trí có thể treo được tên lửa điều khiển với số lượng 1 quả/ 1 giá treo). Công nghệ thông tin N.C. Thành, , L.T.T. Hồng, “Nghiên cứu phương pháp mục tiêu mặt đất, mặt nước.” 166 - Ràng buộc về tính đối xứng: Khi lắp đặt các loại PTST trên máy bay phải bảo đảm tải trọng trên máy bay được bố trí cân bằng; do đó, tại hai vị trí mang treo đối xứng luôn được treo cùng chủng loại, số lượng PTST. Ví dụ, trên máy bay Su- 30MK2 khi treo 6 quả tên lửa điều khiển X-31A phải treo trên các giá đối xứng (3,4), (9,10), (11, 12), mỗi giá treo 01 quả. Nguyên tắc khi tính toán lựa chọn phương án mang treo PTSTHK tối ưu là lựa chọn các loại PTSTHK sao cho tổng diện tích sát thương của tất cả các loại PTSTHK do một máy bay mang theo để tấn công mục tiêu đạt giá trị lớn nhất, nghĩa là tổng hệ số sát thương mục tiêu trên một đơn vị diện tích độ lệch về tầm và hướng đạt giá trị lớn nhất.    s i tbiYiXi iSTii s i i MEE aSn K 11 (max) (1) Trong đó: Ki - Hệ số sát thương mục tiêu trên một đơn vị diện tích độ lệch về tầm và hướng của loại phương tiện sát thương i mà máy có thể mang. ni - Số lượng phương tiện sát thương loại i mà máy bay có thể mang (quả). ai - Hệ số loạt khi sử dụng phương tiện sát thương loại i. EXi, EYi - Độ lệch xác suất theo tầm và hướng (m). SSTi - Diện tích sát thương của một phương tiện sát thương loại i (m 2). Mtbi - Số lượng phương tiện sát thương trung bình cần trúng mục tiêu để sát thương mục tiêu theo mức độ tổn thất dự kiến khi sử dụng phương tiện sát thương loại i (quả). s - số lượng loại phương tiện sát thương được sử dụng để sát thương mục tiêu theo mức độ tổn thất dự kiến. Để giải quyết bài toán nêu trên, cần thực hiện các bước tính toán từ các tham số đầu vào để tính các giá trị trung gian, kết hợp với tra cứu các bảng biểu để tính toán giải bài toán tối ưu thỏa mãn các ràng buộc trên và đưa ra kết quả cuối cùng. Quy trình tổng quát để giải quyết các bài toán này có thể khái quát như sau: Bước 1: Nhập các tham số đầu vào (loại mục tiêu, máy bay sử dụng, các loại PTSTHK có trong trang bị của đơn vị (với dạng bài toán tối ưu theo trang bị hiện có của đơn vị), mức độ sát thương mục tiêu yêu cầu, độ lệch xác suất tản mát theo tầm và theo hướng, hệ số loạt khi sử dụng phương tiện sát thương). Bước 2: Đối với mục tiêu cụ thể, xác định các loại PTSTHK có thể sử dụng để sát thương mục tiêu đó. Đối với loại máy bay đã chọn, xác định các loại PTSTHK có thể mang trên máy bay. Đối với từng loại PTSTHK có thể sử dụng để sát thương mục tiêu mà máy bay có thể mang, ta xác định diện tích sát thương của một phương tiện sát thương với mức độ sát thương mục tiêu theo yêu cầu; xác định số lượng PTSTHK tối đa mà máy bay có thể mang; xác định số lượng phương tiện sát thương trung bình cần trúng mục tiêu để sát thương mục tiêu theo mức độ tổn thất Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 167 dự kiến; xác định các điểm treo có thể treo trên máy bay, số lượng tối ta có thể treo tại từng điểm treo. Bước 3: Tính toán các giá trị trung gian. Giải bài toán tối ưu, đáp ứng các ràng buộc. Bước 4: Đưa ra phương án mang treo PTSTHK tối ưu để tiêu diệt mục tiêu theo yêu cầu của từng bài toán. Ví dụ: Chọn phương án mang phương tiện sát thương hàng không tối ưu đối với MiG-21BIS để tiêu diệt tên lửa chiến thuật “Lance” đặt trên bệ phóng tại trận địa hỏa lực không có công sự với các điều kiện cho trước như sau: MiG-21BIS ném bom bay bằng: độ lệch xác suất theo tầm EX = 86m, độ lệch xác suất theo hướng EY = 62m, hệ số loạt khi ném bom a = 1; MiG-21BIS ném bom bổ nhào: độ lệch xác suất E = 40m, a = 1; Dùng tên lửa C-5: E = 12m, a = 0.18; Dùng tên lửa C-24: E = 15m, a = 0.78; Dùng súng: E = 10m, a = 0.87 Lời giải: Bước 1: Mục tiêu xác định là “Tên lửa chiến thuật Lance trên bệ phóng tại trận địa hỏa lực lộ thiên (không có công sự)”; Máy bay sử dụng là MiG-21BIS; mức độ sát thương mục tiêu yêu cầu là “tiêu diệt” - mức A Bước 2: Từ mục tiêu trên ta xác định các phương tiện sát thương có thể sử dụng để tiêu diệt mục tiêu gồm: ФАБ-500Ш, ФАБ-500ШН, ФАБ-500М-62, ФАБ- 500М-54, ОФАБ-250ШН, ОФАБ-250-270, ФАБ-250М-62, ОФАБ-100-120, АО-10, С-24, С-8, С-5КО, С-5КП, ОФЭ-23, Б3-23, ОФЗ-ЗО, БР-30, ГШ-23 Máy bay sử dụng là MiG-21BIS, ta xác định các loại phương tiện sát thương mà máy bay có thể mang để tiêu diệt mục tiêu trên bao gồm: ФАБ-500Ш, ФАБ- 500ШН, ФАБ-500М-62, ФАБ-500М-54, ОФАБ-250ШН, ОФАБ-250-270, ФАБ- 250М-62, ОФАБ-100-120, С-24, С-5КО, С-5КП, ГШ-23 Đối với từng loại PTSTHK có thể sử dụng để sát thương mục tiêu mà máy bay có thể mang, ta xác định diện tích sát thương của một phương tiện sát thương với mức độ sát thương mục tiêu theo yêu cầu; xác định số lượng PTSTHK tối đa mà máy bay có thể mang; xác định số lượng phương tiện sát thương trung bình cần trúng mục tiêu để sát thương mục tiêu theo mức A; xác định điểm treo PTSTHK đó trên máy bay (máy bay MiG-21Bis có 5 điểm treo, 4 điểm treo dưới cánh, 1 điểm treo dưới thân), số lượng PTSTHK tối đa có thể treo trên mỗi điểm treo. Bước 3: Tính toán các giá trị trung gian, giải bài toán tối ưu để thỏa mãn các ràng buộc, thỏa mãn nguyên tắc chọn phương án mang treo PTSTHK tối ưu:    s i tbiYiXi iSTii s i i MEE aSn K 11 đạt giá trị max Bước 4 (Kết luận): Để tiêu diệt tên lửa chiến thuật “Lance” đặt trên bệ phóng tại trận địa hỏa lực không có công sự thì phương án mang vũ khí tối ưu là mang 4 tên Công nghệ thông tin N.C. Thành, , L.T.T. Hồng, “Nghiên cứu phương pháp mục tiêu mặt đất, mặt nước.” 168 lửa không điều khiển C-24 kết hợp với pháo ГШ-23. 2.2. Mô hình hóa bài toán lựa chọn phương án mang treo PTSTHK tối ưu Từ định nghĩa trên ta có thể thấy bài toán tính toán lựa chọn phương án mang treo PTSTHK tối ưu để tiêu diệt mục tiêu là một bài toán tối ưu tổ hợp. Chúng ta có thể đưa bài toán này về dạng mở rộng của bài toán cái túi [3]. Bài toán cái túi có nội dung như sau: cho một tập hợp các vật thể có khối lượng và giá trị khác nhau, hãy chọn số lượng mỗi vật để cho vào túi sao cho tổng khối lượng không vượt quá giới hạn và tổng giá trị đạt giá trị lớn nhất có thể. Bài toán cái túi đã được quan tâm nghiên cứu từ lâu [4] do nó có nhiều ứng dụng trong công nghiệp và tài chính. Có một số dạng bài toán cái túi như bài toán cái túi dạng 0-1, bài toán cái túi bị chặn và bài toán cái túi không bị chặn, bài toán cái túi nhiều lựa chọn. Ta có n loại đồ vật, x1 tới xn. Mỗi đồ vật xj có một giá trị pj và một khối lượng wj. Khối lượng tối đa mà cái túi có thể chứa là c. Bài toán cái túi dạng 0-1 là bài toán chọn ra một tập con của n vật sao cho tổng giá trị của các vật được chọn là lớn nhất nhưng vẫn thỏa mãn điều kiện tổng khối lượng không vượt quá sức chứa c. Bài toán này có thể được phát biểu bằng toán học như sau: Cực đại hóa ∑ sao cho ∑ ≤ , ∈ {0,1}, = 1, , . Trong đó là biến nhị phân có giá trị là 1 nếu vật j được cho vào túi và có giá trị là 0 nếu ngược lại. Bài toán cái túi nhiều lựa chọn (multiple-choice knapsack problem - MCKP) là một bài toán tổng quát hóa từ bài toán cái túi, với tập hợp các đồ vật được chia thành các lớp. Phát biểu một cách hình thức, xét bài toán xếp các đồ vật thuộc m lớp , , vào một cái túi có sức chứa với khối lượng tối đa c. Mỗi đồ vật ∈ có giá trị là và khối lượng là . Bài toán đặt ra là chọn duy nhất một đồ vật từ mỗi lớp sao cho tổng giá trị đạt được là cực đại sao cho tổng khối lượng tương ứng không vượt quá sức chứa c. Mục tiêu của bài toán là xác định các giá trị của biến nhị phân , biến này có giá trị bằng 1 khi và chỉ khi đồ vật j được chọn trong lớp . Bài toán này được phát biểu dưới dạng toán học như sau: Cực đại hóa ∑ ∑ ∈ sao cho ∑ ∑ ∈ ≤ , ∑ ∈ = 1, = 1, ,, ∈ {0,1}, = 1,, ∈ . Bài toán lựa chọn phương án mang treo PTSTHK tối ưu có thể được đưa về dạng bài toán cái túi và áp dụng các thuật toán giải quyết bài toán cái túi để giải bài toán này. Đối với bài toán lựa chọn phương án mang treo PTSTHK tối ưu được Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 169 phát biểu ở phần 2.1, chúng ta đưa nó về dạng mở rộng của bài toán cái túi nhiều lựa chọn như sau. Coi mỗi PTSTHK là một đồ vật trong bài toán cái túi, các điểm treo của máy bay tương ứng với các lớp, đầu ra của bài toán cái túi nhiều lựa chọn là số lượng từng loại đồ vật được chọn cho mỗi lớp, tương ứng với một phương án mang treo tối ưu với mỗi điểm treo mang một loại PTSTHK. Trên máy bay có những cặp điểm treo đối xứng, yêu cầu với số lượng và chủng loại PTSTHK treo ở những điểm này là giống nhau để đảm bảo tính cân bằng cho máy bay. Để xử lý ràng buộc này, mỗi cặp điểm treo đối xứng có thể cho vào 1 lớp và đối với các lớp này khi tính khối lượng và giá trị thì ta nhân với hệ số 2 cho 2 điểm treo. Ràng buộc về tải trọng tối đa của máy bay có thể đưa về ràng buộc sức chứa c của cái túi. Khối lượng wj của các đồ vật được tính bằng khối lượng của từng loại PTSTHK. Tuy nhiên chúng ta phải thêm các ràng buộc để phù hợp với bài toán lựa chọn phương án mang treo tối ưu như ràng buộc về số lượng PTSTHK có thể mang ở mỗi điểm treo. Ràng buộc theo trang bị hiện có của đơn vị có thể được đưa về ràng buộc theo số lượng tối đa của mỗi loại PTSTHK qj. Giá trị của biến biểu diễn số lượng PTSTHK loại j được mang ở điểm treo tương ứng với lớp i. Ở bài toán này giá trị của không phải là nhị phân mà nó có thể có giá trị từ 0 đến số lượng tối đa PTSTHK loại j có thể treo ở điểm treo tương ứng với lớp i. Bài toán lựa chọn phương án mang treo PTSTHK tối ưu được biểu diễn dưới dạng toán học như sau. Cực đại hóa ∑ ∑ sao cho ∑ ∑ + min, 1 ≤ , (2) ∑ min (, 1) = 1, = 1, ,, (3) ∑ ≤ , = 1, , (4) ∈ 0,1, , , = 1, ,, = 1, , , (5) = 1 nếu ≤ 2 nếu > (6) Trong đó ràng buộc (2) là ràng buộc về tải trọng tối đa của máy bay, là khối lượng của các chốt giá, giá treo, bệ phóng cần sử dụng khi treo PTSTHK loại j trên điểm treo tương ứng với lớp i. Ràng buộc (3) quy định mỗi lớp chỉ được chọn 1 loại PTSTHK. Ràng buộc (4) quy định số lượng tối đa của mỗi loại PTSTHK, tương ứng với số lượng của PTSTHK loại j trong trang bị hiện có của đơn vị. Trong ràng buộc (5), là số lượng tối đa PTSTHK loại j có thể mang trên điểm treo tương ứng với lớp i. là hệ số đối xứng, với f là số lượng những điểm treo không yêu cầu tính đối xứng, tương ứng với các lớp 1, 2, ..., f là các điểm treo không yêu cầu tính đối xứng có giá trị hệ số là 1, các lớp + 1, + 2, , tương ứng với các cặp điểm treo đối xứng, do đó các lớp này có hệ số là 2. Công nghệ thông tin N.C. Thành, , L.T.T. Hồng, “Nghiên cứu phương pháp mục tiêu mặt đất, mặt nước.” 170 Giá trị pj của mỗi đồ vật (tương ứng với mỗi loại PTSTHK) được tính theo công thức sau. tbjYjXj jSTj j MEE aS p .. .  (7) Sau khi giải bài toán cái túi, ta sẽ được một cách chọn các đồ vật để cực đại biểu thức ∑ ∑ , khi đó công thức (1) cũng đạt giá trị cực đại. Điều này được chứng minh như sau. Ta có: = = = ∑ chính là số lượng PTSTHK loại j treo trên các điểm treo của máy bay, chính là bằng giá trị là số lượng phương tiện sát thương loại j mà máy bay mang. Do dó biểu thức ∑ ∑ có giá trị bằng biểu thức (1). Như vậy, phương án lựa chọn PTSTHK tương ứng với cách chọn đồ vật này chính là phương án mang treo tối ưu cần tìm. Để giải quyết bài toán lựa chọn phương án mang treo PTSTHK tối ưu, chúng ta chỉ cần giải bài toán cái túi tương ứng. Để giải quyết bài toán cái túi, các nhà khoa học thường sử dụng các thuật toán như chiến lược tham ăn (greedy algorithm), quy hoạch động (dynamic programming), nhánh cận (branch and bound). Trong các cách tiếp cận này, chiến lược tham ăn thường đơn giản, rất hiệu quả nhưng trong nhiều trường hợp không tìm ra nghiệm tối ưu mà chỉ cho ra nghiệm tốt, gần đúng với nghiệm tối ưu [5]. Kỹ thuật quy hoạch động giải quyết bài toán bằng cách chia bài toán thành các bài toán con theo hướng tiếp cận bottom-up, trong đó ta tính nghiệm của bài toán lớn thông qua nghiệm của các bài toán con đã được giải và ghi lại kết quả. Thuật toán quy hoạch động để giải bài toán cái túi cũng khá đơn giản và hiệu quả, tuy nhiên thuật toán này chỉ áp dụng được với các bài toán có khối lượng các đồ vật là số nguyên, với những bài toán có khối lượng đồ vật không phải là số nguyên thì không áp dụng được thuật toán này. Đối với bài toán lựa chọn phương án mang treo PTSTHK tối ưu thì khối lượng của các PTSTHK không phải là số nguyên do đó chúng tôi không áp dụng thuật toán quy hoạch động cho bài toán này. Chiến lược tham ăn cũng không được sử dụng do nó không tìm ra được nghiệm tối ưu của bài toán. Do đó, đối với bài toán này, chúng tôi lựa chọn thuật toán nhánh cận [6] để giải quyết. Thuật toán nhánh cận có thể tìm ra nghiệm tối ưu và có thể chạy với trường hợp khối lượng đồ vật không phải là số nguyên. Thuật toán nhánh cận tìm phương án tối ưu bằng cách xét các phương án có thể thực hiện và xác định ra phương án tối ưu, trong khi liệt kê các phương án trong không gian tìm kiếm tìm cách giảm số lượng phương án phải xét bằng cách Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 171 đảm bảo các phương án không được xét không thể chứa phương án tối ưu. Thuật toán nhánh cận cho bài toán lựa chọn phương án mang treo PTSTHK tối ưu được minh họa ở Hình 1. Thuật toán NhánhCận(l): l là chỉ số của biến tiếp theo với phương án hiện tại là = ′ với = 1, , − 1, = 1, , if ∑ ∑ + min, 1 > then return if ∑ ∑ > then ≔ ∑ ∑ , ∗ ≔ ′ if ( > ) then return Tính ′ = TínhCậnMCKP(, ) if ′ > then for j := 1 to n ′ ≔ 0 for j := 1 to n for k := dij to 1 ′ ≔ , if ∑ ′ ≤ then NhánhCận(l + 1) ′ ≔ 0 Hình 1. Thuật toán nhánh cận giải bài toán lựa chọn phương án mang treo PTSTHK tối ưu. Ở Hình 1 thuật toán nhánh cận được cài đặt dưới dạng thủ tục đệ quy trong đó biến z là biến toàn cục lưu lại giá trị của phương án tối ưu mà thuật toán tìm được. Thuật toán khởi tạo với z là giá trị của phương án là kết quả của chiến thuật tham ăn. Hàm TínhCậnMCKP tính toán cận cho thuật toán bằng cách giải bài toán MCKP với điều kiện biến xij là số thực, theo cách tính trong [3]. 3. THỬ NGHIỆM, ĐÁNH GIÁ Để thử nghiệm tính chính xác phương pháp được đề xuất ở phần 2 trong việc giải quyết bài toán lựa chọn phương án mang treo PTSTHK tối ưu, chúng tôi đã tiến hành thử nghiệm với 30 bài toán với đầu vào khác nhau, các bài toán này được lấy từ các giáo trình của Học viện PK-KQ hoặc được xây dựng bởi các chuyên gia của Quân chủng PK-KQ. Các bài toán này được xây dựng với tham số đầu vào là các khả năng mang treo thực tế của 4 loại máy bay Su-22M, Su-22M4, Su-27SKM và Su-30MK2; các đặc tính của các loại PTSTHK có trong trang bị của Quân chủng PK-KQ. Sau khi chạy chương trình với 30 bài toán, các kết quả được so Công nghệ thông tin N.C. Thành, , L.T.T. Hồng, “Nghiên cứu phương pháp mục tiêu mặt đất, mặt nước.” 172 sánh với kết quả giải các bài toán bằng tính toán thủ công do những người tham gia thử nghiệm thực hiện. Những người tham gia thử nghiệm được chia thành 2 nhóm là chuyên gia (nắm vững kiến thức về vũ khí hàng không và bài toán mang treo tối ưu) và không phải chuyên gia. Chương trình phần mềm cài đặt thuật toán nhánh cận để giải bài toán lựa chọn phương án mang treo PTSTHK tối ưu được viết bằng công cụ lập trình Visual C#, các thử nghiệm được chạy trên máy tính để bàn hệ điều hành Windows 10. Để xác định phương án mang treo tối ưu, người sử dụng nhập các đầu vào của bài toán như chủng loại máy bay, loại mục tiêu, chủng loại, số lượng PTSTHK có trong trang bị của đơn vị, mức độ sát thương mục tiêu yêu cầu, độ lệch xác suất tản mát theo tầm và theo hướng, hệ số loạt khi sử dụng phương tiện sát thương, phần mềm sẽ tự động tính toán các tham số cho bài toán cái túi tương ứng với các đầu vào đó, do đó người sử dụng chỉ cần nắm được kiến thức chuyên môn nghiệp vụ của ngành vũ khí hàng không là có thể dễ dàng sử dụng. Sau khi thực hiện giải các bài toán bằng chương trình, các kết quả đạt được do chương trình tính toán kiểm tra tính đúng đắn theo quy trình nghiệp vụ. Kết quả cho thấy các kết quả tính toán của chương trình tính đúng đáp số 30/30 bài toán so với lời giải bằng phương pháp nghiệp vụ của chuyên gia, trong khi đó nhóm không phải chuyên gia chỉ giải đúng được 27/30 bài toán. Như vậy, việc sử dụng chương trình giúp việc giải quyết bài toán mang treo tối ưu một cách tự động, tiết kiệm thời gian, công sức cho cán bộ nghiệp vụ và giảm khả năng sai sót khi giải quyết bài toán. 4. KẾT LUẬN Để đáp ứng nhu cầu giải quyết các bài toán tính toán ứng dụng chiến đấu PTSTHK một cách nhanh chóng, chính xác, đáp ứng yêu cầu tác chiến của Quân chủng Phòng không – Không quân, chúng tôi đã nghiên cứu xây dựng thuật toán giải quyết bài toán lựa chọn phương án mang treo PTSTHK tối ưu để tiêu diệt mục tiêu dựa trên thuật toán nhánh cận cho bài toán cái túi. Thuật toán này đã được cài đặt và thử nghiệm với một tập các bài toán mẫu, kết quả thử nghiệm cho thấy kết quả tính toán của mô hình này là chính xác, tốc độ tính toán cao. Phương pháp giải này đã được xây dựng thành một module tính toán tích hợp vào hệ thống phần mềm tính toán ứng dụng chiến đấu sử dụng phương tiện sát hương hàng không tiêu diệt mục tiêu mặt đất, mặt nước, được triển khai tại Quân chủng Phòng không – Không quân, giúp người dùng tra cứu nhanh và giải nhanh các bài toán, phục vụ tham mưu, chỉ huy trong công tác dẫn đường ở Quân chủng Phòng không – Không quân. Lời cảm ơn: Nhóm tác giả cảm ơn sự tài trợ về kinh phí của đề tài: “Nghiên cứu phát triển, hoàn thiện hệ thống phần mềm tính toán ứng dụng chiến đấu sử dụng phương tiện sát thương hàng không tiêu diệt mục tiêu mặt đất, mặt nước”. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 173 TÀI LIỆU THAM KHẢO [1]. Đỗ Duy Đản, “Tài liệu sử dụng vũ khí hàng không công kích mục tiêu mặt đất, mặt nước”, Học viện PK-KQ (2005). [2]. Lê Đình Vạn, “Giáo trình ứng dụng chiến đấu súng, pháo, tên lửa trên máy bay”, Học viện PK-KQ (2000). [3]. Kellerer, Hans, Ulrich Pferschy, and David Pisinger, "Knapsack problems", Springer-Verlag Berlin Heidelberg (2004). [4]. Mathews, George B., "On the partition of numbers.", Proceedings of the London Mathematical Society 1.1 (1896): 486-490. [5]. Đinh Mạnh Tường, “Cấu trúc dữ liệu & thuật toán”, Nhà xuất bản Khoa học và kỹ thuật (2001). [6]. Kolesar, Peter J., "A branch and bound algorithm for the knapsack problem.", Management science 13.9 (1967): 723-735. ABSTRACT A METHOD FOR WEAPONS LOADS OPTIMIZATION PROBLEM OF AIRCRAFTS IN AIR-TO-SURFACE MISSIONS The weapons loads optimization problem is one of the important task in aircraft mission preparation. The paper presents a mathematical representation for the problem, and proposed an algorithm to solve it. Experiment results show that the proposed method could the problem with fast and accurate calculations. The method was applied to build software for Vietnam People’s Air and Air Defense Force. Keywords: Weapons loads optimization; Aircraft weapons usage; Knapsack problem. Nhận bài ngày 28 tháng 06 năm 2018 Hoàn thiện ngày 04 tháng 10 năm 2018 Chấp nhận đăng ngày 05 tháng 11 năm 2018 Địa chỉ: Viện Công nghệ thông tin, Viện KHCNQS. *Email: thanhnc80@gmail.com.