В качестве критерия оптимальности транспортной. Целевые функции

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

Х1,Х2,Х3,…Хп.

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

Целевая функция. Это - выражение, значение которого инженер стремиться сделать максимальным или минимальным. Целевая функция позволяет количественно сравнить два альтернативных решения. С математической точки зрения целевая функция описывает некоторую (п+1) - мерную поверхность. Ее значение определяется проектными параметрами

М = М (х1,х2,…,хп).

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

Рисунок 1. Одномерная целевая функция.

Рисунок 2. Двумерная целевая функция.

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

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

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

Рисунок 3. При изменении знака целевой функции на противоположный в задаче на минимум, превращает ее в задачу на максимум.

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

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

С1 (X1, X2, Х3, . . ., Хп) = 0,

С2 (X1, X2, Х3, . . ., Х п) = 0,

..……………………………..

Сj(X1, X2, Х 3, . . ., Хп) = 0.

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

z1 ?r1(X1, X2, Х3, . . ., Хп) ?Z1

z2 ?r2(X1, X2, Х3, . . ., Хп) ?Z2

………………………………………

zk ?rk(X1, X2, Х3, . . ., Хп) ?Zk

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

Прямые и функциональные ограничения. Прямые ограничения имеют вид

xнi ? xi ? xвi при i ? ,

где xнi , xвi - минимально и максимально допустимые значения i-го управляемого параметра; п - размерность пространства управляемых параметров. Например для многих объектов параметры элементов не могут быть отрицательными: xнi ? 0 (геометрические размеры, электрические сопротивления, массы и т.п.).

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

• 1) типа равенств
• ш (Х) = 0; (2.1)
• 2) типа неравенств

ц (Х) › 0, (2.2)

где ш (Х) и ц (Х) - вектор-функции.

Прямые и функциональные ограничения формируют допустимую область поиска:

ХД = {Х | ш(Х) = 0, ц (Х)›0, xi › xнi ,

xi ‹ xвi при i ? }.

Если ограничения (2.1) и (2.2) совпадают с условиями работоспособности, то допустимую область называют также областью работоспособности ХР.

Любая из точек Х принадлежащая ХД является допустимым решением задачи. Часто параметрический синтез ставится как задача определения любого из допустимых решений. Однако гораздо важнее решить задачу оптимизации - найти оптимальное решение среди допустимых.

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

Рисунок 4. Произвольная целевая функция может иметь несколько локальных оптимумов.

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

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

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

yi < TTi , i О ; yi > TTj , j О ;

yr = TTr ± ?yr; r О .

где yi, yj, yr - множество выходных параметров;

TTi, TTj, TTr - требуемые количественные значения соответствующих выходных параметров по техническому заданию;

Yr - допустимое отклонение r-го выходного параметра от указанного в техническом задании значения TTr.

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

Частные критерии могут применяться в случаях, когда среди выходных параметров можно выделить один основной параметр yi(Х), наиболее полно отражающий эффективность проектируемого объекта. Этот параметр принимают за целевую функцию. Примерами таких параметров являются: для энергетического объекта - мощность, для технологического автомата - производительность, для транспортного средства - грузоподъемность. Для многих технических объектов таким параметром служит стоимость. Условия работоспособности всех остальных выходных параметров объекта относят при этом к функциональным ограничениям. Оптимизация на основе такой постановки называется оптимизацией по частному критерию.

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

Взвешенный аддитивный критерий применяют тогда, когда условия работоспособности позволяют выделить две группы выходных параметров. В первую группу входят выходные параметры, значения которых в процессе оптимизации нужно увеличивать y+i(X) (производительность, помехоустойчивость, вероятность безотказной работы и т. п.), во вторую - выходные параметры, значения которых следует уменьшать y-i (X) (расход топлива, длительность переходного процесса, перерегулирование, смещение и пр.). Объединение нескольких выходных параметров, имеющих в общем случае различную физическую размерность, в одной скалярной целевой функции требует предварительного нормирования этих параметров. Способы нормирования параметров будут рассмотрены ниже. Пока будем считать, что все у(Х) безразмерны и среди них нет таких, которым соответствуют условия работоспособности типа равенства. Тогда для случая минимизации целевой функции свертка векторного критерия будет иметь вид

