Cтраница 1
Полученный новый опорный план транспортной задачи проверяют на оптимальность. Для этого определяют потенциалы пунктов отправления и назначения и находят числа а, р / - а, - с, для всех свободных клеток. Если среди этих чисел не окажется положительных, то это свидетельствует о получении оптимального плана. Если же положительные числа имеются, то следует перейти к новому опорному плану. В результате итерационного процесса после конечного числа шагов получают оптимальный план задачи. [1]
Целочисленность опорных планов транспортной задачи не связана с конкретным вычислительным алгоритмом, она имеет более глубокую природу. [2]
Следовательно, опорный план транспортной задачи может иметь не более п - - т - отличных от нуля неизвестных. [3]
В результате определяется новый опорный план транспортной задачи. Процесс продолжается до тех пор, пока план не станет оптимальным. [4]
Описанный выше переход от одного опорного плана транспортной задачи к другому ее опорному плану называется сдвигом по циклу пересчета. [5]
Действительно, из 1 и 2 сразу следует целочисленность всех опорных планов транспортной задачи, а это как раз то, что нам и нужно. [6]
Легко видеть, что этот процесс представляет собой известный метод минимального элемента для нахождения опорного плана транспортной задачи ( см. § 1 гл. Полученный таким образом план и предлагается принять за приближенный план задачи с фиксированными доплатами. [7]
В результате указанных выше перемещений грузов в пределах клеток, связанных циклом с данной свободной клеткой, определяют новый опорный план транспортной задачи. [8]
Если в результате составления плана поставок все имеющиеся запасы пунктов отправления распределены и потребности в пунктах назначения удовлетворены, то получен опорный план транспортной задачи. [9]
Общий принцип определения оптимального плана транспортной задачи методом потенциалов аналогичен принципу решения задачи линейного программирования симплексным методом, а именно: сначала находят опорный план транспортной задачи, а затем его последовательно улучшают до получения оптимального плана. [10]
При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. [11]
Как правило, применение метода апроксимации Фогеля позволяет получить либо опорный план, близкий к оптимальному, либо сам оптимальный план. Кстати, найденный выше опорный план транспортной задачи является и оптимальным. [12]
Из теоремы и леммы следует следующее утверждение. Если объемы производства а и объемы потребления bj - целые числа, то любой опорный план транспортной задачи состоит из целочисленных перевозок и среди оптимальных решений имеется хотя бы одно целочисленное решение. [13]
Сформулированная теорема позволяет построить алгоритм нахождения решения транспортной задачи. Он состоит в следующем. Пусть одним из рассмотренных выше методов найден опорный план транспортной задачи. [14]
Рассмотрим транспортную задачу, в которой в качестве поставщиков выступают только пункты 5i, i е G, а в качестве потребителей - пункты ф, j е Я. Тогда, пользуясь методом северо-западного угла, можно построить опорный план такой задачи, содержащий не более s t - 1 положительных компонент. Аналогично, рассматривая транспортную задачу для второй группы поставщиков и потребителей, построим опорный план, включающей не более ( т - s) ( п - t) - 1 перевозок. Совокупность всех введенных перевозок образует опорный план исходной транспортной задачи (6.1), содержащий не более ( т - s) ( n - t) - i s t - 1 перевозок. [15]