Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Методы решения транспортной задачи с неправильным балансом
Решение транспортных задач с неправильным балансом Транспортные задачи с неправильным балансом могут быть двух типов. 1-й тип - сумма запасов в ПО превышает сумму поданных заявок: , т.е. имеет место транспортная задача с избытком запасов. 2-й тип - сумма поданных заявок ПН превышает наличные запасы
, т.е. имеет место транспортная задача с избытком заявок.
При решении обоих типов транспортных задач необходимо условия задачи привести к транспортной задаче с правильным балансом, с этой целью для задач первого типа, ввести в исходную транспортную таблицу фиктивный пункт назначения, для задач второго типа, ввести фиктивный пункт отправки. В дальнейшем алгоритмы решения транспортных задач как распределительным, так и методом потенциалов ни в чем не отличается от выше описанных. В заключительной транспортной таблице для первого типа транспортной задачи запасы в колонке фиктивного пункта назначения означают запасы не востребованные с соответствующих пунктов отправки. В заключительной транспортной таблице для второго типа транспортной задачи запасы в строке фиктивного пункта отправки означают не восполненные венные запасы для соответствующих пунктов назначения, в соответствии о поданными заявками. Рассмотрим решение транспортных задач с неправильным балансом на примере. Таблица 3.28
Решение
Разница между запасами и заявками равна: .
Введением фиктивного ПН В Ф с заявкой b Ф=38 сводим задачу к ТЗ с правильным балансом. Таблица 3.29
Таблица 3.30
Таблица 3.31
Таблица 3.31 (продолжение)
Таблица 3.32
План представленный в таблице 3.32 ляется оптимальным, т.к. во всех свободных клетках псевдостоимости не превосходят стоимостей. Согласно этому плану, из 50 единиц груза, имеющихся в пункте А 1, не перевозятся 32, а остальные 18 направляются в пункт В 1, из 40 единиц, имеющихся в пункте А 2: 6 не перевозятся, 1 отправляется в пункт В 2 и 33 – в пункт В 3. Все 20 единиц, имеющиеся в пункте А 3, направляются в пункт В 2. Метод запрещенных клеток 1. При составлении опорного плана перевозок «запретить себе» ставить отличные от нуля перевозки в клетки транспортной таблицы где стоят самые большие времена перевозок из ПО в ПН. 2. Свободные клетки транспортной таблицы с временем равным или большим чем время в базисных клетках перечеркнуть. 3. Попробовать улучшить план с помощью циклических перестановок в транспортной таблице, запретив себе дальнейшее использование перечеркнутых теток. 4. Если циклических перестановок в очередной транспортной таблице для улучшения плана перевозок сделать не удается, то базисная клетка с наибольшим временем перевозки определяет минимально-необходимое время для осуществления всех перевозок с ПО в ПН. Рассмотрим пример. Условия ТЗ по критерию времени (запасы, заявки и времена перевозок) даны в табл.3.33. Требуется найти план перевозок, укладывающихся в минимальное время, и указать это время. Таблица 3.33
Решение Начальный план перевозок можно было бы, как мы и делали раньше составить способом северо-западного угла, но мы видим, что при этом получится (за счет клетки (1,1)) очень большое время Т =10. Попытаемся этого избежать, «запретив» себе ставить отличные от нуля перевозки в клетки (1,1) и (4,1), где стоят самые большие времена в таблице (t 11=10 и t 41=11). Перечеркнем в табл.3.33. эти клетки. В плане (табл. 3.34.) время окончания всех перевозок равно 8 и достигается оно в клетке (3,2). Попробуем улучшить план, запретив себе для дальнейшего использования все клетки, где время tjj ≥ 8, и перечеркнув эти клетки. Перенесем 14 единиц груза по циклу, указанному в табл. 3.34, этим мы устраним перевозки со временем 8, получится план, приведенный в табл. 3.35, со временем окончания Т =7, клетка (3,3). Чтобы еще улучшить этот план, нам нужно устранить перевозки из клетки (3,3), запретив кроме того, перенос в клетку (1,5), содержащую то же время. 7 из 13 единиц, стоящих в клетке (3,3), устраняем переносом по циклу, показанному в табл. 3.35. Новый план приведен в табл. 3.36. Таблица 3.34
Таблица 3.35
Таблица 3.36
Попробуем избавиться от оставшихся 6 единиц в клетке (3,3) путем их циклического переноса. Для этого испробуем все возможные переносы из этой клетки, начинающиеся горизонтально или вертикально. Горизонтальный перенос в клетку (3,5) исключен, так как столбец 5 не содержит не запрещенных клеток. Горизонтальный перенос в клетку (3,1) также исключен, так как для этого пришлось бы уменьшить перевозки в клетке (2,1), что невозможно. Вертикальный перенос непосредственно, как можно убедиться, также не дает ни одного цикла, уменьшающего время перевозок. Из этого мы делаем заключение, что план перевозок, полученный в табл. 3.36, оптимален и минимальное время перевозок равно Tmin = 7.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2017-02-08; просмотров: 1105; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 34.238.138.162 (0.013 с.) |