Учебная работа. Реферат: Решение транспортных задач методом потенциалов

Учебная работа. Реферат: Решение транспортных задач методом потенциалов

Содержание

Содержание 1

Введение 1

1.Теоретические базы способа 4

2.Вырожденность. 12

3.способ потенциалов и способ поочередного улучшения плана 18

4. метод способа потенциалов 22

5. Управление юзера. 29

Заключение. 30

Введение

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

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

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

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

Цель курсовой работы:

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

Теоретические базы способа

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

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

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

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

Пусть — случайный план задачки 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. Несложно усмотреть, что если б мы задались произвольным значением хоть какой из величин либо , то получившиеся в итоге числа отличались бы от , , вычисленных в предположении , на некую постоянную. Отсюда, а именно, следует, что величина определяется совершенно точно для всех i, j.

Если подготовительные потенциалы , таковы, что для хоть какой пары i, j имеет пространство неравенство

,

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

Если же для неких индексов i, j

,

то план не оптимален. Нужен переход к шагу 2, на котором этот план будет улучшен.

Шаг 2. Вычислим уклонения

().

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

.

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

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

.

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

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

,

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

.

Вспомним, что все элементы, стоящие в квадратной скобке, не считая , являются — существенными. Потому

.

Беря во внимание дальше отрицательность уклонения и положительность , имеем

.

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

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

, , (1.4)

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

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

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

Вырожденность.

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

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

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

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

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

,

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

Существует такое число , что при любом , удовлетворяющем условию

, (2.1)

задачка владеет свойством невырожденности.

Существует такое число , что при всех и , удовлетворяющих условиям

, (2.2)

справедливы последующие утверждения:

а) если — опорный план задачки , то — опорный план задачки ;

б) если — опорное решение задачки , то — лучший опорный план задачки .

тут под понимается матрица, составленная из нулей и коэффициентов разложения вектора

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

.

Обосновывать эти утверждения мы не будем.

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

Будем считать число удовлетворяющим условиям (2.1) и (2.2) и так малым, что неравенство оказывается эквивалентным соблюдению 1-го из последующих соотношений: или , или , но ; при довольно малом — невырожденная задачка (утверждение ). Потому способ потенциалов через конечное число итераций приведет к ее решению. Полагая в приобретенном рациональном плане , приходим к разыскиваемому хорошему плану задачки T (утверждение для ).

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

, где

не зависят от . Это событие дозволяет опускать при вычислении рационального плана задачки величину и оперировать только с составляющими плана :

и .

Введем за ранее несколько определений. Пару матриц

,

назовем обобщенным планом задачки T, если при всех довольно малых

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

.

Элементы матрицы будем именовать обобщенными перевозками.

Меж 2-мя обобщенными перевозками введем соотношение «больше, меньше», полагая , если или , или , но . Разумеется, что условие эквивалентно равенствам

, .

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

Пусть — два обобщенных плана задачки T. Будем гласить, что 1-ый план соответствует наименьшим транспортным издержкам по сопоставлению со вторым, если или

,

или

,

но

.

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

3.способ потенциалов и способ поочередного улучшения плана

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

На первом шаге способа потенциалов рассчитываются подготовительные потенциалы

удовлетворяющие системе уравнений

для . (3.1)

(тут — огромное количество пар индексов векторов, составляющих базис плана .)

Переименуем векторы базиса и обозначим l-й вектор через

Беря во внимание, что все составляющие вектора , не считая 2-ух, равных единице, равны нулю, можно переписать систему (3.1) в эквивалентном виде

.

тут

;

— стоимость единичной перевозки по коммуникации, соответственной вектору .

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

,

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

Представим, что при неких i,j

.

Тогда в согласовании с способом поочередного улучшения плана выбирается таковая пара индексов , на которой величина

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

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

. (3.2)

тут — коэффициент при i-м векторе базиса в разложении вектора ограничений (вводимого вектора) по векторам старенького базиса; минимум берется по тем индексам i, для которых . Если , то из базиса удаляется его r-й вектор.

Базовые составляющие новейшего плана определяются по формуле

(3.3)

Для транспортной задачки коэффициенты равны нулю либо . При всем этом в том и лишь в том случае, если i-й вектор базиса соответствует коммуникации, которая занимает нечетную (четную) позицию в построенном маршруте. Потому формула (3.2) в случае транспортной задачки быть может заменена правилом: — малая нечетная перевозка маршрута, связывающего пункты и. Это правило и употребляется в способе потенциалов. Формула (3.3) применительно к транспортной задачке преобразуется в правило конфигурации плана перевозок, употребляемое в способе потенциалов: перевозки, запланированные по нечетным (четным) коммуникациям, уменьшаются (растут) на величину , перевозка меж и полагается равной , другие перевозки сохраняют свои значения.

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

