Сущность методов оптимизации

В ТЕХНОЛОГИИ, ОРГАНИЗАЦИИ И УПРАВЛЕНИИ

АВТОМОБИЛЬНЫМИ ПЕРЕВОЗКАМИ

Повышение эффективности автомобильных перевозок грузов связано с применением методов классической и современной математики для решения прикладных задач. По своему характеру все решаемые на транспорте задачи можно разделить на три группы: разработка тех­нологических процессов перевозки грузов; оперативное управление пере­возочным процессом; учет и статистика.

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

Человеческий ум обладает огромными достоинствами по сравнению с любой машиной. Благодаря интуиции была решена «проблема комми­вояжера». Эта известная математическая проблема, долго ставившая в тупик математиков, в одном из вариантов формулировалась так: комми­вояжер, выезжая из Вашингтона, должен посетить 48 главных городов штатов и вернуться в Вашингтон по кратчайшему пути. Число возмож­ных маршрутов составляет 10⁶². Сотрудники института РЭНД (США) с помощью булавок и ниток и своей интуиции открыли кратчайший мар­шрут, способствовали возникновению и развитию методов динамическо­го программирования.

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

Рассмотрим несколько примеров применения математических ме­тодов при разработке технологических проектов перевозки грузов.

Задача 8.1. Однородный груз в количестве 400 т находится на двух складах. На складе № 1 находится 250 т груза и на складе № 2 - 150 т. Груз необходимо перевезти двум потребителям. Потребителю А требует­ся 250 т и потребителю В - 150 т (рис. 8.1). В такой ситуации возникает желание отправить груз со склада № 1 потребителю А, а со склада №2 - потребителю В. Из рис. 8.1, видно, что такое решение приведет к выпол­нению транспортной работы в объеме

 

Если потребителю В отправить груз из ближайшего склада № 1, а по­требителю А перевезти оставшиеся 100 т, а остальные 150 т со склада № 2, то транспортная работа составит

150-5 + 100-15 + 150-5 = 3000 ткм.

В случае, когда потребителю В направить со склада № 1 - 50 т и со склада Лг 2 - 100 т, а оставшиеся грузы направить потребителю А, транспортная работа составит

50-5+ 100 10 + 50-5+ 200-15 = 4500 т-км.

Таких вариантов можно составить очень много. Будет ли второй ва­риант лучшим? Для того чтобы ответить на этот вопрос, необходимо ли­бо пересчитать все варианты, либо применить математические методы.

Обозначим количества груза, направляемого со склада № 1 потреби­телю В, через X. Тогда потребителю А с этого склада будет перевезено 250 - X. Потребителю В этом случае со склада № 2 будет перевезено 150 - X, а потребителю А - остальной груз в количестве X. Придавая X различные значения от 0 до 150, мы получим различные варианты реше­ний. Математическая модель для решения этой задачи будет иметь вид:

или

Из формулы (8.1.) видно, что лучший вариант решения будет в том случае, когда Сбудет иметь наибольшее значение, т. е. 150.

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

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

где: С_э - стоимость машино-часа экскаватора, руб./ч;

С_а - стоимость автомобиле-часа, руб./ч;

λ - интенсивность входящего потока автомобилей;

А_э - число автомобилей, работающих с экскаватором;

μ₀ - интенсивность обслуживания;

ρ - приведенная плотность потока автомобилей;

D{t₀) - дисперсия времени обслуживания, ч.

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

где: (x₁, х₂,..., х_п) - независимые переменные, сводится к решению сис­темы из уравнений, полученной приравниванием ча­стных производных к нулю

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

Решение задач методами линейного программирования связа­но с разработкой математической модели. Понятие модель в на­стоящее время одно из самых популярных. А. И. Ракитов дает сле­дующее определение модели. Объект А будем называть моделью объ­екта 5, если А является объектом - заместителем по отношению к В и если А в некотором отношении проще, удобнее, компактнее или обла­дает иными преимуществами по отношению к В и, кроме того, суще­ствует такая зависимость между А и В, что, манипулируя А, мы полу­чаем знания, которые могут быть непосредственно или с некоторыми поправками отнесены к В.

Физическая модель с давних пор используется для эксперимента, для проверки разнообразных идей. Экономические явления столь сложны, столь многофакторны, что их практическая проверка бывает трудно осуще­ствима. И здесь используются экономико-математические модели.

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

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

имеет единственное решение X₁ = 1, Х₂ = 2.

Уравнение Х₁+2Х₂=10                                                        (8.6)

имеет бесчисленное множество решений:

