Реферат на тему Симплекс-метод в применении к транспортным задачам

Содержание:

Введение 3
1. Сущность и описание симплексного метода 5
2. Симплекс-метод в применении к транспортным задачам 9
Заключение 15
Список использованной литературы 17

Введение:

На текущий момент большое количество предприятий заняты в сфере перевозки продукции для ее последующей реализации. В связи с этим, важнейшую роль в современной экономике играют процессы оптимизации грузоперевозок, направленные на минимизацию финансовых затрат на доставку товаров. Данной проблемой занимается специализированная дисциплина — линейное программирование, точнее такое его направление, как решение транспортной задачи.
Транспортная задача является специальной задачей линейного программирования. В первую очередь, следует начать с определения термина «транспортная задача». Условно говоря, существует некий товар, который расположен в нескольких складских помещениях. Требуется доставить данный продукт конкретным потребителям, в число которых могут входить магазины, отдельные торговые павильоны, места на рынке и т.д., при этом у существует выбор из нескольких вариантов маршрута. Каждый из потребителей имеет собственную потребность в продукции, одному нужно получить, например, десять тонн груза, а другому хватило бы и трех тонн продукции. В данном случае очевидным является тот факт, что стоимость транспортировки будет различаться в зависимости от общего числа единиц транспортируемого груза и дальности пути. Максимально снизить необходимо итоговые траты на транспортировку товара.
Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи). Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году. Прогресс в решении проблемы был достигнут во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем. Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича.
Основной задачи транспортной логистики является перемещение необходимого количества груза (продукции) в необходимую точку посредством оптимального маршрута за необходимое количество времени и с минимальными финансовыми издержками. Исторически первой, и наиболее изученной на данный момент транспортной моделью является классическая транспортная задача перевозки одного вида товара, то есть однопродуктовая транспортная задача. Для данной модели была разработана развитая теория и эффективные модификации прямого и двойственного симплекс-метода, по-другому называемые метод потенциалов и венгерский метод.
Целью данной работы является изучение применения симплекс-метода в решении транспортных задач.

Заключение:

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

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

1. Сущность и описание симплексного метода
Симплекс метод — это метод последовательного перехода от одного базисного решения (вершины многогранника решений) системы ограничений задачи линейного программирования к другому базисному решению до тех пор, пока функция цели не примет оптимального значения (максимума или минимума) [5, 19-20 c.]. Данный метод является универсальным методом, которым можно решить любую задачу линейного программирования, в то время, как графический метод пригоден лишь для системы ограничений с двумя переменными.
Симплекс метод был предложен американским математиком Р.Данцигом в 1947 году, с тех пор для нужд промышленности этим методом нередко решаются задачи линейного программирования с тысячами переменных и ограничений.
Всякое неотрицательное решение системы ограничений называется допустимым решением. Пусть имеется система m ограничений с n переменными (m < n). Допустимым базисным решением является решение, содержащее m неотрицательных основных (базисных) переменных и n — m неосновных. (небазисных, или свободных) переменных. Неосновные переменные в базисном решении равны нулю, основные же переменные, как правило, отличны от нуля, то есть являются положительными числами. Любые m переменных системы m линейных уравнений с n переменными называются основными, если определитель из коэффициентов при них отличен от нуля. Тогда остальные n — m переменных называются неосновными (или свободными) [7, 64 c.].
Алгоритм симплекс метода выглядит следующим образом [2, 22-23 c.]:
• Шаг 1. Привести задачу линейного программирования к канонической форме. Для этого перенести свободные члены в правые части (если среди этих свободных членов окажутся отрицательные, то соответствующее уравнение или неравенство умножить на — 1) и в каждое ограничение ввести дополнительные переменные (со знаком «плюс», если в исходном неравенстве знак «меньше или равно», и со знаком «минус», если «больше или равно»).
• Шаг 2. Если в полученной системе m уравнений, то m переменных принять за основные, выразить основные переменные через неосновные и найти соответствующее базисное решение. Если найденное базисное решение окажется допустимым, перейти к допустимому базисному решению.
• Шаг 3. Выразить функцию цели через неосновные переменные допустимого базисного решения. Если отыскивается максимум (минимум) линейной формы и в её выражении нет неосновных переменных с отрицательными (положительными) коэффициентами, то критерий оптимальности выполнен и полученное базисное решение является оптимальным — решение окончено.