3. ПРИМЕНЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ОБЩЕЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

ПРОГРАММЫ «SIMPLY», «SIMPLINT», «RASM»

3.1. Формулировка задачи

Общей задачей линейного программирования (ОЗЛП) называется задача, состоящая в определении экстремального (максимального или минимального) значения линейной функции [14, 70]

j =n

F( X ) = ∑ c j x j + c0 (3.l) j =1

при условиях

j =n
∑aij xj = bi	(i=1, 2, …, m)	(3.2)
j =1
xk ≥ 0 (k L {1,2,...,n})		(3.3)

где aij, ci, bi – фиксированные действительные числа; = – один из знаков отношения: ≤, ≥, =. Другими словами, в ОЗЛП ищется оптимальное значение линейной функции (3.1) на множестве решений системы равенств и неравенств (3.2) при условии неотрицательности некоторых переменных. Заметим, что требование неотрицательности (3.3) может быть наложено на все переменные (L = {1, 2, …, n}) или вообще отсутствовать (L = 0).

Функция F(X) называется линейной формой или целевой функцией задачи (3.1) – (3.3), а условия – (3.2) – (3.3) – ограничениями.

Совокупность чисел X=(x1, x2,..., xn), удовлетворяющая ограничениям (3.2) – (3.3), называется допустимым решением или планом задачи.

План X = (x1* , x2* ,..., xn* ) , при котором целевая функция принимает

минимальное или максимальное значение, называется оптимальным. Оптимальное решение задачи находится симплекс-методом, кото-

рый реализован в программе «Simply».

Входные данные программного обеспечения для решения общей задачи линейного программирования симплекс-методом «Simply» приведены в таблицах 3.1–3.5.

26

Таблица 3.1. Исходные данные

Показатель	Обозначение	Поле
Наименование решаемой задачи	Задача	Name
Общее количество переменных, шт.	n	N1
Тип целевой функции	T	T
Таблица вида целевой функции	Целевая	Tabl1
Таблица уравнений и неравенств	Уравнения	Tabl2
Количество уравнений и неравенств, шт.	m	K2
Таблица ограничений вида: Xi>=0 или Xi>=Bi или	Ограничения 1	Tabl3
Xi<=Bi
Количество ограничений вида: Xi>=0 или Xi>=Bi	k	K3
или Xi<=Bi, шт.
Таблица ограничений вида: Di<=Xi<=Fi	Ограничения 2	Tabl4
Количество ограничений вида: Di<=Xi<=Fi, шт.	l	K4

Таблица 3.2. Коэффициенты целевой функции

Коэффициент	1	..	i	..	n	0
	c1	..	ci	..	cn	c0

Таблица 3.3. Коэффициенты уравнений и неравенств

		Коэффициент						Код	0
Уравнение								(=, >=, <=)
	1		..	i	..		n
1	a11		..	a1i	..		a1n	=	a10
..	..		..	..	..	..		..	..
i	ai1		..	aii	..		ain	=	ai0
..	..		..	..	..	..		..	..
m	am1		..	ami	..		amn	=	am0

Таблица 3.4. Коэффициенты ограничений 1

Ограничение	xi	Код	bi
		(>=, <=)
1	x1	>=	b1
..	..	..	..
i	xi	>=	bi
..	..	..	..
k	xk	>=	bk

Таблица 3.5. Коэффициенты ограничений 2

Ограничение	di	Код	xi	Код	fi
		(<=)		(<=)
1	d1	<=	x1	<=	f1
..	..	..	..	..	..
i	di	<=	xi	<=	fi
..	..	..	..	..	..
l	dl	<=	xl	<=	fl

27

3.2. Примеры формулировок экономических задач и их решений при помощи программ «Simply», «Simplint» и «Rasm»

Рассмотрим три примеры формулировок экономических задач и их решения при помощи программ «Simply», «Simplint» и «Rasm». Задачи взяты из главы 8, содержащей варианты задач для самостоятельного решения.

Задача 4. Магистральные дороги области строятся двух типов – с асфальтобетонным и бетонным верхним покрытием. Известны: наличие ресурсов и нормы расходования их на строительство 1 километра дорог разного типа, а также прибыль дорожно-строительной организации от реализации 1 километра дорог с различным покрытием (таблица 3.11). Требуется определить, сколько километров дорог различного типа можно построить при условии максимального использования наличных ресурсов и получения дорожно-строительной организацией максимальной прибыли.

Пример выбора исходных данных и математической формулировки задачи.

Таблица 3.6. Исходные данные для решения задачи 4

	Наличие (Аi) и расход (Вi и Вj) ресурсов, тыс. м3														Прибыль
