Вариант 25. Контрольное задание по теме 3 Линейное программирование. 3

• Название: Контрольное задание по теме 3 Линейное программирование. 3
• Дата: 16.11.2018
• Размер: 1.21 Mb.
• Имя файла: Вариант 25.doc
• Тип: Документы; #56634
• страница: 11 из 13

Итерация №1.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

и из них выберем наименьшее:
Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (0.33) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x1	x2	x3	x4	x5	x6	x7	min
x2	0.33	0.33	1	0.67	-0.33	0	0	0.33	1
x5	25.33	2.33	0	1.67	-0.33	1	0	0.33	10.86
x6	23.33	0.33	0	-1.33	0.67	0	1	-0.67	70
F(X2)	0.33	-24.67	0	3.67	-0.33	0	0	0.33+M	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₂ в план 2 войдет переменная x₁

Строка, соответствующая переменной x₁ в плане 2, получена в результате деления всех элементов строки x₂ плана 1 на разрешающий элемент РЭ=0.33.

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₁ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₁ и столбец x₁ .

Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

B	x1	x2	x3
0.33 / 0.33 = 1	0.33 / 0.33 = 1	1 / 0.33 = 3	0.67 / 0.33 = 2

x4	x5	x6	x7
-0.33 / 0.33 = -1	0 / 0.33 = 0	0 / 0.33 = 0	0.33 / 0.33 = 1

После преобразований получаем новую таблицу:

Базис	В	x1	x2	x3	x4	x5	x6	x7
x1	1	1	3	2	-1	0	0	1
x5	23	0	-7	-3	2	1	0	-2
x6	23	0	-1	-2	1	0	1	-1
F(X2)	25	0	74	53	-25	0	0	25+M

Итерация №3.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее:
Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (2.5) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x1	x2	x3	x4	x5	x6	x7	min
x1	12.5	1	-0.5	0.5	0	0.5	0	0	-
x4	11.5	0	-3.5	-1.5	1	0.5	0	-1	-
x6	11.5	0	2.5	-0.5	0	-0.5	1	-0	4.6
F(X4)	312.5	0	-13.5	15.5	0	12.5	0	M	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₆ в план 4 войдет переменная x₂

Строка, соответствующая переменной x₂ в плане 4, получена в результате деления всех элементов строки x₆ плана 3 на разрешающий элемент РЭ=2.5

На месте разрешающего элемента в плане 4 получаем 1.

В остальных клетках столбца x₂ плана 4 записываем нули.

Таким образом, в новом плане 4 заполнены строка x₂ и столбец x₂ .

Все остальные элементы нового плана 4, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

B	x1	x2	x3
11.5 / 2.5 = 4.6	0 / 2.5 = 0	2.5 / 2.5 = 1	-0.5 / 2.5 = -0.2

x4	x5	x6	x7
0 / 2.5 = 0	-0.5 / 2.5 = -0.2	1 / 2.5 = 0.4	-0 / 2.5 = 0

После преобразований получаем новую таблицу:

Базис	В	x1	x2	x3	x4	x5	x6	x7
x1	14.8	1	0	0.4	0	0.4	0.2	0
x4	27.6	0	0	-2.2	1	-0.2	1.4	-1
x2	4.6	0	1	-0.2	0	-0.2	0.4	0
F(X4)	374.6	0	0	12.8	0	9.8	5.4	M

1. Проверка критерия оптимальности.

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Базис	В	x1	x2	x3	x4	x5	x6	x7
x1	14.8	1	0	0.4	0	0.4	0.2	0
x4	27.6	0	0	-2.2	1	-0.2	1.4	-1
x2	4.6	0	1	-0.2	0	-0.2	0.4	0
F(X5)	374.6	0	0	12.8	0	9.8	5.4	M

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.

Оптимальный план можно записать так:

x₁ = 14.8

x₂ = 4.6

F(X) = 25 • 14.8 + 1 • 4.6 = 374.6
В соответствии с условием задачи величина уступки . Дополнительное ограничение будет иметь вид , то есть .