4. Метод способа потенциалов

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

,

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

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

и .

Матрица представляет собой опорный план задачки T, построенный в итоге k-й итерации. Матрица составлена из оценок векторов относительно базиса плана , т.е.

где и — подготовительные потенциалы, отвечающие плану .

Сначала будем полагать задачку T невырожденной. Нужные замечания относительно вырожденного варианта будут изготовлены ниже.

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

.

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

Полагаем и вычисляем

для .

Дальше определяем

для .

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

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

.

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

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

.

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

Опосля l – 1 шагов все ненулевые — значительные элементы оказываются принадлежащими . Пусть l – нечетное (четное) число. Так как — пустое огромное количество, все — значительные элементы матрицы, приобретенной опосля вычитания (добавления) величины из строк (к столбцам) частей , равны нулю. Итак, величины , удовлетворяют системе (1.3), соответственной плану .

Как следует, — подготовительные потенциалы, надлежащие плану , а

.

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

.

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

Если все элементы матрицы неотрицательны, — разыскиваемое решение. Если же посреди величин имеются отрицательные, нужен переход к шагу 2.

Шаг 2. На шаге 2 делается улучшение плана . Основой шага является процесс составления цепочки из положительных частей этого плана. Выберем меньший элемент матрицы , расположенный, скажем, на пересечении — й строчки и — го столбца, и обозначим его через . По условию . Перебегаем к поиску цепочки из положительных частей матрицы , замыкающейся на элементе (разумеется, =0). Соединим стрелками со всеми положительными элементами его строчки, совокупа которых обозначим через . Потом любой из частей соединим стрелками со всеми положительными элементами, расположенными в его столбце. совокупа всех таковых частей обозначим через . процесс образования множеств длится до того времени, пока при неком p (p – нечетное число) посреди столбцов, содержащих элементы , обнаружится столбец с номером . Заметим, что в силу опорности плана огромного количества , не пересекаются, ибо в неприятном случае была бы замкнутая цепочка из ненулевых перевозок плана . Это событие, также то, что любые два пт невырожденной задачки T могут быть соединены коммуникациями с ненулевыми перевозками, служит подтверждением существования введенного выше числа . сейчас уже несложно образовать разыскиваемую цепочку. От элемента перейдем по столбцу к элементу . От по строке перейдем к соединенному с ним стрелкой элементу и т.д. Двигаясь таковым образом вдоль намеченных стрелок по строчкам и столбцам матрицы , получим в конце концов последовательность положительных частей данной для нас матрицы вида

, (4.1)

образующую цепочку, которая замыкается на элементе .

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

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

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

Обозначим совокупа пар индексов , через , а огромное количество пар индексов вида , через . Положим

. (4.2)

Новейший план определяется согласно правилу

(4.3)

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

Итак, в итоге — й итерации мы перебежали от плана и матрицы оценок

к усовершенствованному плану и к новейшей матрице

.

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

Блок-схема метода способа потенциалов.

5. Управление юзера.

Опосля пуска программки на дисплее возникает основное окно.

Жмем на клавишу «Добавить». Вводим объемы производства и употребления. Нажимая на левую клавишу мыши, перетаскиваем пункты производства и употребления. Нажимая на правую клавишу мыши, устанавливаем связи меж пт употребления и производства, устанавливаем тарифы.

Если все введено правильно, то жмем клавишу «Высчитать».

Заключение.

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

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

Перечень литературы

Гольштейн, Е.Г.
Линейное программирование./ Гольштейн, Е.Г., Юдин, Д.Б. Теория, способы и приложения. – М., Наука, 1969. – с. 424;

Грешилов, А.А.
Прикладные задачки математического программирования: учебное пособие для ВУЗов./ Грешилов, А.А. – М., Логос, 2006. – с. 286;

Зайченко, Ю.П.
исследование операций./ Зайченко, Ю.П. – 2-ое издание, перер. и доп. – Киев., Высшая школа, 1979. – с. 392;

Таха.
Введение в исследование операций./ Таха, Хэмди, А. – 6-е изд. — М., Изд. дом «Вильямс», 2001. – с. 912.

]]>