Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения






Скачать 419.77 Kb.
НазваниеКурсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения
страница5/7
Дата публикации01.11.2013
Размер419.77 Kb.
ТипКурсовой проект
top-bal.ru > Спорт > Курсовой проект
1   2   3   4   5   6   7
^

2.3. Понятие потенциала и цикла


 

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

Циклом пересчета или короче, циклом в таблице перевозок называется последовательность неизвестных, удовлетворяющая следующим условиям:

1.     Одно из неизвестных последовательности свободное, а все остальные – базисные.

2.     Каждые два соседних в последовательности неизвестных лежат либо в одном столбце, либо в одной строке.

3.     Три последовательных неизвестных не могут находиться в одном столбце или в одной строке.

4.     Если, начиная с какого-либо неизвестного, мы будем последовательно переходить от одного к следующему за ним неизвестному то, через несколько шагов мы вернемся к исходному неизвестному.

Второе условие означает, что у двух соседних неизвестных в цикле либо первые, либо вторые индексы одинаковы.

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

Можно доказать, что для любой свободной клетки таблицы перевозок существует один и только один цикл, содержащий свободное неизвестное из этой клетки, и что число вершин в цикле всегда четно.

Так, например, в таблице перевозок, составленной по диагональному методу при решения задачи из предыдущего пункта, неизвестному x21 соответствует цикл x21,x23,x13,x11,x21 и т.д.

Пусть теперь мы имеем некоторую свободную клетку с соответствующим ей циклом. Если мы изменим значение свободного неизвестного, увеличив его на некоторое число x, то, переходя последовательно от одной вершины цикла к другой, мы должны будем в силу неизменности сумм по строкам и по столбцам поочередно уменьшать и увеличивать значения неизвестных в цикле на то же число x. Например, в указанном выше цикле для свободного неизвестного x21 получим:

старые значения: x21= 0, x23= 80, x13= 20,x11= 170, x21= 0;

новые значения:

Очевидно, если снабдить вершины цикла поочередно знаками "+" и "–", приписав вершине в свободной клетке знак "+", то можно сказать, что в вершинах со знаком "+" число x прибавляется к прежнему значению неизвестного, находящегося в этой вершине, а в вершинах со знаком "–" это число x вычитается из прежнего значения неизвестного, находящегося в этой вершине.

Замечание. Так как число вершин в цикле всегда четно, то, возвращаясь в свободную клетку, мы должны будем приписать ей знак "+", т. е. тот знак, который ей уже приписан при выходе из нее. Это очень существенное обстоятельство, так как иначе мы пришли бы к противоречию. Безразлично также, в каком направлении обходится цикл при “означивании” вершин.

Если в качестве x выбрать наименьшее из чисел, стоящих в вершинах, снабженных знаком "–", то, по крайней мере, одно из прежних базисных неизвестных примет значение нуль, и мы можем перевести его в число свободных неизвестных, сделав вместо него базисным то неизвестное, которое было свободным.

Так, например, в рассмотренном выше цикле имеем отрицательные вершины x21 и x11 ; следовательно, выбрав х = min {80; 170} = 80 , мы получаем:

старые значения: x21= 0, x23= 80, x13= 20,x11= 170, x21= 0;

новые значения:

т. е. вместо прежнего базисного решения получаем новое базисное решение:
 

Выбор в качестве x минимального среди чисел, стоящих в отрицательных вершинах цикла, обеспечивает допустимость нового базиса.

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

Может случиться, что и само минимальное значение среди чисел в отрицательных клетках равно нулю. Тогда преобразование таб­лицы перевозок сведется к перестановке этого нуля в свободную клетку. Значения всех неизвестных при этом остаются неизменными, но решения считаются различными, так как различны базисы. Оба решения вырождены.

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

Заметим, что неизвестные, не входящие в цикл, этим преобразованием не затрагиваются, их значения остаются неизменными и каж­дое из них остается либо в группе базисных, либо в группе свобод­ных неизвестных, как и до пересчета.

Выясним теперь, как пересчет по циклу влияет на общий объем затрат на перевозки и при каком условии эти затраты становятся меньше.

