задачи / Документ Microsoft Word5

Симплекс-метод. Вектор результатов X = (0, 10, 0, 8, 27)^T Значение целевой функции F(X) = -5

Решим прямую задачу линейного программирования модифицированным симплексным методом. Определим минимальное значение целевой функции F(X) = - x₁ - 4x₄ + x₅ при следующих условиях-ограничений. - 2x₂ + x₃ + 3x₄=4 x₁ + 3x₂ - 3x₄=6 x₂ - 4x₄ + x₅=5 Решение состоит из двух этапов. Первый этап - введение искусственного базиса (единичной матрицы) и поиск первого опорного плана (без учета целевой функции). Второй этап - поиск оптимального решения на основе целевой функции. Первый этап. Для нахождения начальной допустимой базы воспользуемся методом искусственного базиса. Имеем: Матрица коэффициентов A = a_ij

0	-2	1	3	0	1	0	0
1	3	0	-3	0	0	1	0
0	1	0	-4	1	0	0	1

Матрица b.

b =

4 6 5

Итерация №1. Базисные переменные: = (6, 7, 8)

B_6,7,8 =

1	0	0
0	1	0
0	0	1

Матрица c. c = (0, 0, 0, 0, 0, -1, -1, -1) c_B(6,7,8) = (-1, -1, -1) c_N(1,2,3,4,5) = (0, 0, 0, 0, 0)

N_ =

0	-2	1	3	0
1	3	0	-3	0
0	1	0	-4	1

Вычисляем: Матрицу B^-1 вычисляем через алгебраические дополнения.

B^-1 = 1/1

1	0	0
0	1	0
0	0	1

u = c_BB^-1 = (-1, -1, -1)

b^*_6,7,8 = B^-1 b =

4 6 5

Умножаем вектор u на матрицу N: uN = (-1, -2, -1, 4, -1) c^* = c_N - uN = (1, 2, 1, -4, 1) Откуда номер направляющего столбца s = 2 (индекс максимального значения из положительных элементов).

(a_12 ... a_m2) =

-2 3 1

a^* = B_-1 (a₁₂,...,a_m2)^T = (-2, 0, 0)^T min(-;6:3 = 2;5:1 = 5;) = 2 Откуда номер направляющей строки r = 2 (индекс минимального значения). Итерация №2. Базисные переменные: = (6, 2, 8)

B_6,2,8 =

1	-2	0
0	3	0
0	1	1

Матрица c. c = (1, 2, 1, -4, 1, 0, 0, 0) min(8:1 = 8;-;-;) = 8 Итерация №3. Базисные переменные: = (3, 2, 8)

B_3,2,8 =

1	-2	0
0	3	0
0	1	1

Матрица c. c = (¹/₃, 0, 1, -2, 1, 0, ^-2/₃, 0) min(-;-;3:1 = 3;) = 3 Итерация №4. Базисные переменные: = (3, 2, 5)

B_3,2,5 =

1	-2	0
0	3	0
0	1	1

Матрица c. c = (^-1/₃, 0, 0, -3, 1, -1, -1¹/₃, 0) Вектор С не содержит положительных элементов больше нуля. Первый этап симплекс-метода завершен. Второй этап. Удаляем столбцы с искусственными переменными. Заменим вектор оценок С на целевую функцию. Выразим базисные переменные: x₃ = 8+²/₃x₁+x₄ x₂ = 2+¹/₃x₁-x₄ x₅ = 3^-1/₃x₁-3x₄ которые подставим в целевую функцию: F(X) = 3^-2/₃x₁-x₄ Имеем: Матрица коэффициентов A = a_ij

A =

0	-2	1	3	0
1	3	0	-3	0
0	1	0	-4	1

Матрица b.

b =

4 6 5

Итерация №1. Базисные переменные: = (3, 2, 5)

B_3,2,5 =

1	-2	0
0	3	0
0	1	1

Матрица c. c = (²/₃, 0, 0, 1, 0) c_B(3,2,5) = (0, 0, 0) c_N(1,4) = (²/₃, 1, 0, 0, 0)

N_ =

0	3
1	-3
0	-4

Вычисляем: Матрицу B^-1 вычисляем через алгебраические дополнения.

B^-1 = 1/3

3	2	0
0	1	0
0	-1	3

u = c_BB^-1 = (0, 0, 0)

b^*_3,2,5 = B^-1 b =

8 2 3

Умножаем вектор u на матрицу N: uN = (0, 0, 0, 0, 0) c^* = c_N - uN = (²/₃, 1, 0, 0, 0) Откуда номер направляющего столбца s = 2 (индекс максимального значения из положительных элементов).

(a_12 ... a_m2) =

3 -3 -4

a^* = B_-1 (a₁₂,...,a_m2)^T = (1, 0, 0)^T min(8:1 = 8;-;-;) = 8 Откуда номер направляющей строки r = 1 (индекс минимального значения). Итерация №2. Базисные переменные: = (4, 2, 5)

B_4,2,5 =

3	-2	0
-3	3	0
-4	1	1

Матрица c. c = (²/₃, 0, 0, 1, 0) Вектор С не содержит положительных элементов больше нуля. Найдено оптимальное решение X. Вектор результатов X = (0, 10, 0, 8, 27)^T Значение целевой функции F(X) = bc = -5