- •Линейные методы оптимизации. Задачи линейного программирования
- •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, Донской гау, пос. Персиановский,
Примеры решения типовых задач
Пример 1.
Имеются следующие данные о цене на нефть х (усл.ед) и индексе акций нефтяных компаний у (усл.ед).
Таблица 3
хi |
17,3 |
17,0 |
18,3 |
18,8 |
19,2 |
18,5 |
yi |
537 |
534 |
550 |
555 |
560 |
552 |
Предполагая, что между переменными х и у существует линейная зависимость, найти эмпирическую формулу y=ɑх + b методом наименьших квадратов.
Решение.
Перепишем таблицу в виде столбцов и проведем необходимые вычисления.
Таблица 4
n |
xi |
yi |
xi2 |
xiyi |
1 |
17,3 |
537 |
299,29 |
9290,1 |
2 |
17,0 |
534 |
289,00 |
9078,0 |
3 |
18,3 |
550 |
334,89 |
10065,0 |
4 |
18,8 |
555 |
353,44 |
10434,0 |
5 |
19,2 |
560 |
368,64 |
10752,0 |
6 |
18,5 |
552 |
342,25 |
10212,0 |
∑ |
109,1 |
3288 |
1987,51 |
59831,1 |
Составим систему уравнений :
1987,51ɑ + 109,1 b = 59 831,1
109,1 ɑ + 6 b = 3288
Откуда ɑ=11,946, b=330,78, т.е
y = 11,94 x + 330,78.
Пример 2.
Найти квадратичную зависимость для следующих данных. Предприятие, производящее сельскохозяйственную технику, провело опрос дилеров и получила следующие сведения о спросе Q на свою продукцию в зависимости от цены P:
Таблица 5
P = х, млн. руб |
1,7 |
1,9 |
2,0 |
2,1 |
Q = y, тыс. штук |
27 |
25 |
19 |
9 |
Решение.
Перепишем таблицу в виде столбцов и проведем необходимые вычисления.
Таблица 6
п |
xi |
yi |
xi2 |
xi3 |
xi4 |
xi yi |
xi2 yi |
1 |
1,7 |
27 |
2,89 |
4,913 |
8,3521 |
45,9 |
78,03 |
2 |
1,9 |
25 |
3,61 |
6,859 |
13,0321 |
47,5 |
90,25 |
3 |
2,0 |
19 |
4,00 |
8,000 |
16,0000 |
38,0 |
76,00 |
4 |
2,1 |
9 |
4,41 |
9,261 |
19,4481 |
18,9 |
39,69 |
∑ |
7,7 |
80 |
14,91 |
29,033 |
56,8323 |
150,3 |
283,97 |
Система линейных уравнений для определения величин ɑ, b, с примет вид
5
6,8323ɑ
+ 29,0330 b
+ 14,9100с = 283,97,
29,0330 ɑ + 14,9100 b + 7,7000с = 150,30,
14,9100 ɑ + 7,7000 b + 4 с = 80,00.
Решив систему, получим значения ɑ, b, с. Функция спроса будет иметь вид Q = 0,02 Р2 - 16.64 Р - 6,67.
Пример 3.
Имеются следующие данные о величине пробега автомобиля х (тыс.км) и у – расходе масла (л/тыс.км):
Таблица 7
хi |
50 |
70 |
90 |
110 |
130 |
yi |
0,2 |
0,5 |
0,8 |
1,1 |
1,3 |
Полагая, что между переменными х и у существует линейная зависимость, найти эмпирическую формулу у=ɑх + b методом наименьших квадратов.
Решение.
Перепишем таблицу в виде столбцов и проведем необходимые вычисления.
Таблица 8
n |
xi |
yi |
xi2 |
xiyi |
1 |
50 |
0,2 |
2500 |
10 |
2 |
70 |
0,5 |
4900 |
35 |
3 |
90 |
0,8 |
8100 |
72 |
4 |
110 |
1,1 |
12100 |
121 |
5 |
130 |
1,3 |
16900 |
169 |
∑ |
450 |
3,9 |
44500 |
407 |
Система нормальных уравнений имеет вид:
44500ɑ + 450b = 407
450ɑ + 5b = 3,9
Ее решения ɑ=0,014, b = -0,48. Таким образом, линейная зависимость имеет вид: y= 0,014x – 0,48
Пример 4.
Имеются следующие данные о расходах на рекламу x ( тыс. усл.ед.) и сбыте продукции (тыс. ед.):
Таблица 9
хi |
1 |
2 |
3 |
4 |
5 |
yi |
1,6 |
4,0 |
7,4 |
12,0 |
18,0 |
Предполагая, что между переменными x и y существует квадратичная зависимость вида y = ɑx2 + bx + c, найти значения параметров ɑ, b, c методом наименьших квадратов.
Перепишем таблицу в виде столбцов и проведем необходимые вычисления.
Таблица 10
n |
xi |
yi |
xi2 |
xi3 |
xi4 |
xiyi |
xi2 yi |
1 2 3 4 5 |
1 2 3 4 5 |
1,6 4,0 7,4 12,0 18,0 |
1 4 9 16 25 |
1 8 27 64 125 |
1 16 81 256 625 |
1,6 8,0 22,2 48,0 90,0 |
1,6 16,0 66,6 196,0 450,0 |
∑ |
15 |
43,0 |
55 |
225 |
979 |
169,8 |
680,2 |
Система нормальных уравнений имеет вид:
9 79ɑ + 225b + 55с = 680,2,
225 ɑ + 55b + 15 с = 169,8,
55 ɑ + 15 b + 5 с = 49,0.
Её решения ɑ=0,3, b=0,48, c=5,06.
Искомая зависимость имеет вид: y= 0,3x2 + 0,48x +5,06.
Пример 5.
Имеется шесть измерений пары переменных (х,у) результаты которых приведены в таблице 11:
Таблица 11
xi |
1 |
2 |
3 |
4 |
yi |
0,2 |
0,3 |
1,0 |
1,2 |
Методом
наименьших квадратов построить линейную
зависимость у=ɑх + b.
Сравнить полученную зависимость с
зависимостью у=
.
Решение.
Аналогично примерам 1,3 найдем уравнение линейной регрессии:
у= 0,37х – 0,25.
Сравним
величины U
=
для
найденной линейной зависимости и
зависимости у=
.
Промежуточные вычисления представим
в таблице:
Таблица 12
n |
xi |
yi |
|
0,37хi– 0,25 |
( |
(0,37xi – 0,25 – уi)2 |
1 2 3 4 |
1 2 3 4 |
0,2 0,3 1,0 1,2 |
0,125 0,5 1,125 2 |
0,12 0,49 0,76 1,23 |
0,005625 0,040000 0,015625 0,640000 |
0,0064 0,0361 0,0576 0,0009 |
∑ |
- |
- |
- |
- |
0,701250 |
0,1010 |
Как видно Uлин< Uкв, следовательно, линейная зависимость предпочтительнее.
