Электрическая модель транспортной задачи

Часть 1. Опорный план

Идея использовать электрические цепи при решении транспортной задачи (в дальнейшем ТрЗ) появилась, когда узнал, чем на кафедре программирования мучают студентов. Было это лет 10 – 15 тому. Ход мысли (человека знакомого с электротехникой). Пути? Даже из наименования совершенно ясно, что это цепочки между производителями и потребителями. В простейшем случае – на основе резисторов, сопротивления которых должны соответствовать стоимости транспортировки Сij единицы товара по дороге между i–тым производителем и j–тым
потребителем. Не очень долго пришлось задуматься над типом источников. Помогло несколько вещей. Во-первых, формулировка исходных уравнений ТрЗ совпадает с первым законом Кирхгофа, который касается баланса входящих и выходящих из узла токов. Во-вторых, что же могло соответствовать решению задачи кроме значения тока? Его произведение на величину сопротивления резистора как раз и отразит (в вольтах) затраты на перевозку продукции по данной дороге. Источниками, величина тока которых не должна изменяться при подключении разных дорог (цепей с разными сопротивлениями резисторов), могли быть только «идеальные» источники тока. Вот и претенденты на модели производителей и потребителей.

Простота идеи позволила реализовать модель с первой попытки, но занимался ею в режиме «хобби». Ошибка состояла в том, что я видел основной результат использования модели в наглядности действий, выполняемых в соответствии с использованием известных алгоритмов решения ТрЗ. Ну, какой же преподаватель согласится с советом что-либо менять ради какой-то наглядности, да и видит ли он ее, привыкнув излагать по-своему.

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

И здесь возникает первая сложность, обусловленная вопросом: «А почему же об этом не додумались другие?» Поэтому я должен изложить свои представления о транспортной задаче, ее возможной электрической модели и возможных положительных результатах. Может быть в этом кроются ошибки приведшие к «излагаемому»? Тем, кому о ТрЗ все известно, советую часть материала пропустить, или, возможно, найти то, во что, в отместку за потраченное время, можно будет ткнуть меня носом. Также надо учесть, что не все об этой задаче знают. Потому немного потерпите, или пропустите начало, читая
«по диагонали».

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

Каждый производитель соединен дорогами со всеми потребителями. Поэтому общее количество неизвестных (объемы перевозок по каждой дороге) равно m * п, в то время как число исходных уравнений – m + п. В m уравнениях отражено равенство ресурсов производителя сумме перевозок по подсоединенным к нему дорогам, а в п – аналогичное равенство для каждого потребителя. Затраты на транспортировку всех грузов равны сумме произведений тарифа Сij на объем товара, перевозимого по этой дороге (т.е. на неизвестные Хij, которые необходимо определить при указанных выше условиях).

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

Про Ванг в программировании – не слышал. А Глобы пока специализируется на
предсказаниях (подсказках) оптимального поведения представителей знаков Зодиака
в разные календарные интервалы. И завлечь ее (или его) в программирование для
предсказания оптимального набора значений переменных вряд ли удастся. Поэтому
транспортная задача решается в два этапа. На первом, в результате анализа таблицы стоимости перевозок определяется набор и значения так называемых базисных неизвестных (алгоритмы северо-западного узла, минимальной стоимости, Фогеля и т.п.). Число базисных неизвестных должно быть на единицу меньше числа исходных уравнений. Их значения всегда можно проверить по исходным уравнениям.

Нахождение m + п – 1 базисных ведется на основе предположения, что перевозки по не базисным (свободным) дорогам не осуществляются, т.е. соответствующие им переменные равны нулю. Очевидно исходят из положения, что раз нет транспортировки по «свободной» дороге, то и нет и соответствующих расходов, к уменьшению которых стремятся в ТрЗ. Для дальнейшего отметим, что и в известных алгоритмах линейного программирования, которые используют при решении ТрЗ, свободные переменные также приравниваются нулю.

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

Изложение последующего материала проведем на примере решения конкретной задачи
сбалансированного типа: создадим оптимальный план перевозок продукции от трех
производителей (обозначим их А1, А2, А3) четырем потребителям (обозначим В1, В2, В3, В4). Показатели предложенной ТрЗ (объемы товара и тарифы транспортировки условной единицы товара по дорогам) представлены в таблицах рис. 1.

Рис. 1

Кто дочитал до этого места и, как я надеюсь, прочел и первый абзац, им совершенно ясно, что на рис. 2 изображена электрическая схема электрической модели, конечно же, только что сформулированной транспортной задачи, параметры которой представлены в таблицах А, Б и В рис. 1. (Уууф… Можно перевести дух.) Если «ясность» под сомнением, попробую убедить.

