Решение оптимизационных задач в управлении строительным производством

 

1.Рациональное распределение трудовых ресурсов в строительных сетях


1.1Задача о назначениях


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

Обозначения:

сij - показатель эффективности назначения i-го рабочего на j-й работе, например издержки выполнения i-м рабочим j-й работы;

xij - переменная модели (хij = 1, если i-й рабочий используется на j-й работе, и xij = 0 в противном случае).

Модель задачи о назначениях:



Здесь:

(1) - целевая функция (минимум издержек на выполнение всех работ);

(2) - система ограничений, отражающая следующие условия:

а) каждая работа должна быть выполнена одним рабочим;

б) каждый рабочий может быть привлечен к одной работе;

(3) - условия неотрицательности переменных.

Оптимальный план задачи о назначениях (1) - (3) можно представить в виде квадратной матрицы назначений, в каждой строке и в каждом столбце которой находится ровно одна единица. Такую матрицу иногда называют матрицей перестановок. Значение целевой функции (1), соответствующее оптимальному плану, называют эффективностью назначений.

Исходные данные:

На предприятии ООО «Металлист» имеется 5 рабочих каждый из которых может выполнять 5 различных операций по обработке деталей. Известна затраты времени каждого рабочего при выполнении каждой операции, заданная матрицей (табл. 1.1.1):


Таблица 1.1.1

12345192596287534343884456792552834

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

Шаг 1. Сначала приводим матрицу по строкам, т.е. находим наименьшее значение в каждой строке и вычитаем эти минимальные значения из соответствующих строк (табл. 1.1.2).


Таблица 1.1.2

1234519259622875343343884345679225528342

Затем приводим матрицу по столбцам (табл. 1.1.3).

Таблица 1.1.3

1234517037425420131055143457053061210200

Имеем:

Так как решение не получается, то переходим ко второму этапу.

Проводим под прямым углом прямые таким образом, чтобы исключить все нули. В не вычеркнутых элементах наименьший - Вычитаем этот элемент из каждого не вычеркнутого элемента прибавляем к каждому элементу, стоящему на пересечении проведенных прямых. Переходим к таблице 1.1.4 и 1.1.5.


Таблица 1.1.4

12345170374254201310551434570530612

Таблица 1.1.5

12345160263255201300440435570520501Проводим операцию повторно и переходим к таблице 1.1.6 и 1.1.7.


Таблица 1.1.5

12345160263255201300440435570520501


Таблица 1.1.6

12345140063235001302462415370500301

Таблица 1.1.7

12345140063235001302462415370500301

Данные таблицы (1.7 и 1.8) соответствует оптимальному назначению (1,2), (2,3), (3,1), (4,5) и (5,4) или (1,3), (2,4), (3,1), (4,5) и (5,2). Соответствующие суммарные затраты:


z=++=12+3+1=16 ед. времени.

В таблице 1.1.7 и 1.1.8 находим суммарные затраты времени по клеткам (1,2), (2,3), (3,1), (4,5) и (5,4) и (1,3), (2,4), (3,1), (4,5) и (5,2)

z=2+5+4+2+3=16=5+3+4+2+2,

т.е. результаты совпали.

Ответ: минимальные затраты времени будут составлять 16 ед. времени.


1.2Оптимальное распределение рабочих по захваткам


Пусть имеется n видов работ и несколько специализированных бригад рабочих. Необходимо распределить рабочих между отдельными видами работ таким путем, чтобы в строительный поток включить максимальное количество рабочих. Такая задача близка к транспортной. В научной литературе она известна как задача о максимальном потоке в матричной постановке или задача назначения (выбора). Рассмотрим постановку задачи в общем виде. Пусть заданы количества единиц ресурса а: ,,, направляемые в пункты назначения, в которых потребности b: , , в этом ресурсе. Отличительной особенностью этой задачи является закрепление каждого пункта отправления за некоторыми пунктами назначения. Итак, имеется матрица , в которой

, если нельзя перевозить ресурс из i-го пункт отправления в j-пункт назначения, 0, если перевозка возможна.

Задача составляется в составлении плана перевозок максимального количества ресурса.

Такой план определяется числами (i=1, m, j=1, n);.

Если =0, то =0, т.е. нельзя перевозить ресурс из i-го пункта отправления в j-ый пункт назначения.

При этом должны соблюдаться условия:

1, i=1, m, то есть из i-го пункта отправления вывозится ресурс не более чем .

