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