Главная Численные методы при исследовании физических задач



плоскость. Ее пересечение с областью J дает выпуклый (п - т)-мерный многогранник G; наша задача состоит в том, чтобы найти минимум линейной функции (41а) в этом многограннике G.

Примером такой задачи является распределение производства однотипной продукции по разным заводам. Пусть xi - выпускаемое г-м заводом количество продукции (оно должно быть неотрицательным), - себестоимостью одного изделия на этом заводе, ад при j>m-расход сырья /-го вида и ац при 2 jm-расход заработной платы и других аналогичных показателей /-го вида при выпуске единицы продукции на данном заводе. Положим ац=\; тогда bi будет суммарным выпуском продукции по всем заводам, bj, 2 s£ / т, -полной заработной платой и аналогичными данными по всей отрасли, суммы (41 г)-расходом сырья по всем заводам, а L - себестоимостью общей продукции. Требуется, чтобы себестоимость продукции была минимальной, выпуск продукции, расход заработной платы и т. д. - заданными, а фонды сырья bj, т < /, не перерасходовались. Нас интересует, как распределить неотрицательные плановые задания Xi по заводам так, чтобы удовлетворить всем этим требованиям.

Отметим терминологию, установившуюся в экономике. Вектор х, удовлетворяющий всем дополнительным условиям, называют планом; если он, к тому же, соответствует вершине многогранника G, то опорным планом. Решение экстремальной задачи (41) называют оптимальным планом, столбцы прямоугольной матрицы А -векторами условий, а столбец Ь -вектором ограничений. В задачах экономики обычно все коэффициенты а, Ь, сО, хотя для последующего изложения это несущественно.

Многогранник условий G-выпуклый (он может быть и неограниченным). Поэтому внутри него линейная функция L{x) не может достигать минимума. Ее минимум (если он существует) достигается обязательно в какой-нибудь вершине многогранника. При вырождении он может достигаться во всех точках ребра или даже р-мерной ограничивающей плоскости (р<п -т). Поэтому теоретически задача линейного программирования проста. Достаточно вычислить значения функции в конечном числе точек- в вершинах многогранника и найти среди этих значений наименьшее.

Сложность заключается в другом. Типичное в экономике число переменных - это сотни и даже тысячи. При этом число вершин многогранника G становится астрономическим. Для того чтобы оценить это число, рассмотрим способ нахождения вершин.

Находить вершины самого многогранника G неудобно. Лучше преобразовать задачу к канонической форме, не содержащей условий третьего типа. Для этого введем в качестве новых переменных невязки условий третьего типа:

Xi = bn.m-n-Z ai+m-n.gXgO, n<iN, N = n + M-m. (42)

Доопределим коэффициенты экстремальной задачи (41) следующим образом:

С/ = 0, aji = 6j;i-N при n<i=sN, ljM. (43)



Тогда задача линейного программирования примет каноническую форму:

о, К i < Л/, (446)

2 ajiXi = bj, 1 </<М (M<Л). (44в)

Многогранник новых канонических условий образован пересечением новой (Л - М)-мерной плоскости условий с первым координатным углом. Значит, все его вершины лежат на координатных гиперплоскостях, т. е. у каждой вершины часть координат нули, а остальные координаты положительны.

Будем считать, что строки норой матрицы А линейно-независимы: в противном случае или одно условие лишнее, или система условий, несовместна. Тогда ранг этой прямоугольной матрицы равен М, и среди ее столбцов найдется по крайней мере один набор из М линейно-независимых столбцов. Все линейно-независимые наборы столбцов матрицы А соответствуют точкам пересечения плоскости условий с координатными гиперплоскостями.

Чтобы найти вершину, вфьмем один такой набор столбцов. Для удобства записи перенумеруем переменные так, чтобы первыми стояли столбцы, соответствующие этому набору (базису). Перепишем условия второго типа (44в) в следующем виде:

J]ajiXi = bj- 2 «/Л- liM. (45)

i=l ( = М + 1

Обозначим через aji, leg/, iM, элементы матрицы, обратной к базисной квадратной матрице, стоящей в левой части системы (45). Приравнивая внебазисные координаты нулю и решая эту систему, получим координаты точки пересечения плоскости условий с координатной гиперплоскостью

Xi = 0, M<i=sN.

Если найденные координаты неотрицательны, точка пересечения принадлежит первому координатному углу, т. е. является вершиной многогранника канонических условий. Если хотя бы одно Х{<СО, эту точку надо отбросить и исследовать другой набор столбцов матрицы Л. Если мы забракуем все точки, это



означает, что условия первого и второго рода образуют несовместную систему.

Различные столбцы матрицы А могут образовать См наборов. Поэтому в самом неблагоприятном случае (УИ я«. i/j-A) многогранник условий может иметь до Cn(=2 вершин. Если iVlOO, то это число настолько велико, что простой перебор вершин невозможен. Нетрудно подсчитать, что для ЭВМ типа БЭСМ-6 простой перебор посилен только при N<.\5.

4. Симплекс-метод позволяет найти решение задачи линейного программирования за гораздо меньшее число действий. Изложим идею метода.

Найдем какую-нибудь вершину многогранника и все ребра, выходящие из этой вершины. Пойдем вдоль того из ребер, по которому функция убывает. Придем в следующую вершину, найдем выходящие из нее ребра и повторим процесс. Когда мы придем в такую вершину, что вдоль всех выходящих из нее ребер функция возрастает, то минимум достигнут. Поскольку L{x) - линейная функция, а многогранник условий выпуклый, то этот процесс всегда сходится к решению задачи, причем за конечное число шагов.

При канонической форме записи многогранника условий из каждой его вершины исходит N - M ребер. Выбирая одно ребро, мы выбрасываем из рассмотрения е.- :1шны, лежащие на остальных траекториях. Следовательно, за k шагов мы рассматриваем {N - Му-ю часть вершин, проходя мимо остальных. Нам надо найти искомую вершину среди См вершин многогранника. Приравнивая число вершин С величине (Л - М)*, получим, что минимум достигается примерно за kN шагов, т. е. достаточно быстро.

Выведем формулы шага. Первую вершину находим по формуле (46). Чтобы найти ребро, надо одну из внебазисных переменных Xl сделать положительной; тогда координаты точек ребра можно выразить через нее из (45) при помощи обратной матрицы

Xi =.Xi-Xl Z aijUji, liM, Xi = Xi; (47)

остальные внебазисные координаты остаются равными нулю. Будем увеличивать Xi до тех пор, пока одна из базисных координат не обратится в нуль. Это будет при

. , м

xi= min -f- Sii = Zaija,i>0; (48)

минимум ищется только среди тех индексов i, для которых 5,7> О, ибо только эти координаты вдоль данного ребра уменьшаются и.



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 [72] 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170


0.0414