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

При планировании строительства производственных, социальных и др. объектов всегда стоит задача правильного их размещения, то есть возникает так называемая задача о покрытии. Эта задача является частным случаем рассмотренных выше задач о раскрое и планировании (в ней 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.

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

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

Постановка задачи. В 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 , при которых стоимость перевозок будет минимальной.

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

Таблица

Bj 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) называют закрытой (или замкнутой) транспортной задачей, в отличие от открытой, в которой

n Пример 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
№2	1 x21	4 x22	6 x23	3 x24
№3	5 x31	8 x32	12 x33	7 x34
Объем потребления

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

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.

6.4.6. Задача о назначениях (проблема выбора)

 

Постановка задачи.В распоряжении имеется n механизмов (бригад) и n различных видов работ. Производительность каждого механизма на различных работах, вообще говоря, различна. Обозначим через cij (i, j=1, 2,.., n) производительность i-го механизма на j-й работе. Матрица C=[cij] называется матрицей эффективностей или производительностей. Требуется так распределить n механизмов на n работах, чтобы каждый механизм выполнял одну и только одну работу и чтобы при заданной производительности каждого механизма на каждой из работ суммарный эффект был бы максимальным.

 

Эта задача является частным случаем транспортной задачи

Обозначим через x_ij переменную, равную единице, если i-ймеханизм назначен на j-ю работу, и равен нулю, если он на эту работу не назначен. В качестве целевой функции выбираем суммарную производительность всех механизмов

Ограничения записываем из условия, что каждый механизм выполняет одну работу и что каждая работа обеспечивается одним механизмом:

 

n Пример 6.9. Задача о назначениях.

Имеются три бригады В₁, В₂, В₃, каждая из которых может быть использована на каждой из 3-х строительной площадке с производительностью (в условных единицах), заданной в таблице.

Таблица.

Строител. площадка	Производительность бригад (у.е.)
В1	В2	В3

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

Обозначим x_ij=1, если на i-ю стройплощадку назначена j-я бригада, и x_ij=0, если она на эту стройплощадку не назначена.

В качестве функции цели возьмем суммарную производительность всех бригад:

Z_max =x₁₁ +2x₁₂ +3х₁₃+2x₂₁ +4x₂₂ +x₂₃+3x₃₁ +x₃₂.+5x₃₃.

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

⇐ Предыдущая9101112131415161718Следующая ⇒

Поделиться:

Популярное:

1. A. Оказание помощи при различных травмах и повреждениях.
2. A. особая форма восприятия и познания другого человека, основанная на формировании по отношению к нему устойчивого позитивного чувства
3. B. Принципы единогласия и компенсации
4. Cочетания кнопок при наборе текста
5. D-технология построения чертежа. Типовые объемные тела: призма, цилиндр, конус, сфера, тор, клин. Построение тел выдавливанием и вращением. Разрезы, сечения.
6. EP 3302 Экономика предприятия
7. Exercise 5: Образуйте сравнительные степени прилагательных.
8. H. Приглаживание волос, одергивание одежды и другие подобные жесты
9. I. «Движение при закрытой автоблокировке (по путевой записке).
10. I. Если глагол в главном предложении имеет форму настоящего или будущего времени, то в придаточном предложении может употребляться любое время, которое требуется по смыслу.
11. I. Запоры — основная причина стресса
12. I. Особенности учета в строительстве