Методы оптимизации в технико-экономических задачах
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
г назад и матрицу Гессе в дальнейшем не изменять.
В этом случае сходимость метода уменьшается, но и ошибка округления также снижается.
1.2 Задание
Зависимость расходов предприятия, прогнозируемых на будущий квартал от факторов x1, x2 задаётся в некоторых денежных единицах функцией
Найти значение x1 и x2, при которых прогнозируемые расходы минимальны. Использовать комбинацию одного их градиентных методов с методом Ньютона.
Фиксировать x3=0,31
1.3 Построение математической модели задачи
Задача минимизации функции от двух переменных сводится к нахождению таких значений х1* и х2*, при которых
При kv=0.739,
Найдём производную функции по переменной х1:
Найдём производную функции по переменной х2:
Найдём вторую производную функции по переменной х1:
Найдём вторую производную функции по переменной х2:
Найдём вторую производную функции по переменным х1 и х2:
Таким образом, градиент функции будет равен:
Далее необходимо определить величину шага ?k, для которого бы выполнялось неравенство: f(x(k+1))<f(x(k)).
Задача нахождения минимума функции сводится к построению последовательностей
1(k+1) = х(к) -?к * grad(f(x1(k)))
x2(k+1) = х(к) -?к * grad(f(x2(k)))
до тех пор, пока не выполнятся условия останова:
u1:
, где
:
3:
, где
4: Если условия u2 u3 выполняются, а условие u1 нет, на протяжении 10 итераций, вычисления прекратить и вывести результат.
1.4 Решение задачи
Необходимо найти величину шага. За начальную точку берём х1(0)=0 и х2(0)=0. f(х1(0); х2(0))=16,43.
1)?0(1)=1
х1(1)=-1,3388
х2(1)=0,9076
f(х1(1); х2(1))=33,59
Получили f(x(k+l)) > f(x(k)), таким образом, следует уменьшить шаг.
2)?0(2)=0,5
х1(2)=8,8788
х2(2)=-4,2155
f(х1(2); х2(2))=765,129
Получили f(x(k+l)) > f(x(k)), таким образом, следует уменьшить шаг.
3)?0(3)=0,25
х1(3)=-25,6164
х2(3)=11,1324
f(х1(3); х2(3))=5923,182
Получили f(x(k+l)) > f(x(k)), таким образом, следует уменьшить шаг.
4)?0(4)=0,125
х1(4)=23,2581
х2(4)=-9,4773
f(х1(4); х2(4))=4857,293
Получили f(x(k+l)) < f(x(k)), величина шага выбрана ?0=0,125
Метод градиентного спуска:
итерация:
х1(1)=-1,3388
х2(1)=0,9076
u1: =17.1637
Ef=8.399*10-6
Условие останова не выполняется, т.к.
u2: =1.62621
Ex=0.000808
Условие останова не выполняется, т.к.
u3: =10.818
=0.211653
Условие останова не выполняется, т.к.
2 итерация:
х1(2)=8.8788
х2(2)=-4.2156
u1: =731.5315
Ef=0.000191
Условие останова не выполняется, т.к.
u2: =11.43007
Ex=0.004914
Условие останова не выполняется, т.к.
u3: =76.5888
E=4.820012
Условие останова не выполняется, т.к.
Последняя итерация:
х1(k+1)=-0.05001334
х2(k+1)=0.1100748
u1: =1.2805*10-9
=4.08599*10-6
Условие останова выполняется, т.к.
u2: =5.8072*10-5
Ex=6.045204*10-5
Условие останова выполняется, т.к.
u3: =0.0002276
E=0.10296
Условие останова выполняется, т.к.
Все три условия останова выполняются, следовательно в точках
x*=(-0.05001334;0.1100748) функция достигает своего минимума равного
f(-0.5001334;0.1100748)=8,2853964
На этом останавливаемся и проводим последнюю итерацию методом Ньютона:
Принимаем за начальные точки, точки получившиеся в результате метода градиентного спуска, т.е.
х1(0)=-0.05001334
х2(0)=0.1100748
Подставив вычисленные вторые производные в этих точках в систему уравнений (1,3), решаем её.
14*? х1(1)-3* ? х2(1)=0,27918
* ? х1(1)+8* ? х2(1)=-0,58
Получаем
? х1(1)=0,04764
? х2(1)=-0,0707
Проверяем условия останова:
u1: =0,16797
Ef=4.14861*10-6
Условие останова выполняется, т.к.
u2: =0,08525
Ex=4,2626*10-5
Условие останова выполняется, т.к.
u3: =0,17054
E=0,10453
Условие останова выполняется, т.к.
Решение найдено. Функция
принимает свое минимальное значение 8,2853964 в точках x*=(0,04764; -0,0707)
1.5 Тестирование задачи на ЭВМ
2. Задача линейного планирования производства
.1 Теоретическая часть
Задачи линейного программирования находят широкое распространение в различных областях:
Энергетике - рациональная организация электрификации районов с помощью различных видов электростанций;
Химии - составление сложных смесей с заданным составом компонентов;
Сельском хозяйстве - рациональное распределение посевных площадей под различные культуры;
Металлургии- расчёт шихты для получения специальных легированных сталей;
Несмотря на такое многообразие, существуют способы перехода от всех частных задач к основной задаче линейного программирования. Она формулируется следующим образом.
Для переменных x1, x2, … , xn найти такие неотрицательные значения
xj?0, j=1..n
которые обращали бы в максимум целевую функцию
F=c0+> max
и удовлетворяли системе равенств
i=1..m
Симплексный метод или метод последовательного улучшения плана основан на идее перехода от одного базисного решения в вершине многоугольника допустимых решений к другому базисному решению, более близкому к оптимальному. Предполагается, что ранг системы равен числу уравнений m и меньше числа переменных n.
Если неизвестных переменных n, а ограничений m, то можно m неизвестн