где aj>0 - весовой коэффициент, определяющий степень важности j-го выходного параметра (обычно aj выбираются проектировщиком и в процессе оптимизации остаются постоянными).

Целевую функцию в форме (2.1), выражающую аддитивный критерий, можно записать и в том случае, когда все или основные условия работоспособности имеют вид равенств. Тогда целевая функция

определяет среднеквадратичное приближение yj(X) к заданным техническим требованиям TTj.

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

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

Критерий формы функции используют, когда ставится задача наилучшего совпадения заданной (эталонной) характеристики yТТ(Х,щ) с соответствующей выходной характеристикой y(Х,щ) проектируемого объекта, где щ - некоторая переменная, например частота, время, избранная фазовая переменная. К таким задачам относятся: проектирование системы автоматического регулирования, обеспечивающей требуемый вид переходного процесса по регулируемому параметру; определение параметров модели транзистора, дающих максимальное совпадение его теоретических вольт-амперных характеристик с экспериментальными; поиск параметров сечений балки, значения которых приводят к наилучшему совпадению заданной эпюры напряжений с расчетной, и т. п.

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

где р -- количество узловых точек щj на оси переменной щ; aj - весовые коэффициенты, значения которых тем больше, чем меньшее отклонение y(Х, щj) - yTT(Х, щj) нужно получить в j-и точке.

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

Введем количественную оценку степени выполнения j-го условия работоспособности, обозначим ее через zj и будем называть запасом работоспособности параметра yj. Расчет запаса по j-му выходному параметру можно выполнить различными способами, например,

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

Здесь предполагается, что все соотношения сведены к виду yi < TТj. Если yi > TТj , то -yj < -TТj . Следует принимать аj >1 (рекомендуемые значения 5 ? аj ? 20), если желательно достичь выполнения j-го технического требования с заданным допуском, т. е. yj = TТj ± ?yj; aj=l, если необходимо получить максимально возможную оценку zj.

Качество функционирования технической системы характеризуется вектором выходных параметров и, следовательно, вектором Z=(zm,zm,…,zm). Поэтому целевую функцию следует формировать как некоторую функцию ц(Z) вектора оценок. Например, если в качестве целевой функции рассматривается запас только того выходного параметра, который в данной точке X является наихудшим с позиций выполнения требований ТЗ, то

где m - количество запасов работоспособности.

Естественно теперь поставить задачу о выборе такой стратегии поиска X, которая максимизировала бы минимальный из запасов, т. е.

где ХД - допустимая для поиска область.

Критерий оптимизации с целевой функцией (2.6) называют максиминным критерием.

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

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

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

где оi - коэффициент, численно равный единице параметра ui .

Нормирование выходных параметров можно выполнить с помощью весовых коэффициентов, как в аддитивом критерии, или переходом от уj к запасам работоспособности zj по (2.5).

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

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

Fс = min хij lij, (1)

где m, n - число пунктов соответственно отправления и назначения;

хij - размер перевозок грузопотока по каждой корреспонденции между пунктами олтправления и назначения, т;

lij - расстояние перевозки по каждой корреспонденции грузопотока, км.

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

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

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

В соответствии с основной концепцией оптимизации, обоснованной МИИТом, в условиях наличия резервов пропускной и провозной способности в качестве показателя оптимальности при текущем планировании перевозок экономически целесообразнее использовать минимум зависящих от объема перевозок эксплуатационных расходов, т.е. минимум себестоимости перевозок в части зависящих расходов. Целевая функция транспортной задачи в этом случае будет иметь вид:

Fс = min хij С зав ij, (2)

где С зав ij- себестоимость перевозок грузов по каждой корреспонденции грузопотока в части зависящих расходов, к/т.

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

Fс = min хij tij, (3)

где tjj - время доставки грузов по каждой корреспонденции грузопотока, ч.

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

В условиях перехода транспорта на рыночные отношения должна, очевидно, получить широкое распространение оптимизация планов перевозок исходя из минимума тарифных плат, когда целевая функция имеет вид

