Application of dynamic programming methods for solving a problem on recruiting with considering specific content of military technical education

Full Text

В любом виде производственной и управленческой деятельности актуальными являются вопросы оптимизации, т.е. эффективного использования материальных и трудовых ресурсов. Большой вклад в развитие теории оптимизации внес великий ученый современности, лауреат Нобелевской премии Л.В. Канторович, который долгие годы преподавал в Высшем военно-морском инженерном училище (г. Ленинград). Большой вклад в становление и развитие теории оптимизации внесли отечественные и зарубежные ученые: Н.П. Абовский, И.О. Адамович, Н.В. Баничук, А.И. Богатырёв, В.А. Бунаков, А.И. Виноградов, М.И. Волынский, Г.А. Геммерлинг, Е.Н. Герасимов, В.Н. Гордеев, В.В. Васильев, В.П. Валуйских, Г.И. Гребенюк, Э.Р. Даниелов, В.А. Комаров, И.Б. Лазарев, Л.С. Ляхович и многие другие ученые и педагоги.

В рамках современного информационного общества термин «оптимизация» настолько стал широко использоваться, а в некоторых случаях интерпретироваться как любое улучшение уже имеющегося объекта, процесса (экономического, информационного, социального, биологического и др.) или системы, поэтому остановимся на следующей формулировке термина оптимизация [1, с. 186]. Под оптимизацией будем понимать поиск наилучшего варианта при наличии множества альтернатив [2, с. 100].

Целью данного исследования является адаптация традиционных задач оптимизации с учетом специфики военно-технического образования и разработка методики обучения решению этих задач с использованием различных компьютерных средств, включая программирование.

Одной из ключевых тем изучения таких дисциплин, как высшая математика и информатика, во всех технических гражданских и военных вузах является теория оптимизации, освоение которой строится на основе решения транспортной задачи, задачи о назначениях, коммивояжера и другие. Решение таких классов задач помимо традиционного ручного расчета предусматривает использование автоматизированных средств вычисления, табличных процессоров или систем программирования.

Специфика содержания обучения курсантов военных вузов диктует необходимость формулирования задач с направленностью на военно-технические исследования. На олимпиадах по информатике для курсантов военных вузов неоднократно встречаются задачи практической профессиональной направленности. И вопросы оптимизации тоже рассматриваются в применении к возможным реальным ситуациям на воинской службе будущих офицеров. Приведем некоторые варианты формулировок оптимизационных задач.

Задача 1. Необходимо доставить боеприпасы из пункта складирования на n расчетных позиций, расположенные на большом расстоянии друг от друга. Координаты расчетных позиций заданы (X, Y). Известны параметры, которые определяют пути дальнейшего движения из одной точки в другую, т.е. дороги, по которым можно беспрепятственно передвигаться. Груз доставляется колонной по одному маршруту из позиции «0» с возвратом в пункт складирования, в результате чего маршрут замыкается. Найти кратчайший путь движения средствами табличного процессора, используя надстройку «Поиск решения». Составить карту пути, применив средства построения графиков табличного процессора.

Решение данной задачи предполагает использование сложных формул и составных функций табличного процессора, а также, как сформулировано в задании, применение надстройки «Поиск решений». С учетом особенностей формулирования задачи курсанты должны использовать при решении данной задачи карту местности, на которую необходимо уметь наносить координаты, указанные в задаче (рис. 1).

 

Рисунок 1 – Схема маршрута между позициями

 

Задача 2. Определить оптимальный план перевозок горюче-смазочных материалов из нескольких пунктов отправления в зоне боевых действий при условии ограниченного финансирования. С демонстрацией построения транспортного графа либо в виде таблицы, либо в виде схемы с указанием маркированных вершин и ребер.

Задача 3. Для монтажа n объектов военной инфраструктуры требуется m единиц строительной техники. Известно время cᵢ_j работы i-ой единицы техники на j-ом объекте (например, i = 1..n, j = 1..m) (табл. 1).

 

