Реферат на тему Реферат+презентация по предмету «Оценка эффективности сложных организационно-технических систем» (Тема — «Транспортная задача и методы ее решения»)

Содержание:

Введение 3
1. Определение транспортной задачи 5
2. Решение однопродуктовых и многопродуктовых транспортных задач 9
3. Симплекс-метод в применении к транспортным задачам 18
3.1. Сущность и описание симплексного метода 18
3.2. Симплекс-метод в решении транспортной задачи 24
Заключение 31
Список использованной литературы 34

Введение:

На текущий момент большое количество предприятий заняты в сфере перевозки продукции для ее последующей реализации. В связи с этим, важнейшую роль в современной экономике играют процессы оптимизации грузоперевозок, направленные на минимизацию финансовых затрат на доставку товаров. Данной проблемой занимается специализированная дисциплина — линейное программирование, точнее такое его направление, как решение транспортной задачи.
Основной задачи транспортной логистики является перемещение необходимого количества груза (продукции) в необходимую точку посредством оптимального маршрута за необходимое количество времени и с минимальными финансовыми издержками.
Исторически первой, и наиболее изученной на данный момент транспортной моделью является классическая транспортная задача перевозки одного вида товара, то есть однопродуктовая транспортная задача. Для данной модели была разработана развитая теория и эффективные модификации прямого и двойственного симплексметода, по-другому называемые метод потенциалов и венгерский метод. Последующее изучение данного класса задач происходило, в первую очередь, по направлению многоиндексных транспортных моделей, с помощью которых описываются ситуации перевозки груза разными видами транспорта, перевозка нескольких видов груза, динамические задачи перевозок и ряд прочих задач. Однако, многоиндексные транспортные модели не способны отразить всех особенностей, связанных с перевозкой разнородных грузов. С практической же точки зрения такие задачи более естественны, нежели однопродуктовые.
Целью данной работы является изучение транспортной задачи линейного программирования, также и методов ее решения.
Для достижения поставленной цели необходимо решить ряд задач:
• Раскрыть сущность транспортной задачи в линейном программировании,
• Рассмотреть характерные черты и признаки однопродуктовых и многопродуктовых транспортных задач, а также методов их решения,
• Проанализировать симплекс-метод в применении к транспортным задачам.
Объектом исследования в данной работе является транспортная задача линейного программирования.
Предмет исследования – методы решения транспортных задач различного вида.
В структуру работы входит: введение, основная часть, состоящая из трех глав, заключение и список использованной литературы.

Заключение:

Исходя из рассмотренного в работе материала, можно сделать ряд выводов:
1) Распространено решение транспортной задачи посредством линейного программирования. Сущность данной задачи состоит в минимизации затрат, которые возникают при эксплуатации транспортных средств в условиях ограничений относительно количества данных транспортных средств, продолжительности работы, грузоподъемности и т.д.
2) однопродуктовые и многопродуктовые транспортные задачи представляют собой важное средство решения большинства экономических проблем, которые возникают перед современными предприятиями. С их помощью возможно не только рациональное планирование путей, но и устранение дальних, повторных перевозок. Это ведет к более быстрой доставке товаров, сокращению затрат производства на топливо, ремонт машин, то есть к сокращению транспортных издержек.
В однопродуктовых транспортных задачах речь идет о перевозках какого-то одного груза. В многопродуктовых же задачах рассматриваются перевозки грузов нескольких видов. Конечно, это больше соответствует реальной ситуации.
3) Транспортные задачи относятся к задачам линейного программирования и могут быть решены известным симплексным методом. Однако, обычная транспортная задача имеет большое число переменных и решение ее симплексным методом громозко. С другой стороны матрица системы ограничений транспортной задачи весьма своеобразна, поэтому для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить последовательность опорных решений, которая завершается оптимальным решением.
Говоря о выборе метода решения однопродуктовых транспортных задач, стоит отметить, что задачи одним из наиболее эффективных в данном случае является Метод Фогеля, так как что с помощью данного метода можно получить максимально близкий к оптимальному план.
4) симплекс-метод представляет собой метод последовательного перехода от одного базисного решения (вершины многогранника решений) системы ограничений задачи линейного программирования к другому базисному решению до тех пор, пока функция цели не примет оптимального значения (максимума или минимума).
Симплекс-метод является универсальным методом, которым можно решить любую задачу линейного программирования, в то время, как графический метод пригоден лишь для системы ограничений с двумя переменными.
Для того, чтобы решить транспортную задачу симплексным методом необходимо выполнить следующие шаги:
• Привести задачу к каноническому виду,
• Найти начальное опорное решение с «единичным базисом» (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений),
• Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода,
• Если выполняется признак единственности оптимального решения, то решение задачи заканчивается,
• Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения.
Суть симплексного метода в следующем: если известны какая-нибудь крайняя точка и значение в ней целевой функции, то все крайние точки, в которых целевая функция принимает худшее значение, заведомо не нужны. Отсюда естественно стремление найти способ перехода от данной крайней точки к смежной по ребру лучшей, от нее к еще лучшей (не худшей) и т. д. Для этого нужно иметь признак того, что лучших крайних точек, чем данная крайняя точка, вообще нет. В этом и состоит общая идея наиболее широко применяемого в настоящее время симплексного метода (метода последовательного улучшения плана) для решения задач линейного программирования. Таким образом, в алгебраических терминах симплексный метод предполагает:
• умение находить начальный опорный план;
• наличие признака оптимальности опорного плана;
• умение переходить к нехудшему опорному плану.