Fс = min хij С тар ij, (4)

где С тар ij - доходная тарифная ставка при перевозке грузов для каждой корреспонденциигрузопотока, к/т.

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

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

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

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

Fс = min хij (сij + Ен кij), (5)

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

Fс = min хij (сij + Ен (кij + mij), (6)

где кij - удельные капиталовложения в подвижной состав и постоянные устройства по каждой корреспонденции грузопотока, к/т;

mij - удельная стоимость грузовой массы в пути по каждой корреспонденции грузопотока, к/т.

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

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

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

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

Экономико-математическая модель задачи оптимизации с учетом потребительских свойств взаимозаменяемой продукции была реализована в конкретных решениях, в частности в работе НИИМС (авторы Е. П. Нестеров, В. А. Скворцова и др.). В работах МИИТа установлено, что при разработке оперативных текущих и перспективных оптимальных планов перевозок на железнодорожном транспорте в стоимостных показателях оптимальности должны непременно учитываться потери многих грузов и особенно скоропортящихся, сыпучих и навалочных. При решении комплексных транспортных задач оптимизации перевозок для любого периода и планирования с участием двух и более взаимодействующих видов транспорта потери необходимо включать в стоимостные показатели оптимальности для всех групп грузов в соответствии с классификацией. Различия, если таковые имеются, в потребительских свойствах и качестве взаимозаменяемых грузов должны отражаться через соответстующие цены их в стоимости грузовой массы в пути. Функционалы оптимального плана в общем виде могут быть выражены: без учета стоимости грузовой массы в пути

Fс = min хij (сij + Енкij + у пэ ij), (7)

с учетом стоимости грузовой массы в пути

Fс = min хij (сij + Ен (кij + mij + у пэ ij), (8)

где у пэ ij - удельная величина текущих потерь грузов в стоимостном измерении по каждой корреспонденции грузопотока, к/т.

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

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

Fс = min хij у пэ ij. (9)

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

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

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

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

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

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления (поставщики) A1, A2, . . ., Am в n пунктов потребления (потребители) B1, B2, . . . Bn так, чтобы:

Вывезти все грузы от поставщиков;

Удовлетворить спрос каждого потребителя;

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

Рассмотрим транспортную задачу, в качестве критерия оптимальности которой используется минимальная стоимость перевозки всего груза .

Обозначим:

ai - наличие груза в i -ом пункте отправления https://pandia.ru/text/78/103/images/image205_0.gif" width="81" height="27 src=">;

сij - стоимость перевозки единицы груза из i -ого пункта отправления в j -ый пункт потребления (тариф перевозки);

xij - количество груза, перевозимого из i -ого пункта отправления в j -ый пункт назначения, назначения, xij ≥ 0.

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

Запишем математическую модель транспортной задачи.

Требуется определить матрицу ) , которая удовлетворяет следующим условиям:

Https://pandia.ru/text/78/103/images/image210_0.gif" width="74" height="45">.gif" width="47" height="21">.gif" width="63" height="20"> (5.3)

и доставляет минимальное значение целевой функции

L () = https://pandia.ru/text/78/103/images/image215_0.gif" width="36" height="24"> удовлетворяют системе линейных уравнений (5.1), (5.2) и условию неотрицательности, то обеспечивается доставка необходимого груза каждому потребителю, вывоз имеющегося груза от всех поставщиков, а также исключаются обратные перевозки.

Определение 1. Всякое неотрицательное решение систем линейных уравнений (5.1) и (5.2), определенное матрицей ) называется допустимым планом транспортной задачи .

Определение 2. План ) https://pandia.ru/text/78/103/images/image218_0.gif" width="23" height="24"> , называется базисным или опорным.

Определение 4. Если в опорном плане число отличных от нуля значений переменных https://pandia.ru/text/78/103/images/image219_0.gif" width="55" height="22">.gif" width="55" height="22"> > , вводится фиктивный (n+ 1) –ый пункт назначения с потребностью bn +1 = − https://pandia.ru/text/78/103/images/image221_0.gif" width="83 height=22" height="22">