Таблица 1 – Затраты времени на работу на объектах

Номер техники	Объекты
	I	II	III	n
1	2	9	10	8
2	2	6	4	5
3	4	7	1	3
..	..	..	..	..
m	7	4	3	2

 

Необходимо в соответствии с поставленной командованием задачей в условиях военного времени распределить технику по объектам таким образом, чтобы суммарное время работы на всех объектах было минимальным. Каждый вид строительной техники может работать на любом объекте, но только один.

Задача 4. Военно-транспортный самолет в боевых условиях загружается военными грузами трех типов, причем количество груза каждого типа не должно превышать значения M шт, например, 10. Каждый вид груза первого типа имеет вес [(N + 5) / 6] тонн и стоимость N руб., второго – [(110 − N) / 10] тонн и стоимость N + 10 руб., третий вид груза имеет вес [(70 − N) / 4] тонн и стоимость N + 15. Известна допустимая грузоподъемность, например 100 тонн. Требуется определить оптимальный план загрузки самолета с максимальной стоимостью груза [3, с. 31].

Задача 5. Самолет, имеющий скорость V₀ и находящийся на высоте H₀, должен увеличить скорость и высоту полета до значений V₁ > V₀ и H₁ > H₀. Требуется найти такое оптимальное управление самолетом, позволяющее выполнить заданный маневр с минимальными затратами топлива [4, с. 141].

Среди задач, входящих в круг вопросов оптимизации, имеется задача о комплектовании, которая изучается в соответствующих разделах высшей математики и курса информатики в вузах. Для решения задачи применяется так называемое линейное программирование как математический метод. Задача имеет решение в прикладных программных продуктах, в которых предусмотрено использование надстроек. В учебных целях в курсе информатики может быть использовано, помимо традиционных средств табличных процессоров, решение задачи с применением методов динамического программирования.

Вопросы динамического программирования изучались в работах ведущих ученых-программистов и педагогов: О.С. Аблялимовым, Д.А. Карповым, М.А. Посыпкиным, В.И. Струченковым, С.С.Т. Тант, и др. [5–8]. В них были проанализированы вопросы повышения быстродействия ряда алгоритмов динамического программирования при решении задач с данными большой размерности.

Понятие «динамическое программирование» как математический метод, применяемый наравне с линейным программированием, было введено Ричардом Беллманом (1940-е годы) для описания процедуры решения задачи, когда ответ на нее может быть найден только на основании решения предшествующей ей задачи [8; 4, с. 126], часто растянутой во времени. Это в какой-то мере объясняет термин «динамическое». Обращаясь к термину «программирование» в данном контексте, отметим использование однозначно прописанных последовательностей математических операций, включая логические. Имея своеобразный алгоритм, становится возможным описать его на конкретном языке программирования. Можно сказать, что в какой-то мере динамическое программирование является синонимичным понятию оптимизации [4]. Согласно теории динамического программирования, задача оптимизации должна решаться поэтапно, используя многократные итерации с делением полного исследуемого процесса на простые, далее неделимые в рамках решаемой задачи. Например, процесс планирования видов выполнения работ предприятия можно разделить на более мелкие временные интервалы, например пятилетки, как это было во времена Советского Союза. Есть классические задачи оптимизации, в которых подобное дробление имеет искусственное происхождение – например, задача оптимального резервирования, задача о загрузке, задача нахождения наилучшего способа прокладки дорог между удаленными пунктами, военными базами и т.д. Сущность подхода динамического программирования состоит в возможности заменить решение всей задачи решением последовательности оптимизационных задач более простого вида с применением итерационных приближений и сравнения с заданным критерием. Особенность метода динамического программирования, согласно принципу оптимальности Р. Беллмана, состоит в том, что каждый последующий шаг итерации использует результаты оптимизации предыдущего шага так, чтобы эффект, полученный на нем и на всех последующих шагах, был максимальным [9, с. 5, 45–67].

