4. Симплекс-метод. Сутність методу. Основні поняття. Алгоритм.

Симплекс метод является универсальным вычислительным алгоритмом, который реализует идею последовательного улучшения опорный планов ЗЛП.

Так как опт. решение ЗЛП всегда находится в 1 из угловых точек ОДР, то идея симплекс метода заключается в упорядоченном переборе вершин ОДР в направлении улучшения значения цф.

Каждая угловая точка ОДР является базисным решением с-мы ограничений , записанных в виде равенств, которое имеет все положительные компоненты. Т.к. общее число базисных переменных конечно и равно , поэтому метод перебора в случае ограниченной ОДР всегда будет конечным и приведет к опт. опорной точке. Переход от 1 опорной точки к другой осущ. итерационным способом. Итерация представляет собой набор вычислительных процедур, которые в симплекс методе базируются на алгоритме Джордана-Гаусса.

Алгоритм метода:

1) приводим модель к канонической форме

2) определяем исходное опорное решение – это базисное решение с-мы ограничений, которое содержит только положительные компоненты

3) составляем симплекс таблицу

4) для каждого столбца вычисляем

а) если все , то найдено опт. решение

б) если среди есть отрицательные и в столбце с такой оценкой не содержится положительных элементов, то цф не ограничена в ОДР

в) если среди есть отрицательные, но в каждом столбце с такой оценкой имеется хотя бы 1 положительный элемент, продолжаем выполнять итерации

5) итерация

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

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

6) переходим к пункту 4)

5) Аналіз моделей на чутливість.

Анализ на чувствительность – процесс, который реализуется после того, как оптимальное решение задачи уже найдено. В рамках такого анализа исследуется, каким образом изменение исходных параметров модели повлияет на полученное оптимальное решение. Можно выделить 3 таких задачи анализа на чувствительность: 1) Изменение запасов ресурсов (правых частей ограничений); 2) Определение ценностей ресурсов (теневых цен); 3) Влияние коэффициентов целевой ф-ии на оптимальную точку.

1-ая задача анализа на чувствительность: исследование вопроса, на сколько можно сократить или увеличить запасы ресурсов. Все ресурсы делятся на 2 класса: дефицитные – такие ресурсы, которые в процессе производства использованы полностью и недефицитные – остаются в остатке. Графически дефицитным ресурсам соответствуют связывающие ограничения – проходят через оптимальную точку, а недефицитным ресурсам соответствуют несвязывающие ограничения, не проходят через Хопт. Кроме того, можно определить статус ресурса поставив Хопт в соответствующее ограничение и проверив его знак. Относительно ресурсов исследуются 2 такие вопроса: 1) На сколько можно увеличить запас дефицитного ресурса, так чтобы оптимальное решение задачи улучшилось; 2) На сколько можно уменьшить запас недефицитного ресурса, чтобы не ухудшилось найденное оптимальное решение. Каждый ресурс исследуется по отдельности. Правило 1. Чтобы графически определить максимальное значение запаса дефицитного ресурса, надо передвигать соответствующую прямую в направлении возрастания до тех пор, пока ограничение не станет избыточным (перестанет влиять на ОДР). Правило 2. Для того, чтобы определить аналитически новый запас дефицитного ресурса необходимо: а) определить координаты той точки, в которой соответствующее ограничение становится избыточным (новая оптимальная точка); б) подставить полученные координаты в левую часть соответствующего ограничения. Правило 3. Для того, чтобы определить графически максимально возможное уменьшение запаса недефицитного ресурса нужно передвигать соответствующую прямую в направлении уменьшения до пересечения с оптимальной точкой. Правило 4. Для того, чтобы численно найти новый запас недефицитного ресурса необходимо подставить в левую часть соответствующего ограничения координаты Хопт. Отметим, что при уменьшении запасов недефицитных ресурсов значение ЦФ не меняется.

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

3-ая задача анализа на чувствительность: изменение коэффициентов ЦФ влияет на наклон линии уровня и, как следствие, на расположение оптимальной точки, поэтому в рамках 3-ей задачи рассматриваются такие 2 вопроса: 1) При каком диапазоне изменений коэффициентов ЦФ оптимальная точка не меняется; 2) Каким образом должны измениться коэффициенты ЦФ, чтобы оптимальная точка перешла в другую вершину, и , как следствие, изменился статус некоторых ресурсов. Правило 5. Определение диапазонов изменения коэффициентов ЦФ: 1) находим угловой коэффициент линии уровня в общем виде; 2) находим угловые коэффициенты связывающих ограничений; 3) путём сравнения найденных угловых коэффициентов выясняем возможные последствия изменений коэффициентов С1 и С2. Всевозможные ситуации записываем в таблицу. Диапазон изменений для каждого коэффициента определяем по отдельности. Для этого сначала фиксируется С1 и определяются диапазоны для С2, потом наоборот. При фиксированных С2 находятся изменения для С1.