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

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

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

Цель данного исследования – разработка алгоритма решения задачи линейного программирования с использованием симплекс-метода, что способствовало бы принятию оптимального решения при ограниченных ресурсах. Симплекс-метод находит широкое применение, в том числе для задач оптимизации [5–8]. Помимо преимуществ по сравнению с другими методами (например, методом Гомори [9]), выбор симплекс-метода связан с его использованием при разработке математической модели решения задачи линейного программирования [10] и в алгоритме решения такой задачи [11]. Так, была составлена укрупненная (принципиальная) схема алгоритма симплекс-метода [11, с. 86].

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

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

Анализ схем алгоритмов подзадач [10] показал, что эти схемы, во-первых, выполняют чётко ограниченные функции, во-вторых, позволяют составить на их основе программные модули.

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

WDZSIT – «Ввод данных и заполнение симплексной таблицы»;

WKS – «Выбор ключевого столбца»;

PWSTR – «Поиск ведущей строки»;

PESIT – «Пересчёт симплексной таблицы»;

FWPWD – «Формирование и выдача на печать выходного документа».

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

Основная часть. Формирование выходного документа

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

Для формирования выходного документа используются схемы алгоритмов всех предыдущих подзадач [10], в которых определена логика вычислительных процессов и использованы формулы вычисления значений величин, указанных в макете выходного документа. Расположение выдаваемых на печать выходных данных определяется также макетом выходного документа.

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

Анализ величин, указанных в макете выходного документа, и тех величин, значения которых определяются в четырех сконструированных схемах алгоритмов, показывает, что в этих схемах алгоритмов не определялись значения величин F , Н , X и S [11], поэтому вычисление этих величин включено в схему алгоритма подзадачи 5 (графический символ номер 11) с использованием (см. Рисунок 2):

Вестник Российского нового университета

Серия «Сложные системы: модели, анализ и управление». 2025. № 4

• а)    формулы F = – S _(n+m+1) (т. е. знания того, что оптимальное значение целевой функции F с обратным знаком находится в клетке итоговой симплексной таблицы с координатами 0, ( n + m + 1);

• б)    формулы (18) [10] (т. е. знания того, что индексы базисных неизвестных Х _(j) находятся в нулевом столбце ( j = 0) в строках с 1-й по m (<>), а их значения – в соответствующих строках последнего столбца ( j = n + m + 1);

• в)    формулы (18) [10] (т. е. знания того, что свободные неизвестные Х _(j) равны нулю);

• г)    формулы (19) [10], позволяющей получить значения элементов вектора Н ;

• д)    значений величин, полученных в процессе вычислений и размещённых в памяти ЭВМ в виде итоговой симплексной таблицы S с оптимальным планом.

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

Ком-

_ мен-тар ий

К следующей _ странице

Обнуление векто-

Ком-мен-таоий

Содержание комментариев

Комментарий 1. Определение значения очередного индекса b элемента вектора X. В символе 2 обнуляются все элементы (как базисных, так и свободных неизвестных) вектора X (его полная запись ____), а в символе 5 индексам b присваиваются значения только индексов базисных ( 'Х')Ь=1,п+т неизвестных.

Комментарий 2. Определение значения очередного элемента Х(ь_} (являющегося базисным неизвестным) вектора X (значения свободных неизвестных остаются нулевыми - эти значения свободным неизвестным были присвоены в символе 2).

Рисунок 2. Схема алгоритма подзадачи 5 «Формирование и выдача на печать выходного документа»

Вестник Российского нового университета

Серия «Сложные системы: модели, анализ и управление». 2025. № 4

Рисунок 2. Продолжение, начало на с. 15

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

Из предыдущей страницы

К следую щ е й странице

Начало 2-й части вы ходых данных - печать итоговой симплексной таблицы и L.