2, j=1, n, то есть в j-ый пункт назначения можно ввести не больше потребности -го ресурса.

При этом количество перевозимого ресурса


Ф=max.


Исходные данные:

На строительном объекте имеется 4 вида работ и 4 групп рабочих. Рабочие каждой группы выполняют одни и те же работы. Необходимо, чтобы работы выполняло максимальное количество рабочих. Условия задачи приведены в таблице 1.2.1, в столбцах которой указано требуемое количество рабочих для выполнения соответствующей работы, а строки отдельные виды рабочих. В клетках таблицы приведены нули, если рабочий i-ой группы может выполнять j-ю работу, и единицы, если рабочие i-ой группы не могут выполнять j-ю работу.


Таблица 1.2.1

123414537262853479642354

Помножаем каждый элемент матрицы на -1 и прибавляем 10. Переходим к таблице 1.2.2.


123416573248253631448756Преобразовываем матрицу по строкам. Переходим к таблице 1.2. 3,1.2.4, 1.2.5 и 1.2.6


Таблица 1.2.3

1234165733248252363141487565

Таблица 1.2.4

123413240226033520343201

Таблица 1.2.5

123413240226033520343201

Таблица 1.2.6

123413250215023410242100

Проводим под прямым углом прямые таким образом, чтобы исключить все нули. В не вычеркнутых элементах наименьший - Вычитаем этот элемент из каждого не вычеркнутого элемента прибавляем к каждому элементу, стоящему на пересечении проведенных прямых. Проводим повторно операцию до конечного результата. Переходим к таблице 1.2.7 и 1.2.8.


Таблица 1.2.7

123413260204013300142110

Таблица 1.2.8

123412160204123301241010

Таблица 1.2.9

123411150205233200240000

Таблица 1.2.10

123411150205233200240000

Ответ: На первый станок отправляем 2-го рабочего, на 2-й станок 3-его или 4-го рабочего; на 3-й станок 4-го или 3-его рабочего; на 4-й станок 1-го рабочего.

1.3 Транспортная задача (метод Фогеля)


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



Общее предложение равно общему спросу:



Таблица 1.3.1

j12345i36232634201321315211172172221353813319102128242843125192229175401817334125

Таблица 1.3.2

j12345i372326342012345678913213152111 3274--------2182221353813 1888888----31910 19212824 281111-------4312519 122 2629 217 2222222619-54018 1817 223341251111111171713211342826543421194442-94542--4672--8772---8-2---9-17---

Шаг первый: Находим в строчках минимальные два числа и вычитаем из большего меньшее. Останавливаемся на той строке, где разность будет больше. Аналогично проводим эту операции и со столбцами.

Шаг второй: выбираем столбец 4, где разность равна 13. Направляем максимальный поток в клетку .

Шаг третий: вычеркиваем строку 1.

Проводим повторно операции без учета клеток 1-ой строки до получения конечного результата.


Ответ: груз направляют по оптимальному маршруту с грузооборотом 2157 ткм.


Вводные данные:


Таблица 1.3.3

j12345i28424327201411315211172292221353813333102128242842725192229175301817334125

Таблица 1.3.4

j12345i284243272012345678910141131521 1411 277468886212121-2292221 935 3813 20888814-----33310 2821 328 224281111777728---427251922 2729172222332222--5301817 30334125118-------13211342321-43-21-44-41-65-41--6-41--7--1--8--21--9--21--Шаг первый: Находим в строчках минимальные два числа и вычитаем из большего меньшее. Останавливаемся на той строке, где разность будет больше. Аналогично проводим эту операции и со столбцами.

Шаг второй: выбираем столбец 4, где разность равна 13. Направляем максимальный поток в клетку .

Шаг третий: вычеркиваем столбец 4.

Проводим повторно операции без учета клеток 4-го столбца до получения конечного результата.



Ответ: груз направляют по оптимальному маршруту с грузооборотом 2543 ткм.

Определение минимальной продолжительности работ с использованием алгоритм Джонсона-Афанасьева и многошаговых процессов принятия решений (метод динамического программирования).


Таблица 1.4.1

ABCD15472293643758344621

max A {10; 14; 13}=14B {0; - 1; - 3}=0C {11; 15; 14}=15

T=14+0+15+10=39 у. е.

Продолжительность выполнения комплексов потоков равна T=39 у. е.

Шаг 1:

