После преобразования матрицы…
6.1. Целевая функция при данном плане равна: Ус = 13,2. Итак, мы пришли анали тическим путем к тому же оптимальному плану, который был ранее получен геометрическим способом. Решение примера 6.1 можно сформулировать следующим образом. Чтобы издержки при распределении ресурсов между предприятиями были минимальными, количество предприятий первого типа должно быть равно 4, второго — 0, третьего — 16, четвертого—О, пятого — 10, шестого — 8. При этом издержки будут составлять 13,2 единицы. Важно отметить, что наихудший план распределения, соответ-ствующий точке F, приводит к потере 26,8 единиц. Таким образом, без дополнительного расходования ресурсов (только за счет их рационального распределения) улучшен результат решения задачи более чем в два раза. Рассмотренная вычислительная процедура, как было отмечено, сводится к решению системы уравнений (6.3) методом последовательного исключения неизвестных. Для такого решения в математике с успехом применяется аппарат матричной алгебры, который позволяет наиболее экономно производить требуемые вычисления. Техника решения системы уравнений (6.3) с помощью матриц заключается в следующем. (6.19) Исходную систему уравнений (6.3) можно компактно представить как матричное уравнение такого вида: АХ = S, где А, X и S — некоторые матрицы. (6.20) Матрица А содержит коэффициенты при переменных в уравнении (6.3): '4 0 0 1 0 0" 0 2 0 0 1 0 0 0 1 2 6 0 х: X = (6.21) ,4 3 0 0 0 1. Матрица X содержит переменные величины этого уравнения: Матрица S содержит свободные члены того же уравнения: '16} 10 76 24 S = (6.22) Уравнение целевой функции (6.10) в матричном виде можно представить так: У = СХ, где С — матрица, содержащая коэффициенты при переменных в уравнении (6.4). С = (0,4; 0,5; 0,2; 0,8; 0,6; 0,3). Разобьем матрицы А, X и С на подматрицы (кле тки) в соответствии с принятым базисным решением — исходным (или опорным) планом. (6.23) (6.24) Матрица А разбивается на подматрицы Ао и А^, причем Ао со-держит столбцы, соответствующие коэффициентам при переменных х5 и х(г равных нулю, а матрица As представляет собой столбцы, соответствующие коэффициентам при остальных (базисных) переменных: ^0 1 0 6 0 5 ъ 4 0 0 п 0 2 0 0 0 0 1 2 4 3 0 oj (6.25) (6.26) Х0 = Матрица X разбивается на подматрицы Хо и Xs, причем Хо содержит значение переменных, равных нулю, a Xs — значения остальных (базисных) переменных: (6.27) КЛ6 Матрица С разбивается на подматрицы Со и Cs, причем Со содержит коэффициенты в выражении для линейной формы при нулевых переменных, a Cs — для остальных (базисных) переменных: С0 = (0,6 0,3); Cs = (0,4 0,5 0,2 0,8). Проверка всех получаемых дчопустимых планов (в том числе и исходного) на оптимальность производится с помощью так называемого критериального вектора D. Критериальным называется вектор, обладающий следующим свойством: если хотя бы один из входящих в него элементов поло-жителен, то соответствующий план неоптимален; наличие в составе критериального вектора только отрицательных или равных нулю элементов говорит об оптимальности плана. Критериальный вектор расситывается по формуле D = CSR — С0; (6.31) R=A-'xA0, где As' — обратная матрица* по отношению к матрице А*. (6.29) (6.30) (6.28) X, = (V аеї х2 10 X, 76 24 Имеется доказательство, что в случае оптимальности полученного плана все элементы критериального вектора становятся равными нулю или меньше нуля (см. выше критерий 8). А:1 = Проверим наш исходный план с помощью критериального вектора. AJ находится из равенства A s A s 1 = 1: 0 3 0 1 8 1 4 0 0 0 2 -2 -3 1 2 1 3 0 -1 2 Матрица В называется обратной по отношению к квадратной матрице А, если АВ = 1 (где 1 — единичная матрица). Матрица, обратная матрице А, обозначается А-1. ( 0 3 0 1 ^0 О41 < 3 1 ] 8 1 2 4 8 1 2 4 0 0 0 X і 0 0 -2 -3 1 2 6 0 3 2 1 3 2 0 -1 У Ъ 3 < 2 -1 / 3 П 8 4 0 R=A-'A0 = 19 _ J_ 10 10 CR (6.32) 4_ _5_ _2_ _8_ 10 10 10 10 і -1 2 Г19_ - f6 - _3] - f13- _3] 10 loj 10 "10 V Поскольку jjj > 0, исходный план неоптимален. Переходим ко второму шагу. 13 Из выражения (6.32) находим наибольший коэффициент —, соответствующий переменной Х5, которая вводится в базис. Затем описанным выше путем устанавливается переменная подлежащая исключению из базиса. (6.33) где Х.-В - x5R5, 3 0 1 '16^ (Q>1 8 1 4 4 0 0 10 5 2 X = -3 1 2 76 62 3 2 0 -1 24 7 ч У Значения других переменных рассчитываются по формуле f9' 4 4 5 5 -0 = 62 62 7 7 V У ^ У Таким образом, мы получили следующие значения переменных для второго, улучшенного плана: х} = 62; х4 = 7, х5 =0; *б =о. Это уже знакомый нам первый допустимый план, которому соответствует точка А на графике рис. 6.1, и т. д. Ниже приводится ряд задач, решаемых с помощью линейного программирования, которые иллюстрируют возможности данного метода и приемы решения. Пример 6.2 Рассмотрим некую производственную ситуацию. Например, организация, занимающаяся механизацией трудоемких работ, распола
