Алгоритм решения задачи линейного программирования на основе симплекс-метода

В данной статье в качестве образца разработки алгоритма решения задачи (подготовки к решению на ЭВМ) выбрана задача линейного программирования. Линейное программирование находит применение во многих сферах, в том числе в подготовке управленческих решений при управлении организацией. Решение задачи линейного программирования позволяет найти оптимальный (наилучший) вариант использования имеющихся в распоряжении хозяйствующего субъекта ограниченных ресурсов.

Задачи линейного программирования могут быть решены разными методами: с помощью апекс-метода – новой версии итерационного метода [1], геометрического мето да [2], нейросетевого метода [3], смешанного целочислен ного линейного программиро-

Божко Леся Михайловна доктор экономических наук, доцент, профессор кафедры информационных и вычислительных систем, Петербургский университет путей сообщения Александра I, Санкт-Петербург. Сфера научных интересов: компьютерное и имитационное моделирование, алгоритмы и методы имитационного моделирования в экономических системах, цифровые технологии в менеджменте. Автор более 160 опубликованных научных работ. ORCID: 0000-0002-3329-7977, SPIN-код: 4076-2375, AuthorID: 648758.

вания [4] и др. В данном исследовании поставлена цель разработать алгоритм решения задачи линейного программирования с использованием симплекс-метода.

Симплекс-метод находит применение для решения широкого круга экономических задач [5–8]. Выбор симплекс-метода обоснован наличием преимуществ по сравнению с другими методами, например методом Гомори [9], а также необходимостью применения уже использованного метода при разработке математической модели решения задачи линейного программирования и в алгоритме решения такой задачи [10].

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

• -    при разработке структуры открытого проекта (ГОСТ 34.003–90; ГОСТ 24.104–85; ГОСТ 2.105–95; ГОСТ 7.32–2001; РД 50–34.698–90);

• -    при использовании терминов и определений программного обеспечения (ГОСТ Р 6.30–2003; ГОСТ 19781–90);

• -    при изображении схем алгоритмов (ГОСТ 19.701–90).

Постановка задачи исследования

Управленческая задача состоит в подготовке предложения по определению количества каждого из двух возможных типов схем погрузок комплексов спецгруза для максимальной загрузки (по весу) железнодорожного состава F (т).

Алгоритм решения задачи линейного программирования на основе симплекс-метода

Для погрузки выделен подвижной железнодорожный состав четырех видов i=1,4 в количестве:

• •    четырехосных крытых вагонов ( b (1)) – 12 единиц;

• •    двухосных крытых вагонов ( b (2)) – 8 единиц;

• •    двухосных платформ ( b (3)) – 12 единиц;

• •    четырехосных платформ ( b (4)) – 16 единиц.

Погрузка комплексов спецгруза может производиться с использованием схем погрузок двух типов j=1,2 , включающих следующее количество и вид железнодорожного подвижного состава:

для одной схемы погрузки 1-го типа ( j =1):

• •    четырехосных крытых вагонов ( а _(1,1) ) – 2 единицы/схему;

• •    двухосных крытых вагонов ( а _(2,1) ) – 1 единица/схему;

• •    четырехосных платформ ( а _(4,1) )– 4 единицы/схему;

для одной схемы погрузки 2-го типа ( j = 1):

• •    четырехосных крытых вагонов ( а _(1,2) ) – 2 единицы/схему;

• •    двухосных крытых вагонов ( а _(2,2) ) – 2 единицы/схему;

• •    двухосных платформ ( а _(3,1) ) – 4 единицы/схему.

Расчетная загрузка железнодорожного подвижного состава в зависимости от типа схемы погрузки составляет:

• •    для 1-го типа ( j = 1) C ₍₁₎ = 200 т/схему;

• •    для 2-го типа( j = 2) C ₍₂₎ = 300 т/схему.

2. Клетка нулевой строки и нулевого столбца не заполняется.

Симплексная таблица приведена на Рисунке 1.