Математические модели некоторых задач в строительстве

Роль технико-экономических расчетов для анализа и прогнозирования деятельности, планирования и управления строительными системами значительна, причем узловыми среди них являются вопросы выбора оптимизации решений. При этом решение представляет собой выбор параметров, характеризующих организацию определенного мероприятия, причем выбор почти полностью зависит от лица, принимающего решение [13].

Решения могут быть удачными или неудачными, обоснованными и неразумными. Практику, как правило, интересуют решения оптимальные, такие, которые являются по тем или иным причинам предпочтительнее, чем другие.

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

Сооружение любого строительного объекта происходит путем выполнения в определенной последовательности большого количества разноплановых работ.

Рассмотрим несколько характерных задач и получим для них математическую формулировку (математическую модель).

Задача 1 (Транспортная задача.)

В городе имеется 2 бетонных завода. Первый выпускает вдень 400 т бетона, а второй - 560 т. Бетон с этих заводов отправляется на 4 стройплощадки. На первую стройплощадку поступает в день 220 т бетона, на вторую - 200 т, на третью - 180 т, на четвертую - 360 т. Стоимость перевозки одной тонны бетона с каждого завода на каждую стройплощадку известна. Требуется так организовать перевозку бетона с заводов на стройплощадки, чтобы суммарная стоимость всех перевозок была минимальной.

От содержательной постановки задачи перейдем к математической. Если обозначить через С_ij - стоимость перевозки одной тонны бетона с i - го завода на j- ю стройплощадку (это известные величины), а через х_ij - количество тонн бетона, которое нужно перевести с i - го завода на j -ю стройплощадку (это искомые величины), то стоимость всех перевозок будет выражаться функцией

(5.1)

Необходимо найти минимум этой функции, но х_ij не независимы, они связаны между собой следующими ограничениями. С первого завода вывозится 400 т бетона, следовательно,

Со второго завода вывозится 560 т, следовательно,

На первую стройплощадку завозится 220 т бетона, следовательно,

Аналогично можно записать для остальных стройплощадок:

Таким образом, х_ij должны удовлетворять следующей системы ограничений:

(5.2)

К этим ограничениям необходимо добавить еще х_ij > 0 (так как обратно бетон со стройплощадок на заводы не увозится).

Задача математически ставится так: найти минимум функции (5.1) при условии, что её аргументы удовлетворяют системе уравнений (5.2).

Задача 2 (Задача о ресурсах).

В распоряжении бригады имеются следующие ресурсы: 300 кг металла, 100 м² стекла, 160 чел.-ч (человеко-часов) рабочего времени. Бригаде поручено изготовлять два наименования изделий - А и В. Цена одного изделия А – 10 р., для его изготовления необходимо 4 кг металла, 2 м² стекла и 2 чел.-ч рабочего времени. Цена одного изделия В - 12 р., для его изготовления необходимо 5 кг металла, 1 м² стекла и 3 чел.-ч рабочего времени. Требуется так спланировать объем выпуска продукции, чтобы ее стоимость была максимальной.

Получим математическую модель этой задачи. Обозначим через х₁ и х₂ количество изделий А и В, которое необходимо запланировать (это искомые величины).

Полная стоимость запланированной к производству продукции выражается функцией

(5.3)

На х₁ изделий А требуется 4х₁ кг металла, 2х₁ м² стекла и 2х₁ чел.-ч рабочего времени. На х₂ изделий В требуется 5х₂, кг металла, х₂ м² стекла и 3х₂

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

4 х₁ +5 х₂ < 300

2 х₁ + х₂ < 100 (5.4)

2 х₁ +3 х₂ < 160

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

Задача 3.

Из листового проката определенной формы необходимо вырезать некоторое количество заготовок двух типов А и В для производства 90 шт. изделий. Для одного изделия требуются 2 заготовки типа А и 10 заготовок типа В. Возможны четыре варианта раскроя одного листа проката. Количество заготовок А и В, вырезаемых из одного листа при каждом варианте раскроя, а также отходы от раскроя указаны в таблице 9.

Какое количество листов проката нужно раскроить при помощи каждого варианта для изготовления 90 шт. изделий, чтобы отходы от раскроя были наименьшими?

Таблица 9 – Исходные данные для задачи 3.

Получим математическую модель задачи.

Пусть х₁, х₂, х₃, x₄ - количество листов проката, раскраиваемых соответственно вариантами 1, 2, 3, 4.

Отходы от раскроя составят

(5.5)

Для производства 90 шт. изделий необходимо 180 заготовок типа А и 900 - типа В. Следовательно, аргументы функции (5.5) должны удовлетворять системе уравнений

4 x₁ + 3 х₂ + х₃ =180 (5.6)

З х₂ + 9 x₃ + 12 x₄ =900

Следовательно, математически задача ставится так: найти минимум функции (5.5) при условии, что ее аргументы удовлетворяют системе уравнений (5.6).

