Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Существует два вида постановки — матричная и сетевая. В матричной постановке провоз разрешается только от производителя к потребителю. В сетевой постановке провоз может осуществляться в любом направлении пункты могут быть транзитными. Задача формулируется как [1]. При использовании свалки см. Двойственные переменные симплекс-метода для транспортной задачи называются потенциалами. С экономической точки зрения это можно трактовать как стоимость продукта в точке потребления. Добавление дуги приводит к возникновению цикла в дереве. Увеличение провоза по вводимой дуге приводит к пересчету потоков в цикле, провоз по одной из дуг при этом уменьшится до нуля. Дугу с нулевым потоком удаляем из базиса, при этом базисный граф остаётся деревом цикл разрывается. Обычно в постановке сумма производства больше суммы потребления. Для решения незамкнутых задач, а также для простоты получения начального базисного плана используется метод искусственного базиса [4]. Дуги на свалку от пунктов производства соответствуют дополнительным переменным в симплекс-методе, а дуги со свалки к пунктам потребления соответствуют искусственным переменным. Выберем дугу, инцидентную i. Поток по дуге положим равным минимуму из объёмов производства и потребления на концах дуги. Уменьшим эти объёмы на величину потока по дуге. Вершину с нулевым объёмом устраним из рассмотрения вместе с инцидентными ей дугами. Переходим к пункту 2. Если вершины производств и потребления перенумерованы и каждый раз выбирается дуга с наименьшим номером, метод называется методом северо-западного угла [5]. Определение выводимой дуги и пересчет потенциалов достаточно эффективно реализуется. Если дуга не найдена, уменьшаем барьер до максимальной найденной невязки и соответствующую дугу вводим в базис. На следующем шаге проверяются только отобранные дуги. Определитель базисной матрицы всегда равен 1, так что при целочисленных данных задача дает целочисленные решения. Небольшое усложнение алгоритма может позволить решить задачу с ограничениями на пропускную способность [6]. Алгоритм очень похож на стандартный метод потенциалов. Насыщенная дуга должна не удовлетворять критерию оптимальности, в противном случае поток по ней следует уменьшать. Остальные дуги проверяются на критерий так же, как и в стандартном варианте. Так же, как и в стандартном алгоритме, в обоих случаях появляется контур, в котором следует изменять поток уменьшать для выбранной дуги в случае вывода дуги из насыщенных и увеличивать в случае обычной дуги. Материал из Википедии — свободной энциклопедии. Алгоритмы решения экстремальных задач. Линейное программирование, его применения и обобщения. Линейное программирование методы и приложения. Перевод с английского Гольштейна Е. Под редакцией Юдина Д. Государственное издательство физико-математической литературы А. Руководство к решению задач по математическому программированию. Руководство к решению задач. Изд-во НГТУ, Панюков А. Для улучшения этой статьи желательно: Найти и оформить в виде сносок ссылки на независимые авторитетные источники , подтверждающие написанное. Статьи без ссылок на источники Википедия: Статьи без источников тип: Статьи к викификации Страницы, использующие волшебные ссылки ISBN. Навигация Персональные инструменты Вы не представились системе Обсуждение Вклад Создать учётную запись Войти. Пространства имён Статья Обсуждение. Просмотры Читать Править Править вики-текст История. На других языках Добавить ссылки. Эта страница последний раз была отредактирована 10 мая в Текст доступен по лицензии Creative Commons Attribution-ShareAlike ; в отдельных случаях могут действовать дополнительные условия. Свяжитесь с нами Политика конфиденциальности Описание Википедии Отказ от ответственности Разработчики Соглашение о cookie Мобильная версия.
В данной статье разберемся с решением транспортной задачи. Все действия будем выполнять пошагово с очень подробными пояснениями. Дадим определение, аналогичное тому, которое дано в ваших учебниках или лекциях. Чтобы не загромождать страницу большим объемом пояснений, разобью весь материал на несколько частей - блоков. Существует несколько методов решения транспортной задачи. Мы будем подробно рассматривать два из них:. Определение опорного плана, в свою очередь, можно выполнить несколькими способами. Мы рассмотрим два из них: У нас есть некоторый груз, который находится на складах: Этот груз нам необходимо развести по магазинам: Нам выгоднее как можно эффективнее выполнить работу, то есть найти такой вариант перевозки, при котором затраты будут минимальными. Рассмотрим постановку транспортной задачи, то есть что дано в условии и переведем ее с математического языка на язык, понятный нам. Это наши "склады" - пункты отправления: Далее имеем дело с пунктами назначения - с "магазинами". В нашем случае их 4 штуки: Числа внутри таблицы - матрица стоимостей, или по другому, расценки перевозки 1 единицы груза из соответствующих пунктов. Эти значения также могут интерпритироваться как расстояния между соответствующими пунктами. Подробности — в условии решаемой задачи. Например, для перевозки 1 единицы груза из пункта отправления "склада" А 2 в пункт назначения "магазин" В 3 надо заплатить 4 условные единицы стоимости, например 4 руб. Аналогично, мы заплатим 6 рублей за перевозку 1 единицы груза из "склада" А 1 в "магазин" В 4. Или та же самая задача может быть задана сразу в более понятном виде: Возможна текстовая постановка задачи. В этом случае необходимо самим заполнять все ячейки таблицы, исходя из заданных в условии значений. Называется он так потому, что заполнение таблицы начинается с самой верхней левой северо-западной ячейки. Перед тем, как распределять ресурсы по "магазинам", проверим, равны ли общие потребности имеющимся ресурсам? В этом случае говорят, что транспортная задача закрытая. Решение открытой транспортной задачи рассмотрим чуть позже. Начнем нахождение опорного решения: В магазин В 1 требуется 50 единиц товара. Со склада А 1 отправим в этот магазин 50 единиц. Потребности магазина В 1 выполнены, следовательно, нет необходимости везти туда груз со склада А 2. На складе А 1 еще осталось 50 единиц груза. Эти остатки можем направить в магазин В 2. Ресурсы склада А 1 исчерпаны. Потребности магазинов в товаре полностью выполнены! Рассмотрели северо-западный метод построения первоначального плана опорного решения. Суть метода состоим в том, чтобы в первую очередь направлять груз в те пункты, где "расценки" в матрице стоимостей минимальны. Если клеток с наименьшими тарифами несколько, то заполняется любая из них. Остатки на складе А 2 — единиц. Потребности магазина В 2 выполнены. Размер поставки равен потребности магазина — Остается только раскидать груз со склада А 1 по магазинам: Получили два опорных плана: Видим, суммарные значения элементов каждого столбца равны соответствующим потребностям магазинов. Несмотря на то, что опорные планы разные, оба приведут к одному оптимальному решению или же к решениям, имеющим одну стоимость перевозки. Описанную ниже последовательность действий будем повторять несколько раз, с каждым шагом приближаясь к оптимальному решению. Начнем с проверки опорного плана на оптимальность. Далее строим рядом две таблицы. Размерность таблиц как и в матрице стоимостей:. Припишем каждой строке правой таблице потенциалы u 1 , u 2. Каждому столбцу — потенциалы v 1 , v 2 , v 3 , v 4. Для вычисления этих потенциалов в некоторых учебниках составляют систему и из нее определяют неизвестные покажу на данном шаге. Составим систему уравнений по следующему правилу: Каждое из значений в ячейке правая таблица равно сумме потенциалов соответствующей строки и соответствующего столбца. Тогда сумма потенциалов 1-й строки u 1 и 1-ого столбца v 1 равна 4. Значение 3 находится в первой строке потенциал u 1 , втором столбце потенциал v 2. Аналогично для каждого значения таблицы составим уравнение. Для того, чтобы система имела единственное решение, примем значение одного из потенциалов равным нулю. Значение 4 базисной ячейки находится во 2-й строке, 3-м столбце, тогда рассмотрим сумму соответствующих потенциалов. Свободные ячейки подчиняются тому же правилу суммирования потенциалов. Согласно критерию оптимальности, решение выше не оптимально, так как в оценочной таблице присутствует отрицательное значение. Дабы не загромождать решение множеством таблиц, оценочная матрица в нашем решении будет "вписана" в правую таблицу. Подчеркнутые значения - базисные ячейки, как сказано выше, значения оценочной матрицы в базисных ячейках равны нулю, нули писать не будем. Выделенные значения - значения оценочной матрицы в свободных ячейках, среди них ищем отрицательные значения. Для перехода к следующему опорному решению выполним следующее построим цикл пересчета: Если мы поставим этот "плюс" в столбце В3, то цепочка порвется, так как в этом же столбце невозможно поставить "минус" — нет заполненной ячейки. Далее обратимся к ячейкам, содержащим "минусы". Среди значений этих ячеек найдем минимальное: Алгоритм проверки плана на оптимальность и построение цикла пересчета очень подробно расписан в шаге 1. Для полученного опорного решения строим вспомогательную — правую таблицу и заполняем значениями из матрицы стоимостей базисные ячейки. Для этого из значений матрицы стоимостей вычитаем найденные значения соответствующих свободных ячеек. Закрытая транспортная задача размерностью 2х2. Закрытая транспортная задача размерностью 3х4. Закрытая транспортная задача размерностью 2х3. Закрытая транспортная задача размерностью 4х5. Бесплатные задачи по статистике. Готовые контрольные по статистике. База решенных задач по статистике. Оценить работу Заполнить форму. Бесплатные задачи по эконометрике. Готовые контрольные по эконометрике. Бесплатные задачи по матметодам в экономике. Готовые контрольные по матметодам в экономике. База решенных задач по матметодам в экономике. Бесплатные задачи по теории вероятностей. Готовые контрольные по теории вероятностей. База решенных задач по теории вероятности. Информатика в Excel Готовые решения. Химия Шиманович Готовые решения. Физика Готовые решения Прокофьев. Решебник по термеху Тарг Как решить транспортную задачу? Далее Вводная часть, с которой желательно ознакомиться. Мы будем подробно рассматривать два из них: Решение задачи методом потенциалов происходит в несколько этапов: Применение к найденному опорному решению самого метода потенциалов. О чем говорится в определении транспортной задачи? Рассмотрим пример решения транспортной задачи подробно. Транспортная задача задается следующей таблицей: Далее, что означают числа в условии транспортной задачи? И соответственно потребности каждого из магазинов - потребности пунктов назначения: Далее - Методы определения первоначального плана транспортной задачи. Рассмотрим самый распространенный метод получения опорного плана - метод северо-западного угла. Переходим к складу А 2. Получен опорный первоначальный план транспортной задачи. Далее опишем метод минимальных стоимостей получения опорного плана. Направляем единиц груза из склада А 2 в магазин В 2. Первый опорный план по методу северо-западного угла: Второй опорный план по методу минимальных стоимостей: Далее проверим правильность вычисления первоначального плана. Далее применим метод потенциалов к обоим опорным планам и сравним получившиеся ответы. Выпишем матрицу стоимостей , данную в условии задачи. Размерность таблиц как и в матрице стоимостей: Заполняем первую — левую таблицу в соответствии с полученным опорным планом. Переходим в правую таблицу. Переносим из матрицы стоимостей значения, которые соответствуют занятым клеткам левой таблицы. В матрице стоимости эти значения подчеркнуты. Мы будем определять значения потенциалов непосредственно из правой таблицы. Для удобства в качестве этого потенциала всегда будем брать v 4. Тогда система уравнений будет выглядеть: Решим систему уравнений и получим значения потенциалов: Так как система очень проста, то значения потенциалов можно получить и устно. Значение 2 равно сумме потенциалов 2-й строки и 2-го столбца: Далее приступим к заполнению пустых ячеек свободные ячейки правой таблицы. Вычислим оценочную матрицу, по которой узнаем, оптимален ли рассматриваемый план. Из каждого элемента матрицы стоимостей вычтем соответствующий элемент правой таблицы: Заметим, что в базисных ячейках всегда получим нули. Применим к нашей таблице: В столбце В 4 есть "плюс", следовательно в этом столбце должен быть и "минус". Аналогично, в строке А 2 есть "минус", следовательно должен быть и "плюс". Получили замкнутый цикл чередующихся знаков. Общее количество заполненных базисных ячеек при пересчете не должно изменится! Получили следующий опорный план: Вычислим стоимость перевозки на первом шаге. Для этого найдем сумму произведений значений опорного плана и матрицы стоимостей. Далее решение задачи будем излагать менее детально. Вычисляем потенциалы строк и столбцов: По правилу суммирования соответствующих потенциалов, заполняем свободные ячейки. Вычисляем оценочные значения в свободных ячейках. Среди оценочных значений нет отрицательных, следовательно план перевозки оптимален. Закрытая транспортная задача размерностью 2х2 Закрытая транспортная задача размерностью 3х4 Закрытая транспортная задача размерностью 2х3 Закрытая транспортная задача размерностью 4х5. Вырожденность опорного плана транспортной задачи. Теоретические работы Справочные данные Списки литературы Оценить работу Карта сайта Контакты. Главная Другое Математика Как решить транспортную задачу?
Реферат: Решение задач транспортного типа методом потенциалов
https://gist.github.com/47ca5258c0111ee8af1798830435c797
Лампа бактерицидная philips tuv 15w технические характеристики
https://gist.github.com/27b29b6c573f57dfb7f1ff70f93479bb