КОНТРОЛЬНАЯРАБОТА
по дисциплине
« ОПТИМИЗАЦИЯОРГАНИЗАЦИОННЫХ РЕШЕНИЙ»
Задание №1
Решение задачиоб оптимальном направлении капиталовложений в строительную отрасль иоптимизации поставки строительных грузов
Определитьнаиболее экономичный вариант прироста мощности (строительства илиреконструкции) и одновременно рассчитать оптимальный план перевозокстроительной продукции до потребителя.
/>
Решение
Составимбазисные планы:
а) методсеверо-западного угла
/>
Значение целевойфункции:
L1 =160 х 15 + 20 х 3 + 60 х 10 + 180 х 5 + 40 х 16 + 40 х 0 =
= 2 400 + 60 + 600+ 900 + 640 + 0 = 4 600 у. е.
б) методдвойного предпочтения
/>
Значение целевойфункции:
L2 = 180х 3 + 160 х 3 + 60 х 5 + 20 х 0 + 40 х 5 + 20 х 13 + 20 х 0 =
= 540 + 480 + 300+ 0 + 200 + 260 + 0 = 1 780 у. е.
в) методаппроксимации Фогеля
/>
Значение целевойфункции:
L3 = 160х 3 + 180 х 3 + 20 х 10 + 60 х 5 + 40 х 5 + 40 х 0 =
= 480 + 540 + 200+ 300 + 200 + 0 = 1 720 у. е.
Проведемпроверку матрицы на вырождение:
N – число занятыхклеток матрицы, N = 6.
N= m+ n – 1 = 4 + 4 – 1= 7.
6 ≠ 7.
Следовательно,матрица – вырожденная, поэтому в одну из свободных ячеек в зоне вырождениявводим условную нулевую поставку груза.
/>
Оптимальный планнаходим на основании базисного плана, построенного методом аппроксимацииФогеля, так как этот план имеет минимальную целевую функцию.
Проверим матрицуна оптимальность с помощью потенциалов строк u и столбцов v.
Потенциалыопределим по занятым клеткам матрицы, тем самым соблюдая условие оптимальности(cij = uij+ vij).
/>
Произведемпроверку свободных клеток базисного плана на оптимальность.Коды свободных клеток
Δ = cij – (vij + uij) Примечание A-I 15 – (1 + 0) = 15 >0 A-II 18 – (8 + 0) = 10 >0 A-IV 0 – (-2 + 0) = 2 >0 B-I 12 – (1 – 3) = 14 >0 B-III 16 – (3 – 3) = 16 >0 B-IV 0 – (-2 + 2) = 0 =0 Г-I 17 – (1 + 2) = 14 >0 Г-II 13 – (8 + 2) = 3 >0 Г-III 15 – (3 + 2) = 10 >0
В данном случаевсе значения Δ ≥ 0, следовательно,составленный план неоптимален, переходим к улучшенному плану перевозок. В этомслучае среди незагруженных клеток, для которых Δ ≥ 0,находим клетку с наибольшей величиной превышения стоимости (B-III).
Строим замкнутыйконтур, начиная перемещаться из потенциальной клетки.
/>
Контурраспределения:
/>
Составим новыйплан распределения.
/>
Его целеваяфункция:
L4 =160 х 3 + 180 х 3 + 60 х 10 + 20 х 5 + 40 х 16 + 40 х 0 =
= 480 + 540 + 600+ 100 + 640 + 0 = 2 360 у. е.
Проверяемполученную матрицу на оптимальность.Коды свободных клеток
Δ = cij – (vij + uij) Примечание A-I 15 – (1 + 0) = 15 >0 A-II 18 – (8 + 0) = 10 >0 A-IV 0 – (-2 + 0) = 2 >0 B-I 12 – (1 – 3) = 14 >0 B-II 5 – (8 + 13) = -16 0 Г-II 13 – (8 + 2) = 3 >0 Г-III 15 – (3 + 2) = 10 >0
Наибольшеепревышение стоимости наблюдаем в клетке А-I.
/>
Контурраспределения:
/>
Новый планраспределения:
/>
Его целеваяфункция:
L4 =160 х 15 + 20 х 3 + 60 х 10 + 180 х 5 + 40 х 16 + 40 х 0 =
= 2 400 + 60 +600 + 900 + 640 + 0 = 4 600 у. е.
Проверяемполученную матрицу на оптимальность.Коды свободных клеток
Δ = cij – (vij + uij) Примечание A-II 18 – (22 + 0) = -4 0 Г-II 13 – (22 — 12) = 3 >0 Г-III 15 – (17 — 12) = 10 >0
Данный планраспределения продукции является наиболее эффективным из представленных, хотяне до конца оптимальным.
Вывод
Поскольку воптимальном плане прирост мощности 40 тыс. у. е. продукции за счетстроительства отнесен на фиктивного потребителя, то строительство нового цехаили пристройку цеха к действующему следует считать нецелесообразным, икапитальные вложения необходимо направить на реконструкцию действующегопредприятия.
Задание №2
Применениесимплекс-метода для оптимальной организации
ремонтно-строительныхработ
Определить максимальноеколичество квартир в домах кирпичных и крупнопанельных, которые можноотремонтировать из имеющихся ресурсов.
Ресурсы Потребность в ресурсах на одну квартиру Наименование Количество кирпичный дом панельный дом Арматура, т 900 0,6 1,3
Пиломатериалы, м3 520 0,8 0,3 Цемент, т 7 000 5 9 Керамическая плитка, тыс. шт. 400 0,5 --
Трудозатраты,
чел. дн. 55 000 70 50 /> /> /> /> />
Решение
Для решенияданной задачи применим симплекс-метод.
Обозначим:
Х1 – искомоеколичество квартир в кирпичном доме;
Х2 – искомоеколичество квартир в панельном доме.
Целевая функция:
L= Х1+ Х2/> max
Ограничениямибудут неравенства, полученные на основании исходных данных:
1. Арматура0,6Х1 + 1,3 Х2 ≤ 900;
2. Пиломатериалы0,8Х1 + 0,3 Х2 ≤ 520;
3. Цемент5Х1 + 9Х2 ≤ 7 000;
4. Керамическаяплитка 0,5Х1 ≤ 400;
5. Трудозатраты70Х1 + 50Х2 ≤ 55 000;
6. Х1≥ 0;
7. Х2≥ 0.
Посколькуимеется только два неизвестных, то применим геометрическое решение. Дляудобства построений преобразуем не равенства.
1. 6Х1+ 13 Х2 ≤ 9 000;
2. 8Х1+ 3 Х2 ≤ 5 200;
3. 5Х1+ 9Х2 ≤ 7 000;
4. 5Х1≤ 4 000;
5. 7Х1+ 5Х2 ≤ 5 500;
6. Х1≥ 0;
7. Х2≥ 0.
Геометрическиограничения неравенств выражаются в виде открытых полуплоскостей, ограниченныхосями координат и линиями, описываемыми равенствами, полученными из выраженийограничений:
1. 6Х1+ 13 Х2 = 9 000;
2. 8Х1+ 3 Х2 = 5 200;
3. 5Х1+ 9Х2 = 7 000;
4. 5Х1= 4 000;
5. 7Х1+ 5Х2 = 5 500.
Нанесем этилинии на график.
/>
В целом условиямнеравенств удовлетворяет заштрихованная область. Оптимальное решение находитсяна контуре этой фигуры в одной из узловых точек и определяется совместнымрассмотрением выражений:
L= Х1+ Х2/> max
6Х1 +13 Х2 = 9 000;
8Х1 +3 Х2 = 5 200;
5Х1 +9Х2 = 7 000;
5Х1 =4 000;
7Х1 +5Х2 = 5 500.
Возрастаниецелевой функции направлено слева вверх под углом 45°, и последней точкой вдопустимой области будет точка 1 или 2.
Точка 1 полученапересечением прямых, описываемых равенствами:
6Х1 +13 Х2 = 9 000;
7Х1 +5Х2 = 5 500.
Решая этиравенства, найдем координаты точки 1: Х1 = 200; Х2 = 600.
Аналогичнонайдем координаты точки 2 из выражений:
7Х1 +5Х2 = 5 500;
8Х1 +3 Х2 = 5 200.
Координаты точки2: Х1 = 498; Х2 = 406.
Найдем, какая изуказанных точек дает большее значение целевой функции.
L1= Х1+ Х2=200 + 600 = 800;
L2= Х1+ Х2=498 + 406 = 904.
Оптимальнойявляется точка 2, дающая 498 квартир в кирпичных домах и 406 в панельных. Приэтом будут полностью исчерпаны такие ресурсы как пиломатериалы и трудозатраты.
Использованиеостальных ресурсов найдем, решая вышеуказанные равенства при зафиксированныхзначениях Х1 = 498; Х2 = 406.
0,6 х 498 + 1,3х 406 = 299 + 528 = 827 (арматура), неиспользовано 73 т арматуры.
5 х 498 + 9 х406 = 2 490 + 3 654 = 6 144 (цемент), неиспользовано 856 т.
0,5 х 498 = 249тыс. шт. (керамическая плитка), неиспользовано 151 тыс. шт.
Полученныерезультаты занесем в таблицу:Ресурсы Количество ресурсов Наименование в наличии использованных неиспользованных Арматура, т 900 827 73
Пиломатериалы, м3 520 520 - Цемент, т 7 000 6 144 856 Керамическая плитка, тыс. шт. 400 249 151
Трудозатраты,
чел. дн. 55 000 55 000 -- /> /> /> /> />
Вывод: Максимальноеколичество домов, которые можно отремонтировать, используя данные ресурсы – 498шт. (кирпичные) и 406 шт. (панельные). При ремонте пиломатериалы и трудозатратыиспользуются полностью, остальные ресурсы – с остатком.
Задание №3
Применениеметодов динамического программирования
(принципаоптимальности Р. Беллмана)
при календарномпланировании в строительстве
Выбрать такуюочередность включения объектов в строительный поток, чтобы длина суммарногопути перебазирования оказалась минимальной.
Исходные данные– расстояние между пунктами, кмИндекс пунктов (объектов)
А0
А1
А2
А3
А4
А0 20 5 10 40
А1 20 10 25 30
А2 5 10 35 15
А3 10 25 35 50
А4 40 30 15 50
Составим таблицувариантов, состоящих лишь из трех участков перебазирования. Сгруппируем этиварианты по одинаковым объектам, стоящим на последнем месте.Вариант Суммарное расстояние, км Вариант Суммарное расстояние, км
А0А2 А3 А1
А0А3 А2 А1
5 + 35 + 25 = 65
10 + 35 + 25 = 70
А0А1 А2 А3
А0А2 А1 А3
20 + 10 + 35 = 65
5 + 10 + 25 = 40
А0А2 А4 А1
А0А4 А2 А1
5 + 15 + 30 = 50
40 + 15 + 10 = 65
А0А1 А4 А3
А0А4 А1 А3
20 + 30 + 50 = 100
40 + 30 + 25 = 95
А0А3 А4 А1
А0А4 А3 А1
10 + 50 + 30 = 90
40 + 50 + 25 = 115
А0А2 А4 А3
А0А4 А2 А3
5 + 15 + 50 = 70
40 + 15 + 35 = 90
А0А1 А3 А2
А0А3 А1 А2
20 + 25 + 35 = 80
10 + 25 + 10 = 45
А0А1 А2 А4
А0А2 А1 А4
20 + 10 + 15 = 45
5 + 10 + 30 = 45
А0А1 А4 А2
А0А4 А1 А2
20 + 30 + 15 = 65
40 + 30 + 10 = 80
А0А1 А3 А4
А0А3 А1 А4
20 + 25 + 50 = 95
10 + 25 + 30 = 65
А0А3 А4 А2
А0А4 А3 А2
10 + 50 + 15 = 75
40 + 50 + 35 = 125
А0А2 А3 А4
А0А3 А2 А4
5 + 35 + 50 = 90
10 + 35 + 15 = 60
Из каждой парывариантов выберем наиболее перспективные (с меньшим значением). Затем развиваеми сопоставляем лишь перспективные варианты.Вариант Суммарное расстояние, км Вариант Суммарное расстояние, км
А0А2 А3 А1 А4
А0А2 А4 А1 А3
А0А3 А4 А1 А2
А0А3 А1 А2 А4
А0А1 А4 А2 А3
А0А3 А4 А2 А1
65 + 30 = 95
50 + 25 = 75
90 + 10 = 100
45 + 15 = 60
65 + 35 = 110
75 + 10 = 85
А0А2 А1 А3 А4
А0А4 А1 А3 А2
А0А2 А4 А3 А1
А0А2 А1 А4 А3
А0А3 А1 А4 А2
А0А3 А2 А4 А1
40 + 50 = 90
95 + 35 = 130
70 + 25 = 95
45 + 50 = 95
65 + 15 = 80
60 + 30 = 90
Составляемтаблицу, в которую внесем перспективные варианты из предыдущей таблицы идобавим к каждому из них А0(возвращение мехколонны на исходнуюбазу).Вариант Суммарное расстояние, км
А0А2 А4 А1 А3 А0
А0А3 А1 А2 А4 А0
А0А3 А4 А2 А1 А0
А0А3 А1 А4 А2 А0
75 + 10 = 85
60 + 40 = 100
85 + 20 = 105
80 + 5 = 85
Таким образом,устанавливаем, что есть два равноценных оптимальных варианта последовательностистроительства объектов.
Задание №4
Оптимизацияочередности строительства объектов
в неритмичныхпотоках
Определитьоптимальную очередность строительства нескольких объектов, при которойдостигается минимальная общая продолжительность строительства, а также величинуобщей продолжительности строительства при исходной и оптимальной очередностистроительства объектов.
/>
Выделяем поток№3 как поток наибольшей продолжительности. Затем по каждому объекту находимобщее рабочее время, предшествующее потоку наибольшей продолжительности и общеерабочее время, последующее за потоком наибольшей продолжительности.
В третью строкупод матрицей записываем со своим знаком разницу между продолжительностью работына данном объекте последней и первой бригад.
/>
На основе данныхдополнительных строк устанавливается рациональная очередность строительстваобъектов из следующих соображений:
а) напервом месте располагается объект с наибольшим значением Σапос.Остальные объекты располагаются так, чтобы Σапрпостепенно возрастало, а Σапос снижалась к концуматрицы;
б) напервом месте располагается объект с наибольшим значением (аm— а1), на последнем –с минимальным значением (аm— а1); остальныеобъекты располагаются так, чтобы (аm— а1) изменялосьпостепенно от максимального значения к минимальному.
Принятаяочередность строительства объектов по п. а:
/>
Принятаяочередность строительства объектов по п. б:
/>
Найдем общуюпродолжительность строительства комплекса:
а) приисходной очередности объектов
Т1 =(8 + 8 + 5 + 0 + 4) + (6 + 5 + 4) + (5 + 4) = 49;
б) приочередности объектов 5-2-1-4-3
Т2 =(4 + 8 + 8 + 0 + 5) + (5 + 2 + 0) + (2 + 0) = 34;
в) приочередности объектов 4-5-3-2-1
Т3 =(0 + 4 + 5 + 8 + 8) + (2 + 1 + 9) + (1 + 9) = 47.
Наименьшуюпродолжительность имеет очередность объектов 5-2-1-4-3.
Задание №5
Оптимизация сетевогографика по рабочим ресурсам
и по срокамстроительства
Решитьоптимизационные задачи управления строительством по сетевым моделям.
/>
Тобщ= 45 дней
Данную сетевуюмодель можно оптимизировать. Для этого на критические пути увеличиваемколичество рабочих, снимая их с менее загруженных участков. Таким образом,сокращаются сроки выполнения работ.
/>
Тобщ.= 41 день