.	Асфальт.			Бетон				Песок				Гравий			С1	С2
Вар
	А1	Вi	Вj	А2		Вi	Вj	А3		Вi	Вj	А4	Вi	Вj
1	20	0,6	-	30		-	1,2	60		1,5	2,0	45	2,0	1,0	5,0	7,0

Для решения задачи введем условные обозначения:

X1 – протяженность строящихся асфальтобетонных дорог, км; X2 – протяженность строящихся бетонных дорог, км.

Ограничения решения задачи по материальным ресурсам записываются в виде следующих неравенств:

по асфальтобетону 0,6 X1 ≤ 20; по бетону 1,2 X2 ≤ 30;

по песку 1,5 X1 +2 X2 ≤ 60;

по гравию 2 X1 + X2 ≤ 45,

при этом следует учитывать, что по смыслу задачи значения X1 и X2 не могут быть отрицательными, т. е.

X1 ≥ 0; и X2 ≥ 0.

Целевая функция запишется в следующем виде:

L = 5X1 + 7X2 → max.

Решение данной задачи с помощью программы «Simply» приводится в приложении П5.

Задача 5. Требуется построить жилые дома для работников предприятия. Известна потребность в квартирах двух типов: однокомнатных 400 квартир, двухкомнатных 1000 квартир. Архитекторы и строители представили к застройке четыре варианта домов, которые

28

вмещают известное количество квартир обоих типов. Определена стоимость строительства каждого дома. Необходимо решить вопрос о том, какое количество домов того или иного варианта требуется строить, чтобы обеспечить потребность предприятия в квартирах, исходя из минимума затрат на строительство. Учесть, что количество домов должно быть целым числом.

Исходные данные задачи 5 приведены в таблице 3.7.

Таблица 3.7. Исходные данные для решения задачи 5

Тип	Вместимость вариантов домов, квартиры				Потребность
квартир	1	2	3	4	в квартирах
Однокомнатная	30	40	10	–	400
Двухкомнатная	50	30	–	10	1000
Стоимость, млн. руб.	96	120	20	18

Формируем математическую модель. Принимаем за неизвестные xi – количество домов варианта i (i = 1, 2, 3, 4), тогда задача ЛП будет иметь следующий вид.

Целевая функция

F(X ) = 96x1 +120x2 + 20x3 +18x4 min

Ограничения

30x1 + 40x2 +10x3 + 0x4 = 400

50x1 + 30x2 + 0x3 +10x4 =1000

x1 ≥ 0 ; x2 ≥ 0 ; x3 ≥ 0 ; x4 ≥ 0 ; xi – целые числа

Результаты решения задачи с помощью программы «Simplint» приведены в приложении П8.

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

Критерием оптимальности в математической модели является – минимум энергозатрат:

i=m j =n
Эсум = ∑∑Эудij Xij	→ min , (3.3)
i=1 j =1
где Эсум – суммарные энергозатраты	на производство работ,

кВт год/ед. изм. (ед. изм. – единица измерения в которой измеряется объем работ);

Эудij – удельная энергоемкость работы i-ой машины на j-м производ-

ственном объекте, кВт·ч/ед. изм.;

Xij – продолжительность работы i-й машины на j-м объекте, ч; m – количество машин;

n – количество производственных объектов.

29

Э	удij	=	Nдвi	, (3.4)
			Пэij

где Nдвi – мощность двигателя i-ой машины, кВт;

Пэij – часовая эксплуатационная производительность i-й машины на j-м объекте, ед. изм./ч.

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

Пэij = Птi Куслj , (3.5)

где Птi – техническая производительность i-й машины, ед. изм./ч;

Kуслj – коэффициент, учитывающий местные условия на j-м объекте (коэффициент местных условий может принимать значения от 0 до 1).

Среди условий оптимизации распределения техники необходимо выделить следующие:

1) Полное выполнение объемов работ на объектах ресурсами имеющегося парка машин:

i=m

Vj = ∑Пэij Xij , (3.6)

i=1

где Vj – планируемый объем работ на j-м производственном объекте, ед. изм.

2) Своевременное выполнение объемов работ, в соответствии с имеющимся фондом рабочего времени машин:

j=n

Фi ≥ ∑Xij , (3.7)

j=1

где Фi – фонд рабочего времени i-й машины в планируемом периоде, ч. 3) Продолжительность работы машины при расчетах не должна

принимать отрицательных значений:

Xij ≥ 0 . (3.8)

