- •Линейные методы оптимизации. Задачи линейного программирования
- •1.1 Общая постановка задачи линейного программирования.
- •Линейное программирование в экономике
- •1.3 Решение систем линейных алгебраических уравнений в форме жордановых таблиц
- •1.3.1 Основные понятия
- •1.3.2 Жордановы таблицы
- •1.3.3 Алгоритм решения слау в форме жордановых таблиц
- •1.3.4 Примеры решения типовых задач
- •1.4 Базисные и опорные решения слау
- •1.4.1 Основные понятия
- •1.4.2 Алгоритм отыскания опорных решений слау
- •1.4.3 Примеры решения типовых задач
- •1.3.5 Задания для самостоятельного решения
- •Задания для самостоятельной работы
- •Графическое решение задач линейного программирования
- •1.5.1 Геометрическая интерпретация
- •1.5.2 Алгоритм графического решения злп
- •1.5.3 Пример решения типовой задачи
- •1.5.4 Задания для самостоятельной работы
- •1.6 Симплексный метод решения задач линейного программирования
- •1.6.1 Укрупненный алгоритм симплексного метода
- •1.6.2 Алгоритм отыскания начального опорного плана
- •1.6.3 Алгоритм отыскания оптимального опорного плана
- •1.6.4 Пример решения типовой задачи
- •1.6.5 Задания для самостоятельной работы
- •Двойственность в линейном программировании
- •1.7.1 Понятие двойственности для симметричных задач
- •1.7.2 Экономическая интерпретация симметричных двойственных задач
- •1.7.3 Связь между решениями прямой и двойственной задачи
- •2. Оптимальное распределение ресурсов. Транспортная задача
- •2.1. Метод северо-западного угла (мсзу)
- •2.2. Метод минимального тарифа (ммт)
- •2.3. Определение оптимального плана перевозок методом потенциалов
- •2.4. Транспортная задача с усложнениями
- •2.5. Транспортная задача по критерию времени
- •2.6 Задания для самостоятельной работы
- •3. Элементы нелинейного программирования
- •Постановка задач нелинейного программирования
- •Особенности решения задач нелинейного программирования
- •Метод множителей Лагранжа
- •4 Метод наименьших квадратов
- •4.1 Некоторые типы эмпирических формул
- •Примеры решения типовых задач
- •4.3 Задания для работы в аудитории
- •4.4 Подбор эмпирических формул по выборочным данным
- •4.3 Задание для самостоятельной работы
- •Элементы сетевого планирования
- •При управлении такими проектами применяются специальные способы изображения сетей, позволяющие разработать очень эффективные и простые процедуры вычислений информации о состоянии проекта.
- •5.1 Построение сетевой модели
- •5.2 Наиболее ранний срок наступления события
- •5.3 Наиболее поздний срок наступления события
- •Пример 3. Для всех узлов (событий) сети из примера 1 определить наиболее поздний допустимый срок наступления события.
- •5.4 Резерв времени и критический путь
- •5.5 Оптимизация плана комплексных работ
- •5.6 Задания для самостоятельной работы
- •Литература
- •Методы решения оптимизационных задач
- •346493, Донской гау, пос. Персиановский,
4.3 Задания для работы в аудитории
I. Имеются следующие данные о величинах x и y. Предполагая, что между
x и y существует линейная зависимость, найти эмпирическую формулу
у=ɑх + b методом наименьших квадратов.
Задача 1.
х – цена на товар (усл.ед.); у – уровень продаж (тыс.ед.):
Таблица 13
xi |
3,0 |
4,0 |
5,0 |
6,0 |
7,0 |
yi |
200 |
160 |
120 |
90 |
80 |
Задача 2.
х – уровень потребления электроэнергии на предприятии (млн.кВт . ч); у – себестоимость единицы продукции:
Таблица 14
xi |
30 |
40 |
50 |
60 |
70 |
yi |
18 |
20 |
21 |
24 |
25 |
II. По экспериментальным данным построить методом наименьших квадратов линейную зависимость у=ɑх + b. Сравнить полученную зависимость с альтернативной и определить, какая из них лучше соответствует экспериментальным данным.
Задача 3.
Таблица 15
xi |
2 |
2,5 |
3 |
3,5 |
4 |
yi |
4,2 |
5,5 |
6,9 |
8 |
9,5 |
Альтернативная зависимость y=2x + 0,1x2.
Задача 4.
Таблица 16
xi |
1 |
2 |
3 |
4 |
5 |
yi |
1,0 |
1,4 |
1,7 |
2,0 |
2,2 |
Альтернативная
зависимость y=
Задача 5.
Таблица 17
xi |
1,0 |
1,5 |
2,0 |
2,5 |
3,0 |
yi |
0,50 |
0,30 |
0,25 |
0,18 |
0,12 |
Альтернативная зависимость y=2-х
4.4 Подбор эмпирических формул по выборочным данным
Прибыль предприятия за некоторый период деятельности по годам приведена ниже. Год: xi, прибыль (млн. руб): yi.
Таблица 18
-
xi
yi
1
5
2
4
4
3,5
Требуется подобрать тип зависимости, используя метод наименьших квадратов, исходя из условия минимума суммы квадратов отклонений. Сделать чертеж одной из наиболее подходящих зависимостей, нанести на график исходные данные.
1.Линейная зависимость: у=ax+b.
Запишем нормальную систему для определения параметров ɑ и b зависимости: у = ɑx + b
i= yрасч - yi. .
Таблица 19
-
i
xi
yi
xi2
xiyi
yiрасч
i
i2
1
1
5
1
5
4,79
0,21
0,0441
2
2
4
4
8
4,33
-0,33
0,1089
3
4
3,5
16
14
3,41
0,09
0,0081
7
12,5
21
27
0,1611
ɑ
-0,46; b
5,25
y = - 0,46х + 5,25.
Вычисляем yiрасч :
x1= 1; y1расч=-0,461+5,25=4,79
x1= 2; y2 расч =-0,462+5,25=4,33
x1= 4; y3 расч =-0,464+5,25=3,41.
2. Квадратичная зависимость: y = ax2 + bx + с.
Запишем нормальную систему для определения параметров ɑ, b и c данной зависимости:
,
, i= yрасч - yi .
,
Таблица 20
-
i
xi
yi
xi yi
xi2
xi2 yi
xi3
xi4
yiрасч
i
i2
1
1
5
5
1
5
1
1
5
0
0
2
2
4
8
4
16
8
16
4
0
0
3
4
3,5
14
16
56
64
256
3,5
0
0
7
12,5
27
21
77
73
273
0
ɑ = 0,25; b
= -1,75; c
= 6,5
y = 0,25x2 - 0,75x + 6,5
Вычисляем yiрасч:
x1=1; y1расч =0,25 12 – 1,75 1 + 6,5 =5
x2=2; y2расч =0,25 22 - 1,75 2 + 6,5 =4
x3=4; y3расч =0,25 42 - 1,75 4 + 6,5 =3,5.
3. Дробно-линейная зависимость: y = ɑ + .
Запишем нормальную систему для определения параметров ɑ и b данной зависимости:
i= yрасч - yi .
Таблица 21
-
i
xi
yi
xi2
1/xi
1/xi2
yi /xi
yiрасч
i
i2
1
1
5
1
1
1
5
5
0
0
2
2
4
4
0,5
0,25
2
4
0
0
3
4
3,5
16
0,25
0,0625
0,875
3,5
0
0
7
12,5
21
1,75
1,3125
7,875
0
a=3;
b=2
y=3
+
.
Вычисляем yiрасч:
x1=1;
y1расч
=3 +
=
5
x2=2;
y2расч
=3 +
= 4
x3=4;
y3расч
=3 +
=3,5
4. Показательная зависимость: y = ɑ bx
Запишем нормальную систему для определения параметров ɑ и b данной зависимости:
i= yрасч - yi .
Таблица 22
-
i
xi
yi
xi2
lnyi
xi lnyi
yiрасч
i
i2
1
1
5
1
1,61
1,61
4,86
0,14
0,0196
2
2
4
4
1,39
2,78
4,37
-0,37
0,1369
3
4
3,5
16
1,25
5
3,54
-0,04
0,0016
7
12,5
21
4,25
9,39
0,1581
lnb=-0,11;
b=e-0,110,9;
lna=1,68; a=e1,685,4
y = 5,40,9x
Вычисляем yiрасч:
x1=1; y1расч =5,4 0,914,86
x2=2; y2расч = 5,4 0,924,37
x3=4; y3расч =5,4 0,943,54
Суммы квадратов отклонений расчетных данных от теоретических данных для найденных зависимостей записаны в табл.23.
Таблица 23
-
i
Зависимость
i2
1
y=-0,46х+5,25
0,1611
2
y=0,25x2-0,75x+6,5
0
3
y=3 +
0
4
y=5,40,9x
0,1581
ВЫВОД: Наилучшим образом подходит дробно-линейная зависимость (y=3 + ) и квадратичная зависимость (y=0,25x2-0,75x+6,5).
Сделаем чертеж одной из наиболее подходящих зависимостей, нанесем на график исходные данные.
