Особые случаи применения симплекс-метода

Содержание

Задание 1. Особые случаи применения симплекс-метода……………………...3

1. Вырожденность…………………………………………………..3
2. Альтернативные оптимальные решения………………………..7
3. Неограниченные решения……………………………………...10
4. Отсутствие допустимых решений……………………………..14

Задание 2…………………………………………………………………………16

Задание 3…………………………………………………………………………18

Задание 4…………………………………………………………………………27

Список литературы………………………………………………………………30

Задание 1. Изложить материал по выбранной теме. Проиллюстрировать теоретические положения примерами

Особые случаи применения симплекс-метода

Выделяют следующие особые случаи, встречающиеся при использовании симплекс-метода:

5. вырожденность;
6. альтернативные оптимальные решения;
7. неограниченные решения;
8. отсутствие допустимых решений.

Основное внимание уделять  причинам возникновения таких ситуаций и их интерпретации применительно  к практическим задачам.

Для наглядности используется графический метод решения задач  ЛП.

1. Вырожденность

Пример1. (Вырожденное оптимальное решение).

Дано: максимизировать целевую функцию

при ограничениях:

                                                                                                               (1)

                                                                                                               (2)

                                                                                                                       (3)

                                                                                                                       (4)

Таблица 1.1

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

Наличие вырожденного решения  не свидетельствует о какой-либо «опасности» для исследователя  и вызывает лишь некоторое неудобство в теоретическом отношении. С  практической точки зрения специфика  ситуации целиком объясняется наличием в модели, по крайней мере, одного избыточного ограничения.

Что же практически обусловливает вырожденность решения?

                                                 Рис. 1.1.

Рассмотрим рисунок, иллюстрирующий графический способ решения задачи. Через точку оптимума (х₁=0, х₂=2) проходят три прямые. Задача содержит только две переменные, поэтому такую точку обычно называют переопределенной, так как для ее идентификации необходимы только две прямые. Отсюда следует вывод, что одно из ограничений модели является избыточным. Информация такого рода позволяет также выявить возможные неточности в формулировке задачи.

Важный в теоретическом  отношении второй фактор можно обнаружить, сравнивая итерации 1 и 2. Хотя состав базисных и небазисных переменных на этих итерациях различен, значения всех переменных и целевой функции  не изменяются:

x₁ = 0, x₂ = 2, x₃ = 0, x₄ = 0, Z = 18.

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

Пример2. (Промежуточное вырожденное решение).

    Дано: максимизировать целевую функцию

   при ограничениях:

         (1)

          (2)

          (3)

           (4)

           (5)

Таблица 1.2

В таблице, содержащей результаты всех итераций, вырожденность впервые  обнаруживается на итерации 1. В отличие  от предыдущего примера в данном случае на итерации 2 вырожденность  уже не имеет места, причем значение целевой функции улучшается, возрастая  с Z=6 (итерация 1) до Z= 17/2 (итерация 2). Это связано с тем, что переменная x₂, вводимая в базис на итерации 1, имеет отрицательный коэффициент (—2) в ограничении, соответствующем нулевой базисной переменной x₅. В соответствии с условием допустимости х₅ не может быть переменной, исключаемой из базиса.

На рисунке показано, что  в рассматриваемом случае вырождение решения получается на некоторой  промежуточной итерации.

Рис. 1.2.

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

2. Альтернативные  оптимальные решения

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

Пример 3. (Бесконечное множество решений).

Дано: максимизировать целевую функцию

при ограничениях:

          (1)

          (2)

           (3)

           (4)

Таблица 2.1

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

                                             Рис. 2.1.

Каким образом по результатам  этой итерации, содержащимся в таблице, можно узнать о наличии альтернативных оптимальных решений? Рассмотрим значения коэффициентов при небазисных переменных в Z-уравнении, полученном на данной итерации.

Нулевое значение коэффициента (небазисной) переменной x₁ свидетельствует о том, что ее включение в базис не изменит значения целевой функции, но приведет к изменению значений других переменных. Именно это и происходит на итерации 2, когда переменная x₁ вводится в базис вместо x₄. В результате получается новое оптимальное решение, соответствующее точке С, в которой x₁=3, x₂=1 и Z=10.

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

B: x₁ = 0, x₂ = 5/2,

C: x₁ = 3, x₂ = 1

и полагая  , можно выразить координаты любой точки отрезка ВС следующим образом:

x₁' = a(0) + (1 - a)(3) = 3 - 3a,

x₂' = a(5/2) + (1 -a)(1) = 1 - 3a/2.

