Транспортная задача и ее решение методом потенциалов - Решение оптимизационных экономических задач методами линейного программирования
Математическая модель транспортной задачи:
F = ??cIjXIj, (1)
При условиях:
- ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
1 |
2 |
3 |
4 |
Запасы | |
1 |
5 |
4 |
3 |
4 |
88 |
2 |
3 |
2 |
5 |
5 |
77 |
3 |
1 |
6 |
3 |
2 |
33 |
Потребности |
44 |
44 |
33 |
44 |
Проверим необходимое и достаточное условие разрешимости задачи.
- ?a = 88 + 77 + 33 = 198 ?b = 44 + 44 + 33 + 44 = 165
Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 33 (198--165). Тарифы перевозки единицы груза из базы во все магазины полагаем, равны нулю.
Занесем исходные данные в распределительную таблицу.
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
5 |
4 |
3 |
4 |
0 |
88 |
2 |
3 |
2 |
5 |
5 |
0 |
77 |
3 |
1 |
6 |
3 |
2 |
0 |
33 |
Потребности |
44 |
44 |
33 |
44 |
33 |
Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел aI, или bJ.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен 1
Для этого элемента запасы равны 33, потребности 44. Поскольку минимальным является 33, то вычитаем его.
X31 = min(33,44) = 33.
5 |
4 |
3 |
4 |
0 |
88 |
3 |
2 |
5 |
5 |
0 |
77 |
1 |
X |
X |
X |
X |
33 - 33 = 0 |
44 - 33 = 11 |
44 |
33 |
44 |
33 |
0 |
Искомый элемент равен 2
Для этого элемента запасы равны 77, потребности 44. Поскольку минимальным является 44, то вычитаем его.
X22 = min(77,44) = 44.
5 |
X |
3 |
4 |
0 |
88 |
3 |
2 |
5 |
5 |
0 |
77 - 44 = 33 |
1 |
X |
X |
X |
X |
0 |
11 |
44 - 44 = 0 |
33 |
44 |
33 |
0 |
Искомый элемент равен 3
Для этого элемента запасы равны 88, потребности 33. Поскольку минимальным является 33, то вычитаем его. x13 = min(88,33) = 33.
5 |
X |
3 |
4 |
0 |
88 - 33 = 55 |
3 |
2 |
X |
5 |
0 |
33 |
1 |
X |
X |
X |
X |
0 |
11 |
0 |
33 - 33 = 0 |
44 |
33 |
0 |
Искомый элемент равен 3
Для этого элемента запасы равны 33, потребности 11. Поскольку минимальным является 11, то вычитаем его.
X21 = min(33,11) = 11.
X |
X |
3 |
4 |
0 |
55 |
3 |
2 |
X |
5 |
0 |
33 - 11 = 22 |
1 |
X |
X |
X |
X |
0 |
11 - 11 = 0 |
0 |
0 |
44 |
33 |
0 |
Искомый элемент равен 4
Для этого элемента запасы равны 55, потребности 44. Поскольку минимальным является 44, то вычитаем его.
X14 = min(55,44) = 44.
X |
X |
3 |
4 |
0 |
55 - 44 = 11 |
3 |
2 |
X |
X |
0 |
22 |
1 |
X |
X |
X |
X |
0 |
0 |
0 |
0 |
44 - 44 = 0 |
33 |
0 |
Искомый элемент равен 0
Для этого элемента запасы равны 11, потребности 33. Поскольку минимальным является 11, то вычитаем его.
X15 = min(11,33) = 11.
X |
X |
3 |
4 |
0 |
11 - 11 = 0 |
3 |
2 |
X |
X |
0 |
22 |
1 |
X |
X |
X |
X |
0 |
0 |
0 |
0 |
0 |
33 - 11 = 22 |
0 |
Искомый элемент равен 0
Для этого элемента запасы равны 22, потребности 22. Поскольку минимальным является 22, то вычитаем его.
X25 = min(22,22) = 22.
X |
X |
3 |
4 |
0 |
0 |
3 |
2 |
X |
X |
0 |
22 - 22 = 0 |
1 |
X |
X |
X |
X |
0 |
0 |
0 |
0 |
0 |
22 - 22 = 0 |
0 |
1 |
2 |
3 |
4 |
5 |
Запасы | |
1 |
5 |
4 |
3[33] |
4[44] |
0[11] |
88 |
2 |
3[11] |
2[44] |
5 |
5 |
0[22] |
77 |
3 |
1[33] |
6 |
3 |
2 |
0 |
33 |
Потребности |
44 |
44 |
33 |
44 |
33 |
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 3*33 + 4*44 + 0*11 + 3*11 + 2*44 + 0*22 + 1*33 = 429
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем Предварительные потенциалы uI, vI. по занятым клеткам таблицы, в которых uI + vI = cIj, полагая, что u1 = 0.
U1 + v3 = 3; 0 + v3 = 3; v3 = 3
U1 + v4 = 4; 0 + v4 = 4; v4 = 4
U1 + v5 = 0; 0 + v5 = 0; v5 = 0
U2 + v5 = 0; 0 + u2 = 0; u2 = 0
U2 + v1 = 3; 0 + v1 = 3; v1 = 3
U3 + v1 = 1; 3 + u3 = 1; u3 = -2
U2 + v2 = 2; 0 + v2 = 2; v2 = 2
V1=3 |
V2=2 |
V3=3 |
V4=4 |
V5=0 | |
U1=0 |
5 |
4 |
3[33] |
4[44] |
0[11] |
U2=0 |
3[11] |
2[44] |
5 |
5 |
0[22] |
U3=-2 |
1[33] |
6 |
3 |
2 |
0 |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию uI + vI <= cIj.
Минимальные затраты составят:
F(x) = 3*33 + 4*44 + 0*11 + 3*11 + 2*44 + 0*22 + 1*33 = 429
Похожие статьи
-
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 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Транспортные задачи, имеющие некоторые усложнения в постановке - Экономико-математические методы
Транспортная задача с избытком запасов: Для отыскания оптимального плана вводят фиктивный (n+1)-й пункт назначения Bn+1 с потребностью bn+1 и полагают...
-
Второй раздел курсовой работы посвящен особенностям постановки и решения общей задачи линейного программирования, а именно, транспортной задаче (ТЗЛП)....
-
Решение: Строим на плоскости х1Ох2 многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки...
-
Как известно решение задач симплексным методом применяется очень часто. Это связано с тем, что симплексный метод подходит для решения широкого круга...
-
Вид сырья Запас сырья Количество единиц сырья, идущих на изготовление единицы продукции P1 P2 P3 P4 S1 4 1 1 1 3 S2 18 2 4 6 1 Прибыль от единицы...
-
Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы
Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент. При нахождении решения...
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой...
-
Введение - Решение оптимизационных экономических задач методами линейного программирования
Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных...
-
Пример решения транспортной задачи - Экономико-математические методы
На четырех строительных площадках В1, В2, В3, В4 монтируется в день соответственно 20,120,20 60 м3 сборных плит перекрытий. Производство этих плит...
-
Пусть имеется оптимизационная задача вида: (1) (2) (3) - задан(4) Здесь предполагается, что FJ(xJ,yJ)>0 для всех допустимых значений xJ,yJ. В этом случае...
-
Пример транспортной задачи линейного программирования - Оптимальное программирование
Транспортная задача -- математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из...
-
Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач
Постановка задачи. Пусть имеются N видов грузов с номерами. Единица груза j-го вида имеет все aJ. Если груз j-го вида берется в количестве xJ, то его...
-
Алгоритм решения ТЗ методом потенциалов - Экономико-математические методы
Построить опорный план по одному из правил. Проверить план на невырожденность. Если полученный план вырожденный, формально заполняют нулями некоторые из...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере. Итак, требуется найти легчайший простой основный...
-
Элементы матричного анализа - Методы решения системы линейных уравнений
Вектором, как на плоскости, так и в пространстве, называется направленный Отрезок , то есть такой Отрезок , один из концов которого выделен и называется...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
Метод северо-западного угла - Математическое моделирование в менеджменте и маркетинге
Этап I. Поиск первого опорного плана . 1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи. План начинается...
-
Исходная задача: При ограничениях: Двойственной является следующая задача: При ограничениях: Число неизвестных в двойственной задаче равно 2....
-
Литература - Решение оптимизационных экономических задач методами линейного программирования
1. Карпелович Ф. И., Садовский Л. Е. Элементы линейной алгебры и линейного программирования. - М.: Физматгиз, 1963. 2. Коротков М., Гаврилов М. "Основы...
-
Экономико-математические методы и моделирование в землеустройстве позволяют решать большой круг задач, связанных с оптимизацией территориальной...
-
Несмотря на требование линейности функций критериев и ограничений, в рамки линейного программирования попадают многочисленные задачи распределения...
-
Иногда необходимо управлять сложными комплексами взаимосвязанных работ, направленных на достижение определенных целей. Примерами таких комплексов в...
-
Известно оптимальное решение X*=(0;0;1;1) задачи линейного программирования: Составьте двойственную задачу и найдите ее оптимальное решение по теореме...
-
Экономические задачи, сводящиеся к транспортным моделям - Экономико-математические методы
Алгоритмы и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с...
-
Линейное программирование, Общая задача линейного программирования - Экономико-математические методы
Термин "линейное программирование" впервые появился в 1951 г. в работах американских ученых (Дж. Данциг, Т. Купманс), а первые исследования по линейному...
-
Так как целевая функция не является линейной, то эта задача является задачей нелинейного программирования. Найдем ее решение, используя геометрическую...
-
Динамическое программирование Динамическое программирование -- один из разделов оптимального программирования, в котором процесс принятия решения и...
-
Тема, с которой мы сегодня ознакомимся это "Применение матриц при решении экономических задач." Рассмотрим как с помощью матриц можно решать...
-
Постановка задачи - Экономико-математические методы
Пусть имеется m поставщиков А1, А2, ...,Аm однородного груза в количествах соответственно а1, а2,...,аm единиц и n потребителей В1, В2,...,Вn этого...
-
Необходимо найти минимальное значение целевой функции F = 4x1+18x2 > min, при системе ограничений: X1+4x2?14(1) X1+6x2?15(2) X1+x2?5(3)...
-
Задачей линейного программирования (ЛП) называется задача минимизации или максимизации линейного функционала при линейных ограничениях. В литературе...
-
Вводим дополнительные ограничения в модель: А) продукция типа 1 выпускается только в том случае, если разрешен выпуск хотя бы одного типа продукции: 2 и...
-
Некоторые особенности решения задач нелинейного программирования - Экономико-математические методы
Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой...
-
Приведем систему ограничений к каноническому виду, для этого необходимо неравенства преобразовать в равенства, с добавлением дополнительных переменных....
-
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные...
-
Большое число экономических и планово-производственных задач связано с распределением каких-либо, как правило, ограниченных ресурсов (сырья, рабочей...
-
Это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты (эффективность) возрастают или...
Транспортная задача и ее решение методом потенциалов - Решение оптимизационных экономических задач методами линейного программирования