Симплексный метод решения задач линейного программирования

Для определения оптимального сочетания количества расходуе­мых ресурсов необходимо использовать критерий оптимальности, величина которого зависит от количества расходуемых ресурсов ка­ждого вида. Математическое описание этой зависимости в виде функции называетсяцелевой функцией модели.Оптимизацион­ная модель представляет собой совокупность целевой функции и системы ограничений, накладываемых на переменные целевой функции. Решением оптимизационной модели является множество значений, определяющих величины расхода каждого ресурса, при которых достигается оптимальное (минимальное или максимальное) значение целевой функции, при условии непревышения заданных величин запасов по каждому виду ресурсов.!!!

(Математическое моделирование - процесс построения, исследования и интерпре­тации результатов математической модели.)

Достоинствами матема­тических моделей являются низкая стоимость их создания, возмож­ность быстрой экспериментальной проверки разнообразных гипотез о составе и функциях моделируемого объекта или процесса.

Транспортный процесс является управляемым, то есть его эффективность зависит от того, какие, в каком количестве и в ка­кой пропорции используются ресурсы при осуществлении этого процесса. Качественные и количественные показатели используе­мых в транспортном процессе ресурсов являютсяпараметрамипроцесса.

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

Дескриптивная модель транспортного процесса - (англ. descrip­tion - описание) - представляет собой систему уравнений, описы­вающих взаимосвязи между величинами расхода различных ресур­сов, расходуемых при осуществлении этого процесса. Решением дескриптивной модели является множество значений, определяю­щих величины расхода каждого ресурса, причем эти значения не превышают заданной величины запаса по каждому виду ресурса. Дескриптивная модель не позволяет определить наивыгоднейший план использования ресурсов, при котором достигается наилучшее значение критерия оптимальности транспортного процесса. Для ре­шения этой задачи применяются оптимизационные модели.

!!!Для определения оптимального сочетания количества расходуе­мых ресурсов необходимо использовать критерий оптимальности, величина которого зависит от количества расходуемых ресурсов ка­ждого вида. Математическое описание этой зависимости в виде функции называетсяцелевой функцией модели.Оптимизацион­ная модель представляет собой совокупность целевой функции и системы ограничений, накладываемых на переменные целевой функции. Решением оптимизационной модели является множество значений, определяющих величины расхода каждого ресурса, при которых достигается оптимальное (минимальное или максимальное) значение целевой функции, при условии непревышения заданных величин запасов по каждому виду ресурсов.

Поскольку реальные транспортные процессы могут описывать­ся с различной степенью детализации, учитывать расход различ­ного вида ресурсов и различные виды взаимосвязей между вели­чинами расхода, то для их оптимизации и управления используют­ся различные виды математических моделей.)

Симплексный метод решения задач линейного программирования

Симплексный метод является универсальным и наиболее распро­страненным методом решения задач линейного программирова­ния.

Симплекс -это фигура (область), стороны которой описаны уравнениями или неравенствами системы ограничений задачи линейного програм­мирования. Поскольку оптимальное решение находится в угловой точке многогранника решений или симплекса, тоидея симплекс­ного метода заключается в последовательном переборе угловых точекдля нахождения такой единственной точки, в которой целе­вая функция достигает экстремального значения.

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

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

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