СОДЕРЖАНИЕ
Задача 2 5
Задача 3 6
Задача 4 13
Задача 5 20
Задача 6 27
Задача 7 30
Задача 2
Решение:
Решение СЛАУ методом Гаусса.
Запишем систему в виде расширенной матрицы:
1
0
0
3
-3
4
0
1
0
1
2
1
0
0
1
-1
1
3
Для удобства вычислений поменяем строки местами:
0
1
0
1
2
1
0
0
1
-1
1
3
1
0
0
3
-3
4
Для удобства вычислений поменяем строки местами:
0
0
1
-1
1
3
0
1
0
1
2
1
1
0
0
3
-3
4
Теперь исходную систему можно записать как:
x3 = [3 – ( – x4 + x5)]/1
x2 = [1 – (x4 + 2x5)]/1
x1 = [4 – (3x4 – 3x5)]/1
Необходимо переменные x4,x5 принять в качестве свободных переменных и через них выразить остальные переменные.
Приравняем переменные x4,x5 к 0
Из 1-ой строки выражаем x3
Из 2-ой строки выражаем x2
Из 3-ой строки выражаем x1
Ответ: 3
Задача 3
Решение:
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 10x1 + x2 – x3 + x4 при следующих условиях-ограничений.
– x1 + x2 + x3=1
x1 + x2 + x4=5
x1 – x2 + x5=1
Введем искусственные переменные x: в 1-м равенстве вводим переменную x6; в 2-м равенстве вводим переменную x7; в 3-м равенстве переменную x5 принимаем в качестве базисной;
-1x1 + 1x2 + 1x3 + 0x4 + 0x5 + 1x6 + 0x7 = 1
1x1 + 1x2 + 0x3 + 1x4 + 0x5 + 0x6 + 1x7 = 5
1x1-1x2 + 0x3 + 0x4 + 1x5 + 0x6 + 0x7 = 1
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = 10x1+x2-1x3+x4 – Mx6 – Mx7 > max
Из уравнений выражаем искусственные переменные:
x6 = 1+x1-x2-x3
x7 = 5-x1-x2-x4
которые подставим в целевую функцию:
F(X) = 10x1 + x2-x3 + x4 – M(1+x1-x2-x3) – M(5-x1-x2-x4) > max
или
F(X) = (10)x1+(1+2M)x2+(-1+M)x3+(1+M)x4+(-6M) > max
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
-1
1
1
0
0
1
0
1
1
0
1
0
0
1
1
-1
0
0
1
0
0
Базис
B
x1
x2
x3
x4
x5
x6
x7
x6
1
-1
1
1
0
0
1
0
x7
5
1
1
0
1
0
0
1
x5
1
1
-1
0
0
1
0
0
F(X0)
-6M
-10
-1-2M
1-M
-1-M
0
0
0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi/ai2
и из них выберем наименьшее:
min (1: 1, 5: 1, – ) = 1
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис
B
x1
x2
x3
x4
x5
x6
x7
min
x6
1
-1
1
1
0
0
1
0
1
x7
5
1
1
0
1
0
0
1
5
x5
1
1
-1
0
0
1
0
0
-
F(X1)
-6M
-10
-1-2M
1-M
-1-M
0
0
0
0
Получаем новую симплекс-таблицу:
Базис
B
x1
x2
x3
x4
x5
x6
x7
x2
1
-1
1
1
0
0
1
0
x7
4
2
0
-1
1
0
-1
1
x5
2
0
0
1
0
1
1
0
F(X1)
1-4M
-11-2M
0
2+M
-1-M
0
1+2M
0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi/ai1
и из них выберем наименьшее:
min (–, 4: 2, – ) = 2
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
Базис
B
x1
x2
x3
x4
x5
x6
x7
min
x2
1
-1
1
1
0
0
1
0
-
x7
4
2
0
-1
1
0
-1
1
2
x5
2
0
0
1
0
1
1
0
-
F(X2)
1-4M
-11-2M
0
2+M
-1-M
0
1+2M
0
0
Получаем новую симплекс-таблицу:
Базис
B
x1
x2
x3
x4
x5
x6
x7
x2
3
0
1
1/2
1/2
0
1/2
1/2
x1
2
1
0
-1/2
1/2
0
-1/2
1/2
x5
2
0
0
1
0
1
1
0
F(X2)
23
0
0
-31/2
41/2
0
-41/2+M
51/2+M
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi/ai3
и из них выберем наименьшее:
min (3: 1/2, –, 2: 1 ) = 2
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис
B
x1
x2
x3
x4
x5
x6
x7
min
x2
3
0
1
1/2
1/2
0
1/2
1/2
6
x1
2
1
0
-1/2
1/2
0
-1/2
1/2
-
x5
2
0
0
1
0
1
1
0
2
F(X3)
23
0
0
-31/2
41/2
0
-41/2+M
51/2+M
0
Получаем новую симплекс-таблицу:
Базис
B
x1
x2
x3
x4
x5
x6
x7
x2
2
0
1
0
1/2
-1/2
0
1/2
x1
3
1
0
0
1/2
1/2
0
1/2
x3
2
0
0
1
0
1
1
0
F(X3)
30
0
0
0
41/2
31/2
-1+M
51/2+M
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис
B
x1
x2
x3
x4
x5
x6
x7
x2
2
0
1
0
1/2
-1/2
0
1/2
x1
3
1
0
0
1/2
1/2
0
1/2
x3
2
0
0
1
0
1
1
0
F(X4)
30
0
0
0
41/2
31