Если переменные будут принимать только не отрицательные зна­чения, т. е. Х₁≥ 0 и Х₂ ≥ 0, то

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

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

имеет три следующих решения:

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

Общая задача программирования связана с некоторыми целевыми ус­тановками, т. е. отысканием либо максимума, либо минимума целевой функции. Если в качестве целевой функции (модели) будет выражение

                          X₁ + X₂ + X₃,                                                (8.10)

то когда требуется обеспечить ее максимальное значение, из двух решений оптимальным будет Х₁ =21/5, Х₂ =0, Х₃ =8/5. Когда необходимо обеспечить минимальное значения целевой функции (8.10), то оптималь­ным будет вариант X₁ = 0, Х₂ = 3, Х₃ =1.

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

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

ГРАФОАНАЛИТИЧЕСКИЙ МЕТОД

 

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

Сущность графоаналитического метода рассмотрим на решении сле­дующей задачи:

максимизировать функцию 10Х₁+13Х₂                                        (8.11)

при наличии ограничений

Решение задачи может быть найдено графически, как показано на рис. 8.2. Ограничения (8.12) и (8.13) на рис. 8.2 изображены прямыми ли­ниями как уравнения, полученные заменой неравенств на равенства. Площадь под каждой из двух прямых эквивалентна математической формулировке, имеющей направленный смысл «меньше, чем» (<). Так как X₁ и X₂ не могут принимать отрицательных значений, область до­пустимых значений переменных ограничивается осями координат. Таким образом, многоугольник ОABC содержит в себе область значений Х_х и Х₂, удовлетворяющих всем имеющимся ограничениям. Множество то­чек, принадлежащих области, ограниченной линиями ОАВС (вместе с граничными точками), называется множеством решений. Это множест­во является выпуклым, т. е. любой отрезок, соединяющий две произвольным образом выбранные точки данного множества, лежит внутри или проходит вдоль границы ОABC.

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

 

Изменяя степень достижения цели Z₀, получаем на рис. 8.2 семейст­во параллельных изолированных прямых, уравнение которых

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

Если в формуле для целевой функции (8.11) изменить коэффициенты при переменных (при этом угол наклона параллельных линий по отноше­нию к оси абсцисс также будет другим), то в результате точка, задающая оптимальное решение, может перемещаться. Если при наличии ограни­чений (8.12), (8.13), (8.14) целевая функция будет иметь вид

то в этом случае все точки, лежащие на отрезке АВ, будут являться опти­мальными (рис. 8.3). Решение X₁ = 0,95, Х₂=1,8 будет оптимальным. Однако оптимальным будет и решение X₁ = 0, Х₂ = 2. Оптимальное значение целевой функции будет равно 28,0.

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

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

 

при наличии ограничений:

то приходится пользоваться пространственной моделью.

Когда ограничения являются уравнениями, то каждое из них можно считать уравнением плоскости, лежащей в трехмерном пространстве, и точка, общая этим трем плоскостям, есть единственная точка, представ­ляющая собой допустимое решение (рис. 8.4, а). Если ограничения яв­ляются неравенствами, то область оптимальных решений образуют точки некоторого выпуклого многогранника, расположенного в первом октанте. Придавая переменной Z₀, формула (8.18), различные значения, по­лучим семейство параллельных изоцелевых плоскостей (см. рис. 8.4, а), при­чем большим значениям Z₀ будут соответствовать плоскости, располо­женные дальше от начала координат. Решение задачи дается координа­тами одной из вершин выпуклого многогранника допустимых решений.

 

Если вместо трех уравнений ограничений имеется лишь два, до­пустим, уравнения (8.19) и (8.20), то в этом случае областью допусти­мых решений окажется линия пересечения плоскостей, являющихся изо­бражениями уравнений ограничений (рис. 8.4, б). При одном уравнении ог­раничений областью допустимых решений будет являться треугольник, образованный линиями пересечения плоскости, изображающей это урав­нение, с плоскостями координат (рис. 8.4, в).

В случае, когда необходимо получить не максимум, а минимум функции, то многоугольник будет вогнутым.

Особенности решения задач графоаналитическим методом рас­смотрим на следующих примерах

Задача 8.3. От поставщика А груз перевозится автомобилями КаMA3-5320 двум потребителям B₁ и В₂ на расстояние 15 и 25 км соот­ветственно. При перевозке груза потребителю B₁ на одну ездку затрачи­вается 1,23 ч, а потребителю В₂ - 1,8 ч. Продолжительность работы ав­томобилей на линии -8 ч. Работая на маршруте В₁, водитель делает 6 ездок, затрачивая на это 7,38 ч рабочего времени. На маршруте В₂ во­дитель делает 4 ездки и затрачивает 7,2 ч рабочего времени. Требуется организовать работу так, чтобы максимально использовать рабочее время водителей.

