Файл: пензенский государственный университет политехнический институт.docx

Методы исследования. Для решения поставленных задач использовались методы линейного программирования, целочисленного программирования, многокритериальной оптимизации, системного анализа.

Научная новизна работы заключается в следующем:

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

помощью эквивалентных преобразований и с использованием стандартных алгоритмов.

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

Основные положения, выносимые на защиту:

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

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на конференции:

VII Ежегодная всероссийская межвузовская научно-практическая конференция «Информационные технологии в науке и образовании. Проблемы и перспективы» (г. Пенза, 2020).

Публикации. Основные результаты работы опубликованы в 1 печатном издании.

Структура и объем работы. Работа состоит из введения, трех тематических глав, заключения, списка литературы и приложений. Общий объем основного текста – 83 страница, включая 20 рисунков. Список литературы изложен на 8 страницах и содержит 73 наименования.

Анализ задачи о назначениях и алгоритмов ее решения

Модели задач линейного программирования

Рассмотрим множество

X

 ^x₁

 ^x | g_i(x)  0, i 1, m^,

 

где

^^x2 ^

x 
^... ^

– вектор-столбец;

 

 ^xn

g_i(x), i1,m– заданные скалярные функции.

Пусть на множестве X определена скалярная функция ????⁽x⁾. Задачу максимизации функции ????⁽x⁾на множестве Х называют основной задачей математического программирования. Запись

f(x)  max ,x ∈ ????

означает, что ставится задача:

 либо найти оптимальную точку x^* ∈ ????:
f(x*)  max

xX
^f⁽^x⁾;

 либо если не существует такая точка x^*, то найти

f*  sup

xX

f(x) ;

либо убедиться, что

f(x)

не ограничена сверху на множестве Х;

либо убедиться в том, что X .

Множество Xназывают множеством допустимых решений,

неравенства

g_i(x)  0 , определяющие допустимое множество –

ограничениями, функцию ????⁽x⁾– целевой функцией. Точку

x*  arg max{f (x) | x  X} называют оптимальным решением.

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

Общая модель задачи линейного программирования имеет вид:

f(x)  c₁x₁ c₂x₂ ...  c_nx_n max(min),

_a₁₁x₁ a₁₂x₂ ...  a₁_nx_n b₁,


^...


^a_m₁x₁ a_m₂x₂ ...  a_mnx_n b_m,

a
_m1,1^x1





^^am1,2 ^x2

...

 ...  a

m1,n^xn

 b_m_₁,

_^^am k,1^x1 ^^am k,2 ^x2 ^^...^^am k,n^xn^^bm k^,

x_j 0 , ( j 1, l,

l n).

Без ограничения общности можно считать, что в системе ограничений первые ^mусловий являются уравнениями, а последующие k– неравенствами. Очевидно, этого всегда можно добиться за счет переупорядочения условий. Неравенства системы ограничений можно полагать одного знака, так как неравенства противоположного смысла можно всегда привести к данным путем умножения обеих частей на (–1).

Частными случаями общей модели задачи линейного программирования являются симметричная модель:

f(x)  c₁x₁ c₂x₂ ...  c_nx_n max,


_a₁₁x₁ a₁₂x₂ ...  a₁_nx_n b₁,