6.4.4. Задача о покрытии местности при строительстве объектов

При планировании строительства производственных, социальных и др. объектов всегда стоит задача правильного их размещения, то есть возникает так называемая задача о покрытии. Эта задача является частным случаем рассмотренных выше задач о раскрое и планировании (в ней b_i=1; a_ij{0,1} ).

Постановка задачи. Для строительства гидроэлектростанций могут быть использованы пять мест Vj (j=1,2,…,5). Каждая ГЭС Vj могла бы обслужить (аij=1) или не обслужить (аij=0) некоторые из четырех регионов Li (i=1,2,…,4). Заданы расходы на строительство каждой ГЭС Vj , равное Сj (у.е.). После сооружения минимального количества электростанций, каждый из четырех регионов должен быть «покрыт» хотя бы один раз. Найти наиболее дешевое «покрытие» всех регионов.

В качестве управляемых переменных примем x_j (j=1,2,…,5), причем x_j=1, если в месте V_j построена ГЭС, и x_j=0 в противном случае.

Математическая модель задачи получается такая же, как и в задаче оптимального раскроя (6.23) – (6.25), но с условием, что b_i=1 (i=1,2,…,4) и с дополнительным условием «x_j=0 или x_j=1» при j=1,2,…,5).

Возможны следующие варианты задачи:

1. Заданы расходы на строительство V_j, равные с_j, и ищется наиболее дешевое «покрытие» всех местностей. Целевая функция в этом случае имеет вид:

2. Можно потребовать также k-кратное покрытие. В этом случае b_i = k.

6.4.5. Транспортная задача

Это еще одна типичная и очень важная задача линейного программирования.

Постановка задачи. В n пунктах отправления (склады, заводы и т.п.) A1, A2,.., An имеется (или производится) некоторый однородный продукт в количествах a1, a2,.., an. Необходимо доставить этот продукт в m пунктов назначения B1, B2,.., Bm в количествах b1, b2,.., bm. Стоимость перевозки единицы груза из пункта Ai в пункт Bj равна cij. Заметим, что стоимость – это условное понятие, которое может означать расстояние, тариф, расход топлива, время и т.д. Количество перевозимого груза из пункта Ai в пункт Bj обозначим через xij (i=1,2,..,n; j=1,2,..,m). Задача заключается в определении таких величин xij , при которых стоимость перевозок будет минимальной.

Условия задачи можно записать компактно в виде таблицы (двойной матрицы):

Таблица

B j Ai	b1	b2	…	bm
a1	c11 x11	c12 x12	…..	c1m x1m
a2	c21 x21	c22 x22	…..	c2m x2m
…	…	…	…	….
an	cn1 xn1	cn2 xn2	…	cnm xnm

Cовокупность чисел x_ij, т.е. матрицу Х = [x_ij] будем называть матрицей перевозок или планом перевозки, а матрицу С=[c_ij] – матрицей транспортных издержек (затрат).

Сформулируем математическую модель транспорт-ной задачи.

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

План является допустимым, если числа x_ij удовлетворяют следующим естественным ограничениям:

Поскольку грузы предполагается перевозить только в одном направлении – из пунктов отправления в пункты назначения, то на переменные накладываются условия неотрицательности переменных:

в которых первые m равенств означают, что из каждого пункта производства A_i вывозится весь произведенный продукт. Последние n равенства означают, что каждый пункт потребления полностью удовлетворяется.

Транспортную задачу в приведенной формулировке (6.26) – 6.28) называют закрытой (или замкнутой) транспортной задачей, в отличие от открытой, в которой

• Пример 6.8. Построить математическую модель транспортной задачи.

На трех цементных заводах производится цемент одной и той же марки в количествах соответственно 100, 130, 170 тонн. Цемент следует доставить на четыре ЖБК, потребляющих его соответственно в количествах 150, 120, 80, 50 тонн. Стоимости (у.е.) перевозок одной тонны продукта с i-го (i=1,2,3) завода на j-й (j=1,2,3,4) ЖБК приведены в табл.

Спланировать перевозки так, чтобы их стоимость была минимальной.

Проектные параметры: x_ij–количество (т) продукта, перевозимого с i-го (i=1,2,3) завода на j-й (j=1,2,3,4) ЖБК.

Условия задачи записываем в виде таблицы.

Цемент-ные заводы	Стоимость перевозки (у.е.) Количество . перевозимого продукта (т)				Объем производ-ства (т)
	ЖБК-1	ЖБК-2	ЖБК-3	ЖБК-4
№1	3 x11	5 x12	7 x13	11 x14	100
№2	1 x21	4 x22	6 x23	3 x24	130
№3	5 x31	8 x32	12 x33	7 x34	170
Объем потребления	150	120	80	50

Тогда целевая функция (общая стоимость перевозок) имеет вид:

Z_min =3x₁₁+5x₁₂+7х₁₃+11х₁₄+x₂₁+4x₂₂+6x₂₃+3x₂₄+5x₃₁+8x₃₂+12x₃₃+7x₃₄.

Ограничения записываем из условия, что вывозится весь произведенный на каждом заводе цемент (первые три) и что каждый ЖБК полностью обеспечивается цементом:

x₁₁ +x₁₂ +х₁₃+х₁₄=150,

x₂₁ +x₂₂ +x₂₃+x₂₄=130,

x₃₁ +x₃₂.+x₃₃+x₃₄=170,

x₁₁ +x₂₁ +х₃₁=150,

x₁₂ +x₂₂ +x₃₂=120,

x₁₃ +x₂₃.+x₃₃=80,

x₁₄ +x₂₄.+x₃₄=50,

x_ij0 (i=1,2,3; j=1,2,3,4).

Решение данной транспортной задачи с использованием приложения Microsoft Excel приведено в подразделе 6.5.