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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

👍НравитсяПонравилось2
В избранноеВ избранном0
LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Якщо говорити про загальний випадок розв’язування невизначених СЛАР, то все уже знайдено до нас)) Складається враження про недостанє розуміння понять лінійної алгебри автором.
Загальний розв’язок невизначеної сумісної СЛАР (з якого легко отримати частинні розв’язки просто підставляючи довільні значення замість вільних змінних) знаходиться методом Жордана-Гауса, наприклад. Кількість базисних змінних залежить від рангу матриці системи і вона далеко не завжди на 1 менша від кількості рівнянь, у загальному випадку. Вільні ж змінні (не базисні) можна приймати будь-якими (не тільки нулями) для отримання одного конкретного частинного розв’язку. Таким чином, при наявності загального розв’язку можна виписати скільки душі завгодно наборів значень усіх невідомих, що будуть задовольняти систему.
У транспортній задачі автор, схоже, обнуляє в запропонованому методі певні змінні з найменшими коефіцієнтами, автоматично відносячи їх в розряд вільних (?). Точність страждає через округлення в програмі, що використовується. Чи цей метод оптимальний для пошуку опорного рішення транспортної задачі і чи працює він завжди, питання відкрите.

Что-то вроде PCA изобрел, нет ?

Це NP-повна задача. З ростом кількості змінних можна знаходити лише приблизні рішення. Для цього є всілякі solvers.
Ці проблеми вирішуються наприклад в edunav(розрахунок навчального плану на багато років вперед з варіативними частинами) та curriosio (цікаві туристичні маршути)

Вы что-то путаете. Транспортная задача очень даже P-задача, так как она решается линейным программированием. А для ЛП есть множество полиномиальных алгоритмов (ну, может, и не множество, но пара штук уж точно найдется).

Наче на курсі лінійки вчать таке вирішувати. Там якесь ядро рахують, чи шо. От тут пишуть, наприклад: discourse.julialang.org/...​em-general-solution/37865 Ой, забула бабка... Мені здається зараз прийде, хто ще не забув і розкаже)

А почему северо-западный угол не зашел и метод избавления от вырожденности, а дальше методом потенциалов? Первое из инета — matecos.ru/...​chi-kak-izbavitsya-2.html

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

Если при этом придётся пожертвовать вычислительной мощностью — говно вопрос, надо жертвовать, даже если переплата будет тысячекратной. Иначе цена ошибки (в том числе намеренной) начисто перечёркивает практическую ценность алгоритмов, оставляя за собой патовую ситуацию: у теоретиков вроде всё решено (и закрыт путь новым решения, ибо лучшее враг хорошего), у практиков — ничего не работает, потому что теоретики не касались практики и попросту выкинули «неправильные» условия из задачи.

Мы в 21 веке, привыкай, что даже если работаешь с нейросетью — всё равно закладывай цену ошибки, не считай сами шаги решения бесплатными.

Типичнейший пример: есть массив из N целых элементов по адресу X, нужно записать в і-тый элемент (нумерация с нулевого) значение. «Правильное» решение — тупо записать по адресу Х+i. Но цена ошибки этого «правильного» решения такова, что в десятилетиями проверенных программах до сих пор находят критические уязвимости, позволяющие получить контроль над операционной системой, тупо записав данные за границы массива. «Неправильные» же языки программирования тратят туеву хучу времени на проверку наличия самого массива, на допустимость туда записи, на выход за его границы. Но выигрывают за счёт радикально меньшего числа ошибок, и как следствие, могут похвастать дешевизной качественного прикладного кода. Хотя есть достаточно такого кода, который реально нужно оптимизировать по ресурсу, но цена на такие разработки смущает даже очень не бедных людей.

Так алгоритмическая сложность «записать в массив с валидацией» почти всегда такая же, как алгоритмическая сложность «записать в массив без валидации».

нет, не ключевое. ну либо вы не понимаете значение термина «_алгоритмическая_ сложность»

Я не понимаю апелляции к этому абстрактному понятию.

Окей, напишу попроще. Ваш абзац про массив тупо не в тему и к алгоритмам тупо не имеет отношения как таковой.

В теории, между практикой и теорией нет разницы. На практике есть.
К алгоритмам отношение имеет всё. А то что это не касается отдельного аспекта теории, который ты знаешь — так мой коммент как раз об этом.

Только в теории можно исключить из рассмотрения часть условий ради упрощения ОБЪЯСНЕНИЯ самой теории, чтобы её легче было понять. Но когда дело касается ПРИМЕНЕНИЯ теории — упрощение играет злую шутку С ЛЮДЬМИ, формируя порог вхождения, множась на эффект Даннинга-Крюгера: вызубрившие теорию отбрасывают практические задачи лишь за то, что они не соответствуют теории. А практики — не могут применить теоретиков только потому, что они не теоретики сами, а потому их тупо пошлют с их «неправильным» взглядом.

Конкретно в твоём случае: абстрактное понятие «сложность алгоритма» позволяет увидеть ошибочные (или не всегда оптимальные) пути, которые при линейном усложнении задачи дают нелинейно возрастающую сложность, и по крайней мере сравнивать эти алгоритмы. Однако уверовавшие во всесильность этого критерия будут начисто игнорировать КОНСТАНТНЫЕ факторы, когда требовательность к ресурсам возрастает В РАЗЫ, но линейно в ответ на рост объёма условия.

Так что добро пожаловать в реальность.
PS. А работу сборщика мусора твоя теория вообще забывает. А там ведь нифига не линейный рост возможен. И есть случаи, когда деструкторы нужно писать руками, чтобы простенькие задачки не становились адищем, когда объёмы данных идут на десятки миллионов объектов.

Простите, а что значит константа возрастает линейно в ответ на рост объема условий? что такое «объем условий»?

Подписаться на комментарии