Используя симплекс метод и, при необходимости находя начальное базисное решение решить следующую задачу линейного программирования
Z=8x1+7x2→max
При выполнении ограничений
x1-2x2≤2-x1+x2≤25x1+9x2≤45x1+x2≥1x1,x2≥0
Решение
Приведём задачу к каноническому виду, приводя ограничения типа ˝˝ к ограничениям типа ˝=˝, вводя неотрицательные остаточные переменные S1, S2, S3. Причём, +Sk, если знак в ограничении≤, и -Sk, если знак ≥. Получили:
x1-2x2+s1=2-x1+x2+s2=25x1+9x2+s3=45x1+x2-s4=1
Поскольку в последнем ограничении базисной переменной нет, то найдем базисное решение:
1-21000-11010059001011000-122451= I-IVII+IVIII-5IV =0-3100102010-104001511000-113401
Таким образом, в базисе переменные s1,s2,s3,x1. Составляем симплекс-таблицу:
Целевая функция, c
8 7 0 0 0 0
Базис Коэффициенты у целевой функции, cб
Свободные члены x1
x2
s1
s2
s3
s4
s1
0 1 0 -3 1 0 0 1
s2
0 3 0 2 0 1 0 -1
s3
0 40 0 4 0 0 1 5
x1
8 1 1 1 0 0 0 -1
Строка оценок 0 1 0 0 0 -8
Оценки (для свободных переменных) вычисляем по формуле:
∆j=icбai,j-cj
Т.е
. в нашем случае:
∆x2=0∙-3+0∙2+0∙4+8∙1-7=1
∆s4=0∙1+0∙-1+0∙5+8∙-1-0=-8
Т.к. в строке оценок есть отрицательное (в задаче на максимум) значение, то опорный план не является оптимальным. Назначаем разрешающим столбцом вектор s4 (вектор с отрицательной оценкой) и находим отношение элементов вектора свободных членов к положительным элементам разрешающего столбца:
θs1=11=1
θs3=405=8
Поскольку minθi=θs1, то разрешающей строкой назначаем строку s1. Проводим полное жорданово исключение переменной s4. В результате базисную переменную s1 заменим свободной переменной s4:
Целевая функция, c
8 7 0 0 0 0
Базис Коэффициенты у целевой функции, cб
Свободные члены x1
x2
s1
s2
s3
s4
s4
0 1 0 -3 1 0 0 1
s2
0 4 0 -1 1 1 0 0
s3
0 35 0 19 -5 0 1 0
x1
8 2 1 -2 1 0 0 0
Строка оценок 0 -23 8 0 0 0
Оценки (для свободных переменных):
∆x2=0∙-3+0∙-1+0∙19+8∙-2-7=-23
∆s1=0∙1+0∙1+0∙-5+8∙1-0=8
Т.к