Если < https://pandia.ru/text/78/103/images/image220_0.gif" width="56 height=25" height="25">.gif" width="79" height="22 src=">

Рассмотрим один из методов построения первого опорного плана транспортной задачи – метод минимальной стоимости или наилучшего элемента матрицы удельных затрат.

Определение 6. Наилучшим элементом матрицы удельных затрат (тарифов) будем называть наименьший тариф, если задача поставлена на минимум целевой функции, наибольший тариф – если задача поставлена на максимум.

Алгоритм построения первого опорного плана.

1. Среди матрицы удельных затрат находим наилучший тариф.

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

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

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

Дальнейшее улучшение первого опорного плана транспортной задачи и получение оптимального плана производим методом потенциалов.

Теорема 3 . План ) транспортной задачи является оптимальным, если существует система (m + n) чисел ui и vj (называемых потенциалами), удовлетворяющая условиям:

(5.6)

(5.7)

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

Обозначим: ) оценка свободной (незанятой) клетки таблицы.

Определение 7. Опорный план транспортной задачи является оптимальным, если все оценки свободных клеток распределительной таблицы (задача поставлена на минимум).

Алгоритм метода потенциалов

1. Построение первого опорного плана транспортной задачи методом минимальной стоимости.

2. Проверка вырожденности плана .

Потенциалы могут быть рассчитаны только для невырожденного плана. Если число занятых клеток в опорном плане (число базисных переменных) меньше, чем (m+n−1), то вносим нуль в одну из свободных клеток таблицы так, чтобы общее число занятых клеток стало равным (m+n−1). Нуль вводят в клетку с наилучшим тарифом, которая принадлежит строке или столбцу. Одновременно вычеркиваемых при составлении первого опорного плана. При этом фиктивно занятая нулем клетка таблицы не должна образовывать замкнутого прямоугольного контура с другими занятыми клетками таблицы.

3. Расчет значения функции цели (5.4) путем суммирования произведений тарифов (удельных затрат) на объемы перевозимого груза по всем занятым клеткам таблицы.

4. Проверка оптимальности плана.

Определяем потенциалы . Для каждой занятой клетки записываем уравнение , в результате получаем систему (m + n−1) уравнений с (m + n) переменными.

Так как число переменных больше числа уравнений, то полученная система не определена и имеет бесчисленное множество решений..gif" width="70" height="22">, тогда остальные потенциалы определяются однозначно, а их значения заносятся в дополнительные строку и столбец распределительной таблицы.

Для каждой свободной клетки определяем оценки https://pandia.ru/text/78/103/images/image233.gif" width="72 height=24" height="24">(задача решается на минимум целевой функции), то оптимальный план найден. Если хотя бы одна оценка свободной клетки не удовлетворяет условию оптимальности, то необходимо план улучшить, осуществив перераспределение груза.

5.

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

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

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

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

Полученный опорный план проверяем на оптимальность, т. е. возвращаемся к четвертому этапу алгоритма.

Замечания.

1. Если в минусовых клетках построенного цикла находятся два или несколько одинаковых минимальных значений , то при перераспределении объемов груза освобождается не одна, а две или несколько клеток. В этом случае план становится вырожденным. Для продолжения решения необходимо одну или несколько одновременно освобождающихся клеток таблицы занять нулем, причем предпочтение отдается клеткам с наилучшим тарифом. Нулей вводят столько, чтобы во вновь полученном опорном плане число занятых клеток (базисных переменных) было ровно (m + n−1).

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

3. Значение целевой функции на каждой итерации можно рассчитать следующим образом:

(задача поставлена на минимум),

(задача поставлена на максимум),

где - величина перемещаемого по контуру объема груза;

Оценка свободной клетки, в которую направляется груз при переходе к новому опорному плану;

− значение функции цели на k-ой итерации;

− значение функции цели на предыдущей итерации.

Пример.

На трех складах оптовой базы имеется однородный груз в количествах 40, 80 и 80 единиц. Этот груз необходимо перевезти в четыре магазина, каждый из которых должен получить соответственно 70, 20, 60 и 60 единиц. Стоимости доставки единицы груза (тарифы) из каждого склада ) во все магазины ) заданы матрицей .

