Материал: конспект 3

Условием совместимости транспортной системы ограничений является наличие баланса

количество груза = количеству потребителей (5)

Если условие (5) выполняется, то математическая модель ТЗ называется закрытой. Если условие (5) не выполняется, то математическая модель ТЗ называется открытой.

Заметим, что открытую модель всегда можно привести к ее закрытому виду. Допустим, что , тогда в распределительную таблицу ТЗ вводится фиктивный (n + 1) пункт потребителя с потребляемостью соответственно в . В то же время тарифы для данного пункта.

С точки зрения математики такой подход позволяет сформулировать метематическую модель закрытой и весь груз по задаче будет перевозиться. Однако с точки зрения экономики часть груза будет оставаться на своих местах.

Особенности математической модели ТЗ:

1. Представлена 1-ой канонической формой.

2. Коэффициенты при неизвестных в ограничениях =1.

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

4. Ранг системы ограничений ТЗ ч = m + n –1.

5. Всего в ТЗ будет переменных, из них базисных , а свободных .

Вывод. Представленный анализ математической модели ТЗ показывает, что такая задача может решаться симплексной процедурой. Однако особенности ее математической модели позволили разработать более простые и удобные методы для решения такой задачи, а именно:

— венгерский метод;

— метод дифференциальных рент;

— метод потенциала.

Одним из наиболее простых является метод потенциала.

Метод потенциала

Предварительные сведения и понятия:

1. Любую совокупность клеток распределительной таблицы называют набором.

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

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

Необходимо различать базисные и небазисные клетки распределения таблицы ТЗ. В базисных клетках всегда записываются положительные значения перевозок. Количество базисных клеток должно быть равно . Небазисные клетки пустые с точки зрения перевозок.

Заметим, если количество базисных клеток , то ТЗ называют вырожденный.

Для устранения процедуры вырожденности в состав базисных клеток включают небазисные, но значение перевозок здесь = 0.

Если набор базисных клеток не содержит не одного цикла, то план ТЗ называется ациклическим.

Теорема (об оптимальном плане ТЗ)

Предварительные сведения. Составим математическую модель ТЗ

(2)

(3)

U_i

V_i

(4)

По отношению к задаче (1)—(4) составляют двойственную

(5)

(на все переменные накладывается условие (6)

неотрицательности)

Учитывая, что U_i и U_j могут иметь любые знаки и для аналогичных двойственных переменных с разностью потенциалов, переменным U_i присваивают знак «–», тогда двойственная задача приобретает вид

(7)

(8)

Теорема

Для того, чтобы некоторый план (размерности) был оптимально необходимым и достаточным, надо чтобы для него существовала система чисел U_i и U_j, причем таких чисел, чтобы выполнялись условия

(9)

для клеток небазисного набора и

(10)

для клеток базисного набора.

Здесь числа U_i и U_j соответственно называются потенциалами пунктов отправления и потенциалами пунктов назначения. Тогда условия (9) и (10) называются условиями потенциальности клеток небазисного набора (9) и базисного набора (10).

В связи с отмеченным теорему об оптимальном плане ТЗ в компактном виде можно представить следующим образом.

Теорема

Для того, чтобы некоторый план ТЗ был оптимально необходимым и достаточным, чтобы он был потенциальным.

Доказательство. Пусть есть некоторый оптимальный план, тогда в соответствии с 1 теоремой теории двойственности имеют . В то же время в соответствии со 2 теоремой теории двойственности система ограничений и прямой и двойственной задач будут удовлетворяться условиями дополнительной нежесткости Слейтера. Укажем условия ДНС для двойственной задачи

.

Вполне очевидно, что для базисного набора клеток , т. к. в клетках указано положительное значение перевозок. Тогда, чтобы выполнялось УДНС необходимо и достаточно, чтобы для базисного набора клеток выражение в скобках превращалось бы в 0, т. е. .

В то же время для небазисного набора клеток . Это означает, что выражение в скобках может быть любым (в рамках допустимого плана). Тогда для небазисного набора клеток на оптимальном плане должно выполняться соотношение вида . Теорема доказана.

Алгоритм метода потенциала состоит из 2-х шагов: предварительного и общего повторяющегося.

Предварительный шаг:

1. Составляют первоначальный опорный план.

2. Составляют первоначальную систему потенциалов.

3. Проверяют план на потенциальность.

Вполне очевидно, что если план потенциальный, то он оптимальный, тогда на этом этапе завершают решение задачи.

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

Общий повторяющийся шаг:

1. Перестраивают опорный план с целью его совершенствования (улучшения).

2. Перестраивают систему потенциалов.

3. Проверяют план на потенциальность.

Заметим, что метод потенцирования сходится и притом всегда за конечное число итераций.

Методы составления первоначального опорного плана

Для опорных планов ТЗ предъявляются следующие требования:

1. Должна удовлетворяться система ограничений.

2. Количество базисных клеток должно быть равно . Если такое условие невыполняется, то в состав базисного набора клеток вводят дополнительные клетки небазисного набора, но с нулевыми значениями перевозок. Именно таким образом и устраняется процедура вырожденности ТЗ.

3. Базисный набор клеток ТЗ должен быть ациклическим. Это означает методы составления правила северо-западного угла.

Методы составления правила северо-западного угла

Метод, который называется правилом северо-западного угла, является одним из наиболее простых методов составления первоначального опорного плана.

Рассмотрим распределительную таблицу ТЗ

Такая таблица начинает заполняться с левого верхнего угла (с северо-запада). Принцип заполнения выражается соотношением

Анализируем соотношение между а₁ в₁ и далее процесс заполнения клеток развивается по строке вправо, либо по строке вниз. Допустим,

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

Особенности метода:

1. Такого характера методы еще называются диагональными, поскольку порядок заполнения клеток переменными с левого верхнего угла до правого нижнего.

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

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

Метод наименьшей стоимости

Количество итераций при решении ТЗ можно упростить, если первоначальный опорный план строить по более усовершенствованному методу — методу наименьшей стоимость.

Суть — на І этапе осуществления, максимально возможная поставка в клетку с наименьшим тарифом, а остаток если получается, распределяется по строке или столбцу.

Особенность — он учитывает значения тарифов, а это означает, что построенный опорный план будет более близок к оптимальному, чем план, сформированный по методу северо-западного угла.

Пример

Построить первоначальный опорный план для ТЗ по методу северо-западного угла и методом наименьшей стоимости.