Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
II этап. Определение вводимой в базис переменной (“ме- тод потенциалов”).
Отметим, что “метод потенциалов” эквивалентен принци- пу решения задачи линейного программирования и исполь- зованию условия оптимальности в симплекс-методе. Сначала находят опорный план транспортной задачи, а затем его улуч- шают до получения “оптимального плана”. Содержание “мето- да потенциалов” заключается в следующем: 1. Каждой строке i и столбцу j транспортной таблицы ста- вится в соответствие числа ui и νj, называемые потенциалами. Они должны для каждой базисной переменной xij текущего ре- шения удовлетворять условию ui + νj = cij. Эти условия приво- дят к системе, состоящей из m + n − 1 уравнений (так как име- ется всего m + n − 1 базис-переменных), в которых фигурируют m + n неизвестных. Значение потенциалов определяют из этой системы уравнений, придавая одному из них произвольное значение (например, u1= 0). 2. Определяются оценки для небазисныx переменных в соответствии с соотношением: . 3. Если все оценки неположительны, то найденное ре- шение оптимально, в противном случае необходимо определить новую вводимую в базис переменную. 4. Вводимой в базис переменной является небазисная пе- ременная, имеющая самую большую положительную оцен- ку . Наиболее эффективным методом определения вводимой переменной является метод дифференциальных рент. Если при определении оптимального плана транспортной зада- чи методом потенциалов сначала находился какой-нибудь ее опорный план, а затем он последовательно улучшался, то при нахождении решения транспортной задачи методом диффе- ренциальных рент сначала наилучшим образом распределяют между пунктами назначения часть груза (так называемое ус- ловно оптимальное распределение) и на последующих итера- циях постепенно уменьшают общую величину нераспределен- ных поставок. Первоначальный вариант распределения груза определя- ют следующим образом. В каждом из столбцов таблицы дан- ных транспортной задачи находят минимальный тариф. Най- денные числа заключают в кружки, а клетки, в которых стоят указанные числа, заполняют. В них записывают максимально возможные числа. В результате получают некоторое распре- деление поставок груза в пункты назначения. Это распределе- ние в общем случае не удовлетворяет ограничениям исходной транспортной задачи. Поэтому в результате последующих ша- гов следует постепенно сокращать нераспределенные поставки груза так, чтобы при этом общая стоимость перевозок остава- лась минимальной. Для этого сначала определяют избыточные и недостаточные строки.
Строки, соответствующие поставщикам, запасы которых полностью распределены, а потребности пунктов назначения, связанных с данными потребителями запланированными пос- тавками, не удовлетворены, считаются недостаточными. Эти строки иногда называют также отрицательными. Строки, запа- сы которых исчерпаны неполностью, считаются избыточными. Иногда их называют также положительными. После того как определены избыточные и недостаточные строки, для каждого из столбцов находят разности между чис- лом в кружке и ближайшим к нему тарифом, записанным в из- быточной строке. Если число в кружке находится в положитель- ной строке, то разность не определяют. Среди полученных чисел находят наименьшее. Это число называется промежуточной рентой. После определения промежуточной ренты переходят к новой таблице. Эта таблица получается из предыдущей таблицы прибавлением к соответствующим тарифам, стоящим в отрица- тельных строках, промежуточной ренты. Остальные элементы остаются прежними. При этом все клетки новой таблицы счи- тают свободными. После построения новой таблицы начинают заполнение ее клеток. Теперь уже число заполняемых клеток на одну больше, чем на предыдущем этапе. Эта дополнительная клетка находится в столбце, в котором была записана промежу- точная рента. Все остальные клетки находятся по одной в каж- дом из столбцов и в них записаны наименьшие для данного стол- бца числа, заключенные в кружки. Заключены в кружки и два одинаковых числа, стоящих в столбце, в котором в предыдущей таблице, была записана промежуточная рента. Поскольку в новой таблице число заполняемых клеток больше, чем число столбцов, то при заполнении клеток сле- дует пользоваться специальным правилом, которое состоит в следующем. Выбирают некоторый столбец (строку), в котором имеется одна клетка с помещенным в ней кружком. Эту клет- ку заполняют и исключают из рассмотрения данный стол- бец (строку). После этого берут некоторую строку (столбец), в которой имеется одна клетка с помещенным в ней кружком. Эту клетку заполняют и исключают из рассмотрения данную строку (столбец). Продолжая так, после конечного числа шагов заполняют все клетки, в которых помещены кружки с заклю- ченными в них числами. Если к тому же удается распределить весь груз, имеющийся в пунктах отправления, между пункта- ми назначения, то получают оптимальный план транспортной задачи. Если же оптимальный план не получен, то переходят к новой таблице. Для этого находят избыточные и недостаточные строки, промежуточную ренту и на основе этого строят новую таблицу. При этом могут возникнуть некоторые затруднения при определении знака строки, когда ее нераспределенный ос- таток равен нулю. В этом случае строку считают положитель- ной при условии, что вторая заполненная клетка, стоящая в столбце, связанном с данной строкой еще одной заполненной клеткой, расположена в положительной строке.
После конечного числа описанных выше итераций нерас- пределенный остаток становится равным нулю. В результате получают оптимальный план данной транспортной задачи. Описанный выше метод решения транспортной задачи имеет более простую логическую схему расчетов, чем рас- смотренный выше метод потенциалов. Поэтому в большинстве случаев для нахождения решения конкретных транспортных задач с использованием электронно-вычислительных машин (ЭВМ) применяется метод дифференциальных рент.
|
||||||
Последнее изменение этой страницы: 2021-01-14; просмотров: 69; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.144.69.54 (0.006 с.) |