Преобразуем матрицу (6.12) в…
Для этого необходимо выполнить над ней такие преобразования, чтобы базисные переменные остались по одной в каждом из уравнений (строке матрицы), а коэффициенты при них были равны единице. Начинаем с коэффициента при х1 в первом уравнении. Чтобы сделать его равным единице, делим все коэффициенты первого уравнения на четыре. Для исключения переменной х, из остальных уравнений отнимаем от каждого из них первое уравнение, умноженное на такое число, при котором разность коэффициентов при Л", была бы равна нулю. Например, второе и третье уравнения (с троки) нужно умножить на нуль, четвертое — на единицу.
(6.13)
В результате преобразований получим:
(
1 0 0 1
4 0 0 4
0 2 0 0 1 0 10
0 0 1 2 6 0 76
0 3 0 -1 0 1 8
Аналогичные преобразования выполняем для переменной х2 во второй строке:
Л
1 0 0 1 0 0 4
4 1
0 1 0 0 0 5
2
0 0 1 2 6 0 76
0 0 0 -1 3 1 -7
Для переменной х3 в третьей строке и х4 — в четвертой:
1 0 0 0 3
8 1
2 1
4 9 4
0 1 0 0 0 5
0 0 1 0 3 2 62
0 0 0 1 3 -1 7
I 2 J
Выполненная процедура носит название метода полного иск-лючения (так называемое Жорданово исключение).
Теперь, приравнивая переменные х5 и х6 (соответственно пятый и шестой столбцы матрицы) нулю, можем написать значения базисных переменных, которые будут в этом случае равны свободным членам соответствующих уравнений:
х, = 62; х4 = 7.
Обращаясь к геометрической интерпретации (см. рис. 6.1), МОЖНО убедиться, ЧТО полученные координаты Х| =2j, Х2 = 5, Х5 = Хб = 0 соответствуют вершине А многоугольника ABCDEF — области допустимых планов. Это и есть первый допустимый план.
Теперь можно перейти ко второму шагу симплекс-метода — установлению того, является ли допустимый план, соответствующий найденной вершине А, оптимальным.
Наиболее естественным путем решения этой задачи был бы сплошной перебор всех вершин области допустимых планов, опре-деление для каждой из них значений переменныхх, (j = 1, 2,..., 6) и вычисление по ним в каждой вершине величины целевой функции.
Та вершина, в которой величина у оказалась бы минимальной, и даст искомый оптимальный план.
Но этот путь весьма неэкономичен, ибо требует просчитать большое количество планов, в том числе и явно неоптимальных.
Симплекс-метод предусматривает поэтому не сплошной, а направленный перебор планов, при котором каждый последующий план оказывается лучше предыдущего. Число вычислительных операций при этом резко сокращается.
В чем сущность направленного перебора?
В первом допустимом плане, соответствующем вершине А, целевая функция в соответствии с формулой (6.6) равна:
уА = -2,4Xj +0,8х2 + 22,8 = -2,4 х і +0,8 х 5 + 22,8 = 21,4.
Мы уже знаем из выражения (6.9), что >'mm = 13,2. Следовательно, целевая функция в точке А значительно больше минимума и необходимо продолжать перебор вершин-планов до тех пор, пока не придем к оптимальному.
Из вершины А можно перейти к соседним вершинам F и В (см. рис. 6.1) , двигаясь по сторонам многоугольника А Г и АВ соответственно. Видимо, нужно избрать такое направление перехода к соседней вершине, которое приведет к наибольшему уменьшению целевой функции.
Рассчитаем значения целевой функции для соседних вершин Fи В. Пользуясь формулой (6.6) и подставляя соответствующие значения х\ и Х2, получим:
yF = -2,4 х 0 + 0,8 х 5 + 22,8 = 26,8; ув = -2,4 х 4 + 0,8 х | + 22,8 = 15,33.
Сопоставляя два последних выражения, нетрудно убедиться, что минимизация функции цели достигается при движении к точке В по стороне АВ. Это означает, что в базис вводится переменная которая в вершине А была равна нулю.
Поскольку при отсутствии наглядного геометрического пред-ставления заранее нельзя располагать значениями переменных в вершинах многоугольника, то для установления необходимости и направления перебора планов пользуются специальным критерием 8/.
т
I''." '' • (6-16>
;=1
где индекс j приписывается небазисным (нулевым) переменным, а индекс і — базисным. Для получения значений коэффициента ct целевая функция уА преобразуется таким образом, чтобы исключить из нее небазисные переменные х5 и х():
уА = -2Mi + 0,8*2 + 22,8 = -0,8jq - 1,6х2 + 0,2х3 + 0,8х4 + 72.
Значения й/,- выбираются из соответствующих столбцов матрицы (6.15).
Имеется доказательство того, что в случае оптимальности полу-ченного плана все 8/ становятся равными нулю или меньше нуля. Включению в базис подлежит та переменная, для которой 8/ принимает наибольшее положительное значение. В нашем примере это:
8
L3 10'
(-0-0-2
Таким образом, мы приходим к тому же заключению о необ-ходимости включения в базис переменной для которой критерий имеет наибольшее положительное значение.
Далее необходимо установить, какая переменная должна быть выведена из базиса при введении в него переменной Чтобы ответить на этот вопрос, будем рассуждать так.
Очевидно, следует переместиться по стороне АВ как можно дальше от точки А, чтобы как можно больше уменьшить целевую функцию. Стало быть, можно взять в качестве координаты точки В ее максимальное возможное значение, допускаемое системой уравнений (6.5), соответствующей матрице (6.15), т. е. такое, при котором ни одна из переменных не становится отрицательной.
Можно показать, что это достигается в том случае, если вывести из базиса переменную, которой соответствует минимальное по-ложительное значение отношения свободного члена уравнения к коэффициенту при х5 в соответствующем столбце матрицы (6.15).
Поэтому избирается четвертая строка матрицы и соответственно переменная Jt4, подлежащая исключению из базиса.
Теперь необходимо получить в четвертой строке значение ко-эффициента при новой базисной величине равного единице, а все остальные коэффициенты этого столбца обратить в нуль. Для этого проверяем вычислительную процедуру полного исключения.
Получаем
/
1 0 0 0 0 0 4
0 1 0 0 0 - -
3 3
2 14
3 3
0 0 1 0 0 4 48
0 0 0 -1
3
Данной матрице отвечает допустимый план в вершине В. При-равнивая небазисные переменные нулю (jt4 = = 0), получаем значения остальных переменных, соответствующих второму плану:
Х1 = 4; х3 = 48;
_ 8 . _ 14
ЭСъ » ЭСг «
2 3 5 3
Как уже было показано, у в =151. Итак, получено существенное сокращение целевой функции, однако критерий 5б продолжает оставаться положительным, что говорит о необходимости дальнейшего улучшения плана:
2 3
S4 = -—; Sft = —.
4 5 6 10
На этот раз в базис вводится переменная а выводится переменная Х2, которой соответствует наименьшее значение коэффициента в столбце