Динамическое программирование может рассматриваться как методология, основанная на едином подходе к разработке алгоритмов решения задач с формализацией критериев оценки полученных результатов в ходе пошаговой интерполяции [10, с. 86–121; 11, с. 10–18]. В ходе решения задач с использованием динамического программирования обычно перебирается большое количество вариантов с целью подбора оптимального в рамках поставленной задачи. Их формулировка может включать следующие варианты: подсчитать количество вариантов, найти оптимальный маршрут, эффективно распределить ресурсы и т.д. Оптимизация алгоритмов заключается в использовании дополнительной памяти для хранения результатов предыдущих вычислений, в частности, с меньшими значениями входных параметров [12, с. 123].

Динамическое программирование использует математические методы для решения задач комбинаторики, оптимизации и др. [13, с. 8–15] В задачах оптимизации, как правило, требуется выявить экстремумы с учетом целевой функции (например, максимизировать доходность некоторого мероприятия, минимизировать затраты на производство и т.д.). Задачи комбинаторики ориентированы на нахождение количества вариантов, комбинаций, обладающих конкретными при решении данной задачи свойствами. Динамическое программирование применяется для решения определенного класса подзадач, область применения которых весьма широка: от математики в чистом виде, до прикладных задач в экономике, программировании и военном деле [4; 10; 14, с. 68; 15, с. 35; 16, с. 163–166].

В ходе изучения темы «Решение задач оптимизации методами программирования» с курсантами военного вуза была рассмотрена задача о комплектовании. Условием задачи является обоснование оптимального набора необходимых вещей для организации выезда с миротворческой миссией в дружественное государство. Эти вещи должны быть размещены в походных условиях в помещении ограниченного объема. Исходными данными для решения задачи являются площадь, занимаемая каждым предметом в отдельности, и значимость (ценность) каждого предмета. Цель задачи оптимизации – максимизировать значимость вещей, которые нужно разместить на ограниченной площади помещения S_пом. Значимость, как характеристика анализируемых объектов, ранее использовалась при решении задач методом логико-вероятностного моделирования.

При подготовке исходных данных принимаем, что площадь будет определяться в квадратных дециметрах. Значимость каждого предмета определяется по абсолютной шкале от 0 до 100. Полученный список необходимо сформировать как словарь вида {'название предмета':(площадь, значимость) }:

stuffdict = {'cch_s':(300,75),

'cch_b':(500,80),

'bd':(400,100),

'bd_s':(200,40),

'dek':(200,70),

'tale':(300,80),

….

}

Для проведения процедуры максимизация суммарной значимости выбранных вещей можно осуществить перебор всех возможных комбинаций и выполнить расчет для каждой полученной комбинации. Однако, основываясь на теории комбинаторики, количество комбинаций напрямую зависит от количества предметов:

N = 2ⁿ

Если предположить, что анализируется 30 предметов, которые дают 2³⁰ возможных комбинаций выбора предметов, т.е. более 1 млрд. Вполне понятно, что такой перебор программным кодом займет очень много времени.

Можно начать анализ с наиболее значимого предмета и добавлять к нему следующие по рангу. Предложенные алгоритмы соответствуют полному перебору (метод «грубой силы») и «жадному» алгоритму. Большей эффективностью обладает алгоритм с использованием рекурсивных функций, разделив задачу на подзадачи. Сохраняя результаты в ячейках таблицы памяти и используя их на следующих итерациях, оптимальное решение найдется существенно быстрее [11, с. 35–44; 15, с. 34–35].

Этапы решения задачи с помощью динамического программирования будут следующие. На первом шаге необходимо создать словарь со списком элементов и их параметрами (площадь, значимость). Затем нужно создать списки значений площади и значимости, которые позже будут использоваться для построения таблиц памяти. Анализ таблицы будет осуществляться, начиная с последней строки таблицы, которая содержит оптимальное решение. В ходе решения задачи могут быть получены разные варианты оптимальности, например, когда два предмета занимают одинаковую площадью и имеют равную значимость или несколько предметов получаются сравнимыми с одним более крупным и ценным [13, с. 8; 17, с. 74; 18, с. 126–132; 19, с. 250–252].