Значения токов источников стабильного тока рис. 2 (круглые элементы со стрелами, указывающими направление тока, значение которого проставлено рядом) сопоставьте с цифрами таблиц Б и В рис. 1. Можно увидеть, что вверху схемы расположены «электрические эквиваленты» производителей, внизу – потребителей. Источники производителей соединены с потребителями резистивными цепочками, величины сопротивлений которых совпадает с тарифами перевозки таблицы А. Выходы/входы источников тока подсоединены к длинным проводам, которые назовем шинами (наименование пригодится в дальнейшем, во второй части).

Дополнительно введены: заземления и амперметры. Надеюсь первое не надо объяснять. А без вторых (приборов) … Где же Вы увидите, сколько ампер протекает
по той или иной цепочке? Ох, извините, зарапортовался. Надо было сказать: «Где
же Вы увидите сколько условных единиц условной продукции транспортируется по
той или иной дороге?» И только цифру, полученную в модели, можно будет использовать в соответствующей части решения. Извините за излишнюю
назидательность.

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

Начнем с таблицы, отображающей полученный с помощью ЕМ полный набор решений неопределенной СЛАУ (рис. 2).

Табл. 1

Теперь надо придумать алгоритм «как из многого получить немножко», но значений
базисных переменных, тем более, что остальные (свободные) неизвестные можно
приравнять нулю. Применить географические углы и проч. можно, но это уже было опробовано. Какие только комплексные показатели я для этого изобретал. Страшно вспомнить. Помогло одно воспоминание и в благодарность человеку, их навеявшему, решаюсь на одно лирическое отступление.

Однажды, стоял на остановке, ожидая троллейбус, с М.В. Титаренко, преподававшим ТОЭ (теоретические основы электротехники). Он сказал: «Женя, (он был старше мены лет на 15), я некоторым студентам, принесшим решение задач, говорю: «Ток не дурак, чтобы идти по пути с большим сопротивлением. А ты посмотри, что у тебя.» Это ж надо было так составить задачки, чтобы столь ненавязчиво и безобидно указать (вернее оценить) ошибки решений!

Да и в предложенной электрической модели «ток не дурак». Это различные Омы с Кирхгофами заставляют его распространяться там, где ему не хочется. Так надо ему помочь. Как узнать, где не хочется? Да по его величине! Его заставляют, а он сопротивляется, уменьшается по величине. Как ему помочь? Да обнулить цепь с самым малым током, превративши его в свободную переменную! Для этого надо разомкнуть (разорвать) цепь (дорогу) с этим малым током. Потом также поступить и в следующем наборе решений, выдаваемом ЭМ после очередного разрыва цепи. И это делать до тех пор, пока не останутся m + п – 1 дорог, в которых будут протекать базисные токи, формирующие опорный план.

Так родился, на мой взгляд, почти идеальный для программирования алгоритм получения опорного плана. Я его назвал «Урезальным» от словосочетания «Урезать, так урезать». Самому не очень нравится (выдуманное наименование, а не словосочетание). Отдаю на конкурс, можно и то и другое менять.

Продемонстрируем этот алгоритм на примере нашей задачи.

Эту часть изложения (как, наверное, и только что написанное) проведу «в несколько развязном тоне», в форме диалога. Заранее прошу прощения за эту, надеюсь, последнюю в Части 1 вольность. Но как-то скучно одинаково комментировать шесть, по существу, однотипных действия над изменяющимися значениями токов в цепях модели рис. 2. Результаты вычислений, как обещал, буду представлять в таблицах, подобных табл. 1, в которых уберем словесные надписи.

Приступаю: — Ну, получили мы набор значений всех 12 неизвестных. И что из этого? Подумаешь, фокусник. Давай, базис! Кроме того, что же это такое? Неизвестная Х12 – отрицательная! (цифра «минус 4.8»)

– Извинюсь, программа, выполняющая расчет, «не знала», что ее, бедную, заставили «обслуживать» ТрЗ, в которой отрицательные значения не допустимы. Сейчас исправим. Обнулим эту переменную. (В электрической схеме модели разрывается цепь,
соединяющая первого производителя со вторым потребителем.)

Программа тут же прореагировала изменением значений и остальных неизвестных (сравните приведенные ниже значения с данными Табл. 1).

Табл. 2

– Правда, точности немного не хватило (правая колонка Табл. 2). А может быть обиделась, что обижаем меньшеньких? Проверим. Попробуем обнулить нового малыша – значение Х22. (в модели – разрыв цепи с резистором 5 Ом, значения токов – в табл. 3).

Табл. 3

