Изучение методов системного анализа
Автор: item20 • Декабрь 9, 2021 • Лабораторная работа • 1,748 Слов (7 Страниц) • 279 Просмотры
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ | |||||
Федеральное государственное бюджетное образовательное учреждение | |||||
высшего образования | |||||
«Сибирский государственный университет науки и технологий | |||||
имени академика М.Ф. Решетнева» | |||||
Институт информатики и телекоммуникаций | |||||
Кафедра «Безопасность жизнедеятельности» | |||||
ОТЧЕТ ПО ЛАБОРАТОРНЫМ РАБОТАМ | |||||
по дисциплине: | «Системный анализ» | ||||
Вариант 14. | |||||
Преподаватель: | О.А. Иконников | ||||
(подпись, дата) | (инициалы, фамилия) | ||||
Обучающийся: | |||||
(номер группы) | (подпись, дата) | (инициалы, фамилия) | |||
Красноярск 20 |
Цель работ: Целью работ является изучение методов системного анализа.
Задачи:
Решить персональные задания.
Задания:
- Решить графическим методом
f(x) = 5x1 + 3x2 max (min)
6x1 - 5x2 >= 17
x1 + 2x2 <= 34
-4x1 + 9x2 >= 17
x1, x2 >= 0
Построим область допустимых решений (ОДР), ограниченную прямыми
[pic 1]
[pic 2]
[pic 3]
[pic 4]
[pic 5]
Прямые строим по двум точкам: первую прямую – по точкам (17/6; 0) и (12; 11), вторую – по точкам (0; 17) и (34; 0), третью – по точкам (0; 17/9) и (16; 9). Четвертая и пятая прямые представляют собой оси координат. Каждое из трех неравенств задает полуплоскость, ограниченную соответствующей прямой. Чтобы установить, какая из полуплоскостей задается данным неравенством, подставляем в каждое неравенство координаты точки (0; 0):
[pic 6]
[pic 7]
[pic 8]
Таким образом, вторая полуплоскость содержит начало координат, первая и третья не содержат. ОДР представляет собой пересечение всех трех полуплоскостей.
Построим вектор, компонентами которого являются коэффициенты целевой функции:
[pic 9]
[pic 10]
Рисунок 1 – Графическое решение задачи линейного программирования
Передвигаем линию уровня f = C, перпендикулярную градиенту, в направлении градиента, т.е. в направлении возрастания функции f. Линия уровня войдет в ОДР в точке пересечения прямых
[pic 11]
Решая систему, находим:
[pic 12]
Минимальное значение функции достигается в точке (7; 5):
[pic 13]
Линия уровня выйдет из ОДР в точке пересечения прямых
[pic 14]
Решая систему, находим:
[pic 15]
Максимальное значение функции достигается в точке (16; 9):
[pic 16]
Ответ: fmin = f(7; 5) = 50; fmax = f(16; 9) = 107
2. Решить симплекс-методом
f(x) = -3x1 + 12x2 max
x1 + 4x2 <= 16
x1 - x2 >= 2
3x1 – 5x2 <= 8
x1, x2 >= 0
Запишем задачу в канонической форме, преобразовав ограничения-неравенства в ограничения-равенства, для чего введем дополнительные неотрицательные переменные x4, x5, x6.
[pic 17]
[pic 18]
[pic 19]
Запишем задачу в форме симплекс-таблицы:
Таблица 1
Базис | X1 | X2 | X3 | X4 | X5 | Свободные члены | Симплексные отношения |
X3 | 1 | 4 | 1 | 0 | 0 | 16 | 16 |
1 | -1 | 0 | -1 | 0 | 2 | 2 | |
X5 | 3 | -5 | 0 | 0 | 1 | 8 | 2,667 |
f | 3 | -12 | 0 | 0 | 0 | 0 |
Данное решение не является базисным, так как содержит только две базисные переменную (т.е. переменные, входящие только в одно из уравнений с коэффициентом 1 и отсутствующие в других уравнениях и в целевой функции). Найдем базисное решение симплекс-методом. В качестве ведущего возьмем 1-й столбец. Подсчитаем симплексные отношения свободных членов к положительным элементам ведущего столбца: 16/1 = 16 и т.д. Наименьшее симплексное отношение 2, 2-я строка – ведущая. На пересечении ведущей строки и ведущего столбца стоит ведущий элемент a21 = 1. Пересчитываем таблицу методом Жордана – Гаусса. Делим все элементы ведущей строки на ведущий элемент. Все элементы ведущего столбца, кроме ведущего элемента, равны 0. Остальные элементы пересчитываем по правилу прямоугольника. Например,
...