задачи / 9

Симплекс-метод. Copyright © Semestr.RU

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

-4	1	-4	0	0	1	0	0
3	3	0	0	-1	0	1	0
-10	1	-3	1	0	0	0	1

Матрица b.

b =

4 5 4

Итерация №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_ =

-4	1	-4	0	0
3	3	0	0	-1
-10	1	-3	1	0

Вычисляем: Матрицу 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 5 4

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

(a_12 ... a_m2) =

1 3 1

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

B_6,2,8 =

1	1	0
0	3	0
0	1	1

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

B_6,2,4 =

1	1	0
0	3	0
0	1	1

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

B_5,2,4 =

0	1	0
-1	3	0
0	1	1

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

A =

-4	1	-4	0	0
3	3	0	0	-1
-10	1	-3	1	0

Матрица b.

b =

4 5 4

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

B_5,2,4 =

0	1	0
-1	3	0
0	1	1

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

N_ =

-4	-4
3	0
-10	-3

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

B^-1 = 1/1

3	-1	0
1	0	0
-1	0	1

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

b^*_5,2,4 = B^-1 b =

7 4 0

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

(a_12 ... a_m2) =

-4 0 -3

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

B_5,2,3 =

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

Матрица c. c = (0, 0, -6, 0, 0) min(-;-;-;) = 0 Выводимую переменную r найти невозможно. Прерываем процесс поиска первого опорного плана. Вектор результатов X = (0, 4, 0, 0)^T Значение целевой функции F(X) = bc = 4