Logo GenDocs.ru


Поиск по сайту:  


Лекции по ТПР - файл Лекция№7-тпр.doc


Лекции по ТПР
скачать (681.7 kb.)

Доступные файлы (18):

Лекция№01-тпр.doc38kb.12.11.2008 13:15скачать
Лекция№02-тпр.doc97kb.12.11.2008 13:25скачать
Лекция№03-тпр.doc179kb.12.09.2004 22:30скачать
Лекция№04-тпр.doc146kb.12.09.2004 22:31скачать
Лекция№05-тпр.doc131kb.12.09.2004 22:32скачать
Лекция№06-тпр.doc248kb.12.09.2004 22:33скачать
Лекция№09.doc177kb.03.10.2006 21:09скачать
Лекция№10-тпр.doc179kb.12.09.2004 22:49скачать
Лекция№11-тпр.doc353kb.25.11.2005 11:46скачать
Лекция№12-тпр.doc205kb.12.09.2004 22:53скачать
Лекция№13-тпр.doc191kb.12.09.2004 22:54скачать
Лекция№14-тпр.doc83kb.14.12.2004 14:25скачать
Лекция№15-тпр.doc301kb.12.09.2004 23:02скачать
Лекция№16-тпр.doc131kb.12.09.2004 23:04скачать
Лекция№17-тпр.doc542kb.12.09.2004 23:03скачать
Лекция№7-тпр.doc142kb.12.09.2004 22:38скачать
Лекция№8-тпр.doc93kb.12.09.2004 22:44скачать
Лекция№9-тпр.doc142kb.12.09.2004 22:47скачать

Лекция№7-тпр.doc

Реклама MarketGid:
Лекция №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).
Реклама:





Скачать файл (681.7 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru