Метод потенциалов

2.4 Метод потенциалов

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

Для данной задачи минимальным является метод наименьшей стоимости.

Опорный метод этого плана и будем использовать для решения задачи методом потенциалов:

Проверим оптимальность опорного плана. Найдем потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij

Для этого построим систему уравнений:

Из этой системы уравнений находим потенциалы , полагая, что u₁ = 0:

v1=0, v2=27, v3=18, v4=25, v5=24, u1=0, u1=-3, u3=6

Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых u_i + v_i > c_ij, (3;3): 6 + 18 > 23

Выбираем максимальную оценку свободной клетки (3;3): 23

Для этого в перспективную клетку (3;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.

Из грузов стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 90. Прибавляем 90 к объемам грузов, стоящих в плюсовых клетках и вычитаем 90 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

Проверим оптимальность опорного плана. Найдем потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij (Алгоритм нахождения потенциалов описан выше).

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

Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Подсчитаем затраты на распределение товаров:

F = 27*100 + 18*30 + 24*70 + 18*190 + 21*60 + 23*90 + 31*110 = 15080

Результат: Затраты на распределение товаров между магазинами найденные методом наименьшей стоимости составят 15080рублей.

Похожие работы

Транспортная задача линейного программирования

Скачать

47721

13

4

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

Разработка динамических моделей для транспортно-производственной системы

Скачать

38282

9

2

... 16 11 9 45 Радуга 15 15 12 20 Михайлово 2 6 20 Лебедево 7 3 55 Озерное 4 9 25 20 55 25 40 60 3. Разработка динамических моделей для транспортно-производственной системы.   3.1 Однопродуктовая многоэтапная транспортно-производственная модель. Возьмем из задачи, описанной выше, ...

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

Скачать

52995

4

2

... Основные направления совершенствования организации транспортного обеспечения в коммерческой деятельности ООО «Птица Плюс»   3.1 Недостатки организации транспортного обеспечения в коммерческой деятельности ООО «Птица Плюс»   Как и на любом другом предприятии в организации транспортного обеспечения на «Птице Плюс» существуют свои отрицательные моменты, устранив которые предприятие сможет более ...

Задачи маркетинга, решаемые автоматизированными системами

Скачать

74770

0

0

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