– Смотрите, исправилась! А если еще? Ну, например, расправимся с «предмалышом» – Х31. (В табл. 3 есть еще меньшее число – 18,54).

Табл. 4

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

Табл. 5

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

Табл. 6

– Снова не все ладом. Но, раз пошла такая пья… ! Кто там следующий недоросток? Ааа…– Х34. (Трогать Х24 = 20 нельзя, т.к. он совместно с Х21 обеспечивает полный «вывоз» товара от второго Производителя, что является исходным требованием ТрЗ.)

Табл. 7

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

Изображение плана, полученного с помощью электрической модели и разработанного алгоритма, представлено на рис. 3. Общая сумма транспортных затрат этого базисного плана – 1350 условных единиц (к сожалению, не тех …).

Кажется, все. Подобьем некоторые итоги.

1.       В данной части описана электрическая модель (ЭМ), позволяющая получить полный набор решений (m * п) СЛАУ транспортной задачи.

2. Сформулирован алгоритм получения варианта базисного решения на основании полученного набора . Алгоритм заключается в последовательном разрыве цепей ЭМ, имитирующих дороги с минимальным током (обнулении цепей модели, по которым идет наименьший ток). По моему небольшому опыту, получаемое базисное решение по эффективности последующего поиска оптимума не уступает алгоритму минимальной стоимости (если не превосходит его).

Ну, не может все быть хорошо! Где недостатки?

Основной недостаток предложенного алгоритма решения ТрЗ связан с быстрым ростом числа свободных членов решения СЛАУ в задачах большой размерности. Их число (т –1)(п — 1). Например, для задачи 10 х 10 их 81, а 20 х 20 – 361. Причем, не только столько же раз необходимо выполнить команду обнуления, но и столько же раз произвести расчет электрической схемы.

Несколько аргументов в защиту:

1.  Электрическая схема модели достаточно простая, регулярная, что позволяет надеяться на разработку специальных упрощенных методов ее расчета. Некоторые идеи в этом направлении есть. Даже первый взгляд на предложенную электрическую модель указывает на то, что основную часть расчета можно выполнить на основе метода «узловых потенциалов», которых при указанных выше размерностях ТрЗ будет не больше 20 или 40 соответственно.

2. Если сравнить шесть наименьших значений тока в перечне начальных токов (табл. 1) с конечным расположением свободных членов (разомкнутых цепей) в окончательном опорном плане (табл. 7), то мы увидим, практически, их полное совпадение. Кроме ячейки Х24, обнуление которой не было произведено в связи с тем, что это нарушало бы один из постулатов решения ТрЗ (см. абзац перед табл. 7). Если бы режим проверки
постулатов ТрЗ был бы «железным», не зависящим от числа обнуляемых цепей,
то выход на опорный план можно было выполнить за одну «многоуровневую»
обнуляющую итерацию. Но, по крайней мере, первые три обнуления можно провести
одновременно на основе первичных данных, что сократило на два количество расчетов токов модели. Небольшой опыт показывает, что для задач большой размерности, обнуление на начальных этапах можно проводить одновременно на 2 – 3 дорогах, что значительно уменьшит количество расчетов ЭМ.

Сведение несбалансированного (открытого) варианта исходных данных к только что рассмотренному сбалансированному осуществляется на основе известных подходов. В электрическую модель вводится дополнительный либо Потребитель (в случае излишек товара), либо Производитель (в случае нехватки товара). Дополнительный источник стабильного тока подсоединяется ко всем производителям в первом варианте, либо к потребителям – во втором. Так как транспортировка товара по этим цепям должна быть без затрат, то резисторы в них отсутствуют. Величина тока вводимого дополнительного источника соответствует величине дисбаланса. Примеры таких моделей при дисбалансе в 20 усл. ед. товара приведены ниже: рис. 4 – при излишке, рис. 5 – при нехватке товара.

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

во-первых, имеются стандартные, «промышленно» выпускаемые программы по расчету
электрических цепей и расчету транспортной задачи, что она (ТрЗ), очевидно, заслуживает. Подтверждение последнего – введение ее в программный комплекс Excel;

во-вторых, автор, хотя и обращается к программистам, сам в этом деле профан – не может ни написать программу, ни внедриться в существующие, чтобы продемонстрировать предлагаемую связку: ЭМ – решение ТрЗ.

Поэтому приходится удовлетворяться картинками (рисунками), сопровождаемыми словесами. Извините (оправдание – см. вторая часть во-вторых). Но, если кого-нибудь
заинтересовался, и он захочет что-то повторить, проверить, или, дай Бог, посмотреть, а нельзя ли внедрить электрические цепи в свои программные задачи, то для них привожу дополнительные сведения.

