Лекции по ТПР - файл Лекция№7-тпр.doc
скачать (681.7 kb.)
Доступные файлы (18):
| Лекция№01-тпр.doc | 38kb. | 12.11.2008 13:15 | скачать |
| Лекция№02-тпр.doc | 97kb. | 12.11.2008 13:25 | скачать |
| Лекция№03-тпр.doc | 179kb. | 12.09.2004 22:30 | скачать |
| Лекция№04-тпр.doc | 146kb. | 12.09.2004 22:31 | скачать |
| Лекция№05-тпр.doc | 131kb. | 12.09.2004 22:32 | скачать |
| Лекция№06-тпр.doc | 248kb. | 12.09.2004 22:33 | скачать |
| Лекция№09.doc | 177kb. | 03.10.2006 21:09 | скачать |
| Лекция№10-тпр.doc | 179kb. | 12.09.2004 22:49 | скачать |
| Лекция№11-тпр.doc | 353kb. | 25.11.2005 11:46 | скачать |
| Лекция№12-тпр.doc | 205kb. | 12.09.2004 22:53 | скачать |
| Лекция№13-тпр.doc | 191kb. | 12.09.2004 22:54 | скачать |
| Лекция№14-тпр.doc | 83kb. | 14.12.2004 14:25 | скачать |
| Лекция№15-тпр.doc | 301kb. | 12.09.2004 23:02 | скачать |
| Лекция№16-тпр.doc | 131kb. | 12.09.2004 23:04 | скачать |
| Лекция№17-тпр.doc | 542kb. | 12.09.2004 23:03 | скачать |
| Лекция№7-тпр.doc | 142kb. | 12.09.2004 22:38 | скачать |
| Лекция№8-тпр.doc | 93kb. | 12.09.2004 22:44 | скачать |
| Лекция№9-тпр.doc | 142kb. | 12.09.2004 22:47 | скачать |
Лекция№7-тпр.doc
Лекция №7.Задача о замене оборудования.
Ценность рассмотренных ранее задач состоит не только в их важном прикладном значении, но и в том, что многие другие реальные задачи, содержательно совершенно не связанные с условиями перечисленных задач, имеют аналогичные ММ и могут быть решены наиболее эффективными методами.
Пример такого типа задачи –
Задача о замене оборудования.
Пусть промышленное предприятие функционирует в течение некоторых промежутков времени с номерами
. Для выполнения производственной программы предприятие арендует необходимое оборудование. Через какие-то промежутки времени оборудование заменяется на новое. Если оборудование эксплуатируется в промежутке времени (i, j), т.е. начинается эксплуатация в начале i-того периода и заменяется в начале j-того промежутка времени, то предприятие несет затраты 
(на аренду, тех. обслуживание, ремонт и т.п.).Необходимо определить, в начале каких промежутков времени нужно заменять оборудование, чтобы суммарные затраты в течение рассматриваемых промежутков времени были бы минимальны.
В
севозможные случаи замены оборудования можно изобразить с помощью ориентированного графа:Здесь узлы графа соответствуют номерам начала периодов. Если оборудование эксплуатируется в течение промежутка (i, j), то на графе ставится соответствующая дуга, взвешенная числом
. Оборудование арендуется в начале 1-го периода, а процесс функционирования предприятия завершается в начале периода времени n.Допустим, в процессе эксплуатации оборудование заменяется при i=2 и i=7, т.е. оборудование заменяется в начале первого, второго и седьмого периодов:
и эксплуатируется до узла n. Тогда, очевидно, общая сумма затрат будет равна
. А это выражение есть ни что иное, как длина пути (1,2,7,n).Таким, образом, каждому варианту замены оборудования можно поставить в соответствие некоторый путь из узла 1 в узел n. Т.е. множество вариантов замены оборудования отражается множеством путей на рассматриваемом графе. Следовательно, задача оптимального плана замены оборудования эквивалентна задаче поиска кратчайшего пути из узла 1 в узел n на рассматриваемой сети. (Предложить студентам записать ММ самостоятельно.)^
Рассматривается функционирование предприятия в условиях сурового климата, его производственная программа может быть связана дополнительно с сезонностью. В таких условиях предприятию невыгодно создавать постоянные производственные коллективы и соответствующую социально-экономическую инфраструктуру.
Пусть рассматривается функционирование предприятия в течение n-1 промежутка времени, причем известно потребное количество бригад рабочих Rk (
) для выполнения производственной программы в течение к-того промежутка времени (периода). Если одна бригада рабочих на7имается в начале i-того промежутка и увольняется в начале j-того, т.е. используется в интервале (i,j), то затраты на содержание этой бригады равны .Необходимо найти план найма и увольнения бригад, при котором в каждом промежутке времени должен выполняться заданный объем работ, а суммарные затраты на содержание бригад минимальны.
В
севозможные варианты найма и увольнения бригад можно изобразить в виде сети, в которой дуга (i,j) означает найм в начале i-того и увольнение в начале j-того периода.Построение ММ.
Пусть
- количество бригад, нанимаемых в начале i-того и увольняемых в начале j-того промежутков. Тогда ММ запишется:
(1)
(2)
, 
(3)
(4)
-целые (5)В модели целевая функция (1) отражает суммарные затраты на содержание рабочих бригад. Ограничение (2) требует, чтобы в первом промежутке времени было ровно столько бригад, сколько требуется для выполнения работ на первом промежутке времени. Неравенство (3) допускает целесообразность содержания резервных бригад, т.к. они могут в конечном счете обойтись дешевле. Равенство (4) обеспечивает в последнем промежутке наличие ровно стольких бригад, сколько требуется. Условие (5) вытекает из физического смысла.
Модель (1)-(5) относится к классу задач линейного целочисленного программирования. Однако она тождественными преобразованиями сводится к модели транспортной задачи в сетевой постановке.
Неравенство (3) приводится к равенству введением доп. переменных:
, (6)
, (7)Идея последующих тождественных преобразований заключается в следующем: из уравнений (7) и (4) соответственно вычитаем уравнения (2) и (7), записанные для участка с номером на единицу меньше. Запишем уравнение (7) для участка с номером к-1:
, (8)Далее, вычтем (8) из (7):
Заметим:
, и 
=
Тогда:
.Проведя сокращения, можно записать:
, 
(9)Если вычесть из уравнения (7) с номером к=2 уравнение (2), то получим:
, 
(10)Теперь из уравнения (4) вычтем уравнение (7) с номером
. Т.к. уравнение (4) аналогично (7) при 
и 
, то результат вычитания следует из формулы (9) при :
, (11)К полученной системе уравнений (9)-(11) присоединим уравнения (2) и (4), умножив (4) слева и с права на –1:
, 
(12)
, 
(13)Полученные уравнения (9)-(13) эквивалентны уравнениям исходной задачи, которая теперь свелась к задаче (1), (9)-(13) с условиями
, -целые Далее можно условно интерпретировать:
- объем перевозки по дуге (i,j).R1- запас продукции в первом узле,
Rк- Rк-1 – запас продукции k-того узла
,Rn-1 - запас продукции n-ого узла.
Тогда уравнение (12) интерпретируется как объем вывоза из первого узла, равный запасу продукции в этом узле, т.е. аналогично уравнению для истока транспортной сети. Уравнение (13) интерпретируется как объем продукции, привозимой в размере потребности в узел n, т.е. аналогичное уравнению для стока транспортной сети.
Рассмотрим уравнение (10):
- определяет объем продукции, вывозимый из узла 2,
- объем продукции, ввозимый в узел 2 по дуге (1,2).В сеть вводится дополнительная дуга (3,2), по которой перевозится продукция в объеме
. Тогда 
- суммарный объем продукции, привозимой в узел 2. Следовательно уравнение (10) можно интерпретировать как уравнение баланса для промежуточных узлов транспортной задачи в сетевой постановке.Аналогично в сеть добавляются дуги (k,k-1) для всех
с объемами перевозок 
. 
Тогда уравнения (9) интерпретируются как уравнения баланса для промежуточных пунктов ТЗ в сетевой постановке: суммарный объем вывозимой продукции минус суммарный объем ввозимой продукции равняется запасу продукции в этих узлах.
Таким образом, задача календарного планирования трудовых ресурсов (1)-(5) тождественными преобразованиями и добавлением новых дуг свелась к модели транспортной задачи в сетевой постановке (1), (9)-(13).