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

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

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

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

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

          (1)

           (2)

           (3)

           (4)

Таблица 3.2

Итерация	Базисные переменные	X1	x2	x3	x4	Решение
0 (начало вычислений) х1 вводится х3 исключается	Z	-6	2	0	0	0
	x3	2	-1	1	0	2
	x4	1	0	0	1	4
1 х2 вводится х4 исключается	Z	0	-1	3	0	6
	x1	1	-1/2	1/2	0	1
	x4	0	1/2	-1/2	1	3
2 оптимум	Z	0	0	2	2	12
	x1	1	0	0	1	4
	x2	0	1	-1	2	6

Рис. 3.2.

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

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

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

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

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

          (1)

         (2)

           (3)

           (4)

Таблица 4.1

Итерация	Базисные переменные	х1	х2	х4	х3	R	Решение
0 (начало вычислений) х2 вводится х3 исключ.	Z	-3-3M	-2-4M	M	0	0	-12M
	x3	2	1	0	1	0	2
	R	3	4	-1	0	1	12
1 (псевдоопт.)	Z	1+5M	0	M	2+4M	0	4-4M
	x2	2	1	0	1	0	2
	R	-5	0	-1	-4	1	4

 

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

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

Результаты итераций симплекс-метода, приведенные в таблице 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) этого показателя  приведен в таблице:

t	yt
1	3
2	7
3	10
4	11
5	15
6	17
7	21
8	25
9	23

 

Требуется:

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. Так как выполняется условие

,

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