Задача 1.
Решить задачу линейного программирования симплексным методом.
Вариант 2.
Найти наибольшее значение функции f(X) = x1 – 4x4 при ограничениях
x1 – x2 + x3 + x4 = 3
x1 + x2 + 2x3 = 5,
xj ³ 0, j = 1, 2, 3, 4.
Решение.
Задача записана в каноническом виде, но не имеет необходимого числа единичных столбцов, т. е. не обладает очевидным начальным опорным решением.
Для нахождения опорного плана переходим к М-задаче:
f(X) = x1 – 4x4 – Мy1 ® max
x1 – x2 + x3 + x4 = 3
x1 + x2 + 2x3 + y1 = 5,
xj ³ 0, j = 1, 2, 3, 4; y1³ 0.
Очевидное начальное опорное решение (0; 0; 0; 3; 5).
Решение осуществляется симплекс-методом с искусственным базисом.
Расчеты оформим в симплекс-таблицах
Номер симплекс-таблицы Базис
Cj
Ci
B 1 0 0 -4 -M Q
A1
A2
A3
A4
P1
0
A4
-4 3 1 -1 1 1 0 3:1 = 3
P1
-M 5 1 1 2 0 1 5:2 = 2,5
j
- -5M-12 -M-5 -M+4 -2M-4 0 0 1
A4
-4 1/2 1/2 -3/2 0 1 1/2:1/2=1
A3
0 5/2 1/2 1/2 1 0 5/2:1/2=1
j
- -2 -3 6 0 0 2
A1
1 1 1 -3 0 2
A3
0 2 0 2 1 -1 2:2=1
j
- 1 0 -3 0 6 3
A1
1 4 1 0 3/2 1/2
A2
0 1 0 1 1/2 -1/2
j
- 4 0 0 3/2 9/2
Начальное опорное решение (0; 0; 0; 3; 5), соответствующее симплекс-таблице 0, неоптимальное, так как в D - строке есть отрицательные значения, наименьшее в столбце А3. Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке P1, эта строка направляющая. Направляющий элемент на пересечении направляющих строки и столбца. Столбец P1 выводим из базиса, а А3 - вводим в базис.
При пересчете таблицы столбец Р1 далее можно не рассчитывать.
После пересчета получаем симплекс-таблицу 1. Соответствующее опорное решение (0; 0; 5/2; 1/2; 0) не оптимально, так как в D - строке есть отрицательные значения, в столбце А1.Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А4. В качестве направляющей строки возьмем А4. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А4 выводим из базиса, а А1 - вводим в базис.
После пересчета получаем симплекс-таблицу 2. Опорное решение, соответствующее симплекс-таблице 2 (1; 0; 2; 0; 0) – не оптимально, так как в D - строке есть отрицательные значения, в столбце А2. Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А3. В качестве направляющей строки возьмем А3. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А3 выводим из базиса, а А2 - вводим в базис.
После пересчета получаем симплекс-таблицу 3. Опорное решение, соответствующее симплекс-таблице 3 (4; 1; 0; 0; 0) – оптимально, так как в D - строке нет отрицательных значений.
Отбрасывая значения переменной y1, получаем оптимальное решение исходной задачи:
х1 = 4, х2 = 1; х3 = 0; х4 = 0; fmax = 1×4 + 0×1 + 0×0 – 4×0 = 4.
Задача 2.
Задание 1. Сформулировать экономико-математическую модель исходной экономической задачи.
Задание 2. Решить полученную задачу линейного программирования графическим методом.
Задание 3. ............
