Симплекс-метод с искусственным базисом
Содержание
Стр.
1. Теоритическая часть …............................. |
3 |
Задача 1. Симплекс-метод с искусственным базисом (М-задача).... |
3 |
2. Практическая часть…........................ |
6 |
Задача 2. Решить графическим
методом типовую задачу оптимизации….................. |
6 |
Задача 3. Экономико-математическая
модель межотраслевого баланса (модель
Леонтьева)…................... |
9 |
Задача 4. Методы и модели анализа и прогнозирования экономических процессов с использованием временных рядов.......... |
18 |
Список литературы............. |
20 |
- Теоретическая часть
Задача
1. Симплекс-метод с
Симплекс-метод с
В линейную форму исходной задачи добавляется в случае ее максимизации слагаемое, представляющее собой произведение числа (-М) на сумму искусственных переменных, где М –достаточно большое число. В полученной задаче первоначальный опорный план очевиден.
При применении к этой задаче симплекс-метода оценки ∆j теперь будет зависеть от буквы М. Для сравнения оценок нужно помнить, что М- достаточно большое число.
В процессе решения М-задачи следует вычеркивать в симплекс-таблице искусственные векторы по мере их выхода из базиса. Если все искусственные векторы вышли из базиса, то получаем исходную задачу.
Если в оптимальном решении М-задачи нет искусственных переменных, это решение есть оптимальное решение исходной задачи. Если же в оптимальном решении M-задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима.
Пример
Целевая функция:
2x1-x2+7x3+11x4+5x5→min
Условия:
2x1+5x3+x4+8x5=12
-3x1+6x2+2x3-2x4≤5
РЕШЕНИЕ.
Приведем систему ограничений к каноническому виду, для этого необходимо неравенства преобразовать в равенства, с добавлением дополнительных переменных. Если в преобразуемом неравенстве стоит знак больше или равно, то при переходе к равенству знаки всех его коэффициентов и свободных членов меняются. Тогда система будет выглядеть следующим образом:
2x1+5x3+x4+8x5+R1=12
-3x1+6x2+2x3-2x4+X6=5
Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции.
Так как среди исходного набора условий было равенство (первое условие) мы ввели искусственную переменную R1. Это значит, что в симплекс таблицу нам необходимо добавить дополнительную строку M, элементы которой рассчитываются как сумма соответствующих элементов условий-равенств (тех которые после приведения к каноническому виду содержат искусственные переменные R) взятая с противоположным знаком.
Из данных задачи составляем исходную симплекс таблицу.
X1 |
X2 |
X3 |
X4 |
X5 |
Свободный член | |
F |
2 |
-1 |
7 |
11 |
5 |
0 |
R1 |
2 |
0 |
5 |
0 |
8 |
12 |
X6 |
-3 |
6 |
2 |
-2 |
0 |
5 |
M |
-2 |
0 |
-5 |
0 |
-8 |
-12 |
Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. В строке M имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -8. Ведущей строкой будет та, для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R1, а ведущий элемент: 8.
X1 |
X2 |
X3 |
X4 |
Свободный член | |
F |
0.75 |
-1 |
3.875 |
11 |
-7.5 |
X5 |
0.25 |
0 |
0.625 |
0 |
1.5 |
X6 |
-3 |
6 |
2 |
-2 |
5 |
M |
0 |
0 |
0 |
0 |
0 |
В строке M отрицательные
элементы отсутствуют. Рассмотрим строку
F в которой имеются
X1 |
X6 |
X3 |
X4 |
Свободный член | |||||||
F |
0.25 |
0.167 |
4.208 |
10.667 |
-6.667 | ||||||
X5 |
0.25 |
0 |
0.625 |
0 |
1.5 | ||||||
X2 |
-0.5 |
0.167 |
0.333 |
-0.333 |
0.833 | ||||||
M |
0 |
0 |
0 |
0 |
0 | ||||||
ОТВЕТ:
Так как исходной задачей был поиск минимума, оптимальное решение есть свободный член строки F, взятый с противоположным знаком. Найдено оптимальное решение F=6.667 при значениях переменных равных: X5=1.5, X2=0.833,
2. Практическая часть
Задача 2. Решить графическим методом типовую задачу оптимизации
Задача 2.2. Совхоз для кормления животных использует два вида корма. В дневном рационе животного должно содержаться не менее 6 единиц питательного вещества А и не менее 12 единиц питательного вещества В. Какое количество корма надо расходовать ежедневно на одного животного, чтобы затраты были минимальными? Исходные данные приведены ниже.
Питательные вещества |
Количество питательных веществ на 1 кг корма | |
1-ый вид |
2-ой вид | |
А В |
2 2 |
1 4 |
Цена 1 кг корма, тыс. руб. |
0,2 |
0,3 |
Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на максимум, и почему?
Решение: Введем обозначения:
Х1 - количество корма 1 вида;
Х2 - количество корма 2 вида.
Целевая функция в данном случае затраты на корма обоих видов. Требуется найти такое распределение кормов обоих видов, чтобы суммарные затраты на покупку кормов были минимальны. При этом значения переменных должны находиться в области допустимых решений.
Целевая функция задачи:
f(X) = 0,2x1 + 0,3x2 min
Ограничения:
2х1+1х2>=6
2х1+4х2<=12
Прямые ограничения означают, что область решений будет лежат в первой четверти декартовой системы координат, отметим штриховкой эту область на рис.1.
Определим множество решений первого неравенства:
2x1 + x2 = 6
X1 |
0 |
6 |
X2 |
3 |
0 |
Построим прямую по двум точкам (0;6) и (3;0). На рисунке обозначим её цифрой 1.
Аналогичным образом построим область решения второго неравенства:
2x1 + 4x2 = 12
X1 |
0 |
3 |
X2 |
6 |
0 |
(на рисунке прямая 2).
Зададим произвольное значение для целевой функции.
0,2 x1 + 0,3 x2 = 3
X1 |
0 |
10 |
X2 |
15 |
0 |
Через эти две точки проведем линию уровня (пунктирная прямая на рисунке).
Построим вектор-градиент, координаты которого являются частными производными функции f(X), т.е. (0,2;0,3). Чтобы построить этот вектор, нужно соединить точку (0,2;0,3) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента, а при минимизации – в противоположном направлении.
В этом случае движение линии уровня
осуществляем до её пересечения с
точкой В. Следовательно, именно в этой
точке достигается минимум целе
Определим координаты точки В, являющейся точкой пересечения граничных прямых, решив систему уравнений:
2х1 + х2 = 6
2х1 + 4х2 =12
2x1+x2-2x1-4x2=6-12
-3х2 = -6 х2 = 2 |
2х1+2=6 2х1 =4 х1 =2 |
Ответ: В (2; 2) – min целевой функции.
Точка В является так называемым оптимальным планом. В точке В целевая функция принимает свое минимальное значение при заданной системе ограничений. Эта точка отвечает минимально возможным затратам на корма при заданной области допустимых решений. При заданной области допустимых решений отсутствует точка максимума для целевой функции. Смысл данного факта: затраты на корма при данной области допустимых решений никак не ограничиваются . Таким образом, целевая функция в задаче линейного программирования принимает, при заданной системе ограничений:
минимальное значение min f(X) = 0,2*2 + 0,3*2 = 1. (тыс. руб.);
максимальное значение max f(X) = +∞ (функция неограниченна сверху на области допустимых решений).
Ответ: Чтобы затраты были минимальными необходимо расходовать 2ед. первого корма и 2 ед. второго корма.
Если данную задачу решать на максимум, то задача не имеет решения, так как целевая функция не ограничена сверху, т.е max f(X) = +∞.
Графическое решение (рис.1)
Задача 3. Экономико-математическая модель межотраслевого баланса (модель Леонтьева)
Задача 3.2. В течение девяти последовательных недель фиксировался спрос Y(t) (млн руб.) на кредитные ресурсы финансовой компании. Временной ряд Y(t) этого показателя приведен ниже.
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
43 |
47 |
50 |
48 |
54 |
57 |
61 |
59 |
65 |
Требуется:
1) проверить наличие аномальных наблюдений;
2) построить линейную модель Y(t)
3) оценить адекватность
4) оценить точность моделей на
основе использования средней
относительной ошибки
5) по построенной модели
6) фактические значения
Вычисления провести с точностью до одного знака после запятой. Основные промежуточные результаты вычислений представить в таблицах (при использовании компьютера представить соответствующие листинги с комментариями).
Решение:
- Проверить наличие аномальных наблюдений
Для выявления аномальностей ряда наблюдения воспользуемся методом Ирвина.
Рассчитаем значение
Где ,
Для удобства вычисления
промежуточные расчеты
Таблица 1
t |
|||||
|
1 |
43 |
-10,78 |
116,21 |
-- |
-- |
2 |
47 |
-6,78 |
45,97 |
4 |
0,55 |
3 |
50 |
-3,78 |
14,29 |
3 |
0,41 |
4 |
48 |
-5,78 |
33,41 |
2 |
0,27 |
5 |
54 |
0,22 |
0,05 |
6 |
0,82 |
6 |
57 |
3,22 |
10,37 |
3 |
0,41 |
7 |
61 |
7,22 |
52,13 |
4 |
0,55 |
8 |
59 |
5,22 |
27,25 |
-2 |
-0,27 |
9 |
65 |
11,22 |
125,89 |
6 |
0,82 |
484 |
425,57 |
Все расчетные значения меньше табличного значения критерия Ирвина (при n=9, =1,5), следовательно, можно говорить о том, что аномальных наблюдений не обнаружено.
- Построить линейную модель , параметры которой оценить МНК ( - расчетные, смоделированные значения временного ряда).
Построю линейную модель регрессии Y от t.
- Введу исходные данные, рис 2.1:
Рис 2.1
- Для проведения регрессионного анализа выберу команду Сервис → Анализ Данных.
- В диалоговом окне Анализ Данных выберу инструмент Регрессия, нажимаю ОК.
- В окне Регрессия в поле Входной интервал Y ввожу адрес диапазона ячеек, который представляет зависимую переменную. В поле Входной интервал Х ввожу адрес диапазона независимой переменной t.
- В поле График подбора ставлю флажок.
- В поле Остатки ставлю необходимые флажки и нажимаю кнопку ОК.
Результат получаю в виде, приведенном на рисунках 2.2 и 2.3:
Рис 2.2 Результат регрессионного анализа
Рис. 2.3 Вывод остатка
Оценка параметров модели «вручную». Привожу таблицу промежуточных расчетов параметров линейной модели по формулам:
Таблица 2
t |
yt |
t - t |
(t – t) |
yt-y |
(t-t)(yt-y) |
yt=a0+a1t |
Et=yt-yt |
|
1 |
43 |
- 4 |
16 |
-10,78 |
43,12 |
43,44 |
-0,44 |
2 |
47 |
- 3 |
9 |
-6,78 |
20,34 |
46,03 |
0,97 |
3 |
50 |
- 2 |
4 |
-3,78 |
7,56 |
48,61 |
1,39 |
4 |
48 |
-1 |
1 |
-5,78 |
5,78 |
51,19 |
-3,19 |
5 |
54 |
0 |
0 |
0,22 |
0 |
53,78 |
0,22 |
6 |
57 |
1 |
1 |
3,22 |
3,22 |
56,36 |
0,63 |
7 |
61 |
2 |
4 |
7,22 |
14,44 |
58,94 |
2,06 |
8 |
59 |
3 |
9 |
5,22 |
15,66 |
61,53 |
-2,53 |
9 |
65 |
4 |
16 |
11,22 |
44,88 |
64,11 |
0,89 |
60 |
155 |
Линейная модель будет выглядеть следующим образом:
- Оценить адекватность модели, используя свойства независимости остаточной компоненты, случайности и соответствия нормальному закону распределения.
Оценка адекватности. Исследую свойства остаточной компоненты, т.е. расхождения уровней, рассчитанных по модели и фактических наблюдений. Результаты привожу в таблице 3:
Таблица 3
Проверка независимости (отсутствие автокорреляции). Определяю с помощью dw – критерия Дарбина – Уотсона по формуле:
Так как dw` попало в интервал от d2 до 2, то поданному критерию можно сделать вывод о выполнении свойства независимости. Это означает, что в ряде динамики не имеется автокорреляции, следовательно, модель по этому критерию адекватна.
Проверка случайности. Проведу ее на основе критерия поворотных точек. Количество поворотных точек р равно 4 (р=4), при n=9.
Неравенство 4 > 2 выполняется, Следовательно, выполняется свойство случайности. Модель по этому критерию адекватна.
Нормальный закон распределения. Соответствие ряда остатков нормальному закону распределения определим с помощью RS – критерия:
где - максимальный уровень ряда остатков, = 2,06; - минимальный уровень ряда остатков, = - 3,19
Расчетное значение попадает в интервал (2,7 – 3,7), следовательно, выполняется свойство нормальности распределения. Модель по этому критерию адекватна.
- Оценить точность модели на основе использования средней относительной ошибки аппроксимации.
Для оценки точности модели вычислю среднюю относительную ошибку аппроксимации Еотн.
Таблица 4
t |
| ||
|
1 |
43 |
-0,44 |
0,01 |
2 |
47 |
0,97 |
0,02 |
3 |
50 |
1,39 |
0,03 |
4 |
48 |
-3,19 |
0,07 |
5 |
54 |
0,22 |
0,004 |
6 |
57 |
0,63 |
0,011 |
7 |
61 |
2,06 |
0,034 |
8 |
59 |
-2,53 |
0,04 |
9 |
65 |
0,89 |
0,014 |
Полученные значения средней относительной ошибки говорит о высоком уровне точности построенных моделей, т.к. ошибка менее 5% свидетельствует об удовлетворительном уровне точности.
- По построенным моделям осуществить прогноз спроса на следующие две недели (доверительная вероятность р = 70%)
Для вычисления точечного прогноза в построенную модель подставляем соответствующие значения фактора t = n + k
В нашей задаче:
у10 = 40,86 + 2,58*10 = 66,66
у11 = 40,860 + 2,58*11 = 69,24
Для построения интервального прогноза рассчитаю доверительный интервал. При уровне значимости α = 0,05, доверительная вероятность р = 70%, а критерий Стьюдента при ν = n – 2 = 7 равен 2,3646
Ширину доверительного интервала вычислим по формуле:
Где = 2,24; t = 5;
U(1) = 2,24*2,365 = 6,56
U(2) = 2,24*2,365 = 6,93
Далее вычисляю верхнюю и нижнюю границы прогноза, таблица 5:
Таблица 5
n + k |
U(k) |
Прогноз |
Верхняя граница |
Нижняя граница |
10 |
U(1) |
66,66 |
73,22 |
60,10 |
11 |
U(2) |
69,24 |
76,17 |
62,31 |
- Фактические значения показателя, результаты моделирования и прогнозирования представить графически
Рис. 2.4. График линейной модели временного ряда
Рис. 2.5. График остатков временного ряда
Рис 2.6. График прогноза на два шага вперед
Задача 4. Методы и модели анализа и прогнозирования экономических процессов с использованием временных рядов
Задание 4.2. Компания по продаже мототехники оценивает ежедневный спрос в 20 единиц. Годовые издержки хранения на один мотоцикл составляют 10 тыс. руб. Магазин работает 300 дней в году. Средние издержки одного заказа составляют 40 тыс. руб. Определите совокупные издержки заказа и оптимальный размер партии. Постройте график общих годовых затрат.
Дано:
T = 300 р.д./год
M = 20 ед./день*300 р.д./год = 6 тыс.ед./год
h = 10 тыс.руб./год
K = 40 тыс.руб./заказ
Определить: Qопт, Z1(Q), и построить график общих годовых затрат.
Решение:
- Количество мотоциклов в 1 заказе:
Qопт=√2KM/h=√2*40000*6000/
- Совокупные издержки на заказ и хранение:
Z1(Q)=KM/Qопт+hQопт/2=40000*
- Частота заказов:
M/Qопт=6000/219≈27,39=27 заказов в год.
- Периодичность поступления (интервал между поступлением) заказов:
Qопт/M=219/6000≈0,0365 лет, или 0,0365*300≈10,95=11 дней.
- Построим график общих годовых затрат Z1(Q) с помощью таблицы 6:
Таблица 6
Q |
K*M/Q |
h*Q/2 |
Z1(Q) |
50 |
4800000 |
250000 |
5050000 |
100 |
2400000 |
500000 |
2900000 |
190 |
1263157,89 |
950000 |
2213158 |
219 |
1095890,41 |
1095000 |
2190890 |
300 |
800000 |
1500000 |
2300000 |
380 |
631578,947 |
1900000 |
2531579 |
450 |
533333,333 |
2250000 |
2783333 |
График общих годовых затрат
Из таблицы и графика очевидно выполнение характеристического свойства оптимального размера партии.
Ответ: Совокупные издержки заказа равны 2190890 рублей в год, а оптимальный размер партии 219 штук.
Список литературы
- Экономико-математические методы и модели. Выполнение расчетов в среде Excel / Практикум: Учебное пособие для вузов. – М.: ЗАО, 2000. – 136с.
- Экономико-математические методы и модели: компьютерное моделирование: Учеб. пособие. – М.: Вузовский учебник, 2007. – 365 с.
- Экономико-математические методы и прикладные модели: Учеб. пособие для вузов/ В.В. Федосеев, А.Н. Гармаш, Д.М. Дайитбегов и др.; под ред. В.В. Федосеева. – М.: ЮНИТИ, 1999. – 391 с.
