Контрольная работа на тему КОНТРОЛЬНАЯ РАБОТА 150411-01

СОДЕРЖАНИЕ


Задача 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