Фрагмент текста работы:

1. Определение транспортной задачи

Транспортная задача является специальной задачей линейного программирования. В первую очередь, следует начать с определения термина «транспортная задача». Условно говоря, существует некий товар, который расположен в нескольких складских помещениях. Требуется доставить данный продукт конкретным потребителям, в число которых могут входить магазины, отдельные торговые павильоны, места на рынке и т.д., при этом у существует выбор из нескольких вариантов маршрута. Каждый из потребителей имеет собственную потребность в продукции, одному нужно получить, например, десять тонн груза, а другому хватило бы и трех тонн продукции. В данном случае очевидным является тот факт, что стоимость транспортировки будет различаться в зависимости от общего числа единиц транспортируемого груза и дальности пути. Максимально снизить необходимо итоговые траты на транспортировку товара.
Среди большого количества оптимизационных задач выделяются задачи линейного программирования, которые имеют специфические черты. В каждой задаче элементы решения – это ряд неотрицательных переменных x1, x2,…, xn. Следует так выбирать значения данных переменных, чтобы:
• Действовали некоторые ограничения вида линейных неравенств или же неравенств в отношении переменных x1, x2,…, xn.
• Линейная функция $f$ переменных являлась максимумом (минимумом).
Общая задача линейного программирования – это задача, где оптимизируемая функция цели является линейной комбинацией известных коэффициентов cj и неизвестных переменных xj вида:

Функция f также называется целевой функцией или же критерием эффективности. Найти решение задачи линейного программирования означает отыскать значения переменных xj, которые удовлетворяют ограничениям, а целевая функция при таких значениях принимает максимальное или минимальное значение.
Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи). Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году. Прогресс в решении проблемы был достигнут во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем. Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича .
Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку) .
Под названием транспортная задача, определяется широкий круг задач с единой математической моделью, эти задачи относятся к задачам линейного программирования и могут быть решены оптимальным методом. Однако, спецметод решения транспортной задачи позволяет существенно упростить её решение, поскольку транспортная задача разрабатывалась для минимизации стоимости перевозок .
Введем необходимые обозначения, пусть n – количество складов, а m – количество точек назначения. Посредством С(i,j) = cij обозначается стоимость транспортировки 1 единицы груза из i-го склада к j-му потребителю. При этом a(i) = ai указывает на запас продукции на i-ом складском помещении, а b(j) = bj – это потребность в товаре соответствующего потребителя.
Таким образом, суммарная стоимость транспортировки считается как сумма всех трат на транспортировку груза из каждого складского помещения к каждому из потребителей. Подобная общая постановка задачи е должна настораживать – в том случае, если из какого-либо склада нет возможности транспортировать груз, к примеру, по причине невыгодного географического расположения, значит соответствующий b можно считать равным 0.
Затем можно перейти к математической формулировке задачи. На языке формул задача будет выглядеть следующим образом: