Алгоритм получения задачи, двойственной данной.
Исходя из св-в:
число переменных одной задачи = числу ограничений др. задачи.
а одной ф-я max-ется , в др. находится min
коэф-ты при переменных в выр-нии функции цели одной задачи явл. Равными частями системы ограничений др. задачи.
система ограничений одной и др. задачи задается как система неравенств: нер-ва смысла <= при max, нер-ва >= при min
матрицы коэф-ов при переменных транспонированы относительно друг друга.
условия не отрицательности переменных сохр-ется у той и др. задачи.
Задачи отвечающие св-вам явл. симметричными взаимодвойственными, при этом одну из них наз. Прямой, вторую двойственной.
привести прямую задачу к исходной форме. Если в прямой задаче отыскивается max (знаки нер-ва <=) , для двойственной ищем min
написать расширенную матрицу прямой з.
транспонировать эту матрицу
записать условие двойственной задачи.
1 теорема двойственности
(Основная)
Если одна из задач имеет оптимальное решение, то др. задача также имеет оптимальное решение, функции цели = между собой, т.е. fmax=gmin
Если ф-я цели одной из задач не ограниченна, то условие др. з. противоречиво.
2 теорема двойственности
(О дополняющей нежесткости)
Если при подстановке компонентов оптимального плана в систему ограничений исходной задачи i-е ограничение обращается в равенство, то i-я компонента др. з. положительна.
Если i-я компонента дв. з. =0, то i-е ограничение прямой задачи выполняется, как строгое нер-во.

3 теорема двойственности
(Об оценках) (она же 3-св-во ООО)
значения переменных yi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi системы ограничений – нер-в прямой задачи на величину EMBED Equation.3
EMBED Equation.3
Св-ва Объективно-
обусловленных оценок
ООО выступает в качестве показателей степени дефицитности ресурсов. Чем дефицитнее ресурс, тем выше его оценка.
величина ООО показывает, как изменяется ф-я цели при увеличении запаса соответствующего ресурса на одну единицу. (с-во справедливо при относительно небольших изменениях запаса ресурсов, т.е. в пределах интервалов устойчивости.)
ООО выступает в качестве показателя целесообразности выпуска новых видов изделий.
Понятие о временном ряде
Совокупность значений к-л показателя упорядоченная во времени есть вр.р.
Уровни вр.р. состоят из следующих компонентов:
1. Тренд Ut (долговременная тенденция в изменении показателя)
2. Сезонная компонента St (отображает периодические колебания происходящие в течение года. Вр.р. должен быть задан либо квартальными, либо месячными данными. Сезонность присутствует на транспорте)
3. Циклическая компонента Ct (отражает повторяющееся во времени процесс, но происходящий через ряд лет (урожайность))
4. Остаточная компонента Et (есть часть вр.р. оставшаяся после удаления из него регулярных компонентов: тренда, сезонных и циклических)
Если регулярные комп-ты выделить правильно, то остаточная будет удовлетворять требованиям:
M(E) =0
D(E) const
Последовательные ур-ни ее не коррелированны
Ряд распределения отс. комп. подчиняется норм. закону рапр.







Предварительный анализ вр.р.
Анализ вр.р. начин. С выявления аномальных наблюдений.
Причины вызвавшие аномальные наблюдения:
заведомо подготовленные аном. набл.
ошибки вызванные неверной передачей статистич. Информации
Подлежат устранения:
ошибки второго рода носят объективный хар-р. АН возникшие из-за этих ошибок устранению не подлежат. Для выявления АН используются методы:
метод Ирвина (для каждого уровня ряда начиная со 2-го вычисляют EMBED Equation.3 где EMBED Equation.3 - средн. кв. откл. в данном вр.р.
EMBED Equation.3 сравнивают EMBED Equation.3 (кот. нах. по таблице)
если EMBED Equation.3 , то наблюдение с номером t явл-ся аномальным, в противном случае yt неаном. набл. После обнаружения аном. набл. выясн. его причину.
Методы определение наличия
тренда
метод проверки разности средних уровней (метод «Земских статистик»)
вр.р. делится на 2 примерно равные по кол-ву ур-ней части. Для каждой части вычисляют ср. ариф. и дисперсию. Большую дисп. делят на меньшую и получают расчетное значение критерия Фишера. F расч сравнивают с F Крит (из таблицы), если Fрасч <Fкрит, делаем вывод о равенстве дисперсий этих двух частей вр.р.
Знаковый критерий Кокса и Стюарта
Метод Фостера-Стюарта. Применяют для рядов с любой тенденцией. Для каждого уровня ряда, начиная со второго вычисляются величины: kt и lt. Kt = 1 если yt > всех предыдущих уровней, kt = 0 в ост. случ. Lt =1 если yt < всех пред. Уровней, =0 в ост. случ. Значения величин: st=kt+lt; dt=kt-lt. Находим сумму s и d. t расч для s = EMBED Equation.3 ; t расч для d = EMBED Equation.3 , где … табличные значения. Каждое t расч сравн. с t крит. Если t расч для s > t крит. То есть тренд у дисперсии ряда. Если t расч для d > t крит, то есть тренд.




Сглаживание временных рядов
Простая скользящая средняя.
Выбирают интервал сглаживания (кол-во ур-ней берут нечетное). 1-й сглаженный уровень придется на середину интервала сглаживания. Недостатки: Ур-ни равноправны по отношению к сглаженному ур-ю; в процедуре сглаживания участвуют не только предыдущие но и последующие ур-ни ряда; теряются p-первых и p – последних уровней ряда, где EMBED Equation.3
Метод взвешенной скользящей средней
Уровни ряда входящие в интервал сглаживания берутся с некоторым определенным весом. Например для m=5 эти веса -3, 12, 17, 12, -3; Для m=3 … 1,2,1. Недостатки те же.
Метод экспоненциальной скользящей средней.
Сглаживание свободных от недостатков прост с.с. и взв. с.с. Сглаженный уровень ряда нах по формуле: EMBED Equation.3 , где EMBED Equation.3 параметр сглаживания. EMBED Equation.3 принадлежит интервалу, если EMBED Equation.3 явл наилучшим Нах методом подбора.
Хар-ка полиномиальных кривых роста
При помощи кр.р. производится прогнозирование (предсказание поведения показателя в будущем периоде по его поведению в прошлый и настоящий момент). Прогнозирование производится на основании построенной МатМодели вр.ряда.
Yt = a0+a1t. Найдем абсолютные приросты 1-го порядка для ut.
Ut(1)=yt+1-yt=(a0+a1(t+1))-(a0+a1t)=a1=const
EMBED Equation.3 абсолютные приросты 1-го порядка линейны относительно t
Найдем абс приросты 2-го порядка (приросты от приростов 1-го порядка)
Ut(2)=ut+1(1)-ut(1)=((a1+a2)+2a2(t+1))-((a1+a2)+2a2t)=2a2=const
Для полинома 2-й степени пост явл-ся абс приросты 2-го порядка
Для полинома k-ой степени пост будут абс приросты k-го порядка




Хар-ка экспоненциальных
кривых роста
При помощи кр.р. производится прогнозирование (предсказание поведения показателя в будущем периоде по его поведению в прошлый и настоящий момент). Прогнозирование производится на основании построенной МатМодели вр.ряда.
Yt=a*bt (исх уровень)
Yt=k+ abt
Для простой экспоненты абс приросты любого порядка зависят от исходного уровня и от t
Для модифицированной k-это предел насыщения, т.е. значение меньше либо больше которого не может быть k определяется либо из прошлого опыта, либо из графика. SHAPE \* MERGEFORMAT t
k

Зная k ур-ние модификации экспоненты имеет вид yt-k= abt
Хар-ка S-образных кривых роста
При помощи кр.р. производится прогнозирование (предсказание поведения показателя в будущем периоде по его поведению в прошлый и настоящий момент). Прогнозирование производится на основании построенной МатМодели вр.ряда.
Если изменение эк-го показателя хар-ся sобразной кривой, то он в своем развитии проходит 4 этапа:
На 1 э абс приросты отсутствуют; на 2 э возрастают, на 3 постоянны, на 4 уменьшаются.
Из S образных кривых наиболее часто встречаются:
Кривая Гомперца; Кривая Перла-Рида; различные типы логистических кривых.


Выбор наилучшей кривой роста: метод конечных разностей.
м. Тинтнера Суть м.: для данного ряда нах абс приросты 1-го 2-го k-го порядка. Для каждого исходного ряда, а т ж для приростового р вычисляют дисперсию. Каждое очередное вычисленное значение дисперсии сравн с предыдущим. Наилучшим выравнивающим полиномом будет полином k-1 если S2 k-1 = S2k М. Т. позволяет определить наилучш. выравн. кривую только среди полиномиальных кр.
Метод наименьших квадратов
Наилучшей кривой из всех кр явл та, для которой сумма квадратов отклонений исходных значений yt и модельных EMBED Equation.3 значения явл наименьшей. Это принцып наименьших квадратов, леж в основе м. наименьших квадратов
EMBED Equation.3
Ф-я S имеет экстремум в той точке, в кот частные производные обращ в 0
Найдем частн произв
EMBED Equation.3
1-й критерий адекватности
Док-ть гипотезу M(E)=0. Для проверки используем .
EMBED Equation.3
S – ср квадр-е откл-е в ряду значений остаточной компоненты
Если t расч < t крит= EMBED Equation.3 то гипотеза принимается
2-й критерий адекватности
(критерий поворотных точек)
т.п. – это значение остаточной компоненты Et, если оно одновременно >2-х соседних значений, либо < них. При пом 2-го крит проверяется случайность ряда значений Et.. В случайном ряду число п.т. p удовлетворяет нер-ву
EMBED Equation.3 полученное значение не округляется!!!





3-й критерий адекватности
(критерий Дарбина-Уотсона)
Проверяется независимость последовательных уровней Et
EMBED Equation.3
d расч сравн с двумя крит-ми уровнями. Знач-я крит-х ур-ней зависят от длины вр. р.
I-уровни зависимы; II – критерий не дает ответа; III – уровни независимы
I II III
0 0,8 1,36 2
Если dp>2, то треб доп исследование dp’=4-dp (больше 4-х не бывает)
r(1)-1-й коэффициент автокорреляции
EMBED Equation.3 если r(1) <0.36, то ур-ни независимы.
4-й критерий адекватности
(R/S критерий)
проверяется: соответствует ли ряд распределения Et нормальному закону. Для этого
EMBED Equation.3 Если R/S расч попадает в пром от (2,7;3,7), то Et распределяется по норм закону.
Точность модели
Определяется по величине средней относительной ошибки
EMBED Equation.3 Если <=5% модель точна;
5%<=E отн <=10% - модель удовл; E отн > 10% - модельне точна






Прогнозирование при помощи кривой роста
Для получения прогнозных значений подставим в модель вместо t последующие значения. k-шаг прогноза; t=n+k (точечный прогноз)
Вероятность того, что точечный прогноз сбудется =0, поэтому строим интервальный прогноз. uk-ширина доверительного интервала
EMBED Equation.3 где Sy – средняя квадр ош модели
EMBED Equation.3 t крит = EMBED Equation.3
Точечный интервальный прогноз по м. Брауна
М. Б. не учитывает сезонную и циклическую компоненты (в ней только тренд и Et)
Для прогнозирования используем ур-ние с последнего шага. EMBED Equation.3 = а0+а1 EMBED Equation.3 , при EMBED Equation.3 =1, =2 (точечный прогноз)
Для интервального прогноза нужно рассчитать ширину доверительного интервала
EMBED Equation.3
где EMBED Equation.3
Определение начальных
параметров модели Брауна
М. Б. не учитывает сезонную и циклическую компоненты (в ней только тренд и Et)
Пересчет параметров осущ по формулам
EMBED Equation.3 где B коэфф дисконтирования данных. Наилучшее B (0,1;0,4)
Модель на начальном шаге имела вид EMBED Equation.3 =а0+а1t
EMBED Equation.3 , а0 и а1 берем из предыстории




Канонический вид ЗЛП
ЗЛП назыв заданной в каноническом виде, если система ограничений ее явл системой ур-ний с неотриц правыми частыми. Любое нер-во можно привести к ур-нию путем введения в него любой дополнительной неотрицательной переменной. EMBED Equation.3
EMBED Equation.3 xj>=0; j=1
Графический метод решения ЗЛП
Необходимо:
построить множество решений сис ограничений. В общем случае реш-ем явл выпуклый многоугольник n-мерного пространства. Любая точка многоуг-ка явл допустимым решением.
Находим оптимальный план. Точки многоугольника в кот ф-я цель принимает к-л определенное значение f(x)=a. Эти точки располагаем на прямой наз. линией уровня. При f(x)=а линия уровня пройдет параллельно (0;0). Имея 2-е линии уровня достаточно, чтобы определить направление вектора-градиента. Перемещаем лин уровня до той
Особые случаи решения ЗЛП
графически
оптимальное решение задачи единственно
оптимальное решение существует и не одно
SHAPE \* MERGEFORMAT F(x)=a
А
B
fmax=f(А)=f(B)=f(AB)
ф-я-цель не ограничена
SHAPE \* MERGEFORMAT F(x)=a
А
B

Если у многоугольника решений нет, то система противоречива, следовательно ЗЛП противоречива



Соотношение между угловыми точками множества допустимых решений ЗЛП…
Между угл точками множ доп решений системы лин-х нер-в и допуст базисн реш соот сис лин Ур-ний сущ-ет взаимно однозначное соотвествие: Каждому допуст базисн решению соответствует угловая точка. Каждый угловой точке соответствует базисное решение допустимое.
Транспортная задача
Пусть в m пунктах отправления сосредоточен однородный груз, кот надо доставить в n пунктов назначения. Известны мощности каждого поставщика и спрос каждого потребителя ( r), показатели затрат (aj) на перевозку ед груза от поставщика (i) к потребителю (j).
Открытая и закрытая модели транспортной задачи
Если EMBED Equation.3 задача закрытая
Если EMBED Equation.3 задача открытая
Любую открытую задачу сводим к закрытой путем введения фиктивного поставщика и потребителя. Mi-мощность поставщика, Nj-спрос потребителя
Mф= EMBED Equation.3
Особенности математической модели транспортной задачи
Пусть задача закрытая, напишем мат модель. Обозначим кол-во груза перевез поставщиком I к потребителю j через xij
EMBED Equation.3 достав бы min значением ф-ции f(x) и удовлетв системе ограничений
EMBED Equation.3