Вычеркивая нулевую третью строку, получим матрицу, в базисном виде:
В первой строке базисной является переменная x2 , а во второй – переменная x4. Переменные x1 и x3 являются свободными. Приравнивая их нулю, получаем базисное решение, соответствующее этому базису: x1 = x3 = 0, x2 =8/3,
x4 = 4/3 или Х1 = (0, 8/3, 0, 4/3). Найдем другое базисное решение, т.е. решение, в котором базисными являются другие переменные. В базис можно включить переменные x1 или x3 , которые сейчас являются свободными. Выберем, например, переменную x1 для включения в базис. Ее можно сделать базисной в первой строке, т.к. элемент а11 = 8/3 ≠ 0 (при этом из базиса выйдет переменная x2), или во второй строке а21 = -2/3 ≠ 0 (при этом из базиса выйдет х4 ). Будем делать x1 базисной, например, в первой строке, т.е. в качестве разрешающего выберем элемент а11 = 8/3 ≠ 0 (помечен в последней матрице). Как и раньше, разделив первую строку на разрешающий элемент и прибавив ко второй строке полученную первую, умноженную на 2/3, приведем матрицу к новому базису:
Полагая свободные переменные x2 и x3 равными нулю, получим новое базисное решение Х2 = (1, 0, 0, 2).
Контрольные задания для самостоятельного решения
Задание 1. Найти целочисленное базисное решение системы с заданной расширенной матрицей:
Варианты:
   1. 0 1 0 –1 -1 2. 2 2 0 1 8
-3 3 -2 4 1 3 0 3 -2 12
0 1 0 3 -1 -3 4 0 -1 2
3. 4 -3 3 2 9 4. 1 3 1 3 -2
3 3 -4 1 12 0 3 3 1 0
11 -3 2 5 30 2 9 5 7 -4
5. 1 0 1 1 3 6. 4 -3 1 1 3
0 1 3 2 6 1 1 1 -1 -3
1 0 -1 1 -3 3 1 -2 -1 -13
7. -2 2 -3 4 12 8. 0 3 4 2 10
3 -1 -1 1 -7 0 2 -3 2 1
2 -2 -3 2 0 3 4 -1 3 10
9. 0 2 0 -1 -6 10. 2 -2 3 -1 8
-3 4 4 0 -20 -1 1 1 2 6
2 -3 1 -4 7 2 4 -3 0 2
II. Решение задачи линейного программирования геометрическим методом
Общей задачей линейного программирования называется задача нахождения минимума (максимума) линейной функции
Z = c1 x1 + c2 x2 + . . .+ cn xn min (max) (1)
при ограничениях :
 a11 x1 + a12 x2 + . . .+ a1n xn (=, ) b1
a21 x1 + a22 x2 + . . .+ a2n xn (=, ) b2 (2)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
am1 x1 + am2 x2 + . . .+ amn xn (=, ) bm ,
xj 0 , j = 1, . . . , n (3)
где cj, aij, bi - заданные числа, xj - неизвестные, i = 1,…,m, j = 1,…,n и в любом из ограничений вида (2) может встречаться любой из знаков , = или .
Если число неизвестных n = 2, то задача (1) – (3) примет вид
Z = c1 x + c2 y min (max) (4)
a11 x + a12 y (=, ) b1
a21 x + a22 y (=, ) b2 (5)
. . . . . . . . . . . . . . . . . . . . . .
am1 x + am2 y (=, ) bm ,
x 0 , y 0 . (6)
и ее можно решить геометрическим методом, так как каждая пара неизвестных (х , y) может быть представлена точкой на координатной плоскости хОy.
При решении задачи (4) – (6) сначала строят так называемую допустимую область, т.е. множество точек (х , y) плоскости, координаты которых удовлетворяют всем ограничениям (5) и лежат в первой четверти координатной плоскости (ограничение (6)). Поскольку все ограничения (5) – линейные, то допустимая область будет представлять собой выпуклый многоугольник (конечный или бесконечный) или пустое множество.
Затем среди точек допустимой области находят оптимальную, т.е. такую точку М0 координаты которой (х0 , y0) доставляют минимум (максимум) целевой функции Z. Для этого по виду целевой функции (4) строят линию уровня функции Z, соответствующую Z=0, т.е. прямую L0: c1 x + c2 y = 0 и находят градиент функции Z – вектор  , который показывает направление наибыстрейшего возрастания функции ^ Вектор антиградиента (-с1, -с2) будет показывать направление наибыстрейшего убывания целевой функции Z. Вектор градиента перпендикулярен линии уровня L0 .
Перемещая линию уровня L0 параллельно самой себе в направлении градиента (с1, с2) , находим последнюю точку допустимой области, которую она пересекает при таком движении. Очевидно, что это будет точка максимума. Перемещая линию уровня в противоположном направлении (-с1, -с2) , находим точку минимума. Поясним этот метод на конкретном примере.
Геометрическим методом найти максимум и минимум функции Z для
x, y 0 при заданных ограничениях.
|