Составить план перевозок однородного груза с минимальными транспортными затратами (числа условные).

Решение.

1. Проверим необходимое и достаточное условие разрешимости задачи:

40+80+80 = 200,

70+20+60+60 = 210.

Как видно, суммарная потребность груза превышает его запасы на складах оптовой базы. Следовательно, модель транспортной задачи является открытой и в исходном виде решения не имеет. Для получения закрытой модели введем дополнительный (фиктивный) склад А4 с запасом груза, равным а 4 = 210 – 200 = 10 ед. тарифы перевозки единицы груза из склада А4 во все магазины полагаем равными нулю.

Все исходные данные заносим в таблицу 7.

						Запасы
	A 1
	A 2		3
	A 3
	A 4
Потребности					210 210

2. Построение первого опорного плана методом минимальной стоимости.

Среди тарифов минимальным или наилучшим является С14 =1. В клетку А1В4 направляем максимально возможный груз, равный min{60,40} = 40. Тогда x 14 = 40. Из склада А1 весь груз вывезен, но потребность четвертого магазина неудовлетворенна на 20 ед. строка А1 выходит из рассмотрения.

Среди оставшихся тарифов минимальный элемент - С23 = 2. В клетку А2В3 направляем груз min{60,80} = 60. При этом столбец В3 выходит из рассмотрения, а из склада А2 не вывезено 20 ед.

Из оставшихся элементов минимальный С22 = 3. В клетку А2В2 направляем груз в количестве min{20,20} = 20. При этом столбец одновременно вычеркиваются строка А2 и столбец В2.

Выбираем минимальный элемент С31 = 4. В клетку А3В1 направляем груз, равный min{70,80} = 70. При этом столбец В1 выходит из рассмотрения, а из склада А3 не вывезено 10 ед. Оставшийся груз с третьего склада направляем в летку А3В4, x 34 = 10. Потребность четвертого магазина не удовлетворена на 10 ед. направим от фиктивного поставщика – склад А4 10 ед. груза в клетку А4В4, x 44 = 10.

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

3. Проверка вырожденности плана.

Число занятых клеток или базисных переменных в первом опорном плане равно шести. план транспортной задачи является вырожденным, так как число базисных переменных в невырожденном плане равно m + n – 1 = 4 + 4 – 1 = 7. Для продолжения решения задачи опорный план необходимо дополнить введением фиктивной перевозки, т. е. занять нулем одну из свободных клеток.

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

4. Расчет значения целевой функции.

Значение целевой функции первого опорного плана определяем путем суммирования произведений тарифов на объемы перевозимого груза по всем занятым клеткам таблицы.

L(Х1) = 4∙70 + 3∙20 + 2∙60 + 1∙40 + 3∙0 + 6∙10 + 0∙10 = 560 (тыс. руб.).

5. Проверка условия оптимальности.

Рассчитаем потенциалы по занятым клеткам таблицы из условия: https://pandia.ru/text/78/103/images/image260_0.gif" width="139" height="22">Так как число неизвестных потенциалов больше числа уравнений (m + n > m + n – 1), то один из потенциалов принимаем равным нулю..gif" width="115 height=154" height="154">

Полагая , получим https://pandia.ru/text/78/103/images/image265_0.gif" width="82" height="22">, ,https://pandia.ru/text/78/103/images/image268_0.gif" width="193" height="22">

Рассчитанные потенциалы заносим в таблицу 7. Подсчитаем оценки свободных клеток.

https://pandia.ru/text/78/103/images/image270_0.gif" width="167" height="22 src=">,

https://pandia.ru/text/78/103/images/image272_0.gif" width="210" height="22 src=">,

https://pandia.ru/text/78/103/images/image274_0.gif" width="183" height="22 src=">,

https://pandia.ru/text/78/103/images/image276_0.gif" width="153" height="22 src=">,

Первый опорный план не является оптимальным, так как имеются положительные оценки свободных клеток и . Выбираем максимальную положительную оценку свободной клетки - .

6. Построение нового опорного плана.