Приведенные здесь результаты по электрическим цепям были получены, с помощью программы Electronics Workbench (EWB512). Ее основной недостаток для формирования изображения электрической модели ТрЗ присущ всем программам, выполняющим расчет электрических схем – это горизонтально-вертикальное расположение элементов и соединительных линий. Так «читабельнее» выглядят чертежи электрических схем, для которых программы ведут расчет. Попробуйте провести в них под углом какую-нибудь
соединительную линию. Программа тут же трансформирует ее в
горизонтально-вертикальные отрезки. В EWB это дополняется вытянутым горизонтальным начертанием амперметров, изображения которых занимают
значительную площадь экрана. Это привело к ограничению размерности рассмотренных ТрЗ (до 4 * 6). Рисунки для задач большей размерности просто не умещались на экране компьютера, либо необходимо было пользоваться лупой для чтения цифр (в связи с уменьшением масштаба). Дополнительный дефект – несоответствие изображений элементов ГОСТам, но, надеюсь, они понятны.

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

Более серьезным при использовании программы расчета электрических цепей для создания предлагаемой модели является выбор системы единиц при задании параметров компонентов. Обусловлено это тем, что в ТрЗ мы оперируем условными единицами продукта (изделий, денег и т.п.), а в электрической модели – амперами, вольтами, омами, между которыми существуют заданные физическими законами соотношения. В связи с этим, напоминаю, что из модели в ТрЗ для дальнейшего использования переносятся только численные значения полученных результатов (на данном этапе – значения тока). Но, если величина сопротивлений будет задана в кило омах, то ток в цепях будет 1000 раз меньше, чем при использовании «омного» диапазона. Остерегайтесь также «залезть» в сотни-тысячи кило Ом. Они становятся соизмеримыми с внутренними сопротивлениями источников тока и вольтметров, введение которых Вам может понадобится.

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

Одним из наиболее частых указаний, которое необходимо реализовывать в ТрЗ является: «Обнуление транспортного потока» (прекращение транспортировки груза по определенной дороге). В электрических схемах, вариантом которых является предлагаемая модель, это легко выполнить путем размыкания цепи. Для этого в каждую резисторную цепь (дорогу) можно ввести выключатели. Но, на всех рисунках модели они отсутствуют (занимают много места). В программе EWB разрыв цепи обеспечивается путем выделения и последующего удаления соединительной линии (см. рисунки). При необходимости – соединение (линия) восстанавливается.

И последнее «лирическое» отступление.

Как уже указывалось, вышеприведенная модель была создана сравнительно давно в результате «спилкування» с программистами. Попытки заинтересовать их не увенчались успехом, т.к. тогда я пытался привлечь их тем, что использование модели увеличивает наглядность применения стандартных алгоритмов. «Урезальный» алгоритм был найден недавно, поэтому не знаю, как он был бы тогда (и будет сейчас) воспринят. Но в наглядности работы с электрической схемой я и сейчас убежден. Попробую это продемонстрировать.

На рис. 6 приведено изображение электрической модели, если к ней, после обнуления цепи с отрицательным током (табл. 1), последовательно применить алгоритмы северо-западного угла, а, затем, – минимальной стоимости. Обычно при решении ТрЗ от начала и до конца применяют один из этих алгоритмов.

Северо-западный угол. Это проблема обеспечения первого потребителя. Ему надо 120 единиц продукции. Такие объемы может обеспечить любой из трех производителей. Наиболее дешевый «подвоз» может быть организован по дороге с тарифом 4 ус. единицы (цепь с 4-х омным резистором). Поэтому эта цепь сохраняется, а две соседние – разрываются (потоки грузов по ним обнуляются: Х11 = 0, Х31 = 0).

Наименьшая стоимость перевозки. Это цепь (дорога) с резистором в 1 Ом между первым производителем и третьим получателем. Ее и оставляем. Но первый производитель «вырабатывает» всего 160 единиц продукции, а получателю надо 190. Поэтому остаются также и другие пути к третьему потребителю (надо же кому-то подвести еще 30 единиц продукции). А вот пути поставок от первого производителя другим потребителям разрываются (ресурс первого производителя полностью поглотил
третий получатель).

В результате указанных действий получаем схему рис. 6. Если, как Вы теперь знаете, обнулить пути (разорвать цепи) с отрицательными токами, то можно выйти на иной (по сравнению с ранее рассмотренным – табл. 7) набор базисных переменных. Он, правда, характеризуется более значительными затратами (1530 усл. ед.). После процесса первой же оптимизации получилось бы базисное распределение, представленное в табл. 7, к которому пришли в результате предложенного «урезального» алгоритма.

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

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