На место первой строки устанавливаем первую строку исходной матрицы. Незафиксированные работы переформируются в оптимальные очередности по алгоритму Джонсона и пересчитывается продолжительность выполнения комплекса работ.


Таблица 1.4.2

ABCD15472375588344662212933664

max A {8; 7; 10}=10

max B {2; 0; 1}=2

max C {13; 12; 17}=17

T=10+2+17+10=39 у. е.

Продолжительность выполнения комплексов потоков равна Т=39 у.е.

На место первой строки устанавливаем вторую строку исходной матрицы. Незафиксированные работы переформируются в оптимальные очередности по алгоритму Джонсона и пересчитывается продолжительность выполнения комплекса работ.


Таблица 1.4.3

ABCD29364375588344662211544772

max A {13; 12; 11}=13B {2; 0; 2}=2

max C {10; 9; 15}=15

T=13+2+15+10=40 у. е.

Продолжительность выполнения комплексов потоков равна Т=40 у. е.

На место первой строки устанавливаем третью строку исходной матрицы. Незафиксированные работы переформируются в оптимальные очередности по алгоритму Джонсона и пересчитывается продолжительность выполнения комплекса работ.


Таблица 1.4.4

ABCD37583154477244662212933664

max A {7; 7; 10}=10B {1; 0; 1}=1

max C {11; 12; 17}=17

T=10+1+17+10=38 у. е.

Продолжительность выполнения комплексов потоков равна Т=38 у. е.

На место первой строки устанавливаем четвертую строку исходной матрицы. Незафиксированные работы переформируются в оптимальные очередности по алгоритму Джонсона и пересчитывается продолжительность выполнения комплекса работ.


Таблица 1.4.5

ABCD44621154477237583372933664

max A {3; 4; 10}=10B {8; 6; 1}=8

max C {8; 14; 17}=17

T=10+8+17+10=45 у. е.

Продолжительность выполнения комплексов потоков равна Т=45 у.е.

После подсчета продолжительности выполнения комплекса работ определяем матрицу с минимальной продолжительностью. Это матрица М3 (таб. 1.4.4.) она подлежит дальнейшему ветвлению. Итак, на месте первой строки фиксируется выявленная на первом шаге расчета третья строка исходной матрицы, а на место второй строки поочередно устанавливаем 1,2,4 строки и вычисляем продолжительность выполнения комплекса работ.

Шаг 2:

1На место второй строки устанавливается первая строка исходной матрицы. Незафиксированные работы переформируются в оптимальные очередности по алгоритму Джонсона и пересчитывается продолжительность выполнения комплекса работ.


Таблица 1.4.6

ABCD37583154477244662212933664

max A {7; 7; 10}=10B {1; 0; 1}=1

max C {11; 12; 17}=17

T=10+1+17+10=38 у. е.

Продолжительность выполнения комплексов потоков равна Т=38 у.е.

2На место второй строки устанавливается вторая строка исходной матрицы. Незафиксированные работы переформируются в оптимальные очередности по алгоритму Джонсона и пересчитывается продолжительность выполнения комплекса работ.


Таблица 1.4.7

ABCD37583293366444662211544772

max A {11; 12; 11}=12B {0; 0; 2}=2

max C {11; 915}=15

T=12+2+15+10=39 у. е.

Продолжительность выполнения комплексов потоков равна Т=39 у.е.

На место второй строки устанавливается четвертая строка исходной матрицы. Незафиксированные работы переформируются в оптимальные очередности по алгоритму Джонсона и пересчитывается продолжительность выполнения комплекса работ.


Таблица 1.4.8

ABCD37583446622129336641544772

max A {6; 9; 11}=11B {3; 4; 2}=4

max C {7; 12; 15}=15

T=11+4+15+10=40 у. е.

Продолжительность выполнения комплексов потоков равна Т=40 у. е.

Шаг 3:

Рассмотрим матрицу М3142


Таблица 1.4.6

ABCD37583446212936415472

max A {7; 7; 10}=10B {1; 0; 1}=1

max C {11; 12; 17}=17

T=10+1+17+10=38 у. е.

Продолжительность выполнения комплексов потоков равна Т=38 у. е.

Оптимальной очередностью при минимальном значении продолжительности строительства (Т=38 у.е.) является очередность строительства объектов 3,4,2,1. В результате решения задачи продолжительность выполнения комплекса работ была снижена на 1.


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


2.1 Метод северо-западного угла


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

Шаг 1:

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


