Решить симплекс-методом:
Z=-3x1+5x2-3x3+x4+x5+8x6→max
x1-3x2+4x3+5x4-6x5+x6=607x1-17x2+26x3+31x4-35x5+6x6=420x1, x2,x3,x4,x5,x6≥0
Идея симплекс метода заключается в том, чтобы переходить от одного базиса к другому, получая значение функции, как минимум, не хуже имеющегося. Количество всевозможных базисов конечное число, поэтому рано или поздно получим ответ.
Нужно полное решение этой работы?
Ответ
x1=x2=x3=x4=0,x5=60,x6=420
Zmax=3420.
Решение
1. Свободные члены системы должны быть неотрицательными. Данное условие выполнено.
2. Каждое ограничение системы должно представлять собой уравнение. Данное условие выполнено.
3. Нахождение начального базиса и значения функции Z, которое соответствует найденному начальному базису.
Без начального базиса невозможно начать решение. Поэтому введем искусственные переменные R1 и R2 и добавим их в те уравнения, где не было базисной переменной.
x1-3x2+4x3+5x4-6x5+x6+R1=607x1-17x2+26x3+31x4-35x5+6x6+R2=420
Решим вспомогательную задачу. Необходимо получить базис без искусственных переменных. Для этого рассмотрим функцию W и найдем ее наименьшее значение:
W=R1+R2
W=60-x1-3x2+4x3+5x4-6x5+x6+420-(7x1-17x2+26x3+31x4-35x5+6x6)
W=480-8x1+20x2-30x3-36x4+41x5-7x6
Приравниваем свободные переменные к нулю и находим значения базисных переменных и функции W:
x1=x2=x3=x4=x5=x6=0⇒
R1=60, R2=420, W=480
Поскольку требуется найти Wmin, то в третьей строке выбираем наименьший отрицательный коэффициент. Это необходимо для того, чтобы получить значение функции, как минимум, не больше имеющегося. Для положительных коэффициентов соответствующего столбца считаем отношение Θ и выбираем наименьшее значение
. Это необходимо для того, чтобы после преобразования столбец свободных членов остался положительным. Следовательно, определен элемент, который будет базисным:
Шаг 1.
x1
x2
x3
x4
x5
x6
R1
R2
Св. член Θ
1 -3 4 5 -6 1 1 0 60 60:5=12
7 -17 26 31 -35 6 0 1 420 420:31≈13,6
-8 20 -30 -36 41 -7 0 0 W-480
x1
x2
x3
x4
x5
x6
R1
R2
Св. член
1/5 -3/5 4/5 1 -6/5 1/5 1/5 0 12 Делим на 5
7 -17 26 31 -35 6 0 1 420
-8 20 -30 -36 41 -7 0 0 W-480
x1
x2
x3
x4
x5
x6
R1
R2
Св. член
1/5 -3/5 4/5 1 -6/5 1/5 1/5 0 12
4/5 8/5 6/5 0 11/5 -1/5 -31/5 1 48 Добавляем первую строку, умноженную на -31
-4/5 -8/5 -6/5 0 -11/5 1/5 36/5 0 W-48 Добавляем первую строку, умноженную на 36
Приравниваем свободные переменные к нулю и находим значения базисных переменных и функции W:
x1=x2=x3=x5=x6=R1=0⇒
x4=12, R2=48, W=48
Шаг 2.
x1
x2
x3
x4
x5
x6
R1
R2
Св. член Θ
1/5 -3/5 4/5 1 -6/5 1/5 1/5 0 12
4/5 8/5 6/5 0 11/5 -1/5 -31/5 1 48
-4/5 -8/5 -6/5 0 -11/5 1/5 36/5 0 W-48
x1
x2
x3
x4
x5
x6
R1
R2
Св. член
1/5 -3/5 4/5 1 -6/5 1/5 1/5 0 12
4/11 8/11 6/11 0 1 -1/11 -31/11 5/11 240/11 Делим на 11/5
-4/5 -8/5 -6/5 0 -11/5 1/5 36/5 0 W-48
x1
x2
x3
x4
x5
x6
R1
R2
Св