Очевидно, задачу (25.34) — (25.36) можно решить симплексным методом как задачу линейного программирования. Однако если привести определенными приемами коэффициент ау к единице, то данная модель не будет отличаться от модели транспортной задачи, и ее можно будет решить, в частности, методом потенциалов. [c.527]
Следует отметить, что модели оптимальной реализации планов перераспределения представляют собой модели транспортной задачи и могут решаться методом потенциалов. [c.183]
Оказывается, для того, чтобы решить маршрутную задачу с помощью транспортной модели, нужно принять в качестве однородного груза... пустые вагоны, направляемые от пункта выгрузки к пунктам погрузки. Полученное распределение, которое без труда находится на основе транспортной задачи, и дает решение задачи об оптимальной маршрутизации, так как оно определяет пути следования вагонов. Практическое применение транспортной задачи для решения задач оптимальной маршрутизации получило особенное распространение на автотранспорте. В ряде крупных городов производится ежедневный расчет рациональных маршрутов на ЭВМ и на их основе пишутся наряды для значительного процента автомашин. В некоторых небольших автохозяйствах эту методику хорошо освоили и регулярно используют сами диспетчеры. Это позволяет в ряде случаев снижать холостой пробег на 20—40%. Об эффекте ее применения убедительно свидетельствует и такой любопытный факт. В одном автохозяйстве, где проводился эксперимент по введению наилучшей маршрутизации транспорта, шоферы, ездившие по оптимальным маршрутам, найденным с помощью метода. потенциалов, имели на своих машинах отличительные флажки. Через несколько дней после начала эксперимента шоферы наглухо припаяли флажки к машинам, так как они стремились и впредь получать математические наряды. Большая эффективность работы этих машин была выгодна не только для автохозяйства в целом, но и для каждого и,з водителей. [c.43]
Точно так же как транспортная задача является частным случаем задачи ЛП, так и метод потенциалов, вообще говоря, может трактоваться как разновидность симплексных процедур. Он представляет собой итеративный процесс, на каждом шаге которого рассматривается некоторый текущий базисный план, проверяется его оптимальность, и при необходимости определяется переход к лучшему базисному плану. [c.115]
Методы разрешающих слагаемых и потенциалов были подробно рассмотрены в транспортной задаче и задаче размещения. Симплексный метод будет рассмотрен ниже (см. гл. XI). [c.268]
При решении транспортных задач методом потенциалов прежде всего необходимо построить исходный план перевозки грузов, в котором все мощности будут использованы, а потребности удовлетворены. Это возможно в случае общего баланса спроса и предложения. Выдвинем также некоторые дополнительные требования к исходному плану [c.189]
Соответствующая задача сводится к сетевой транспортной задаче с дополнительными ограничениями (,СТЗ ДО), где условия СТЗ полностью определяются сетью (графом) задачи, а дополнительные ограничения формируются по информации о связующих дугах. При этом число дополнительных ограничений равно (А —1)7, где / — число цепочек в (7 + 1)-й подсети. Для решения возникающей задачи могут быть использованы специальные алгоритмы и программы решения СТЗ ДО. Следует подчеркнуть, что в этих алгоритмах существенно используется структура матрицы СТЗ ДО, т. е. на каждой итерации операции преобразования обратной матрицы строятся в соответствии с методом потенциалов решения СТЗ. [c.70]
В настоящее время разработано множество различных алгоритмов решения Т.з. распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, способ двойного предпочтения, различные сетевые методы. Они относительно просты, по ним составлены десятки программ для различных вычислительных машин. Во многих снабженческих, транспортных и других организациях во всем мире с их помощью рассчитываются маршруты доставки материалов на строительные площадки, планы длительного прикрепления поставщиков металлопроката к потребителям, планы перевозок топлива. Задачи эти часто усложняются разного рода дополнительными условиями напр., в них включается расчет не только себестоимости перевозок, но и себестоимости производства продукции (производственно-транспортная задача), оптимизируется совместно доставка взаимозаменяемых видов продукции (скажем, различных кровельных материалов), оптимизируется доставка грузов с промежуточными базами (складами). Кроме того, следует учитывать, что экономико-математическая модель Т.з. позволяет описывать множество ситуаций, весьма далеких от проблемы перевозок, в частности, находить оптимальное размещение заказов на производство изделий с разной себестоимостью. [c.367]
После построения экономико-математической модели решается задача прикрепления поставщиков к потребителям. Расчеты выполняют в специальной таблице (матрице) линейного программирования методом потенциалов (табл. 4.19). В этой таблице, кроме ресурсов поставщиков, потребностей потребителей и транспортных расходов, имеются столбец и строка для записи потенциалов /, и Uj, которые дают возможность определить оптимальность плана закрепления поставщиков за потребителями. [c.153]
Для исследований базисной устойчивости стохастической транспортной задачи может быть использован метод статистических испытаний (метод Монте-Карло) в сочетании с двойственным методом потенциалов. При этом данные, характеризующие ресурсы поставщиков и потребности потребителей, формируются ЭВМ на основе определенных законов распределения и возможных интервалов их изменений. Под набором подразумевается совокупность величин ресурсов и потребностей, которые соответствуют их предполагаемым значениям в заранее определенных интервалах. Необходимое число наборов значений ресурсов и потребностей формируется соответствующей машинной программой для ЭВМ Минск-22 . При этом по рекуррентному соотношению по способу перемешивания определяется последовательность квазислучайных чисел, обладающих статистическими свойствами последовательности независимо от выбранных значений равномерно распределенной случайной величины =f (l/z-i),l г /г ЛЛ Полученные числа обычно удовлетворяют системе принятых статистических критериев для проверки равномерности распределения. [c.112]
Модель (1) — (4) и ее конкретная реализация (5) — (15) — есть классическая транспортная задача линейного программирования. Найдем численное решение задачи (5) — (15) методом потенциалов. [c.254]
Различия между транспортными задачами в матричной и сетевой формах весьма незначительны, так как методы их решения основаны на одних и тех же идеях (метод потенциалов). [c.289]
Рассмотрим процесс определения потенциалов текущего плана транспортной задачи на примере. В табл. 3.3 переписаны условия задачи из табл. 3.1 и ее допустимый базисный план, построенный методом северо-западного угла (см. табл. 3.2). [c.116]
В описанном алгоритме, как и в случае с матричной транспортной задачей, мы не гарантированы от возникновения вырожденного потока. Как уже упоминалось выше, такому потоку будет соответствовать несвязная опора. Для преодоления вырожденности рекомендуется включить в текущий план фиктивные компоненты с нулевыми объемами так, чтобы соответствующие им дуги дополняли опору до остова сети. Построенный таким способом план позволяет выполнить все действия, входящие в стандартную итерацию метода потенциалов. [c.127]
Идея этого метода заключается в том, что вместо решения задачи с тп неизвестными отыскивают т + п — 1 неизвестных, называемых разрешающими множителями и обозначаемыми Хь Х2,. .., X,-, которые имеют такое же значение, как в транспортной задаче потенциалы. [c.268]
Существующий алгоритм решения транспортных задач (метод потенциалов) предполагает, что ЦФ стремится к минимуму. Однако существуют ситуации, когда в рамках транспортной модели требуется максимизировать ЦФ, например, общий доход, объем продаж, прибыль, качество выполняемых работ и т.д. В этом случае в модель вместо искомой ЦФ L(X) вводится ЦФ LI(X)=-L(X), в которой тарифы умножаются на (-1). [c.64]
КАНТОРОВИЧ Леонид Витальевич (р.6.1.1912), советский математик и экономист, акад. АН СССР (1964 чл.-корр. 1958). Окончил Ленингр. гос. ун-т (1930). В 1930—39 работал в Ленингр. ин-те инженеров пром. строительства в 1934—60 проф. Ленингр. гос. ун-та в 1939—48 нач. кафедры Высшего инжеперно-технич. училища в 1945—60 ст. научный сотрудник, зав. отделом Ленингр. отделения математич. ин-та АН СССР и 1960—71 зам. директора, зав. математико-экономич. отделением Ин-та математики Сиб. отделения АН СССР. С 1971 зав. проблемной лабораторией Ин-та управления нар. х-вом Госкомитета по науке и технике СССР. Опубликовал начиная с 1929 большое число работ по различным областям математики и её приложений теории множеств, теории функций, функционального анализа (теория полуупорядоченных — К-пространств), приближённым методам анализа, вычислит, математике и технике. Работы К. положили начало новому разделу математики — линейному программированию и его обобщениям. Общие принципы линейного программирования изложены им в книге Математические методы организации и планирования производства (Л., 1939), дан универсальный метод их решения, а также указаны осн. типы экономич. задач, к к-рым приложимы линейно-программные модели. В частности, в его работах (1940—49) решены т. н. транспортная задача и метод потенциалов для неё. Результаты исследовании К. оставались неизвестными за рубежом и были повторены в кон. 40-х гг. амер. учёными (Т. Купманс, Дж. Данциг). В наст, время приоритет сов. науки, и в частности К., в разработке осн. принципов линейного программирования признан и за рубежом. [c.95]
Решение транспортных задач методом потенциалов. Продемонстрируем метод решения транспортных задач в сетевой постановке, так называемый метод потенциалов. Он был предложен Л. В. Канторовичем в начале сороковых годов п является первым методом решения транспортных задач. Интересно отметить, что метод с самого начала предназначался для решения транспортных задач в сетевой постановке и только впоследствии был преобразован к матричной форме. Метод потенциалов является одним из способов реализации общего принципа решения задач линейного программирования — принципа последовательного улучшения плана, о котором мы уже говорили в 4 гл. 1. [c.189]
Во-вторых, специфика зависимости величины минимума расхода электроэнергии на перекачку от ее объема (в соответствии с принципом 1 это и отображено в критерии оптимальности) такова, что эта зависимость выражается кусочно-линейной выпуклой (вниз) функцией. Это позволило построить точный, быстро сходящийся алгоритм решения задачи, являющейся обобщением метода потенциалов решения сетевой транспортной задачи линейного программирования (СТЗ ЛП) для случая кусочно-линейного выпуклого функционала [41, 47]. Для построения экономико-математической модели задачи введем обозначения г — номер вершины сети 3 (г, s) —дуга сети между вершинами г и s R(E) — множество вершин (дуг) сети Rir(R r< R) [R2t(R2r z zR) подмножество вершин сети, из которых выходят дуги, входящие в r-ю вершину (в которые входят дуги, выходящие из г-й вершины) ur(vr) — объем поступления (потребления) нефти в r-й вершине за плановый период . х — объем перекачки нефти по дуге (г, s) за плановый период ars(Prs) — нижний (верхний) предел значений xrs frs(xrs) — функция зависимости расхода электроэнергии от объема перекачки для дуги (г, s). [c.156]
Метод потенциалов (8.1.) —метод решения транспортной задачи, основанный на построении специальных характеристик-потенциалов. Необходимым и достаточным условем оптимального плана является его потенциальность. [c.344]
Проверка оптимальности решения транспортной задачи методом потенциалов. Идея метода потенциалов для решения транспортной задачи сводится к следующему. Представим себе, что каждый из поставщиков Z, вносит за перевозку единицы груза какую-то сумму Z, в свою очередь каждый из потребителей YJ также вносит за перевозку груза сумму YJ. Эти платежи передаются некоему третьему лицу (перевозчику). Обозначим Z,+ Yj = K,j(i = l...m j= 1... n) и будем называть величину Ки псевдостоимостью перевозки единицы груза от Z, к YJ. Заметим, что платежи Z, и Y не обязательно должны быть положительными не исключено, что перевозчик сам платит тому или другому пункту какую-то премию за перевозку. Также надо отметить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах (Z, и YJ, ) одна и та же и от плана к плану не меняется. [c.269]
Алгоритм метода потенциалов для транспортной задачи. Критерий (3.8)-(3.9) положен в основу однюго из методов решений транспортной задачи, получившего название метода потенциалов. Впервые он был предложен в 1949г. Л. В. Канторовичем и М. К. Гавуриным. Позже на базе общих идей линейного программирования аналогичный метод был предложен Дж. Данцигом. [c.115]
Завершая разговор о методе потенциалов, следует отдельно остановиться на ситуации возникновения вырожденного плана. Возможность получения вырожденного плана уже отмечалась при описании метода северо-западного угла. Нетрудно заметить, что вырожденный план также может получиться на этапе преобразования текущего плана по цепочке если одинаковое минимальное значение будет достигнуто сразу на нескольких клетках, помеченных знаком — , то при вычитании перемещаемого по цепочке объема в новом плане будет меньше чем т+n-l ненулевых компонент. Способ преодоления вырожденности в транспортной задаче весьма прост, а именно предлагается дополнить текущий план необходимым количеством нулевых клеток (фиктивными перевозками) таким образом, чтобы они позволяли рассчитать полную систему потенциалов, и далее действовать в соответствии с правилами описанного выше алгоритма. Фактически здесь мы имеем дело не с чем иным, как с аналогом метода возмущений для транспортной задачи как частного случая ЗЛП. К taKOMy выводу легко прийти, если положить, что добавляемые фиктивные клетки содержат некоторый малый объем 8. [c.120]
Необходимо также отметить, что ни в работах А. Н. Толстого, ни у Хичкока не было дано законченного метода решения рассматриваемой задачи. Первый общий метод решения транспортной задачи, получивший в дальнейшем название метода потенциалов , предложен ныне академиком Л. В. Канторовичем и опубликован в 1949 году, хотя разработан был им еще в 1941 г. [c.194]
Смотреть страницы где упоминается термин Транспортная задача и метод потенциалов
: [c.26] [c.270] [c.227] [c.42]Смотреть главы в:
Экономико-математические модели и методы -> Транспортная задача и метод потенциалов