Введение
В наше время всё человечество находиться на такой стадии развития, что дальнейший прогресс связан с огромными затратами ресурсов. Не каждая страна или крупная корпорация может позволить себе вести исследования в передовых областях науки. Примером таких исследований служит освоение космоса, создание реактора ядерного синтеза и изучение короткоживущих элементарных частиц. Очевидно, что ошибка в проекте может привести к провалу всего начинания. Ресурсы, затраченные на проект, также не являются бесконечными. В такой обстановке большое влияние на успех всего оказывают процессы моделирования и оптимизации. Теории, позволяющей оптимизировать любое выражение, не существует, однако, для определённых видов выражений построен математический аппарат, позволяющий найти оптимум.
В данной курсовой работе приведены примеры решения фундаментальных задач оптимизации наиболее распространенными методами.
1. Линейное программирование
1.1 Решение задачи 1.1
Максимизировать целевую функцию:
Y=-x1+9x2-3x3 → max
При ограничениях:
-x1-2x2-x3 ≥ -5
-x1+x2-2x3 ≤ -5
x1+2x2+x3 ≤ 7
x1,2,3,4 ≥ 0
Нужно привести систему ограничений к каноническому виду. Для этого следует добавить дополнительные переменные x4, x5, x6.
x1+2x2+x3 +x4+0x5+0x6=5
x1-x2+2x3 +0x4-x5+0x6=5
x1+2x2+x3 +0x4+0x5+1x6=7
Выразим допустимый базис в форме Таккера:
X4=5-( x1+2x2+x3)
X5=-5-(-x1+x2-2x3)
X6=7-( x1+2x2+x3)
Целевая функция в форме Таккера:
Y=0-(1x1-9x2+3x3)
На основании целевой функции и полученных ограничений можно составить симплекс-таблицу (Таблица 1.1).
Таблица 1.1
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
|
X4 |
5 |
1 |
2 |
1 |
1 |
0 |
0 |
|
X5 |
-5 |
-1 |
1 |
-2 |
0 |
1 |
0 |
|
X6 |
7 |
1 |
2 |
1 |
0 |
0 |
1 |
|
Y |
0 |
1 |
-9 |
3 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X5. Результат отображен в таблице 1.2.
Таблица 1.2
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
|
X4 |
0 |
0 |
3 |
-1 |
1 |
1 |
0 |
|
X1 |
5 |
1 |
-1 |
2 |
0 |
-1 |
0 |
|
X6 |
2 |
0 |
3 |
-1 |
0 |
1 |
1 |
|
Y |
-5 |
0 |
-8 |
1 |
0 |
1 |
0 |
Используем обычный симплекс-метод. Вводим в базис X2, выводим из базиса X4. Результат отображен в таблице 1.3.
Таблица 1.3
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
|
X2 |
0 |
0 |
1 |
-1/3 |
1/3 |
1/3 |
0 |
|
X1 |
5 |
1 |
0 |
5/3 |
1/3 |
-2/3 |
0 |
|
X6 |
2 |
0 |
0 |
0 |
-1 |
0 |
1 |
|
Y |
-5 |
0 |
0 |
-5/3 |
8/3 |
11/3 |
0 |
Используем обычный симплекс-метод. Вводим в базис X3, выводим из базиса X1. Результат отображен в таблице 1.4.
Таблица 1.4
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
|
X2 |
1 |
1/5 |
1 |
0 |
2/5 |
1/5 |
0 |
|
X3 |
3 |
3/5 |
0 |
1 |
1/5 |
-2/5 |
0 |
|
X6 |
2 |
0 |
0 |
0 |
-1 |
0 |
1 |
|
Y |
0 |
1 |
0 |
0 |
3 |
3 |
0 |
В столбце свободных членов и в строке коэффициентов отсутствуют отрицательные элементы, а следовательно, полученный план оптимален. Произведём проверку, подставив полученные значения для переменных в начальные условия и убедившись в их верности, выписываем ответ.
Ответ : Решения оптимально
Y=0
X=(0;1;3;0;0;2)
Количество итераций=3