Файл: Баженов, Ю. М. Перспективы применения математических методов в технологии сборного железобетона.pdf

нужно выпустить, чтобы обеспечить возведение максимального ко­ личества сооружений.

На изготовление арматурных каркасов может быть затрачено 11 чел.-дней. Соответственно за это время может быть произведено 200 м3 бетона, а па изготовление конструкций может быть затрачено 210 чел.-дней (включая вспомогательные работы), для прогрева из­ делий может быть использовано 22 г пара.

удовлетворяет еще и условие (Ѵ.5), то он будет оптимальным пла­ ном задачи.

Для нахождения оптимального плана симплексным методом си­ стема неравенств (Ѵ.7) преобразуется в систему линейных уравне­ ний путем введения дополнительных неизвестных. Обозначим их *5, *6- *7. *8 и назовем дополнительными переменными. Каждая допол­

нительная переменная входит в соответствующее уравнение с ко­ эффициентом, равным единице, а в уравнение целевой функции — с нулевым коэффициентом.

Запишем полученные уравнения, поменяв местами правые и ле­ вые части и для удобства дальнейших вычислений умножив каждый

Решение задачи состоит из следующих этапов: составление исходной симплексной таблицы; проверка плана на оптимальность;

последовательное улучшение плана путем пересчета симп­ лексной таблицы.

На приведенной ниже схеме показаны основные элементы симплексной таблицы.

В верхней части таблицы записываются все неизвестные, вхо-

166

дящне в математическую модель задачи: вначале располагаются ос­ новные неизвестные, а затем дополнительные. Над неизвестными за­ писываются значения коэффициентов эффективности при соответст­ вующих неизвестных.

В центре симплексной таблицы располагается матрица коэффи­ циентов при неизвестных, в которой число столбцов равно числу всех

ся основная часть матрицы, справа — единичная матрица, состав­ ленная коэффициентами при дополнительных переменных.

Внизу таблицы располагается целевая строка, служащая для определения оптимальности плана на каждом этапе вычислений. Элементы этой строки показывают для каждого вектора Xj, насколь­ ко увеличится значение функционала L цели при включении в план

данного вектора.

Столбец Я Л>— содержит неизвестные, входящие в план на дан­ ной итерации к. Число компонентов вектора Pw должно быть давно числу уравнений ограничений т. Входящие в план векторы должны

В исходной таблице в столбец PW записывают дополнительные

неизвестные. Эти неизвестные независимы, они обозначают фиктив­ ную продукцию, другими словами, решение по симплексному спосо­

бу начинается с момента, когда ничего не производится, т. е. lS°}= 0.

Затем с помощью последовательных этапов решения (итераций) оп­ ределяют нужный объем производства каждого продукта при за­ данной целевой функции и положенных ограничениях.

В столбце С) записываются коэффициенты при неизвестных, вхо­

167

дящих в план. В исходной таблице здесь записываются коэффициен­ ты при дополнительных неизвестных, т. е. 0.

В столбец Л'о записываются свободные члены уравнений ограни­ чении. В конце процесса вычислении в столбце Я(Л) будут записаны неизвестные оптимального плана, в столбце х0— значение этих пе­

ременных, т. е. итог решения, а в /+ > — максимальное (минималь­ ное) значение функции цели.

Последние два столбца таблицы (а и ß) имеют вспомогатель­ ное значение. Заполнение их удобно для выполнения проверки хода

Значение L<°> и элементов целевой строки вычисляется следую­ щим образом:

+ 0 -28)—1 = —1.

168

На основе сказанного можно установить правила, позволяющие формально производить заполнение симплексной таблицы:

ний ограничений; в) элементы целевой строки в столбцах основных переменных

равны коэффициентам эффективности при этих переменных, взятых

В других случаях необходимо провести улучшение плана, в частно­ сти после составления исходной таблицы.

Улучшение плана производится введением в план (столбец Я(*>) вектора той неизвестной, которая может больше, чем другие, увели­ чить (уменьшить) значение целевой функции задачи. А так как в плане может быть лишь т неизвестных, то из плана нужно ис­

ключить ту неизвестную, которая вносит меньший вклад в функцию цели. Таким образом, на каждой итерации в план вводится одна неизвестная и одна исключается из него.

Алгоритм симплексного метода определяет формальные прави­ ла выбора вектора, который необходимо ввести в план, н вектора,

ментов целевой строки выбирается наибольшее отрицательное чис­ ло (за исключением столбца х0). Этот вектор подлежит вводу в план. Столбец называется направляющим, обозначим его индек­ сом к.

В нашем примере можно вводить любой из векторов *і, х2, х3 или х4, так как коэффициенты у них одинаковые. Введем вектор Х \ . Столбец х х— направляющий. Этот столбец в табл. Ѵ.2 обведен жир­

ной линией.

2. Определяем вектор, подлежащий исключению нз плана:

xik

нов уравнений к соответствующим коэффициентам направляющего столбца. Значения этих отношений записываем в столбец а табл. Ѵ.2.

Минимальное из этих отношений определяет исключаемый нз плана вектор. Выбранная строка называется направляющей строкой и обо­

*4о __ 2200 = 78

*4і 28

Выбираем минимальное из этих отношений, т. е. 44.

169