Поиск оптимального решения методом потенциалов

Основные данные о работе

Версия шаблона	1.1
Филиал	СГА
Вид работы	Творческая работа
Название дисциплины	Математический метод исследования экономики
Тема	Поиск оптимального решения методом потенциалов
Фамилия студента	Коновец
Имя студента	Тимур
Отчество студента	Евгеньевич
№ контракта	02201110201379

 

Содержание

 

Основная часть

Поиск оптимального решения методом потенциалов.

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

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

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

Перед тем как начать детальное рассмотрение способа потенциалов, безусловно, возвратиться к представлению потенциала.

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

Функция W, определенная на общности пунктов производства и потребления задачи T, была названа вектором потенциалов либо легко потенциалом данной задачи, если

(1.1)

(1.2)

для всех Х-значительных элементов некоторого плана X.

Будем называть план X потенциальным, если существует потенциал задачи T, связанный с этим планом условием (1.2). Между оптимальностью и потенциальностью планов задачи T существует узкая связь. Для оптимальности плана X нужна и довольна его потенциальность.

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

 

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

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

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

.

Тогда производимая при этом работа A вычисляется по формуле

.

Используя теперь свойства потенциала задачи T, имеем

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

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

Опишем отдельную итерацию способа, ограничившись сначала невырожденным случаем. Выходит, возможен, что теснее проведено k итераций способа потенциалов и в итоге получен опорный план. Разберем детально очередную, - итерацию.

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

для всех . (1.3)

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

Поэтому решение системы (1.3) осуществляется предельно просто.

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

.

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

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

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

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

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

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

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

,

Алгоритм метода потенциалов складывается из предварительного этапа и конечного числа однотипных итераций. На предварительном этапе строится исходный опорный план задачи T и составляется матрица

,

где и - предварительные потенциалы, отвечающие исходному плану .

На каждой итерации рассматриваются и преобразуются две матрицы

.

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

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

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

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

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

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

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

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

Метод потенциалов – первый точный метод решения транспортной задачи – был предложен в 1949 г. Л.В. Канторовичем и М. К. Гавуриным. По существу этот метод является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данцигом, который исходил из общих идей линейного программирования. В американской литературе метод потенциалов принято называть модифицированным распределительным методом. Метод потенциалов позволяет, отправляясь от некоторого опорного плана перевозок, построить решение транспортной задачи за конечное число итераций (шагов).