![](/user_photo/_userpic.png)
0303_Болкунов_ВО_МО_ЛР2
.docxМИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра математического обеспечения и применения ЭВМ
отчет
По лабораторной работе № 2
по дисциплине «Методы оптимизации»
Тема: Симплексный метод
Студент гр. 0303 |
|
Болкунов В. О. |
Преподаватель |
|
Мальцева Н. В. |
Санкт-Петербург
2023
Цели работы.
Решение задачи линейного программирования симплекс методом с помощью стандартной программы.
Решение задачи линейного программирования графически.
Сравнение результатов решения задачи обоими способами.
Постановка задачи.
Рассматривается следующая задача линейного программирования.
Найти минимум
линейной функции
:
где
- постоянные коэффициенты; на множестве,
заданном набором линейных ограничений:
где
- постоянные коэффициенты.
В матричной форме ограничения записываются следующим образом:
Целевая функция может быть представлена в виде скалярного
произведения:
Задание.
Вариант 15.
Целевая функция:
Ограничения:
Основные теоретические положения.
Симплексный метод позволяет решить основную задачу линейного программирования.
,
Где целевая функция
,
А допустимое
множество
A
– матрица
,
и b – вектор
задают ограничение допустимого множества
m гиперплоскостями:
Ещё n
гиперплоскостей ограничивают снизу
каждую компоненту вектора x:
Симплексный метод решения задачи линейного программирования
состоит из двух этапов:
1) поиск крайней точки допустимого множества,
2) поиск оптимальной точки путем направленного перебора крайних точек.
Крайняя точка не существует, если в таблице существует строка,
все элементы которой не положительны, а последний элемент - отрицательный.
Крайняя точка найдена, еcли все элементы вектора-столбца B
больше нуля.
Порядок нахождения крайней точки:
1) выбрать строку
i,
в которой
;
2) выбрать столбец
s,
в котором
3) в столбце s
задать номер строки r
разрешающего элемента так, чтобы
отрицательное отношение
.
4) поменять местами имена координат в таблице из строки r и столбца s;
5) рассматривая
элемент
как разрешающий, необходимо
преобразовать таблицу по формулам:
:=
;
:=
;
:=
,
;
(1)
:=
,
;
:=
,
;
:= z1;
где под z и z1 понимается соответственно первоначальное и преобразованное значение таблицы (кроме левого столбца и верхней строки).
Оптимальная точка найдена если текущая точка крайняя (все элементы вектор-столбца
) и все элементы вектор-строки
Оптимальная точка не существует, если в таблице есть столбец j, в котором
, и
.
Порядок нахождения оптимальной точки:
1) выбрать столбец
s,
в котором
;
2) в столбце s задать номер строки r разрешающего элемента так,
чтобы отрицательное
отношение
было максимальным;
3) поменять местами имена координат в таблице из строки r и столбца s;
4) рассматривая элемент как разрешающий, необходимо
преобразовать таблицу по формулам (1).
Координаты оптимальной точки определяются следующим образом:
1) если
находится на i-м
месте левого столбца, то его значение
равно
;
2) если
находится на j-м
месте верхней строки, то его значение
равно 0.
Выполнение работы.
Начальные условия задачи (вариант 15) представлены на рисунке 1.
Рисунок 1: начальные условия задачи
Что соответствует следующему формальному определению:
Приведём задачу к матричному виду:
Построим графики каждой из ограничивающих прямой (рисунки 2-5 соответственно)
Рисунок 2: y1
Рисунок 3: y2
Рисунок 4: y3
Рисунок 5: y4
Изобразим все прямые на одном графике (рис. 6)
Рисунок 6: ограничивающие прямые
Можно
заметить, что в первой четверти (где
)
области образованные данными прямыми
не пересекаются, это особенно заметно,
если отдельно изобразить области,
соответствующие ограничениям
(рис. 7)
Рисунок 7: y1 и y2
На данном графике чётко видно, что области ограничения не имеют общих точек в первой четверти координатной плоскости, следовательно в независимости от наложения дополнительных ограничений, допустимое множество задачи минимизации будет пусто.
Рассмотрим
работу программы. На первом шаге (рис.8)
алгоритм находится в точке
,
– точка не крайняя и
– следовательно можно сделать шаг
алгоритма.
Рисунок 8: 1-ый шаг алгоритма
Найдём
,
им будет являться
, следовательно разрешающий элемент
находится в 3 строке и 1 столбце.
На следующем шаге программы (рис. 9) в первой строке все элементы отрицательные, следовательно допустимое множество пусто и решения не существует.
Рисунок 9: 2-ой шаг алгоритма
Решение, полученное с помощью программы совпадает с графическим.
Вывод.
В ходе выполнения лабораторной работы был изучен метод решения основной задачи линейного программирования: симплексный метод. С помощью подготовленной программы, решающей задачу минимизации данным методом, была решена задача минимизации в соответствии с вариантом. Задача минимизации была также решена графически, графическое решение и решение программы алгоритмом симплексного метода полностью совпадают.