Задача 4.

Необходимо составить наиболее дешевую смесь из трех веществ. В состав смеси должны входить не менее 6 единиц химического вещества А, не менее 8 единиц вещества В и не менее 12 единиц вещества С. Имеются 3 вида продуктов (I, II, III), содержащих эти химические вещества в следующих пропорциях (таблица 10).

Таблица 10 – Исходные данные для задачи 4

Стоимость одной весовой единицы продукта 1 - 2 р., продукта II -3 р., продукта III - 2, 5 р.

Получим математическую модель задачи.

Обозначим через х₁, х₂, х₃ - количество продуктов вида I, II, III соответственно, входящих в смесь.

Стоимость смеси из трех веществ выражается функцией

(5.7)

Система ограничений примет вид

2 x₁ + х₂ + 3 x₃ > 6

х₁ + 2 х₂ + 1, 5 х₃> 8 (5.8)

3 х₁ + 4х₂ + 2 х₃ > 12

Математически задача ставится так: найти минимум функции (5.7) при условии, что ее аргументы удовлетворяют системе неравенств (5.8).

Задача 5.

В задаче 1 все производственное сырье (бетон) было использовано. Но бывает и так, что часть сырья не используется. Такие задачи называются открытыми. Рассмотрим одну из таких задач.

Имеются 4 хранилища горючего с запасами 500, 300, 500 и 200 т и 3 заправочные станции с потребностями 300, 400 и 300 т. Стоимость перевозок одной тонны горючего из хранилищ в заправочные станции приведена в таблице 11.

Таблица 11 – Исходные данные для задачи 5

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

В задаче сумма запасов горючего в хранилищах на 500 т больше, чем потребности на станциях. Поэтому введем фиктивную заправочную станцию В с потребностью в горючем 500 т, равной разности суммы запасов и суммы потребностей. Стоимость перевозок горючего из хранилищ А₁, А₂, А₃, А₄ в фиктивную станцию В₄ назначим равной нулю.

Теперь постановка рассматриваемой задачи не отличается от постановки задачи 1.

Задача 6.

Найти оптимальную массу плоской фермы при выполнении условий прочности (рисунок 22).

Рисунок 22 – Условия прочности к задаче 6

Эта задача не столько экономическая, сколько техническая - задача оптимизации строительных конструкций.

Статически неопределимая шарнирно-стержневая система (ферма) нагружена силой F.

Необходимо выбрать площади поперечных сечений А таким образом, чтобы общая масса М фермы была минимальной.

Длина стержней L, м, известна:

l₁ = 6, 3246

l₂= 6, 03 ВС = 2

l₃= 12 СО = 0, 6

l₄=2, 6

Масса фермы определяется формулой

(5.9)

где ρ - удельный вес материала стержней, кг/м³.

Выражение (5.9) - функция цели, минимум которой нужно найти.

Систему ограничений составим из условий прочности. Требуется, чтобы во всех стержнях фермы напряжения не превосходили по абсолютной величине расчетного сопротивления материала стержней R (одинакового на растяжение и сжатие).

(5.10)

Следовательно, система ограничений представляется в виде двух неравенств

(5.11)

Первое неравенство в (5.11) означает, что стержень работает на сжатие, второе - на растяжение. Так как стержни 1 и 4 работают только на сжатие, а 2 - только на растяжение, то систему (5.11) можно записать в виде

(5.12)

Исходя из условий равновесия в узлах фермы, получим три уравнения с четырьмя неизвестными:

Подставляя эти выражения в неравенства (5.12) и вводя дополнительные переменные у, получим систему ограничений в виде равенств:

y₁ – RA₁+1, 5812N₄=-1, 5812F

y₂ – RA₂-5, 025N₄=0

y₃ – RA₃-6, 5N₄=1, 5F (5.13)

y₄ – RA₃+6, 5N₄=-1, 5F

y₅ – RA₄-N₄=0

Таким образом, математически задача ставится так: найти минимум функции (5.9) при условии, что ее аргументы удовлетворяют системе ограничений (5.13).

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

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

Функция, глобальный экстремум которой находится, называется функцией цели, а условия, налагаемые на ее аргументы, называются системой ограничений.

Естественными называются ограничения, при которых все аргументы функции цели считаются неотрицательными.

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

Различают следующие виды математического программирования: линейное, нелинейное, динамическое и др.

Математическое программирование называется линейным, если функция цели и система ограничений линейны относительно всех аргументов.

В противном случае математическое программирование называется нелинейным.

Математическое программирование называется динамическим, если условия рассматриваемой задачи зависят от времени.

Область возможного изменения аргументов функции цели, определяемая системой ограничений, называется областью допустимых значений аргументов. Следовательно, минимум функции цели нужно искать в точках, принадлежащих этой области. Можно показать, что в случае линейного программирования областью допустимых значений аргументов будет:

