Получаем и используем полный набор решений неопределенного СЛАУ. На примере транспортной задачи

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.

По специальности я инженер-электронщик. Работал в НИИ в Подмосковье. По возвращению в Украину преподавал на кафедре «Автоматика и телемеханика».

Я не встречал методов нахождения полного набора всех неизвестных неопределенной СЛАУ, классическим образцом которой является транспортная задача. Алгоритмы нахождения только части неизвестных (названных базовыми) являются одними из основ линейного программирования. Поэтому статья может вызвать интерес как у математиков (Высшая математика/Абстрактная алгебра) так и у программистов, разрабатывающих программы решения различных оптимизационных задач.

Известно, что система линейных алгебраических уравнений (СЛАУ) при количестве неизвестных большем, чем число уравнений, имеет бесконечное множество решений. Наверное, потому ее назвали неопределенной, так как надеяться на угадывание хотя бы одного варианта решения маловероятно.

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

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

Подобная ситуация характерна для так называемой транспортной задачи (ТрЗ), которая является одной из основных задач линейного программирования. В ней решается проблема создания такого плана перевозки грузов от т источников (предприятий, складов и т. п.) п потребителям (например, магазинам), чтобы затраты, на перевозку были минимальными. Для этого приводится таблица размерностью т х п стоимости перевозки единицы продукции от i-того производителя j-тому потребителю (С_ij). Обычно таблица дополняется столбцом, в котором указывают ресурс производителя, и строкой — потребность получателя.

Каждый производитель соединен со всеми потребителями. Поэтому количество неизвестных равно т х п, в то время как число уравнений — т + п. В т уравнениях отражено равенство ресурсов производителя сумме перевозок по подсоединенным к нему дорогам, а в п — аналогичное равенство для каждого потребителя. Общие затраты на транспортировку всех грузов равны сумме произведений С_ij на объем товара, перевозимого по этой дороге (неизвестная Х_ij). Нахождение т + п — 1 базовых неизвестных ведется на основе предположения, что перевозки по не базовым дорогам не осуществляются, т. е. соответствующие им переменные равны нулю.

Получить один из бесчисленного множества вариантов решения ТрЗ мне удалось довольно давно, лет 10 — 15 тому. Использовалась при этом обычная компьютерная программа, которую, или ей подобные, применяют даже в школе. Попытки заинтересовать программистов (от которых я узнал о ТрЗ и алгоритмах ее решения) не увенчались успехом. Исходное решение так же легко видоизменялось при вносимых изменениях.

Не будучи профессиональным математиком, полез в изучение математических основ СЛАУ. Наконец наткнулся на формулировку, как проверить являются ли полученные значения решением исходных уравнений (оказывается просто: подставь и получи тождество). Да я же все время это делал и получал! Все это сподвигло меня на данное послание.

Постановка транспортной задачи

Три производителя, четыре потребителя. В табл. А рис. 1 приведены значения стоимости перевозки единицы продукции от i-того производителя j-тому потребителю, в табл. Б — ресурсы производителей, табл. В — потребности получателей.

Результаты определения всех 12-ти неизвестных — табл. А рис. 2. В табл. Б и В рис. 2 — значения сумм по строкам и столбцам табл. А, т.е. данные проверки, подтверждающие истинность приведенных значений неизвестных.

Но что же это такое? Неизвестное Х₁₂ — отрицательное?! Но прошу извинения,: программа, выполняющая расчет, «не знала», что ее, бедную, заставили «обслуживать» ТрЗ. Сейчас исправим. Обнулим эту переменную! Программа тут же прореагировала изменением значений и остальных неизвестных (см. рис.3).

Правда, точности немного не хватило (табл. Б). А может быть обиделась, что обижаем меньшеньких? Проверим, попробуем обнулить нового малыша — значение Х₂₂.

Смотрите, исправилась! А если еще? Ну, например, расправимся с предмалышом Х₁₃.

Опять обиды. Хотя только по вертикальным суммам (таблица В). Все-таки, продолжим. Следующий «недомерок» Х₃₂. Обнулим.

Опять вылезло это Х₁₁. Может быть, из-за него неточности в пятом знаке некоторых сумм? Сейчас выясним. Кто там малыш? А, — Х₁₁. Обнулим.

Опять не все ладом! Но раз пошла такая пья... ! Кто там следующий недоросток? А — Х₃₄!

Похоже, исправились! С чего бы это? Да ведь, смотри, мы вышли на шесть базисных неизвестных, для получения которых программистами придуманы оригинальнейшие алгоритмы, которые я до конца не смог освоить (основная работа мешала).

Общая сумма затрат — 1530 условных единиц (к сожалению не тех ...). Методом потенциалов затраты были уменьшены до 1170. Кстати, Вы заметили, что получен достаточно простой алгоритм нахождения базового решения: режь, вернее, обнуляй «мелочь пузатую».

Приведем еще несколько решений для более сложной ТрЗ. Исходная матрица 4×6, рис. 9.

Результаты исходного решения — на рис 10, один из промежуточных — рис.11, базовое — рис. 12.

Базовое решение, к сожалению, получилось вырожденным — всего семь элементов, вместо рекламируемых 9 (6+4-1= 9). Хотя говорят (?) о допустимой «вырожденности» — иметь на 1 меньше. А здесь — аж на два. Но подстановка полученных значений в исходные выражения СЛАУ (результаты в табл. Б и В) показывают, что и этот «нонсенс» является решением. Может быть, надо поменять понятие определения правильности решения?

Более сложными ТрЗ (чем 4×6) не занимался. Рисунки, которые приходится создавать в расчетной программе, в этом случае не умещаются на экране, либо придется пользоваться лупой для чтения цифр. Ни то, ни другое делать не хочется. Усовершенствовать или создать новую программу расчета — скорей всего не сумею или не успею.

Заключение

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

К сожалению, попытка получить соответствующие математические выражения для нахождения неизвестных у меня, на мой взгляд, была неудачной, т. к. они (выражения) получались очень громоздкими (некоторые занимали значительную часть листа формата А4). Ноутбук же их (или что-нибудь подобное) при использовании известных программ щелкал как орехи.

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

Представьте, например, только что преподнесенную задачу 4×6. Это 24 числа. Любое изменение (например, обнуление) заставляет вновь переписать новое решение. Опять 24 числа. До базового решения 24-9 = 15 «перезаписей». А, если списывая, ошибся, или клюнет какая-то «мысля», заставляющая что-то еще попробовать, изменить?

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

Если заинтересуетесь и предложите что-то дельное, поделюсь и остальным. Хотя, может и сами додумаетесь, намеков и подталкивания сделано предостаточно.