Учитывая отмеченные ограничения, экономико-математическая модель оптимизации распределения парка машин по производственным объектам будет иметь следующий вид:

i=m j =n
Эсум = ∑∑Эудij Xij → min ,
i=1	j =1
Vj = ∑Пэij Xij
	i=m
	i=1	(3.9)
	j=n
Фi ≥ ∑Xij
	j=1

30

Xij ≥ 0 ,

i =1,2,...,m; j =1,2,...,n .

Рассмотренная математическая модель реализована в программе «Rasm». Приведем пример формулировки и решения задачи наилучшего распределения парка машин по объектам.

Задача 11. Требуется определить оптимальный план распределения землеройных машин по производственным объектам согласно исходным данным, приведенным в таблице 3.8. Производственный план должен предусматривать полное выполнение объемов работ на каждом из пяти производственных объектов (V1, V2, V3, V4, V5) имеющимся парком машин, в сроки ограниченные фондом рабочего времени машин. При оптимизации распределения техники суммарные энергозатраты должны быть минимальные.

Таблица 3.8. Показатели машин

		Объекты и объемы работ, м3					Техни-	Мощность	Фонд
Марка	V1		V2	V3	V4	V5	ческая	двигателя	рабо-
машины							произ-	Nдвi,	чего
	77000		46000	38000	73000	110000	води-	кВт	вре-
							тель-		мени
							ность		Фi,
							Птi,		маш.-
							м3/ч		ч
ДЗ-11П	37,6		38,0	36,8	34,4	36,0	40	158	1620
ДЗ-13	65,8		66,5	64,4	60,2	63,0	70	265	1620
ЭО-	18,8		19,0	18,4	17,2	18,0	20	44	2330
2621А
ЭО-3322	23,5		23,8	23,0	21,5	22,5	25	55	2330
ЭО-4321	37,6		38,0	36,8	34,4	36,0	40	59	2315
ЭО-4121	47,0		47,5	46,0	43,0	45,0	50	95	2315
Коэф-	0,94		0,95	0,92	0,86	0,9
фициент
местных
условий,
Kуслj

1.Определить оптимальную продолжительность работы машин на объектах.

2.Рассчитать энергозатраты на разработку грунта по производственным объектам.

3.Определить резерв машинного времени по каждой машине.

Для решения задачи введем условные обозначения:

Xij – продолжительность работы i-й машины на j-м объекте, ч.

Тогда существующие ограничения в ресурсах при решении задачи запишутся следующими неравенствами:

37,6 X11 + 65,8 X21 + 18,8 X31 + 23,5 X41 + 37,6 X51 + 47,0 X61 = 77000; 38,0 X12 + 66,5 X22 + 19,0 X32 + 23,8 X42 + 38,0 X52 + 47,5 X62 = 46000; 36,8 X13 + 64,4 X23 + 18,4 X33 + 23,0 X43 + 36,8 X53 + 46,0 X63 = 38000;

31

34,4 X14 + 60,2 X24 + 17,2 X34 + 21,5 X44 + 34,4 X54 + 43,0 X64 = 73000; 36,0 X15 + 63,0 X25 + 18,0 X35 + 22,5 X45 + 36,0 X55 + 45,0 X65 =

110000;

X11 + X12 + X13 + X14 + X15 ≤ 1620;

X21 + X22 + X23 + X24 + X25 ≤ 1620;

X31 + X32 + X33 + X34 + X35 ≤ 2330;

X41 + X42 + X43 + X44 + X45 ≤ 2330;

X51 + X52 + X53 + X54 + X55 ≤ 2315;

X61 + X62 + X63 + X64 + X65 ≤ 2315;

при этом следует учитывать, что по смыслу задачи значения X11 … X65 не могут быть отрицательными, т. е.

X11 ≥ 0 … X65 ≥ 0.

Целевая функция запишется в следующем виде:

L = 4,202 X11 + 4,158 X12 + 4,293 X13 + 4,593 X14 + 4,389 X15 + + 4,027 X21 + 3,985 X22 + 4,115 X23 + 4,402 X24 + 4,206 X25 + + 2,340 X31 + 2,316 X32 + 2,391 X33 + 2,558 X34 + 2,444 X35 + + 2,340 X41 + 2,311 X42 + 2,391 X43 + 2,558 X44 + 2,444 X45 + + 1,569 X51 + 1,553 X52 + 1,603 X53 + 1,715 X54 + 1,639 X55 +

+ 2,021 X61 + 2,000 X62 + 2,065 X63 + 2,209 X64 + 2,111 X65 → min.

Результаты решения задачи с помощью программы «Rasm» приводятся в приложении П7.

32