Заметим, что при a=0 имеем (x₁', x₂') = (3, 1), что соответствует точке С. Если a=1, то (x₁, x₂)= (0, 5/2), т. е. получаем точку В. При значениях a, заключенных между 0 и 1, точка (x₁', x₂') располагается на отрезке ВС.

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

3. Неограниченные  решения

Пример 4. (Неограниченная целевая функция).

Дано: максимизировать целевую функцию

при ограничениях:

          (1)

          (2)

           (3)

           (4)

Начальная итерация

Таблица 3.1

Рис. 3.1.

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

Неограниченность решения  задачи ЛП свидетельствует только об одном: разработанная модель недостаточно точна. Бессмысленность использования  модели, прогнозирующей «бесконечную»  прибыль, вполне очевидна. Наиболее типичные ошибки, приводящие построению моделей  такого рода, состоят в том, что 

1) не учтено одно (или несколько) ограничение, не являющееся избыточным;

2) неточно оценены параметры (постоянные), фигурирующие в не которых ограничениях.

Анализ начальной симплекс-таблицы  показывает, что в качестве переменной, включаемой в базис, можно выбрать  либо x₁, либо x₂. Переменная x₁ имеет наибольший по абсолютной величине отрицательный коэффициент в z-уравнении, и именно такая переменная обычно вводится в базис. Заметим, однако, что во всех ограничениях коэффициенты при x₂ либо отрицательны, либо равны 0. Это означает, что x₂ можно бесконечно увеличивать, не нарушая ни одного из ограничений модели. Так как прирост переменной x₂ на единицу приводит к такому же увеличению функции Z, становится ясно, что при неограниченном возрастании x₂ будет неограниченно увеличиваться и значение целевой функции Z. Поэтому, не проводя дальнейших вычислений, можно заключить, что решение сформулированной задачи не ограничено. Иллюстрацией рассмотренной ситуации служит рисунок, из которого видно, что в направлении оси х₂ пространство решений не ограничено и значение Z может быть сделано сколь угодно большим.

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

Пример 5. (Пространство решений не ограничено, а оптимальное значение целевой функции конечно).

Дано: максимизировать целевую функцию

при ограничениях:

          (1)

           (2)

           (3)

           (4)

Таблица 3.2

Рис. 3.2.

В таблице приведены результаты итераций симплекс-метода. Результаты начальной итерации показывают, что  пространство решений данной задачи не ограничено в направлении оси  x₂. Однако, поскольку переменная х₂ фигурирует в Z-уравнении не с отрицательным коэффициентом, нельзя сделать вывод о неограниченности целевой функции. Действительно, результаты итерации 2 показывают, что оптимальное значение целевой функции конечно. Очевидно, что фактором, определяющим, будет ли целевая функция ограниченной, является наклон прямой, представляющей целевую функцию.

4. Отсутствие  допустимых решений

Пример 6. (Отсутствие допустимых решений).

Дано: максимизировать целевую функцию

при ограничениях:

          (1)

         (2)

           (3)

           (4)

Таблица 4.1

Если ограничения модели одновременно выполняться не могут, то задача не имеет допустимых решений.

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

Результаты итераций симплекс-метода, приведенные в таблице 4.1, показывают, что в точке оптимума искусственная переменная R имеет положительное значение (=4).

Это свидетельствует об отсутствии допустимых решений. Рассматриваемую  ситуацию иллюстрирует рисунок. Алгоритм симплекс-метода, допускающий положительные  значения искусственных переменных, по существу, «обращает» направление  неравенства в соответствующем  ограничении. В данном случае исходное неравенство  превращается в обратное: . (Можете ли вы объяснить, за счет чего это происходит?). В результате получается решение, которое можно назвать псевдооптимальным.

Рис. 4.1.

Задание 2. Решить графическим методом типовую задачу оптимизации

Задача. Фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входит 3 кг азотных, 4 кг фосфорных и 1 кг  калийных удобрений, а в улучшенный – 2 кг азотных, 6 кг фосфорных и 3 кг калийных удобрений. Известно, что для некоторого газона требуется, по меньшей мере, 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений. Обычный набор стоит 3 ден. ед., а улучшенный – 4 ден. ед. Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

Построить экономико-математическую модель задачи, дать необходимые комментарии  к ее элементам и получить решение  графическим методом. Что произойдет, если решать задачу на максимум, и почему?

Решение.

Пусть B_i – необходимый минимум питательных веществ i-го типа. Так, B₁=10 кг, B₂=20 кг, B₃= 7 кг. C_i – стоимость 1 кг j-го набора.

Целевая функция (общие расходы):