Для клетки А3В2 построим прямоугольный замкнутый контур 0таблица 7) и проведем перераспределение груза контуру. Вершинам контура, начиная от вершины, находящейся в свободной клетке А3В2,присваиваем поочередно знаки «+» и «−» .

Из объемов груза, стоящих в минусовых клетках, выбираем наименьшее, т. е. θ = min(20,10) = 10. Прибавляем значение θ = 10 к объемам груза, стоящих в плюсовых клетках, вычитаем из объемов груза, стоящих в минусовых клетках замкнутого контура. В результате получим новый опорный план, приведенный в таблице 8.

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления в п пунктов назначения . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i -го пункта отправления в j -й пункт назначения, через – запасы груза в i -м пункте отправления, через – потребности в грузе в j – м пункте назначения, а через – количество единиц груза, перевозимого из i -го пункта отправления в j -й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

при условиях

(64)

(65)

(66)

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

Определение 15.

Всякое неотрицательное решение систем линейных уравнений (64) и (65), определяемое матрицей , называется планом транспортной задачи.

Определение 16.

План , при котором функция (63) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записывают в виде таблицы 21.

Таблица 21

Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна единиц. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е.

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

Теорема 13.

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

В случае превышения запаса над потребностью, т. е. вводится фиктивный (n +1)–й пункт назначения с потребностью и соответствующие тарифы считаются равными нулю: Полученная задача является транспортной задачей, для которой выполняется равенство (67).

Аналогично, при вводится фиктивный (m +1)–й пункт отправления с запасом груза и тарифы полагаются равными нулю: Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. В дальнейшем будем рассматривать закрытую модель транспортной задачи. Если же модель конкретной задачи является открытой, то, исходя из сказанного выше, перепишем таблицу условий задачи так, чтобы выполнялось равенство (67).

Число переменных в транспортной задаче с т пунктами отправления и п пунктами назначения равно пт , а число уравнений в системах (64) и (65) равно п+т . Так как мы предполагаем, что выполняется условие (67), то число линейно независимых уравнений равно п+т – 1. Следовательно, опорный план транспортной задачи может иметь не более п + т – 1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности п +т – 1, то план является невырожденным, а если меньше – то вырожденным.

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

Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы.

Пример 19.

Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Решение. Обозначим через количество единиц сырья, перевозимого из i –го пункта его получения на j –е предприятие. Тогда условия доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств:

(68)

При данном плане перевозок общая стоимость перевозок составит

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

Программа для решения транспортной задачи методом потенциалов

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

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

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

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

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

Распределительный метод. При этомметоде для каждой пустой клетки строят цикл и для каждого цикла непосредственно вычисляют алгебраическую сумму тарифов.

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

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

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

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

Выше рассматривалась закрытая модель транспортной задачи, с правильным балансом, когда выполняется условие (1.3). В случае выполнения (1.4) (открытая модель) баланс транспортной задачи может нарушаться в 2-ух направлениях:

1. Сумма запасов в пунктах отправления превышает сумму поданных заявок (транспортная задача с избытком запасов):

а i > b j (где i=1,...,m ; j=1,...,n);

2. Сумма поданных заявок превышает наличные запасы (транспортная задача с избытком заявок):

а i < b j (где i=1,...,m ; j=1,...,n);

Рассмотрим последовательно эти два случая:

Транспортная задача с избытком запасов.

Сведем её к ранее рассмотренной транспортной задаче с правильным балансом. Для этого, сверх имеющихся n пунктов назначения В 1 , B 2 , ... , B n , введём ещё один, фиктивный, пункт назначения B n +1 , которому припишем фиктивную заявку, равную избытку запасов над заявками

b n+1 = а i - b j (где i=1,...,m ; j=1,...,n) ,

а стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения b n +1 будем считать равной нулю. Введением фиктивного пункта назначения B n +1 с его заявкой b n +1 мы сравняли баланс транспортной задачи, и теперь ее можно решать, как обычную транспортную задачу с правильным балансом.

Транспортная задача с избытком заявок.

Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления A m +1 с запасом a m +1 равным недостающему запасу, и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равной нулю.