Пусть xpq – некоторое свободное неизвестное, для которого мы построили цикл и осуществили пересчет по циклу с некоторым числом x. Если вершине цикла, находящейся в i строке и j столбце таблицы перевозок, приписан знак "+", то значение неизвестного xij , находящегося в этой вершине, увеличивается на x, что в свою очередь вызывает увеличение затрат на cij x, где cij – тариф, соответствующий этой клетке; если же указанной вершине приписан знак “–”, то значение неизвестного xij уменьшается на x, что вызывает уменьшение затрат на cij x.

Сложим тарифы, соответствующие положительным вершинам цикла, и вычтем из этой суммы сумму тарифов, соответствующих отрицательным вершинам цикла; полученную разность Spq назовем алгебраической суммой тарифов для данного свободного неизвестного xpq . Подсчет алгебраической суммы тарифов можно истолковать и так: припишем тарифам те же знаки, которые приписаны соответствующим вершинам цикла, тогда алгебраическая сумма тарифов равна сумме таких тарифов со знаком (“относительных тарифов”).

Теперь, очевидно, мы можем, заключить, что в целом при пере­счете но циклу, соответствующему свободному неизвестному xpq общий объем затрат на перевозки изменится на произведение алгеб­раической суммы тарифов на x, т. е. на величину Spqx . Следовательно, если алгебраическая сумма тарифов для некоторого свобод­ного неизвестного xpq отрицательна (Spq < 0), то пересчет по циклу, соответствующему этому неизвестному, приводит к уменьшению общей суммы затрат на реализацию плана перевозок. Если же алгебраическая сумма тарифов положительна (Spq > 0), то пересчет по соответствующему циклу приведет к увеличению общей суммы затрат. И, наконец, если алгебраическая сумма тарифов равна нулю (Spq = 0), то пересчет по соответствующему циклу не изменит общую сумму затрат (два различных базисных плана требуют одинаковых затрат на их реализацию).

Так, например, для цикла x21,x23,x13,x11,x21 в рассмотренной задаче алгебраическая сумма тарифов

 .

Значит, пересчет по этому циклу снижает расходы. И действитель­но, осуществив такой пересчет, мы получаем план, по которому объем перевозок в тонно-километрах составляет

 

тогда как по исходному плану он составил S1= 30650. Имеем снижение объема перевозок на 1200 тонно-километров, что и следовало ожидать, так как алгебраическая сумма тарифов в дан­ном случае равна –15, а пересчет по циклу осуществляется с помощью числа х = 80 (изменение затрат равно -15*80 = - 1200).

Вычисление алгебраической суммы тарифов для каждого из сво­бодных неизвестных можно производить без построения соответ­ствующего цикла, пользуясь, так называемыми, потенциалами. При­пишем каждой базе Ai, , некоторое число ui, и каждому потребителю Bj некоторое число vj :

 ,

так что 

ui, + vj = cij , (3.6)  

где cij – тарифы, соответствующие клеткам, заполненным базис­ными неизвестными. Эти числа ui, и vj называются потенциалами соответствующих баз и потребителей.

Зная потенциалы, легко вычислить алгебраическую сумму тари­фов. Действительно, если в алгебраической сумме тарифов по циклу, соответствующему свободному неизвестному xpq , заменить тарифы базисных клеток их выражениями через потенциалы по формулам (3.6), то, в силу чередования знаков при вершинах цикла, все потенциалы, кроме up и vq сократятся, и мы получим:

Spq = cpq - ( up + vq ).

Так, например, для цикла x21,x23,x13,x11,x21 в рассмотренной выше задаче имеем

.

Для базисных клеток сумма потенциалов строки и столбца, в которых находится эта клетка, равна тарифу, соответствующему этой клетке; если же клетка для неизвестного xpq свободная, то сумму потенциалов

(3.7)

называют косвенным тарифом этой клетки. Следовательно, алгеб­раическая сумма тарифов для свободной клетки xpq равна разности ее настоящего (“истинного”) и косвенного тарифов:

(3.8)

Из (3.8) следует, что если косвенный тариф для данной свобод­ной клетки больше её истинного тарифа, то алгебраическая сумма тарифов по циклу, соответствующему этой клетке, будет отрица­тельна; если же косвенный тариф меньше истинного, то алгебраи­ческая сумма тарифов положительна, и, наконец, если косвенный тариф равен истинному, то алгебраическая сумма тарифов равна нулю.