Математическая модель запишется в следующем виде:

максимизировать

при наличии ограничения

где: X₁ - число ездок на маршруте В₁;

Х₂ - число ездок на маршруте В₂.

 

Решение может быть найдено графически, как показано на рис. 8.5. При X1 = 0, Х2 = 4,4. При Х2 = 0, X1 = 6,5. Соединив полученные точки А и В, получим область допустимых решений X, и Х2. Левые части уравнений целевой функции (8.22) и ограничения (8.23) совпадают. Это значит, что все точки, лежащие на линии 1,23Х1+1,8Х2=8.

будут оптимальными. Точки Q, С₂ и так далее, заключенные между прямой АВ и осями координат, имеющие координатами целые числа, изображают все возможные варианты работы автомобиля. Точки, которые ближе расположены к прямой или лежат на ней, дают наилучшие - оптимальные решения.

В рассматриваемом примере точки C₁ с координатами X₁=5 и Х₂ = 1 и С₄ с координатами X₁ = 2, Х₂ =3 ближе всех расположены к линии АВ. В первом случае продолжительность работы водителя на ли­нии составит

1,23-5 + 1,8*1 = 7,95 ч,

а во втором

1,23-2 + 1,8*3 = 7,86 ч.

Задача 8.4. Определить потребное число поддонов для перевозки грузов пакетами, упакованными в потребительскую тару двух размеров - А и В. Количество грузов в таре типа А составляет 600 единиц и типа В - 300 единиц. Количество тары, загружаемой на поддон различными спо­собами, приведено в табл. 8.1.

Таблица 8.1

Тип тары	Способы размещения тары на поддоне
	1	2	3	4
А	3	2	1	0
В	1	3	6	8

Математическая модель задачи будет сформулирована следующим образом:

