Солдатенко Л.В. Введение в математическое моделирование строительно-технологических задач
Подождите немного. Документ загружается.
111
разноплановых работ.
Рассмотрим несколько характерных задач и получим для них
математическую формулировку (математическую модель).
Задача 1 (Транспортная задача.)
В городе имеется 2 бетонных завода. Первый выпускает в день 400 т
бетона, а второй - 560 т. Бетон с этих заводов отправляется на 4
стройплощадки. На первую стройплощадку поступает в день 220 т бетона, на
вторую - 200 т, на третью- 180 т, на четвертую - 360 т. Стоимость перевозки
одной тонны бетона с каждого завода на каждую стройплощадку известна.
Требуется так организовать перевозку бетона с заводов на стройплощадки,
чтобы суммарная стоимость всех перевозок была минимальной.
От содержательной постановки задачи перейдем к математической. Если
обозначить через С
ij
- стоимость перевозки одной тонны бетона с i - го завода
на j- ю стройплощадку (это известные величины), а через х
ij
- количество тонн
бетона, которое нужно перевести с i - го завода на j -ю стройплощадку (это
искомые величины), то стоимость всех перевозок будет выражаться функцией
∑∑
==
=
2
1
4
1ij
ijij
xCf
(5.1)
Необходимо найти минимум этой функции, но х
ij
не независимы, они
связаны между собой следующими ограничениями. С первого завода вывозится
400 т бетона, следовательно,
∑
=
=
4
1
1
400
j
j
x
Со второго завода вывозится 560 т, следовательно,
∑
=
=
4
1
2
560
j
j
x
На первую стройплощадку завозится 220 т бетона, следовательно,
∑
=
=
2
1
1
220
i
i
x
Аналогично можно записать для остальных стройплощадок:
∑∑∑
===
===
2
1
2
1
43
2
1
2
.360,180,200
ii
ji
i
i
xxx
Таким образом, х
ij
должны удовлетворять следующей системы
ограничений:
112
∑∑∑∑∑
=====
=====
2
1
4
2
1
3
4
1
2
1
12
4
1
1
.360,180,220,560,400
i
i
i
i
ji
ij
j
j
xxxxx
(5.2)
К этим ограничениям необходимо добавить еще х
ij
> О (так как обратно
бетон со стройплощадок на заводы не увозится).
Задача математически ставится так: найти минимум функции (5.1) условии,
что ее аргументы удовлетворяют системе уравнений (5.2).
Задача 2 (Задача о ресурсах).
В распоряжении бригады имеются следующие ресурсы: 300 кг металла,
100 м
2
стекла, 160 чел.-ч (человеко-часов) рабочего времени. Бригаде поручено
изготовлять два наименования изделий - А и В. Цена одного изделия А – 10 р.,
для его изготовления необходимо 4 кг металла, 2 м
2
стекла и 2 чел.-ч рабочего
времени. Цена одного изделия В - 12 р., для его изготовления необходимо 5 кг
металла, 1 м
2
стекла и 3 чел.-ч рабочего времени. Требуется так спланировать
объем выпуска продукции, чтобы ее стоимость была максимальной.
Получим математическую модель этой задачи. Обозначим через х
1
и х
2
количество изделий А и В, которое необходимо запланировать (это искомые
величины).
Полная стоимость запланированной к производству продукции выражается
функцией
21
1210
xx
f
+
=
(5.3)
На х
1
изделий А требуется 4х
1
кг металла, 2х
1
м
2
стекла и 2х чел.-ч
рабочего времени. На х
2
изделий В требуется 5х
2
, кг металла, х
2
м
2
стекла и 3х
2
чел.-ч рабочего времени. Следовательно, так как ресурсы заданы, то должны
выполняться условия:
4 х
1
+5 х
2
< 300
2 х
1
+ х
2
< 100 (5.4)
2 х
1
+3 х
2
<160
Таким образом, нужно найти максимум функции (5.3) при условии, что ее
аргументы удовлетворяют системе неравенств (5.4).
Задача 3.
Из листового проката определенной формы необходимо вырезать
некоторое количество заготовок двух типов А и В для производства 90 шт.
изделий. Для одного изделия требуются 2 заготовки типа А и 10 заготовок типа
В. Возможны четыре варианта раскроя одного листа проката. Количество
заготовок А и В, вырезаемых из одного листа при каждом варианте раскроя, а
также отходы от раскроя указаны в таблице 9.
Какое количество листов проката нужно раскроить при помощи каждого
варианта для изготовления 90 шт. изделий, чтобы отходы от раскроя были
наименьшими?
113
Таблица 9 – Исходные данные для задачи 3.
Заготовки, шт.
Вариант раскроя
А В
Отходы от
раскроя, ед.
1 4 0 12
2 3 3 5
3 1 9 3
4 0 12 0
Получим математическую модель задачи.
Пусть х
1
, х
2
, х
3
, x
4
- количество листов проката, раскраиваемых
соответственно вариантами 1, 2, 3, 4.
Отходы от раскроя составят
31
3512
2
xf
xx
+
+
=
(5.5)
Для производства 90 шт. изделий необходимо 180 заготовок типа А и 900 -
типа В. Следовательно, аргументы функции (5.5) должны удовлетворять
системе уравнений
4 x
1
+ 3 х
2
+ х
3
=180 (5.6)
З х
2
+ 9 x
3
+ 12 x
4
=900
Следовательно, математически задача ставится так: найти минимум
функции (5.5) при условии, что ее аргументы удовлетворяют системе
уравнений (5.6).
Задача 4.
Необходимо составить наиболее дешевую смесь из трех веществ. В состав
смеси должны входить не менее 6 единиц химического вещества А, не менее 8
единиц вещества В и не менее 12 единиц вещества С. Имеются 3 вида
продуктов (I, II, III), содержащих эти химические вещества в следующих
пропорциях (таблица 10).
Таблица 10 – Исходные данные для задачи 4
Вещества
Продукты
А В С
I 2 1 3
II 1 2 4
III 3 1,5 2
Стоимость одной весовой единицы продукта 1 - 2 р., продукта II -3 р.,
продукта III - 2,5 р.
Получим математическую модель задачи.
114
Обозначим через х
1
, х
2
, х
3
- количество продуктов вида I, II, III
соответственно, входящих в смесь.
Стоимость смеси из трех веществ выражается функцией
321
5,232
xxx
f
+
+
=
(5.7)
Система ограничений примет вид
2 x
1
+ х
2
+ 3 x
3
> 6
х
1
+ 2 х
2
+ 1,5 х
3
>8 (5.8)
3 х
1
+ 4х
2
+ 2 х
3
>12
Математически задача ставится так: найти минимум функции (5.7) при
условии, что ее аргументы удовлетворяют системе неравенств (5.8).
Задача 5.
В задаче 1 все производственное сырье (бетон) было использовано. Но
бывает и так, что часть сырья не используется. Такие задачи называются
открытыми. Рассмотрим одну из таких задач.
Имеются 4 хранилища горючего с запасами 500, 300, 500 и 200 т и 3
заправочные станции с потребностями 300, 400 и 300 т. Стоимость перевозок
одной тонны горючего из хранилищ в заправочные станции приведена в
таблица 11.
Таблица 11 – Исходные данные для задачи 5
Заправочные станции
Хранилища
B
1
B
2
B
3
A
1
6 4 5
A
2
8 3 2
A
3
7 5 6
A
4
5 2 2
Требуется спланировать перевозку горючего так, чтобы затраты были
минимальными.
В задаче сумма запасов горючего в хранилищах на 500 т больше, чем
потребности на станциях. Поэтому введем фиктивную заправочную станцию В
с потребностью в горючем 500 т, равной разности суммы запасов и суммы
потребностей. Стоимость перевозок горючего из хранилищ А
1
, А
2
, А
3
, А
4
в
фиктивную станцию В
4
назначим равной нулю.
Теперь постановка рассматриваемой задачи не отличается от постановки
задачи 1.
Задача 6.
Найти оптимальную массу плоской фермы при выполнении условий
прочности (рисунок 22).
115
Рисунок 22 – Условия прочности к задаче 6
Эта задача не столько экономическая, сколько техническая - задача
оптимизации строительных конструкций.
Статически неопределимая шарнирно-стержневая система (ферма)
нагружена силой F.
Необходимо выбрать площади поперечных сечений А таким образом чтобы
общая масса М фермы была минимальной.
Длина стержней L, м, известна:
l
1
= 6,3246
l
2
= 6,03 ВС = 2
l
3
= 12 СО = 0,6
l
4
=2,6
Масса фермы определяется формулой
)6.21206.126492.12(
4321
AAAAM
+
+
+
=
ρ
(5.9)
где ρ - удельный вес материала стержней, кг/м
3
.
Выражение (5.9) - функция цели, минимум которой нужно найти.
Систему ограничений составим из условий прочности. Требуется, чтобы во
всех стержнях фермы напряжения не превосходили по абсолютной величине
расчетного сопротивления материала стержней R (одинакового на растяжение и
сжатие)
R
A
N
i
i
≤
(5.10)
Следовательно, система ограничений представляется в виде двух
неравенств
116
0,0 ≥
+
−
≥+
iiii
RANRAN (5.11)
Первое неравенство в (5.11) означает, что стержень работает на сжатие,
второе - на растяжение. Так как стержни 1 и 4 работают только на сжатие, а 2 -
только на растяжение, то систему (5.11) можно записать в виде
.0;0;0;0;0
3333224411
≥
+
−
≥
+
≥
+
−≥+≥+ RANRANRANRANRAN (5.12)
Исходя из условий равновесия в узлах фермы, получим три уравнения с
четырьмя неизвестными:
.5,15,6;025,5;5812,15812,1
434241
FNNNNFNN +
=
−
=
−−=
Подставляя эти выражения в неравенства (5.12) и вводя дополнительные
переменные у, получим систему ограничений в виде равенств:
y
1
– RA
1
+1,5812N
4
=-1,5812F
y
2
– RA
2
-5,025N
4
=0
y
3
– RA
3
-6,5N
4
=1,5F (5.13)
y
4
– RA
3
+6,5N
4
=-1,5F
y
5
– RA
4
-N
4
=0
Таким образом, математически задача ставится так: найти минимум
функции (5.9) при условии, что ее аргументы удовлетворяют системе
ограничений (5.13).
Таким образом, для различных производственных задач получается одна и
та же математическая модель, которая состоит в следующем.
Нужно найти экстремум некоторой функции, аргументы которой
удовлетворяют некоторой системе уравнений или неравенств. Такие задачи
получили название задач математического программирования.
Функция, глобальный экстремум которой находится, называется функцией
цели, а условия, налагаемые на ее аргументы, называются системой
ограничений.
Естественными называются ограничения, при которых все аргументы
функции цели считаются неотрицательными.
Канонической формой задачи математического программирования
считается такая форма, когда находится глобальный минимум функции цели и
система ограничений, исключая естественные, выражается равенствами.
Различают следующие виды математического программирования:
линейное, нелинейное, динамическое и др.
Математическое программирование называется линейным, если функция и
цели и система ограничений линейны относительно всех аргументов.
В противном случае математическое программирование называется
нелинейным.
117
Математическое программирование называется динамическим, если
условия рассматриваемой задачи зависят от времени.
Область возможного изменения аргументов функции цели, определяемая
системой ограничений, называется областью допустимых значений аргументов.
Следовательно, минимум функции цели нужно искать в точках,
принадлежащих этой области. Можно показать, что в случае линейного
программирования областью допустимых значений аргументов будет:
при 2 аргументах - выпуклый многоугольник, так как система ограничений
в этом случае (графически) - это система прямых линий (рисунок 23);
Рисунок 23 – Область допустимых значений при двух аргументах
при 3 аргументах – выпуклый многогранник;
при n > 3 аргументов – это выпуклый гипермногогранник.
В математическом программировании речь идет о нахождении глобального
экстремума функции цели. Этот экстремум может быть внутри или на границе
области допустимых значений аргументов.
Можно показать, что в случае линейного программирования, если
глобальный экстремум функции цели существует, то он имеет место только в
вершинах многоугольника, многогранника и гипермногогранника.
Дадим общую формулировку задачи линейного программирования в
канонической форме. Требуется найти глобальный минимум линейной
функции n аргументов (функции цели)
∑
=
+=
n
i
ii
xCff
1
0
(5.14)
при условии, что аргументы этой функции удовлетворяют следующей
совместной (имеющей решение), неопределенной (имеющей множество
решений) системе линейных алгебраических уравнений:
a
11
x
1
+a
12
x
2
+…+a
1n
x
n
=b
1
a
21
x
1
+a
22
x
2
+…+a
2n
x
n
=b
2
(5.15)
…....................................
a
m1
x
1
+a
m2
x
2
+…+a
mn
x
n
=b
m
Ранг матрицы которой r < n.
(Ранг матрицы – это наивысший порядок отличного от нуля определителя,
118
который можно из этой матрицы составить.) Ранг матрицы равен числу
основных, базисных неизвестных. Будем считать, что все b
k
> 0. Занумеруем
неизвестные так, чтобы свободными неизвестными были первые р неизвестных
(р = n – r). Тогда прочие r неизвестных, называемых базисными, можно
выразить из системы (5.15):
x
p+1
=β
1
+ α
12
x
1
+ α
12
x
2
+…+α
1p
x
p
x
p+2
=β
2
+ α
21
x
1
+ α
22
x
2
+…+α
2p
x
p
(5.16)
…................................................
x
p+r
=β
r
+ α
r1
x
1
+ α
r2
x
2
+…+α
rp
x
p
Система (5.16) называется базисной системой ограничений.
Подставив (5.16) в выражение (5.14) вместо базисных неизвестных,
получим функцию цели в базисной форме
∑
=
+=
p
i
ii
xdFF
1
0
(5.17)
Задание функции цели в виде (5.17), а системы ограничений в виде (5.16)
называется базисной формой задачи линейного программирования (такая
форма задачи линейного программирования нужна для симплекс-метода).
Упорядоченная совокупность n величин (х
1
, х
2
, …, x
n
), удовлетворяющая
системе ограничений (5.15) или (5.16), называется допустимым решением
(планом).
Допустимое решение, у которого все свободные неизвестные равны нулю,
называется допустимым базисным решением, или опорным планом (это как раз
вершины многоугольника, многогранника, гипермногогранника).
Упорядоченная совокупность n величин (х
1
х
2
, …,х
n
), удовлетворяющая системе
ограничений (5.15) или (5.16) и дающая глобальный экстремум функции цели
(5.14) или (5.17) называется оптимальным решением (планом).
Известно, что оптимальный план, если он существует, принадлежит
множеству опорных планов.
Число опорных планов конечно. Оно равно С (числу сочетаний из n по р).
Но, например, число С
20
50
= 10
20
– очень большое, перебор всех опорных планов
провести трудно, поэтому такой перебор не реален.
Американским экономистом Дж. Данцигом был предложен метод
направленного перебора опорных планов, при котором функция цели все время
уменьшается. Такой метод получил название симплекс-метода. При таком
направленном переборе нужно провести не более 2n переборов опорных
планов.
Изложим методику применения симплекс-метода в общем виде:
1 Систему ограничения вида (5.15) следует привести к базисной форме по
правилам линейной алгебры.
2 Положив в базисной системе уравнений все свободные неизвестные
равными нулю, нужно найти значения базисных неизвестных. Если эти
значения будут неотрицательными, то первый исходный план будет опорным.
119
В противном случае следует выбрать другие свободные неизвестные так, чтобы
исходный план был опорным.
3 В выражении функции цели базисные неизвестные нужно заменить их
выражениями из базисной системы уравнений.
4 Положив в найденном выражении функции цели все свободные
неизвестные равными нулю, найдем значение функции цели, соответствующее
выбранному опорному плану.
5 Если все коэффициенты при свободных неизвестных в функции цели
неотрицательные, то найденный опорный план будет оптимальным, а
найденное значение функции цели будет искомым глобальным ее минимумом.
6 Если же не все коэффициенты при свободных неизвестных функции цели
будут неотрицательными, то нужно выбрать свободную неизвестную с
отрицательным коэффициентом, например, x
α
(обычно берется неизвестная с
максимальным по модулю отрицательным коэффициентом). Далее положить в
базисной системе уравнений все свободные неизвестные, кроме х
α
, равными
нулю и определить максимально возможное значение х
α
, при котором все
базисные неизвестные неотрицательные.
7 Ту из базисных неизвестных, например, х
β
, которая обращается в нуль
при указанном значении x
α
, следует выбрать за свободную неизвестную вместо
x .
Неизвестную же x
α
перевести в разряд базисных.
8 Далее следует повторить цикл расчетов по пп. 3 – 7 до тех пор, пока
опорный план не будет оптимальным, то есть пока все коэффициенты при
свободных неизвестных в функции цели не будут неотрицательными.
В математическом обеспечении ЭВМ есть стандартная программа решения
задач линейного программирования по симплекс-методу.
5.2 Примеры решения некоторых задач
5.2.1 Решение транспортной задачи
Чтобы применить к решению транспортной задачи симплекс-метод,
переобозначим неизвестные так:
x
1
, х
2
, х
3
, х
4
– количество тонн бетона, которое вывозится с первого
бетонного завода соответственно на 1, 2, 3 и 4-ю строительные площадки;
x
5
, х
6
, х
7
, x
8
– количество тонн бетона, вывозимого со второго бетонного
завода соответственно на 1, 2, 3 и 4-ю строительные площадки. Зададимся
конкретными значениями стоимости перевозки одной тонны бетона с
соответствующих заводов на строительные площадки (в определенных
денежных единицах).
Все данные сведем в таблицу 12.
120
Таблица 12 – Транспортная задача
Входные параметры
Бетонные заводы
Строительные
площадки
Стоимость
перевозки 1т
Количество
тонн
1 Х
1
2
2 Х
2
1
3 Х
3
3
1
4 Х
4
2
1 Х
5
2
2 Х
6
3
3 Х
7
3
2
4 Х
8
1
Тогда функция цели (стоимость всех перевозок) и система ограничений
примут вид
f = 2x
1
+ x
2
+ 3x
3
+ 2x
4
+ 2x
5
+ 3x
6
+ 3x
7
+ x
8
x
1
+ x
2
+ x
3
+ x
4
= 400
x
5
+ x
6
+ x
7
+ x
8
= 560
x
1
+ x
2
= 220 (5.18)
x
2
+ x
6
= 200
x
3
+ x
7
= 180
x
4
+ x
8
= 360
Выпишем матрицу системы ограничений
⎪
⎪
⎪
⎪
⎭
⎪
⎪
⎪
⎪
⎬
⎫
⎪
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎪
⎨
⎧
1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 0
0 0 1 0 0 0 1 0
0 0 0 1 0 0 0 1
1 1 1 1 0 0 0 0
0 0 0 0
1 1 1 1
(5.19)
Теперь нужно найти ранг этой матрицы. Если первые две строки матрицы
поменять местами, то можно получить неравный нулю определитель
01
10001
00010
00100
01000
10000
≠=
⎪
⎪
⎪
⎭
⎪
⎪
⎪
⎬
⎫
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎨
⎧
(5.20)
Следовательно, ранг матрицы системы ограничений r = 5 (не равен нулю