Рассмотрим фрагменты программы решения задачи. Созданные списки значений площади и значимости следует разделить, например, следующим образом:

def Area_val(S_dict):

area = [S_dict[item][0] for item in S_dist]

value = [S_dict[item][1] for item in S_dist]

return area, value

Эти списки будут использованы для таблиц памяти.

Пусть n – общее число предметов, A – их максимально возможная суммарная площадь в передвижном пункте дислокации (2000 дм²). Требуется составить таблицу, которая должна состоять из (n + 1)-строк и (A + 1)-столбцов. Номера строк обозначим через i, столбцы – индексом a. Таким образом, номера столбцов – это использованы дискретные значения площади, отличающиеся друг от друга на единицу.

def get_memtable(S_dict, A=2000):

area, value = Area_val(S_dict)

# n – размер таблицы

n = len(value)

Создание и заполнение таблицы нулевыми значениями:

V=[[0 for a in range(A+1)] for i in range(n+1)]

for i in range(n+1):

for a in range(A+1):

# основной случай

if i==0 or a==0:

V[i][a]=0

Максимизируем значение суммарной значимости при условиия, что площадь, занимаемая предметом оказалась меньше площади, указанной в столбце:

elif area[i-1] <= a:

V[i][a] = max(value[i-1] +

V[i-1][a-area[i-1]], V[i-1][a])

Если площадь предмета больше площади, указанной в столбце, происходит присваивание значения ячейки из предыдущей строки:

else:

V[i][a] = V[i-1][a]

return V, area, value

Таблица создается и заполняется в формате вложенных списков. Заполнение получившегося массива строк осуществляется следующим образом:

(1) первая строка (с индексом 0) и первый столбец (с индексом 0) заполняются нулями, поскольку при нулевых значениях площади и количества элементов значение ячейки будет равно нулю;

(2) следующие строки таблицы значений V заполняются слева направо и сверху вниз. Выбор выполняется максимально из двух значений.

Сумма значимости актуального предмета value[i-1] и величина элемента из предыдущей строки i-1 с площадью, меньшей на величину площади текущего предмета area[i-1]. При этом отметим, что нумерация элементов в таблице начинается с нулевого. Значение элемента, находящегося в предыдущей строке и имеющего ту же площадь, присваивается из того же самого столбца, что и текущая ячейка. То же значение устанавливается в случае, если площадь, указанная в текущей ячейке, меньше, чем площадь соответствующего элемента. При одной и той же суммарной площади предметов происходит максимизация суммарной значимости. Найденные элементы находятся в последней строке таблицы. Для нахождения набора предметов с максимальной суммарной значимостью для указанной возможной площади просмотр таблицы должен вестись, начиная с нижнего правого угла таблицы от максимального значения.

def get_selected (S_dict, A=2000):

V, area, value = get_memtable(S_dict)

n = len(value)

# начало с последнего элемента таблицы

res = V[n][A]

# начальное значение площади

# максимальное

a = A

# список площадей и значимостей

items_list = []

for i in range(n, 0, −1):

# обратный проход

if res <= 0:

# условие прерывания (набор выполнен)

break

if res == V[i-1][a]:

continue

else:

# добавление предмета в общую сумму

items_list.append((area[i-1], value[i-1]))

# вычитание значения значимости от

# общей

res −= value[i-1]

# вычитание площади от общей

a −= area[i-1]

selected_stuff = []

# выбор ключей из исходного словаря

# (названия предметов)

for search in items_list:

for key, value in S_dict.items():

if value == search:

selected_stuff.append(key)

return selected_stuff

В результате получен список:

>>> stuff = get_selected (S_dict)

>>> print(stuff)

[…, 'tale', 'dek', 'bd', 'cch_s']

Для проверки нужно сделать контрольный расчет суммарной площади и значимости предметов:

