Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы
Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент.
При нахождении решения транспортной задачи методом дифференциальных рент сначала наилучшим образом распределяются между пунктами назначения часть груза (так называемое условно оптимальное распределение) и на последующих интерациях постепенно уменьшают общую величину нераспределенных поставок. Первоначальный вариант распределения груза определяют следующим образом. В каждом из столбцов таблицу данных транспортной задачи находят минимальный тариф. Найденные числа заключают в кружки, а клетки, в которых стоят указанные числа, заполняют. В них записывают максимально возможные числа. В результате получают некоторое распределение поставок груза в пункты назначения. Это распределение в общем случае не удовлетворяет ограничениям исходной транспортной задачи. Поэтому в результате последующих шагов следует постепенно сокращать нераспределенные поставки груза так, что бы при этом общая стоимость перевозок оставалась минимальной. Для этого сначала определяют избыточные и недостаточные строки.
Строки, соответствующие поставщикам, запасы которых полностью распределены, а потребности пунктов назначения, связанных с данными потребителями запланированными поставщиками, не удовлетворены, считаются недостаточными. Эти строки иногда называют также отрицательными. Строки, запасы которых исчерпаны не полностью, считаются избыточными. Иногда их также называют положительными.
После того как определены избыточные и недостаточные строки, для каждого из столбцов находят разности между числом в кружке и ближайшем к нему тарифом, записанным в избыточной строке. Если число в кружке находится в положительной строке, то разность не определяют. Среди полученных чисел находят наименьшее. Это число называется промежуточной рентой. После определения промежуточной ренты переходят к новой таблице. Эта таблица получается из предыдущей таблицы прибавлением к соответствующим тарифам, стоящим в отрицательных строках, промежуточной ренты. Остальные элементы остаются прежними. При этом все клетки новой таблицы считают свободными. После построения новой таблицы начинают заполнение ее клеток. Теперь уже число заполняемых клеток на одну больше, чем на предыдущем этапе. Эта дополнительная клетка находится в столбце, в котором была записана промежуточная рента. Все остальные клетки находятся по одной в каждом из столбцов и в них записаны наименьшие для данного столбца числа, заключенные в кружки. Заключены в кружки и два одинаковых числа, стоящих в столбце, в котором в предыдущей таблице была записана промежуточная рента.
Поскольку в новой таблице число заполняемых клеток больше, чем число столбцов, то при заполнении клеток следует пользоваться специальным правилом, которое состоит в следующем. Выбирают некоторый столбец (строку), в котором имеется одна клетка с помеченным в ней кружком. Эту клетку заполняют и исключают из рассмотрения данный столбец (строку). После этого берут некоторую строку (столбец), в которой имеется одна клетка с помещенным в ней кружком. Эту клетку заполняют и исключают из рассмотрения данную строку (столбец). Продолжая так, после конечного числа шагов заполняют все клетки, в которых помещены кружки с заключенными в них числами. Если к тому же удается распределить весь груз, имеющийся в пунктах отправления, между пунктами назначения, то получают оптимальный план транспортной задачи. Если же оптимальный план не получен, то переходят к новой таблице. Для этого находят избыточные и недостаточные строки, промежуточную ренту и на основе этого строят новую таблицу. При этом могут возникнуть некоторые затруднения при определении знака строки, когда ее нераспределенный остаток равен нулю. В этом случае строку считают положительной при условии, что вторая заполненная клетка, стоящая в столбце, связанном с данной строкой еще одной заполненной клеткой, расположена в положительной строке.
После конечного числа, описанных выше интераций нераспределенный остаток становится равным нулю. В результате получают оптимальный план данной транспортной задачи.
Описанный выше метод решения транспортной задачи имеет более простую логическую схему расчетов, чем метод потенциалов. Поэтому в большинстве случаев для нахождения решения конкретных транспортных задач с использованием ЭВМ применяется метод дифференциальных рент.
Пример решения задачи.
Для транспортной задачи, исходные данные которой приведены в табл. 1.2.1, найти оптимальный план методом дифференциальных рент.
Таблица 1.2.1 Исходные данные транспортной задачи
Пункты отправления |
Пункты назначения |
Запасы | ||||
В1 |
В2 |
В3 |
В4 |
В5 | ||
А1 |
7 |
12 |
4 |
8 |
5 |
180 |
А2 |
1 |
8 |
6 |
5 |
3 |
350 |
А3 |
6 |
13 |
8 |
7 |
4 |
20 |
Потребности |
110 |
90 |
120 |
80 |
150 |
550 |
Решение. Перейдем от табл. 1.2.1 к табл. 1.2.2, добавив один дополнительный столбец для указания избытка и недостатка по строкам и одну строку для записи соответствующих разностей.
Таблица 1.2.2 Избытки и недостатки
Пункты отправления |
Пункты назначения |
Запасы |
Недостаток(-), Избыток(+) | ||||
В1 |
В2 |
В3 |
В4 |
В5 | |||
А1 |
7 |
12 |
|
8 |
5 |
180 |
+60 |
А2 |
|
|
6 |
|
|
350 |
-80 |
А3 |
6 |
13 |
8 |
7 |
4 |
20 |
+20 |
Потребности |
110 |
90 |
120 |
80 |
150 |
550 | |
Разности |
5 |
4 |
- |
2 |
1 |
В каждом столбце табл. 1.2.2 находим минимальные тарифы и обводим их кружками. Заполняем клетки, в которых стоят указанные числа. Для этого в каждую из клеток записываем максимально допустимое число. Например, в клетку, находящуюся на пересечении строки А1 И столбца В3, записываем число 120. В эту клетку нельзя поместить большее число, поскольку в таком случае были бы превышены потребности пункта назначения В3.
В результате заполнения отмеченных выше клеток получен так называемый условно оптимальный план, согласно которому полностью удовлетворяются потребности пунктов назначения В1, В2, В3 и В4 и частично - пункта назначения В5. При этом полностью распределены запасы пункта отправления А2, частично - пункта отправления А1 и остались совсем нераспределенными запасы пункта отправления А3.
После получения условно оптимального плана определяем избыточные и недостаточные строки. Здесь недостаточной является строка А2, так как запасы пункта отправления А2 полностью использованы, а потребности пункта назначения В5 удовлетворены частично. Величина недостатка равна 80 ед.
Строки А1 и А3 являются избыточными, поскольку запасы пунктов отправления А1 и А3 распределены не полностью. При этом величина избытка строки А1 равна 60 ед., а строки А3 - 20 ед. общая величина избытка 60+20=80 совпадает с общей величиной недостатка, равной 80.
После определения избыточных и недостаточных строк по каждому из столбцов находим разности между минимальными тарифами, записанными в избыточных строках, и тарифами, стоящими в заполненных клетках. В данном случае эти разности соответственно равны 5,4,2,1 (табл. 1.2.2). Для столбца В3 разность не определена, так как число, записанное в кружке в данном столбце, находится в положительной строке. В столбце В1 число, стоящее в кружке, равно 1, а в избыточных строках в клетках данного столбца наименьшим является число 6. Следовательно, разность для данного столбца равна 6-1=5. Аналогично находим разности для других столбцов: для В2 12-8=4; для В4 7-5=2; для В5 4-3=1.
Выбираем наименьшую из найденных разностей, которая является промежуточной рентой. В данном случае промежуточная рента равна 1 и находится в столбце В5. Найдя промежуточную ренту, переходим к табл. 1.2.3
Таблица 1.2.3 Промежуточная рента
Пункты отправления |
Пункты назначения |
Запасы |
Недостаток(-), Избыток(+) | ||||
В1 |
В2 |
В3 |
В4 |
В5 | |||
А1 |
7 |
12 |
|
8 |
5 |
180 |
+60 |
А2 |
|
|
7 |
|
|
350 |
-60 |
А3 |
6 |
13 |
8 |
7 |
|
20 |
-0 |
Потребности |
110 |
90 |
120 |
80 |
150 |
550 | |
Разности |
5 |
3 |
- |
2 |
1 |
В данной таблице в строках А1 и А3 (являющихся избыточными) переписываем соответствующие тарифы из строк А1 и А3 табл. 1.2.2. элементы строки А2 (которая была недостаточной) получаются в результате прибавления к соответствующим тарифам, находящимся в строке А2 табл. 1.2.2, промежуточной ренты, т. е. 1.
В таблице 1.2.3 число заполняемых клеток возросло на одну. Это обусловлено тем, что число минимальных тарифов, стоящих в каждом из столбцов данной таблицы, возросло на единицу, а именно в столбце В5 теперь имеются два минимальных элемента 4. Эти числа заключаем в кружки; клетки, в которых они стоят, следует запомнить. Необходимо заполнить и клетки, в которых в которых стоят наименьшие для других столбцов тарифы. Это клетки табл. 1.2.3, в которых соответствующие тарифы заключены в кружки. После того как указанные клетки определены, устанавливаем последовательность их заполнения. Для этого находим столбцы (строки), в которых имеется лишь одна клетка для заполнения. Определив и заполнив некоторую клетку, исключаем из рассмотрения соответствующий столбец (строку) и переходим к заполнению следующей клетки. В данном случае заполнение клеток проводим в такой последовательности. Сначала заполняем клетки А1В3, А2В1, А2В2, А2В4, так как они являются единственными клетками для заполнения в столбцах В1, В2, В3 и В4. После заполнения указанных клеток заполняем клетку А3В5, поскольку она является единственной для заполнения в строке А3. Заполнив эту клетку, исключаем из рассмотрения строку А3. Тогда в столбце В5 останется все лишь одна клетка для заполнения. Это клетка А2В5, которую заполняем. После заполнения клеток устанавливаем избыточные и недостаточные строки. Как видно из табл. 1.2.3, еще имеется нераспределенный остаток. Следовательно получен условно оптимальный план задачи и нужно перейти к новой таблице. Для этого по каждому их столбцов находим разности между числом, записанным в кружке данного столбца, и наименьшим по отношению к нему числом, находящимся в избыточных строках. Среди этих разностей наименьшая равна 1. Это и есть промежуточная рента. Переходим к следующей таблице (табл. 1.2.4).
Таблица 1.2.4 Оптимальный план транспортной задачи
Пункты отправления |
Пункты назначения |
Запасы |
Недостаток(-), Избыток(+) | ||||
В1 |
В2 |
В3 |
В4 |
В5 | |||
А1 |
7 |
12 |
|
8 |
|
180 |
0 |
А2 |
|
|
8 |
|
|
350 |
0 |
А3 |
7 |
14 |
9 |
8 |
|
20 |
0 |
Потребности |
110 |
90 |
120 |
80 |
150 |
550 |
В новой таблице элементы строк А2 и А3 получены в результате прибавления к соответствующим числам строк А2 и А3(являющихся недостаточными) табл. 1.2.3 промежуточной ренты, т. е 1. В результате в табл. 1.2.4 число клеток ля заполнения возросло еще на одну и стало равным 6. Определяем указанные клетки и заполняем их. Сначала заполняем клетки А1В3, А2В1, А2В2, А2В4, а затем А3В5, А2В5, А1В5. В результате все имеющиеся запасы поставщиков распределяются в соответствии с фактическими потребностями пунктов назначения. Число заполненных клеток равно 7, и вес они имеют наименьший показатель CIj. Следовательно получен оптимальный план исходной транспортной задачи:
X=
При этом плане перевозок общие затраты таковы:
S=4*120+5*60+1*110+8*90+5*80+3*70+4*20=2300.
Похожие статьи
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
Экономические задачи, сводящиеся к транспортной модели Транспортная модель используется для составления наиболее экономичного плана перевозок одного вида...
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере. Итак, требуется найти легчайший простой основный...
-
Решение: Строим на плоскости х1Ох2 многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки...
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач
Постановка задачи. Пусть имеются N видов грузов с номерами. Единица груза j-го вида имеет все aJ. Если груз j-го вида берется в количестве xJ, то его...
-
Технология разработки формы для ввода исходных данных средствами VBA Для разработки формы ввода исходных данных необходимо отобразить вкладку...
-
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 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...
-
Описание процесса решения - Формирование оптимального штата фирмы
На рабочем листе Excel в диапазоне ячеек от А1 до D4 в зависимости от выбранного количества предприятий размещаются исходные данные. Они будут...
-
С целью формализации задачи введем необходимые обозначения: I - код изделия (i = 1,...,n); ХI - искомый объем выпуска годовой программы по i-му изделию;...
-
Второй раздел курсовой работы посвящен особенностям постановки и решения общей задачи линейного программирования, а именно, транспортной задаче (ТЗЛП)....
-
Пример решения транспортной задачи - Экономико-математические методы
На четырех строительных площадках В1, В2, В3, В4 монтируется в день соответственно 20,120,20 60 м3 сборных плит перекрытий. Производство этих плит...
-
Комментарии к третьему разделу курсовой работы В третьем разделе курсовой работы студенту предлагается определить оптимальную стратегию заказа в условиях...
-
Введение - Формирование оптимального штата фирмы
Тема данного курсового проекта: "Формирование оптимального штата фирмы". Данная работа посвящена изучению теоретических вопросов, связанных с этой темой,...
-
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...
-
Как известно решение задач симплексным методом применяется очень часто. Это связано с тем, что симплексный метод подходит для решения широкого круга...
-
Введение - Приложение интегрального и дифференциального исчисления к решению прикладных задач
Целью данной курсовой работы является самостоятельное изучение следующих разделов высшей математики: задачи линейного программирования (симплексный и...
-
Инвестиционный портфель оптимальный многокритериальный В качестве тестового примера использовались следующие входные данные [Социальная сеть инвесторов,...
-
Теория: Применяется, как правило, для задач линейного программирования, содержащих не более 2 переменных. Суть геометрического метода сводится к...
-
Решение смешанной задачи для уравнения теплопроводности методом конечных разностей
Решение смешанной задачи для уравнения теплопроводности методом конечных разностей 1. Цель работы Ознакомление с методами решения смешанных задач для...
-
Пусть имеется оптимизационная задача вида: (1) (2) (3) - задан(4) Здесь предполагается, что FJ(xJ,yJ)>0 для всех допустимых значений xJ,yJ. В этом случае...
-
Задание. Рассматривается вычислительная система состоящая из n вычислительных машин. Имеется n задач. Задана матрица T определяющая время решения i-й...
-
Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах
Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе...
-
Элементы матричного анализа - Методы решения системы линейных уравнений
Вектором, как на плоскости, так и в пространстве, называется направленный Отрезок , то есть такой Отрезок , один из концов которого выделен и называется...
-
Регрессия -- зависимость среднего значения какой-либо величины от некоторой другой величины или от нескольких величин. Задача регрессионного анализа...
-
Решение симплекс-методом с помощью симплекс-таблиц - Математические методы и модели в экономике
Определим оптимальный план выпуска продукции, решив задачу линейного программирования (ЗЛП). Для этого сначала приведем модель к каноническому виду...
-
Наличие особых ситуаций на террайне зависит от характеристик его сложности. Ниже приведена возможная классификационная схема характеристик сложности...
-
Вводим дополнительные ограничения в модель: А) продукция типа 1 выпускается только в том случае, если разрешен выпуск хотя бы одного типа продукции: 2 и...
-
Экономические задачи, сводящиеся к транспортным моделям - Экономико-математические методы
Алгоритмы и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с...
-
Динамическое программирование Динамическое программирование -- один из разделов оптимального программирования, в котором процесс принятия решения и...
-
Эконометрика контроллинг анализ технология Почему старые методы эконометрики не подходят для новых условий? При взгляде на эконометрику со стороны часто...
-
Транспортная задача - Экономико-математические методы
Методы линейного программирования, являются хорошим инструментом для решения ряда проблем распределения ресурсов. Применение пакетов прикладных программ...
-
Все генетические алгоритмы участвовали в двух группах тестов. В каждой группе исследовались различные наборы значений управляющих параметров МГА:...
-
Вид сырья Запас сырья Количество единиц сырья, идущих на изготовление единицы продукции P1 P2 P3 P4 S1 4 1 1 1 3 S2 18 2 4 6 1 Прибыль от единицы...
-
По продаже системного блока компьютера на базе процессора Celeron в одном из магазинов фирмы N за месяц сложилась следующая ситуация: Цена (тыс. рублей)...
-
Формирование З -областей в матрице R осуществляется в процессе ее эволюционной модификации. Эволюционная модификация матрицы R производится путем...
-
Метод дихотомии требует менее всего итераций цикла для получения корней уравнения с заданной точностью. Если расчет ведется без помощи ЭВМ, то это...
Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы