Logo GenDocs.ru

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

Загрузка...

Лекции по ТПР - файл Лекция№05-тпр.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скачать

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

Лекция №5.

Решение ТЗ в сетевой постановке методом буферного запаса.

Построение ММ. При этом методе решения ТЗ узлы ТС классифицируются следующим образом:

  1. Узел i называется источником, если существуют только выходящие из него дуги.

  2. Узел i называется стоком, если существуют только входящие в него дуги.

  3. Узел i называется промежуточным, если существуют и входящие в него, и исходящие из него дуги.

Обозначим: - множество истоков сети.

- множество стоков сети.

- множество промежуточных узлов сети.

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

Введем дополнительные обозначения:

- множество всех дуг сети,

- множество дуг, входящих в узел i.

- множество дуг, исходящих из узла i.

Пусть - объем перевозок по дуге . Тогда ММ ТЗ в сетевой постановке запишется:

(1)

(2)

(3)

(4)

(5)

В ММ целевая функция (1) выражает суммарную стоимость перевозок на сети. Ограничения (2) требуют вывозить все излишки продукции из узлов-истоков, а ограничения (3) – потребности всех узлов-стоков д.б. удовлетворены. Ограничения (4) для промежуточных узлов отражает тот факт, что разность между объемами вывозимой и ввозимой продукции должна равняться запасу продукции в этом узле (если в узле имелся избыток, то он будет вывезен, если недостаток- он удовлетворен).

ММ (1)-(5) относится к классу ЗЛП и может быть решена стандартными методами решения ЗЛП. Однако, если учитывать особенности ограничений (2)-(5), можно эту задачу свести к модели КТЗ. Тогда модель (1)-(5) будет решаться более эффективно методом потенциалов.

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

Преобразуем данные ограничения таким образом, чтобы они не выводили задачу за рамки КТЗ.

Будем считать, что в каждом промежуточном пункте возможна перевозка со стоимостью перевозки единицы продукции . Также введем обозначения - буферный запас, т.е. общий объем излишков продукции.

Теперь уравнение (4) перепишем в виде:

(6)

Разобьем это уравнение на два:

(7)

(8)

(9)

Уравнение (7) аналогично уравнениям (2), т.е. объем вывозимой продукции из узла равен имеющемуся там запасу . Уравнение (8) аналогично уравнениям (3), т.е. объем ввозимой продукции в узел равен потребности этого узла В.

Теперь вместо исходной модели рассмотрим ММ (1)-(3), (5), (7)-(9). Это модель КТЗ, в которой пунктами производства являются все источники с объемами производства и все промежуточные пункты с объемами производства , а пунктами потребления являются все стоки с объемами потребления и все промежуточные пункты с объемами потребления В.

Допустим, эта модель КТЗ решена и найдены оптимальные значения и . Будут ли значения и образовывать решение исходной модели (1)-(5). ДА! Положительный ответ на этот вопрос дает тот факт, что задача (1)-(5) эквивалентна задаче (1)-(3), (5), (7)-(9). Покажем, что это действительно так.

Пусть удовлетворяет ограничениям (2)-(5), тогда они удовлетворяют ограничениям и второй задачи (2),(3), (5), (7)-(9). Из уравнения (8) следует, что

(10)

Знак 0 следует из того, что суммарный объем ввоза в любой узел не может быть больше буферного запаса В. Т.о. выполняется ограничение (9).

Подставляя (10) в (7), получим тождество:

(11)

т.е. получим уравнение (4), которое удовлетворяется в силу того, что удовлетворяет ограничениям (4). Следовательно, удовлетворяет и ограничениям (7)-(9). Остальные ограничения (2), (3) являются общими для обеих задач. Следовательно, допустимые планы исходной задачи являются допустимыми и для (1)-(3), (5), (7)-(9).

Аналогично доказывается, что если и удовлетворяют ограничениям второй задачи, то они удовлетворяют и ограничениям первой задачи (1)-(5). Для этого достаточно вычесть из (7) уравнение (8). В результате получается уравнение (4).

В обеих задачах минимизируется одна и та же целевая функция. Т.О. (1)-(5) эквивалентна (1)-(3), (5), (7)-(9).

Сравнение методов путей минимальной стоимости и буферного запаса.

При методе поиска кратчайшего пути пунктами производства являются пункты с положительными запасами, а пунктами потребления – с отрицательными. Обычно таких узлов в сети значительно меньше общего числа узлов. Поэтому получаемая в результате КТЗ имеет меньшую размерность, чем при методе буферного запаса. Так как в методе БЗ промежуточные пункты выступают и как пункты производства, и как пункты потребления. Однако в первом случае необходимо предварительно решать столько задач поиска кратчайших путей, сколько имеется в сети пар узлов с положительными и отрицательными запасами.

Кроме того, очень часто встречаются ТЗ, в которых наложены ограничения на пропускную способность дуг:

.

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


^ Задача поиска кратчайшего пути на транспортной сети.

Постановка задачи. Пусть дана некоторая транспортная сеть как совокупность узлов с номерами и множества дуг D, соединяющих между собой некоторые узлы сети. Длина дуги равна . На сети выделены узел r- начало пути, и узел s- конец пути. Требуется найти путь из узла r в узел s, имеющий минимальную длину, т.е. кратчайший путь.

Построение ММ. Для составления ММ задачи вводится переменная .

Тогда ММ задачи будет иметь вид:

(1)

(2)

(3)

(4)

(5)

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

Таким образом, задача о кратчайшем пути свелась к ММ (1)-(5), которая относится к классу задач булевского программирования. Самый простой (но не самый эффективный) способ ее решения состоит в рассмотрении ее как транспортной задачи в сетевой постановке. Действительно, ограничения (2)-(4) аналогичны ограничениям транспортной задачи с единственным пунктом r с положительным запасом и с единственным пунктом s с отрицательным запасом (потребностью) . Промежуточные узлы имеют нулевой запас . В свою очередь эту задачу методом буферного запаса можно привести к КТЗ, в которой в качестве пунктов производства выступают узел r и все промежуточные узлы с запасом продукции, равным буферному запасу , а в качестве пунктов потребления – s с потребностью и все ром. узлы с запасом продукции . В результате приведения к КТЗ получаем модель задачи о назначениях, где заказы- это пункты производства, а исполнители- это пункты потребления.

Однако существует более эффективный метод решения задачи (1)-(5), основанный на рассмотрении двойственной задачи.


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

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

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