минимизировать  Х_{ + Х₂ + Х₃ + Х₄ = Z₀,                    (8.24)

при наличии ограничений

где: X_i - число поддонов, загруженных по i-способу размещения тары.

Для решения задачи начертим прямоугольную систему координат АОВ (рис. 8.6) и каждому возможному способу размещения тары на под­доне поставим точку, координаты которой соответствуют числу соответ­ствующей тары, размещаемой на поддоне. Буквой С с индексом обозначим номер способа размещения тары на поддоне. Множество всевозможных планов размещения тары на поддоне изображается совокупностью точек выпуклого многоугольника С₁ С₂ С₄ С₃. Например, точки на отрезке С₁ С₂ будут указывать

своими координа­тами количество тары типа А и ти­па В, приходящейся на один под­дон в различных способах разме­щения их, сочетающих собой размещения по способу С1 и С2 (рис. 8.6). Из всех решений нас ин­тересует выполнение условия ком­плектности, т. е. отношение числа тары А к числу тары В. В соот­ветствии с заданием это соотно­шение равно 2 (600:300). Если из начала системы координат про­вести луч, координаты которого А= 2, В = 1, то оптимальным бу­дет план размещения тары на под­доне, которому соответствует точка, одновременно принадлежащая многоугольнику и лучу, и имеющая наи­большие координаты, т. е. соответствующая плану наибольшего исполь­зования площади поддонов. Такой точкой будет Р, лежащая на отрезке С1 С3. Это указывает на то, что оптимальный план размещения тары на поддонах представляет собой комбинацию размещения тары по способу C1 и С3.

Обозначим через δ долю поддонов, загружаемых по способу C₁, а остальную часть (l-δ) - по способу С₃, долю одного и другого способа размещения поддонов найдем из условия комплектности

Минимальное число поддонов Z₀ определится из уравнения

откуда Z₀ =212. Таким образом, по способу C₁ будет загружено 194 поддона и по способу С₃ - 18.

 

МЕТОД ПОТЕНЦИАЛОВ

 

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

Математическая модель классической транс­портной задачи в общем виде записывается в следующей форме:

минимизировать

при ограничениях

где: m - число поставщиков;

n - число потребителей;

Xij - объем перевозок между i и j пунктами;

S_i- - ограничения по предложению;

Di - ограничения по спросу;

a_ij - расстояние от пункта i до пункта j.

Условия задачи можно представить следующим образом. Каждый по­ставщик должен дать потребителям столько продукции, сколько у него есть, т. е.

Каждый потребитель должен получить столько, сколько ему требует­ся, т. е.

Необходимо найти такой вариант плана перевозок, чтобы транспорт­ная работа была минимальна, т.е.

Запись и решение транспортной задачи методом потенциалов вы­полняется в таблично-матричной форме. Совокупность всех элементов матрицы х_ij называется планом перевозок или распределением поставок. Элементы матрицы называются показателями критерия оптимальности.

В каждой конкретной транспортной задаче можно найти бесчислен­ное множество вариантов плана перевозок. План перевозок считается до­пустимым, если все возможности поставщиков используются, а спрос всех потребителей удовлетворяется. Такая модель транспортной задачи называется закрытой в силу сбалансированности спроса и предложения. Транспортная задача, в которой спрос не равен предложению, называется открытой моделью.

Если допустимый план удовлетворяет условию (8.34), то он является оптимальным. В условии (8.34) сформулирована цель задачи или ее целе­вая функция. При решении транспортной задачи в качестве целевой функции могут приниматься следующие показатели: минимум тонно-километрового пробега, минимум провозных плат, минимум эксплуата­ционных расходов, минимум тонно-часов транспортирования и др.

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

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

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

Критерий «минимум тонно-часов транспортирова­ния груза» (показатель критерия - время транспортирования) может применяться при перевозке скоропортящихся грузов, овощей, живности и другой продукции. К его недостаткам относится то, что он не учитывает затрат, связанных с транспортированием груза.

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

Чтобы задача имела допустимое решение, требуется, чтобы общие ресурсы поставщиков были не меньше общего спроса потребителей S_i ≥ Dj, а также естественным представляется и требование неотрица­тельности объема поставок и спроса, т. е. Si ≥ 0, Dj≥ 0.

Рассмотрим применение метода потенциалов на следующем примере:

Задача 8.5. Из трех грузообразующих пунктов A₁, А₂, А₃ необхо­димо перевезти однородный груз четырем потребителям B_l, В₂, B₃, B₄. Количество груза в пункте А₁ = 300 т, в пункте А₂ = 500 т, A₃ = 800 т. Спрос потребителей на данный груз составляет: В₁ = 200 т, В₂ = 350 т, B₃ = 650 т, В₄ = 400 т. Расстояния между грузоотправите­лями и грузополучателями приведены в табл. 8.2. Необходимо так закре­пить потребителей груза за грузополучателями, чтобы общая транспорт­ная работа была минимальной (показатель критерия оптимальности - расстояние).

Таблица 8.2

Расстояние между грузообразующими и грузопоглощающими пунктами

 

Грузообразующие пункты	Грузопоглащающие пункты
	В1	В2	В3	В4
	Расстояния, км
А1	11	7	9	5
А2	5	13	7	8
А3	3	12	5	9

 

Для решения задачи обозначим через х_ij количество тонн груза, ко­торое должно быть перевезено от i-поставщика j-потребителю. Тогда ма­тематическая модель задачи выразится системой уравнений (8.35), а це­левая функция, представляющая собой сумму произведений расстояний на соответствующий объем перевозок груза в тоннах, уравнением (8.36).

Минимизировать

Полученная система уравнений (8.35) является линейно зависимой, так как любое ее уравнение можно представить в виде линейной комби­нации остальных уравнений. Действительно, если из суммы уравнений 1, 2, 3 вычесть сумму уравнений 4, 5, 6, то получим уравнение 7 и т. д. Чис­ло линейно независимых уравнений должно быть меньше на одно общего числа уравнений в системе, т. е. базис системы должен быть равен коли­честву уравнений в системе ограничений за вычетом единицы. Так как общее число уравнений в системе определяется суммой поставщиков и потребителей, то в базисе должно быть уравнений

т + п-1,                                                                               (8.37)

где: m - число поставщиков;

n - число потребителей.

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

Матрица - прямоугольная таблица чисел, состоящая из m строк и n столбцов, в которой на пересечении строк и столбцов, обычно в пра­вых верхних углах, указывается расстояние между данным поставщи­ком и потребителем (в общем случае указывается показатель целевой функции).

К базисному плану предъявляются следующие требования:

он должен быть допустимым, содержать m + n — 1 загруженных клеток, чтобы загруженные клетки были расположены в порядке вычеркивае­мой комбинации. Для сокращения числа итераций при последующем ре­шении желательно, чтобы базисный план был, возможно, ближе к оп­тимальному.

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

Число неизвестных Х в задаче равно произведению числа строк m на число столбцов n. Максимальное число уравнений, которое можно полу­чить при решении транспортной задачи, определяется суммой поставщи­ков и потребителей, т. е. т + п. В этом случае, как показано выше, система уравнений является линейно зависимой. Для решения транспортной задачи базис системы должен содержать т + п-1 уравнений, а следовательно, в матрице должно быть т + п-1 загруженных клеток.

Условие вычеркиваемой комбинации загружен­ных клеток означает, что если, последовательно проходя по строкам и столбцам матрицы, можно вычеркнуть все загружаемые клетки, то их комбинация считается вычеркиваемой. При этом загруженная клетка вы­черкивается, если она единственная в своей строке или своем столбце.

Самый простой способ составления базисного плана - это так назы­ваемый способ северо-западного угла. Сущность этого спо­соба заключается в следующем. Распределение груза по потребителям начинается с клетки А₁ В₁ (табл. 8.3). Если предложение больше спроса, то следующая цифра ставится в клетке А₁ В₂ и т. п.

Таблица 8.3

Базисный план, составленный способом северо-западного угла

Клетки таблицы, в которых отмечено количество груза, перевозимого от грузоотправителя к данному грузополучателю, называются загружен­ными. Остальные клетки - незагруженными. Способ северо-западного угла является плохим способом составления базисного плана, так как в большинстве случаев дает базисный план, очень далекий от оптималь­ного. Положительная сторона его заключается в том, что он очень прост и обеспечивает получение т + п-1 загруженных клеток.

При полученном базисном плане закрепления поставщиков за потребителями (табл. 8.3), транспортная работа составит

200 • 11 +100 • 7 + 250 • 13 + 250 • 7 + 400 • 5 + 400 -9 = 13500 т-км.

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

них заносятся поставки. Если при записи поставок спрос по столбцу удовлетворен не полностью, ищется следующий по величине показа­тель a_ij, и так до полного удовлетворения спроса. Только после этого переходят на следующий столбец. Когда в столбце два или несколько одинаковых по величине минимальных показателей a_ij, то поставки мо­гут быть размещены в любом из них. Результаты составления базисного плана этим способом приведены в табл. 8.4.

Таблица 8.4

Базисный план, составленный способом наименьшего элемента по столбцу

При базисном плане, полученном способом наименьшего элемента по столбцу (табл. 8.4), транспортная работа составит

200-3 + 300-7 + 50-12 +100-7 +550-5 + 400-8 = 9950т-км.

Базисный план получился лучше (транспортная работа сократилась на 3550 т-км), однако нельзя сказать, является ли он оптимальным или нет. Для ответа на этот вопрос необходимо составленный базисный план проверить на оптимальность. Для этих целей разработано несколько ме­тодов. Наиболее широкое применение находят методы потенциалов (ме­тода МОДИ), Хичкока, Креко.

Идея метода потенциалов была высказана Л. В. Канторовичем в 1940 г. В 1951 г. американский ученый Дж. Д. Данциг предложил ту же идею, назвав ее модифицированным распределительным методом (МО­ДИ). Идея метода потенциалов, или метода МОДИ, заключается в том, что для проверки допустимого базисного плана на оптимальность опре­деляются особым образом числа, называемые потенциалами. Главное требование к потенциалам заключается в том, чтобы каждый показатель a_ij в загруженной клетке был равен сумме потенциалов своих строки и столбца

a_ij=V_i+Vj,                                                                       (8.38)

где: Ui - значение потенциала строки;

Vj - значение потенциала столбца.

Совершенно безразлично, с какой строки или столбца начинать опре­деление потенциалов. Безразлично также, каким по величине взять пер­вый по счету потенциал, так как произвольно определяется только пер­вый потенциал. Все остальные потенциалы жестко связаны с ним, и по­сле того, как первый потенциал установлен, он определяется единственно возможным способом. Определенные потенциалы строк и столбцов должны обеспечить значение потенциалов загруженных клеток равными нулю.

Потенциалы незагруженных (свободных) клеток определяются по формуле

где: Е_ij - потенциал свободной клетки.

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

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

Проверим на оптимальность базисный план, составленный способом наименьшего элемента по столбцу. Для этого матрицу распределительно­го метода дополним одним столбцом и строкой (табл. 8.5). Поставим в строке A₁ величину потенциала, равную нулю. Тогда, согласно форму­ле (8.38), потенциал столбца В₂ будет равен 7. Потенциал строки A₃ будет равен 5, а столбца B₃ - 0 и т. д. Потенциалы незагруженных кле­ток находим по формуле (8.39).