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