Понятие математической линейной оптимизационной модели. Сущность и алгоритм симплексного метода решения линейных оптимизационных моделей

43. Понятие математической линейной оптимизационной модели. Сущность и алгоритм симплексного метода решения линейных оптимизационных моделей

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

Математические модели подразделяют на 2 большие класса:

1)  Простые, описательные (дескриптивные) модели (позволяют отобразить при помощи модели взаимосвязь параметров).

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

В зависимости от вида функции, описываемой цель и его ограничения, различают нелинейные и линейные оптимизационные модели. Разделение моделей на лин. и нелин. связано с применением различных методов их решения. Для поиска экстремума нелин.функции применяется универсал.метод, основанный на дифференциации нелин.функции. Производная нелин.функции приравнивается к 0 и из решения уравнения получается экстремум – значение нелин.функции.

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

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

Достоинства: ●Простота, ●Широкая распространенность,●Высокая эффект-ть метода

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

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

Фактически симплексный метод состоит из двух действий: 1) определение очередного базиса, 2) проверка наличия лучшего базисного решения.

При определении базисного решения при использовании симплексного метода необходимо решить 2 вопроса: 1)определение начального базис.решения, если базиса в исходной модели не существует;2) пропуск заведомо неоптимал.базисн.решений.

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

При определении начального базиса могут возникнуть следующие случаи:

1)  Система ограничений содержит неравенства вида ≤

                 х₃, х₄ – дополнит.базисн.переменные

В целевую функцию дополнит.переменные вводятся с коэф-ом 0, для того чтобы их значение не влияло на значение целевой функции.

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

2)  Система ограничений может иметь в своем составе уравнения и неравенства различного вида и тем не менее иметь базис

3)  Система ограничений содержит неравенства вида ≥ или уравнения, в каждое уравнение дабавляется искусственная переменная, затем модель решается симплексным методом с искусственным базисом

Искусственные переменные не имеют физ.смысла и необхоиы только для расчета первого реального базис.решения, то их необходимо в процессе решения удалить из модели. Если задача реш.на максиму, то искусствен.перемен. со знаком –М, где М-максимально большое число, есди решается на минимум то +М.

Послед-ть симплекс. преобразований удобно оформлять в виде симплексных таблиц.

Вверху таблицы помещают все переменные Х1, Х2, Xn и коэффициенты Cj, с которыми эти еременные входят в целевую функцию. Первый столбец C состоит из коэффициентов целевой функции при базисных еременных. Затем следует столбец базисных еременных и свободных членов уравнений. В остальные столбцы таблицы записываются коэффициенты при переменных Х1, Х2, Xn, с которыми они входят в систему уравнений. Таким образом, каждой строке таблицы соответствует уравнение системы, решенное относительно базисной еременной. Нижняя строка таблицы называется индексной. Каждый ее элемент , называется оценкой и определяется по формуле                                         

где  Cj — коэффициенты при переменных в целевой функции;

Zj — сумма произведений коэффициентов целевой функции при базисных   переменных на соответствующие   переменные — элементы j-го столбца таблицы. Если ajj — коэффициент симплексной таблицы i-й строки j-го столбца, а Ci — коэффициент целевой функции i-й базисной переменной, то  Zj = ∑ Ciaj,j = 1,2,... ,n.

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

Разрешающим столбцом явл. столбец с наибольшей положит.оценкой при решении задач на min или наибольш.отрицат.оценкой для задач на max.

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

Кажд эл-т разрешающей строки следует разделить на разреш.эл-т, то есть  где a_r'j — новое значение эл-та разрешающей строки; arj - старое значение этого эл-та;

a_rh – разр-щий эл-т, т.е. эл-т, стоящий на пересечении разр-ей строки  и разрешающего столбца h.

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

где a’_ij - новое значение элемента i-й строки j-го столбца; _aij - старое значение этого элемента;

arj - элемент, стоящий на пересечении разрешающей строки и данного столбца;

a_ih - элемент, стоящий на пересечении i-й строки и разрешающего столбца.