Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Нахождение опорного решения методом минимального тарифа (минимальной стоимости)
Согласно этому методу грузы распределяются в первую очередь в те клетки, в которых находится минимальный тариф перевозок 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. Кроме вышерассмотренных методов существуют и другие приёмы составления опорного плана: · метод двойного предпочтения; · метод минимальной стоимости по столбцу или строке и др. · метод дфференциальных рент и др.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2017-01-25; просмотров: 287; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.138.141.202 (0.011 с.) |