Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Нахождение опорного решения методом минимального тарифа (минимальной стоимости)
Согласно этому методу грузы распределяются в первую очередь в те клетки, в которых находится минимальный тариф перевозок Cij. Далее поставки распределяются в незанятые клетки с наименьшими тарифами с учетом оставшихся запасов у поставщиков и удовлетворения спроса потребителей. Процесс распределения продолжается до тех пор, пока все грузы от поставщиков не будут вывезены, а потребители не будут удовлетворены. При распределении грузов может оказаться, что количество занятых клеток меньше чем m+n-1. В этом случае недостающее их число заполняется клетками с нулевыми поставками, такие клетки называют условно занятыми. Нулевые поставки помещают в незанятые клетки с учетом наименьшего тарифа таким образом, чтобы в каждой строке и каждом столбце было не менее чем по одной занятой клетке. Рассмотрим нахождение исходного опорного решения транспортной задачи на конкретном примере.
На каждом шаге будем делать поставку в клетку с наименьшей стоимостью перевозки единицы груза среди всех незаполненных клеток. Шаг 1. Среди всех незаполненных клеток у клетки (2,2) наименьшая стоимость перевозки груза – 1. Поэтому делаем поставку в эту клетку min (190,120)=120. Исключаем 2-й столбец как полностью «удовлетворенный».
Шаг 2. Среди всех незаполненных клеток у клеток (1,3) и (2,3) наименьшая стоимость перевозки единицы груза – 2. Для клетки (1,3) min (30,150)=30. Для клетки (2,3) min(190-120,150)=70. Выбираем ту клетку, куда можно сделать наибольшую поставку. Так как 70>>30, то это клетка (2,3). Исключаем 2-ю строку как полностью «использованную»:
Среди всех незаполненных клеток у клетки (1,3) наименьшая стоимость перевозки единицы груза – 2. min (30,150 – 70)=30. Исключаем 1-ю строку как полностью «использованную»:
И т.д. Окончательный вариант:
Число отмеченных клеток = число строк + число столбцов – 1: 6=3+4–1. Стоимость перевозки равна: 2*30+1*120+2*70+5*70+3*50+7*130=1730. Нахождение опорного плана методом Фогеля. Метод Фогеля предусматривает введение штрафов строк (di) и штрафов столбцов (dj). Каждый штраф определяется как разность между минимальным элементом рассматриваемой строки (столбца) и следующим по величине. Вычеркнутые строки и столбцы в рассмотрение не принимают. Перевозку осуществляют в клетку, лежащую на строке (в столбце) с максимальным штрафом и имеющую минимальную стоимость перевозки. Далее при необходимости реализуют вычёркивание строк и столбцов, и все штрафы пересчитываются заново. Алгоритм заканчивается, когда все перевозки реализованы. Шаги алгоритма представлены ниже. Шаг 1. Рассчитываем штрафы строк и столбцов:
Максимальный штраф в столбце 2. Минимальный элемент этого столбца – 1. Загружаем его максимально возможным количеством груза – 120. Получаем следующую таблицу:
Шаг 2. Убираем столбец 2, одновременно уменьшаем количество груза у второго поставщика (строка 2) на 120 единиц и пересчитываем штрафы.
Загружаем клетку с тарифом 3 в строке 3 максимально возможным количеством груза – 150, получаем таблицу:
Шаг 3. Убираем отмеченный столбец, одновременно уменьшаем количество груза у третьего поставщика на 150 и пересчитываем штрафы.
Загружаем клетку А3В1 70 единицами груза, получаем:
Шаг 4. На этом шаге после исключения первого потребителя остается столбец В 4, в клетки которого загружаем оставшееся количество груза.
В итоге получаем опорный план:
Стоимость перевозки – 1500. Кроме вышерассмотренных методов существуют и другие приёмы составления опорного плана: · метод двойного предпочтения; · метод минимальной стоимости по столбцу или строке и др. Date: 2015-07-27; view: 591; Нарушение авторских прав |