Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Способ наименьшего элемента в матрице
Этот способ заключается в том, что максимально возможная поставка заносится в клетку с самым минимальным элементом во всей матрице, затем выбирается следующий по величине минимальным элемент (расстояние) и в эту клетку заносится величина поставки с учетом соотношения спроса и ресурсов. Исходная программа перевозки кирпича па строительные площадки, составленная способом минимального элемента в матрице, приведена в табл. 15. Функционал полученного решения L(x) = 6 * 25 + 12 * 75 +5 * 75+16 * 25 + 18 * 75 + 14 * 50 + 12 * 150 +22 * 25 = 7625 т*км. Обычно способ наименьшего элемента в матрице дает допустимое решение, более близкое к оптимальному, чем способ северо-западного угла. В условии нашего примера суммарный объем транспортной работы меньше на 2050 т*км (96*75 - 7625 = 2050). Способ наименьшего элемента в матрице целесообразно использовать при решении небольших матриц, поскольку с увеличением размера матрицы его применение затрудняется. В данном случае хорошие результаты позволяет получить способ двойного предпочтения. Таблица 15
Способ двойного предпочтения Этот способ заключается в нахождении минимального элемента в столбце и его проверке на минимальность по строке таблицы. Если этот элемент окажется наименьшим и по столбцу, и по строке, то в данную клетку записывают максимально возможную поставку, и все элементы данной строки или столбца из дальнейшего рассмотрения исключают. Если минимальный элемент в столбце не является минимальным в строке, то временно этот столбец из рассмотрения опускают и переходят к следующему. После рассмотрения всех столбцов возвращаются к пропущенным и операции повторяют. Так поступают до тех пор, пока не будет получено базисное распределение. Базисное распределение, полученное способом двойного предпочтения, приведено в табл. 16. Допустимое распределение, полученное способом двойного предпочтения, обычно не отличается от распределения способом минимального элемента в матрице, что подтвердилось и в нашем случае: загрузки клеток и функциональные элементы совпали.
Способ аппроксимации Фогеля При этом способе первое допустимое распределение является близким к оптимальному и по сути является приближенным решением задачи. Таблица 16
При этом способе исходная матрица дополняется столбцом и строкой разностей. Затем в каждой строке и каждом столбце матрицы отыскивают два наименьших элемента и определяют абсолютную разность между ними, которую заносят соответственно разности по строке в столбец разностей, разности по столбцам - в строку разностей. Если две клетки в одной и той же строке или столбце имеют одинаковые значения элементов, то разность для этой строки или столбца принимается равной нулю и также проставляется в соответствующую строку или столбец. Затем выбирают наибольшую величину разности независимо от того, стоит ли она в столбце или строке разностей. В клетку с минимальным элементом в данной строке или столбце заносят максимально возможную загрузку, учитывая при этом соотношение ресурса поставщика и спрос потребителя. Наибольшая разность зачеркивается. Если окажется, что спрос потребителя полностью удовлетворен или ресурс поставщика полностью исчерпан, в соответствующей строке или столбце разностей проставляется буква К (конец) и данная строка или столбец матрицы из дальнейшего рассмотрения исключается. После заполнения клетки матрицы разности пересчитывают и операции повторяются вновь до тех пор, пока не будет составлена допустимая программа распределения. При наличии двух одинаковых наибольших разностей загрузку записывают в клетку, которая имеет меньший элемент по строке и столбцу. Такая клетка называется седловой. Последние распределения можно сделать без вычисления разностей, поскольку остается несколько незагруженных клеток, поставки в которые очевидны.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2021-03-09; просмотров: 96; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.119.133.228 (0.005 с.) |