>>> totarea = sum([S_dict[item][0] for item in stuff])

>>> totvalue = sum([S_dist[item][1] for item in stuff])

>>> print(totarea)

2000

>>> print(totvalue)

715

Задача об определении нужного набора предметов с ограничениями относится к классическим задачам о рюкзаке [20, с. 400–402; 21, с. 14–42]. В курсе информатики изучение раздела оптимизационных задач рекомендуется проводить, анализируя и применяя различные алгоритмы и программные средства. В этом случае у курсантов формируется более глубокое понимание особенностей алгоритмов, технологии программирования в целом, а также закрепляются знания математической теории оптимизации.

Подводя итог проведенному исследованию, следует отметить, что комплексный подход к обучению решению данного типа задач заключается в использовании разных прикладных программных продуктов и технологий программирования. При подготовке курсантов военного вуза к участию в Международной олимпиаде по информатике авторами статьи был разработан комплекс задач оптимизации, ориентированный на решение их в различных программных продуктах и средствах программирования. Была сделана комплексная оценка скорости решения задач разными методами, как того требует олимпиадное соревнование. На практических занятиях в стандартных контрольной и экспериментальной учебных группах сравнительный анализ показал более глубокое понимание курсантами теоретического материала и уверенное практическое владение технологиями программирования и решения задач в целом при указанном подходе обучения, что подтверждают результаты контрольных срезов, проведенных авторами в ходе подготовки к проверке вуза в 2021 г. (табл. 1).

 

Таблица 1 – Сравнительная таблица результатов обучения курсантов по теме «Динамическое программирование»

Контролируемая позиция	Контрольная группа (23 чел.)	Экспериментальная группа (21 чел.)
Понимание условия задачи	64%	75%
Правильность составления алгоритма решения задачи	65%	78%
Правильность решения задачи математическим методом	55%	67%
Правильность решения в табличном процессоре	60%	85%
Правильность решения задачи на языке программирования	58%	78%

 

Ежегодная проверка остаточных знаний курсантов проводится в форме тестирования. Вопросы контрольного теста по информатике включают раздел, связанный с пониманием сути задач оптимизации и методов их автоматизированного решения с применением компьютерных и программных средств. Анализ ответов показывает, что через два года после завершения изучения курса информатики курсанты, обучавшиеся в экспериментальных группах (20 чел.), дают на 25% больше верных ответов в сравнении с курсантами контрольных групп (23 чел.).

Темы дипломных проектов выпускников военных вузов, рекомендуемые заказчиками, в 80 процентах случаях содержат решение задач оптимизации с использованием средств автоматизированной обработки данных и технологий программирования. Таким образом, следует отметить, что задачи оптимизации остаются актуальными и имеющими большое практическое применение при обучении на старших курсах военного вуза и в профессиональной деятельности выпускников.

About the authors

Tatiana Evgenjevna Tarasova

Military Institute (Engineering and Technical) of Military Educational Institution of Logistics named after General of the Army A.V. Khrulyov

Email: tarasovate@yandex.ru

candidate of pedagogical sciences, associate professor of Military Architecture, Computer-Aided Design Systems, Natural Science Disciplines Department

Russian Federation, Saint Petersburg

Anatoly Vladimirovich Tarasov

Military Institute (Engineering and Technical) of Military Educational Institution of Logistics named after General of the Army A.V. Khrulyov

Email: toros707@mail.ru

candidate of technical sciences, associate professor of Military Architecture, Computer-Aided Design Systems, Natural Science Disciplines Department

Russian Federation, Saint Petersburg

Tatiana Sergeevna Smirnova

Military Institute (Engineering and Technical) of Military Educational Institution of Logistics named after General of the Army A.V. Khrulyov

Author for correspondence.
Email: smirnova_stef@mail.ru

candidate of pedagogical sciences, lecturer of Military Architecture, Computer-Aided Design Systems, Natural Science Disciplines Department

Russian Federation, Saint Petersburg

References

Supplementary files