при 2 аргументах - выпуклый многоугольник, так как система ограничений в этом случае (графически) - это система прямых линий (рисунок 23);

Рисунок 23 – Область допустимых значений при двух аргументах

при 3 аргументах – выпуклый многогранник;

при n > 3 аргументов – это выпуклый гипермногогранник.

В математическом программировании речь идет о нахождении глобального экстремума функции цели. Этот экстремум может быть внутри или на границе области допустимых значений аргументов.

Можно показать, что в случае линейного программирования, если глобальный экстремум функции цели существует, то он имеет место только в вершинах многоугольника, многогранника и гипермногогранника.

Дадим общую формулировку задачи линейного программирования в канонической форме. Требуется найти глобальный минимум линейной функции n аргументов (функции цели)

(5.14)

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

a₁₁x₁+a₁₂x₂+…+a_1nx_n=b₁

a₂₁x₁+a₂₂x₂+…+a_2nx_n=b₂ (5.15)

…....................................

a_m1x₁+a_m2x₂+…+a_mnx_n=b_m

ранг матрицы которой r < n.

(Ранг матрицы – это наивысший порядок отличного от нуля определителя, который можно из этой матрицы составить.) Ранг матрицы равен числу основных, базисных неизвестных. Будем считать, что все b_k > 0. Занумеруем неизвестные так, чтобы свободными неизвестными были первые р неизвестных (р = n – r). Тогда прочие r неизвестных, называемых базисными, можно выразить из системы (5.15):

x_p+1=β ₁+ α ₁₂x₁+ α ₁₂x₂+…+α _1px_p

x_p+2=β ₂+ α ₂₁x₁+ α ₂₂x₂+…+α _2px_p (5.16)

…................................................

x_p+r=β _r+ α _r1x₁+ α _r2x₂+…+α _rpx_p

Система (5.16) называется базисной системой ограничений.

Подставив (5.16) в выражение (5.14) вместо базисных неизвестных, получим функцию цели в базисной форме

(5.17)

Задание функции цели в виде (5.17), а системы ограничений в виде (5.16) называется базисной формой задачи линейного программирования (такая форма задачи линейного программирования нужна для симплекс-метода).

Упорядоченная совокупность n величин (х₁, х₂, …, x_n), удовлетворяющая системе ограничений (5.15) или (5.16), называется допустимым решением (планом).

Допустимое решение, у которого все свободные неизвестные равны нулю, называется допустимым базисным решением, или опорным планом (это как раз вершины многоугольника, многогранника, гипермногогранника). Упорядоченная совокупность n величин (х₁ х₂, …, х_n), удовлетворяющая системе ограничений (5.15) или (5.16) и дающая глобальный экстремум функции цели (5.14) или (5.17) называется оптимальным решением (планом).

Известно, что оптимальный план, если он существует, принадлежит множеству опорных планов.

Число опорных планов конечно. Оно равно С (числу сочетаний из n по р). Но, например, число С²⁰₅₀= 10²⁰ – очень большое, перебор всех опорных планов провести трудно, поэтому такой перебор нереален.

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

Изложим методику применения симплекс-метода в общем виде.

1 Систему ограничения вида (5.15) следует привести к базисной форме по правилам линейной алгебры.

2 Положив в базисной системе уравнений все свободные неизвестные равными нулю, нужно найти значения базисных неизвестных. Если эти значения будут неотрицательными, то первый исходный план будет опорным. В противном случае следует выбрать другие свободные неизвестные так, чтобы исходный план был опорным.

3 В выражении функции цели базисные неизвестные нужно заменить их выражениями из базисной системы уравнений.

4 Положив в найденном выражении функции цели все свободные неизвестные равными нулю, найдем значение функции цели, соответствующее выбранному опорному плану.

5 Если все коэффициенты при свободных неизвестных в функции цели неотрицательные, то найденный опорный план будет оптимальным, а найденное значение функции цели будет искомым глобальным ее минимумом.

6 Если же не все коэффициенты при свободных неизвестных функции цели будут неотрицательными, то нужно выбрать свободную неизвестную с отрицательным коэффициентом, например, x_α (обычно берется неизвестная с максимальным по модулю отрицательным коэффициентом). Далее положить в базисной системе уравнений все свободные неизвестные, кроме х_α , равными нулю и определить максимально возможное значение х_α , при котором все базисные неизвестные неотрицательные.

7 Ту из базисных неизвестных, например, х_β , которая обращается в нуль при указанном значении x_α , следует выбрать за свободную неизвестную вместо x.

Неизвестную же x_α перевести в разряд базисных.

8 Далее следует повторить цикл расчетов по пп. 3 – 7 до тех пор, пока опорный план не будет оптимальным, то есть пока все коэффициенты при свободных неизвестных в функции цели не будут неотрицательными.

В математическом обеспечении ЭВМ есть стандартная программа решения задач линейного программирования по симплекс-методу.