Алгоритм решения задачи линейного программирования на основе симплекс-метода
Автор: Божко Л.М., Дергачев А.И., Дергачев С.А.
Рубрика: Информатика и вычислительная техника
Статья в выпуске: 4, 2024 года.
Бесплатный доступ
В статье рассматриваются этапы разработки алгоритма решения управленческой задачи с использованием симплекс-метода и результаты решения задачи по данному алгоритму. Задачи, решаемые с применением электронно-вычислительных машин, зачастую требуют наиболее полного учета нескольких целей. Необходимость разработки алгоритма задачи линейного программирования обоснована тем, что в ней, наряду с записью выполняемых действий, определяются логические связи для достижения поставленных целей. Предписанием для ЭВМ является программа, составленная на основе предложенной схемы алгоритма решения задачи. Преимуществом предложенного алгоритма является то, что он позволяет получать оптимальные решения как на этапе планирования, так и в ходе оперативного управления и впоследствии дает возможность оценить эффективность деятельности организаций с позиции системного подхода. Разработанный алгоритм может быть использован при постановке задач для их последующего решения на ЭВМ.
Математическая модель, математическое моделирование, линейное программирование, симплекс-метод
Короткий адрес: https://sciup.org/148330269
IDR: 148330269 | DOI: 10.18137/RNU.V9187.24.04.P.79
Текст научной статьи Алгоритм решения задачи линейного программирования на основе симплекс-метода
В данной статье в качестве образца разработки алгоритма решения задачи (подготовки к решению на ЭВМ) выбрана задача линейного программирования. Линейное программирование находит применение во многих сферах, в том числе в подготовке управленческих решений при управлении организацией. Решение задачи линейного программирования позволяет найти оптимальный (наилучший) вариант использования имеющихся в распоряжении хозяйствующего субъекта ограниченных ресурсов.
Задачи линейного программирования могут быть решены разными методами: с помощью апекс-метода – новой версии итерационного метода [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 (1) = 200 т/схему;
-
• для 2-го типа( j = 2) C (2) = 300 т/схему.
2. Клетка нулевой строки и нулевого столбца не заполняется.
Симплексная таблица приведена на Рисунке 1.
] jV Нулевая! |
0 |
1 |
1 |
П |
п+1 |
п+2 |
п+т |
п+т+1 |
|||
строка Г 0 |
С,ц |
О:, |
С 1П> |
0 |
0 |
0 |
0 |
Значение |
|||
1 |
п+1 |
«11.1) |
Al J) |
«41л» |
о |
0 |
^(т |
целевой с функции |
|||
2 |
п+2 |
Alii) |
0|И |
«4 2л» |
0 |
1 |
0 |
Ла, |
|||
— |
тт: |
||||||||||
ш |
п+т |
«(m.h |
«1тД» |
«4тл» |
() |
0 |
1 |
^Щ| |
|||
Индексы базисных неизвестных |
Столбец свободных членов системы ограничении (значение базисных неизвестных) |
Список литературы Алгоритм решения задачи линейного программирования на основе симплекс-метода
- Соколинский Л.Б., Соколинская И.М. О новой версии апекс-метода для решения задач линейного программирования // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2023. Т. 12. № 2. С. 5-46. DOI: 10.14529/cmse230201 EDN: QKTRMC
- Бахтиярова О.Н., Птицына И.В., Подзорова М.И. Применение геометрического метода для решения задач линейного программирования в курсе дисциплин "Исследование операций" и "Методы оптимизации" // Modern European Research. 2024. Т. 1. № 1. С. 12-22. EDN: GVVUZQ
- Ольховский Н.А. Исследование нейросетевого метода решения задач линейного программирования // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2023. Т. 12. № 4. С. 55-75. DOI: 10.14529/cmse230402 EDN: AQKNZA
- Усатюк В.С., Егоров С.И. Поиск треппин-сетов методом смешанного целочисленного линейного программирования с использованием априорного списка кодовых вершин // Известия Юго-Западного государственного университета. 2023. Т. 27. № 4. С. 79-97. DOI: 10.21869/2223-1560-2023-27-4-79-97 EDN: RFTGRE
- Полежаев С.В. Симплекс-метод: основные идеи // Современные информационно-коммуникационные технологии. 2022. № 12. С. 44-46. EDN: ESCQMQ
- Вихарев Н.А. Использование симплекс-метода для оптимизации переработки никеля с помощью цифрового двойника // Ceteris Paribus. 2022. № 12. С. 9-11. EDN: UPTZPD
- Султанов А.Т. Применение симплекс-метода для решения задач инженерной оптимизации // Уральский научный вестник. 2023. Т. 10. № 7. С. 8-15. EDN: YXTKNL
- Галкин В. А., Кузина Е.Л., Кузина М.А., Василенко Е.А. Применение симплекс-метода в повышении экологичности производства на транспортных предприятиях // Качество. Инновации. Образование. 2024. № 1 (189). С. 26-33. DOI: 10.31145/1999-513x-2024-1-26-33 EDN: AFVYFG
- Смагин Б.И., Машин В.В. Критический анализ решения задачи целочисленного линейного программирования методом Гомори // Наука и Образование. 2022. Т. 5. № 1. EDN: OPXXSH
- Божко Л.М., Дергачев А.И., Дергачев С.А. Математическая модель решения задачи линейного программирования с помощью симплекс-метода // Вестник Российского нового университета. Серия: Сложные системы: модели, анализ и управление. 2024. № 3. С. 3-15. DOI: 10.18137/RNU.V9187.24.03.P.3 EDN: ZJJGFQ