Ограничения:

(азотные удобрения)

(фосфорные удобрения)

(калийные удобрения)

1. По системе ограничений построим область допустимых решений  - область, которая удовлетворяет всем неравенствам системы ограничений. Она ограничена фигурой Ох2-А-С-Е-В-0x1.
2. Построим линию целевой функции f(x) = 0 и укажем направление вектор - градиента F (xl, х2) = {3;4}. Перемещаем линию F(xl, x2) по направлению вектор - градиента параллельно самой себе (в сторону ). Первая точка области допустимых решений, которую коснется линия F(xl, x2), является точкой минимума (в нашем случае, линия F(xl, x2) первой коснется т.С).
3. Найдем координаты угловой точки С (решение нашей задачи):

т.С - пересечение   (1) и (2) : т.С(2;2)

4. Определим значение F(xl, x2) в угловой точке области допустимых решений - С и определим min:

F(C) = 3*2 + 4*2 = 14 = min f(x)

Решая на максимум значение F(xl, x2) будет стремиться в , т.к. область допустимых решений не ограничена сверху:

  Рис.1. Графический метод  решения задачи.

Задание 3.  Исследовать динамику экономического показателя на основе анализа одномерного временного ряда

Задача. В течение девяти последовательных недель фиксировался спрос Y(t) (млн. руб.) на кредитные ресурсы финансовой компании. Временной ряд Y(t) этого показателя  приведен в таблице:

Требуется:

1. Проверить наличие аномальных наблюдений. 
2. Построить линейную модель , параметры которой оценить МНК ( — расчетные, смоделированные значения временного ряда). 
3. Оценить адекватность линейной модели, используя свойства независимости остаточной компоненты, случайности и соответствия нормальному закону распределения (при использовании R/S - критерия взять табулированные границы 2,7–3,7);
4. Оценить точность модели на основе использования средней относительной ошибки аппроксимации.
5. По построенной модели осуществить прогноз спроса на следующие две недели (доверительный интервал прогноза рассчитать при доверительной вероятности р=70 %).
6. Фактические значения показателя, результаты моделирования и прогнозирования представить графически.

Решение:

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

,

где — стандартное отклонение уровней ряда.

Стандартное отклонение определяется с помощью встроенной функции  EXCEL «СТАНДОТКЛОН»: S_y»7,52 млн. руб. (прил. 1). Расчет значений l_t для всех уровней ряда, начиная со второго, приведен в прил. 1. Табличное значение критерия Ирвина для уровня значимости a=0,05 и длины временного ряда n=9 составляет l=1,5.

Вывод: видно, что ни одно из значений l_t не превышает критического значения, что свидетельствует об отсутствии аномальных наблюдений.

2. Линейную трендовую модель строим с помощью надстройки EXCEL «Анализ данных… Регрессия» (меню «Сервис»):

Уравнение линейного тренда имеет вид (см. «Коэффициенты» в прил. 1):

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

Коэффициент детерминации уравнения R²»0,967 (см. «R-квадрат» в прил. 1) превышает критическое значение для a=0,05 и n=9, что свидетельствует о статистической значимости линейной модели и наличии устойчивого линейного тренда во временном ряду. Само значение R² показывает, что изменение спроса во времени на 96,7 % описывается линейной моделью.

3. Оценим адекватность линейной модели. Рассчитанные по модели значения спроса , остатки и их график были получены в EXCEL одновременно с построением модели (см. «ВЫВОД ОСТАТКА» в прил. 1).

Случайность остаточной компоненты проверим по критерию поворотных точек. Для этого каждый уровень ряда остатков сравниваем с двумя соседними — предыдущим и последующим. Если этот уровень одновременно больше или одновременно меньше обоих соседних уровней, то точка считается поворотной (на графике остатков такие уровни выглядят как «пики» и «впадины»). В нашем случае общее число поворотных точек в ряду остатков составляет p=5.

Критическое число поворотных точек для a=0,05 и n=9 определяется по формуле:

Так как  , остатки признаются случайными.

Проверим независимость остатков с помощью критерия Дарбина–Уотсона. Для расчета d-статистики используется выражение, составленное из встроенных функций EXCEL:

=СУММКВРАЗН («Остатки 2, …, n»; «Остатки 1, …, n–1») /СУММКВ(«Остатки 1, …,n»)

d-статистика имеет значение (см. прил. 1):

.

Критические значения d-статистики для a=0,05 и n=9 составляют: d₁=0,82; d₂=1,32. Так как выполняется условие

,

остатки признаются независимыми (автокорреляция остатков не выявлена).