Таблица 2.1.1

j12345i362326342013213 321521117V21722 421 13353813V3191021 1028 92428V431251922 1729 1417V54018173341 2025 20VVVVVV

Направляем в первую клетку максимальный поток грузов (, закрываем строку 1. В клетку ( направляем 4 и тем самым закрываем столбец. Аналогично проводим такие же операции с другими стоками и столбцами и закрываем их. Таким образом, сумма затрат равна:


Ответ: при использовании диагонального (северо-западного угла) метода, сумма затрат составила 3339 ткм.


Таблица 2.1.2

j12345i284243272014113 2815 1321117V2292221 2935 03813V333102128 332428V427251922 1029 1717V53018173341 1025 20VVVVVV

Аналогично проводим те же операции, что и в первом примере. «0» - дефективная (пустая) перевозка.

Таким образом, сумма затрат равна:



Ответ: при использовании диагонального (северо-западного угла) метода, сумма затрат составила ткм.


2.2 Метод минимума элемента по строке


При использовании данного метода явление выраженности не наблюдается. Смысл данного метода заключается в направлении максимального потока в минимальный элемент строки.

Выбираем в первой строке минимальный элемент ( и направляем максимальный поток 20, закрываем столбец 5. Так как строка еще не закрыта, то в клетку с минимальным элементом 11, направляем максимальный поток (. Закрываем первую строчку и переходим ко второй строке. Аналогичные операции проводим с оставшимися строчками до получения конечного результата (таблица 2.2.1).


Таблица 2.2.1

j12345i362326342013213152111 127 20V2172221 17353813V31910 1921282428V4312519 622 252917V54018 171733 141 2225V

Таким образом, сумма затрат равна:



Ответ: при использовании метода минимального элемента по строке, сумма затрат составила


Таблица 2.2.2

j12345i284243272014113152111 217 20V2292221 2935 3813V33310 2821 528 2428V4272519 822 192917V530181733 2441 625V

Таким образом, сумма затрат равна:



Ответ: при использовании метода минимального элемента по строке, сумма затрат составила


Список источников


1Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения: Учеб. пособие. - М.: ИНФА-М, 2003. - 444 с.

2Вагнер Г. Основы исследования операций. Т.1-3. - М.: Мир, 1973. - 632 с.

3Васильев Ф.П. Иваницкий А.Ю. Линейное программирование. - М.: Факториал Пресс. 2003. - 352 с.

Васин А.А. Морозов В.В. Теория игр и модели математической экономики (учебное пособие). - М.: МАКС Пресс, 2005 г. - 272 с.

Вентцель Е.С. Исследование операций. Задачи, принципы, методология. Учебное пособие для вузов. Изд-во: Дрофа, 2006 г.

Данилов Н.Н. Курс математической экономики. Новосибирск. Изд-во СО РАН, 2002. - 444 с.

7Интрилигатор М. Математические методы оптимизации и экономическая теория. Изд-во: Айрис-Пресс, 2002 г. - 576 с.

8Коробов П.Н. Математическое программирование и моделирование экономических процессов. Изд-во: ДНК, 2003 г.-555 с.

9Кремер Н.Ш., Путко Б.А., Тришин И.М. и др. Исследование операций в экономике. Учебное пособие для вузов. Изд-во: Юнити, 2005 г. - 407 с.

10Кузнецов Б.Т. Математические методы и модели исследования операций. Изд-во: Юнити-Дана, 2005 г. - 462 с.

Летова Т.А., Пантелеев А.В. Методы оптимизации в примерах и задачах. Учебное пособие. 2-е изд., испр. Изд-во: Высшая школа. 2005 г., 544 с.

12Основы математики и ее приложения в экономическом образовании: Учебник. - 4-е изд., испр. - М.: Дело, 2003. - 688 с.

13Печерский С.Л. Яновская Е.Б. Кооперативные игры: решения и аксиомы. СПб.: Изд-во Европейского ун-та в Санкт-Петербурге, 2004. - 459 с.

14Протасов И.Д. Теория игр и исследование операций. Изд-во: Гелиос АРВ, 2006 г. 368 с.

Розен В.В. Математические модели принятия решений в экономике. Изд-ва: Университет, Высшая школа, 2002 г., 288 с.

строительный фогель транспортный ресурс


1.Рациональное распределение трудовых ресурсов в строительных сетях 1.1Задача о назначениях При рассмотрении задачи о назначениях в стандартной фо

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