Алгоритм решения ТЗ методом потенциалов - Экономико-математические методы
Построить опорный план по одному из правил.
Проверить план на невырожденность. Если полученный план вырожденный, формально заполняют нулями некоторые из свободных клеток так, чтобы общее число занятых клеток было равно m+n-1. Нули надо расставлять так, чтобы не образовался замкнутый цикл из занятых клеток.
Проверка плана на оптимальность.
3.1. Определение потенциалов поставщиков и потребителей. Для всех занятых клеток рассчитываются потенциалы по формуле
(3.8)
Где ui - потенциалы поставщиков (строк), vj - потенциалы потребителей (столбцов).
Так как всех занятых клеток должно быть m+n-1, т. е. на единицу меньше числа потенциалов (их m+n), то для определения чисел ui, vj необходимо решить систему из m+n-1 уравнений ui+vj=cij c m+n неизвестными. Система неопределенная, и, чтобы найти частные решения, одному из потенциалов придают произвольное числовое значение (обычно полагают u1=0), тогда остальные потенциалы определяются однозначно.
3.2. Для всех свободных клеток рассчитываются оценки по формуле
) (3.9)
Здесь - реальные тарифы, а - косвенные тарифы.
Если все sто полученный план является оптимальным. При этом, если все sij>0, то полученный оптимальный план единственный. В случае, если хотя бы одна оценка sij=0, имеем бесчисленное множество оптимальных планов с одним и тем же значением целевой функции. Если хотя бы для одной свободной клетки, то план может быть улучшен. Переход к шагу 4.
4. Среди отрицательных оценок выбирается минимальная. Например, для клеток (i, j) и (k, l) имеем оценки: sij=-2, skl=-4. В этом случае наиболее потенциальной (перспективной) является клетка (k, l). Экономически оценка показывает, на сколько денежных единиц уменьшатся транспортные расходы от загрузки данной клетки единицей груза. Так, от загрузки клетки (i, j) единицей груза транспортные расходы уменьшаются на денежных единиц, а от загрузки единицей груза клетки (k, l) - на денежных единиц. Эффективность плана от загрузки потенциальной клетки грузом в единиц составит денежных единиц.
Для наиболее перспективной свободной клетки (клетки с min отрицательной оценкой) строится замкнутый цикл. Для этого из выбранной свободной клетки проводится по строке или столбцу прямая линия до любой занятой клетки, затем под углом 90линия проводится до следующей занятой клетки и так до тех пор пока цепь не замкнется в исходной клетке (цикл включает одну свободную клетку, остальные клетки цикла заняты. В цикле всегда четное число клеток. Каждое звено цепи соединяет две клетки строки (столбца). Для свободной клетки всегда можно построить единственный цикл. Если из занятых клеток образуется цикл, то план перевозок не является опорным. Цикл строится лишь для свободной клетки).
5. В вершинах цепи, чередуя проставляются знаки "+" и "-", начиная с выбранной свободной клетки (в нее помещают знак "+"). В клетках со знаком "-" выбирается минимальная поставка (, которая перераспределяется по цепи: там, где стоит знак "+" она прибавляется, а где "-" - отнимается. В результате чего баланс цикла не нарушается. Исходная свободная клетка становится занятой, а клетка в которой выбрана минимальная поставка - свободной (рис.3.1 а, б)
а) б)
+ - 20 20
40
- + 80
20 60
Рис.3.1
Может случится, что найденное наименьшее число ( одинаково для нескольких клеток цепи, помеченных знаком "-" (рис.3.2а). В этом случае во всех таких клетках (с минимальными стоимостями), кроме одной, нужно оставить нулевые (фиктивные) поставки (рис.3.2б).
а) б)
+ 4 - 3 33
20 20
- + 10 30
30 10
- 2 + 0 60
20 40
Рис.3.2
Составляется новый план, рассчитывается значение целевой функции. Переходим к шагу 2.
Похожие статьи
-
Пример решения транспортной задачи - Экономико-математические методы
На четырех строительных площадках В1, В2, В3, В4 монтируется в день соответственно 20,120,20 60 м3 сборных плит перекрытий. Производство этих плит...
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
A 25 40 50 30 45 20 7 3 4 8 6 60 5 7 2 3 5 45 1 4 10 2 6 70 3 4 2 7 8 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...
-
Построение исходного опорного плана - Экономико-математические методы
Моделирование экономический математический опорный Построение опорных планов, а также их преобразование будем производить непосредственно в...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...
-
Алгоритмы метода Монте-Карло для решения интегральных уравнений второго рода Пусть необходимо вычислить линейный функционал , Где, причем для...
-
Некоторые особенности решения задач нелинейного программирования - Экономико-математические методы
Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой...
-
Решение: Строим на плоскости х1Ох2 многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
Счетные и несчетные множества - Методы решения системы линейных уравнений
Пусть, например, А и В Ї некоторые множества. Тогда их возможные взаимоотношения можно рассмотреть в виде таблицы: Диаграмма Венна Диаграмма Венна...
-
Функции и ее свойства - Методы решения системы линейных уравнений
В современной математике понятие множества является одним из основных. Универсальность этого понятия в том, что под него можно подвести любую...
-
Элементы матричного анализа - Методы решения системы линейных уравнений
Вектором, как на плоскости, так и в пространстве, называется направленный Отрезок , то есть такой Отрезок , один из концов которого выделен и называется...
-
Метод северо-западного угла - Математическое моделирование в менеджменте и маркетинге
Этап I. Поиск первого опорного плана . 1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи. План начинается...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере. Итак, требуется найти легчайший простой основный...
-
Постановка задачи - Экономико-математические методы
Пусть имеется m поставщиков А1, А2, ...,Аm однородного груза в количествах соответственно а1, а2,...,аm единиц и n потребителей В1, В2,...,Вn этого...
-
Провести комплексное исследование численных методов для задачи решения нелинейных уравнений. 1. Решить нелинейные уравнения А) ; Б) ; В) . 2....
-
Свойства операции умножения матриц - Методы решения системы линейных уравнений
1)Умножение матриц не коммутативно, т. е. АВ ВА даже если определены оба произведения. Однако, если для каких - либо матриц соотношение АВ=ВА...
-
В процессе анализа и обобщения результатов исследований, проведенных в [4 - 10], стало ясно, что не все ситуации экспертного задания исходных параметров,...
-
Метод множителей Лагранжа - Экономико-математические методы
Среди задач (4.1)-(4.3) особое место занимают задачи типа (6.10) , (6.11) Для решения которых можно воспользоваться классическим методом оптимизации...
-
Иногда необходимо управлять сложными комплексами взаимосвязанных работ, направленных на достижение определенных целей. Примерами таких комплексов в...
-
Транспортные задачи, имеющие некоторые усложнения в постановке - Экономико-математические методы
Транспортная задача с избытком запасов: Для отыскания оптимального плана вводят фиктивный (n+1)-й пункт назначения Bn+1 с потребностью bn+1 и полагают...
-
Наличие особых ситуаций на террайне зависит от характеристик его сложности. Ниже приведена возможная классификационная схема характеристик сложности...
-
В большинстве реальных больших систем не обойтись без учета "состояний природы" -- воздействий Стохастического типа, случайных величин или случайных...
-
Экономико-математическая модель ТЗ - Экономико-математические методы
Рассмотрим ситуацию (3.1). Обозначим через количество единиц груза, которое необходимо доставить от i-го поставщика к j-му потребителю....
-
Линейное программирование в экономике - Экономико-математические методы
Задача о наилучшем использовании ресурсов. Пусть некоторая производственная единица (цех, завод, фирма и т. д.), исходя из конъюнктуры рынка, технических...
-
Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы
Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент. При нахождении решения...
-
Системы массового обслуживания -- это такие системы, в которые в случайные моменты времени поступают заявки на обслуживание, при этом поступившие заявки...
-
Основные методы экономическо-математического прогнозирования Кратко рассмотрим различные методы прогнозирования (предсказания, экстраполяции),...
-
Производной. - Методы решения системы линейных уравнений
Наиболее просто основные теоремы дифференциального исчисления формулируются для гладких функций. [ Править ] Производные и гладкие функции Пусть функция...
-
Метод дихотомии требует менее всего итераций цикла для получения корней уравнения с заданной точностью. Если расчет ведется без помощи ЭВМ, то это...
-
Все генетические алгоритмы участвовали в двух группах тестов. В каждой группе исследовались различные наборы значений управляющих параметров МГА:...
-
Элементарные преобразования, Миноры - Методы решения системы линейных уравнений
Определение. Элементарными преобразованиями матрицы назовем следующие преобразования: 1) умножение строки на число, отличное от нуля; 2) прибавление к...
-
Определители (детерминанты) - Методы решения системы линейных уравнений
Определение. Определителем квадратной матрицы А= называется число, которое может быть вычислено по элементам матрицы по формуле: Det A = , где (1) М1к -...
-
Методы построения решений по математическим моделям - Математическое моделирование в электромеханике
Системы дифференциальных уравнений, полученные для конкретных ти-пов электрических машин, содержат в скрытом виде исчерпывающую инфор-мацию о всех...
-
Матрицы и определители - Методы решения системы линейных уравнений
Определение. Матрицей размера mn, где m - число строк, n - число столбцов, называется таблица чисел, расположенных в определенном порядке. Эти числа...
-
Системы линейных уравнений - Методы решения системы линейных уравнений
Системой m линейных уравнений с n неизвестными называется система вида Где aIj и bI (i=1,...,m; b=1,...,n) - некоторые известные числа, а x1,...,xN -...
-
Пример решения задачи симплекс-методом, Условие задачи - Математические методы и модели в экономике
Рассмотрим алгоритм симплексного метода на примере решения задачи планирования товарооборота предприятия торговли. Требуется определить оптимальную...
-
Пусть имеется оптимизационная задача вида: (1) (2) (3) - задан(4) Здесь предполагается, что FJ(xJ,yJ)>0 для всех допустимых значений xJ,yJ. В этом случае...
-
Экономические задачи, сводящиеся к транспортным моделям - Экономико-математические методы
Алгоритмы и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с...
Алгоритм решения ТЗ методом потенциалов - Экономико-математические методы