ГУАП
КАФЕДРА № 41
ОТЧЕТ
ЗАЩИЩЕН С ОЦЕНКОЙ
ПРЕПОДАВАТЕЛЬ
старший преподаватель |
|
|
|
Е.П. Виноградова |
должность, уч. степень, звание |
|
подпись, дата |
|
инициалы, фамилия |
ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ №5 |
Симплекс-метод |
по курсу: Прикладные методы оптимизации |
|
|
РАБОТУ ВЫПОЛНИЛА
СТУДЕНТКА ГР. |
4716 |
|
|
|
С.А. Янышева |
|
|
|
подпись, дата |
|
инициалы, фамилия |
Санкт-Петербург
2020
Лабораторная работа № 5 Симплекс-метод
Цель работы
Симплексный метод применяется при решении задач линейного программирования, заданных в канонической форме. Приобрести практические навыки решения задач линейного программирования симплекс методом.
Вариант задания
Вариант 3
Ход выполнения работы
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≥) вводим базисную переменную x4 со знаком минус. В 2-м неравенстве смысла (≥) вводим базисную переменную x5 со знаком минус. В 3-м неравенстве смысла (≥) вводим базисную переменную x6 со знаком минус. В 4-м неравенстве смысла (≥) вводим базисную переменную x7 со знаком минус. В 5-м неравенстве смысла (≥) вводим базисную переменную x8 со знаком минус.
x1+2x2-x4 = 10
2x1+x2+x3-x5 = 10
x2+x3-x6 = 4
x1-x7 = 0
x2-x8 = 0
Расширенная матрица системы ограничений-равенств данной задачи:
-
1
2
0
-1
0
0
0
0
10
2
1
1
0
-1
0
0
0
10
0
1
1
0
0
-1
0
0
4
1
0
0
0
0
0
-1
0
0
0
1
0
0
0
0
0
-1
0
Приведем систему к единичной матрице методом жордановских преобразований.
В качестве базовой переменной можно выбрать x4.
Получаем новую матрицу:
-
-1
-2
0
1
0
0
0
0
-10
2
1
1
0
-1
0
0
0
10
0
1
1
0
0
-1
0
0
4
1
0
0
0
0
0
-1
0
0
0
1
0
0
0
0
0
-1
0
В качестве базовой переменной можно выбрать x5.
Получаем новую матрицу:
-
-1
-2
0
1
0
0
0
0
-10
-2
-1
-1
0
1
0
0
0
-10
0
1
1
0
0
-1
0
0
4
1
0
0
0
0
0
-1
0
0
0
1
0
0
0
0
0
-1
0
В качестве базовой переменной можно выбрать x6.
Получаем новую матрицу:
-
-1
-2
0
1
0
0
0
0
-10
-2
-1
-1
0
1
0
0
0
-10
0
-1
-1
0
0
1
0
0
-4
1
0
0
0
0
0
-1
0
0
0
1
0
0
0
0
0
-1
0
В качестве базовой переменной можно выбрать x7.
Получаем новую матрицу:
-
-1
-2
0
1
0
0
0
0
-10
-2
-1
-1
0
1
0
0
0
-10
0
-1
-1
0
0
1
0
0
-4
-1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
-1
0
В качестве базовой переменной можно выбрать x8.
Получаем новую матрицу:
-
-1
-2
0
1
0
0
0
0
-10
-2
-1
-1
0
1
0
0
0
-10
0
-1
-1
0
0
1
0
0
-4
-1
0
0
0
0
0
1
0
0
0
-1
0
0
0
0
0
1
0
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,5,6,7,8).
Выразим базисные переменные через остальные:
x4 = x1+2x2-10
x5 = 2x1+x2+x3-10
x6 = x2+x3-4
x7 = x1
x8 = x2
Подставим их в целевую функцию:
F(X) = 2x1+3x2-x3
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x4 следует ввести переменную x2.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
-
Базис
B
x1
x2
x3
x4
x5
x6
x7
x8
x2
5
1/2
1
0
-1/2
0
0
0
0
x5
-5
-3/2
0
-1
-1/2
1
0
0
0
x6
1
1/2
0
-1
-1/2
0
1
0
0
x7
0
-1
0
0
0
0
0
1
0
x8
5
1/2
0
0
-1/2
0
0
0
1
F(X0)
-15
1/2
0
-1
3/2
0
0
0
0
Представим расчет каждого элемента в виде таблицы:
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
-10 : -2 |
-1 : -2 |
-2 : -2 |
0 : -2 |
1 : -2 |
0 : -2 |
0 : -2 |
0 : -2 |
0 : -2 |
-10-(-10 • -1):-2 |
-2-(-1 • -1):-2 |
-1-(-2 • -1):-2 |
-1-(0 • -1):-2 |
0-(1 • -1):-2 |
1-(0 • -1):-2 |
0-(0 • -1):-2 |
0-(0 • -1):-2 |
0-(0 • -1):-2 |
-4-(-10 • -1):-2 |
0-(-1 • -1):-2 |
-1-(-2 • -1):-2 |
-1-(0 • -1):-2 |
0-(1 • -1):-2 |
0-(0 • -1):-2 |
1-(0 • -1):-2 |
0-(0 • -1):-2 |
0-(0 • -1):-2 |
0-(-10 • 0):-2 |
-1-(-1 • 0):-2 |
0-(-2 • 0):-2 |
0-(0 • 0):-2 |
0-(1 • 0):-2 |
0-(0 • 0):-2 |
0-(0 • 0):-2 |
1-(0 • 0):-2 |
0-(0 • 0):-2 |
0-(-10 • -1):-2 |
0-(-1 • -1):-2 |
-1-(-2 • -1):-2 |
0-(0 • -1):-2 |
0-(1 • -1):-2 |
0-(0 • -1):-2 |
0-(0 • -1):-2 |
0-(0 • -1):-2 |
1-(0 • -1):-2 |
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x5 следует ввести переменную x4.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x2 |
10 |
2 |
1 |
1 |
0 |
-1 |
0 |
0 |
0 |
x4 |
10 |
3 |
0 |
2 |
1 |
-2 |
0 |
0 |
0 |
x6 |
6 |
2 |
0 |
0 |
0 |
-1 |
1 |
0 |
0 |
x7 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
x8 |
10 |
2 |
0 |
1 |
0 |
-1 |
0 |
0 |
1 |
F(X1) |
-30 |
-4 |
0 |
-4 |
0 |
3 |
0 |
0 |
0 |
Представим расчет каждого элемента в виде таблицы:
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
5-(-5 • -1/2):-1/2 |
1/2-(-11/2 • -1/2):-1/2 |
1-(0 • -1/2):-1/2 |
0-(-1 • -1/2):-1/2 |
-1/2-(-1/2 • -1/2):-1/2 |
0-(1 • -1/2):-1/2 |
0-(0 • -1/2):-1/2 |
0-(0 • -1/2):-1/2 |
0-(0 • -1/2):-1/2 |
-5 : -1/2 |
-11/2 : -1/2 |
0 : -1/2 |
-1 : -1/2 |
-1/2 : -1/2 |
1 : -1/2 |
0 : -1/2 |
0 : -1/2 |
0 : -1/2 |
1-(-5 • -1/2):-1/2 |
1/2-(-11/2 • -1/2):-1/2 |
0-(0 • -1/2):-1/2 |
-1-(-1 • -1/2):-1/2 |
-1/2-(-1/2 • -1/2):-1/2 |
0-(1 • -1/2):-1/2 |
1-(0 • -1/2):-1/2 |
0-(0 • -1/2):-1/2 |
0-(0 • -1/2):-1/2 |
0-(-5 • 0):-1/2 |
-1-(-11/2 • 0):-1/2 |
0-(0 • 0):-1/2 |
0-(-1 • 0):-1/2 |
0-(-1/2 • 0):-1/2 |
0-(1 • 0):-1/2 |
0-(0 • 0):-1/2 |
1-(0 • 0):-1/2 |
0-(0 • 0):-1/2 |
5-(-5 • -1/2):-1/2 |
1/2-(-11/2 • -1/2):-1/2 |
0-(0 • -1/2):-1/2 |
0-(-1 • -1/2):-1/2 |
-1/2-(-1/2 • -1/2):-1/2 |
0-(1 • -1/2):-1/2 |
0-(0 • -1/2):-1/2 |
0-(0 • -1/2):-1/2 |
1-(0 • -1/2):-1/2 |
Выразим базисные переменные через остальные:
x2 = -2x1-x3+x5+10
x4 = -3x1-2x3+2x5+10
x6 = -2x1+x5+6
x7 = x1
x8 = -2x1-x3+x5+10
Подставим их в целевую функцию:
F(X) = 2x1+3(-2x1-x3+x5+10)-x3
Или
F(X) = -4x1-4x3+3x5+30
2x1+x2+x3-x5=10
3x1+2x3+x4-2x5=10
2x1-x5+x6=6
-x1+x7=0
2x1+x3-x5+x8=10
При вычислениях значение Fc = 30 временно не учитываем.
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
-
2
1
1
0
-1
0
0
0
3
0
2
1
-2
0
0
0
2
0
0
0
-1
1
0
0
-1
0
0
0
0
0
1
0
2
0
1
0
-1
0
0
1
Базисные переменные - это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x2, x4, x6, x7, x8. Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,10,0,10,0,6,0,10)
Базисное решение называется допустимым, если оно неотрицательно.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x2 |
10 |
2 |
1 |
1 |
0 |
-1 |
0 |
0 |
0 |
x4 |
10 |
3 |
0 |
2 |
1 |
-2 |
0 |
0 |
0 |
x6 |
6 |
2 |
0 |
0 |
0 |
-1 |
1 |
0 |
0 |
x7 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
x8 |
10 |
2 |
0 |
1 |
0 |
-1 |
0 |
0 |
1 |
F(X0) |
0 |
4 |
0 |
4 |
0 |
-3 |
0 |
0 |
0 |
Переходим к основному алгоритму симплекс-метода.
Окончательный вариант симплекс-таблицы:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x2 |
10 |
2 |
1 |
1 |
0 |
-1 |
0 |
0 |
0 |
x4 |
10 |
3 |
0 |
2 |
1 |
-2 |
0 |
0 |
0 |
x6 |
6 |
2 |
0 |
0 |
0 |
-1 |
1 |
0 |
0 |
x7 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
x8 |
10 |
2 |
0 |
1 |
0 |
-1 |
0 |
0 |
1 |
F(X1) |
0 |
4 |
0 |
4 |
0 |
-3 |
0 |
0 |
0 |
Последняя строка содержит отрицательные элементы. Пространство допустимых решений неограниченно. Решения не существует.
Выводы
При выполнении лабораторной работы был изучен Симплекс-метод. Было выяснено, что симплексный метод применяется при решении задач линейного программирования, заданных в канонической форме. Были приобретены практические навыки решения задач линейного программирования симплекс методом.