Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 8
Текст из файла (страница 8)
Предположим, что для каждого периода 1 известен минимальный спрос Р! на рабочую силу. Пусть хп — число людей, нанятых на,работу в начале Вго периода и уволенных в конце !' — 1-го периода, а с!! — затраты на одного рабочего .из числа хеь Тогда число людей, работающих в 1-й период, равно ! Е Е хв1, или л. л х,!. Если избыток рабочей силы на период ( гас!)! 1! Н! обозначить через зь то задача календарного планирования трудовых ресурсов на и — 1 периодов заключается в нахождении неотрицательных целых чисел хп и з1, минимизирующих функ- ционал 39 Детерминированные потоки в сетях Вычитая (2.15) из (2.16), (2.16) из (2.17) и добавляя избыточное условие, полученное умножением обеих частей уравнения (2.17) на — 1, мы получаем следующую систему уравнений: хм+ ха в+ хге — зх = 1т„ — х, +х +ха +   — хтз — хзз +хм +зз — зз — — Рз — 17з, хы хы хы +аз = ~з Нетрудно видеть, что каждая переменная входит в полученные уравнения дважды — один раз с коэффициентом +! и один раз с коэффициентом — 1.
Такая структура коэффициентов имеет к,е Рис. 2.7. Сеть в задаче календарного планировании трудовых ресурсов. особый смысл, и в равд. 2.2 мы подробно остановимся на вопросах, связанных с ее использованием. На рис. 2.7 изображена сеть для рассматриваемого примера. Переменные здесь приписаны дугам, а величины предложения — узлам. Данная сеть во многом схожа с сетью, построенной нами при рассмотрении задачи о замене оборудования, за исключением дуг зь 2.1.8, ЗАДАЧА СОСТАВЛЕНИЯ РАСПИСАНИЯ ДВИЖЕНИЯ ТРАНСПОРТНЫХ СУДОВ На практике часто возникают задачи планирования работы транспортных средств, решение которых необходимо для усовершенствования процесса перевозки некоторого продукта из пунктов снабжения к пунктам потребления.
Частный случай такой задачи — составление расписания движения грузовых судов — связан с определением минимального числа судов, необходимого для выполнения плана перевозок к заданному сроку, и составлением оптимального маршрута их движения. Предположим, что вы являетесь владельцем судоходной компании, специализирующейся на перевозке скоропортящихся Глава г 40 Таблица гд. Исходные данные в задаче составления рисиисания движения грузових судов продуктов. Нескольким вашим клиентам потребовалось осуществить перевозку товара. Поскольку груз скоропортящийся, клиенты указывают точную дату перевозки. Если ваша компания не сможет перевезти груз в назначенный срок, то это будет сделано конкурирующей компанией.
Ниже описаны четыре, рейса (в каждом из которых суда загружаются полностью). В табл. 2.1 содержится информация о каждом рейсе. Первую строку таблицы можно интерпретировать следующим образом: в порту А имеется груз, который следует доставить в порт С на третий день (считая день выгрузки). Прибыль, получаемая от каждой перевозки, определяется доходами и эксплуатационными расходами, непосредственно связанными с данной перевозкой. Помимо эксплуатационных расходов компания платит постоянную сумму (5 единиц) за то, чтобы ввести судно в эксплуатацию. Следует также учитывать выплату компанией постоянной суммы, включающей накладные расходы и расходы, связанные с наймом новых членов экипажей судов. Время транспортировки (включая время на погрузку и разгрузку) определяется следующим образом: Пункт назначения с п А з г отправления В г Время, требуемое для возвращения судна (когда оно загружено только балластом), определяется следующим образом: Пунктотправления А В П у~к~ С г назначения В 41 Детеряинироеанна(е потока и сетяк При .рассмотрении данной задачи возникает несколько вопросов.
А именно, какие перевозки нам следует выполнять и сколько судов для этого потребуется? Сколько судов потребуется для того, чтобы выполнить все перевозки в заданные сроки? Для того чтобы ответить на эти вопросы, необходимо по- 3 4 5 6 7 8 Относительное время рис. 2.8 Задача составления расписания движения грузового судна. Жирными шрелками изображенм маршруты загруженного судна, следуюшего в одни из портов (узел), сплошными стрелками изображены маршруты разгруженного судна, следуюшего в один из портов для погрузки. Пунктирные стрелки вводятся для обозначения затрат, связанных с вводом судов в эксплуатацию (узел 3) и овончанием их работы (узел Т).
строить сеть, описывающую всевозможные расписания движения судов. Каждый узел данной сети соответствует некоторому порту и некоторому моменту времени. При данных обозначениях для каждого порта и момента прихода в него загруженного судна в сети имеется соответствующий им узел. То же справедливо и для каждого порта и момента начала погрузки в нем судна. Для удобства построения сети в нижней части рис. 2.8 изображена временная шкала. Жирные дуги соответствуют четырем рейсам, рассмотренным выше. Пропускная способность жирных дуг равна 1.
Все остальные дуги имеют бесконечную пропускную способность. Числа, приписанные дугам, представляют собой ненулевые стоимости. Глава 2 При завершении порожнего рейса судно может быть загружено и отправлено в какой-нибудь другой порт. Поскольку время, необходимое для того„чтобы судно возвратилось из порта С в порт В,,равно одному дню, в сеть включена дуга, соответствующая выходу судна из порта С в момент времени 3 и заходу его в порт В в момент времени 4. Остальные дуги, соединяющие конец одной жирной дуги, соответствующей транспортированию товара, с началом другой жирной дуги, изображают другие маршруты разгруженного судна, следующего в порт для того, чтобы загрузиться и совершить очередную перевозку. Для завершения построения сети вводятся два дополнительных узла. Источник 3 помещается в начало временнбй шкалы для обозначения начальной точки маршрута судов, а сток 1 — в конец шкалы для обозначения конечного пункта их движения.
Пунктирные дуги, исходящие из 3, соответствуют первому использованию судна. Дуги, заходящие в Т, соответствуют окончанию эксплуатации судна. Каждая цепь из источника в сток соответствует допустимому расписанию движения одного судна. Ответы на поставленные выше вопросы можно получить, решая задачу нахождения потока минимальной стоимости. Для того чтобы были учтены расходы, связанные с первым использованием судна, каждой дуге, всходящей из 3, приписана стоимость,,равная 5 единицам. Стоимость каждой дуги, соответствующей транспортировке товара, равна взятой со знаком минус величине прибыли, получаемой от данной перевозки.
Все остальные дуги имеют нулевую стоимость. Пропускная способность каждой дуги, соответствующей транспортировке товара, равна 1, поскольку существует только один рейс данного типа. Все остальные дуги имеют бесконечную пропускную способность. Если количество используемых судов равно М, то поток, величина которого также равна М, а стоимость минимальная, будет определять оптимальное расписание движения судов и перевозки, которые следует производить. Если количество судов выбирается, исходя из максимальной прибыли, то задача может быть решена путем определения зависимости прибыли от числа судов, Для нашего примера такая зависимость сведена в табл. 2.2. Расписание движения судов может быть составлено с помощью сети или непосредственно из исходных данных.
В рассматриваемом примере второе судно, выполняющее рейсы 3 и 2, начинает грузиться в порту В в нулевой момент времени для выполнения рейса 3. В порту 0 его разгрузка заканчивается в момент времени 3. Затем судно следует разгруженным в порт А и в момент времени 5 загружается там для выполнения рей- Детвриинированнмв потоки в сетях Таблица 2.2. Решения, зависящие от параметра, для задачи составления расписания движения грузовик судов са 2.
В порту С его,разгрузка заканчивается в момент времени 8. Методика решения рассмотренной здесь задачи используется также для определения оптимального маршрута движения автолавки при заданном множестве всех путей, ведущих к пунктам сбыта продукции. Затраты связаны с выполнением порожних рейсов, когда автолавка возвращается незагруженной в начальную точку маршрута. 2дтд МОДЕЛЬ ПРОИЗВОДСТВЕННОГО ПЛАНИРОВАНИЯ (СМИТА И ДЖОНСОНА) Предпринимателю необходимо удовлетворять спрос на продукцию в течение Т периодов [49]. Обозначим величины ожидаемого спроса в рассматриваемых периодах через 4, с(т,. „ Нт, где с(т — ожидаемый спрос в 1-м периоде. Предположим, что предприниматель может получать продукциею из Т, различных пунктов производства, или пунктов снабжения.
Пусть В» — максимальный объем продукции, которая может быть получена из 1-го пункта снабжения в 1-й период, а х»(1=1,2,..., А, 1'=1,...,Т) — объем продукции, действительно получаемой из 1-го пункта снабжения в )ьй период. Таким образом, х» — искомые значения переменных. Пусть с» †затра, необходимые для получения единицы продукции из (-го пункта снабжения в 1-й период, а с, — издцржки хранения единицы продукции в течение одного периода. Предполагается, что вместимость товарных складов достаточно большая и поэтому можно не накладывать ограничений на объем хранимой в них продукции.
И наконец, через То обозначим запас продукции, имеющий~я в начальный момент периода планирования. Для математического описания данной модели будет полезно иметь выражение объема запасов продукции на конец каждого периода 1. Обозначая эту величину через Уь имеем !с=!о+Х'г=ьос;,х» — Х'т=,с(ь 1=1, 2, ..., Т.
Здесь следует отметить, что если величины х» выбраны таким образом, что )~)0 при всех с, то спуос будет удовлетворяться в каждый период. 44 Глава 2 Теперь задачу можно сформулировать следующим образом: найти неотрицательные величины хп, при которых функция т т г-т т,р„ч., т!г,ч-т т — тв) ! ! ! ! принимает минимальное значение. Первое слагаемое в целевой функции (2.18) представляет собой затраты, необходимые на получение продукции из пунктов снабжения, второе слагаемое соответствует издержкам сЛгг=!!с хранения продукции за весь период планирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
