Задача 1.
Решить задачу линейногопрограммирования симплексным методом.
Вариант 3.
Найти наибольшее значениефункции f(X) = — x1 — x2 + 2x3 приограничениях
/>2x1 + x2 + x3 £ 2
x1 — x2+ x3 £ 1,
xj ³ 0, j = 1, 2, 3.
Решение.
Приведем задачу кканоническому виду, вводя дополнительные неотрицательные переменные x4,5³ 0.
f(X) = — x1 — x2 + 2x3 ® max
/>2x1 + x2 + x3+ x4 = 2
x1 — x2 + x3 + x5 = 1,
xj ³ 0, j = 1, 2, 3, 4, 5.
Каноническая задача имеетнеобходимое число единичных столбцов, т. е. обладает очевидным начальнымопорным решением.
Очевидное начальноеопорное решение (0; 0; 0; 2; 1).
Решение осуществляетсясимплекс-методом с естественным базисом. Расчеты оформим в симплекс-таблицахНомер симплекс-таблицы Базис
Cj
Ci B -1 -1 2 Q
A1
A2
A3
A4
A5
A4 2 2 1 1 1 2:1 = 1
A5 1 1 -1 1 1 1:1 = 1
j - 1 1 -2 1
A4 1 1 2 1 -1 1:2 = 1/2
A3 2 1 1 -1 1 1
j - 2 3 -1 2 2
A2 -1 1/2 1/2 1 1/2 -1/2
A3 2 3/2 3/2 1 1/2 1/2
j - 5/2 7/2 1/2 3/2
Начальное опорное решение(0; 0; 0; 1; 1), соответствующее симплекс-таблице 0, неоптимальное, так как в D — строке есть отрицательныезначения, наименьшее в столбце А3. Этот столбец будет направляющим.Минимальное положительное оценочное отношение Q в строке А5, этастрока направляющая. Направляющий элемент на пересечении направляющих строки истолбца. Столбец А5 выводим из базиса, а А3 — вводим вбазис. После пересчета получаем симплекс-таблицу 1. Соответствующее опорноерешение (0; 0; 1; 1; 0) не оптимально, так как в D — строке есть отрицательные значения, в столбце А2.Этотстолбец будет направляющим. Минимальное положительное оценочное отношение Q встроке А4. В качестве направляющей строки возьмем А4.Направляющий элемент на пересечении направляющих строки и столбца. Столбец А4выводим из базиса, а А2 — вводим в базис. Опорное решение,соответствующее симплекс-таблице 2 (0; 1/2; 3/2; 0; 0) — оптимально, так как в D — строке нет отрицательных значений.
Отбрасывая значениядополнительных переменных х4 и х5, получаем оптимальноерешение исходной задачи:
х1 = 0, х2= 1/2 = 0,5; х3 = 3/2 = 1,5; fmax = -1×0 — 1×0,5 + 2×1,5 = 2,5.
Задача 2.
Задание 1. Сформулироватьэкономико-математическую модель исходной экономической задачи.
Задание 2. Решитьполученную задачу линейного программирования графическим методом.
Задание 3. Сформулироватьдвойственную задачу и найти ее оптимальное решение, используя теоремыдвойственности.
Вариант 3.
Из 505 м2ткани нужно сшить не более 150 женских и не более 100 детских платьев. На пошиводного женского и детского платья требуется соответственно 3 м2 и 1м2 ткани. При реализации каждого женского платья получают 10 ден.единиц прибыли, а детского – 5 ден. единиц. Сколько нужно сшить женских идетских платьев, чтобы получить наибольшую прибыль?
Решение.
Задание 1.
Обозначим x1 иx2 количество женских и детских платьев, соответственно (планпошива). Очевидно, x1,2 ³ 0 и целые. Так как женских платьев должно быть не более 150,то x1 £ 150, аналогично, для детских платьев получаем x2 £ 100. Расход ткани на план пошива (x1,x2) составит 3x1 + x2 м2, этавеличина не должна превышать запаса ткани 505 м2. Следовательно,должно выполняться неравенство 3x1 + x2 £ 505.
Прибыль от продажиплатьев составит f(X) = 10x1 + 5x2 ден. единиц, и онадолжна быть наибольшей
Получаемэкономико-математическую модель задачи:
Найти максимум функцииf(X) при заданных ограничениях
f(X) = 10x1+ 5x2 ® max
3x1 + x2 £ 505
x1 £ 150
x2 £ 100
x1,2 ³ 0, целые.
Задание 2.
Решаем задачу без условияцелочисленности решения. Построим множество допустимых решений задачи.
Прямые ограничения x1,2³ 0 выделяют первую четвертьплоскости.
Проведем прямую 3x1+ x2 = 505 через точки (110; 175) и (175; -5). Подставим в первоенеравенство координаты точки (0; 0): 3×0 +1×0 = 0
Проведем прямую x1 = 150и выберем левую полуплоскость.
Проведем прямую x2 = 100и выберем нижнюю полуплоскость.
Множество допустимыхрешений – это многоугольник ABCDO.
Построим линию уровняцелевой функции f(X) = 10x1 + 5x2 10x1 + 5x2= 0 через точки (0; 0 ) и (-10; 20). Вектор-градиент {10; 5} задаетнаправление, перемещаясь вдоль которого, можно увеличить значение целевойфункции; перемещаясь в противоположном направлении, можно уменьшить еезначение.
Из чертежа видно, чтонаибольшее значение целевой функции будет на линии уровня, проходящей черезточку В.
Координаты этой точкинайдем из системы
/>3x1 + x2 = 505,
x2 = 100.
/>x1 = 135,
x2 = 100.
fmах = 10 ×135 + 5 ×100 = 1850 ден. единиц.
Полученное оптимальноерешение оказалось целым, следовательно, это решение поставленной задачи.Получили: в оптимальном плане пошива следует сшить женских платьев 135 шт.,детских – 100 шт. При этом прибыль составит 1850 ден. единиц и будетнаибольшей.
/>
Задание 3.
Двойственная задача.
Найти минимум функцииg(Y) при ограничениях:
g(Y) = 505y1+ 150y2 + 100y3 ® min
3y1+ y2 ³ 10
y1 + y3 ³ 5
y1,2,3 ³ 0.
Оптимальное решениепрямой задачи Х = (135; 100). Подставим его в ограничения этой задачи
3×135 + 1×100 = 505
135
100 = 100.
Условия дополняющейнежесткости (вторая теорема двойственности): для оптимальных плановдвойственных задач имеют место соотношения:
/>
Так как для оптимальногорешения прямой задачи второе ограничение выполняется как неравенство, то воптимальном решении двойственной задачи y2 = 0.
Так как для оптимальногорешения прямой задачи х1 > 0и х2 > 0, то обаограничения двойственной задачи выполняются как равенство. Для нахождениярешения двойственной задачи получаем систему
/>y2 = 0
3y1 + y2 = 10
y1 + y3 = 5.
Получаем решение: y1 = 10/3, y2 = 0, y3 = 5/3.
Найдем значение целевойфункции двойственной задачи:
g(Y) = 505×10/3 + 150×0 + 100×5/3 = 5550/3 = 1850.
Получили gmin = fmax = 1850 ден. единиц.
Так как значения прямой идвойственной функций равны, то Y = (10/3; 0; 5/3) является оптимальным решениемдвойственной задачи (по первой теореме двойственности).
Задача 3.
Задание 1. Записатьисходные данные задачи в виде транспортной таблицы, определить, открытой илизакрытой является транспортная задача.
Задание 2. Сформулироватьэкономико-математическую модель исходной транспортной задачи.
Задание 3. Найтиоптимальный план перевозок, отметив при этом единственность илинеединственность оптимального плана.
Вариант 3.
Картофель из четырехрайонов должен быть перевезен в три хранилища. Запасы картофеля в районахсоответственно равны 400 т, 500 т, 800 т и 500 т. Возможности хранилищсоответственно равны 700 т, 800 т и 700 т. Затраты на перевозку одной тонныкартофеля из первого района в каждое из хранилищ равны соответственно 1, 4 и 3ден. единиц; аналогичные затраты на перевозку из второго района составляют 7, 1и 5 ден. единиц, из третьего — 4, 8 и 3 ден. единиц, из четвертого — 6, 2 и 8ден. единиц. Найти план перевозок картофеля из районов в хранилища, при которомтранспортные расходы были бы минимальными.
Решение.
Задание 1.
Мощности
поставщиков Мощности потребителей 700 800 700 400 1 4 3 500 7 1 5 800 4 8 3 500 6 2 8
Сумма мощностейпоставщиков (запасы картофеля в всех районах) 400+500+800+500 = 2200, суммамощностей потребителей (возможности всех хранилищ) 700+800+700 = 2200. Суммы равны,данная задача является транспортной задачей закрытого типа.
Задание 2.
Обозначим xij объем поставок картофеля от i – го поставщика (района) j – му потребителю (хранилищу), i = 1, 2, 3, 4; j = 1, 2, 3. Очевидно, xij³ 0. В закрытой транспортной задаче всеограничения являются равенствами.
Так как потребностидолжны быть удовлетворены, то выполняются условия:
х11 + х21+ х31 + х41 = 700
х12 + х22+ х32 + х42 = 800 (1)
х13 + х23+ х33 + х43 = 700
Так как поставки отпоставщика всем потребителям не могут быть больше его возможностей, товыполняются условия:
х11 + х12+ х13 = 400
х21 + х22+ х23 = 500 (2)
х31 + х32+ х33 = 800
х41 + х42+ х43 = 500
Затраты натранспортировку составят
F(X) = х11 + 4х12 + 3х13 +
+ 7х21 + х22+ 5x23 +
+ 4х31 + 8х32+ 3х33 +
+ 6х41 + 2х42+ 8х43 .
Требуется найтинеотрицательное решение системы уравнений (1) – (2), на котором целевая функциязатрат F(X) принимает минимальное значение.
Задание 3.
Начальный план перевозокнаходим методом минимальной стоимости:
Заполняем клетку (1; 1)х11 = min {700, 400} =400, от поставщика 1 вывезено все, в строке 1 больше поставок нет. Заполняемклетку (2; 2) х22 = min{800, 500} = 500, от поставщика 2 вывезено все, в строке 2 больше поставок нет.Клетка (4; 2) х42 = min{800 — 500, 500} = 300, потребителю 2 все завезено, в столбец 2 больше поставокнет. Клетка (3; 3) х33 = min {700, 800} = 700, потребителю 3 все завезено, в столбец 3 большепоставок нет. Далее клетка (3; 1) х31 = 100. Клетка (4; 1) х41= 200. Все клетки, в которые даны поставки, считаем занятыми, остальные –свободными. Первоначальный план перевозок задается таблицей 1.
Таблица 1.
Мощности
поставщиков Мощности потребителей
ui 700 800 700 400
1
400 4 3 500 7
1
500 5 -4 800
4
100 8
3
700 -3 500
6
200
2
300 8 -5
vj 1 -3
Исследуем этот планперевозок на оптимальность методом потенциалов. Потенциалы для занятых клеток удовлетворяютуравнениям: vj= cij+ ui.
Пусть u1 = 0; по клетке (1; 1) находим v1 = 1; по клетке (3; 1) находим u3 = -3; по клетке (4; 1) находим u4 = -5; по клетке (4; 2) находим v2 = -3; по клетке (3; 3) находим v3 = -0; по клетке (2; 2) находим u2 = -4.
Для всех клеток матрицыперевозок найдем оценки клеток dij = (ui + cij) — vj:
/>
Среди оценок нетотрицательных, следовательно план перевозок Х0 (таблица 1) оптимальный.
Так как среди оценоксвободных клеток есть нулевые (клетка (1; 3)), то оптимальный план перевозок неединственный.
Общие затраты наперевозки
F(X1) = 1*400 + 1*500 + 4*100 + 3*700 + 6*200 + 2*300 = 5200 ден.единиц будут минимальными при:
x11 = 400, x22 = 500, x31 = 100, х33 = 700, x41 = 200, x42 = 300, остальные xij = 0.
По оптимальному плануперевозок следует перевезти картофеля:
из первого района впервое хранилище — 400 т;
из второго района вовторое хранилище — 500 т;
из третьего района впервое хранилище — 100 т,
в третье хранилище — 700 т;
из четвертого района впервое хранилище — 200 т,
во второе хранилище — 300 т.
Задача 4
Втаблице приведены годовые данные о трудоемкости производства I т цемента (нормо-смен) (N —последняя цифра зачетной книжкистудента):Текущий номер года (t) 1 2 3 4 5 6 7 8 9 10
Трудоемкость 1 т цемента (yi) 7,9+0,N 8,3+0,N 7,5+0,N 6,9+0,N 7,2+0,N 6,5+0,N 5,8+0,N 4,9+0,N 5,1+0,N 4,4+0,N
Задание1. Сгладить временной ряд методом простой скользящей средней, выбрав длинуинтервала сглаживания m = 3;результаты отразить на графике.
Задание2. Определить наличие тренда во временном ряду методом Фостера — Стьюарта.Табличные значения статистики Стьюдента taпринять равными при уровне значимостиa = 0.05 ta = 2,23, а при a = 0,30 — ta = 1,09; другие необходимые табличныеданные приведены в таблице 4.5 учебника на с.153 (описание метода Фостера — Стьюарта см. учебник с. 151- 153).
Задание 3. Для исходноговременного ряда построить линейную трендовую модель />, определив ее параметры на основеметода наименьших квадратов (соответствующую систему нормальных уравнений см. вучебнике на с. 196 формула (5.5)).
Задание 4. Оценитьадекватность построенной модели на основе исследования
а) близостиматематического ожидания остаточной компоненты (ряда остатков) нулю;критические значения r-критерия принять равным тому числу, как указанно взадании 2;
б) случайности отклоненийостаточной компоненты по критерию пиков (поворотных точек); Расчеты выполнитьна основе соотношения 5.9. учебника на с. 200;
в) независимости уровнейряда остатков (отсутствие автокорреляции) на основе критерия Дарбина — Уотсона(см. учебник с. 203— 204), используя в качестве критических значений dl= 1.08 и d2 = 1,36; если критерий Дарбина — Уотсона ответа не дает,исследование независимости провести по первому коэффициенту автокорреляции:
/>,
где ei — уровни остаточной компоненты;
Модуль первогокоэффициента автокорреляции сравнить с критическим уровнем этого коэффициента,значение которого принять равным 0,36;
г) нормальности законараспределения уровней остаточной компоненты на основе RS-критерия;
В качестве критическихзначений принять интервал от 2,7 до 3,7 (см. учебник, стр. 201—-202).
Задание 5. Оценитьточность построенной трендовой линейной модели, используя показатели среднегоквадратического отклонения от линии тренда (формула (5,17) учебника на с. 210,k = 1) и средней относительной ошибки аппроксимации (формула (5.14) учебника нас. 204).
Задание 6. Построитьточечный и интервальный прогноз трудоемкости производства 1 т цемента на двашага вперед (формула (5.18) учебника на с. 210). Результаты моделирования ипрогнозирования отразить на графике.
Всепромежуточные результаты вычислений представить в таблицах, вычисленияпровести с двумя десятичными знаками в дробной части.
Вариант3. Условия при N = 3Текущий номер года (t) 1 2 3 4 5 6 7 8 9 10
Трудоемкость 1 т цемента (yi) 8,2 8,6 7,8 7,2 7,5 6,8 6,1 5,2 5,4 4,7
Решение.
Задание1. Сглаживание ряда Y(t) произведем по простой скользящей средней
/>
Результатыв таблице 1. Таблица 1. Сглаживание ряда динамики t Факт Y(t) Скользящая сумма Скользящее среднее 1 8,2 - - 2 8,6 24,6 8,20 3 7,8 23,6 7,87 4 7,2 22,5 7,50 5 7,5 21,5 7,17 6 6,8 20,4 6,80 7 6,1 18,1 6,03 8 5,2 16,7 5,57 9 5,4 15,3 5,10 10 4,7 - -
/>
Задание2.
Этап 1.Строим две числовые последовательности kt и ltt
kt
lt 2 1 3 1 4 1 5 6 1 7 1 8 1 9 10 1
Этап 2.Находим величины
/>7; />1 – 6 = -5.
Этап 3.Для n = 10 выпишем табличные значения m = 3,858; s1 = 1,288; s2 = 1,964.
Вычисляем
/>2,44; />2,55.
Этап 4.
Так какрасчетные значения ts = 2,44 и td = 2,55 большетабличного значения ta = 2,23, то в данном временном рядуприсутствуют тренд и тенденция в дисперсии ряда.
Изтаблицы 1 видно, что ряд Y(t) имеет тенденцию к снижению.
Задание3. Линейную трендовую модель ищем в виде />. Параметры модели а0,а1 найдем, решив систему уравнений
/>.
n = 10.
Составимрасчетную таблицу 2. Таблица 2 t y
t2 yt 1 8,2 1 8,2 2 8,6 4 17,2 3 7,8 9 23,4 4 7,2 16 28,8 5 7,5 25 37,5 6 6,8 36 40,8 7 6,1 49 42,7 8 5,2 64 41,6 9 5,4 81 48,6 10 4,7 100 47,0 55 67,5 385 335,8
Получаемсистему
/>; />.
Получили1,5а1 = -0,64, а1 = -0,64:1,5 = -0,43; а0=6,75 — 5,5а1 = 6,75 — 5,5×(-0,43) = 9,12.
Получилитрендовую модель: />.
Задание4.
Оценимкачество модели. Для этого найдем расчетные значения Yp(t),подставляя t =1, …, 10 в трендовую модель, найдем отклонения расчетных значенийот исходных E(t) = Y(t) — Yp(t). Для исследования модели наадекватность составим таблицу 3. Таблица 3. Расчетные величины для оценки адекватности модели t Y(t)
Yр(t) E(t) k
E(t)2 E(t)-E(t-1)
(E(t)-E(t-1))2 E(t)*E(t-1) IE(t)I:Y(t)*100 1 8,2 8,69 -0,48 0,24 5,915 2 8,6 8,26 0,35 1 0,12 0,83 0,69 -0,17 4,012 3 7,8 7,83 -0,03 0,00 -0,37 0,14 -0,01 0,321 4 7,2 7,40 -0,20 1 0,04 -0,17 0,03 0,00 2,708 5 7,5 6,97 0,54 1 0,29 0,73 0,53 -0,10 7,133 6 6,8 6,54 0,27 0,07 -0,27 0,07 0,14 3,897 7 6,1 6,11 -0,01 0,00 -0,27 0,07 0,00 0,082 8 5,2 5,68 -0,48 1 0,23 -0,47 0,22 0,00 9,135 9 5,4 5,25 0,15 1 0,02 0,63 0,40 -0,07 2,87 10 4,7 4,82 -0,12 0,01 -0,27 0,07 -0,02 2,447 S 67,5 67,5 0,00 5 1,01 2,22 -0,22 38,520
а)Близость математического ожидания остаточной компоненты нулю.
Суммаостатков равна 0. Расчетное значение критерия Стьюдента
/>0.
Критическоезначение ta = 2,23 больше расчетного, следовательно, математическоеожидание остаточной компоненты равно нулю.
б)Проверка остатков E(t) на случайность.
Критическоеколичество поворотных точек для n =10 равно 2.
/>2.
Дляданного ряда количество таких точек k = 5. Это больше 2, поэтому остатки E(t) случайные.
в)Проверка остатков E(t) на независимость.
Независимость(отсутствие автокорреляции) проверим, используя критерий Дарбина-Уотсона:
/>, />2,20.
d > 2,преобразуем d' = 4 — d = 4 — 2,20 = 1,80, получили 1,36
г)Проверка остатков на соответствие нормальному закону распределения.
ИспользуетсяRS — критерий:
/>, где />0,36.
/>2,87,
RSт= 2,7 — 3,7; так как расчетное значение RS — критерия RSрасч = 2,87попадает внутрь интервала от 2,7 до 3,7, то остатки E(t) подчиняются понормальному закону распределения.
Вывод:так как выполняются все условия адекватности, то модель является полностьюадекватной реальному ряду экономической динамики. Ее можно использовать дляпостроения прогнозных оценок
Задание5.
Определимточность модели.
Среднееквадратическое отклонение от линии тренда
/>0,36.
Средняяотносительная ошибка
/>.
Так как3,85%
Задание6.
Точечныйпрогноз для Y получим, подставляя в трендовую модель t =11 и t = 12.
/>4,385; />3,955.
Дляинтервального прогноза найдем ширину интервала
/>.
Длячисла степеней свободы k = n -2 = 10 — 2 = 8 и уровня значимости a = 0,05 ta= 2,31.
/>1,00; />1,04.
Границыинтервалов прогноза: НГ = Yn+k — U(k), ВГ = Yn+k + U(k).
Результатыпрогноза представлены таблицей 4. Таблица 4. Точечный и интервальный прогноз t U(k)
Yn+k p НГ ВГ 10 1,00 4,39 3,39 5,38 11 1,04 3,96 2,91 5,00
Построимграфик.
/>
Задача5.
Втаблице представлены первый (хij) и второй (Yi) квадранты схемы межотраслевого баланса производства и распределенияпродукции для трехотраслевой экономической системы (N — последняя цифра зачетной книжки студента):Потребляющие отрасли Производящие отрасли Конечная продукция 1 2 3 1 200+10N 50+10N 300+10N 200+10N 2 150+10N 250+10N 0+10N 100+10N 3 230+10N 50+10N 150+10N 300+10N
Задание1. Рассчитать объемы валовой продукции отраслей (формула (6.2) учебника на с.237).
Задание2. Рассчитать матрицу коэффициентов прямых затрат А = (aij) (формула (6.4) учебника на с. 238).
Задание3. Найти матрицу коэффициентов полных затрат B = (bij), используя формулу (6.16) учебника на с. 244.
Задание4. Рассчитать объемы условно чистой продукции отраслей Zj, используя формулу (6.1) учебника на с. 236.
Задание 5. Представить втаблице полную схему межотраслевого баланса (в соответствии с принципиальнойсхемой МОБ; табл. 6.1 учебника на с.234).
Вариант 3. Условия при N= 3. Таблица 1. Потребляющие отрасли Производящие отрасли Конечная продукция 1 2 3 1 230 80 330 230 2 180 280 30 130 3 260 80 180 330
Решение.
Задание1.
Объемваловой продукции находим по формуле
/>.
Результатыв таблице 2. Таблица 2. Потребляющие отрасли Производящие отрасли Конечная продукция Валовой продукт 1 2 3 1 230 80 330 230 870 2 180 280 30 130 620 3 260 80 180 330 850
Задание2.
Коэффициентыматрицы прямых затрат находим по формуле
/>
Получаемматрицу А.
/>0,26 0,13 0,39 А = 0,21 0,45 0,04 0,30 0,13 0,21
Задание3. Чтобы найти матрицу коэффициентов полных затрат В, запишем матрицу Е — А,где Е — единичная матрица.
/> 0,74 -0,13 -0,39 Е — А = -0,21 0,55 -0,04 -0,30 -0,13 0,79
МатрицаВ находится по формуле