Потенциалы можно найти из системы равенств (3.6), рассматри­вая их как систему (m + n - 1) уравнений с m+n неизвестными. Так как неизвестных здесь на единицу больше, чем уравнений, то, по крайней мере, один из потенциалов мы можем выбрать произвольно, положив, например, u1 = 0; тогда остальные потенциалы легко опре­деляются из уравнений (3.6).

Например, для плана, полученного по диагональному методу в рассмотренной выше задаче, имеем



Система содержит семь уравнений с восемью неизвестными. Выбирая произвольно значение , находим последовательно из пер­вых трех уравнений значения , затем из четвертого уравнения – , из пятого уравнения – , из шестого уравнения и, наконец, из седь­мого уравнения – .

Положив, например, u1 = 0 , получаем значения потенциалов:



Найдем теперь косвенные тарифы для свободных клеток и сравним их с истинными тарифами: 

 

Для клеток с неизвестными x21 и x32 косвенные тарифы больше истинных. Следовательно, для них мы будем иметь отрицательные алгебраические суммы тарифов: 

 

Значение S21 = -15 мы уже имели раньше, вычисляя алгебраиче­скую сумму тарифов для этой клетки непосредственно по циклу.

Замечание 1. Подсчитывая косвенные тарифы как суммы соответ­ствующих потенциалов, полезно не пропускать и клетки с базисны­ми неизвестными (заполненные клетки). Для этих клеток сумма потенциалов равна истинному тарифу; последнее может служить проверкой правильности найденных значении потенциалов.

Замечание 2. Можно показать, что если сумму всех затрат по данному плану перевозок выразить черех свободные неизвестные, то коэффициент при каждом из таких неизвестных будет равен алгебраической сумме тарифов по циклу, соответствующему ей в таблице перевозок. Это еще раз подтверждает, что пересчет по циклам является специфической формой применения симплекс-метода к решению транспортной задачи.
1   2   3   4   5   6   7

Похожие:

Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения iconРабочая учебная программа по дисциплине Теория информации и кодирования
«Теория информации и кодирования». Теория информации исследует общие закономерности информационных процессов, позволяет оценить качество...

Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения iconРабочая программа дисциплины Теория оптимальных процессов Направление...
Дисциплина «Теория оптимальных процессов» (годовой спецкурс) является частью математического цикла ооп. Дисциплина реализуется на...

Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения iconМетодические рекомендации по написанию курсовой работы по дисциплине «Экономическая теория»
Невская, Н. А. Методические рекомендации по написанию по написанию курсовой работы по дисциплине «Экономическая теория» для студентов...

Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения iconУчебно-методический комплекс по дисциплине теория систем и системный анализ для специальности
Целью изучения данной дисциплины является рассмотрение теоретических основ и закономерностей построения и функционирования систем,...

Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения icon08. 00. 01 Экономическая теория
Микроэкономическая теория: теория потребительского спроса; теория фирмы; теория организации рынков; теория конкуренции и антимонопольного...

Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения iconЛекции по курсу «теория автоматического управления» теория нелинейных систем автоматического
Рассмотрим особые точки и фазовые портреты линейных систем, математическими моделями которых являются дифференциальные уравнения...

Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения iconЛекции по курсу «теория автоматического управления» теория нелинейных систем автоматического
Рассмотрим особые точки и фазовые портреты линейных систем, математическими моделями которых являются дифференциальные уравнения...

Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения iconКурс. 01;Мпк. 01;3 методическое пособие по курсовой работе теория перевода
Методическое пособие предназначено для студентов, обучающихся по направлениям “Лингвистика” 031100. 62, руководителей курсовых работ...

Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения iconУчебно-методический комплекс по дисциплине теория алгоритмов
Курс "Теория алгоритмов" рассчитан на один семестр и призван упрочить фундамент специальной подготовки будущих педагогов, способствовать...

Курсовой проект по дисциплине “Теория информационных систем” тема: Теория транспортных сетей с различными транспортными издержками. Поиск оптимальных маршрутов снабжения iconУчебно-методический комплекс по дисциплине теория алгоритмов
Курс "Теория алгоритмов" рассчитан на один семестр и призван упрочить фундамент специальной подготовки будущих педагогов, способствовать...



Школьные материалы


При копировании материала укажите ссылку © 2018
контакты
top-bal.ru

Поиск