Преобразовать задачу линейного программирования из канонической формы в стандартную форму. Графическим методом найти значения неизвестных, при которых целевая функция принимает наибольшее и наименьшее значения.
z=-x1+2x2-x3+3x4
2x1-x2+3x3-x4=5,x1+2x2-x3+2x4=0,
xi≥0, i=1, 2, 3, 4.
Ответ
zmax=1 при x1=0, x2=0, x3=2, x4=1.
zmin=-2 при x1=1, x2=0, x3=0, x4=1.
Решение
Запишем соотношение, определяющее функцию цели Z, в виде уравнения и добавим его к системе ограничений
z+x1-2x2+x3-3x4=0,2x1-x2+3x3-x4=5,x1+2x2-x3+2x4=0,
Заполним симплексную.
z
x1
x2
x3
x4
b
1
1 -2 1 -3 0 Нулевая строка
0
2 -1 3 -1 5 Первая строка
0
1 2 -1 2 0 Вторая строка
Будем выполнять линейные преобразования Жордана-Гаусса такие, чтобы в преобразованной таблице были единичные столбцы, например, в столбце x3 будет один элемент, равный единице, а остальные элементы равны нулю, для этого выполним над строками преобразования
0+II→0
I+3II→I
В результате получаем:
z
x1
x2
x3
x4
b
1 2 0 0 -1 0 Нулевая строка
0 5 5 0 5 5 Первая строка
0 1 2 -1 2 0 Вторая строка
На втором шаге разделим первую строку на 5, а вторую умножим на -1.
z
x1
x2
x3
x4
b
1 2 0 0 -1 0 Нулевая строка
0 1 1 0 1 1 Первая строка
0 -1 -2 1 -2 0 Вторая строка
На третьем шаге выполним преобразования, чтобы столбец для x4 стал единичным:
0+I→0
II+2I→II
В результате получаем:
z
x1
x2
x3
x4
b
1 3 1 0 0 1 Нулевая строка
0 1 1 0 1 1 Первая строка
0 1 0 1 0 2 Вторая строка
Переменные x3 и x4 называются базисными, а переменные x1, x2 – свободными
. Последней таблице соответствуют задачи
z=-3x1-x2+1 max, min
x1+x2+x4=1,x1+x3=2, xi≥0, i=1, 2, 3, 4.
Отсюда получим
z=-3x1-x2+1 max, min
x4=1-x1-x2,x3=2-x1,
xi≥0, i=1, 2, 3, 4.
Поскольку переменные x4, x3 могут по условию принимать только неотрицательные значения, то уравнение-равенство можно записать в виде неравенств:
z=-3x1-x2+1 max, min
1-x1-x2≥0,2-x1≥0, x1≥0, x2≥0 .
В результате получим задачу линейного программирования в стандартной форме, в которой остались две переменные
z=-3x1-x2+1 max, min
x1+x2≤1,x1≤2, x1≥0, x2≥0 .
Решим задачу графическим методом.
В прямоугольной декартовой системе координат строим прямую x1+x2=1, соответствующую первому ограничению и выделяем полуплоскость над прямой, точки которой являются решением неравенства x1+x2≤1.
Построим теперь прямую x1=2, соответствующую второму ограничению и выделим полуплоскость под прямой, точки которой удовлетворяют неравенству x1≤2.
Находим теперь общую часть полуплоскостей решений, учитывая условия неотрицательности переменных x1, x2 (находим область допустимых значений).
Областью допустимых решений (ОДР) является закрашенная область, представленная треугольником ABC.
Найдем в этой области оптимальное решение
Задать вопрос
на новый заказ в Автор24.
