Рефераты | Рефераты по математике | Транспортная задача линейного программирования | страница реферата 14 | Большая Энциклопедия Рефератов от А до Я
Большая Энциклопедия Рефератов от А до Я
  • Рефераты, курсовые, шпаргалки, сочинения, изложения
  • Дипломы, диссертации, решебники, рассказы, тезисы
  • Конспекты, отчеты, доклады, контрольные работы

  • 100

    120

    200

    700

    Выбор в качестве х минимального среди чисел, стоящих в отрицательных вершинах цикла, обеспечивает допустимость нового базиса.

    Если минимальное значение среди базисных неизвестных, стоящих в отрицательных вершинах цикла, принимается не в одной отрицательной вершине, то свободной оставляют только одну из них, а в других клетках с тем же минимальным значением пишут нули. В этом случае новое базисное решение будет вырожденным.

    Может случиться, что и само минимальное значение среди чисел в отрицательных клетках равно нулю. Тогда преобразование таблицы перевозок сведется к перестановке этого нуля в свободную клетку. Значения всех неизвестных при этом остаются неизменными, но решения считаются различными, так как различны базисы. Оба решения вырождены.

    Описанное выше преобразование таблицы перевозок, в результате которого преобразуется базис, называется пересчетом по циклу.

    Заметим, что неизвестные, не входящие в цикл, этим преобразованием не затрагиваются, их значения остаются неизменными и каждое из них остается либо в группе базисных, либо в группе свободных неизвестных, как и до пересчета.

    Выясним теперь, как пересчет по циклу влияет на общий объем затрат на перевозки и при каком условии эти затраты становятся меньше.

    Пусть Рефераты | Рефераты по математике | Транспортная задача линейного программирования – некоторое свободное неизвестное, для которого мы построили цикл и осуществили пересчет по циклу с некоторым числом Рефераты | Рефераты по математике | Транспортная задача линейного программирования. Если вершине цикла, находящейся в Рефераты | Рефераты по математике | Транспортная задача линейного программирования строке и Рефераты | Рефераты по математике | Транспортная задача линейного программирования столбце таблицы перевозок, приписан знак “+”, то значение неизвестного Рефераты | Рефераты по математике | Транспортная задача линейного программирования, находящегося в этой вершине, увеличивается на Рефераты | Рефераты по математике | Транспортная задача линейного программирования, что в свою очередь вызывает увеличение затрат на Рефераты | Рефераты по математике | Транспортная задача линейного программирования. где Рефераты | Рефераты по математике | Транспортная задача линейного программирования – тариф, соответствующий этой клетке; если же указанной вершине приписан знак “–”, то значение неизвестного Рефераты | Рефераты по математике | Транспортная задача линейного программирования уменьшается на Рефераты | Рефераты по математике | Транспортная задача линейного программирования, что вызывает уменьшение затрат на Рефераты | Рефераты по математике | Транспортная задача линейного программирования.

    Сложим тарифы, соответствующие положительным вершинам цикла, и вычтем из этой суммы сумму тарифов, соответствующих отрицательным вершинам цикла; полученную разность Рефераты | Рефераты по математике | Транспортная задача линейного программирования назовем алгебраической суммой тарифов для данного свободного неизвестного Рефераты | Рефераты по математике | Транспортная задача линейного программирования. Подсчет алгебраической суммы тарифов можно истолковать и так: припишем тарифам те же знаки, которые приписаны соответствующим вершинам цикла, тогда алгебраическая сумма тарифов равна сумме таких тарифов со знаком (“относительных тарифов”).

    Теперь, очевидно, мы можем, заключить, что в целом при пересчете но циклу, соответствующему свободному неизвестному Рефераты | Рефераты по математике | Транспортная задача линейного программирования общий объем затрат на перевозки изменится на произведение алгебраической суммы тарифов на Рефераты | Рефераты по математике | Транспортная задача линейного программирования, т. е. на величину Рефераты | Рефераты по математике | Транспортная задача линейного программирования. Следовательно, если алгебраическая сумма тарифов для некоторого свободного неизвестного Рефераты | Рефераты по математике | Транспортная задача линейного программирования отрицательна Рефераты | Рефераты по математике | Транспортная задача линейного программирования, то пересчет по циклу, соответствующему этому неизвестному, приводит к уменьшению общей суммы затрат на реализацию плана перевозок. Если же алгебраическая сумма тарифов положительна Рефераты | Рефераты по математике | Транспортная задача линейного программирования, то пересчет по соответствующему циклу приведет к увеличению общей суммы затрат. И, наконец, если алгебраическая сумма тарифов равна нулю Рефераты | Рефераты по математике | Транспортная задача линейного программирования, то пересчет по соответствующему циклу не изменит общую сумму затрат (два различных базисных плана требуют одинаковых затрат на их реализацию).

    Так, например, для цикла Рефераты | Рефераты по математике | Транспортная задача линейного программирования в рассмотренной задаче алгебраическая сумма тарифов

    Рефераты | Рефераты по математике | Транспортная задача линейного программирования.

    Значит, пересчет по этому циклу снижает расходы. И действительно, осуществив такой пересчет, мы получаем план, по которому объем перевозок в тонно-километрах составляет

    Рефераты | Рефераты по математике | Транспортная задача линейного программирования

    тогда как по исходному плану он составил Рефераты | Рефераты по математике | Транспортная задача линейного программирования. Имеем снижение объема перевозок на 1200 тонно-километров, что и следовало ожидать, так как алгебраическая сумма тарифов в данном случае равна –15, а пересчет по циклу осуществляется с помощью числа Рефераты | Рефераты по математике | Транспортная задача линейного программирования (изменение затрат равно Рефераты | Рефераты по математике | Транспортная задача линейного программирования).

    Вычисление алгебраической суммы тарифов для каждого из свободных неизвестных можно производить без построения соответствующего цикла, пользуясь, так называемыми, потенциалами. Припишем каждой базе Рефераты | Рефераты по математике | Транспортная задача линейного программирования, некоторое число Рефераты | Рефераты по математике | Транспортная задача линейного программирования и каждому потребителю Рефераты | Рефераты по математике | Транспортная задача линейного программирования некоторое число Рефераты | Рефераты по математике | Транспортная задача линейного программирования:

    Рефераты | Рефераты по математике | Транспортная задача линейного программирования,

    так что

    (4.1)

    Рефераты | Рефераты по математике | Транспортная задача линейного программирования,

    где Рефераты | Рефераты по математике | Транспортная задача линейного программирования – тарифы, соответствующие клеткам, заполненным базисными неизвестными. Эти числа Рефераты | Рефераты по математике | Транспортная задача линейного программирования и Рефераты | Рефераты по математике | Транспортная задача линейного программирования называются потенциалами соответствующих баз и потребителей.

    Зная потенциалы, легко вычислить алгебраическую сумму тарифов. Действительно, если в алгебраической сумме тарифов по циклу, соответствующему свободному неизвестному Рефераты | Рефераты по математике | Транспортная задача линейного программирования, заменить тарифы базисных клеток их выражениями через потенциалы по формулам (4.1), то, в силу чередования знаков при вершинах цикла, все потенциалы, кроме Рефераты | Рефераты по математике | Транспортная задача линейного программирования и Рефераты | Рефераты по математике | Транспортная задача линейного программирования сократятся, и мы получим:


    Рекомендуем скачать другие рефераты по теме: сайт рефератов, контрольная работа 7.



    Предыдущая страница реферата | 9  10  11  12  13  14  15  16  17  18  19 |




    Поделитесь этой записью или добавьте в закладки

       




    Категории:



    Разделы сайта




    •