Для приведенной задачи (прямой) составить двойственную задачу. Решить прямую или двойственную задачу симплексным методом. Используя полученное решение найти решение второй из пары двойственных задач. Сравнить полученное решение с решением, найденным с помощью надстройки Excel «Поиск решения». Проанализировать отчет об устойчивости.
Решение
Приведем задачу к стандартному виду.
Из третьего равенства x3=1-0,5x1, по условию x3≥0, тогда
Zx=3x1+2x2+31-0,5x1→max&-x1-x2+22-0,5x1≤-2&-x1+2x2+1-0,5x1≤4&1-0,5x1≥0xj≥0,j=1,2⇒Zx=1,5x1+2x2+3→max&-2x1-x2≤-4&-1,5x1+2x2≤3&x1≤2xj≥0,j=1,2
Составим математическую модель двойственной задачи. Двойственной к задаче на максимум будет задача на минимум.
-2-1-1,52101,52-4323T=-2-1,51-120-4321,523.
Так как в прямой задачи все переменные неотрицательны, то в двойственной все ограничения будут "≥". Так как в прямой задачи все ограничения "≤", то в двойственной задаче y1,y2,y3≥0. Получаем экономико-математическую модель двойственной задачи:
Fy=-4y1+3y2+3y3→min&-2y1-1,5y2+y3≥1,5&-y1+2y2≥2y1≥0,y2≥0,y3≥0.
Решим прямую задачу симплекс методом, для этого приведем ее к каноническому виду:
Zx=1,5x1+2x2+3→max&-2x1-x2+u1=-4&-1,5x1+2x2+u2=3&x1+u3=2xj≥0,j=1,2
Первое базисное решение X0=0,0,-4,3,2, ZX0=3.
Первая симплекс-таблица:
Базис b x1 x2 u1 u2 u3
u1 -4 -2 -1 1 0 0
u2 3 -1,5 2 0 1 0
u3 2 1 0 0 0 1
Z 3 -1,5 -2 0 0 0
В столбце свободных членов отрицательное значение, план не допустимый
maxb<0bi=-4, есть отрицательный элементы в первой строке, т.е
. в базис переходит переменная x1 вместо u1.
Новая симплекс-таблица:
Базис b x1 x2 u1 u2 u3 θ
x1 2 1 0,5 -0,5 0 0 4
u2 6 0 2,75 -0,75 1 0 2,18
u3 0 0 -0,5 0,5 0 1
Z 6 0 -1,25 -0,75 0 0
Новый опорный план: X1=2,0,0,6,0 не допустимый, так как в строке для функции есть отрицательные значения.
В новый базис необходимо ввести переменную . Для положительных элементов разрешающего столбца рассчитываем:
.
Данное соотношение определяет разрешающую строку, т. е. ту переменную, которую необходимо вывести из базиса (в нашем случае это u2).
Новая симплекс-таблица:
Базис b x1 x2 u1 u2 u3
x1 0,909091 1 0 -0,36364 -0,18182 0
x2 2,181818 0 1 -0,27273 0,363636 0
u3 1,090909 0 0 0,363636 0,181818 1
Z 8,727273 0 0 -1,09091 0,454545 0
Новый опорный план: X2=0.91,2.18,0,0,1.09 не допустимый, так как в строке для функции есть отрицательные значения.
В новый базис необходимо ввести переменную u1