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